Replace homegrown OrderedDict with purpose-built Registry. (#688)

All processors and patterns now get "registered" to a Registry.
Each item is given a name (string) and a priority. The name is for
later reference and the priority can be either an integer or float
and is used to sort. Priority is sorted from highest to lowest. A 
Registry instance is a list-like iterable with the items auto-sorted 
by priority. If two items have the same priority, then they are 
listed in the order there were "registered". Registering a new 
item with the same name as an already registered item replaces
the old item with the new item (however, the new item is sorted by
its newly assigned priority). To remove an item, "deregister" it by 
name or index.

A backwards compatible shim is included so that existing simple
extensions should continue to work. DeprecationWarnings will 
be raised for any code which calls the old API.

Fixes #418.

17 files changed, 51 insertions, 87 deletions

diff --git a/markdown/extensions/abbr.py b/markdown/extensions/abbr.py
index 5e8845b..a3d456f 100644
--- a/markdown/extensions/abbr.py
+++ b/markdown/extensions/abbr.py
@@ -33,7 +33,7 @@ class AbbrExtension(Extension):
 
     def extendMarkdown(self, md, md_globals):
         """ Insert AbbrPreprocessor before ReferencePreprocessor. """
-        md.preprocessors.add('abbr', AbbrPreprocessor(md), '<reference')
+        md.preprocessors.register(AbbrPreprocessor(md), 'abbr', 12)
 
 
 class AbbrPreprocessor(Preprocessor):
@@ -51,8 +51,9 @@ class AbbrPreprocessor(Preprocessor):
             if m:
                 abbr = m.group('abbr').strip()
                 title = m.group('title').strip()
-                self.markdown.inlinePatterns['abbr-%s' % abbr] = \
-                    AbbrInlineProcessor(self._generate_pattern(abbr), title)
+                self.markdown.inlinePatterns.register(
+                    AbbrInlineProcessor(self._generate_pattern(abbr), title), 'abbr-%s' % abbr, 2
+                )
                 # Preserve the line to prevent raw HTML indexing issue.
                 # https://github.com/Python-Markdown/markdown/issues/584
                 new_text.append('')
diff --git a/markdown/extensions/admonition.py b/markdown/extensions/admonition.py
index b001957..cf1b506 100644
--- a/markdown/extensions/admonition.py
+++ b/markdown/extensions/admonition.py
@@ -32,9 +32,7 @@ class AdmonitionExtension(Extension):
         """ Add Admonition to Markdown instance. """
         md.registerExtension(self)
 
-        md.parser.blockprocessors.add('admonition',
-                                      AdmonitionProcessor(md.parser),
-                                      '_begin')
+        md.parser.blockprocessors.register(AdmonitionProcessor(md.parser), 'admonition', 105)
 
 
 class AdmonitionProcessor(BlockProcessor):
diff --git a/markdown/extensions/attr_list.py b/markdown/extensions/attr_list.py
index 76b7d99..a63a5ea 100644
--- a/markdown/extensions/attr_list.py
+++ b/markdown/extensions/attr_list.py
@@ -163,9 +163,7 @@ class AttrListTreeprocessor(Treeprocessor):
 
 class AttrListExtension(Extension):
     def extendMarkdown(self, md, md_globals):
-        md.treeprocessors.add(
-            'attr_list', AttrListTreeprocessor(md), '>prettify'
-        )
+        md.treeprocessors.register(AttrListTreeprocessor(md), 'attr_list', 8)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/codehilite.py b/markdown/extensions/codehilite.py
index fed4d64..8b9cd8f 100644
--- a/markdown/extensions/codehilite.py
+++ b/markdown/extensions/codehilite.py
@@ -255,7 +255,7 @@ class CodeHiliteExtension(Extension):
         """ Add HilitePostprocessor to Markdown instance. """
         hiliter = HiliteTreeprocessor(md)
         hiliter.config = self.getConfigs()
-        md.treeprocessors.add("hilite", hiliter, "<inline")
+        md.treeprocessors.register(hiliter, 'hilite', 30)
 
         md.registerExtension(self)
 
diff --git a/markdown/extensions/def_list.py b/markdown/extensions/def_list.py
index a79c1c1..9463d3a 100644
--- a/markdown/extensions/def_list.py
+++ b/markdown/extensions/def_list.py
@@ -103,12 +103,8 @@ class DefListExtension(Extension):
 
     def extendMarkdown(self, md, md_globals):
         """ Add an instance of DefListProcessor to BlockParser. """
-        md.parser.blockprocessors.add('defindent',
-                                      DefListIndentProcessor(md.parser),
-                                      '>indent')
-        md.parser.blockprocessors.add('deflist',
-                                      DefListProcessor(md.parser),
-                                      '>ulist')
+        md.parser.blockprocessors.register(DefListIndentProcessor(md.parser), 'defindent', 85)
+        md.parser.blockprocessors.register(DefListProcessor(md.parser), 'deflist', 25)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/extra.py b/markdown/extensions/extra.py
index d1294e0..da4cb38 100644
--- a/markdown/extensions/extra.py
+++ b/markdown/extensions/extra.py
@@ -59,9 +59,9 @@ class ExtraExtension(Extension):
         md.registerExtensions(extensions, self.config)
         # Turn on processing of markdown text within raw html
         md.preprocessors['html_block'].markdown_in_raw = True
-        md.parser.blockprocessors.add('markdown_block',
-                                      MarkdownInHtmlProcessor(md.parser),
-                                      '_begin')
+        md.parser.blockprocessors.register(
+            MarkdownInHtmlProcessor(md.parser), 'markdown_block', 105
+        )
         md.parser.blockprocessors.tag_counter = -1
         md.parser.blockprocessors.contain_span_tags = re.compile(
             r'^(p|h[1-6]|li|dd|dt|td|th|legend|address)$', re.IGNORECASE)
diff --git a/markdown/extensions/fenced_code.py b/markdown/extensions/fenced_code.py
index e1a616e..c38dabf 100644
--- a/markdown/extensions/fenced_code.py
+++ b/markdown/extensions/fenced_code.py
@@ -29,9 +29,7 @@ class FencedCodeExtension(Extension):
         """ Add FencedBlockPreprocessor to the Markdown instance. """
         md.registerExtension(self)
 
-        md.preprocessors.add('fenced_code_block',
-                             FencedBlockPreprocessor(md),
-                             ">normalize_whitespace")
+        md.preprocessors.register(FencedBlockPreprocessor(md), 'fenced_code_block', 25)
 
 
 class FencedBlockPreprocessor(Preprocessor):
diff --git a/markdown/extensions/footnotes.py b/markdown/extensions/footnotes.py
index a957278..2b9cc40 100644
--- a/markdown/extensions/footnotes.py
+++ b/markdown/extensions/footnotes.py
@@ -21,7 +21,7 @@ from ..inlinepatterns import InlineProcessor
 from ..treeprocessors import Treeprocessor
 from ..postprocessors import Postprocessor
 from .. import util
-from ..odict import OrderedDict
+from collections import OrderedDict
 import re
 import copy
 
@@ -71,33 +71,24 @@ class FootnoteExtension(Extension):
         self.parser = md.parser
         self.md = md
         # Insert a preprocessor before ReferencePreprocessor
-        md.preprocessors.add(
-            "footnote", FootnotePreprocessor(self), "<reference"
-        )
+        md.preprocessors.register(FootnotePreprocessor(self), 'footnote', 15)
+
         # Insert an inline pattern before ImageReferencePattern
         FOOTNOTE_RE = r'\[\^([^\]]*)\]'  # blah blah [^1] blah
-        md.inlinePatterns.add(
-            "footnote", FootnoteInlineProcessor(FOOTNOTE_RE, self), "<reference"
-        )
+        md.inlinePatterns.register(FootnoteInlineProcessor(FOOTNOTE_RE, self), 'footnote', 175)
         # Insert a tree-processor that would actually add the footnote div
         # This must be before all other treeprocessors (i.e., inline and
         # codehilite) so they can run on the the contents of the div.
-        md.treeprocessors.add(
-            "footnote", FootnoteTreeprocessor(self), "_begin"
-        )
+        md.treeprocessors.register(FootnoteTreeprocessor(self), 'footnote', 50)
 
         # 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'
-        )
+        md.treeprocessors.register(FootnotePostTreeprocessor(self), 'footnote-duplicate', 15)
 
