hphp/runtime/vm/bc-pattern.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/runtime/vm/bc-pattern.h"
  18
  19 #include <iterator>
  20
  21 #include "hphp/runtime/vm/func.h"
  22 #include "hphp/runtime/vm/hhbc-codec.h"
  23
  24 namespace HPHP {
  25 //////////////////////////////////////////////////////////////////////
  26
  27 using Result = BCPattern::Result;
  28
  29 Result BCPattern::matchAnchored(const Func* func) {
  30   return matchAnchored(func->unit()->entry() + func->base(),
  31                        func->unit()->entry() + func->past());
  32 }
  33
  34 Result BCPattern::matchAnchored(PC start, PC end) {
  35   Result result;
  36
  37   matchAnchored(m_pattern, start, end, result);
  38   return result;
  39 }
  40
  41 void BCPattern::matchAnchored(const Expr& pattern,
  42                               PC start, PC end, Result& result) {
  43   auto pos = pattern.begin();
  44
  45   for (auto inst = start; inst != end; ) {
  46     // Detect a match.
  47     if (pos == pattern.end()) {
  48       result.m_start = start;
  49       result.m_end = inst;
  50       return;
  51     }
  52
  53     auto const op = peek_op(inst);
  54
  55     // Skip pattern-globally ignored opcodes.
  56     if (m_ignores.count(op)) {
  57       inst = next(inst);
  58       continue;
  59     }
  60
  61     // Check for alternations whenever we fail to match.
  62     auto nomatch = [&] {
  63       if (!pos->hasAlt()) return result.erase();
  64
  65       // Pop the capture if we made one.
  66       if (pos->shouldCapture()) {
  67         result.m_captures.pop_back();
  68       }
  69
  70       for (auto const& atom : pos->getAlt()) {
  71         // Construct the full alternate pattern.
  72         auto alt = Expr { atom };
  73         alt.insert(alt.end(), std::next(pos), pattern.end());
  74         auto res = result;
  75
  76         // Match on the alternate.
  77         matchAnchored(alt, inst, end, res);
  78
  79         if (res.found()) {
  80           result = res;
  81           result.m_start = start;
  82           return;
  83         }
  84       }
  85       return result.erase();
  86     };
  87
  88     // Capture the atom if desired.
  89     if (pos->shouldCapture()) {
  90       result.m_captures.push_back(inst);
  91     }
  92
  93     // Check for shallow match.
  94     if (pos->op() != op) {
  95       return nomatch();
  96     }
  97
  98     auto filter = pos->getFilter();
  99
 100     // Check for deep match if desired.
 101     if (filter && !filter(inst, result.m_captures)) {
 102       return nomatch();
 103     }
 104
 105     if ((pos->op() == Op::JmpZ || pos->op() == Op::JmpNZ)) {
 106       // Match the taken block, if there is one.
 107       auto off = instrJumpOffset(inst);
 108       assert(off);
 109
 110       auto res = result;
 111       matchAnchored(pos->getTaken(), inst + *off, end, res);
 112
 113       if (!res.found()) {
 114         return nomatch();
 115       }
 116
 117       // Grab the captures.
 118       result.m_captures = res.m_captures;
 119     }
 120
 121     if (pos->hasSeq()) {
 122       // Match the subsequence if we have one.
 123       auto res = result;
 124       matchAnchored(pos->getSeq(), next(inst), end, res);
 125
 126       if (!res.found()) {
 127         return nomatch();
 128       }
 129
 130       // Set the PC.
 131       result.m_captures = res.m_captures;
 132       inst = res.m_end;
 133     } else {
 134       // Step the PC.
 135       inst = next(inst);
 136     }
 137
 138     // Step the pattern.
 139     ++pos;
 140   }
 141
 142   // Detect a terminal match.
 143   if (pos == pattern.end()) {
 144     result.m_start = start;
 145     result.m_end = end;
 146   }
 147 }
 148
 149 //////////////////////////////////////////////////////////////////////
 150 }