node.go

Documentation: github.com/russross/blackfriday/v2

     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  }
   361
View as plain text