1use std::fmt;
2use std::hash::{Hash, Hasher};
3use std::iter::Copied;
4use std::ops::Range;
5use std::{slice, vec};
6
7use super::scope_chain::{ChainPrefix, SharedScopes};
8
9#[derive(
10 Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize,
11)]
12pub struct Scope(u32);
13
14#[derive(Default, serde::Serialize, serde::Deserialize)]
15pub struct ScopeAllocator {
16 next: u32,
17}
18
19impl ScopeAllocator {
20 pub fn next_scope(&self) -> Scope {
21 Scope(self.next)
22 }
23
24 pub fn fresh(&mut self) -> Scope {
25 let scope = Scope(self.next);
26 self.next += 1;
27 scope
28 }
29}
30
31#[derive(Clone, Default, serde::Serialize, serde::Deserialize)]
32pub struct ScopeSet {
33 sorted: SortedScopes,
34}
35
36impl ScopeSet {
37 pub(super) const SHORTEST_SHARED_PREFIX: usize = 64;
38
39 pub fn add(&mut self, scope: Scope) {
40 if let Err(position) = self.position(scope)
41 && !self.shares(scope)
42 {
43 self.sorted.insert(position, scope);
44 }
45 }
46
47 pub fn add_prefix(&mut self, prefix: &ChainPrefix) {
48 if self.is_worth_sharing(prefix) {
49 self.sorted.share(prefix.clone());
50 } else {
51 prefix.for_each(|scope| self.add(scope));
52 }
53 }
54
55 pub fn remove(&mut self, scope: Scope) {
56 match self.position(scope) {
57 Ok(position) => self.sorted.remove(position),
58 Err(_) if self.shares(scope) => self.remove_shared(scope),
59 Err(_) => {}
60 }
61 }
62
63 pub fn retain(&mut self, keep: impl Fn(Scope) -> bool) {
64 if self.shared().is_some_and(|shared| shared.splits(&keep)) {
65 self.unshare();
66 }
67 self.sorted.retain(keep);
68 }
69
70 pub fn flip(&mut self, scope: Scope) {
71 match self.position(scope) {
72 Ok(position) => self.sorted.remove(position),
73 Err(_) if self.shares(scope) => self.remove_shared(scope),
74 Err(position) => self.sorted.insert(position, scope),
75 }
76 }
77
78 pub fn contains(&self, scope: Scope) -> bool {
79 self.position(scope).is_ok() || self.shares(scope)
80 }
81
82 pub fn any(&self, matches: impl Fn(Scope) -> bool) -> bool {
83 self.own().iter().any(|scope| matches(*scope))
84 || self.shared().is_some_and(|shared| shared.any(&matches))
85 }
86
87 #[inline]
88 pub fn is_subset_of(&self, other: &ScopeSet) -> bool {
89 if self.is_plain() && other.is_plain() {
90 return self.is_plain_subset_of(other);
91 }
92 self.shared_is_subset_of(other)
93 }
94
95 pub(super) fn largest(&self) -> Option<Scope> {
96 let own_largest = self.own().last().copied();
97 match self.shared() {
98 Some(shared) => own_largest.max(shared.largest()),
99 None => own_largest,
100 }
101 }
102
103 pub(super) fn iter(&self) -> SortedIter<'_> {
104 match self.shared() {
105 Some(_) => SortedIter::Merged(self.merged().into_iter()),
106 None => SortedIter::Own(self.own().iter().copied()),
107 }
108 }
109
110 pub(super) fn len(&self) -> usize {
111 self.own().len() + self.shared().map_or(0, SharedScopes::len)
112 }
113
114 pub(super) fn may_hold_scope_in(&self, range: &Range<Scope>) -> bool {
115 let own = self.own();
116 let first_at_or_after = own.partition_point(|scope| *scope < range.start);
117 self.shared().is_some()
118 || own
119 .get(first_at_or_after)
120 .is_some_and(|scope| *scope < range.end)
121 }
122
123 pub(super) fn is_plain(&self) -> bool {
124 self.shared().is_none()
125 }
126
127 #[inline]
128 pub(super) fn is_plain_subset_of(&self, other: &ScopeSet) -> bool {
129 debug_assert!(self.is_plain() && other.is_plain());
130 let mut larger = other.own().iter();
131 self.own()
132 .iter()
133 .all(|scope| larger.any(|candidate| candidate == scope))
134 }
135
136 pub(super) fn plain_largest(&self) -> Option<Scope> {
137 debug_assert!(self.is_plain());
138 self.own().last().copied()
139 }
140
141 pub(super) fn plain_iter(&self) -> impl Iterator<Item = Scope> {
142 debug_assert!(self.is_plain());
143 self.own().iter().copied()
144 }
145
146 pub(super) fn plain_len(&self) -> usize {
147 debug_assert!(self.is_plain());
148 self.own().len()
149 }
150
151 #[inline(never)]
152 fn shared_is_subset_of(&self, other: &ScopeSet) -> bool {
153 self.own().iter().all(|scope| other.contains(*scope))
154 && self.shared().is_none_or(|shared| {
155 shared
156 .prefixes()
157 .iter()
158 .all(|prefix| other.contains_prefix(prefix))
159 })
160 }
161
162 fn is_worth_sharing(&self, prefix: &ChainPrefix) -> bool {
163 prefix.len() >= Self::SHORTEST_SHARED_PREFIX && Some(prefix.first()) > self.largest()
164 }
165
166 fn contains_prefix(&self, prefix: &ChainPrefix) -> bool {
167 let covered = self
168 .shared()
169 .map_or(0, |shared| shared.covered_length(prefix));
170 prefix.all_from(covered, |scope| self.contains(scope))
171 }
172
173 #[inline(never)]
174 fn remove_shared(&mut self, scope: Scope) {
175 self.unshare();
176 self.remove(scope);
177 }
178
179 fn merged(&self) -> Vec<Scope> {
180 let mut scopes = self.own().to_vec();
181 if let Some(shared) = self.shared() {
182 scopes.extend(shared.ascending());
183 scopes.sort_unstable();
184 }
185 scopes
186 }
187
188 #[inline]
189 fn shares(&self, scope: Scope) -> bool {
190 self.shared().is_some_and(|shared| shared.contains(scope))
191 }
192
193 fn unshare(&mut self) {
194 self.sorted = SortedScopes::spilled(self.merged());
195 }
196
197 #[inline]
198 fn shared(&self) -> Option<&SharedScopes> {
199 self.sorted.shared()
200 }
201
202 fn own(&self) -> &[Scope] {
203 self.sorted.as_slice()
204 }
205
206 fn position(&self, scope: Scope) -> Result<usize, usize> {
207 self.own().binary_search(&scope)
208 }
209}
210
211impl PartialEq for ScopeSet {
212 fn eq(&self, other: &Self) -> bool {
213 if self.shared() == other.shared() {
214 return self.own() == other.own();
215 }
216 self.len() == other.len() && self.merged() == other.merged()
217 }
218}
219
220impl Eq for ScopeSet {}
221
222impl Hash for ScopeSet {
223 fn hash<H: Hasher>(&self, state: &mut H) {
224 match self.shared() {
225 Some(_) => self.merged().hash(state),
226 None => self.own().hash(state),
227 }
228 }
229}
230
231impl fmt::Debug for ScopeSet {
232 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
233 formatter.debug_set().entries(self.iter()).finish()
234 }
235}
236
237pub(super) enum SortedIter<'set> {
238 Own(Copied<slice::Iter<'set, Scope>>),
239 Merged(vec::IntoIter<Scope>),
240}
241
242impl Iterator for SortedIter<'_> {
243 type Item = Scope;
244
245 fn next(&mut self) -> Option<Scope> {
246 match self {
247 Self::Own(scopes) => scopes.next(),
248 Self::Merged(scopes) => scopes.next(),
249 }
250 }
251}
252
253#[derive(Clone, serde::Serialize, serde::Deserialize)]
254enum SortedScopes {
255 Inline {
256 length: usize,
257 scopes: [Scope; SortedScopes::INLINE_CAPACITY],
258 },
259 Spilled {
260 scopes: Vec<Scope>,
261 shared: SharedScopes,
262 },
263}
264
265impl Default for SortedScopes {
266 fn default() -> Self {
267 Self::Inline {
268 length: 0,
269 scopes: [Scope(0); Self::INLINE_CAPACITY],
270 }
271 }
272}
273
274impl SortedScopes {
275 const INLINE_CAPACITY: usize = 8;
276
277 fn spilled(scopes: Vec<Scope>) -> Self {
278 Self::Spilled {
279 scopes,
280 shared: SharedScopes::default(),
281 }
282 }
283
284 fn as_slice(&self) -> &[Scope] {
285 match self {
286 Self::Inline { length, scopes } => &scopes[..*length],
287 Self::Spilled { scopes, .. } => scopes,
288 }
289 }
290
291 fn shared(&self) -> Option<&SharedScopes> {
292 match self {
293 Self::Spilled { shared, .. } if !shared.is_empty() => Some(shared),
294 Self::Inline { .. } | Self::Spilled { .. } => None,
295 }
296 }
297
298 fn share(&mut self, prefix: ChainPrefix) {
299 if let Self::Inline { .. } = self {
300 *self = Self::spilled(self.as_slice().to_vec());
301 }
302 if let Self::Spilled { shared, .. } = self {
303 shared.push(prefix);
304 }
305 }
306
307 fn insert(&mut self, position: usize, scope: Scope) {
308 match self {
309 Self::Inline { length, scopes } if *length < Self::INLINE_CAPACITY => {
310 scopes.copy_within(position..*length, position + 1);
311 scopes[position] = scope;
312 *length += 1;
313 }
314 Self::Inline { .. } => *self = Self::spilled(self.spilled_with(position, scope)),
315 Self::Spilled { scopes, .. } => scopes.insert(position, scope),
316 }
317 }
318
319 fn spilled_with(&self, position: usize, scope: Scope) -> Vec<Scope> {
320 let mut scopes = self.as_slice().to_vec();
321 scopes.insert(position, scope);
322 scopes
323 }
324
325 fn remove(&mut self, position: usize) {
326 match self {
327 Self::Inline { length, scopes } => {
328 scopes.copy_within(position + 1..*length, position);
329 *length -= 1;
330 }
331 Self::Spilled { scopes, .. } => {
332 scopes.remove(position);
333 }
334 }
335 }
336
337 fn retain(&mut self, keep: impl Fn(Scope) -> bool) {
338 match self {
339 Self::Inline { length, scopes } => {
340 *length = Self::retain_inline(&mut scopes[..*length], keep)
341 }
342 Self::Spilled { scopes, shared } => {
343 scopes.retain(|scope| keep(*scope));
344 shared.retain_kept(&keep);
345 }
346 }
347 }
348
349 fn retain_inline(scopes: &mut [Scope], keep: impl Fn(Scope) -> bool) -> usize {
350 let mut retained = 0;
351 for index in 0..scopes.len() {
352 if keep(scopes[index]) {
353 scopes[retained] = scopes[index];
354 retained += 1;
355 }
356 }
357 retained
358 }
359}
360
361#[cfg(test)]
362mod tests {
363 use super::*;
364 use crate::scope::ScopeChain;
365
366 struct Scopes {
367 allocator: ScopeAllocator,
368 }
369
370 impl Scopes {
371 const SHARED_LENGTH: usize = ScopeSet::SHORTEST_SHARED_PREFIX;
372
373 fn new() -> Self {
374 Self {
375 allocator: ScopeAllocator::default(),
376 }
377 }
378
379 fn set_of(&mut self, count: usize) -> (ScopeSet, Vec<Scope>) {
380 let scopes: Vec<Scope> = (0..count).map(|_| self.allocator.fresh()).collect();
381 let mut set = ScopeSet::default();
382 scopes.iter().for_each(|scope| set.add(*scope));
383 (set, scopes)
384 }
385
386 fn chain_of(&mut self, count: usize) -> (ScopeChain, Vec<Scope>) {
387 let chain = ScopeChain::default();
388 let scopes: Vec<Scope> = (0..count).map(|_| self.allocator.fresh()).collect();
389 scopes.iter().for_each(|scope| chain.push(*scope));
390 (chain, scopes)
391 }
392
393 fn shared_set_of(&mut self, count: usize) -> (ScopeSet, Vec<Scope>) {
394 let (chain, scopes) = self.chain_of(count);
395 let mut set = ScopeSet::default();
396 set.add_prefix(&Scopes::prefix_of(&chain));
397 (set, scopes)
398 }
399
400 fn prefix_of(chain: &ScopeChain) -> ChainPrefix {
401 chain.prefix().expect("a test chain holds scopes")
402 }
403
404 fn added_one_by_one(scopes: &[Scope]) -> ScopeSet {
405 let mut set = ScopeSet::default();
406 scopes.iter().for_each(|scope| set.add(*scope));
407 set
408 }
409
410 fn hash_of(set: &ScopeSet) -> u64 {
411 let mut hasher = std::hash::DefaultHasher::new();
412 set.hash(&mut hasher);
413 hasher.finish()
414 }
415 }
416
417 #[test]
418 fn finds_a_scope_among_its_own_scopes() {
419 let (set, scopes) = Scopes::new().set_of(3);
420 assert!(set.any(|scope| scope == scopes[1]));
421 }
422
423 #[test]
424 fn finds_a_scope_among_its_shared_scopes() {
425 let (set, scopes) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
426 let last = scopes[scopes.len() - 1];
427 assert!(set.any(|scope| scope == last));
428 }
429
430 #[test]
431 fn finds_no_scope_that_a_shared_set_lacks() {
432 let mut fixture = Scopes::new();
433 let (set, _) = fixture.shared_set_of(Scopes::SHARED_LENGTH);
434 let absent = fixture.allocator.fresh();
435 assert!(!set.any(|scope| scope == absent));
436 }
437
438 #[test]
439 fn flipping_twice_restores_the_set() {
440 let (mut set, scopes) = Scopes::new().set_of(2);
441 let original = set.clone();
442 set.flip(scopes[0]);
443 set.flip(scopes[0]);
444 assert_eq!(set, original);
445 }
446
447 #[test]
448 fn a_smaller_set_is_a_subset_of_a_larger_one() {
449 let (larger, scopes) = Scopes::new().set_of(3);
450 let mut smaller = larger.clone();
451 smaller.remove(scopes[1]);
452 assert!(smaller.is_subset_of(&larger));
453 assert!(!larger.is_subset_of(&smaller));
454 }
455
456 #[test]
457 fn a_set_beyond_its_inline_capacity_keeps_every_scope_in_order() {
458 let (set, scopes) = Scopes::new().set_of(SortedScopes::INLINE_CAPACITY + 2);
459 assert_eq!(set.iter().collect::<Vec<_>>(), scopes);
460 }
461
462 #[test]
463 fn scopes_added_out_of_order_come_back_sorted() {
464 for count in [
465 SortedScopes::INLINE_CAPACITY,
466 SortedScopes::INLINE_CAPACITY + 2,
467 ] {
468 let (sorted, scopes) = Scopes::new().set_of(count);
469 let mut reversed = ScopeSet::default();
470 scopes.iter().rev().for_each(|scope| reversed.add(*scope));
471 assert_eq!(reversed, sorted);
472 }
473 }
474
475 #[test]
476 fn removing_and_retaining_work_beyond_the_inline_capacity() {
477 let (mut set, scopes) = Scopes::new().set_of(SortedScopes::INLINE_CAPACITY + 2);
478 set.remove(scopes[0]);
479 set.flip(scopes[1]);
480 set.retain(|scope| scope != scopes[2]);
481 assert_eq!(set.iter().collect::<Vec<_>>(), scopes[3..]);
482 }
483
484 #[test]
485 fn retaining_an_inline_set_keeps_the_chosen_scopes() {
486 let (mut set, scopes) = Scopes::new().set_of(3);
487 set.retain(|scope| scope != scopes[1]);
488 assert_eq!(set.iter().collect::<Vec<_>>(), [scopes[0], scopes[2]]);
489 }
490
491 #[test]
492 fn a_spilled_set_equals_and_hashes_like_an_inline_set_with_the_same_scopes() {
493 let (mut spilled, scopes) = Scopes::new().set_of(SortedScopes::INLINE_CAPACITY + 1);
494 spilled.remove(scopes[SortedScopes::INLINE_CAPACITY]);
495 let mut inline = ScopeSet::default();
496 scopes[..SortedScopes::INLINE_CAPACITY]
497 .iter()
498 .for_each(|scope| inline.add(*scope));
499 assert_eq!(spilled, inline);
500 assert_eq!(Scopes::hash_of(&spilled), Scopes::hash_of(&inline));
501 }
502
503 #[test]
504 fn a_set_shows_its_scopes() {
505 let (set, _) = Scopes::new().set_of(2);
506 assert_eq!(format!("{set:?}"), "{Scope(0), Scope(1)}");
507 }
508
509 #[test]
510 fn a_prefix_shares_its_scopes_instead_of_copying_them() {
511 let (set, scopes) = Scopes::new().shared_set_of(SortedScopes::INLINE_CAPACITY * 100);
512 assert!(set.own().is_empty());
513 assert_eq!(set.len(), scopes.len());
514 }
515
516 #[test]
517 fn a_prefix_keeps_the_scopes_its_chain_held_when_taken() {
518 let mut scopes = Scopes::new();
519 let (chain, held) = scopes.chain_of(3);
520 let mut set = ScopeSet::default();
521 set.add_prefix(&Scopes::prefix_of(&chain));
522 chain.push(scopes.allocator.fresh());
523 assert_eq!(set.iter().collect::<Vec<_>>(), held);
524 }
525
526 #[test]
527 fn a_shared_set_equals_and_hashes_like_its_scopes_added_one_by_one() {
528 let (shared, scopes) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
529 let added = Scopes::added_one_by_one(&scopes);
530 assert_eq!(shared, added);
531 assert_eq!(Scopes::hash_of(&shared), Scopes::hash_of(&added));
532 assert_eq!(shared.largest(), added.largest());
533 assert!(shared.is_subset_of(&added) && added.is_subset_of(&shared));
534 }
535
536 #[test]
537 fn own_scopes_and_shared_scopes_come_back_sorted() {
538 let mut scopes = Scopes::new();
539 let older = scopes.allocator.fresh();
540 let (mut set, shared) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
541 let newer = scopes.allocator.fresh();
542 set.add(newer);
543 set.add(older);
544 let expected: Vec<Scope> = [older].into_iter().chain(shared).chain([newer]).collect();
545 assert_eq!(set.iter().collect::<Vec<_>>(), expected);
546 }
547
548 #[test]
549 fn a_shorter_prefix_of_a_chain_is_a_subset_of_a_longer_one() {
550 let mut scopes = Scopes::new();
551 let (chain, _) = scopes.chain_of(Scopes::SHARED_LENGTH);
552 let mut shorter = ScopeSet::default();
553 shorter.add_prefix(&Scopes::prefix_of(&chain));
554 chain.push(scopes.allocator.fresh());
555 let mut longer = ScopeSet::default();
556 longer.add_prefix(&Scopes::prefix_of(&chain));
557 assert!(shorter.is_subset_of(&longer));
558 assert!(!longer.is_subset_of(&shorter));
559 assert_ne!(shorter, longer);
560 }
561
562 #[test]
563 fn a_prefix_of_another_chain_is_not_a_subset() {
564 let mut scopes = Scopes::new();
565 let (first, _) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
566 let (second, _) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
567 assert!(!second.is_subset_of(&first));
568 }
569
570 #[test]
571 fn a_scope_between_a_prefixs_scopes_is_not_in_the_set() {
572 let mut scopes = Scopes::new();
573 let chain = ScopeChain::default();
574 chain.push(scopes.allocator.fresh());
575 let between = scopes.allocator.fresh();
576 (1..Scopes::SHARED_LENGTH).for_each(|_| chain.push(scopes.allocator.fresh()));
577 let mut set = ScopeSet::default();
578 set.add_prefix(&Scopes::prefix_of(&chain));
579 assert!(!set.contains(between));
580 }
581
582 #[test]
583 fn sets_sharing_prefixes_of_different_chains_differ() {
584 let mut scopes = Scopes::new();
585 let (first, _) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
586 let (second, _) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
587 assert_ne!(first, second);
588 }
589
590 #[test]
591 fn a_set_sharing_two_prefixes_contains_the_scopes_of_each() {
592 let mut scopes = Scopes::new();
593 let (mut set, older) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
594 let (newer_chain, newer) = scopes.chain_of(Scopes::SHARED_LENGTH);
595 set.add_prefix(&Scopes::prefix_of(&newer_chain));
596 assert!(set.contains(older[0]));
597 assert!(set.contains(newer[0]));
598 }
599
600 #[test]
601 fn a_set_sharing_two_prefixes_has_the_newer_prefix_largest() {
602 let mut scopes = Scopes::new();
603 let (mut set, _) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
604 let (newer_chain, newer) = scopes.chain_of(Scopes::SHARED_LENGTH);
605 set.add_prefix(&Scopes::prefix_of(&newer_chain));
606 assert_eq!(set.largest(), newer.last().copied());
607 }
608
609 #[test]
610 fn an_own_scope_beside_a_prefix_keeps_the_set_from_being_a_subset_of_the_prefix() {
611 let mut scopes = Scopes::new();
612 let (chain, _) = scopes.chain_of(Scopes::SHARED_LENGTH);
613 let mut prefix_alone = ScopeSet::default();
614 prefix_alone.add_prefix(&Scopes::prefix_of(&chain));
615 let mut with_own_scope = prefix_alone.clone();
616 with_own_scope.add(scopes.allocator.fresh());
617 assert!(!with_own_scope.is_subset_of(&prefix_alone));
618 }
619
620 #[test]
621 fn adding_a_shared_scope_keeps_the_set() {
622 let (mut set, scopes) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
623 set.add(scopes[0]);
624 assert!(set.own().is_empty());
625 assert_eq!(set.len(), scopes.len());
626 }
627
628 #[test]
629 fn a_prefix_older_than_the_set_adds_its_scopes_one_by_one() {
630 let mut scopes = Scopes::new();
631 let (chain, shared) = scopes.chain_of(Scopes::SHARED_LENGTH);
632 let newer = scopes.allocator.fresh();
633 let mut set = Scopes::added_one_by_one(&[newer]);
634 set.add_prefix(&Scopes::prefix_of(&chain));
635 let expected: Vec<Scope> = shared.into_iter().chain([newer]).collect();
636 assert_eq!(set.own(), expected);
637 }
638
639 #[test]
640 fn removing_an_absent_scope_keeps_the_set() {
641 let mut scopes = Scopes::new();
642 let (mut set, _) = scopes.set_of(2);
643 let original = set.clone();
644 let (_, absent) = scopes.set_of(1);
645 set.remove(absent[0]);
646 assert_eq!(set, original);
647 }
648
649 #[test]
650 fn removing_a_shared_scope_keeps_the_others() {
651 let (mut set, scopes) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
652 set.remove(scopes[0]);
653 assert_eq!(set.iter().collect::<Vec<_>>(), scopes[1..]);
654 }
655
656 #[test]
657 fn flipping_a_shared_scope_keeps_the_others() {
658 let (mut set, scopes) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
659 set.flip(scopes[0]);
660 assert_eq!(set.iter().collect::<Vec<_>>(), scopes[1..]);
661 }
662
663 #[test]
664 fn retaining_keeps_or_drops_a_whole_prefix_without_copying_it() {
665 let mut scopes = Scopes::new();
666 let (mut kept, _) = scopes.shared_set_of(Scopes::SHARED_LENGTH);
667 let (dropped_chain, dropped) = scopes.chain_of(Scopes::SHARED_LENGTH);
668 kept.add_prefix(&Scopes::prefix_of(&dropped_chain));
669 kept.retain(|scope| !dropped.contains(&scope));
670 assert!(kept.own().is_empty());
671 assert_eq!(kept.len(), Scopes::SHARED_LENGTH);
672 }
673
674 #[test]
675 fn retaining_none_of_a_prefix_leaves_the_set_plain() {
676 let (mut set, _) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
677 set.retain(|_| false);
678 assert!(set.is_plain());
679 assert_eq!(set.len(), 0);
680 }
681
682 #[test]
683 fn retaining_part_of_a_prefix_keeps_the_chosen_scopes() {
684 let (mut set, mut scopes) = Scopes::new().shared_set_of(Scopes::SHARED_LENGTH);
685 let removed = scopes.remove(1);
686 set.retain(|scope| scope != removed);
687 assert_eq!(set.iter().collect::<Vec<_>>(), scopes);
688 }
689
690 #[test]
691 fn a_short_prefix_is_added_scope_by_scope() {
692 let (set, scopes) = Scopes::new().shared_set_of(ScopeSet::SHORTEST_SHARED_PREFIX - 1);
693 assert_eq!(set.own(), scopes);
694 }
695}