Python

3 posts with the tag “Python”

Implementing a Static Single Assigment (SSA) in FAST-Python

Sep 29, 2026

Cyril Ferlicot-Delbecque

Research engineer at Inria

Implementing the SSA of Python in FAST-Python

---

What is SSA?

Static Single Assignment is a program representation where every variable is assigned exactly once. The same logical variable x is renamed into several versions x_1, x_2, … — one per assignment — and each use points to the version that can actually provide its value.

The goal is to make data flow explicit in the AST: instead of “this x is assigned somewhere before”, we get “this x is exactly the value produced by that assignment”.

x = 2        # x_1
print(x)     # uses x_1

x = 3        # x_2
print(x)     # uses x_2

The hard part starts when the value of a variable can come from several assignments depending on the control flow:

if z > 3:
    x = 2     # x_1
else:
    x = 3     # x_2

print(x)      # uses phi(x_1, x_2)

After the merge of the two branches there is no single assignment that produced x: we say x has a phi version phi(x_1, x_2), a virtual assignment stating “the value is x_1 if we came from the first branch, x_2 if we came from the second”. An analysis consuming the SSA can then explore both possible values.

For us, the SSA is the third stage of the pipeline, sitting on top of the two previous stages:

Import → Local resolution → CFG → SSA

It has a hard prerequisite: we must know, for each use, which declaration it refers to (the local resolution stage) and which control-flow paths exist (the CFG stage). If you have not read about the FAST CFG and its visitor, I strongly recommend the Visiting the control-flow graph article first — this blog post is the direct continuation.

---

Architecture: one visitor on top of the CFG

The whole transform lives in a single class, FASTPythonSSAVisitor. Its declaration shows the trick that makes it work: it combines two visiting abilities—

