Lossless, immutable concrete syntax trees for Haskell, modelled on rust-analyzer's Rowan.
A Graft tree keeps every byte of the source: whitespace, comments and malformed fragments are ordinary tokens. You can navigate the tree, find the syntax at a byte offset, edit it and print it back, and everything you didn't touch comes out exactly as it went in. That makes it a base for formatters, refactoring and codemod tools, and language servers. You supply the lexer and parser; Graft supplies the tree.
Graft is experimental. The API may change before 1.0.
Graft is on Hackage. Add it to
your build-depends:
build-depends: graft ^>=0.1Graft follows the PVP: ^>=0.1 accepts every
0.1.x release and no breaking one. To try changes that aren't released yet,
pin a commit in cabal.project:
source-repository-package
type: git
location: https://github.com/andreabedini/graft
tag: <commit>This program builds a tree, finds the number at byte offset 5, replaces it, and prints the source before and after:
{-# LANGUAGE OverloadedStrings #-}
module Main (main) where
import qualified Data.Text.IO as Text
import Graft
import qualified Graft.Build as Build
import qualified Graft.Cursor as Cursor
import qualified Graft.Edit as Edit
import qualified Graft.Green as Green
import qualified Graft.Range as Range
data Kind = Root | Binding | Name | Number | Trivia
deriving (Eq, Show)
-- A parser would emit these events; here they are written by hand.
parsed :: Either BuilderError (GreenNode Kind)
parsed = Build.exec $ Build.node Root $ do
Build.node Binding $ do
Build.token Name "x"
Build.token Trivia " = "
Build.token Number "1"
Build.token Trivia " -- keep\r\n"
main :: IO ()
main = do
tree <- either (fail . show) pure parsed
Text.putStr (Green.renderNode tree)
case Cursor.covering (Range.fromLength 5 1) (Cursor.fromGreen (Node tree)) of
Just number -> do
let edits = [Edit.replace number (Token (Green.token Number "42"))]
edited <- either (fail . show) pure (Edit.apply (Node tree) edits)
Text.putStr (Green.render edited)
Nothing -> fail "nothing at offset 5"It prints:
x = 1 -- keep
x = 42 -- keep
The double space, the comment and the CRLF line ending survive the edit.
Cursor.covering returns the innermost element that contains a range, here
the one byte at offset 5. Cursor.tokenAt 5 would return both tokens that
touch offset 5, " = " and "1", as an editor's caret between them touches
both. Edit.replace describes a change at a cursor, and Edit.apply makes a
list of such changes to the tree they were made on, all at once, sharing
everything the changes don't touch. Edit.textEdits gives the same changes
as edits to the source text, for an editor.
- Green trees (
Graft.Green) are immutable nodes and tokens tagged with your own syntax-kind type. Each node caches its length in UTF-8 bytes and the offset of each child, so length and child lookups don't traverse anything. Green values have no parents or positions, so equal subtrees can be shared, within a tree and between versions of it.Green.foldM,Green.fold,Green.mapandGreen.traversecover a whole tree. - Cursors (
Graft.Cursor) are zippers over a green tree. They know their parent, siblings and absolute byte range, and find tokens by offset. - Edits (
Graft.Edit) are described against a tree through its cursors and made all at once: a plan of replacements, splices, insertions and removals, or a top-down rewrite that replaces elements as it goes. Every decision reads the original tree, unchanged subtrees are shared with it, and a plan also yields the edits to the source text. - Builders (
Graft.Build,Graft.Builder) turn a parser's start/token/finish events into a tree, in a monad or as a pure value. Checkpoints let a parser wrap elements it has already emitted, as an operator-precedence parser needs to. - Typed views (
Graft.Ast) are newtypes over cursors that give your grammar's nodes typed accessors, without building a separate AST. - Byte ranges (
Graft.Range) describe where things are. - Line index (
Graft.LineIndex) converts byte offsets to and from line and column positions, including the UTF-16 columns used by the Language Server Protocol.
Graft exports the types and classes. The functions have short names meant
for qualified import, as in the example: Cursor.parent, Green.node,
Range.start. Several, such as Green.length and Green.map, clash with the
Prelude. All offsets and lengths are TextLength, a count of UTF-8 bytes,
never characters.
- The API documentation of the latest
release gives each function's contract and cost. The introductions to
Graft.Build,Graft.Cursor,Graft.Edit,Graft.AstandGraft.LineIndexeach start with an example: wrapping an operand at a checkpoint, finding a token by offset and reading its ancestors, applying a plan and renaming every matching token in one pass, a typed view with a field, and converting Language Server Protocol positions. examples/ExactUpdate.hsuses typed views to change a number's value while keeping its spelling (001stays001if the value doesn't change).docs/architecture.mdexplains the design, how it differs from Rowan, and what is left to do.docs/performance.mdrecords benchmark results, andbench/README.mdexplains how to reproduce them.CONTRIBUTING.mddescribes how to build and test Graft, and how releases are made.
MIT. Graft is a port of ideas from Rowan, which is MIT or Apache-2.0; see NOTICE and licenses/ROWAN-MIT.