diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
index 0bccc72..07f7a02 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisEnvironment.java
@@ -45,6 +45,11 @@
    * Returns the artifact for the derived file {@code rootRelativePath}.
    *
    * <p>Creates the artifact if necessary and sets the root of that artifact to {@code root}.
+   *
+   * <p>This method can create artifacts anywhere in the output tree, thus making it possible for
+   * artifacts generated by two different rules to clash. To avoid this, use the methods
+   * {@code getUniqueDirectoryArtifact} and {@code getPackageRelativeArtifact} on
+   * {@link RuleContext}.
    */
   Artifact getDerivedArtifact(PathFragment rootRelativePath, Root root);
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
index 3ded47d..9abcb25 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AnalysisUtils.java
@@ -125,7 +125,7 @@
    * <p>For example "//pkg:target" -> "pkg/&lt;fragment&gt;/target.
    */
   public static PathFragment getUniqueDirectory(Label label, PathFragment fragment) {
-    return label.getPackageFragment().getRelative(fragment)
+    return label.getPackageIdentifier().getPathFragment().getRelative(fragment)
         .getRelative(label.getName());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java b/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
index 2ac3bcc..d71998b 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/PseudoAction.java
@@ -88,9 +88,8 @@
   }
 
   public static Artifact getDummyOutput(RuleContext ruleContext) {
-    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-        ruleContext.getLabel().toPathFragment().replaceName(
-            ruleContext.getLabel().getName() + ".extra_action_dummy"),
+    return ruleContext.getPackageRelativeArtifact(
+        ruleContext.getLabel().getName() + ".extra_action_dummy",
         ruleContext.getConfiguration().getGenfilesDirectory());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index 8f5351f..875e89f 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -358,10 +358,10 @@
   @Override
   public void attributeError(String attrName, String message) {
     reportError(rule.getAttributeLocation(attrName),
-                prefixAttributeMessage(Attribute.isImplicit(attrName)
-                                           ? "(an implicit dependency)"
-                                           : attrName,
-                                       message));
+        prefixAttributeMessage(Attribute.isImplicit(attrName)
+                ? "(an implicit dependency)"
+                : attrName,
+            message));
   }
 
   /**
@@ -373,10 +373,10 @@
   @Override
   public void attributeWarning(String attrName, String message) {
     reportWarning(rule.getAttributeLocation(attrName),
-                  prefixAttributeMessage(Attribute.isImplicit(attrName)
-                                             ? "(an implicit dependency)"
-                                             : attrName,
-                                         message));
+        prefixAttributeMessage(Attribute.isImplicit(attrName)
+                ? "(an implicit dependency)"
+                : attrName,
+            message));
   }
 
   private String prefixAttributeMessage(String attrName, String message) {
@@ -424,8 +424,12 @@
    * signature.
    */
   private Artifact internalCreateOutputArtifact(Target target) {
+    Preconditions.checkState(
+        target.getLabel().getPackageIdentifier().equals(getLabel().getPackageIdentifier()),
+        "Creating output artifact for target '%s' in different package than the rule '%s' "
+            + "being analyzed", target.getLabel(), getLabel());
     Root root = getBinOrGenfilesDirectory();
-    return getAnalysisEnvironment().getDerivedArtifact(Util.getWorkspaceRelativePath(target), root);
+    return getPackageRelativeArtifact(target.getName(), root);
   }
 
   /**
@@ -440,6 +444,71 @@
         : getConfiguration().getGenfilesDirectory();
   }
 
+  /**
+   * Creates an artifact in a directory that is unique to the package that contains the rule,
+   * thus guaranteeing that it never clashes with artifacts created by rules in other packages.
+   */
+  public Artifact getPackageRelativeArtifact(String relative, Root root) {
+    return getPackageRelativeArtifact(new PathFragment(relative), root);
+  }
+
+  /**
+   * Creates an artifact in a directory that is unique to the package that contains the rule,
+   * thus guaranteeing that it never clashes with artifacts created by rules in other packages.
+   */
+  public Artifact getPackageRelativeArtifact(PathFragment relative, Root root) {
+    return getDerivedArtifact(getPackageDirectory().getRelative(relative), root);
+  }
+
+  /**
+   * Returns the root-relative path fragment under which output artifacts of this rule should go.
+   *
+   * <p>Note that:
+   * <ul>
+   *   <li>This doesn't guarantee that there are no clashes with rules in the same package.
+   *   <li>If possible, {@link #getPackageRelativeArtifact(PathFragment, Root)} should be used
+   *   instead of this method.
+   * </ul>
+   *
+   * Ideally, user-visible artifacts should all have corresponding output file targets, all others
+   * should go into a rule-specific directory.
+   * {@link #getUniqueDirectoryArtifact(String, PathFragment, Root)}) ensures that this is the case.
+   */
+  public PathFragment getPackageDirectory() {
+    return getLabel().getPackageIdentifier().getPathFragment();
+  }
+
+  /**
+   * Creates an artifact under a given root with the given root-relative path.
+   *
+   * <p>Verifies that it is in the root-relative directory corresponding to the package of the rule,
+   * thus ensuring that it doesn't clash with other artifacts generated by other rules using this
+   * method.
+   */
+  public Artifact getDerivedArtifact(PathFragment rootRelativePath, Root root) {
+    Preconditions.checkState(rootRelativePath.startsWith(getPackageDirectory()),
+        "Output artifact '%s' not under package directory '%s' for target '%s'",
+        rootRelativePath, getPackageDirectory(), getLabel());
+    return getAnalysisEnvironment().getDerivedArtifact(rootRelativePath, root);
+  }
+  /**
+   * Creates an artifact in a directory that is unique to the rule, thus guaranteeing that it never
+   * clashes with artifacts created by other rules.
+   */
+  public Artifact getUniqueDirectoryArtifact(
+      String uniqueDirectory, String relative, Root root) {
+    return getUniqueDirectoryArtifact(uniqueDirectory, new PathFragment(relative), root);
+  }
+
+  public Artifact getUniqueDirectoryArtifact(
+      String uniqueDirectory, PathFragment relative, Root root) {
+    return getDerivedArtifact(getUniqueDirectory(uniqueDirectory).getRelative(relative), root);
+  }
+
+  public PathFragment getArtifactPackagePrefix() {
+    return getLabel().getPackageIdentifier().getPathFragment();
+  }
+
   private Attribute getAttribute(String attributeName) {
     // TODO(bazel-team): We should check original rule for such attribute first, because aspect
     // can't contain empty attribute. Consider changing type of prerequisiteMap from
@@ -982,9 +1051,7 @@
    * Only use from Skylark. Returns the implicit output artifact for a given output path.
    */
   public Artifact getImplicitOutputArtifact(String path) {
-    Root root = getBinOrGenfilesDirectory();
-    PathFragment packageFragment = getLabel().getPackageFragment();
-    return getAnalysisEnvironment().getDerivedArtifact(packageFragment.getRelative(path), root);
+    return getPackageRelativeArtifact(path, getBinOrGenfilesDirectory());
   }
 
   /**
@@ -1061,7 +1128,7 @@
    */
   public final Artifact getRelatedArtifact(PathFragment pathFragment, String extension) {
     PathFragment file = FileSystemUtils.replaceExtension(pathFragment, extension);
-    return getAnalysisEnvironment().getDerivedArtifact(file, getConfiguration().getBinDirectory());
+    return getDerivedArtifact(file, getConfiguration().getBinDirectory());
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
index dd91cfb..fcfce07 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RunfilesSupport.java
@@ -88,7 +88,7 @@
    */
   private RunfilesSupport(RuleContext ruleContext, Artifact executable, Runfiles runfiles,
       List<String> appendingArgs, boolean createSymlinks) {
-    owningExecutable = executable;
+    owningExecutable = Preconditions.checkNotNull(executable);
     this.createSymlinks = createSymlinks;
 
     // Adding run_under target to the runfiles manifest so it would become part
@@ -123,19 +123,6 @@
         .build();
   }
 
-  private RunfilesSupport(Runfiles runfiles, Artifact runfilesInputManifest,
-      Artifact runfilesManifest, Artifact runfilesMiddleman, Artifact sourcesManifest,
-      Artifact owningExecutable, boolean createSymlinks, ImmutableList<String> args) {
-    this.runfiles = runfiles;
-    this.runfilesInputManifest = runfilesInputManifest;
-    this.runfilesManifest = runfilesManifest;
-    this.runfilesMiddleman = runfilesMiddleman;
-    this.sourcesManifest = sourcesManifest;
-    this.owningExecutable = owningExecutable;
-    this.createSymlinks = createSymlinks;
-    this.args = args;
-  }
-
   /**
    * Returns the executable owning this RunfilesSupport. Only use from Skylark.
    */
@@ -149,10 +136,6 @@
    * returns null.
    */
   public PathFragment getRunfilesDirectoryExecPath() {
-    if (owningExecutable == null) {
-      return null;
-    }
-
     PathFragment executablePath = owningExecutable.getExecPath();
     return executablePath.getParentDirectory().getChild(
         executablePath.getBaseName() + RUNFILES_DIR_EXT);
@@ -181,14 +164,14 @@
     return runfilesInputManifest;
   }
 
-  private Artifact createRunfilesInputManifestArtifact(ActionConstructionContext context) {
+  private Artifact createRunfilesInputManifestArtifact(RuleContext context) {
     // The executable may be null for emptyRunfiles
     PathFragment relativePath = (owningExecutable != null)
         ? owningExecutable.getRootRelativePath()
-        : Util.getWorkspaceRelativePath(context.getRule());
+        : context.getPackageDirectory().getRelative(context.getLabel().getName());
     String basename = relativePath.getBaseName();
     PathFragment inputManifestPath = relativePath.replaceName(basename + ".runfiles_manifest");
-    return context.getAnalysisEnvironment().getDerivedArtifact(inputManifestPath,
+    return context.getDerivedArtifact(inputManifestPath,
         context.getConfiguration().getBinDirectory());
   }
 
@@ -259,7 +242,6 @@
 
   /**
    * Returns the Sources manifest.
-   * This may be null if the owningRule has no executable.
    */
   public Artifact getSourceManifest() {
     return sourcesManifest;
@@ -302,7 +284,7 @@
     PathFragment outputManifestPath = runfilesDir.getRelative("MANIFEST");
 
     BuildConfiguration config = context.getConfiguration();
-    Artifact outputManifest = context.getAnalysisEnvironment().getDerivedArtifact(
+    Artifact outputManifest = context.getDerivedArtifact(
         outputManifestPath, config.getBinDirectory());
     context.getAnalysisEnvironment().registerAction(new SymlinkTreeAction(
         context.getActionOwner(), inputManifest, outputManifest, /*filesetTree=*/false));
@@ -318,18 +300,14 @@
    */
   private Artifact createSourceManifest(ActionConstructionContext context, Runfiles runfiles) {
     // Put the sources only manifest next to the MANIFEST file but call it SOURCES.
-    PathFragment runfilesDir = getRunfilesDirectoryExecPath();
-    if (runfilesDir != null) {
-      PathFragment sourcesManifestPath = runfilesDir.getRelative("SOURCES");
-      Artifact sourceOnlyManifest = context.getAnalysisEnvironment().getDerivedArtifact(
-          sourcesManifestPath, context.getConfiguration().getBinDirectory());
-      context.getAnalysisEnvironment().registerAction(
-          SourceManifestAction.forRunfiles(
-              ManifestType.SOURCES_ONLY, context.getActionOwner(), sourceOnlyManifest, runfiles));
-      return sourceOnlyManifest;
-    } else {
-      return null;
-    }
+    PathFragment executablePath = owningExecutable.getRootRelativePath();
+    PathFragment sourcesManifestPath = executablePath.getParentDirectory().getChild(
+        executablePath.getBaseName() + ".runfiles.SOURCES");
+    Artifact sourceOnlyManifest = context.getDerivedArtifact(
+        sourcesManifestPath, context.getConfiguration().getBinDirectory());
+    context.getAnalysisEnvironment().registerAction(SourceManifestAction.forRunfiles(
+        ManifestType.SOURCES_ONLY, context.getActionOwner(), sourceOnlyManifest, runfiles));
+    return sourceOnlyManifest;
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/ActionConstructionContext.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/ActionConstructionContext.java
index b7461e5..71261a7 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/ActionConstructionContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/ActionConstructionContext.java
@@ -14,9 +14,12 @@
 package com.google.devtools.build.lib.analysis.actions;
 
 import com.google.devtools.build.lib.actions.ActionOwner;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.analysis.AnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.vfs.PathFragment;
 
 /**
  * A temporary interface to allow migration from RuleConfiguredTarget to RuleContext. It bundles
@@ -34,4 +37,13 @@
 
   /** The current analysis environment. */
   AnalysisEnvironment getAnalysisEnvironment();
+
+  /**
+   * Creates an artifact under a given root with the given root-relative path.
+   *
+   * <p>Verifies that it is in the root-relative directory corresponding to the package of the rule,
+   * thus ensuring that it doesn't clash with other artifacts generated by other rules using this
+   * method.
+   */
+  Artifact getDerivedArtifact(PathFragment rootRelativePath, Root root);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
index 1128617..4ffaa92 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
@@ -135,9 +135,8 @@
    */
   public static Artifact createFile(RuleContext ruleContext,
       String fileName, CharSequence contents, boolean executable) {
-    Artifact scriptFileArtifact = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-        ruleContext.getTarget().getLabel().getPackageFragment().getRelative(fileName),
-        ruleContext.getConfiguration().getGenfilesDirectory());
+    Artifact scriptFileArtifact = ruleContext.getPackageRelativeArtifact(
+        fileName, ruleContext.getConfiguration().getGenfilesDirectory());
     ruleContext.registerAction(new FileWriteAction(
         ruleContext.getActionOwner(), scriptFileArtifact, contents, executable));
     return scriptFileArtifact;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
index 45d64f0..6864e44 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
@@ -398,22 +398,13 @@
 
   @SkylarkCallable(doc = "Creates a file object with the given filename. " + DOC_NEW_FILE_TAIL)
   public Artifact newFile(String filename) {
-    PathFragment fragment = ruleContext.getLabel().getPackageFragment();
-    for (String pathFragmentString : filename.split("/")) {
-      fragment = fragment.getRelative(pathFragmentString);
-    }
-    Root root = ruleContext.getBinOrGenfilesDirectory();
-    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(fragment, root);
+    return newFile(ruleContext.getBinOrGenfilesDirectory(), filename);
   }
 
   // Kept for compatibility with old code.
   @SkylarkCallable(documented = false)
   public Artifact newFile(Root root, String filename) {
-    PathFragment fragment = ruleContext.getLabel().getPackageFragment();
-    for (String pathFragmentString : filename.split("/")) {
-      fragment = fragment.getRelative(pathFragmentString);
-    }
-    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(fragment, root);
+    return ruleContext.getPackageRelativeArtifact(filename, root);
   }
 
   @SkylarkCallable(doc =
@@ -429,7 +420,7 @@
     PathFragment original = baseArtifact.getRootRelativePath();
     PathFragment fragment = original.replaceName(original.getBaseName() + suffix);
     Root root = ruleContext.getBinOrGenfilesDirectory();
-    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(fragment, root);
+    return ruleContext.getDerivedArtifact(fragment, root);
   }
 
   // Kept for compatibility with old code.
@@ -437,7 +428,7 @@
   public Artifact newFile(Root root, Artifact baseArtifact, String suffix) {
     PathFragment original = baseArtifact.getRootRelativePath();
     PathFragment fragment = original.replaceName(original.getBaseName() + suffix);
-    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(fragment, root);
+    return ruleContext.getDerivedArtifact(fragment, root);
   }
 
   @SkylarkCallable(documented = false)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
index e7c2fa5..87d2253 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
@@ -56,7 +56,6 @@
 import com.google.devtools.build.lib.rules.java.JavaCompilationArgsProvider;
 import com.google.devtools.build.lib.rules.java.JavaSemantics;
 import com.google.devtools.build.lib.rules.java.JavaTargetAttributes;
-import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.ArrayList;
 import java.util.LinkedHashMap;
@@ -791,8 +790,8 @@
   static DexingOutput dex(RuleContext ruleContext, MultidexMode multidexMode, List<String> dexopts,
       Artifact deployJar,  Artifact proguardedJar, AndroidCommon common,
       JavaTargetAttributes attributes) {
-    Artifact classesDex = AndroidBinary.getDxArtifact(ruleContext,
-        getMultidexMode(ruleContext).getOutputDexFilename());
+    String classesDexFileName = getMultidexMode(ruleContext).getOutputDexFilename();
+    Artifact classesDex = AndroidBinary.getDxArtifact(ruleContext, classesDexFileName);
     if (!AndroidBinary.supportsMultidexMode(ruleContext, multidexMode)) {
       ruleContext.ruleError("Multidex mode \"" + multidexMode.getAttributeValue()
           + "\" not supported by this version of the Android SDK");
@@ -904,10 +903,9 @@
         return new DexingOutput(classesDex, javaResourceJar, shardDexes);
       } else {
         // Create an artifact for the intermediate zip output that includes non-.dex files.
-        PathFragment dexPath = classesDex.getRootRelativePath();
-        Artifact classesDexIntermediate = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-            dexPath.getParentDirectory().getRelative("intermediate_" + dexPath.getBaseName()),
-            ruleContext.getBinOrGenfilesDirectory());
+        Artifact classesDexIntermediate = AndroidBinary.getDxArtifact(
+            ruleContext,
+            "intermediate_" + classesDexFileName);
 
         // Have the dexer generate the intermediate file and the "cleaner" action consume this to
         // generate the final archive with only .dex files.
@@ -1255,8 +1253,7 @@
    * Returns an intermediate artifact used to support dex generation.
    */
   public static Artifact getDxArtifact(RuleContext ruleContext, String baseName) {
-    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-        ruleContext.getUniqueDirectory("_dx").getRelative(baseName),
+    return ruleContext.getUniqueDirectoryArtifact("_dx", baseName,
         ruleContext.getBinOrGenfilesDirectory());
   }
 
@@ -1266,11 +1263,10 @@
   public static Artifact getProguardConfigArtifact(RuleContext ruleContext, String prefix) {
     // TODO(bazel-team): Remove the redundant inclusion of the rule name, as getUniqueDirectory
     // includes the rulename as well.
-    return Preconditions.checkNotNull(
-        ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-            ruleContext.getUniqueDirectory("proguard").getRelative(
-                Joiner.on("_").join(prefix, ruleContext.getLabel().getName(), "proguard.cfg")),
-            ruleContext.getBinOrGenfilesDirectory()));
+    return Preconditions.checkNotNull(ruleContext.getUniqueDirectoryArtifact(
+        "proguard",
+        Joiner.on("_").join(prefix, ruleContext.getLabel().getName(), "proguard.cfg"),
+        ruleContext.getBinOrGenfilesDirectory()));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
index a34cb55..e5bc26c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidCommon.java
@@ -300,12 +300,9 @@
     // Since the Java sources are generated by combining all resources with the
     // ones included in the binary, the path of the artifact has to be unique
     // per binary and per library (not only per library).
-    PathFragment resourceJarsPathFragment = ruleContext.getUniqueDirectory("resource_jars");
-    PathFragment artifactPathFragment = resourceJarsPathFragment.getRelative(
-        container.getLabel().getPackageFragment().getRelative(artifactName));
-
-    Artifact artifact = ruleContext.getAnalysisEnvironment()
-        .getDerivedArtifact(artifactPathFragment, ruleContext.getBinOrGenfilesDirectory());
+    Artifact artifact = ruleContext.getUniqueDirectoryArtifact("resource_jars",
+        container.getLabel().getPackageIdentifier().getPathFragment().getRelative(artifactName),
+        ruleContext.getBinOrGenfilesDirectory());
     return artifact;
   }
 
@@ -647,16 +644,15 @@
   private ImmutableMap<Artifact, Artifact> generateTranslatedIdlArtifacts(
       RuleContext ruleContext, Collection<Artifact> idls) {
     ImmutableMap.Builder<Artifact, Artifact> outputJavaSources = ImmutableMap.builder();
-    PathFragment rulePackage = ruleContext.getRule().getLabel().getPackageFragment();
     String ruleName = ruleContext.getRule().getName();
     // for each aidl file use aggregated preprocessed files to generate Java code
     for (Artifact idl : idls) {
       // Reconstruct the package tree under <rule>_aidl to avoid a name conflict
       // if the same AIDL files are used in multiple targets.
       PathFragment javaOutputPath = FileSystemUtils.replaceExtension(
-          rulePackage.getRelative(ruleName + "_aidl").getRelative(idl.getRootRelativePath()),
+          new PathFragment(ruleName + "_aidl").getRelative(idl.getRootRelativePath()),
           ".java");
-      Artifact output = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
+      Artifact output = ruleContext.getPackageRelativeArtifact(
           javaOutputPath, ruleContext.getConfiguration().getGenfilesDirectory());
       outputJavaSources.put(idl, output);
     }
@@ -688,14 +684,13 @@
 
     // preprocess each aidl file
     preprocessedArgs.add("-p" + sdk.getFrameworkAidl().getExecPathString());
-    PathFragment rulePackage = ruleContext.getRule().getLabel().getPackageFragment();
     String ruleName = ruleContext.getRule().getName();
     for (Artifact idl : idls) {
       // Reconstruct the package tree under <rule>_aidl to avoid a name conflict
       // if the source AIDL files are also generated.
-      PathFragment preprocessedPath = rulePackage.getRelative(ruleName + "_aidl")
+      PathFragment preprocessedPath = new PathFragment(ruleName + "_aidl")
           .getRelative(idl.getRootRelativePath());
-      Artifact preprocessed = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
+      Artifact preprocessed = ruleContext.getPackageRelativeArtifact(
           preprocessedPath, ruleContext.getConfiguration().getGenfilesDirectory());
       preprocessedIdls.add(preprocessed);
       preprocessedArgs.add("-p" + preprocessed.getExecPathString());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibrary.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibrary.java
index fa40809..010fa48 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidLibrary.java
@@ -378,9 +378,10 @@
       for (Artifact specToValidate : getProguardConfigs(ruleContext)) {
         //If we're validating j/a/b/testapp/proguard.cfg, the output will be:
         //j/a/b/testapp/proguard.cfg_valid
-        Artifact output = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-            specToValidate.getRootRelativePath()
-                .replaceName(specToValidate.getFilename() + "_valid"),
+        Artifact output = ruleContext.getUniqueDirectoryArtifact(
+            "validated_proguard",
+            specToValidate.getRootRelativePath().replaceName(
+                specToValidate.getFilename() + "_valid"),
             ruleContext.getBinOrGenfilesDirectory());
         ruleContext.registerAction(new SpawnAction.Builder()
             .addInput(specToValidate)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ApplicationManifest.java b/src/main/java/com/google/devtools/build/lib/rules/android/ApplicationManifest.java
index a379cc0..e1f84e7 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ApplicationManifest.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ApplicationManifest.java
@@ -35,6 +35,7 @@
 import com.google.devtools.build.lib.rules.android.LocalResourceContainer.Builder.InvalidAssetPath;
 import com.google.devtools.build.lib.rules.android.LocalResourceContainer.Builder.InvalidResourcePath;
 import com.google.devtools.build.lib.rules.java.JavaUtil;
+import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.List;
 
@@ -145,9 +146,8 @@
    * @return the generated ApplicationManifest
    */
   public static ApplicationManifest generatedManifest(RuleContext ruleContext) {
-    Artifact generatedManifest = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-        ruleContext.getUniqueDirectory(ruleContext.getRule().getName() + "_generated")
-            .getChild("AndroidManifest.xml"),
+    Artifact generatedManifest = ruleContext.getUniqueDirectoryArtifact(
+        ruleContext.getRule().getName() + "_generated", new PathFragment("AndroidManifest.xml"),
         ruleContext.getBinOrGenfilesDirectory());
 
     String manifestPackage;
@@ -179,9 +179,8 @@
       Iterable<ResourceContainer> resourceContainers) {
     if (!Iterables.isEmpty(getMergeeManifests(resourceContainers))) {
       Iterable<Artifact> exportedManifests = getMergeeManifests(resourceContainers);
-      Artifact outputManifest = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-          ruleContext.getUniqueDirectory(
-              ruleContext.getRule().getName() + "_merged").getChild("AndroidManifest.xml"),
+      Artifact outputManifest = ruleContext.getUniqueDirectoryArtifact(
+          ruleContext.getRule().getName() + "_merged", "AndroidManifest.xml",
           ruleContext.getBinOrGenfilesDirectory());
       AndroidManifestMergeHelper.createMergeManifestAction(ruleContext, getManifest(),
           exportedManifests, ImmutableList.of("all"), outputManifest);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java
index d8377d2..de9c089 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/JackCompilationHelper.java
@@ -57,6 +57,10 @@
  */
 public final class JackCompilationHelper {
 
+  private static final String PARTIAL_JACK_DIRECTORY = "_jill";
+
+  private static final String JACK_DIRECTORY = "_jack";
+
   /** Filetype for the intermediate library created by Jack. */
   public static final FileType JACK_LIBRARY_TYPE = FileType.of(".jack");
 
@@ -366,13 +370,10 @@
    * @see #postprocessPartialJackAndAddResources(Artifact,Artifact)
    */
   private Artifact convertJarToPartialJack(Artifact jar) {
-    PathFragment outputPath =
-        FileSystemUtils.replaceExtension(
-            getPartialJackRoot().getRelative(jar.getRootRelativePath()), ".jack");
-    Artifact result =
-        ruleContext
-            .getAnalysisEnvironment()
-            .getDerivedArtifact(outputPath, ruleContext.getBinOrGenfilesDirectory());
+    Artifact result = ruleContext.getUniqueDirectoryArtifact(
+        PARTIAL_JACK_DIRECTORY,
+        FileSystemUtils.replaceExtension(jar.getRootRelativePath(), ".jack"),
+        ruleContext.getBinOrGenfilesDirectory());
     ruleContext.registerAction(
         new SpawnAction.Builder()
             .setExecutable(jillBinary)
@@ -391,13 +392,11 @@
    * non-resource files and returning a zip file containing only resources.
    */
   private Artifact extractResourcesFromJar(Artifact jar) {
-    PathFragment outputPath =
-        FileSystemUtils.replaceExtension(
-            getPartialJackRoot().getRelative(jar.getRootRelativePath()), "-resources.zip");
-    Artifact result =
-        ruleContext
-            .getAnalysisEnvironment()
-            .getDerivedArtifact(outputPath, ruleContext.getBinOrGenfilesDirectory());
+    Artifact result =  ruleContext.getUniqueDirectoryArtifact(
+        PARTIAL_JACK_DIRECTORY,
+        FileSystemUtils.replaceExtension(jar.getRootRelativePath(), "-resources.zip"),
+        ruleContext.getBinOrGenfilesDirectory());
+
     ruleContext.registerAction(
         new SpawnAction.Builder()
             .setExecutable(resourceExtractorBinary)
@@ -416,13 +415,11 @@
    */
   private Artifact postprocessPartialJackAndAddResources(
       Artifact partialJackLibrary, Artifact resources) {
-    PathFragment outputPath =
-        getFinalizedJackRoot()
-            .getRelative(partialJackLibrary.getRootRelativePath().relativeTo(getPartialJackRoot()));
-    Artifact result =
-        ruleContext
-            .getAnalysisEnvironment()
-            .getDerivedArtifact(outputPath, ruleContext.getBinOrGenfilesDirectory());
+    Artifact result = ruleContext.getUniqueDirectoryArtifact(
+        JACK_DIRECTORY,
+        partialJackLibrary.getRootRelativePath().relativeTo(
+            ruleContext.getUniqueDirectory(PARTIAL_JACK_DIRECTORY)),
+        ruleContext.getBinOrGenfilesDirectory());
     CustomCommandLine.Builder builder =
         CustomCommandLine.builder()
             // Have jack double-check its behavior and crash rather than producing invalid output
@@ -446,26 +443,6 @@
   }
 
   /**
-   * Creates an intermediate directory to store partially-converted Jack libraries.
-   *
-   * @see #convertJarToPartialJack(Artifact)
-   */
-  private PathFragment getPartialJackRoot() {
-    PathFragment rulePath = ruleContext.getLabel().toPathFragment();
-    return rulePath.replaceName(rulePath.getBaseName() + "_jill");
-  }
-
-  /**
-   * Creates an intermediate directory to store fully-converted Jack libraries.
-   *
-   * @see #postprocessPartialJackAndAddResources(Artifact,Artifact)
-   */
-  private PathFragment getFinalizedJackRoot() {
-    PathFragment rulePath = ruleContext.getLabel().toPathFragment();
-    return rulePath.replaceName(rulePath.getBaseName() + "_jack");
-  }
-
-  /**
    * Creates an action to build an empty jack library given by outputArtifact.
    */
   private void buildEmptyJackAction() {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java b/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
index 965106e..7c48f1b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
@@ -80,8 +80,8 @@
       // The native deps name file must be the only file in its directory because ApkBuilder does
       // not have an option to add a particular file to the .apk, only one to add every file in a
       // particular directory.
-      Artifact nativeDepsName = ruleContext.getAnalysisEnvironment().getDerivedArtifact(
-          ruleContext.getUniqueDirectory("nativedeps_filename").getRelative(nativeDepsFileName),
+      Artifact nativeDepsName = ruleContext.getUniqueDirectoryArtifact(
+          "nativedeps_filename", nativeDepsFileName,
           ruleContext.getBinOrGenfilesDirectory());
       ruleContext.registerAction(new FileWriteAction(ruleContext.getActionOwner(), nativeDepsName,
           anyNativeLibrary.getExecPath().getBaseName(), false));
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
index 55d65ef..326575c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcBinary.java
@@ -22,7 +22,6 @@
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ParameterFile;
-import com.google.devtools.build.lib.analysis.AnalysisEnvironment;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.OutputGroupProvider;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
@@ -32,7 +31,6 @@
 import com.google.devtools.build.lib.analysis.RunfilesProvider;
 import com.google.devtools.build.lib.analysis.RunfilesSupport;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
-import com.google.devtools.build.lib.analysis.Util;
 import com.google.devtools.build.lib.analysis.actions.FileWriteAction;
 import com.google.devtools.build.lib.analysis.actions.SpawnAction;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -191,8 +189,8 @@
     // linkopt "-shared", which causes the result of linking to be a shared
     // library. In this case, the name of the executable target should end
     // in ".so".
-    PathFragment executableName = Util.getWorkspaceRelativePath(
-        ruleContext.getTarget(), "", OsUtils.executableExtension());
+    PathFragment executableName = ruleContext.getPackageDirectory().getRelative(
+        ruleContext.getTarget().getName() +  OsUtils.executableExtension());
     CppLinkAction.Builder linkActionBuilder = determineLinkerArguments(
         ruleContext, common, cppConfiguration, ccCompilationOutputs,
         cppCompilationContext.getCompilationPrerequisites(), fake, executableName);
@@ -543,8 +541,7 @@
 
       for (SpawnAction.Builder packager : packagers) {
         Artifact intermediateOutput =
-            getIntermediateDwpFile(
-                context.getAnalysisEnvironment(), dwpOutput, intermediateDwpCount++);
+            getIntermediateDwpFile(context, dwpOutput, intermediateDwpCount++);
         context.registerAction(packager
             .addArgument("-o")
             .addOutputArgument(intermediateOutput)
@@ -574,14 +571,13 @@
   /**
    * Creates an intermediate dwp file keyed off the name and path of the final output.
    */
-  private static Artifact getIntermediateDwpFile(AnalysisEnvironment env, Artifact dwpOutput,
+  private static Artifact getIntermediateDwpFile(RuleContext ruleContext, Artifact dwpOutput,
       int orderNumber) {
     PathFragment outputPath = dwpOutput.getRootRelativePath();
     PathFragment intermediatePath =
         FileSystemUtils.appendWithoutExtension(outputPath, "-" + orderNumber);
-    return env.getDerivedArtifact(
-        outputPath.getParentDirectory().getRelative(
-            INTERMEDIATE_DWP_DIR + "/" + intermediatePath.getPathString()),
+    return ruleContext.getPackageRelativeArtifact(
+        new PathFragment(INTERMEDIATE_DWP_DIR + "/" + intermediatePath.getPathString()),
         dwpOutput.getRoot());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
index 6833e29..751be08 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
@@ -28,7 +28,6 @@
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
-import com.google.devtools.build.lib.analysis.Util;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.packages.RuleErrorConsumer;
@@ -41,7 +40,6 @@
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
 import com.google.devtools.build.lib.util.FileTypeSet;
 import com.google.devtools.build.lib.util.IncludeScanningUtil;
-import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.LipoMode;
 
@@ -303,11 +301,12 @@
    */
   public static PathFragment getLinkedFilename(RuleContext ruleContext,
       LinkTargetType linkType) {
-    PathFragment relativePath = Util.getWorkspaceRelativePath(ruleContext.getTarget());
-    PathFragment linkedFileName = (linkType == LinkTargetType.EXECUTABLE) ?
-        relativePath :
-        relativePath.replaceName("lib" + relativePath.getBaseName() + linkType.getExtension());
-    return linkedFileName;
+    PathFragment result =
+        ruleContext.getPackageDirectory().getRelative(ruleContext.getLabel().getName());
+    if (linkType != LinkTargetType.EXECUTABLE) {
+      result = result.replaceName("lib" + result.getBaseName() + linkType.getExtension());
+    }
+    return result;
   }
 
   /**
@@ -404,11 +403,10 @@
   public static CppModuleMap addCppModuleMapToContext(RuleContext ruleContext,
       CppCompilationContext.Builder contextBuilder) {
     // Create the module map artifact as a genfile.
-    PathFragment mapPath = FileSystemUtils.appendExtension(ruleContext.getLabel().toPathFragment(),
-        Iterables.getOnlyElement(CppFileTypes.CPP_MODULE_MAP.getExtensions()));
-    Artifact mapFile = ruleContext.getAnalysisEnvironment().getDerivedArtifact(mapPath,
-        ruleContext.getConfiguration().getGenfilesDirectory());
-    CppModuleMap moduleMap =
+    Artifact mapFile = ruleContext.getPackageRelativeArtifact(
+        ruleContext.getLabel().getName()
+            + Iterables.getOnlyElement(CppFileTypes.CPP_MODULE_MAP.getExtensions()),
+        ruleContext.getConfiguration().getGenfilesDirectory());    CppModuleMap moduleMap =
         new CppModuleMap(mapFile, ruleContext.getLabel().toString());
     contextBuilder.setCppModuleMap(moduleMap);
     return moduleMap;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java b/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java
index 2df7a8f..0856345 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java
@@ -18,7 +18,6 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.actions.Action;
-import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.CommandHelper;
 import com.google.devtools.build.lib.analysis.FilesToRunProvider;
@@ -77,14 +76,12 @@
   /**
    * Adds an extra_action to the action graph based on the action to shadow.
    */
-  public Collection<Artifact> addExtraAction(RuleContext owningRule,
-      Action actionToShadow) {
+  public Collection<Artifact> addExtraAction(RuleContext owningRule, Action actionToShadow) {
     Collection<Artifact> extraActionOutputs = new LinkedHashSet<>();
     Collection<Artifact> protoOutputs = new ArrayList<>();
     NestedSetBuilder<Artifact> extraActionInputs = NestedSetBuilder.stableOrder();
 
-    ActionOwner owner = actionToShadow.getOwner();
-    Label ownerLabel = owner.getLabel();
+    Label ownerLabel = owningRule.getLabel();
     if (requiresActionOutput) {
       extraActionInputs.addAll(actionToShadow.getOutputs());
     }
@@ -96,20 +93,20 @@
     for (String outputTemplate : outputTemplates) {
       // We create output for the extra_action based on the 'out_template' attribute.
       // See {link #getExtraActionOutputArtifact} for supported variables.
-      extraActionOutputs.add(getExtraActionOutputArtifact(owningRule, actionToShadow,
-          owner, outputTemplate));
+      extraActionOutputs.add(getExtraActionOutputArtifact(
+          owningRule, actionToShadow, outputTemplate));
     }
     // extra_action has no output, we need to create some dummy output to keep the build up-to-date.
     if (extraActionOutputs.isEmpty()) {
       createDummyOutput = true;
-      extraActionOutputs.add(getExtraActionOutputArtifact(owningRule, actionToShadow,
-          owner, "$(ACTION_ID).dummy"));
+      extraActionOutputs.add(getExtraActionOutputArtifact(
+          owningRule, actionToShadow, "$(ACTION_ID).dummy"));
     }
 
     // We generate a file containing a protocol buffer describing the action that is being shadowed.
     // It is up to each action being shadowed to decide what contents to store here.
-    Artifact extraActionInfoFile = getExtraActionOutputArtifact(owningRule, actionToShadow,
-        owner, "$(ACTION_ID).xa");
+    Artifact extraActionInfoFile = getExtraActionOutputArtifact(
+        owningRule, actionToShadow, "$(ACTION_ID).xa");
     owningRule.registerAction(new ExtraActionInfoFileWriteAction(
         actionToShadow.getOwner(), extraActionInfoFile, actionToShadow));
     extraActionInputs.add(extraActionInfoFile);
@@ -117,7 +114,7 @@
 
     // Expand extra_action specific variables from the provided command-line.
     // See {@link #createExpandedCommand} for list of supported variables.
-    String command = createExpandedCommand(owningRule, actionToShadow, owner, extraActionInfoFile);
+    String command = createExpandedCommand(owningRule, actionToShadow, extraActionInfoFile);
 
     Map<String, String> env = owningRule.getConfiguration().getDefaultShellEnvironment();
 
@@ -158,12 +155,12 @@
    * <build_path>/extra_actions/bar/baz/devtools/build/test_A41234.out
    */
   private String createExpandedCommand(RuleContext owningRule,
-      Action action, ActionOwner owner, Artifact extraActionInfoFile) {
+      Action action, Artifact extraActionInfoFile) {
     String realCommand = command.replace(
         "$(EXTRA_ACTION_FILE)", extraActionInfoFile.getExecPathString());
 
     for (String outputTemplate : outputTemplates) {
-      String outFile = getExtraActionOutputArtifact(owningRule, action, owner, outputTemplate)
+      String outFile = getExtraActionOutputArtifact(owningRule, action, outputTemplate)
         .getExecPathString();
       realCommand = realCommand.replace("$(output " + outputTemplate + ")", outFile);
     }
@@ -186,36 +183,38 @@
    *    expands to: output/configuration/extra_actions/\
    *      foo/bar/extra/foo/bar/4683026f7ac1dd1a873ccc8c3d764132.analysis
    */
-  private Artifact getExtraActionOutputArtifact(RuleContext owningRule, Action action,
-      ActionOwner owner, String template) {
-    String actionId = getActionId(owner, action);
+  private Artifact getExtraActionOutputArtifact(
+      RuleContext ruleContext, Action action, String template) {
+    String actionId = getActionId(ruleContext.getLabel(), action);
 
     template = template.replace("$(ACTION_ID)", actionId);
-    template = template.replace("$(OWNER_LABEL_DIGEST)", getOwnerDigest(owner));
+    template = template.replace("$(OWNER_LABEL_DIGEST)", getOwnerDigest(ruleContext));
 
-    PathFragment rootRelativePath = getRootRelativePath(template, owner);
-    return owningRule.getAnalysisEnvironment().getDerivedArtifact(rootRelativePath,
-        owningRule.getConfiguration().getOutputDirectory());
+    return getRootRelativePath(template, ruleContext);
   }
 
-  private PathFragment getRootRelativePath(String template, ActionOwner owner) {
-    PathFragment extraActionPackageFragment = label.getPackageFragment();
+  private Artifact getRootRelativePath(String template, RuleContext ruleContext) {
+    PathFragment extraActionPackageFragment = label.getPackageIdentifier().getPathFragment();
     PathFragment extraActionPrefix = extraActionPackageFragment.getRelative(label.getName());
-
-    PathFragment ownerFragment = owner.getLabel().getPackageFragment();
-    return new PathFragment("extra_actions").getRelative(extraActionPrefix)
-        .getRelative(ownerFragment).getRelative(template);
+    PathFragment rootRelativePath = new PathFragment("extra_actions")
+        .getRelative(extraActionPrefix)
+        .getRelative(ruleContext.getPackageDirectory())
+        .getRelative(template);
+    // We need to use getDerivedArtifact here because extra actions are at
+    // <EXTRA ACTION LABEL> / <RULE LABEL> instead of <RULE LABEL> / <EXTRA ACTION LABEL>. Bummer.
+    return ruleContext.getAnalysisEnvironment().getDerivedArtifact(rootRelativePath,
+        ruleContext.getConfiguration().getOutputDirectory());
   }
 
   /**
-   * Calculates a digest representing the owner label.  We use the digest instead of the
+   * Calculates a digest representing the rule context.  We use the digest instead of the
    * original value as the original value might lead to a filename that is too long.
    * By using a digest, tools can deterministically find all extra_action outputs for a given
    * target, without having to open every file in the package.
    */
-  private static String getOwnerDigest(ActionOwner owner) {
+  private static String getOwnerDigest(RuleContext ruleContext) {
     Fingerprint f = new Fingerprint();
-    f.addString(owner.getLabel().toString());
+    f.addString(ruleContext.getLabel().toString());
     return f.hexDigestAndReset();
   }
 
@@ -229,9 +228,9 @@
    * of a uniqueness guarantee.
    */
   @VisibleForTesting
-  public static String getActionId(ActionOwner owner, Action action) {
+  public static String getActionId(Label label, Action action) {
     Fingerprint f = new Fingerprint();
-    f.addString(owner.getLabel().toString());
+    f.addString(label.toString());
     f.addString(action.getKey());
     return f.hexDigestAndReset();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java
index a8c27bc..6c6020c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/BaseJavaCompilationHelper.java
@@ -146,7 +146,7 @@
       PathFragment ruleBase = ruleContext.getUniqueDirectory("_ijar");
       PathFragment artifactDirFragment = jar.getRootRelativePath().getParentDirectory();
       String ijarBasename = FileSystemUtils.removeExtension(jar.getFilename()) + "-ijar.jar";
-      return getAnalysisEnvironment().getDerivedArtifact(
+      return ruleContext.getDerivedArtifact(
           ruleBase.getRelative(artifactDirFragment).getRelative(ijarBasename),
           getConfiguration().getGenfilesDirectory());
     } else {
@@ -241,6 +241,6 @@
     PathFragment path = artifact.getRootRelativePath();
     String basename = FileSystemUtils.removeExtension(path.getBaseName()) + suffix;
     path = path.replaceName(prefix + basename);
-    return getAnalysisEnvironment().getDerivedArtifact(path, root);
+    return ruleContext.getDerivedArtifact(path, root);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
index edff523..f321d35 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
@@ -200,7 +200,7 @@
    */
   public Artifact createGensrcJar(@Nullable Artifact outputJar) {
     if (usesAnnotationProcessing()) {
-      return getAnalysisEnvironment().getDerivedArtifact(
+      return getRuleContext().getDerivedArtifact(
           FileSystemUtils.appendWithoutExtension(outputJar.getRootRelativePath(), "-gensrc"),
           outputJar.getRoot());
     } else {
@@ -224,7 +224,7 @@
    * @return The output artifact for the manifest proto emitted from JavaBuilder 
    */
   public Artifact createManifestProtoOutput(Artifact outputJar) {
-    return getAnalysisEnvironment().getDerivedArtifact(
+    return getRuleContext().getDerivedArtifact(
         FileSystemUtils.appendExtension(outputJar.getRootRelativePath(), "_manifest_proto"),
         outputJar.getRoot());
   }
@@ -276,7 +276,7 @@
       return null;
     }
 
-    outputDepsProtoArtifact = getAnalysisEnvironment().getDerivedArtifact(
+    outputDepsProtoArtifact = getRuleContext().getDerivedArtifact(
           FileSystemUtils.replaceExtension(outputJar.getRootRelativePath(), ".jdeps"),
           outputJar.getRoot());
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
index 474d210..9e87fb6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
@@ -35,6 +35,7 @@
 import com.google.devtools.build.lib.actions.Executor;
 import com.google.devtools.build.lib.actions.ParameterFile;
 import com.google.devtools.build.lib.actions.ResourceSet;
+import com.google.devtools.build.lib.actions.Root;
 import com.google.devtools.build.lib.actions.Spawn;
 import com.google.devtools.build.lib.actions.SpawnActionContext;
 import com.google.devtools.build.lib.actions.extra.ExtraActionInfo;
@@ -71,7 +72,6 @@
  */
 @ThreadCompatible
 public class JavaCompileAction extends AbstractAction {
-
   private static final String GUID = "786e174d-ed97-4e79-9f61-ae74430714cf";
 
   private static final ResourceSet LOCAL_RESOURCES =
@@ -694,11 +694,34 @@
   }
 
   /**
+   * Tells {@link Builder} how to create new artifacts. Is there so that {@link Builder} can be
+   * exercised in tests without creating a full {@link RuleContext}.
+   */
+  public interface ArtifactFactory {
+
+    /**
+     * Create an artifact with the specified root-relative path under the specified root.
+     */
+    Artifact create(PathFragment rootRelativePath, Root root);
+  }
+
+  @VisibleForTesting
+  public static ArtifactFactory createArtifactFactory(final AnalysisEnvironment env) {
+    return new ArtifactFactory() {
+      @Override
+      public Artifact create(PathFragment rootRelativePath, Root root) {
+        return env.getDerivedArtifact(rootRelativePath, root);
+      }
+    };
+  }
+
+  /**
    * Builder class to construct Java compile actions.
    */
   public static class Builder {
     private final ActionOwner owner;
     private final AnalysisEnvironment analysisEnvironment;
+    private final ArtifactFactory artifactFactory;
     private final BuildConfiguration configuration;
     private final JavaSemantics semantics;
 
@@ -740,9 +763,11 @@
      * Creates a Builder from an owner and a build configuration.
      */
     public Builder(ActionOwner owner, AnalysisEnvironment analysisEnvironment,
-        BuildConfiguration configuration, JavaSemantics semantics) {
+        ArtifactFactory artifactFactory, BuildConfiguration configuration,
+        JavaSemantics semantics) {
       this.owner = owner;
       this.analysisEnvironment = analysisEnvironment;
+      this.artifactFactory = artifactFactory;
       this.configuration = configuration;
       this.semantics = semantics;
     }
@@ -750,8 +775,15 @@
     /**
      * Creates a Builder from an owner and a build configuration.
      */
-    public Builder(RuleContext ruleContext, JavaSemantics semantics) {
-      this(ruleContext.getActionOwner(), ruleContext.getAnalysisEnvironment(),
+    public Builder(final RuleContext ruleContext, JavaSemantics semantics) {
+      this(ruleContext.getActionOwner(),
+          ruleContext.getAnalysisEnvironment(),
+          new ArtifactFactory() {
+            @Override
+            public Artifact create(PathFragment rootRelativePath, Root root) {
+              return ruleContext.getDerivedArtifact(rootRelativePath, root);
+            }
+          },
           ruleContext.getConfiguration(), semantics);
     }
 
@@ -787,7 +819,7 @@
       }
 
       if (paramFile == null) {
-        paramFile = analysisEnvironment.getDerivedArtifact(
+        paramFile = artifactFactory.create(
             ParameterFile.derivePath(outputJar.getRootRelativePath()),
             configuration.getBinDirectory());
       }
diff --git a/src/test/shell/bazel/local_repository_test.sh b/src/test/shell/bazel/local_repository_test.sh
index 77a5c41b..bde15c7 100755
--- a/src/test/shell/bazel/local_repository_test.sh
+++ b/src/test/shell/bazel/local_repository_test.sh
@@ -467,7 +467,7 @@
 EOF
   bazel fetch //external:best-turtle || fail "Fetch failed"
   bazel build //external:best-turtle &> $TEST_log || fail "First build failed"
-  assert_contains "Raphael" bazel-genfiles/tmnt
+  assert_contains "Raphael" bazel-genfiles/external/mutant/tmnt
 
   cat > mutant.BUILD <<EOF
 genrule(
@@ -478,7 +478,7 @@
 )
 EOF
   bazel build //external:best-turtle &> $TEST_log || fail "Second build failed"
-  assert_contains "Michaelangelo" bazel-genfiles/tmnt
+  assert_contains "Michaelangelo" bazel-genfiles/external/mutant/tmnt
 }
 
 function test_local_deps() {
diff --git a/src/test/shell/bazel/workspace_test.sh b/src/test/shell/bazel/workspace_test.sh
index 51abf7f..ec04ffc 100755
--- a/src/test/shell/bazel/workspace_test.sh
+++ b/src/test/shell/bazel/workspace_test.sh
@@ -48,7 +48,7 @@
 EOF
 
   bazel build @x//:x || fail "build failed"
-  assert_contains "hi" bazel-genfiles/out
+  assert_contains "hi" bazel-genfiles/external/x/out
 
   cat > WORKSPACE <<EOF
 local_repository(
@@ -58,7 +58,7 @@
 EOF
 
   bazel build @x//:x || fail "build failed"
-  assert_contains "bye" bazel-genfiles/out
+  assert_contains "bye" bazel-genfiles/external/x/out
 }