Compiler Services: APIs for the untyped AST

The ParsedInput module

As established inTutorial: Expressions, the AST held in aParsedInput valuecan be traversed by a set of recursive functions. It can be tedious and error-prone to write these functions from scratch every time, though,so theParsedInput moduleexposes a number of functions to make common operations easier.

For example:

• ParsedInput.exists
  • May be used by tooling to determine whether the user's cursor is in a certain context, e.g., to determine whether to offer a certain tooling action.
• ParsedInput.fold
  • May be used when writing analyzers to collect diagnostic information for an entire source file.
• ParsedInput.foldWhile
  • Likefold but supports stopping traversal early.
• ParsedInput.tryNode
  • May be used by tooling to get the last (deepest) node under the user's cursor.
• ParsedInput.tryPick
  • May be used by tooling to find the first (shallowest) matching node near the user's cursor.
• ParsedInput.tryPickLast
  • May be used by tooling to find the last (deepest) matching node near the user's cursor.

SyntaxVisitorBase & SyntaxTraversal.Traverse

While theParsedInput module functions are usually the simplest way to meet most needs,there is also aSyntaxVisitorBase-based API that canprovide somewhat more fine-grained control over syntax traversal for a subset of use-cases at the expense of a bit moreceremony and complexity.

Examples

Let's start by introducing a helper function for constructing an AST from source code so we can run through some real examples:

#r"FSharp.Compiler.Service.dll"openFSharp.Compiler.CodeAnalysisopenFSharp.Compiler.TextopenFSharp.Compiler.Syntaxletchecker=FSharpChecker.Create()/// A helper for constructing a `ParsedInput` from a code snippet.letmkTreecodeSample=letparseFileResults=checker.ParseFile("FileName.fs",SourceText.ofStringcodeSample,{FSharpParsingOptions.DefaultwithSourceFiles=[|"FileName.fs"|]})|>Async.RunSynchronouslyparseFileResults.ParseTree

ParsedInput.exists

Now consider the following code sample:

letbrokenTypeDefn="""module Lib// Whoops, we forgot the equals sign.type T { A: int; B: int }"""

Let's say we have a code fix for adding an equals sign to a type definition that's missing one—like the one above.We want to offer the fix when the user's cursor is inside of—or just after—the broken type definition.

We can determine this by usingParsedInput.exists and passing in the position of the user's cursor:

// type T { A: int; B: int }// ···········↑letposInMiddleOfTypeDefn=Position.mkPos512

Given that cursor position, all we need to do is find aSynTypeDefn node:

letisPosInTypeDefn=// true.(posInMiddleOfTypeDefn,mkTreebrokenTypeDefn)||>ParsedInput.exists(fun_pathnode->matchnodewith|SyntaxNode.SynTypeDefn_->true|_->false)

If the position passed intoParsedInput.exists is not contained in any node in the given AST,but rather is below or to the right of all nodes,ParsedInput.exists will fall back to exploring the nearest branch aboveand/or to the left. This is useful because the user's cursor may lie beyond the range of all nodes.

// type T { A: int; B: int }// ··························↑letposAfterTypeDefn=Position.mkPos528

Our function still returnstrue if the cursor is past the end of the type definition node itself:

letisPosInTypeDefn'=// Still true.(posAfterTypeDefn,mkTreebrokenTypeDefn)||>ParsedInput.exists(fun_pathnode->matchnodewith|SyntaxNode.SynTypeDefn_->true|_->false)

ParsedInput.fold

ParsedInput.fold can be useful when writing an analyzer to collect diagnostics from entire input files.

Take this code that has unnecessary parentheses in both patterns and expressions:

letunnecessaryParentheses="""let (x) = (id (3))"""

We can gather the ranges of all unnecessary parentheses like this:

openSystem.Collections.GenericmoduleHashSet=letadditem(set:HashSet<_>)=ignore(set.Additem)setletunnecessaryParenthesesRanges=(HashSetRange.comparer,mkTreeunnecessaryParentheses)||>ParsedInput.fold(funrangespathnode->matchnodewith|SyntaxNode.SynExpr(SynExpr.Paren(expr=inner;rightParenRange=Some_;range=range))whennot(SynExpr.shouldBeParenthesizedInContextgetLineStrpathinner)->ranges|>HashSet.addrange|SyntaxNode.SynPat(SynPat.Paren(inner,range))whennot(SynPat.shouldBeParenthesizedInContextpathinner)->ranges|>HashSet.addrange|_->ranges)

