nanvm_lib/vm/object/own_entries.rs
1use std::collections::{BTreeMap, btree_map::Entry};
2
3use super::Object;
4use crate::{
5 common::sized_index::SizedIndex,
6 vm::{IVm, Property, String, member_access::string_to_index},
7};
8
9/// The `u32` value of `k` if ECMAScript's own-property enumeration treats it
10/// as an "array index" — the keys `JSON.stringify` (via
11/// `[[OwnPropertyKeys]]`) lists first, ascending, ahead of every other key
12/// in insertion order: [`string_to_index`]'s canonical index, except
13/// `"4294967295"`, the one `ToUint32` value the spec carves out
14/// (`ToUint32(key) != 2^32 - 1`).
15///
16/// [`Object::own_entries`] uses this to sort an object's array-index keys ahead
17/// of the rest, by this value rather than by the key's own text — `"10"`
18/// sorts after `"2"` numerically, the opposite of their lexicographic order.
19fn array_index_value<A: IVm>(k: &String<A>) -> Option<u32> {
20 string_to_index(k).filter(|&n| n != u32::MAX)
21}
22
23impl<A: IVm> Object<A> {
24 /// The own enumerable string-keyed entries, as `[[OwnPropertyKeys]]`
25 /// lists them: each key once, holding its *last* value at its *first*
26 /// position, array-index keys first, ascending by value, then every
27 /// other key in insertion order. The one view `JSON.stringify` writes
28 /// and an object spread copies (`Any::to_json`, `Any::object_spread`),
29 /// so the two cannot disagree on order.
30 ///
31 /// An object's property list is never deduplicated on construction
32 /// ([`Object::own_property`]'s doc comment), so one pass over it keeps
33 /// each key's first position and overwrites its value on every later
34 /// write, finding the key's slot through a map ordered by
35 /// [`String`]'s `Ord`: `O(n log n)` in the number of properties, where a
36 /// scan per key would be quadratic.
37 ///
38 /// ```
39 /// use nanvm_lib::{naive::Naive, vm::{Any, IVm, Object, String, ToAny, ToObject}};
40 /// fn own_entries_test<A: IVm>() {
41 /// let o: Object<A> = [
42 /// ("b".into(), true.to_any()),
43 /// ("1".into(), true.to_any()),
44 /// ("b".into(), false.to_any()),
45 /// ].to_object();
46 /// let keys: Vec<String<A>> = o.own_entries().into_iter().map(|(k, _)| k).collect();
47 /// assert_eq!(keys, [String::from("1"), String::from("b")]);
48 /// }
49 /// own_entries_test::<Naive>();
50 /// ```
51 pub fn own_entries(&self) -> Vec<Property<A>> {
52 let mut slots: BTreeMap<String<A>, usize> = BTreeMap::new();
53 let mut entries: Vec<Property<A>> = Vec::new();
54 for i in 0..self.length() {
55 let (k, v) = &self[i];
56 match slots.entry(k.clone()) {
57 Entry::Occupied(slot) => entries[*slot.get()].1 = v.clone(),
58 Entry::Vacant(slot) => {
59 slot.insert(entries.len());
60 entries.push((k.clone(), v.clone()));
61 }
62 }
63 }
64 let mut index_entries: Vec<(u32, Property<A>)> = Vec::new();
65 let mut other_entries: Vec<Property<A>> = Vec::new();
66 for (k, v) in entries {
67 match array_index_value(&k) {
68 Some(n) => index_entries.push((n, (k, v))),
69 None => other_entries.push((k, v)),
70 }
71 }
72 index_entries.sort_by_key(|(n, _)| *n);
73 index_entries
74 .into_iter()
75 .map(|(_, entry)| entry)
76 .chain(other_entries)
77 .collect()
78 }
79}
80
81#[cfg(test)]
82mod tests {
83 use super::array_index_value;
84 use crate::{
85 naive::Naive,
86 vm::{Object, String, ToAny, ToObject, member_access::string_to_index},
87 };
88
89 /// `array_index_value` is `string_to_index` but for one key,
90 /// `"4294967295"`: an element read's index, never an own-key ordering's.
91 #[test]
92 fn array_index_value_is_string_to_index_but_for_u32_max() {
93 let long = "1".repeat(40);
94 let cases: [(&str, Option<u32>); 14] = [
95 ("", None),
96 ("0", Some(0)),
97 ("00", None),
98 ("01", None),
99 ("7", Some(7)),
100 ("10", Some(10)),
101 ("a", None),
102 ("1a", None),
103 ("\u{0661}", None),
104 ("\u{FF11}", None),
105 ("4294967294", Some(u32::MAX - 1)),
106 ("4294967295", None),
107 ("4294967296", None),
108 (long.as_str(), None),
109 ];
110 for (key, expected) in cases {
111 let k: String<Naive> = key.into();
112 assert_eq!(array_index_value(&k), expected, "{key:?}");
113 let scanned = if key == "4294967295" {
114 Some(u32::MAX)
115 } else {
116 expected
117 };
118 assert_eq!(string_to_index(&k), scanned, "{key:?}");
119 }
120 }
121
122 const SIZE: u32 = 100_000;
123
124 fn key(i: u32) -> String<Naive> {
125 format!("k{i}").as_str().into()
126 }
127
128 /// A size where a scan per key, quadratic, ran for seconds: one pass
129 /// keeps every key, in insertion order.
130 #[test]
131 fn many_distinct_keys() {
132 let o: Object<Naive> = (0..SIZE)
133 .map(|i| (key(i), f64::from(i).to_any()))
134 .to_object();
135 let entries = o.own_entries();
136 assert_eq!(entries.len(), SIZE as usize);
137 for (i, (k, v)) in (0..SIZE).zip(entries) {
138 assert_eq!(k, key(i));
139 assert_eq!(v, f64::from(i).to_any());
140 }
141 }
142
143 /// Every key written twice, the whole list over again: each key once,
144 /// at its first position, holding the second write.
145 #[test]
146 fn many_repeated_keys() {
147 let o: Object<Naive> = (0..2 * SIZE)
148 .map(|i| (key(i % SIZE), f64::from(i).to_any()))
149 .to_object();
150 let entries = o.own_entries();
151 assert_eq!(entries.len(), SIZE as usize);
152 for (i, (k, v)) in (0..SIZE).zip(entries) {
153 assert_eq!(k, key(i));
154 assert_eq!(v, f64::from(SIZE + i).to_any());
155 }
156 }
157}