all_is_cubes/space/
palette.rs

1//! [`Palette`] and related.
2
3#![allow(
4    elided_lifetimes_in_paths,
5    clippy::needless_pass_by_value,
6    reason = "Bevy systems"
7)]
8
9use alloc::sync::{Arc, Weak};
10use alloc::vec::Vec;
11use core::cell::Cell;
12use core::fmt;
13use core::sync::atomic::Ordering;
14
15use bevy_ecs::change_detection::DetectChangesMut as _;
16use bevy_ecs::prelude as ecs;
17use bevy_ecs::schedule::IntoScheduleConfigs as _;
18use bevy_platform::sync::Mutex;
19use hashbrown::HashMap as HbHashMap;
20use itertools::Itertools as _;
21
22use crate::block::{self, AIR, AIR_EVALUATED, Block, BlockChange, EvaluatedBlock};
23use crate::listen::{self, Listener as _};
24use crate::math::{self, OpacityCategory};
25use crate::space::{BlockIndex, ChangeBuffer, SetCubeError, SpaceChange};
26use crate::time::{self, TimeStats};
27use crate::universe::{self, ReadTicket};
28use crate::util::atomic_cell::{AtomicCell32 as AtomicCell, ZERO, ZERO3, Zero, Zero3};
29
30#[cfg(doc)]
31use crate::space;
32
33cfg_if::cfg_if! {
34    if #[cfg(feature = "std")] {
35        // HashDoS-resistant
36        use std::collections::HashMap as BlockHashMap;
37    } else {
38        // no_std compatible
39        use hashbrown::HashMap as BlockHashMap;
40    }
41
42}
43
44// -------------------------------------------------------------------------------------------------
45
46/// Table of the [`Block`]s in a [`Space`](super::Space) independent of their location.
47#[derive(ecs::Component)]
48#[require(PaletteUpdates)]
49// Note: visibility must be pub(crate) to work with ECS, but only manipulated by `space` code
50pub(crate) struct Palette {
51    /// Lookup from arbitrarily assigned indices to blocks.
52    entries: Vec<SpaceBlockData>,
53
54    /// Reverse lookup from `Block` value to the index in `entries`.
55    //---
56    // TODO: We may want to switch this to
57    block_to_index: BlockHashMap<Block, BlockIndex>,
58
59    /// Storage for incoming change notifications from blocks.
60    todo: Arc<Mutex<PaletteTodo>>,
61}
62
63impl Palette {
64    /// Constructs a new `Palette` with one entry, or zero entries if `count` is zero.
65    pub(crate) fn new(read_ticket: ReadTicket<'_>, block: Block, count: usize) -> Self {
66        let todo = Default::default();
67
68        if count == 0 {
69            return Self {
70                entries: Vec::new(),
71                block_to_index: BlockHashMap::new(),
72                todo,
73            };
74        }
75
76        let gate = Arc::new(());
77        let mut block_data = SpaceBlockData::new(
78            read_ticket,
79            block.clone(),
80            // initial-creation version of listener_for_block()
81            Arc::new(BlockListener {
82                gate: Arc::downgrade(&gate),
83                todo: Arc::downgrade(&todo),
84                index: AtomicCell::new(ListenerIndexState::Set(ZERO, 0)),
85            }),
86            gate,
87        );
88
89        block_data.count = count;
90
91        Self {
92            entries: vec![block_data],
93            block_to_index: BlockHashMap::from([(block, 0)]),
94            todo,
95        }
96    }
97
98    /// Constructs a `Palette` with the given blocks and all zero counts.
99    ///
100    /// If the input contains any duplicate entries, then they will be combined, and the
101    /// returned [`hashbrown::HashMap`] will contain the required data remapping.
102    /// Any index not requiring remapping will be absent from the map.
103    pub(crate) fn from_blocks(
104        read_ticket: ReadTicket<'_>,
105        blocks: &mut dyn ExactSizeIterator<Item = Block>,
106    ) -> Result<(Self, hashbrown::HashMap<BlockIndex, BlockIndex>), PaletteError> {
107        let dummy_notifier = listen::Notifier::new();
108        let dummy_buffer = &mut dummy_notifier.buffer();
109
110        let len = blocks.len();
111        if len.saturating_sub(1) > (BlockIndex::MAX as usize) {
112            return Err(PaletteError::PaletteTooLarge { len });
113        }
114
115        let mut new_self = Self {
116            entries: Vec::with_capacity(blocks.len()),
117            block_to_index: BlockHashMap::with_capacity(blocks.len()),
118            todo: Default::default(),
119        };
120
121        let mut remapping = hashbrown::HashMap::new();
122        for (original_index, block) in (0..=BlockIndex::MAX).zip(blocks) {
123            let new_index = new_self
124                .ensure_index(
125                    &mut EvaluationMethod::Ticket(read_ticket),
126                    &block,
127                    dummy_buffer,
128                    false,
129                )
130                .expect("palette iterator lied about its length");
131            if new_index != original_index {
132                remapping.insert(original_index, new_index);
133            }
134        }
135
136        Ok((new_self, remapping))
137    }
138
139    pub(crate) fn entries(&self) -> &[SpaceBlockData] {
140        &self.entries
141    }
142
143    /// Get an entry by index. Panics if out of range.
144    #[inline]
145    #[track_caller]
146    pub(crate) fn entry(&self, index: BlockIndex) -> &SpaceBlockData {
147        &self.entries[index as usize]
148    }
149
150    /// If this palette contains only blocks of uniform [`EvaluatedBlock::opacity_as_category()`]
151    /// according to their current evaluations, return that, otherwise
152    /// return [`OpacityCategory::Partial`].
153    pub(crate) fn all_block_opacities_as_category(&self) -> OpacityCategory {
154        self.entries
155            .iter()
156            .map(|entry| entry.evaluated.opacity_as_category())
157            .all_equal_value()
158            .unwrap_or(OpacityCategory::Partial)
159    }
160
161    /// Finds or creates a new palette entry for the given block, and returns the index.
162    ///
163    /// The caller is responsible for incrementing the count to indicate usage of the entry.
164    ///
165    /// If `use_zeroed_entries` is true, then entries which currently have a count of zero
166    /// will be considered free for reuse. If it is false, they will not, and every returned index
167    /// will either be an existing block or extend the palette.
168    #[inline]
169    pub(super) fn ensure_index(
170        &mut self,
171        evaluation_method: &mut EvaluationMethod<'_>,
172        block: &Block,
173        change_buffer: &mut ChangeBuffer<'_>,
174        use_zeroed_entries: bool,
175    ) -> Result<BlockIndex, TooManyBlocks> {
176        if let Some(&old_index) = self.block_to_index.get(block) {
177            Ok(old_index)
178        } else {
179            // Look for if there is a previously used index to take.
180            // TODO: more efficient free index finding
181            let high_mark = self.entries.len();
182            if use_zeroed_entries {
183                for new_index in 0..high_mark {
184                    if self.entries[new_index].count == 0 {
185                        self.entries[new_index] = self.create_pending_entry(
186                            evaluation_method,
187                            block.clone(),
188                            new_index as BlockIndex,
189                        );
190                        self.block_to_index.insert(block.clone(), new_index as BlockIndex);
191                        change_buffer.push(SpaceChange::BlockIndex(new_index as BlockIndex));
192                        return Ok(new_index as BlockIndex);
193                    }
194                }
195            }
196            if high_mark > BlockIndex::MAX as usize {
197                return Err(TooManyBlocks);
198            }
199            let new_index = high_mark as BlockIndex;
200            // Evaluate the new block type.
201            let new_data = self.create_pending_entry(evaluation_method, block.clone(), new_index);
202            // Grow the vector.
203            self.entries.push(new_data);
204            self.block_to_index.insert(block.clone(), new_index);
205            change_buffer.push(SpaceChange::BlockIndex(new_index));
206            Ok(new_index)
207        }
208    }
209
210    /// Determine whether `old_block_index` has a count of 1, and if it does, replace the
211    /// [`Block`] for that index with `new_block`
212    pub(super) fn try_replace_unique(
213        &mut self,
214        evaluation_method: &mut EvaluationMethod<'_>,
215        old_block_index: BlockIndex,
216        new_block: &Block,
217        change_buffer: &mut ChangeBuffer<'_>,
218    ) -> bool {
219        if self.entries[old_block_index as usize].count == 1
220            && !self.block_to_index.contains_key(new_block)
221        {
222            // Swap out the block_data entry.
223            let old_block = {
224                let mut data = self.create_pending_entry(
225                    evaluation_method,
226                    new_block.clone(),
227                    old_block_index,
228                );
229                data.count = 1;
230                core::mem::swap(&mut data, &mut self.entries[old_block_index as usize]);
231                data.block
232            };
233
234            // Update block_to_index.
235            self.block_to_index.remove(&old_block);
236            self.block_to_index.insert(new_block.clone(), old_block_index);
237
238            change_buffer.push(SpaceChange::BlockIndex(old_block_index));
239
240            true
241        } else {
242            false
243        }
244    }
245
246    pub(crate) fn increment(&mut self, index: u16) {
247        self.entries[index as usize].count += 1
248    }
249
250    pub(crate) fn decrement_maybe_free(&mut self, old_block_index: BlockIndex) {
251        let old_data: &mut SpaceBlockData = &mut self.entries[old_block_index as usize];
252        old_data.count -= 1;
253        if old_data.count == 0 {
254            // Free data of old entry.
255            self.block_to_index.remove(&old_data.block);
256            *old_data = SpaceBlockData::tombstone();
257        }
258    }
259
260    pub(crate) fn free_all_zero_counts(&mut self) {
261        for data in self.entries.iter_mut() {
262            if data.count == 0 {
263                self.block_to_index.remove(&data.block);
264                *data = SpaceBlockData::tombstone();
265            }
266        }
267    }
268
269    /// Creates a [`SpaceBlockData`] for a block newly entering the palette, with its listener
270    /// hooked up.
271    fn create_pending_entry(
272        &self,
273        evaluation_method: &mut EvaluationMethod<'_>,
274        block: Block,
275        index: BlockIndex,
276    ) -> SpaceBlockData {
277        match evaluation_method {
278            &mut EvaluationMethod::Ticket(read_ticket) => {
279                let (listener, gate) =
280                    self.listener_for_block(ListenerIndexState::Set(ZERO, index));
281                SpaceBlockData::new(read_ticket, block, listener, gate)
282            }
283            EvaluationMethod::AlreadyEvaluated(data) => {
284                let PendingEvaluation { entry, listener } =
285                    data.take().expect("shouldn’t happen: new entry already taken");
286                let already_changed = listener.set_index(index);
287                if already_changed {
288                    self.todo.lock().unwrap().blocks.insert(index);
289                }
290                entry
291            }
292        }
293    }
294
295    /// Creates the [`BlockListener`] communicating with this palette for a particular index
296    /// (or the index is not yet known).
297    ///
298    /// This is used when a new block is to be inserted into the palette,
299    /// in order to be notified of changes to the block definition.
300    fn listener_for_block(&self, index_state: ListenerIndexState) -> (Arc<BlockListener>, Arc<()>) {
301        let gate = Arc::new(());
302        let listener = Arc::new(BlockListener {
303            gate: Arc::downgrade(&gate),
304            todo: Arc::downgrade(&self.todo),
305            index: AtomicCell::new(index_state),
306        });
307        (listener, gate)
308    }
309
310    /// Check that this palette is self-consistent and has `count`s that accurately count the
311    /// `contents`.
312    #[cfg(test)]
313    #[track_caller]
314    pub(crate) fn consistency_check(&self, contents: &[BlockIndex]) {
315        let mut problems = Vec::new();
316
317        let mut actual_counts: hashbrown::HashMap<BlockIndex, usize> = Default::default();
318        for index in contents.iter().copied() {
319            *actual_counts.entry(index).or_insert(0) += 1;
320        }
321
322        // Check that block_data has only correct counts.
323        for (index, data) in self.entries.iter().enumerate() {
324            let index = index as BlockIndex;
325
326            let actual_count = actual_counts.remove(&index).unwrap_or(0);
327            if data.count != actual_count {
328                problems.push(format!(
329                    "Index {} appears {} times but {:?}",
330                    index, actual_count, &data
331                ));
332            }
333        }
334
335        // Check that block_data isn't missing any indexes that appeared in contents.
336        // (The previous section should have drained actual_counts).
337        if !actual_counts.is_empty() {
338            problems.push(format!(
339                "Block indexes were not indexed in palette: {:?}",
340                &actual_counts
341            ));
342        }
343
344        // Check that block_to_index contains all entries it should.
345        for (index, data) in self.entries.iter().enumerate() {
346            if data.count == 0 {
347                // Zero entries are tombstone entries that should not be expected in the mapping.
348                continue;
349            }
350            let bti_index = self.block_to_index.get(&data.block).copied();
351            if bti_index != Some(index as BlockIndex) {
352                problems.push(format!(
353                    "block_to_index[{:?}] should have been {:?}={:?} but was {:?}={:?}",
354                    &data.block,
355                    index,
356                    data,
357                    bti_index,
358                    bti_index.map(|i| self.entries.get(usize::from(i))),
359                ));
360            }
361        }
362        // Check that block_to_index contains no incorrect entries.
363        for (block, &index) in self.block_to_index.iter() {
364            let data = self.entries.get(usize::from(index));
365            if Some(block) != data.map(|data| &data.block) {
366                problems.push(format!(
367                    "block_to_index[{block:?}] points to {index} : {data:?}"
368                ));
369            }
370        }
371
372        if !problems.is_empty() {
373            panic!(
374                "Palette consistency check failed:\n • {}\n",
375                problems.join("\n • ")
376            );
377        }
378    }
379
380    /// Returns whether the given block in this space’s palette is to be reevaluated
381    /// (such as because of having received a change notification).
382    ///
383    /// Panics if the block is not in the palette.
384    #[cfg(test)]
385    pub(crate) fn block_is_to_be_reevaluated(&self, block: &Block) -> bool {
386        let index = self.block_to_index[block];
387        self.todo.lock().unwrap().blocks.contains(&index)
388    }
389}
390
391impl fmt::Debug for Palette {
392    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
393        let Self {
394            entries,
395            block_to_index: _,
396            todo: _,
397        } = self;
398
399        // Inherit the alternate/prettyprint state, but don't put any
400        // prettyprint space between the () and the [].
401        write!(fmt, "Palette(")?;
402        fmt::Debug::fmt(entries, fmt)?;
403        write!(fmt, ")")?;
404        Ok(())
405    }
406}
407
408impl universe::VisitHandles for Palette {
409    fn visit_handles(&self, visitor: &mut dyn universe::HandleVisitor) {
410        for SpaceBlockData { block, .. } in self.entries.iter() {
411            block.visit_handles(visitor);
412        }
413    }
414}
415
416impl Clone for Palette {
417    /// Cloning a [`Palette`] produces a copy which is independently mutable and
418    /// independently tracks block changes, but initially has the same state. It will
419    /// reevaluate on the next `step()`.
420    fn clone(&self) -> Self {
421        // Construct the new set with a full todo so that it establishes listeners.
422        // This will unfortunately also cause a reevaluation, but avoiding that would
423        // be additional complexity.
424        let todo = Arc::new(Mutex::new(PaletteTodo {
425            blocks: hashbrown::HashSet::from_iter((0..self.entries.len()).map(|i| i as BlockIndex)),
426        }));
427
428        Self {
429            entries: self
430                .entries()
431                .iter()
432                .map(|e| SpaceBlockData {
433                    block: e.block.clone(),
434                    count: e.count,
435                    evaluated: e.evaluated.clone(),
436                    block_listen_gate: None,
437                })
438                .collect(),
439            block_to_index: self.block_to_index.clone(),
440            todo,
441        }
442    }
443}
444
445/// Information about the interpretation of a block index.
446///
447/// Design note: This doubles as an internal data structure for [`Space`]. While we'll
448/// try to keep it available, this interface has a higher risk of needing to change
449/// incompatibility.
450///
451/// [`Space`]: crate::space::Space
452//
453// TODO: rename this struct to `PaletteEntry` or something?
454pub struct SpaceBlockData {
455    /// The block itself.
456    pub(super) block: Block,
457    /// Number of uses of this block in the space.
458    count: usize,
459    pub(super) evaluated: EvaluatedBlock,
460    #[expect(dead_code, reason = "Used only for its `Drop`")]
461    block_listen_gate: Option<Arc<()>>,
462}
463
464impl fmt::Debug for SpaceBlockData {
465    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
466        // Omit the evaluated data because it is usually redundant.
467        // We may regret this later...
468        fmt.debug_struct("SpaceBlockData")
469            .field("count", &self.count)
470            .field("block", &self.block)
471            .finish_non_exhaustive()
472    }
473}
474
475impl SpaceBlockData {
476    /// A `SpaceBlockData` value used to represent out-of-bounds or placeholder
477    /// situations. The block is [`AIR`] and the count is always zero.
478    pub const NOTHING: Self = Self {
479        block: AIR,
480        count: 0,
481        evaluated: AIR_EVALUATED,
482        block_listen_gate: None,
483    };
484
485    /// Value used to fill empty entries in the block data vector.
486    /// This is the same value as [`SpaceBlockData::NOTHING`] but is not merely done
487    /// by `.clone()` because I haven't decided whether providing [`Clone`] for
488    /// `SpaceBlockData` is a good long-term API design decision.
489    fn tombstone() -> Self {
490        Self {
491            block: AIR,
492            count: 0,
493            evaluated: AIR_EVALUATED,
494            block_listen_gate: None,
495        }
496    }
497
498    fn new(
499        read_ticket: ReadTicket<'_>,
500        block: Block,
501        block_listener: Arc<BlockListener>,
502        block_listen_gate: Arc<()>,
503    ) -> Self {
504        // Note: Block evaluation also happens in `Space` stepping.
505
506        let block_listener: listen::DynListener<BlockChange> = block_listener; // coerce to dyn
507
508        let original_budget = block::Budget::default();
509        let filter = block::EvalFilter {
510            read_ticket,
511            skip_eval: false,
512            listener: Some(block_listener.clone()),
513            budget: Cell::new(original_budget),
514        };
515        let evaluated = match block.evaluate2(&filter) {
516            Ok(ev) => ev,
517            Err(err) => {
518                // Trigger retrying evaluation at next step.
519                block_listener.receive(&[BlockChange::new()]);
520                // Use a placeholder value.
521                err.to_placeholder()
522            }
523        };
524        Self {
525            block,
526            count: 0,
527            evaluated,
528            block_listen_gate: Some(block_listen_gate),
529        }
530    }
531
532    /// Returns the [`Block`] this data is about.
533    #[inline]
534    pub fn block(&self) -> &Block {
535        &self.block
536    }
537
538    /// Returns the [`EvaluatedBlock`] representation of the block.
539    ///
540    /// TODO: Describe when this may be stale.
541    #[inline]
542    pub fn evaluated(&self) -> &EvaluatedBlock {
543        &self.evaluated
544    }
545
546    #[inline]
547    pub(crate) fn count(&self) -> usize {
548        self.count
549    }
550
551    // TODO: Expose the count field? It is the most like an internal bookkeeping field,
552    // but might be interesting 'statistics'.
553}
554
555// -------------------------------------------------------------------------------------------------
556
557/// A means of evaluating new blocks entering the palette.
558#[allow(clippy::large_enum_variant)]
559pub(in crate::space) enum EvaluationMethod<'t> {
560    /// Use the given [`ReadTicket`] to evaluate the block.
561    Ticket(ReadTicket<'t>),
562
563    /// The block has already been evaluated; use the given [`SpaceBlockData`] as the evaluation
564    /// result, and tell the [`BlockListener`] what index it is being assigned.
565    ///
566    /// All this is wrapped in [`Option`] so that it can be used in cases where the data may or
567    /// may not be consumed.
568    AlreadyEvaluated(Option<PendingEvaluation>),
569}
570
571// -------------------------------------------------------------------------------------------------
572
573/// [`Palette`]'s todo list for the next `step()`.
574#[derive(Debug, Default)]
575struct PaletteTodo {
576    blocks: hashbrown::HashSet<BlockIndex>,
577}
578
579// -------------------------------------------------------------------------------------------------
580
581/// [`PaletteTodo`]'s listener for block change notifications, installed on blocks when they
582/// are inserted into the palette.
583#[derive(Debug)]
584struct BlockListener {
585    /// This weak reference breaks when our entry is removed from the palette,
586    /// telling us to stop sending changes even though `todo` may be still alive.
587    gate: Weak<()>,
588
589    /// Way we write notifications to the palette.
590    todo: Weak<Mutex<PaletteTodo>>,
591
592    /// Index in the palette this listener is for, and related state.
593    index: AtomicCell<ListenerIndexState>,
594}
595
596/// Association of a [`BlockListener`] with a specific palette entry, or lack thereof.
597///
598/// This enum can be stored in an [`AtomicCell`] and is crufty in order to support that.
599#[repr(u8, align(4))]
600#[derive(Debug, Clone, Copy, bytemuck::NoUninit, bytemuck::CheckedBitPattern)]
601enum ListenerIndexState {
602    /// The listener does not yet know the palette entry’s index,
603    /// AND has not yet received any messages.
604    ///
605    /// `Zero3` is just padding-filler to enable our atomic operations.
606    Unset(Zero3),
607
608    /// The listener does not yet know the palette entry’s index,
609    /// AND has received a message.
610    ///
611    /// `Zero3` is just padding-filler to enable our atomic operations.
612    AlreadyChanged(Zero3),
613
614    /// The listener knows the palette entry’s index.
615    /// Messages are forwarded to [`super::PaletteTodo`].
616    ///
617    /// `Zero` is just padding-filler to enable our atomic operations.
618    Set(Zero, BlockIndex),
619}
620
621impl BlockListener {
622    /// Sets the index, and returns whether any change notifications arrived before then.
623    #[must_use]
624    fn set_index(&self, index: BlockIndex) -> bool {
625        match self.index.swap(ListenerIndexState::Set(ZERO, index), Ordering::Release) {
626            ListenerIndexState::Unset(ZERO3) => false,
627            ListenerIndexState::AlreadyChanged(ZERO3) => true,
628            ListenerIndexState::Set(ZERO, _index) => panic!("index should only be set once"),
629        }
630    }
631}
632
633impl listen::Listener<BlockChange> for BlockListener {
634    fn receive(&self, messages: &[BlockChange]) -> bool {
635        if self.gate.strong_count() == 0 {
636            false
637        } else if let Some(todo_mutex) = self.todo.upgrade() {
638            if !messages.is_empty() {
639                // Obtain the index, if we have one; else record that we got a notification without
640                // an index to record it in the todo.
641                let index = match self.index.compare_exchange(
642                    ListenerIndexState::Unset(ZERO3),
643                    ListenerIndexState::AlreadyChanged(ZERO3),
644                    Ordering::AcqRel,
645                    Ordering::Acquire,
646                ) {
647                    Ok(_) | Err(ListenerIndexState::AlreadyChanged(ZERO3)) => {
648                        // The exchange either succeeded or was already performed, which constitutes
649                        // delivery of our change notification despite the lack of an index value.
650                        return true;
651                    }
652                    Err(ListenerIndexState::Set(ZERO, index)) => index,
653                    Err(ListenerIndexState::Unset(ZERO3)) => unreachable!(),
654                };
655
656                if let Ok(mut todo) = todo_mutex.lock() {
657                    todo.blocks.insert(index);
658                } else {
659                    // If the mutex is poisoned, don't panic but do die
660                    return false;
661                }
662            }
663            true
664        } else {
665            false
666        }
667    }
668}
669
670// -------------------------------------------------------------------------------------------------
671
672/// Block evaluation and listener which has not yet been inserted into a [`Palette`].
673/// Used by transactions.
674#[derive(Debug)]
675pub(in crate::space) struct PendingEvaluation {
676    entry: SpaceBlockData,
677    listener: Arc<BlockListener>,
678}
679
680impl PendingEvaluation {
681    pub fn new(read_ticket: ReadTicket<'_>, palette: &Palette, block: Block) -> Self {
682        let (listener, gate) = palette.listener_for_block(ListenerIndexState::Unset(ZERO3));
683        Self {
684            entry: SpaceBlockData::new(read_ticket, block, listener.clone(), gate),
685            listener,
686        }
687    }
688}
689
690/// Errors that can occur in palette-and-indices data, such as that provided to
691/// [`space::Builder::palette_and_contents()`].
692//
693// TODO: `space::Builder` doesn't actually use `Palette` directly yet; this is here because
694// we plan that it *will*, and then `Palette` will be returning some of these errors.
695#[derive(Clone, Debug, PartialEq)]
696#[allow(missing_docs)]
697#[non_exhaustive]
698pub enum PaletteError {
699    /// The given palette is larger than the maximum supported length.
700    PaletteTooLarge { len: usize },
701
702    /// One of the indices in the data was outside the bounds of the palette.
703    Index {
704        index: BlockIndex,
705        cube: math::Cube,
706        palette_len: usize,
707    },
708
709    /// The provided data did not match the bounds of the [`Space`](crate::space::Space).
710    WrongDataBounds {
711        expected: math::GridAab,
712        actual: math::GridAab,
713    },
714
715    /// The palette contained duplicate blocks.
716    ///
717    /// Note: in some cases, duplicates are permitted and this error will not be produced.
718    Duplicate {
719        index_1: BlockIndex,
720        index_2: BlockIndex,
721        block: Block,
722    },
723}
724
725impl core::error::Error for PaletteError {}
726
727impl fmt::Display for PaletteError {
728    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
729        match self {
730            PaletteError::PaletteTooLarge { len } => {
731                write!(f, "a palette of {len} blocks is too large")
732            }
733            PaletteError::Index {
734                index,
735                cube,
736                palette_len,
737            } => write!(
738                f,
739                "block index {index} for cube {cube:?} exceeds palette length {palette_len}",
740                cube = Into::<[i32; 3]>::into(*cube),
741            ),
742            PaletteError::WrongDataBounds { expected, actual } => write!(
743                f,
744                "data bounds {actual:?} is incorrect for space bounds {expected:?}",
745            ),
746            PaletteError::Duplicate {
747                index_1,
748                index_2,
749                block,
750            } => write!(
751                f,
752                "duplicate block at indices {index_1} and {index_2}: {block:?}",
753            ),
754        }
755    }
756}
757
758/// Error returned from palette operations that would expand the palette but are out of
759/// indices.
760///
761/// This is not public, because currently all public operations return either
762/// [`SetCubeError::TooManyBlocks`] or [`PaletteError::PaletteTooLarge`].
763#[derive(Copy, Clone, Debug, Eq, PartialEq)]
764pub(crate) struct TooManyBlocks;
765
766impl From<TooManyBlocks> for SetCubeError {
767    fn from(TooManyBlocks: TooManyBlocks) -> Self {
768        SetCubeError::TooManyBlocks()
769    }
770}
771
772// -------------------------------------------------------------------------------------------------
773// Palette ECS pieces
774
775#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq, bevy_ecs::schedule::SystemSet)]
776pub(crate) struct SpacePaletteUpdateSet;
777
778/// [`InfoCollector`] tag for palette evaluations.
779pub(crate) struct PaletteStatsTag;
780
781pub(super) fn add_palette_systems(world: &mut ecs::World) {
782    let mut schedules = world.resource_mut::<ecs::Schedules>();
783
784    schedules.add_systems(
785        time::schedule::Synchronize,
786        (update_palette_phase_1, update_palette_phase_2).in_set(SpacePaletteUpdateSet),
787    );
788}
789
790/// When updating spaces' palettes, this temporarily stores the new block evaluations.
791/// into the `PaletteUpdates` component.
792///
793/// It is used only between [`update_palette_phase_1`] and [`update_palette_phase_2`].
794#[derive(bevy_ecs::component::Component, Default)]
795pub(in crate::space) struct PaletteUpdates(HbHashMap<BlockIndex, EvaluatedBlock>);
796
797/// ECS system that computes but does not apply updates to [`Space`]'s `Palette`.
798///
799/// TODO: this is basically a copy of similar code for `BlockDef`
800pub(crate) fn update_palette_phase_1(
801    mut info_collector: ecs::ResMut<universe::InfoCollector<TimeStats, PaletteStatsTag>>,
802    mut spaces: ecs::Query<'_, '_, (&Palette, &mut PaletteUpdates)>,
803    data_sources: universe::QueryBlockDataSources<'_, '_>,
804) {
805    let data_sources = data_sources.get();
806    let read_ticket = ReadTicket::from_queries(&data_sources);
807
808    // TODO: parallel iter, + pipe out update info
809    // TODO: Somehow filter only to palettes with any dirty flag.
810    for (current_palette, mut next_palette) in spaces.iter_mut() {
811        debug_assert!(
812            next_palette.0.is_empty(),
813            "PaletteUpdates should have been cleared"
814        );
815
816        let mut last_start_time = time::Instant::now();
817        let mut evaluations = TimeStats::default();
818
819        let mut try_eval_again = hashbrown::HashSet::new();
820        let mut todo = current_palette.todo.lock().unwrap();
821        for block_index in todo.blocks.drain() {
822            let data: &SpaceBlockData = &current_palette.entries[usize::from(block_index)];
823
824            // TODO: We may want to have a higher-level error handling by pausing the Space
825            // and giving the user choices like reverting to save, editing to fix, or
826            // continuing with a partly broken world. Right now, we just continue with the
827            // placeholder, which may have cascading effects despite the placeholder's
828            // design to be innocuous.
829            next_palette.0.insert(
830                block_index,
831                data.block.evaluate(read_ticket).unwrap_or_else(|e| {
832                    // Trigger retrying evaluation at next step.
833                    try_eval_again.insert(block_index);
834
835                    e.to_placeholder()
836                }),
837            );
838
839            // TODO: Process side effects on individual cubes such as reevaluating the
840            // lighting influenced by the block.
841
842            evaluations.record_consecutive_interval(&mut last_start_time, time::Instant::now());
843        }
844        if !try_eval_again.is_empty() {
845            todo.blocks = try_eval_again;
846        }
847
848        info_collector.record(evaluations);
849    }
850}
851
852/// ECS system that moves new block evaluations from `PaletteUpdates` to [`Space`]'s
853/// [`Palette`].
854///
855/// This system being separate resolves the borrow conflict between writing to a [`Space`]
856/// and block evaluation (which may read from any [`Space`]).
857pub(crate) fn update_palette_phase_2(
858    mut spaces: ecs::Query<
859        (&mut Palette, &mut PaletteUpdates, &super::Notifiers),
860        ecs::Changed<PaletteUpdates>,
861    >,
862) {
863    spaces
864        .par_iter_mut()
865        .for_each(|(mut current_palette, mut next_palette, notifiers)| {
866            let change_buffer: &mut ChangeBuffer<'_> = &mut notifiers.change_notifier.buffer();
867
868            // By bypassing change detection, we avoid detecting this consumption of the change.
869            // (This means that change detection no longer strictly functions as change detection,
870            // but that is okay because `PaletteUpdates` is *only* for palette updates.)
871            for (block_index, evaluation) in next_palette.bypass_change_detection().0.drain() {
872                current_palette.entries[usize::from(block_index)].evaluated = evaluation;
873                change_buffer.push(SpaceChange::BlockEvaluation(block_index));
874            }
875        });
876}
877
878// -------------------------------------------------------------------------------------------------
879
880#[cfg(test)]
881mod tests {
882    use super::*;
883    use crate::content::make_some_blocks;
884    use crate::math::{GridAab, Rgba, Vol};
885    use crate::space::Space;
886    use pretty_assertions::assert_eq;
887
888    #[test]
889    fn clone_palette() {
890        let blocks = make_some_blocks::<2>();
891        // Use a Space to create our starting palette
892        let bounds = GridAab::from_lower_size([0, 0, 0], [3, 1, 1]);
893        let space = Space::builder(bounds)
894            .palette_and_contents(
895                blocks.clone(),
896                Vol::from_elements(bounds, [0, 1, 0]).unwrap(),
897                None,
898            )
899            .unwrap()
900            .build();
901
902        let cloned = space.palette.clone();
903
904        // The clone should be consistent internally and with the space data.
905        cloned.consistency_check(space.contents.as_linear());
906
907        let extract = |p: &Palette| {
908            p.entries().iter().map(|e| (e.block.clone(), e.count)).collect::<Vec<_>>()
909        };
910        assert_eq!(extract(&cloned), extract(&space.palette));
911
912        // TODO: also check evaluation and block change tracking
913    }
914
915    #[test]
916    fn with_maximum_number_of_entries() {
917        let expected_len = usize::from(BlockIndex::MAX) + 1;
918        let mut blocks_iter = (0..=BlockIndex::MAX).map(|i| {
919            // These blocks must all be distinct.
920            Block::builder()
921                .color(Rgba::WHITE)
922                .display_name(arcstr::format!("#{i}"))
923                .build()
924        });
925
926        let (palette, remap) = Palette::from_blocks(ReadTicket::stub(), &mut blocks_iter).unwrap();
927
928        assert_eq!(palette.entries().len(), expected_len);
929        assert_eq!(remap, hashbrown::HashMap::default());
930    }
931
932    // TODO: test Palette::from_blocks(), especially around remapping.
933    // It has tests via `space::Builder`, but not much.
934}
all_is_cubes/space/palette.rs

all_is_cubes/space/
palette.rs