FASTPythonVisitor << #FASTPythonSSAVisitor
  traits: 'FASTCFGTVisitor';
  slots: { #newVariablesMap. #localDeclarations };
  tag: 'CFG/LocalResolver/SSA';
  package: 'FAST-Python-Tools'

• the superclass FASTPythonVisitor brings the language visitor (the visitFASTPyXxx: methods generated from the model, through FASTPyTVisitor);
• the trait FASTCFGTVisitor brings the CFG visitor (the visitCFGXxxBlock: methods that walk the blocks of the CFG, plus the conditional-branch hooks).

So a single accept: can traverse the CFG (visitCFGBlock: and friends) and, when a block contains Python statements, dispatch back to the language-specific visit methods (visitFASTPyAssignment:, visitFASTTCanBeVariable:, …).

The trait is generic and lives in the base FAST project (FAST-Core-Tools), which means any language model can reuse it the same way. It is the same trait-based composition idea as the local resolver, but applied to the CFG.

The state

The visitor has only two instance variables:

• localDeclarations — an IdentitySet of every local declaration that received at least one SSA version while walking the entity. It is the source of the “current active versions” snapshot (see below).
• newVariablesMap — an IdentityDictionary used only during the merge of conditional branches, to accumulate, per branch, the versions that were created inside that branch.

And the entry point is a class-side convenience:

FASTPythonSSAVisitor class >> resolve: aPythonEntity
    ^ self new resolve: aPythonEntity

The three SSA value classes

The versions are not strings, they are first-class objects living in FAST-Core-Tools (again reusable across languages), and they are Moose entities: each version is added to the model, so it is persisted and exported with it.

• FASTAbstractVariableVersionSSA — abstract root. It holds the localDeclaration the version belongs to, and offers the queries we need once the SSA is built: nodes (the accesses directly linked to this version, the bidirectional opposite of ssaVersion), localUses, readAccesses, writeAccesses (restricted to this version), name, isPhi, ssaVariables.
• FASTVariableVersionSSA — a basic version for one assignment. It carries an integer version number, so name answers x_1, x.y_1…
• FASTVariablePhiVersionSSA — a phi version. It carries choices, the collection of versions being merged, so name answers phi(x_1, x_2), and isPhi answers true.

FASTVariableVersionSSA >> name
    ^ String streamContents: [ :s |
          s
              nextPutAll: self localDeclarationName;
              nextPut: $_;
              nextPutAll: version asString ]

FASTVariablePhiVersionSSA >> name
    ^ 'phi(' , ($, join: (choices collect: #name)) , ')'

Nested merges flatten themselves: the phi’s addChoiceToPhi: re-dispatches each choice into the receiving phi, so a phi inside a branch ultimately contributes its own choices to the outer phi.

The links carried on the model

The SSA result is attached to the model through two links defined in FAST-Core-Tools on the trait FASTTCanBeLocalDeclaration (used by FASTTEntity, so available on every FAST entity):

• entity ssaVersion — on any access (read or write) to a variable, the version it is linked to. This is a bidirectional relation: each version exposes the accesses linked to it through its nodes collection.
• declaration activeVersion — on the local declaration, the current version at the current point of the traversal. This is the internal “state variable” of the algorithm: it is bumped at each assignment and replaced by a phi at each merge. It stays a plain attribute.

FASTTCanBeLocalDeclaration >> activeVersion
    ^ self attributeAt: #activeVersion ifAbsent: [ nil ]

FASTTCanBeLocalDeclaration >> ssaVersion
    <FMProperty: #ssaVersion type: #FASTAbstractVariableVersionSSA opposite: #nodes>
    ^ self attributeAt: #ssaVersion ifAbsent: [ nil ]

The SSA is then a traversal that, at every write, creates a version, adds it to the model, and sets it as activeVersion; at every read, copies activeVersion into ssaVersion of the access.

---

The pipeline inside resolve:

FASTPythonSSAVisitor>>#resolve: is deliberately buildable in your own project step by step:

FASTPythonSSAVisitor >> resolve: aFASTBehaviouralEntity
    "First we do a local resolution so that each entity is linked to its
     local declaration."
    FASTPythonLocalResolverVisitor resolve: aFASTBehaviouralEntity.

    "Then we build the CFG to know the different paths in the entity."
    cfg := aFASTBehaviouralEntity cfg.

    "And lastly, I can build the SSA now that I have the CFG and the
     local declarations."
    self visit: cfg

Three stages, three small lines. The local resolution is done inside the SSA visitor only for convenience; you can equally run it beforehand.

---

Producing the SSA versions

The core: visitFASTTCanBeVariable:

Just like the local resolver, the SSA logic is concentrated on the trait FASTTCanBeVariable, caught in a single visit method for every node kind that can be a variable (identifier, attribute access, subscript, walrus):

FASTPythonSSAVisitor >> visitFASTTCanBeVariable: aTCanBeVariable

    aTCanBeVariable isVariableWriteAccess
        ifTrue: [ self handleNewAssignemntTo: aTCanBeVariable ]
        ifFalse: [
            aTCanBeVariable localDeclaration isNonLocalDeclaration ifFalse: [
                "Subscript is a special case since it is not directly assigned.
                 So the first read acts as a new declaration."
                (aTCanBeVariable isSubscript
                     and: [ aTCanBeVariable localDeclaration activeVersion isNil ])
                    ifTrue: [ self handleNewAssignemntTo: aTCanBeVariable ]
                    ifFalse: [ aTCanBeVariable ssaVersion: aTCanBeVariable localDeclaration activeVersion ] ] ].

    super visitFASTTCanBeVariable: aTCanBeVariable

The rule is a direct SSA translation of the local resolver’s “write declares, read binds”:

• write access → create a new version (handleNewAssignemntTo:);
• read access → copy the declaration’s activeVersion into the access’s ssaVersion;
• read of an unresolved name (localDeclaration isNonLocalDeclaration) → nothing. print, len, imported functions and variables have no declaration in the model, so they get no version (ssaVersion stays nil);
• first read of a subscript whose declaration has no version yet → it behaves like a declaration: the first x[3] read is treated as an assignment (mirroring the local-resolver convention), so its version is created there.

Creating a version

FASTPythonSSAVisitor >> handleNewAssignemntTo: aFASTEntity
    aFASTEntity ssaVersion: ((self createVariableVersionFor: aFASTEntity)
                 newVersionNumber;
                 yourself)

FASTPythonSSAVisitor >> createVariableVersionFor: aFASTEntity
    | newSSA |
    newSSA := FASTVariableVersionSSA for: aFASTEntity.
    aFASTEntity mooseModel add: newSSA.
    aFASTEntity lastSSAVersion ifNotNil: [ :lastSSA | newSSA version: lastSSA version ].

    aFASTEntity localDeclaration activeVersion: newSSA.
    localDeclarations add: aFASTEntity localDeclaration.
    ^ newSSA

FASTVariableVersionSSA for: aFASTEntity records aFASTEntity localDeclaration as the declaration the version belongs to. Then:

1. the new version is added to the model — the versions are Moose entities, so this makes them persistent and exported with the model;
2. the version number is seeded from lastSSAVersion — the active version of the previous declaration of the same name, chased through the local-resolver shadowing chain: it is what makes x_1 then x_2 even when an unrelated def x(): was declared in between;
3. the new version becomes the activeVersion of the declaration;
4. the declaration is added to localDeclarations (so the “snapshot” of active versions, used for the branches, sees it);
5. newVersionNumber bumps the integer — version := version + 1 — and the result is stored as the write access’s ssaVersion.

FASTPyEntity >> lastSSAVersion
    "scrolling the shadowing chain of the declaration to find a previous version"
    | entity |
    entity := self localDeclaration.
    [ entity isNotNil ] whileTrue: [
        entity activeVersion ifNotNil: [ :version | ^ version ].
        entity := entity shadowing ].
    ^ nil

---

Reordering the visits: the order matters for SSA

The generated visitor visits the children of a node in metamodel order. For the SSA, that order is often wrong because a read must be resolved against the versions before the node, and a write must only bump the version after its right-hand side has been read. We overwrite the generated visit methods in four places.

Assignments: the right side comes first

This is the most important one. In the metamodel, the left of an assignment comes before its right. For the SSA we must invert:

visitFASTPyAssignment: anAssignment
    "Visiting the right field before the left because the variables at the
     right should be linked to the previous assignment."
    self visitFASTPyTAssignable: anAssignment.
    self visitFASTPyExpression: anAssignment.

    self visitEntity: anAssignment right.
    self visitEntity: anAssignment left.
    self visitEntity: anAssignment type

Consider x = x + 1. In metamodel order we would visit the left x first: it would create x_2 and set it as activeVersion, and then the x in x + 1 would read — wrongly — the new x_2. By visiting right before left, the read sees x_1 and the write bumps afterwards.

Function definitions: parameters before the body

Parameters are declarations that the body reads, so they have to be visited before the body:

visitFASTPyFunctionDefinition: aFunctionDefinition
    "Reordering so parameters are visited before the statements, in order
     to have all the declarations."
    self visitFASTTWithParameters: aFunctionDefinition.
    self visitEntity: aFunctionDefinition returnType.
    self visitFASTPyTDefinition: aFunctionDefinition.
    self visitFASTPyTWithTypeParameters: aFunctionDefinition.
    self visitFASTPyStatement: aFunctionDefinition

visitFASTPyMethodDefinition: aMethodDefinition
    "We resolve in the same way as functions."
    self visitFASTPyFunctionDefinition: aMethodDefinition

Definitions rebuild their own CFG

A function definition appearing as a statement of the module is inside the module CFG. But the function’s body is a separate control-flow world. When we reach a definition, we therefore rebuild a fresh CFG and restart the traversal on it, so each definition is turned into its own SSA form:

visitFASTPyTDefinition: aTDefinition
    "We need to redo the CFG for definitions."
    | cfg |
    self visitFASTTNamedEntity: aTDefinition.
    self visitCollection: aTDefinition decorators.

    cfg := aTDefinition cfg.
    self visit: cfg

---

Building the phi versions

Where do phi versions come from? The CFG visitor. When FASTCFGTVisitor visits a conditional block, it visits all the branches before the merge, and during that it calls four hooks you can override. Their default implementation in the trait is empty:

preConditionalsBranchesVisitOf: aConditionalBlock          "before the first branch"
preConditionalsBranchVisitOf: block conditional: aConditionalBlock   "before each branch"
postConditionalsBranchVisitOf: block conditional: aConditionalBlock  "after each branch"
postConditionalsBranchesVisitOf: aConditionalBlock         "after all branches, before the merge"

That is exactly the machinery we fill in to build phis. The idea is a three-step protocol:

1. before the branches: snapshot the active versions;
2. after each branch: record which new versions were created by that branch;
3. after all branches: merge, per variable, one version per branch (plus the snapshot version for branches that did not assign it) into a phi.

Step 1 — snapshot before the branches

FASTPythonSSAVisitor >> preConditionalsBranchesVisitOf: aConditionalBlock
    "When we start to visit the branches of a conditional, we create an
     entry for this conditional in the new variables map and we save the
     active versions present before visiting the children."
    newVariablesMap at: aConditionalBlock put: (IdentityDictionary with: #previousVariables -> self currentActiveVersions)

currentActiveVersions is a snapshot of every declaration’s active version at this point:

currentActiveVersions
    ^ localDeclarations collect: #activeVersion

Step 2 — record the new versions of each branch

FASTPythonSSAVisitor >> postConditionalsBranchVisitOf: firstBranchBlock conditional: aConditionalBlock
    "Once we visited a conditional branch, we save the current active
     versions for this branch."
    | mapForConditional |
    mapForConditional := newVariablesMap at: aConditionalBlock.
    mapForConditional at: firstBranchBlock put: (self currentActiveVersions difference: (mapForConditional at: #previousVariables))

The difference is atomic: subtracting the snapshot (#previousVariables) from the current active versions leaves exactly the versions created inside this branch (the ones that were not there before). We store them per branch block.

Step 3 — build the phis and merge

FASTPythonSSAVisitor >> postConditionalsBranchesVisitOf: aConditionalBlock
    "Once we are done visiting a conditional block we can clean the map and build the Phi variables."

    | mapForConditional previousVariables |
    mapForConditional := newVariablesMap at: aConditionalBlock.
    previousVariables := mapForConditional at: #previousVariables.
    mapForConditional removeKey: #previousVariables.
    self producePhiVersionBasedOnPreviousVariables: previousVariables andNewVariableMap: mapForConditional.
    newVariablesMap removeKey: aConditionalBlock

The heavy lifting is in producePhiVersionBasedOnPreviousVariables:andNewVariableMap::

FASTPythonSSAVisitor >> producePhiVersionBasedOnPreviousVariables: previousVariables andNewVariableMap: newVariablesMap
    | declarationsToMerge |
    declarationsToMerge := newVariablesMap values flatten collectAsSet: #localDeclaration.

    declarationsToMerge do: [ :localDeclaration |
        | allVersions |
        "First we collect all the versions to use to produce a new Phi version
         for the current local declaration."
        allVersions := Set new.
        newVariablesMap valuesDo: [ :variables |
            variables
                detect: [ :variable | variable localDeclaration = localDeclaration ]
                ifFound: [ :variable | allVersions add: variable ] ].

        "If not all branches create a new version, we need to add the previous
         version also to the list of variables for the Phi variable. Note that
         it is possible it did not exist before."
        allVersions size = newVariablesMap size ifFalse: [
            previousVariables
                detect: [ :variable | variable localDeclaration = localDeclaration ]
                ifFound: [ :variable | allVersions add: variable ] ].

        self createPhiVersionFor: localDeclaration versions: allVersions ]

Decoding it:

1. declarationsToMerge — the set of distinct local declarations that received at least one new version in some branch;
2. for each such declaration, walk the branch map and gather the one version per branch that belongs to it;
3. if not every branch created a version for it, a branch may fall straight through with the old value — so we also merge in the version that was active before the conditional (from the previousVariables snapshot), if it existed;
4. createPhiVersionFor:versions: then decides.

FASTPythonSSAVisitor >> createPhiVersionFor: localDeclaration versions: allVersions
    "No need to add it to the versions since it was already added by the
     previous versions."
    | phiVersion |
    allVersions size < 2 ifTrue: [ ^ self ]. "No phi if we do not have at least 2 versions"

    phiVersion := FASTVariablePhiVersionSSA for: allVersions.
    allVersions anyOne mooseModel add: phiVersion.
    localDeclaration activeVersion: phiVersion.
    ^ phiVersion

Two guard rails:

• if a single candidate version remains (e.g. only one branch assigns, and merging the previous version produces a single version) there is nothing to merge, so no phi is created — the single version just stays active;
• otherwise a FASTVariablePhiVersionSSA is created with the candidate versions as choices, and becomes the new activeVersion of the declaration — so the reads right after the merge pick it up via the normal “copy activeVersion into ssaVersion” rule.

No need to “attach” anything else: the phi inherits from the version classes, so it knows its localDeclaration and exposes localUses, readAccesses, writeAccesses restricted to the merged versions.

Traced example

if y < 2:
    x = 4     # x_1
else:
    x = 5     # x_2

print(x)      # phi(x_1, x_2)

Walked by the visitor:

1. preConditionalsBranchesVisitOf: → previousVariables snapshot is empty (no version yet).
2. then branch: x = 4 → handleNewAssignemntTo: creates x_1, becomes active.
3. postConditionalsBranchVisitOf: → branch recorded with {x_1}.
4. else branch: x = 5 → creates x_2, becomes active.
5. postConditionalsBranchVisitOf: → branch recorded with {x_2}.
6. postConditionalsBranchesVisitOf: → declaration merged: {x_1} from branch 1, {x_2} from branch 2 → both branches assigned, so no previous version added → allVersions = {x_1, x_2} → phi created, becomes active.
7. print(x) is read after the merge → ssaVersion := activeVersion → phi(x_1, x_2). The use is linked to both possible values.

And the case where a branch does not assign the variable:

x = 3       # x_1
if y < 2:
    function()   # no assignment of x
else:
    x = 4   # x_2

print(x)    # phi(x_1, x_2)

Step 6 here: branch 2 introduced x_2 only, and branch 1 introduced none for x → allVersions starts as {x_2}, its size (1) is not the number of branches (2) → we add the previous version x_1 from the snapshot → allVersions = {x_1, x_2} → phi. Correct: if the first branch is taken, x still holds the old value.

If the assignment happens in a single branch and no previous version exists, then allVersions ends up with a single element → no phi, and the reads just use that single version — matching the (correct) semantics that the variable is simply that assignment in all reachable paths.

---

Querying the result

Once the SSA is built, the model can be queried directly:

• access ssaVersion — the version of the access: a FASTVariableVersionSSA or a FASTVariablePhiVersionSSA (or nil for unresolved names and non-local declarations).
• access ssaName — its pretty name, e.g. x_1, x.y_2, phi(x_1, x_2).
• version nodes — the accesses directly linked to this version through ssaVersion (the bidirectional opposite).
• version localUses / version readAccesses / version writeAccesses — the accesses for this specific version (in the phi case, over all its choices).
• model allSSAVersions / model allResolvedVariableVersions — all the versions of the model, the latter without duplicates.
• variable allSSAVersions / variable allSSABasicVersions — all versions of one variable, the latter without the phis.

(printCall arguments first) ssaVersion name.          "phi(x_1, x_2)"
(printCall arguments first) ssaVersion localUses size.

The full API is documented in the Exploiting the SSA section of analysis.md.

---

Known limits

The SSA inherits the limitations of the two stages it sits on:

• Instance variables (self.x) cannot be treated correctly: there is no declaration of them, and we do not know the order in which methods are invoked.
• Subscripts are matched by their source code, so x[a] and x[b] are conflated — and the whole “first read acts as a declaration” convention is a workaround, not a real answer.
• Non-local declarations get no version: unresolved and imported names are invisible to the SSA.
• Attribute access chains are not tracked (a = x.y then a.z is not linked to x.y.z).

You will find these documented in the Limitations section.

---

Quick start

"Import"
model := FASTPythonImporter parseFile: aFile.

"Full pipeline: local resolution is done inside"
FASTPythonSSAVisitor resolve: model allFunctionDefinitions first.

"Or explicitly, step by step"
model := FASTPythonImporter parseFile: aFile.
FASTPythonLocalResolverVisitor resolve: model module.
model allFunctionDefinitions first cfg.
FASTPythonSSAVisitor resolve: model allFunctionDefinitions first.

The SSA requires Python 3 scoping, like the local resolver it builds on.

---

Advice for implementing SSA in your own FAST project

1. Reuse the generic machinery. FASTCFGTVisitor, FASTVariableVersionSSA, FASTVariablePhiVersionSSA and the version queries live in the base FAST project (FAST-Core-Tools). You should only have to write the language-specific part: the visitX: rules for your nodes and the branch hooks.
2. The write/read rule is your whole core. One visit on the trait “can be a variable” (read → copy active version, write → create version) is enough, provided the local resolution already linked uses to declarations.
3. Drive phis from the CFG hooks, not by scanning. The four pre/postConditionals* hooks give you the branch boundaries for free. Snapshot before, record per branch, merge after — that protocol is generic.
4. Order your visits so reads see the old version. The metamodel order is a trap: reorder assignments (right before left), functions (parameters before body), and anything that mixes declaration and use.
5. Give each access a version and each declaration a “current version” attribute. A ssaVersion relation (bidirectional with nodes) and an activeVersion attribute on FASTTCanBeLocalDeclaration were enough. Make the versions Moose entities and add them to the model so they are persisted and exported.
6. Make the versions first-class objects, not strings. Give them a localDeclaration, name, and ssaVariables/choices; the query API (localUses, readAccesses, …) then comes almost for free on the abstract root.
7. Handle your “no declaration” case explicitly. In Python, unresolved/imported names simply get no version. Decide early what your language’s equivalent is (a non-local placeholder, an explicit global scope…).

The FAST-Python sources you will want to look at: FASTPythonSSAVisitor (this post is a guided read of it), the FASTCFGTVisitor trait and the FAST*VersionSSA classes in FAST-Core-Tools, and the SSA tests in FASTPythonSSATest.

---

Moving this implementation to FAST

This implementation currently lives in FAST-Python, but almost everything in it could move to the base FAST project in the future.

The language-specific part is surprisingly thin. Given a CFG, a local resolution, and a model whose variables use the FASTTCanBeVariable trait, this SSA implementation gives you almost everything for free:

• the version classes (FASTVariableVersionSSA, FASTVariablePhiVersionSSA) and the FASTCFGTVisitor trait already live in FAST-Core-Tools;
• the write/read rule is a single visit method on FASTTCanBeVariable;
• the phi building runs on the generic CFG hooks.

So, for a new language, there is almost nothing more to do: mostly override the few visitX: methods where the metamodel order is wrong for SSA — assignments (right before left), functions (parameters before body), and definitions (rebuild their own CFG) — to reorder the visits.

Tags:

• FAST
• SSA
• Python

Implementing the Local Resolver of Python in FAST-Python

Sep 16, 2026

Cyril Ferlicot-Delbecque

Research engineer at Inria

Implementing the Local Resolver of Python in FAST-Python

The goal of this blog post is to explain how I implemented a local resolver for FAST-Python. FAST-Python is on of the hardest project to implement this kind of algo, so reading this should help implementing any other local resolver for other languages.

---

What is local resolution?

Local resolution is a symbol resolution pass: it links each named entity to the entity that declares it. In other words, for every occurrence of a name — read, write, call, import — it answers the question “where does this name come from?”.

In FAST-Python, after the model is imported from source, running the local resolver produces a model where every name usage points to its local declaration:

x = 1        # this is the declaration of `x`
print(x)     # this use of `x` is linked to the declaration above

It is called local because it only resolves declarations that live in the same file/model (in contrast to a global/system resolution that would also resolve calls to external libraries, standard modules, etc.). Once we went through the file, a name that is not declared anywhere in the file gets bound to a special FASTNonLocalDeclaration placeholder — it is a declaration for the model, but we know it refers to something outside.

Local resolution is the foundation on top of which our other analyses are built such as the Static Single Assignment (SSA). Without it, you cannot even tell whether two x in the code are the same variable. You can’t even say if a FASTPyIdentifier is a variable or not.

The API

The result of the resolution is exposed through two accessors available on every FAST entity (they live in the FAST-Core-Tools package of the base FAST project, so they are reusable across languages):

• entity localDeclaration — from any use of a name, returns the entity that declares it (the first assignment, a FASTPyFunctionDefinition, a loop variable, an import…). If the name was not declared in the file, it returns a FASTNonLocalDeclaration.
• declaration localUses — from a declaration, returns all the entities that resolve to it (usages and other declarations that share it).

This is a bidirectional relationship: localUses is the exact inverse information of localDeclaration.

On top of those two, FAST-Python adds a set of convenience queries that only make sense once the resolution is done — and only for nodes that represent variables:

• access allAccesses / allReadAccesses / allWriteAccesses — all the read/write accesses to the same variable.
• access internalAccesses — the attribute accesses and subscripts on the variable (x.y, x[3]).
• access allNodesUsingMe / access allStatementsUsingMe — the statements that use the variable.
• variable isResolvedVariable — true if the node resolves to a local variable declaration (and is not a function, method, import or unresolved name).
• node usedVariables — all the entities in the subtree of the node that resolve to local variables.

The full list is documented in the analysis.md “Querying local resolver information” section.

The accessors above are expressed as #localDeclaration, #localUses, they are attributes in Moose.

For those new to attributes, it’s a way to add data in a MooseEntity even if we do not have a slot for it.

---

Implementation: a Moose visitor

The resolver is implemented as a Moose/FAST visitor: FASTPythonLocalResolverVisitor. It visits a FAST model (a FASTPythonVisitor built on the generated visitor trait FASTPyTVisitor) and inspects/annotates the nodes in place.

If you are not familiar with how the visitor is generated from the model, I strongly recommend reading Improving the Visitor Generator first: it explains how FASTPyTVisitor is produced and how you can override the generated visitX: methods.

The Python problem: there is no declaration of variables

Before we can write a single line of the algorithm, we have to deal with the first (and deepest) Python quirk: there is no declaration of variables.

In Java you get a real declaration:

int x = 1;   // I declare and type `x`

In Python, an assignment is the declaration:

x = 1        # this IS the declaration of `x`

There is no keyword, no type, no way to distinguish “declare a fresh variable” from “reassign an existing one” syntactically — the same syntax x = ... does both. The resolver has to decide, and the decision is purely lexical reasoning about scopes and order, with no syntactic marker to lean on. Concretely:

• The first assignment in a scope is the declaration. The resolver must therefore know the order in which things appear, and which construct “creates” a scope.
• Parameters are declarations: def f(x): ... declares x as the function’s parameter. They are semantically the first assignment in the function’s scope.
• Walrus operators (x := ...) declare x inline, even inside an expression or an if condition.
• A for ... in ... loop declares its target variable — but only the first time; it must be a declaration when the variable is not already known in the scope.
• Augmented assignments (x += 1) are uses + writes to the same variable.
• For clauses in a list comprehension.

In our implementation this all boils down to a single rule expressed in visitFASTTCanBeVariable: (see below): a write access declares and bind, a read access binds. Everything else is scope management around that rule.

Note

A note on “first write access”: the “declaration” is the lexically first write access (or parameter, or walrus) in a scope — but not necessarily the first at runtime.A variable assigned inside a branch that is not taken, or behind a condition that is false, is still the declaration for the resolver. This may sound wrong if you think of declarations as a runtime concept, but local resolution is not about execution semantics: its purpose is to link all the entities that represent the same variable in the source. For that purpose, the lexically first declaration is a good enough anchor — it gives us a stable, deterministic reference point for every name in a scope, regardless of control flow.

A scope stack

The whole state of the algorithm is a single instance variable — and the class itself is tiny. Here is the complete class declaration:

FASTPythonVisitor << #FASTPythonLocalResolverVisitor
  slots: { #namesContext };
  tag: 'CFG/LocalResolver/SSA';
  package: 'FAST-Python-Tools'

The superclass is FASTPythonVisitor (from the generated FASTPyTVisitor trait), so all the visitX: methods come for free: we only override the ones where the metamodel visit order differs from the resolution order.

namesContext is a stack of scopes (a Stack of Dictionarys, mapping name -> declaration). It is initialized in initialize:

initialize
    super initialize.
    namesContext := Stack new

The class entry point is trivial:

FASTPythonLocalResolverVisitor class >> resolve: aModule
    ^ self new resolve: aModule

and the instance resolve: wraps everything in one scope and runs the visitor:

resolve: aFASTBehaviouralEntity
    self useNewScopeDuring: [
        "flush attributes in case this is not the first resolution"
        aFASTBehaviouralEntity withAllContainedEntities do: [ :entity | entity resetLocalResolution ].
        aFASTBehaviouralEntity accept: self ] "<== Launch the resolution on the tree"

Scopes are pushed/popped around the constructs that define a new scope (module, function, comprehension), through useNewScopeDuring::

useNewScopeDuring: aBlock
    namesContext push: Dictionary new.
    [ aBlock value ] ensure: [ namesContext pop ]

The core operations

The algorithm is three small operations combined:

1. get — look a name up in the stack of scopes (from top to bottom):

declarationNamed: aName
    namesContext do: [ :scope |
        scope at: aName ifPresent: [ :declaration | ^ declaration ] ].
    ^ nil

2. set / ensure a declaration — put a declaration in the current scope, handling re-declaration and shadowing (see Shadowing):

ensureDeclarationOf: aName declaration: aFASTNode in: scope
    scope
        at: aName
        ifPresent: [ :declaration |
            declaration localResolverKind = aFASTNode localResolverKind
                ifTrue:  [ ^ declaration ]
                ifFalse: [ declaration shadowedBy: aFASTNode.
                           aFASTNode ensureLocalUses.
                           scope at: aName put: aFASTNode ] ]
        ifAbsentPut: [ aFASTNode ensureLocalUses; yourself ]

3. bind — link a use to the existing declaration (creating a FASTNonLocalDeclaration if none is found):

bind: aFASTNode toDeclarationNamed: aName
    ^ self bind: aFASTNode toDeclarationNamed: aName
              ifAbsentUse: [ self ensureNonlocalDeclarationNamed: aName ]

bind: aFASTNode toDeclarationNamed: aName ifAbsentUse: aBlock
    | declaration |
    declaration := (self declarationNamed: aName) ifNil: [ aBlock cull: aFASTNode cull: aName ].
    aFASTNode localDeclaration: declaration.
    declaration addLocalUse: aFASTNode

What happens when no declaration is found

When a read has no matching declaration in any scope, bind:...ifAbsentUse: falls back to ensureNonlocalDeclarationNamed::

ensureNonlocalDeclarationNamed: aName
    ^ self
          ensureDeclarationOf: aName
          declaration: (FASTNonLocalDeclaration new
                   name: aName;
                   yourself)
          in: namesContext first

Note the scope: namesContext first is the bottom of the stack, so a FASTNonLocalDeclaration behaves as if it were declared at module level — reads of an undeclared name in a function and at module level end up in the same place. Also note that the fallback for attribute accesses and subscripts is slightly different (see the heart): declarationForUndeclaredNode:named: creates a local declaration on the first read of a subscript when the receiving variable has a declaration, and only resorts to the non-local declaration otherwise:

declarationForUndeclaredNode: aNode named: aName
    "In case of a subscript, if the receiving variable exists, we consider
     that the first read access to the subscript is the declaration."
    aNode isSubscript ifTrue: [
        aNode value
            localDeclarationifPresent: [ :decl |
                ^ self ensureDeclarationOf: aName
                                declaration: aNode
                                in: namesContext top ]
            ifAbsent: [ "Nothing, just let the non local declaration." ] ].
    ^ self ensureNonlocalDeclarationNamed: aName

The heart: visitFASTTCanBeVariable:

Everything that can be a variable in FAST-Python implements the trait FASTTCanBeVariable (identifiers, attribute accesses, subscripts, walrus…). The visitor intercepts them in one place, and this is where “write declares / read binds” lives:

visitFASTTCanBeVariable: aTCanBeVariable
    aTCanBeVariable isVariableWriteAccess
        ifTrue:  [ self ensureDeclarationOf: aTCanBeVariable
                            named: aTCanBeVariable localDeclarationName
                            declaration: aTCanBeVariable ]
        ifFalse: [ self bind: aTCanBeVariable
                            toDeclarationNamed: aTCanBeVariable localDeclarationName
                            ifAbsentUse: [ :node :name |
                                self declarationForUndeclaredNode: node named: name ] ].

    super visitFASTTCanBeVariable: aTCanBeVariable

Two details make Python specific here:

• localDeclarationName is the name that will be used for scope lookup. It is not always the identifier text: an attribute access and a subscript use their source code as their name, so x.y and x[3] are treated as first-class “variables” (with known limits, see Limitations). Every named entity gets a default from the base FAST project (FASTTNamedEntity>>localDeclarationName returns #name); the Python classes only override it where the name is not the identifier:

"from FAST, the default for any named entity:"
FASTTNamedEntity >> localDeclarationName [ ^ self name ]

"Python overrides:"
FASTPyAttributeAccess >> localDeclarationName [ ^ self sourceCode ]
FASTPySubscript       >> localDeclarationName [ ^ self sourceCode ]

• isVariableWriteAccess decides whether a node is a write access or a read access. It comes from FAST (FASTTEntity>>isVariableWriteAccess), but it delegates to variableDeclaration which is an explicitRequirement — every FAST project must implement it for the node kinds that can be variable write accesses. In FAST-Python, each relevant class provides its own logic to walk up the AST and check whether it sits in a write position:

"FAST core — the API:"
FASTTEntity >> isVariableWriteAccess [
    ^ self variableDeclaration isNotNil
]

FASTTEntity >> variableDeclaration [
    "If I am a node representing a write access, I return the node
     assigning me. Else I return nil."
    ^ self explicitRequirement
]

"FAST-Python — an identifier checks whether it is the left side of
 an assignment, a for-loop target, etc.:"
FASTPyIdentifier >> variableDeclaration [
    | assignedNode |
    assignedNode := self selfOrTopmostAssignableCollection.
    assignedNode parentAssignmentLeft ifNotNil: [ :assignment | ^ assignment ].
    assignedNode parentForStatementLeft ifNotNil: [ :for | ^ for ].
    assignedNode parentForInClauseLeft ifNotNil: [ :clause | ^ clause ].
    ^ super variableDeclaration
]

"Parameters and walrus are their own declarator:"
FASTPyParameter >> variableDeclaration [ ^ self ]
FASTPyWalrus    >> variableDeclaration [ ^ self ]

"Attribute accesses and subscripts check for parentAssignmentLeft:"
FASTPyAttributeAccess >> variableDeclaration [
    self selfOrTopmostAssignableCollection parentAssignmentLeft
        ifNotNil: [ :assignment | ^ assignment ].
    ^ super variableDeclaration
]

"The default on FASTPyEntity returns nil (not a write access):"
FASTPyEntity >> variableDeclaration [ ^ nil ]

The interesting bit: for identifiers, variableDeclaration does not just check the immediate parent — it first walks through tuple/destructuring parents via selfOrTopmostAssignableCollection, so that in (a, b) = (1, 2) the individual a and b correctly return the tuple assignment as their declaration.

---

Reordering the visit, or dealing with Python scoping

Because the visitor is generated (see the visitor generator blog post), it visits the children of a node in the metamodel order. For a resolver, metamodel order is not always resolution order: a construct may declare a name in a part of the syntax that the generated visitor reaches too late (or too early) relative to its uses.

Our main tool is therefore: override the generated visitX: with a manual ordering of a few visitEntity:/visitCollection: calls — and be very careful about when to open a scope, because Python does not create a scope where you would expect one.

Block scoping is inconsistent: if and while

In most block-structured languages you expect:

if (cond) { let y = 3; }
use(y);   // Compile error: y does not exist

Python does not create a scope for blocks. An if, a while, a for body do not introduce a new scope:

if cond:
    y = 3
print(y)      # 3, perfectly valid Python

Combine that with “assignment is the declaration” and you get leaks: a variable assigned inside an if branch or a loop is visible after the block. For the resolver this means no useNewScopeDuring: around branches — a name assigned in the then must be visible in the else and after the whole statement. What we do control is the order, which is important for shadowing: in an if, the semantics are

1. the condition (can use outer variables, and walrus operators can even declare variables!),
2. the then clause,
3. the elif clauses (in order),
4. the else clause.

visitFASTPyIfStatement: anIfStatement
    "visit then - elif(s) -> else"
    self visitFASTTConditionalStatement: anIfStatement.
    self visitFASTPyStatement: anIfStatement.
    self visitEntity: anIfStatement thenClause.
    self visitCollection: anIfStatement elifClauses.
    self visitFASTPyTWithElseClause: anIfStatement

Note that we do not call super here: the point is precisely to produce our own child order instead of the metamodel one.

while statements are similar, but the else clause has to go last (it runs when the loop condition becomes false):

visitFASTPyWhileStatement: aWhileStatement
    self visitFASTTConditionalStatement: aWhileStatement.
    self visitFASTTStatementBlock: aWhileStatement.
    self visitFASTPyStatement: aWhileStatement.
    self visitFASTPyTWithElseClause: aWhileStatement

for loops leak their variable

for i in range(10):
    pass
print(i)      # 9 — the loop variable is still there!

The for ... in ... statement declares its loop variable in the enclosing scope (there is no loop scope). i survives after the loop. So a for is simultaneously a scoping and a declaring construct: the resolver must declare the target (left) in the current scope — no push — and, since that is the declaration, visit it before the iterable and the body:

visitFASTPyForStatement: aForStatement
    self visitEntity: aForStatement left.
    self visitEntity: aForStatement right.
    self visitFASTPyTWithElseClause: aForStatement.
    self visitFASTTStatementBlock: aForStatement.
    self visitFASTPyStatement: aForStatement

Function and method definitions: parameters are declarations

The generated visitor does not visit the parameters before the body — but the parameters are declarations that the body uses. So visitFASTPyFunctionDefinition: manually visits parameters first, wrapped in a new scope, and does not use super:

visitFASTPyFunctionDefinition: aFunctionDefinition
    self ensureDeclarationOf: aFunctionDefinition
        named: aFunctionDefinition name
        declaration: aFunctionDefinition.
    self useNewScopeDuring: [ "do not use super: parameters must be visited before the body"
        self visitFASTTWithParameters: aFunctionDefinition.
        self visitFASTPyTWithTypeParameters: aFunctionDefinition.
        self visitFASTPyStatement: aFunctionDefinition.
        self visitEntity: aFunctionDefinition returnType.
        self visitFASTPyTDefinition: aFunctionDefinition ]

visitFASTPyMethodDefinition: simply delegates to the function one.

Comprehensions: a scope that leaks itself, but not its body

Comprehensions are Python 3’s attempt at “introduce an expression-level scope”, and they only partially succeed:

[x for x in coll]
print(x)      # NameError in Python 3 — x does not leak OUT of the comprehension

In Python 3, the comprehension has its own scope, so the loop variable of its for clause does not escape. But the for clause(s) and the if condition(s) can still see and use variables from the enclosing scope, and the comprehension’s own variable is in scope through the whole comprehension (the body and the conditions can refer to the for clause variables).

That gives you a scope that is neither fully lexical like a function, nor absent like a block. In our implementation, visitFASTPyComprehension: opens a dedicated scope and reorders the visit so that the for clauses are processed before the conditions and the body (otherwise the conditions/body would be visited against the wrong scope):

visitFASTPyComprehension: aComprehension
    self useNewScopeDuring: [
        self visitFASTPyTSplatExpression: aComprehension.
        self visitFASTPyExpression: aComprehension.
        self visitCollection: aComprehension forClauses.
        self visitCollection: aComprehension conditions.
        self visitEntity: aComprehension body ]

We also had to choose a Python version:

Note

The resolver is implemented for Python 3 semantics. In Python 2, comprehensions had no scope at all and their variable leaked to the enclosing scope. We explicitly did not support Python 2 scoping; supporting both would require making the comprehension scoping rule configurable.

Other constructs that declare names

• Imports declare the imported name (or its alias) in the current scope — visitFASTPyImport: ensures a declaration for each imported entity (using alias if present, source code otherwise).
• Walrus operator (x := ...) declares x — visitFASTPyWalrus: ensures its declaration (it can even appear in an if condition).

global and nonlocal statements

Python is one of the rare languages where a function can explicitly opt out of local scoping:

x = 1

def f():
    global x      # `x` is the module-level x, not a local one
    x = 2

def g():
    y = 1
    def h():
        nonlocal y    # `y` is the `y` of `g`, not a new local
        y = 2

These two statements redirect resolution away from the current scope:

• a global x means: “in this scope, x is the module-scope x”. Writes here target the global declaration, they must not create a new local declaration.
• a nonlocal x means: “x is the variable of the nearest enclosing function that defines it”. It is similar to global but with a different target scope.

In the model, a FASTPyGlobalStatement (resp. FASTPyNonlocalStatement) contains a collection of variables, and each FASTPyVariable keeps the inverse parentGlobalStatement / parentNonlocalStatement pointer. That is what the visitor checks in FASTPythonLocalResolverVisitor>>#visitFASTPyVariable: — when visiting a variable that is the target of one of these statements, we change which scope the write will land in:

visitFASTPyVariable: aVariable
    "We handle two specific cases here.
     - global: the variables impacted should act as if they were in the
       global scope. I ensure the variable is in the bottom scope and add
       a copy in the current scope (so that if we assign it, it goes in
       the global and does not create a new local).
     - nonlocal: the variables impacted should act as if they were in the
       first parent scope defining the variable."
    aVariable parentGlobalStatement ifNotNil: [
        namesContext top
            at: aVariable localDeclarationName
            ifAbsentPut: [ self ensureDeclarationOf: aVariable localDeclarationName declaration: aVariable in: namesContext last ] ].

    aVariable parentNonlocalStatement ifNotNil: [
        namesContext allButFirst
            detect: [ :scope | scope includesKey: aVariable localDeclarationName ]
            ifFound: [ :scope | namesContext top at: aVariable localDeclarationName put: (scope at: aVariable localDeclarationName) ]
            ifNone: [ self error: 'Non local statement points a variable that was never defined.' ] ].

    super visitFASTPyVariable: aVariable

Let’s unpack the two branches:

• global — we want a write x = 2 inside the function to target the module-level x. So we look at the bottom scope (namesContext last, the module scope) and, if x is not there yet, we declare it there with the current writing variable as its declaration. Then we copy a reference into the top scope (namesContext top). From then on, any write in this scope simply finds x present in the top scope — ensureDeclarationOf: sees the same kind (#variable = #variable) and keeps the same declaration, so no new local is created and the write silently targets the global one. The copy trick makes the subsequent writes “resolve” without us having to special-case every write site.
• nonlocal — the target scope is not the module but the nearest enclosing function that already defines the name. So we scan namesContext allButFirst (everything except the bottom scope) and re-bind x in the top scope to the existing declaration found there. If no enclosing scope defines the name, this is a Python error (SyntaxError at compile time in real Python), so we raise an error too.

Both branches rely on a nice property of our data structure: the top entry of the stack is always the current scope, and putting a reference to an existing declaration (rather than a fresh node) in the current scope is exactly what redirects future uses.

---

Shadowing in Python

Shadowing is another direct consequence of “no declarations”: in Python, anything named can shadow anything named, in the same scope:

x = 1              # Declaration 1: variable
from os import x   # Declaration 2: import (shadows Declaration 1)
def x():           # Declaration 3: function (shadows Declaration 2)
    pass
print(x)           # links to Declaration 3

The rule we implemented

In ensureDeclarationOf: (see core operations), when a name is re-declared in the same scope, the resolver does not decide based on types (there are none) but on localResolverKind:

• if the new entity has the same kind (e.g. re-assigning a variable): we keep the same declaration and do nothing special. Two x = ... in a row share one declaration. (This is why ensureLocalUses initializes the uses instead of resetting them: several nodes can be declarations of one shared declaration.)
• if the kind is different (a variable shadowed by an import or a function): we create a new declaration, and link the two declarations together.

localResolverKind is not used anywhere else in the resolver — it exists only to drive this decision. Each node kind that can act as a declaration returns its kind, and the base FAST project provides no default because it is purely language-specific:

FASTPyIdentifier          >> localResolverKind [ ^ #variable ]
FASTPyParameter           >> localResolverKind [ ^ #variable ]   "can be reassigned"
FASTPyWalrus              >> localResolverKind [ ^ #variable ]
FASTPyAttributeAccess     >> localResolverKind [ ^ #variable ]
FASTPySubscript           >> localResolverKind [ ^ #subscript ]
FASTPyFunctionDefinition  >> localResolverKind [ ^ #function ]
FASTPyMethodDefinition    >> localResolverKind [ ^ #method ]
FASTPyImport              >> localResolverKind [ ^ #import ]

Two subtleties we hit:

• Parameters are #variable, not a dedicated kind, because they can be reassigned inside the body: def f(x): x = 2 must share the declaration with the parameter, not shadow it.
• FASTPyEntity>>localResolverKind raises an error by default, which catches any node kind that is used as a declaration without having declared its kind — a cheap safety net while extending the metamodel.

The shadowing API

To make shadowing queryable, two back-links were added on the declarations (FASTPyEntity, in FAST-Python-Model, generated via the metamodel generator):

• declaration shadowing — returns the declaration it shadows, or nil.
• declaration shadowedBy — returns the declaration that shadows it, or nil.

Together they form a linked list from the first declaration to the most recent one. Each declaration keeps its own localUses (the set of entities that resolve to it, not to its successors), and usages always resolve to the most recent declaration.

Going back to the example:

varDecl := model module statements first left.      "FASTPyVariable"
importStmt := model module statements second.       "FASTPyImportFromStatement"
funcDecl := model module statements third.          "FASTPyFunctionDefinition"

varDecl shadowedBy.        "=> FASTPyImportFromStatement"
importStmt shadowedBy.     "=> FASTPyFunctionDefinition"
importStmt shadowing.      "=> FASTPyVariable"
funcDecl shadowing.        "=> FASTPyImportFromStatement"

varDecl localUses size.     "1  (just the assignment)"
importStmt localUses size.  "1  (just the import)"
funcDecl localUses size.    "2  (the definition + print(x))"

A caution about “same kind”

Same-kind re-declaration shares the declaration, which also means shadowing’s chain and local uses are independent of the SSA versioning: if you need to know which assignment impacts a particular use, local resolution is not enough — combine it with the SSA pass (it produces one version per assignment). The two analyses are designed to be composed in this pipeline order: Local resolution → CFG → SSA.

---

Known limits and what is left to do

We implemented local resolution for Python, but we focused on variables first, because that is what the CFG/SSA and the reachability analyses needed. Functions, methods and imports are handled in the scope bookkeeping (localResolverKind, reordering in the visitor), but if your mission is a complete Python symbol table, expect more work there (call graph resolution, self/class attributes, closures and bound variables…).

Specific known weaknesses (documented in analysis.md → Limitations):

• Attribute access chains: x.y.z = 3; a = x.y; print(a.z) — a.z should resolve to x.y.z, but it does not (only the source code of the attribute access is used as the name).
• Subscripts are compared by source code: y[x] with different x values are conflated; x[0:4] and x[:4] (semantically equal) are seen as different. Matching the expression instead of the string would fix it.
• Instance variables (self.x) cannot be handled correctly without knowing the order in which methods are invoked.
• Python 2 scoping is not supported (comprehension variables leak in Python 2; we implement Python 3).
• global/nonlocal are handled, but nonlocal errors out if the variable was never defined in an enclosing scope.

Also, one of the future step zould be to make some parts, such as the context stack, generic and push it to FAST so that it can be reused in other FAST projects.

---

Quick start

"Import"
model := FASTPythonImporter parseFile: aFile.

"Resolve"
FASTPythonLocalResolverVisitor resolve: model module.

"Query"
(model allFunctionDefinitions first) localDeclaration.  "a FASTPyFunctionDefinition"

The recommended pipeline for analysis:

model := FASTPythonImporter parseFile: aFile.
FASTPythonLocalResolverVisitor resolve: model module.
model allFunctionDefinitions first cfg.                          "CFG"
FASTPythonSSAVisitor resolve: model allFunctionDefinitions first. "SSA (after resolution)"

The local resolver and SSA require Python 3 scoping.

---

Advice for implementing it in your own FAST project

1. Use the generated visitor, override visitX: selectively. You rarely need to reorder everything — only where the metamodel order differs from the declaration-before-use order (if, for, while, functions, comprehensions).
2. Model a scope stack explicitly. One Stack of Dictionarys was enough for the whole algorithm. Wrap “new scope” sites in a useNewScopeDuring:/[ensure: pop] pair so the stack is popped even on error.
3. Make “what declares a name” explicit and language-aware. For Python: write access declares; read access binds; for target declares in the enclosing scope; comprehensions open a scope; global/nonlocal redirect.
4. Add a localDeclarationName per node kind (it is sourceCode for attribute accesses/subscripts, the identifier name otherwise) — do not hard-code “the name is the text” everywhere.
5. Add a localResolverKind and use it to drive shadowing. It made the Java-free, type-free Python shadowing tractable and gave us a cheap way to keep-or-split declarations.
6. Reset your attributes before re-resolving. We flush localDeclaration/localUses on all contained entities at the start of resolve: so the resolver is idempotent on a model.

The FAST-Python sources you will want to look at: FASTPythonLocalResolverVisitor, the localResolverKind/localDeclarationName extensions in FAST-Python-Tools.

Tags:

• FAST
• Python

Generation of new FAST-Language metamodel using Pharo-Tree-Sitter project

Sep 15, 2025

Aless Hosry

Research engineer at Berger-Levrault

If you’re here, you’re probably interested in creating a new FAST metamodel and expanding Moose to represent the AST (Abstract Syntax Tree) of an additional language. In this post, we explain to you how to generate a “First version” of a new FAST-Language metamodel using the project Pharo-Tree-Sitter. To be able to understand that, we assume you are already familiar with:

• Tree-Sitter
• Pharo-Tree-Sitter
• FAST
• Metamodel generators

If you are not, the following provides a general introduction to these tools/libraries along with references for further details:

• Tree-Sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and efficiently update the syntax tree as the source file is edited. It is able to parse a large variety of programming languages such as Java, C++, C#, Python and many others.

• Pharo-Tree-Sitter is a project developed in Pharo that integrates the original Tree-Sitter parsers and allows visualizing their results (such as ASTs) directly in Pharo. It relies on the FFI protocol, which requires the corresponding libraries depending on the OS (.dll, .so, or .pylib) to be present in Pharo’s VM folders. The project supports parsing several languages, and for some of them (like Python, TypeScript, and C), the library generation is automated. You can find more details in the repository’s README. This is the project that we will use to generate a new FAST-Language metamodel, so you need to download it into your Pharo image.

• FAST means Famix AST. Contrary to Famix that represent application at a high abstraction level, FAST uses a low-level representation: the AST. FAST defines a set of traits that can be used to create new meta-models compatible with Moose tools. When developing a new FAST-Language metamodel, you will rely on these FAST traits to structure your metamodel. However, this does not apply to the “First version” described in this post, but rather to the upgraded versions when you evolve and refine it.

• Metamodel generator is a Pharo library used to create new metamodels such as FAST-Java, Famix-Java, or FAST-Fortran. The generation of any new version of a FAST-Language metamodel can only be achieved through the metamodel generator. As you will see in this post, Pharo-Tree-Sitter enables you to define a new metamodel generator. Once executed, it produces the corresponding FAST-Language metamodel. We will explain this process in more detail in the following sections.

Download Pharo-Tree-Sitter and get the correspondent libraries

First you need to create a Moose image and download Pharo-Tree-Sitter:

Metacello new
  baseline: 'TreeSitter';
  repository: 'github://Evref-BL/Pharo-Tree-Sitter:main/src';
  load.

Once downloaded, you need to make sure that Pharo-Tree-Sitter is able to parse the language that you intend to create the metamodel for. If it is not included, you need to follow the instructions in the readme file of this repository and add the new language. For this blog post we will assume that the language is already supported and we will continue with “Python” 🐍🐍🐍.

To be able to continue, and if this is the first time you’re using this project (Pharo-Tree-Sitter), you need to launch the tests of python in package “TreeSitter-Tests” class “TSParserPythonTest”. This is needed to launch the process of downloading the original tree-sitter and tree-sitter-python projects from GitHub, generating the correspondent libraries and moving them to the correspondent VM folder based on the image version you create: for example Moose 12. If you create another image of another version, you need to launch the tests again to make sure the libraries are again moved to the correspondent folder. Now that you have the libraries, you can parse python code and get an AST, but not FAST-Python model. So in the next step we explain how this can be possible.

Create the first version of the metamodel (FAST-Python in our example)

Don’t worry, not too much to be done, but a snippet of code needs to be written and executed. But we have to explain to you first how it is working.

Explaining package TreeSitter-FAST-Utils

This package contains two main classes: “TSFASTBuilder” and “TSFASTImporter”. For our task we will rely on the first one. The second is used to make the transition between an AST generated by TreeSitter and a FAST-Language model.

“TSFASTBuilder” contains a set of methods responsible for generating a new metamodel generator:

• #tsLanguage: is used to set an instance of TSLanguage, which is TSLanguage python in our case.
• #createMetamodelGeneratorClass is responsible for creating a new package and a class inside. By default, the class name will be “FASTLanguageNameMetamodelGenerator” which is “FASTPythonMetamodelGenerator” and the package name is “FAST-LanguageName-Model-Generator”. This method also calls another one “typesToReify”, which gets all the symbols from the initial TreeSitter project (using an FFI call), and add them as slots in the class definition. These symbols represent the nodes of the language in question like “class” for Python.
• #addPrefixMethodIn: adds #prefix method on the class side of the metamodel generator class. By default it is FASTLanguage.
• #addPackageNameMethodIn: adds #packageName method on the class side of the metamodel generator class. By default it’s ‘FAST-Language-Model’.
• #addSubmetamodelsMethodIn: adds #submetamodels method on the class side of the metamodel generator class, and by default it contains FASTMetamodelGenerator.
• #addDefineClassIn: adds #defineClasses method. In this method slots are defined, starting by #entity then all the symbols imported from TreeSitter.
• #addDefineTraitsIn: adds #defineTraits method. By default FASTTEntity trait is created.
• #addDefineHierarchyIn: adds #defineHierarchy method. By default only #entity relation is defined with FASTTEntity.
• #addDefineRelationsIn: adds #defineRelations method. By default only #entity relations are defined with genericChildren and genericParent.

Voilà, now that you understand how it works, we will show you how to generate one for Python:

tsb := TSFASTBuilder new.
tsb languageName: 'Python'.
tsb tsLanguage: TSLanguage python.
tsb build.

This will generate the metamodel generator. Now that the generator is created you can use it to generate the metamodel:

FASTPythonMetamodelGenerator new generate.

Now you can access the packages and classes created: ‘FAST-Python-Model’ and ‘FAST-Python-Model-Generator’.

From now on you have to handle the metamodel manually. You have to add missing traits (including FAST Traits), properties that should be imported from TreeSitter… You benefit from the importer to handle the parsing on the metamodel side. You can create a package for tools having a #parse method doing this for example:

| parser tsLanguage importer |

Smalltalk image garbageCollect.

parser := TSParser new.
tsLanguage := TSLanguage python.
parser language: tsLanguage.

importer := TSFASTImporter new.
importer tsLanguage: tsLanguage.
importer languageName: 'Python'.
importer originString: string.

^ importer import: (parser parseString: string) rootNode "pay attention to #source: "

You can check FASTTypeScript for more details.

N.B: We recommend you to parse many python examples (you can find a lot in the main project of TreeSitter-Python), using Pharo-Tree-Sitter project. Once parsed you can inspect in Pharo the properties for each node using #collectFieldNameOfNamedChild and find the properties for each one. Then you can add them in #defineRelations of the metamodel.

That’s it for now!

Tags:

• meta-model
• Python