Don't use external node ids in crate metadata

[brson]

I believe one of the reasons linking is so flaky right now is because we encode data about external crates using their external node ids, which are not stable.

For example if crate A uses type foo from crate B, when we write A's metadata we will refer to foo as node 3048 (for example). When B is recompiled foo will probably get a different node ID, while A still refers to the old ID.

When we later link a different crate to crate A the metadata reader runs off the rails chasing bogus node ID's in crate B.

Here's what I think is the easiest way to fix this within the current design:

1. define a new cryptographic hash, node_hash, that hashes the type signature and path of a node
2. when we write a crate's metadata, we also write a table that maps from the node hash to the node id
3. when we write a crate's metadata, we also write a table that maps all used external def ids to node hashes
4. when looking up a node in crate B via crate A we first translate A's notion of B's node id to the node hash, then look up the node hash in crate B to find the actual, current node id.

[catamorphism]

Nominating for milestone 5, production-ready

[pcwalton]

We're calling this "def ID drift" and it's disrupting Servo a lot.

[graydon]

accepted for production-ready milestone

[pnkfelix]

Accepted for P-low.

[metajack]

This does not seem to be a problem for Servo these days.

[emberian]

Rust now gives better warnings when libraries start to drift out of date, and I haven't observed def id drift in practice for quite some time now. This is still an issue, though.

[steveklabnik]

A lot has changed in a post-cargo world. Is this still true? Can we get a reproduction?

[arielb1]

We now reference dependencies by-hash, making relying on internal NodeIds perfectly fine (that's it, until we decide on a [stable-ey] metadata ABI).