We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Ignoring ${} parameters from Fn::Sub checks
*cfn-lint version: 0.44.1*

*Description of issue.* 
I using the `AWS::ApiGatewayV2::Api` clause and referencing the [`RouteSelectionExpression`](https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-resource-apigatewayv2-api.html#cfn-apigatewayv2-api-routeselectionexpression) property which takes values like `${request.body.action}`. Cloudformation accepts `RouteSelectionExpression: "${request.body.action}"` as perfectly valid but cfn-lint is triggering `E1029: Found an embedded parameter "${request.body.action}" outside of an "Fn::Sub" at Resources/agwApi/Properties/RouteSelectionExpression`. I'm not sure if there's a way to escape the ${} characters which makes cfn-lint happy as well as CFN.


Cfn-lint uses the [CloudFormation Resource Specifications](https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/cfn-resource-specification.html) as the base to do validation. These files are included as part of the application version. Please update to the latest version of `cfn-lint` or update the spec files manually (`cfn-lint -u`)


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `src/cfnlint/rules/functions/SubNeeded.py`
Content:
```
1 """
2 Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
3 SPDX-License-Identifier: MIT-0
4 """
5 from functools import reduce  # pylint: disable=redefined-builtin
6 import re
7 import six
8 from cfnlint.rules import CloudFormationLintRule
9 from cfnlint.rules import RuleMatch
10 
11 
12 class SubNeeded(CloudFormationLintRule):
13     """Check if a substitution string exists without a substitution function"""
14     id = 'E1029'
15     shortdesc = 'Sub is required if a variable is used in a string'
16     description = 'If a substitution variable exists in a string but isn\'t wrapped with the Fn::Sub function the deployment will fail.'
17     source_url = 'https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html'
18     tags = ['functions', 'sub']
19 
20     # Free-form text properties to exclude from this rule
21     excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',
22                 'CloudWatchAlarmDefinition', 'TopicRulePayload', 'BuildSpec',
23                 'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate']
24     api_excludes = ['Uri', 'Body', 'ConnectionId']
25 
26 
27     # IAM Policy has special variables that don't require !Sub, Check for these
28     # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_variables.html
29     # https://docs.aws.amazon.com/iot/latest/developerguide/basic-policy-variables.html
30     # https://docs.aws.amazon.com/iot/latest/developerguide/thing-policy-variables.html
31     # https://docs.aws.amazon.com/transfer/latest/userguide/users.html#users-policies-scope-down
32     # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_iam-condition-keys.html
33     resource_excludes = ['${aws:CurrentTime}', '${aws:EpochTime}',
34                          '${aws:TokenIssueTime}', '${aws:principaltype}',
35                          '${aws:SecureTransport}', '${aws:SourceIp}',
36                          '${aws:UserAgent}', '${aws:userid}',
37                          '${aws:username}', '${ec2:SourceInstanceARN}',
38                          '${iot:Connection.Thing.ThingName}',
39                          '${iot:Connection.Thing.ThingTypeName}',
40                          '${iot:Connection.Thing.IsAttached}',
41                          '${iot:ClientId}', '${transfer:HomeBucket}',
42                          '${transfer:HomeDirectory}', '${transfer:HomeFolder}',
43                          '${transfer:UserName}', '${redshift:DbUser}',
44                          '${cognito-identity.amazonaws.com:aud}',
45                          '${cognito-identity.amazonaws.com:sub}',
46                          '${cognito-identity.amazonaws.com:amr}']
47 
48     # https://docs.aws.amazon.com/redshift/latest/mgmt/redshift-iam-access-control-identity-based.html
49     condition_excludes = [
50         '${redshift:DbUser}',
51     ]
52 
53     def __init__(self):
54         """Init"""
55         super(SubNeeded, self).__init__()
56         self.config_definition = {
57             'custom_excludes': {
58                 'default': '',
59                 'type': 'string'
60             }
61         }
62         self.configure()
63         self.subParameterRegex = re.compile(r'(\$\{[A-Za-z0-9_:\.]+\})')
64 
65     def _match_values(self, cfnelem, path):
66         """Recursively search for values matching the searchRegex"""
67         values = []
68         if isinstance(cfnelem, dict):
69             for key in cfnelem:
70                 pathprop = path[:]
71                 pathprop.append(key)
72                 values.extend(self._match_values(cfnelem[key], pathprop))
73         elif isinstance(cfnelem, list):
74             for index, item in enumerate(cfnelem):
75                 pathprop = path[:]
76                 pathprop.append(index)
77                 values.extend(self._match_values(item, pathprop))
78         else:
79             # Leaf node
80             if isinstance(cfnelem, six.string_types):  # and re.match(searchRegex, cfnelem):
81                 for variable in re.findall(self.subParameterRegex, cfnelem):
82                     values.append(path + [variable])
83 
84         return values
85 
86     def match_values(self, cfn):
87         """
88             Search for values in all parts of the templates that match the searchRegex
89         """
90         results = []
91         results.extend(self._match_values(cfn.template, []))
92         # Globals are removed during a transform.  They need to be checked manually
93         results.extend(self._match_values(cfn.template.get('Globals', {}), []))
94         return results
95 
96     def _api_exceptions(self, value):
97         """ Key value exceptions """
98         parameter_search = re.compile(r'^\$\{stageVariables\..*\}$')
99         return re.match(parameter_search, value)
100 
101     def _variable_custom_excluded(self, value):
102         """ User-defined exceptions for variables, anywhere in the file """
103         custom_excludes = self.config['custom_excludes']
104         if custom_excludes:
105             custom_search = re.compile(custom_excludes)
106             return re.match(custom_search, value)
107         return False
108 
109     def match(self, cfn):
110         matches = []
111 
112         # Get a list of paths to every leaf node string containing at least one ${parameter}
113         parameter_string_paths = self.match_values(cfn)
114         # We want to search all of the paths to check if each one contains an 'Fn::Sub'
115         for parameter_string_path in parameter_string_paths:
116             if parameter_string_path[0] in ['Parameters']:
117                 continue
118             # Exclude the special IAM variables
119             variable = parameter_string_path[-1]
120 
121             if 'Resource' in parameter_string_path:
122                 if variable in self.resource_excludes:
123                     continue
124             if 'NotResource' in parameter_string_path:
125                 if variable in self.resource_excludes:
126                     continue
127             if 'Condition' in parameter_string_path:
128                 if variable in self.condition_excludes:
129                     continue
130 
131             # Step Function State Machine has a Definition Substitution that allows usage of special variables outside of a !Sub
132             # https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-properties-stepfunctions-statemachine-definitionsubstitutions.html
133 
134             if 'DefinitionString' in parameter_string_path:
135                 modified_parameter_string_path = parameter_string_path
136                 index = parameter_string_path.index('DefinitionString')
137                 modified_parameter_string_path[index] = 'DefinitionSubstitutions'
138                 modified_parameter_string_path = modified_parameter_string_path[:index+1]
139                 modified_parameter_string_path.append(variable[2:-1])
140                 if reduce(lambda c, k: c.get(k, {}), modified_parameter_string_path, cfn.template):
141                     continue
142 
143             # Exclude variables that match custom exclude filters, if configured
144             # (for third-party tools that pre-process templates before uploading them to AWS)
145             if self._variable_custom_excluded(variable):
146                 continue
147 
148             # Exclude literals (https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html)
149             if variable.startswith('${!'):
150                 continue
151 
152             found_sub = False
153             # Does the path contain an 'Fn::Sub'?
154             for step in parameter_string_path:
155                 if step in self.api_excludes:
156                     if self._api_exceptions(parameter_string_path[-1]):
157                         found_sub = True
158                 elif step == 'Fn::Sub' or step in self.excludes:
159                     found_sub = True
160 
161             # If we didn't find an 'Fn::Sub' it means a string containing a ${parameter} may not be evaluated correctly
162             if not found_sub:
163                 # Remove the last item (the variable) to prevent multiple errors on 1 line errors
164                 path = parameter_string_path[:-1]
165                 message = 'Found an embedded parameter "{}" outside of an "Fn::Sub" at {}'.format(
166                     variable, '/'.join(map(str, path)))
167                 matches.append(RuleMatch(path, message))
168 
169         return matches
170
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/src/cfnlint/rules/functions/SubNeeded.py b/src/cfnlint/rules/functions/SubNeeded.py
--- a/src/cfnlint/rules/functions/SubNeeded.py
+++ b/src/cfnlint/rules/functions/SubNeeded.py
@@ -20,7 +20,8 @@
     # Free-form text properties to exclude from this rule
     excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',
                 'CloudWatchAlarmDefinition', 'TopicRulePayload', 'BuildSpec',
-                'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate']
+                'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate',
+                'RouteSelectionExpression']
     api_excludes = ['Uri', 'Body', 'ConnectionId']

{"golden_diff": "diff --git a/src/cfnlint/rules/functions/SubNeeded.py b/src/cfnlint/rules/functions/SubNeeded.py\n--- a/src/cfnlint/rules/functions/SubNeeded.py\n+++ b/src/cfnlint/rules/functions/SubNeeded.py\n@@ -20,7 +20,8 @@\n     # Free-form text properties to exclude from this rule\n     excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',\n                 'CloudWatchAlarmDefinition', 'TopicRulePayload', 'BuildSpec',\n-                'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate']\n+                'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate',\n+                'RouteSelectionExpression']\n     api_excludes = ['Uri', 'Body', 'ConnectionId']\n", "issue": "Ignoring ${} parameters from Fn::Sub checks\n*cfn-lint version: 0.44.1*\r\n\r\n*Description of issue.* \r\nI using the `AWS::ApiGatewayV2::Api` clause and referencing the [`RouteSelectionExpression`](https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-resource-apigatewayv2-api.html#cfn-apigatewayv2-api-routeselectionexpression) property which takes values like `${request.body.action}`. Cloudformation accepts `RouteSelectionExpression: \"${request.body.action}\"` as perfectly valid but cfn-lint is triggering `E1029: Found an embedded parameter \"${request.body.action}\" outside of an \"Fn::Sub\" at Resources/agwApi/Properties/RouteSelectionExpression`. I'm not sure if there's a way to escape the ${} characters which makes cfn-lint happy as well as CFN.\r\n\r\n\r\nCfn-lint uses the [CloudFormation Resource Specifications](https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/cfn-resource-specification.html) as the base to do validation. These files are included as part of the application version. Please update to the latest version of `cfn-lint` or update the spec files manually (`cfn-lint -u`)\r\n\n", "before_files": [{"content": "\"\"\"\nCopyright Amazon.com, Inc. or its affiliates. All Rights Reserved.\nSPDX-License-Identifier: MIT-0\n\"\"\"\nfrom functools import reduce  # pylint: disable=redefined-builtin\nimport re\nimport six\nfrom cfnlint.rules import CloudFormationLintRule\nfrom cfnlint.rules import RuleMatch\n\n\nclass SubNeeded(CloudFormationLintRule):\n    \"\"\"Check if a substitution string exists without a substitution function\"\"\"\n    id = 'E1029'\n    shortdesc = 'Sub is required if a variable is used in a string'\n    description = 'If a substitution variable exists in a string but isn\\'t wrapped with the Fn::Sub function the deployment will fail.'\n    source_url = 'https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html'\n    tags = ['functions', 'sub']\n\n    # Free-form text properties to exclude from this rule\n    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',\n                'CloudWatchAlarmDefinition', 'TopicRulePayload', 'BuildSpec',\n                'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate']\n    api_excludes = ['Uri', 'Body', 'ConnectionId']\n\n\n    # IAM Policy has special variables that don't require !Sub, Check for these\n    # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_variables.html\n    # https://docs.aws.amazon.com/iot/latest/developerguide/basic-policy-variables.html\n    # https://docs.aws.amazon.com/iot/latest/developerguide/thing-policy-variables.html\n    # https://docs.aws.amazon.com/transfer/latest/userguide/users.html#users-policies-scope-down\n    # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_iam-condition-keys.html\n    resource_excludes = ['${aws:CurrentTime}', '${aws:EpochTime}',\n                         '${aws:TokenIssueTime}', '${aws:principaltype}',\n                         '${aws:SecureTransport}', '${aws:SourceIp}',\n                         '${aws:UserAgent}', '${aws:userid}',\n                         '${aws:username}', '${ec2:SourceInstanceARN}',\n                         '${iot:Connection.Thing.ThingName}',\n                         '${iot:Connection.Thing.ThingTypeName}',\n                         '${iot:Connection.Thing.IsAttached}',\n                         '${iot:ClientId}', '${transfer:HomeBucket}',\n                         '${transfer:HomeDirectory}', '${transfer:HomeFolder}',\n                         '${transfer:UserName}', '${redshift:DbUser}',\n                         '${cognito-identity.amazonaws.com:aud}',\n                         '${cognito-identity.amazonaws.com:sub}',\n                         '${cognito-identity.amazonaws.com:amr}']\n\n    # https://docs.aws.amazon.com/redshift/latest/mgmt/redshift-iam-access-control-identity-based.html\n    condition_excludes = [\n        '${redshift:DbUser}',\n    ]\n\n    def __init__(self):\n        \"\"\"Init\"\"\"\n        super(SubNeeded, self).__init__()\n        self.config_definition = {\n            'custom_excludes': {\n                'default': '',\n                'type': 'string'\n            }\n        }\n        self.configure()\n        self.subParameterRegex = re.compile(r'(\\$\\{[A-Za-z0-9_:\\.]+\\})')\n\n    def _match_values(self, cfnelem, path):\n        \"\"\"Recursively search for values matching the searchRegex\"\"\"\n        values = []\n        if isinstance(cfnelem, dict):\n            for key in cfnelem:\n                pathprop = path[:]\n                pathprop.append(key)\n                values.extend(self._match_values(cfnelem[key], pathprop))\n        elif isinstance(cfnelem, list):\n            for index, item in enumerate(cfnelem):\n                pathprop = path[:]\n                pathprop.append(index)\n                values.extend(self._match_values(item, pathprop))\n        else:\n            # Leaf node\n            if isinstance(cfnelem, six.string_types):  # and re.match(searchRegex, cfnelem):\n                for variable in re.findall(self.subParameterRegex, cfnelem):\n                    values.append(path + [variable])\n\n        return values\n\n    def match_values(self, cfn):\n        \"\"\"\n            Search for values in all parts of the templates that match the searchRegex\n        \"\"\"\n        results = []\n        results.extend(self._match_values(cfn.template, []))\n        # Globals are removed during a transform.  They need to be checked manually\n        results.extend(self._match_values(cfn.template.get('Globals', {}), []))\n        return results\n\n    def _api_exceptions(self, value):\n        \"\"\" Key value exceptions \"\"\"\n        parameter_search = re.compile(r'^\\$\\{stageVariables\\..*\\}$')\n        return re.match(parameter_search, value)\n\n    def _variable_custom_excluded(self, value):\n        \"\"\" User-defined exceptions for variables, anywhere in the file \"\"\"\n        custom_excludes = self.config['custom_excludes']\n        if custom_excludes:\n            custom_search = re.compile(custom_excludes)\n            return re.match(custom_search, value)\n        return False\n\n    def match(self, cfn):\n        matches = []\n\n        # Get a list of paths to every leaf node string containing at least one ${parameter}\n        parameter_string_paths = self.match_values(cfn)\n        # We want to search all of the paths to check if each one contains an 'Fn::Sub'\n        for parameter_string_path in parameter_string_paths:\n            if parameter_string_path[0] in ['Parameters']:\n                continue\n            # Exclude the special IAM variables\n            variable = parameter_string_path[-1]\n\n            if 'Resource' in parameter_string_path:\n                if variable in self.resource_excludes:\n                    continue\n            if 'NotResource' in parameter_string_path:\n                if variable in self.resource_excludes:\n                    continue\n            if 'Condition' in parameter_string_path:\n                if variable in self.condition_excludes:\n                    continue\n\n            # Step Function State Machine has a Definition Substitution that allows usage of special variables outside of a !Sub\n            # https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-properties-stepfunctions-statemachine-definitionsubstitutions.html\n\n            if 'DefinitionString' in parameter_string_path:\n                modified_parameter_string_path = parameter_string_path\n                index = parameter_string_path.index('DefinitionString')\n                modified_parameter_string_path[index] = 'DefinitionSubstitutions'\n                modified_parameter_string_path = modified_parameter_string_path[:index+1]\n                modified_parameter_string_path.append(variable[2:-1])\n                if reduce(lambda c, k: c.get(k, {}), modified_parameter_string_path, cfn.template):\n                    continue\n\n            # Exclude variables that match custom exclude filters, if configured\n            # (for third-party tools that pre-process templates before uploading them to AWS)\n            if self._variable_custom_excluded(variable):\n                continue\n\n            # Exclude literals (https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html)\n            if variable.startswith('${!'):\n                continue\n\n            found_sub = False\n            # Does the path contain an 'Fn::Sub'?\n            for step in parameter_string_path:\n                if step in self.api_excludes:\n                    if self._api_exceptions(parameter_string_path[-1]):\n                        found_sub = True\n                elif step == 'Fn::Sub' or step in self.excludes:\n                    found_sub = True\n\n            # If we didn't find an 'Fn::Sub' it means a string containing a ${parameter} may not be evaluated correctly\n            if not found_sub:\n                # Remove the last item (the variable) to prevent multiple errors on 1 line errors\n                path = parameter_string_path[:-1]\n                message = 'Found an embedded parameter \"{}\" outside of an \"Fn::Sub\" at {}'.format(\n                    variable, '/'.join(map(str, path)))\n                matches.append(RuleMatch(path, message))\n\n        return matches\n", "path": "src/cfnlint/rules/functions/SubNeeded.py"}], "after_files": [{"content": "\"\"\"\nCopyright Amazon.com, Inc. or its affiliates. All Rights Reserved.\nSPDX-License-Identifier: MIT-0\n\"\"\"\nfrom functools import reduce  # pylint: disable=redefined-builtin\nimport re\nimport six\nfrom cfnlint.rules import CloudFormationLintRule\nfrom cfnlint.rules import RuleMatch\n\n\nclass SubNeeded(CloudFormationLintRule):\n    \"\"\"Check if a substitution string exists without a substitution function\"\"\"\n    id = 'E1029'\n    shortdesc = 'Sub is required if a variable is used in a string'\n    description = 'If a substitution variable exists in a string but isn\\'t wrapped with the Fn::Sub function the deployment will fail.'\n    source_url = 'https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html'\n    tags = ['functions', 'sub']\n\n    # Free-form text properties to exclude from this rule\n    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',\n                'CloudWatchAlarmDefinition', 'TopicRulePayload', 'BuildSpec',\n                'RequestMappingTemplate', 'LogFormat', 'TemplateBody', 'ResponseMappingTemplate',\n                'RouteSelectionExpression']\n    api_excludes = ['Uri', 'Body', 'ConnectionId']\n\n\n    # IAM Policy has special variables that don't require !Sub, Check for these\n    # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_variables.html\n    # https://docs.aws.amazon.com/iot/latest/developerguide/basic-policy-variables.html\n    # https://docs.aws.amazon.com/iot/latest/developerguide/thing-policy-variables.html\n    # https://docs.aws.amazon.com/transfer/latest/userguide/users.html#users-policies-scope-down\n    # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_iam-condition-keys.html\n    resource_excludes = ['${aws:CurrentTime}', '${aws:EpochTime}',\n                         '${aws:TokenIssueTime}', '${aws:principaltype}',\n                         '${aws:SecureTransport}', '${aws:SourceIp}',\n                         '${aws:UserAgent}', '${aws:userid}',\n                         '${aws:username}', '${ec2:SourceInstanceARN}',\n                         '${iot:Connection.Thing.ThingName}',\n                         '${iot:Connection.Thing.ThingTypeName}',\n                         '${iot:Connection.Thing.IsAttached}',\n                         '${iot:ClientId}', '${transfer:HomeBucket}',\n                         '${transfer:HomeDirectory}', '${transfer:HomeFolder}',\n                         '${transfer:UserName}', '${redshift:DbUser}',\n                         '${cognito-identity.amazonaws.com:aud}',\n                         '${cognito-identity.amazonaws.com:sub}',\n                         '${cognito-identity.amazonaws.com:amr}']\n\n    # https://docs.aws.amazon.com/redshift/latest/mgmt/redshift-iam-access-control-identity-based.html\n    condition_excludes = [\n        '${redshift:DbUser}',\n    ]\n\n    def __init__(self):\n        \"\"\"Init\"\"\"\n        super(SubNeeded, self).__init__()\n        self.config_definition = {\n            'custom_excludes': {\n                'default': '',\n                'type': 'string'\n            }\n        }\n        self.configure()\n        self.subParameterRegex = re.compile(r'(\\$\\{[A-Za-z0-9_:\\.]+\\})')\n\n    def _match_values(self, cfnelem, path):\n        \"\"\"Recursively search for values matching the searchRegex\"\"\"\n        values = []\n        if isinstance(cfnelem, dict):\n            for key in cfnelem:\n                pathprop = path[:]\n                pathprop.append(key)\n                values.extend(self._match_values(cfnelem[key], pathprop))\n        elif isinstance(cfnelem, list):\n            for index, item in enumerate(cfnelem):\n                pathprop = path[:]\n                pathprop.append(index)\n                values.extend(self._match_values(item, pathprop))\n        else:\n            # Leaf node\n            if isinstance(cfnelem, six.string_types):  # and re.match(searchRegex, cfnelem):\n                for variable in re.findall(self.subParameterRegex, cfnelem):\n                    values.append(path + [variable])\n\n        return values\n\n    def match_values(self, cfn):\n        \"\"\"\n            Search for values in all parts of the templates that match the searchRegex\n        \"\"\"\n        results = []\n        results.extend(self._match_values(cfn.template, []))\n        # Globals are removed during a transform.  They need to be checked manually\n        results.extend(self._match_values(cfn.template.get('Globals', {}), []))\n        return results\n\n    def _api_exceptions(self, value):\n        \"\"\" Key value exceptions \"\"\"\n        parameter_search = re.compile(r'^\\$\\{stageVariables\\..*\\}$')\n        return re.match(parameter_search, value)\n\n    def _variable_custom_excluded(self, value):\n        \"\"\" User-defined exceptions for variables, anywhere in the file \"\"\"\n        custom_excludes = self.config['custom_excludes']\n        if custom_excludes:\n            custom_search = re.compile(custom_excludes)\n            return re.match(custom_search, value)\n        return False\n\n    def match(self, cfn):\n        matches = []\n\n        # Get a list of paths to every leaf node string containing at least one ${parameter}\n        parameter_string_paths = self.match_values(cfn)\n        # We want to search all of the paths to check if each one contains an 'Fn::Sub'\n        for parameter_string_path in parameter_string_paths:\n            if parameter_string_path[0] in ['Parameters']:\n                continue\n            # Exclude the special IAM variables\n            variable = parameter_string_path[-1]\n\n            if 'Resource' in parameter_string_path:\n                if variable in self.resource_excludes:\n                    continue\n            if 'NotResource' in parameter_string_path:\n                if variable in self.resource_excludes:\n                    continue\n            if 'Condition' in parameter_string_path:\n                if variable in self.condition_excludes:\n                    continue\n\n            # Step Function State Machine has a Definition Substitution that allows usage of special variables outside of a !Sub\n            # https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-properties-stepfunctions-statemachine-definitionsubstitutions.html\n\n            if 'DefinitionString' in parameter_string_path:\n                modified_parameter_string_path = parameter_string_path\n                index = parameter_string_path.index('DefinitionString')\n                modified_parameter_string_path[index] = 'DefinitionSubstitutions'\n                modified_parameter_string_path = modified_parameter_string_path[:index+1]\n                modified_parameter_string_path.append(variable[2:-1])\n                if reduce(lambda c, k: c.get(k, {}), modified_parameter_string_path, cfn.template):\n                    continue\n\n            # Exclude variables that match custom exclude filters, if configured\n            # (for third-party tools that pre-process templates before uploading them to AWS)\n            if self._variable_custom_excluded(variable):\n                continue\n\n            # Exclude literals (https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html)\n            if variable.startswith('${!'):\n                continue\n\n            found_sub = False\n            # Does the path contain an 'Fn::Sub'?\n            for step in parameter_string_path:\n                if step in self.api_excludes:\n                    if self._api_exceptions(parameter_string_path[-1]):\n                        found_sub = True\n                elif step == 'Fn::Sub' or step in self.excludes:\n                    found_sub = True\n\n            # If we didn't find an 'Fn::Sub' it means a string containing a ${parameter} may not be evaluated correctly\n            if not found_sub:\n                # Remove the last item (the variable) to prevent multiple errors on 1 line errors\n                path = parameter_string_path[:-1]\n                message = 'Found an embedded parameter \"{}\" outside of an \"Fn::Sub\" at {}'.format(\n                    variable, '/'.join(map(str, path)))\n                matches.append(RuleMatch(path, message))\n\n        return matches\n", "path": "src/cfnlint/rules/functions/SubNeeded.py"}]}