greenwood - v1.0.0

greenwood

Greenwood: a generic trivia-preserving concrete syntax tree

Greenwood provides an immutable concrete syntax tree parameterized by node and token kind, with associated trivia and structural transformation primitives. Greenwood syntax trees are format-agnostic and parsers supply their own kind types.

Function Groups

There are six types of functions in the Greenwood interface:

Each function and type in the Greenwood interface is marked with the appropriate interface group or groups.

Trivia

In syntax tree terminology, “trivia” refers to source text that has no semantic meaning to the language but matters to humans: whitespace, comments, blank lines, and sometimes preprocessor directives. A pure AST discards trivia entirely, but a CST must track it.

Greenwood implements a hybrid concrete syntax tree supporting Roslyn-style Trivia annotations (attached trivia) or Rowan-style green tree child tokens (inline trivia), depending on the choices made by the parser.

Concrete and Abstract Syntax Trees

A concrete syntax tree is a tree representation of the actual tokens for a language, whereas abstract syntax trees are simplified forms discarding anything not necessary for resolution of the language into meaning.

As an example, consider what the abstract syntax tree for the following Gleam code might look like:

/// Tail-recursive Fibonacci sequence implementation
pub fn fib(n: Int) -> Int {
  case n {
    0 | 1 -> n
    _ -> fib(n - 1) + fib(n - 2)
  }
}

This would produce an executable abstract syntax tree like:

Function(
 name: "fib", publicity: Public,
 parameters: [Parameter(name: "n", type: Int)],
 return_type: Int,
 body: Case(
   subjects: [Variable("n")],
   clauses: [
     Clause(patterns: [Int(0), Int(1)], body: Variable("n")),
     Clause(patterns: [Discard], body: BinOp(
       Add,
       Call("fib", [BinOp(Sub, Variable("n"), Int(1))]),
       Call("fib", [BinOp(Sub, Variable("n"), Int(2))]),
     )),
   ],
 ),
)

This could be transformed, but when rendered back to Gleam, the result would drop the leading documentation comment. Comparatively, the concrete syntax tree is about the form of the text and keeps the leading documentation comment. Every single run of contiguous whitespace is accounted for. Everything is assigned a meaning for preservation.

Function(
  trivia: Trivia(leading: [
    DocComment("/// Tail-recursive Fibonacci sequence implementation"),
    Newline("\n")
  ]),
  children: [
    Token(Pub, "pub"),
    Token(Whitespace, " "),
    Token(Fn, "fn"),
    Token(Whitespace, " "),
    Token(Name, "fib"),
    Token(LeftParen, "("),
    Token(Name, "n"),
    Token(Colon, ":"),
    Token(Whitespace, " "),
    Token(UpperName, "Int"),
    Token(RightParen, ")"),
    Token(Whitespace, " "),
    Token(Arrow, "->"),
    Token(Whitespace, " "),
    Token(UpperName, "Int"),
    Token(Whitespace, " "),
    Token(LeftBrace, "{"),
    Token(Newline, "\n"),
    Token(Whitespace, "  "),
    Node(Case, [
      Token(Case, "case"),
      Token(Whitespace, " "),
      Token(Name, "n"),
      Token(Whitespace, " "),
      Token(LeftBrace, "{"),
      Token(Newline, "\n"),
      ...every token including whitespace, pipes, arrows...
    ]),
    Token(Newline, "\n"),
    Token(RightBrace, "}"),
    Token(Newline, "\n"),
  ],
)

The differences are vast: the abstract syntax tree tells you what the code means, but the concrete syntax tree tells you what the source looks like. The source can be reconstructed byte-for-byte from the concrete syntax tree.

This makes a concrete syntax tree useful for editors, language server implementations, and for edit-safe transformations.

Types

Crumb

</>

A breadcrumb: the context needed to reconstruct a parent from a focused child.

cursor

pub type Crumb(kind) {
  Crumb(
    kind: kind,
    trivia: Trivia(kind),
    left: List(Element(kind)),
    right: List(Element(kind)),
  )
}

