Repository: aws-cloudformation/cfn-lint

Issue:
Performance problems with AWS::StepFunctions::StateMachine
**cfn-lint Version**
cfn-lint 1.18.4

**Provide additional details e.g. code snippets. _Be sure to remove any sensitive data._**
Hi,
first of all sorry if this is the wrong issue type but I´m not quite sure about the problem at the moment. 

We use cfn-lint in our CI/CD Pipeline to test CloudFormation templates. After an upgrade from version 0.8.x to 1.18.4 our lint job broke because cfn-lint took longer than 1 hour to lint the templates. The problematic templates only contain AWS::StepFunctions::StateMachine resources. It seems like cfn-lint takes extremely long to parse the DefinitionString's if they contain many intrinsic functions like "Ref", "FindInMap", "If". It takes so long, that I don't even know if it would actually finish execution. I let it ran locally for over an hour and it wouldn't proceed past the E1001 rule:

```
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Starting match function for rule E3041 at 2025-01-06 16:13:04.160515
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Complete match function for rule E3041 at 2025-01-06 16:13:04.160525.  Ran in 0:00:00.000010
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Starting match function for rule E3023 at 2025-01-06 16:13:04.160540
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Complete match function for rule E3023 at 2025-01-06 16:13:04.160550.  Ran in 0:00:00.000010
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Starting match function for rule E3029 at 2025-01-06 16:13:04.160564
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Complete match function for rule E3029 at 2025-01-06 16:13:04.160575.  Ran in 0:00:00.000011
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Starting match function for rule E1005 at 2025-01-06 16:13:04.160589
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Complete match function for rule E1005 at 2025-01-06 16:13:04.160599.  Ran in 0:00:00.000010
2025-01-06 16:13:04,160 - cfnlint.rules._rule - DEBUG - Starting match function for rule E1001 at 2025-01-06 16:13:04.160613
```

Because I couldn't understand what the problem is I cloned the cfn-lint repo and started to debug it.
So far I can only tell that at some point, this for loop: https://github.com/aws-cloudformation/cfn-lint/blob/main/src/cfnlint/rules/jsonschema/CfnLint.py#L33  won't proceed because cfn-lint tries to constantly resolve values: https://github.com/aws-cloudformation/cfn-lint/blob/main/src/cfnlint/jsonschema/validators.py#L172 and this goes on forever.

