循环引用和深度克隆

August 16 2019

简介

深度克隆我想很多人都写过，但是很多人实现的都是简单版本，对于复杂的深度克隆，基本上工程上大家都会使用 underscore 的 cloneDeep，那么深度克隆有什么技术难点呢：

  • 复杂数据类型，比如函数、正则、日期、Symbol 等不能通过直接遍历属性的方式拷贝
  • 数据可能会有循环引用，如果一直拷贝就会无穷递归

我最近在对以前实现的一个深度克隆进行思考改进的时候，灵感来了有了一点思路，下面分别进行说明

复杂数据类型

第一，我们先处理复杂数据类型，我们只要实现一个严格的数据类型判断，在拷贝的时候进行判断，并分别进行处理

  • 对于基本类型数据，直接复制
  • 对于 正则对象，可以提取字符串，再调用构造函数重新创建正则对象
  • 对于日期对象，也可以通过构造函数重新黄建
  • 其实比较难的是函数对象，主要是 new Function 传入的字符串会被包装到一个匿名函数中并返回，我用了一些比较hack的办法，主要是处理函数名和参数，算是暂时解决了这个问题。
  • 除此之外的对象可以递归遍历

下面直接看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
function cloneObject(src) {
  var newValue;

  if (!src ||
      isString(src) ||
      isNumber(src) ||
      isBoolean(src)) { //基本值 null, undefined, string, number, bool 直接复制

    newValue = src;

  } else if (isDate(src)) { //日期

    newValue = new Date(src);

  } else if (isFunction(src)) { // 函数
    // 方法一，把函数解体

    // 一个函数分为三个部分，名字、参数、函数体 转换为字符串后，要分别解析出来

    var fnString = src.toString().replace(/[\r\n]*\s+/g, ' ');//去掉换行符
    var fnMatch = fnString.match(/^function\s*(?:([\w\$]*)\s*(?:\(([\w,]*)\))(?:\s*\{(.*)\}))/);//
    var fnName = fnMatch[1];
    var fnArgs = fnMatch[2].split(',');
    var fnBody = fnMatch[3];

    // 如果函数字符串中用名字递归调用自己，我们则relace为arguments.callee
    // 函数名前面和后面必然有边界符才替换
    if (fnName) {
      fnBody = fnMatch[3].replace(new RegExp('\\b'+ fnName + '\\b'), 'arguments.callee');
    }

    newValue = new Function(...fnArgs, fnBody); // 这里要借助... 不然很难展开参数


    // 第二种，一种比较hack的方法，替换函数名字，增加立即调用

    // 如果传给Function一个带有function声明的函数字符串的话，一定需要函数名，
    // 而且返回的函数被匿名函数包裹，我们通过在字符串后面添加立即执行函数来执行
    // 由于这个函数时被封闭的，所以名字可以随意
    // var fnString = src.toString().replace(/[\r\n]*\s+/g, ' ');
    // var fnMatch = fnString.match(/^function\s*(?:([\w\$]*))/);
    // var fnName = fnMatch[1] ? fnMatch[1] : 'noName';

    // if (!fnMatch[1]) {
    //     fnString = fnString.replace('function', 'function ' + fnName);
    // }

    // // 追加立即调用
    // fnString += ';' + fnName + '.apply(this, [].slice.call(arguments));'

    // newValue = new Function(fnString); // 这里会返回一个匿名函数，匿名函数中包裹原来的函数和函数调用

  } else if (isRegExp(src)) { // 正则

    // 一个正则对象的字符串分为两种情况，我们只需要处理字面量
    // 1. /^abc/ 这种是字面量，处理为 ^abc，对于/^abc/ig 这种，要把ig提取出来作为RegExp的第二个参数
    // 2. 还有通过RegExp创建的 ^abc，无需处理

    var reg = src.toString();
    var start = 1;
    var last = reg.lastIndexOf('/');

    var patten = reg.slice(start, last);
    var end = reg.slice(last+1); // i、g、m ...

    newValue = new RegExp(patten, end);

  } else if (isArray(src) || isObject(src)){ // 数据和对象

    for (var item in src) {
        if (src.hasOwnProperty(item)) {  //防止继承属性
          newValue[item] = cloneObject(src[item]); // 递归复制
        }
      }

  } // end else

  return newValue;
}

