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