git ssb

1
const Graph = require('ipld-graph-builder')
2
const Uint1Array = require('uint1array')
3
const TextEncoder = require('text-encoding').TextEncoder
4
const DataStore = require('./datastore.js')
5
const treeNode = require('./treeNode.js')
6
7
const encoder = new TextEncoder('utf-8')
8
9
module.exports = class RadixTree {
10
  /**
11
   * @param opts
12
   * @param opts.root {object} a merkle root to a radix tree. If none, RadixTree will create an new root.
13
   * @param opts.db {object} a level db  instance alternitly `opts.graph` can be used
14
   * @param opts.graph {object} an instance of [ipld-graph-builder](https://github.com/ipld/js-ipld-graph-builder) alternitvly `opts.dag` can be used
15
   * @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.
16
   */
17
  constructor (opts) {
18
    this.root = opts.root || {
19
      '/': RadixTree.emptyTreeState
20
    }
21
22
    this.dag = opts.dag || new DataStore(opts.db)
23
    this.graph = opts.graph || new Graph(this.dag)
24
    this._setting = Promise.resolve()
25
    this.appendKeyToRoot = opts.appendKeyToRoot
26
  }
27
28
  /**
29
   * creates a new instance of RadixTree that is the subTree of the given key
30
   * @param {*} key
31
   * @return {Promise} resolve to the new instance of RadixTree
32
   */
33
  async getSubTree (key, decode) {
34
    key = this.formatKey(key)
35
    await this.done()
36
    const {root} = await this._get(key, decode)
37
    return new RadixTree({dag: this.dag, root: root, appendKeyToRoot: true})
38
  }
39
40
  /**
41
   * gets a value given a key. The promise resolves with an object containing
42
   * `node` the node in the merkle tree and `value` the value of the that the
43
   * node contains
44
   * @param {*} key
45
   * @return {Promise}
46
   */
47
  async get (key, decode) {
48
    key = this.formatKey(key)
49
    await this.done()
50
    const result = await this._get(key)
51
    return result.value
52
  }
53
54
  async _get (key) {
55
    let index = 0
56
    let root = this.root
57
    let parent
58
59
    while (1) {
60
      // load the root
61
      const exNode = await this.graph.get(root, treeNode.EXTENSION, true)
62
      if (exNode) {
63
        let subKey = key.subarray(index)
64
65
        const {extensionIndex, extensionLen, extension} = findMatchBits(subKey, root)
66
        index += extensionIndex
67
        // check if we compelete travered the extension
68
        if (extensionIndex !== extensionLen) {
69
          return {
70
            index,
71
            root,
72
            extension,
73
            extensionIndex
74
          }
75
        }
76
      }
77
78
      let keySegment = key[index]
79
      if (keySegment !== undefined) {
80
        const branch = treeNode.getBranch(root)
81
        await this.graph.get(branch, keySegment, true)
82
        // preseves the '/'
83
        const nextRoot = branch[keySegment]
84
        if (!nextRoot) {
85
          return {
86
            root: root,
87
            index: index
88
          }
89
        } else {
90
          parent = root
91
          root = nextRoot
92
        }
93
      } else {
94
        break
95
      }
96
97
      index++
98
    }
99
100
    const value = treeNode.getValue(root)
101
102
    return {
103
      value,
104
      root,
105
      parent,
106
      index
107
    }
108
  }
109
110
  /**
111
   * stores a value at a given key
112
   * @param {*} key
113
   * @return {Promise}
114
   */
115
  set (key, value) {
116
    key = this.formatKey(key)
117
    return this._mutationLock(this._set.bind(this, key, value))
118
  }
119
120
  async _set (key, value) {
121
    if (treeNode.isEmpty(this.root)) {
122
      this.root['/'] = createNode(key, [null, null], value)['/']
123
    } else {
124
      let {root, extensionIndex, extension, index, value: rValue} = await this._get(key)
125
126
      if (rValue) {
127
        treeNode.setValue(root, value)
128
      } else {
129
        if (extensionIndex !== undefined) {
130
          // split the extension node in two
131
          const extensionKey = extension[extensionIndex]
132
          const remExtension = extension.subarray(extensionIndex + 1)
133
          extension = extension.subarray(0, extensionIndex)
134
135
          treeNode.setExtension(root, remExtension)
136
          const branch = [null, null]
137
          branch[extensionKey] = {
138
            '/': root['/']
139
          }
140
          root['/'] = createNode(extension, branch)['/']
141
        }
142
143
        // if there are remaning key segments create an extension node
144
        if (index < key.length) {
145
          const keySegment = key[index]
146
          const extension = key.subarray(index + 1, key.length)
147
          const newNode = createNode(extension, [null, null], value)
148
          const rootBranch = treeNode.getBranch(root)
149
          rootBranch[keySegment] = newNode
150
          treeNode.setBranch(root, rootBranch)
151
        } else {
152
          treeNode.setValue(root, value)
153
        }
154
      }
155
    }
156
  }
157
158
  /**
159
   * deletes a value at a given key
160
   * @param {*} key
161
   * @return {Promise}
162
   */
163
  delete (key) {
164
    key = this.formatKey(key)
165
    return this._mutationLock(this._delete.bind(this, key))
166
  }
167
168
  async _delete (key) {
169
    const results = await this._get(key)
170
    if (results.value !== undefined) {
171
      const root = results.root
172
      const parent = results.parent
173
174
      treeNode.deleteValue(root)
175
176
      const branch = treeNode.getBranch(root)
177
      if (branch.some(el => el !== null)) {
178
        joinNodes(root)
179
      } else {
180
        if (!parent) {
181
          root['/'] = RadixTree.emptyTreeState
182
        } else {
183
          let branch = treeNode.getBranch(parent)
184
          branch = branch.map(node => node === root ? null : node)
185
          treeNode.setBranch(parent, branch)
186
          await this.graph.tree(parent, 2)
187
188
          joinNodes(parent)
189
        }
190
      }
191
    }
192
193
    function joinNodes (root) {
194
      if (treeNode.getValue(root) === undefined) {
195
        let index
196
        const branch = treeNode.getBranch(root)
197
        const nodes = branch.filter((node, i) => {
198
          if (node) {
199
            index = i
200
            return true
201
          }
202
        })
203
204
        if (nodes.length === 1) {
205
          const child = nodes[0]
206
          const pExtension = treeNode.getExtension(root)
207
          const childExtension = treeNode.getExtension(child)
208
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
209
210
          newExtension.set(pExtension)
211
          newExtension[pExtension.length] = index
212
          newExtension.set(childExtension, pExtension.length + 1)
213
214
          treeNode.setExtension(child, newExtension)
215
          root['/'] = child['/']
216
        }
217
      }
218
    }
219
  }
220
221
  /**
222
   * returns a promise that resolve when the tree is done with all of its writes
223
   * @returns {Promise}
224
   */
225
  async done () {
226
    let setting
227
    while (this._setting !== setting) {
228
      setting = this._setting
229
      await setting
230
    }
231
  }
232
233
  _mutationLock (func) {
234
    const setting = this._setting
235
    this._setting = new Promise((resolve, reject) => {
236
      return setting.then(() => {
237
        return func().then(resolve).catch(reject)
238
      })
239
    })
240
    return this._setting
241
  }
242
243
  /**
244
   * creates a merkle root for the current tree and stores the data perstantly
245
   * @returns {Promise}
246
   */
247
  async flush () {
248
    await this.done()
249
    return this.graph.flush(this.root)
250
  }
251
252
  formatKey (key) {
253
    key = RadixTree.formatKey(key)
254
    if (this.appendKeyToRoot) {
255
      key = treeNode.getExtension(this.root).toJSON().concat(key.toJSON())
256
      key = new RadixTree.ArrayConstructor(key)
257
    }
258
    return key
259
  }
260
261
  static formatKey (key) {
262
    if (typeof key === 'string') {
263
      key = encoder.encode(key)
264
    }
265
266
    if (key.constructor !== RadixTree.ArrayConstructor) {
267
      if (Buffer.isBuffer(key)) {
268
        return new RadixTree.ArrayConstructor(new Uint8Array(key).buffer)
269
      } else {
270
        return new RadixTree.ArrayConstructor(key.buffer)
271
      }
272
    } else {
273
      return key
274
    }
275
  }
276
277
  /**
278
   * returns the state of an empty tree
279
   */
280
  static get emptyTreeState () {
281
    return [null, null, null]
282
  }
283
284
  /**
285
   * returns an Uint1Array constructir which is used to repersent keys
286
   * @returns {object}
287
   */
288
  static get ArrayConstructor () {
289
    return Uint1Array
290
  }
291
292
  /**
293
   * returns a merkle link for some given data
294
   * @param {Buffer} data - the data which you would like to hash
295
   * @returns {Buffer}
296
   */
297
  static getMerkleLink (data) {
298
    return DataStore.getMerkleLink(data)
299
  }
300
}
301
302
function createNode (ex, branch, value) {
303
  const node = {
304
    '/': []
305
  }
306
307
  treeNode.setValue(node, value)
308
  treeNode.setExtension(node, ex)
309
  treeNode.setBranch(node, branch)
310
311
  return node
312
}
313
314
function findMatchBits (key, node) {
315
  let extensionIndex = 0
316
  const extension = treeNode.getExtension(node)
317
  const extensionLen = extension.length
318
319
  // checks the extension against the key
320
  while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) {
321
    extensionIndex++
322
  }
323
324
  return {
325
    extensionIndex,
326
    extensionLen,
327
    extension
328
  }
329
}
330