Improve ".." handling in FileSpec normalization

[labath]

Summary

.. handling for windows path was completely broken because the function was
expecting \ as path separators, but we were passing it normalized file paths,
where these have been replaced by forward slashes. Apart from this, the function
was incorrect for posix paths as well in some corner cases, as well as being
generally hard to follow.

The corner cases were:

• /../bar -> should be same as /bar
• /bar/.. -> should be same as / (slightly dodgy as the former depends on /bar actually existing, but since we're doing it in an abstract way, I think the transformation is reasonable)

I rewrite the function to fix these corner cases and handle windows paths more
correctly. The function should now handle the posix paths (modulo symlinks, but
we cannot really do anything about that without a real filesystem). For windows
paths, there are a couple of corner cases left, mostly to do with drive letter
handling, which cannot be fixed until the rest of the class understands drive
letters better.

[amccarth]

source/Host/common/FileSpec.cpp

550 ↗

(On Diff #76201)

Do we have to worry about an unnecessary single dot in the directory, like /foo/./bar/? Are those handled when the FileSpec is constructed?

576 ↗

(On Diff #76201)

Ah, here we're skipping the unnecessary single dots, but the short-circuit at the top would prevent us from getting here unless the directory also contained a /...

unittests/Host/FileSpecTest.cpp

144 ↗

(On Diff #76201)

How about a test to make sure C:/foo/./bar is the same as C:/foo/bar?

212 ↗

(On Diff #76201)

Here, too, I'd like to see test cases for paths with single dots.

[labath]

Good point about the single dots. I'll add the tests and make sure they work properly.

[labath]

source/Host/common/FileSpec.cpp

550 ↗

(On Diff #76201)

Good catch. The fast path was too optimistic. I've replaced it with a much more conservative one. It can be beefed up, if we find that this is actually a performance problem.

unittests/Host/FileSpecTest.cpp

144 ↗

(On Diff #76201)

I added a bunch more tests with single dots in various places. If you see more interesting corner cases, let me know.

[labath]

Fix handling of single dots and add tests for that.

[labath]

Fix typo in the test

lldb/trunk/include/lldb/Host/FileSpec.h

public:
   ///     must be checked prior to using it.
   //------------------------------------------------------------------
   lldb::DataBufferSP ReadFileContentsAsCString(Error *error_ptr = nullptr);
 
   //------------------------------------------------------------------
   /// Normalize a pathname by collapsing redundant separators and
   /// up-level references.
   //------------------------------------------------------------------
-  void NormalizePath();
-
-  //------------------------------------------------------------------
-  /// Run through the input string, replaying the effect of any ".." and produce
-  /// the resultant path.  The input path is not required to be in the host file
-  /// system
-  /// format, but it is required to be normalized to that system.
-  ///
-  /// @param[in] input
-  ///     The input path to analyze.
-  ///
-  /// @param[out] result
-  ///     The backup-resolved path will be written here.
-  //------------------------------------------------------------------
-  static void RemoveBackupDots(const ConstString &input_const_str,
-                               ConstString &result_const_str);
+  FileSpec GetNormalizedPath() const;
 
   //------------------------------------------------------------------
   /// Change the file specified with a new path.
   ///
   /// Update the contents of this object with a new path. The path will
   /// be split up into a directory and filename and stored as uniqued
   /// string values for quick comparison and efficient memory usage.
   ///

lldb/trunk/source/Host/common/FileSpec.cpp

 
 bool FileSpec::Equal(const FileSpec &a, const FileSpec &b, bool full,
                      bool remove_backups) {
   // case sensitivity of equality test
   const bool case_sensitive = a.IsCaseSensitive() || b.IsCaseSensitive();
 
   if (!full && (a.GetDirectory().IsEmpty() || b.GetDirectory().IsEmpty()))
     return ConstString::Equals(a.m_filename, b.m_filename, case_sensitive);
-  else if (remove_backups == false)
+
+  if (remove_backups == false)
     return a == b;
-  else {
-    if (!ConstString::Equals(a.m_filename, b.m_filename, case_sensitive))
-      return false;
-    if (ConstString::Equals(a.m_directory, b.m_directory, case_sensitive))
-      return true;
-    ConstString a_without_dots;
-    ConstString b_without_dots;
 
-    RemoveBackupDots(a.m_directory, a_without_dots);
-    RemoveBackupDots(b.m_directory, b_without_dots);
-    return ConstString::Equals(a_without_dots, b_without_dots, case_sensitive);
-  }
-}
+  if (a == b)
+    return true;
 
-void FileSpec::NormalizePath() {
-  ConstString normalized_directory;
-  FileSpec::RemoveBackupDots(m_directory, normalized_directory);
-  m_directory = normalized_directory;
+  return Equal(a.GetNormalizedPath(), b.GetNormalizedPath(), full, false);
 }
 
-void FileSpec::RemoveBackupDots(const ConstString &input_const_str,
-                                ConstString &result_const_str) {
-  const char *input = input_const_str.GetCString();
-  result_const_str.Clear();
-  if (!input || input[0] == '\0')
-    return;
-
-  const char win_sep = '\\';
-  const char unix_sep = '/';
-  char found_sep;
-  const char *win_backup = "\\..";
-  const char *unix_backup = "/..";
-
-  bool is_win = false;
-
-  // Determine the platform for the path (win or unix):
-
-  if (input[0] == win_sep)
-    is_win = true;
-  else if (input[0] == unix_sep)
-    is_win = false;
-  else if (input[1] == ':')
-    is_win = true;
-  else if (strchr(input, unix_sep) != nullptr)
-    is_win = false;
-  else if (strchr(input, win_sep) != nullptr)
-    is_win = true;
-  else {
-    // No separators at all, no reason to do any work here.
-    result_const_str = input_const_str;
-    return;
-  }
+FileSpec FileSpec::GetNormalizedPath() const {
+  // Fast path. Do nothing if the path is not interesting.
+  if (!m_directory.GetStringRef().contains(".") &&
+      (m_filename.GetStringRef() != ".." && m_filename.GetStringRef() != "."))
+    return *this;
 
-  llvm::StringRef backup_sep;
-  if (is_win) {
-    found_sep = win_sep;
-    backup_sep = win_backup;
+  llvm::SmallString<64> path, result;
+  const bool normalize = false;
+  GetPath(path, normalize);
+  llvm::StringRef rest(path);
+
+  // We will not go below root dir.
+  size_t root_dir_start = RootDirStart(path, m_syntax);
+  const bool absolute = root_dir_start != llvm::StringRef::npos;
+  if (absolute) {
+    result += rest.take_front(root_dir_start + 1);
+    rest = rest.drop_front(root_dir_start + 1);
   } else {
-    found_sep = unix_sep;
-    backup_sep = unix_backup;
-  }
-
-  llvm::StringRef input_ref(input);
-  llvm::StringRef curpos(input);
-
-  bool had_dots = false;
-  std::string result;
-
-  while (1) {
-    // Start of loop
-    llvm::StringRef before_sep;
-    std::pair<llvm::StringRef, llvm::StringRef> around_sep =
-        curpos.split(backup_sep);
-
-    before_sep = around_sep.first;
-    curpos = around_sep.second;
-
-    if (curpos.empty()) {
-      if (had_dots) {
-        while (before_sep.startswith("//"))
-          before_sep = before_sep.substr(1);
-        if (!before_sep.empty()) {
-          result.append(before_sep.data(), before_sep.size());
-        }
-      }
-      break;
+    if (m_syntax == ePathSyntaxWindows && path.size() > 2 && path[1] == ':') {
+      result += rest.take_front(2);
+      rest = rest.drop_front(2);
     }
-    had_dots = true;
-
-    unsigned num_backups = 1;
-    while (curpos.startswith(backup_sep)) {
-      num_backups++;
-      curpos = curpos.slice(backup_sep.size(), curpos.size());
-    }
 
-    size_t end_pos = before_sep.size();
-    while (num_backups-- > 0) {
-      end_pos = before_sep.rfind(found_sep, end_pos);
-      if (end_pos == llvm::StringRef::npos) {
-        result_const_str = input_const_str;
-        return;
-      }
-    }
-    result.append(before_sep.data(), end_pos);
-  }
+  bool anything_added = false;
+  llvm::SmallVector<llvm::StringRef, 0> components, processed;
+  rest.split(components, '/', -1, false);
+  processed.reserve(components.size());
+  for (auto component : components) {
+    if (component == ".")
+      continue; // Skip these.
+    if (component != "..") {
+      processed.push_back(component);
+      continue; // Regular file name.
+    }
+    if (!processed.empty()) {
+      processed.pop_back();
+      continue; // Dots. Go one level up if we can.
+    }
+    if (absolute)
+      continue; // We're at the top level. Cannot go higher than that. Skip.
+
+    result += component; // We're a relative path. We need to keep these.
+    result += '/';
+    anything_added = true;
+  for (auto component : processed) {
+    result += component;
+    result += '/';
+    anything_added = true;
+  if (anything_added)
+    result.pop_back(); // Pop last '/'.
+  else if (result.empty())
+    result = ".";
 
-  if (had_dots)
-    result_const_str.SetCString(result.c_str());
-  else
-    result_const_str = input_const_str;
-
-  return;
+  return FileSpec(result, false, m_syntax);
 }
 
 //------------------------------------------------------------------
 // Dump the object to the supplied stream. If the object contains
 // a valid directory name, it will be displayed followed by a
 // directory delimiter, and the filename.
 //------------------------------------------------------------------
 void FileSpec::Dump(Stream *s) const {

lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

if (!rpath_paths.empty()) {
         for (const auto &rpath : rpath_paths) {
           std::string path = rpath;
           path += rpath_relative_path;
           // It is OK to resolve this path because we must find a file on
           // disk for us to accept it anyway if it is rpath relative.
           FileSpec file_spec(path, true);
           // Remove any redundant parts of the path (like "../foo") since
           // LC_RPATH values often contain "..".
-          file_spec.NormalizePath();
+          file_spec = file_spec.GetNormalizedPath();
           if (file_spec.Exists() && files.AppendIfUnique(file_spec)) {
             count++;
             break;
           }
         }
       }
     }
   }

lldb/trunk/unittests/Host/FileSpecTest.cpp

TEST(FileSpecTest, EqualSeparator) {
   const bool remove_backup_dots = true;
   const bool match = true;
   Compare(forward, backward, full_match, remove_backup_dots, match);
   Compare(forward, backward, full_match, !remove_backup_dots, match);
   Compare(forward, backward, !full_match, remove_backup_dots, match);
   Compare(forward, backward, !full_match, !remove_backup_dots, match);
 }
 
-#if 0
 TEST(FileSpecTest, EqualDotsWindows) {
   const bool full_match = true;
   const bool remove_backup_dots = true;
   const bool match = true;
   std::pair<const char *, const char *> tests[] = {
       {R"(C:\foo\bar\baz)", R"(C:\foo\foo\..\bar\baz)"},
       {R"(C:\bar\baz)", R"(C:\foo\..\bar\baz)"},
       {R"(C:\bar\baz)", R"(C:/foo/../bar/baz)"},
       {R"(C:/bar/baz)", R"(C:\foo\..\bar\baz)"},
       {R"(C:\bar)", R"(C:\foo\..\bar)"},
+      {R"(C:\foo\bar)", R"(C:\foo\.\bar)"},
   };
 
   for(const auto &test: tests) {
     FileSpec one(test.first, false, FileSpec::ePathSyntaxWindows);
     FileSpec two(test.second, false, FileSpec::ePathSyntaxWindows);
     EXPECT_NE(one, two);
     Compare(one, two, full_match, remove_backup_dots, match);
     Compare(one, two, full_match, !remove_backup_dots, !match);
     Compare(one, two, !full_match, remove_backup_dots, match);
-    Compare(one, two, !full_match, !remove_backup_dots, match);
+    Compare(one, two, !full_match, !remove_backup_dots, !match);
   }
 
 }
-#endif
 
 TEST(FileSpecTest, EqualDotsPosix) {
   const bool full_match = true;
   const bool remove_backup_dots = true;
   const bool match = true;
   std::pair<const char *, const char *> tests[] = {
       {R"(/foo/bar/baz)", R"(/foo/foo/../bar/baz)"},
       {R"(/bar/baz)", R"(/foo/../bar/baz)"},
-//      {R"(/bar)", R"(/foo/../bar)"},
+      {R"(/bar)", R"(/foo/../bar)"},
+      {R"(/foo/bar)", R"(/foo/./bar)"},
   };
 
   for(const auto &test: tests) {
     FileSpec one(test.first, false, FileSpec::ePathSyntaxPosix);
     FileSpec two(test.second, false, FileSpec::ePathSyntaxPosix);
     EXPECT_NE(one, two);
     Compare(one, two, full_match, remove_backup_dots, match);
     Compare(one, two, full_match, !remove_backup_dots, !match);
     Compare(one, two, !full_match, remove_backup_dots, match);
-//    Compare(one, two, !full_match, !remove_backup_dots, match);
+    Compare(one, two, !full_match, !remove_backup_dots, !match);
   }
 
 }
 
-#if 0
 TEST(FileSpecTest, EqualDotsPosixRoot) {
   const bool full_match = true;
   const bool remove_backup_dots = true;
   const bool match = true;
   std::pair<const char *, const char *> tests[] = {
-      {R"(/)", R"(/..)"},
-      {R"(/)", R"(/foo/..)"},
+      {R"(/)", R"(/..)"}, {R"(/)", R"(/.)"}, {R"(/)", R"(/foo/..)"},
   };
 
   for(const auto &test: tests) {
     FileSpec one(test.first, false, FileSpec::ePathSyntaxPosix);
     FileSpec two(test.second, false, FileSpec::ePathSyntaxPosix);
     EXPECT_NE(one, two);
     Compare(one, two, full_match, remove_backup_dots, match);
-    Compare(one, two, !full_match, remove_backup_dots, match);
+    Compare(one, two, full_match, !remove_backup_dots, !match);
+    Compare(one, two, !full_match, remove_backup_dots, !match);
+    Compare(one, two, !full_match, !remove_backup_dots, !match);
+  }
+}
+
+TEST(FileSpecTest, GetNormalizedPath) {
+  std::pair<const char *, const char *> posix_tests[] = {
+      {"/foo/../bar", "/bar"},
+      {"/foo/./bar", "/foo/bar"},
+      {"/foo/..", "/"},
+      {"/foo/.", "/foo"},
+      {"/./foo", "/foo"},
+      {"/", "/"},
+      {"//", "//"},
+      {"//net", "//net"},
+      {"/..", "/"},
+      {"/.", "/"},
+      {"..", ".."},
+      {".", "."},
+      {"../..", "../.."},
+      {"foo/..", "."},
+      {"foo/../bar", "bar"},
+      {"../foo/..", ".."},
+      {"./foo", "foo"},
+  };
+  for (auto test : posix_tests) {
+    EXPECT_EQ(test.second,
+              FileSpec(test.first, false, FileSpec::ePathSyntaxPosix)
+                  .GetNormalizedPath()
+                  .GetPath());
+  }
+
+  std::pair<const char *, const char *> windows_tests[] = {
+      {R"(c:\bar\..\bar)", R"(c:\bar)"},
+      {R"(c:\bar\.\bar)", R"(c:\bar\bar)"},
+      {R"(c:\bar\..)", R"(c:\)"},
+      {R"(c:\bar\.)", R"(c:\bar)"},
+      {R"(c:\.\bar)", R"(c:\bar)"},
+      {R"(\)", R"(\)"},
+      //      {R"(\\)", R"(\\)"},
+      //      {R"(\\net)", R"(\\net)"},
+      {R"(c:\..)", R"(c:\)"},
+      {R"(c:\.)", R"(c:\)"},
+      {R"(\..)", R"(\)"},
+      //      {R"(c:..)", R"(c:..)"},
+      {R"(..)", R"(..)"},
+      {R"(.)", R"(.)"},
+      {R"(c:..\..)", R"(c:..\..)"},
+      {R"(..\..)", R"(..\..)"},
+      {R"(foo\..)", R"(.)"},
+      {R"(foo\..\bar)", R"(bar)"},
+      {R"(..\foo\..)", R"(..)"},
+      {R"(.\foo)", R"(foo)"},
+  };
+  for (auto test : windows_tests) {
+    EXPECT_EQ(test.second,
+              FileSpec(test.first, false, FileSpec::ePathSyntaxWindows)
+                  .GetNormalizedPath()
+                  .GetPath())
+        << "Original path: " << test.first;
   }
 }
-#endif