tools/build/ninjago/ninjagraph/ninjagraph.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.

 // ninjagraph provides utilities to parse the DOT output from Ninja's `-t graph`
 // tool to a Go native format.
 package ninjagraph

 import (
 	"bufio"
 	"fmt"
 	"io"
 	"regexp"
 	"runtime"
 	"strconv"
 	"strings"
 	"sync"
 	"time"

 	"go.fuchsia.dev/fuchsia/tools/build/ninjago/ninjalog"
 	"golang.org/x/sync/errgroup"
 )

 var (
 	// Example: "0x1234567" [label="../../path/to/myfile.cc"]
 	nodePattern = regexp.MustCompile(`^"0x([0-9a-f"]+)" \[label="([^"]+)"`)
 	// Example:
 	//   "0x1234567" -> "0x7654321"
 	//   or
 	//   "0x1234567" -> "0x7654321" [label=" host_x64_cxx"]
 	//
 	// Labels for edges currently have a leading space. Optionally match it just
 	// in case it's removed in the future.
 	// https://github.com/ninja-build/ninja/blob/6c5e886aacd98766fe43539c2c8ae7f3ca2af2aa/src/graphviz.cc#L53
 	edgePattern = regexp.MustCompile(`^"0x([0-9a-f]+)" -> "0x([0-9a-f]+)"(?: \[label=" ?([^"]+)")?`)
 )

 // graphvizNode is a node in Ninja's Graphviz output.
 //
 // It is possible for a graphviz node to represent an edge with multiple
 // inputs/outputs in Ninja's build graph.
 type graphvizNode struct {
 	id    int64
 	label string
 	// isNinjaEdge is true if this Graphviz node represents a Ninja build edge.
 	isNinjaEdge bool
 }

 // graphvizEdge is an edge in Ninja's Graphviz output.
 type graphvizEdge struct {
 	from, to int64
 	// If label is non-empty, this edge represents a build edge in Ninja's build
 	// graph, and label is the rule for this build edge.
 	label string
 }

 func graphvizNodeFrom(line string) (graphvizNode, bool, error) {
 	match := nodePattern.FindStringSubmatch(line)
 	if match == nil {
 		return graphvizNode{}, false, nil
 	}

 	id, err := strconv.ParseInt(match[1], 16, 64)
 	if err != nil {
 		return graphvizNode{}, false, err
 	}

 	return graphvizNode{
 		id:    id,
 		label: match[2],
 		// A Graphviz node can represent a Ninja build edge with multiple inputs and
 		// outputs, in this case Ninja draws a ellipse instead of a rectangle.
 		isNinjaEdge: strings.HasSuffix(line, "shape=ellipse]"),
 	}, true, nil
 }

 func graphvizEdgeFrom(line string) (graphvizEdge, bool, error) {
 	match := edgePattern.FindStringSubmatch(line)
 	if match == nil {
 		return graphvizEdge{}, false, nil
 	}

 	from, err := strconv.ParseInt(match[1], 16, 64)
 	if err != nil {
 		return graphvizEdge{}, false, err
 	}
 	to, err := strconv.ParseInt(match[2], 16, 64)
 	if err != nil {
 		return graphvizEdge{}, false, err
 	}
 	var label string
 	if len(match) > 3 {
 		label = match[3]
 	}

 	return graphvizEdge{
 		from:  from,
 		to:    to,
 		label: label,
 	}, true, nil
 }

 // Node is a node in Ninja's build graph. It represents an input/ouput file in
 // the build.
 type Node struct {
 	// ID is an unique ID of this node.
 	ID int64
 	// Path is the path to the input/output file this node represents.
 	Path string
 	// In is the edge that produced this node. Nil if this node is not produced by
 	// any rule.
 	In *Edge
 	// Outs contains all edges that use this node as input.
 	Outs []*Edge

 	// Fields below are used to memoize search results while looking up the
 	// critical path.

 	// criticalInput points to the one of inputs used to produce this node, which
 	// took the longest time to build.
 	criticalInput *Node
 	// criticalBuildDuration is the sum of build durations of all edges along the
 	// critical path that produced this output.
 	criticalBuildDuration *time.Duration
 }

 // Edge is an edge in Ninja's build graph. It links nodes with a build rule.
 type Edge struct {
 	Inputs  []int64
 	Outputs []int64
 	Rule    string

 	// Fields below are populated after `PopulateEdges`.

 	// Step is a build step associated with this edge. It can be derived from
 	// joining with ninja_log. After the join, all steps on non-phony edges are
 	// populated.
 	Step *ninjalog.Step

 	// Fields to memoize earliest start and latest finish for critical path
 	// calculation based on float.
 	//
 	// https://en.wikipedia.org/wiki/Critical_path_method
 	earliestStart, latestFinish *time.Duration
 }

 // Graph is a Ninja build graph.
 type Graph struct {
 	// Nodes maps from node IDs to nodes.
 	Nodes map[int64]*Node
 	// Edges contains all edges in the graph.
 	Edges []*Edge

 	// sink is an edge that marks the completion of the build.
 	//
 	// This edge will only be populated after `addSink`.
 	sink *Edge
 }

 // addEdge adds an edge to the graph and updates the related nodes accordingly.
 func (g *Graph) addEdge(e *Edge) error {
 	for _, input := range e.Inputs {
 		n, ok := g.Nodes[input]
 		if !ok {
 			return fmt.Errorf("node %x not found, while an edge claims to use it as input", input)
 		}
 		n.Outs = append(n.Outs, e)
 	}

 	var outputs []int64
 	for _, output := range e.Outputs {
 		n, ok := g.Nodes[output]
 		if !ok {
 			// Skip this output because it is not included in the build graph.
 			//
 			// This is possible when a rule produces multiple outputs, and some of
 			// those outputs are not explicitly included in the build graph. For
 			// example, some rule produces both stripped and unstripped versions of a
 			// binary, and the unstripped ones are not included in the build graph.
 			continue
 		}
 		outputs = append(outputs, output)
 		if n.In != nil {
 			return fmt.Errorf("multiple edges claim to produce %x as output", output)
 		}
 		n.In = e
 	}

 	e.Outputs = outputs
 	g.Edges = append(g.Edges, e)
 	return nil
 }

 // FromDOT reads all lines from the input reader and parses it into a `Graph`.
 //
 // This function expects the content to be parsed to follow the Ninja log format,
 // otherwise the results is undefined.
 func FromDOT(r io.Reader) (Graph, error) {
 	var gNodes []graphvizNode
 	var gEdges []graphvizEdge

 	gNodesCh := make(chan []graphvizNode)
 	gEdgesCh := make(chan []graphvizEdge)

 	// If a Ninja build edge contains zero or multiple inputs and multiple outputs,
 	// it is represented as a Graphviz node + edges connected to input and output
 	// nodes. These two indexes are useful later when we convert the Graphviz
 	// representation back into a Ninja build edge.
 	edgesBySrc := make(map[int64][]graphvizEdge)
 	edgesByDst := make(map[int64][]graphvizEdge)

 	wg := sync.WaitGroup{}
 	go func() {
 		wg.Add(1)
 		defer wg.Done()
 		for ns := range gNodesCh {
 			gNodes = append(gNodes, ns...)
 		}
 	}()
 	go func() {
 		wg.Add(1)
 		defer wg.Done()
 		for es := range gEdgesCh {
 			gEdges = append(gEdges, es...)
 			for _, e := range es {
 				edgesBySrc[e.from] = append(edgesBySrc[e.from], e)
 				edgesByDst[e.to] = append(edgesByDst[e.to], e)
 			}
 		}
 	}()

 	eg := errgroup.Group{}
 	sem := make(chan struct{}, runtime.GOMAXPROCS(0)-2)
 	s := bufio.NewScanner(r)
 	for s.Scan() {
 		sem <- struct{}{}

 		// Chunk the lines to reduce channel IO, this significantly reduces runtime.
 		lines := []string{s.Text()}
 		for i := 0; i < 10_000 && s.Scan(); i++ {
 			lines = append(lines, s.Text())
 		}

 		eg.Go(func() error {
 			defer func() { <-sem }()

 			var ns []graphvizNode
 			var es []graphvizEdge

 			for _, line := range lines {
 				n, ok, err := graphvizNodeFrom(line)
 				if err != nil {
 					return err
 				}
 				if ok {
 					ns = append(ns, n)
 					continue
 				}

 				e, ok, err := graphvizEdgeFrom(line)
 				if err != nil {
 					return err
 				}
 				if ok {
 					es = append(es, e)
 					continue
 				}
 			}

 			gNodesCh <- ns
 			gEdgesCh <- es
 			return nil
 		})
 	}

 	if err := eg.Wait(); err != nil {
 		return Graph{}, err
 	}
 	close(gNodesCh)
 	close(gEdgesCh)
 	wg.Wait()

 	if err := s.Err(); err != nil && err != io.EOF {
 		return Graph{}, err
 	}

 	// We've done parsing of the Graphviz representation, now map it back to the
 	// actual Ninja build graph.
 	g := Graph{
 		Nodes: make(map[int64]*Node),
 	}

 	// Collect all Graphviz nodes that represent Ninja build edges and assemble
 	// them later.
 	var edgeNodes []graphvizNode
 	// Later steps require all nodes to be present in the graph, so this step
 	// cannot be done in parallel. This is fine because the number of nodes is
 	// usually much smaller than the number of edges.
 	for _, n := range gNodes {
 		if n.isNinjaEdge {
 			edgeNodes = append(edgeNodes, n)
 			continue
 		}
 		g.Nodes[n.id] = &Node{ID: n.id, Path: n.label}
 	}

 	wg.Add(2)
 	edges := make(chan []*Edge)
 	go func() {
 		defer wg.Done()

 		var es []*Edge
 		for _, edge := range gEdges {
 			if edge.label == "" {
 				continue
 			}
 			es = append(es, &Edge{
 				Inputs:  []int64{edge.from},
 				Outputs: []int64{edge.to},
 				Rule:    edge.label,
 			})
 			// Chunk the edges to reduce channel IO, this significantly reduces runtime.
 			if len(es) > 10_000 {
 				edges <- es
 				es = nil
 			}
 		}
 		edges <- es
 	}()

 	go func() {
 		defer wg.Done()

 		var es []*Edge
 		for _, n := range edgeNodes {
 			// If a Ninja build edge is represented as a Graphviz node, all the
 			// Graphviz edges pointing to it are connected to inputs, and all the
 			// Graphviz edges going out of it are connected to outputs.
 			e := &Edge{Rule: n.label}
 			for _, from := range edgesByDst[n.id] {
 				e.Inputs = append(e.Inputs, from.from)
 			}
 			for _, to := range edgesBySrc[n.id] {
 				e.Outputs = append(e.Outputs, to.to)
 			}
 			es = append(es, e)
 			// Chunk the edges to reduce channel IO, this significantly reduces runtime.
 			if len(es) > 10_000 {
 				edges <- es
 				es = nil
 			}
 		}
 		edges <- es
 	}()

 	go func() {
 		wg.Wait()
 		close(edges)
 	}()

 	for es := range edges {
 		for _, e := range es {
 			if err := g.addEdge(e); err != nil {
 				return Graph{}, err
 			}
 		}
 	}
 	return g, nil
 }

 // PopulateEdges joins the build steps from ninjalog with the graph and
 // populates build time on edges.
 //
 // `steps` should be deduplicated, so they have a 1-to-1 mapping to edges.
 // Although the mapping can be partial, which means not all edges from the graph
 // have a corresponding step from the input.
 //
 // If any non-phony edges are missing steps, subsequent attempt to calculate
 // critical path will fail. To avoid this, use `WithStepsOnly` to extract a
 // partial graph.
 func (g *Graph) PopulateEdges(steps []ninjalog.Step) error {
 	stepByOut := make(map[string]ninjalog.Step)

 	for _, step := range steps {
 		// Index all outputs, otherwise the edges can miss steps due to missing
 		// nodes. If steps are only indexed on their main output, and that output
 		// node is missing from the graph, we can't draw a link between the step and
 		// its corresponding edge.
 		//
 		// For example, if a step has its main output set to `foo`, and also
 		// produces `bar` and `baz`, we want to index this step on all three of the
 		// outputs. This way, if an edge missed `foo` in its output (possible when
 		// the output node is not included in the build graph), it can still be
 		// associated with the step since it can match on both other outputs.
 		for _, out := range append(step.Outs, step.Out) {
 			if conflict, ok := stepByOut[out]; ok {
 				return fmt.Errorf("multiple steps claim to produce the same output %s\nverbose debugging info:\n:step 1: %#v\ncommand 1: %#v\nstep 2: %#v\ncommand 2: %#v\n", out, conflict, conflict.Command, step, step.Command)
 			}
 			stepByOut[out] = step
 		}
 	}

 	for _, edge := range g.Edges {
 		// Skip "phony" builds because they don't actually run any build commands.
 		//
 		// For example "build default: phony obj/default.stamp" can be included in
 		// the graph.
 		if edge.Rule == "phony" {
 			continue
 		}

 		var nodes []*Node
 		for _, output := range edge.Outputs {
 			node := g.Nodes[output]
 			if node == nil {
 				return fmt.Errorf("node %x not found, yet an edge claims to produce it, invalid graph", output)
 			}
 			nodes = append(nodes, node)
 		}

 		// Look for the corresponding ninjalog step for this edge. We do this by
 		// matching outputs: for each output we look for the build step that
 		// produced it, and associate that with the edge. Along the way we also
 		// check all the outputs claimed by this edge is produced by the same step,
 		// so there is a 1-to-1 mapping between them.
 		var step *ninjalog.Step
 		for _, node := range nodes {
 			s, ok := stepByOut[node.Path]
 			if !ok {
 				break
 			}
 			if step != nil && step.CmdHash != s.CmdHash {
 				return fmt.Errorf("multiple steps match the same edge on outputs %v, previous step: %#v, this step: %#v", pathsOf(nodes), step, s)
 			}
 			step = &s
 		}
 		// Steps can be missing if they are from a partial build, for example
 		// incremental builds and failed builds. In this case, some edges in the
 		// graphs have not been reached.
 		if step != nil {
 			edge.Step = step
 		}
 	}
 	return nil
 }

 func pathsOf(nodes []*Node) []string {
 	var paths []string
 	for _, n := range nodes {
 		paths = append(paths, n.Path)
 	}
 	return paths
 }

 // WithStepsOnly returns an extracted subgraph that contains edges that either
 // have `Step`s associated with them, or are phonies. Only nodes with edges
 // connected to them are kept in the returned graph.
 //
 // This function is useful, after `Step`s are populated, for extracting a
 // partial build graph from, for example, incremental builds and failed builds.
 //
 // If this function returns successfully, the returned Graph is guaranteed to
 // have steps associated to all non-phony edges. All phony edges are kept to
 // preserve dependencies.
 func WithStepsOnly(g Graph) (Graph, error) {
 	subGraph := Graph{
 		Nodes: make(map[int64]*Node),
 	}

 	for _, edge := range g.Edges {
 		// Steps can be missing when analyzing partial builds, for example
 		// incremental and failed builds. Missing a step means this edge is not
 		// reached in this partial build (build command for this edge is not
 		// executed), so we simply omit them.
 		if edge.Rule != "phony" && edge.Step == nil {
 			continue
 		}
 		subGraph.Edges = append(subGraph.Edges, &Edge{
 			// Avoid reusing the existing edge or copying over memoized pointer
 			// fields, so when memoized fields are set on the new graph, it won't
 			// affect the old one.
 			Inputs:  edge.Inputs,
 			Outputs: edge.Outputs,
 			Rule:    edge.Rule,
 			Step:    edge.Step,
 		})
 	}

 	for _, edge := range subGraph.Edges {
 		for _, id := range edge.Inputs {
 			node, ok := subGraph.Nodes[id]
 			if !ok {
 				n, ok := g.Nodes[id]
 				if !ok {
 					return Graph{}, fmt.Errorf("node %x not found, yet an edge claims it as input, invalid graph", id)
 				}
 				node = &Node{
 					// Avoid reusing the existing node or copying over memoized pointer
 					// fields, so when memoized fields are set on the new graph, it won't
 					// affect the old one.
 					ID:   n.ID,
 					Path: n.Path,
 				}
 				subGraph.Nodes[id] = node
 			}
 			node.Outs = append(node.Outs, edge)
 		}

 		for _, id := range edge.Outputs {
 			node, ok := subGraph.Nodes[id]
 			if !ok {
 				n, ok := g.Nodes[id]
 				if !ok {
 					return Graph{}, fmt.Errorf("node %x not found, yet an edge claims to produce it, invalid graph", id)
 				}
 				node = &Node{
 					// Avoid reusing the existing node or copying over memoized pointer
 					// fields, so when memoized fields are set on the new graph, it won't
 					// affect the old one.
 					ID:   n.ID,
 					Path: n.Path,
 				}
 				subGraph.Nodes[id] = node
 			}
 			if node.In != nil {
 				return Graph{}, fmt.Errorf("multiple edges claim to produce %x as output, invalid graph", id)
 			}
 			node.In = edge
 		}
 	}
 	return subGraph, nil
 }
	// 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.

	// ninjagraph provides utilities to parse the DOT output from Ninja's `-t graph`
	// tool to a Go native format.
	package ninjagraph

	import (
	"bufio"
	"fmt"
	"io"
	"regexp"
	"runtime"
	"strconv"
	"strings"
	"sync"
	"time"

	"go.fuchsia.dev/fuchsia/tools/build/ninjago/ninjalog"
	"golang.org/x/sync/errgroup"
	)

	var (
	// Example: "0x1234567" [label="../../path/to/myfile.cc"]
	nodePattern = regexp.MustCompile(`^"0x([0-9a-f"]+)" \[label="([^"]+)"`)
	// Example:
	// "0x1234567" -> "0x7654321"
	// or
	// "0x1234567" -> "0x7654321" [label=" host_x64_cxx"]
	//
	// Labels for edges currently have a leading space. Optionally match it just
	// in case it's removed in the future.
	// https://github.com/ninja-build/ninja/blob/6c5e886aacd98766fe43539c2c8ae7f3ca2af2aa/src/graphviz.cc#L53
	edgePattern = regexp.MustCompile(`^"0x([0-9a-f]+)" -> "0x([0-9a-f]+)"(?: \[label=" ?([^"]+)")?`)
	)

	// graphvizNode is a node in Ninja's Graphviz output.
	//
	// It is possible for a graphviz node to represent an edge with multiple
	// inputs/outputs in Ninja's build graph.
	type graphvizNode struct {
	id int64
	label string
	// isNinjaEdge is true if this Graphviz node represents a Ninja build edge.
	isNinjaEdge bool
	}

	// graphvizEdge is an edge in Ninja's Graphviz output.
	type graphvizEdge struct {
	from, to int64
	// If label is non-empty, this edge represents a build edge in Ninja's build
	// graph, and label is the rule for this build edge.
	label string
	}

	func graphvizNodeFrom(line string) (graphvizNode, bool, error) {
	match := nodePattern.FindStringSubmatch(line)
	if match == nil {
	return graphvizNode{}, false, nil
	}

	id, err := strconv.ParseInt(match[1], 16, 64)
	if err != nil {
	return graphvizNode{}, false, err
	}

	return graphvizNode{
	id: id,
	label: match[2],
	// A Graphviz node can represent a Ninja build edge with multiple inputs and
	// outputs, in this case Ninja draws a ellipse instead of a rectangle.
	isNinjaEdge: strings.HasSuffix(line, "shape=ellipse]"),
	}, true, nil
	}

	func graphvizEdgeFrom(line string) (graphvizEdge, bool, error) {
	match := edgePattern.FindStringSubmatch(line)
	if match == nil {
	return graphvizEdge{}, false, nil
	}

	from, err := strconv.ParseInt(match[1], 16, 64)
	if err != nil {
	return graphvizEdge{}, false, err
	}
	to, err := strconv.ParseInt(match[2], 16, 64)
	if err != nil {
	return graphvizEdge{}, false, err
	}
	var label string
	if len(match) > 3 {
	label = match[3]
	}

	return graphvizEdge{
	from: from,
	to: to,
	label: label,
	}, true, nil
	}

	// Node is a node in Ninja's build graph. It represents an input/ouput file in
	// the build.
	type Node struct {
	// ID is an unique ID of this node.
	ID int64
	// Path is the path to the input/output file this node represents.
	Path string
	// In is the edge that produced this node. Nil if this node is not produced by
	// any rule.
	In *Edge
	// Outs contains all edges that use this node as input.
	Outs []*Edge

	// Fields below are used to memoize search results while looking up the
	// critical path.

	// criticalInput points to the one of inputs used to produce this node, which
	// took the longest time to build.
	criticalInput *Node
	// criticalBuildDuration is the sum of build durations of all edges along the
	// critical path that produced this output.
	criticalBuildDuration *time.Duration
	}

	// Edge is an edge in Ninja's build graph. It links nodes with a build rule.
	type Edge struct {
	Inputs []int64
	Outputs []int64
	Rule string

	// Fields below are populated after `PopulateEdges`.

	// Step is a build step associated with this edge. It can be derived from
	// joining with ninja_log. After the join, all steps on non-phony edges are
	// populated.
	Step *ninjalog.Step

	// Fields to memoize earliest start and latest finish for critical path
	// calculation based on float.
	//
	// https://en.wikipedia.org/wiki/Critical_path_method
	earliestStart, latestFinish *time.Duration
	}

	// Graph is a Ninja build graph.
	type Graph struct {
	// Nodes maps from node IDs to nodes.
	Nodes map[int64]*Node
	// Edges contains all edges in the graph.
	Edges []*Edge

	// sink is an edge that marks the completion of the build.
	//
	// This edge will only be populated after `addSink`.
	sink *Edge
	}

	// addEdge adds an edge to the graph and updates the related nodes accordingly.
	func (g Graph) addEdge(e Edge) error {
	for _, input := range e.Inputs {
	n, ok := g.Nodes[input]
	if !ok {
	return fmt.Errorf("node %x not found, while an edge claims to use it as input", input)
	}
	n.Outs = append(n.Outs, e)
	}

	var outputs []int64
	for _, output := range e.Outputs {
	n, ok := g.Nodes[output]
	if !ok {
	// Skip this output because it is not included in the build graph.
	//
	// This is possible when a rule produces multiple outputs, and some of
	// those outputs are not explicitly included in the build graph. For
	// example, some rule produces both stripped and unstripped versions of a
	// binary, and the unstripped ones are not included in the build graph.
	continue
	}
	outputs = append(outputs, output)
	if n.In != nil {
	return fmt.Errorf("multiple edges claim to produce %x as output", output)
	}
	n.In = e
	}

	e.Outputs = outputs
	g.Edges = append(g.Edges, e)
	return nil
	}

	// FromDOT reads all lines from the input reader and parses it into a `Graph`.
	//
	// This function expects the content to be parsed to follow the Ninja log format,
	// otherwise the results is undefined.
	func FromDOT(r io.Reader) (Graph, error) {
	var gNodes []graphvizNode
	var gEdges []graphvizEdge

	gNodesCh := make(chan []graphvizNode)
	gEdgesCh := make(chan []graphvizEdge)

	// If a Ninja build edge contains zero or multiple inputs and multiple outputs,
	// it is represented as a Graphviz node + edges connected to input and output
	// nodes. These two indexes are useful later when we convert the Graphviz
	// representation back into a Ninja build edge.
	edgesBySrc := make(map[int64][]graphvizEdge)
	edgesByDst := make(map[int64][]graphvizEdge)

	wg := sync.WaitGroup{}
	go func() {
	wg.Add(1)
	defer wg.Done()
	for ns := range gNodesCh {
	gNodes = append(gNodes, ns...)
	}
	}()
	go func() {
	wg.Add(1)
	defer wg.Done()
	for es := range gEdgesCh {
	gEdges = append(gEdges, es...)
	for _, e := range es {
	edgesBySrc[e.from] = append(edgesBySrc[e.from], e)
	edgesByDst[e.to] = append(edgesByDst[e.to], e)
	}
	}
	}()

	eg := errgroup.Group{}
	sem := make(chan struct{}, runtime.GOMAXPROCS(0)-2)
	s := bufio.NewScanner(r)
	for s.Scan() {
	sem <- struct{}{}

	// Chunk the lines to reduce channel IO, this significantly reduces runtime.
	lines := []string{s.Text()}
	for i := 0; i < 10_000 && s.Scan(); i++ {
	lines = append(lines, s.Text())
	}

	eg.Go(func() error {
	defer func() { <-sem }()

	var ns []graphvizNode
	var es []graphvizEdge

	for _, line := range lines {
	n, ok, err := graphvizNodeFrom(line)
	if err != nil {
	return err
	}
	if ok {
	ns = append(ns, n)
	continue
	}

	e, ok, err := graphvizEdgeFrom(line)
	if err != nil {
	return err
	}
	if ok {
	es = append(es, e)
	continue
	}
	}

	gNodesCh <- ns
	gEdgesCh <- es
	return nil
	})
	}

	if err := eg.Wait(); err != nil {
	return Graph{}, err
	}
	close(gNodesCh)
	close(gEdgesCh)
	wg.Wait()

	if err := s.Err(); err != nil && err != io.EOF {
	return Graph{}, err
	}

	// We've done parsing of the Graphviz representation, now map it back to the
	// actual Ninja build graph.
	g := Graph{
	Nodes: make(map[int64]*Node),
	}

	// Collect all Graphviz nodes that represent Ninja build edges and assemble
	// them later.
	var edgeNodes []graphvizNode
	// Later steps require all nodes to be present in the graph, so this step
	// cannot be done in parallel. This is fine because the number of nodes is
	// usually much smaller than the number of edges.
	for _, n := range gNodes {
	if n.isNinjaEdge {
	edgeNodes = append(edgeNodes, n)
	continue
	}
	g.Nodes[n.id] = &Node{ID: n.id, Path: n.label}
	}

	wg.Add(2)
	edges := make(chan []*Edge)
	go func() {
	defer wg.Done()

	var es []*Edge
	for _, edge := range gEdges {
	if edge.label == "" {
	continue
	}
	es = append(es, &Edge{
	Inputs: []int64{edge.from},
	Outputs: []int64{edge.to},
	Rule: edge.label,
	})
	// Chunk the edges to reduce channel IO, this significantly reduces runtime.
	if len(es) > 10_000 {
	edges <- es
	es = nil
	}
	}
	edges <- es
	}()

	go func() {
	defer wg.Done()

	var es []*Edge
	for _, n := range edgeNodes {
	// If a Ninja build edge is represented as a Graphviz node, all the
	// Graphviz edges pointing to it are connected to inputs, and all the
	// Graphviz edges going out of it are connected to outputs.
	e := &Edge{Rule: n.label}
	for _, from := range edgesByDst[n.id] {
	e.Inputs = append(e.Inputs, from.from)
	}
	for _, to := range edgesBySrc[n.id] {
	e.Outputs = append(e.Outputs, to.to)
	}
	es = append(es, e)
	// Chunk the edges to reduce channel IO, this significantly reduces runtime.
	if len(es) > 10_000 {
	edges <- es
	es = nil
	}
	}
	edges <- es
	}()

	go func() {
	wg.Wait()
	close(edges)
	}()

	for es := range edges {
	for _, e := range es {
	if err := g.addEdge(e); err != nil {
	return Graph{}, err
	}
	}
	}
	return g, nil
	}

	// PopulateEdges joins the build steps from ninjalog with the graph and
	// populates build time on edges.
	//
	// `steps` should be deduplicated, so they have a 1-to-1 mapping to edges.
	// Although the mapping can be partial, which means not all edges from the graph
	// have a corresponding step from the input.
	//
	// If any non-phony edges are missing steps, subsequent attempt to calculate
	// critical path will fail. To avoid this, use `WithStepsOnly` to extract a
	// partial graph.
	func (g *Graph) PopulateEdges(steps []ninjalog.Step) error {
	stepByOut := make(map[string]ninjalog.Step)

	for _, step := range steps {
	// Index all outputs, otherwise the edges can miss steps due to missing
	// nodes. If steps are only indexed on their main output, and that output
	// node is missing from the graph, we can't draw a link between the step and
	// its corresponding edge.
	//
	// For example, if a step has its main output set to `foo`, and also
	// produces `bar` and `baz`, we want to index this step on all three of the
	// outputs. This way, if an edge missed `foo` in its output (possible when
	// the output node is not included in the build graph), it can still be
	// associated with the step since it can match on both other outputs.
	for _, out := range append(step.Outs, step.Out) {
	if conflict, ok := stepByOut[out]; ok {
	return fmt.Errorf("multiple steps claim to produce the same output %s\nverbose debugging info:\n:step 1: %#v\ncommand 1: %#v\nstep 2: %#v\ncommand 2: %#v\n", out, conflict, conflict.Command, step, step.Command)
	}
	stepByOut[out] = step
	}
	}

	for _, edge := range g.Edges {
	// Skip "phony" builds because they don't actually run any build commands.
	//
	// For example "build default: phony obj/default.stamp" can be included in
	// the graph.
	if edge.Rule == "phony" {
	continue
	}

	var nodes []*Node
	for _, output := range edge.Outputs {
	node := g.Nodes[output]
	if node == nil {
	return fmt.Errorf("node %x not found, yet an edge claims to produce it, invalid graph", output)
	}
	nodes = append(nodes, node)
	}

	// Look for the corresponding ninjalog step for this edge. We do this by
	// matching outputs: for each output we look for the build step that
	// produced it, and associate that with the edge. Along the way we also
	// check all the outputs claimed by this edge is produced by the same step,
	// so there is a 1-to-1 mapping between them.
	var step *ninjalog.Step
	for _, node := range nodes {
	s, ok := stepByOut[node.Path]
	if !ok {
	break
	}
	if step != nil && step.CmdHash != s.CmdHash {
	return fmt.Errorf("multiple steps match the same edge on outputs %v, previous step: %#v, this step: %#v", pathsOf(nodes), step, s)
	}
	step = &s
	}
	// Steps can be missing if they are from a partial build, for example
	// incremental builds and failed builds. In this case, some edges in the
	// graphs have not been reached.
	if step != nil {
	edge.Step = step
	}
	}
	return nil
	}

	func pathsOf(nodes []*Node) []string {
	var paths []string
	for _, n := range nodes {
	paths = append(paths, n.Path)
	}
	return paths
	}

	// WithStepsOnly returns an extracted subgraph that contains edges that either
	// have `Step`s associated with them, or are phonies. Only nodes with edges
	// connected to them are kept in the returned graph.
	//
	// This function is useful, after `Step`s are populated, for extracting a
	// partial build graph from, for example, incremental builds and failed builds.
	//
	// If this function returns successfully, the returned Graph is guaranteed to
	// have steps associated to all non-phony edges. All phony edges are kept to
	// preserve dependencies.
	func WithStepsOnly(g Graph) (Graph, error) {
	subGraph := Graph{
	Nodes: make(map[int64]*Node),
	}

	for _, edge := range g.Edges {
	// Steps can be missing when analyzing partial builds, for example
	// incremental and failed builds. Missing a step means this edge is not
	// reached in this partial build (build command for this edge is not
	// executed), so we simply omit them.
	if edge.Rule != "phony" && edge.Step == nil {
	continue
	}
	subGraph.Edges = append(subGraph.Edges, &Edge{
	// Avoid reusing the existing edge or copying over memoized pointer
	// fields, so when memoized fields are set on the new graph, it won't
	// affect the old one.
	Inputs: edge.Inputs,
	Outputs: edge.Outputs,
	Rule: edge.Rule,
	Step: edge.Step,
	})
	}

	for _, edge := range subGraph.Edges {
	for _, id := range edge.Inputs {
	node, ok := subGraph.Nodes[id]
	if !ok {
	n, ok := g.Nodes[id]
	if !ok {
	return Graph{}, fmt.Errorf("node %x not found, yet an edge claims it as input, invalid graph", id)
	}
	node = &Node{
	// Avoid reusing the existing node or copying over memoized pointer
	// fields, so when memoized fields are set on the new graph, it won't
	// affect the old one.
	ID: n.ID,
	Path: n.Path,
	}
	subGraph.Nodes[id] = node
	}
	node.Outs = append(node.Outs, edge)
	}

	for _, id := range edge.Outputs {
	node, ok := subGraph.Nodes[id]
	if !ok {
	n, ok := g.Nodes[id]
	if !ok {
	return Graph{}, fmt.Errorf("node %x not found, yet an edge claims to produce it, invalid graph", id)
	}
	node = &Node{
	// Avoid reusing the existing node or copying over memoized pointer
	// fields, so when memoized fields are set on the new graph, it won't
	// affect the old one.
	ID: n.ID,
	Path: n.Path,
	}
	subGraph.Nodes[id] = node
	}
	if node.In != nil {
	return Graph{}, fmt.Errorf("multiple edges claim to produce %x as output, invalid graph", id)
	}
	node.In = edge
	}
	}
	return subGraph, nil
	}