/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * 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.android.manifmerger;

import com.android.SdkConstants;
import com.android.annotations.NonNull;
import com.android.annotations.Nullable;
import com.android.manifmerger.IMergerLog.FileAndLine;
import com.android.manifmerger.IMergerLog.Severity;
import com.android.xml.AndroidXPathFactory;

import org.w3c.dom.Attr;
import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;

import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

import javax.xml.xpath.XPath;
import javax.xml.xpath.XPathConstants;
import javax.xml.xpath.XPathExpressionException;

/**
 * Merges a library manifest into a main application manifest.
 * <p/>
 * To use, create with {@link ManifestMerger#ManifestMerger(IMergerLog, ICallback)} then
 * call {@link ManifestMerger#process(File, File, File[])}.
 * <p/>
 * <pre> Merge operations:
 * - root manifest: attributes ignored, warn if defined.
 * - application:
 *      G- {@code @attributes}: most attributes are ignored in libs
 *          except: application:name if defined, it must match.
 *          except: application:agentBackup if defined, it must match.
 *          (these represent class names and we don't want a lib to assume their app or backup
 *           classes are being used when that will never be the case.)
 *      C- activity / activity-alias / service / receiver / provider
 *          => Merge as-is. Error if exists in the destination (same {@code @name})
 *             unless the definitions are exactly the same.
 *             New elements are always merged at the end of the application element.
 *          => Indicate if there's a dup.
 *      D- uses-library
 *          => Merge. OK if already exists same {@code @name}.
 *          => Merge {@code @required}: true>false.
 * A- instrumentation:
 *      => Do not merge. ignore the ones from libs.
 * C- permission / permission-group / permission-tree:
 *      => Merge as-is. Error if exists in the destination (same {@code @name})
 *         unless the definitions are exactly the same.
 * C- uses-permission:
 *      => Add. OK if already defined.
 * E- uses-sdk:
 *      {@code @minSdkVersion}: error if dest&lt;lib. Never automatically change dest minsdk.
 *                              Codenames are accepted if we can resolve their API level.
 *      {@code @targetSdkVersion}: warning if dest&lt;lib.
 *                                 Never automatically change dest targetsdk.
 *      {@code @maxSdkVersion}: obsolete, ignored. Not used in comparisons and not merged.
 * D- uses-feature with {@code @name}:
 *      => Merge with same {@code @name}
 *      => Merge {@code @required}: true>false.
 *      - Do not merge any {@code @glEsVersion} attribute at this point.
 * F- uses-feature with {@code @glEsVersion}:
 *      => Error if defined in lib+dest with dest&lt;lib. Never automatically change dest.
 * B- uses-configuration:
 *      => There can be many. Error if source defines one that is not an exact match in dest.
 *      (e.g. right now app must manually define something that matches exactly each lib)
 * B- supports-screens / compatible-screens:
 *      => Do not merge.
 *      => Error (warn?) if defined in lib and not strictly the same as in dest.
 * B- supports-gl-texture:
 *      => Do not merge. Can have more than one.
 *      => Error (warn?) if defined in lib and not present as-is in dest.
 *
 * Strategies:
 * A = Ignore, do not merge (no-op).
 * B = Do not merge but if defined in both must match equally.
 * C = Must not exist in dest or be exactly the same (key is the {@code @name} attribute).
 * D = Add new or merge with same key {@code @name}, adjust {@code @required} true>false.
 * E, F, G = Custom strategies; see above.
 *
 * What happens when merging libraries with conflicting information?
 * Say for example a main manifest has a minSdkVersion of 3, whereas libraries have
 * a minSdkVersion of 4 and 11. We could have 2 point of views:
 * - Play it safe: If we have a library with a minSdkVersion of 11, it means this
 *   library code knows it can't work reliably on a lower API level. So the safest end
 *   result would be a merged manifest with the highest minSdkVersion of all libraries.
 * - Trust the main manifest: When an app declares a given minSdkVersion, it also expects
 *   to run a given range of devices. If we change the final minSdkVersion, the app won't
 *   be available on as many devices as the developer might expect. And as a counterpoint
 *   to issue 1, the app may be careful and not call the library without checking the
 *   necessary features or APIs are available before hand.
 * Both points of views are conflicting. The solution taken here is to be conservative
 * and generate an error rather than merge and change a value that might be surprising.
 * On the other hand this can be problematic and force a developer to keep the main
 * manifest in sync with the libraries ones, in essence reducing the usefulness of the
 * automated merge to pure trivial cases. The idea is to just start this way and enhance
 * or revisit the mechanism later.
 * </pre>
 */
public class ManifestMerger {

    /** Logger object. Never null. */
    private final IMergerLog mLog;
    /** An optional callback that the merger can use to query the calling SDK. */
    private final ICallback mCallback;
    private XPath mXPath;
    private Document mMainDoc;

    private String NS_URI = SdkConstants.NS_RESOURCES;
    private String NS_PREFIX = AndroidXPathFactory.DEFAULT_NS_PREFIX;
    private int destMinSdk;

    /**
     * Sets of element/attribute that need to be treated as class names.
     * The attribute name must be the local name for the Android namespace.
     * For example "application/name" maps to &lt;application android:name=...&gt;.
     */
    private static final String[] sClassAttributes = {
            "application/name",
            "application/backupAgent",
            "activity/name",
            "receiver/name",
            "service/name",
            "provider/name",
            "instrumentation/name"
    };

    /**
     * Creates a new {@link ManifestMerger}.
     *
     * @param log A non-null merger log to capture all warnings, errors and their location.
     * @param callback An optional callback that the merger can use to query the calling SDK.
     */
    public ManifestMerger(@NonNull IMergerLog log, @Nullable ICallback callback) {
        mLog = log;
        mCallback = callback;
    }

