Source/WebCore/contentextensions/URLFilterParser.cpp

   1 /*
   2  * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "URLFilterParser.h"
  28
  29 #if ENABLE(CONTENT_EXTENSIONS)
  30
  31 #include "NFA.h"
  32 #include <JavaScriptCore/YarrParser.h>
  33
  34 namespace WebCore {
  35
  36 namespace ContentExtensions {
  37
  38 const uint16_t hasNonCharacterMask = 0x0080;
  39 const uint16_t characterMask = 0x0007F;
  40 const uint16_t newlineClassIDBuiltinMask = 0x100;
  41
  42 static TrivialAtom trivialAtomFromASCIICharacter(char character)
  43 {
  44     ASSERT(isASCII(character));
  45
  46     return static_cast<uint16_t>(character);
  47 }
  48
  49 enum class TrivialAtomQuantifier : uint16_t {
  50     ZeroOrOne = 0x1000,
  51     ZeroToMany = 0x2000,
  52     OneToMany = 0x4000
  53 };
  54
  55 static void quantifyTrivialAtom(TrivialAtom& trivialAtom, TrivialAtomQuantifier quantifier)
  56 {
  57     ASSERT(trivialAtom & (hasNonCharacterMask | characterMask));
  58     ASSERT(!(trivialAtom & 0xf000));
  59     trivialAtom |= static_cast<uint16_t>(quantifier);
  60 }
  61
  62 static TrivialAtom trivialAtomForNewlineClassIDBuiltin()
  63 {
  64     return hasNonCharacterMask | newlineClassIDBuiltinMask;
  65 }
  66
  67 class GraphBuilder {
  68 private:
  69     struct BoundedSubGraph {
  70         unsigned start;
  71         unsigned end;
  72     };
  73 public:
  74     GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, uint64_t patternId)
  75         : m_nfa(nfa)
  76         , m_patternId(patternId)
  77         , m_activeGroup({ nfa.root(), nfa.root() })
  78         , m_lastPrefixTreeEntry(&prefixTreeRoot)
  79     {
  80     }
  81
  82     void finalize()
  83     {
  84         if (hasError())
  85             return;
  86
  87         sinkPendingAtomIfNecessary();
  88
  89         if (m_activeGroup.start != m_activeGroup.end)
  90             m_nfa.setFinal(m_activeGroup.end, m_patternId);
  91         else
  92             fail(ASCIILiteral("The pattern cannot match anything."));
  93     }
  94
  95     const String& errorMessage() const
  96     {
  97         return m_errorMessage;
  98     }
  99
 100     void atomPatternCharacter(UChar character)
 101     {
 102         if (!isASCII(character)) {
 103             fail(ASCIILiteral("Only ASCII characters are supported in pattern."));
 104             return;
 105         }
 106
 107         if (hasError())
 108             return;
 109
 110         sinkPendingAtomIfNecessary();
 111
 112         char asciiChararacter = static_cast<char>(character);
 113         m_hasValidAtom = true;
 114
 115         ASSERT(m_lastPrefixTreeEntry);
 116         m_pendingTrivialAtom = trivialAtomFromASCIICharacter(asciiChararacter);
 117     }
 118
 119     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
 120     {
 121         if (hasError())
 122             return;
 123
 124         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
 125             m_hasValidAtom = true;
 126             ASSERT(m_lastPrefixTreeEntry);
 127             m_pendingTrivialAtom = trivialAtomForNewlineClassIDBuiltin();
 128         } else
 129             fail(ASCIILiteral("Character class is not supported."));
 130     }
 131
 132     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
 133     {
 134         if (hasError())
 135             return;
 136
 137         ASSERT(m_hasValidAtom);
 138         if (!m_hasValidAtom) {
 139             fail(ASCIILiteral("Quantifier without corresponding atom to quantify."));
 140             return;
 141         }
 142
 143         ASSERT(m_lastPrefixTreeEntry);
 144         if (!minimum && maximum == 1)
 145             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroOrOne);
 146         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
 147             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroToMany);
 148         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
 149             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::OneToMany);
 150         else
 151             fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
 152     }
 153
 154     NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned)
 155     {
 156         fail(ASCIILiteral("Patterns cannot contain backreferences."));
 157         ASSERT_NOT_REACHED();
 158     }
 159
 160     void atomCharacterClassAtom(UChar)
 161     {
 162         fail(ASCIILiteral("Character class atoms are not supported yet."));
 163     }
 164
 165     void assertionBOL()
 166     {
 167         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
 168     }
 169
 170     void assertionEOL()
 171     {
 172         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
 173     }
 174
 175     void assertionWordBoundary(bool)
 176     {
 177         fail(ASCIILiteral("Word boundaries assertions are not supported yet."));
 178     }
 179
 180     void atomCharacterClassBegin(bool = false)
 181     {
 182         fail(ASCIILiteral("Character class atoms are not supported yet."));
 183     }
 184
 185     void atomCharacterClassRange(UChar, UChar)
 186     {
 187         fail(ASCIILiteral("Character class ranges are not supported yet."));
 188     }
 189
 190     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
 191     {
 192         fail(ASCIILiteral("Buildins character class atoms are not supported yet."));
 193     }
 194
 195     void atomCharacterClassEnd()
 196     {
 197         fail(ASCIILiteral("Character class are not supported yet."));
 198     }
 199
 200     void atomParenthesesSubpatternBegin(bool = true)
 201     {
 202         fail(ASCIILiteral("Groups are not supported yet."));
 203     }
 204
 205     void atomParentheticalAssertionBegin(bool = false)
 206     {
 207         fail(ASCIILiteral("Groups are not supported yet."));
 208     }
 209
 210     void atomParenthesesEnd()
 211     {
 212         fail(ASCIILiteral("Groups are not supported yet."));
 213     }
 214
 215     void disjunction()
 216     {
 217         fail(ASCIILiteral("Disjunctions are not supported yet."));
 218     }
 219
 220 private:
 221     bool hasError() const
 222     {
 223         return !m_errorMessage.isNull();
 224     }
 225
 226     void fail(const String& errorMessage)
 227     {
 228         if (hasError())
 229             return;
 230
 231         if (m_newPrefixSubtreeRoot)
 232             m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
 233
 234         m_errorMessage = errorMessage;
 235     }
 236
 237     void generateTransition(TrivialAtom trivialAtom, unsigned source, unsigned target)
 238     {
 239         if (trivialAtom & hasNonCharacterMask) {
 240             ASSERT(trivialAtom & newlineClassIDBuiltinMask);
 241             for (unsigned i = 1; i < 128; ++i)
 242                 m_nfa.addTransition(source, target, i);
 243         } else
 244             m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
 245     }
 246
 247     BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
 248     {
 249         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroOrOne)) {
 250             unsigned newEnd = m_nfa.createNode();
 251             m_nfa.addRuleId(newEnd, m_patternId);
 252             generateTransition(trivialAtom, start, newEnd);
 253             m_nfa.addEpsilonTransition(start, newEnd);
 254             return { start, newEnd };
 255         }
 256
 257         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroToMany)) {
 258             unsigned repeatStart = m_nfa.createNode();
 259             m_nfa.addRuleId(repeatStart, m_patternId);
 260             unsigned repeatEnd = m_nfa.createNode();
 261             m_nfa.addRuleId(repeatEnd, m_patternId);
 262
 263             generateTransition(trivialAtom, repeatStart, repeatEnd);
 264             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
 265
 266             m_nfa.addEpsilonTransition(start, repeatStart);
 267
 268             unsigned kleenEnd = m_nfa.createNode();
 269             m_nfa.addRuleId(kleenEnd, m_patternId);
 270             m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
 271             m_nfa.addEpsilonTransition(start, kleenEnd);
 272             return { start, kleenEnd };
 273         }
 274
 275         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::OneToMany)) {
 276             unsigned repeatStart = m_nfa.createNode();
 277             m_nfa.addRuleId(repeatStart, m_patternId);
 278             unsigned repeatEnd = m_nfa.createNode();
 279             m_nfa.addRuleId(repeatEnd, m_patternId);
 280
 281             generateTransition(trivialAtom, repeatStart, repeatEnd);
 282             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
 283
 284             m_nfa.addEpsilonTransition(start, repeatStart);
 285
 286             unsigned afterRepeat = m_nfa.createNode();
 287             m_nfa.addRuleId(afterRepeat, m_patternId);
 288             m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
 289             return { start, afterRepeat };
 290         }
 291
 292         unsigned newEnd = m_nfa.createNode();
 293         m_nfa.addRuleId(newEnd, m_patternId);
 294         generateTransition(trivialAtom, start, newEnd);
 295         return { start, newEnd };
 296     }
 297
 298     void sinkPendingAtomIfNecessary()
 299     {
 300         ASSERT(m_lastPrefixTreeEntry);
 301
 302         if (!m_hasValidAtom)
 303             return;
 304
 305         ASSERT(m_pendingTrivialAtom);
 306
 307         auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
 308         if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
 309             m_lastPrefixTreeEntry = nextEntry->value.get();
 310             m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
 311         } else {
 312             std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
 313
 314             BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
 315             nextPrefixTreeEntry->nfaNode = newSubGraph.end;
 316
 317             auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
 318             ASSERT(addResult.isNewEntry);
 319
 320             m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
 321             m_newPrefixStaringPoint = m_pendingTrivialAtom;
 322
 323             m_lastPrefixTreeEntry = addResult.iterator->value.get();
 324         }
 325         ASSERT(m_lastPrefixTreeEntry);
 326
 327         m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
 328         m_pendingTrivialAtom = 0;
 329         m_hasValidAtom = false;
 330     }
 331
 332     NFA& m_nfa;
 333     const uint64_t m_patternId;
 334
 335     BoundedSubGraph m_activeGroup;
 336
 337     PrefixTreeEntry* m_lastPrefixTreeEntry;
 338     bool m_hasValidAtom = false;
 339     TrivialAtom m_pendingTrivialAtom = 0;
 340
 341     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
 342     TrivialAtom m_newPrefixStaringPoint = 0;
 343
 344     String m_errorMessage;
 345 };
 346
 347 URLFilterParser::URLFilterParser(NFA& nfa)
 348     : m_nfa(nfa)
 349 {
 350     m_prefixTreeRoot.nfaNode = nfa.root();
 351 }
 352
 353 String URLFilterParser::addPattern(const String& pattern, uint64_t patternId)
 354 {
 355     if (!pattern.containsOnlyASCII())
 356         return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
 357     ASSERT(!pattern.isEmpty());
 358
 359     if (pattern.isEmpty())
 360         return ASCIILiteral("Empty pattern.");
 361
 362     unsigned oldSize = m_nfa.graphSize();
 363
 364     String error;
 365
 366     GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternId);
 367     error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
 368     if (error.isNull())
 369         graphBuilder.finalize();
 370
 371     if (error.isNull())
 372         error = graphBuilder.errorMessage();
 373
 374     if (!error.isNull())
 375         m_nfa.restoreToGraphSize(oldSize);
 376
 377     return error;
 378 }
 379
 380 } // namespace ContentExtensions
 381 } // namespace WebCore
 382
 383 #endif // ENABLE(CONTENT_EXTENSIONS)