search

chromium / subspace

A concept-centered standard library for C++20, enabling safer and more reliable products and a more modern feel for C++ code.; Also home of Subdoc the code-documentation generator.
https://suslib.cc
Apache License 2.0
89 stars 15 forks source link

Vec::kMovedFromLen is non-zero #250

Closed nigeltao closed 1 year ago

nigeltao commented 1 year ago

https://github.com/chromium/subspace/blob/4273d92da22dd5f8fd9eef83aad76049be4df155/subspace/containers/vec.h#L291-L297

and

https://github.com/chromium/subspace/blob/4273d92da22dd5f8fd9eef83aad76049be4df155/subspace/containers/vec.h#L745-L746

Because kMovedFromLen is non-zero, you're setting the Slice with a nullptr data_ but non-zero len_. This is bad (and also violates the (unwritten??) invariant that length <= capacity), right?

Is the fix just changing kMovedFromLen from 1_usize to 0_usize?

danakj commented 1 year ago

length > capacity signals the vector is moved from:

https://github.com/chromium/subspace/blob/56ceccdc4b048826c9c47b8b1bcceb6f129993c8/subspace/containers/vec.h#L740-L743

danakj commented 1 year ago

Added some more comments in https://github.com/chromium/subspace/commit/09d95e9c4b74850140ac26e3bb9d25974a7442e8

nigeltao commented 1 year ago

Thanks for more comments.

Vec::operator[] does not check(!is_moved_from()). It only does check(i < len()) and Vec::len also does not check(!is_moved_from()). Ditto for Vec::get or anything else defined in slice_methods.inc.

Therefore, if (i < v.len()) doStuffWith(v[i]); can still dereference a nullptr, right? If the T element type is a struct with a field f, then IIUC &(v[0].f) will get me a non-nullptr pointer with value offsetof(T, f), without needing sus::marker::UnsafeFnMarker, right? Is this WAI (Working As Intended)?

I assume that it's an explicit design decision that "a moved-from Vec" is in an invalid state, not a valid-but-empty state?

nigeltao commented 1 year ago

Just a suggestion / thinking-out-loud (but I am not a C++ expert):

If you want to keep the notion of moved-from being a detectable "invalid state", without the len > cap 'violation', perhaps an alternative representation is (ptr = p, len = 0, cap = 0), where p is some static non-nullptr void*.

nigeltao commented 1 year ago

get me a non-nullptr pointer with value offsetof(T, f)

I don't seem to have permissions to re-open this issue, and I'm not sure if closed issues get updates, so I spun out this question as https://github.com/chromium/subspace/issues/254

length > capacity signals the vector is moved ... an alternative representation is (ptr = p, len = 0, cap = 0)

Another idea: either approach above is possibly premature sizeof(Vec) optimization. Simpler is adding a bool is_moved_from_ field.

danakj commented 1 year ago

perhaps an alternative representation is (ptr = p, len = 0, cap = 0), where p is some static non-nullptr void*

A problem with this is that nullptr + 0 is okay but invalid_ptr + 0 (or using it in any other arithmetic) is UB. Which is okay if literally everything checks, but this type of check (lifetimes, basically) can't as easily be elided as bounds where the compiler can see the values.