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

fakecloud_cloudformation/template/
resolution.rs
