refactor(web): context operations should use a sliding window

[jahorton]

...

Still, it does just move the goalposts. As expected, when I tested with longer documents, I observed linear growth in script time. So this still fails with long documents -- and not all that long really, with just over 1 page of text in a note, I saw 160msec/key event which is barely tolerable. This is on a relatively fast device (for Android), so slower devices would probably be completely unusable with that much content.

The big problem in this whole algorithm is that it is ever scanning the whole document. That's not limited to this one function, but to the whole approach, I think. That seems completely unnecessary: we're never going to have a keyboard that affects more than the last few characters.

We should be working with a sliding window, say 128 code units either side of the caret. Is this possible to achieve? We may still need to iterate through the document once to get our relative code point base for the sliding window but that should be done just once for a keystroke and would then be relatively inconsequential.

I know that all our indexing is by document position, so it may be a significant challenge to rewrite it. But improved algorithms are only going to take us so far and I think we may need to consider this for a full fix.

As noted, this is important... but is also definitely not trivial.

In terms of context passed through to the KeyboardProcessor, there would be little problem. As noted, keystrokes don't ever have that wide a range of effect.

The major pain point would be retooling how suggestions and reversions are applied. The process for both involves comparing the "before" snapshot with the current context state, which gets tricky when context is represented by sliding windows. It does seem possible, though.

I do think we should have a "design" round before making such a change. There are a number of ramifications to think through, especially given how critical context synchronization is when embedded within the mobile apps.

Originally posted by @jahorton in https://github.com/keymanapp/keyman/issues/5248#issuecomment-858198679

[mcdurdin]

Given we are not observing current performance issues here, let's wait on this.

[ermshiperete]

Related to #5312 ?

[jahorton]

Related to #5312 ?

Nah, that has nothing to do with predictive text and everything to do with how the TouchAliasElement operates. It's not exactly an optimized word-processing element.

[mcdurdin]

Although ... good to think about both areas in tandem!

[jahorton]

This is the sort of change that should happen early in a development cycle, by the way. Lots of chances for things to go wrong if something is broken, and I'm not convinced that all possible side-effects would be obvious.

[jahorton]

Before taking in extra constraints specific to our use cases, I believe a major part of this problem can be rephrased as the "longest common substring" problem. When the context window slides, we expect most of the context string to remain intact.

An extra constraint I believe we can impose:

• We expect the "longest common substring" between (old context + recent keystroke transform) and (post-slide context) to lie on one of the two borders for both context variants.
  • We do need to factor in the post-keystroke transform in order to guarantee this.
  • Assumes that we'll never need to align sliding contexts across two context-editing events of different types.
    • I believe that we shouldn't need to handle "across two context-editing events" in general.
      • We certainly invalidate suggestions when a new keystroke is received.
      • When embedded within our mobile apps, the app is generally able to update its context - and even signal the embedded engine afterward - before a new key event would begin.
      • Though... part of me isn't 100% sure that related race conditions are impossible.
  • If new text is added: the "new context" window would "slide right"
    • right-hand side of "old context" should match left-hand side of "new context"
      • left-hand of "old context": holds chars that were previously out-of-window
      • right-hand of "new context": holds newly-typed chars
  • If old text is deleted, pre-caret: the "new context" window would "slide left"
    • left-hand side of "old context" should match the right-hand side of "new context"
      • right-hand of "old context": holds deleted chars
      • left-hand of "new context": holds chars that were previously out-of-window

Note that this one constraint should dramatically reduce the runtime complexity of a would-be dynamic programming approach - we only need to check for matching substrings on the border of both ends. This should give us a O(n+m) time complexity, with n and m being the length of the two strings, rather than the O(n*m) we'd get if the longest substrings could start at any index within both contexts.

While there are faster generalized approaches - via use of a "generalized suffix tree" (as mentioned on the linked Wikipedia page) - that's a data structure I'm less familiar with, one we haven't used anywhere else in the project, and one that's notably more complex than a "start at each end and count" approach. I don't see a need to go "suffix tree" complex here.

[jahorton]

10662 (and its state as of commit https://github.com/keymanapp/keyman/pull/10662/commits/1222b2b3e286fb969aaca1f423289b8a72948a71) may be a useful reference if and when we decide to tackle this issue. It should be particularly be relevant to the most recent comment above this one. Turns out "longest common prefix / suffix" is a pretty useful tool for processing context-window differences even when they aren't sliding.

That said, I imagine that the outcome of the discussion on https://github.com/keymanapp/keyman/pull/10662#discussion_r1480975734 will be relevant to whatever approach ought be taken for sliding window operations as well.