Quelle  fathom.mjs   Sprache: unbekannt

/*
DO NOT TOUCH fathom.mjs DIRECTLY. See the README for instructions.
*/

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/**
 * A :func:`rule` depends on another rule which itself depends on the first
 * rule again, either directly or indirectly.
 */
class CycleError extends Error {
}

/**
  * An examined element was not contained in a browser ``window`` object, but
  * something needed it to be.
  */
class NoWindowError extends Error {
}

var exceptions = /*#__PURE__*/Object.freeze({
  __proto__: null,
  CycleError: CycleError,
  NoWindowError: NoWindowError
});

/**
 * Return the passed-in arg. Useful as a default.
 */
function identity(x) {
    return x;
}

/*eslint-env browser*/

/**
 * From an iterable return the best item, according to an arbitrary comparator
 * function. In case of a tie, the first item wins.
 *
 * @arg by {function} Given an item of the iterable, return a value to compare
 * @arg isBetter {function} Return whether its first arg is better than its
 *     second
 */
function best(iterable, by, isBetter) {
    let bestSoFar, bestKeySoFar;
    let isFirst = true;
    forEach(
        function (item) {
            const key = by(item);
            if (isBetter(key, bestKeySoFar) || isFirst) {
                bestSoFar = item;
                bestKeySoFar = key;
                isFirst = false;
            }
        },
        iterable);
    if (isFirst) {
        throw new Error('Tried to call best() on empty iterable');
    }
    return bestSoFar;
}

/**
 * Return the maximum item from an iterable, as defined by >.
 *
 * Works with any type that works with >. If multiple items are equally great,
 * return the first.
 *
 * @arg by {function} Given an item of the iterable, returns a value to
 *     compare
 */
function max(iterable, by = identity) {
    return best(iterable, by, (a, b) => a > b);
}

/**
 * Return an Array of maximum items from an iterable, as defined by > and ===.
 *
 * If an empty iterable is passed in, return [].
 */
function maxes(iterable, by = identity) {
    let bests = [];
    let bestKeySoFar;
    let isFirst = true;
    forEach(
        function (item) {
            const key = by(item);
            if (key > bestKeySoFar || isFirst) {
                bests = [item];
                bestKeySoFar = key;
                isFirst = false;
            } else if (key === bestKeySoFar) {
                bests.push(item);
            }
        },
        iterable);
    return bests;
}

/**
 * Return the minimum item from an iterable, as defined by <.
 *
 * If multiple items are equally great, return the first.
 */
function min(iterable, by = identity) {
    return best(iterable, by, (a, b) => a < b);
}

/**
 * Return the sum of an iterable, as defined by the + operator.
 */
function sum(iterable) {
    let total;
    let isFirst = true;
    forEach(
        function assignOrAdd(addend) {
            if (isFirst) {
                total = addend;
                isFirst = false;
            } else {
                total += addend;
            }
        },
        iterable);
    return total;
}

/**
 * Return the number of items in an iterable, consuming it as a side effect.
 */
function length(iterable) {
    let num = 0;
    // eslint-disable-next-line no-unused-vars
    for (let item of iterable) {
        num++;
    }
    return num;
}

/**
 * Iterate, depth first, over a DOM node. Return the original node first.
 *
 * @arg shouldTraverse {function} Given a node, say whether we should
 *     include it and its children. Default: always true.
 */
function *walk(element, shouldTraverse = element => true) {
    yield element;
    for (let child of element.childNodes) {
        if (shouldTraverse(child)) {
            for (let w of walk(child, shouldTraverse)) {
                yield w;
            }
        }
    }
}

const blockTags = new Set(
    ['ADDRESS', 'BLOCKQUOTE', 'BODY', 'CENTER', 'DIR', 'DIV', 'DL',
     'FIELDSET', 'FORM', 'H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'HR',
     'ISINDEX', 'MENU', 'NOFRAMES', 'NOSCRIPT', 'OL', 'P', 'PRE',
     'TABLE', 'UL', 'DD', 'DT', 'FRAMESET', 'LI', 'TBODY', 'TD',
     'TFOOT', 'TH', 'THEAD', 'TR', 'HTML']);
/**
 * Return whether a DOM element is a block element by default (rather than by
 * styling).
 */
function isBlock(element) {
    return blockTags.has(element.tagName);
}

/**
 * Yield strings of text nodes within a normalized DOM node and its children,
 * without venturing into any contained block elements.
 *
 * @arg shouldTraverse {function} Specify additional elements to exclude by
 *     returning false
 */
function *inlineTexts(element, shouldTraverse = element => true) {
    // TODO: Could we just use querySelectorAll() with a really long
    // selector rather than walk(), for speed?
    for (let child of walk(element,
                           element => !(isBlock(element) ||
                                        element.tagName === 'SCRIPT' &&
                                        element.tagName === 'STYLE')
                                      && shouldTraverse(element))) {
        if (child.nodeType === child.TEXT_NODE) {
            // wholeText() is not implemented by jsdom, so we use
            // textContent(). The result should be the same, since
            // we're calling it on only text nodes, but it may be
            // slower. On the positive side, it means we don't need to
            // normalize the DOM tree first.
            yield child.textContent;
        }
    }
}

/**
 * Return the total length of the inline text within an element, with
 * whitespace collapsed.
 *
 * @arg shouldTraverse {function} Specify additional elements to exclude by
 *     returning false
 */
function inlineTextLength(element, shouldTraverse = element => true) {
    return sum(map(text => collapseWhitespace(text).length,
                   inlineTexts(element, shouldTraverse)));
}

/**
 * Return a string with each run of whitespace collapsed to a single space.
 */
function collapseWhitespace(str) {
    return str.replace(/\s{2,}/g, ' ');
}

/**
 * Return the ratio of the inline text length of the links in an element to the
 * inline text length of the entire element.
 *
 * @arg inlineLength {number} Optionally, the precalculated inline
 *     length of the fnode. If omitted, we will calculate it ourselves.
 */
function linkDensity(fnode, inlineLength) {
    if (inlineLength === undefined) {
        inlineLength = inlineTextLength(fnode.element);
    }
    const lengthWithoutLinks = inlineTextLength(fnode.element,
                                                element => element.tagName !== 'A');
    return (inlineLength - lengthWithoutLinks) / inlineLength;
}

/**
 * Return whether an element is a text node that consist wholly of whitespace.
 */
function isWhitespace(element) {
    return (element.nodeType === element.TEXT_NODE &&
            element.textContent.trim().length === 0);
}

/**
 * Get a key of a map, first setting it to a default value if it's missing.
 */
function setDefault(map, key, defaultMaker) {
    if (map.has(key)) {
        return map.get(key);
    }
    const defaultValue = defaultMaker();
    map.set(key, defaultValue);
    return defaultValue;
}

/**
 * Get a key of a map or, if it's missing, a default value.
 */
function getDefault(map, key, defaultMaker) {
    if (map.has(key)) {
        return map.get(key);
    }
    return defaultMaker();
}

/**
 * Return an Array, the reverse topological sort of the given nodes.
 *
 * @arg nodes An iterable of arbitrary things
 * @arg nodesThatNeed {function} Take a node and returns an Array of nodes
 *     that depend on it
 */
function toposort(nodes, nodesThatNeed) {
    const ret = [];
    const todo = new Set(nodes);
    const inProgress = new Set();

    function visit(node) {
        if (inProgress.has(node)) {
            throw new CycleError('The graph has a cycle.');
        }
        if (todo.has(node)) {
            inProgress.add(node);
            for (let needer of nodesThatNeed(node)) {
                visit(needer);
            }
            inProgress.delete(node);
            todo.delete(node);
            ret.push(node);
        }
    }

    while (todo.size > 0) {
        visit(first(todo));
    }
    return ret;
}

