Module tree 

Tree structures for representing kind trees (green and red trees). Red-green tree implementation for efficient kind tree representation.

This module provides the core red-green tree data structures that enable efficient incremental parsing and kind tree manipulation. The red-green tree architecture separates immutable structure (green) from position-aware representation (red), enabling optimal sharing and incremental updates.

Key Components

• Green Trees: Immutable, position-agnostic kind tree nodes that can be cached and shared across different parse trees
• Red Trees: Position-aware kind tree nodes computed from green trees with absolute offsets for error reporting and diagnostics
• Green Builder: Utility for constructing green trees incrementally

Architecture

The red-green tree design enables:

• Incremental Parsing: Only re-parse changed regions of source code
• Memory Efficiency: Share immutable green nodes across parse trees
• Position Tracking: Provide accurate source locations for diagnostics
• Performance: Minimize allocations through reference counting and caching

Structs

Arc

An atomically reference counted shared pointer

GreenBuilder

Green tree builder for constructing nodes from child elements.

GreenLeaf

A green leaf kind that stores only kind and length.

GreenNode

A green node that contains child elements without parent pointers.

IncrementalCache

Incremental cache for preserving old green trees and optional lexical caches.

RedChildren

Iterator over the child elements of a red node.

RedLeaf

A red leaf kind with absolute position information.

RedNode

A red node that wraps a green node with absolute offset information.

Enums

GreenTree

A green tree element - either a node or a leaf kind.

RedTree

A red tree element with absolute position information.