staptree.h

   1 // -*- C++ -*-
   2 // Copyright (C) 2005-2014 Red Hat Inc.
   3 // Copyright (C) 2006 Intel Corporation.
   4 //
   5 // This file is part of systemtap, and is free software.  You can
   6 // redistribute it and/or modify it under the terms of the GNU General
   7 // Public License (GPL); either version 2, or (at your option) any
   8 // later version.
   9
  10 #ifndef STAPTREE_H
  11 #define STAPTREE_H
  12
  13 #include <map>
  14 #include <stack>
  15 #include <set>
  16 #include <string>
  17 #include <vector>
  18 #include <iostream>
  19 #include <stdexcept>
  20 #include <cassert>
  21 #include <typeinfo>
  22 extern "C" {
  23 #include <stdint.h>
  24 }
  25
  26 #include "util.h"
  27
  28 #if defined(HAVE_TR1_MEMORY)
  29 #include <tr1/memory>
  30 using std::tr1::shared_ptr;
  31 #elif defined(HAVE_BOOST_SHARED_PTR_HPP)
  32 #include <boost/shared_ptr.hpp>
  33 using boost::shared_ptr;
  34 #else
  35 #error "No shared_ptr implementation found; get boost or modern g++"
  36 #endif
  37
  38 struct token; // parse.h
  39 struct systemtap_session; // session.h
  40
  41 struct semantic_error: public std::runtime_error
  42 {
  43   const token* tok1;
  44   const token* tok2;
  45   std::string errsrc;
  46
  47   // Extra details to explain the error or provide alternatives to the user.
  48   // Each one printed after the main error message and tokens aligned on
  49   // separate lines. Just push_back anything you want that better explains
  50   // the error to the user (not meant for extra verbose developer messages).
  51   std::vector<std::string> details;
  52
  53   ~semantic_error () throw ()
  54     {
  55       if (chain)
  56         delete chain;
  57     }
  58
  59   semantic_error (const std::string& src, const std::string& msg, const token* t1=0):
  60     runtime_error (msg), tok1 (t1), tok2 (0), errsrc (src), chain (0) {}
  61
  62   semantic_error (const std::string& src, const std::string& msg, const token* t1,
  63                   const token* t2, const semantic_error* chn=0):
  64       runtime_error (msg), tok1 (t1), tok2 (t2), errsrc (src), chain (0)
  65     {
  66       if (chn)
  67         set_chain(*chn);
  68     }
  69
  70   /* override copy-ctor to deep-copy chain */
  71   semantic_error (const semantic_error& other):
  72       runtime_error(other), tok1(other.tok1), tok2(other.tok2),
  73       errsrc(other.errsrc), details(other.details), chain (0)
  74     {
  75       if (other.chain)
  76         set_chain(*other.chain);
  77     }
  78
  79   std::string errsrc_chain(void) const
  80     {
  81       return errsrc + (chain ? "|" + chain->errsrc_chain() : "");
  82     }
  83
  84   void set_chain(const semantic_error& new_chain)
  85     {
  86       if (chain)
  87         delete chain;
  88       chain = new semantic_error(new_chain);
  89     }
  90
  91   const semantic_error* get_chain(void) const
  92     {
  93       return chain;
  94     }
  95
  96 private:
  97   const semantic_error* chain;
  98 };
  99
 100 // ------------------------------------------------------------------------
 101
 102 /* struct statistic_decl moved to session.h */
 103
 104 // ------------------------------------------------------------------------
 105
 106 enum exp_type
 107   {
 108     pe_unknown,
 109     pe_long,   // int64_t
 110     pe_string, // std::string
 111     pe_stats
 112   };
 113
 114 std::ostream& operator << (std::ostream& o, const exp_type& e);
 115
 116 struct functioncall;
 117 struct autocast_op;
 118 struct exp_type_details
 119 {
 120   virtual ~exp_type_details () {};
 121
 122   // A process-wide unique identifier; probably a pointer.
 123   virtual uintptr_t id () const = 0;
 124   bool operator==(const exp_type_details& other) const
 125     { return id () == other.id (); }
 126   bool operator!=(const exp_type_details& other) const
 127     { return !(*this == other); }
 128
 129   // Expand this autocast_op into a function call
 130   virtual bool expandable() const = 0;
 131   virtual functioncall *expand(autocast_op* e, bool lvalue) = 0;
 132 };
 133 typedef shared_ptr<exp_type_details> exp_type_ptr;
 134
 135
 136 struct token;
 137 struct visitor;
 138 struct update_visitor;
 139
 140 struct visitable
 141 {
 142   virtual ~visitable ();
 143 };
 144
 145 struct expression : public visitable
 146 {
 147   exp_type type;
 148   exp_type_ptr type_details;
 149   const token* tok;
 150   expression ();
 151   virtual ~expression ();
 152   virtual void print (std::ostream& o) const = 0;
 153   virtual void visit (visitor* u) = 0;
 154 };
 155
 156 std::ostream& operator << (std::ostream& o, const expression& k);
 157
 158
 159 struct literal: public expression
 160 {
 161 };
 162
 163
 164 struct literal_string: public literal
 165 {
 166   std::string value;
 167   literal_string (const std::string& v);
 168   void print (std::ostream& o) const;
 169   void visit (visitor* u);
 170 };
 171
 172
 173 struct literal_number: public literal
 174 {
 175   int64_t value;
 176   bool print_hex;
 177   literal_number (int64_t v, bool hex=false);
 178   void print (std::ostream& o) const;
 179   void visit (visitor* u);
 180 };
 181
 182
 183 struct embedded_expr: public expression
 184 {
 185   std::string code;
 186   void print (std::ostream& o) const;
 187   void visit (visitor* u);
 188 };
 189
 190
 191 struct binary_expression: public expression
 192 {
 193   expression* left;
 194   std::string op;
 195   expression* right;
 196   void print (std::ostream& o) const;
 197   void visit (visitor* u);
 198 };
 199
 200
 201 struct unary_expression: public expression
 202 {
 203   std::string op;
 204   expression* operand;
 205   void print (std::ostream& o) const;
 206   void visit (visitor* u);
 207 };
 208
 209
 210 struct pre_crement: public unary_expression
 211 {
 212   void visit (visitor* u);
 213 };
 214
 215
 216 struct post_crement: public unary_expression
 217 {
 218   void print (std::ostream& o) const;
 219   void visit (visitor* u);
 220 };
 221
 222
 223 struct logical_or_expr: public binary_expression
 224 {
 225   void visit (visitor* u);
 226 };
 227
 228
 229 struct logical_and_expr: public binary_expression
 230 {
 231   void visit (visitor* u);
 232 };
 233
 234
 235 struct arrayindex;
 236 struct array_in: public expression
 237 {
 238   arrayindex* operand;
 239   void print (std::ostream& o) const;
 240   void visit (visitor* u);
 241 };
 242
 243 struct regex_query: public expression
 244 {
 245   expression* left;
 246   std::string op;
 247   literal_string* right;
 248   void visit (visitor* u);
 249   void print (std::ostream& o) const;
 250 };
 251
 252 struct comparison: public binary_expression
 253 {
 254   void visit (visitor* u);
 255 };
 256
 257
 258 struct concatenation: public binary_expression
 259 {
 260   void visit (visitor* u);
 261 };
 262
 263
 264 struct ternary_expression: public expression
 265 {
 266   expression* cond;
 267   expression* truevalue;
 268   expression* falsevalue;
 269   void print (std::ostream& o) const;
 270   void visit (visitor* u);
 271 };
 272
 273
 274 struct assignment: public binary_expression
 275 {
 276   void visit (visitor* u);
 277 };
 278
 279 struct symbol;
 280 struct hist_op;
 281 struct indexable : public expression
 282 {
 283   // This is a helper class which, type-wise, acts as a disjoint union
 284   // of symbols and histograms. You can ask it whether it's a
 285   // histogram or a symbol, and downcast accordingly.
 286   virtual bool is_symbol(symbol *& sym_out);
 287   virtual bool is_hist_op(hist_op *& hist_out);
 288   virtual ~indexable() {}
 289 };
 290
 291 // Perform a downcast to one out-value and NULL the other, throwing an
 292 // exception if neither downcast succeeds. This is (sadly) about the
 293 // best we can accomplish in C++.
 294 void
 295 classify_indexable(indexable* ix,
 296                    symbol *& array_out,
 297                    hist_op *& hist_out);
 298
 299 struct vardecl;
 300 struct symbol: public indexable
 301 {
 302   std::string name;
 303   vardecl *referent;
 304   symbol ();
 305   void print (std::ostream& o) const;
 306   void visit (visitor* u);
 307   // overrides of type 'indexable'
 308   bool is_symbol(symbol *& sym_out);
 309 };
 310
 311
 312 struct target_symbol: public expression
 313 {
 314   enum component_type
 315     {
 316       comp_struct_member,
 317       comp_literal_array_index,
 318       comp_expression_array_index,
 319       comp_pretty_print, // must be final
 320     };
 321
 322   struct component
 323     {
 324       const token* tok;
 325       component_type type;
 326       std::string member; // comp_struct_member, comp_pretty_print
 327       int64_t num_index; // comp_literal_array_index
 328       expression* expr_index; // comp_expression_array_index
 329
 330       component(const token* t, const std::string& m, bool pprint=false):
 331         tok(t),
 332         type(pprint ? comp_pretty_print : comp_struct_member),
 333         member(m), num_index(0), expr_index(0)
 334       {}
 335       component(const token* t, int64_t n):
 336         tok(t), type(comp_literal_array_index), num_index(n),
 337         expr_index(0) {}
 338       component(const token* t, expression* e):
 339         tok(t), type(comp_expression_array_index), num_index(0),
 340          expr_index(e) {}
 341       void print (std::ostream& o) const;
 342     };
 343
 344   std::string name;
 345   bool addressof;
 346   std::vector<component> components;
 347   semantic_error* saved_conversion_error; // hand-made linked list
 348   target_symbol(): addressof(false), saved_conversion_error (0) {}
 349   virtual std::string sym_name ();
 350   void chain (const semantic_error& er);
 351   void print (std::ostream& o) const;
 352   void visit (visitor* u);
 353   void visit_components (visitor* u);
 354   void visit_components (update_visitor* u);
 355   void assert_no_components(const std::string& tapset, bool pretty_ok=false);
 356   size_t pretty_print_depth () const;
 357   bool check_pretty_print (bool lvalue=false) const;
 358 };
 359
 360 std::ostream& operator << (std::ostream& o, const target_symbol::component& c);
 361
 362
 363 struct cast_op: public target_symbol
 364 {
 365   expression *operand;
 366   std::string type_name, module;
 367   void print (std::ostream& o) const;
 368   void visit (visitor* u);
 369 };
 370
 371 // An autocast is like an implicit @cast on any expression, like
 372 // (expr)->foo->var[baz], and the type is gleaned from the expr.
 373 struct autocast_op: public target_symbol
 374 {
 375   expression *operand;
 376   void print (std::ostream& o) const;
 377   void visit (visitor* u);
 378 };
 379
 380 struct atvar_op: public target_symbol
 381 {
 382   std::string target_name, cu_name, module;
 383   virtual std::string sym_name ();
 384   void print (std::ostream& o) const;
 385   void visit (visitor* u);
 386 };
 387
 388 struct defined_op: public expression
 389 {
 390   expression *operand;
 391   void print (std::ostream& o) const;
 392   void visit (visitor* u);
 393 };
 394
 395
 396 struct entry_op: public expression
 397 {
 398   expression *operand;
 399   void print (std::ostream& o) const;
 400   void visit (visitor* u);
 401 };
 402
 403
 404 struct perf_op: public expression
 405 {
 406   literal_string *operand;
 407   void print (std::ostream& o) const;
 408   void visit (visitor* u);
 409 };
 410
 411
 412 struct arrayindex: public expression
 413 {
 414   std::vector<expression*> indexes;
 415   indexable *base;
 416   arrayindex ();
 417   void print (std::ostream& o) const;
 418   void visit (visitor* u);
 419 };
 420
 421
 422 struct functiondecl;
 423 struct functioncall: public expression
 424 {
 425   std::string function;
 426   std::vector<expression*> args;
 427   functiondecl *referent;
 428   functioncall ();
 429   void print (std::ostream& o) const;
 430   void visit (visitor* u);
 431 };
 432
 433
 434 struct print_format: public expression
 435 {
 436   bool print_to_stream;
 437   bool print_with_format;
 438   bool print_with_delim;
 439   bool print_with_newline;
 440   bool print_char;
 441
 442   // XXX match runtime/vsprintf.c's print_flag
 443   // ... for use with number() & number_size()
 444   enum format_flag
 445     {
 446       fmt_flag_zeropad = 1,
 447       fmt_flag_sign = 2,
 448       fmt_flag_plus = 4,
 449       fmt_flag_space = 8,
 450       fmt_flag_left = 16,
 451       fmt_flag_special = 32,
 452       fmt_flag_large = 64,
 453     };
 454
 455   enum conversion_type
 456     {
 457       conv_unspecified,
 458       conv_pointer,
 459       conv_number,
 460       conv_string,
 461       conv_char,
 462       conv_memory,
 463       conv_memory_hex,
 464       conv_literal,
 465       conv_binary
 466     };
 467
 468   enum width_type
 469     {
 470       width_unspecified,
 471       width_static,
 472       width_dynamic
 473     };
 474
 475   enum precision_type
 476     {
 477       prec_unspecified,
 478       prec_static,
 479       prec_dynamic
 480     };
 481
 482   struct format_component
 483   {
 484     unsigned long flags;
 485     unsigned base;
 486     unsigned width;
 487     unsigned precision;
 488     width_type widthtype;
 489     precision_type prectype;
 490     conversion_type type;
 491     std::string literal_string;
 492     bool is_empty() const
 493     {
 494       return flags == 0
 495         && widthtype == width_unspecified
 496         && prectype == prec_unspecified
 497         && type == conv_unspecified
 498         && literal_string.empty();
 499     }
 500     void clear()
 501     {
 502       flags = 0;
 503       widthtype = width_unspecified;
 504       precision = 0;
 505       prectype = prec_unspecified;
 506       type = conv_unspecified;
 507       literal_string.clear();
 508     }
 509     format_component() { clear(); }
 510     inline void set_flag(format_flag f) { flags |= f; }
 511     inline bool test_flag(format_flag f) const { return flags & f; }
 512   };
 513
 514   std::string raw_components;
 515   std::vector<format_component> components;
 516   format_component delimiter;
 517   std::vector<expression*> args;
 518   hist_op *hist;
 519
 520   static std::string components_to_string(std::vector<format_component> const & components);
 521   static std::vector<format_component> string_to_components(std::string const & str);
 522   static print_format* create(const token *t, const char *n = NULL);
 523
 524   void print (std::ostream& o) const;
 525   void visit (visitor* u);
 526
 527 private:
 528   std::string print_format_type;
 529   print_format(bool stream, bool format, bool delim, bool newline, bool _char, std::string type):
 530     print_to_stream(stream), print_with_format(format),
 531     print_with_delim(delim), print_with_newline(newline),
 532     print_char(_char), hist(NULL), print_format_type(type)
 533   {}
 534 };
 535
 536
 537 enum stat_component_type
 538   {
 539     sc_average,
 540     sc_count,
 541     sc_sum,
 542     sc_min,
 543     sc_max,
 544     sc_none,
 545   };
 546
 547 struct stat_op: public expression
 548 {
 549   stat_component_type ctype;
 550   expression* stat;
 551   void print (std::ostream& o) const;
 552   void visit (visitor* u);
 553 };
 554
 555 enum histogram_type
 556   {
 557     hist_linear,
 558     hist_log
 559   };
 560
 561 struct hist_op: public indexable
 562 {
 563   histogram_type htype;
 564   expression* stat;
 565   std::vector<int64_t> params;
 566   void print (std::ostream& o) const;
 567   void visit (visitor* u);
 568   // overrides of type 'indexable'
 569   bool is_hist_op(hist_op *& hist_out);
 570 };
 571
 572 // ------------------------------------------------------------------------
 573
 574
 575 struct symboldecl // unique object per (possibly implicit)
 576                   // symbol declaration
 577 {
 578   const token* tok;
 579   const token* systemtap_v_conditional; //checking systemtap compatibility
 580   std::string name;
 581   exp_type type;
 582   exp_type_ptr type_details;
 583   symboldecl ();
 584   virtual ~symboldecl ();
 585   virtual void print (std::ostream &o) const = 0;
 586   virtual void printsig (std::ostream &o) const = 0;
 587 };
 588
 589
 590 std::ostream& operator << (std::ostream& o, const symboldecl& k);
 591
 592
 593 struct vardecl: public symboldecl
 594 {
 595   void print (std::ostream& o) const;
 596   void printsig (std::ostream& o) const;
 597   vardecl ();
 598   void set_arity (int arity, const token* t);
 599   bool compatible_arity (int a);
 600   const token* arity_tok; // site where arity was first resolved
 601   int arity; // -1: unknown; 0: scalar; >0: array
 602   int maxsize; // upperbound on size for arrays
 603   std::vector<exp_type> index_types; // for arrays only
 604   literal *init; // for global scalars only
 605   bool synthetic; // for probe locals only, don't init on entry
 606   bool wrap;
 607 };
 608
 609
 610 struct vardecl_builtin: public vardecl
 611 {
 612 };
 613
 614 struct statement;
 615 struct functiondecl: public symboldecl
 616 {
 617   std::vector<vardecl*> formal_args;
 618   std::vector<vardecl*> locals;
 619   std::vector<vardecl*> unused_locals;
 620   statement* body;
 621   bool synthetic;
 622   bool mangle_oldstyle;
 623   functiondecl ();
 624   void print (std::ostream& o) const;
 625   void printsig (std::ostream& o) const;
 626   void printsigtags (std::ostream& o, bool all_tags) const;
 627   void join (systemtap_session& s); // for synthetic functions only
 628 };
 629
 630
 631 // ------------------------------------------------------------------------
 632
 633
 634 struct statement : public visitable
 635 {
 636   virtual void print (std::ostream& o) const = 0;
 637   virtual void visit (visitor* u) = 0;
 638   const token* tok;
 639   statement ();
 640   statement (const token* tok);
 641   virtual ~statement ();
 642 };
 643
 644 std::ostream& operator << (std::ostream& o, const statement& k);
 645
 646
 647 struct embeddedcode: public statement
 648 {
 649   std::string code;
 650   void print (std::ostream& o) const;
 651   void visit (visitor* u);
 652 };
 653
 654
 655 struct block: public statement
 656 {
 657   std::vector<statement*> statements;
 658   void print (std::ostream& o) const;
 659   void visit (visitor* u);
 660   block () {}
 661   block (statement* car, statement* cdr);
 662   virtual ~block () {}
 663 };
 664
 665
 666 struct try_block: public statement
 667 {
 668   statement* try_block; // may be 0
 669   statement* catch_block; // may be 0
 670   symbol* catch_error_var; // may be 0
 671   void print (std::ostream& o) const;
 672   void visit (visitor* u);
 673 };
 674
 675
 676 struct expr_statement;
 677 struct for_loop: public statement
 678 {
 679   expr_statement* init; // may be 0
 680   expression* cond;
 681   expr_statement* incr; // may be 0
 682   statement* block;
 683   void print (std::ostream& o) const;
 684   void visit (visitor* u);
 685 };
 686
 687
 688 struct foreach_loop: public statement
 689 {
 690   // this part is a specialization of arrayindex
 691   std::vector<symbol*> indexes;
 692   std::vector<expression*> array_slice; // optional array slice to iterate over
 693   indexable *base;
 694   int sort_direction; // -1: decreasing, 0: none, 1: increasing
 695   unsigned sort_column; // 0: value, 1..N: index
 696   enum stat_component_type sort_aggr; // for aggregate arrays, which aggregate to sort on
 697   symbol* value; // optional iteration value
 698   expression* limit; // optional iteration limit
 699
 700   statement* block;
 701   void print (std::ostream& o) const;
 702   void visit (visitor* u);
 703 };
 704
 705
 706 struct null_statement: public statement
 707 {
 708   void print (std::ostream& o) const;
 709   void visit (visitor* u);
 710   null_statement (const token* tok);
 711 };
 712
 713
 714 struct expr_statement: public statement
 715 {
 716   expression* value;  // executed for side-effects
 717   void print (std::ostream& o) const;
 718   void visit (visitor* u);
 719 };
 720
 721
 722 struct if_statement: public statement
 723 {
 724   expression* condition;
 725   statement* thenblock;
 726   statement* elseblock; // may be 0
 727   void print (std::ostream& o) const;
 728   void visit (visitor* u);
 729 };
 730
 731
 732 struct return_statement: public expr_statement
 733 {
 734   void print (std::ostream& o) const;
 735   void visit (visitor* u);
 736 };
 737
 738
 739 struct delete_statement: public expr_statement
 740 {
 741   void print (std::ostream& o) const;
 742   void visit (visitor* u);
 743 };
 744
 745
 746 struct break_statement: public statement
 747 {
 748   void print (std::ostream& o) const;
 749   void visit (visitor* u);
 750 };
 751
 752
 753 struct continue_statement: public statement
 754 {
 755   void print (std::ostream& o) const;
 756   void visit (visitor* u);
 757 };
 758
 759
 760 struct next_statement: public statement
 761 {
 762   void print (std::ostream& o) const;
 763   void visit (visitor* u);
 764 };
 765
 766
 767 struct probe;
 768 struct derived_probe;
 769 struct probe_alias;
 770 struct embeddedcode;
 771 struct stapfile
 772 {
 773   std::string name;
 774   std::vector<probe*> probes;
 775   std::vector<probe_alias*> aliases;
 776   std::vector<functiondecl*> functions;
 777   std::vector<vardecl*> globals;
 778   std::vector<embeddedcode*> embeds;
 779   std::string file_contents;
 780   bool privileged;
 781   bool synthetic; // via parse_synthetic_*
 782   stapfile (): file_contents (""),
 783     privileged (false), synthetic (false) {}
 784   void print (std::ostream& o) const;
 785 };
 786
 787
 788 struct probe_point
 789 {
 790   struct component // XXX: sort of a restricted functioncall
 791   {
 792     std::string functor;
 793     literal* arg; // optional
 794     component ();
 795     const token* tok; // points to component's functor
 796     component(std::string const & f, literal * a = NULL);
 797   };
 798   std::vector<component*> components;
 799   bool optional;
 800   bool sufficient;
 801   bool from_glob;
 802   bool well_formed; // used in derived_probe::script_location()
 803   expression* condition;
 804   void print (std::ostream& o, bool print_extras=true) const;
 805   probe_point ();
 806   probe_point(const probe_point& pp);
 807   probe_point(std::vector<component*> const & comps);
 808   std::string str(bool print_extras=true) const;
 809 };
 810
 811 std::ostream& operator << (std::ostream& o, const probe_point& k);
 812
 813
 814 struct probe
 815 {
 816   std::vector<probe_point*> locations;
 817   statement* body;
 818   struct probe* base;
 819   const token* tok;
 820   const token* systemtap_v_conditional; //checking systemtap compatibility
 821   std::vector<vardecl*> locals;
 822   std::vector<vardecl*> unused_locals;
 823   static unsigned last_probeidx;
 824   probe ();
 825   probe (probe* p, probe_point *l);
 826   void print (std::ostream& o) const;
 827   virtual void printsig (std::ostream &o) const;
 828   virtual void collect_derivation_chain (std::vector<probe*> &probes_list) const;
 829   virtual void collect_derivation_pp_chain (std::vector<probe_point*> &) const;
 830   virtual const probe_alias *get_alias () const { return 0; }
 831   virtual probe_point *get_alias_loc () const { return 0; }
 832   virtual ~probe() {}
 833   bool privileged;
 834   std::string name;
 835 };
 836
 837 struct probe_alias: public probe
 838 {
 839   probe_alias(std::vector<probe_point*> const & aliases);
 840   std::vector<probe_point*> alias_names;
 841   virtual void printsig (std::ostream &o) const;
 842   bool epilogue_style;
 843 };
 844
 845
 846 // A derived visitor instance is used to visit the entire
 847 // statement/expression tree.
 848 struct visitor
 849 {
 850   // Machinery for differentiating lvalue visits from non-lvalue.
 851   std::vector<expression *> active_lvalues;
 852   bool is_active_lvalue(expression *e);
 853   void push_active_lvalue(expression *e);
 854   void pop_active_lvalue();
 855
 856   virtual ~visitor () {}
 857   virtual void visit_block (block *s) = 0;
 858   virtual void visit_try_block (try_block *s) = 0;
 859   virtual void visit_embeddedcode (embeddedcode *s) = 0;
 860   virtual void visit_null_statement (null_statement *s) = 0;
 861   virtual void visit_expr_statement (expr_statement *s) = 0;
 862   virtual void visit_if_statement (if_statement* s) = 0;
 863   virtual void visit_for_loop (for_loop* s) = 0;
 864   virtual void visit_foreach_loop (foreach_loop* s) = 0;
 865   virtual void visit_return_statement (return_statement* s) = 0;
 866   virtual void visit_delete_statement (delete_statement* s) = 0;
 867   virtual void visit_next_statement (next_statement* s) = 0;
 868   virtual void visit_break_statement (break_statement* s) = 0;
 869   virtual void visit_continue_statement (continue_statement* s) = 0;
 870   virtual void visit_literal_string (literal_string* e) = 0;
 871   virtual void visit_literal_number (literal_number* e) = 0;
 872   virtual void visit_embedded_expr (embedded_expr* e) = 0;
 873   virtual void visit_binary_expression (binary_expression* e) = 0;
 874   virtual void visit_unary_expression (unary_expression* e) = 0;
 875   virtual void visit_pre_crement (pre_crement* e) = 0;
 876   virtual void visit_post_crement (post_crement* e) = 0;
 877   virtual void visit_logical_or_expr (logical_or_expr* e) = 0;
 878   virtual void visit_logical_and_expr (logical_and_expr* e) = 0;
 879   virtual void visit_array_in (array_in* e) = 0;
 880   virtual void visit_regex_query (regex_query* e) = 0;
 881   virtual void visit_comparison (comparison* e) = 0;
 882   virtual void visit_concatenation (concatenation* e) = 0;
 883   virtual void visit_ternary_expression (ternary_expression* e) = 0;
 884   virtual void visit_assignment (assignment* e) = 0;
 885   virtual void visit_symbol (symbol* e) = 0;
 886   virtual void visit_target_symbol (target_symbol* e) = 0;
 887   virtual void visit_arrayindex (arrayindex* e) = 0;
 888   virtual void visit_functioncall (functioncall* e) = 0;
 889   virtual void visit_print_format (print_format* e) = 0;
 890   virtual void visit_stat_op (stat_op* e) = 0;
 891   virtual void visit_hist_op (hist_op* e) = 0;
 892   virtual void visit_cast_op (cast_op* e) = 0;
 893   virtual void visit_autocast_op (autocast_op* e) = 0;
 894   virtual void visit_atvar_op (atvar_op* e) = 0;
 895   virtual void visit_defined_op (defined_op* e) = 0;
 896   virtual void visit_entry_op (entry_op* e) = 0;
 897   virtual void visit_perf_op (perf_op* e) = 0;
 898 };
 899
 900
 901 // A simple kind of visitor, which travels down to the leaves of the
 902 // statement/expression tree, up to but excluding following vardecls
 903 // and functioncalls.
 904 struct traversing_visitor: public visitor
 905 {
 906   void visit_block (block *s);
 907   void visit_try_block (try_block *s);
 908   void visit_embeddedcode (embeddedcode *s);
 909   void visit_null_statement (null_statement *s);
 910   void visit_expr_statement (expr_statement *s);
 911   void visit_if_statement (if_statement* s);
 912   void visit_for_loop (for_loop* s);
 913   void visit_foreach_loop (foreach_loop* s);
 914   void visit_return_statement (return_statement* s);
 915   void visit_delete_statement (delete_statement* s);
 916   void visit_next_statement (next_statement* s);
 917   void visit_break_statement (break_statement* s);
 918   void visit_continue_statement (continue_statement* s);
 919   void visit_literal_string (literal_string* e);
 920   void visit_literal_number (literal_number* e);
 921   void visit_embedded_expr (embedded_expr* e);
 922   void visit_binary_expression (binary_expression* e);
 923   void visit_unary_expression (unary_expression* e);
 924   void visit_pre_crement (pre_crement* e);
 925   void visit_post_crement (post_crement* e);
 926   void visit_logical_or_expr (logical_or_expr* e);
 927   void visit_logical_and_expr (logical_and_expr* e);
 928   void visit_array_in (array_in* e);
 929   void visit_regex_query (regex_query* e);
 930   void visit_comparison (comparison* e);
 931   void visit_concatenation (concatenation* e);
 932   void visit_ternary_expression (ternary_expression* e);
 933   void visit_assignment (assignment* e);
 934   void visit_symbol (symbol* e);
 935   void visit_target_symbol (target_symbol* e);
 936   void visit_arrayindex (arrayindex* e);
 937   void visit_functioncall (functioncall* e);
 938   void visit_print_format (print_format* e);
 939   void visit_stat_op (stat_op* e);
 940   void visit_hist_op (hist_op* e);
 941   void visit_cast_op (cast_op* e);
 942   void visit_autocast_op (autocast_op* e);
 943   void visit_atvar_op (atvar_op* e);
 944   void visit_defined_op (defined_op* e);
 945   void visit_entry_op (entry_op* e);
 946   void visit_perf_op (perf_op* e);
 947 };
 948
 949
 950 // A visitor that calls a generic visit_expression on every expression.
 951 struct expression_visitor: public traversing_visitor
 952 {
 953   virtual void visit_expression(expression *e) = 0;
 954
 955   void visit_literal_string (literal_string* e);
 956   void visit_literal_number (literal_number* e);
 957   void visit_embedded_expr (embedded_expr* e);
 958   void visit_binary_expression (binary_expression* e);
 959   void visit_unary_expression (unary_expression* e);
 960   void visit_pre_crement (pre_crement* e);
 961   void visit_post_crement (post_crement* e);
 962   void visit_logical_or_expr (logical_or_expr* e);
 963   void visit_logical_and_expr (logical_and_expr* e);
 964   void visit_array_in (array_in* e);
 965   void visit_regex_query (regex_query* e);
 966   void visit_comparison (comparison* e);
 967   void visit_concatenation (concatenation* e);
 968   void visit_ternary_expression (ternary_expression* e);
 969   void visit_assignment (assignment* e);
 970   void visit_symbol (symbol* e);
 971   void visit_target_symbol (target_symbol* e);
 972   void visit_arrayindex (arrayindex* e);
 973   void visit_functioncall (functioncall* e);
 974   void visit_print_format (print_format* e);
 975   void visit_stat_op (stat_op* e);
 976   void visit_hist_op (hist_op* e);
 977   void visit_cast_op (cast_op* e);
 978   void visit_autocast_op (autocast_op* e);
 979   void visit_atvar_op (atvar_op* e);
 980   void visit_defined_op (defined_op* e);
 981   void visit_entry_op (entry_op* e);
 982   void visit_perf_op (perf_op* e);
 983 };
 984
 985
 986 // A kind of traversing visitor, which also follows function calls.
 987 // It uses an internal set object to prevent infinite recursion.
 988 struct functioncall_traversing_visitor: public traversing_visitor
 989 {
 990   std::set<functiondecl*> seen;
 991   std::set<functiondecl*> nested;
 992   functiondecl* current_function;
 993   functioncall_traversing_visitor(): current_function(0) {}
 994   void visit_functioncall (functioncall* e);
 995   virtual void note_recursive_functioncall (functioncall* e);
 996 };
 997
 998
 999 // A kind of traversing visitor, which also follows function calls,
