git ssb

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