[index-while-building] PathIndexer

[jkorous]

Summary

Part of i-w-b upstreaming https://reviews.llvm.org/D64384

This is actually a bit polished PathStorage.

[gribozavr]

I tried my best to provide meaningful comments, however, I can't find users of PathIndexer in https://reviews.llvm.org/D64384, so I don't think I understand this abstraction at all. I would appreciate some big-picture description.

clang/include/clang/IndexSerialization/PathIndexer.h

20 ↗

(On Diff #217551)

"namespace clang"?

36 ↗

(On Diff #217551)

s/Represents// (throughout the patch)

"Represents" is generally a filler word -- of course types represent some concept, they rarely *are* that concept itself, except for concepts that we invent ourselves.

39 ↗

(On Diff #217551)

Would be best to not refer to one concept with two terms -- root and prefix.

40 ↗

(On Diff #217551)

"Path relative to the root specified by PrefixKind."

41 ↗

(On Diff #217551)

Const members in structs are not great because they make structs not act like values -- the assignment operator becomes deleted. (Throughout the patch.)

56 ↗

(On Diff #217551)

Builds => stores, or maintains. It does not walk the filesystem itself.

66 ↗

(On Diff #217551)

In this context, "\param".

80 ↗

(On Diff #217551)

Add an assert for uniqueness?

Rename to storeNewPath?

clang/lib/IndexSerialization/PathIndexer.cpp

15 ↗

(On Diff #217551)

It is OK to shadow member variables with parameters. Shadowing does the right thing in the member initializer list.

[gribozavr]

Oh, it is called PathStorage there. Looking.

[gribozavr]

clang/include/clang/IndexSerialization/PathIndexer.h

34 ↗

(On Diff #217551)

I believe it would be helpful to build a separate class that just does string interning, and let BitPathComponent be a reference to a string in that string pool. That would simplify code in PathIndexer, and separate the concerns of path handling and string storage. PathIndexer would expose a reference to the interned storage through a getter.

54 ↗

(On Diff #217551)

WDYT about moving DirBitPath and FileBitPath to be nested types in PathIndexer? You should be able to also remove "Bit" from their names then.

57 ↗

(On Diff #217551)

SerializablePaths? SerializablePathCollection? OnDiskPathCollection? (like clang/lib/Serialization/MultiOnDiskHashTable.h)

I'm not a fan of using the word "Indexer" for a passive entity.

76 ↗

(On Diff #217551)

WDYT about using optional instead of a special marker value?

clang/lib/IndexSerialization/PathIndexer.cpp

22 ↗

(On Diff #217551)

s/FileBitPaths.size()/FileToIndex.size()/ would probably be more intuitive.

[jkorous]

clang/include/clang/IndexSerialization/PathIndexer.h

20 ↗

(On Diff #217551)

clang::index?

41 ↗

(On Diff #217551)

I don't have a particularly strong opinion but in general I like immutability as an invariant.

76 ↗

(On Diff #217551)

Good point! Originally the -1 convention for both return values and indices being passed as parameters was used throughout the i-w-b. It avoided explicit error handling which allowed code to look simpler but was more difficult to reason about. This seems to be the last surviving specimen.

[jkorous]

Addressed the comments and tried to simplify things by splitting into multiple smaller classes.

[jkorous]

@arphaman can you please take a look at this patch?

[arphaman]

Sure, will do.

[jkorous]

Rebased on recent master + https://reviews.llvm.org/D66854

[jkorous]

Restore the patch. Previous update wasn't meant for this review - I confused the review IDs.

[arphaman]

clang/include/clang/IndexSerialization/SerializablePathCollection.h

32

I feel like StringOffSz isn't very informative. Can this be renamed to something like StringPool::OffsetSize, or maybe StringPool::Index.

clang/lib/IndexSerialization/SerializablePathCollection.cpp

48

Do you think you can use llvm::sys::path::starts_with instead? why is it important to return false when dir is equivalent to rest. Would we be able to store paths a path like /path/to/xyz_ab, when the CWD/Sysroot is /path/to/xyz when we don't have this check?

55

I looked through the uses of tryStoreFilePath in the full patch, and it doesn't seem like the use of try in the name is justified, since it could imply that some form of error could be produced as a result of a call. Can this be named more precisely, perhaps something like getStoreIndexForFile()? Also, uses seem to imply that it's always converted to uint64_t, can we avoid the conversion and return uint64_t here instead?

68

Same name critique, could this be named something like storeDirPath, without the try?

83

Please use is_separator instead of comparing to /

[jkorous]

clang/lib/IndexSerialization/SerializablePathCollection.cpp

48

I'll try to get rid of this. It's only used in tryStoreDirPath(). The logic is probably sound but maybe it could be implemented in a more readable fashion.

55

The semantics of the name are the same as STL containers - say std::map::try_emplace. I'm open to renaming but would like to have a name that conveys the fact that this is actually the method used for gathering the data for serialization.

68

Maybe storeUniqueDirPath or storeNewDirPath? Because we aren't always storing the input.

83

That's a good point!

[jkorous]

Addressed comments.

[jkorous]

Friendly ping

clang/include/clang/IndexSerialization/SerializablePathCollection.h

+//===--- SerializablePathCollection.h -- Index of paths ---------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_INDEX_SerializablePathCollection_H
+#define LLVM_CLANG_INDEX_SerializablePathCollection_H
+
+#include "clang/Basic/FileManager.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace index {
+
+/// Pool of strings
+class StringPool {
+  llvm::SmallString<512> Buffer;
+
+public:
+  struct StringOffSz {
+    std::size_t Offset;
+    std::size_t Size;
+
+    StringOffSz(size_t Offset, size_t Size) : Offset(Offset), Size(Size) {}
+  };
+
+  StringOffSz add(StringRef Str);
+  StringRef getBuffer() const { return Buffer; }
+};
+
+/// Pool of filesystem paths backed by a StringPool
+class PathPool {
+public:
+  /// Special root directory of a filesystem path.
+  enum class RootDirKind {
+    Regular = 0,
+    CurrentWorkDir = 1,
+    SysRoot = 2,
+  };
+
+  struct DirPath {
+    RootDirKind Root;
+    StringPool::StringOffSz Path;
+
+    DirPath(RootDirKind Root, const StringPool::StringOffSz &Path)
+        : Root(Root), Path(Path) {}
+  };
+
+  struct FilePath {
+    DirPath Dir;
+    StringPool::StringOffSz Filename;
+
+    FilePath(const DirPath &Dir, const StringPool::StringOffSz &Filename)
+        : Dir(Dir), Filename(Filename) {}
+  };
+
+  /// \returns index of the newly added file in FilePaths.
+  size_t addFilePath(RootDirKind Root, const StringPool::StringOffSz &Dir,
+                     StringRef Filename);
+
+  /// \returns offset in Paths and size of newly added directory.
+  StringPool::StringOffSz addDirPath(StringRef Dir);
+
+  llvm::ArrayRef<FilePath> getFilePaths() const;
+
+  StringRef getPaths() const;
+
+private:
+  StringPool Paths;
+  std::vector<FilePath> FilePaths;
+};
+
+/// Stores file paths and produces serialization-friendly representation.
+class SerializablePathCollection {
+  std::string WorkDir;
+  std::string SysRoot;
+
+  PathPool Paths;
+  llvm::DenseMap<const clang::FileEntry *, std::size_t> UniqueFiles;
+  llvm::StringMap<PathPool::DirPath, llvm::BumpPtrAllocator> UniqueDirs;
+
+public:
+  const StringPool::StringOffSz WorkDirPath;
+  const StringPool::StringOffSz SysRootPath;
+  const StringPool::StringOffSz OutputFilePath;
+
+  SerializablePathCollection(llvm::StringRef CurrentWorkDir,
+                             llvm::StringRef SysRoot,
+                             llvm::StringRef OutputFile);
+
+  /// \returns buffer containing all the paths.
+  llvm::StringRef getPathsBuffer() const { return Paths.getPaths(); }
+
+  /// \returns file paths (no directories) backed by buffer exposed in
+  /// getPathsBuffer.
+  ArrayRef<PathPool::FilePath> getFilePaths() const {
+    return Paths.getFilePaths();
+  }
+
+  /// Stores path to \p FE if it hasn't been stored yet.
+  /// \returns index to array exposed by getPathsBuffer().
+  size_t tryStoreFilePath(const clang::FileEntry &FE);
+
+private:
+  /// Stores \p Path if it is non-empty.
+  /// Warning: this method doesn't check for uniqueness.
+  /// \returns offset of \p Path value begin in buffer with stored paths.
+  StringPool::StringOffSz storePath(llvm::StringRef Path);
+
+  /// Stores \p dirStr path if it hasn't been stored yet.
+  PathPool::DirPath tryStoreDirPath(llvm::StringRef dirStr);
+};
+
+} // namespace index
+} // namespace clang
+
+#endif // LLVM_CLANG_INDEX_SerializablePathCollection_H

clang/lib/CMakeLists.txt

 add_subdirectory(Tooling)
 add_subdirectory(DirectoryWatcher)
 add_subdirectory(Index)
+add_subdirectory(IndexSerialization)
 if(CLANG_ENABLE_STATIC_ANALYZER)
   add_subdirectory(StaticAnalyzer)
 endif()

clang/lib/IndexSerialization/CMakeLists.txt

+add_clang_library(clangIndexSerialization
+  SerializablePathCollection.cpp
+
+  LINK_LIBS
+  clangBasic
+  )

clang/lib/IndexSerialization/SerializablePathCollection.cpp

+//===--- SerializablePathCollection.cpp -- Index of paths -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/IndexSerialization/SerializablePathCollection.h"
+#include "llvm/Support/Path.h"
+
+using namespace llvm;
+using namespace clang;
+using namespace clang::index;
+
+StringPool::StringOffSz StringPool::add(StringRef Str) {
+  const std::size_t Offset = Buffer.size();
+  Buffer += Str;
+  return StringPool::StringOffSz(Offset, Str.size());
+}
+
+size_t PathPool::addFilePath(RootDirKind Root,
+                             const StringPool::StringOffSz &Dir,
+                             StringRef Filename) {
+  FilePaths.emplace_back(DirPath(Root, Dir), Paths.add(Filename));
+  return FilePaths.size() - 1;
+}
+
+StringPool::StringOffSz PathPool::addDirPath(StringRef Dir) {
+  return Paths.add(Dir);
+}
+
+llvm::ArrayRef<PathPool::FilePath> PathPool::getFilePaths() const {
+  return FilePaths;
+}
+
+StringRef PathPool::getPaths() const { return Paths.getBuffer(); }
+
+SerializablePathCollection::SerializablePathCollection(
+    StringRef CurrentWorkDir, StringRef SysRoot, llvm::StringRef OutputFile)
+    : WorkDir(CurrentWorkDir),
+      SysRoot(llvm::sys::path::parent_path(SysRoot).empty() ? StringRef()
+                                                                : SysRoot),
+      WorkDirPath(Paths.addDirPath(WorkDir)),
+      SysRootPath(Paths.addDirPath(SysRoot)),
+      OutputFilePath(Paths.addDirPath(OutputFile)) {}
+
+static bool isPathInDir(StringRef dir, StringRef path) {
+  if (dir.empty() || !path.startswith(dir))
+    return false;
+  StringRef rest = path.drop_front(dir.size());
+  return !rest.empty() && sys::path::is_separator(rest.front());
+}
+
+size_t SerializablePathCollection::tryStoreFilePath(const FileEntry &FE) {
+  auto FileIt = UniqueFiles.find(&FE);
+  if (FileIt != UniqueFiles.end())
+    return FileIt->second;
+
+  const auto Dir = tryStoreDirPath(sys::path::parent_path(FE.getName()));
+  const auto FileIdx =
+      Paths.addFilePath(Dir.Root, Dir.Path, sys::path::filename(FE.getName()));
+
+  UniqueFiles.try_emplace(&FE, FileIdx);
+  return FileIdx;
+}
+
+PathPool::DirPath SerializablePathCollection::tryStoreDirPath(StringRef Dir) {
+  auto DirIt = UniqueDirs.find(Dir);
+  if (DirIt != UniqueDirs.end())
+    return DirIt->second;
+
+  const std::string OrigDir = Dir.str();
+  PathPool::RootDirKind Root = PathPool::RootDirKind::Regular;
+  if (isPathInDir(SysRoot, Dir)) {
+    Root = PathPool::RootDirKind::SysRoot;
+    Dir = Dir.drop_front(SysRoot.size());
+    while (!Dir.empty() && Dir[0] == '/')
+      Dir = Dir.drop_front();
+  } else if (isPathInDir(WorkDir, Dir)) {
+    Root = PathPool::RootDirKind::CurrentWorkDir;
+    Dir = Dir.drop_front(WorkDir.size());
+    while (!Dir.empty() && Dir[0] == '/')
+      Dir = Dir.drop_front();
+  }
+
+  PathPool::DirPath Result(Root, Paths.addDirPath(Dir));
+  UniqueDirs.try_emplace(OrigDir, Result);
+  return Result;
+}