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

jj_lib/
graph.rs
