Streamline `Symbol`, `InternedString`, and `LocalInternedString`.

[nnethercote]

We currently have three closely-related symbol types.

Symbol is the fundamental type. A Symbol is an index. All operations work on that index. StableHash is not implemented for it, but there's no reason why it couldn't be. A Symbol can be a gensym, which gets special treatment -- it's a guaranteed unique index, even if its chars have been seen before.

InternedString is a thin wrapper around Symbol. You can convert a Symbol to an InternedString. It has two differences with Symbol.

• Its PartialOrd/Ord/Hash impls use the chars, rather than the index.
• Gensym-ness is ignored/irrelevant.

LocalInternedString is an alternative that contains a &str. You can convert both Symbol and InternedString to LocalInternedString. Its PartialOrd/Ord/Hash impls (plus PartialEq/Eq) naturally work on chars. Its main use is to provide a way to look some or all of the individual chars within a Symbol or InternedString, which is sometimes necessary.

I have always found the differences between these types confusing and hard to remember. Furthermore, the distinction between Symbol and InternedString is subtle and has caused
bugs.

Also, gensyms in general make things a lot more complicated, and it would be great to eliminate them.

Here's what I would like as a final state.

• Symbol exists.
• InternedString does not exist.
• LocalInternedString perhaps exists, but is only used temporarily when code needs access to the chars within a Symbol. Alternatively, Symbol could provide a with() method (like InternedString currently has) that provides access to the chars, and then LocalInternedString wouldn't be needed.
• Symbol's impl of Hash uses the index, and its impl of StableHash uses the chars.
• Not sure about Symbol's impl of PartialOrd/Ord. If a stable ordering is really needed (perhaps for error messages?) we could introduce a StableOrd trait and use that in the relevant places, or do a custom sort, or something.
• Gensyms don't really exist. They are simulated: when you call gensym(), it just appends a unique suffix. It's worth noting that gensyms are always identifiers, and so the unique suffix can use a non-identifier char. And Interner could keep a counter. So "foo" would gensym to something lke "foo$1", "foo$2", etc. Once the suffix is added, they would just be treated as normal symbols (in terms of hashing, etc.) I would hope that identifier gensyms would never be compared with non-identifier symbols, so a false positive equality match should be impossible. (Different types for identifier symbols and non-identifier symbols would protect against that, but might cause other difficulties.) Alternatively, syntax_pos::symbol::Symbol::gensym() is incompatible with stable hashing. #49300 talks about other ways of dealing with gensyms.
• All this should also help performance, because we'd end up with more operations on indexes, and only the necessary ones on chars (which require TLS lookups).

I haven't even touched on the way lifetimes work in the interner, which are subtle and error-prone. But having fewer types would only make improvements on that front simpler.

Thoughts?

CC @petrochenkov @Zoxc @eddyb @Mark-Simulacrum @michaelwoerister

[petrochenkov]

StableHash is not implemented for it, but there's no reason why it couldn't be.

Small correction: StableHash is implemented for Symbol, see impl<'a> HashStable<StableHashingContext<'a>> for ast::Name in impls_syntax.rs.

(ast::Name is an alias of Symbol conventionally used for identifier symbols (in AST/HIR/etc. coming from token::Ident, lowered from ast::Ident.))

[michaelwoerister]

In general, I'm in favor of simplifying the setup here (and properly documenting it in the process). The main problem here, from the point of view of incremental compilation, is that gensym depends on the state of the entire crate, so changing something in one source file will change gensyms in (potentially) all other source files. As long as gensym indices are generated from a global counter, every tiny change will look to incremental compilation as if you'd renamed half things in your code base.

I think that:

