RFC: Why #[deriving(IterBytes)], not #[deriving(Hash)]?

[bblum]

I anticipate a lot of "GEE I WONDER WHY I DIDN'T THINK OF THAT" when newcomers come into the channel asking how to make their types hashable, since the hash trait has some weirdo type signature, and the answer is "Derive this other typeclass you've never heard of before."

Why can't we just make it be #[deriving(Hash)]? It also makes already-written code more legible.

[graydon]

Because deriving(Hash) won't be deriving ... a hash function. It'll be deriving a way-to-iterate-over-your-fields to feed to the hash function. The hash function is in a central location and very carefully chosen.

That said, we could probably rename it somehow. A lot of the ugliness in the way hash is implemented had to do with missing features in default methods and inheritence, which I think all work now.

[nikomatsakis]

As an aside, I still think IterBytes and Encodable are the same thing.

[graydon]

They're certainly related. Not sure if identical? I guess encoding is supposed to hit all the "meaningful" bytes and skip the "meaningless" ones. Maybe we could build a default method on the encode trait that funnels all the other encoding methods (including a prefix byte for each tycon) into a byte stream? Essentially a "default encoder" that delegates to an inner function with a byte slice?

Or, I guess, hash could provide that encoder itself. But I bet it's useful elsewhere.

[nikomatsakis]

To put it another way, it seems like iterbytes could be trivially implemented in terms of encodable, but encodable provides higher-level information. The only reason I see to separate them is that perhaps there are bits of data that one wants to encode but which do not affect the value when used as a hash; but I think this is subtle and a bit error-prone. I would personally be inclined to separate out the "hash key" value from the rest, in such cases. Also, this last bit presumes that IterBytes is only used for hashing, which is currently true afaik, but not obvious from its name. I guess I personally would rather just have one way of serializing types into bytes (the Encodable trait) and then use that for multiple purposes than to have many distinct serialization traits.

[thestinger]

By implementing IterBytes, you currently give up the ability to supply a custom Hash implementation. I don't think we have the machinery to implement a default method for types implementing a trait at the moment. It might make sense to move it into the hash module and change the naming to reflect it being the standard way of making a type hashable.

[erickt]

@nikomatsakis: It shouldn't be that hard to reimplement the IterBytes trait in terms of Encodable. I can think of one big issue with it though. Encodable doesn't guarantee the output is ordered in any fashion. It would make sense for HashMap to implement Encodable, but it probably wouldn't make sense to support generating a hash for that structure because `Encodable doesn't guarantee order in the output.

However, it would be nice for us to add a raw binary Encoder/Decoder. This would be handy for libraries like extra::flatpipes that can guarantee we are encoding/decoding the type so we don't need a binary format that tags each piece of data for type checking deserialization, like ebml.

[nikomatsakis]

@erickt I'm not sure what you mean by "doesn't guarantee ordering"? In my head, at least, most of the methods are in fact ordered (i.e., a tuple must try to encode each of its elements in order, a struct each of its fields, etc), but I guess the higher-order methods for emitting a map might not be. I was envisioning creating a "HashEncoder" that just hashed data in response to calls to the encoder methods. Still, now that we have deriving modes, it doesn't hurt to have them be separate interfaces, and I can imagine it might allow for looser or more efficient encoding around maps and other data structures that are not obviously ordered. I cared about this more when there was no deriving for iterbytes.

[erickt]

@nikomatsakis: Yeah, I'm talking about the higher ordered methods for emitting a map. For example:

let a = HashMap::new();
a.insert(1, 2);
a.insert(3, 4);
let a_bytes = io::with_bytes_writer(|wr| a.encode(&BytesEncoder::new(&wr)));

let b = HashMap::new();
b.insert(3, 4);
b.insert(1, 2);
let b_bytes = io::with_bytes_writer(|wr| b.encode(&BytesEncoder::new(&wr)));

That hypothetical BytesEncoder won't necessarily guarantee that the keys are outputted in the same order, so while a equals b, a_bytes may or may not equal b_bytes.

If we wanted to prevent someone from using a HashMap as a key, we add a simple Hashable trait:

trait Hashable {
    fn hash(&self) -> uint;
}

We could then either use #[deriving(Hashable)] that depends on an implementation of Encodable, or we could start using default methods to do the same thing. Assuming this would actually work, we could mash together Hashable and Encodable into one HashableEncodable trait with a default method like this:

trait HashableEncodable: Hashable + Encodable {
    fn hash(&self) -> uint {
         let hash_encoder = HashEncoder::new();
         self.encode(&hash_encoder);
         hash_encoder.hash
    }
}

Then to use it, we just write:

#[deriving(Encodable)]
struct Foo { ... }

impl HashableEncodable for Foo {}

This would save us from having to write another deriving syntax extension. HashableEncodable is pretty ugly though, so I'm a little torn.

[huonw]

(fwiw, writing new derivings is fairly easy.)

[erickt]

@huonw: It's true, but I worry that deriving is a crutch. Writing a new deriving extension isn't that hard, but it is a royal pain to do the snapshot dance if the underlying trait changes. I hope that someday we'll figure out some mechanism to lift deriving out of the compiler and into a library. I expect that would remove the need to do the snapshot dance, and it'd be much easier for third parties to add their own implementations.

[huonw]

They're normal syntax extensions, so #1762 should cover that (if/when that happens).

[emberian]

This is pretty messy. Should be fixed.