關於 JavaScript Object-keys-- 排序問題的探索

利用 Object.keys 取得對象所有屬性的 key ，然後進行 map 操作是 JavaScript 開發者常用的方法。但你是否思考過 key list 是依據什麼順序排列的呢？

一、背景

近期維護輔導 App 內嵌 WebView 頁面調 native 拍照上傳的業務時，遇到一個詭異的兼容 Bug：iOS 端新提交的圖片偶現順序不一致的問題，但 Android 端一切正常。

首先簡單梳理下拍照上傳的關鍵業務邏輯：

JS 側用一個 Object 保存各個圖片的信息，拍照上傳後 native 會觸發 JS 的回調回傳對應圖片 URL，其中以 unix 時間戳作爲 tag，區分不同的圖片拍照任務，以 tag 爲 key 存入 Object 中；
對於在本次 WebView 會話之前已提交過的圖片，則通過 sha256 取已有的圖片 URL 的哈希生成 tag，往 Object 存入對應圖片信息。
提交時會用 Object.keys() 方法獲得 Object 中所有的 tag，再 map 到對應的圖片 URL 列表提交到後臺。

定位了一波發現原因是：Android 與 iOS 客戶端給到的 tag 存在差異，Android 傳來了毫秒級的時間戳，iOS 傳來的是秒級的時間戳。當 iOS 端以秒級時間戳作爲 tag 插入時，這個新的圖片地址自動排在了最前面。

原邏輯較爲複雜，簡化復現此問題的代碼如下：

function getNewUrlList(oldTagUrlMap, newUrl, newTag) {
  const newMap = {
    ...oldTagUrlMap,
    [newTag]: newUrl,
  };
  return Object.keys(newMap).map((tag) => newMap[tag]);
}

const originTagUrlMap = {
  'aaaaa': "https://xxx/1.jpg",
  'bbbbb': "https://xxx/2.jpg",
};

// native 回傳的新拍攝圖片的 URL
const newUrl = "https://xxx/3.jpg";
// Android 回調的 tag
const newTagAndroid = "1612076930661";
// iOS 回調的 tag
const newTagIOS = "1612076930";

console.log(getNewUrlList(originTagUrlMap, newUrl, newTagAndroid));
console.log(getNewUrlList(originTagUrlMap, newUrl, newTagIOS));

運行發現兩個回調 Tag 生成的 urlList 不一致：

[ 'https://xxx/1.jpg', 'https://xxx/2.jpg', 'https://xxx/3.jpg' ] // Android 回調
[ 'https://xxx/3.jpg', 'https://xxx/1.jpg', 'https://xxx/2.jpg' ] // iOS 回調

可以確定一點：Object.keys() 的返回並不總能保持先來後到的順序。從解決業務需要的角度，我們可以通過維護一個單獨的 tag 數組來回避這個問題。

從徹底解決問題的角度出發，這裏冒出兩個疑問點：

Object.keys() 的排序機制是什麼樣的？
爲什麼毫秒時間戳作爲 key 的時候輸出的是正常的先來後到順序？

接下來也正是針對這兩點問題的探索和發現。

二、Object.keys() 的排序機制

《現代 JavaScript 教程》的 Object 章節裏對這個話題有一句簡單的概括：

integer properties are sorted, others appear in creation order.

當 key 整數類型會做一層排序，其他類型則按創建順序來排。

在《你不知道的 JavaScript》中是這麼描述的：

在 ES6 之前，羅列一個對象的鍵 / 屬性的順序沒有在語言規範中定義，而是依賴於具體實現的。一般來說，大多數引擎會以創建的順序來羅列它們，雖然開發者們已經被強烈建議永遠不要依仗這種順序。

在 ES6 中，羅列直屬屬性的屬性是由[[OwnPropertyKeys]]算法定義的（ES6 語言規範，9.1.12 部分），它產生所有直屬屬性（字符串或 symbol），不論其可枚舉性。這種順序僅對Reflect.ownKeys(..)有保證。

這個順序是：

首先，以數字上升的順序，枚舉所有數字索引的直屬屬性。

然後，以創建順序枚舉剩下的直屬字符串屬性名。

最後，以創建順序枚舉直屬 symbol 屬性。

教程文檔的細節說的不太明確，尋找 ES6 標準中 Object.keys() 算法的定義，原文如下：

