@@ -119,61 +119,76 @@ export function retainRead(
119119 ( a , b ) => scope ( a [ 0 ] ) - scope ( b [ 0 ] ) || byUse ( a , b ) ,
120120 ) ;
121121 const byRecent = [ ...frontiers ] . sort ( byUse ) ;
122- const dropped = new Set < string > ( ) ;
122+ // A dropped mark and the kept mark that covered it when it was dropped.
123+ const dropped = new Map < string , string > ( ) ;
124+ const keptCover = ( key : string , value : number ) => {
125+ const cover = coveredBy ?.( key , ( other ) =>
126+ other === key ? value : retained . get ( other ) ,
127+ ) ;
128+ return cover !== undefined && cover !== key && retained . has ( cover )
129+ ? cover
130+ : undefined ;
131+ } ;
132+ // A mark that a kept mark already covers is dropped as it comes up, without
133+ // taking space, so refilling never admits and then frees the same slot.
134+ const admit = ( key : string , value : number , share = 1 ) => {
135+ const cover = keptCover ( key , value ) ;
136+ if ( cover !== undefined ) {
137+ dropped . set ( key , cover ) ;
138+ return true ;
139+ }
140+ if ( ! take ( frontierKey ( key ) , value , share ) ) return false ;
141+ retained . set ( key , value ) ;
142+ return true ;
143+ } ;
123144 const select = ( ) => {
124145 for ( const [ key , value ] of scoped ) {
125146 if ( retained . has ( key ) || dropped . has ( key ) ) continue ;
126147 // Stop at the first broad mark that does not fit, so a narrower mark
127148 // never takes the share ahead of it.
128- if ( ! take ( frontierKey ( key ) , value , SCOPED_SHARE ) ) break ;
129- retained . set ( key , value ) ;
149+ if ( ! admit ( key , value , SCOPED_SHARE ) ) break ;
130150 }
131151 for ( const [ key , value ] of byRecent )
132- if (
133- ! retained . has ( key ) &&
134- ! dropped . has ( key ) &&
135- take ( frontierKey ( key ) , value )
136- )
137- retained . set ( key , value ) ;
152+ if ( ! retained . has ( key ) && ! dropped . has ( key ) ) admit ( key , value ) ;
138153 } ;
139154 select ( ) ;
140- // Refilling can keep more covered marks, so repeat until nothing drops.
155+ // A cover admitted after the marks it covers frees them here. Only then can
156+ // refilling keep more, so repeat until nothing drops.
141157 let pruned = true ;
142158 while ( coveredBy && pruned ) {
143159 pruned = false ;
144160 // Prune against the kept marks only: a cover that did not fit cannot
145161 // replace anything. Decide on one snapshot so a cover is never pruned
146162 // after it has already replaced another mark.
147- const kept = new Map ( retained ) ;
148163 const covers = new Map < string , string > ( ) ;
149- for ( const [ key , value ] of kept ) {
150- const cover = coveredBy ( key , ( other ) =>
151- other === key ? value : kept . get ( other ) ,
152- ) ;
153- if ( cover !== undefined && cover !== key && kept . has ( cover ) )
154- covers . set ( key , cover ) ;
164+ for ( const [ key , value ] of retained ) {
165+ const cover = keptCover ( key , value ) ;
166+ if ( cover !== undefined ) covers . set ( key , cover ) ;
155167 }
156- // A cover that is itself covered passes the recency on to what replaced it.
157- const final = ( key : string ) => {
158- let cover = covers . get ( key ) ?? key ;
159- for ( let hops = 0 ; covers . has ( cover ) && hops < covers . size ; hops ++ )
160- cover = covers . get ( cover ) as string ;
161- return cover ;
162- } ;
163- for ( const key of covers . keys ( ) ) {
164- const cover = final ( key ) ;
165- if ( cover === key || covers . has ( cover ) ) continue ;
168+ for ( const [ key , cover ] of covers ) {
169+ // Chains end at a kept mark: scopes only get broader along them.
170+ let last = cover ;
171+ for ( let hops = 0 ; covers . has ( last ) && hops < covers . size ; hops ++ )
172+ last = covers . get ( last ) as string ;
173+ if ( covers . has ( last ) ) continue ;
166174 const value = retained . get ( key ) as number ;
167175 retained . delete ( key ) ;
168- dropped . add ( key ) ;
176+ dropped . set ( key , cover ) ;
169177 pruned = true ;
170178 used -= cost ( frontierKey ( key ) , value ) ;
171179 keys -- ;
172- if ( nextRecent [ key ] !== undefined )
173- nextRecent [ cover ] = Math . max ( nextRecent [ cover ] ?? 0 , nextRecent [ key ] ) ;
174180 }
175181 if ( pruned ) select ( ) ;
176182 }
183+ // A dropped mark gives its recency to the kept mark at the end of its chain.
184+ for ( const [ key , cover ] of dropped ) {
185+ if ( nextRecent [ key ] === undefined ) continue ;
186+ let last = cover ;
187+ for ( let hops = 0 ; dropped . has ( last ) && hops < dropped . size ; hops ++ )
188+ last = dropped . get ( last ) as string ;
189+ if ( retained . has ( last ) )
190+ nextRecent [ last ] = Math . max ( nextRecent [ last ] ?? 0 , nextRecent [ key ] ) ;
191+ }
177192 const state = Object . freeze ( {
178193 frontiers : Object . freeze ( Object . fromEntries ( retained ) ) ,
179194 overrides : protectedState . overrides ,
0 commit comments