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 const uint16_t caseInsensitiveMask = 0x200;
  42
  43 static TrivialAtom trivialAtomFromASCIICharacter(char character, bool caseSensitive)
  44 {
  45     ASSERT(isASCII(character));
  46
  47     if (caseSensitive || !isASCIIAlpha(character))
  48         return static_cast<uint16_t>(character);
  49
  50     return static_cast<uint16_t>(toASCIILower(character)) | caseInsensitiveMask;
  51 }
  52
  53 enum class TrivialAtomQuantifier : uint16_t {
  54     ZeroOrOne = 0x1000,
  55     ZeroToMany = 0x2000,
  56     OneToMany = 0x4000
  57 };
  58
  59 static void quantifyTrivialAtom(TrivialAtom& trivialAtom, TrivialAtomQuantifier quantifier)
  60 {
  61     ASSERT(trivialAtom & (hasNonCharacterMask | characterMask));
  62     ASSERT(!(trivialAtom & 0xf000));
  63     trivialAtom |= static_cast<uint16_t>(quantifier);
  64 }
  65
  66 static TrivialAtom trivialAtomForNewlineClassIDBuiltin()
  67 {
  68     return hasNonCharacterMask | newlineClassIDBuiltinMask;
  69 }
  70
  71 class GraphBuilder {
  72 private:
  73     struct BoundedSubGraph {
  74         unsigned start;
  75         unsigned end;
  76     };
  77 public:
  78     GraphBuilder(NFA& nfa, PrefixTreeEntry& prefixTreeRoot, bool patternIsCaseSensitive, uint64_t patternId)
  79         : m_nfa(nfa)
  80         , m_patternIsCaseSensitive(patternIsCaseSensitive)
  81         , m_patternId(patternId)
  82         , m_activeGroup({ nfa.root(), nfa.root() })
  83         , m_lastPrefixTreeEntry(&prefixTreeRoot)
  84     {
  85     }
  86
  87     void finalize()
  88     {
  89         if (hasError())
  90             return;
  91
  92         sinkPendingAtomIfNecessary();
  93
  94         if (m_activeGroup.start != m_activeGroup.end)
  95             m_nfa.setFinal(m_activeGroup.end, m_patternId);
  96         else
  97             fail(ASCIILiteral("The pattern cannot match anything."));
  98     }
  99
 100     const String& errorMessage() const
 101     {
 102         return m_errorMessage;
 103     }
 104
 105     void atomPatternCharacter(UChar character)
 106     {
 107         if (!isASCII(character)) {
 108             fail(ASCIILiteral("Only ASCII characters are supported in pattern."));
 109             return;
 110         }
 111
 112         if (hasError())
 113             return;
 114
 115         sinkPendingAtomIfNecessary();
 116
 117         char asciiChararacter = static_cast<char>(character);
 118         m_hasValidAtom = true;
 119
 120         ASSERT(m_lastPrefixTreeEntry);
 121         m_pendingTrivialAtom = trivialAtomFromASCIICharacter(asciiChararacter, m_patternIsCaseSensitive);
 122     }
 123
 124     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
 125     {
 126         if (hasError())
 127             return;
 128
 129         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
 130             m_hasValidAtom = true;
 131             ASSERT(m_lastPrefixTreeEntry);
 132             m_pendingTrivialAtom = trivialAtomForNewlineClassIDBuiltin();
 133         } else
 134             fail(ASCIILiteral("Character class is not supported."));
 135     }
 136
 137     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
 138     {
 139         if (hasError())
 140             return;
 141
 142         ASSERT(m_hasValidAtom);
 143         if (!m_hasValidAtom) {
 144             fail(ASCIILiteral("Quantifier without corresponding atom to quantify."));
 145             return;
 146         }
 147
 148         ASSERT(m_lastPrefixTreeEntry);
 149         if (!minimum && maximum == 1)
 150             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroOrOne);
 151         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite)
 152             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::ZeroToMany);
 153         else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
 154             quantifyTrivialAtom(m_pendingTrivialAtom, TrivialAtomQuantifier::OneToMany);
 155         else
 156             fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
 157     }
 158
 159     NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned)
 160     {
 161         fail(ASCIILiteral("Patterns cannot contain backreferences."));
 162         ASSERT_NOT_REACHED();
 163     }
 164
 165     void atomCharacterClassAtom(UChar)
 166     {
 167         fail(ASCIILiteral("Character class atoms are not supported yet."));
 168     }
 169
 170     void assertionBOL()
 171     {
 172         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
 173     }
 174
 175     void assertionEOL()
 176     {
 177         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
 178     }
 179
 180     void assertionWordBoundary(bool)
 181     {
 182         fail(ASCIILiteral("Word boundaries assertions are not supported yet."));
 183     }
 184
 185     void atomCharacterClassBegin(bool = false)
 186     {
 187         fail(ASCIILiteral("Character class atoms are not supported yet."));
 188     }
 189
 190     void atomCharacterClassRange(UChar, UChar)
 191     {
 192         fail(ASCIILiteral("Character class ranges are not supported yet."));
 193     }
 194
 195     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
 196     {
 197         fail(ASCIILiteral("Buildins character class atoms are not supported yet."));
 198     }
 199
 200     void atomCharacterClassEnd()
 201     {
 202         fail(ASCIILiteral("Character class are not supported yet."));
 203     }
 204
 205     void atomParenthesesSubpatternBegin(bool = true)
 206     {
 207         fail(ASCIILiteral("Groups are not supported yet."));
 208     }
 209
 210     void atomParentheticalAssertionBegin(bool = false)
 211     {
 212         fail(ASCIILiteral("Groups are not supported yet."));
 213     }
 214
 215     void atomParenthesesEnd()
 216     {
 217         fail(ASCIILiteral("Groups are not supported yet."));
 218     }
 219
 220     void disjunction()
 221     {
 222         fail(ASCIILiteral("Disjunctions are not supported yet."));
 223     }
 224
 225 private:
 226     bool hasError() const
 227     {
 228         return !m_errorMessage.isNull();
 229     }
 230
 231     void fail(const String& errorMessage)
 232     {
 233         if (hasError())
 234             return;
 235
 236         if (m_newPrefixSubtreeRoot)
 237             m_newPrefixSubtreeRoot->nextPattern.remove(m_newPrefixStaringPoint);
 238
 239         m_errorMessage = errorMessage;
 240     }
 241
 242     void generateTransition(TrivialAtom trivialAtom, unsigned source, unsigned target)
 243     {
 244         if (trivialAtom & hasNonCharacterMask) {
 245             ASSERT(trivialAtom & newlineClassIDBuiltinMask);
 246             for (unsigned i = 1; i < 128; ++i)
 247                 m_nfa.addTransition(source, target, i);
 248         } else {
 249             if (trivialAtom & caseInsensitiveMask) {
 250                 char character = static_cast<char>(trivialAtom & characterMask);
 251                 m_nfa.addTransition(source, target, character);
 252                 m_nfa.addTransition(source, target, toASCIIUpper(character));
 253             } else
 254                 m_nfa.addTransition(source, target, static_cast<char>(trivialAtom & characterMask));
 255         }
 256     }
 257
 258     BoundedSubGraph sinkTrivialAtom(TrivialAtom trivialAtom, unsigned start)
 259     {
 260         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroOrOne)) {
 261             unsigned newEnd = m_nfa.createNode();
 262             m_nfa.addRuleId(newEnd, m_patternId);
 263             generateTransition(trivialAtom, start, newEnd);
 264             m_nfa.addEpsilonTransition(start, newEnd);
 265             return { start, newEnd };
 266         }
 267
 268         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::ZeroToMany)) {
 269             unsigned repeatStart = m_nfa.createNode();
 270             m_nfa.addRuleId(repeatStart, m_patternId);
 271             unsigned repeatEnd = m_nfa.createNode();
 272             m_nfa.addRuleId(repeatEnd, m_patternId);
 273
 274             generateTransition(trivialAtom, repeatStart, repeatEnd);
 275             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
 276
 277             m_nfa.addEpsilonTransition(start, repeatStart);
 278
 279             unsigned kleenEnd = m_nfa.createNode();
 280             m_nfa.addRuleId(kleenEnd, m_patternId);
 281             m_nfa.addEpsilonTransition(repeatEnd, kleenEnd);
 282             m_nfa.addEpsilonTransition(start, kleenEnd);
 283             return { start, kleenEnd };
 284         }
 285
 286         if (trivialAtom & static_cast<uint16_t>(TrivialAtomQuantifier::OneToMany)) {
 287             unsigned repeatStart = m_nfa.createNode();
 288             m_nfa.addRuleId(repeatStart, m_patternId);
 289             unsigned repeatEnd = m_nfa.createNode();
 290             m_nfa.addRuleId(repeatEnd, m_patternId);
 291
 292             generateTransition(trivialAtom, repeatStart, repeatEnd);
 293             m_nfa.addEpsilonTransition(repeatEnd, repeatStart);
 294
 295             m_nfa.addEpsilonTransition(start, repeatStart);
 296
 297             unsigned afterRepeat = m_nfa.createNode();
 298             m_nfa.addRuleId(afterRepeat, m_patternId);
 299             m_nfa.addEpsilonTransition(repeatEnd, afterRepeat);
 300             return { start, afterRepeat };
 301         }
 302
 303         unsigned newEnd = m_nfa.createNode();
 304         m_nfa.addRuleId(newEnd, m_patternId);
 305         generateTransition(trivialAtom, start, newEnd);
 306         return { start, newEnd };
 307     }
 308
 309     void sinkPendingAtomIfNecessary()
 310     {
 311         ASSERT(m_lastPrefixTreeEntry);
 312
 313         if (!m_hasValidAtom)
 314             return;
 315
 316         ASSERT(m_pendingTrivialAtom);
 317
 318         auto nextEntry = m_lastPrefixTreeEntry->nextPattern.find(m_pendingTrivialAtom);
 319         if (nextEntry != m_lastPrefixTreeEntry->nextPattern.end()) {
 320             m_lastPrefixTreeEntry = nextEntry->value.get();
 321             m_nfa.addRuleId(m_lastPrefixTreeEntry->nfaNode, m_patternId);
 322         } else {
 323             std::unique_ptr<PrefixTreeEntry> nextPrefixTreeEntry = std::make_unique<PrefixTreeEntry>();
 324
 325             BoundedSubGraph newSubGraph = sinkTrivialAtom(m_pendingTrivialAtom, m_lastPrefixTreeEntry->nfaNode);
 326             nextPrefixTreeEntry->nfaNode = newSubGraph.end;
 327
 328             auto addResult = m_lastPrefixTreeEntry->nextPattern.set(m_pendingTrivialAtom, WTF::move(nextPrefixTreeEntry));
 329             ASSERT(addResult.isNewEntry);
 330
 331             m_newPrefixSubtreeRoot = m_lastPrefixTreeEntry;
 332             m_newPrefixStaringPoint = m_pendingTrivialAtom;
 333
 334             m_lastPrefixTreeEntry = addResult.iterator->value.get();
 335         }
 336         ASSERT(m_lastPrefixTreeEntry);
 337
 338         m_activeGroup.end = m_lastPrefixTreeEntry->nfaNode;
 339         m_pendingTrivialAtom = 0;
 340         m_hasValidAtom = false;
 341     }
 342
 343     NFA& m_nfa;
 344     bool m_patternIsCaseSensitive;
 345     const uint64_t m_patternId;
 346
 347     BoundedSubGraph m_activeGroup;
 348
 349     PrefixTreeEntry* m_lastPrefixTreeEntry;
 350     bool m_hasValidAtom = false;
 351     TrivialAtom m_pendingTrivialAtom = 0;
 352
 353     PrefixTreeEntry* m_newPrefixSubtreeRoot = nullptr;
 354     TrivialAtom m_newPrefixStaringPoint = 0;
 355
 356     String m_errorMessage;
 357 };
 358
 359 URLFilterParser::URLFilterParser(NFA& nfa)
 360     : m_nfa(nfa)
 361 {
 362     m_prefixTreeRoot.nfaNode = nfa.root();
 363 }
 364
 365 String URLFilterParser::addPattern(const String& pattern, bool patternIsCaseSensitive, uint64_t patternId)
 366 {
 367     if (!pattern.containsOnlyASCII())
 368         return ASCIILiteral("URLFilterParser only supports ASCII patterns.");
 369     ASSERT(!pattern.isEmpty());
 370
 371     if (pattern.isEmpty())
 372         return ASCIILiteral("Empty pattern.");
 373
 374     unsigned oldSize = m_nfa.graphSize();
 375
 376     String error;
 377
 378     GraphBuilder graphBuilder(m_nfa, m_prefixTreeRoot, patternIsCaseSensitive, patternId);
 379     error = String(JSC::Yarr::parse(graphBuilder, pattern, 0));
 380     if (error.isNull())
 381         graphBuilder.finalize();
 382
 383     if (error.isNull())
 384         error = graphBuilder.errorMessage();
 385
 386     if (!error.isNull())
 387         m_nfa.restoreToGraphSize(oldSize);
 388
 389     return error;
 390 }
 391
 392 } // namespace ContentExtensions
 393 } // namespace WebCore
 394
 395 #endif // ENABLE(CONTENT_EXTENSIONS)