18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 2635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project * Copyright (C) 2004, 2008, 2009 Apple Inc. All rights reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2008 Collabora Ltd. 42fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * Copyright (C) 2011 Peter Varga (pvarga@webkit.org), University of Szeged 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Redistribution and use in source and binary forms, with or without 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modification, are permitted provided that the following conditions 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * are met: 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer. 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * documentation and/or other materials provided with the distribution. 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "config.h" 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "RegularExpression.h" 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/BumpPointerAllocator.h> 322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <yarr/Yarr.h> 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "Logging.h" 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WebCore { 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 37231d4e3152a9c27a73b6ac7badbe6be673aa3ddfSteve Blockclass RegularExpression::Private : public RefCounted<RegularExpression::Private> { 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectpublic: 392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static PassRefPtr<Private> create(const String& pattern, TextCaseSensitivity caseSensitivity) 402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return adoptRef(new Private(pattern, caseSensitivity)); 422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int lastMatchLength; 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block unsigned m_numSubpatterns; 472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block OwnPtr<JSC::Yarr::BytecodePattern> m_regExpByteCode; 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 492fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockprivate: 502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Private(const String& pattern, TextCaseSensitivity caseSensitivity) 512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : lastMatchLength(-1) 522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_regExpByteCode(compile(pattern, caseSensitivity)) 532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_constructionError(0) 542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block PassOwnPtr<JSC::Yarr::BytecodePattern> compile(const String& patternString, TextCaseSensitivity caseSensitivity) 582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block JSC::Yarr::YarrPattern pattern(JSC::UString(patternString.impl()), (caseSensitivity == TextCaseInsensitive), false, &m_constructionError); 602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_constructionError) { 612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("RegularExpression: YARR compile failed with '%s'", m_constructionError); 622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return PassOwnPtr<JSC::Yarr::BytecodePattern>(); 632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_numSubpatterns = pattern.m_numSubpatterns; 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return JSC::Yarr::byteCompile(pattern, &m_regexAllocator); 682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block BumpPointerAllocator m_regexAllocator; 712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const char* m_constructionError; 722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 74635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source ProjectRegularExpression::RegularExpression(const String& pattern, TextCaseSensitivity caseSensitivity) 75635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project : d(Private::create(pattern, caseSensitivity)) 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectRegularExpression::RegularExpression(const RegularExpression& re) 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project : d(re.d) 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectRegularExpression::~RegularExpression() 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectRegularExpression& RegularExpression::operator=(const RegularExpression& re) 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 90635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project d = re.d; 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return *this; 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectint RegularExpression::match(const String& str, int startFrom, int* matchLength) const 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!d->m_regExpByteCode) 97635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project return -1; 98635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (str.isNull()) 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return -1; 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int offsetVectorSize = (d->m_numSubpatterns + 1) * 2; 1032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int* offsetVector; 1042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<int, 32> nonReturnedOvector; 1052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block nonReturnedOvector.resize(offsetVectorSize); 1072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block offsetVector = nonReturnedOvector.data(); 1082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(offsetVector); 1102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (unsigned j = 0, i = 0; i < d->m_numSubpatterns + 1; j += 2, i++) 1112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block offsetVector[j] = -1; 1122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int result = JSC::Yarr::interpret(d->m_regExpByteCode.get(), str.characters(), startFrom, str.length(), offsetVector); 1142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(result >= -1); 1152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 116635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project if (result < 0) { 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project d->lastMatchLength = -1; 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return -1; 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 120635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 1212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // 1 means 1 match; 0 means more than one match. First match is recorded in offsetVector. 1222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block d->lastMatchLength = offsetVector[1] - offsetVector[0]; 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (matchLength) 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project *matchLength = d->lastMatchLength; 1252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return offsetVector[0]; 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectint RegularExpression::searchRev(const String& str) const 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 130635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // FIXME: This could be faster if it actually searched backwards. 131635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project // Instead, it just searches forwards, multiple times until it finds the last match. 132635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int start = 0; 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int pos; 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int lastPos = -1; 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int lastMatchLength = -1; 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project do { 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int matchLength; 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project pos = match(str, start, &matchLength); 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (pos >= 0) { 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (pos + matchLength > lastPos + lastMatchLength) { 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // replace last match if this one is later and not a subset of the last match 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project lastPos = pos; 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project lastMatchLength = matchLength; 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project start = pos + 1; 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } while (pos != -1); 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project d->lastMatchLength = lastMatchLength; 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return lastPos; 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectint RegularExpression::matchedLength() const 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return d->lastMatchLength; 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectvoid replace(String& string, const RegularExpression& target, const String& replacement) 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int index = 0; 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (index < static_cast<int>(string.length())) { 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int matchLength; 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project index = target.match(string, index, &matchLength); 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (index < 0) 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project string.replace(index, matchLength, replacement); 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project index += replacement.length(); 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!matchLength) 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; // Avoid infinite loop on 0-length matches, e.g. [a-z]* 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} // namespace WebCore 174