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 =
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.
64 abstract 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.
86 class _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).
130 class _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).
291 class _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' )
356 int _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' )
372 List <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' )
389 List <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' )
398 T _unsafeCast <T>(Object ? o ) {
399 return o as T ;
400 }
401