1// Package ast defines AST nodes that represent markdown elements.
  2package ast
  3
  4import (
  5	"bytes"
  6	"fmt"
  7	"strings"
  8
  9	textm "github.com/yuin/goldmark/text"
 10	"github.com/yuin/goldmark/util"
 11)
 12
 13// A NodeType indicates what type a node belongs to.
 14type NodeType int
 15
 16const (
 17	// TypeBlock indicates that a node is kind of block nodes.
 18	TypeBlock NodeType = iota + 1
 19	// TypeInline indicates that a node is kind of inline nodes.
 20	TypeInline
 21	// TypeDocument indicates that a node is kind of document nodes.
 22	TypeDocument
 23)
 24
 25// NodeKind indicates more specific type than NodeType.
 26type NodeKind int
 27
 28func (k NodeKind) String() string {
 29	return kindNames[k]
 30}
 31
 32var kindMax NodeKind
 33var kindNames = []string{""}
 34
 35// NewNodeKind returns a new Kind value.
 36func NewNodeKind(name string) NodeKind {
 37	kindMax++
 38	kindNames = append(kindNames, name)
 39	return kindMax
 40}
 41
 42// An Attribute is an attribute of the Node.
 43type Attribute struct {
 44	Name  []byte
 45	Value interface{}
 46}
 47
 48// A Node interface defines basic AST node functionalities.
 49type Node interface {
 50	// Type returns a type of this node.
 51	Type() NodeType
 52
 53	// Kind returns a kind of this node.
 54	Kind() NodeKind
 55
 56	// NextSibling returns a next sibling node of this node.
 57	NextSibling() Node
 58
 59	// PreviousSibling returns a previous sibling node of this node.
 60	PreviousSibling() Node
 61
 62	// Parent returns a parent node of this node.
 63	Parent() Node
 64
 65	// SetParent sets a parent node to this node.
 66	SetParent(Node)
 67
 68	// SetPreviousSibling sets a previous sibling node to this node.
 69	SetPreviousSibling(Node)
 70
 71	// SetNextSibling sets a next sibling node to this node.
 72	SetNextSibling(Node)
 73
 74	// HasChildren returns true if this node has any children, otherwise false.
 75	HasChildren() bool
 76
 77	// ChildCount returns a total number of children.
 78	ChildCount() int
 79
 80	// FirstChild returns a first child of this node.
 81	FirstChild() Node
 82
 83	// LastChild returns a last child of this node.
 84	LastChild() Node
 85
 86	// AppendChild append a node child to the tail of the children.
 87	AppendChild(self, child Node)
 88
 89	// RemoveChild removes a node child from this node.
 90	// If a node child is not children of this node, RemoveChild nothing to do.
 91	RemoveChild(self, child Node)
 92
 93	// RemoveChildren removes all children from this node.
 94	RemoveChildren(self Node)
 95
 96	// SortChildren sorts childrens by comparator.
 97	SortChildren(comparator func(n1, n2 Node) int)
 98
 99	// ReplaceChild replace a node v1 with a node insertee.
100	// If v1 is not children of this node, ReplaceChild append a insetee to the
101	// tail of the children.
102	ReplaceChild(self, v1, insertee Node)
103
104	// InsertBefore inserts a node insertee before a node v1.
105	// If v1 is not children of this node, InsertBefore append a insetee to the
106	// tail of the children.
107	InsertBefore(self, v1, insertee Node)
108
109	// InsertAfterinserts a node insertee after a node v1.
110	// If v1 is not children of this node, InsertBefore append a insetee to the
111	// tail of the children.
112	InsertAfter(self, v1, insertee Node)
113
114	// OwnerDocument returns this node's owner document.
115	// If this node is not a child of the Document node, OwnerDocument
116	// returns nil.
117	OwnerDocument() *Document
118
119	// Dump dumps an AST tree structure to stdout.
120	// This function completely aimed for debugging.
121	// level is a indent level. Implementer should indent informations with
122	// 2 * level spaces.
123	Dump(source []byte, level int)
124
125	// Text returns text values of this node.
126	// This method is valid only for some inline nodes.
127	// If this node is a block node, Text returns a text value as reasonable as possible.
128	// Notice that there are no 'correct' text values for the block nodes.
129	// Result for the block nodes may be different from your expectation.
130	//
131	// Deprecated: Use other properties of the node to get the text value(i.e. Pragraph.Lines, Text.Value).
132	Text(source []byte) []byte
133
134	// HasBlankPreviousLines returns true if the row before this node is blank,
135	// otherwise false.
136	// This method is valid only for block nodes.
137	HasBlankPreviousLines() bool
138
139	// SetBlankPreviousLines sets whether the row before this node is blank.
140	// This method is valid only for block nodes.
141	SetBlankPreviousLines(v bool)
142
143	// Lines returns text segments that hold positions in a source.
144	// This method is valid only for block nodes.
145	Lines() *textm.Segments
146
147	// SetLines sets text segments that hold positions in a source.
148	// This method is valid only for block nodes.
149	SetLines(*textm.Segments)
150
151	// IsRaw returns true if contents should be rendered as 'raw' contents.
152	IsRaw() bool
153
154	// SetAttribute sets the given value to the attributes.
155	SetAttribute(name []byte, value interface{})
156
157	// SetAttributeString sets the given value to the attributes.
158	SetAttributeString(name string, value interface{})
159
160	// Attribute returns a (attribute value, true) if an attribute
161	// associated with the given name is found, otherwise
162	// (nil, false)
163	Attribute(name []byte) (interface{}, bool)
164
165	// AttributeString returns a (attribute value, true) if an attribute
166	// associated with the given name is found, otherwise
167	// (nil, false)
168	AttributeString(name string) (interface{}, bool)
169
170	// Attributes returns a list of attributes.
171	// This may be a nil if there are no attributes.
172	Attributes() []Attribute
173
174	// RemoveAttributes removes all attributes from this node.
175	RemoveAttributes()
176}
177
178// A BaseNode struct implements the Node interface partialliy.
179type BaseNode struct {
180	firstChild Node
181	lastChild  Node
182	parent     Node
183	next       Node
184	prev       Node
185	childCount int
186	attributes []Attribute
187}
188
189func ensureIsolated(v Node) {
190	if p := v.Parent(); p != nil {
191		p.RemoveChild(p, v)
192	}
193}
194
195// HasChildren implements Node.HasChildren .
196func (n *BaseNode) HasChildren() bool {
197	return n.firstChild != nil
198}
199
200// SetPreviousSibling implements Node.SetPreviousSibling .
201func (n *BaseNode) SetPreviousSibling(v Node) {
202	n.prev = v
203}
204
205// SetNextSibling implements Node.SetNextSibling .
206func (n *BaseNode) SetNextSibling(v Node) {
207	n.next = v
208}
209
210// PreviousSibling implements Node.PreviousSibling .
211func (n *BaseNode) PreviousSibling() Node {
212	return n.prev
213}
214
215// NextSibling implements Node.NextSibling .
216func (n *BaseNode) NextSibling() Node {
217	return n.next
218}
219
220// RemoveChild implements Node.RemoveChild .
221func (n *BaseNode) RemoveChild(self, v Node) {
222	if v.Parent() != self {
223		return
224	}
225	n.childCount--
226	prev := v.PreviousSibling()
227	next := v.NextSibling()
228	if prev != nil {
229		prev.SetNextSibling(next)
230	} else {
231		n.firstChild = next
232	}
233	if next != nil {
234		next.SetPreviousSibling(prev)
235	} else {
236		n.lastChild = prev
237	}
238	v.SetParent(nil)
239	v.SetPreviousSibling(nil)
240	v.SetNextSibling(nil)
241}
242
243// RemoveChildren implements Node.RemoveChildren .
244func (n *BaseNode) RemoveChildren(self Node) {
245	for c := n.firstChild; c != nil; {
246		c.SetParent(nil)
247		c.SetPreviousSibling(nil)
248		next := c.NextSibling()
249		c.SetNextSibling(nil)
250		c = next
251	}
252	n.firstChild = nil
253	n.lastChild = nil
254	n.childCount = 0
255}
256
257// SortChildren implements Node.SortChildren.
258func (n *BaseNode) SortChildren(comparator func(n1, n2 Node) int) {
259	var sorted Node
260	current := n.firstChild
261	for current != nil {
262		next := current.NextSibling()
263		if sorted == nil || comparator(sorted, current) >= 0 {
264			current.SetNextSibling(sorted)
265			if sorted != nil {
266				sorted.SetPreviousSibling(current)
267			}
268			sorted = current
269			sorted.SetPreviousSibling(nil)
270		} else {
271			c := sorted
272			for c.NextSibling() != nil && comparator(c.NextSibling(), current) < 0 {
273				c = c.NextSibling()
274			}
275			current.SetNextSibling(c.NextSibling())
276			current.SetPreviousSibling(c)
277			if c.NextSibling() != nil {
278				c.NextSibling().SetPreviousSibling(current)
279			}
280			c.SetNextSibling(current)
281		}
282		current = next
283	}
284	n.firstChild = sorted
285	for c := n.firstChild; c != nil; c = c.NextSibling() {
286		n.lastChild = c
287	}
288}
289
290// FirstChild implements Node.FirstChild .
291func (n *BaseNode) FirstChild() Node {
292	return n.firstChild
293}
294
295// LastChild implements Node.LastChild .
296func (n *BaseNode) LastChild() Node {
297	return n.lastChild
298}
299
300// ChildCount implements Node.ChildCount .
301func (n *BaseNode) ChildCount() int {
302	return n.childCount
303}
304
305// Parent implements Node.Parent .
306func (n *BaseNode) Parent() Node {
307	return n.parent
308}
309
310// SetParent implements Node.SetParent .
311func (n *BaseNode) SetParent(v Node) {
312	n.parent = v
313}
314
315// AppendChild implements Node.AppendChild .
316func (n *BaseNode) AppendChild(self, v Node) {
317	ensureIsolated(v)
318	if n.firstChild == nil {
319		n.firstChild = v
320		v.SetNextSibling(nil)
321		v.SetPreviousSibling(nil)
322	} else {
323		last := n.lastChild
324		last.SetNextSibling(v)
325		v.SetPreviousSibling(last)
326	}
327	v.SetParent(self)
328	n.lastChild = v
329	n.childCount++
330}
331
332// ReplaceChild implements Node.ReplaceChild .
333func (n *BaseNode) ReplaceChild(self, v1, insertee Node) {
334	n.InsertBefore(self, v1, insertee)
335	n.RemoveChild(self, v1)
336}
337
338// InsertAfter implements Node.InsertAfter .
339func (n *BaseNode) InsertAfter(self, v1, insertee Node) {
340	n.InsertBefore(self, v1.NextSibling(), insertee)
341}
342
343// InsertBefore implements Node.InsertBefore .
344func (n *BaseNode) InsertBefore(self, v1, insertee Node) {
345	n.childCount++
346	if v1 == nil {
347		n.AppendChild(self, insertee)
348		return
349	}
350	ensureIsolated(insertee)
351	if v1.Parent() == self {
352		c := v1
353		prev := c.PreviousSibling()
354		if prev != nil {
355			prev.SetNextSibling(insertee)
356			insertee.SetPreviousSibling(prev)
357		} else {
358			n.firstChild = insertee
359			insertee.SetPreviousSibling(nil)
360		}
361		insertee.SetNextSibling(c)
362		c.SetPreviousSibling(insertee)
363		insertee.SetParent(self)
364	}
365}
366
367// OwnerDocument implements Node.OwnerDocument.
368func (n *BaseNode) OwnerDocument() *Document {
369	d := n.Parent()
370	for {
371		p := d.Parent()
372		if p == nil {
373			if v, ok := d.(*Document); ok {
374				return v
375			}
376			break
377		}
378		d = p
379	}
380	return nil
381}
382
383// Text implements Node.Text .
384//
385// Deprecated: Use other properties of the node to get the text value(i.e. Pragraph.Lines, Text.Value).
386func (n *BaseNode) Text(source []byte) []byte {
387	var buf bytes.Buffer
388	for c := n.firstChild; c != nil; c = c.NextSibling() {
389		buf.Write(c.Text(source))
390		if sb, ok := c.(interface {
391			SoftLineBreak() bool
392		}); ok && sb.SoftLineBreak() {
393			buf.WriteByte('\n')
394		}
395	}
396	return buf.Bytes()
397}
398
399// SetAttribute implements Node.SetAttribute.
400func (n *BaseNode) SetAttribute(name []byte, value interface{}) {
401	if n.attributes == nil {
402		n.attributes = make([]Attribute, 0, 10)
403	} else {
404		for i, a := range n.attributes {
405			if bytes.Equal(a.Name, name) {
406				n.attributes[i].Name = name
407				n.attributes[i].Value = value
408				return
409			}
410		}
411	}
412	n.attributes = append(n.attributes, Attribute{name, value})
413}
414
415// SetAttributeString implements Node.SetAttributeString.
416func (n *BaseNode) SetAttributeString(name string, value interface{}) {
417	n.SetAttribute(util.StringToReadOnlyBytes(name), value)
418}
419
420// Attribute implements Node.Attribute.
421func (n *BaseNode) Attribute(name []byte) (interface{}, bool) {
422	if n.attributes == nil {
423		return nil, false
424	}
425	for i, a := range n.attributes {
426		if bytes.Equal(a.Name, name) {
427			return n.attributes[i].Value, true
428		}
429	}
430	return nil, false
431}
432
433// AttributeString implements Node.AttributeString.
434func (n *BaseNode) AttributeString(s string) (interface{}, bool) {
435	return n.Attribute(util.StringToReadOnlyBytes(s))
436}
437
438// Attributes implements Node.Attributes.
439func (n *BaseNode) Attributes() []Attribute {
440	return n.attributes
441}
442
443// RemoveAttributes implements Node.RemoveAttributes.
444func (n *BaseNode) RemoveAttributes() {
445	n.attributes = nil
446}
447
448// DumpHelper is a helper function to implement Node.Dump.
449// kv is pairs of an attribute name and an attribute value.
450// cb is a function called after wrote a name and attributes.
451func DumpHelper(v Node, source []byte, level int, kv map[string]string, cb func(int)) {
452	name := v.Kind().String()
453	indent := strings.Repeat("    ", level)
454	fmt.Printf("%s%s {\n", indent, name)
455	indent2 := strings.Repeat("    ", level+1)
456	if v.Type() == TypeBlock {
457		fmt.Printf("%sRawText: \"", indent2)
458		for i := 0; i < v.Lines().Len(); i++ {
459			line := v.Lines().At(i)
460			fmt.Printf("%s", line.Value(source))
461		}
462		fmt.Printf("\"\n")
463		fmt.Printf("%sHasBlankPreviousLines: %v\n", indent2, v.HasBlankPreviousLines())
464	}
465	for name, value := range kv {
466		fmt.Printf("%s%s: %s\n", indent2, name, value)
467	}
468	if cb != nil {
469		cb(level + 1)
470	}
471	for c := v.FirstChild(); c != nil; c = c.NextSibling() {
472		c.Dump(source, level+1)
473	}
474	fmt.Printf("%s}\n", indent)
475}
476
477// WalkStatus represents a current status of the Walk function.
478type WalkStatus int
479
480const (
481	// WalkStop indicates no more walking needed.
482	WalkStop WalkStatus = iota + 1
483
484	// WalkSkipChildren indicates that Walk wont walk on children of current
485	// node.
486	WalkSkipChildren
487
488	// WalkContinue indicates that Walk can continue to walk.
489	WalkContinue
490)
491
492// Walker is a function that will be called when Walk find a
493// new node.
494// entering is set true before walks children, false after walked children.
495// If Walker returns error, Walk function immediately stop walking.
496type Walker func(n Node, entering bool) (WalkStatus, error)
497
498// Walk walks a AST tree by the depth first search algorithm.
499func Walk(n Node, walker Walker) error {
500	_, err := walkHelper(n, walker)
501	return err
502}
503
504func walkHelper(n Node, walker Walker) (WalkStatus, error) {
505	status, err := walker(n, true)
506	if err != nil || status == WalkStop {
507		return status, err
508	}
509	if status != WalkSkipChildren {
510		for c := n.FirstChild(); c != nil; c = c.NextSibling() {
511			if st, err := walkHelper(c, walker); err != nil || st == WalkStop {
512				return WalkStop, err
513			}
514		}
515	}
516	status, err = walker(n, false)
517	if err != nil || status == WalkStop {
518		return WalkStop, err
519	}
520	return WalkContinue, nil
521}