作者：钱宝坤 宋雅儒

标准参考

在 ECMAScript 第三、五版中，Array.prototype.sort(comparefn) 如果定义了 comparefn 这个方法，它接受两个参数 x 和 y。要求的返回值是一个正数 (x > y)，零 (x = y) 或者是负数 (x < y)。

关于 sort 语法的说明，请参考 ECMAScript 5th Edition 15.4.4.11 Array.prototype.sort。

问题描述

ECMAScript 中并没有明确说明 comparefn 返回值是布尔型时应该如何处理，它仅仅描述 comparefn 调用的返回值应当是 -1、0、1 这三种情况之一。comparefn 的返回值规范实现约束是 “引擎开发者” 还是 “脚本使用者” 并没有明确表述¹

这导致不同引擎对于 comparefn 返回值为非 -1、0、1 范围时具体处理不一致，从而使排序结果非预期。

【注】：一般认为 ECMAScript 是脚本引擎实现与开发者的桥梁，它的规范内容对两者都有约束效力。 因此我们无法明确认定 comparefn 的返回值范围是约束的实现方还是开发方。 尽管规范中有描述到 ：“Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN.”， 这表示 comparefn 的返回值必须是个非 NaN 的 Number 类型，这两个类型都为 JS 使用者所知，但是提示使用 Type(v) 是约束引擎实现方的。实际仍然没有明确两者的约束关系。

造成的影响

Array.prototype.sort 方法在使用 comparefn 辅助排序时，如果 comparefn 返回值非规范规定的 -1、0、1 值范围，返回的排序结果可能与预期不一致。

受影响的浏览器

所有浏览器

问题分析

各浏览器使用的脚本引擎不同，导致对于 ECMAScript 相关规范细节实现并不一致。常见的浏览器以及脚本引擎如下表所示，此文将基于此表的脚本引擎常用名做描述。

Browser Name	ECMAScript Engine
Internet Explorer 6 - 8	JScript
Internet Explorer 9 - 10	Chakra
Firefox	IonMonkey(Monkey系列引擎)
Chrome	V8
Safair	JavaScriptCore(SquirrelFish Extreme)
Opera	Carakan

分析以下代码，预期将数组元素进行升序排序：

var result = document.getElementById("result"); var test10Elements = [7, 6, 5, 4, 3, 2, 1, 0, 8, 9];
                var comparefn = function (x, y) { return x > y; }; test10Elements.sort(comparefn);

代码中，comparefn 函数返回值为 bool 类型，并非为规范规定的 -1、0、1 值。那么执行此代码，各 JS 脚本引擎实现情况如何？

	输出结果	是否符合预期
JScript	[2, 3, 5, 1, 4, 6, 7, 0, 8, 9]	否
Carakan	[0, 1, 3, 8, 2, 4, 9, 5, 6, 7]	否
Chakra & JavaScriptCore	[7, 6, 5, 4, 3, 2, 1, 0, 8, 9]	否
IonMonkey	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]	是
V8	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]	是

根据表中数据可见，当数组内元素个数小于等于 10 时：

• JScript & Carakan 排序结果有误
• Chakra & JavaScriptCore 看起来没有进行排序
• IonMonkey 返回了预期的正确结果
• V8 暂时看起来排序正确

将数组元素扩大至 11 位：

var result = document.getElementById("result"); var test11Elements = [7, 6, 5, 4, 3, 2, 1, 0, 10, 9,
                8]; var comparefn = function (x, y) { return x > y; }; test11Elements.sort(comparefn);

	输出结果	是否符合预期
JScript	[2, 3, 5, 1, 4, 6, 7, 0, 8, 9, 10]	否
Carakan	[0, 1, 3, 8, 2, 4, 9, 5, 10, 6, 7]	否
Chakra & JavaScriptCore	[7, 6, 5, 4, 3, 2, 1, 0, 10, 8, 9]	否
IonMonkey	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]	是
V8	[5, 0, 1, 2, 3, 4, 6, 7, 8, 9, 10]	否

