staptree.cxx

   1 // parse tree functions
   2 // Copyright (C) 2005-2009 Red Hat Inc.
   3 //
   4 // This file is part of systemtap, and is free software.  You can
   5 // redistribute it and/or modify it under the terms of the GNU General
   6 // Public License (GPL); either version 2, or (at your option) any
   7 // later version.
   8
   9 #include "config.h"
  10 #include "staptree.h"
  11 #include "parse.h"
  12 #include "util.h"
  13 #include "session.h"
  14
  15 #include <iostream>
  16 #include <typeinfo>
  17 #include <sstream>
  18 #include <cassert>
  19 #include <cstring>
  20 #include <vector>
  21 #include <algorithm>
  22 #include <cstring>
  23
  24 using namespace std;
  25
  26
  27
  28 expression::expression ():
  29   type (pe_unknown), tok (0)
  30 {
  31 }
  32
  33
  34 expression::~expression ()
  35 {
  36 }
  37
  38
  39 statement::statement ():
  40   tok (0)
  41 {
  42 }
  43
  44
  45 statement::~statement ()
  46 {
  47 }
  48
  49
  50 symbol::symbol ():
  51   referent (0)
  52 {
  53 }
  54
  55
  56 arrayindex::arrayindex ():
  57   base (0)
  58 {
  59 }
  60
  61
  62 functioncall::functioncall ():
  63   referent (0)
  64 {
  65 }
  66
  67
  68 symboldecl::symboldecl ():
  69   tok (0),
  70   type (pe_unknown)
  71 {
  72 }
  73
  74
  75 symboldecl::~symboldecl ()
  76 {
  77 }
  78
  79 probe_point::probe_point (std::vector<component*> const & comps,
  80                           const token * t):
  81   components(comps), tok(t), optional (false), sufficient (false),
  82   condition (0)
  83 {
  84 }
  85
  86 // NB: shallow-copy of compoonents & condition!
  87 probe_point::probe_point (const probe_point& pp):
  88   components(pp.components), tok(pp.tok), optional (pp.optional), sufficient (pp.sufficient),
  89   condition (pp.condition)
  90 {
  91 }
  92
  93
  94 probe_point::probe_point ():
  95   tok (0), optional (false), sufficient (false), condition (0)
  96 {
  97 }
  98
  99
 100 probe::probe ():
 101   body (0), tok (0)
 102 {
 103   static unsigned last_probeidx = 0;
 104   this->name = string ("probe_") + lex_cast(last_probeidx ++);
 105 }
 106
 107
 108 probe_point::component::component ():
 109   arg (0)
 110 {
 111 }
 112
 113
 114 probe_point::component::component (std::string const & f, literal * a):
 115   functor(f), arg(a)
 116 {
 117 }
 118
 119
 120 vardecl::vardecl ():
 121   arity (-1), maxsize(0), init(NULL)
 122 {
 123 }
 124
 125
 126 void
 127 vardecl::set_arity (int a)
 128 {
 129   if (a < 0)
 130     return;
 131
 132   if ((arity != a && arity >= 0) || (a == 0 && maxsize > 0))
 133     throw semantic_error ("inconsistent arity", tok);
 134
 135   if (arity != a)
 136     {
 137       arity = a;
 138       index_types.resize (arity);
 139       for (int i=0; i<arity; i++)
 140         index_types[i] = pe_unknown;
 141     }
 142 }
 143
 144 bool
 145 vardecl::compatible_arity (int a)
 146 {
 147   if (a == 0 && maxsize > 0)
 148     return false;
 149   if (arity == -1 || a == -1)
 150     return true;
 151   return arity == a;
 152 }
 153
 154
 155 functiondecl::functiondecl ():
 156   body (0)
 157 {
 158 }
 159
 160
 161 literal_number::literal_number (int64_t v)
 162 {
 163   value = v;
 164   type = pe_long;
 165 }
 166
 167
 168 literal_string::literal_string (const string& v)
 169 {
 170   value = v;
 171   type = pe_string;
 172 }
 173
 174
 175 ostream&
 176 operator << (ostream& o, const exp_type& e)
 177 {
 178   switch (e)
 179     {
 180     case pe_unknown: o << "unknown"; break;
 181     case pe_long: o << "long"; break;
 182     case pe_string: o << "string"; break;
 183     case pe_stats: o << "stats"; break;
 184     default: o << "???"; break;
 185     }
 186   return o;
 187 }
 188
 189
 190 void
 191 target_symbol::assert_no_components(const std::string& tapset)
 192 {
 193   if (components.empty())
 194     return;
 195
 196   switch (components[0].type)
 197     {
 198     case target_symbol::comp_literal_array_index:
 199     case target_symbol::comp_expression_array_index:
 200       throw semantic_error(tapset + " variable '" + base_name +
 201                            "' may not be used as array",
 202                            components[0].tok);
 203     case target_symbol::comp_struct_member:
 204       throw semantic_error(tapset + " variable '" + base_name +
 205                            "' may not be used as a structure",
 206                            components[0].tok);
 207     default:
 208       throw semantic_error ("invalid use of " + tapset +
 209                             " variable '" + base_name + "'",
 210                             components[0].tok);
 211     }
 212 }
 213
 214
 215 // ------------------------------------------------------------------------
 216 // parse tree printing
 217
 218 ostream& operator << (ostream& o, const expression& k)
 219 {
 220   k.print (o);
 221   return o;
 222 }
 223
 224
 225 void literal_string::print (ostream& o) const
 226 {
 227   o << '"';
 228   for (unsigned i=0; i<value.size(); i++)
 229     if (value[i] == '"') // or other escapeworthy characters?
 230       o << '\\' << '"';
 231     else
 232       o << value[i];
 233   o << '"';
 234 }
 235
 236
 237 void literal_number::print (ostream& o) const
 238 {
 239   o << value;
 240 }
 241
 242
 243 void binary_expression::print (ostream& o) const
 244 {
 245   o << "(" << *left << ") "
 246     << op
 247     << " (" << *right << ")";
 248 }
 249
 250
 251 void unary_expression::print (ostream& o) const
 252 {
 253   o << op << '(' << *operand << ")";
 254 }
 255
 256 void array_in::print (ostream& o) const
 257 {
 258   o << "[";
 259   for (unsigned i=0; i<operand->indexes.size(); i++)
 260     {
 261       if (i > 0) o << ", ";
 262       operand->indexes[i]->print (o);
 263     }
 264   o << "] in ";
 265   operand->base->print_indexable (o);
 266 }
 267
 268 void post_crement::print (ostream& o) const
 269 {
 270   o << '(' << *operand << ")" << op;
 271 }
 272
 273
 274 void ternary_expression::print (ostream& o) const
 275 {
 276   o << "(" << *cond << ")?("
 277     << *truevalue << "):("
 278     << *falsevalue << ")";
 279 }
 280
 281
 282 void symbol::print (ostream& o) const
 283 {
 284   o << name;
 285 }
 286
 287
 288 void target_symbol::component::print (ostream& o) const
 289 {
 290   switch (type)
 291     {
 292     case comp_struct_member:
 293       o << "->" << member;
 294       break;
 295     case comp_literal_array_index:
 296       o << '[' << num_index << ']';
 297       break;
 298     case comp_expression_array_index:
 299       o << '[' << *expr_index << ']';
 300       break;
 301     }
 302 }
 303
 304
 305 std::ostream& operator << (std::ostream& o, const target_symbol::component& c)
 306 {
 307   c.print (o);
 308   return o;
 309 }
 310
 311
 312 void target_symbol::print (ostream& o) const
 313 {
 314   if (addressof)
 315     o << "&";
 316   o << base_name;
 317   for (unsigned i = 0; i < components.size(); ++i)
 318     o << components[i];
 319 }
 320
 321
 322 void cast_op::print (ostream& o) const
 323 {
 324   if (addressof)
 325     o << "&";
 326   o << base_name << '(' << *operand;
 327   o << ", " << lex_cast_qstring (type);
 328   if (module.length() > 0)
 329     o << ", " << lex_cast_qstring (module);
 330   o << ')';
 331   for (unsigned i = 0; i < components.size(); ++i)
 332     o << components[i];
 333 }
 334
 335
 336 void vardecl::print (ostream& o) const
 337 {
 338   o << name;
 339   if (maxsize > 0)
 340     o << "[" << maxsize << "]";
 341   if (arity > 0 || index_types.size() > 0)
 342     o << "[...]";
 343   if (init)
 344     {
 345       o << " = ";
 346       init->print(o);
 347     }
 348 }
 349
 350
 351 void vardecl::printsig (ostream& o) const
 352 {
 353   o << name;
 354   if (maxsize > 0)
 355     o << "[" << maxsize << "]";
 356   o << ":" << type;
 357   if (index_types.size() > 0)
 358     {
 359       o << " [";
 360       for (unsigned i=0; i<index_types.size(); i++)
 361         o << (i>0 ? ", " : "") << index_types[i];
 362       o << "]";
 363     }
 364 }
 365
 366
 367 void functiondecl::print (ostream& o) const
 368 {
 369   o << "function " << name << " (";
 370   for (unsigned i=0; i<formal_args.size(); i++)
 371     o << (i>0 ? ", " : "") << *formal_args[i];
 372   o << ")" << endl;
 373   body->print(o);
 374 }
 375
 376
 377 void functiondecl::printsig (ostream& o) const
 378 {
 379   o << name << ":" << type << " (";
 380   for (unsigned i=0; i<formal_args.size(); i++)
 381     o << (i>0 ? ", " : "")
 382       << *formal_args[i]
 383       << ":"
 384       << formal_args[i]->type;
 385   o << ")";
 386 }
 387
 388
 389 void arrayindex::print (ostream& o) const
 390 {
 391   base->print_indexable (o);
 392   o << "[";
 393   for (unsigned i=0; i<indexes.size(); i++)
 394     o << (i>0 ? ", " : "") << *indexes[i];
 395   o << "]";
 396 }
 397
 398
 399 void functioncall::print (ostream& o) const
 400 {
 401   o << function << "(";
 402   for (unsigned i=0; i<args.size(); i++)
 403     o << (i>0 ? ", " : "") << *args[i];
 404   o << ")";
 405 }
 406
 407
 408 bool
 409 print_format::parse_print(const std::string &name,
 410   bool &stream, bool &format, bool &delim, bool &newline, bool &_char)
 411 {
 412   const char *n = name.c_str();
 413
 414   stream = true;
 415   format = delim = newline = _char = false;
 416
 417   if (strcmp(n, "print_char") == 0)
 418     {
 419       _char = true;
 420       return true;
 421     }
 422
 423   if (*n == 's')
 424     {
 425       stream = false;
 426       ++n;
 427     }
 428
 429   if (0 != strncmp(n, "print", 5))
 430     return false;
 431   n += 5;
 432
 433   if (*n == 'f')
 434     {
 435       format = true;
 436       ++n;
 437     }
 438   else
 439     {
 440       if (*n == 'd')
 441         {
 442           delim = true;
 443           ++n;
 444         }
 445
 446       if (*n == 'l' && *(n+1) == 'n')
 447         {
 448           newline = true;
 449           n += 2;
 450         }
 451     }
 452
 453   return (*n == '\0');
 454 }
 455
 456
 457 string
 458 print_format::components_to_string(vector<format_component> const & components)
 459 {
 460   ostringstream oss;
 461
 462   for (vector<format_component>::const_iterator i = components.begin();
 463        i != components.end(); ++i)
 464     {
 465
 466       assert (i->type != conv_unspecified);
 467
 468       if (i->type == conv_literal)
 469         {
 470           assert(!i->literal_string.empty());
 471           for (string::const_iterator j = i->literal_string.begin();
 472                j != i->literal_string.end(); ++j)
 473             {
 474               // See also: c_unparser::visit_literal_string and lex_cast_qstring
 475               if (*j == '%')
 476                 oss << '%';
 477               else if(*j == '"')
 478                 oss << '\\';
 479               oss << *j;
 480             }
 481         }
 482       else
 483         {
 484           oss << '%';
 485
 486           if (i->flags & static_cast<unsigned long>(fmt_flag_zeropad))
 487             oss << '0';
 488
 489           if (i->flags & static_cast<unsigned long>(fmt_flag_plus))
 490             oss << '+';
 491
 492           if (i->flags & static_cast<unsigned long>(fmt_flag_space))
 493             oss << ' ';
 494
 495           if (i->flags & static_cast<unsigned long>(fmt_flag_left))
 496             oss << '-';
 497
 498           if (i->flags & static_cast<unsigned long>(fmt_flag_special))
 499             oss << '#';
 500
 501           if (i->widthtype == width_dynamic)
 502             oss << '*';
 503           else if (i->widthtype != width_unspecified && i->width > 0)
 504             oss << i->width;
 505
 506           if (i->prectype == prec_dynamic)
 507             oss << ".*";
 508           else if (i->prectype != prec_unspecified && i->precision > 0)
 509             oss << '.' << i->precision;
 510
 511           switch (i->type)
 512             {
 513             case conv_binary:
 514               oss << "b";
 515               break;
 516
 517             case conv_char:
 518               oss << "llc";
 519               break;
 520
 521             case conv_signed_decimal:
 522               oss << "lld";
 523               break;
 524
 525             case conv_unsigned_decimal:
 526               oss << "llu";
 527               break;
 528
 529             case conv_unsigned_octal:
 530               oss << "llo";
 531               break;
 532
 533             case conv_unsigned_ptr:
 534               oss << "p";
 535               break;
 536
 537             case conv_unsigned_uppercase_hex:
 538               oss << "llX";
 539               break;
 540
 541             case conv_unsigned_lowercase_hex:
 542               oss << "llx";
 543               break;
 544
 545             case conv_string:
 546               oss << 's';
 547               break;
 548
 549             case conv_memory:
 550               oss << 'm';
 551               break;
 552
 553             case conv_memory_hex:
 554               oss << 'M';
 555               break;
 556
 557             default:
 558               break;
 559             }
 560         }
 561     }
 562   return oss.str ();
 563 }
 564
 565 vector<print_format::format_component>
 566 print_format::string_to_components(string const & str)
 567 {
 568   format_component curr;
 569   vector<format_component> res;
 570
 571   curr.clear();
 572
 573   string::const_iterator i = str.begin();
 574
 575   while (i != str.end())
 576     {
 577       if (*i != '%')
 578         {
 579           assert (curr.type == conv_unspecified || curr.type == conv_literal);
 580           curr.type = conv_literal;
 581           curr.literal_string += *i;
 582           ++i;
 583           continue;
 584         }
 585       else if (i+1 == str.end() || *(i+1) == '%')
 586         {
 587           assert(*i == '%');
 588           // *i == '%' and *(i+1) == '%'; append only one '%' to the literal string
 589           assert (curr.type == conv_unspecified || curr.type == conv_literal);
 590           curr.type = conv_literal;
 591           curr.literal_string += '%';
 592           i += 2;
 593           continue;
 594         }
 595       else
 596         {
 597           assert(*i == '%');
 598           if (curr.type != conv_unspecified)
 599             {
 600               // Flush any component we were previously accumulating
 601               assert (curr.type == conv_literal);
 602               res.push_back(curr);
 603               curr.clear();
 604             }
 605         }
 606       ++i;
 607
 608       if (i == str.end())
 609         break;
 610
 611       // Now we are definitely parsing a conversion.
 612       // Begin by parsing flags (which are optional).
 613
 614       switch (*i)
 615         {
 616         case '0':
 617           curr.flags |= static_cast<unsigned long>(fmt_flag_zeropad);
 618           ++i;
 619           break;
 620
 621         case '+':
 622           curr.flags |= static_cast<unsigned long>(fmt_flag_plus);
 623           ++i;
 624           break;
 625
 626         case '-':
 627           curr.flags |= static_cast<unsigned long>(fmt_flag_left);
 628           ++i;
 629           break;
 630
 631         case ' ':
 632           curr.flags |= static_cast<unsigned long>(fmt_flag_space);
 633           ++i;
 634           break;
 635
 636         case '#':
 637           curr.flags |= static_cast<unsigned long>(fmt_flag_special);
 638           ++i;
 639           break;
 640
 641         default:
 642           break;
 643         }
 644
 645       if (i == str.end())
 646         break;
 647
 648       // Parse optional width
 649       if (*i == '*')
 650         {
 651           curr.widthtype = width_dynamic;
 652           ++i;
 653         }
 654       else if (isdigit(*i))
 655         {
 656           curr.widthtype = width_static;
 657           curr.width = 0;
 658           do
 659             {
 660               curr.width *= 10;
 661               curr.width += (*i - '0');
 662               ++i;
 663             }
 664           while (i != str.end() && isdigit(*i));
 665         }
 666
 667       if (i == str.end())
 668         break;
 669
 670       // Parse optional precision
 671       if (*i == '.')
 672         {
 673           ++i;
 674           if (i == str.end())
 675             break;
 676           if (*i == '*')
 677             {
 678               curr.prectype = prec_dynamic;
 679               ++i;
 680             }
 681           else if (isdigit(*i))
 682             {
 683               curr.prectype = prec_static;
 684               curr.precision = 0;
 685               do
 686                 {
 687                   curr.precision *= 10;
 688                   curr.precision += (*i - '0');
 689                   ++i;
 690                 }
 691               while (i != str.end() && isdigit(*i));
 692             }
 693         }
 694
 695       if (i == str.end())
 696         break;
 697
 698       // Parse the actual conversion specifier (bcsmdioupxXn)
 699       switch (*i)
 700         {
 701           // Valid conversion types
 702         case 'b':
 703           curr.type = conv_binary;
 704           break;
 705
 706         case 'c':
 707           curr.type = conv_char;
 708           break;
 709
 710         case 's':
 711           curr.type = conv_string;
 712           break;
 713
 714         case 'm':
 715           curr.type = conv_memory;
 716           break;
 717
 718         case 'M':
 719           curr.type = conv_memory_hex;
 720           break;
 721
 722         case 'd':
 723         case 'i':
 724           curr.type = conv_signed_decimal;
 725           break;
 726
 727         case 'o':
 728           curr.type = conv_unsigned_octal;
 729           break;
 730
 731         case 'u':
 732           curr.type = conv_unsigned_decimal;
 733           break;
 734
 735         case 'p':
 736           curr.type = conv_unsigned_ptr;
 737           break;
 738
 739         case 'X':
 740           curr.type = conv_unsigned_uppercase_hex;
 741           break;
 742
 743         case 'x':
 744           curr.type = conv_unsigned_lowercase_hex;
 745           break;
 746
 747         default:
 748           break;
 749         }
 750
 751       if (curr.type == conv_unspecified)
 752         throw parse_error("invalid or missing conversion specifier");
 753
 754       ++i;
 755       res.push_back(curr);
 756       curr.clear();
 757     }
 758
 759   // If there's a remaining partly-composed conversion, fail.
 760   if (!curr.is_empty())
 761     {
 762       if (curr.type == conv_literal)
 763         res.push_back(curr);
 764       else
 765         throw parse_error("trailing incomplete print format conversion");
 766     }
 767
 768   return res;
 769 }
 770
 771
 772 void print_format::print (ostream& o) const
 773 {
 774   o << tok->content << "(";
 775   if (print_with_format)
 776     o << lex_cast_qstring (raw_components);
 777   if (print_with_delim)
 778     o << lex_cast_qstring (delimiter.literal_string);
 779   if (hist)
 780     hist->print(o);
 781   for (vector<expression*>::const_iterator i = args.begin();
 782        i != args.end(); ++i)
 783     {
 784       if (i != args.begin() || print_with_format || print_with_delim)
 785         o << ", ";
 786       (*i)->print(o);
 787     }
 788   o << ")";
 789 }
 790
 791 void stat_op::print (ostream& o) const
 792 {
 793   o << '@';
 794   switch (ctype)
 795     {
 796     case sc_average:
 797       o << "avg(";
 798       break;
 799
 800     case sc_count:
 801       o << "count(";
 802       break;
 803
 804     case sc_sum:
 805       o << "sum(";
 806       break;
 807
 808     case sc_min:
 809       o << "min(";
 810       break;
 811
 812     case sc_max:
 813       o << "max(";
 814       break;
 815     }
 816   stat->print(o);
 817   o << ")";
 818 }
 819
 820 void
 821 hist_op::print (ostream& o) const
 822 {
 823   o << '@';
 824   switch (htype)
 825     {
 826     case hist_linear:
 827       assert(params.size() == 3);
 828       o << "hist_linear(";
 829       stat->print(o);
 830       for (size_t i = 0; i < params.size(); ++i)
 831         {
 832           o << ", " << params[i];
 833         }
 834       o << ")";
 835       break;
 836
 837     case hist_log:
 838       assert(params.size() == 0);
 839       o << "hist_log(";
 840       stat->print(o);
 841       o << ")";
 842       break;
 843     }
 844 }
 845
 846 ostream& operator << (ostream& o, const statement& k)
 847 {
 848   k.print (o);
 849   return o;
 850 }
 851
 852
 853 void embeddedcode::print (ostream &o) const
 854 {
 855   o << "%{";
 856   o << code;
 857   o << "%}";
 858 }
 859
 860 void block::print (ostream& o) const
 861 {
 862   o << "{" << endl;
 863   for (unsigned i=0; i<statements.size(); i++)
 864     o << *statements [i] << endl;
 865   o << "}";
 866 }
 867
 868 block::block (statement* car, statement* cdr)
 869 {
 870   statements.push_back(car);
 871   statements.push_back(cdr);
 872   this->tok = car->tok;
 873 }
 874
 875
 876
 877 void for_loop::print (ostream& o) const
 878 {
 879   o << "for (";
 880   if (init) init->print (o);
 881   o << "; ";
 882   cond->print (o);
 883   o << "; ";
 884   if (incr) incr->print (o);
 885   o << ") ";
 886   block->print (o);
 887 }
 888
 889
 890 void foreach_loop::print (ostream& o) const
 891 {
 892   o << "foreach ([";
 893   for (unsigned i=0; i<indexes.size(); i++)
 894     {
 895       if (i > 0) o << ", ";
 896       indexes[i]->print (o);
 897       if (sort_direction != 0 && sort_column == i+1)
 898         o << (sort_direction > 0 ? "+" : "-");
 899     }
 900   o << "] in ";
 901   base->print_indexable (o);
 902   if (sort_direction != 0 && sort_column == 0)
 903     o << (sort_direction > 0 ? "+" : "-");
 904   if (limit)
 905     {
 906       o << " limit ";
 907       limit->print (o);
 908     }
 909   o << ") ";
 910   block->print (o);
 911 }
 912
 913
 914 void null_statement::print (ostream& o) const
 915 {
 916   o << ";";
 917 }
 918
 919
 920 void expr_statement::print (ostream& o) const
 921 {
 922   o << *value;
 923 }
 924
 925
 926 void return_statement::print (ostream& o) const
 927 {
 928   o << "return " << *value;
 929 }
 930
 931
 932 void delete_statement::print (ostream& o) const
 933 {
 934   o << "delete " << *value;
 935 }
 936
 937 void next_statement::print (ostream& o) const
 938 {
 939   o << "next";
 940 }
 941
 942 void break_statement::print (ostream& o) const
 943 {
 944   o << "break";
 945 }
 946
 947 void continue_statement::print (ostream& o) const
 948 {
 949   o << "continue";
 950 }
 951
 952 void if_statement::print (ostream& o) const
 953 {
 954   o << "if (" << *condition << ") "
 955     << *thenblock << endl;
 956   if (elseblock)
 957     o << "else " << *elseblock << endl;
 958 }
 959
 960
 961 void stapfile::print (ostream& o) const
 962 {
 963   o << "# file " << name << endl;
 964
 965   for (unsigned i=0; i<embeds.size(); i++)
 966     embeds[i]->print (o);
 967
 968   for (unsigned i=0; i<globals.size(); i++)
 969     {
 970       o << "global ";
 971       globals[i]->print (o);
 972       o << endl;
 973     }
 974
 975   for (unsigned i=0; i<aliases.size(); i++)
 976     {
 977       aliases[i]->print (o);
 978       o << endl;
 979     }
 980
 981   for (unsigned i=0; i<probes.size(); i++)
 982     {
 983       probes[i]->print (o);
 984       o << endl;
 985     }
 986
 987   for (unsigned j = 0; j < functions.size(); j++)
 988     {
 989       functions[j]->print (o);
 990       o << endl;
 991     }
 992 }
 993
 994
 995 void probe::print (ostream& o) const
 996 {
 997   o << "probe ";
 998   printsig (o);
 999   o << *body;
1000 }
1001
1002
1003 void probe::printsig (ostream& o) const
1004 {
1005   const probe_alias *alias = get_alias ();
1006   if (alias)
1007     {
1008       alias->printsig (o);
1009       return;
1010     }
1011
1012   for (unsigned i=0; i<locations.size(); i++)
1013     {
1014       if (i > 0) o << ",";
1015       locations[i]->print (o);
1016     }
1017 }
1018
1019
1020 void
1021 probe::collect_derivation_chain (std::vector<probe*> &probes_list)
1022 {
1023   probes_list.push_back(this);
1024 }
1025
1026
1027 void probe_point::print (ostream& o) const
1028 {
1029   for (unsigned i=0; i<components.size(); i++)
1030     {
1031       if (i>0) o << ".";
1032       probe_point::component* c = components[i];
1033       o << c->functor;
1034       if (c->arg)
1035         o << "(" << *c->arg << ")";
1036     }
1037   if (sufficient)
1038     o << "!";
1039   else if (optional) // sufficient implies optional
1040     o << "?";
1041   if (condition)
1042     o<< " if (" << *condition << ")";
1043 }
1044
1045 string probe_point::str ()
1046 {
1047   ostringstream o;
1048   for (unsigned i=0; i<components.size(); i++)
1049     {
1050       if (i>0) o << ".";
1051       probe_point::component* c = components[i];
1052       o << c->functor;
1053       if (c->arg)
1054         o << "(" << *c->arg << ")";
1055     }
1056   if (sufficient)
1057     o << "!";
1058   else if (optional) // sufficient implies optional
1059     o << "?";
1060   if (condition)
1061     o<< " if (" << *condition << ")";
1062   return o.str();
1063 }
1064
1065
1066 probe_alias::probe_alias(std::vector<probe_point*> const & aliases):
1067   probe (), alias_names (aliases)
1068 {
1069 }
1070
1071 void probe_alias::printsig (ostream& o) const
1072 {
1073   for (unsigned i=0; i<alias_names.size(); i++)
1074     {
1075       o << (i>0 ? " = " : "");
1076       alias_names[i]->print (o);
1077     }
1078   o << " = ";
1079   for (unsigned i=0; i<locations.size(); i++)
1080     {
1081       if (i > 0) o << ", ";
1082       locations[i]->print (o);
1083     }
1084 }
1085
1086
1087 ostream& operator << (ostream& o, const probe_point& k)
1088 {
1089   k.print (o);
1090   return o;
1091 }
1092
1093
1094 ostream& operator << (ostream& o, const symboldecl& k)
1095 {
1096   k.print (o);
1097   return o;
1098 }
1099
1100
1101
1102 // ------------------------------------------------------------------------
1103 // visitors
1104
1105
1106 void
1107 block::visit (visitor* u)
1108 {
1109   u->visit_block (this);
1110 }
1111
1112
1113 void
1114 embeddedcode::visit (visitor* u)
1115 {
1116   u->visit_embeddedcode (this);
1117 }
1118
1119
1120 void
1121 for_loop::visit (visitor* u)
1122 {
1123   u->visit_for_loop (this);
1124 }
1125
1126 void
1127 foreach_loop::visit (visitor* u)
1128 {
1129   u->visit_foreach_loop (this);
1130 }
1131
1132 void
1133 null_statement::visit (visitor* u)
1134 {
1135   u->visit_null_statement (this);
1136 }
1137
1138 void
1139 expr_statement::visit (visitor* u)
1140 {
1141   u->visit_expr_statement (this);
1142 }
1143
1144 void
1145 return_statement::visit (visitor* u)
1146 {
1147   u->visit_return_statement (this);
1148 }
1149
1150 void
1151 delete_statement::visit (visitor* u)
1152 {
1153   u->push_active_lvalue (this->value);
1154   u->visit_delete_statement (this);
1155   u->pop_active_lvalue ();
1156 }
1157
1158 void
1159 if_statement::visit (visitor* u)
1160 {
1161   u->visit_if_statement (this);
1162 }
1163
1164 void
1165 next_statement::visit (visitor* u)
1166 {
1167   u->visit_next_statement (this);
1168 }
1169
1170 void
1171 break_statement::visit (visitor* u)
1172 {
1173   u->visit_break_statement (this);
1174 }
1175
1176 void
1177 continue_statement::visit (visitor* u)
1178 {
1179   u->visit_continue_statement (this);
1180 }
1181
1182 void
1183 literal_string::visit(visitor* u)
1184 {
1185   u->visit_literal_string (this);
1186 }
1187
1188 void
1189 literal_number::visit(visitor* u)
1190 {
1191   u->visit_literal_number (this);
1192 }
1193
1194 void
1195 binary_expression::visit (visitor* u)
1196 {
1197   u->visit_binary_expression (this);
1198 }
1199
1200 void
1201 unary_expression::visit (visitor* u)
1202 {
1203   u->visit_unary_expression (this);
1204 }
1205
1206 void
1207 pre_crement::visit (visitor* u)
1208 {
1209   u->push_active_lvalue (this->operand);
1210   u->visit_pre_crement (this);
1211   u->pop_active_lvalue ();
1212 }
1213
1214 void
1215 post_crement::visit (visitor* u)
1216 {
1217   u->push_active_lvalue (this->operand);
1218   u->visit_post_crement (this);
1219   u->pop_active_lvalue ();
1220 }
1221
1222 void
1223 logical_or_expr::visit (visitor* u)
1224 {
1225   u->visit_logical_or_expr (this);
1226 }
1227
1228 void
1229 logical_and_expr::visit (visitor* u)
1230 {
1231   u->visit_logical_and_expr (this);
1232 }
1233
1234 void
1235 array_in::visit (visitor* u)
1236 {
1237   u->visit_array_in (this);
1238 }
1239
1240 void
1241 comparison::visit (visitor* u)
1242 {
1243   u->visit_comparison (this);
1244 }
1245
1246 void
1247 concatenation::visit (visitor* u)
1248 {
1249   u->visit_concatenation (this);
1250 }
1251
1252 void
1253 ternary_expression::visit (visitor* u)
1254 {
1255   u->visit_ternary_expression (this);
1256 }
1257
1258 void
1259 assignment::visit (visitor* u)
1260 {
1261   u->push_active_lvalue (this->left);
1262   u->visit_assignment (this);
1263   u->pop_active_lvalue ();
1264 }
1265
1266 void
1267 symbol::visit (visitor* u)
1268 {
1269   u->visit_symbol (this);
1270 }
1271
1272 void
1273 target_symbol::visit (visitor* u)
1274 {
1275   u->visit_target_symbol(this);
1276 }
1277
1278 void
1279 target_symbol::visit_components (visitor* u)
1280 {
1281   for (unsigned i = 0; i < components.size(); ++i)
1282     if (components[i].type == comp_expression_array_index)
1283       components[i].expr_index->visit (u);
1284 }
1285
1286 void
1287 target_symbol::visit_components (update_visitor* u)
1288 {
1289   for (unsigned i = 0; i < components.size(); ++i)
1290     if (components[i].type == comp_expression_array_index)
1291       u->replace (components[i].expr_index);
1292 }
1293
1294 void
1295 cast_op::visit (visitor* u)
1296 {
1297   u->visit_cast_op(this);
1298 }
1299
1300 void
1301 arrayindex::visit (visitor* u)
1302 {
1303   u->visit_arrayindex (this);
1304 }
1305
1306 void
1307 functioncall::visit (visitor* u)
1308 {
1309   u->visit_functioncall (this);
1310 }
1311
1312 void
1313 print_format::visit (visitor *u)
1314 {
1315   u->visit_print_format (this);
1316 }
1317
1318 void
1319 stat_op::visit (visitor *u)
1320 {
1321   u->visit_stat_op (this);
1322 }
1323
1324 void
1325 hist_op::visit (visitor *u)
1326 {
1327   u->visit_hist_op (this);
1328 }
1329
1330 void
1331 indexable::print_indexable (std::ostream& o) const
1332 {
1333   const symbol *sym;
1334   const hist_op *hist;
1335   classify_const_indexable(this, sym, hist);
1336   if (sym)
1337     sym->print (o);
1338   else
1339     {
1340       assert (hist);
1341       hist->print (o);
1342     }
1343 }
1344
1345 void
1346 indexable::visit_indexable (visitor* u)
1347 {
1348   symbol *sym;
1349   hist_op *hist;
1350   classify_indexable(this, sym, hist);
1351   if (sym)
1352     sym->visit (u);
1353   else
1354     {
1355       assert (hist);
1356       hist->visit (u);
1357     }
1358 }
1359
1360
1361 bool
1362 indexable::is_symbol(symbol *& sym_out)
1363 {
1364   sym_out = NULL;
1365   return false;
1366 }
1367
1368 bool
1369 indexable::is_hist_op(hist_op *& hist_out)
1370 {
1371   hist_out = NULL;
1372   return false;
1373 }
1374
1375 bool
1376 indexable::is_const_symbol(const symbol *& sym_out) const
1377 {
1378   sym_out = NULL;
1379   return false;
1380 }
1381
1382 bool
1383 indexable::is_const_hist_op(const hist_op *& hist_out) const
1384 {
1385   hist_out = NULL;
1386   return false;
1387 }
1388
1389 bool
1390 symbol::is_symbol(symbol *& sym_out)
1391 {
1392   sym_out = this;
1393   return true;
1394 }
1395
1396 bool
1397 symbol::is_const_symbol(const symbol *& sym_out) const
1398 {
1399   sym_out = this;
1400   return true;
1401 }
1402
1403 const token *
1404 symbol::get_tok() const
1405 {
1406   return tok;
1407 }
1408
1409 bool
1410 hist_op::is_hist_op(hist_op *& hist_out)
1411 {
1412   hist_out = this;
1413   return true;
1414 }
1415
1416 bool
1417 hist_op::is_const_hist_op(const hist_op *& hist_out) const
1418 {
1419   hist_out = this;
1420   return true;
1421 }
1422
1423 const token *
1424 hist_op::get_tok() const
1425 {
1426   return tok;
1427 }
1428
1429 void
1430 classify_indexable(indexable* ix,
1431                    symbol *& array_out,
1432                    hist_op *& hist_out)
1433 {
1434   array_out = NULL;
1435   hist_out = NULL;
1436   if (!(ix->is_symbol (array_out) || ix->is_hist_op (hist_out)))
1437     throw semantic_error("Expecting symbol or histogram operator", ix->get_tok());
1438   if (ix && !(hist_out || array_out))
1439     throw semantic_error("Failed to classify indexable", ix->get_tok());
1440 }
1441
1442 void
1443 classify_const_indexable(const indexable* ix,
1444                          const symbol *& array_out,
1445                          const hist_op *& hist_out)
1446 {
1447   array_out = NULL;
1448   hist_out = NULL;
1449   if (!(ix->is_const_symbol(array_out) || ix->is_const_hist_op(hist_out)))
1450     throw semantic_error("Expecting symbol or histogram operator", ix->get_tok());
1451 }
1452
1453 // ------------------------------------------------------------------------
1454
1455 bool
1456 visitor::is_active_lvalue(expression *e)
1457 {
1458   for (unsigned i = 0; i < active_lvalues.size(); ++i)
1459     {
1460       if (active_lvalues[i] == e)
1461         return true;
1462     }
1463   return false;
1464 }
1465
1466 void
1467 visitor::push_active_lvalue(expression *e)
1468 {
1469   active_lvalues.push_back(e);
1470 }
1471
1472 void
1473 visitor::pop_active_lvalue()
1474 {
1475   assert(!active_lvalues.empty());
1476   active_lvalues.pop_back();
1477 }
1478
1479
1480
1481 // ------------------------------------------------------------------------
1482
1483 void
1484 traversing_visitor::visit_block (block* s)
1485 {
1486   for (unsigned i=0; i<s->statements.size(); i++)
1487     s->statements[i]->visit (this);
1488 }
1489
1490 void
1491 traversing_visitor::visit_embeddedcode (embeddedcode*)
1492 {
1493 }
1494
1495 void
1496 traversing_visitor::visit_null_statement (null_statement*)
1497 {
1498 }
1499
1500 void
1501 traversing_visitor::visit_expr_statement (expr_statement* s)
1502 {
1503   s->value->visit (this);
1504 }
1505
1506 void
1507 traversing_visitor::visit_if_statement (if_statement* s)
1508 {
1509   s->condition->visit (this);
1510   s->thenblock->visit (this);
1511   if (s->elseblock)
1512     s->elseblock->visit (this);
1513 }
1514
1515 void
1516 traversing_visitor::visit_for_loop (for_loop* s)
1517 {
1518   if (s->init) s->init->visit (this);
1519   s->cond->visit (this);
1520   if (s->incr) s->incr->visit (this);
1521   s->block->visit (this);
1522 }
1523
1524 void
1525 traversing_visitor::visit_foreach_loop (foreach_loop* s)
1526 {
1527   symbol *array = NULL;
1528   hist_op *hist = NULL;
1529   classify_indexable (s->base, array, hist);
1530   if (array)
1531     array->visit(this);
1532   else
1533     hist->visit(this);
1534
1535   for (unsigned i=0; i<s->indexes.size(); i++)
1536     s->indexes[i]->visit (this);
1537
1538   if (s->limit)
1539     s->limit->visit (this);
1540
1541   s->block->visit (this);
1542 }
1543
1544 void
1545 traversing_visitor::visit_return_statement (return_statement* s)
1546 {
1547   s->value->visit (this);
1548 }
1549
1550 void
1551 traversing_visitor::visit_delete_statement (delete_statement* s)
1552 {
1553   s->value->visit (this);
1554 }
1555
1556 void
1557 traversing_visitor::visit_next_statement (next_statement*)
1558 {
1559 }
1560
1561 void
1562 traversing_visitor::visit_break_statement (break_statement*)
1563 {
1564 }
1565
1566 void
1567 traversing_visitor::visit_continue_statement (continue_statement*)
1568 {
1569 }
1570
1571 void
1572 traversing_visitor::visit_literal_string (literal_string*)
1573 {
1574 }
1575
1576 void
1577 traversing_visitor::visit_literal_number (literal_number*)
1578 {
1579 }
1580
1581 void
1582 traversing_visitor::visit_binary_expression (binary_expression* e)
1583 {
1584   e->left->visit (this);
1585   e->right->visit (this);
1586 }
1587
1588 void
1589 traversing_visitor::visit_unary_expression (unary_expression* e)
1590 {
1591   e->operand->visit (this);
1592 }
1593
1594 void
1595 traversing_visitor::visit_pre_crement (pre_crement* e)
1596 {
1597   e->operand->visit (this);
1598 }
1599
1600 void
1601 traversing_visitor::visit_post_crement (post_crement* e)
1602 {
1603   e->operand->visit (this);
1604 }
1605
1606
1607 void
1608 traversing_visitor::visit_logical_or_expr (logical_or_expr* e)
1609 {
1610   e->left->visit (this);
1611   e->right->visit (this);
1612 }
1613
1614 void
1615 traversing_visitor::visit_logical_and_expr (logical_and_expr* e)
1616 {
1617   e->left->visit (this);
1618   e->right->visit (this);
1619 }
1620
1621 void
1622 traversing_visitor::visit_array_in (array_in* e)
1623 {
1624   e->operand->visit (this);
1625 }
1626
1627 void
1628 traversing_visitor::visit_comparison (comparison* e)
1629 {
1630   e->left->visit (this);
1631   e->right->visit (this);
1632 }
1633
1634 void
1635 traversing_visitor::visit_concatenation (concatenation* e)
1636 {
1637   e->left->visit (this);
1638   e->right->visit (this);
1639 }
1640
1641 void
1642 traversing_visitor::visit_ternary_expression (ternary_expression* e)
1643 {
1644   e->cond->visit (this);
1645   e->truevalue->visit (this);
1646   e->falsevalue->visit (this);
1647 }
1648
1649 void
1650 traversing_visitor::visit_assignment (assignment* e)
1651 {
1652   e->left->visit (this);
1653   e->right->visit (this);
1654 }
1655
1656 void
1657 traversing_visitor::visit_symbol (symbol*)
1658 {
1659 }
1660
1661 void
1662 traversing_visitor::visit_target_symbol (target_symbol* e)
1663 {
1664   e->visit_components (this);
1665 }
1666
1667 void
1668 traversing_visitor::visit_cast_op (cast_op* e)
1669 {
1670   e->operand->visit (this);
1671   e->visit_components (this);
1672 }
1673
1674 void
1675 traversing_visitor::visit_arrayindex (arrayindex* e)
1676 {
1677   for (unsigned i=0; i<e->indexes.size(); i++)
1678     e->indexes[i]->visit (this);
1679
1680   symbol *array = NULL;
1681   hist_op *hist = NULL;
1682   classify_indexable(e->base, array, hist);
1683   if (array)
1684     return array->visit(this);
1685   else
1686     return hist->visit(this);
1687 }
1688
1689 void
1690 traversing_visitor::visit_functioncall (functioncall* e)
1691 {
1692   for (unsigned i=0; i<e->args.size(); i++)
1693     e->args[i]->visit (this);
1694 }
1695
1696 void
1697 traversing_visitor::visit_print_format (print_format* e)
1698 {
1699   for (unsigned i=0; i<e->args.size(); i++)
1700     e->args[i]->visit (this);
1701   if (e->hist)
1702     e->hist->visit(this);
1703 }
1704
1705 void
1706 traversing_visitor::visit_stat_op (stat_op* e)
1707 {
1708   e->stat->visit (this);
1709 }
1710
1711 void
1712 traversing_visitor::visit_hist_op (hist_op* e)
1713 {
1714   e->stat->visit (this);
1715 }
1716
1717
1718 void
1719 functioncall_traversing_visitor::visit_functioncall (functioncall* e)
1720 {
1721   traversing_visitor::visit_functioncall (e);
1722
1723   // prevent infinite recursion
1724   if (traversed.find (e->referent) == traversed.end ())
1725     {
1726       traversed.insert (e->referent);
1727       // recurse
1728       functiondecl* last_current_function = current_function;
1729       current_function = e->referent;
1730       e->referent->body->visit (this);
1731       current_function = last_current_function;
1732     }
1733 }
1734
1735
1736 void
1737 varuse_collecting_visitor::visit_embeddedcode (embeddedcode *s)
1738 {
1739   assert (current_function); // only they get embedded code
1740
1741   // Don't allow embedded C functions in unprivileged mode unless
1742   // they are tagged with /* unprivileged */
1743   if (session.unprivileged && s->code.find ("/* unprivileged */") == string::npos)
1744     throw semantic_error ("function may not be used when --unprivileged is specified",
1745                           current_function->tok);
1746
1747   // We want to elide embedded-C functions when possible.  For
1748   // example, each $target variable access is expanded to an
1749   // embedded-C function call.  Yet, for safety reasons, we should
1750   // presume that embedded-C functions have intentional side-effects.
1751   //
1752   // To tell these two types of functions apart, we apply a
1753   // Kludge(tm): we look for a magic string within the function body.
1754   // $target variables as rvalues will have this; lvalues won't.
1755   // Also, explicit side-effect-free tapset functions will have this.
1756
1757   if (s->code.find ("/* pure */") != string::npos)
1758     return;
1759
1760   embedded_seen = true;
1761 }
1762
1763 void
1764 varuse_collecting_visitor::visit_target_symbol (target_symbol *e)
1765 {
1766   // Still-unresolved target symbol assignments get treated as
1767   // generating side-effects like embedded-C, to prevent premature
1768   // elision and later error message suppression (PR5516).  rvalue use
1769   // of unresolved target symbols is OTOH not considered a side-effect.
1770
1771   if (is_active_lvalue (e))
1772     embedded_seen = true;
1773
1774   functioncall_traversing_visitor::visit_target_symbol (e);
1775 }
1776
1777 void
1778 varuse_collecting_visitor::visit_cast_op (cast_op *e)
1779 {
1780   // As with target_symbols, unresolved cast assignments need to preserved
1781   // for later error handling.
1782   if (is_active_lvalue (e))
1783     embedded_seen = true;
1784
1785   functioncall_traversing_visitor::visit_cast_op (e);
1786 }
1787
1788 void
1789 varuse_collecting_visitor::visit_print_format (print_format* e)
1790 {
1791   // NB: Instead of being top-level statements, "print" and "printf"
1792   // are implemented as statement-expressions containing a
1793   // print_format.  They have side-effects, but not via the
1794   // embedded-code detection method above.
1795   //
1796   // But sprint and sprintf don't have side-effects.
1797
1798   if (e->print_to_stream)
1799     embedded_seen = true; // a proxy for "has unknown side-effects"
1800
1801   functioncall_traversing_visitor::visit_print_format (e);
1802 }
1803
1804
1805 void
1806 varuse_collecting_visitor::visit_assignment (assignment *e)
1807 {
1808   if (e->op == "=" || e->op == "<<<") // pure writes
1809     {
1810       expression* last_lvalue = current_lvalue;
1811       current_lvalue = e->left; // leave a mark for ::visit_symbol
1812       functioncall_traversing_visitor::visit_assignment (e);
1813       current_lvalue = last_lvalue;
1814     }
1815   else // read-modify-writes
1816     {
1817       expression* last_lrvalue = current_lrvalue;
1818       current_lrvalue = e->left; // leave a mark for ::visit_symbol
1819       functioncall_traversing_visitor::visit_assignment (e);
1820       current_lrvalue = last_lrvalue;
1821     }
1822 }
1823
1824 void
1825 varuse_collecting_visitor::visit_symbol (symbol *e)
1826 {
1827   if (e->referent == 0)
1828     throw semantic_error ("symbol without referent", e->tok);
1829
1830   // We could handle initialized globals by marking them as "written".
1831   // However, this current visitor may be called for a function or
1832   // probe body, from the point of view of which this global is
1833   // already initialized, so not written.
1834   /*
1835   if (e->referent->init)
1836     written.insert (e->referent);
1837   */
1838
1839   if (current_lvalue == e || current_lrvalue == e)
1840     {
1841       written.insert (e->referent);
1842       // clog << "write ";
1843     }
1844   if (current_lvalue != e || current_lrvalue == e)
1845     {
1846       read.insert (e->referent);
1847       // clog << "read ";
1848     }
1849   // clog << *e->tok << endl;
1850 }
1851
1852 // NB: stat_op need not be overridden, since it will get to
1853 // visit_symbol and only as a possible rvalue.
1854
1855
1856 void
1857 varuse_collecting_visitor::visit_arrayindex (arrayindex *e)
1858 {
1859   // Hooking this callback is necessary because of the hacky
1860   // statistics representation.  For the expression "i[4] = 5", the
1861   // incoming lvalue will point to this arrayindex.  However, the
1862   // symbol corresponding to the "i[4]" is multiply inherited with
1863   // arrayindex.  If the symbol base part of this object is not at
1864   // offset 0, then static_cast<symbol*>(e) may result in a different
1865   // address, and not match lvalue by number when we recurse that way.
1866   // So we explicitly override the incoming lvalue/lrvalue values to
1867   // point at the embedded objects' actual base addresses.
1868
1869   expression* last_lrvalue = current_lrvalue;
1870   expression* last_lvalue = current_lvalue;
1871
1872   symbol *array = NULL;
1873   hist_op *hist = NULL;
1874   classify_indexable(e->base, array, hist);
1875
1876   if (array)
1877     {
1878       if (current_lrvalue == e) current_lrvalue = array;
1879       if (current_lvalue == e) current_lvalue = array;
1880       functioncall_traversing_visitor::visit_arrayindex (e);
1881     }
1882   else // if (hist)
1883     {
1884       if (current_lrvalue == e) current_lrvalue = hist->stat;
1885       if (current_lvalue == e) current_lvalue = hist->stat;
1886       functioncall_traversing_visitor::visit_arrayindex (e);
1887     }
1888
1889   current_lrvalue = last_lrvalue;
1890   current_lvalue = last_lvalue;
1891 }
1892
1893
1894 void
1895 varuse_collecting_visitor::visit_pre_crement (pre_crement *e)
1896 {
1897   expression* last_lrvalue = current_lrvalue;
1898   current_lrvalue = e->operand; // leave a mark for ::visit_symbol
1899   functioncall_traversing_visitor::visit_pre_crement (e);
1900   current_lrvalue = last_lrvalue;
1901 }
1902
1903 void
1904 varuse_collecting_visitor::visit_post_crement (post_crement *e)
1905 {
1906   expression* last_lrvalue = current_lrvalue;
1907   current_lrvalue = e->operand; // leave a mark for ::visit_symbol
1908   functioncall_traversing_visitor::visit_post_crement (e);
1909   current_lrvalue = last_lrvalue;
1910 }
1911
1912 void
1913 varuse_collecting_visitor::visit_foreach_loop (foreach_loop* s)
1914 {
1915   // NB: we duplicate so don't bother call
1916   // functioncall_traversing_visitor::visit_foreach_loop (s);
1917
1918   symbol *array = NULL;
1919   hist_op *hist = NULL;
1920   classify_indexable (s->base, array, hist);
1921   if (array)
1922     array->visit(this);
1923   else
1924     hist->visit(this);
1925
1926   // If the collection is sorted, imply a "write" access to the
1927   // array in addition to the "read" one already noted above.
1928   if (s->sort_direction)
1929     {
1930       symbol *array = NULL;
1931       hist_op *hist = NULL;
1932       classify_indexable (s->base, array, hist);
1933       if (array) this->written.insert (array->referent);
1934       // XXX: Can hist_op iterations be sorted?
1935     }
1936
1937   // NB: don't forget to visit the index expressions, which are lvalues.
1938   for (unsigned i=0; i<s->indexes.size(); i++)
1939     {
1940       expression* last_lvalue = current_lvalue;
1941       current_lvalue = s->indexes[i]; // leave a mark for ::visit_symbol
1942       s->indexes[i]->visit (this);
1943       current_lvalue = last_lvalue;
1944     }
1945
1946   if (s->limit)
1947     s->limit->visit (this);
1948
1949   s->block->visit (this);
1950 }
1951
1952
1953 void
1954 varuse_collecting_visitor::visit_delete_statement (delete_statement* s)
1955 {
1956   // Ideally, this would be treated like an assignment: a plain write
1957   // to the underlying value ("lvalue").  XXX: However, the
1958   // optimization pass is not smart enough to remove an unneeded
1959   // "delete" yet, so we pose more like a *crement ("lrvalue").  This
1960   // should protect the underlying value from optimizional mischief.
1961   expression* last_lrvalue = current_lrvalue;
1962   current_lrvalue = s->value; // leave a mark for ::visit_symbol
1963   functioncall_traversing_visitor::visit_delete_statement (s);
1964   current_lrvalue = last_lrvalue;
1965 }
1966
1967 bool
1968 varuse_collecting_visitor::side_effect_free ()
1969 {
1970   return (written.empty() && !embedded_seen);
1971 }
1972
1973
1974 bool
1975 varuse_collecting_visitor::side_effect_free_wrt (const set<vardecl*>& vars)
1976 {
1977   // A looser notion of side-effect-freeness with respect to a given
1978   // list of variables.
1979
1980   // That's useful because the written list may consist of local
1981   // variables of called functions.  But visible side-effects only
1982   // occur if the client's locals, or any globals are written-to.
1983
1984   set<vardecl*> intersection;
1985   insert_iterator<set<vardecl*> > int_it (intersection, intersection.begin());
1986   set_intersection (written.begin(), written.end(),
1987                     vars.begin(), vars.end(),
1988                     int_it);
1989
1990   return (intersection.empty() && !embedded_seen);
1991 }
1992
1993
1994
1995
1996 // ------------------------------------------------------------------------
1997
1998
1999 throwing_visitor::throwing_visitor (const std::string& m): msg (m) {}
2000 throwing_visitor::throwing_visitor (): msg ("invalid element") {}
2001
2002
2003 void
2004 throwing_visitor::throwone (const token* t)
2005 {
2006   throw semantic_error (msg, t);
2007 }
2008
2009 void
2010 throwing_visitor::visit_block (block* s)
2011 {
2012   throwone (s->tok);
2013 }
2014
2015 void
2016 throwing_visitor::visit_embeddedcode (embeddedcode* s)
2017 {
2018   throwone (s->tok);
2019 }
2020
2021 void
2022 throwing_visitor::visit_null_statement (null_statement* s)
2023 {
2024   throwone (s->tok);
2025 }
2026
2027 void
2028 throwing_visitor::visit_expr_statement (expr_statement* s)
2029 {
2030   throwone (s->tok);
2031 }
2032
2033 void
2034 throwing_visitor::visit_if_statement (if_statement* s)
2035 {
2036   throwone (s->tok);
2037 }
2038
2039 void
2040 throwing_visitor::visit_for_loop (for_loop* s)
2041 {
2042   throwone (s->tok);
2043 }
2044
2045 void
2046 throwing_visitor::visit_foreach_loop (foreach_loop* s)
2047 {
2048   throwone (s->tok);
2049 }
2050
2051 void
2052 throwing_visitor::visit_return_statement (return_statement* s)
2053 {
2054   throwone (s->tok);
2055 }
2056
2057 void
2058 throwing_visitor::visit_delete_statement (delete_statement* s)
2059 {
2060   throwone (s->tok);
2061 }
2062
2063 void
2064 throwing_visitor::visit_next_statement (next_statement* s)
2065 {
2066   throwone (s->tok);
2067 }
2068
2069 void
2070 throwing_visitor::visit_break_statement (break_statement* s)
2071 {
2072   throwone (s->tok);
2073 }
2074
2075 void
2076 throwing_visitor::visit_continue_statement (continue_statement* s)
2077 {
2078   throwone (s->tok);
2079 }
2080
2081 void
2082 throwing_visitor::visit_literal_string (literal_string* e)
2083 {
2084   throwone (e->tok);
2085 }
2086
2087 void
2088 throwing_visitor::visit_literal_number (literal_number* e)
2089 {
2090   throwone (e->tok);
2091 }
2092
2093 void
2094 throwing_visitor::visit_binary_expression (binary_expression* e)
2095 {
2096   throwone (e->tok);
2097 }
2098
2099 void
2100 throwing_visitor::visit_unary_expression (unary_expression* e)
2101 {
2102   throwone (e->tok);
2103 }
2104
2105 void
2106 throwing_visitor::visit_pre_crement (pre_crement* e)
2107 {
2108   throwone (e->tok);
2109 }
2110
2111 void
2112 throwing_visitor::visit_post_crement (post_crement* e)
2113 {
2114   throwone (e->tok);
2115 }
2116
2117
2118 void
2119 throwing_visitor::visit_logical_or_expr (logical_or_expr* e)
2120 {
2121   throwone (e->tok);
2122 }
2123
2124 void
2125 throwing_visitor::visit_logical_and_expr (logical_and_expr* e)
2126 {
2127   throwone (e->tok);
2128 }
2129
2130 void
2131 throwing_visitor::visit_array_in (array_in* e)
2132 {
2133   throwone (e->tok);
2134 }
2135
2136 void
2137 throwing_visitor::visit_comparison (comparison* e)
2138 {
2139   throwone (e->tok);
2140 }
2141
2142 void
2143 throwing_visitor::visit_concatenation (concatenation* e)
2144 {
2145   throwone (e->tok);
2146 }
2147
2148 void
2149 throwing_visitor::visit_ternary_expression (ternary_expression* e)
2150 {
2151   throwone (e->tok);
2152 }
2153
2154 void
2155 throwing_visitor::visit_assignment (assignment* e)
2156 {
2157   throwone (e->tok);
2158 }
2159
2160 void
2161 throwing_visitor::visit_symbol (symbol* e)
2162 {
2163   throwone (e->tok);
2164 }
2165
2166 void
2167 throwing_visitor::visit_target_symbol (target_symbol* e)
2168 {
2169   throwone (e->tok);
2170 }
2171
2172 void
2173 throwing_visitor::visit_cast_op (cast_op* e)
2174 {
2175   throwone (e->tok);
2176 }
2177
2178 void
2179 throwing_visitor::visit_arrayindex (arrayindex* e)
2180 {
2181   throwone (e->tok);
2182 }
2183
2184 void
2185 throwing_visitor::visit_functioncall (functioncall* e)
2186 {
2187   throwone (e->tok);
2188 }
2189
2190 void
2191 throwing_visitor::visit_print_format (print_format* e)
2192 {
2193   throwone (e->tok);
2194 }
2195
2196 void
2197 throwing_visitor::visit_stat_op (stat_op* e)
2198 {
2199   throwone (e->tok);
2200 }
2201
2202 void
2203 throwing_visitor::visit_hist_op (hist_op* e)
2204 {
2205   throwone (e->tok);
2206 }
2207
2208
2209 // ------------------------------------------------------------------------
2210
2211
2212 void
2213 update_visitor::visit_block (block* s)
2214 {
2215   for (unsigned i = 0; i < s->statements.size(); ++i)
2216     replace (s->statements[i]);
2217   provide (s);
2218 }
2219
2220 void
2221 update_visitor::visit_embeddedcode (embeddedcode* s)
2222 {
2223   provide (s);
2224 }
2225
2226 void
2227 update_visitor::visit_null_statement (null_statement* s)
2228 {
2229   provide (s);
2230 }
2231
2232 void
2233 update_visitor::visit_expr_statement (expr_statement* s)
2234 {
2235   replace (s->value);
2236   provide (s);
2237 }
2238
2239 void
2240 update_visitor::visit_if_statement (if_statement* s)
2241 {
2242   replace (s->condition);
2243   replace (s->thenblock);
2244   replace (s->elseblock);
2245   provide (s);
2246 }
2247
2248 void
2249 update_visitor::visit_for_loop (for_loop* s)
2250 {
2251   replace (s->init);
2252   replace (s->cond);
2253   replace (s->incr);
2254   replace (s->block);
2255   provide (s);
2256 }
2257
2258 void
2259 update_visitor::visit_foreach_loop (foreach_loop* s)
2260 {
2261   for (unsigned i = 0; i < s->indexes.size(); ++i)
2262     replace (s->indexes[i]);
2263   replace (s->base);
2264   replace (s->limit);
2265   replace (s->block);
2266   provide (s);
2267 }
2268
2269 void
2270 update_visitor::visit_return_statement (return_statement* s)
2271 {
2272   replace (s->value);
2273   provide (s);
2274 }
2275
2276 void
2277 update_visitor::visit_delete_statement (delete_statement* s)
2278 {
2279   replace (s->value);
2280   provide (s);
2281 }
2282
2283 void
2284 update_visitor::visit_next_statement (next_statement* s)
2285 {
2286   provide (s);
2287 }
2288
2289 void
2290 update_visitor::visit_break_statement (break_statement* s)
2291 {
2292   provide (s);
2293 }
2294
2295 void
2296 update_visitor::visit_continue_statement (continue_statement* s)
2297 {
2298   provide (s);
2299 }
2300
2301 void
2302 update_visitor::visit_literal_string (literal_string* e)
2303 {
2304   provide (e);
2305 }
2306
2307 void
2308 update_visitor::visit_literal_number (literal_number* e)
2309 {
2310   provide (e);
2311 }
2312
2313 void
2314 update_visitor::visit_binary_expression (binary_expression* e)
2315 {
2316   replace (e->left);
2317   replace (e->right);
2318   provide (e);
2319 }
2320
2321 void
2322 update_visitor::visit_unary_expression (unary_expression* e)
2323 {
2324   replace (e->operand);
2325   provide (e);
2326 }
2327
2328 void
2329 update_visitor::visit_pre_crement (pre_crement* e)
2330 {
2331   replace (e->operand);
2332   provide (e);
2333 }
2334
2335 void
2336 update_visitor::visit_post_crement (post_crement* e)
2337 {
2338   replace (e->operand);
2339   provide (e);
2340 }
2341
2342
2343 void
2344 update_visitor::visit_logical_or_expr (logical_or_expr* e)
2345 {
2346   replace (e->left);
2347   replace (e->right);
2348   provide (e);
2349 }
2350
2351 void
2352 update_visitor::visit_logical_and_expr (logical_and_expr* e)
2353 {
2354   replace (e->left);
2355   replace (e->right);
2356   provide (e);
2357 }
2358
2359 void
2360 update_visitor::visit_array_in (array_in* e)
2361 {
2362   replace (e->operand);
2363   provide (e);
2364 }
2365
2366 void
2367 update_visitor::visit_comparison (comparison* e)
2368 {
2369   replace (e->left);
2370   replace (e->right);
2371   provide (e);
2372 }
2373
2374 void
2375 update_visitor::visit_concatenation (concatenation* e)
2376 {
2377   replace (e->left);
2378   replace (e->right);
2379   provide (e);
2380 }
2381
2382 void
2383 update_visitor::visit_ternary_expression (ternary_expression* e)
2384 {
2385   replace (e->cond);
2386   replace (e->truevalue);
2387   replace (e->falsevalue);
2388   provide (e);
2389 }
2390
2391 void
2392 update_visitor::visit_assignment (assignment* e)
2393 {
2394   replace (e->left);
2395   replace (e->right);
2396   provide (e);
2397 }
2398
2399 void
2400 update_visitor::visit_symbol (symbol* e)
2401 {
2402   provide (e);
2403 }
2404
2405 void
2406 update_visitor::visit_target_symbol (target_symbol* e)
2407 {
2408   e->visit_components (this);
2409   provide (e);
2410 }
2411
2412 void
2413 update_visitor::visit_cast_op (cast_op* e)
2414 {
2415   replace (e->operand);
2416   e->visit_components (this);
2417   provide (e);
2418 }
2419
2420 void
2421 update_visitor::visit_arrayindex (arrayindex* e)
2422 {
2423   replace (e->base);
2424   for (unsigned i = 0; i < e->indexes.size(); ++i)
2425     replace (e->indexes[i]);
2426   provide (e);
2427 }
2428
2429 void
2430 update_visitor::visit_functioncall (functioncall* e)
2431 {
2432   for (unsigned i = 0; i < e->args.size(); ++i)
2433     replace (e->args[i]);
2434   provide (e);
2435 }
2436
2437 void
2438 update_visitor::visit_print_format (print_format* e)
2439 {
2440   for (unsigned i = 0; i < e->args.size(); ++i)
2441     replace (e->args[i]);
2442   replace (e->hist);
2443   provide (e);
2444 }
2445
2446 void
2447 update_visitor::visit_stat_op (stat_op* e)
2448 {
2449   replace (e->stat);
2450   provide (e);
2451 }
2452
2453 void
2454 update_visitor::visit_hist_op (hist_op* e)
2455 {
2456   replace (e->stat);
2457   provide (e);
2458 }
2459
2460 template <> indexable*
2461 update_visitor::require <indexable> (indexable* src, bool clearok)
2462 {
2463   indexable *dst = NULL;
2464   if (src != NULL)
2465     {
2466       symbol *array_src=NULL;
2467       hist_op *hist_src=NULL;
2468
2469       classify_indexable(src, array_src, hist_src);
2470
2471       if (array_src)
2472         dst = require (array_src);
2473       else
2474         dst = require (hist_src);
2475       assert(clearok || dst);
2476     }
2477   return dst;
2478 }
2479
2480
2481 // ------------------------------------------------------------------------
2482
2483
2484 void
2485 deep_copy_visitor::visit_block (block* s)
2486 {
2487   update_visitor::visit_block(new block(*s));
2488 }
2489
2490 void
2491 deep_copy_visitor::visit_embeddedcode (embeddedcode* s)
2492 {
2493   update_visitor::visit_embeddedcode(new embeddedcode(*s));
2494 }
2495
2496 void
2497 deep_copy_visitor::visit_null_statement (null_statement* s)
2498 {
2499   update_visitor::visit_null_statement(new null_statement(*s));
2500 }
2501
2502 void
2503 deep_copy_visitor::visit_expr_statement (expr_statement* s)
2504 {
2505   update_visitor::visit_expr_statement(new expr_statement(*s));
2506 }
2507
2508 void
2509 deep_copy_visitor::visit_if_statement (if_statement* s)
2510 {
2511   update_visitor::visit_if_statement(new if_statement(*s));
2512 }
2513
2514 void
2515 deep_copy_visitor::visit_for_loop (for_loop* s)
2516 {
2517   update_visitor::visit_for_loop(new for_loop(*s));
2518 }
2519
2520 void
2521 deep_copy_visitor::visit_foreach_loop (foreach_loop* s)
2522 {
2523   update_visitor::visit_foreach_loop(new foreach_loop(*s));
2524 }
2525
2526 void
2527 deep_copy_visitor::visit_return_statement (return_statement* s)
2528 {
2529   update_visitor::visit_return_statement(new return_statement(*s));
2530 }
2531
2532 void
2533 deep_copy_visitor::visit_delete_statement (delete_statement* s)
2534 {
2535   update_visitor::visit_delete_statement(new delete_statement(*s));
2536 }
2537
2538 void
2539 deep_copy_visitor::visit_next_statement (next_statement* s)
2540 {
2541   update_visitor::visit_next_statement(new next_statement(*s));
2542 }
2543
2544 void
2545 deep_copy_visitor::visit_break_statement (break_statement* s)
2546 {
2547   update_visitor::visit_break_statement(new break_statement(*s));
2548 }
2549
2550 void
2551 deep_copy_visitor::visit_continue_statement (continue_statement* s)
2552 {
2553   update_visitor::visit_continue_statement(new continue_statement(*s));
2554 }
2555
2556 void
2557 deep_copy_visitor::visit_literal_string (literal_string* e)
2558 {
2559   update_visitor::visit_literal_string(new literal_string(*e));
2560 }
2561
2562 void
2563 deep_copy_visitor::visit_literal_number (literal_number* e)
2564 {
2565   update_visitor::visit_literal_number(new literal_number(*e));
2566 }
2567
2568 void
2569 deep_copy_visitor::visit_binary_expression (binary_expression* e)
2570 {
2571   update_visitor::visit_binary_expression(new binary_expression(*e));
2572 }
2573
2574 void
2575 deep_copy_visitor::visit_unary_expression (unary_expression* e)
2576 {
2577   update_visitor::visit_unary_expression(new unary_expression(*e));
2578 }
2579
2580 void
2581 deep_copy_visitor::visit_pre_crement (pre_crement* e)
2582 {
2583   update_visitor::visit_pre_crement(new pre_crement(*e));
2584 }
2585
2586 void
2587 deep_copy_visitor::visit_post_crement (post_crement* e)
2588 {
2589   update_visitor::visit_post_crement(new post_crement(*e));
2590 }
2591
2592
2593 void
2594 deep_copy_visitor::visit_logical_or_expr (logical_or_expr* e)
2595 {
2596   update_visitor::visit_logical_or_expr(new logical_or_expr(*e));
2597 }
2598
2599 void
2600 deep_copy_visitor::visit_logical_and_expr (logical_and_expr* e)
2601 {
2602   update_visitor::visit_logical_and_expr(new logical_and_expr(*e));
2603 }
2604
2605 void
2606 deep_copy_visitor::visit_array_in (array_in* e)
2607 {
2608   update_visitor::visit_array_in(new array_in(*e));
2609 }
2610
2611 void
2612 deep_copy_visitor::visit_comparison (comparison* e)
2613 {
2614   update_visitor::visit_comparison(new comparison(*e));
2615 }
2616
2617 void
2618 deep_copy_visitor::visit_concatenation (concatenation* e)
2619 {
2620   update_visitor::visit_concatenation(new concatenation(*e));
2621 }
2622
2623 void
2624 deep_copy_visitor::visit_ternary_expression (ternary_expression* e)
2625 {
2626   update_visitor::visit_ternary_expression(new ternary_expression(*e));
2627 }
2628
2629 void
2630 deep_copy_visitor::visit_assignment (assignment* e)
2631 {
2632   update_visitor::visit_assignment(new assignment(*e));
2633 }
2634
2635 void
2636 deep_copy_visitor::visit_symbol (symbol* e)
2637 {
2638   symbol* n = new symbol(*e);
2639   n->referent = NULL; // don't copy!
2640   update_visitor::visit_symbol(n);
2641 }
2642
2643 void
2644 deep_copy_visitor::visit_target_symbol (target_symbol* e)
2645 {
2646   target_symbol* n = new target_symbol(*e);
2647   n->referent = NULL; // don't copy!
2648   update_visitor::visit_target_symbol(n);
2649 }
2650
2651 void
2652 deep_copy_visitor::visit_cast_op (cast_op* e)
2653 {
2654   update_visitor::visit_cast_op(new cast_op(*e));
2655 }
2656
2657 void
2658 deep_copy_visitor::visit_arrayindex (arrayindex* e)
2659 {
2660   update_visitor::visit_arrayindex(new arrayindex(*e));
2661 }
2662
2663 void
2664 deep_copy_visitor::visit_functioncall (functioncall* e)
2665 {
2666   functioncall* n = new functioncall(*e);
2667   n->referent = NULL; // don't copy!
2668   update_visitor::visit_functioncall(n);
2669 }
2670
2671 void
2672 deep_copy_visitor::visit_print_format (print_format* e)
2673 {
2674   update_visitor::visit_print_format(new print_format(*e));
2675 }
2676
2677 void
2678 deep_copy_visitor::visit_stat_op (stat_op* e)
2679 {
2680   update_visitor::visit_stat_op(new stat_op(*e));
2681 }
2682
2683 void
2684 deep_copy_visitor::visit_hist_op (hist_op* e)
2685 {
2686   update_visitor::visit_hist_op(new hist_op(*e));
2687 }
2688
2689 /* vim: set sw=2 ts=8 cino=>4,n-2,{2,^-2,t0,(0,u0,w1,M1 : */