diff --git a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
index 7d187f9..3f2f360 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFactory.java
@@ -305,17 +305,17 @@
       // Source exec paths cannot escape the source root.
       return null;
     }
-    Artifact artifact = sourceArtifactCache.getArtifactIfValid(execPath);
-    if (artifact != null) {
-      return artifact;
-    }
     // Don't create an artifact if it's derived.
     if (isDerivedArtifact(execPath)) {
       return null;
     }
-
-    return createArtifactIfNotValid(
-        findSourceRoot(execPath, baseExecPath, baseRoot, repositoryName), execPath);
+    Root sourceRoot = findSourceRoot(execPath, baseExecPath, baseRoot, repositoryName);
+    Artifact artifact = sourceArtifactCache.getArtifactIfValid(execPath);
+    if (artifact != null) {
+      Preconditions.checkState(sourceRoot == null || sourceRoot.equals(artifact.getRoot()));
+      return artifact;
+    }
+    return createArtifactIfNotValid(sourceRoot, execPath);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Root.java b/src/main/java/com/google/devtools/build/lib/actions/Root.java
index 59010e9..859a8b6 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Root.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Root.java
@@ -15,16 +15,15 @@
 package com.google.devtools.build.lib.actions;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.io.Serializable;
 import java.util.Objects;
-
 import javax.annotation.Nullable;
 
 /**
@@ -57,6 +56,20 @@
     return new Root(null, path, false, isMainRepo);
   }
 
+  // This must always be consistent with Package.getSourceRoot; otherwise computing source roots
+  // from exec paths does not work, which can break the action cache for input-discovering actions.
+  public static Root computeSourceRoot(Path packageRoot, RepositoryName repository) {
+    if (repository.isMain()) {
+      return Root.asSourceRoot(packageRoot, true);
+    } else {
+      Path actualRoot = packageRoot;
+      for (int i = 0; i < repository.getSourceRoot().segmentCount(); i++) {
+        actualRoot = actualRoot.getParentDirectory();
+      }
+      return Root.asSourceRoot(actualRoot, false);
+    }
+  }
+
   /**
    * testonly until {@link #asSourceRoot(Path, boolean)} is deleted.
    */
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 1e2e3d0..5688a31 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
@@ -20,10 +20,8 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.Canonicalizer;
 import com.google.devtools.build.lib.vfs.PathFragment;
-
 import java.io.Serializable;
 import java.util.Objects;
-
 import javax.annotation.concurrent.Immutable;
 
 /**
@@ -59,6 +57,41 @@
   }
 
   /**
+   * Tries to infer the package identifier from the given exec path. This method does not perform
+   * any I/O, but looks solely at the structure of the exec path. The resulting identifier may
+   * actually be a subdirectory of a package rather than a package, e.g.:
+   * <pre><code>
+   * + WORKSPACE
+   * + foo/BUILD
+   * + foo/bar/bar.java
+   * </code></pre>
+   *
+   * In this case, this method returns a package identifier for foo/bar, even though that is not a
+   * package. Callers need to look up the actual package if needed.
+   *
+   * @throws LabelSyntaxException if the exec path seems to be for an external repository that doe
+   *         not have a valid repository name (see {@link RepositoryName#create})
+   */
+  public static PackageIdentifier discoverFromExecPath(PathFragment execPath, boolean forFiles)
+      throws LabelSyntaxException {
+    Preconditions.checkArgument(!execPath.isAbsolute(), execPath);
+    PathFragment tofind = forFiles
+        ? Preconditions.checkNotNull(
+            execPath.getParentDirectory(), "Must pass in files, not root directory")
+        : execPath;
+    if (tofind.startsWith(new PathFragment(Label.EXTERNAL_PATH_PREFIX))) {
+      // TODO(ulfjack): Remove this when kchodorow@'s exec root rearrangement has been rolled out.
+      RepositoryName repository = RepositoryName.create("@" + tofind.getSegment(1));
+      return PackageIdentifier.create(repository, tofind.subFragment(2, tofind.segmentCount()));
+    } else if (!tofind.normalize().isNormalized()) {
+      RepositoryName repository = RepositoryName.create("@" + tofind.getSegment(1));
+      return PackageIdentifier.create(repository, tofind.subFragment(2, tofind.segmentCount()));
+    } else {
+      return PackageIdentifier.createInMainRepo(tofind);
+    }
+  }
+
+  /**
    * The identifier for this repository. This is either "" or prefixed with an "@",
    * e.g., "@myrepo".
    */
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java
index 45fa5ca..e4f7261 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Package.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -260,6 +260,8 @@
     defaultRestrictedTo = environments;
   }
 