• the gensym stuff should be factored out of the string interning infrastructure entirely (there's no fundamental reason to intertwine the two), and
• gensym index generation should use a more stable scheme rather than a global counter.

[petrochenkov]

I'm all for reducing the number of types if that's possible.
I'd rather use a separate "stable" set of operations/traits used by incremental (and query?) infra, than introduce separate types that have to leak into all other parts of the compiler, if that's possible.

I'm not sure the scheme with simply incrementing a session-local counter will work for gensyms.
Gensyms can come from metadata from other crates, encoded as strings and "foo$3" from other crate may mean entirely different thing than "foo$3" based on the local counter.
Perhaps appending long enough hashes will work better.
Anyway, I think the proper solution is to use hygiene and move gensymness from Symbol to Ident, so I'm not sure any intermediate solutions would improve significantly enough on the current situation to implement them. (But you can certainly try.)

[michaelwoerister]

StableHash is not implemented for it, but there's no reason why it couldn't be.

Small correction: StableHash is implemented for Symbol, see impl<'a> > HashStable<StableHashingContext<'a>> for ast::Name in impls_syntax.rs.

(ast::Name is an alias of Symbol conventionally used for identifier symbols (in AST/HIR/etc. coming from token::Ident, lowered from ast::Ident.))

Ah, interesting. I think the real problem is actually that StableHash must be equivalent to PartialEq, that is:

• x == y implies stable_hash(x) == stable_hash(y), and
• x != y implies stable_hash(x) != stable_hash(y).

That second condition makes it more strict than Hash (i.e. no hash collisions are allowed). I going to open PRs trying to document this.

[nnethercote]

I tried doing the "foo$3" approach but bootstrapping failed very early on with blatant bugs in name resolution. I suspect it's a dead end for the reasons mentioned above.

I agree that moving the gensym stuff from the symbol/interning level to the ident level sounds like the right idea. (Plenty of the interned strings are not identifiers.) What would "use hygiene" look like for dealing with gensyms? I know that Spans can have a hygiene element, but I don't know what data would be added to the hygiene element.

[petrochenkov]

What would "use hygiene" look like for dealing with gensyms? I know that Spans can have a hygiene element, but I don't know what data would be added to the hygiene element.

"Gensym span" == Span::def_site() of a unique freshly introduced macro.
This means a unique fresh outer_mark in SyntaxContextData specifically.

Most of gensyms used in the compiler (those introduced by built-in derives or desugarings) don't even need the "unique fresh" part, they can just use Span::def_site() of the macro/desugaring they are introduced by.

A relevant recent thread - #60106.

[nnethercote]

I think the proper solution is to use hygiene and move gensymness from Symbol to Ident

#60903 is a first step: it moves the gensym operations from Symbol to Ident. (The gensym implementation details are still within Interner.)

[matthewjasper]

So I've had a look through the code and done some experimentation with replacing gensyms with hygiene. To give a summary

Don't need to be unique identifiers at all

As far as I can tell, these don't escape into the AST, so the gensym call is unnecessary:

rust/src/libsyntax/ext/tt/macro_rules.rs

Lines 255 to 256 in 50a0def

	let lhs_nm = ast::Ident::from_str("lhs").gensym();
	let rhs_nm = ast::Ident::from_str("rhs").gensym();

I also can't see the point of the module declared here:

rust/src/libsyntax/diagnostics/plugin.rs

Line 124 in 50a0def

let name = Ident::from_str_and_span(&format!("__register_diagnostic_{}", code), span).gensym();

Refactor out of existence

This gensym avoids an assert, before it get converted to an interned string. It could be removed now, but there's probably a larger set of refactorings around type/lifetime parameters so that we aren't using the name of a parameter to determine whether it's Self or not.

rust/src/librustc/hir/lowering.rs

Lines 2712 to 2716 in 50a0def

	let ident = if param.ident.name == keywords::SelfUpper.name() {
	param.ident.gensym()
	} else {
	param.ident
	};

Once the async fn desugaring can be moved to HIR lowering, we can also avoid gensyms there.

Could be replaced with _

This doesn't really avoid the gensym, so much as make someone else do it.

Subject to a decision on #61019, we could use _ as the rename instead.

rust/src/libsyntax/std_inject.rs

Line 72 in 50a0def

(orig_name_ident.gensym(), Some(orig_name_sym))

Likewise, we could use _ here as well:

rust/src/librustc_resolve/build_reduced_graph.rs

Line 317 in 50a0def

Some(Ident::from_str_and_span("__dummy", new_span).gensym()),

Can use hygiene

Making built in derives have def-site hygiene appears to work (from some simple testing). format_args! appears to be similar.

Don't have an associated macro

Global allocators, tests and proc macros have AST passes that use a gensym to hide a global module. We could use hygiene, but we don't have a mark associated to a macro expansion, so the compiler will ICE here:

rust/src/librustc_resolve/build_reduced_graph.rs

Line 761 in 50a0def

let def_id = self.macro_defs[&expansion];

Tests

Here we run in to trouble with because the obvious way to add hygiene runs into the problem with this code:

#![feature(decl_macro)]

macro a() {
    pub struct A;

    mod module {
        use super::A; // Fails to resolve, since the the context of `A` is stripped when we try to resolve it in the root.
    }
}

a!();

Resolve and _

Finally we use gensyms to allow multiple items called _ in the same module. I'm not sure what the motivation for using gensyms rather than a special case in resolve is. But this seems to be the case that is most likely to need "gensym spans"

[michaelwoerister]

Wow, nice write-up, @matthewjasper!

[eddyb]

Global allocators, tests and proc macros have AST passes that use a gensym to hide a global module. We could use hygiene, but we don't have a mark associated to a macro expansion, so the compiler will ICE here:

Could we get the Mark from the fact that in all of these cases there is an attribute?
And perform all the work as expanding that attribute?

[matthewjasper]

There's one attribute per test. Since a user isn't obligated to write at least one test we don't necessarily have a mark but we still have to hide the main test runner function.

Global allocators could probably use the attribute.

[petrochenkov]

I global allocators can be formulated in terms of a proc macro, that would be great (one less special case).

If not, then we can create fresh marks for them (Mark::fresh, which is already used in various non-macro places, even too liberally perhaps), it just needs to be "registered" in resolve, so it has a module parent and other associated data, and doesn't ICE on attempts to access them.

[eddyb]

@matthewjasper You can make --test inject a #![test] on the crate (or #![test_harness] etc.)
I don't remember who was working in this area, but there were some plans to make it all less magical, for various reasons (fixing bugs and allowing custom test harnesses) - cc @Manishearth