Inferno  0.2
identifier_tracker.cpp
Go to the documentation of this file.
00001 #include "common/common.hpp"
00002 #include "clang/Parse/Parser.h"
00003 #include "clang/Parse/DeclSpec.h"
00004 #include "clang/Parse/Scope.h"
00005 #include "identifier_tracker.hpp"
00006 
00007 
00008 IdentifierTracker::IdentifierTracker( shared_ptr<Node> g ) :
00009     global( g )
00010 {
00011     shared_ptr<TNode> ts( new TNode );    
00012     ts->cs = NULL;
00013     ts->parent = shared_ptr<TNode>(); 
00014     ts->II = NULL;
00015     ts->node = g;
00016     tnodes.push_back( ts );
00017     TRACE("Global tnode %s\n", ToString(ts).c_str() );
00018     scope_stack.push( ts );
00019 }
00020 
00021 shared_ptr<IdentifierTracker::TNode> IdentifierTracker::Find( shared_ptr<Node> node )
00022 {
00023     ASSERT( node );
00024     shared_ptr<TNode> found;
00025     for( int i=0; i<tnodes.size(); i++ )
00026     {
00027         //TRACE("%d of %d T%p\n", i, tnodes.size(), tnodes[i].get() );
00028         if( tnodes[i]->node == node )
00029             return tnodes[i];
00030     }
00031     
00032     return shared_ptr<TNode>();
00033 }
00034 
00035 void IdentifierTracker::PushScope( clang::Scope *S, shared_ptr<Node> n )
00036 {
00037     shared_ptr<TNode> ts;
00038     if( n )
00039     {
00040         ts = Find( n );
00041     }
00042     else
00043     {
00044         ts = shared_ptr<TNode>( new TNode );    
00045         ts->cs = NULL;
00046         ts->parent = shared_ptr<TNode>(); 
00047         ts->II = NULL;
00048         ts->node = shared_ptr<Node>();
00049     }
00050         
00051     ASSERT( ts );
00052     PushScope( S, ts );    
00053 }
00054 
00055 
00056 void IdentifierTracker::PushScope( clang::Scope *S, shared_ptr<TNode> ts )
00057 {
00058     // If scope has no decls, clang will not invoke ActOnPopScope()
00059     // so we set a non-NULL rubbish value in there whenever we push, in order
00060     // to be sure of getting a corresponding pop
00061     TRACE("push new=%s clang=S%p top=%s\n", ToString( ts ).c_str(), S, ToString( scope_stack.top() ).c_str() );
00062     
00063     if( S )
00064     {
00065         clang::IdentifierInfo *fake_id = (clang::IdentifierInfo *)0xbad1dbad;    
00066         S->AddDecl(fake_id); 
00067         ts->cs = S;
00068     }
00069     else
00070     {
00071         ASSERT( ts->cs ); 
00072     }
00073     
00074     //ASSERT( ts->parent == scope_stack.top() );     
00075     scope_stack.push( ts );    
00076 }
00077 
00078 
00079 // Dump the current scope and move back to the parent
00080 void IdentifierTracker::PopScope(clang::Scope *S) 
00081 {
00082     TRACE("pop top=%s clang=S%p\n", scope_stack.empty()?"<empty>":ToString(scope_stack.top()).c_str(), S );
00083     if( !scope_stack.empty() && scope_stack.top() && (!S || scope_stack.top()->cs == S) ) // do not pop if we never pushed because didnt get an Add() for this scope
00084     {
00085         scope_stack.pop();
00086         ASSERT( !scope_stack.empty() );
00087     }
00088     //TRACE("done pop %s S%p\n", ToString(scope_stack.top()).c_str(), S );
00089 }
00090 
00091 
00092 void IdentifierTracker::NewScope( clang::Scope *S )
00093 {
00094     // See if we already know about the "next_record" specified during parse.
00095     // If so, make this tnode be the parent. 
00096     if( !next_record.empty() && (S->getFlags() & clang::Scope::CXXClassScope) ) // Only use next_record if scope is actually a Record
00097     {
00098         TRACE("got next_record; \n");
00099         ASSERT( next_record.top() ); // probably tried to create more than one scope for this record
00100         PushScope( S, next_record.top() );
00101         next_record.pop();
00102         next_record.push( shared_ptr<Node>() );   // Remove since we've used it and shouldn't use it again     
00103     }
00104     else
00105     {
00106         // We were not warned about the new scope, so just make a new anonymous one.
00107         TRACE("no next_record; \n");
00108         shared_ptr<TNode> ts = shared_ptr<TNode>( new TNode );    
00109         ts->II = NULL;
00110         ts->parent = scope_stack.empty()?shared_ptr<TNode>():scope_stack.top();
00111         PushScope( S, ts );
00112     }
00113 }
00114 
00115 void IdentifierTracker::SeenScope( clang::Scope *S )
00116 {
00117     // Detect a change of scope and create a new scope if required. Do not do anything for
00118     // global scope (=no parent) - in that case, we leave the current scope as NULL
00119     ASSERT(S);
00120     if( S->getParent() && (scope_stack.empty() || !scope_stack.top() || scope_stack.top()->cs != S) )
00121     {
00122         TRACE("Seen new clang=S%p", S);
00123         if( !scope_stack.empty() && scope_stack.top() )
00124             TRACE(" top=")(ToString(scope_stack.top()));
00125         TRACE("\n");
00126        NewScope( S );
00127     }
00128 }
00129 
00130 
00131 void IdentifierTracker::Add( clang::IdentifierInfo *II, shared_ptr<Node> node, clang::Scope *S ) 
00132 {
00133     SeenScope( S );
00134     
00135     // Make the TNode for this identifier and fill in    
00136     shared_ptr<TNode> i( new TNode );    
00137     i->II = II;
00138     i->node = node;
00139     i->parent = scope_stack.top();  
00140     i->cs = NULL; // Remember cs is the clang scope *owned* by i
00141     tnodes.push_back( i );
00142       
00143     TRACE("added %s new=%p top=%s clang=S%p\n", ToString( i ).c_str(), node.get(), ToString( scope_stack.top() ).c_str(), S );    
00144 }
00145 
00146 
00147 // Just for debug; make a pretty string of the scope
00148 string IdentifierTracker::ToString( shared_ptr<TNode> tss )
00149 {
00150     if( !tss )
00151         return string("T<nil>");
00152 
00153     string s;
00154     int i=0;
00155     shared_ptr<TNode> ts = tss;
00156     while( ts )
00157     {        
00158         if( ts->node == global )
00159             break;
00160         string ss;    
00161         if( ts->II )
00162         {
00163             ss = string(ts->II->getName()) + s;
00164         }
00165         else
00166         {
00167             char c[100];
00168             sprintf( c, "T%p", ts.get() );
00169             ss = string(c) + s;
00170         }
00171         s = "::" + ss;
00172         ts = ts->parent;        
00173         i++;
00174         ASSERT( i<=tnodes.size() )( "TNode loop detected!!!!!!!!! OH NO!!!!!1\n" );
00175     }
00176     
00177     if( s.empty() )
00178         s = "::"; // global scope
00179     
00180     s = SSPrintf("T%pS%p\"", tss.get(), tss->cs) + s + "\"";
00181 
00182     if( tss->parent )
00183         s += SSPrintf("->T%p", tss->parent.get() );
00184     
00185     return s;
00186 }
00187 
00188 
00189 #define NOMATCH 1000000
00190 
00191 // Does identifier "II" found in scope "current" match rooted "ident"? if not return NOMATCH otherwise
00192 // return the number of scopes we went down through from current to get a match (effectively a distance)
00193 bool IdentifierTracker::IsIdentical( shared_ptr<TNode> current, shared_ptr<TNode> ident )
00194 {
00195     return current == ident;
00196 }
00197 
00198 // Does identifier "II" found in scope "current" match rooted "ident"? if not return NOMATCH otherwise
00199 // return the number of scopes we went down through from current to get a match (effectively a distance)
00200 int IdentifierTracker::IsMatch( const clang::IdentifierInfo *II, shared_ptr<TNode> start, shared_ptr<TNode> ident, bool recurse )
00201 {
00202     string cs, ips;
00203     cs = ToString( start );
00204     ASSERT( ident );
00205     ips = ToString( ident->parent );
00206     ASSERT( II ); // identifier being searched must have name
00207      
00208     if( !(ident->II) )
00209         return NOMATCH; // not all tnodes have a name eg global, which will never match here
00210         
00211     if( II != ident->II )
00212     {
00213         return NOMATCH; // different strings
00214     }
00215     
00216     shared_ptr<TNode> cur_it = start; 
00217     shared_ptr<TNode> id_it = ident->parent;
00218     int d = 0;
00219     
00220     // Try stepping out of the starting scope, one scope at a time,
00221     // until we match the identifier's scope.
00222     while( !IsIdentical( cur_it, id_it ) )
00223     {
00224         if( cur_it == NULL || !recurse )
00225         {
00226             return NOMATCH; 
00227         }
00228         cur_it = cur_it->parent;
00229         d++;
00230     }
00231     
00232     return d;
00233 }
00234 
00235 
00236 shared_ptr<Node> IdentifierTracker::Get( const clang::IdentifierInfo *II, shared_ptr<Node> iscope, bool recurse )
00237 {
00238     ASSERT(II);
00239     TRACE();
00240     shared_ptr<Node> n = TryGet( II, iscope, recurse );
00241     if( !n ) // All just tracing to see what went wrong
00242     {
00243         TRACE("recurse=%s\n", recurse?"true":"false");
00244         if(iscope)
00245         {
00246             TRACE("iscope: ")(*iscope)("\n");
00247         }
00248         else
00249         {
00250             FOREACH( shared_ptr<TNode> x, tnodes )
00251             {
00252                 TRACE(ToString(x))("\n");
00253             }
00254         }
00255     }
00256     ASSERT(n)("Decl not found : ")(II->getName()); 
00257     return n;
00258 }
00259 
00260 
00261 shared_ptr<Node> IdentifierTracker::TryGet( const clang::IdentifierInfo *II, shared_ptr<Node> iscope, bool recurse )
00262 {
00263     ASSERT(II);
00264     
00265     // Choose the required identifier via a proximity search
00266     shared_ptr<TNode> start;
00267     if( iscope )
00268     {
00269         // A C++ style scope was supplied (iscope::II) - search in here and don't recurse
00270         start = Find( iscope );
00271         ASSERT(start);
00272         recurse = false; // Never recurse with a C++ scope - they are exact specifications
00273     }    
00274     else
00275     {
00276         // No C++ scope, so use the current scope and recurse through parents
00277         ASSERT( !scope_stack.empty() );
00278         start = scope_stack.top();
00279         ASSERT(start);
00280     }
00281 
00282     TRACE("TryGet ")(II->getName())(" in scope ")(ToString(start))(" only, ")(iscope?"C++ ":"")(recurse?"":"not ")("recursive\n"); 
00283         
00284     int best_distance=NOMATCH;
00285     shared_ptr<TNode> best_tnode;
00286     for( int i=0; i<tnodes.size(); i++ )
00287     {
00288         
00289         int distance = IsMatch( II, start, tnodes[i], recurse );
00290         if( distance < best_distance )
00291         {
00292             best_distance = distance;
00293             best_tnode = tnodes[i];            
00294         }
00295     }
00296  
00297     if( best_tnode )
00298         return best_tnode->node;
00299     else
00300         return shared_ptr<Node>();
00301 }
00302 
00303 
00304 /* Untested
00305 shared_ptr<Node> IdentifierTracker::FindMemberNode( const clang::IdentifierInfo *II, shared_ptr<Node> record )
00306 {
00307     // Find the tnode for the record, based on the supplied node
00308     shared_ptr<TNode> found_record = Find( record );
00309         
00310     if( !found_record )
00311         return shared_ptr<Node>();
00312     
00313     // Find the member based on matching (a) the name and (b) the parent matching
00314     ASSERT( II );
00315     for( int i=0; i<tnodes.size(); i++ )
00316         if( tnodes[i]->II == II && tnodes[i]->parent == found_record )
00317         {
00318             return tnodes[i]->node;            
00319         }
00320         
00321     return shared_ptr<Node>();
00322 }
00323 */