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/11 15:56:36 UTC
[incubator-annotator] branch import-dom-seek updated (615e836 ->
e1df8ed)
This is an automated email from the ASF dual-hosted git repository.
gerben pushed a change to branch import-dom-seek
in repository https://gitbox.apache.org/repos/asf/incubator-annotator.git.
discard 615e836 WIP make describe quote work
new bffbeaf WIP make describe quote work
new e1df8ed Change approach, (re)implement normalizeRange
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (615e836)
\
N -- N -- N refs/heads/import-dom-seek (e1df8ed)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
packages/dom/src/chunker.ts | 19 ++++-
packages/dom/src/normalize-range.ts | 135 ++++++++++++++++++++++++++++++++
packages/dom/src/seek.ts | 19 +----
packages/dom/src/text-quote/describe.ts | 16 +---
4 files changed, 155 insertions(+), 34 deletions(-)
create mode 100644 packages/dom/src/normalize-range.ts
[incubator-annotator] 01/02: WIP make describe quote work
Posted by ge...@apache.org.
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 bffbeaf17076905576ef1fcbb91ba0f67f2af787
Author: Gerben <ge...@treora.com>
AuthorDate: Fri Nov 6 22:20:22 2020 +0100
WIP make describe quote work
---
packages/dom/src/seek.ts | 46 ++++++++-
packages/dom/src/text-quote/describe.ts | 163 ++++++++++++++------------------
2 files changed, 112 insertions(+), 97 deletions(-)
diff --git a/packages/dom/src/seek.ts b/packages/dom/src/seek.ts
index c055291..7d7c107 100644
--- a/packages/dom/src/seek.ts
+++ b/packages/dom/src/seek.ts
@@ -18,11 +18,11 @@
* 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>> {
readonly currentChunk: TChunk;
nextChunk(): TChunk | null;
previousChunk(): TChunk | null;
@@ -77,6 +77,28 @@ 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 will follow 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);
+ }
+ if (offset > this.offsetInChunk)
+ result += this.read(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 +164,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 +181,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 };
}
[incubator-annotator] 02/02: Change approach,
(re)implement normalizeRange
Posted by ge...@apache.org.
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 e1df8ed3a3174865f671bd769dc428c6f76f0cb7
Author: Gerben <ge...@treora.com>
AuthorDate: Wed Nov 11 16:54:10 2020 +0100
Change approach, (re)implement normalizeRange
---
packages/dom/src/chunker.ts | 19 ++++-
packages/dom/src/normalize-range.ts | 135 ++++++++++++++++++++++++++++++++
packages/dom/src/seek.ts | 13 ---
packages/dom/src/text-quote/describe.ts | 16 +---
4 files changed, 154 insertions(+), 29 deletions(-)
diff --git a/packages/dom/src/chunker.ts b/packages/dom/src/chunker.ts
index c8e3015..c386403 100644
--- a/packages/dom/src/chunker.ts
+++ b/packages/dom/src/chunker.ts
@@ -75,7 +75,14 @@ export class TextNodeChunker implements Chunker<PartialTextNode> {
private iter: NodeIterator;
get currentChunk() {
- const node = this.iter.referenceNode;
+ return this.nodeToChunk(this.iter.referenceNode);
+ }
+
+ nodeToChunk(node: Text): PartialTextNode;
+ nodeToChunk(node: Node): PartialTextNode | null;
+ nodeToChunk(node: Node): PartialTextNode | null {
+ if (!this.scope.intersectsNode(node))
+ throw new Error('Cannot convert node to chunk, as it falls outside of chunker’s scope.');
if (!isText(node))
return null;
const startOffset = (node === this.scope.startContainer) ? this.scope.startOffset : 0;
@@ -88,6 +95,16 @@ export class TextNodeChunker implements Chunker<PartialTextNode> {
}
}
+ rangeToChunkRange(range: Range): ChunkRange<PartialTextNode> {
+ normalizeRange(range);
+ const startChunk = this.nodeToChunk(range.startContainer as Text);
+ const startIndex = range.startOffset - startChunk.startOffset;
+ const endChunk = this.nodeToChunk(range.endContainer as Text);
+ const endIndex = range.endOffset - endChunk.endOffset;
+
+ return { startChunk, startIndex, endChunk, endIndex };
+ }
+
constructor(private scope: Range) {
this.iter = ownerDocument(scope).createNodeIterator(
scope.commonAncestorContainer,
diff --git a/packages/dom/src/normalize-range.ts b/packages/dom/src/normalize-range.ts
new file mode 100644
index 0000000..32c8bf4
--- /dev/null
+++ b/packages/dom/src/normalize-range.ts
@@ -0,0 +1,135 @@
+/**
+ * @license
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import { ownerDocument } from "./owner-document";
+
+// TextRange is a Range that guarantees to always have Text nodes as its start
+// and end nodes. To ensure the type remains correct, it also restricts usage
+// of methods that would modify these nodes (note that a user can simply cast
+// the TextRange back to a Range to remove these restrictions).
+export interface TextRange extends Range {
+ readonly startContainer: Text;
+ readonly endContainer: Text;
+ cloneRange(): TextRange;
+
+ // Allow only Text nodes to be passed to these methods.
+ insertNode(node: Text): void;
+ selectNodeContents(node: Text): void;
+ setEnd(node: Text, offset: number): void;
+ setStart(node: Text, offset: number): void;
+
+ // Do not allow these methods to be used at all.
+ selectNode(node: never): void;
+ setEndAfter(node: never): void;
+ setEndBefore(node: never): void;
+ setStartAfter(node: never): void;
+ setStartBefore(node: never): void;
+ surroundContents(newParent: never): void;
+}
+
+// Normalise a range such that both its start and end are text nodes, and that
+// if there are equivalent text selections it takes the narrowest option (i.e.
+// it prefers the start not to be at the end of a text node, and vice versa).
+//
+// Note that if the given range does not contain non-empty text nodes, it will
+// end up pointing at a text node outside of it (after it if possible, else
+// before). If the document does not contain any text nodes, an error is thrown.
+export function normalizeRange(range: Range): TextRange {
+ const document = ownerDocument(range);
+ const walker = document.createTreeWalker(document, NodeFilter.SHOW_TEXT);
+
+ let [ startContainer, startOffset ] = findTextNearBoundaryPoint(range.startContainer, range.startOffset);
+
+ // If we point at the end of a text node, move to the start of the next one.
+ // The step is repeated to skip over empty text nodes.
+ walker.currentNode = startContainer;
+ while (startOffset === startContainer.length && walker.nextNode()) {
+ startContainer = walker.currentNode as Text;
+ startOffset = 0;
+ }
+
+ range.setStart(startContainer, startOffset);
+
+ let [ endContainer, endOffset ] = findTextNearBoundaryPoint(range.endContainer, range.endOffset);
+
+ // If we point at the start of a text node, move to the end of the previous one.
+ // The step is repeated to skip over empty text nodes.
+ walker.currentNode = endContainer;
+ while (endOffset === 0 && walker.previousNode()) {
+ endContainer = walker.currentNode as Text;
+ endOffset = endContainer.length;
+ }
+
+ range.setEnd(endContainer, endOffset);
+
+ return range as TextRange;
+}
+
+// Given an arbitrary boundary point, this returns either:
+// - the that same boundary point, if its node is a text node;
+// - otherwise the first boundary point after it whose node is a text node, if any;
+// - otherwise, the last boundary point before it whose node is a text node.
+// If the document has no text nodes, it throws an error.
+function findTextNearBoundaryPoint(node: Node, offset: number): [Text, number] {
+ if (isText(node))
+ return [node, offset];
+
+ // Find the node at or right after the boundary point.
+ let curNode: Node;
+ if (isCharacterData(node)) {
+ curNode = node;
+ } else if (offset < node.childNodes.length) {
+ curNode = node.childNodes[offset];
+ } else {
+ curNode = node;
+ while (curNode.nextSibling === null) {
+ if (curNode.parentNode === null) // Boundary point is at end of document
+ throw new Error('not implemented'); // TODO
+ curNode = curNode.parentNode;
+ }
+ curNode = curNode.nextSibling;
+ }
+
+ if (isText(curNode))
+ return [curNode, 0];
+
+ // Walk to the next text node, or the last if there is none.
+ const document = node.ownerDocument ?? node as Document;
+ const walker = document.createTreeWalker(document, NodeFilter.SHOW_TEXT);
+ walker.currentNode = curNode;
+ if (walker.nextNode() !== null)
+ return [walker.currentNode as Text, 0];
+ else if (walker.previousNode() !== null)
+ return [walker.currentNode as Text, (walker.currentNode as Text).length];
+ else
+ throw new Error('Document contains no text nodes.');
+}
+
+function isText(node: Node): node is Text {
+ return node.nodeType === Node.TEXT_NODE;
+}
+
+function isCharacterData(node: Node): node is CharacterData {
+ return (
+ node.nodeType === Node.PROCESSING_INSTRUCTION_NODE
+ || node.nodeType === Node.COMMENT_NODE
+ || node.nodeType === Node.TEXT_NODE
+ );
+}
diff --git a/packages/dom/src/seek.ts b/packages/dom/src/seek.ts
index 7d7c107..0042ff6 100644
--- a/packages/dom/src/seek.ts
+++ b/packages/dom/src/seek.ts
@@ -181,17 +181,4 @@ 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 8ccf47e..9800d06 100644
--- a/packages/dom/src/text-quote/describe.ts
+++ b/packages/dom/src/text-quote/describe.ts
@@ -45,7 +45,7 @@ export async function describeTextQuote(
range.setEnd(scope.endContainer, scope.endOffset);
return await abstractDescribeTextQuote(
- convertRangeToChunkRange(chunker, range),
+ chunker.rangeToChunkRange(range),
chunker,
);
}
@@ -114,17 +114,3 @@ async function abstractDescribeTextQuote<TChunk extends Chunk<string>>(
throw new Error('Target cannot be disambiguated; how could that have happened‽');
}
}
-
-function convertRangeToChunkRange(chunker: Chunker<PartialTextNode>, range: Range): ChunkRange<PartialTextNode> {
- const domSeeker = new DomSeeker(chunker);
-
- 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;
-
- return { startChunk, startIndex, endChunk, endIndex };
-}