Using std::collections and unsafe: anything can happen

[jbe]

@tczajka

2. Unambiguous spec. The idea that the collection can randomly change at any time is quite ambiguous to me (e.g. does that mean that a Vec that is inside a struct inside that collection can suddenly start changing too?).

That's where I would concur mostly. It doesn't seem to be easy to find an unambiguous (but generic/open/relaxed) spec.

Not sure I agree on the two other points though. In regard to 1., some sloppy/informal wording might be simple (but maybe ambiguous, yeah ), and in regard to 3., I'm not sure if you ever should or need to rely on a collection behaving properly when the underlying Hash implementation is broken. And if you do, you could take some "specialized collection in a seperate crate", as you suggested in the opposite context .

[tczajka]

@jbe

3., I'm not sure if you ever should or need to rely on a collection behaving properly when the underlying Hash implementation is broken

Simple quick example: you write a function that takes a s: HashSet<T> for any T. You preallocate s.len() entries, then iterate over the collection and fill those entries using get_unchecked_mut indexing, assuming that there won't be more than s.len() entries.

Perhaps not super practical because collect already exists on iterators, but just to give an example.

[CAD97]

HashSet doesn't offer any way to do this, nor does BTreeMap. The closest you can get is creating a set with MaybeUninit slots and initializing those... in which case you're not giving the collection access to the potentially buggy trait implementation during initialization. (And the transmute to remove the MaybeUninit wrapper is unsound.)

I do believe that it is possible to write code that uses a generic map/set and relies on it not misbehaving for soundness, but most examples are going to be quite artificial (an unsafe assert rather than actually relying on a property). The most realistic I can think of is using a side table map and relying on the consistency of that.

But that's broken even by reasonable misbehavior. I can't think of a non artificial example which would work with a stricter form of misbehavior but fail with the weak "anything that doesn't violate encapsulation" misbehavior.

EDIT: I misread the comment originally.

It does seem somewhat reasonable to at least say that methods which are not bound on the traits cannot misbehave.

[tczajka]

Here is example code I had in mind:

pub fn convert_hash_set_to_array<T: Default>(h: HashSet<T>) -> [T; 10] {
    assert_eq!(h.len(), 10);
    let mut res: [T; 10] = Default::default();
    for (index, elem) in h.into_iter().enumerate() {
        // Safety: index < 10 because we have asserted h has 10 elements.
        // OOPS!
        unsafe { *res.get_unchecked_mut(index) = elem };
    }
    res
}

I don't think it has to do with whether methods are bound on the traits or not. For instance, I could similarly write generic code that calls insert on a HashSet of any type, and assumes that len() will increase by 0 or 1, rather than by 27 -- and insert is bound by traits.

[quinedot]

@jbe

P.S.: Note that my OP does not only refer to std 's documentation though, but also to the Rust reference, which also makes very unconstrained statements in describing the impact of wrong Hash or Eq implementations:

The reference is explicitly non-normative.

[jbe]

@quinedot

The reference is explicitly non-normative.

Yeah right, I also mentioned that in my OP, as I learned it recently :

@jbe

I am aware that this is a rather hypothetical problem, and will not pose any issue in practice. Moreover, the Rust reference is non-normative. (Not sure about the documentation of std though.)

But even being non-normative, it can still contain mistakes/errors that should be fixed, of course. Afterall, we're talking about documentation problems in both cases: std and the reference, as I think we agree that the case outlined by my example does not happen in practice (and likely will never happen in the future either).

However, my conclusion was/is wrong then:

@jbe

So it isn't really just a problem of std.

Yet, even if Rust's encapsulation model (of which we have no normative reference other than the source code) would protect us from std doing weird stuff outside std, then a std that may go berzerk (according to its own documentation) is bad enough .

We could say that an error in non-normative documentation or other documentation that nobody believes in is not a problem… but… I think it should be fixed in both cases.

---

P.S.: Actually the reference being non-normative just means that it has to be fixed in regard to the actual behavior. So even if std will not be fixed, the reference would need be fixed to clarify that not the whole program behavior is unpredictable but std's behavior. Not sure if that would make things better.

[CAD97]

I opened a PR for std to bound misbehavior:

Put a bound on collection misbehavior

[steffahn]

@CAD97

I opened a PR

this makes writing user unsafe code that utilizes std theoretically impossible, as it now relies on undocumented QOI that unrelated parts of std cannot be caused to misbehave by a misuse of std::collections APIs.

What’s “QOI”?

---

Even web search is no help so far. E.g. Wikipedia only lists

Qoi or QOI may refer to:

• QoI or quinone outside inhibitors, a type of fungicide
• QOI (image format)
• Qoi, Tibet
• Qoi fish or Koi

Please try to avoid obscure abbreviations/initialisms (or at least include an explanation on first use case)?

[CAD97]

Ah sorry I've got C on the brain from phantomderp's twitter. QOI = Quality Of Implementation. (First non-card result for "define QOI" on Google does show this use for me: https://acronyms.thefreedictionary.com/QOI)

[jbe]

What does "encapsulated to the X that observed the logic error" mean? Would it cover iterators, for example?

I saw you mentioned:

This is not meant to be formal; a formal refinement would likely need to mention that values derived from the collection can also misbehave after a logic error is observed, as well as define what it means to "observe" a logic error in the first place.

"Encapsulated" (as I read it) implies that the misbehavior can't "escape". But I'm not really familiar with terminology.

Perhaps one can assume that the usual "encapsulation" rules of Rust apply here, so it's probably not a problem.

[simonbuchan]

I would say the description of the various associated types makes it pretty clear they could be affected by a invalidated collection, eg hash_map::Entry and Drain are introduced as:

A view into a single entry in a map

and

A draining iterator over the entries of a HashMap.

Both of these make it clear they are exposing internals of a collection, so transitively would expose the unspecified behavior with the current deliberately general wording.