Documentation
¶
Overview ¶
Package tree provides basic functions for building, manipulating, and traversing syntax trees. A tree consists of linked node and token elements, the root is the initial node element.
Index ¶
- Constants
- func AppendChild(parent NodeElement, el Element)
- func AppendSibling(prev, el Element)
- func Detach(n Element)
- func NodeHook(node string, tok *lexer.Token, pc *parser.ParseContext) (parser.NodeHookInstance, error)
- func PrependSibling(next, el Element)
- func Replace(old, n Element)
- func Walk(root Element, mode WalkMode, visitor Visitor)
- type Element
- func Ancestors(el Element) []Element
- func Children(n Element) []Element
- func FirstTokenElement(n Element) Element
- func LastTokenElement(n Element) Element
- func NewTokenElement(t *lexer.Token) Element
- func NextSiblings(el Element) []Element
- func NextTokenElement(n Element) Element
- func PrevSiblings(el Element) []Element
- func PrevTokenElement(n Element) Element
- type Extractor
- type Filter
- type HookInstance
- type NodeElement
- type Selector
- type Visitor
- type WalkMode
- type WalkStat
- type Walker
- type WalkerFlags
Examples ¶
Constants ¶
const ( WalkerStop = 1 << iota // Stop traversing. WalkerSkipChildren // Skip traversing child subtrees of the last fetched element. Ignored if no elements fetched yet. WalkerSkipSiblings // Skip sibling subtrees of the last fetched element. Ignored if no elements fetched yet. )
Variables ¶
This section is empty.
Functions ¶
func AppendChild ¶
func AppendChild(parent NodeElement, el Element)
AppendChild places new element as a child of target one. New element becomes target's last child.
func AppendSibling ¶
func AppendSibling(prev, el Element)
AppendSibling places new element after target one. Target becomes new element's previous sibling, target's next sibling (if any) becomes new element's next sibling. Does nothing if either new or target element is nil.
func Detach ¶
func Detach(n Element)
Detach removes element from tree. Parent and sibling references are removed, but descendants are kept. Does nothing if the element is the tree root.
func NodeHook ¶
func NodeHook(node string, tok *lexer.Token, pc *parser.ParseContext) (parser.NodeHookInstance, error)
NodeHook implements parser.NodeHook and builds syntax tree. Intended to be used as node hook for parser.AnyNode.
func PrependSibling ¶
func PrependSibling(next, el Element)
PrependSibling places new element before target one. Target becomes new element's next sibling, target's previous sibling (if any) becomes new element's previous sibling. Does nothing if either new or target element is nil.
func Replace ¶
func Replace(old, n Element)
Replace replaces old element with new one or simply removes old element if the new one is nil.
func Walk ¶
Walk traverses given subtree in specified order calling visitor for each fetched element.
Example ¶
package main
import (
"fmt"
"github.com/ava12/llx/langdef"
"github.com/ava12/llx/parser"
"github.com/ava12/llx/tree"
)
func main() {
input := "foo=bar"
grammar := `$name = /\w+/; $op = /=/; g = var, "=", value; var = $name; value = $name;`
g, e := langdef.ParseString("grammar", grammar)
if e != nil {
fmt.Println(e)
return
}
p, _ := parser.New(g)
h := parser.Hooks{Nodes: parser.NodeHooks{
parser.AnyNode: tree.NodeHook,
}}
root, e := p.ParseString("input", input, &h)
if e != nil {
fmt.Println(e)
return
}
indent := "----------"
visitor := func(stat tree.WalkStat) tree.WalkerFlags {
el := stat.Element
if el.IsNode() {
fmt.Printf("%s%s:\n", indent[:stat.Level*2], el.TypeName())
} else {
fmt.Printf("%s%s %q\n", indent[:stat.Level*2], el.TypeName(), el.Token().Text())
}
return 0
}
tree.Walk(root.(tree.Element), tree.WalkLtr, visitor)
}
Output: g: --var: ----name "foo" --op "=" --value: ----name "bar"
Types ¶
type Element ¶
type Element interface {
// IsNode returns true for node element, false for token element.
IsNode() bool
// TypeName returns token or node type name.
TypeName() string
// Token returns token for this element (for node it is initial token).
Token() *lexer.Token
// Parent returns parent node element, nil for tree root.
Parent() NodeElement
// Prev returns previous sibling for element, nil for first child or tree root.
Prev() Element
// Next returns the next sibling for element, nil for last child or tree root.
Next() Element
// SetParent sets parent node for element, nil to remove element from tree.
// Used by SetChild and RemoveChild.
SetParent(NodeElement)
// SetPrev sets previous sibling for element, nil to make the first sibling or to remove element from tree.
// Used by functions manipulating child and sibling elements.
SetPrev(Element)
// SetNext sets the next sibling for element, nil to make the last sibling or to remove element from tree.
// Used by functions manipulating child and sibling elements.
SetNext(Element)
}
Element represents parse tree element, either a node or a token.
func Ancestors ¶
Ancestors returns ancestors of given element in closest-to-farthest order, i.e. the first output element is given element's parent and the last one is the tree root.
func Children ¶
Children returns child elements (if there are any) or nil if given element is not a node. Child elements are returned in left-to-right order.
func FirstTokenElement ¶
FirstTokenElement returns element itself if it's not a node or returns the first token element captured by node or its descendant nodes. Returns nil if neither node nor its descendants contain token elements.
func LastTokenElement ¶
LastTokenElement returns element itself if it's not a node or returns the last token element captured by node or its descendant nodes. Returns nil if neither node nor its descendants contain token elements.
func NewTokenElement ¶
NewTokenElement creates token element for given token.
func NextSiblings ¶
NextSiblings returns following siblings of given element in closest-to-farthest order, i.e. the first output element is given element's next sibling and the last one is the last sibling.
func NextTokenElement ¶
NextTokenElement returns the first token element after given one, if there are any. I.e. the first token element in the next sibling or its parent's next sibling etc.
func PrevSiblings ¶
PrevSiblings returns preceding siblings of given element in closest-to-farthest order, i.e. the first output element is given element's previous sibling and the last one is the first sibling.
func PrevTokenElement ¶
PrevTokenElement returns the last token element before given one, if there are any. I.e. the last token element in the previous sibling or its parent's previous sibling etc.
type Extractor ¶
Extractor returns a list of elements related to given non-nil element. Result must not contain nil elements.
func All ¶
All creates extractor that applies all given extractors to input element. Returns merged outputs, may contain duplicate elements.
type Filter ¶
Filter examines given non-nil element and decides whether it is accepted and must be kept in element list (true) or rejected and must be removed from list (false).
func IsALiteral ¶
IsALiteral creates filter that accepts token elements with given content and rejects others.
func IsAll ¶
IsAll creates filter that accepts element if it is accepted by all of given filters and rejects otherwise.
type HookInstance ¶
type HookInstance struct {
// contains filtered or unexported fields
}
func NewHookInstance ¶
func NewHookInstance(typeName string, tok *lexer.Token) *HookInstance
func (*HookInstance) EndNode ¶
func (hi *HookInstance) EndNode() (result interface{}, e error)
func (*HookInstance) HandleNode ¶
func (hi *HookInstance) HandleNode(name string, result interface{}) error
func (*HookInstance) HandleToken ¶
func (hi *HookInstance) HandleToken(token *lexer.Token) error
type NodeElement ¶
type NodeElement interface {
Element
// FirstChild returns first child element or nil if there are no children.
FirstChild() Element
// LastChild returns last child element or nil if there are no children.
LastChild() Element
// AddChild inserts child element. New child is placed before given one or after the last child.
// Does nothing if n is nil or given element does not belong to node.
AddChild(n, before Element)
// RemoveChild detaches given child element from node.
// Does nothing if given element is not this node's child.
RemoveChild(Element)
}
NodeElement represents parse tree node.
func NewNodeElement ¶
func NewNodeElement(typeName string, tok *lexer.Token) NodeElement
NewNodeElement creates node element of given type with given initial token, token may be nil.
type Selector ¶
type Selector struct {
// contains filtered or unexported fields
}
Selector transforms list of elements to another list using provided transformers (extractors and filters). Contains list of transformers, configurable and reusable.
func NewSelector ¶
func NewSelector() *Selector
NewSelector creates selector with empty list of transformers.
func (*Selector) Apply ¶
Apply applies stored list of transformers to passed list of elements and returns output. Transformers are used in FIFO order, output is used as an input for the next transformer.
func (*Selector) DeepSearch ¶
DeepSearch adds transformer that treats input element as a subtree root and traverses this subtree extracting elements that are accepted by given filter. Extracted elements are also traversed, so if accepted element contains acceptable descendants, those descendants will be output as well. Modifies selector, chainable.
func (*Selector) Extract ¶
Extract adds extractor to transformer list. Modifies selector, chainable.
func (*Selector) Search ¶
Search adds transformer that treats input element as a subtree root and traverses this subtree extracting elements that are accepted by given filter. Extracted elements are not traversed, so if accepted element contains acceptable descendants, those descendants will not be output. Modifies selector, chainable.
type Visitor ¶
type Visitor func(s WalkStat) WalkerFlags
Visitor processes element fetched by walker and responds which parts of subtree must be skipped on next step.
type WalkStat ¶
type WalkStat struct {
// Element is the fetched element. nil if subtree traversal is finished.
Element Element
// Level is the nest level of fetched element relative to subtree root.
// 0 is root, 1 is root's child etc.
Level int
}
WalkStat contains information about fetched subtree element.
type Walker ¶
type Walker struct {
// contains filtered or unexported fields
}
Walker traverses given subtree in specified order. References given subtree, not reusable. Subtree should not be modified while walker is in use.
func (*Walker) Step ¶
func (w *Walker) Step(f WalkerFlags) (stat WalkStat)
Step returns the next element omitting specified parts of subtree. Result.Element is nil if WalkerStop is passed or traversal is finished. When this method returns nil all future calls wil return nil.
type WalkerFlags ¶
type WalkerFlags = int
WalkerFlags instruct walker which parts of subtree must be skipped.
Source Files