blob: f062efce72e32febf86bb23c4bce6b78c2da8383 [file] [log] [blame]
/*
* Copyright (C) 2014-2015 Apple Inc. All rights reserved.
*
* 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. AND ITS CONTRIBUTORS ``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 ITS 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.
*/
#pragma once
#if ENABLE(CONTENT_EXTENSIONS)
#include "ContentExtensionsDebugging.h"
#include "NFA.h"
#include <unicode/utypes.h>
#include <wtf/ASCIICType.h>
#include <wtf/Hasher.h>
#include <wtf/Vector.h>
#include <wtf/text/StringBuilder.h>
namespace WebCore {
namespace ContentExtensions {
enum class AtomQuantifier : uint8_t {
One,
ZeroOrOne,
ZeroOrMore,
OneOrMore
};
class Term {
public:
Term();
Term(char character, bool isCaseSensitive);
enum UniversalTransitionTag { UniversalTransition };
explicit Term(UniversalTransitionTag);
enum CharacterSetTermTag { CharacterSetTerm };
explicit Term(CharacterSetTermTag, bool isInverted);
enum GroupTermTag { GroupTerm };
explicit Term(GroupTermTag);
enum EndOfLineAssertionTermTag { EndOfLineAssertionTerm };
explicit Term(EndOfLineAssertionTermTag);
Term(const Term& other);
Term(Term&& other);
enum EmptyValueTag { EmptyValue };
Term(EmptyValueTag);
~Term();
bool isValid() const;
// CharacterSet terms only.
void addCharacter(UChar character, bool isCaseSensitive);
// Group terms only.
void extendGroupSubpattern(const Term&);
void quantify(const AtomQuantifier&);
ImmutableCharNFANodeBuilder generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const;
void generateGraph(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
bool isEndOfLineAssertion() const;
bool matchesAtLeastOneCharacter() const;
// Matches any string, the empty string included.
// This is very conservative. Patterns matching any string can return false here.
bool isKnownToMatchAnyString() const;
// Return true if the term can only match input of a single fixed length.
bool hasFixedLength() const;
Term& operator=(const Term& other);
Term& operator=(Term&& other);
bool operator==(const Term& other) const;
unsigned hash() const;
bool isEmptyValue() const;
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
String toString() const;
#endif
#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
size_t memoryUsed() const;
#endif
private:
// This is exact for character sets but conservative for groups.
// The return value can be false for a group equivalent to a universal transition.
bool isUniversalTransition() const;
void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const;
void generateSubgraphForAtom(NFA&, ImmutableCharNFANodeBuilder& source, uint32_t destination) const;
void destroy();
enum class TermType : uint8_t {
Empty,
CharacterSet,
Group
};
TermType m_termType { TermType::Empty };
AtomQuantifier m_quantifier { AtomQuantifier::One };
class CharacterSet {
public:
void set(UChar character)
{
RELEASE_ASSERT(character < 128);
m_characters[character / 64] |= (uint64_t(1) << (character % 64));
}
bool get(UChar character) const
{
RELEASE_ASSERT(character < 128);
return m_characters[character / 64] & (uint64_t(1) << (character % 64));
}
void invert()
{
ASSERT(!m_inverted);
m_inverted = true;
}
bool inverted() const { return m_inverted; }
unsigned bitCount() const
{
return WTF::bitCount(m_characters[0]) + WTF::bitCount(m_characters[1]);
}
bool operator==(const CharacterSet& other) const
{
return other.m_inverted == m_inverted
&& other.m_characters[0] == m_characters[0]
&& other.m_characters[1] == m_characters[1];
}
unsigned hash() const
{
return computeHash(m_inverted, m_characters);
}
private:
bool m_inverted { false };
std::array<uint64_t, 2> m_characters { 0, 0 };
};
struct Group {
Vector<Term> terms;
bool operator==(const Group& other) const
{
return other.terms == terms;
}
unsigned hash() const
{
unsigned hash = 6421749;
for (const Term& term : terms) {
unsigned termHash = term.hash();
hash = (hash << 16) ^ ((termHash << 11) ^ hash);
hash += hash >> 11;
}
return hash;
}
};
union AtomData {
AtomData()
: invalidTerm(0)
{
}
~AtomData()
{
}
char invalidTerm;
CharacterSet characterSet;
Group group;
} m_atomData;
};
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
inline String quantifierToString(AtomQuantifier quantifier)
{
switch (quantifier) {
case AtomQuantifier::One:
return "";
case AtomQuantifier::ZeroOrOne:
return "?";
case AtomQuantifier::ZeroOrMore:
return "*";
case AtomQuantifier::OneOrMore:
return "+";
}
}
inline String Term::toString() const
{
switch (m_termType) {
case TermType::Empty:
return "(Empty)";
case TermType::CharacterSet: {
StringBuilder builder;
builder.append('[');
for (UChar c = 0; c < 128; c++) {
if (m_atomData.characterSet.get(c)) {
if (isASCIIPrintable(c) && !isASCIISpace(c))
builder.append(c);
else
builder.append("\\u", c);
}
}
builder.append(']');
builder.append(quantifierToString(m_quantifier));
return builder.toString();
}
case TermType::Group: {
StringBuilder builder;
builder.append('(');
for (const Term& term : m_atomData.group.terms)
builder.append(term.toString());
builder.append(')');
builder.append(quantifierToString(m_quantifier));
return builder.toString();
}
}
}
#endif
inline Term::Term()
{
}
inline Term::Term(char character, bool isCaseSensitive)
: m_termType(TermType::CharacterSet)
{
new (NotNull, &m_atomData.characterSet) CharacterSet();
addCharacter(character, isCaseSensitive);
}
inline Term::Term(UniversalTransitionTag)
: m_termType(TermType::CharacterSet)
{
new (NotNull, &m_atomData.characterSet) CharacterSet();
for (UChar i = 1; i < 128; ++i)
m_atomData.characterSet.set(i);
}
inline Term::Term(CharacterSetTermTag, bool isInverted)
: m_termType(TermType::CharacterSet)
{
new (NotNull, &m_atomData.characterSet) CharacterSet();
if (isInverted)
m_atomData.characterSet.invert();
}
inline Term::Term(GroupTermTag)
: m_termType(TermType::Group)
{
new (NotNull, &m_atomData.group) Group();
}
inline Term::Term(EndOfLineAssertionTermTag)
: Term(CharacterSetTerm, false)
{
m_atomData.characterSet.set(0);
}
inline Term::Term(const Term& other)
: m_termType(other.m_termType)
, m_quantifier(other.m_quantifier)
{
switch (m_termType) {
case TermType::Empty:
break;
case TermType::CharacterSet:
new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
break;
case TermType::Group:
new (NotNull, &m_atomData.group) Group(other.m_atomData.group);
break;
}
}
inline Term::Term(Term&& other)
: m_termType(WTFMove(other.m_termType))
, m_quantifier(WTFMove(other.m_quantifier))
{
switch (m_termType) {
case TermType::Empty:
break;
case TermType::CharacterSet:
new (NotNull, &m_atomData.characterSet) CharacterSet(WTFMove(other.m_atomData.characterSet));
break;
case TermType::Group:
new (NotNull, &m_atomData.group) Group(WTFMove(other.m_atomData.group));
break;
}
other.destroy();
}
inline Term::Term(EmptyValueTag)
: m_termType(TermType::Empty)
{
}
inline Term::~Term()
{
destroy();
}
inline bool Term::isValid() const
{
return m_termType != TermType::Empty;
}
inline void Term::addCharacter(UChar character, bool isCaseSensitive)
{
ASSERT(isASCII(character));
ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
if (m_termType != TermType::CharacterSet)
return;
if (isCaseSensitive || !isASCIIAlpha(character))
m_atomData.characterSet.set(character);
else {
m_atomData.characterSet.set(toASCIIUpper(character));
m_atomData.characterSet.set(toASCIILower(character));
}
}
inline void Term::extendGroupSubpattern(const Term& term)
{
ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::Group);
if (m_termType != TermType::Group)
return;
m_atomData.group.terms.append(term);
}
inline void Term::quantify(const AtomQuantifier& quantifier)
{
ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
m_quantifier = quantifier;
}
inline ImmutableCharNFANodeBuilder Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ActionList& finalActions) const
{
ImmutableCharNFANodeBuilder newEnd(nfa);
generateGraph(nfa, source, newEnd.nodeId());
newEnd.setActions(finalActions.begin(), finalActions.end());
return newEnd;
}
inline void Term::generateGraph(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
{
ASSERT(isValid());
switch (m_quantifier) {
case AtomQuantifier::One: {
generateSubgraphForAtom(nfa, source, destination);
break;
}
case AtomQuantifier::ZeroOrOne: {
generateSubgraphForAtom(nfa, source, destination);
source.addEpsilonTransition(destination);
break;
}
case AtomQuantifier::ZeroOrMore: {
ImmutableCharNFANodeBuilder repeatStart(nfa);
source.addEpsilonTransition(repeatStart);
ImmutableCharNFANodeBuilder repeatEnd(nfa);
generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
repeatEnd.addEpsilonTransition(repeatStart);
repeatEnd.addEpsilonTransition(destination);
source.addEpsilonTransition(destination);
break;
}
case AtomQuantifier::OneOrMore: {
ImmutableCharNFANodeBuilder repeatStart(nfa);
source.addEpsilonTransition(repeatStart);
ImmutableCharNFANodeBuilder repeatEnd(nfa);
generateSubgraphForAtom(nfa, repeatStart, repeatEnd);
repeatEnd.addEpsilonTransition(repeatStart);
repeatEnd.addEpsilonTransition(destination);
break;
}
}
}
inline bool Term::isEndOfLineAssertion() const
{
return m_termType == TermType::CharacterSet && m_atomData.characterSet.bitCount() == 1 && m_atomData.characterSet.get(0);
}
inline bool Term::matchesAtLeastOneCharacter() const
{
ASSERT(isValid());
if (m_quantifier == AtomQuantifier::ZeroOrOne || m_quantifier == AtomQuantifier::ZeroOrMore)
return false;
if (isEndOfLineAssertion())
return false;
if (m_termType == TermType::Group) {
for (const Term& term : m_atomData.group.terms) {
if (term.matchesAtLeastOneCharacter())
return true;
}
return false;
}
return true;
}
inline bool Term::isKnownToMatchAnyString() const
{
ASSERT(isValid());
switch (m_termType) {
case TermType::Empty:
ASSERT_NOT_REACHED();
break;
case TermType::CharacterSet:
// ".*" is the only simple term matching any string.
return isUniversalTransition() && m_quantifier == AtomQuantifier::ZeroOrMore;
break;
case TermType::Group: {
// There are infinitely many ways to match anything with groups, we just handle simple cases
if (m_atomData.group.terms.size() != 1)
return false;
const Term& firstTermInGroup = m_atomData.group.terms.first();
// -(.*) with any quantifier.
if (firstTermInGroup.isKnownToMatchAnyString())
return true;
if (firstTermInGroup.isUniversalTransition()) {
// -(.)*, (.+)*, (.?)* etc.
if (m_quantifier == AtomQuantifier::ZeroOrMore)
return true;
// -(.+)?.
if (m_quantifier == AtomQuantifier::ZeroOrOne && firstTermInGroup.m_quantifier == AtomQuantifier::OneOrMore)
return true;
// -(.?)+.
if (m_quantifier == AtomQuantifier::OneOrMore && firstTermInGroup.m_quantifier == AtomQuantifier::ZeroOrOne)
return true;
}
break;
}
}
return false;
}
inline bool Term::hasFixedLength() const
{
ASSERT(isValid());
switch (m_termType) {
case TermType::Empty:
ASSERT_NOT_REACHED();
break;
case TermType::CharacterSet:
return m_quantifier == AtomQuantifier::One;
case TermType::Group: {
if (m_quantifier != AtomQuantifier::One)
return false;
for (const Term& term : m_atomData.group.terms) {
if (!term.hasFixedLength())
return false;
}
return true;
}
}
return false;
}
inline Term& Term::operator=(const Term& other)
{
destroy();
new (NotNull, this) Term(other);
return *this;
}
inline Term& Term::operator=(Term&& other)
{
destroy();
new (NotNull, this) Term(WTFMove(other));
return *this;
}
inline bool Term::operator==(const Term& other) const
{
if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
return false;
switch (m_termType) {
case TermType::Empty:
return true;
case TermType::CharacterSet:
return m_atomData.characterSet == other.m_atomData.characterSet;
case TermType::Group:
return m_atomData.group == other.m_atomData.group;
}
ASSERT_NOT_REACHED();
return false;
}
inline unsigned Term::hash() const
{
unsigned primary = static_cast<unsigned>(m_termType) << 16 | static_cast<unsigned>(m_quantifier);
unsigned secondary = 0;
switch (m_termType) {
case TermType::Empty:
secondary = 52184393;
break;
case TermType::CharacterSet:
secondary = m_atomData.characterSet.hash();
break;
case TermType::Group:
secondary = m_atomData.group.hash();
break;
}
return pairIntHash(primary, secondary);
}
inline bool Term::isEmptyValue() const
{
return m_termType == TermType::Empty;
}
inline bool Term::isUniversalTransition() const
{
ASSERT(isValid());
switch (m_termType) {
case TermType::Empty:
ASSERT_NOT_REACHED();
break;
case TermType::CharacterSet:
return (m_atomData.characterSet.inverted() && !m_atomData.characterSet.bitCount())
|| (!m_atomData.characterSet.inverted() && m_atomData.characterSet.bitCount() == 127 && !m_atomData.characterSet.get(0));
case TermType::Group:
return m_atomData.group.terms.size() == 1 && m_atomData.group.terms.first().isUniversalTransition();
}
return false;
}
inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, const ImmutableCharNFANodeBuilder& destination) const
{
generateSubgraphForAtom(nfa, source, destination.nodeId());
}
inline void Term::generateSubgraphForAtom(NFA& nfa, ImmutableCharNFANodeBuilder& source, uint32_t destination) const
{
switch (m_termType) {
case TermType::Empty:
ASSERT_NOT_REACHED();
source.addEpsilonTransition(destination);
break;
case TermType::CharacterSet: {
if (!m_atomData.characterSet.inverted()) {
UChar i = 0;
while (true) {
while (i < 128 && !m_atomData.characterSet.get(i))
++i;
if (i == 128)
break;
UChar start = i;
++i;
while (i < 128 && m_atomData.characterSet.get(i))
++i;
source.addTransition(start, i - 1, destination);
}
} else {
UChar i = 1;
while (true) {
while (i < 128 && m_atomData.characterSet.get(i))
++i;
if (i == 128)
break;
UChar start = i;
++i;
while (i < 128 && !m_atomData.characterSet.get(i))
++i;
source.addTransition(start, i - 1, destination);
}
}
break;
}
case TermType::Group: {
if (m_atomData.group.terms.isEmpty()) {
// FIXME: any kind of empty term could be avoided in the parser. This case should turned into an assertion.
source.addEpsilonTransition(destination);
return;
}
if (m_atomData.group.terms.size() == 1) {
m_atomData.group.terms.first().generateGraph(nfa, source, destination);
return;
}
ImmutableCharNFANodeBuilder lastTarget = m_atomData.group.terms.first().generateGraph(nfa, source, ActionList());
for (unsigned i = 1; i < m_atomData.group.terms.size() - 1; ++i) {
const Term& currentTerm = m_atomData.group.terms[i];
ImmutableCharNFANodeBuilder newNode = currentTerm.generateGraph(nfa, lastTarget, ActionList());
lastTarget = WTFMove(newNode);
}
const Term& lastTerm = m_atomData.group.terms.last();
lastTerm.generateGraph(nfa, lastTarget, destination);
break;
}
}
}
inline void Term::destroy()
{
switch (m_termType) {
case TermType::Empty:
break;
case TermType::CharacterSet:
m_atomData.characterSet.~CharacterSet();
break;
case TermType::Group:
m_atomData.group.~Group();
break;
}
m_termType = TermType::Empty;
}
#if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
inline size_t Term::memoryUsed() const
{
size_t extraMemory = 0;
if (m_termType == TermType::Group) {
for (const Term& term : m_atomData.group.terms)
extraMemory += term.memoryUsed();
}
return sizeof(Term) + extraMemory;
}
#endif
} // namespace ContentExtensions
} // namespace WebCore
#endif // ENABLE(CONTENT_EXTENSIONS)