语法糖解析系列之——数组相关函数实现（持续更新）

[MyPrototypeWhat]

flat / flatMap

• Array.prototype.flat

  function flat(/* depthArg = 1 */) {
    // 函数名花里胡哨的，其实很好理解
   		// 拿到参数	
      var depthArg = arguments.length ? arguments[0] : undefined;
    	// if(this==undefined) 判断，否返回Objec(this)
      var O = toObject(this);
    	// lengthOfArrayLike => toLength(obj.length) 
    	// 其实就是拿到数组的length 规范length的边界为有效整数(2 ** 53 - 1)
      var sourceLen = lengthOfArrayLike(O);
    	// 相当于new Array(0)
      // 拿到数组的构造函数 并new 不赘述，感兴趣可以去看源码实现
      var A = arraySpeciesCreate(O, 0);
    	// 核心
      A.length = flattenIntoArray(A, O, O, sourceLen, 0, depthArg === undefined ? 1 : toIntegerOrInfinity(depthArg));
      return A;
    }

• Array.prototype.flatMap

  function flatMap(callbackfn /* , thisArg */) {
      var O = toObject(this);
      var sourceLen = lengthOfArrayLike(O);
      var A;
    	// typeof callbackfn == 'function'
      aCallable(callbackfn);
      A = arraySpeciesCreate(O, 0);
    	// 与flat不同的是多了个callbackfn和thisArg depthArg写死为1
      A.length = flattenIntoArray(A, O, O, sourceLen, 0, 1, callbackfn, arguments.length > 1 ? arguments[1] : undefined);
      return A;
    }

  • flattenIntoArray：

    /**
     * 
     * @param {*} target  目标数组
     * @param {*} original 原数组，用于mapper
     * @param {*} source 当前遍历数组
     * @param {*} sourceLen 当前遍历数组长度
     * @param {*} start target中下一位索引值
     * @param {*} depth 拍平深度
     * @param {*} mapper 遍历函数
     * @param {*} thisArg 遍历函数上下文
     * @returns 
     */
    var flattenIntoArray = function (target, original, source, sourceLen, start, depth, mapper, thisArg) {
      var targetIndex = start;
      var sourceIndex = 0;
      // 绑定函数上下文
      var mapFn = mapper ? bind(mapper, thisArg) : false;
      var element, elementLen;
    	// 开始遍历
      while (sourceIndex < sourceLen) {
        // 判断索引有效
        if (sourceIndex in source) {
          // 处理遍历函数返回值，没有遍历函数则返回当前项
          // 每次遇到数组时都会执行
          element = mapFn ? mapFn(source[sourceIndex], sourceIndex, original) : source[sourceIndex];
    			// 遇到数组并且存在有效depth
          if (depth > 0 && isArray(element)) {
            elementLen = lengthOfArrayLike(element);
            // 递归
            targetIndex = flattenIntoArray(target, original, element, elementLen, targetIndex, depth - 1) - 1;
          } else {
            // 如果拍平结束或者不是数组
            // 判断数组长度的有效值
            if (targetIndex >= 0x1FFFFFFFFFFFFF) throw TypeError('Exceed the acceptable array length');
            // 设置对应值
            target[targetIndex] = element;
          }
    			// 索引++
          targetIndex++;
        }
        sourceIndex++;
      }
      return targetIndex;
    };

    • targetIndex是关键，始终穿插在各层数组中记录索引，例如：

      [1,[2,3]]
      
      第一轮循环,targetIndex=0 target赋值之后 targetIndex++
      第二轮循环，为数组，递归遍历[2,3]，不为数组 target[targetIndex]=2 => target[1]=2
      然后 targetIndex++
      然后 target[targetIndex]=3 => target[2]=3
      target=[1,2,3]

fill

