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