Source/WebCore/contentextensions/DFABytecodeCompiler.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 "DFABytecodeCompiler.h"
  28
  29 #if ENABLE(CONTENT_EXTENSIONS)
  30
  31 #include "ContentExtensionRule.h"
  32 #include "DFA.h"
  33 #include "DFANode.h"
  34
  35 namespace WebCore {
  36
  37 namespace ContentExtensions {
  38
  39 template <typename IntType>
  40 inline void append(Vector<DFABytecode>& bytecode, IntType value)
  41 {
  42     bytecode.resize(bytecode.size() + sizeof(IntType));
  43     *reinterpret_cast<IntType*>(&bytecode[bytecode.size() - sizeof(IntType)]) = value;
  44 }
  45
  46 inline void set32Bits(Vector<DFABytecode>& bytecode, unsigned index, unsigned value)
  47 {
  48     *reinterpret_cast<unsigned*>(&bytecode[index]) = value;
  49 }
  50
  51 void DFABytecodeCompiler::emitAppendAction(unsigned action)
  52 {
  53     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::AppendAction);
  54     append<unsigned>(m_bytecode, action);
  55 }
  56
  57 void DFABytecodeCompiler::emitTestFlagsAndAppendAction(uint16_t flags, unsigned action)
  58 {
  59     ASSERT(flags);
  60     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::TestFlagsAndAppendAction);
  61     append<uint16_t>(m_bytecode, flags);
  62     append<unsigned>(m_bytecode, action);
  63 }
  64
  65 void DFABytecodeCompiler::emitJump(unsigned destinationNodeIndex)
  66 {
  67     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Jump);
  68     m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
  69     append<unsigned>(m_bytecode, 0); // This value will be set when linking.
  70 }
  71
  72 void DFABytecodeCompiler::emitCheckValue(uint8_t value, unsigned destinationNodeIndex, bool caseSensitive)
  73 {
  74     append<DFABytecodeInstruction>(m_bytecode, caseSensitive ? DFABytecodeInstruction::CheckValueCaseSensitive : DFABytecodeInstruction::CheckValueCaseInsensitive);
  75     append<uint8_t>(m_bytecode, value);
  76     m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
  77     append<unsigned>(m_bytecode, 0); // This value will be set when linking.
  78 }
  79
  80 void DFABytecodeCompiler::emitCheckValueRange(uint8_t lowValue, uint8_t highValue, unsigned destinationNodeIndex, bool caseSensitive)
  81 {
  82     ASSERT_WITH_MESSAGE(lowValue < highValue, "The instruction semantic impose lowValue is strictly less than highValue.");
  83
  84     append<DFABytecodeInstruction>(m_bytecode, caseSensitive ? DFABytecodeInstruction::CheckValueRangeCaseSensitive : DFABytecodeInstruction::CheckValueRangeCaseInsensitive);
  85     append<uint8_t>(m_bytecode, lowValue);
  86     append<uint8_t>(m_bytecode, highValue);
  87     m_linkRecords.append(std::make_pair(m_bytecode.size(), destinationNodeIndex));
  88     append<unsigned>(m_bytecode, 0); // This value will be set when linking.
  89 }
  90
  91 void DFABytecodeCompiler::emitTerminate()
  92 {
  93     append<DFABytecodeInstruction>(m_bytecode, DFABytecodeInstruction::Terminate);
  94 }
  95
  96 void DFABytecodeCompiler::compileNode(unsigned index)
  97 {
  98     const DFANode& node = m_dfa.nodeAt(index);
  99
 100     // Record starting index for linking.
 101     m_nodeStartOffsets[index] = m_bytecode.size();
 102
 103     for (uint64_t action : node.actions) {
 104         // High bits are used to store flags. See compileRuleList.
 105         if (action & 0xFFFF00000000)
 106             emitTestFlagsAndAppendAction(static_cast<uint16_t>(action >> 32), static_cast<unsigned>(action));
 107         else
 108             emitAppendAction(static_cast<unsigned>(action));
 109     }
 110     compileNodeTransitions(node);
 111 }
 112
 113 void DFABytecodeCompiler::compileNodeTransitions(const DFANode& node)
 114 {
 115     unsigned destinations[128];
 116     const unsigned noDestination = std::numeric_limits<unsigned>::max();
 117     for (uint16_t i = 0; i < 128; i++) {
 118         auto it = node.transitions.find(i);
 119         if (it == node.transitions.end())
 120             destinations[i] = noDestination;
 121         else
 122             destinations[i] = it->value;
 123     }
 124
 125     Vector<Range> ranges;
 126     uint8_t rangeMin;
 127     bool hasRangeMin = false;
 128     for (uint8_t i = 0; i < 128; i++) {
 129         if (hasRangeMin) {
 130             ASSERT_WITH_MESSAGE(!(node.hasFallbackTransition && node.fallbackTransition == destinations[rangeMin]), "Individual transitions to the fallback transitions should have been eliminated by the optimizer.");
 131             if (destinations[i] != destinations[rangeMin]) {
 132
 133                 // This is the end of a range. Check if it can be case insensitive.
 134                 uint8_t rangeMax = i - 1;
 135                 bool caseSensitive = true;
 136                 if (rangeMin >= 'A' && rangeMax <= 'Z') {
 137                     caseSensitive = false;
 138                     for (uint8_t rangeIndex = rangeMin; rangeIndex <= rangeMax; rangeIndex++) {
 139                         if (destinations[rangeMin] != destinations[toASCIILower(rangeIndex)]) {
 140                             caseSensitive = true;
 141                             break;
 142                         }
 143                     }
 144                 }
 145
 146                 if (!caseSensitive) {
 147                     // If all the lower-case destinations are the same as the upper-case destinations,
 148                     // then they will be covered by a case-insensitive range and will not need their own range.
 149                     for (uint8_t rangeIndex = rangeMin; rangeIndex <= rangeMax; rangeIndex++) {
 150                         ASSERT(destinations[rangeMin] == destinations[toASCIILower(rangeIndex)]);
 151                         destinations[toASCIILower(rangeIndex)] = noDestination;
 152                     }
 153                     ranges.append(Range(toASCIILower(rangeMin), toASCIILower(rangeMax), destinations[rangeMin], caseSensitive));
 154                 } else
 155                     ranges.append(Range(rangeMin, rangeMax, destinations[rangeMin], caseSensitive));
 156
 157                 if (destinations[i] == noDestination)
 158                     hasRangeMin = false;
 159                 else
 160                     rangeMin = i;
 161             }
 162         } else {
 163             if (destinations[i] != noDestination) {
 164                 rangeMin = i;
 165                 hasRangeMin = true;
 166             }
 167         }
 168     }
 169     if (hasRangeMin) {
 170         // Ranges are appended after passing the end of them.
 171         // If a range goes to 127, we will have an uncommitted rangeMin because the loop does not check 128.
 172         // If a range goes to 127, there will never be values higher than it, so checking for case-insensitive ranges would always fail.
 173         ranges.append(Range(rangeMin, 127, destinations[rangeMin], true));
 174     }
 175
 176     for (const auto& range : ranges)
 177         compileCheckForRange(range);
 178     if (node.hasFallbackTransition)
 179         emitJump(node.fallbackTransition);
 180     else
 181         emitTerminate();
 182 }
 183
 184 void DFABytecodeCompiler::compileCheckForRange(const Range& range)
 185 {
 186     ASSERT_WITH_MESSAGE(range.max < 128, "The DFA engine only supports the ASCII alphabet.");
 187     ASSERT(range.min <= range.max);
 188
 189     if (range.min == range.max)
 190         emitCheckValue(range.min, range.destination, range.caseSensitive);
 191     else
 192         emitCheckValueRange(range.min, range.max, range.destination, range.caseSensitive);
 193 }
 194
 195 void DFABytecodeCompiler::compile()
 196 {
 197     // DFA header.
 198     unsigned startLocation = m_bytecode.size();
 199     append<unsigned>(m_bytecode, 0);
 200     m_nodeStartOffsets.resize(m_dfa.size());
 201
 202     // Make sure the root is always at the beginning of the bytecode.
 203     compileNode(m_dfa.root());
 204     for (unsigned i = 0; i < m_dfa.size(); i++) {
 205         if (i != m_dfa.root())
 206             compileNode(i);
 207     }
 208
 209     // Link.
 210     for (const auto& linkRecord : m_linkRecords)
 211         set32Bits(m_bytecode, linkRecord.first, m_nodeStartOffsets[linkRecord.second]);
 212
 213     // Set size header.
 214     set32Bits(m_bytecode, startLocation, m_bytecode.size() - startLocation);
 215 }
 216
 217 } // namespace ContentExtensions
 218
 219 } // namespace WebCore
 220
 221 #endif // ENABLE(CONTENT_EXTENSIONS)