Inferno  0.2
search_replace.hpp
Go to the documentation of this file.
00001 #ifndef SEARCH_REPLACE_HPP
00002 #define SEARCH_REPLACE_HPP
00003 
00004 #include "common/common.hpp"
00005 #include "common/read_args.hpp"
00006 #include "helpers/walk.hpp"
00007 #include "helpers/transformation.hpp"
00008 #include "coupling.hpp"
00009 #include "agent.hpp"
00010 #include <set>
00011 
00012 // In-tree search and replace utility. To use, you make a search pattern and a 
00013 // replace pattern, each in the form of a subtree. You pass these into the 
00014 // constructor and you now have a pass object (functor) that will apply the 
00015 // implied transformation on programs passed to it.
00016 // 
00017 // Additional functionality as follows:
00018 // - Intermediate tree nodes like Numeric or Expression can be placed
00019 //   in search pattern, in which case they act as wildcards matching
00020 //   any subclass node (think of set-theory interpretation of inheritance)
00021 //
00022 // - A NULL shared_ptr is also a wildcard for anything.
00023 //
00024 // - Multiple nodes in the search pattern can be forced to match the same 
00025 //   program node if a the same node is pointed to by more than one
00026 //   parent in the search pattern. Must be >= 1 node in normal 
00027 //   context.
00028 //
00029 // - Nodes in the replace pattern may be substituted by program nodes
00030 //   found during matching by allowing the replace pattern to point to 
00031 //   a node also present in the search patter (in a normal context).
00032 //
00033 // - Identifiers (any node derived from Identifier) are kept unique
00034 //   during replace by pointing directly to the identifier in the 
00035 //   program tree rather than duplicating (only when substituting).
00036 //
00037 // - Soft search pattern nodes may be created which can support custom
00038 //   matching rules by implementing a virtual DecidedCompare() function.
00039 //   Ready made soft nodes are documented in soft_patterns.hpp
00040 //
00041 // - Sequence/ContainerCommon support: sequences require matching ordering
00042 //   and containers do not (only the presence of the matching elements).
00043 //
00044 // - Multi-node wildcards like * in sequences and collections (Star node).
00045 //
00046 // - Recursive wildcards, arbitrary depth and arbitrary depth with
00047 //   restricted intermediates (the Stuff node). Restriction can be a
00048 //   general tree (in abnormal context)
00049 //
00050 // - SlaveSearchReplace search/replace so that a second SR can happen 
00051 //   for each match of the first one, and can borrow its couplings.
00052 //
00053 // - Boolean rules supported by NotMatch, MAtchAll, MatchAny and
00054 //   MatchOdd. For all but MatchAll, pattern is abnormal context.
00055 //
00056 // - The base type supplied as template param to all special nodes
00057 //   acts as a pre-restriction according to usual topological rules.
00058 //
00059 // - Green grass node only matches nodes that have not already been
00060 //   replaced, to avoid spinning forever.
00061 //
00062 // - Overlay node allows a replace pattern to be overlayed over 
00063 //   a substituted node. NULL shared_ptr (or empty container) in overly 
00064 //   means fill this in from the substitute. Intemediate node types
00065 //   mean fill in those members introduced in derived classes from the
00066 //   substitute.
00067 //
00068 
00069 class Conjecture;
00070 class SpecialBase;
00071 class StuffBase;
00072 class StarBase;
00073 class SlaveBase;
00074 class SearchContainerBase;
00075 
00076 class CompareReplace : virtual public InPlaceTransformation, 
00077                        public Filter 
00078 {  
00079 public:
00080     // Constructor and destructor. Search and replace patterns and couplings are
00081     // specified here, so that we have a fully confiugured functor.
00082     CompareReplace( TreePtr<Node> cp = TreePtr<Node>(),
00083                     TreePtr<Node> rp = TreePtr<Node>(),
00084                     bool im = true );
00085                     
00086     // Call this to set the patterns after construction. This should not be virtual since
00087     // the constructor calls it.
00088     void Configure( TreePtr<Node> cp,
00089                     TreePtr<Node> rp = TreePtr<Node>() );                 
00090     
00091     // Stuff for soft nodes; support this base class in addition to whatever tree intermediate
00092     // is required. Call GetProgram() if program root needed; call DecidedCompare() to recurse
00093     // back into the general search algorithm.
00094     TreePtr<Node> GetContext() const { ASSERT(pcontext&&*pcontext); return *pcontext; }
00095 
00096     // Some self-testing
00097     static void Test();
00098         
00099     bool is_master;// TODO seems to be obsolete
00100     TreePtr<Node> compare_pattern;
00101     TreePtr<Node> replace_pattern;
00102     CompareReplace *master_ptr;
00103     TreePtr<Node> *pcontext;
00104     mutable CouplingKeys coupling_keys;
00105     mutable set< TreePtr<Node> > dirty_grass;
00106     
00107     // Sets of nodes for debugging purposes. Checks should be positive, because identifiers are copied
00108     // shallowly and will appear in more than one set. Since they are const, preservation rules do not
00109     // apply to identifiers. Only use these when ReadArgs::assert_pedigree is true.
00110     Set< TreePtr<Node> > pattern_pedigree;            // Nodes from the replace pattern 
00111     mutable Set< TreePtr<Node> > duplicated_pedigree; // Nodes generated by duplication in replace 
00112     mutable Set< TreePtr<Node> > keyed_pedigree;      // Nodes found in coupling keys, essentially the input
00113     
00114     virtual void GetGraphInfo( vector<string> *labels, 
00115                                vector< TreePtr<Node> > *links ) const;
00116 
00117     static void SetMaxReps( int n, bool e ) { repetitions=n; rep_error=e; }
00118     const CompareReplace * GetOverallMaster() const
00119     {
00120         const CompareReplace *m = this;
00121         while( m->master_ptr )
00122             m = m->master_ptr;
00123         return m;
00124     }
00125 
00126 private:
00127     static int repetitions;
00128     static bool rep_error;
00129 public:
00130     bool DecidedCompare( const TreePtrInterface &x,
00131                        TreePtr<Node> pattern,
00132                        bool can_key,
00133                        Conjecture &conj ) const;
00134 private:
00135     // MatchingDecidedCompare ring
00136     friend class Conjecture;
00137     bool MatchingDecidedCompare( const TreePtrInterface &x,
00138                                TreePtr<Node> pattern,
00139                                bool can_key,
00140                                Conjecture &conj ) const;
00141 
00142     void FlushSoftPatternCaches( TreePtr<Node> pattern ) const;
00143 public:
00144     // Compare ring (now trivial)
00145     bool Compare( const TreePtrInterface &x,
00146                 TreePtr<Node> pattern,
00147                   bool can_key = false ) const;
00148     virtual bool IsMatch( TreePtr<Node> context,       
00149                           TreePtr<Node> root );
00150 public:
00151     TreePtr<Node> BuildReplace( TreePtr<Node> pattern ) const;
00152 private:
00153     TreePtr<Node> DuplicateNode( TreePtr<Node> pattern,
00154                              bool force_dirty ) const;
00155     TreePtr<Node> DuplicateSubtree( TreePtr<Node> source,
00156                                 TreePtr<Node> source_terminus = TreePtr<Node>(),
00157                                 TreePtr<Node> dest_terminus = TreePtr<Node>() ) const;
00158     void KeyReplaceNodes( TreePtr<Node> pattern ) const;
00159     TreePtr<Node> ReplacePhase( TreePtr<Node> x ) const;
00160     // implementation ring: Do the actual search and replace
00161     bool SingleCompareReplace( TreePtr<Node> *proot );
00162     int RepeatingCompareReplace( TreePtr<Node> *proot );
00163 public:
00164     // Functor style interface for RepeatingSearchReplace; implements Pass interface.
00165     using Transformation::operator();
00166     void operator()( TreePtr<Node> context, 
00167                      TreePtr<Node> *proot );
00168 
00169   friend class NormalAgent;
00170 };
00171 
00172 
00173 class SearchReplace : public CompareReplace
00174 {
00175 public:
00176     SearchReplace( TreePtr<Node> sp = TreePtr<Node>(),
00177                    TreePtr<Node> rp = TreePtr<Node>(),
00178                    bool im = true );
00179                    
00180     // Call this to set the patterns after construction. This should not be virtual since
00181     // the constructor calls it.
00182     void Configure( TreePtr<Node> sp,
00183                     TreePtr<Node> rp = TreePtr<Node>() );                 
00184                     
00185     virtual void GetGraphInfo( vector<string> *labels, 
00186                                vector< TreePtr<Node> > *links ) const;
00187 };
00188 
00189 
00190 // --- General note on SPECIAL_NODE_FUNCTIONS and PRE_RESTRICTION ---
00191 // Special nodes (that is nodes defined here with special S&R behaviour)
00192 // derive from a normal tree node via templating. This base class is
00193 // the PRE_RESTRICTION node, and we want it for 2 reasons:
00194 // 1. To allow normal nodes to point to special nodes, they must
00195 //    expose a normal interface, which can vary depending on usage
00196 //    so must be templated.
00197 // 2. We are able to provide a "free" and-rule restriction on all
00198 //    special nodes by restricting to non-strict subclasses of the
00199 //    pre-restrictor.
00200 // In order to make 2. work, we need to *avoid* overriding IsLocalMatch()
00201 // or IsSubclass() on special nodes, so that the behaviour of the 
00202 // PRE_RESTRICTION is preserved wrt comparisons. So all special nodes
00203 // including speicialisations of TransformTo etc should use 
00204 // SPECIAL_NODE_FUNCTIONS instead of NODE_FUNCTIONS.
00205 // Itemise is known required (for eg graph plotting), other bounces
00206 // are TBD.
00207 #define SPECIAL_NODE_FUNCTIONS ITEMISE_FUNCTION  
00208 struct SpecialBase
00209 {
00210     virtual shared_ptr< TreePtrInterface > GetPreRestrictionArchitype() = 0;
00211 };
00212 template<class PRE_RESTRICTION>
00213 struct Special : SpecialBase, virtual PRE_RESTRICTION
00214 {
00215     virtual shared_ptr< TreePtrInterface > GetPreRestrictionArchitype()
00216     {
00217         // Esta muchos indirection
00218         return shared_ptr<TreePtrInterface>( new TreePtr<PRE_RESTRICTION>( new PRE_RESTRICTION ));  
00219     }
00220 };
00221 
00222 /// Coupling slave can read the master's CouplingKeys structure
00223 struct CouplingSlave 
00224 {
00225     virtual void SetCouplingsMaster( CouplingKeys *ck ) = 0;    
00226 };
00227 
00228 struct SlaveBase : virtual CouplingSlave, virtual InPlaceTransformation
00229 {
00230     virtual TreePtr<Node> GetThrough() const = 0;
00231 };
00232 
00233 template<typename ALGO>
00234 struct SlaveIntermediate : public SlaveBase, public ALGO                                 
00235 {
00236   SlaveIntermediate( TreePtr<Node> sp, TreePtr<Node> rp ) :
00237     ALGO( sp, rp, false )
00238   {}
00239     virtual void SetCouplingsMaster( CouplingKeys *ck )
00240     {
00241         ALGO::coupling_keys.SetMaster( ck ); 
00242     }
00243     virtual void GetGraphInfo( vector<string> *labels, 
00244                                vector< TreePtr<Node> > *links ) const
00245     {
00246         labels->push_back("through");
00247         links->push_back(GetThrough());
00248         ALGO::GetGraphInfo( labels, links );
00249     }
00250 };
00251 
00252 template<typename ALGO, class PRE_RESTRICTION>
00253 struct Slave : SlaveIntermediate<ALGO>, Special<PRE_RESTRICTION>
00254 {
00255   SPECIAL_NODE_FUNCTIONS
00256 
00257   // SlaveSearchReplace must be constructed using constructor
00258   Slave( TreePtr<PRE_RESTRICTION> t, TreePtr<Node> sp, TreePtr<Node> rp ) :
00259     through( t ),
00260     SlaveIntermediate<ALGO>( sp, rp )
00261   {
00262   }
00263 
00264   TreePtr<PRE_RESTRICTION> through;
00265   virtual TreePtr<Node> GetThrough() const
00266   {
00267     return TreePtr<Node>( through );
00268   }
00269 };
00270 
00271 // Partial specialisation is an arse in C++
00272 template<class PRE_RESTRICTION>
00273 struct SlaveCompareReplace : Slave<CompareReplace, PRE_RESTRICTION>, virtual Node
00274 {
00275     SlaveCompareReplace() : Slave<CompareReplace, PRE_RESTRICTION>( NULL, NULL, NULL ) {}      
00276     SlaveCompareReplace( TreePtr<PRE_RESTRICTION> t, TreePtr<Node> sp=TreePtr<Node>(), TreePtr<Node> rp=TreePtr<Node>() ) :
00277         Slave<CompareReplace, PRE_RESTRICTION>( t, sp, rp ) {}
00278 };
00279 
00280 template<class PRE_RESTRICTION>
00281 struct SlaveSearchReplace : Slave<SearchReplace, PRE_RESTRICTION>, virtual Node
00282 {
00283     SlaveSearchReplace() : Slave<SearchReplace, PRE_RESTRICTION>( NULL, NULL, NULL ) {}      
00284     SlaveSearchReplace( TreePtr<PRE_RESTRICTION> t, TreePtr<Node> sp=TreePtr<Node>(), TreePtr<Node> rp=TreePtr<Node>() ) :
00285         Slave<SearchReplace, PRE_RESTRICTION>( t, sp, rp ) {}
00286 };
00287 
00288 
00289 // The * wildcard can match more than one node of any type in a container
00290 // In a Sequence, only a contiguous subsequence of 0 or more elements will match
00291 // In a Collection, a sub-collection of 0 or more elements may be matched anywhere in the collection
00292 // Only one Star is allowed in a Collection. Star must be templated on a type that is allowed
00293 // in the collection. TODO a restrict pattern
00294 struct StarBase : virtual Node 
00295 {
00296     virtual TreePtr<Node> GetPattern() = 0;
00297     bool MatchRange( const CompareReplace *sr,
00298                        ContainerInterface &range,
00299                        bool can_key );
00300 };
00301 template<class PRE_RESTRICTION>
00302 struct Star : StarBase, Special<PRE_RESTRICTION> 
00303 { 
00304     SPECIAL_NODE_FUNCTIONS 
00305     TreePtr<PRE_RESTRICTION> pattern; // TODO rename to "restriction"
00306     virtual TreePtr<Node> GetPattern() 
00307     {
00308         return pattern;
00309     }
00310 };
00311 
00312 
00313 struct GreenGrassBase : virtual Node
00314 {
00315     virtual TreePtr<Node> GetThrough() const = 0;
00316 };
00317 template<class PRE_RESTRICTION>
00318 struct GreenGrass : GreenGrassBase, Special<PRE_RESTRICTION>
00319 {
00320     SPECIAL_NODE_FUNCTIONS
00321     TreePtr<PRE_RESTRICTION> through;
00322     virtual TreePtr<Node> GetThrough() const
00323     {
00324         return TreePtr<Node>( through );
00325     }
00326 };
00327 
00328 struct TerminusKey : Key // TODO put in TerminusBase
00329 {
00330     TreePtr<Node> terminus;
00331 };
00332 struct TerminusBase : virtual Node 
00333 {
00334     TreePtr<Node> terminus; // A node somewhere under Stuff, that matches normally, truncating the subtree
00335 };
00336 
00337 
00338 struct SearchContainerBase : TerminusBase
00339 {
00340     virtual shared_ptr<ContainerInterface> GetContainerInterface( TreePtr<Node> x ) = 0;
00341 };
00342 
00343 
00344 
00345 // The Stuff wildcard can match a truncated subtree with special powers as listed by the members
00346 struct StuffBase : virtual Node, 
00347                    public SearchContainerBase
00348 {
00349     StuffBase() : one_level(false){}
00350     TreePtr<Node> recurse_restriction; // Restricts the intermediate nodes in the truncated subtree
00351     CompareReplace recurse_comparer; // TODO only need the compare half, maybe split it out?
00352     bool one_level;
00353     virtual shared_ptr<ContainerInterface> GetContainerInterface( TreePtr<Node> x );
00354 };
00355 template<class PRE_RESTRICTION>
00356 struct Stuff : StuffBase, Special<PRE_RESTRICTION> 
00357 {
00358     // Do the itemiser by hand since it gets confused by the CompareReplace object   
00359     virtual vector< Itemiser::Element * > Itemise( const Itemiser *itemise_object = 0 ) const
00360     {
00361         vector< Itemiser::Element * > v;
00362         v.push_back( (Itemiser::Element *)(&recurse_restriction) );
00363         v.push_back( (Itemiser::Element *)(&terminus) );
00364         return v;
00365     }
00366     virtual Itemiser::Element *ItemiseIndex( int i ) const  
00367     { 
00368         return Itemise()[i];
00369     } 
00370     virtual int ItemiseSize() const  
00371     { 
00372         return Itemise().size();
00373     }
00374 };
00375 
00376 
00377 
00378 struct AnyNodeBase : virtual Node, 
00379                      public SearchContainerBase
00380 {
00381     virtual shared_ptr<ContainerInterface> GetContainerInterface( TreePtr<Node> x );
00382 };
00383 template<class PRE_RESTRICTION>
00384 struct AnyNode : AnyNodeBase, Special<PRE_RESTRICTION> 
00385 {
00386     SPECIAL_NODE_FUNCTIONS
00387 };
00388 
00389 
00390 struct OverlayBase : virtual Node
00391 {
00392     virtual TreePtr<Node> GetThrough() const = 0;
00393     virtual TreePtr<Node> GetOverlay() const = 0;    
00394 };
00395 
00396 template<class PRE_RESTRICTION>
00397 struct Overlay : OverlayBase, Special<PRE_RESTRICTION>
00398 {
00399     SPECIAL_NODE_FUNCTIONS
00400     TreePtr<PRE_RESTRICTION> through;
00401     TreePtr<PRE_RESTRICTION> overlay;
00402     virtual TreePtr<Node> GetThrough() const 
00403     {
00404         return (TreePtr<Node>)through;
00405     }
00406     virtual TreePtr<Node> GetOverlay() const
00407     {
00408         return (TreePtr<Node>)overlay;
00409     }
00410 };
00411 
00412 struct InsertBase : virtual Node
00413 {
00414     virtual SequenceInterface *GetInsert() = 0;    
00415 };
00416 
00417 template<class PRE_RESTRICTION>
00418 struct Insert : InsertBase, Special<PRE_RESTRICTION>
00419 {
00420     SPECIAL_NODE_FUNCTIONS
00421     Sequence<PRE_RESTRICTION> insert;
00422     virtual SequenceInterface *GetInsert()  
00423     {
00424         return &insert;
00425     }
00426 };
00427 
00428 struct EraseBase : virtual Node
00429 {
00430     virtual SequenceInterface *GetErase() = 0;    
00431 };
00432 
00433 template<class PRE_RESTRICTION>
00434 struct Erase : EraseBase, Special<PRE_RESTRICTION>
00435 {
00436     SPECIAL_NODE_FUNCTIONS
00437     Sequence<PRE_RESTRICTION> erase;
00438     virtual SequenceInterface *GetErase()  
00439     {
00440         return &erase;
00441     }
00442 };
00443 
00444 // Tell soft nodes that a compare rtun is beginning and it can flush any caches it may have
00445 struct Flushable
00446 {
00447   virtual void FlushCache() {}
00448 };
00449 
00450 struct SoftSearchPattern : Flushable
00451 {
00452   virtual bool DecidedCompare( const CompareReplace *sr,
00453                   const TreePtrInterface &x,
00454                   bool can_key,
00455                   Conjecture &conj ) = 0;
00456 };
00457 struct SoftSearchPatternSpecialKey : Flushable
00458 {
00459   // Return NULL for not found
00460   virtual shared_ptr<Key> DecidedCompare( const CompareReplace *sr,
00461                       const TreePtrInterface &x,
00462                       bool can_key,
00463                       Conjecture &conj ) = 0;
00464 };
00465 struct SoftReplacePattern : Flushable
00466 {
00467   // Called when not coupled
00468   virtual TreePtr<Node> DuplicateSubtree( const CompareReplace *sr ) = 0;
00469   // Called when coupled, dest is coupling key
00470   virtual TreePtr<Node> GetOverlayPattern() 
00471   { 
00472     return TreePtr<Node>(); // default implementation for weak modifiers 
00473                 // so that couplings appear to override local functionality
00474   }
00475 };
00476 
00477 #endif
00478