Decouple SCC annotations from SCCs

This rewires SCC annotations to have them be a separate,
visitor-type data structure. It was broken out of #130227,
which needed them to be able to remove unused annotations
after computation without recomputing the SCCs themselves.

As a drive-by it also removes some redundant code from
the hot loop in SCC construction for a performance improvement.

2 files changed, 172 insertions, 138 deletions

diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs
index e7c4ea3daae..c0fe9e8ff93 100644
--- a/compiler/rustc_data_structures/src/graph/scc/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs
@@ -13,7 +13,7 @@ use std::fmt::Debug;
 use std::ops::Range;
 
 use rustc_index::{Idx, IndexSlice, IndexVec};
-use tracing::{debug, instrument};
+use tracing::{debug, instrument, trace};
 
 use crate::fx::FxHashSet;
 use crate::graph::vec_graph::VecGraph;
@@ -48,6 +48,20 @@ pub trait Annotation: Debug + Copy {
     }
 }
 
+/// An accumulator for annotations.
+pub trait Annotations<N: Idx, S: Idx, A: Annotation> {
+    fn new(&self, element: N) -> A;
+    fn annotate_scc(&mut self, scc: S, annotation: A);
+}
+
+/// The nil annotation accumulator, which does nothing.
+impl<N: Idx, S: Idx> Annotations<N, S, ()> for () {
+    fn new(&self, _element: N) -> () {
+        ()
+    }
+    fn annotate_scc(&mut self, _scc: S, _annotation: ()) {}
+}
+
 /// The empty annotation, which does nothing.
 impl Annotation for () {
     fn merge_reached(self, _other: Self) -> Self {
@@ -62,23 +76,20 @@ impl Annotation for () {
 /// the index type for the graph nodes and `S` is the index type for
 /// the SCCs. We can map from each node to the SCC that it
 /// participates in, and we also have the successors of each SCC.
-pub struct Sccs<N: Idx, S: Idx, A: Annotation = ()> {
+pub struct Sccs<N: Idx, S: Idx> {
     /// For each node, what is the SCC index of the SCC to which it
     /// belongs.
     scc_indices: IndexVec<N, S>,
 
     /// Data about all the SCCs.
-    scc_data: SccData<S, A>,
+    scc_data: SccData<S>,
 }
 
 /// Information about an invidividual SCC node.
-struct SccDetails<A: Annotation> {
+struct SccDetails {
     /// For this SCC, the range of `all_successors` where its
     /// successors can be found.
     range: Range<usize>,
-
-    /// User-specified metadata about the SCC.
-    annotation: A,
 }
 
 // The name of this struct should discourage you from making it public and leaking
@@ -87,10 +98,10 @@ struct SccDetails<A: Annotation> {
 // is difficult when it's publicly inspectable.
 //
 // Obey the law of Demeter!
-struct SccData<S: Idx, A: Annotation> {
+struct SccData<S: Idx> {
     /// Maps SCC indices to their metadata, including
     /// offsets into `all_successors`.
-    scc_details: IndexVec<S, SccDetails<A>>,
+    scc_details: IndexVec<S, SccDetails>,
 
     /// Contains the successors for all the Sccs, concatenated. The
     /// range of indices corresponding to a given SCC is found in its
@@ -98,24 +109,18 @@ struct SccData<S: Idx, A: Annotation> {
     all_successors: Vec<S>,
 }
 
-impl<N: Idx, S: Idx + Ord> Sccs<N, S, ()> {
+impl<N: Idx, S: Idx + Ord> Sccs<N, S> {
     /// Compute SCCs without annotations.
     pub fn new(graph: &impl Successors<Node = N>) -> Self {
-        Self::new_with_annotation(graph, |_| ())
+        Self::new_with_annotation(graph, &mut ())
     }
-}
 
-impl<N: Idx, S: Idx + Ord, A: Annotation> Sccs<N, S, A> {
     /// Compute SCCs and annotate them with a user-supplied annotation
-    pub fn new_with_annotation<F: Fn(N) -> A>(
+    pub fn new_with_annotation<A: Annotation, AA: Annotations<N, S, A>>(
         graph: &impl Successors<Node = N>,
-        to_annotation: F,
+        annotations: &mut AA,
     ) -> Self {
-        SccsConstruction::construct(graph, to_annotation)
-    }
-
-    pub fn annotation(&self, scc: S) -> A {
-        self.scc_data.annotation(scc)
+        SccsConstruction::construct(graph, annotations)
     }
 
     pub fn scc_indices(&self) -> &IndexSlice<N, S> {
@@ -136,7 +141,13 @@ impl<N: Idx, S: Idx + Ord, A: Annotation> Sccs<N, S, A> {
     pub fn all_sccs(&self) -> impl Iterator<Item = S> + 'static {
         (0..self.scc_data.len()).map(S::new)
     }
-
+    /*
+        /// Returns an iterator over the SCC annotations in the graph
+        /// The order is the same as `all_sccs()`, dependency order.
+        pub fn all_annotations(&self, annotations: &A) -> impl Iterator<Item = (S, A)> + use<'_, N, S, A> {
+            self.all_sccs().map(|scc| (scc, self.annotation(scc)))
+        }
+    */
     /// Returns the SCC to which a node `r` belongs.
     pub fn scc(&self, r: N) -> S {
         self.scc_indices[r]
@@ -160,7 +171,7 @@ impl<N: Idx, S: Idx + Ord, A: Annotation> Sccs<N, S, A> {
     }
 }
 
-impl<N: Idx, S: Idx + Ord, A: Annotation> DirectedGraph for Sccs<N, S, A> {
+impl<N: Idx, S: Idx + Ord> DirectedGraph for Sccs<N, S> {
     type Node = S;
 
     fn num_nodes(&self) -> usize {
@@ -168,19 +179,19 @@ impl<N: Idx, S: Idx + Ord, A: Annotation> DirectedGraph for Sccs<N, S, A> {
     }
 }
 
-impl<N: Idx, S: Idx + Ord, A: Annotation> NumEdges for Sccs<N, S, A> {
+impl<N: Idx, S: Idx + Ord> NumEdges for Sccs<N, S> {
     fn num_edges(&self) -> usize {
         self.scc_data.all_successors.len()
     }
 }
 
-impl<N: Idx, S: Idx + Ord, A: Annotation> Successors for Sccs<N, S, A> {
+impl<N: Idx, S: Idx + Ord> Successors for Sccs<N, S> {
     fn successors(&self, node: S) -> impl Iterator<Item = Self::Node> {
         self.successors(node).iter().cloned()
     }
 }
 
-impl<S: Idx, A: Annotation> SccData<S, A> {
+impl<S: Idx> SccData<S> {
     /// Number of SCCs,
     fn len(&self) -> usize {
         self.scc_details.len()
@@ -192,9 +203,8 @@ impl<S: Idx, A: Annotation> SccData<S, A> {
     }
 
     /// Creates a new SCC with `successors` as its successors and
-    /// the maximum weight of its internal nodes `scc_max_weight` and
     /// returns the resulting index.
-    fn create_scc(&mut self, successors: impl IntoIterator<Item = S>, annotation: A) -> S {
+    fn create_scc(&mut self, successors: impl IntoIterator<Item = S>) -> S {
         // Store the successors on `scc_successors_vec`, remembering
         // the range of indices.
         let all_successors_start = self.all_successors.len();
@@ -202,28 +212,23 @@ impl<S: Idx, A: Annotation> SccData<S, A> {
         let all_successors_end = self.all_successors.len();
 
         debug!(
-            "create_scc({:?}) successors={:?}, annotation={:?}",
+            "create_scc({:?}) successors={:?}",
             self.len(),
             &self.all_successors[all_successors_start..all_successors_end],
-            annotation
         );
 
         let range = all_successors_start..all_successors_end;
-        let metadata = SccDetails { range, annotation };
+        let metadata = SccDetails { range };
         self.scc_details.push(metadata)
     }
-
-    fn annotation(&self, scc: S) -> A {
-        self.scc_details[scc].annotation
-    }
 }
 
-struct SccsConstruction<'c, G, S, A, F>
+struct SccsConstruction<'c, 'a, G, S, A, AA>
 where
     G: DirectedGraph + Successors,
     S: Idx,
     A: Annotation,
-    F: Fn(G::Node) -> A,
+    AA: Annotations<G::Node, S, A>,
 {
     graph: &'c G,
 
@@ -247,11 +252,9 @@ where
     /// around between successors to amortize memory allocation costs.
     duplicate_set: FxHashSet<S>,
 
-    scc_data: SccData<S, A>,
+    scc_data: SccData<S>,
 
-    /// A function that constructs an initial SCC annotation
-    /// out of a single node.
-    to_annotation: F,
+    annotations: &'a mut AA,
 }
 
 #[derive(Copy, Clone, Debug)]
@@ -299,12 +302,12 @@ enum WalkReturn<S, A> {
     Complete { scc_index: S, annotation: A },
 }
 
-impl<'c, G, S, A, F> SccsConstruction<'c, G, S, A, F>
+impl<'c, 'a, G, S, A, AA> SccsConstruction<'c, 'a, G, S, A, AA>
 where
     G: DirectedGraph + Successors,
     S: Idx,
-    F: Fn(G::Node) -> A,
     A: Annotation,
+    AA: Annotations<G::Node, S, A>,
 {
     /// Identifies SCCs in the graph `G` and computes the resulting
     /// DAG. This uses a variant of [Tarjan's
@@ -320,7 +323,7 @@ where
     /// Additionally, we keep track of a current annotation of the SCC.
     ///
     /// [wikipedia]: https://bit.ly/2EZIx84
-    fn construct(graph: &'c G, to_annotation: F) -> Sccs<G::Node, S, A> {
+    fn construct(graph: &'c G, annotations: &'a mut AA) -> Sccs<G::Node, S> {
         let num_nodes = graph.num_nodes();
 
         let mut this = Self {
@@ -330,7 +333,7 @@ where
             successors_stack: Vec::new(),
             scc_data: SccData { scc_details: IndexVec::new(), all_successors: Vec::new() },
             duplicate_set: FxHashSet::default(),
-            to_annotation,
+            annotations,
         };
 
         let scc_indices = graph
@@ -408,7 +411,7 @@ where
         // a potentially derived version of the root state for non-root nodes in the chain.
         let (root_state, assigned_state) = {
             loop {
-                debug!("find_state(r = {node:?} in state {:?})", self.node_states[node]);
+                trace!("find_state(r = {node:?} in state {:?})", self.node_states[node]);
                 match self.node_states[node] {
                     // This must have been the first and only state since it is unexplored*;
                     // no update needed! * Unless there is a bug :')
@@ -482,7 +485,7 @@ where
             if previous_node == node {
                 return root_state;
             }
-            debug!("Compressing {node:?} down to {previous_node:?} with state {assigned_state:?}");
+            trace!("Compressing {node:?} down to {previous_node:?} with state {assigned_state:?}");
 
             // Update to previous node in the link.
             match self.node_states[previous_node] {
@@ -507,9 +510,9 @@ where
     /// Call this method when `inspect_node` has returned `None`. Having the
     /// caller decide avoids mutual recursion between the two methods and allows
     /// us to maintain an allocated stack for nodes on the path between calls.
-    #[instrument(skip(self, initial), level = "debug")]
+    #[instrument(skip(self, initial), level = "trace")]
     fn walk_unvisited_node(&mut self, initial: G::Node) -> WalkReturn<S, A> {
-        debug!("Walk unvisited node: {initial:?}");
+        trace!("Walk unvisited node: {initial:?}");
         struct VisitingNodeFrame<G: DirectedGraph, Successors, A> {
             node: G::Node,
             successors: Option<Successors>,
@@ -537,7 +540,7 @@ where
             successors_len: 0,
             min_cycle_root: initial,
             successor_node: initial,
-            current_component_annotation: (self.to_annotation)(initial),
+            current_component_annotation: self.annotations.new(initial),
         }];
 
         let mut return_value = None;
@@ -556,11 +559,7 @@ where
             let node = *node;
             let depth = *depth;
 
-            // node is definitely in the current component, add it to the annotation.
-            if node != initial {
-                current_component_annotation.update_scc((self.to_annotation)(node));
-            }
-            debug!(
+            trace!(
                 "Visiting {node:?} at depth {depth:?}, annotation: {current_component_annotation:?}"
             );
 
@@ -568,7 +567,7 @@ where
                 Some(successors) => successors,
                 None => {
                     // This None marks that we still have the initialize this node's frame.
-                    debug!(?depth, ?node);
+                    trace!(?depth, ?node);
 
                     debug_assert_matches!(self.node_states[node], NodeState::NotVisited);
 
@@ -598,7 +597,7 @@ where
                 return_value.take().into_iter().map(|walk| (*successor_node, Some(walk)));
 
             let successor_walk = successors.map(|successor_node| {
-                debug!(?node, ?successor_node);
+                trace!(?node, ?successor_node);
                 (successor_node, self.inspect_node(successor_node))
             });
             for (successor_node, walk) in returned_walk.chain(successor_walk) {
@@ -609,13 +608,13 @@ where
                         min_depth: successor_min_depth,
                         annotation: successor_annotation,
                     }) => {
-                        debug!(
+                        trace!(
                             "Cycle found from {node:?}, minimum depth: {successor_min_depth:?}, annotation: {successor_annotation:?}"
                         );
                         // Track the minimum depth we can reach.
                         assert!(successor_min_depth <= depth);
                         if successor_min_depth < *min_depth {
-                            debug!(?node, ?successor_min_depth);
+                            trace!(?node, ?successor_min_depth);
                             *min_depth = successor_min_depth;
                             *min_cycle_root = successor_node;
                         }
@@ -627,20 +626,20 @@ where
                         scc_index: successor_scc_index,
                         annotation: successor_annotation,
                     }) => {
-                        debug!(
+                        trace!(
                             "Complete; {node:?} is root of complete-visited SCC idx {successor_scc_index:?} with annotation {successor_annotation:?}"
                         );
                         // Push the completed SCC indices onto
                         // the `successors_stack` for later.
-                        debug!(?node, ?successor_scc_index);
+                        trace!(?node, ?successor_scc_index);
                         successors_stack.push(successor_scc_index);
                         current_component_annotation.update_reachable(successor_annotation);
                     }
                     // `node` has no more (direct) successors; search recursively.
                     None => {
                         let depth = depth + 1;
-                        debug!("Recursing down into {successor_node:?} at depth {depth:?}");
-                        debug!(?depth, ?successor_node);
+                        trace!("Recursing down into {successor_node:?} at depth {depth:?}");
+                        trace!(?depth, ?successor_node);
                         // Remember which node the return value will come from.
                         frame.successor_node = successor_node;
                         // Start a new stack frame, then step into it.
@@ -652,14 +651,14 @@ where
                             min_depth: depth,
                             min_cycle_root: successor_node,
                             successor_node,
-                            current_component_annotation: (self.to_annotation)(successor_node),
+                            current_component_annotation: self.annotations.new(successor_node),
                         });
                         continue 'recurse;
                     }
                 }
             }
 
-            debug!("Finished walk from {node:?} with annotation: {current_component_annotation:?}");
+            trace!("Finished walk from {node:?} with annotation: {current_component_annotation:?}");
 
             // Completed walk, remove `node` from the stack.
             let r = self.node_stack.pop();
@@ -691,8 +690,9 @@ where
 
                 debug!("Creating SCC rooted in {node:?} with successor {:?}", frame.successor_node);
 
-                let scc_index =
-                    self.scc_data.create_scc(deduplicated_successors, current_component_annotation);
+                let scc_index = self.scc_data.create_scc(deduplicated_successors);
+
+                self.annotations.annotate_scc(scc_index, current_component_annotation);
 
                 self.node_states[node] =
                     NodeState::InCycle { scc_index, annotation: current_component_annotation };
diff --git a/compiler/rustc_data_structures/src/graph/scc/tests.rs b/compiler/rustc_data_structures/src/graph/scc/tests.rs
index 373f87bfdbc..e388e7b6680 100644
--- a/compiler/rustc_data_structures/src/graph/scc/tests.rs
+++ b/compiler/rustc_data_structures/src/graph/scc/tests.rs
@@ -5,8 +5,28 @@ use crate::graph::tests::TestGraph;
 
 #[derive(Copy, Clone, Debug)]
 struct MaxReached(usize);
-type UsizeSccs = Sccs<usize, usize, ()>;
-type MaxReachedSccs = Sccs<usize, usize, MaxReached>;
+struct Maxes(IndexVec<usize, MaxReached>, fn(usize) -> usize);
+type UsizeSccs = Sccs<usize, usize>;
+
+impl Annotations<usize, usize, MaxReached> for Maxes {
+    fn new(&self, element: usize) -> MaxReached {
+        MaxReached(self.1(element))
+    }
+
+    fn annotate_scc(&mut self, scc: usize, annotation: MaxReached) {
+        let i = self.0.push(annotation);
+        assert!(i == scc);
+    }
+}
+
+impl Maxes {
+    fn annotation(&self, scc: usize) -> MaxReached {
+        self.0[scc]
+    }
+    fn new(mapping: fn(usize) -> usize) -> Self {
+        Self(IndexVec::new(), mapping)
+    }
+}
 
 impl Annotation for MaxReached {
     fn merge_scc(self, other: Self) -> Self {
@@ -14,7 +34,7 @@ impl Annotation for MaxReached {
     }
 
     fn merge_reached(self, other: Self) -> Self {
-        self.merge_scc(other)
+        Self(std::cmp::max(other.0, self.0))
     }
 }
 
@@ -24,17 +44,29 @@ impl PartialEq<usize> for MaxReached {
     }
 }
 
-impl MaxReached {
-    fn from_usize(nr: usize) -> Self {
-        Self(nr)
-    }
-}
-
 #[derive(Copy, Clone, Debug)]
 struct MinMaxIn {
     min: usize,
     max: usize,
 }
+struct MinMaxes(IndexVec<usize, MinMaxIn>, fn(usize) -> MinMaxIn);
+
+impl MinMaxes {
+    fn annotation(&self, scc: usize) -> MinMaxIn {
+        self.0[scc]
+    }
+}
+
+impl Annotations<usize, usize, MinMaxIn> for MinMaxes {
+    fn new(&self, element: usize) -> MinMaxIn {
+        self.1(element)
+    }
+
+    fn annotate_scc(&mut self, scc: usize, annotation: MinMaxIn) {
+        let i = self.0.push(annotation);
+        assert!(i == scc);
+    }
+}
 
 impl Annotation for MinMaxIn {
     fn merge_scc(self, other: Self) -> Self {
@@ -261,67 +293,68 @@ fn bench_sccc(b: &mut test::Bencher) {
 #[test]
 fn test_max_self_loop() {
     let graph = TestGraph::new(0, &[(0, 0)]);
-    let sccs: MaxReachedSccs =
-        Sccs::new_with_annotation(&graph, |n| if n == 0 { MaxReached(17) } else { MaxReached(0) });
-    assert_eq!(sccs.annotation(0), 17);
+    let mut annotations = Maxes(IndexVec::new(), |n| if n == 0 { 17 } else { 0 });
+    Sccs::new_with_annotation(&graph, &mut annotations);
+    assert_eq!(annotations.0[0], 17);
 }
 
 #[test]
 fn test_max_branch() {
     let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 4)]);
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, MaxReached::from_usize);
-    assert_eq!(sccs.annotation(sccs.scc(0)), 4);
-    assert_eq!(sccs.annotation(sccs.scc(1)), 3);
-    assert_eq!(sccs.annotation(sccs.scc(2)), 4);
+    let mut annotations = Maxes(IndexVec::new(), |n| n);
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+    assert_eq!(annotations.0[sccs.scc(0)], 4);
+    assert_eq!(annotations.0[sccs.scc(1)], 3);
+    assert_eq!(annotations.0[sccs.scc(2)], 4);
 }
+
 #[test]
 fn test_single_cycle_max() {
     let graph = TestGraph::new(0, &[(0, 2), (2, 3), (2, 4), (4, 1), (1, 2)]);
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, MaxReached::from_usize);
-    assert_eq!(sccs.annotation(sccs.scc(2)), 4);
-    assert_eq!(sccs.annotation(sccs.scc(0)), 4);
-}
-
-#[test]
-fn test_simple_cycle_max() {
-    let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 0)]);
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, MaxReached::from_usize);
-    assert_eq!(sccs.num_sccs(), 1);
+    let mut annotations = Maxes(IndexVec::new(), |n| n);
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+    assert_eq!(annotations.0[sccs.scc(2)], 4);
+    assert_eq!(annotations.0[sccs.scc(0)], 4);
 }
 
 #[test]
 fn test_double_cycle_max() {
     let graph =
         TestGraph::new(0, &[(0, 1), (1, 2), (1, 4), (2, 3), (2, 4), (3, 5), (4, 1), (5, 4)]);
-    let sccs: MaxReachedSccs =
-        Sccs::new_with_annotation(&graph, |n| if n == 5 { MaxReached(2) } else { MaxReached(1) });
+    let mut annotations = Maxes(IndexVec::new(), |n| if n == 5 { 2 } else { 1 });
 
-    assert_eq!(sccs.annotation(sccs.scc(0)).0, 2);
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+
+    assert_eq!(annotations.0[sccs.scc(0)].0, 2);
 }
 
 #[test]
 fn test_bug_minimised() {
     let graph = TestGraph::new(0, &[(0, 3), (0, 1), (3, 2), (2, 3), (1, 4), (4, 5), (5, 4)]);
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |n| match n {
-        3 => MaxReached(1),
-        _ => MaxReached(0),
+    let mut annotations = Maxes(IndexVec::new(), |n| match n {
+        3 => 1,
+        _ => 0,
     });
-    assert_eq!(sccs.annotation(sccs.scc(2)), 1);
-    assert_eq!(sccs.annotation(sccs.scc(1)), 0);
-    assert_eq!(sccs.annotation(sccs.scc(4)), 0);
+
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+    assert_eq!(annotations.annotation(sccs.scc(2)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(1)), 0);
+    assert_eq!(annotations.annotation(sccs.scc(4)), 0);
 }
 
 #[test]
 fn test_bug_max_leak_minimised() {
     let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (3, 0), (3, 4), (4, 3)]);
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
-        4 => MaxReached(1),
-        _ => MaxReached(0),
+    let mut annotations = Maxes(IndexVec::new(), |w| match w {
+        4 => 1,
+        _ => 0,
     });
 
-    assert_eq!(sccs.annotation(sccs.scc(2)), 0);
-    assert_eq!(sccs.annotation(sccs.scc(3)), 1);
-    assert_eq!(sccs.annotation(sccs.scc(0)), 1);
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+
+    assert_eq!(annotations.annotation(sccs.scc(2)), 0);
+    assert_eq!(annotations.annotation(sccs.scc(3)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(0)), 1);
 }
 
 #[test]
@@ -369,48 +402,49 @@ fn test_bug_max_leak() {
             (23, 24),
         ],
     );
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
-        22 => MaxReached(1),
-        24 => MaxReached(2),
-        27 => MaxReached(2),
-        _ => MaxReached(0),
+    let mut annotations = Maxes::new(|w| match w {
+        22 => 1,
+        24 => 2,
+        27 => 2,
+        _ => 0,
     });
-
-    assert_eq!(sccs.annotation(sccs.scc(2)), 0);
-    assert_eq!(sccs.annotation(sccs.scc(7)), 0);
-    assert_eq!(sccs.annotation(sccs.scc(8)), 2);
-    assert_eq!(sccs.annotation(sccs.scc(23)), 2);
-    assert_eq!(sccs.annotation(sccs.scc(3)), 2);
-    assert_eq!(sccs.annotation(sccs.scc(0)), 2);
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+
+    assert_eq!(annotations.annotation(sccs.scc(2)), 0);
+    assert_eq!(annotations.annotation(sccs.scc(7)), 0);
+    assert_eq!(annotations.annotation(sccs.scc(8)), 2);
+    assert_eq!(annotations.annotation(sccs.scc(23)), 2);
+    assert_eq!(annotations.annotation(sccs.scc(3)), 2);
+    assert_eq!(annotations.annotation(sccs.scc(0)), 2);
 }
 
 #[test]
 fn test_bug_max_zero_stick_shape() {
     let graph = TestGraph::new(0, &[(0, 1), (1, 2), (2, 3), (3, 2), (3, 4)]);
-
-    let sccs: MaxReachedSccs = Sccs::new_with_annotation(&graph, |w| match w {
-        4 => MaxReached(1),
-        _ => MaxReached(0),
+    let mut annotations = Maxes::new(|w| match w {
+        4 => 1,
+        _ => 0,
     });
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
 
-    assert_eq!(sccs.annotation(sccs.scc(0)), 1);
-    assert_eq!(sccs.annotation(sccs.scc(1)), 1);
-    assert_eq!(sccs.annotation(sccs.scc(2)), 1);
-    assert_eq!(sccs.annotation(sccs.scc(3)), 1);
-    assert_eq!(sccs.annotation(sccs.scc(4)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(0)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(1)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(2)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(3)), 1);
+    assert_eq!(annotations.annotation(sccs.scc(4)), 1);
 }
 
 #[test]
 fn test_min_max_in() {
     let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (3, 0), (3, 4), (4, 3), (3, 5)]);
-    let sccs: Sccs<usize, usize, MinMaxIn> =
-        Sccs::new_with_annotation(&graph, |w| MinMaxIn { min: w, max: w });
-
-    assert_eq!(sccs.annotation(sccs.scc(2)).min, 2);
-    assert_eq!(sccs.annotation(sccs.scc(2)).max, 2);
-    assert_eq!(sccs.annotation(sccs.scc(0)).min, 0);
-    assert_eq!(sccs.annotation(sccs.scc(0)).max, 4);
-    assert_eq!(sccs.annotation(sccs.scc(3)).min, 0);
-    assert_eq!(sccs.annotation(sccs.scc(3)).max, 4);
-    assert_eq!(sccs.annotation(sccs.scc(5)).min, 5);
+    let mut annotations = MinMaxes(IndexVec::new(), |w| MinMaxIn { min: w, max: w });
+    let sccs = Sccs::new_with_annotation(&graph, &mut annotations);
+
+    assert_eq!(annotations.annotation(sccs.scc(2)).min, 2);
+    assert_eq!(annotations.annotation(sccs.scc(2)).max, 2);
+    assert_eq!(annotations.annotation(sccs.scc(0)).min, 0);
+    assert_eq!(annotations.annotation(sccs.scc(0)).max, 4);
+    assert_eq!(annotations.annotation(sccs.scc(3)).min, 0);
+    assert_eq!(annotations.annotation(sccs.scc(3)).max, 4);
+    assert_eq!(annotations.annotation(sccs.scc(5)).min, 5);
 }