When the abstract operation EnumerableOwnNames is called with Object O the following steps are taken:

Assert: Type(O) is Object.

Let ownKeys be O.[OwnPropertyKeys].

ReturnIfAbrupt(ownKeys).

Let names be a new empty List.

Repeat, for each element key of ownKeys in List order

Let desc be O.[GetOwnProperty].

ReturnIfAbrupt(desc).

If desc is not undefined, then

If desc.[[Enumerable]] is true, append key to names.

If Type(key) is String, then

Order the elements of names so they are in the same relative order as would be produced by the Iterator that would be returned if the [[Enumerate]] internal method was invoked on O.

Return names.

NOTEThe order of elements in the returned list is the same as the enumeration order that is used by a for-in statement.

其中獲取 ownKeys 時，依賴了 ES6 標準中定義的 [[OwnPropertyKeys]] 算法，標準原文對該算法的描述如下：

When the [[OwnPropertyKeys]] internal method of O is called the following steps are taken:

Let keys be a new empty List.

For each own property key P of O that is an integer index, in ascending numeric index order

Add P as the last element of keys.

For each own property key P of O that is a String but is not an integer index, in property creation order

Add P as the last element of keys.

For each own property key P of O that is a Symbol, in property creation order

Add P as the last element of keys.

Return keys.

到這裏，對問題 1 我們已經有了一個大概的印象：Object.keys() 在執行過程中，若發現 key 是整數類型索引，那它首先按照從小到大排序加入；然後再按照先來先到的創建順序加入其他元素，最後加入 Symbol 類型的 key。

三、key 何時會被識別爲 “整數”？

對於未知事物，並不可能都通過有限的已知推導出來，需要引入新的信息去解決。至於如何引入，很大程度也需要靠想象力與直覺去猜想，然後做實驗驗證才能發現。看到這裏的問題，聯想到 Unix 時間戳本身是一個 32 位 int 整型，直覺告訴我，會不會有什麼關於 32 位整數的限定？

開始驗證這個猜想。這裏我們可以通過控制 tag 的數字大小，來確定是否觸發整數排序的邊界值。嘗試給時間戳的十進制數字加一位（例如 16120769300），發現排序失效，這說明邊界值在這兩者之間。經過多次嘗試，最後發現邊界值恰好是 4294967295，即 (1 << 32) - 1、32 位無符號整數的最大值，與猜想恰好相符。

猜想得到肯定，接下來尋找資料，確認 JS 語言是否真的如此設計。再回到 ES6 標準文檔，經過一番搜索和查找，關注點鎖定在了 ECMA-262 6.1.7 The Object Type 提到的 integer index 這一概念：

An integer index is a String-valued property key that is a canonical numeric String (see 7.1.16) and whose numeric value is either +0 or a positive integer ≤ 2^53−1. An array index is an integer index whose numeric value i is in the range +0 ≤ i < 2^32−1.

這裏遇到一個問題，ES6 標準文檔在 [[OwnPropertyKeys]] 裏面描述的是 integer index，而我們這裏的實現中用的是 array index，存在矛盾。

帶着問題一番搜索，發現已有人提過類似問題，還有標準文檔的改動 PR。

javascript - Object.keys order for large numerical indexes? - Stack Overflow
Normative: Use array indices instead of integer indices in OrdinaryOwnPropertyKeys by mathiasbynens · Pull Request #1242 · tc39/ecma262

對應 ECMA-262 最新版的 9.1.11.1 OrdinaryOwnPropertyKeys 的更新：

Let keys be a new empty List.

For each own property key P of O such that P is an array index, in ascending numeric index order, do

Add P as the last element of keys.

For each own property key P of O such that Type(P) is String and P is not an array index, in ascending chronological order of property creation, do

Add P as the last element of keys.

For each own property key P of O such that Type(P) is Symbol, in ascending chronological order of property creation, do

Add P as the last element of keys.

Return keys.

到這裏問題 2 其實也有了完整的解釋：毫秒的時間戳已不滿足 array index 的條件，引擎便按照 string 的先來後到順序來處理。

四、JS 引擎相關源碼

