pre-RFC: a new symbol mangling scheme

[Centril]

cc:

Issue: Simplify symbol version mangling

[tromey]

Many projects, like GDB, will not want to have a Rust dependency

Yes, it’s pretty unlikely IMO that gdb or binutils would accept a Rust dependency. At the same time, I think it’s not important to worry about this. Someone, probably me, will write a demangler for use here.

One other thing I’d like to point out is that c++filt already has hacks in place for Rust – it’s not the case that the current scheme is sufficiently C+±like to just work. In fact these hacks don’t go far enough (there’s also a patch thread somewhere that goes deeper into this).

[jsgf]

If one were to take that seriously, then I’d propose using zstd with a standard dictionary computed over some corpus of existing Rust symbols. That would get much better compression than gzip/zlib. And it would be better to use some larger base; at least use the full available character set.

This avoids quines causing infinite loops

Already a huge risk with compression - you can set up exponential explosions with small inputs.

[zackw]

I think it would be wise to make the standard Rust mangling scheme(s), whatever they end up being, intentionally incompatible with the standard C++ mangling scheme(s) used on the same target. This is because, if you have C++ and Rust components linked into the same program, the linker should not resolve a call to extern void foo(int, int) as targeting pub fn foo(i32, i32) -> () unless the author of the latter specifically declared it pub extern "C++".

[m4b]

I don’t have time to give any kind of detailed response but I just wanted to say, to paraphrase Spock: I have been, and always shall be, a friend (to rust defining and owning it’s own principled name mangling scheme).

Good luck! And I look forward eagerly to any resolutions on this front

[michaelwoerister]

A Rust mangled symbol, starting at the version code (dropping the _R only), compressed with gzip and encoded with base32.

I’d be interested in how much better this would be than the Itanium compression scheme. The basic principle of Itanium and gzip is the same: Build up a “dictionary” of things that have already been encountered and emit the “keys” instead of the data for subsequent occurrences. But I guess the more advanced derivations of LZ77 (like zstd and even DEFLATE) have some more tricks up their sleeve that could provide better compression.

EDIT: It looks like zstd with its prepopulated dictionary would indeed be a great fit here. Who knows, maybe we’d really like to have this as a fallback for really long symbol names at some point :)

[rocallahan]

The C++ ad-hoc substitution scheme is a nightmare. It’s a ton of complexity to figure out what a substitution actually maps to, and it’s not even clear how substitutions are to be interpreted. See https://github.com/itanium-cxx-abi/cxx-abi/issues/68 for example.

[rocallahan]

Having fixed a number of bugs in the cpp_demangle crate, I personally think that the Itanium ABI mangling is horrendous, though some of that is C++ madness. But it would be great to have a standard Rust mangling scheme.

• Define a precise AST for demangled names and be careful to describe what the productions mean.
• Define the serialization and ensure the grammar is trivial to parse. The Itanium ABI requires lookahead in some places. No more than 1 token please.
• Ensure it’s easy to extend the grammar unambiguously without hacks.
• Make the compression as simple as possible. I would suggest defining tokenization of mangled names, and then compressing using backreferences to ranges of tokens.
• Avoid smuggling in other kinds of references, like the Itanium ABI template-parameter references (T_ etc).

[michaelwoerister]

Thanks for the feedback! That’s very helpful.

The C++ ad-hoc substitution scheme is a nightmare.

The core algorithm (minus template parameter references) does not seem too ad-hoc to me. It seems like a reasonable way of implementing a dictionary coder for an AST. Is your criticism directed at the core algorithm or at the concrete way it’s applied by the Itanium mangling?

• Define a precise AST for demangled names and be careful to describe what the productions mean.

The reference implementation I’m working on uses an AST and defines compression in terms of the AST. So I think we should be covered here?

Define the serialization and ensure the grammar is trivial to parse. The Itanium ABI requires lookahead in some places. No more than 1 token please.

The current implementation does not need more than 1 character look-ahead needed.

Make the compression as simple as possible. I would suggest defining tokenization of mangled names, and then compressing using backreferences to ranges of tokens.

Can you describe this in more detail? It seems like that would take up more space because you have to encode too numbers for a range, instead of just one number for a dictionary index. It also seems like it might make the compression algorithm more complex (while making decompression simpler).

[rocallahan]

Is your criticism directed at the core algorithm or at the concrete way it’s applied by the Itanium mangling?

Maybe “ad-hoc” isn’t the right phrase, but because only a subset of AST productions are counted when enumerating substitution targets, that subset has to be known to any tool processing mangled names. That seems like unnecessary complexity to me.

