func TestPruneNoopTransformer(t *testing.T) {
	g := Graph{Path: RootModulePath}

	a := &testGraphNodeNoop{NameValue: "A"}
	b := &testGraphNodeNoop{NameValue: "B", Value: true}
	c := &testGraphNodeNoop{NameValue: "C"}

	g.Add(a)
	g.Add(b)
	g.Add(c)
	g.Connect(dag.BasicEdge(a, b))
	g.Connect(dag.BasicEdge(b, c))

	{
		tf := &PruneNoopTransformer{}
		if err := tf.Transform(&g); err != nil {
			t.Fatalf("err: %s", err)
		}
	}

	actual := strings.TrimSpace(g.String())
	expected := strings.TrimSpace(testTransformPruneNoopStr)
	if actual != expected {
		t.Fatalf("bad:\n\n%s", actual)
	}
}

func TestVertexTransformer(t *testing.T) {
	var g Graph
	g.Add(1)
	g.Add(2)
	g.Add(3)
	g.Connect(dag.BasicEdge(1, 2))
	g.Connect(dag.BasicEdge(2, 3))

	{
		tf := &VertexTransformer{
			Transforms: []GraphVertexTransformer{
				&testVertexTransform{Source: 2, Target: 42},
			},
		}
		if err := tf.Transform(&g); err != nil {
			t.Fatalf("err: %s", err)
		}
	}

	actual := strings.TrimSpace(g.String())
	expected := strings.TrimSpace(testVertexTransformerStr)
	if actual != expected {
		t.Fatalf("bad: %s", actual)
	}
}

func (t *CreateBeforeDestroyTransformer) Transform(g *Graph) error {
	// We "stage" the edge connections/destroys in these slices so that
	// while we're doing the edge transformations (transpositions) in
	// the graph, we're not affecting future edge transpositions. These
	// slices let us stage ALL the changes that WILL happen so that all
	// of the transformations happen atomically.
	var connect, destroy []dag.Edge

	for _, v := range g.Vertices() {
		// We only care to use the destroy nodes
		dn, ok := v.(GraphNodeDestroy)
		if !ok {
			continue
		}

		// If the node doesn't need to create before destroy, then continue
		if !dn.CreateBeforeDestroy() {
			continue
		}

		// Get the creation side of this node
		cn := dn.CreateNode()

		// Take all the things which depend on the creation node and
		// make them dependencies on the destruction. Clarifying this
		// with an example: if you have a web server and a load balancer
		// and the load balancer depends on the web server, then when we
		// do a create before destroy, we want to make sure the steps are:
		//
		// 1.) Create new web server
		// 2.) Update load balancer
		// 3.) Delete old web server
		//
		// This ensures that.
		for _, sourceRaw := range g.UpEdges(cn).List() {
			source := sourceRaw.(dag.Vertex)
			connect = append(connect, dag.BasicEdge(dn, source))
		}

		// Swap the edge so that the destroy depends on the creation
		// happening...
		connect = append(connect, dag.BasicEdge(dn, cn))
		destroy = append(destroy, dag.BasicEdge(cn, dn))
	}

	for _, edge := range connect {
		g.Connect(edge)
	}
	for _, edge := range destroy {
		g.RemoveEdge(edge)
	}

	return nil
}

func (t *Tree) buildProviderAliasGraph(g *dag.AcyclicGraph, parent dag.Vertex) {
	// Add all our defined aliases
	defined := make(map[string]struct{})
	for _, p := range t.config.ProviderConfigs {
		defined[p.FullName()] = struct{}{}
	}

	// Add all our used aliases
	used := make(map[string]struct{})
	for _, r := range t.config.Resources {
		if r.Provider != "" {
			used[r.Provider] = struct{}{}
		}
	}

	// Add it to the graph
	vertex := &providerAliasVertex{
		Path:    t.Path(),
		Defined: defined,
		Used:    used,
	}
	g.Add(vertex)

	// Connect to our parent if we have one
	if parent != nil {
		g.Connect(dag.BasicEdge(vertex, parent))
	}

	// Build all our children
	for _, c := range t.Children() {
		c.buildProviderAliasGraph(g, vertex)
	}
}

// ConnectFrom creates an edge by finding the source from a DependableName
// and connecting it to the specific vertex.
func (g *Graph) ConnectFrom(source string, target dag.Vertex) {
	g.once.Do(g.init)

	if source := g.dependableMap[source]; source != nil {
		g.Connect(dag.BasicEdge(source, target))
	}
}

