We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
E1029 - False positive with IAM policy Redshift condition keys
*cfn-lint version: (`cfn-lint --version`)*
cfn-lint 0.24.1

*Description of issue.*
${redshift:DbUser} triggers:
`E1029:Found an embedded parameter outside of an "Fn::Sub"`

I'm defining a policy document similar to the one below.  cfn-lint returns a E1029 on each line where the ${redshift:DbUser} condition key is used. Source: [https://docs.aws.amazon.com/redshift/latest/mgmt/redshift-iam-access-control-identity-based.html#redshift-policy-resources.getclustercredentials-resources](url)

Sample:
```json
{
"Version": "2012-10-17",
  "Statement": [
    {
     "Sid": "GetClusterCredsStatement",
      "Effect": "Allow",
      "Action": [
        "redshift:GetClusterCredentials"
      ],
      "Resource": [
        "arn:aws:redshift:us-west-2:123456789012:dbuser:examplecluster/${redshift:DbUser}",
        "arn:aws:redshift:us-west-2:123456789012:dbname:examplecluster/testdb",
        "arn:aws:redshift:us-west-2:123456789012:dbgroup:examplecluster/common_group"
      ],
        "Condition": {
            "StringEquals": {
           "aws:userid":"AIDIODR4TAW7CSEXAMPLE:${redshift:DbUser}@yourdomain.com"
                            }
                      }
    },
    {
      "Sid": "CreateClusterUserStatement",
      "Effect": "Allow",
      "Action": [
        "redshift:CreateClusterUser"
      ],
      "Resource": [
        "arn:aws:redshift:us-west-2:123456789012:dbuser:examplecluster/${redshift:DbUser}"
      ],
      "Condition": {
        "StringEquals": {
          "aws:userid":"AIDIODR4TAW7CSEXAMPLE:${redshift:DbUser}@yourdomain.com"
        }
      }
    },
    {
      "Sid": "RedshiftJoinGroupStatement",
      "Effect": "Allow",
      "Action": [
        "redshift:JoinGroup"
      ],
      "Resource": [
        "arn:aws:redshift:us-west-2:123456789012:dbgroup:examplecluster/common_group"
      ]
    }
  ]
}
```
Resource string from actual template:
`{ "Fn::Join" : [ "", [ "arn:aws:redshift:us-west-2:", { "Ref" : "AWS::AccountId" }, ":dbuser:", { "Fn::FindInMap" : [ "Environment", { "Ref" : "EnvironmentType" }, "RSClusterName" ] }, "/${redshift:DBUser}" ] ] }`