• Array.prototype.fill：

  function toIntegerOrInfinity(argument) {
    // 转换为number 
    // +undefined = NaN
    // +null = 0
    var number = +argument;
    // eslint-disable-next-line no-self-compare -- safe
    // 取小值 例如 1.1取1 -1.1取-2
    // number !== number 判断NaN情况
    // number === 0 判断0和null情况
    return number !== number || number === 0 ? 0 : (number > 0 ? floor : ceil)(number);
  }
  
  function toAbsoluteIndex(index, length) {
    // 先对第一个参数取整
    var integer = toIntegerOrInfinity(index);
    // 小于0取0 大于0取自身
    return integer < 0 ? max(integer + length, 0) : min(integer, length);
  }
  
  function fill(value /* , start = 0, end = @length */) {
    // if(this==undefined) 判断，否返回Objec(this)
    var O = toObject(this);
    // 与数组length与2**53-1 取小值（Math.min）
    var length = lengthOfArrayLike(O);
    var argumentsLength = arguments.length;
    // start参数初始化
    var index = toAbsoluteIndex(argumentsLength > 1 ? arguments[1] : undefined, length);
    var end = argumentsLength > 2 ? arguments[2] : undefined;
    // end参数初始化 默认为length
    var endPos = end === undefined ? length : toAbsoluteIndex(end, length);
    // 遍历填充值
    while (endPos > index) O[index++] = value;
    return O;
  }

  • 这里有一个使用陷阱，O[index++] = value; 直接赋值操作，如果value为引用类型，一旦`value某些属性更改，那么所有填充的值都会被更改

forEach, map, filter, some, every, find, findIndex, filterReject

Array.prototype.{ forEach, map, filter, some, every, find, findIndex, filterReject }以上函数的核心实现函数

var createMethod = function (TYPE) {
  var IS_MAP = TYPE == 1;
  var IS_FILTER = TYPE == 2;
  var IS_SOME = TYPE == 3;
  var IS_EVERY = TYPE == 4;
  var IS_FIND_INDEX = TYPE == 6;
  var IS_FILTER_REJECT = TYPE == 7;
  var NO_HOLES = TYPE == 5 || IS_FIND_INDEX;
  return function ($this, callbackfn, that, specificCreate) {
    // if(this==undefined) 判断，否返回Objec(this)
    var O = toObject($this);
    var self = IndexedObject(O);
    // callbackfn绑定上下文，一般是第三个参数
    var boundFunction = bind(callbackfn, that);
    // 取数组length与2**53-1 取小值（Math.min）
    var length = lengthOfArrayLike(self);
    var index = 0;
    // 创建数组
    // 具体实现有兴趣可以查看相关源码
    var create = specificCreate || arraySpeciesCreate;
    // 创建最终返回结果
    // map => new Array(length)
    // filter/filterReject => new Array(0)
    // 其余为 undefined
    var target = IS_MAP ? create($this, length) : IS_FILTER || IS_FILTER_REJECT ? create($this, 0) : undefined;
    var value, result;
    for (;length > index; index++) if (NO_HOLES || index in self) {
      // find/findIndex 或者 有效索引
      value = self[index];
      // 执行callbackfn拿到结果
      result = boundFunction(value, index, O);
      if (TYPE) {
        // 排除了forEach
        if (IS_MAP) target[index] = result; // map修改索引对应值
        else if (result) switch (TYPE) {
          // 只要出现一次true
          case 3: return true;              // some 只要有一项返回true就返回true
          case 5: return value;             // find 直接返回值
          case 6: return index;             // findIndex 直接返回值的索引
          case 2: push(target, value);      // filter => target.push(value)
        } else switch (TYPE) {
          // 只要出现一次false
          case 4: return false;             // every 
          case 7: push(target, value);      // filterReject
        }
      }
    }
    // findIndex没找到返回-1
    // 如果是every此时result应该全为true，所以返回false
    // 如果是some此时result应该全为false,所以判断是否是every函数即可
    // 除此之外的函数都返回target
    return IS_FIND_INDEX ? -1 : IS_SOME || IS_EVERY ? IS_EVERY : target;
  };
};

module.exports = {
  // `Array.prototype.forEach` method
  // https://tc39.es/ecma262/#sec-array.prototype.foreach
  forEach: createMethod(0),
  // `Array.prototype.map` method
  // https://tc39.es/ecma262/#sec-array.prototype.map
  map: createMethod(1),
  // `Array.prototype.filter` method
  // https://tc39.es/ecma262/#sec-array.prototype.filter
  filter: createMethod(2),
  // `Array.prototype.some` method
  // https://tc39.es/ecma262/#sec-array.prototype.some
  some: createMethod(3),
  // `Array.prototype.every` method
  // https://tc39.es/ecma262/#sec-array.prototype.every
  every: createMethod(4),
  // `Array.prototype.find` method
  // https://tc39.es/ecma262/#sec-array.prototype.find
  find: createMethod(5),
  // `Array.prototype.findIndex` method
  // https://tc39.es/ecma262/#sec-array.prototype.findIndex
  findIndex: createMethod(6),
  // `Array.prototype.filterReject` method
  // https://github.com/tc39/proposal-array-filtering
  filterReject: createMethod(7)
};

• IndexedObject

  fails(function () {
    // 针对非数组（如ES3）和不可枚举的旧V8字符串的回退
    // throws an error in rhino, see https://github.com/mozilla/rhino/issues/346
    // eslint-disable-next-line no-prototype-builtins -- safe
    // 判断字符串是否可枚举
    return !Object('z').propertyIsEnumerable(0);
  }) ? function (it) {
    // 如果是字符串，切分为数组
    return classof(it) == 'String' ? split(it, '') : Object(it);
  } : Object;

• result = boundFunction(value, index, O);遍历函数第三个参数一般为原始数组，很少用到

• 流程：遍历数组，先排除没有返回值的，some,find,findIndex,every 函数都为短路判断，只要出现一次false/true就返回。

reduce

• es.array.reduce.js

  var $reduce = require('../internals/array-reduce').left;
  $({ target: 'Array', proto: true, forced: !STRICT_METHOD || CHROME_BUG }, {
    // 关注下面这部分
    reduce: function reduce(callbackfn /* , initialValue */) {
      var length = arguments.length;
      return $reduce(this, callbackfn, length, length > 1 ? arguments[1] : undefined);
    }
  });

• array-reduce.js

  var createMethod = function (IS_RIGHT) {
    /**
     * that 上下文
     * callbackfn 回调函数
     * argumentsLength 参数长度
     * memo 上一轮循环返回值
     */
    return function (that, callbackfn, argumentsLength, memo) {
      // typeof callbackfn === ‘function’
      aCallable(callbackfn);
      // var O = Object(that)
      var O = toObject(that);
      // 判断是String还是Array,是String则split为数组
      var self = IndexedObject(O);
      // 返回数组长度
      var length = lengthOfArrayLike(O);
      // 初始化索引，reduceRight初始索引为最后一项
      var index = IS_RIGHT ? length - 1 : 0;
      // 判断每次循环+1\-1
      var i = IS_RIGHT ? -1 : 1;
      // 如果reduce/reduceRight入参只有一项，没有初始值时
      if (argumentsLength < 2) while (true) {
        if (index in self) {
          // 则memo为数组第一项/最后一项
          memo = self[index];
          index += i;
          break;
        }
        index += i;
        if (IS_RIGHT ? index < 0 : length <= index) {
          throw TypeError('Reduce of empty array with no initial value');
        }
      }
      for (;IS_RIGHT ? index >= 0 : length > index; index += i) if (index in self) {
        // 执行回调
        memo = callbackfn(memo, self[index], index, O);
      }
      return memo;
    };
  };
  
  module.exports = {
    // `Array.prototype.reduce` method
    // https://tc39.es/ecma262/#sec-array.prototype.reduce
    left: createMethod(false),
    // `Array.prototype.reduceRight` method
    // https://tc39.es/ecma262/#sec-array.prototype.reduceright
    right: createMethod(true)
  };

Array.from

• array-from.js

  module.exports = function from(arrayLike /* , mapfn = undefined, thisArg = undefined */) {
    // if(this==undefined) 判断，否返回Objec(this)
    var O = toObject(arrayLike);
    // 判断是否是构造函数
  	// 判断this不是function或者调用reflect.construct(function(){},[],this)，返回false，否则返回true
    var IS_CONSTRUCTOR = isConstructor(this);
    var argumentsLength = arguments.length;
    var mapfn = argumentsLength > 1 ? arguments[1] : undefined;
    var mapping = mapfn !== undefined;
    // 相当于 mapfn = mapfn.bind(thisArg,argumentsLength > 2 ? arguments[2] : undefined)
    if (mapping) mapfn = bind(mapfn, argumentsLength > 2 ? arguments[2] : undefined);
    // 获取迭代器或者默认迭代器
    // 相当于 O[Symbol['iterator']]
    var iteratorMethod = getIteratorMethod(O);
    var index = 0;
    var length, result, step, iterator, next, value;
    // 如果目标是不可迭代的或者它是一个带有默认迭代器的数组
    if (iteratorMethod && !(this == Array && isArrayIteratorMethod(iteratorMethod))) {
      // 相当于 iteratorMethod.call(O)，iterator为迭代器执行之后的对象
      iterator = getIterator(O, iteratorMethod);
      next = iterator.next;
      // 如果有构造函数，则new，否则为[]
      result = IS_CONSTRUCTOR ? new this() : [];
      // (step = iterator.next()).done
      for (;!(step = call(next, iterator)).done; index++) {
        // 相当于 value = mapfn(step.value,index)
        value = mapping ? callWithSafeIterationClosing(iterator, mapfn, [step.value, index], true) : step.value;
        // result插入对应值
        createProperty(result, index, value);
      }
    } else {
      length = lengthOfArrayLike(O);
      // 创建对应长度的数组
      result = IS_CONSTRUCTOR ? new this(length) : Array(length);
      for (;length > index; index++) {
        // 遍历插入对应值
        value = mapping ? mapfn(O[index], index) : O[index];
        createProperty(result, index, value);
      }
    }
    result.length = index;
    return result;
  };

sort

根据数组长度不同，用到了两个算法，分别是插入和归并

• es.array.sort.js

  var getSortCompare = function (comparefn) {
    return function (x, y) {
      // 使用陷阱，注意undefined的情况
      if (y === undefined) return -1;
      if (x === undefined) return 1;
      if (comparefn !== undefined) return +comparefn(x, y) || 0;
      // 没有comparefn默认从大到小排序
      return toString(x) > toString(y) ? 1 : -1;
    };
  };
  sort: function sort(comparefn) {
      if (comparefn !== undefined) aCallable(comparefn);
  
      var array = toObject(this);
  		// 通过判断版本判断是否使用原生sort,以及对Chakra和v8的错误情况判断
      if (STABLE_SORT) return comparefn === undefined ? un$Sort(array) : un$Sort(array, comparefn);
  
      var items = [];
      var arrayLength = lengthOfArrayLike(array);
      var itemsLength, index;
  
      for (index = 0; index < arrayLength; index++) {
  			// 相当于items.push(array[index])
        if (index in array) push(items, array[index]);
      }
  		// 重点
    	// internalSort就是下文的mergeSort函数 负责计算排序
    	// getSortCompare负责初始化比较函数
      internalSort(items, getSortCompare(comparefn));
  
      itemsLength = items.length;
      index = 0;
  
      while (index < itemsLength) array[index] = items[index++];
      while (index < arrayLength) delete array[index++];
  
      return array;
    }

• array-sort.js

  插入和归并就不多介绍了

  var mergeSort = function (array, comparefn) {
    var length = array.length;
    var middle = floor(length / 2);
    // 长度小于8，使用插入排序，大于则使用归并排序
    return length < 8 ? insertionSort(array, comparefn) : merge(
      array,
      mergeSort(arraySlice(array, 0, middle), comparefn),
      mergeSort(arraySlice(array, middle), comparefn),
      comparefn
    );
  };
  var insertionSort = function (array, comparefn) {
    // 插入排序
    var length = array.length;
    var i = 1;
    var element, j;
  
    while (i < length) {
      j = i;
      element = array[i];
      while (j && comparefn(array[j - 1], element) > 0) {
        array[j] = array[--j];
      }
      if (j !== i++) array[j] = element;
    } return array;
  };
  
  var merge = function (array, left, right, comparefn) {
    // 归并排序
    var llength = left.length;
    var rlength = right.length;
    var lindex = 0;
    var rindex = 0;
  
    while (lindex < llength || rindex < rlength) {
      array[lindex + rindex] = (lindex < llength && rindex < rlength)
        ? comparefn(left[lindex], right[rindex]) <= 0 ? left[lindex++] : right[rindex++]
        : lindex < llength ? left[lindex++] : right[rindex++];
    } return array;
  };