Unfortunately I´m not able to provide a CloudFormation template at the moment because it`s too big (1.4k loc) and contains too many sensitive data. I try to recreate a "not working" minimal example in the next few days but does someone has some guesses in the meantime what the problem could be?

Thank you!

Discussion:
@kddejong: @b01f6b82b8a347f6045406b8f31f239d Can you see if the solution in #3717 helps your use case?  Lots of `if` conditions are very possibly the issue here as we are trying to compute different scenarios to validate all those scenarios.  If the number of scenarios are large, the equations can be slow. We try to minimize this by putting in max limits.@b01f6b82b8a347f6045406b8f31f239d: Unfortunately I didn't see any improvement. 
One template took ~6min whether pycosat and/or a fixed seed was used or not. The other still didn't finish after a few hours.
But we only have like 7 If Statements which are not nested. Join, Ref and FindInMap on the other hand get used pretty extensively in the DefinitionString's.

I try to supply a "non working" example as soon as possible..@kddejong: Thanks.  If needed we may have some options to exchange that template privately if that would help.@b01f6b82b8a347f6045406b8f31f239d: I think I have a non working template. If you don't mind I would still prefer to send it to you privately ^^@kddejong: You can email to `kddejong@amazon.com`@kddejong: Based on this template.  We are adding to #3906 to improve the logic of how context is passed between intrinsic functions when doing resolution. 

I also improved the testing to make sure more of the functions are doing the appropriate things.

Solution patch:
diff --git a/src/cfnlint/jsonschema/_resolvers_cfn.py b/src/cfnlint/jsonschema/_resolvers_cfn.py
index 0088ad2e4..5fff8b6b3 100644
--- a/src/cfnlint/jsonschema/_resolvers_cfn.py
+++ b/src/cfnlint/jsonschema/_resolvers_cfn.py
@@ -7,6 +7,7 @@ from __future__ import annotations
 
 import json
 from collections import deque
+from copy import deepcopy
 from typing import Any, Iterator
 
 import regex as re
@@ -243,9 +244,9 @@ def find_in_map(validator: Validator, instance: Any) -> ResolutionResult:
                 ):
                     yield (
                         value,
-                        validator.evolve(
-                            context=validator.context.evolve(
-                                path=validator.context.path.evolve(
+                        second_v.evolve(
+                            context=second_v.context.evolve(
+                                path=second_v.context.path.evolve(
                                     value_path=deque(
                                         [
                                             "Mappings",
@@ -282,15 +283,17 @@ def get_azs(validator: Validator, instance: Any) -> ResolutionResult:
                 yield AVAILABILITY_ZONES.get(instance), v, None
 
 
-def _join_expansion(validator: Validator, instances: Any) -> Iterator[Any]:
+def _join_expansion(
+    validator: Validator, instances: Any
+) -> Iterator[tuple[Any, Validator]]:
     if len(instances) == 0:
         return
 
     if len(instances) == 1:
-        for value, _, _ in validator.resolve_value(instances[0]):
+        for value, instance_validator, _ in validator.resolve_value(instances[0]):
             if not isinstance(value, (str, int, float, bool)):
                 raise ValueError(f"Incorrect value type for {value!r}")
-            yield [value]
+            yield [value], instance_validator
         return
 
     for value, instance_validator, errs in validator.resolve_value(instances[0]):
@@ -298,8 +301,10 @@ def _join_expansion(validator: Validator, instances: Any) -> Iterator[Any]:
             continue
         if not isinstance(value, (str, int, float, bool)):
             raise ValueError(f"Incorrect value type for {value!r}")
-        for values in _join_expansion(instance_validator, instances[1:]):
-            yield [value] + values
+        for values, expansion_validator in _join_expansion(
+            instance_validator, instances[1:]
+        ):
+            yield [value] + values, expansion_validator
 
 
 def join(validator: Validator, instance: Any) -> ResolutionResult:
@@ -312,12 +317,21 @@ def join(validator: Validator, instance: Any) -> ResolutionResult:
     for delimiter, delimiter_v, _ in validator.resolve_value(instance[0]):
         if not delimiter_v.is_type(delimiter, "string"):
             continue
-        for values, values_v, _ in validator.resolve_value(instance[1]):
+        for values, values_v, _ in delimiter_v.resolve_value(instance[1]):
             if not values_v.is_type(values, "array"):
                 continue
             try:
-                for value in _join_expansion(values_v, values):
-                    yield delimiter.join([str(v) for v in value]), values_v, None
+                for value, expansion_validator in _join_expansion(values_v, values):
+                    # reset the value path because we could get a Ref value_path
+                    yield delimiter.join(
+                        [str(v) for v in value]
+                    ), expansion_validator.evolve(
+                        context=expansion_validator.context.evolve(
+                            path=expansion_validator.context.path.evolve(
+                                value_path=deque([])
+                            )
+                        )
+                    ), None
             except (ValueError, TypeError):
                 return
 
@@ -417,7 +431,7 @@ def sub(validator: Validator, instance: Any) -> ResolutionResult:
             return
 
         string = instance[0]
-        parameters = instance[1]
+        parameters = deepcopy(instance[1])
         if not validator.is_type(string, "string"):
             return
         if not validator.is_type(parameters, "object"):
@@ -438,7 +452,11 @@ def sub(validator: Validator, instance: Any) -> ResolutionResult:
                     ref_values=resolved_parameters,
                 )
             )
-            yield from _sub_string(resolved_validator, string)
+            for sub_string, sub_validator, _ in _sub_string(resolved_validator, string):
+                for key in instance[1].keys():
+                    sub_validator.context.ref_values.pop(key, None)
+
+                yield sub_string, sub_validator, None
 
         return
 


Test patch:
diff --git a/test/unit/module/jsonschema/test_resolvers_cfn.py b/test/unit/module/jsonschema/test_resolvers_cfn.py
index fbec3d1ec..bc3a75549 100644
--- a/test/unit/module/jsonschema/test_resolvers_cfn.py
+++ b/test/unit/module/jsonschema/test_resolvers_cfn.py
@@ -8,7 +8,7 @@ from collections import deque
 import pytest
 
 from cfnlint.context._mappings import Mappings
-from cfnlint.context.context import Context, Parameter, Resource
+from cfnlint.context.context import Context, Parameter, Path, Resource
 from cfnlint.jsonschema import ValidationError
 from cfnlint.jsonschema.validators import CfnTemplateValidator
 
@@ -24,10 +24,16 @@ def _resolve(name, instance, expected_results, **kwargs):
 
     for i, (instance, v, errors) in enumerate(resolutions):
         assert instance == expected_results[i][0], f"{name!r} got {instance!r}"
-        assert (
-            v.context.path.value_path == expected_results[i][1]
-        ), f"{name!r} got {v.context.path.value_path!r}"
         assert errors == expected_results[i][2], f"{name!r} got {errors!r}"
+        if not errors:
+            expected_context = expected_results[i][1]
+            _, expected_context = list(expected_context.ref_value("AWS::Region"))[0]
+            assert (
+                v.context.path == expected_context.path
+            ), f"{name!r} got {v.context.path!r}"
+            assert (
+                v.context.ref_values == expected_context.ref_values
+            ), f"{name!r} got {v.context.ref_values!r}"
 
 
 @pytest.mark.parametrize(
@@ -203,7 +209,7 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid Join with a list of strings",
             {"Fn::Join": [".", ["a", "b", "c"]]},
-            [("a.b.c", deque([]), None)],
+            [("a.b.c", Context(), None)],
         ),
         (
             "Valid GetAZs with empty string",
@@ -218,7 +224,7 @@ def test_invalid_functions(name, instance, response):
                         "us-east-1e",
                         "us-east-1f",
                     ],
-                    deque([]),
+                    Context(),
                     None,
                 )
             ],
@@ -226,14 +232,32 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid FindInMap with bad keys and a default value",
             {"Fn::FindInMap": ["foo", "bar", "value", {"DefaultValue": "default"}]},
-            [("default", deque([4, "DefaultValue"]), None)],
+            [
+                (
+                    "default",
+                    Context(path=Path(value_path=deque([4, "DefaultValue"]))),
+                    None,
+                )
+            ],
         ),
         (
             "Valid FindInMap with valid keys and a default value",
             {"Fn::FindInMap": ["foo", "first", "second", {"DefaultValue": "default"}]},
             [
-                ("default", deque([4, "DefaultValue"]), None),
-                ("bar", deque(["Mappings", "foo", "first", "second"]), None),
+                (
+                    "default",
+                    Context(path=Path(value_path=deque([4, "DefaultValue"]))),
+                    None,
+                ),
+                (
+                    "bar",
+                    Context(
+                        path=Path(
+                            value_path=deque(["Mappings", "foo", "first", "second"])
+                        )
+                    ),
+                    None,
+                ),
             ],
         ),
         (
@@ -242,7 +266,7 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     None,
-                    deque([]),
+                    Context(),
                     ValidationError(
                         (
                             "'bar' is not one of ['foo', "
@@ -257,7 +281,13 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid FindInMap with a bad mapping and default",
             {"Fn::FindInMap": ["bar", "first", "second", {"DefaultValue": "default"}]},
-            [("default", deque([4, "DefaultValue"]), None)],
+            [
+                (
+                    "default",
+                    Context(path=Path(value_path=deque([4, "DefaultValue"]))),
+                    None,
+                )
+            ],
         ),
         (
             "Valid FindInMap with a bad mapping and aws no value",
@@ -277,7 +307,7 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     None,
-                    deque([]),
+                    Context(),
                     ValidationError(
                         ("'second' is not one of ['first'] for " "mapping 'foo'"),
                         path=deque(["Fn::FindInMap", 1]),
@@ -288,7 +318,13 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid FindInMap with a bad top key and default",
             {"Fn::FindInMap": ["foo", "second", "first", {"DefaultValue": "default"}]},
-            [("default", deque([4, "DefaultValue"]), None)],
+            [
+                (
+                    "default",
+                    Context(path=Path(value_path=deque([4, "DefaultValue"]))),
+                    None,
+                )
+            ],
         ),
         (
             "Valid FindInMap with a map name that is a Ref to pseudo param",
@@ -301,7 +337,13 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     "bar",
-                    deque(["Mappings", "accounts", "123456789012", "dev"]),
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "accounts", "123456789012", "dev"]
+                            )
+                        ),
+                    ),
                     None,
                 )
             ],
@@ -315,7 +357,13 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     "bar",
-                    deque(["Mappings", "accounts", "123456789012", "dev"]),
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "accounts", "123456789012", "dev"]
+                            )
+                        ),
+                    ),
                     None,
                 )
             ],
@@ -326,7 +374,13 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     "foo",
-                    deque(["Mappings", "accounts", "us-east-1", "bar"]),
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "accounts", "us-east-1", "bar"]
+                            )
+                        ),
+                    ),
                     None,
                 )
             ],
@@ -337,7 +391,7 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     None,
-                    deque([]),
+                    Context(),
                     ValidationError(
                         (
                             "'bar' is not a second level key "
@@ -355,7 +409,7 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     None,
-                    deque([]),
+                    Context(),
                     ValidationError(
                         (
                             "{'Ref': 'AWS::AccountId'} is not a "
@@ -377,7 +431,7 @@ def test_invalid_functions(name, instance, response):
             [
                 (
                     None,
-                    deque([]),
+                    Context(),
                     ValidationError(
                         (
                             "'third' is not one of ['second'] for "
@@ -391,7 +445,15 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid FindInMap with integer types",
             {"Fn::FindInMap": ["integers", 1, 2]},
-            [("Value", deque(["Mappings", "integers", "1", "2"]), None)],
+            [
+                (
+                    "Value",
+                    Context(
+                        path=Path(value_path=deque(["Mappings", "integers", "1", "2"]))
+                    ),
+                    None,
+                )
+            ],
         ),
         (
             (
@@ -400,8 +462,28 @@ def test_invalid_functions(name, instance, response):
             ),
             {"Fn::FindInMap": ["environments", {"Ref": "Environment"}, "foo"]},
             [
-                ("one", deque(["Mappings", "environments", "dev", "foo"]), None),
-                ("two", deque(["Mappings", "environments", "test", "foo"]), None),
+                (
+                    "one",
+                    Context(
+                        path=Path(
+                            value_path=deque(["Mappings", "environments", "dev", "foo"])
+                        ),
+                        ref_values={"Environment": "dev"},
+                    ),
+                    None,
+                ),
+                (
+                    "two",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "test", "foo"]
+                            ),
+                        ),
+                        ref_values={"Environment": "test"},
+                    ),
+                    None,
+                ),
             ],
         ),
         (
@@ -444,9 +526,42 @@ def test_invalid_functions(name, instance, response):
             ),
             {"Fn::FindInMap": ["environments", "lion", {"Ref": "Environment"}]},
             [
-                ("one", deque(["Mappings", "environments", "lion", "dev"]), None),
-                ("two", deque(["Mappings", "environments", "lion", "test"]), None),
-                ("three", deque(["Mappings", "environments", "lion", "prod"]), None),
+                (
+                    "one",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "dev"]
+                            )
+                        ),
+                        ref_values={"Environment": "dev"},
+                    ),
+                    None,
+                ),
+                (
+                    "two",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "test"]
+                            )
+                        ),
+                        ref_values={"Environment": "test"},
+                    ),
+                    None,
+                ),
+                (
+                    "three",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "prod"]
+                            )
+                        ),
+                        ref_values={"Environment": "prod"},
+                    ),
+                    None,
+                ),
             ],
         ),
         (
@@ -468,7 +583,13 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid FindInMap with a bad second key and default",
             {"Fn::FindInMap": ["foo", "first", "third", {"DefaultValue": "default"}]},
-            [("default", deque([4, "DefaultValue"]), None)],
+            [
+                (
+                    "default",
+                    Context(path=Path(value_path=deque([4, "DefaultValue"]))),
+                    None,
+                )
+            ],
         ),
         (
             "Valid FindInMap with a transform on first key",
@@ -495,16 +616,59 @@ def test_invalid_functions(name, instance, response):
             ("Valid FindInMap with a Sub with no parameters"),
             {"Fn::FindInMap": ["environments", "lion", {"Fn::Sub": "dev"}]},
             [
-                ("one", deque(["Mappings", "environments", "lion", "dev"]), None),
+                (
+                    "one",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "dev"]
+                            )
+                        )
+                    ),
+                    None,
+                ),
             ],
         ),
         (
             ("Valid FindInMap with sub to a paremter"),
             {"Fn::FindInMap": ["environments", "lion", {"Fn::Sub": "${Environment}"}]},
             [
-                ("one", deque(["Mappings", "environments", "lion", "dev"]), None),
-                ("two", deque(["Mappings", "environments", "lion", "test"]), None),
-                ("three", deque(["Mappings", "environments", "lion", "prod"]), None),
+                (
+                    "one",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "dev"]
+                            )
+                        ),
+                        ref_values={"Environment": "dev"},
+                    ),
+                    None,
+                ),
+                (
+                    "two",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "test"]
+                            )
+                        ),
+                        ref_values={"Environment": "test"},
+                    ),
+                    None,
+                ),
+                (
+                    "three",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "prod"]
+                            )
+                        ),
+                        ref_values={"Environment": "prod"},
+                    ),
+                    None,
+                ),
             ],
         ),
         (
@@ -517,9 +681,42 @@ def test_invalid_functions(name, instance, response):
                 ]
             },
             [
-                ("one", deque(["Mappings", "environments", "lion", "dev"]), None),
-                ("two", deque(["Mappings", "environments", "lion", "test"]), None),
-                ("three", deque(["Mappings", "environments", "lion", "prod"]), None),
+                (
+                    "one",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "dev"]
+                            )
+                        ),
+                        ref_values={"Environment": "dev"},
+                    ),
+                    None,
+                ),
+                (
+                    "two",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "test"]
+                            )
+                        ),
+                        ref_values={"Environment": "test"},
+                    ),
+                    None,
+                ),
+                (
+                    "three",
+                    Context(
+                        path=Path(
+                            value_path=deque(
+                                ["Mappings", "environments", "lion", "prod"]
+                            )
+                        ),
+                        ref_values={"Environment": "prod"},
+                    ),
+                    None,
+                ),
             ],
         ),
         (
@@ -536,12 +733,12 @@ def test_invalid_functions(name, instance, response):
         (
             "Valid Sub with a resolvable values",
             {"Fn::Sub": ["${a}-${b}", {"a": "foo", "b": "bar"}]},
-            [("foo-bar", deque([]), None)],
+            [("foo-bar", Context(), None)],
         ),
         (
             "Valid Sub with empty parameters",
             {"Fn::Sub": ["foo", {}]},
-            [("foo", deque([]), None)],
+            [("foo", Context(), None)],
         ),
         (
             "Valid Sub with a getatt and list",
@@ -557,9 +754,9 @@ def test_invalid_functions(name, instance, response):
             "Fn::Join uses previous values when doing resolution",
             {"Fn::Join": ["-", [{"Ref": "Environment"}, {"Ref": "Environment"}]]},
             [
-                ("dev-dev", deque(), None),
-                ("test-test", deque(), None),
-                ("prod-prod", deque(), None),
+                ("dev-dev", Context(ref_values={"Environment": "dev"}), None),
+                ("test-test", Context(ref_values={"Environment": "test"}), None),
+                ("prod-prod", Context(ref_values={"Environment": "prod"}), None),
             ],
         ),
         (
@@ -629,7 +826,7 @@ def test_valid_functions(name, instance, response):
             [
                 (
                     None,
-                    deque([]),
+                    Context(),
                     ValidationError(
                         ("{'Ref': 'MyParameter'} is not one of []"),
                         path=deque(["Fn::FindInMap", 0]),
@@ -640,7 +837,13 @@ def test_valid_functions(name, instance, response):
         (
             "Invalid FindInMap with no mappings and default value",
             {"Fn::FindInMap": ["A", "B", "C", {"DefaultValue": "default"}]},
-            [("default", deque([4, "DefaultValue"]), None)],
+            [
+                (
+                    "default",
+                    Context(path=Path(value_path=deque([4, "DefaultValue"]))),
+                    None,
+                )
+            ],
         ),
     ],
 )