@typeberry/trie - npm Package Compare versions

Comparing version 0.0.1-9932697 to 0.0.1-0ed875f

index.js

@@ -17,2 +17,23 @@ 'use strict';
 /**
+ * @fileoverview `Opaque<Type, Token>` constructs a unique type which is a subset of Type with a
+ * specified unique token Token. It means that base type cannot be assigned to unique type by accident.
+ * Good examples of opaque types include:
+ * - JWTs or other tokens - these are special kinds of string used for authorization purposes.
+ *   If your app uses multiple types of tokens each should be a separate opaque type to avoid confusion
+ * - Specific currencies - amount of different currencies shouldn't be mixed
+ * - Bitcoin address - special kind of string
+ *
+ * `type GithubAccessToken = Opaque<string, "GithubAccessToken">;`
+ * `type USD = Opaque<number, "USD">;`
+ * `type PositiveNumber = Opaque<number, "PositiveNumber">;
+ *
+ * More: https://github.com/ts-essentials/ts-essentials/blob/master/lib/opaque/README.md
+ *
+ * Copyright (c) 2018-2019 Chris Kaczor (github.com/krzkaczor)
+ */
+function asOpaqueType(v) {
+    return v;
+}
+
+/**
  * A variable-length blob of bytes with a concise text representation.
@@ -25,5 +46,4 @@ *
     constructor(data) {
-        this.buffer = new Uint8Array([]);
         this.length = 0;
-        this.buffer = data;
+        this.raw = data;
         this.length = data.byteLength;
@@ -35,11 +55,44 @@ }
     toString() {
-        return bytesToHexString(this.buffer);
+        return bytesToHexString(this.raw);
     }
+    /** Decode contained bytes as string. */
+    asText() {
+        const decoder = new TextDecoder();
+        return decoder.decode(this.raw);
+    }
+    /** Converts current type into some opaque extension. */
+    asOpaque() {
+        return asOpaqueType(this);
+    }
+    /** Compare the sequence to another one. */
+    isEqualTo(other) {
+        if (this.length !== other.length) {
+            return false;
+        }
+        return u8ArraySameLengthEqual(this.raw, other.raw);
+    }
+    /** Create a new [`BytesBlob'] by converting given UTF-u encoded string into bytes. */
+    static blobFromString(v) {
+        const encoder = new TextEncoder();
+        return BytesBlob.blobFrom(encoder.encode(v));
+    }
     /** Create a new [`BytesBlob`] from existing [`Uint8Array`]. */
