1use core::fmt::{Debug, Formatter};
2
3use bevy_platform::collections::HashTable;
4use bevy_reflect_derive::impl_type_path;
5
6use crate::{
7 generics::impl_generic_info_methods, type_info::impl_type_methods, ApplyError, Generics,
8 MaybeTyped, PartialReflect, Reflect, ReflectKind, ReflectMut, ReflectOwned, ReflectRef, Type,
9 TypeInfo, TypePath,
10};
11use alloc::{boxed::Box, format, vec::Vec};
12
13pub trait Map: PartialReflect {
49 fn get(&self, key: &dyn PartialReflect) -> Option<&dyn PartialReflect>;
53
54 fn get_mut(&mut self, key: &dyn PartialReflect) -> Option<&mut dyn PartialReflect>;
58
59 fn get_at(&self, index: usize) -> Option<(&dyn PartialReflect, &dyn PartialReflect)>;
61
62 fn get_at_mut(
64 &mut self,
65 index: usize,
66 ) -> Option<(&dyn PartialReflect, &mut dyn PartialReflect)>;
67
68 fn len(&self) -> usize;
70
71 fn is_empty(&self) -> bool {
73 self.len() == 0
74 }
75
76 fn iter(&self) -> MapIter;
78
79 fn drain(&mut self) -> Vec<(Box<dyn PartialReflect>, Box<dyn PartialReflect>)>;
83
84 #[deprecated(since = "0.16.0", note = "use `to_dynamic_map` instead")]
86 fn clone_dynamic(&self) -> DynamicMap {
87 self.to_dynamic_map()
88 }
89
90 fn to_dynamic_map(&self) -> DynamicMap {
92 let mut map = DynamicMap::default();
93 map.set_represented_type(self.get_represented_type_info());
94 for (key, value) in self.iter() {
95 map.insert_boxed(key.to_dynamic(), value.to_dynamic());
96 }
97 map
98 }
99
100 fn insert_boxed(
105 &mut self,
106 key: Box<dyn PartialReflect>,
107 value: Box<dyn PartialReflect>,
108 ) -> Option<Box<dyn PartialReflect>>;
109
110 fn remove(&mut self, key: &dyn PartialReflect) -> Option<Box<dyn PartialReflect>>;
115
116 fn get_represented_map_info(&self) -> Option<&'static MapInfo> {
118 self.get_represented_type_info()?.as_map().ok()
119 }
120}
121
122#[derive(Clone, Debug)]
124pub struct MapInfo {
125 ty: Type,
126 generics: Generics,
127 key_info: fn() -> Option<&'static TypeInfo>,
128 key_ty: Type,
129 value_info: fn() -> Option<&'static TypeInfo>,
130 value_ty: Type,
131 #[cfg(feature = "documentation")]
132 docs: Option<&'static str>,
133}
134
135impl MapInfo {
136 pub fn new<
138 TMap: Map + TypePath,
139 TKey: Reflect + MaybeTyped + TypePath,
140 TValue: Reflect + MaybeTyped + TypePath,
141 >() -> Self {
142 Self {
143 ty: Type::of::<TMap>(),
144 generics: Generics::new(),
145 key_info: TKey::maybe_type_info,
146 key_ty: Type::of::<TKey>(),
147 value_info: TValue::maybe_type_info,
148 value_ty: Type::of::<TValue>(),
149 #[cfg(feature = "documentation")]
150 docs: None,
151 }
152 }
153
154 #[cfg(feature = "documentation")]
156 pub fn with_docs(self, docs: Option<&'static str>) -> Self {
157 Self { docs, ..self }
158 }
159
160 impl_type_methods!(ty);
161
162 pub fn key_info(&self) -> Option<&'static TypeInfo> {
167 (self.key_info)()
168 }
169
170 pub fn key_ty(&self) -> Type {
174 self.key_ty
175 }
176
177 pub fn value_info(&self) -> Option<&'static TypeInfo> {
182 (self.value_info)()
183 }
184
185 pub fn value_ty(&self) -> Type {
189 self.value_ty
190 }
191
192 #[cfg(feature = "documentation")]
194 pub fn docs(&self) -> Option<&'static str> {
195 self.docs
196 }
197
198 impl_generic_info_methods!(generics);
199}
200
201#[macro_export]
202macro_rules! hash_error {
203 ( $key:expr ) => {{
204 let type_path = (*$key).reflect_type_path();
205 if !$key.is_dynamic() {
206 format!(
207 "the given key of type `{}` does not support hashing",
208 type_path
209 )
210 } else {
211 match (*$key).get_represented_type_info() {
212 None => format!("the dynamic type `{}` does not support hashing", type_path),
214 Some(s) => format!(
216 "the dynamic type `{}` (representing `{}`) does not support hashing",
217 type_path,
218 s.type_path()
219 ),
220 }
221 }
222 }}
223}
224
225#[derive(Default)]
227pub struct DynamicMap {
228 represented_type: Option<&'static TypeInfo>,
229 values: Vec<(Box<dyn PartialReflect>, Box<dyn PartialReflect>)>,
230 indices: HashTable<usize>,
231}
232
233impl DynamicMap {
234 pub fn set_represented_type(&mut self, represented_type: Option<&'static TypeInfo>) {
242 if let Some(represented_type) = represented_type {
243 assert!(
244 matches!(represented_type, TypeInfo::Map(_)),
245 "expected TypeInfo::Map but received: {:?}",
246 represented_type
247 );
248 }
249
250 self.represented_type = represented_type;
251 }
252
253 pub fn insert<K: PartialReflect, V: PartialReflect>(&mut self, key: K, value: V) {
255 self.insert_boxed(Box::new(key), Box::new(value));
256 }
257
258 fn internal_hash(value: &dyn PartialReflect) -> u64 {
259 value.reflect_hash().expect(&hash_error!(value))
260 }
261
262 fn internal_eq<'a>(
263 value: &'a dyn PartialReflect,
264 values: &'a [(Box<dyn PartialReflect>, Box<dyn PartialReflect>)],
265 ) -> impl FnMut(&usize) -> bool + 'a {
266 |&index| {
267 value
268 .reflect_partial_eq(&*values[index].0)
269 .expect("underlying type does not reflect `PartialEq` and hence doesn't support equality checks")
270 }
271 }
272}
273
274impl Map for DynamicMap {
275 fn get(&self, key: &dyn PartialReflect) -> Option<&dyn PartialReflect> {
276 let hash = Self::internal_hash(key);
277 let eq = Self::internal_eq(key, &self.values);
278 self.indices
279 .find(hash, eq)
280 .map(|&index| &*self.values[index].1)
281 }
282
283 fn get_mut(&mut self, key: &dyn PartialReflect) -> Option<&mut dyn PartialReflect> {
284 let hash = Self::internal_hash(key);
285 let eq = Self::internal_eq(key, &self.values);
286 self.indices
287 .find(hash, eq)
288 .map(|&index| &mut *self.values[index].1)
289 }
290
291 fn get_at(&self, index: usize) -> Option<(&dyn PartialReflect, &dyn PartialReflect)> {
292 self.values
293 .get(index)
294 .map(|(key, value)| (&**key, &**value))
295 }
296
297 fn get_at_mut(
298 &mut self,
299 index: usize,
300 ) -> Option<(&dyn PartialReflect, &mut dyn PartialReflect)> {
301 self.values
302 .get_mut(index)
303 .map(|(key, value)| (&**key, &mut **value))
304 }
305
306 fn len(&self) -> usize {
307 self.values.len()
308 }
309
310 fn iter(&self) -> MapIter {
311 MapIter::new(self)
312 }
313
314 fn drain(&mut self) -> Vec<(Box<dyn PartialReflect>, Box<dyn PartialReflect>)> {
315 self.values.drain(..).collect()
316 }
317
318 fn insert_boxed(
319 &mut self,
320 key: Box<dyn PartialReflect>,
321 value: Box<dyn PartialReflect>,
322 ) -> Option<Box<dyn PartialReflect>> {
323 assert_eq!(
324 key.reflect_partial_eq(&*key),
325 Some(true),
326 "keys inserted in `Map`-like types are expected to reflect `PartialEq`"
327 );
328
329 let hash = Self::internal_hash(&*key);
330 let eq = Self::internal_eq(&*key, &self.values);
331 match self.indices.find(hash, eq) {
332 Some(&index) => {
333 let (key_ref, value_ref) = &mut self.values[index];
334 *key_ref = key;
335 let old_value = core::mem::replace(value_ref, value);
336 Some(old_value)
337 }
338 None => {
339 let index = self.values.len();
340 self.values.push((key, value));
341 self.indices.insert_unique(hash, index, |&index| {
342 Self::internal_hash(&*self.values[index].0)
343 });
344 None
345 }
346 }
347 }
348
349 fn remove(&mut self, key: &dyn PartialReflect) -> Option<Box<dyn PartialReflect>> {
350 let hash = Self::internal_hash(key);
351 let eq = Self::internal_eq(key, &self.values);
352 match self.indices.find_entry(hash, eq) {
353 Ok(entry) => {
354 let (index, _) = entry.remove();
355 let (_, old_value) = self.values.swap_remove(index);
356
357 if let Some((moved_key, _)) = self.values.get(index) {
363 let hash = Self::internal_hash(&**moved_key);
364 let moved_index = self
365 .indices
366 .find_mut(hash, |&moved_index| moved_index == self.values.len())
367 .expect("key inserted in a `DynamicMap` is no longer present, this means its reflected `Hash` might be incorrect");
368 *moved_index = index;
369 }
370
371 Some(old_value)
372 }
373 Err(_) => None,
374 }
375 }
376}
377
378impl PartialReflect for DynamicMap {
379 #[inline]
380 fn get_represented_type_info(&self) -> Option<&'static TypeInfo> {
381 self.represented_type
382 }
383
384 #[inline]
385 fn into_partial_reflect(self: Box<Self>) -> Box<dyn PartialReflect> {
386 self
387 }
388
389 #[inline]
390 fn as_partial_reflect(&self) -> &dyn PartialReflect {
391 self
392 }
393
394 #[inline]
395 fn as_partial_reflect_mut(&mut self) -> &mut dyn PartialReflect {
396 self
397 }
398
399 fn try_into_reflect(self: Box<Self>) -> Result<Box<dyn Reflect>, Box<dyn PartialReflect>> {
400 Err(self)
401 }
402
403 fn try_as_reflect(&self) -> Option<&dyn Reflect> {
404 None
405 }
406
407 fn try_as_reflect_mut(&mut self) -> Option<&mut dyn Reflect> {
408 None
409 }
410
411 fn apply(&mut self, value: &dyn PartialReflect) {
412 map_apply(self, value);
413 }
414
415 fn try_apply(&mut self, value: &dyn PartialReflect) -> Result<(), ApplyError> {
416 map_try_apply(self, value)
417 }
418
419 fn reflect_kind(&self) -> ReflectKind {
420 ReflectKind::Map
421 }
422
423 fn reflect_ref(&self) -> ReflectRef {
424 ReflectRef::Map(self)
425 }
426
427 fn reflect_mut(&mut self) -> ReflectMut {
428 ReflectMut::Map(self)
429 }
430
431 fn reflect_owned(self: Box<Self>) -> ReflectOwned {
432 ReflectOwned::Map(self)
433 }
434
435 fn reflect_partial_eq(&self, value: &dyn PartialReflect) -> Option<bool> {
436 map_partial_eq(self, value)
437 }
438
439 fn debug(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
440 write!(f, "DynamicMap(")?;
441 map_debug(self, f)?;
442 write!(f, ")")
443 }
444
445 #[inline]
446 fn is_dynamic(&self) -> bool {
447 true
448 }
449}
450
451impl_type_path!((in bevy_reflect) DynamicMap);
452
453impl Debug for DynamicMap {
454 fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
455 self.debug(f)
456 }
457}
458
459pub struct MapIter<'a> {
461 map: &'a dyn Map,
462 index: usize,
463}
464
465impl MapIter<'_> {
466 #[inline]
468 pub const fn new(map: &dyn Map) -> MapIter {
469 MapIter { map, index: 0 }
470 }
471}
472
473impl<'a> Iterator for MapIter<'a> {
474 type Item = (&'a dyn PartialReflect, &'a dyn PartialReflect);
475
476 fn next(&mut self) -> Option<Self::Item> {
477 let value = self.map.get_at(self.index);
478 self.index += value.is_some() as usize;
479 value
480 }
481
482 fn size_hint(&self) -> (usize, Option<usize>) {
483 let size = self.map.len();
484 (size, Some(size))
485 }
486}
487
488impl FromIterator<(Box<dyn PartialReflect>, Box<dyn PartialReflect>)> for DynamicMap {
489 fn from_iter<I: IntoIterator<Item = (Box<dyn PartialReflect>, Box<dyn PartialReflect>)>>(
490 items: I,
491 ) -> Self {
492 let mut map = Self::default();
493 for (key, value) in items.into_iter() {
494 map.insert_boxed(key, value);
495 }
496 map
497 }
498}
499
500impl<K: Reflect, V: Reflect> FromIterator<(K, V)> for DynamicMap {
501 fn from_iter<I: IntoIterator<Item = (K, V)>>(items: I) -> Self {
502 let mut map = Self::default();
503 for (key, value) in items.into_iter() {
504 map.insert(key, value);
505 }
506 map
507 }
508}
509
510impl IntoIterator for DynamicMap {
511 type Item = (Box<dyn PartialReflect>, Box<dyn PartialReflect>);
512 type IntoIter = alloc::vec::IntoIter<Self::Item>;
513
514 fn into_iter(self) -> Self::IntoIter {
515 self.values.into_iter()
516 }
517}
518
519impl<'a> IntoIterator for &'a DynamicMap {
520 type Item = (&'a dyn PartialReflect, &'a dyn PartialReflect);
521 type IntoIter = MapIter<'a>;
522
523 fn into_iter(self) -> Self::IntoIter {
524 self.iter()
525 }
526}
527
528impl<'a> ExactSizeIterator for MapIter<'a> {}
529
530#[inline]
540pub fn map_partial_eq<M: Map + ?Sized>(a: &M, b: &dyn PartialReflect) -> Option<bool> {
541 let ReflectRef::Map(map) = b.reflect_ref() else {
542 return Some(false);
543 };
544
545 if a.len() != map.len() {
546 return Some(false);
547 }
548
549 for (key, value) in a.iter() {
550 if let Some(map_value) = map.get(key) {
551 let eq_result = value.reflect_partial_eq(map_value);
552 if let failed @ (Some(false) | None) = eq_result {
553 return failed;
554 }
555 } else {
556 return Some(false);
557 }
558 }
559
560 Some(true)
561}
562
563#[inline]
581pub fn map_debug(dyn_map: &dyn Map, f: &mut Formatter<'_>) -> core::fmt::Result {
582 let mut debug = f.debug_map();
583 for (key, value) in dyn_map.iter() {
584 debug.entry(&key as &dyn Debug, &value as &dyn Debug);
585 }
586 debug.finish()
587}
588
589#[inline]
597pub fn map_apply<M: Map>(a: &mut M, b: &dyn PartialReflect) {
598 if let Err(err) = map_try_apply(a, b) {
599 panic!("{err}");
600 }
601}
602
603#[inline]
613pub fn map_try_apply<M: Map>(a: &mut M, b: &dyn PartialReflect) -> Result<(), ApplyError> {
614 let map_value = b.reflect_ref().as_map()?;
615
616 for (key, b_value) in map_value.iter() {
617 if let Some(a_value) = a.get_mut(key) {
618 a_value.try_apply(b_value)?;
619 } else {
620 a.insert_boxed(key.to_dynamic(), b_value.to_dynamic());
621 }
622 }
623
624 Ok(())
625}
626
627#[cfg(test)]
628mod tests {
629 use super::{DynamicMap, Map};
630 use alloc::{
631 borrow::ToOwned,
632 string::{String, ToString},
633 };
634
635 #[test]
636 fn test_into_iter() {
637 let expected = ["foo", "bar", "baz"];
638
639 let mut map = DynamicMap::default();
640 map.insert(0usize, expected[0].to_string());
641 map.insert(1usize, expected[1].to_string());
642 map.insert(2usize, expected[2].to_string());
643
644 for (index, item) in map.into_iter().enumerate() {
645 let key = item
646 .0
647 .try_take::<usize>()
648 .expect("couldn't downcast to usize");
649 let value = item
650 .1
651 .try_take::<String>()
652 .expect("couldn't downcast to String");
653 assert_eq!(index, key);
654 assert_eq!(expected[index], value);
655 }
656 }
657
658 #[test]
659 fn test_map_get_at() {
660 let values = ["first", "second", "third"];
661 let mut map = DynamicMap::default();
662 map.insert(0usize, values[0].to_string());
663 map.insert(1usize, values[1].to_string());
664 map.insert(1usize, values[2].to_string());
665
666 let (key_r, value_r) = map.get_at(1).expect("Item wasn't found");
667 let value = value_r
668 .try_downcast_ref::<String>()
669 .expect("Couldn't downcast to String");
670 let key = key_r
671 .try_downcast_ref::<usize>()
672 .expect("Couldn't downcast to usize");
673 assert_eq!(key, &1usize);
674 assert_eq!(value, &values[2].to_owned());
675
676 assert!(map.get_at(2).is_none());
677 map.remove(&1usize);
678 assert!(map.get_at(1).is_none());
679 }
680
681 #[test]
682 fn test_map_get_at_mut() {
683 let values = ["first", "second", "third"];
684 let mut map = DynamicMap::default();
685 map.insert(0usize, values[0].to_string());
686 map.insert(1usize, values[1].to_string());
687 map.insert(1usize, values[2].to_string());
688
689 let (key_r, value_r) = map.get_at_mut(1).expect("Item wasn't found");
690 let value = value_r
691 .try_downcast_mut::<String>()
692 .expect("Couldn't downcast to String");
693 let key = key_r
694 .try_downcast_ref::<usize>()
695 .expect("Couldn't downcast to usize");
696 assert_eq!(key, &1usize);
697 assert_eq!(value, &mut values[2].to_owned());
698
699 value.clone_from(&values[0].to_owned());
700
701 assert_eq!(
702 map.get(&1usize)
703 .expect("Item wasn't found")
704 .try_downcast_ref::<String>()
705 .expect("Couldn't downcast to String"),
706 &values[0].to_owned()
707 );
708
709 assert!(map.get_at(2).is_none());
710 }
711
712 #[test]
713 fn next_index_increment() {
714 let values = ["first", "last"];
715 let mut map = DynamicMap::default();
716 map.insert(0usize, values[0]);
717 map.insert(1usize, values[1]);
718
719 let mut iter = map.iter();
720 let size = iter.len();
721
722 for _ in 0..2 {
723 let prev_index = iter.index;
724 assert!(iter.next().is_some());
725 assert_eq!(prev_index, iter.index - 1);
726 }
727
728 for _ in 0..2 {
730 assert!(iter.next().is_none());
731 assert_eq!(size, iter.index);
732 }
733 }
734
735 #[test]
736 fn remove() {
737 let mut map = DynamicMap::default();
738 map.insert(0, 0);
739 map.insert(1, 1);
740
741 assert_eq!(map.remove(&0).unwrap().try_downcast_ref(), Some(&0));
742 assert!(map.get(&0).is_none());
743 assert_eq!(map.get(&1).unwrap().try_downcast_ref(), Some(&1));
744
745 assert_eq!(map.remove(&1).unwrap().try_downcast_ref(), Some(&1));
746 assert!(map.get(&1).is_none());
747
748 assert!(map.remove(&1).is_none());
749 assert!(map.get(&1).is_none());
750 }
751}