This reverts commit 88008cd8ca.
Revert "Bug 2012637 - part 8: Make `nsContentUtils::ComparePoints` handle `TreeKind::Flat` and `TreeKind::FlatForSelection` correctly r=smaug,dom-core"
This reverts commit 73e6f6587b.
Revert "Bug 2012637 - part 7: Make `RangeUtils::CompareNodeToRangeBoundaries()` use `nsContentUtils::ComparePoints` with valid point in the tree r=smaug"
This reverts commit 6985d5e80f.
Revert "Bug 2012637 - part 6: Make `nsRange::CutContents()` convert the range boundaries to the ones in the DOM before comparing r=smaug"
This reverts commit 73b585af3d.
Revert "Bug 2012637 - part 5: Delete the default template parameter of `nsContentUtils::ComparePoints` and relatives r=smaug,dom-core"
This reverts commit 1a7f24e5b5.
Revert "Bug 2012637 - part 4: Make `nsContentUtils` use `nsIContent` for taking a child node as a parameter r=smaug"
This reverts commit a6ea8d6824.
Revert "Bug 2012637 - part 3: Add template `nsINode` API which can switch to call API from `TreeKind` r=smaug,dom-core,webidl"
This reverts commit a4211e9df0.
Revert "Bug 2012637 - part 2: Add `TreeKind::FlatForSelection` and change the template parameter of `ChildIteratorBase` to `TreeKind` r=smaug,dom-core"
This reverts commit 0241749ee7.
Revert "Bug 2012637 - part 1: Make `ChildIterBase` template class to re-implement `FlattenedChildIterator` for DOM, Flat and FlatForSelection TreeKind r=smaug,dom-core,layout-reviewers,emilio"
This reverts commit 9e71cb77fb.
They accept any kind of points even if it does not match with the
template parameter's `TreeKind` because the caller wants to check the
relation in different kind of tree. Therefore, any callers need to
consider the `TreeKind` more carefully and clarify the `TreeKind` makes
developers easier to find a bug.
Differential Revision: https://phabricator.services.mozilla.com/D281308
The range-based approach for creating a text directive uses the word breaker algorithm
to identify where to split between `start` and `end` term. If the range ends with a word
which is over 50% of the length content, the algorithm would return wordEnd=length,
which would result in the `end` term being empty, which is not allowed.
This patch fixes this case by choosing the word begin position in this case.
Differential Revision: https://phabricator.services.mozilla.com/D263867
The range-based approach for creating a text directive uses the word breaker algorithm
to identify where to split between `start` and `end` term. If the range ends with a word
which is over 50% of the length content, the algorithm would return wordEnd=length,
which would result in the `end` term being empty, which is not allowed.
This patch fixes this case by choosing the word begin position in this case.
Differential Revision: https://phabricator.services.mozilla.com/D263867
Most changes are automated. Relevant bit is dom/.clang-format. I had to
manually disable clang-format in a few places where importing external
files and so on that aren't self-contained, and fix a couple includes /
forward declarations.
Differential Revision: https://phabricator.services.mozilla.com/D256800
Bug 1976480 introduced a special code path if the target range only consists of punctuation.
However, this new code path did not "normalize" the boundary points, ie. moving them to
the actual text node. Therefore, the target range could contain empty blocks
(such as an empty <td>), which would then trigger range-based matching.
This patch adds normalizing to the target range in case of punctuation-only ranges.
Differential Revision: https://phabricator.services.mozilla.com/D259037
This patch adds a new check in the beginning of the algorithm which leaves the
input range unchanged if its content is only punctuation characters.
This edge case is handled by checking if all characters are punctuation and would return early, hence not going into the algorithm that extends the range to word boundaries
(which would become more complex trying to achieve the same).
Additionally, this patch contains a minor refactoring: Other edge cases in the input range
(empty range, whitespace-only ranges) are moved into the function that extends the
range to word boundaries.
Differential Revision: https://phabricator.services.mozilla.com/D258246
In some edge cases (eg. boundary point already at end of block), the algorithm would
return the length of the reference string as common substring length (instead of 0).
This is fixed by moving the actual common length computation part out of the loop
(which in some conditions may not run).
Differential Revision: https://phabricator.services.mozilla.com/D258057
The patch for Bug 1976473 changed the behavior of the algorithm to collect word boundary distances
to merge punctuation characters with the preceding word. However, this led to unexpected behavior if a
context term only consisted of punctuation, where this function would unexpectedly return an empty array.
This patch makes sure that the returned list of word boundary distances is always non-empty
by appending the total length of the context term, which simplifies the next steps of the algorithm.
This change required some adaptations to an early-return condition where an empty word boundary distance list
indicated an edge case where the target range is too long for exact matching,
but doesn't contain a word boundary (for which we refuse to continue).
This check is now moved into a previous stage of the algorithm, where it should have been in the first place.
Differential Revision: https://phabricator.services.mozilla.com/D257943
Constructing an `nsFind` instance involves running non-trivial code.
In rare edge cases this can accumulate and shows up in profiles.
Differential Revision: https://phabricator.services.mozilla.com/D256176
The previous approach limited the amount of words which are considered
for creating context terms.
This affects only the latter part of the algorithm (identifying the best candidate).
However, in rare edge cases finding the common strings can already be time-consuming.
Therefore, the cutoff metric has been changed to a maximum context term length,
with an empirically set value of 1024 chars per context term.
Differential Revision: https://phabricator.services.mozilla.com/D256174
Before this patch, the end term for
range-based matching could have been
created wrongly, resulting in potentially
wrong or longer-than-necessary
text directives. This was due to a bad
handling of start and end term word distances,
which used a wrong offset.
This patch removes the first / last word of
the start / end terms before computing the
common substring lengths with other matches,
therefore setting the offsets to 0 instead of
`length of the first/last word`. Additionally,
whitespaces are taken into account correctly.
Differential Revision: https://phabricator.services.mozilla.com/D252964
Before this patch, the 5 second timeout was applied
to each range individually. In some edge cases,
the number of ranges could be large. And even if
creating a text directive for a single range was
very fast, the accumulated time for all ranges
could exceed the 5 second limit.
This patch changes the watchdog to run
globally instead of per range, therefore
cutting off the whole process of creating
a text directive after 5 seconds.
It is not feasible to create a test case for
the timeout watchdog, hence there are
no changed tests.
Differential Revision: https://phabricator.services.mozilla.com/D252946
This is a pure refactoring commit, no functional changes are expected.
As a drive-by, this patch also renames
`TextDirectiveCreator::ExtendRangeToBlockBoundaries()`
to reflect what it actually does (which is extending to
_word_ boundaries).
Differential Revision: https://phabricator.services.mozilla.com/D251285
This patch introduces an algorithm which compares
all potential candidates against all available matches.
A candidate is defined as a combination of word-bounded
distances in the context terms.
A match is defined as the common substring lengths
of all relevant context terms.
A valid candidate must exceed the match in at least
one dimension.
For exact matching, the only relevant context terms
are prefix and suffix.
For range-based matching, two runs are required:
The start match uses prefix and start.
The end match uses end and suffix.
Differential Revision: https://phabricator.services.mozilla.com/D246196
Search the partial document to find all
other matches for the content of the target range.
Then, for these matches, compute and save the
common lengths of the context terms.
For range-based matching, this needs to be done
separately for the start term and the end term.
Differential Revision: https://phabricator.services.mozilla.com/D246195
The distances are always in search direction:
For prefix and end terms, the positions are
relative to the end of the term and use the word
start boundary.
For start and suffix, they are relative to its
beginning and use the word end boundary.
Differential Revision: https://phabricator.services.mozilla.com/D246194
This patch converts all required context around the target range
into normal and fold case string representations.
Prefix and suffix terms can reach until the next block boundary.
For exact matching, the whole target range content is used for
the Start term, the End term is empty.
If there are block boundaries in the target range,
the start term defined by the sub range until the first
block boundary is reached, and the end term is defined
by the sub range starting at the last block boundary.
If the range is longer than the threshold,
its content is split in the middle.
Differential Revision: https://phabricator.services.mozilla.com/D246193
Range-based matching has to be used if
- there is a block boundary in the target range
- the range content is too long.
This commit introduces sub classes for the
`TextDirectiveCreator` class, which are implemented
to correctly create exact and range-based matching
text directives in the following patches.
Differential Revision: https://phabricator.services.mozilla.com/D246192
For range-based matching, the previous matches were determined incorrectly:
The `start` match must be matched until the end of the `start` of the target range,
and the `end` match must be matched until the end of the `end` of the target rage.
Before this change, the `start` of the target range was always considered as a
match to eliminate, therefore producing wrong results.
Differential Revision: https://phabricator.services.mozilla.com/D240131
Filtering non-matching candidates is the biggest
perf bottleneck in the algorithm to create a
text fragment, especially if the user attempts to
create a text fragment for a very common string
on a very large page.
Since the expensive code only does string comparisons,
it can easily be moved to rust and run in parallel
using rayon.
Differential Revision: https://phabricator.services.mozilla.com/D235559
This is a prerequisite commit, which moves the `nsString*` members of the
`TextDirectiveCandidate` C++ class into a bindgen-exposed Rust struct.
Differential Revision: https://phabricator.services.mozilla.com/D235558
`nsContentUtils::ComparePoints()` already has a cache which
keeps the last 100 indices in a stack-allocated array.
This patch makes use of this cache in the hot path.
Differential Revision: https://phabricator.services.mozilla.com/D235557
The algorithm to collect all occurrences of the
search string used to resize its search range after each match.
`nsRange::SetStart()` is an expensive call,
because it calls `nsContentUtils::ComparePoints()`.
However, `nsFind` uses the collapsed `nsRange`s
`aStartPoint` and `aEndPoint` to determine the search range.
Therefore, the code can be updated to accept range boundaries
instead, and to create the collapsed ranges locally.
Differential Revision: https://phabricator.services.mozilla.com/D235555
Profiling has shown that for extreme cases
hash table lookups of the `RangeContentCache`
implementation could take a considerable amount of time.
Additionally, the design of returning a pair of strings
for a pair of ranges was awkward and rather unintuitive.
This patch reorganizes the cache.
The cache now contains the fold case representations as
`UniquePtr<nsString>` and returns constant raw pointers,
which are kept alive by the cache lifetime.
This allows to implement a much more intuitive
`GetOrInsert()` method, which accepts one `nsRange*`,
and returns one `const nsString*`.
Additionally, the `TextDirectiveCandidate` objects now
keep these raw pointers as members.
This way the hash table lookups are only required when
a new object is created that contains changed ranges.
Otherwise, the strings can be accessed directly.
These measures eliminate the hash table lookups
from the performance profiles entirely.
Differential Revision: https://phabricator.services.mozilla.com/D235382
This patch introduces the `TimeoutWatchdog` helper class
and checks at certain points in the algorithm
whether the timeout is hit, and aborts the
algorithm if necessary.
Differential Revision: https://phabricator.services.mozilla.com/D235539
Jan-Niklas Jaeschke