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
  }
26
27
  /**
28
   * returns the state of an empty tree
29
   */
30
  static get emptyTreeState () {
31
    return [null, null, null]
32
  }
33
34
  /**
35
   * returns an Uint1Array constructir which is used to repersent keys
36
   * @returns {object}
37
   */
38
  static get ArrayConstructor () {
39
    return Uint1Array
40
  }
41
42
  /**
43
   * returns a merkle link for some given data
44
   * @param {Buffer} data - the data which you would like to hash
45
   * @returns {Buffer}
46
   */
47
  static getMerkleLink (data) {
48
    return DataStore.getMerkleLink(data)
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: index,
68
            root: root,
69
            extension: extension,
70
            extensionIndex: 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: value,
101
      root: root,
102
      parent: parent,
103
      index: index
104
    }
105
  }
106
107
  /**
108
   * gets a value given a key. The promise resolves with an object containing
109
   * `node` the node in the merkle tree and `value` the value of the that the
110
   * node contains
111
   * @param {*} key
112
   * @return {Promise}
113
   */
114
  async get (key, decode) {
115
    key = RadixTree.formatKey(key)
116
    let {root, value} = await this._get(key)
117
    if (decode && Buffer.isBuffer(value)) {
118
      value = cbor.decode(value)
119
      treeNode.setValue(root, value)
120
    }
121
    return {node: root, value}
122
  }
123
124
  /**
125
   * stores a value at a given key
126
   * @param {*} key
127
   * @return {Promise}
128
   */
129
  async set (key, value) {
130
    key = RadixTree.formatKey(key)
131
132
    if (treeNode.isEmpty(this.root)) {
133
      this.root['/'] = createNode(key, [null, null], value)['/']
134
    } else {
135
      let {root, extensionIndex, extension, index, value: rValue} = await this._get(key)
136
137
      if (rValue) {
138
        treeNode.setValue(root, value)
139
      } else {
140
        if (extensionIndex !== undefined) {
141
          // split the extension node in two
142
          const extensionKey = extension[extensionIndex]
143
          const remExtension = extension.subarray(extensionIndex + 1)
144
          extension = extension.subarray(0, extensionIndex)
145
146
          treeNode.setExtension(root, remExtension)
147
          const branch = [null, null]
148
          branch[extensionKey] = {
149
            '/': root['/']
150
          }
151
          root['/'] = createNode(extension, branch)['/']
152
        }
153
154
        // if there are remaning key segments create an extension node
155
        if (index < key.length) {
156
          const keySegment = key[index]
157
          const extension = key.subarray(index + 1, key.length)
158
          const newNode = createNode(extension, [null, null], value)
159
          const rootBranch = treeNode.getBranch(root)
160
          rootBranch[keySegment] = newNode
161
          treeNode.setBranch(root, rootBranch)
162
        } else {
163
          treeNode.setValue(root, value)
164
        }
165
      }
166
    }
167
  }
168
169
  /**
170
   * deletes a value at a given key
171
   * @param {*} key
172
   * @return {Promise}
173
   */
174
  async delete (key) {
175
    key = RadixTree.formatKey(key)
176
    const results = await this._get(key)
177
    if (results.value !== undefined) {
178
      const root = results.root
179
      const parent = results.parent
180
181
      treeNode.deleteValue(root)
182
183
      const branch = treeNode.getBranch(root)
184
      if (branch.some(el => el !== null)) {
185
        joinNodes(root)
186
      } else {
187
        if (!parent) {
188
          root['/'] = RadixTree.emptyTreeState
189
        } else {
190
          let branch = treeNode.getBranch(parent)
191
          branch = branch.map(node => node === root ? null : node)
192
          treeNode.setBranch(parent, branch)
193
          await this.graph.tree(parent, 2)
194
195
          joinNodes(parent)
196
        }
197
      }
198
    }
199
200
    function joinNodes (root) {
201
      if (treeNode.getValue(root) === undefined) {
202
        let index
203
        const branch = treeNode.getBranch(root)
204
        const nodes = branch.filter((node, i) => {
205
          if (node) {
206
            index = i
207
            return true
208
          }
209
        })
210
211
        if (nodes.length === 1) {
212
          const child = nodes[0]
213
          const pExtension = treeNode.getExtension(root)
214
          const childExtension = treeNode.getExtension(child)
215
          const newExtension = new RadixTree.ArrayConstructor(pExtension.length + childExtension.length + 1)
216
217
          newExtension.set(pExtension)
218
          newExtension[pExtension.length] = index
219
          newExtension.set(childExtension, pExtension.length + 1)
220
221
          treeNode.setExtension(child, newExtension)
222
          root['/'] = child['/']
223
        }
224
      }
225
    }
226
  }
227
228
  /**
229
   * creates a merkle root for the current tree and stores the data perstantly
230
   * @returns {Promise}
231
   */
232
  flush () {
233
    return this.graph.flush(this.root)
234
  }
235
236
  static formatKey (key) {
237
    if (typeof key === 'string') {
238
      key = encoder.encode(key)
239
    }
240
241
    if (key.constructor !== RadixTree.ArrayConstructor) {
242
      return new RadixTree.ArrayConstructor(key.buffer)
243
    } else {
244
      return key
245
    }
246
  }
247
}
248
249
function createNode (ex, branch, value) {
250
  const node = {
251
    '/': []
252
  }
253
254
  treeNode.setValue(node, value)
255
  treeNode.setExtension(node, ex)
256
  treeNode.setBranch(node, branch)
257
258
  return node
259
}
260
261
function findMatchBits (key, node) {
262
  let extensionIndex = 0
263
  const extension = treeNode.getExtension(node)
264
  const extensionLen = extension.length
265
266
  // checks the extension against the key
267
  while (extensionIndex < extensionLen && extension[extensionIndex] === key[extensionIndex]) {
268
    extensionIndex++
269
  }
270
271
  return {
272
    extensionIndex: extensionIndex,
273
    extensionLen: extensionLen,
274
    extension: extension
275
  }
276
}
277