hphp/compiler/analysis/analysis_result.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- 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_ANALYSIS_RESULT_H_
  18 #define incl_HPHP_ANALYSIS_RESULT_H_
  19
  20 #include <compiler/code_generator.h>
  21 #include <compiler/analysis/code_error.h>
  22 #include <compiler/option.h>
  23 #include <compiler/analysis/block_scope.h>
  24 #include <compiler/analysis/symbol_table.h>
  25 #include <compiler/analysis/function_container.h>
  26 #include <compiler/package.h>
  27
  28 #include <util/string_bag.h>
  29 #include <util/thread_local.h>
  30
  31 #include <boost/graph/adjacency_list.hpp>
  32 #include <tbb/concurrent_hash_map.h>
  33
  34 namespace HPHP {
  35 ///////////////////////////////////////////////////////////////////////////////
  36
  37
  38 DECLARE_BOOST_TYPES(ClassScope);
  39 DECLARE_BOOST_TYPES(FileScope);
  40 DECLARE_BOOST_TYPES(FunctionScope);
  41 DECLARE_BOOST_TYPES(Location);
  42 DECLARE_BOOST_TYPES(AnalysisResult);
  43 DECLARE_BOOST_TYPES(ScalarExpression);
  44
  45 class AnalysisResult : public BlockScope, public FunctionContainer {
  46 public:
  47   /**
  48    * There are multiple passes over our syntax trees. This lists all of them.
  49    */
  50   enum Phase {
  51     // parse
  52     ParseAllFiles,
  53
  54     // analyzeProgram
  55     AnalyzeAll,
  56     AnalyzeFinal,
  57
  58     // pre-optimize
  59     FirstPreOptimize,
  60
  61     // inferTypes
  62     FirstInference,
  63
  64     // post-optimize
  65     PostOptimize,
  66
  67     CodeGen,
  68   };
  69
  70   enum FindClassBy {
  71     ClassName,
  72     MethodName,
  73     PropertyName
  74   };
  75
  76   enum GlobalSymbolType {
  77     KindOfStaticGlobalVariable,
  78     KindOfDynamicGlobalVariable,
  79     KindOfMethodStaticVariable,
  80     KindOfClassStaticVariable,
  81     KindOfDynamicConstant,
  82     KindOfPseudoMain,
  83     KindOfRedeclaredFunction,
  84     KindOfRedeclaredClass,
  85     KindOfRedeclaredClassId,
  86     KindOfVolatileClass,
  87     KindOfLazyStaticInitializer,
  88
  89     GlobalSymbolTypeCount
  90   };
  91
  92   class Locker {
  93   public:
  94     explicit Locker(const AnalysisResult *ar) :
  95         m_ar(const_cast<AnalysisResult*>(ar)),
  96         m_mutex(m_ar->getMutex()) {
  97       m_mutex.lock();
  98     }
  99     explicit Locker(AnalysisResultConstPtr ar) :
 100         m_ar(const_cast<AnalysisResult*>(ar.get())),
 101         m_mutex(m_ar->getMutex()) {
 102       m_mutex.lock();
 103     }
 104     Locker(const Locker &l) : m_ar(l.m_ar), m_mutex(l.m_mutex) {
 105       const_cast<Locker&>(l).m_ar = 0;
 106     }
 107     ~Locker() {
 108       if (m_ar) m_mutex.unlock();
 109     }
 110     AnalysisResultPtr get() const {
 111       return m_ar->shared_from_this();
 112     }
 113     AnalysisResult *operator->() const {
 114       return m_ar;
 115     }
 116   private:
 117     AnalysisResult *m_ar;
 118     Mutex &m_mutex;
 119   };
 120
 121 public:
 122   AnalysisResult();
 123   Locker lock() const { return Locker(this); }
 124   void setPackage(Package *package) { m_package = package;}
 125   void setParseOnDemand(bool v) { m_parseOnDemand = v;}
 126   bool isParseOnDemand() const { return m_package && m_parseOnDemand;}
 127   void setParseOnDemandDirs(const std::vector<std::string> &dirs) {
 128     assert(m_package && !m_parseOnDemand);
 129     m_parseOnDemandDirs = dirs;
 130   }
 131
 132   /**
 133    * create_function() generates extra PHP code that defines the lambda.
 134    * Stores the code in a temporary string, so we can parse this as an
 135    * extra file appended to parsed code.
 136    */
 137   void appendExtraCode(const std::string &key, const std::string &code);
 138   void appendExtraCode(const std::string &key, const std::string &code) const;
 139   void parseExtraCode(const std::string &key);
 140
 141   Phase getPhase() const { return m_phase;}
 142   void setPhase(Phase phase) { m_phase = phase;}
 143
 144   int getFunctionCount() const;
 145   int getClassCount() const;
 146   void countReturnTypes(std::map<std::string, int> &counts);
 147
 148   void addEntryPoint(const std::string &name);
 149   void addEntryPoints(const std::vector<std::string> &names);
 150
 151   void loadBuiltinFunctions();
 152   void loadBuiltins();
 153   void analyzeProgram(bool system = false);
 154   void analyzeIncludes();
 155   void analyzeProgramFinal();
 156   void analyzePerfectVirtuals();
 157   void dump();
 158
 159   void docJson(const std::string &filename);
 160   void visitFiles(void (*cb)(AnalysisResultPtr, StatementPtr, void*),
 161                   void *data);
 162
 163   void getScopesSet(BlockScopeRawPtrQueue &v);
 164
 165   void preOptimize();
 166   void inferTypes();
 167   void postOptimize();
 168
 169   /**
 170    * Force all class variables to be variants, since l-val or reference
 171    * of dynamic properties are used.
 172    */
 173   void forceClassVariants(
 174       ClassScopePtr curScope,
 175       bool doStatic,
 176       bool acquireLocks = false);
 177
 178   /**
 179    * Force specified variable of all classes to be variants.
 180    */
 181   void forceClassVariants(
 182       const std::string &name,
 183       ClassScopePtr curScope,
 184       bool doStatic,
 185       bool acquireLocks = false);
 186
 187   /**
 188    * Code generation functions.
 189    */
 190   bool outputAllPHP(CodeGenerator::Output output);
 191
 192   /**
 193    * Parser creates a FileScope upon parsing a new file.
 194    */
 195   void parseOnDemand(const std::string &name) const;
 196   void parseOnDemandByClass(const std::string &name) const {
 197     parseOnDemandBy(name, Option::AutoloadClassMap);
 198   }
 199   void parseOnDemandByFunction(const std::string &name) const {
 200     parseOnDemandBy(name, Option::AutoloadFuncMap);
 201   }
 202   void parseOnDemandByConstant(const std::string &name) const {
 203     parseOnDemandBy(name, Option::AutoloadConstMap);
 204   }
 205   void parseOnDemandBy(const std::string &name,
 206                        const std::map<std::string,std::string>& amap) const;
 207   FileScopePtr findFileScope(const std::string &name) const;
 208   const StringToFileScopePtrMap &getAllFiles() { return m_files;}
 209   const std::vector<FileScopePtr> &getAllFilesVector() {
 210     return m_fileScopes;
 211   }
 212
 213   void addFileScope(FileScopePtr fileScope);
 214
 215   /**
 216    * Declarations
 217    */
 218   bool declareFunction(FunctionScopePtr funcScope) const;
 219   bool declareClass(ClassScopePtr classScope) const;
 220   void declareUnknownClass(const std::string &name);
 221   bool declareConst(FileScopePtr fs, const std::string &name);
 222
 223   /**
 224    * Dependencies
 225    */
 226   void link(FileScopePtr user, FileScopePtr provider);
 227   bool addClassDependency(FileScopePtr usingFile,
 228                           const std::string &className);
 229   bool addFunctionDependency(FileScopePtr usingFile,
 230                              const std::string &functionName);
 231   bool addIncludeDependency(FileScopePtr usingFile,
 232                             const std::string &includeFilename);
 233   bool addConstantDependency(FileScopePtr usingFile,
 234                              const std::string &constantName);
 235
 236   ClassScopePtr findClass(const std::string &className) const;
 237   ClassScopePtr findClass(const std::string &className,
 238                           FindClassBy by);
 239   /**
 240    * Find all the redeclared classes by the name, excluding system classes.
 241    * Note that system classes cannot be redeclared.
 242    */
 243   const ClassScopePtrVec &findRedeclaredClasses(
 244     const std::string &className) const;
 245   /**
 246    * Find all the classes by the name, including system classes.
 247    */
 248   ClassScopePtrVec findClasses(const std::string &className) const;
 249   bool classMemberExists(const std::string &name, FindClassBy by) const;
 250   ClassScopePtr findExactClass(ConstructPtr cs, const std::string &name) const;
 251   bool checkClassPresent(ConstructPtr cs, const std::string &name) const;
 252   FunctionScopePtr findFunction(const std::string &funcName) const ;
 253   BlockScopeConstPtr findConstantDeclarer(const std::string &constName) const {
 254     return const_cast<AnalysisResult*>(this)->findConstantDeclarer(constName);
 255   }
 256   BlockScopePtr findConstantDeclarer(const std::string &constName);
 257
 258   bool isConstantDeclared(const std::string &constName) const;
 259   bool isConstantRedeclared(const std::string &constName) const;
 260   bool isSystemConstant(const std::string &constName) const;
 261
 262   /**
 263    * For function declaration parsing.
 264    */
 265   static std::string prepareFile(const char *root, const std::string &fileName,
 266                                  bool chop, bool stripPath = true);
 267
 268   void setOutputPath(const std::string &path) {
 269     m_outputPath = path;
 270   }
 271   const std::string &getOutputPath() {
 272     return m_outputPath;
 273   }
 274
 275   /**
 276    * Literal string to String precomputation
 277    */
 278   std::string getLiteralStringName(int64_t hash, int index, bool iproxy = false);
 279   std::string getLitVarStringName(int64_t hash, int index, bool iproxy = false);
 280   int getLiteralStringId(const std::string &s, int &index);
 281
 282   /**
 283    * Profiling runtime parameter type
 284    */
 285   std::string getFuncId(ClassScopePtr cls, FunctionScopePtr func);
 286   std::vector<const char *> &getFuncTableBucket(FunctionScopePtr func);
 287
 288   std::set<std::string> m_variableTableFunctions;
 289   std::set<int> m_concatLengths;
 290   int m_arrayLitstrKeyMaxSize;
 291   int m_arrayIntegerKeyMaxSize;
 292
 293   std::string getHashedName(int64_t hash, int index, const char *prefix,
 294                             bool longName = false);
 295   void addNamedLiteralVarString(const std::string &s);
 296   void addNamedScalarVarArray(const std::string &s);
 297   StringToClassScopePtrVecMap getExtensionClasses();
 298   void addInteger(int64_t n);
 299 private:
 300   Package *m_package;
 301   bool m_parseOnDemand;
 302   std::vector<std::string> m_parseOnDemandDirs;
 303   Phase m_phase;
 304   StringToFileScopePtrMap m_files;
 305   FileScopePtrVec m_fileScopes;
 306
 307   StringBag m_extraCodeFileNames;
 308   std::map<std::string, std::string> m_extraCodes;
 309
 310   StringToClassScopePtrMap m_systemClasses;
 311   StringToFunctionScopePtrMap m_functionDecs;
 312   StringToFunctionScopePtrVecMap m_functionReDecs;
 313   StringToClassScopePtrVecMap m_classDecs;
 314   StringToClassScopePtrVecMap m_methodToClassDecs;
 315   StringToFileScopePtrMap m_constDecs;
 316   std::set<std::string> m_constRedeclared;
 317
 318   bool m_classForcedVariants[2];
 319
 320   StatementPtrVec m_stmts;
 321   StatementPtr m_stmt;
 322
 323   std::string m_outputPath;
 324 public:
 325   AnalysisResultPtr shared_from_this() {
 326     return boost::static_pointer_cast<AnalysisResult>
 327       (BlockScope::shared_from_this());
 328   }
 329
 330   AnalysisResultConstPtr shared_from_this() const {
 331     return boost::static_pointer_cast<const AnalysisResult>
 332       (BlockScope::shared_from_this());
 333   }
 334
 335 private:
 336   BlockScopePtrVec m_ignoredScopes;
 337
 338   typedef boost::adjacency_list<boost::setS, boost::vecS> Graph;
 339   typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 340   typedef boost::graph_traits<Graph>::adjacency_iterator adjacency_iterator;
 341   Mutex m_depGraphMutex;
 342   Graph m_depGraph;
 343   typedef std::map<vertex_descriptor, FileScopePtr> VertexToFileScopePtrMap;
 344   VertexToFileScopePtrMap m_fileVertMap;
 345
 346   /**
 347    * Checks whether the file is in one of the on-demand parsing directories.
 348    */
 349   bool inParseOnDemandDirs(const std::string &filename) const;
 350
 351   void collectFunctionsAndClasses(FileScopePtr fs);
 352
 353   /**
 354    * Making sure symbol orders are not different even with multithreading, so
 355    * to make sure generated code are consistent every time.
 356    */
 357   void canonicalizeSymbolOrder();
 358
 359   /**
 360    * Checks circular class derivations that can cause stack overflows for
 361    * subsequent analysis. Also checks to make sure no two redundant parents.
 362    */
 363   void checkClassDerivations();
 364
 365   int getFileSize(FileScopePtr fs);
 366
 367 public:
 368   static DECLARE_THREAD_LOCAL(BlockScopeRawPtr, s_currentScopeThreadLocal);
 369   static DECLARE_THREAD_LOCAL(BlockScopeRawPtrFlagsHashMap,
 370                               s_changedScopesMapThreadLocal);
 371
 372 #ifdef HPHP_INSTRUMENT_PROCESS_PARALLEL
 373   static int                                  s_NumDoJobCalls;
 374   static ConcurrentBlockScopeRawPtrIntHashMap s_DoJobUniqueScopes;
 375   static int                                  s_NumForceRerunGlobal;
 376   static int                                  s_NumReactivateGlobal;
 377   static int                                  s_NumForceRerunUseKinds;
 378   static int                                  s_NumReactivateUseKinds;
 379 #endif /* HPHP_INSTRUMENT_PROCESS_PARALLEL */
 380
 381 private:
 382   template <typename Visitor>
 383   void processScopesParallel(const char *id, void *opaque = nullptr);
 384
 385   template <typename Visitor>
 386   void preWaitCallback(bool first,
 387                        const BlockScopeRawPtrQueue &scopes,
 388                        void *opaque);
 389
 390   template <typename Visitor>
 391   bool postWaitCallback(bool first,
 392                         bool again,
 393                         const BlockScopeRawPtrQueue &scopes,
 394                         void *opaque);
 395 };
 396
 397 ///////////////////////////////////////////////////////////////////////////////
 398 // Type Inference
 399
 400 class RescheduleException : public Exception {
 401 public:
 402   explicit RescheduleException(BlockScopeRawPtr scope) :
 403     Exception(), m_scope(scope) {}
 404   BlockScopeRawPtr &getScope() { return m_scope; }
 405 #ifdef HPHP_INSTRUMENT_TYPE_INF
 406   static int s_NumReschedules;
 407   static int s_NumForceRerunSelfCaller;
 408   static int s_NumRetTypesChanged;
 409 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 410 private:
 411   BlockScopeRawPtr m_scope;
 412 };
 413
 414 class SetCurrentScope {
 415 public:
 416   explicit SetCurrentScope(BlockScopeRawPtr scope) {
 417     assert(!((*AnalysisResult::s_currentScopeThreadLocal).get()));
 418     *AnalysisResult::s_currentScopeThreadLocal = scope;
 419     scope->setInVisitScopes(true);
 420   }
 421   ~SetCurrentScope() {
 422     (*AnalysisResult::s_currentScopeThreadLocal)->setInVisitScopes(false);
 423     AnalysisResult::s_currentScopeThreadLocal.destroy();
 424   }
 425 };
 426
 427 #define IMPLEMENT_INFER_AND_CHECK_ASSERT(scope) \
 428   do { \
 429     assert(AnalysisResult::s_currentScopeThreadLocal->get()); \
 430     assert(AnalysisResult::s_currentScopeThreadLocal->get() == \
 431            (scope).get()); \
 432     (scope)->getInferTypesMutex().assertOwnedBySelf(); \
 433   } while (0)
 434
 435 #ifdef HPHP_INSTRUMENT_TYPE_INF
 436 typedef std::pair < const char *, int > LEntry;
 437
 438 struct LEntryHasher {
 439   bool equal(const LEntry &l1, const LEntry &l2) const {
 440     assert(l1.first);
 441     assert(l2.first);
 442     return l1.second == l2.second &&
 443            strcmp(l1.first, l2.first) == 0;
 444   }
 445   size_t hash(const LEntry &l) const {
 446     assert(l.first);
 447     return hash_string(l.first) ^ l.second;
 448   }
 449 };
 450
 451 typedef tbb::concurrent_hash_map < LEntry, int, LEntryHasher >
 452         LProfileMap;
 453 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 454
 455 class BaseTryLock {
 456   friend class TryLock;
 457   friend class ConditionalTryLock;
 458 public:
 459 #ifdef HPHP_INSTRUMENT_TYPE_INF
 460   static LProfileMap s_LockProfileMap;
 461 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 462 private:
 463   inline bool acquireImpl(BlockScopeRawPtr scopeToLock) {
 464     // A class scope can NEVER grab a lock on a function scope
 465     BlockScopeRawPtr current ATTRIBUTE_UNUSED =
 466       *(AnalysisResult::s_currentScopeThreadLocal.get());
 467     assert(current);
 468     assert(!current->is(BlockScope::ClassScope) ||
 469            !scopeToLock->is(BlockScope::FunctionScope));
 470     return m_mutex.tryLock();
 471   }
 472 #ifdef HPHP_INSTRUMENT_TYPE_INF
 473   BaseTryLock(BlockScopeRawPtr scopeToLock,
 474               const char * fromFunction,
 475               int fromLine,
 476               bool lockCondition = true,
 477               bool profile = true)
 478     : m_profiler(profile),
 479       m_mutex(scopeToLock->getInferTypesMutex()),
 480       m_acquired(false) {
 481     if (LIKELY(lockCondition)) {
 482       bool success = acquireImpl(scopeToLock);
 483       if (UNLIKELY(!success)) {
 484         // put entry in profiler
 485         LProfileMap::accessor acc;
 486         LEntry key(fromFunction, fromLine);
 487         if (!s_LockProfileMap.insert(acc, key)) {
 488           // pre-existing
 489           acc->second++;
 490         } else {
 491           acc->second = 1;
 492         }
 493         // could not acquire lock, throw reschedule exception
 494         throw RescheduleException(scopeToLock);
 495       }
 496       assert(success);
 497       m_acquired = true;
 498       m_mutex.assertOwnedBySelf();
 499     }
 500   }
 501 #else
 502   explicit BaseTryLock(BlockScopeRawPtr scopeToLock,
 503                        bool lockCondition = true,
 504                        bool profile = true)
 505     : m_profiler(profile),
 506       m_mutex(scopeToLock->getInferTypesMutex()),
 507       m_acquired(false) {
 508     if (LIKELY(lockCondition)) {
 509       bool success = acquireImpl(scopeToLock);
 510       if (UNLIKELY(!success)) {
 511         // could not acquire lock, throw reschedule exception
 512         throw RescheduleException(scopeToLock);
 513       }
 514       assert(success);
 515       m_acquired = true;
 516       m_mutex.assertOwnedBySelf();
 517     }
 518   }
 519 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 520
 521   ~BaseTryLock() {
 522     if (m_acquired) m_mutex.unlock();
 523   }
 524
 525   LockProfiler     m_profiler;
 526   InferTypesMutex& m_mutex;
 527   bool             m_acquired;
 528 };
 529
 530 class TryLock : public BaseTryLock {
 531 public:
 532 #ifdef HPHP_INSTRUMENT_TYPE_INF
 533   TryLock(BlockScopeRawPtr scopeToLock,
 534           const char * fromFunction,
 535           int fromLine,
 536           bool profile = true) :
 537     BaseTryLock(scopeToLock, fromFunction, fromLine, true, profile) {}
 538 #else
 539   explicit TryLock(BlockScopeRawPtr scopeToLock,
 540                    bool profile = true) :
 541     BaseTryLock(scopeToLock, true, profile) {}
 542 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 543 };
 544
 545 class ConditionalTryLock : public BaseTryLock {
 546 public:
 547 #ifdef HPHP_INSTRUMENT_TYPE_INF
 548   ConditionalTryLock(BlockScopeRawPtr scopeToLock,
 549                      const char * fromFunction,
 550                      int fromLine,
 551                      bool condition,
 552                      bool profile = true) :
 553     BaseTryLock(scopeToLock, fromFunction, fromLine, condition, profile) {}
 554 #else
 555   ConditionalTryLock(BlockScopeRawPtr scopeToLock,
 556                      bool condition,
 557                      bool profile = true) :
 558     BaseTryLock(scopeToLock, condition, profile) {}
 559 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 560 };
 561
 562 #define GET_LOCK(scopeToLock) \
 563   SimpleLock _lock((scopeToLock)->getInferTypesMutex())
 564
 565 #define COND_GET_LOCK(scopeToLock, condition) \
 566   SimpleConditionalLock _clock((scopeToLock)->getInferTypesMutex(), \
 567                                (condition))
 568
 569 #define GET_LOCK_THIS() \
 570   SimpleLock _lock(this->getInferTypesMutex())
 571
 572 #define COND_GET_LOCK_THIS(condition) \
 573   SimpleConditionalLock _clock(this->getInferTypesMutex(), (condition))
 574
 575 #ifdef HPHP_INSTRUMENT_TYPE_INF
 576   #define TRY_LOCK(scopeToLock) \
 577     TryLock _tl((scopeToLock), __PRETTY_FUNCTION__, __LINE__)
 578
 579   #define COND_TRY_LOCK(scopeToLock, condition) \
 580     ConditionalTryLock _ctl((scopeToLock), __PRETTY_FUNCTION__, \
 581                             __LINE__, condition)
 582 #else
 583   #define TRY_LOCK(scopeToLock) \
 584     TryLock _tl((scopeToLock))
 585
 586   #define COND_TRY_LOCK(scopeToLock, condition) \
 587     ConditionalTryLock _ctl((scopeToLock), (condition))
 588 #endif /* HPHP_INSTRUMENT_TYPE_INF */
 589
 590 #define TRY_LOCK_THIS() \
 591   TRY_LOCK(BlockScopeRawPtr(this))
 592
 593 #define COND_TRY_LOCK_THIS(condition) \
 594   COND_TRY_LOCK(BlockScopeRawPtr(this), condition)
 595
 596 ///////////////////////////////////////////////////////////////////////////////
 597 }
 598 #endif // incl_HPHP_ANALYSIS_RESULT_H_