Bazel client; implement NormalizePath

This method can normalize paths with "." and ".."
and multiple "/" characters.

E.g. normalize("../foo/./bar/../baz") = "foo/baz"

This method enables us implementing PathExists on
Windows. If the path to check is too long, we need
to prefix it with "\\?\" for the Windows API
functions to work, but then the path must be
fully normalized and in Windows format. We already
have functions to convert a path to Windows format
but that doesn't normalize; with this function we
can finally convert paths like "/c/foo/../bar" to
L"\\?\c:\foo" and check if it exists.

See https://github.com/bazelbuild/bazel/issues/2107
See https://github.com/bazelbuild/bazel/issues/2181

--
PiperOrigin-RevId: 142648194
MOS_MIGRATED_REVID=142648194

3 files changed, 81 insertions, 0 deletions

diff --git a/src/main/cpp/util/file.cc b/src/main/cpp/util/file.cc
index 392af372af..8d66710813 100644
--- a/src/main/cpp/util/file.cc
+++ b/src/main/cpp/util/file.cc
@@ -18,6 +18,7 @@
 
 #include <algorithm>
 #include <cstdlib>
+#include <sstream>  // ostringstream
 #include <vector>
 
 #include "src/main/cpp/util/file_platform.h"
@@ -31,6 +32,61 @@ using std::pair;
 using std::string;
 using std::vector;
 
+string NormalizePath(const string &path) {
+  if (path.empty()) {
+    return string();
+  }
+
+  static const string dot(".");
+  static const string dotdot("..");
+
+  vector<string> segments;
+  int segment_start = -1;
+  // Find the path segments in `path` (separated by "/").
+  for (int i = 0;; ++i) {
+    if (path[i] != '/' && path[i] != '\0') {
+      // The current character does not end a segment, so start one unless it's
+      // already started.
+      if (segment_start < 0) {
+        segment_start = i;
+      }
+    } else if (segment_start >= 0 && i > segment_start) {
+      // The current character is "/" or "\0", so this ends a segment.
+      // Add that to `segments` if there's anything to add; handle "." and "..".
+      string segment(path, segment_start, i - segment_start);
+      segment_start = -1;
+      if (segment == dotdot) {
+        if (!segments.empty()) {
+          segments.pop_back();
+        }
+      } else if (segment != dot) {
+        segments.push_back(segment);
+      }
+    }
+    if (path[i] == '\0') {
+      break;
+    }
+  }
+
+  // Handle the case when `path` was just "/" (or some degenerate form of it,
+  // e.g. "/..").
+  if (segments.empty() && path[0] == '/') {
+    return "/";
+  }
+
+  // Join all segments, make sure we preserve the leading "/" if any.
+  bool first = true;
+  std::ostringstream result;
+  for (const auto &s : segments) {
+    if (!first || path[0] == '/') {
+      result << "/";
+    }
+    first = false;
+    result << s;
+  }
+  return result.str();
+}
+
 bool ReadFrom(const std::function<int(void *, int)> &read_func, string *content,
               int max_size) {
   content->clear();
diff --git a/src/main/cpp/util/file.h b/src/main/cpp/util/file.h
index efe963c6d7..d380c33a0a 100644
--- a/src/main/cpp/util/file.h
+++ b/src/main/cpp/util/file.h
@@ -34,6 +34,15 @@ class IPipe {
   virtual int Receive(void *buffer, int size) = 0;
 };
 
+// Returns a normalized form of the input `path`.
+// Normalization means removing "." references, resolving ".." references, and
+// deduplicating "/" characters.
+// For example if `path` is "foo/../bar/.//qux", the result is "bar/qux".
+// Uplevel references that cannot go any higher in the directory tree are simply
+// ignored, e.g. "/.." is normalized to "/" and "../../foo" is normalized to
+// "foo".
+std::string NormalizePath(const std::string &path);
+
 // Replaces 'content' with data read from a source using `read_func`.
 // If `max_size` is positive, the method reads at most that many bytes;
 // otherwise the method reads everything.
diff --git a/src/test/cpp/util/file_test.cc b/src/test/cpp/util/file_test.cc
index fa379f567d..f98ed9975a 100644
--- a/src/test/cpp/util/file_test.cc
+++ b/src/test/cpp/util/file_test.cc
@@ -22,6 +22,22 @@
 
 namespace blaze_util {
 
+TEST(FileTest, TestNormalizePath) {
+  ASSERT_EQ(string(""), NormalizePath(""));
+  ASSERT_EQ(string(""), NormalizePath("."));
+  ASSERT_EQ(string("/"), NormalizePath("/"));
+  ASSERT_EQ(string("/"), NormalizePath("//"));
+  ASSERT_EQ(string("foo"), NormalizePath("foo"));
+  ASSERT_EQ(string("foo"), NormalizePath("foo/"));
+  ASSERT_EQ(string("foo/bar"), NormalizePath("foo//bar"));
+  ASSERT_EQ(string("foo/bar"), NormalizePath("../..//foo//bar"));
+  ASSERT_EQ(string("/foo"), NormalizePath("/foo"));
+  ASSERT_EQ(string("/foo"), NormalizePath("/foo/"));
+  ASSERT_EQ(string("/foo/bar"), NormalizePath("/foo/./bar/"));
+  ASSERT_EQ(string("foo/bar"), NormalizePath("../foo/baz/../bar"));
+  ASSERT_EQ(string("foo/bar"), NormalizePath("../foo//./baz/../bar///"));
+}
+
 TEST(FileTest, TestSingleThreadedPipe) {
   std::unique_ptr<IPipe> pipe(CreatePipe());
   char buffer[50] = {0};