ParsedInput.tryNode

Sometimes, we might just want to get whatever node is directly at a given position—for example, if the user'scursor is on an argument of a function being applied, we can find the node representing the argument and use its pathto backtrack and find the function's name.

letfunctionApplication="""f x y"""

If we have our cursor ony:

// f x y// ·····↑letposOnY=Position.mkPos25

The syntax node representing the functionf technically contains the cursor's position,butParsedInput.tryNode will keep diving until it finds thedeepest node containing the position.

We can thus get the node representingy and its ancestors (thepath) like this:

letyAndPath=// Some (SynExpr (Ident y), [SynExpr (App …); …])mkTreefunctionApplication|>ParsedInput.tryNodeposOnY

Note that, unlikeParsedInput.exists,ParsedInput.tryPick, andParsedInput.tryPickLast,ParsedInput.tryNode doesnot fall back to the nearest branch above or to the left.

// f x y// ······↑letposAfterY=Position.mkPos28

If we take the same code snippet but pass in a position aftery,we get no node:

letnope=// None.mkTreefunctionApplication|>ParsedInput.tryNodeposAfterY

ParsedInput.tryPick

Now imagine that we have a code fix for converting a record construction expression into an anonymous record constructionexpression when there is no record type in scope whose fields match.

letrecordExpr="""let r = { A = 1; B = 2 }"""

We can offer this fix when the user's cursor is inside of a record expression byusingParsedInput.tryPick to return the surrounding record expression's range, if any.

// let r = { A = 1; B = 2 }// ······················↑letposInRecordExpr=Position.mkPos225

Here, even thoughParsedInput.tryPick will try to cleave to the given position by default,we want to verify that the record expression node that we've come across actually contains the position,since, likeParsedInput.exists,ParsedInput.tryPick will also fall back to the nearest branch above and/orto the left if no node actually contains the position. In this case, we don't want to offer the code fixif the user's cursor isn't actually inside of the record expression.

letrecordExprRange=// Some (2,8--2,24).(posInRecordExpr,mkTreerecordExpr)||>ParsedInput.tryPick(fun_pathnode->matchnodewith|SyntaxNode.SynExpr(SynExpr.Record(range=range))whenRange.rangeContainsPosrangeposInRecordExpr->Somerange|_->None)

We might also sometimes want to make use of thepath parameter. Take this simple function definition:

letmyFunction="""module Liblet myFunction paramOne paramTwo =    ()"""

Imagine we want to grab themyFunction name from theheadPat in theSynBinding.

We can write a function to match the node we're looking for—andnot match anything we'renot looking for (like the argument patterns)—by taking its path into account:

letmyFunctionId=// Some "myFunction".(Position.pos0,mkTreemyFunction)||>ParsedInput.tryPick(funpathnode->// Match on the node and the path (the node's ancestors) to see whether://   1. The node is a pattern.//   2. The pattern is a long identifier pattern.//   3. The pattern's parent node (the head of the path) is a binding.matchnode,pathwith|SyntaxNode.SynPat(SynPat.LongIdent(longDotId=SynLongIdent(id=[ident]))),SyntaxNode.SynBinding_::_->// We have found what we're looking for.Someident.idText|_->// If the node or its context don't match,// we continue.None)

Instead of traversing manually fromParsedInput toSynModuleOrNamespace toSynModuleDecl.Let toSynBinding toSynPat, we leverage the default navigation that happens inParsedInput.tryPick.
ParsedInput.tryPick will short-circuit once we have indicated that we have found what we're looking for by returningSome value.

Our code sample of course only had one let-binding and thus we didn't need to specify any further logic to differentiate between bindings.

Let's consider a second example involving multiple let-bindings:

letmultipleLetsInModule="""module Xlet a = 0let b = 1let c = 2"""

