Node-JS专精07手写深拷贝02

思路

递归

  • 看节点的类型 7种(number bool string undefined null symbol 和 object)
    • array function regexp date 是 object的子类型
  • 如果是简单数据类型就直接拷贝
  • 如果是 object 就情况讨论

Object

  • 普通 object 的 for in ?
    • for in 有bug
  • 数组 array - Array初始化
    • 它里面可能还是对象
  • 函数 function - 怎么拷贝？ 闭包？
  • 日期 Date - 怎么拷贝？

开始干

  • 创建目录 

    1
    2
    3
    4
    5
    根目录
    deep-clone

    src/index.js
    test/index.js

  • 引入 chai 和 sinon

    • 参考代码引入库
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      npm init -y 

      加入如下内容
      "scripts": {
          "test": "mocha test/**/*.js"
      },
      "devDependencies": {
          "chai": "^4.2.0",
          "mocha": "^6.2.0",
          "sinon": "^7.4.1",
          "sinon-chai": "^3.3.0"
      }

      yarn install 

      运行 yarn test
      如果显示 0 passing (1ms) 代表环境搭建成功

  • 开始驱动测试开发

    • src/index.js

      1
      2
      function deepClone(){}
      module.exports = deepClone;

    • 注意！ 由于是js

      • 引入模块：js是不支持 import的 所以只能用 require
      • 导出模块：js是不支持 export default 所以只能用 module.exports = xxx
    • test/index.js
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      // 注意！！！
      // js是不支持 import的 所以只能用 require
      const chai = require("chai");
      const sinon = require("sinon");
      const sinonChai = require("sinon-chai");
      chai.use(sinonChai);
      const assert = chai.assert;
      const deepClone = require("../src/index");

      describe('deepClone',()=>{
          it("是一个函数",()=>{
              assert.isFunction(deepClone)
          })
      })

  • 测试失败 =》 改代码 =》 测试成功 =》 加测试 =》 测试失败

  • 这就是永动机

鸡贼的完成基本数据类型深拷贝

src/index.js

1
2
3
4
5
function deepClone(source){
    return source;
}

module.exports = deepClone;

test/index.js

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
const chai = require("chai");
const sinon = require("sinon");
const sinonChai = require("sinon-chai");
chai.use(sinonChai);
const assert = chai.assert;
const deepClone = require("../src/index");

describe('deepClone',()=>{
    it("是一个函数",()=>{
        assert.isFunction(deepClone)
    })

    it("能够复制基本类型",()=>{
        const n = 123;
        const n2 = deepClone(n);
        assert(n === n2);

        const s = "123456";
        const s2 = deepClone(s);
        assert(s === s2);

        const b = true;
        const b2 = deepClone(b);
        assert(b === b2);

        const u = undefined;
        const u2 = deepClone(u);
        assert(u === u2);

        const empty = null;
        const empty2 = deepClone(empty);
        assert(empty === empty2);

        const sym = Symbol();
        const sym2 = deepClone(sym);
        assert(sym === sym2);
        
    })
})

Symbol的疑问？ 为什么会相等

  • 不是说不会有两个相同的 Symbol吗？它到底是引用呢？还是没有引用啊？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var a = Symbol()
var b = a;

// 此时 a 和 b 是同一个 Symbol吗？ 是不是不确定啊

// 但是如果这样
var a2 = 1;
var b2 = a2;
// a2 和 b2 是同一个 1吗 在内存里？ 你会回答 不是

// 同样的问题回到 Symbol

// a === b 吗？ 答案是 true
// 所以 symbol 可能是个 不可变的引用类型。 此时你已经陷入知识盲区了，就不要在深入了

复制简单对象

test/index.js

1
2
3
4
5
6
7
8
9
10
describe("对象",()=>{
    it("能够复制普通对象",()=>{
        const a = {name: "方方", chlid: {name: "小方方"}};
        const a2 = deepClone(a);
        assert(a !== a2);
        assert(a.name === a2.name);
        assert(a.chai !== a2.chlid);
        assert(a.chlid.name === a2.chlid.name);
    })
})

通常你会这样想

  • for in的坑 你怎么知道 key是 source的属性 还是它原型上的属性
