diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContextFactory.java b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContextFactory.java
index e87d72e..fd5f2dd 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContextFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionExecutionContextFactory.java
@@ -25,5 +25,5 @@
  */
 public interface ActionExecutionContextFactory {
   ActionExecutionContext getContext(ActionInputFileCache graphFileCache,
-      MetadataHandler metadataHandler, Map<Artifact, Collection<ArtifactFile>> expandedInputs);
+      MetadataHandler metadataHandler, Map<Artifact, Collection<Artifact>> expandedInputs);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java b/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java
index 4471c4c..a4a85d2 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionInputHelper.java
@@ -21,6 +21,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
+import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
@@ -41,7 +42,7 @@
       final ActionGraph actionGraph) {
     return new ArtifactExpander() {
       @Override
-      public void expand(Artifact mm, Collection<? super ArtifactFile> output) {
+      public void expand(Artifact mm, Collection<? super Artifact> output) {
         // Skyframe is stricter in that it checks that "mm" is a input of the action, because
         // it cannot expand arbitrary middlemen without access to a global action graph.
         // We could check this constraint here too, but it seems unnecessary. This code is
@@ -129,60 +130,57 @@
   }
 
   /**
-   * Instantiates a concrete ArtifactFile with the given parent Artifact and path
+   * Instantiates a concrete TreeFileArtifact with the given parent Artifact and path
    * relative to that Artifact.
    */
-  public static ArtifactFile artifactFile(Artifact parent, PathFragment relativePath) {
+  public static TreeFileArtifact treeFileArtifact(
+      Artifact parent, PathFragment relativePath) {
     Preconditions.checkState(parent.isTreeArtifact(),
         "Given parent %s must be a TreeArtifact", parent);
-    return new TreeArtifactFile(parent, relativePath);
+    return new TreeFileArtifact(parent, relativePath);
+  }
+
+  public static TreeFileArtifact treeFileArtifact(
+      Artifact parent, PathFragment relativePath, ArtifactOwner artifactOwner) {
+    Preconditions.checkState(parent.isTreeArtifact(),
+        "Given parent %s must be a TreeArtifact", parent);
+    return new TreeFileArtifact(
+        parent,
+        relativePath,
+        artifactOwner);
   }
 
   /**
-   * Instantiates a concrete ArtifactFile with the given parent Artifact and path
+   * Instantiates a concrete TreeFileArtifact with the given parent Artifact and path
    * relative to that Artifact.
    */
-  public static ArtifactFile artifactFile(Artifact parent, String relativePath) {
-    return artifactFile(parent, new PathFragment(relativePath));
+  public static TreeFileArtifact treeFileArtifact(Artifact parent, String relativePath) {
+    return treeFileArtifact(parent, new PathFragment(relativePath));
   }
 
-  /** Returns an Iterable of ArtifactFiles with the given parent and parent relative paths. */
-  public static Iterable<ArtifactFile> asArtifactFiles(
+  /** Returns an Iterable of TreeFileArtifacts with the given parent and parent relative paths. */
+  public static Iterable<TreeFileArtifact> asTreeFileArtifacts(
       final Artifact parent, Iterable<? extends PathFragment> parentRelativePaths) {
     Preconditions.checkState(parent.isTreeArtifact(),
         "Given parent %s must be a TreeArtifact", parent);
     return Iterables.transform(parentRelativePaths,
-        new Function<PathFragment, ArtifactFile>() {
+        new Function<PathFragment, TreeFileArtifact>() {
           @Override
-          public ArtifactFile apply(PathFragment pathFragment) {
-            return artifactFile(parent, pathFragment);
+          public TreeFileArtifact apply(PathFragment pathFragment) {
+            return treeFileArtifact(parent, pathFragment);
           }
         });
   }
 
-  /** Returns an Collection of ArtifactFiles with the given parent and parent-relative paths. */
-  public static Collection<ArtifactFile> asArtifactFiles(
-      final Artifact parent, Collection<? extends PathFragment> parentRelativePaths) {
-    Preconditions.checkState(parent.isTreeArtifact(),
-        "Given parent %s must be a TreeArtifact", parent);
-    return Collections2.transform(parentRelativePaths,
-        new Function<PathFragment, ArtifactFile>() {
-          @Override
-          public ArtifactFile apply(PathFragment pathFragment) {
-            return artifactFile(parent, pathFragment);
-          }
-        });
-  }
-
-  /** Returns a Set of ArtifactFiles with the given parent and parent relative paths. */
-  public static Set<ArtifactFile> asArtifactFiles(
+  /** Returns a Set of TreeFileArtifacts with the given parent and parent-relative paths. */
+  public static Set<TreeFileArtifact> asTreeFileArtifacts(
       final Artifact parent, Set<? extends PathFragment> parentRelativePaths) {
     Preconditions.checkState(parent.isTreeArtifact(),
         "Given parent %s must be a TreeArtifact", parent);
 
-    ImmutableSet.Builder<ArtifactFile> builder = ImmutableSet.builder();
+    ImmutableSet.Builder<TreeFileArtifact> builder = ImmutableSet.builder();
     for (PathFragment path : parentRelativePaths) {
-      builder.add(artifactFile(parent, path));
+      builder.add(treeFileArtifact(parent, path));
     }
 
     return builder.build();
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 4e8989f..f28683b 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
@@ -70,7 +70,7 @@
  * In the usual case, an Artifact represents a single file. However, an Artifact may
  * also represent the following:
  * <ul>
- * <li>A TreeArtifact, which is a directory containing a tree of unknown {@link ArtifactFile}s.
+ * <li>A TreeArtifact, which is a directory containing a tree of unknown {@link Artifact}s.
  * In the future, Actions will be able to examine these files as inputs and declare them as outputs
  * at execution time, but this is not yet implemented. This is used for Actions where
  * the inputs and/or outputs might not be discoverable except during Action execution.
@@ -87,8 +87,8 @@
  * by new rule implementations.
  * </ul>
  * <p/>
- * This class implements {@link ArtifactFile}, and is modeled as an Artifact "containing" itself
- * as an ArtifactFile.
+ * This class implements {@link Artifact}, and is modeled as an Artifact "containing" itself
+ * as an Artifact.
  * <p/>
  * <p>This class is "theoretically" final; it should not be subclassed except by
  * {@link SpecialArtifact}.
@@ -98,7 +98,7 @@
     doc = "This type represents a file used by the build system. It can be "
         + "either a source file or a derived file produced by a rule.")
 public class Artifact
-    implements FileType.HasFilename, ArtifactFile, SkylarkValue , Comparable<Object> {
+    implements FileType.HasFilename, ActionInput, SkylarkValue, Comparable<Object> {
 
   /**
    * Compares artifact according to their exec paths. Sorts null values first.
@@ -136,7 +136,7 @@
      * <p>{@code artifact.isMiddlemanArtifact() || artifact.isTreeArtifact()} must be true.
      * Only aggregating middlemen and tree artifacts are expanded.
      */
-    void expand(Artifact artifact, Collection<? super ArtifactFile> output);
+    void expand(Artifact artifact, Collection<? super Artifact> output);
   }
 
   public static final ImmutableList<Artifact> NO_ARTIFACTS = ImmutableList.of();
@@ -239,20 +239,20 @@
         root.getExecPath().getRelative(rootRelativePath), ArtifactOwner.NULL_OWNER);
   }
 
-  @Override
   public final Path getPath() {
     return path;
   }
 
+  public boolean hasParent() {
+    return getParent() != null;
+  }
+
   /**
-   * Returns the Artifact containing this ArtifactFile. Since normal Artifacts correspond
-   * to only one ArtifactFile -- itself -- for normal Artifacts, this method returns {@code this}.
-   * For special artifacts, throws {@link UnsupportedOperationException}.
-   * See also {@link ArtifactFile#getParent()}.
+   * Returns the parent Artifact containing this Artifact. Artifacts without parents shall
+   * return null.
    */
-  @Override
-  public Artifact getParent() throws UnsupportedOperationException {
-    return this;
+  @Nullable public Artifact getParent() {
+    return null;
   }
 
   /**
@@ -307,7 +307,6 @@
    * package-path entries (for source Artifacts), or one of the bin, genfiles or includes dirs
    * (for derived Artifacts). It will always be an ancestor of getPath().
    */
-  @Override
   @SkylarkCallable(name = "root", structField = true,
       doc = "The root beneath which this file resides."
   )
@@ -315,18 +314,16 @@
     return root;
   }
 
-  @Override
   public final PathFragment getExecPath() {
     return execPath;
   }
 
   /**
-   * Returns the path of this ArtifactFile relative to this containing Artifact. Since
-   * ordinary Artifacts correspond to only one ArtifactFile -- itself -- for ordinary Artifacts,
+   * Returns the path of this Artifact relative to this containing Artifact. Since
+   * ordinary Artifacts correspond to only one Artifact -- itself -- for ordinary Artifacts,
    * this just returns the empty path. For special Artifacts, throws
-   * {@link UnsupportedOperationException}. See also {@link ArtifactFile#getParentRelativePath()}.
+   * {@link UnsupportedOperationException}. See also {@link Artifact#getParentRelativePath()}.
    */
-  @Override
   public PathFragment getParentRelativePath() {
     return PathFragment.EMPTY_FRAGMENT;
   }
@@ -350,7 +347,7 @@
   }
 
   /**
-   * Returns true iff this is a TreeArtifact representing a directory tree containing ArtifactFiles.
+   * Returns true iff this is a TreeArtifact representing a directory tree containing Artifacts.
    */
   public boolean isTreeArtifact() {
     return false;
@@ -418,13 +415,77 @@
     }
 
     @Override
+    public boolean hasParent() {
+      return false;
+    }
+
+    @Override
+    @Nullable
     public Artifact getParent() {
-      throw new UnsupportedOperationException();
+      return null;
+    }
+
+    @Override
+    @Nullable
+    public PathFragment getParentRelativePath() {
+      return null;
+    }
+  }
+
+  /**
+   * A special kind of artifact that represents a concrete file created at execution time under
+   * its associated TreeArtifact.
+   *
+   * <p> TreeFileArtifacts should be only created during execution time inside some special actions
+   * to support action inputs and outputs that are unpredictable at analysis time.
+   * TreeFileArtifacts should not be created directly by any rules at analysis time.
+   *
+   * <p>We subclass {@link Artifact} instead of storing the extra fields directly inside in order
+   * to save memory. The proportion of TreeFileArtifacts is very small, and by not having to keep
+   * around the extra fields for the rest we save some memory.
+   */
+  @Immutable
+  public static final class TreeFileArtifact extends Artifact {
+    private final Artifact parentTreeArtifact;
+    private final PathFragment parentRelativePath;
+
+    /**
+     * Constructs a TreeFileArtifact with the given parent-relative path under the given parent
+     * TreeArtifact. The {@link ArtifactOwner} of the TreeFileArtifact is the {@link ArtifactOwner}
+     * of the parent TreeArtifact.
+     */
+    TreeFileArtifact(Artifact parent, PathFragment parentRelativePath) {
+      this(parent, parentRelativePath, parent.getArtifactOwner());
+    }
+
+    /**
+     * Constructs a TreeFileArtifact with the given parent-relative path under the given parent
+     * TreeArtifact, owned by the given {@code artifactOwner}.
+     */
+    TreeFileArtifact(Artifact parent, PathFragment parentRelativePath,
+        ArtifactOwner artifactOwner) {
+      super(
+          parent.getPath().getRelative(parentRelativePath),
+          parent.getRoot(),
+          parent.getExecPath().getRelative(parentRelativePath),
+          artifactOwner);
+      Preconditions.checkState(
+          parent.isTreeArtifact(),
+          "The parent of TreeFileArtifact (parent-relative path: %s) is not a TreeArtifact: %s",
+          parentRelativePath,
+          parent);
+      this.parentTreeArtifact = parent;
+      this.parentRelativePath = parentRelativePath;
+    }
+
+    @Override
+    public Artifact getParent() {
+      return parentTreeArtifact;
     }
 
     @Override
     public PathFragment getParentRelativePath() {
-      throw new UnsupportedOperationException();
+      return parentRelativePath;
     }
   }
 
@@ -432,7 +493,6 @@
    * Returns the relative path to this artifact relative to its root.  (Useful
    * when deriving output filenames from input files, etc.)
    */
-  @Override
   public final PathFragment getRootRelativePath() {
     return rootRelativePath;
   }
@@ -478,7 +538,6 @@
     return getRootRelativePath().getPathString();
   }
 
-  @Override
   public final String prettyPrint() {
     // toDetailString would probably be more useful to users, but lots of tests rely on the
     // current values.
@@ -550,26 +609,26 @@
   /**
    * Formatter for execPath PathFragment output.
    */
-  private static final Function<ArtifactFile, PathFragment> EXEC_PATH_FORMATTER =
-      new Function<ArtifactFile, PathFragment>() {
+  private static final Function<Artifact, PathFragment> EXEC_PATH_FORMATTER =
+      new Function<Artifact, PathFragment>() {
         @Override
-        public PathFragment apply(ArtifactFile input) {
+        public PathFragment apply(Artifact input) {
           return input.getExecPath();
         }
       };
 
-  public static final Function<ArtifactFile, String> ROOT_RELATIVE_PATH_STRING =
-      new Function<ArtifactFile, String>() {
+  public static final Function<Artifact, String> ROOT_RELATIVE_PATH_STRING =
+      new Function<Artifact, String>() {
         @Override
-        public String apply(ArtifactFile artifact) {
+        public String apply(Artifact artifact) {
           return artifact.getRootRelativePath().getPathString();
         }
       };
 
-  public static final Function<ArtifactFile, String> ABSOLUTE_PATH_STRING =
-      new Function<ArtifactFile, String>() {
+  public static final Function<Artifact, String> ABSOLUTE_PATH_STRING =
+      new Function<Artifact, String>() {
         @Override
-        public String apply(ArtifactFile artifact) {
+        public String apply(Artifact artifact) {
           return artifact.getPath().getPathString();
         }
       };
@@ -654,8 +713,8 @@
    * {@link MiddlemanType#AGGREGATING_MIDDLEMAN} middleman actions expanded once.
    */
   public static void addExpandedArtifacts(Iterable<Artifact> artifacts,
-      Collection<? super ArtifactFile> output, ArtifactExpander artifactExpander) {
-    addExpandedArtifacts(artifacts, output, Functions.<ArtifactFile>identity(), artifactExpander);
+      Collection<? super Artifact> output, ArtifactExpander artifactExpander) {
+    addExpandedArtifacts(artifacts, output, Functions.<Artifact>identity(), artifactExpander);
   }
 
   /**
@@ -690,7 +749,7 @@
    */
   private static <E> void addExpandedArtifacts(Iterable<? extends Artifact> artifacts,
                                                Collection<? super E> output,
-                                               Function<? super ArtifactFile, E> outputFormatter,
+                                               Function<? super Artifact, E> outputFormatter,
                                                ArtifactExpander artifactExpander) {
     for (Artifact artifact : artifacts) {
       if (artifact.isMiddlemanArtifact() || artifact.isTreeArtifact()) {
@@ -703,12 +762,12 @@
 
   private static <E> void expandArtifact(Artifact middleman,
       Collection<? super E> output,
-      Function<? super ArtifactFile, E> outputFormatter,
+      Function<? super Artifact, E> outputFormatter,
       ArtifactExpander artifactExpander) {
     Preconditions.checkArgument(middleman.isMiddlemanArtifact() || middleman.isTreeArtifact());
-    List<ArtifactFile> artifacts = new ArrayList<>();
+    List<Artifact> artifacts = new ArrayList<>();
     artifactExpander.expand(middleman, artifacts);
-    for (ArtifactFile artifact : artifacts) {
+    for (Artifact artifact : artifacts) {
       output.add(outputFormatter.apply(artifact));
     }
   }
@@ -785,7 +844,7 @@
   /**
    * Converts artifacts into their exec paths. Returns an immutable list.
    */
-  public static List<PathFragment> asPathFragments(Iterable<? extends ArtifactFile> artifacts) {
+  public static List<PathFragment> asPathFragments(Iterable<? extends Artifact> artifacts) {
     return ImmutableList.copyOf(Iterables.transform(artifacts, EXEC_PATH_FORMATTER));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFile.java b/src/main/java/com/google/devtools/build/lib/actions/ArtifactFile.java
deleted file mode 100644
index be165fb..0000000
--- a/src/main/java/com/google/devtools/build/lib/actions/ArtifactFile.java
+++ /dev/null
@@ -1,115 +0,0 @@
-// Copyright 2016 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.
-
-package com.google.devtools.build.lib.actions;
-
-import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.lib.vfs.PathFragment;
-
-/**
- * An ArtifactFile represents a file used by the build system during execution of Actions.
- * An ArtifactFile may be a source file or a derived (output) file.
- *
- * During the creation of {@link com.google.devtools.build.lib.analysis.ConfiguredTarget}s and
- * {@link com.google.devtools.build.lib.analysis.ConfiguredAspect}s, generally one
- * is only interested in {@link Artifact}s. Most Actions are only interested in Artifacts as well.
- * During action execution, however, some Artifacts (notably
- * TreeArtifacts) may correspond to more than one ArtifactFile. This is for the benefit
- * of some Actions which only know their inputs or outputs at execution time, via the
- * TreeArtifact mechanism.
- * <ul><li>
- *   Generally, most Artifacts represent a file on the filesystem, and correspond to exactly one
- *   ArtifactFile. For ease of use, Artifact itself implements ArtifactFile, and is modeled
- *   as an Artifact containing itself.
- * </li><li>
- *   Some Artifacts are so-called TreeArtifacts, for which the method
- *   {@link Artifact#isTreeArtifact()} returns true. These artifacts contain a (possibly empty)
- *   tree of ArtifactFiles, which are unknown until Action execution time.
- * </li><li>
- *   Some 'special artifacts' do not meaningfully represent a file or tree of files.
- * </li></ul>
- */
-public interface ArtifactFile extends ActionInput {
-  /**
-   * Returns the exec path of this ArtifactFile. The exec path is a relative path
-   * that is suitable for accessing this artifact relative to the execution
-   * directory for this build.
-   */
-  PathFragment getExecPath();
-
-  /**
-   * Returns the path of this ArtifactFile relative to its containing Artifact.
-   * See {@link #getParent()}.
-   * */
-  PathFragment getParentRelativePath();
-
-  /** Returns the location of this ArtifactFile on the filesystem. */
-  Path getPath();
-
-  /**
-   * Returns the relative path to this ArtifactFile relative to its root. Useful
-   * when deriving output filenames from input files, etc.
-   */
-  PathFragment getRootRelativePath();
-
-  /**
-   * Returns the root beneath which this ArtifactFile resides, if any. This may be one of the
-   * package-path entries (for files belonging to source {@link Artifact}s), or one of the bin
-   * genfiles or includes dirs (for files belonging to derived {@link Artifact}s). It will always be
-   * an ancestor of {@link #getPath()}.
-   */
-  Root getRoot();
-
-  /**
-   * Returns the Artifact containing this File. For Artifacts which are files, returns
-   * {@code this}. Otherwise, returns a Artifact whose path and root relative path
-   * are an ancestor of this ArtifactFile's path, and for which {@link Artifact#isTreeArtifact()}
-   * returns true.
-   * <p/>
-   * For ArtifactFiles which are special artifacts (including TreeArtifacts),
-   * this method throws UnsupportedOperationException, because the ArtifactFile abstraction
-   * fails for those cases.
-   */
-  Artifact getParent() throws UnsupportedOperationException;
-
-  /**
-   * Returns a pretty string representation of the path denoted by this ArtifactFile, suitable for
-   * use in user error messages. ArtifactFiles beneath a root will be printed relative to that root;
-   * other ArtifactFiles will be printed as an absolute path.
-   *
-   * <p>(The toString method is intended for developer messages since its more informative.)
-   */
-  String prettyPrint();
-
-  /**
-   * Two ArtifactFiles are equal if their parent Artifacts and parent relative paths
-   * are equal. If this ArtifactFile is itself an Artifact, see {@link Artifact#equals(Object)}.
-   * Note that within a build, two ArtifactFiles produced by the build system will be equal
-   * if and only if their full paths are equal.
-   */
-  @Override
-  boolean equals(Object o);
-
-  /**
-   * An ArtifactFile's hash code should be equal to
-   * {@code {@link #getParent().hashCode()} * 257 +
-   * {@link #getParentRelativePath().hashCode()}}. If this ArtifactFile is itself an Artifact,
-   * see {@link Artifact#hashCode()}.
-   * <p/>
-   * 257 is chosen because it is a Fermat prime, and has minimal 'bit overlap' with the Mersenne
-   * prime of 31 used in {@link Path#hashCode()} and {@link String#hashCode()}.
-   */
-  @Override
-  int hashCode();
-}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/TreeArtifactFile.java b/src/main/java/com/google/devtools/build/lib/actions/TreeArtifactFile.java
deleted file mode 100644
index 8b4cde8..0000000
--- a/src/main/java/com/google/devtools/build/lib/actions/TreeArtifactFile.java
+++ /dev/null
@@ -1,92 +0,0 @@
-// Copyright 2016 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.
-
-package com.google.devtools.build.lib.actions;
-
-import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.vfs.Path;
-import com.google.devtools.build.lib.vfs.PathFragment;
-
-/** An ArtifactFile implementation for descendants of TreeArtifacts. */
-final class TreeArtifactFile implements ArtifactFile {
-  private final Artifact parent;
-  private final PathFragment parentRelativePath;
-
-  TreeArtifactFile(Artifact parent, PathFragment parentRelativePath) {
-    Preconditions.checkArgument(parent.isTreeArtifact(), "%s must be a TreeArtifact", parent);
-    this.parent = parent;
-    this.parentRelativePath = parentRelativePath;
-  }
-
-  @Override
-  public PathFragment getExecPath() {
-    return parent.getExecPath().getRelative(parentRelativePath);
-  }
-
-  @Override
-  public PathFragment getParentRelativePath() {
-    return parentRelativePath;
-  }
-
-  @Override
-  public Path getPath() {
-    return parent.getPath().getRelative(parentRelativePath);
-  }
-
-  @Override
-  public PathFragment getRootRelativePath() {
-    return parent.getRootRelativePath().getRelative(parentRelativePath);
-  }
-
-  @Override
-  public Root getRoot() {
-    return parent.getRoot();
-  }
-
-  @Override
-  public Artifact getParent() {
-    return parent;
-  }
-
-  @Override
-  public String prettyPrint() {
-    return getRootRelativePath().toString();
-  }
-
-  @Override
-  public String getExecPathString() {
-    return getExecPath().toString();
-  }
-
-  @Override
-  public String toString() {
-    return "ArtifactFile:[" + parent.toDetailString() + "]" + parentRelativePath;
-  }
-
-  @Override
-  public boolean equals(Object other) {
-    if (!(other instanceof ArtifactFile)) {
-      return false;
-    }
-
-    ArtifactFile that = (ArtifactFile) other;
-    return this.getParent().equals(that.getParent())
-        && this.getParentRelativePath().equals(that.getParentRelativePath());
-  }
-
-  @Override
-  public int hashCode() {
-    return getParent().hashCode() * 257 + getParentRelativePath().hashCode();
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
index e75ab9a..6fcb964 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/MetadataHandler.java
@@ -15,7 +15,7 @@
 
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactFile;
+import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.MiddlemanAction;
 import com.google.devtools.build.lib.vfs.FileStatus;
 
@@ -52,9 +52,8 @@
   /**
    * Registers the given output as contents of a TreeArtifact, without injecting its digest.
    * Prefer {@link #injectDigest} when the digest is available.
-   * @throws IllegalStateException if the given output does not have a TreeArtifact parent.
    */
-  void addExpandedTreeOutput(ArtifactFile output) throws IllegalStateException;
+  void addExpandedTreeOutput(TreeFileArtifact output);
 
   /**
    * Injects provided digest into the metadata handler, simultaneously caching lstat() data as well.
@@ -83,14 +82,14 @@
   boolean artifactOmitted(Artifact artifact);
 
   /**
-   * @return Whether the ArtifactFile's data was injected.
-   * @throws IOException if implementation tried to stat the ArtifactFile which threw an exception.
+   * @return Whether the artifact's data was injected.
+   * @throws IOException if implementation tried to stat the Artifact which threw an exception.
    *         Technically, this means that the artifact could not have been injected, but by throwing
    *         here we save the caller trying to stat this file on their own and throwing the same
    *         exception. Implementations are not guaranteed to throw in this case if they are able to
    *         determine that the artifact is not injected without statting it.
    */
-  boolean isInjected(ArtifactFile file) throws IOException;
+  boolean isInjected(Artifact file) throws IOException;
 
   /**
    * Discards all known output artifact metadata, presumably because outputs will be modified.
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 986dacc..04b862c 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
@@ -28,7 +28,6 @@
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
-import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.actions.ArtifactResolver;
 import com.google.devtools.build.lib.actions.ExecException;
 import com.google.devtools.build.lib.actions.Executor;
@@ -730,7 +729,7 @@
       throws ActionExecutionException {
     IncludeProblems errors = new IncludeProblems();
     IncludeProblems warnings = new IncludeProblems();
-    Set<ArtifactFile> allowedIncludes = new HashSet<>();
+    Set<Artifact> allowedIncludes = new HashSet<>();
     for (Artifact input : mandatoryInputs) {
       if (input.isMiddlemanArtifact() || input.isTreeArtifact()) {
         artifactExpander.expand(input, allowedIncludes);
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 963fe1d..e821976 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
@@ -16,6 +16,7 @@
 import com.google.common.base.Function;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
@@ -27,7 +28,6 @@
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.AlreadyReportedActionExecutionException;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.actions.MissingInputFileException;
 import com.google.devtools.build.lib.actions.NotifyOnActionCacheHit;
 import com.google.devtools.build.lib.actions.PackageRootResolutionException;
@@ -127,7 +127,7 @@
       env.getValues(state.allInputs.keysRequested);
       Preconditions.checkState(!env.valuesMissing(), "%s %s", action, state);
     }
-    Pair<Map<Artifact, FileArtifactValue>, Map<Artifact, Collection<ArtifactFile>>> checkedInputs =
+    Pair<Map<Artifact, FileArtifactValue>, Map<Artifact, Collection<Artifact>>> checkedInputs =
         null;
     try {
       // Declare deps on known inputs to action. We do this unconditionally to maintain our
@@ -346,7 +346,7 @@
     if (state.token == null) {
       // We got a hit from the action cache -- no need to execute.
       return new ActionExecutionValue(
-          metadataHandler.getOutputArtifactFileData(),
+          metadataHandler.getOutputArtifactData(),
           metadataHandler.getOutputTreeArtifactData(),
           metadataHandler.getAdditionalOutputData());
     }
@@ -531,7 +531,7 @@
    * Declare dependency on all known inputs of action. Throws exception if any are known to be
    * missing. Some inputs may not yet be in the graph, in which case the builder should abort.
    */
-  private Pair<Map<Artifact, FileArtifactValue>, Map<Artifact, Collection<ArtifactFile>>>
+  private Pair<Map<Artifact, FileArtifactValue>, Map<Artifact, Collection<Artifact>>>
   checkInputs(Environment env, Action action,
       Map<SkyKey, ValueOrException2<MissingInputFileException, ActionExecutionException>> inputDeps)
       throws ActionExecutionException {
@@ -546,7 +546,7 @@
     NestedSetBuilder<Label> rootCauses = NestedSetBuilder.stableOrder();
     Map<Artifact, FileArtifactValue> inputArtifactData =
         new HashMap<>(populateInputData ? inputDeps.size() : 0);
-    Map<Artifact, Collection<ArtifactFile>> expandedArtifacts =
+    Map<Artifact, Collection<Artifact>> expandedArtifacts =
         new HashMap<>(populateInputData ? 128 : 0);
 
     ActionExecutionException firstActionExecutionException = null;
@@ -564,15 +564,17 @@
             // We have to cache the "digest" of the aggregating value itself,
             // because the action cache checker may want it.
             inputArtifactData.put(input, aggregatingValue.getSelfData());
-            ImmutableList.Builder<ArtifactFile> expansionBuilder = ImmutableList.builder();
+            ImmutableList.Builder<Artifact> expansionBuilder = ImmutableList.builder();
             for (Pair<Artifact, FileArtifactValue> pair : aggregatingValue.getInputs()) {
               expansionBuilder.add(pair.first);
             }
             expandedArtifacts.put(input, expansionBuilder.build());
           } else if (value instanceof TreeArtifactValue) {
             TreeArtifactValue setValue = (TreeArtifactValue) value;
-            expandedArtifacts.put(input, ActionInputHelper.asArtifactFiles(
-                    input, setValue.getChildPaths()));
+            ImmutableSet<Artifact> expandedTreeArtifacts = ImmutableSet.copyOf(
+                ActionInputHelper.asTreeFileArtifacts(input, setValue.getChildPaths()));
+
+            expandedArtifacts.put(input, expandedTreeArtifacts);
             // Again, we cache the "digest" of the value for cache checking.
             inputArtifactData.put(input, setValue.getSelfData());
           } else if (value instanceof FileArtifactValue) {
@@ -694,7 +696,7 @@
   private static class ContinuationState {
     AllInputs allInputs;
     Map<Artifact, FileArtifactValue> inputArtifactData = null;
-    Map<Artifact, Collection<ArtifactFile>> expandedArtifacts = null;
+    Map<Artifact, Collection<Artifact>> expandedArtifacts = null;
     Token token = null;
     Collection<Artifact> discoveredInputs = null;
     ActionExecutionValue value = null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
index 25a4339..fdce7c6 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionValue.java
@@ -20,7 +20,6 @@
 import com.google.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.Action.MiddlemanType;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -55,7 +54,7 @@
    * The FileValues of all files for this ActionExecutionValue. These FileValues can be
    * read and checked quickly from the filesystem, unlike FileArtifactValues.
    */
-  private final ImmutableMap<ArtifactFile, FileValue> artifactFileData;
+  private final ImmutableMap<Artifact, FileValue> artifactData;
 
   /** The TreeArtifactValue of all TreeArtifacts output by this Action. */
   private final ImmutableMap<Artifact, TreeArtifactValue> treeArtifactData;
@@ -67,7 +66,7 @@
   private final ImmutableMap<Artifact, FileArtifactValue> additionalOutputData;
 
   /**
-   * @param artifactFileData Map from Artifacts to corresponding FileValues.
+   * @param artifactData Map from Artifacts to corresponding FileValues.
    * @param treeArtifactData All tree artifact data.
    * @param additionalOutputData Map from Artifacts to values if the FileArtifactValue for this
    *     artifact cannot be derived from the corresponding FileValue (see {@link
@@ -76,10 +75,10 @@
    *     to invalidate ActionExecutionValues.
    */
   ActionExecutionValue(
-      Map<? extends ArtifactFile, FileValue> artifactFileData,
+      Map<Artifact, FileValue> artifactData,
       Map<Artifact, TreeArtifactValue> treeArtifactData,
       Map<Artifact, FileArtifactValue> additionalOutputData) {
-    this.artifactFileData = ImmutableMap.<ArtifactFile, FileValue>copyOf(artifactFileData);
+    this.artifactData = ImmutableMap.<Artifact, FileValue>copyOf(artifactData);
     this.additionalOutputData = ImmutableMap.copyOf(additionalOutputData);
     this.treeArtifactData = ImmutableMap.copyOf(treeArtifactData);
   }
@@ -98,10 +97,10 @@
    * @return The data for each non-middleman output of this action, in the form of the {@link
    * FileValue} that would be created for the file if it were to be read from disk.
    */
-  FileValue getData(ArtifactFile file) {
-    Preconditions.checkState(!additionalOutputData.containsKey(file),
-        "Should not be requesting data for already-constructed FileArtifactValue: %s", file);
-    return artifactFileData.get(file);
+  FileValue getData(Artifact artifact) {
+    Preconditions.checkState(!additionalOutputData.containsKey(artifact),
+        "Should not be requesting data for already-constructed FileArtifactValue: %s", artifact);
+    return artifactData.get(artifact);
   }
 
   TreeArtifactValue getTreeArtifactValue(Artifact artifact) {
@@ -110,11 +109,11 @@
   }
 
   /**
-   * @return The map from {@link ArtifactFile}s to the corresponding {@link FileValue}s that would
+   * @return The map from {@link Artifact}s to the corresponding {@link FileValue}s that would
    * be returned by {@link #getData}. Should only be needed by {@link FilesystemValueChecker}.
    */
-  ImmutableMap<ArtifactFile, FileValue> getAllFileValues() {
-    return artifactFileData;
+  ImmutableMap<Artifact, FileValue> getAllFileValues() {
+    return artifactData;
   }
 
   /**
@@ -158,7 +157,7 @@
   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this)
-        .add("artifactFileData", artifactFileData)
+        .add("artifactData", artifactData)
         .add("treeArtifactData", treeArtifactData)
         .add("additionalOutputData", additionalOutputData)
         .toString();
@@ -173,13 +172,13 @@
       return false;
     }
     ActionExecutionValue o = (ActionExecutionValue) obj;
-    return artifactFileData.equals(o.artifactFileData)
+    return artifactData.equals(o.artifactData)
         && treeArtifactData.equals(o.treeArtifactData)
         && additionalOutputData.equals(o.additionalOutputData);
   }
 
   @Override
   public int hashCode() {
-    return Objects.hashCode(artifactFileData, treeArtifactData, additionalOutputData);
+    return Objects.hashCode(artifactData, treeArtifactData, additionalOutputData);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
index cf8f668..28f7d0c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionMetadataHandler.java
@@ -22,7 +22,7 @@
 import com.google.devtools.build.lib.actions.ActionInput;
 import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactFile;
+import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.cache.Digest;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
 import com.google.devtools.build.lib.actions.cache.Metadata;
@@ -79,8 +79,8 @@
    */
   private final Map<Artifact, FileArtifactValue> inputArtifactData;
 
-  /** FileValues for each output ArtifactFile. */
-  private final ConcurrentMap<ArtifactFile, FileValue> outputArtifactFileData =
+  /** FileValues for each output Artifact. */
+  private final ConcurrentMap<Artifact, FileValue> outputArtifactData =
       new ConcurrentHashMap<>();
 
   /**
@@ -89,7 +89,7 @@
    * If the value is null, this means nothing was injected, and the output TreeArtifact
    * is to have its values read from disk instead.
    */
-  private final ConcurrentMap<Artifact, Set<ArtifactFile>> outputDirectoryListings =
+  private final ConcurrentMap<Artifact, Set<TreeFileArtifact>> outputDirectoryListings =
       new ConcurrentHashMap<>();
 
   /** Outputs that are to be omitted. */
@@ -109,18 +109,18 @@
    * Unlike additionalOutputData, this map is discarded (the relevant FileArtifactValues
    * are stored in outputTreeArtifactData's values instead).
    */
-  private final ConcurrentMap<ArtifactFile, FileArtifactValue> cachedTreeArtifactFileData =
+  private final ConcurrentMap<TreeFileArtifact, FileArtifactValue> cachedTreeFileArtifactData =
       new ConcurrentHashMap<>();
 
   /**
-   * Data for TreeArtifactValues, constructed from outputArtifactFileData and
+   * Data for TreeArtifactValues, constructed from outputArtifactData and
    * additionalOutputFileData.
    */
   private final ConcurrentMap<Artifact, TreeArtifactValue> outputTreeArtifactData =
       new ConcurrentHashMap<>();
 
-  /** Tracks which ArtifactFiles have had metadata injected. */
-  private final Set<ArtifactFile> injectedFiles = Sets.newConcurrentHashSet();
+  /** Tracks which Artifacts have had metadata injected. */
+  private final Set<Artifact> injectedFiles = Sets.newConcurrentHashSet();
 
   private final ImmutableSet<Artifact> outputs;
   private final TimestampGranularityMonitor tsgm;
@@ -214,7 +214,7 @@
       throw new FileNotFoundException(artifact + " not found");
     }
     // It's an ordinary artifact.
-    FileValue fileValue = outputArtifactFileData.get(artifact);
+    FileValue fileValue = outputArtifactData.get(artifact);
     if (fileValue != null) {
       // Non-middleman artifacts should only have additionalOutputData if they have
       // outputArtifactData. We don't assert this because of concurrency possibilities, but at least
@@ -237,16 +237,16 @@
   }
 
   /**
-   * Check that the new {@code data} we just calculated for an {@link ArtifactFile} agrees with the
+   * Check that the new {@code data} we just calculated for an {@link Artifact} agrees with the
    * {@code oldData} (presumably calculated concurrently), if it was present.
    */
   // Not private only because used by SkyframeActionExecutor's metadata handler.
-  static void checkInconsistentData(ArtifactFile file,
+  static void checkInconsistentData(Artifact artifact,
       @Nullable Object oldData, Object data) throws IOException {
     if (oldData != null && !oldData.equals(data)) {
       // Another thread checked this file since we looked at the map, and got a different answer
       // than we did. Presumably the user modified the file between reads.
-      throw new IOException("Data for " + file.prettyPrint() + " changed to " + data
+      throw new IOException("Data for " + artifact.prettyPrint() + " changed to " + data
           + " after it was calculated as " + oldData);
     }
   }
@@ -256,13 +256,13 @@
    * for normal (non-middleman) artifacts.
    */
   @Nullable
-  private Metadata maybeStoreAdditionalData(ArtifactFile file, FileValue data,
+  private Metadata maybeStoreAdditionalData(Artifact artifact, FileValue data,
       @Nullable byte[] injectedDigest) throws IOException {
     if (!data.exists()) {
       // Nonexistent files should only occur before executing an action.
-      throw new FileNotFoundException(file.prettyPrint() + " does not exist");
+      throw new FileNotFoundException(artifact.prettyPrint() + " does not exist");
     }
-    if (file instanceof Artifact) {
+    if (!artifact.hasParent()) {
       // Artifacts may use either the "real" digest or the mtime, if the file is size 0.
       boolean isFile = data.isFile();
       boolean useDigest = DigestUtils.useFileDigest(isFile, isFile ? data.getSize() : 0);
@@ -279,17 +279,17 @@
       injectedDigest = injectedDigest != null || !isFile ? injectedDigest : data.getDigest();
       FileArtifactValue value =
           FileArtifactValue.create(
-              (Artifact) file, isFile, isFile ? data.getSize() : 0, injectedDigest);
-      FileArtifactValue oldValue = additionalOutputData.putIfAbsent((Artifact) file, value);
-      checkInconsistentData(file, oldValue, value);
+              (Artifact) artifact, isFile, isFile ? data.getSize() : 0, injectedDigest);
+      FileArtifactValue oldValue = additionalOutputData.putIfAbsent((Artifact) artifact, value);
+      checkInconsistentData(artifact, oldValue, value);
       return metadataFromValue(value);
     } else {
-      // Non-Artifact ArtifactFiles are always "real" files, and always use the real digest.
-      // When null, createWithDigest() will pull the digest from the filesystem.
+      // We are dealing with artifacts inside a tree artifact.
       FileArtifactValue value =
-          FileArtifactValue.createWithDigest(file.getPath(), injectedDigest, data.getSize());
-      FileArtifactValue oldValue = cachedTreeArtifactFileData.putIfAbsent(file, value);
-      checkInconsistentData(file, oldValue, value);
+          FileArtifactValue.createWithDigest(artifact.getPath(), injectedDigest, data.getSize());
+      FileArtifactValue oldValue = cachedTreeFileArtifactData.putIfAbsent(
+          (TreeFileArtifact) artifact, value);
+      checkInconsistentData(artifact, oldValue, value);
       return new Metadata(value.getDigest());
     }
   }
@@ -302,13 +302,13 @@
         FileArtifactValue.createProxy(digest.asMetadata().digest));
   }
 
-  private Set<ArtifactFile> getTreeArtifactContents(Artifact artifact) {
+  private Set<TreeFileArtifact> getTreeArtifactContents(Artifact artifact) {
     Preconditions.checkArgument(artifact.isTreeArtifact(), artifact);
-    Set<ArtifactFile> contents = outputDirectoryListings.get(artifact);
+    Set<TreeFileArtifact> contents = outputDirectoryListings.get(artifact);
     if (contents == null) {
       // Unfortunately, there is no such thing as a ConcurrentHashSet.
-      contents = Collections.newSetFromMap(new ConcurrentHashMap<ArtifactFile, Boolean>());
-      Set<ArtifactFile> oldContents = outputDirectoryListings.putIfAbsent(artifact, contents);
+      contents = Collections.newSetFromMap(new ConcurrentHashMap<TreeFileArtifact, Boolean>());
+      Set<TreeFileArtifact> oldContents = outputDirectoryListings.putIfAbsent(artifact, contents);
       // Avoid a race condition.
       if (oldContents != null) {
         contents = oldContents;
@@ -323,7 +323,7 @@
       return value;
     }
 
-    Set<ArtifactFile> registeredContents = outputDirectoryListings.get(artifact);
+    Set<TreeFileArtifact> registeredContents = outputDirectoryListings.get(artifact);
     if (registeredContents != null) {
       // Check that our registered outputs matches on-disk outputs. Only perform this check
       // when contents were explicitly registered.
@@ -338,10 +338,10 @@
       } catch (TreeArtifactException e) {
         throw new IllegalStateException(e);
       }
-      Set<ArtifactFile> diskFiles = ActionInputHelper.asArtifactFiles(artifact, paths);
+      Set<TreeFileArtifact> diskFiles = ActionInputHelper.asTreeFileArtifacts(artifact, paths);
       if (!diskFiles.equals(registeredContents)) {
         // There might be more than one error here. We first look for missing output files.
-        Set<ArtifactFile> missingFiles = Sets.difference(registeredContents, diskFiles);
+        Set<TreeFileArtifact> missingFiles = Sets.difference(registeredContents, diskFiles);
         if (!missingFiles.isEmpty()) {
           // Don't throw IOException--getMetadataMaybe() eats them.
           // TODO(bazel-team): Report this error in a better way when called by checkOutputs()
@@ -352,7 +352,7 @@
               + " was registered, but not present on disk");
         }
 
-        Set<ArtifactFile> extraFiles = Sets.difference(diskFiles, registeredContents);
+        Set<TreeFileArtifact> extraFiles = Sets.difference(diskFiles, registeredContents);
         // extraFiles cannot be empty
         throw new IllegalStateException(
             "File " + extraFiles.iterator().next().getParentRelativePath()
@@ -369,28 +369,30 @@
     return value;
   }
 
-  private TreeArtifactValue constructTreeArtifactValue(Collection<ArtifactFile> contents)
+  private TreeArtifactValue constructTreeArtifactValue(Collection<TreeFileArtifact> contents)
       throws IOException {
-    Map<PathFragment, FileArtifactValue> values = Maps.newHashMapWithExpectedSize(contents.size());
+    Map<TreeFileArtifact, FileArtifactValue> values =
+        Maps.newHashMapWithExpectedSize(contents.size());
 
-    for (ArtifactFile file : contents) {
-      FileArtifactValue cachedValue = cachedTreeArtifactFileData.get(file);
+    for (TreeFileArtifact treeFileArtifact : contents) {
+      FileArtifactValue cachedValue = cachedTreeFileArtifactData.get(treeFileArtifact);
       if (cachedValue == null) {
-        FileValue fileValue = outputArtifactFileData.get(file);
-        // This is similar to what's present in getRealMetadataForArtifactFile, except
+        FileValue fileValue = outputArtifactData.get(treeFileArtifact);
+        // This is similar to what's present in getRealMetadataForArtifact, except
         // we get back the FileValue, not the metadata.
         // We do not cache exceptions besides nonexistence here, because it is unlikely that the
         // file will be requested from this cache too many times.
         if (fileValue == null) {
-          fileValue = constructFileValue(file, /*statNoFollow=*/ null);
+          fileValue = constructFileValue(treeFileArtifact, /*statNoFollow=*/ null);
           // A minor hack: maybeStoreAdditionalData will force the data to be stored
-          // in cachedTreeArtifactFileData.
-          maybeStoreAdditionalData(file, fileValue, null);
+          // in cachedTreeFileArtifactData.
+          maybeStoreAdditionalData(treeFileArtifact, fileValue, null);
         }
-        cachedValue = Preconditions.checkNotNull(cachedTreeArtifactFileData.get(file), file);
+        cachedValue = Preconditions.checkNotNull(
+            cachedTreeFileArtifactData.get(treeFileArtifact), treeFileArtifact);
       }
 
-      values.put(file.getParentRelativePath(), cachedValue);
+      values.put(treeFileArtifact, cachedValue);
     }
 
     return TreeArtifactValue.create(values);
@@ -414,34 +416,32 @@
     // something has gone terribly wrong.
     Object previousDirectoryListing =
         outputDirectoryListings.put(artifact,
-            Collections.newSetFromMap(new ConcurrentHashMap<ArtifactFile, Boolean>()));
+            Collections.newSetFromMap(new ConcurrentHashMap<TreeFileArtifact, Boolean>()));
     Preconditions.checkState(previousDirectoryListing == null,
         "Race condition while constructing TreArtifactValue: %s, %s",
         artifact, previousDirectoryListing);
-    return constructTreeArtifactValue(ActionInputHelper.asArtifactFiles(artifact, paths));
+    return constructTreeArtifactValue(ActionInputHelper.asTreeFileArtifacts(artifact, paths));
   }
 
   @Override
-  public void addExpandedTreeOutput(ArtifactFile output) {
-    Preconditions.checkArgument(output.getParent().isTreeArtifact(),
-        "Expanded set output must belong to a TreeArtifact");
-    Set<ArtifactFile> values = getTreeArtifactContents(output.getParent());
+  public void addExpandedTreeOutput(TreeFileArtifact output) {
+    Set<TreeFileArtifact> values = getTreeArtifactContents(output.getParent());
     values.add(output);
   }
 
   @Override
   public void injectDigest(ActionInput output, FileStatus statNoFollow, byte[] digest) {
-    // Assumption: any non-ArtifactFile output is 'virtual' and should be ignored here.
-    if (output instanceof ArtifactFile) {
-      final ArtifactFile file = (ArtifactFile) output;
-      Preconditions.checkState(injectedFiles.add(file), file);
+    // Assumption: any non-Artifact output is 'virtual' and should be ignored here.
+    if (output instanceof Artifact) {
+      final Artifact artifact = (Artifact) output;
+      Preconditions.checkState(injectedFiles.add(artifact), artifact);
       FileValue fileValue;
       try {
         // This call may do an unnecessary call to Path#getFastDigest to see if the digest is
         // readily available. We cannot pass the digest in, though, because if it is not available
         // from the filesystem, this FileValue will not compare equal to another one created for the
         // same file, because the other one will be missing its digest.
-        fileValue = fileValueFromArtifactFile(file,
+        fileValue = fileValueFromArtifact(artifact,
             FileStatusWithDigestAdapter.adapt(statNoFollow), tsgm);
         // Ensure the digest supplied matches the actual digest if it exists.
         byte[] fileDigest = fileValue.getDigest();
@@ -450,9 +450,9 @@
           String digestString = (digest != null) ? base16.encode(digest) : "null";
           String fileDigestString = base16.encode(fileDigest);
           throw new IllegalStateException("Expected digest " + digestString + " for artifact "
-              + file + ", but got " + fileDigestString + " (" + fileValue + ")");
+              + artifact + ", but got " + fileDigestString + " (" + fileValue + ")");
         }
-        outputArtifactFileData.put(file, fileValue);
+        outputArtifactData.put(artifact, fileValue);
       } catch (IOException e) {
         // Do nothing - we just failed to inject metadata. Real error handling will be done later,
         // when somebody will try to access that file.
@@ -462,14 +462,14 @@
       // the filesystem does not support fast digests. Since we usually only inject digests when
       // running with a filesystem that supports fast digests, this is fairly unlikely.
       try {
-        maybeStoreAdditionalData(file, fileValue, digest);
+        maybeStoreAdditionalData(artifact, fileValue, digest);
       } catch (IOException e) {
         if (fileValue.getSize() != 0) {
           // Empty files currently have their mtimes examined, and so could throw. No other files
           // should throw, since all filesystem access has already been done.
           throw new IllegalStateException(
               "Filesystem should not have been accessed while injecting data for "
-                  + file.prettyPrint(), e);
+                  + artifact.prettyPrint(), e);
         }
         // Ignore exceptions for empty files, as above.
       }
@@ -496,11 +496,11 @@
         "Files cannot be injected before action execution: %s", injectedFiles);
     Preconditions.checkState(omittedOutputs.isEmpty(),
         "Artifacts cannot be marked omitted before action execution: %s", omittedOutputs);
-    outputArtifactFileData.clear();
+    outputArtifactData.clear();
     outputDirectoryListings.clear();
     outputTreeArtifactData.clear();
     additionalOutputData.clear();
-    cachedTreeArtifactFileData.clear();
+    cachedTreeFileArtifactData.clear();
   }
 
   @Override
@@ -521,13 +521,13 @@
   }
 
   @Override
-  public boolean isInjected(ArtifactFile file) {
+  public boolean isInjected(Artifact file) {
     return injectedFiles.contains(file);
   }
 
   /** @return data for output files that was computed during execution. */
-  Map<ArtifactFile, FileValue> getOutputArtifactFileData() {
-    return outputArtifactFileData;
+  Map<Artifact, FileValue> getOutputArtifactData() {
+    return outputArtifactData;
   }
 
   /**
@@ -540,7 +540,7 @@
 
   /**
    * Returns data for any output files whose metadata was not computable from the corresponding
-   * entry in {@link #getOutputArtifactFileData}.
+   * entry in {@link #getOutputArtifactData}.
    *
    * <p>There are three reasons why we might not be able to compute metadata for an artifact from
    * the FileValue. First, middleman artifacts have no corresponding FileValues. Second, if
@@ -558,21 +558,21 @@
   }
 
   /** Constructs a new FileValue, saves it, and checks inconsistent data. */
-  FileValue constructFileValue(ArtifactFile file, @Nullable FileStatusWithDigest statNoFollow)
+  FileValue constructFileValue(Artifact artifact, @Nullable FileStatusWithDigest statNoFollow)
       throws IOException {
-    FileValue value = fileValueFromArtifactFile(file, statNoFollow, tsgm);
-    FileValue oldFsValue = outputArtifactFileData.putIfAbsent(file, value);
-    checkInconsistentData(file, oldFsValue, null);
+    FileValue value = fileValueFromArtifact(artifact, statNoFollow, tsgm);
+    FileValue oldFsValue = outputArtifactData.putIfAbsent(artifact, value);
+    checkInconsistentData(artifact, oldFsValue, null);
     return value;
   }
 
   @VisibleForTesting
-  static FileValue fileValueFromArtifactFile(ArtifactFile file,
+  static FileValue fileValueFromArtifact(Artifact artifact,
       @Nullable FileStatusWithDigest statNoFollow, @Nullable TimestampGranularityMonitor tsgm)
       throws IOException {
-    Path path = file.getPath();
+    Path path = artifact.getPath();
     RootedPath rootedPath =
-        RootedPath.toRootedPath(file.getRoot().getPath(), file.getRootRelativePath());
+        RootedPath.toRootedPath(artifact.getRoot().getPath(), artifact.getRootRelativePath());
     if (statNoFollow == null) {
       statNoFollow = FileStatusWithDigestAdapter.adapt(path.statIfFound(Symlinks.NOFOLLOW));
       if (statNoFollow == null) {
@@ -592,7 +592,7 @@
       }
     }
     RootedPath realRootedPath = RootedPath.toRootedPathMaybeUnderRoot(realPath,
-        ImmutableList.of(file.getRoot().getPath()));
+        ImmutableList.of(artifact.getRoot().getPath()));
     FileStateValue fileStateValue;
     FileStateValue realFileStateValue;
     try {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
index 63a3800..9df851b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
@@ -21,7 +21,6 @@
 import com.google.common.collect.Sets;
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.concurrent.ExecutorUtil;
 import com.google.devtools.build.lib.concurrent.Sharder;
 import com.google.devtools.build.lib.concurrent.ThrowableRecordingRunnableWrapper;
@@ -216,7 +215,7 @@
     return new Runnable() {
       @Override
       public void run() {
-        Map<ArtifactFile, Pair<SkyKey, ActionExecutionValue>> fileToKeyAndValue = new HashMap<>();
+        Map<Artifact, Pair<SkyKey, ActionExecutionValue>> fileToKeyAndValue = new HashMap<>();
         Map<Artifact, Pair<SkyKey, ActionExecutionValue>> treeArtifactsToKeyAndValue =
             new HashMap<>();
         for (Pair<SkyKey, ActionExecutionValue> keyAndValue : shard) {
@@ -224,9 +223,9 @@
           if (actionValue == null) {
             dirtyKeys.add(keyAndValue.getFirst());
           } else {
-            for (ArtifactFile file : actionValue.getAllFileValues().keySet()) {
-              if (shouldCheckFile(knownModifiedOutputFiles, file)) {
-                fileToKeyAndValue.put(file, keyAndValue);
+            for (Artifact artifact : actionValue.getAllFileValues().keySet()) {
+              if (shouldCheckFile(knownModifiedOutputFiles, artifact)) {
+                fileToKeyAndValue.put(artifact, keyAndValue);
               }
             }
 
@@ -242,11 +241,11 @@
           }
         }
 
-        List<ArtifactFile> files = ImmutableList.copyOf(fileToKeyAndValue.keySet());
+        List<Artifact> artifacts = ImmutableList.copyOf(fileToKeyAndValue.keySet());
         List<FileStatusWithDigest> stats;
         try {
           stats = batchStatter.batchStat(/*includeDigest=*/true, /*includeLinks=*/true,
-              Artifact.asPathFragments(files));
+              Artifact.asPathFragments(artifacts));
         } catch (IOException e) {
           // Batch stat did not work. Log an exception and fall back on system calls.
           LoggingUtil.logToRemote(Level.WARNING, "Unable to process batch stat", e);
@@ -257,17 +256,17 @@
           return;
         }
 
-        Preconditions.checkState(files.size() == stats.size(),
-            "artifacts.size() == %s stats.size() == %s", files.size(), stats.size());
-        for (int i = 0; i < files.size(); i++) {
-          ArtifactFile file = files.get(i);
+        Preconditions.checkState(artifacts.size() == stats.size(),
+            "artifacts.size() == %s stats.size() == %s", artifacts.size(), stats.size());
+        for (int i = 0; i < artifacts.size(); i++) {
+          Artifact artifact = artifacts.get(i);
           FileStatusWithDigest stat = stats.get(i);
-          Pair<SkyKey, ActionExecutionValue> keyAndValue = fileToKeyAndValue.get(file);
+          Pair<SkyKey, ActionExecutionValue> keyAndValue = fileToKeyAndValue.get(artifact);
           ActionExecutionValue actionValue = keyAndValue.getSecond();
           SkyKey key = keyAndValue.getFirst();
-          FileValue lastKnownData = actionValue.getAllFileValues().get(file);
+          FileValue lastKnownData = actionValue.getAllFileValues().get(artifact);
           try {
-            FileValue newData = ActionMetadataHandler.fileValueFromArtifactFile(file, stat,
+            FileValue newData = ActionMetadataHandler.fileValueFromArtifact(artifact, stat,
                 tsgm);
             if (!newData.equals(lastKnownData)) {
               updateIntraBuildModifiedCounter(stat != null ? stat.getLastChangeTime() : -1,
@@ -366,12 +365,13 @@
   private boolean actionValueIsDirtyWithDirectSystemCalls(ActionExecutionValue actionValue,
       ImmutableSet<PathFragment> knownModifiedOutputFiles) {
     boolean isDirty = false;
-    for (Map.Entry<ArtifactFile, FileValue> entry : actionValue.getAllFileValues().entrySet()) {
-      ArtifactFile file = entry.getKey();
+    for (Map.Entry<Artifact, FileValue> entry : actionValue.getAllFileValues().entrySet()) {
+      Artifact file = entry.getKey();
       FileValue lastKnownData = entry.getValue();
       if (shouldCheckFile(knownModifiedOutputFiles, file)) {
         try {
-          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifactFile(file, null, tsgm);
+          FileValue fileValue = ActionMetadataHandler.fileValueFromArtifact(file, null,
+              tsgm);
           if (!fileValue.equals(lastKnownData)) {
             updateIntraBuildModifiedCounter(fileValue.exists()
                 ? fileValue.realRootedPath().asPath().getLastModifiedTime()
@@ -410,9 +410,9 @@
   }
 
   private static boolean shouldCheckFile(ImmutableSet<PathFragment> knownModifiedOutputFiles,
-      ArtifactFile file) {
+      Artifact artifact) {
     return knownModifiedOutputFiles == null
-        || knownModifiedOutputFiles.contains(file.getExecPath());
+        || knownModifiedOutputFiles.contains(artifact.getExecPath());
   }
 
   private BatchDirtyResult getDirtyValues(ValueFetcher fetcher,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java b/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
index 2d281f4..2700904 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PerActionFileCache.java
@@ -56,6 +56,12 @@
     if (!(input instanceof Artifact)) {
       return null;
     }
+
+    // TODO(rduan): Implement action file caching for TreeFileArtifacts.
+    if (((Artifact) input).hasParent()) {
+      return null;
+    }
+
     return Preconditions.checkNotNull(inputArtifactData.get(input), input);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
index 82b8411..78c4dee 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeActionExecutor.java
@@ -40,7 +40,6 @@
 import com.google.devtools.build.lib.actions.AlreadyReportedActionExecutionException;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
-import com.google.devtools.build.lib.actions.ArtifactFile;
 import com.google.devtools.build.lib.actions.ArtifactPrefixConflictException;
 import com.google.devtools.build.lib.actions.CachedActionEvent;
 import com.google.devtools.build.lib.actions.EnvironmentalExecException;
@@ -432,17 +431,17 @@
   }
 
   private static class ArtifactExpanderImpl implements ArtifactExpander {
-    private final Map<Artifact, Collection<ArtifactFile>> expandedInputs;
+    private final Map<Artifact, Collection<Artifact>> expandedInputs;
 
-    private ArtifactExpanderImpl(Map<Artifact, Collection<ArtifactFile>> expandedInputMiddlemen) {
+    private ArtifactExpanderImpl(Map<Artifact, Collection<Artifact>> expandedInputMiddlemen) {
       this.expandedInputs = expandedInputMiddlemen;
     }
 
     @Override
-    public void expand(Artifact artifact, Collection<? super ArtifactFile> output) {
+    public void expand(Artifact artifact, Collection<? super Artifact> output) {
       Preconditions.checkState(artifact.isMiddlemanArtifact() || artifact.isTreeArtifact(),
           artifact);
-      Collection<ArtifactFile> result = expandedInputs.get(artifact);
+      Collection<Artifact> result = expandedInputs.get(artifact);
       // Note that result may be null for non-aggregating middlemen.
       if (result != null) {
         output.addAll(result);
@@ -458,7 +457,7 @@
   @Override
   public ActionExecutionContext getContext(
       ActionInputFileCache graphFileCache, MetadataHandler metadataHandler,
-      Map<Artifact, Collection<ArtifactFile>> expandedInputs) {
+      Map<Artifact, Collection<Artifact>> expandedInputs) {
     FileOutErr fileOutErr = actionLogBufferPathGenerator.generate();
     return new ActionExecutionContext(
         executorEngine,
@@ -616,7 +615,7 @@
             "%s %s", actionExecutionContext.getMetadataHandler(), metadataHandler);
         prepareScheduleExecuteAndCompleteAction(action, actionExecutionContext, actionStartTime);
         return new ActionExecutionValue(
-            metadataHandler.getOutputArtifactFileData(),
+            metadataHandler.getOutputArtifactData(),
             metadataHandler.getOutputTreeArtifactData(),
             metadataHandler.getAdditionalOutputData());
       } finally {
@@ -851,14 +850,14 @@
   }
 
   private static void setPathReadOnlyAndExecutable(MetadataHandler metadataHandler,
-      ArtifactFile file)
+      Artifact artifact)
       throws IOException {
     // If the metadata was injected, we assume the mode is set correct and bail out early to avoid
     // the additional overhead of resetting it.
-    if (metadataHandler.isInjected(file)) {
+    if (metadataHandler.isInjected(artifact)) {
       return;
     }
-    Path path = file.getPath();
+    Path path = artifact.getPath();
     if (path.isFile(Symlinks.NOFOLLOW)) { // i.e. regular files only.
       // We trust the files created by the execution-engine to be non symlinks with expected
       // chmod() settings already applied.
@@ -877,7 +876,7 @@
       }
     } else {
       setPathReadOnlyAndExecutable(
-          metadataHandler, ActionInputHelper.artifactFile(parent, subpath));
+          metadataHandler, ActionInputHelper.treeFileArtifact(parent, subpath));
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
index a60ad09..a0f2241 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TreeArtifactValue.java
@@ -14,13 +14,14 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Function;
 import com.google.common.base.MoreObjects;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
-import com.google.devtools.build.lib.actions.ActionInputHelper;
 import com.google.devtools.build.lib.actions.Artifact;
-import com.google.devtools.build.lib.actions.ArtifactFile;
+import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
 import com.google.devtools.build.lib.actions.cache.Digest;
 import com.google.devtools.build.lib.actions.cache.Metadata;
 import com.google.devtools.build.lib.vfs.Path;
@@ -36,13 +37,21 @@
 
 /**
  * Value for TreeArtifacts, which contains a digest and the {@link FileArtifactValue}s
- * of its child {@link ArtifactFile}s.
+ * of its child {@link TreeFileArtifact}s.
  */
 public class TreeArtifactValue extends ArtifactValue {
-  private final byte[] digest;
-  private final Map<PathFragment, FileArtifactValue> childData;
+  private static final Function<Artifact, PathFragment> PARENT_RELATIVE_PATHS =
+      new Function<Artifact, PathFragment>() {
+        @Override
+        public PathFragment apply(Artifact artifact) {
+            return artifact.getParentRelativePath();
+        }
+      };
 
-  private TreeArtifactValue(byte[] digest, Map<PathFragment, FileArtifactValue> childData) {
+  private final byte[] digest;
+  private final Map<TreeFileArtifact, FileArtifactValue> childData;
+
+  private TreeArtifactValue(byte[] digest, Map<TreeFileArtifact, FileArtifactValue> childData) {
     this.digest = digest;
     this.childData = ImmutableMap.copyOf(childData);
   }
@@ -52,11 +61,13 @@
    * and their corresponding FileArtifactValues.
    */
   @VisibleForTesting
-  public static TreeArtifactValue create(Map<PathFragment, FileArtifactValue> childFileValues) {
+  public static TreeArtifactValue create(Map<TreeFileArtifact, FileArtifactValue> childFileValues) {
     Map<String, Metadata> digestBuilder =
         Maps.newHashMapWithExpectedSize(childFileValues.size());
-    for (Map.Entry<PathFragment, FileArtifactValue> e : childFileValues.entrySet()) {
-      digestBuilder.put(e.getKey().getPathString(), new Metadata(e.getValue().getDigest()));
+    for (Map.Entry<TreeFileArtifact, FileArtifactValue> e : childFileValues.entrySet()) {
+      digestBuilder.put(
+          e.getKey().getParentRelativePath().getPathString(),
+          new Metadata(e.getValue().getDigest()));
     }
 
     return new TreeArtifactValue(
@@ -68,17 +79,12 @@
     return FileArtifactValue.createProxy(digest);
   }
 
-  /** Returns the inputs that this artifact expands to, in no particular order. */
-  Iterable<ArtifactFile> getChildren(final Artifact base) {
-    return ActionInputHelper.asArtifactFiles(base, childData.keySet());
-  }
-
   public Metadata getMetadata() {
     return new Metadata(digest.clone());
   }
 
   public Set<PathFragment> getChildPaths() {
-    return childData.keySet();
+    return ImmutableSet.copyOf(Iterables.transform(childData.keySet(), PARENT_RELATIVE_PATHS));
   }
 
   @Nullable
@@ -86,6 +92,14 @@
     return digest.clone();
   }
 
+  public Iterable<TreeFileArtifact> getChildren() {
+    return childData.keySet();
+  }
+
+  public FileArtifactValue getChildValue(TreeFileArtifact artifact) {
+    return childData.get(artifact);
+  }
+
   @Override
   public int hashCode() {
     return Arrays.hashCode(digest);
@@ -122,14 +136,19 @@
    * This is occasionally useful because Java's concurrent collections disallow null members.
    */
   static final TreeArtifactValue MISSING_TREE_ARTIFACT = new TreeArtifactValue(null,
-      ImmutableMap.<PathFragment, FileArtifactValue>of()) {
+      ImmutableMap.<TreeFileArtifact, FileArtifactValue>of()) {
     @Override
     public FileArtifactValue getSelfData() {
       throw new UnsupportedOperationException();
     }
 
     @Override
-    Iterable<ArtifactFile> getChildren(Artifact base) {
+    public Iterable<TreeFileArtifact> getChildren() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public FileArtifactValue getChildValue(TreeFileArtifact artifact) {
       throw new UnsupportedOperationException();
     }