UNPKG

47.1 kBJavaScriptView Raw
1"use strict";
2var __awaiter = (this && this.__awaiter) || function (thisArg, _arguments, P, generator) {
3 function adopt(value) { return value instanceof P ? value : new P(function (resolve) { resolve(value); }); }
4 return new (P || (P = Promise))(function (resolve, reject) {
5 function fulfilled(value) { try { step(generator.next(value)); } catch (e) { reject(e); } }
6 function rejected(value) { try { step(generator["throw"](value)); } catch (e) { reject(e); } }
7 function step(result) { result.done ? resolve(result.value) : adopt(result.value).then(fulfilled, rejected); }
8 step((generator = generator.apply(thisArg, _arguments || [])).next());
9 });
10};
11var __generator = (this && this.__generator) || function (thisArg, body) {
12 var _ = { label: 0, sent: function() { if (t[0] & 1) throw t[1]; return t[1]; }, trys: [], ops: [] }, f, y, t, g;
13 return g = { next: verb(0), "throw": verb(1), "return": verb(2) }, typeof Symbol === "function" && (g[Symbol.iterator] = function() { return this; }), g;
14 function verb(n) { return function (v) { return step([n, v]); }; }
15 function step(op) {
16 if (f) throw new TypeError("Generator is already executing.");
17 while (_) try {
18 if (f = 1, y && (t = op[0] & 2 ? y["return"] : op[0] ? y["throw"] || ((t = y["return"]) && t.call(y), 0) : y.next) && !(t = t.call(y, op[1])).done) return t;
19 if (y = 0, t) op = [op[0] & 2, t.value];
20 switch (op[0]) {
21 case 0: case 1: t = op; break;
22 case 4: _.label++; return { value: op[1], done: false };
23 case 5: _.label++; y = op[1]; op = [0]; continue;
24 case 7: op = _.ops.pop(); _.trys.pop(); continue;
25 default:
26 if (!(t = _.trys, t = t.length > 0 && t[t.length - 1]) && (op[0] === 6 || op[0] === 2)) { _ = 0; continue; }
27 if (op[0] === 3 && (!t || (op[1] > t[0] && op[1] < t[3]))) { _.label = op[1]; break; }
28 if (op[0] === 6 && _.label < t[1]) { _.label = t[1]; t = op; break; }
29 if (t && _.label < t[2]) { _.label = t[2]; _.ops.push(op); break; }
30 if (t[2]) _.ops.pop();
31 _.trys.pop(); continue;
32 }
33 op = body.call(thisArg, _);
34 } catch (e) { op = [6, e]; y = 0; } finally { f = t = 0; }
35 if (op[0] & 5) throw op[1]; return { value: op[0] ? op[1] : void 0, done: true };
36 }
37};
38var __values = (this && this.__values) || function(o) {
39 var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0;
40 if (m) return m.call(o);
41 if (o && typeof o.length === "number") return {
42 next: function () {
43 if (o && i >= o.length) o = void 0;
44 return { value: o && o[i++], done: !o };
45 }
46 };
47 throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
48};
49var __importDefault = (this && this.__importDefault) || function (mod) {
50 return (mod && mod.__esModule) ? mod : { "default": mod };
51};
52Object.defineProperty(exports, "__esModule", { value: true });
53exports.Trie = void 0;
54var semaphore_async_await_1 = __importDefault(require("semaphore-async-await"));
55var ethereumjs_util_1 = require("ethereumjs-util");
56var db_1 = require("./db");
57var readStream_1 = require("./readStream");
58var nibbles_1 = require("./util/nibbles");
59var walkController_1 = require("./util/walkController");
60var trieNode_1 = require("./trieNode");
61var assert = require('assert');
62/**
63 * The basic trie interface, use with `import { BaseTrie as Trie } from 'merkle-patricia-tree'`.
64 * In Ethereum applications stick with the {@link SecureTrie} overlay.
65 * The API for the base and the secure interface are about the same.
66 */
67var Trie = /** @class */ (function () {
68 /**
69 * test
70 * @param db - A [levelup](https://github.com/Level/levelup) instance. By default (if the db is `null` or
71 * left undefined) creates an in-memory [memdown](https://github.com/Level/memdown) instance.
72 * @param root - A `Buffer` for the root of a previously stored trie
73 * @param deleteFromDB - Delete nodes from DB on delete operations (disallows switching to an older state root) (default: `false`)
74 */
75 function Trie(db, root, deleteFromDB) {
76 if (deleteFromDB === void 0) { deleteFromDB = false; }
77 this.EMPTY_TRIE_ROOT = ethereumjs_util_1.KECCAK256_RLP;
78 this.lock = new semaphore_async_await_1.default(1);
79 this.db = db ? new db_1.DB(db) : new db_1.DB();
80 this._root = this.EMPTY_TRIE_ROOT;
81 this._deleteFromDB = deleteFromDB;
82 if (root) {
83 this.root = root;
84 }
85 }
86 Object.defineProperty(Trie.prototype, "root", {
87 /**
88 * Gets the current root of the `trie`
89 */
90 get: function () {
91 return this._root;
92 },
93 /**
94 * Sets the current root of the `trie`
95 */
96 set: function (value) {
97 if (!value) {
98 value = this.EMPTY_TRIE_ROOT;
99 }
100 assert(value.length === 32, 'Invalid root length. Roots are 32 bytes');
101 this._root = value;
102 },
103 enumerable: false,
104 configurable: true
105 });
106 /**
107 * This method is deprecated.
108 * Please use {@link Trie.root} instead.
109 *
110 * @param value
111 * @deprecated
112 */
113 Trie.prototype.setRoot = function (value) {
114 this.root = value !== null && value !== void 0 ? value : this.EMPTY_TRIE_ROOT;
115 };
116 /**
117 * Checks if a given root exists.
118 */
119 Trie.prototype.checkRoot = function (root) {
120 return __awaiter(this, void 0, void 0, function () {
121 var value, error_1;
122 return __generator(this, function (_a) {
123 switch (_a.label) {
124 case 0:
125 _a.trys.push([0, 2, , 3]);
126 return [4 /*yield*/, this._lookupNode(root)];
127 case 1:
128 value = _a.sent();
129 return [2 /*return*/, value !== null];
130 case 2:
131 error_1 = _a.sent();
132 if (error_1.message == 'Missing node in DB') {
133 return [2 /*return*/, false];
134 }
135 else {
136 throw error_1;
137 }
138 return [3 /*break*/, 3];
139 case 3: return [2 /*return*/];
140 }
141 });
142 });
143 };
144 Object.defineProperty(Trie.prototype, "isCheckpoint", {
145 /**
146 * BaseTrie has no checkpointing so return false
147 */
148 get: function () {
149 return false;
150 },
151 enumerable: false,
152 configurable: true
153 });
154 /**
155 * Gets a value given a `key`
156 * @param key - the key to search for
157 * @param throwIfMissing - if true, throws if any nodes are missing. Used for verifying proofs. (default: false)
158 * @returns A Promise that resolves to `Buffer` if a value was found or `null` if no value was found.
159 */
160 Trie.prototype.get = function (key, throwIfMissing) {
161 if (throwIfMissing === void 0) { throwIfMissing = false; }
162 return __awaiter(this, void 0, void 0, function () {
163 var _a, node, remaining, value;
164 return __generator(this, function (_b) {
165 switch (_b.label) {
166 case 0: return [4 /*yield*/, this.findPath(key, throwIfMissing)];
167 case 1:
168 _a = _b.sent(), node = _a.node, remaining = _a.remaining;
169 value = null;
170 if (node && remaining.length === 0) {
171 value = node.value;
172 }
173 return [2 /*return*/, value];
174 }
175 });
176 });
177 };
178 /**
179 * Stores a given `value` at the given `key` or do a delete if `value` is empty
180 * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
181 * @param key
182 * @param value
183 * @returns A Promise that resolves once value is stored.
184 */
185 Trie.prototype.put = function (key, value) {
186 return __awaiter(this, void 0, void 0, function () {
187 var _a, remaining, stack;
188 return __generator(this, function (_b) {
189 switch (_b.label) {
190 case 0:
191 if (!(!value || value.toString() === '')) return [3 /*break*/, 2];
192 return [4 /*yield*/, this.del(key)];
193 case 1: return [2 /*return*/, _b.sent()];
194 case 2: return [4 /*yield*/, this.lock.wait()];
195 case 3:
196 _b.sent();
197 if (!this.root.equals(ethereumjs_util_1.KECCAK256_RLP)) return [3 /*break*/, 5];
198 // If no root, initialize this trie
199 return [4 /*yield*/, this._createInitialNode(key, value)];
200 case 4:
201 // If no root, initialize this trie
202 _b.sent();
203 return [3 /*break*/, 8];
204 case 5: return [4 /*yield*/, this.findPath(key)
205 // then update
206 ];
207 case 6:
208 _a = _b.sent(), remaining = _a.remaining, stack = _a.stack;
209 // then update
210 return [4 /*yield*/, this._updateNode(key, value, remaining, stack)];
211 case 7:
212 // then update
213 _b.sent();
214 _b.label = 8;
215 case 8:
216 this.lock.signal();
217 return [2 /*return*/];
218 }
219 });
220 });
221 };
222 /**
223 * Deletes a value given a `key` from the trie
224 * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
225 * @param key
226 * @returns A Promise that resolves once value is deleted.
227 */
228 Trie.prototype.del = function (key) {
229 return __awaiter(this, void 0, void 0, function () {
230 var _a, node, stack;
231 return __generator(this, function (_b) {
232 switch (_b.label) {
233 case 0: return [4 /*yield*/, this.lock.wait()];
234 case 1:
235 _b.sent();
236 return [4 /*yield*/, this.findPath(key)];
237 case 2:
238 _a = _b.sent(), node = _a.node, stack = _a.stack;
239 if (!node) return [3 /*break*/, 4];
240 return [4 /*yield*/, this._deleteNode(key, stack)];
241 case 3:
242 _b.sent();
243 _b.label = 4;
244 case 4:
245 this.lock.signal();
246 return [2 /*return*/];
247 }
248 });
249 });
250 };
251 /**
252 * Tries to find a path to the node for the given key.
253 * It returns a `stack` of nodes to the closest node.
254 * @param key - the search key
255 * @param throwIfMissing - if true, throws if any nodes are missing. Used for verifying proofs. (default: false)
256 */
257 Trie.prototype.findPath = function (key, throwIfMissing) {
258 if (throwIfMissing === void 0) { throwIfMissing = false; }
259 return __awaiter(this, void 0, void 0, function () {
260 var _this = this;
261 return __generator(this, function (_a) {
262 // eslint-disable-next-line no-async-promise-executor
263 return [2 /*return*/, new Promise(function (resolve, reject) { return __awaiter(_this, void 0, void 0, function () {
264 var stack, targetKey, onFound, error_2;
265 var _this = this;
266 return __generator(this, function (_a) {
267 switch (_a.label) {
268 case 0:
269 stack = [];
270 targetKey = (0, nibbles_1.bufferToNibbles)(key);
271 onFound = function (nodeRef, node, keyProgress, walkController) { return __awaiter(_this, void 0, void 0, function () {
272 var keyRemainder, branchIndex, branchNode, matchingLen;
273 return __generator(this, function (_a) {
274 if (node === null) {
275 return [2 /*return*/, reject(new Error('Path not found'))];
276 }
277 keyRemainder = targetKey.slice((0, nibbles_1.matchingNibbleLength)(keyProgress, targetKey));
278 stack.push(node);
279 if (node instanceof trieNode_1.BranchNode) {
280 if (keyRemainder.length === 0) {
281 // we exhausted the key without finding a node
282 resolve({ node: node, remaining: [], stack: stack });
283 }
284 else {
285 branchIndex = keyRemainder[0];
286 branchNode = node.getBranch(branchIndex);
287 if (!branchNode) {
288 // there are no more nodes to find and we didn't find the key
289 resolve({ node: null, remaining: keyRemainder, stack: stack });
290 }
291 else {
292 // node found, continuing search
293 // this can be optimized as this calls getBranch again.
294 walkController.onlyBranchIndex(node, keyProgress, branchIndex);
295 }
296 }
297 }
298 else if (node instanceof trieNode_1.LeafNode) {
299 if ((0, nibbles_1.doKeysMatch)(keyRemainder, node.key)) {
300 // keys match, return node with empty key
301 resolve({ node: node, remaining: [], stack: stack });
302 }
303 else {
304 // reached leaf but keys dont match
305 resolve({ node: null, remaining: keyRemainder, stack: stack });
306 }
307 }
308 else if (node instanceof trieNode_1.ExtensionNode) {
309 matchingLen = (0, nibbles_1.matchingNibbleLength)(keyRemainder, node.key);
310 if (matchingLen !== node.key.length) {
311 // keys don't match, fail
312 resolve({ node: null, remaining: keyRemainder, stack: stack });
313 }
314 else {
315 // keys match, continue search
316 walkController.allChildren(node, keyProgress);
317 }
318 }
319 return [2 /*return*/];
320 });
321 }); };
322 _a.label = 1;
323 case 1:
324 _a.trys.push([1, 3, , 4]);
325 return [4 /*yield*/, this.walkTrie(this.root, onFound)];
326 case 2:
327 _a.sent();
328 return [3 /*break*/, 4];
329 case 3:
330 error_2 = _a.sent();
331 if (error_2.message == 'Missing node in DB' && !throwIfMissing) {
332 // pass
333 }
334 else {
335 reject(error_2);
336 }
337 return [3 /*break*/, 4];
338 case 4:
339 // Resolve if _walkTrie finishes without finding any nodes
340 resolve({ node: null, remaining: [], stack: stack });
341 return [2 /*return*/];
342 }
343 });
344 }); })];
345 });
346 });
347 };
348 /**
349 * Walks a trie until finished.
350 * @param root
351 * @param onFound - callback to call when a node is found. This schedules new tasks. If no tasks are available, the Promise resolves.
352 * @returns Resolves when finished walking trie.
353 */
354 Trie.prototype.walkTrie = function (root, onFound) {
355 return __awaiter(this, void 0, void 0, function () {
356 return __generator(this, function (_a) {
357 switch (_a.label) {
358 case 0: return [4 /*yield*/, walkController_1.WalkController.newWalk(onFound, this, root)];
359 case 1:
360 _a.sent();
361 return [2 /*return*/];
362 }
363 });
364 });
365 };
366 /**
367 * @hidden
368 * Backwards compatibility
369 * @param root -
370 * @param onFound -
371 */
372 Trie.prototype._walkTrie = function (root, onFound) {
373 return __awaiter(this, void 0, void 0, function () {
374 return __generator(this, function (_a) {
375 switch (_a.label) {
376 case 0: return [4 /*yield*/, this.walkTrie(root, onFound)];
377 case 1:
378 _a.sent();
379 return [2 /*return*/];
380 }
381 });
382 });
383 };
384 /**
385 * Creates the initial node from an empty tree.
386 * @private
387 */
388 Trie.prototype._createInitialNode = function (key, value) {
389 return __awaiter(this, void 0, void 0, function () {
390 var newNode;
391 return __generator(this, function (_a) {
392 switch (_a.label) {
393 case 0:
394 newNode = new trieNode_1.LeafNode((0, nibbles_1.bufferToNibbles)(key), value);
395 this.root = newNode.hash();
396 return [4 /*yield*/, this.db.put(this.root, newNode.serialize())];
397 case 1:
398 _a.sent();
399 return [2 /*return*/];
400 }
401 });
402 });
403 };
404 /**
405 * Retrieves a node from db by hash.
406 */
407 Trie.prototype.lookupNode = function (node) {
408 return __awaiter(this, void 0, void 0, function () {
409 var value, foundNode;
410 return __generator(this, function (_a) {
411 switch (_a.label) {
412 case 0:
413 if ((0, trieNode_1.isRawNode)(node)) {
414 return [2 /*return*/, (0, trieNode_1.decodeRawNode)(node)];
415 }
416 value = null;
417 foundNode = null;
418 return [4 /*yield*/, this.db.get(node)];
419 case 1:
420 value = _a.sent();
421 if (value) {
422 foundNode = (0, trieNode_1.decodeNode)(value);
423 }
424 else {
425 // Dev note: this error message text is used for error checking in `checkRoot`, `verifyProof`, and `findPath`
426 throw new Error('Missing node in DB');
427 }
428 return [2 /*return*/, foundNode];
429 }
430 });
431 });
432 };
433 /**
434 * @hidden
435 * Backwards compatibility
436 * @param node The node hash to lookup from the DB
437 */
438 Trie.prototype._lookupNode = function (node) {
439 return __awaiter(this, void 0, void 0, function () {
440 return __generator(this, function (_a) {
441 return [2 /*return*/, this.lookupNode(node)];
442 });
443 });
444 };
445 /**
446 * Updates a node.
447 * @private
448 * @param key
449 * @param value
450 * @param keyRemainder
451 * @param stack
452 */
453 Trie.prototype._updateNode = function (k, value, keyRemainder, stack) {
454 return __awaiter(this, void 0, void 0, function () {
455 var toSave, lastNode, key, matchLeaf, l, i, n, newLeaf, lastKey, matchingLength, newBranchNode, newKey, newExtNode, branchKey, formattedNode, newLeafNode;
456 return __generator(this, function (_a) {
457 switch (_a.label) {
458 case 0:
459 toSave = [];
460 lastNode = stack.pop();
461 if (!lastNode) {
462 throw new Error('Stack underflow');
463 }
464 key = (0, nibbles_1.bufferToNibbles)(k);
465 matchLeaf = false;
466 if (lastNode instanceof trieNode_1.LeafNode) {
467 l = 0;
468 for (i = 0; i < stack.length; i++) {
469 n = stack[i];
470 if (n instanceof trieNode_1.BranchNode) {
471 l++;
472 }
473 else {
474 l += n.key.length;
475 }
476 }
477 if ((0, nibbles_1.matchingNibbleLength)(lastNode.key, key.slice(l)) === lastNode.key.length &&
478 keyRemainder.length === 0) {
479 matchLeaf = true;
480 }
481 }
482 if (matchLeaf) {
483 // just updating a found value
484 lastNode.value = value;
485 stack.push(lastNode);
486 }
487 else if (lastNode instanceof trieNode_1.BranchNode) {
488 stack.push(lastNode);
489 if (keyRemainder.length !== 0) {
490 // add an extension to a branch node
491 keyRemainder.shift();
492 newLeaf = new trieNode_1.LeafNode(keyRemainder, value);
493 stack.push(newLeaf);
494 }
495 else {
496 lastNode.value = value;
497 }
498 }
499 else {
500 lastKey = lastNode.key;
501 matchingLength = (0, nibbles_1.matchingNibbleLength)(lastKey, keyRemainder);
502 newBranchNode = new trieNode_1.BranchNode();
503 // create a new extension node
504 if (matchingLength !== 0) {
505 newKey = lastNode.key.slice(0, matchingLength);
506 newExtNode = new trieNode_1.ExtensionNode(newKey, value);
507 stack.push(newExtNode);
508 lastKey.splice(0, matchingLength);
509 keyRemainder.splice(0, matchingLength);
510 }
511 stack.push(newBranchNode);
512 if (lastKey.length !== 0) {
513 branchKey = lastKey.shift();
514 if (lastKey.length !== 0 || lastNode instanceof trieNode_1.LeafNode) {
515 // shrinking extension or leaf
516 lastNode.key = lastKey;
517 formattedNode = this._formatNode(lastNode, false, toSave);
518 newBranchNode.setBranch(branchKey, formattedNode);
519 }
520 else {
521 // remove extension or attaching
522 this._formatNode(lastNode, false, toSave, true);
523 newBranchNode.setBranch(branchKey, lastNode.value);
524 }
525 }
526 else {
527 newBranchNode.value = lastNode.value;
528 }
529 if (keyRemainder.length !== 0) {
530 keyRemainder.shift();
531 newLeafNode = new trieNode_1.LeafNode(keyRemainder, value);
532 stack.push(newLeafNode);
533 }
534 else {
535 newBranchNode.value = value;
536 }
537 }
538 return [4 /*yield*/, this._saveStack(key, stack, toSave)];
539 case 1:
540 _a.sent();
541 return [2 /*return*/];
542 }
543 });
544 });
545 };
546 /**
547 * Deletes a node from the trie.
548 * @private
549 */
550 Trie.prototype._deleteNode = function (k, stack) {
551 return __awaiter(this, void 0, void 0, function () {
552 var processBranchNode, lastNode, parentNode, opStack, key, lastNodeKey, branchNodes, branchNode, branchNodeKey, foundNode;
553 return __generator(this, function (_a) {
554 switch (_a.label) {
555 case 0:
556 processBranchNode = function (key, branchKey, branchNode, parentNode, stack) {
557 // branchNode is the node ON the branch node not THE branch node
558 if (!parentNode || parentNode instanceof trieNode_1.BranchNode) {
559 // branch->?
560 if (parentNode) {
561 stack.push(parentNode);
562 }
563 if (branchNode instanceof trieNode_1.BranchNode) {
564 // create an extension node
565 // branch->extension->branch
566 // @ts-ignore
567 var extensionNode = new trieNode_1.ExtensionNode([branchKey], null);
568 stack.push(extensionNode);
569 key.push(branchKey);
570 }
571 else {
572 var branchNodeKey = branchNode.key;
573 // branch key is an extension or a leaf
574 // branch->(leaf or extension)
575 branchNodeKey.unshift(branchKey);
576 branchNode.key = branchNodeKey.slice(0);
577 key = key.concat(branchNodeKey);
578 }
579 stack.push(branchNode);
580 }
581 else {
582 // parent is an extension
583 var parentKey = parentNode.key;
584 if (branchNode instanceof trieNode_1.BranchNode) {
585 // ext->branch
586 parentKey.push(branchKey);
587 key.push(branchKey);
588 parentNode.key = parentKey;
589 stack.push(parentNode);
590 }
591 else {
592 var branchNodeKey = branchNode.key;
593 // branch node is an leaf or extension and parent node is an exstention
594 // add two keys together
595 // dont push the parent node
596 branchNodeKey.unshift(branchKey);
597 key = key.concat(branchNodeKey);
598 parentKey = parentKey.concat(branchNodeKey);
599 branchNode.key = parentKey;
600 }
601 stack.push(branchNode);
602 }
603 return key;
604 };
605 lastNode = stack.pop();
606 assert(lastNode);
607 parentNode = stack.pop();
608 opStack = [];
609 key = (0, nibbles_1.bufferToNibbles)(k);
610 if (!parentNode) {
611 // the root here has to be a leaf.
612 this.root = this.EMPTY_TRIE_ROOT;
613 return [2 /*return*/];
614 }
615 if (lastNode instanceof trieNode_1.BranchNode) {
616 lastNode.value = null;
617 }
618 else {
619 // the lastNode has to be a leaf if it's not a branch.
620 // And a leaf's parent, if it has one, must be a branch.
621 if (!(parentNode instanceof trieNode_1.BranchNode)) {
622 throw new Error('Expected branch node');
623 }
624 lastNodeKey = lastNode.key;
625 key.splice(key.length - lastNodeKey.length);
626 // delete the value
627 this._formatNode(lastNode, false, opStack, true);
628 parentNode.setBranch(key.pop(), null);
629 lastNode = parentNode;
630 parentNode = stack.pop();
631 }
632 branchNodes = lastNode.getChildren();
633 if (!(branchNodes.length === 1)) return [3 /*break*/, 4];
634 branchNode = branchNodes[0][1];
635 branchNodeKey = branchNodes[0][0];
636 return [4 /*yield*/, this._lookupNode(branchNode)];
637 case 1:
638 foundNode = _a.sent();
639 if (!foundNode) return [3 /*break*/, 3];
640 key = processBranchNode(key, branchNodeKey, foundNode, parentNode, stack);
641 return [4 /*yield*/, this._saveStack(key, stack, opStack)];
642 case 2:
643 _a.sent();
644 _a.label = 3;
645 case 3: return [3 /*break*/, 6];
646 case 4:
647 // simple removing a leaf and recaluclation the stack
648 if (parentNode) {
649 stack.push(parentNode);
650 }
651 stack.push(lastNode);
652 return [4 /*yield*/, this._saveStack(key, stack, opStack)];
653 case 5:
654 _a.sent();
655 _a.label = 6;
656 case 6: return [2 /*return*/];
657 }
658 });
659 });
660 };
661 /**
662 * Saves a stack of nodes to the database.
663 * @private
664 * @param key - the key. Should follow the stack
665 * @param stack - a stack of nodes to the value given by the key
666 * @param opStack - a stack of levelup operations to commit at the end of this funciton
667 */
668 Trie.prototype._saveStack = function (key, stack, opStack) {
669 return __awaiter(this, void 0, void 0, function () {
670 var lastRoot, node, branchKey;
671 return __generator(this, function (_a) {
672 switch (_a.label) {
673 case 0:
674 // update nodes
675 while (stack.length) {
676 node = stack.pop();
677 if (node instanceof trieNode_1.LeafNode) {
678 key.splice(key.length - node.key.length);
679 }
680 else if (node instanceof trieNode_1.ExtensionNode) {
681 key.splice(key.length - node.key.length);
682 if (lastRoot) {
683 node.value = lastRoot;
684 }
685 }
686 else if (node instanceof trieNode_1.BranchNode) {
687 if (lastRoot) {
688 branchKey = key.pop();
689 node.setBranch(branchKey, lastRoot);
690 }
691 }
692 lastRoot = this._formatNode(node, stack.length === 0, opStack);
693 }
694 if (lastRoot) {
695 this.root = lastRoot;
696 }
697 return [4 /*yield*/, this.db.batch(opStack)];
698 case 1:
699 _a.sent();
700 return [2 /*return*/];
701 }
702 });
703 });
704 };
705 /**
706 * Formats node to be saved by `levelup.batch`.
707 * @private
708 * @param node - the node to format.
709 * @param topLevel - if the node is at the top level.
710 * @param opStack - the opStack to push the node's data.
711 * @param remove - whether to remove the node (only used for CheckpointTrie).
712 * @returns The node's hash used as the key or the rawNode.
713 */
714 Trie.prototype._formatNode = function (node, topLevel, opStack, remove) {
715 if (remove === void 0) { remove = false; }
716 var rlpNode = node.serialize();
717 if (rlpNode.length >= 32 || topLevel) {
718 // Do not use TrieNode.hash() here otherwise serialize()
719 // is applied twice (performance)
720 var hashRoot = (0, ethereumjs_util_1.keccak)(rlpNode);
721 if (remove) {
722 if (this._deleteFromDB) {
723 opStack.push({
724 type: 'del',
725 key: hashRoot,
726 });
727 }
728 }
729 else {
730 opStack.push({
731 type: 'put',
732 key: hashRoot,
733 value: rlpNode,
734 });
735 }
736 return hashRoot;
737 }
738 return node.raw();
739 };
740 /**
741 * The given hash of operations (key additions or deletions) are executed on the trie
742 * (delete operations are only executed on DB with `deleteFromDB` set to `true`)
743 * @example
744 * const ops = [
745 * { type: 'del', key: Buffer.from('father') }
746 * , { type: 'put', key: Buffer.from('name'), value: Buffer.from('Yuri Irsenovich Kim') }
747 * , { type: 'put', key: Buffer.from('dob'), value: Buffer.from('16 February 1941') }
748 * , { type: 'put', key: Buffer.from('spouse'), value: Buffer.from('Kim Young-sook') }
749 * , { type: 'put', key: Buffer.from('occupation'), value: Buffer.from('Clown') }
750 * ]
751 * await trie.batch(ops)
752 * @param ops
753 */
754 Trie.prototype.batch = function (ops) {
755 return __awaiter(this, void 0, void 0, function () {
756 var ops_1, ops_1_1, op, e_1_1;
757 var e_1, _a;
758 return __generator(this, function (_b) {
759 switch (_b.label) {
760 case 0:
761 _b.trys.push([0, 7, 8, 9]);
762 ops_1 = __values(ops), ops_1_1 = ops_1.next();
763 _b.label = 1;
764 case 1:
765 if (!!ops_1_1.done) return [3 /*break*/, 6];
766 op = ops_1_1.value;
767 if (!(op.type === 'put')) return [3 /*break*/, 3];
768 if (!op.value) {
769 throw new Error('Invalid batch db operation');
770 }
771 return [4 /*yield*/, this.put(op.key, op.value)];
772 case 2:
773 _b.sent();
774 return [3 /*break*/, 5];
775 case 3:
776 if (!(op.type === 'del')) return [3 /*break*/, 5];
777 return [4 /*yield*/, this.del(op.key)];
778 case 4:
779 _b.sent();
780 _b.label = 5;
781 case 5:
782 ops_1_1 = ops_1.next();
783 return [3 /*break*/, 1];
784 case 6: return [3 /*break*/, 9];
785 case 7:
786 e_1_1 = _b.sent();
787 e_1 = { error: e_1_1 };
788 return [3 /*break*/, 9];
789 case 8:
790 try {
791 if (ops_1_1 && !ops_1_1.done && (_a = ops_1.return)) _a.call(ops_1);
792 }
793 finally { if (e_1) throw e_1.error; }
794 return [7 /*endfinally*/];
795 case 9: return [2 /*return*/];
796 }
797 });
798 });
799 };
800 /**
801 * Saves the nodes from a proof into the trie. If no trie is provided a new one wil be instantiated.
802 * @param proof
803 * @param trie
804 */
805 Trie.fromProof = function (proof, trie) {
806 return __awaiter(this, void 0, void 0, function () {
807 var opStack;
808 return __generator(this, function (_a) {
809 switch (_a.label) {
810 case 0:
811 opStack = proof.map(function (nodeValue) {
812 return {
813 type: 'put',
814 key: (0, ethereumjs_util_1.keccak)(nodeValue),
815 value: nodeValue,
816 };
817 });
818 if (!trie) {
819 trie = new Trie();
820 if (opStack[0]) {
821 trie.root = opStack[0].key;
822 }
823 }
824 return [4 /*yield*/, trie.db.batch(opStack)];
825 case 1:
826 _a.sent();
827 return [2 /*return*/, trie];
828 }
829 });
830 });
831 };
832 /**
833 * prove has been renamed to {@link Trie.createProof}.
834 * @deprecated
835 * @param trie
836 * @param key
837 */
838 Trie.prove = function (trie, key) {
839 return __awaiter(this, void 0, void 0, function () {
840 return __generator(this, function (_a) {
841 return [2 /*return*/, this.createProof(trie, key)];
842 });
843 });
844 };
845 /**
846 * Creates a proof from a trie and key that can be verified using {@link Trie.verifyProof}.
847 * @param trie
848 * @param key
849 */
850 Trie.createProof = function (trie, key) {
851 return __awaiter(this, void 0, void 0, function () {
852 var stack, p;
853 return __generator(this, function (_a) {
854 switch (_a.label) {
855 case 0: return [4 /*yield*/, trie.findPath(key)];
856 case 1:
857 stack = (_a.sent()).stack;
858 p = stack.map(function (stackElem) {
859 return stackElem.serialize();
860 });
861 return [2 /*return*/, p];
862 }
863 });
864 });
865 };
866 /**
867 * Verifies a proof.
868 * @param rootHash
869 * @param key
870 * @param proof
871 * @throws If proof is found to be invalid.
872 * @returns The value from the key, or null if valid proof of non-existence.
873 */
874 Trie.verifyProof = function (rootHash, key, proof) {
875 return __awaiter(this, void 0, void 0, function () {
876 var proofTrie, e_2, value, err_1;
877 return __generator(this, function (_a) {
878 switch (_a.label) {
879 case 0:
880 proofTrie = new Trie(null, rootHash);
881 _a.label = 1;
882 case 1:
883 _a.trys.push([1, 3, , 4]);
884 return [4 /*yield*/, Trie.fromProof(proof, proofTrie)];
885 case 2:
886 proofTrie = _a.sent();
887 return [3 /*break*/, 4];
888 case 3:
889 e_2 = _a.sent();
890 throw new Error('Invalid proof nodes given');
891 case 4:
892 _a.trys.push([4, 6, , 7]);
893 return [4 /*yield*/, proofTrie.get(key, true)];
894 case 5:
895 value = _a.sent();
896 return [2 /*return*/, value];
897 case 6:
898 err_1 = _a.sent();
899 if (err_1.message == 'Missing node in DB') {
900 throw new Error('Invalid proof provided');
901 }
902 else {
903 throw err_1;
904 }
905 return [3 /*break*/, 7];
906 case 7: return [2 /*return*/];
907 }
908 });
909 });
910 };
911 /**
912 * The `data` event is given an `Object` that has two properties; the `key` and the `value`. Both should be Buffers.
913 * @return Returns a [stream](https://nodejs.org/dist/latest-v12.x/docs/api/stream.html#stream_class_stream_readable) of the contents of the `trie`
914 */
915 Trie.prototype.createReadStream = function () {
916 return new readStream_1.TrieReadStream(this);
917 };
918 /**
919 * Creates a new trie backed by the same db.
920 */
921 Trie.prototype.copy = function () {
922 var db = this.db.copy();
923 return new Trie(db._leveldb, this.root);
924 };
925 /**
926 * Finds all nodes that are stored directly in the db
927 * (some nodes are stored raw inside other nodes)
928 * called by {@link ScratchReadStream}
929 * @private
930 */
931 Trie.prototype._findDbNodes = function (onFound) {
932 return __awaiter(this, void 0, void 0, function () {
933 var outerOnFound;
934 var _this = this;
935 return __generator(this, function (_a) {
936 switch (_a.label) {
937 case 0:
938 outerOnFound = function (nodeRef, node, key, walkController) { return __awaiter(_this, void 0, void 0, function () {
939 return __generator(this, function (_a) {
940 if ((0, trieNode_1.isRawNode)(nodeRef)) {
941 if (node !== null) {
942 walkController.allChildren(node, key);
943 }
944 }
945 else {
946 onFound(nodeRef, node, key, walkController);
947 }
948 return [2 /*return*/];
949 });
950 }); };
951 return [4 /*yield*/, this.walkTrie(this.root, outerOnFound)];
952 case 1:
953 _a.sent();
954 return [2 /*return*/];
955 }
956 });
957 });
958 };
959 /**
960 * Finds all nodes that store k,v values
961 * called by {@link TrieReadStream}
962 * @private
963 */
964 Trie.prototype._findValueNodes = function (onFound) {
965 return __awaiter(this, void 0, void 0, function () {
966 var outerOnFound;
967 var _this = this;
968 return __generator(this, function (_a) {
969 switch (_a.label) {
970 case 0:
971 outerOnFound = function (nodeRef, node, key, walkController) { return __awaiter(_this, void 0, void 0, function () {
972 var fullKey;
973 return __generator(this, function (_a) {
974 fullKey = key;
975 if (node instanceof trieNode_1.LeafNode) {
976 fullKey = key.concat(node.key);
977 // found leaf node!
978 onFound(nodeRef, node, fullKey, walkController);
979 }
980 else if (node instanceof trieNode_1.BranchNode && node.value) {
981 // found branch with value
982 onFound(nodeRef, node, fullKey, walkController);
983 }
984 else {
985 // keep looking for value nodes
986 if (node !== null) {
987 walkController.allChildren(node, key);
988 }
989 }
990 return [2 /*return*/];
991 });
992 }); };
993 return [4 /*yield*/, this.walkTrie(this.root, outerOnFound)];
994 case 1:
995 _a.sent();
996 return [2 /*return*/];
997 }
998 });
999 });
1000 };
1001 return Trie;
1002}());
1003exports.Trie = Trie;
1004//# sourceMappingURL=baseTrie.js.map
\No newline at end of file