ast.cc revision e46be819fca9468a0cd4e74859ce0f778eb8ca60
1// Copyright 2006-2008 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#include "v8.h" 29 30#include "ast.h" 31#include "parser.h" 32#include "scopes.h" 33#include "string-stream.h" 34 35namespace v8 { 36namespace internal { 37 38 39VariableProxySentinel VariableProxySentinel::this_proxy_(true); 40VariableProxySentinel VariableProxySentinel::identifier_proxy_(false); 41ValidLeftHandSideSentinel ValidLeftHandSideSentinel::instance_; 42Property Property::this_property_(VariableProxySentinel::this_proxy(), NULL, 0); 43Call Call::sentinel_(NULL, NULL, 0); 44 45 46// ---------------------------------------------------------------------------- 47// All the Accept member functions for each syntax tree node type. 48 49#define DECL_ACCEPT(type) \ 50 void type::Accept(AstVisitor* v) { \ 51 if (v->CheckStackOverflow()) return; \ 52 v->Visit##type(this); \ 53 } 54AST_NODE_LIST(DECL_ACCEPT) 55#undef DECL_ACCEPT 56 57 58// ---------------------------------------------------------------------------- 59// Implementation of other node functionality. 60 61VariableProxy::VariableProxy(Handle<String> name, 62 bool is_this, 63 bool inside_with) 64 : name_(name), 65 var_(NULL), 66 is_this_(is_this), 67 inside_with_(inside_with) { 68 // names must be canonicalized for fast equality checks 69 ASSERT(name->IsSymbol()); 70 // at least one access, otherwise no need for a VariableProxy 71 var_uses_.RecordRead(1); 72} 73 74 75VariableProxy::VariableProxy(bool is_this) 76 : is_this_(is_this) { 77} 78 79 80void VariableProxy::BindTo(Variable* var) { 81 ASSERT(var_ == NULL); // must be bound only once 82 ASSERT(var != NULL); // must bind 83 ASSERT((is_this() && var->is_this()) || name_.is_identical_to(var->name())); 84 // Ideally CONST-ness should match. However, this is very hard to achieve 85 // because we don't know the exact semantics of conflicting (const and 86 // non-const) multiple variable declarations, const vars introduced via 87 // eval() etc. Const-ness and variable declarations are a complete mess 88 // in JS. Sigh... 89 var_ = var; 90 var->var_uses()->RecordUses(&var_uses_); 91 var->obj_uses()->RecordUses(&obj_uses_); 92} 93 94 95Token::Value Assignment::binary_op() const { 96 switch (op_) { 97 case Token::ASSIGN_BIT_OR: return Token::BIT_OR; 98 case Token::ASSIGN_BIT_XOR: return Token::BIT_XOR; 99 case Token::ASSIGN_BIT_AND: return Token::BIT_AND; 100 case Token::ASSIGN_SHL: return Token::SHL; 101 case Token::ASSIGN_SAR: return Token::SAR; 102 case Token::ASSIGN_SHR: return Token::SHR; 103 case Token::ASSIGN_ADD: return Token::ADD; 104 case Token::ASSIGN_SUB: return Token::SUB; 105 case Token::ASSIGN_MUL: return Token::MUL; 106 case Token::ASSIGN_DIV: return Token::DIV; 107 case Token::ASSIGN_MOD: return Token::MOD; 108 default: UNREACHABLE(); 109 } 110 return Token::ILLEGAL; 111} 112 113 114bool FunctionLiteral::AllowsLazyCompilation() { 115 return scope()->AllowsLazyCompilation(); 116} 117 118 119ObjectLiteral::Property::Property(Literal* key, Expression* value) { 120 key_ = key; 121 value_ = value; 122 Object* k = *key->handle(); 123 if (k->IsSymbol() && Heap::Proto_symbol()->Equals(String::cast(k))) { 124 kind_ = PROTOTYPE; 125 } else if (value_->AsMaterializedLiteral() != NULL) { 126 kind_ = MATERIALIZED_LITERAL; 127 } else if (value_->AsLiteral() != NULL) { 128 kind_ = CONSTANT; 129 } else { 130 kind_ = COMPUTED; 131 } 132} 133 134 135ObjectLiteral::Property::Property(bool is_getter, FunctionLiteral* value) { 136 key_ = new Literal(value->name()); 137 value_ = value; 138 kind_ = is_getter ? GETTER : SETTER; 139} 140 141 142bool ObjectLiteral::Property::IsCompileTimeValue() { 143 return kind_ == CONSTANT || 144 (kind_ == MATERIALIZED_LITERAL && 145 CompileTimeValue::IsCompileTimeValue(value_)); 146} 147 148 149bool ObjectLiteral::IsValidJSON() { 150 int length = properties()->length(); 151 for (int i = 0; i < length; i++) { 152 Property* prop = properties()->at(i); 153 if (!prop->value()->IsValidJSON()) 154 return false; 155 } 156 return true; 157} 158 159 160bool ArrayLiteral::IsValidJSON() { 161 int length = values()->length(); 162 for (int i = 0; i < length; i++) { 163 if (!values()->at(i)->IsValidJSON()) 164 return false; 165 } 166 return true; 167} 168 169 170void TargetCollector::AddTarget(BreakTarget* target) { 171 // Add the label to the collector, but discard duplicates. 172 int length = targets_->length(); 173 for (int i = 0; i < length; i++) { 174 if (targets_->at(i) == target) return; 175 } 176 targets_->Add(target); 177} 178 179 180// ---------------------------------------------------------------------------- 181// Implementation of AstVisitor 182 183 184void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) { 185 for (int i = 0; i < declarations->length(); i++) { 186 Visit(declarations->at(i)); 187 } 188} 189 190 191void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) { 192 for (int i = 0; i < statements->length(); i++) { 193 Visit(statements->at(i)); 194 } 195} 196 197 198void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) { 199 for (int i = 0; i < expressions->length(); i++) { 200 // The variable statement visiting code may pass NULL expressions 201 // to this code. Maybe this should be handled by introducing an 202 // undefined expression or literal? Revisit this code if this 203 // changes 204 Expression* expression = expressions->at(i); 205 if (expression != NULL) Visit(expression); 206 } 207} 208 209 210// ---------------------------------------------------------------------------- 211// Regular expressions 212 213#define MAKE_ACCEPT(Name) \ 214 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ 215 return visitor->Visit##Name(this, data); \ 216 } 217FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) 218#undef MAKE_ACCEPT 219 220#define MAKE_TYPE_CASE(Name) \ 221 RegExp##Name* RegExpTree::As##Name() { \ 222 return NULL; \ 223 } \ 224 bool RegExpTree::Is##Name() { return false; } 225FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 226#undef MAKE_TYPE_CASE 227 228#define MAKE_TYPE_CASE(Name) \ 229 RegExp##Name* RegExp##Name::As##Name() { \ 230 return this; \ 231 } \ 232 bool RegExp##Name::Is##Name() { return true; } 233FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 234#undef MAKE_TYPE_CASE 235 236RegExpEmpty RegExpEmpty::kInstance; 237 238 239static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) { 240 Interval result = Interval::Empty(); 241 for (int i = 0; i < children->length(); i++) 242 result = result.Union(children->at(i)->CaptureRegisters()); 243 return result; 244} 245 246 247Interval RegExpAlternative::CaptureRegisters() { 248 return ListCaptureRegisters(nodes()); 249} 250 251 252Interval RegExpDisjunction::CaptureRegisters() { 253 return ListCaptureRegisters(alternatives()); 254} 255 256 257Interval RegExpLookahead::CaptureRegisters() { 258 return body()->CaptureRegisters(); 259} 260 261 262Interval RegExpCapture::CaptureRegisters() { 263 Interval self(StartRegister(index()), EndRegister(index())); 264 return self.Union(body()->CaptureRegisters()); 265} 266 267 268Interval RegExpQuantifier::CaptureRegisters() { 269 return body()->CaptureRegisters(); 270} 271 272 273bool RegExpAssertion::IsAnchored() { 274 return type() == RegExpAssertion::START_OF_INPUT; 275} 276 277 278bool RegExpAlternative::IsAnchored() { 279 ZoneList<RegExpTree*>* nodes = this->nodes(); 280 for (int i = 0; i < nodes->length(); i++) { 281 RegExpTree* node = nodes->at(i); 282 if (node->IsAnchored()) { return true; } 283 if (node->max_match() > 0) { return false; } 284 } 285 return false; 286} 287 288 289bool RegExpDisjunction::IsAnchored() { 290 ZoneList<RegExpTree*>* alternatives = this->alternatives(); 291 for (int i = 0; i < alternatives->length(); i++) { 292 if (!alternatives->at(i)->IsAnchored()) 293 return false; 294 } 295 return true; 296} 297 298 299bool RegExpLookahead::IsAnchored() { 300 return is_positive() && body()->IsAnchored(); 301} 302 303 304bool RegExpCapture::IsAnchored() { 305 return body()->IsAnchored(); 306} 307 308 309// Convert regular expression trees to a simple sexp representation. 310// This representation should be different from the input grammar 311// in as many cases as possible, to make it more difficult for incorrect 312// parses to look as correct ones which is likely if the input and 313// output formats are alike. 314class RegExpUnparser: public RegExpVisitor { 315 public: 316 RegExpUnparser(); 317 void VisitCharacterRange(CharacterRange that); 318 SmartPointer<const char> ToString() { return stream_.ToCString(); } 319#define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data); 320 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) 321#undef MAKE_CASE 322 private: 323 StringStream* stream() { return &stream_; } 324 HeapStringAllocator alloc_; 325 StringStream stream_; 326}; 327 328 329RegExpUnparser::RegExpUnparser() : stream_(&alloc_) { 330} 331 332 333void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { 334 stream()->Add("(|"); 335 for (int i = 0; i < that->alternatives()->length(); i++) { 336 stream()->Add(" "); 337 that->alternatives()->at(i)->Accept(this, data); 338 } 339 stream()->Add(")"); 340 return NULL; 341} 342 343 344void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { 345 stream()->Add("(:"); 346 for (int i = 0; i < that->nodes()->length(); i++) { 347 stream()->Add(" "); 348 that->nodes()->at(i)->Accept(this, data); 349 } 350 stream()->Add(")"); 351 return NULL; 352} 353 354 355void RegExpUnparser::VisitCharacterRange(CharacterRange that) { 356 stream()->Add("%k", that.from()); 357 if (!that.IsSingleton()) { 358 stream()->Add("-%k", that.to()); 359 } 360} 361 362 363 364void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, 365 void* data) { 366 if (that->is_negated()) 367 stream()->Add("^"); 368 stream()->Add("["); 369 for (int i = 0; i < that->ranges()->length(); i++) { 370 if (i > 0) stream()->Add(" "); 371 VisitCharacterRange(that->ranges()->at(i)); 372 } 373 stream()->Add("]"); 374 return NULL; 375} 376 377 378void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { 379 switch (that->type()) { 380 case RegExpAssertion::START_OF_INPUT: 381 stream()->Add("@^i"); 382 break; 383 case RegExpAssertion::END_OF_INPUT: 384 stream()->Add("@$i"); 385 break; 386 case RegExpAssertion::START_OF_LINE: 387 stream()->Add("@^l"); 388 break; 389 case RegExpAssertion::END_OF_LINE: 390 stream()->Add("@$l"); 391 break; 392 case RegExpAssertion::BOUNDARY: 393 stream()->Add("@b"); 394 break; 395 case RegExpAssertion::NON_BOUNDARY: 396 stream()->Add("@B"); 397 break; 398 } 399 return NULL; 400} 401 402 403void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) { 404 stream()->Add("'"); 405 Vector<const uc16> chardata = that->data(); 406 for (int i = 0; i < chardata.length(); i++) { 407 stream()->Add("%k", chardata[i]); 408 } 409 stream()->Add("'"); 410 return NULL; 411} 412 413 414void* RegExpUnparser::VisitText(RegExpText* that, void* data) { 415 if (that->elements()->length() == 1) { 416 that->elements()->at(0).data.u_atom->Accept(this, data); 417 } else { 418 stream()->Add("(!"); 419 for (int i = 0; i < that->elements()->length(); i++) { 420 stream()->Add(" "); 421 that->elements()->at(i).data.u_atom->Accept(this, data); 422 } 423 stream()->Add(")"); 424 } 425 return NULL; 426} 427 428 429void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) { 430 stream()->Add("(# %i ", that->min()); 431 if (that->max() == RegExpTree::kInfinity) { 432 stream()->Add("- "); 433 } else { 434 stream()->Add("%i ", that->max()); 435 } 436 stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n "); 437 that->body()->Accept(this, data); 438 stream()->Add(")"); 439 return NULL; 440} 441 442 443void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { 444 stream()->Add("(^ "); 445 that->body()->Accept(this, data); 446 stream()->Add(")"); 447 return NULL; 448} 449 450 451void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { 452 stream()->Add("(-> "); 453 stream()->Add(that->is_positive() ? "+ " : "- "); 454 that->body()->Accept(this, data); 455 stream()->Add(")"); 456 return NULL; 457} 458 459 460void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, 461 void* data) { 462 stream()->Add("(<- %i)", that->index()); 463 return NULL; 464} 465 466 467void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) { 468 stream()->Put('%'); 469 return NULL; 470} 471 472 473SmartPointer<const char> RegExpTree::ToString() { 474 RegExpUnparser unparser; 475 Accept(&unparser, NULL); 476 return unparser.ToString(); 477} 478 479 480RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) 481 : alternatives_(alternatives) { 482 ASSERT(alternatives->length() > 1); 483 RegExpTree* first_alternative = alternatives->at(0); 484 min_match_ = first_alternative->min_match(); 485 max_match_ = first_alternative->max_match(); 486 for (int i = 1; i < alternatives->length(); i++) { 487 RegExpTree* alternative = alternatives->at(i); 488 min_match_ = Min(min_match_, alternative->min_match()); 489 max_match_ = Max(max_match_, alternative->max_match()); 490 } 491} 492 493 494RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes) 495 : nodes_(nodes) { 496 ASSERT(nodes->length() > 1); 497 min_match_ = 0; 498 max_match_ = 0; 499 for (int i = 0; i < nodes->length(); i++) { 500 RegExpTree* node = nodes->at(i); 501 min_match_ += node->min_match(); 502 int node_max_match = node->max_match(); 503 if (kInfinity - max_match_ < node_max_match) { 504 max_match_ = kInfinity; 505 } else { 506 max_match_ += node->max_match(); 507 } 508 } 509} 510 511 512} } // namespace v8::internal 513