--- 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 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
3 
4   Permission is hereby granted, free of charge, to any person obtaining a copy of this
5   software and associated documentation files (the "Software"), to deal in the Software
6   without restriction, including without limitation the rights to use, copy, modify,
7   merge, publish, distribute, sublicense, and/or sell copies of the Software, and to
8   permit persons to whom the Software is furnished to do so.
9 
10   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
11   INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
12   PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
13   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
14   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
15   SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
16 """
17 import re
18 from cfnlint.rules import CloudFormationLintRule
19 from cfnlint.rules import RuleMatch
20 
21 class SubNeeded(CloudFormationLintRule):
22     """Check if a substitution string exists without a substitution function"""
23     id = 'E1029'
24     shortdesc = 'Sub is required if a variable is used in a string'
25     description = 'If a substitution variable exists in a string but isn\'t wrapped with the Fn::Sub function the deployment will fail.'
26     source_url = 'https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html'
27     tags = ['functions', 'sub']
28 
29     # Free-form text properties to exclude from this rule
30     # content is part of AWS::CloudFormation::Init
31     excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init', 'CloudWatchAlarmDefinition', 'TopicRulePayload']
32     api_excludes = ['Uri', 'Body']
33 
34     # IAM Policy has special variables that don't require !Sub, Check for these
35     # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_variables.html
36     # https://docs.aws.amazon.com/iot/latest/developerguide/basic-policy-variables.html
37     # https://docs.aws.amazon.com/iot/latest/developerguide/thing-policy-variables.html
38     # https://docs.aws.amazon.com/transfer/latest/userguide/users.html#users-policies-scope-down
39     # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_iam-condition-keys.html
40     resource_excludes = ['${aws:CurrentTime}', '${aws:EpochTime}', '${aws:TokenIssueTime}', '${aws:principaltype}',
41                          '${aws:SecureTransport}', '${aws:SourceIp}', '${aws:UserAgent}', '${aws:userid}',
42                          '${aws:username}', '${ec2:SourceInstanceARN}',
43                          '${iot:Connection.Thing.ThingName}', '${iot:Connection.Thing.ThingTypeName}',
44                          '${iot:Connection.Thing.IsAttached}', '${iot:ClientId}', '${transfer:HomeBucket}',
45                          '${transfer:HomeDirectory}', '${transfer:HomeFolder}', '${transfer:UserName}',
46                          '${cognito-identity.amazonaws.com:aud}', '${cognito-identity.amazonaws.com:sub}', '${cognito-identity.amazonaws.com:amr}']
47 
48     def _match_values(self, searchRegex, cfnelem, path):
49         """Recursively search for values matching the searchRegex"""
50         values = []
51         if isinstance(cfnelem, dict):
52             for key in cfnelem:
53                 pathprop = path[:]
54                 pathprop.append(key)
55                 values.extend(self._match_values(searchRegex, cfnelem[key], pathprop))
56         elif isinstance(cfnelem, list):
57             for index, item in enumerate(cfnelem):
58                 pathprop = path[:]
59                 pathprop.append(index)
60                 values.extend(self._match_values(searchRegex, item, pathprop))
61         else:
62             # Leaf node
63             if isinstance(cfnelem, str) and re.match(searchRegex, cfnelem):
64                 # Get all variables as seperate paths
65                 regex = re.compile(r'(\$\{.*?\.?.*?})')
66                 for variable in re.findall(regex, cfnelem):
67                     values.append(path + [variable])
68 
69         return values
70 
71     def match_values(self, searchRegex, cfn):
72         """
73             Search for values in all parts of the templates that match the searchRegex
74         """
75         results = []
76         results.extend(self._match_values(searchRegex, cfn.template, []))
77         # Globals are removed during a transform.  They need to be checked manually
78         results.extend(self._match_values(searchRegex, cfn.template.get('Globals', {}), []))
79         return results
80 
81     def _api_exceptions(self, value):
82         """ Key value exceptions """
83         parameter_search = re.compile(r'^\$\{stageVariables\..*\}$')
84         return re.match(parameter_search, value)
85 
86     def match(self, cfn):
87         """Basic Rule Matching"""
88 
89         matches = []
90 
91         # Generic regex to match a string containing at least one ${parameter}
92         parameter_search = re.compile(r'^.*(\$\{.*\}.*(\$\{.*\}.*)*)$')
93 
94         # Get a list of paths to every leaf node string containing at least one ${parameter}
95         parameter_string_paths = self.match_values(parameter_search, cfn)
96 
97         # We want to search all of the paths to check if each one contains an 'Fn::Sub'
98         for parameter_string_path in parameter_string_paths:
99 
100             # Exxclude the special IAM variables
101             variable = parameter_string_path[-1]
102 
103             if 'Resource' in parameter_string_path:
104                 if variable in self.resource_excludes:
105                     continue
106 
107             # Exclude literals (https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html)
108             if variable.startswith('${!'):
109                 continue
110 
111             found_sub = False
112             # Does the path contain an 'Fn::Sub'?
113             for step in parameter_string_path:
114                 if step in self.api_excludes:
115                     if self._api_exceptions(parameter_string_path[-1]):
116                         found_sub = True
117                 elif step == 'Fn::Sub' or step in self.excludes:
118                     found_sub = True
119 
120             # If we didn't find an 'Fn::Sub' it means a string containing a ${parameter} may not be evaluated correctly
121             if not found_sub:
122                 # Remove the last item (the variable) to prevent multiple errors on 1 line errors
123                 path = parameter_string_path[:-1]
124                 message = 'Found an embedded parameter outside of an "Fn::Sub" at {}'.format('/'.join(map(str, path)))
125                 matches.append(RuleMatch(path, message))
126 
127         return matches
128
```
--- 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
@@ -18,6 +18,7 @@
 from cfnlint.rules import CloudFormationLintRule
 from cfnlint.rules import RuleMatch
 
+
 class SubNeeded(CloudFormationLintRule):
     """Check if a substitution string exists without a substitution function"""
     id = 'E1029'
@@ -28,7 +29,8 @@
 
     # Free-form text properties to exclude from this rule
     # content is part of AWS::CloudFormation::Init
-    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init', 'CloudWatchAlarmDefinition', 'TopicRulePayload']
+    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',
+                'CloudWatchAlarmDefinition', 'TopicRulePayload']
     api_excludes = ['Uri', 'Body']
 
     # IAM Policy has special variables that don't require !Sub, Check for these
@@ -37,13 +39,25 @@
     # https://docs.aws.amazon.com/iot/latest/developerguide/thing-policy-variables.html
     # https://docs.aws.amazon.com/transfer/latest/userguide/users.html#users-policies-scope-down
     # https://docs.aws.amazon.com/IAM/latest/UserGuide/reference_policies_iam-condition-keys.html
-    resource_excludes = ['${aws:CurrentTime}', '${aws:EpochTime}', '${aws:TokenIssueTime}', '${aws:principaltype}',
-                         '${aws:SecureTransport}', '${aws:SourceIp}', '${aws:UserAgent}', '${aws:userid}',
+    resource_excludes = ['${aws:CurrentTime}', '${aws:EpochTime}',
+                         '${aws:TokenIssueTime}', '${aws:principaltype}',
+                         '${aws:SecureTransport}', '${aws:SourceIp}',
+                         '${aws:UserAgent}', '${aws:userid}',
                          '${aws:username}', '${ec2:SourceInstanceARN}',
-                         '${iot:Connection.Thing.ThingName}', '${iot:Connection.Thing.ThingTypeName}',
-                         '${iot:Connection.Thing.IsAttached}', '${iot:ClientId}', '${transfer:HomeBucket}',
-                         '${transfer:HomeDirectory}', '${transfer:HomeFolder}', '${transfer:UserName}',
-                         '${cognito-identity.amazonaws.com:aud}', '${cognito-identity.amazonaws.com:sub}', '${cognito-identity.amazonaws.com:amr}']
+                         '${iot:Connection.Thing.ThingName}',
+                         '${iot:Connection.Thing.ThingTypeName}',
+                         '${iot:Connection.Thing.IsAttached}',
+                         '${iot:ClientId}', '${transfer:HomeBucket}',
+                         '${transfer:HomeDirectory}', '${transfer:HomeFolder}',
+                         '${transfer:UserName}', '${redshift:DbUser}',
+                         '${cognito-identity.amazonaws.com:aud}',
+                         '${cognito-identity.amazonaws.com:sub}',
+                         '${cognito-identity.amazonaws.com:amr}']
+
+    # https://docs.aws.amazon.com/redshift/latest/mgmt/redshift-iam-access-control-identity-based.html
+    condition_excludes = [
+        '${redshift:DbUser}',
+    ]
 
     def _match_values(self, searchRegex, cfnelem, path):
         """Recursively search for values matching the searchRegex"""
@@ -96,13 +110,15 @@
 
         # We want to search all of the paths to check if each one contains an 'Fn::Sub'
         for parameter_string_path in parameter_string_paths:
-
             # Exxclude the special IAM variables
             variable = parameter_string_path[-1]
 
             if 'Resource' in parameter_string_path:
                 if variable in self.resource_excludes:
                     continue
+            if 'Condition' in parameter_string_path:
+                if variable in self.condition_excludes:
+                    continue
 
             # Exclude literals (https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html)
             if variable.startswith('${!'):
@@ -121,7 +137,8 @@
             if not found_sub:
                 # Remove the last item (the variable) to prevent multiple errors on 1 line errors
                 path = parameter_string_path[:-1]
-                message = 'Found an embedded parameter outside of an "Fn::Sub" at {}'.format('/'.join(map(str, path)))
+                message = 'Found an embedded parameter outside of an "Fn::Sub" at {}'.format(
+                    '/'.join(map(str, path)))
                 matches.append(RuleMatch(path, message))
 
         return matches

{"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@@ -18,6 +18,7 @@\n from cfnlint.rules import CloudFormationLintRule\n from cfnlint.rules import RuleMatch\n \n+\n class SubNeeded(CloudFormationLintRule):\n     \"\"\"Check if a substitution string exists without a substitution function\"\"\"\n     id = 'E1029'\n@@ -28,7 +29,8 @@\n \n     # Free-form text properties to exclude from this rule\n     # content is part of AWS::CloudFormation::Init\n-    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init', 'CloudWatchAlarmDefinition', 'TopicRulePayload']\n+    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',\n+                'CloudWatchAlarmDefinition', 'TopicRulePayload']\n     api_excludes = ['Uri', 'Body']\n \n     # IAM Policy has special variables that don't require !Sub, Check for these\n@@ -37,13 +39,25 @@\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}', '${aws:TokenIssueTime}', '${aws:principaltype}',\n-                         '${aws:SecureTransport}', '${aws:SourceIp}', '${aws:UserAgent}', '${aws:userid}',\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}', '${iot:Connection.Thing.ThingTypeName}',\n-                         '${iot:Connection.Thing.IsAttached}', '${iot:ClientId}', '${transfer:HomeBucket}',\n-                         '${transfer:HomeDirectory}', '${transfer:HomeFolder}', '${transfer:UserName}',\n-                         '${cognito-identity.amazonaws.com:aud}', '${cognito-identity.amazonaws.com:sub}', '${cognito-identity.amazonaws.com:amr}']\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 _match_values(self, searchRegex, cfnelem, path):\n         \"\"\"Recursively search for values matching the searchRegex\"\"\"\n@@ -96,13 +110,15 @@\n \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-\n             # Exxclude 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 'Condition' in parameter_string_path:\n+                if variable in self.condition_excludes:\n+                    continue\n \n             # Exclude literals (https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/intrinsic-function-reference-sub.html)\n             if variable.startswith('${!'):\n@@ -121,7 +137,8 @@\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('/'.join(map(str, path)))\n+                message = 'Found an embedded parameter outside of an \"Fn::Sub\" at {}'.format(\n+                    '/'.join(map(str, path)))\n                 matches.append(RuleMatch(path, message))\n \n         return matches\n", "issue": "E1029 - False positive with IAM policy Redshift condition keys\n*cfn-lint version: (`cfn-lint --version`)*\r\ncfn-lint 0.24.1\r\n\r\n*Description of issue.*\r\n${redshift:DbUser} triggers:\r\n`E1029:Found an embedded parameter outside of an \"Fn::Sub\"`\r\n\r\nI'm defining a policy document similar to the one below.  cfn-lint returns a E1029 on each line where the ${redshift:DbUser} condition key is used. Source: [https://docs.aws.amazon.com/redshift/latest/mgmt/redshift-iam-access-control-identity-based.html#redshift-policy-resources.getclustercredentials-resources](url)\r\n\r\nSample:\r\n```json\r\n{\r\n\"Version\": \"2012-10-17\",\r\n  \"Statement\": [\r\n    {\r\n     \"Sid\": \"GetClusterCredsStatement\",\r\n      \"Effect\": \"Allow\",\r\n      \"Action\": [\r\n        \"redshift:GetClusterCredentials\"\r\n      ],\r\n      \"Resource\": [\r\n        \"arn:aws:redshift:us-west-2:123456789012:dbuser:examplecluster/${redshift:DbUser}\",\r\n        \"arn:aws:redshift:us-west-2:123456789012:dbname:examplecluster/testdb\",\r\n        \"arn:aws:redshift:us-west-2:123456789012:dbgroup:examplecluster/common_group\"\r\n      ],\r\n        \"Condition\": {\r\n            \"StringEquals\": {\r\n           \"aws:userid\":\"AIDIODR4TAW7CSEXAMPLE:${redshift:DbUser}@yourdomain.com\"\r\n                            }\r\n                      }\r\n    },\r\n    {\r\n      \"Sid\": \"CreateClusterUserStatement\",\r\n      \"Effect\": \"Allow\",\r\n      \"Action\": [\r\n        \"redshift:CreateClusterUser\"\r\n      ],\r\n      \"Resource\": [\r\n        \"arn:aws:redshift:us-west-2:123456789012:dbuser:examplecluster/${redshift:DbUser}\"\r\n      ],\r\n      \"Condition\": {\r\n        \"StringEquals\": {\r\n          \"aws:userid\":\"AIDIODR4TAW7CSEXAMPLE:${redshift:DbUser}@yourdomain.com\"\r\n        }\r\n      }\r\n    },\r\n    {\r\n      \"Sid\": \"RedshiftJoinGroupStatement\",\r\n      \"Effect\": \"Allow\",\r\n      \"Action\": [\r\n        \"redshift:JoinGroup\"\r\n      ],\r\n      \"Resource\": [\r\n        \"arn:aws:redshift:us-west-2:123456789012:dbgroup:examplecluster/common_group\"\r\n      ]\r\n    }\r\n  ]\r\n}\r\n```\r\nResource string from actual template:\r\n`{ \"Fn::Join\" : [ \"\", [ \"arn:aws:redshift:us-west-2:\", { \"Ref\" : \"AWS::AccountId\" }, \":dbuser:\", { \"Fn::FindInMap\" : [ \"Environment\", { \"Ref\" : \"EnvironmentType\" }, \"RSClusterName\" ] }, \"/${redshift:DBUser}\" ] ] }`\n", "before_files": [{"content": "\"\"\"\n  Copyright 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.\n\n  Permission is hereby granted, free of charge, to any person obtaining a copy of this\n  software and associated documentation files (the \"Software\"), to deal in the Software\n  without restriction, including without limitation the rights to use, copy, modify,\n  merge, publish, distribute, sublicense, and/or sell copies of the Software, and to\n  permit persons to whom the Software is furnished to do so.\n\n  THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,\n  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A\n  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT\n  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION\n  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE\n  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\n\"\"\"\nimport re\nfrom cfnlint.rules import CloudFormationLintRule\nfrom cfnlint.rules import RuleMatch\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    # content is part of AWS::CloudFormation::Init\n    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init', 'CloudWatchAlarmDefinition', 'TopicRulePayload']\n    api_excludes = ['Uri', 'Body']\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}', '${aws:TokenIssueTime}', '${aws:principaltype}',\n                         '${aws:SecureTransport}', '${aws:SourceIp}', '${aws:UserAgent}', '${aws:userid}',\n                         '${aws:username}', '${ec2:SourceInstanceARN}',\n                         '${iot:Connection.Thing.ThingName}', '${iot:Connection.Thing.ThingTypeName}',\n                         '${iot:Connection.Thing.IsAttached}', '${iot:ClientId}', '${transfer:HomeBucket}',\n                         '${transfer:HomeDirectory}', '${transfer:HomeFolder}', '${transfer:UserName}',\n                         '${cognito-identity.amazonaws.com:aud}', '${cognito-identity.amazonaws.com:sub}', '${cognito-identity.amazonaws.com:amr}']\n\n    def _match_values(self, searchRegex, 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(searchRegex, 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(searchRegex, item, pathprop))\n        else:\n            # Leaf node\n            if isinstance(cfnelem, str) and re.match(searchRegex, cfnelem):\n                # Get all variables as seperate paths\n                regex = re.compile(r'(\\$\\{.*?\\.?.*?})')\n                for variable in re.findall(regex, cfnelem):\n                    values.append(path + [variable])\n\n        return values\n\n    def match_values(self, searchRegex, 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(searchRegex, cfn.template, []))\n        # Globals are removed during a transform.  They need to be checked manually\n        results.extend(self._match_values(searchRegex, 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 match(self, cfn):\n        \"\"\"Basic Rule Matching\"\"\"\n\n        matches = []\n\n        # Generic regex to match a string containing at least one ${parameter}\n        parameter_search = re.compile(r'^.*(\\$\\{.*\\}.*(\\$\\{.*\\}.*)*)$')\n\n        # Get a list of paths to every leaf node string containing at least one ${parameter}\n        parameter_string_paths = self.match_values(parameter_search, cfn)\n\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\n            # Exxclude 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\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('/'.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": "\"\"\"\n  Copyright 2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.\n\n  Permission is hereby granted, free of charge, to any person obtaining a copy of this\n  software and associated documentation files (the \"Software\"), to deal in the Software\n  without restriction, including without limitation the rights to use, copy, modify,\n  merge, publish, distribute, sublicense, and/or sell copies of the Software, and to\n  permit persons to whom the Software is furnished to do so.\n\n  THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,\n  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A\n  PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT\n  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION\n  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE\n  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\n\"\"\"\nimport re\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    # content is part of AWS::CloudFormation::Init\n    excludes = ['UserData', 'ZipFile', 'Condition', 'AWS::CloudFormation::Init',\n                'CloudWatchAlarmDefinition', 'TopicRulePayload']\n    api_excludes = ['Uri', 'Body']\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 _match_values(self, searchRegex, 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(searchRegex, 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(searchRegex, item, pathprop))\n        else:\n            # Leaf node\n            if isinstance(cfnelem, str) and re.match(searchRegex, cfnelem):\n                # Get all variables as seperate paths\n                regex = re.compile(r'(\\$\\{.*?\\.?.*?})')\n                for variable in re.findall(regex, cfnelem):\n                    values.append(path + [variable])\n\n        return values\n\n    def match_values(self, searchRegex, 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(searchRegex, cfn.template, []))\n        # Globals are removed during a transform.  They need to be checked manually\n        results.extend(self._match_values(searchRegex, 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 match(self, cfn):\n        \"\"\"Basic Rule Matching\"\"\"\n\n        matches = []\n\n        # Generic regex to match a string containing at least one ${parameter}\n        parameter_search = re.compile(r'^.*(\\$\\{.*\\}.*(\\$\\{.*\\}.*)*)$')\n\n        # Get a list of paths to every leaf node string containing at least one ${parameter}\n        parameter_string_paths = self.match_values(parameter_search, cfn)\n\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            # Exxclude 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 'Condition' in parameter_string_path:\n                if variable in self.condition_excludes:\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                    '/'.join(map(str, path)))\n                matches.append(RuleMatch(path, message))\n\n        return matches\n", "path": "src/cfnlint/rules/functions/SubNeeded.py"}]}