diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 95faf51..3c71f88 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -498,6 +498,21 @@
   }
 
   /**
+   * For targets in external repositories, this returns the path the artifact live at in the
+   * runfiles tree. For local targets, it returns the rootRelativePath.
+   */
+  public final PathFragment getRunfilesPath() {
+    PathFragment relativePath = rootRelativePath;
+    if (relativePath.segmentCount() > 1
+        && relativePath.getSegment(0).equals(Label.EXTERNAL_PATH_PREFIX)) {
+      // Turn external/repo/foo into ../repo/foo.
+      relativePath = relativePath.relativeTo(Label.EXTERNAL_PATH_PREFIX);
+      relativePath = new PathFragment("..").getRelative(relativePath);
+    }
+    return relativePath;
+  }
+
+  /**
    * Returns this.getExecPath().getPathString().
    */
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
index d147bdd..15ff6f2 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
@@ -208,7 +208,7 @@
         buffer.append(delimiter);
       }
       buffer.append("${RUNPATH}");
-      buffer.append(artifact.getRootRelativePath().getPathString());
+      buffer.append(artifact.getRunfilesPath().getPathString());
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
index 5b72cbd..f82c9fe 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/BazelPythonSemantics.java
@@ -72,7 +72,11 @@
   @Override
   public List<PathFragment> getImports(RuleContext ruleContext) {
     List<PathFragment> result = new ArrayList<>();
-    PathFragment packageFragment = ruleContext.getLabel().getPackageIdentifier().getPathFragment();
+    PathFragment packageFragment = ruleContext.getLabel().getPackageIdentifier().getRunfilesPath();
+    // Python scripts start with x.runfiles/ as the module space, so everything must be manually
+    // adjusted to be relative to the workspace name.
+    packageFragment = new PathFragment(ruleContext.getWorkspaceName())
+        .getRelative(packageFragment);
     for (String importsAttr : ruleContext.attributes().get("imports", Type.STRING_LIST)) {
       importsAttr = ruleContext.expandMakeVariables("includes", importsAttr);
       if (importsAttr.startsWith("/")) {
@@ -83,7 +87,7 @@
       PathFragment importsPath = packageFragment.getRelative(importsAttr).normalize();
       if (!importsPath.isNormalized()) {
         ruleContext.attributeError("imports",
-            "Path references a path above the execution root.");
+            "Path " + importsAttr + " references a path above the execution root");
       }
       result.add(importsPath);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt
index 594e534..f3fcc8c 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/python/stub_template.txt
@@ -75,18 +75,11 @@
                          sys.argv[0])
 
   python_imports = '%imports%'
-  module_space_with_workspace_name = module_space
-  if '%workspace_name%' != '':
-    module_space_with_workspace_name = os.path.join(module_space, '%workspace_name%')
+  python_path_entries = CreatePythonPathEntries(python_imports, module_space)
 
-  python_path_entries = CreatePythonPathEntries(
-    python_imports, module_space_with_workspace_name)
-
-  external_dir = os.path.join(module_space_with_workspace_name, 'external')
-  if os.path.isdir(external_dir):
-    external_entries = [os.path.join(external_dir, d) for d in os.listdir(external_dir)]
-    repositories = [d for d in external_entries if os.path.isdir(d)]
-    python_path_entries += repositories
+  repo_dirs = [os.path.join(module_space, d) for d in os.listdir(module_space)]
+  repositories = [d for d in repo_dirs if os.path.isdir(d)]
+  python_path_entries += repositories
 
   old_python_path = os.environ.get('PYTHONPATH')
   separator = ':'
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java b/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
index 021845c..2fa4494 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/PackageIdentifier.java
@@ -129,6 +129,14 @@
     return repository.getPathFragment().getRelative(pkgName);
   }
 