根据表中数据可见，当数组内元素个数大于 10 时：

• JScript & Carakan 排序结果有误
• Chakra & JavaScriptCore 看起来没有进行排序
• IonMonkey 返回了预期的正确结果
• V8 排序结果由正确转为不正确

单引擎多种排序实现

由于规范中并不要求引擎采用何种排序算法来实现 sort 函数。因此同一引擎对于所需排序元素总体数量不同，可能会采用不同的优化排序算方法。

V8 正是使用了这种多排序算法，参照 V8 : v8/src/array.js

var QuickSort = function QuickSort(a, from, to) { var third_index = 0; while (true) { // Insertion sort
                is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; } if (to -
                from > 1000) { third_index = GetThirdIndex(a, from, to); } else { third_index = from + ((to - from)
                >> 1); } ... } ... }

当待排序的数组长度小于或等于 10 的时候，使用的是插入排序，大于 10 使用的是快速排序。

先看小于等于 10 位数据时，使用的插入排序实现：

var InsertionSort = function InsertionSort(a, from, to) { for (var i = from + 1; i < to; i++) { var
                element = a[i]; for (var j = i - 1; j >= from; j--) { var tmp = a[j]; var order =
                %_CallFunction(receiver, tmp, element, comparefn); if (order > 0) { a[j +
                1] = tmp; } else { break; } } a[j + 1] = element; } };

可见，当 comparefn 函数调用后，其返回值需要判断是否大于 0。 由于 TestCase 中 comparefn 函数返回值为 true 或 false，隐式类型转换后 true 为 1 false 为 0。 他们恰好使此判断返回预期的 true 、false 值，因此排序结果正常。

再看大于 10 个数据时使用的快速排序实现：

