Keeping Text Annotations Attached When a Document Changes

// index.ts
import type {
	AnchorOptions,
	Answer,
	Candidate,
	CandidateSource,
	FoundSpan,
	IndexedText,
	Location,
	Match,
	PendingCluster,
	SourceRun,
	StoredAnchor,
	TextIndex,
	TextPiece,
	TextSource,
	TextSpan,
} from './types';

/**
 * How many characters of context a note stores on each side of its passage.
 *
 * It's long enough to tell a sentence from a copy of it in another paragraph, and short enough that an edit a few sentences away never touches it.
 */
export const CONTEXT_LENGTH = 32;

/**
 * How alike each side's context has to be, from 0 to 1, before the place counts as the passage's place.
 *
 * An exact copy of the words in another paragraph has the right words but the wrong surroundings, and its context scores come out below this value.
 * A place has to reach it on both sides, or on one side when the note covered a whole block and the place fills one.
 */
export const CONTEXT_AGREES = 0.8;

/**
 * Below this many characters, a passage counts as short.
 *
 * A short passage, a word or a command, can appear in many places on a page.
 */
export const SHORT_PASSAGE = 16;

/**
 * How alike each side's context has to be for a short passage.
 *
 * Higher than `CONTEXT_AGREES`, because a short passage leans on its context to tell one copy from another.
 */
export const SHORT_CONTEXT_AGREES = 0.9;

/**
 * How alike the words have to be, from 0 to 1, for a place whose context agrees to count as the passage with its text changed.
 *
 * Below it, the words changed enough that the user's note may not apply anymore, even when the surroundings are the same.
 * Short passages never get this answer, since one edit to a short word changes what it says.
 */
export const WORDS_CHANGED = 0.8;

/**
 * How alike the words have to be, from 0 to 1, for a place to be offered as a possible match when nothing could be placed.
 *
 * A candidate below it is never offered to the user as the possible match.
 */
export const GUESS_FLOOR = 0.65;

/**
 * How close two scores have to be to count as equal.
 *
 * Two places whose context differs by one character in 32 still tie.
 */
export const TIE_MARGIN = 0.05;

/**
 * How much longer than the stored words a span found through the context may be, as a share of their length.
 *
 * It caps the length of a span found through the context, inside the block where the span starts.
 */
export const SPAN_GROWTH = 0.5;

/**
 * The extra characters a span found through the context may have on top of `SPAN_GROWTH`.
 *
 * A short passage gets room for a few added words even though half its length is only a few characters.
 */
export const SPAN_SLACK = 16;

/**
 * Matches one character of the ASCII whitespace that HTML collapses, which the index treats as whitespace.
 *
 * A non-breaking space isn't in the list, because a page writes it on purpose and CSS keeps it.
 */
const WHITESPACE = /^[\t\n\f\r ]$/;

/**
 * One unit of raw text: a single whitespace character, or one character plus the combining marks after it.
 *
 * Whitespace is a unit of its own, so a space or a tab before a combining mark collapses like any other whitespace.
 * `joins()` tests which units have to be normalized together, inside one piece or across several.
 */
const CLUSTER = /[\t\n\f\r ]|[^\t\n\f\r \p{M}]\p{M}*|\p{M}+/gu;

/**
 * Tells whether a unit of raw text has to be NFC-normalized together with the text before it.
 *
 * A unit that starts with a combining mark always does.
 * Any other unit does when NFC gives one result for the two together and another for each one alone, as it does for Hangul written as separate letters.
 * It compares NFC results instead of checking a list of scripts, because a list misses the characters a new version of Unicode adds.
 * Nothing below U+0300 composes with the character before it, so for ASCII text the function returns before any normalize call.
 *
 * @param before - The raw text of the unit that isn't written to the page text yet.
 * @param cluster - The next unit.
 * @returns Whether the two are normalized as one unit.
 */
function joins( before: string, cluster: string ): boolean {
	return /^\p{M}/u.test( cluster ) || ( cluster.charCodeAt( 0 ) >= 0x300
		&& ( before + cluster ).normalize( 'NFC' ) !== before.normalize( 'NFC' ) + cluster.normalize( 'NFC' ) );
}

/**
 * The elements that start and end a block when the app passes no selector of its own.
 *
 * It lists the block containers a docs page is built from.
 * The text of two of them never runs together, even when one is empty or the HTML has no whitespace between them.
 */
export const DEFAULT_BLOCKS = [
	'article', 'aside', 'blockquote', 'dd', 'details', 'div', 'dl', 'dt', 'figcaption', 'figure', 'footer',
	'h1', 'h2', 'h3', 'h4', 'h5', 'h6', 'header', 'hr', 'li', 'main', 'nav', 'ol', 'p', 'pre',
	'section', 'summary', 'table', 'td', 'th', 'tr', 'ul',
].join( ', ' );