Constructors

Element

</>

A child of a node: either an interior node or a leaf token.

builder

pub type Element(kind) {
  NodeElement(Node(kind))
  TokenElement(Token(kind))
}

Constructors 

  • NodeElement(Node(kind))

    The constructor for a Node element.

    In parsers or syntax manipulation modules where there’s substantial pattern matching, it may be beneficial to import this aliased to a much shorter name.

    import greenwood.{NodeElement as N}

    builder

  • TokenElement(Token(kind))

    The constructor for a Token element.

    In parsers or syntax manipulation modules where there’s substantial pattern matching, it may be beneficial to import this aliased to a much shorter name.

    import greenwood.{TokenElement as T}

    builder

Node

</>

An interior syntax tree node with typed children and associated trivia.

builder

pub type Node(kind) {
  Node(
    kind: kind,
    children: List(Element(kind)),
    trivia: Trivia(kind),
  )
}

Constructors 

  • Node(
  kind: kind,
  children: List(Element(kind)),
  trivia: Trivia(kind),
)

Token

</>

A leaf node carrying literal source text for the kind.

builder

pub type Token(kind) {
  Token(kind: kind, text: String)
}

Constructors 

  • Token(kind: kind, text: String)

Trivia

</> 
pub type Trivia(kind) {
  Trivia(leading: List(Token(kind)), trailing: List(Token(kind)))
  Bare
}

Constructors 

  • Trivia(leading: List(Token(kind)), trailing: List(Token(kind)))

    Trivia attached to an element: comments, whitespace, blank lines that should travel with the element during transforms. This is the Roslyn approach.

    builder, trivia

  • Bare

    No trivia association. Use this when trivia tokens (whitespace, comments) are stored directly in the node’s children list rather than in separate leading/trailing fields. This is the Rowan approach: the tree is uniform and trivia is just another child element.

    This is also appropriate for nodes where trivia attachment is meaningless (e.g., a synthetic node created during a transform that has no source origin).

    builder, trivia

Zipper

</>

A zipper provides a focused view into a tree (a cursor), allowing navigation and local edits while preserving the ability to reconstruct the whole tree.

The term zipper comes from an article by Gérard Huet in 1997.

Gérard Huet. “The Zipper.” Journal of Functional Programming, 7(5):549–554, September 1997.

cursor

pub type Zipper(kind) {
  Zipper(focus: Node(kind), crumbs: List(Crumb(kind)))
}

Constructors 

  • Zipper(focus: Node(kind), crumbs: List(Crumb(kind)))

Values

all_trivia

</> 
pub fn all_trivia(from node: Node(kind)) -> List(Token(kind))

Get all trivia tokens (leading then trailing) from a node.

trivia

append_child

</> 
pub fn append_child(
  in node: Node(kind),
  child element: Element(kind),
) -> Node(kind)

Append a child to the end of a node’s children.

transformer

down

</> 
pub fn down(zipper: Zipper(kind)) -> option.Option(Zipper(kind))

Move focus to the first child that is a Node.

cursor

down_where

</> 
pub fn down_where(
  zipper: Zipper(kind),
  predicate: fn(Node(kind)) -> Bool,
) -> option.Option(Zipper(kind))

Move focus to the first child Node matching a predicate.

cursor

each

</> 
pub fn each(
  over node: Node(kind),
  with f: fn(Element(kind)) -> Nil,
) -> Nil

Recursively traverse all elements for side effects.

traversal

each_with_depth

</> 
pub fn each_with_depth(
  over node: Node(kind),
  with f: fn(Element(kind), Int) -> Nil,
) -> Nil

Recursively traverse all elements for side effects, with depth.

traversal

filter_children

</> 
pub fn filter_children(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
) -> List(Element(kind))

Find all immediate child elements matching a predicate.

query

find_child

</> 
pub fn find_child(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
) -> option.Option(Element(kind))

Find the first immediate child element matching a predicate.

query

find_descendant

</> 
pub fn find_descendant(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
) -> option.Option(Element(kind))