1
2
3
4
5
6
7
8
9
10
11
12
function deepClone(source){
    if(source instanceof Object){
        const dist = new Object();
        for(let key in source){
            dist[key] = deepClone(source[key]);
        }
        return dist;
    }
    return source;
}

module.exports = deepClone;

试试数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
it("能够复制数组对象",()=>{
    const a = [[11,12],[21,22],[31,32]]
    const a2 = deepClone(a);
    assert(a !== a2);
    assert(a[0] !== a2[0]);
    assert(a[1] !== a2[1]);
    assert(a[2] !== a2[2]);
    assert.deepEqual(a,a2);
})

// yarn test报错
AssertionError: expected [ [ 11, 12 ], [ 21, 22 ], [ 31, 32 ] ] to deeply equal { Object (0, 1, ...) }
// 你可以把代码拷到浏览器试一下， a2 实际是一个 包含 0,1,2 key的伪数组

// 要分支处理判断 Object的子类型

修改src/index.js

  • 注意此时不要优化代码
  • 注意此时不要优化代码
  • 注意此时不要优化代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function deepClone(source){
    if(source instanceof Object){
        if(source instanceof Array){
            const dist = new Array();
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }else{
            const dist = new Object();
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }
    }
    return source;
}

module.exports = deepClone;

复制函数

test/index.js

1
2
3
4
5
6
7
8
9
10
11
12
13
it("能够复制函数",()=>{
    const a = function(x,y){
        return x + y;
    }
    a.xxx = { yyy: { zzz: 1 } }
    const a2 = deepClone(a);
    assert(a !== a2);
    assert(a.xxx.yyy.zzz === a2.xxx.yyy.zzz);
    assert(a.xxx.yyy !== a2.xxx.yyy);
    assert(a.xxx !== a2.xxx);
    assert(a(1,2) === a2(1,2));

})

网上的一个思路 eval

1
2
3
4
5
6
7
8
9
10
11
12
// 浏览器控制台里
function x(a,b){return a+b;}
// 直接f 显示是个函数 
// 你要这样
console.dir(x);
// 你会发现他的 __proto__ 里有个 toString
x.toString() // "function x(a,b){return a+b;}"


// 假设 source是一个函数 而且是具名函数
eval(source.toString())
// 但是 eval 是一个很难控制的东西

我们的思路是 call / apply

  • 唯一的缺陷就是比原来的函数多嵌套了一层
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
function deepClone(source){
    if(source instanceof Object){
        if(source instanceof Array){
            const dist = new Array();
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        } else if(source instanceof Function){
            const dist = function(){
                return source.apply(this,arguments);
            }
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }else{
            const dist = new Object();
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }
    }
    return source;
}

module.exports = deepClone;

环检测

  • 我们完成的递归都是对象有结尾的，而如果对象是个环状的就有问题了
1
2
3
4
5
var a = {name:"方方"}
a.self = a

// 此时 a 就是一个环状结构
a.self.self.self.self ..... .self = a  // true

思路

  • 优化代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    function deepClone(source){
        if(source instanceof Object){
            let dist;
            if(source instanceof Array){
                dist = new Array();
            } else if(source instanceof Function){
                dist = function(){
                    return source.apply(this,arguments);
                }
            }else{
                dist = new Object();
            }
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }
        return source;
    }

    module.exports = deepClone;

  • 你要把出现过的 节点 和 克隆后的节点 都保存起来

src/index.js

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
let cache = [];
function deepClone(source){
    if(source instanceof Object){
        let cacheDist = findCache(source)
        if(cacheDist){
            console.log("有缓存")
            return cacheDist;
        }else{
            console.log("没缓存")
            let dist;
            if(source instanceof Array){
                dist = new Array();
            } else if(source instanceof Function){
                dist = function(){
                    return source.apply(this,arguments);
                }
            }else{
                dist = new Object();
            }
            // 数据源 和 副本 都存入缓存 ，注意一定要 在 dist创建成功之后就把它 存入，防止重复的生成
            cache.push([source,dist])
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }
    }
    return source;
}

function findCache(source){
    for(let i=0;i<cache.length;i++){
        if(cache[i][0] === source){
            return cache[i][1];
        }
    }
    return undefined
}

module.exports = deepClone;

如果这个对象不是环，就是特别深呢？

  • 由于你用的是递归它会使用调用栈，所以在一定层数后它会爆栈
