Add traits w/ auto-deriving for soundly serializing/inspecting/transforming rustc types.

[eddyb]

Currently, we're limited to the general-purpose Eq, Ord, Hash, Encodable and Decodable traits, even though the compiler often has more unconventional desires, involving contexts and custom behaviors.

There are several special-purpose traits already in the compiler, such as AST/HIR Folder/Visitor and the two-in-one TypeFoldable (which also does visiting).

Also, #36551 adds a specialization mechanism in the bundled rustc_serialize to work around the fact that Encodable and Decodable have their methods be generic over the encoder/decoder instead of the trait, but this abuses the yet-unclosed lifetime soundness hole in specialization (#31844):

impl<'a, 'tcx> SpecializedDecoder<Ty<'tcx>> for DecodeContext<'a, 'tcx> {...}

That impl requires that the 'tcx of the decoded Ty match the 'tcx of the decoder, but this cannot be enforced through specialization as the lifetime relationships do not exist before monomorphization.

A better solution would involve custom traits that can dispatch over the decoder w/o specialization, i.e.:

impl<'a, 'tcx> Decodable<DecodeContext<'a, 'tcx>> for Ty<'tcx> {...}

To make all of this ergonomic, auto-deriving is necessary, and I believe macros 1.1 (perhaps helped by a permanent switch to rustbuild) can make it happen.

Last but not least, it may be possible to generalize encoding/decoding and visiting/folding/relating into a single (or a pair of) abstraction(s), but I'd have to leave that to someone who understands tree folding, transducers, and perhaps Haskell lenses, although there's no guarantee they map nicely to Rust.

cc @rust-lang/compiler

[nikomatsakis]

Nominating for discussion next week. In this week's compiler team meeting, @arielb1 raised concerns about leaving (ab)uses of unsound specialization in the compiler, which I am sympathetic to. It'd be good to figure out how we can prioritize moving away from that.

[eddyb]

I believe we can reduce our deriving needs to a single "ShapeReflect" trait with 4 operations:

• Self -> (fields...)
• &Self -> (&fields...)
• &mut Self -> (&mut fields...)
• (fields...) -> Self

Even without VG we can build implementations of all sorts of operations we need (such as Relate which does (&T, &T) -> Result<T, E>) out of this one trait + specialization.

EDITs:

• my intution appears to hold except for needing rust-lang/rfcs#1672.
• only requires an extra trait to do the associated type dispatch.
• we can side-step VG with the HList pattern.
• we can probably do something similar for First | Rest, using an enum with two variants
• I've been informed that Haskell has come up with this before (of course)