Create additional references for duplicate footnotes (#534)

Track when we find duplicate footnote references and create unique ids
for them.  Then add an additional tree-processor after inline to go
back and update the footnotes with additional back references that link
to the duplicate footnote references. Fixes #468.

3 files changed, 115 insertions, 5 deletions

diff --git a/markdown/extensions/footnotes.py b/markdown/extensions/footnotes.py
index b52815f..368334d 100644
--- a/markdown/extensions/footnotes.py
+++ b/markdown/extensions/footnotes.py
@@ -23,11 +23,13 @@ from ..postprocessors import Postprocessor
 from ..util import etree, text_type
 from ..odict import OrderedDict
 import re
+import copy
 
 FN_BACKLINK_TEXT = "zz1337820767766393qq"
 NBSP_PLACEHOLDER = "qq3936677670287331zz"
 DEF_RE = re.compile(r'[ ]{0,3}\[\^([^\]]*)\]:\s*(.*)')
 TABBED_RE = re.compile(r'((\t)|(    ))(.*)')
+RE_REF_ID = re.compile(r'(fnref)(\d+)')
 
 
 class FootnoteExtension(Extension):
@@ -53,6 +55,8 @@ class FootnoteExtension(Extension):
 
         # In multiple invocations, emit links that don't get tangled.
         self.unique_prefix = 0
+        self.found_refs = {}
+        self.used_refs = set()
 
         self.reset()
 
@@ -76,6 +80,15 @@ class FootnoteExtension(Extension):
         md.treeprocessors.add(
             "footnote", FootnoteTreeprocessor(self), "_begin"
         )
+
+        # Insert a tree-processor that will run after inline is done.
+        # In this tree-processor we want to check our duplicate footnote tracker
+        # And add additional backrefs to the footnote pointing back to the
+        # duplicated references.
+        md.treeprocessors.add(
+            "footnote-duplicate", FootnotePostTreeprocessor(self), '>inline'
+        )
+
         # Insert a postprocessor after amp_substitute oricessor
         md.postprocessors.add(
             "footnote", FootnotePostprocessor(self), ">amp_substitute"
@@ -85,6 +98,29 @@ class FootnoteExtension(Extension):
         """ Clear footnotes on reset, and prepare for distinct document. """
         self.footnotes = OrderedDict()
         self.unique_prefix += 1
+        self.found_refs = {}
+        self.used_refs = set()
+
+    def unique_ref(self, reference, found=False):
+        """ Get a unique reference if there are duplicates. """
+        if not found:
+            return reference
+
+        original_ref = reference
+        while reference in self.used_refs:
+            ref, rest = reference.split(self.get_separator(), 1)
+            m = RE_REF_ID.match(ref)
+            if m:
+                reference = '%s%d%s%s' % (m.group(1), int(m.group(2))+1, self.get_separator(), rest)
+            else:
+                reference = '%s%d%s%s' % (ref, 2, self.get_separator(), rest)
+
+        self.used_refs.add(reference)
+        if original_ref in self.found_refs:
+            self.found_refs[original_ref] += 1
+        else:
+            self.found_refs[original_ref] = 1
+        return reference
 
     def findFootnotesPlaceholder(self, root):
         """ Return ElementTree Element that contains Footnote placeholder. """
@@ -120,13 +156,12 @@ class FootnoteExtension(Extension):
         else:
             return 'fn%s%s' % (self.get_separator(), id)
 
-    def makeFootnoteRefId(self, id):
+    def makeFootnoteRefId(self, id, found=False):
         """ Return footnote back-link id. """
         if self.getConfig("UNIQUE_IDS"):
-            return 'fnref%s%d-%s' % (self.get_separator(),
-                                     self.unique_prefix, id)
+            return self.unique_ref('fnref%s%d-%s' % (self.get_separator(), self.unique_prefix, id), found)
         else:
-            return 'fnref%s%s' % (self.get_separator(), id)
+            return self.unique_ref('fnref%s%s' % (self.get_separator(), id), found)
 
     def makeFootnotesDiv(self, root):
         """ Return div of footnotes as et Element. """
@@ -270,7 +305,7 @@ class FootnotePattern(Pattern):
         if id in self.footnotes.footnotes.keys():
             sup = etree.Element("sup")
             a = etree.SubElement(sup, "a")
-            sup.set('id', self.footnotes.makeFootnoteRefId(id))
+            sup.set('id', self.footnotes.makeFootnoteRefId(id, found=True))
             a.set('href', '#' + self.footnotes.makeFootnoteId(id))
             if self.footnotes.md.output_format not in ['html5', 'xhtml5']:
                 a.set('rel', 'footnote')  # invalid in HTML5
@@ -281,6 +316,59 @@ class FootnotePattern(Pattern):
             return None
 
 
+class FootnotePostTreeprocessor(Treeprocessor):
+    """ Ammend footnote div with duplicates. """
+
+    def __init__(self, footnotes):
+        self.footnotes = footnotes
+
+    def add_duplicates(self, li, duplicates):
+        """ Adjust current li and add the duplicates: fnref2, fnref3, etc. """
+        for link in li.iter('a'):
+            # Find the link that needs to be duplicated.
+            if link.attrib.get('class', '') == 'footnote-backref':
+                ref, rest = link.attrib['href'].split(self.footnotes.get_separator(), 1)
+                # Duplicate link the number of times we need to
+                # and point the to the appropriate references.
+                links = []
+                for index in range(2, duplicates + 1):
+                    sib_link = copy.deepcopy(link)
+                    sib_link.attrib['href'] = '%s%d%s%s' % (ref, index, self.footnotes.get_separator(), rest)
+                    links.append(sib_link)
+                    self.offset += 1
+                # Add all the new duplicate links.
+                el = list(li)[-1]
+                for l in links:
+                    el.append(l)
+                break
+
+    def get_num_duplicates(self, li):
+        """ Get the number of duplicate refs of the footnote. """
+        fn, rest = li.attrib.get('id', '').split(self.footnotes.get_separator(), 1)
+        link_id = '%sref%s%s' % (fn, self.footnotes.get_separator(), rest)
+        return self.footnotes.found_refs.get(link_id, 0)
+
+    def handle_duplicates(self, parent):
+        """ Find duplicate footnotes and format and add the duplicates. """
+        for li in list(parent):
+            # Check number of duplicates footnotes and insert
+            # additional links if needed.
+            count = self.get_num_duplicates(li)
+            if count > 1:
+                self.add_duplicates(li, count)
+
+    def run(self, root):
+        """ Crawl the footnote div and add missing duplicate footnotes. """
+        self.offset = 0
+        for div in root.iter('div'):
+            if div.attrib.get('class', '') == 'footnote':
+                # Footnotes shoul be under the first orderd list under
+                # the footnote div.  So once we find it, quit.
+                for ol in div.iter('ol'):
+                    self.handle_duplicates(ol)
+                    break
+
+
 class FootnoteTreeprocessor(Treeprocessor):
     """ Build and append footnote div to end of document. """
 
diff --git a/tests/extensions/extra/footnote.html b/tests/extensions/extra/footnote.html
index e5b41a7..9cf42ed 100644
--- a/tests/extensions/extra/footnote.html
+++ b/tests/extensions/extra/footnote.html
@@ -1,5 +1,8 @@
 <p>This is the body with a footnote<sup id="fnref:1"><a class="footnote-ref" href="#fn:1" rel="footnote">1</a></sup> or two<sup id="fnref:2"><a class="footnote-ref" href="#fn:2" rel="footnote">2</a></sup> or more<sup id="fnref:3"><a class="footnote-ref" href="#fn:3" rel="footnote">3</a></sup> <sup id="fnref:4"><a class="footnote-ref" href="#fn:4" rel="footnote">4</a></sup> <sup id="fnref:5"><a class="footnote-ref" href="#fn:5" rel="footnote">5</a></sup>.</p>
 <p>Also a reference that does not exist[^6].</p>
+<p>Duplicate<sup id="fnref:a"><a class="footnote-ref" href="#fn:a" rel="footnote">6</a></sup> footnotes<sup id="fnref2:a"><a class="footnote-ref" href="#fn:a" rel="footnote">6</a></sup> test<sup id="fnref3:a"><a class="footnote-ref" href="#fn:a" rel="footnote">6</a></sup>.</p>
+<p>Duplicate<sup id="fnref:b"><a class="footnote-ref" href="#fn:b" rel="footnote">7</a></sup> footnotes<sup id="fnref2:b"><a class="footnote-ref" href="#fn:b" rel="footnote">7</a></sup> test<sup id="fnref3:b"><a class="footnote-ref" href="#fn:b" rel="footnote">7</a></sup>.</p>
+<p>Single after duplicates<sup id="fnref:c"><a class="footnote-ref" href="#fn:c" rel="footnote">8</a></sup>.</p>
 <div class="footnote">
 <hr />
 <ol>
@@ -29,5 +32,14 @@
 Second line of first paragraph is not intended.
 Nor is third...&#160;<a class="footnote-backref" href="#fnref:5" rev="footnote" title="Jump back to footnote 5 in the text">&#8617;</a></p>
 </li>
+<li id="fn:a">
+<p>1&#160;<a class="footnote-backref" href="#fnref:a" rev="footnote" title="Jump back to footnote 6 in the text">&#8617;</a><a class="footnote-backref" href="#fnref2:a" rev="footnote" title="Jump back to footnote 6 in the text">&#8617;</a><a class="footnote-backref" href="#fnref3:a" rev="footnote" title="Jump back to footnote 6 in the text">&#8617;</a></p>
+</li>
+<li id="fn:b">
+<p>2&#160;<a class="footnote-backref" href="#fnref:b" rev="footnote" title="Jump back to footnote 7 in the text">&#8617;</a><a class="footnote-backref" href="#fnref2:b" rev="footnote" title="Jump back to footnote 7 in the text">&#8617;</a><a class="footnote-backref" href="#fnref3:b" rev="footnote" title="Jump back to footnote 7 in the text">&#8617;</a></p>
+</li>
+<li id="fn:c">
+<p>3&#160;<a class="footnote-backref" href="#fnref:c" rev="footnote" title="Jump back to footnote 8 in the text">&#8617;</a></p>
+</li>
 </ol>
 </div>
\ No newline at end of file
diff --git a/tests/extensions/extra/footnote.txt b/tests/extensions/extra/footnote.txt
index c5c1c92..f95ff2c 100644
--- a/tests/extensions/extra/footnote.txt
+++ b/tests/extensions/extra/footnote.txt
@@ -2,6 +2,12 @@ This is the body with a footnote[^1] or two[^2] or more[^3] [^4] [^5].
 
 Also a reference that does not exist[^6].
 
+Duplicate[^a] footnotes[^a] test[^a].
+
+Duplicate[^b] footnotes[^b] test[^b].
+
+Single after duplicates[^c].
+
 [^1]: Footnote that ends with a list:
 
     * item 1
@@ -18,3 +24,7 @@ Also a reference that does not exist[^6].
 [^5]: First line of first paragraph.
 Second line of first paragraph is not intended.
 Nor is third...
+
+[^a]: 1
+[^b]: 2
+[^c]: 3