[lldb] Introduce the FileSpecBuilder abstraction

[bulbazord]

Summary

Mutating a FileSpec is quite expensive. Every time you add or remove a
component of a path, we need to re-parse the entire path and insert a
new directory and filename into the ConstString StringPool. In many
cases, we take an existing FilePath and slowly morph it into the one we
want to actually use.

In order to improve performance, I want to introduce a new abstraction
called the FileSpecBuilder. The idea is that it maintains a
SmallString to store the entire path and a path style. It uses llvm's
path manipulation code to quickly append and remove things so we don't
have to re-parse the path every single time. When you're done
manipulating paths and want a FileSpec for sure, you can invoke
FileSpecBuilder::CreateFileSpec to create a new FileSpec, only parsing
the path once.

This patch primarily is to gather feedback about the idea. I wanted to
keep this patch small and targeted to get specific feedback, and for
that reason I avoided doing any kind of refactoring as most changes will
be quite invasive. Instead I opted to add unit tests to show how I want
FileSpecBuilder to be used in code. If this abstraction goes into LLDB,
I will refactor every place where we mutate a FileSpec until
FileSpecBuilder is the default way of manipulating paths.

For further motivation of this change, please see:
https://reviews.llvm.org/D149096

[jingham]

Why did you choose to have a separate FileSpecBuilder class, rather than making FileSpec smarter about the structure of the path (e.g. have an array of StringRef's into the paths for each component.) We could do the parse once the first time a path element was requested, and then operations like "RemovePathComponent" would be trivial. We could maybe even get rid of the distinction between "path" and "filename" since "filename" is really just "last path component".

[bulbazord]

In D151765#4385711, @jingham wrote:

Why did you choose to have a separate FileSpecBuilder class, rather than making FileSpec smarter about the structure of the path (e.g. have an array of StringRef's into the paths for each component.) We could do the parse once the first time a path element was requested, and then operations like "RemovePathComponent" would be trivial. We could maybe even get rid of the distinction between "path" and "filename" since "filename" is really just "last path component".

You mean have FileSpec replace its ConstString m_directory and ConstString m_filename fields with llvm::SmallString m_path or std::string m_path? That would indeed avoid something like FileSpecBuilder (and probably be simpler in the end). As long as the API of FileSpec stays the same, the changes to call sites should be minimal. The thing I'm mostly concerned about is lifetimes... How often do we grab a ConstString from a FileSpec and not think about the lifetime? Hopefully not many places.

I'll try this out and see what the fallout is. If it's the better way to go, then I'll just refactor all the places where those assumptions are problematic.

[clayborg]

The idea behind FileSpec containing two ConstStrings, one for the directory and one for he filename is for lookup performance when searching thousands of line tables for a given file and line when setting breakpoints.

Currently we pass in a FileSpec + line number and we expect fast searching. This is currently done by asking each CompileUnit to find a matching file in its support files array and to return a matching index. If just the filename is filled in, then we compare the just the ConstString for m_filename which is really quick for ConstString values. Then we compare all or part of the m_directory if the path is a full path or if it is relative. But at least the filename comparison is very fast. If we get a valid index back, then we know to search the compile unit's full line table for any matching entries by looking for any line entries with a matching file index. IF the file index is invalid, we don't materialize the line table at all for a compile unit.

Maybe we want the notion of a "FileSpec" (which could contain a llvm::Vector class) and a ConstFileSpec (which would contain two ConstString objects like FileSpec currently has). And we make anyone that needs quick searching, like the support files for a compile unit, use the new ConstFileSpec class.

If you change anything in the FileSpec class, please test setting breakpoints with a really large codebase to ensure we don't regress performance.

If we go the FileSpecBuilder route, we probably want to remove all FileSpec path modification methods and force people to use this class by converting a FileSpec to a FileSpecBuilder, manipulating the path with the FileSpecBuilder calls, and then extracting the FileSpec object from the FileSpecBuilder at the end.

lldb/include/lldb/Utility/FileSpecBuilder.h

+//===-- FileSpecBuilder.h ---------------------------------------*- 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 LLDB_UTILITY_FILESPECBUILDER_H
+#define LLDB_UTILITY_FILESPECBUILDER_H
+
+#include "lldb/Utility/FileSpec.h"
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Path.h"
+
+namespace lldb_private {
+
+/// \class FileSpecBuilder FileSpecBuilder.h "lldb/Utility/FileSpecBuilder.h"
+/// A utility for quickly building FileSpec objects
+///
+/// A class for quickly building FileSpec objects. FileSpec is a useful
+/// abstraction but mutating them can be an expensive operation. FileSpecBuilder
+/// is meant to be an abstraction for quickly creating a FileSpec object by
+/// mutating an existing FileSpec object.
+class FileSpecBuilder {
+public:
+  using Style = llvm::sys::path::Style;
+
+  /// Empty constructors
+  ///
+  /// Creates an FileSpecBuilder where the path is empty. The path style will
+  /// default to the host system's native path style.
+  FileSpecBuilder();
+
+  /// Constructor with path.
+  ///
+  /// Takes a path to a file. This can be a full path or just the filename.
+  ///
+  /// \param[in] path
+  ///     The full or partial path to a file.
+  ///
+  /// \param[in] style
+  ///     The style of the path
+  explicit FileSpecBuilder(const llvm::StringRef path,
+                           const Style style = Style::native);
+
+  /// Constructor with FileSpec.
+  ///
+  /// Takes an existing FileSpec and uses the path from the FileSpec.
+  ///
+  /// \param[in] fspec
+  ///   An existing FileSpec object.
+  explicit FileSpecBuilder(const FileSpec &fspec);
+
+  /// Returns the existing FileSpecBuilder's path.
+  ///
+  /// \return
+  ///   A StringRef to the FileSpecBuilder's current path
+  const llvm::StringRef GetCurrentPath() const;
+
+  /// Appends a new path component to the end of this FileSpecBuilder.
+  ///
+  /// \param[in] component
+  ///   A StringRef referring to the component.
+  void AppendPathComponent(const llvm::StringRef component);
+
+  /// Removes the last path component in the path.
+  ///
+  /// If there is only one component in the path, this will not change the path.
+  ///
+  /// \return
+  ///     A boolean value indicating whether the path was updated.
+  bool RemoveLastPathComponent();
+
+  /// Creates a FileSpec from this FileSpecBuilder.
+  ///
+  /// \return
+  ///   A FileSpec object using the path from this FileSpecBuilder.
+  FileSpec CreateFileSpec();
+
+protected:
+  llvm::SmallString<128> m_path;
+  Style m_style; ///< The syntax that this path uses (e.g. Windows / Posix)
+};
+
+} // namespace lldb_private
+
+#endif // LLDB_UTILITY_FILESPECBUILDER_H

lldb/source/Utility/CMakeLists.txt

add_lldb_library(lldbUtility NO_INTERNAL_DEPENDENCIES
   DataBufferHeap.cpp
   DataBufferLLVM.cpp
   DataEncoder.cpp
   DataExtractor.cpp
   Diagnostics.cpp
   Environment.cpp
   Event.cpp
   FileSpec.cpp
+  FileSpecBuilder.cpp
   FileSpecList.cpp
   GDBRemote.cpp
   IOObject.cpp
   LLDBAssert.cpp
   LLDBLog.cpp
   Listener.cpp
   Log.cpp
   NameMatches.cpp

lldb/source/Utility/FileSpecBuilder.cpp

+//===-- FileSpecBuilder.cpp -----------------------------------------------===//
+//
+// 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 "lldb/Utility/FileSpecBuilder.h"
+
+#include "lldb/Utility/FileSpec.h"
+
+#include "llvm/ADT/StringRef.h"
+
+using namespace lldb_private;
+
+FileSpecBuilder::FileSpecBuilder() : m_path(), m_style(Style::native) {}
+
+FileSpecBuilder::FileSpecBuilder(const llvm::StringRef path, const Style style)
+    : m_path(path), m_style(style) {}
+
+FileSpecBuilder::FileSpecBuilder(const FileSpec &fspec)
+    : m_path(fspec.GetPath()), m_style(fspec.GetPathStyle()) {}
+
+const llvm::StringRef FileSpecBuilder::GetCurrentPath() const { return m_path; }
+
+void FileSpecBuilder::AppendPathComponent(const llvm::StringRef component) {
+  llvm::sys::path::append(m_path, m_style, component);
+}
+
+bool FileSpecBuilder::RemoveLastPathComponent() {
+  if (!llvm::sys::path::has_parent_path(m_path, m_style))
+    return false;
+
+  llvm::sys::path::remove_filename(m_path, m_style);
+  return true;
+}
+
+FileSpec FileSpecBuilder::CreateFileSpec() {
+  return FileSpec(m_path.str(), m_style);
+}

lldb/unittests/Utility/FileSpecBuilderTest.cpp

+//===-- FileSpecBuilderTest.cpp -------------------------------------------===//
+//
+// 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 "gtest/gtest.h"
+
+#include "lldb/Utility/FileSpec.h"
+#include "lldb/Utility/FileSpecBuilder.h"
+
+using namespace lldb_private;
+
+static FileSpec PosixSpec(llvm::StringRef path) {
+  return FileSpec(path, FileSpec::Style::posix);
+}
+
+static FileSpec WindowsSpec(llvm::StringRef path) {
+  return FileSpec(path, FileSpec::Style::windows);
+}
+
+TEST(FileSpecBuilderTest, AppendPathComponent) {
+  FileSpecBuilder from_scratch_posix("/", FileSpecBuilder::Style::posix);
+  EXPECT_EQ("/", from_scratch_posix.GetCurrentPath());
+  from_scratch_posix.AppendPathComponent("foo");
+  EXPECT_EQ("/foo", from_scratch_posix.GetCurrentPath());
+  from_scratch_posix.AppendPathComponent("bar");
+  EXPECT_EQ("/foo/bar", from_scratch_posix.GetCurrentPath());
+  from_scratch_posix.AppendPathComponent("baz");
+  EXPECT_EQ("/foo/bar/baz", from_scatch_posix.GetCurrentPath());
+  const FileSpec posix_scratch_result = from_scratch_posix.CreateFileSpec();
+  EXPECT_STREQ("/foo/bar/baz", posix_scratch_result.GetPath().c_str());
+
+  const FileSpec fs_posix = PosixSpec("/foo");
+  FileSpecBuilder builder_posix(fs_posix);
+  builder_posix.AppendPathComponent("bar");
+  EXPECT_EQ("/foo/bar", builder_posix.GetCurrentPath());
+  const FileSpec posix_result = builder_posix.CreateFileSpec();
+  EXPECT_STREQ("/foo/bar", posix_result.GetPath().c_str());
+
+  const FileSpec fs_windows = WindowsSpec("F:\\");
+  FileSpecBuilder builder_windows(fs_windows);
+  builder_windows.AppendPathComponent("bar");
+  EXPECT_EQ("F:\\bar", builder_windows.GetCurrentPath());
+  builder_windows.AppendPathComponent("baz");
+  EXPECT_EQ("F:\\bar\\baz", builder_windows.GetCurrentPath());
+  const FileSpec windows_result = builder_windows.CreateFileSpec();
+  EXPECT_STREQ("F:\\bar\\baz", windows_result.GetPath().c_str());
+}
+
+TEST(FileSpecBuilderTest, RemoveLastPathComponent) {
+  const FileSpec fs_posix = PosixSpec("/foo/bar/baz");
+  FileSpecBuilder builder_posix(fs_posix);
+
+  EXPECT_EQ("/foo/bar/baz", builder_posix.GetCurrentPath());
+  EXPECT_TRUE(fs_posix.RemoveLastPathComponent());
+  EXPECT_EQ("/foo/bar", builder_posix.GetCurrentPath());
+  EXPECT_TRUE(fs_posix.RemoveLastPathComponent());
+  EXPECT_EQ("/foo", builder_posix.GetCurrentPath());
+  EXPECT_TRUE(fs_posix.RemoveLastPathComponent());
+  EXPECT_EQ("/", builder_posix.GetCurrentPath());
+  EXPECT_FALSE(fs_posix.RemoveLastPathComponent());
+  EXPECT_EQ("/", builder_posix.GetCurrentPath());
+
+  const FileSpec fs_posix_relative = PosixSpec("./foo/bar/baz");
+  FileSpecBuilder builder_posix_relative(fs_posix_relative);
+  EXPECT_EQ("foo/bar/baz", builder_posix_relative.GetCurrentPath());
+  EXPECT_TRUE(fs_posix_relative.RemoveLastPathComponent());
+  EXPECT_EQ("foo/bar", builder_posix_relative.GetCurrentPath());
+  EXPECT_TRUE(fs_posix_relative.RemoveLastPathComponent());
+  EXPECT_EQ("foo", builder_posix_relative.GetCurrentPath());
+  EXPECT_FALSE(fs_posix_relative.RemoveLastPathComponent());
+  EXPECT_EQ("foo", builder_posix_relative.GetCurrentPath());
+
+  const FileSpec fs_posix_relative2 = PosixSpec("./");
+  FileSpecBuilder builder_posix_relative2(fs_posix_relative2);
+
+  EXPECT_EQ(".", builder_posix_relative2.GetCurrentPath());
+  EXPECT_FALSE(fs_posix_relative2.RemoveLastPathComponent());
+  EXPECT_EQ(".", builder_posix_relative2.GetCurrentPath());
+  EXPECT_FALSE(fs_posix_relative.RemoveLastPathComponent());
+  EXPECT_EQ(".", builder_posix_relative2.GetCurrentPath());
+
+  const FileSpec fs_windows = WindowsSpec("C:\\foo\\bar\\baz");
+  FileSpecBuilder builder_windows(fs_windows);
+  EXPECT_EQ("C:\\foo\\bar\\baz", builder_windows.GetCurrentPath());
+  EXPECT_TRUE(fs_windows.RemoveLastPathComponent());
+  EXPECT_EQ("C:\\foo\\bar", builder_windows.GetCurrentPath());
+  EXPECT_TRUE(fs_windows.RemoveLastPathComponent());
+  EXPECT_EQ("C:\\foo", builder_windows.GetCurrentPath());
+  EXPECT_TRUE(fs_windows.RemoveLastPathComponent());
+  EXPECT_EQ("C:\\", builder_windows.GetCurrentPath());
+  EXPECT_TRUE(fs_windows.RemoveLastPathComponent());
+  EXPECT_EQ("C:", builder_windows.GetCurrentPath());
+  EXPECT_FALSE(fs_windows.RemoveLastPathComponent());
+  EXPECT_EQ("C:", builder_windows.GetCurrentPath());
+}
+
+TEST(FileSpecBuilderTest, FindDsymNextToExecutable) {
+  const FileSpec exec = PosixSpec("/foo/bar/baz");
+  const llvm::StringRef name = exec.GetFilename();
+
+  FileSpecBuilder builder(exec);
+  builder.RemoveLastPathComponent();
+
+  const std::string dsym_name = name.str() + ".dSYM";
+  builder.AppendPathComponent(dsym_name);
+  builder.AppendPathComponent("Contents");
+  builder.AppendPathComponent("Resources");
+  builder.AppendPathComponent("DWARF");
+  builder.AppendPathComponent(name);
+
+  const FileSpec dsym_file = builder.CreateFileSpec();
+  EXPECT_STREQ("/foo/bar/baz.dSYM/Contents/Resources/DWARF/baz",
+               dsym_file.GetPath().c_str());
+}