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