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