光看標準文檔畢竟還是紙上談兵，存在代碼實現與文檔不一致的可能（比如剛剛的發現），嘗試挑戰看看現有 JS 引擎的底層實現。由於 V8 本身做了好多優化，之前也沒讀源碼的經驗，暫時難以下手，只能先試試 “ VSCode 字符串搜索大法”。聽聞 Fabrice Bellard 大神的 QuickJS 只幾萬行代碼就完整支持了 ES2020 標準，決定先從代碼量小一些的 QuickJS 出發，然後大概看看 V8 的實現。

QuickJS 的 Array Index 排序實現

QuickJS 的實現在 quickjs.c 的 7426 行的 JS_GetOwnPropertyNamesInternal 方法中，判斷是否爲 array index 的邏輯位於 quickjs.c:7471 的 JS_AtomIsArrayIndex 方法。

// 位於 quickjs.c:3104
/* return TRUE if the atom is an array index (i.e. 0 <= index <=
   2^32-2 and return its value */
static BOOL JS_AtomIsArrayIndex(JSContext *ctx, uint32_t *pval, JSAtom atom)
{
    if (__JS_AtomIsTaggedInt(atom)) {
        *pval = __JS_AtomToUInt32(atom);
        return TRUE;
    } else {
        JSRuntime *rt = ctx->rt;
        JSAtomStruct *p;
        uint32_t val;

        assert(atom < rt->atom_size);
        p = rt->atom_array[atom];
        if (p->atom_type == JS_ATOM_TYPE_STRING &&
            is_num_string(&val, p) && val != -1) {
            *pval = val;
            return TRUE;
        } else {
            *pval = 0;
            return FALSE;
        }
    }
}

其中調用的 is_num_string 承擔了判斷的任務：

// 位於 quickjs.c:2398
/* return TRUE if the string is a number n with 0 <= n <= 2^32-1 */
static inline BOOL is_num_string(uint32_t *pval, const JSString *p)
{
    uint32_t n;
    uint64_t n64;
    int c, i, len;

    len = p->len;
    if (len == 0 || len > 10)
        return FALSE;
    if (p->is_wide_char)
        c = p->u.str16[0];
    else
        c = p->u.str8[0];
    if (is_num(c)) {
        if (c == '0') {
            if (len != 1)
                return FALSE;
            n = 0;
        } else {
            n = c - '0';
            for(i = 1; i < len; i++) {
                if (p->is_wide_char)
                    c = p->u.str16[i];
                else
                    c = p->u.str8[i];
                if (!is_num(c))
                    return FALSE;
                n64 = (uint64_t)n * 10 + (c - '0');
                if ((n64 >> 32) != 0)
                    return FALSE;
                n = n64;
            }
        }
        *pval = n;
        return TRUE;
    } else {
        return FALSE;
    }
}

掃了一遍 array index 類型的 key 以後， JS_GetOwnPropertyNamesInternal 判斷這部分 key 的數量，若存在 array index 的 key，則調用 rqsort 方法對這部分 key 進行排序，最後返回。

if (num_keys_count != 0 && !num_sorted) {
    rqsort(tab_atom, num_keys_count, sizeof(tab_atom[0]), num_keys_cmp,
           ctx);
}

V8 的排序實現

V8 的代碼沒看的很懂（畢竟還只是 VSCode 查找大法水平），搜索了一堆文章，克隆了 Node 的 v12.x 源碼看其中的 deps/v8 部分。找到其中字符串類定義的判斷與轉換 array index 類型的方法。

// 位於 deps/v8/src/objects/string-inl.h:773
bool String::AsArrayIndex(uint32_t* index) {
  uint32_t field = hash_field();
  if (IsHashFieldComputed(field) && (field & kIsNotArrayIndexMask)) {
    return false;
  }
  return SlowAsArrayIndex(index);
}

// 位於 deps/v8/src/objects/string.cc:1361
bool String::ComputeArrayIndex(uint32_t* index) {
  int length = this->length();
  if (length == 0 || length > kMaxArrayIndexSize) return false;
  StringCharacterStream stream(*this);
  return StringToArrayIndex(&stream, index);
}

bool String::SlowAsArrayIndex(uint32_t* index) {
  DisallowHeapAllocation no_gc;
  if (length() <= kMaxCachedArrayIndexLength) {
    Hash();  // force computation of hash code
    uint32_t field = hash_field();
    if ((field & kIsNotArrayIndexMask) != 0) return false;
    // Isolate the array index form the full hash field.
    *index = ArrayIndexValueBits::decode(field);
    return true;
  } else {
    return ComputeArrayIndex(index);
  }
}