In this case, we know the user's cursor inside an IDE is placed afterc, and we are interested in the body expression of thelast let-binding.

// …// let c = 2// ·····↑letposInLastLet=Position.mkPos65

Thanks to the cursor position we passed in, we do not need to write any code to exclude the expressions of the sibling let-bindings.ParsedInput.tryPick will check whether the current position is inside any given syntax node before drilling deeper.

letbodyOfLetContainingPos=// Some (Const (Int32 2, (6,8--6,9))).(posInLastLet,mkTreemultipleLetsInModule)||>ParsedInput.tryPick(fun_pathnode->matchnodewith|SyntaxNode.SynBinding(SynBinding(expr=e))->Somee|_->None)

As noted above,ParsedInput.tryPick will short-circuit at the first matching node.ParsedInput.tryPickLast can be used to get thelast matching node that contains a given position.

Take this example of multiple nested modules:

letnestedModules="""module Mmodule N =    module O =        module P = begin end"""

By usingParsedInput.tryPick, we'll get the name of the outermost nested module even if we pass in a position inside the innermost,since the innermost is contained within the outermost.

This position is inside moduleP, which is nested inside of moduleO, which is nested inside of moduleN,which is nested inside of top-level moduleM:

// module M//// module N =//     module O =//         module P = begin end// ···························↑letposInsideOfInnermostNestedModule=Position.mkPos628

ParsedInput.tryPick short-circuits on the first match, and since moduleN is the firstnested module whose range contains position (6, 28), that's the result we get.

letoutermostNestedModule=// Some ["N"].(posInsideOfInnermostNestedModule,mkTreenestedModules)||>ParsedInput.tryPick(fun_pathnode->matchnodewith|SyntaxNode.SynModule(SynModuleDecl.NestedModule(moduleInfo=SynComponentInfo(longId=longId)))->Some[foridentinlongId->ident.idText]|_->None)

ParsedInput.tryPickLast

If however we use the same code snippet and pass the same position intoParsedInput.tryPickLast,we can get the name of thelast (deepest or innermost) matching node:

letinnermostNestedModule=// Some ["P"].(posInsideOfInnermostNestedModule,mkTreenestedModules)||>ParsedInput.tryPickLast(fun_pathnode->matchnodewith|SyntaxNode.SynModule(SynModuleDecl.NestedModule(moduleInfo=SynComponentInfo(longId=longId)))->Some[foridentinlongId->ident.idText]|_->None)

If we want the next-to-innermost nested module, we can do likewise but make use of thepath parameter:

letnextToInnermostNestedModule=// Some ["O"].(posInsideOfInnermostNestedModule,mkTreenestedModules)||>ParsedInput.tryPickLast(funpathnode->matchnode,pathwith|SyntaxNode.SynModule(SynModuleDecl.NestedModule_),SyntaxNode.SynModule(SynModuleDecl.NestedModule(moduleInfo=SynComponentInfo(longId=longId)))::_->Some[foridentinlongId->ident.idText]|_->None)

SyntaxTraversal.Traverse

Consider again the following code sample:

letcodeSample="""module Liblet myFunction paramOne paramTwo =    ()"""

Imagine we wish to grab themyFunction name from theheadPat in theSynBinding.

We can create a visitor to traverse the tree and find the function name:

