How to find usages of an identifer in an AST?

Given the following AST definition and sample code, what would be the best algorithm to find all the usages of an identifier given its position in the tree ?

AST Definition

type Literal
   = Char  of  char          // character literal
   | String of string        // string literal
   | Integer of  int         // integer literal
   | Float  of  float        // floating point literal   
   | Double of double 
   | Unit

type SrcCol = { startColumn : int; endColumn : int }

type SrcLine = { startLine : int; endLine : int }

type SrcLoc = { srcFilename : string; srcLine : SrcLine; srcColumn : SrcCol }     

type Pat =
    | PVar of 'a
    | PApp of Pat * Pat
    | PLit of Literal    
    | PWithTy of Pat * Type

type Exp 
    = Var      of 'a                           // variable    
    | Lam      of Pat list * Exp       // lambda abstraction
    | App      of Exp * Exp            // application    
    | Let      of Pat * Exp * Exp  // local definition    
    | Lit      of Literal                      // literal 
    | WithTy   of Exp * Type



Sample Code:

let f x = let g x = x                               
          g x 

AST instance of Sample Code
  [Let
                   (PApp
                      (PVar
                         ("f",
                          {srcFilename =
                            "test.fs";
                           srcLine = {startLine = 1;
                                      endLine = 1;};
                           srcColumn = {startColumn = 4;
                                        endColumn = 5;};}),
                       PVar
                         ("x",
                          {srcFilename =
                            "test.fs";
                           srcLine = {startLine = 1;
                                      endLine = 1;};
                           srcColumn = 开发者_Go百科{startColumn = 6;
                                        endColumn = 7;};})),
                    Let
                      (PApp
                         (PVar
                            ("g",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 1;
                                         endLine = 1;};
                              srcColumn = {startColumn = 14;
                                           endColumn = 15;};}),
                          PVar
                            ("x",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 1;
                                         endLine = 1;};
                              srcColumn = {startColumn = 16;
                                           endColumn = 17;};})),
                       Var
                         ("x",
                          {srcFilename =
                            "test.fs";
                           srcLine = {startLine = 1;
                                      endLine = 1;};
                           srcColumn = {startColumn = 20;
                                        endColumn = 21;};}),
                       App
                         (Var
                            ("g",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 2;
                                         endLine = 2;};
                              srcColumn = {startColumn = 10;
                                           endColumn = 11;};}),
                          Var
                            ("x",
                             {srcFilename =
                               "test.fs";
                              srcLine = {startLine = 2;
                                         endLine = 2;};
                              srcColumn = {startColumn = 12;
                                           endColumn = 13;};}))),Lit Unit)]

Basically any kind of enumeration of the tree nodes with a filter for the desired property is what is needed. A depth-first-search (as proposed in another answer) is one way to enumerate the nodes.

However, what one typically wants to know, for a particular identifier in a particular tree node, is what "declared entity" does it represent? Otherwise you find all the references but they are to different entities and that's generally not helpful.

This requires building symbol tables for the application language in question, and then constructing a map between identifier nodes and symbol table entries. A simple enumerator won't do the trick for building symbol tables.

What about a DFS in the child trees of the node where the ident is "created" ?

Take a look at the implementation I hacked over the weekend:

http://fsharprefactor.codeplex.com/

Seems to work :)

FSharpRefactor 0.1 (Preview version) Release on the Visual Studio Gallery.

http://visualstudiogallery.msdn.microsoft.com/339cbae9-911d-4f99-9033-3c3564676f45?SRC=Home

Cheers ;)