Autocorrect error

[drashna]

Wasn't sure where to ask, specifically. But if i's seeing this error, I'm assuming that it's because I've hit the limit of what the current autocorrect code can handle for the trie structure?

  File "[...]/qmk_firmware/lib/python/qmk/cli/generate/autocorrect_data.py", line 188, in traverse
    assert 0 <= backspaces <= 63
           ^^^^^^^^^^^^^^^^^^^^^
AssertionError

[getreuer]

Good question. Cool to see you pushing the limits of Autocorrect! =)

This error means that the typo entry would require more than 63 backspaces to remove the incorrect letters before send-string'ing the correction, long enough that it exceeds what the serialization format can represent. I presumed this was a "this will never happen" sort of error path, but now in hindsight, I wish this had a proper error message and context, something like

if backspaces > 63:
  print('Error: Typo entry with more than 63 backspaces is unsupported.')
  print(f'{typo} -> {correction}')
  sys.exit(1)

The limit comes from how I serialized the trie nodes. There are 3 kinds of nodes: chain nodes, branching nodes, and leaf nodes. It costs 2 bits per node to identify its kind. I packed this node kind identifier metadata into the top 2 bits of the first byte, leaving the lower 6 bits for the node itself. For a leaf node, these 6 bits are where the number of backspaces is stored. This is where the 63 backspaces limit comes from.

E.g. in the docs is this example of encoding a leaf node, where the "128" is the leaf node kind identifier and "3" is the number of backspaces:

For fitler, we need to tap backspace 3 times (not 4, because we catch the typo as the final ‘r’ is pressed) and replace it with lter. To identify the node as a leaf, the two high bits are set to 10 by ORing the backspace count with 128:

+-------+-------+-------+-------+-------+-------+
| 3|128 |  'l'  |  't'  |  'e'  |  'r'  |   0   |
+-------+-------+-------+-------+-------+-------+

[drashna]

Well, looks like I'm not pushing the limits quite yet.

Though did find an edge case. It looks like if you have the same string for both the incorrect and corrected entry, it generates the error. Eg, 0 backspaces. And it doesn't seem to catch this until it's trying to build the trie array.

As for limits, added ~500 more words, so I'm up to about 3500 words (and about 54kB array). And filterpaper lead me to some other lists (and roughly 5k words)

Also, adding a bunch of more words, having the english_words module makes it a PITA.

A bit of testing shows that this works to at least tell you what entries are bad:

           if backspaces > 63:
                cli.log.error('{fg_red}Error:{fg_reset} Typo entry with more than 63 backspaces is unsupported: "{fg_cyan}%s{fg_reset}" -> "{fg_cyan}%s{fg_reset}".', typo, correction)
                maybe_exit(1)
            if backspaces <= 0:
                cli.log.error('{fg_red}Error:{fg_reset} Typo entry with no backspaces is unsupported: "{fg_cyan}%s{fg_reset}" -> "{fg_cyan}%s{fg_reset}".', typo, correction)
                maybe_exit(1)

Edit: Oh boy, this looks like it's something more complicated. Yay.

But at least the code above helps

[drashna]

Huh, yeah, it looks like it's simply the number of entries that is the issue for me. 4069 entries seems okay, but even mone more, and it just .... chokes.

Traceback (most recent call last):
  File "/Users/drashna/.local/share/uv/tools/qmk/lib/python3.13/site-packages/milc/milc.py", line 609, in __call__
    return self.__call__()
           ~~~~~~~~~~~~~^^
  File "/Users/drashna/.local/share/uv/tools/qmk/lib/python3.13/site-packages/milc/milc.py", line 614, in __call__
    return self._subcommand(self)
           ~~~~~~~~~~~~~~~~^^^^^^
  File "/Users/drashna/repos/qmk_firmware/lib/python/qmk/cli/generate/autocorrect_data.py", line 268, in generate_autocorrect_data
    data = serialize_trie(autocorrections, trie)
  File "/Users/drashna/repos/qmk_firmware/lib/python/qmk/cli/generate/autocorrect_data.py", line 237, in serialize_trie
    assert 0 <= byte_offset <= 0xffff
           ^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Correction, it looks like the array size for me is 65525.... It's almost like 65536 is a magical number (or .... 0xFFFF)

[getreuer]

That's a good point about typo == correction being an edge case. It would be good to explicitly detect and warn/error about such entries.

Though did find an edge case. It looks like if you have the same string for both the incorrect and corrected entry, it generates the error. Eg, 0 backspaces. And it doesn't seem to catch this until it's trying to build the trie array.

I'm confused about the 0 backspaces. Based on the "assert 0 <= backspaces <= 63" line (code link), it looks like a backspaces value of 0 gets serialized without raising an error?

Looking at the logic, could it be that backspaces is negative in some edge case discussed here?...

word_boundary_ending = typo[-1] == ':'
typo = typo.strip(':')
i = 0  # Make the autocorrection data for this entry and serialize it.
while i < min(len(typo), len(correction)) and typo[i] == correction[i]:
    i += 1
backspaces = len(typo) - i - 1 + word_boundary_ending
assert 0 <= backspaces <= 63

Details of what this formula is intending to do:

• i is counts the number of common chars between the start of typo and start of correction, so that typo[:i] == correction[:i]. Therefore, the number of differing chars is len(typo) - i.

• When a typo is typed, Autocorrect catches it as the final key is pressed, and if so, Autocorrect returns false to block that key event. So the number of backspaces to emit is one less: len(typo) - i - 1.

  • An exception to this off-by-one adjustment is when the typo ends with a word boundary :. In this case, Autocorrect yet returns true so that whichever word-breaking ended the word still gets processed after the correction is made.

Also, adding a bunch of more words, having the english_words module makes it a PITA.

Sorry! The search code is essentially this lame, unoptimized Python loop:

for word in correct_words:
    if typo in word:
        # error

This was expensive to begin with, and I can imagine at 3500 words that this lookup is costing a lot of time. For sake of investigation, I'd add an early return in check_typo_against_dictionary to skip the search.

Probably there are more performant ways of doing this type of string search in Python.

[drashna]

I was wrong about the backspaces part.

The issue is that it's limited to 0xFFFF, and I'm guessing the data structure is limited to that too.

My dictionary size is sitting at 65525.
https://github.com/drashna/qmk_userspace/blob/83b54bc407b5ea2a247462add93d2c31e5605906/users/drashna/autocorrect_data.h#L4101-L4103

I'm sure I could probably reduce the library size but what fun is that.