FAST

5 posts with the tag “FAST”

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

Control Flow Graph for FAST Fortran

Mar 8, 2025

Nicolas Anquetil

Moose expert

A Control Flow Graph analysis for FAST Fortran

Control Flow Graphs (CFG) are a common tool for static analyzis of a computation unit (eg. a method) and find some errors (unreachable code, infinite loops)

It is based on the concept of Basic Block: a sequence of consecutive statements in which flow of control can only enter at the beginning and leave at the end. Only the last statement of a basic block can be a branch statement and only the first statement of a basic block can be a target of a branch.

There are two distinctive basic blocks:

• Start Block: The entry block allows the control to enter into the control flow graph. There should be only one start block.
• Final Block: Control flow leaves through the exit block. There may be several final blocks.

The package FAST-Fortran-Analyses in https://github.com/moosetechnology/FAST-Fortran contains classes to build a CFG of a Fortran program unit (a main program, a function, or a subroutine).

Creating the FAST Model

We must first create a FAST model of a Fortran program. For this we need an external parser. We currently use fortran-src-extras from https://github.com/camfort/fortran-src-extras.

To run it on a fortran file you do:

fortran-src-extras serialize -t json -v77l encode <fortran-file.f>

This will produce a json AST of the program that we can turn into a FAST-Fortran AST.

If you have fortran-src-extras installed on your computer, all this is automated in FAST-Fortran

 <fortran-file.f> asFileReference
  readStreamDo: [ :st |
    FortranProjectImporter new getFASTFor: st contents ]

This script will create an array of ASTs from the <fortran-file.f> given fortran file. If there are several program units in the file, there will be several FAST models in this array. In the example below, there is only one program, so the list contains only the AST for this program.

We will use the following Fortran-77 code:

      PROGRAM EUCLID
*     Find greatest common divisor using the Euclidean algorithm
        PRINT *, 'A?'
        READ *, NA
        IF (NA.LE.0) THEN
          PRINT *, 'A must be a positive integer.'
          STOP
        END IF
        PRINT *, 'B?'
        READ *, NB
        IF (NB.LE.0) THEN
          PRINT *, 'B must be a positive integer.'
          STOP
        END IF
        IA = NA
        IB = NB
    1   IF (IB.NE.0) THEN
          ITEMP = IA
          IA = IB
          IB = MOD(ITEMP, IB)
          GOTO 1
        END IF
        PRINT *, 'The GCD of', NA, ' and', NB, ' is', IA, '.'
        STOP
        END

Creating the CFG

From the FAST model above, we will now create a Control-Flow-Graph:

 <FAST-model> accept: FASTFortranCFGVisitor new

The class FASTFortranCFGVisitor implements an algorithm to compute basic blocks from https://en.wikipedia.org/wiki/Basic_block.

This visitor goes throught the FAST model and creates a list of basic blocks that can be inspected with the #basicBlocks method.

There is a small hierarchy of basic block classes:

• FASTFortranAbstractBasicBlock, the root of the hierarchy. It contains #statements (which are FAST statement nodes). It has methods to test its nature: isStart, isFinal, isConditional. It defines an abstract method #nextBlocks that returns a list of basic blocks that this one can directly reach. Typically there are 1 or 2 next blocks, but Fortran can have more due to “arithmetic IF”, “computed GOTO” and “assigned GOTO” statements.
• FASTFortranBasicBlock, a common basic block with no branch statement. If it is final, its #nextBlocks is empty, otherwise it’s a list of 1 block.
• FASTFortranConditionalBasicBlock, a conditional basic block. It may reach several #nextBlocks, each one associated with a value, for example true and false. The method #nextBlockForValue: returns the next block associated to a given value. In our version of CFG, a conditional block may only have one statement (a conditional statement).

You may have noticed that our blocks are a bit different from the definition given at the beginning of the blog-post:

• our “common” blocs cannot have several next, they never end with a conditional statement;
• our conditional blocks can have only one statement.

For the program above, the CFG has 10 blocks.

