Inferno
0.2
|
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