blackfriday/v2/node.go

package blackfriday

import (
        "bytes"
        "fmt"
)

// NodeType specifies a type of a single node of a syntax tree. Usually one
// node (and its type) corresponds to a single markdown feature, e.g. emphasis
// or code block.
type NodeType int

// Constants for identifying different types of nodes. See NodeType.
const (
        Document NodeType = iota
        BlockQuote
        List
        Item
        Paragraph
        Heading
        HorizontalRule
        Emph
        Strong
        Del
        Link
        Image
        Text
        HTMLBlock
        CodeBlock
        Softbreak
        Hardbreak
        Code
        HTMLSpan
        Table
        TableCell
        TableHead
        TableBody
        TableRow
)

var nodeTypeNames = []string{
        Document:       "Document",
        BlockQuote:     "BlockQuote",
        List:           "List",
        Item:           "Item",
        Paragraph:      "Paragraph",
        Heading:        "Heading",
        HorizontalRule: "HorizontalRule",
        Emph:           "Emph",
        Strong:         "Strong",
        Del:            "Del",
        Link:           "Link",
        Image:          "Image",
        Text:           "Text",
        HTMLBlock:      "HTMLBlock",
        CodeBlock:      "CodeBlock",
        Softbreak:      "Softbreak",
        Hardbreak:      "Hardbreak",
        Code:           "Code",
        HTMLSpan:       "HTMLSpan",
        Table:          "Table",
        TableCell:      "TableCell",
        TableHead:      "TableHead",
        TableBody:      "TableBody",
        TableRow:       "TableRow",
}

func (t NodeType) String() string {
        return nodeTypeNames[t]
}

// ListData contains fields relevant to a List and Item node type.
type ListData struct {
        ListFlags       ListType
        Tight           bool   // Skip <p>s around list item data if true
        BulletChar      byte   // '*', '+' or '-' in bullet lists
        Delimiter       byte   // '.' or ')' after the number in ordered lists
        RefLink         []byte // If not nil, turns this list item into a footnote item and triggers different rendering
        IsFootnotesList bool   // This is a list of footnotes
}

// LinkData contains fields relevant to a Link node type.
type LinkData struct {
        Destination []byte // Destination is what goes into a href
        Title       []byte // Title is the tooltip thing that goes in a title attribute
        NoteID      int    // NoteID contains a serial number of a footnote, zero if it's not a footnote
        Footnote    *Node  // If it's a footnote, this is a direct link to the footnote Node. Otherwise nil.
}

// CodeBlockData contains fields relevant to a CodeBlock node type.
type CodeBlockData struct {
        IsFenced    bool   // Specifies whether it's a fenced code block or an indented one
        Info        []byte // This holds the info string
        FenceChar   byte
        FenceLength int
        FenceOffset int
}

// TableCellData contains fields relevant to a TableCell node type.
type TableCellData struct {
        IsHeader bool           // This tells if it's under the header row
        Align    CellAlignFlags // This holds the value for align attribute
}

// HeadingData contains fields relevant to a Heading node type.
type HeadingData struct {
        Level        int    // This holds the heading level number
        HeadingID    string // This might hold heading ID, if present
        IsTitleblock bool   // Specifies whether it's a title block
}

// Node is a single element in the abstract syntax tree of the parsed document.
// It holds connections to the structurally neighboring nodes and, for certain
// types of nodes, additional information that might be needed when rendering.
type Node struct {
        Type       NodeType // Determines the type of the node
        Parent     *Node    // Points to the parent
        FirstChild *Node    // Points to the first child, if any
        LastChild  *Node    // Points to the last child, if any
        Prev       *Node    // Previous sibling; nil if it's the first child
        Next       *Node    // Next sibling; nil if it's the last child

        Literal []byte // Text contents of the leaf nodes

        HeadingData   // Populated if Type is Heading
        ListData      // Populated if Type is List
        CodeBlockData // Populated if Type is CodeBlock
        LinkData      // Populated if Type is Link
        TableCellData // Populated if Type is TableCell

        content []byte // Markdown content of the block nodes
        open    bool   // Specifies an open block node that has not been finished to process yet
}

