bfs_thing.js

// run a breadth-first search, logging all matches to the console along with the path followed to get there.
// this is designed for interactive use in e.g. browser dev console,
//  I use it when i'm writing userscripts to look for places where certain data is exposed through the global scope

// by amgg.
// license: you can do whatever you want forever

function BFS(root, predicate, { traversers = null, chunk_size = 512, verbose = false } = {}) {
    // populate default options
    traversers ??= [BFS.traversers.key_via_reflect];
    // tracks already-seen nodes
    const seen = new Set([root]);
    // wrappper around predicate so caller doesn't need to manually catch errors
    function matchTest(val) { try { return predicate(val); } catch(err) { return false; } }
    // populate initial queue
    const queue = [];
    for(const traverser of traversers) {
        if(traverser.is_candidate(root)) { queue.push({traverser, item: root, path: []}); }
    }
    if(queue.length < 1) { console.error('no traversers recognized root as a candidate!'); }
    if(verbose) { console.log('starting BFS with', {verbose, traversers, chunk_size}); }
    // run distributed across frames, so that the page won't totally freeze
    (function doChunk() {
        for(let i = 0; i < chunk_size; i++) {
            if(queue.length < 1) { console.log('done!'); seen.clear(); return; }
            const cur = queue.shift();
            for(const edge of cur.traverser.successor_edges(cur.item)) {
                let v;
                try {
                    v = cur.traverser.follow_edge(cur.item, edge);
                } catch(err) {
                    if(verbose) { console.error(err); }
                    continue;
                }
                if(!seen.has(v)) for(const child_traverser of traversers) {
                    if(child_traverser.is_candidate(v)) {
                        queue.push({traverser: child_traverser, item: v, path: [...cur.path, edge]});
                    }
                    seen.add(v);
                }
                if(matchTest(v)) console.log( {result: v, path: [...cur.path, edge]} );
            }
        }
        setTimeout(doChunk, 0);
    })();
};
BFS.traversers = {
    key_via_reflect: {
        is_candidate(o) { return typeof o === 'object' && o !== null && o !== undefined; },
        successor_edges(o) { return Reflect.ownKeys(o); },
        follow_edge(o, k) { return Reflect.get(o, k); },
    },
    parse_json: {
        _jsonparse_edge: Symbol("JSON.parse()"),
        is_candidate(o) { return o !== null && o !== undefined && o.constructor === String },
        successor_edges(o) { return [this._jsonparse_edge]; },
        follow_edge(o, k) { return JSON.parse(o); },
    },
};


// example usages

// find a value
BFS(window, x => x === 'qux');
// find objects with a given property
BFS(window, x => x?.foo !== undefined);

// specifying traversers
BFS(window, x => x === 'qux', {
    traversers: [BFS.traversers.key_via_reflect, BFS.traversers.parse_json],
});