Reduce ambiguous unicode character table

[MichaReiser]

The ambiguous Unicode character table generates by far the most lllvm instructions (1.3% of all generated instructions).

RUSTFLAGS="-Csymbol-mangling-version=v0" cargo llvm-lines -p ruff --lib | head -20

Lines                  Copies               Function name
-----                  ------               -------------
1532601                35211                (TOTAL)
  20559 (1.3%,  1.3%)      1 (0.0%,  0.0%)  ruff[9ef597ff107e57e5]::rules::ruff::rules::ambiguous_unicode_character::CONFUSABLES::{closure#0}
   8800 (0.6%,  1.9%)      1 (0.0%,  0.0%)  <ruff[9ef597ff107e57e5]::codes::RuleCodePrefix>::iter
   7408 (0.5%,  2.4%)      1 (0.0%,  0.0%)  <ruff[9ef597ff107e57e5]::checkers::ast::Checker as ruff_python_ast[47d0f9a8c15cbca1]::visitor::Visitor>::visit_stmt
   6898 (0.5%,  2.8%)      1 (0.0%,  0.0%)  <ruff[9ef597ff107e57e5]::registry::Rule>::noqa_code

I think we can do better by generating fixed arrays that we use for lookups similar to unicode-width or unicode-ident. The input is a mapping from "UTF8" character to the ascii character (ideally, as character and not the number representation).

Why could this work? Because UTF8 only uses a subset of the 4-byte space, the first bit is always 0 for the first byte and always 1 for the following bytes. That means, each byte has at most 128 valid values, and it should be sufficient to have at most 4-128bit tables.

This should also improve performance because it simplifies the lookup to a few bit operations and a static array lookup.

[konstin]

Prior art from rustc: https://github.com/rust-lang/rust/tree/8a7ca936e61d04399198911ee2b07ac110bf17b0/src/tools/unicode-table-generator/src . I'm surprised i didn't find any existing crate for that

[evanrittenhouse]

Out of curiosity, when you say

The input is a mapping from "UTF8" character to the ascii character

Do you mean something like this table, except where we actually maintain a list of character representations instead of number representations? I'm also curious as to why we'd need to generate the arrays at all - could we just used a static list in a consts file or something?

Purely for my own curiosity!

[MichaReiser]

Do you mean something like this table, except where we actually maintain a list of character representations instead of number representations?

Yeah, that's the rough idea I have. I haven't fully worked out the details but I believe something along these lines should be possible.

I'm also curious as to why we'd need to generate the arrays at all - could we just used a static list in a consts file or something?

We can also hand-write the table but my worry is that it becomes hard to understand because you'll have to add up the numbers from up to three table to know which unicode character it maps. That's why I think that having a char -> ascii input table and generating the derived tables is easier to maintain.

[evanrittenhouse]

Hmm, intriguing. I'd be very interested in helping out with this, if you'd like any!

[MichaReiser]

Hmm, intriguing. I'd be very interested in helping out with this, if you'd like any!

That would be awesome and it should be a lot of fun if you enjoy fiddling with bytes. I'll assign the task to you. Let me know if there's anything I can help you with.

[evanrittenhouse]

Sure, there are a few implementation details I'm curious about (I'm pretty new to all the character encoding/byte stuff, so please bear with me. If this would be easier on Discord or something, I can also ping you there!).

1. You mention 4 128-bit tables. What would those actually represent? Why do that instead of just cramming the entire conversion into one table? What would they contain and where do we draw the boundary between each table?
2. Can you please explain the CONFUSABLES map in the rule's current implementation and how we want to adapt that to this new dynamically generated array? It seems like we're suggesting shrinking the 4-byte space down to only the relevant bytes, but not sure how that actually works in practice.
3. How would the input actually map to the lookup table?
4. The Unicode character Ø has a binary representation of 11000011 10011000. I must be misunderstanding the statement "UTF8 only uses a subset of the 4-byte space, the first bit is always 0 for the first byte and always 1 for the following bytes". Do you mind elaborating a little bit?

I haven't gone too deep into the ambiguous_unicode_character rule, so apologies if some of these questions are easily answerable.

E: At a brief glance, it seems like CONFUSABLES contains a character's unicode value and its ASCII counterpart (8232 being a line separator, 32 being a space in ASCII). Is that correct?

[MichaReiser]

E: At a brief glance, it seems like CONFUSABLES contains a character's unicode value and its ASCII counterpart (8232 being a line separator, 32 being a space in ASCII). Is that correct?

That's correct!

Sure, there are a few implementation details I'm curious about (I'm pretty new to all the character encoding/byte stuff, so please bear with me. If this would be easier on Discord or something, I can also ping you there!).

The Unicode character Ø has a binary representation of 11000011 10011000. I must be misunderstanding the statement "UTF8 only uses a subset of the 4-byte space, the first bit is always 0 for the first byte and always 1 for the following bytes". Do you mind elaborating a little bit?

I was actually incorrect, the left most bit is actually 1 for unicode characters. I also don't know the details yet myself. I observed that the first bit (the left most) in every byte is always 1 for unicode characters see Wikipedia. That's why I think that we can use 4 smaller lookup tables (maybe even fewer depending on in which ranges our values fall) that only represent the valid ranges from >0b1000 0000. At least that's what unicodewidth seems to be doing.

Do you want to spend some time trying to figure out the details? If not, then I'm okay with spending some time to figure out the necessary data structure and comment again.

[evanrittenhouse]

To be honest, I'm currently pretty slammed with work stuff and am not sure that I'm able to commit to learning the problem space well enough to design a solution. If it's possible for you to work one out, I'd probably prefer that - if not, I can definitely take a stab at it, but the timeline will probably be increased 😬

[MichaReiser]

To be honest, I'm currently pretty slammed with work stuff and am not sure that I'm able to commit to learning the problem space well enough to design a solution. If it's possible for you to work one out, I'd probably prefer that - if not, I can definitely take a stab at it, but the timeline will probably be increased grimacing

Oh my mistake. It wasn't my intention to pressure you. The timeline isn't really important. This is more of a nice to have. I unassigned you for now, and I'll try to come up with a more detailed design except someone beats me to it.

[charliermarsh]

1.6% on my machine 🤢

  Lines                  Copies               Function name
  -----                  ------               -------------
  1738103                38931                (TOTAL)
    27423 (1.6%,  1.6%)      1 (0.0%,  0.0%)  ruff[58726c95636f7b65]::rules::ruff::rules::confusables::CONFUSABLES::{closure#0}
    10182 (0.6%,  2.2%)      1 (0.0%,  0.0%)  <ruff[58726c95636f7b65]::codes::RuleCodePrefix>::iter
     8094 (0.5%,  2.6%)      1 (0.0%,  0.0%)  <ruff[58726c95636f7b65]::codes::Rule>::noqa_code
     7315 (0.4%,  3.1%)      1 (0.0%,  0.0%)  <ruff[58726c95636f7b65]::checkers::ast::Checker as ruff_python_ast[2ac961f4186054]::visitor::Visitor>::visit_stmt