import { decode } from '@ipld/dag-pb' import { murmur3128 } from '@multiformats/murmur3' import { Bucket, createHAMT } from 'hamt-sharding' import { UnixFS } from 'ipfs-unixfs' import toBuffer from 'it-to-buffer' import { NotUnixFSError } from '../../errors.ts' import type { ReadableStorage, WalkPathOptions } from '../../index.ts' import type { ResolveResult } from '../index.ts' import type { PBLink, PBNode } from '@ipld/dag-pb' import type { BucketPosition } from 'hamt-sharding' interface ShardTraversalContext { hamtDepth: number rootBucket: Bucket lastBucket: Bucket } // FIXME: this is copy/pasted from ipfs-unixfs-importer/src/options.js const hashFn = async function (buf: Uint8Array): Promise { return (await murmur3128.encode(buf)) // Murmur3 outputs 128 bit but, accidentally, IPFS Go's // implementation only uses the first 64, so we must do the same // for parity.. .slice(0, 8) // Invert buffer because that's how Go impl does it .reverse() } const addLinksToHamtBucket = async (links: PBLink[], bucket: Bucket, rootBucket: Bucket): Promise => { const padLength = (bucket.tableSize() - 1).toString(16).length await Promise.all( links.map(async link => { if (link.Name == null) { // TODO(@rvagg): what do? this is technically possible throw new Error('Unexpected Link without a Name') } if (link.Name.length === padLength) { const pos = parseInt(link.Name, 16) bucket._putObjectAt(pos, new Bucket({ hash: rootBucket._options.hash, bits: rootBucket._options.bits }, bucket, pos)) return } await rootBucket.put(link.Name.substring(2), true) }) ) } const toPrefix = (position: number, padLength: number): string => { return position .toString(16) .toUpperCase() .padStart(padLength, '0') .substring(0, padLength) } const toBucketPath = (position: BucketPosition): Array> => { let bucket = position.bucket const path = [] while (bucket._parent != null) { path.push(bucket) bucket = bucket._parent } path.push(bucket) return path.reverse() } export async function * findShardCid (node: PBNode, name: string, rest: string[], blockstore: ReadableStorage, context?: ShardTraversalContext, options?: WalkPathOptions): AsyncGenerator { if (context == null) { if (node.Data == null) { throw new NotUnixFSError('No data in PBNode') } let dir: UnixFS try { dir = UnixFS.unmarshal(node.Data) } catch (err: any) { throw new NotUnixFSError(err.message) } if (dir.type !== 'hamt-sharded-directory') { throw new NotUnixFSError('Not a HAMT') } if (dir.fanout == null) { throw new NotUnixFSError('Missing fanout') } const rootBucket = createHAMT({ hashFn, bits: Math.log2(Number(dir.fanout)) }) context = { rootBucket, hamtDepth: 1, lastBucket: rootBucket } } const padLength = (context.lastBucket.tableSize() - 1).toString(16).length await addLinksToHamtBucket(node.Links, context.lastBucket, context.rootBucket) const position = await context.rootBucket._findNewBucketAndPos(name) let prefix = toPrefix(position.pos, padLength) const bucketPath = toBucketPath(position) if (bucketPath.length > context.hamtDepth) { context.lastBucket = bucketPath[context.hamtDepth] prefix = toPrefix(context.lastBucket._posAtParent, padLength) } const link = node.Links.find(link => { if (link.Name == null) { return false } const entryPrefix = link.Name.substring(0, padLength) const entryName = link.Name.substring(padLength) if (entryPrefix !== prefix) { // not the entry or subshard we're looking for return false } if (entryName !== '' && entryName !== name) { // not the entry we're looking for return false } return true }) if (link == null) { return } if (link.Name != null && link.Name.substring(padLength) === name) { yield { cid: link.Hash, name: link.Name.substring(padLength), rest } return } context.hamtDepth++ const block = await toBuffer(blockstore.get(link.Hash, options)) node = decode(block) if (options?.yieldSubShards === true) { yield { cid: link.Hash, name: link.Name ?? '', rest: [name, ...rest] } } yield * findShardCid(node, name, rest, blockstore, context, options) }