/**
 * A Set with the additional methods it ought to have had
 */
class NiceSet extends Set {
    /**
     * Remove and return an arbitrary item. Throw an Error if I am empty.
     */
    pop() {
        for (let v of this.values()) {
            this.delete(v);
            return v;
        }
        throw new Error('Tried to pop from an empty NiceSet.');
    }

    /**
     * Union another set or other iterable into myself.
     *
     * @return myself, for chaining
     */
    extend(otherSet) {
        for (let item of otherSet) {
            this.add(item);
        }
        return this;
    }

    /**
     * Subtract another set from a copy of me.
     *
     * @return a copy of myself excluding the elements in ``otherSet``.
     */
    minus(otherSet) {
        const ret = new NiceSet(this);
        for (const item of otherSet) {
            ret.delete(item);
        }
        return ret;
    }

    /**
     * Actually show the items in me.
     */
    toString() {
        return '{' + Array.from(this).join(', ') + '}';
    }
}

/**
 * Return the first item of an iterable.
 */
function first(iterable) {
    for (let i of iterable) {
        return i;
    }
}

/**
 * Given any node in a DOM tree, return the root element of the tree, generally
 * an HTML element.
 */
function rootElement(element) {
    return element.ownerDocument.documentElement;
}

/**
 * Return the number of times a regex occurs within the string `haystack`.
 *
 * Caller must make sure `regex` has the 'g' option set.
 */
function numberOfMatches(regex, haystack) {
    return (haystack.match(regex) || []).length;
}

/**
 * Wrap a scoring callback, and set its element to the page root iff a score is
 * returned.
 *
 * This is used to build rulesets which classify entire pages rather than
 * picking out specific elements.
 *
 * For example, these rules might classify a page as a "login page", influenced
 * by whether they have login buttons or username fields:
 *
 * ``rule(type('loginPage'), score(page(pageContainsLoginButton))),``
 * ``rule(type('loginPage'), score(page(pageContainsUsernameField)))``
 */
function page(scoringFunction) {
    function wrapper(fnode) {
        const scoreAndTypeAndNote = scoringFunction(fnode);
        if (scoreAndTypeAndNote.score !== undefined) {
            scoreAndTypeAndNote.element = rootElement(fnode.element);
        }
        return scoreAndTypeAndNote;
    }
    return wrapper;
}

/**
 * Sort the elements by their position in the DOM.
 *
 * @arg fnodes {iterable} fnodes to sort
 * @return {Array} sorted fnodes
 */
function domSort(fnodes) {
    function compare(a, b) {
        const element = a.element;
        const position = element.compareDocumentPosition(b.element);
        if (position & element.DOCUMENT_POSITION_FOLLOWING) {
            return -1;
        } else if (position & element.DOCUMENT_POSITION_PRECEDING) {
            return 1;
        } else {
            return 0;
        }
    }
    return Array.from(fnodes).sort(compare);
}

/* istanbul ignore next */
/**
 * Return the DOM element contained in a passed-in fnode. Return passed-in DOM
 * elements verbatim.
 *
 * @arg fnodeOrElement {Node|Fnode}
 */
function toDomElement(fnodeOrElement) {
    return isDomElement(fnodeOrElement) ? fnodeOrElement : fnodeOrElement.element;
}

/**
 * Checks whether any of the element's attribute values satisfy some condition.
 *
 * Example::
 *
 *     rule(type('foo'),
 *          score(attributesMatch(element,
 *                                attr => attr.includes('good'),
 *                                ['id', 'alt']) ? 2 : 1))
 *
 * @arg element {Node} Element whose attributes you want to search
 * @arg predicate {function} A condition to check. Take a string and
 *     return a boolean. If an attribute has multiple values (e.g. the class
 *     attribute), attributesMatch will check each one.
 * @arg attrs {string[]} An Array of attributes you want to search. If none are
 *     provided, search all.
 * @return Whether any of the attribute values satisfy the predicate function
 */
function attributesMatch(element, predicate, attrs = []) {
    const attributes = attrs.length === 0 ? Array.from(element.attributes).map(a => a.name) : attrs;
    for (let i = 0; i < attributes.length; i++) {
        const attr = element.getAttribute(attributes[i]);
        // If the attribute is an array, apply the scoring function to each element
        if (attr && ((Array.isArray(attr) && attr.some(predicate)) || predicate(attr))) {
            return true;
        }
    }
    return false;
}

/* istanbul ignore next */
/**
 * Yield an element and each of its ancestors.
 */
function *ancestors(element) {
    yield element;
    let parent;
    while ((parent = element.parentNode) !== null && parent.nodeType === parent.ELEMENT_NODE) {
        yield parent;
        element = parent;
    }
}

/**
 * Return the sigmoid of the argument: 1 / (1 + exp(-x)). This is useful for
 * crunching a feature value that may have a wide range into the range (0, 1)
 * without a hard ceiling: the sigmoid of even a very large number will be a
 * little larger than that of a slightly smaller one.
 *
 * @arg x {Number} a number to be compressed into the range (0, 1)
 */
function sigmoid(x) {
    return 1 / (1 + Math.exp(-x));
}

/* istanbul ignore next */
/**
 * Return whether an element is practically visible, considering things like 0
 * size or opacity, ``visibility: hidden`` and ``overflow: hidden``.
 *
 * Merely being scrolled off the page in either horizontally or vertically
 * doesn't count as invisible; the result of this function is meant to be
 * independent of viewport size.
 *
 * @throws {NoWindowError} The element (or perhaps one of its ancestors) is not
 *     in a window, so we can't find the `getComputedStyle()` routine to call.
 *     That routine is the source of most of the information we use, so you
 *     should pick a different strategy for non-window contexts.
 */
function isVisible(fnodeOrElement) {
    // This could be 5x more efficient if https://github.com/w3c/csswg-drafts/issues/4122 happens.
    const element = toDomElement(fnodeOrElement);
    const elementWindow = windowForElement(element);
    const elementRect = element.getBoundingClientRect();
    const elementStyle = elementWindow.getComputedStyle(element);
    // Alternative to reading ``display: none`` due to Bug 1381071.
    if (elementRect.width === 0 && elementRect.height === 0 && elementStyle.overflow !== 'hidden') {
        return false;
    }
    if (elementStyle.visibility === 'hidden') {
        return false;
    }
    // Check if the element is irrevocably off-screen:
    if (elementRect.x + elementRect.width < 0 ||
        elementRect.y + elementRect.height < 0
    ) {
        return false;
    }
    for (const ancestor of ancestors(element)) {
        const isElement = ancestor === element;
        const style = isElement ? elementStyle : elementWindow.getComputedStyle(ancestor);
        if (style.opacity === '0') {
            return false;
        }
        if (style.display === 'contents') {
            // ``display: contents`` elements have no box themselves, but children are
            // still rendered.
            continue;
        }
        const rect = isElement ? elementRect : ancestor.getBoundingClientRect();
        if ((rect.width === 0 || rect.height === 0) && elementStyle.overflow === 'hidden') {
            // Zero-sized ancestors don’t make descendants hidden unless the descendant
            // has ``overflow: hidden``.
            return false;
        }
    }
    return true;
}

/**
 * Return the extracted [r, g, b, a] values from a string like "rgba(0, 5, 255, 0.8)",
 * and scale them to 0..1. If no alpha is specified, return undefined for it.
 */
