关于 JavaScript Object.keys() 排序问题的探索 - 哈喽比特

402次阅读 | 发布于3年以前

| 导语利用 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]](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 时，依赖了 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.

3 . 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.

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

Add P as the last element of keys.

5 . 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 的更新：

1 . Let keys be a new empty List. 2 . 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.

3 . 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.

4 . 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.

5 . 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 或是矛盾之处，无论业务代码还是基础设施，只要把握得当，都可能是通往真正知识之路、开启新世界的大门。

时间关系，探索暂时到这里，留下这篇记录。才疏学浅，其中必然会有许多不完善的地方，还请大佬们不吝赐教。