[ninjago] Fix a CriticalPathV2 edge case
It was not correctly handling an edge case: when
constructing the critical path, it is possible to encounter nodes with
multiple inputs that are all on critical path, and in this case we
always want to pick the input that finishes the last.
Test: fx test --host -o ninjagraph_test
Change-Id: Ic578962c7416e0313b3ed45081fff16f14c82642
Reviewed-on: https://fuchsia-review.googlesource.com/c/fuchsia/+/443855
Reviewed-by: Shai Barack <shayba@google.com>
Testability-Review: Shai Barack <shayba@google.com>
Commit-Queue: Jay Zhuang <jayzhuang@google.com>
diff --git a/tools/build/ninjago/ninjagraph/ninjagraph.go b/tools/build/ninjago/ninjagraph/ninjagraph.go
index ac765ff..18dc6f38 100644
--- a/tools/build/ninjago/ninjagraph/ninjagraph.go
+++ b/tools/build/ninjago/ninjagraph/ninjagraph.go
@@ -721,9 +721,33 @@
if err != nil {
return nil, fmt.Errorf("calculating total float: %w", err)
}
- if tf == 0 {
+ if tf != 0 {
+ continue
+ }
+
+ if nextCriticalEdge == nil {
nextCriticalEdge = n.In
- break
+ continue
+ }
+ // Among all the inputs, pick the one that finishes the last, so we don't
+ // accidentally skip actions when multiple inputs of the same node are on
+ // the critical path.
+ //
+ // For example, imagine a graph:
+ // 1 -> 2 -------> 4
+ // \ /
+ // -> 3
+ // When we are at 4, we want to pick up 3 as the next step, not 2.
+ lfNew, err := g.latestFinish(n.In)
+ if err != nil {
+ return nil, fmt.Errorf("calculating latest finish: %w", err)
+ }
+ lfCur, err := g.latestFinish(nextCriticalEdge)
+ if err != nil {
+ return nil, fmt.Errorf("calculating latest finish: %w", err)
+ }
+ if lfNew > lfCur {
+ nextCriticalEdge = n.In
}
}
criticalEdge = nextCriticalEdge
diff --git a/tools/build/ninjago/ninjagraph/ninjagraph_test.go b/tools/build/ninjago/ninjagraph/ninjagraph_test.go
index 653f47a..e3adfea 100644
--- a/tools/build/ninjago/ninjagraph/ninjagraph_test.go
+++ b/tools/build/ninjago/ninjagraph/ninjagraph_test.go
@@ -576,6 +576,22 @@
}
}
+func TestCriticalPathWithRealBuild(t *testing.T) {
+ graph := readTestGraph(t)
+
+ cp, err := graph.CriticalPath()
+ if err != nil {
+ t.Fatalf("CriticalPath() got error: %v", err)
+ }
+ cp2, err := graph.CriticalPathV2()
+ if err != nil {
+ t.Fatalf("CriticalPathV2() got error: %v", err)
+ }
+ if diff := cmp.Diff(cp, cp2); diff != "" {
+ t.Errorf("CriticalPath() and CriticalPathV2() returned different critical paths (-v1, +v2):\n%s", diff)
+ }
+}
+
func BenchmarkCriticalPath(b *testing.B) {
graph := readTestGraph(b)
@@ -699,6 +715,12 @@
step5 := ninjalog.Step{Start: 100, End: 200, Out: "5"}
edge5 := &Edge{Inputs: []int64{2, 4}, Outputs: []int64{5}, Step: &step5}
+ step6 := ninjalog.Step{Start: 20, End: 30, Out: "6"}
+ edge6 := &Edge{Inputs: []int64{2, 7}, Outputs: []int64{6}, Step: &step6}
+
+ step7 := ninjalog.Step{Start: 10, End: 20, Out: "7"}
+ edge7 := &Edge{Inputs: []int64{2}, Outputs: []int64{7}, Step: &step7}
+
clearEdgeMemoizations := func() {
for _, e := range []*Edge{edge1, edge2, edge3, edge4, edge4LateStart, edge5} {
e.earliestStart = nil
@@ -794,6 +816,22 @@
},
want: []ninjalog.Step{step2, step5},
},
+ {
+ // 1 -> 2 -------> 6
+ // \ /
+ // -> 7
+ desc: "multiple inputs all on critical path",
+ graph: Graph{
+ Nodes: map[int64]*Node{
+ 1: {ID: 1, Outs: []*Edge{edge2}},
+ 2: {ID: 2, In: edge2, Outs: []*Edge{edge6, edge7}},
+ 6: {ID: 6, In: edge6},
+ 7: {ID: 7, In: edge7, Outs: []*Edge{edge6}},
+ },
+ Edges: []*Edge{edge2, edge6, edge7},
+ },
+ want: []ninjalog.Step{step2, step7, step6},
+ },
} {
t.Run(tc.desc, func(t *testing.T) {
// Clear memoization fields because we are reusing pointers to edges.
