1package blackfriday 2 3import ( 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. 11type NodeType int 12 13// Constants for identifying different types of nodes. See NodeType. 14const ( 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 41var 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 68func (t NodeType) String() string { 69 return nodeTypeNames[t] 70} 71 72// ListData contains fields relevant to a List and Item node type. 73type 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. 83type 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. 91type 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. 100type 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. 106type 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. 115type 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. 136func NewNode(typ NodeType) *Node { 137 return &Node{ 138 Type: typ, 139 open: true, 140 } 141} 142 143func (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. 155func (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. 173func (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. 188func (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 202func (n *Node) isContainer() bool { 203 switch n.Type { 204 case Document: 205 fallthrough 206 case BlockQuote: 207 fallthrough 208 case List: 209 fallthrough 210 case Item: 211 fallthrough 212 case Paragraph: 213 fallthrough 214 case Heading: 215 fallthrough 216 case Emph: 217 fallthrough 218 case Strong: 219 fallthrough 220 case Del: 221 fallthrough 222 case Link: 223 fallthrough 224 case Image: 225 fallthrough 226 case Table: 227 fallthrough 228 case TableHead: 229 fallthrough 230 case TableBody: 231 fallthrough 232 case TableRow: 233 fallthrough 234 case TableCell: 235 return true 236 default: 237 return false 238 } 239} 240 241func (n *Node) canContain(t NodeType) bool { 242 if n.Type == List { 243 return t == Item 244 } 245 if n.Type == Document || n.Type == BlockQuote || n.Type == Item { 246 return t != Item 247 } 248 if n.Type == Table { 249 return t == TableHead || t == TableBody 250 } 251 if n.Type == TableHead || n.Type == TableBody { 252 return t == TableRow 253 } 254 if n.Type == TableRow { 255 return t == TableCell 256 } 257 return false 258} 259 260// WalkStatus allows NodeVisitor to have some control over the tree traversal. 261// It is returned from NodeVisitor and different values allow Node.Walk to 262// decide which node to go to next. 263type WalkStatus int 264 265const ( 266 // GoToNext is the default traversal of every node. 267 GoToNext WalkStatus = iota 268 // SkipChildren tells walker to skip all children of current node. 269 SkipChildren 270 // Terminate tells walker to terminate the traversal. 271 Terminate 272) 273 274// NodeVisitor is a callback to be called when traversing the syntax tree. 275// Called twice for every node: once with entering=true when the branch is 276// first visited, then with entering=false after all the children are done. 277type NodeVisitor func(node *Node, entering bool) WalkStatus 278 279// Walk is a convenience method that instantiates a walker and starts a 280// traversal of subtree rooted at n. 281func (n *Node) Walk(visitor NodeVisitor) { 282 w := newNodeWalker(n) 283 for w.current != nil { 284 status := visitor(w.current, w.entering) 285 switch status { 286 case GoToNext: 287 w.next() 288 case SkipChildren: 289 w.entering = false 290 w.next() 291 case Terminate: 292 return 293 } 294 } 295} 296 297type nodeWalker struct { 298 current *Node 299 root *Node 300 entering bool 301} 302 303func newNodeWalker(root *Node) *nodeWalker { 304 return &nodeWalker{ 305 current: root, 306 root: root, 307 entering: true, 308 } 309} 310 311func (nw *nodeWalker) next() { 312 if (!nw.current.isContainer() || !nw.entering) && nw.current == nw.root { 313 nw.current = nil 314 return 315 } 316 if nw.entering && nw.current.isContainer() { 317 if nw.current.FirstChild != nil { 318 nw.current = nw.current.FirstChild 319 nw.entering = true 320 } else { 321 nw.entering = false 322 } 323 } else if nw.current.Next == nil { 324 nw.current = nw.current.Parent 325 nw.entering = false 326 } else { 327 nw.current = nw.current.Next 328 nw.entering = true 329 } 330} 331 332func dump(ast *Node) { 333 fmt.Println(dumpString(ast)) 334} 335 336func dumpR(ast *Node, depth int) string { 337 if ast == nil { 338 return "" 339 } 340 indent := bytes.Repeat([]byte("\t"), depth) 341 content := ast.Literal 342 if content == nil { 343 content = ast.content 344 } 345 result := fmt.Sprintf("%s%s(%q)\n", indent, ast.Type, content) 346 for n := ast.FirstChild; n != nil; n = n.Next { 347 result += dumpR(n, depth+1) 348 } 349 return result 350} 351 352func dumpString(ast *Node) string { 353 return dumpR(ast, 0) 354} 355