Merge branch 'master' into devel
[dyninst.git] / dynutil / h / AST.h
1 /*
2  * Copyright (c) 2007-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
30  */
31
32 #if !defined(AST_H)
33 #define AST_H
34
35 #include <vector>
36 #include <string>
37 #include <sstream>
38 #include <dyn_detail/boost/shared_ptr.hpp>
39 #include <dyn_detail/boost/enable_shared_from_this.hpp>
40 #include "util.h"
41
42 namespace Dyninst {
43
44 // We fully template the three types of nodes we have so that
45 // users can specify their own. This basically makes the AST
46 // a fully generic class. 
47 //
48 // TODO: do we want Variable and Constant to be different classes?
49 // I'm using the Absloc case as the basis here; EAX and '5' are
50 // very different things...
51 //
52 // Possible fourth template type: Type
53 // though I'm currently arguing that Type is an artifact of the
54 // Eval method you apply here. 
55 // ... and are Eval methods independent of Operation/Variable/Constant?
56 // I think they are...x
57
58 class ASTVisitor;  
59
60  // For this to work, the ASTVisitor has to have a virtual
61  // visit() method for every instantiation of an AST-typed
62  // class. Yes, this means that if you add an AST class
63  // somewhere else you have to come back and put it in here. 
64  // Well, if you want to run a visitor over it, that is.
65  class AST;
66
67  // SymEval...
68  namespace SymbolicEvaluation {
69  class BottomAST;
70  class ConstantAST;
71  class VariableAST;
72  class RoseAST;
73  };
74  // Stack analysis...
75  class StackAST;
76
77  // InsnAPI...
78
79  // Codegen...
80
81  // Concolic execution...
82  class InputVariableAST;
83  class ReferenceAST;
84  class StpAST;
85  class YicesAST;
86
87 #define DEF_AST_LEAF_TYPE(name, type)                                   \
88 class name : public AST {                                               \
89  public:                                                                \
90  typedef dyn_detail::boost::shared_ptr<name> Ptr;                       \
91  static Ptr create(type t) { return Ptr(new name(t)); }                 \
92  virtual ~name() {};                                                    \
93  virtual const std::string format() const {                             \
94    std::stringstream ret;                                               \
95    ret << "<" << t_ << ">";                                             \
96    return ret.str();                                                    \
97  }                                                                      \
98  virtual AST::Ptr accept(ASTVisitor *v) { return v->visit(this); }      \
99  virtual ID getID() const { return V_##name; }                          \
100   static Ptr convert(AST::Ptr a) {                                      \
101     return ((a->getID() == V_##name) ? dyn_detail::boost::static_pointer_cast<name>(a) : Ptr()); \
102   }                                                                     \
103   const type &val() const { return t_; }                                \
104  private:                                                               \
105  name(type t) : t_(t) {};                                               \
106  virtual bool isStrictEqual(const AST &rhs) const {                     \
107    const name &other(dynamic_cast<const name&>(rhs));                   \
108    return t_ == other.t_;                                               \
109  }                                                                      \
110  const type t_;                                                         \
111  };                                                                     \
112
113 #define DEF_AST_INTERNAL_TYPE(name, type)                               \
114 class name : public AST {                                               \
115  public:                                                                \
116   typedef dyn_detail::boost::shared_ptr<name> Ptr;                      \
117   virtual ~name() {};                                                   \
118   static Ptr create(type t, AST::Ptr a) { return Ptr(new name(t, a)); } \
119   static Ptr create(type t, AST::Ptr a, AST::Ptr b) { return Ptr(new name(t, a, b)); } \
120   static Ptr create(type t, AST::Ptr a, AST::Ptr b, AST::Ptr c) { return Ptr(new name(t, a, b, c)); } \
121   static Ptr create(type t, Children c) { return Ptr(new name(t, c)); } \
122   virtual const std::string format() const {                            \
123     std::stringstream ret;                                              \
124     ret << t_ << "(";                                                   \
125     for (Children::const_iterator i = kids_.begin(); i != kids_.end(); ++i) {   \
126       ret << (*i)->format() << ",";                                     \
127     }                                                                   \
128     ret << ")";                                                         \
129     return ret.str();                                                   \
130   }                                                                     \
131   virtual AST::Ptr child(unsigned i) const { return kids_[i];}          \
132   virtual unsigned numChildren() const { return kids_.size();}          \
133   virtual AST::Ptr accept(ASTVisitor *v) { return v->visit(this); }     \
134   virtual ID getID() const { return V_##name; }                         \
135   static Ptr convert(AST::Ptr a) {                                      \
136     return ((a->getID() == V_##name) ? dyn_detail::boost::static_pointer_cast<name>(a) : Ptr()); \
137   }                                                                     \
138   const type &val() const { return t_; }                                \
139   void setChild(int i, AST::Ptr a) { kids_[i] = a; };                   \
140  private:                                                               \
141  name(type t, AST::Ptr a) : t_(t) { kids_.push_back(a); };              \
142  name(type t, AST::Ptr a, AST::Ptr b) : t_(t) {                         \
143     kids_.push_back(a);                                                 \
144     kids_.push_back(b);                                                 \
145   };                                                                    \
146  name(type t, AST::Ptr a, AST::Ptr b, AST::Ptr c) : t_(t) {             \
147     kids_.push_back(a);                                                 \
148     kids_.push_back(b);                                                 \
149     kids_.push_back(c);                                                 \
150   };                                                                    \
151  name(type t, Children kids) : t_(t), kids_(kids) {};                   \
152   virtual bool isStrictEqual(const AST &rhs) const {                    \
153     const name &other(dynamic_cast<const name&>(rhs));                  \
154     return ((t_ == other.t_) && (kids_ == other.kids_));                \
155   }                                                                     \
156   const type t_;                                                        \
157   Children kids_;                                                       \
158  };                                                                     \
159
160 class AST : public dyn_detail::boost::enable_shared_from_this<AST> {
161  public:
162
163   // This is a global list of all AST types, including those that are not
164   // yet implemented. The format is a "V_" string prepending the class name.
165   // If you add an AST type you should update this list.
166
167   typedef enum {
168     V_AST,
169     // SymEval
170     V_BottomAST,
171     V_ConstantAST,
172     V_VariableAST,
173     V_RoseAST,
174     // Stack analysis
175     V_StackAST,
176     // Concolic execution
177     V_InputVariableAST,
178     V_ReferenceAST,
179     V_StpAST,
180     V_YicesAST } ID;
181
182   typedef dyn_detail::boost::shared_ptr<AST> Ptr;
183   typedef std::vector<AST::Ptr> Children;      
184
185   AST() {};
186   virtual ~AST() {};
187   
188   bool operator==(const AST &rhs) const {
189     // make sure rhs and this have the same type
190     return((typeid(*this) == typeid(rhs)) && isStrictEqual(rhs));
191   }
192
193   virtual unsigned numChildren() const { return 0; }                   
194
195   virtual AST::Ptr child(unsigned) const {                              
196     assert(0);                                                          
197     return AST::Ptr();                                                  
198   }                                                                    
199
200   virtual const std::string format() const = 0;
201
202   // Substitutes every occurrence of a with b in
203   // AST in. Returns a new AST. 
204
205   static COMMON_EXPORT AST::Ptr substitute(AST::Ptr in, AST::Ptr a, AST::Ptr b); 
206
207   virtual ID getID() const { return V_AST; };
208
209   // VISITOR wooo....
210   virtual Ptr accept(ASTVisitor *);
211
212   Ptr ptr() { return shared_from_this(); }
213
214   virtual void setChild(int, AST::Ptr) {
215     assert(0);
216   };
217
218  protected:
219   virtual bool isStrictEqual(const AST &rhs) const = 0;
220 };
221
222  class ASTVisitor {
223  public:
224    typedef dyn_detail::boost::shared_ptr<AST> ASTPtr;
225    virtual ASTPtr visit(AST *) {return AST::Ptr();};
226    virtual ASTPtr visit(SymbolicEvaluation::BottomAST *) {return AST::Ptr();};
227    virtual ASTPtr visit(SymbolicEvaluation::ConstantAST *) {return AST::Ptr();};
228    virtual ASTPtr visit(SymbolicEvaluation::VariableAST *) {return AST::Ptr();};
229    virtual ASTPtr visit(SymbolicEvaluation::RoseAST *) {return AST::Ptr();};
230    virtual ASTPtr visit(StackAST *) {return AST::Ptr();};
231    virtual ASTPtr visit(InputVariableAST *) {return AST::Ptr();};
232    virtual ASTPtr visit(ReferenceAST *) {return AST::Ptr();};
233    virtual ASTPtr visit(StpAST *) {return AST::Ptr();};
234    virtual ASTPtr visit(YicesAST *) {return AST::Ptr();};
235
236    virtual ~ASTVisitor() {};
237  };
238
239 }
240 #endif // AST_H
241