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