fakecloud_cloudformation/template/
resolution.rs

1//! `resolution` concerns from template.rs (audit-2026-05-19).
2
3use super::*;
4
5/// Re-resolve a single resource definition's properties with updated physical IDs.
6pub fn resolve_resource_properties(
7    resource: &ResourceDefinition,
8    template_body: &str,
9    parameters: &BTreeMap<String, String>,
10    resource_physical_ids: &BTreeMap<String, String>,
11) -> Result<ResourceDefinition, String> {
12    resolve_resource_properties_with_attrs(
13        resource,
14        template_body,
15        parameters,
16        resource_physical_ids,
17        &BTreeMap::new(),
18        &BTreeMap::new(),
19    )
20}
21
22/// Re-resolve a single resource definition's properties with updated physical
23/// IDs and attribute values for `Fn::GetAtt`.
24pub fn resolve_resource_properties_with_attrs(
25    resource: &ResourceDefinition,
26    template_body: &str,
27    parameters: &BTreeMap<String, String>,
28    resource_physical_ids: &BTreeMap<String, String>,
29    resource_attributes: &BTreeMap<String, BTreeMap<String, String>>,
30    imports: &BTreeMap<String, String>,
31) -> Result<ResourceDefinition, String> {
32    let value: Value = if template_body.trim_start().starts_with('{') {
33        serde_json::from_str(template_body).map_err(|e| format!("Invalid JSON template: {e}"))?
34    } else {
35        serde_yaml::from_str(template_body).map_err(|e| format!("Invalid YAML template: {e}"))?
36    };
37    // Re-expand ForEach so the resource we look up matches the post-
38    // expansion logical IDs from the original parse.
39    let value = expand_for_each(&value, &BTreeMap::new(), parameters)?;
40    // Re-apply the SAM transform too: the original parse rewrote SAM
41    // resources (e.g. AWS::Serverless::StateMachine -> the native
42    // AWS::StepFunctions::StateMachine, Role -> RoleArn). Without this the
43    // properties get re-read from the raw SAM resource and the native
44    // provisioner sees SAM property names it doesn't understand.
45    let value = expand_sam(&value);
46
47    let resources_obj = value
48        .get("Resources")
49        .and_then(|v| v.as_object())
50        .ok_or("Template must contain a Resources section")?;
51
52    let raw_props = resources_obj
53        .get(&resource.logical_id)
54        .and_then(|r| r.get("Properties"))
55        .cloned()
56        .unwrap_or(Value::Object(serde_json::Map::new()));
57
58    // Re-evaluate Conditions / Mappings on every resolve so Fn::If picks
59    // the right branch and AWS::NoValue still strips at incremental
60    // provisioning time. Without this, the sentinel would leak into the
61    // provisioned property map.
62    let conditions = evaluate_conditions(&value, parameters)?;
63    let mappings = parse_mappings(&value);
64    let raw_props = apply_mappings(&raw_props, parameters, &mappings, &conditions)?;
65
66    let resolved = resolve_refs_full(
67        &raw_props,
68        parameters,
69        resources_obj,
70        resource_physical_ids,
71        resource_attributes,
72        imports,
73        &conditions,
74    );
75    let resolved = strip_no_value(resolved);
76
77    Ok(ResourceDefinition {
78        logical_id: resource.logical_id.clone(),
79        resource_type: resource.resource_type.clone(),
80        properties: resolved,
81    })
82}
83
84/// Compute a provisioning order for `resource_defs` such that every resource is
85/// provisioned *after* the resources it references — via an explicit
86/// `DependsOn` or an implicit `Ref` / `Fn::GetAtt` / `Fn::Sub` to another
87/// resource's logical id.
88///
89/// Returns a permutation of indices into `resource_defs`. CloudFormation
90/// provisions in dependency order; FakeCloud previously provisioned in template
91/// order, so a `Ref` to a not-yet-created resource resolved to the bare logical
92/// id (the "not yet provisioned" fallback in `resolve_refs_full`) and got baked
93/// into derived state — e.g. a Step Functions ASL whose `DefinitionSubstitutions`
94/// reference a Lambda declared later in the template, leaving the logical id in
95/// the definition and failing every invoke with `Lambda.ResourceNotFoundException`.
96///
97/// The graph is built from the post-`ForEach`/post-SAM template so the logical
98/// ids and reference shapes match what provisioning actually sees. Falls back to
99/// the original order on a parse failure or a dependency cycle (which real CFN
100/// rejects outright), and breaks ties by original index so the order is
101/// deterministic.
102pub fn dependency_order(
103    template_body: &str,
104    parameters: &BTreeMap<String, String>,
105    resource_defs: &[ResourceDefinition],
106) -> Vec<usize> {
107    let n = resource_defs.len();
108    let identity = || (0..n).collect::<Vec<usize>>();
109    if n < 2 {
110        return identity();
111    }
112
113    let parse = |body: &str| -> Result<Value, ()> {
114        if body.trim_start().starts_with('{') {
115            serde_json::from_str(body).map_err(|_| ())
116        } else {
117            serde_yaml::from_str(body).map_err(|_| ())
118        }
119    };
120    let Ok(value) = parse(template_body) else {
121        return identity();
122    };
123    // Match the logical ids the rest of provisioning sees (ForEach + SAM).
124    let Ok(value) = expand_for_each(&value, &BTreeMap::new(), parameters) else {
125        return identity();
126    };
127    let value = expand_sam(&value);
128    let Some(resources_obj) = value.get("Resources").and_then(|v| v.as_object()) else {
129        return identity();
130    };
131
132    let index_of: BTreeMap<&str, usize> = resource_defs
133        .iter()
134        .enumerate()
135        .map(|(i, r)| (r.logical_id.as_str(), i))
136        .collect();
137    let known: BTreeSet<&str> = index_of.keys().copied().collect();
138
139    // deps[i] = indices that resource i must be provisioned after.
140    let mut deps: Vec<BTreeSet<usize>> = vec![BTreeSet::new(); n];
141    for (i, r) in resource_defs.iter().enumerate() {
142        let Some(raw) = resources_obj.get(&r.logical_id) else {
143            continue;
144        };
145        let mut refs: BTreeSet<String> = BTreeSet::new();
146        match raw.get("DependsOn") {
147            Some(Value::String(s)) => {
148                refs.insert(s.clone());
149            }
150            Some(Value::Array(a)) => {
151                for x in a {
152                    if let Some(s) = x.as_str() {
153                        refs.insert(s.to_string());
154                    }
155                }
156            }
157            _ => {}
158        }
159        if let Some(props) = raw.get("Properties") {
160            collect_resource_refs(props, &known, &mut refs);
161        }
162        for name in refs {
163            if let Some(&j) = index_of.get(name.as_str()) {
164                if j != i {
165                    deps[i].insert(j);
166                }
167            }
168        }
169    }
170
171    // Kahn's algorithm; ready set ordered by original index for determinism.
172    let mut indeg: Vec<usize> = deps.iter().map(|d| d.len()).collect();
173    let mut dependents: Vec<Vec<usize>> = vec![Vec::new(); n];
174    for (i, d) in deps.iter().enumerate() {
175        for &j in d {
176            dependents[j].push(i);
177        }
178    }
179    let mut ready: BTreeSet<usize> = (0..n).filter(|&i| indeg[i] == 0).collect();
180    let mut order: Vec<usize> = Vec::with_capacity(n);
181    while let Some(&i) = ready.iter().next() {
182        ready.remove(&i);
183        order.push(i);
184        for &j in &dependents[i] {
185            indeg[j] -= 1;
186            if indeg[j] == 0 {
187                ready.insert(j);
188            }
189        }
190    }
191    if order.len() != n {
192        // Dependency cycle — append the unresolved remainder in original order.
193        let placed: BTreeSet<usize> = order.iter().copied().collect();
194        for i in 0..n {
195            if !placed.contains(&i) {
196                order.push(i);
197            }
198        }
199    }
200    order
201}
202
203/// Recursively collect the logical ids in `known` that `value` references via
204/// `Ref`, `Fn::GetAtt`, or `Fn::Sub`.
205fn collect_resource_refs(value: &Value, known: &BTreeSet<&str>, out: &mut BTreeSet<String>) {
206    match value {
207        Value::Object(map) => {
208            if let Some(Value::String(name)) = map.get("Ref") {
209                if known.contains(name.as_str()) {
210                    out.insert(name.clone());
211                }
212            }
213            if let Some(g) = map.get("Fn::GetAtt") {
214                let logical = match g {
215                    Value::Array(a) => a.first().and_then(|x| x.as_str()),
216                    Value::String(s) => s.split('.').next(),
217                    _ => None,
218                };
219                if let Some(l) = logical {
220                    if known.contains(l) {
221                        out.insert(l.to_string());
222                    }
223                }
224            }
225            if let Some(s) = map.get("Fn::Sub") {
226                collect_sub_refs(s, known, out);
227            }
228            // Recurse into every value to catch nested references.
229            for v in map.values() {
230                collect_resource_refs(v, known, out);
231            }
232        }
233        Value::Array(a) => {
234            for v in a {
235                collect_resource_refs(v, known, out);
236            }
237        }
238        _ => {}
239    }
240}
241
242/// Extract `${LogicalId}` / `${LogicalId.Attr}` references from an `Fn::Sub`
243/// (string form or `[template, {vars}]` form), skipping the locally-defined
244/// variables and `${!Literal}` escapes.
245fn collect_sub_refs(sub: &Value, known: &BTreeSet<&str>, out: &mut BTreeSet<String>) {
246    let (template, local_vars): (Option<&str>, BTreeSet<&str>) = match sub {
247        Value::String(t) => (Some(t.as_str()), BTreeSet::new()),
248        Value::Array(a) => {
249            let t = a.first().and_then(|x| x.as_str());
250            let vars = a
251                .get(1)
252                .and_then(|x| x.as_object())
253                .map(|m| m.keys().map(|k| k.as_str()).collect())
254                .unwrap_or_default();
255            (t, vars)
256        }
257        _ => (None, BTreeSet::new()),
258    };
259    let Some(t) = template else {
260        return;
261    };
262    let mut i = 0;
263    while let Some(start) = t[i..].find("${") {
264        let abs = i + start + 2;
265        let Some(end_rel) = t[abs..].find('}') else {
266            break;
267        };
268        let token = &t[abs..abs + end_rel];
269        // `${!X}` is a literal `${X}`, not a reference.
270        if !token.starts_with('!') {
271            let logical = token.split('.').next().unwrap_or(token).trim();
272            if !local_vars.contains(logical) && known.contains(logical) {
273                out.insert(logical.to_string());
274            }
275        }
276        i = abs + end_rel + 1;
277    }
278}
279
280#[cfg(test)]
281mod dependency_order_tests {
282    use super::*;
283
284    fn rd(logical: &str, resource_type: &str) -> ResourceDefinition {
285        ResourceDefinition {
286            logical_id: logical.to_string(),
287            resource_type: resource_type.to_string(),
288            properties: serde_json::json!({}),
289        }
290    }
291
292    // The Gap #3 scenario: a StateMachine declared (and sorting) before the
293    // Lambda it references via a DefinitionSubstitutions `Ref` must provision
294    // after that Lambda, so the substitution resolves to the function name.
295    #[test]
296    fn referenced_resource_is_ordered_first() {
297        let template = r#"{
298            "Resources": {
299                "Machine": {
300                    "Type": "AWS::StepFunctions::StateMachine",
301                    "Properties": {
302                        "DefinitionString": "${fn}",
303                        "DefinitionSubstitutions": {"fn": {"Ref": "WorkerFn"}}
304                    }
305                },
306                "WorkerFn": {"Type": "AWS::Lambda::Function", "Properties": {}}
307            }
308        }"#;
309        // Template order (alphabetical, as the parser yields): Machine, WorkerFn.
310        let defs = vec![
311            rd("Machine", "AWS::StepFunctions::StateMachine"),
312            rd("WorkerFn", "AWS::Lambda::Function"),
313        ];
314        let order = dependency_order(template, &BTreeMap::new(), &defs);
315        assert_eq!(
316            order,
317            vec![1, 0],
318            "WorkerFn must be provisioned before Machine"
319        );
320    }
321
322    #[test]
323    fn get_att_sub_and_depends_on_all_create_edges() {
324        // A: referenced by B via GetAtt, by C via Fn::Sub, by D via DependsOn.
325        let template = r#"{
326            "Resources": {
327                "B": {"Type": "X", "Properties": {"V": {"Fn::GetAtt": ["A", "Arn"]}}},
328                "C": {"Type": "X", "Properties": {"V": {"Fn::Sub": "p-${A}-s"}}},
329                "D": {"Type": "X", "DependsOn": "A", "Properties": {}},
330                "A": {"Type": "X", "Properties": {}}
331            }
332        }"#;
333        let defs = vec![rd("B", "X"), rd("C", "X"), rd("D", "X"), rd("A", "X")];
334        let order = dependency_order(template, &BTreeMap::new(), &defs);
335        let pos = |name: &str| {
336            order
337                .iter()
338                .position(|&i| defs[i].logical_id == name)
339                .unwrap()
340        };
341        assert!(pos("A") < pos("B"), "GetAtt edge");
342        assert!(pos("A") < pos("C"), "Fn::Sub edge");
343        assert!(pos("A") < pos("D"), "DependsOn edge");
344    }
345
346    #[test]
347    fn import_value_in_property_resolves_from_imports() {
348        // §1.5: Fn::ImportValue inside a resource property must resolve to the
349        // real exported value, not the empty string the old code baked.
350        let template = r#"{
351            "Resources": {
352                "Q": {"Type": "AWS::SQS::Queue", "Properties": {"QueueName": {"Fn::ImportValue": "SharedQueueName"}}}
353            }
354        }"#;
355        let mut imports = BTreeMap::new();
356        imports.insert("SharedQueueName".to_string(), "shared-q".to_string());
357        let resolved = resolve_resource_properties_with_attrs(
358            &rd("Q", "AWS::SQS::Queue"),
359            template,
360            &BTreeMap::new(),
361            &BTreeMap::new(),
362            &BTreeMap::new(),
363            &imports,
364        )
365        .unwrap();
366        assert_eq!(
367            resolved.properties["QueueName"],
368            serde_json::json!("shared-q")
369        );
370    }
371
372    #[test]
373    fn independent_resources_keep_original_order() {
374        let template =
375            r#"{"Resources": {"A": {"Type": "X"}, "B": {"Type": "X"}, "C": {"Type": "X"}}}"#;
376        let defs = vec![rd("A", "X"), rd("B", "X"), rd("C", "X")];
377        assert_eq!(
378            dependency_order(template, &BTreeMap::new(), &defs),
379            vec![0, 1, 2]
380        );
381    }
382
383    #[test]
384    fn sub_escape_and_local_vars_are_not_edges() {
385        // `${!A}` is a literal; `${V}` is a local Sub variable — neither is a
386        // dependency on resource A.
387        let template = r#"{
388            "Resources": {
389                "A": {"Type": "X", "Properties": {}},
390                "B": {"Type": "X", "Properties": {
391                    "V": {"Fn::Sub": ["${!A}-${V}", {"V": "literal"}]}
392                }}
393            }
394        }"#;
395        let defs = vec![rd("A", "X"), rd("B", "X")];
396        // No real edge -> original order preserved.
397        assert_eq!(
398            dependency_order(template, &BTreeMap::new(), &defs),
399            vec![0, 1]
400        );
401    }
402
403    #[test]
404    fn dependency_cycle_falls_back_to_original_order() {
405        let template = r#"{
406            "Resources": {
407                "A": {"Type": "X", "Properties": {"V": {"Ref": "B"}}},
408                "B": {"Type": "X", "Properties": {"V": {"Ref": "A"}}}
409            }
410        }"#;
411        let defs = vec![rd("A", "X"), rd("B", "X")];
412        assert_eq!(
413            dependency_order(template, &BTreeMap::new(), &defs),
414            vec![0, 1]
415        );
416    }
417}
fakecloud_cloudformation/template/resolution.rs

fakecloud_cloudformation/template/
resolution.rs
