[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

"namespace clang"?

36

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

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

40

"Path relative to the root specified by PrefixKind."

41

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

56

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

66

In this context, "\param".

80

Add an assert for uniqueness?

Rename to storeNewPath?

clang/lib/IndexSerialization/PathIndexer.cpp

15

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

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

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

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

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

76

WDYT about using optional instead of a special marker value?

clang/lib/IndexSerialization/PathIndexer.cpp

22

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

[jkorous]

clang/include/clang/IndexSerialization/PathIndexer.h

20

clang::index?

41

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

76

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 ↗

(On Diff #279310)

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 ↗

(On Diff #279310)

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 ↗

(On Diff #279310)

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 ↗

(On Diff #279310)

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

83 ↗

(On Diff #279310)

Please use is_separator instead of comparing to /

[jkorous]

clang/lib/IndexSerialization/SerializablePathCollection.cpp

48 ↗

(On Diff #279310)

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 ↗

(On Diff #279310)

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 ↗

(On Diff #279310)

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

83 ↗

(On Diff #279310)

That's a good point!

[jkorous]

Addressed comments.

[jkorous]

Friendly ping

clang/include/clang/IndexSerialization/PathIndexer.h

+//===--- PathIndexer.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_PATHINDEXER_H
+#define LLVM_CLANG_INDEX_PATHINDEXER_H
+
+#include "clang/Basic/FileManager.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+
+#include <string>
+#include <vector>
+
+/// Represents a special root directory of a filesystem path.
+enum class RootDirKind {
+  Regular = 0,
+  CurrentWorkDir = 1,
+  SysRoot = 2,
+};
+
+/// Represents a single filesystem path backed by a buffer.
+struct BitPathComponent {
+  const size_t Offset;
+  const size_t Size;
+
+  BitPathComponent(size_t Offset, size_t Size) : Offset(Offset), Size(Size) {}
+};
+
+/// Represents a directory path backed by a buffer.
+struct DirBitPath {
+  /// Is this directory in any special root directory?
+  const RootDirKind PrefixKind;
+  /// Relative path to root represented by PrefixKind.
+  const BitPathComponent Dir;
+
+  DirBitPath(RootDirKind Kind, const BitPathComponent &Dir)
+      : PrefixKind(Kind), Dir(Dir) {}
+};
+
+/// Represents a file path backed by a buffer.
+struct FileBitPath : DirBitPath {
+  const BitPathComponent Filename;
+
+  FileBitPath(RootDirKind Kind, const BitPathComponent &Dir,
+              const BitPathComponent &Filename)
+      : DirBitPath(Kind, Dir), Filename(Filename) {}
+};
+
+/// Builds index of unique filesystem paths.
+class PathIndexer {
+  std::string WorkDir;
+  std::string SysrootPath;
+  llvm::SmallString<512> PathsBuf;
+  llvm::StringMap<DirBitPath, llvm::BumpPtrAllocator> Dirs;
+  std::vector<FileBitPath> FileBitPaths;
+  llvm::DenseMap<const clang::FileEntry *, size_t> FileToIndex;
+
+public:
+  /// \p CWD is current working directory.
+  PathIndexer(llvm::StringRef CWD, llvm::StringRef sysrootPath);
+
+  /// \returns buffer with stored paths.
+  llvm::StringRef getPathsBuffer() const { return PathsBuf.str(); }
+
+  /// \returns array of offsets and sizes of stored paths.
+  llvm::ArrayRef<FileBitPath> getBitPaths() const { return FileBitPaths; }
+
+  /// Stores path to \p FE if it hasn't been stored yet.
+  /// \returns index to FileToIndex or -1 if \p FE == nullptr.
+  int tryStoreFilePath(const clang::FileEntry *FE);
+
+  /// 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.
+  size_t storePath(llvm::StringRef Path);
+
+private:
+  /// Stores \p dirStr path if it hasn't been stored yet.
+  DirBitPath tryStoreDirPath(llvm::StringRef dirStr);
+};
+
+#endif // LLVM_CLANG_INDEX_PATHINDEXER_H

clang/lib/CMakeLists.txt

 endif()
 add_subdirectory(Driver)
 add_subdirectory(Serialization)
 add_subdirectory(Frontend)
 add_subdirectory(FrontendTool)
 add_subdirectory(Tooling)
 add_subdirectory(DirectoryWatcher)
 add_subdirectory(Index)
+add_subdirectory(IndexSerialization)
 if(CLANG_ENABLE_STATIC_ANALYZER)
   add_subdirectory(StaticAnalyzer)
 endif()
 add_subdirectory(Format)

clang/lib/IndexSerialization/CMakeLists.txt

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

clang/lib/IndexSerialization/PathIndexer.cpp

+//===--- PathIndexer.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/PathIndexer.h"
+
+using namespace llvm;
+using namespace clang;
+
+PathIndexer::PathIndexer(StringRef workDir, StringRef sysrootPath)
+    : WorkDir(workDir),
+      SysrootPath(sysrootPath == "/" ? sysrootPath = StringRef()
+                                     : sysrootPath) {}
+
+int PathIndexer::tryStoreFilePath(const FileEntry *FE) {
+  if (!FE)
+    return -1;
+  auto Pair = FileToIndex.insert(std::make_pair(FE, FileBitPaths.size()));
+  bool IsNew = Pair.second;
+  size_t Index = Pair.first->getSecond();
+
+  if (IsNew) {
+    StringRef Filename = sys::path::filename(FE->getName());
+    DirBitPath Dir = tryStoreDirPath(sys::path::parent_path(FE->getName()));
+    FileBitPaths.emplace_back(
+        Dir.PrefixKind, Dir.Dir,
+        BitPathComponent(storePath(Filename), Filename.size()));
+  }
+  return Index;
+}
+
+size_t PathIndexer::storePath(StringRef Path) {
+  if (Path.empty())
+    return 0;
+  size_t offset = PathsBuf.size();
+  PathsBuf += Path;
+  return offset;
+}
+
+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());
+}
+
+DirBitPath PathIndexer::tryStoreDirPath(StringRef dirStr) {
+  auto dirIt = Dirs.find(dirStr);
+  if (dirIt != Dirs.end())
+    return dirIt->second;
+
+  RootDirKind Kind = RootDirKind::Regular;
+  if (isPathInDir(SysrootPath, dirStr)) {
+    Kind = RootDirKind::SysRoot;
+    dirStr = dirStr.drop_front(SysrootPath.size());
+    while (!dirStr.empty() && dirStr[0] == '/')
+      dirStr = dirStr.drop_front();
+  } else if (isPathInDir(WorkDir, dirStr)) {
+    Kind = RootDirKind::CurrentWorkDir;
+    dirStr = dirStr.drop_front(WorkDir.size());
+    while (!dirStr.empty() && dirStr[0] == '/')
+      dirStr = dirStr.drop_front();
+  }
+
+  return DirBitPath(Kind, BitPathComponent(storePath(dirStr), dirStr.size()));
+}