hphp/hhbbc/check.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 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 <boost/dynamic_bitset.hpp>
  18 #include <boost/next_prior.hpp>
  19
  20 #include "folly/gen/Base.h"
  21
  22 #include "hphp/hhbbc/representation.h"
  23 #include "hphp/hhbbc/unit-util.h"
  24 #include "hphp/hhbbc/cfg.h"
  25
  26 namespace HPHP { namespace HHBBC { namespace php {
  27
  28 namespace {
  29
  30 const StaticString s_Closure("Closure");
  31 const StaticString s_invoke("__invoke");
  32
  33 //////////////////////////////////////////////////////////////////////
  34
  35 bool checkBlock(const php::Block& b) {
  36   assert(!b.hhbcs.empty());
  37
  38   // No instructions in the middle of a block should have taken edges,
  39   // or be an unconditional Jmp.
  40   for (auto it = begin(b.hhbcs); it != end(b.hhbcs); ++it) {
  41     assert(it->op != Op::Jmp && "unconditional Jmp mid-block");
  42     if (boost::next(it) == end(b.hhbcs)) break;
  43     forEachTakenEdge(*it, [&] (php::Block& b) {
  44       assert(!"Instruction in middle of block had a jump target");
  45     });
  46   }
  47
  48   // The factored exit list contains unique elements.
  49   std::set<borrowed_ptr<const php::Block>> exitSet;
  50   std::copy(begin(b.factoredExits), end(b.factoredExits),
  51             std::inserter(exitSet, begin(exitSet)));
  52   assert(exitSet.size() == b.factoredExits.size());
  53
  54   return true;
  55 }
  56
  57 bool checkParams(const php::Func& f) {
  58   assert(f.params.size() <= f.locals.size());
  59   for (uint32_t i = 0; i < f.locals.size(); ++i) {
  60     assert(f.locals[i]->id == i);
  61   }
  62   for (uint32_t i = 0; i < f.iters.size(); ++i) {
  63     assert(f.iters[i]->id == i);
  64   }
  65
  66   // dvInit pointers are consistent in the parameters vector and on
  67   // the func.
  68   for (uint32_t i = 0; i < f.params.size(); ++i) {
  69     assert(f.params[i].dvEntryPoint == f.dvEntries[i]);
  70   }
  71
  72   return true;
  73 }
  74
  75 // N is usually small ... ;)
  76 template<class Container>
  77 bool has_edge_linear(const Container& c,
  78                      borrowed_ptr<const php::Block> target) {
  79   return std::find(begin(c), end(c), target) != end(c);
  80 }
  81
  82 void checkExnTreeBasic(boost::dynamic_bitset<>& seenIds,
  83                        borrowed_ptr<const ExnNode> node,
  84                        borrowed_ptr<const ExnNode> expectedParent) {
  85   // All exnNode ids must be unique.
  86   if (seenIds.size() < node->id + 1) {
  87     seenIds.resize(node->id + 1);
  88   }
  89   assert(!seenIds[node->id]);
  90   seenIds[node->id] = true;
  91
  92   // Parent pointers should point to the node that has a given node as
  93   // a child.
  94   assert(node->parent == expectedParent);
  95
  96   for (auto& c : node->children) {
  97     checkExnTreeBasic(seenIds, borrow(c), node);
  98   }
  99 }
 100
 101 void checkFaultEntryRec(boost::dynamic_bitset<>& seenBlocks,
 102                         const php::Block& faultEntry,
 103                         const php::ExnNode& exnNode) {
 104   // Loops in fault funclets could cause us to revisit the same block,
 105   // so we track the ones we've seen.
 106   if (seenBlocks.size() < faultEntry.id + 1) {
 107     seenBlocks.resize(faultEntry.id + 1);
 108   }
 109   if (seenBlocks[faultEntry.id]) return;
 110   seenBlocks[faultEntry.id] = true;
 111
 112   /*
 113    * All funclets aren't in the main section.
 114    */
 115   assert(faultEntry.section != php::Block::Section::Main);
 116
 117   /*
 118    * The fault blocks should all have factored exits to parent
 119    * catches/faults, if there are any.
 120    *
 121    * Note: for now this is an invariant, but if we start pruning
 122    * factoredExits this might need to change.
 123    */
 124   for (auto parent = exnNode.parent; parent; parent = parent->parent) {
 125     match<void>(
 126       parent->info,
 127       [&] (const TryRegion& tr) {
 128         for (DEBUG_ONLY auto& c : tr.catches) {
 129           assert(has_edge_linear(faultEntry.factoredExits, c.second));
 130         }
 131       },
 132       [&] (const FaultRegion& fr) {
 133         assert(has_edge_linear(faultEntry.factoredExits, fr.faultEntry));
 134       }
 135     );
 136   }
 137
 138   // Note: right now we're only asserting about normal successors, but
 139   // there can be exception-only successors for catch blocks inside of
 140   // fault funclets for finally handlers.  (Just going un-asserted for
 141   // now.)
 142   forEachNormalSuccessor(faultEntry, [&] (const php::Block& succ) {
 143     checkFaultEntryRec(seenBlocks, succ, exnNode);
 144   });
 145 }
 146
 147 void checkExnTreeMore(borrowed_ptr<const ExnNode> node) {
 148   // Fault entries have a few things to assert.
 149   match<void>(
 150     node->info,
 151     [&] (const FaultRegion& fr) {
 152       boost::dynamic_bitset<> seenBlocks;
 153       checkFaultEntryRec(seenBlocks, *fr.faultEntry, *node);
 154     },
 155     [&] (const TryRegion& tr) {}
 156   );
 157
 158   for (auto& c : node->children) checkExnTreeMore(borrow(c));
 159 }
 160
 161 bool checkExnTree(const php::Func& f) {
 162   boost::dynamic_bitset<> seenIds;
 163   for (auto& n : f.exnNodes) checkExnTreeBasic(seenIds, borrow(n), nullptr);
 164
 165   // ExnNode ids are contiguous.
 166   for (size_t i = 0; i < seenIds.size(); ++i) assert(seenIds[i] == true);
 167
 168   // The following assertions come after the above, because if the
 169   // tree is totally clobbered it's easy for the wrong ones to fire.
 170   for (auto& n : f.exnNodes) checkExnTreeMore(borrow(n));
 171   return true;
 172 }
 173
 174 bool checkName(SString name) {
 175   return isNSNormalized(name);
 176 }
 177
 178 //////////////////////////////////////////////////////////////////////
 179
 180 }
 181
 182 bool check(const php::Func& f) {
 183   assert(checkParams(f));
 184   assert(checkName(f.name));
 185   for (DEBUG_ONLY auto& block : f.blocks) assert(checkBlock(*block));
 186
 187   /*
 188    * Some of these relationships may change as async/await
 189    * implementation progresses.  Asserting them now so they are
 190    * revisited here if they aren't true anymore.
 191    */
 192   if (f.isClosureBody)          assert(!f.top);
 193   if (f.isAsync)                assert(f.isGeneratorBody ||
 194                                        f.innerGeneratorFunc);
 195   if (f.isPairGenerator)        assert(f.isGeneratorBody);
 196   if (f.isGeneratorBody)        assert(f.outerGeneratorFunc);
 197
 198   if (f.isClosureBody) {
 199     assert(f.cls &&
 200            f.cls->parentName &&
 201            f.cls->parentName->isame(s_Closure.get()));
 202   }
 203
 204   if (f.isGeneratorFromClosure) {
 205     assert(f.isGeneratorBody);
 206     // Inner generator functions from closures don't live on any
 207     // class.
 208     assert(f.cls == nullptr);
 209   }
 210
 211   assert(!(f.outerGeneratorFunc && f.innerGeneratorFunc));
 212   if (f.outerGeneratorFunc) {
 213     assert(f.outerGeneratorFunc->innerGeneratorFunc == &f);
 214   }
 215   if (f.innerGeneratorFunc) {
 216     assert(f.innerGeneratorFunc->outerGeneratorFunc == &f);
 217   }
 218
 219   boost::dynamic_bitset<> seenId(f.nextBlockId);
 220   for (auto& block : f.blocks) {
 221     assert(checkBlock(*block));
 222
 223     // All blocks have unique ids in a given function; not necessarily
 224     // consecutive.
 225     assert(block->id < f.nextBlockId);
 226     assert(!seenId.test(block->id));
 227     seenId.set(block->id);
 228   }
 229
 230   assert(checkExnTree(f));
 231
 232   return true;
 233 }
 234
 235 bool check(const php::Class& c) {
 236   assert(checkName(c.name));
 237   for (DEBUG_ONLY auto& m : c.methods) assert(check(*m));
 238
 239   // Some invariants about Closure classes.
 240   auto const isClo = c.parentName && c.parentName->isame(s_Closure.get());
 241   if (c.closureContextCls) {
 242     assert(c.closureContextCls->unit == c.unit);
 243     assert(isClo);
 244   }
 245   if (isClo) {
 246     assert(c.methods.size() == 1);
 247     assert(c.methods[0]->name->isame(s_invoke.get()));
 248     assert(c.methods[0]->isClosureBody);
 249     assert(c.hoistability == PreClass::ClosureHoistable);
 250   } else {
 251     assert(!c.closureContextCls);
 252   }
 253
 254   return true;
 255 }
 256
 257 bool check(const php::Unit& u) {
 258   assert(check(*u.pseudomain));
 259   for (DEBUG_ONLY auto& c : u.classes)   assert(check(*c));
 260   for (DEBUG_ONLY auto& f : u.funcs)     assert(check(*f));
 261   return true;
 262 }
 263
 264 bool check(const php::Program& p) {
 265   for (DEBUG_ONLY auto& u : p.units) assert(check(*u));
 266   return true;
 267 }
 268
 269 //////////////////////////////////////////////////////////////////////
 270
 271 }}}