blob: cfe804f99f5eee19693772225ad307d452ed6b64 [file] [log] [blame]
/*
* Copyright (C) 2009 Apple Inc. All rights reserved.
* Copyright (C) 2010 Peter Varga (pvarga@inf.u-szeged.hu), University of Szeged
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef YarrPattern_h
#define YarrPattern_h
#include <runtime/UString.h>
#include <wtf/Vector.h>
#include <wtf/unicode/Unicode.h>
namespace JSC { namespace Yarr {
struct PatternDisjunction;
struct CharacterRange {
UChar begin;
UChar end;
CharacterRange(UChar begin, UChar end)
: begin(begin)
, end(end)
{
}
};
struct CharacterClassTable : RefCounted<CharacterClassTable> {
const char* m_table;
bool m_inverted;
static PassRefPtr<CharacterClassTable> create(const char* table, bool inverted)
{
return adoptRef(new CharacterClassTable(table, inverted));
}
private:
CharacterClassTable(const char* table, bool inverted)
: m_table(table)
, m_inverted(inverted)
{
}
};
struct CharacterClass {
WTF_MAKE_FAST_ALLOCATED;
public:
// All CharacterClass instances have to have the full set of matches and ranges,
// they may have an optional table for faster lookups (which must match the
// specified matches and ranges)
CharacterClass(PassRefPtr<CharacterClassTable> table)
: m_table(table)
{
}
Vector<UChar> m_matches;
Vector<CharacterRange> m_ranges;
Vector<UChar> m_matchesUnicode;
Vector<CharacterRange> m_rangesUnicode;
RefPtr<CharacterClassTable> m_table;
};
enum QuantifierType {
QuantifierFixedCount,
QuantifierGreedy,
QuantifierNonGreedy,
};
struct PatternTerm {
enum Type {
TypeAssertionBOL,
TypeAssertionEOL,
TypeAssertionWordBoundary,
TypePatternCharacter,
TypeCharacterClass,
TypeBackReference,
TypeForwardReference,
TypeParenthesesSubpattern,
TypeParentheticalAssertion,
} type;
bool m_capture :1;
bool m_invert :1;
union {
UChar patternCharacter;
CharacterClass* characterClass;
unsigned backReferenceSubpatternId;
struct {
PatternDisjunction* disjunction;
unsigned subpatternId;
unsigned lastSubpatternId;
bool isCopy;
bool isTerminal;
} parentheses;
};
QuantifierType quantityType;
unsigned quantityCount;
int inputPosition;
unsigned frameLocation;
PatternTerm(UChar ch)
: type(PatternTerm::TypePatternCharacter)
, m_capture(false)
, m_invert(false)
{
patternCharacter = ch;
quantityType = QuantifierFixedCount;
quantityCount = 1;
}
PatternTerm(CharacterClass* charClass, bool invert)
: type(PatternTerm::TypeCharacterClass)
, m_capture(false)
, m_invert(invert)
{
characterClass = charClass;
quantityType = QuantifierFixedCount;
quantityCount = 1;
}
PatternTerm(Type type, unsigned subpatternId, PatternDisjunction* disjunction, bool capture = false, bool invert = false)
: type(type)
, m_capture(capture)
, m_invert(invert)
{
parentheses.disjunction = disjunction;
parentheses.subpatternId = subpatternId;
parentheses.isCopy = false;
parentheses.isTerminal = false;
quantityType = QuantifierFixedCount;
quantityCount = 1;
}
PatternTerm(Type type, bool invert = false)
: type(type)
, m_capture(false)
, m_invert(invert)
{
quantityType = QuantifierFixedCount;
quantityCount = 1;
}
PatternTerm(unsigned spatternId)
: type(TypeBackReference)
, m_capture(false)
, m_invert(false)
{
backReferenceSubpatternId = spatternId;
quantityType = QuantifierFixedCount;
quantityCount = 1;
}
static PatternTerm ForwardReference()
{
return PatternTerm(TypeForwardReference);
}
static PatternTerm BOL()
{
return PatternTerm(TypeAssertionBOL);
}
static PatternTerm EOL()
{
return PatternTerm(TypeAssertionEOL);
}
static PatternTerm WordBoundary(bool invert)
{
return PatternTerm(TypeAssertionWordBoundary, invert);
}
bool invert()
{
return m_invert;
}
bool capture()
{
return m_capture;
}
void quantify(unsigned count, QuantifierType type)
{
quantityCount = count;
quantityType = type;
}
};
struct PatternAlternative {
WTF_MAKE_FAST_ALLOCATED;
public:
PatternAlternative(PatternDisjunction* disjunction)
: m_parent(disjunction)
, m_onceThrough(false)
, m_hasFixedSize(false)
, m_startsWithBOL(false)
, m_containsBOL(false)
{
}
PatternTerm& lastTerm()
{
ASSERT(m_terms.size());
return m_terms[m_terms.size() - 1];
}
void removeLastTerm()
{
ASSERT(m_terms.size());
m_terms.shrink(m_terms.size() - 1);
}
void setOnceThrough()
{
m_onceThrough = true;
}
bool onceThrough()
{
return m_onceThrough;
}
Vector<PatternTerm> m_terms;
PatternDisjunction* m_parent;
unsigned m_minimumSize;
bool m_onceThrough : 1;
bool m_hasFixedSize : 1;
bool m_startsWithBOL : 1;
bool m_containsBOL : 1;
};
struct PatternDisjunction {
WTF_MAKE_FAST_ALLOCATED;
public:
PatternDisjunction(PatternAlternative* parent = 0)
: m_parent(parent)
, m_hasFixedSize(false)
{
}
~PatternDisjunction()
{
deleteAllValues(m_alternatives);
}
PatternAlternative* addNewAlternative()
{
PatternAlternative* alternative = new PatternAlternative(this);
m_alternatives.append(alternative);
return alternative;
}
Vector<PatternAlternative*> m_alternatives;
PatternAlternative* m_parent;
unsigned m_minimumSize;
unsigned m_callFrameSize;
bool m_hasFixedSize;
};
// You probably don't want to be calling these functions directly
// (please to be calling newlineCharacterClass() et al on your
// friendly neighborhood YarrPattern instance to get nicely
// cached copies).
CharacterClass* newlineCreate();
CharacterClass* digitsCreate();
CharacterClass* spacesCreate();
CharacterClass* wordcharCreate();
CharacterClass* nondigitsCreate();
CharacterClass* nonspacesCreate();
CharacterClass* nonwordcharCreate();
struct TermChain {
TermChain(PatternTerm term)
: term(term)
{}
PatternTerm term;
Vector<TermChain> hotTerms;
};
struct BeginChar {
BeginChar()
: value(0)
, mask(0)
{}
BeginChar(unsigned value, unsigned mask)
: value(value)
, mask(mask)
{}
unsigned value;
unsigned mask;
};
struct YarrPattern {
YarrPattern(const UString& pattern, bool ignoreCase, bool multiline, const char** error);
~YarrPattern()
{
deleteAllValues(m_disjunctions);
deleteAllValues(m_userCharacterClasses);
}
void reset()
{
m_numSubpatterns = 0;
m_maxBackReference = 0;
m_containsBackreferences = false;
m_containsBeginChars = false;
m_containsBOL = false;
newlineCached = 0;
digitsCached = 0;
spacesCached = 0;
wordcharCached = 0;
nondigitsCached = 0;
nonspacesCached = 0;
nonwordcharCached = 0;
deleteAllValues(m_disjunctions);
m_disjunctions.clear();
deleteAllValues(m_userCharacterClasses);
m_userCharacterClasses.clear();
m_beginChars.clear();
}
bool containsIllegalBackReference()
{
return m_maxBackReference > m_numSubpatterns;
}
CharacterClass* newlineCharacterClass()
{
if (!newlineCached)
m_userCharacterClasses.append(newlineCached = newlineCreate());
return newlineCached;
}
CharacterClass* digitsCharacterClass()
{
if (!digitsCached)
m_userCharacterClasses.append(digitsCached = digitsCreate());
return digitsCached;
}
CharacterClass* spacesCharacterClass()
{
if (!spacesCached)
m_userCharacterClasses.append(spacesCached = spacesCreate());
return spacesCached;
}
CharacterClass* wordcharCharacterClass()
{
if (!wordcharCached)
m_userCharacterClasses.append(wordcharCached = wordcharCreate());
return wordcharCached;
}
CharacterClass* nondigitsCharacterClass()
{
if (!nondigitsCached)
m_userCharacterClasses.append(nondigitsCached = nondigitsCreate());
return nondigitsCached;
}
CharacterClass* nonspacesCharacterClass()
{
if (!nonspacesCached)
m_userCharacterClasses.append(nonspacesCached = nonspacesCreate());
return nonspacesCached;
}
CharacterClass* nonwordcharCharacterClass()
{
if (!nonwordcharCached)
m_userCharacterClasses.append(nonwordcharCached = nonwordcharCreate());
return nonwordcharCached;
}
bool m_ignoreCase : 1;
bool m_multiline : 1;
bool m_containsBackreferences : 1;
bool m_containsBeginChars : 1;
bool m_containsBOL : 1;
unsigned m_numSubpatterns;
unsigned m_maxBackReference;
PatternDisjunction* m_body;
Vector<PatternDisjunction*, 4> m_disjunctions;
Vector<CharacterClass*> m_userCharacterClasses;
Vector<BeginChar> m_beginChars;
private:
const char* compile(const UString& patternString);
CharacterClass* newlineCached;
CharacterClass* digitsCached;
CharacterClass* spacesCached;
CharacterClass* wordcharCached;
CharacterClass* nondigitsCached;
CharacterClass* nonspacesCached;
CharacterClass* nonwordcharCached;
};
} } // namespace JSC::Yarr
#endif // YarrPattern_h