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