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 35 namespace v8 { 36 namespace internal { 37 38 39 VariableProxySentinel VariableProxySentinel::this_proxy_(true); 40 VariableProxySentinel VariableProxySentinel::identifier_proxy_(false); 41 ValidLeftHandSideSentinel ValidLeftHandSideSentinel::instance_; 42 Property Property::this_property_(VariableProxySentinel::this_proxy(), NULL, 0); 43 Call 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 } 54 AST_NODE_LIST(DECL_ACCEPT) 55 #undef DECL_ACCEPT 56 57 58 // ---------------------------------------------------------------------------- 59 // Implementation of other node functionality. 60 61 VariableProxy::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 75 VariableProxy::VariableProxy(bool is_this) 76 : is_this_(is_this) { 77 } 78 79 80 void 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 95 Token::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 114 bool FunctionLiteral::AllowsLazyCompilation() { 115 return scope()->AllowsLazyCompilation(); 116 } 117 118 119 ObjectLiteral::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 135 ObjectLiteral::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 142 bool ObjectLiteral::Property::IsCompileTimeValue() { 143 return kind_ == CONSTANT || 144 (kind_ == MATERIALIZED_LITERAL && 145 CompileTimeValue::IsCompileTimeValue(value_)); 146 } 147 148 149 void TargetCollector::AddTarget(BreakTarget* target) { 150 // Add the label to the collector, but discard duplicates. 151 int length = targets_->length(); 152 for (int i = 0; i < length; i++) { 153 if (targets_->at(i) == target) return; 154 } 155 targets_->Add(target); 156 } 157 158 159 // ---------------------------------------------------------------------------- 160 // Implementation of AstVisitor 161 162 163 void AstVisitor::VisitDeclarations(ZoneList<Declaration*>* declarations) { 164 for (int i = 0; i < declarations->length(); i++) { 165 Visit(declarations->at(i)); 166 } 167 } 168 169 170 void AstVisitor::VisitStatements(ZoneList<Statement*>* statements) { 171 for (int i = 0; i < statements->length(); i++) { 172 Visit(statements->at(i)); 173 } 174 } 175 176 177 void AstVisitor::VisitExpressions(ZoneList<Expression*>* expressions) { 178 for (int i = 0; i < expressions->length(); i++) { 179 // The variable statement visiting code may pass NULL expressions 180 // to this code. Maybe this should be handled by introducing an 181 // undefined expression or literal? Revisit this code if this 182 // changes 183 Expression* expression = expressions->at(i); 184 if (expression != NULL) Visit(expression); 185 } 186 } 187 188 189 // ---------------------------------------------------------------------------- 190 // Regular expressions 191 192 #define MAKE_ACCEPT(Name) \ 193 void* RegExp##Name::Accept(RegExpVisitor* visitor, void* data) { \ 194 return visitor->Visit##Name(this, data); \ 195 } 196 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ACCEPT) 197 #undef MAKE_ACCEPT 198 199 #define MAKE_TYPE_CASE(Name) \ 200 RegExp##Name* RegExpTree::As##Name() { \ 201 return NULL; \ 202 } \ 203 bool RegExpTree::Is##Name() { return false; } 204 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 205 #undef MAKE_TYPE_CASE 206 207 #define MAKE_TYPE_CASE(Name) \ 208 RegExp##Name* RegExp##Name::As##Name() { \ 209 return this; \ 210 } \ 211 bool RegExp##Name::Is##Name() { return true; } 212 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_TYPE_CASE) 213 #undef MAKE_TYPE_CASE 214 215 RegExpEmpty RegExpEmpty::kInstance; 216 217 218 static Interval ListCaptureRegisters(ZoneList<RegExpTree*>* children) { 219 Interval result = Interval::Empty(); 220 for (int i = 0; i < children->length(); i++) 221 result = result.Union(children->at(i)->CaptureRegisters()); 222 return result; 223 } 224 225 226 Interval RegExpAlternative::CaptureRegisters() { 227 return ListCaptureRegisters(nodes()); 228 } 229 230 231 Interval RegExpDisjunction::CaptureRegisters() { 232 return ListCaptureRegisters(alternatives()); 233 } 234 235 236 Interval RegExpLookahead::CaptureRegisters() { 237 return body()->CaptureRegisters(); 238 } 239 240 241 Interval RegExpCapture::CaptureRegisters() { 242 Interval self(StartRegister(index()), EndRegister(index())); 243 return self.Union(body()->CaptureRegisters()); 244 } 245 246 247 Interval RegExpQuantifier::CaptureRegisters() { 248 return body()->CaptureRegisters(); 249 } 250 251 252 bool RegExpAssertion::IsAnchored() { 253 return type() == RegExpAssertion::START_OF_INPUT; 254 } 255 256 257 bool RegExpAlternative::IsAnchored() { 258 ZoneList<RegExpTree*>* nodes = this->nodes(); 259 for (int i = 0; i < nodes->length(); i++) { 260 RegExpTree* node = nodes->at(i); 261 if (node->IsAnchored()) { return true; } 262 if (node->max_match() > 0) { return false; } 263 } 264 return false; 265 } 266 267 268 bool RegExpDisjunction::IsAnchored() { 269 ZoneList<RegExpTree*>* alternatives = this->alternatives(); 270 for (int i = 0; i < alternatives->length(); i++) { 271 if (!alternatives->at(i)->IsAnchored()) 272 return false; 273 } 274 return true; 275 } 276 277 278 bool RegExpLookahead::IsAnchored() { 279 return is_positive() && body()->IsAnchored(); 280 } 281 282 283 bool RegExpCapture::IsAnchored() { 284 return body()->IsAnchored(); 285 } 286 287 288 // Convert regular expression trees to a simple sexp representation. 289 // This representation should be different from the input grammar 290 // in as many cases as possible, to make it more difficult for incorrect 291 // parses to look as correct ones which is likely if the input and 292 // output formats are alike. 293 class RegExpUnparser: public RegExpVisitor { 294 public: 295 RegExpUnparser(); 296 void VisitCharacterRange(CharacterRange that); 297 SmartPointer<const char> ToString() { return stream_.ToCString(); } 298 #define MAKE_CASE(Name) virtual void* Visit##Name(RegExp##Name*, void* data); 299 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE) 300 #undef MAKE_CASE 301 private: 302 StringStream* stream() { return &stream_; } 303 HeapStringAllocator alloc_; 304 StringStream stream_; 305 }; 306 307 308 RegExpUnparser::RegExpUnparser() : stream_(&alloc_) { 309 } 310 311 312 void* RegExpUnparser::VisitDisjunction(RegExpDisjunction* that, void* data) { 313 stream()->Add("(|"); 314 for (int i = 0; i < that->alternatives()->length(); i++) { 315 stream()->Add(" "); 316 that->alternatives()->at(i)->Accept(this, data); 317 } 318 stream()->Add(")"); 319 return NULL; 320 } 321 322 323 void* RegExpUnparser::VisitAlternative(RegExpAlternative* that, void* data) { 324 stream()->Add("(:"); 325 for (int i = 0; i < that->nodes()->length(); i++) { 326 stream()->Add(" "); 327 that->nodes()->at(i)->Accept(this, data); 328 } 329 stream()->Add(")"); 330 return NULL; 331 } 332 333 334 void RegExpUnparser::VisitCharacterRange(CharacterRange that) { 335 stream()->Add("%k", that.from()); 336 if (!that.IsSingleton()) { 337 stream()->Add("-%k", that.to()); 338 } 339 } 340 341 342 343 void* RegExpUnparser::VisitCharacterClass(RegExpCharacterClass* that, 344 void* data) { 345 if (that->is_negated()) 346 stream()->Add("^"); 347 stream()->Add("["); 348 for (int i = 0; i < that->ranges()->length(); i++) { 349 if (i > 0) stream()->Add(" "); 350 VisitCharacterRange(that->ranges()->at(i)); 351 } 352 stream()->Add("]"); 353 return NULL; 354 } 355 356 357 void* RegExpUnparser::VisitAssertion(RegExpAssertion* that, void* data) { 358 switch (that->type()) { 359 case RegExpAssertion::START_OF_INPUT: 360 stream()->Add("@^i"); 361 break; 362 case RegExpAssertion::END_OF_INPUT: 363 stream()->Add("@$i"); 364 break; 365 case RegExpAssertion::START_OF_LINE: 366 stream()->Add("@^l"); 367 break; 368 case RegExpAssertion::END_OF_LINE: 369 stream()->Add("@$l"); 370 break; 371 case RegExpAssertion::BOUNDARY: 372 stream()->Add("@b"); 373 break; 374 case RegExpAssertion::NON_BOUNDARY: 375 stream()->Add("@B"); 376 break; 377 } 378 return NULL; 379 } 380 381 382 void* RegExpUnparser::VisitAtom(RegExpAtom* that, void* data) { 383 stream()->Add("'"); 384 Vector<const uc16> chardata = that->data(); 385 for (int i = 0; i < chardata.length(); i++) { 386 stream()->Add("%k", chardata[i]); 387 } 388 stream()->Add("'"); 389 return NULL; 390 } 391 392 393 void* RegExpUnparser::VisitText(RegExpText* that, void* data) { 394 if (that->elements()->length() == 1) { 395 that->elements()->at(0).data.u_atom->Accept(this, data); 396 } else { 397 stream()->Add("(!"); 398 for (int i = 0; i < that->elements()->length(); i++) { 399 stream()->Add(" "); 400 that->elements()->at(i).data.u_atom->Accept(this, data); 401 } 402 stream()->Add(")"); 403 } 404 return NULL; 405 } 406 407 408 void* RegExpUnparser::VisitQuantifier(RegExpQuantifier* that, void* data) { 409 stream()->Add("(# %i ", that->min()); 410 if (that->max() == RegExpTree::kInfinity) { 411 stream()->Add("- "); 412 } else { 413 stream()->Add("%i ", that->max()); 414 } 415 stream()->Add(that->is_greedy() ? "g " : that->is_possessive() ? "p " : "n "); 416 that->body()->Accept(this, data); 417 stream()->Add(")"); 418 return NULL; 419 } 420 421 422 void* RegExpUnparser::VisitCapture(RegExpCapture* that, void* data) { 423 stream()->Add("(^ "); 424 that->body()->Accept(this, data); 425 stream()->Add(")"); 426 return NULL; 427 } 428 429 430 void* RegExpUnparser::VisitLookahead(RegExpLookahead* that, void* data) { 431 stream()->Add("(-> "); 432 stream()->Add(that->is_positive() ? "+ " : "- "); 433 that->body()->Accept(this, data); 434 stream()->Add(")"); 435 return NULL; 436 } 437 438 439 void* RegExpUnparser::VisitBackReference(RegExpBackReference* that, 440 void* data) { 441 stream()->Add("(<- %i)", that->index()); 442 return NULL; 443 } 444 445 446 void* RegExpUnparser::VisitEmpty(RegExpEmpty* that, void* data) { 447 stream()->Put('%'); 448 return NULL; 449 } 450 451 452 SmartPointer<const char> RegExpTree::ToString() { 453 RegExpUnparser unparser; 454 Accept(&unparser, NULL); 455 return unparser.ToString(); 456 } 457 458 459 RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) 460 : alternatives_(alternatives) { 461 ASSERT(alternatives->length() > 1); 462 RegExpTree* first_alternative = alternatives->at(0); 463 min_match_ = first_alternative->min_match(); 464 max_match_ = first_alternative->max_match(); 465 for (int i = 1; i < alternatives->length(); i++) { 466 RegExpTree* alternative = alternatives->at(i); 467 min_match_ = Min(min_match_, alternative->min_match()); 468 max_match_ = Max(max_match_, alternative->max_match()); 469 } 470 } 471 472 473 RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes) 474 : nodes_(nodes) { 475 ASSERT(nodes->length() > 1); 476 min_match_ = 0; 477 max_match_ = 0; 478 for (int i = 0; i < nodes->length(); i++) { 479 RegExpTree* node = nodes->at(i); 480 min_match_ += node->min_match(); 481 int node_max_match = node->max_match(); 482 if (kInfinity - max_match_ < node_max_match) { 483 max_match_ = kInfinity; 484 } else { 485 max_match_ += node->max_match(); 486 } 487 } 488 } 489 490 491 } } // namespace v8::internal 492