8 "github.com/hashicorp/terraform/config"
9 "github.com/hashicorp/terraform/dag"
12 // GraphNodeReferenceable must be implemented by any node that represents
13 // a Terraform thing that can be referenced (resource, module, etc.).
15 // Even if the thing has no name, this should return an empty list. By
16 // implementing this and returning a non-nil result, you say that this CAN
17 // be referenced and other methods of referencing may still be possible (such
19 type GraphNodeReferenceable interface {
20 // ReferenceableName is the name by which this can be referenced.
21 // This can be either just the type, or include the field. Example:
22 // "aws_instance.bar" or "aws_instance.bar.id".
23 ReferenceableName() []string
26 // GraphNodeReferencer must be implemented by nodes that reference other
27 // Terraform items and therefore depend on them.
28 type GraphNodeReferencer interface {
29 // References are the list of things that this node references. This
30 // can include fields or just the type, just like GraphNodeReferenceable
35 // GraphNodeReferenceGlobal is an interface that can optionally be
36 // implemented. If ReferenceGlobal returns true, then the References()
37 // and ReferenceableName() must be _fully qualified_ with "module.foo.bar"
40 // This allows a node to reference and be referenced by a specific name
41 // that may cross module boundaries. This can be very dangerous so use
44 // The primary use case for this is module boundaries (variables coming in).
45 type GraphNodeReferenceGlobal interface {
46 // Set to true to signal that references and name are fully
47 // qualified. See the above docs for more information.
48 ReferenceGlobal() bool
51 // ReferenceTransformer is a GraphTransformer that connects all the
52 // nodes that reference each other in order to form the proper ordering.
53 type ReferenceTransformer struct{}
55 func (t *ReferenceTransformer) Transform(g *Graph) error {
56 // Build a reference map so we can efficiently look up the references
58 m := NewReferenceMap(vs)
60 // Find the things that reference things and connect them
61 for _, v := range vs {
62 parents, _ := m.References(v)
63 parentsDbg := make([]string, len(parents))
64 for i, v := range parents {
65 parentsDbg[i] = dag.VertexName(v)
68 "[DEBUG] ReferenceTransformer: %q references: %v",
69 dag.VertexName(v), parentsDbg)
71 for _, parent := range parents {
72 g.Connect(dag.BasicEdge(v, parent))
79 // DestroyReferenceTransformer is a GraphTransformer that reverses the edges
80 // for locals and outputs that depend on other nodes which will be
81 // removed during destroy. If a destroy node is evaluated before the local or
82 // output value, it will be removed from the state, and the later interpolation
84 type DestroyValueReferenceTransformer struct{}
86 func (t *DestroyValueReferenceTransformer) Transform(g *Graph) error {
88 for _, v := range vs {
90 case *NodeApplyableOutput, *NodeLocal:
96 // reverse any outgoing edges so that the value is evaluated first.
97 for _, e := range g.EdgesFrom(v) {
100 // only destroy nodes will be evaluated in reverse
101 if _, ok := target.(GraphNodeDestroyer); !ok {
105 log.Printf("[TRACE] output dep: %s", dag.VertexName(target))
108 g.Connect(&DestroyEdge{S: target, T: v})
115 // PruneUnusedValuesTransformer is s GraphTransformer that removes local and
116 // output values which are not referenced in the graph. Since outputs and
117 // locals always need to be evaluated, if they reference a resource that is not
118 // available in the state the interpolation could fail.
119 type PruneUnusedValuesTransformer struct{}
121 func (t *PruneUnusedValuesTransformer) Transform(g *Graph) error {
122 // this might need multiple runs in order to ensure that pruning a value
123 // doesn't effect a previously checked value.
124 for removed := 0; ; removed = 0 {
125 for _, v := range g.Vertices() {
127 case *NodeApplyableOutput, *NodeLocal:
133 dependants := g.UpEdges(v)
135 switch dependants.Len() {
137 // nothing at all depends on this
141 // because an output's destroy node always depends on the output,
142 // we need to check for the case of a single destroy node.
143 d := dependants.List()[0]
144 if _, ok := d.(*NodeDestroyableOutput); ok {
158 // ReferenceMap is a structure that can be used to efficiently check
159 // for references on a graph.
160 type ReferenceMap struct {
161 // m is the mapping of referenceable name to list of verticies that
162 // implement that name. This is built on initialization.
163 references map[string][]dag.Vertex
164 referencedBy map[string][]dag.Vertex
167 // References returns the list of vertices that this vertex
168 // references along with any missing references.
169 func (m *ReferenceMap) References(v dag.Vertex) ([]dag.Vertex, []string) {
170 rn, ok := v.(GraphNodeReferencer)
175 var matches []dag.Vertex
177 prefix := m.prefix(v)
179 for _, ns := range rn.References() {
181 for _, n := range strings.Split(ns, "/") {
183 parents, ok := m.references[n]
188 // Mark that we found a match
191 for _, p := range parents {
192 // don't include self-references
196 matches = append(matches, p)
203 missing = append(missing, ns)
207 return matches, missing
210 // ReferencedBy returns the list of vertices that reference the
212 func (m *ReferenceMap) ReferencedBy(v dag.Vertex) []dag.Vertex {
213 rn, ok := v.(GraphNodeReferenceable)
218 var matches []dag.Vertex
219 prefix := m.prefix(v)
220 for _, n := range rn.ReferenceableName() {
222 children, ok := m.referencedBy[n]
227 // Make sure this isn't a self reference, which isn't included
229 for _, p := range children {
239 matches = append(matches, children...)
245 func (m *ReferenceMap) prefix(v dag.Vertex) string {
246 // If the node is stating it is already fully qualified then
247 // we don't have to create the prefix!
248 if gn, ok := v.(GraphNodeReferenceGlobal); ok && gn.ReferenceGlobal() {
252 // Create the prefix based on the path
254 if pn, ok := v.(GraphNodeSubPath); ok {
255 if path := normalizeModulePath(pn.Path()); len(path) > 1 {
256 prefix = modulePrefixStr(path) + "."
263 // NewReferenceMap is used to create a new reference map for the
264 // given set of vertices.
265 func NewReferenceMap(vs []dag.Vertex) *ReferenceMap {
268 // Build the lookup table
269 refMap := make(map[string][]dag.Vertex)
270 for _, v := range vs {
271 // We're only looking for referenceable nodes
272 rn, ok := v.(GraphNodeReferenceable)
277 // Go through and cache them
278 prefix := m.prefix(v)
279 for _, n := range rn.ReferenceableName() {
281 refMap[n] = append(refMap[n], v)
284 // If there is a path, it is always referenceable by that. For
285 // example, if this is a referenceable thing at path []string{"foo"},
286 // then it can be referenced at "module.foo"
287 if pn, ok := v.(GraphNodeSubPath); ok {
288 for _, p := range ReferenceModulePath(pn.Path()) {
289 refMap[p] = append(refMap[p], v)
294 // Build the lookup table for referenced by
295 refByMap := make(map[string][]dag.Vertex)
296 for _, v := range vs {
297 // We're only looking for referenceable nodes
298 rn, ok := v.(GraphNodeReferencer)
303 // Go through and cache them
304 prefix := m.prefix(v)
305 for _, n := range rn.References() {
307 refByMap[n] = append(refByMap[n], v)
311 m.references = refMap
312 m.referencedBy = refByMap
316 // Returns the reference name for a module path. The path "foo" would return
317 // "module.foo". If this is a deeply nested module, it will be every parent
318 // as well. For example: ["foo", "bar"] would return both "module.foo" and
319 // "module.foo.module.bar"
320 func ReferenceModulePath(p []string) []string {
321 p = normalizeModulePath(p)
327 result := make([]string, 0, len(p)-1)
328 for i := len(p); i > 1; i-- {
329 result = append(result, modulePrefixStr(p[:i]))
335 // ReferencesFromConfig returns the references that a configuration has
336 // based on the interpolated variables in a configuration.
337 func ReferencesFromConfig(c *config.RawConfig) []string {
339 for _, v := range c.Variables {
340 if r := ReferenceFromInterpolatedVar(v); len(r) > 0 {
341 result = append(result, r...)
348 // ReferenceFromInterpolatedVar returns the reference from this variable,
349 // or an empty string if there is no reference.
350 func ReferenceFromInterpolatedVar(v config.InterpolatedVariable) []string {
351 switch v := v.(type) {
352 case *config.ModuleVariable:
353 return []string{fmt.Sprintf("module.%s.output.%s", v.Name, v.Field)}
354 case *config.ResourceVariable:
357 // If we have a multi-reference (splat), then we depend on ALL
358 // resources with this type/name.
359 if v.Multi && v.Index == -1 {
360 return []string{fmt.Sprintf("%s.*", id)}
363 // Otherwise, we depend on a specific index.
365 if !v.Multi || v.Index == -1 {
369 // Depend on the index, as well as "N" which represents the
370 // un-expanded set of resources.
371 return []string{fmt.Sprintf("%s.%d/%s.N", id, idx, id)}
372 case *config.UserVariable:
373 return []string{fmt.Sprintf("var.%s", v.Name)}
374 case *config.LocalVariable:
375 return []string{fmt.Sprintf("local.%s", v.Name)}
381 func modulePrefixStr(p []string) string {
383 if len(p) > 0 && p[0] == rootModulePath[0] {
387 parts := make([]string, 0, len(p)*2)
388 for _, p := range p {
389 parts = append(parts, "module", p)
392 return strings.Join(parts, ".")
395 func modulePrefixList(result []string, prefix string) []string {
397 for i, v := range result {
398 result[i] = fmt.Sprintf("%s.%s", prefix, v)