function rgbaFromString(str) {
    const m = str.match(/^rgba?\s*\(\s*(\d+)\s*,\s*(\d+)\s*,\s*(\d+)\s*(?:,\s*(\d+(?:\.\d+)?)\s*)?\)$/i);
    if (m) {
        return [m[1] / 255, m[2] / 255, m[3] / 255, m[4] === undefined ? undefined : parseFloat(m[4])];
    } else {
        throw new Error('Color ' + str + ' did not match pattern rgb[a](r, g, b[, a]).');
    }
}

/**
 * Return the saturation 0..1 of a color defined by RGB values 0..1.
 */
function saturation(r, g, b) {
    const cMax = Math.max(r, g, b);
    const cMin = Math.min(r, g, b);
    const delta = cMax - cMin;
    const lightness = (cMax + cMin) / 2;
    const denom = (1 - (Math.abs(2 * lightness - 1)));
    // Return 0 if it's black (R, G, and B all 0).
    return (denom === 0) ? 0 : delta / denom;
}

/**
 * Scale a number to the range [0, 1] using a linear slope.
 *
 * For a rising line, the result is 0 until the input reaches zeroAt, then
 * increases linearly until oneAt, at which it becomes 1. To make a falling
 * line, where the result is 1 to the left and 0 to the right, use a zeroAt
 * greater than oneAt.
 */
function linearScale(number, zeroAt, oneAt) {
    const isRising = zeroAt < oneAt;
    if (isRising) {
        if (number <= zeroAt) {
            return 0;
        } else if (number >= oneAt) {
            return 1;
        }
    } else {
        if (number >= zeroAt) {
            return 0;
        } else if (number <= oneAt) {
            return 1;
        }
    }
    const slope = 1 / (oneAt - zeroAt);
    return slope * (number - zeroAt);
}

// -------- Routines below this point are private to the framework. --------

/**
 * Flatten out an iterable of iterables into a single iterable of non-
 * iterables. Does not consider strings to be iterable.
 */
function *flatten(iterable) {
    for (const i of iterable) {
        if (typeof i !== 'string' && isIterable(i)) {
            yield *(flatten(i));
        } else {
            yield i;
        }
    }
}

/**
 * A lazy, top-level ``Array.map()`` workalike that works on anything iterable
 */
function *map(fn, iterable) {
    for (const i of iterable) {
        yield fn(i);
    }
}

/**
 * A lazy, top-level ``Array.forEach()`` workalike that works on anything
 * iterable
 */
function forEach(fn, iterable) {
    for (const i of iterable) {
        fn(i);
    }
}

/* istanbul ignore next */
/**
 * @return whether a thing appears to be a DOM element.
 */
function isDomElement(thing) {
    return thing.nodeName !== undefined;
}

function isIterable(thing) {
    return thing && typeof thing[Symbol.iterator] === 'function';
}

/**
 * Return an backward iterator over an Array without reversing it in place.
 */
function *reversed(array) {
    for (let i = array.length - 1; i >= 0; i--) {
        yield array[i];
    }
}

/* istanbul ignore next */
/*
 * Return the window an element is in.
 *
 * @throws {NoWindowError} There isn't such a window.
 */
function windowForElement(element) {
    let doc = element.ownerDocument;
    if (doc === null) {
        // The element itself was a document.
        doc = element;
    }
    const win = doc.defaultView;
    if (win === null) {
        throw new NoWindowError();
    }
    return win;
}

var utilsForFrontend = /*#__PURE__*/Object.freeze({
  __proto__: null,
  identity: identity,
  best: best,
  max: max,
  maxes: maxes,
  min: min,
  sum: sum,
  length: length,
  walk: walk,
  isBlock: isBlock,
  inlineTexts: inlineTexts,
  inlineTextLength: inlineTextLength,
  collapseWhitespace: collapseWhitespace,
  linkDensity: linkDensity,
  isWhitespace: isWhitespace,
  setDefault: setDefault,
  getDefault: getDefault,
  toposort: toposort,
  NiceSet: NiceSet,
  first: first,
  rootElement: rootElement,
  numberOfMatches: numberOfMatches,
  page: page,
  domSort: domSort,
  toDomElement: toDomElement,
  attributesMatch: attributesMatch,
  ancestors: ancestors,
  sigmoid: sigmoid,
  isVisible: isVisible,
  rgbaFromString: rgbaFromString,
  saturation: saturation,
  linearScale: linearScale,
  flatten: flatten,
  map: map,
  forEach: forEach,
  isDomElement: isDomElement,
  reversed: reversed,
  windowForElement: windowForElement
});

/**
 * Return the number of stride nodes between 2 DOM nodes *at the same
 * level of the tree*, without going up or down the tree.
 *
 * ``left`` xor ``right`` may also be undefined.
 */
function numStrides(left, right) {
    let num = 0;

    // Walk right from left node until we hit the right node or run out:
    let sibling = left;
    let shouldContinue = sibling && sibling !== right;
    while (shouldContinue) {
        sibling = sibling.nextSibling;
        if ((shouldContinue = sibling && sibling !== right) &&
            !isWhitespace(sibling)) {
            num += 1;
        }
    }
    if (sibling !== right) {  // Don't double-punish if left and right are siblings.
        // Walk left from right node:
        sibling = right;
        while (sibling) {
            sibling = sibling.previousSibling;
            if (sibling && !isWhitespace(sibling)) {
                num += 1;
            }
        }
    }
    return num;
}

/**
 * Return a topological distance between 2 DOM nodes or :term:`fnodes<fnode>`
 * weighted according to the similarity of their ancestry in the DOM. For
 * instance, if one node is situated inside ``<div><span><b><theNode>`` and the
 * other node is at ``<differentDiv><span><b><otherNode>``, they are considered
 * close to each other for clustering purposes. This is useful for picking out
 * nodes which have similar purposes.
 *
 * Return ``Number.MAX_VALUE`` if one of the nodes contains the other.
 *
 * This is largely an implementation detail of :func:`clusters`, but you can
 * call it yourself if you wish to implement your own clustering. Takes O(n log
 * n) time.
 *
 * Note that the default costs may change; pass them in explicitly if they are
 * important to you.
 *
 * @arg fnodeA {Node|Fnode}
 * @arg fnodeB {Node|Fnode}
 * @arg differentDepthCost {number} Cost for each level deeper one node is than
 *    the other below their common ancestor
 * @arg differentTagCost {number} Cost for a level below the common ancestor
 *    where tagNames differ
 * @arg sameTagCost {number} Cost for a level below the common ancestor where
 *    tagNames are the same
 * @arg strideCost {number} Cost for each stride node between A and B. Stride
 *     nodes are siblings or siblings-of-ancestors that lie between the 2
 *     nodes. These interposed nodes make it less likely that the 2 nodes
 *     should be together in a cluster.
 * @arg additionalCost {function} Return an additional cost, given 2 fnodes or
 *    nodes.
 *
 */