-    static fromBlob(v) {
+    static blobFrom(v) {
         return new BytesBlob(v);
     }
+    /** Create a new [`BytesBlob`] by concatenating data from multiple `Uint8Array`s. */
+    static blobFromParts(v, ...rest) {
+        const totalLength = v.length + rest.reduce((a, v) => a + v.length, 0);
+        const buffer = new Uint8Array(totalLength);
+        buffer.set(v, 0);
+        let offset = v.length;
+        for (const r of rest) {
+            buffer.set(r, offset);
+            offset += r.length;
+        }
+        return new BytesBlob(buffer);
+    }
     /** Create a new [`BytesBlob`] from an array of bytes. */
-    static fromNumbers(v) {
-        check(v.find((x) => (x & 0xff) !== x) === undefined, "BytesBlob.fromNumbers used with non-byte number array.");
+    static blobFromNumbers(v) {
+        check(v.find((x) => (x & 0xff) !== x) === undefined, "BytesBlob.blobFromNumbers used with non-byte number array.");
         const arr = new Uint8Array(v);
@@ -73,24 +126,8 @@ return new BytesBlob(arr);
  */
-class Bytes {
+class Bytes extends BytesBlob {
     constructor(raw, len) {
+        super(raw);
         check(raw.byteLength === len, `Given buffer has incorrect size ${raw.byteLength} vs expected ${len}`);
-        this.raw = raw;
         this.length = len;
     }
-    /** Return hex encoding of the sequence. */
-    toString() {
-        return bytesToHexString(this.raw);
-    }
-    /** Compare the sequence to another one. */
-    isEqualTo(other) {
-        if (this.length !== other.length) {
-            return false;
-        }
-        for (let i = 0; i < this.length; i++) {
-            if (this.raw[i] !== other.raw[i]) {
-                return false;
-            }
-        }
-        return true;
-    }
     /** Create new [`Bytes<X>`] given a backing buffer and it's length. */
@@ -100,2 +137,8 @@ static fromBlob(v, len) {
     }
+    /** Create new [`Bytes<X>`] given an array of bytes and it's length. */
+    static fromNumbers(v, len) {
+        check(v.find((x) => (x & 0xff) !== x) === undefined, "Bytes.fromNumbers used with non-byte number array.");
+        const x = new Uint8Array(v);
+        return new Bytes(x, len);
+    }
     /** Create an empty [`Bytes<X>`] of given length. */
@@ -118,3 +161,3 @@ static zero(len) {
         const blob = BytesBlob.parseBlobNoPrefix(v);
-        return new Bytes(blob.buffer, len);
+        return new Bytes(blob.raw, len);
     }
@@ -127,4 +170,9 @@ /** Parse a hex-encoded fixed-length bytes with `0x` prefix. */
         const blob = BytesBlob.parseBlob(v);
-        return new Bytes(blob.buffer, len);
+        return new Bytes(blob.raw, len);
     }
+    /** Compare the sequence to another one. */
+    isEqualTo(other) {
+        check(this.length === other.length, "Comparing incorrectly typed bytes!");
+        return u8ArraySameLengthEqual(this.raw, other.raw);
+    }
 }
@@ -170,2 +218,10 @@ function byteFromString(s) {
 }
+function u8ArraySameLengthEqual(self, other) {
+    for (let i = 0; i < self.length; i += 1) {
+        if (self[i] !== other[i]) {
+            return false;
+        }
+    }
+    return true;
+}
 
@@ -269,5 +325,6 @@ /**
 class TrieNode {
-    constructor() {
-        /** Exactly 512 bits / 64 bytes */
-        this.data = new Uint8Array(64);
+    constructor(
+    /** Exactly 512 bits / 64 bytes */
+    data = new Uint8Array(64)) {
+        this.data = data;
     }
@@ -322,7 +379,7 @@ /** Returns the type of the node */
     getLeft() {
-        return Bytes.fromBlob(this.node.data.subarray(0, HASH_BYTES), HASH_BYTES);
+        return Bytes.fromBlob(this.node.data.subarray(0, HASH_BYTES), HASH_BYTES).asOpaque();
     }
     /** Get the hash of the right sub-trie. */
     getRight() {
-        return Bytes.fromBlob(this.node.data.subarray(HASH_BYTES), HASH_BYTES);
+        return Bytes.fromBlob(this.node.data.subarray(HASH_BYTES), HASH_BYTES).asOpaque();
     }
@@ -361,3 +418,3 @@ }
             // copy the value
-            node.data.set(value.buffer, TRUNCATED_KEY_BYTES + 1);
+            node.data.set(value.raw, TRUNCATED_KEY_BYTES + 1);
         }
@@ -375,3 +432,3 @@ else {
     getKey() {
-        return Bytes.fromBlob(this.node.data.subarray(1, TRUNCATED_KEY_BYTES + 1), TRUNCATED_KEY_BYTES);
+        return Bytes.fromBlob(this.node.data.subarray(1, TRUNCATED_KEY_BYTES + 1), TRUNCATED_KEY_BYTES).asOpaque();
     }
@@ -396,3 +453,3 @@ /**
         const len = this.getValueLength();
-        return BytesBlob.fromBlob(this.node.data.subarray(HASH_BYTES, HASH_BYTES + len));
+        return BytesBlob.blobFrom(this.node.data.subarray(HASH_BYTES, HASH_BYTES + len));
     }
@@ -406,6 +463,47 @@ /**
     getValueHash() {
-        return Bytes.fromBlob(this.node.data.subarray(HASH_BYTES), HASH_BYTES);
+        return Bytes.fromBlob(this.node.data.subarray(HASH_BYTES), HASH_BYTES).asOpaque();
     }
 }
 
+/** A map which uses hashes as keys. */
+class HashDictionary {
+    constructor() {
+        // TODO [ToDr] [crit] We can't use `TrieHash` directly in the map,
+        // because of the way it's being compared. Hence having `string` here.
+        // This has to be benchmarked and re-written to a custom map most likely.
+        this.map = new Map();
+    }
+    /** Return number of items in the dictionary. */
+    get size() {
+        return this.map.size;
+    }
+    /** Return true if the key is present in the dictionary. */
+    has(key) {
+        return this.map.has(key.toString());
+    }
+    /** Get the value under given key or `null` if the value is not present. */
+    get(key) {
+        return this.map.get(key.toString());
+    }
+    /** Insert/overwrite the value at given key. */
+    set(key, value) {
+        this.map.set(key.toString(), value);
+    }
+    /** Remove the key and any value from the dictionary. */
+    delete(key) {
+        this.map.delete(key.toString());
+    }
+}
+
+/** A return value of some comparator. */
+var Ordering;
+(function (Ordering) {
+    /** `self < other` */
+    Ordering[Ordering["Less"] = -1] = "Less";
+    /** `self === other` */
+    Ordering[Ordering["Equal"] = 0] = "Equal";
+    /** `self > other` */
+    Ordering[Ordering["Greater"] = 1] = "Greater";
+})(Ordering || (Ordering = {}));
+
 /**
@@ -417,7 +515,8 @@ * An abstraction over read-only nodes storage.
         this.hasher = hasher;
-        this.nodes = new Map();
+        this.nodes = new HashDictionary();
     }
     get(hash) {
-        const key = NodesDb.hashCompatStr(hash);
-        return this.nodes.get(key) ?? null;
+        return NodesDb.withHashCompat(hash, (key) => {
+            return this.nodes.get(key) ?? null;
+        });
     }
@@ -431,14 +530,14 @@ hashNode(n) {
      * Before calling `toString` the first bit is set to 0, to maintain compatibility
-     * with branch nodes, which have the left subtree stripped out of the first bit (since it's
-     * a branch node identifier).
+     * with branch nodes, which have the left subtree stripped out of the first bit
+     * (since it's a branch node identifier).
      *
      */
-    static hashCompatStr(hash) {
+    static withHashCompat(hash, exe) {
         const prevValue = hash.raw[0];
         hash.raw[0] &= 0b1111_1110;
-        const hashString = hash.toString();
+        const returnValue = exe(hash);
         // restore the original byte, so that we have correct value in case it
         // ends up in the right part of the subtree.
         hash.raw[0] = prevValue;
-        return hashString;
+        return returnValue;
     }
@@ -451,9 +550,11 @@ }
     remove(hash) {
-        const key = NodesDb.hashCompatStr(hash);
-        this.nodes.delete(key);
+        return NodesDb.withHashCompat(hash, (key) => {
+            this.nodes.delete(key);
+        });
     }
     insert(node, hash) {
         const h = hash ?? this.hashNode(node);
-        const key = NodesDb.hashCompatStr(h);
-        this.nodes.set(key, node);
+        NodesDb.withHashCompat(h, (key) => {
+            this.nodes.set(key, node);
+        });
         return h;
@@ -474,9 +575,13 @@ }
         this.flat.set(key.toString(), value);
-        const valueHash = maybeValueHash ?? this.nodes.hasher.hashConcat(value.buffer);
+        const valueHash = maybeValueHash ?? this.nodes.hasher.hashConcat(value.raw);
         const leafNode = LeafNode.fromValue(key, value, valueHash);
         this.root = trieInsert(this.root, this.nodes, leafNode);
     }
+    remove(_) {
+        // TODO [ToDr] implement me.
+        throw new Error("Removing from the trie not implemented yet.");
+    }
     getRoot() {
         if (this.root === null) {
-            return Bytes.zero(HASH_BYTES);
+            return Bytes.zero(HASH_BYTES).asOpaque();
         }
@@ -610,3 +715,3 @@ return this.nodes.hashNode(this.root);
     // Now construct the common branches, and insert zero hash in place of other sub-trees.
-    const zero = Bytes.zero(HASH_BYTES);
+    const zero = Bytes.zero(HASH_BYTES).asOpaque();
     // In case we move the leaf from left to right it's hash needs to be re-calculated (missing bit).
@@ -613,0 +718,0 @@ // TODO [ToDr] [opti] might be better to store the original bit value instead of recalculating.

package.json

 {
   "name": "@typeberry/trie",
-  "version": "0.0.1-9932697",
+  "version": "0.0.1-0ed875f",
   "main": "index.js",
@@ -5,0 +5,0 @@ "author": "Fluffy Labs",

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

45988

increased by30.08%

Lines of code

1280

increased by33.75%

Worsened metrics

Number of package files

3

decreased by-76.92%

No dependency changes