7 "github.com/hashicorp/hcl2/hcl"
8 "github.com/hashicorp/terraform/configs/configschema"
9 "github.com/hashicorp/terraform/lang"
11 "github.com/hashicorp/terraform/addrs"
12 "github.com/hashicorp/terraform/config"
13 "github.com/hashicorp/terraform/dag"
16 // GraphNodeReferenceable must be implemented by any node that represents
17 // a Terraform thing that can be referenced (resource, module, etc.).
19 // Even if the thing has no name, this should return an empty list. By
20 // implementing this and returning a non-nil result, you say that this CAN
21 // be referenced and other methods of referencing may still be possible (such
23 type GraphNodeReferenceable interface {
26 // ReferenceableAddrs returns a list of addresses through which this can be
28 ReferenceableAddrs() []addrs.Referenceable
31 // GraphNodeReferencer must be implemented by nodes that reference other
32 // Terraform items and therefore depend on them.
33 type GraphNodeReferencer interface {
36 // References returns a list of references made by this node, which
37 // include both a referenced address and source location information for
39 References() []*addrs.Reference
42 // GraphNodeReferenceOutside is an interface that can optionally be implemented.
43 // A node that implements it can specify that its own referenceable addresses
44 // and/or the addresses it references are in a different module than the
47 // Any referenceable addresses returned by ReferenceableAddrs are interpreted
48 // relative to the returned selfPath.
50 // Any references returned by References are interpreted relative to the
51 // returned referencePath.
53 // It is valid but not required for either of these paths to match what is
54 // returned by method Path, though if both match the main Path then there
55 // is no reason to implement this method.
57 // The primary use-case for this is the nodes representing module input
58 // variables, since their expressions are resolved in terms of their calling
59 // module, but they are still referenced from their own module.
60 type GraphNodeReferenceOutside interface {
61 // ReferenceOutside returns a path in which any references from this node
63 ReferenceOutside() (selfPath, referencePath addrs.ModuleInstance)
66 // ReferenceTransformer is a GraphTransformer that connects all the
67 // nodes that reference each other in order to form the proper ordering.
68 type ReferenceTransformer struct{}
70 func (t *ReferenceTransformer) Transform(g *Graph) error {
71 // Build a reference map so we can efficiently look up the references
73 m := NewReferenceMap(vs)
75 // Find the things that reference things and connect them
76 for _, v := range vs {
77 parents, _ := m.References(v)
78 parentsDbg := make([]string, len(parents))
79 for i, v := range parents {
80 parentsDbg[i] = dag.VertexName(v)
83 "[DEBUG] ReferenceTransformer: %q references: %v",
84 dag.VertexName(v), parentsDbg)
86 for _, parent := range parents {
87 g.Connect(dag.BasicEdge(v, parent))
94 // DestroyReferenceTransformer is a GraphTransformer that reverses the edges
95 // for locals and outputs that depend on other nodes which will be
96 // removed during destroy. If a destroy node is evaluated before the local or
97 // output value, it will be removed from the state, and the later interpolation
99 type DestroyValueReferenceTransformer struct{}
101 func (t *DestroyValueReferenceTransformer) Transform(g *Graph) error {
103 for _, v := range vs {
105 case *NodeApplyableOutput, *NodeLocal:
111 // reverse any outgoing edges so that the value is evaluated first.
112 for _, e := range g.EdgesFrom(v) {
115 // only destroy nodes will be evaluated in reverse
116 if _, ok := target.(GraphNodeDestroyer); !ok {
120 log.Printf("[TRACE] output dep: %s", dag.VertexName(target))
123 g.Connect(&DestroyEdge{S: target, T: v})
130 // PruneUnusedValuesTransformer is s GraphTransformer that removes local and
131 // output values which are not referenced in the graph. Since outputs and
132 // locals always need to be evaluated, if they reference a resource that is not
133 // available in the state the interpolation could fail.
134 type PruneUnusedValuesTransformer struct{}
136 func (t *PruneUnusedValuesTransformer) Transform(g *Graph) error {
137 // this might need multiple runs in order to ensure that pruning a value
138 // doesn't effect a previously checked value.
139 for removed := 0; ; removed = 0 {
140 for _, v := range g.Vertices() {
142 case *NodeApplyableOutput, *NodeLocal:
148 dependants := g.UpEdges(v)
150 switch dependants.Len() {
152 // nothing at all depends on this
156 // because an output's destroy node always depends on the output,
157 // we need to check for the case of a single destroy node.
158 d := dependants.List()[0]
159 if _, ok := d.(*NodeDestroyableOutput); ok {
173 // ReferenceMap is a structure that can be used to efficiently check
174 // for references on a graph.
175 type ReferenceMap struct {
176 // vertices is a map from internal reference keys (as produced by the
177 // mapKey method) to one or more vertices that are identified by each key.
179 // A particular reference key might actually identify multiple vertices,
180 // e.g. in situations where one object is contained inside another.
181 vertices map[string][]dag.Vertex
183 // edges is a map whose keys are a subset of the internal reference keys
184 // from "vertices", and whose values are the nodes that refer to each
185 // key. The values in this map are the referrers, while values in
186 // "verticies" are the referents. The keys in both cases are referents.
187 edges map[string][]dag.Vertex
190 // References returns the set of vertices that the given vertex refers to,
191 // and any referenced addresses that do not have corresponding vertices.
192 func (m *ReferenceMap) References(v dag.Vertex) ([]dag.Vertex, []addrs.Referenceable) {
193 rn, ok := v.(GraphNodeReferencer)
197 if _, ok := v.(GraphNodeSubPath); !ok {
201 var matches []dag.Vertex
202 var missing []addrs.Referenceable
204 for _, ref := range rn.References() {
205 subject := ref.Subject
207 key := m.referenceMapKey(v, subject)
208 if _, exists := m.vertices[key]; !exists {
209 // If what we were looking for was a ResourceInstance then we
210 // might be in a resource-oriented graph rather than an
211 // instance-oriented graph, and so we'll see if we have the
212 // resource itself instead.
213 switch ri := subject.(type) {
214 case addrs.ResourceInstance:
215 subject = ri.ContainingResource()
216 case addrs.ResourceInstancePhase:
217 subject = ri.ContainingResource()
219 key = m.referenceMapKey(v, subject)
222 vertices := m.vertices[key]
223 for _, rv := range vertices {
224 // don't include self-references
228 matches = append(matches, rv)
230 if len(vertices) == 0 {
231 missing = append(missing, ref.Subject)
235 return matches, missing
238 // Referrers returns the set of vertices that refer to the given vertex.
239 func (m *ReferenceMap) Referrers(v dag.Vertex) []dag.Vertex {
240 rn, ok := v.(GraphNodeReferenceable)
244 sp, ok := v.(GraphNodeSubPath)
249 var matches []dag.Vertex
250 for _, addr := range rn.ReferenceableAddrs() {
251 key := m.mapKey(sp.Path(), addr)
252 referrers, ok := m.edges[key]
257 // If the referrer set includes our own given vertex then we skip,
258 // since we don't want to return self-references.
260 for _, p := range referrers {
270 matches = append(matches, referrers...)
276 func (m *ReferenceMap) mapKey(path addrs.ModuleInstance, addr addrs.Referenceable) string {
277 return fmt.Sprintf("%s|%s", path.String(), addr.String())
280 // vertexReferenceablePath returns the path in which the given vertex can be
281 // referenced. This is the path that its results from ReferenceableAddrs
282 // are considered to be relative to.
284 // Only GraphNodeSubPath implementations can be referenced, so this method will
285 // panic if the given vertex does not implement that interface.
286 func (m *ReferenceMap) vertexReferenceablePath(v dag.Vertex) addrs.ModuleInstance {
287 sp, ok := v.(GraphNodeSubPath)
289 // Only nodes with paths can participate in a reference map.
290 panic(fmt.Errorf("vertexMapKey on vertex type %T which doesn't implement GraphNodeSubPath", sp))
293 if outside, ok := v.(GraphNodeReferenceOutside); ok {
294 // Vertex is referenced from a different module than where it was
296 path, _ := outside.ReferenceOutside()
300 // Vertex is referenced from the same module as where it was declared.
304 // vertexReferencePath returns the path in which references _from_ the given
305 // vertex must be interpreted.
307 // Only GraphNodeSubPath implementations can have references, so this method
308 // will panic if the given vertex does not implement that interface.
309 func vertexReferencePath(referrer dag.Vertex) addrs.ModuleInstance {
310 sp, ok := referrer.(GraphNodeSubPath)
312 // Only nodes with paths can participate in a reference map.
313 panic(fmt.Errorf("vertexReferencePath on vertex type %T which doesn't implement GraphNodeSubPath", sp))
316 var path addrs.ModuleInstance
317 if outside, ok := referrer.(GraphNodeReferenceOutside); ok {
318 // Vertex makes references to objects in a different module than where
320 _, path = outside.ReferenceOutside()
324 // Vertex makes references to objects in the same module as where it
329 // referenceMapKey produces keys for the "edges" map. "referrer" is the vertex
330 // that the reference is from, and "addr" is the address of the object being
333 // The result is an opaque string that includes both the address of the given
334 // object and the address of the module instance that object belongs to.
336 // Only GraphNodeSubPath implementations can be referrers, so this method will
337 // panic if the given vertex does not implement that interface.
338 func (m *ReferenceMap) referenceMapKey(referrer dag.Vertex, addr addrs.Referenceable) string {
339 path := vertexReferencePath(referrer)
340 return m.mapKey(path, addr)
343 // NewReferenceMap is used to create a new reference map for the
344 // given set of vertices.
345 func NewReferenceMap(vs []dag.Vertex) *ReferenceMap {
348 // Build the lookup table
349 vertices := make(map[string][]dag.Vertex)
350 for _, v := range vs {
351 _, ok := v.(GraphNodeSubPath)
353 // Only nodes with paths can participate in a reference map.
357 // We're only looking for referenceable nodes
358 rn, ok := v.(GraphNodeReferenceable)
363 path := m.vertexReferenceablePath(v)
365 // Go through and cache them
366 for _, addr := range rn.ReferenceableAddrs() {
367 key := m.mapKey(path, addr)
368 vertices[key] = append(vertices[key], v)
371 // Any node can be referenced by the address of the module it belongs
372 // to or any of that module's ancestors.
373 for _, addr := range path.Ancestors()[1:] {
374 // Can be referenced either as the specific call instance (with
375 // an instance key) or as the bare module call itself (the "module"
376 // block in the parent module that created the instance).
377 callPath, call := addr.Call()
378 callInstPath, callInst := addr.CallInstance()
379 callKey := m.mapKey(callPath, call)
380 callInstKey := m.mapKey(callInstPath, callInst)
381 vertices[callKey] = append(vertices[callKey], v)
382 vertices[callInstKey] = append(vertices[callInstKey], v)
386 // Build the lookup table for referenced by
387 edges := make(map[string][]dag.Vertex)
388 for _, v := range vs {
389 _, ok := v.(GraphNodeSubPath)
391 // Only nodes with paths can participate in a reference map.
395 rn, ok := v.(GraphNodeReferencer)
397 // We're only looking for referenceable nodes
401 // Go through and cache them
402 for _, ref := range rn.References() {
403 if ref.Subject == nil {
404 // Should never happen
405 panic(fmt.Sprintf("%T.References returned reference with nil subject", rn))
407 key := m.referenceMapKey(v, ref.Subject)
408 edges[key] = append(edges[key], v)
412 m.vertices = vertices
417 // ReferencesFromConfig returns the references that a configuration has
418 // based on the interpolated variables in a configuration.
419 func ReferencesFromConfig(body hcl.Body, schema *configschema.Block) []*addrs.Reference {
423 refs, _ := lang.ReferencesInBlock(body, schema)
427 // ReferenceFromInterpolatedVar returns the reference from this variable,
428 // or an empty string if there is no reference.
429 func ReferenceFromInterpolatedVar(v config.InterpolatedVariable) []string {
430 switch v := v.(type) {
431 case *config.ModuleVariable:
432 return []string{fmt.Sprintf("module.%s.output.%s", v.Name, v.Field)}
433 case *config.ResourceVariable:
436 // If we have a multi-reference (splat), then we depend on ALL
437 // resources with this type/name.
438 if v.Multi && v.Index == -1 {
439 return []string{fmt.Sprintf("%s.*", id)}
442 // Otherwise, we depend on a specific index.
444 if !v.Multi || v.Index == -1 {
448 // Depend on the index, as well as "N" which represents the
449 // un-expanded set of resources.
450 return []string{fmt.Sprintf("%s.%d/%s.N", id, idx, id)}
451 case *config.UserVariable:
452 return []string{fmt.Sprintf("var.%s", v.Name)}
453 case *config.LocalVariable:
454 return []string{fmt.Sprintf("local.%s", v.Name)}
460 // appendResourceDestroyReferences identifies resource and resource instance
461 // references in the given slice and appends to it the "destroy-phase"
462 // equivalents of those references, returning the result.
464 // This can be used in the References implementation for a node which must also
465 // depend on the destruction of anything it references.
466 func appendResourceDestroyReferences(refs []*addrs.Reference) []*addrs.Reference {
468 for _, ref := range given {
469 switch tr := ref.Subject.(type) {
471 newRef := *ref // shallow copy
472 newRef.Subject = tr.Phase(addrs.ResourceInstancePhaseDestroy)
473 refs = append(refs, &newRef)
474 case addrs.ResourceInstance:
475 newRef := *ref // shallow copy
476 newRef.Subject = tr.Phase(addrs.ResourceInstancePhaseDestroy)
477 refs = append(refs, &newRef)
483 func modulePrefixStr(p addrs.ModuleInstance) string {
487 func modulePrefixList(result []string, prefix string) []string {
489 for i, v := range result {
490 result[i] = fmt.Sprintf("%s.%s", prefix, v)