• the first block is a common block and contains 2 statements, the PRINT and the READ;
• its next bloc is a conditional block for the IF. It has 2 next blocs:
  • true leads to a common block with 2 statements, the PRINT and the STOP. This is a final block (STOP ends the program);
  • false leads to the common block after the IF
• …

Visualize the CFG

As a first analysis tool, we can visualize the CFG. Inspecting the result of the next script will open a Roassal visualization on the CFG contained in the FASTFortranCFGVisitor.

FASTFortranCFGVisualization on: <aFASTFortranCFGVisitor>

For the program above, this gives the visualization below.

• the dark dot is the starting block (note that it is a block and contains statements);
• the hollow dots are final blocks;
• it’s not the case here, but a block may also be start and final (if there are no conditional blocks in the program) and this would be represented by a “target”, a circle with a dot inside;
• a grey square is a comon block;
• a blue square is a conditional block;
• hovering the mouse on a block will bring a pop up with the list of its statements (this relies on the FASTFortranExporterVisitor)

One can see that:

• the start block has 2 associated statements (PRINT and READ);
• there are several final blocks, due to the STOP statements;
• there is a loop at the bottom left of the graph where the last blue conditional block is “IF (IB.NE.0)” and the last statement of the grey block (true value of the IF), is a GOTO.

Other analyses

There are little analyses for now on the CFG, but FASTFortranCFGChecker will compute a list of unreachableBlocks that would represent dead code.

Control flow graphs may also be used to do more advanced analyses and possibly refactor code. For example, we mentioned the loop at the end of our program implemented with a IF statement and a GOTO. This could be refactored into a real WHILE loop that would be easier to read.

This is left as an exercise for the interested people 😉

Adapting to other languages

Building a control flow graph is language dependant to identify the conditional statements, where they lead, and the final statements.

But much could be done in FAST core based on FASTTReturnStatement and a (not yet existing at the time of writing) FASTTConditionalStatement.

Inspiration could be taken from FASTFortranCFGVisitor and the process is not overly complicated. It would probably be even easier for modern languages that do not have the various GOTO statements of Fortran.

Once the CFG is computed, the other tools (eg. the visualization) should be completely independant of the language.

All hands on deck!

Tags:

• Famix-tools
• FAST

Some tools on FAST models

Mar 7, 2025

Nicolas Anquetil

Moose expert

The package FAST-Core-Tools in repository https://github.com/moosetechnology/FAST offers some tools or algorithms that are running on FAST models.

These tools may be usable directly on a specific language FAST meta-model, or might require some adjustements by subtyping them. They are not out-of-the-shelf ready to use stuff, but they can provide good inspiration for whatever you need to do.

Dumping AST

Writing test for FAST can be pretty tedious because you have to build a FAST model in the test corresponding to your need. It often has a lot of nodes that you need to create in the right order with the right properties.

This is where FASTDumpVisitor can help by visiting an existing AST and “dump” it as a string. The goal is that executing this string in Pharo should recreate exactly the same AST.

Dumping an AST can also be useful to debug an AST and checking that it has the right properties.

To use it, you can just call FASTDumpVisitor visit: <yourAST> and print the result. For example:

FASTDumpVisitor visit:
  (FASTJavaUnaryExpression new
    operator: '-' ;
    expression:
      (FASTJavaIntegerLiteral new
        primitiveValue: '5'))

will return the string: FASTJavaUnaryExpression new expression:(FASTJavaIntegerLiteral new primitiveValue:'5');operator:'-' which, if evaluated, in Pharo will recreate the same AST as the original.

Note: Because FAST models are actually Famix models (Famix-AST), the tools works also for Famix models. But Famix entities typically have more properties and the result is not so nice:

FASTDumpVisitor visit:
  (FamixJavaMethod new
    name: 'toto' ;
    parameters: {
      FamixJavaParameter new name: 'x' .
      FamixJavaParameter new name: 'y'} ).

