You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This commit was created on GitHub.com and signed with GitHub’s verified signature.
Tree initialization is revised to establish miri safety:
miri tests on the prior versions failed due to the uninitialized data in the first offset elements of the vector backing the tree. Note that the implementation guarantees that these elements are never accessed.
One potential solution to avoid uninitialized elements was to require Default or PseudoDefault for tree nodes. Most probably, this could have worked in most practical use cases. However, one exception is references. It might be considered a practical case where nodes are references, which would not implement neither Default or PseudoDefault.
Since we require Clone, another solution would be to fill the offset elements with the first ever pushed node to the queue. In other words, tree initialization is delayed until the first element is pushed. The concern on this was its potential impact of the additional "is backing vector empty" check on push methods. However, benchmarks show that this check does no measurable impact on the performance.
Since the latter solution does not add a trait requirement on keys or values, and since it does not degrade performance, it is implemented in this PR.
With the updated & delayed tree initialization without assume_init, all miri tests pass.