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