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

jj_lib/
graph.rs
