Guarantee uniqueness in `RelationshipTarget`
- Dominant language
- Rust
- Stars
- 48.2k
- Forks
- 4.8k
- Avg merge
- 3d 16h
- Merged PRs (30d)
- 171
Description
## What problem does this solve or what need does it fill?
Certain algorithms require a guarantee that the entities in a `RelationshipTarget` are unique for performant and correct behavior. Specifically this is required for transform propagation, which I am looking to have support user-defined relationships in https://github.com/bevyengine/bevy/issues/25468.
## What solution would you like?
`RelationshipTarget::Collection::SourceIter` should be required to implement `EntitySetIterator`. With this change `Vec` could not be used as `RelationshipTarget::Collection` anymore as safe user code edit it to contain duplicates, causing undefined behavior. This is currently the case for `Children`, and is already causing undefined behavior as seen here https://github.com/bevyengine/bevy/issues/25349. We would need a Vec that prevents duplicates, or use other collections such as `EntityIndexSet`, see https://github.com/bevyengine/bevy/pull/23296.
## What alternative(s) have you considered?
We could add a `UniqueRelationshipTarget` supertrait that is implemented for every `RelationshipTarget` which fulfills the requirement above. This way non-unique relationships would still be possible, though I am not aware of a use case for those.
Contributor guide
Research direction
Start with RelationshipTarget::Collection::SourceIter and the EntitySetIterator requirement, then inspect Children and the referenced EntityIndexSet work. Compare the proposed required iterator with the UniqueRelationshipTarget alternative and trace the linked undefined-behavior issues. Done means relationship targets cannot be safely edited into duplicate-containing collections, while the intended transform-propagation use case remains supported.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- game-dev
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100