// 位於 deps/v8/src/utils/utils-inl.h:45
template <typename Stream>
bool StringToArrayIndex(Stream* stream, uint32_t* index) {
  uint16_t ch = stream->GetNext();

  // If the string begins with a '0' character, it must only consist
  // of it to be a legal array index.
  if (ch == '0') {
    *index = 0;
    return !stream->HasMore();
  }

  // Convert string to uint32 array index; character by character.
  if (!IsDecimalDigit(ch)) return false;
  int d = ch - '0';
  uint32_t result = d;
  while (stream->HasMore()) {
    if (!TryAddIndexChar(&result, stream->GetNext())) return false;
  }

  *index = result;
  return true;
}

另外嘗試找了 Object 與 keys 的實現邏輯，看到一段註釋：

// 位於 deps/v8/src/objects/keys.h

// This is a helper class for JSReceiver::GetKeys which collects and sorts keys.
// GetKeys needs to sort keys per prototype level, first showing the integer
// indices from elements then the strings from the properties. However, this
// does not apply to proxies which are in full control of how the keys are
// sorted.
//
// For performance reasons the KeyAccumulator internally separates integer keys
// in |elements_| into sorted lists per prototype level. String keys are
// collected in |string_properties_|, a single OrderedHashSet (similar for
// Symbols in |symbol_properties_|. To separate the keys per level later when
// assembling the final list, |levelLengths_| keeps track of the number of
// String and Symbol keys per level.
//
// Only unique keys are kept by the KeyAccumulator, strings are stored in a
// HashSet for inexpensive lookups. Integer keys are kept in sorted lists which
// are more compact and allow for reasonably fast includes check.
class KeyAccumulator final {
 public:
  KeyAccumulator(Isolate* isolate, KeyCollectionMode mode,
                 PropertyFilter filter)
      : isolate_(isolate), mode_(mode), filter_(filter) {}
  ~KeyAccumulator() = default;

  static MaybeHandle<FixedArray> GetKeys(
      Handle<JSReceiver> object, KeyCollectionMode mode, PropertyFilter filter,
      GetKeysConversion keys_conversion = GetKeysConversion::kKeepNumbers,
      bool is_for_in = false, bool skip_indices = false);
...

說是因爲性能原因，V8 按照 spec 分成了 elements 與 string_properties 和 symbol_properties_ 這幾部分，其中將整數存到了 sorted list 中保證順序。

v8 代碼較爲複雜，目前只找到這些，日後再戰。這其中參考了這兩篇文：

V8 團隊引入 KeyAccumulator 優化 for-in 查找的博文
（更新）從 Chrome 源碼看 JS Object 的實現 - 知乎

五、總結

因爲 bug 開啓了一小段探索之旅，問題雖小，但也收穫頗豐，做幾點小小總結：

ES6 後的 Object 實現中，會按照新元素是否爲 array index，界定是否重新排序並插入到開頭。若業務需依賴對象 key 先來後到的排序、且涉及普通字符串與數字字符串的混合，再考慮到舊引擎的兼容問題的情況，另外維護一個 key 的數組會更加穩妥。
V8 引擎的代碼量十分龐大，不是簡單花一兩天時間搜索搜索就能把握的，還需要輔以動態調試等技能。後續可能還需再找一些 Overview 類型的資料，慢慢在腦中建立基本的輪廓和地圖，纔好進一步深入去了解。相比之下 QuickJS 會更容易上手些。
紙上得來終覺淺，文檔或教程常介紹一些細小的坑和細節，但如果自己沒有實際的踩坑，其實很難留意到；大概文檔本身是靜態的，而世界每時每刻都在變化，即使是標準文檔，也可能會隱藏一些不完善之處。這也顯得實踐機會的彌足珍貴，實踐中遇到的每一個 bug 或是矛盾之處，無論業務代碼還是基礎設施，只要把握得當，都可能是通往真正知識之路、開啓新世界的大門。

時間關係，探索暫時到這裏，留下這篇記錄。才疏學淺，其中必然會有許多不完善的地方，還請大佬們不吝賜教。

[1] https://v8.dev/blog/fast-for-in

[2] https://zhuanlan.zhihu.com/p/26169639

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/oyCfv60JJqBiYtnx8arewA