Find the first descendant matching a predicate. Searches from root to leaves returning the shallowest match.

query

fold

</> 
pub fn fold(
  over node: Node(kind),
  from acc: a,
  with f: fn(a, Element(kind)) -> a,
) -> a

Recursively fold over all elements depth-first.

If you only need to fold over a node’s immediate children, consider using node.children |> list.fold(...) directly.

traversal

fold_with_depth

</> 
pub fn fold_with_depth(
  over node: Node(kind),
  from acc: a,
  with f: fn(a, Element(kind), Int) -> a,
) -> a

Recursively fold over all elements depth-first, with depth. Depth 0 is the immediate children of the provided node (e.g., node.children).

traversal

insert_after

</> 
pub fn insert_after(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
  insert element: Element(kind),
) -> Node(kind)

Insert an element after the first child matching a predicate.

transformer

insert_before

</> 
pub fn insert_before(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
  insert element: Element(kind),
) -> Node(kind)

Insert an element before the first child matching a predicate.

transformer

leading_trivia

</> 
pub fn leading_trivia(from node: Node(kind)) -> List(Token(kind))

Get leading trivia tokens from a node.

trivia

left

</> 
pub fn left(zipper: Zipper(kind)) -> option.Option(Zipper(kind))

Move focus to the nearest sibling Node to the left of the focus.

Returns None if the focus is the root or has no Node sibling to the left.

cursor

left_n

</> 
pub fn left_n(
  zipper zipper: Zipper(kind),
  by n: Int,
) -> option.Option(Zipper(kind))

Move focus n sibling Nodes to the left. Strict: returns None if the move cannot be completed in full.

left_n(z, by: 0) returns Some(z). Negative n flips direction: left_n(z, by: -n) is equivalent to right_n(z, by: n).

cursor

left_where

</> 
pub fn left_where(
  zipper: Zipper(kind),
  predicate: fn(Node(kind)) -> Bool,
) -> option.Option(Zipper(kind))

Move focus to the nearest sibling Node to the left matching a predicate.

Token siblings (whitespace, comments stored inline) are skipped and remain in place between the old and new focus.

cursor

map_children

</> 
pub fn map_children(
  in node: Node(kind),
  with f: fn(Element(kind)) -> Element(kind),
) -> Node(kind)

Map over immediate children of a node.

transformer

map_focus

</> 
pub fn map_focus(
  zipper: Zipper(kind),
  with f: fn(Node(kind)) -> Node(kind),
) -> Zipper(kind)

Apply a transform to the focused node.

cursor

map_tree_down

</> 
pub fn map_tree_down(
  in node: Node(kind),
  with f: fn(Element(kind)) -> Element(kind),
) -> Node(kind)

Recursively map all elements root node first. Child nodes are processed before sibling nodes.

Unlike map_tree_up, this runs the mapping function over the root node first and recurses into the result of the mapping function. It is therefore possible to affect the next iteration with the mapping function.

      A        ← processed first
     / \
    B′  C′     ← processed second
   / \
  D″  E″       ← processed last

transformer

map_tree_up

</> 
pub fn map_tree_up(
  in node: Node(kind),
  with f: fn(Element(kind)) -> Element(kind),
) -> Node(kind)

Recursively map all elements leaf nodes first. Child nodes are processed before sibling nodes.

      A        ← processed last
     / \
    B   C      ← processed second
   / \
  D   E        ← processed first

transformer

node

</> 
pub fn node(
  kind kind: kind,
  children children: List(Element(kind)),
) -> Node(kind)

Create a node without Trivia.

This is the same as Node(kind:, children:, trivia: Bare).

builder

node_element

</> 
pub fn node_element(
  kind kind: kind,
  children children: List(Element(kind)),
) -> Element(kind)

Create a node element without Trivia. This is the same as NodeElement(Node(kind:, children:, trivia: Bare)).

builder

node_element_with_trivia

</> 
pub fn node_element_with_trivia(
  kind kind: kind,
  children children: List(Element(kind)),
  trivia trivia: Trivia(kind),
) -> Element(kind)