/**
 * The elements whose text the index skips when the app passes no `ignore` function of its own.
 */
const SKIPPED = 'script, style, noscript, template, [data-anchor-ignore]';

/**
 * Builds the page text from pieces of raw text, with a map from every position back to its piece.
 *
 * Every run of whitespace, every line break, and every edge between blocks becomes one space, and the text never starts or ends with one.
 * The stored words of a note come out of the same rule as the page text they're compared with.
 * Two paragraphs never run together, whether or not the HTML source has a newline between them.
 * Each character is NFC-normalized together with the characters that compose with it, even when they start the next piece of the same block.
 * An accent typed as two code points then matches the same accent typed as one, and Hangul typed as separate letters matches the same syllables typed whole.
 * Whitespace, a block edge, and a line break end that run, so a combining mark after one of them never composes with the text before it.
 *
 * @param pieces - The raw text, in reading order, with the block each piece is in.
 * @returns The page text, the blocks, and the map back to the pieces.
 */
export function indexPieces( pieces: readonly TextPiece[] ): IndexedText {
	let text = '';
	const piece: number[] = [];
	const from: number[] = [];
	const endPiece: number[] = [];
	const to: number[] = [];
	const blocks: TextSpan[] = [];
	let space: SourceRun | null = null;
	let open: TextSpan | null = null;
	let pending: PendingCluster | null = null;
	let current: unknown;

	/**
	 * Writes the pending unit to the page text after NFC, and maps every position it becomes back to its raw characters.
	 */
	const flush = (): void => {
		if ( !pending || !open ) {
			return;
		}
		const normalized = pending.raw.normalize( 'NFC' );
		for ( let unit = 0; unit < normalized.length; unit++ ) {
			piece.push( pending.piece );
			from.push( pending.from );
			endPiece.push( pending.endPiece );
			to.push( pending.to );
		}
		text += normalized;
		open.end = text.length;
		pending = null;
	};

	pieces.forEach( ( { data, block, breakBefore }, index ) => {
		if ( index === 0 || block !== current ) {
			flush();
			open = null;
			space ??= { piece: index, from: 0, to: 0 };
			current = block;
		} else if ( breakBefore ) {
			flush();
			space ??= { piece: index, from: 0, to: 0 };
		}
		for ( const match of data.matchAll( CLUSTER ) ) {
			const cluster = match[ 0 ];
			const offset = match.index;
			if ( WHITESPACE.test( cluster ) ) {
				flush();
				if ( !space ) {
					space = { piece: index, from: offset, to: offset + 1 };
				} else if ( space.piece === index && space.to === offset ) {
					space.to = offset + 1;
				}
				continue;
			}
			if ( pending && joins( pending.raw, cluster ) ) {
				pending.raw += cluster;
				pending.endPiece = index;
				pending.to = offset + cluster.length;
				continue;
			}
			flush();
			if ( space && text.length > 0 ) {
				text += ' ';
				piece.push( space.piece );
				from.push( space.from );
				endPiece.push( space.piece );
				to.push( space.to );
			}
			space = null;
			if ( !open ) {
				open = { start: text.length, end: text.length };
				blocks.push( open );
			}
			pending = { raw: cluster, piece: index, from: offset, endPiece: index, to: offset + cluster.length };
		}
	} );
	flush();

	return { text, blocks, piece, from, endPiece, to };
}

/**
 * Finds which block a position falls in, by its place in the list of blocks.
 *
 * Because the blocks come in reading order and never overlap, a binary search over their starts finds the block in a few steps per candidate.
 *
 * @param blocks - The blocks of the page text.
 * @param position - A position in the page text.
 * @returns The index of the last block that starts at or before the position, or 0 when there are no blocks.
 */
function blockIndex( blocks: readonly TextSpan[], position: number ): number {
	let low = 0;
	let high = Math.max( 0, blocks.length - 1 );
	while ( low < high ) {
		const middle = Math.ceil( ( low + high ) / 2 );
		if ( blocks[ middle ].start <= position ) {
			low = middle;
		} else {
			high = middle - 1;
		}
	}
	return low;
}

/**
 * Finds the block a position falls in, whose edges a span found through the context must stay inside.
 *
 * A source with no blocks, such as a plain string in a test, counts as one block.
 *
 * @param source - The page text and its blocks.
 * @param position - A position in the page text.
 * @returns The block, or the whole text when there are no blocks.
 */
function blockAt( source: TextSource, position: number ): TextSpan {
	return source.blocks.at( blockIndex( source.blocks, position ) ) ?? { start: 0, end: source.text.length };
}

