1use 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#[derive(Default)]
23pub(crate) struct KeysSeen {
24 hashes: Option<FxHashSet<u64>>,
25}
26
27impl KeysSeen {
28 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 Empty,
51 Owned(Box<OrderedMap<Value>>),
53 Small(Vec<(String, Value)>),
56 Shared {
57 shape: Rc<KeyShape>,
58 values: Vec<Value>,
59 },
60}
61
62#[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 pub fn new() -> Self {
82 Self {
83 storage: Storage::Empty,
84 }
85 }
86
87 pub(crate) fn building() -> Self {
91 Self {
92 storage: Storage::Small(Vec::new()),
93 }
94 }
95
96 pub fn with_capacity(capacity: usize) -> Self {
98 Self::with_capacity_and_hasher(capacity, FxBuildHasher)
99 }
100
101 pub fn with_capacity_and_hasher(capacity: usize, hasher: FxBuildHasher) -> Self {
103 Self::from(OrderedMap::with_capacity_and_hasher(capacity, hasher))
104 }
105
106 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 pub fn is_empty(&self) -> bool {
118 self.len() == 0
119 }
120
121 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 pub fn is_shared(&self) -> bool {
134 matches!(self.storage, Storage::Shared { .. })
135 }
136
137 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 pub fn contains_key(&self, key: &str) -> bool {
151 self.get_index_of(key).is_some()
152 }
153
154 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 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 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 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 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 pub fn keys(&self) -> MapEntriesKeys<'_> {
222 MapEntriesKeys { inner: self.iter() }
223 }
224
225 pub fn values(&self) -> MapEntriesValues<'_> {
227 MapEntriesValues { inner: self.iter() }
228 }
229
230 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 pub fn values_mut(&mut self) -> MapEntriesValuesMut<'_> {
247 MapEntriesValuesMut {
248 inner: self.iter_mut(),
249 }
250 }
251
252 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 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 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 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 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 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 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
415pub 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
462pub 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
493pub 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
531pub 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
578pub 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
627pub 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#[derive(Default)]
697pub(crate) struct MapShapePool {
698 entries: FxHashMap<u64, Weak<KeyShape>>,
699}
700
701impl MapShapePool {
702 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 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 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 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;