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