Compiler Services: Processing SyntaxTree

This tutorial demonstrates how to get the SyntaxTree (AST)for F# code and how to walk over the tree. This can be used for creating toolssuch as code formatter, basic refactoring or code navigation tools. The untypedsyntax tree contains information about the code structure, but does not containtypes and there are some ambiguities that are resolved only later by the typechecker. You can also combine the SyntaxTree information with the API availablefromeditor services.

NOTE: The FSharp.Compiler.Service API is subject to change when later versions of the nuget package are published

Getting the SyntaxTree

To access the untyped AST, you need to create an instance ofFSharpChecker.This type represents a context for type checking and parsing and corresponds eitherto a stand-alone F# script file (e.g. opened in Visual Studio) or to a loaded projectfile with multiple files. Once you have an instance ofFSharpChecker, you canuse it to perform "untyped parse" which is the first step of type-checking. Thesecond phase is "typed parse" and is used byeditor services.

To use the interactive checker, referenceFSharp.Compiler.Service.dll and open theSourceCodeServices namespace:

#r"FSharp.Compiler.Service.dll"openSystemopenFSharp.Compiler.CodeAnalysisopenFSharp.Compiler.Text

Performing untyped parse

The untyped parse operation is very fast (compared to type checking, which cantake notable amount of time) and so we can perform it synchronously. First, weneed to createFSharpChecker - the constructor takes an argument thatcan be used to notify the checker about file changes (which we ignore).

// Create an interactive checker instanceletchecker=FSharpChecker.Create()

To get the AST, we define a function that takes file name and the source code(the file is only used for location information and does not have to exist).We first need to get "interactive checker options" which represents the context.For simple tasks, you can useGetProjectOptionsFromScriptRoot which infersthe context for a script file. Then we use theParseFile method andreturn theParseTree property:

/// Get untyped tree for a specified inputletgetUntypedTree(file,input)=// Get compiler options for the 'project' implied by a single script fileletprojOptions,diagnostics=checker.GetProjectOptionsFromScript(file,input,assumeDotNetFramework=false)|>Async.RunSynchronouslyletparsingOptions,_errors=checker.GetParsingOptionsFromProjectOptions(projOptions)// Run the first phase (untyped parsing) of the compilerletparseFileResults=checker.ParseFile(file,input,parsingOptions)|>Async.RunSynchronouslyparseFileResults.ParseTree

Walking over the AST

The abstract syntax tree is defined as a number of discriminated unions that representdifferent syntactical elements (such as expressions, patterns, declarations etc.). The bestway to understand the AST is to look at the definitions inSyntaxTree.fsiin the source code.

The relevant parts are in the following namespace:

openFSharp.Compiler.Syntax

When processing the AST, you will typically write a number of mutually recursive functionsthat pattern match on the different syntactical elements. There is a number of elementsthat need to be supported - the top-level element is module or namespace declaration,containing declarations inside a module (let bindings, types etc.). A let declaration insidea module then contains expressions, which can contain patterns.

Walking over patterns and expressions

We start by looking at functions that walk over expressions and patterns - as we walk,we print information about the visited elements. For patterns, the input is of typeSynPat and has a number of cases includingWild (for_ pattern),Named (for<pat> as name) andLongIdent (for aFoo.Bar name). Note that the parsed patternis occasionally more complex than what is in the source code (in particular,Named isused more often):

/// Walk over a pattern - this is for example used in/// let <pat> = <expr> or in the 'match' expressionletrecvisitPattern=function|SynPat.Wild_->printfn"  .. underscore pattern"|SynPat.Named(ident=SynIdent(ident=name))->printfn"  .. named as '%s'"name.idText|SynPat.LongIdent(longDotId=SynLongIdent(id=ident))->letnames=String.concat"."[foriinident->i.idText]printfn"  .. identifier:%s"names|pat->printfn"  .. other pattern:%A"pat

The function is recursive (for nested patterns such as(foo, _) as bar), but it does notcall any of the functions defined later (because patterns cannot contain other syntacticalelements).