will return the string: FamixJavaMethod new parameters:{FamixJavaParameter new name:'x';isFinal:false;numberOfLinesOfCode:0;isStub:false.FamixJavaParameter new name:'y';isFinal:false;numberOfLinesOfCode:0;isStub:false};isStub:false;isClassSide:false;isFinal:false;numberOfLinesOfCode:-1;isSynchronized:false;numberOfConditionals:-1;isAbstract:false;cyclomaticComplexity:-1;name:'toto'.

Local symbol resolution in an AST

By definition an AST (Abstract Syntax Tree) is a tree (!). So the same variable can appear several time in an AST in different nodes (for example if the same variable is accessed several times).

The idea of the class FASTLocalResolverVisitor is to relate all uses of a symbol in the AST to the node where the symbol is defined. This is mostly useful for parameters and local variables inside a method, because the local resover only looks at the AST itself and we do not build ASTs for entire systems.

This local resolver will look at identifier appearing in an AST and try to link them all together when they correspond to the same entity. There is no complex computation in it. It just looks at names defined or used in the AST.

This is dependant on the programming language because the nodes using or defining a variable are not the same in all languages. For Java, there is FASTJavaLocalResolverVisitor, and for Fortran FASTFortranLocalResolverVisitor.

The tool brings an extra level of detail by managing scopes, so that if the same variable name is defined in different loops (for example), then each use of the name will be related to the correct definition.

The resolution process creates:

• In declaration nodes (eg. FASTJavaVariableDeclarator or FASTJavaParameter),a property #localUses will list all referencing nodes for this variable;
• In accessing nodes, (eg. FASTJavaVariableExpression), a property #localDeclarations will lists the declaration node corresponding this variable.
• If the declaration node was not found a FASTNonLocalDeclaration is used as the declaration node.

Note: That this looks a bit like what Carrefour does (see /blog/2022-06-30-carrefour), because both will bind several FAST nodes to the same entity. But the process is very different:

• Carrefour will bind a FAST node to a corresponding Famix node;
• The local resolver binds FAST nodes together.

So Carrefour is not local, it look in the entire Famix model to find the entity that matches a FAST node. In Famix, there is only one Famix entity for one software entity and it “knows” all its uses (a FamixVariable has a list of FamixAccess-es). Each FAST declaration node will be related to the Famix entity (the FamixVariable) and the FAST use nodes will be related to the FamixAccess-es.

On the other hand, the local resolver is a much lighter tool. It only needs a FAST model to work on and will only bind FAST nodes between themselves in that FAST model.

Round-trip validation

For round-trip re-engineering, we need to import a program in a model, modify the model, and re-export it as a (modified) program. A lot can go wrong or be fogotten in all these steps and they are not trivial to validate.

First, unless much extra information is added to the AST, the re-export will not be syntactically equivalent: there are formatting issues, indentation, white spaces, blank lines, comments that could make the re-exported program very different (apparently) from the original one.

The class FASTDifferentialValidator helps checking that the round-trip implementation works well. It focuses on the meaning of the program independently of the formatting issues. The process is the follwing:

• parse a set of (representative) programs
• model them in FAST
• re-export the programs
• re-import the new programs, and
• re-create a new model

Hopefully, the two models (2nd and last steps) should be equivalent This is what this tool checks.

Obviously the validation can easily be circumvented. Trivially, if we create an empty model the 1st time, re-export anything, and create an empty model the second time, then the 2 models are equivalent, yet we did not accomplish anything. This tool is an help for developers to pinpoint small mistakes in the process.

Note that even in the best of conditions, there can still be subtle differences between two equivalent ASTs. For example the AST for “a + b + c” will often differ from that of “a + (b + c)”.

The validator is intended to run on a set of source files and check that they are all parsed and re-exported correctly. It will report differences and will allow to fine tune the comparison or ignore some differences.

It goes through all the files in a directory and uses an importer, an exporter, and a comparator. The importer generates a FAST model from some source code (eg. JavaSmaCCProgramNodeImporterVisitor); the exporter generates source code from a model (eg. FASTJavaExportVisitor); the comparator is a companion class to the DifferentialValidator that handle the differences between the ASTs.