由于数据类型判断的实现比较简单，就不在这里占篇幅了，通过上面的代码，可以看出函数的处理是最复杂的，因为传给 Function 构造函数的字符串都会被放进一个匿名函数进行返回，我实现了两种hack：

  • 一种是，对于原函数的字符串，通过正则提取函数名、参数、函数体，由于函数体可能递归调用函数自己，所以我们替换了函数体内和函数名同名的字符串为 arguments.callee，然后把参数和函数体分别传给 Function。

    对于Function的参数展开目前我们使用了ES6的...展开符，如果没有这个运算符，我们如何处理这里的参数是个问题，而且这里不能调用apply，我有了一点思考，准备单开一个主题来聊聊我的思路

  • 第二种是，我们直接传递原函数的字符串给 Function，但是现在返回的函数是一个匿名函数包裹了原函数的形式，不能被直接调用，所以我们在匿名函数内部实现了函数立即调用，并通过匿名函数的参数调用原函数，并将我们添加的调用字符串追加到原函数的字符串后面，传给Function即可

如果不用这种方式处理的话，目前我还没有想到什么理想的方案，如果各位有想法的话欢迎交流

解决循环引用

我那天在草稿纸上画一棵树的时候，突然想到了循环引用的问题，并开始了展开思考，当A对象引用了B对象，而B对象又引用了A对象的话就构成了循环引用，如果采用上面的方法，碰到对象就递归，那么就会进入无线循环，如何解决呢，我们要做的不是斩断这个引用，而是如果源对象就是相互引用的，那么我们拷贝的结果也应当是相互引用的，考虑如下数据

1
2
3
4
5
6
7
8
9
var a = {
  name: 'a',
}
var b = {
  name: 'b',
}

a.src = b;
b.src = a;

我也实现过两次，下面展开我的思路

第一种：类似原型链的方式

如果大家了解原型链，就比较好理解这种方式，当我们使用 instanceof 操作符的时候，它会一直遍历原型链检查原型对象直到 null 才终止，我的思路和这个思想差不多。

我们可以把它想象成有两颗节点的一棵树，一开始只有一个父节点为null的根节点，当从根节点向下遍历的时候，判断这个节点的祖先节点是否和该节点指向同一个地址，如果是，则表示进入循环，直接复制地址，然后返回（不进入递归）。如果遍历完祖先节点都没有找到相同相同地址的节点，表示没有循环，则将该节点加入这棵树。

这棵树长这样，由于curent是函数闭包里面的局部变量，每次递归的时候，传递给子节点，子节点保存父节点的引用和自己的引用，所以current不会相互影响，下面的代码省略了一些之前的一些过程，只表达主要思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 刚开始的根节点
function cloneObject(a, parent=null) {
  var current = {
    parent: parent, // 这是我们要遍历的树，伴随指针
    src: a, // 这是原对象，我们不能更改，只是用作检查
  }；
  if (!checkCircle(a, current)) {
    // 遍历a的属性clone，这里省略了循环
    cloneObject(a, current);
  } else {
    return a
  }
  
}

// 加入b
function cloneObject(b, parent=a) {
  var current = ｛
      parent: parent,
      src: b
  ｝
  if (!checkCircle(b, current)) {
    // 遍历b的属性clone，这里省略了循环
    cloneObject(b, current);
  } else {
    return b
  }
}

// 每次遇到一个对象 进行遍历检查是否循环引用
function checkCircle(src, parent) {
  var current = parent;
  
  while (current) {
    if (current.src === src) {
      return true;
    }
    current = current.parent;
  }
  return false;
}

上面的代码很清晰的表达做了什么事情，这里的思路没问题，但没有完全解决问题，所以没有贴出完整代码。我刚开始很喜滋滋的欣赏自己的成果，然后画了一颗复杂的树进行测试，然后发现，对于当前节点对兄弟节点或者兄弟节点的子孙节点进行引用的情况没有很好的处理，这样会出现什么情况呢，就是兄弟节点会复制自己的子孙节点，而当前节点也会复制其兄弟节点或其子孙节点，这种情况表示正在创建的这颗对象树有两份其兄弟节点的拷贝，这和原对象的引用情况不符，也不是我们想要的情况，毕竟浪费了内存。

第二种：柳暗花明又一村的标记法

在我苦思冥想以后，我仍然基于这棵树有了新的思路，如果一个对象表示这棵树的一个节点，它一旦被访问就保存到访问列表，然后保存被复制前的地址和复制后的地址，如果下次再访问就表示被创建过了，不管其他父节点，子孙节点还是兄弟节点再访问我，就表示重复访问，那我就直接把我上次创建的新的的引用地址给它，它就不用重复创建了，这个应该算是标记法吧。而且这个还很好的解决了循环引用的问题，因为一个节点一旦被访问过就被保存起来，下一次再访问如果不是重复创建就是循环引用，perfect，这个方案非常完美的解决了问题。

下面是 show time 。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// 创建一个节点图，保存访问过的节点
var nodesMap = {
  nodes: [], /* { oldSrc: a, newSrc: b } */

  add: function(node) {
    this.nodes.push(node);
  },

  reset: function() {
    this.nodes.length = 0;
  },

  find: function(ref) {
    var i,
        len,
        nodes = this.nodes;

    for ( i = 0, len = nodes.length; i < len; i++) {
      if (ref === nodes[i].oldSrc) {
        return nodes[i];
      }
    }

    return;
  }
}