+  /**
+   * Returns the runfiles path for this repository (relative to the x.runfiles/main-repo/
+   * directory).
+   */
+  public PathFragment getRunfilesPath() {
+    return getRepository().getRunfilesPath().getRelative(getPackageFragment());
+  }
+
   public PackageIdentifier makeAbsolute() {
     if (!repository.isDefault()) {
       return this;
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java b/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java
index 9a4e5a7..6b89a6e 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/RepositoryName.java
@@ -202,6 +202,16 @@
   }
 
   /**
+   * Returns the runfiles path for this repository (relative to the x.runfiles/main-repo/
+   * directory). If we don't know the name of this repo (i.e., it is in the main repository),
+   * return an empty path fragment.
+   */
+  public PathFragment getRunfilesPath() {
+    return isDefault() || isMain()
+        ? PathFragment.EMPTY_FRAGMENT : new PathFragment("..").getRelative(strippedName());
+  }
+
+  /**
    * Returns the repository name, with leading "{@literal @}" (or "" for the default repository).
    */
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
index b4650d2..1a564ab 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
@@ -459,7 +459,7 @@
     if (launcher != null) {
       javaExecutable = launcher.getRootRelativePath();
     } else {
-      javaExecutable = ruleContext.getFragment(Jvm.class).getJavaExecutable();
+      javaExecutable = ruleContext.getFragment(Jvm.class).getRunfilesJavaExecutable();
     }
 
     String pathPrefix = javaExecutable.isAbsolute() ? "" : "${JAVA_RUNFILES}/"
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java b/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java
index e24266d..edecece 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/Jvm.java
@@ -39,6 +39,10 @@
   private final PathFragment jar;
   private final PathFragment java;
 
+  private static final String BIN_JAVAC = "bin/javac" + OsUtils.executableExtension();
+  private static final String BIN_JAR = "bin/jar" + OsUtils.executableExtension();
+  private static final String BIN_JAVA = "bin/java" + OsUtils.executableExtension();
+
   /**
    * Creates a Jvm instance. Either the {@code javaHome} parameter is absolute,
    * or the {@code jvmLabel} parameter must be non-null. This restriction might
@@ -48,9 +52,9 @@
     Preconditions.checkArgument(javaHome.isAbsolute() ^ (jvmLabel != null));
     this.javaHome = javaHome;
     this.jvmLabel = jvmLabel;
-    this.javac = getJavaHome().getRelative("bin/javac" + OsUtils.executableExtension());
-    this.jar = getJavaHome().getRelative("bin/jar" + OsUtils.executableExtension());
-    this.java = getJavaHome().getRelative("bin/java" + OsUtils.executableExtension());
+    this.javac = getJavaHome().getRelative(BIN_JAVAC);
+    this.jar = getJavaHome().getRelative(BIN_JAR);
+    this.java = getJavaHome().getRelative(BIN_JAVA);
   }
 
   /**
@@ -95,6 +99,17 @@
     return jvmLabel;
   }
 
+  /**
+   * If possible, resolves java relative to the jvmLabel's repository. Otherwise, returns the
+   * same thing as getJavaExecutable().
+   */
+  public PathFragment getRunfilesJavaExecutable() {
+    if (jvmLabel == null || jvmLabel.getPackageIdentifier().getRepository().isMain()) {
+      return getJavaExecutable();
+    }
+    return jvmLabel.getPackageIdentifier().getRepository().getRunfilesPath().getRelative(BIN_JAVA);
+  }
+
   @Override
   public void addGlobalMakeVariables(Builder<String, String> globalMakeEnvBuilder) {
     globalMakeEnvBuilder.put("JAVABASE", getJavaHome().getPathString());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java b/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
index 60fa5a6..045c06c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/python/PyCommon.java
@@ -406,8 +406,8 @@
         } else {
           ruleContext.attributeError("srcs",
               buildMultipleMainMatchesErrorText(explicitMain, mainSourceName,
-                  mainArtifact.getRootRelativePath().toString(),
-                  outItem.getRootRelativePath().toString()));
+                  mainArtifact.getRunfilesPath().toString(),
+                  outItem.getRunfilesPath().toString()));
         }
       }
     }
@@ -418,7 +418,7 @@
     }
 
     PathFragment workspaceName = new PathFragment(ruleContext.getRule().getWorkspaceName());
-    return workspaceName.getRelative(mainArtifact.getRootRelativePath()).getPathString();
+    return workspaceName.getRelative(mainArtifact.getRunfilesPath()).getPathString();
   }
 
   public Artifact getExecutable() {