Inferno  0.2
sort_decls.cpp
Go to the documentation of this file.
00001 
00002 #include "sort_decls.hpp"
00003 #include "tree/misc.hpp"
00004 
00005 using namespace CPPTree;
00006 
00007 /** Walks the tree, avoiding recursing into the body (initialiser) of Callables. */
00008 class UniqueWalkNoBody_iterator : public UniqueWalk::iterator
00009 {
00010 public:
00011     UniqueWalkNoBody_iterator( TreePtr<Node> &root ) : UniqueWalk::iterator(root) {}        
00012     UniqueWalkNoBody_iterator() : UniqueWalk::iterator() {}
00013   virtual shared_ptr<ContainerInterface::iterator_interface> Clone() const
00014   {
00015         return shared_ptr<UniqueWalkNoBody_iterator>( new UniqueWalkNoBody_iterator(*this) );
00016   }      
00017 protected:
00018     virtual shared_ptr<ContainerInterface> GetChildContainer( TreePtr<Node> n ) const
00019     {
00020         INDENT;
00021         // We need to create a container of elements of the child.
00022         if( shared_ptr<Instance> i = dynamic_pointer_cast<Instance>( n ) ) // an instance...
00023             if( dynamic_pointer_cast<Callable>( i->type ) ) // ...of a function
00024             {
00025                 TRACE("special behaviour for ")(*n)("\n");
00026                 // it's an instance, so set up a container containing type and identifier only, 
00027                 // not initialiser (others don't matter for deps purposes). We need 
00028                 // the type for params etc
00029                 shared_ptr< Sequence<Node> > seq( new Sequence<Node> );
00030                 seq->push_back( i->type );
00031                 seq->push_back( i->identifier );
00032                 return seq;
00033             }
00034         // it's not a slave, so proceed as for UniqueWalk
00035         TRACE("defaulting ")(*n)("\n");
00036         return UniqueWalk::iterator::GetChildContainer(n);
00037     }
00038 };
00039 
00040 typedef ContainerFromIterator< UniqueWalkNoBody_iterator, TreePtr<Node> > UniqueWalkNoBody;
00041 
00042 /** Walks the tree, avoiding recursing into the body (initialiser) of Callables and anything under an indirection. */
00043 class UniqueWalkNoBodyOrIndirection_iterator : public UniqueWalkNoBody::iterator
00044 {
00045 public:
00046     UniqueWalkNoBodyOrIndirection_iterator( TreePtr<Node> &root ) : UniqueWalkNoBody::iterator(root) {}        
00047     UniqueWalkNoBodyOrIndirection_iterator() : UniqueWalkNoBody::iterator() {}
00048   virtual shared_ptr<ContainerInterface::iterator_interface> Clone() const
00049   {
00050         return shared_ptr<UniqueWalkNoBodyOrIndirection_iterator>( new UniqueWalkNoBodyOrIndirection_iterator(*this) );
00051   }      
00052 private:
00053     virtual shared_ptr<ContainerInterface> GetChildContainer( TreePtr<Node> n ) const
00054     {
00055         INDENT;
00056         // We need to create a container of elements of the child.
00057         if( dynamic_pointer_cast<Indirection>( n ) ) // an instance...
00058         {
00059             TRACE("special behaviour for ")(*n)("\n");
00060             shared_ptr< Sequence<Node> > seq( new Sequence<Node> );
00061             return seq;
00062         }
00063         TRACE("defaulting ")(*n)("\n");
00064         // it's not a slave, so proceed as for UniqueWalk
00065         return UniqueWalkNoBody::iterator::GetChildContainer(n);
00066     }
00067 };
00068 
00069 
00070 typedef ContainerFromIterator< UniqueWalkNoBodyOrIndirection_iterator, TreePtr<Node> > UniqueWalkNoBodyOrIndirection;
00071 
00072 // Does a depend on b?
00073 bool IsDependOn( TreePtr<Declaration> a, TreePtr<Declaration> b, bool ignore_indirection_to_record )
00074 {
00075   if( a == b )
00076       return false;
00077   
00078     const TreePtr<Record> recb = dynamic_pointer_cast<Record>(b); // 2 unrelated uses
00079   
00080   // Only ignore pointers and refs if we're checking dependency on a record; typedefs
00081   // still apply (since you can't forward declare a typedef).
00082     bool ignore_indirection = ignore_indirection_to_record && recb;
00083 
00084     // Actually, we really want to see whether declaration a depends on the identifier of b
00085     // since the rest of b is irrelevent (apart from the above).
00086     TreePtr<Identifier> ib = GetIdentifier( b );
00087     ASSERT(ib);
00088           
00089     TRACE("Looking for dependencies on ")(*b)(" (identifier ")(*ib)(") under ")(*a)(ignore_indirection?"":" not")(" ignoring indirection\n");      
00090           
00091     // Always ignore function bodies since these are taken outboard by the renderer anyway      
00092     UniqueWalkNoBody wnb( a );
00093     UniqueWalkNoBodyOrIndirection wnbi( a );
00094     ContainerInterface *w = ignore_indirection ? (ContainerInterface *)&wnbi : (ContainerInterface *)&wnb;
00095         
00096     ContainerInterface::iterator wa=w->begin();
00097     while(!(wa == w->end()))
00098     {
00099         TRACE("Seen node ")(**wa)("\n");
00100     /*  if( ignore_indirection ) // are we to ignore pointers/refs?
00101       {
00102         if( TreePtr<Indirection> inda = TreePtr<Indirection>::DynamicCast(*wa) ) // is a a pointer or ref?
00103         {
00104           if( dynamic_pointer_cast<Identifier>(inda->destination) == ib ) // does it depend on b?
00105               {
00106                 wa.AdvanceOver(); // Then skip it
00107                 continue;
00108               }
00109         }
00110       }
00111       */
00112         if( TreePtr<Node>(*wa) == TreePtr<Node>(ib) ) // If we see b in *any* other context under a's type, there's dep.
00113         {
00114             TRACE("Found dependency\n");
00115             return true;     
00116         }           
00117 
00118         ++wa;
00119     }
00120     
00121     // Recurse though members of records since Inferno doesn't require scope to be remembered - so
00122     // the dependency might be on something buried in the record.
00123     if( recb )
00124     {
00125       FOREACH( TreePtr<Declaration> memberb, recb->members )
00126           if( IsDependOn( a, memberb, ignore_indirection_to_record ) )
00127               return true;
00128     }
00129     TRACE("Did not find dependency\n");
00130     return false; 
00131 }
00132 
00133 
00134 Sequence<Declaration> SortDecls( ContainerInterface &c, bool ignore_indirection_to_record )
00135 {
00136   Sequence<Declaration> s;
00137     int ocs = c.size();
00138     
00139     // Our algorithm will modify the source container, so make a copy of it
00140     Collection<Declaration> cc;
00141     FOREACH( const TreePtrInterface &a, c )
00142       cc.insert( a );
00143 
00144   // Keep searching our local container of decls (cc) for decls that do not depend
00145     // on anything else in the container. Such a decl may be safely rendered before the
00146     // rest of the decls, so place it at the end of the sequence we are building up
00147     // (s) and remove from the container cc since cc only holds the ones we have still to
00148     // place in s. Repeat until we've done all the decls at which point cc is empty.
00149     // If no non-dependent decl may be found in cc then it's irredemably circular and
00150     // we fail. This looks like O(N^3). Well, that's just a damn shame.
00151   TRACE("Adding decls in dep order: ");
00152   while( !cc.empty() )
00153   {
00154     bool found = false; // just for ASSERT check
00155     FOREACH( const TreePtr<Declaration> &a, cc )
00156     {
00157       bool a_has_deps=false;
00158       FOREACH( const TreePtr<Declaration> &b, cc )
00159         {
00160             TreePtr<Declaration> aid = dynamic_cast< const TreePtr<Declaration> & >(a);
00161           a_has_deps |= IsDependOn( aid, b, ignore_indirection_to_record );
00162         }
00163         if( !a_has_deps )
00164         {
00165             TRACE(*a)(" ");
00166         s.push_back(a);
00167         cc.erase(a);
00168         found = true;
00169             break;
00170         }
00171     }
00172 
00173     if( !found )
00174     {   
00175         TRACE("\nRemaining unsequenceable decls: ");
00176         FOREACH( const TreePtr<Declaration> &a, cc )
00177               TRACE(*a)(" ");
00178     }
00179     ASSERT( found )("\nfailed to find a decl to add without dependencies, maybe circular\n");
00180     //TRACE("%d %d\n", s.size(), c.size() );
00181   }
00182     TRACE("\n");
00183   ASSERT( s.size() == ocs );
00184   return s;
00185 }
00186 
00187 
00188 Sequence<Declaration> JumbleDecls( Sequence<Declaration> c )
00189 {
00190   srand(99);
00191   
00192   Sequence<Declaration> s;
00193   FOREACH( TreePtr<Declaration> to_insert, c ) // we will insert each element from the collection
00194   {
00195     // Idea is to insert each new element just before the first exiting element that
00196     // depends on it. This is the latest position we can insert the new element.
00197     Sequence<Declaration>::iterator i;
00198     int n = rand() % (s.size()+1);
00199     for( i = s.begin(); i != s.end(); ++i )
00200         {
00201           if( n-- == 0 )
00202           {
00203             // Found element that depends on the one we want to insert. So insert just 
00204             // before the found element.
00205             break;        
00206           }
00207         }
00208         
00209         // Insert the element. If we didn't find a dependency, we'll be off the end of
00210         // the sequence and hopefully insert() will actually push_back()
00211       s.insert( i, to_insert ); 
00212   }
00213   
00214   ASSERT( s.size() == c.size() );
00215   return s;
00216 }
00217 
00218 Sequence<Declaration> ReverseDecls( Sequence<Declaration> c )
00219 {
00220   Sequence<Declaration> s;
00221   FOREACH( TreePtr<Declaration> to_insert, c ) // we will insert each element from the collection
00222   {
00223         // Insert the element. If we didn't find a dependency, we'll be off the end of
00224         // the sequence and hopefully insert() will actually push_back()
00225       s.insert( s.begin(), to_insert ); 
00226   }
00227   
00228   ASSERT( s.size() == c.size() );
00229   return s;
00230 }
00231