Update runfiles lib (#982)

* runfiles: Find runfiles in directories that are themselves runfiles

Cherry-picks a fix added to the Bazel version of the runfiles library in
https://github.com/bazelbuild/bazel/commit/486d153d1981c3f47129f675de20189667667fa7

* runfiles: Add tests from Bazel
diff --git a/python/runfiles/runfiles.py b/python/runfiles/runfiles.py
index d7417ec..293af3a 100644
--- a/python/runfiles/runfiles.py
+++ b/python/runfiles/runfiles.py
@@ -200,7 +200,22 @@
 
     def RlocationChecked(self, path):
         # type: (str) -> Optional[str]
-        return self._runfiles.get(path)
+        """Returns the runtime path of a runfile."""
+        exact_match = self._runfiles.get(path)
+        if exact_match:
+            return exact_match
+        # If path references a runfile that lies under a directory that
+        # itself is a runfile, then only the directory is listed in the
+        # manifest. Look up all prefixes of path in the manifest and append
+        # the relative path from the prefix to the looked up path.
+        prefix_end = len(path)
+        while True:
+            prefix_end = path.rfind("/", 0, prefix_end - 1)
+            if prefix_end == -1:
+                return None
+            prefix_match = self._runfiles.get(path[0:prefix_end])
+            if prefix_match:
+                return prefix_match + "/" + path[prefix_end + 1 :]
 
     @staticmethod
     def _LoadRunfiles(path):
diff --git a/tests/runfiles/BUILD.bazel b/tests/runfiles/BUILD.bazel
new file mode 100644
index 0000000..d62e179
--- /dev/null
+++ b/tests/runfiles/BUILD.bazel
@@ -0,0 +1,7 @@
+load("@rules_python//python:defs.bzl", "py_test")
+
+py_test(
+    name = "runfiles_test",
+    srcs = ["runfiles_test.py"],
+    deps = ["//python/runfiles"],
+)
diff --git a/tests/runfiles/runfiles_test.py b/tests/runfiles/runfiles_test.py
new file mode 100644
index 0000000..958ca01
--- /dev/null
+++ b/tests/runfiles/runfiles_test.py
@@ -0,0 +1,375 @@
+# pylint: disable=g-bad-file-header
+# Copyright 2018 The Bazel Authors. 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.
+
+import os
+import tempfile
+import unittest
+
+from python.runfiles import runfiles
+
+
+class RunfilesTest(unittest.TestCase):
+    # """Unit tests for `runfiles.Runfiles`."""
+
+    def testRlocationArgumentValidation(self):
+        r = runfiles.Create({"RUNFILES_DIR": "whatever"})
+        self.assertRaises(ValueError, lambda: r.Rlocation(None))
+        self.assertRaises(ValueError, lambda: r.Rlocation(""))
+        self.assertRaises(TypeError, lambda: r.Rlocation(1))
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("../foo")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("foo/..")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("foo/../bar")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("./foo")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("foo/.")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("foo/./bar")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("//foobar")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("foo//")
+        )
+        self.assertRaisesRegex(
+            ValueError, "is not normalized", lambda: r.Rlocation("foo//bar")
+        )
+        self.assertRaisesRegex(
+            ValueError,
+            "is absolute without a drive letter",
+            lambda: r.Rlocation("\\foo"),
+        )
+
+    def testCreatesManifestBasedRunfiles(self):
+        with _MockFile(contents=["a/b c/d"]) as mf:
+            r = runfiles.Create(
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "RUNFILES_DIR": "ignored when RUNFILES_MANIFEST_FILE has a value",
+                    "TEST_SRCDIR": "always ignored",
+                }
+            )
+            self.assertEqual(r.Rlocation("a/b"), "c/d")
+            self.assertIsNone(r.Rlocation("foo"))
+
+    def testManifestBasedRunfilesEnvVars(self):
+        with _MockFile(name="MANIFEST") as mf:
+            r = runfiles.Create(
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "TEST_SRCDIR": "always ignored",
+                }
+            )
+            self.assertDictEqual(
+                r.EnvVars(),
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "RUNFILES_DIR": mf.Path()[: -len("/MANIFEST")],
+                    "JAVA_RUNFILES": mf.Path()[: -len("/MANIFEST")],
+                },
+            )
+
+        with _MockFile(name="foo.runfiles_manifest") as mf:
+            r = runfiles.Create(
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "TEST_SRCDIR": "always ignored",
+                }
+            )
+            self.assertDictEqual(
+                r.EnvVars(),
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "RUNFILES_DIR": (
+                        mf.Path()[: -len("foo.runfiles_manifest")] + "foo.runfiles"
+                    ),
+                    "JAVA_RUNFILES": (
+                        mf.Path()[: -len("foo.runfiles_manifest")] + "foo.runfiles"
+                    ),
+                },
+            )
+
+        with _MockFile(name="x_manifest") as mf:
+            r = runfiles.Create(
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "TEST_SRCDIR": "always ignored",
+                }
+            )
+            self.assertDictEqual(
+                r.EnvVars(),
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "RUNFILES_DIR": "",
+                    "JAVA_RUNFILES": "",
+                },
+            )
+
+    def testCreatesDirectoryBasedRunfiles(self):
+        r = runfiles.Create(
+            {
+                "RUNFILES_DIR": "runfiles/dir",
+                "TEST_SRCDIR": "always ignored",
+            }
+        )
+        self.assertEqual(r.Rlocation("a/b"), "runfiles/dir/a/b")
+        self.assertEqual(r.Rlocation("foo"), "runfiles/dir/foo")
+
+    def testDirectoryBasedRunfilesEnvVars(self):
+        r = runfiles.Create(
+            {
+                "RUNFILES_DIR": "runfiles/dir",
+                "TEST_SRCDIR": "always ignored",
+            }
+        )
+        self.assertDictEqual(
+            r.EnvVars(),
+            {
+                "RUNFILES_DIR": "runfiles/dir",
+                "JAVA_RUNFILES": "runfiles/dir",
+            },
+        )
+
+    def testFailsToCreateManifestBasedBecauseManifestDoesNotExist(self):
+        def _Run():
+            runfiles.Create({"RUNFILES_MANIFEST_FILE": "non-existing path"})
+
+        self.assertRaisesRegex(IOError, "non-existing path", _Run)
+
+    def testFailsToCreateAnyRunfilesBecauseEnvvarsAreNotDefined(self):
+        with _MockFile(contents=["a b"]) as mf:
+            runfiles.Create(
+                {
+                    "RUNFILES_MANIFEST_FILE": mf.Path(),
+                    "RUNFILES_DIR": "whatever",
+                    "TEST_SRCDIR": "always ignored",
+                }
+            )
+        runfiles.Create(
+            {
+                "RUNFILES_DIR": "whatever",
+                "TEST_SRCDIR": "always ignored",
+            }
+        )
+        self.assertIsNone(runfiles.Create({"TEST_SRCDIR": "always ignored"}))
+        self.assertIsNone(runfiles.Create({"FOO": "bar"}))
+
+    def testManifestBasedRlocation(self):
+        with _MockFile(
+            contents=[
+                "Foo/runfile1",
+                "Foo/runfile2 C:/Actual Path\\runfile2",
+                "Foo/Bar/runfile3 D:\\the path\\run file 3.txt",
+                "Foo/Bar/Dir E:\\Actual Path\\Directory",
+            ]
+        ) as mf:
+            r = runfiles.CreateManifestBased(mf.Path())
+            self.assertEqual(r.Rlocation("Foo/runfile1"), "Foo/runfile1")
+            self.assertEqual(r.Rlocation("Foo/runfile2"), "C:/Actual Path\\runfile2")
+            self.assertEqual(
+                r.Rlocation("Foo/Bar/runfile3"), "D:\\the path\\run file 3.txt"
+            )
+            self.assertEqual(
+                r.Rlocation("Foo/Bar/Dir/runfile4"),
+                "E:\\Actual Path\\Directory/runfile4",
+            )
+            self.assertEqual(
+                r.Rlocation("Foo/Bar/Dir/Deeply/Nested/runfile4"),
+                "E:\\Actual Path\\Directory/Deeply/Nested/runfile4",
+            )
+            self.assertIsNone(r.Rlocation("unknown"))
+            if RunfilesTest.IsWindows():
+                self.assertEqual(r.Rlocation("c:/foo"), "c:/foo")
+                self.assertEqual(r.Rlocation("c:\\foo"), "c:\\foo")
+            else:
+                self.assertEqual(r.Rlocation("/foo"), "/foo")
+
+    def testDirectoryBasedRlocation(self):
+        # The _DirectoryBased strategy simply joins the runfiles directory and the
+        # runfile's path on a "/". This strategy does not perform any normalization,
+        # nor does it check that the path exists.
+        r = runfiles.CreateDirectoryBased("foo/bar baz//qux/")
+        self.assertEqual(r.Rlocation("arg"), "foo/bar baz//qux/arg")
+        if RunfilesTest.IsWindows():
+            self.assertEqual(r.Rlocation("c:/foo"), "c:/foo")
+            self.assertEqual(r.Rlocation("c:\\foo"), "c:\\foo")
+        else:
+            self.assertEqual(r.Rlocation("/foo"), "/foo")
+
+    def testPathsFromEnvvars(self):
+        # Both envvars have a valid value.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "mock1/MANIFEST",
+            lambda path: path == "mock2",
+        )
+        self.assertEqual(mf, "mock1/MANIFEST")
+        self.assertEqual(dr, "mock2")
+
+        # RUNFILES_MANIFEST_FILE is invalid but RUNFILES_DIR is good and there's a
+        # runfiles manifest in the runfiles directory.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "mock2/MANIFEST",
+            lambda path: path == "mock2",
+        )
+        self.assertEqual(mf, "mock2/MANIFEST")
+        self.assertEqual(dr, "mock2")
+
+        # RUNFILES_MANIFEST_FILE is invalid but RUNFILES_DIR is good, but there's no
+        # runfiles manifest in the runfiles directory.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: False,
+            lambda path: path == "mock2",
+        )
+        self.assertEqual(mf, "")
+        self.assertEqual(dr, "mock2")
+
+        # RUNFILES_DIR is invalid but RUNFILES_MANIFEST_FILE is good, and it is in
+        # a valid-looking runfiles directory.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "mock1/MANIFEST",
+            lambda path: path == "mock1",
+        )
+        self.assertEqual(mf, "mock1/MANIFEST")
+        self.assertEqual(dr, "mock1")
+
+        # RUNFILES_DIR is invalid but RUNFILES_MANIFEST_FILE is good, but it is not
+        # in any valid-looking runfiles directory.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "mock1/MANIFEST",
+            lambda path: False,
+        )
+        self.assertEqual(mf, "mock1/MANIFEST")
+        self.assertEqual(dr, "")
+
+        # Both envvars are invalid, but there's a manifest in a runfiles directory
+        # next to argv0, however there's no other content in the runfiles directory.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "argv0.runfiles/MANIFEST",
+            lambda path: False,
+        )
+        self.assertEqual(mf, "argv0.runfiles/MANIFEST")
+        self.assertEqual(dr, "")
+
+        # Both envvars are invalid, but there's a manifest next to argv0. There's
+        # no runfiles tree anywhere.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "argv0.runfiles_manifest",
+            lambda path: False,
+        )
+        self.assertEqual(mf, "argv0.runfiles_manifest")
+        self.assertEqual(dr, "")
+
+        # Both envvars are invalid, but there's a valid manifest next to argv0, and
+        # a valid runfiles directory (without a manifest in it).
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "argv0.runfiles_manifest",
+            lambda path: path == "argv0.runfiles",
+        )
+        self.assertEqual(mf, "argv0.runfiles_manifest")
+        self.assertEqual(dr, "argv0.runfiles")
+
+        # Both envvars are invalid, but there's a valid runfiles directory next to
+        # argv0, though no manifest in it.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: False,
+            lambda path: path == "argv0.runfiles",
+        )
+        self.assertEqual(mf, "")
+        self.assertEqual(dr, "argv0.runfiles")
+
+        # Both envvars are invalid, but there's a valid runfiles directory next to
+        # argv0 with a valid manifest in it.
+        mf, dr = runfiles._PathsFrom(
+            "argv0",
+            "mock1/MANIFEST",
+            "mock2",
+            lambda path: path == "argv0.runfiles/MANIFEST",
+            lambda path: path == "argv0.runfiles",
+        )
+        self.assertEqual(mf, "argv0.runfiles/MANIFEST")
+        self.assertEqual(dr, "argv0.runfiles")
+
+        # Both envvars are invalid and there's no runfiles directory or manifest
+        # next to the argv0.
+        mf, dr = runfiles._PathsFrom(
+            "argv0", "mock1/MANIFEST", "mock2", lambda path: False, lambda path: False
+        )
+        self.assertEqual(mf, "")
+        self.assertEqual(dr, "")
+
+    @staticmethod
+    def IsWindows():
+        return os.name == "nt"
+
+
+class _MockFile(object):
+    def __init__(self, name=None, contents=None):
+        self._contents = contents or []
+        self._name = name or "x"
+        self._path = None
+
+    def __enter__(self):
+        tmpdir = os.environ.get("TEST_TMPDIR")
+        self._path = os.path.join(tempfile.mkdtemp(dir=tmpdir), self._name)
+        with open(self._path, "wt") as f:
+            f.writelines(l + "\n" for l in self._contents)
+        return self
+
+    def __exit__(self, exc_type, exc_value, traceback):
+        os.remove(self._path)
+        os.rmdir(os.path.dirname(self._path))
+
+    def Path(self):
+        return self._path
+
+
+if __name__ == "__main__":
+    unittest.main()