prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Not all headers are automatically linked
  I have an API reference site for a project that's hosted on ReadTheDocs using mkdocs as the documentation engine. Headers that contain things like `<code>` blocks aren't linked, while all others seem to be.
  
  I can reproduce this locally with a plain mkdocs install using the RTD theme.
  
  Here's an example:
  http://carbon.lpghatguy.com/en/latest/Classes/Collections.Tuple/
  
  All three of the methods in that page should be automatically linked in the sidebar navigation, but only the one without any fancy decoration is. All of them have been given valid HTML ids, so they're possible to link, they just aren't.
  
  The markdown for that page, which works around a couple RTD bugs and doesn't look that great, is here:
  https://raw.githubusercontent.com/lua-carbon/carbon/master/docs/Classes/Collections.Tuple.md
  
  
  </issue>
  <code>
  [start of mkdocs/compat.py]
  1 # coding: utf-8
  2 """Python 2/3 compatibility module."""
  3 import sys
  4 
  5 PY2 = int(sys.version[0]) == 2
  6 
  7 if PY2:
  8     from urlparse import urljoin, urlparse, urlunparse
  9     import urllib
  10     urlunquote = urllib.unquote
  11 
  12     import SimpleHTTPServer as httpserver
  13     httpserver = httpserver
  14     import SocketServer
  15     socketserver = SocketServer
  16 
  17     import itertools
  18     zip = itertools.izip
  19 
  20     text_type = unicode
  21     binary_type = str
  22     string_types = (str, unicode)
  23     unicode = unicode
  24     basestring = basestring
  25 else:  # PY3
  26     from urllib.parse import urljoin, urlparse, urlunparse, unquote
  27     urlunquote = unquote
  28 
  29     import http.server as httpserver
  30     httpserver = httpserver
  31     import socketserver
  32     socketserver = socketserver
  33 
  34     zip = zip
  35 
  36     text_type = str
  37     binary_type = bytes
  38     string_types = (str,)
  39     unicode = str
  40     basestring = (str, bytes)
  41
  [end of mkdocs/compat.py]
  [start of mkdocs/toc.py]
  1 # coding: utf-8
  2 
  3 """
  4 Deals with generating the per-page table of contents.
  5 
  6 For the sake of simplicity we use an existing markdown extension to generate
  7 an HTML table of contents, and then parse that into the underlying data.
  8 
  9 The steps we take to generate a table of contents are:
  10 
  11 * Pre-process the markdown, injecting a [TOC] marker.
  12 * Generate HTML from markdown.
  13 * Post-process the HTML, spliting the content and the table of contents.
  14 * Parse table of contents HTML into the underlying data structure.
  15 """
  16 
  17 import re
  18 
  19 TOC_LINK_REGEX = re.compile('<a href=["]([^"]*)["]>([^<]*)</a>')
  20 
  21 
  22 class TableOfContents(object):
  23     """
  24     Represents the table of contents for a given page.
  25     """
  26     def __init__(self, html):
  27         self.items = _parse_html_table_of_contents(html)
  28 
  29     def __iter__(self):
  30         return iter(self.items)
  31 
  32     def __str__(self):
  33         return ''.join([str(item) for item in self])
  34 
  35 
  36 class AnchorLink(object):
  37     """
  38     A single entry in the table of contents.
  39     """
  40     def __init__(self, title, url):
  41         self.title, self.url = title, url
  42         self.children = []
  43 
  44     def __str__(self):
  45         return self._indent_print()
  46 
  47     def _indent_print(self, depth=0):
  48         indent = '    ' * depth
  49         ret = '%s%s - %s\n' % (indent, self.title, self.url)
  50         for item in self.children:
  51             ret += item._indent_print(depth + 1)
  52         return ret
  53 
  54 
  55 def _parse_html_table_of_contents(html):
  56     """
  57     Given a table of contents string that has been automatically generated by
  58     the markdown library, parse it into a tree of AnchorLink instances.
  59 
  60     Returns a list of all the parent AnchorLink instances.
  61     """
  62     lines = html.splitlines()[2:-2]
  63     parents = []
  64     ret = []
  65     for line in lines:
  66         match = TOC_LINK_REGEX.search(line)
  67         if match:
  68             href, title = match.groups()
  69             nav = AnchorLink(title, href)
  70             # Add the item to its parent if required.  If it is a topmost
  71             # item then instead append it to our return value.
  72             if parents:
  73                 parents[-1].children.append(nav)
  74             else:
  75                 ret.append(nav)
  76             # If this item has children, store it as the current parent
  77             if line.endswith('<ul>'):
  78                 parents.append(nav)
  79         elif line.startswith('</ul>'):
  80             if parents:
  81                 parents.pop()
  82 
  83     # For the table of contents, always mark the first element as active
  84     if ret:
  85         ret[0].active = True
  86 
  87     return ret
  88
  [end of mkdocs/toc.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/mkdocs/compat.py b/mkdocs/compat.py
  --- a/mkdocs/compat.py
  +++ b/mkdocs/compat.py
  @@ -13,6 +13,7 @@
       httpserver = httpserver
       import SocketServer
       socketserver = SocketServer
  +    from HTMLParser import HTMLParser
   
       import itertools
       zip = itertools.izip
  @@ -30,6 +31,7 @@
       httpserver = httpserver
       import socketserver
       socketserver = socketserver
  +    from html.parser import HTMLParser
   
       zip = zip
   
  diff --git a/mkdocs/toc.py b/mkdocs/toc.py
  --- a/mkdocs/toc.py
  +++ b/mkdocs/toc.py
  @@ -14,9 +14,7 @@
   * Parse table of contents HTML into the underlying data structure.
   """
   
  -import re
  -
  -TOC_LINK_REGEX = re.compile('<a href=["]([^"]*)["]>([^<]*)</a>')
  +from mkdocs.compat import HTMLParser
   
   
   class TableOfContents(object):
  @@ -52,6 +50,32 @@
           return ret
   
   
  +class TOCParser(HTMLParser):
  +
  +    def __init__(self):
  +        HTMLParser.__init__(self)
  +        self.links = []
  +
  +        self.in_anchor = True
  +        self.attrs = None
  +        self.title = ''
  +
  +    def handle_starttag(self, tag, attrs):
  +
  +        if tag == 'a':
  +            self.in_anchor = True
  +            self.attrs = dict(attrs)
  +
  +    def handle_endtag(self, tag):
  +        if tag == 'a':
  +            self.in_anchor = False
  +
  +    def handle_data(self, data):
  +
  +        if self.in_anchor:
  +            self.title += data
  +
  +
   def _parse_html_table_of_contents(html):
       """
       Given a table of contents string that has been automatically generated by
  @@ -63,9 +87,11 @@
       parents = []
       ret = []
       for line in lines:
  -        match = TOC_LINK_REGEX.search(line)
  -        if match:
  -            href, title = match.groups()
  +        parser = TOCParser()
  +        parser.feed(line)
  +        if parser.title:
  +            href = parser.attrs['href']
  +            title = parser.title
               nav = AnchorLink(title, href)
               # Add the item to its parent if required.  If it is a topmost
               # item then instead append it to our return value.
  
verification_info: {"golden_diff": "diff --git a/mkdocs/compat.py b/mkdocs/compat.py\n--- a/mkdocs/compat.py\n+++ b/mkdocs/compat.py\n@@ -13,6 +13,7 @@\n     httpserver = httpserver\n     import SocketServer\n     socketserver = SocketServer\n+    from HTMLParser import HTMLParser\n \n     import itertools\n     zip = itertools.izip\n@@ -30,6 +31,7 @@\n     httpserver = httpserver\n     import socketserver\n     socketserver = socketserver\n+    from html.parser import HTMLParser\n \n     zip = zip\n \ndiff --git a/mkdocs/toc.py b/mkdocs/toc.py\n--- a/mkdocs/toc.py\n+++ b/mkdocs/toc.py\n@@ -14,9 +14,7 @@\n * Parse table of contents HTML into the underlying data structure.\n \"\"\"\n \n-import re\n-\n-TOC_LINK_REGEX = re.compile('<a href=[\"]([^\"]*)[\"]>([^<]*)</a>')\n+from mkdocs.compat import HTMLParser\n \n \n class TableOfContents(object):\n@@ -52,6 +50,32 @@\n         return ret\n \n \n+class TOCParser(HTMLParser):\n+\n+    def __init__(self):\n+        HTMLParser.__init__(self)\n+        self.links = []\n+\n+        self.in_anchor = True\n+        self.attrs = None\n+        self.title = ''\n+\n+    def handle_starttag(self, tag, attrs):\n+\n+        if tag == 'a':\n+            self.in_anchor = True\n+            self.attrs = dict(attrs)\n+\n+    def handle_endtag(self, tag):\n+        if tag == 'a':\n+            self.in_anchor = False\n+\n+    def handle_data(self, data):\n+\n+        if self.in_anchor:\n+            self.title += data\n+\n+\n def _parse_html_table_of_contents(html):\n     \"\"\"\n     Given a table of contents string that has been automatically generated by\n@@ -63,9 +87,11 @@\n     parents = []\n     ret = []\n     for line in lines:\n-        match = TOC_LINK_REGEX.search(line)\n-        if match:\n-            href, title = match.groups()\n+        parser = TOCParser()\n+        parser.feed(line)\n+        if parser.title:\n+            href = parser.attrs['href']\n+            title = parser.title\n             nav = AnchorLink(title, href)\n             # Add the item to its parent if required.  If it is a topmost\n             # item then instead append it to our return value.\n", "issue": "Not all headers are automatically linked\nI have an API reference site for a project that's hosted on ReadTheDocs using mkdocs as the documentation engine. Headers that contain things like `<code>` blocks aren't linked, while all others seem to be.\n\nI can reproduce this locally with a plain mkdocs install using the RTD theme.\n\nHere's an example:\nhttp://carbon.lpghatguy.com/en/latest/Classes/Collections.Tuple/\n\nAll three of the methods in that page should be automatically linked in the sidebar navigation, but only the one without any fancy decoration is. All of them have been given valid HTML ids, so they're possible to link, they just aren't.\n\nThe markdown for that page, which works around a couple RTD bugs and doesn't look that great, is here:\nhttps://raw.githubusercontent.com/lua-carbon/carbon/master/docs/Classes/Collections.Tuple.md\n\n", "before_files": [{"content": "# coding: utf-8\n\"\"\"Python 2/3 compatibility module.\"\"\"\nimport sys\n\nPY2 = int(sys.version[0]) == 2\n\nif PY2:\n    from urlparse import urljoin, urlparse, urlunparse\n    import urllib\n    urlunquote = urllib.unquote\n\n    import SimpleHTTPServer as httpserver\n    httpserver = httpserver\n    import SocketServer\n    socketserver = SocketServer\n\n    import itertools\n    zip = itertools.izip\n\n    text_type = unicode\n    binary_type = str\n    string_types = (str, unicode)\n    unicode = unicode\n    basestring = basestring\nelse:  # PY3\n    from urllib.parse import urljoin, urlparse, urlunparse, unquote\n    urlunquote = unquote\n\n    import http.server as httpserver\n    httpserver = httpserver\n    import socketserver\n    socketserver = socketserver\n\n    zip = zip\n\n    text_type = str\n    binary_type = bytes\n    string_types = (str,)\n    unicode = str\n    basestring = (str, bytes)\n", "path": "mkdocs/compat.py"}, {"content": "# coding: utf-8\n\n\"\"\"\nDeals with generating the per-page table of contents.\n\nFor the sake of simplicity we use an existing markdown extension to generate\nan HTML table of contents, and then parse that into the underlying data.\n\nThe steps we take to generate a table of contents are:\n\n* Pre-process the markdown, injecting a [TOC] marker.\n* Generate HTML from markdown.\n* Post-process the HTML, spliting the content and the table of contents.\n* Parse table of contents HTML into the underlying data structure.\n\"\"\"\n\nimport re\n\nTOC_LINK_REGEX = re.compile('<a href=[\"]([^\"]*)[\"]>([^<]*)</a>')\n\n\nclass TableOfContents(object):\n    \"\"\"\n    Represents the table of contents for a given page.\n    \"\"\"\n    def __init__(self, html):\n        self.items = _parse_html_table_of_contents(html)\n\n    def __iter__(self):\n        return iter(self.items)\n\n    def __str__(self):\n        return ''.join([str(item) for item in self])\n\n\nclass AnchorLink(object):\n    \"\"\"\n    A single entry in the table of contents.\n    \"\"\"\n    def __init__(self, title, url):\n        self.title, self.url = title, url\n        self.children = []\n\n    def __str__(self):\n        return self._indent_print()\n\n    def _indent_print(self, depth=0):\n        indent = '    ' * depth\n        ret = '%s%s - %s\\n' % (indent, self.title, self.url)\n        for item in self.children:\n            ret += item._indent_print(depth + 1)\n        return ret\n\n\ndef _parse_html_table_of_contents(html):\n    \"\"\"\n    Given a table of contents string that has been automatically generated by\n    the markdown library, parse it into a tree of AnchorLink instances.\n\n    Returns a list of all the parent AnchorLink instances.\n    \"\"\"\n    lines = html.splitlines()[2:-2]\n    parents = []\n    ret = []\n    for line in lines:\n        match = TOC_LINK_REGEX.search(line)\n        if match:\n            href, title = match.groups()\n            nav = AnchorLink(title, href)\n            # Add the item to its parent if required.  If it is a topmost\n            # item then instead append it to our return value.\n            if parents:\n                parents[-1].children.append(nav)\n            else:\n                ret.append(nav)\n            # If this item has children, store it as the current parent\n            if line.endswith('<ul>'):\n                parents.append(nav)\n        elif line.startswith('</ul>'):\n            if parents:\n                parents.pop()\n\n    # For the table of contents, always mark the first element as active\n    if ret:\n        ret[0].active = True\n\n    return ret\n", "path": "mkdocs/toc.py"}]}