// NewNode allocates a node of a specified type.
func NewNode(typ NodeType) *Node {
        return &Node{
                Type: typ,
                open: true,
        }
}

func (n *Node) String() string {
        ellipsis := ""
        snippet := n.Literal
        if len(snippet) > 16 {
                snippet = snippet[:16]
                ellipsis = "..."
        }
        return fmt.Sprintf("%s: '%s%s'", n.Type, snippet, ellipsis)
}

// Unlink removes node 'n' from the tree.
// It panics if the node is nil.
func (n *Node) Unlink() {
        if n.Prev != nil {
                n.Prev.Next = n.Next
        } else if n.Parent != nil {
                n.Parent.FirstChild = n.Next
        }
        if n.Next != nil {
                n.Next.Prev = n.Prev
        } else if n.Parent != nil {
                n.Parent.LastChild = n.Prev
        }
        n.Parent = nil
        n.Next = nil
        n.Prev = nil
}

// AppendChild adds a node 'child' as a child of 'n'.
// It panics if either node is nil.
func (n *Node) AppendChild(child *Node) {
        child.Unlink()
        child.Parent = n
        if n.LastChild != nil {
                n.LastChild.Next = child
                child.Prev = n.LastChild
                n.LastChild = child
        } else {
                n.FirstChild = child
                n.LastChild = child
        }
}

// InsertBefore inserts 'sibling' immediately before 'n'.
// It panics if either node is nil.
func (n *Node) InsertBefore(sibling *Node) {
        sibling.Unlink()
        sibling.Prev = n.Prev
        if sibling.Prev != nil {
                sibling.Prev.Next = sibling
        }
        sibling.Next = n
        n.Prev = sibling
        sibling.Parent = n.Parent
        if sibling.Prev == nil {
                sibling.Parent.FirstChild = sibling
        }
}

// IsContainer returns true if 'n' can contain children.
func (n *Node) IsContainer() bool {
        switch n.Type {
        case Document:
                fallthrough
        case BlockQuote:
                fallthrough
        case List:
                fallthrough
        case Item:
                fallthrough
        case Paragraph:
                fallthrough
        case Heading:
                fallthrough
        case Emph:
                fallthrough
        case Strong:
                fallthrough
        case Del:
                fallthrough
        case Link:
                fallthrough
        case Image:
                fallthrough
        case Table:
                fallthrough
        case TableHead:
                fallthrough
        case TableBody:
                fallthrough
        case TableRow:
                fallthrough
        case TableCell:
                return true
        default:
                return false
        }
}

// IsLeaf returns true if 'n' is a leaf node.
func (n *Node) IsLeaf() bool {
        return !n.IsContainer()
}

func (n *Node) canContain(t NodeType) bool {
        if n.Type == List {
                return t == Item
        }
        if n.Type == Document || n.Type == BlockQuote || n.Type == Item {
                return t != Item
        }
        if n.Type == Table {
                return t == TableHead || t == TableBody
        }
        if n.Type == TableHead || n.Type == TableBody {
                return t == TableRow
        }
        if n.Type == TableRow {
                return t == TableCell
        }
        return false
}

// WalkStatus allows NodeVisitor to have some control over the tree traversal.
// It is returned from NodeVisitor and different values allow Node.Walk to
// decide which node to go to next.
type WalkStatus int

const (
        // GoToNext is the default traversal of every node.
        GoToNext WalkStatus = iota
        // SkipChildren tells walker to skip all children of current node.
        SkipChildren
        // Terminate tells walker to terminate the traversal.
        Terminate
)

// NodeVisitor is a callback to be called when traversing the syntax tree.
// Called twice for every node: once with entering=true when the branch is
// first visited, then with entering=false after all the children are done.
type NodeVisitor func(node *Node, entering bool) WalkStatus

// Walk is a convenience method that instantiates a walker and starts a
// traversal of subtree rooted at n.
func (n *Node) Walk(visitor NodeVisitor) {
        w := newNodeWalker(n)
        for w.current != nil {
                status := visitor(w.current, w.entering)
                switch status {
                case GoToNext:
                        w.next()
                case SkipChildren:
                        w.entering = false
                        w.next()
                case Terminate:
                        return
                }
        }
}

