OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1198 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1209 | 1209 |
1210 // ---------------------------------------------------------------------------- | 1210 // ---------------------------------------------------------------------------- |
1211 // Regular expressions | 1211 // Regular expressions |
1212 | 1212 |
1213 | 1213 |
1214 class RegExpTree: public ZoneObject { | 1214 class RegExpTree: public ZoneObject { |
1215 public: | 1215 public: |
1216 virtual ~RegExpTree() { } | 1216 virtual ~RegExpTree() { } |
1217 virtual void* Accept(RegExpVisitor* visitor, void* data) = 0; | 1217 virtual void* Accept(RegExpVisitor* visitor, void* data) = 0; |
1218 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1218 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1219 RegExpNode* on_success, | 1219 RegExpNode* on_success) = 0; |
1220 RegExpNode* on_failure) = 0; | |
1221 virtual bool IsTextElement() { return false; } | 1220 virtual bool IsTextElement() { return false; } |
1222 virtual void AppendToText(RegExpText* text); | 1221 virtual void AppendToText(RegExpText* text); |
1223 SmartPointer<const char> ToString(); | 1222 SmartPointer<const char> ToString(); |
1224 #define MAKE_ASTYPE(Name) \ | 1223 #define MAKE_ASTYPE(Name) \ |
1225 virtual RegExp##Name* As##Name(); \ | 1224 virtual RegExp##Name* As##Name(); \ |
1226 virtual bool Is##Name(); | 1225 virtual bool Is##Name(); |
1227 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE) | 1226 FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE) |
1228 #undef MAKE_ASTYPE | 1227 #undef MAKE_ASTYPE |
1229 }; | 1228 }; |
1230 | 1229 |
1231 | 1230 |
1232 class RegExpDisjunction: public RegExpTree { | 1231 class RegExpDisjunction: public RegExpTree { |
1233 public: | 1232 public: |
1234 explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) | 1233 explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives) |
1235 : alternatives_(alternatives) { } | 1234 : alternatives_(alternatives) { } |
1236 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1235 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1237 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1236 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1238 RegExpNode* on_success, | 1237 RegExpNode* on_success); |
1239 RegExpNode* on_failure); | |
1240 virtual RegExpDisjunction* AsDisjunction(); | 1238 virtual RegExpDisjunction* AsDisjunction(); |
1241 virtual bool IsDisjunction(); | 1239 virtual bool IsDisjunction(); |
1242 ZoneList<RegExpTree*>* alternatives() { return alternatives_; } | 1240 ZoneList<RegExpTree*>* alternatives() { return alternatives_; } |
1243 private: | 1241 private: |
1244 ZoneList<RegExpTree*>* alternatives_; | 1242 ZoneList<RegExpTree*>* alternatives_; |
1245 }; | 1243 }; |
1246 | 1244 |
1247 | 1245 |
1248 class RegExpAlternative: public RegExpTree { | 1246 class RegExpAlternative: public RegExpTree { |
1249 public: | 1247 public: |
1250 explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes) : nodes_(nodes) { } | 1248 explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes) : nodes_(nodes) { } |
1251 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1249 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1252 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1250 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1253 RegExpNode* on_success, | 1251 RegExpNode* on_success); |
1254 RegExpNode* on_failure); | |
1255 virtual RegExpAlternative* AsAlternative(); | 1252 virtual RegExpAlternative* AsAlternative(); |
1256 virtual bool IsAlternative(); | 1253 virtual bool IsAlternative(); |
1257 ZoneList<RegExpTree*>* nodes() { return nodes_; } | 1254 ZoneList<RegExpTree*>* nodes() { return nodes_; } |
1258 private: | 1255 private: |
1259 ZoneList<RegExpTree*>* nodes_; | 1256 ZoneList<RegExpTree*>* nodes_; |
1260 }; | 1257 }; |
1261 | 1258 |
1262 | 1259 |
1263 class RegExpText: public RegExpTree { | 1260 class RegExpText: public RegExpTree { |
1264 public: | 1261 public: |
1265 RegExpText() : elements_(2) { } | 1262 RegExpText() : elements_(2) { } |
1266 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1263 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1267 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1264 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1268 RegExpNode* on_success, | 1265 RegExpNode* on_success); |
1269 RegExpNode* on_failure); | |
1270 virtual RegExpText* AsText(); | 1266 virtual RegExpText* AsText(); |
1271 virtual bool IsText(); | 1267 virtual bool IsText(); |
1272 virtual bool IsTextElement() { return true; } | 1268 virtual bool IsTextElement() { return true; } |
1273 virtual void AppendToText(RegExpText* text); | 1269 virtual void AppendToText(RegExpText* text); |
1274 void AddElement(TextElement elm) { elements_.Add(elm); } | 1270 void AddElement(TextElement elm) { elements_.Add(elm); } |
1275 ZoneList<TextElement>* elements() { return &elements_; } | 1271 ZoneList<TextElement>* elements() { return &elements_; } |
1276 private: | 1272 private: |
1277 ZoneList<TextElement> elements_; | 1273 ZoneList<TextElement> elements_; |
1278 }; | 1274 }; |
1279 | 1275 |
1280 | 1276 |
1281 class RegExpAssertion: public RegExpTree { | 1277 class RegExpAssertion: public RegExpTree { |
1282 public: | 1278 public: |
1283 enum Type { | 1279 enum Type { |
1284 START_OF_LINE, | 1280 START_OF_LINE, |
1285 START_OF_INPUT, | 1281 START_OF_INPUT, |
1286 END_OF_LINE, | 1282 END_OF_LINE, |
1287 END_OF_INPUT, | 1283 END_OF_INPUT, |
1288 BOUNDARY, | 1284 BOUNDARY, |
1289 NON_BOUNDARY | 1285 NON_BOUNDARY |
1290 }; | 1286 }; |
1291 explicit RegExpAssertion(Type type) : type_(type) { } | 1287 explicit RegExpAssertion(Type type) : type_(type) { } |
1292 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1288 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1293 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1289 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1294 RegExpNode* on_success, | 1290 RegExpNode* on_success); |
1295 RegExpNode* on_failure); | |
1296 virtual RegExpAssertion* AsAssertion(); | 1291 virtual RegExpAssertion* AsAssertion(); |
1297 virtual bool IsAssertion(); | 1292 virtual bool IsAssertion(); |
1298 Type type() { return type_; } | 1293 Type type() { return type_; } |
1299 private: | 1294 private: |
1300 Type type_; | 1295 Type type_; |
1301 }; | 1296 }; |
1302 | 1297 |
1303 | 1298 |
1304 class RegExpCharacterClass: public RegExpTree { | 1299 class RegExpCharacterClass: public RegExpTree { |
1305 public: | 1300 public: |
1306 RegExpCharacterClass(ZoneList<CharacterRange>* ranges, bool is_negated) | 1301 RegExpCharacterClass(ZoneList<CharacterRange>* ranges, bool is_negated) |
1307 : ranges_(ranges), | 1302 : ranges_(ranges), |
1308 is_negated_(is_negated) { } | 1303 is_negated_(is_negated) { } |
1309 explicit RegExpCharacterClass(uc16 type) | 1304 explicit RegExpCharacterClass(uc16 type) |
1310 : ranges_(new ZoneList<CharacterRange>(2)), | 1305 : ranges_(new ZoneList<CharacterRange>(2)), |
1311 is_negated_(false) { | 1306 is_negated_(false) { |
1312 CharacterRange::AddClassEscape(type, ranges_); | 1307 CharacterRange::AddClassEscape(type, ranges_); |
1313 } | 1308 } |
1314 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1309 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1315 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1310 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1316 RegExpNode* on_success, | 1311 RegExpNode* on_success); |
1317 RegExpNode* on_failure); | |
1318 virtual RegExpCharacterClass* AsCharacterClass(); | 1312 virtual RegExpCharacterClass* AsCharacterClass(); |
1319 virtual bool IsCharacterClass(); | 1313 virtual bool IsCharacterClass(); |
1320 virtual bool IsTextElement() { return true; } | 1314 virtual bool IsTextElement() { return true; } |
1321 virtual void AppendToText(RegExpText* text); | 1315 virtual void AppendToText(RegExpText* text); |
1322 ZoneList<CharacterRange>* ranges() { return ranges_; } | 1316 ZoneList<CharacterRange>* ranges() { return ranges_; } |
1323 bool is_negated() { return is_negated_; } | 1317 bool is_negated() { return is_negated_; } |
1324 private: | 1318 private: |
1325 ZoneList<CharacterRange>* ranges_; | 1319 ZoneList<CharacterRange>* ranges_; |
1326 bool is_negated_; | 1320 bool is_negated_; |
1327 }; | 1321 }; |
1328 | 1322 |
1329 | 1323 |
1330 class RegExpAtom: public RegExpTree { | 1324 class RegExpAtom: public RegExpTree { |
1331 public: | 1325 public: |
1332 explicit RegExpAtom(Vector<const uc16> data) : data_(data) { } | 1326 explicit RegExpAtom(Vector<const uc16> data) : data_(data) { } |
1333 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1327 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1334 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1328 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1335 RegExpNode* on_success, | 1329 RegExpNode* on_success); |
1336 RegExpNode* on_failure); | |
1337 virtual RegExpAtom* AsAtom(); | 1330 virtual RegExpAtom* AsAtom(); |
1338 virtual bool IsAtom(); | 1331 virtual bool IsAtom(); |
1339 virtual bool IsTextElement() { return true; } | 1332 virtual bool IsTextElement() { return true; } |
1340 virtual void AppendToText(RegExpText* text); | 1333 virtual void AppendToText(RegExpText* text); |
1341 Vector<const uc16> data() { return data_; } | 1334 Vector<const uc16> data() { return data_; } |
1342 private: | 1335 private: |
1343 Vector<const uc16> data_; | 1336 Vector<const uc16> data_; |
1344 }; | 1337 }; |
1345 | 1338 |
1346 | 1339 |
1347 class RegExpQuantifier: public RegExpTree { | 1340 class RegExpQuantifier: public RegExpTree { |
1348 public: | 1341 public: |
1349 RegExpQuantifier(int min, int max, bool is_greedy, RegExpTree* body) | 1342 RegExpQuantifier(int min, int max, bool is_greedy, RegExpTree* body) |
1350 : min_(min), | 1343 : min_(min), |
1351 max_(max), | 1344 max_(max), |
1352 is_greedy_(is_greedy), | 1345 is_greedy_(is_greedy), |
1353 body_(body) { } | 1346 body_(body) { } |
1354 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1347 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1355 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1348 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1356 RegExpNode* on_success, | 1349 RegExpNode* on_success); |
1357 RegExpNode* on_failure); | |
1358 static RegExpNode* ToNode(int min, | 1350 static RegExpNode* ToNode(int min, |
1359 int max, | 1351 int max, |
1360 bool is_greedy, | 1352 bool is_greedy, |
1361 RegExpTree* body, | 1353 RegExpTree* body, |
1362 RegExpCompiler* compiler, | 1354 RegExpCompiler* compiler, |
1363 RegExpNode* on_success, | 1355 RegExpNode* on_success); |
1364 RegExpNode* on_failure); | |
1365 virtual RegExpQuantifier* AsQuantifier(); | 1356 virtual RegExpQuantifier* AsQuantifier(); |
1366 virtual bool IsQuantifier(); | 1357 virtual bool IsQuantifier(); |
1367 int min() { return min_; } | 1358 int min() { return min_; } |
1368 int max() { return max_; } | 1359 int max() { return max_; } |
1369 bool is_greedy() { return is_greedy_; } | 1360 bool is_greedy() { return is_greedy_; } |
1370 RegExpTree* body() { return body_; } | 1361 RegExpTree* body() { return body_; } |
1371 // We just use a very large integer value as infinity because 2^30 | 1362 // We just use a very large integer value as infinity because 2^30 |
1372 // is infinite in practice. | 1363 // is infinite in practice. |
1373 static const int kInfinity = (1 << 30); | 1364 static const int kInfinity = (1 << 30); |
1374 private: | 1365 private: |
1375 int min_; | 1366 int min_; |
1376 int max_; | 1367 int max_; |
1377 bool is_greedy_; | 1368 bool is_greedy_; |
1378 RegExpTree* body_; | 1369 RegExpTree* body_; |
1379 }; | 1370 }; |
1380 | 1371 |
1381 | 1372 |
1382 enum CaptureAvailability { | 1373 enum CaptureAvailability { |
1383 CAPTURE_AVAILABLE, | 1374 CAPTURE_AVAILABLE, |
1384 CAPTURE_UNREACHABLE, | 1375 CAPTURE_UNREACHABLE, |
1385 CAPTURE_PERMANENTLY_UNREACHABLE | 1376 CAPTURE_PERMANENTLY_UNREACHABLE |
1386 }; | 1377 }; |
1387 | 1378 |
1388 class RegExpCapture: public RegExpTree { | 1379 class RegExpCapture: public RegExpTree { |
1389 public: | 1380 public: |
1390 explicit RegExpCapture(RegExpTree* body, int index) | 1381 explicit RegExpCapture(RegExpTree* body, int index) |
1391 : body_(body), index_(index), available_(CAPTURE_AVAILABLE) { } | 1382 : body_(body), index_(index), available_(CAPTURE_AVAILABLE) { } |
1392 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1383 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1393 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1384 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1394 RegExpNode* on_success, | 1385 RegExpNode* on_success); |
1395 RegExpNode* on_failure); | |
1396 static RegExpNode* ToNode(RegExpTree* body, | 1386 static RegExpNode* ToNode(RegExpTree* body, |
1397 int index, | 1387 int index, |
1398 RegExpCompiler* compiler, | 1388 RegExpCompiler* compiler, |
1399 RegExpNode* on_success, | 1389 RegExpNode* on_success); |
1400 RegExpNode* on_failure); | |
1401 virtual RegExpCapture* AsCapture(); | 1390 virtual RegExpCapture* AsCapture(); |
1402 virtual bool IsCapture(); | 1391 virtual bool IsCapture(); |
1403 RegExpTree* body() { return body_; } | 1392 RegExpTree* body() { return body_; } |
1404 int index() { return index_; } | 1393 int index() { return index_; } |
1405 inline CaptureAvailability available() { return available_; } | 1394 inline CaptureAvailability available() { return available_; } |
1406 inline void set_available(CaptureAvailability availability) { | 1395 inline void set_available(CaptureAvailability availability) { |
1407 available_ = availability; | 1396 available_ = availability; |
1408 } | 1397 } |
1409 static int StartRegister(int index) { return index * 2; } | 1398 static int StartRegister(int index) { return index * 2; } |
1410 static int EndRegister(int index) { return index * 2 + 1; } | 1399 static int EndRegister(int index) { return index * 2 + 1; } |
1411 private: | 1400 private: |
1412 RegExpTree* body_; | 1401 RegExpTree* body_; |
1413 int index_; | 1402 int index_; |
1414 CaptureAvailability available_; | 1403 CaptureAvailability available_; |
1415 }; | 1404 }; |
1416 | 1405 |
1417 | 1406 |
1418 class RegExpLookahead: public RegExpTree { | 1407 class RegExpLookahead: public RegExpTree { |
1419 public: | 1408 public: |
1420 RegExpLookahead(RegExpTree* body, bool is_positive) | 1409 RegExpLookahead(RegExpTree* body, bool is_positive) |
1421 : body_(body), | 1410 : body_(body), |
1422 is_positive_(is_positive) { } | 1411 is_positive_(is_positive) { } |
1423 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1412 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1424 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1413 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1425 RegExpNode* on_success, | 1414 RegExpNode* on_success); |
1426 RegExpNode* on_failure); | |
1427 virtual RegExpLookahead* AsLookahead(); | 1415 virtual RegExpLookahead* AsLookahead(); |
1428 virtual bool IsLookahead(); | 1416 virtual bool IsLookahead(); |
1429 RegExpTree* body() { return body_; } | 1417 RegExpTree* body() { return body_; } |
1430 bool is_positive() { return is_positive_; } | 1418 bool is_positive() { return is_positive_; } |
1431 private: | 1419 private: |
1432 RegExpTree* body_; | 1420 RegExpTree* body_; |
1433 bool is_positive_; | 1421 bool is_positive_; |
1434 }; | 1422 }; |
1435 | 1423 |
1436 | 1424 |
1437 class RegExpBackReference: public RegExpTree { | 1425 class RegExpBackReference: public RegExpTree { |
1438 public: | 1426 public: |
1439 explicit RegExpBackReference(RegExpCapture* capture) | 1427 explicit RegExpBackReference(RegExpCapture* capture) |
1440 : capture_(capture) { } | 1428 : capture_(capture) { } |
1441 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1429 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1442 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1430 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1443 RegExpNode* on_success, | 1431 RegExpNode* on_success); |
1444 RegExpNode* on_failure); | |
1445 virtual RegExpBackReference* AsBackReference(); | 1432 virtual RegExpBackReference* AsBackReference(); |
1446 virtual bool IsBackReference(); | 1433 virtual bool IsBackReference(); |
1447 int index() { return capture_->index(); } | 1434 int index() { return capture_->index(); } |
1448 RegExpCapture* capture() { return capture_; } | 1435 RegExpCapture* capture() { return capture_; } |
1449 private: | 1436 private: |
1450 RegExpCapture* capture_; | 1437 RegExpCapture* capture_; |
1451 }; | 1438 }; |
1452 | 1439 |
1453 | 1440 |
1454 class RegExpEmpty: public RegExpTree { | 1441 class RegExpEmpty: public RegExpTree { |
1455 public: | 1442 public: |
1456 RegExpEmpty() { } | 1443 RegExpEmpty() { } |
1457 virtual void* Accept(RegExpVisitor* visitor, void* data); | 1444 virtual void* Accept(RegExpVisitor* visitor, void* data); |
1458 virtual RegExpNode* ToNode(RegExpCompiler* compiler, | 1445 virtual RegExpNode* ToNode(RegExpCompiler* compiler, |
1459 RegExpNode* on_success, | 1446 RegExpNode* on_success); |
1460 RegExpNode* on_failure); | |
1461 virtual RegExpEmpty* AsEmpty(); | 1447 virtual RegExpEmpty* AsEmpty(); |
1462 virtual bool IsEmpty(); | 1448 virtual bool IsEmpty(); |
1463 static RegExpEmpty* GetInstance() { return &kInstance; } | 1449 static RegExpEmpty* GetInstance() { return &kInstance; } |
1464 private: | 1450 private: |
1465 static RegExpEmpty kInstance; | 1451 static RegExpEmpty kInstance; |
1466 }; | 1452 }; |
1467 | 1453 |
1468 | 1454 |
1469 class RegExpVisitor BASE_EMBEDDED { | 1455 class RegExpVisitor BASE_EMBEDDED { |
1470 public: | 1456 public: |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1514 #undef DEF_VISIT | 1500 #undef DEF_VISIT |
1515 | 1501 |
1516 private: | 1502 private: |
1517 bool stack_overflow_; | 1503 bool stack_overflow_; |
1518 }; | 1504 }; |
1519 | 1505 |
1520 | 1506 |
1521 } } // namespace v8::internal | 1507 } } // namespace v8::internal |
1522 | 1508 |
1523 #endif // V8_AST_H_ | 1509 #endif // V8_AST_H_ |
OLD | NEW |