Skip to main content

decl_lang/semantics/
map_entries.rs

1//! Ordered map entries with optional shared, immutable key shapes.
2//!
3//! Each map owns its values. Sharing a shape never shares mutable values or
4//! introduces an additional owner of a runtime value. Structural mutations
5//! promote a shared map to an ordinary ordered map; replacing an existing value
6//! does not copy keys or affect another map.
7
8use super::{OrderedMap, Value};
9use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet, FxHasher};
10use std::hash::{BuildHasher, Hash, Hasher};
11use std::iter::FusedIterator;
12use std::rc::{Rc, Weak};
13
14const MAX_SHAPE_KEYS: usize = 8;
15const MAX_POOL_ENTRIES: usize = 4096;
16const SCANNED_KEYS: usize = 16;
17
18/// The keys an entry list under construction already holds (E5004). A short
19/// list is scanned. From `SCANNED_KEYS` entries on the keys' hashes are kept
20/// and only a hash seen before is confirmed by a scan, so a long comprehension
21/// checks each key in constant time, not in the length of the list.
22#[derive(Default)]
23pub(crate) struct KeysSeen {
24    hashes: Option<FxHashSet<u64>>,
25}
26
27impl KeysSeen {
28    /// Whether `key` is new among `entries`. The caller pushes it next or
29    /// abandons the list: every later call sees the entries this one admitted.
30    pub(crate) fn admits(&mut self, entries: &[(String, Value)], key: &str) -> bool {
31        if entries.len() < SCANNED_KEYS {
32            return !entries.iter().any(|(k, _)| k == key);
33        }
34        let hash = |k: &str| FxBuildHasher.hash_one(k);
35        let hashes = self
36            .hashes
37            .get_or_insert_with(|| entries.iter().map(|(k, _)| hash(k)).collect());
38        hashes.insert(hash(key)) || !entries.iter().any(|(k, _)| k == key)
39    }
40}
41
42struct KeyShape {
43    keys: OrderedMap<()>,
44}
45
46#[derive(Clone)]
47enum Storage {
48    // Keep empty construction and temporary replacement allocation-free. In
49    // particular, clearing Shared must detach its values before their drops.
50    Empty,
51    // The ordinary table header must not determine every Shared map's size.
52    Owned(Box<OrderedMap<Value>>),
53    // Only engine construction starts here. Keep values on the heap and move
54    // them into their final storage without constructing a temporary key table.
55    Small(Vec<(String, Value)>),
56    Shared {
57        shape: Rc<KeyShape>,
58        values: Vec<Value>,
59    },
60}
61
62/// Insertion-ordered map entries with independent values and optional shared
63/// keys. Duplicate insertion replaces the value at the original key position.
64///
65/// Cloning clones each value exactly once. When keys are shared, cloning retains
66/// their immutable shape instead of cloning the key strings. Use
67/// [`Self::as_ordered_mut`] for operations specific to an ordinary ordered map.
68#[derive(Clone)]
69pub struct MapEntries {
70    storage: Storage,
71}
72
73impl Default for MapEntries {
74    fn default() -> Self {
75        Self::new()
76    }
77}
78
79impl MapEntries {
80    /// Construct an empty, unshared map without allocating entry storage.
81    pub fn new() -> Self {
82        Self {
83            storage: Storage::Empty,
84        }
85    }
86
87    /// Start an engine-produced map without allocating an ordinary key table.
88    /// The ninth distinct key promotes to ordinary storage; duplicate keys
89    /// replace their value at the original position before either transition.
90    pub(crate) fn building() -> Self {
91        Self {
92            storage: Storage::Small(Vec::new()),
93        }
94    }
95
96    /// Construct an unshared map with room for at least `capacity` entries.
97    pub fn with_capacity(capacity: usize) -> Self {
98        Self::with_capacity_and_hasher(capacity, FxBuildHasher)
99    }
100
101    /// Construct an unshared map with the ordinary ordered map's hasher.
102    pub fn with_capacity_and_hasher(capacity: usize, hasher: FxBuildHasher) -> Self {
103        Self::from(OrderedMap::with_capacity_and_hasher(capacity, hasher))
104    }
105
106    /// The number of entries.
107    pub fn len(&self) -> usize {
108        match &self.storage {
109            Storage::Empty => 0,
110            Storage::Owned(entries) => entries.len(),
111            Storage::Small(entries) => entries.len(),
112            Storage::Shared { values, .. } => values.len(),
113        }
114    }
115
116    /// Whether there are no entries.
117    pub fn is_empty(&self) -> bool {
118        self.len() == 0
119    }
120
121    /// The capacity of this map's value storage. For shared maps this is the
122    /// value vector's capacity, not the capacity of the shared key table.
123    pub fn capacity(&self) -> usize {
124        match &self.storage {
125            Storage::Empty => 0,
126            Storage::Owned(entries) => entries.capacity(),
127            Storage::Small(entries) => entries.capacity(),
128            Storage::Shared { values, .. } => values.capacity(),
129        }
130    }
131
132    /// Whether this map currently uses an immutable shared key shape.
133    pub fn is_shared(&self) -> bool {
134        matches!(self.storage, Storage::Shared { .. })
135    }
136
137    /// Borrow the value at `key`.
138    pub fn get(&self, key: &str) -> Option<&Value> {
139        match &self.storage {
140            Storage::Empty => None,
141            Storage::Owned(entries) => entries.get(key),
142            Storage::Small(entries) => entries.iter().find(|(k, _)| k == key).map(|(_, v)| v),
143            Storage::Shared { shape, values } => {
144                shape.keys.get_index_of(key).map(|index| &values[index])
145            }
146        }
147    }
148
149    /// Whether the key is present.
150    pub fn contains_key(&self, key: &str) -> bool {
151        self.get_index_of(key).is_some()
152    }
153
154    /// The insertion-order index of a key.
155    pub fn get_index_of(&self, key: &str) -> Option<usize> {
156        match &self.storage {
157            Storage::Empty => None,
158            Storage::Owned(entries) => entries.get_index_of(key),
159            Storage::Small(entries) => entries.iter().position(|(k, _)| k == key),
160            Storage::Shared { shape, .. } => shape.keys.get_index_of(key),
161        }
162    }
163
164    /// Borrow an entry by insertion-order index.
165    pub fn get_index(&self, index: usize) -> Option<(&String, &Value)> {
166        match &self.storage {
167            Storage::Empty => None,
168            Storage::Owned(entries) => entries.get_index(index),
169            Storage::Small(entries) => entries.get(index).map(|(k, v)| (k, v)),
170            Storage::Shared { shape, values } => shape
171                .keys
172                .get_index(index)
173                .map(|(key, ())| (key, &values[index])),
174        }
175    }
176
177    /// Mutably borrow one value without changing or copying its key shape.
178    pub fn get_mut(&mut self, key: &str) -> Option<&mut Value> {
179        match &mut self.storage {
180            Storage::Empty => None,
181            Storage::Owned(entries) => entries.get_mut(key),
182            Storage::Small(entries) => entries
183                .iter_mut()
184                .find(|(k, _)| k.as_str() == key)
185                .map(|(_, v)| v),
186            Storage::Shared { shape, values } => {
187                let index = shape.keys.get_index_of(key)?;
188                Some(&mut values[index])
189            }
190        }
191    }
192
193    /// Borrow a key and mutably borrow its value by insertion-order index.
194    pub fn get_index_mut(&mut self, index: usize) -> Option<(&String, &mut Value)> {
195        match &mut self.storage {
196            Storage::Empty => None,
197            Storage::Owned(entries) => entries.get_index_mut(index),
198            Storage::Small(entries) => entries.get_mut(index).map(|(k, v)| (&*k, v)),
199            Storage::Shared { shape, values } => {
200                let (key, ()) = shape.keys.get_index(index)?;
201                Some((key, &mut values[index]))
202            }
203        }
204    }
205
206    /// Borrow entries in insertion order without cloning keys or values.
207    pub fn iter(&self) -> MapEntriesIter<'_> {
208        MapEntriesIter {
209            inner: match &self.storage {
210                Storage::Empty => IterStorage::Empty,
211                Storage::Owned(entries) => IterStorage::Owned(entries.iter()),
212                Storage::Small(entries) => IterStorage::Small(entries.iter()),
213                Storage::Shared { shape, values } => {
214                    IterStorage::Shared(shape.keys.keys().zip(values.iter()))
215                }
216            },
217        }
218    }
219
220    /// Borrow keys in insertion order.
221    pub fn keys(&self) -> MapEntriesKeys<'_> {
222        MapEntriesKeys { inner: self.iter() }
223    }
224
225    /// Borrow values in insertion order.
226    pub fn values(&self) -> MapEntriesValues<'_> {
227        MapEntriesValues { inner: self.iter() }
228    }
229
230    /// Borrow keys and mutably borrow values in insertion order. Keys remain
231    /// immutable and each mutable value belongs to this map alone.
232    pub fn iter_mut(&mut self) -> MapEntriesIterMut<'_> {
233        MapEntriesIterMut {
234            inner: match &mut self.storage {
235                Storage::Empty => IterMutStorage::Empty,
236                Storage::Owned(entries) => IterMutStorage::Owned(entries.iter_mut()),
237                Storage::Small(entries) => IterMutStorage::Small(entries.iter_mut()),
238                Storage::Shared { shape, values } => {
239                    IterMutStorage::Shared(shape.keys.keys().zip(values.iter_mut()))
240                }
241            },
242        }
243    }
244
245    /// Mutably borrow values in insertion order without copying keys.
246    pub fn values_mut(&mut self) -> MapEntriesValuesMut<'_> {
247        MapEntriesValuesMut {
248            inner: self.iter_mut(),
249        }
250    }
251
252    /// Insert or replace an entry. Replacing an existing key keeps its original
253    /// position and returns its previous value without promoting shared keys.
254    /// Adding a key promotes shared storage before insertion.
255    pub fn insert(&mut self, key: String, value: Value) -> Option<Value> {
256        match &mut self.storage {
257            Storage::Empty => {}
258            Storage::Owned(entries) => return entries.insert(key, value),
259            Storage::Small(entries) => {
260                if let Some((_, old)) = entries.iter_mut().find(|(k, _)| k.as_str() == key.as_str())
261                {
262                    return Some(std::mem::replace(old, value));
263                }
264                if entries.len() < MAX_SHAPE_KEYS {
265                    entries.push((key, value));
266                    return None;
267                }
268            }
269            Storage::Shared { shape, values } => {
270                if let Some(index) = shape.keys.get_index_of(key.as_str()) {
271                    return Some(std::mem::replace(&mut values[index], value));
272                }
273            }
274        }
275        self.as_ordered_mut().insert(key, value)
276    }
277
278    /// Remove a key, shifting later entries left while preserving their order.
279    /// An absent key leaves the representation unchanged.
280    pub fn shift_remove(&mut self, key: &str) -> Option<Value> {
281        if !self.contains_key(key) {
282            return None;
283        }
284        self.as_ordered_mut().shift_remove(key)
285    }
286
287    /// Remove a key, moving the last entry into its position. An absent key
288    /// leaves the representation unchanged.
289    pub fn swap_remove(&mut self, key: &str) -> Option<Value> {
290        if !self.contains_key(key) {
291            return None;
292        }
293        self.as_ordered_mut().swap_remove(key)
294    }
295
296    /// Remove all values in insertion order. Shared storage becomes an empty
297    /// ordinary map without first allocating or cloning a key table.
298    pub fn clear(&mut self) {
299        match &mut self.storage {
300            Storage::Empty => {}
301            Storage::Owned(entries) => entries.clear(),
302            Storage::Small(entries) => entries.clear(),
303            Storage::Shared { .. } => {
304                let old = std::mem::replace(&mut self.storage, Storage::Empty);
305                drop(old);
306            }
307        }
308    }
309
310    /// Obtain ordinary mutable map storage. Shared keys are cloned and values
311    /// are moved exactly once; other maps retain their keys and values.
312    /// Subsequent ordered-map operations follow the ordinary map API.
313    pub fn as_ordered_mut(&mut self) -> &mut OrderedMap<Value> {
314        if !matches!(self.storage, Storage::Owned(_)) {
315            let old = std::mem::replace(&mut self.storage, Storage::Empty);
316            self.storage = Storage::Owned(Box::new(Self { storage: old }.into_ordered()));
317        }
318        match &mut self.storage {
319            Storage::Owned(entries) => entries,
320            Storage::Empty | Storage::Small(_) | Storage::Shared { .. } => {
321                unreachable!("entries were promoted")
322            }
323        }
324    }
325
326    /// Consume the entries as an ordinary ordered map. Shared keys are cloned;
327    /// values are moved, preserving their order and identity.
328    pub fn into_ordered(self) -> OrderedMap<Value> {
329        match self.storage {
330            Storage::Empty => OrderedMap::default(),
331            Storage::Owned(entries) => *entries,
332            Storage::Small(entries) => entries.into_iter().collect(),
333            Storage::Shared { shape, values } => {
334                let mut entries = OrderedMap::with_capacity_and_hasher(values.len(), FxBuildHasher);
335                for (key, value) in shape.keys.keys().zip(values) {
336                    entries.insert(key.clone(), value);
337                }
338                entries
339            }
340        }
341    }
342
343    /// Reconstruct entries with new, independently owned values in the same
344    /// order. Shared storage retains exactly the same immutable key shape.
345    ///
346    /// The caller must register any recursive destination before producing its
347    /// values. This method does not perform recursion or resolve cycles.
348    ///
349    /// # Panics
350    ///
351    /// Panics if `values` does not contain exactly one value per source key.
352    pub(crate) fn with_values(&self, values: Vec<Value>) -> Self {
353        assert_eq!(
354            values.len(),
355            self.len(),
356            "map reconstruction changes key count"
357        );
358        match &self.storage {
359            Storage::Empty => Self::new(),
360            Storage::Owned(entries) => entries.keys().cloned().zip(values).collect(),
361            Storage::Small(entries) => Self {
362                storage: Storage::Small(
363                    entries.iter().map(|(k, _)| k.clone()).zip(values).collect(),
364                ),
365            },
366            Storage::Shared { shape, .. } => Self {
367                storage: Storage::Shared {
368                    shape: shape.clone(),
369                    values,
370                },
371            },
372        }
373    }
374}
375
376impl From<OrderedMap<Value>> for MapEntries {
377    fn from(entries: OrderedMap<Value>) -> Self {
378        if entries.capacity() == 0 {
379            Self::new()
380        } else {
381            Self {
382                storage: Storage::Owned(Box::new(entries)),
383            }
384        }
385    }
386}
387
388impl From<MapEntries> for OrderedMap<Value> {
389    fn from(entries: MapEntries) -> Self {
390        entries.into_ordered()
391    }
392}
393
394impl FromIterator<(String, Value)> for MapEntries {
395    fn from_iter<T: IntoIterator<Item = (String, Value)>>(iter: T) -> Self {
396        Self::from(OrderedMap::from_iter(iter))
397    }
398}
399
400impl Extend<(String, Value)> for MapEntries {
401    fn extend<T: IntoIterator<Item = (String, Value)>>(&mut self, iter: T) {
402        for (key, value) in iter {
403            self.insert(key, value);
404        }
405    }
406}
407
408enum IterStorage<'a> {
409    Empty,
410    Owned(indexmap::map::Iter<'a, String, Value>),
411    Small(std::slice::Iter<'a, (String, Value)>),
412    Shared(std::iter::Zip<indexmap::map::Keys<'a, String, ()>, std::slice::Iter<'a, Value>>),
413}
414
415/// An iterator over borrowed map entries in insertion order.
416pub struct MapEntriesIter<'a> {
417    inner: IterStorage<'a>,
418}
419
420impl<'a> Iterator for MapEntriesIter<'a> {
421    type Item = (&'a String, &'a Value);
422
423    fn next(&mut self) -> Option<Self::Item> {
424        match &mut self.inner {
425            IterStorage::Empty => None,
426            IterStorage::Owned(iter) => iter.next(),
427            IterStorage::Small(iter) => iter.next().map(|(k, v)| (k, v)),
428            IterStorage::Shared(iter) => iter.next(),
429        }
430    }
431
432    fn size_hint(&self) -> (usize, Option<usize>) {
433        let len = self.len();
434        (len, Some(len))
435    }
436}
437
438impl DoubleEndedIterator for MapEntriesIter<'_> {
439    fn next_back(&mut self) -> Option<Self::Item> {
440        match &mut self.inner {
441            IterStorage::Empty => None,
442            IterStorage::Owned(iter) => iter.next_back(),
443            IterStorage::Small(iter) => iter.next_back().map(|(k, v)| (k, v)),
444            IterStorage::Shared(iter) => iter.next_back(),
445        }
446    }
447}
448
449impl ExactSizeIterator for MapEntriesIter<'_> {
450    fn len(&self) -> usize {
451        match &self.inner {
452            IterStorage::Empty => 0,
453            IterStorage::Owned(iter) => iter.len(),
454            IterStorage::Small(iter) => iter.len(),
455            IterStorage::Shared(iter) => iter.len(),
456        }
457    }
458}
459
460impl FusedIterator for MapEntriesIter<'_> {}
461
462/// An iterator over borrowed map keys in insertion order.
463pub struct MapEntriesKeys<'a> {
464    inner: MapEntriesIter<'a>,
465}
466
467impl<'a> Iterator for MapEntriesKeys<'a> {
468    type Item = &'a String;
469
470    fn next(&mut self) -> Option<Self::Item> {
471        self.inner.next().map(|(key, _)| key)
472    }
473
474    fn size_hint(&self) -> (usize, Option<usize>) {
475        self.inner.size_hint()
476    }
477}
478
479impl DoubleEndedIterator for MapEntriesKeys<'_> {
480    fn next_back(&mut self) -> Option<Self::Item> {
481        self.inner.next_back().map(|(key, _)| key)
482    }
483}
484
485impl ExactSizeIterator for MapEntriesKeys<'_> {
486    fn len(&self) -> usize {
487        self.inner.len()
488    }
489}
490
491impl FusedIterator for MapEntriesKeys<'_> {}
492
493/// An iterator over borrowed map values in insertion order.
494pub struct MapEntriesValues<'a> {
495    inner: MapEntriesIter<'a>,
496}
497
498impl<'a> Iterator for MapEntriesValues<'a> {
499    type Item = &'a Value;
500
501    fn next(&mut self) -> Option<Self::Item> {
502        self.inner.next().map(|(_, value)| value)
503    }
504
505    fn size_hint(&self) -> (usize, Option<usize>) {
506        self.inner.size_hint()
507    }
508}
509
510impl DoubleEndedIterator for MapEntriesValues<'_> {
511    fn next_back(&mut self) -> Option<Self::Item> {
512        self.inner.next_back().map(|(_, value)| value)
513    }
514}
515
516impl ExactSizeIterator for MapEntriesValues<'_> {
517    fn len(&self) -> usize {
518        self.inner.len()
519    }
520}
521
522impl FusedIterator for MapEntriesValues<'_> {}
523
524enum IterMutStorage<'a> {
525    Empty,
526    Owned(indexmap::map::IterMut<'a, String, Value>),
527    Small(std::slice::IterMut<'a, (String, Value)>),
528    Shared(std::iter::Zip<indexmap::map::Keys<'a, String, ()>, std::slice::IterMut<'a, Value>>),
529}
530
531/// An iterator over borrowed keys and independently mutable map values.
532pub struct MapEntriesIterMut<'a> {
533    inner: IterMutStorage<'a>,
534}
535
536impl<'a> Iterator for MapEntriesIterMut<'a> {
537    type Item = (&'a String, &'a mut Value);
538
539    fn next(&mut self) -> Option<Self::Item> {
540        match &mut self.inner {
541            IterMutStorage::Empty => None,
542            IterMutStorage::Owned(iter) => iter.next(),
543            IterMutStorage::Small(iter) => iter.next().map(|(k, v)| (&*k, v)),
544            IterMutStorage::Shared(iter) => iter.next(),
545        }
546    }
547
548    fn size_hint(&self) -> (usize, Option<usize>) {
549        let len = self.len();
550        (len, Some(len))
551    }
552}
553
554impl DoubleEndedIterator for MapEntriesIterMut<'_> {
555    fn next_back(&mut self) -> Option<Self::Item> {
556        match &mut self.inner {
557            IterMutStorage::Empty => None,
558            IterMutStorage::Owned(iter) => iter.next_back(),
559            IterMutStorage::Small(iter) => iter.next_back().map(|(k, v)| (&*k, v)),
560            IterMutStorage::Shared(iter) => iter.next_back(),
561        }
562    }
563}
564
565impl ExactSizeIterator for MapEntriesIterMut<'_> {
566    fn len(&self) -> usize {
567        match &self.inner {
568            IterMutStorage::Empty => 0,
569            IterMutStorage::Owned(iter) => iter.len(),
570            IterMutStorage::Small(iter) => iter.len(),
571            IterMutStorage::Shared(iter) => iter.len(),
572        }
573    }
574}
575
576impl FusedIterator for MapEntriesIterMut<'_> {}
577
578/// An iterator over independently mutable map values in insertion order.
579pub struct MapEntriesValuesMut<'a> {
580    inner: MapEntriesIterMut<'a>,
581}
582
583impl<'a> Iterator for MapEntriesValuesMut<'a> {
584    type Item = &'a mut Value;
585
586    fn next(&mut self) -> Option<Self::Item> {
587        self.inner.next().map(|(_, value)| value)
588    }
589
590    fn size_hint(&self) -> (usize, Option<usize>) {
591        self.inner.size_hint()
592    }
593}
594
595impl DoubleEndedIterator for MapEntriesValuesMut<'_> {
596    fn next_back(&mut self) -> Option<Self::Item> {
597        self.inner.next_back().map(|(_, value)| value)
598    }
599}
600
601impl ExactSizeIterator for MapEntriesValuesMut<'_> {
602    fn len(&self) -> usize {
603        self.inner.len()
604    }
605}
606
607impl FusedIterator for MapEntriesValuesMut<'_> {}
608
609impl<'a> IntoIterator for &'a MapEntries {
610    type Item = (&'a String, &'a Value);
611    type IntoIter = MapEntriesIter<'a>;
612
613    fn into_iter(self) -> Self::IntoIter {
614        self.iter()
615    }
616}
617
618impl<'a> IntoIterator for &'a mut MapEntries {
619    type Item = (&'a String, &'a mut Value);
620    type IntoIter = MapEntriesIterMut<'a>;
621
622    fn into_iter(self) -> Self::IntoIter {
623        self.iter_mut()
624    }
625}
626
627/// An owning iterator over map entries. Shared keys become owned strings when
628/// this iterator is constructed; values are moved without cloning.
629pub struct MapEntriesIntoIter {
630    inner: IntoIterStorage,
631}
632
633enum IntoIterStorage {
634    Empty,
635    Owned(indexmap::map::IntoIter<String, Value>),
636    Small(std::vec::IntoIter<(String, Value)>),
637}
638
639impl Iterator for MapEntriesIntoIter {
640    type Item = (String, Value);
641
642    fn next(&mut self) -> Option<Self::Item> {
643        match &mut self.inner {
644            IntoIterStorage::Empty => None,
645            IntoIterStorage::Owned(iter) => iter.next(),
646            IntoIterStorage::Small(iter) => iter.next(),
647        }
648    }
649
650    fn size_hint(&self) -> (usize, Option<usize>) {
651        let len = self.len();
652        (len, Some(len))
653    }
654}
655
656impl DoubleEndedIterator for MapEntriesIntoIter {
657    fn next_back(&mut self) -> Option<Self::Item> {
658        match &mut self.inner {
659            IntoIterStorage::Empty => None,
660            IntoIterStorage::Owned(iter) => iter.next_back(),
661            IntoIterStorage::Small(iter) => iter.next_back(),
662        }
663    }
664}
665
666impl ExactSizeIterator for MapEntriesIntoIter {
667    fn len(&self) -> usize {
668        match &self.inner {
669            IntoIterStorage::Empty => 0,
670            IntoIterStorage::Owned(iter) => iter.len(),
671            IntoIterStorage::Small(iter) => iter.len(),
672        }
673    }
674}
675
676impl FusedIterator for MapEntriesIntoIter {}
677
678impl IntoIterator for MapEntries {
679    type Item = (String, Value);
680    type IntoIter = MapEntriesIntoIter;
681
682    fn into_iter(self) -> Self::IntoIter {
683        MapEntriesIntoIter {
684            inner: match self.storage {
685                Storage::Empty => IntoIterStorage::Empty,
686                Storage::Small(entries) => IntoIterStorage::Small(entries.into_iter()),
687                other => IntoIterStorage::Owned(Self { storage: other }.into_ordered().into_iter()),
688            },
689        }
690    }
691}
692
693/// A bounded interner holding only weak references to immutable key shapes.
694/// Fingerprints are a lookup hint; complete ordered key equality is always
695/// checked before sharing. Neither the pool nor a shape owns runtime values.
696#[derive(Default)]
697pub(crate) struct MapShapePool {
698    entries: FxHashMap<u64, Weak<KeyShape>>,
699}
700
701impl MapShapePool {
702    /// Share the keys of a completed map containing one through eight entries.
703    /// Empty and wider maps remain ordinary maps. Returns whether the resulting
704    /// map is shared, including maps that were already shared on entry.
705    pub(crate) fn seal(&mut self, entries: &mut MapEntries) -> bool {
706        if entries.is_shared() {
707            return true;
708        }
709        if entries.is_empty() {
710            // A successful empty construction publishes the same ordinary
711            // empty representation as before, without allocating either table.
712            if matches!(entries.storage, Storage::Small(_)) {
713                entries.storage = Storage::Empty;
714            }
715            return false;
716        }
717        if !(1..=MAX_SHAPE_KEYS).contains(&entries.len()) {
718            return false;
719        }
720        let mut hash = FxHasher::default();
721        entries.len().hash(&mut hash);
722        for key in entries.keys() {
723            key.len().hash(&mut hash);
724            key.hash(&mut hash);
725        }
726        self.seal_with_fingerprint(entries, hash.finish())
727    }
728
729    // Kept separate so native tests can inject a collision without depending
730    // on the hasher or attempting to discover an actual fingerprint collision.
731    fn seal_with_fingerprint(&mut self, entries: &mut MapEntries, fingerprint: u64) -> bool {
732        if entries.is_shared() {
733            return true;
734        }
735        if !(1..=MAX_SHAPE_KEYS).contains(&entries.len()) {
736            return false;
737        }
738        let existing = self
739            .entries
740            .get(&fingerprint)
741            .and_then(Weak::upgrade)
742            .filter(|shape| shape.keys.keys().eq(entries.keys()));
743        let old = std::mem::replace(&mut entries.storage, Storage::Empty);
744        let owned = MapEntries { storage: old }.into_iter();
745        let mut values = Vec::with_capacity(owned.len());
746        let shape = if let Some(shape) = existing {
747            for (_, value) in owned {
748                values.push(value);
749            }
750            shape
751        } else {
752            let mut keys = OrderedMap::with_capacity_and_hasher(owned.len(), FxBuildHasher);
753            for (key, value) in owned {
754                keys.insert(key, ());
755                values.push(value);
756            }
757            let shape = Rc::new(KeyShape { keys });
758            if self.entries.len() >= MAX_POOL_ENTRIES && !self.entries.contains_key(&fingerprint) {
759                // Clearing only weak references cannot destroy any live shape
760                // or value. It bounds stale fingerprints without a full scan
761                // on every insertion or a separately allocated collision list.
762                self.entries.clear();
763            }
764            self.entries.insert(fingerprint, Rc::downgrade(&shape));
765            shape
766        };
767        entries.storage = Storage::Shared { shape, values };
768        true
769    }
770}
771
772#[cfg(test)]
773#[path = "../../tests/private/map_entries_test.rs"]
774mod tests;