<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[181282] trunk/Source/WebCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/181282">181282</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-03-09 14:07:19 -0700 (Mon, 09 Mar 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge TrivialAtom and CharacterSet into a Term abstraction, prepare Term for composition
https://bugs.webkit.org/show_bug.cgi?id=142429
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-03-09
Reviewed by Darin Adler.
This patch merges CharacterSet and Trivial atom into a new class: Term. A Term is
a combination of an Atom and one Quantifier.
With term being the basic block, we can use the PrefixTree for any construct,
greatly reducing the size of the NFA graph.
Term is built on top of an union holding the Atom storage. This is done in preparation
for more complicated Atoms like a disjunction.
Everything else is pretty much the same. BuildMode is gone since we use the prefix
tree for everything. FloatingAtomType is gone, a TrivialAtom is now represented
by a single character CharacterSet (or two for case insensitive).
* contentextensions/ContentExtensionParser.cpp:
(WebCore::ContentExtensions::parseRuleList):
* contentextensions/NFA.cpp:
(WebCore::ContentExtensions::NFA::addRuleId):
* contentextensions/URLFilterParser.cpp:
(WebCore::ContentExtensions::Term::Term):
(WebCore::ContentExtensions::Term::~Term):
(WebCore::ContentExtensions::Term::isValid):
(WebCore::ContentExtensions::Term::addCharacter):
(WebCore::ContentExtensions::Term::quantify):
(WebCore::ContentExtensions::Term::quantifier):
(WebCore::ContentExtensions::Term::isUniversalTransition):
(WebCore::ContentExtensions::Term::visitSimpleTransitions):
(WebCore::ContentExtensions::Term::operator=):
(WebCore::ContentExtensions::Term::operator==):
(WebCore::ContentExtensions::Term::hash):
(WebCore::ContentExtensions::Term::isEmptyValue):
(WebCore::ContentExtensions::Term::isDeletedValue):
(WebCore::ContentExtensions::Term::destroy):
(WebCore::ContentExtensions::Term::CharacterSet::operator==):
(WebCore::ContentExtensions::Term::CharacterSet::hash):
(WebCore::ContentExtensions::TermHash::hash):
(WebCore::ContentExtensions::TermHash::equal):
(WebCore::ContentExtensions::GraphBuilder::GraphBuilder):
(WebCore::ContentExtensions::GraphBuilder::finalize):
(WebCore::ContentExtensions::GraphBuilder::atomPatternCharacter):
(WebCore::ContentExtensions::GraphBuilder::atomBuiltInCharacterClass):
(WebCore::ContentExtensions::GraphBuilder::quantifyAtom):
(WebCore::ContentExtensions::GraphBuilder::atomCharacterClassBegin):
(WebCore::ContentExtensions::GraphBuilder::atomCharacterClassAtom):
(WebCore::ContentExtensions::GraphBuilder::atomCharacterClassRange):
(WebCore::ContentExtensions::GraphBuilder::addTransitions):
(WebCore::ContentExtensions::GraphBuilder::sinkFloatingTerm):
(WebCore::ContentExtensions::GraphBuilder::sinkFloatingTermIfNecessary):
(WebCore::ContentExtensions::URLFilterParser::URLFilterParser):
(WebCore::ContentExtensions::URLFilterParser::~URLFilterParser):
(WebCore::ContentExtensions::URLFilterParser::addPattern):
(WebCore::ContentExtensions::trivialAtomFromASCIICharacter): Deleted.
(WebCore::ContentExtensions::quantifyTrivialAtom): Deleted.
(WebCore::ContentExtensions::trivialAtomQuantifier): Deleted.
(WebCore::ContentExtensions::trivialAtomForNewlineClassIDBuiltin): Deleted.
(WebCore::ContentExtensions::GraphBuilder::sinkAtom): Deleted.
(WebCore::ContentExtensions::GraphBuilder::generateTransition): Deleted.
(WebCore::ContentExtensions::GraphBuilder::sinkTrivialAtom): Deleted.
(WebCore::ContentExtensions::GraphBuilder::sinkCharacterSet): Deleted.
(WebCore::ContentExtensions::GraphBuilder::sinkPendingAtomIfNecessary): Deleted.
* contentextensions/URLFilterParser.h:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWebCoreChangeLog">trunk/Source/WebCore/ChangeLog</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsContentExtensionParsercpp">trunk/Source/WebCore/contentextensions/ContentExtensionParser.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsNFAcpp">trunk/Source/WebCore/contentextensions/NFA.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsURLFilterParsercpp">trunk/Source/WebCore/contentextensions/URLFilterParser.cpp</a></li>
<li><a href="#trunkSourceWebCorecontentextensionsURLFilterParserh">trunk/Source/WebCore/contentextensions/URLFilterParser.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceWebCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/ChangeLog (181281 => 181282)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/ChangeLog 2015-03-09 20:51:51 UTC (rev 181281)
+++ trunk/Source/WebCore/ChangeLog 2015-03-09 21:07:19 UTC (rev 181282)
</span><span class="lines">@@ -1,3 +1,71 @@
</span><ins>+2015-03-09 Benjamin Poulain <bpoulain@apple.com>
+
+ Merge TrivialAtom and CharacterSet into a Term abstraction, prepare Term for composition
+ https://bugs.webkit.org/show_bug.cgi?id=142429
+
+ Reviewed by Darin Adler.
+
+ This patch merges CharacterSet and Trivial atom into a new class: Term. A Term is
+ a combination of an Atom and one Quantifier.
+
+ With term being the basic block, we can use the PrefixTree for any construct,
+ greatly reducing the size of the NFA graph.
+
+ Term is built on top of an union holding the Atom storage. This is done in preparation
+ for more complicated Atoms like a disjunction.
+
+ Everything else is pretty much the same. BuildMode is gone since we use the prefix
+ tree for everything. FloatingAtomType is gone, a TrivialAtom is now represented
+ by a single character CharacterSet (or two for case insensitive).
+
+ * contentextensions/ContentExtensionParser.cpp:
+ (WebCore::ContentExtensions::parseRuleList):
+ * contentextensions/NFA.cpp:
+ (WebCore::ContentExtensions::NFA::addRuleId):
+ * contentextensions/URLFilterParser.cpp:
+ (WebCore::ContentExtensions::Term::Term):
+ (WebCore::ContentExtensions::Term::~Term):
+ (WebCore::ContentExtensions::Term::isValid):
+ (WebCore::ContentExtensions::Term::addCharacter):
+ (WebCore::ContentExtensions::Term::quantify):
+ (WebCore::ContentExtensions::Term::quantifier):
+ (WebCore::ContentExtensions::Term::isUniversalTransition):
+ (WebCore::ContentExtensions::Term::visitSimpleTransitions):
+ (WebCore::ContentExtensions::Term::operator=):
+ (WebCore::ContentExtensions::Term::operator==):
+ (WebCore::ContentExtensions::Term::hash):
+ (WebCore::ContentExtensions::Term::isEmptyValue):
+ (WebCore::ContentExtensions::Term::isDeletedValue):
+ (WebCore::ContentExtensions::Term::destroy):
+ (WebCore::ContentExtensions::Term::CharacterSet::operator==):
+ (WebCore::ContentExtensions::Term::CharacterSet::hash):
+ (WebCore::ContentExtensions::TermHash::hash):
+ (WebCore::ContentExtensions::TermHash::equal):
+ (WebCore::ContentExtensions::GraphBuilder::GraphBuilder):
+ (WebCore::ContentExtensions::GraphBuilder::finalize):
+ (WebCore::ContentExtensions::GraphBuilder::atomPatternCharacter):
+ (WebCore::ContentExtensions::GraphBuilder::atomBuiltInCharacterClass):
+ (WebCore::ContentExtensions::GraphBuilder::quantifyAtom):
+ (WebCore::ContentExtensions::GraphBuilder::atomCharacterClassBegin):
+ (WebCore::ContentExtensions::GraphBuilder::atomCharacterClassAtom):
+ (WebCore::ContentExtensions::GraphBuilder::atomCharacterClassRange):
+ (WebCore::ContentExtensions::GraphBuilder::addTransitions):
+ (WebCore::ContentExtensions::GraphBuilder::sinkFloatingTerm):
+ (WebCore::ContentExtensions::GraphBuilder::sinkFloatingTermIfNecessary):
+ (WebCore::ContentExtensions::URLFilterParser::URLFilterParser):
+ (WebCore::ContentExtensions::URLFilterParser::~URLFilterParser):
+ (WebCore::ContentExtensions::URLFilterParser::addPattern):
+ (WebCore::ContentExtensions::trivialAtomFromASCIICharacter): Deleted.
+ (WebCore::ContentExtensions::quantifyTrivialAtom): Deleted.
+ (WebCore::ContentExtensions::trivialAtomQuantifier): Deleted.
+ (WebCore::ContentExtensions::trivialAtomForNewlineClassIDBuiltin): Deleted.
+ (WebCore::ContentExtensions::GraphBuilder::sinkAtom): Deleted.
+ (WebCore::ContentExtensions::GraphBuilder::generateTransition): Deleted.
+ (WebCore::ContentExtensions::GraphBuilder::sinkTrivialAtom): Deleted.
+ (WebCore::ContentExtensions::GraphBuilder::sinkCharacterSet): Deleted.
+ (WebCore::ContentExtensions::GraphBuilder::sinkPendingAtomIfNecessary): Deleted.
+ * contentextensions/URLFilterParser.h:
+
</ins><span class="cx"> 2015-03-09 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> Fix the !ENABLE(WEBGL) build after r180609
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsContentExtensionParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/ContentExtensionParser.cpp (181281 => 181282)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/ContentExtensionParser.cpp 2015-03-09 20:51:51 UTC (rev 181281)
+++ trunk/Source/WebCore/contentextensions/ContentExtensionParser.cpp 2015-03-09 21:07:19 UTC (rev 181282)
</span><span class="lines">@@ -188,7 +188,7 @@
</span><span class="cx">
</span><span class="cx"> #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
</span><span class="cx"> double loadExtensionEndTime = monotonicallyIncreasingTime();
</span><del>- dataLogF("Time spent loading extension %s: %f\n", identifier.utf8().data(), (loadExtensionEndTime - loadExtensionStartTime));
</del><ins>+ dataLogF("Time spent loading extension %f\n", (loadExtensionEndTime - loadExtensionStartTime));
</ins><span class="cx"> #endif
</span><span class="cx">
</span><span class="cx"> return ruleList;
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsNFAcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/NFA.cpp (181281 => 181282)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/NFA.cpp 2015-03-09 20:51:51 UTC (rev 181281)
+++ trunk/Source/WebCore/contentextensions/NFA.cpp 2015-03-09 21:07:19 UTC (rev 181282)
</span><span class="lines">@@ -105,8 +105,8 @@
</span><span class="cx">
</span><span class="cx"> void NFA::addRuleId(unsigned node, uint64_t ruleId)
</span><span class="cx"> {
</span><del>- ASSERT(!m_nodes[node].ruleIds.contains(ruleId));
- m_nodes[node].ruleIds.append(ruleId);
</del><ins>+ if (!m_nodes[node].ruleIds.contains(ruleId))
+ m_nodes[node].ruleIds.append(ruleId);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> static void printRange(bool firstRange, uint16_t rangeStart, uint16_t rangeEnd, uint16_t epsilonTransitionCharacter)
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsURLFilterParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/URLFilterParser.cpp (181281 => 181282)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/URLFilterParser.cpp 2015-03-09 20:51:51 UTC (rev 181281)
+++ trunk/Source/WebCore/contentextensions/URLFilterParser.cpp 2015-03-09 21:07:19 UTC (rev 181282)
</span><span class="lines">@@ -36,68 +36,277 @@
</span><span class="cx">
</span><span class="cx"> namespace ContentExtensions {
</span><span class="cx">
</span><del>-const uint16_t hasNonCharacterMask = 0x0080;
-const uint16_t characterMask = 0x0007F;
-const uint16_t newlineClassIDBuiltinMask = 0x100;
-const uint16_t caseInsensitiveMask = 0x200;
</del><ins>+enum class AtomQuantifier : uint8_t {
+ One,
+ ZeroOrOne,
+ ZeroOrMore,
+ OneOrMore
+};
</ins><span class="cx">
</span><del>-static TrivialAtom trivialAtomFromASCIICharacter(char character, bool caseSensitive)
-{
- ASSERT(isASCII(character));
</del><ins>+class Term {
+public:
+ Term()
+ {
+ }
</ins><span class="cx">
</span><del>- if (caseSensitive || !isASCIIAlpha(character))
- return static_cast<uint16_t>(character);
</del><ins>+ Term(char character, bool isCaseSensitive)
+ : m_termType(TermType::CharacterSet)
+ {
+ new (NotNull, &m_atomData.characterSet) CharacterSet();
+ addCharacter(character, isCaseSensitive);
+ }
</ins><span class="cx">
</span><del>- return static_cast<uint16_t>(toASCIILower(character)) | caseInsensitiveMask;
-}
</del><ins>+ enum UniversalTransitionTag { UniversalTransition };
+ explicit Term(UniversalTransitionTag)
+ : m_termType(TermType::CharacterSet)
+ {
+ new (NotNull, &m_atomData.characterSet) CharacterSet();
+ for (unsigned i = 0; i < 128; ++i)
+ m_atomData.characterSet.characters.set(i);
+ }
</ins><span class="cx">
</span><del>-enum class AtomQuantifier : uint16_t {
- One = 0,
- ZeroOrOne = 0x1000,
- ZeroOrMore = 0x2000,
- OneOrMore = 0x4000
-};
</del><ins>+ enum CharacterSetTermTag { CharacterSetTerm };
+ Term(CharacterSetTermTag, bool isInverted)
+ : m_termType(TermType::CharacterSet)
+ {
+ new (NotNull, &m_atomData.characterSet) CharacterSet();
+ m_atomData.characterSet.inverted = isInverted;
+ }
</ins><span class="cx">
</span><del>-static void quantifyTrivialAtom(TrivialAtom& trivialAtom, AtomQuantifier quantifier)
-{
- ASSERT(trivialAtom & (hasNonCharacterMask | characterMask));
- ASSERT(!(trivialAtom & 0xf000));
- trivialAtom |= static_cast<uint16_t>(quantifier);
-}
</del><ins>+ Term(const Term& other)
+ : m_termType(other.m_termType)
+ , m_quantifier(other.m_quantifier)
+ {
+ switch (m_termType) {
+ case TermType::Empty:
+ case TermType::Deleted:
+ break;
+ case TermType::CharacterSet:
+ new (NotNull, &m_atomData.characterSet) CharacterSet(other.m_atomData.characterSet);
+ break;
+ }
+ }
</ins><span class="cx">
</span><del>-static AtomQuantifier trivialAtomQuantifier(TrivialAtom trivialAtom)
-{
- switch (trivialAtom & 0xf000) {
- case static_cast<unsigned>(AtomQuantifier::One):
- return AtomQuantifier::One;
- case static_cast<unsigned>(AtomQuantifier::ZeroOrOne):
- return AtomQuantifier::ZeroOrOne;
- case static_cast<unsigned>(AtomQuantifier::ZeroOrMore):
- return AtomQuantifier::ZeroOrMore;
- case static_cast<unsigned>(AtomQuantifier::OneOrMore):
- return AtomQuantifier::OneOrMore;
</del><ins>+ Term(Term&& other)
+ : m_termType(WTF::move(other.m_termType))
+ , m_quantifier(WTF::move(other.m_quantifier))
+ {
+ switch (m_termType) {
+ case TermType::Empty:
+ case TermType::Deleted:
+ break;
+ case TermType::CharacterSet:
+ new (NotNull, &m_atomData.characterSet) CharacterSet(WTF::move(other.m_atomData.characterSet));
+ break;
+ }
+ other.destroy();
</ins><span class="cx"> }
</span><del>- ASSERT_NOT_REACHED();
- return AtomQuantifier::One;
-}
</del><span class="cx">
</span><del>-static TrivialAtom trivialAtomForNewlineClassIDBuiltin()
-{
- return hasNonCharacterMask | newlineClassIDBuiltinMask;
-}
</del><ins>+ enum EmptyValueTag { EmptyValue };
+ Term(EmptyValueTag)
+ : m_termType(TermType::Empty)
+ {
+ }
</ins><span class="cx">
</span><del>-class GraphBuilder {
- struct BoundedSubGraph {
- unsigned start;
- unsigned end;
</del><ins>+ enum DeletedValueTag { DeletedValue };
+ Term(DeletedValueTag)
+ : m_termType(TermType::Deleted)
+ {
+ }
+
+ ~Term()
+ {
+ destroy();
+ }
+
+ bool isValid() const
+ {
+ return m_termType != TermType::Empty && m_termType != TermType::Deleted;
+ }
+
+ void 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.characters.set(character);
+ else {
+ m_atomData.characterSet.characters.set(toASCIIUpper(character));
+ m_atomData.characterSet.characters.set(toASCIILower(character));
+ }
+ }
+
+ void quantify(const AtomQuantifier& quantifier)
+ {
+ ASSERT_WITH_MESSAGE(m_quantifier == AtomQuantifier::One, "Transition to quantified term should only happen once.");
+ m_quantifier = quantifier;
+ }
+
+ AtomQuantifier quantifier() const
+ {
+ return m_quantifier;
+ }
+
+ bool isUniversalTransition() const
+ {
+ return m_termType == TermType::CharacterSet
+ && ((m_atomData.characterSet.inverted && !m_atomData.characterSet.characters.bitCount())
+ || (!m_atomData.characterSet.inverted && m_atomData.characterSet.characters.bitCount() == 128));
+ }
+
+ void visitSimpleTransitions(std::function<void(char)> visitor) const
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(m_termType == TermType::CharacterSet);
+ if (m_termType != TermType::CharacterSet)
+ return;
+
+ if (!m_atomData.characterSet.inverted) {
+ for (const auto& characterIterator : m_atomData.characterSet.characters.setBits())
+ visitor(static_cast<char>(characterIterator));
+ } else {
+ for (unsigned i = 1; i < m_atomData.characterSet.characters.size(); ++i) {
+ if (m_atomData.characterSet.characters.get(i))
+ continue;
+ visitor(static_cast<char>(i));
+ }
+ }
+ }
+
+ Term& operator=(const Term& other)
+ {
+ destroy();
+ new (NotNull, this) Term(other);
+ return *this;
+ }
+
+ Term& operator=(Term&& other)
+ {
+ destroy();
+ new (NotNull, this) Term(WTF::move(other));
+ return *this;
+ }
+
+ bool operator==(const Term& other) const
+ {
+ if (other.m_termType != m_termType || other.m_quantifier != m_quantifier)
+ return false;
+
+ switch (m_termType) {
+ case TermType::Empty:
+ case TermType::Deleted:
+ return true;
+ case TermType::CharacterSet:
+ return m_atomData.characterSet == other.m_atomData.characterSet;
+ }
+ ASSERT_NOT_REACHED();
+ return false;
+ }
+
+ unsigned 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::Deleted:
+ secondary = 40342988;
+ break;
+ case TermType::CharacterSet:
+ secondary = m_atomData.characterSet.hash();
+ break;
+ }
+ return WTF::pairIntHash(primary, secondary);
+ }
+
+ bool isEmptyValue() const
+ {
+ return m_termType == TermType::Empty;
+ }
+
+ bool isDeletedValue() const
+ {
+ return m_termType == TermType::Deleted;
+ }
+
+private:
+ void destroy()
+ {
+ switch (m_termType) {
+ case TermType::Empty:
+ case TermType::Deleted:
+ break;
+ case TermType::CharacterSet:
+ m_atomData.characterSet.~CharacterSet();
+ break;
+ }
+ m_termType = TermType::Deleted;
+ }
+
+ enum class TermType : uint8_t {
+ Empty,
+ Deleted,
+ CharacterSet
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+ TermType m_termType { TermType::Empty };
+ AtomQuantifier m_quantifier { AtomQuantifier::One };
+
+ struct CharacterSet {
+ bool inverted { false };
+ BitVector characters { 128 };
+
+ bool operator==(const CharacterSet& other) const
+ {
+ return other.inverted == inverted && other.characters == characters;
+ }
+
+ unsigned hash() const
+ {
+ return WTF::pairIntHash(inverted, characters.hash());
+ }
+ };
+
+ union AtomData {
+ AtomData()
+ : invalidTerm(0)
+ {
+ }
+ ~AtomData()
+ {
+ }
+
+ char invalidTerm;
+ CharacterSet characterSet;
+ } m_atomData;
+};
+
+struct TermHash {
+ static unsigned hash(const Term& term) { return term.hash(); }
+ static bool equal(const Term& a, const Term& b) { return a == b; }
+ static const bool safeToCompareToEmptyOrDeleted = true;
+};
+
+struct TermHashTraits : public WTF::CustomHashTraits<Term> { };
+
+struct PrefixTreeEntry {
+ unsigned nfaNode;
+ HashMap<Term, std::unique_ptr<PrefixTreeEntry>, TermHash, TermHashTraits> nextPattern;
+};
+
+class GraphBuilder {
</ins><span class="cx"> public:
</span><span class="cx"> GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, bool patternIsCaseSensitive, uint64_t patternId)
</span><span class="cx"> : m_nfa(nfa)
</span><span class="cx"> , m_patternIsCaseSensitive(patternIsCaseSensitive)
</span><span class="cx"> , m_patternId(patternId)
</span><del>- , m_activeGroup({ nfa.root(), nfa.root() })
</del><ins>+ , m_subtreeStart(nfa.root())
+ , m_subtreeEnd(nfa.root())
</ins><span class="cx"> , m_lastPrefixTreeEntry(&prefixTreeRoot)
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="lines">@@ -107,10 +316,10 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- sinkPendingAtomIfNecessary();
</del><ins>+ sinkFloatingTermIfNecessary();
</ins><span class="cx">
</span><del>- if (m_activeGroup.start != m_activeGroup.end)
- m_nfa.setFinal(m_activeGroup.end, m_patternId);
</del><ins>+ if (m_subtreeStart != m_subtreeEnd)
+ m_nfa.setFinal(m_subtreeEnd, m_patternId);
</ins><span class="cx"> else
</span><span class="cx"> fail(ASCIILiteral("The pattern cannot match anything."));
</span><span class="cx"> }
</span><span class="lines">@@ -130,13 +339,11 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- sinkPendingAtomIfNecessary();
- ASSERT(m_floatingAtomType == FloatingAtomType::Invalid);
- ASSERT(!m_pendingTrivialAtom);
</del><ins>+ sinkFloatingTermIfNecessary();
+ ASSERT(!m_floatingTerm.isValid());
</ins><span class="cx">
</span><span class="cx"> char asciiChararacter = static_cast<char>(character);
</span><del>- m_pendingTrivialAtom = trivialAtomFromASCIICharacter(asciiChararacter, m_patternIsCaseSensitive);
- m_floatingAtomType = FloatingAtomType::Trivial;
</del><ins>+ m_floatingTerm = Term(asciiChararacter, m_patternIsCaseSensitive);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
</span><span class="lines">@@ -144,14 +351,12 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- sinkPendingAtomIfNecessary();
- ASSERT(m_floatingAtomType == FloatingAtomType::Invalid);
- ASSERT(!m_pendingTrivialAtom);
</del><ins>+ sinkFloatingTermIfNecessary();
+ ASSERT(!m_floatingTerm.isValid());
</ins><span class="cx">
</span><del>- if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
- m_pendingTrivialAtom = trivialAtomForNewlineClassIDBuiltin();
- m_floatingAtomType = FloatingAtomType::Trivial;
- } else
</del><ins>+ if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted)
+ m_floatingTerm = Term(Term::UniversalTransition);
+ else
</ins><span class="cx"> fail(ASCIILiteral("Character class is not supported."));
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -160,34 +365,17 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- switch (m_floatingAtomType) {
- case FloatingAtomType::Invalid:
- fail(ASCIILiteral("Quantifier without corresponding atom to quantify."));
- break;
</del><ins>+ if (!m_floatingTerm.isValid())
+ fail(ASCIILiteral("Quantifier without corresponding term to quantify."));
</ins><span class="cx">
</span><del>- case FloatingAtomType::Trivial:
- if (!minimum && maximum == 1)
- quantifyTrivialAtom(m_pendingTrivialAtom, AtomQuantifier::ZeroOrOne);
- else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
- quantifyTrivialAtom(m_pendingTrivialAtom, AtomQuantifier::ZeroOrMore);
- else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
- quantifyTrivialAtom(m_pendingTrivialAtom, AtomQuantifier::OneOrMore);
- else
- fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
- break;
- case FloatingAtomType::CharacterSet: {
- ASSERT(m_characterSetQuantifier == AtomQuantifier::One);
- if (!minimum && maximum == 1)
- m_characterSetQuantifier = AtomQuantifier::ZeroOrOne;
- else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
- m_characterSetQuantifier = AtomQuantifier::ZeroOrMore;
- else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
- m_characterSetQuantifier = AtomQuantifier::OneOrMore;
- else
- fail(ASCIILiteral("Arbitrary character set repetitions are not supported."));
- break;
- }
- }
</del><ins>+ if (!minimum && maximum == 1)
+ m_floatingTerm.quantify(AtomQuantifier::ZeroOrOne);
+ else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
+ m_floatingTerm.quantify(AtomQuantifier::ZeroOrMore);
+ else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
+ m_floatingTerm.quantify(AtomQuantifier::OneOrMore);
+ else
+ fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void atomBackReference(unsigned)
</span><span class="lines">@@ -215,16 +403,10 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- sinkPendingAtomIfNecessary();
</del><ins>+ sinkFloatingTermIfNecessary();
+ ASSERT(!m_floatingTerm.isValid());
</ins><span class="cx">
</span><del>- ASSERT_WITH_MESSAGE(!m_pendingCharacterSet.bitCount(), "We should not have nested character classes.");
- ASSERT(m_floatingAtomType == FloatingAtomType::Invalid);
-
- m_buildMode = BuildMode::DirectGeneration;
- m_lastPrefixTreeEntry = nullptr;
-
- m_isInvertedCharacterSet = inverted;
- m_floatingAtomType = FloatingAtomType::CharacterSet;
</del><ins>+ m_floatingTerm = Term(Term::CharacterSetTerm, inverted);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void atomCharacterClassAtom(UChar character)
</span><span class="lines">@@ -232,13 +414,12 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- ASSERT(m_floatingAtomType == FloatingAtomType::CharacterSet);
-
</del><span class="cx"> if (!isASCII(character)) {
</span><span class="cx"> fail(ASCIILiteral("Non ASCII Character in a character set."));
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>- m_pendingCharacterSet.set(character);
</del><ins>+
+ m_floatingTerm.addCharacter(character, m_patternIsCaseSensitive);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void atomCharacterClassRange(UChar a, UChar b)
</span><span class="lines">@@ -246,14 +427,13 @@
</span><span class="cx"> if (hasError())
</span><span class="cx"> return;
</span><span class="cx">
</span><del>- ASSERT(m_floatingAtomType == FloatingAtomType::CharacterSet);
-
</del><span class="cx"> if (!a || !b || !isASCII(a) || !isASCII(b)) {
</span><span class="cx"> fail(ASCIILiteral("Non ASCII Character in a character range of a character set."));
</span><span class="cx"> return;
</span><span class="cx"> }
</span><ins>+
</ins><span class="cx"> for (unsigned i = a; i <= b; ++i)
</span><del>- m_pendingCharacterSet.set(i);
</del><ins>+ m_floatingTerm.addCharacter(static_cast<UChar>(i), m_patternIsCaseSensitive);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void atomCharacterClassEnd()
</span><span class="lines">@@ -303,20 +483,31 @@
</span><span class="cx"> m_errorMessage = errorMessage;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- BoundedSubGraph sinkAtom(std::function<void(unsigned, unsigned)> transitionFunction, AtomQuantifier quantifier, unsigned start)
</del><ins>+ void addTransitions(unsigned source, unsigned target)
</ins><span class="cx"> {
</span><del>- switch (quantifier) {
</del><ins>+ auto visitor = [this, source, target](char character) {
+ if (m_floatingTerm.isUniversalTransition())
+ m_nfa.addTransitionsOnAnyCharacter(source, target);
+ else
+ m_nfa.addTransition(source, target, character);
+ };
+ m_floatingTerm.visitSimpleTransitions(visitor);
+ }
+
+ unsigned sinkFloatingTerm(unsigned start)
+ {
+ switch (m_floatingTerm.quantifier()) {
</ins><span class="cx"> case AtomQuantifier::One: {
</span><span class="cx"> unsigned newEnd = m_nfa.createNode();
</span><span class="cx"> m_nfa.addRuleId(newEnd, m_patternId);
</span><del>- transitionFunction(start, newEnd);
- return { start, newEnd };
</del><ins>+ addTransitions(start, newEnd);
+ return newEnd;
</ins><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::ZeroOrOne: {
</span><span class="cx"> unsigned newEnd = m_nfa.createNode();
</span><span class="cx"> m_nfa.addRuleId(newEnd, m_patternId);
</span><del>- transitionFunction(start, newEnd);
- return { start, newEnd };
</del><ins>+ addTransitions(start, newEnd);
+ return newEnd;
</ins><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::ZeroOrMore: {
</span><span class="cx"> unsigned repeatStart = m_nfa.createNode();
</span><span class="lines">@@ -324,7 +515,7 @@
</span><span class="cx"> unsigned repeatEnd = m_nfa.createNode();
</span><span class="cx"> m_nfa.addRuleId(repeatEnd, m_patternId);
</span><span class="cx">
</span><del>- transitionFunction(repeatStart, repeatEnd);
</del><ins>+ addTransitions(repeatStart, repeatEnd);
</ins><span class="cx"> m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
</span><span class="cx">
</span><span class="cx"> m_nfa.addEpsilonTransition(start, repeatStart);
</span><span class="lines">@@ -333,7 +524,7 @@
</span><span class="cx"> m_nfa.addRuleId(kleenEnd, m_patternId);
</span><span class="cx"> m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
</span><span class="cx"> m_nfa.addEpsilonTransition(start, kleenEnd);
</span><del>- return { start, kleenEnd };
</del><ins>+ return kleenEnd;
</ins><span class="cx"> }
</span><span class="cx"> case AtomQuantifier::OneOrMore: {
</span><span class="cx"> unsigned repeatStart = m_nfa.createNode();
</span><span class="lines">@@ -341,7 +532,7 @@
</span><span class="cx"> unsigned repeatEnd = m_nfa.createNode();
</span><span class="cx"> m_nfa.addRuleId(repeatEnd, m_patternId);
</span><span class="cx">
</span><del>- transitionFunction(repeatStart, repeatEnd);
</del><ins>+ addTransitions(repeatStart, repeatEnd);
</ins><span class="cx"> m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
</span><span class="cx">
</span><span class="cx"> m_nfa.addEpsilonTransition(start, repeatStart);
</span><span class="lines">@@ -349,174 +540,71 @@
</span><span class="cx"> unsigned afterRepeat = m_nfa.createNode();
</span><span class="cx"> m_nfa.addRuleId(afterRepeat, m_patternId);
</span><span class="cx"> m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
</span><del>- return { start, afterRepeat };
</del><ins>+ return afterRepeat;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void generateTransition(TrivialAtom trivialAtom, unsigned source, unsigned target)
</del><ins>+ void sinkFloatingTermIfNecessary()
</ins><span class="cx"> {
</span><del>- if (trivialAtom & hasNonCharacterMask) {
- ASSERT(trivialAtom & newlineClassIDBuiltinMask);
- m_nfa.addTransitionsOnAnyCharacter(source, target);
- } else {
- if (trivialAtom & caseInsensitiveMask) {
- char character = static_cast<char>(trivialAtom & characterMask);
- m_nfa.addTransition(source, target, character);
- m_nfa.addTransition(source, target, toASCIIUpper(character));
- } else
- m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
- }
- }
</del><ins>+ if (!m_floatingTerm.isValid())
+ return;
</ins><span class="cx">
</span><del>- BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
- {
- auto transitionFunction = [this, trivialAtom](unsigned source, unsigned target)
- {
- generateTransition(trivialAtom, source, target);
- };
- return sinkAtom(transitionFunction, trivialAtomQuantifier(trivialAtom), start);
- }
</del><ins>+ ASSERT(m_lastPrefixTreeEntry);
</ins><span class="cx">
</span><del>- void generateTransition(const BitVector& characterSet, bool isInverted, unsigned source, unsigned target)
- {
- ASSERT(characterSet.bitCount());
- if (!isInverted) {
- for (const auto& characterIterator : characterSet.setBits()) {
- char character = static_cast<char>(characterIterator);
- if (!m_patternIsCaseSensitive && isASCIIAlpha(character)) {
- m_nfa.addTransition(source, target, toASCIIUpper(character));
- m_nfa.addTransition(source, target, toASCIILower(character));
- } else
- m_nfa.addTransition(source, target, character);
- }
</del><ins>+ auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_floatingTerm);
+ if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
+ m_lastPrefixTreeEntry = nextEntry->value.get();
+ m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
</ins><span class="cx"> } else {
</span><del>- for (unsigned i = 1; i < characterSet.size(); ++i) {
- if (characterSet.get(i))
- continue;
- char character = static_cast<char>(i);
</del><ins>+ std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
</ins><span class="cx">
</span><del>- if (!m_patternIsCaseSensitive && (characterSet.get(toASCIIUpper(character)) || characterSet.get(toASCIILower(character))))
- continue;
</del><ins>+ unsigned newEnd = sinkFloatingTerm(m_lastPrefixTreeEntry->nfaNode);
+ nextPrefixTreeEntry->nfaNode = newEnd;
</ins><span class="cx">
</span><del>- m_nfa.addTransition(source, target, character);
- }
- }
- }
</del><ins>+ auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_floatingTerm, WTF::move(nextPrefixTreeEntry));
+ ASSERT(addResult.isNewEntry);
</ins><span class="cx">
</span><del>- BoundedSubGraph sinkCharacterSet(const BitVector& characterSet, bool isInverted, unsigned start)
- {
- auto transitionFunction = [this, &characterSet, isInverted](unsigned source, unsigned target)
- {
- generateTransition(characterSet, isInverted, source, target);
- };
- return sinkAtom(transitionFunction, m_characterSetQuantifier, start);
- }
-
- void sinkPendingAtomIfNecessary()
- {
- if (m_floatingAtomType == FloatingAtomType::Invalid)
- return;
-
- switch (m_buildMode) {
- case BuildMode::PrefixTree: {
- ASSERT(m_lastPrefixTreeEntry);
- ASSERT_WITH_MESSAGE(m_floatingAtomType == FloatingAtomType::Trivial, "Only trivial atoms are handled with a prefix tree.");
-
- auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
- if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
- m_lastPrefixTreeEntry = nextEntry->value.get();
- m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
- } else {
- std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
-
- BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
- nextPrefixTreeEntry->nfaNode = newSubGraph.end;
-
- auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
- ASSERT(addResult.isNewEntry);
-
- if (!m_newPrefixSubtreeRoot) {
- m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
- m_newPrefixStaringPoint = m_pendingTrivialAtom;
- }
-
- m_lastPrefixTreeEntry = addResult.iterator->value.get();
</del><ins>+ if (!m_newPrefixSubtreeRoot) {
+ m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
+ m_newPrefixStaringPoint = m_floatingTerm;
</ins><span class="cx"> }
</span><del>- m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
- ASSERT(m_lastPrefixTreeEntry);
- break;
- }
- case BuildMode::DirectGeneration: {
- ASSERT(!m_lastPrefixTreeEntry);
</del><span class="cx">
</span><del>- switch (m_floatingAtomType) {
- case FloatingAtomType::Invalid:
- ASSERT_NOT_REACHED();
- break;
- case FloatingAtomType::Trivial: {
- BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_activeGroup.end);
- m_activeGroup.end = newSubGraph.end;
- break;
- }
- case FloatingAtomType::CharacterSet:
- if (!m_pendingCharacterSet.bitCount()) {
- fail(ASCIILiteral("Empty character set."));
- return;
- }
- BoundedSubGraph newSubGraph = sinkCharacterSet(m_pendingCharacterSet, m_isInvertedCharacterSet, m_activeGroup.end);
- m_activeGroup.end = newSubGraph.end;
-
- m_isInvertedCharacterSet = false;
- m_characterSetQuantifier = AtomQuantifier::One;
- m_pendingCharacterSet.clearAll();
- break;
- }
- break;
- }
</del><ins>+ m_lastPrefixTreeEntry = addResult.iterator->value.get();
</ins><span class="cx"> }
</span><ins>+ m_subtreeEnd = m_lastPrefixTreeEntry->nfaNode;
</ins><span class="cx">
</span><del>- m_pendingTrivialAtom = 0;
- m_floatingAtomType = FloatingAtomType::Invalid;
</del><ins>+ m_floatingTerm = Term();
+ ASSERT(m_lastPrefixTreeEntry);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> NFA& m_nfa;
</span><span class="cx"> bool m_patternIsCaseSensitive;
</span><span class="cx"> const uint64_t m_patternId;
</span><span class="cx">
</span><del>- BoundedSubGraph m_activeGroup;
</del><ins>+ unsigned m_subtreeStart { 0 };
+ unsigned m_subtreeEnd { 0 };
</ins><span class="cx">
</span><span class="cx"> PrefixTreeEntry* m_lastPrefixTreeEntry;
</span><del>- enum class FloatingAtomType {
- Invalid,
- Trivial,
- CharacterSet
- };
- FloatingAtomType m_floatingAtomType { FloatingAtomType::Invalid };
- TrivialAtom m_pendingTrivialAtom = 0;
</del><ins>+ Term m_floatingTerm;
</ins><span class="cx">
</span><del>- bool m_isInvertedCharacterSet { false };
- BitVector m_pendingCharacterSet { 128 };
- AtomQuantifier m_characterSetQuantifier { AtomQuantifier::One };
-
- enum class BuildMode {
- PrefixTree,
- DirectGeneration
- };
- BuildMode m_buildMode { BuildMode::PrefixTree };
-
</del><span class="cx"> PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
</span><del>- TrivialAtom m_newPrefixStaringPoint = 0;
</del><ins>+ Term m_newPrefixStaringPoint;
</ins><span class="cx">
</span><span class="cx"> String m_errorMessage;
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> URLFilterParser::URLFilterParser(NFA& nfa)
</span><span class="cx"> : m_nfa(nfa)
</span><ins>+ , m_prefixTreeRoot(std::make_unique<PrefixTreeEntry>())
</ins><span class="cx"> {
</span><del>- m_prefixTreeRoot.nfaNode = nfa.root();
</del><ins>+ m_prefixTreeRoot->nfaNode = nfa.root();
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+URLFilterParser::~URLFilterParser()
+{
+}
+
</ins><span class="cx"> String URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
</span><span class="cx"> {
</span><span class="cx"> if (!pattern.containsOnlyASCII())
</span><span class="lines">@@ -530,7 +618,7 @@
</span><span class="cx">
</span><span class="cx"> String error;
</span><span class="cx">
</span><del>- GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternIsCaseSensitive, patternId);
</del><ins>+ GraphBuilder graphBuilder(m_nfa, *m_prefixTreeRoot, patternIsCaseSensitive, patternId);
</ins><span class="cx"> error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
</span><span class="cx"> if (error.isNull())
</span><span class="cx"> graphBuilder.finalize();
</span></span></pre></div>
<a id="trunkSourceWebCorecontentextensionsURLFilterParserh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WebCore/contentextensions/URLFilterParser.h (181281 => 181282)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WebCore/contentextensions/URLFilterParser.h 2015-03-09 20:51:51 UTC (rev 181281)
+++ trunk/Source/WebCore/contentextensions/URLFilterParser.h 2015-03-09 21:07:19 UTC (rev 181282)
</span><span class="lines">@@ -37,22 +37,17 @@
</span><span class="cx">
</span><span class="cx"> class NFA;
</span><span class="cx">
</span><del>-typedef uint16_t TrivialAtom;
</del><ins>+struct PrefixTreeEntry;
</ins><span class="cx">
</span><del>-struct PrefixTreeEntry {
- unsigned nfaNode;
- HashMap<TrivialAtom, std::unique_ptr<PrefixTreeEntry>> nextPattern;
-};
-
-
</del><span class="cx"> class URLFilterParser {
</span><span class="cx"> public:
</span><span class="cx"> explicit URLFilterParser(NFA&);
</span><ins>+ ~URLFilterParser();
</ins><span class="cx"> String addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId);
</span><span class="cx">
</span><span class="cx"> private:
</span><span class="cx"> NFA& m_nfa;
</span><del>- PrefixTreeEntry m_prefixTreeRoot;
</del><ins>+ std::unique_ptr<PrefixTreeEntry> m_prefixTreeRoot;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // namespace ContentExtensions
</span></span></pre>
</div>
</div>
</body>
</html>