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