hphp/runtime/vm/bc-pattern.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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
  23 namespace HPHP {
  24 //////////////////////////////////////////////////////////////////////
  25
  26 using Result = BCPattern::Result;
  27
  28 Result BCPattern::matchAnchored(const Func* func) {
  29   return matchAnchored(func->unit()->entry() + func->base(),
  30                        func->unit()->entry() + func->past());
  31 }
  32
  33 Result BCPattern::matchAnchored(PC start, PC end) {
  34   Result result;
  35
  36   matchAnchored(m_pattern, start, end, result);
  37   return result;
  38 }
  39
  40 void BCPattern::matchAnchored(const Expr& pattern,
  41                               PC start, PC end, Result& result) {
  42   auto pos = pattern.begin();
  43
  44   for (auto inst = start; inst != end; ) {
  45     // Detect a match.
  46     if (pos == pattern.end()) {
  47       result.m_start = start;
  48       result.m_end = inst;
  49       return;
  50     }
  51
  52     auto op = *(Op*)inst;
  53
  54     // Skip pattern-globally ignored opcodes.
  55     if (m_ignores.count(op)) {
  56       inst = next(inst);
  57       continue;
  58     }
  59
  60     // Check for alternations whenever we fail to match.
  61     auto nomatch = [&] {
  62       if (!pos->hasAlt()) return result.erase();
  63
  64       // Pop the capture if we made one.
  65       if (pos->shouldCapture()) {
  66         result.m_captures.pop_back();
  67       }
  68
  69       for (auto const& atom : pos->getAlt()) {
  70         // Construct the full alternate pattern.
  71         auto alt = Expr { atom };
  72         alt.insert(alt.end(), std::next(pos), pattern.end());
  73         auto res = result;
  74
  75         // Match on the alternate.
  76         matchAnchored(alt, inst, end, res);
  77
  78         if (res.found()) {
  79           result = res;
  80           result.m_start = start;
  81           return;
  82         }
  83       }
  84       return result.erase();
  85     };
  86
  87     // Capture the atom if desired.
  88     if (pos->shouldCapture()) {
  89       result.m_captures.push_back(inst);
  90     }
  91
  92     // Check for shallow match.
  93     if (pos->op() != op) {
  94       return nomatch();
  95     }
  96
  97     auto filter = pos->getFilter();
  98
  99     // Check for deep match if desired.
 100     if (filter && !filter(inst, result.m_captures)) {
 101       return nomatch();
 102     }
 103
 104     if ((pos->op() == Op::JmpZ || pos->op() == Op::JmpNZ)) {
 105       // Match the taken block, if there is one.
 106       auto off = instrJumpOffset((Op*)inst);
 107       assert(off);
 108
 109       auto res = result;
 110       matchAnchored(pos->getTaken(), inst + *off, end, res);
 111
 112       if (!res.found()) {
 113         return nomatch();
 114       }
 115
 116       // Grab the captures.
 117       result.m_captures = res.m_captures;
 118     }
 119
 120     if (pos->hasSeq()) {
 121       // Match the subsequence if we have one.
 122       auto res = result;
 123       matchAnchored(pos->getSeq(), next(inst), end, res);
 124
 125       if (!res.found()) {
 126         return nomatch();
 127       }
 128
 129       // Set the PC.
 130       result.m_captures = res.m_captures;
 131       inst = res.m_end;
 132     } else {
 133       // Step the PC.
 134       inst = next(inst);
 135     }
 136
 137     // Step the pattern.
 138     ++pos;
 139   }
 140
 141   // Detect a terminal match.
 142   if (pos == pattern.end()) {
 143     result.m_start = start;
 144     result.m_end = end;
 145   }
 146 }
 147
 148 //////////////////////////////////////////////////////////////////////
 149 }