steel_core/chunk/light/
queue.rs

1use std::cell::RefCell;
2use std::iter::FusedIterator;
3use std::mem;
4use std::ops::{Deref, DerefMut};
5
6use steel_utils::{BlockPos, Direction};
7
8use super::{MAX_LIGHT_LEVEL, PackedLightBlockPos};
9
10const QUEUE_ENTRY_LEVEL_MASK: u64 = 0b1111;
11const QUEUE_ENTRY_DIRECTIONS_MASK: u64 = 0b11_1111_0000;
12const QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE: u64 = 1 << 10;
13const QUEUE_ENTRY_FLAG_INCREASE_FROM_EMISSION: u64 = 1 << 11;
14const LIGHT_QUEUE_MIN_CAPACITY: usize = 512;
15const PACKED_LIGHT_QUEUE_MIN_CAPACITY: usize = 16 * 16 * 16;
16const PACKED_LIGHT_QUEUE_POSITION_BITS: u64 = 28;
17const PACKED_LIGHT_QUEUE_LEVEL_BITS: u64 = 4;
18const PACKED_LIGHT_QUEUE_DIRECTION_BITS: u64 = 6;
19const PACKED_LIGHT_QUEUE_LEVEL_MASK: u64 = (1 << PACKED_LIGHT_QUEUE_LEVEL_BITS) - 1;
20const PACKED_LIGHT_QUEUE_DIRECTION_MASK: u8 = (1 << PACKED_LIGHT_QUEUE_DIRECTION_BITS) - 1;
21const PACKED_LIGHT_QUEUE_LEVEL_SHIFT: u64 = PACKED_LIGHT_QUEUE_POSITION_BITS;
22const PACKED_LIGHT_QUEUE_DIRECTIONS_SHIFT: u64 =
23    PACKED_LIGHT_QUEUE_LEVEL_SHIFT + PACKED_LIGHT_QUEUE_LEVEL_BITS;
24const PACKED_LIGHT_QUEUE_POSITION_MASK: u64 = (1_u64 << PACKED_LIGHT_QUEUE_POSITION_BITS) - 1;
25const PACKED_LIGHT_QUEUE_FLAGS_MASK: u64 = (1_u64 << 61) | (1_u64 << 62) | (1_u64 << 63);
26
27/// `ScalableLux` axis direction order used by packed light propagation queues.
28///
29/// This intentionally differs from vanilla's `Direction.ordinal()` order.
30/// `ScalableLux` stores direction bitsets as +X, -X, +Z, -Z, +Y, -Y and relies on
31/// positive directions being even so `index ^ 1` gives the opposite direction.
32#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
33pub enum LightAxisDirection {
34    /// Positive X / east.
35    PositiveX,
36    /// Negative X / west.
37    NegativeX,
38    /// Positive Z / south.
39    PositiveZ,
40    /// Negative Z / north.
41    NegativeZ,
42    /// Positive Y / up.
43    PositiveY,
44    /// Negative Y / down.
45    NegativeY,
46}
47
48impl LightAxisDirection {
49    /// All directions in `ScalableLux` propagation order.
50    pub const ALL: [Self; 6] = [
51        Self::PositiveX,
52        Self::NegativeX,
53        Self::PositiveZ,
54        Self::NegativeZ,
55        Self::PositiveY,
56        Self::NegativeY,
57    ];
58
59    /// Horizontal directions in `ScalableLux` propagation order.
60    pub const HORIZONTAL: [Self; 4] = [
61        Self::PositiveX,
62        Self::NegativeX,
63        Self::PositiveZ,
64        Self::NegativeZ,
65    ];
66
67    /// Converts a vanilla direction into `ScalableLux`'s axis-direction order.
68    #[must_use]
69    pub const fn from_direction(direction: Direction) -> Self {
70        match direction {
71            Direction::East => Self::PositiveX,
72            Direction::West => Self::NegativeX,
73            Direction::South => Self::PositiveZ,
74            Direction::North => Self::NegativeZ,
75            Direction::Up => Self::PositiveY,
76            Direction::Down => Self::NegativeY,
77        }
78    }
79
80    /// Returns the `ScalableLux` axis direction for a direction-bit index.
81    #[must_use]
82    pub const fn from_bit_index(bit_index: u8) -> Option<Self> {
83        match bit_index {
84            0 => Some(Self::PositiveX),
85            1 => Some(Self::NegativeX),
86            2 => Some(Self::PositiveZ),
87            3 => Some(Self::NegativeZ),
88            4 => Some(Self::PositiveY),
89            5 => Some(Self::NegativeY),
90            _ => None,
91        }
92    }
93
94    /// Returns the vanilla direction represented by this axis direction.
95    #[must_use]
96    pub const fn direction(self) -> Direction {
97        match self {
98            Self::PositiveX => Direction::East,
99            Self::NegativeX => Direction::West,
100            Self::PositiveZ => Direction::South,
101            Self::NegativeZ => Direction::North,
102            Self::PositiveY => Direction::Up,
103            Self::NegativeY => Direction::Down,
104        }
105    }
106
107    /// Returns the block-coordinate offset for this axis direction.
108    #[must_use]
109    pub const fn offset(self) -> (i32, i32, i32) {
110        match self {
111            Self::PositiveX => (1, 0, 0),
112            Self::NegativeX => (-1, 0, 0),
113            Self::PositiveZ => (0, 0, 1),
114            Self::NegativeZ => (0, 0, -1),
115            Self::PositiveY => (0, 1, 0),
116            Self::NegativeY => (0, -1, 0),
117        }
118    }
119
120    /// Returns the opposite `ScalableLux` axis direction.
121    #[must_use]
122    pub const fn opposite(self) -> Self {
123        match self {
124            Self::PositiveX => Self::NegativeX,
125            Self::NegativeX => Self::PositiveX,
126            Self::PositiveZ => Self::NegativeZ,
127            Self::NegativeZ => Self::PositiveZ,
128            Self::PositiveY => Self::NegativeY,
129            Self::NegativeY => Self::PositiveY,
130        }
131    }
132
133    /// Returns this direction's `ScalableLux` bit index.
134    #[must_use]
135    pub const fn bit_index(self) -> u8 {
136        match self {
137            Self::PositiveX => 0,
138            Self::NegativeX => 1,
139            Self::PositiveZ => 2,
140            Self::NegativeZ => 3,
141            Self::PositiveY => 4,
142            Self::NegativeY => 5,
143        }
144    }
145
146    const fn bit(self) -> u8 {
147        1 << self.bit_index()
148    }
149}
150
151/// `ScalableLux` propagation direction bitset.
152#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
153pub struct LightDirectionSet(u8);
154
155impl LightDirectionSet {
156    /// Creates an empty direction set.
157    #[must_use]
158    pub const fn empty() -> Self {
159        Self(0)
160    }
161
162    /// Creates a direction set containing all six axis directions.
163    #[must_use]
164    pub const fn all() -> Self {
165        Self(PACKED_LIGHT_QUEUE_DIRECTION_MASK)
166    }
167
168    /// Creates a direction set from raw `ScalableLux` direction bits.
169    #[must_use]
170    pub const fn from_raw(raw: u8) -> Self {
171        Self(raw & PACKED_LIGHT_QUEUE_DIRECTION_MASK)
172    }
173
174    /// Creates a direction set containing exactly one axis direction.
175    #[must_use]
176    pub const fn only(direction: LightAxisDirection) -> Self {
177        Self(direction.bit())
178    }
179
180    /// Returns this set with one additional direction.
181    #[must_use]
182    pub const fn with(self, direction: LightAxisDirection) -> Self {
183        Self(self.0 | direction.bit())
184    }
185
186    /// Creates a direction set containing all directions except one.
187    #[must_use]
188    pub const fn all_except(direction: LightAxisDirection) -> Self {
189        Self(PACKED_LIGHT_QUEUE_DIRECTION_MASK & !direction.bit())
190    }
191
192    /// Creates a direction set containing all directions except the opposite of one direction.
193    #[must_use]
194    pub const fn all_except_opposite(direction: LightAxisDirection) -> Self {
195        Self::all_except(direction.opposite())
196    }
197
198    /// Returns the raw `ScalableLux` direction bits.
199    #[must_use]
200    pub const fn raw(self) -> u8 {
201        self.0
202    }
203
204    /// Returns true when this set contains the selected axis direction.
205    #[must_use]
206    pub const fn contains(self, direction: LightAxisDirection) -> bool {
207        self.0 & direction.bit() != 0
208    }
209
210    /// Iterates selected directions in `ScalableLux`'s propagation order.
211    #[must_use]
212    pub const fn directions(self) -> LightDirectionSetIter {
213        LightDirectionSetIter { remaining: self.0 }
214    }
215}
216
217/// Iterator over a `LightDirectionSet` in `ScalableLux` propagation order.
218#[derive(Debug, Clone)]
219pub struct LightDirectionSetIter {
220    remaining: u8,
221}
222
223impl Iterator for LightDirectionSetIter {
224    type Item = LightAxisDirection;
225
226    fn next(&mut self) -> Option<Self::Item> {
227        if self.remaining == 0 {
228            return None;
229        }
230
231        let bit_index = self.remaining.trailing_zeros() as u8;
232        self.remaining &= self.remaining - 1;
233        LightAxisDirection::from_bit_index(bit_index)
234    }
235
236    fn size_hint(&self) -> (usize, Option<usize>) {
237        let len = self.remaining.count_ones() as usize;
238        (len, Some(len))
239    }
240}
241
242impl ExactSizeIterator for LightDirectionSetIter {}
243
244impl FusedIterator for LightDirectionSetIter {}
245
246/// `ScalableLux` state flags stored in the top three queue-entry bits.
247#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
248pub struct LightQueueFlags(u64);
249
250impl LightQueueFlags {
251    /// No queue state flags.
252    pub const EMPTY: Self = Self(0);
253    /// The increase pass should write the entry's level before propagating.
254    pub const WRITE_LEVEL: Self = Self(1_u64 << 61);
255    /// The increase pass should confirm the current level still matches.
256    pub const RECHECK_LEVEL: Self = Self(1_u64 << 62);
257    /// Propagation must account for sided transparent block shapes.
258    pub const HAS_SIDED_TRANSPARENT_BLOCKS: Self = Self(1_u64 << 63);
259
260    /// Creates flags from raw queue bits.
261    #[must_use]
262    pub const fn from_raw(raw: u64) -> Self {
263        Self(raw & PACKED_LIGHT_QUEUE_FLAGS_MASK)
264    }
265
266    /// Returns the raw queue flag bits.
267    #[must_use]
268    pub const fn raw(self) -> u64 {
269        self.0
270    }
271
272    /// Returns a set with `flag` included.
273    #[must_use]
274    pub const fn with(self, flag: Self) -> Self {
275        Self(self.0 | flag.0)
276    }
277
278    /// Returns true when all bits in `flag` are present.
279    #[must_use]
280    pub const fn contains(self, flag: Self) -> bool {
281        self.0 & flag.0 == flag.0
282    }
283}
284
285/// `ScalableLux` packed light-propagation queue entry.
286///
287/// The lower 28 bits store `PackedLightBlockPos`, followed by a 4-bit light
288/// level and a 6-bit `LightDirectionSet`. Bits 61, 62, and 63 carry
289/// `LightQueueFlags`; the middle 23 bits are intentionally unused to preserve
290/// `ScalableLux`'s layout.
291#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
292pub struct PackedLightQueueEntry(u64);
293
294impl PackedLightQueueEntry {
295    /// Creates a packed queue entry from typed `ScalableLux` parts.
296    #[must_use]
297    pub const fn from_parts(
298        block_pos: PackedLightBlockPos,
299        level: u8,
300        directions: LightDirectionSet,
301        flags: LightQueueFlags,
302    ) -> Self {
303        Self(
304            block_pos.raw() as u64
305                | ((level as u64 & PACKED_LIGHT_QUEUE_LEVEL_MASK)
306                    << PACKED_LIGHT_QUEUE_LEVEL_SHIFT)
307                | ((directions.raw() as u64) << PACKED_LIGHT_QUEUE_DIRECTIONS_SHIFT)
308                | flags.raw(),
309        )
310    }
311
312    /// Creates a packed queue entry from raw `ScalableLux` queue bits.
313    #[must_use]
314    pub const fn from_raw(raw: u64) -> Self {
315        Self(raw)
316    }
317
318    /// Returns the raw `ScalableLux` queue entry.
319    #[must_use]
320    pub const fn raw(self) -> u64 {
321        self.0
322    }
323
324    /// Returns the packed block position stored in this queue entry.
325    #[must_use]
326    pub const fn block_pos(self) -> PackedLightBlockPos {
327        PackedLightBlockPos::from_raw((self.0 & PACKED_LIGHT_QUEUE_POSITION_MASK) as u32)
328    }
329
330    /// Returns the propagated light level.
331    #[must_use]
332    pub const fn level(self) -> u8 {
333        ((self.0 >> PACKED_LIGHT_QUEUE_LEVEL_SHIFT) & PACKED_LIGHT_QUEUE_LEVEL_MASK) as u8
334    }
335
336    /// Returns the propagation direction set.
337    #[must_use]
338    pub const fn directions(self) -> LightDirectionSet {
339        LightDirectionSet::from_raw(
340            ((self.0 >> PACKED_LIGHT_QUEUE_DIRECTIONS_SHIFT)
341                & PACKED_LIGHT_QUEUE_DIRECTION_MASK as u64) as u8,
342        )
343    }
344
345    /// Returns the top-bit state flags.
346    #[must_use]
347    pub const fn flags(self) -> LightQueueFlags {
348        LightQueueFlags::from_raw(self.0)
349    }
350
351    /// Returns true when the increase pass should write this entry's level.
352    #[must_use]
353    pub const fn should_write_level(self) -> bool {
354        self.flags().contains(LightQueueFlags::WRITE_LEVEL)
355    }
356
357    /// Returns true when the increase pass should confirm the current level.
358    #[must_use]
359    pub const fn should_recheck_level(self) -> bool {
360        self.flags().contains(LightQueueFlags::RECHECK_LEVEL)
361    }
362
363    /// Returns true when propagation must account for sided transparent shapes.
364    #[must_use]
365    pub const fn has_sided_transparent_blocks(self) -> bool {
366        self.flags()
367            .contains(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS)
368    }
369}
370
371/// Array-backed FIFO used for `ScalableLux` packed light propagation entries.
372#[derive(Debug)]
373pub struct PackedLightPropagationQueue {
374    entries: Vec<PackedLightQueueEntry>,
375    read_index: usize,
376}
377
378impl PackedLightPropagationQueue {
379    /// Creates an empty `ScalableLux` packed propagation queue.
380    #[must_use]
381    pub fn new() -> Self {
382        Self {
383            entries: Vec::with_capacity(PACKED_LIGHT_QUEUE_MIN_CAPACITY),
384            read_index: 0,
385        }
386    }
387
388    /// Returns true when no packed queued work remains.
389    #[must_use]
390    pub const fn is_empty(&self) -> bool {
391        self.read_index >= self.entries.len()
392    }
393
394    /// Returns the number of packed entries that have not been dequeued yet.
395    #[must_use]
396    pub const fn len(&self) -> usize {
397        self.entries.len() - self.read_index
398    }
399
400    /// Adds packed propagation work to the back of the queue.
401    pub fn enqueue(&mut self, entry: PackedLightQueueEntry) {
402        self.entries.push(entry);
403    }
404
405    /// Removes packed propagation work from the front of the queue.
406    pub fn dequeue(&mut self) -> Option<PackedLightQueueEntry> {
407        if self.is_empty() {
408            self.clear();
409            return None;
410        }
411
412        let entry = self.entries[self.read_index];
413        self.read_index += 1;
414        if self.is_empty() {
415            self.clear();
416        }
417
418        Some(entry)
419    }
420
421    /// Removes all queued packed work while keeping allocated storage for reuse.
422    pub fn clear(&mut self) {
423        self.entries.clear();
424        self.read_index = 0;
425    }
426}
427
428impl Default for PackedLightPropagationQueue {
429    fn default() -> Self {
430        Self::new()
431    }
432}
433
434/// `ScalableLux`'s separate packed increase and decrease propagation queues.
435#[derive(Debug, Default)]
436pub struct PackedLightPropagationQueues {
437    increase: PackedLightPropagationQueue,
438    decrease: PackedLightPropagationQueue,
439}
440
441impl PackedLightPropagationQueues {
442    /// Creates empty packed increase and decrease queues.
443    #[must_use]
444    pub fn new() -> Self {
445        Self::default()
446    }
447
448    /// Returns true when either packed propagation queue contains work.
449    #[must_use]
450    pub const fn has_work(&self) -> bool {
451        !self.increase.is_empty() || !self.decrease.is_empty()
452    }
453
454    /// Enqueues packed decrease propagation work.
455    pub fn enqueue_decrease(&mut self, entry: PackedLightQueueEntry) {
456        self.decrease.enqueue(entry);
457    }
458
459    /// Enqueues packed increase propagation work.
460    pub fn enqueue_increase(&mut self, entry: PackedLightQueueEntry) {
461        self.increase.enqueue(entry);
462    }
463
464    /// Dequeues packed decrease propagation work.
465    pub fn dequeue_decrease(&mut self) -> Option<PackedLightQueueEntry> {
466        self.decrease.dequeue()
467    }
468
469    /// Dequeues packed increase propagation work.
470    pub fn dequeue_increase(&mut self) -> Option<PackedLightQueueEntry> {
471        self.increase.dequeue()
472    }
473
474    /// Removes all packed increase and decrease work.
475    pub fn clear(&mut self) {
476        self.increase.clear();
477        self.decrease.clear();
478    }
479
480    /// Creates an empty queue pair without reserving propagation scratch capacity.
481    const fn empty_without_capacity() -> Self {
482        Self {
483            increase: PackedLightPropagationQueue {
484                entries: Vec::new(),
485                read_index: 0,
486            },
487            decrease: PackedLightPropagationQueue {
488                entries: Vec::new(),
489                read_index: 0,
490            },
491        }
492    }
493
494    const fn total_capacity(&self) -> usize {
495        self.increase.entries.capacity() + self.decrease.entries.capacity()
496    }
497}
498
499/// Retained-capacity ceiling for the recycled queue pair, summed over both
500/// queues (~2 MiB of packed 8-byte entries). Larger buffers are dropped
501/// instead of pinned to a worker thread.
502const POOLED_PACKED_QUEUES_MAX_ENTRIES: usize = 256 * 1024;
503
504thread_local! {
505    static POOLED_PACKED_QUEUES: RefCell<Option<PackedLightPropagationQueues>> =
506        const { RefCell::new(None) };
507}
508
509/// A packed propagation queue pair leased from a thread-local pool.
510///
511/// Light chunk work constructs fresh queues per chunk; leasing recycles the
512/// worker's previous buffers instead of reallocating ~64 KiB each time. The
513/// guard returns its buffers to the pool on drop, so early returns and panics
514/// stay safe.
515///
516/// Dropping an oversized lease discards its buffers without evicting a pair
517/// that an overlapping lease has already parked.
518#[must_use]
519pub struct PooledPackedLightQueues {
520    inner: PackedLightPropagationQueues,
521}
522
523impl PooledPackedLightQueues {
524    /// Leases empty queues from the worker's pool, allocating on first use.
525    pub fn take() -> Self {
526        let inner = POOLED_PACKED_QUEUES.with(|pool| match pool.borrow_mut().take() {
527            Some(queues) => queues,
528            None => PackedLightPropagationQueues::new(),
529        });
530
531        Self { inner }
532    }
533}
534
535impl Default for PooledPackedLightQueues {
536    fn default() -> Self {
537        Self::take()
538    }
539}
540
541impl Deref for PooledPackedLightQueues {
542    type Target = PackedLightPropagationQueues;
543
544    #[inline]
545    fn deref(&self) -> &Self::Target {
546        &self.inner
547    }
548}
549
550impl DerefMut for PooledPackedLightQueues {
551    #[inline]
552    fn deref_mut(&mut self) -> &mut Self::Target {
553        &mut self.inner
554    }
555}
556
557impl Drop for PooledPackedLightQueues {
558    fn drop(&mut self) {
559        let mut queues = mem::replace(
560            &mut self.inner,
561            PackedLightPropagationQueues::empty_without_capacity(),
562        );
563
564        queues.clear();
565
566        let recycled =
567            (queues.total_capacity() <= POOLED_PACKED_QUEUES_MAX_ENTRIES).then_some(queues);
568
569        POOLED_PACKED_QUEUES.with(|pool| {
570            if let Some(queues) = recycled {
571                *pool.borrow_mut() = Some(queues);
572            }
573        });
574    }
575}
576
577/// Vanilla's packed light-propagation queue entry.
578///
579/// `LightEngine.QueueEntry` stores the source level in bits 0..3, one
580/// propagation bit per vanilla `Direction.ordinal()` in bits 4..9, and two
581/// increase flags in bits 10 and 11.
582#[derive(Debug, Clone, Copy, PartialEq, Eq)]
583pub struct LightQueueEntry(u64);
584
585impl LightQueueEntry {
586    /// Creates a decrease entry that propagates to all directions except one.
587    #[must_use]
588    pub const fn decrease_skip_one_direction(
589        old_from_level: u8,
590        skip_direction: Direction,
591    ) -> Self {
592        Self::with_level(
593            Self::without_direction(QUEUE_ENTRY_DIRECTIONS_MASK, skip_direction),
594            old_from_level,
595        )
596    }
597
598    /// Creates a decrease entry that propagates to all directions.
599    #[must_use]
600    pub const fn decrease_all_directions(old_from_level: u8) -> Self {
601        Self::with_level(QUEUE_ENTRY_DIRECTIONS_MASK, old_from_level)
602    }
603
604    /// Creates an increase entry sourced from a block's light emission.
605    #[must_use]
606    pub const fn increase_light_from_emission(new_from_level: u8, from_empty_shape: bool) -> Self {
607        let mut entry = QUEUE_ENTRY_DIRECTIONS_MASK | QUEUE_ENTRY_FLAG_INCREASE_FROM_EMISSION;
608        if from_empty_shape {
609            entry |= QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE;
610        }
611
612        Self::with_level(entry, new_from_level)
613    }
614
615    /// Creates an increase entry that propagates to all directions except one.
616    #[must_use]
617    pub const fn increase_skip_one_direction(
618        new_from_level: u8,
619        from_empty_shape: bool,
620        skip_direction: Direction,
621    ) -> Self {
622        let mut entry = Self::without_direction(QUEUE_ENTRY_DIRECTIONS_MASK, skip_direction);
623        if from_empty_shape {
624            entry |= QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE;
625        }
626
627        Self::with_level(entry, new_from_level)
628    }
629
630    /// Creates an increase entry that propagates to exactly one direction.
631    #[must_use]
632    pub const fn increase_only_one_direction(
633        new_from_level: u8,
634        from_empty_shape: bool,
635        direction: Direction,
636    ) -> Self {
637        let mut entry = 0;
638        if from_empty_shape {
639            entry |= QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE;
640        }
641
642        Self::with_level(Self::with_direction(entry, direction), new_from_level)
643    }
644
645    /// Creates a sky-source increase entry for selected directions.
646    #[must_use]
647    pub fn increase_sky_source_in_directions(directions: &[Direction]) -> Self {
648        let mut entry = u64::from(MAX_LIGHT_LEVEL);
649        for &direction in directions {
650            entry = Self::with_direction(entry, direction);
651        }
652
653        Self(entry)
654    }
655
656    /// Creates a queue entry from vanilla's packed representation.
657    #[must_use]
658    pub const fn from_raw(raw: u64) -> Self {
659        Self(raw)
660    }
661
662    /// Returns vanilla's packed representation.
663    #[must_use]
664    pub const fn raw(self) -> u64 {
665        self.0
666    }
667
668    /// Returns the source light level stored in this entry.
669    #[must_use]
670    pub const fn level(self) -> u8 {
671        (self.0 & QUEUE_ENTRY_LEVEL_MASK) as u8
672    }
673
674    /// Returns true if propagation starts from an empty occlusion shape.
675    #[must_use]
676    pub const fn is_from_empty_shape(self) -> bool {
677        self.0 & QUEUE_ENTRY_FLAG_FROM_EMPTY_SHAPE != 0
678    }
679
680    /// Returns true if this increase came from block light emission.
681    #[must_use]
682    pub const fn is_increase_from_emission(self) -> bool {
683        self.0 & QUEUE_ENTRY_FLAG_INCREASE_FROM_EMISSION != 0
684    }
685
686    /// Returns true if this entry propagates in `direction`.
687    #[must_use]
688    pub const fn should_propagate_in_direction(self, direction: Direction) -> bool {
689        self.0 & Self::direction_bit(direction) != 0
690    }
691
692    const fn with_level(entry: u64, level: u8) -> Self {
693        Self(entry & !QUEUE_ENTRY_LEVEL_MASK | (level as u64 & QUEUE_ENTRY_LEVEL_MASK))
694    }
695
696    const fn with_direction(entry: u64, direction: Direction) -> u64 {
697        entry | Self::direction_bit(direction)
698    }
699
700    const fn without_direction(entry: u64, direction: Direction) -> u64 {
701        entry & !Self::direction_bit(direction)
702    }
703
704    const fn direction_bit(direction: Direction) -> u64 {
705        1 << (Self::vanilla_direction_index(direction) + 4)
706    }
707
708    const fn vanilla_direction_index(direction: Direction) -> u64 {
709        match direction {
710            Direction::Down => 0,
711            Direction::Up => 1,
712            Direction::North => 2,
713            Direction::South => 3,
714            Direction::West => 4,
715            Direction::East => 5,
716        }
717    }
718}
719
720/// One typed light propagation queue item.
721#[derive(Debug, Clone, Copy, PartialEq, Eq)]
722pub struct QueuedLightUpdate {
723    /// Block position whose light should propagate.
724    pub block_pos: BlockPos,
725    /// Packed vanilla propagation metadata.
726    pub entry: LightQueueEntry,
727}
728
729/// Array-backed FIFO used for vanilla light propagation work.
730///
731/// Vanilla stores alternating packed block positions and `QueueEntry` longs in
732/// `LongArrayFIFOQueue`. Steel keeps typed records instead, while preserving
733/// the FIFO ordering and packed queue-entry semantics that propagation depends
734/// on.
735#[derive(Debug)]
736pub struct LightPropagationQueue {
737    entries: Vec<QueuedLightUpdate>,
738    read_index: usize,
739}
740
741impl LightPropagationQueue {
742    /// Creates an empty propagation queue.
743    #[must_use]
744    pub fn new() -> Self {
745        Self {
746            entries: Vec::with_capacity(LIGHT_QUEUE_MIN_CAPACITY),
747            read_index: 0,
748        }
749    }
750
751    /// Returns true when no queued work remains.
752    #[must_use]
753    pub const fn is_empty(&self) -> bool {
754        self.read_index >= self.entries.len()
755    }
756
757    /// Returns the number of queued items that have not been dequeued yet.
758    #[must_use]
759    pub const fn len(&self) -> usize {
760        self.entries.len() - self.read_index
761    }
762
763    /// Adds propagation work to the back of the queue.
764    pub fn enqueue(&mut self, block_pos: BlockPos, entry: LightQueueEntry) {
765        self.entries.push(QueuedLightUpdate { block_pos, entry });
766    }
767
768    /// Removes propagation work from the front of the queue.
769    pub fn dequeue(&mut self) -> Option<QueuedLightUpdate> {
770        if self.is_empty() {
771            self.clear();
772            return None;
773        }
774
775        let update = self.entries[self.read_index];
776        self.read_index += 1;
777        if self.is_empty() {
778            self.clear();
779        }
780
781        Some(update)
782    }
783
784    /// Removes all queued work while keeping allocated storage for reuse.
785    pub fn clear(&mut self) {
786        self.entries.clear();
787        self.read_index = 0;
788    }
789}
790
791impl Default for LightPropagationQueue {
792    fn default() -> Self {
793        Self::new()
794    }
795}
796
797/// Vanilla's separate increase and decrease propagation queues.
798#[derive(Debug, Default)]
799pub struct LightPropagationQueues {
800    increase: LightPropagationQueue,
801    decrease: LightPropagationQueue,
802}
803
804impl LightPropagationQueues {
805    /// Creates empty increase and decrease queues.
806    #[must_use]
807    pub fn new() -> Self {
808        Self::default()
809    }
810
811    /// Returns true when either propagation queue contains work.
812    #[must_use]
813    pub const fn has_work(&self) -> bool {
814        !self.increase.is_empty() || !self.decrease.is_empty()
815    }
816
817    /// Enqueues decrease propagation work.
818    pub fn enqueue_decrease(&mut self, block_pos: BlockPos, entry: LightQueueEntry) {
819        self.decrease.enqueue(block_pos, entry);
820    }
821
822    /// Enqueues increase propagation work.
823    pub fn enqueue_increase(&mut self, block_pos: BlockPos, entry: LightQueueEntry) {
824        self.increase.enqueue(block_pos, entry);
825    }
826
827    /// Dequeues decrease propagation work.
828    pub fn dequeue_decrease(&mut self) -> Option<QueuedLightUpdate> {
829        self.decrease.dequeue()
830    }
831
832    /// Dequeues increase propagation work.
833    pub fn dequeue_increase(&mut self) -> Option<QueuedLightUpdate> {
834        self.increase.dequeue()
835    }
836
837    /// Removes all increase and decrease work.
838    pub fn clear(&mut self) {
839        self.increase.clear();
840        self.decrease.clear();
841    }
842}
843
844#[cfg(test)]
845mod tests {
846    use super::*;
847
848    fn packed_entry(level: u8) -> PackedLightQueueEntry {
849        PackedLightQueueEntry::from_parts(
850            PackedLightBlockPos::from_raw(u32::from(level)),
851            level,
852            LightDirectionSet::all(),
853            LightQueueFlags::EMPTY,
854        )
855    }
856
857    #[test]
858    fn light_axis_direction_matches_scalable_lux_order() {
859        assert_eq!(
860            LightAxisDirection::ALL,
861            [
862                LightAxisDirection::PositiveX,
863                LightAxisDirection::NegativeX,
864                LightAxisDirection::PositiveZ,
865                LightAxisDirection::NegativeZ,
866                LightAxisDirection::PositiveY,
867                LightAxisDirection::NegativeY,
868            ]
869        );
870        assert_eq!(
871            LightAxisDirection::HORIZONTAL,
872            [
873                LightAxisDirection::PositiveX,
874                LightAxisDirection::NegativeX,
875                LightAxisDirection::PositiveZ,
876                LightAxisDirection::NegativeZ,
877            ]
878        );
879
880        assert_eq!(LightAxisDirection::PositiveX.bit_index(), 0);
881        assert_eq!(LightAxisDirection::NegativeX.bit_index(), 1);
882        assert_eq!(LightAxisDirection::PositiveZ.bit_index(), 2);
883        assert_eq!(LightAxisDirection::NegativeZ.bit_index(), 3);
884        assert_eq!(LightAxisDirection::PositiveY.bit_index(), 4);
885        assert_eq!(LightAxisDirection::NegativeY.bit_index(), 5);
886    }
887
888    #[test]
889    fn light_axis_direction_maps_to_steel_direction() {
890        assert_eq!(
891            LightAxisDirection::from_direction(Direction::East),
892            LightAxisDirection::PositiveX
893        );
894        assert_eq!(
895            LightAxisDirection::from_direction(Direction::West),
896            LightAxisDirection::NegativeX
897        );
898        assert_eq!(
899            LightAxisDirection::from_direction(Direction::South),
900            LightAxisDirection::PositiveZ
901        );
902        assert_eq!(
903            LightAxisDirection::from_direction(Direction::North),
904            LightAxisDirection::NegativeZ
905        );
906        assert_eq!(
907            LightAxisDirection::from_direction(Direction::Up),
908            LightAxisDirection::PositiveY
909        );
910        assert_eq!(
911            LightAxisDirection::from_direction(Direction::Down),
912            LightAxisDirection::NegativeY
913        );
914
915        assert_eq!(LightAxisDirection::PositiveX.direction(), Direction::East);
916        assert_eq!(LightAxisDirection::NegativeX.direction(), Direction::West);
917        assert_eq!(LightAxisDirection::PositiveZ.direction(), Direction::South);
918        assert_eq!(LightAxisDirection::NegativeZ.direction(), Direction::North);
919        assert_eq!(LightAxisDirection::PositiveY.direction(), Direction::Up);
920        assert_eq!(LightAxisDirection::NegativeY.direction(), Direction::Down);
921
922        assert_eq!(LightAxisDirection::PositiveX.offset(), (1, 0, 0));
923        assert_eq!(LightAxisDirection::NegativeX.offset(), (-1, 0, 0));
924        assert_eq!(LightAxisDirection::PositiveZ.offset(), (0, 0, 1));
925        assert_eq!(LightAxisDirection::NegativeZ.offset(), (0, 0, -1));
926        assert_eq!(LightAxisDirection::PositiveY.offset(), (0, 1, 0));
927        assert_eq!(LightAxisDirection::NegativeY.offset(), (0, -1, 0));
928    }
929
930    #[test]
931    fn light_axis_direction_opposites_flip_low_bit() {
932        for direction in LightAxisDirection::ALL {
933            assert_eq!(direction.opposite().bit_index(), direction.bit_index() ^ 1);
934            assert_eq!(direction.opposite().opposite(), direction);
935        }
936    }
937
938    #[test]
939    fn light_direction_set_matches_scalable_lux_masks() {
940        assert_eq!(LightDirectionSet::empty().raw(), 0);
941        assert_eq!(LightDirectionSet::all().raw(), 0b11_1111);
942        assert_eq!(LightDirectionSet::from_raw(u8::MAX).raw(), 0b11_1111);
943        assert_eq!(
944            LightDirectionSet::only(LightAxisDirection::PositiveZ).raw(),
945            0b00_0100
946        );
947        assert_eq!(
948            LightDirectionSet::all_except(LightAxisDirection::PositiveZ).raw(),
949            0b11_1011
950        );
951        assert_eq!(
952            LightDirectionSet::all_except_opposite(LightAxisDirection::PositiveZ).raw(),
953            0b11_0111
954        );
955
956        let set = LightDirectionSet::from_raw(0b10_0101);
957        assert!(set.contains(LightAxisDirection::PositiveX));
958        assert!(set.contains(LightAxisDirection::PositiveZ));
959        assert!(set.contains(LightAxisDirection::NegativeY));
960        assert!(!set.contains(LightAxisDirection::NegativeX));
961        assert!(!set.contains(LightAxisDirection::NegativeZ));
962        assert!(!set.contains(LightAxisDirection::PositiveY));
963    }
964
965    #[test]
966    fn light_direction_set_iterates_in_scalable_lux_order() {
967        let mut directions = LightDirectionSet::from_raw(0b10_1101).directions();
968
969        assert_eq!(directions.len(), 4);
970        assert_eq!(directions.next(), Some(LightAxisDirection::PositiveX));
971        assert_eq!(directions.next(), Some(LightAxisDirection::PositiveZ));
972        assert_eq!(directions.len(), 2);
973        assert_eq!(directions.next(), Some(LightAxisDirection::NegativeZ));
974        assert_eq!(directions.next(), Some(LightAxisDirection::NegativeY));
975        assert_eq!(directions.next(), None);
976        assert_eq!(directions.next(), None);
977    }
978
979    #[test]
980    fn light_queue_flags_match_scalable_lux_top_bits() {
981        assert_eq!(LightQueueFlags::WRITE_LEVEL.raw(), 1_u64 << 61);
982        assert_eq!(LightQueueFlags::RECHECK_LEVEL.raw(), 1_u64 << 62);
983        assert_eq!(
984            LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS.raw(),
985            1_u64 << 63
986        );
987
988        let flags = LightQueueFlags::EMPTY
989            .with(LightQueueFlags::WRITE_LEVEL)
990            .with(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS);
991        assert!(flags.contains(LightQueueFlags::WRITE_LEVEL));
992        assert!(!flags.contains(LightQueueFlags::RECHECK_LEVEL));
993        assert!(flags.contains(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS));
994        assert_eq!(
995            LightQueueFlags::from_raw(u64::MAX).raw(),
996            LightQueueFlags::WRITE_LEVEL
997                .with(LightQueueFlags::RECHECK_LEVEL)
998                .with(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS)
999                .raw()
1000        );
1001    }
1002
1003    #[test]
1004    fn packed_light_queue_entry_matches_scalable_lux_bit_layout() {
1005        let position = PackedLightBlockPos::from_raw(0x0abc_def0);
1006        let directions = LightDirectionSet::from_raw(0b10_1011);
1007        let flags = LightQueueFlags::EMPTY
1008            .with(LightQueueFlags::WRITE_LEVEL)
1009            .with(LightQueueFlags::HAS_SIDED_TRANSPARENT_BLOCKS);
1010        let entry = PackedLightQueueEntry::from_parts(position, 31, directions, flags);
1011
1012        assert_eq!(entry.block_pos(), position);
1013        assert_eq!(entry.level(), 15);
1014        assert_eq!(entry.directions(), directions);
1015        assert_eq!(entry.flags(), flags);
1016        assert!(entry.should_write_level());
1017        assert!(!entry.should_recheck_level());
1018        assert!(entry.has_sided_transparent_blocks());
1019        assert_eq!(entry.raw() & ((1_u64 << 28) - 1), u64::from(position.raw()));
1020        assert_eq!((entry.raw() >> 28) & 0x0f, 15);
1021        assert_eq!((entry.raw() >> 32) & 0x3f, u64::from(directions.raw()));
1022        assert_eq!(entry.raw() & (1_u64 << 61), 1_u64 << 61);
1023        assert_eq!(entry.raw() & (1_u64 << 62), 0);
1024        assert_eq!(entry.raw() & (1_u64 << 63), 1_u64 << 63);
1025    }
1026
1027    #[test]
1028    fn packed_light_queue_entry_reads_raw_scalable_lux_values() {
1029        let raw = u64::MAX;
1030        let entry = PackedLightQueueEntry::from_raw(raw);
1031
1032        assert_eq!(entry.raw(), raw);
1033        assert_eq!(entry.block_pos().raw(), (1 << 28) - 1);
1034        assert_eq!(entry.level(), 15);
1035        assert_eq!(entry.directions(), LightDirectionSet::all());
1036        assert!(entry.should_write_level());
1037        assert!(entry.should_recheck_level());
1038        assert!(entry.has_sided_transparent_blocks());
1039    }
1040
1041    #[test]
1042    fn packed_light_propagation_queue_preserves_fifo_order() {
1043        let first = packed_entry(1);
1044        let second = packed_entry(2);
1045        let third = packed_entry(3);
1046        let mut queue = PackedLightPropagationQueue::new();
1047
1048        assert!(queue.is_empty());
1049        queue.enqueue(first);
1050        queue.enqueue(second);
1051        assert_eq!(queue.len(), 2);
1052        assert_eq!(queue.dequeue(), Some(first));
1053
1054        queue.enqueue(third);
1055        assert_eq!(queue.len(), 2);
1056        assert_eq!(queue.dequeue(), Some(second));
1057        assert_eq!(queue.dequeue(), Some(third));
1058        assert_eq!(queue.dequeue(), None);
1059        assert!(queue.is_empty());
1060    }
1061
1062    #[test]
1063    fn packed_light_propagation_queues_keep_increase_and_decrease_work_separate() {
1064        let decrease_entry = packed_entry(6);
1065        let increase_entry = packed_entry(7);
1066        let mut queues = PackedLightPropagationQueues::new();
1067
1068        assert!(!queues.has_work());
1069        queues.enqueue_decrease(decrease_entry);
1070        queues.enqueue_increase(increase_entry);
1071        assert!(queues.has_work());
1072
1073        assert_eq!(queues.dequeue_increase(), Some(increase_entry));
1074        assert_eq!(queues.dequeue_increase(), None);
1075        assert!(queues.has_work());
1076
1077        assert_eq!(queues.dequeue_decrease(), Some(decrease_entry));
1078        assert_eq!(queues.dequeue_decrease(), None);
1079        assert!(!queues.has_work());
1080    }
1081
1082    #[test]
1083    fn light_queue_entry_decrease_entries_match_vanilla_bits() {
1084        let all = LightQueueEntry::decrease_all_directions(7);
1085
1086        assert_eq!(all.raw(), 0b11_1111_0000 | 7);
1087        assert_eq!(all.level(), 7);
1088        for direction in Direction::ALL {
1089            assert!(all.should_propagate_in_direction(direction));
1090        }
1091        assert!(!all.is_from_empty_shape());
1092        assert!(!all.is_increase_from_emission());
1093
1094        let skip_north = LightQueueEntry::decrease_skip_one_direction(7, Direction::North);
1095        assert_eq!(skip_north.raw(), 951);
1096        assert!(!skip_north.should_propagate_in_direction(Direction::North));
1097        assert!(skip_north.should_propagate_in_direction(Direction::South));
1098    }
1099
1100    #[test]
1101    fn light_queue_entry_increase_entries_match_vanilla_bits() {
1102        let emission = LightQueueEntry::increase_light_from_emission(15, true);
1103        assert_eq!(emission.raw(), 4095);
1104        assert_eq!(emission.level(), 15);
1105        assert!(emission.is_from_empty_shape());
1106        assert!(emission.is_increase_from_emission());
1107
1108        let skip_up = LightQueueEntry::increase_skip_one_direction(10, false, Direction::Up);
1109        assert_eq!(skip_up.raw(), 986);
1110        assert!(!skip_up.is_from_empty_shape());
1111        assert!(!skip_up.is_increase_from_emission());
1112        assert!(!skip_up.should_propagate_in_direction(Direction::Up));
1113        assert!(skip_up.should_propagate_in_direction(Direction::Down));
1114
1115        let east_only = LightQueueEntry::increase_only_one_direction(4, true, Direction::East);
1116        assert_eq!(east_only.raw(), 1540);
1117        assert!(east_only.is_from_empty_shape());
1118        assert!(east_only.should_propagate_in_direction(Direction::East));
1119        assert!(!east_only.should_propagate_in_direction(Direction::West));
1120    }
1121
1122    #[test]
1123    fn light_queue_entry_sky_source_entry_selects_horizontal_and_down_directions() {
1124        let entry = LightQueueEntry::increase_sky_source_in_directions(&[
1125            Direction::Down,
1126            Direction::North,
1127            Direction::West,
1128        ]);
1129
1130        assert_eq!(entry.raw(), 351);
1131        assert_eq!(entry.level(), 15);
1132        assert!(entry.should_propagate_in_direction(Direction::Down));
1133        assert!(!entry.should_propagate_in_direction(Direction::Up));
1134        assert!(entry.should_propagate_in_direction(Direction::North));
1135        assert!(!entry.should_propagate_in_direction(Direction::South));
1136        assert!(entry.should_propagate_in_direction(Direction::West));
1137        assert!(!entry.should_propagate_in_direction(Direction::East));
1138    }
1139
1140    #[test]
1141    fn light_queue_entry_masks_levels_like_vanilla() {
1142        let entry = LightQueueEntry::increase_light_from_emission(31, false);
1143
1144        assert_eq!(entry.level(), 15);
1145        assert_eq!(entry.raw(), 0b11_1111_0000 | 0b1000_0000_0000 | 15);
1146    }
1147
1148    #[test]
1149    fn light_propagation_queue_preserves_fifo_order() {
1150        let first_pos = BlockPos::new(1, 2, 3);
1151        let second_pos = BlockPos::new(4, 5, 6);
1152        let first_entry = LightQueueEntry::decrease_all_directions(3);
1153        let second_entry =
1154            LightQueueEntry::increase_skip_one_direction(12, false, Direction::North);
1155        let mut queue = LightPropagationQueue::new();
1156
1157        queue.enqueue(first_pos, first_entry);
1158        queue.enqueue(second_pos, second_entry);
1159
1160        assert_eq!(queue.len(), 2);
1161        assert_eq!(
1162            queue.dequeue(),
1163            Some(QueuedLightUpdate {
1164                block_pos: first_pos,
1165                entry: first_entry,
1166            })
1167        );
1168        assert_eq!(
1169            queue.dequeue(),
1170            Some(QueuedLightUpdate {
1171                block_pos: second_pos,
1172                entry: second_entry,
1173            })
1174        );
1175        assert_eq!(queue.dequeue(), None);
1176        assert!(queue.is_empty());
1177    }
1178
1179    #[test]
1180    fn light_propagation_queues_keep_increase_and_decrease_work_separate() {
1181        let decrease_pos = BlockPos::new(1, 2, 3);
1182        let increase_pos = BlockPos::new(4, 5, 6);
1183        let decrease_entry = LightQueueEntry::decrease_all_directions(4);
1184        let increase_entry = LightQueueEntry::increase_only_one_direction(9, true, Direction::East);
1185        let mut queues = LightPropagationQueues::new();
1186
1187        assert!(!queues.has_work());
1188
1189        queues.enqueue_decrease(decrease_pos, decrease_entry);
1190        queues.enqueue_increase(increase_pos, increase_entry);
1191
1192        assert!(queues.has_work());
1193        assert_eq!(
1194            queues.dequeue_increase(),
1195            Some(QueuedLightUpdate {
1196                block_pos: increase_pos,
1197                entry: increase_entry,
1198            })
1199        );
1200        assert!(queues.has_work());
1201        assert_eq!(
1202            queues.dequeue_decrease(),
1203            Some(QueuedLightUpdate {
1204                block_pos: decrease_pos,
1205                entry: decrease_entry,
1206            })
1207        );
1208        assert!(!queues.has_work());
1209    }
1210
1211    #[test]
1212    fn oversized_lease_preserves_parked_pool_entry() {
1213        let mut oversized = PooledPackedLightQueues::take();
1214        for _ in 0..=POOLED_PACKED_QUEUES_MAX_ENTRIES {
1215            oversized.enqueue_increase(packed_entry(15));
1216        }
1217        assert!(oversized.total_capacity() > POOLED_PACKED_QUEUES_MAX_ENTRIES);
1218
1219        // Lease a second pair while the oversized one is still open; dropping
1220        // it parks buffers that the oversized lease's drop must not evict.
1221        let mut parked = PooledPackedLightQueues::take();
1222        for _ in 0..=PACKED_LIGHT_QUEUE_MIN_CAPACITY {
1223            parked.enqueue_increase(packed_entry(15));
1224        }
1225        let parked_capacity = parked.total_capacity();
1226        assert!(parked_capacity > 2 * PACKED_LIGHT_QUEUE_MIN_CAPACITY);
1227        drop(parked);
1228
1229        drop(oversized);
1230
1231        assert_eq!(
1232            PooledPackedLightQueues::take().total_capacity(),
1233            parked_capacity
1234        );
1235    }
1236}
steel_core/chunk/light/queue.rs

steel_core/chunk/light/
queue.rs