Create a node element with Trivia. This is the same as NodeElement(Node(kind:, children:, trivia:)).

builder

node_with_trivia

</> 
pub fn node_with_trivia(
  kind kind: kind,
  children children: List(Element(kind)),
  trivia trivia: Trivia(kind),
) -> Node(kind)

Create a node with Trivia.

This is the same as Node(kind:, children:, trivia:).

builder

prepend_child

</> 
pub fn prepend_child(
  in node: Node(kind),
  child element: Element(kind),
) -> Node(kind)

Prepend a child to the beginning of a node’s children.

transformer

remove_children

</> 
pub fn remove_children(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
) -> Node(kind)

Remove all children matching a predicate.

transformer

replace_child

</> 
pub fn replace_child(
  in node: Node(kind),
  at index: Int,
  with element: Element(kind),
) -> Node(kind)

Replace a child at a given index.

transformer

replace_first

</> 
pub fn replace_first(
  in node: Node(kind),
  where predicate: fn(Element(kind)) -> Bool,
  with replacement: fn(Element(kind)) -> Element(kind),
) -> Node(kind)

Replace the first child matching a predicate.

transformer

</> 
pub fn right(zipper: Zipper(kind)) -> option.Option(Zipper(kind))

Move focus to the nearest sibling Node to the right of the focus.

Returns None if the focus is the root or has no Node sibling to the right.

cursor

right_n

</> 
pub fn right_n(
  zipper zipper: Zipper(kind),
  by n: Int,
) -> option.Option(Zipper(kind))

Move focus n sibling Nodes to the right. Strict: returns None if the move cannot be completed in full.

right_n(z, by: 0) returns Some(z). Negative n flips direction: right_n(z, by: -n) is equivalent to left_n(z, by: n).

cursor

right_where

</> 
pub fn right_where(
  zipper: Zipper(kind),
  predicate: fn(Node(kind)) -> Bool,
) -> option.Option(Zipper(kind))

Move focus to the nearest sibling Node to the right matching a predicate.

Token siblings (whitespace, comments stored inline) are skipped and remain in place between the old and new focus.

cursor

set_focus

</> 
pub fn set_focus(
  zipper zipper: Zipper(kind),
  node node: Node(kind),
) -> Zipper(kind)

Replace the focused node and return the updated zipper.

cursor

set_leading_trivia

</> 
pub fn set_leading_trivia(
  on node: Node(kind),
  trivia tokens: List(Token(kind)),
) -> Node(kind)

Attach leading trivia to a node.

trivia

set_trailing_trivia

</> 
pub fn set_trailing_trivia(
  on node: Node(kind),
  trivia tokens: List(Token(kind)),
) -> Node(kind)

Attach trailing trivia to a node.

trivia

token

</> 
pub fn token(kind kind: kind, text text: String) -> Token(kind)

Create a token. This is the same as Token(kind:, text:).

builder

token_element

</> 
pub fn token_element(
  kind kind: kind,
  text text: String,
) -> Element(kind)

Create a token element. This is the same as Token(kind:, text:).

builder

trailing_trivia

</> 
pub fn trailing_trivia(
  from node: Node(kind),
) -> List(Token(kind))

Get trailing trivia tokens from a node.

trivia

unzip

</> 
pub fn unzip(zipper: Zipper(kind)) -> Node(kind)

Reconstruct the full tree from a zipper by moving up to the root.

cursor

up

</> 
pub fn up(zipper: Zipper(kind)) -> option.Option(Zipper(kind))

Move focus back up to the parent.

cursor

up_n

</> 
pub fn up_n(
  zipper zipper: Zipper(kind),
  by n: Int,
) -> option.Option(Zipper(kind))

Move focus up n parents. Strict: returns None if n is negative or if the cursor would move above the root.

up_n(z, by: 0) returns Some(z).

cursor

zip

</> 
pub fn zip(root: Node(kind)) -> Zipper(kind)

Create a zipper focused on the root node.

cursor

✨ Search Document