/**
 * Tells whether a span starts where a block starts and ends where a block ends, as a note on a whole paragraph does.
 *
 * @param source - The page text and its blocks.
 * @param start - The first position of the span.
 * @param end - The position right after the span.
 * @returns Whether the span fills its block, or a run of whole blocks.
 */
function fillsBlock( source: TextSource, start: number, end: number ): boolean {
	const { blocks } = source;
	return blocks.length > 0
		&& blocks[ blockIndex( blocks, start ) ].start === start
		&& blocks[ blockIndex( blocks, end - 1 ) ].end === end;
}

/**
 * Finds how far the context around a span may reach on each side.
 *
 * The context stops at the edges of the span's block, out of reach of an edit in a heading or in the previous paragraph.
 * A span that fills its block would get empty context on both sides there, and empty context matches every other whole block.
 * Such a span reaches one block further on each side, to the end of the previous block and the start of the next one.
 * When the note covered a whole block too, `contextAgrees()` needs only one of those two neighbors to match.
 *
 * @param source - The page text and its blocks.
 * @param start - The first position of the span.
 * @param end - The position right after the span.
 * @returns The first position the text before may use, and the position right after the last one the text after may use.
 */
function contextReach( source: TextSource, start: number, end: number ): TextSpan {
	const { blocks, text } = source;
	if ( blocks.length === 0 ) {
		return { start: 0, end: text.length };
	}
	const first = blockIndex( blocks, start );
	const last = blockIndex( blocks, end - 1 );
	if ( !fillsBlock( source, start, end ) ) {
		return { start: blocks[ first ].start, end: blocks[ last ].end };
	}
	return { start: first > 0 ? blocks[ first - 1 ].start : 0, end: blocks.at( last + 1 )?.end ?? text.length };
}

/**
 * Returns the context before a span, up to `CONTEXT_LENGTH` characters and no further than `contextReach()` allows.
 *
 * @param source - The page text and its blocks.
 * @param start - The first position of the span.
 * @param end - The position right after the span, needed to tell whether the span fills its block.
 * @returns The text right before the span.
 */
function contextBefore( source: TextSource, start: number, end: number ): string {
	const reach = contextReach( source, start, end );
	return source.text.slice( Math.max( reach.start, start - CONTEXT_LENGTH ), start );
}

/**
 * Returns the context after a span, up to `CONTEXT_LENGTH` characters and no further than `contextReach()` allows.
 *
 * @param source - The page text and its blocks.
 * @param start - The first position of the span, needed to tell whether the span fills its block.
 * @param end - The position right after the span.
 * @returns The text right after the span.
 */
function contextAfter( source: TextSource, start: number, end: number ): string {
	const reach = contextReach( source, start, end );
	return source.text.slice( end, Math.min( reach.end, end + CONTEXT_LENGTH ) );
}

/**
 * Drops the spaces at both ends of a span, after clamping it to the text.
 *
 * A selection often starts or ends on the space between words, and the index never stores a passage that starts with one.
 *
 * @param text - The page text.
 * @param start - The first position.
 * @param end - The position right after the last one.
 * @returns The trimmed span, or null when nothing but whitespace is left.
 */
function trimSpan( text: string, start: number, end: number ): TextSpan | null {
	let first = Math.max( 0, Math.min( start, text.length ) );
	let last = Math.max( first, Math.min( end, text.length ) );
	while ( first < last && text[ first ] === ' ' ) {
		first++;
	}
	while ( last > first && text[ last - 1 ] === ' ' ) {
		last--;
	}
	return first < last ? { start: first, end: last } : null;
}

/**
 * Counts the single-character edits that turn one string into the other (Levenshtein distance).
 *
 * @param a - One string.
 * @param b - The other string.
 * @returns The number of insertions, deletions, and substitutions.
 */
export function editDistance( a: string, b: string ): number {
	let previous = Array.from( { length: b.length + 1 }, ( _, index ) => index );
	for ( let row = 1; row <= a.length; row++ ) {
		const next = [ row ];
		for ( let column = 1; column <= b.length; column++ ) {
			const substitution = previous[ column - 1 ] + ( a[ row - 1 ] === b[ column - 1 ] ? 0 : 1 );
			next.push( Math.min( previous[ column ] + 1, next[ column - 1 ] + 1, substitution ) );
		}
		previous = next;
	}
	return previous[ b.length ];
}

/**
 * Scores how alike two strings are, from 0 for nothing in common to 1 for identical.
 *
 * With the edit distance divided by the longer length, a missing context counts against a candidate as much as a different one.
 * Two empty strings are identical, which is how two passages that both start at the edge of their block agree.
 *
 * @param a - One string.
 * @param b - The other string.
 * @returns The similarity.
 */
