hphp/compiler/analysis/block_scope.h

   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 #ifndef incl_HPHP_BLOCK_SCOPE_H_
  18 #define incl_HPHP_BLOCK_SCOPE_H_
  19
  20 #include "hphp/compiler/hphp.h"
  21
  22 #include "hphp/util/bits.h"
  23 #include "hphp/util/lock.h"
  24 #include "hphp/runtime/base/macros.h"
  25
  26 #include <tbb/concurrent_hash_map.h>
  27 #include <list>
  28 #include <memory>
  29 #include <set>
  30 #include <utility>
  31 #include <vector>
  32
  33 namespace HPHP {
  34 ///////////////////////////////////////////////////////////////////////////////
  35
  36 class CodeGenerator;
  37 DECLARE_BOOST_TYPES(Statement);
  38 DECLARE_BOOST_TYPES(AnalysisResult);
  39 DECLARE_BOOST_TYPES(VariableTable);
  40 DECLARE_BOOST_TYPES(ConstantTable);
  41 DECLARE_BOOST_TYPES(ModifierExpression);
  42 DECLARE_BOOST_TYPES(IncludeExpression);
  43 DECLARE_BOOST_TYPES(StatementList);
  44 DECLARE_BOOST_TYPES(BlockScope);
  45 DECLARE_BOOST_TYPES(ClassScope);
  46 DECLARE_BOOST_TYPES(FunctionScope);
  47 DECLARE_BOOST_TYPES(FileScope);
  48
  49 typedef hphp_hash_map<BlockScopeRawPtr, int,
  50                       smart_pointer_hash<BlockScopeRawPtr>
  51                       > BlockScopeRawPtrFlagsHashMap;
  52 typedef hphp_hash_set<BlockScopeRawPtr,
  53                       smart_pointer_hash<BlockScopeRawPtr>
  54                       > BlockScopeRawPtrHashSet;
  55 typedef tbb::concurrent_hash_map<BlockScopeRawPtr, int,
  56                                  smart_pointer_hash<BlockScopeRawPtr> >
  57         ConcurrentBlockScopeRawPtrIntHashMap;
  58
  59 typedef std::vector<BlockScopeRawPtr> BlockScopeRawPtrVec;
  60 typedef std::list<BlockScopeRawPtr>   BlockScopeRawPtrQueue;
  61 typedef std::vector<BlockScopeRawPtrFlagsHashMap::
  62                     value_type*> BlockScopeRawPtrFlagsVec;
  63 typedef std::pair< BlockScopeRawPtr, int* >
  64         BlockScopeRawPtrFlagsPtrPair;
  65 typedef std::vector< std::pair< BlockScopeRawPtr, int* > >
  66         BlockScopeRawPtrFlagsPtrVec;
  67
  68 typedef SimpleMutex InferTypesMutex;
  69
  70 /**
  71  * Base class of ClassScope and FunctionScope.
  72  */
  73 class BlockScope : private boost::noncopyable,
  74                    public std::enable_shared_from_this<BlockScope> {
  75 public:
  76   enum KindOf {
  77     ClassScope,
  78     FunctionScope,
  79     FileScope,
  80     ProgramScope,
  81   };
  82
  83   enum UseKinds {
  84     /* Callers */
  85     UseKindCallerInline   = 0x1,
  86     UseKindCallerParam    = 0x1 << 1,
  87     UseKindCallerReturn   = 0x1 << 2,
  88     UseKindCaller         = (UseKindCallerInline |
  89                              UseKindCallerParam  |
  90                              UseKindCallerReturn),
  91
  92     /* Static references */
  93     UseKindStaticRef      = 0x1 << 3,
  94
  95     /* 16 bits of Non static references */
  96     UseKindNonStaticRef0  = 0x1 << 4,
  97     UseKindNonStaticRef1  = 0x1 << 5,
  98     UseKindNonStaticRef2  = 0x1 << 6,
  99     UseKindNonStaticRef3  = 0x1 << 7,
 100     UseKindNonStaticRef4  = 0x1 << 8,
 101     UseKindNonStaticRef5  = 0x1 << 9,
 102     UseKindNonStaticRef6  = 0x1 << 10,
 103     UseKindNonStaticRef7  = 0x1 << 11,
 104     UseKindNonStaticRef8  = 0x1 << 12,
 105     UseKindNonStaticRef9  = 0x1 << 13,
 106     UseKindNonStaticRef10 = 0x1 << 14,
 107     UseKindNonStaticRef11 = 0x1 << 15,
 108     UseKindNonStaticRef12 = 0x1 << 16,
 109     UseKindNonStaticRef13 = 0x1 << 17,
 110     UseKindNonStaticRef14 = 0x1 << 18,
 111     UseKindNonStaticRef15 = 0x1 << 19,
 112     UseKindNonStaticRef   = (UseKindNonStaticRef0  |
 113                              UseKindNonStaticRef1  |
 114                              UseKindNonStaticRef2  |
 115                              UseKindNonStaticRef3  |
 116                              UseKindNonStaticRef4  |
 117                              UseKindNonStaticRef5  |
 118                              UseKindNonStaticRef6  |
 119                              UseKindNonStaticRef7  |
 120                              UseKindNonStaticRef8  |
 121                              UseKindNonStaticRef9  |
 122                              UseKindNonStaticRef10 |
 123                              UseKindNonStaticRef11 |
 124                              UseKindNonStaticRef12 |
 125                              UseKindNonStaticRef13 |
 126                              UseKindNonStaticRef14 |
 127                              UseKindNonStaticRef15),
 128
 129     /* Constants */
 130     UseKindConstRef       = 0x1 << 20,
 131
 132     /* Other types */
 133     UseKindParentRef      = 0x1 << 21,
 134     UseKindInclude        = 0x1 << 22,
 135     UseKindClosure        = 0x1 << 23,
 136     UseKindAny            = (unsigned)-1
 137   };
 138
 139   /* Assert the size and bit-consecutiveness of UseKindNonStaticRef */
 140   static_assert(BitCount<UseKindNonStaticRef>::value == 16,
 141                 "UseKindNonStaticRef should have 16 bits set");
 142   static_assert(BitPhase<UseKindNonStaticRef>::value <= 2,
 143                 "UseKindNonStaticRef set bits should be consecutive");
 144
 145   static int GetNonStaticRefUseKind(unsigned int hash) {
 146     int res = ((int)UseKindNonStaticRef0) << (hash % 16);
 147     assert(res >= ((int)UseKindNonStaticRef0) &&
 148            res <= ((int)UseKindNonStaticRef15));
 149     return res;
 150   }
 151
 152   enum Marks {
 153     MarkWaitingInQueue,
 154     MarkProcessingDeps,
 155     MarkReady,
 156     MarkWaiting,
 157     MarkProcessing,
 158     MarkProcessedInQueue,
 159     MarkProcessed
 160   };
 161
 162   class ScopeCompare {
 163   public:
 164     bool operator()(const BlockScopeRawPtr &p1,
 165                     const BlockScopeRawPtr &p2) const {
 166       return cmp(p1,p2) < 0;
 167     }
 168     int cmp(const BlockScopeRawPtr &p1, const BlockScopeRawPtr &p2) const;
 169   };
 170   typedef std::set<BlockScopeRawPtr, ScopeCompare> BlockScopeSet;
 171   friend class ScopeCompare;
 172
 173   BlockScope(const std::string &name, const std::string &docComment,
 174              StatementPtr stmt, KindOf kind);
 175   virtual ~BlockScope() {}
 176   bool is(KindOf kind) const { return kind == m_kind;}
 177   const std::string &getName() const { return m_name;}
 178   void setName(const std::string name) { m_name = name;}
 179   virtual bool isBuiltin() const { return false; }
 180   StatementPtr getStmt() const { return m_stmt;}
 181   VariableTableConstPtr getVariables() const { return m_variables;}
 182   ConstantTableConstPtr getConstants() const { return m_constants;}
 183   VariableTablePtr getVariables() { return m_variables;}
 184   ConstantTablePtr getConstants() { return m_constants;}
 185   ClassScopeRawPtr getContainingClass();
 186   FunctionScopeRawPtr getContainingNonClosureFunction();
 187   FunctionScopeRawPtr getContainingFunction() const {
 188     return FunctionScopeRawPtr(is(FunctionScope) ?
 189                                (HPHP::FunctionScope*)this : 0);
 190   }
 191   FileScopeRawPtr getContainingFile();
 192   AnalysisResultRawPtr getContainingProgram();
 193
 194   ClassScopeRawPtr findExactClass(ClassScopeRawPtr cls);
 195   FunctionScopeRawPtr findExactFunction(FunctionScopeRawPtr func);
 196
 197   bool hasUser(BlockScopeRawPtr user, int useFlags) const;
 198   void addUse(BlockScopeRawPtr user, int useFlags);
 199
 200   /**
 201    * Helpers for keeping track of break/continue nested level.
 202    */
 203   void incLoopNestedLevel();
 204   void decLoopNestedLevel();
 205   int getLoopNestedLevel() const { return m_loopNestedLevel;}
 206
 207   /**
 208    * Helpers for parsing class functions and variables.
 209    */
 210   ModifierExpressionPtr setModifiers(ModifierExpressionPtr modifiers);
 211   ModifierExpressionPtr getModifiers() { return m_modifiers;}
 212
 213   void setClassInfoAttribute(int flag) {
 214     m_attributeClassInfo |= flag;
 215   }
 216   const std::string &getDocComment() const { return m_docComment;}
 217   void setDocComment(const std::string &doc) { m_docComment = doc;}
 218
 219   /**
 220    * Triggers type inference of all statements inside this block.
 221    */
 222   void inferTypes(AnalysisResultPtr ar);
 223
 224   /**
 225    * Code gen
 226    */
 227   virtual void outputPHP(CodeGenerator &cg, AnalysisResultPtr ar);
 228
 229   virtual bool inPseudoMain() const {
 230     return false;
 231   }
 232
 233   virtual ClassScopePtr getParentScope(AnalysisResultConstPtr ar) const {
 234     return ClassScopePtr();
 235   }
 236
 237   void setOuterScope(BlockScopePtr o) { m_outerScope = o; }
 238   BlockScopePtr getOuterScope() { return m_outerScope.lock(); }
 239   bool isOuterScope() { return m_outerScope.expired(); }
 240
 241   const BlockScopeRawPtrFlagsPtrVec &getDeps() const {
 242     return m_orderedDeps;
 243   }
 244   const BlockScopeRawPtrFlagsVec &getOrderedUsers() const {
 245     return m_orderedUsers;
 246   }
 247
 248   void setMark(Marks m) { m_mark = m;    }
 249   Marks getMark() const { return m_mark; }
 250
 251   void setLockedMark(Marks m) { Lock l(s_jobStateMutex); m_mark = m;    }
 252   Marks getLockedMark() const { Lock l(s_jobStateMutex); return m_mark; }
 253
 254   void incPass() { m_pass++; }
 255   bool isFirstPass() const { return !m_pass; }
 256
 257   void incRunId() { m_runId++; }
 258   int getRunId() const { return m_runId; }
 259
 260   void clearUpdated() { m_updated = 0; }
 261   void addUpdates(int f);
 262   void announceUpdates(int f);
 263   int getUpdated() const { return m_updated; }
 264
 265   void setInTypeInference(bool inTypeInference) {
 266     m_inTypeInference = inTypeInference;
 267   }
 268   bool inTypeInference() const { return m_inTypeInference; }
 269
 270   void setInVisitScopes(bool inVisitScopes) {
 271     m_inVisitScopes = inVisitScopes;
 272   }
 273   bool inVisitScopes() const { return m_inVisitScopes; }
 274
 275   void setNeedsReschedule(bool needsReschedule) {
 276     m_needsReschedule = needsReschedule;
 277   }
 278   bool needsReschedule() const { return m_needsReschedule; }
 279
 280   void setRescheduleFlags(int rescheduleFlags) {
 281     m_rescheduleFlags = rescheduleFlags;
 282   }
 283   int rescheduleFlags() const { return m_rescheduleFlags; }
 284
 285   void incEffectsTag() { m_effectsTag++; }
 286   int getEffectsTag() const { return m_effectsTag; }
 287
 288   Mutex &getMutex() { return m_mutex; }
 289   InferTypesMutex &getInferTypesMutex() { return m_inferTypesMutex; }
 290
 291   void setNumDepsToWaitFor(int n) {
 292     assert(n >= 0);
 293     m_numDepsToWaitFor = n;
 294   }
 295   int getNumDepsToWaitFor() const {
 296     return m_numDepsToWaitFor;
 297   }
 298   int incNumDepsToWaitFor() {
 299     return ++m_numDepsToWaitFor;
 300   }
 301   int decNumDepsToWaitFor() {
 302     assert(m_numDepsToWaitFor > 0);
 303     return --m_numDepsToWaitFor;
 304   }
 305
 306   inline void assertNumDepsSanity() const {
 307 #ifdef HPHP_DETAILED_TYPE_INF_ASSERT
 308     int waiting = 0;
 309     const BlockScopeRawPtrFlagsPtrVec &deps = getDeps();
 310     for (BlockScopeRawPtrFlagsPtrVec::const_iterator it = deps.begin(),
 311          end = deps.end(); it != end; ++it) {
 312       const BlockScopeRawPtrFlagsPtrPair &p(*it);
 313       int m = p.first->getMark();
 314       if (m == MarkWaiting ||
 315           m == MarkReady   ||
 316           m == MarkProcessing) {
 317         waiting++;
 318       } else {
 319         assert(m == MarkProcessed);
 320       }
 321     }
 322     // >= b/c of cycles
 323     assert(waiting >= getNumDepsToWaitFor());
 324 #endif /* HPHP_DETAILED_TYPE_INF_ASSERT */
 325   }
 326
 327   void setForceRerun(bool v) { m_forceRerun = v; }
 328   bool forceRerun() const { return m_forceRerun; }
 329
 330   int selfUser() const { return m_selfUser; }
 331
 332 protected:
 333   std::string m_originalName;
 334   std::string m_name;
 335   int m_attributeClassInfo;
 336   std::string m_docComment;
 337   StatementPtr m_stmt;
 338   KindOf m_kind;
 339   VariableTablePtr m_variables;
 340   ConstantTablePtr m_constants;
 341   BlockScopeRawPtr m_outerScope;
 342
 343   int m_loopNestedLevel;
 344   ModifierExpressionPtr m_modifiers;
 345   StatementListPtr m_includes;
 346   int m_pass;
 347   int m_updated;
 348   int m_runId;
 349 private:
 350   Marks m_mark;
 351   BlockScopeRawPtrFlagsPtrVec  m_orderedDeps;
 352   BlockScopeRawPtrFlagsVec     m_orderedUsers;
 353   BlockScopeRawPtrFlagsHashMap m_userMap;
 354   int m_effectsTag;
 355   int m_numDepsToWaitFor;
 356   Mutex m_mutex;
 357   InferTypesMutex m_inferTypesMutex;
 358   bool m_forceRerun;      /* do we need to be re-run (allows deps to run during
 359                            * re-schedule) */
 360   bool m_inTypeInference; /* are we in AnalysisResult::inferTypes() */
 361   bool m_inVisitScopes;   /* are we in visitScope() */
 362   bool m_needsReschedule; /* do we need to be re-scheduled (does not allow deps
 363                            * to run during re-schedule)  */
 364   int  m_rescheduleFlags; /* who do we need to run after a re-schedule */
 365   int  m_selfUser;
 366 public:
 367   static Mutex s_jobStateMutex;
 368   static Mutex s_depsMutex;
 369   static Mutex s_constMutex;
 370 };
 371
 372 ///////////////////////////////////////////////////////////////////////////////
 373 }
 374 #endif // incl_HPHP_BLOCK_SCOPE_H_