1000 // and stores the vardecl* referent of each variable read and/or
1001 // written and other such sundry side-effect data.  It's used by
1002 // the elaboration-time optimizer pass.
1003 struct varuse_collecting_visitor: public functioncall_traversing_visitor
1004 {
1005   systemtap_session& session;
1006   std::set<vardecl*> read;
1007   std::set<vardecl*> written;
1008   std::set<vardecl*> used;
1009   bool embedded_seen;
1010   bool current_lvalue_read;
1011   expression* current_lvalue;
1012   expression* current_lrvalue;
1013   varuse_collecting_visitor(systemtap_session& s):
1014     session (s),
1015     embedded_seen (false),
1016     current_lvalue_read (false),
1017     current_lvalue(0),
1018     current_lrvalue(0) {}
1019   void visit_embeddedcode (embeddedcode *s);
1020   void visit_embedded_expr (embedded_expr *e);
1021   void visit_try_block (try_block *s);
1022   void visit_delete_statement (delete_statement *s);
1023   void visit_print_format (print_format *e);
1024   void visit_assignment (assignment *e);
1025   void visit_arrayindex (arrayindex *e);
1026   void visit_target_symbol (target_symbol *e);
1027   void visit_symbol (symbol *e);
1028   void visit_pre_crement (pre_crement *e);
1029   void visit_post_crement (post_crement *e);
1030   void visit_foreach_loop (foreach_loop *s);
1031   void visit_cast_op (cast_op* e);
1032   void visit_autocast_op (autocast_op* e);
1033   void visit_atvar_op (atvar_op *e);
1034   void visit_defined_op (defined_op* e);
1035   void visit_entry_op (entry_op* e);
1036   void visit_perf_op (perf_op* e);
1037   bool side_effect_free ();
1038   bool side_effect_free_wrt (const std::set<vardecl*>& vars);
1039 };
1040
1041
1042
1043 // A kind of visitor that throws an semantic_error exception
1044 // whenever a non-overridden method is called.
1045 struct throwing_visitor: public visitor
1046 {
1047   std::string msg;
1048   throwing_visitor (const std::string& m);
1049   throwing_visitor ();
1050
1051   virtual void throwone (const token* t);
1052
1053   void visit_block (block *s);
1054   void visit_try_block (try_block *s);
1055   void visit_embeddedcode (embeddedcode *s);
1056   void visit_null_statement (null_statement *s);
1057   void visit_expr_statement (expr_statement *s);
1058   void visit_if_statement (if_statement* s);
1059   void visit_for_loop (for_loop* s);
1060   void visit_foreach_loop (foreach_loop* s);
1061   void visit_return_statement (return_statement* s);
1062   void visit_delete_statement (delete_statement* s);
1063   void visit_next_statement (next_statement* s);
1064   void visit_break_statement (break_statement* s);
1065   void visit_continue_statement (continue_statement* s);
1066   void visit_literal_string (literal_string* e);
1067   void visit_literal_number (literal_number* e);
1068   void visit_embedded_expr (embedded_expr* e);
1069   void visit_binary_expression (binary_expression* e);
1070   void visit_unary_expression (unary_expression* e);
1071   void visit_pre_crement (pre_crement* e);
1072   void visit_post_crement (post_crement* e);
1073   void visit_logical_or_expr (logical_or_expr* e);
1074   void visit_logical_and_expr (logical_and_expr* e);
1075   void visit_array_in (array_in* e);
1076   void visit_regex_query (regex_query* e);
1077   void visit_comparison (comparison* e);
1078   void visit_concatenation (concatenation* e);
1079   void visit_ternary_expression (ternary_expression* e);
1080   void visit_assignment (assignment* e);
1081   void visit_symbol (symbol* e);
1082   void visit_target_symbol (target_symbol* e);
1083   void visit_arrayindex (arrayindex* e);
1084   void visit_functioncall (functioncall* e);
1085   void visit_print_format (print_format* e);
1086   void visit_stat_op (stat_op* e);
1087   void visit_hist_op (hist_op* e);
1088   void visit_cast_op (cast_op* e);
1089   void visit_autocast_op (autocast_op* e);
1090   void visit_atvar_op (atvar_op* e);
1091   void visit_defined_op (defined_op* e);
1092   void visit_entry_op (entry_op* e);
1093   void visit_perf_op (perf_op* e);
1094 };
1095
1096 // A visitor similar to a traversing_visitor, but with the ability to rewrite
1097 // parts of the tree through require/provide.
1098
1099 struct update_visitor: public visitor
1100 {
1101   template <typename T> T* require (T* src, bool clearok=false)
1102   {
1103     T* dst = NULL;
1104     if (src != NULL)
1105       {
1106         src->visit(this);
1107         if (values.empty())
1108           throw std::runtime_error(_("update_visitor wasn't provided a value"));
1109         visitable *v = values.top();
1110         values.pop();
1111         if (v == NULL && !clearok)
1112           throw std::runtime_error(_("update_visitor was provided a NULL value"));
1113         dst = dynamic_cast<T*>(v);
1114         if (v != NULL && dst == NULL)
1115           throw std::runtime_error(_F("update_visitor can't set type \"%s\" with a \"%s\"",
1116                                       typeid(T).name(), typeid(*v).name()));
1117       }
1118     return dst;
1119   }
1120
1121   template <typename T> void provide (T* src)
1122   {
1123     values.push(src);
1124   }
1125
1126   template <typename T> void replace (T*& src, bool clearok=false)
1127   {
1128     src = require(src, clearok);
1129   }
1130
1131   virtual ~update_visitor() { assert(values.empty()); }
1132
1133   virtual void visit_block (block *s);
1134   virtual void visit_try_block (try_block *s);
1135   virtual void visit_embeddedcode (embeddedcode *s);
1136   virtual void visit_null_statement (null_statement *s);
1137   virtual void visit_expr_statement (expr_statement *s);
1138   virtual void visit_if_statement (if_statement* s);
1139   virtual void visit_for_loop (for_loop* s);
1140   virtual void visit_foreach_loop (foreach_loop* s);
1141   virtual void visit_return_statement (return_statement* s);
1142   virtual void visit_delete_statement (delete_statement* s);
1143   virtual void visit_next_statement (next_statement* s);
1144   virtual void visit_break_statement (break_statement* s);
1145   virtual void visit_continue_statement (continue_statement* s);
1146   virtual void visit_literal_string (literal_string* e);
1147   virtual void visit_literal_number (literal_number* e);
1148   virtual void visit_embedded_expr (embedded_expr* e);
1149   virtual void visit_binary_expression (binary_expression* e);
1150   virtual void visit_unary_expression (unary_expression* e);
1151   virtual void visit_pre_crement (pre_crement* e);
1152   virtual void visit_post_crement (post_crement* e);
1153   virtual void visit_logical_or_expr (logical_or_expr* e);
1154   virtual void visit_logical_and_expr (logical_and_expr* e);
1155   virtual void visit_array_in (array_in* e);
1156   virtual void visit_regex_query (regex_query* e);
1157   virtual void visit_comparison (comparison* e);
1158   virtual void visit_concatenation (concatenation* e);
1159   virtual void visit_ternary_expression (ternary_expression* e);
1160   virtual void visit_assignment (assignment* e);
1161   virtual void visit_symbol (symbol* e);
1162   virtual void visit_target_symbol (target_symbol* e);
1163   virtual void visit_arrayindex (arrayindex* e);
1164   virtual void visit_functioncall (functioncall* e);
1165   virtual void visit_print_format (print_format* e);
1166   virtual void visit_stat_op (stat_op* e);
1167   virtual void visit_hist_op (hist_op* e);
1168   virtual void visit_cast_op (cast_op* e);
1169   virtual void visit_autocast_op (autocast_op* e);
1170   virtual void visit_atvar_op (atvar_op* e);
1171   virtual void visit_defined_op (defined_op* e);
1172   virtual void visit_entry_op (entry_op* e);
1173   virtual void visit_perf_op (perf_op* e);
1174
1175 private:
1176   std::stack<visitable *> values;
1177 };
1178
1179 // A visitor which performs a deep copy of the root node it's applied
1180 // to. NB: It does not copy any of the variable or function
1181 // declarations; those fields are set to NULL, assuming you want to
1182 // re-infer the declarations in a new context (the one you're copying
1183 // to).
1184
1185 struct deep_copy_visitor: public update_visitor
1186 {
1187   template <typename T> static T* deep_copy (T* e)
1188   {
1189     deep_copy_visitor v;
1190     return v.require (e);
1191   }
1192
1193   virtual void visit_block (block *s);
1194   virtual void visit_try_block (try_block *s);
1195   virtual void visit_embeddedcode (embeddedcode *s);
1196   virtual void visit_null_statement (null_statement *s);
1197   virtual void visit_expr_statement (expr_statement *s);
1198   virtual void visit_if_statement (if_statement* s);
1199   virtual void visit_for_loop (for_loop* s);
1200   virtual void visit_foreach_loop (foreach_loop* s);
1201   virtual void visit_return_statement (return_statement* s);
1202   virtual void visit_delete_statement (delete_statement* s);
1203   virtual void visit_next_statement (next_statement* s);
1204   virtual void visit_break_statement (break_statement* s);
1205   virtual void visit_continue_statement (continue_statement* s);
1206   virtual void visit_literal_string (literal_string* e);
1207   virtual void visit_literal_number (literal_number* e);
1208   virtual void visit_embedded_expr (embedded_expr* e);
1209   virtual void visit_binary_expression (binary_expression* e);
1210   virtual void visit_unary_expression (unary_expression* e);
1211   virtual void visit_pre_crement (pre_crement* e);
1212   virtual void visit_post_crement (post_crement* e);
1213   virtual void visit_logical_or_expr (logical_or_expr* e);
1214   virtual void visit_logical_and_expr (logical_and_expr* e);
1215   virtual void visit_array_in (array_in* e);
1216   virtual void visit_regex_query (regex_query* e);
1217   virtual void visit_comparison (comparison* e);
1218   virtual void visit_concatenation (concatenation* e);
1219   virtual void visit_ternary_expression (ternary_expression* e);
1220   virtual void visit_assignment (assignment* e);
1221   virtual void visit_symbol (symbol* e);
1222   virtual void visit_target_symbol (target_symbol* e);
1223   virtual void visit_arrayindex (arrayindex* e);
1224   virtual void visit_functioncall (functioncall* e);
1225   virtual void visit_print_format (print_format* e);
1226   virtual void visit_stat_op (stat_op* e);
1227   virtual void visit_hist_op (hist_op* e);
1228   virtual void visit_cast_op (cast_op* e);
1229   virtual void visit_autocast_op (autocast_op* e);
1230   virtual void visit_atvar_op (atvar_op* e);
1231   virtual void visit_defined_op (defined_op* e);
1232   virtual void visit_entry_op (entry_op* e);
1233   virtual void visit_perf_op (perf_op* e);
1234 };
1235
1236 #endif // STAPTREE_H
1237
1238 /* vim: set sw=2 ts=8 cino=>4,n-2,{2,^-2,t0,(0,u0,w1,M1 : */