Docserver: Support markdown for HTML content. Request thirdparty submission review.

third_party/markdown/odict.py

Index: third_party/markdown/odict.py
diff --git a/third_party/markdown/odict.py b/third_party/markdown/odict.py
new file mode 100644
index 0000000000000000000000000000000000000000..1bfca51d3cb136960d65f037240e94b83e381500
--- /dev/null
+++ b/third_party/markdown/odict.py
@@ -0,0 +1,226 @@
+# markdown is released under the BSD license
+# Copyright 2007, 2008 The Python Markdown Project (v. 1.7 and later)
+# Copyright 2004, 2005, 2006 Yuri Takhteyev (v. 0.2-1.6b)
+# Copyright 2004 Manfred Stienstra (the original version)
+# 
+# All rights reserved.
+# 
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are met:
+# 
+# *   Redistributions of source code must retain the above copyright
+#     notice, this list of conditions and the following disclaimer.
+# *   Redistributions in binary form must reproduce the above copyright
+#     notice, this list of conditions and the following disclaimer in the
+#     documentation and/or other materials provided with the distribution.
+# *   Neither the name of the <organization> nor the
+#     names of its contributors may be used to endorse or promote products
+#     derived from this software without specific prior written permission.
+# 
+# THIS SOFTWARE IS PROVIDED BY THE PYTHON MARKDOWN PROJECT ''AS IS'' AND ANY
+# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL ANY CONTRIBUTORS TO THE PYTHON MARKDOWN PROJECT
+# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+
+
+from __future__ import unicode_literals
+from __future__ import absolute_import
+from . import util
+
+from copy import deepcopy
+
+def iteritems_compat(d):
+    """Return an iterator over the (key, value) pairs of a dictionary.
+    Copied from `six` module."""
+    return iter(getattr(d, _iteritems)())
+
+class OrderedDict(dict):
+    """
+    A dictionary that keeps its keys in the order in which they're inserted.
+    
+    Copied from Django's SortedDict with some modifications.
+
+    """
+    def __new__(cls, *args, **kwargs):
+        instance = super(OrderedDict, cls).__new__(cls, *args, **kwargs)
+        instance.keyOrder = []
+        return instance
+
+    def __init__(self, data=None):
+        if data is None or isinstance(data, dict):
+            data = data or []
+            super(OrderedDict, self).__init__(data)
+            self.keyOrder = list(data) if data else []
+        else:
+            super(OrderedDict, self).__init__()
+            super_set = super(OrderedDict, self).__setitem__
+            for key, value in data:
+                # Take the ordering from first key
+                if key not in self:
+                    self.keyOrder.append(key)
+                # But override with last value in data (dict() does this)
+                super_set(key, value)
+
+    def __deepcopy__(self, memo):
+        return self.__class__([(key, deepcopy(value, memo))
+                               for key, value in self.items()])
+
+    def __copy__(self):
+        # The Python's default copy implementation will alter the state
+        # of self. The reason for this seems complex but is likely related to
+        # subclassing dict.
+        return self.copy()
+
+    def __setitem__(self, key, value):
+        if key not in self:
+            self.keyOrder.append(key)
+        super(OrderedDict, self).__setitem__(key, value)
+
+    def __delitem__(self, key):
+        super(OrderedDict, self).__delitem__(key)
+        self.keyOrder.remove(key)
+
+    def __iter__(self):
+        return iter(self.keyOrder)
+
+    def __reversed__(self):
+        return reversed(self.keyOrder)
+
+    def pop(self, k, *args):
+        result = super(OrderedDict, self).pop(k, *args)
+        try:
+            self.keyOrder.remove(k)
+        except ValueError:
+            # Key wasn't in the dictionary in the first place. No problem.
+            pass
+        return result
+
+    def popitem(self):
+        result = super(OrderedDict, self).popitem()
+        self.keyOrder.remove(result[0])
+        return result
+
+    def _iteritems(self):
+        for key in self.keyOrder:
+            yield key, self[key]
+
+    def _iterkeys(self):
+        for key in self.keyOrder:
+            yield key
+
+    def _itervalues(self):
+        for key in self.keyOrder:
+            yield self[key]
+
+    if util.PY3:
+        items = _iteritems
+        keys = _iterkeys
+        values = _itervalues
+    else:
+        iteritems = _iteritems
+        iterkeys = _iterkeys
+        itervalues = _itervalues
+
+        def items(self):
+            return [(k, self[k]) for k in self.keyOrder]
+
+        def keys(self):
+            return self.keyOrder[:]
+
+        def values(self):
+            return [self[k] for k in self.keyOrder]
+
+    def update(self, dict_):
+        for k, v in iteritems_compat(dict_):
+            self[k] = v
+
+    def setdefault(self, key, default):
+        if key not in self:
+            self.keyOrder.append(key)
+        return super(OrderedDict, self).setdefault(key, default)
+
+    def value_for_index(self, index):
+        """Returns the value of the item at the given zero-based index."""
+        return self[self.keyOrder[index]]
+
+    def insert(self, index, key, value):
+        """Inserts the key, value pair before the item with the given index."""
+        if key in self.keyOrder:
+            n = self.keyOrder.index(key)
+            del self.keyOrder[n]
+            if n < index:
+                index -= 1
+        self.keyOrder.insert(index, key)
+        super(OrderedDict, self).__setitem__(key, value)
+
+    def copy(self):
+        """Returns a copy of this object."""
+        # This way of initializing the copy means it works for subclasses, too.
+        return self.__class__(self)
+
+    def __repr__(self):
+        """
+        Replaces the normal dict.__repr__ with a version that returns the keys
+        in their Ordered order.
+        """
+        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in iteritems_compat(self)])
+
+    def clear(self):
+        super(OrderedDict, self).clear()
+        self.keyOrder = []
+
+    def index(self, key):
+        """ Return the index of a given key. """
+        try:
+            return self.keyOrder.index(key)
+        except ValueError:
+            raise ValueError("Element '%s' was not found in OrderedDict" % key)
+
+    def index_for_location(self, location):
+        """ Return index or None for a given location. """
+        if location == '_begin':
+            i = 0
+        elif location == '_end':
+            i = None
+        elif location.startswith('<') or location.startswith('>'):
+            i = self.index(location[1:])
+            if location.startswith('>'):
+                if i >= len(self):
+                    # last item
+                    i = None
+                else:
+                    i += 1
+        else:
+            raise ValueError('Not a valid location: "%s". Location key '
+                             'must start with a ">" or "<".' % location)
+        return i
+
+    def add(self, key, value, location):
+        """ Insert by key location. """
+        i = self.index_for_location(location)
+        if i is not None:
+            self.insert(i, key, value)
+        else:
+            self.__setitem__(key, value)
+
+    def link(self, key, location):
+        """ Change location of an existing item. """
+        n = self.keyOrder.index(key)
+        del self.keyOrder[n]
+        try:
+            i = self.index_for_location(location)
+            if i is not None:
+                self.keyOrder.insert(i, key)
+            else:
+                self.keyOrder.append(key)
+        except Exception as e:
+            # restore to prevent data loss and reraise
+            self.keyOrder.insert(n, key)
+            raise e