function distance(fnodeA,
                         fnodeB,
                         {differentDepthCost = 2,
                          differentTagCost = 2,
                          sameTagCost = 1,
                          strideCost = 1,
                          additionalCost = (fnodeA, fnodeB) => 0} = {}) {
    // I was thinking of something that adds little cost for siblings. Up
    // should probably be more expensive than down (see middle example in the
    // Nokia paper).

    // TODO: Test and tune default costs. They're off the cuff at the moment.

    if (fnodeA === fnodeB) {
        return 0;
    }

    const elementA = isDomElement(fnodeA) ? fnodeA : fnodeA.element;
    const elementB = isDomElement(fnodeB) ? fnodeB : fnodeB.element;

    // Stacks that go from the common ancestor all the way to A and B:
    const aAncestors = [elementA];
    const bAncestors = [elementB];

    let aAncestor = elementA;
    let bAncestor = elementB;

    // Ascend to common parent, stacking them up for later reference:
    while (!aAncestor.contains(elementB)) {  // Note: an element does contain() itself.
        aAncestor = aAncestor.parentNode;
        aAncestors.push(aAncestor); //aAncestors = [a, b]. aAncestor = b // if a is outer: no loop here; aAncestors = [a]. aAncestor = a.
    }

    // In compareDocumentPosition()'s opinion, inside implies after. Basically,
    // before and after pertain to opening tags.
    const comparison = elementA.compareDocumentPosition(elementB);

    // If either contains the other, abort. We'd either return a misleading
    // number or else walk upward right out of the document while trying to
    // make the ancestor stack.
    if (comparison & (elementA.DOCUMENT_POSITION_CONTAINS | elementA.DOCUMENT_POSITION_CONTAINED_BY)) {
        return Number.MAX_VALUE;
    }
    // Make an ancestor stack for the right node too so we can walk
    // efficiently down to it:
    do {
        bAncestor = bAncestor.parentNode;  // Assumes we've early-returned above if A === B. This walks upward from the outer node and up out of the tree. It STARTS OUT with aAncestor === bAncestor!
        bAncestors.push(bAncestor);
    } while (bAncestor !== aAncestor);

    // Figure out which node is left and which is right, so we can follow
    // sibling links in the appropriate directions when looking for stride
    // nodes:
    let left = aAncestors;
    let right = bAncestors;
    let cost = 0;
    if (comparison & elementA.DOCUMENT_POSITION_FOLLOWING) {
        // A is before, so it could contain the other node. What did I mean to do if one contained the other?
        left = aAncestors;
        right = bAncestors;
    } else if (comparison & elementA.DOCUMENT_POSITION_PRECEDING) {
        // A is after, so it might be contained by the other node.
        left = bAncestors;
        right = aAncestors;
    }

    // Descend to both nodes in parallel, discounting the traversal
    // cost iff the nodes we hit look similar, implying the nodes dwell
    // within similar structures.
    while (left.length || right.length) {
        const l = left.pop();
        const r = right.pop();
        if (l === undefined || r === undefined) {
            // Punishment for being at different depths: same as ordinary
            // dissimilarity punishment for now
            cost += differentDepthCost;
        } else {
            // TODO: Consider similarity of classList.
            cost += l.tagName === r.tagName ? sameTagCost : differentTagCost;
        }
        // Optimization: strides might be a good dimension to eliminate.
        if (strideCost !== 0) {
            cost += numStrides(l, r) * strideCost;
        }
    }

    return cost + additionalCost(fnodeA, fnodeB);
}

/**
 * Return the spatial distance between 2 fnodes or elements, assuming a
 * rendered page.
 *
 * Specifically, return the distance in pixels between the centers of
 * ``fnodeA.element.getBoundingClientRect()`` and
 * ``fnodeB.element.getBoundingClientRect()``.
 */
function euclidean(fnodeA, fnodeB) {
    /**
     * Return the horizontal distance from the left edge of the viewport to the
     * center of an element, given a DOMRect object for it. It doesn't matter
     * that the distance is affected by the page's scroll offset, since the 2
     * elements have the same offset.
     */
    function xCenter(domRect) {
        return domRect.left + domRect.width / 2;
    }
    function yCenter(domRect) {
        return domRect.top + domRect.height / 2;
    }

    const elementA = toDomElement(fnodeA);
    const elementB = toDomElement(fnodeB);
    const aRect = elementA.getBoundingClientRect();
    const bRect = elementB.getBoundingClientRect();
    return Math.sqrt((xCenter(aRect) - xCenter(bRect)) ** 2 +
                     (yCenter(aRect) - yCenter(bRect)) ** 2);
}

/** A lower-triangular matrix of inter-cluster distances */
class DistanceMatrix {
    /**
     * @arg distance {function} Some notion of distance between 2 given nodes
     */
    constructor(elements, distance) {
        // A sparse adjacency matrix:
        // {A => {},
        //  B => {A => 4},
        //  C => {A => 4, B => 4},
        //  D => {A => 4, B => 4, C => 4}
        //  E => {A => 4, B => 4, C => 4, D => 4}}
        //
        // A, B, etc. are arrays of [arrays of arrays of...] nodes, each
        // array being a cluster. In this way, they not only accumulate a
        // cluster but retain the steps along the way.
        //
        // This is an efficient data structure in terms of CPU and memory, in
        // that we don't have to slide a lot of memory around when we delete a
        // row or column from the middle of the matrix while merging. Of
        // course, we lose some practical efficiency by using hash tables, and
        // maps in particular are slow in their early implementations.
        this._matrix = new Map();

        // Convert elements to clusters:
        const clusters = elements.map(el => [el]);

        // Init matrix:
        for (let outerCluster of clusters) {
            const innerMap = new Map();
            for (let innerCluster of this._matrix.keys()) {
                innerMap.set(innerCluster, distance(outerCluster[0],
                                                    innerCluster[0]));
            }
            this._matrix.set(outerCluster, innerMap);
        }
        this._numClusters = clusters.length;
    }

    // Return (distance, a: clusterA, b: clusterB) of closest-together clusters.
    // Replace this to change linkage criterion.
    closest() {
        const self = this;

        if (this._numClusters < 2) {
            throw new Error('There must be at least 2 clusters in order to return the closest() ones.');
        }

        // Return the distances between every pair of clusters.
        function clustersAndDistances() {
            const ret = [];
            for (let [outerKey, row] of self._matrix.entries()) {
                for (let [innerKey, storedDistance] of row.entries()) {
                    ret.push({a: outerKey, b: innerKey, distance: storedDistance});
                }
            }
            return ret;
        }
        // Optimizing this by inlining the loop and writing it less
        // functionally doesn't help:
        return min(clustersAndDistances(), x => x.distance);
    }

    // Look up the distance between 2 clusters in me. Try the lookup in the
    // other direction if the first one falls in the nonexistent half of the
    // triangle.
    _cachedDistance(clusterA, clusterB) {
        let ret = this._matrix.get(clusterA).get(clusterB);
        if (ret === undefined) {
            ret = this._matrix.get(clusterB).get(clusterA);
        }
        return ret;
    }

    // Merge two clusters.
    merge(clusterA, clusterB) {
        // An example showing how rows merge:
        //  A: {}
        //  B: {A: 1}
        //  C: {A: 4, B: 4},
        //  D: {A: 4, B: 4, C: 4}
        //  E: {A: 4, B: 4, C: 2, D: 4}}
        //
        // Step 2:
        //  C: {}
        //  D: {C: 4}
        //  E: {C: 2, D: 4}}
        //  AB: {C: 4, D: 4, E: 4}
        //
        // Step 3:
        //  D:  {}
        //  AB: {D: 4}
        //  CE: {D: 4, AB: 4}

        // Construct new row, finding min distances from either subcluster of
        // the new cluster to old clusters.
        //
        // There will be no repetition in the matrix because, after all,
        // nothing pointed to this new cluster before it existed.
        const newRow = new Map();
        for (let outerKey of this._matrix.keys()) {
            if (outerKey !== clusterA && outerKey !== clusterB) {
                newRow.set(outerKey, Math.min(this._cachedDistance(clusterA, outerKey),
                                              this._cachedDistance(clusterB, outerKey)));
            }
        }

        // Delete the rows of the clusters we're merging.
        this._matrix.delete(clusterA);
        this._matrix.delete(clusterB);

        // Remove inner refs to the clusters we're merging.
        for (let inner of this._matrix.values()) {
            inner.delete(clusterA);
            inner.delete(clusterB);
        }

        // Attach new row.
        this._matrix.set([clusterA, clusterB], newRow);

        // There is a net decrease of 1 cluster:
        this._numClusters -= 1;
    }

