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