The next function iterates over expressions - this is where most of the work would be andthere are around 20 cases to cover (typeSynExpr. and you'll get completion with otheroptions). In the following, we only show how to handleif .. then .. andlet .. = ...:

/// Walk over an expression - if expression contains two or three/// sub-expressions (two if the 'else' branch is missing), let expression/// contains pattern and two sub-expressionsletrecvisitExpressione=matchewith|SynExpr.IfThenElse(ifExpr=cond;thenExpr=trueBranch;elseExpr=falseBranchOpt)->// Visit all sub-expressionsprintfn"Conditional:"visitExpressioncondvisitExpressiontrueBranchfalseBranchOpt|>Option.itervisitExpression|SynExpr.LetOrUse(_,_,bindings,body,_,_)->// Visit bindings (there may be multiple// for 'let .. = .. and .. = .. in ...'printfn"LetOrUse with the following bindings:"forbindinginbindingsdolet(SynBinding(headPat=headPat;expr=init))=bindingvisitPatternheadPatvisitExpressioninit// Visit the body expressionprintfn"And the following body:"visitExpressionbody|expr->printfn" - not supported expression:%A"expr

ThevisitExpression function will be called from a function that visits all top-leveldeclarations inside a module. In this tutorial, we ignore types and members, but that wouldbe another source of calls tovisitExpression.

Walking over declarations

As mentioned earlier, the AST of a file contains a number of module or namespace declarations(top-level node) that contain declarations inside a module (let bindings or types) or insidea namespace (just types). The following function walks over declarations - we ignore types,nested modules and all other elements and look only at top-levellet bindings (values andfunctions):

/// Walk over a list of declarations in a module. This is anything/// that you can write as a top-level inside module (let bindings,/// nested modules, type declarations etc.)letvisitDeclarationsdecls=fordeclarationindeclsdomatchdeclarationwith|SynModuleDecl.Let(isRec,bindings,range)->// Let binding as a declaration is similar to let binding// as an expression (in visitExpression), but has no bodyforbindinginbindingsdolet(SynBinding(headPat=pat;expr=body))=bindingvisitPatternpatvisitExpressionbody|_->printfn" - not supported declaration:%A"declaration

ThevisitDeclarations function will be called from a function that walks over asequence of module or namespace declarations. This corresponds, for example, to a filewith multiplenamespace Foo declarations:

/// Walk over all module or namespace declarations/// (basically 'module Foo =' or 'namespace Foo.Bar')/// Note that there is one implicitly, even if the file/// does not explicitly define it..letvisitModulesAndNamespacesmodulesOrNss=formoduleOrNsinmodulesOrNssdolet(SynModuleOrNamespace(longId=lid;decls=decls))=moduleOrNsprintfn"Namespace or module:%A"lidvisitDeclarationsdecls

Now that we have functions that walk over the elements of the AST (starting from declaration,down to expressions and patterns), we can get AST of a sample input and run the above function.

Putting things together

As already discussed, thegetUntypedTree function usesFSharpChecker to run the firstphase (parsing) on the AST and get back the tree. The function requires F# source code togetherwith location of the file. The location does not have to exist (it is used only for locationinformation) and it can be in both Unix and Windows formats:

// Sample input for the compiler serviceletinput="""  let foo() =    let msg = "Hello world"    if true then      printfn "%s" msg  """// File name in Unix formatletfile="/home/user/Test.fsx"// Get the AST of sample F# codelettree=getUntypedTree(file,SourceText.ofStringinput)

When you run the code in F# interactive, you can entertree;; in the interactive console andsee a pretty printed representation of the data structure - the tree contains a lot of information,so this is not particularly readable, but it gives you a good idea about how the tree looks.

The returnedtree value is again a discriminated union that can be two different cases - one caseisParsedInput.SigFile which represents F# signature file (*.fsi) and the other one isParsedInput.ImplFile representing regular source code (*.fsx or*.fs). The implementationfile contains a sequence of modules or namespaces that we can pass to the function implementedin the previous step:

// Extract implementation file detailsmatchtreewith|ParsedInput.ImplFile(implFile)->// Extract declarations and walk over themlet(ParsedImplFileInput(contents=modules))=implFilevisitModulesAndNamespacesmodules|_->failwith"F# Interface file (*.fsi) not supported."

Summary

In this tutorial, we looked at the basics of working with the untyped abstract syntax tree. This is acomprehensive topic, so it is not possible to explain everything in a single article. TheFantomas project is a good example of a tool based on the untypedAST that can help you understand more. In practice, it is also useful to combine the information herewith some information you can obtain from theeditor services discussed in the nexttutorial.