export function similarity( a: string, b: string ): number {
	const longest = Math.max( a.length, b.length );
	return longest === 0 ? 1 : 1 - editDistance( a, b ) / longest;
}

/**
 * Describes a span of the page text as the shape a note stores.
 *
 * `findPassage()` measures each candidate's context with the same `contextReach()` rule used here.
 * The description also says whether the span fills its block, and how many places tie with it on this page when there's more than one, as with a paragraph that appears twice.
 * With that count, a note attached to one of two identical paragraphs stays on it.
 *
 * @param source - The page text and its blocks.
 * @param start - The first position of the passage.
 * @param end - The position right after the passage.
 * @returns The stored shape, or null when the span holds only whitespace.
 */
export function describeSpan( source: TextSource, start: number, end: number ): StoredAnchor | null {
	const span = trimSpan( source.text, start, end );
	if ( !span ) {
		return null;
	}
	const stored: StoredAnchor = {
		start: span.start,
		end: span.end,
		exact: source.text.slice( span.start, span.end ),
		prefix: contextBefore( source, span.start, span.end ),
		suffix: contextAfter( source, span.start, span.end ),
	};
	if ( fillsBlock( source, span.start, span.end ) ) {
		stored.wholeBlock = true;
	}
	const agrees = contextTest( source, stored );
	const passing = scoreCandidates( source, stored ).filter( ( candidate ) => candidate.words === 1 && agrees( candidate ) );
	const itself = passing.find( ( candidate ) => candidate.start === span.start && candidate.end === span.end );
	const copies = itself ? distinctPlaces( passing ).places.filter( ( place ) => ties( place, itself ) ).length : 1;
	if ( copies > 1 ) {
		stored.copies = copies;
	}
	return stored;
}

/**
 * Lists the positions right after each copy of the stored prefix, where a span found through the context can start.
 *
 * When the stored prefix is empty, as it is for a passage that started its block, every block start counts.
 *
 * @param source - The page text and its blocks.
 * @param prefix - The stored prefix.
 * @returns The possible starts.
 */
function contextStarts( source: TextSource, prefix: string ): number[] {
	if ( !prefix ) {
		return source.blocks.map( ( block ) => block.start );
	}
	const starts: number[] = [];
	for ( let at = source.text.indexOf( prefix ); at !== -1; at = source.text.indexOf( prefix, at + 1 ) ) {
		starts.push( at + prefix.length );
	}
	return starts;
}

/**
 * Finds the end of a span found through the context, at the first copy of the stored suffix close enough after its start.
 *
 * The span runs to the end of the block when the stored suffix is empty, as it is for a passage that ended its block.
 * The span never leaves the block it starts in.
 *
 * @param source - The page text and its blocks.
 * @param start - Where the span starts.
 * @param suffix - The stored suffix.
 * @param longest - The longest the span may be.
 * @returns The end of the span, or null when the suffix isn't close enough or is in another block.
 */
function contextEnd( source: TextSource, start: number, suffix: string, longest: number ): number | null {
	const block = blockAt( source, start );
	const end = suffix ? source.text.indexOf( suffix, start ) : block.end;
	return end > start && end <= block.end && end - start <= longest ? end : null;
}

/**
 * Lists the whole blocks right after a copy of the stored prefix and right before a copy of the stored suffix.
 *
 * A passage that fills its block stored the end of the block before it as its prefix and the start of the block after it as its suffix.
 * When a release edits the passage and also changes one of those neighbors, no span runs from a copy of the prefix to a copy of the suffix anymore.
 * The block next to the neighbor that stayed the same is still a candidate.
 *
 * @param source - The page text and its blocks.
 * @param prefix - The stored prefix.
 * @param suffix - The stored suffix.
 * @returns The blocks, possibly with repeats.
 */
function neighborBlocks( source: TextSource, prefix: string, suffix: string ): TextSpan[] {
	const { text } = source;
	const found: TextSpan[] = [];
	for ( let at = prefix ? text.indexOf( prefix ) : -1; at !== -1; at = text.indexOf( prefix, at + 1 ) ) {
		const block = blockAt( source, at + prefix.length );
		if ( block.start === at + prefix.length ) {
			found.push( block );
		}
	}
	for ( let at = suffix ? text.indexOf( suffix ) : -1; at !== -1; at = text.indexOf( suffix, at + 1 ) ) {
		const block = blockAt( source, at - 1 );
		if ( block.end === at ) {
			found.push( block );
		}
	}
	return found;
}

