import { Queue } from '@libp2p/utils' import filter from 'it-filter' import toBuffer from 'it-to-buffer' import { createUnsafe } from 'multiformats/block' import type { GraphWalker, GraphWalkerComponents, GraphWalkerInit, GraphNode, WalkOptions } from '@helia/interface' import type { AbortOptions } from '@libp2p/interface' import type { CID } from 'multiformats' export type { GraphWalker, GraphWalkerComponents, GraphWalkerInit, GraphNode, WalkOptions } /** * A depth-first walker descends into child blocks before processing successor * sibling blocks */ export function depthFirstWalker (init?: GraphWalkerInit): (components: GraphWalkerComponents) => GraphWalker { return (components) => new DepthFirstGraphWalker(components, init) } /** * A breadth-first walker processes sibling blocks before child blocks */ export function breadthFirstWalker (init?: GraphWalkerInit): (components: GraphWalkerComponents) => GraphWalker { return (components) => new BreadthFirstGraphWalker(components, init) } /** * A natural order walker processes blocks in the order defined by the codec and * does not try to sort them */ export function naturalOrderWalker (init?: GraphWalkerInit): (components: GraphWalkerComponents) => GraphWalker { return (components) => new NaturalOrderGraphWalker(components, init) } interface JobOptions extends AbortOptions { cid: CID depth: number path: CID[] } abstract class AbstractGraphWalker { private readonly components: GraphWalkerComponents constructor (components: GraphWalkerComponents, init: GraphWalkerInit = {}) { this.components = components } async * walk (cid: CID, options?: WalkOptions): AsyncGenerator> { const queue = this.getQueue() const gen = filter(queue.toGenerator(options), (node) => node != null) as AsyncGenerator> let finished = false const maxDepth = options?.depth ?? Infinity const job = async (opts: JobOptions): Promise | undefined> => { const cid = opts.cid const bytes = await toBuffer(this.components.blockstore.get(cid, opts)) const block = createUnsafe({ cid, bytes, codec: await this.components.getCodec(cid.code) }) if (opts.depth < maxDepth) { for (const [, linkedCid] of block.links()) { if (options?.includeChild?.(linkedCid, block) === false) { continue } queue.add(job, { ...opts, cid: linkedCid, depth: opts.depth + 1, path: [...opts.path, linkedCid] }) // eslint-disable-next-line no-loop-func .catch(err => { // only throw if the generator is still yielding results, otherwise // it can cause unhandled promise rejections if (!finished) { gen.throw(err) } }) } } return { block, depth: opts.depth, path: opts.path } } queue.add(job, { ...options, cid, depth: 0, path: [cid] }) .catch(err => { // only throw if the generator is still yielding results, otherwise it // can cause unhandled promise rejections if (!finished) { gen.throw(err) } }) try { yield * gen } finally { finished = true // abort any in-progress operations queue.abort() } } abstract getQueue (): Queue | undefined, JobOptions> } class DepthFirstGraphWalker extends AbstractGraphWalker { getQueue(): Queue | undefined, JobOptions> { return new Queue | undefined, JobOptions>({ concurrency: 1, sort: (a, b) => { if (a.options.depth === b.options.depth) { return 0 } if (a.options.depth < b.options.depth) { return 1 } return -1 } }) } } class BreadthFirstGraphWalker extends AbstractGraphWalker { getQueue(): Queue | undefined, JobOptions> { return new Queue | undefined, JobOptions>({ concurrency: 1, sort: (a, b) => { if (a.options.depth === b.options.depth) { return 0 } if (a.options.depth < b.options.depth) { return -1 } return 1 } }) } } export class NaturalOrderGraphWalker extends AbstractGraphWalker { getQueue(): Queue | undefined, JobOptions> { return new Queue | undefined, JobOptions>({ concurrency: 1 }) } }