tools/build/ninjago/ninjagraph/ninjagraph_test.go - fuchsia - Git at Google

 // 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 (
 	"compress/gzip"
 	"flag"
 	"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 testDataDir = 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(*testDataDir, "graph.dot.gz")
 	dotFile, err := os.Open(dotFilePath)
 	if err != nil {
 		t.Fatalf("Failed to open file %q: %s", dotFilePath, err)
 	}
 	defer dotFile.Close()

 	dotFileUnzipped, err := gzip.NewReader(dotFile)
 	if err != nil {
 		t.Fatalf("Failed to unzip file %q: %s", dotFilePath, err)
 	}
 	defer dotFileUnzipped.Close()

 	got, err := FromDOT(dotFileUnzipped)
 	if err != nil {
 		t.Fatalf("FromDOT failed: %s", err)
 	}
 	if gotNodes := len(got.Nodes); gotNodes != 12369 {
 		t.Errorf("FromDOT(Zircon build graph) got %d nodes, want 12369", gotNodes)
 	}
 	if gotEdges := len(got.Edges); gotEdges != 10568 {
 		t.Errorf("FromDOT(Zircon build graph) got %d edges, want 10567", gotEdges)
 	}
 }

 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",
 					},
 				},
 			},
 		},
 		{
 			desc: "partial graph with missing steps",
 			steps: []ninjalog.Step{
 				{Out: "bar"},
 			},
 			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"},
 				},
 				Edges: []*Edge{
 					{Outputs: []int64{0}},
 					{Outputs: []int64{1}},
 				},
 			},
 			wantGraph: Graph{
 				Nodes: map[int64]*Node{
 					0: {ID: 0, Path: "foo"},
 					1: {ID: 1, Path: "bar"},
 				},
 				Edges: []*Edge{
 					{
 						Outputs: []int64{0},
 					},
 					{
 						Outputs: []int64{1},
 						Step:    &ninjalog.Step{Out: "bar"},
 					},
 				},
 			},
 		},
 	} {
 		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: "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}},
 				},
 			},
 		},
 	} {
 		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 readAndUnzip(tb testing.TB, path string) *gzip.Reader {
 	f, err := os.Open(path)
 	if err != nil {
 		tb.Fatalf("Failed to read %q: %v", path, err)
 	}
 	tb.Cleanup(func() { f.Close() })

 	unzipped, err := gzip.NewReader(f)
 	if err != nil {
 		tb.Fatalf("Failed to unzip %q: %v", path, err)
 	}
 	tb.Cleanup(func() { unzipped.Close() })
 	return unzipped
 }

 func readTestGraph(tb testing.TB) Graph {
 	ninjaLogPath := filepath.Join(*testDataDir, "ninja_log.gz")
 	ninjaLog, err := ninjalog.Parse(ninjaLogPath, readAndUnzip(tb, ninjaLogPath))
 	if err != nil {
 		tb.Fatalf("Failed to parse Ninja log %q: %v", ninjaLogPath, err)
 	}
 	steps := ninjalog.Dedup(ninjaLog.Steps)

 	compdbPath := filepath.Join(*testDataDir, "compdb.json.gz")
 	commands, err := compdb.Parse(readAndUnzip(tb, compdbPath))
 	if err != nil {
 		tb.Fatalf("Failed to parse compdb from path %q: %v", compdbPath, err)
 	}
 	steps = ninjalog.Populate(steps, commands)

 	dotFilePath := filepath.Join(*testDataDir, "graph.dot.gz")
 	graph, err := FromDOT(readAndUnzip(tb, dotFilePath))
 	if err != nil {
 		tb.Fatalf("Failed to parse Ninja graph %q: %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 TestWithStepsOnly(t *testing.T) {
 	edge2 := &Edge{Inputs: []int64{1}, Outputs: []int64{2}, Step: &ninjalog.Step{Out: "2"}}
 	edge2NoStep := &Edge{Inputs: []int64{1}, Outputs: []int64{2}}

 	edge4Phony := &Edge{Inputs: []int64{3}, Outputs: []int64{4}, Rule: "phony"}
 	edge4NoStep := &Edge{Inputs: []int64{3}, Outputs: []int64{4}}

 	edge5 := &Edge{Inputs: []int64{2, 4}, Outputs: []int64{5}, Step: &ninjalog.Step{Out: "5"}}
 	edge5NoStep := &Edge{Inputs: []int64{2, 4}, Outputs: []int64{5}}

 	edge6 := &Edge{Inputs: []int64{5}, Outputs: []int64{6}, Step: &ninjalog.Step{Out: "6"}}
 	edge6NoStep := &Edge{Inputs: []int64{5}, Outputs: []int64{6}}

 	for _, tc := range []struct {
 		desc string
 		g    Graph
 		want Graph
 	}{
 		{
 			desc: "empty graph",
 			g:    Graph{},
 			want: Graph{},
 		},
 		{
 			desc: "partial graph",
 			//     1 -> 2 -no step-> 5 -> 6
 			//               /
 			// 3 -phony-> 4 -
 			g: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge2}},
 					2: {ID: 2, In: edge2, Outs: []*Edge{edge5NoStep}},
 					3: {ID: 3, Outs: []*Edge{edge4Phony}},
 					4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5NoStep}},
 					5: {ID: 5, In: edge5NoStep, Outs: []*Edge{edge6}},
 					6: {ID: 6, In: edge6},
 				},
 				Edges: []*Edge{edge2, edge4Phony, edge5NoStep, edge6},
 			},
 			// 1 -> 2  5 -> 6
 			// 3 -phony-> 4
 			want: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge2}},
 					2: {ID: 2, In: edge2},
 					3: {ID: 3, Outs: []*Edge{edge4Phony}},
 					4: {ID: 4, In: edge4Phony},
 					5: {ID: 5, Outs: []*Edge{edge6}},
 					6: {ID: 6, In: edge6},
 				},
 				Edges: []*Edge{edge2, edge4Phony, edge6},
 			},
 		},
 		{
 			desc: "yet another partial graph",
 			// 1 -no step-> 2 ---> 5 -no step-> 6
 			//                 /
 			//   3 -phony-> 4 -
 			g: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge2NoStep}},
 					2: {ID: 2, In: edge2NoStep, Outs: []*Edge{edge5}},
 					3: {ID: 3, Outs: []*Edge{edge4Phony}},
 					4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
 					5: {ID: 5, In: edge5, Outs: []*Edge{edge6NoStep}},
 					6: {ID: 6, In: edge6NoStep},
 				},
 				Edges: []*Edge{edge2NoStep, edge4Phony, edge5, edge6NoStep},
 			},
 			//              2 ---> 5
 			//                 /
 			//   3 -phony-> 4 -
 			want: Graph{
 				Nodes: map[int64]*Node{
 					2: {ID: 2, Outs: []*Edge{edge5}},
 					3: {ID: 3, Outs: []*Edge{edge4Phony}},
 					4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
 					5: {ID: 5, In: edge5},
 				},
 				Edges: []*Edge{edge4Phony, edge5},
 			},
 		},
 		{
 			desc: "full graph because all steps are populated",
 			//        1 -> 2 --> 5 -> 6
 			//               /
 			// 3 -phony-> 4 -
 			g: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge2}},
 					2: {ID: 2, In: edge2, Outs: []*Edge{edge5}},
 					3: {ID: 3, Outs: []*Edge{edge4Phony}},
 					4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
 					5: {ID: 5, In: edge5, Outs: []*Edge{edge6}},
 					6: {ID: 6, In: edge6},
 				},
 				Edges: []*Edge{edge2, edge4Phony, edge5, edge6},
 			},
 			// 1 -> 2  5 -> 6
 			// 3 -phony-> 4
 			want: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge2}},
 					2: {ID: 2, In: edge2, Outs: []*Edge{edge5}},
 					3: {ID: 3, Outs: []*Edge{edge4Phony}},
 					4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
 					5: {ID: 5, In: edge5, Outs: []*Edge{edge6}},
 					6: {ID: 6, In: edge6},
 				},
 				Edges: []*Edge{edge2, edge4Phony, edge5, edge6},
 			},
 		},
 		{
 			desc: "result graph empty because no steps are populated",
 			// 1 -no step-> 2 -no step-> 5 -no step-> 6
 			//                   /
 			//   3 -no step-> 4 -
 			g: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge2NoStep}},
 					2: {ID: 2, In: edge2NoStep, Outs: []*Edge{edge5NoStep}},
 					3: {ID: 3, Outs: []*Edge{edge4NoStep}},
 					4: {ID: 4, In: edge4NoStep, Outs: []*Edge{edge5NoStep}},
 					5: {ID: 5, In: edge5NoStep, Outs: []*Edge{edge6NoStep}},
 					6: {ID: 6, In: edge6NoStep},
 				},
 				Edges: []*Edge{edge2NoStep, edge4NoStep, edge5NoStep, edge6NoStep},
 			},
 			want: Graph{},
 		},
 	} {
 		t.Run(tc.desc, func(t *testing.T) {
 			got, err := WithStepsOnly(tc.g)
 			if err != nil {
 				t.Errorf("WithStepsOnly got error: %v", err)
 			}
 			opts := []cmp.Option{
 				cmpopts.EquateEmpty(),
 				cmpopts.IgnoreUnexported(Graph{}, Node{}, Edge{}),
 			}
 			if diff := cmp.Diff(tc.want, got, opts...); diff != "" {
 				t.Errorf("WithStepsOnly got output graph diff (-want +got):\n%s", diff)
 			}
 		})
 	}
 }

 func TestWithStepsOnlyErrors(t *testing.T) {
 	edge := &Edge{Inputs: []int64{1}, Outputs: []int64{2}, Step: &ninjalog.Step{Out: "2"}}

 	for _, tc := range []struct {
 		desc string
 		g    Graph
 	}{
 		{
 			desc: "missing node",
 			g: Graph{
 				Edges: []*Edge{edge},
 			},
 		},
 		{
 			desc: "duplicate edges",
 			g: Graph{
 				Nodes: map[int64]*Node{
 					1: {ID: 1, Outs: []*Edge{edge}},
 					2: {ID: 2, In: edge},
 				},
 				Edges: []*Edge{edge, edge},
 			},
 		},
 	} {
 		t.Run(tc.desc, func(t *testing.T) {
 			if _, err := WithStepsOnly(tc.g); err == nil {
 				t.Error("WithStepsOnly got no error, want non-nil error")
 			}
 		})
 	}
 }
	// 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 (
	"compress/gzip"
	"flag"
	"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 testDataDir = 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(*testDataDir, "graph.dot.gz")
	dotFile, err := os.Open(dotFilePath)
	if err != nil {
	t.Fatalf("Failed to open file %q: %s", dotFilePath, err)
	}
	defer dotFile.Close()

	dotFileUnzipped, err := gzip.NewReader(dotFile)
	if err != nil {
	t.Fatalf("Failed to unzip file %q: %s", dotFilePath, err)
	}
	defer dotFileUnzipped.Close()

	got, err := FromDOT(dotFileUnzipped)
	if err != nil {
	t.Fatalf("FromDOT failed: %s", err)
	}
	if gotNodes := len(got.Nodes); gotNodes != 12369 {
	t.Errorf("FromDOT(Zircon build graph) got %d nodes, want 12369", gotNodes)
	}
	if gotEdges := len(got.Edges); gotEdges != 10568 {
	t.Errorf("FromDOT(Zircon build graph) got %d edges, want 10567", gotEdges)
	}
	}

	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",
	},
	},
	},
	},
	{
	desc: "partial graph with missing steps",
	steps: []ninjalog.Step{
	{Out: "bar"},
	},
	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"},
	},
	Edges: []*Edge{
	{Outputs: []int64{0}},
	{Outputs: []int64{1}},
	},
	},
	wantGraph: Graph{
	Nodes: map[int64]*Node{
	0: {ID: 0, Path: "foo"},
	1: {ID: 1, Path: "bar"},
	},
	Edges: []*Edge{
	{
	Outputs: []int64{0},
	},
	{
	Outputs: []int64{1},
	Step: &ninjalog.Step{Out: "bar"},
	},
	},
	},
	},
	} {
	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: "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}},
	},
	},
	},
	} {
	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 readAndUnzip(tb testing.TB, path string) *gzip.Reader {
	f, err := os.Open(path)
	if err != nil {
	tb.Fatalf("Failed to read %q: %v", path, err)
	}
	tb.Cleanup(func() { f.Close() })

	unzipped, err := gzip.NewReader(f)
	if err != nil {
	tb.Fatalf("Failed to unzip %q: %v", path, err)
	}
	tb.Cleanup(func() { unzipped.Close() })
	return unzipped
	}

	func readTestGraph(tb testing.TB) Graph {
	ninjaLogPath := filepath.Join(*testDataDir, "ninja_log.gz")
	ninjaLog, err := ninjalog.Parse(ninjaLogPath, readAndUnzip(tb, ninjaLogPath))
	if err != nil {
	tb.Fatalf("Failed to parse Ninja log %q: %v", ninjaLogPath, err)
	}
	steps := ninjalog.Dedup(ninjaLog.Steps)

	compdbPath := filepath.Join(*testDataDir, "compdb.json.gz")
	commands, err := compdb.Parse(readAndUnzip(tb, compdbPath))
	if err != nil {
	tb.Fatalf("Failed to parse compdb from path %q: %v", compdbPath, err)
	}
	steps = ninjalog.Populate(steps, commands)

	dotFilePath := filepath.Join(*testDataDir, "graph.dot.gz")
	graph, err := FromDOT(readAndUnzip(tb, dotFilePath))
	if err != nil {
	tb.Fatalf("Failed to parse Ninja graph %q: %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 TestWithStepsOnly(t *testing.T) {
	edge2 := &Edge{Inputs: []int64{1}, Outputs: []int64{2}, Step: &ninjalog.Step{Out: "2"}}
	edge2NoStep := &Edge{Inputs: []int64{1}, Outputs: []int64{2}}

	edge4Phony := &Edge{Inputs: []int64{3}, Outputs: []int64{4}, Rule: "phony"}
	edge4NoStep := &Edge{Inputs: []int64{3}, Outputs: []int64{4}}

	edge5 := &Edge{Inputs: []int64{2, 4}, Outputs: []int64{5}, Step: &ninjalog.Step{Out: "5"}}
	edge5NoStep := &Edge{Inputs: []int64{2, 4}, Outputs: []int64{5}}

	edge6 := &Edge{Inputs: []int64{5}, Outputs: []int64{6}, Step: &ninjalog.Step{Out: "6"}}
	edge6NoStep := &Edge{Inputs: []int64{5}, Outputs: []int64{6}}

	for _, tc := range []struct {
	desc string
	g Graph
	want Graph
	}{
	{
	desc: "empty graph",
	g: Graph{},
	want: Graph{},
	},
	{
	desc: "partial graph",
	// 1 -> 2 -no step-> 5 -> 6
	// /
	// 3 -phony-> 4 -
	g: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge2}},
	2: {ID: 2, In: edge2, Outs: []*Edge{edge5NoStep}},
	3: {ID: 3, Outs: []*Edge{edge4Phony}},
	4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5NoStep}},
	5: {ID: 5, In: edge5NoStep, Outs: []*Edge{edge6}},
	6: {ID: 6, In: edge6},
	},
	Edges: []*Edge{edge2, edge4Phony, edge5NoStep, edge6},
	},
	// 1 -> 2 5 -> 6
	// 3 -phony-> 4
	want: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge2}},
	2: {ID: 2, In: edge2},
	3: {ID: 3, Outs: []*Edge{edge4Phony}},
	4: {ID: 4, In: edge4Phony},
	5: {ID: 5, Outs: []*Edge{edge6}},
	6: {ID: 6, In: edge6},
	},
	Edges: []*Edge{edge2, edge4Phony, edge6},
	},
	},
	{
	desc: "yet another partial graph",
	// 1 -no step-> 2 ---> 5 -no step-> 6
	// /
	// 3 -phony-> 4 -
	g: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge2NoStep}},
	2: {ID: 2, In: edge2NoStep, Outs: []*Edge{edge5}},
	3: {ID: 3, Outs: []*Edge{edge4Phony}},
	4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
	5: {ID: 5, In: edge5, Outs: []*Edge{edge6NoStep}},
	6: {ID: 6, In: edge6NoStep},
	},
	Edges: []*Edge{edge2NoStep, edge4Phony, edge5, edge6NoStep},
	},
	// 2 ---> 5
	// /
	// 3 -phony-> 4 -
	want: Graph{
	Nodes: map[int64]*Node{
	2: {ID: 2, Outs: []*Edge{edge5}},
	3: {ID: 3, Outs: []*Edge{edge4Phony}},
	4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
	5: {ID: 5, In: edge5},
	},
	Edges: []*Edge{edge4Phony, edge5},
	},
	},
	{
	desc: "full graph because all steps are populated",
	// 1 -> 2 --> 5 -> 6
	// /
	// 3 -phony-> 4 -
	g: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge2}},
	2: {ID: 2, In: edge2, Outs: []*Edge{edge5}},
	3: {ID: 3, Outs: []*Edge{edge4Phony}},
	4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
	5: {ID: 5, In: edge5, Outs: []*Edge{edge6}},
	6: {ID: 6, In: edge6},
	},
	Edges: []*Edge{edge2, edge4Phony, edge5, edge6},
	},
	// 1 -> 2 5 -> 6
	// 3 -phony-> 4
	want: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge2}},
	2: {ID: 2, In: edge2, Outs: []*Edge{edge5}},
	3: {ID: 3, Outs: []*Edge{edge4Phony}},
	4: {ID: 4, In: edge4Phony, Outs: []*Edge{edge5}},
	5: {ID: 5, In: edge5, Outs: []*Edge{edge6}},
	6: {ID: 6, In: edge6},
	},
	Edges: []*Edge{edge2, edge4Phony, edge5, edge6},
	},
	},
	{
	desc: "result graph empty because no steps are populated",
	// 1 -no step-> 2 -no step-> 5 -no step-> 6
	// /
	// 3 -no step-> 4 -
	g: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge2NoStep}},
	2: {ID: 2, In: edge2NoStep, Outs: []*Edge{edge5NoStep}},
	3: {ID: 3, Outs: []*Edge{edge4NoStep}},
	4: {ID: 4, In: edge4NoStep, Outs: []*Edge{edge5NoStep}},
	5: {ID: 5, In: edge5NoStep, Outs: []*Edge{edge6NoStep}},
	6: {ID: 6, In: edge6NoStep},
	},
	Edges: []*Edge{edge2NoStep, edge4NoStep, edge5NoStep, edge6NoStep},
	},
	want: Graph{},
	},
	} {
	t.Run(tc.desc, func(t *testing.T) {
	got, err := WithStepsOnly(tc.g)
	if err != nil {
	t.Errorf("WithStepsOnly got error: %v", err)
	}
	opts := []cmp.Option{
	cmpopts.EquateEmpty(),
	cmpopts.IgnoreUnexported(Graph{}, Node{}, Edge{}),
	}
	if diff := cmp.Diff(tc.want, got, opts...); diff != "" {
	t.Errorf("WithStepsOnly got output graph diff (-want +got):\n%s", diff)
	}
	})
	}
	}

	func TestWithStepsOnlyErrors(t *testing.T) {
	edge := &Edge{Inputs: []int64{1}, Outputs: []int64{2}, Step: &ninjalog.Step{Out: "2"}}

	for _, tc := range []struct {
	desc string
	g Graph
	}{
	{
	desc: "missing node",
	g: Graph{
	Edges: []*Edge{edge},
	},
	},
	{
	desc: "duplicate edges",
	g: Graph{
	Nodes: map[int64]*Node{
	1: {ID: 1, Outs: []*Edge{edge}},
	2: {ID: 2, In: edge},
	},
	Edges: []*Edge{edge, edge},
	},
	},
	} {
	t.Run(tc.desc, func(t *testing.T) {
	if _, err := WithStepsOnly(tc.g); err == nil {
	t.Error("WithStepsOnly got no error, want non-nil error")
	}
	})
	}
	}