steel_core/world/tick_scheduler/
list.rs

1use super::{
2    BinaryHeap, BlockPos, FxHashSet, Ordering, SavedTick, ScheduledTick, ScheduledTickKey, TickKey,
3    TickPriority,
4};
5
6impl<T: TickKey> ScheduledTick<T> {
7    /// Returns the position/type identity used to deduplicate this tick.
8    #[must_use]
9    pub fn key(&self) -> ScheduledTickKey {
10        (self.pos, self.tick_type.key())
11    }
12
13    fn drain_order(&self, other: &Self) -> Ordering {
14        self.trigger_tick.cmp(&other.trigger_tick).then_with(|| {
15            intra_tick_drain_order(
16                self.priority,
17                self.sub_tick_order,
18                other.priority,
19                other.sub_tick_order,
20            )
21        })
22    }
23}
24
25pub(super) fn intra_tick_drain_order(
26    left_priority: TickPriority,
27    left_sub_tick_order: i64,
28    right_priority: TickPriority,
29    right_sub_tick_order: i64,
30) -> Ordering {
31    left_priority
32        .cmp(&right_priority)
33        .then_with(|| left_sub_tick_order.cmp(&right_sub_tick_order))
34}
35
36#[derive(Debug)]
37struct QueuedTick<T: TickKey> {
38    tick: ScheduledTick<T>,
39    insertion_order: u64,
40}
41
42impl<T: TickKey> PartialEq for QueuedTick<T> {
43    fn eq(&self, other: &Self) -> bool {
44        self.tick.drain_order(&other.tick) == Ordering::Equal
45            && self.insertion_order == other.insertion_order
46    }
47}
48
49impl<T: TickKey> Eq for QueuedTick<T> {}
50
51impl<T: TickKey> PartialOrd for QueuedTick<T> {
52    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
53        Some(self.cmp(other))
54    }
55}
56
57impl<T: TickKey> Ord for QueuedTick<T> {
58    fn cmp(&self, other: &Self) -> Ordering {
59        self.tick
60            .drain_order(&other.tick)
61            .reverse()
62            .then_with(|| other.insertion_order.cmp(&self.insertion_order))
63    }
64}
65
66/// Per-chunk storage for scheduled ticks of one type (block or fluid).
67///
68/// Saved and proto-chunk entries remain in `pending_ticks` until the chunk first
69/// reaches block-ticking readiness. Live entries use absolute game-time deadlines.
70/// A priority queue keeps live work ordered without scanning every tick.
71#[derive(Debug)]
72pub struct TickList<T: TickKey> {
73    pending_ticks: Option<Vec<SavedTick<T>>>,
74    ticks: BinaryHeap<QueuedTick<T>>,
75    scheduled: FxHashSet<ScheduledTickKey>,
76    next_insertion_order: u64,
77}
78
79pub(super) struct TickListPackingSnapshot<T: TickKey> {
80    pending_ticks: Vec<SavedTick<T>>,
81    live_ticks: Vec<(ScheduledTick<T>, u64)>,
82}
83
84impl<T: TickKey> TickListPackingSnapshot<T> {
85    pub(super) fn pack(mut self, current_tick: i64) -> Vec<SavedTick<T>> {
86        self.live_ticks.sort_by(|left, right| {
87            left.0
88                .sub_tick_order
89                .cmp(&right.0.sub_tick_order)
90                .then_with(|| left.1.cmp(&right.1))
91        });
92        self.pending_ticks
93            .extend(self.live_ticks.into_iter().map(|(tick, _)| SavedTick {
94                tick_type: tick.tick_type,
95                pos: tick.pos,
96                delay: tick.trigger_tick.wrapping_sub(current_tick) as i32,
97                priority: tick.priority,
98            }));
99        self.pending_ticks
100    }
101}
102
103impl<T: TickKey> TickList<T> {
104    /// Creates an empty tick list.
105    #[must_use]
106    pub fn new() -> Self {
107        Self {
108            pending_ticks: None,
109            ticks: BinaryHeap::new(),
110            scheduled: FxHashSet::default(),
111            next_insertion_order: 0,
112        }
113    }
114
115    /// Creates an empty proto-chunk list whose entries remain relative until
116    /// the promoted Full chunk first becomes block-ticking.
117    #[must_use]
118    pub(crate) fn new_pending() -> Self {
119        Self {
120            pending_ticks: Some(Vec::new()),
121            ticks: BinaryHeap::new(),
122            scheduled: FxHashSet::default(),
123            next_insertion_order: 0,
124        }
125    }
126
127    /// Creates a tick list from relative-delay ticks loaded from chunk storage.
128    ///
129    /// Vanilla assigns loaded entries the range `-len..-1` in saved list order,
130    /// ensuring they execute before newly scheduled entries with equal timing
131    /// once the list is unpacked.
132    #[must_use]
133    pub(crate) fn from_saved_ticks(saved_ticks: Vec<SavedTick<T>>) -> Self {
134        let mut result = Self::new_pending();
135        result.scheduled.reserve(saved_ticks.len());
136        for saved_tick in &saved_ticks {
137            result
138                .scheduled
139                .insert((saved_tick.pos, saved_tick.tick_type.key()));
140        }
141        result.pending_ticks = Some(saved_ticks);
142        result
143    }
144
145    /// Creates a proto-chunk tick list from relative-delay storage entries.
146    ///
147    /// `ProtoChunkTicks.load` schedules saved entries individually, so duplicate
148    /// `(pos, type)` keys are discarded while preserving the first entry. Full
149    /// chunk loading intentionally uses [`Self::from_saved_ticks`] instead because
150    /// `LevelChunkTicks` retains its saved list exactly as stored.
151    #[must_use]
152    pub(crate) fn from_proto_saved_ticks(saved_ticks: Vec<SavedTick<T>>) -> Self {
153        let mut result = Self::new_pending();
154        result.scheduled.reserve(saved_ticks.len());
155        for saved_tick in saved_ticks {
156            result.schedule_saved_pending(saved_tick);
157        }
158        result
159    }
160
161    /// Schedules a live tick with an absolute world game-time deadline.
162    ///
163    /// Returns `true` if the tick was added, or `false` when the same `(pos, type)`
164    /// is already scheduled.
165    pub(crate) fn schedule(
166        &mut self,
167        tick_type: T,
168        pos: BlockPos,
169        trigger_tick: i64,
170        priority: TickPriority,
171        sub_tick_order: i64,
172    ) -> bool {
173        let key = (pos, tick_type.key());
174        if !self.scheduled.insert(key) {
175            return false;
176        }
177
178        self.push_unchecked(ScheduledTick {
179            tick_type,
180            pos,
181            trigger_tick,
182            priority,
183            sub_tick_order,
184        });
185        true
186    }
187
188    /// Stores a proto-chunk tick with Vanilla's fixed zero delay.
189    pub(crate) fn schedule_pending(
190        &mut self,
191        tick_type: T,
192        pos: BlockPos,
193        priority: TickPriority,
194    ) -> bool {
195        self.schedule_saved_pending(SavedTick {
196            tick_type,
197            pos,
198            delay: 0,
199            priority,
200        })
201    }
202
203    fn schedule_saved_pending(&mut self, saved_tick: SavedTick<T>) -> bool {
204        let key = (saved_tick.pos, saved_tick.tick_type.key());
205        if !self.scheduled.insert(key) {
206            return false;
207        }
208        let pending_ticks = self.pending_ticks.get_or_insert_default();
209        pending_ticks.push(saved_tick);
210        true
211    }
212
213    /// Returns `true` if a tick is scheduled for the given `(pos, type)`.
214    #[must_use]
215    pub(crate) fn has_tick(&self, pos: BlockPos, tick_type: T) -> bool {
216        self.scheduled.contains(&(pos, tick_type.key()))
217    }
218
219    /// Returns the saved entries that have not yet been anchored to game time.
220    #[must_use]
221    pub(crate) fn pending_entries(&self) -> &[SavedTick<T>] {
222        self.pending_ticks.as_deref().unwrap_or_default()
223    }
224
225    /// Removes pending entries matching `predicate` while keeping deduplication in sync.
226    pub(crate) fn remove_pending_matching(
227        &mut self,
228        mut predicate: impl FnMut(&SavedTick<T>) -> bool,
229    ) -> usize {
230        let Self {
231            pending_ticks,
232            scheduled,
233            ..
234        } = self;
235        let Some(pending_ticks) = pending_ticks.as_mut() else {
236            return 0;
237        };
238
239        let old_len = pending_ticks.len();
240        pending_ticks.retain(|tick| {
241            if !predicate(tick) {
242                return true;
243            }
244
245            scheduled.remove(&(tick.pos, tick.tick_type.key()));
246            false
247        });
248        old_len - pending_ticks.len()
249    }
250
251    /// Packs pending entries followed by live entries in Vanilla saved-list order.
252    #[must_use]
253    #[cfg(test)]
254    pub(crate) fn pack(&self, current_tick: i64) -> Vec<SavedTick<T>> {
255        self.packing_snapshot().pack(current_tick)
256    }
257
258    pub(super) fn packing_snapshot(&self) -> TickListPackingSnapshot<T> {
259        let mut pending_ticks = Vec::with_capacity(self.len());
260        if let Some(pending) = &self.pending_ticks {
261            pending_ticks.extend_from_slice(pending);
262        }
263        let live_ticks = self
264            .ticks
265            .iter()
266            .map(|queued| (queued.tick, queued.insertion_order))
267            .collect();
268        TickListPackingSnapshot {
269            pending_ticks,
270            live_ticks,
271        }
272    }
273
274    /// Converts pending saved/proto ticks into live absolute-time ordering.
275    ///
276    /// This mirrors `LevelChunkTicks.unpack`: delays are anchored to `current_tick`
277    /// and entries receive negative sub-tick orders in saved-list order. Repeated
278    /// calls are no-ops, so later readiness changes cannot re-anchor deadlines.
279    pub(crate) fn unpack(&mut self, current_tick: i64) {
280        let Some(pending_ticks) = self.pending_ticks.take() else {
281            return;
282        };
283        let tick_count = pending_ticks.len() as i64;
284        self.ticks.reserve(pending_ticks.len());
285        for (index, saved_tick) in pending_ticks.into_iter().enumerate() {
286            self.push_unchecked(ScheduledTick {
287                tick_type: saved_tick.tick_type,
288                pos: saved_tick.pos,
289                trigger_tick: current_tick.wrapping_add(i64::from(saved_tick.delay)),
290                priority: saved_tick.priority,
291                sub_tick_order: -tick_count + index as i64,
292            });
293        }
294    }
295
296    /// Returns the number of scheduled ticks.
297    #[must_use]
298    pub(crate) fn len(&self) -> usize {
299        self.ticks.len() + self.pending_ticks.as_ref().map_or(0, Vec::len)
300    }
301
302    fn push_unchecked(&mut self, tick: ScheduledTick<T>) {
303        let insertion_order = self.next_insertion_order;
304        self.next_insertion_order = self.next_insertion_order.wrapping_add(1);
305        self.ticks.push(QueuedTick {
306            tick,
307            insertion_order,
308        });
309    }
310
311    pub(super) fn peek(&self) -> Option<ScheduledTick<T>> {
312        Some(self.ticks.peek()?.tick)
313    }
314
315    pub(super) fn peek_ready(&self, current_tick: i64) -> Option<ScheduledTick<T>> {
316        let tick = self.ticks.peek()?.tick;
317        (tick.trigger_tick <= current_tick).then_some(tick)
318    }
319
320    pub(super) fn pop_ready(&mut self, current_tick: i64) -> Option<ScheduledTick<T>> {
321        self.peek_ready(current_tick)?;
322        let tick = self.ticks.pop()?.tick;
323        self.scheduled.remove(&tick.key());
324        Some(tick)
325    }
326
327    #[cfg(test)]
328    pub(super) fn drain_ready(&mut self, current_tick: i64) -> Vec<ScheduledTick<T>> {
329        let mut ready = Vec::new();
330        while let Some(tick) = self.pop_ready(current_tick) {
331            ready.push(tick);
332        }
333        ready
334    }
335}
336
337impl<T: TickKey> Default for TickList<T> {
338    fn default() -> Self {
339        Self::new()
340    }
341}
steel_core/world/tick_scheduler/list.rs

steel_core/world/tick_scheduler/
list.rs
