關(guān)于 JavaScript Object.keys() 排序問題的探索與總結(jié)
| 導(dǎo)語(yǔ) 利用 Object.keys 取得對(duì)象所有屬性的 key ，然后進(jìn)行 map 操作是 JavaScript 開發(fā)者常用的方法。但你是否思考過 key list 是依據(jù)什么順序排列的呢？
一、背景
近期維護(hù)輔導(dǎo) App 內(nèi)嵌 WebView 頁(yè)面調(diào) native 拍照上傳的業(yè)務(wù)時(shí)，遇到一個(gè)詭異的兼容 Bug：iOS 端新提交的圖片偶現(xiàn)順序不一致的問題，但 Android 端一切正常。
首先簡(jiǎn)單梳理下拍照上傳的關(guān)鍵業(yè)務(wù)邏輯：
JS 側(cè)用一個(gè) Object 保存各個(gè)圖片的信息，拍照上傳后 native 會(huì)觸發(fā) JS 的回調(diào)回傳對(duì)應(yīng)圖片 URL，其中以 unix 時(shí)間戳作為 tag，區(qū)分不同的圖片拍照任務(wù)，以 tag 為 key 存入 Object 中；
對(duì)于在本次 WebView 會(huì)話之前已提交過的圖片，則通過 sha256 取已有的圖片 URL 的哈希生成 tag，往 Object 存入對(duì)應(yīng)圖片信息。
提交時(shí)會(huì)用
Object.keys()方法獲得 Object 中所有的 tag，再 map 到對(duì)應(yīng)的圖片 URL 列表提交到后臺(tái)。
定位了一波發(fā)現(xiàn)原因是：Android 與 iOS 客戶端給到的 tag 存在差異，Android 傳來了毫秒級(jí)的時(shí)間戳，iOS 傳來的是秒級(jí)的時(shí)間戳。當(dāng) iOS 端以秒級(jí)時(shí)間戳作為 tag 插入時(shí)，這個(gè)新的圖片地址自動(dòng)排在了最前面。
原邏輯較為復(fù)雜，簡(jiǎn)化復(fù)現(xiàn)此問題的代碼如下：
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 回調(diào)的 tag
const newTagAndroid = "1612076930661";
// iOS 回調(diào)的 tag
const newTagIOS = "1612076930";
console.log(getNewUrlList(originTagUrlMap, newUrl, newTagAndroid));
console.log(getNewUrlList(originTagUrlMap, newUrl, newTagIOS));
運(yùn)行發(fā)現(xiàn)兩個(gè)回調(diào) Tag 生成的 urlList 不一致：
[ 'https://xxx/1.jpg', 'https://xxx/2.jpg', 'https://xxx/3.jpg' ] // Android 回調(diào)
[ 'https://xxx/3.jpg', 'https://xxx/1.jpg', 'https://xxx/2.jpg' ] // iOS 回調(diào)
可以確定一點(diǎn)：Object.keys() 的返回并不總能保持先來后到的順序。從解決業(yè)務(wù)需要的角度，我們可以通過維護(hù)一個(gè)單獨(dú)的 tag 數(shù)組來回避這個(gè)問題。
從徹底解決問題的角度出發(fā)，這里冒出兩個(gè)疑問點(diǎn)：
Object.keys()的排序機(jī)制是什么樣的？為什么毫秒時(shí)間戳作為 key 的時(shí)候輸出的是正常的先來后到順序？
接下來也正是針對(duì)這兩點(diǎn)問題的探索和發(fā)現(xiàn)。
二、Object.keys() 的排序機(jī)制
《現(xiàn)代 JavaScript 教程》的 Object 章節(jié)里對(duì)這個(gè)話題有一句簡(jiǎn)單的概括：
integer properties are sorted, others appear in creation order.
當(dāng) key 整數(shù)類型會(huì)做一層排序，其他類型則按創(chuàng)建順序來排。
在《你不知道的JavaScript》中是這么描述的：
在ES6之前，羅列一個(gè)對(duì)象的鍵/屬性的順序沒有在語(yǔ)言規(guī)范中定義，而是依賴于具體實(shí)現(xiàn)的。一般來說，大多數(shù)引擎會(huì)以創(chuàng)建的順序來羅列它們，雖然開發(fā)者們已經(jīng)被強(qiáng)烈建議永遠(yuǎn)不要依仗這種順序。
在ES6中，羅列直屬屬性的屬性是由
[[OwnPropertyKeys]]算法定義的（ES6語(yǔ)言規(guī)范，9.1.12部分），它產(chǎn)生所有直屬屬性（字符串或symbol），不論其可枚舉性。這種順序僅對(duì)Reflect.ownKeys(..)有保證。這個(gè)順序是：
首先，以數(shù)字上升的順序，枚舉所有數(shù)字索引的直屬屬性。 然后，以創(chuàng)建順序枚舉剩下的直屬字符串屬性名。 最后，以創(chuàng)建順序枚舉直屬symbol屬性。
教程文檔的細(xì)節(jié)說的不太明確，尋找 ES6 標(biāo)準(zhǔn)中 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]](key). 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 時(shí)，依賴了 ES6 標(biāo)準(zhǔn)中定義的 [[OwnPropertyKeys]] 算法，標(biāo)準(zhǔn)原文對(duì)該算法的描述如下：
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.
到這里，對(duì)問題 1 我們已經(jīng)有了一個(gè)大概的印象：Object.keys() 在執(zhí)行過程中，若發(fā)現(xiàn) key 是整數(shù)類型索引，那它首先按照從小到大排序加入；然后再按照先來先到的創(chuàng)建順序加入其他元素，最后加入 Symbol 類型的 key。
三、key 何時(shí)會(huì)被識(shí)別為“整數(shù)”？
對(duì)于未知事物，并不可能都通過有限的已知推導(dǎo)出來，需要引入新的信息去解決。至于如何引入，很大程度也需要靠想象力與直覺去猜想，然后做實(shí)驗(yàn)驗(yàn)證才能發(fā)現(xiàn)。看到這里的問題，聯(lián)想到 Unix 時(shí)間戳本身是一個(gè) 32 位 int 整型，直覺告訴我，會(huì)不會(huì)有什么關(guān)于 32 位整數(shù)的限定？
開始驗(yàn)證這個(gè)猜想。這里我們可以通過控制 tag 的數(shù)字大小，來確定是否觸發(fā)整數(shù)排序的邊界值。嘗試給時(shí)間戳的十進(jìn)制數(shù)字加一位（例如 16120769300），發(fā)現(xiàn)排序失效，這說明邊界值在這兩者之間。經(jīng)過多次嘗試，最后發(fā)現(xiàn)邊界值恰好是 4294967295，即 (1 << 32) - 1、32 位無(wú)符號(hào)整數(shù)的最大值，與猜想恰好相符。
猜想得到肯定，接下來尋找資料，確認(rèn) JS 語(yǔ)言是否真的如此設(shè)計(jì)。再回到 ES6 標(biāo)準(zhǔn)文檔，經(jīng)過一番搜索和查找，關(guān)注點(diǎn)鎖定在了 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.
這里遇到一個(gè)問題，ES6 標(biāo)準(zhǔn)文檔在 [[OwnPropertyKeys]] 里面描述的是 integer index，而我們這里的實(shí)現(xiàn)中用的是 array index，存在矛盾。
帶著問題一番搜索，發(fā)現(xiàn)已有人提過類似問題，還有標(biāo)準(zhǔn)文檔的改動(dòng) 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
對(duì)應(yīng) 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 其實(shí)也有了完整的解釋：毫秒的時(shí)間戳已不滿足 array index 的條件，引擎便按照 string 的先來后到順序來處理。
四、JS 引擎相關(guān)源碼
光看標(biāo)準(zhǔn)文檔畢竟還是紙上談兵，存在代碼實(shí)現(xiàn)與文檔不一致的可能（比如剛剛的發(fā)現(xiàn)），嘗試挑戰(zhàn)看看現(xiàn)有 JS 引擎的底層實(shí)現(xiàn)。由于 V8 本身做了好多優(yōu)化，之前也沒讀源碼的經(jīng)驗(yàn)，暫時(shí)難以下手，只能先試試“ VSCode 字符串搜索大法”。聽聞 Fabrice Bellard 大神的 QuickJS 只幾萬(wàn)行代碼就完整支持了 ES2020 標(biāo)準(zhǔn)，決定先從代碼量小一些的 QuickJS 出發(fā)，然后大概看看 V8 的實(shí)現(xiàn)。
QuickJS 的 Array Index 排序?qū)崿F(xiàn)
QuickJS 的實(shí)現(xiàn)在 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;
}
}
}
其中調(diào)用的 is_num_string 承擔(dān)了判斷的任務(wù)：
// 位于 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 的數(shù)量，若存在 array index 的 key，則調(diào)用 rqsort 方法對(duì)這部分 key 進(jìn)行排序，最后返回。
if (num_keys_count != 0 && !num_sorted) {
rqsort(tab_atom, num_keys_count, sizeof(tab_atom[0]), num_keys_cmp,
ctx);
}
V8 的排序?qū)崿F(xiàn)
V8 的代碼沒看的很懂（畢竟還只是 VSCode 查找大法水平），搜索了一堆文章，克隆了 Node 的 v12.x 源碼看其中的 deps/v8 部分。找到其中字符串類定義的判斷與轉(zhuǎn)換 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 的實(shí)現(xiàn)邏輯，看到一段注釋：
// 位于 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);
...
說是因?yàn)樾阅茉颍琕8 按照 spec 分成了 elements 與 string_properties 和 symbol_properties_ 這幾部分，其中將整數(shù)存到了 sorted list 中保證順序。
v8 代碼較為復(fù)雜，目前只找到這些，日后再戰(zhàn)。這其中參考了這兩篇文：
V8 團(tuán)隊(duì)引入 KeyAccumulator 優(yōu)化 for-in 查找的博文 （更新）從Chrome源碼看JS Object的實(shí)現(xiàn) - 知乎
五、總結(jié)
因?yàn)?bug 開啟了一小段探索之旅，問題雖小，但也收獲頗豐，做幾點(diǎn)小小總結(jié)：
ES6 后的 Object 實(shí)現(xiàn)中，會(huì)按照新元素是否為
array index，界定是否重新排序并插入到開頭。若業(yè)務(wù)需依賴對(duì)象 key 先來后到的排序、且涉及普通字符串與數(shù)字字符串的混合，再考慮到舊引擎的兼容問題的情況，另外維護(hù)一個(gè) key 的數(shù)組會(huì)更加穩(wěn)妥。V8 引擎的代碼量十分龐大，不是簡(jiǎn)單花一兩天時(shí)間搜索搜索就能把握的，還需要輔以動(dòng)態(tài)調(diào)試等技能。后續(xù)可能還需再找一些 Overview 類型的資料，慢慢在腦中建立基本的輪廓和地圖，才好進(jìn)一步深入去了解。相比之下 QuickJS 會(huì)更容易上手些。
紙上得來終覺淺，文檔或教程常介紹一些細(xì)小的坑和細(xì)節(jié)，但如果自己沒有實(shí)際的踩坑，其實(shí)很難留意到；大概文檔本身是靜態(tài)的，而世界每時(shí)每刻都在變化，即使是標(biāo)準(zhǔn)文檔，也可能會(huì)隱藏一些不完善之處。這也顯得實(shí)踐機(jī)會(huì)的彌足珍貴，實(shí)踐中遇到的每一個(gè) bug 或是矛盾之處，無(wú)論業(yè)務(wù)代碼還是基礎(chǔ)設(shè)施，只要把握得當(dāng)，都可能是通往真正知識(shí)之路、開啟新世界的大門。
時(shí)間關(guān)系，探索暫時(shí)到這里，留下這篇記錄。才疏學(xué)淺，其中必然會(huì)有許多不完善的地方，還請(qǐng)大佬們不吝賜教。
[1] https://v8.dev/blog/fast-for-in
[2] https://zhuanlan.zhihu.com/p/26169639
“分享、點(diǎn)贊、在看” 支持一波 