Inferno  0.2
agent.cpp
Go to the documentation of this file.
00001 #include "search_replace.hpp"
00002 #include "conjecture.hpp"
00003 #include "common/hit_count.hpp"
00004 #include "helpers/simple_compare.hpp"
00005 #include "agent.hpp"
00006 
00007 void NormalAgent::Configure( const CompareReplace *s, CouplingKeys *c )
00008 {
00009   ASSERT(s);
00010   ASSERT(c);
00011   sr = s;
00012     coupling_keys = c;
00013   // TODO recursively configure children
00014 }
00015 
00016 
00017 void NormalAgent::ConfigureTreePtrThis( TreePtr<Node> tpt )               
00018 {
00019   //TODO
00020 }
00021 
00022 bool NormalAgent::DecidedCompare( const TreePtrInterface &x,
00023                      TreePtr<Node> pattern,
00024                      bool can_key,
00025                        Conjecture &conj ) const
00026 {
00027     INDENT;
00028   ASSERT( x ); // Target must not be NULL
00029   if( !pattern )    // NULL matches anything in search patterns (just to save typing)
00030     return true;
00031     TRACE("Comparing x=")
00032          (*x)
00033          (" with pattern=")
00034          (*pattern)
00035          ("\n");
00036     shared_ptr<Key> special_key;
00037     
00038   // Check whether the present node matches. Do this for all nodes: this will be the local
00039   // restriction for normal nodes and the pre-restriction for special nodes (based on
00040   // how IsLocalMatch() has been overridden.
00041   if( !pattern->IsLocalMatch(x.get()) )
00042   {
00043     return false;
00044     }
00045     
00046     if( shared_ptr<SoftSearchPattern> ssp = dynamic_pointer_cast<SoftSearchPattern>(pattern) )
00047     {
00048         // Hand over to any soft search functionality in the search pattern node
00049         bool r = ssp->DecidedCompare( sr, x, can_key, conj );
00050         if( !r )
00051             return false;
00052     }
00053     else if( shared_ptr<SoftSearchPatternSpecialKey> sspsk = dynamic_pointer_cast<SoftSearchPatternSpecialKey>(pattern) )
00054     {
00055         // Hand over to any soft search functionality in the search pattern node
00056         special_key = sspsk->DecidedCompare( sr, x, can_key, conj );
00057         if( !special_key )
00058             return false;
00059     }
00060     else if( dynamic_pointer_cast<SoftReplacePattern>(pattern) )
00061     {
00062       // No further restriction beyond the pre-restriction for these nodes when searching.
00063     }
00064     else if( shared_ptr<SearchContainerBase> sc_pattern = dynamic_pointer_cast<SearchContainerBase>(pattern) )
00065     {
00066       // Invoke stuff node compare
00067       // Check whether the present node matches
00068       bool r = DecidedCompare( x, sc_pattern, can_key, conj );
00069         if( !r )
00070             return false;
00071     }
00072     else if( shared_ptr<GreenGrassBase> green_pattern = dynamic_pointer_cast<GreenGrassBase>(pattern) )
00073     {
00074         // Restrict so that everything in the input program under here must be "green grass"
00075         // ie unmodified by previous replaces in this RepeatingSearchReplace() run.
00076        // Walk w( x );
00077        // FOREACH( TreePtr<Node> p, w )
00078     if( sr->GetOverallMaster()->dirty_grass.find( /*p*/x ) != sr->GetOverallMaster()->dirty_grass.end() )
00079     {
00080       TRACE/*(*p)(" under ")*/(*x)(" is dirty grass so rejecting\n");
00081       return false;
00082     }
00083         TRACE("subtree under ")(*x)(" is green grass\n");
00084         // Normal matching for the through path
00085         bool r = DecidedCompare( x, green_pattern->GetThrough(), can_key, conj );
00086         if( !r )
00087             return false;
00088     }
00089     else if( shared_ptr<OverlayBase> op = dynamic_pointer_cast<OverlayBase>(pattern) )
00090     {
00091         // When Overlay node seen duriung search, just forward through the "through" path
00092         bool r = DecidedCompare( x, op->GetThrough(), can_key, conj );
00093         if( !r )
00094             return false;
00095     }
00096     else if( dynamic_pointer_cast<InsertBase>(pattern) || dynamic_pointer_cast<EraseBase>(pattern) )
00097     {
00098        ASSERTFAIL(*pattern)(" found outside of a container; can only be used in containers\n");
00099     }
00100     else if( shared_ptr<SlaveBase> sp = dynamic_pointer_cast<SlaveBase>(pattern) )
00101     {
00102         // When a slave node seen duriung search, just forward through the "base" path
00103         bool r = DecidedCompare( x, sp->GetThrough(), can_key, conj );
00104         if( !r )
00105             return false;
00106     }
00107     else
00108     {
00109     // Recurse through the children. Note that the itemiser internally does a
00110     // dynamic_cast onto the type of pattern, and itemises over that type. x must
00111     // be dynamic_castable to pattern's type.
00112     vector< Itemiser::Element * > pattern_memb = pattern->Itemise();
00113     vector< Itemiser::Element * > x_memb = pattern->Itemise( x.get() );   // Get the members of x corresponding to pattern's class
00114     ASSERT( pattern_memb.size() == x_memb.size() );
00115     for( int i=0; i<pattern_memb.size(); i++ )
00116     {
00117       bool r;
00118       ASSERT( pattern_memb[i] )( "itemise returned null element");
00119       ASSERT( x_memb[i] )( "itemise returned null element");
00120 
00121       if( SequenceInterface *pattern_seq = dynamic_cast<SequenceInterface *>(pattern_memb[i]) )
00122       {
00123         SequenceInterface *x_seq = dynamic_cast<SequenceInterface *>(x_memb[i]);
00124         ASSERT( x_seq )( "itemise for x didn't match itemise for pattern");
00125         TRACE("Member %d is Sequence, x %d elts, pattern %d elts\n", i, x_seq->size(), pattern_seq->size() );
00126         r = DecidedCompare( *x_seq, *pattern_seq, can_key, conj );
00127       }
00128       else if( CollectionInterface *pattern_col = dynamic_cast<CollectionInterface *>(pattern_memb[i]) )
00129       {
00130         CollectionInterface *x_col = dynamic_cast<CollectionInterface *>(x_memb[i]);
00131         ASSERT( x_col )( "itemise for x didn't match itemise for pattern");
00132         TRACE("Member %d is Collection, x %d elts, pattern %d elts\n", i, x_col->size(), pattern_col->size() );
00133         r = DecidedCompare( *x_col, *pattern_col, can_key, conj );
00134       }
00135       else if( TreePtrInterface *pattern_ptr = dynamic_cast<TreePtrInterface *>(pattern_memb[i]) )
00136       {
00137         TreePtrInterface *x_ptr = dynamic_cast<TreePtrInterface *>(x_memb[i]);
00138         ASSERT( x_ptr )( "itemise for x didn't match itemise for pattern");
00139         TRACE("Member %d is TreePtr, pattern ptr=%p\n", i, pattern_ptr->get());
00140         r = DecidedCompare( *x_ptr, TreePtr<Node>(*pattern_ptr), can_key, conj );
00141       }
00142       else
00143       {
00144         ASSERTFAIL("got something from itemise that isnt a Sequence, Collection or a TreePtr");
00145       }
00146 
00147       if( !r )
00148         return false;
00149     }
00150     }
00151    
00152     // Check couplings after everything else because they can get keyed during keying pass
00153     // and then seem to match during restricting pass. A key match is not a guarantee 
00154     // because when it keyed some coupled node below it may not have been keyed yet 
00155     // and so their checks would not have occured and hte check would not be strict 
00156     // enough. Perhaps keys can be "concrete" when all the couplings below them have
00157     // been checked as matching?
00158     if( TreePtr<Node> keynode = coupling_keys->GetCoupled( pattern ) )
00159     {
00160         SimpleCompare sc;
00161         if( sc( x, keynode ) == false )
00162             return false;
00163     }
00164   
00165   if( can_key )
00166     {
00167         if( special_key )
00168             coupling_keys->DoKey( special_key, pattern );  
00169         else
00170             coupling_keys->DoKey( x, pattern );  
00171     }
00172 
00173     return true;
00174 }
00175 
00176 
00177 // TODO support SearchContainerBase(ie Stuff nodes) here and below inside the container.
00178 // Behaviour would be to try the container at each of the nodes matched by the star, and if
00179 // one match is found we have a hit (ie OR behaviour). I think this results in 3 decisions
00180 // for sequences as opposed to Star and Stuff, which are one decision each. They are:
00181 // first: How many elements to match (as with Star)
00182 // second: Which of the above to try for container match
00183 // third: Which element of the SearchContainer to try 
00184 bool NormalAgent::DecidedCompare( SequenceInterface &x,
00185                               SequenceInterface &pattern,
00186                               bool can_key,
00187                               Conjecture &conj ) const
00188 {
00189     INDENT;
00190     Sequence<Node> epattern = WalkContainerPattern( pattern, false );    
00191     
00192   // Attempt to match all the elements between start and the end of the sequence; stop
00193   // if either pattern or subject runs out.
00194   ContainerInterface::iterator xit = x.begin();
00195   ContainerInterface::iterator pit, npit, nnpit;
00196 
00197   for( pit = epattern.begin(); pit != epattern.end(); ++pit )
00198   {
00199     ASSERT( xit == x.end() || *xit );
00200 
00201     // Get the next element of the pattern
00202     TreePtr<Node> pe( *pit );
00203     ASSERT( pe );
00204     npit=pit;
00205     ++npit;
00206 
00207         if( shared_ptr<StarBase> ps = dynamic_pointer_cast<StarBase>(pe) )
00208         {
00209             // We have a Star type wildcard that can match multiple elements.
00210             // Remember where we are - this is the beginning of the subsequence that
00211             // potentially matches the Star.
00212             ContainerInterface::iterator xit_begin_star = xit;
00213 
00214             // Star always matches at the end of a sequence, so we only need a 
00215             // decision when there are more elements left
00216             if( npit == epattern.end() )
00217             {
00218                 xit = x.end(); // match all remaining members of x; jump to end
00219             }
00220             else
00221             {
00222                 TRACE("Pattern continues after star\n");
00223 
00224                 // Star not at end so there is more stuff to match; ensure not another star
00225             //  ASSERT( !dynamic_pointer_cast<StarBase>(TreePtr<Node>(*npit)) )
00226             //        ( "Not allowed to have two neighbouring Star elements in search pattern Sequence");
00227 
00228                 // Decide how many elements the current * should match, using conjecture. Jump forward
00229                 // that many elements, to the element after the star. We need to use the special 
00230                 // interface to Conjecture because the iterator we get is itself an end to the 
00231                 // range matched by the star, and so x.end() is a legitimate choice for ss.end()
00232                 // So allow the Conjecture class to give us two ends, and only give up on the second.
00233                 Conjecture::Choice *current_choice = conj.GetChoicePtr();
00234                 {
00235                     xit = conj.HandleDecision( xit_begin_star, x.end(), 1 );
00236                 }                               
00237             }
00238             
00239             // Star matched [xit_begin_star, xit) i.e. xit-xit_begin_star elements
00240             // Now make a copy of the elements that matched the star and apply couplings
00241             TreePtr<SubSequenceRange> ss( new SubSequenceRange( xit_begin_star, xit ) );
00242             //for( ContainerInterface::iterator it=xit_begin_star; it != xit; ++it ) // TODO FOREACH?
00243             //{
00244             //  ss->push_back( *it );
00245             //}
00246             
00247             // Apply couplings to this Star and matched range
00248             if( TreePtr<Node> keynode = coupling_keys->GetCoupled( pe ) )
00249             {
00250                 SimpleCompare sc;
00251                 if( sc( TreePtr<Node>(ss), keynode ) == false )
00252                     return false;
00253             }
00254             
00255             // Restrict to pre-restriction or pattern
00256             bool r = ps->MatchRange( sr, *ss, can_key );
00257             if( !r )
00258                 return false;
00259 
00260             if( can_key )
00261                 coupling_keys->DoKey( TreePtr<Node>(ss), pe );   
00262         }
00263       else // not a Star so match singly...
00264       {
00265             // If there is one more element in x, see if it matches the pattern
00266       //TreePtr<Node> xe( x[xit] );
00267       if( xit != x.end() && DecidedCompare( *xit, pe, can_key, conj ) == true )
00268       {
00269         ++xit;
00270       }
00271       else
00272       {
00273         TRACE("Element mismatched\n");
00274         return false;
00275       }
00276       }
00277   }
00278 
00279     // If we finished the job and pattern and subject are still aligned, then it was a match
00280   TRACE("Finishing compare sequence %d %d\n", xit==x.end(), pit==epattern.end() );
00281     return (xit==x.end() && pit==epattern.end()) ? true : false;
00282 }
00283 
00284 
00285 bool NormalAgent::DecidedCompare( CollectionInterface &x,
00286                      CollectionInterface &pattern,
00287                      bool can_key,
00288                      Conjecture &conj ) const
00289 {
00290     INDENT;
00291     Sequence<Node> epattern = WalkContainerPattern( pattern, false );    
00292    
00293     // Make a copy of the elements in the tree. As we go though the pattern, we'll erase them from
00294   // here so that (a) we can tell which ones we've done so far and (b) we can get the remainder
00295   // after decisions.
00296   // TODO is there some stl algorithm for this?
00297     TreePtr<SubCollection> xremaining( new SubCollection );
00298     FOREACH( const TreePtrInterface &xe, x )
00299         xremaining->insert( xe );
00300     
00301     shared_ptr<StarBase> star;
00302     bool seen_star = false;
00303 
00304     for( CollectionInterface::iterator pit = epattern.begin(); pit != epattern.end(); ++pit )
00305     {
00306       TRACE("Collection compare %d remain out of %d; looking at %s in epattern\n",
00307           xremaining->size(),
00308           epattern.size(),
00309           TypeInfo( TreePtr<Node>(*pit) ).name().c_str() );
00310       shared_ptr<StarBase> maybe_star = dynamic_pointer_cast<StarBase>( TreePtr<Node>(*pit) );
00311 
00312         if( maybe_star ) // Star in pattern collection?
00313         {
00314           ASSERT(!seen_star)("Only one Star node (or NULL ptr) allowed in a search epattern Collection");
00315           // TODO remove this restriction - I might want to match one star and leave another unmatched.
00316             star = maybe_star; // remember for later and skip to next pattern
00317             seen_star = true; // TODO do we need?
00318         }
00319       else // not a Star so match singly...
00320       {
00321         // We have to decide which node in the tree to match, so use the present conjecture
00322         ContainerInterface::iterator xit = conj.HandleDecision( x.begin(), x.end() );
00323       if( xit == x.end() )
00324         return false;
00325 
00326         // Remove the chosen element from the remaineder collection. If it is not there (ret val==0)
00327         // then the present chosen iterator has been chosen before and the choices are conflicting.
00328         // We'll just return false so we do not stop trying further choices (xit+1 may be legal).
00329         if( xremaining->erase( *xit ) == 0 )
00330           return false;
00331 
00332         // Recurse into comparison function for the chosen node
00333       if( !DecidedCompare( *xit, TreePtr<Node>(*pit), can_key, conj ) )
00334           return false;
00335       }
00336     }
00337 
00338     // Now handle the star if there was one; all the non-star matches have been erased from
00339     // the collection, leaving only the star matches.
00340 
00341     if( !xremaining->empty() && !seen_star )
00342       return false; // there were elements left over and no star to match them against
00343 
00344     TRACE("seen_star %d star %p size of xremaining %d\n", seen_star, star.get(), xremaining->size() );
00345 
00346     // Apply pre-restriction to the star
00347     if( seen_star )
00348     {
00349         if( TreePtr<Node> keynode = coupling_keys->GetCoupled( star ) )
00350         {
00351             SimpleCompare sc;
00352             if( sc( TreePtr<Node>(xremaining), keynode ) == false )
00353                 return false;
00354         }
00355 
00356         bool r = star->MatchRange( sr, *xremaining, can_key );
00357         if( !r )
00358             return false;
00359     
00360         if( can_key )
00361             coupling_keys->DoKey( TreePtr<Node>(xremaining), star );  
00362     }
00363     TRACE("matched\n");
00364   return true;
00365 }
00366 
00367 
00368 // Helper for DecidedCompare that does the actual match testing work for the children and recurses.
00369 // Also checks for soft matches.
00370 bool NormalAgent::DecidedCompare( const TreePtrInterface &x,
00371                      shared_ptr<SearchContainerBase> pattern,
00372                      bool can_key,
00373                      Conjecture &conj ) const
00374 {
00375     INDENT;
00376   ASSERT( pattern->terminus )("Stuff node without terminus, seems pointless, if there's a reason for it remove this assert");
00377 
00378     TRACE("SearchContainer pattern ")(*pattern)(" terminus pattern is ")(*(pattern->terminus))(" at ")(*x)("\n");
00379 
00380     // Get an interface to the container we will search
00381     shared_ptr<ContainerInterface> pwx = pattern->GetContainerInterface( x );
00382     
00383   // Get choice from conjecture about where we are in the walk
00384   ContainerInterface::iterator thistime = conj.HandleDecision( pwx->begin(), pwx->end() );
00385   if( thistime == (ContainerInterface::iterator)(pwx->end()) )
00386     return false; // ran out of choices
00387 
00388   // Try out comparison at this position
00389   TRACE("Trying terminus ")(**thistime);
00390   bool r = DecidedCompare( *thistime, pattern->terminus, can_key, conj );
00391     if( !r )
00392         return false;
00393         
00394     if( TreePtr<Node> keynode = coupling_keys->GetCoupled( pattern ) )
00395     {
00396         SimpleCompare sc;
00397         if( sc( x, keynode ) == false )
00398             return false;
00399     }
00400     
00401     // If we got this far, do the couplings
00402     if( can_key )
00403     {
00404       shared_ptr<TerminusKey> key( new TerminusKey );
00405       key->root = x;
00406       key->terminus = *thistime;
00407       shared_ptr<Key> sckey( key );
00408       TRACE("Matched, so keying search container type ")(*pattern)(" for ")(*x)(" at %p\n", key.get());
00409         coupling_keys->DoKey( sckey, pattern ); 
00410     }
00411   return r;
00412 }
00413 
00414 
00415 TreePtr<Node> NormalAgent::BuildReplace( TreePtr<Node> pattern,
00416                                        TreePtr<Node> keynode ) const
00417 {
00418     INDENT;
00419     ASSERT( pattern );
00420 
00421     // See if the pattern node is coupled to anything
00422     shared_ptr<Key> key = coupling_keys->GetKey( pattern );
00423   if( key )
00424     keynode = key->root;
00425   if( dynamic_pointer_cast<SearchContainerBase>(pattern) )
00426   {
00427     // SearchContainer.
00428     // Are we substituting a stuff node? If so, see if we reached the terminus, and if
00429     // so come out of substitution. Done as tail recursion so that we already duplicated
00430     // the terminus key, and can just overlay the terminus replace pattern.
00431     shared_ptr<TerminusKey> stuff_key = dynamic_pointer_cast<TerminusKey>(key);
00432     ASSERT( stuff_key );
00433     ASSERT( stuff_key->replace_pattern );
00434     shared_ptr<TerminusBase> replace_stuff = dynamic_pointer_cast<TerminusBase>( stuff_key->replace_pattern );
00435     ASSERT( replace_stuff );
00436     ASSERT( replace_stuff->terminus );
00437     TRACE( "Stuff node: Duplicating at terminus first: keynode=")(*(replace_stuff->terminus))
00438                                                       (", term=")(*(stuff_key->terminus))("\n");
00439     TreePtr<Node> term = BuildReplace( replace_stuff->terminus, stuff_key->terminus );
00440     TRACE( "Stuff node: Substituting stuff");
00441     return sr->DuplicateSubtree(keynode, stuff_key->terminus, term);   
00442   }     
00443   else
00444   {
00445       return BuildReplaceKeyed( pattern, keynode );
00446   }
00447 }
00448   
00449   
00450 TreePtr<Node> NormalAgent::BuildReplaceKeyed( TreePtr<Node> pattern,
00451                                             TreePtr<Node> keynode ) const
00452 { 
00453     INDENT;
00454     ASSERT( pattern );
00455 
00456   if( shared_ptr<StarBase> stb = dynamic_pointer_cast<StarBase>( pattern ) )
00457   {
00458     return BuildReplaceStar( stb, keynode ); // Strong modifier
00459   }
00460   if( shared_ptr<SoftReplacePattern> srp = dynamic_pointer_cast<SoftReplacePattern>( pattern ) )
00461   {
00462     TreePtr<Node> overlay = srp->GetOverlayPattern(); // only strong modifiers use this
00463     if( overlay ) // Really two different kinds of pattern node
00464       return BuildReplace( overlay, keynode ); // Strong modifier
00465     else
00466       return sr->DuplicateSubtree(keynode);   // Weak modifier
00467   }
00468   else if( shared_ptr<OverlayBase> ob = dynamic_pointer_cast<OverlayBase>( pattern ) )
00469   {
00470     ASSERT( ob->GetOverlay() );          
00471     TRACE("Overlay node through=")(*(ob->GetThrough()))(" overlay=")(*(ob->GetOverlay()))("\n");
00472     return BuildReplace( ob->GetOverlay(), keynode );
00473   }
00474   else if( shared_ptr<GreenGrassBase> ggb = dynamic_pointer_cast<GreenGrassBase>( pattern ) )
00475   {
00476     ASSERT( ggb->GetThrough() );          
00477     TRACE("GreenGrass node through=")(*(ggb->GetThrough()))("\n");
00478       return BuildReplace( ggb->GetThrough(), keynode );
00479   }
00480   else if( shared_ptr<SlaveBase> sb = dynamic_pointer_cast<SlaveBase>(pattern) )
00481   {   
00482     return BuildReplaceSlave( sb, keynode );
00483   } 
00484   else if( dynamic_pointer_cast<SpecialBase>(pattern) )
00485   {
00486     // Star, Not, TransformOf etc. Also MatchAll with no overlay pattern falls thru to here
00487     return sr->DuplicateSubtree(keynode);   
00488   }     
00489     else // Normal node
00490     {
00491         if( keynode && pattern->IsLocalMatch(keynode.get()) ) 
00492             return BuildReplaceOverlay( pattern, keynode );
00493         else
00494             return BuildReplaceNormal( pattern ); // Overwriting pattern over dest, need to make a duplicate 
00495   }
00496 }
00497 
00498 
00499 
00500 TreePtr<Node> NormalAgent::BuildReplaceOverlay( TreePtr<Node> pattern, 
00501                              TreePtr<Node> keynode ) const // under substitution if not NULL
00502 {
00503   INDENT;
00504     ASSERT( pattern );
00505     ASSERT( keynode );
00506 
00507 #ifdef STRACE
00508     TRACE("DoOverlayPattern dest={");
00509    {    Walk w(dest);
00510         bool first=true;
00511         FOREACH( TreePtr<Node> n, w )
00512         {
00513             if( !first )
00514                 TRACE(", ");
00515             TRACE( n ? *n : string("NULL"));
00516             first=false;
00517         }
00518         TRACE("}\n"); // TODO put this in as a common utility somewhere
00519    }
00520    TRACE("pattern={");
00521    {    Walk w(pattern);
00522         bool first=true;
00523         FOREACH( TreePtr<Node> n, w )
00524         {
00525             if( !first )
00526                 TRACE(", ");
00527             TRACE( n ? *n : string("NULL"));
00528             first=false;
00529         }
00530         TRACE("}\n"); // TODO put this in as a common utility somewhere
00531    }
00532 #endif   
00533     
00534     ASSERT( pattern->IsLocalMatch(keynode.get()) )
00535         ("pattern=")
00536       (*pattern)
00537       (" must be a non-strict superclass of keynode=")
00538       (*keynode)
00539       (", so that it does not have more members");
00540     TreePtr<Node> dest;
00541     
00542     // Make a new node, we will overlay from pattern, so resulting node will be dirty     
00543     dest = sr->DuplicateNode( keynode, true );
00544 
00545     // Loop over the elements of pattern, keynode and dest, limited to elements
00546     // present in pattern, which is a non-strict subclass of keynode and dest.
00547     // Overlay or overwrite pattern over a duplicate of dest. Keep track of 
00548     // corresponding elements of dest. 
00549     vector< Itemiser::Element * > pattern_memb = pattern->Itemise();
00550     vector< Itemiser::Element * > keynode_memb = keynode->Itemise( dest.get() ); // Get the members of keynode corresponding to pattern's class
00551     vector< Itemiser::Element * >  dest_memb = pattern->Itemise( dest.get() ); // Get the members of dest corresponding to pattern's class
00552     ASSERT( pattern_memb.size() == dest_memb.size() );
00553     Set< Itemiser::Element * > present_in_pattern;
00554     
00555     TRACE("Copying %d members from pattern=%s dest=%s\n", dest_memb.size(), TypeInfo(pattern).name().c_str(), TypeInfo(dest).name().c_str());
00556     for( int i=0; i<dest_memb.size(); i++ )
00557     {
00558       TRACE("member %d from pattern\n", i );
00559         ASSERT( pattern_memb[i] )( "itemise returned null element" );
00560         ASSERT( dest_memb[i] )( "itemise returned null element" );
00561         ASSERT( keynode_memb[i] )( "itemise returned null element" );                
00562         if( ContainerInterface *pattern_con = dynamic_cast<ContainerInterface *>(pattern_memb[i]) )                
00563         {
00564             Sequence<Node> expanded_pattern_con = WalkContainerPattern( *pattern_con, true );    
00565 
00566             ContainerInterface *dest_con = dynamic_cast<ContainerInterface *>(dest_memb[i]);
00567             ASSERT( dest_con )( "itemise for dest didn't match itemise for expanded_pattern_con");
00568             dest_con->clear();
00569 
00570             TRACE("Copying container size %d from expanded_pattern_con\n", expanded_pattern_con.size() );
00571           FOREACH( const TreePtrInterface &p, expanded_pattern_con )
00572           {
00573             ASSERT( p )("Some element of member %d (", i)(*pattern_con)(") of ")(*pattern)(" was NULL\n");
00574             TRACE("Got ")(*p)("\n");
00575         TreePtr<Node> n = BuildReplace( p );
00576                 if( ContainerInterface *psc = dynamic_cast<ContainerInterface *>(n.get()) )
00577                 {
00578                     TRACE("Walking SubContainer length %d\n", psc->size() );
00579                     FOREACH( const TreePtrInterface &pp, *psc )
00580                         dest_con->insert( pp );
00581                 }
00582                 else 
00583                 {
00584                     TRACE("Normal element, inserting %s directly\n", TypeInfo(n).name().c_str());
00585                     dest_con->insert( n );
00586                 }
00587           }
00588           present_in_pattern.insert( dest_memb[i] );
00589         }            
00590         else if( TreePtrInterface *pattern_ptr = dynamic_cast<TreePtrInterface *>(pattern_memb[i]) )
00591         {
00592           TRACE();
00593             TreePtrInterface *dest_ptr = dynamic_cast<TreePtrInterface *>(dest_memb[i]);
00594             TreePtrInterface *keynode_ptr = dynamic_cast<TreePtrInterface *>(keynode_memb[i]);
00595             ASSERT( dest_ptr )( "itemise for target didn't match itemise for pattern");
00596             TreePtr<Node> pattern_child = *pattern_ptr;
00597             TreePtr<Node> dest_child = *dest_ptr;
00598                        
00599             if( pattern_child )
00600             {                             
00601                 dest_child = BuildReplace( pattern_child, *keynode_ptr );
00602                 ASSERT( dest_child );
00603                 ASSERT( dest_child->IsFinal() );
00604                 present_in_pattern.insert( dest_memb[i] );
00605             }
00606             
00607             *dest_ptr = dest_child;
00608         }
00609         else
00610         {
00611             ASSERTFAIL("got something from itemise that isn't a sequence or a shared pointer");
00612         }        
00613     }
00614     
00615     // Loop over all the elements of keynode and dest that do not appear in pattern or
00616     // appear in pattern but are NULL TreePtr<>s. Duplicate from keynode into dest.
00617     keynode_memb = keynode->Itemise();
00618     dest_memb = dest->Itemise(); 
00619     
00620     TRACE("Copying %d members from keynode=%s dest=%s\n", dest_memb.size(), TypeInfo(keynode).name().c_str(), TypeInfo(dest).name().c_str());
00621     // Loop over all the members of keynode (which can be a subset of dest)
00622     // and for non-NULL members, duplicate them by recursing and write the
00623     // duplicates to the destination.
00624     for( int i=0; i<dest_memb.size(); i++ )
00625     {
00626         ASSERT( keynode_memb[i] )( "itemise returned null element" );
00627         ASSERT( dest_memb[i] )( "itemise returned null element" );
00628         
00629         if( present_in_pattern.IsExist(dest_memb[i]) )
00630             continue; // already did this one in the above loop
00631 
00632       TRACE("Member %d from key\n", i );
00633         if( ContainerInterface *keynode_con = dynamic_cast<ContainerInterface *>(keynode_memb[i]) )                
00634         {
00635             // Note: we get here when a wildcard is coupled that does not have the container
00636             // because it is an intermediate node. Eg Scope as a wildcard matching Module does 
00637             // not have "bases".
00638             ContainerInterface *dest_con = dynamic_cast<ContainerInterface *>(dest_memb[i]);
00639             dest_con->clear();
00640 
00641             TRACE("Copying container size %d from key\n", keynode_con->size() );
00642           FOREACH( const TreePtrInterface &p, *keynode_con )
00643           {
00644             ASSERT( p ); // present simplified scheme disallows NULL
00645             TreePtr<Node> n = sr->DuplicateSubtree( p );
00646             if( ContainerInterface *sc = dynamic_cast<ContainerInterface *>(n.get()) )
00647             {
00648               TRACE("Walking SubContainer length %d\n", sc->size() );
00649                 FOREACH( const TreePtrInterface &xx, *sc )
00650                   dest_con->insert( xx );
00651               }
00652             else
00653             {
00654               TRACE("Normal element, inserting %s directly\n", TypeInfo(n).name().c_str());
00655               dest_con->insert( n );
00656             }
00657           }
00658         }            
00659         else if( TreePtrInterface *keynode_ptr = dynamic_cast<TreePtrInterface *>(keynode_memb[i]) )
00660         {
00661             TreePtrInterface *dest_ptr = dynamic_cast<TreePtrInterface *>(dest_memb[i]);
00662             ASSERT( *keynode_ptr );
00663             *dest_ptr = sr->DuplicateSubtree( *keynode_ptr );
00664             ASSERT( *dest_ptr );
00665             ASSERT( TreePtr<Node>(*dest_ptr)->IsFinal() );            
00666         }
00667         else
00668         {
00669             ASSERTFAIL("got something from itemise that isn't a sequence or a shared pointer");
00670         }
00671     }
00672     
00673 #ifdef STRACE
00674     TRACE("DoOverlayPattern result={");
00675    {    Walk w(dest);
00676         bool first=true;
00677         FOREACH( TreePtr<Node> n, w )
00678         {
00679             if( !first )
00680                 TRACE(", ");
00681             TRACE( n ? *n : string("NULL"));
00682             first=false;
00683         }
00684         TRACE("}\n"); // TODO put this in as a common utility somewhere
00685    }
00686 #endif    
00687     ASSERT( dest );
00688     return dest;
00689 }
00690 
00691 
00692 TreePtr<Node> NormalAgent::BuildReplaceSlave( shared_ptr<SlaveBase> pattern, 
00693                            TreePtr<Node> keynode ) const 
00694 {
00695     INDENT;
00696   ASSERT( pattern );
00697   ASSERT( pattern->GetThrough() );   
00698   
00699   // Continue current replace operation by following the "through" pointer
00700     TreePtr<Node> dest = BuildReplace( pattern->GetThrough(), keynode );
00701     
00702   // Run the slave as a new transformation at the current location
00703   (*pattern)( sr->GetContext(), &dest );
00704   
00705     ASSERT( dest );
00706     return dest;
00707 }
00708 
00709     
00710 TreePtr<Node> NormalAgent::BuildReplaceNormal( TreePtr<Node> pattern ) const
00711 {
00712   INDENT;
00713     ASSERT( pattern );
00714  
00715   // Make a new node, force dirty because from pattern
00716     TreePtr<Node> dest = sr->DuplicateNode( pattern, true );
00717 
00718     // Itemise the members. Note that the itemiser internally does a
00719     // dynamic_cast onto the type of pattern, and itemises over that type. dest must
00720     // be dynamic_castable to pattern's type.
00721     vector< Itemiser::Element * > pattern_memb = pattern->Itemise();
00722     vector< Itemiser::Element * > dest_memb = dest->Itemise(); 
00723 
00724     TRACE("Copying %d members pattern=", dest_memb.size())(*pattern)(" dest=")(*dest)("\n");
00725     // Loop over all the members of pattern (which can be a subset of dest)
00726     // and for non-NULL members, duplicate them by recursing and write the
00727     // duplicates to the destination.
00728     for( int i=0; i<dest_memb.size(); i++ )
00729     {
00730       TRACE("Copying member %d\n", i );
00731         ASSERT( pattern_memb[i] )( "itemise returned null element" );
00732         ASSERT( dest_memb[i] )( "itemise returned null element" );
00733         
00734         if( ContainerInterface *pattern_con = dynamic_cast<ContainerInterface *>(pattern_memb[i]) )                
00735         {
00736             ContainerInterface *dest_con = dynamic_cast<ContainerInterface *>(dest_memb[i]);
00737             dest_con->clear();
00738 
00739             TRACE("Copying container size %d\n", pattern_con->size() );
00740           FOREACH( const TreePtrInterface &p, *pattern_con )
00741           {
00742             ASSERT( p )("Some element of member %d (", i)(*pattern_con)(") of ")(*pattern)(" was NULL\n");
00743             TRACE("Got ")(*p)("\n");
00744               TreePtr<Node> n = BuildReplace( p );
00745             if( ContainerInterface *psc = dynamic_cast<ContainerInterface *>(n.get()) )
00746             {
00747               TRACE("Walking SubContainer length %d\n", psc->size() );
00748                 FOREACH( const TreePtrInterface &pp, *psc )
00749                   dest_con->insert( pp );  // TODO support Container::insert(Container) to do this generically
00750               }
00751             else
00752             {
00753               TRACE("Normal element, inserting %s directly\n", TypeInfo(n).name().c_str());
00754               dest_con->insert( n );
00755             }
00756           }
00757         }            
00758         else if( TreePtrInterface *pattern_ptr = dynamic_cast<TreePtrInterface *>(pattern_memb[i]) )
00759         {
00760             TRACE("Copying single element\n");
00761             TreePtrInterface *dest_ptr = dynamic_cast<TreePtrInterface *>(dest_memb[i]);
00762             ASSERT( *pattern_ptr )("Member %d (", i)(*pattern_ptr)(") of ")(*pattern)(" was NULL when not overlaying\n");
00763             *dest_ptr = BuildReplace( *pattern_ptr );
00764             ASSERT( *dest_ptr );
00765             ASSERT( TreePtr<Node>(*dest_ptr)->IsFinal() )("Member %d (", i)(**pattern_ptr)(") of ")(*pattern)(" was not final\n");            
00766         }
00767         else
00768         {
00769             ASSERTFAIL("got something from itemise that isn't a sequence or a shared pointer");
00770         }
00771     }
00772     return dest;
00773 }
00774 
00775 
00776 TreePtr<Node> NormalAgent::BuildReplaceStar( shared_ptr<StarBase> pattern,
00777                                            TreePtr<Node> keynode ) const
00778 {
00779   ASSERT( pattern ); // not used at present but should be there since we may need to use it
00780   ASSERT( keynode );
00781   ContainerInterface *psc = dynamic_cast<ContainerInterface *>(keynode.get());
00782   ASSERT( psc )("Star node ")(*pattern)(" keyed to ")(*keynode)(" which should implement ContainerInterface");  
00783   TRACE("Walking container length %d\n", psc->size() );
00784   
00785   TreePtr<SubContainer> dest;
00786   ContainerInterface *dest_container;
00787   if( dynamic_cast<SequenceInterface *>(keynode.get()) )
00788     dest = TreePtr<SubSequence>(new SubSequence);
00789   else if( dynamic_cast<CollectionInterface *>(keynode.get()) )
00790     dest = TreePtr<SubCollection>(new SubCollection);
00791   else
00792     ASSERT(0)("Please add new kind of Star");
00793   
00794     dest_container = dynamic_cast<ContainerInterface *>(dest.get());
00795   FOREACH( const TreePtrInterface &pp, *psc )
00796   {
00797     TreePtr<Node> nn = sr->DuplicateSubtree( pp );
00798     dest_container->insert( nn );
00799   }
00800   
00801   return dest;
00802 }
00803 
00804 
00805 Sequence<Node> NormalAgent::WalkContainerPattern( ContainerInterface &pattern,
00806                                                   bool replacing ) const
00807 {
00808     // This helper is for Insert and Erase nodes. It takes a pattern container (which
00809     // is the only place these nodes should occur) and expands out either Insert or
00810     // Erase nodes. When searching, Erase is expanded out so that the program nodes
00811     // to be erased may be matched off (cond keyed etc) and Insert is skipped because
00812     // it does not need to correspond to anything during search. When replacing, 
00813     // erase is skipped to erase the elements and Insert is expanded to insert them. 
00814     Sequence<Node> expanded;
00815     FOREACH( TreePtr<Node> n, pattern )
00816     {
00817         if( shared_ptr<EraseBase> pe = dynamic_pointer_cast<EraseBase>(n) )
00818         {
00819             if( !replacing )
00820                 FOREACH( TreePtr<Node> e, *(pe->GetErase()) )
00821                     expanded.push_back( e );                
00822         }
00823         else if( shared_ptr<InsertBase> pi = dynamic_pointer_cast<InsertBase>(n) )
00824         {
00825             if( replacing )
00826                 FOREACH( TreePtr<Node> i, *(pi->GetInsert()) )
00827                     expanded.push_back( i );                
00828         }
00829         else if( shared_ptr<OverlayBase> po = dynamic_pointer_cast<OverlayBase>(n) )
00830         {
00831             // Unfortunate inconsistency here: An overlay node ca either (a) support stars under it for use in 
00832             // collections or (b) support overlaying, but not both. TODO think about overlaying subsequences 
00833             // We use the pattern-tweaking method if thre are stars, but let the replace engine do overlaying
00834             // if there are not (overlaying takes place for the single element at the position of the Overlay node)
00835             if( dynamic_pointer_cast<StarBase>(po->GetOverlay()) || dynamic_pointer_cast<StarBase>(po->GetThrough()) )
00836             {
00837                 if( replacing )
00838                     expanded.push_back( po->GetOverlay() );         
00839                 else
00840                     expanded.push_back( po->GetThrough() );    
00841             }
00842             else
00843             {
00844                 expanded.push_back( n );
00845             }                
00846         }
00847         else
00848         {
00849             expanded.push_back( n );
00850         }
00851     }
00852     return expanded;
00853 }
00854                                                                                                         
00855