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 <iostream>
39 #include <dyn_detail/boost/shared_ptr.hpp>
40 #include <dyn_detail/boost/enable_shared_from_this.hpp>
41 #include "util.h"
42
43 namespace Dyninst {
44
45 // We fully template the three types of nodes we have so that
46 // users can specify their own. This basically makes the AST
47 // a fully generic class. 
48 //
49 // TODO: do we want Variable and Constant to be different classes?
50 // I'm using the Absloc case as the basis here; EAX and '5' are
51 // very different things...
52 //
53 // Possible fourth template type: Type
54 // though I'm currently arguing that Type is an artifact of the
55 // Eval method you apply here. 
56 // ... and are Eval methods independent of Operation/Variable/Constant?
57 // I think they are...x
58
59 class ASTVisitor;  
60
61  // For this to work, the ASTVisitor has to have a virtual
62  // visit() method for every instantiation of an AST-typed
63  // class. Yes, this means that if you add an AST class
64  // somewhere else you have to come back and put it in here. 
65  // Well, if you want to run a visitor over it, that is.
66  class AST;
67
68  // SymEval...
69  namespace DataflowAPI {
70  class BottomAST;
71  class ConstantAST;
72  class VariableAST;
73  class RoseAST;
74  };
75  // Stack analysis...
76  class StackAST;
77
78  // InsnAPI...
79
80  // Codegen...
81
82  // Concolic execution...
83  class InputVariableAST;
84  class ReferenceAST;
85  class StpAST;
86  class YicesAST;
87  class SemanticsAST;
88
89 #define DEF_AST_LEAF_TYPE(name, type)                                   \
90 class name : public AST {                                               \
91  public:                                                                \
92  typedef dyn_detail::boost::shared_ptr<name> Ptr;                       \
93  static Ptr create(type t) { return Ptr(new name(t)); }                 \
94  virtual ~name() {};                                                    \
95  virtual const std::string format() const {                             \
96    std::stringstream ret;                                               \
97    ret << "<" << t_ << ">";                                             \
98    return ret.str();                                                    \
99  }                                                                      \
100  virtual AST::Ptr accept(ASTVisitor *v) { return v->visit(this); }      \
101  virtual ID getID() const { return V_##name; }                          \
102   static Ptr convert(AST::Ptr a) {                                      \
103     return ((a->getID() == V_##name) ? dyn_detail::boost::static_pointer_cast<name>(a) : Ptr()); \
104   }                                                                     \
105   const type &val() const { return t_; }                                \
106  private:                                                               \
107  name(type t) : t_(t) {};                                               \
108  virtual bool isStrictEqual(const AST &rhs) const {                     \
109    const name &other(dynamic_cast<const name&>(rhs));                   \
110    return t_ == other.t_;                                               \
111  }                                                                      \
112  const type t_;                                                         \
113  };                                                                     \
114
115 #define DEF_AST_INTERNAL_TYPE(name, type)                               \
116 class name : public AST {                                               \
117  public:                                                                \
118   typedef dyn_detail::boost::shared_ptr<name> Ptr;                      \
119   virtual ~name() {};                                                   \
120   static Ptr create(type t, AST::Ptr a) { return Ptr(new name(t, a)); } \
121   static Ptr create(type t, AST::Ptr a, AST::Ptr b) { return Ptr(new name(t, a, b)); } \
122   static Ptr create(type t, AST::Ptr a, AST::Ptr b, AST::Ptr c) { return Ptr(new name(t, a, b, c)); } \
123   static Ptr create(type t, Children c) { return Ptr(new name(t, c)); } \
124   virtual const std::string format() const {                            \
125     std::stringstream ret;                                              \
126     ret << t_ << "(";                                                   \
127     for (Children::const_iterator i = kids_.begin(); i != kids_.end(); ++i) {   \
128       ret << (*i)->format() << ",";                                     \
129     }                                                                   \
130     ret << ")";                                                         \
131     return ret.str();                                                   \
132   }                                                                     \
133   virtual AST::Ptr child(unsigned i) const { return kids_[i];}          \
134   virtual unsigned numChildren() const { return kids_.size();}          \
135   virtual AST::Ptr accept(ASTVisitor *v) { return v->visit(this); }     \
136   virtual ID getID() const { return V_##name; }                         \
137   static Ptr convert(AST::Ptr a) {                                      \
138     return ((a->getID() == V_##name) ? dyn_detail::boost::static_pointer_cast<name>(a) : Ptr()); \
139   }                                                                     \
140   const type &val() const { return t_; }                                \
141   void setChild(int i, AST::Ptr a) { kids_[i] = a; };                   \
142  private:                                                               \
143  name(type t, AST::Ptr a) : t_(t) { kids_.push_back(a); };              \
144  name(type t, AST::Ptr a, AST::Ptr b) : t_(t) {                         \
145     kids_.push_back(a);                                                 \
146     kids_.push_back(b);                                                 \
147   };                                                                    \
148  name(type t, AST::Ptr a, AST::Ptr b, AST::Ptr c) : t_(t) {             \
149     kids_.push_back(a);                                                 \
150     kids_.push_back(b);                                                 \
151     kids_.push_back(c);                                                 \
152   };                                                                    \
153  name(type t, Children kids) : t_(t), kids_(kids) {};                   \
154   virtual bool isStrictEqual(const AST &rhs) const {                    \
155     const name &other(dynamic_cast<const name&>(rhs));                  \
156     if (!(t_ == other.t_)) return false;                                \
157     if (kids_.size() != other.kids_.size()) return false;               \
158     for (unsigned i = 0; i < kids_.size(); ++i)                         \
159       if (!(kids_[i]->equals(other.kids_[i]))) return false;            \
160     return true;                                                        \
161   }                                                                     \
162   const type t_;                                                        \
163   Children kids_;                                                       \
164  };                                                                     \
165
166 class COMMON_EXPORT AST : public dyn_detail::boost::enable_shared_from_this<AST> {
167  public:
168
169   // This is a global list of all AST types, including those that are not
170   // yet implemented. The format is a "V_" string prepending the class name.
171   // If you add an AST type you should update this list.
172
173   typedef enum {
174     V_AST,
175     // SymEval
176     V_BottomAST,
177     V_ConstantAST,
178     V_VariableAST,
179     V_RoseAST,
180     // Stack analysis
181     V_StackAST,
182     // Concolic execution
183     V_InputVariableAST,
184     V_ReferenceAST,
185     V_StpAST,
186     V_YicesAST,
187     V_SemanticsAST } ID;
188
189   typedef dyn_detail::boost::shared_ptr<AST> Ptr;
190   typedef std::vector<AST::Ptr> Children;      
191
192   AST() {};
193   virtual ~AST() {};
194   
195   bool operator==(const AST &rhs) const {
196     // make sure rhs and this have the same type
197     return((typeid(*this) == typeid(rhs)) && isStrictEqual(rhs));
198   }
199
200   virtual unsigned numChildren() const { return 0; }                   
201
202   virtual AST::Ptr child(unsigned) const {                              
203     assert(0);                                                          
204     return AST::Ptr();                                                  
205   }                                                                    
206
207   bool equals(AST::Ptr rhs) {
208     if (!rhs) return false;
209     return *this == (*rhs);
210   }
211
212   virtual const std::string format() const = 0;
213
214   // Substitutes every occurrence of a with b in
215   // AST in. Returns a new AST. 
216
217   static AST::Ptr substitute(AST::Ptr in, AST::Ptr a, AST::Ptr b); 
218
219   virtual ID getID() const { return V_AST; };
220
221   // VISITOR wooo....
222   virtual Ptr accept(ASTVisitor *);
223
224   Ptr ptr() { return shared_from_this(); }
225
226   virtual void setChild(int, AST::Ptr) {
227     assert(0);
228   };
229
230  protected:
231   virtual bool isStrictEqual(const AST &rhs) const = 0;
232 };
233
234  class COMMON_EXPORT ASTVisitor {
235  public:
236    typedef dyn_detail::boost::shared_ptr<AST> ASTPtr;
237    virtual ASTPtr visit(AST *) {return AST::Ptr();};
238    virtual ASTPtr visit(DataflowAPI::BottomAST *) {return AST::Ptr();};
239    virtual ASTPtr visit(DataflowAPI::ConstantAST *) {return AST::Ptr();};
240    virtual ASTPtr visit(DataflowAPI::VariableAST *) {return AST::Ptr();};
241    virtual ASTPtr visit(DataflowAPI::RoseAST *) {return AST::Ptr();};
242    virtual ASTPtr visit(StackAST *) {return AST::Ptr();};
243    virtual ASTPtr visit(InputVariableAST *) {return AST::Ptr();};
244    virtual ASTPtr visit(ReferenceAST *) {return AST::Ptr();};
245    virtual ASTPtr visit(StpAST *) {return AST::Ptr();};
246    virtual ASTPtr visit(YicesAST *) {return AST::Ptr();};
247    virtual ASTPtr visit(SemanticsAST *) {return AST::Ptr();};
248
249    virtual ~ASTVisitor() {};
250  };
251
252 }
253 #endif // AST_H
254