type nodeWalker struct {
        current  *Node
        root     *Node
        entering bool
}

func newNodeWalker(root *Node) *nodeWalker {
        return &nodeWalker{
                current:  root,
                root:     root,
                entering: true,
        }
}

func (nw *nodeWalker) next() {
        if (!nw.current.IsContainer() || !nw.entering) && nw.current == nw.root {
                nw.current = nil
                return
        }
        if nw.entering && nw.current.IsContainer() {
                if nw.current.FirstChild != nil {
                        nw.current = nw.current.FirstChild
                        nw.entering = true
                } else {
                        nw.entering = false
                }
        } else if nw.current.Next == nil {
                nw.current = nw.current.Parent
                nw.entering = false
        } else {
                nw.current = nw.current.Next
                nw.entering = true
        }
}

func dump(ast *Node) {
        fmt.Println(dumpString(ast))
}

func dumpR(ast *Node, depth int) string {
        if ast == nil {
                return ""
        }
        indent := bytes.Repeat([]byte("\t"), depth)
        content := ast.Literal
        if content == nil {
                content = ast.content
        }
        result := fmt.Sprintf("%s%s(%q)\n", indent, ast.Type, content)
        for n := ast.FirstChild; n != nil; n = n.Next {
                result += dumpR(n, depth+1)
        }
        return result
}

