prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Nikola generates invalid html5 when markdown footnote extension is used
  The [default output type](http://pythonhosted.org/Markdown/reference.html#markdown) of the python markdown library is xhtml1. The 4 templates that ship with Nikola have <!DOCTYPE html> which defines them as html5, so I'm assuming that we're intending to generate html5.
  
  When the footnote markdown extension is used, it generates invalid html5 according to the w3c validator.
  
  `<a class="footnote-ref" href="..." rev="footnote">...</a>`
  
  (rev="footnote" is valid html4, but not html5)
  
  The markdown library indicates that this is invalid html5 (https://github.com/waylan/Python-Markdown/blob/master/markdown/extensions/footnotes.py#L149) so we can trigger the correct behaviour by setting the output_format.
  
  Given the markdown library does not make much use of the output_format variable, I don't think this is likely to materially change the output for many people at all - https://github.com/waylan/Python-Markdown/search?utf8=%E2%9C%93&q=output_format)
  
  
  </issue>
  <code>
  [start of nikola/plugins/compile/markdown/__init__.py]
  1 # -*- coding: utf-8 -*-
  2 
  3 # Copyright © 2012-2016 Roberto Alsina and others.
  4 
  5 # Permission is hereby granted, free of charge, to any
  6 # person obtaining a copy of this software and associated
  7 # documentation files (the "Software"), to deal in the
  8 # Software without restriction, including without limitation
  9 # the rights to use, copy, modify, merge, publish,
  10 # distribute, sublicense, and/or sell copies of the
  11 # Software, and to permit persons to whom the Software is
  12 # furnished to do so, subject to the following conditions:
  13 #
  14 # The above copyright notice and this permission notice
  15 # shall be included in all copies or substantial portions of
  16 # the Software.
  17 #
  18 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
  19 # KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  20 # WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  21 # PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS
  22 # OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  23 # OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  24 # OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  25 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26 
  27 """Implementation of compile_html based on markdown."""
  28 
  29 from __future__ import unicode_literals
  30 
  31 import io
  32 import os
  33 
  34 try:
  35     from markdown import markdown
  36 except ImportError:
  37     markdown = None  # NOQA
  38     nikola_extension = None
  39     gist_extension = None
  40     podcast_extension = None
  41 
  42 from nikola.plugin_categories import PageCompiler
  43 from nikola.utils import makedirs, req_missing, write_metadata
  44 
  45 
  46 class CompileMarkdown(PageCompiler):
  47     """Compile Markdown into HTML."""
  48 
  49     name = "markdown"
  50     friendly_name = "Markdown"
  51     demote_headers = True
  52     extensions = []
  53     site = None
  54 
  55     def set_site(self, site):
  56         """Set Nikola site."""
  57         super(CompileMarkdown, self).set_site(site)
  58         self.config_dependencies = []
  59         for plugin_info in self.get_compiler_extensions():
  60             self.config_dependencies.append(plugin_info.name)
  61             self.extensions.append(plugin_info.plugin_object)
  62             plugin_info.plugin_object.short_help = plugin_info.description
  63 
  64         self.config_dependencies.append(str(sorted(site.config.get("MARKDOWN_EXTENSIONS"))))
  65 
  66     def compile_html(self, source, dest, is_two_file=True):
  67         """Compile source file into HTML and save as dest."""
  68         if markdown is None:
  69             req_missing(['markdown'], 'build this site (compile Markdown)')
  70         makedirs(os.path.dirname(dest))
  71         self.extensions += self.site.config.get("MARKDOWN_EXTENSIONS")
  72         try:
  73             post = self.site.post_per_input_file[source]
  74         except KeyError:
  75             post = None
  76         with io.open(dest, "w+", encoding="utf8") as out_file:
  77             with io.open(source, "r", encoding="utf8") as in_file:
  78                 data = in_file.read()
  79             if not is_two_file:
  80                 _, data = self.split_metadata(data)
  81             output = markdown(data, self.extensions)
  82             output, shortcode_deps = self.site.apply_shortcodes(output, filename=source, with_dependencies=True, extra_context=dict(post=post))
  83             out_file.write(output)
  84         if post is None:
  85             if shortcode_deps:
  86                 self.logger.error(
  87                     "Cannot save dependencies for post {0} due to unregistered source file name",
  88                     source)
  89         else:
  90             post._depfile[dest] += shortcode_deps
  91 
  92     def create_post(self, path, **kw):
  93         """Create a new post."""
  94         content = kw.pop('content', None)
  95         onefile = kw.pop('onefile', False)
  96         # is_page is not used by create_post as of now.
  97         kw.pop('is_page', False)
  98 
  99         metadata = {}
  100         metadata.update(self.default_metadata)
  101         metadata.update(kw)
  102         makedirs(os.path.dirname(path))
  103         if not content.endswith('\n'):
  104             content += '\n'
  105         with io.open(path, "w+", encoding="utf8") as fd:
  106             if onefile:
  107                 fd.write('<!-- \n')
  108                 fd.write(write_metadata(metadata))
  109                 fd.write('-->\n\n')
  110             fd.write(content)
  111
  [end of nikola/plugins/compile/markdown/__init__.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/nikola/plugins/compile/markdown/__init__.py b/nikola/plugins/compile/markdown/__init__.py
  --- a/nikola/plugins/compile/markdown/__init__.py
  +++ b/nikola/plugins/compile/markdown/__init__.py
  @@ -78,7 +78,7 @@
                   data = in_file.read()
               if not is_two_file:
                   _, data = self.split_metadata(data)
  -            output = markdown(data, self.extensions)
  +            output = markdown(data, self.extensions, output_format="html5")
               output, shortcode_deps = self.site.apply_shortcodes(output, filename=source, with_dependencies=True, extra_context=dict(post=post))
               out_file.write(output)
           if post is None:
  
verification_info: {"golden_diff": "diff --git a/nikola/plugins/compile/markdown/__init__.py b/nikola/plugins/compile/markdown/__init__.py\n--- a/nikola/plugins/compile/markdown/__init__.py\n+++ b/nikola/plugins/compile/markdown/__init__.py\n@@ -78,7 +78,7 @@\n                 data = in_file.read()\n             if not is_two_file:\n                 _, data = self.split_metadata(data)\n-            output = markdown(data, self.extensions)\n+            output = markdown(data, self.extensions, output_format=\"html5\")\n             output, shortcode_deps = self.site.apply_shortcodes(output, filename=source, with_dependencies=True, extra_context=dict(post=post))\n             out_file.write(output)\n         if post is None:\n", "issue": "Nikola generates invalid html5 when markdown footnote extension is used\nThe [default output type](http://pythonhosted.org/Markdown/reference.html#markdown) of the python markdown library is xhtml1. The 4 templates that ship with Nikola have <!DOCTYPE html> which defines them as html5, so I'm assuming that we're intending to generate html5.\n\nWhen the footnote markdown extension is used, it generates invalid html5 according to the w3c validator.\n\n`<a class=\"footnote-ref\" href=\"...\" rev=\"footnote\">...</a>`\n\n(rev=\"footnote\" is valid html4, but not html5)\n\nThe markdown library indicates that this is invalid html5 (https://github.com/waylan/Python-Markdown/blob/master/markdown/extensions/footnotes.py#L149) so we can trigger the correct behaviour by setting the output_format.\n\nGiven the markdown library does not make much use of the output_format variable, I don't think this is likely to materially change the output for many people at all - https://github.com/waylan/Python-Markdown/search?utf8=%E2%9C%93&q=output_format)\n\n", "before_files": [{"content": "# -*- coding: utf-8 -*-\n\n# Copyright \u00a9 2012-2016 Roberto Alsina and others.\n\n# Permission is hereby granted, free of charge, to any\n# person obtaining a copy of this software and associated\n# documentation files (the \"Software\"), to deal in the\n# Software without restriction, including without limitation\n# the rights to use, copy, modify, merge, publish,\n# distribute, sublicense, and/or sell copies of the\n# Software, and to permit persons to whom the Software is\n# furnished to do so, subject to the following conditions:\n#\n# The above copyright notice and this permission notice\n# shall be included in all copies or substantial portions of\n# the Software.\n#\n# THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY\n# KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE\n# WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR\n# PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS\n# OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR\n# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR\n# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE\n# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\n\n\"\"\"Implementation of compile_html based on markdown.\"\"\"\n\nfrom __future__ import unicode_literals\n\nimport io\nimport os\n\ntry:\n    from markdown import markdown\nexcept ImportError:\n    markdown = None  # NOQA\n    nikola_extension = None\n    gist_extension = None\n    podcast_extension = None\n\nfrom nikola.plugin_categories import PageCompiler\nfrom nikola.utils import makedirs, req_missing, write_metadata\n\n\nclass CompileMarkdown(PageCompiler):\n    \"\"\"Compile Markdown into HTML.\"\"\"\n\n    name = \"markdown\"\n    friendly_name = \"Markdown\"\n    demote_headers = True\n    extensions = []\n    site = None\n\n    def set_site(self, site):\n        \"\"\"Set Nikola site.\"\"\"\n        super(CompileMarkdown, self).set_site(site)\n        self.config_dependencies = []\n        for plugin_info in self.get_compiler_extensions():\n            self.config_dependencies.append(plugin_info.name)\n            self.extensions.append(plugin_info.plugin_object)\n            plugin_info.plugin_object.short_help = plugin_info.description\n\n        self.config_dependencies.append(str(sorted(site.config.get(\"MARKDOWN_EXTENSIONS\"))))\n\n    def compile_html(self, source, dest, is_two_file=True):\n        \"\"\"Compile source file into HTML and save as dest.\"\"\"\n        if markdown is None:\n            req_missing(['markdown'], 'build this site (compile Markdown)')\n        makedirs(os.path.dirname(dest))\n        self.extensions += self.site.config.get(\"MARKDOWN_EXTENSIONS\")\n        try:\n            post = self.site.post_per_input_file[source]\n        except KeyError:\n            post = None\n        with io.open(dest, \"w+\", encoding=\"utf8\") as out_file:\n            with io.open(source, \"r\", encoding=\"utf8\") as in_file:\n                data = in_file.read()\n            if not is_two_file:\n                _, data = self.split_metadata(data)\n            output = markdown(data, self.extensions)\n            output, shortcode_deps = self.site.apply_shortcodes(output, filename=source, with_dependencies=True, extra_context=dict(post=post))\n            out_file.write(output)\n        if post is None:\n            if shortcode_deps:\n                self.logger.error(\n                    \"Cannot save dependencies for post {0} due to unregistered source file name\",\n                    source)\n        else:\n            post._depfile[dest] += shortcode_deps\n\n    def create_post(self, path, **kw):\n        \"\"\"Create a new post.\"\"\"\n        content = kw.pop('content', None)\n        onefile = kw.pop('onefile', False)\n        # is_page is not used by create_post as of now.\n        kw.pop('is_page', False)\n\n        metadata = {}\n        metadata.update(self.default_metadata)\n        metadata.update(kw)\n        makedirs(os.path.dirname(path))\n        if not content.endswith('\\n'):\n            content += '\\n'\n        with io.open(path, \"w+\", encoding=\"utf8\") as fd:\n            if onefile:\n                fd.write('<!-- \\n')\n                fd.write(write_metadata(metadata))\n                fd.write('-->\\n\\n')\n            fd.write(content)\n", "path": "nikola/plugins/compile/markdown/__init__.py"}]}