256
|
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 |
|
260
|
202 |
// IsContainer returns true if 'n' can contain children. |
|
203 |
func (n *Node) IsContainer() bool { |
256
|
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 |
|
260
|
242 |
// IsLeaf returns true if 'n' is a leaf node. |
|
243 |
func (n *Node) IsLeaf() bool { |
|
244 |
return !n.IsContainer() |
|
245 |
} |
|
246 |
|
256
|
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() { |
260
|
318 |
if (!nw.current.IsContainer() || !nw.entering) && nw.current == nw.root { |
256
|
319 |
nw.current = nil |
|
320 |
return |
|
321 |
} |
260
|
322 |
if nw.entering && nw.current.IsContainer() { |
256
|
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 |
} |