hphp/runtime/ext/facts/symbol-map.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source path is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the path 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 #pragma once
  18
  19 #include <atomic>
  20 #include <memory>
  21 #include <mutex>
  22 #include <optional>
  23 #include <queue>
  24 #include <string>
  25 #include <vector>
  26
  27 #include <folly/Executor.h>
  28 #include <folly/SharedMutex.h>
  29 #include <folly/Synchronized.h>
  30 #include <folly/experimental/io/FsUtil.h>
  31 #include <folly/futures/Future.h>
  32 #include <folly/futures/FutureSplitter.h>
  33
  34 #include "hphp/runtime/ext/facts/autoload-db.h"
  35 #include "hphp/runtime/ext/facts/file-facts.h"
  36 #include "hphp/runtime/ext/facts/inheritance-info.h"
  37 #include "hphp/runtime/ext/facts/lazy-two-way-map.h"
  38 #include "hphp/runtime/ext/facts/path-symbols-map.h"
  39 #include "hphp/runtime/ext/facts/string-ptr.h"
  40 #include "hphp/runtime/ext/facts/symbol-types.h"
  41 #include "hphp/runtime/ext/facts/type-attribute-map.h"
  42 #include "hphp/util/assertions.h"
  43 #include "hphp/util/hash-map.h"
  44 #include "hphp/util/hash-set.h"
  45 #include "hphp/util/sha1.h"
  46 #include "hphp/util/sqlite-wrapper.h"
  47
  48 namespace HPHP {
  49 namespace Facts {
  50
  51 struct UpdateDBWorkItem;
  52
  53 /**
  54  * Stores and updates one PathToSymbolsMap for each kind of symbol.
  55  *
  56  * Multiple readers can run concurrently with one writer, but only one
  57  * call to SymbolMap::update should happen at any given time.
  58  *
  59  * Queries the SQLite AutoloadDB when the DB has information
  60  * we don't, and updates the AutoloadDB when we have
  61  * information the DB doesn't have.
  62  */
  63 template <typename S> struct SymbolMap {
  64   explicit SymbolMap(
  65       folly::fs::path root,
  66       DBData dbData,
  67       SQLite::OpenMode dbMode = SQLite::OpenMode::ReadWrite);
  68   SymbolMap() = delete;
  69   SymbolMap(const SymbolMap&) = delete;
  70   SymbolMap(SymbolMap&&) noexcept = delete;
  71   SymbolMap& operator=(const SymbolMap&) = delete;
  72   SymbolMap& operator=(SymbolMap&&) noexcept = delete;
  73   ~SymbolMap();
  74
  75   /**
  76    * Resolve a type's name to its canonical, correctly-capitalized name.
  77    *
  78    * Return nullptr if the type is not defined, or if the type is defined in
  79    * more than one file.
  80    */
  81   std::optional<Symbol<S, SymKind::Type>> getTypeName(const S& type);
  82
  83   /**
  84    * Return the one and only definition for the given symbol.
  85    *
  86    * If the symbol is defined in no files, or in more than one file,
  87    * return nullptr.
  88    *
  89    * These methods may fill the map with information from the SQLite
  90    * DB, and as such may throw SQLite exceptions.
  91    */
  92   Path<S> getTypeFile(Symbol<S, SymKind::Type> type);
  93   Path<S> getTypeFile(const S& type);
  94   Path<S> getFunctionFile(Symbol<S, SymKind::Function> function);
  95   Path<S> getFunctionFile(const S& function);
  96   Path<S> getConstantFile(Symbol<S, SymKind::Constant> constant);
  97   Path<S> getConstantFile(const S& constant);
  98   Path<S> getTypeAliasFile(Symbol<S, SymKind::Type> typeAlias);
  99   Path<S> getTypeAliasFile(const S& typeAlias);
 100
 101   /**
 102    * Return all symbols in the repo, along with the relative path defining
 103    * them. For large repos, this will be slow.
 104    *
 105    * Results are returned in an unspecified order. If a symbol is defined in
 106    * more than one path, the symbol will appear multiple times in the returned
 107    * vector, with each path defining it.
 108    */
 109   std::vector<std::pair<Symbol<S, SymKind::Type>, Path<S>>> getAllTypes();
 110   std::vector<std::pair<Symbol<S, SymKind::Function>, Path<S>>>
 111   getAllFunctions();
 112   std::vector<std::pair<Symbol<S, SymKind::Constant>, Path<S>>>
 113   getAllConstants();
 114   std::vector<std::pair<Symbol<S, SymKind::Type>, Path<S>>> getAllTypeAliases();
 115
 116   /**
 117    * Return all symbols of a given kind declared in the given path.
 118    *
 119    * These methods may fill the map with information from the SQLite
 120    * DB, and as such may throw SQLite exceptions.
 121    */
 122   std::vector<Symbol<S, SymKind::Type>> getFileTypes(Path<S> path);
 123   std::vector<Symbol<S, SymKind::Type>>
 124   getFileTypes(const folly::fs::path& path);
 125
 126   std::vector<Symbol<S, SymKind::Function>> getFileFunctions(Path<S> path);
 127   std::vector<Symbol<S, SymKind::Function>>
 128   getFileFunctions(const folly::fs::path& path);
 129
 130   std::vector<Symbol<S, SymKind::Constant>> getFileConstants(Path<S> path);
 131   std::vector<Symbol<S, SymKind::Constant>>
 132   getFileConstants(const folly::fs::path& path);
 133
 134   std::vector<Symbol<S, SymKind::Type>> getFileTypeAliases(Path<S> path);
 135   std::vector<Symbol<S, SymKind::Type>>
 136   getFileTypeAliases(const folly::fs::path& path);
 137
 138   /**
 139    * Return inheritance data about the given type
 140    */
 141   std::vector<Symbol<S, SymKind::Type>>
 142   getBaseTypes(Symbol<S, SymKind::Type> derivedType, DeriveKind kind);
 143   std::vector<Symbol<S, SymKind::Type>>
 144   getBaseTypes(const S& derivedType, DeriveKind kind);
 145
 146   std::vector<Symbol<S, SymKind::Type>>
 147   getDerivedTypes(Symbol<S, SymKind::Type> baseType, DeriveKind kind);
 148   std::vector<Symbol<S, SymKind::Type>>
 149   getDerivedTypes(const S& baseType, DeriveKind kind);
 150
 151   /**
 152    * Return all types which transitively extend, implement, or use the given
 153    * base type.
 154    *
 155    * `kinds` is a bitmask dictating whether we should follow classes,
 156    * interfaces, enums, or traits. If one of these kinds is missing, we don't
 157    * include anything of that kind, or any of their subtypes.
 158    *
 159    * `deriveKinds` is a bitmask dictating whether we should follow `extends` or
 160    * `require extends` relationships.
 161    */
 162   using DerivedTypeInfo =
 163       std::tuple<Symbol<S, SymKind::Type>, Path<S>, TypeKind, TypeFlagMask>;
 164   std::vector<DerivedTypeInfo> getTransitiveDerivedTypes(
 165       Symbol<S, SymKind::Type> baseType,
 166       TypeKindMask kinds = kTypeKindAll,
 167       DeriveKindMask deriveKinds = kDeriveKindAll);
 168   std::vector<DerivedTypeInfo> getTransitiveDerivedTypes(
 169       const S& baseType,
 170       TypeKindMask kinds = kTypeKindAll,
 171       DeriveKindMask deriveKinds = kDeriveKindAll);
 172
 173   /**
 174    * Return the attributes of a type
 175    */
 176   std::vector<Symbol<S, SymKind::Type>>
 177   getAttributesOfType(Symbol<S, SymKind::Type> type);
 178   std::vector<Symbol<S, SymKind::Type>> getAttributesOfType(const S& type);
 179
 180   /**
 181    * Return the types and type aliases with a given attribute
 182    */
 183   std::vector<Symbol<S, SymKind::Type>>
 184   getTypesAndTypeAliasesWithAttribute(Symbol<S, SymKind::Type> attr);
 185   std::vector<Symbol<S, SymKind::Type>>
 186   getTypesAndTypeAliasesWithAttribute(const S& attr);
 187
 188   /**
 189    * Return the argument at the given position of a given type with a given
 190    * attribute.
 191    *
 192    * So if a type were defined with an attribute like this:
 193    *
 194    *     <<Oncalls('hhvm')>>
 195    *     class Foo {}
 196    *
 197    * You'd expect to be able to extract that "hhvm" argument this way:
 198    *
 199    *     getAttributeArg("Foo", "Oncalls").at(0) == "hhvm"
 200    *
 201    * If this function returns an empty vector, it could be because:
 202    *
 203    * - The type is not defined.
 204    * - The type is defined in more than one file, violating the One Definition
 205    *   Rule.
 206    * - The type doesn't have the given attribute.
 207    * - The attribute doesn't have any arguments.
 208    *
 209    * You can check that the type is defined with `getTypeFile()`, and you can
 210    * check that the type has the given attribute with `getAttributesOfType()`.
 211    */
 212   std::vector<folly::dynamic> getAttributeArgs(
 213       Symbol<S, SymKind::Type> type, Symbol<S, SymKind::Type> attribute);
 214   std::vector<folly::dynamic>
 215   getAttributeArgs(const S& type, const S& attribute);
 216
 217   /**
 218    * Return whether the given type is, for example, a class or interface.
 219    *
 220    * Return `TypeKind::Unknown` if the given type does not have a unique
 221    * definition or is not an autoloadable type at all.
 222    */
 223   TypeKind getKind(Symbol<S, SymKind::Type> type);
 224   TypeKind getKind(const S& type);
 225
 226   bool isTypeAbstract(Symbol<S, SymKind::Type> type);
 227   bool isTypeAbstract(const S& type);
 228
 229   bool isTypeFinal(Symbol<S, SymKind::Type> type);
 230   bool isTypeFinal(const S& type);
 231
 232   /**
 233    * Return a hash representing the given path's last-known checksum.
 234    */
 235   std::optional<SHA1> getSha1Hash(Path<S> path) const;
 236
 237   /**
 238    * For each file, update the SymbolMap with the given file facts.
 239    *
 240    * On success set m_clock to the given clock, and schedule a thread
 241    * to update the DB with the new information.
 242    *
 243    * If the `since` token is nonempty and does not correspond to
 244    * either our in-memory clock or the clock in the DB, throw an
 245    * UpdateExc and do not perform any writes. The caller should
 246    * initiate a fresh Watchman query with a `since` token
 247    * corresponding to the clock in the map.
 248    *
 249    * since: An opaque token originating from Watchman representing the
 250    * beginning of this update's time interval. `since` should either
 251    * be empty (if we're initializing the map from scratch) or should
 252    * be the timestamp currently in either the map or the DB (if we're
 253    * incrementally updating the map).
 254    *
 255    * clock: An opaque token originating from Watchman representing the
 256    * end of this update's time interval. After updating, this clock
 257    * will be stored in the SymbolMap and DB.
 258    *
 259    * alteredPaths: A list of all paths which have changed between the
 260    * last two queries to Watchman (represented by `since` and
 261    * `clock`). This vector must have the same number of elements as
 262    * `facts`.
 263    *
 264    * deletedPaths: A list of all paths which have been deleted between
 265    * the last two queries to Watchman (represented by `since` and
 266    * `clock`).
 267    *
 268    * alteredPathFacts: A list of all symbols found in the
 269    * `alteredPaths`. Must be the same size as `alteredPaths`, and
 270    * elements must be in the same order.
 271    */
 272   void update(
 273       std::string_view since,
 274       std::string_view clock,
 275       std::vector<folly::fs::path> alteredPaths,
 276       std::vector<folly::fs::path> deletedPaths,
 277       std::vector<FileFacts> alteredPathFacts); // throws(SQLiteExc)
 278
 279   /**
 280    * Return an opaque token representing how up to date this map is.
 281    *
 282    * This token originated from Watchman.
 283    */
 284   std::string getClock() const noexcept;
 285
 286   /**
 287    * Return an opaque token representing how up to date the SQLite DB is.
 288    *
 289    * This token originated from Watchman.
 290    */
 291   std::string dbClock() const; // throws(SQLiteExc)
 292
 293   /**
 294    * Return the one and only path where `symbol` is defined.
 295    *
 296    * If `symbol` is not defined, or if `symbol` is defined in more
 297    * than one path, return nullptr.
 298    *
 299    * Query the DB if there is no data about `symbol` in the given
 300    * symbolMap, and add any information found to the corresponding symbolMap if
 301    * so.
 302    */
 303   template <SymKind k>
 304   Path<S> getOnlyPath(Symbol<S, k> symbol); // throws(SQLiteExc)
 305
 306   /**
 307    * Return all the symbols of the kind corresponding to symbolMap
 308    * defined in the given path.
 309    *
 310    * Query the DB if there is no data about `path` in the given
 311    * symbolMap, and add any information found to the corresponding symbolMap if
 312    * so.
 313    */
 314   template <SymKind k>
 315   const typename PathToSymbolsMap<S, k>::PathSymbolMap::ValuesSet&
 316   getPathSymbols(Path<S> path);
 317
 318   void waitForDBUpdate();
 319
 320   /**
 321    * Return every path we know about.
 322    */
 323   hphp_hash_set<Path<S>> getAllPaths() const;
 324
 325   /**
 326    * Return a map from path to hash for every path we know about.
 327    */
 328   hphp_hash_map<Path<S>, SHA1> getAllPathsWithHashes() const;
 329
 330   std::shared_ptr<folly::Executor> m_exec;
 331
 332   struct Data {
 333     /**
 334      * A Watchman clock representing how up-to-date this map is.
 335      *
 336      * If this string is empty, then this map has not yet updated.
 337      */
 338     std::string m_clock;
 339
 340     /**
 341      * Maps between symbols and the paths defining them.
 342      */
 343     PathToSymbolsMap<S, SymKind::Type> m_typePath;
 344     PathToSymbolsMap<S, SymKind::Function> m_functionPath;
 345     PathToSymbolsMap<S, SymKind::Constant> m_constantPath;
 346
 347     /**
 348      * Future chain and queue holding the work that needs to be done before the
 349      * DB is considered up to date.
 350      */
 351     std::queue<UpdateDBWorkItem> m_updateDBWork;
 352     folly::FutureSplitter<folly::Unit> m_updateDBFuture{folly::makeFuture()};
 353
 354     struct TypeInfo {
 355       using KindAndFlags = std::pair<TypeKind, int>;
 356
 357       void setKindAndFlags(
 358           Symbol<S, SymKind::Type> type,
 359           Path<S> path,
 360           TypeKind kind,
 361           int flags) {
 362         auto& defs = m_map[type];
 363         for (auto& [existingPath, existingInfo] : defs) {
 364           if (existingPath == path) {
 365             existingInfo = {kind, flags};
 366             return;
 367           }
 368         }
 369         defs.push_back({path, {kind, flags}});
 370       }
 371
 372       std::optional<std::pair<TypeKind, int>>
 373       getKindAndFlags(Symbol<S, SymKind::Type> type, Path<S> path) const {
 374         auto const it = m_map.find(type);
 375         if (it == m_map.end()) {
 376           return std::nullopt;
 377         }
 378         for (auto& [existingPath, info] : it->second) {
 379           if (existingPath == path) {
 380             return info;
 381           }
 382         }
 383         return std::nullopt;
 384       }
 385
 386       // {type: (path, (kind, flags))}
 387       hphp_hash_map<
 388           Symbol<S, SymKind::Type>,
 389           std::vector<std::pair<Path<S>, KindAndFlags>>>
 390           m_map;
 391     } m_typeKind;
 392
 393     /**
 394      * True if the file exists, false if the file is deleted.
 395      */
 396     hphp_hash_map<Path<S>, bool> m_fileExistsMap;
 397
 398     /**
 399      * Maps between types and their subtypes/supertypes.
 400      */
 401     InheritanceInfo<S> m_inheritanceInfo;
 402
 403     /**
 404      * Maps between types and the attributes that decorate them.
 405      */
 406     TypeAttributeMap<S> m_typeAttrs;
 407
 408     /**
 409      * 40-byte hex strings representing the last-known SHA1 checksums of
 410      * each file we've seen
 411      */
 412     hphp_hash_map<Path<S>, SHA1> m_sha1Hashes;
 413
 414     /**
 415      * Parse the given path and store all its data in the map.
 416      */
 417     void updatePath(Path<S> path, FileFacts facts);
 418
 419     /**
 420      * Remove the given path from the map, along with all data associated with
 421      * the path.
 422      */
 423     void removePath(AutoloadDB& db, SQLiteTxn& txn, Path<S> path);
 424   };
 425
 426 private:
 427   /**
 428    * Update the DB on the time interval beginning at `since` and
 429    * ending at `clock`.
 430    *
 431    * We throw an UpdateExc if the `since` token does not match the clock
 432    * in the DB, and we don't catch SQLiteExc from the underlying SQLite layer.
 433    */
 434   void updateDB(
 435       std::string_view since,
 436       std::string_view clock,
 437       const std::vector<folly::fs::path>& alteredPaths,
 438       const std::vector<folly::fs::path>& deletedPaths,
 439       const std::vector<FileFacts>& alteredPathFacts) const; // throws
 440
 441   /**
 442    * Replace all facts in the DB with in-memory facts about the given path.
 443    */
 444   void updateDBPath(
 445       AutoloadDB& db,
 446       SQLiteTxn& txn,
 447       const folly::fs::path& path,
 448       const FileFacts& facts) const;
 449
 450   /**
 451    * True iff the given path is known to be deleted.
 452    */
 453   bool isPathDeleted(Path<S> path) const noexcept;
 454
 455   /**
 456    * Mark `derivedType` as inheriting from each of the `baseTypes`.
 457    */
 458   void setBaseTypes(
 459       Path<S> path,
 460       Symbol<S, SymKind::Type> derivedType,
 461       std::vector<std::string> baseTypes);
 462
 463   /**
 464    * Load information from the DB about who the given `derivedType` inherits.
 465    */
 466   void loadBaseTypesFromDB(
 467       AutoloadDB& db,
 468       SQLiteTxn& txn,
 469       Path<S> path,
 470       Symbol<S, SymKind::Type> derivedType);
 471
 472   /**
 473    * Helper function to read from and write to m_synchronizedData.
 474    *
 475    * readFn: ((const Data&) -> std::optional<Ret>)
 476    * GetFromDBFn: ((AutoloadDB&, SQLiteTxn&) -> DataFromDB)
 477    * writeFn: ((Data&, DataFromDB) -> Ret)
 478    */
 479   template <
 480       typename Ret,
 481       typename ReadFn,
 482       typename GetFromDBFn,
 483       typename WriteFn>
 484   Ret readOrUpdate(ReadFn readFn, GetFromDBFn getFromDBFn, WriteFn writeFn);
 485
 486   /**
 487    * Return a thread-local connection to the DB associated with this map.
 488    */
 489   AutoloadDB& getDB() const;
 490
 491   /**
 492    * Return the type's kind (class/interface/enum) along with an
 493    * abstract/final bitmask.
 494    */
 495   std::pair<TypeKind, TypeFlagMask>
 496   getKindAndFlags(Symbol<S, SymKind::Type> type);
 497   std::pair<TypeKind, TypeFlagMask>
 498   getKindAndFlags(Symbol<S, SymKind::Type> type, Path<S> path);
 499
 500   std::atomic<bool> m_useDB = false;
 501   // Used to prioritize updates over caching. Pending updates increment this
 502   // count, while caching only occurs if this count is at 0.
 503   std::atomic<size_t> m_updatesInFlight = 0;
 504
 505   folly::Synchronized<Data, folly::SharedMutexWritePriority> m_syncedData;
 506
 507   const folly::fs::path m_root;
 508   const std::string m_schemaHash;
 509   const DBData m_dbData;
 510   const SQLite::OpenMode m_dbMode{SQLite::OpenMode::ReadWrite};
 511 };
 512
 513 struct UpdateDBWorkItem {
 514   std::string m_since;
 515   std::string m_clock;
 516   std::vector<folly::fs::path> m_alteredPaths;
 517   std::vector<folly::fs::path> m_deletedPaths;
 518   std::vector<FileFacts> m_alteredPathFacts;
 519 };
 520
 521 } // namespace Facts
 522 } // namespace HPHP