ast.go

Documentation: github.com/yuin/goldmark/ast

     1  // Package ast defines AST nodes that represent markdown elements.
     2  package ast
     3  
     4  import (
     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.
    14  type NodeType int
    15  
    16  const (
    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.
    26  type NodeKind int
    27  
    28  func (k NodeKind) String() string {
    29  	return kindNames[k]
    30  }
    31  
    32  var kindMax NodeKind
    33  var kindNames = []string{""}
    34  
    35  // NewNodeKind returns a new Kind value.
    36  func 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
    43  type Attribute struct {
    44  	Name  []byte
    45  	Value interface{}
    46  }
    47  
    48  // A Node interface defines basic AST node functionalities.
    49  type 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.
   173  type 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  
   183  func ensureIsolated(v Node) {
   184  	if p := v.Parent(); p != nil {
   185  		p.RemoveChild(p, v)
   186  	}
   187  }
   188  
   189  // HasChildren implements Node.HasChildren .
   190  func (n *BaseNode) HasChildren() bool {
   191  	return n.firstChild != nil
   192  }
   193  
   194  // SetPreviousSibling implements Node.SetPreviousSibling .
   195  func (n *BaseNode) SetPreviousSibling(v Node) {
   196  	n.prev = v
   197  }
   198  
   199  // SetNextSibling implements Node.SetNextSibling .
   200  func (n *BaseNode) SetNextSibling(v Node) {
   201  	n.next = v
   202  }
   203  
   204  // PreviousSibling implements Node.PreviousSibling .
   205  func (n *BaseNode) PreviousSibling() Node {
   206  	return n.prev
   207  }
   208  
   209  // NextSibling implements Node.NextSibling .
   210  func (n *BaseNode) NextSibling() Node {
   211  	return n.next
   212  }
   213  
   214  // RemoveChild implements Node.RemoveChild .
   215  func (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 .
   238  func (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
   252  func (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 .
   285  func (n *BaseNode) FirstChild() Node {
   286  	return n.firstChild
   287  }
   288  
   289  // LastChild implements Node.LastChild .
   290  func (n *BaseNode) LastChild() Node {
   291  	return n.lastChild
   292  }
   293  
   294  // ChildCount implements Node.ChildCount .
   295  func (n *BaseNode) ChildCount() int {
   296  	return n.childCount
   297  }
   298  
   299  // Parent implements Node.Parent .
   300  func (n *BaseNode) Parent() Node {
   301  	return n.parent
   302  }
   303  
   304  // SetParent implements Node.SetParent .
   305  func (n *BaseNode) SetParent(v Node) {
   306  	n.parent = v
   307  }
   308  
   309  // AppendChild implements Node.AppendChild .
   310  func (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 .
   327  func (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 .
   333  func (n *BaseNode) InsertAfter(self, v1, insertee Node) {
   334  	n.InsertBefore(self, v1.NextSibling(), insertee)
   335  }
   336  
   337  // InsertBefore implements Node.InsertBefore .
   338  func (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
   362  func (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  .
   378  func (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.
   387  func (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
   403  func (n *BaseNode) SetAttributeString(name string, value interface{}) {
   404  	n.SetAttribute(util.StringToReadOnlyBytes(name), value)
   405  }
   406  
   407  // Attribute implements Node.Attribute.
   408  func (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.
   421  func (n *BaseNode) AttributeString(s string) (interface{}, bool) {
   422  	return n.Attribute(util.StringToReadOnlyBytes(s))
   423  }
   424  
   425  // Attributes implements Node.Attributes
   426  func (n *BaseNode) Attributes() []Attribute {
   427  	return n.attributes
   428  }
   429  
   430  // RemoveAttributes implements Node.RemoveAttributes
   431  func (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.
   438  func 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.
   465  type WalkStatus int
   466  
   467  const (
   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.
   483  type Walker func(n Node, entering bool) (WalkStatus, error)
   484  
   485  // Walk walks a AST tree by the depth first search algorithm.
   486  func Walk(n Node, walker Walker) error {
   487  	_, err := walkHelper(n, walker)
   488  	return err
   489  }
   490  
   491  func 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  }
   509
View as plain text