/**
 * Tells whether the text around a candidate agrees with the stored context.
 *
 * Both sides have to reach the floor, except for a note that covered a whole block at a candidate that fills a block, which needs one side.
 * A note on a whole paragraph stored the text of the blocks before and after it, and a release can add, edit, or remove either of them without touching the paragraph.
 * An exact copy of the paragraph with other blocks on both sides still fails.
 * A note on part of a paragraph never gets the exception, or a copy of its words that fills a block of its own could pass on one side.
 *
 * @param source - The page text and its blocks.
 * @param candidate - The candidate.
 * @param floor - How alike a side has to be, from 0 to 1.
 * @param wholeBlock - Whether the note covered a whole block.
 * @returns Whether the context agrees.
 */
function contextAgrees( source: TextSource, candidate: Candidate, floor: number, wholeBlock: boolean ): boolean {
	const sides = [ candidate.before, candidate.after ].filter( ( side ) => side >= floor ).length;
	return sides === 2 || ( sides === 1 && wholeBlock && fillsBlock( source, candidate.start, candidate.end ) );
}

/**
 * Builds the test a candidate's context has to pass for a stored passage.
 *
 * A short passage needs a higher floor, and only a note that covered a whole block gets the one-side rule.
 *
 * @param source - The page text and its blocks.
 * @param stored - What the note stored.
 * @returns The test.
 */
function contextTest( source: TextSource, stored: StoredAnchor ): ( candidate: Candidate ) => boolean {
	const floor = stored.exact.normalize( 'NFC' ).length < SHORT_PASSAGE ? SHORT_CONTEXT_AGREES : CONTEXT_AGREES;
	return ( candidate ) => contextAgrees( source, candidate, floor, stored.wholeBlock === true );
}

/**
 * Tells whether one candidate is no worse than another on every signal and ahead by more than the tie margin on at least one.
 *
 * Comparing signal by signal, instead of adding them into one number, means a strong word match can never make up for context that disagrees.
 * Being no worse on every signal keeps the wins from going in a circle, where three candidates each beat the next one and none is left.
 * A lead within the tie margin doesn't count, so two near-identical places stay a tie for `settle()` to break.
 *
 * @param a - The candidate that might be better.
 * @param b - The candidate it's compared with.
 * @returns Whether `a` beats `b`.
 */
function dominates( a: Candidate, b: Candidate ): boolean {
	const signals = [ [ a.words, b.words ], [ a.before, b.before ], [ a.after, b.after ] ];
	return signals.every( ( [ mine, theirs ] ) => mine >= theirs )
		&& signals.some( ( [ mine, theirs ] ) => mine > theirs + TIE_MARGIN );
}

/**
 * Tells whether two candidates score the same on every signal, within the tie margin.
 *
 * @param a - One candidate.
 * @param b - The other candidate.
 * @returns Whether they tie.
 */
function ties( a: Candidate, b: Candidate ): boolean {
	return Math.abs( a.words - b.words ) <= TIE_MARGIN
		&& Math.abs( a.before - b.before ) <= TIE_MARGIN
		&& Math.abs( a.after - b.after ) <= TIE_MARGIN;
}

/**
 * Narrows the candidates that passed down to separate places.
 *
 * A candidate that another one beats on the signals drops out first.
 * Then spans that start at the same position count as one place, and the one whose context matches best is kept, then the one with the better words, then the nearer one.
 * When an edit changes a passage's length by one character, the text at the old position and the span between the copies of the stored context start together and end one character apart, and both are the same passage.
 * Copies that only overlap, as in a run of repeated characters, stay separate places.
 *
 * @param passing - The candidates that cleared the thresholds.
 * @returns The candidates no other one beats, and the places they make.
 */
function distinctPlaces( passing: Candidate[] ): { undominated: Candidate[]; places: Candidate[] } {
	const undominated = passing.filter( ( candidate ) => !passing.some( ( other ) => dominates( other, candidate ) ) );
	const fit = ( candidate: Candidate ) => Math.min( candidate.before, candidate.after );
	const ranked = [ ...undominated ].sort( ( a, b ) => fit( b ) - fit( a )
		|| b.words - a.words
		|| a.distance - b.distance );
	const places: Candidate[] = [];
	for ( const candidate of ranked ) {
		if ( !places.some( ( kept ) => kept.start === candidate.start ) ) {
			places.push( candidate );
		}
	}
	return { undominated, places };
}

/**
 * Picks the winner among the candidates that passed, or reports that the user has to choose.
 *
 * A single candidate no other one beats wins, and so does a single place once spans with the same start count as one.
 * The old position breaks a tie only when exactly one tied place starts there and the passage already had that many places when it was saved.
 * A paragraph copied right above the original takes the original's old position, and the page text alone can't say which copy is new.
 * So a tie with a place the note didn't have goes to the user, nearest first.
 *
 * @param answer - The answer a single winner gets.
 * @param passing - The candidates that cleared the thresholds for that answer.
 * @param candidates - Every candidate, for the result.
 * @param copies - How many places tied with the passage when the note was saved.
 * @returns The match.
 */
