prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Add URL pattern mating support to Protected Capability
  Add URL pattern mating support to Protected Capability model.  For example, something like this could work:
  
  [
      ["POST", "/fhir/v3/Practitioner"],
      ["PUT", "/fhir/v3/Practitioner/[id]"],
      ["POST", "/fhir/v3/Organization"],
      ["PUT", "/fhir/v3/Organization/[id]"],
      ["POST", "/npi/v1/update-all/[npi]"],
      ["POST", "/npi/v1/update-partial/[npi]"],
      ["GET", "/fhir/v3/metadata"]
  ]
  
  Perhaps how the pattern format is expressed in the form should simply match how django URLs work. I leave that to you how best to address.
  
  
  </issue>
  <code>
  [start of apps/dot_ext/models.py]
  1 from __future__ import absolute_import
  2 from __future__ import unicode_literals
  3 
  4 import logging
  5 
  6 from django.core.urlresolvers import reverse
  7 from django.db import models
  8 from django.utils.encoding import python_2_unicode_compatible
  9 
  10 from oauth2_provider.models import AbstractApplication
  11 
  12 from apps.capabilities.models import ProtectedCapability
  13 
  14 
  15 logger = logging.getLogger('hhs_server.%s' % __name__)
  16 
  17 
  18 @python_2_unicode_compatible
  19 class Endorsement(models.Model):
  20     title   = models.TextField(max_length=256, default="")
  21     iss     = models.TextField(max_length=512, default="", verbose_name="Issuer",
  22                                help_text= "Must contain a QDN")
  23     jws     = models.TextField(max_length=10240, default="")
  24 
  25     def __str__(self):
  26         return self.title
  27 
  28 
  29 class Application(AbstractApplication):
  30     scope                  = models.ManyToManyField(ProtectedCapability)
  31     endorsements           = models.ManyToManyField(Endorsement, blank=True)
  32     agree                  = models.BooleanField(default=False)
  33 
  34     _messages = {
  35         "resource_allowed": "application '%s': access to resource '%s %s' allowed",
  36         "resource_forbidden": "application '%s': access to resource '%s %s' forbidden",
  37     }
  38 
  39     def get_absolute_url(self):
  40         return reverse('dote_detail', args=[str(self.id)])
  41 
  42     def allow_resource(self, method, path):
  43         """
  44         Return True when this applications has capability to allow
  45         request to `path` with method `method`.
  46         """
  47         logger.debug("application '%s': checking access to resource '%s %s' is allowed",
  48                      self.name, method, path)
  49 
  50         for scope in self.scope.all():
  51             resources = scope.resources_as_dict()
  52             logger.debug("application '%s': checking access with scope '%s'", self.name, resources)
  53             # both paths are normalized removing trailing slash
  54             for allowed_path in resources.get(method, []):
  55                 if path.rstrip('/') == allowed_path.rstrip('/'):
  56                     logger.info(self._messages['resource_allowed'], self.name, method, path)
  57                     return True
  58 
  59         logger.info(self._messages['resource_forbidden'], self.name, method, path)
  60         return False
  61
  [end of apps/dot_ext/models.py]
  [start of apps/capabilities/models.py]
  1 from __future__ import absolute_import
  2 from __future__ import unicode_literals
  3 
  4 import json
  5 
  6 from django.db import models
  7 from django.utils.encoding import python_2_unicode_compatible
  8 from django.contrib.auth.models import Group
  9 
  10 
  11 @python_2_unicode_compatible
  12 class ProtectedCapability(models.Model):
  13     title               = models.CharField(max_length=256, default="", unique=True)
  14     slug                = models.SlugField(verbose_name="Scope", max_length=100, default="", unique=True)
  15     group               = models.ForeignKey(Group)
  16     protected_resources = models.TextField(max_length=10240,
  17                             help_text="""A JSON list of pairs containing HTTP method and URL.
  18                             Example: [["GET","/api/task1"], ["POST","/api/task2"]]
  19                             """, default="""[["GET", "/some-url"]]""")
  20     description         = models.TextField(max_length=10240, blank=True, default="")
  21 
  22     def __str__(self):
  23         return self.title
  24 
  25     def resources_as_dict(self):
  26         """
  27         Return protected_resources mapped into a dictionary.
  28         e.g. {"GET": ["/api/example1", "/api/example2"], "POST": ... }
  29         """
  30         protected_resources = {}
  31         for method, path in json.loads(self.protected_resources):
  32             if method not in protected_resources:
  33                 protected_resources[method] = [path]
  34             else:
  35                 protected_resources[method].append(path)
  36         return protected_resources
  37 
  38     def scope(self):
  39         return self.slug
  40 
  41     class Meta:
  42         verbose_name_plural = "Protected Capabilities"
  43         verbose_name        = "Protected Capability"
  44
  [end of apps/capabilities/models.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/apps/capabilities/models.py b/apps/capabilities/models.py
  --- a/apps/capabilities/models.py
  +++ b/apps/capabilities/models.py
  @@ -2,10 +2,18 @@
   from __future__ import unicode_literals
   
   import json
  +import re
  +
  +try:
  +    # this import should work on python2 only
  +    from itertools import izip as zip
  +except ImportError:
  +    pass
   
   from django.db import models
  -from django.utils.encoding import python_2_unicode_compatible
   from django.contrib.auth.models import Group
  +from django.utils.encoding import python_2_unicode_compatible
  +from django.utils.lru_cache import lru_cache
   
   
   @python_2_unicode_compatible
  @@ -35,9 +43,63 @@
                   protected_resources[method].append(path)
           return protected_resources
   
  +    def allow(self, method, path):
  +        """
  +        Check if the capability allow access for `method` and `path`.
  +        """
  +        resources = self.resources_as_dict()
  +        for allowed_path in resources.get(method, []):
  +            if _match(path, allowed_path):
  +                return True
  +        return False
  +
       def scope(self):
           return self.slug
   
       class Meta:
           verbose_name_plural = "Protected Capabilities"
           verbose_name        = "Protected Capability"
  +
  +
  +@lru_cache()
  +def _tokenize_path(path):
  +    """
  +    Helper function that removes trailing slash
  +    and split the path into bits.
  +
  +    e.g.: "/api/foo/" -> ["", "api", "foo"]
  +    """
  +    return path.rstrip("/").split("/")
  +
  +
  +URL_BIT_PATTERN = re.compile(r"\[.*\]")
  +
  +
  +@lru_cache()
  +def _match(request_path, allowed_path):
  +    """
  +    Helper function that check if request_path matches with allowed_path
  +    """
  +    # normalize and tokenize both paths
  +    # from '/api/foo' to ['', 'api', 'foo']
  +    request_tokens = _tokenize_path(request_path)
  +    allowed_tokens = _tokenize_path(allowed_path)
  +
  +    # if the number of tokens is different we know
  +    # that the request path does not match the allowed path
  +    if len(request_tokens) != len(allowed_tokens):
  +        return False
  +
  +    # otherwise we start the comparison token by token
  +    for request_token, allowed_token in zip(request_tokens, allowed_tokens):
  +        # if the allowed token matches a pattern like "[id]"
  +        # the match is valid and move to the next token
  +        if URL_BIT_PATTERN.match(allowed_token):
  +            continue
  +
  +        # we can break the loop and return False
  +        # when we encounter the first non-matching token
  +        if request_token != allowed_token:
  +            return False
  +
  +    return True
  diff --git a/apps/dot_ext/models.py b/apps/dot_ext/models.py
  --- a/apps/dot_ext/models.py
  +++ b/apps/dot_ext/models.py
  @@ -48,13 +48,11 @@
                        self.name, method, path)
   
           for scope in self.scope.all():
  -            resources = scope.resources_as_dict()
  -            logger.debug("application '%s': checking access with scope '%s'", self.name, resources)
  -            # both paths are normalized removing trailing slash
  -            for allowed_path in resources.get(method, []):
  -                if path.rstrip('/') == allowed_path.rstrip('/'):
  -                    logger.info(self._messages['resource_allowed'], self.name, method, path)
  -                    return True
  +            logger.debug("application '%s': checking access with scope '%s'",
  +                         self.name, scope.protected_resources)
  +            if scope.allow(method, path):
  +                logger.info(self._messages['resource_allowed'], self.name, method, path)
  +                return True
   
           logger.info(self._messages['resource_forbidden'], self.name, method, path)
           return False
  
