add functions for normalizing win32 include paths

(Note from Evan: this is landing Scott's code more or less verbatim
without a lot of analysis; it could maybe be simplified and reduced,
but it's only intended to be used in the MSVC helper so it's fine
to be experimental.)

4 files changed, 252 insertions, 1 deletions

diff --git a/configure.py b/configure.py
index 1cdab49..ed05031 100755
--- a/configure.py
+++ b/configure.py
@@ -254,6 +254,7 @@ for name in ['build',
 if platform in ('mingw', 'windows'):
     objs += cxx('subprocess-win32')
     if platform == 'windows':
+        objs += cxx('includes_normalize-win32')
         objs += cxx('msvc_helper-win32')
         objs += cxx('minidump-win32')
     objs += cc('getopt')
@@ -325,7 +326,8 @@ for name in ['build_log_test',
              'util_test']:
     objs += cxx(name, variables=[('cflags', test_cflags)])
 if platform == 'windows':
-    objs += cxx('msvc_helper_test', variables=[('cflags', test_cflags)])
+    for name in ['includes_normalize_test', 'msvc_helper_test']:
+        objs += cxx(name, variables=[('cflags', test_cflags)])
 
 if platform != 'mingw' and platform != 'windows':
     test_libs.append('-lpthread')
diff --git a/src/includes_normalize-win32.cc b/src/includes_normalize-win32.cc
new file mode 100644
index 0000000..cf398ae
--- /dev/null
+++ b/src/includes_normalize-win32.cc
@@ -0,0 +1,116 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "includes_normalize.h"
+
+#include "string_piece.h"
+#include "util.h"
+
+#include <algorithm>
+#include <iterator>
+#include <sstream>
+
+#include <windows.h>
+
+namespace {
+
+/// Return true if paths a and b are on the same Windows drive.
+bool SameDrive(StringPiece a, StringPiece b)  {
+  char a_absolute[_MAX_PATH];
+  char b_absolute[_MAX_PATH];
+  GetFullPathName(a.AsString().c_str(), sizeof(a_absolute), a_absolute, NULL);
+  GetFullPathName(b.AsString().c_str(), sizeof(b_absolute), b_absolute, NULL);
+  char a_drive[_MAX_DIR];
+  char b_drive[_MAX_DIR];
+  _splitpath(a_absolute, a_drive, NULL, NULL, NULL);
+  _splitpath(b_absolute, b_drive, NULL, NULL, NULL);
+  return _stricmp(a_drive, b_drive) == 0;
+}
+
+}  // anonymous namespace
+
+string IncludesNormalize::Join(const vector<string>& list, char sep) {
+  string ret;
+  for (size_t i = 0; i < list.size(); ++i) {
+    ret += list[i];
+    if (i != list.size() - 1)
+      ret += sep;
+  }
+  return ret;
+}
+
+vector<string> IncludesNormalize::Split(const string& input, char sep) {
+  vector<string> elems;
+  stringstream ss(input);
+  string item;
+  while (getline(ss, item, sep))
+    elems.push_back(item);
+  return elems;
+}
+
+string IncludesNormalize::ToLower(const string& s) {
+  string ret;
+  transform(s.begin(), s.end(), back_inserter(ret), tolower);
+  return ret;
+}
+
+string IncludesNormalize::AbsPath(StringPiece s) {
+  char result[_MAX_PATH];
+  GetFullPathName(s.AsString().c_str(), sizeof(result), result, NULL);
+  return result;
+}
+
+string IncludesNormalize::Relativize(StringPiece path, const string& start) {
+  vector<string> start_list = Split(AbsPath(start), '\\');
+  vector<string> path_list = Split(AbsPath(path), '\\');
+  int i;
+  for (i = 0; i < static_cast<int>(min(start_list.size(), path_list.size()));
+       ++i) {
+    if (ToLower(start_list[i]) != ToLower(path_list[i]))
+      break;
+  }
+
+  vector<string> rel_list;
+  for (int j = 0; j < static_cast<int>(start_list.size() - i); ++j)
+    rel_list.push_back("..");
+  for (int j = i; j < static_cast<int>(path_list.size()); ++j)
+    rel_list.push_back(path_list[j]);
+  if (rel_list.size() == 0)
+    return ".";
+  return Join(rel_list, '\\');
+}
+
+string IncludesNormalize::Normalize(StringPiece input,
+                                    const char* relative_to) {
+  char copy[_MAX_PATH];
+  size_t len = input.len_;
+  strncpy(copy, input.str_, input.len_ + 1);
+  for (size_t j = 0; j < len; ++j)
+    if (copy[j] == '/')
+      copy[j] = '\\';
+  string err;
+  if (!CanonicalizePath(copy, &len, &err)) {
+    Warning("couldn't canonicalize '%*s': %s\n", input.len_, input.str_,
+            err.c_str());
+  }
+  string curdir;
+  if (!relative_to) {
+    curdir = AbsPath(".");
+    relative_to = curdir.c_str();
+  }
+  StringPiece partially_fixed(copy, len);
+  if (!SameDrive(partially_fixed, relative_to))
+    return partially_fixed.AsString();
+  return ToLower(Relativize(partially_fixed, relative_to));
+}
diff --git a/src/includes_normalize.h b/src/includes_normalize.h
new file mode 100644
index 0000000..458613a
--- /dev/null
+++ b/src/includes_normalize.h
@@ -0,0 +1,35 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <string>
+#include <vector>
+using namespace std;
+
+struct StringPiece;
+
+/// Utility functions for normalizing include paths on Windows.
+/// TODO: this likely duplicates functionality of CanonicalizePath; refactor.
+struct IncludesNormalize {
+  // Internal utilities made available for testing, maybe useful otherwise.
+  static string Join(const vector<string>& list, char sep);
+  static vector<string> Split(const string& input, char sep);
+  static string ToLower(const string& s);
+  static string AbsPath(StringPiece s);
+  static string Relativize(StringPiece path, const string& start);
+
+  /// Normalize by fixing slashes style, fixing redundant .. and . and makes the
+  /// path relative to |relative_to|. Case is normalized to lowercase on
+  /// Windows too.
+  static string Normalize(StringPiece input, const char* relative_to);
+};
diff --git a/src/includes_normalize_test.cc b/src/includes_normalize_test.cc
new file mode 100644
index 0000000..97f7174
--- /dev/null
+++ b/src/includes_normalize_test.cc
@@ -0,0 +1,98 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "includes_normalize.h"
+
+#include <gtest/gtest.h>
+
+#include "test.h"
+#include "util.h"
+
+TEST(IncludesNormalize, Simple) {
+  EXPECT_EQ("b", IncludesNormalize::Normalize("a\\..\\b", NULL));
+  EXPECT_EQ("b", IncludesNormalize::Normalize("a\\../b", NULL));
+  EXPECT_EQ("a\\b", IncludesNormalize::Normalize("a\\.\\b", NULL));
+  EXPECT_EQ("a\\b", IncludesNormalize::Normalize("a\\./b", NULL));
+}
+
+namespace {
+
+string GetCurDir() {
+  char buf[_MAX_PATH];
+  _getcwd(buf, sizeof(buf));
+  vector<string> parts = IncludesNormalize::Split(string(buf), '\\');
+  return parts[parts.size() - 1];
+}
+
+}  // namespace
+
+TEST(IncludesNormalize, WithRelative) {
+  string currentdir = IncludesNormalize::ToLower(GetCurDir());
+  EXPECT_EQ("c", IncludesNormalize::Normalize("a/b/c", "a/b"));
+  EXPECT_EQ("a", IncludesNormalize::Normalize(IncludesNormalize::AbsPath("a"), NULL));
+  EXPECT_EQ(string("..\\") + currentdir + string("\\a"),
+            IncludesNormalize::Normalize("a", "../b"));
+  EXPECT_EQ(string("..\\") + currentdir + string("\\a\\b"),
+            IncludesNormalize::Normalize("a/b", "../c"));
+  EXPECT_EQ("..\\..\\a", IncludesNormalize::Normalize("a", "b/c"));
+  EXPECT_EQ(".", IncludesNormalize::Normalize("a", "a"));
+}
+
+TEST(IncludesNormalize, Case) {
+  EXPECT_EQ("b", IncludesNormalize::Normalize("Abc\\..\\b", NULL));
+  EXPECT_EQ("bdef", IncludesNormalize::Normalize("Abc\\..\\BdEf", NULL));
+  EXPECT_EQ("a\\b", IncludesNormalize::Normalize("A\\.\\b", NULL));
+  EXPECT_EQ("a\\b", IncludesNormalize::Normalize("A\\./b", NULL));
+  EXPECT_EQ("a\\b", IncludesNormalize::Normalize("A\\.\\B", NULL));
+  EXPECT_EQ("a\\b", IncludesNormalize::Normalize("A\\./B", NULL));
+}
+
+TEST(IncludesNormalize, Join) {
+  vector<string> x;
+  EXPECT_EQ("", IncludesNormalize::Join(x, ':'));
+  x.push_back("alpha");
+  EXPECT_EQ("alpha", IncludesNormalize::Join(x, ':'));
+  x.push_back("beta");
+  x.push_back("gamma");
+  EXPECT_EQ("alpha:beta:gamma", IncludesNormalize::Join(x, ':'));
+}
+
+TEST(IncludesNormalize, Split) {
+  EXPECT_EQ("", IncludesNormalize::Join(IncludesNormalize::Split("", '/'), ':'));
+  EXPECT_EQ("a", IncludesNormalize::Join(IncludesNormalize::Split("a", '/'), ':'));
+  EXPECT_EQ("a:b:c", IncludesNormalize::Join(IncludesNormalize::Split("a/b/c", '/'), ':'));
+}
+
+TEST(IncludesNormalize, ToLower) {
+  EXPECT_EQ("", IncludesNormalize::ToLower(""));
+  EXPECT_EQ("stuff", IncludesNormalize::ToLower("Stuff"));
+  EXPECT_EQ("stuff and things", IncludesNormalize::ToLower("Stuff AND thINGS"));
+  EXPECT_EQ("stuff 3and thin43gs", IncludesNormalize::ToLower("Stuff 3AND thIN43GS"));
+}
+
+TEST(IncludesNormalize, DifferentDrive) {
+  EXPECT_EQ("stuff.h",
+      IncludesNormalize::Normalize("p:\\vs08\\stuff.h", "p:\\vs08"));
+  EXPECT_EQ("stuff.h",
+      IncludesNormalize::Normalize("P:\\vs08\\stuff.h", "p:\\vs08"));
+  EXPECT_EQ("P:\\vs08\\stuff.h",
+      IncludesNormalize::Normalize("P:\\vs08\\stuff.h", "c:\\vs08"));
+  EXPECT_EQ("P:\\vs08\\stuff.h",
+      IncludesNormalize::Normalize("P:\\vs08\\stuff.h", "D:\\stuff/things"));
+  EXPECT_EQ("P:\\vs08\\stuff.h",
+      IncludesNormalize::Normalize("P:/vs08\\stuff.h", "D:\\stuff/things"));
+  // TODO: this fails; fix it.
+  //EXPECT_EQ("P:\\wee\\stuff.h",
+  //    IncludesNormalize::Normalize("P:/vs08\\../wee\\stuff.h", "D:\\stuff/things"));
+}