function settle( answer: Answer, passing: Candidate[], candidates: Candidate[], copies: number ): Match {
	const { undominated, places } = distinctPlaces( passing );
	for ( const best of [ undominated, places ] ) {
		if ( best.length === 1 ) {
			return { answer, chosen: best, guess: null, candidates };
		}
		const home = best.filter( ( candidate ) => candidate.distance === 0 );
		if ( home.length === 1 && best.length <= copies && best.every( ( candidate ) => ties( candidate, best[ 0 ] ) ) ) {
			return { answer, chosen: home, guess: null, candidates };
		}
	}
	const nearest = [ ...places ].sort( ( a, b ) => a.distance - b.distance );
	return { answer: 'ambiguous', chosen: nearest, guess: null, candidates };
}

/**
 * Lists the places in the page text that could be a stored passage, and scores each one.
 *
 * The candidates are the text at the stored position, every exact copy of the words, every span between a copy of the stored prefix and the stored suffix, and every whole block right after a copy of the prefix or right before a copy of the suffix.
 * Only the last two kinds find a passage whose words were edited.
 * Each candidate gets its own scores for the words, the text before, the text after, and the distance from the old position.
 *
 * @param source - The page text and its blocks.
 * @param stored - What the note stored, with words that aren't empty.
 * @returns The candidates, best words first.
 */
function scoreCandidates( source: TextSource, stored: StoredAnchor ): Candidate[] {
	const exact = stored.exact.normalize( 'NFC' );
	const prefix = stored.prefix.normalize( 'NFC' );
	const suffix = stored.suffix.normalize( 'NFC' );
	const { text } = source;

	const spans = new Map<string, FoundSpan>();
	const add = ( start: number, end: number, found: CandidateSource ): void => {
		const span = trimSpan( text, start, end );
		if ( !span ) {
			return;
		}
		const key = `${span.start}:${span.end}`;
		const entry = spans.get( key ) ?? { span, found: new Set<CandidateSource>() };
		entry.found.add( found );
		spans.set( key, entry );
	};

	add( stored.start, stored.start + exact.length, 'position' );
	for ( let at = text.indexOf( exact ); at !== -1; at = text.indexOf( exact, at + 1 ) ) {
		add( at, at + exact.length, 'quote' );
	}
	const longest = Math.ceil( exact.length * ( 1 + SPAN_GROWTH ) ) + SPAN_SLACK;
	for ( const start of contextStarts( source, prefix ) ) {
		const end = contextEnd( source, start, suffix, longest );
		if ( end !== null ) {
			add( start, end, 'context' );
		}
	}
	for ( const block of neighborBlocks( source, prefix, suffix ) ) {
		if ( block.end - block.start <= longest ) {
			add( block.start, block.end, 'context' );
		}
	}

	const candidates: Candidate[] = [ ...spans.values() ].map( ( { span, found } ) => {
		const words = text.slice( span.start, span.end );
		return {
			start: span.start,
			end: span.end,
			text: words,
			words: similarity( exact, words ),
			before: similarity( prefix, contextBefore( source, span.start, span.end ) ),
			after: similarity( suffix, contextAfter( source, span.start, span.end ) ),
			distance: Math.abs( span.start - stored.start ),
			found: [ ...found ],
		};
	} );
	return candidates.sort( ( a, b ) => b.words - a.words
		|| Math.min( b.before, b.after ) - Math.min( a.before, a.after )
		|| a.distance - b.distance );
}

/**
 * Looks for a stored passage in the page text and gives it one of the four answers.
 *
 * @param source - The page text and its blocks.
 * @param stored - What the note stored.
 * @returns The answer, the chosen places, the guess, and every candidate with its signals.
 */
export function findPassage( source: TextSource, stored: StoredAnchor ): Match {
	const exact = stored.exact.normalize( 'NFC' );
	if ( !exact ) {
		return { answer: 'orphaned', chosen: [], guess: null, candidates: [] };
	}
	const candidates = scoreCandidates( source, stored );
	const agrees = contextTest( source, stored );
	const copies = stored.copies ?? 1;

	const placed = candidates.filter( ( candidate ) => candidate.words === 1 && agrees( candidate ) );
	if ( placed.length > 0 ) {
		return settle( 'placed', placed, candidates, copies );
	}
	const changed = exact.length < SHORT_PASSAGE
		? []
		: candidates.filter( ( candidate ) => candidate.words >= WORDS_CHANGED && agrees( candidate ) );
	if ( changed.length > 0 ) {
		return settle( 'changed', changed, candidates, copies );
	}
	const guess = candidates.find( ( candidate ) => candidate.words >= GUESS_FLOOR ) ?? null;
	return { answer: 'orphaned', chosen: [], guess, candidates };
}