verification_info: {"golden_diff": "diff --git a/apps/capabilities/models.py b/apps/capabilities/models.py\n--- a/apps/capabilities/models.py\n+++ b/apps/capabilities/models.py\n@@ -2,10 +2,18 @@\n from __future__ import unicode_literals\n \n import json\n+import re\n+\n+try:\n+    # this import should work on python2 only\n+    from itertools import izip as zip\n+except ImportError:\n+    pass\n \n from django.db import models\n-from django.utils.encoding import python_2_unicode_compatible\n from django.contrib.auth.models import Group\n+from django.utils.encoding import python_2_unicode_compatible\n+from django.utils.lru_cache import lru_cache\n \n \n @python_2_unicode_compatible\n@@ -35,9 +43,63 @@\n                 protected_resources[method].append(path)\n         return protected_resources\n \n+    def allow(self, method, path):\n+        \"\"\"\n+        Check if the capability allow access for `method` and `path`.\n+        \"\"\"\n+        resources = self.resources_as_dict()\n+        for allowed_path in resources.get(method, []):\n+            if _match(path, allowed_path):\n+                return True\n+        return False\n+\n     def scope(self):\n         return self.slug\n \n     class Meta:\n         verbose_name_plural = \"Protected Capabilities\"\n         verbose_name        = \"Protected Capability\"\n+\n+\n+@lru_cache()\n+def _tokenize_path(path):\n+    \"\"\"\n+    Helper function that removes trailing slash\n+    and split the path into bits.\n+\n+    e.g.: \"/api/foo/\" -> [\"\", \"api\", \"foo\"]\n+    \"\"\"\n+    return path.rstrip(\"/\").split(\"/\")\n+\n+\n+URL_BIT_PATTERN = re.compile(r\"\\[.*\\]\")\n+\n+\n+@lru_cache()\n+def _match(request_path, allowed_path):\n+    \"\"\"\n+    Helper function that check if request_path matches with allowed_path\n+    \"\"\"\n+    # normalize and tokenize both paths\n+    # from '/api/foo' to ['', 'api', 'foo']\n+    request_tokens = _tokenize_path(request_path)\n+    allowed_tokens = _tokenize_path(allowed_path)\n+\n+    # if the number of tokens is different we know\n+    # that the request path does not match the allowed path\n+    if len(request_tokens) != len(allowed_tokens):\n+        return False\n+\n+    # otherwise we start the comparison token by token\n+    for request_token, allowed_token in zip(request_tokens, allowed_tokens):\n+        # if the allowed token matches a pattern like \"[id]\"\n+        # the match is valid and move to the next token\n+        if URL_BIT_PATTERN.match(allowed_token):\n+            continue\n+\n+        # we can break the loop and return False\n+        # when we encounter the first non-matching token\n+        if request_token != allowed_token:\n+            return False\n+\n+    return True\ndiff --git a/apps/dot_ext/models.py b/apps/dot_ext/models.py\n--- a/apps/dot_ext/models.py\n+++ b/apps/dot_ext/models.py\n@@ -48,13 +48,11 @@\n                      self.name, method, path)\n \n         for scope in self.scope.all():\n-            resources = scope.resources_as_dict()\n-            logger.debug(\"application '%s': checking access with scope '%s'\", self.name, resources)\n-            # both paths are normalized removing trailing slash\n-            for allowed_path in resources.get(method, []):\n-                if path.rstrip('/') == allowed_path.rstrip('/'):\n-                    logger.info(self._messages['resource_allowed'], self.name, method, path)\n-                    return True\n+            logger.debug(\"application '%s': checking access with scope '%s'\",\n+                         self.name, scope.protected_resources)\n+            if scope.allow(method, path):\n+                logger.info(self._messages['resource_allowed'], self.name, method, path)\n+                return True\n \n         logger.info(self._messages['resource_forbidden'], self.name, method, path)\n         return False\n", "issue": "Add URL pattern mating support to Protected Capability\nAdd URL pattern mating support to Protected Capability model.  For example, something like this could work:\n\n[\n    [\"POST\", \"/fhir/v3/Practitioner\"],\n    [\"PUT\", \"/fhir/v3/Practitioner/[id]\"],\n    [\"POST\", \"/fhir/v3/Organization\"],\n    [\"PUT\", \"/fhir/v3/Organization/[id]\"],\n    [\"POST\", \"/npi/v1/update-all/[npi]\"],\n    [\"POST\", \"/npi/v1/update-partial/[npi]\"],\n    [\"GET\", \"/fhir/v3/metadata\"]\n]\n\nPerhaps how the pattern format is expressed in the form should simply match how django URLs work. I leave that to you how best to address.\n\n", "before_files": [{"content": "from __future__ import absolute_import\nfrom __future__ import unicode_literals\n\nimport logging\n\nfrom django.core.urlresolvers import reverse\nfrom django.db import models\nfrom django.utils.encoding import python_2_unicode_compatible\n\nfrom oauth2_provider.models import AbstractApplication\n\nfrom apps.capabilities.models import ProtectedCapability\n\n\nlogger = logging.getLogger('hhs_server.%s' % __name__)\n\n\n@python_2_unicode_compatible\nclass Endorsement(models.Model):\n    title   = models.TextField(max_length=256, default=\"\")\n    iss     = models.TextField(max_length=512, default=\"\", verbose_name=\"Issuer\",\n                               help_text= \"Must contain a QDN\")\n    jws     = models.TextField(max_length=10240, default=\"\")\n\n    def __str__(self):\n        return self.title\n\n\nclass Application(AbstractApplication):\n    scope                  = models.ManyToManyField(ProtectedCapability)\n    endorsements           = models.ManyToManyField(Endorsement, blank=True)\n    agree                  = models.BooleanField(default=False)\n\n    _messages = {\n        \"resource_allowed\": \"application '%s': access to resource '%s %s' allowed\",\n        \"resource_forbidden\": \"application '%s': access to resource '%s %s' forbidden\",\n    }\n\n    def get_absolute_url(self):\n        return reverse('dote_detail', args=[str(self.id)])\n\n    def allow_resource(self, method, path):\n        \"\"\"\n        Return True when this applications has capability to allow\n        request to `path` with method `method`.\n        \"\"\"\n        logger.debug(\"application '%s': checking access to resource '%s %s' is allowed\",\n                     self.name, method, path)\n\n        for scope in self.scope.all():\n            resources = scope.resources_as_dict()\n            logger.debug(\"application '%s': checking access with scope '%s'\", self.name, resources)\n            # both paths are normalized removing trailing slash\n            for allowed_path in resources.get(method, []):\n                if path.rstrip('/') == allowed_path.rstrip('/'):\n                    logger.info(self._messages['resource_allowed'], self.name, method, path)\n                    return True\n\n        logger.info(self._messages['resource_forbidden'], self.name, method, path)\n        return False\n", "path": "apps/dot_ext/models.py"}, {"content": "from __future__ import absolute_import\nfrom __future__ import unicode_literals\n\nimport json\n\nfrom django.db import models\nfrom django.utils.encoding import python_2_unicode_compatible\nfrom django.contrib.auth.models import Group\n\n\n@python_2_unicode_compatible\nclass ProtectedCapability(models.Model):\n    title               = models.CharField(max_length=256, default=\"\", unique=True)\n    slug                = models.SlugField(verbose_name=\"Scope\", max_length=100, default=\"\", unique=True)\n    group               = models.ForeignKey(Group)\n    protected_resources = models.TextField(max_length=10240,\n                            help_text=\"\"\"A JSON list of pairs containing HTTP method and URL.\n                            Example: [[\"GET\",\"/api/task1\"], [\"POST\",\"/api/task2\"]]\n                            \"\"\", default=\"\"\"[[\"GET\", \"/some-url\"]]\"\"\")\n    description         = models.TextField(max_length=10240, blank=True, default=\"\")\n\n    def __str__(self):\n        return self.title\n\n    def resources_as_dict(self):\n        \"\"\"\n        Return protected_resources mapped into a dictionary.\n        e.g. {\"GET\": [\"/api/example1\", \"/api/example2\"], \"POST\": ... }\n        \"\"\"\n        protected_resources = {}\n        for method, path in json.loads(self.protected_resources):\n            if method not in protected_resources:\n                protected_resources[method] = [path]\n            else:\n                protected_resources[method].append(path)\n        return protected_resources\n\n    def scope(self):\n        return self.slug\n\n    class Meta:\n        verbose_name_plural = \"Protected Capabilities\"\n        verbose_name        = \"Protected Capability\"\n", "path": "apps/capabilities/models.py"}]}