The basic implementation (FamixModelComparator) does a strict comparison (no differences allowed), but it has methods for accepting some differences:

• #ast: node1 acceptableDifferenceTo: node2: If for some reason the difference in the nodes is acceptable, this method must return true and the comparison will restart from the parent of the two nodes as if they were the same.
• #ast: node1 acceptableDifferenceTo: node2 property: aSymbol. This is for property comparison (eg. the name of an entity), it should return nil if the difference in value is not acceptable and a recovery block if it is acceptable. Instead of resuming from the parent of the nodes, the comparison will resume from an ancestor for which the recovery block evaluates to true.

Tags:

• Famix-tools
• FAST

Carrefour: The bridge between FAMIX and FAST

Jun 30, 2022

Ahmed Zaki BENNECER

Working on data flow analysis project for my internship

Introduction

To analyze software systems, the Famix meta-model provides enough abstraction to understand how models work.

However, when we are interested in details, the FAST (Famix AST) meta-model provides less abstraction and gives us more information about our model (for example expression statements, identifiers etc.).

In some situations, such as modernization/migration projects, we need the binding between the two meta models. And here Carrefour comes in!

Carrefour represents a two-way link between Famix and FAST, it allows one to navigate on the AST and at the same time return to the elements of FAMIX when needed.

Configuration

In this blog, we are going to use a simple snippet of code to simplify and grasp all necessary concepts we should know about FAST & Carrefour & Famix. Consider the MyClass class and the following methodAB method:

class MyClass {
  public int methodAB(int a, int b){
    if (a > b) {
      a = a + 2;
    } else {
      b = 1;
    }
    return b;
  }
}

Let’s prepare the ground for using Carrefour by generating the Famix model of the MyClass class using VerveineJ. Open a code editor and create a new MyClass.java file. Inside the Java file, we add the code above.

To generate the Famix Java model we use VerveineJ by running this command in the MyClass java file directory:

/path/to/VerveineJ/verveinej.sh -format json -o MyClass.json -anchor assoc -autocp ./ ./

PS: Note that Carrefour uses entities & associations as source anchor information, so make sure to add the option -anchor assoc.

Load Carrefour

In this section, we start from the MyClass Famix java model and we build the link between Famix and FAST using Carrefour. First, we need to install Carrefour, for example by running the following script on Moose Playground:

Metacello new
    githubUser: 'badetitou' project: 'Carrefour' commitish: 'v3' path: 'src';
    baseline: 'Carrefour';
    load

Then we import the MyClass model and pick the first class (which is the only class MyClass).

'/path/to/MyClass.json' asFileReference readStreamDo: [ :stream |
    model := FamixJavaModel new importFromJSONStream: stream
  ].
model rootFolder: '/path/to/MyClass/Directory/'.
method := model allModelClasses first.

Now, we call Carrefour to generate the AST (the figure below) and bind the newly created AST with Famix.

method generateFastAndBind

it’s recommended to use generateFastIfNotDoneAndBind instead of generateFastAndBind in complex project and heavy computation when generating AST

Bidirectional binding

To have a complete vision of the meta-models described above, we give the corresponding figures of each meta-model FAST and FAMIX:

Once Carrefour has been called and the binding is done, we will have the first links between the meta-models as follows:

From FAST to Famix

As an example, for the condition level variable (a>b) in FAST we would want its correspondence in FAMIX. To do this, we send the #famixVariable message to the FASTJavaVariableExpression object and we get as returned value the corresponding FAMIX variable.

From Famix to FAST

Now we go in the opposite direction, we will access all the matches of the FAMIX variable a in the FAST meta-model.

To do so, we use the #fastAccesses message as in the figure:

Carrefour also provides the #fastDeclaration API to get where a Famix variable has been declared at the FAST meta-model level.

Conclusion

In conclusion, Carrefour allows us to go back and forth between FAST and FAMIX meta-models. The example used in the blog post is not complex but allowed us to see how to navigate between the two meta-models. In large projects, where there are more initialization, invocation, and relationships between entities Carrefour is crucial to perform deep analysis 💪.

