Yes, sorry, I didn't mean to imply you didn't do it in your first message. I just stumbled upon that sentence in your second message (as it reminded me very much of what current std documentation does).
I just wanted to emphasize the point that unspecified behavior needs to be specified in one way or the other, as otherwise it's formally or practically UB.
Sorry if I phrased it in a misleading way or put it in the wrong context.
Doesn't this leave the possibility that other functions in std behave differently/unexpectedly until the HashMap is dropped? E.g. there could be a global Weak referencing HashMap's corrupted state, which will cause other functions in std behave oddly. (But perhaps this is a bit far-fetched.)
In my preferred state of affairs, such global state existing should be counted a violation of the ālaws of causalityā ā std and other well-written libraries should be expected to act as if no such global state exists except where it is explicitly documented (e.g. the panic_hook is a piece of global state, as are various OS process-wide concepts like stdin).
First, obligatory reference to http://smallcultfollowing.com/babysteps/blog/2016/05/27/the-tootsie-pop-model-for-unsafe-code/.
Arbitrary misbehaviour of unknown safe code can never cause unsound actions. That's a global rule about unsafe, not something that needs to be specified on everything -- sorting can't be unsound if Ord misbehaves, cloning can't be unsound if Clone misbehaves, formatting can't be unsound if Display misbehaves, etc. (If the called implementation is unsound then the unsoundness is the callee's fault, not the caller's, but unsafe code in the caller must be resilient to anything sound that the callee does.)
And this is actually a very strong rule, because it's unsound to access uninitialized memory and it's unsound to drop the same thing twice. So even if the elements are ZSTs, it's unsound for a HashSet to just magic them up out of nowhere and give you them from, say, its IntoIterator.
If it weren't for our parametricity leaks, then that would actually be enough to prevent the container from ever doing things like returning items that weren't added. This is one of the scary things about specialization -- if all you have is T: Eq + Hash, there's no sound way to create one, but with specialization you could optimize things for, say, u8 to create values out of nothing because you know how to do that, though it's unclear if that would be good.
Vec<i32> is Send, so it can't really do that.
More generally, I wonder if that leads to the true solution here. Data Races are unsound in Rust, as are mutations of anything (without UnsafeCell) held behind a reference. That means that anything that can affect across instances requires intentionally-horrible implementations that use global atomics/locks to store stuff.
Maybe there's a way to phrase this as a provenance-like rule for containers? Like std::collections can make the promise for all the std containers that what you do to one container instance can only affect things derived from that instance (like its iterators and such), but not unrelated instances.
(TBH this is an implied guarantee of everything in order to ever be able to program anything, but I can see how the misbehaviour impacts could be construed to weaken it.)
It was just an example. It could (theoretically) be a thread-local cache that gets reinitialized if you send the values to another thread, or a global state syncronized with mutex.
I know this is likely not what std will ever do, and maybe the examples are far-fetched. But currently s.insert(Wobbly) could affect the values of the Vec (according to documentation), because modifying Vec's is not unsound per-se.
Uh, yes? That's why I said
in the next paragraph.
Did you have thoughts about the general idea I expressed in that section?
Yes I saw, but I wasn't sure if you applied it to the case of Vec since you said that s.insert(Wobbly) cannot modify a Vec through mutating a thread-local state (which I still think could be done if it's a cache that gets reinitialized after sending the Vec). Anyway, these are just examples and I think it doesn't really matter how it's done or how horrible the implementation would be, as long as the documentation allows it to happen. (Just have to think on tricks like take_mut for example.)
Yes, but I felt too unsure to contribute something substantial. Anyway, I thought you made an important point here:
I didn't think of iterators before. I think the tricky part is to correctly phrase what a "related instance" is.
I think this guarantee is explicitly void because of what the Rust reference says:
P.S.: I didn't understand what you wrote here:
I know zero-sized types, but not sure what you mean here. Maybe you can explain.
I have had a case where I considered doing implicit deduplication of certain data in order to save memory (at the expense of execution time). I never actually used it in the end.
I don't think that a global or thread-local cache, for example, must/should be explicitly documented if it doesn't affect the behavior documented. But I'm not sure.
My main problem is that HashSet, HashMap explicitly state that the behavior is not specified, without making any constraints except that it must not be undefined (UB).
This may sound like a strong guarantee at first, but as soon as you rely on the safe code's behavior on some way in unsafe code, it will very quickly (formally) result in UB. (Edit: At least if there is no guarantee at all about the the actions and everything is unspecified except that it's not UB.)
Anyway, I'm not sure, and maybe I am really too nit-picky here. I would also like to say that I'm not really THAT familiar with Rust yet 
, which is why I thought it's best if I bring up this topic here.
P.S.: I'm sorry if I caused more confusion with my responses than clarifying things. Maybe the whole problem isn't that bad. From my perspective, not being so familiar with Rust yet (though I'm learning more every day), a statement that anything in the program can happen, as long as it's not unsafe or unsound or UB, is a pretty hard statement that makes it difficult for me to reason about my program, particularly when I use unsafe in some other places. I'm not sure about when or under which circumstances I could assume that other functions/datatypes/etc. of std are not affected by this "unspecified behavior" or "unpredictable behavior". That is, because the documentation doesn't tell me (or if it does, I cannot find it easily).
This may sound like a strong guarantee at first, but as soon as you rely on the safe code's behavior on some way in
unsafecode, it will very quickly (formally) result in UB.
unsafe code should not rely on safe code's behavior for this exact reason.
Edit: on the second thought, I think I got what you mean: unsafe code cannot even rely on std::collection::HashMap having the "correct" behavior, since K might have a problematic Eq or Hash.
Unfortunately that's not actually possible. In practice unsafe code has to rely on safe interfaces to be correct. After all, 1 + 1 is safe...
What you can't do is trust an unknown implementation of a safe trait. Trusting known upstream safe code is fine, it just includes it as part of the code that you rely on for soundness.
Well, yes, you are right, and I should have expanded that. The thing is that you can't really write some generic unsafe code around HashSet<K> for K, and wrap it in a safe fn interface. (or you have to make more check I guess, but since the behavior is unspecified, you don't even know what to check.)
As I understood it, whenever I use unsafe, I must ensure that whichever unsafe functions or language constructs I use, the prerequisites for them being sound must be met. E.g., if I use get_unchecked on a Vec, then I must ensure that the underlying slice is big enough:
Safety
Calling this method with an out-of-bounds index is undefined behavior even if the resulting reference is not used.
But if I have to assume that Vec can do anything as long as it's not unsafe behavior, then I simply can't do that reasoning. This is why I get irritated when I read something like (I'm exaggerating now, to clarify my point): "If you do this, then it's a logic error and then anything could happen as long as it's not unsafe behavior; we call this 'logic error'. Don't worry, you're still safe, nothing unsafe can ever happen because of this. Just anything else, so don't count on anything anymore (except that there's no memory violation)."
Rust's safety guarantees indeed protect me from certain (worse) errors, namely memory related errors. But this only holds if I don't use unsafe anywhere in my code.
Even worse: If I must always assume that all code can contain logic-errors, then I can't soundly use unsafe at all!
My point that I try to express is that Rust's safety guarantees would act like a "one-shot safety net" if I accept arbitrary non-unsafe behavior in case of logic-errors. (Correct me if I understand it wrong, but let me try to explain.) Some errors are so bad that I lose track what happens in my code, effectively leading to (let me cite the reference here) "erroneous" code and "unpredictable" behavior. Rust's gurantees that as long as I only use code which is not marked as unsafe and as long as all unsafe code is sound, it will make sure this will never lead to one of the things listed in Behavior considered undefined. That's good! But if I'm at that point where everything is unpredictable except that (i.e. if I accept that my error is so bad that reasoning about my program doesn't work anymore), then I can't ensure anymore that unsafe code will be sound.
So I see three options here:
unsafeunsafe might always be unsoundThat is what I mean with one-shot: If an (isolated) part of my program causes an unbound logic-error, then this part would be tainted and cannot use unsafe soundly anymore (edit: as long as that tainted part is involved and the error isn't somehow contained by encapsulation).
The problem with that happening in std::collections would be that std::collections (or even std) gets "tainted", which is bad for writing unsafe code.
So I think that std::collections should not laxly rely on Rust's safety mechanisms (by not specifying what may happen for the sake of forward compatibility), because it will consume this "one-shot" safety net which Rust's safety mechanisms provide us with.
This whole section of the reference should be renamed "Behavior considered unsound".
"Undefined" is simply something that has not been defined. This is what Undefined Behavior means in the C standard, and presumably it's also what it means in Rust. "Sound" is a stronger property than "defined".
Similarly, where HashMap docs say "The behavior resulting from such a logic error is not specified, but will not result in undefined behavior", it means nothing, because the statement doesn't define any behavior, and so, it remains undefined.
What it should really be saying is "will not result in unsound behavior" (or even stronger guarantees, as discussed in this thread).
No it shouldnāt. In fact, the section itself explains the difference in terminology:
It is the programmer's responsibility when writing
unsafecode to ensure that any safe code interacting with theunsafecode cannot trigger these behaviors.unsafecode that satisfies this property for any safe client is called sound; ifunsafecode can be misused by safe code to exhibit undefined behavior, it is unsound.
Sound vs. unsound is not a type of behavior but a property of a piece of code with respect to its public API[1].
which might also be crate-internal API in case itās supposed to uphold the same soundness standards as public APIs ā©ļø
I would disagree here. The fact that it states that the behavior will not result in UB (undefined behavior) explicitly makes clear that anything in the list in "Behavior considered undefined" cannot directly happen as a consequence.
Nonetheless, anything else is possible, which, in combination with some unsafe code, would be unsound and can result in UB. But formally that "unsafe" code would have to be blamed.
The problem here is that std::collections makes this a problem of anyone who wants to use unsafe.
P.S.: Trying to put this in one sentence: How can we soundly use unsafe in an unspecified (but safe) world?
I understand that, I am proposing to expand the use of the delineation "sound / unsound" to the things specified on that page.
Using the word "defined" for the good behaviors and "undefined" for the bad behaviors doesn't really make sense, and doesn't match how C and C++ standards use the terms.
In particular, defining a behavior by saying things like "will not result in undefined behavior" sounds circular, because of this strange approach of defining certain behaviors as as "undefined".
Oh, I see! That sounds like it could be a reasonable idea to discuss.
I think it's not a contradiction per-se. Undefined behavior is defined in the way that you cannot make any reasoning about the program anymore (like a contradiction in math, which can be also described/defined, and where if it's true, anything is true, or false.)
So you could say that some behavior can cause any behavior except a certain set of things (those listed which require unsafe in this instance). The practical value is still very low though, because it's effectively the same as UB.
Right, all I'm saying there should be a different name for that list. "Unsound" seems about right. "We define f(x) to do anything it wants that is sound" makes sense. "We define f(x) to do anything it wants that is defined" is ... weird.
I feel like, for HashMap and similar, the logic errors should simplyTM be restricted to āside-effect-freeā (aka āpureā) behavior. Rust doesnāt have an effects system, but if it did, then HashMapās API could be pure (or ratherā¦ ājust as pure as the Eq/Hash/Hasher implementations involvedā [1]). (Violating the properties of such effects would be considered unsound / ālibrary-UBā.) Then logic errors would be unspecified, but the whole API of HashMap would still be guaranteed to be sound (anything else would be a bug), which means that logic errors would keep side-effect-free functions side-effect-free. (Without having checked it all, I would believe that the entire API of HashMap might be side-effect-free.)
In my mind, modifying global state is a side-effect; as is anything that influences the behavior of any other function/code that doesnāt depend on its result. But e.g. mutation through a &mut ā¦ reference is allowed / not considered a side-effect; as anything that observes the mutation will depend on the result: the fact that &mut ā¦ references are exclusive enforces this kind of dependency. Side-effect-free code can still panic, or not terminate; and (in a logic error case), &mut self method on the HashMap can modify its internal state arbitrarily, resulting in unpredictable behavior of subsequent calls to &self methods (āunpredictableā when compared to their behavior before the last &mut self ā¦ method call). Those can still yield nonsensical results, e.g. incorrectly indicate whether things are or arenāt contained in the HashMap, etcā¦
Iām imagining trait implementations with different effects, similar to the unstable feature allowing things like T: const Eq; and Iām imagining some form of effect-polymorphism so that the function signature could indicate that the (possible) effects of a HashMap API function is just the union of all the effects of the relevant trait implementations ā©ļø