tree e7d2c759f02ee6296e7a48b9b9b80a027e5a0804
parent 1f64d6156d11335c3f22d9330b0ad14fc1e789ce
author CJ Cullen <cjcullen@google.com> 1579627180 -0800
committer Gustavo Niemeyer <gustavo@niemeyer.net> 1579627180 +0000

Optimize cases with long potential simple_keys (#555)

This change introduces an index to lookup token numbers referenced by simple_keys in O(1),
thus significantly reducing the performance impact of certain abusively constructed snippets.

When we build up the simple_keys stack, we count on the (formerly named) staleness check to
catch errors where a simple key is required but would be > 1024 chars or span lines. The previous
simplification that searches the stack from the top can go 1024 keys deep before finding a "stale"
key and stopping. I added a test that shows that this consumes ~3s per 1MB of document size.