func (t *ProxyTransformer) Transform(g *Graph) error {
	for _, v := range g.Vertices() {
		pn, ok := v.(GraphNodeProxy)
		if !ok {
			continue
		}

		// If we don't want to be proxies, don't do it
		if !pn.Proxy() {
			continue
		}

		// Connect all the things that depend on this to things that
		// we depend on as the proxy. See docs for GraphNodeProxy for
		// a visual explanation.
		for _, s := range g.UpEdges(v).List() {
			for _, t := range g.DownEdges(v).List() {
				g.Connect(GraphProxyEdge{
					Edge: dag.BasicEdge(s, t),
				})
			}
		}
	}

	return nil
}

func (c *Compiled) UnmarshalJSON(data []byte) error {
	var raw compiledJSON
	if err := json.Unmarshal(data, &raw); err != nil {
		return err
	}

	c.File = raw.File
	c.Graph = new(dag.AcyclicGraph)
	for _, v := range raw.Vertices {
		c.Graph.Add(v)
	}
	for _, e := range raw.Edges {
		for a, b := range e {
			ai, err := strconv.ParseInt(a, 0, 0)
			if err != nil {
				return err
			}

			bi, err := strconv.ParseInt(b, 0, 0)
			if err != nil {
				return err
			}

			c.Graph.Connect(dag.BasicEdge(raw.Vertices[ai], raw.Vertices[bi]))
		}
	}

	return nil
}

func TestExpandTransform(t *testing.T) {
	var g Graph
	g.Add(1)
	g.Add(2)
	g.Connect(dag.BasicEdge(1, 2))

	tf := &ExpandTransform{}
	out, err := tf.Transform(&testExpandable{
		Result: &g,
	})
	if err != nil {
		t.Fatalf("err: %s", err)
	}

	sn, ok := out.(GraphNodeSubgraph)
	if !ok {
		t.Fatalf("not subgraph: %#v", out)
	}

	actual := strings.TrimSpace(sn.Subgraph().String())
	expected := strings.TrimSpace(testExpandTransformStr)
	if actual != expected {
		t.Fatalf("bad: %s", actual)
	}
}

func (t *PruneNoopTransformer) Transform(g *Graph) error {
	// Find the leaves.
	leaves := make([]dag.Vertex, 0, 10)
	for _, v := range g.Vertices() {
		if g.DownEdges(v).Len() == 0 {
			leaves = append(leaves, v)
		}
	}

	// Do a depth first walk from the leaves and remove things.
	return g.ReverseDepthFirstWalk(leaves, func(v dag.Vertex, depth int) error {
		// We need a prunable
		pn, ok := v.(GraphNodeNoopPrunable)
		if !ok {
			return nil
		}

		// Start building the noop opts
		path := g.Path
		if pn, ok := v.(GraphNodeSubPath); ok {
			path = pn.Path()
		}

		var modDiff *ModuleDiff
		var modState *ModuleState
		if t.Diff != nil {
			modDiff = t.Diff.ModuleByPath(path)
		}
		if t.State != nil {
			modState = t.State.ModuleByPath(path)
		}

		// Determine if its a noop. If it isn't, just return
		noop := pn.Noop(&NoopOpts{
			Graph:    g,
			Vertex:   v,
			Diff:     t.Diff,
			State:    t.State,
			ModDiff:  modDiff,
			ModState: modState,
		})
		if !noop {
			return nil
		}

		// It is a noop! We first preserve edges.
		up := g.UpEdges(v).List()
		for _, downV := range g.DownEdges(v).List() {
			for _, upV := range up {
				g.Connect(dag.BasicEdge(upV, downV))
			}
		}

		// Then remove it
		g.Remove(v)

		return nil
	})
}

func TestDebugJSON2Dot(t *testing.T) {
	// create the graph JSON output
	logFile, err := ioutil.TempFile("", "tf")
	if err != nil {
		t.Fatal(err)
	}
	defer os.Remove(logFile.Name())

	var g dag.Graph
	g.SetDebugWriter(logFile)

	g.Add(1)
	g.Add(2)
	g.Add(3)
	g.Connect(dag.BasicEdge(1, 2))
	g.Connect(dag.BasicEdge(2, 3))

	ui := new(cli.MockUi)
	c := &DebugJSON2DotCommand{
		Meta: Meta{
			ContextOpts: testCtxConfig(testProvider()),
			Ui:          ui,
		},
	}

	args := []string{
		logFile.Name(),
	}
	if code := c.Run(args); code != 0 {
		t.Fatalf("bad: \n%s", ui.ErrorWriter.String())
	}

	output := ui.OutputWriter.String()
	if !strings.HasPrefix(output, "digraph {") {
		t.Fatalf("doesn't look like digraph: %s", output)
	}

	if !strings.Contains(output, `subgraph "root" {`) {
		t.Fatalf("doesn't contains root subgraph: %s", output)
	}
}

