Changeset 47337 in webkit for trunk/JavaScriptCore/yarr/RegexInterpreter.cpp
- Timestamp:
- Aug 16, 2009, 6:14:24 AM (16 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/JavaScriptCore/yarr/RegexInterpreter.cpp
r46778 r47337 21 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 24 */ 25 25 … … 91 91 { 92 92 } 93 93 94 94 void* operator new(size_t, void* where) 95 95 { … … 125 125 output[(firstSubpatternId << 1) + i] = -1; 126 126 } 127 127 128 128 new(getDisjunctionContext(term)) DisjunctionContext(); 129 129 } … … 139 139 output[(firstSubpatternId << 1) + i] = subpatternBackup[i]; 140 140 } 141 141 142 142 DisjunctionContext* getDisjunctionContext(ByteTerm& term) 143 143 { … … 209 209 return -1; 210 210 } 211 211 212 212 unsigned getPos() 213 213 { … … 219 219 pos = p; 220 220 } 221 221 222 222 bool atStart() 223 223 { … … 285 285 if (input.atEnd()) 286 286 return false; 287 287 288 288 int ch = input.read(); 289 289 … … 342 342 } 343 343 } 344 344 345 345 return true; 346 346 } … … 607 607 if (matchDisjunction(term.atom.parenthesesDisjunction, context->getDisjunctionContext(term), true)) 608 608 return true; 609 609 610 610 resetMatches(term, context); 611 611 freeParenthesesDisjunctionContext(context); … … 947 947 return true; 948 948 } 949 949 950 950 // pop a match off the stack 951 951 resetMatches(term, context); … … 1267 1267 : m_pattern(pattern) 1268 1268 { 1269 bodyDisjunction = 0;1270 currentAlternativeIndex = 0;1271 } 1272 1269 m_bodyDisjunction = 0; 1270 m_currentAlternativeIndex = 0; 1271 } 1272 1273 1273 BytecodePattern* compile() 1274 1274 { … … 1277 1277 regexEnd(); 1278 1278 1279 return new BytecodePattern( bodyDisjunction, m_allParenthesesInfo, m_pattern);1280 } 1281 1279 return new BytecodePattern(m_bodyDisjunction, m_allParenthesesInfo, m_pattern); 1280 } 1281 1282 1282 void checkInput(unsigned count) 1283 1283 { 1284 bodyDisjunction->terms.append(ByteTerm::CheckInput(count));1284 m_bodyDisjunction->terms.append(ByteTerm::CheckInput(count)); 1285 1285 } 1286 1286 1287 1287 void assertionBOL(int inputPosition) 1288 1288 { 1289 bodyDisjunction->terms.append(ByteTerm::BOL(inputPosition));1289 m_bodyDisjunction->terms.append(ByteTerm::BOL(inputPosition)); 1290 1290 } 1291 1291 1292 1292 void assertionEOL(int inputPosition) 1293 1293 { 1294 bodyDisjunction->terms.append(ByteTerm::EOL(inputPosition));1294 m_bodyDisjunction->terms.append(ByteTerm::EOL(inputPosition)); 1295 1295 } 1296 1296 1297 1297 void assertionWordBoundary(bool invert, int inputPosition) 1298 1298 { 1299 bodyDisjunction->terms.append(ByteTerm::WordBoundary(invert, inputPosition));1299 m_bodyDisjunction->terms.append(ByteTerm::WordBoundary(invert, inputPosition)); 1300 1300 } 1301 1301 … … 1305 1305 UChar lo = Unicode::toLower(ch); 1306 1306 UChar hi = Unicode::toUpper(ch); 1307 1307 1308 1308 if (lo != hi) { 1309 bodyDisjunction->terms.append(ByteTerm(lo, hi, inputPosition, frameLocation, quantityCount, quantityType));1309 m_bodyDisjunction->terms.append(ByteTerm(lo, hi, inputPosition, frameLocation, quantityCount, quantityType)); 1310 1310 return; 1311 1311 } 1312 1312 } 1313 1313 1314 bodyDisjunction->terms.append(ByteTerm(ch, inputPosition, frameLocation, quantityCount, quantityType));1315 } 1316 1314 m_bodyDisjunction->terms.append(ByteTerm(ch, inputPosition, frameLocation, quantityCount, quantityType)); 1315 } 1316 1317 1317 void atomCharacterClass(CharacterClass* characterClass, bool invert, int inputPosition, unsigned frameLocation, unsigned quantityCount, QuantifierType quantityType) 1318 1318 { 1319 bodyDisjunction->terms.append(ByteTerm(characterClass, invert, inputPosition));1320 1321 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount;1322 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;1323 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;1319 m_bodyDisjunction->terms.append(ByteTerm(characterClass, invert, inputPosition)); 1320 1321 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount; 1322 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType; 1323 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation; 1324 1324 } 1325 1325 … … 1328 1328 ASSERT(subpatternId); 1329 1329 1330 bodyDisjunction->terms.append(ByteTerm::BackReference(subpatternId, inputPosition));1331 1332 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount;1333 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType;1334 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;1330 m_bodyDisjunction->terms.append(ByteTerm::BackReference(subpatternId, inputPosition)); 1331 1332 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityCount = quantityCount; 1333 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].atom.quantityType = quantityType; 1334 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation; 1335 1335 } 1336 1336 1337 1337 void atomParenthesesSubpatternBegin(unsigned subpatternId, bool capture, int inputPosition, unsigned frameLocation, unsigned alternativeFrameLocation) 1338 1338 { 1339 int beginTerm = bodyDisjunction->terms.size();1340 1341 bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, inputPosition));1342 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;1343 bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());1344 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;1345 1346 m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, currentAlternativeIndex));1347 currentAlternativeIndex = beginTerm + 1;1339 int beginTerm = m_bodyDisjunction->terms.size(); 1340 1341 m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpatternOnceBegin, subpatternId, capture, inputPosition)); 1342 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation; 1343 m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin()); 1344 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation; 1345 1346 m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, m_currentAlternativeIndex)); 1347 m_currentAlternativeIndex = beginTerm + 1; 1348 1348 } 1349 1349 1350 1350 void atomParentheticalAssertionBegin(unsigned subpatternId, bool invert, unsigned frameLocation, unsigned alternativeFrameLocation) 1351 1351 { 1352 int beginTerm = bodyDisjunction->terms.size();1353 1354 bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionBegin, subpatternId, invert, 0));1355 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].frameLocation = frameLocation;1356 bodyDisjunction->terms.append(ByteTerm::AlternativeBegin());1357 bodyDisjunction->terms[bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation;1358 1359 m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, currentAlternativeIndex));1360 currentAlternativeIndex = beginTerm + 1;1352 int beginTerm = m_bodyDisjunction->terms.size(); 1353 1354 m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParentheticalAssertionBegin, subpatternId, invert, 0)); 1355 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = frameLocation; 1356 m_bodyDisjunction->terms.append(ByteTerm::AlternativeBegin()); 1357 m_bodyDisjunction->terms[m_bodyDisjunction->terms.size() - 1].frameLocation = alternativeFrameLocation; 1358 1359 m_parenthesesStack.append(ParenthesesStackEntry(beginTerm, m_currentAlternativeIndex)); 1360 m_currentAlternativeIndex = beginTerm + 1; 1361 1361 } 1362 1362 … … 1366 1366 int stackEnd = m_parenthesesStack.size() - 1; 1367 1367 unsigned beginTerm = m_parenthesesStack[stackEnd].beginTerm; 1368 currentAlternativeIndex = m_parenthesesStack[stackEnd].savedAlternativeIndex;1368 m_currentAlternativeIndex = m_parenthesesStack[stackEnd].savedAlternativeIndex; 1369 1369 m_parenthesesStack.shrink(stackEnd); 1370 1370 1371 ASSERT(beginTerm < bodyDisjunction->terms.size());1372 ASSERT( currentAlternativeIndex <bodyDisjunction->terms.size());1373 1371 ASSERT(beginTerm < m_bodyDisjunction->terms.size()); 1372 ASSERT(m_currentAlternativeIndex < m_bodyDisjunction->terms.size()); 1373 1374 1374 return beginTerm; 1375 1375 } … … 1388 1388 { 1389 1389 int origBeginTerm = beginTerm; 1390 ASSERT( bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeBegin);1391 int endIndex = bodyDisjunction->terms.size();1392 1393 unsigned frameLocation = bodyDisjunction->terms[beginTerm].frameLocation;1394 1395 if (! bodyDisjunction->terms[beginTerm].alternative.next)1396 bodyDisjunction->terms.remove(beginTerm);1390 ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeBegin); 1391 int endIndex = m_bodyDisjunction->terms.size(); 1392 1393 unsigned frameLocation = m_bodyDisjunction->terms[beginTerm].frameLocation; 1394 1395 if (!m_bodyDisjunction->terms[beginTerm].alternative.next) 1396 m_bodyDisjunction->terms.remove(beginTerm); 1397 1397 else { 1398 while ( bodyDisjunction->terms[beginTerm].alternative.next) {1399 beginTerm += bodyDisjunction->terms[beginTerm].alternative.next;1400 ASSERT( bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeDisjunction);1401 bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm;1402 bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;1403 } 1404 1405 bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm;1406 1407 bodyDisjunction->terms.append(ByteTerm::AlternativeEnd());1408 bodyDisjunction->terms[endIndex].frameLocation = frameLocation;1398 while (m_bodyDisjunction->terms[beginTerm].alternative.next) { 1399 beginTerm += m_bodyDisjunction->terms[beginTerm].alternative.next; 1400 ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeAlternativeDisjunction); 1401 m_bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm; 1402 m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation; 1403 } 1404 1405 m_bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm; 1406 1407 m_bodyDisjunction->terms.append(ByteTerm::AlternativeEnd()); 1408 m_bodyDisjunction->terms[endIndex].frameLocation = frameLocation; 1409 1409 } 1410 1410 } … … 1414 1414 int beginTerm = 0; 1415 1415 int origBeginTerm = 0; 1416 ASSERT( bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeBegin);1417 int endIndex = bodyDisjunction->terms.size();1418 1419 unsigned frameLocation = bodyDisjunction->terms[beginTerm].frameLocation;1420 1421 while ( bodyDisjunction->terms[beginTerm].alternative.next) {1422 beginTerm += bodyDisjunction->terms[beginTerm].alternative.next;1423 ASSERT( bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeDisjunction);1424 bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm;1425 bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;1426 } 1427 1428 bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm;1429 1430 bodyDisjunction->terms.append(ByteTerm::BodyAlternativeEnd());1431 bodyDisjunction->terms[endIndex].frameLocation = frameLocation;1416 ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeBegin); 1417 int endIndex = m_bodyDisjunction->terms.size(); 1418 1419 unsigned frameLocation = m_bodyDisjunction->terms[beginTerm].frameLocation; 1420 1421 while (m_bodyDisjunction->terms[beginTerm].alternative.next) { 1422 beginTerm += m_bodyDisjunction->terms[beginTerm].alternative.next; 1423 ASSERT(m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeBodyAlternativeDisjunction); 1424 m_bodyDisjunction->terms[beginTerm].alternative.end = endIndex - beginTerm; 1425 m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation; 1426 } 1427 1428 m_bodyDisjunction->terms[beginTerm].alternative.next = origBeginTerm - beginTerm; 1429 1430 m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeEnd()); 1431 m_bodyDisjunction->terms[endIndex].frameLocation = frameLocation; 1432 1432 } 1433 1433 … … 1436 1436 unsigned beginTerm = popParenthesesStack(); 1437 1437 closeAlternative(beginTerm + 1); 1438 unsigned endTerm = bodyDisjunction->terms.size();1439 1440 bool isAssertion = bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParentheticalAssertionBegin;1441 bool invertOrCapture = bodyDisjunction->terms[beginTerm].invertOrCapture;1442 unsigned subpatternId = bodyDisjunction->terms[beginTerm].atom.subpatternId;1443 1444 bodyDisjunction->terms.append(ByteTerm(isAssertion ? ByteTerm::TypeParentheticalAssertionEnd : ByteTerm::TypeParenthesesSubpatternOnceEnd, subpatternId, invertOrCapture, inputPosition));1445 bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm;1446 bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm;1447 bodyDisjunction->terms[endTerm].frameLocation = frameLocation;1438 unsigned endTerm = m_bodyDisjunction->terms.size(); 1439 1440 bool isAssertion = m_bodyDisjunction->terms[beginTerm].type == ByteTerm::TypeParentheticalAssertionBegin; 1441 bool invertOrCapture = m_bodyDisjunction->terms[beginTerm].invertOrCapture; 1442 unsigned subpatternId = m_bodyDisjunction->terms[beginTerm].atom.subpatternId; 1443 1444 m_bodyDisjunction->terms.append(ByteTerm(isAssertion ? ByteTerm::TypeParentheticalAssertionEnd : ByteTerm::TypeParenthesesSubpatternOnceEnd, subpatternId, invertOrCapture, inputPosition)); 1445 m_bodyDisjunction->terms[beginTerm].atom.parenthesesWidth = endTerm - beginTerm; 1446 m_bodyDisjunction->terms[endTerm].atom.parenthesesWidth = endTerm - beginTerm; 1447 m_bodyDisjunction->terms[endTerm].frameLocation = frameLocation; 1448 1448 1449 1449 if (doInline) { 1450 bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;1451 bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;1452 bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount;1453 bodyDisjunction->terms[endTerm].atom.quantityType = quantityType;1450 m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount; 1451 m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType; 1452 m_bodyDisjunction->terms[endTerm].atom.quantityCount = quantityCount; 1453 m_bodyDisjunction->terms[endTerm].atom.quantityType = quantityType; 1454 1454 } else { 1455 ByteTerm& parenthesesBegin = bodyDisjunction->terms[beginTerm];1455 ByteTerm& parenthesesBegin = m_bodyDisjunction->terms[beginTerm]; 1456 1456 ASSERT(parenthesesBegin.type == ByteTerm::TypeParenthesesSubpatternOnceBegin); 1457 1457 … … 1464 1464 parenthesesDisjunction->terms.append(ByteTerm::SubpatternBegin()); 1465 1465 for (unsigned termInParentheses = beginTerm + 1; termInParentheses < endTerm; ++termInParentheses) 1466 parenthesesDisjunction->terms.append( bodyDisjunction->terms[termInParentheses]);1466 parenthesesDisjunction->terms.append(m_bodyDisjunction->terms[termInParentheses]); 1467 1467 parenthesesDisjunction->terms.append(ByteTerm::SubpatternEnd()); 1468 1468 1469 bodyDisjunction->terms.shrink(beginTerm);1469 m_bodyDisjunction->terms.shrink(beginTerm); 1470 1470 1471 1471 m_allParenthesesInfo.append(parenthesesDisjunction); 1472 bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, invertOrCapture, inputPosition));1473 1474 bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount;1475 bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType;1476 bodyDisjunction->terms[beginTerm].frameLocation = frameLocation;1472 m_bodyDisjunction->terms.append(ByteTerm(ByteTerm::TypeParenthesesSubpattern, subpatternId, parenthesesDisjunction, invertOrCapture, inputPosition)); 1473 1474 m_bodyDisjunction->terms[beginTerm].atom.quantityCount = quantityCount; 1475 m_bodyDisjunction->terms[beginTerm].atom.quantityType = quantityType; 1476 m_bodyDisjunction->terms[beginTerm].frameLocation = frameLocation; 1477 1477 } 1478 1478 } … … 1480 1480 void regexBegin(unsigned numSubpatterns, unsigned callFrameSize) 1481 1481 { 1482 bodyDisjunction = new ByteDisjunction(numSubpatterns, callFrameSize);1483 bodyDisjunction->terms.append(ByteTerm::BodyAlternativeBegin());1484 bodyDisjunction->terms[0].frameLocation = 0;1485 currentAlternativeIndex = 0;1482 m_bodyDisjunction = new ByteDisjunction(numSubpatterns, callFrameSize); 1483 m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeBegin()); 1484 m_bodyDisjunction->terms[0].frameLocation = 0; 1485 m_currentAlternativeIndex = 0; 1486 1486 } 1487 1487 … … 1493 1493 void alterantiveBodyDisjunction() 1494 1494 { 1495 int newAlternativeIndex = bodyDisjunction->terms.size();1496 bodyDisjunction->terms[currentAlternativeIndex].alternative.next = newAlternativeIndex -currentAlternativeIndex;1497 bodyDisjunction->terms.append(ByteTerm::BodyAlternativeDisjunction());1498 1499 currentAlternativeIndex = newAlternativeIndex;1495 int newAlternativeIndex = m_bodyDisjunction->terms.size(); 1496 m_bodyDisjunction->terms[m_currentAlternativeIndex].alternative.next = newAlternativeIndex - m_currentAlternativeIndex; 1497 m_bodyDisjunction->terms.append(ByteTerm::BodyAlternativeDisjunction()); 1498 1499 m_currentAlternativeIndex = newAlternativeIndex; 1500 1500 } 1501 1501 1502 1502 void alterantiveDisjunction() 1503 1503 { 1504 int newAlternativeIndex = bodyDisjunction->terms.size();1505 bodyDisjunction->terms[currentAlternativeIndex].alternative.next = newAlternativeIndex -currentAlternativeIndex;1506 bodyDisjunction->terms.append(ByteTerm::AlternativeDisjunction());1507 1508 currentAlternativeIndex = newAlternativeIndex;1504 int newAlternativeIndex = m_bodyDisjunction->terms.size(); 1505 m_bodyDisjunction->terms[m_currentAlternativeIndex].alternative.next = newAlternativeIndex - m_currentAlternativeIndex; 1506 m_bodyDisjunction->terms.append(ByteTerm::AlternativeDisjunction()); 1507 1508 m_currentAlternativeIndex = newAlternativeIndex; 1509 1509 } 1510 1510 … … 1513 1513 for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) { 1514 1514 unsigned currentCountAlreadyChecked = inputCountAlreadyChecked; 1515 1515 1516 1516 if (alt) { 1517 1517 if (disjunction == m_pattern.m_body) … … 1587 1587 case PatternTerm::TypeParentheticalAssertion: { 1588 1588 unsigned alternativeFrameLocation = term.inputPosition + RegexStackSpaceForBackTrackInfoParentheticalAssertion; 1589 1589 1590 1590 atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invertOrCapture, term.frameLocation, alternativeFrameLocation); 1591 1591 emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, 0); … … 1600 1600 private: 1601 1601 RegexPattern& m_pattern; 1602 ByteDisjunction* bodyDisjunction;1603 unsigned currentAlternativeIndex;1602 ByteDisjunction* m_bodyDisjunction; 1603 unsigned m_currentAlternativeIndex; 1604 1604 Vector<ParenthesesStackEntry> m_parenthesesStack; 1605 1605 Vector<ByteDisjunction*> m_allParenthesesInfo;
Note:
See TracChangeset
for help on using the changeset viewer.