optimize dynamic regex matching

Authored by cullmann on Mar 13 2020, 7:02 PM.



allow such matches to be cached, too, by guarding the cache
with the last used captures

makes VHDL highlighting instantanious for bug 418778

BUG: 418778

Test Plan

make && make test

example from bug 418778 is fast!

Diff Detail

R216 Syntax Highlighting
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.
cullmann created this revision.Mar 13 2020, 7:02 PM
Restricted Application added projects: Kate, Frameworks. · View Herald TranscriptMar 13 2020, 7:02 PM
Restricted Application added subscribers: kde-frameworks-devel, kwrite-devel. · View Herald Transcript
cullmann requested review of this revision.Mar 13 2020, 7:02 PM

For the example from the bug this makes the difference between ~30 seconds on a 4 Ghz machine to << 1 second ;=)

dhaumann accepted this revision.Mar 13 2020, 9:48 PM

I guess this is OK, but the concept of a "skip offset" is a bit fuzzy to me.


I dislike this protected hack :-)

This revision is now accepted and ready to land.Mar 13 2020, 9:48 PM
mwolff added a subscriber: mwolff.Mar 14 2020, 7:47 AM

Let me try to explain the skip offset idea (it's been years since I came up with this in GeSHi :) )

A code highlighter will repeatedly ask all highlight contexts and items therein to find the closest token to highlight next to the current cursor position.
The closest token will win and then the highlighter will repeat its question at the position after the token.
For regular expressions, it's often cheaper (as indicated by this patch once again), to match the line once starting from the current position and then remember where the first match - if any - is in the current line.
Then, the next time the highlighter asks for a token position, we can check the last matched position. This is essentially the skip offset - i.e. we know that we can skip querying the regexp again until the cursor position is beyond the next match.

Dominik, does this clear things up?

Thanks yes, maybe you can add a comment to the skipOffset, Christoph :)

First let's have this, the current state is bad ;=)


That is called inheritance ;=)
I first had a virtual function, but this is much easier and faster. (and just costs a few bytes)

This revision was automatically updated to reflect the committed changes.