1# markdown is released under the BSD license
2# Copyright 2007, 2008 The Python Markdown Project (v. 1.7 and later)
3# Copyright 2004, 2005, 2006 Yuri Takhteyev (v. 0.2-1.6b)
4# Copyright 2004 Manfred Stienstra (the original version)
5#
6# All rights reserved.
7#
8# Redistribution and use in source and binary forms, with or without
9# modification, are permitted provided that the following conditions are met:
10#
11# *   Redistributions of source code must retain the above copyright
12#     notice, this list of conditions and the following disclaimer.
13# *   Redistributions in binary form must reproduce the above copyright
14#     notice, this list of conditions and the following disclaimer in the
15#     documentation and/or other materials provided with the distribution.
16# *   Neither the name of the <organization> nor the
17#     names of its contributors may be used to endorse or promote products
18#     derived from this software without specific prior written permission.
19#
20# THIS SOFTWARE IS PROVIDED BY THE PYTHON MARKDOWN PROJECT ''AS IS'' AND ANY
21# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
22# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
23# DISCLAIMED. IN NO EVENT SHALL ANY CONTRIBUTORS TO THE PYTHON MARKDOWN PROJECT
24# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30# POSSIBILITY OF SUCH DAMAGE.
31
32
33"""
34Table of Contents Extension for Python-Markdown
35* * *
36
37(c) 2008 [Jack Miller](http://codezen.org)
38
39Dependencies:
40* [Markdown 2.1+](http://packages.python.org/Markdown/)
41
42"""
43
44from __future__ import absolute_import
45from __future__ import unicode_literals
46from . import Extension
47from ..treeprocessors import Treeprocessor
48from ..util import etree
49from .headerid import slugify, unique, itertext
50import re
51
52
53def order_toc_list(toc_list):
54    """Given an unsorted list with errors and skips, return a nested one.
55    [{'level': 1}, {'level': 2}]
56    =>
57    [{'level': 1, 'children': [{'level': 2, 'children': []}]}]
58
59    A wrong list is also converted:
60    [{'level': 2}, {'level': 1}]
61    =>
62    [{'level': 2, 'children': []}, {'level': 1, 'children': []}]
63    """
64
65    def build_correct(remaining_list, prev_elements=[{'level': 1000}]):
66
67        if not remaining_list:
68            return [], []
69
70        current = remaining_list.pop(0)
71        if not 'children' in current.keys():
72            current['children'] = []
73
74        if not prev_elements:
75            # This happens for instance with [8, 1, 1], ie. when some
76            # header level is outside a scope. We treat it as a
77            # top-level
78            next_elements, children = build_correct(remaining_list, [current])
79            current['children'].append(children)
80            return [current] + next_elements, []
81
82        prev_element = prev_elements.pop()
83        children = []
84        next_elements = []
85        # Is current part of the child list or next list?
86        if current['level'] > prev_element['level']:
87            #print "%d is a child of %d" % (current['level'], prev_element['level'])
88            prev_elements.append(prev_element)
89            prev_elements.append(current)
90            prev_element['children'].append(current)
91            next_elements2, children2 = build_correct(remaining_list, prev_elements)
92            children += children2
93            next_elements += next_elements2
94        else:
95            #print "%d is ancestor of %d" % (current['level'], prev_element['level'])
96            if not prev_elements:
97                #print "No previous elements, so appending to the next set"
98                next_elements.append(current)
99                prev_elements = [current]
100                next_elements2, children2 = build_correct(remaining_list, prev_elements)
101                current['children'].extend(children2)
102            else:
103                #print "Previous elements, comparing to those first"
104                remaining_list.insert(0, current)
105                next_elements2, children2 = build_correct(remaining_list, prev_elements)
106                children.extend(children2)
107            next_elements += next_elements2
108
109        return next_elements, children
110
111    ordered_list, __ = build_correct(toc_list)
112    return ordered_list
113
114
115class TocTreeprocessor(Treeprocessor):
116
117    # Iterator wrapper to get parent and child all at once
118    def iterparent(self, root):
119        for parent in root.getiterator():
120            for child in parent:
121                yield parent, child
122
123    def add_anchor(self, c, elem_id): #@ReservedAssignment
124        if self.use_anchors:
125            anchor = etree.Element("a")
126            anchor.text = c.text
127            anchor.attrib["href"] = "#" + elem_id
128            anchor.attrib["class"] = "toclink"
129            c.text = ""
130            for elem in c.getchildren():
131                anchor.append(elem)
132                c.remove(elem)
133            c.append(anchor)
134
135    def build_toc_etree(self, div, toc_list):
136        # Add title to the div
137        if self.config["title"]:
138            header = etree.SubElement(div, "span")
139            header.attrib["class"] = "toctitle"
140            header.text = self.config["title"]
141
142        def build_etree_ul(toc_list, parent):
143            ul = etree.SubElement(parent, "ul")
144            for item in toc_list:
145                # List item link, to be inserted into the toc div
146                li = etree.SubElement(ul, "li")
147                link = etree.SubElement(li, "a")
148                link.text = item.get('name', '')
149                link.attrib["href"] = '#' + item.get('id', '')
150                if item['children']:
151                    build_etree_ul(item['children'], li)
152            return ul
153
154        return build_etree_ul(toc_list, div)
155
156    def run(self, doc):
157
158        div = etree.Element("div")
159        div.attrib["class"] = "toc"
160        header_rgx = re.compile("[Hh][123456]")
161
162        self.use_anchors = self.config["anchorlink"] in [1, '1', True, 'True', 'true']
163
164        # Get a list of id attributes
165        used_ids = set()
166        for c in doc.getiterator():
167            if "id" in c.attrib:
168                used_ids.add(c.attrib["id"])
169
170        toc_list = []
171        marker_found = False
172        for (p, c) in self.iterparent(doc):
173            text = ''.join(itertext(c)).strip()
174            if not text:
175                continue
176
177            # To keep the output from screwing up the
178            # validation by putting a <div> inside of a <p>
179            # we actually replace the <p> in its entirety.
180            # We do not allow the marker inside a header as that
181            # would causes an enless loop of placing a new TOC
182            # inside previously generated TOC.
183            if c.text and c.text.strip() == self.config["marker"] and \
184               not header_rgx.match(c.tag) and c.tag not in ['pre', 'code']:
185                for i in range(len(p)):
186                    if p[i] == c:
187                        p[i] = div
188                        break
189                marker_found = True
190
191            if header_rgx.match(c.tag):
192
193                # Do not override pre-existing ids
194                if not "id" in c.attrib:
195                    elem_id = unique(self.config["slugify"](text, '-'), used_ids)
196                    c.attrib["id"] = elem_id
197                else:
198                    elem_id = c.attrib["id"]
199
200                tag_level = int(c.tag[-1])
201
202                toc_list.append({'level': tag_level,
203                    'id': elem_id,
204                    'name': text})
205
206                self.add_anchor(c, elem_id)
207
208        toc_list_nested = order_toc_list(toc_list)
209        self.build_toc_etree(div, toc_list_nested)
210        prettify = self.markdown.treeprocessors.get('prettify')
211        if prettify: prettify.run(div)
212        if not marker_found:
213            # serialize and attach to markdown instance.
214            toc = self.markdown.serializer(div)
215            for pp in self.markdown.postprocessors.values():
216                toc = pp.run(toc)
217            self.markdown.toc = toc
218
219
220class TocExtension(Extension):
221
222    TreeProcessorClass = TocTreeprocessor
223
224    def __init__(self, configs=[]):
225        self.config = { "marker" : ["[TOC]",
226                            "Text to find and replace with Table of Contents -"
227                            "Defaults to \"[TOC]\""],
228                        "slugify" : [slugify,
229                            "Function to generate anchors based on header text-"
230                            "Defaults to the headerid ext's slugify function."],
231                        "title" : [None,
232                            "Title to insert into TOC <div> - "
233                            "Defaults to None"],
234                        "anchorlink" : [0,
235                            "1 if header should be a self link"
236                            "Defaults to 0"]}
237
238        for key, value in configs:
239            self.setConfig(key, value)
240
241    def extendMarkdown(self, md, md_globals):
242        tocext = self.TreeProcessorClass(md)
243        tocext.config = self.getConfigs()
244        # Headerid ext is set to '>prettify'. With this set to '_end',
245        # it should always come after headerid ext (and honor ids assinged
246        # by the header id extension) if both are used. Same goes for
247        # attr_list extension. This must come last because we don't want
248        # to redefine ids after toc is created. But we do want toc prettified.
249        md.treeprocessors.add("toc", tocext, "_end")
250
251
252def makeExtension(configs={}):
253    return TocExtension(configs=configs)
254