| // Copyright 2020 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| package ninjagraph |
| |
| import ( |
| "flag" |
| "fmt" |
| "os" |
| "path/filepath" |
| "strings" |
| "testing" |
| "time" |
| |
| "github.com/google/go-cmp/cmp" |
| "github.com/google/go-cmp/cmp/cmpopts" |
| "go.fuchsia.dev/fuchsia/tools/build/ninjago/compdb" |
| "go.fuchsia.dev/fuchsia/tools/build/ninjago/ninjalog" |
| ) |
| |
| var testDataFlag = flag.String("test_data_dir", "../test_data", "Path to ../test_data/; only used in GN build") |
| |
| // This ordering is not perfect but good enough for these tests, since we always |
| // have unique Rule names in edges. |
| var orderEdgesByRule = cmpopts.SortSlices(func(x, y *Edge) bool { return x.Rule < y.Rule }) |
| |
| func TestFromDOT(t *testing.T) { |
| for _, tc := range []struct { |
| desc string |
| dot string |
| want Graph |
| }{ |
| { |
| desc: "empty", |
| dot: `digraph ninja {}`, |
| want: Graph{}, |
| }, |
| { |
| desc: "no inputs single output", |
| // build some_file: touch |
| dot: `digraph ninja { |
| "0x13e8900" [label="some_file"] |
| "0x13e8850" [label="touch", shape=ellipse] |
| "0x13e8850" -> "0x13e8900" |
| }`, |
| want: Graph{ |
| Nodes: map[int64]*Node{ |
| 0x13e8900: { |
| ID: 0x13e8900, |
| Path: "some_file", |
| In: &Edge{Outputs: []int64{0x13e8900}, Rule: "touch"}, |
| }, |
| }, |
| Edges: []*Edge{{Outputs: []int64{0x13e8900}, Rule: "touch"}}, |
| }, |
| }, |
| { |
| desc: "single input single output", |
| // build bar: cp foo |
| dot: `digraph ninja { |
| "0x1cc1a20" [label="bar"] |
| "0x1cc1ac0" -> "0x1cc1a20" [label=" cp"] |
| "0x1cc1ac0" [label="foo"] |
| }`, |
| want: Graph{ |
| Nodes: map[int64]*Node{ |
| 0x1cc1ac0: { |
| ID: 0x1cc1ac0, |
| Path: "foo", |
| Outs: []*Edge{ |
| {Inputs: []int64{0x1cc1ac0}, Outputs: []int64{0x1cc1a20}, Rule: "cp"}, |
| }, |
| }, |
| 0x1cc1a20: { |
| ID: 0x1cc1a20, |
| Path: "bar", |
| In: &Edge{Inputs: []int64{0x1cc1ac0}, Outputs: []int64{0x1cc1a20}, Rule: "cp"}, |
| }, |
| }, |
| Edges: []*Edge{ |
| {Inputs: []int64{0x1cc1ac0}, Outputs: []int64{0x1cc1a20}, Rule: "cp"}, |
| }, |
| }, |
| }, |
| { |
| desc: "multiple inputs multiple outputs", |
| // build d e: phony a b c |
| dot: `digraph ninja { |
| "0x1110870" [label="d"] |
| "0x11107e0" [label="phony", shape=ellipse] |
| "0x11107e0" -> "0x1110870" |
| "0x11107e0" -> "0x11108f0" |
| "0x11109a0" -> "0x11107e0" [arrowhead=none] |
| "0x1110a60" -> "0x11107e0" [arrowhead=none] |
| "0x1110b10" -> "0x11107e0" [arrowhead=none] |
| "0x11109a0" [label="a"] |
| "0x1110a60" [label="b"] |
| "0x1110b10" [label="c"] |
| "0x11108f0" [label="e"] |
| }`, |
| want: Graph{ |
| Nodes: map[int64]*Node{ |
| 0x11109a0: { |
| ID: 0x11109a0, |
| Path: "a", |
| Outs: []*Edge{ |
| { |
| Inputs: []int64{0x11109a0, 0x1110a60, 0x1110b10}, |
| Outputs: []int64{0x1110870, 0x11108f0}, |
| Rule: "phony", |
| }, |
| }, |
| }, |
| 0x1110a60: { |
| ID: 0x1110a60, |
| Path: "b", |
| Outs: []*Edge{ |
| { |
| Inputs: []int64{0x11109a0, 0x1110a60, 0x1110b10}, |
| Outputs: []int64{0x1110870, 0x11108f0}, |
| Rule: "phony", |
| }, |
| }, |
| }, |
| 0x1110b10: { |
| ID: 0x1110b10, |
| Path: "c", |
| Outs: []*Edge{ |
| { |
| Inputs: []int64{0x11109a0, 0x1110a60, 0x1110b10}, |
| Outputs: []int64{0x1110870, 0x11108f0}, |
| Rule: "phony", |
| }, |
| }, |
| }, |
| 0x1110870: { |
| ID: 0x1110870, |
| Path: "d", |
| In: &Edge{ |
| Inputs: []int64{0x11109a0, 0x1110a60, 0x1110b10}, |
| Outputs: []int64{0x1110870, 0x11108f0}, |
| Rule: "phony", |
| }, |
| }, |
| 0x11108f0: { |
| ID: 0x11108f0, |
| Path: "e", |
| In: &Edge{ |
| Inputs: []int64{0x11109a0, 0x1110a60, 0x1110b10}, |
| Outputs: []int64{0x1110870, 0x11108f0}, |
| Rule: "phony", |
| }, |
| }, |
| }, |
| Edges: []*Edge{ |
| { |
| Inputs: []int64{0x11109a0, 0x1110a60, 0x1110b10}, |
| Outputs: []int64{0x1110870, 0x11108f0}, |
| Rule: "phony", |
| }, |
| }, |
| }, |
| }, |
| { |
| desc: "multiple builds", |
| // build baz: touch |
| // build bar: cp foo |
| dot: `digraph ninja { |
| "0x13c3c70" [label="bar"] |
| "0x13c3d10" -> "0x13c3c70" [label=" cp"] |
| "0x13c3d10" [label="foo"] |
| "0x13c3e30" [label="baz"] |
| "0x13c3dc0" [label="touch", shape=ellipse] |
| "0x13c3dc0" -> "0x13c3e30" |
| }`, |
| want: Graph{ |
| Nodes: map[int64]*Node{ |
| 0x13c3d10: { |
| ID: 0x13c3d10, |
| Path: "foo", |
| Outs: []*Edge{ |
| {Inputs: []int64{0x13c3d10}, Outputs: []int64{0x13c3c70}, Rule: "cp"}, |
| }, |
| }, |
| 0x13c3c70: { |
| ID: 0x13c3c70, |
| Path: "bar", |
| In: &Edge{Inputs: []int64{0x13c3d10}, Outputs: []int64{0x13c3c70}, Rule: "cp"}, |
| }, |
| 0x13c3e30: { |
| ID: 0x13c3e30, |
| Path: "baz", |
| In: &Edge{Outputs: []int64{0x13c3e30}, Rule: "touch"}, |
| }, |
| }, |
| Edges: []*Edge{ |
| {Inputs: []int64{0x13c3d10}, Outputs: []int64{0x13c3c70}, Rule: "cp"}, |
| {Outputs: []int64{0x13c3e30}, Rule: "touch"}, |
| }, |
| }, |
| }, |
| { |
| desc: "omit output not in build graph", |
| // build b: rule a |
| // Note in the graph "0x11108f0" doesn't exist, although `rule` claims to |
| // produce it. |
| dot: `digraph ninja { |
| "0x1110870" [label="b"] |
| "0x11107e0" [label="rule", shape=ellipse] |
| "0x11107e0" -> "0x1110870" |
| "0x11107e0" -> "0x11108f0" |
| "0x11109a0" -> "0x11107e0" [arrowhead=none] |
| "0x11109a0" [label="a"] |
| }`, |
| want: Graph{ |
| Nodes: map[int64]*Node{ |
| 0x11109a0: { |
| ID: 0x11109a0, |
| Path: "a", |
| Outs: []*Edge{ |
| { |
| Inputs: []int64{0x11109a0}, |
| Outputs: []int64{0x1110870}, // Note 0x11108f0 is omitted. |
| Rule: "rule", |
| }, |
| }, |
| }, |
| 0x1110870: { |
| ID: 0x1110870, |
| Path: "b", |
| In: &Edge{ |
| Inputs: []int64{0x11109a0}, |
| Outputs: []int64{0x1110870}, // Note 0x11108f0 is omitted. |
| Rule: "rule", |
| }, |
| }, |
| }, |
| Edges: []*Edge{ |
| { |
| Inputs: []int64{0x11109a0}, |
| Outputs: []int64{0x1110870}, // Note 0x11108f0 is omitted. |
| Rule: "rule", |
| }, |
| }, |
| }, |
| }, |
| } { |
| t.Run(tc.desc, func(t *testing.T) { |
| got, err := FromDOT(strings.NewReader(tc.dot)) |
| if err != nil { |
| t.Errorf("FromDOT(%s) failed: %s", tc.dot, err) |
| } |
| opts := []cmp.Option{ |
| cmpopts.EquateEmpty(), |
| cmpopts.IgnoreUnexported(Graph{}, Node{}, Edge{}), |
| orderEdgesByRule, |
| } |
| if diff := cmp.Diff(tc.want, got, opts...); diff != "" { |
| t.Errorf("FromDOT(%s) got diff (-want +got):\n%s", tc.dot, diff) |
| } |
| }) |
| } |
| } |
| |
| func TestFromDOTErrors(t *testing.T) { |
| for _, tc := range []struct { |
| desc string |
| dot string |
| }{ |
| { |
| desc: "multiple edges pointing to the same output", |
| dot: `digraph ninja { |
| "0x13e8900" [label="some_file"] |
| "0x13e8850" [label="touch", shape=ellipse] |
| "0x13e8850" -> "0x13e8900" |
| "0x13e8851" [label="touch", shape=ellipse] |
| "0x13e8851" -> "0x13e8900" |
| }`, |
| }, |
| } { |
| t.Run(tc.desc, func(t *testing.T) { |
| if got, err := FromDOT(strings.NewReader(tc.dot)); err == nil { |
| t.Errorf("FromDOT(%s) got no error, want error, parsed graph:\n%v", tc.dot, got) |
| } |
| }) |
| } |
| } |
| |
| func TestParsingFileFromRealBuild(t *testing.T) { |
| dotFilePath := filepath.Join(*testDataFlag, "graph.dot") |
| dotFile, err := os.Open(dotFilePath) |
| if err != nil { |
| t.Fatalf("Failed to open file %q: %s", dotFilePath, err) |
| } |
| defer dotFile.Close() |
| |
| wantCXXEdge := Edge{ |
| Inputs: []int64{0x17471d0}, |
| Outputs: []int64{0x1747150}, |
| Rule: "cxx", |
| } |
| wantLinkEdge := Edge{ |
| Inputs: []int64{0x1747150, 0x1719e30, 0x1745bc0}, |
| Outputs: []int64{0x1747530}, |
| Rule: "link", |
| } |
| want := Graph{ |
| Nodes: map[int64]*Node{ |
| 0x1747530: {ID: 0x1747530, Path: "gn", In: &wantLinkEdge}, |
| 0x1747150: {ID: 0x1747150, Path: "src/gn/gn_main.o", In: &wantCXXEdge, Outs: []*Edge{&wantLinkEdge}}, |
| 0x17471d0: {ID: 0x17471d0, Path: "../src/gn/gn_main.cc", Outs: []*Edge{&wantCXXEdge}}, |
| 0x1719e30: {ID: 0x1719e30, Path: "base.a", Outs: []*Edge{&wantLinkEdge}}, |
| 0x1745bc0: {ID: 0x1745bc0, Path: "gn_lib.a", Outs: []*Edge{&wantLinkEdge}}, |
| }, |
| Edges: []*Edge{&wantCXXEdge, &wantLinkEdge}, |
| } |
| |
| got, err := FromDOT(dotFile) |
| if err != nil { |
| t.Fatalf("FromDOT failed: %s", err) |
| } |
| opts := []cmp.Option{ |
| cmpopts.IgnoreUnexported(Graph{}, Node{}, Edge{}), |
| orderEdgesByRule, |
| } |
| if diff := cmp.Diff(want, got, opts...); diff != "" { |
| t.Errorf("FromDOT(small gn build graph) =\n%#v\nwant:\n%#v\ndiff(-want +got):\n%s", got, want, diff) |
| } |
| } |
| |
| func TestPopulateEdges(t *testing.T) { |
| for _, tc := range []struct { |
| desc string |
| steps []ninjalog.Step |
| graph Graph |
| wantGraph Graph |
| }{ |
| { |
| desc: "empty graph", |
| }, |
| { |
| desc: "phony edges are skipped", |
| graph: Graph{ |
| Edges: []*Edge{ |
| {Outputs: []int64{0, 1, 2}, Rule: "phony"}, |
| }, |
| }, |
| wantGraph: Graph{ |
| Edges: []*Edge{ |
| {Outputs: []int64{0, 1, 2}, Rule: "phony"}, |
| }, |
| }, |
| }, |
| { |
| desc: "single output", |
| steps: []ninjalog.Step{ |
| {Start: time.Millisecond, End: time.Second, Out: "foo"}, |
| }, |
| graph: Graph{ |
| // `In` and `Outs` edges on nodes are omitted since they don't affect |
| // this test. |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| }, |
| Edges: []*Edge{ |
| {Outputs: []int64{0}}, |
| }, |
| }, |
| wantGraph: Graph{ |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| }, |
| Edges: []*Edge{ |
| { |
| Outputs: []int64{0}, |
| Step: &ninjalog.Step{Start: time.Millisecond, End: time.Second, Out: "foo"}, |
| }, |
| }, |
| }, |
| }, |
| { |
| desc: "multiple outputs", |
| steps: []ninjalog.Step{ |
| {Out: "foo", Outs: []string{"bar", "baz"}}, |
| }, |
| graph: Graph{ |
| // `In` and `Outs` edges on nodes are omitted since they don't affect |
| // this test. |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| 1: {ID: 1, Path: "bar"}, |
| 2: {ID: 2, Path: "baz"}, |
| }, |
| Edges: []*Edge{ |
| {Outputs: []int64{0, 1, 2}}, |
| }, |
| }, |
| wantGraph: Graph{ |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| 1: {ID: 1, Path: "bar"}, |
| 2: {ID: 2, Path: "baz"}, |
| }, |
| Edges: []*Edge{ |
| { |
| Outputs: []int64{0, 1, 2}, |
| Step: &ninjalog.Step{Out: "foo", Outs: []string{"bar", "baz"}}, |
| }, |
| }, |
| }, |
| }, |
| { |
| desc: "multiple edges", |
| steps: []ninjalog.Step{ |
| {Out: "foo"}, |
| {Out: "bar", Outs: []string{"baz"}}, |
| }, |
| graph: Graph{ |
| // `In` and `Outs` edges on nodes are omitted since they don't affect |
| // this test. |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| 1: {ID: 1, Path: "bar"}, |
| 2: {ID: 2, Path: "baz"}, |
| 42: {ID: 42, Path: "truth"}, |
| }, |
| Edges: []*Edge{ |
| {Outputs: []int64{0}}, |
| {Outputs: []int64{1, 2}}, |
| {Outputs: []int64{42}, Rule: "phony"}, |
| }, |
| }, |
| wantGraph: Graph{ |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| 1: {ID: 1, Path: "bar"}, |
| 2: {ID: 2, Path: "baz"}, |
| 42: {ID: 42, Path: "truth"}, |
| }, |
| Edges: []*Edge{ |
| { |
| Outputs: []int64{0}, |
| Step: &ninjalog.Step{Out: "foo"}, |
| }, |
| { |
| Outputs: []int64{1, 2}, |
| Step: &ninjalog.Step{Out: "bar", Outs: []string{"baz"}}, |
| }, |
| { |
| Outputs: []int64{42}, |
| Rule: "phony", |
| }, |
| }, |
| }, |
| }, |
| } { |
| t.Run(tc.desc, func(t *testing.T) { |
| if err := tc.graph.PopulateEdges(tc.steps); err != nil { |
| t.Errorf("PopulateEdges(%v) failed: %v", tc.steps, err) |
| } |
| if diff := cmp.Diff(tc.wantGraph, tc.graph, cmpopts.IgnoreUnexported(Graph{}, Node{}, Edge{})); diff != "" { |
| t.Errorf("PopulateEdges(%v) got graph diff (-want +got):\n%s", tc.steps, diff) |
| } |
| }) |
| } |
| } |
| |
| func TestPopulateEdgesErrors(t *testing.T) { |
| for _, tc := range []struct { |
| desc string |
| steps []ninjalog.Step |
| graph Graph |
| }{ |
| { |
| desc: "steps with duplicate output", |
| steps: []ninjalog.Step{ |
| {Out: "foo", Outs: []string{"bar"}}, |
| {Out: "bar"}, |
| }, |
| }, |
| { |
| desc: "missing step for edge", |
| graph: Graph{ |
| // `In` and `Outs` edges on the Node are not spelled out since they |
| // don't affect this test. |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| }, |
| Edges: []*Edge{ |
| {Outputs: []int64{0}}, |
| }, |
| }, |
| }, |
| { |
| desc: "multiple steps match the same edge", |
| steps: []ninjalog.Step{ |
| {Out: "foo", CmdHash: 123}, |
| {Out: "bar", CmdHash: 456}, |
| }, |
| graph: Graph{ |
| // `In` and `Outs` edges on the Node are not spelled out since they |
| // don't affect this test. |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| 1: {ID: 1, Path: "bar"}, |
| }, |
| Edges: []*Edge{ |
| {Outputs: []int64{0, 1}}, |
| }, |
| }, |
| }, |
| { |
| desc: "outputs in step don't match edge", |
| steps: []ninjalog.Step{ |
| {Out: "foo", CmdHash: 123}, |
| }, |
| graph: Graph{ |
| // `In` and `Outs` edges on the Node are not spelled out since they |
| // don't affect this test. |
| Nodes: map[int64]*Node{ |
| 0: {ID: 0, Path: "foo"}, |
| 1: {ID: 1, Path: "bar"}, |
| }, |
| Edges: []*Edge{ |
| {Outputs: []int64{0, 1}}, |
| }, |
| }, |
| }, |
| } { |
| t.Run(tc.desc, func(t *testing.T) { |
| if err := tc.graph.PopulateEdges(tc.steps); err == nil { |
| t.Errorf("PopulateEdges(%v) got no errors, want error", tc.steps) |
| } |
| }) |
| } |
| } |
| |
| func readTestGraph(tb testing.TB) Graph { |
| ninjaLogPath := filepath.Join(*testDataFlag, "ninja_log") |
| ninjaLogFile, err := os.Open(ninjaLogPath) |
| if err != nil { |
| tb.Fatalf("Failed to open Ninja log with path %s: %v", ninjaLogPath, err) |
| } |
| defer ninjaLogFile.Close() |
| ninjaLog, err := ninjalog.Parse(ninjaLogPath, ninjaLogFile) |
| if err != nil { |
| tb.Fatalf("Failed to parse Ninja log from path %s: %v", ninjaLogPath, err) |
| } |
| steps := ninjalog.Dedup(ninjaLog.Steps) |
| |
| compdbPath := filepath.Join(*testDataFlag, "compdb.json") |
| compdbFile, err := os.Open(compdbPath) |
| if err != nil { |
| tb.Fatalf("Failed to open compdb with path %s: %v", compdbPath, err) |
| } |
| defer compdbFile.Close() |
| commands, err := compdb.Parse(compdbFile) |
| if err != nil { |
| tb.Fatalf("Failed to parse compdb from path %s: %v", compdbPath, err) |
| } |
| steps = ninjalog.Populate(steps, commands) |
| |
| dotFilePath := filepath.Join(*testDataFlag, "graph.dot") |
| dotFile, err := os.Open(dotFilePath) |
| if err != nil { |
| tb.Fatalf("Failed to open Ninja graph with path %s: %v", dotFilePath, err) |
| } |
| defer dotFile.Close() |
| graph, err := FromDOT(dotFile) |
| if err != nil { |
| tb.Fatalf("Failed to parse Ninja graph from path %s: %v", dotFilePath, err) |
| } |
| |
| if err := graph.PopulateEdges(steps); err != nil { |
| tb.Fatalf("Failed to populate parsed Ninja graph with deduplicated steps: %v", err) |
| } |
| return graph |
| } |
| |
| func TestPopulateEdgesWithRealBuild(t *testing.T) { |
| graph := readTestGraph(t) |
| for _, e := range graph.Edges { |
| if isPhony, gotNilStep := e.Rule == "phony", e.Step == nil; isPhony != gotNilStep { |
| var outputs []string |
| for _, output := range e.Outputs { |
| outputs = append(outputs, graph.Nodes[output].Path) |
| } |
| t.Errorf("Invalid edge after `PopulateEdges`, isPhony (%t) != gotNilStep (%t), outputs of this edge: %v", isPhony, gotNilStep, outputs) |
| } |
| } |
| } |
| |
| func BenchmarkCriticalPath(b *testing.B) { |
| b.Run("CriticalPath", func(b *testing.B) { |
| for i := 0; i < b.N; i++ { |
| graph := readTestGraph(b) |
| if _, err := graph.CriticalPath(); err != nil { |
| b.Fatalf("CriticalPath() got error: %v", err) |
| } |
| } |
| }) |
| |
| b.Run("CriticalPathV2", func(b *testing.B) { |
| for i := 0; i < b.N; i++ { |
| graph := readTestGraph(b) |
| if _, err := graph.CriticalPathV2(); err != nil { |
| b.Fatalf("CriticalPathV2() got error: %v", err) |
| } |
| } |
| }) |
| } |
| |
| func TestCriticalPath(t *testing.T) { |
| step1 := ninjalog.Step{End: 5} |
| edge1 := &Edge{Outputs: []int64{1}, Step: &step1} |
| |
| step2 := ninjalog.Step{Start: 5, End: 10, Out: "2"} |
| edge2 := &Edge{Inputs: []int64{1}, Outputs: []int64{2}, Step: &step2} |
| |
| step3 := ninjalog.Step{Start: 42, End: 420, Out: "3"} |
| edge3 := &Edge{Inputs: []int64{2}, Outputs: []int64{3}, Step: &step3} |
| |
| edge3Phony := &Edge{Inputs: []int64{2}, Outputs: []int64{3}, Rule: "phony"} |
| |
| step4 := ninjalog.Step{End: 100, Out: "4"} |
| edge4 := &Edge{Inputs: []int64{3}, Outputs: []int64{4}, Step: &step4} |
| |
| step4LateStart := ninjalog.Step{Start: 99, End: 100, Out: "4"} |
| edge4LateStart := &Edge{Inputs: []int64{3}, Outputs: []int64{4}, Step: &step4LateStart} |
| |
| step5 := ninjalog.Step{Start: 100, End: 200, Out: "5"} |
| edge5 := &Edge{Inputs: []int64{2, 4}, Outputs: []int64{5}, Step: &step5} |
| |
| clearEdgeMemoizations := func() { |
| for _, e := range []*Edge{edge1, edge2, edge3, edge4, edge4LateStart, edge5} { |
| e.earliestStart = nil |
| e.latestFinish = nil |
| } |
| } |
| |
| for _, tc := range []struct { |
| desc string |
| graph Graph |
| want []ninjalog.Step |
| }{ |
| { |
| desc: "empty graph", |
| }, |
| { |
| // 1 -> 2 -> 3 |
| desc: "single inputs", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1, Outs: []*Edge{edge2}}, |
| 2: {ID: 2, In: edge2, Outs: []*Edge{edge3}}, |
| 3: {ID: 3, In: edge3}, |
| }, |
| Edges: []*Edge{edge2, edge3}, |
| }, |
| want: []ninjalog.Step{step2, step3}, |
| }, |
| { |
| // 1 -> 2 --phony--> 3 |
| desc: "phony edge", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1, Outs: []*Edge{edge2}}, |
| 2: {ID: 2, In: edge2, Outs: []*Edge{edge3Phony}}, |
| 3: {ID: 3, In: edge3Phony}, |
| }, |
| Edges: []*Edge{edge2, edge3Phony}, |
| }, |
| want: []ninjalog.Step{step2}, // Phony edge is not included. |
| }, |
| { |
| // -> 1 -> 2 -> 3 |
| desc: "edge with no input file", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1, In: edge1, Outs: []*Edge{edge2}}, |
| 2: {ID: 2, In: edge2, Outs: []*Edge{edge3}}, |
| 3: {ID: 3, In: edge3}, |
| }, |
| Edges: []*Edge{edge1, edge2, edge3}, |
| }, |
| want: []ninjalog.Step{step1, step2, step3}, |
| }, |
| { |
| // 1 -> 2 ---> 5 |
| // / |
| // 3 -> 4 - |
| desc: "multiple inputs same start time", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| // `Outs` edges on nodes are omitted since they don't affect this test. |
| 1: {ID: 1, Outs: []*Edge{edge2}}, |
| 2: {ID: 2, In: edge2, Outs: []*Edge{edge5}}, |
| |
| 3: {ID: 3, Outs: []*Edge{edge4}}, |
| 4: {ID: 4, In: edge4, Outs: []*Edge{edge5}}, |
| |
| 5: {ID: 5, In: edge5}, |
| }, |
| // `Edges` are omitted since they don't affect this test. |
| Edges: []*Edge{edge2, edge4, edge5}, |
| }, |
| want: []ninjalog.Step{step4, step5}, |
| }, |
| { |
| // 1 -> 2 ---> 5 |
| // / |
| // 3 -> 4 - |
| desc: "multiple inputs different start times", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| // `Outs` edges on nodes are omitted since they don't affect this test. |
| 1: {ID: 1, Outs: []*Edge{edge2}}, |
| 2: {ID: 2, In: edge2, Outs: []*Edge{edge5}}, |
| |
| 3: {ID: 3, Outs: []*Edge{edge4LateStart}}, |
| 4: {ID: 4, In: edge4LateStart, Outs: []*Edge{edge5}}, |
| |
| 5: {ID: 5, In: edge5}, |
| }, |
| Edges: []*Edge{edge2, edge4LateStart, edge5}, |
| }, |
| want: []ninjalog.Step{step2, step5}, |
| }, |
| } { |
| t.Run(tc.desc, func(t *testing.T) { |
| // Clear memoization fields because we are reusing pointers to edges. |
| defer clearEdgeMemoizations() |
| |
| got, err := tc.graph.CriticalPath() |
| if err != nil { |
| t.Fatalf("CriticalPath() got error: %v", err) |
| } |
| if diff := cmp.Diff(tc.want, got); diff != "" { |
| t.Errorf("CriticalPath() got diff (-want, +got):\n%s", diff) |
| } |
| |
| got, err = tc.graph.CriticalPathV2() |
| if err != nil { |
| t.Fatalf("CriticalPathV2() got error: %v", err) |
| } |
| if diff := cmp.Diff(tc.want, got); diff != "" { |
| t.Errorf("CriticalPathV2() got diff (-want +got):\n%s", diff) |
| } |
| }) |
| } |
| } |
| |
| func TestCriticalPathErrors(t *testing.T) { |
| edge2 := &Edge{Inputs: []int64{1}, Outputs: []int64{2}, Step: &ninjalog.Step{End: 10, Out: "2"}} |
| edge2WithNoStep := &Edge{Inputs: []int64{1}, Outputs: []int64{2}} |
| |
| for _, tc := range []struct { |
| desc string |
| graph Graph |
| }{ |
| { |
| desc: "edge missing step", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1}, |
| 2: {ID: 2, In: edge2WithNoStep}, |
| }, |
| Edges: []*Edge{edge2WithNoStep}, |
| }, |
| }, |
| { |
| desc: "missing input node", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 2: {ID: 2, In: edge2}, |
| }, |
| Edges: []*Edge{edge2}, |
| }, |
| }, |
| } { |
| t.Run(tc.desc, func(t *testing.T) { |
| if _, err := tc.graph.CriticalPath(); err == nil { |
| t.Error("CriticalPath() got no error, want error") |
| } |
| }) |
| } |
| } |
| |
| func TestAddSink(t *testing.T) { |
| edge2 := &Edge{Inputs: []int64{1}, Outputs: []int64{2}} |
| edge3 := &Edge{Inputs: []int64{1}, Outputs: []int64{3}} |
| |
| for _, v := range []struct { |
| desc string |
| graph Graph |
| want []*Edge |
| }{ |
| { |
| desc: "empty graph", |
| }, |
| { |
| // 1 -> 2 |
| desc: "single pure output", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1, Outs: []*Edge{edge2}}, |
| 2: {ID: 2, In: edge2}, |
| }, |
| Edges: []*Edge{edge2}, |
| }, |
| want: []*Edge{ |
| edge2, |
| { |
| Inputs: []int64{2}, |
| Rule: ninjagoArtificialSinkRule, |
| Step: &ninjalog.Step{}, |
| }, |
| }, |
| }, |
| { |
| // 1 ----> 2 |
| // \ |
| // --> 3 |
| desc: "multiple pure outputs", |
| graph: Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1, Outs: []*Edge{edge2, edge3}}, |
| 2: {ID: 2, In: edge2}, |
| 3: {ID: 3, In: edge3}, |
| }, |
| Edges: []*Edge{edge2, edge3}, |
| }, |
| want: []*Edge{ |
| edge2, |
| edge3, |
| { |
| Inputs: []int64{2, 3}, |
| Rule: ninjagoArtificialSinkRule, |
| Step: &ninjalog.Step{}, |
| }, |
| }, |
| }, |
| } { |
| t.Run(v.desc, func(t *testing.T) { |
| if err := v.graph.addSink(); err != nil { |
| t.Fatalf("addSink() got error: %v", err) |
| } |
| opts := []cmp.Option{ |
| cmpopts.IgnoreUnexported(Edge{}), |
| // Input IDs on sink edge has indeterministic order. |
| cmpopts.SortSlices(func(i, j int64) bool { return i < j }), |
| } |
| if diff := cmp.Diff(v.graph.Edges, v.want, opts...); diff != "" { |
| t.Errorf("After addSink(), got graph.Edges diff (-want, +got):\n%s", diff) |
| } |
| |
| // addSink should be idempotent. |
| if err := v.graph.addSink(); err != nil { |
| t.Fatalf("addSink() got error: %v", err) |
| } |
| if diff := cmp.Diff(v.graph.Edges, v.want, opts...); diff != "" { |
| t.Errorf("After addSink(), got graph.Edges diff (-want, +got):\n%s", diff) |
| } |
| }) |
| } |
| } |
| |
| func TestTotalFloat(t *testing.T) { |
| step1 := ninjalog.Step{End: 10} |
| edge1 := &Edge{ |
| Outputs: []int64{1}, |
| Step: &step1, |
| } |
| |
| step2 := ninjalog.Step{Start: 10, End: 30} |
| edge2 := &Edge{ |
| Inputs: []int64{1}, |
| Outputs: []int64{2}, |
| Step: &step2, |
| } |
| |
| step3 := ninjalog.Step{Start: 30, End: 35} |
| edge3 := &Edge{ |
| Inputs: []int64{2}, |
| Outputs: []int64{3}, |
| Step: &step3, |
| } |
| |
| step4 := ninjalog.Step{Start: 35, End: 45} |
| edge4 := &Edge{ |
| Inputs: []int64{3}, |
| Outputs: []int64{4}, |
| Step: &step4, |
| } |
| |
| step5 := ninjalog.Step{Start: 45, End: 65} |
| edge5 := &Edge{ |
| Inputs: []int64{4, 7, 8}, |
| Outputs: []int64{5}, |
| Step: &step5, |
| } |
| |
| step6 := ninjalog.Step{Start: 10, End: 25} |
| edge6 := &Edge{ |
| Inputs: []int64{1}, |
| Outputs: []int64{6}, |
| Step: &step6, |
| } |
| |
| step7 := ninjalog.Step{Start: 35, End: 40} |
| edge7 := &Edge{ |
| Inputs: []int64{3, 6}, |
| Outputs: []int64{7}, |
| Step: &step7, |
| } |
| |
| step8 := ninjalog.Step{Start: 10, End: 25} |
| edge8 := &Edge{ |
| Inputs: []int64{1}, |
| Outputs: []int64{8}, |
| Step: &step8, |
| } |
| |
| // Test graph based on https://en.wikipedia.org/wiki/Critical_path_drag#/media/File:SimpleAONwDrag3.png. |
| g := Graph{ |
| Nodes: map[int64]*Node{ |
| 1: {ID: 1, In: edge1, Outs: []*Edge{edge2, edge6, edge8}}, |
| 2: {ID: 2, In: edge2, Outs: []*Edge{edge3}}, |
| 3: {ID: 3, In: edge3, Outs: []*Edge{edge4, edge7}}, |
| 4: {ID: 4, In: edge4, Outs: []*Edge{edge5}}, |
| |
| 5: {ID: 5, In: edge5}, |
| |
| 6: {ID: 6, In: edge6, Outs: []*Edge{edge7}}, |
| 7: {ID: 7, In: edge7, Outs: []*Edge{edge5}}, |
| |
| 8: {ID: 8, In: edge8, Outs: []*Edge{edge5}}, |
| }, |
| Edges: []*Edge{edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8}, |
| } |
| |
| t.Log(`In graph: |
| -----> 6 ----------> 7 -- |
| / / \ |
| / / \ |
| 1 -----> 2 -----> 3 -----> 4 ----->5 |
| \ / |
| \ / |
| -----------> 8 ----------`) |
| |
| wantCriticalPath := []ninjalog.Step{step1, step2, step3, step4, step5} |
| |
| got, err := g.CriticalPath() |
| if err != nil { |
| t.Fatalf("CriticalPath failed: %v", err) |
| } |
| if diff := cmp.Diff(wantCriticalPath, got); diff != "" { |
| t.Errorf("CriticalPath got: %v, want: %v, diff (-want +got):\n%s", got, wantCriticalPath, diff) |
| } |
| |
| got, err = g.CriticalPathV2() |
| if err != nil { |
| t.Fatalf("CriticalPathV2 failed: %v", err) |
| } |
| if diff := cmp.Diff(wantCriticalPath, got); diff != "" { |
| t.Errorf("CriticalPathV2 got: %v, want: %v, diff (-want +got):\n%s", got, wantCriticalPath, diff) |
| } |
| |
| for _, want := range []struct { |
| input *Edge |
| parallelizables []*Edge |
| }{ |
| {input: edge1}, |
| {input: edge2, parallelizables: []*Edge{edge6, edge8}}, |
| {input: edge3, parallelizables: []*Edge{edge6, edge8}}, |
| {input: edge4, parallelizables: []*Edge{edge7, edge8}}, |
| {input: edge5}, |
| } { |
| got, err := g.parallelizableEdges(want.input) |
| if err != nil { |
| t.Errorf("parallelizableEdges(edge outputting %v) error: %v", want.input.Outputs, err) |
| } |
| if !cmp.Equal(got, want.parallelizables, cmpopts.IgnoreUnexported(Edge{})) { |
| t.Errorf("parallelizableEdges(edge outputting %v) = %s, want: %s", want.input.Outputs, edgesToStr(got), edgesToStr(want.parallelizables)) |
| } |
| } |
| |
| for _, want := range []struct { |
| input *Edge |
| earliestStart time.Duration |
| earliestFinish time.Duration |
| latestStart time.Duration |
| latestFinish time.Duration |
| totalFloat time.Duration |
| }{ |
| { |
| input: edge1, |
| earliestStart: 0, |
| earliestFinish: 10, |
| latestStart: 0, |
| latestFinish: 10, |
| totalFloat: 0, |
| }, |
| { |
| input: edge2, |
| earliestStart: 10, |
| earliestFinish: 30, |
| latestStart: 10, |
| latestFinish: 30, |
| totalFloat: 0, |
| }, |
| { |
| input: edge3, |
| earliestStart: 30, |
| earliestFinish: 35, |
| latestStart: 30, |
| latestFinish: 35, |
| totalFloat: 0, |
| }, |
| { |
| input: edge4, |
| earliestStart: 35, |
| earliestFinish: 45, |
| latestStart: 35, |
| latestFinish: 45, |
| totalFloat: 0, |
| }, |
| { |
| input: edge5, |
| earliestStart: 45, |
| earliestFinish: 65, |
| latestStart: 45, |
| latestFinish: 65, |
| totalFloat: 0, |
| }, |
| { |
| input: edge6, |
| earliestStart: 10, |
| earliestFinish: 25, |
| latestStart: 25, |
| latestFinish: 40, |
| totalFloat: 15, |
| }, |
| { |
| input: edge7, |
| earliestStart: 35, |
| earliestFinish: 40, |
| latestStart: 40, |
| latestFinish: 45, |
| totalFloat: 5, |
| }, |
| { |
| input: edge8, |
| earliestStart: 10, |
| earliestFinish: 25, |
| latestStart: 30, |
| latestFinish: 45, |
| totalFloat: 20, |
| }, |
| } { |
| for _, fn := range []struct { |
| name string |
| f func(*Edge) (time.Duration, error) |
| want time.Duration |
| }{ |
| {name: "earliestStart", f: g.earliestStart, want: want.earliestStart}, |
| {name: "earliestFinish", f: g.earliestFinish, want: want.earliestFinish}, |
| {name: "latestStart", f: g.latestStart, want: want.latestStart}, |
| {name: "latestFinish", f: g.latestFinish, want: want.latestFinish}, |
| {name: "totalFloat", f: g.totalFloat, want: want.totalFloat}, |
| } { |
| if got := mustDuration(t, want.input, fn.f); got != fn.want { |
| t.Errorf("%s(edge outputting %v) = %s, want: %s", fn.name, want.input.Outputs, got, fn.want) |
| } |
| } |
| } |
| |
| for _, want := range []struct { |
| input *Edge |
| err bool |
| drag time.Duration |
| }{ |
| {input: edge1, drag: 10}, |
| {input: edge2, drag: 15}, |
| {input: edge3, drag: 5}, |
| {input: edge4, drag: 5}, |
| {input: edge5, drag: 20}, |
| {input: edge6, err: true}, |
| {input: edge7, err: true}, |
| {input: edge8, err: true}, |
| } { |
| got, err := g.drag(want.input) |
| if (err != nil) != want.err { |
| t.Errorf("drag(edge outputting %v) got error: %v, want error: %t", want.input.Outputs, err, want.err) |
| } |
| if got != want.drag { |
| t.Errorf("drag(edge outputting %v) = %s, want: %s", want.input.Outputs, got, want.drag) |
| } |
| } |
| } |
| |
| func edgesToStr(edges []*Edge) string { |
| var ss []string |
| for _, e := range edges { |
| ss = append(ss, fmt.Sprintf("edge outputting %v", e.Outputs)) |
| } |
| return "[" + strings.Join(ss, ", ") + "]" |
| } |
| |
| func mustDuration(t *testing.T, edge *Edge, f func(*Edge) (time.Duration, error)) time.Duration { |
| t.Helper() |
| d, err := f(edge) |
| if err != nil { |
| t.Fatalf("Failed to get duration: %v", err) |
| } |
| return d |
| } |