Tags:

• FAST

Load FAST Pharo/Java model

Jun 22, 2022

Ahmed Zaki BENNECER

Working on data flow analysis project for my internship

Introduction

When we are interested in the migration/modernization of projects we are using models of the project and their meta-models. Moose revolves around a powerful Famix meta-model that allows us to do several operations. For instance, previous posts present how to analyze and query a model, visualize a model with plantUML, or create a model, etc.

FAST is a meta-model that helps us understand source code in a less abstract way. Indeed, FAST is based on AST (Abstract Syntax Tree) which is close to the source code. And as the devil is in the details, FAST contains interesting elements when analyzing programs (for example some specific expression or statement), and effectively this is what makes the difference between FAST and Famix. (Consult this overview about the FAST model).

In this blog post we will explain how to load FAST Java and generate a FAST model of Java code. For this we will take ArgoUML, an open-source Java project, as an example.

Overview & Prerequisites

First of all, we have to understand from where we are going to start and where we are going to end up. As already mentioned, we will take the AgroUML’s java code and the goal is to generate the corresponding AST and do analyses on it. To do this, 3 steps are necessary to have the AST as illustrated in the figure below:

1. Parse Java to build a Famix model
2. Load the model into Moose
3. Generate the AST

Before starting, we must download the source code and the Famix model of the ArgoUML project, step 1 of the diagram above (follow this blog for more details).

Configuration

Now, we will import the Famix model from the ArgoUML-0-34.json file in the Models Browser. Then, we should know that the FAST meta-model is specific to a gien programming language, i.e for Pharo code we need FAST for Pharo, for X language code we need the FAST meta-model for the X language. Right now, there are two FAST meta-models: FAST Java and FAST Pharo.

In the following, we will generate the AST of a class (or method) for Pharo/Java code in three different ways: directly from some source code, from a method in Pharo, or from a Famix entity.

FAST Installation

To install FAST Java you can run the following script on Moose Playground:

Metacello new
    githubUser: 'moosetechnology' project: 'FAST-JAVA' commitish: 'v3' path: 'src';
    baseline: 'FASTJava';
    load: 'all'

To install FAST Pharo use the following script:

Metacello new
baseline: 'FASTPharo';
repository: 'github://moosetechnology/FAST-Pharo:v2/src';
load: 'importer'.

Java code as string

In this case, we will use a specialized importer “FAST-Java importer” to import the AST from a method source code. The complete code of the method to import is between single quote (i.e. a Pharo string) in the following code:

JavaSmaCCProgramNodeImporterVisitor new
  parseCodeMethodString: 'public boolean covidTest(Person person) {
    if(testCovid(person) == "POSITIVE"){
      return true;
    } else {
      return false;
    }
  }'

Pharo class or method

The following script imports the method #collect: of Collection :

FASTSmalltalkImporterVisitor new
  runWithSource: (Collection >> #collect:) sourceCode

Generate FastJava model

In this section, we will not proceed as above. Instead, we start from a class/method of the Famix Java model and we will load its FAST representation.

We will add the model to the Playground

We got this:

argoUML034 := MooseModel root at: 1.

We pick any model class from the model:

class := argoUML034 allModelClasses anyOne.

And finally we generate the AST using generateFastJava:

class generateFastJava

Navigating Through AST

One nice way to explore a FAST model is to use the source code and the tree extensions of the inspector. It allows one to navigate in a FAST model and see the code corresponding to each node.

To use it, we start from the Java model loaded above. Then, we select a model method entity. On the right-hand pane of the inspector, select the Tree tab, on the left-hand pane, select the source code extension. The source code is highlighted and the area selected corresponds to the entity selected in the right-hand panel. ( from FAST-Pharo article )

Conclusion

In this post, we saw how to load the AST of a Pharo/Java model using FAST. The FAST model is useful when we need to understand more details about our model (for example identifiers, expression statements .. etc) which are not provided by Famix.

Tags:

• FAST