text: /*
   * Copyright (c) Meta Platforms, Inc. and affiliates.
   *
   * This source code is licensed under the MIT license found in the
   * LICENSE file in the root directory of this source tree.
   */
  
  #include "watchman/InMemoryView.h"
  #include <folly/ScopeGuard.h>
  #include <algorithm>
  #include <chrono>
  #include <memory>
  #include <thread>
  #include "watchman/Errors.h"
  #include "watchman/ThreadPool.h"
  #include "watchman/query/GlobTree.h"
  #include "watchman/query/Query.h"
  #include "watchman/query/QueryContext.h"
  #include "watchman/query/eval.h"
  #include "watchman/root/Root.h"
  #include "watchman/thirdparty/wildmatch/wildmatch.h"
  #include "watchman/watcher/Watcher.h"
  #include "watchman/watchman_file.h"
  
  // Each root gets a number that uniquely identifies it within the process. This
  // helps avoid confusion if a root is removed and then added again.
  static std::atomic<long> next_root_number{1};
  
  namespace watchman {
  
  namespace {
  /** Concatenate dir_name and name around a unix style directory
   * separator.
   * dir_name may be NULL in which case this returns a copy of name.
   */
  inline std::string make_path_name(
      const char* dir_name,
      uint32_t dlen,
      const char* name,
      uint32_t nlen) {
    std::string result;
    result.reserve(dlen + nlen + 1);
  
    if (dlen) {
      result.append(dir_name, dlen);
      // wildmatch wants unix separators
      result.push_back('/');
    }
    result.append(name, nlen);
    return result;
  }
  } // namespace
  
  InMemoryViewCaches::InMemoryViewCaches(
      const w_string& rootPath,
      size_t maxHashes,
      size_t maxSymlinks,
      std::chrono::milliseconds errorTTL)
      : contentHashCache(rootPath, maxHashes, errorTTL),
        symlinkTargetCache(rootPath, maxSymlinks, errorTTL) {}
  
  InMemoryFileResult::InMemoryFileResult(
      const watchman_file* file,
      InMemoryViewCaches& caches)
      : file_(file), caches_(caches) {}
  
  void InMemoryFileResult::batchFetchProperties(
      const std::vector<std::unique_ptr<FileResult>>& files) {
    std::vector<folly::Future<folly::Unit>> readlinkFutures;
    std::vector<folly::Future<folly::Unit>> sha1Futures;
  
    // Since we may initiate some async work in the body of the function
    // below, we need to ensure that we wait for it to complete before
    // we return from this scope, even if we are throwing an exception.
    // If we fail to do so, the continuation on the futures that we
    // schedule will access invalid memory and we'll all feel bad.
    SCOPE_EXIT {
      if (!readlinkFutures.empty()) {
        folly::collectAll(readlinkFutures.begin(), readlinkFutures.end()).wait();
      }
      if (!sha1Futures.empty()) {
        folly::collectAll(sha1Futures.begin(), sha1Futures.end()).wait();
      }
    };
  
    for (auto& f : files) {
      auto* file = dynamic_cast<InMemoryFileResult*>(f.get());
  
      if (file->neededProperties() & FileResult::Property::SymlinkTarget) {
        if (!file->file_->stat.isSymlink()) {
          // If this file is not a symlink then we yield
          // a nullptr w_string instance rather than propagating an error.
          // This behavior is relied upon by the field rendering code and
          // checked in test_symlink.py.
          file->symlinkTarget_ = w_string();
        } else {
          auto dir = file->dirName();
          dir.advance(file->caches_.symlinkTargetCache.rootPath().size());
  
          // If dirName is the root, dir.size() will now be zero
          if (dir.size() > 0) {
            // if not at the root, skip the slash character at the
            // front of dir
            dir.advance(1);
          }
  
          SymlinkTargetCacheKey key{
              w_string::pathCat({dir, file->baseName()}), file->file_->otime};
  
          readlinkFutures.emplace_back(
              caches_.symlinkTargetCache.get(key).thenTry(
                  [file](folly::Try<std::shared_ptr<
                             const SymlinkTargetCache::Node>>&& result) {
                    if (result.hasValue()) {
                      file->symlinkTarget_ = result.value()->value();
                    } else {
                      // we don't have a way to report the error for readlink
                      // due to legacy requirements in the interface, so we
                      // just set it to empty.
                      file->symlinkTarget_ = w_string();
                    }
                  }));
        }
      }
  
      if (file->neededProperties() & FileResult::Property::ContentSha1) {
        auto dir = file->dirName();
        dir.advance(file->caches_.contentHashCache.rootPath().size());
  
        // If dirName is the root, dir.size() will now be zero
        if (dir.size() > 0) {
          // if not at the root, skip the slash character at the
          // front of dir
          dir.advance(1);
        }
  
        ContentHashCacheKey key{
            w_string::pathCat({dir, file->baseName()}),
            size_t(file->file_->stat.size),
            file->file_->stat.mtime};
  
        sha1Futures.emplace_back(caches_.contentHashCache.get(key).thenTry(
            [file](folly::Try<std::shared_ptr<const ContentHashCache::Node>>&&
                       result) {
              file->contentSha1_ =
                  makeResultWith([&] { return result.value()->value(); });
            }));
      }
  
      file->clearNeededProperties();
    }
  }
  
  std::optional<FileInformation> InMemoryFileResult::stat() {
    return file_->stat;
  }
  
  std::optional<size_t> InMemoryFileResult::size() {
    return file_->stat.size;
  }
  
  std::optional<struct timespec> InMemoryFileResult::accessedTime() {
    return file_->stat.atime;
  }
  
  std::optional<struct timespec> InMemoryFileResult::modifiedTime() {
    return file_->stat.mtime;
  }
  
  std::optional<struct timespec> InMemoryFileResult::changedTime() {
    return file_->stat.ctime;
  }
  
  w_string_piece InMemoryFileResult::baseName() {
    return file_->getName();
  }
  
  w_string_piece InMemoryFileResult::dirName() {
    if (!dirName_) {
      dirName_ = file_->parent->getFullPath();
    }
    return dirName_;
  }
  
  std::optional<bool> InMemoryFileResult::exists() {
    return file_->exists;
  }
  
  std::optional<ClockStamp> InMemoryFileResult::ctime() {
    return file_->ctime;
  }
  
  std::optional<ClockStamp> InMemoryFileResult::otime() {
    return file_->otime;
  }
  
  std::optional<w_string> InMemoryFileResult::readLink() {
    if (!symlinkTarget_.has_value()) {
      if (!file_->stat.isSymlink()) {
        // If this file is not a symlink then we immediately yield
        // a nullptr w_string instance rather than propagating an error.
        // This behavior is relied upon by the field rendering code and
        // checked in test_symlink.py.
        symlinkTarget_ = w_string();
        return symlinkTarget_;
      }
      // Need to load the symlink target; batch that up
      accessorNeedsProperties(FileResult::Property::SymlinkTarget);
      return std::nullopt;
    }
    return symlinkTarget_;
  }
  
  std::optional<FileResult::ContentHash> InMemoryFileResult::getContentSha1() {
    if (!file_->exists) {
      // Don't return hashes for files that we believe to be deleted.
      throw std::system_error(
          std::make_error_code(std::errc::no_such_file_or_directory));
    }
  
    if (!file_->stat.isFile()) {
      // We only want to compute the hash for regular files
      throw std::system_error(std::make_error_code(std::errc::is_a_directory));
    }
  
    if (contentSha1_.empty()) {
      accessorNeedsProperties(FileResult::Property::ContentSha1);
      return std::nullopt;
    }
    return contentSha1_.value();
  }
  
  ViewDatabase::ViewDatabase(const w_string& root_path)
      : rootPath_{root_path},
        rootDir_{std::make_unique<watchman_dir>(root_path, nullptr)} {}
  
  watchman_dir* ViewDatabase::resolveDir(const w_string& dir_name, bool create) {
    if (dir_name == rootPath_) {
      return rootDir_.get();
    }
  
    const char* dir_component = dir_name.data();
    const char* dir_end = dir_component + dir_name.size();
  
    watchman_dir* dir = rootDir_.get();
    dir_component += rootPath_.size() + 1; // Skip root path prefix
  
    w_assert(dir_component <= dir_end, "impossible file name");
  
    watchman_dir* parent;
    while (true) {
      auto sep = (const char*)memchr(dir_component, '/', dir_end - dir_component);
      // Note: if sep is NULL it means that we're looking at the basename
      // component of the input directory name, which is the terminal
      // iteration of this search.
  
      w_string_piece component(
          dir_component, sep ? (sep - dir_component) : (dir_end - dir_component));
  
      auto child = dir->getChildDir(component);
  
      if (!child && !create) {
        return nullptr;
      }
      if (!child && sep && create) {
        // A component in the middle wasn't present.  Since we're in create
        // mode, we know that the leaf must exist.  The assumption is that
        // we have another pending item for the parent.  We'll create the
        // parent dir now and our other machinery will populate its contents
        // later.
        w_string child_name(dir_component, (uint32_t)(sep - dir_component));
  
        // Careful! dir->dirs is keyed by non-owning string pieces so the
        // child_name MUST be stored or otherwise kept alive by the watchman_dir
        // instance constructed below!
        auto& new_child = dir->dirs[child_name];
        new_child.reset(new watchman_dir(child_name, dir));
  
        child = new_child.get();
      }
  
      parent = dir;
      dir = child;
  
      if (!sep) {
        // We reached the end of the string
        if (dir) {
          // We found the dir
          return dir;
        }
        // We need to create the dir
        break;
      }
  
      // Skip to the next component for the next iteration
      dir_component = sep + 1;
    }
  
    w_string child_name(dir_component, (uint32_t)(dir_end - dir_component));
    // Careful! parent->dirs is keyed by non-owning string pieces so the
    // child_name MUST be stored or otherwise kept alive by the watchman_dir
    // instance constructed below!
    auto& new_child = parent->dirs[child_name];
    new_child.reset(new watchman_dir(child_name, parent));
    return new_child.get();
  }
  
  const watchman_dir* ViewDatabase::resolveDir(const w_string& dir_name) const {
    if (dir_name == rootPath_) {
      return rootDir_.get();
    }
  
    const char* dir_component = dir_name.data();
    const char* dir_end = dir_component + dir_name.size();
  
    watchman_dir* dir = rootDir_.get();
    dir_component += rootPath_.size() + 1; // Skip root path prefix
  
    w_assert(dir_component <= dir_end, "impossible file name");
  
    while (true) {
      auto sep = (const char*)memchr(dir_component, '/', dir_end - dir_component);
      // Note: if sep is NULL it means that we're looking at the basename
      // component of the input directory name, which is the terminal
      // iteration of this search.
  
      w_string_piece component(
          dir_component, sep ? (sep - dir_component) : (dir_end - dir_component));
  
      auto child = dir->getChildDir(component);
      if (!child) {
        return nullptr;
      }
  
      dir = child;
  
      if (!sep) {
        // We reached the end of the string
        if (dir) {
          // We found the dir
          return dir;
        }
        // Does not exist
        return nullptr;
      }
  
      // Skip to the next component for the next iteration
      dir_component = sep + 1;
    }
  
    return nullptr;
  }
  
  watchman_file* ViewDatabase::getOrCreateChildFile(
      Watcher& watcher,
      watchman_dir* dir,
      const w_string& file_name,
      ClockStamp ctime) {
    // file_name is typically a baseName slice; let's use it as-is
    // to look up a child...
    auto it = dir->files.find(file_name);
    if (it != dir->files.end()) {
      return it->second.get();
    }
  
    // ... but take the shorter string from inside the file that
    // we create as the key.
    auto file = watchman_file::make(file_name, dir);
    auto& file_ptr = dir->files[file->getName()];
    file_ptr = std::move(file);
  
    file_ptr->ctime = ctime;
  
    watcher.startWatchFile(file_ptr.get());
  
    return file_ptr.get();
  }
  
  void ViewDatabase::markFileChanged(
      Watcher& watcher,
      watchman_file* file,
      ClockStamp otime) {
    if (file->exists) {
      watcher.startWatchFile(file);
    }
  
    file->otime = otime;
  
    if (latestFile_ != file) {
      // unlink from list
      file->removeFromFileList();
  
      // and move to the head
      insertAtHeadOfFileList(file);
    }
  }
  
  void ViewDatabase::markDirDeleted(
      Watcher& watcher,
      watchman_dir* dir,
      ClockStamp otime,
      bool recursive) {
    if (!dir->last_check_existed) {
      // If we know that it doesn't exist, return early
      return;
    }
    dir->last_check_existed = false;
  
    for (auto& it : dir->files) {
      auto file = it.second.get();
  
      if (file->exists) {
        auto full_name = dir->getFullPathToChild(file->getName());
        logf(DBG, "mark_deleted: {}\n", full_name);
        file->exists = false;
        markFileChanged(watcher, file, otime);
      }
    }
  
    if (recursive) {
      for (auto& it : dir->dirs) {
        auto child = it.second.get();
  
        markDirDeleted(watcher, child, otime, true);
      }
    }
  }
  
  void ViewDatabase::insertAtHeadOfFileList(struct watchman_file* file) {
    file->next = latestFile_;
    if (file->next) {
      file->next->prev = &file->next;
    }
    latestFile_ = file;
    file->prev = &latestFile_;
  }
  
  InMemoryView::PendingChangeLogEntry::PendingChangeLogEntry(
      const PendingChange& pc,
      std::error_code errcode,
      const FileInformation& st) noexcept {
    this->now = pc.now;
    this->pending_flags = pc.flags.asRaw();
    storeTruncatedTail(this->path_tail, pc.path);
  
    this->errcode = errcode.value();
    this->mode = st.mode;
    this->size = st.size;
    this->mtime = st.mtime.tv_sec;
  }
  
  json_ref InMemoryView::PendingChangeLogEntry::asJsonValue() const {
    return json_object({
        {"now", json_integer(now.time_since_epoch().count())},
        {"pending_flags",
         typed_string_to_json(PendingFlags::raw(pending_flags).format())},
        {"path",
         w_string_to_json(w_string{path_tail, strnlen(path_tail, kPathLength)})},
        {"errcode", json_integer(errcode)},
        {"mode", json_integer(mode)},
        {"size", json_integer(size)},
        {"mtime", json_integer(mtime)},
    });
  }
  
  InMemoryView::InMemoryView(
      FileSystem& fileSystem,
      const w_string& root_path,
      Configuration config,
      std::shared_ptr<Watcher> watcher)
      : QueryableView{root_path, /*requiresCrawl=*/true},
        fileSystem_{fileSystem},
        config_(std::move(config)),
        view_(folly::in_place, root_path),
        rootNumber_(next_root_number++),
        rootPath_(root_path),
        watcher_(std::move(watcher)),
        caches_(
            root_path,
            config_.getInt("content_hash_max_items", 128 * 1024),
            config_.getInt("symlink_target_max_items", 32 * 1024),
            std::chrono::milliseconds(
                config_.getInt("content_hash_negative_cache_ttl_ms", 2000))),
        enableContentCacheWarming_(
            config_.getBool("content_hash_warming", false)),
        maxFilesToWarmInContentCache_(
            size_t(config_.getInt("content_hash_max_warm_per_settle", 1024))),
        syncContentCacheWarming_(
            config_.getBool("content_hash_warm_wait_before_settle", false)) {
    json_int_t in_memory_view_ring_log_size =
        config_.getInt("in_memory_view_ring_log_size", 0);
    if (in_memory_view_ring_log_size) {
      this->processedPaths_ = std::make_unique<RingBuffer<PendingChangeLogEntry>>(
          in_memory_view_ring_log_size);
    }
  }
  
  InMemoryView::~InMemoryView() = default;
  
  ClockStamp InMemoryView::ageOutFile(
      std::unordered_set<w_string>& dirs_to_erase,
      watchman_file* file) {
    auto parent = file->parent;
  
    auto full_name = parent->getFullPathToChild(file->getName());
    logf(DBG, "age_out file={}\n", full_name);
  
    auto ageOutOtime = file->otime;
  
    // If we have a corresponding dir, we want to arrange to remove it, but only
    // after we have unlinked all of the associated file nodes.
    dirs_to_erase.insert(full_name);
  
    // Remove the entry from the containing file hash; this will free it.
    // We don't need to stop watching it, because we already stopped watching it
    // when we marked it as !exists.
    parent->files.erase(file->getName());
  
    return ageOutOtime;
  }
  
  void InMemoryView::ageOut(PerfSample& sample, std::chrono::seconds minAge) {
    uint32_t num_aged_files = 0;
    uint32_t num_walked = 0;
    std::unordered_set<w_string> dirs_to_erase;
  
    auto now = std::chrono::system_clock::now();
    lastAgeOutTimestamp_ = now;
    auto view = view_.wlock();
  
    watchman_file* file = view->getLatestFile();
    watchman_file* prior = nullptr;
    while (file) {
      ++num_walked;
      if (file->exists ||
          std::chrono::system_clock::from_time_t(file->otime.timestamp) + minAge >
              now) {
        prior = file;
        file = file->next;
        continue;
      }
  
      auto agedOtime = ageOutFile(dirs_to_erase, file);
  
      // Revise tick for fresh instance reporting
      lastAgeOutTick_ = std::max(lastAgeOutTick_, agedOtime.ticks);
  
      num_aged_files++;
  
      // Go back to last good file node; we can't trust that the
      // value of file->next saved before age_out_file is a valid
      // file node as anything past that point may have also been
      // aged out along with it.
      file = prior;
    }
  
    for (auto& name : dirs_to_erase) {
      auto parent = view->resolveDir(name.dirName(), false);
      if (parent) {
        parent->dirs.erase(name.baseName());
      }
    }
  
    if (num_aged_files + dirs_to_erase.size()) {
      logf(ERR, "aged {} files, {} dirs\n", num_aged_files, dirs_to_erase.size());
    }
    sample.add_meta(
        "age_out",
        json_object(
            {{"walked", json_integer(num_walked)},
             {"files", json_integer(num_aged_files)},
             {"dirs", json_integer(dirs_to_erase.size())}}));
  }
  
  void InMemoryView::timeGenerator(const Query* query, QueryContext* ctx) const {
    // Walk back in time until we hit the boundary
    auto view = view_.rlock();
    ctx->generationStarted();
  
    for (watchman_file* f = view->getLatestFile(); f; f = f->next) {
      ctx->bumpNumWalked();
      // Note that we use <= for the time comparisons in here so that we
      // report the things that changed inclusive of the boundary presented.
      // This is especially important for clients using the coarse unix
      // timestamp as the since basis, as they would be much more
      // likely to miss out on changes if we didn't.
      if (auto* since_ts = std::get_if<QuerySince::Timestamp>(&ctx->since.since);
          since_ts && f->otime.timestamp <= since_ts->time) {
        break;
      }
      if (auto* since_clock = std::get_if<QuerySince::Clock>(&ctx->since.since);
          since_clock && f->otime.ticks <= since_clock->ticks) {
        break;
      }
  
      if (!ctx->fileMatchesRelativeRoot(f)) {
        continue;
      }
  
      w_query_process_file(
          query, ctx, std::make_unique<InMemoryFileResult>(f, caches_));
    }
  }
  
  void InMemoryView::pathGenerator(const Query* query, QueryContext* ctx) const {
    w_string_t* relative_root;
    struct watchman_file* f;
  
    if (query->relative_root) {
      relative_root = query->relative_root;
    } else {
      relative_root = rootPath_;
    }
  
    auto view = view_.rlock();
    ctx->generationStarted();
  
    for (const auto& path : *query->paths) {
      const watchman_dir* dir;
      w_string dir_name;
  
      // Compose path with root
      auto full_name = w_string::pathCat({relative_root, path.name});
  
      // special case of root dir itself
      if (w_string_equal(rootPath_, full_name)) {
        // dirname on the root is outside the root, which is useless
        dir = view->resolveDir(full_name);
        goto is_dir;
      }
  
      // Ideally, we'd just resolve it directly as a dir and be done.
      // It's not quite so simple though, because we may resolve a dir
      // that had been deleted and replaced by a file.
      // We prefer to resolve the parent and walk down.
      dir_name = full_name.dirName();
      if (!dir_name) {
        continue;
      }
  
      dir = view->resolveDir(dir_name);
  
      if (!dir) {
        // Doesn't exist, and never has
        continue;
      }
  
      if (!dir->files.empty()) {
        auto file_name = path.name.baseName();
        f = dir->getChildFile(file_name);
  
        // If it's a file (but not an existent dir)
        if (f && (!f->exists || !f->stat.isDir())) {
          ctx->bumpNumWalked();
          w_query_process_file(
              query, ctx, std::make_unique<InMemoryFileResult>(f, caches_));
          continue;
        }
      }
  
      // Is it a dir?
      if (dir->dirs.empty()) {
        continue;
      }
  
      dir = dir->getChildDir(full_name.baseName());
    is_dir:
      // We got a dir; process recursively to specified depth
      if (dir) {
        dirGenerator(query, ctx, dir, path.depth);
      }
    }
  }
  
  void InMemoryView::dirGenerator(
      const Query* query,
      QueryContext* ctx,
      const watchman_dir* dir,
      uint32_t depth) const {
    for (auto& it : dir->files) {
      auto file = it.second.get();
      ctx->bumpNumWalked();
  
      w_query_process_file(
          query, ctx, std::make_unique<InMemoryFileResult>(file, caches_));
    }
  
    if (depth > 0) {
      for (auto& it : dir->dirs) {
        const auto child = it.second.get();
  
        dirGenerator(query, ctx, child, depth - 1);
      }
    }
  }
  
  /** This is our specialized handler for the ** recursive glob pattern.
   * This is the unhappy path because we have no choice but to recursively
   * walk the tree; we have no way to prune portions that won't match.
   * We do coalesce recursive matches together that might generate multiple
   * results.
   * For example: */
  // globs: ["foo/**/*.h", "foo/**/**/*.h"]
  /* effectively runs the same query multiple times.  By combining the
   * doublestar walk for both into a single walk, we can then match each
   * file against the list of patterns, terminating that match as soon
   * as any one of them matches the file node.
   */
  void InMemoryView::globGeneratorDoublestar(
      QueryContext* ctx,
      const struct watchman_dir* dir,
      const GlobTree* node,
      const char* dir_name,
      uint32_t dir_name_len) const {
    bool matched;
  
    // First step is to walk the set of files contained in this node
    for (auto& it : dir->files) {
      auto file = it.second.get();
      auto file_name = file->getName();
  
      ctx->bumpNumWalked();
  
      if (!file->exists) {
        // Globs can only match files that exist
        continue;
      }
  
      auto subject = make_path_name(
          dir_name, dir_name_len, file_name.data(), file_name.size());
  
      // Now that we have computed the name of this candidate file node,
      // attempt to match against each of the possible doublestar patterns
      // in turn.  As soon as any one of them matches we can stop this loop
      // as it doesn't make a lot of sense to yield multiple results for
      // the same file.
      for (const auto& child_node : node->doublestar_children) {
        matched =
            wildmatch(
                child_node->pattern.c_str(),
                subject.c_str(),
                ctx->query->glob_flags | WM_PATHNAME |
                    (ctx->query->case_sensitive == CaseSensitivity::CaseSensitive
                         ? 0
                         : WM_CASEFOLD),
                0) == WM_MATCH;
  
        if (matched) {
          w_query_process_file(
              ctx->query,
              ctx,
              std::make_unique<InMemoryFileResult>(file, caches_));
          // No sense running multiple matches for this same file node
          // if this one succeeded.
          break;
        }
      }
    }
  
    // And now walk down to any dirs; all dirs are eligible
    for (auto& it : dir->dirs) {
      const auto child = it.second.get();
  
      if (!child->last_check_existed) {
        // Globs can only match files in dirs that exist
        continue;
      }
  
      auto subject = make_path_name(
          dir_name, dir_name_len, child->name.data(), child->name.size());
      globGeneratorDoublestar(ctx, child, node, subject.data(), subject.size());
    }
  }
  
  /* Match each child of node against the children of dir */
  void InMemoryView::globGeneratorTree(
      QueryContext* ctx,
      const GlobTree* node,
      const struct watchman_dir* dir) const {
    if (!node->doublestar_children.empty()) {
      globGeneratorDoublestar(ctx, dir, node, nullptr, 0);
    }
  
    for (const auto& child_node : node->children) {
      w_assert(!child_node->is_doublestar, "should not get here with ** glob");
  
      // If there are child dirs, consider them for recursion.
      // Note that we don't restrict this to !leaf because the user may have
      // set their globs list to something like ["some_dir", "some_dir/file"]
      // and we don't want to preclude matching the latter.
      if (!dir->dirs.empty()) {
        // Attempt direct lookup if possible
        if (!child_node->had_specials &&
            ctx->query->case_sensitive == CaseSensitivity::CaseSensitive) {
          w_string_piece component(
              child_node->pattern.data(), child_node->pattern.size());
          const auto child_dir = dir->getChildDir(component);
  
          if (child_dir) {
            globGeneratorTree(ctx, child_node.get(), child_dir);
          }
        } else {
          // Otherwise we have to walk and match
          for (auto& it : dir->dirs) {
            const auto child_dir = it.second.get();
  
            if (!child_dir->last_check_existed) {
              // Globs can only match files in dirs that exist
              continue;
            }
  
            if (wildmatch(
                    child_node->pattern.c_str(),
                    child_dir->name.c_str(),
                    ctx->query->glob_flags |
                        (ctx->query->case_sensitive ==
                                 CaseSensitivity::CaseSensitive
                             ? 0
                             : WM_CASEFOLD),
                    0) == WM_MATCH) {
              globGeneratorTree(ctx, child_node.get(), child_dir);
            }
          }
        }
      }
  
      // If the node is a leaf we are in a position to match files.
      if (child_node->is_leaf && !dir->files.empty()) {
        // Attempt direct lookup if possible
        if (!child_node->had_specials &&
            ctx->query->case_sensitive == CaseSensitivity::CaseSensitive) {
          w_string_piece component(
              child_node->pattern.data(), child_node->pattern.size());
          auto file = dir->getChildFile(component);
  
          if (file) {
            ctx->bumpNumWalked();
            if (file->exists) {
              // Globs can only match files that exist
              w_query_process_file(
                  ctx->query,
                  ctx,
                  std::make_unique<InMemoryFileResult>(file, caches_));
            }
          }
        } else {
          for (auto& it : dir->files) {
            // Otherwise we have to walk and match
            auto file = it.second.get();
            auto file_name = file->getName();
            ctx->bumpNumWalked();
  
            if (!file->exists) {
              // Globs can only match files that exist
              continue;
            }
  
            if (wildmatch(
                    child_node->pattern.c_str(),
                    file_name.data(),
                    ctx->query->glob_flags |
                        (ctx->query->case_sensitive ==
                                 CaseSensitivity::CaseSensitive
                             ? 0
                             : WM_CASEFOLD),
                    0) == WM_MATCH) {
              w_query_process_file(
                  ctx->query,
                  ctx,
                  std::make_unique<InMemoryFileResult>(file, caches_));
            }
          }
        }
      }
    }
  }
  
  void InMemoryView::globGenerator(const Query* query, QueryContext* ctx) const {
    w_string relative_root;
  
    if (query->relative_root) {
      relative_root = query->relative_root;
    } else {
      relative_root = rootPath_;
    }
  
    auto view = view_.rlock();
  
    const auto dir = view->resolveDir(relative_root);
    if (!dir) {
      throw QueryExecError(folly::to<std::string>(
          "glob_generator could not resolve ",
          relative_root.view(),
          ", check your "
          "relative_root parameter!"));
    }
  
    globGeneratorTree(ctx, query->glob_tree.get(), dir);
  }
  
  void InMemoryView::allFilesGenerator(const Query* query, QueryContext* ctx)
      const {
    struct watchman_file* f;
    auto view = view_.rlock();
    ctx->generationStarted();
  
    for (f = view->getLatestFile(); f; f = f->next) {
      ctx->bumpNumWalked();
      if (!ctx->fileMatchesRelativeRoot(f)) {
        continue;
      }
  
      w_query_process_file(
          query, ctx, std::make_unique<InMemoryFileResult>(f, caches_));
    }
  }
  
  ClockPosition InMemoryView::getMostRecentRootNumberAndTickValue() const {
    return ClockPosition(rootNumber_, mostRecentTick_);
  }
  
  w_string InMemoryView::getCurrentClockString() const {
    char clockbuf[128];
    if (!clock_id_string(
            rootNumber_, mostRecentTick_, clockbuf, sizeof(clockbuf))) {
      throw std::runtime_error("clock string exceeded clockbuf size");
    }
    return w_string(clockbuf, W_STRING_UNICODE);
  }
  
  uint32_t InMemoryView::getLastAgeOutTickValue() const {
    return lastAgeOutTick_;
  }
  
  std::chrono::system_clock::time_point InMemoryView::getLastAgeOutTimeStamp()
      const {
    return lastAgeOutTimestamp_;
  }
  
  void InMemoryView::startThreads(const std::shared_ptr<Root>& root) {
    // Start a thread to call into the watcher API for filesystem notifications
    auto self = std::static_pointer_cast<InMemoryView>(shared_from_this());
    logf(DBG, "starting threads for {} {}\n", fmt::ptr(this), rootPath_);
    std::thread notifyThreadInstance([self, root]() {
      w_set_thread_name(
          "notify ", uintptr_t(self.get()), " ", self->rootPath_.view());
      try {
        self->notifyThread(root);
      } catch (const std::exception& e) {
        log(ERR, "Exception: ", e.what(), " cancel root\n");
        root->cancel();
      }
      log(DBG, "out of loop\n");
    });
    notifyThreadInstance.detach();
  
    // Wait for it to signal that the watcher has been initialized
    pendingFromWatcher_.lockAndWait(std::chrono::milliseconds(-1) /* infinite */);
  
    // And now start the IO thread
    std::thread ioThreadInstance([self, root]() {
      w_set_thread_name(
          "io ", uintptr_t(self.get()), " ", self->rootPath_.view());
      try {
        self->ioThread(root);
      } catch (const std::exception& e) {
        log(ERR, "Exception: ", e.what(), " cancel root\n");
        root->cancel();
      }
      log(DBG, "out of loop\n");
    });
    ioThreadInstance.detach();
  }
  
  void InMemoryView::stopThreads() {
    logf(DBG, "signalThreads! {} {}\n", fmt::ptr(this), rootPath_);
    stopThreads_.store(true, std::memory_order_release);
    watcher_->stopThreads();
    pendingFromWatcher_.lock()->ping();
  }
  
  void InMemoryView::wakeThreads() {
    pendingFromWatcher_.lock()->ping();
  }
  
  folly::SemiFuture<folly::Unit> InMemoryView::waitForSettle(
      std::chrono::milliseconds settle_period) {
    auto [p, f] = folly::makePromiseContract<folly::Unit>();
    pendingSettles_.withWLock(
        [&, p = std::move(p)](auto& pendingSettles) mutable {
          pendingSettles.insert(std::make_pair(settle_period, std::move(p)));
        });
  
    // iothread might be waiting, so wake it so it sees the new entry in
    // pendingSettles_.
    pendingFromWatcher_.lock()->ping();
  
    return std::move(f);
  }
  
  /* Ensure that we're synchronized with the state of the
   * filesystem at the current time.
   * We do this by touching a cookie file and waiting to
   * observe it via inotify.  When we see it we know that
   * we've seen everything up to the point in time at which
   * we're asking questions.
   * Throws a std::system_error with an ETIMEDOUT error if
   * the timeout expires before we observe the change, or
   * a runtime_error if the root has been deleted or rendered
   * inaccessible. */
  CookieSync::SyncResult InMemoryView::syncToNow(
      const std::shared_ptr<Root>& root,
      std::chrono::milliseconds timeout) {
    auto syncResult = syncToNowCookies(root, timeout);
  
    // Some watcher implementations (notably, FSEvents) reorder change events
    // before they're reported, and cookie files are not sufficient. Instead, the
    // watcher supports direct synchronization. Once a cookie file has been
    // observed, ensure that all pending events have been flushed and wait until
    // the pending event queue is fully crawled.
    auto result = watcher_->flushPendingEvents();
    if (result.valid()) {
      // The watcher has made all pending events available and inserted a promise
      // into its PendingCollection. Wait for InMemoryView to observe it and
      // everything prior.
      //
      // Would be nice to use a deadline rather than a timeout here.
  
      try {
        std::move(result).get(timeout);
      } catch (folly::FutureTimeout&) {
        auto why = folly::to<std::string>(
            "syncToNow: timed out waiting for pending watcher events to be flushed within ",
            timeout.count(),
            " milliseconds");
        log(ERR, why, "\n");
        throw std::system_error(ETIMEDOUT, std::generic_category(), why);
      }
    }
  
    return syncResult;
  }
  
  folly::SemiFuture<CookieSync::SyncResult> InMemoryView::sync(
      const std::shared_ptr<Root>& root) {
    return root->cookies.sync();
  }
  
  CookieSync::SyncResult InMemoryView::syncToNowCookies(
      const std::shared_ptr<Root>& root,
      std::chrono::milliseconds timeout) {
    try {
      return root->cookies.syncToNow(timeout);
    } catch (const std::system_error& exc) {
      auto cookieDirs = root->cookies.cookieDirs();
  
      if (exc.code() == error_code::no_such_file_or_directory ||
          exc.code() == error_code::permission_denied ||
          exc.code() == error_code::not_a_directory) {
        // A key path was removed; this is either the vcs dir (.hg, .git, .svn)
        // or possibly the root of the watch itself.
        if (!(watcher_->flags & WATCHER_HAS_SPLIT_WATCH)) {
          w_assert(
              cookieDirs.size() == 1,
              "Non split watchers cannot have multiple cookie directories");
          if (cookieDirs.count(rootPath_) == 1) {
            // If the root was removed then we need to cancel the watch.
            // We may have already observed the removal via the notifythread,
            // but in some cases (eg: btrfs subvolume deletion) no notification
            // is received.
            root->cancel();
            throw std::runtime_error("root dir was removed or is inaccessible");
          } else {
            // The cookie dir was a VCS subdir and it got deleted.  Let's
            // focus instead on the parent dir and recursively retry.
            root->cookies.setCookieDir(rootPath_);
            return root->cookies.syncToNow(timeout);
          }
        } else {
          // Split watchers have one watch on the root and watches for nested
          // directories, and syncToNow will only throw if no cookies were
          // created, ie: if all the nested watched directories are no longer
          // present and the root directory has been removed.
          root->cancel();
          throw std::runtime_error("root dir was removed or is inaccessible");
        }
      }
  
      // Let's augment the error reason with the current recrawl state,
      // if any.
      {
        auto info = root->recrawlInfo.rlock();
  
        if (!root->inner.done_initial || info->shouldRecrawl) {
          std::string extra = (info->recrawlCount > 0)
              ? folly::to<std::string>(
                    "(re-crawling, count=", info->recrawlCount, ")")
              : "(performing initial crawl)";
  
          throw std::system_error(
              exc.code(), folly::to<std::string>(exc.what(), ". ", extra));
        }
      }
  
      // On BTRFS we're not guaranteed to get notified about all classes
      // of replacement so we make a best effort attempt to do something
      // reasonable.   Let's pretend that we got notified about the cookie
      // dir changing and schedule the IO thread to look at it.
      // If it observes a change it will do the right thing.
      {
        auto now = std::chrono::system_clock::now();
  
        // TODO: pass this PendingCollection in as a parameter
        auto lock = pendingFromWatcher_.lock();
        for (const auto& dir : cookieDirs) {
          lock->add(dir, now, W_PENDING_CRAWL_ONLY);
        }
        lock->ping();
      }
  
      // We didn't have any useful additional contextual information
      // to add so let's just bubble up the exception.
      throw;
    }
  }
  
  bool InMemoryView::doAnyOfTheseFilesExist(
      const std::vector<w_string>& fileNames) const {
    auto view = view_.rlock();
    for (auto& name : fileNames) {
      auto fullName = w_string::pathCat({rootPath_, name});
      const auto dir = view->resolveDir(fullName.dirName());
      if (!dir) {
        continue;
      }
  
      auto file = dir->getChildFile(fullName.baseName());
      if (!file) {
        continue;
      }
      if (file->exists) {
        return true;
      }
    }
    return false;
  }
  
  const w_string& InMemoryView::getName() const {
    return watcher_->name;
  }
  
  const std::shared_ptr<Watcher>& InMemoryView::getWatcher() const {
    return watcher_;
  }
  
  json_ref InMemoryView::getWatcherDebugInfo() const {
    return json_object({
        {"watcher", watcher_->getDebugInfo()},
        {"view", getViewDebugInfo()},
    });
  }
  
  void InMemoryView::clearWatcherDebugInfo() {
    watcher_->clearDebugInfo();
    clearViewDebugInfo();
  }
  
  json_ref InMemoryView::getViewDebugInfo() const {
    auto processedPathsResult = json_null();
    if (processedPaths_) {
      std::vector<json_ref> paths;
      for (auto& entry : processedPaths_->readAll()) {
        paths.push_back(entry.asJsonValue());
      }
      processedPathsResult = json_array(std::move(paths));
    }
    return json_object({
        {"processed_paths", processedPathsResult},
    });
  }
  
  void InMemoryView::clearViewDebugInfo() {
    if (processedPaths_) {
      processedPaths_->clear();
    }
  }
  
  void InMemoryView::warmContentCache() {
    if (!enableContentCacheWarming_) {
      return;
    }
  
    log(DBG, "considering files for content hash cache warming\n");
  
    size_t n = 0;
    std::deque<folly::Future<std::shared_ptr<const ContentHashCache::Node>>>
        futures;
  
    {
      // Walk back in time until we hit the boundary, or hit the limit
      // on the number of files we should warm up.
      auto view = view_.rlock();
      struct watchman_file* f;
      for (f = view->getLatestFile(); f && n < maxFilesToWarmInContentCache_;
           f = f->next) {
        if (f->otime.ticks <= lastWarmedTick_) {
          log(DBG,
              "warmContentCache: stop because file ticks ",
              f->otime.ticks,
              " is <= lastWarmedTick_ ",
              lastWarmedTick_,
              "\n");
          break;
        }
  
        if (f->exists && f->stat.isFile()) {
          // Note: we could also add an expression to further constrain
          // the things we warm up here.  Let's see if we need it before
          // going ahead and adding.
  
          auto dirStr = f->parent->getFullPath();
          w_string_piece dir(dirStr);
          dir.advance(caches_.contentHashCache.rootPath().size());
  
          // If dirName is the root, dir.size() will now be zero
          if (dir.size() > 0) {
            // if not at the root, skip the slash character at the
            // front of dir
            dir.advance(1);
          }
          ContentHashCacheKey key{
              w_string::pathCat({dir, f->getName()}),
              size_t(f->stat.size),
              f->stat.mtime};
  
          log(DBG, "warmContentCache: lookup ", key.relativePath, "\n");
          auto f = caches_.contentHashCache.get(key);
          if (syncContentCacheWarming_) {
            futures.emplace_back(std::move(f));
          }
          ++n;
        }
      }
  
      lastWarmedTick_ = mostRecentTick_;
    }
  
    log(DBG,
        "warmContentCache, lastWarmedTick_ now ",
        lastWarmedTick_,
        " scheduled ",
        n,
        " files for hashing, will wait for ",
        futures.size(),
        " lookups to finish\n");
  
    if (syncContentCacheWarming_) {
      // Wait for them to finish, but don't use get() because we don't
      // care about any errors that may have occurred.
      folly::collectAll(futures.begin(), futures.end()).wait();
      log(DBG, "warmContentCache: hashing complete\n");
    }
  }
  
  } // namespace watchman
  