prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  ${aws:username} now fails
  *cfn-lint version: 0.8
  
  E1029 Found an embedded parameter outside of an "Fn::Sub" at Resources/ForceMFAPolicy/Properties/PolicyDocument/Statement/3/Resource/0/arn:aws:iam::*:mfa/${aws:username}
  
  It looks like the IAM variables are now being detected as embedded parameters in cfn-lint.
  
              Effect: "Allow"
              Action:
                - "iam:UploadSSHPublicKey"
              Resource: "arn:aws:iam::*:user/${aws:username}"
  
  </issue>
  <code>
  [start of src/cfnlint/rules/functions/SubNeeded.py]
  1 """
  2   Copyright 2018 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 import CloudFormationLintRule
  19 from cfnlint 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     excludes = ['UserData', 'ZipFile']
  31 
  32     def _match_values(self, searchRegex, cfnelem, path):
  33         """Recursively search for values matching the searchRegex"""
  34         values = []
  35         if isinstance(cfnelem, dict):
  36             for key in cfnelem:
  37                 pathprop = path[:]
  38                 pathprop.append(key)
  39                 values.extend(self._match_values(searchRegex, cfnelem[key], pathprop))
  40         elif isinstance(cfnelem, list):
  41             for index, item in enumerate(cfnelem):
  42                 pathprop = path[:]
  43                 pathprop.append(index)
  44                 values.extend(self._match_values(searchRegex, item, pathprop))
  45         else:
  46             # Leaf node
  47             if isinstance(cfnelem, str) and re.match(searchRegex, cfnelem):
  48                 values.append(path + [cfnelem])
  49 
  50         return values
  51 
  52     def match_values(self, searchRegex, cfn):
  53         """
  54             Search for values in all parts of the templates that match the searchRegex
  55         """
  56         results = []
  57         results.extend(self._match_values(searchRegex, cfn.template, []))
  58         # Globals are removed during a transform.  They need to be checked manually
  59         results.extend(self._match_values(searchRegex, cfn.template.get('Globals', {}), []))
  60         return results
  61 
  62     def match(self, cfn):
  63         """Basic Rule Matching"""
  64 
  65         matches = []
  66 
  67         # Generic regex to match a string containing at least one ${parameter}
  68         parameter_search = re.compile(r'^(.*\$\{.*\}.*(\$\{.*\}.*)*)$')
  69 
  70         # Get a list of paths to every leaf node string containing at least one ${parameter}
  71         parameter_string_paths = self.match_values(parameter_search, cfn)
  72 
  73         # We want to search all of the paths to check if each one contains an 'Fn::Sub'
  74         for parameter_string_path in parameter_string_paths:
  75             found_sub = False
  76 
  77             # Does the path contain an 'Fn::Sub'?
  78             for step in parameter_string_path:
  79                 if step == 'Fn::Sub' or step in self.excludes:
  80                     found_sub = True
  81 
  82             # If we didn't find an 'Fn::Sub' it means a string containing a ${parameter} may not be evaluated correctly
  83             if not found_sub:
  84                 message = 'Found an embedded parameter outside of an "Fn::Sub" at {}'.format('/'.join(map(str, parameter_string_path)))
  85                 matches.append(RuleMatch(parameter_string_path, message))
  86 
  87         return matches
  88
  [end of src/cfnlint/rules/functions/SubNeeded.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: 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
  @@ -27,7 +27,7 @@
       tags = ['functions', 'sub']
   
       # Free-form text properties to exclude from this rule
  -    excludes = ['UserData', 'ZipFile']
  +    excludes = ['UserData', 'ZipFile', 'Resource', 'Condition']
   
       def _match_values(self, searchRegex, cfnelem, path):
           """Recursively search for values matching the searchRegex"""
  
verification_info: {"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@@ -27,7 +27,7 @@\n     tags = ['functions', 'sub']\n \n     # Free-form text properties to exclude from this rule\n-    excludes = ['UserData', 'ZipFile']\n+    excludes = ['UserData', 'ZipFile', 'Resource', 'Condition']\n \n     def _match_values(self, searchRegex, cfnelem, path):\n         \"\"\"Recursively search for values matching the searchRegex\"\"\"\n", "issue": "${aws:username} now fails\n*cfn-lint version: 0.8\r\n\r\nE1029 Found an embedded parameter outside of an \"Fn::Sub\" at Resources/ForceMFAPolicy/Properties/PolicyDocument/Statement/3/Resource/0/arn:aws:iam::*:mfa/${aws:username}\r\n\r\nIt looks like the IAM variables are now being detected as embedded parameters in cfn-lint.\r\n\r\n            Effect: \"Allow\"\r\n            Action:\r\n              - \"iam:UploadSSHPublicKey\"\r\n            Resource: \"arn:aws:iam::*:user/${aws:username}\"\n", "before_files": [{"content": "\"\"\"\n  Copyright 2018 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 import CloudFormationLintRule\nfrom cfnlint 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    excludes = ['UserData', 'ZipFile']\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                values.append(path + [cfnelem])\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 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            found_sub = False\n\n            # Does the path contain an 'Fn::Sub'?\n            for step in parameter_string_path:\n                if 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                message = 'Found an embedded parameter outside of an \"Fn::Sub\" at {}'.format('/'.join(map(str, parameter_string_path)))\n                matches.append(RuleMatch(parameter_string_path, message))\n\n        return matches\n", "path": "src/cfnlint/rules/functions/SubNeeded.py"}]}