func (t *ParentProviderTransformer) Transform(g *Graph) error {
	// Make a mapping of path to dag.Vertex, where path is: "path.name"
	m := make(map[string]dag.Vertex)

	// Also create a map that maps a provider to its parent
	parentMap := make(map[dag.Vertex]string)
	for _, raw := range g.Vertices() {
		// If it is the flat version, then make it the non-flat version.
		// We eventually want to get rid of the flat version entirely so
		// this is a stop-gap while it still exists.
		var v dag.Vertex = raw
		if f, ok := v.(*graphNodeProviderFlat); ok {
			v = f.graphNodeProvider
		}

		// Only care about providers
		pn, ok := v.(GraphNodeProvider)
		if !ok || pn.ProviderName() == "" {
			continue
		}

		// Also require a subpath, if there is no subpath then we
		// just totally ignore it. The expectation of this transform is
		// that it is used with a graph builder that is already flattened.
		var path []string
		if pn, ok := raw.(GraphNodeSubPath); ok {
			path = pn.Path()
		}
		path = normalizeModulePath(path)

		// Build the key with path.name i.e. "child.subchild.aws"
		key := fmt.Sprintf("%s.%s", strings.Join(path, "."), pn.ProviderName())
		m[key] = raw

		// Determine the parent if we're non-root. This is length 1 since
		// the 0 index should be "root" since we normalize above.
		if len(path) > 1 {
			path = path[:len(path)-1]
			key := fmt.Sprintf("%s.%s", strings.Join(path, "."), pn.ProviderName())
			parentMap[raw] = key
		}
	}

	// Connect!
	for v, key := range parentMap {
		if parent, ok := m[key]; ok {
			g.Connect(dag.BasicEdge(v, parent))
		}
	}

	return nil
}

func TestProxyTransformer(t *testing.T) {
	var g Graph
	proxy := &testNodeProxy{NameValue: "proxy"}
	g.Add("A")
	g.Add("C")
	g.Add(proxy)
	g.Connect(dag.BasicEdge("A", proxy))
	g.Connect(dag.BasicEdge(proxy, "C"))

	{
		tf := &ProxyTransformer{}
		if err := tf.Transform(&g); err != nil {
			t.Fatalf("err: %s", err)
		}
	}

	actual := strings.TrimSpace(g.String())
	expected := strings.TrimSpace(testProxyTransformStr)
	if actual != expected {
		t.Fatalf("bad: %s", actual)
	}
}

// ConnectTo connects a vertex to a raw string of targets that are the
// result of DependableName, and returns the list of targets that are missing.
func (g *Graph) ConnectTo(v dag.Vertex, targets []string) []string {
	g.once.Do(g.init)

	var missing []string
	for _, t := range targets {
		if dest := g.dependableMap[t]; dest != nil {
			g.Connect(dag.BasicEdge(v, dest))
		} else {
			missing = append(missing, t)
		}
	}

	return missing
}

func (t *CountBoundaryTransformer) Transform(g *Graph) error {
	node := &NodeCountBoundary{}
	g.Add(node)

	// Depends on everything
	for _, v := range g.Vertices() {
		// Don't connect to ourselves
		if v == node {
			continue
		}

		// Connect!
		g.Connect(dag.BasicEdge(node, v))
	}

	return nil
}

func (t *ModuleInputTransformer) Transform(g *Graph) error {
	// Create the node
	n := &graphNodeModuleInput{Variables: t.Variables}

	// Add it to the graph
	g.Add(n)

	// Connect the inputs to the bottom of the graph so that it happens
	// first.
	for _, v := range g.Vertices() {
		if v == n {
			continue
		}

		if g.DownEdges(v).Len() == 0 {
			g.Connect(dag.BasicEdge(v, n))
		}
	}

	return nil
}

func (t *ProvisionerTransformer) Transform(g *Graph) error {
	// Go through the other nodes and match them to provisioners they need
	var err error
	m := provisionerVertexMap(g)
	for _, v := range g.Vertices() {
		if pv, ok := v.(GraphNodeProvisionerConsumer); ok {
			for _, p := range pv.ProvisionedBy() {
				if m[p] == nil {
					err = multierror.Append(err, fmt.Errorf(
						"%s: provisioner %s couldn't be found",
						dag.VertexName(v), p))
					continue
				}

				g.Connect(dag.BasicEdge(v, m[p]))
			}
		}
	}

	return err
}

