实现深拷贝之调用栈溢出、循环引用、复杂数据类型

前言

最近在项目中，尝试使用 JSON.parse(JSON.stringify(..)) 来深拷贝数据，发现 undefined 会被自动忽略。

查阅 MDN-JSON.stringify() 后得知 undefined、任意的函数以及 symbol 值，在序列化过程中会被忽略（出现在非数组对象的属性值中时）或者被转换成 null（出现在数组中时）。文档还指出 Date、NaN、Infinity...等类型都会被简易处理，不能保证序列化前后数据的一致性。

既然原生 API 靠不住，便自己手写一个深拷贝，主要遇到了三个难题：

调用栈溢出
循环引用
复杂数据类型

下面 👇，我带领大家从 V0 开始，翻越这三座大山，逐步实现一个小而美、功能俱全的深拷贝函数。

人人都会的解法

deepCloneV0 采用了递归的解决方法。

js
const deepCloneV0 = target => {
  if (typeof target !== "object" && target) return target;
  const cloneTarget = {};
  for (const key in target) {
    if (target.hasOwnProperty(key)) {
      if (Object.prototype.toString.call(target[key]) === "[object Object]") {
        cloneTarget[key] = deepCloneV0(target[key]);
      } else {
        cloneTarget[key] = target[key];
      }
    }
  }
  return cloneTarget;
};

js
const deepCloneV0 = target => {
  if (typeof target !== "object" && target) return target;
  const cloneTarget = {};
  for (const key in target) {
    if (target.hasOwnProperty(key)) {
      if (Object.prototype.toString.call(target[key]) === "[object Object]") {
        cloneTarget[key] = deepCloneV0(target[key]);
      } else {
        cloneTarget[key] = target[key];
      }
    }
  }
  return cloneTarget;
};

避免调用栈溢出

众所周知，在 JavaScript 中存在一类错误：Uncaught RangeError: Maximum call stack size exceeded，他表示栈的调用次数超过了 V8 引擎所能承受的最大极限，这是递归天生的缺陷。

为了验证 V0 的不足，我写了一个工具函数，它可以生成指定层级的嵌套对象：

js
const genNestedObj = level => {
  const nested = {},
    stack = [nested];
  let i = 1;
  while (i <= level) {
    const parent = stack.pop();
    let child = (parent[i] = {});
    stack.push(child);
    i++;
  }
  return nested;
};

js
const genNestedObj = level => {
  const nested = {},
    stack = [nested];
  let i = 1;
  while (i <= level) {
    const parent = stack.pop();
    let child = (parent[i] = {});
    stack.push(child);
    i++;
  }
  return nested;
};

js
const nestedObj = genNestedObj(10000);
// { 1: { 2: { 3: {……} } } }
// throw an error
const cloneObj = deepCloneV0(nestedObj);

js
const nestedObj = genNestedObj(10000);
// { 1: { 2: { 3: {……} } } }
// throw an error
const cloneObj = deepCloneV0(nestedObj);

看来递归是行不通了，但还有循环，使用 while 语句搭配数据结构 - 栈，即可实现改进后的 V1：

js
const deepCloneV1 = target => {
  if (typeof target !== "object" && target) return target;
  const cloneTarget = {};
  // 通过栈来保存上一级对象
  const stack = [
    {
      parent: cloneTarget,
      key: undefined,
      raw: target,
    },
  ];
  while (stack.length) {
    const { parent, key, raw } = stack.pop();
    if (key) {
      // 创建子对象，并维持父对象引用关系
      child = parent[key] = {};
    } else {
      // 第一次拷贝，直接赋值 cloneTarget 最顶级父对象
      child = parent;
    }
    for (const key in raw) {
      if (raw.hasOwnProperty(key)) {
        if (Object.prototype.toString.call(raw[key]) === "[object Object]") {
          stack.push({
            parent: child,
            key,
            raw: raw[key],
          });
        } else {
          child[key] = raw[key];
        }
      }
    }
  }
  return cloneTarget;
};

