`BitStringRef` that works with `Cow`

[tarcieri]

In #1998 the lifetime was removed from OctetStringRef by making it a slice newtype, which to simplify looks something like pub struct OctetStringRef([u8]), and in practice used as &OctetStringRef.

What's really nice about this it means we can impl Borrow<OctetStringRef> for OctetString and ToOwned for OctetStringRef, and with that we can use Cow<OctetStringRef>.

We discussed several times whether it would be possible to do this for BitStringRef too and at the time I couldn't figure out a way. I looked into trying to put the unused bits in a tagged pointer but that won't work since we need to construct them from &[u8]. However the other place we can stick the information is in the length part of the fat pointer by using it to store the length in bits instead of bytes.

Concretely that might look like pub struct BitStringRef([UnsafeCell<()>]) where the length of that inner slice represents a number of bits.

Here's a POC of the idea:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=e162511e707fe74c8f9f7731972acd32

cc @baloo @dishmaker

(Thanks to #dark-arts for some help here)

[tarcieri]

Open questions: is this actually sound? I saw a suggestion here something similar may not be valid under stacked borrows: ferrilab/bitvec#283 (comment)

I guess I can run my POC by Miri and cargo careful to start with.

[dishmaker]

I think we're spending too much time and unsafe tricks on the Cow issue. Let's just add BitStringCow which could be changed to something like:

type BitStringCow<'a> = Cow<'a, BitStringRef>

in later versions of der.

And for now it could be an enum.

[tarcieri]

I think this solves it (I believe bitvec already does a similar trick), and really this was the only one I couldn't previously think of a good solution for. I would definitely like to get the second opinion of some experts on the topic though regarding soundness, though UnsafeCell<()> is a ZST and therefore slices can't refer to invalid memory so long as the pointer (which is tied to the lifetime of the reference) is valid.

I'd really like to avoid adding bespoke Cow-alike types. We can change pretty much all of the string types to work with Cow as well.

[tarcieri]

Here's a draft PR that implements the basic functionality: #2300

Edit: uhoh, looks like a stacked borrows failure!

[tarcieri]

So, #2300 passes with -Zmiri-tree-borrows, but not under stacked borrows. My first instinct is to give up, particularly as implementing this would require a breaking change to der. It just seems rather scary to implement a core zero copy data structure used in cryptography applications using an approach that could, in any manner, be considered unsound.

I came back to this issue as I was working on and just about ready to ship pkcs5. We are currently in the position where I could ship a der v0.9 with breaking changes because very few things have been released that depend on der v0.8 (just sec1 and spki I believe) but as soon as I start shipping pkcs* that window will likely close for quite sometime.

This whole area in particular seems like an open opsem question: rust-lang/unsafe-code-guidelines#256

Unfortunately ASN.1 BIT STRING just happens to be one of the most fundamental core data structures in cryptography, being baked in to X.509 Subject Public Key Info which is one of if not the most pervasive public key format on the Internet. Being able to represent it with a Cow-friendly ref/owned type pair where the ref type can be implemented as a reference-to-reference conversion from &[u8] sure would be nice.

I am quite conflicted by this and I guess I will just keep asking around for advice, but as I mentioned earlier I'm much less excited about the prospects of a breaking der v0.9 now.

[tarcieri]

Alright, I'm going to close this for now, especially as we've already shipped der v0.8 and trying to do anything here would require breaking changes, in addition to the soundness being somewhat unclear:

rust-lang/unsafe-code-guidelines#134

I opened an IRLO issue to discuss this sort of data type and how it could be soundly implemented:

https://internals.rust-lang.org/t/bitslice-or-a-sound-way-to-implement-one/24194/6

I'd say we can revisit this in a hypothetical forthcoming der v0.9.

In the intervening time I guess we can look into making a special Cow type in der which works with our RefToOwned/OwnedToRef traits, and try to get rid of that in the next breaking release.