    /**
     * Performs the merge operation.
     * <p/>
     * This does NOT stop on errors, in an attempt to accumulate as much
     * info as possible to return to the user.
     * Unless it failed to read the main manifest, a result file will be
     * created. However if process() returns false, the file should not
     * be used except for debugging purposes.
     *
     * @param outputFile The output path to generate. Can be the same as the main path.
     * @param mainFile The main manifest paths to read. What we merge into.
     * @param libraryFiles The library manifest paths to read. Must not be null.
     * @return True if the merge was completed, false otherwise.
     */
    public boolean process(File outputFile, File mainFile, File[] libraryFiles) {
        Document mainDoc = XmlUtils.parseDocument(mainFile, mLog);
        if (mainDoc == null) {
            return false;
        }

        boolean success = process(mainDoc, libraryFiles);

        if (!XmlUtils.printXmlFile(mainDoc, outputFile, mLog)) {
            success = false;
        }
        return success;
    }

    /**
     * Performs the merge operation in-place in the given DOM.
     * <p/>
     * This does NOT stop on errors, in an attempt to accumulate as much
     * info as possible to return to the user.
     * <p/>
     * The method might modify the input XML document in-place for its own processing.
     *
     * @param mainDoc The document to merge into. Will be modified in-place.
     * @param libraryFiles The library manifest paths to read. Must not be null.
     *                     These will be modified in-place.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    public boolean process(Document mainDoc, File[] libraryFiles) {

        boolean success = true;
        mMainDoc = mainDoc;
        XmlUtils.decorateDocument(mainDoc, IMergerLog.MAIN_MANIFEST);

        String prefix = XmlUtils.lookupNsPrefix(mainDoc, SdkConstants.NS_RESOURCES);
        mXPath = AndroidXPathFactory.newXPath(prefix);

        expandFqcns(mainDoc);
        for (File libFile : libraryFiles) {
            Document libDoc = XmlUtils.parseDocument(libFile, mLog);
            if (libDoc == null || !mergeLibDoc(libDoc)) {
                success = false;
            }
        }

        mXPath = null;
        mMainDoc = null;
        return success;
    }

    /**
     * Performs the merge operation in-place in the given DOM.
     * <p/>
     * This does NOT stop on errors, in an attempt to accumulate as much
     * info as possible to return to the user.
     * <p/>
     * The method might modify the input XML documents in-place for its own processing.
     *
     * @param mainDoc The document to merge into. Will be modified in-place.
     * @param libraryDocs The library manifest documents to merge in. Must not be null.
     *                    These will be modified in-place.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    public boolean process(@NonNull Document mainDoc, @NonNull Document... libraryDocs) {

        boolean success = true;
        mMainDoc = mainDoc;
        XmlUtils.decorateDocument(mainDoc, IMergerLog.MAIN_MANIFEST);

        String prefix = XmlUtils.lookupNsPrefix(mainDoc, SdkConstants.NS_RESOURCES);
        mXPath = AndroidXPathFactory.newXPath(prefix);

        expandFqcns(mainDoc);
        for (Document libDoc : libraryDocs) {
            XmlUtils.decorateDocument(libDoc, IMergerLog.LIBRARY);
            if (!mergeLibDoc(libDoc)) {
                success = false;
            }
        }

        mXPath = null;
        mMainDoc = null;
        return success;
    }

    // --------

    /**
     * Merges the given library manifest into the destination manifest.
     * See {@link ManifestMerger} for merge details.
     *
     * @param libDoc The library document to merge from. Must not be null.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean mergeLibDoc(Document libDoc) {

        boolean err = false;

        expandFqcns(libDoc);

        // Strategy G (check <application> is compatible)
        err |= !checkApplication(libDoc);

        // Strategy B
        err |= !doNotMergeCheckEqual("/manifest/uses-configuration",  libDoc);     //$NON-NLS-1$
        err |= !doNotMergeCheckEqual("/manifest/supports-screens",    libDoc);     //$NON-NLS-1$
        err |= !doNotMergeCheckEqual("/manifest/compatible-screens",  libDoc);     //$NON-NLS-1$
        err |= !doNotMergeCheckEqual("/manifest/supports-gl-texture", libDoc);     //$NON-NLS-1$

        // Strategy C
        err |= !mergeNewOrEqual(
                    "/manifest/application/activity",                               //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    true);
        err |= !mergeNewOrEqual(
                    "/manifest/application/activity-alias",                         //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    true);
        err |= !mergeNewOrEqual(
                    "/manifest/application/service",                                //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    true);
        err |= !mergeNewOrEqual(
                    "/manifest/application/receiver",                               //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    true);
        err |= !mergeNewOrEqual(
                    "/manifest/application/provider",                               //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    true);
        err |= !mergeNewOrEqual(
                    "/manifest/permission",                                         //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    false);
        err |= !mergeNewOrEqual(
                    "/manifest/permission-group",                                   //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    false);
        err |= !mergeNewOrEqual(
                    "/manifest/permission-tree",                                    //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    false);
        err |= !mergeNewOrEqual(
                    "/manifest/uses-permission",                                    //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    libDoc,
                    false);

        // Strategy D
        err |= !mergeAdjustRequired(
                    "/manifest/application/uses-library",                           //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    "required",                                                     //$NON-NLS-1$
                    libDoc,
                    null /*alternateKeyAttr*/);
        err |= !mergeAdjustRequired(
                    "/manifest/uses-feature",                                       //$NON-NLS-1$
                    "name",                                                         //$NON-NLS-1$
                    "required",                                                     //$NON-NLS-1$
                    libDoc,
                    "glEsVersion" /*alternateKeyAttr*/);

        // Strategy E
        err |= !checkSdkVersion(libDoc);

        // Strategy F
        err |= !checkGlEsVersion(libDoc);

        return !err;
    }

    /**
     * Expand all possible class names attributes in the given document.
     * <p/>
     * Some manifest attributes represent class names. These can be specified as fully
     * qualified class names or use a short notation consisting of just the terminal
     * class simple name or a dot followed by a partial class name. Unfortunately this
     * makes textual comparison of the attributes impossible. To simplify this, we can
     * modify the document to fully expand all these class names. The list of elements
     * and attributes to process is listed by {@link #sClassAttributes} and the expansion
     * simply consists of appending the manifest' package if defined.
     *
     * @param doc The document in which to expand potential FQCNs.
     */
    private void expandFqcns(Document doc) {
        // Find the package attribute of the manifest.
        String pkg = null;
        Element manifest = findFirstElement(doc, "/manifest");
        if (manifest != null) {
            pkg = manifest.getAttribute("package");
        }

        if (pkg == null || pkg.length() == 0) {
            // We can't adjust FQCNs if we don't know the root package name.
            // It's not a proper manifest if this is missing anyway.
            assert manifest != null;
            mLog.error(Severity.WARNING,
                       xmlFileAndLine(manifest),
                       "Missing 'package' attribute in manifest.");
            return;
        }

        for (String elementAttr : sClassAttributes) {
            String[] names = elementAttr.split("/");
            if (names.length != 2) {
                continue;
            }
            String elemName = names[0];
            String attrName = names[1];
            NodeList elements = doc.getElementsByTagName(elemName);
            for (int i = 0; i < elements.getLength(); i++) {
                Node elem = elements.item(i);
                if (elem instanceof Element) {
                    Attr attr = ((Element) elem).getAttributeNodeNS(NS_URI, attrName);
                    if (attr != null) {
                        String value = attr.getNodeValue();

                        // We know it's a shortened FQCN if it starts with a dot
                        // or does not contain any dot.
                        if (value != null && value.length() > 0 &&
                                (value.indexOf('.') == -1 || value.charAt(0) == '.')) {
                            if (value.charAt(0) == '.') {
                                value = pkg + value;
                            } else {
                                value = pkg + '.' + value;
                            }
                            attr.setNodeValue(value);
                        }
                    }
                }
            }
        }
    }

    /**
     * Checks (but does not merge) the application attributes using the following rules:
     * <pre>
     * - {@code @name}: Ignore if empty. Warning if its expanded FQCN doesn't match the main doc.
     * - {@code @backupAgent}:  Ignore if empty. Warning if its expanded FQCN doesn't match main doc.
     * - All other attributes are ignored.
     * </pre>
     * The name and backupAgent represent classes and the merger will warn since if a lib has
     * these defined they will never be used anyway.
     * @param libDoc The library document to merge from. Must not be null.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean checkApplication(Document libDoc) {

        Element mainApp = findFirstElement(mMainDoc, "/manifest/application");  //$NON-NLS-1$
        Element libApp  = findFirstElement(libDoc,   "/manifest/application");  //$NON-NLS-1$

        // A manifest does not necessarily define an application.
        // If the lib has none, there's nothing to check for.
        if (libApp == null) {
            return true;
        }

        for (String attrName : new String[] { "name", "backupAgent" }) {
            String libValue  = getAttributeValue(libApp, attrName);
            if (libValue == null || libValue.length() == 0) {
                // Nothing to do if the attribute is not defined in the lib.
                continue;
            }
            // The main doc does not have to have an application node.
            String mainValue = mainApp == null ? "" : getAttributeValue(mainApp, attrName);
            if (!libValue.equals(mainValue)) {
                assert mainApp != null;
                mLog.conflict(Severity.WARNING,
                        xmlFileAndLine(mainApp),
                        xmlFileAndLine(libApp),
                        mainApp == null ?
                            "Library has <application android:%1$s='%3$s'> but main manifest has no application element." :
                            "Main manifest has <application android:%1$s='%2$s'> but library uses %1$s='%3$s'.",
                        attrName,
                        mainValue,
                        libValue);
            }
        }

        return true;
    }

    /**
     * Do not merge anything. Instead it checks that the requested elements from the
     * given library are all present and equal in the destination and prints a warning
     * if it's not the case.
     * <p/>
     * For example if a library supports a given screen configuration, print a
     * warning if the main manifest doesn't indicate the app supports the same configuration.
     * We should not merge it since we don't want to silently give the impression an app
     * supports a configuration just because it uses a library which does.
     * On the other hand we don't want to silently ignore this fact.
     * <p/>
     * TODO there should be a way to silence this warning.
     * The current behavior is certainly arbitrary and needs to be tweaked somehow.
     *
     * @param path The XPath of the elements to merge from the library. Must not be null.
     * @param libDoc The library document to merge from. Must not be null.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean doNotMergeCheckEqual(String path, Document libDoc) {

        for (Element src : findElements(libDoc, path)) {

            boolean found = false;

            for (Element dest : findElements(mMainDoc, path)) {
                if (compareElements(src, dest, false, null /*diff*/, null /*keyAttr*/)) {
                    found = true;
                    break;
                }
            }

            if (!found) {
                mLog.conflict(Severity.WARNING,
                        xmlFileAndLine(mMainDoc),
                        xmlFileAndLine(src),
                        "%1$s defined in library, missing from main manifest:\n%2$s",
                        path,
                        XmlUtils.dump(src, false /*nextSiblings*/));
            }
        }

        return true;
    }

    /**
     * Merges the requested elements from the library in the main document.
     * The key attribute name is used to identify the same elements.
     * Merged elements must either not exist in the destination or be identical.
     * <p/>
     * When merging, append to the end of the application element.
     * Also merges any preceding whitespace and up to one comment just prior to the merged element.
     *
     * @param path The XPath of the elements to merge from the library. Must not be null.
     * @param keyAttr The Android-namespace attribute used as key to identify similar elements.
     *   E.g. "name" for "android:name"
     * @param libDoc The library document to merge from. Must not be null.
     * @param warnDups When true, will print a warning when a library definition is already
     *   present in the destination and is equal.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean mergeNewOrEqual(
            String path,
            String keyAttr,
            Document libDoc,
            boolean warnDups) {

        // The parent of XPath /p1/p2/p3 is /p1/p2. To find it, delete the last "/segment"
        int pos = path.lastIndexOf('/');
        assert pos > 1;
        String parentPath = path.substring(0, pos);
        Element parent = findFirstElement(mMainDoc, parentPath);
        assert parent != null;
        if (parent == null) {
            mLog.error(Severity.ERROR,
                    xmlFileAndLine(mMainDoc),
                    "Could not find element %1$s.",
                    parentPath);
            return false;
        }

        boolean success = true;

        nextSource: for (Element src : findElements(libDoc, path)) {
            String name = getAttributeValue(src, keyAttr);
            if (name.length() == 0) {
                mLog.error(Severity.ERROR,
                        xmlFileAndLine(src),
                        "Undefined '%1$s' attribute in %2$s.",
                        keyAttr, path);
                success = false;
                continue;
            }

            // Look for the same item in the destination
            List<Element> dests = findElements(mMainDoc, path, keyAttr, name);
            if (dests.size() > 1) {
                // This should not be happening. We'll just use the first one found in this case.
                mLog.error(Severity.WARNING,
                        xmlFileAndLine(dests.get(0)),
                        "Manifest has more than one %1$s[@%2$s=%3$s] element.",
                        path, keyAttr, name);
            }
            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)) {
                    // Same element. Skip.
                    if (warnDups) {
                        mLog.conflict(Severity.INFO,
                                xmlFileAndLine(dest),
                                xmlFileAndLine(src),
                                "Skipping identical %1$s[@%2$s=%3$s] element.",
                                path, keyAttr, name);
                    }
                    continue nextSource;
                } else {
                    // Print the diff we got from the comparison.
                    mLog.conflict(Severity.ERROR,
                            xmlFileAndLine(dest),
                            xmlFileAndLine(src),
                            "Trying to merge incompatible %1$s[@%2$s=%3$s] element:\n%4$s",
                            path, keyAttr, name, diff.toString());
                    success = false;
                    continue nextSource;
                }
            }

            // Ready to merge element src. Select which previous siblings to merge.
            Node start = selectPreviousSiblings(src);

            insertAtEndOf(parent, start, src);
        }

        return success;
    }

    /**
     * Returns the value of the given "android:attribute" in the given element.
     *
     * @param element The non-null element where to extract the attribute.
     * @param attrName The local name of the attribute.
     *                 It must use the {@link #NS_URI} but no prefix should be specified here.
     * @return The value of the attribute or a non-null empty string if not found.
     */
    private String getAttributeValue(Element element, String attrName) {
        Attr attr = element.getAttributeNodeNS(NS_URI, attrName);
        String value = attr == null ? "" : attr.getNodeValue();  //$NON-NLS-1$
        return value;
    }

    /**
     * Merge elements as identified by their key name attribute.
     * The element must have an option boolean "required" attribute which can be either "true" or
     * "false". Default is true if the attribute is misisng. When merging, a "false" is superseded
     * by a "true" (explicit or implicit).
     * <p/>
     * When merging, this does NOT merge any other attributes than {@code keyAttr} and
     * {@code requiredAttr}.
     *
     * @param path The XPath of the elements to merge from the library. Must not be null.
     * @param keyAttr The Android-namespace attribute used as key to identify similar elements.
     *   E.g. "name" for "android:name"
     * @param requiredAttr The name of the Android-namespace boolean attribute that must be merged.
     *   Typically should be "required".
     * @param libDoc The library document to merge from. Must not be null.
     * @param alternateKeyAttr When non-null, this is an alternate valid key attribute. If the
     *   default key attribute is missing, we won't output a warning if the alternate one is
     *   present.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean mergeAdjustRequired(
            String path,
            String keyAttr,
            String requiredAttr,
            Document libDoc,
            @Nullable String alternateKeyAttr) {

        // The parent of XPath /p1/p2/p3 is /p1/p2. To find it, delete the last "/segment"
        int pos = path.lastIndexOf('/');
        assert pos > 1;
        String parentPath = path.substring(0, pos);
        Element parent = findFirstElement(mMainDoc, parentPath);
        assert parent != null;
        if (parent == null) {
            mLog.error(Severity.ERROR,
                    xmlFileAndLine(mMainDoc),
                    "Could not find element %1$s.",
                    parentPath);
            return false;
        }

        boolean success = true;

        for (Element src : findElements(libDoc, path)) {
            Attr attr = src.getAttributeNodeNS(NS_URI, keyAttr);
            String name = attr == null ? "" : attr.getNodeValue().trim();  //$NON-NLS-1$
            if (name.length() == 0) {
                if (alternateKeyAttr != null) {
                    attr = src.getAttributeNodeNS(NS_URI, alternateKeyAttr);
                    String s = attr == null ? "" : attr.getNodeValue().trim(); //$NON-NLS-1$
                    if (s.length() != 0) {
                        // This element lacks the keyAttr but has the alternateKeyAttr. Skip it.
                        continue;
                    }
                }

                mLog.error(Severity.ERROR,
                        xmlFileAndLine(src),
                        "Undefined '%1$s' attribute in %2$s.",
                        keyAttr, path);
                success = false;
                continue;
            }

            // Look for the same item in the destination
            List<Element> dests = findElements(mMainDoc, path, keyAttr, name);
            if (dests.size() > 1) {
                // This should not be happening. We'll just use the first one found in this case.
                mLog.error(Severity.WARNING,
                        xmlFileAndLine(dests.get(0)),
                        "Manifest has more than one %1$s[@%2$s=%3$s] element.",
                        path, keyAttr, name);
            }
            if (dests.size() > 0) {
                attr = src.getAttributeNodeNS(NS_URI, requiredAttr);
                String value = attr == null ? "true" : attr.getNodeValue();    //$NON-NLS-1$
                if (value == null || !(value.equals("true") || value.equals("false"))) {
                    mLog.error(Severity.WARNING,
                            xmlFileAndLine(src),
                            "Invalid attribute '%1$s' in %2$s[@%3$s=%4$s] element:\nExpected 'true' or 'false' but found '%5$s'.",
                            requiredAttr, path, keyAttr, name, value);
                    continue;
                }
                boolean boolE = Boolean.parseBoolean(value);

                for (Element dest : dests) {
                    // Destination node exists. Compare the required attributes.

                    attr = dest.getAttributeNodeNS(NS_URI, requiredAttr);
                    value = attr == null ? "true" : attr.getNodeValue();    //$NON-NLS-1$
                    if (value == null || !(value.equals("true") || value.equals("false"))) {
                        mLog.error(Severity.WARNING,
                                xmlFileAndLine(dest),
                                "Invalid attribute '%1$s' in %2$s[@%3$s=%4$s] element:\nExpected 'true' or 'false' but found '%5$s'.",
                                requiredAttr, path, keyAttr, name, value);
                        continue;
                    }
                    boolean boolD = Boolean.parseBoolean(value);

                    if (!boolD && boolE) {
                        // Required attributes differ: destination is false and source was true
                        // so we need to change the destination to true.

                        // If attribute was already in the destination, change it in place
                        if (attr != null) {
                            attr.setNodeValue("true");                        //$NON-NLS-1$
                        } else {
                            // Otherwise, do nothing. The destination doesn't have the
                            // required=true attribute, and true is the default value.
                            // Consequently not setting is the right thing to do.

                            // -- code snippet for reference --
                            // If we wanted to create a new attribute, we'd use the code
                            // below. There's a simpler call to d.setAttributeNS(ns, name, value)
                            // but experience shows that it would create a new prefix out of the
                            // blue instead of looking it up.
                            //
                            // Attr a=d.getOwnerDocument().createAttributeNS(NS_URI, requiredAttr);
                            // String prefix = d.lookupPrefix(NS_URI);
                            // if (prefix != null) {
                            //     a.setPrefix(prefix);
                            // }
                            // a.setValue("true");  //$NON-NLS-1$
                            // d.setAttributeNodeNS(attr);
                        }
                    }
                }
            } else {
                // Destination doesn't exist. We simply merge the source element.
                // Select which previous siblings to merge.
                Node start = selectPreviousSiblings(src);

                Node node = insertAtEndOf(parent, start, src);

                NamedNodeMap attrs = node.getAttributes();
                if (attrs != null) {
                    for (int i = 0; i < attrs.getLength(); i++) {
                        Node a = attrs.item(i);
                        if (a.getNodeType() == Node.ATTRIBUTE_NODE) {
                            boolean keep = NS_URI.equals(a.getNamespaceURI());
                            if (keep) {
                                name = a.getLocalName();
                                keep = keyAttr.equals(name) || requiredAttr.equals(name);
                            }
                            if (!keep) {
                                attrs.removeNamedItemNS(NS_URI, name);
                                // Restart the loop from index 0 since there's no
                                // guarantee on the order of the nodes in the "map".
                                // This makes it O(n+2n) at most, where n is [2..3] in
                                // a typical case.
                                i = -1;
                            }
                        }
                    }
                }
            }
        }

        return success;
    }


    /**
     * Checks (but does not merge) uses-feature glEsVersion attribute using the following rules:
     * <pre>
     * - Error if defined in lib+dest with dest&lt;lib.
     * - Never automatically change dest.
     * - Default implied value is 1.0 (0x00010000).
     * </pre>
     *
     * @param libDoc The library document to merge from. Must not be null.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean checkGlEsVersion(Document libDoc) {

        String parentPath = "/manifest";                                    //$NON-NLS-1$
        Element parent = findFirstElement(mMainDoc, parentPath);
        assert parent != null;
        if (parent == null) {
            mLog.error(Severity.ERROR,
                    xmlFileAndLine(mMainDoc),
                    "Could not find element %1$s.",
                    parentPath);
            return false;
        }

        // Find the max glEsVersion on the destination side
        String path = "/manifest/uses-feature";                             //$NON-NLS-1$
        String keyAttr = "glEsVersion";                                     //$NON-NLS-1$
        long destGlEsVersion = 0x00010000L; // default minimum is 1.0
        Element destNode = null;
        boolean result = true;
        for (Element dest : findElements(mMainDoc, path)) {
            Attr attr = dest.getAttributeNodeNS(NS_URI, keyAttr);
            String value = attr == null ? "" : attr.getNodeValue().trim();   //$NON-NLS-1$
            if (value.length() != 0) {
                try {
                    // Note that the value can be an hex number such as 0x00020001 so we
                    // need Integer.decode instead of Integer.parseInt.
                    // Note: Integer.decode cannot handle "ffffffff", see JDK issue 6624867
                    // so we just treat the version as a long and test like this, ignoring
                    // the fact that a value of 0xFFFF/.0xFFFF is probably invalid anyway
                    // in the context of glEsVersion.
                    long version = Long.decode(value);
                    if (version >= destGlEsVersion) {
                        destGlEsVersion = version;
                        destNode = dest;
                    } else if (version < 0x00010000) {
                        mLog.error(Severity.WARNING,
                                xmlFileAndLine(dest),
                                "Ignoring <uses-feature android:glEsVersion='%1$s'> because it's smaller than 1.0.",
                                value);
                    }
                } catch (NumberFormatException e) {
                    // Note: NumberFormatException.toString() has no interesting information
                    // so we don't output it.
                    mLog.error(Severity.ERROR,
                            xmlFileAndLine(dest),
                            "Failed to parse <uses-feature android:glEsVersion='%1$s'>: must be an integer in the form 0x00020001.",
                            value);
                    result = false;
                }
            }
        }

        // If we found at least one valid with no error, use that, otherwise bail out.
        if (!result && destNode == null) {
            return false;
        }

        // Now find the max glEsVersion on the source side.

        long srcGlEsVersion = 0x00010000L; // default minimum is 1.0
        Element srcNode = null;
        result = true;
        for (Element src : findElements(libDoc, path)) {
            Attr attr = src.getAttributeNodeNS(NS_URI, keyAttr);
            String value = attr == null ? "" : attr.getNodeValue().trim();   //$NON-NLS-1$
            if (value.length() != 0) {
                try {
                    // See comment on Long.decode above.
                    long version = Long.decode(value);
                    if (version >= srcGlEsVersion) {
                        srcGlEsVersion = version;
                        srcNode = src;
                    } else if (version < 0x00010000) {
                        mLog.error(Severity.WARNING,
                                xmlFileAndLine(src),
                                "Ignoring <uses-feature android:glEsVersion='%1$s'> because it's smaller than 1.0.",
                                value);
                    }
                } catch (NumberFormatException e) {
                    // Note: NumberFormatException.toString() has no interesting information
                    // so we don't output it.
                    mLog.error(Severity.ERROR,
                            xmlFileAndLine(src),
                            "Failed to parse <uses-feature android:glEsVersion='%1$s'>: must be an integer in the form 0x00020001.",
                            value);
                    result = false;
                }
            }
        }

        if (srcNode != null && destGlEsVersion < srcGlEsVersion) {
            mLog.conflict(Severity.WARNING,
                    xmlFileAndLine(destNode == null ? mMainDoc : destNode),
                    xmlFileAndLine(srcNode),
                    "Main manifest has <uses-feature android:glEsVersion='0x%1$08x'> but library uses glEsVersion='0x%2$08x'%3$s",
                    destGlEsVersion,
                    srcGlEsVersion,
                    destNode != null ? "" :   //$NON-NLS-1$
                        "\nNote: main manifest lacks a <uses-feature android:glEsVersion> declaration, and thus defaults to glEsVersion=0x00010000."
                    );
            result = false;
        }

        return result;
    }

    /**
     * Checks (but does not merge) uses-sdk attributes using the following rules:
     * <pre>
     * - {@code @minSdkVersion}: error if dest&lt;lib. Never automatically change dest minsdk.
     * - {@code @targetSdkVersion}: warning if dest&lt;lib. Never automatically change destination.
     * - {@code @maxSdkVersion}: obsolete, ignored. Not used in comparisons and not merged.
     * - The API level can be a codename if we have a callback that can convert it to an integer.
     * </pre>
     * @param libDoc The library document to merge from. Must not be null.
     * @return True on success, false if any error occurred (printed to the {@link IMergerLog}).
     */
    private boolean checkSdkVersion(Document libDoc) {

        boolean result = true;

        Element destUsesSdk = findFirstElement(mMainDoc, "/manifest/uses-sdk");  //$NON-NLS-1$
        Element srcUsesSdk  = findFirstElement(libDoc,   "/manifest/uses-sdk");  //$NON-NLS-1$

        AtomicInteger destValue = new AtomicInteger(1);
        AtomicInteger srcValue  = new AtomicInteger(1);
        AtomicBoolean destImplied = new AtomicBoolean(true);
        AtomicBoolean srcImplied = new AtomicBoolean(true);

        // Check minSdkVersion
        destMinSdk = 1;
        result = extractSdkVersionAttribute(
                    libDoc,
                    destUsesSdk, srcUsesSdk,
                    "min",  //$NON-NLS-1$
                    destValue, srcValue,
                    destImplied, srcImplied);

        if (result) {
            // Make it an error for an application to use a library with a greater
            // minSdkVersion. This means the library code may crash unexpectedly.
            // TODO it would be nice to be able to work around this in case the
            // user think s/he knows what s/he's doing.
            // We could define a simple XML comment flag: <!-- @NoMinSdkVersionMergeError -->

            destMinSdk = destValue.get();

            if (destMinSdk < srcValue.get()) {
                mLog.conflict(Severity.ERROR,
                        xmlFileAndLine(destUsesSdk == null ? mMainDoc : destUsesSdk),
                        xmlFileAndLine(srcUsesSdk == null ? libDoc : srcUsesSdk),
                        "Main manifest has <uses-sdk android:minSdkVersion='%1$d'> but library uses minSdkVersion='%2$d'%3$s",
                        destMinSdk,
                        srcValue.get(),
                        !destImplied.get() ? "" :   //$NON-NLS-1$
                            "\nNote: main manifest lacks a <uses-sdk android:minSdkVersion> declaration, which defaults to value 1."
                        );
                result = false;
            }
        }

        // Check targetSdkVersion.

        // Note that destValue/srcValue purposely defaults to whatever minSdkVersion was last read
        // since that's their definition when missing.
        destImplied.set(true);
        srcImplied.set(true);

        boolean result2 = extractSdkVersionAttribute(
                    libDoc,
                    destUsesSdk, srcUsesSdk,
                    "target",  //$NON-NLS-1$
                    destValue, srcValue,
                    destImplied, srcImplied);

        result &= result2;
        if (result2) {
            // Make it a warning for an application to use a library with a greater
            // targetSdkVersion.

            int destTargetSdk = destImplied.get() ? destMinSdk : destValue.get();

            if (destTargetSdk < srcValue.get()) {
                mLog.conflict(Severity.WARNING,
                        xmlFileAndLine(destUsesSdk == null ? mMainDoc : destUsesSdk),
                        xmlFileAndLine(srcUsesSdk == null ? libDoc : srcUsesSdk),
                        "Main manifest has <uses-sdk android:targetSdkVersion='%1$d'> but library uses targetSdkVersion='%2$d'%3$s",
                        destTargetSdk,
                        srcValue.get(),
                        !destImplied.get() ? "" :   //$NON-NLS-1$
                            "\nNote: main manifest lacks a <uses-sdk android:targetSdkVersion> declaration, which defaults to value minSdkVersion or 1."
                        );
                result = false;
            }
        }

        return result;
    }

    /**
     * Implementation detail for {@link #checkSdkVersion(Document)}.
     * Note that the various atomic out-variables must be preset to their default before
     * the call.
     * <p/>
     * destValue/srcValue will be filled with the integer value of the field, if present
     * and a correct number, in which case destImplied/destImplied are also set to true.
     * Otherwise the values and the implied variables are left untouched.
     */
    private boolean extractSdkVersionAttribute(
            Document libDoc,
            Element destUsesSdk,
            Element srcUsesSdk,
            String attr,
            AtomicInteger destValue,
            AtomicInteger srcValue,
            AtomicBoolean destImplied,
            AtomicBoolean srcImplied) {
        String s = destUsesSdk == null ? ""                                      //$NON-NLS-1$
                     : destUsesSdk.getAttributeNS(NS_URI, attr + "SdkVersion");  //$NON-NLS-1$

        boolean result = true;
        assert s != null;
        s = s.trim();
        try {
            if (s.length() > 0) {
                destValue.set(Integer.parseInt(s));
                destImplied.set(false);
            }
        } catch (NumberFormatException e) {
            boolean error = true;
            if (mCallback != null) {
                // Versions can contain codenames such as "JellyBean".
                // We'll accept it only if have a callback that can give us the API level for it.
                int apiLevel = mCallback.queryCodenameApiLevel(s);
                if (apiLevel > ICallback.UNKNOWN_CODENAME) {
                    destValue.set(apiLevel);
                    destImplied.set(false);
                    error = false;
                }
            }
            if (error) {
                // Note: NumberFormatException.toString() has no interesting information
                // so we don't output it.
                mLog.error(Severity.ERROR,
                    xmlFileAndLine(destUsesSdk == null ? mMainDoc : destUsesSdk),
                    "Failed to parse <uses-sdk %1$sSdkVersion='%2$s'>: must be an integer number or codename.",
                    attr,
                    s);
                result = false;
            }
        }

        s = srcUsesSdk == null ? ""                                      //$NON-NLS-1$
              : srcUsesSdk.getAttributeNS(NS_URI, attr + "SdkVersion");  //$NON-NLS-1$
        assert s != null;
        s = s.trim();
        try {
            if (s.length() > 0) {
                srcValue.set(Integer.parseInt(s));
                srcImplied.set(false);
            }
        } catch (NumberFormatException e) {
            boolean error = true;
            if (mCallback != null) {
                // Versions can contain codenames such as "JellyBean".
                // We'll accept it only if have a callback that can give us the API level for it.
                int apiLevel = mCallback.queryCodenameApiLevel(s);
                if (apiLevel > ICallback.UNKNOWN_CODENAME) {
                    srcValue.set(apiLevel);
                    srcImplied.set(false);
                    error = false;
                }
            }
            if (error) {
                mLog.error(Severity.ERROR,
                    xmlFileAndLine(srcUsesSdk == null ? libDoc : srcUsesSdk),
                    "Failed to parse <uses-sdk %1$sSdkVersion='%2$s'>: must be an integer number or codename.",
                    attr,
                    s);
                result = false;
            }
        }

        return result;
    }


    // -----


    /**
     * Given an element E, select which previous siblings we want to merge.
     * We want to include any whitespace up to the closing of the previous element.
     * We also want to include up preceding comment nodes and their preceding whitespace.
     * <p/>
     * This may returns either {@code end} or a previous sibling. Never returns null.
     */
    @NonNull
    private Node selectPreviousSiblings(Node end) {

        Node start = end;
        Node prev = start.getPreviousSibling();
        while (prev != null) {
            short t = prev.getNodeType();
            if (t == Node.TEXT_NODE) {
                String text = prev.getNodeValue();
                if (text == null || text.trim().length() != 0) {
                    // Not whitespace, we don't want it.
                    break;
                }
            } else if (t == Node.COMMENT_NODE) {
                // It's a comment. We'll take it.
            } else {
                // Not a comment node nor a whitespace text. We don't want it.
                break;
            }
            start = prev;
            prev = start.getPreviousSibling();
        }

        return start;
    }

    /**
     * Inserts all siblings from {@code start} to {@code end} at the end
     * of the given destination element.
     * <p/>
     * Implementation detail: this clones the source nodes into the destination.
     *
     * @param dest The destination at the end of which to insert. Cannot be null.
     * @param start The first element to insert. Must not be null.
     * @param end The last element to insert (included). Must not be null.
     *   Must be a direct "next sibling" of the start node.
     *   Can be equal to the start node to insert just that one node.
     * @return The copy of the {@code end} node in the destination document or null
     *   if no such copy was created and added to the destination.
     */
    private Node insertAtEndOf(Element dest, Node start, Node end) {
        // Check whether we'll need to adjust URI prefixes
        String destPrefix = XmlUtils.lookupNsPrefix(mMainDoc, NS_URI);
        String srcPrefix  = XmlUtils.lookupNsPrefix(start.getOwnerDocument(), NS_URI);
        boolean needPrefixChange = destPrefix != null && !destPrefix.equals(srcPrefix);

        // First let's figure out the insertion point.
        // We want the end of the last 'content' element of the
        // destination element and basically we want to insert right
        // before the last whitespace of the destination element.
        Node target = dest.getLastChild();
        while (target != null) {
            if (target.getNodeType() == Node.TEXT_NODE) {
                String text = target.getNodeValue();
                if (text == null || text.trim().length() != 0) {
                    // Not whitespace, insert after.
                    break;
                }
            } else {
                // Not text. Insert after
                break;
            }
            target = target.getPreviousSibling();
        }
        if (target != null) {
            target = target.getNextSibling();
        }

        // Destination and start..end must not be part of the same document
        // because we try to import below. If they were, it would mess the
        // structure.
        assert dest.getOwnerDocument() == mMainDoc;
        assert dest.getOwnerDocument() != start.getOwnerDocument();
        assert start.getOwnerDocument() == end.getOwnerDocument();

        while (start != null) {
            Node node = mMainDoc.importNode(start, true /*deep*/);
            if (needPrefixChange) {
                changePrefix(node, srcPrefix, destPrefix);
            }
            dest.insertBefore(node, target);

            if (start == end) {
                return node;
            }
            start = start.getNextSibling();
        }
        return null;
    }

    /**
     * Changes the namespace prefix of all nodes, recursively.
     *
     * @param node The node to process, as well as all it's descendants. Can be null.
     * @param srcPrefix The prefix to match.
     * @param destPrefix The new prefix to replace with.
     */
    private void changePrefix(Node node, String srcPrefix, String destPrefix) {
        for (; node != null; node = node.getNextSibling()) {
            if (srcPrefix.equals(node.getPrefix())) {
                node.setPrefix(destPrefix);
            }
            Node child = node.getFirstChild();
            if (child != null) {
                changePrefix(child, srcPrefix, destPrefix);
            }
        }
    }

    /**
     * Compares two {@link Element}s recursively. They must be identical with the same
     * structure and order. Whitespace and comments are ignored.
     *
     * @param e1 The first element to compare.
     * @param e2 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.
     * @param keyAttr An optional key attribute to always add to elements when dumping a diff.
     * @return True if {@code e1} and {@code e2} are equal.
     */
    private boolean compareElements(
            @NonNull Node e1,
            @NonNull Node e2,
            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
            }

            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;
                }
            }

            // 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());
        }
    }

    /**
     * Finds the first element matching the given XPath expression in the given document.
     *
     * @param doc The document where to find the expression.
     * @param path The XPath expression. It must yield an {@link Element} node type.
     * @return The {@link Element} found or null.
     */
    @Nullable
    private Element findFirstElement(
            @NonNull Document doc,
            @NonNull String path) {
        Node result;
        try {
            result = (Node) mXPath.evaluate(path, doc, XPathConstants.NODE);
            if (result instanceof Element) {
                return (Element) result;
            }

            if (result != null) {
                mLog.error(Severity.ERROR,
                        xmlFileAndLine(doc),
                        "Unexpected Node type %s when evaluating %s",   //$NON-NLS-1$
                        result.getClass().getName(), path);
            }
        } catch (XPathExpressionException e) {
            mLog.error(Severity.ERROR,
                    xmlFileAndLine(doc),
                    "XPath error on expr %s: %s",                       //$NON-NLS-1$
                    path, e.toString());
        }
        return null;
    }

    /**
     * Finds zero or more elements matching the given XPath expression in the given document.
     *
     * @param doc The document where to find the expression.
     * @param path The XPath expression. Only {@link Element}s nodes will be returned.
     * @return A list of {@link Element} found, possibly empty but never null.
     */
    private List<Element> findElements(
            @NonNull Document doc,
            @NonNull String path) {
        return findElements(doc, path, null, null);
    }


    /**
     * Finds zero or more elements matching the given XPath expression in the given document.
     * <p/>
     * Furthermore, the elements must have an attribute matching the given attribute name
     * and value if provided. (If you don't need to match an attribute, use the other version.)
     * <p/>
     * Note that if you provide {@code attrName} as non-null then the {@code attrValue}
     * must be non-null too. In this case the XPath expression will be modified to add
     * the check by naively appending a "[name='value']" filter.
     *
     * @param doc The document where to find the expression.
     * @param path The XPath expression. Only {@link Element}s nodes will be returned.
     * @param attrName The name of the optional attribute to match. Can be null.
     * @param attrValue The value of the optional attribute to match.
     *   Can be null if {@code attrName} is null, otherwise must be non-null.
     * @return A list of {@link Element} found, possibly empty but never null.
     *
     * @see #findElements(Document, String)
     */
    private List<Element> findElements(
            @NonNull Document doc,
            @NonNull String path,
            @Nullable String attrName,
            @Nullable String attrValue) {
        List<Element> elements = new ArrayList<Element>();

        if (attrName != null) {
            assert attrValue != null;
            // Generate expression /manifest/application/activity[@android:name='my.fqcn']
            path = String.format("%1$s[@%2$s:%3$s='%4$s']",                     //$NON-NLS-1$
                    path, NS_PREFIX, attrName, attrValue);
        }

        try {
            NodeList results = (NodeList) mXPath.evaluate(path, doc, XPathConstants.NODESET);
            if (results != null && results.getLength() > 0) {
                for (int i = 0; i < results.getLength(); i++) {
                    Node n = results.item(i);
                    assert n instanceof Element;
                    if (n instanceof Element) {
                        elements.add((Element) n);
                    } else {
                        mLog.error(Severity.ERROR,
                                xmlFileAndLine(doc),
                                "Unexpected Node type %s when evaluating %s",   //$NON-NLS-1$
                                n.getClass().getName(), path);
                    }
                }
            }

        } catch (XPathExpressionException e) {
            mLog.error(Severity.ERROR,
                    xmlFileAndLine(doc),
                    "XPath error on expr %s: %s",                       //$NON-NLS-1$
                    path, e.toString());
        }

        return elements;
    }

    /**
     * Returns a new {@link FileAndLine} structure that identifies
     * the base filename & line number from which the XML node was parsed.
     * <p/>
     * When the line number is unknown (e.g. if a {@link Document} instance is given)
     * then line number 0 will be used.
     *
     * @param node The node or document where the error occurs. Must not be null.
     * @return A new non-null {@link FileAndLine} combining the file name and line number.
     */
    private @NonNull FileAndLine xmlFileAndLine(@NonNull Node node) {
        String name = XmlUtils.extractXmlFilename(node);
        int line = XmlUtils.extractLineNumber(node); // 0 in case of error or unknown
        return new FileAndLine(name, line);
    }

}