1
a.x.x.x.x.x.x.x.x.x.x  大概2w层呢？

test/index.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
xit("不会爆栈",()=>{
    const a = {child:null};
    let b = a
    for(let i=0;i<20000;i++){
        b.child = {
            child:null
        }
        b = b.child
    }
    const a2 = deepClone(a);
    assert(a !== a2);
    assert(a.child !== a2.child);

})
// 测试通不过
// 而层数改成 5000 又没问题了

如何解决递归爆栈问题?

  • 就是把递归变成循环
    • 每进入一个对象，不要去复制他，先把它放到数组里，然后把它的子元素放在数组后面
    • 就是把竖着的拍平
  • 本次不实现这个功能！！！
    • 面试一般不会考到这一步，因为要把上面所有的思路改掉

如果面试问到

  • 可能会遇到爆栈
  • 解决办法是对它的结构进行一个改造，用循环的方式把它放在数组里

复制正则表达式和Date

  • 首先要去看文档，起码要知道 正则有那些属性

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 it("可以复制正则表达式",()=>{
    const a = new RegExp("/hi\d+/","gi");
    a.xxx = { yyy: { zzz: 1 } }
    const a2 = deepClone(a);
    assert(a.source === a2.source);
    assert(a.flags === a2.flags);
    assert(a !== a2);
    assert(a.xxx.yyy.zzz === a2.xxx.yyy.zzz);
    assert(a.xxx.yyy !== a2.xxx.yyy);
    assert(a.xxx !== a2.xxx);
})

it("可以复制日期",()=>{
    const a = new Date();
    a.xxx = { yyy: { zzz: 1 } }
    const a2 = deepClone(a);
    assert(a.source === a2.source);
    assert(a !== a2);
    assert(a.getTime() === a2.getTime());
    assert(a.xxx.yyy.zzz === a2.xxx.yyy.zzz);
    assert(a.xxx.yyy !== a2.xxx.yyy);
    assert(a.xxx !== a2.xxx);
})

src/index.js

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
let cache = [];
function deepClone(source){
    if(source instanceof Object){
        let cacheDist = findCache(source)
        if(cacheDist){
            // console.log("有缓存")
            return cacheDist;
        }else{
            // console.log("没缓存")
            let dist;
            if(source instanceof Array){
                dist = new Array();
            } else if(source instanceof Function){
                dist = function(){
                    return source.apply(this,arguments);
                }
            
            } else if(source instanceof RegExp){
                dist = new RegExp(source.source,source.flags);
            } else if(source instanceof Date){
                dist = new Date(source);
            } else {
                dist = new Object();
            }
            // 数据源 和 副本 都存入缓存 ，注意一定要 在 dist创建成功之后就把它 存入，防止重复的生成
            cache.push([source,dist])
            for(let key in source){
                dist[key] = deepClone(source[key]);
            }
            return dist;
        }
    }
    return source;
}

function findCache(source){
    for(let i=0;i<cache.length;i++){
        if(cache[i][0] === source){
            return cache[i][1];
        }
    }
    return undefined
}

module.exports = deepClone;

是否拷贝原型属性？

1
2
3
4
var a = {name:'hi'}

var a2 = Object.create({say:function(){}})
// a2的原型上有个 say函数，如果深拷贝需要复制这个 say吗？
  • 一般来说不拷贝，因为如果拷贝这个对象内存占用就太大了
    • 因为一旦你拷贝这一层，那它的原型链的所有原型都要拷贝，这个原型上的每个函数也有原型那岂不是都要拷贝
    • 所以你开了一个头，那整个 JS对象身上的东西都要拷贝，这样占用的内存就太大了

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
it("自动跳过原型属性",()=>{
    const a = Object.create({name:"a"})
    a.xxx = { yyy: { zzz: 1 } }
    const a2 = deepClone(a);
    assert(a !== a2);
    assert.isFalse("name" in a2);
    assert(a.xxx.yyy.zzz === a2.xxx.yyy.zzz);
    assert(a.xxx.yyy !== a2.xxx.yyy);
    assert(a.xxx !== a2.xxx);
})

// 测试没有通过，因为你用的是 for in
// 需要加一个判断
// if(source.hasOwnProperty(key)){ ... }

尽量少用for in 复制属性

代码仓库