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