/**
 * Lists the nodes the walk visits inside an element, in the order the page renders them.
 *
 * For a shadow host, the walk goes into its shadow root, the part the page renders in place of the host's own children.
 * A slot shows the nodes assigned to it, or its fallback content when nothing is.
 * `textContent`, `innerText`, and a TreeWalker all skip shadow content, which is why the index walks by hand.
 *
 * @param $element - The element to read.
 * @returns The nodes to visit next.
 */
function renderedChildren( $element: Element ): Node[] {
	if ( $element.shadowRoot ) {
		return [ $element.shadowRoot ];
	}
	if ( $element instanceof HTMLSlotElement ) {
		const assigned = $element.assignedNodes( { flatten: true } );
		return assigned.length > 0 ? assigned : Array.from( $element.childNodes );
	}
	return Array.from( $element.childNodes );
}

/**
 * Builds the page text over a root element and keeps the way back from each position to its Text node.
 *
 * It takes Text node data, the characters a Range counts, and never `innerText`, which collapses whitespace its own way, drops hidden text, and applies `text-transform`.
 * It walks into open shadow roots in reading order, and skips the elements the app marks as not part of the content.
 * Entering or leaving a block element starts a new block.
 * Even an empty block, such as an `hr`, keeps the text on either side of it apart.
 * A `<br>` holds no text and counts as a space, like the line break the page shows for it.
 *
 * @param $root - The element that holds the content.
 * @param options - What the app says about its markup.
 * @returns The index.
 */
export function buildTextIndex( $root: Node, options: AnchorOptions = {} ): TextIndex {
	const blocks = options.blocks ?? DEFAULT_BLOCKS;
	const ignore = options.ignore ?? ( ( $element: Element ) => $element.matches( SKIPPED ) );
	const pieces: TextPiece[] = [];
	const $nodes: Text[] = [];
	const enter = new Map<Node, number>();
	const exit = new Map<Node, number>();
	let block = 0;
	let breakBefore = false;

	const visit = ( $node: Node ): void => {
		enter.set( $node, pieces.length );
		if ( $node instanceof Text ) {
			pieces.push( { data: $node.data, block, breakBefore } );
			$nodes.push( $node );
			breakBefore = false;
		} else if ( $node instanceof Element ) {
			if ( !ignore( $node ) ) {
				const edge = $node.matches( blocks );
				block += edge ? 1 : 0;
				breakBefore ||= $node.localName === 'br';
				for ( const $child of renderedChildren( $node ) ) {
					visit( $child );
				}
				block += edge ? 1 : 0;
			}
		} else if ( $node instanceof DocumentFragment ) {
			for ( const $child of Array.from( $node.childNodes ) ) {
				visit( $child );
			}
		}
		exit.set( $node, pieces.length );
	};
	visit( $root );

	return { ...indexPieces( pieces ), $nodes, enter, exit };
}

/**
 * Finds the first position in the page text for which a test holds, for a test that's false and then true.
 *
 * @param index - The text index.
 * @param test - The test, given a position.
 * @returns The first position that passes, or the length of the text when none does.
 */
function firstPosition( index: TextIndex, test: ( position: number ) => boolean ): number {
	let low = 0;
	let high = index.text.length;
	while ( low < high ) {
		const middle = Math.floor( ( low + high ) / 2 );
		if ( test( middle ) ) {
			high = middle;
		} else {
			low = middle + 1;
		}
	}
	return low;
}

/**
 * Turns one boundary point of a range into a position in the page text.
 *
 * A boundary inside a Text node maps through the characters that node contributed.
 * A boundary between nodes, the kind a triple-click makes, maps to the first text after it.
 * A start is compared with where each position's characters end, and an end with where they start.
 * When a character's combining mark sits in the next Text node, a boundary between the letter and the mark maps to a position that includes the whole character.
 *
 * @param index - The text index.
 * @param $container - The boundary's container.
 * @param offset - The boundary's offset in the container.
 * @param edge - Whether the boundary starts or ends the range.
 * @returns The position, or null when the boundary is outside the indexed content.
 */
