1package blackfriday
  2
  3import (
  4	"bytes"
  5	"fmt"
  6)
  7
  8type NodeType int
  9
 10const (
 11	Document NodeType = iota
 12	BlockQuote
 13	List
 14	Item
 15	Paragraph
 16	Header
 17	HorizontalRule
 18	Emph
 19	Strong
 20	Del
 21	Link
 22	Image
 23	Text
 24	HTMLBlock
 25	CodeBlock
 26	Softbreak
 27	Hardbreak
 28	Code
 29	HTMLSpan
 30	Table
 31	TableCell
 32	TableHead
 33	TableBody
 34	TableRow
 35)
 36
 37var nodeTypeNames = []string{
 38	Document:       "Document",
 39	BlockQuote:     "BlockQuote",
 40	List:           "List",
 41	Item:           "Item",
 42	Paragraph:      "Paragraph",
 43	Header:         "Header",
 44	HorizontalRule: "HorizontalRule",
 45	Emph:           "Emph",
 46	Strong:         "Strong",
 47	Del:            "Del",
 48	Link:           "Link",
 49	Image:          "Image",
 50	Text:           "Text",
 51	HTMLBlock:      "HTMLBlock",
 52	CodeBlock:      "CodeBlock",
 53	Softbreak:      "Softbreak",
 54	Hardbreak:      "Hardbreak",
 55	Code:           "Code",
 56	HTMLSpan:       "HTMLSpan",
 57	Table:          "Table",
 58	TableCell:      "TableCell",
 59	TableHead:      "TableHead",
 60	TableBody:      "TableBody",
 61	TableRow:       "TableRow",
 62}
 63
 64func (t NodeType) String() string {
 65	return nodeTypeNames[t]
 66}
 67
 68type ListData struct {
 69	ListFlags  ListType
 70	Tight      bool   // Skip <p>s around list item data if true
 71	BulletChar byte   // '*', '+' or '-' in bullet lists
 72	Delimiter  byte   // '.' or ')' after the number in ordered lists
 73	RefLink    []byte // If not nil, turns this list item into a footnote item and triggers different rendering
 74}
 75
 76type LinkData struct {
 77	Destination []byte
 78	Title       []byte
 79	NoteID      int
 80}
 81
 82type CodeBlockData struct {
 83	IsFenced    bool   // Specifies whether it's a fenced code block or an indented one
 84	Info        []byte // This holds the info string
 85	FenceChar   byte
 86	FenceLength uint32
 87	FenceOffset uint32
 88}
 89
 90type TableCellData struct {
 91	IsHeader bool           // This tells if it's under the header row
 92	Align    CellAlignFlags // This holds the value for align attribute
 93}
 94
 95type HeaderData struct {
 96	Level        uint32 // This holds the heading level number
 97	HeaderID     string // This might hold header ID, if present
 98	IsTitleblock bool   // Specifies whether it's a title block
 99}
