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	Text(source []byte) []byte
127
128	// HasBlankPreviousLines returns true if the row before this node is blank,
129	// otherwise false.
130	// This method is valid only for block nodes.
131	HasBlankPreviousLines() bool
132
133	// SetBlankPreviousLines sets whether the row before this node is blank.
134	// This method is valid only for block nodes.
135	SetBlankPreviousLines(v bool)
136
137	// Lines returns text segments that hold positions in a source.
138	// This method is valid only for block nodes.
139	Lines() *textm.Segments
140
141	// SetLines sets text segments that hold positions in a source.
142	// This method is valid only for block nodes.
143	SetLines(*textm.Segments)
144
145	// IsRaw returns true if contents should be rendered as 'raw' contents.
146	IsRaw() bool
147
148	// SetAttribute sets the given value to the attributes.
149	SetAttribute(name []byte, value interface{})
150
151	// SetAttributeString sets the given value to the attributes.
152	SetAttributeString(name string, value interface{})
153
154	// Attribute returns a (attribute value, true) if an attribute
155	// associated with the given name is found, otherwise
156	// (nil, false)
157	Attribute(name []byte) (interface{}, bool)
158
159	// AttributeString returns a (attribute value, true) if an attribute
160	// associated with the given name is found, otherwise
161	// (nil, false)
162	AttributeString(name string) (interface{}, bool)
163
164	// Attributes returns a list of attributes.
165	// This may be a nil if there are no attributes.
166	Attributes() []Attribute
167
168	// RemoveAttributes removes all attributes from this node.
169	RemoveAttributes()
170}
171
172// A BaseNode struct implements the Node interface partialliy.
173type BaseNode struct {
174	firstChild Node
175	lastChild  Node
176	parent     Node
177	next       Node
178	prev       Node
179	childCount int
180	attributes []Attribute
181}
182
183func ensureIsolated(v Node) {
184	if p := v.Parent(); p != nil {
185		p.RemoveChild(p, v)
186	}
187}
188
189// HasChildren implements Node.HasChildren .
190func (n *BaseNode) HasChildren() bool {
191	return n.firstChild != nil
192}
193
194// SetPreviousSibling implements Node.SetPreviousSibling .
195func (n *BaseNode) SetPreviousSibling(v Node) {
196	n.prev = v
197}
198
199// SetNextSibling implements Node.SetNextSibling .
200func (n *BaseNode) SetNextSibling(v Node) {
201	n.next = v
202}
203
204// PreviousSibling implements Node.PreviousSibling .
205func (n *BaseNode) PreviousSibling() Node {
206	return n.prev
207}
208
209// NextSibling implements Node.NextSibling .
210func (n *BaseNode) NextSibling() Node {
211	return n.next
212}
213
214// RemoveChild implements Node.RemoveChild .
215func (n *BaseNode) RemoveChild(self, v Node) {
216	if v.Parent() != self {
217		return
218	}
219	n.childCount--
220	prev := v.PreviousSibling()
221	next := v.NextSibling()
222	if prev != nil {
223		prev.SetNextSibling(next)
224	} else {
225		n.firstChild = next
226	}
227	if next != nil {
228		next.SetPreviousSibling(prev)
229	} else {
230		n.lastChild = prev
231	}
232	v.SetParent(nil)
233	v.SetPreviousSibling(nil)
234	v.SetNextSibling(nil)
235}
236
237// RemoveChildren implements Node.RemoveChildren .
238func (n *BaseNode) RemoveChildren(self Node) {
239	for c := n.firstChild; c != nil; {
240		c.SetParent(nil)
241		c.SetPreviousSibling(nil)
242		next := c.NextSibling()
243		c.SetNextSibling(nil)
244		c = next
245	}
246	n.firstChild = nil
247	n.lastChild = nil
248	n.childCount = 0
249}
250
251// SortChildren implements Node.SortChildren
252func (n *BaseNode) SortChildren(comparator func(n1, n2 Node) int) {
253	var sorted Node
254	current := n.firstChild
255	for current != nil {
256		next := current.NextSibling()
257		if sorted == nil || comparator(sorted, current) >= 0 {
258			current.SetNextSibling(sorted)
259			if sorted != nil {
260				sorted.SetPreviousSibling(current)
261			}
262			sorted = current
263			sorted.SetPreviousSibling(nil)
264		} else {
265			c := sorted
266			for c.NextSibling() != nil && comparator(c.NextSibling(), current) < 0 {
267				c = c.NextSibling()
268			}
269			current.SetNextSibling(c.NextSibling())
270			current.SetPreviousSibling(c)
271			if c.NextSibling() != nil {
272				c.NextSibling().SetPreviousSibling(current)
273			}
274			c.SetNextSibling(current)
275		}
276		current = next
277	}
278	n.firstChild = sorted
279	for c := n.firstChild; c != nil; c = c.NextSibling() {
280		n.lastChild = c
281	}
282}
283
284// FirstChild implements Node.FirstChild .
285func (n *BaseNode) FirstChild() Node {
286	return n.firstChild
287}
288
289// LastChild implements Node.LastChild .
290func (n *BaseNode) LastChild() Node {
291	return n.lastChild
292}
293
294// ChildCount implements Node.ChildCount .
295func (n *BaseNode) ChildCount() int {
296	return n.childCount
297}
298
299// Parent implements Node.Parent .
300func (n *BaseNode) Parent() Node {
301	return n.parent
302}
303
304// SetParent implements Node.SetParent .
305func (n *BaseNode) SetParent(v Node) {
306	n.parent = v
307}
308
309// AppendChild implements Node.AppendChild .
310func (n *BaseNode) AppendChild(self, v Node) {
311	ensureIsolated(v)
312	if n.firstChild == nil {
313		n.firstChild = v
314		v.SetNextSibling(nil)
315		v.SetPreviousSibling(nil)
316	} else {
317		last := n.lastChild
318		last.SetNextSibling(v)
319		v.SetPreviousSibling(last)
320	}
321	v.SetParent(self)
322	n.lastChild = v
323	n.childCount++
324}
325
326// ReplaceChild implements Node.ReplaceChild .
327func (n *BaseNode) ReplaceChild(self, v1, insertee Node) {
328	n.InsertBefore(self, v1, insertee)
329	n.RemoveChild(self, v1)
330}
331
332// InsertAfter implements Node.InsertAfter .
333func (n *BaseNode) InsertAfter(self, v1, insertee Node) {
334	n.InsertBefore(self, v1.NextSibling(), insertee)
335}
336
337// InsertBefore implements Node.InsertBefore .
338func (n *BaseNode) InsertBefore(self, v1, insertee Node) {
339	n.childCount++
340	if v1 == nil {
341		n.AppendChild(self, insertee)
342		return
343	}
344	ensureIsolated(insertee)
345	if v1.Parent() == self {
346		c := v1
347		prev := c.PreviousSibling()
348		if prev != nil {
349			prev.SetNextSibling(insertee)
350			insertee.SetPreviousSibling(prev)
351		} else {
352			n.firstChild = insertee
353			insertee.SetPreviousSibling(nil)
354		}
355		insertee.SetNextSibling(c)
356		c.SetPreviousSibling(insertee)
357		insertee.SetParent(self)
358	}
359}
360
361// OwnerDocument implements Node.OwnerDocument
362func (n *BaseNode) OwnerDocument() *Document {
363	d := n.Parent()
364	for {
365		p := d.Parent()
366		if p == nil {
367			if v, ok := d.(*Document); ok {
368				return v
369			}
370			break
371		}
372		d = p
373	}
374	return nil
375}
376
377// Text implements Node.Text  .
378func (n *BaseNode) Text(source []byte) []byte {
379	var buf bytes.Buffer
380	for c := n.firstChild; c != nil; c = c.NextSibling() {
381		buf.Write(c.Text(source))
382	}
383	return buf.Bytes()
384}
385
386// SetAttribute implements Node.SetAttribute.
387func (n *BaseNode) SetAttribute(name []byte, value interface{}) {
388	if n.attributes == nil {
389		n.attributes = make([]Attribute, 0, 10)
390	} else {
391		for i, a := range n.attributes {
392			if bytes.Equal(a.Name, name) {
393				n.attributes[i].Name = name
394				n.attributes[i].Value = value
395				return
396			}
397		}
398	}
399	n.attributes = append(n.attributes, Attribute{name, value})
400}
401
402// SetAttributeString implements Node.SetAttributeString
403func (n *BaseNode) SetAttributeString(name string, value interface{}) {
404	n.SetAttribute(util.StringToReadOnlyBytes(name), value)
405}
406
407// Attribute implements Node.Attribute.
408func (n *BaseNode) Attribute(name []byte) (interface{}, bool) {
409	if n.attributes == nil {
410		return nil, false
411	}
412	for i, a := range n.attributes {
413		if bytes.Equal(a.Name, name) {
414			return n.attributes[i].Value, true
415		}
416	}
417	return nil, false
418}
419
420// AttributeString implements Node.AttributeString.
421func (n *BaseNode) AttributeString(s string) (interface{}, bool) {
422	return n.Attribute(util.StringToReadOnlyBytes(s))
423}
424
425// Attributes implements Node.Attributes
426func (n *BaseNode) Attributes() []Attribute {
427	return n.attributes
428}
429
430// RemoveAttributes implements Node.RemoveAttributes
431func (n *BaseNode) RemoveAttributes() {
432	n.attributes = nil
433}
434
435// DumpHelper is a helper function to implement Node.Dump.
436// kv is pairs of an attribute name and an attribute value.
437// cb is a function called after wrote a name and attributes.
438func DumpHelper(v Node, source []byte, level int, kv map[string]string, cb func(int)) {
439	name := v.Kind().String()
440	indent := strings.Repeat("    ", level)
441	fmt.Printf("%s%s {\n", indent, name)
442	indent2 := strings.Repeat("    ", level+1)
443	if v.Type() == TypeBlock {
444		fmt.Printf("%sRawText: \"", indent2)
445		for i := 0; i < v.Lines().Len(); i++ {
446			line := v.Lines().At(i)
447			fmt.Printf("%s", line.Value(source))
448		}
449		fmt.Printf("\"\n")
450		fmt.Printf("%sHasBlankPreviousLines: %v\n", indent2, v.HasBlankPreviousLines())
451	}
452	for name, value := range kv {
453		fmt.Printf("%s%s: %s\n", indent2, name, value)
454	}
455	if cb != nil {
456		cb(level + 1)
457	}
458	for c := v.FirstChild(); c != nil; c = c.NextSibling() {
459		c.Dump(source, level+1)
460	}
461	fmt.Printf("%s}\n", indent)
462}
463
464// WalkStatus represents a current status of the Walk function.
465type WalkStatus int
466
467const (
468	// WalkStop indicates no more walking needed.
469	WalkStop WalkStatus = iota + 1
470
471	// WalkSkipChildren indicates that Walk wont walk on children of current
472	// node.
473	WalkSkipChildren
474
475	// WalkContinue indicates that Walk can continue to walk.
476	WalkContinue
477)
478
479// Walker is a function that will be called when Walk find a
480// new node.
481// entering is set true before walks children, false after walked children.
482// If Walker returns error, Walk function immediately stop walking.
483type Walker func(n Node, entering bool) (WalkStatus, error)
484
485// Walk walks a AST tree by the depth first search algorithm.
486func Walk(n Node, walker Walker) error {
487	_, err := walkHelper(n, walker)
488	return err
489}
490
491func walkHelper(n Node, walker Walker) (WalkStatus, error) {
492	status, err := walker(n, true)
493	if err != nil || status == WalkStop {
494		return status, err
495	}
496	if status != WalkSkipChildren {
497		for c := n.FirstChild(); c != nil; c = c.NextSibling() {
498			if st, err := walkHelper(c, walker); err != nil || st == WalkStop {
499				return WalkStop, err
500			}
501		}
502	}
503	status, err = walker(n, false)
504	if err != nil || status == WalkStop {
505		return WalkStop, err
506	}
507	return WalkContinue, nil
508}