-        # Insert a postprocessor after amp_substitute oricessor
-        md.postprocessors.add(
-            "footnote", FootnotePostprocessor(self), ">amp_substitute"
-        )
+        # Insert a postprocessor after amp_substitute processor
+        md.postprocessors.register(FootnotePostprocessor(self), 'footnote', 25)
 
     def reset(self):
         """ Clear footnotes on reset, and prepare for distinct document. """
@@ -180,7 +171,7 @@ class FootnoteExtension(Extension):
         ol = util.etree.SubElement(div, "ol")
         surrogate_parent = util.etree.Element("div")
 
-        for id in self.footnotes.keys():
+        for index, id in enumerate(self.footnotes.keys(), start=1):
             li = util.etree.SubElement(ol, "li")
             li.set("id", self.makeFootnoteId(id))
             # Parse footnote with surrogate parent as li cannot be used.
@@ -197,8 +188,7 @@ class FootnoteExtension(Extension):
             backlink.set("class", "footnote-backref")
             backlink.set(
                 "title",
-                self.getConfig("BACKLINK_TITLE") %
-                (self.footnotes.index(id)+1)
+                self.getConfig("BACKLINK_TITLE") % (index)
             )
             backlink.text = FN_BACKLINK_TEXT
 
@@ -332,7 +322,7 @@ class FootnoteInlineProcessor(InlineProcessor):
             if self.footnotes.md.output_format not in ['html5', 'xhtml5']:
                 a.set('rel', 'footnote')  # invalid in HTML5
             a.set('class', 'footnote-ref')
