Support: add sys::path::canonical

[arphaman]

Summary

This patch implements the the sys::path::canonical function, which converts a path to its canonical form.

This function is needed for Clang's FileManager::getCanonicalName (there's a FIXME there) and the new
coverage mapping system.

[arphaman]

Fix comment typos

[rnk]

If this is implemented correctly as Duncan describes, we can probably use it to solve http://llvm.org/bugs/show_bug.cgi?id=20440.

[arphaman]

I guess than it would make sense to move it to sys::fs and use realpath internally for unix.
For windows GetFullPathName can be used.

[rnk]

Doug Gregor attempted to use realpath years ago, but it wasn't portable. I would find out why realpath got reverted before using it again.

[arphaman]

Well, his revert comment was:

Rip out realpath() support. It's expensive, and often a bad idea, and I have another way to achieve the same goal.

I'm not sure that portability is an issue here.

[ikonst]

As someone who was looking into http://llvm.org/bugs/show_bug.cgi?id=20440, some comments:

• This naive canonization will break Unix path behavior with symlinks. realpath does the right thing on Un*x. I suspect (although didn't verify) that this is what makes it slow.
• Win32 directory symlinks don't behave like Unix symlinks, so this will do the right thing on Win32.
• That looks like a whole lot of work for path manipulation. All this copying and vectors. Why not do string processing, e.g. "Got a ".."? Go back to the last slash/backslash." I thought performance is of importance here. You can see my code: https://github.com/ikonst/LongPathFix/blob/master/LongPathFixHook/Path.cpp -- I suppose there's a way to do it without using the venerable C string functions.
• This comment says "in place", but the work isn't done "in place" nor is the result "in place".

Now, as to 20440:

• We can keep doing include path concatenations as usual (growing it even to thousands of characters in length) and when time comes for CreateFileWs, we'll pass a canonized \??\ path, same as I implemented here in the form of an API hook: https://github.com/ikonst/LongPathFix
• I don't think this canonizing function quite cuts it for \\?\. You need to handle absolute paths, root paths, relative paths, UNC paths. It's rather Win32 specific.
• The beautiful thing is that 20440 isn't an issue on Un*x since open accepts long paths naturally.

[arphaman]

I'm abandoning this patch because there is another way to deal with my problem for code coverage,
and thus I think that I would also like to keep the non-canonical names in the coverage data.

include/llvm/Support/Path.h

 /// @param path A path that is transformed to native format.
 void native(SmallVectorImpl<char> &path);
 
+/// @brief Convert path to the canonical form in place.
+///
+/// @code
+///   /foo/./net/..//bar/ => "/foo/bar
+///   /foo/bar/net/ => /foo/bar/net"
+///   /foo/bar/../../net => /net
+/// @endcode
+///
+/// @param Path A path that is transformed to canonical format.
+/// @param Result Holds the result of the transformation.
+void canonical(StringRef path, SmallVectorImpl<char> &Result);
+
 /// @}
 /// @name Lexical Observers
 /// @{

lib/Support/Path.cpp

 #endif
 }
 
+void canonical(StringRef Path, SmallVectorImpl<char> &Result) {
+  Result.clear();
+  SmallVector<StringRef, 16> Components;
+
+  // Split the path into the root and relative parts
+  // This is needed to ensure that the root path is just one component,
+  // as the path iterator can represent the root path using more than one
+  // component.
+  auto Root = root_path(Path);
+  auto Relative = Path.substr(Root.size());
+  if (!Root.empty())
+    Components.push_back(Root);
+
+  for(auto I = begin(Relative), End = end(Relative); I != End; ++I) {
+    auto Component = *I;
+    if (Component == ".")
+      continue;
+    else if(Component == ".." && !Components.empty() &&
+            Components.back() != "..") {
+      // Remove the previous component unless it's root
+      if (Components.back() != Root)
+        Components.pop_back();
+      continue;
+    }
+    Components.push_back(Component);
+  }
+  for (const auto &Component : Components)
+    append(Result, Component);
+}
+
 const StringRef filename(StringRef path) {
   return *(--end(path));
 }

unittests/Support/Path.cpp

     EXPECT_EQ(*(--sys::path::end(filename)), (stem + ext).str());
 
     path::native(*i, temp_store);
+    path::canonical(*i, temp_store);
   }
 }
 

 #endif
 }
 
+TEST(Support, CanonicalPath) {
+  auto canonical = [] (StringRef Path) -> std::string {
+    SmallString<256> Result;
+    path::canonical(Path, Result);
+    return Result.str();
+  };
+#ifdef LLVM_ON_WIN32
+  EXPECT_EQ(canonical("..\\foo/."), "..\\foo");
+  EXPECT_EQ(canonical("a:/foo\net/.."),"a:\\foo");
+  EXPECT_EQ(canonical("d:\\foo/net\\bar"), "d:\\foo\\net\\bar");
+  EXPECT_EQ(canonical("..\\\\./.."), "..\\..");
+  EXPECT_EQ(canonical("a:\\\\foo\\.\\net/..\\\\bar\\"), "a:\\foo\\bar");
+  EXPECT_EQ(canonical("\\\\net\\dir\\../bar"), "\\\\net\\bar");
+  EXPECT_EQ(canonical("a:/.."), "a:\\");
+#else
+  EXPECT_EQ(canonical("/foo/./net/..//bar/"), "/foo/bar");
+  EXPECT_EQ(canonical("foo/./bar/../../../net"), "../net");
+  EXPECT_EQ(canonical("../foo/."), "../foo");
+  EXPECT_EQ(canonical("..//./.."), "../..");
+  EXPECT_EQ(canonical("/foo/./net/../../net"), "/net");
+  EXPECT_EQ(canonical("/foo/bar/net/"), "/foo/bar/net");
+  EXPECT_EQ(canonical("/foo/../net"), "/net");
+  EXPECT_EQ(canonical("/.."), "/");
+#endif
+}
+
 class FileSystemTest : public testing::Test {
 protected:
   /// Unique temporary directory in which all created filesystem entities must