CodeGen is the process for auto-generating language-specific, strongly-typed ASTs to be used in Semantic. Since it is a critical component of Semantic's language support process, we recommend reading these docs first, as they provide an overview of the pipeline CodeGen supports.
The following diagram outlines the entire language support pipeline.
- Ingest source code. The input to our system is blob data on GitHub.
- Write and generate tree-sitter grammar. During parser generation, tree-sitter produces a
node-types.jsonfile that captures the structure of a language's grammar. Based on this JSON file, we're able to derive datatypes representing surface languages, and then use those datatypes to generically build ASTs. - Provide interface to the C source. The FFI provides us a way to bridge tree-sitter to our Haskell library. For more information, see our docs on adding a new language.
- Automated AST generation via CodeGen APIs. The CodeGen APIs live in the
semantic-astpackage within Semantic, and are explained as follows:- Deserialize. First, we deserialize the
node-types.jsonfile for a given language into the desired shape of datatypes via parsing capabilities afforded by the Aeson library. There are four distinct types represented in the node-types.json file takes on: sums, products, named leaves and anonymous leaves. - Generate Syntax. We then use Template Haskell to auto-generate language-specific, strongly-typed datatypes that represent various language constructs at compile-time. This API exports the top-level function
astDeclarationsForLanguageto auto-generate datatypes at compile-time, which is is invoked by a given language AST module. - Unmarshal. Unmarshaling is the runtime process of iterating over tree-sitter’s parse trees using its tree cursor API, and producing Haskell ASTs for the relevant nodes. We parse source code from tree-sitter and unmarshal the data we get to build these ASTs generically. This file exports the top-level function
parseByteString, which takes source code and a language as arguments, and produces an AST.
- Deserialize. First, we deserialize the
- Generate strongly-typed trees for a given language. Finally, we create
semantic-[LANGUAGE]packages (such as this one for Python). From here, we can call our CodeGen APIs to generate language-specific, strongly-typed trees via the following process:Language.[LANGUAGE].ASTcallsastDeclarationsForLanguage, passing in the relevant language as the argument, and using thegetNodeTypesPathfunction to access the tree-sitter generatednode-types.jsonfile.- This triggers the generation of the exhaustive syntax types contained by that language.
Language.[LANGUAGE]provides the semantic functionality for Python programs, and calls the unmarshal API.- Finally, the unmarshaling process takes the source code input, and auto-generates a tree using the syntax nodes generated in step 2.
The remaining document provides more details on generating ASTs, inspecting datatypes, tests, and information on decisions pertaining to relevant APIs.
To parse source code and produce ASTs locally:
- Load the REPL for a given language package:
cabal new-repl lib:semantic-python
- Set language extensions,
OverloadedStringsandTypeApplications, and import relevant modules,AST.Unmarshal,Source.RangeandSource.Span:
:seti -XOverloadedStrings
:seti -XTypeApplications
import Source.Span
import Source.Range
import AST.Unmarshal
- You can now call
parseByteString, passing in the desired language you wish to parse (in this case Python is given by the argumentLanguage.Python.Grammar.tree_sitter_python), and the source code (in this case an integer1). Since the function is constrained by(Unmarshal t, UnmarshalAnn a), you can use type applications to provide a top-level nodet, an entry point into the tree, in addition to a polymorphic annotationaused to represent range and span. In this case, that top-level root node isModule, and the annotation is given bySpanandRangeas defined in the semantic-source package:
TS.parseByteString @Language.Python.AST.Module @(Source.Span.Span, Source.Range.Range) Language.Python.Grammar.tree_sitter_python "1"
This generates the following AST:
Right (Module {ann = (Span {start = Pos {line = 0, column = 0}, end = Pos {line = 0, column = 1}},Range {start = 0, end = 1}), extraChildren = [R1 (SimpleStatement {getSimpleStatement = L1 (R1 (R1 (L1 (ExpressionStatement {ann = (Span {start = Pos {line = 0, column = 0}, end = Pos {line = 0, column = 1}},Range {start = 0, end = 1}), extraChildren = L1 (L1 (Expression {getExpression = L1 (L1 (L1 (PrimaryExpression {getPrimaryExpression = R1 (L1 (L1 (L1 (Integer {ann = (Span {start = Pos {line = 0, column = 0}, end = Pos {line = 0, column = 1}},Range {start = 0, end = 1}), text = "1"}))))})))})) :| []}))))})]})
Unmarshal defines both generic and non-generic classes. This is because generic behaviors are different than what we get non-generically, and in the case of Maybe, [], and NonEmpty, we prefer non-generic behavior. Since [] is a sum, the generic behavior for :+: would be invoked. The generic :+: expects repetitions represented in the parse tree as right-nested singly-linked lists (ex., (a (b (c (d…))))), rather than as consecutive sibling nodes (ex., (a b c ...d), which is what our trees have. We want to match the latter.
Datatypes are derived from a language and its node-types.json file using the GenerateSyntax API. These datatypes can be viewed in the REPL just as they would for any other datatype, using :i after loading the language-specific AST.hs module for a given language.
:l semantic-python/src/Language/Python/AST.hs
Ok, six modules loaded.
*Language.Python.AST Source.Span Source.Range> :i Module
This shows us the auto-generated Module datatype:
data Module a
= Module {Language.Python.AST.ann :: a,
Language.Python.AST.extraChildren :: [(GHC.Generics.:+:)
CompoundStatement SimpleStatement a]}
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1
instance Show a => Show (Module a)
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1
instance Ord a => Ord (Module a)
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1
instance Eq a => Eq (Module a)
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1
instance Traversable Module
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1
instance Functor Module
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1
instance Foldable Module
-- Defined at /Users/aymannadeem/github/semantic/semantic-python/src/Language/Python/AST.hs:23:1Here is an example that describes the relationship between a Python identifier represented in the tree-sitter generated JSON file, and a datatype generated by Template Haskell based on the provided JSON:
| Type | JSON | TH-generated code |
|---|---|---|
| Named leaf | { |
data TreeSitter.Python.AST.Identifier a |
Annotations are captured by a polymorphic parameter a instead of range/span values.
Examples contains a set of pre-defined, hand-written datatypes for which Template Haskell is not used. Any datatypes among the node types defined here will be skipped when the splice is run, allowing customization of the representation of parts of the tree. While this gives us flexibility, we encourage that this is used sparingly, as it imposes extra maintenance burden, particularly when the grammar is changed. This may be used to e.g. parse literals into Haskell equivalents (e.g. parsing the textual contents of integer literals into Integers), and may require defining TS.UnmarshalAnn or TS.SymbolMatching instances for (parts of) the custom datatypes, depending on where and how the datatype occurs in the generated tree, in addition to the usual Foldable, Functor, etc. instances provided for generated datatypes.
As of right now, Hedgehog tests are minimal and only in place for the Python library.
To run tests:
cabal v2-test semantic-python
CodeGen automates the engineering effort historically required for adding a new language, which included writing a second assignment grammar, along with manually defining data types à la carte.
CodeGen addresses the following challenges posed by the old system:
1. No named child nodes. Tree-sitter’s syntax nodes didn’t provide us with named child nodes, just ordered-lists. In other words, the children were structured as an ordered list, without any name indicating the role of each child. This didn’t match Semantic’s internal representation of syntax nodes, where each type of node has a specific set of named children. This created concerns which meant more Assignment work was necessary to compensate for this discrepancy. For instance, one concern being the way we represent comments, which could be any arbitrary node attached to any part of the AST. But if we had named child nodes, this would allow us to associate comments relative to their parent nodes (for example, if a comment appeared in an if statement, it could be the first child for that if-statement node). However in the old system, comments as well as heredocs could appear anywhere are a source of errors.
2. Time and effort. Our system involves a two-step parsing process, which requires writing two separate language-specific grammars by hand. This is super time-consuming, very developer-intensive, error-prone, and extremely tedious. Assignment requires writing a grammar using parser combinators in Haskell that are really close to the tree-sitter grammar specification. The mechanical nature of this work has, for a long time, begged the question of whether we could automate parts of it. Although we’ve open-sourced Semantic, it’s still tough to leverage community support for adding languages with such a grueling process behind it and a brittle system.
3. Brittle. Each language's Assignment code was tightly coupled to the language's Tree-sitter grammar, and it could break at runtime if we changed the structure of the grammar, without any compile-time error. This meant tracking ongoing changes in tree-sitter. This was also tedious, manual, and error prone. Bumping grammars meant making changes to assignment to accommodate new tree-structures, like nodes that have changed names or positions, etc.
4. Evaluation and a la carte sum types. This also gave us an opportunity to re-think our à la carte datatypes, as well as the evaluation machinery. À la carte syntax types were motivated by a desire to migrate away from a previous representation of syntax in favor of creating a way to better share effort and tooling involved in diffing, and especially in evaluating common fragments of languages: for example, most languages share if statements, functions, while loops, etc. However, the introduction of these syntax types (and the design of the Evaluatable typeclass) made it hard for us to make our analysis sensitive to minor linguistic differences, or even to relate different pieces of syntax together. This is because our à la carte syntax is essentially untyped, in that it enforces only a minimal structure on the tree; but any given subterm can be any element of the syntax, and not some limited subset. This means that a number of Evaluatable instances have to deal with error conditions that in practice can’t occur. For example, function, method, and class declarations have a term for their name field, and thus have to deal with the possibility that the term doesn’t have a declaredName by throwing an error if this arises.