function positionOf( index: TextIndex, $container: Node, offset: number, edge: 'start' | 'end' ): number | null {
	if ( $container instanceof Text ) {
		const piece = index.enter.get( $container );
		if ( piece === undefined ) {
			return null;
		}
		return firstPosition( index, edge === 'start'
			? ( at ) => index.endPiece[ at ] > piece || ( index.endPiece[ at ] === piece && index.to[ at ] > offset )
			: ( at ) => index.piece[ at ] > piece || ( index.piece[ at ] === piece && index.from[ at ] >= offset ) );
	}
	const $child = $container.childNodes[ offset ];
	const pieces = $child ? index.enter.get( $child ) : index.exit.get( $container );
	if ( pieces === undefined ) {
		return null;
	}
	return firstPosition( index, edge === 'start'
		? ( at ) => index.endPiece[ at ] >= pieces
		: ( at ) => index.piece[ at ] >= pieces );
}

/**
 * Converts a range into a span of the page text.
 *
 * Any AbstractRange works here, a StaticRange from `getComposedRanges()` that crosses into a shadow root as well as a live Range.
 *
 * @param index - The text index.
 * @param range - The range.
 * @returns The span with the spaces at its ends dropped, or null when the range is outside the content or holds only whitespace.
 */
export function spanOf( index: TextIndex, range: AbstractRange ): TextSpan | null {
	const start = positionOf( index, range.startContainer, range.startOffset, 'start' );
	const end = positionOf( index, range.endContainer, range.endOffset, 'end' );
	if ( start === null || end === null ) {
		return null;
	}
	return trimSpan( index.text, start, end );
}

/**
 * Builds a fresh range over a span of the page text.
 *
 * When both ends share a root, it's a live Range, ready for painting, geometry, and hit testing.
 * A span that crosses into a shadow root comes back as a StaticRange.
 *
 * @param index - The text index.
 * @param start - The first position.
 * @param end - The position right after the last one.
 * @returns The range.
 */
export function rangeFor( index: TextIndex, start: number, end: number ): AbstractRange {
	const $startNode = index.$nodes[ index.piece[ start ] ];
	const $endNode = index.$nodes[ index.endPiece[ end - 1 ] ];
	const startOffset = index.from[ start ];
	const endOffset = index.to[ end - 1 ];
	if ( $startNode.getRootNode() === $endNode.getRootNode() ) {
		const range = ( $startNode.ownerDocument ?? document ).createRange();
		range.setStart( $startNode, startOffset );
		range.setEnd( $endNode, endOffset );
		return range;
	}
	return new StaticRange( { startContainer: $startNode, startOffset, endContainer: $endNode, endOffset } );
}

/**
 * Describes the passage a range covers, as the shape a note stores.
 *
 * Call it with the range of the user's selection; the result is plain data, ready for `JSON.stringify()`.
 *
 * @param $root - The element that holds the content.
 * @param range - The passage.
 * @param options - What the app says about its markup, the same options `locate()` gets.
 * @returns The stored shape, or null when the range is outside the content or holds only whitespace.
 */
export function describe( $root: Node, range: AbstractRange, options: AnchorOptions = {} ): StoredAnchor | null {
	const index = buildTextIndex( $root, options );
	const span = spanOf( index, range );
	return span ? describeSpan( index, span.start, span.end ) : null;
}

/**
 * Looks for a stored passage in the content as it is now, and gives the note its answer.
 *
 * It builds a new index and new ranges on every call, because a range made for an older version of the page points at the wrong characters or at nodes that are gone.
 *
 * @param $root - The element that holds the content.
 * @param stored - What the note stored.
 * @param options - What the app says about its markup, the same options `describe()` got.
 * @returns The answer, fresh ranges for the chosen places and the guess, and every candidate with its signals.
 */
export function locate( $root: Node, stored: StoredAnchor, options: AnchorOptions = {} ): Location {
	const index = buildTextIndex( $root, options );
	const match = findPassage( index, stored );
	return {
		...match,
		ranges: match.chosen.map( ( candidate ) => rangeFor( index, candidate.start, candidate.end ) ),
		guessRange: match.guess ? rangeFor( index, match.guess.start, match.guess.end ) : null,
	};
}

/**
 * Checks that a value read back from storage has the stored shape, before the app uses it.
 *
 * @param value - The parsed JSON.
 * @returns Whether it's a stored anchor.
 */
export function isStoredAnchor( value: unknown ): value is StoredAnchor {
	return typeof value === 'object' && value !== null
		&& 'start' in value && typeof value.start === 'number'
		&& 'end' in value && typeof value.end === 'number'
		&& 'exact' in value && typeof value.exact === 'string'
		&& 'prefix' in value && typeof value.prefix === 'string'
		&& 'suffix' in value && typeof value.suffix === 'string'
		&& ( !( 'wholeBlock' in value ) || value.wholeBlock === true )
		&& ( !( 'copies' in value ) || ( Number.isInteger( value.copies ) && Number( value.copies ) > 1 ) );
}