js
const deepCloneV1 = target => {
  if (typeof target !== "object" && target) return target;
  const cloneTarget = {};
  // 通过栈来保存上一级对象
  const stack = [
    {
      parent: cloneTarget,
      key: undefined,
      raw: target,
    },
  ];
  while (stack.length) {
    const { parent, key, raw } = stack.pop();
    if (key) {
      // 创建子对象，并维持父对象引用关系
      child = parent[key] = {};
    } else {
      // 第一次拷贝，直接赋值 cloneTarget 最顶级父对象
      child = parent;
    }
    for (const key in raw) {
      if (raw.hasOwnProperty(key)) {
        if (Object.prototype.toString.call(raw[key]) === "[object Object]") {
          stack.push({
            parent: child,
            key,
            raw: raw[key],
          });
        } else {
          child[key] = raw[key];
        }
      }
    }
  }
  return cloneTarget;
};

同样测试一下 10000 层对象的情况：

js
const nestedObj = genNestedObj(10000);
// OK
const cloneObj = deepCloneV1(nestedObj);

js
const nestedObj = genNestedObj(10000);
// OK
const cloneObj = deepCloneV1(nestedObj);

js
const demoObj = { a: 1, b: { c: "c" } };
deepCloneV1(demoObj);

js
const demoObj = { a: 1, b: { c: "c" } };
deepCloneV1(demoObj);

以上述代码为例，在此配上图例说明：

破解循环引用

好不容易跨过第一座大山：调用栈溢出，又迎来了新的问题。

在一些对象中，会存在循环引用的情况，举个例子：

js
const o = { some: 1 };
o.A = o;

js
const o = { some: 1 };
o.A = o;

对象 o 上属性 A 的值是它本身，发生了循环依赖。

在 NodeJS 中，循环引用的对象用 [Circular] 表示：

而在 Chrome 中是这样子的：

破解循环引用的关键是 对于已经拷贝过的对象，不再进行拷贝，否则会进入死循环。

大致遵循以下步骤：

查询即将被拷贝的对象在记录中是否存在？
- Y，返回查询到的对象，结束本轮循环
- N，拷贝并记录该对象

这时，以何种数据结构来记录对象就显得尤为重要，Map 凭借其 key 能为任意值、不局限于字符串的特点成为首选，使得 key 能成为一个对象。

我可以直接以对象 o 为键名进行查询，并返回键值 o.

js
const deepCloneV2 = target => {
  if (typeof target !== "object" && target) return target;
  const cloneTarget = {};
  // 记录循环引用
  const map = new Map();
  const stack = [
    {
      parent: cloneTarget,
      key: undefined,
      raw: target,
    },
  ];
  while (stack.length) {
    const { parent, key, raw } = stack.pop();
    let child = parent;
    if (map.has(raw)) {
      // 直接赋值已经拷贝过的对象
      child[key] = map.get(raw);
      continue;
    }
    if (key) {
      child = parent[key] = {};
    }
    // 记录被拷贝的对象
    map.set(raw, child);
    for (const key in raw) {
      if (raw.hasOwnProperty(key)) {
        if (Object.prototype.toString.call(raw[key]) === "[object Object]") {
          stack.push({
            parent: child,
            key,
            raw: raw[key],
          });
        } else {
          child[key] = raw[key];
        }
      }
    }
  }
  return cloneTarget;
};

js
const deepCloneV2 = target => {
  if (typeof target !== "object" && target) return target;
  const cloneTarget = {};
  // 记录循环引用
  const map = new Map();
  const stack = [
    {
      parent: cloneTarget,
      key: undefined,
      raw: target,
    },
  ];
  while (stack.length) {
    const { parent, key, raw } = stack.pop();
    let child = parent;
    if (map.has(raw)) {
      // 直接赋值已经拷贝过的对象
      child[key] = map.get(raw);
      continue;
    }
    if (key) {
      child = parent[key] = {};
    }
    // 记录被拷贝的对象
    map.set(raw, child);
    for (const key in raw) {
      if (raw.hasOwnProperty(key)) {
        if (Object.prototype.toString.call(raw[key]) === "[object Object]") {
          stack.push({
            parent: child,
            key,
            raw: raw[key],
          });
        } else {
          child[key] = raw[key];
        }
      }
    }
  }
  return cloneTarget;
};

用 V2 测试一下含有循环引用的对象，看来正确拷贝了 [Circular].

js
const o = { some: 1 };
o.A = o;
const cloneObj = deepCloneV2(o);
// { some: 1, A: { A: [Circular] } }

js
const o = { some: 1 };
o.A = o;
const cloneObj = deepCloneV2(o);
// { some: 1, A: { A: [Circular] } }

为了方便说明 V2 代码的巧妙之处，我以对象 o 为例，去除了中间代码，做了一个简化版的过程，其核心执行逻辑如下：