var QuickSort = function QuickSort(a, from, to) { var third_index = 0; while (true) { // Insertion sort
                is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; } if (to -
                from > 1000) { third_index = GetThirdIndex(a, from, to); } else { third_index = from + ((to - from)
                >> 1); } // Find a pivot as the median of first, last and middle element. var v0 = a[from]; var v1
                = a[to - 1]; var v2 = a[third_index]; var c01 = %_CallFunction(receiver, v0, v1, comparefn); if (c01 > 0) { // v1 < v0, so swap them. var tmp = v0; v0 = v1; v1 = tmp; } //
                v0 <= v1. var c02 = %_CallFunction(receiver, v0, v2, comparefn); if (c02 >= 0)
                { // v2 <= v0 <= v1. var tmp = v0; v0 = v2; v2 = v1; v1 = tmp; } else { // v0 <= v1
                && v0 < v2 var c12 = %_CallFunction(receiver, v1, v2, comparefn); if (c12
                > 0) { // v0 <= v2 < v1 var tmp = v1; v1 = v2; v2 = tmp; } } } ... }

根据 TestCase 中用例情况， comparefn 被调用后进入 if (c02 >= 0) 分支。 此时，如果 comparefn 返回的是布尔值，那么 c02 >= 0 结果永远是 true。 元素被不符合使用者预期的调换了位置，这导致了 V8 高于 10 位元素时排序结果不符合预期¹。

【注】：在 V8 的测试工程中(v8/test/mjsunit/array-sort.js) TestNumberSort 方法中的测试用例覆盖不全，最长的测试用例是 10 个元素的数组，快排分支没有被检测到。

返回值类型转为某种数值类型与 0 做比较

观看 JavaScriptCore 中此问题的具体实现， 参照 JavaScriptCore/runtime/JSArray.cpp

int compare_key_key(key va, key vb) { ASSERT(!va.isUndefined()); ASSERT(!vb.isUndefined()); if
                (m_exec->hadException()) return 1; double compareResult; if (m_cachedCall) {
                m_cachedCall->setThis(jsUndefined()); m_cachedCall->setArgument(0, va);
                m_cachedCall->setArgument(1, vb); compareResult =
                m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec)); } else { MarkedArgumentBuffer
                arguments; arguments.append(va); arguments.append(vb); compareResult = call(m_exec, m_compareFunction,
                m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec); } return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to
                store all values, even if equivalent. }

JavaScriptCore 的实现中，引擎先将 bool 转为 double 类型，并采用具体逻辑语句将其转为符合规范描述的 -1 、1 值范围。

TestCase 中 comparefn 返回结果是布尔类型，引擎采用 double 类型来接受此值，并且判断它是否小于 0。 因此 bool 被转为 1 或 0，不管如何表达式都返回 false，并被适配到 1 值上。

于是元素没有被交换位置，导致看起来排序后结果与原数组顺序一致。将 comparefn 的返回值强制设置为 -1，可发现其实际上进行了排序。

var result = document.getElementById("result"); var test11Elements = [7, 6, 5, 4, 3, 2, 1, 0, 10, 9,
                8]; var comparefn = function (x, y) { return -1; }; test11Elements.sort(comparefn);

	输出结果
Chakra & JavaScriptCore	[8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7]

同时可以发现，Chakra 引擎排序结果与 JavaScriptCore 一致，可推断出此处其实现方式与 JavaScriptCore 可能一致¹。

【注】: Chakra 引擎并不开源，无法根据其源码得出可靠结论，此处仅根据测试现象得出推测。

返回值转为符合规范的值范围

IonMonkey 引擎为何 TestCase 的排序结总符合预期呢？参照 Firefox : js/src/jsarray.cpp

double cmp; if (!ToNumber(cx, ag.rval(), &cmp)) return false; *lessOrEqualp =
                (MOZ_DOUBLE_IS_NaN(cmp) || cmp <= 0);

其中 ToNumber 会调用 js/src/jsnum.cpp 的 ToNumberSlow

js::ToNumberSlow(JSContext *cx, Value v, double *out){ ... if (v.isNumber()) { *out = v.toNumber();
                return true; } skip_int_double: if (v.isString()) return StringToNumberType< double>(cx,
                v.toString(), out); if (v.isBoolean()) { if (v.toBoolean()) { *out = 1.0;
                return true; } *out = 0.0; return true; } if (v.isNull()) { *out = 0.0; return true; } if (v.isUndefined()) break; JS_ASSERT(v.isObject()); if
                (!ToPrimitive(cx, JSTYPE_NUMBER, &v)) return false; if (v.isObject()) break; } *out = js_NaN; return
                true; }

我们可以发现，ToNumberSlow 方法会判断 comparefn 执行后的返回结果的数据类型，并将这个结果统一转换为 double 且值范围为符合规范的 0 、1。所以当 return x > y 返回布尔型的结果总能进行正确排序。

无法知晓返回值处理规则的引擎

最后关于 JScript、Chakra、Carakan 引擎，它们均非开源项目，无法一窥源码分析出实际问题点。 但从以上其它引擎的实现分析中可以看出，他们都采用了类似的排序算法，区别仅在与是否以及如何约束 comparefn 返回值在 -1、0、1 范围内。 这导致了当 comparefn 返回非规范值范围时：

• 无视规范要求，直接使用返回值转为 bool 型交换前后数据位置，从而得到非预期的排序结果。
• 根据规范要求，直接使用返回转为数值类型得出交换值 -1、0、1，从而得到非预期的排序结果。
• 根据规范要求，可能存在其它类型被转为某种数值类型与 0 做某种逻辑判断后，得出交换值 -1、0、1，从而得到非预期的排序结果。

解决方案

调用 Array.prototype.sort 函数并需要依赖 comparefn 处理排序结果时，应遵循规将 comparefn 函数返回值约束在 -1、0、1 范围内。

参见

知识库

• ...

相关问题

• ...