1// Copyright 2014 The Flutter Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5/// A collection of key/value pairs which provides efficient retrieval of
6/// value by key.
7///
8/// This class implements a persistent map: extending this map with a new
9/// key/value pair does not modify an existing instance but instead creates a
10/// new instance.
11///
12/// Unlike [Map], this class does not support `null` as a key value and
13/// implements only a functionality needed for a specific use case at the
14/// core of the framework.
15///
16/// Underlying implementation uses a variation of *hash array mapped trie*
17/// data structure with compressed (bitmap indexed) nodes.
18///
19/// See also:
20///
21/// * [Bagwell, Phil. Ideal hash trees.](https://infoscience.epfl.ch/record/64398);
22/// * [Steindorfer, Michael J., and Jurgen J. Vinju. "Optimizing hash-array mapped tries for fast and lean immutable JVM collections."](https://dl.acm.org/doi/abs/10.1145/2814270.2814312);
23/// * [Clojure's `PersistentHashMap`](https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashMap.java).
24///
25class PersistentHashMap<K extends Object, V> {
26 /// Creates an empty hash map.
27 const PersistentHashMap.empty() : this._(null);
28
29 const PersistentHashMap._(this._root);
30
31 final _TrieNode? _root;
32
33 /// If this map does not already contain the given [key] to [value]
34 /// mapping then create a new version of the map which contains
35 /// all mappings from the current one plus the given [key] to [value]
36 /// mapping.
37 PersistentHashMap<K, V> put(K key, V value) {
38 final _TrieNode newRoot =
39 (_root ?? _CompressedNode.empty).put(0, key, key.hashCode, value);
40 if (newRoot == _root) {
41 return this;
42 }
43 return PersistentHashMap<K, V>._(newRoot);
44 }
45
46 /// Returns value associated with the given [key] or `null` if [key]
47 /// is not in the map.
48 @pragma('dart2js:as:trust')
49 V? operator[](K key) {
50 // Unfortunately can not use unsafeCast(...) here because it leads
51 // to worse code generation on VM.
52 return _root?.get(0, key, key.hashCode) as V?;
53 }
54}
55
56/// Base class for nodes in a hash trie.
57///
58/// This trie is keyed by hash code bits using [hashBitsPerLevel] bits
59/// at each level.
60abstract class _TrieNode {
61 static const int hashBitsPerLevel = 5;
62 static const int hashBitsPerLevelMask = (1 << hashBitsPerLevel) - 1;
63
64 @pragma('dart2js:tryInline')
65 @pragma('vm:prefer-inline')
66 @pragma('wasm:prefer-inline')
67 static int trieIndex(int hash, int bitIndex) {
68 return (hash >>> bitIndex) & hashBitsPerLevelMask;
69 }
70
71 /// Insert [key] to [value] mapping into the trie using bits from [keyHash]
72 /// starting at [bitIndex].
73 _TrieNode put(int bitIndex, Object key, int keyHash, Object? value);
74
75 /// Lookup a value associated with the given [key] using bits from [keyHash]
76 /// starting at [bitIndex].
77 Object? get(int bitIndex, Object key, int keyHash);
78}
79
80/// A full (uncompressed) node in the trie.
81///
82/// It contains an array with `1<<_hashBitsPerLevel` elements which
83/// are references to deeper nodes.
84class _FullNode extends _TrieNode {
85 _FullNode(this.descendants);
86
87 static const int numElements = 1 << _TrieNode.hashBitsPerLevel;
88
89 // Caveat: this array is actually List<_TrieNode?> but typing it like that
90 // will introduce a type check when copying this array. For performance
91 // reasons we instead omit the type and use (implicit) casts when accessing
92 // it instead.
93 final List<Object?> descendants;
94
95 @override
96 _TrieNode put(int bitIndex, Object key, int keyHash, Object? value) {
97 final int index = _TrieNode.trieIndex(keyHash, bitIndex);
98 final _TrieNode node = _unsafeCast<_TrieNode?>(descendants[index]) ?? _CompressedNode.empty;
99 final _TrieNode newNode = node.put(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash, value);
100 return identical(newNode, node)
101 ? this
102 : _FullNode(_copy(descendants)..[index] = newNode);
103 }
104
105 @override
106 Object? get(int bitIndex, Object key, int keyHash) {
107 final int index = _TrieNode.trieIndex(keyHash, bitIndex);
108
109 final _TrieNode? node = _unsafeCast<_TrieNode?>(descendants[index]);
110 return node?.get(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash);
111 }
112}
113
114/// Compressed node in the trie.
115///
116/// Instead of storing the full array of outgoing edges this node uses a
117/// compressed representation:
118///
119/// * [_CompressedNode.occupiedIndices] has a bit set for indices which are
120/// occupied.
121/// * furthermore, each occupied index can either be a `(key, value)` pair
122/// representing an actual key/value mapping or a `(null, trieNode)` pair
123/// representing a descendant node.
124///
125/// Keys and values are stored together in a single array (instead of two
126/// parallel arrays) for performance reasons: this improves memory access
127/// locality and reduces memory usage (two arrays of length N take slightly
128/// more space than one array of length 2*N).
129class _CompressedNode extends _TrieNode {
130 _CompressedNode(this.occupiedIndices, this.keyValuePairs);
131 _CompressedNode._empty() : this(0, _emptyArray);
132
133 factory _CompressedNode.single(int bitIndex, int keyHash, _TrieNode node) {
134 final int bit = 1 << _TrieNode.trieIndex(keyHash, bitIndex);
135 // A single (null, node) pair.
136 final List<Object?> keyValuePairs = _makeArray(2)
137 ..[1] = node;
138 return _CompressedNode(bit, keyValuePairs);
139 }
140
141 static final _CompressedNode empty = _CompressedNode._empty();
142
143 // Caveat: do not replace with [] or const [] this will
144 // introduce polymorphism in the keyValuePairs field and significantly
145 // degrade performance on the VM because it will no longer be able to
146 // devirtualize method calls on keyValuePairs.
147 static final List<Object?> _emptyArray = _makeArray(0);
148
149 // This bitmap only uses 32bits due to [_TrieNode.hashBitsPerLevel] being `5`.
150 final int occupiedIndices;
151 final List<Object?> keyValuePairs;
152
153 @override
154 _TrieNode put(int bitIndex, Object key, int keyHash, Object? value) {
155 final int bit = 1 << _TrieNode.trieIndex(keyHash, bitIndex);
156 final int index = _compressedIndex(bit);
157
158 if ((occupiedIndices & bit) != 0) {
159 // Index is occupied.
160 final Object? keyOrNull = keyValuePairs[2 * index];
161 final Object? valueOrNode = keyValuePairs[2 * index + 1];
162
163 // Is this a (null, trieNode) pair?
164 if (identical(keyOrNull, null)) {
165 final _TrieNode newNode = _unsafeCast<_TrieNode>(valueOrNode).put(
166 bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash, value);
167 if (newNode == valueOrNode) {
168 return this;
169 }
170 return _CompressedNode(
171 occupiedIndices, _copy(keyValuePairs)..[2 * index + 1] = newNode);
172 }
173
174 if (key == keyOrNull) {
175 // Found key/value pair with a matching key. If values match
176 // then avoid doing anything otherwise copy and update.
177 return identical(value, valueOrNode)
178 ? this
179 : _CompressedNode(
180 occupiedIndices, _copy(keyValuePairs)..[2 * index + 1] = value);
181 }
182
183 // Two different keys at the same index, resolve collision.
184 final _TrieNode newNode = _resolveCollision(
185 bitIndex + _TrieNode.hashBitsPerLevel,
186 keyOrNull,
187 valueOrNode,
188 key,
189 keyHash,
190 value);
191 return _CompressedNode(
192 occupiedIndices,
193 _copy(keyValuePairs)
194 ..[2 * index] = null
195 ..[2 * index + 1] = newNode);
196 } else {
197 // Adding new key/value mapping.
198 final int occupiedCount = _bitCount(occupiedIndices);
199 if (occupiedCount >= 16) {
200 // Too many occupied: inflate compressed node into full node and
201 // update descendant at the corresponding index.
202 return _inflate(bitIndex)
203 ..descendants[_TrieNode.trieIndex(keyHash, bitIndex)] =
204 _CompressedNode.empty.put(
205 bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash, value);
206 } else {
207 // Grow keyValuePairs by inserting key/value pair at the given
208 // index.
209 final int prefixLength = 2 * index;
210 final int totalLength = 2 * occupiedCount;
211 final List<Object?> newKeyValuePairs = _makeArray(totalLength + 2);
212 for (int srcIndex = 0; srcIndex < prefixLength; srcIndex++) {
213 newKeyValuePairs[srcIndex] = keyValuePairs[srcIndex];
214 }
215 newKeyValuePairs[prefixLength] = key;
216 newKeyValuePairs[prefixLength + 1] = value;
217 for (int srcIndex = prefixLength, dstIndex = prefixLength + 2;
218 srcIndex < totalLength;
219 srcIndex++, dstIndex++) {
220 newKeyValuePairs[dstIndex] = keyValuePairs[srcIndex];
221 }
222 return _CompressedNode(occupiedIndices | bit, newKeyValuePairs);
223 }
224 }
225 }
226
227 @override
228 Object? get(int bitIndex, Object key, int keyHash) {
229 final int bit = 1 << _TrieNode.trieIndex(keyHash, bitIndex);
230 if ((occupiedIndices & bit) == 0) {
231 return null;
232 }
233 final int index = _compressedIndex(bit);
234 final Object? keyOrNull = keyValuePairs[2 * index];
235 final Object? valueOrNode = keyValuePairs[2 * index + 1];
236 if (keyOrNull == null) {
237 final _TrieNode node = _unsafeCast<_TrieNode>(valueOrNode);
238 return node.get(bitIndex + _TrieNode.hashBitsPerLevel, key, keyHash);
239 }
240 if (key == keyOrNull) {
241 return valueOrNode;
242 }
243 return null;
244 }
245
246 /// Convert this node into an equivalent [_FullNode].
247 _FullNode _inflate(int bitIndex) {
248 final List<Object?> nodes = _makeArray(_FullNode.numElements);
249 int srcIndex = 0;
250 for (int dstIndex = 0; dstIndex < _FullNode.numElements; dstIndex++) {
251 if (((occupiedIndices >>> dstIndex) & 1) != 0) {
252 final Object? keyOrNull = keyValuePairs[srcIndex];
253 if (keyOrNull == null) {
254 nodes[dstIndex] = keyValuePairs[srcIndex + 1];
255 } else {
256 nodes[dstIndex] = _CompressedNode.empty.put(
257 bitIndex + _TrieNode.hashBitsPerLevel,
258 keyOrNull,
259 keyValuePairs[srcIndex].hashCode,
260 keyValuePairs[srcIndex + 1]);
261 }
262 srcIndex += 2;
263 }
264 }
265 return _FullNode(nodes);
266 }
267
268 @pragma('dart2js:tryInline')
269 @pragma('vm:prefer-inline')
270 @pragma('wasm:prefer-inline')
271 int _compressedIndex(int bit) {
272 return _bitCount(occupiedIndices & (bit - 1));
273 }
274
275 static _TrieNode _resolveCollision(int bitIndex, Object existingKey,
276 Object? existingValue, Object key, int keyHash, Object? value) {
277 final int existingKeyHash = existingKey.hashCode;
278 // Check if this is a full hash collision and use _HashCollisionNode
279 // in this case.
280 return (existingKeyHash == keyHash)
281 ? _HashCollisionNode.fromCollision(
282 keyHash, existingKey, existingValue, key, value)
283 : _CompressedNode.empty
284 .put(bitIndex, existingKey, existingKeyHash, existingValue)
285 .put(bitIndex, key, keyHash, value);
286 }
287}
288
289/// Trie node representing a full hash collision.
290///
291/// Stores a list of key/value pairs (where all keys have the same hash code).
292class _HashCollisionNode extends _TrieNode {
293 _HashCollisionNode(this.hash, this.keyValuePairs);
294
295 factory _HashCollisionNode.fromCollision(
296 int keyHash, Object keyA, Object? valueA, Object keyB, Object? valueB) {
297 final List<Object?> list = _makeArray(4);
298 list[0] = keyA;
299 list[1] = valueA;
300 list[2] = keyB;
301 list[3] = valueB;
302 return _HashCollisionNode(keyHash, list);
303 }
304
305 final int hash;
306 final List<Object?> keyValuePairs;
307
308 @override
309 _TrieNode put(int bitIndex, Object key, int keyHash, Object? val) {
310 // Is this another full hash collision?
311 if (keyHash == hash) {
312 final int index = _indexOf(key);
313 if (index != -1) {
314 return identical(keyValuePairs[index + 1], val)
315 ? this
316 : _HashCollisionNode(
317 keyHash, _copy(keyValuePairs)..[index + 1] = val);
318 }
319 final int length = keyValuePairs.length;
320 final List<Object?> newArray = _makeArray(length + 2);
321 for (int i = 0; i < length; i++) {
322 newArray[i] = keyValuePairs[i];
323 }
324 newArray[length] = key;
325 newArray[length + 1] = val;
326 return _HashCollisionNode(keyHash, newArray);
327 }
328
329 // Not a full hash collision, need to introduce a _CompressedNode which
330 // uses previously unused bits.
331 return _CompressedNode.single(bitIndex, hash, this)
332 .put(bitIndex, key, keyHash, val);
333 }
334
335 @override
336 Object? get(int bitIndex, Object key, int keyHash) {
337 final int index = _indexOf(key);
338 return index < 0 ? null : keyValuePairs[index + 1];
339 }
340
341 int _indexOf(Object key) {
342 final int length = keyValuePairs.length;
343 for (int i = 0; i < length; i += 2) {
344 if (key == keyValuePairs[i]) {
345 return i;
346 }
347 }
348 return -1;
349 }
350}
351
352/// Returns number of bits set in a 32bit integer.
353///
354/// dart2js safe because we work with 32bit integers.
355@pragma('dart2js:tryInline')
356@pragma('vm:prefer-inline')
357@pragma('wasm:prefer-inline')
358int _bitCount(int n) {
359 assert((n & 0xFFFFFFFF) == n);
360 n = n - ((n >> 1) & 0x55555555);
361 n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
362 n = (n + (n >> 4)) & 0x0F0F0F0F;
363 n = n + (n >> 8);
364 n = n + (n >> 16);
365 return n & 0x0000003F;
366}
367
368/// Create a copy of the given array.
369///
370/// Caveat: do not replace with List.of or similar methods. They are
371/// considerably slower.
372@pragma('dart2js:tryInline')
373@pragma('vm:prefer-inline')
374@pragma('wasm:prefer-inline')
375List<Object?> _copy(List<Object?> array) {
376 final List<Object?> clone = _makeArray(array.length);
377 for (int j = 0; j < array.length; j++) {
378 clone[j] = array[j];
379 }
380 return clone;
381}
382
383/// Create a fixed-length array of the given length filled with `null`.
384///
385/// We are using fixed length arrays because they are smaller and
386/// faster to access on VM. Growable arrays are represented by 2 objects
387/// (growable array instance pointing to a fixed array instance) and
388/// consequently fixed length arrays are faster to allocated, require less
389/// memory and are faster to access (less indirections).
390@pragma('dart2js:tryInline')
391@pragma('vm:prefer-inline')
392@pragma('wasm:prefer-inline')
393List<Object?> _makeArray(int length) {
394 return List<Object?>.filled(length, null);
395}
396
397/// This helper method becomes an no-op when compiled with dart2js on
398/// with high level of optimizations enabled.
399@pragma('dart2js:as:trust')
400@pragma('dart2js:tryInline')
401@pragma('vm:prefer-inline')
402@pragma('wasm:prefer-inline')
403T _unsafeCast<T>(Object? o) {
404 return o as T;
405}
406