js
const map = new Map();
const o = { some: 1 };
o.A = o;
let child = {};
map.set(o, child); // 记录 o 已被拷贝
child.some = 1; // 第一次拷贝
child.A = map.get(o); // 第二次拷贝
child;
// { some: 1, A: [Circular] }

js
const map = new Map();
const o = { some: 1 };
o.A = o;
let child = {};
map.set(o, child); // 记录 o 已被拷贝
child.some = 1; // 第一次拷贝
child.A = map.get(o); // 第二次拷贝
child;
// { some: 1, A: [Circular] }

如图所示，完成了对循环对象的拷贝：

处理复杂数据类型

常言道在 JS 的世界中，万物皆“对象”类型，但这句话是广义上的，正确的说法是万物的原型链顶端皆为对象的原型链。

其实 JS “对象”类型也是有”三六九等“之分的，除了 简单（基本） 数据类型：number、boolean、string、undefined、null、symbol、bigint 可以直接赋值进行深拷贝。

剩下的 复杂（引用） 数据类型均要特殊处理，抛开已实现的 Object（{}）不谈，还要深拷贝 Array、Map、RegExp、Date…… 等众多数据类型，那如何判断这些类型呢？显然 typeof 是行不通的。

在 Lodash 中有一个工具函数叫 getTag，旨在获取对象的类型标记（Tag），即我们所熟知的，利用 Object.prototype.toString.call() 去做类型检测。

js
const getTag = value => {
  if (value == null) {
    return value === undefined ? "[object Undefined]" : "[object Null]";
  }
  return Object.prototype.toString.call(value);
};

js
const getTag = value => {
  if (value == null) {
    return value === undefined ? "[object Undefined]" : "[object Null]";
  }
  return Object.prototype.toString.call(value);
};

如果你想明白其中的原理，戳此链接你所不知道的 toString()。

简而言之，不同的对象在调用此方法后，都会返回遵循 '[object <Type>]' 模式的字符串，例如：

getTag	返回的字符串
`getTag({})`	`[object Object]`
`getTag([])`	`[object Array]`
`getTag(new Set())`	`[object Set]`
`getTag(new Map())`	`[object Map]`
`getTag(new Date())`	`[object Date]`
`getTag(new RegExp())`	`[object RegExp]`
`getTag(new Error())`	`[object Error]`
`getTag(Promise.resolve())`	`[object Promise]`
`getTag(function() {})`	`[object Function]`
`getTag(Math)`	`[object Math]`
`getTag(Intl)`	`[object Intl]`
`getTag(globalThis)`	`[object Window]`（in browser） / `[object global]`（in nodejs）

当然表格中还有许多未列出的对象，难道要全部去实现吗？起码有两个理由证明不用：

对于 Function，两个对象使用一个在内存中处于同一个地址的函数是没有任何问题的，Lodash 中的处理策略是直接返回
深拷贝的核心意义在于数据结构的复制，改动原始数据而不会影响新数据，数据来源一般是后端返回，或者自己为了处理逻辑，前端组装的数据结构，其中极少数情况会包含拷贝 Promise、Error、Math、globalThis…… 此类没有应用场景的情形。

所以我提前定义好深拷贝需要处理的复杂数据类型，至少涵盖 90% 的场景，满足业务需求。

js
const REGEXP_TAG = "[object RegExp]",
  DATE_TAG = "[object Date]",
  MAP_TAG = "[object Map]",
  SET_TAG = "[object Set]",
  OBJECT_TAG = "[object Object]";
ARRAY_TAG = "[object Array]";

js
const REGEXP_TAG = "[object RegExp]",
  DATE_TAG = "[object Date]",
  MAP_TAG = "[object Map]",
  SET_TAG = "[object Set]",
  OBJECT_TAG = "[object Object]";
ARRAY_TAG = "[object Array]";

Tip：自己写的深拷贝函数，比起社区中成熟的 deepClone 库当然还有很多不足，但能让自己构建一个完整的知识体系，无论是在面试中或是日常业务中都能轻松应对。

在上述复杂数据类型中，可以分为两大类型，便于后续代码处理：

可遍历类型
不可遍历类型

可遍历类型

可遍历类型包括 Array、Object、Set、Map，拷贝可遍历类型的前置条件是先创建初始化数据，比如拷贝 Object，要先初始化一个对象字面量 {}。

虽然 weakMap、weakSet 同属于可遍历类型，但由于它们的键名弱引用特性，无法被深拷贝。