    numClusters() {
        return this._numClusters;
    }

    // Return an Array of nodes for each cluster in me.
    clusters() {
        // TODO: Can't get map to work here. Don't know why.
        return Array.from(this._matrix.keys()).map(e => Array.from(flatten(e)));
    }
}

/**
 * Partition the given nodes into one or more clusters by position in the DOM
 * tree.
 *
 * This implements an agglomerative clustering. It uses single linkage, since
 * we're talking about adjacency here more than Euclidean proximity: the
 * clusters we're talking about in the DOM will tend to be adjacent, not
 * overlapping. We haven't tried other linkage criteria yet.
 *
 * In a later release, we may consider score or notes.
 *
 * @arg {Fnode[]|Node[]} fnodes :term:`fnodes<fnode>` or DOM nodes to group
 *     into clusters
 * @arg {number} splittingDistance The closest-nodes :func:`distance` beyond
 *     which we will not attempt to unify 2 clusters. Make this larger to make
 *     larger clusters.
 * @arg getDistance {function} A function that returns some notion of numerical
 *    distance between 2 nodes. Default: :func:`distance`
 * @return {Array} An Array of Arrays, with each Array containing all the
 *     nodes in one cluster. Note that neither the clusters nor the nodes are
 *     in any particular order. You may find :func:`domSort` helpful to remedy
 *     the latter.
 */
function clusters(fnodes, splittingDistance, getDistance = distance) {
    const matrix = new DistanceMatrix(fnodes, getDistance);
    let closest;

    while (matrix.numClusters() > 1 && (closest = matrix.closest()).distance < splittingDistance) {
        matrix.merge(closest.a, closest.b);
    }

    return matrix.clusters();
}

var clusters$1 = /*#__PURE__*/Object.freeze({
  __proto__: null,
  distance: distance,
  euclidean: euclidean,
  clusters: clusters
});

// The left-hand side of a rule


/**
 * Take nodes that match a given DOM selector. Example:
 * ``dom('meta[property="og:title"]')``
 *
 * Every ruleset has at least one ``dom`` or :func:`element` rule, as that is
 * where nodes begin to flow into the system. If run against a subtree of a
 * document, the root of the subtree is not considered as a possible match.
 */
function dom(selector) {
    return new DomLhs(selector);
}

/**
 * Take a single given node if it matches a given DOM selector, without looking
 * through its descendents or ancestors. Otherwise, take no nodes. Example:
 * ``element('input')``
 *
 * This is useful for applications in which you want Fathom to classify an
 * element the user has selected, rather than scanning the whole page for
 * candidates.
 */
function element(selector) {
    return new ElementLhs(selector);
}

/**
 * Rules and the LHSs and RHSs that comprise them have no mutable state. This
 * lets us make BoundRulesets from Rulesets without duplicating the rules. It
 * also lets us share a common cache among rules: multiple ones might care
 * about a cached type(), for instance; there isn't a one-to-one relationship
 * of storing with caring. There would also, because of the interdependencies
 * of rules in a ruleset, be little use in segmenting the caches: if you do
 * something that causes one to need to be cleared, you'll need to clear many
 * more as well.
 *
 * Lhses are responsible for maintaining ruleset.maxCache.
 *
 * Lhs and its subclasses are private to the Fathom framework.
 */
class Lhs {
    constructor() {
        this._predicate = () => true;
    }

    /** Return a new Lhs of the appropriate kind, given its first call. */
    static fromFirstCall(firstCall) {
        // firstCall is never 'dom', because dom() directly returns a DomLhs.
        if (firstCall.method === 'type') {
            return new TypeLhs(...firstCall.args);
        } else if (firstCall.method === 'and') {
            return new AndLhs(firstCall.args);
        } else if (firstCall.method === 'nearest') {
            return new NearestLhs(firstCall.args);
        } else {
            throw new Error('The left-hand side of a rule() must start with dom(), type(), and(), or nearest().');
        }
    }

    /**
     * Prune nodes from consideration early in run execution, before scoring is
     * done.
     *
     * Reserve this for where you are sure it is always correct or when
     * performance demands it. It is generally preferable to use :func:`score`
     * and let the :doc:`trainer<training>` determine the relative significance
     * of each rule. Human intuition as to what is important is often wrong:
     * for example, one might assume that a music player website would include
     * the word "play", but this does not hold once you include sites in other
     * languages.
     *
     * Can be chained after :func:`type` or :func:`dom`.
     *
     * Example: ``dom('p').when(isVisible)``
     *
     * @arg {function} predicate Accepts a fnode and returns a boolean
     */
    when(predicate) {
        let lhs = this.clone();
        lhs._predicate = predicate;
        return lhs;
    }

    /**
     * Of all the dom nodes selected by type() or dom(), return only
     * the fnodes that satisfy all the predicates imposed by calls to
     * when()
     */
    fnodesSatisfyingWhen(fnodes) {
        return Array.from(fnodes).filter(this._predicate);
    }

    /**
     * Return an iterable of output fnodes selected by this left-hand-side
     * expression.
     *
     * Pre: The rules I depend on have already been run, and their results are
     * in ruleset.typeCache.
     *
     * @arg ruleset {BoundRuleset}
     */
    // fnodes (ruleset) {}

    /**
     * Check that a RHS-emitted fact is legal for this kind of LHS, and throw
     * an error if it isn't.
     */
    checkFact(fact) {}

    /**
     * Return the single type the output of the LHS is guaranteed to have.
     * Return undefined if there is no such single type we can ascertain.
     */
    guaranteedType() {}

    /**
     * Return the type I aggregate if I am an aggregate LHS; return undefined
     * otherwise.
     */
    aggregatedType() {}

    /**
     * Return each combination of types my selected nodes could be locally (that
     * is, by this rule only) constrained to have.
     *
     * For example, type(A) would return [A]. and(A, or(B, C)) would return
     * [AB, AC, ABC]. More examples:
     *
     * or(A, B) → typeIn(A, B, C)  # Finalizes A, B.   combos A, B, AB: finalizes AB. Optimization: there's no point in returning the last combo in ors. Compilation into 2 rules with identical RHSs will inherently implement this optimization.
     * or(A, B) → typeIn(A, B)  # Finalizes A, B
     * or(A, B) → A  # Finalizes B
     * and(A) -> A  # Finalizes nothing
     * and(A, B) -> A  # Finalizes nothing.   AB: Ø
     * and(A) -> typeIn(A, B)  # Finalizes A.   A
     * and(A, B) -> typeIn(A, B)  # Finalizes nothing.   AB
     * and(A, B) -> typeIn(A, B, C)  # Finalizes A, B.   AB
     * and(A, or(B, C)) -> D  # Finalizes A, B, C.   AB, AC, ABC: ABC
     * and(A, or(B, C)) -> B  # Finalizes A, C.   AB, AC, ABC: AC
     * type(A).not(and(A, B)) ->
     *
     * @return {NiceSet[]}
     */
    // possibleTypeCombinations() {}

    /**
     * Types mentioned in this LHS.
     *
     * In other words, the types I need to know the assignment status of before
     * I can make my selections
     *
     * @return NiceSet of strings
     */
    // typesMentioned() {}
}

