staptree.h

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