diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
index 57abd35..1a6c4c8 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionCacheChecker.java
@@ -50,6 +50,28 @@
  * otherwise lightweight, and should be constructed anew and discarded for each build request.
  */
 public class ActionCacheChecker {
+  private static final Metadata CONSTANT_METADATA = new Metadata() {
+    @Override
+    public boolean isFile() {
+      return false;
+    }
+
+    @Override
+    public byte[] getDigest() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getSize() {
+      return 0;
+    }
+
+    @Override
+    public long getModifiedTime() {
+      return -1;
+    }
+  };
+
   private final ActionCache actionCache;
   private final Predicate<? super Action> executionFilter;
   private final ArtifactResolver artifactResolver;
@@ -294,7 +316,7 @@
   private static Metadata getMetadataOrConstant(MetadataHandler metadataHandler, Artifact artifact)
       throws IOException {
     if (artifact.isConstantMetadata()) {
-      return Metadata.CONSTANT_METADATA;
+      return CONSTANT_METADATA;
     } else {
       return metadataHandler.getMetadata(artifact);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/Metadata.java b/src/main/java/com/google/devtools/build/lib/actions/cache/Metadata.java
index 0f5a037..642bd29 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/Metadata.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/Metadata.java
@@ -14,104 +14,43 @@
 
 package com.google.devtools.build.lib.actions.cache;
 
-import com.google.common.io.BaseEncoding;
-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;
-import java.util.Arrays;
-import java.util.Date;
-
 /**
- * A class to represent file metadata.
- * ActionCacheChecker may assume that, for a given file, equal
- * metadata at different moments implies equal file-contents,
- * where metadata equality is computed using Metadata.equals().
- * <p>
- * NB! Several other parts of Blaze are relying on the fact that metadata
- * uses mtime and not ctime. If metadata is ever changed
- * to use ctime, all uses of Metadata must be carefully examined.
+ * An interface to represent the state of a file (or directory). This is used to determine whether a
+ * file has changed or not.
+ *
+ * <p>NB! Several other parts of Blaze are relying on the fact that metadata uses mtime and not
+ * ctime. If metadata is ever changed to use ctime, all uses of Metadata must be carefully examined.
  */
-@Immutable @ThreadSafe
-public final class Metadata {
-  private final long mtime;
-  private final byte[] digest;
-
-  // Convenience object for use with volatile files that we do not want checked
-  // (e.g. the build-changelist.txt)
-  public static final Metadata CONSTANT_METADATA = new Metadata(-1);
-
+public interface Metadata {
   /**
-   * Construct an instance for a directory with the specified mtime. The {@link #isFile} method
-   * returns true if and only if a digest is set.
+   * Marker interface for singleton implementations of the Metadata interface. This is only needed
+   * for a correct implementation of {@code equals}.
    */
-  public Metadata(long mtime) {
-    this.mtime = mtime;
-    this.digest = null;
+  public interface Singleton {
   }
 
   /**
-   * Construct an instance for a file with the specified digest. The {@link #isFile} method returns
-   * true if and only if a digest is set.
+   * Whether the underlying file system object is a file or a symlink to a file, rather than a
+   * directory. All files are guaranteed to have a digest, and {@link #getDigest} must only be
+   * called on files.
    */
-  public Metadata(byte[] digest) {
-    this.mtime = 0L;
-    this.digest = Preconditions.checkNotNull(digest);
-  }
-
-  public boolean isFile() {
-    return digest != null;
-  }
+  boolean isFile();
 
   /**
-   * Returns the digest for the underlying file system object.
+   * Returns the file's digest; must only be called on objects for which {@link #isFile} returns
+   * true.
    *
    * <p>The return value is owned by the cache and must not be modified.
    */
-  public byte[] getDigest() {
-    Preconditions.checkState(digest != null);
-    return digest;
-  }
+  byte[] getDigest();
 
-  public long getModifiedTime() {
-    return mtime;
-  }
+  /** Returns the file's size, or 0 if the underlying file system object is not a file. */
+  // TODO(ulfjack): Throw an exception if it's not a file.
+  long getSize();
 
-  @Override
-  public int hashCode() {
-    int hash = 0;
-    if (digest != null) {
-      // We are already dealing with the digest so we can just use portion of it
-      // as a hash code.
-      hash += digest[0] + (digest[1] << 8) + (digest[2] << 16) + (digest[3] << 24);
-    } else {
-      // Inlined hashCode for Long, so we don't
-      // have to construct an Object, just to compute
-      // a 32-bit hash out of a 64 bit value.
-      hash = (int) (mtime ^ (mtime >>> 32));
-    }
-    return hash;
-  }
-
-  @Override
-  public boolean equals(Object that) {
-    if (this == that) {
-      return true;
-    }
-    if (!(that instanceof Metadata)) {
-      return false;
-    }
-    // Do a strict comparison - both digest and mtime should match
-    return Arrays.equals(this.digest, ((Metadata) that).digest)
-        && this.mtime == ((Metadata) that).mtime;
-  }
-
-  @Override
-  public String toString() {
-    if (digest != null) {
-      return "MD5 " + BaseEncoding.base16().lowerCase().encode(digest);
-    } else if (mtime > 0) {
-      return "timestamp " + new Date(mtime);
-    }
-    return "no metadata";
-  }
+  /**
+   * Returns the last modified time; must only be called on objects for which {@link #isFile}
+   * returns false.
+   */
+  long getModifiedTime();
 }
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 47cd18f..3027a38 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
@@ -153,10 +153,7 @@
         || value == FileArtifactValue.OMITTED_FILE_MARKER) {
       throw new FileNotFoundException();
     }
-    // If the file is a directory, we need to return the mtime because the action cache uses mtime
-    // to determine if this artifact has changed. We want this code path to go away somehow
-    // for directories (maybe by implementing FileSet in Skyframe).
-    return value.isFile() ? new Metadata(value.getDigest()) : new Metadata(value.getModifiedTime());
+    return value;
   }
 
   @Nullable
@@ -218,7 +215,7 @@
       if (!fileValue.exists()) {
         throw new FileNotFoundException(artifact.prettyPrint() + " does not exist");
       }
-      return new Metadata(Preconditions.checkNotNull(fileValue.getDigest(), artifact));
+      return FileArtifactValue.createNormalFile(fileValue);
     }
     // We do not cache exceptions besides nonexistence here, because it is unlikely that the file
     // will be requested from this cache too many times.
@@ -256,7 +253,7 @@
     if (isFile && !artifact.hasParent() && data.getDigest() != null) {
       // We do not need to store the FileArtifactValue separately -- the digest is in the file value
       // and that is all that is needed for this file's metadata.
-      return new Metadata(data.getDigest());
+      return FileArtifactValue.createNormalFile(data);
     }
     // Unfortunately, the FileValue does not contain enough information for us to calculate the
     // corresponding FileArtifactValue -- either the metadata must use the modified time, which we
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java
index cfdcb187..2f06471 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileArtifactValue.java
@@ -17,6 +17,9 @@
 import com.google.common.base.MoreObjects;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.cache.DigestUtils;
+import com.google.devtools.build.lib.actions.cache.Metadata;
+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;
 import com.google.devtools.build.lib.vfs.FileStatus;
 import com.google.devtools.build.lib.vfs.Path;
@@ -39,8 +42,9 @@
  * </ul>
  */
 // TODO(janakr): make this an interface once JDK8 allows us to have static methods on interfaces.
-public abstract class FileArtifactValue implements SkyValue {
-  private static final class SingletonMarkerValue extends FileArtifactValue {
+@Immutable @ThreadSafe
+public abstract class FileArtifactValue implements SkyValue, Metadata {
+  private static final class SingletonMarkerValue extends FileArtifactValue implements Singleton {
     @Nullable
     @Override
     public byte[] getDigest() {
@@ -48,7 +52,7 @@
     }
 
     @Override
-    boolean isFile() {
+    public boolean isFile() {
       return false;
     }
 
@@ -68,6 +72,33 @@
     }
   }
 
+  private static final class OmittedFileValue extends FileArtifactValue implements Singleton {
+    @Override
+    public byte[] getDigest() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean isFile() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getSize() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getModifiedTime() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public String toString() {
+      return "OMITTED_FILE_MARKER";
+    }
+  }
+
   static final FileArtifactValue DEFAULT_MIDDLEMAN = new SingletonMarkerValue();
   /** Data that marks that a file is not present on the filesystem. */
   @VisibleForTesting
@@ -77,33 +108,7 @@
    * Represents an omitted file -- we are aware of it but it doesn't exist. All access methods are
    * unsupported.
    */
-  static final FileArtifactValue OMITTED_FILE_MARKER =
-      new FileArtifactValue() {
-        @Override
-        public byte[] getDigest() {
-          throw new UnsupportedOperationException();
-        }
-
-        @Override
-        boolean isFile() {
-          throw new UnsupportedOperationException();
-        }
-
-        @Override
-        public long getSize() {
-          throw new UnsupportedOperationException();
-        }
-
-        @Override
-        public long getModifiedTime() {
-          throw new UnsupportedOperationException();
-        }
-
-        @Override
-        public String toString() {
-          return "OMITTED_FILE_MARKER";
-        }
-      };
+  static final FileArtifactValue OMITTED_FILE_MARKER = new OmittedFileValue();
 
   private static final class DirectoryArtifactValue extends FileArtifactValue {
     private final long mtime;
@@ -134,18 +139,6 @@
     }
 
     @Override
-    public int hashCode() {
-      return (int) mtime;
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      return (this == other)
-          || ((other instanceof DirectoryArtifactValue)
-              && this.mtime == ((DirectoryArtifactValue) other).mtime);
-    }
-
-    @Override
     public String toString() {
       return MoreObjects.toStringHelper(this).add("mtime", mtime).toString();
     }
@@ -166,7 +159,7 @@
     }
 
     @Override
-    boolean isFile() {
+    public boolean isFile() {
       return true;
     }
 
@@ -182,29 +175,6 @@
     }
 
     @Override
-    public int hashCode() {
-      // Hash digest by content, not reference.
-      return 37 * (int) size + Arrays.hashCode(digest);
-    }
-
-    /**
-     * Two RegularFileArtifactValues will only compare equal if they have the same content. This
-     * differs from the {@code Metadata#equivalence} method, which allows for comparison using mtime
-     * if one object does not have a digest available.
-     */
-    @Override
-    public boolean equals(Object other) {
-      if (this == other) {
-        return true;
-      }
-      if (!(other instanceof RegularFileArtifactValue)) {
-        return false;
-      }
-      RegularFileArtifactValue that = (RegularFileArtifactValue) other;
-      return this.size == that.size && Arrays.equals(this.digest, that.digest);
-    }
-
-    @Override
     public String toString() {
       return MoreObjects.toStringHelper(this).add("digest", digest).add("size", size).toString();
     }
@@ -239,10 +209,18 @@
     return createNormalFile(digest, size);
   }
 
-  static FileArtifactValue createNormalFile(byte[] digest, long size) {
+  public static FileArtifactValue createNormalFile(byte[] digest, long size) {
     return new RegularFileArtifactValue(digest, size);
   }
 
+  static FileArtifactValue createNormalFile(FileValue fileValue) {
+    return new RegularFileArtifactValue(fileValue.getDigest(), fileValue.getSize());
+  }
+
+  public static FileArtifactValue createDirectory(long mtime) {
+    return new DirectoryArtifactValue(mtime);
+  }
+
   /**
    * Creates a FileArtifactValue used as a 'proxy' input for other ArtifactValues.
    * These are used in {@link com.google.devtools.build.lib.actions.ActionCacheChecker}.
@@ -252,16 +230,48 @@
     return createNormalFile(digest, /*size=*/ 0);
   }
 
-  /** Returns the digest of this value. Null for non-files, non-null for files. */
+  @Override
+  public abstract boolean isFile();
+
   @Nullable
+  @Override
   public abstract byte[] getDigest();
 
-  /** @return true if this is a file or a symlink to an existing file */
-  abstract boolean isFile();
-
-  /** Gets the size of the file. Non-files (including directories) have size 0. */
+  @Override
   public abstract long getSize();
 
-  /** Gets last modified time of file. Should only be called if this is not a file. */
-  abstract long getModifiedTime();
+  @Override
+  public abstract long getModifiedTime();
+
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
+    }
+    if (!(o instanceof Metadata)) {
+      return false;
+    }
+    if ((this instanceof Singleton) || (o instanceof Singleton)) {
+      return false;
+    }
+    Metadata m = (Metadata) o;
+    if (isFile()) {
+      return m.isFile() && Arrays.equals(getDigest(), m.getDigest()) && getSize() == m.getSize();
+    } else {
+      return !m.isFile() && getModifiedTime() == m.getModifiedTime();
+    }
+  }
+
+  @Override
+  public int hashCode() {
+    if (this instanceof Singleton) {
+      return System.identityHashCode(this);
+    }
+    // Hash digest by content, not reference.
+    if (isFile()) {
+      return 37 * Long.hashCode(getSize()) + Arrays.hashCode(getDigest());
+    } else {
+      return Long.hashCode(getModifiedTime());
+    }
+  }
 }
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 5a132c3..783899a 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
@@ -61,9 +61,7 @@
     Map<String, Metadata> digestBuilder =
         Maps.newHashMapWithExpectedSize(childFileValues.size());
     for (Map.Entry<TreeFileArtifact, FileArtifactValue> e : childFileValues.entrySet()) {
-      digestBuilder.put(
-          e.getKey().getParentRelativePath().getPathString(),
-          new Metadata(e.getValue().getDigest()));
+      digestBuilder.put(e.getKey().getParentRelativePath().getPathString(), e.getValue());
     }
 
     return new TreeArtifactValue(
@@ -76,7 +74,7 @@
   }
 
   Metadata getMetadata() {
-    return new Metadata(digest.clone());
+    return getSelfData();
   }
 
   Set<PathFragment> getChildPaths() {
diff --git a/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java b/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java
index c2bf185..dfadf20 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCacheTest.java
@@ -17,6 +17,7 @@
 import static com.google.common.truth.Truth.assertWithMessage;
 
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.skyframe.FileArtifactValue;
 import com.google.devtools.build.lib.testutil.Scratch;
 import com.google.devtools.build.lib.util.Clock;
 import com.google.devtools.build.lib.vfs.Path;
@@ -157,7 +158,7 @@
     ActionCache.Entry entry =
         new ActionCache.Entry("actionKey", ImmutableMap.<String, String>of(), false);
     entry.toString();
-    entry.addFile(PathFragment.create("foo/bar"), Metadata.CONSTANT_METADATA);
+    entry.addFile(PathFragment.create("foo/bar"), FileArtifactValue.createDirectory(1234));
     entry.toString();
     entry.getFileDigest();
     entry.toString();
diff --git a/src/test/java/com/google/devtools/build/lib/actions/cache/MetadataTest.java b/src/test/java/com/google/devtools/build/lib/actions/cache/MetadataTest.java
deleted file mode 100644
index 5458713..0000000
--- a/src/test/java/com/google/devtools/build/lib/actions/cache/MetadataTest.java
+++ /dev/null
@@ -1,45 +0,0 @@
-// Copyright 2015 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.cache;
-
-
-import com.google.common.io.BaseEncoding;
-import com.google.common.testing.EqualsTester;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
-@RunWith(JUnit4.class)
-public class MetadataTest {
-
-  private static byte[] toBytes(String hex) {
-    return BaseEncoding.base16().upperCase().decode(hex);
-  }
-
-  @Test
-  public void testEqualsAndHashCode() throws Exception {
-    // Each "equality group" is checked for equality within itself (including hashCode equality)
-    // and inequality with members of other equality groups.
-    new EqualsTester()
-        .addEqualityGroup(new Metadata(toBytes("00112233445566778899AABBCCDDEEFF")),
-                          new Metadata(toBytes("00112233445566778899AABBCCDDEEFF")))
-        .addEqualityGroup(new Metadata(1))
-        .addEqualityGroup(new Metadata(toBytes("FFFFFF00000000000000000000000000")))
-        .addEqualityGroup(new Metadata(2),
-                          new Metadata(2))
-        .addEqualityGroup("a string")
-        .testEquals();
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/FileArtifactValueTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/FileArtifactValueTest.java
new file mode 100644
index 0000000..641c28e
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/FileArtifactValueTest.java
@@ -0,0 +1,51 @@
+// Copyright 2015 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.skyframe;
+
+import com.google.common.io.BaseEncoding;
+import com.google.common.testing.EqualsTester;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+@RunWith(JUnit4.class)
+public class FileArtifactValueTest {
+
+  private static byte[] toBytes(String hex) {
+    return BaseEncoding.base16().upperCase().decode(hex);
+  }
+
+  @Test
+  public void testEqualsAndHashCode() throws Exception {
+    // Each "equality group" is checked for equality within itself (including hashCode equality)
+    // and inequality with members of other equality groups.
+    new EqualsTester()
+        .addEqualityGroup(
+            FileArtifactValue.createNormalFile(toBytes("00112233445566778899AABBCCDDEEFF"), 1),
+            FileArtifactValue.createNormalFile(toBytes("00112233445566778899AABBCCDDEEFF"), 1))
+        .addEqualityGroup(
+            FileArtifactValue.createNormalFile(toBytes("00112233445566778899AABBCCDDEEFF"), 2))
+        .addEqualityGroup(FileArtifactValue.createDirectory(1))
+        .addEqualityGroup(
+            FileArtifactValue.createNormalFile(toBytes("FFFFFF00000000000000000000000000"), 1))
+        .addEqualityGroup(
+            FileArtifactValue.createDirectory(2),
+            FileArtifactValue.createDirectory(2))
+        .addEqualityGroup(FileArtifactValue.OMITTED_FILE_MARKER)
+        .addEqualityGroup(FileArtifactValue.MISSING_FILE_MARKER)
+        .addEqualityGroup(FileArtifactValue.DEFAULT_MIDDLEMAN)
+        .addEqualityGroup("a string")
+        .testEquals();
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
index d8c2e40..b1d8b08 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/TreeArtifactMetadataTest.java
@@ -102,7 +102,9 @@
     // breaking changes.
     Map<String, Metadata> digestBuilder = new HashMap<>();
     for (PathFragment child : children) {
-      Metadata subdigest = new Metadata(tree.getPath().getRelative(child).getDigest());
+      Metadata subdigest = FileArtifactValue.createNormalFile(
+          tree.getPath().getRelative(child).getDigest(),
+          tree.getPath().getRelative(child).getFileSize());
       digestBuilder.put(child.getPathString(), subdigest);
     }
     assertThat(DigestUtils.fromMetadata(digestBuilder).getDigestBytesUnsafe())