class DomLhs extends Lhs {
    constructor(selector) {
        super();
        if (selector === undefined) {
            throw new Error('A querySelector()-style selector is required as the argument to ' + this._callName() + '().');
        }
        this.selector = selector;
    }

    /**
     * Return the name of this kind of LHS, for use in error messages.
     */
    _callName() {
        return 'dom';
    }

    clone() {
        return new this.constructor(this.selector);
    }

    fnodes(ruleset) {
        return this._domNodesToFilteredFnodes(
            ruleset,
            ruleset.doc.querySelectorAll(this.selector));
    }

    /**
     * Turn a NodeList of DOM nodes into an array of fnodes, and filter out
     * those that don't match the :func:`when()` clause.
     */
    _domNodesToFilteredFnodes(ruleset, domNodes) {
        let ret = [];
        for (let i = 0; i < domNodes.length; i++) {
            ret.push(ruleset.fnodeForElement(domNodes[i]));
        }
        return this.fnodesSatisfyingWhen(ret);
    }

    checkFact(fact) {
        if (fact.type === undefined) {
            throw new Error(`The right-hand side of a ${this._callName()}() rule failed to specify a type. This means there is no way for its output to be used by later rules. All it specified was ${fact}.`);
        }
    }

    asLhs() {
        return this;
    }

    possibleTypeCombinations() {
        return [];
    }

    typesMentioned() {
        return new NiceSet();
    }
}

class ElementLhs extends DomLhs {
    _callName() {
        return 'element';
    }

    fnodes(ruleset) {
        return this._domNodesToFilteredFnodes(
            ruleset,
            ruleset.doc.matches(this.selector) ? [ruleset.doc] : []);
    }
}

/** Internal representation of a LHS constrained by type but not by max() */
class TypeLhs extends Lhs {
    constructor(type) {
        super();
        if (type === undefined) {
            throw new Error('A type name is required when calling type().');
        }
        this._type = type;  // the input type
    }

    clone() {
        return new this.constructor(this._type);
    }

    fnodes(ruleset) {
        const cached = getDefault(ruleset.typeCache, this._type, () => []);
        return this.fnodesSatisfyingWhen(cached);
    }

    /** Override the type previously specified by this constraint. */
    type(inputType) {
        // Preserve the class in case this is a TypeMaxLhs.
        return new this.constructor(inputType);
    }

    /**
     * Of the nodes selected by a ``type`` call to the left, constrain the LHS
     * to return only the max-scoring one. If there is a tie, more than 1 node
     * will be returned. Example: ``type('titley').max()``
     */
    max() {
        return new TypeMaxLhs(this._type);
    }

    /**
     * Take the nodes selected by a ``type`` call to the left, group them into
     * clusters, and return the nodes in the cluster that has the highest total
     * score (on the relevant type).
     *
     * Nodes come out in arbitrary order, so, if you plan to emit them,
     * consider using ``.out('whatever').allThrough(domSort)``. See
     * :func:`domSort`.
     *
     * If multiple clusters have equally high scores, return an arbitrary one,
     * because Fathom has no way to represent arrays of arrays in rulesets.
     *
     * @arg options {Object} The same depth costs taken by :func:`distance`,
     *     plus ``splittingDistance``, which is the distance beyond which 2
     *     clusters will be considered separate. ``splittingDistance``, if
     *     omitted, defaults to 3.
     */
    bestCluster(options) {
        return new BestClusterLhs(this._type, options);
    }

    // Other clustering calls could be called biggestCluster() (having the most
    // nodes) and bestAverageCluster() (having the highest average score).

    guaranteedType() {
        return this._type;
    }

    possibleTypeCombinations() {
        return [this.typesMentioned()];
    }

    typesMentioned() {
        return new NiceSet([this._type]);
    }
}

/**
 * Abstract LHS that is an aggregate function taken across all fnodes of a type
 *
 * The main point here is that any aggregate function over a (typed) set of
 * nodes depends on first computing all the rules that could emit those nodes
 * (nodes of that type).
 */
class AggregateTypeLhs extends TypeLhs {
    aggregatedType() {
        return this._type;
    }
}

/**
 * Internal representation of a LHS that has both type and max([NUMBER])
 * constraints. max(NUMBER != 1) support is not yet implemented.
 */
class TypeMaxLhs extends AggregateTypeLhs {
    /**
     * Return the max-scoring node (or nodes if there is a tie) of the given
     * type.
     */
    fnodes(ruleset) {
        // TODO: Optimize better. Walk the dependency tree, and run only the
        // rules that could possibly lead to a max result. As part of this,
        // make RHSs expose their max potential scores.
        const self = this;
        // Work around V8 bug:
        // https://stackoverflow.com/questions/32943776/using-super-within-an-
        // arrow-function-within-an-arrow-function-within-a-method
        const getSuperFnodes = () => super.fnodes(ruleset);
        return setDefault(
            ruleset.maxCache,
            this._type,
            function maxFnodesOfType() {
                return maxes(getSuperFnodes(), fnode => ruleset.weightedScore(fnode.scoresSoFarFor(self._type)));
            });
    }
}

class BestClusterLhs extends AggregateTypeLhs {
    constructor(type, options) {
        super(type);
        this._options = options || {splittingDistance: 3};
    }

    /**
     * Group the nodes of my type into clusters, and return the cluster with
     * the highest total score for that type.
     */
    fnodes(ruleset) {
        // Get the nodes of the type:
        const fnodesOfType = Array.from(super.fnodes(ruleset));
        if (fnodesOfType.length === 0) {
            return [];
        }
        // Cluster them:
        const clusts = clusters(
            fnodesOfType,
            this._options.splittingDistance,
            (a, b) => distance(a, b, this._options));
        // Tag each cluster with the total of its nodes' scores:
        const clustsAndSums = clusts.map(
            clust => [clust,
                      sum(clust.map(fnode => fnode.scoreFor(this._type)))]);
        // Return the highest-scoring cluster:
        return max(clustsAndSums, clustAndSum => clustAndSum[1])[0];
    }
}

class AndLhs extends Lhs {
    constructor(lhss) {
        super();

        // For the moment, we accept only type()s as args. TODO: Generalize to
        // type().max() and such later.
        this._args = lhss.map(sideToTypeLhs);
    }

    *fnodes(ruleset) {
        // Take an arbitrary one for starters. Optimization: we could always
        // choose the pickiest one to start with.
        const fnodes = this._args[0].fnodes(ruleset);
        // Then keep only the fnodes that have the type of every other arg:
        fnodeLoop: for (let fnode of fnodes) {
            for (let otherLhs of this._args.slice(1)) {
                // Optimization: could use a .hasTypeSoFar() below
                if (!fnode.hasType(otherLhs.guaranteedType())) {
                    // TODO: This is n^2. Why is there no set intersection in JS?!
                    continue fnodeLoop;
                }
            }
            yield fnode;
        }
    }

    possibleTypeCombinations() {
        return [this.typesMentioned()];
    }

    typesMentioned() {
        return new NiceSet(this._args.map(arg => arg.guaranteedType()));
    }
}

function sideToTypeLhs(side) {
    const lhs = side.asLhs();
    if (!(lhs.constructor === TypeLhs)) {
        throw new Error('and() and nearest() support only simple type() calls as arguments for now.');
        // TODO: Though we could solve this with a compilation step: and(type(A), type(B).max()) is equivalent to type(B).max() -> type(Bmax); and(type(A), type(Bmax)).
        // In fact, we should be able to compile most (any?) arbitrary and()s, including nested ands and and(type(...).max(), ...) constructions into several and(type(A), type(B), ...) rules.
    }
    return lhs;
}