func dumpString(ast *Node) string {
        return dumpR(ast, 0)
}
1	package blackfriday
2
3	import (
4	"bytes"
5	"fmt"
6	)
7
8	// NodeType specifies a type of a single node of a syntax tree. Usually one
9	// node (and its type) corresponds to a single markdown feature, e.g. emphasis
10	// or code block.
11	type NodeType int
12
13	// Constants for identifying different types of nodes. See NodeType.
14	const (
15	Document NodeType = iota
16	BlockQuote
17	List
18	Item
19	Paragraph
20	Heading
21	HorizontalRule
22	Emph
23	Strong
24	Del
25	Link
26	Image
27	Text
28	HTMLBlock
29	CodeBlock
30	Softbreak
31	Hardbreak
32	Code
33	HTMLSpan
34	Table
35	TableCell
36	TableHead
37	TableBody
38	TableRow
39	)
40
41	var nodeTypeNames = []string{
42	Document: "Document",
43	BlockQuote: "BlockQuote",
44	List: "List",
45	Item: "Item",
46	Paragraph: "Paragraph",
47	Heading: "Heading",
48	HorizontalRule: "HorizontalRule",
49	Emph: "Emph",
50	Strong: "Strong",
51	Del: "Del",
52	Link: "Link",
53	Image: "Image",
54	Text: "Text",
55	HTMLBlock: "HTMLBlock",
56	CodeBlock: "CodeBlock",
57	Softbreak: "Softbreak",
58	Hardbreak: "Hardbreak",
59	Code: "Code",
60	HTMLSpan: "HTMLSpan",
61	Table: "Table",
62	TableCell: "TableCell",
63	TableHead: "TableHead",
64	TableBody: "TableBody",
65	TableRow: "TableRow",
66	}
67
68	func (t NodeType) String() string {
69	return nodeTypeNames[t]
70	}
71
72	// ListData contains fields relevant to a List and Item node type.
73	type ListData struct {
74	ListFlags ListType
75	Tight bool // Skip <p>s around list item data if true
76	BulletChar byte // '*', '+' or '-' in bullet lists
77	Delimiter byte // '.' or ')' after the number in ordered lists
78	RefLink []byte // If not nil, turns this list item into a footnote item and triggers different rendering
79	IsFootnotesList bool // This is a list of footnotes
80	}
81
82	// LinkData contains fields relevant to a Link node type.
83	type LinkData struct {
84	Destination []byte // Destination is what goes into a href
85	Title []byte // Title is the tooltip thing that goes in a title attribute
86	NoteID int // NoteID contains a serial number of a footnote, zero if it's not a footnote
87	Footnote *Node // If it's a footnote, this is a direct link to the footnote Node. Otherwise nil.
88	}
89
90	// CodeBlockData contains fields relevant to a CodeBlock node type.
91	type CodeBlockData struct {
92	IsFenced bool // Specifies whether it's a fenced code block or an indented one
93	Info []byte // This holds the info string
94	FenceChar byte
95	FenceLength int
96	FenceOffset int
97	}
98
99	// TableCellData contains fields relevant to a TableCell node type.
100	type TableCellData struct {
101	IsHeader bool // This tells if it's under the header row
102	Align CellAlignFlags // This holds the value for align attribute
103	}
104
105	// HeadingData contains fields relevant to a Heading node type.
106	type HeadingData struct {
107	Level int // This holds the heading level number
108	HeadingID string // This might hold heading ID, if present
109	IsTitleblock bool // Specifies whether it's a title block
110	}
111
112	// Node is a single element in the abstract syntax tree of the parsed document.
113	// It holds connections to the structurally neighboring nodes and, for certain
114	// types of nodes, additional information that might be needed when rendering.
115	type Node struct {
116	Type NodeType // Determines the type of the node
117	Parent *Node // Points to the parent
118	FirstChild *Node // Points to the first child, if any
119	LastChild *Node // Points to the last child, if any
120	Prev *Node // Previous sibling; nil if it's the first child
121	Next *Node // Next sibling; nil if it's the last child
122
123	Literal []byte // Text contents of the leaf nodes
124
125	HeadingData // Populated if Type is Heading
126	ListData // Populated if Type is List
127	CodeBlockData // Populated if Type is CodeBlock
128	LinkData // Populated if Type is Link
129	TableCellData // Populated if Type is TableCell
130
131	content []byte // Markdown content of the block nodes
132	open bool // Specifies an open block node that has not been finished to process yet
133	}
134
135	// NewNode allocates a node of a specified type.
136	func NewNode(typ NodeType) *Node {
137	return &Node{
138	Type: typ,
139	open: true,
140	}
141	}
142
143	func (n *Node) String() string {
144	ellipsis := ""
145	snippet := n.Literal
146	if len(snippet) > 16 {
147	snippet = snippet[:16]
148	ellipsis = "..."
149	}
150	return fmt.Sprintf("%s: '%s%s'", n.Type, snippet, ellipsis)
151	}
152
153	// Unlink removes node 'n' from the tree.
154	// It panics if the node is nil.
155	func (n *Node) Unlink() {
156	if n.Prev != nil {
157	n.Prev.Next = n.Next
158	} else if n.Parent != nil {
159	n.Parent.FirstChild = n.Next
160	}
161	if n.Next != nil {
162	n.Next.Prev = n.Prev
163	} else if n.Parent != nil {
164	n.Parent.LastChild = n.Prev
165	}
166	n.Parent = nil
167	n.Next = nil
168	n.Prev = nil
169	}
170
171	// AppendChild adds a node 'child' as a child of 'n'.
172	// It panics if either node is nil.
173	func (n Node) AppendChild(child Node) {
174	child.Unlink()
175	child.Parent = n
176	if n.LastChild != nil {
177	n.LastChild.Next = child
178	child.Prev = n.LastChild
179	n.LastChild = child
180	} else {
181	n.FirstChild = child
182	n.LastChild = child
183	}
184	}
185
186	// InsertBefore inserts 'sibling' immediately before 'n'.
187	// It panics if either node is nil.
188	func (n Node) InsertBefore(sibling Node) {
189	sibling.Unlink()
190	sibling.Prev = n.Prev
191	if sibling.Prev != nil {
192	sibling.Prev.Next = sibling
193	}
194	sibling.Next = n
195	n.Prev = sibling
196	sibling.Parent = n.Parent
197	if sibling.Prev == nil {
198	sibling.Parent.FirstChild = sibling
199	}
200	}
201
202	// IsContainer returns true if 'n' can contain children.
203	func (n *Node) IsContainer() bool {
204	switch n.Type {
205	case Document:
206	fallthrough
207	case BlockQuote:
208	fallthrough
209	case List:
210	fallthrough
211	case Item:
212	fallthrough
213	case Paragraph:
214	fallthrough
215	case Heading:
216	fallthrough
217	case Emph:
218	fallthrough
219	case Strong:
220	fallthrough
221	case Del:
222	fallthrough
223	case Link:
224	fallthrough
225	case Image:
226	fallthrough
227	case Table:
228	fallthrough
229	case TableHead:
230	fallthrough
231	case TableBody:
232	fallthrough
233	case TableRow:
234	fallthrough
235	case TableCell:
236	return true
237	default:
238	return false
239	}
240	}
241
242	// IsLeaf returns true if 'n' is a leaf node.
243	func (n *Node) IsLeaf() bool {
244	return !n.IsContainer()
245	}
246
247	func (n *Node) canContain(t NodeType) bool {
248	if n.Type == List {
249	return t == Item
250	}
251	if n.Type == Document \|\| n.Type == BlockQuote \|\| n.Type == Item {
252	return t != Item
253	}
254	if n.Type == Table {
255	return t == TableHead \|\| t == TableBody
256	}
257	if n.Type == TableHead \|\| n.Type == TableBody {
258	return t == TableRow
259	}
260	if n.Type == TableRow {
261	return t == TableCell
262	}
263	return false
264	}
265
266	// WalkStatus allows NodeVisitor to have some control over the tree traversal.
267	// It is returned from NodeVisitor and different values allow Node.Walk to
268	// decide which node to go to next.
269	type WalkStatus int
270
271	const (
272	// GoToNext is the default traversal of every node.
273	GoToNext WalkStatus = iota
274	// SkipChildren tells walker to skip all children of current node.
275	SkipChildren
276	// Terminate tells walker to terminate the traversal.
277	Terminate
278	)
279
280	// NodeVisitor is a callback to be called when traversing the syntax tree.
281	// Called twice for every node: once with entering=true when the branch is
282	// first visited, then with entering=false after all the children are done.
283	type NodeVisitor func(node *Node, entering bool) WalkStatus
284
285	// Walk is a convenience method that instantiates a walker and starts a
286	// traversal of subtree rooted at n.
287	func (n *Node) Walk(visitor NodeVisitor) {
288	w := newNodeWalker(n)
289	for w.current != nil {
290	status := visitor(w.current, w.entering)
291	switch status {
292	case GoToNext:
293	w.next()
294	case SkipChildren:
295	w.entering = false
296	w.next()
297	case Terminate:
298	return
299	}
300	}
301	}
302
303	type nodeWalker struct {
304	current *Node
305	root *Node
306	entering bool
307	}
308
309	func newNodeWalker(root Node) nodeWalker {
310	return &nodeWalker{
311	current: root,
312	root: root,
313	entering: true,
314	}
315	}
316
317	func (nw *nodeWalker) next() {
318	if (!nw.current.IsContainer() \|\| !nw.entering) && nw.current == nw.root {
319	nw.current = nil
320	return
321	}
322	if nw.entering && nw.current.IsContainer() {
323	if nw.current.FirstChild != nil {
324	nw.current = nw.current.FirstChild
325	nw.entering = true
326	} else {
327	nw.entering = false
328	}
329	} else if nw.current.Next == nil {
330	nw.current = nw.current.Parent
331	nw.entering = false
332	} else {
333	nw.current = nw.current.Next
334	nw.entering = true
335	}
336	}
337
338	func dump(ast *Node) {
339	fmt.Println(dumpString(ast))
340	}
341
342	func dumpR(ast *Node, depth int) string {
343	if ast == nil {
344	return ""
345	}
346	indent := bytes.Repeat([]byte("\t"), depth)
347	content := ast.Literal
348	if content == nil {
349	content = ast.content
350	}
351	result := fmt.Sprintf("%s%s(%q)\n", indent, ast.Type, content)
352	for n := ast.FirstChild; n != nil; n = n.Next {
353	result += dumpR(n, depth+1)
354	}
355	return result
356	}
357
358	func dumpString(ast *Node) string {
359	return dumpR(ast, 0)
360	}
nishi@chaotic.ninja	ViewVC Help
Powered by ViewVC 1.3.0-dev