mod.ts
1 import { assert } from "@std/assert"; 2 import { getLogger } from "@logtape/logtape"; 3 import { 4 type codec, 5 get, 6 type Hash, 7 isHash, 8 remove, 9 set, 10 } from "@massmarket/utils"; 11 import { type AbstractStore, ContentAddressableStore } from "@massmarket/store"; 12 13 const logger = getLogger(["mass-market", "merkle-dag-builder"]); 14 15 export type RootValue = 16 | codec.CodecValue 17 | Promise<codec.CodecValue>; 18 19 export class DAG { 20 /** the store that the graph is stored in */ 21 public store: ContentAddressableStore; 22 23 /** 24 * Creates a new graph 25 */ 26 constructor(store: AbstractStore) { 27 this.store = new ContentAddressableStore(store); 28 } 29 30 // this loads a hash from the store 31 async #loadHash( 32 hash: Hash, 33 clone = false, 34 ): Promise<codec.CodecValue> { 35 const val = await this.store.get(hash); 36 if (!val) { 37 logger.info`Hash not found: ${hash}`; 38 throw new Error(`Hash not found`); 39 } 40 if (clone) { 41 // we assume the store shares objects as a caching mechanism 42 // (TODO: it doesn't yet though) 43 // so we need to clone the object to avoid modifying the original 44 return structuredClone(val); 45 } else { 46 return val; 47 } 48 } 49 50 /** 51 * An async generator that walks a given path 52 */ 53 async *walk( 54 root: RootValue, 55 path: codec.CodecKey[], 56 clone = false, 57 ): AsyncGenerator<{ 58 value: codec.CodecValue; 59 step?: codec.CodecValue; 60 }> { 61 if (root instanceof Promise) { 62 root = await root; 63 } 64 if (isHash(root)) { 65 root = (await this.#loadHash(root, clone))!; 66 } 67 if (clone) { 68 root = structuredClone(root); 69 } 70 yield { 71 value: root, 72 }; 73 for (const step of path) { 74 let value = get(root, step) as codec.CodecValue; 75 if (value !== undefined) { 76 // load hash links 77 if (isHash(value)) { 78 // replace the hash with the value it loaded 79 value = await this.#loadHash(value, clone); 80 set(root, step, { "/": value }); 81 } 82 root = value; 83 yield { 84 value, 85 step, 86 }; 87 } else { 88 return; 89 } 90 } 91 } 92 93 /** 94 * traverses an object's path and returns the resulting value, if any, in a Promise 95 */ 96 async get( 97 root: RootValue, 98 path: codec.CodecKey[], 99 ): Promise<codec.CodecValue | undefined> { 100 const walk = await Array.fromAsync( 101 this.walk(root, path), 102 ); 103 104 if (walk.length === path.length + 1) { 105 return walk.pop()!.value; 106 } 107 } 108 109 /** 110 * sets a value on a root object given its path 111 */ 112 async set( 113 root: RootValue, 114 path: codec.CodecKey[], 115 value: 116 | codec.CodecValue 117 | (( 118 parent: codec.CodecValue, 119 key: codec.CodecKey, 120 ) => Promise<void> | void), 121 ): Promise<codec.CodecValue> { 122 assert(path.length); 123 const last = path[path.length - 1]; 124 path = path.slice(0, -1); 125 const walk = await Array.fromAsync( 126 this.walk(root, path, true), 127 ); 128 129 if (walk.length === path.length + 1) { 130 const parent = walk[walk.length - 1].value; 131 if (typeof value === "function") { 132 await value(parent, last); 133 } else { 134 set(parent, last, value); 135 } 136 } else { 137 logger.info`Path ${path.join(".")} does not exist`; 138 throw new Error(`Path does not exist`); 139 } 140 return walk[0].value; 141 } 142 143 /** 144 * adds a value to a root object given its path. if the parent value is an array the added value will be sliced into the array 145 */ 146 add( 147 root: RootValue, 148 path: codec.CodecKey[], 149 value: codec.CodecValue, 150 ): Promise<codec.CodecValue> { 151 return this.set( 152 root, 153 path, 154 (parent: codec.CodecValue, key: codec.CodecKey) => { 155 assert( 156 parent, 157 `The Value at the path ${path.join("/")} does not exist`, 158 ); 159 if (parent instanceof Array && typeof key === "number") { 160 parent.splice(key, 0, value); 161 } else { 162 set(parent, key, value); 163 } 164 }, 165 ); 166 } 167 168 /** 169 * appends a value to an array. If the value at the given path is not an array, it will throw an error 170 */ 171 append( 172 root: RootValue, 173 path: codec.CodecKey[], 174 value: codec.CodecValue, 175 ): Promise<codec.CodecValue> { 176 return this.set( 177 root, 178 path, 179 (parent: codec.CodecValue, step: codec.CodecKey) => { 180 const arr = get(parent, step); 181 if (Array.isArray(arr)) { 182 arr.push(value); 183 } else { 184 logger.info`Trying to append to non-array, path ${path.join("/")}`; 185 throw new Error(`Trying to append to non-array`); 186 } 187 }, 188 ); 189 } 190 191 /** 192 * removes a value. If the parent is an array, it will remove the value at the given index. If the parent is an object, it will delete the key. 193 */ 194 remove( 195 root: RootValue, 196 path: codec.CodecKey[], 197 ): Promise<codec.CodecValue> { 198 return this.set( 199 root, 200 path, 201 (parent: codec.CodecValue, step: codec.CodecKey) => { 202 remove(parent, step); 203 }, 204 ); 205 } 206 207 /** 208 * adds a number to a value at the given path. If the value at the path is not a number, it will throw an error. 209 */ 210 addNumber( 211 root: RootValue, 212 path: codec.CodecKey[], 213 amount: number, 214 ): Promise<codec.CodecValue> { 215 return this.set( 216 root, 217 path, 218 (parent: codec.CodecValue, step: codec.CodecKey) => { 219 const currentValue = get(parent, step); 220 if (typeof currentValue === "number") { 221 set(parent, step, currentValue + amount); 222 } else { 223 logger.info`Trying to add number to non-number, path ${ 224 path.join("/") 225 }`; 226 throw new Error(`Trying to add number to non-number`); 227 } 228 }, 229 ); 230 } 231 232 /** 233 * flush an object to the store and create a merkle root 234 */ 235 async merklelize( 236 root: RootValue, 237 ): Promise<Hash> { 238 if (root instanceof Promise) { 239 root = await root; 240 } 241 return this.store.set(root); 242 } 243 }