XXHolic/blog

Read Lodash ：cloneDeep

XXHolic opened this issue · 0 comments

XXHolic commented

目录

引子

碰到深拷贝时循环引用的问题，就去看了 Lodash 中深拷贝方法 cloneDeep 的实现。

Lodash 版本 4.17.15 。

简介

Lodash 是一个一致性、模块化、高性能的 JavaScript 实用工具库。以下面的例子查看深拷贝的逻辑。

var obj1 = {c:'apple'};
var obj2 = {};
obj1.a = obj2;
obj2.b = obj1;
var copy = _.cloneDeep(obj1);

主要实现

找到 cloneDeep.js 文件：

const CLONE_DEEP_FLAG = 1
const CLONE_SYMBOLS_FLAG = 4

function cloneDeep(value) {
  return baseClone(value, CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG)
}

在使用 cloneDeep 时，调用了 baseClone 方法，传递的第二个参数 CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG，使用了按位操作符，按位操作符将其操作数当作 32 位的比特序列（由 0 和 1 组成），有下面的一些规则:

运算符 用法 描述
按位与（AND） a & b 相应比特位都是 1 时，结果才是 1 ，否则为 0。
按位或（OR） a | b 相应比特位至少有一个是 1 时，结果是 1 ，否则为 0。
按位异或（XOR） a ^ b 相应比特位有且只有一个是 1 时，结果是 1 ，否则为 0。
按位非（NOT） ~ a 比特位 1 变成 0，0 变成 1。

CLONE_DEEP_FLAG | CLONE_SYMBOLS_FLAG 转换为二进制也就是 0001 | 0100 ，按照上面规则结果就是 0101 ，转换为数值就是 5 。

然后看 baseClone 方法实现。在 .internal 文件夹下找到 baseClone.js ，在这里列出主要的逻辑和方法：

// 省略其它方法的引用

// 克隆用的位掩码
const CLONE_DEEP_FLAG = 1
const CLONE_FLAT_FLAG = 2
const CLONE_SYMBOLS_FLAG = 4

// 对象使用 toString 后的结果常量 总共有 24 个，这里列举 3 个作为示例
const argsTag = '[object Arguments]'
const arrayTag = '[object Array]'
const boolTag = '[object Boolean]'

// 用来标记克隆支持的 toStringTag 的值，基于上面 24 Tag 的值，这里列举 3 个作为示例
const cloneableTags = {}
cloneableTags[argsTag] = cloneableTags[arrayTag] =
cloneableTags[boolTag] = cloneableTags[dateTag] = true

// 用来检查是否拥有属性
const hasOwnProperty = Object.prototype.hasOwnProperty

/**
 * 基于 toStringTag 初始化一个对象克隆
 * 注意：这个方法支持的值有 `Boolean`, `Date`, `Error`, `Map`, `Number`, `RegExp`, `Set`, `String`
 */
function initCloneByTag(object, tag, isDeep) {
  // 针对不同的类型进行不同的初始化
  switch (tag) {
    // 省略
  }
}

/**
 * 初始化数组克隆
 */
