New upstream version 8.1.2.upstream/8.1.2

1 files changed, 274 insertions, 0 deletions

diff --git a/nikola/hierarchy_utils.py b/nikola/hierarchy_utils.py
new file mode 100644
index 0000000..8993518
--- /dev/null
+++ b/nikola/hierarchy_utils.py
@@ -0,0 +1,274 @@
+# -*- coding: utf-8 -*-
+
+# Copyright © 2012-2020 Roberto Alsina and others.
+
+# Permission is hereby granted, free of charge, to any
+# person obtaining a copy of this software and associated
+# documentation files (the "Software"), to deal in the
+# Software without restriction, including without limitation
+# the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the
+# Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice
+# shall be included in all copies or substantial portions of
+# the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
+# KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
+# WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
+# PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS
+# OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+"""Hierarchy utility functions."""
+
+import natsort
+
+__all__ = ('TreeNode', 'clone_treenode', 'flatten_tree_structure',
+           'sort_classifications', 'join_hierarchical_category_path',
+           'parse_escaped_hierarchical_category_name',)
+
+
+class TreeNode(object):
+    """A tree node."""
+
+    indent_levels = None  # use for formatting comments as tree
+    indent_change_before = 0  # use for formatting comments as tree
+    indent_change_after = 0  # use for formatting comments as tree
+
+    # The indent levels and changes allow to render a tree structure
+    # without keeping track of all that information during rendering.
+    #
+    # The indent_change_before is the different between the current
+    # comment's level and the previous comment's level; if the number
+    # is positive, the current level is indented further in, and if it
+    # is negative, it is indented further out. Positive values can be
+    # used to open HTML tags for each opened level.
+    #
+    # The indent_change_after is the difference between the next
+    # comment's level and the current comment's level. Negative values
+    # can be used to close HTML tags for each closed level.
+    #
+    # The indent_levels list contains one entry (index, count) per
+    # level, informing about the index of the current comment on that
+    # level and the count of comments on that level (before a comment
+    # of a higher level comes). This information can be used to render
+    # tree indicators, for example to generate a tree such as:
+    #
+    # +--- [(0,3)]
+    # +-+- [(1,3)]
+    # | +--- [(1,3), (0,2)]
+    # | +-+- [(1,3), (1,2)]
+    # |   +--- [(1,3), (1,2), (0, 1)]
+    # +-+- [(2,3)]
+    #   +- [(2,3), (0,1)]
+    #
+    # (The lists used as labels represent the content of the
+    # indent_levels property for that node.)
+
+    def __init__(self, name, parent=None):
+        """Initialize node."""
+        self.name = name
+        self.parent = parent
+        self.children = []
+
+    def get_path(self):
+        """Get path."""
+        path = []
+        curr = self
+        while curr is not None:
+            path.append(curr)
+            curr = curr.parent
+        return reversed(path)
+
+    def get_children(self):
+        """Get children of a node."""
+        return self.children
+
+    def __str__(self):
+        """Stringify node (return name)."""
+        return self.name
+
+    def _repr_partial(self):
+        """Return partial representation."""
+        if self.parent:
+            return "{0}/{1!r}".format(self.parent._repr_partial(), self.name)
+        else:
+            return repr(self.name)
+
+    def __repr__(self):
+        """Return programmer-friendly node representation."""
+        return "<TreeNode {0}>".format(self._repr_partial())
+
+
+def clone_treenode(treenode, parent=None, acceptor=lambda x: True):
+    """Clone a TreeNode.
+
+    Children are only cloned if `acceptor` returns `True` when
+    applied on them.
+
+    Returns the cloned node if it has children or if `acceptor`
+    applied to it returns `True`. In case neither applies, `None`
+    is returned.
+    """
+    # Copy standard TreeNode stuff
+    node_clone = TreeNode(treenode.name, parent)
+    node_clone.children = [clone_treenode(node, parent=node_clone, acceptor=acceptor) for node in treenode.children]
+    node_clone.children = [node for node in node_clone.children if node]
+    node_clone.indent_levels = treenode.indent_levels
+    node_clone.indent_change_before = treenode.indent_change_before
+    node_clone.indent_change_after = treenode.indent_change_after
+    if hasattr(treenode, 'classification_path'):
+        # Copy stuff added by taxonomies_classifier plugin
+        node_clone.classification_path = treenode.classification_path
+        node_clone.classification_name = treenode.classification_name
+
+    # Accept this node if there are no children (left) and acceptor fails
+    if not node_clone.children and not acceptor(treenode):
+        return None
+    return node_clone
+
+
+def flatten_tree_structure(root_list):
+    """Flatten a tree."""
+    elements = []
+
+    def generate(input_list, indent_levels_so_far):
+        """Generate flat list of nodes."""
+        for index, element in enumerate(input_list):
+            # add to destination
+            elements.append(element)
+            # compute and set indent levels
+            indent_levels = indent_levels_so_far + [(index, len(input_list))]
+            element.indent_levels = indent_levels
+            # add children
+            children = element.get_children()
+            element.children_count = len(children)
+            generate(children, indent_levels)
+
+    generate(root_list, [])
+    # Add indent change counters
+    level = 0
+    last_element = None
+    for element in elements:
+        new_level = len(element.indent_levels)
+        # Compute level change before this element
+        change = new_level - level
+        if last_element is not None:
+            last_element.indent_change_after = change
+        element.indent_change_before = change
+        # Update variables
+        level = new_level
+        last_element = element
+    # Set level change after last element
+    if last_element is not None:
+        last_element.indent_change_after = -level
+    return elements
+
+
+def parse_escaped_hierarchical_category_name(category_name):
+    """Parse a category name."""
+    result = []
+    current = None
+    index = 0
+    next_backslash = category_name.find('\\', index)
+    next_slash = category_name.find('/', index)
+    while index < len(category_name):
+        if next_backslash == -1 and next_slash == -1:
+            current = (current if current else "") + category_name[index:]
+            index = len(category_name)
+        elif next_slash >= 0 and (next_backslash == -1 or next_backslash > next_slash):
+            result.append((current if current else "") + category_name[index:next_slash])
+            current = ''
+            index = next_slash + 1
+            next_slash = category_name.find('/', index)
+        else:
+            if len(category_name) == next_backslash + 1:
+                raise Exception("Unexpected '\\' in '{0}' at last position!".format(category_name))
+            esc_ch = category_name[next_backslash + 1]
+            if esc_ch not in {'/', '\\'}:
+                raise Exception("Unknown escape sequence '\\{0}' in '{1}'!".format(esc_ch, category_name))
+            current = (current if current else "") + category_name[index:next_backslash] + esc_ch
+            index = next_backslash + 2
+            next_backslash = category_name.find('\\', index)
+            if esc_ch == '/':
+                next_slash = category_name.find('/', index)
+    if current is not None:
+        result.append(current)
+    return result
+
+
+def join_hierarchical_category_path(category_path):
+    """Join a category path."""
+    def escape(s):
+        """Espace one part of category path."""
+        return s.replace('\\', '\\\\').replace('/', '\\/')
+
+    return '/'.join([escape(p) for p in category_path])
+
+
+def sort_classifications(taxonomy, classifications, lang):
+    """Sort the given list of classifications of the given taxonomy and language.
+
+    ``taxonomy`` must be a ``Taxonomy`` plugin.
+    ``classifications`` must be an iterable collection of
+    classification strings for that taxonomy.
+    ``lang`` is the language the classifications are for.
+
+    The result will be returned as a sorted list. Sorting will
+    happen according to the way the complete classification
+    hierarchy for the taxonomy is sorted.
+    """
+    if taxonomy.has_hierarchy:
+        # To sort a hierarchy of classifications correctly, we first
+        # build a tree out of them (and mark for each node whether it
+        # appears in the list), then sort the tree node-wise, and finally
+        # collapse the tree into a list of recombined classifications.
+
+        # Step 1: build hierarchy. Here, each node consists of a boolean
+        # flag (node appears in list) and a dictionary mapping path elements
+        # to nodes.
+        root = [False, {}]
+        for classification in classifications:
+            node = root
+            for elt in taxonomy.extract_hierarchy(classification):
+                if elt not in node[1]:
+                    node[1][elt] = [False, {}]
+                node = node[1][elt]
+            node[0] = True
+        # Step 2: sort hierarchy. The result for a node is a pair
+        # (flag, subnodes), where subnodes is a list of pairs (name, subnode).
+
+        def sort_node(node, level=0):
+            """Return sorted node, with children as `(name, node)` list instead of a dictionary."""
+            keys = natsort.natsorted(node[1].keys(), alg=natsort.ns.F | natsort.ns.IC)
+            taxonomy.sort_classifications(keys, lang, level)
+            subnodes = []
+            for key in keys:
+                subnodes.append((key, sort_node(node[1][key], level + 1)))
+            return (node[0], subnodes)
+
+        root = sort_node(root)
+        # Step 3: collapse the tree structure into a linear sorted list,
+        # with a node coming before its children.
+
+        def append_node(classifications, node, path=()):
+            """Append the node and then its children to the classifications list."""
+            if node[0]:
+                classifications.append(taxonomy.recombine_classification_from_hierarchy(path))
+            for key, subnode in node[1]:
+                append_node(classifications, subnode, path + (key, ))
+
+        classifications = []
+        append_node(classifications, root)
+        return classifications
+    else:
+        # Sorting a flat hierarchy is simpler. We pre-sort with
+        # natsorted and call taxonomy.sort_classifications.
+        classifications = natsort.natsorted(classifications, alg=natsort.ns.F | natsort.ns.IC)
+        taxonomy.sort_classifications(classifications, lang)
+        return classifications