100
101// Node is a single element in the abstract syntax tree of the parsed document.
102// It holds connections to the structurally neighboring nodes and, for certain
103// types of nodes, additional information that might be needed when rendering.
104type Node struct {
105	Type       NodeType // Determines the type of the node
106	Parent     *Node    // Points to the parent
107	FirstChild *Node    // Points to the first child, if any
108	LastChild  *Node    // Points to the last child, if any
109	Prev       *Node    // Previous sibling; nil if it's the first child
110	Next       *Node    // Next sibling; nil if it's the last child
111
112	Literal []byte // Text contents of the leaf nodes
113
114	HeaderData    // Populated if Type == Header
115	ListData      // Populated if Type == List
116	CodeBlockData // Populated if Type == CodeBlock
117	LinkData      // Populated if Type == Link
118	TableCellData // Populated if Type == TableCell
119
120	content []byte // Markdown content of the block nodes
121	open    bool   // Specifies an open block node that has not been finished to process yet
122}
123
124func NewNode(typ NodeType) *Node {
125	return &Node{
126		Type: typ,
127		open: true,
128	}
129}
130
131func (n *Node) unlink() {
132	if n.Prev != nil {
133		n.Prev.Next = n.Next
134	} else if n.Parent != nil {
135		n.Parent.FirstChild = n.Next
136	}
137	if n.Next != nil {
138		n.Next.Prev = n.Prev
139	} else if n.Parent != nil {
140		n.Parent.LastChild = n.Prev
141	}
142	n.Parent = nil
143	n.Next = nil
144	n.Prev = nil
145}
146
147func (n *Node) appendChild(child *Node) {
148	child.unlink()
149	child.Parent = n
150	if n.LastChild != nil {
151		n.LastChild.Next = child
152		child.Prev = n.LastChild
153		n.LastChild = child
154	} else {
155		n.FirstChild = child
156		n.LastChild = child
157	}
158}
159
160func (n *Node) isContainer() bool {
161	switch n.Type {
162	case Document:
163		fallthrough
164	case BlockQuote:
165		fallthrough
166	case List:
167		fallthrough
168	case Item:
169		fallthrough
170	case Paragraph:
171		fallthrough
172	case Header:
173		fallthrough
174	case Emph:
175		fallthrough
176	case Strong:
177		fallthrough
178	case Del:
179		fallthrough
180	case Link:
181		fallthrough
182	case Image:
183		fallthrough
184	case Table:
185		fallthrough
186	case TableHead:
187		fallthrough
188	case TableBody:
189		fallthrough
190	case TableRow:
191		fallthrough
192	case TableCell:
193		return true
194	default:
195		return false
196	}
197	return false
198}
199
200func (n *Node) canContain(t NodeType) bool {
201	if n.Type == List {
202		return t == Item
203	}
204	if n.Type == Document || n.Type == BlockQuote || n.Type == Item {
205		return t != Item
206	}
207	if n.Type == Table {
208		return t == TableHead || t == TableBody
209	}
210	if n.Type == TableHead || n.Type == TableBody {
211		return t == TableRow
212	}
213	if n.Type == TableRow {
214		return t == TableCell
215	}
216	return false
217}
218
219func (root *Node) Walk(visitor func(node *Node, entering bool)) {
220	walker := NewNodeWalker(root)
221	node, entering := walker.next()
222	for node != nil {
223		visitor(node, entering)
224		node, entering = walker.next()
225	}
226}
227
228type NodeWalker struct {
229	current  *Node
230	root     *Node
231	entering bool
232}
233
234func NewNodeWalker(root *Node) *NodeWalker {
235	return &NodeWalker{
236		current:  root,
237		root:     nil,
238		entering: true,
239	}
240}
241
242func (nw *NodeWalker) next() (*Node, bool) {
243	if nw.current == nil {
244		return nil, false
245	}
246	if nw.root == nil {
247		nw.root = nw.current
248		return nw.current, nw.entering
249	}
250	if nw.entering && nw.current.isContainer() {
251		if nw.current.FirstChild != nil {
252			nw.current = nw.current.FirstChild
253			nw.entering = true
254		} else {
255			nw.entering = false
256		}
257	} else if nw.current.Next == nil {
258		nw.current = nw.current.Parent
259		nw.entering = false
260	} else {
261		nw.current = nw.current.Next
262		nw.entering = true
263	}
264	if nw.current == nw.root {
265		return nil, false
266	}
267	return nw.current, nw.entering
268}
269
270func (nw *NodeWalker) resumeAt(node *Node, entering bool) {
271	nw.current = node
272	nw.entering = entering
273}
274
275func dump(ast *Node) {
276	fmt.Println(dumpString(ast))
277}
278
279func dump_r(ast *Node, depth int) string {
280	if ast == nil {
281		return ""
282	}
283	indent := bytes.Repeat([]byte("\t"), depth)
284	content := ast.Literal
285	if content == nil {
286		content = ast.content
287	}
288	result := fmt.Sprintf("%s%s(%q)\n", indent, ast.Type, content)
289	for n := ast.FirstChild; n != nil; n = n.Next {
290		result += dump_r(n, depth+1)
291	}
292	return result
293}
294
295func dumpString(ast *Node) string {
296	return dump_r(ast, 0)
297}