unlit_ecs/query/iter.rs
1//! The iterator a query hands out.
2
3use crate::archetype::{Archetype, ScopeSummary};
4use crate::borrow::Claims;
5use crate::entity::Entity;
6use crate::query::{ArchetypeFilter, Ask, PlanBuilder, Query};
7use crate::world::World;
8
9/// Iterates the entities a [`Query`] matches.
10///
11/// The plan of the archetype being visited is resolved once, before its rows
12/// are read, so the components are looked up a handful of times per archetype
13/// rather than once per row. Each read then borrows the plan for one row, which
14/// is what keeps the exclusive references of one row from aliasing those of the
15/// next.
16///
17/// The iterator is lent by the query holder that owns the claims, so an item
18/// cannot outlive it: the items borrow from the holder as well, which is what
19/// lets a caller hold as many as the holder's claims allow and no more.
20pub struct QueryIter<'q, 'w, Q: Query> {
21 world: &'w World,
22 /// The scope the query looks through.
23 scope: Entity,
24 /// Narrows which of the archetypes the query matches are visited.
25 filter: &'q dyn ArchetypeFilter,
26 archetype: usize,
27 row: usize,
28 /// What the archetype being visited resolves its components to.
29 /// [`None`] until that archetype is accepted.
30 plan: Option<Q::Plan<'w>>,
31 /// Set once the archetype being visited has been accepted and its visibility
32 /// decided, so that the per-row loop repeats neither.
33 resolved: bool,
34 /// Set while the archetype being visited is uniform: whether the one scope
35 /// its rows live in is visible, which is the answer every row shares.
36 /// [`None`] for a mixed archetype, and until the archetype is resolved.
37 ///
38 /// Resolved here rather than per row because deciding it walks the scope
39 /// tree, and a uniform archetype answers the same thing for every row.
40 uniform_visible: Option<bool>,
41 /// The holder's claims, which the archetypes accepted here are added to.
42 claims: &'q mut Claims<'w>,
43 /// Where a pass records the components it asks an archetype for. Owned by
44 /// the holder, so a second pass over the same world reuses it.
45 asks: &'q mut Vec<Ask>,
46 /// Where the query was asked for, reported when a claim conflicts with one
47 /// already held.
48 origin: &'static core::panic::Location<'static>,
49}
50
51impl<'q, 'w, Q: Query> QueryIter<'q, 'w, Q> {
52 pub(crate) fn new(
53 world: &'w World,
54 scope: Entity,
55 filter: &'q dyn ArchetypeFilter,
56 claims: &'q mut Claims<'w>,
57 asks: &'q mut Vec<Ask>,
58 origin: &'static core::panic::Location<'static>,
59 ) -> Self {
60 Self {
61 world,
62 scope,
63 filter,
64 archetype: 0,
65 row: world.content_start(0),
66 plan: None,
67 resolved: false,
68 uniform_visible: None,
69 claims,
70 asks,
71 origin,
72 }
73 }
74
75 /// Whether `archetype` is one this query may visit.
76 ///
77 /// This is only the cheap half: whether the query can resolve its plan on
78 /// the archetype is decided by `Q::prepare` itself, once, when that
79 /// archetype is resolved. Resolving here as well would reach the columns
80 /// twice per archetype.
81 fn archetype_matches(&self, archetype: &Archetype) -> bool {
82 self.filter.accept(archetype)
83 && archetype
84 .scope_summary()
85 .any_visible(self.world, self.scope)
86 }
87
88 /// Whether `row` of `archetype` is visible from this query's scope.
89 fn row_matches(&self, archetype: &Archetype, row: usize) -> bool {
90 match self.uniform_visible {
91 // The whole archetype lives in one scope, so the tree walk is done
92 // once for it. The one row that can still be visible without it is
93 // the caller's own: a scope lives in its parent, and that row sits
94 // in the parent's archetype, not in the caller's.
95 Some(visible) => visible || archetype.entities()[row] == self.scope,
96 None => archetype
97 .scope_summary()
98 .row_visible(archetype, self.world, self.scope, row),
99 }
100 }
101}
102
103impl<'q, 'w: 'q, Q: Query + 'q> Iterator for QueryIter<'q, 'w, Q> {
104 type Item = Q::Item<'q>;
105
106 fn next(&mut self) -> Option<Self::Item> {
107 let archetypes = self.world.archetypes().as_slice();
108 loop {
109 let archetype = archetypes.get(self.archetype)?;
110 if self.row >= archetype.len() {
111 // Done with this archetype; move to the next and decide it
112 // lazily. Its scaffolding, if any, is skipped the same way: by
113 // starting the scan past it rather than testing every row.
114 self.archetype += 1;
115 self.row = self.world.content_start(self.archetype as u32);
116 self.plan = None;
117 self.resolved = false;
118 self.uniform_visible = None;
119 continue;
120 }
121 if !self.resolved {
122 if !self.archetype_matches(archetype) {
123 self.archetype += 1;
124 self.row = self.world.content_start(self.archetype as u32);
125 continue;
126 }
127 // The buffer is the holder's, so every archetype visited after
128 // the first reuses its capacity instead of allocating. It is
129 // cleared first: the asks of the archetype before this one are
130 // not asks on this one.
131 let mut asks = core::mem::take(&mut *self.asks);
132 asks.clear();
133 let mut builder = PlanBuilder::new(archetype, asks);
134 let plan = Q::prepare(&mut builder);
135 *self.asks = builder.into_asks();
136 let Some(plan) = plan else {
137 self.archetype += 1;
138 self.row = self.world.content_start(self.archetype as u32);
139 continue;
140 };
141 self.claims.claim_archetype(
142 self.archetype as u32,
143 archetype,
144 self.asks,
145 self.origin,
146 );
147 self.plan = Some(plan);
148 let summary = archetype.scope_summary();
149 self.uniform_visible = match summary {
150 // [`all_visible`] on a uniform archetype is exactly "the
151 // scope its rows live in is visible", the row-invariant
152 // half of [`row_visible`].
153 ScopeSummary::Uniform(_) => Some(summary.all_visible(self.world, self.scope)),
154 _ => None,
155 };
156 self.resolved = true;
157 }
158 let row = self.row;
159 self.row += 1;
160 if !self.row_matches(archetype, row) {
161 continue;
162 }
163 let plan = self.plan.as_mut()?;
164 // SAFETY: the plan lives in this holder and [`next`] hands out one
165 // row at a time, so no two items of this iterator name the same cell.
166 // [`read`] takes the plan exclusively, so one call yields at most
167 // one exclusive reference per column. 'q comes from the holder's own
168 // [`&mut self`], so every item dies before the holder does.
169 let plan: &'q mut Q::Plan<'w> = unsafe { &mut *(plan as *mut Q::Plan<'w>) };
170 return Some(Q::read(plan, row));
171 }
172 }
173}