-            a.text = util.text_type(self.footnotes.footnotes.index(id) + 1)
+            a.text = util.text_type(list(self.footnotes.footnotes.keys()).index(id) + 1)
             return sup, m.start(0), m.end(0)
         else:
             return None, None, None
diff --git a/markdown/extensions/legacy_attrs.py b/markdown/extensions/legacy_attrs.py
index b28223f..740f9d6 100644
--- a/markdown/extensions/legacy_attrs.py
+++ b/markdown/extensions/legacy_attrs.py
@@ -41,8 +41,7 @@ class LegacyAttrs(Treeprocessor):
 
 class LegacyAttrExtension(Extension):
     def extendMarkdown(self, md, md_globals):
-        la = LegacyAttrs(md)
-        md.treeprocessors.add('legacyattrs', la, '>inline')
+        md.treeprocessors.register(LegacyAttrs(md), 'legacyattrs', 15)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/meta.py b/markdown/extensions/meta.py
index 2c2c8e3..27adcb2 100644
--- a/markdown/extensions/meta.py
+++ b/markdown/extensions/meta.py
@@ -38,9 +38,7 @@ class MetaExtension (Extension):
         """ Add MetaPreprocessor to Markdown instance. """
         md.registerExtension(self)
         self.md = md
-        md.preprocessors.add("meta",
-                             MetaPreprocessor(md),
-                             ">normalize_whitespace")
+        md.preprocessors.register(MetaPreprocessor(md), 'meta', 27)
 
     def reset(self):
         self.md.Meta = {}
diff --git a/markdown/extensions/nl2br.py b/markdown/extensions/nl2br.py
index 5b9373f..d334b02 100644
--- a/markdown/extensions/nl2br.py
+++ b/markdown/extensions/nl2br.py
@@ -28,7 +28,7 @@ class Nl2BrExtension(Extension):
 
     def extendMarkdown(self, md, md_globals):
         br_tag = SubstituteTagInlineProcessor(BR_RE, 'br')
-        md.inlinePatterns.add('nl', br_tag, '_end')
+        md.inlinePatterns.register(br_tag, 'nl', 5)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/sane_lists.py b/markdown/extensions/sane_lists.py
index 89f929f..7fb4fd6 100644
--- a/markdown/extensions/sane_lists.py
+++ b/markdown/extensions/sane_lists.py
@@ -47,8 +47,8 @@ class SaneListExtension(Extension):
 
     def extendMarkdown(self, md, md_globals):
         """ Override existing Processors. """
-        md.parser.blockprocessors['olist'] = SaneOListProcessor(md.parser)
-        md.parser.blockprocessors['ulist'] = SaneUListProcessor(md.parser)
+        md.parser.blockprocessors.register(SaneOListProcessor(md.parser), 'olist', 40)
+        md.parser.blockprocessors.register(SaneUListProcessor(md.parser), 'ulist', 30)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/smart_strong.py b/markdown/extensions/smart_strong.py
index f34531d..e7a15d9 100644
--- a/markdown/extensions/smart_strong.py
+++ b/markdown/extensions/smart_strong.py
@@ -29,12 +29,8 @@ class SmartEmphasisExtension(Extension):
 
     def extendMarkdown(self, md, md_globals):
         """ Modify inline patterns. """