+  // This must always be consistent with Root.computeSourceRoot; otherwise computing source roots
+  // from exec paths does not work, which can break the action cache for input-discovering actions.
   private static Path getSourceRoot(Path buildFile, PathFragment packageFragment) {
     Path current = buildFile.getParentDirectory();
     for (int i = 0, len = packageFragment.segmentCount();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index 3f84370..7f43372 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -334,9 +334,11 @@
     // the inputs are as declared, hence known, and remain so.
     this.shouldScanIncludes = shouldScanIncludes;
     this.shouldPruneModules = shouldPruneModules;
+    // We can only prune modules if include scanning is enabled.
+    Preconditions.checkArgument(!shouldPruneModules || shouldScanIncludes, this);
     this.usePic = usePic;
     this.useHeaderModules = useHeaderModules;
-    this.inputsKnown = !shouldScanIncludes;
+    this.inputsKnown = !shouldScanIncludes && !cppSemantics.needsDotdInputPruning();
     this.cppCompileCommandLine =
         new CppCompileCommandLine(
             sourceFile, dotdFile, copts, coptsFilter, features, variables, actionName);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java
index 5b59a06..5ae21d1 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/HeaderDiscovery.java
@@ -20,6 +20,8 @@
 import com.google.devtools.build.lib.actions.ActionExecutionException;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ArtifactResolver;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
+import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
@@ -122,7 +124,15 @@
       }
       Artifact artifact = allowedDerivedInputsMap.get(execPathFragment);
       if (artifact == null) {
-        artifact = artifactResolver.resolveSourceArtifact(execPathFragment, RepositoryName.MAIN);
+        try {
+          RepositoryName repository =
+              PackageIdentifier.discoverFromExecPath(execPathFragment, false).getRepository();
+          artifact = artifactResolver.resolveSourceArtifact(execPathFragment, repository);
+        } catch (LabelSyntaxException e) {
+          throw new ActionExecutionException(
+              String.format("Could not find the external repository for %s", execPathFragment),
+              e, action, false);
+        }
       }
       if (artifact != null) {
         inputs.add(artifact);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index fc7db60..538ef90 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -33,6 +33,7 @@
 import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.causes.Cause;
 import com.google.devtools.build.lib.causes.LabelCause;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.events.Event;
@@ -296,10 +297,15 @@
         PathFragment parent = Preconditions.checkNotNull(
             path.getParentDirectory(), "Must pass in files, not root directory");
         Preconditions.checkArgument(!parent.isAbsolute(), path);
-        SkyKey depKey =
-            ContainingPackageLookupValue.key(PackageIdentifier.createInMainRepo(parent));
-        depKeys.put(path, depKey);
-        keysRequested.add(depKey);
+        try {
+          SkyKey depKey =
+              ContainingPackageLookupValue.key(PackageIdentifier.discoverFromExecPath(path, true));
+          depKeys.put(path, depKey);
+          keysRequested.add(depKey);
+        } catch (LabelSyntaxException e) {
+          throw new PackageRootResolutionException(
+              String.format("Could not find the external repository for %s", path), e);
+        }
       }
 
       Map<SkyKey,
@@ -315,8 +321,8 @@
         try {
           value = (ContainingPackageLookupValue) values.get(depKeys.get(path)).get();
         } catch (NoSuchPackageException | InconsistentFilesystemException e) {
-          throw new PackageRootResolutionException("Could not determine containing package for "
-              + path, e);
+          throw new PackageRootResolutionException(
+              String.format("Could not determine containing package for %s", path), e);
         }
 
         if (value == null) {
@@ -325,8 +331,10 @@
         }
         if (value.hasContainingPackage()) {
           // We have found corresponding root for current execPath.
-          result.put(path, Root.asSourceRoot(value.getContainingPackageRoot(),
-              value.getContainingPackageName().getRepository().isMain()));
+          result.put(path,
+              Root.computeSourceRoot(
+                  value.getContainingPackageRoot(),
+                  value.getContainingPackageName().getRepository()));
         } else {
           // We haven't found corresponding root for current execPath.
           result.put(path, null);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index a8acf88..59a0bbc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -72,6 +72,7 @@
 import com.google.devtools.build.lib.analysis.config.ConfigurationFragmentFactory;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
@@ -744,7 +745,6 @@
     return ImmutableList.of(value.getStableArtifact(), value.getVolatileArtifact());
   }
 
-  // TODO(bazel-team): Make this take a PackageIdentifier.
   public Map<PathFragment, Root> getArtifactRootsForFiles(
       final EventHandler eventHandler, Iterable<PathFragment> execPaths)
       throws PackageRootResolutionException, InterruptedException {
@@ -760,28 +760,23 @@
   private Map<PathFragment, Root> getArtifactRoots(
       final EventHandler eventHandler, Iterable<PathFragment> execPaths, boolean forFiles)
       throws PackageRootResolutionException, InterruptedException {
-
-    final List<SkyKey> packageKeys = new ArrayList<>();
-    if (forFiles) {
-      for (PathFragment execPath : execPaths) {
-        PathFragment parent = Preconditions.checkNotNull(
-            execPath.getParentDirectory(), "Must pass in files, not root directory");
-        Preconditions.checkArgument(!parent.isAbsolute(), execPath);
-        packageKeys.add(ContainingPackageLookupValue.key(
-            PackageIdentifier.createInMainRepo(parent)));
-      }
-    } else {
-      for (PathFragment execPath : execPaths) {
-        Preconditions.checkArgument(!execPath.isAbsolute(), execPath);
-        packageKeys.add(ContainingPackageLookupValue.key(
-            PackageIdentifier.createInMainRepo(execPath)));
+    final Map<PathFragment, SkyKey> packageKeys = new HashMap<>();
+    for (PathFragment execPath : execPaths) {
+      try {
+        PackageIdentifier pkgIdentifier =
+            PackageIdentifier.discoverFromExecPath(execPath, forFiles);
+        packageKeys.put(execPath, ContainingPackageLookupValue.key(pkgIdentifier));
+      } catch (LabelSyntaxException e) {
+        throw new PackageRootResolutionException(
+            String.format("Could not find the external repository for %s", execPath), e);
       }
     }
 
     EvaluationResult<ContainingPackageLookupValue> result;
     synchronized (valueLookupLock) {
       result =
-          buildDriver.evaluate(packageKeys, /*keepGoing=*/ true, /*numThreads=*/ 1, eventHandler);
+          buildDriver.evaluate(
+              packageKeys.values(), /*keepGoing=*/ true, /*numThreads=*/ 1, eventHandler);
     }
 
     if (result.hasError()) {
@@ -791,11 +786,12 @@
 
     Map<PathFragment, Root> roots = new HashMap<>();
     for (PathFragment execPath : execPaths) {
-      ContainingPackageLookupValue value = result.get(ContainingPackageLookupValue.key(
-          PackageIdentifier.createInMainRepo(forFiles ? execPath.getParentDirectory() : execPath)));
+      ContainingPackageLookupValue value = result.get(packageKeys.get(execPath));
       if (value.hasContainingPackage()) {
-        roots.put(execPath, Root.asSourceRoot(value.getContainingPackageRoot(),
-            value.getContainingPackageName().getRepository().isMain()));
+        roots.put(execPath,
+            Root.computeSourceRoot(
+                value.getContainingPackageRoot(),
+                value.getContainingPackageName().getRepository()));
       } else {
         roots.put(execPath, null);
       }