function cloneObject(src) {
  var newValue;

  if (!src ||
      isString(src) ||
      isNumber(src) ||
      isBoolean(src)) { //基本值 null, undefined, string, number, bool

    newValue = src;

  } else if (isDate(src)) { //日期

    newValue = new Date(src);

  } else if (isFunction(src)) {
    // 方法一，把函数解体

    // 一个函数分为三个部分，名字、参数、函数体 转换为字符串后，要分别解析出来

    var fnString = src.toString().replace(/[\r\n]*\s+/g, ' ');//去掉换行符
    var fnMatch = fnString.match(/^function\s*(?:([\w\$]*)\s*(?:\(([\w,]*)\))(?:\s*\{(.*)\}))/);//
    var fnName = fnMatch[1];
    var fnArgs = fnMatch[2].split(',');
    var fnBody = fnMatch[3];

    // 如果函数字符串中用名字递归调用自己，我们则relace为arguments.callee
    // 函数名前面和后面必然有边界符才替换
    if (fnName) {
      fnBody = fnMatch[3].replace(new RegExp('\\b'+ fnName + '\\b'), 'arguments.callee');
    }

    newValue = new Function(...fnArgs, fnBody); // 这里要借助... 不然很难展开参数


    // 第二种，一种比较hack的方法，替换函数名字，增加立即调用

    // 如果传给Function一个带有function声明的函数字符串的话，一定需要函数名，
    // 而且返回的函数被匿名函数包裹，我们通过在字符串后面添加立即执行函数来执行
    // 由于这个函数时被封闭的，所以名字可以随意
    // var fnString = src.toString().replace(/[\r\n]*\s+/g, ' ');
    // var fnMatch = fnString.match(/^function\s*(?:([\w\$]*))/);
    // var fnName = fnMatch[1] ? fnMatch[1] : 'noName';

    // if (!fnMatch[1]) {
    //     fnString = fnString.replace('function', 'function ' + fnName);
    // }

    // // 追加立即调用
    // fnString += ';' + fnName + '.apply(this, [].slice.call(arguments));'

    // newValue = new Function(fnString); // 这里会返回一个匿名函数，匿名函数中包裹原来的函数和函数调用

  } else if (isRegExp(src)) {

    // 一个正则字符串分为两种情况，我们只需要处理字面量
    // 1. /^abc/ 这种是字面量
    // 2. 还有通过RegExp创建的 ^abc

    var reg = src.toString();
    var start = 1;
    var last = reg.lastIndexOf('/');

    var patten = reg.slice(start, last);
    var end = reg.slice(last+1); // i、g、m ...

    newValue = new RegExp(patten, end);

  } else if (isArray(src) || isObject(src)){ // array and object

    // 从节点缓存中查找如果找到，则不用递归
    var current = nodesMap.find(src);

    if (!current) { // 如果没找到
      // 如果没找到，则创建新地址
      newValue = isArray(src) ? [] : {};

      // 每当访问一个节点的时候，会做两件事
      // 一是保存旧地址，而是创建新地址
      nodesMap.add({
        oldSrc: src,
        newSrc: newValue,
      });

      for (var item in src) {
        if (src.hasOwnProperty(item)) {  //防止继承属性
          newValue[item] = cloneObject(src[item]);
        }
      }

    } else {

      // 如果该节点被访问过，必然已经创建了新地址，则指向新地址即可
      newValue = current.newSrc;

    }

  } // end else

  return newValue;
}

// 处理一些克隆之外的工作
function cloneDeep(src) {
  var res = cloneObject(src);

  nodesMap.reset();

  return res;
}

主要增加了几个东西

  • 首先是nodesMap，保存了一个已访问列表，每个元素都保存了一个节点的新地址和旧地址
  • 当判断是对象类型的时候，就从nodesMap中查找该对象
    • 如果找到，则说明已经被访问过，并且肯定被复制了，就把新地址返回即可，不用再递归
    • 如果没找到，则说明还是第一次访问，就创建新对象，并在nodesMap中新增访问节点，保存了被复制的对象的旧地址和新地址
  • 增加了一次cloneDeep的调用，这是由于cloneObject完成的时候，需要做一些清理工作

上面的就是完整思路和代码了

其实还有 Symbol 类型的数据没处理，这个我想了下，Symbol 是一个生成一个唯一标识符，我知道有全局注册表，但是如果从全局注册表拿出来的话，那个Symbol就是原来的，如果生成一个新的话，是否有必要？而且Symbol数据类型对于用户几乎是不可见的

所以对于是否拷贝 Symbol 我持保留态度

如有问题，欢迎交流

biu -。-

avatar

神无

舍悟离迷，六尘不改。