-        md.inlinePatterns['strong'] = SimpleTagInlineProcessor(STRONG_RE, 'strong')
-        md.inlinePatterns.add(
-            'strong2',
-            SimpleTagInlineProcessor(SMART_STRONG_RE, 'strong'),
-            '>emphasis2'
-        )
+        md.inlinePatterns.register(SimpleTagInlineProcessor(STRONG_RE, 'strong'), 'strong', 40)
+        md.inlinePatterns.register(SimpleTagInlineProcessor(SMART_STRONG_RE, 'strong'), 'strong2', 10)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/smarty.py b/markdown/extensions/smarty.py
index 189651f..d25620b 100644
--- a/markdown/extensions/smarty.py
+++ b/markdown/extensions/smarty.py
@@ -84,8 +84,8 @@ smartypants.py license:
 from __future__ import unicode_literals
 from . import Extension
 from ..inlinepatterns import HtmlInlineProcessor, HTML_RE
-from ..odict import OrderedDict
 from ..treeprocessors import InlineProcessor
+from ..util import Registry
 
 
 # Constants for quote education.
@@ -180,13 +180,12 @@ class SmartyExtension(Extension):
         self.substitutions = dict(substitutions)
         self.substitutions.update(self.getConfig('substitutions', default={}))
 
-    def _addPatterns(self, md, patterns, serie):
+    def _addPatterns(self, md, patterns, serie, priority):
         for ind, pattern in enumerate(patterns):
             pattern += (md,)
             pattern = SubstituteTextPattern(*pattern)
-            after = ('>smarty-%s-%d' % (serie, ind - 1) if ind else '_begin')
             name = 'smarty-%s-%d' % (serie, ind)
