Part 3 of 5: Merging semantics.

Introduces the AndroidDataMerger, MergeConflict, and UnwrittenMergedAndroidData which is the entry point in the AndroidResourceProcessing *AndroidData lifecycle.

Also, refactors the AndroidDataSet parsing of resources, making it functionally immutable.

--
MOS_MIGRATED_REVID=117492690

10 files changed, 588 insertions, 31 deletions

diff --git a/src/tools/android/java/com/google/devtools/build/android/AndroidDataMerger.java b/src/tools/android/java/com/google/devtools/build/android/AndroidDataMerger.java
new file mode 100644
index 0000000000..50a471b656
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/AndroidDataMerger.java
@@ -0,0 +1,233 @@
+// 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.android;
+
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+
+import com.android.ide.common.res2.MergingException;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Handles the Merging of AndroidDataSet.
+ */
+public class AndroidDataMerger {
+
+  /** An internal class that handles the homogenization of AndroidDataSets. */
+  // TODO(corysmith): Move this functionality to AndroidDataSet?
+  private static class ResourceMap {
+
+    private final Map<FullyQualifiedName, DataResource> overwritableResources;
+    private final Set<MergeConflict> conflicts;
+    private final Map<FullyQualifiedName, DataResource> nonOverwritingResourceMap;
+
+    private ResourceMap(
+        Map<FullyQualifiedName, DataResource> overwritableResources,
+        Set<MergeConflict> conflicts,
+        Map<FullyQualifiedName, DataResource> nonOverwritingResourceMap) {
+      this.overwritableResources = overwritableResources;
+      this.conflicts = conflicts;
+      this.nonOverwritingResourceMap = nonOverwritingResourceMap;
+    }
+
+    /**
+     * Creates ResourceMap from an AndroidDataSet.
+     */
+    static ResourceMap from(AndroidDataSet data) {
+      Map<FullyQualifiedName, DataResource> overwritingResourceMap = new HashMap<>();
+      Set<MergeConflict> conflicts = new HashSet<>();
+      for (DataResource resource : data.getOverwritingResources()) {
+        if (overwritingResourceMap.containsKey(resource.fullyQualifiedName())) {
+          conflicts.add(
+              MergeConflict.between(
+                  resource.fullyQualifiedName(),
+                  overwritingResourceMap.get(resource.fullyQualifiedName()),
+                  resource));
+        }
+        overwritingResourceMap.put(resource.fullyQualifiedName(), resource);
+      }
+
+      Map<FullyQualifiedName, DataResource> nonOverwritingResourceMap = new HashMap<>();
+      for (DataResource resource : data.getNonOverwritingResources()) {
+        nonOverwritingResourceMap.put(resource.fullyQualifiedName(), resource);
+      }
+      return new ResourceMap(overwritingResourceMap, conflicts, nonOverwritingResourceMap);
+    }
+
+    boolean containsOverwritable(FullyQualifiedName name) {
+      return overwritableResources.containsKey(name);
+    }
+
+    Iterable<Map.Entry<FullyQualifiedName, DataResource>> iterateOverwritableEntries() {
+      return overwritableResources.entrySet();
+    }
+
+    public MergeConflict foundConflict(FullyQualifiedName key, DataResource value) {
+      return MergeConflict.between(key, overwritableResources.get(key), value);
+    }
+
+    public Collection<DataResource> mergeNonOverwritable(ResourceMap other) {
+      Map<FullyQualifiedName, DataResource> merged = new HashMap<>(other.nonOverwritingResourceMap);
+      merged.putAll(nonOverwritingResourceMap);
+      return merged.values();
+    }
+  }
+
+  /**
+   * Merges DataResources into an UnwrittenMergedAndroidData.
+   *
+   * This method has two basic states, library and binary. These are distinguished by
+   * allowPrimaryOverrideAll, which allows the primary data to overwrite any value in the closure,
+   * a trait associated with binaries, as a binary is a leaf node. The other semantics are
+   * slightly more complicated: a given resource can be overwritten only if it resides in the
+   * direct dependencies of primary data. This forces an explicit simple priority for each resource,
+   * instead of the more subtle semantics of multiple layers of libraries with potential overwrites.
+   *
+   * The UnwrittenMergedAndroidData contains only one of each FullyQualifiedName in both the
+   * direct and transitive closure.
+   *
+   * The merge semantics are as follows:
+   *   Key:
+   *     A(): package A
+   *     A(foo): package A with resource symbol foo
+   *     A() -> B(): a dependency relationship of B.deps = [:A]
+   *     A(),B() -> C(): a dependency relationship of C.deps = [:A,:B]
+   *
+   *   For android library (allowPrimaryOverrideAll = False)
+   *
+   *     A() -> B(foo) -> C(foo) == Valid
+   *     A() -> B() -> C(foo) == Valid
+   *     A() -> B() -> C(foo),D(foo) == Conflict
+   *     A(foo) -> B(foo) -> C() == Conflict
+   *     A(foo) -> B() -> C(foo) == Conflict
+   *     A(foo),B(foo) -> C() -> D() == Conflict
+   *     A() -> B(foo),C(foo) -> D() == Conflict
+   *     A(foo),B(foo) -> C() -> D(foo) == Conflict
+   *     A() -> B(foo),C(foo) -> D(foo) == Conflict
+   *
+   *   For android binary (allowPrimaryOverrideAll = True)
+   *
+   *     A() -> B(foo) -> C(foo) == Valid
+   *     A() -> B() -> C(foo) == Valid
+   *     A() -> B() -> C(foo),D(foo) == Conflict
+   *     A(foo) -> B(foo) -> C() == Conflict
+   *     A(foo) -> B() -> C(foo) == Valid
+   *     A(foo),B(foo) -> C() -> D() == Conflict
+   *     A() -> B(foo),C(foo) -> D() == Conflict
+   *     A(foo),B(foo) -> C() -> D(foo) == Valid
+   *     A() -> B(foo),C(foo) -> D(foo) == Valid
+   *
+   * @param transitive The transitive dependencies to merge.
+   * @param direct The direct dependencies to merge.
+   * @param primaryData The primary data to merge against.
+   * @param allowPrimaryOverrideAll Boolean that indicates if the primary data will be considered
+   *                                the ultimate source of truth, provided it doesn't conflict
+   *                                with itself.
+   * @return An UnwrittenMergedAndroidData, containing DataResource objects that can be written
+   * to disk for aapt processing or serialized for future merge passes.
+   * @throws MergingException if there are merge conflicts or issues with parsing resources from
+   * Primary.
+   * @throws IOException if there are issues with reading resources.
+   */
+  UnwrittenMergedAndroidData merge(
+      AndroidDataSet transitive,
+      AndroidDataSet direct,
+      UnvalidatedAndroidData primaryData,
+      boolean allowPrimaryOverrideAll)
+      throws MergingException, IOException {
+
+    // Extract the primary resources.
+    AndroidDataSet primary = AndroidDataSet.from(primaryData);
+    ResourceMap primaryMap = ResourceMap.from(primary);
+
+    // Handle the overwriting resources first.
+    ResourceMap directMap = ResourceMap.from(direct);
+    ResourceMap transitiveMap = ResourceMap.from(transitive);
+
+    List<DataResource> overwritableDeps = new ArrayList<>();
+
+    Set<MergeConflict> conflicts = new HashSet<>();
+    conflicts.addAll(primaryMap.conflicts);
+    for (MergeConflict conflict : directMap.conflicts) {
+      if (allowPrimaryOverrideAll
+          && primaryMap.containsOverwritable(conflict.fullyQualifiedName())) {
+        continue;
+      }
+      conflicts.add(conflict);
+    }
+
+    for (MergeConflict conflict : transitiveMap.conflicts) {
+      if (allowPrimaryOverrideAll
+          && primaryMap.containsOverwritable(conflict.fullyQualifiedName())) {
+        continue;
+      }
+      conflicts.add(conflict);
+    }
+
+    for (Map.Entry<FullyQualifiedName, DataResource> entry :
+        directMap.iterateOverwritableEntries()) {
+      // Direct dependencies are simply overwritten, no conflict.
+      if (!primaryMap.containsOverwritable(entry.getKey())) {
+        overwritableDeps.add(entry.getValue());
+      }
+    }
+
+    for (Map.Entry<FullyQualifiedName, DataResource> entry :
+        transitiveMap.iterateOverwritableEntries()) {
+      // If the primary is considered to be intentional (usually at the binary level),
+      // skip.
+      if (primaryMap.containsOverwritable(entry.getKey()) && allowPrimaryOverrideAll) {
+        continue;
+      }
+      // If a transitive value is in the direct map report a conflict, as it is commonly
+      // unintentional.
+      if (directMap.containsOverwritable(entry.getKey())) {
+        conflicts.add(directMap.foundConflict(entry.getKey(), entry.getValue()));
+      } else if (primaryMap.containsOverwritable(entry.getKey())) {
+        // If overwriting a transitive value with a primary map, assume it's an unintentional
+        // override, unless allowPrimaryOverrideAll is set. At which point, this code path
+        // should not be reached.
+        conflicts.add(primaryMap.foundConflict(entry.getKey(), entry.getValue()));
+      } else {
+        // If it's in none of the of sources, add it.
+        overwritableDeps.add(entry.getValue());
+      }
+    }
+
+    if (!conflicts.isEmpty()) {
+      List<String> messages = new ArrayList<>();
+      for (MergeConflict conflict : conflicts) {
+        messages.add(conflict.toConflictMessage());
+      }
+      throw new MergingException(Joiner.on("\n").join(messages));
+    }
+
+    Collections.sort(overwritableDeps);
+
+    return UnwrittenMergedAndroidData.of(
+        primaryData.getManifest(),
+        primary,
+        AndroidDataSet.of(
+            overwritableDeps, ImmutableList.copyOf(directMap.mergeNonOverwritable(transitiveMap))));
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/AndroidDataSet.java b/src/tools/android/java/com/google/devtools/build/android/AndroidDataSet.java
index 48377dd1cd..971851d103 100644
--- a/src/tools/android/java/com/google/devtools/build/android/AndroidDataSet.java
+++ b/src/tools/android/java/com/google/devtools/build/android/AndroidDataSet.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.android;
 
+import com.google.common.base.MoreObjects;
 import com.google.common.collect.ImmutableList;
 
 import com.android.ide.common.res2.MergingException;
@@ -26,7 +27,9 @@ import java.nio.file.attribute.BasicFileAttributes;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
+import java.util.Objects;
 
+import javax.annotation.concurrent.Immutable;
 import javax.xml.stream.XMLInputFactory;
 import javax.xml.stream.XMLStreamException;
 
@@ -37,6 +40,7 @@ import javax.xml.stream.XMLStreamException;
  * together. It extracts the android resource symbols (e.g. R.string.Foo) from the xml files to
  * allow an AndroidDataMerger to consume and produce a merged set of data.
  */
+@Immutable
 public class AndroidDataSet {
   /**
    * A FileVisitor that walks a resource tree and extract FullyQualifiedName and resource values.
@@ -55,6 +59,16 @@ public class AndroidDataSet {
       this.nonOverwritingResources = nonOverwritingResources;
     }
 
+    private void checkForErrors() throws MergingException {
+      if (!getErrors().isEmpty()) {
+        StringBuilder errors = new StringBuilder();
+        for (Exception e : getErrors()) {
+          errors.append("\n").append(e.getMessage());
+        }
+        throw new MergingException(errors.toString());
+      }
+    }
+
     @Override
     public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs)
         throws IOException {
@@ -77,9 +91,8 @@ public class AndroidDataSet {
       try {
         if (!Files.isDirectory(path)) {
           if (inValuesSubtree) {
-            XmlDataResource.fromPath(xmlInputFactory, path, fqnFactory,
-                overwritingResources,
-                nonOverwritingResources);
+            XmlDataResource.fromPath(
+                xmlInputFactory, path, fqnFactory, overwritingResources, nonOverwritingResources);
           } else {
             overwritingResources.add(FileDataResource.fromPath(path, fqnFactory));
           }
@@ -95,29 +108,80 @@ public class AndroidDataSet {
     }
   }
 
-  private final List<DataResource> overwritingResources = new ArrayList<>();
-  private final List<DataResource> nonOverwritingResources = new ArrayList<>();
+  /** Creates an AndroidDataSet of the overwriting and nonOverwritingResources lists. */
+  public static AndroidDataSet of(
+      List<DataResource> overwritingResources, List<DataResource> nonOverwritingResources) {
+    return new AndroidDataSet(
+        ImmutableList.copyOf(overwritingResources), ImmutableList.copyOf(nonOverwritingResources));
+  }
+
+  public static AndroidDataSet from(UnvalidatedAndroidData primary)
+      throws IOException, MergingException {
+    List<DataResource> overwritingResources = new ArrayList<>();
+    List<DataResource> nonOverwritingResources = new ArrayList<>();
+    ResourceFileVisitor visitor =
+        new ResourceFileVisitor(overwritingResources, nonOverwritingResources);
+    primary.walkResources(visitor);
+    visitor.checkForErrors();
+    return of(overwritingResources, nonOverwritingResources);
+  }
 
   /**
-   * Adds a DependencyAndroidData to the dataset
+   * Creates an AndroidDataSet from a list of DependencyAndroidDatas.
    *
    * The adding process parses out all the provided symbol into DataResource objects.
    *
-   * @param androidData The dependency data to parse into DataResources.
+   * @param dependencyAndroidDataList The dependency data to parse into DataResources.
    * @throws IOException when there are issues with reading files.
    * @throws MergingException when there is invalid resource information.
    */
-  public void add(DependencyAndroidData androidData) throws IOException, MergingException {
+  public static AndroidDataSet from(List<DependencyAndroidData> dependencyAndroidDataList)
+      throws IOException, MergingException {
+    List<DataResource> overwritingResources = new ArrayList<>();
+    List<DataResource> nonOverwritingResources = new ArrayList<>();
     ResourceFileVisitor visitor =
         new ResourceFileVisitor(overwritingResources, nonOverwritingResources);
-    androidData.walk(visitor);
-    if (!visitor.getErrors().isEmpty()) {
-      StringBuilder errors = new StringBuilder();
-      for (Exception e : visitor.getErrors()) {
-        errors.append("\n").append(e.getMessage());
-      }
-      throw new MergingException(errors.toString());
+    for (DependencyAndroidData data : dependencyAndroidDataList) {
+      data.walkResources(visitor);
     }
+    visitor.checkForErrors();
+    return of(overwritingResources, nonOverwritingResources);
+  }
+
+  private final ImmutableList<DataResource> overwritingResources;
+  private final ImmutableList<DataResource> nonOverwritingResources;
+
+  private AndroidDataSet(
+      ImmutableList<DataResource> overwritingResources,
+      ImmutableList<DataResource> nonOverwritingResources) {
+    this.overwritingResources = overwritingResources;
+    this.nonOverwritingResources = nonOverwritingResources;
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this)
+        .add("overwritingResources", overwritingResources)
+        .add("nonOverwritingResources", nonOverwritingResources)
+        .toString();
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+    if (!(other instanceof AndroidDataSet)) {
+      return false;
+    }
+    AndroidDataSet that = (AndroidDataSet) other;
+    return Objects.equals(overwritingResources, that.overwritingResources)
+        && Objects.equals(nonOverwritingResources, that.nonOverwritingResources);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(overwritingResources, nonOverwritingResources);
   }
 
   /**
diff --git a/src/tools/android/java/com/google/devtools/build/android/DataResource.java b/src/tools/android/java/com/google/devtools/build/android/DataResource.java
index 96d765e110..4e64fb7ae3 100644
--- a/src/tools/android/java/com/google/devtools/build/android/DataResource.java
+++ b/src/tools/android/java/com/google/devtools/build/android/DataResource.java
@@ -19,7 +19,17 @@ import java.nio.file.Path;
 /**
  * Represents an Android Resource parsed from an xml or binary file.
  */
-public interface DataResource {
+public interface DataResource extends Comparable<DataResource> {
+
+  /**
+   * Provides the FullyQualifiedName of the DataResource
+   */
+  FullyQualifiedName fullyQualifiedName();
+
+  /**
+   * Provides the Path to the file from which the DataResource was derived.
+   */
+  Path source();
 
   /**
    * Writes the resource to the given resource directory.
diff --git a/src/tools/android/java/com/google/devtools/build/android/DependencyAndroidData.java b/src/tools/android/java/com/google/devtools/build/android/DependencyAndroidData.java
index e4bf85b932..74e7371fe3 100644
--- a/src/tools/android/java/com/google/devtools/build/android/DependencyAndroidData.java
+++ b/src/tools/android/java/com/google/devtools/build/android/DependencyAndroidData.java
@@ -207,7 +207,7 @@ class DependencyAndroidData {
     return new DependencyAndroidData(modifiedResources, modifiedAssets, manifest, rTxt, null);
   }
 
-  public void walk(final FileVisitor<Path> fileVisitor) throws IOException {
+  public void walkResources(final FileVisitor<Path> fileVisitor) throws IOException {
     for (Path path : resourceDirs) {
       Files.walkFileTree(
           path, ImmutableSet.of(FileVisitOption.FOLLOW_LINKS), Integer.MAX_VALUE, fileVisitor);
diff --git a/src/tools/android/java/com/google/devtools/build/android/FileDataResource.java b/src/tools/android/java/com/google/devtools/build/android/FileDataResource.java
index d012ceed39..930a9d2f8c 100644
--- a/src/tools/android/java/com/google/devtools/build/android/FileDataResource.java
+++ b/src/tools/android/java/com/google/devtools/build/android/FileDataResource.java
@@ -80,8 +80,23 @@ public class FileDataResource implements DataResource {
   }
 
   @Override
+  public FullyQualifiedName fullyQualifiedName() {
+    return qn;
+  }
+
+  @Override
+  public Path source() {
+    return source;
+  }
+
+  @Override
   public void write(Path newResourceDirectory) throws IOException {
     // TODO(corysmith): Implement the copy semantics.
     throw new UnsupportedOperationException();
   }
+
+  @Override
+  public int compareTo(DataResource o) {
+    return qn.compareTo(o.fullyQualifiedName());
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/FullyQualifiedName.java b/src/tools/android/java/com/google/devtools/build/android/FullyQualifiedName.java
index 2f74db5e85..85161bf2ef 100644
--- a/src/tools/android/java/com/google/devtools/build/android/FullyQualifiedName.java
+++ b/src/tools/android/java/com/google/devtools/build/android/FullyQualifiedName.java
@@ -16,6 +16,8 @@ package com.google.devtools.build.android;
 import com.google.common.base.Joiner;
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Ordering;
 
 import com.android.resources.ResourceType;
 
@@ -24,16 +26,20 @@ import java.util.Objects;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 
+import javax.annotation.CheckReturnValue;
+import javax.annotation.concurrent.Immutable;
+
 /**
  * Represents a fully qualified name for an android resource.
  *
  * Each resource name consists of the resource package, name, type, and qualifiers.
  */
-public class FullyQualifiedName {
+@Immutable
+public class FullyQualifiedName implements Comparable<FullyQualifiedName> {
   public static final String DEFAULT_PACKAGE = "res-auto";
 
   private final String pkg;
-  private final List<String> qualifiers;
+  private final ImmutableList<String> qualifiers;
   private final ResourceType resourceType;
   private final String resourceName;
 
@@ -98,16 +104,8 @@ public class FullyQualifiedName {
     }
   }
 
-  private FullyQualifiedName(
-      String pkg, List<String> qualifiers, ResourceType resourceType, String resourceName) {
-    this.pkg = pkg;
-    this.qualifiers = qualifiers;
-    this.resourceType = resourceType;
-    this.resourceName = resourceName;
-  }
-
   /**
-   * Creates a new FullyQualifiedName.
+   * Creates a new FullyQualifiedName with sorted qualifiers.
    * @param pkg The resource package of the name. If unknown the default should be "res-auto"
    * @param qualifiers The resource qualifiers of the name, such as "en" or "xhdpi".
    * @param resourceType The resource type of the name.
@@ -116,7 +114,30 @@ public class FullyQualifiedName {
    */
   public static FullyQualifiedName of(
       String pkg, List<String> qualifiers, ResourceType resourceType, String resourceName) {
-    return new FullyQualifiedName(pkg, qualifiers, resourceType, resourceName);
+    return new FullyQualifiedName(pkg, Ordering.natural().immutableSortedCopy(qualifiers),
+        resourceType, resourceName);
+  }
+
+  private FullyQualifiedName(
+      String pkg,
+      ImmutableList<String> qualifiers,
+      ResourceType resourceType,
+      String resourceName) {
+    this.pkg = pkg;
+    this.qualifiers = qualifiers;
+    this.resourceType = resourceType;
+    this.resourceName = resourceName;
+  }
+
+  /** Creates a FullyQualifiedName from this one with a different package. */
+  @CheckReturnValue
+  public FullyQualifiedName replacePackage(String newPackage) {
+    if (pkg.equals(newPackage)) {
+      return this;
+    }
+    // Don't use "of" because it ensures the qualifiers are sorted -- we already know
+    // they are sorted here.
+    return new FullyQualifiedName(newPackage, qualifiers, resourceType, resourceName);
   }
 
   @Override
@@ -145,4 +166,26 @@ public class FullyQualifiedName {
         .add("resourceName", resourceName)
         .toString();
   }
+
+  @Override
+  public int compareTo(FullyQualifiedName other) {
+    if (!pkg.equals(other.pkg)) {
+      return pkg.compareTo(other.pkg);
+    }
+    if (!resourceType.equals(other.resourceType)) {
+      return resourceType.compareTo(other.resourceType);
+    }
+    if (!resourceName.equals(other.resourceName)) {
+      return resourceName.compareTo(other.resourceName);
+    }
+    // TODO(corysmith): Figure out a more performant stable way to keep a stable order.
+    if (!qualifiers.equals(other.qualifiers)) {
+      if (qualifiers.size() != other.qualifiers.size()) {
+        return qualifiers.size() - other.qualifiers.size();
+      }
+      // This works because the qualifiers are sorted on creation.
+      return qualifiers.toString().compareTo(other.qualifiers.toString());
+    }
+    return 0;
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/MergeConflict.java b/src/tools/android/java/com/google/devtools/build/android/MergeConflict.java
new file mode 100644
index 0000000000..2728af1fb8
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/MergeConflict.java
@@ -0,0 +1,70 @@
+// 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.android;
+
+import com.google.common.base.MoreObjects;
+
+import java.util.Objects;
+
+/**
+ * Represents a conflict of two DataResources that share the same FullyQualifiedName.
+ */
+public class MergeConflict {
+  static final String CONFLICT_MESSAGE = "%s is provided from %s and %s";
+  private final FullyQualifiedName fullyQualifiedName;
+  private final DataResource first;
+  private final DataResource second;
+
+  private MergeConflict(
+      FullyQualifiedName fullyQualifiedName, DataResource first, DataResource second) {
+    this.fullyQualifiedName = fullyQualifiedName;
+    this.first = first;
+    this.second = second;
+  }
+
+  public static MergeConflict between(
+      FullyQualifiedName fullyQualifiedName, DataResource first, DataResource second) {
+    return new MergeConflict(fullyQualifiedName, first, second);
+  }
+
+  public String toConflictMessage() {
+    return String.format(CONFLICT_MESSAGE, fullyQualifiedName, first.source(), second.source());
+  }
+
+  public FullyQualifiedName fullyQualifiedName() {
+    return fullyQualifiedName;
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this).add("first", first).add("second", second).toString();
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+    if (!(other instanceof MergeConflict)) {
+      return false;
+    }
+    MergeConflict that = (MergeConflict) other;
+    return Objects.equals(first, that.first) && Objects.equals(second, that.second);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(first, second);
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/UnvalidatedAndroidData.java b/src/tools/android/java/com/google/devtools/build/android/UnvalidatedAndroidData.java
index ae6df22140..71f1712a43 100644
--- a/src/tools/android/java/com/google/devtools/build/android/UnvalidatedAndroidData.java
+++ b/src/tools/android/java/com/google/devtools/build/android/UnvalidatedAndroidData.java
@@ -15,12 +15,16 @@ package com.google.devtools.build.android;
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 
 import com.android.ide.common.res2.AssetSet;
 import com.android.ide.common.res2.ResourceSet;
 
+import java.io.IOException;
 import java.nio.file.FileSystem;
 import java.nio.file.FileSystems;
+import java.nio.file.FileVisitOption;
+import java.nio.file.FileVisitor;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.util.List;
@@ -76,8 +80,8 @@ class UnvalidatedAndroidData {
   private final ImmutableList<Path> assetDirs;
   private final ImmutableList<Path> resourceDirs;
 
-  public UnvalidatedAndroidData(ImmutableList<Path> resourceDirs, ImmutableList<Path> assetDirs,
-      Path manifest) {
+  public UnvalidatedAndroidData(
+      ImmutableList<Path> resourceDirs, ImmutableList<Path> assetDirs, Path manifest) {
     this.resourceDirs = resourceDirs;
     this.assetDirs = assetDirs;
     this.manifest = manifest;
@@ -160,4 +164,11 @@ class UnvalidatedAndroidData {
       assetSets.add(set);
     }
   }
+
+  public void walkResources(final FileVisitor<Path> fileVisitor) throws IOException {
+    for (Path path : resourceDirs) {
+      Files.walkFileTree(
+          path, ImmutableSet.of(FileVisitOption.FOLLOW_LINKS), Integer.MAX_VALUE, fileVisitor);
+    }
+  }
 }
diff --git a/src/tools/android/java/com/google/devtools/build/android/UnwrittenMergedAndroidData.java b/src/tools/android/java/com/google/devtools/build/android/UnwrittenMergedAndroidData.java
new file mode 100644
index 0000000000..1a19fc133c
--- /dev/null
+++ b/src/tools/android/java/com/google/devtools/build/android/UnwrittenMergedAndroidData.java
@@ -0,0 +1,96 @@
+// 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.android;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.MoreObjects;
+
+import java.io.IOException;
+import java.nio.file.Path;
+import java.util.Objects;
+
+/**
+ * Merged Android Data that has yet to written into a {@link MergedAndroidData}.
+ */
+public class UnwrittenMergedAndroidData {
+
+  private final Path manifest;
+  private final AndroidDataSet resources;
+  private final AndroidDataSet deps;
+
+  public static UnwrittenMergedAndroidData of(
+      Path manifest, AndroidDataSet resources, AndroidDataSet deps) {
+    return new UnwrittenMergedAndroidData(manifest, resources, deps);
+  }
+
+  private UnwrittenMergedAndroidData(Path manifest, AndroidDataSet resources, AndroidDataSet deps) {
+    this.manifest = manifest;
+    this.resources = resources;
+    this.deps = deps;
+  }
+
+  /**
+   * Writes the android data to directories for consumption by aapt.
+   * @param newResourceDirectory The new resource directory to write to.
+   * @return A MergedAndroidData that is ready for further tool processing.
+   * @throws IOException when something goes wrong while writing.
+   */
+  public MergedAndroidData write(Path newResourceDirectory) throws IOException {
+    // TODO(corysmith): Implement write.
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public String toString() {
+    return MoreObjects.toStringHelper(this)
+        .add("manifest", manifest)
+        .add("resources", resources)
+        .add("deps", deps)
+        .toString();
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (this == other) {
+      return true;
+    }
+    if (!(other instanceof UnwrittenMergedAndroidData)) {
+      return false;
+    }
+    UnwrittenMergedAndroidData that = (UnwrittenMergedAndroidData) other;
+    return Objects.equals(manifest, that.manifest)
+        && Objects.equals(resources, that.resources)
+        && Objects.equals(deps, that.deps);
+  }
+
+  @Override
+  public int hashCode() {
+    return Objects.hash(manifest, resources, deps);
+  }
+
+  @VisibleForTesting
+  Path getManifest() {
+    return manifest;
+  }
+
+  @VisibleForTesting
+  AndroidDataSet getResources() {
+    return resources;
+  }
+
+  @VisibleForTesting
+  AndroidDataSet getDeps() {
+    return deps;
+  }
+}
diff --git a/src/tools/android/java/com/google/devtools/build/android/XmlDataResource.java b/src/tools/android/java/com/google/devtools/build/android/XmlDataResource.java
index dfc7867299..9f5245b3a3 100644
--- a/src/tools/android/java/com/google/devtools/build/android/XmlDataResource.java
+++ b/src/tools/android/java/com/google/devtools/build/android/XmlDataResource.java
@@ -171,6 +171,16 @@ public class XmlDataResource implements DataResource {
   }
 
   @Override
+  public Path source() {
+    return source;
+  }
+
+  @Override
+  public FullyQualifiedName fullyQualifiedName() {
+    return fqn;
+  }
+
+  @Override
   public int hashCode() {
     return Objects.hash(fqn, source, xml);
   }
@@ -200,4 +210,9 @@ public class XmlDataResource implements DataResource {
     // TODO(corysmith): Implement write.
     throw new UnsupportedOperationException();
   }
+
+  @Override
+  public int compareTo(DataResource o) {
+    return fqn.compareTo(o.fullyQualifiedName());
+  }
 }