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 class GraphBuilder {
  39 private:
  40     struct BoundedSubGraph {
  41         unsigned start;
  42         unsigned end;
  43     };
  44 public:
  45     GraphBuilder(NFA& nfa, uint64_t patternId)
  46         : m_nfa(nfa)
  47         , m_patternId(patternId)
  48         , m_activeGroup({ nfa.root(), nfa.root() })
  49         , m_lastAtom(m_activeGroup)
  50     {
  51     }
  52
  53     void finalize()
  54     {
  55         if (hasError())
  56             return;
  57         if (m_activeGroup.start != m_activeGroup.end)
  58             m_nfa.setFinal(m_activeGroup.end);
  59         else
  60             fail(ASCIILiteral("The pattern cannot match anything."));
  61     }
  62
  63     const String& errorMessage() const
  64     {
  65         return m_errorMessage;
  66     }
  67
  68     void atomPatternCharacter(UChar character)
  69     {
  70         if (isASCII(character)) {
  71             fail(ASCIILiteral("Only ASCII characters are supported in pattern."));
  72             return;
  73         }
  74
  75         if (hasError())
  76             return;
  77
  78         m_hasValidAtom = true;
  79         unsigned newEnd = m_nfa.createNode(m_patternId);
  80         m_nfa.addTransition(m_lastAtom.end, newEnd, static_cast<char>(character));
  81         m_lastAtom.start = m_lastAtom.end;
  82         m_lastAtom.end = newEnd;
  83         m_activeGroup.end = m_lastAtom.end;
  84     }
  85
  86     void atomBuiltInCharacterClass(JSC::Yarr::BuiltInCharacterClassID builtInCharacterClassID, bool inverted)
  87     {
  88         if (hasError())
  89             return;
  90
  91         if (builtInCharacterClassID == JSC::Yarr::NewlineClassID && inverted) {
  92             // FIXME: handle new line properly.
  93             m_hasValidAtom = true;
  94             unsigned newEnd = m_nfa.createNode(m_patternId);
  95             for (unsigned i = 1; i < 128; ++i)
  96                 m_nfa.addTransition(m_lastAtom.end, newEnd, i);
  97             m_lastAtom.start = m_lastAtom.end;
  98             m_lastAtom.end = newEnd;
  99             m_activeGroup.end = m_lastAtom.end;
 100         } else
 101             fail(ASCIILiteral("Character class is not supported."));
 102     }
 103
 104     void quantifyAtom(unsigned minimum, unsigned maximum, bool)
 105     {
 106         if (hasError())
 107             return;
 108
 109         ASSERT(m_hasValidAtom);
 110         if (!m_hasValidAtom) {
 111             fail(ASCIILiteral("Quantifier without corresponding atom to quantify."));
 112             return;
 113         }
 114
 115         if (!minimum && maximum == 1)
 116             m_nfa.addEpsilonTransition(m_lastAtom.start, m_lastAtom.end);
 117         else if (!minimum && maximum == JSC::Yarr::quantifyInfinite) {
 118             m_nfa.addEpsilonTransition(m_lastAtom.start, m_lastAtom.end);
 119             m_nfa.addEpsilonTransition(m_lastAtom.end, m_lastAtom.start);
 120         } else if (minimum == 1 && maximum == JSC::Yarr::quantifyInfinite)
 121             m_nfa.addEpsilonTransition(m_lastAtom.end, m_lastAtom.start);
 122         else
 123             fail(ASCIILiteral("Arbitrary atom repetitions are not supported."));
 124     }
 125
 126     NO_RETURN_DUE_TO_ASSERT void atomBackReference(unsigned)
 127     {
 128         fail(ASCIILiteral("Patterns cannot contain backreferences."));
 129         ASSERT_NOT_REACHED();
 130     }
 131
 132     void atomCharacterClassAtom(UChar)
 133     {
 134         fail(ASCIILiteral("Character class atoms are not supported yet."));
 135     }
 136
 137     void assertionBOL()
 138     {
 139         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
 140     }
 141
 142     void assertionEOL()
 143     {
 144         fail(ASCIILiteral("Line boundary assertions are not supported yet."));
 145     }
 146
 147     void assertionWordBoundary(bool)
 148     {
 149         fail(ASCIILiteral("Word boundaries assertions are not supported yet."));
 150     }
 151
 152     void atomCharacterClassBegin(bool = false)
 153     {
 154         fail(ASCIILiteral("Character class atoms are not supported yet."));
 155     }
 156
 157     void atomCharacterClassRange(UChar, UChar)
 158     {
 159         fail(ASCIILiteral("Character class ranges are not supported yet."));
 160     }
 161
 162     void atomCharacterClassBuiltIn(JSC::Yarr::BuiltInCharacterClassID, bool)
 163     {
 164         fail(ASCIILiteral("Buildins character class atoms are not supported yet."));
 165     }
 166
 167     void atomCharacterClassEnd()
 168     {
 169         fail(ASCIILiteral("Character class are not supported yet."));
 170     }
 171
 172     void atomParenthesesSubpatternBegin(bool = true)
 173     {
 174         fail(ASCIILiteral("Groups are not supported yet."));
 175     }
 176
 177     void atomParentheticalAssertionBegin(bool = false)
 178     {
 179         fail(ASCIILiteral("Groups are not supported yet."));
 180     }
 181
 182     void atomParenthesesEnd()
 183     {
 184         fail(ASCIILiteral("Groups are not supported yet."));
 185     }
 186
 187     void disjunction()
 188     {
 189         fail(ASCIILiteral("Disjunctions are not supported yet."));
 190     }
 191
 192
 193 private:
 194     bool hasError() const
 195     {
 196         return !m_errorMessage.isNull();
 197     }
 198
 199     void fail(const String& errorMessage)
 200     {
 201         if (hasError())
 202             return;
 203         m_errorMessage = errorMessage;
 204     }
 205
 206     NFA& m_nfa;
 207     const uint64_t m_patternId;
 208
 209     BoundedSubGraph m_activeGroup;
 210
 211     bool m_hasValidAtom = false;
 212     BoundedSubGraph m_lastAtom;
 213
 214     String m_errorMessage;
 215 };
 216
 217 void URLFilterParser::parse(const String& pattern, uint64_t patternId, NFA& nfa)
 218 {
 219     if (!pattern.containsOnlyASCII())
 220         m_errorMessage = ASCIILiteral("URLFilterParser only supports ASCII patterns.");
 221     ASSERT(!pattern.isEmpty());
 222
 223     if (pattern.isEmpty())
 224         return;
 225
 226     unsigned oldSize = nfa.graphSize();
 227
 228     GraphBuilder graphBuilder(nfa, patternId);
 229     const char* error = JSC::Yarr::parse(graphBuilder, pattern, 0);
 230     if (error)
 231         m_errorMessage = String(error);
 232     else
 233         graphBuilder.finalize();
 234
 235     if (!error)
 236         m_errorMessage = graphBuilder.errorMessage();
 237
 238     if (hasError())
 239         nfa.restoreToGraphSize(oldSize);
 240 }
 241
 242 } // namespace ContentExtensions
 243 } // namespace WebCore
 244
 245 #endif // ENABLE(CONTENT_EXTENSIONS)