hphp/compiler/expression/expression.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 Facebook, Inc. (http://www.facebook.com)     |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/compiler/expression/expression.h"
  18 #include "hphp/compiler/analysis/code_error.h"
  19 #include "hphp/compiler/parser/parser.h"
  20 #include "hphp/util/parser/hphp.tab.hpp"
  21 #include "hphp/util/util.h"
  22 #include "hphp/compiler/analysis/class_scope.h"
  23 #include "hphp/compiler/analysis/function_scope.h"
  24 #include "hphp/compiler/expression/scalar_expression.h"
  25 #include "hphp/compiler/expression/constant_expression.h"
  26 #include "hphp/compiler/expression/expression_list.h"
  27 #include "hphp/compiler/expression/simple_variable.h"
  28 #include "hphp/compiler/expression/assignment_expression.h"
  29 #include "hphp/compiler/expression/array_pair_expression.h"
  30 #include "hphp/compiler/expression/array_element_expression.h"
  31 #include "hphp/compiler/expression/object_property_expression.h"
  32 #include "hphp/compiler/expression/unary_op_expression.h"
  33 #include "hphp/compiler/analysis/constant_table.h"
  34 #include "hphp/compiler/analysis/variable_table.h"
  35 #include "hphp/compiler/expression/function_call.h"
  36 #include "hphp/compiler/analysis/file_scope.h"
  37 #include "hphp/util/hash.h"
  38 #include "hphp/runtime/base/array_iterator.h"
  39
  40 using namespace HPHP;
  41
  42 ///////////////////////////////////////////////////////////////////////////////
  43
  44 #define DEC_EXPR_NAMES(x,t) #x
  45 const char *Expression::Names[] = {
  46   DECLARE_EXPRESSION_TYPES(DEC_EXPR_NAMES)
  47 };
  48
  49 #define DEC_EXPR_CLASSES(x,t) Expression::t
  50 Expression::ExprClass Expression::Classes[] = {
  51   DECLARE_EXPRESSION_TYPES(DEC_EXPR_CLASSES)
  52 };
  53
  54 Expression::Expression(EXPRESSION_CONSTRUCTOR_BASE_PARAMETERS)
  55     : Construct(scope, loc), m_context(RValue), m_kindOf(kindOf),
  56       m_originalScopeSet(false), m_unused(false), m_canon_id(0), m_error(0),
  57       m_canonPtr() {
  58 }
  59
  60 ExpressionPtr Expression::replaceValue(ExpressionPtr rep) {
  61   if (hasContext(Expression::RefValue) &&
  62       isRefable(true) && !rep->isRefable(true)) {
  63     /*
  64       An assignment isRefable, but the rhs may not be. Need this to
  65       prevent "bad pass by reference" errors.
  66     */
  67     ExpressionListPtr el(new ExpressionList(getScope(), getLocation(),
  68                                             ExpressionList::ListKindWrapped));
  69     el->addElement(rep);
  70     rep->clearContext(AssignmentRHS);
  71     rep = el;
  72   }
  73   if (isChildOfYield()) rep->setChildOfYield();
  74   if (rep->is(KindOfSimpleVariable) && !is(KindOfSimpleVariable)) {
  75     static_pointer_cast<SimpleVariable>(rep)->setAlwaysStash();
  76   }
  77   rep->copyContext(m_context & ~(DeadStore|AccessContext));
  78   if (TypePtr t1 = getType()) {
  79     if (TypePtr t2 = rep->getType()) {
  80       if (!Type::SameType(t1, t2)) {
  81         rep->setExpectedType(t1);
  82       }
  83     }
  84   }
  85
  86   if (rep->getScope() != getScope()) {
  87     rep->resetScope(getScope());
  88   }
  89
  90   return rep;
  91 }
  92
  93 void Expression::copyContext(int contexts) {
  94   unsigned val = contexts;
  95   while (val) {
  96     unsigned next = val & (val - 1);
  97     unsigned low = val ^ next; // lowest set bit
  98     setContext((Context)low);
  99     val = next;
 100   }
 101 }
 102
 103 void Expression::clearContext() {
 104   unsigned val = m_context;
 105   while (val) {
 106     unsigned next = val & (val - 1);
 107     unsigned low = val ^ next; // lowest set bit
 108     clearContext((Context)low);
 109     val = next;
 110   }
 111 }
 112
 113 void Expression::setArgNum(int n) {
 114   m_argNum = n;
 115   int kc = getKidCount();
 116   for (int i=0; i < kc; i++) {
 117     ExpressionPtr kid = getNthExpr(i);
 118     if (kid) {
 119       kid->setArgNum(n);
 120     }
 121   }
 122 }
 123
 124 void Expression::deepCopy(ExpressionPtr exp) {
 125   exp->m_actualType = m_actualType;
 126   exp->m_expectedType = m_expectedType;
 127   exp->m_implementedType = m_implementedType;
 128   exp->m_assertedType = m_assertedType;
 129   exp->m_canon_id = 0;
 130   exp->m_unused = false;
 131   exp->m_canonPtr.reset();
 132   exp->m_replacement.reset();
 133   exp->clearVisited();
 134 };
 135
 136 bool Expression::hasSubExpr(ExpressionPtr sub) const {
 137   if (this == sub.get()) return true;
 138   for (int i = getKidCount(); i--; ) {
 139     ExpressionPtr kid = getNthExpr(i);
 140     if (kid && kid->hasSubExpr(sub)) return true;
 141   }
 142   return false;
 143 }
 144
 145 Expression::ExprClass Expression::getExprClass() const {
 146   ExprClass cls = Classes[m_kindOf];
 147   if (cls == Update) {
 148     ExpressionPtr k = getStoreVariable();
 149     if (!k || !(k->hasContext(OprLValue))) cls = Expression::None;
 150   }
 151   return cls;
 152 }
 153
 154 FileScopeRawPtr Expression::getUsedScalarScope(CodeGenerator& cg) {
 155   return cg.getLiteralScope() ?
 156     cg.getLiteralScope() : getFileScope();
 157 }
 158
 159 bool Expression::getEffectiveScalar(Variant &v) {
 160   if (is(KindOfExpressionList)) {
 161     ExpressionRawPtr sub = static_cast<ExpressionList*>(this)->listValue();
 162     if (!sub) return false;
 163     return sub->getEffectiveScalar(v);
 164   }
 165   return getScalarValue(v);
 166 }
 167
 168 void Expression::addElement(ExpressionPtr exp) {
 169   assert(false);
 170 }
 171
 172 void Expression::insertElement(ExpressionPtr exp, int index /* = 0 */) {
 173   assert(false);
 174 }
 175
 176 ExpressionPtr Expression::unneededHelper() {
 177   ExpressionListPtr elist = ExpressionListPtr
 178     (new ExpressionList(getScope(), getLocation(),
 179                         ExpressionList::ListKindWrapped));
 180
 181   bool change = false;
 182   for (int i=0, n = getKidCount(); i < n; i++) {
 183     ExpressionPtr kid = getNthExpr(i);
 184     if (kid && kid->getContainedEffects()) {
 185       ExpressionPtr rep = kid->unneeded();
 186       if (rep != kid) change = true;
 187       if (rep->is(Expression::KindOfExpressionList)) {
 188         for (int j=0, m = rep->getKidCount(); j < m; j++) {
 189           elist->addElement(rep->getNthExpr(j));
 190         }
 191       } else {
 192         elist->addElement(rep);
 193       }
 194     }
 195   }
 196
 197   if (change) {
 198     getScope()->addUpdates(BlockScope::UseKindCaller);
 199   }
 200
 201   int n = elist->getCount();
 202   assert(n);
 203   if (n == 1) {
 204     return elist->getNthExpr(0);
 205   } else {
 206     return elist;
 207   }
 208 }
 209
 210 ExpressionPtr Expression::unneeded() {
 211   if (getLocalEffects() || is(KindOfScalarExpression) || isNoRemove()) {
 212     return static_pointer_cast<Expression>(shared_from_this());
 213   }
 214   if (!getContainedEffects()) {
 215     getScope()->addUpdates(BlockScope::UseKindCaller);
 216     return ScalarExpressionPtr
 217       (new ScalarExpression(getScope(), getLocation(),
 218                             T_LNUMBER, string("0")));
 219   }
 220
 221   return unneededHelper();
 222 }
 223
 224 ///////////////////////////////////////////////////////////////////////////////
 225
 226 bool Expression::IsIdentifier(const string &value) {
 227   if (value.empty()) {
 228     return false;
 229   }
 230   unsigned char ch = value[0];
 231   if ((ch < 'a' || ch > 'z') && (ch < 'A' || ch > 'Z') &&
 232       ch < '\x7f' && ch != '_') {
 233     return false;
 234   }
 235   for (unsigned int i = 1; i < value.size(); i++) {
 236     unsigned char ch = value[i];
 237     if (((ch < 'a' || ch > 'z') && (ch < 'A' || ch > 'Z') &&
 238          (ch < '0' || ch > '9') && ch < '\x7f' && ch != '_')) {
 239       if (ch == '\\' && i < value.size() - 1 && value[i+1] != '\\') {
 240         continue;
 241       }
 242       return false;
 243     }
 244   }
 245   return true;
 246 }
 247
 248 TypePtr Expression::getType() {
 249   if (m_expectedType) return m_expectedType;
 250   if (m_actualType) return m_actualType;
 251   return Type::Any;
 252 }
 253
 254 TypePtr Expression::getGenType() {
 255   if (m_expectedType) return m_expectedType;
 256   if (m_implementedType) return m_implementedType;
 257   if (m_actualType) return m_actualType;
 258   return Type::Any;
 259 }
 260
 261 TypePtr Expression::getCPPType() {
 262   if (m_implementedType) return m_implementedType;
 263   if (m_actualType) return m_actualType;
 264   return Type::Variant;
 265 }
 266
 267 TypePtr Expression::propagateTypes(AnalysisResultConstPtr ar, TypePtr inType) {
 268   ExpressionPtr e = getCanonTypeInfPtr();
 269   TypePtr ret = inType;
 270
 271   while (e) {
 272     if (e->getAssertedType() && !getAssertedType()) {
 273       setAssertedType(e->getAssertedType());
 274     }
 275     TypePtr inferred = Type::Inferred(ar, ret, e->m_actualType);
 276     if (!inferred) {
 277       break;
 278     }
 279     ret = inferred;
 280     e = e->getCanonTypeInfPtr();
 281   }
 282
 283   return ret;
 284 }
 285
 286 void Expression::analyzeProgram(AnalysisResultPtr ar) {
 287 }
 288
 289 BlockScopeRawPtr Expression::getOriginalScope() {
 290   if (!m_originalScopeSet) {
 291     m_originalScopeSet = true;
 292     m_originalScope = getScope();
 293   }
 294   return m_originalScope;
 295 }
 296
 297 void Expression::setOriginalScope(BlockScopeRawPtr scope) {
 298   m_originalScope = scope;
 299   m_originalScopeSet = true;
 300 }
 301
 302 ClassScopeRawPtr Expression::getOriginalClass() {
 303   BlockScopeRawPtr scope = getOriginalScope();
 304   return scope ? scope->getContainingClass() : ClassScopeRawPtr();
 305 }
 306
 307 FunctionScopeRawPtr Expression::getOriginalFunction() {
 308   BlockScopeRawPtr scope = getOriginalScope();
 309   return scope ? scope->getContainingFunction() : FunctionScopeRawPtr();
 310 }
 311
 312 void Expression::resetTypes() {
 313   m_actualType     .reset();
 314   m_expectedType   .reset();
 315   m_implementedType.reset();
 316 }
 317
 318 TypePtr Expression::inferAndCheck(AnalysisResultPtr ar, TypePtr type,
 319                                   bool coerce) {
 320   IMPLEMENT_INFER_AND_CHECK_ASSERT(getScope());
 321   assert(type);
 322   resetTypes();
 323   TypePtr actualType = inferTypes(ar, type, coerce);
 324   if (type->is(Type::KindOfSome) || type->is(Type::KindOfAny)) {
 325     m_actualType = actualType;
 326     m_expectedType.reset();
 327     return actualType;
 328   }
 329   return checkTypesImpl(ar, type, actualType, coerce);
 330 }
 331
 332 TypePtr Expression::checkTypesImpl(AnalysisResultConstPtr ar,
 333                                    TypePtr expectedType,
 334                                    TypePtr actualType, bool coerce) {
 335   TypePtr ret;
 336   actualType = propagateTypes(ar, actualType);
 337   assert(actualType);
 338   if (coerce) {
 339     ret = Type::Coerce(ar, expectedType, actualType);
 340     setTypes(ar, actualType, expectedType);
 341   } else {
 342     ret = Type::Intersection(ar, actualType, expectedType);
 343     setTypes(ar, actualType, ret);
 344   }
 345   assert(ret);
 346   return ret;
 347 }
 348
 349 void Expression::setTypes(AnalysisResultConstPtr ar, TypePtr actualType,
 350                           TypePtr expectedType) {
 351   assert(actualType);
 352   assert(expectedType);
 353
 354   m_actualType = actualType;
 355   if (!expectedType->is(Type::KindOfAny) &&
 356       !expectedType->is(Type::KindOfSome)) {
 357     // store the expected type if it is not Any nor Some,
 358     // regardless of the actual type
 359     m_expectedType = expectedType;
 360   } else {
 361     m_expectedType.reset();
 362   }
 363
 364   // This is a special case where Type::KindOfObject means any object.
 365   if (m_expectedType && m_expectedType->is(Type::KindOfObject) &&
 366       !m_expectedType->isSpecificObject() &&
 367       m_actualType->isSpecificObject()) {
 368     m_expectedType.reset();
 369   }
 370
 371   if (m_actualType->isSpecificObject()) {
 372     boost::const_pointer_cast<AnalysisResult>(ar)->
 373       addClassDependency(getFileScope(), m_actualType->getName());
 374   }
 375 }
 376
 377 void Expression::setDynamicByIdentifier(AnalysisResultPtr ar,
 378                                         const std::string &value) {
 379   string id = Util::toLower(value);
 380   size_t c = id.find("::");
 381   FunctionScopePtr fi;
 382   ClassScopePtr ci;
 383   if (c != 0 && c != string::npos && c+2 < id.size()) {
 384     string cl = id.substr(0, c);
 385     string fn = id.substr(c+2);
 386     if (IsIdentifier(cl) && IsIdentifier(fn)) {
 387       ci = ar->findClass(cl);
 388       if (ci) {
 389         fi = ci->findFunction(ar, fn, false);
 390         if (fi) fi->setDynamic();
 391       }
 392     }
 393   } else if (IsIdentifier(id)) {
 394     fi = ar->findFunction(id);
 395     if (fi) fi->setDynamic();
 396     ClassScopePtr ci = ar->findClass(id, AnalysisResult::MethodName);
 397     if (ci) {
 398       fi = ci->findFunction(ar, id, false);
 399       if (fi) fi->setDynamic();
 400     }
 401   }
 402 }
 403
 404 bool Expression::CheckNeededRHS(ExpressionPtr value) {
 405   bool needed = true;
 406   always_assert(value);
 407   while (value->is(KindOfAssignmentExpression)) {
 408     value = dynamic_pointer_cast<AssignmentExpression>(value)->getValue();
 409   }
 410   if (value->isScalar()) {
 411     needed = false;
 412   } else {
 413     TypePtr type = value->getType();
 414     if (type && (type->is(Type::KindOfSome) || type->is(Type::KindOfAny))) {
 415       type = value->getActualType();
 416     }
 417     if (type && type->isNoObjectInvolved()) needed = false;
 418   }
 419   return needed;
 420 }
 421
 422 bool Expression::CheckNeeded(ExpressionPtr variable, ExpressionPtr value) {
 423   // if the value may involve object, consider the variable as "needed"
 424   // so that objects are not destructed prematurely.
 425   bool needed = true;
 426   if (value) needed = CheckNeededRHS(value);
 427   if (variable->is(Expression::KindOfSimpleVariable)) {
 428     SimpleVariablePtr var =
 429       dynamic_pointer_cast<SimpleVariable>(variable);
 430     const std::string &name = var->getName();
 431     VariableTablePtr variables = var->getScope()->getVariables();
 432     if (needed) {
 433       variables->addNeeded(name);
 434     } else {
 435       needed = variables->isNeeded(name);
 436     }
 437   }
 438   return needed;
 439 }
 440
 441 bool Expression::CheckVarNR(ExpressionPtr value,
 442                             TypePtr expectedType /* = TypePtr */) {
 443   if (!expectedType) expectedType = value->getExpectedType();
 444   return (!value->hasContext(Expression::RefValue) &&
 445           expectedType && expectedType->is(Type::KindOfVariant) &&
 446           (value->getCPPType()->is(Type::KindOfArray) ||
 447            value->getCPPType()->is(Type::KindOfString) ||
 448            value->getCPPType()->is(Type::KindOfObject) ||
 449            value->getCPPType()->isPrimitive() ||
 450            value->isScalar()));
 451 }
 452
 453 TypePtr Expression::inferAssignmentTypes(AnalysisResultPtr ar, TypePtr type,
 454                                          bool coerce, ExpressionPtr variable,
 455                                          ExpressionPtr
 456                                          value /* =ExpressionPtr() */) {
 457   assert(type);
 458   TypePtr ret = type;
 459   if (value) {
 460     ret = value->inferAndCheck(ar, Type::Some, false);
 461     if (value->isLiteralNull()) {
 462       ret = Type::Null;
 463     }
 464     assert(ret);
 465   }
 466
 467   BlockScopePtr scope = getScope();
 468   if (variable->is(Expression::KindOfConstantExpression)) {
 469     // ...as in ClassConstant statement
 470     ConstantExpressionPtr exp =
 471       dynamic_pointer_cast<ConstantExpression>(variable);
 472     BlockScope *defScope = nullptr;
 473     std::vector<std::string> bases;
 474     scope->getConstants()->check(getScope(), exp->getName(), ret,
 475                                  true, ar, variable,
 476                                  bases, defScope);
 477   }
 478
 479   m_implementedType.reset();
 480   TypePtr vt = variable->inferAndCheck(ar, ret, true);
 481   if (!coerce && type->is(Type::KindOfAny)) {
 482     ret = vt;
 483   } else {
 484     TypePtr it = variable->getCPPType();
 485     if (!Type::SameType(it, ret)) {
 486       m_implementedType = it;
 487     }
 488   }
 489
 490   if (value) {
 491     TypePtr vat(value->getActualType());
 492     TypePtr vet(value->getExpectedType());
 493     TypePtr vit(value->getImplementedType());
 494     if (vat && !vet && vit &&
 495         Type::IsMappedToVariant(vit) &&
 496         Type::HasFastCastMethod(vat)) {
 497       value->setExpectedType(vat);
 498     }
 499   }
 500
 501   return ret;
 502 }
 503
 504 ExpressionPtr Expression::MakeConstant(AnalysisResultConstPtr ar,
 505                                        BlockScopePtr scope,
 506                                        LocationPtr loc,
 507                                        const std::string &value) {
 508   ConstantExpressionPtr exp(new ConstantExpression(
 509                               scope, loc,
 510                               value, false));
 511   if (value == "true" || value == "false") {
 512     if (ar->getPhase() >= AnalysisResult::PostOptimize) {
 513       exp->m_actualType = Type::Boolean;
 514     }
 515   } else if (value == "null") {
 516     if (ar->getPhase() >= AnalysisResult::PostOptimize) {
 517       exp->m_actualType = Type::Variant;
 518     }
 519   } else {
 520     assert(false);
 521   }
 522   return exp;
 523 }
 524
 525 void Expression::CheckPassByReference(AnalysisResultPtr ar,
 526                                       ExpressionPtr param) {
 527   if (param->hasContext(Expression::RefValue) &&
 528       !param->isRefable(true)) {
 529     param->setError(Expression::BadPassByRef);
 530     Compiler::Error(Compiler::BadPassByReference, param);
 531   }
 532 }
 533
 534 unsigned Expression::getCanonHash() const {
 535   int64_t val = hash_int64(getKindOf());
 536   for (int i = getKidCount(); i--; ) {
 537     ExpressionPtr k = getNthExpr(i);
 538     if (k) {
 539       val = hash_int64(val ^ (((int64_t)k->getKindOf()<<32)+k->getCanonID()));
 540     }
 541   }
 542
 543   return (unsigned)val ^ (unsigned)(val >> 32);
 544 }
 545
 546 bool Expression::canonCompare(ExpressionPtr e) const {
 547   if (e->getKindOf() != getKindOf()) {
 548     return false;
 549   }
 550
 551   int kk = getKidCount();
 552   if (kk != e->getKidCount()) {
 553     return false;
 554   }
 555
 556   for (int i = kk; i--; ) {
 557     ExpressionPtr k1 = getNthExpr(i);
 558     ExpressionPtr k2 = e->getNthExpr(i);
 559
 560     if (k1 != k2) {
 561       if (!k1 || !k2) {
 562         return false;
 563       }
 564       if (k1->getCanonID() != k2->getCanonID()) {
 565         return false;
 566       }
 567     }
 568   }
 569
 570   return true;
 571 }
 572
 573 bool Expression::equals(ExpressionPtr other) {
 574   if (!other) return false;
 575
 576   // So that we can leverage canonCompare()
 577   setCanonID(0);
 578   other->setCanonID(0);
 579
 580   if (other->getKindOf() != getKindOf()) {
 581     return false;
 582   }
 583
 584   int nKids = getKidCount();
 585   if (nKids != other->getKidCount()) {
 586     return false;
 587   }
 588
 589   for (int i = 0; i < nKids; i++) {
 590     ExpressionPtr thisKid = getNthExpr(i);
 591     ExpressionPtr otherKid = other->getNthExpr(i);
 592
 593     if (!thisKid || !otherKid) {
 594       if (thisKid == otherKid) continue;
 595       return false;
 596     }
 597     if (!thisKid->equals(otherKid)) {
 598       return false;
 599     }
 600   }
 601
 602   return canonCompare(other);
 603 }
 604
 605 ExpressionPtr Expression::getCanonTypeInfPtr() const {
 606   if (!m_canonPtr) return ExpressionPtr();
 607   if (!(m_context & (LValue|RefValue|UnsetContext|DeepReference))) {
 608     return m_canonPtr;
 609   }
 610   if (!hasAnyContext(AccessContext|ObjectContext) ||
 611       !m_canonPtr->getActualType()) {
 612     return ExpressionPtr();
 613   }
 614   switch (m_canonPtr->getActualType()->getKindOf()) {
 615   case Type::KindOfArray:
 616     {
 617       if (!hasContext(AccessContext)) break;
 618       if (m_canonPtr->getAssertedType()) return m_canonPtr;
 619       if (!is(Expression::KindOfSimpleVariable)) break;
 620       SimpleVariableConstPtr sv(
 621         static_pointer_cast<const SimpleVariable>(shared_from_this()));
 622       if (sv->couldBeAliased()) return ExpressionPtr();
 623       if (hasContext(LValue) &&
 624           !(m_context & (RefValue | UnsetContext | DeepReference))) {
 625         return m_canonPtr;
 626       }
 627     }
 628     break;
 629   case Type::KindOfObject:
 630     {
 631       if (!hasContext(ObjectContext)) break;
 632       if (m_canonPtr->getAssertedType()) return m_canonPtr;
 633       if (!is(Expression::KindOfSimpleVariable)) break;
 634       SimpleVariableConstPtr sv(
 635         static_pointer_cast<const SimpleVariable>(shared_from_this()));
 636       if (sv->couldBeAliased()) return ExpressionPtr();
 637       if (hasContext(LValue) &&
 638           !(m_context & (RefValue | UnsetContext | DeepReference))) {
 639         return m_canonPtr;
 640       }
 641     }
 642   default:
 643     break;
 644   }
 645   return ExpressionPtr();
 646 }
 647
 648 ExpressionPtr Expression::fetchReplacement() {
 649   ExpressionPtr t = m_replacement;
 650   m_replacement.reset();
 651   return t;
 652 }
 653
 654 void Expression::computeLocalExprAltered() {
 655   // if no kids, do nothing
 656   if (getKidCount() == 0) return;
 657
 658   bool res = false;
 659   for (int i = 0; i < getKidCount(); i++) {
 660     ExpressionPtr k = getNthExpr(i);
 661     if (k) {
 662       k->computeLocalExprAltered();
 663       res |= k->isLocalExprAltered();
 664     }
 665   }
 666   if (res) {
 667     setLocalExprAltered();
 668   }
 669 }
 670
 671 bool Expression::isArray() const {
 672   if (is(KindOfUnaryOpExpression)) {
 673     return static_cast<const UnaryOpExpression*>(this)->getOp() == T_ARRAY;
 674   }
 675   return false;
 676 }
 677
 678 bool Expression::isUnquotedScalar() const {
 679   if (!is(KindOfScalarExpression)) return false;
 680   return !((ScalarExpression*)this)->isQuoted();
 681 }
 682
 683 ExpressionPtr Expression::MakeScalarExpression(AnalysisResultConstPtr ar,
 684                                                BlockScopePtr scope,
 685                                                LocationPtr loc,
 686                                                CVarRef value) {
 687   if (value.isArray()) {
 688     ExpressionListPtr el(new ExpressionList(scope, loc,
 689                                             ExpressionList::ListKindParam));
 690
 691     for (ArrayIter iter(value.toArray()); iter; ++iter) {
 692       ExpressionPtr k(MakeScalarExpression(ar, scope, loc, iter.first()));
 693       ExpressionPtr v(MakeScalarExpression(ar, scope, loc, iter.second()));
 694       if (!k || !v) return ExpressionPtr();
 695       ArrayPairExpressionPtr ap(
 696         new ArrayPairExpression(scope, loc, k, v, false));
 697       el->addElement(ap);
 698     }
 699     if (!el->getCount()) el.reset();
 700     return ExpressionPtr(
 701       new UnaryOpExpression(scope, loc, el, T_ARRAY, true));
 702   } else if (value.isNull()) {
 703     return MakeConstant(ar, scope, loc, "null");
 704   } else if (value.isBoolean()) {
 705     return MakeConstant(ar, scope, loc, value.toBoolean() ? "true" : "false");
 706   } else {
 707     return ScalarExpressionPtr
 708       (new ScalarExpression(scope, loc, value));
 709   }
 710 }
 711
 712 ///////////////////////////////////////////////////////////////////////////////
 713
 714 void Expression::collectCPPTemps(ExpressionPtrVec &collection) {
 715   if (isChainRoot()) {
 716     collection.push_back(static_pointer_cast<Expression>(shared_from_this()));
 717   } else {
 718     for (int i = 0; i < getKidCount(); i++) {
 719       ExpressionPtr kid = getNthExpr(i);
 720       if (kid) kid->collectCPPTemps(collection);
 721     }
 722   }
 723 }
 724
 725 void Expression::disableCSE() {
 726   ExpressionPtrVec v;
 727   collectCPPTemps(v);
 728   ExpressionPtrVec::iterator it(v.begin());
 729   for (; it != v.end(); ++it) {
 730     ExpressionPtr p(*it);
 731     p->clearChainRoot();
 732   }
 733 }
 734
 735 bool Expression::hasChainRoots() {
 736   ExpressionPtrVec v;
 737   collectCPPTemps(v);
 738   return !v.empty();
 739 }
 740
 741 bool Expression::GetCseTempInfo(
 742     AnalysisResultPtr ar,
 743     ExpressionPtr p,
 744     TypePtr &t) {
 745   assert(p);
 746   switch (p->getKindOf()) {
 747   case Expression::KindOfArrayElementExpression:
 748     {
 749       ArrayElementExpressionPtr ap(
 750           static_pointer_cast<ArrayElementExpression>(p));
 751       ExpressionPtr var(ap->getVariable());
 752
 753       TypePtr srcType, dstType;
 754       bool needsCast =
 755         var->getTypeCastPtrs(ar, srcType, dstType);
 756
 757       TypePtr testType(needsCast ? dstType : srcType);
 758       if (testType) {
 759         t = testType;
 760         return !testType->is(Type::KindOfArray);
 761       }
 762
 763       return true;
 764     }
 765     break;
 766   default:
 767     break;
 768   }
 769   return true;
 770 }
 771
 772 ExpressionPtr Expression::getNextCanonCsePtr() const {
 773
 774   bool dAccessCtx =
 775     hasContext(AccessContext);
 776   bool dLval =
 777     hasContext(LValue);
 778   bool dExistCtx =
 779     hasContext(ExistContext);
 780   bool dUnsetCtx =
 781     hasContext(UnsetContext);
 782
 783   bool dGlobals = false;
 784   if (is(KindOfArrayElementExpression)) {
 785     ArrayElementExpressionConstPtr a(
 786         static_pointer_cast<const ArrayElementExpression>(
 787           shared_from_this()));
 788     dGlobals = a->isSuperGlobal() || a->isDynamicGlobal();
 789   }
 790
 791   // see rules below - no hope to find CSE candidate
 792   if (dExistCtx || dUnsetCtx || dGlobals || (!dAccessCtx && dLval)) {
 793     return ExpressionPtr();
 794   }
 795
 796   KindOf dKindOf = getKindOf();
 797
 798   ExpressionPtr match;
 799   ExpressionPtr p(getCanonLVal());
 800   for (; p; p = p->getCanonLVal()) {
 801     // check if p is a suitable candidate for CSE of
 802     // downstream. the rules are:
 803     // A) rvals can always be CSE-ed regardless of access context,
 804     //    except for unset context, which it never can be CSE-ed for
 805     // B) lvals can only be CSE-ed if in AccessContext
 806     // C) rvals and lvals cannot be CSE-ed for each other
 807     // D) for now, ExistContext is not optimized
 808     // E) no CSE for $GLOBALS[...]
 809     // F) node types need to match
 810
 811     bool pLval = p->hasContext(LValue);
 812     KindOf pKindOf = p->getKindOf();
 813
 814     if (dKindOf != pKindOf) continue;
 815
 816     if (dLval) {
 817       assert(dAccessCtx);
 818       bool pAccessCtx = p->hasContext(AccessContext);
 819       if (pLval && pAccessCtx) {
 820         // match found
 821         match = p;
 822         break;
 823       }
 824     } else {
 825       bool pExistCtx = p->hasContext(ExistContext);
 826       bool pUnsetCtx = p->hasContext(UnsetContext);
 827       if (!pLval && !pExistCtx && !pUnsetCtx) {
 828         // match found
 829         match = p;
 830         break;
 831       }
 832     }
 833   }
 834
 835   return match;
 836 }
 837
 838 ExpressionPtr Expression::getCanonCsePtr() const {
 839   ExpressionPtr next(getNextCanonCsePtr());
 840   if (next) {
 841     if (next->isChainRoot()) return next;
 842     return next->getCanonCsePtr();
 843   }
 844   return ExpressionPtr();
 845 }
 846
 847 bool Expression::getTypeCastPtrs(
 848     AnalysisResultPtr ar, TypePtr &srcType, TypePtr &dstType) {
 849   srcType = m_actualType;
 850   dstType = m_expectedType;
 851   if (m_implementedType && srcType &&
 852       !Type::SameType(m_implementedType, srcType)) {
 853     srcType = m_implementedType;
 854   }
 855   if (!srcType && dstType && Type::IsCastNeeded(ar, Type::Variant, dstType)) {
 856     srcType = Type::Variant;
 857     return true;
 858   }
 859   return dstType && srcType && ((m_context & LValue) == 0) &&
 860       Type::IsCastNeeded(ar, srcType, dstType);
 861 }