Document why *ring* does not use traits to model algorithm choice

[briansmith]

For example, why doesn't ring have a DigestAlgorithm trait that is implemented by types named SHA256, SHA384, etc.? Why is everything dynamically dispatched instead of parameterized on types and statically dispatched? How does the current design avoids unnecessary heap usage and minimizes code size. That means we have to verify that there is actually a code size savings relative to the type parameterization and static dispatching approach that people seem to expect in Rust.

[briansmith]

Reconsider this after the placement box stuff is stable: rust-lang/rfcs#1228

[briansmith]

It looks like the whole placement new stuff is being tracked in rust-lang/rust#27779. I asked about how to resolve the issues that ring has run into with Traits in rust-lang/rust#27779 (comment).

[briansmith]

See also https://www.ralfj.de/blog/2015/10/12/formalizing-rust.html: Traits are not in the subset of Rust that they are hoping to define semantics for and/or prove correct.

[briansmith]

See https://internals.rust-lang.org/t/pre-rfc-thinness-as-a-property-of-the-data-rather-than-the-trait/2794, https://internals.rust-lang.org/t/blog-post-extended-enums-and-thin-traits/2755, https://internals.rust-lang.org/t/blog-post-extended-enums-and-thin-traits/2755, http://smallcultfollowing.com/babysteps/blog/2015/10/08/virtual-structs-part-4-extended-enums-and-thin-traits/.

[briansmith]

Now in ring::signature we are using traits. And, of course, it creates a problem: We cannot always say &'static signature::Algorithm but instead have to say &'static (signature::Algorithm + Sync) when referencing algorithms from other statics, because of Rust type system weirdness.

[briansmith]

Now in ring::signature we are using traits. And, of course, it creates a problem: We cannot always say &'static signature::Algorithm but instead have to say &'static (signature::Algorithm + Sync) when referencing algorithms from other statics, because of Rust type system weirdness.

And, it was so awkward I ended up implementing wrapper types to hide the traits.

Separately, I already had to explain this a bit on IRC:

briansmith> right now, you can use ring with "use ring;" or "use ring::{submodule, submodule, submodule};" and everything works.
20:30 But, as soon as you use traits, that stops working, because you need to import the traits too.
20:31 And also, in ring we usually use polymorphism to select between algorithms.
20:31 And so, usually, every implementation of each trait would only have one implementation, each.
20:32 So, instead, in ring I basically emulate per-object (vs per-trait) polymorphism.
20:34 IMO, it is something that should be fixed in the language: when a type implements a trait, it should be able to say "when I am in scope, the trait should also be in scope."
20:34 but, that's not the case yet.
briansmith

[Diggsey]

It looks like VerificationAlgorithm extends Sync now - doesn't that solve the problem with verbosity? And is the requirement to import traits separately really a show-stopper?

With function pointers, the algorithm structs become much larger than the double-pointer sized &'static Algorithm, and it becomes difficult to add more trait implementations like Debug in future, without introducing even more inefficiencies. It also prevents downstream crates from extending the set of possible algorithms.

From a security perspective, storing multiple function pointers in writable locations on the stack also seems much more dangerous than a reference to a vtable in read-only memory.

[briansmith]

It looks like VerificationAlgorithm extends Sync now - doesn't that solve the problem with verbosity?

Yes.

And is the requirement to import traits separately really a show-stopper?

It's a real usability problem. But, it's not worse in ring than it is in other APIs.

With function pointers, the algorithm structs become much larger

It doesn't matter, because there is only one copy of every Algorithm, so I don't think it creates any bloat.

it becomes difficult to add more trait implementations like Debug in future

Not really, because the best implementation of Debug for Algorithm types is just to output the name of the algorithm and omit the details anyway.

It also prevents downstream crates from extending the set of possible algorithms.

True. OTOH, we don't have to worry about external crates' implementations when we refactor the code, because of this. People can contribute implementations of new algorithms to ring if they want more algorithms supported.

From a security perspective, storing multiple function pointers in writable locations on the stack also seems much more dangerous than a reference to a vtable in read-only memory.

Very true, but the compiler should be able to put them in read-only memory since they are all static and not static mut, just like trait vtables. I'm not sure if the compiler actually does this, though.

[burdges]

There is an RFC somewhere to allow types to bring trait methods into scope. I forget where or what the syntax is, but maybe something like struct MyStruct: MyTrait+Sync where ... And no movement recently.

[Diggsey]

It doesn't matter, because there is only one copy of every Algorithm, so I don't think it creates any bloat.

Ah, some of my arguments were based on the mistaken assumption that Algorithms were passed around by value.