[news.eclipse.technology.imp] Re: IMP support for multplei ASTs

["Robert M. Fuhrer" <rfuhrer@xxxxxxxxxxxxxx>]

Mattias Felt wrote:
> Hello,
>
> In my IDE compilation unit has its own AST.  But each project consists of 
> several
> compilation units (e.g. files), so to be able to do some kind of semantic 
> analysis several
> AST must be analysed. I can't see how IMP (LPG?) can help me with this.
>
> Any thoughts ideas would be appreciated.

Hi there,

The standard (scalable) way of doing this is to process each AST in turn 
to produce some sort of "digested" data structures that describe the 
salient characteristics of each compilation unit/type/function/etc. This
representation should be space-efficient enough to be able to fit 
however many compilation units you might find in a user's workspace, or 
at least as many compilation units as you need to process for the 
particular analysis in question. You then run the core of your analysis 
over this digested representation. One needs to take care to save enough 
information in the "digested" form to correlate back to the ASTs/source.
[Saving source extents for the relevant entities is typically enough.]

The representation might be a dictionary of types, a list of defined or 
referenced variables/functions, 3-address code for function bodies, or
whatever you need.

To help with this, the IMP's "PDB" (Program DataBase) plugin 
org.eclipse.imp.pdb.values provides persistable representations and 
operators for a variety of types that are useful for program analysis, 
e.g. sets, relations, maps, and so on.

The PDB is intended to be fairly CPU- and memory-efficient, and can be
used, for example, to persist indices in support of indexed search.

We're actively working on the PDB (particularly with our colleagues at
CWI).

The other area of active development in this space is the declarative
language "Rascal", the result of some nice work at CWI, which we intend
to make available as part of IMP in the not-too-distant future. Rascal
combines both AST pattern matching and computations over the kinds of
data structures that the PDB supports. As a result, it can be used for
both "fact extraction" and analysis per se.

I don't believe Rascal is ready for prime time yet, but it's getting
there. In the meantime you can write code against the PDB API.

If you tell us more about the kind of analysis you're interested in,
I might be able to provide more specific guidance.

--
Cheers,
  -- Bob

--------------------------------
Robert M. Fuhrer
Research Staff Member
Programming Technologies Dept.
IBM T.J. Watson Research Center

IDE Meta-tooling Platform Project Lead (http://www.eclipse.org/imp)
X10: Productive High-Performance Parallel Programming (http://x10.sf.net)