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