function initCloneArray(array) { //省略 }

/**
 * “clone” 和 “cloneDeep” 的基本实现，用于跟踪遍历的对象。
 */
function baseClone(value, bitmask, customizer, key, object, stack) {
  // 根据上面的给出的例子，以下只注释相关的主要逻辑
  let result
  const isDeep = bitmask & CLONE_DEEP_FLAG
  const isFlat = bitmask & CLONE_FLAT_FLAG
  const isFull = bitmask & CLONE_SYMBOLS_FLAG

  // 自定义克隆相关
  if (customizer) {
    result = object ? customizer(value, key, object, stack) : customizer(value)
  }
  if (result !== undefined) {
    return result
  }
  // 这里的 isObject 方法使用了 typeof 检测和判断 null
  if (!isObject(value)) {
    return value
  }
  const isArr = Array.isArray(value)
  // getTag 里面主要使用 toString 得到值返回
  const tag = getTag(value)
  if (isArr) {
    result = initCloneArray(value)
    if (!isDeep) {
      return copyArray(value, result)
    }
  } else {
    const isFunc = typeof value == 'function'

    if (isBuffer(value)) {
      return cloneBuffer(value, isDeep)
    }
    if (tag == objectTag || tag == argsTag || (isFunc && !object)) {
      result = (isFlat || isFunc) ? {} : initCloneObject(value)
      if (!isDeep) {
        return isFlat
          ? copySymbolsIn(value, copyObject(value, keysIn(value), result))
          : copySymbols(value, Object.assign(result, value))
      }
    } else {
      if (isFunc || !cloneableTags[tag]) {
        return object ? value : {}
      }
      result = initCloneByTag(value, tag, isDeep)
    }
  }
  // 以上主要就是对 result 的初始化处理，下面就是包含检查循环引用的逻辑
  // Stack 判断循环引用的主要方法，见下面的分析
  stack || (stack = new Stack)
  const stacked = stack.get(value)
  // 在 stacked 中有值的话就直接返回，这里就解决了循环引用的问题
  if (stacked) {
    return stacked
  }
  stack.set(value, result)

  // 省略 mapTag 和 setTag 的处理

  if (isTypedArray(value)) {
    return result
  }

  // 获取属性名方法
  const keysFunc = isFull
    ? (isFlat ? getAllKeysIn : getAllKeys)
    : (isFlat ? keysIn : keys)

  // 由对象的属性名组成的数组
  const props = isArr ? undefined : keysFunc(value)
  // arrayEach 方法根据得到的 props 遍历属性
  arrayEach(props || value, (subValue, key) => {
    if (props) {
      key = subValue
      subValue = value[key]
    }
    // 递归处理
    assignValue(result, key, baseClone(subValue, bitmask, customizer, key, value, stack))
  })
  return result
}

从上面可以大体的看出，深拷贝方法会在遍历属性时，把每次原对象的值，保存在一个数组里面，然后每次都会基于数组检查。这样就可以解决循环引用的问题。

方法中涉及到两个重要的方法： Stack 和 ListCache 。Stack 在初始化时，使用了 ListCache ，下面简单介绍一下：

ListCache

ListCache 作用是创建保存对象数组，初始化属性有：

  • size
  • __data__

提供的方法有：

  • clear：重置数据 __data__ 和 size
  • delete：根据 key 删除
  • get：根据 key 获取值
  • has：根据 key 判断是否有值
  • set：设置 key 和对应 value

Stack

Stack 创建一个缓存 key-value 的栈，初始化属性有：

  • size
  • __data__

提供的方法有：

  • clear：清空数据
  • delete：根据 key 删除
  • get：根据 key 获取值
  • has：根据 key 判断是否有值
  • set：设置 key 和对应 value

初始化生成的数据是基于 ListCache，这些方法也主要是基于 ListCache 的方法。当 ListCache 数据长度大于或等于 LARGE_ARRAY_SIZE-1 时，会将所有的数据通过 MapCache 转换为 Map 类型的数据。这里这么转换的原因，可能是数组超过一定长度后，Map 比 Array 性能更好，或者更加方便。

接下来结合实际数据来看下过程是什么样子的。

关键数据

下面是示例在执行递归过程中的关键数据。

第一次执行 baseClone

stack 初始化值：

40-stack-init

stack 第一次设置值后：

40-stack-first

  props = ["c", "a"];
  arrayEach(props || value, (subValue, key) => {
    // some code
    assignValue({}, "c", baseClone("apple", bitmask, customizer, "c", value, stack))
  });
  return result;

第二次执行 baseClone

由于 value 为纯字符串，直接返回了结果，传递给 assignValue 方法。

assignValue({}, "c", "apple") // {c:"apple"}

数组第一项遍历结束，开始第二项遍历。

assignValue({c:"apple"}, "a", baseClone(value.a, bitmask, customizer, "a", value, stack))

第三次执行 baseClone

在 stack 中没有找到对应值，第二次设置值后：

40-stack-second

开启新的遍历。

  props = ["b"];
  arrayEach(props || value, (subValue, key) => {
    // some code
    assignValue({}, "b", baseClone(value.b, bitmask, customizer, "b", value, stack))
  })

第四次执行 baseClone

这次循环在 stack 中匹配到了值，直接返回了结果，这里返回的结果是指向第二次中 result 。

assignValue({}, "b", {c:"apple"});
// after arrayEach done
return result; // {b:{c:"apple"}}

结束后回到第二次执行的 assignValue 中，

assignValue({c:"apple"}, "a", {b:{c:"apple"}});
// after arrayEach done
return result;

至此深拷贝结束。

参考资料