(Summarized from an in-team discussion)

Since a8eac8c5fb912b76f8e849609644c55a4804662a, separate rules call document.findText individually. Now we have RegExp rules (since 52a22ea9ac3c800a6826ab76131cf85b56c661c0), the question arises whether testing each RegExp individually is fast enough.

We wish to consider the alternative of joining /Foo/, /Bar/, ..., /Baz/ into a single giant RegExp /Foo|Bar|...|Baz/ and executing this to pre-screen whether *any* RegExp rules match a given run of text. If not, there's no need to execute any of the individual rules.

Advantages

• If we have hundreds of RegExp rules, executing one giant RegExp would be much faster than executing each one separately.
• We can assume heuristically that most runs of text do not match any rule (else the config would be burdensome for editors).
• Caching cannot apply on the first run of checks through a document, nor in headless batch mode. This would boost the speed of that case.

Limitations

• No speedup in an edit session (after first run) for unmodified paragraphs, because results are cached.
• No speedup if any of the RegExps match the paragraph.
• Heuristically, most edits are in a single paragraph,
• So no speedup in the common case where the editor is modifying a paragraph that matched a suggestion.

Possible architecture

const pool = new ve.dm.TextFinderPool();
regExpRules.forEach( ( config ) => {
    const finder = new RegExpTextFinder( config.regExp, pool );
    //...
} );

• Each RegExpTextFinder registers itself with the pool.
• The pool maintains a giant disjunction RegExp ( the /Foo|Bar|...|Baz/ ), using techniques to avoid things like backreference issues.
• Before checking a text, the finder asks the pool to prescreen it.
• The pool only checks once per text (by caching results).
• The complexity is isolated inside the pool code.

Results of exploration

For suggestions while editing a long article, the "giant disjunction" method gives some speedup for the initial scan. However it fails in the case where speed is most important: i.e. when the paragraph being edited matches some check.

We tried a giant disjunction that captures every matching branch, achieved with zero-width lookahead:

/(?=(?<rule1>ab.d)?)(?=(?<rule2>ghi)?)(?=(?<rule3>a.cd)?)/g

However when we benchmarked, that only executed 33% faster than the raw individual RegExps, and the bookkeeping took more time than we saved (see comment).

A fast algorithm

While thinking about this, we found a fast algorithm that could handle many thousands of RegExps even on an entry-level Android phone. However it would be complex to implement, test and benchmark. Therefore we will not take implement this for the time being. Here is a description of the algorithm, for future reference:

1. Thousands of RegExps are stored in a pool that tests all of them at once.
2. Each RegExp has a temperature: can be "hot" (=has matched recently) or "cold" (=has not matched for a while). We measure this by tracking the number of tests since the last match: a higher number means a cooler temperature, so 0 is hottest (like the original Celsius scale). This is heuristically useful, since in the case where speed is most important, the user is editing a paragraph and we are rechecking. Therefore a recent match is a great predictor that the next test may match.
3. Cool RegExps are periodically grouped into buckets of say 50, and a bucket disjunction formed:

bucket.regExp = new RegExp( bucket.regExps.map( ( regExp ) => `(?:${ regExp.source })` ).join( '|' ) )

4. Subsequently, if bucket.regExp.test( line ) is false (which is likely) then none of the constituent RegExps matched: we don't have to check them individually.
5. Cool enough buckets can themselves be grouped into buckets of buckets, meaning eventually all sufficiently cold RegExps can be tested with a single bucket.regExp.test.
6. If any bucket tests positive, it is broken open into its constituent parts (each of which may be a RegExp or a bucket) which are tested individually. The one (or occasionally more) that tests positive has its temperature reset to zero. The rest continue to have their temperature incremented and will therefore be eligible for rebucketing.

We assume the heuristics that for a single paragraph being edited, at most a few RegExps will match, and the set of matching RegExps won't change much between keystrokes. Therefore most of the RegExps will quickly become cold and get bucketed. We could start with a temperature > 0 so the bucketing happens more swiftly or even immediately on startup.