class NearestLhs extends Lhs {
    constructor([a, b, distance]) {
        super();
        this._a = sideToTypeLhs(a);
        this._b = sideToTypeLhs(b);
        this._distance = distance;
    }

    /**
     * Return an iterable of {fnodes, transformer} pairs.
     */
    *fnodes(ruleset) {
        // Go through all the left arg's nodes. For each one, find the closest
        // right-arg's node. O(a * b). Once a right-arg's node is used, we
        // don't eliminate it from consideration, because then order of left-
        // args' nodes would matter.

        // TODO: Still not sure how to get the distance to factor into the
        // score unless we hard-code nearest() to do that. It's a
        // matter of not being able to bind on the RHS to the output of the
        // distance function on the LHS. Perhaps we could at least make
        // distance part of the note and read it in a props() callback.

        // We're assuming here that simple type() calls return just plain
        // fnodes, not {fnode, rhsTransformer} pairs:
        const as_ = this._a.fnodes(ruleset);
        const bs = Array.from(this._b.fnodes(ruleset));
        if (bs.length > 0) {
            // If bs is empty, there can be no nearest nodes, so don't emit any.
            for (const a of as_) {
                const nearest = min(bs, b => this._distance(a, b));
                yield {fnode: a,
                       rhsTransformer: function setNoteIfEmpty(fact) {
                           // If note is explicitly set by the RHS, let it take
                           // precedence, even though that makes this entire LHS
                           // pointless.
                           if (fact.note === undefined) {
                               fact.note = nearest;  // TODO: Wrap this in an object to make room to return distance later.
                           }
                           return fact;
                       }};
            }
        }
    }

    checkFact(fact) {
        // Barf if the fact doesn't set a type at least. It should be a *new* type or at least one that doesn't result in cycles, but we can't deduce that.
    }

    possibleTypeCombinations() {
        return [new NiceSet([this._a.guaranteedType()])];
    }

    typesMentioned() {
        return new NiceSet([this._a.guaranteedType(),
                            this._b.guaranteedType()]);
    }

    guaranteedType() {
        return this._a.guaranteedType();
    }
}

// The right-hand side of a rule


const TYPE = 1;
const NOTE = 2;
const SCORE = 4;
const ELEMENT = 8;
const SUBFACTS = {
    type: TYPE,
    note: NOTE,
    score: SCORE,
    element: ELEMENT
};

/**
 * Expose the output of this rule's LHS as a "final result" to the surrounding
 * program. It will be available by calling :func:`~BoundRuleset.get` on the
 * ruleset and passing the key. You can run each node through a callback
 * function first by adding :func:`through()`, or you can run the entire set of
 * nodes through a callback function by adding :func:`allThrough()`.
 */
function out(key) {
    return new OutwardRhs(key);
}

class InwardRhs {
    constructor(calls = [], max = Infinity, types) {
        this._calls = calls.slice();
        this._max = max;  // max score
        this._types = new NiceSet(types);  // empty set if unconstrained
    }

    /**
     * Declare that the maximum returned subscore is such and such,
     * which helps the optimizer plan efficiently. This doesn't force it to be
     * true; it merely throws an error at runtime if it isn't. To lift an
     * ``atMost`` constraint, call ``atMost()`` (with no args). The reason
     * ``atMost`` and ``typeIn`` apply until explicitly cleared is so that, if
     * someone used them for safety reasons on a lexically distant rule you are
     * extending, you won't stomp on their constraint and break their
     * invariants accidentally.
     */
    atMost(score) {
        return new this.constructor(this._calls, score, this._types);
    }

    _checkAtMost(fact) {
        if (fact.score !== undefined && fact.score > this._max) {
            throw new Error(`Score of ${fact.score} exceeds the declared atMost(${this._max}).`);
        }
    }

    /**
      * Determine any of type, note, score, and element using a callback. This
      * overrides any previous call to `props` and, depending on what
      * properties of the callback's return value are filled out, may override
      * the effects of other previous calls as well.
      *
      * The callback should return...
      *
      * * An optional :term:`subscore`
      * * A type (required on ``dom(...)`` rules, defaulting to the input one on
      *   ``type(...)`` rules)
      * * Optional notes
      * * An element, defaulting to the input one. Overriding the default
      *   enables a callback to walk around the tree and say things about nodes
      *   other than the input one.
      */
    props(callback) {
        function getSubfacts(fnode) {
            const subfacts = callback(fnode);
            // Filter the raw result down to okayed properties so callbacks
            // can't insert arbitrary keys (like conserveScore, which might
            // mess up the optimizer).
            for (let subfact in subfacts) {
                if (!SUBFACTS.hasOwnProperty(subfact) || !(SUBFACTS[subfact] & getSubfacts.possibleSubfacts)) {
                    // The ES5.1 spec says in 12.6.4 that it's fine to delete
                    // as we iterate.
                    delete subfacts[subfact];
                }
            }
            return subfacts;
        }
        // Thse are the subfacts this call could affect:
        getSubfacts.possibleSubfacts = TYPE | NOTE | SCORE | ELEMENT;
        getSubfacts.kind = 'props';
        return new this.constructor(this._calls.concat(getSubfacts),
                                    this._max,
                                    this._types);
    }

    /**
     * Set the type applied to fnodes processed by this RHS.
     */
    type(theType) {
        // In the future, we might also support providing a callback that receives
        // the fnode and returns a type. We couldn't reason based on these, but the
        // use would be rather a consise way to to override part of what a previous
        // .props() call provides.

        // Actually emit a given type.
        function getSubfacts() {
            return {type: theType};
        }
        getSubfacts.possibleSubfacts = TYPE;
        getSubfacts.type = theType;
        getSubfacts.kind = 'type';
        return new this.constructor(this._calls.concat(getSubfacts),
                                    this._max,
                                    this._types);
    }

    /**
     * Constrain this rule to emit 1 of a set of given types. Pass no args to lift
     * a previous ``typeIn`` constraint, as you might do when basing a LHS on a
     * common value to factor out repetition.
     *
     * ``typeIn`` is mostly a hint for the query planner when you're emitting types
     * dynamically from ``props`` calls—in fact, an error will be raised if
     * ``props`` is used without a ``typeIn`` or ``type`` to constrain it—but it
     * also checks conformance at runtime to ensure validity.
     */
    typeIn(...types) {
        // Rationale: If we used the spelling "type('a', 'b', ...)" instead of
        // this, one might expect type('a', 'b').type(fn) to have the latter
        // call override, while expecting type(fn).type('a', 'b') to keep both
        // in effect. Then different calls to type() don't consistently
        // override each other, and the rules get complicated. Plus you can't
        // inherit a type constraint and then sub in another type-returning
        // function that still gets the constraint applied.
        return new this.constructor(this._calls,
                                    this._max,
                                    types);
    }

    /**
     * Check a fact for conformance with any typeIn() call.
     *
     * @arg leftType the type of the LHS, which becomes my emitted type if the
     *    fact doesn't specify one
     */
    _checkTypeIn(result, leftType) {
        if (this._types.size > 0) {
            if (result.type === undefined) {
                if (!this._types.has(leftType)) {
                    throw new Error(`A right-hand side claimed, via typeIn(...) to emit one of the types ${this._types} but actually inherited ${leftType} from the left-hand side.`);
                }
            } else if (!this._types.has(result.type)) {
                throw new Error(`A right-hand side claimed, via typeIn(...) to emit one of the types ${this._types} but actually emitted ${result.type}.`);
            }
        }
    }

