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

Question

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

MyPrototypeWhat opened this issue 3 years ago · 0 comments

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;
};