staptree.h

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