typst / ecow

Compact, clone-on-write vector and string.
Apache License 2.0
208 stars 16 forks source link

Replace `Sentinel` with `Self::dangling()` for uninitialized `EcoVec` #28

Closed Kmeakin closed 1 year ago

Kmeakin commented 1 year ago

This allows EcoVec::new() to be const.

I believe this is safe. All tests pass with cargo miri test, and I have given my reasoning in the comments. It also does not make EcoVec::as_slice() any more expensive.

codecov-commenter commented 1 year ago

Codecov Report

Patch coverage: 100.00% and project coverage change: +0.03% :tada:

Comparison is base (9aa2b9e) 91.59% compared to head (46ff467) 91.62%.

:exclamation: Your organization is not using the GitHub App Integration. As a result you may experience degraded service beginning May 15th. Please install the Github App Integration for your organization. Read more.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #28 +/- ## ========================================== + Coverage 91.59% 91.62% +0.03% ========================================== Files 3 3 Lines 1047 1039 -8 ========================================== - Hits 959 952 -7 + Misses 88 87 -1 ``` | [Files Changed](https://app.codecov.io/gh/typst/ecow/pull/28?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=typst) | Coverage Δ | | |---|---|---| | [src/vec.rs](https://app.codecov.io/gh/typst/ecow/pull/28?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=typst#diff-c3JjL3ZlYy5ycw==) | `91.16% <100.00%> (+0.04%)` | :arrow_up: |

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

laurmaedje commented 1 year ago

Interesting observation with the header. It's only possible through an optimization that's more recent than the sentinel mechanic (the fact that an EcoVec's pointer points behind its header).

Technically, I don't think there is any guarantee that NonNull<u8>::dangling() is actually 1 though, is there?

I still think the approach has potential, maybe we'd have to drop lower and construct the dangling pointer ourselves to get the guarantees we need. Directly from the value mem::size_of::<Header>().

laurmaedje commented 1 year ago

I think if we use NonNull::new_unchecked(Self::offset() as *mut u8) as a dangling pointer, then we can make things const and eliminate the branch in data() for any type regardless of alignment. It can't ever be the ptr of a valid EcoVec because the pointer is always shifted by the offset, which means the original allocation would have been exactly a null pointer.

It's kind of funny, actually. Vec can't use the null pointer for initialization because of slice deref. We kind of can, except that our null pointer like all our pointers is shifted by the offset, making it non-null. Thanks for bringing this wonderful insight to my attention!

laurmaedje commented 1 year ago

The changes look great! Most of the explanation is already there in the doc comment, but it would be great if there was also an explicit Safety: block before the unsafe block in Self::dangling to explain why it is safe (i.e. why Self::offset() will never be zero). Other than that, it looks good to merge!

Edit: Could you also wrap the doc comment at 80 columns?

laurmaedje commented 1 year ago

Thanks for the idea and implementation!