You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@annotator.apache.org by ge...@apache.org on 2020/11/12 22:08:09 UTC
[incubator-annotator] 01/04: WIP make describe quote work
This is an automated email from the ASF dual-hosted git repository.
gerben pushed a commit to branch import-dom-seek
in repository https://gitbox.apache.org/repos/asf/incubator-annotator.git
commit 0dd6dc420d9544d73f3aab39fed4041f49089c0a
Author: Gerben <ge...@treora.com>
AuthorDate: Fri Nov 6 22:20:22 2020 +0100
WIP make describe quote work
---
packages/dom/src/seek.ts | 55 +++++++++--
packages/dom/src/text-quote/describe.ts | 163 ++++++++++++++------------------
2 files changed, 119 insertions(+), 99 deletions(-)
diff --git a/packages/dom/src/seek.ts b/packages/dom/src/seek.ts
index c055291..af38386 100644
--- a/packages/dom/src/seek.ts
+++ b/packages/dom/src/seek.ts
@@ -18,14 +18,12 @@
* under the License.
*/
-import { Chunk, TextNodeChunker, PartialTextNode } from "./chunker";
+import { Chunk, Chunker, TextNodeChunker, PartialTextNode, chunkEquals } from "./chunker";
const E_END = 'Iterator exhausted before seek ended.';
-interface NonEmptyChunker<TChunk extends Chunk<any>> {
+export interface NonEmptyChunker<TChunk extends Chunk<any>> extends Chunker<TChunk> {
readonly currentChunk: TChunk;
- nextChunk(): TChunk | null;
- previousChunk(): TChunk | null;
}
export interface BoundaryPointer<T extends any> {
@@ -77,6 +75,35 @@ export class TextSeeker<TChunk extends Chunk<string>> implements Seeker<string>
this._readOrSeekTo(false, target);
}
+ seekToChunk(target: TChunk, offset: number = 0) {
+ this._readOrSeekToChunk(false, target, offset);
+ }
+
+ readToChunk(target: TChunk, offset: number = 0): string {
+ return this._readOrSeekToChunk(true, target, offset);
+ }
+
+ private _readOrSeekToChunk(read: true, target: TChunk, offset?: number): string
+ private _readOrSeekToChunk(read: false, target: TChunk, offset?: number): void
+ private _readOrSeekToChunk(read: boolean, target: TChunk, offset: number = 0): string {
+ // XXX We have no way of knowing whether a chunk follows or precedes the current chunk; we assume it follows.
+ let result = '';
+ // This will throw a RangeError if we reach the end without encountering the target chunk.
+ while (!chunkEquals(this.currentChunk, target)) {
+ if (read)
+ result += this.read(1, true);
+ else
+ this._readOrSeekTo(false, this.position + 1, true);
+ }
+ if (offset > this.offsetInChunk) {
+ if (read)
+ result += this.read(offset - this.offsetInChunk);
+ else
+ this.seekBy(offset - this.offsetInChunk);
+ }
+ return result;
+ }
+
private _readOrSeekTo(read: true, target: number, roundUp?: boolean): string
private _readOrSeekTo(read: false, target: number, roundUp?: boolean): void
private _readOrSeekTo(read: boolean, target: number, roundUp: boolean = false): string | void {
@@ -142,10 +169,11 @@ export class TextSeeker<TChunk extends Chunk<string>> implements Seeker<string>
}
}
-
export class DomSeeker extends TextSeeker<PartialTextNode> implements BoundaryPointer<Text> {
- constructor(scope: Range) {
- const chunker = new TextNodeChunker(scope);
+ constructor(chunkerOrScope: Chunker<PartialTextNode> | Range) {
+ const chunker = 'currentChunk' in chunkerOrScope
+ ? chunkerOrScope
+ : new TextNodeChunker(chunkerOrScope);
if (chunker.currentChunk === null)
throw new RangeError('Range does not contain any Text nodes.');
super(chunker as NonEmptyChunker<PartialTextNode>);
@@ -158,4 +186,17 @@ export class DomSeeker extends TextSeeker<PartialTextNode> implements BoundaryPo
get offsetInReferenceNode() {
return this.offsetInChunk + this.currentChunk.startOffset;
}
+
+ seekToBoundaryPoint(node: Node, offset: number) {
+ const document = (node.ownerDocument ?? node as Document);
+ const target = document.createRange();
+ target.setStart(node, offset);
+ // target.setEnd(node, offset); // (implied by setting the start)
+
+ // Seek step by step until we are at, or crossed, the target point.
+ const reverse = !!(node.compareDocumentPosition(this.referenceNode) & Node.DOCUMENT_POSITION_PRECEDING);
+ while (target.comparePoint(this.referenceNode, this.offsetInReferenceNode) === (reverse ? 1 : -1)) {
+ this.seekBy(reverse ? -1 : 1);
+ }
+ }
}
diff --git a/packages/dom/src/text-quote/describe.ts b/packages/dom/src/text-quote/describe.ts
index e5846bc..8ccf47e 100644
--- a/packages/dom/src/text-quote/describe.ts
+++ b/packages/dom/src/text-quote/describe.ts
@@ -20,7 +20,9 @@
import type { TextQuoteSelector } from '@annotator/selector';
import { ownerDocument } from '../owner-document';
-import { Seeker } from '../seek';
+import { Chunk, Chunker, ChunkRange, PartialTextNode, TextNodeChunker, chunkRangeEquals } from '../chunker';
+import { abstractTextQuoteSelectorMatcher } from '.';
+import { DomSeeker, TextSeeker, NonEmptyChunker } from '../seek';
export async function describeTextQuote(
range: Range,
@@ -32,120 +34,97 @@ export async function describeTextQuote(
scope = document.createRange();
scope.selectNodeContents(document);
}
- range = range.cloneRange();
+
+ const chunker = new TextNodeChunker(scope);
// Take the part of the range that falls within the scope.
+ range = range.cloneRange();
if (range.compareBoundaryPoints(Range.START_TO_START, scope) === -1)
range.setStart(scope.startContainer, scope.startOffset);
if (range.compareBoundaryPoints(Range.END_TO_END, scope) === 1)
range.setEnd(scope.endContainer, scope.endOffset);
- return {
- type: 'TextQuoteSelector',
- exact: range.toString(),
- ...calculateContextForDisambiguation(range, scope),
- };
+ return await abstractDescribeTextQuote(
+ convertRangeToChunkRange(chunker, range),
+ chunker,
+ );
}
-function calculateContextForDisambiguation(
- range: Range,
- scope: Range,
-): { prefix: string; suffix: string } {
- const exactText = range.toString();
- const scopeText = scope.toString();
- const targetStartIndex = getRangeTextPosition(range, scope);
- const targetEndIndex = targetStartIndex + exactText.length;
+async function abstractDescribeTextQuote<TChunk extends Chunk<string>>(
+ target: ChunkRange<TChunk>,
+ scope: Chunker<TChunk>,
+): Promise<TextQuoteSelector> {
+ const seeker = new TextSeeker(scope as NonEmptyChunker<TChunk>);
+ seeker.seekToChunk(target.startChunk, target.startIndex);
+ const exact = seeker.readToChunk(target.endChunk, target.endIndex);
// Starting with an empty prefix and suffix, we search for matches. At each unintended match
// we encounter, we extend the prefix or suffix just enough to ensure it will no longer match.
let prefix = '';
let suffix = '';
- let fromIndex = 0;
- while (fromIndex <= scopeText.length) {
- const searchPattern = prefix + exactText + suffix;
- const patternMatchIndex = scopeText.indexOf(searchPattern, fromIndex);
- if (patternMatchIndex === -1) break;
- fromIndex = patternMatchIndex + 1;
- const matchStartIndex = patternMatchIndex + prefix.length;
- const matchEndIndex = matchStartIndex + exactText.length;
+ while (true) {
+ const tentativeSelector: TextQuoteSelector = {
+ type: 'TextQuoteSelector',
+ exact,
+ prefix,
+ suffix,
+ }
+ const matches = abstractTextQuoteSelectorMatcher(tentativeSelector)(scope);
+ let nextMatch = await matches.next();
+
+ if (!nextMatch.done && chunkRangeEquals(nextMatch.value, target)) {
+ // This match is the intended one, ignore it.
+ nextMatch = await matches.next();
+ }
+
+ // If there are no more unintended matches, our selector is unambiguous!
+ if (nextMatch.done) return tentativeSelector;
+
+ // TODO either reset chunker to start from the beginning, or rewind the chunker by previous match’s length.
+ // chunker.seekTo(0) or chunker.seek(-prefix)
- // Skip the found match if it is the actual target.
- if (matchStartIndex === targetStartIndex) continue;
+ // We’ll have to add more prefix/suffix to disqualify this unintended match.
+ const unintendedMatch = nextMatch.value;
+ const seeker1 = new TextSeeker(scope as NonEmptyChunker<TChunk>);
+ const seeker2 = new TextSeeker(scope as NonEmptyChunker<TChunk>); // TODO must clone scope.
// Count how many characters we’d need as a prefix to disqualify this match.
- let sufficientPrefixLength = prefix.length + 1;
- const firstChar = (offset: number) =>
- scopeText[offset - sufficientPrefixLength];
- while (
- firstChar(targetStartIndex) &&
- firstChar(targetStartIndex) === firstChar(matchStartIndex)
- )
- sufficientPrefixLength++;
- if (!firstChar(targetStartIndex))
- // We reached the start of scopeText; prefix won’t work.
- sufficientPrefixLength = Infinity;
-
- // Count how many characters we’d need as a suffix to disqualify this match.
- let sufficientSuffixLength = suffix.length + 1;
- const lastChar = (offset: number) =>
- scopeText[offset + sufficientSuffixLength - 1];
- while (
- lastChar(targetEndIndex) &&
- lastChar(targetEndIndex) === lastChar(matchEndIndex)
- )
- sufficientSuffixLength++;
- if (!lastChar(targetEndIndex))
- // We reached the end of scopeText; suffix won’t work.
- sufficientSuffixLength = Infinity;
+ seeker1.seekToChunk(target.startChunk, target.startIndex);
+ seeker2.seekToChunk(unintendedMatch.startChunk, unintendedMatch.startIndex);
+ let sufficientPrefix: string | undefined = prefix;
+ while (true) {
+ let previousCharacter: string;
+ try {
+ previousCharacter = seeker1.read(-1);
+ } catch (err) {
+ sufficientPrefix = undefined; // Start of text reached.
+ break;
+ }
+ sufficientPrefix = previousCharacter + sufficientPrefix;
+ if (previousCharacter !== seeker2.read(-1)) break;
+ }
// Use either the prefix or suffix, whichever is shortest.
- if (sufficientPrefixLength <= sufficientSuffixLength) {
- // Compensate our search position for the increase in prefix length.
- fromIndex -= sufficientPrefixLength - prefix.length;
- prefix = scopeText.substring(
- targetStartIndex - sufficientPrefixLength,
- targetStartIndex,
- );
- } else {
- suffix = scopeText.substring(
- targetEndIndex,
- targetEndIndex + sufficientSuffixLength,
- );
- }
+ if (sufficientPrefix !== undefined && (sufficientSuffix === undefined || sufficientPrefix.length <= sufficientSuffix.length))
+ prefix = sufficientPrefix; // chunker.seek(prefix.length - sufficientPrefix.length)
+ else if (sufficientSuffix !== undefined)
+ suffix = sufficientSuffix;
+ else
+ throw new Error('Target cannot be disambiguated; how could that have happened‽');
}
-
- return { prefix, suffix };
}
-// Get the index of the first character of range within the text of scope.
-function getRangeTextPosition(range: Range, scope: Range): number {
- const seeker = new Seeker(scope);
- const scopeOffset = isTextNode(scope.startContainer) ? scope.startOffset : 0;
- if (isTextNode(range.startContainer))
- return seeker.seek(range.startContainer) + range.startOffset - scopeOffset;
- else return seeker.seek(firstTextNodeInRange(range)) - scopeOffset;
-}
+function convertRangeToChunkRange(chunker: Chunker<PartialTextNode>, range: Range): ChunkRange<PartialTextNode> {
+ const domSeeker = new DomSeeker(chunker);
-function firstTextNodeInRange(range: Range): Text {
- // Find the first text node inside the range.
- const iter = ownerDocument(range).createNodeIterator(
- range.commonAncestorContainer,
- NodeFilter.SHOW_TEXT,
- {
- acceptNode(node: Text) {
- // Only reveal nodes within the range; and skip any empty text nodes.
- return range.intersectsNode(node) && node.length > 0
- ? NodeFilter.FILTER_ACCEPT
- : NodeFilter.FILTER_REJECT;
- },
- },
- );
- const node = iter.nextNode() as Text | null;
- if (node === null) throw new Error('Range contains no text nodes');
- return node;
-}
+ domSeeker.seekToBoundaryPoint(range.startContainer, range.startOffset);
+ const startChunk = domSeeker.currentChunk;
+ const startIndex = domSeeker.offsetInChunk;
+
+ domSeeker.seekToBoundaryPoint(range.endContainer, range.endOffset);
+ const endChunk = domSeeker.currentChunk;
+ const endIndex = domSeeker.offsetInChunk;
-function isTextNode(node: Node): node is Text {
- return node.nodeType === Node.TEXT_NODE;
+ return { startChunk, startIndex, endChunk, endIndex };
}