func (t *RootTransformer) Transform(g *Graph) error {
	// If we already have a good root, we're done
	if _, err := g.Root(); err == nil {
		return nil
	}

	// Add a root
	var root graphNodeRoot
	g.Add(root)

	// Connect the root to all the edges that need it
	for _, v := range g.Vertices() {
		if v == root {
			continue
		}

		if g.UpEdges(v).Len() == 0 {
			g.Connect(dag.BasicEdge(root, v))
		}
	}

	return nil
}

func (t *ReferenceTransformer) Transform(g *Graph) error {
	// Build a reference map so we can efficiently look up the references
	vs := g.Vertices()
	m := NewReferenceMap(vs)

	// Find the things that reference things and connect them
	for _, v := range vs {
		parents, _ := m.References(v)
		parentsDbg := make([]string, len(parents))
		for i, v := range parents {
			parentsDbg[i] = dag.VertexName(v)
		}
		log.Printf(
			"[DEBUG] ReferenceTransformer: %q references: %v",
			dag.VertexName(v), parentsDbg)

		for _, parent := range parents {
			g.Connect(dag.BasicEdge(v, parent))
		}
	}

	return nil
}

func (t *CloseProviderTransformer) Transform(g *Graph) error {
	m := closeProviderVertexMap(g)
	for _, v := range g.Vertices() {
		if pv, ok := v.(GraphNodeProviderConsumer); ok {
			for _, p := range pv.ProvidedBy() {
				source := m[p]

				if source == nil {
					// Create a new graphNodeCloseProvider and add it to the graph
					source = &graphNodeCloseProvider{ProviderNameValue: p}
					g.Add(source)

					// Make sure we also add the new graphNodeCloseProvider to the map
					// so we don't create and add any duplicate graphNodeCloseProviders.
					m[p] = source
				}

				g.Connect(dag.BasicEdge(source, v))
			}
		}
	}

	return nil
}

//.........这里部分代码省略.........
	for d, _ := range destroyers {
		// d is what is being destroyed. We parse the resource address
		// which it came from it is a panic if this fails.
		addr, err := ParseResourceAddress(d)
		if err != nil {
			panic(err)
		}

		// This part is a little bit weird but is the best way to
		// find the dependencies we need to: build a graph and use the
		// attach config and state transformers then ask for references.
		node := &NodeAbstractResource{Addr: addr}
		tempG.Add(node)
	}

	// Run the graph transforms so we have the information we need to
	// build references.
	for _, s := range steps {
		if err := s.Transform(&tempG); err != nil {
			return err
		}
	}

	// Create a reference map for easy lookup
	refMap := NewReferenceMap(tempG.Vertices())

	// Go through all the nodes in the graph and determine what they
	// depend on.
	for _, v := range tempG.Vertices() {
		// Find all the references
		refs, _ := refMap.References(v)
		log.Printf(
			"[TRACE] DestroyEdgeTransformer: creation node %q references %v",
			dag.VertexName(v), refs)

		// If we have no references, then we won't need to do anything
		if len(refs) == 0 {
			continue
		}

		// Get the destroy node for this. In the example of our struct,
		// we are currently at B and we're looking for B_d.
		rn, ok := v.(GraphNodeResource)
		if !ok {
			continue
		}

		addr := rn.ResourceAddr()
		if addr == nil {
			continue
		}

		dns := destroyers[addr.String()]

		// We have dependencies, check if any are being destroyed
		// to build the list of things that we must depend on!
		//
		// In the example of the struct, if we have:
		//
		//   B_d => A_d => A => B
		//
		// Then at this point in the algorithm we started with B_d,
		// we built B (to get dependencies), and we found A. We're now looking
		// to see if A_d exists.
		var depDestroyers []dag.Vertex
		for _, v := range refs {
			rn, ok := v.(GraphNodeResource)
			if !ok {
				continue
			}

			addr := rn.ResourceAddr()
			if addr == nil {
				continue
			}

			key := addr.String()
			if ds, ok := destroyers[key]; ok {
				for _, d := range ds {
					depDestroyers = append(depDestroyers, d.(dag.Vertex))
					log.Printf(
						"[TRACE] DestroyEdgeTransformer: destruction of %q depends on %s",
						key, dag.VertexName(d))
				}
			}
		}

		// Go through and make the connections. Use the variable
		// names "a_d" and "b_d" to reference our example.
		for _, a_d := range dns {
			for _, b_d := range depDestroyers {
				if b_d != a_d {
					g.Connect(dag.BasicEdge(b_d, a_d))
				}
			}
		}
	}

	return nil
}