The reference implementation I’m working on uses an AST and defines compression in terms of the AST. So I think we should be covered here?

Sure, as long as it’s clearly specified.

The current implementation does not need more than 1 character look-ahead needed.

Great! I hope you have a way to ensure that remains true as the specification evolves.

Can you describe this in more detail?

No, you’re probably right that referring to AST nodes is a better option so you don’t have to encode a length.

OTOH a downside of AST nodes is you need to have a clear processing model that precisely describes what kinds of nodes are allowed in what contexts … and those constraints need to be faithfully implemented. E.g. if you have an AST node <ident>, and a substitution references that node where you’re expecting an <expression>, depending on how your AST works you may or may not promote that <ident> to the right variant of your Expression AST node. Token or string backreferences would have the appealing property that that’s all handled by existing code in the parser.

[michaelwoerister]

Yes, deciding what goes into dictionary in which order is a bit tricky. I hope that the Rust version is a bit simpler than the C++ version because the AST is simpler.

It’s a bit of a trade-off between implementation difficulty and compression ratio. My hope is that a clean reference implementation that can be easily ported will alleviate the problem somewhat.

[rocallahan]

I actually think having at least two independent implementations is important to making sure the spec is accurate and complete, i.e. that bugs in the reference implementation don’t become de-facto spec.

If compression ratio is really important then I think you need a methodology for evaluating different alternatives over a good test corpus and actually measure the impact of different alternatives. We’ve all seen formats that tried to introduce DIY compression based on intuitions and made some really bad decisions (hello DWARF!). You’ll want to determine the maximum set of ASCII symbols you can use, and use them all. You probably should also figure out exactly what “human readability” means to you and push right up against that boundary.

[eddyb]

I’m not sure a range would need two numbers, as long as each possible subtree is self-contained and self-terminating.

E.g. the start of a polish notation subtree is enough to determine its entire range, as each prefix fully determines the shape its children take.

Also, byte offsets would allow relatively efficient zero-allocation demangling, if I’m understanding correctly, whereas tokens would require a separate tokenization step.

[michaelwoerister]

I actually think having at least two independent implementations is important to making sure the spec is accurate and complete, i.e. that bugs in the reference implementation don’t become de-facto spec.

Good point.

If compression ratio is really important then I think you need a methodology for evaluating different alternatives over a good test corpus and actually measure the impact of different alternatives.

Such a test corpus should not be too hard to get by.

You’ll want to determine the maximum set of ASCII symbols you can use, and use them all.

I personally would like to stick to A-Za-z0-9_. Others in this thread have expressed a preference of allowing symbols to be UTF-8.

You probably should also figure out exactly what “human readability” means to you and push right up against that boundary.

This is a tricky one. Here’s are some examples from the reference implementation test cases:

• _RN7std_xxx3fooITNS_3BarES1_ES2_EE:
  std[xxx]::foo<(std[xxx]::Bar,std[xxx]::Bar),(std[xxx]::Bar,std[xxx]::Bar)>
• _RN7std_xxx3fooFINMNS_4QUUXE3barINS0_3BARSEEEEE:
std[xxx]::foo<std[xxx]::QUUX::bar<std[xxx]::foo::BAR>>
• _RNXlN7foo_xxx3BarIxEE4quuxF1_Cs_IcEE:
  <i32 as foo[xxx]::Bar<i64>>::quux::{closure}'2<char>

As soon as definitions get nested, it’s almost impossible to demangle the name in your head. And compression makes it worse still. So I’d say anything Itanium-based is past human readable except for simple cases. Although one can still glean some useful information from a mangled - which might be all we are interested here.

I guess a good next step would be to collect a test corpus of symbol names for trying out compression schemes.

[newpavlov]

I wonder if can take a step back, give up on a symbol mangling completely, and instead use simple IDs (either auto-incremented or hash-based) with a separate file which will include table for debuggers to use. If I am not mistaken, it will be something similar to .pdb files used in Windows. Or is there an additional motivation for mangling except a desire to keep all information in one file?

[michaelwoerister]

@newpavlov This is basically what debuginfo already provides (not just on Windows). However, you don’t always have debuginfo available.

[newpavlov]

I guess my point is that trading debugability of stripped binaries to a significantly simpler symbol construction algorithm (which also IIUC as a nice bonus will result in a somewhat smaller binaries) is not a bad compromise to take.

[michaelwoerister]

I think we’ll want to provide the option in the compiler to emit completely opaque symbols (something like plain 160bit hashes) for this case. But I don’t think that that would be a good default.

[michaelwoerister]

For anyone interested: I opened the actual RFC

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.