1const chai = require("chai");
  2
  3const Fr = require("ffjavascript").bn128.Fr;
  4
  5const smt = require("../src/smt.js");
  6
  7const assert = chai.assert;
  8
  9describe("SMT Javascript test", function () {
 10    this.timeout(100000);
 11    before( async () => {
 12    });
 13
 14    it("Should insert 2 elements and empty them", async () => {
 15        const tree = await smt.newMemEmptyTrie();
 16        const key1 = Fr.e(111);
 17        const value1 = Fr.e(222);
 18        const key2 = Fr.e(333);
 19        const value2 = Fr.e(444);
 20
 21        await tree.insert(key1,value1);
 22        await tree.insert(key2,value2);
 23        await tree.delete(key2);
 24        await tree.delete(key1);
 25
 26        assert(Fr.isZero(tree.root));
 27    });
 28
 29    it("Should insert 3 elements in dferent order and should be the same", async () => {
 30        const keys = [Fr.e(8), Fr.e(9), Fr.e(32)];
 31        const values = [Fr.e(88), Fr.e(99), Fr.e(3232)];
 32        const tree1 = await smt.newMemEmptyTrie();
 33        const tree2 = await smt.newMemEmptyTrie();
 34        const tree3 = await smt.newMemEmptyTrie();
 35        const tree4 = await smt.newMemEmptyTrie();
 36        const tree5 = await smt.newMemEmptyTrie();
 37        const tree6 = await smt.newMemEmptyTrie();
 38
 39        await tree1.insert(keys[0],values[0]);
 40        await tree1.insert(keys[1],values[1]);
 41        await tree1.insert(keys[2],values[2]);
 42
 43        await tree2.insert(keys[0],values[0]);
 44        await tree2.insert(keys[2],values[2]);
 45        await tree2.insert(keys[1],values[1]);
 46
 47        await tree3.insert(keys[1],values[1]);
 48        await tree3.insert(keys[0],values[0]);
 49        await tree3.insert(keys[2],values[2]);
 50
 51        await tree4.insert(keys[1],values[1]);
 52        await tree4.insert(keys[2],values[2]);
 53        await tree4.insert(keys[0],values[0]);
 54
 55        await tree5.insert(keys[2],values[2]);
 56        await tree5.insert(keys[0],values[0]);
 57        await tree5.insert(keys[1],values[1]);
 58
 59        await tree6.insert(keys[2],values[2]);
 60        await tree6.insert(keys[1],values[1]);
 61        await tree6.insert(keys[0],values[0]);
 62
 63        assert(Fr.eq(tree1.root, tree2.root));
 64        assert(Fr.eq(tree2.root, tree3.root));
 65        assert(Fr.eq(tree3.root, tree4.root));
 66        assert(Fr.eq(tree4.root, tree5.root));
 67        assert(Fr.eq(tree5.root, tree6.root));
 68
 69        assert.equal(Object.keys(tree1.db.nodes).length,  Object.keys(tree2.db.nodes).length);
 70        assert.equal(Object.keys(tree2.db.nodes).length,  Object.keys(tree3.db.nodes).length);
 71        assert.equal(Object.keys(tree3.db.nodes).length,  Object.keys(tree4.db.nodes).length);
 72        assert.equal(Object.keys(tree4.db.nodes).length,  Object.keys(tree5.db.nodes).length);
 73        assert.equal(Object.keys(tree5.db.nodes).length,  Object.keys(tree6.db.nodes).length);
 74
 75        await tree1.delete(keys[0]);
 76        await tree1.delete(keys[1]);
 77        await tree2.delete(keys[1]);
 78        await tree2.delete(keys[0]);
 79        assert(Fr.eq(tree1.root, tree2.root));
 80
 81        await tree3.delete(keys[0]);
 82        await tree3.delete(keys[2]);
 83        await tree4.delete(keys[2]);
 84        await tree4.delete(keys[0]);
 85        assert(Fr.eq(tree3.root, tree4.root));
 86
 87        await tree5.delete(keys[1]);
 88        await tree5.delete(keys[2]);
 89        await tree6.delete(keys[2]);
 90        await tree6.delete(keys[1]);
 91        assert(Fr.eq(tree5.root, tree6.root));
 92
 93        await tree1.delete(keys[2]);
 94        await tree2.delete(keys[2]);
 95        await tree3.delete(keys[1]);
 96        await tree4.delete(keys[1]);
 97        await tree5.delete(keys[0]);
 98        await tree6.delete(keys[0]);
 99
100        assert(Fr.isZero(tree1.root));
101        assert(Fr.isZero(tree2.root));
102        assert(Fr.isZero(tree3.root));
103        assert(Fr.isZero(tree4.root));
104        assert(Fr.isZero(tree5.root));
105        assert(Fr.isZero(tree6.root));
106
107        assert.equal(Object.keys(tree1.db.nodes).length, 0);
108        assert.equal(Object.keys(tree2.db.nodes).length, 0);
109        assert.equal(Object.keys(tree3.db.nodes).length, 0);
110        assert.equal(Object.keys(tree4.db.nodes).length, 0);
111        assert.equal(Object.keys(tree5.db.nodes).length, 0);
112        assert.equal(Object.keys(tree6.db.nodes).length, 0);
113    });
114
115    it("Insert and remove 100 numbers randomly", async () => {
116        function perm(a) {
117            const arr = a.slice();
118            const rArr = [];
119            for (let i=0; i<arr.length; i++) {
120                let rIdx = Math.floor(Math.random() * (arr.length - i));
121                rArr.push(arr[rIdx]);
122                arr[rIdx] = arr[arr.length - i - 1];
123            }
124            return rArr;
125        }
126        const tree = await smt.newMemEmptyTrie();
127        const arr = [];
128        const N = 100;
129        for (let i=0; i<N; i++) {
130            arr.push(Fr.e(i));
131        }
132        const insArr = perm(arr);
133        for (let i=0; i<N; i++) {
134            await tree.insert(insArr[i], i);
135        }
136        const delArr = perm(insArr);
137        for (let i=0; i<N; i++) {
138            await tree.delete(delArr[i]);
139        }
140
141        assert(Fr.isZero(tree.root));
142        assert.equal(Object.keys(tree.db.nodes).length, 0);
143    });
144
145    it("Should test update", async () => {
146        const tree1 = await smt.newMemEmptyTrie();
147        const tree2 = await smt.newMemEmptyTrie();
148
149        await tree1.insert(8,88);
150        await tree1.insert(9,99,);
151        await tree1.insert(32,3232);
152
153        await tree2.insert(8,888);
154        await tree2.insert(9,999);
155        await tree2.insert(32,323232);
156
157        await tree1.update(8, 888);
158        await tree1.update(9, 999);
159        await tree1.update(32, 323232);
160
161        assert(Fr.eq(tree1.root, tree2.root));
162    });
163
164});