[ContentExtensions] Prepare for compiling stylesheets of selectors to be used on...
[WebKit-https.git] / Source / WebCore / contentextensions / ContentExtensionCompiler.cpp
1 /*
2  * Copyright (C) 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 "ContentExtensionCompiler.h"
28
29 #if ENABLE(CONTENT_EXTENSIONS)
30
31 #include "CompiledContentExtension.h"
32 #include "ContentExtensionActions.h"
33 #include "ContentExtensionParser.h"
34 #include "ContentExtensionRule.h"
35 #include "ContentExtensionsDebugging.h"
36 #include "DFABytecodeCompiler.h"
37 #include "NFA.h"
38 #include "NFAToDFA.h"
39 #include "URLFilterParser.h"
40 #include <wtf/CurrentTime.h>
41 #include <wtf/DataLog.h>
42 #include <wtf/text/CString.h>
43
44 namespace WebCore {
45 namespace ContentExtensions {
46
47 static Vector<unsigned> serializeActions(const Vector<ContentExtensionRule>& ruleList, Vector<SerializedActionByte>& actions)
48 {
49     ASSERT(!actions.size());
50     
51     Vector<unsigned> actionLocations;
52         
53     for (unsigned ruleIndex = 0; ruleIndex < ruleList.size(); ++ruleIndex) {
54         const ContentExtensionRule& rule = ruleList[ruleIndex];
55         
56         // Identical sequential actions should not be rewritten.
57         if (ruleIndex && rule.action() == ruleList[ruleIndex - 1].action()) {
58             actionLocations.append(actionLocations[ruleIndex - 1]);
59             continue;
60         }
61         actionLocations.append(actions.size());
62         
63         switch (rule.action().type()) {
64         case ActionType::InvalidAction:
65             RELEASE_ASSERT_NOT_REACHED();
66
67         case ActionType::BlockLoad:
68         case ActionType::BlockCookies:
69         case ActionType::IgnorePreviousRules:
70             actions.append(static_cast<SerializedActionByte>(rule.action().type()));
71             break;
72
73         case ActionType::CSSDisplayNone: {
74             const String& selector = rule.action().cssSelector();
75             // Append action type (1 byte).
76             actions.append(static_cast<SerializedActionByte>(ActionType::CSSDisplayNone));
77             // Append Selector length (4 bytes).
78             unsigned selectorLength = selector.length();
79             actions.resize(actions.size() + sizeof(unsigned));
80             *reinterpret_cast<unsigned*>(&actions[actions.size() - sizeof(unsigned)]) = selectorLength;
81             bool wideCharacters = !selector.is8Bit();
82             actions.append(wideCharacters);
83             // Append Selector.
84             if (wideCharacters) {
85                 for (unsigned i = 0; i < selectorLength; i++) {
86                     actions.resize(actions.size() + sizeof(UChar));
87                     *reinterpret_cast<UChar*>(&actions[actions.size() - sizeof(UChar)]) = selector[i];
88                 }
89             } else {
90                 for (unsigned i = 0; i < selectorLength; i++)
91                     actions.append(selector[i]);
92             }
93             break;
94         }
95         }
96     }
97     return actionLocations;
98 }
99
100
101 CompiledContentExtensionData compileRuleList(const String& ruleList)
102 {
103     auto parsedRuleList = parseRuleList(ruleList);
104
105 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
106     double nfaBuildTimeStart = monotonicallyIncreasingTime();
107 #endif
108
109     Vector<SerializedActionByte> actions;
110     Vector<unsigned> actionLocations = serializeActions(parsedRuleList, actions);
111     Vector<uint64_t> universalActionLocations;
112
113     NFA nfa;
114     URLFilterParser urlFilterParser(nfa);
115     bool nonUniversalActionSeen = false;
116     for (unsigned ruleIndex = 0; ruleIndex < parsedRuleList.size(); ++ruleIndex) {
117         const ContentExtensionRule& contentExtensionRule = parsedRuleList[ruleIndex];
118         const Trigger& trigger = contentExtensionRule.trigger();
119         ASSERT(trigger.urlFilter.length());
120
121         // High bits are used for flags. This should match how they are used in DFABytecodeCompiler::compileNode.
122         uint64_t actionLocationAndFlags =(static_cast<uint64_t>(trigger.flags) << 32) | static_cast<uint64_t>(actionLocations[ruleIndex]);
123         URLFilterParser::ParseStatus status = urlFilterParser.addPattern(trigger.urlFilter, trigger.urlFilterIsCaseSensitive, actionLocationAndFlags);
124
125         if (status == URLFilterParser::MatchesEverything) {
126             if (nonUniversalActionSeen)
127                 dataLogF("Trigger matching everything found not at beginning.  This may cause incorrect behavior with ignore-previous-rules");
128             universalActionLocations.append(actionLocationAndFlags);
129         } else
130             nonUniversalActionSeen = true;
131         
132         if (status != URLFilterParser::Ok && status != URLFilterParser::MatchesEverything) {
133             dataLogF("Error while parsing %s: %s\n", trigger.urlFilter.utf8().data(), URLFilterParser::statusString(status).utf8().data());
134             continue;
135         }
136     }
137
138 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
139     double nfaBuildTimeEnd = monotonicallyIncreasingTime();
140     dataLogF("    Time spent building the NFA: %f\n", (nfaBuildTimeEnd - nfaBuildTimeStart));
141 #endif
142
143 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
144     nfa.debugPrintDot();
145 #endif
146
147 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
148     double dfaBuildTimeStart = monotonicallyIncreasingTime();
149 #endif
150
151     DFA dfa = NFAToDFA::convert(nfa);
152     for (uint64_t actionLocation : universalActionLocations)
153         dfa.nodeAt(dfa.root()).actions.append(actionLocation);
154
155 #if CONTENT_EXTENSIONS_PERFORMANCE_REPORTING
156     double dfaBuildTimeEnd = monotonicallyIncreasingTime();
157     dataLogF("    Time spent building the DFA: %f\n", (dfaBuildTimeEnd - dfaBuildTimeStart));
158 #endif
159
160     // FIXME: never add a DFA that only matches the empty set.
161
162 #if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
163     dfa.debugPrintDot();
164 #endif
165
166     Vector<DFABytecode> bytecode;
167     DFABytecodeCompiler compiler(dfa, bytecode);
168     compiler.compile();
169
170     return { WTF::move(bytecode), WTF::move(actions) };
171 }
172
173 } // namespace ContentExtensions
174 } // namespace WebCore
175
176 #endif // ENABLE(CONTENT_EXTENSIONS)