-            self.inlinePatterns.add(name, pattern, after)
+            self.inlinePatterns.register(pattern, name, priority-ind)
 
     def educateDashes(self, md):
         emDashesPattern = SubstituteTextPattern(
@@ -195,16 +194,14 @@ class SmartyExtension(Extension):
         enDashesPattern = SubstituteTextPattern(
             r'(?<!-)--(?!-)', (self.substitutions['ndash'],), md
         )
-        self.inlinePatterns.add('smarty-em-dashes', emDashesPattern, '_begin')
-        self.inlinePatterns.add(
-            'smarty-en-dashes', enDashesPattern, '>smarty-em-dashes'
-        )
+        self.inlinePatterns.register(emDashesPattern, 'smarty-em-dashes', 50)
+        self.inlinePatterns.register(enDashesPattern, 'smarty-en-dashes', 45)
 
     def educateEllipses(self, md):
         ellipsesPattern = SubstituteTextPattern(
             r'(?<!\.)\.{3}(?!\.)', (self.substitutions['ellipsis'],), md
         )
-        self.inlinePatterns.add('smarty-ellipses', ellipsesPattern, '_begin')
+        self.inlinePatterns.register(ellipsesPattern, 'smarty-ellipses', 10)
 
     def educateAngledQuotes(self, md):
         leftAngledQuotePattern = SubstituteTextPattern(
@@ -213,14 +210,8 @@ class SmartyExtension(Extension):
         rightAngledQuotePattern = SubstituteTextPattern(
             r'\>\>', (self.substitutions['right-angle-quote'],), md
         )
-        self.inlinePatterns.add(
-            'smarty-left-angle-quotes', leftAngledQuotePattern, '_begin'
-        )
-        self.inlinePatterns.add(
-            'smarty-right-angle-quotes',
-            rightAngledQuotePattern,
-            '>smarty-left-angle-quotes'
-        )
+        self.inlinePatterns.register(leftAngledQuotePattern, 'smarty-left-angle-quotes', 40)
+        self.inlinePatterns.register(rightAngledQuotePattern, 'smarty-right-angle-quotes', 35)
 
     def educateQuotes(self, md):
         lsquo = self.substitutions['left-single-quote']
@@ -242,11 +233,11 @@ class SmartyExtension(Extension):
             (closingDoubleQuotesRegex2, (rdquo,)),
             (remainingDoubleQuotesRegex, (ldquo,))
         )
-        self._addPatterns(md, patterns, 'quotes')
+        self._addPatterns(md, patterns, 'quotes', 30)
 
     def extendMarkdown(self, md, md_globals):
         configs = self.getConfigs()
-        self.inlinePatterns = OrderedDict()
+        self.inlinePatterns = Registry()
         if configs['smart_ellipses']:
             self.educateEllipses(md)
         if configs['smart_quotes']:
@@ -255,12 +246,12 @@ class SmartyExtension(Extension):
             self.educateAngledQuotes(md)
             # Override HTML_RE from inlinepatterns.py so that it does not
             # process tags with duplicate closing quotes.
-            md.inlinePatterns["html"] = HtmlInlineProcessor(HTML_STRICT_RE, md)
+            md.inlinePatterns.register(HtmlInlineProcessor(HTML_STRICT_RE, md), 'html', 90)
         if configs['smart_dashes']:
             self.educateDashes(md)
         inlineProcessor = InlineProcessor(md)
         inlineProcessor.inlinePatterns = self.inlinePatterns
-        md.treeprocessors.add('smarty', inlineProcessor, '_end')
+        md.treeprocessors.register(inlineProcessor, 'smarty', 2)
         md.ESCAPED_CHARS.extend(['"', "'"])
 
 
diff --git a/markdown/extensions/tables.py b/markdown/extensions/tables.py
index b8218b0..0f221a6 100644
--- a/markdown/extensions/tables.py
+++ b/markdown/extensions/tables.py
@@ -218,9 +218,7 @@ class TableExtension(Extension):
         """ Add an instance of TableProcessor to BlockParser. """
         if '|' not in md.ESCAPED_CHARS:
             md.ESCAPED_CHARS.append('|')
-        md.parser.blockprocessors.add('table',
-                                      TableProcessor(md.parser),
-                                      '<hashheader')
+        md.parser.blockprocessors.register(TableProcessor(md.parser), 'table', 75)
 
 
 def makeExtension(**kwargs):  # pragma: no cover
diff --git a/markdown/extensions/toc.py b/markdown/extensions/toc.py
index 5783f3d..f5f2b2e 100644
--- a/markdown/extensions/toc.py
+++ b/markdown/extensions/toc.py
@@ -218,9 +218,10 @@ class TocTreeprocessor(Treeprocessor):
             return ul
 
         build_etree_ul(toc_list, div)
-        prettify = self.markdown.treeprocessors.get('prettify')
-        if prettify:
-            prettify.run(div)
+
+        if 'prettify' in self.markdown.treeprocessors:
+            self.markdown.treeprocessors['prettify'].run(div)
+
         return div
 
     def run(self, doc):
@@ -260,7 +261,7 @@ class TocTreeprocessor(Treeprocessor):
 
         # serialize and attach to markdown instance.
         toc = self.markdown.serializer(div)
-        for pp in self.markdown.postprocessors.values():
+        for pp in self.markdown.postprocessors:
             toc = pp.run(toc)
         self.markdown.toc = toc
 
@@ -305,7 +306,7 @@ class TocExtension(Extension):
         # by the header id extension) if both are used. Same goes for
         # attr_list extension. This must come last because we don't want
         # to redefine ids after toc is created. But we do want toc prettified.
-        md.treeprocessors.add("toc", tocext, "_end")
+        md.treeprocessors.register(tocext, 'toc', 5)
 
     def reset(self):
         self.md.toc = ''
diff --git a/markdown/extensions/wikilinks.py b/markdown/extensions/wikilinks.py
index b535d9c..603682f 100644
--- a/markdown/extensions/wikilinks.py
+++ b/markdown/extensions/wikilinks.py
@@ -48,7 +48,7 @@ class WikiLinkExtension(Extension):
         WIKILINK_RE = r'\[\[([\w0-9_ -]+)\]\]'
         wikilinkPattern = WikiLinksInlineProcessor(WIKILINK_RE, self.getConfigs())
         wikilinkPattern.md = md
-        md.inlinePatterns.add('wikilink', wikilinkPattern, "<not_strong")
+        md.inlinePatterns.register(wikilinkPattern, 'wikilink', 75)
 
 
 class WikiLinksInlineProcessor(InlineProcessor):