dfinity-radix-tree - npm Package Compare versions

Comparing version 0.1.5 to 0.2.0

datastore.js

@@ -9,11 +9,31 @@ const Buffer = require('safe-buffer').Buffer
 
+function insertTags (val) {
+  if (Array.isArray(val)) {
+    val = val.map(v => {
+      if (v && v.hasOwnProperty('/')) {
+        return new cbor.Tagged(LINK_TAG, v['/'])
+      } else {
+        return insertTags(v)
+      }
+    })
+  }
+  return val
+}
+
 module.exports = class TreeDAG extends DAG {
-  async put (val) {
-    if (val[1]) {
-      val[1] = new cbor.Tagged(LINK_TAG, val[1]['/'])
+  constructor (dag, decoder = new cbor.Decoder({
+    tags: {
+      42: val => {
+        return {
+          '/': val
+        }
+      }
     }
-    if (val[2]) {
-      val[2] = new cbor.Tagged(LINK_TAG, val[2]['/'])
-    }
+  })) {
+    super(dag)
+    this.decoder = decoder
+  }
 
+  async put (val) {
+    val = insertTags(val)
     const encoded = cbor.encode(val)
@@ -36,9 +56,3 @@ const key = await TreeDAG.getMerkleLink(encoded)
           val = Buffer.from(val, 'hex')
-          const decoded = cbor.decode(val)
-          if (decoded[1]) {
-            decoded[1]['/'] = decoded[1].value
-          }
-          if (decoded[2]) {
-            decoded[2]['/'] = decoded[2].value
-          }
+          const decoded = this.decoder.decodeFirst(val)
           resolve(decoded)
@@ -45,0 +59,0 @@ }

docs/index.md

@@ -5,15 +5,17 @@ <!-- Generated by documentation.js. Update this documentation by updating the source code. -->
 
--   [constructor](#constructor)
--   [get](#get)
--   [set](#set)
--   [delete](#delete)
--   [done](#done)
--   [flush](#flush)
--   [emptyTreeState](#emptytreestate)
--   [ArrayConstructor](#arrayconstructor)
--   [getMerkleLink](#getmerklelink)
+-   [constructor][1]
+-   [root][2]
+-   [get][3]
+-   [set][4]
+-   [delete][5]
+-   [done][6]
+-   [flush][7]
+-   [rootExists][8]
+-   [emptyTreeState][9]
+-   [ArrayConstructor][10]
+-   [getMerkleLink][11]
 
 ## constructor
 
-[index.js:17-25](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L17-L25 "Source code on GitHub")
+[index.js:18-25][12]
 
@@ -25,8 +27,17 @@ **Parameters**
     -   `opts.db`  {object} a level db instance; alternatively, `opts.graph` can be used
-    -   `opts.graph`  {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder); alternatively, `opts.dag` can be used
-    -   `opts.dag`  {object} an instance if [ipfs.dag](https://github.com/ipfs/js-ipfs#dag). If there is no `opts.graph` this will be used to create a new graph instance.
+    -   `opts.graph`  {object} an instance of [ipld-graph-builder][13]; alternatively, `opts.dag` can be used
+    -   `opts.dag`  {object} an instance if [ipfs.dag][14]. If there is no `opts.graph` this will be used to create a new graph instance.
+    -   `opts.decoder`  {object} a cbor decoder
 
+## root
+
+[index.js:31-33][15]
+
+the root of the tree
+
+Type: [Buffer][16]
+
 ## get
 
-[index.js:32-36](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L32-L36 "Source code on GitHub")
+[index.js:44-48][17]
 
@@ -39,7 +50,7 @@ gets a value given a key
 
-Returns **[Promise](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Promise)** 
+Returns **[Promise][18]** 
 
 ## set
 
-[index.js:87-90](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L87-L90 "Source code on GitHub")
+[index.js:98-101][19]
 
@@ -53,7 +64,7 @@ stores a value at a given key returning the tree node that the value was saved in
 
-Returns **[Promise](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Promise)** 
+Returns **[Promise][18]** 
 
 ## delete
 
-[index.js:139-142](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L139-L142 "Source code on GitHub")
+[index.js:150-153][20]
 
@@ -66,23 +77,35 @@ smContainer.js deletes a value at a given key
 
-Returns **[Promise](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Promise)** 
+Returns **[Promise][18]** 
 
 ## done
 
-[index.js:201-207](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L201-L207 "Source code on GitHub")
+[index.js:212-218][21]
 
 returns a promise that resolve when the tree is done with all of its writes
 
-Returns **[Promise](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Promise)** 
+Returns **[Promise][18]** 
 
 ## flush
 
-[index.js:223-226](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L223-L226 "Source code on GitHub")
+[index.js:234-238][22]
 
 creates a merkle root for the current tree and stores the data persistently
 
-Returns **[Promise](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Promise)** 
+Returns **[Promise][18]** 
 
+## rootExists
+
+[index.js:250-258][23]
+
+Checks if a given root exists or not
+
+**Parameters**
+
+-   `root` **[Buffer][16]** 
+
+Returns **[Promise][18]&lt;[boolean][24]>** 
+
 ## emptyTreeState
 
-[index.js:252-254](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L252-L254 "Source code on GitHub")
+[index.js:279-281][25]
 
@@ -93,11 +116,11 @@ returns the state of an empty tree
 
-[index.js:260-262](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L260-L262 "Source code on GitHub")
+[index.js:287-289][26]
 
 returns an Uint1Array constructor which is used to represent keys
 
-Returns **[object](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Object)** 
+Returns **[object][27]** 
 
 ## getMerkleLink
 
-[index.js:269-271](https://github.com/dfinity/js-dfinity-radix-tree/blob/806b9f80cab0da81d7e98a62754b80167fe58296/index.js#L269-L271 "Source code on GitHub")
+[index.js:296-298][28]
 
@@ -108,4 +131,60 @@ returns a merkle link for some given data
 
--   `data` **[Buffer](https://nodejs.org/api/buffer.html)** the data which you would like to hash
+-   `data` **[Buffer][16]** the data which you would like to hash
 
-Returns **[Buffer](https://nodejs.org/api/buffer.html)** 
+Returns **[Buffer][16]** 
+
+[1]: #constructor
+
+[2]: #root
+
+[3]: #get
+
+[4]: #set
+
+[5]: #delete
+
+[6]: #done
+
+[7]: #flush
+
+[8]: #rootexists
+
+[9]: #emptytreestate
+
+[10]: #arrayconstructor
+
+[11]: #getmerklelink
+
+[12]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L18-L25 "Source code on GitHub"
+
+[13]: https://github.com/ipld/js-ipld-graph-builder
+
+[14]: https://github.com/ipfs/js-ipfs#dag
+
+[15]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L31-L33 "Source code on GitHub"
+
+[16]: https://nodejs.org/api/buffer.html
+
+[17]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L44-L48 "Source code on GitHub"
+
+[18]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Promise
+
+[19]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L98-L101 "Source code on GitHub"
+
+[20]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L150-L153 "Source code on GitHub"
+
+[21]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L212-L218 "Source code on GitHub"
+
+[22]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L234-L238 "Source code on GitHub"
+
+[23]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L250-L258 "Source code on GitHub"
+
+[24]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Boolean
+
+[25]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L279-L281 "Source code on GitHub"
+
+[26]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L287-L289 "Source code on GitHub"
+
+[27]: https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Object
+
+[28]: https://github.com/dfinity/js-dfinity-radix-tree/blob/588bfeefe36f73792935e70a42db416f2a0d838c/index.js#L296-L298 "Source code on GitHub"

index.js

@@ -16,9 +16,9 @@ const Graph = require('ipld-graph-builder')
    * @param opts.dag {object} an instance if [ipfs.dag](https://github.com/ipfs/js-ipfs#dag). If there is no `opts.graph` this will be used to create a new graph instance.
+   * @param opts.decoder {object} a cbor decoder
    */
   constructor (opts) {
-    this.root = opts.root || {
-      '/': RadixTree.emptyTreeState
-    }
+    this._root = {}
+    this.root = opts.root || RadixTree.emptyTreeState
 
-    this.dag = opts.dag || new DataStore(opts.db)
+    this.dag = opts.dag || new DataStore(opts.db, opts.decoder)
     this.graph = opts.graph || new Graph(this.dag)
@@ -29,2 +29,14 @@ this._setting = Promise.resolve()
   /**
+   * the root of the tree
+   * @type {Buffer}
+   */
+  get root () {
+    return this._root['/']
+  }
+
+  set root (root) {
+    this._root['/'] = root
+  }
+
+  /**
    * gets a value given a key
@@ -42,3 +54,3 @@ * @param {*} key
     let index = 0
-    let root = this.root
+    let root = this._root
     let parent
@@ -51,3 +63,2 @@
         let subKey = key.subarray(index)
-
         const {extensionIndex, extensionLen, extension} = findMatchBits(subKey, root)
@@ -97,5 +108,5 @@ index += extensionIndex
   async _set (key, value) {
-    if (treeNode.isEmpty(this.root)) {
-      this.root['/'] = createNode(key, [null, null], value)['/']
-      return this.root['/']
+    if (treeNode.isEmpty(this._root)) {
+      this._root['/'] = createNode(key, [null, null], value)['/']
+      return this._root['/']
     } else {
@@ -230,3 +241,4 @@ let {node, root, extensionIndex, extension, index, value: rValue} = await this._get(key)
     await this.done()
-    return this.graph.flush(this.root)
+    await this.graph.flush(this._root)
+    return this.root
   }
@@ -239,2 +251,17 @@
 
+  /**
+   * Checks if a given root exists or not
+   * @param {Buffer} root
+   * @return {Promise<boolean>}
+   */
+  async rootExists (root) {
+    await this.flush()
+    try {
+      await this.dag.get(root)
+    } catch (e) {
+      return false
+    }
+    return true
+  }
+
   static formatKey (key) {
@@ -241,0 +268,0 @@ if (typeof key === 'string') {

package.json

 {
   "name": "dfinity-radix-tree",
-  "version": "0.1.5",
+  "version": "0.2.0",
   "description": "This implements a binary merkle radix tree",
@@ -30,3 +30,3 @@ "main": "index.js",
   "dependencies": {
-    "borc": "^2.0.2",
+    "borc": "git+ssh://[e-mail]:dignifiedquire/borc.git#fix/nested-array",
     "ipld-graph-builder": "^1.3.8",
@@ -33,0 +33,0 @@ "text-encoding": "^0.6.4",

tests/index.js

@@ -7,2 +7,15 @@ const tape = require('tape')
 
+tape('root existance', async t => {
+  let tree = new RadixTree({
+    db: db
+  })
+  let exists = await tree.rootExists(Buffer.from([0]))
+  t.equals(exists, false)
+
+  tree.set('test', Buffer.from('cat'))
+  exists = await tree.rootExists(Buffer.from('01cff22f1e93e25d8691d6238031d98885ab468f', 'hex'))
+  t.equals(exists, true)
+  t.end()
+})
+
 tape('should generate the same stateRoot', async t => {
@@ -12,2 +25,3 @@ let tree = new RadixTree({
   })
+  tree.root = [null, null, null]
   const stateRoot = await tree.flush()
@@ -19,2 +33,19 @@ const stateRoot2 = await tree.flush()
 
+tape('should generate the same stateRoot', async t => {
+  let tree1 = new RadixTree({
+    db
+  })
+
+  let tree2 = new RadixTree({
+    db
+  })
+  await tree1.flush()
+  tree1.set('test', Buffer.from('cat'))
+  tree2.set('test', Buffer.from('cat'))
+  const stateRoot = await tree1.flush()
+  const stateRoot2 = await tree2.flush()
+  t.deepEquals(stateRoot2, stateRoot)
+  t.end()
+})
+
 tape('set and get', async t => {
@@ -104,3 +135,3 @@ const r = await RadixTree.getMerkleLink(Buffer.from([0]))
   await tree.delete('ter')
-  t.deepEquals(tree.root['/'], RadixTree.emptyTreeState)
+  t.deepEquals(tree.root, RadixTree.emptyTreeState)
 
@@ -120,3 +151,3 @@ // tests delete midle branchs
   await tree.delete('test')
-  t.deepEquals(tree.root['/'], RadixTree.emptyTreeState)
+  t.deepEquals(tree._root['/'], RadixTree.emptyTreeState)
   t.end()
@@ -176,5 +207,5 @@ })
 
-  t.deepEquals(tree.root['/'], RadixTree.emptyTreeState)
+  t.deepEquals(tree._root['/'], RadixTree.emptyTreeState)
 
   t.end()
 })

treeNode.js

 const Uint1Array = require('uint1array')
+const EMPTY_STATE_ROOT = Buffer.from('4cf812be9be2c6008325050f43d06676a08612c7', 'hex')
 
@@ -53,4 +54,7 @@ function toTypedArray (array) {
 exports.isEmpty = function (node) {
-  const branch = exports.getBranch(node)
-  return !node['/'][EXTENSION] && !branch[0] && !branch[1] && node['/'][VALUE] === undefined
+  if (Buffer.isBuffer(node['/'])) {
+    return !Buffer.compare(node['/'], EMPTY_STATE_ROOT)
+  } else {
+    return node['/'].every(el => !el)
+  }
 }

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

Git dependency

Supply chain risk

Contains a dependency which resolves to a remote git URL. Dependencies fetched from git URLs are not immutable and can be used to inject untrusted code or reduce the likelihood of a reproducible install.

Found 1 instance in 1 package

Manifest confusion

Supply chain risk

This package has inconsistent metadata. This could be malicious or caused by an error when publishing the package.

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

279963

increased by4.02%

Lines of code

1560

increased by4.63%

Worsened metrics

Number of high supply chain risk alerts

1

increased byInfinity%

Number of medium supply chain risk alerts

1

increased byInfinity%

Dependency changes

• - Removedbignumber.js@9.1.2(transitive)

• - Removedborc@2.1.2(transitive)

• - Removedcommander@2.20.3(transitive)

• - Removeddelimit-stream@0.1.0(transitive)

• - Removedinherits@2.0.4(transitive)

• - Removediso-url@0.4.7(transitive)

• - Removedjson-text-sequence@0.1.1(transitive)

• - Removedreadable-stream@3.6.2(transitive)

• - Removedstring_decoder@1.3.0(transitive)

• - Removedutil-deprecate@1.0.2(transitive)

• Updatedborc@git+ssh://[e-mail]:dignifiedquire/borc.git#fix/nested-array