这里有一个小技巧，利用原型链上构造函数 prototype.constructor 的方式来通用创建初始化数据。

js
({}.constructor);
// ƒ Object() { [native code] }
new Set().constructor;
// ƒ Set() { [native code] }

js
({}.constructor);
// ƒ Object() { [native code] }
new Set().constructor;
// ƒ Set() { [native code] }

const obj = {} 就是 const obj = new Object() 的语法糖，所以不管是 Object 还是 Array、Set、Map，都可以用下面的方法初始化数据：

js
// ……
if (key) {
  // 使用原始数据的构造函数初始化数据
  child = parent[key] = new raw.constructor();
}
// 处理 Set
if (getTag(child) === SET_TAG) {
  raw.forEach(value => {
    child.add(deepClone(value));
  });
  continue;
}
// 处理 Map
if (getTag(child) === MAP_TAG) {
  raw.forEach((value, key) => {
    child.set(key, deepClone(value));
  });
  continue;
}
// ……

js
// ……
if (key) {
  // 使用原始数据的构造函数初始化数据
  child = parent[key] = new raw.constructor();
}
// 处理 Set
if (getTag(child) === SET_TAG) {
  raw.forEach(value => {
    child.add(deepClone(value));
  });
  continue;
}
// 处理 Map
if (getTag(child) === MAP_TAG) {
  raw.forEach((value, key) => {
    child.set(key, deepClone(value));
  });
  continue;
}
// ……

另外这种方法还有一个好处：因为使用了原对象的构造方法，所以它可以保留对象原型上的数据，如果直接使用普通的 {} ，那么原型必然是丢失了的。

不可遍历类型

剩下的都是不可遍历类型，可以直接用构造函数和原始数据创建一个新对象：

js
switch (tag) {
  case REGEXP_TAG:
    child[key] = new rawVal.constructor(rawVal);
    break;
  case DATE_TAG:
    child[key] = new rawVal.constructor(rawVal);
    break;
  default:
    // boolean string number undefined null symbol bigint
    child[key] = rawVal;
    break;
}

js
switch (tag) {
  case REGEXP_TAG:
    child[key] = new rawVal.constructor(rawVal);
    break;
  case DATE_TAG:
    child[key] = new rawVal.constructor(rawVal);
    break;
  default:
    // boolean string number undefined null symbol bigint
    child[key] = rawVal;
    break;
}

最终完整实现

js
const REGEXP_TAG = "[object RegExp]",
  DATE_TAG = "[object Date]",
  SYMBOL_TAG = "[object Symbol]",
  MAP_TAG = "[object Map]",
  SET_TAG = "[object Set]",
  OBJECT_TAG = "[object Object]";
ARRAY_TAG = "[object Array]";
const getTag = value => {
  if (value == null) {
    return value === undefined ? "[object Undefined]" : "[object Null]";
  }
  return Object.prototype.toString.call(value);
};
function deepCloneV3(target) {
  // 如果不是复杂数据类型，直接返回
  if (typeof target !== "object" || target === null) return target;
  // 定义克隆对象
  const cloneTarget = {};
  // 记录循环引用
  const map = new Map();
  // 通过栈来保存上一级对象
  const stack = [
    {
      parent: cloneTarget,
      key: undefined,
      raw: target,
    },
  ];
  while (stack.length) {
    const node = stack.pop();
    const { parent, key, raw } = node;
    // 第一次拷贝，直接赋值 cloneTarget 最顶级父对象
    let child = parent;
    if (map.has(raw)) {
      // 直接赋值已经拷贝过的对象
      child[key] = map.get(raw);
      continue;
    }
    // 记录被拷贝的对象
    map.set(raw, child);
    if (key) {
      // 创建子对象，并维持父对象引用关系
      // 使用原始数据的构造函数初始化数据
      child = parent[key] = new raw.constructor();
    }
    // 处理 Set
    if (getTag(child) === SET_TAG) {
      raw.forEach(value => {
        child.add(deepCloneV3(value));
      });
      continue;
    }
    // 处理 Map
    if (getTag(child) === MAP_TAG) {
      raw.forEach((value, key) => {
        child.set(key, deepCloneV3(value));
      });
      continue;
    }
    for (const key in raw) {
      if (raw.hasOwnProperty(key)) {
        const rawVal = raw[key];
        const tag = getTag(rawVal);
        if (
          tag === OBJECT_TAG ||
          tag === ARRAY_TAG ||
          tag === SET_TAG ||
          tag === MAP_TAG
        ) {
          stack.push({
            parent: child,
            key,
            raw: rawVal,
          });
        } else {
          switch (tag) {
            case REGEXP_TAG:
              child[key] = new rawVal.constructor(rawVal);
              break;
            case DATE_TAG:
              child[key] = new rawVal.constructor(rawVal);
              break;
            default:
              // boolean string number undefined null symbol bigint
              child[key] = rawVal;
          }
        }
      }
    }
  }
  return cloneTarget;
}

