Manifest Merger: children order should not impact merge.

Change-Id: I5d4e0b5042c5e510ae1865d5d3ac759c89d00641

10 files changed, 777 insertions, 270 deletions

diff --git a/manifmerger/src/com/android/manifmerger/ManifestMerger.java b/manifmerger/src/com/android/manifmerger/ManifestMerger.java
index d6063ea..e8058c7 100755
--- a/manifmerger/src/com/android/manifmerger/ManifestMerger.java
+++ b/manifmerger/src/com/android/manifmerger/ManifestMerger.java
@@ -32,9 +32,9 @@ import org.w3c.dom.NodeList;
 
 import java.io.File;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.TreeMap;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicInteger;
 
@@ -484,7 +484,7 @@ public class ManifestMerger {
             boolean found = false;
 
             for (Element dest : findElements(mMainDoc, path)) {
-                if (compareElements(src, dest, false, null /*diff*/, null /*keyAttr*/)) {
+                if (compareElements(dest, src, false, null /*diff*/, null /*keyAttr*/)) {
                     found = true;
                     break;
                 }
@@ -564,7 +564,7 @@ public class ManifestMerger {
             for (Element dest : dests) {
                 // If there's already a similar node in the destination, check it's identical.
                 StringBuilder diff = new StringBuilder();
-                if (compareElements(src, dest, false, diff, keyAttr)) {
+                if (compareElements(dest, src, false, diff, keyAttr)) {
                     // Same element. Skip.
                     if (warnDups) {
                         mLog.conflict(Severity.INFO,
@@ -1190,11 +1190,13 @@ public class ManifestMerger {
     }
 
     /**
-     * Compares two {@link Element}s recursively. They must be identical with the same
-     * structure and order. Whitespace and comments are ignored.
+     * Compares two {@link Element}s recursively.
+     * They must be identical with the same structure.
+     * Order should not matter.
+     * Whitespace and comments are ignored.
      *
-     * @param e1 The first element to compare.
-     * @param e2 The second element to compare with.
+     * @param expected The first element to compare.
+     * @param actual The second element to compare with.
      * @param nextSiblings If true, will also compare the following siblings.
      *   If false, it will just compare the given node.
      * @param diff An optional {@link StringBuilder} where to accumulate a diff output.
@@ -1202,197 +1204,22 @@ public class ManifestMerger {
      * @return True if {@code e1} and {@code e2} are equal.
      */
     private boolean compareElements(
-            @NonNull Node e1,
-            @NonNull Node e2,
+            @NonNull Node expected,
+            @NonNull Node actual,
             boolean nextSiblings,
             @Nullable StringBuilder diff,
             @Nullable String keyAttr) {
-        return compareElements(e1, e2, nextSiblings, diff, 0, keyAttr);
-    }
-
-    /**
-     * Do not call directly. This is an implementation detail for
-     * {@link #compareElements(Node, Node, boolean, StringBuilder, String)}.
-     */
-    private boolean compareElements(
-            @NonNull Node e1,
-            @NonNull Node e2,
-            boolean nextSiblings,
-            @Nullable StringBuilder diff,
-            int diffOffset,
-            @Nullable String keyAttr) {
-        while(true) {
-            // Find the next non-whitespace text or non-comment in e1.
-            while (e1 != null) {
-                short t = e1.getNodeType();
-
-                if (t == Node.COMMENT_NODE) {
-                    e1 = e1.getNextSibling();
-                } else if (t == Node.TEXT_NODE) {
-                    String s = e1.getNodeValue().trim();
-                    if (s.length() == 0) {
-                        e1 = e1.getNextSibling();
-                    } else {
-                        break;
-                    }
-                } else {
-                    break;
-                }
-            }
-
-            // Find the next non-whitespace text or non-comment in e2.
-            while (e2 != null) {
-                short t = e2.getNodeType();
-
-                if (t == Node.COMMENT_NODE) {
-                    e2 = e2.getNextSibling();
-                } else if (t == Node.TEXT_NODE) {
-                    String s = e2.getNodeValue().trim();
-                    if (s.length() == 0) {
-                        e2 = e2.getNextSibling();
-                    } else {
-                        break;
-                    }
-                } else {
-                    break;
-                }
-            }
-
-            // Same elements, or both null?
-            if (e1 == e2 || (e1 == null && e2 == null)) {
-                return true;
-            }
-
-            // Is one null but not the other?
-            if ((e1 == null && e2 != null) || (e1 != null && e2 == null)) {
-                break;  // dumpMismatchAndExit
-            }
-
-            assert e1 != null;
-            assert e2 != null;
-
-            // Same type?
-            short t = e1.getNodeType();
-            if (t != e2.getNodeType()) {
-                break;  // dumpMismatchAndExit
-            }
-
-            // Same node name? Must both be null or have the same value.
-            String s1 = e1.getNodeName();
-            String s2 = e2.getNodeName();
-            if ( !( (s1 == null && s2 == null) || (s1 != null && s1.equals(s2)) ) ) {
-                break;  // dumpMismatchAndExit
-            }
-
-            // Same node value? Must both be null or have the same value once whitespace is trimmed.
-            s1 = e1.getNodeValue();
-            s2 = e2.getNodeValue();
-            if (s1 != null) {
-                s1 = s1.trim();
-            }
-            if (s2 != null) {
-                s2 = s2.trim();
-            }
-            if ( !( (s1 == null && s2 == null) || (s1 != null && s1.equals(s2)) ) ) {
-                break;  // dumpMismatchAndExit
-            }
-
+        Map<String, String> nsPrefixE = new HashMap<String, String>();
+        Map<String, String> nsPrefixA = new HashMap<String, String>();
+        String sE = XmlUtils.printElement(expected, nsPrefixE, "");                 //$NON-NLS-1$
+        String sA = XmlUtils.printElement(actual,   nsPrefixA, "");                 //$NON-NLS-1$
+        if (sE.equals(sA)) {
+            return true;
+        } else {
             if (diff != null) {
-                // So far e1 and e2 seem pretty much equal. Dump it to the diff.
-                // We need to print to the diff before dealing with the children or attributes.
-                // Note: diffOffset + 1 because we want to reserve 2 spaces to write -/+
-                diff.append(XmlUtils.dump(e1, diffOffset + 1,
-                                          false /*nextSiblings*/, false /*deep*/, keyAttr));
-            }
-
-            // Now compare the attributes. When using the w3c.DOM this way, attributes are
-            // accessible via the Node/Element attributeMap and are not actually exposed
-            // as ATTR_NODEs in the node list. The downside is that we don't really
-            // have the proper attribute order but that's not an issue as far as the validity
-            // of the XML since attribute order should never matter.
-            List<Attr> a1 = XmlUtils.sortedAttributeList(e1.getAttributes());
-            List<Attr> a2 = XmlUtils.sortedAttributeList(e2.getAttributes());
-            if (a1.size() > 0 || a2.size() > 0) {
-
-                  int count1 = 0;
-                  int count2 = 0;
-                Map<String, AttrDiff> map = new TreeMap<String, AttrDiff>();
-                for (Attr a : a1) {
-                    AttrDiff ad1 = new AttrDiff(a, "--");       //$NON-NLS-1$
-                    map.put(ad1.mKey, ad1);
-                    count1++;
-                }
-
-                for (Attr a : a2) {
-                    AttrDiff ad2 = new AttrDiff(a, "++");       //$NON-NLS-1$
-                    AttrDiff ad1 = map.get(ad2.mKey);
-                    if (ad1 != null) {
-                        ad1.mSide = "  ";                       //$NON-NLS-1$
-                        count1--;
-                    } else {
-                        map.put(ad2.mKey, ad2);
-                        count2++;
-                    }
-                }
-
-                if (count1 != 0 || count2 != 0) {
-                    // We found some items not matching in both sets. Dump the result.
-                    if (diff != null) {
-                        for (AttrDiff ad : map.values()) {
-                            diff.append(ad.mSide)
-                                .append(XmlUtils.dump(ad.mAttr, diffOffset,
-                                                      false /*nextSiblings*/, false /*deep*/,
-                                                      keyAttr));
-                        }
-                    }
-                    // Exit without dumping
-                    return false;
-                }
+                XmlUtils.printXmlDiff(diff, sE, sA, nsPrefixE, nsPrefixA, NS_URI + ':' + keyAttr);
             }
-
-            // Compare recursively for elements.
-            if (t == Node.ELEMENT_NODE &&
-                    !compareElements(
-                            e1.getFirstChild(), e2.getFirstChild(), true,
-                            diff, diffOffset + 1, keyAttr)) {
-                // Exit without dumping since the recursive call take cares of its own diff
-                return false;
-            }
-
-            if (nextSiblings) {
-                e1 = e1.getNextSibling();
-                e2 = e2.getNextSibling();
-                continue;
-            } else {
-                return true;
-            }
-        }
-
-        // <INTERCAL COME FROM dumpMismatchAndExit PLEASE>
-        if (diff != null) {
-            diff.append("--")
-                .append(XmlUtils.dump(e1, diffOffset,
-                                      false /*nextSiblings*/, false /*deep*/, keyAttr));
-            diff.append("++")
-                .append(XmlUtils.dump(e2, diffOffset,
-                                      false /*nextSiblings*/, false /*deep*/, keyAttr));
-        }
-        return false;
-    }
-
-    private static class AttrDiff {
-        public final String mKey;
-        public final Attr mAttr;
-        public String mSide;
-
-        public AttrDiff(Attr attr, String side) {
-            mKey = getKey(attr);
-            mAttr = attr;
-            mSide = side;
-        }
-
-        String getKey(Attr attr) {
-            return String.format("%s=%s", attr.getNodeName(), attr.getNodeValue());
+            return false;
         }
     }
 
@@ -1519,4 +1346,5 @@ public class ManifestMerger {
         return new FileAndLine(name, line);
     }
 
+
 }
diff --git a/manifmerger/src/com/android/manifmerger/XmlUtils.java b/manifmerger/src/com/android/manifmerger/XmlUtils.java
index 7e92d55..71aac91 100755
--- a/manifmerger/src/com/android/manifmerger/XmlUtils.java
+++ b/manifmerger/src/com/android/manifmerger/XmlUtils.java
@@ -39,6 +39,10 @@ import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
 
 import javax.xml.parsers.DocumentBuilder;
 import javax.xml.parsers.DocumentBuilderFactory;
@@ -499,4 +503,296 @@ class XmlUtils {
             }
         };
     }
+
+    // -------
+
+    /**
+     * Flatten the element to a string. This "pretty prints" the XML tree starting
+     * from the given node and all its children and attributes.
+     * <p/>
+     * The output is designed to be printed using {@link #printXmlDiff}.
+     *
+     * @param node The root node to print.
+     * @param nsPrefix A map that is filled with all the URI=>prefix found.
+     *   The internal string only contains the expanded URIs but this is rather verbose
+     *   so when printing the diff these will be replaced by the prefixes collected here.
+     * @param prefix A "space" prefix added at the beginning of each line for indentation
+     *   purposes. The diff printer later relies on this to find out the structure.
+     */
+    @NonNull
+    static String printElement(
+            @NonNull Node node,
+            @NonNull Map<String, String> nsPrefix,
+            @NonNull String prefix) {
+        StringBuilder sb = new StringBuilder();
+        sb.append(prefix).append('<');
+        String uri = node.getNamespaceURI();
+        if (uri != null) {
+            sb.append(uri).append(':');
+            nsPrefix.put(uri, node.getPrefix());
+        }
+        sb.append(node.getLocalName());
+        printAttributes(sb, node, nsPrefix, prefix);
+        sb.append(">\n");                                                           //$NON-NLS-1$
+        printChildren(sb, node.getFirstChild(), true, nsPrefix, prefix + "    "); //$NON-NLS-1$
+
+        sb.append(prefix).append("</");                                             //$NON-NLS-1$
+        if (uri != null) {
+            sb.append(uri).append(':');
+        }
+        sb.append(node.getLocalName());
+        sb.append(">\n");                                                           //$NON-NLS-1$
+
+        return sb.toString();
+    }
+
+    /**
+     * Flatten several children elements to a string.
+     * This is an implementation detail for {@link #printElement(Node, Map, String)}.
+     * <p/>
+     * If {@code nextSiblings} is false, the string conversion takes only the given
+     * child element and stops there.
+     * <p/>
+     * If {@code nextSiblings} is true, the string conversion also takes _all_ the siblings
+     * after the given element. The idea is the caller can call this with the first child
+     * of a parent and get a string showing all the children at the same time. They are
+     * sorted to avoid the ordering issue.
+     */
+    @NonNull
+    private static StringBuilder printChildren(
+            @NonNull StringBuilder sb,
+            @NonNull Node child,
+            boolean nextSiblings,
+            @NonNull Map<String, String> nsPrefix,
+            @NonNull String prefix) {
+        ArrayList<String> children = new ArrayList<String>();
+
+        boolean hasText = false;
+        for (; child != null; child = child.getNextSibling()) {
+            short t = child.getNodeType();
+            if (nextSiblings && t == Node.TEXT_NODE) {
+                // We don't typically have meaningful text nodes in an Android manifest.
+                // If there are, just dump them as-is into the element representation.
+                // We do trim whitespace and ignore all-whitespace or empty text nodes.
+                String s = child.getNodeValue().trim();
+                if (s.length() > 0) {
+                    sb.append(s);
+                    hasText = true;
+                }
+            } else if (t == Node.ELEMENT_NODE) {
+                children.add(printElement(child, nsPrefix, prefix)); //$NON-NLS-1$
+                if (!nextSiblings) {
+                    break;
+                }
+            }
+        }
+
+        if (hasText) {
+            sb.append('\n');
+        }
+
+        if (!children.isEmpty()) {
+            Collections.sort(children);
+            for (String s : children) {
+                sb.append(s);
+            }
+        }
+
+        return sb;
+    }
+
+    /**
+     * Flatten several attributes to a string using their alphabethical order.
+     * This is an implementation detail for {@link #printElement(Node, Map, String)}.
+     */
+    @NonNull
+    private static StringBuilder printAttributes(
+            @NonNull StringBuilder sb,
+            @NonNull Node node,
+            @NonNull Map<String, String> nsPrefix,
+            @NonNull String prefix) {
+        ArrayList<String> attrs = new ArrayList<String>();
+
+        NamedNodeMap attrMap = node.getAttributes();
+        if (attrMap != null) {
+            StringBuilder sb2 = new StringBuilder();
+            for (int i = 0; i < attrMap.getLength(); i++) {
+                Node attr = attrMap.item(i);
+                if (attr instanceof Attr) {
+                    sb2.setLength(0);
+                    sb2.append('@');
+                    String uri = attr.getNamespaceURI();
+                    if (uri != null) {
+                        sb2.append(uri).append(':');
+                        nsPrefix.put(uri, attr.getPrefix());
+                    }
+                    sb2.append(attr.getLocalName());
+                    sb2.append("=\"").append(attr.getNodeValue()).append('\"');     //$NON-NLS-1$
+                    attrs.add(sb2.toString());
+                }
+            }
+        }
+
+        Collections.sort(attrs);
+
+        for(String attr : attrs) {
+            sb.append('\n');
+            sb.append(prefix).append("    ").append(attr);                          //$NON-NLS-1$
+        }
+        return sb;
+    }
+
+    //------------
+
+    /**
+     * Computes a quick diff between two strings generated by
+     * {@link #printElement(Node, Map, String)}.
+     * <p/>
+     * This is a <em>not</em> designed to be a full contextual diff.
+     * It just stops at the first difference found, printing up to 3 lines of diff
+     * and backtracking to add prior contextual information to understand the
+     * structure of the element where the first diff line occured (by printing
+     * each parent found till the root one as well as printing the attribute
+     * named by {@code keyAttr}).
+     *
+     * @param sb The string builder where to output is written.
+     * @param expected The expected XML tree (as generated by {@link #printElement}.)
+     *          For best result this would be the "destination" XML we're merging into,
+     *          e.g. the main manifest.
+     * @param actual   The actual XML tree (as generated by {@link #printElement}.)
+     *          For best result this would be the "source" XML we're merging from,
+     *          e.g. a library manifest.
+     * @param nsPrefixE The map of URI=>prefix for the expected XML tree.
+     * @param nsPrefixA The map of URI=>prefix for the actual XML tree.
+     * @param keyAttr An optional attribute *full* name (uri:local name) to always
+     *          insert when writing the contextual lines before a diff line.
+     *          For example when writing an Activity, it helps to always insert
+     *          the "name" attribute since that's the key element to help the user
+     *          identify which node is being dumped.
+     */
+    static void printXmlDiff(
+            StringBuilder sb,
+            String expected,
+            String actual,
+            Map<String, String> nsPrefixE,
+            Map<String, String> nsPrefixA,
+            String keyAttr) {
+        String[] aE = expected.split("\n");
+        String[] aA = actual.split("\n");
+        int lE = aE.length;
+        int lA = aA.length;
+        int lm = lE < lA ? lA : lE;
+        boolean eofE = false;
+        boolean eofA = false;
+        boolean contextE = true;
+        boolean contextA = true;
+        int numDiff = 0;
+
+        StringBuilder sE = new StringBuilder();
+        StringBuilder sA = new StringBuilder();
+
+        outerLoop: for (int i = 0, iE = 0, iA = 0; i < lm; i++) {
+            if (iE < lE && iA < lA && aE[iE].equals(aA[iA])) {
+                if (numDiff > 0) {
+                    // If we found a difference, stop now.
+                    break outerLoop;
+                }
+                iE++;
+                iA++;
+                continue;
+            } else {
+                // Try to print some context for each side based on previous lines's space prefix.
+                if (contextE) {
+                    if (iE > 0) {
+                        String p = diffGetPrefix(aE[iE]);
+                        for (int kE = iE-1; kE >= 0; kE--) {
+                            if (!aE[kE].startsWith(p)) {
+                                sE.insert(0, '\n').insert(0, diffReplaceNs(aE[kE], nsPrefixE)).insert(0, "  ");
+                                if (p.length() == 0) {
+                                    break;
+                                }
+                                p = diffGetPrefix(aE[kE]);
+                            } else if (aE[kE].contains(keyAttr) || kE == 0) {
+                                sE.insert(0, '\n').insert(0, diffReplaceNs(aE[kE], nsPrefixE)).insert(0, "  ");
+                            }
+                        }
+                    }
+                    contextE = false;
+                }
+                if (iE >= lE) {
+                    if (!eofE) {
+                        sE.append("--(end reached)\n");
+                        eofE = true;
+                    }
+                } else {
+                    sE.append("--").append(diffReplaceNs(aE[iE++], nsPrefixE)).append('\n');
+                }
+
+                if (contextA) {
+                    if (iA > 0) {
+                        String p = diffGetPrefix(aA[iA]);
+                        for (int kA = iA-1; kA >= 0; kA--) {
+                            if (!aA[kA].startsWith(p)) {
+                                sA.insert(0, '\n').insert(0, diffReplaceNs(aA[kA], nsPrefixA)).insert(0, "  ");
+                                p = diffGetPrefix(aA[kA]);
+                                if (p.length() == 0) {
+                                    break;
+                                }
+                            } else if (aA[kA].contains(keyAttr) || kA == 0) {
+                                sA.insert(0, '\n').insert(0, diffReplaceNs(aA[kA], nsPrefixA)).insert(0, "  ");
+                            }
+                        }
+                    }
+                    contextA = false;
+                }
+                if (iA >= lA) {
+                    if (!eofA) {
+                        sA.append("++(end reached)\n");
+                        eofA = true;
+                    }
+                } else {
+                    sA.append("++").append(diffReplaceNs(aA[iA++], nsPrefixA)).append('\n');
+                }
+
+                // Dump up to 3 lines of difference
+                numDiff++;
+                if (numDiff == 3) {
+                    break outerLoop;
+                }
+            }
+        }
+
+        sb.append(sE);
+        sb.append(sA);
+    }
+
+    /**
+     * Returns all the whitespace at the beginning of a string.
+     * Implementation details for {@link #printXmlDiff} used to find the "parent"
+     * element and include it in the context of the diff.
+     */
+    private static String diffGetPrefix(String str) {
+        int pos = 0;
+        int len = str.length();
+        while (pos < len && str.charAt(pos) == ' ') {
+            pos++;
+        }
+        return str.substring(0, pos);
+    }
+
+    /**
+     * Simplifies a diff line by replacing NS URIs by their prefix.
+     * Implementation details for {@link #printXmlDiff}.
+     */
+    private static String diffReplaceNs(String str, Map<String, String> nsPrefix) {
+        for (Entry<String, String> entry : nsPrefix.entrySet()) {
+            String uri = entry.getKey();
+            String prefix = entry.getValue();
+            if (prefix != null && str.contains(uri)) {
+                str = str.replaceAll(Pattern.quote(uri), Matcher.quoteReplacement(prefix));
+            }
+        }
+        return str;
+    }
+
 }
diff --git a/manifmerger/tests/src/com/android/manifmerger/ManifestMergerTest.java b/manifmerger/tests/src/com/android/manifmerger/ManifestMergerTest.java
index 1482792..564fc6d 100755
--- a/manifmerger/tests/src/com/android/manifmerger/ManifestMergerTest.java
+++ b/manifmerger/tests/src/com/android/manifmerger/ManifestMergerTest.java
@@ -145,4 +145,8 @@ public class ManifestMergerTest extends ManifestMergerTestCase {
     public void test56_support_gltext_warning() throws Exception {
         processTestFiles();
     }
+
+    public void test60_merge_order() throws Exception {
+        processTestFiles();
+    }
 }
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/11_activity_dup.xml b/manifmerger/tests/src/com/android/manifmerger/data/11_activity_dup.xml
index 5ba6688..ef163b0 100755
--- a/manifmerger/tests/src/com/android/manifmerger/data/11_activity_dup.xml
+++ b/manifmerger/tests/src/com/android/manifmerger/data/11_activity_dup.xml
@@ -366,22 +366,41 @@
 
 </manifest>
 
+
 @errors
 
 E [ManifestMergerTest0_main.xml:32, ManifestMergerTest1_lib1_widget.xml:16] Trying to merge incompatible /manifest/application/activity[@name=com.example.WidgetConfigurationUI] element:
-  <activity android:name=com.example.WidgetConfigurationUI>
---  <intent-filter>
-++  (end reached)
+  <activity
+      @android:name="com.example.WidgetConfigurationUI"
+--</activity>
+--(end reached)
+  <activity
+      @android:name="com.example.WidgetConfigurationUI"
+++    <intent-filter>
+++        <action
+++            @android:name="android.appwidget.action.APPWIDGET_CONFIGURE">
 E [ManifestMergerTest0_main.xml:38, ManifestMergerTest2_lib2_activity.xml:6] Trying to merge incompatible /manifest/application/activity[@name=com.example.LibActivity] element:
-  <activity android:name=com.example.LibActivity>
-      @android:icon = @drawable/lib_activity_icon
-      @android:label = @string/lib_activity_name
-      @android:name = com.example.LibActivity
---    @android:theme = @style/Lib.Theme
+  <activity
+--    @android:name="com.example.LibActivity">
+--    <intent-filter>
+--        <action
+  <activity
+++    @android:name="com.example.LibActivity"
+++    @android:theme="@style/Lib.Theme">
+++    <intent-filter>
 E [ManifestMergerTest0_main.xml, ManifestMergerTest3_lib3_alias.xml:19] Trying to merge incompatible /manifest/application/activity[@name=com.example.LibActivity2] element:
-  <activity android:name=com.example.LibActivity2>
-    <intent-filter>
-      <action android:name=android.intent.action.MAIN>
-      <category android:name=android.intent.category.LAUNCHER>
---    <category android:name=android.intent.category.MOARCATZPLZ>
-++    (end reached)
+  <activity
+      @android:name="com.example.LibActivity2"
+              @android:name="android.intent.action.MAIN">
+              @android:name="android.intent.category.LAUNCHER">
+--    </intent-filter>
+--</activity>
+--(end reached)
+  <activity
+      @android:name="com.example.LibActivity2"
+      <intent-filter>
+              @android:name="android.intent.action.MAIN">
+              @android:name="android.intent.category.LAUNCHER">
+++        <category
+++            @android:name="android.intent.category.MOARCATZPLZ">
+++        </category>
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/12_alias_dup.xml b/manifmerger/tests/src/com/android/manifmerger/data/12_alias_dup.xml
index 696965f..7b5aed3 100755
--- a/manifmerger/tests/src/com/android/manifmerger/data/12_alias_dup.xml
+++ b/manifmerger/tests/src/com/android/manifmerger/data/12_alias_dup.xml
@@ -192,14 +192,20 @@
 
 P [ManifestMergerTest0_main.xml:6, ManifestMergerTest1_lib1.xml:6] Skipping identical /manifest/application/activity-alias[@name=com.example.alias.MyActivity1] element.
 E [ManifestMergerTest0_main.xml:13, ManifestMergerTest1_lib1.xml:14] Trying to merge incompatible /manifest/application/activity-alias[@name=com.example.alias.MyActivity2] element:
-  <activity-alias android:name=com.example.alias.MyActivity2>
-++    @android:icon = @drawable/alias_icon2
-++    @android:label = @string/alias_name2
-      @android:name = com.example.alias.MyActivity2
-      @android:targetActivity = com.example.MainActivity2
+  <activity-alias
+--    @android:icon="@drawable/alias_icon2"
+--    @android:label="@string/alias_name2"
+--    @android:name="com.example.alias.MyActivity2"
+  <activity-alias
+++    @android:name="com.example.alias.MyActivity2"
+++    @android:targetActivity="com.example.MainActivity2">
+++</activity-alias>
 E [ManifestMergerTest0_main.xml, ManifestMergerTest2_lib2.xml:6] Trying to merge incompatible /manifest/application/activity-alias[@name=com.example.alias.MyActivity3] element:
-  <activity-alias android:name=com.example.alias.MyActivity3>
-      @android:icon = @drawable/alias_icon3
-      @android:label = @string/alias_name3
-      @android:name = com.example.alias.MyActivity3
-++    @android:targetActivity = com.example.MainActivity3
+  <activity-alias
+--    @android:name="com.example.alias.MyActivity3"
+--    @android:targetActivity="com.example.MainActivity3">
+--    <intent-filter>
+  <activity-alias
+++    @android:name="com.example.alias.MyActivity3">
+++    <intent-filter>
+++        <category
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/13_service_dup.xml b/manifmerger/tests/src/com/android/manifmerger/data/13_service_dup.xml
index 36d7e24..4c257fa 100755
--- a/manifmerger/tests/src/com/android/manifmerger/data/13_service_dup.xml
+++ b/manifmerger/tests/src/com/android/manifmerger/data/13_service_dup.xml
@@ -146,10 +146,22 @@
 
 P [ManifestMergerTest0_main.xml:6, ManifestMergerTest1_lib1.xml:6] Skipping identical /manifest/application/service[@name=com.example.AppService1] element.
 E [ManifestMergerTest0_main.xml:8, ManifestMergerTest1_lib1.xml:9] Trying to merge incompatible /manifest/application/service[@name=com.example.AppService2] element:
-  <service android:name=com.example.AppService2>
---  <intent-filter>
-++  (end reached)
+  <service
+      @android:name="com.example.AppService2">
+--</service>
+--(end reached)
+  <service
+      @android:name="com.example.AppService2">
+++    <intent-filter>
+++        <action
+++            @android:name="android.intent.action.MAIN">
 E [ManifestMergerTest0_main.xml, ManifestMergerTest2_lib2.xml:6] Trying to merge incompatible /manifest/application/service[@name=com.example.AppService3] element:
-  <service android:name=com.example.AppService3>
---  (end reached)
-++  <intent-filter>
+  <service
+      @android:name="com.example.AppService3">
+--    <intent-filter>
+--        <action
+--            @android:name="android.intent.action.MAIN">
+  <service
+      @android:name="com.example.AppService3">
+++</service>
+++(end reached)
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/14_receiver_dup.xml b/manifmerger/tests/src/com/android/manifmerger/data/14_receiver_dup.xml
index a2547af..777ba22 100755
--- a/manifmerger/tests/src/com/android/manifmerger/data/14_receiver_dup.xml
+++ b/manifmerger/tests/src/com/android/manifmerger/data/14_receiver_dup.xml
@@ -165,12 +165,22 @@
 
 P [ManifestMergerTest0_main.xml:6, ManifestMergerTest1_lib1.xml:6] Skipping identical /manifest/application/receiver[@name=com.example.AppReceiver1] element.
 E [ManifestMergerTest0_main.xml:12, ManifestMergerTest1_lib1.xml:13] Trying to merge incompatible /manifest/application/receiver[@name=com.example.AppReceiver2] element:
-  <receiver android:name=com.example.AppReceiver2>
-++    @android:icon = @drawable/app_icon
-      @android:name = com.example.AppReceiver2
+  <receiver
+--    @android:icon="@drawable/app_icon"
+--    @android:name="com.example.AppReceiver2">
+--    <intent-filter>
+  <receiver
+++    @android:name="com.example.AppReceiver2">
+++</receiver>
+++(end reached)
 E [ManifestMergerTest0_main.xml, ManifestMergerTest2_lib2.xml:6] Trying to merge incompatible /manifest/application/receiver[@name=com.example.AppReceiver3] element:
-  <receiver android:name=com.example.AppReceiver3>
-    <intent-filter>
-      <action android:name=com.example.action.ACTION_CUSTOM>
---        @android:name = com.example.action.ACTION_CUSTOM
-++        @android:name = com.example.action.ACTION_CUSTOM1
+  <receiver
+      @android:name="com.example.AppReceiver3">
+      <intent-filter>
+          <action
+--            @android:name="com.example.action.ACTION_CUSTOM1">
+  <receiver
+      @android:name="com.example.AppReceiver3">
+      <intent-filter>
+          <action
+++            @android:name="com.example.action.ACTION_CUSTOM">
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/15_provider_dup.xml b/manifmerger/tests/src/com/android/manifmerger/data/15_provider_dup.xml
index 7938c1e..bd0c8fe 100755
--- a/manifmerger/tests/src/com/android/manifmerger/data/15_provider_dup.xml
+++ b/manifmerger/tests/src/com/android/manifmerger/data/15_provider_dup.xml
@@ -134,12 +134,20 @@
 
 P [ManifestMergerTest0_main.xml:6, ManifestMergerTest1_lib1.xml:6] Skipping identical /manifest/application/provider[@name=com.example.Provider1] element.
 E [ManifestMergerTest0_main.xml:8, ManifestMergerTest1_lib1.xml:9] Trying to merge incompatible /manifest/application/provider[@name=com.example.Provider2] element:
-  <provider android:name=com.example.Provider2>
---    @android:authorities = com.example.android.apis.app.thingy2
---    @android:enabled = @bool/someConditionalValue2
-      @android:name = com.example.Provider2
+  <provider
+--    @android:name="com.example.Provider2">
+--</provider>
+--(end reached)
+  <provider
+++    @android:authorities="com.example.android.apis.app.thingy2"
+++    @android:enabled="@bool/someConditionalValue2"
+++    @android:name="com.example.Provider2">
 E [ManifestMergerTest0_main.xml, ManifestMergerTest2_lib2.xml:6] Trying to merge incompatible /manifest/application/provider[@name=com.example.Provider3] element:
-  <provider android:name=com.example.Provider3>
-      @android:authorities = com.example.android.apis.app.thingy3
-++    @android:enabled = @bool/someConditionalValue
-      @android:name = com.example.Provider3
+  <provider
+--    @android:enabled="@bool/someConditionalValue"
+--    @android:name="com.example.Provider3">
+--</provider>
+  <provider
+++    @android:name="com.example.Provider3">
+++</provider>
+++(end reached)
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/26_permission_dup.xml b/manifmerger/tests/src/com/android/manifmerger/data/26_permission_dup.xml
index 3862249..bd9a4f1 100755
--- a/manifmerger/tests/src/com/android/manifmerger/data/26_permission_dup.xml
+++ b/manifmerger/tests/src/com/android/manifmerger/data/26_permission_dup.xml
@@ -269,39 +269,46 @@
 @errors
 
 E [ManifestMergerTest0_main.xml:12, ManifestMergerTest1_lib1.xml:4] Trying to merge incompatible /manifest/permission[@name=com.example.DangerWillRobinson] element:
-  <permission android:name=com.example.DangerWillRobinson>
---    @android:description = Different description here
-++    @android:description = Insert boring description here
---    @android:icon = @drawable/not_the_same_icon
-++    @android:icon = @drawable/robot
-      @android:label = Danger, Will Robinson!
-      @android:name = com.example.DangerWillRobinson
-      @android:permissionGroup = com.example.MasterControlPermission
-      @android:protectionLevel = dangerous
+  <permission
+--    @android:description="Insert boring description here"
+--    @android:icon="@drawable/robot"
+  <permission
+++    @android:description="Different description here"
+++    @android:icon="@drawable/not_the_same_icon"
 E [ManifestMergerTest0_main.xml:14, ManifestMergerTest1_lib1.xml:8] Trying to merge incompatible /manifest/permission[@name=com.example.WhatWereYouThinking] element:
-  <permission android:name=com.example.WhatWereYouThinking>
-      @android:name = com.example.WhatWereYouThinking
-      @android:permissionGroup = com.example.MasterControlPermission
---    @android:protectionLevel = normal
-++    @android:protectionLevel = signatureOrSystem
+  <permission
+      @android:name="com.example.WhatWereYouThinking"
+--    @android:protectionLevel="signatureOrSystem">
+  <permission
+      @android:name="com.example.WhatWereYouThinking"
+++    @android:protectionLevel="normal">
 E [ManifestMergerTest0_main.xml:16, ManifestMergerTest1_lib1.xml:5] Trying to merge incompatible /manifest/permission-group[@name=com.example.MasterControlPermission] element:
-  <permission-group android:name=com.example.MasterControlPermission>
-      @android:description = Nobody expects...
-++    @android:icon = @drawable/ignored_icon
-      @android:label = the Spanish Inquisition
-      @android:name = com.example.MasterControlPermission
+  <permission-group
+--    @android:icon="@drawable/ignored_icon"
+--    @android:label="the Spanish Inquisition"
+--    @android:name="com.example.MasterControlPermission">
+  <permission-group
+++    @android:label="the Spanish Inquisition"
+++    @android:name="com.example.MasterControlPermission">
+++</permission-group>
 E [ManifestMergerTest0_main.xml:18, ManifestMergerTest1_lib1.xml:6] Trying to merge incompatible /manifest/permission-tree[@name=com.example.PermTree] element:
-  <permission-tree android:name=com.example.PermTree>
-++    @android:label = This is not a label
---    @android:label = This is not the same label
-      @android:name = com.example.PermTree
+  <permission-tree
+--    @android:label="This is not a label"
+  <permission-tree
+++    @android:label="This is not the same label"
 E [ManifestMergerTest0_main.xml, ManifestMergerTest2_lib2.xml:6] Trying to merge incompatible /manifest/permission[@name=com.example.Permission1] element:
-  <permission android:name=com.example.Permission1>
-      @android:name = com.example.Permission1
-      @android:permissionGroup = com.example.Permission1
-++    @android:protectionLevel = normal
---    @android:protectionLevel = system
+  <permission
+      @android:name="com.example.Permission1"
+--    @android:protectionLevel="normal">
+  <permission
+      @android:name="com.example.Permission1"
+++    @android:protectionLevel="system">
 E [ManifestMergerTest0_main.xml, ManifestMergerTest2_lib2.xml:7] Trying to merge incompatible /manifest/permission-tree[@name=com.example.PermTree1] element:
-  <permission-tree android:name=com.example.PermTree1>
---    @android:description = Extra description
-      @android:name = com.example.PermTree1
+  <permission-tree
+--    @android:name="com.example.PermTree1">
+--</permission-tree>
+--(end reached)
+  <permission-tree
+++    @android:description="Extra description"
+++    @android:name="com.example.PermTree1">
+++</permission-tree>
diff --git a/manifmerger/tests/src/com/android/manifmerger/data/60_merge_order.xml b/manifmerger/tests/src/com/android/manifmerger/data/60_merge_order.xml
new file mode 100755
index 0000000..e820ecb
--- /dev/null
+++ b/manifmerger/tests/src/com/android/manifmerger/data/60_merge_order.xml
@@ -0,0 +1,317 @@
+#
+# Test:
+# - When activity / activity-alias / service / receiver / provider are merged,
+#   we do a comparison to check whether the elements are already present in the
+#   main manifest.
+# - What this checks is that the order of the elements or attributes within
+#   the elements should not matter.
+#
+
+@main
+
+<manifest
+    xmlns:android="http://schemas.android.com/apk/res/android"
+    package="com.example.app1">
+
+    <application
+        android:label="@string/app_name"
+        android:icon="@drawable/app_icon"
+        android:backupAgent="com.example.app.BackupAgentClass"
+        android:restoreAnyVersion="true"
+        android:allowBackup="true"
+        android:killAfterRestore="true"
+        android:name="com.example.TheApp" >
+
+        <activity
+            android:name="com.example.Activity1"
+            android:label="@string/activity_name"
+            android:icon="@drawable/activity_icon"
+            android:theme="@style/Some.Theme">
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <meta-data
+                android:name="metaName"
+                android:value="metaValue"
+                android:resource="@color/someColor" />
+        </activity>
+
+        <!-- Receiver -->
+        <receiver
+            android:name="com.example.AppReceiver"
+            android:icon="@drawable/app_icon">
+            <intent-filter>
+                <action android:name="android.intent.action.BOOT_COMPLETED" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="com.example.intent.action.DO_THIS" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="com.example.intent.action.DO_THAT" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.TIMEZONE_CHANGED" />
+                <action android:name="android.intent.action.TIME_SET" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.PHONE_STATE"/>
+            </intent-filter>
+        </receiver>
+
+        <activity
+            android:name="com.example.LibActivity"
+            android:label="@string/lib_activity_name"
+            android:icon="@drawable/lib_activity_icon"
+            android:theme="@style/Lib.Theme">
+
+            <!-- When comparing duplicate elements, whitespace and comments are ignored. -->
+
+            <intent-filter>
+                <action android:name="com.example.IN_APP_NOTIFY" />
+                <action android:name="com.example.RESPONSE_CODE" />
+                <action android:name="com.example.PURCHASE_STATE_CHANGED" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <meta-data
+                android:name="metaName2"
+                android:value="metaValue2"
+                android:resource="@color/someColor2"
+            />
+        </activity>
+    </application>
+</manifest>
+
+
+@lib1
+
+<manifest
+    xmlns:android="http://schemas.android.com/apk/res/android"
+    package="com.example.lib1">
+
+    <!-- Redefine the same elements as in the main manifest except it changes
+         the attribute order and the the inner elements order. -->
+    <application
+        android:name="com.example.TheApp"
+        android:icon="@drawable/app_icon"
+        android:label="@string/app_name"
+        android:allowBackup="true"
+        android:killAfterRestore="true"
+        android:restoreAnyVersion="true"
+        android:backupAgent="com.example.app.BackupAgentClass"
+        >
+
+        <!-- Receiver -->
+        <receiver
+            android:icon="@drawable/app_icon"
+            android:name="com.example.AppReceiver"
+            >
+            <intent-filter>
+                <action android:name="android.intent.action.TIME_SET" />
+                <action android:name="android.intent.action.TIMEZONE_CHANGED" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="com.example.intent.action.DO_THIS" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.PHONE_STATE"/>
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.BOOT_COMPLETED" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="com.example.intent.action.DO_THAT" />
+            </intent-filter>
+        </receiver>
+
+        <activity
+            android:theme="@style/Lib.Theme"
+            android:name="com.example.LibActivity"
+            android:icon="@drawable/lib_activity_icon"
+            android:label="@string/lib_activity_name"
+            >
+            <!-- When comparing duplicate elements, whitespace and comments are ignored. -->
+            <intent-filter>
+                <category android:name="android.intent.category.LAUNCHER" />
+                <action android:name="android.intent.action.MAIN" />
+            </intent-filter>
+            <meta-data
+                android:resource="@color/someColor2"
+                android:value="metaValue2"
+                android:name="metaName2">
+            </meta-data>
+            <intent-filter>
+                <action android:name="com.example.IN_APP_NOTIFY" />
+                <action android:name="com.example.PURCHASE_STATE_CHANGED" />
+                <action android:name="com.example.RESPONSE_CODE" />
+            </intent-filter>
+        </activity>
+
+        <activity
+            android:icon="@drawable/activity_icon"
+            android:label="@string/activity_name"
+            android:name="com.example.Activity1"
+            android:theme="@style/Some.Theme">
+            <meta-data
+                android:value="metaValue"
+                android:name="metaName"
+                android:resource="@color/someColor" />
+            <intent-filter>
+                <category android:name="android.intent.category.LAUNCHER" />
+                <action android:name="android.intent.action.MAIN" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+        </activity>
+    </application>
+
+</manifest>
+
+
+@lib2
+
+<manifest
+    xmlns:android="http://schemas.android.com/apk/res/android"
+    package="com.example.lib2">
+
+    <application
+        android:label="@string/app_name"
+        android:icon="@drawable/app_icon"
+        android:backupAgent="com.example.app.BackupAgentClass"
+        android:restoreAnyVersion="true"
+        android:allowBackup="true"
+        android:killAfterRestore="true"
+        android:name="com.example.TheApp" >
+
+        <!-- The whitespace and alignment is also drastically different here and has
+             no impact whatsoever on the content's comparison.
+             Some empty elements have been 'uncollapsed' with their closing element separated. -->
+        <activity android:label="@string/activity_name" android:icon="@drawable/activity_icon" android:theme="@style/Some.Theme" android:name="com.example.Activity1">
+            <intent-filter><action android:name="android.intent.action.MAIN" /><category android:name="android.intent.category.LAUNCHER" /></intent-filter>
+            <intent-filter><action android:name="android.intent.action.MAIN" /><category android:name="android.intent.category.LAUNCHER" /></intent-filter>
+            <meta-data android:value="metaValue" android:resource="@color/someColor" android:name="metaName" />
+        </activity>
+        <activity android:label="@string/lib_activity_name" android:icon="@drawable/lib_activity_icon" android:name="com.example.LibActivity" android:theme="@style/Lib.Theme"><intent-filter>
+            <action android:name="com.example.IN_APP_NOTIFY" /> <action android:name="com.example.RESPONSE_CODE" /> <action android:name="com.example.PURCHASE_STATE_CHANGED" />
+            </intent-filter>
+            <intent-filter><action android:name="android.intent.action.MAIN" /><category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <meta-data android:name="metaName2" android:value="metaValue2" android:resource="@color/someColor2"
+            />
+        </activity>
+
+        <!-- Receiver -->
+        <receiver android:icon="@drawable/app_icon" android:name="com.example.AppReceiver" >
+            <intent-filter><action android:name="android.intent.action.TIME_SET"></action>
+                <action android:name="android.intent.action.TIMEZONE_CHANGED" /></intent-filter>
+            <intent-filter><action android:name="android.intent.action.PHONE_STATE" >
+                </action></intent-filter>
+            <intent-filter><action android:name="android.intent.action.BOOT_COMPLETED" />
+            </intent-filter>
+            <intent-filter><action android:name="com.example.intent.action.DO_THIS" /></intent-filter>
+            <intent-filter><action android:name="com.example.intent.action.DO_THAT" /></intent-filter>
+        </receiver>
+    </application>
+</manifest>
+
+
+
+@result
+
+<manifest
+    xmlns:android="http://schemas.android.com/apk/res/android"
+    package="com.example.app1">
+
+    <application
+        android:label="@string/app_name"
+        android:icon="@drawable/app_icon"
+        android:backupAgent="com.example.app.BackupAgentClass"
+        android:restoreAnyVersion="true"
+        android:allowBackup="true"
+        android:killAfterRestore="true"
+        android:name="com.example.TheApp" >
+
+        <activity
+            android:name="com.example.Activity1"
+            android:label="@string/activity_name"
+            android:icon="@drawable/activity_icon"
+            android:theme="@style/Some.Theme">
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <meta-data
+                android:name="metaName"
+                android:value="metaValue"
+                android:resource="@color/someColor" />
+        </activity>
+
+        <!-- Receiver -->
+        <receiver
+            android:name="com.example.AppReceiver"
+            android:icon="@drawable/app_icon">
+            <intent-filter>
+                <action android:name="android.intent.action.BOOT_COMPLETED" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="com.example.intent.action.DO_THIS" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="com.example.intent.action.DO_THAT" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.TIMEZONE_CHANGED" />
+                <action android:name="android.intent.action.TIME_SET" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.PHONE_STATE"/>
+            </intent-filter>
+        </receiver>
+
+        <activity
+            android:name="com.example.LibActivity"
+            android:label="@string/lib_activity_name"
+            android:icon="@drawable/lib_activity_icon"
+            android:theme="@style/Lib.Theme">
+
+            <!-- When comparing duplicate elements, whitespace and comments are ignored. -->
+
+            <intent-filter>
+                <action android:name="com.example.IN_APP_NOTIFY" />
+                <action android:name="com.example.RESPONSE_CODE" />
+                <action android:name="com.example.PURCHASE_STATE_CHANGED" />
+            </intent-filter>
+            <intent-filter>
+                <action android:name="android.intent.action.MAIN" />
+                <category android:name="android.intent.category.LAUNCHER" />
+            </intent-filter>
+            <meta-data
+                android:name="metaName2"
+                android:value="metaValue2"
+                android:resource="@color/someColor2"
+            />
+        </activity>
+    </application>
+</manifest>
+
+@errors
+
+P [ManifestMergerTest0_main.xml:37, ManifestMergerTest1_lib1.xml:26] Skipping identical /manifest/application/activity[@name=com.example.LibActivity] element.
+P [ManifestMergerTest0_main.xml:5, ManifestMergerTest1_lib1.xml:41] Skipping identical /manifest/application/activity[@name=com.example.Activity1] element.
+P [ManifestMergerTest0_main.xml:18, ManifestMergerTest1_lib1.xml:7] Skipping identical /manifest/application/receiver[@name=com.example.AppReceiver] element.
+P [ManifestMergerTest0_main.xml:5, ManifestMergerTest2_lib2.xml:6] Skipping identical /manifest/application/activity[@name=com.example.Activity1] element.
+P [ManifestMergerTest0_main.xml:37, ManifestMergerTest2_lib2.xml:11] Skipping identical /manifest/application/activity[@name=com.example.LibActivity] element.
+P [ManifestMergerTest0_main.xml:18, ManifestMergerTest2_lib2.xml:20] Skipping identical /manifest/application/receiver[@name=com.example.AppReceiver] element.