letvisitor={newSyntaxVisitorBase<string>()withoverridethis.VisitPat(path,defaultTraverse,synPat)=// First check if the pattern is what we are looking for.matchsynPatwith|SynPat.LongIdent(longDotId=SynLongIdent(id=[ident]))->// Next we can check if the current path of visited nodes, matches our expectations.// The path will contain all the ancestors of the current node.matchpathwith// The parent node of `synPat` should be a `SynBinding`.|SyntaxNode.SynBinding_::_->// We return a `Some` option to indicate we found what we are looking for.Someident.idText// If the parent is something else, we can skip it here.|_->None|_->None}letresult=SyntaxTraversal.Traverse(Position.pos0,mkTreecodeSample,visitor)// Some "myFunction"

Instead of traversing manually fromParsedInput toSynModuleOrNamespace toSynModuleDecl.Let toSynBinding toSynPat, we leverage the default navigation that happens inSyntaxTraversal.Traverse.
ASyntaxVisitorBase will shortcut all other code paths once a singleVisitXYZ override has found anything.

Our code sample of course only had one let binding and thus we didn't need to specify any further logic whether to differentiate between multiple bindings.

SyntaxTraversal.Traverse: using position

Let's now consider a second example where we know the user's cursor inside an IDE is placed afterc and we are interested in the body expression of the let binding.

letsecondCodeSample="""module Xlet a = 0let b = 1let c = 2"""letsecondVisitor={newSyntaxVisitorBase<SynExpr>()withoverridethis.VisitBinding(path,defaultTraverse,binding)=matchbindingwith|SynBinding(expr=e)->Somee}letcursorPos=Position.mkPos65letsecondResult=SyntaxTraversal.Traverse(cursorPos,mkTreesecondCodeSample,secondVisitor)// Some (Const (Int32 2, (6,8--6,9)))

Due to our passed cursor position, we did not need to write any code to exclude the expressions of the other let bindings.SyntaxTraversal.Traverse will check whether the current position is inside any syntax node before drilling deeper.

SyntaxTraversal.Traverse: using defaultTraverse

Lastly, someVisitXYZ overrides can contain a defaultTraverse. This helper allows you to continue the default traversal when you currently hit a node that is not of interest.Consider1 + 2 + 3 + 4, this will be reflected in a nested infix application expression.If the cursor is at the end of the entire expression, we can grab the value of4 using the following visitor:

letthirdCodeSample="let sum = 1 + 2 + 3 + 4"(*AST will look like:Let (false,  [SynBinding     (None, Normal, false, false, [],      PreXmlDoc ((1,0), Fantomas.FCS.Xml.XmlDocCollector),      SynValData        (None, SynValInfo ([], SynArgInfo ([], false, None)), None,         None),      Named (SynIdent (sum, None), false, None, (1,4--1,7)), None,      App        (NonAtomic, false,         App           (NonAtomic, true,            LongIdent              (false,               SynLongIdent                 ([op_Addition], [], [Some (OriginalNotation "+")]),               None, (1,20--1,21)),            App              (NonAtomic, false,               App                 (NonAtomic, true,                  LongIdent                    (false,                     SynLongIdent                       ([op_Addition], [],                        [Some (OriginalNotation "+")]), None,                     (1,16--1,17)),                  App                    (NonAtomic, false,                     App                       (NonAtomic, true,                        LongIdent                          (false,                           SynLongIdent                             ([op_Addition], [],                              [Some (OriginalNotation "+")]), None,                           (1,12--1,13)),                        Const (Int32 1, (1,10--1,11)), (1,10--1,13)),                     Const (Int32 2, (1,14--1,15)), (1,10--1,15)),                  (1,10--1,17)), Const (Int32 3, (1,18--1,19)),               (1,10--1,19)), (1,10--1,21)),         Const (Int32 4, (1,22--1,23)), (1,10--1,23)), (1,4--1,7),      Yes (1,0--1,23), { LeadingKeyword = Let (1,0--1,3)                         InlineKeyword = None                         EqualsRange = Some (1,8--1,9) })*)letthirdCursorPos=Position.mkPos122letthirdVisitor={newSyntaxVisitorBase<int>()withoverridethis.VisitExpr(path,traverseSynExpr,defaultTraverse,synExpr)=matchsynExprwith|SynExpr.Const(constant=SynConst.Int32v)->Somev// We do want to continue to traverse when nodes like `SynExpr.App` are found.|otherExpr->defaultTraverseotherExpr}letthirdResult=SyntaxTraversal.Traverse(cursorPos,mkTreethirdCodeSample,thirdVisitor)// Some 4

defaultTraverse is especially useful when you do not know upfront what syntax tree you will be walking.
This is a common case when dealing with IDE tooling. You won't know what actual code the end-user is currently processing.

Note: SyntaxVisitorBase is designed to find a single value inside a tree!
This is not an ideal solution when you are interested in all nodes of certain shape.
It will always verify if the given cursor position is still matching the range of the node.
As a fallback the first branch will be explored when you passPosition.pos0.
By design, it is meant to find a single result.