js
const REGEXP_TAG = "[object RegExp]",
  DATE_TAG = "[object Date]",
  SYMBOL_TAG = "[object Symbol]",
  MAP_TAG = "[object Map]",
  SET_TAG = "[object Set]",
  OBJECT_TAG = "[object Object]";
ARRAY_TAG = "[object Array]";
const getTag = value => {
  if (value == null) {
    return value === undefined ? "[object Undefined]" : "[object Null]";
  }
  return Object.prototype.toString.call(value);
};
function deepCloneV3(target) {
  // 如果不是复杂数据类型，直接返回
  if (typeof target !== "object" || target === null) return target;
  // 定义克隆对象
  const cloneTarget = {};
  // 记录循环引用
  const map = new Map();
  // 通过栈来保存上一级对象
  const stack = [
    {
      parent: cloneTarget,
      key: undefined,
      raw: target,
    },
  ];
  while (stack.length) {
    const node = stack.pop();
    const { parent, key, raw } = node;
    // 第一次拷贝，直接赋值 cloneTarget 最顶级父对象
    let child = parent;
    if (map.has(raw)) {
      // 直接赋值已经拷贝过的对象
      child[key] = map.get(raw);
      continue;
    }
    // 记录被拷贝的对象
    map.set(raw, child);
    if (key) {
      // 创建子对象，并维持父对象引用关系
      // 使用原始数据的构造函数初始化数据
      child = parent[key] = new raw.constructor();
    }
    // 处理 Set
    if (getTag(child) === SET_TAG) {
      raw.forEach(value => {
        child.add(deepCloneV3(value));
      });
      continue;
    }
    // 处理 Map
    if (getTag(child) === MAP_TAG) {
      raw.forEach((value, key) => {
        child.set(key, deepCloneV3(value));
      });
      continue;
    }
    for (const key in raw) {
      if (raw.hasOwnProperty(key)) {
        const rawVal = raw[key];
        const tag = getTag(rawVal);
        if (
          tag === OBJECT_TAG ||
          tag === ARRAY_TAG ||
          tag === SET_TAG ||
          tag === MAP_TAG
        ) {
          stack.push({
            parent: child,
            key,
            raw: rawVal,
          });
        } else {
          switch (tag) {
            case REGEXP_TAG:
              child[key] = new rawVal.constructor(rawVal);
              break;
            case DATE_TAG:
              child[key] = new rawVal.constructor(rawVal);
              break;
            default:
              // boolean string number undefined null symbol bigint
              child[key] = rawVal;
          }
        }
      }
    }
  }
  return cloneTarget;
}

来一波数据测试：

js
let arr = [1, 2, 3];
let obj = { name: "jack" };
let reg = new RegExp("\\d+", "im");
let set = new Set([1, 2, 3]);
let map = new Map([
  [1, 1],
  [2, 2],
]);
let date = new Date("1998-5-21");
var A = {
  _number: 1,
  _null: null,
  _undefined: undefined,
  _symbol: Symbol("s"),
  _obj: obj,
  _set: set,
  _map: map,
  _arr: arr,
  _date: date,
  _reg: reg,
};
A.A = A;

js
let arr = [1, 2, 3];
let obj = { name: "jack" };
let reg = new RegExp("\\d+", "im");
let set = new Set([1, 2, 3]);
let map = new Map([
  [1, 1],
  [2, 2],
]);
let date = new Date("1998-5-21");
var A = {
  _number: 1,
  _null: null,
  _undefined: undefined,
  _symbol: Symbol("s"),
  _obj: obj,
  _set: set,
  _map: map,
  _arr: arr,
  _date: date,
  _reg: reg,
};
A.A = A;

有兴趣的小伙伴，可以继续拓展，比如实现 Function 及其他数据类型的拷贝，加深对 JS 基础的理解。

这篇文章就先到这了~

Reference

https://juejin.cn/post/6844903929705136141