    /**
     * Whatever the callback returns (even ``undefined``) becomes the note of
     * the fact. This overrides any previous call to ``note``.
     */
    note(callback) {
        function getSubfacts(fnode) {
            return {note: callback(fnode)};
        }
        getSubfacts.possibleSubfacts = NOTE;
        getSubfacts.kind = 'note';
        return new this.constructor(this._calls.concat(getSubfacts),
                                    this._max,
                                    this._types);
    }

    /**
     * Affect the confidence with which the input node should be considered a
     * member of a type.
     *
     * The parameter is generally between 0 and 1 (inclusive), with 0 meaning
     * the node does not have the "smell" this rule checks for and 1 meaning it
     * does. The range between 0 and 1 is available to represent "fuzzy"
     * confidences. If you have an unbounded range to compress down to [0, 1],
     * consider using :func:`sigmoid` or a scaling thereof.
     *
     * Since every node can have multiple, independent scores (one for each
     * type), this applies to the type explicitly set by the RHS or, if none,
     * to the type named by the ``type`` call on the LHS. If the LHS has none
     * because it's a ``dom(...)`` LHS, an error is raised.
     *
     * @arg {number|function} scoreOrCallback Can either be a static number,
     *     generally 0 to 1 inclusive, or else a callback which takes the fnode
     *     and returns such a number. If the callback returns a boolean, it is
     *     cast to a number.
     */
    score(scoreOrCallback) {
        let getSubfacts;

        function getSubfactsFromNumber(fnode) {
            return {score: scoreOrCallback};
        }

        function getSubfactsFromFunction(fnode) {
            let result = scoreOrCallback(fnode);
            if (typeof result === 'boolean') {
                // Case bools to numbers for convenience. Boolean features are
                // common. Don't cast other things, as it frustrates ruleset
                // debugging.
                result = Number(result);
            }
            return {score: result};
        }

        if (typeof scoreOrCallback === 'number') {
            getSubfacts = getSubfactsFromNumber;
        } else {
            getSubfacts = getSubfactsFromFunction;
        }
        getSubfacts.possibleSubfacts = SCORE;
        getSubfacts.kind = 'score';

        return new this.constructor(this._calls.concat(getSubfacts),
                                    this._max,
                                    this._types);
    }

    // Future: why not have an .element() method for completeness?

    // -------- Methods below this point are private to the framework. --------

    /**
     * Run all my props().type().note().score() stuff across a given fnode,
     * enforce my max() stuff, and return a fact ({element, type, score,
     * notes}) for incorporation into that fnode (or a different one, if
     * element is specified). Any of the 4 fact properties can be missing;
     * filling in defaults is a job for the caller.
     *
     * @arg leftType The type the LHS takes in
     */
    fact(fnode, leftType) {
        const doneKinds = new Set();
        const result = {};
        let haveSubfacts = 0;
        for (let call of reversed(this._calls)) {
            // If we've already called a call of this kind, then forget it.
            if (!doneKinds.has(call.kind)) {
                doneKinds.add(call.kind);

                if (~haveSubfacts & call.possibleSubfacts) {
                    // This call might provide a subfact we are missing.
                    const newSubfacts = call(fnode);

                    // We start with an empty object, so we're okay here.
                    // eslint-disable-next-line guard-for-in
                    for (let subfact in newSubfacts) {
                        // A props() callback could insert arbitrary keys into
                        // the result, but it shouldn't matter, because nothing
                        // pays any attention to them.
                        if (!result.hasOwnProperty(subfact)) {
                            result[subfact] = newSubfacts[subfact];
                        }
                        haveSubfacts |= SUBFACTS[subfact];
                    }
                }
            }
        }
        this._checkAtMost(result);
        this._checkTypeIn(result, leftType);
        return result;
    }

    /**
     * Return a record describing the types I might emit (which means either to
     * add a type to a fnode or to output a fnode that already has that type).
     * {couldChangeType: whether I might add a type to the fnode,
     *  possibleTypes: If couldChangeType, the types I might emit; empty set if
     *      we cannot infer it. If not couldChangeType, undefined.}
     */
    possibleEmissions() {
        // If there is a typeIn() constraint or there is a type() call to the
        // right of all props() calls, we have a constraint. We hunt for the
        // tightest constraint we can find, favoring a type() call because it
        // gives us a single type but then falling back to a typeIn().
        let couldChangeType = false;
        for (let call of reversed(this._calls)) {
            if (call.kind === 'props') {
                couldChangeType = true;
                break;
            } else if (call.kind === 'type') {
                return {couldChangeType: true,
                        possibleTypes: new Set([call.type])};
            }
        }
        return {couldChangeType,
                possibleTypes: this._types};
    }
}

class OutwardRhs {
    constructor(key, through = x => x, allThrough = x => x) {
        this.key = key;
        this.callback = through;
        this.allCallback = allThrough;
    }

    /**
     * Append ``.through`` to :func:`out` to run each :term:`fnode` emitted
     * from the LHS through an arbitrary function before returning it to the
     * containing program. Example::
     *
     *     out('titleLengths').through(fnode => fnode.noteFor('title').length)
     */
    through(callback) {
        return new this.constructor(this.key, callback, this.allCallback);
    }

    /**
     * Append ``.allThrough`` to :func:`out` to run the entire iterable of
     * emitted :term:`fnodes<fnode>` through an arbitrary function before
     * returning them to the containing program. Example::
     *
     *     out('sortedTitles').allThrough(domSort)
     */
    allThrough(callback) {
        return new this.constructor(this.key, this.callback, callback);
    }

    asRhs() {
        return this;
    }
}

function props(callback) {
    return new Side({method: 'props', args: [callback]});
}

/** Constrain to an input type on the LHS, or apply a type on the RHS. */
function type(theType) {
    return new Side({method: 'type', args: [theType]});
}

function note(callback) {
    return new Side({method: 'note', args: [callback]});
}

function score(scoreOrCallback) {
    return new Side({method: 'score', args: [scoreOrCallback]});
}

function atMost(score) {
    return new Side({method: 'atMost', args: [score]});
}

function typeIn(...types) {
    return new Side({method: 'typeIn', args: types});
}

/**
 * Pull nodes that conform to multiple conditions at once.
 *
 * For example: ``and(type('title'), type('english'))``
 *
 * Caveats: ``and`` supports only simple ``type`` calls as arguments for now,
 * and it may fire off more rules as prerequisites than strictly necessary.
 * ``not`` and ``or`` don't exist yet, but you can express ``or`` the long way
 * around by having 2 rules with identical RHSs.
 */
function and(...lhss) {
    return new Side({method: 'and', args: lhss});
}

/**
 * Experimental. For each :term:`fnode` from ``typeCallA``, find the closest
 * node from ``typeCallB``, and attach it as a note. The note is attached to
 * the type specified by the RHS, defaulting to the type of ``typeCallA``. If
 * no nodes are emitted from ``typeCallB``, do nothing.
 *
 * For example... ::
 *
 *     nearest(type('image'), type('price'))
 *
 * The score of the ``typeCallA`` can be added to the new type's score by using
 * :func:`conserveScore` (though this routine has since been removed)::
 *
 *     rule(nearest(type('image'), type('price')),
 *          type('imageWithPrice').score(2).conserveScore())
 *
 * Caveats: ``nearest`` supports only simple ``type`` calls as arguments ``a``
 * and ``b`` for now.
 *
 * @arg distance {function} A function that takes 2 fnodes and returns a
 *     numerical distance between them. Included options are :func:`distance`,
 *     which is a weighted topological distance, and :func:`euclidean`, which
 *     is a spatial distance.
 */
function nearest(typeCallA, typeCallB, distance = euclidean) {
--> --------------------

--> maximum size reached

--> --------------------