jj_lib/
graph.rs

1// Copyright 2021-2023 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![allow(missing_docs)]
16
17use std::collections::HashMap;
18use std::collections::HashSet;
19use std::collections::VecDeque;
20use std::hash::Hash;
21
22/// Node and edges pair of type `N` and `ID` respectively.
23///
24/// `ID` uniquely identifies a node within the graph. It's usually cheap to
25/// clone. There should be a pure `(&N) -> &ID` function.
26pub type GraphNode<N, ID = N> = (N, Vec<GraphEdge<ID>>);
27
28#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
29pub struct GraphEdge<N> {
30    pub target: N,
31    pub edge_type: GraphEdgeType,
32}
33
34impl<N> GraphEdge<N> {
35    pub fn missing(target: N) -> Self {
36        Self {
37            target,
38            edge_type: GraphEdgeType::Missing,
39        }
40    }
41
42    pub fn direct(target: N) -> Self {
43        Self {
44            target,
45            edge_type: GraphEdgeType::Direct,
46        }
47    }
48
49    pub fn indirect(target: N) -> Self {
50        Self {
51            target,
52            edge_type: GraphEdgeType::Indirect,
53        }
54    }
55
56    pub fn map<M>(self, f: impl FnOnce(N) -> M) -> GraphEdge<M> {
57        GraphEdge {
58            target: f(self.target),
59            edge_type: self.edge_type,
60        }
61    }
62}
63
64#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
65pub enum GraphEdgeType {
66    Missing,
67    Direct,
68    Indirect,
69}
70
71fn reachable_targets<N>(edges: &[GraphEdge<N>]) -> impl DoubleEndedIterator<Item = &N> {
72    edges
73        .iter()
74        .filter(|edge| edge.edge_type != GraphEdgeType::Missing)
75        .map(|edge| &edge.target)
76}
77
78/// Creates new graph in which nodes and edges are reversed.
79pub fn reverse_graph<N, ID: Clone + Eq + Hash, E>(
80    input: impl Iterator<Item = Result<GraphNode<N, ID>, E>>,
81    as_id: impl Fn(&N) -> &ID,
82) -> Result<Vec<GraphNode<N, ID>>, E> {
83    let mut entries = vec![];
84    let mut reverse_edges: HashMap<ID, Vec<GraphEdge<ID>>> = HashMap::new();
85    for item in input {
86        let (node, edges) = item?;
87        for GraphEdge { target, edge_type } in edges {
88            reverse_edges.entry(target).or_default().push(GraphEdge {
89                target: as_id(&node).clone(),
90                edge_type,
91            });
92        }
93        entries.push(node);
94    }
95
96    let mut items = vec![];
97    for node in entries.into_iter().rev() {
98        let edges = reverse_edges.remove(as_id(&node)).unwrap_or_default();
99        items.push((node, edges));
100    }
101    Ok(items)
102}
103
104/// Graph iterator adapter to group topological branches.
105///
106/// Basic idea is DFS from the heads. At fork point, the other descendant
107/// branches will be visited. At merge point, the second (or the last) ancestor
108/// branch will be visited first. This is practically [the same as Git][Git].
109///
110/// If no branches are prioritized, the branch containing the first commit in
111/// the input iterator will be emitted first. It is often the working-copy
112/// ancestor branch. The other head branches won't be enqueued eagerly, and will
113/// be emitted as late as possible.
114///
115/// [Git]: https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting
116#[derive(Clone, Debug)]
117pub struct TopoGroupedGraphIterator<N, I> {
118    input_iter: I,
119    /// Graph nodes read from the input iterator but not yet emitted.
120    nodes: HashMap<N, TopoGroupedGraphNode<N>>,
121    /// Stack of graph nodes to be emitted.
122    emittable_ids: Vec<N>,
123    /// List of new head nodes found while processing unpopulated nodes, or
124    /// prioritized branch nodes added by caller.
125    new_head_ids: VecDeque<N>,
126    /// Set of nodes which may be ancestors of `new_head_ids`.
127    blocked_ids: HashSet<N>,
128}
129
130#[derive(Clone, Debug)]
131struct TopoGroupedGraphNode<N> {
132    /// Graph nodes which must be emitted before.
133    child_ids: HashSet<N>,
134    /// Graph edges to parent nodes. `None` until this node is populated.
135    edges: Option<Vec<GraphEdge<N>>>,
136}
137
138impl<N> Default for TopoGroupedGraphNode<N> {
139    fn default() -> Self {
140        Self {
141            child_ids: Default::default(),
142            edges: None,
143        }
144    }
145}
146
147impl<N, E, I> TopoGroupedGraphIterator<N, I>
148where
149    N: Clone + Hash + Eq,
150    I: Iterator<Item = Result<GraphNode<N>, E>>,
151{
152    /// Wraps the given iterator to group topological branches. The input
153    /// iterator must be topologically ordered.
154    pub fn new(input_iter: I) -> Self {
155        TopoGroupedGraphIterator {
156            input_iter,
157            nodes: HashMap::new(),
158            emittable_ids: Vec::new(),
159            new_head_ids: VecDeque::new(),
160            blocked_ids: HashSet::new(),
161        }
162    }
163
164    /// Makes the branch containing the specified node be emitted earlier than
165    /// the others.
166    ///
167    /// The `id` usually points to a head node, but this isn't a requirement.
168    /// If the specified node isn't a head, all preceding nodes will be queued.
169    ///
170    /// The specified node must exist in the input iterator. If it didn't, the
171    /// iterator would panic.
172    pub fn prioritize_branch(&mut self, id: N) {
173        // Mark existence of unpopulated node
174        self.nodes.entry(id.clone()).or_default();
175        // Push to non-emitting list so the prioritized heads wouldn't be
176        // interleaved
177        self.new_head_ids.push_back(id);
178    }
179
180    fn populate_one(&mut self) -> Result<Option<()>, E> {
181        let (current_id, edges) = match self.input_iter.next() {
182            Some(Ok(data)) => data,
183            Some(Err(err)) => {
184                return Err(err);
185            }
186            None => {
187                return Ok(None);
188            }
189        };
190
191        // Set up reverse reference
192        for parent_id in reachable_targets(&edges) {
193            let parent_node = self.nodes.entry(parent_id.clone()).or_default();
194            parent_node.child_ids.insert(current_id.clone());
195        }
196
197        // Populate the current node
198        if let Some(current_node) = self.nodes.get_mut(&current_id) {
199            assert!(current_node.edges.is_none());
200            current_node.edges = Some(edges);
201        } else {
202            let current_node = TopoGroupedGraphNode {
203                edges: Some(edges),
204                ..Default::default()
205            };
206            self.nodes.insert(current_id.clone(), current_node);
207            // Push to non-emitting list so the new head wouldn't be interleaved
208            self.new_head_ids.push_back(current_id);
209        }
210
211        Ok(Some(()))
212    }
213
214    /// Enqueues the first new head which will unblock the waiting ancestors.
215    ///
216    /// This does not move multiple head nodes to the queue at once because
217    /// heads may be connected to the fork points in arbitrary order.
218    fn flush_new_head(&mut self) {
219        assert!(!self.new_head_ids.is_empty());
220        if self.blocked_ids.is_empty() || self.new_head_ids.len() <= 1 {
221            // Fast path: orphaned or no choice
222            let new_head_id = self.new_head_ids.pop_front().unwrap();
223            self.emittable_ids.push(new_head_id);
224            self.blocked_ids.clear();
225            return;
226        }
227
228        // Mark descendant nodes reachable from the blocking nodes
229        let mut to_visit: Vec<&N> = self
230            .blocked_ids
231            .iter()
232            .map(|id| {
233                // Borrow from self.nodes so self.blocked_ids can be mutated later
234                let (id, _) = self.nodes.get_key_value(id).unwrap();
235                id
236            })
237            .collect();
238        let mut visited: HashSet<&N> = to_visit.iter().copied().collect();
239        while let Some(id) = to_visit.pop() {
240            let node = self.nodes.get(id).unwrap();
241            to_visit.extend(node.child_ids.iter().filter(|id| visited.insert(id)));
242        }
243
244        // Pick the first reachable head
245        let index = self
246            .new_head_ids
247            .iter()
248            .position(|id| visited.contains(id))
249            .expect("blocking head should exist");
250        let new_head_id = self.new_head_ids.remove(index).unwrap();
251
252        // Unmark ancestors of the selected head so they won't contribute to future
253        // new-head resolution within the newly-unblocked sub graph. The sub graph
254        // can have many fork points, and the corresponding heads should be picked in
255        // the fork-point order, not in the head appearance order.
256        to_visit.push(&new_head_id);
257        visited.remove(&new_head_id);
258        while let Some(id) = to_visit.pop() {
259            let node = self.nodes.get(id).unwrap();
260            if let Some(edges) = &node.edges {
261                to_visit.extend(reachable_targets(edges).filter(|id| visited.remove(id)));
262            }
263        }
264        self.blocked_ids.retain(|id| visited.contains(id));
265        self.emittable_ids.push(new_head_id);
266    }
267
268    fn next_node(&mut self) -> Result<Option<GraphNode<N>>, E> {
269        // Based on Kahn's algorithm
270        loop {
271            if let Some(current_id) = self.emittable_ids.last() {
272                let Some(current_node) = self.nodes.get_mut(current_id) else {
273                    // Queued twice because new children populated and emitted
274                    self.emittable_ids.pop().unwrap();
275                    continue;
276                };
277                if !current_node.child_ids.is_empty() {
278                    // New children populated after emitting the other
279                    let current_id = self.emittable_ids.pop().unwrap();
280                    self.blocked_ids.insert(current_id);
281                    continue;
282                }
283                let Some(edges) = current_node.edges.take() else {
284                    // Not yet populated
285                    self.populate_one()?
286                        .expect("parent or prioritized node should exist");
287                    continue;
288                };
289                // The second (or the last) parent will be visited first
290                let current_id = self.emittable_ids.pop().unwrap();
291                self.nodes.remove(&current_id).unwrap();
292                for parent_id in reachable_targets(&edges) {
293                    let parent_node = self.nodes.get_mut(parent_id).unwrap();
294                    parent_node.child_ids.remove(&current_id);
295                    if parent_node.child_ids.is_empty() {
296                        let reusable_id = self.blocked_ids.take(parent_id);
297                        let parent_id = reusable_id.unwrap_or_else(|| parent_id.clone());
298                        self.emittable_ids.push(parent_id);
299                    } else {
300                        self.blocked_ids.insert(parent_id.clone());
301                    }
302                }
303                return Ok(Some((current_id, edges)));
304            } else if !self.new_head_ids.is_empty() {
305                self.flush_new_head();
306            } else {
307                // Populate the first or orphan head
308                if self.populate_one()?.is_none() {
309                    return Ok(None);
310                }
311            }
312        }
313    }
314}
315
316impl<N, E, I> Iterator for TopoGroupedGraphIterator<N, I>
317where
318    N: Clone + Hash + Eq,
319    I: Iterator<Item = Result<GraphNode<N>, E>>,
320{
321    type Item = Result<GraphNode<N>, E>;
322
323    fn next(&mut self) -> Option<Self::Item> {
324        match self.next_node() {
325            Ok(Some(node)) => Some(Ok(node)),
326            Ok(None) => {
327                assert!(self.nodes.is_empty(), "all nodes should have been emitted");
328                None
329            }
330            Err(err) => Some(Err(err)),
331        }
332    }
333}
334
335#[cfg(test)]
336mod tests {
337    use std::convert::Infallible;
338
339    use itertools::Itertools as _;
340    use renderdag::Ancestor;
341    use renderdag::GraphRowRenderer;
342    use renderdag::Renderer as _;
343
344    use super::*;
345
346    fn missing(c: char) -> GraphEdge<char> {
347        GraphEdge::missing(c)
348    }
349
350    fn direct(c: char) -> GraphEdge<char> {
351        GraphEdge::direct(c)
352    }
353
354    fn indirect(c: char) -> GraphEdge<char> {
355        GraphEdge::indirect(c)
356    }
357
358    fn format_edge(edge: &GraphEdge<char>) -> String {
359        let c = edge.target;
360        match edge.edge_type {
361            GraphEdgeType::Missing => format!("missing({c})"),
362            GraphEdgeType::Direct => format!("direct({c})"),
363            GraphEdgeType::Indirect => format!("indirect({c})"),
364        }
365    }
366
367    fn format_graph(
368        graph_iter: impl IntoIterator<Item = Result<GraphNode<char>, Infallible>>,
369    ) -> String {
370        let mut renderer = GraphRowRenderer::new()
371            .output()
372            .with_min_row_height(2)
373            .build_box_drawing();
374        graph_iter
375            .into_iter()
376            .map(|item| match item {
377                Ok(node) => node,
378                Err(err) => match err {},
379            })
380            .map(|(id, edges)| {
381                let glyph = id.to_string();
382                let message = edges.iter().map(format_edge).join(", ");
383                let parents = edges
384                    .into_iter()
385                    .map(|edge| match edge.edge_type {
386                        GraphEdgeType::Missing => Ancestor::Anonymous,
387                        GraphEdgeType::Direct => Ancestor::Parent(edge.target),
388                        GraphEdgeType::Indirect => Ancestor::Ancestor(edge.target),
389                    })
390                    .collect();
391                renderer.next_row(id, parents, glyph, message)
392            })
393            .collect()
394    }
395
396    #[test]
397    fn test_format_graph() {
398        let graph = [
399            ('D', vec![direct('C'), indirect('B')]),
400            ('C', vec![direct('A')]),
401            ('B', vec![missing('X')]),
402            ('A', vec![]),
403        ]
404        .map(Ok);
405        insta::assert_snapshot!(format_graph(graph), @r"
406        D    direct(C), indirect(B)
407        ├─╮
408        C ╷  direct(A)
409        │ ╷
410        │ B  missing(X)
411        │ │
412        │ ~
413        │
414        A
415        ");
416    }
417
418    fn topo_grouped<I, E>(graph_iter: I) -> TopoGroupedGraphIterator<char, I::IntoIter>
419    where
420        I: IntoIterator<Item = Result<GraphNode<char>, E>>,
421    {
422        TopoGroupedGraphIterator::new(graph_iter.into_iter())
423    }
424
425    #[test]
426    fn test_topo_grouped_multiple_roots() {
427        let graph = [
428            ('C', vec![missing('Y')]),
429            ('B', vec![missing('X')]),
430            ('A', vec![]),
431        ]
432        .map(Ok);
433        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
434        C  missing(Y)
435        │
436        ~
437
438        B  missing(X)
439        │
440        ~
441
442        A
443        ");
444        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
445        C  missing(Y)
446        │
447        ~
448
449        B  missing(X)
450        │
451        ~
452
453        A
454        ");
455
456        // All nodes can be lazily emitted.
457        let mut iter = topo_grouped(graph.iter().cloned().peekable());
458        assert_eq!(iter.next().unwrap().unwrap().0, 'C');
459        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'B');
460        assert_eq!(iter.next().unwrap().unwrap().0, 'B');
461        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'A');
462    }
463
464    #[test]
465    fn test_topo_grouped_trivial_fork() {
466        let graph = [
467            ('E', vec![direct('B')]),
468            ('D', vec![direct('A')]),
469            ('C', vec![direct('B')]),
470            ('B', vec![direct('A')]),
471            ('A', vec![]),
472        ]
473        .map(Ok);
474        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
475        E  direct(B)
476        │
477        │ D  direct(A)
478        │ │
479        │ │ C  direct(B)
480        ├───╯
481        B │  direct(A)
482        ├─╯
483        A
484        ");
485        // D-A is found earlier than B-A, but B is emitted first because it belongs to
486        // the emitting branch.
487        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
488        E  direct(B)
489        │
490        │ C  direct(B)
491        ├─╯
492        B  direct(A)
493        │
494        │ D  direct(A)
495        ├─╯
496        A
497        ");
498
499        // E can be lazy, then D and C will be queued.
500        let mut iter = topo_grouped(graph.iter().cloned().peekable());
501        assert_eq!(iter.next().unwrap().unwrap().0, 'E');
502        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'D');
503        assert_eq!(iter.next().unwrap().unwrap().0, 'C');
504        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'B');
505        assert_eq!(iter.next().unwrap().unwrap().0, 'B');
506        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'A');
507    }
508
509    #[test]
510    fn test_topo_grouped_fork_interleaved() {
511        let graph = [
512            ('F', vec![direct('D')]),
513            ('E', vec![direct('C')]),
514            ('D', vec![direct('B')]),
515            ('C', vec![direct('B')]),
516            ('B', vec![direct('A')]),
517            ('A', vec![]),
518        ]
519        .map(Ok);
520        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
521        F  direct(D)
522        │
523        │ E  direct(C)
524        │ │
525        D │  direct(B)
526        │ │
527        │ C  direct(B)
528        ├─╯
529        B  direct(A)
530        │
531        A
532        ");
533        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
534        F  direct(D)
535        │
536        D  direct(B)
537        │
538        │ E  direct(C)
539        │ │
540        │ C  direct(B)
541        ├─╯
542        B  direct(A)
543        │
544        A
545        ");
546
547        // F can be lazy, then E will be queued, then C.
548        let mut iter = topo_grouped(graph.iter().cloned().peekable());
549        assert_eq!(iter.next().unwrap().unwrap().0, 'F');
550        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'E');
551        assert_eq!(iter.next().unwrap().unwrap().0, 'D');
552        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'C');
553        assert_eq!(iter.next().unwrap().unwrap().0, 'E');
554        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'B');
555    }
556
557    #[test]
558    fn test_topo_grouped_fork_multiple_heads() {
559        let graph = [
560            ('I', vec![direct('E')]),
561            ('H', vec![direct('C')]),
562            ('G', vec![direct('A')]),
563            ('F', vec![direct('E')]),
564            ('E', vec![direct('C')]),
565            ('D', vec![direct('C')]),
566            ('C', vec![direct('A')]),
567            ('B', vec![direct('A')]),
568            ('A', vec![]),
569        ]
570        .map(Ok);
571        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
572        I  direct(E)
573        │
574        │ H  direct(C)
575        │ │
576        │ │ G  direct(A)
577        │ │ │
578        │ │ │ F  direct(E)
579        ├─────╯
580        E │ │  direct(C)
581        ├─╯ │
582        │ D │  direct(C)
583        ├─╯ │
584        C   │  direct(A)
585        ├───╯
586        │ B  direct(A)
587        ├─╯
588        A
589        ");
590        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
591        I  direct(E)
592        │
593        │ F  direct(E)
594        ├─╯
595        E  direct(C)
596        │
597        │ H  direct(C)
598        ├─╯
599        │ D  direct(C)
600        ├─╯
601        C  direct(A)
602        │
603        │ G  direct(A)
604        ├─╯
605        │ B  direct(A)
606        ├─╯
607        A
608        ");
609
610        // I can be lazy, then H, G, and F will be queued.
611        let mut iter = topo_grouped(graph.iter().cloned().peekable());
612        assert_eq!(iter.next().unwrap().unwrap().0, 'I');
613        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'H');
614        assert_eq!(iter.next().unwrap().unwrap().0, 'F');
615        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'E');
616    }
617
618    #[test]
619    fn test_topo_grouped_fork_parallel() {
620        let graph = [
621            // Pull all sub graphs in reverse order:
622            ('I', vec![direct('A')]),
623            ('H', vec![direct('C')]),
624            ('G', vec![direct('E')]),
625            // Orphan sub graph G,F-E:
626            ('F', vec![direct('E')]),
627            ('E', vec![missing('Y')]),
628            // Orphan sub graph H,D-C:
629            ('D', vec![direct('C')]),
630            ('C', vec![missing('X')]),
631            // Orphan sub graph I,B-A:
632            ('B', vec![direct('A')]),
633            ('A', vec![]),
634        ]
635        .map(Ok);
636        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
637        I  direct(A)
638        │
639        │ H  direct(C)
640        │ │
641        │ │ G  direct(E)
642        │ │ │
643        │ │ │ F  direct(E)
644        │ │ ├─╯
645        │ │ E  missing(Y)
646        │ │ │
647        │ │ ~
648        │ │
649        │ │ D  direct(C)
650        │ ├─╯
651        │ C  missing(X)
652        │ │
653        │ ~
654        │
655        │ B  direct(A)
656        ├─╯
657        A
658        ");
659        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
660        I  direct(A)
661        │
662        │ B  direct(A)
663        ├─╯
664        A
665
666        H  direct(C)
667        │
668        │ D  direct(C)
669        ├─╯
670        C  missing(X)
671        │
672        ~
673
674        G  direct(E)
675        │
676        │ F  direct(E)
677        ├─╯
678        E  missing(Y)
679        │
680        ~
681        ");
682    }
683
684    #[test]
685    fn test_topo_grouped_fork_nested() {
686        fn sub_graph(
687            chars: impl IntoIterator<Item = char>,
688            root_edges: Vec<GraphEdge<char>>,
689        ) -> Vec<GraphNode<char>> {
690            let [b, c, d, e, f]: [char; 5] = chars.into_iter().collect_vec().try_into().unwrap();
691            vec![
692                (f, vec![direct(c)]),
693                (e, vec![direct(b)]),
694                (d, vec![direct(c)]),
695                (c, vec![direct(b)]),
696                (b, root_edges),
697            ]
698        }
699
700        // One nested fork sub graph from A
701        let graph = itertools::chain!(
702            vec![('G', vec![direct('A')])],
703            sub_graph('B'..='F', vec![direct('A')]),
704            vec![('A', vec![])],
705        )
706        .map(Ok)
707        .collect_vec();
708        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
709        G  direct(A)
710        │
711        │ F  direct(C)
712        │ │
713        │ │ E  direct(B)
714        │ │ │
715        │ │ │ D  direct(C)
716        │ ├───╯
717        │ C │  direct(B)
718        │ ├─╯
719        │ B  direct(A)
720        ├─╯
721        A
722        ");
723        // A::F is picked at A, and A will be unblocked. Then, C::D at C, ...
724        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
725        G  direct(A)
726        │
727        │ F  direct(C)
728        │ │
729        │ │ D  direct(C)
730        │ ├─╯
731        │ C  direct(B)
732        │ │
733        │ │ E  direct(B)
734        │ ├─╯
735        │ B  direct(A)
736        ├─╯
737        A
738        ");
739
740        // Two nested fork sub graphs from A
741        let graph = itertools::chain!(
742            vec![('L', vec![direct('A')])],
743            sub_graph('G'..='K', vec![direct('A')]),
744            sub_graph('B'..='F', vec![direct('A')]),
745            vec![('A', vec![])],
746        )
747        .map(Ok)
748        .collect_vec();
749        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
750        L  direct(A)
751        │
752        │ K  direct(H)
753        │ │
754        │ │ J  direct(G)
755        │ │ │
756        │ │ │ I  direct(H)
757        │ ├───╯
758        │ H │  direct(G)
759        │ ├─╯
760        │ G  direct(A)
761        ├─╯
762        │ F  direct(C)
763        │ │
764        │ │ E  direct(B)
765        │ │ │
766        │ │ │ D  direct(C)
767        │ ├───╯
768        │ C │  direct(B)
769        │ ├─╯
770        │ B  direct(A)
771        ├─╯
772        A
773        ");
774        // A::K is picked at A, and A will be unblocked. Then, H::I at H, ...
775        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
776        L  direct(A)
777        │
778        │ K  direct(H)
779        │ │
780        │ │ I  direct(H)
781        │ ├─╯
782        │ H  direct(G)
783        │ │
784        │ │ J  direct(G)
785        │ ├─╯
786        │ G  direct(A)
787        ├─╯
788        │ F  direct(C)
789        │ │
790        │ │ D  direct(C)
791        │ ├─╯
792        │ C  direct(B)
793        │ │
794        │ │ E  direct(B)
795        │ ├─╯
796        │ B  direct(A)
797        ├─╯
798        A
799        ");
800
801        // Two nested fork sub graphs from A, interleaved
802        let graph = itertools::chain!(
803            vec![('L', vec![direct('A')])],
804            sub_graph(['C', 'E', 'G', 'I', 'K'], vec![direct('A')]),
805            sub_graph(['B', 'D', 'F', 'H', 'J'], vec![direct('A')]),
806            vec![('A', vec![])],
807        )
808        .sorted_by(|(id1, _), (id2, _)| id2.cmp(id1))
809        .map(Ok)
810        .collect_vec();
811        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
812        L  direct(A)
813        │
814        │ K  direct(E)
815        │ │
816        │ │ J  direct(D)
817        │ │ │
818        │ │ │ I  direct(C)
819        │ │ │ │
820        │ │ │ │ H  direct(B)
821        │ │ │ │ │
822        │ │ │ │ │ G  direct(E)
823        │ ├───────╯
824        │ │ │ │ │ F  direct(D)
825        │ │ ├─────╯
826        │ E │ │ │  direct(C)
827        │ ├───╯ │
828        │ │ D   │  direct(B)
829        │ │ ├───╯
830        │ C │  direct(A)
831        ├─╯ │
832        │   B  direct(A)
833        ├───╯
834        A
835        ");
836        // A::K is picked at A, and A will be unblocked. Then, E::G at E, ...
837        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
838        L  direct(A)
839        │
840        │ K  direct(E)
841        │ │
842        │ │ G  direct(E)
843        │ ├─╯
844        │ E  direct(C)
845        │ │
846        │ │ I  direct(C)
847        │ ├─╯
848        │ C  direct(A)
849        ├─╯
850        │ J  direct(D)
851        │ │
852        │ │ F  direct(D)
853        │ ├─╯
854        │ D  direct(B)
855        │ │
856        │ │ H  direct(B)
857        │ ├─╯
858        │ B  direct(A)
859        ├─╯
860        A
861        ");
862
863        // Merged fork sub graphs at K
864        let graph = itertools::chain!(
865            vec![('K', vec![direct('E'), direct('J')])],
866            sub_graph('F'..='J', vec![missing('Y')]),
867            sub_graph('A'..='E', vec![missing('X')]),
868        )
869        .map(Ok)
870        .collect_vec();
871        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
872        K    direct(E), direct(J)
873        ├─╮
874        │ J  direct(G)
875        │ │
876        │ │ I  direct(F)
877        │ │ │
878        │ │ │ H  direct(G)
879        │ ├───╯
880        │ G │  direct(F)
881        │ ├─╯
882        │ F  missing(Y)
883        │ │
884        │ ~
885        │
886        E  direct(B)
887        │
888        │ D  direct(A)
889        │ │
890        │ │ C  direct(B)
891        ├───╯
892        B │  direct(A)
893        ├─╯
894        A  missing(X)
895        │
896        ~
897        ");
898        // K-E,J is resolved without queuing new heads. Then, G::H, F::I, B::C, and
899        // A::D.
900        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
901        K    direct(E), direct(J)
902        ├─╮
903        │ J  direct(G)
904        │ │
905        E │  direct(B)
906        │ │
907        │ │ H  direct(G)
908        │ ├─╯
909        │ G  direct(F)
910        │ │
911        │ │ I  direct(F)
912        │ ├─╯
913        │ F  missing(Y)
914        │ │
915        │ ~
916        │
917        │ C  direct(B)
918        ├─╯
919        B  direct(A)
920        │
921        │ D  direct(A)
922        ├─╯
923        A  missing(X)
924        │
925        ~
926        ");
927
928        // Merged fork sub graphs at K, interleaved
929        let graph = itertools::chain!(
930            vec![('K', vec![direct('I'), direct('J')])],
931            sub_graph(['B', 'D', 'F', 'H', 'J'], vec![missing('Y')]),
932            sub_graph(['A', 'C', 'E', 'G', 'I'], vec![missing('X')]),
933        )
934        .sorted_by(|(id1, _), (id2, _)| id2.cmp(id1))
935        .map(Ok)
936        .collect_vec();
937        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
938        K    direct(I), direct(J)
939        ├─╮
940        │ J  direct(D)
941        │ │
942        I │  direct(C)
943        │ │
944        │ │ H  direct(B)
945        │ │ │
946        │ │ │ G  direct(A)
947        │ │ │ │
948        │ │ │ │ F  direct(D)
949        │ ├─────╯
950        │ │ │ │ E  direct(C)
951        ├───────╯
952        │ D │ │  direct(B)
953        │ ├─╯ │
954        C │   │  direct(A)
955        ├─────╯
956        │ B  missing(Y)
957        │ │
958        │ ~
959        │
960        A  missing(X)
961        │
962        ~
963        ");
964        // K-I,J is resolved without queuing new heads. Then, D::F, B::H, C::E, and
965        // A::G.
966        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
967        K    direct(I), direct(J)
968        ├─╮
969        │ J  direct(D)
970        │ │
971        I │  direct(C)
972        │ │
973        │ │ F  direct(D)
974        │ ├─╯
975        │ D  direct(B)
976        │ │
977        │ │ H  direct(B)
978        │ ├─╯
979        │ B  missing(Y)
980        │ │
981        │ ~
982        │
983        │ E  direct(C)
984        ├─╯
985        C  direct(A)
986        │
987        │ G  direct(A)
988        ├─╯
989        A  missing(X)
990        │
991        ~
992        ");
993    }
994
995    #[test]
996    fn test_topo_grouped_merge_interleaved() {
997        let graph = [
998            ('F', vec![direct('E')]),
999            ('E', vec![direct('C'), direct('D')]),
1000            ('D', vec![direct('B')]),
1001            ('C', vec![direct('A')]),
1002            ('B', vec![direct('A')]),
1003            ('A', vec![]),
1004        ]
1005        .map(Ok);
1006        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1007        F  direct(E)
1008        │
1009        E    direct(C), direct(D)
1010        ├─╮
1011        │ D  direct(B)
1012        │ │
1013        C │  direct(A)
1014        │ │
1015        │ B  direct(A)
1016        ├─╯
1017        A
1018        ");
1019        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1020        F  direct(E)
1021        │
1022        E    direct(C), direct(D)
1023        ├─╮
1024        │ D  direct(B)
1025        │ │
1026        │ B  direct(A)
1027        │ │
1028        C │  direct(A)
1029        ├─╯
1030        A
1031        ");
1032
1033        // F, E, and D can be lazy, then C will be queued, then B.
1034        let mut iter = topo_grouped(graph.iter().cloned().peekable());
1035        assert_eq!(iter.next().unwrap().unwrap().0, 'F');
1036        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'E');
1037        assert_eq!(iter.next().unwrap().unwrap().0, 'E');
1038        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'D');
1039        assert_eq!(iter.next().unwrap().unwrap().0, 'D');
1040        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'C');
1041        assert_eq!(iter.next().unwrap().unwrap().0, 'B');
1042        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'A');
1043    }
1044
1045    #[test]
1046    fn test_topo_grouped_merge_but_missing() {
1047        let graph = [
1048            ('E', vec![direct('D')]),
1049            ('D', vec![missing('Y'), direct('C')]),
1050            ('C', vec![direct('B'), missing('X')]),
1051            ('B', vec![direct('A')]),
1052            ('A', vec![]),
1053        ]
1054        .map(Ok);
1055        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1056        E  direct(D)
1057        │
1058        D    missing(Y), direct(C)
1059        ├─╮
1060        │ │
1061        ~ │
1062          │
1063          C  direct(B), missing(X)
1064        ╭─┤
1065        │ │
1066        ~ │
1067          │
1068          B  direct(A)
1069          │
1070          A
1071        ");
1072        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1073        E  direct(D)
1074        │
1075        D    missing(Y), direct(C)
1076        ├─╮
1077        │ │
1078        ~ │
1079          │
1080          C  direct(B), missing(X)
1081        ╭─┤
1082        │ │
1083        ~ │
1084          │
1085          B  direct(A)
1086          │
1087          A
1088        ");
1089
1090        // All nodes can be lazily emitted.
1091        let mut iter = topo_grouped(graph.iter().cloned().peekable());
1092        assert_eq!(iter.next().unwrap().unwrap().0, 'E');
1093        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'D');
1094        assert_eq!(iter.next().unwrap().unwrap().0, 'D');
1095        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'C');
1096        assert_eq!(iter.next().unwrap().unwrap().0, 'C');
1097        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'B');
1098        assert_eq!(iter.next().unwrap().unwrap().0, 'B');
1099        assert_eq!(iter.input_iter.peek().unwrap().as_ref().unwrap().0, 'A');
1100    }
1101
1102    #[test]
1103    fn test_topo_grouped_merge_criss_cross() {
1104        let graph = [
1105            ('G', vec![direct('E')]),
1106            ('F', vec![direct('D')]),
1107            ('E', vec![direct('B'), direct('C')]),
1108            ('D', vec![direct('B'), direct('C')]),
1109            ('C', vec![direct('A')]),
1110            ('B', vec![direct('A')]),
1111            ('A', vec![]),
1112        ]
1113        .map(Ok);
1114        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1115        G  direct(E)
1116        │
1117        │ F  direct(D)
1118        │ │
1119        E │    direct(B), direct(C)
1120        ├───╮
1121        │ D │  direct(B), direct(C)
1122        ╭─┴─╮
1123        │   C  direct(A)
1124        │   │
1125        B   │  direct(A)
1126        ├───╯
1127        A
1128        ");
1129        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1130        G  direct(E)
1131        │
1132        E    direct(B), direct(C)
1133        ├─╮
1134        │ │ F  direct(D)
1135        │ │ │
1136        │ │ D  direct(B), direct(C)
1137        ╭─┬─╯
1138        │ C  direct(A)
1139        │ │
1140        B │  direct(A)
1141        ├─╯
1142        A
1143        ");
1144    }
1145
1146    #[test]
1147    fn test_topo_grouped_merge_descendants_interleaved() {
1148        let graph = [
1149            ('H', vec![direct('F')]),
1150            ('G', vec![direct('E')]),
1151            ('F', vec![direct('D')]),
1152            ('E', vec![direct('C')]),
1153            ('D', vec![direct('C'), direct('B')]),
1154            ('C', vec![direct('A')]),
1155            ('B', vec![direct('A')]),
1156            ('A', vec![]),
1157        ]
1158        .map(Ok);
1159        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1160        H  direct(F)
1161        │
1162        │ G  direct(E)
1163        │ │
1164        F │  direct(D)
1165        │ │
1166        │ E  direct(C)
1167        │ │
1168        D │  direct(C), direct(B)
1169        ├─╮
1170        │ C  direct(A)
1171        │ │
1172        B │  direct(A)
1173        ├─╯
1174        A
1175        ");
1176        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1177        H  direct(F)
1178        │
1179        F  direct(D)
1180        │
1181        D    direct(C), direct(B)
1182        ├─╮
1183        │ B  direct(A)
1184        │ │
1185        │ │ G  direct(E)
1186        │ │ │
1187        │ │ E  direct(C)
1188        ├───╯
1189        C │  direct(A)
1190        ├─╯
1191        A
1192        ");
1193    }
1194
1195    #[test]
1196    fn test_topo_grouped_merge_multiple_roots() {
1197        let graph = [
1198            ('D', vec![direct('C')]),
1199            ('C', vec![direct('B'), direct('A')]),
1200            ('B', vec![missing('X')]),
1201            ('A', vec![]),
1202        ]
1203        .map(Ok);
1204        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1205        D  direct(C)
1206        │
1207        C    direct(B), direct(A)
1208        ├─╮
1209        B │  missing(X)
1210        │ │
1211        ~ │
1212          │
1213          A
1214        ");
1215        // A is emitted first because it's the second parent.
1216        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1217        D  direct(C)
1218        │
1219        C    direct(B), direct(A)
1220        ├─╮
1221        │ A
1222        │
1223        B  missing(X)
1224        │
1225        ~
1226        ");
1227    }
1228
1229    #[test]
1230    fn test_topo_grouped_merge_stairs() {
1231        let graph = [
1232            // Merge topic branches one by one:
1233            ('J', vec![direct('I'), direct('G')]),
1234            ('I', vec![direct('H'), direct('E')]),
1235            ('H', vec![direct('D'), direct('F')]),
1236            // Topic branches:
1237            ('G', vec![direct('D')]),
1238            ('F', vec![direct('C')]),
1239            ('E', vec![direct('B')]),
1240            // Base nodes:
1241            ('D', vec![direct('C')]),
1242            ('C', vec![direct('B')]),
1243            ('B', vec![direct('A')]),
1244            ('A', vec![]),
1245        ]
1246        .map(Ok);
1247        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1248        J    direct(I), direct(G)
1249        ├─╮
1250        I │    direct(H), direct(E)
1251        ├───╮
1252        H │ │    direct(D), direct(F)
1253        ├─────╮
1254        │ G │ │  direct(D)
1255        ├─╯ │ │
1256        │   │ F  direct(C)
1257        │   │ │
1258        │   E │  direct(B)
1259        │   │ │
1260        D   │ │  direct(C)
1261        ├─────╯
1262        C   │  direct(B)
1263        ├───╯
1264        B  direct(A)
1265        │
1266        A
1267        ");
1268        // Second branches are visited first.
1269        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1270        J    direct(I), direct(G)
1271        ├─╮
1272        │ G  direct(D)
1273        │ │
1274        I │    direct(H), direct(E)
1275        ├───╮
1276        │ │ E  direct(B)
1277        │ │ │
1278        H │ │  direct(D), direct(F)
1279        ├─╮ │
1280        F │ │  direct(C)
1281        │ │ │
1282        │ D │  direct(C)
1283        ├─╯ │
1284        C   │  direct(B)
1285        ├───╯
1286        B  direct(A)
1287        │
1288        A
1289        ");
1290    }
1291
1292    #[test]
1293    fn test_topo_grouped_merge_and_fork() {
1294        let graph = [
1295            ('J', vec![direct('F')]),
1296            ('I', vec![direct('E')]),
1297            ('H', vec![direct('G')]),
1298            ('G', vec![direct('D'), direct('E')]),
1299            ('F', vec![direct('C')]),
1300            ('E', vec![direct('B')]),
1301            ('D', vec![direct('B')]),
1302            ('C', vec![direct('A')]),
1303            ('B', vec![direct('A')]),
1304            ('A', vec![]),
1305        ]
1306        .map(Ok);
1307        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1308        J  direct(F)
1309        │
1310        │ I  direct(E)
1311        │ │
1312        │ │ H  direct(G)
1313        │ │ │
1314        │ │ G  direct(D), direct(E)
1315        │ ╭─┤
1316        F │ │  direct(C)
1317        │ │ │
1318        │ E │  direct(B)
1319        │ │ │
1320        │ │ D  direct(B)
1321        │ ├─╯
1322        C │  direct(A)
1323        │ │
1324        │ B  direct(A)
1325        ├─╯
1326        A
1327        ");
1328        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1329        J  direct(F)
1330        │
1331        F  direct(C)
1332        │
1333        C  direct(A)
1334        │
1335        │ I  direct(E)
1336        │ │
1337        │ │ H  direct(G)
1338        │ │ │
1339        │ │ G  direct(D), direct(E)
1340        │ ╭─┤
1341        │ E │  direct(B)
1342        │ │ │
1343        │ │ D  direct(B)
1344        │ ├─╯
1345        │ B  direct(A)
1346        ├─╯
1347        A
1348        ");
1349    }
1350
1351    #[test]
1352    fn test_topo_grouped_merge_and_fork_multiple_roots() {
1353        let graph = [
1354            ('J', vec![direct('F')]),
1355            ('I', vec![direct('G')]),
1356            ('H', vec![direct('E')]),
1357            ('G', vec![direct('E'), direct('B')]),
1358            ('F', vec![direct('D')]),
1359            ('E', vec![direct('C')]),
1360            ('D', vec![direct('A')]),
1361            ('C', vec![direct('A')]),
1362            ('B', vec![missing('X')]),
1363            ('A', vec![]),
1364        ]
1365        .map(Ok);
1366        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1367        J  direct(F)
1368        │
1369        │ I  direct(G)
1370        │ │
1371        │ │ H  direct(E)
1372        │ │ │
1373        │ G │  direct(E), direct(B)
1374        │ ├─╮
1375        F │ │  direct(D)
1376        │ │ │
1377        │ │ E  direct(C)
1378        │ │ │
1379        D │ │  direct(A)
1380        │ │ │
1381        │ │ C  direct(A)
1382        ├───╯
1383        │ B  missing(X)
1384        │ │
1385        │ ~
1386        │
1387        A
1388        ");
1389        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1390        J  direct(F)
1391        │
1392        F  direct(D)
1393        │
1394        D  direct(A)
1395        │
1396        │ I  direct(G)
1397        │ │
1398        │ G    direct(E), direct(B)
1399        │ ├─╮
1400        │ │ B  missing(X)
1401        │ │ │
1402        │ │ ~
1403        │ │
1404        │ │ H  direct(E)
1405        │ ├─╯
1406        │ E  direct(C)
1407        │ │
1408        │ C  direct(A)
1409        ├─╯
1410        A
1411        ");
1412    }
1413
1414    #[test]
1415    fn test_topo_grouped_parallel_interleaved() {
1416        let graph = [
1417            ('E', vec![direct('C')]),
1418            ('D', vec![direct('B')]),
1419            ('C', vec![direct('A')]),
1420            ('B', vec![missing('X')]),
1421            ('A', vec![]),
1422        ]
1423        .map(Ok);
1424        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1425        E  direct(C)
1426        │
1427        │ D  direct(B)
1428        │ │
1429        C │  direct(A)
1430        │ │
1431        │ B  missing(X)
1432        │ │
1433        │ ~
1434        │
1435        A
1436        ");
1437        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1438        E  direct(C)
1439        │
1440        C  direct(A)
1441        │
1442        A
1443
1444        D  direct(B)
1445        │
1446        B  missing(X)
1447        │
1448        ~
1449        ");
1450    }
1451
1452    #[test]
1453    fn test_topo_grouped_multiple_child_dependencies() {
1454        let graph = [
1455            ('I', vec![direct('H'), direct('G')]),
1456            ('H', vec![direct('D')]),
1457            ('G', vec![direct('B')]),
1458            ('F', vec![direct('E'), direct('C')]),
1459            ('E', vec![direct('D')]),
1460            ('D', vec![direct('B')]),
1461            ('C', vec![direct('B')]),
1462            ('B', vec![direct('A')]),
1463            ('A', vec![]),
1464        ]
1465        .map(Ok);
1466        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1467        I    direct(H), direct(G)
1468        ├─╮
1469        H │  direct(D)
1470        │ │
1471        │ G  direct(B)
1472        │ │
1473        │ │ F    direct(E), direct(C)
1474        │ │ ├─╮
1475        │ │ E │  direct(D)
1476        ├───╯ │
1477        D │   │  direct(B)
1478        ├─╯   │
1479        │     C  direct(B)
1480        ├─────╯
1481        B  direct(A)
1482        │
1483        A
1484        ");
1485        // Topological order must be preserved. Depending on the implementation,
1486        // E might be requested more than once by paths D->E and B->D->E.
1487        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1488        I    direct(H), direct(G)
1489        ├─╮
1490        │ G  direct(B)
1491        │ │
1492        H │  direct(D)
1493        │ │
1494        │ │ F    direct(E), direct(C)
1495        │ │ ├─╮
1496        │ │ │ C  direct(B)
1497        │ ├───╯
1498        │ │ E  direct(D)
1499        ├───╯
1500        D │  direct(B)
1501        ├─╯
1502        B  direct(A)
1503        │
1504        A
1505        ");
1506    }
1507
1508    #[test]
1509    fn test_topo_grouped_prioritized_branches_trivial_fork() {
1510        // The same setup as test_topo_grouped_trivial_fork()
1511        let graph = [
1512            ('E', vec![direct('B')]),
1513            ('D', vec![direct('A')]),
1514            ('C', vec![direct('B')]),
1515            ('B', vec![direct('A')]),
1516            ('A', vec![]),
1517        ]
1518        .map(Ok);
1519        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1520        E  direct(B)
1521        │
1522        │ D  direct(A)
1523        │ │
1524        │ │ C  direct(B)
1525        ├───╯
1526        B │  direct(A)
1527        ├─╯
1528        A
1529        ");
1530
1531        // Emit the branch C first
1532        let mut iter = topo_grouped(graph.iter().cloned());
1533        iter.prioritize_branch('C');
1534        insta::assert_snapshot!(format_graph(iter), @r"
1535        C  direct(B)
1536        │
1537        │ E  direct(B)
1538        ├─╯
1539        B  direct(A)
1540        │
1541        │ D  direct(A)
1542        ├─╯
1543        A
1544        ");
1545
1546        // Emit the branch D first
1547        let mut iter = topo_grouped(graph.iter().cloned());
1548        iter.prioritize_branch('D');
1549        insta::assert_snapshot!(format_graph(iter), @r"
1550        D  direct(A)
1551        │
1552        │ E  direct(B)
1553        │ │
1554        │ │ C  direct(B)
1555        │ ├─╯
1556        │ B  direct(A)
1557        ├─╯
1558        A
1559        ");
1560
1561        // Emit the branch C first, then D. E is emitted earlier than D because
1562        // E belongs to the branch C compared to the branch D.
1563        let mut iter = topo_grouped(graph.iter().cloned());
1564        iter.prioritize_branch('C');
1565        iter.prioritize_branch('D');
1566        insta::assert_snapshot!(format_graph(iter), @r"
1567        C  direct(B)
1568        │
1569        │ E  direct(B)
1570        ├─╯
1571        B  direct(A)
1572        │
1573        │ D  direct(A)
1574        ├─╯
1575        A
1576        ");
1577
1578        // Non-head node can be prioritized
1579        let mut iter = topo_grouped(graph.iter().cloned());
1580        iter.prioritize_branch('B');
1581        insta::assert_snapshot!(format_graph(iter), @r"
1582        E  direct(B)
1583        │
1584        │ C  direct(B)
1585        ├─╯
1586        B  direct(A)
1587        │
1588        │ D  direct(A)
1589        ├─╯
1590        A
1591        ");
1592
1593        // Root node can be prioritized
1594        let mut iter = topo_grouped(graph.iter().cloned());
1595        iter.prioritize_branch('A');
1596        insta::assert_snapshot!(format_graph(iter), @r"
1597        D  direct(A)
1598        │
1599        │ E  direct(B)
1600        │ │
1601        │ │ C  direct(B)
1602        │ ├─╯
1603        │ B  direct(A)
1604        ├─╯
1605        A
1606        ");
1607    }
1608
1609    #[test]
1610    fn test_topo_grouped_prioritized_branches_fork_multiple_heads() {
1611        // The same setup as test_topo_grouped_fork_multiple_heads()
1612        let graph = [
1613            ('I', vec![direct('E')]),
1614            ('H', vec![direct('C')]),
1615            ('G', vec![direct('A')]),
1616            ('F', vec![direct('E')]),
1617            ('E', vec![direct('C')]),
1618            ('D', vec![direct('C')]),
1619            ('C', vec![direct('A')]),
1620            ('B', vec![direct('A')]),
1621            ('A', vec![]),
1622        ]
1623        .map(Ok);
1624        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1625        I  direct(E)
1626        │
1627        │ H  direct(C)
1628        │ │
1629        │ │ G  direct(A)
1630        │ │ │
1631        │ │ │ F  direct(E)
1632        ├─────╯
1633        E │ │  direct(C)
1634        ├─╯ │
1635        │ D │  direct(C)
1636        ├─╯ │
1637        C   │  direct(A)
1638        ├───╯
1639        │ B  direct(A)
1640        ├─╯
1641        A
1642        ");
1643
1644        // Emit B, G, then remainders
1645        let mut iter = topo_grouped(graph.iter().cloned());
1646        iter.prioritize_branch('B');
1647        iter.prioritize_branch('G');
1648        insta::assert_snapshot!(format_graph(iter), @r"
1649        B  direct(A)
1650        │
1651        │ G  direct(A)
1652        ├─╯
1653        │ I  direct(E)
1654        │ │
1655        │ │ F  direct(E)
1656        │ ├─╯
1657        │ E  direct(C)
1658        │ │
1659        │ │ H  direct(C)
1660        │ ├─╯
1661        │ │ D  direct(C)
1662        │ ├─╯
1663        │ C  direct(A)
1664        ├─╯
1665        A
1666        ");
1667
1668        // Emit D, H, then descendants of C. The order of B and G is not
1669        // respected because G can be found earlier through C->A->G. At this
1670        // point, B is not populated yet, so A is blocked only by {G}. This is
1671        // a limitation of the current node reordering logic.
1672        let mut iter = topo_grouped(graph.iter().cloned());
1673        iter.prioritize_branch('D');
1674        iter.prioritize_branch('H');
1675        iter.prioritize_branch('B');
1676        iter.prioritize_branch('G');
1677        insta::assert_snapshot!(format_graph(iter), @r"
1678        D  direct(C)
1679        │
1680        │ H  direct(C)
1681        ├─╯
1682        │ I  direct(E)
1683        │ │
1684        │ │ F  direct(E)
1685        │ ├─╯
1686        │ E  direct(C)
1687        ├─╯
1688        C  direct(A)
1689        │
1690        │ G  direct(A)
1691        ├─╯
1692        │ B  direct(A)
1693        ├─╯
1694        A
1695        ");
1696    }
1697
1698    #[test]
1699    fn test_topo_grouped_prioritized_branches_fork_parallel() {
1700        // The same setup as test_topo_grouped_fork_parallel()
1701        let graph = [
1702            // Pull all sub graphs in reverse order:
1703            ('I', vec![direct('A')]),
1704            ('H', vec![direct('C')]),
1705            ('G', vec![direct('E')]),
1706            // Orphan sub graph G,F-E:
1707            ('F', vec![direct('E')]),
1708            ('E', vec![missing('Y')]),
1709            // Orphan sub graph H,D-C:
1710            ('D', vec![direct('C')]),
1711            ('C', vec![missing('X')]),
1712            // Orphan sub graph I,B-A:
1713            ('B', vec![direct('A')]),
1714            ('A', vec![]),
1715        ]
1716        .map(Ok);
1717        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1718        I  direct(A)
1719        │
1720        │ H  direct(C)
1721        │ │
1722        │ │ G  direct(E)
1723        │ │ │
1724        │ │ │ F  direct(E)
1725        │ │ ├─╯
1726        │ │ E  missing(Y)
1727        │ │ │
1728        │ │ ~
1729        │ │
1730        │ │ D  direct(C)
1731        │ ├─╯
1732        │ C  missing(X)
1733        │ │
1734        │ ~
1735        │
1736        │ B  direct(A)
1737        ├─╯
1738        A
1739        ");
1740
1741        // Emit the sub graph G first
1742        let mut iter = topo_grouped(graph.iter().cloned());
1743        iter.prioritize_branch('G');
1744        insta::assert_snapshot!(format_graph(iter), @r"
1745        G  direct(E)
1746        │
1747        │ F  direct(E)
1748        ├─╯
1749        E  missing(Y)
1750        │
1751        ~
1752
1753        I  direct(A)
1754        │
1755        │ B  direct(A)
1756        ├─╯
1757        A
1758
1759        H  direct(C)
1760        │
1761        │ D  direct(C)
1762        ├─╯
1763        C  missing(X)
1764        │
1765        ~
1766        ");
1767
1768        // Emit sub graphs in reverse order by selecting roots
1769        let mut iter = topo_grouped(graph.iter().cloned());
1770        iter.prioritize_branch('E');
1771        iter.prioritize_branch('C');
1772        iter.prioritize_branch('A');
1773        insta::assert_snapshot!(format_graph(iter), @r"
1774        G  direct(E)
1775        │
1776        │ F  direct(E)
1777        ├─╯
1778        E  missing(Y)
1779        │
1780        ~
1781
1782        H  direct(C)
1783        │
1784        │ D  direct(C)
1785        ├─╯
1786        C  missing(X)
1787        │
1788        ~
1789
1790        I  direct(A)
1791        │
1792        │ B  direct(A)
1793        ├─╯
1794        A
1795        ");
1796    }
1797
1798    #[test]
1799    fn test_topo_grouped_requeue_unpopulated() {
1800        let graph = [
1801            ('C', vec![direct('A'), direct('B')]),
1802            ('B', vec![direct('A')]),
1803            ('A', vec![]),
1804        ]
1805        .map(Ok);
1806        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1807        C    direct(A), direct(B)
1808        ├─╮
1809        │ B  direct(A)
1810        ├─╯
1811        A
1812        ");
1813        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1814        C    direct(A), direct(B)
1815        ├─╮
1816        │ B  direct(A)
1817        ├─╯
1818        A
1819        ");
1820
1821        // A is queued once by C-A because B isn't populated at this point. Since
1822        // B is the second parent, B-A is processed next and A is queued again. So
1823        // one of them in the queue has to be ignored.
1824        let mut iter = topo_grouped(graph.iter().cloned());
1825        assert_eq!(iter.next().unwrap().unwrap().0, 'C');
1826        assert_eq!(iter.emittable_ids, vec!['A', 'B']);
1827        assert_eq!(iter.next().unwrap().unwrap().0, 'B');
1828        assert_eq!(iter.emittable_ids, vec!['A', 'A']);
1829        assert_eq!(iter.next().unwrap().unwrap().0, 'A');
1830        assert!(iter.next().is_none());
1831        assert!(iter.emittable_ids.is_empty());
1832    }
1833
1834    #[test]
1835    fn test_topo_grouped_duplicated_edges() {
1836        // The graph shouldn't have duplicated parent->child edges, but topo-grouped
1837        // iterator can handle it anyway.
1838        let graph = [('B', vec![direct('A'), direct('A')]), ('A', vec![])].map(Ok);
1839        insta::assert_snapshot!(format_graph(graph.iter().cloned()), @r"
1840        B  direct(A), direct(A)
1841        │
1842        A
1843        ");
1844        insta::assert_snapshot!(format_graph(topo_grouped(graph.iter().cloned())), @r"
1845        B  direct(A), direct(A)
1846        │
1847        A
1848        ");
1849
1850        let mut iter = topo_grouped(graph.iter().cloned());
1851        assert_eq!(iter.next().unwrap().unwrap().0, 'B');
1852        assert_eq!(iter.emittable_ids, vec!['A', 'A']);
1853        assert_eq!(iter.next().unwrap().unwrap().0, 'A');
1854        assert!(iter.next().is_none());
1855        assert!(iter.emittable_ids.is_empty());
1856    }
1857}
jj_lib/graph.rs

jj_lib/
graph.rs
