1c435b66ab3ebb50706f31c0ffe39931b4985cd4
[WebKit-https.git] / Source / JavaScriptCore / yarr / RegularExpression.cpp
1
2 /*
3  * Copyright (C) 2004, 2008, 2009 Apple Inc. All rights reserved.
4  * Copyright (C) 2008 Collabora Ltd.
5  * Copyright (C) 2011 Peter Varga (pvarga@webkit.org), University of Szeged
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
24  * 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
29 #include "config.h"
30 #include "RegularExpression.h"
31
32 #include "Yarr.h"
33 #include <wtf/Assertions.h>
34 #include <wtf/BumpPointerAllocator.h>
35
36 namespace JSC { namespace Yarr {
37
38 class RegularExpression::Private : public RefCounted<RegularExpression::Private> {
39 public:
40     static Ref<Private> create(const String& pattern, TextCaseSensitivity caseSensitivity, MultilineMode multilineMode)
41     {
42         return adoptRef(*new Private(pattern, caseSensitivity, multilineMode));
43     }
44
45     int lastMatchLength;
46
47     unsigned m_numSubpatterns;
48     std::unique_ptr<JSC::Yarr::BytecodePattern> m_regExpByteCode;
49
50 private:
51     Private(const String& pattern, TextCaseSensitivity caseSensitivity, MultilineMode multilineMode)
52         : lastMatchLength(-1)
53         , m_regExpByteCode(compile(pattern, caseSensitivity, multilineMode))
54         , m_constructionError(nullptr)
55     {
56     }
57
58     std::unique_ptr<JSC::Yarr::BytecodePattern> compile(const String& patternString, TextCaseSensitivity caseSensitivity, MultilineMode multilineMode)
59     {
60         RegExpFlags flags = NoFlags;
61
62         if (caseSensitivity == TextCaseInsensitive)
63             flags = static_cast<RegExpFlags>(flags | FlagIgnoreCase);
64
65         if (multilineMode == MultilineEnabled)
66             flags = static_cast<RegExpFlags>(flags | FlagMultiline);
67
68         JSC::Yarr::YarrPattern pattern(patternString, flags, &m_constructionError);
69         if (m_constructionError) {
70             LOG_ERROR("RegularExpression: YARR compile failed with '%s'", m_constructionError);
71             return nullptr;
72         }
73
74         m_numSubpatterns = pattern.m_numSubpatterns;
75
76         return JSC::Yarr::byteCompile(pattern, &m_regexAllocator);
77     }
78
79     BumpPointerAllocator m_regexAllocator;
80     const char* m_constructionError;
81 };
82
83 RegularExpression::RegularExpression(const String& pattern, TextCaseSensitivity caseSensitivity, MultilineMode multilineMode)
84     : d(Private::create(pattern, caseSensitivity, multilineMode))
85 {
86 }
87
88 RegularExpression::RegularExpression(const RegularExpression& re)
89     : d(re.d)
90 {
91 }
92
93 RegularExpression::~RegularExpression()
94 {
95 }
96
97 RegularExpression& RegularExpression::operator=(const RegularExpression& re)
98 {
99     d = re.d;
100     return *this;
101 }
102
103 int RegularExpression::match(const String& str, int startFrom, int* matchLength) const
104 {
105     if (!d->m_regExpByteCode)
106         return -1;
107
108     if (str.isNull())
109         return -1;
110
111     int offsetVectorSize = (d->m_numSubpatterns + 1) * 2;
112     unsigned* offsetVector;
113     Vector<unsigned, 32> nonReturnedOvector;
114
115     nonReturnedOvector.resize(offsetVectorSize);
116     offsetVector = nonReturnedOvector.data();
117
118     ASSERT(offsetVector);
119     for (unsigned j = 0, i = 0; i < d->m_numSubpatterns + 1; j += 2, i++)
120         offsetVector[j] = JSC::Yarr::offsetNoMatch;
121
122     unsigned result;
123     if (str.length() <= INT_MAX)
124         result = JSC::Yarr::interpret(d->m_regExpByteCode.get(), str, startFrom, offsetVector);
125     else {
126         // This code can't handle unsigned offsets. Limit our processing to strings with offsets that
127         // can be represented as ints.
128         result = JSC::Yarr::offsetNoMatch;
129     }
130
131     if (result == JSC::Yarr::offsetNoMatch) {
132         d->lastMatchLength = -1;
133         return -1;
134     }
135
136     // 1 means 1 match; 0 means more than one match. First match is recorded in offsetVector.
137     d->lastMatchLength = offsetVector[1] - offsetVector[0];
138     if (matchLength)
139         *matchLength = d->lastMatchLength;
140     return offsetVector[0];
141 }
142
143 int RegularExpression::searchRev(const String& str) const
144 {
145     // FIXME: This could be faster if it actually searched backwards.
146     // Instead, it just searches forwards, multiple times until it finds the last match.
147
148     int start = 0;
149     int pos;
150     int lastPos = -1;
151     int lastMatchLength = -1;
152     do {
153         int matchLength;
154         pos = match(str, start, &matchLength);
155         if (pos >= 0) {
156             if (pos + matchLength > lastPos + lastMatchLength) {
157                 // replace last match if this one is later and not a subset of the last match
158                 lastPos = pos;
159                 lastMatchLength = matchLength;
160             }
161             start = pos + 1;
162         }
163     } while (pos != -1);
164     d->lastMatchLength = lastMatchLength;
165     return lastPos;
166 }
167
168 int RegularExpression::matchedLength() const
169 {
170     return d->lastMatchLength;
171 }
172
173 void replace(String& string, const RegularExpression& target, const String& replacement)
174 {
175     int index = 0;
176     while (index < static_cast<int>(string.length())) {
177         int matchLength;
178         index = target.match(string, index, &matchLength);
179         if (index < 0)
180             break;
181         string.replace(index, matchLength, replacement);
182         index += replacement.length();
183         if (!matchLength)
184             break; // Avoid infinite loop on 0-length matches, e.g. [a-z]*
185     }
186 }
187
188 bool RegularExpression::isValid() const
189 {
190     return d->m_regExpByteCode.get();
191 }
192
193 } } // namespace JSC::Yarr