@@ -118,42 +118,105 @@ namespace ts {
118118 export const MapCtr = typeof Map !== "undefined" && "entries" in Map . prototype ? Map : shimMap ( ) ;
119119
120120 // Keep the class inside a function so it doesn't get compiled if it's not used.
121- function shimMap ( ) : new < T > ( ) => Map < T > {
121+ export function shimMap ( ) : new < T > ( ) => Map < T > {
122+
123+ interface MapEntry < T > {
124+ readonly key ?: string ;
125+ value ?: T ;
126+
127+ // Linked list references for iterators.
128+ nextEntry ?: MapEntry < T > ;
129+ previousEntry ?: MapEntry < T > ;
130+
131+ /**
132+ * Specifies if iterators should skip the next entry.
133+ * This will be set when an entry is deleted.
134+ * See https://github.com/Microsoft/TypeScript/pull/27292 for more information.
135+ */
136+ skipNext ?: boolean ;
137+ }
122138
123139 class MapIterator < T , U extends ( string | T | [ string , T ] ) > {
124- private data : MapLike < T > ;
125- private keys : ReadonlyArray < string > ;
126- private index = 0 ;
127- private selector : ( data : MapLike < T > , key : string ) => U ;
128- constructor ( data : MapLike < T > , selector : ( data : MapLike < T > , key : string ) => U ) {
129- this . data = data ;
140+ private currentEntry ?: MapEntry < T > ;
141+ private selector : ( key : string , value : T ) => U ;
142+
143+ constructor ( currentEntry : MapEntry < T > , selector : ( key : string , value : T ) => U ) {
144+ this . currentEntry = currentEntry ;
130145 this . selector = selector ;
131- this . keys = Object . keys ( data ) ;
132146 }
133147
134148 public next ( ) : { value : U , done : false } | { value : never , done : true } {
135- const index = this . index ;
136- if ( index < this . keys . length ) {
137- this . index ++ ;
138- return { value : this . selector ( this . data , this . keys [ index ] ) , done : false } ;
149+ // Navigate to the next entry.
150+ while ( this . currentEntry ) {
151+ const skipNext = ! ! this . currentEntry . skipNext ;
152+ this . currentEntry = this . currentEntry . nextEntry ;
153+
154+ if ( ! skipNext ) {
155+ break ;
156+ }
157+ }
158+
159+ if ( this . currentEntry ) {
160+ return { value : this . selector ( this . currentEntry . key ! , this . currentEntry . value ! ) , done : false } ;
161+ }
162+ else {
163+ return { value : undefined as never , done : true } ;
139164 }
140- return { value : undefined as never , done : true } ;
141165 }
142166 }
143167
144168 return class < T > implements Map < T > {
145- private data = createDictionaryObject < T > ( ) ;
169+ private data = createDictionaryObject < MapEntry < T > > ( ) ;
146170 public size = 0 ;
147171
172+ // Linked list references for iterators.
173+ // See https://github.com/Microsoft/TypeScript/pull/27292
174+ // for more information.
175+
176+ /**
177+ * The first entry in the linked list.
178+ * Note that this is only a stub that serves as starting point
179+ * for iterators and doesn't contain a key and a value.
180+ */
181+ private readonly firstEntry : MapEntry < T > ;
182+ private lastEntry : MapEntry < T > ;
183+
184+ constructor ( ) {
185+ // Create a first (stub) map entry that will not contain a key
186+ // and value but serves as starting point for iterators.
187+ this . firstEntry = { } ;
188+ // When the map is empty, the last entry is the same as the
189+ // first one.
190+ this . lastEntry = this . firstEntry ;
191+ }
192+
148193 get ( key : string ) : T | undefined {
149- return this . data [ key ] ;
194+ const entry = this . data [ key ] as MapEntry < T > | undefined ;
195+ return entry && entry . value ! ;
150196 }
151197
152198 set ( key : string , value : T ) : this {
153199 if ( ! this . has ( key ) ) {
154200 this . size ++ ;
201+
202+ // Create a new entry that will be appended at the
203+ // end of the linked list.
204+ const newEntry : MapEntry < T > = {
205+ key,
206+ value
207+ } ;
208+ this . data [ key ] = newEntry ;
209+
210+ // Adjust the references.
211+ const previousLastEntry = this . lastEntry ;
212+ previousLastEntry . nextEntry = newEntry ;
213+ newEntry . previousEntry = previousLastEntry ;
214+ this . lastEntry = newEntry ;
155215 }
156- this . data [ key ] = value ;
216+ else {
217+ this . data [ key ] . value = value ;
218+ }
219+
157220 return this ;
158221 }
159222
@@ -165,32 +228,81 @@ namespace ts {
165228 delete ( key : string ) : boolean {
166229 if ( this . has ( key ) ) {
167230 this . size -- ;
231+ const entry = this . data [ key ] ;
168232 delete this . data [ key ] ;
233+
234+ // Adjust the linked list references of the neighbor entries.
235+ const previousEntry = entry . previousEntry ! ;
236+ previousEntry . nextEntry = entry . nextEntry ;
237+ if ( entry . nextEntry ) {
238+ entry . nextEntry . previousEntry = previousEntry ;
239+ }
240+
241+ // When the deleted entry was the last one, we need to
242+ // adust the lastEntry reference.
243+ if ( this . lastEntry === entry ) {
244+ this . lastEntry = previousEntry ;
245+ }
246+
247+ // Adjust the forward reference of the deleted entry
248+ // in case an iterator still references it. This allows us
249+ // to throw away the entry, but when an active iterator
250+ // (which points to the current entry) continues, it will
251+ // navigate to the entry that originally came before the
252+ // current one and skip it.
253+ entry . previousEntry = undefined ;
254+ entry . nextEntry = previousEntry ;
255+ entry . skipNext = true ;
256+
169257 return true ;
170258 }
171259 return false ;
172260 }
173261
174262 clear ( ) : void {
175- this . data = createDictionaryObject < T > ( ) ;
263+ this . data = createDictionaryObject < MapEntry < T > > ( ) ;
176264 this . size = 0 ;
265+
266+ // Reset the linked list. Note that we must adjust the forward
267+ // references of the deleted entries to ensure iterators stuck
268+ // in the middle of the list don't continue with deleted entries,
269+ // but can continue with new entries added after the clear()
270+ // operation.
271+ const firstEntry = this . firstEntry ;
272+ let currentEntry = firstEntry . nextEntry ;
273+ while ( currentEntry ) {
274+ const nextEntry = currentEntry . nextEntry ;
275+ currentEntry . previousEntry = undefined ;
276+ currentEntry . nextEntry = firstEntry ;
277+ currentEntry . skipNext = true ;
278+
279+ currentEntry = nextEntry ;
280+ }
281+ firstEntry . nextEntry = undefined ;
282+ this . lastEntry = firstEntry ;
177283 }
178284
179285 keys ( ) : Iterator < string > {
180- return new MapIterator ( this . data , ( _data , key ) => key ) ;
286+ return new MapIterator ( this . firstEntry , key => key ) ;
181287 }
182288
183289 values ( ) : Iterator < T > {
184- return new MapIterator ( this . data , ( data , key ) => data [ key ] ) ;
290+ return new MapIterator ( this . firstEntry , ( _key , value ) => value ) ;
185291 }
186292
187293 entries ( ) : Iterator < [ string , T ] > {
188- return new MapIterator ( this . data , ( data , key ) => [ key , data [ key ] ] as [ string , T ] ) ;
294+ return new MapIterator ( this . firstEntry , ( key , value ) => [ key , value ] as [ string , T ] ) ;
189295 }
190296
191297 forEach ( action : ( value : T , key : string ) => void ) : void {
192- for ( const key in this . data ) {
193- action ( this . data [ key ] , key ) ;
298+ const iterator = this . entries ( ) ;
299+ while ( true ) {
300+ const { value : entry , done } = iterator . next ( ) ;
301+ if ( done ) {
302+ break ;
303+ }
304+
305+ action ( entry [ 1 ] , entry [ 0 ] ) ;
194306 }
195307 }
196308 } ;
0 commit comments