AAPT2: Insert <uses-sdk> element before <application>

PackageParser on the device uses the targetSdkVersion of the
app while it parses <application>. That means that if the
<uses-sdk> tag comes after <application>, the targetSdkVersion
is assumed to be 0.

Test: make libaapt2_tests
Change-Id: I60f2179a7ff44e7419217afb53f3d24f8c030f6e
diff --git a/tools/aapt2/link/Link.cpp b/tools/aapt2/link/Link.cpp
index 717978ea..b525758 100644
--- a/tools/aapt2/link/Link.cpp
+++ b/tools/aapt2/link/Link.cpp
@@ -1356,8 +1356,8 @@
     application_el->attributes.push_back(
         xml::Attribute{xml::kSchemaAndroid, "hasCode", "false"});
 
-    manifest_el->AddChild(std::move(application_el));
-    namespace_android->AddChild(std::move(manifest_el));
+    manifest_el->AppendChild(std::move(application_el));
+    namespace_android->AppendChild(std::move(manifest_el));
     doc->root = std::move(namespace_android);
     return doc;
   }
diff --git a/tools/aapt2/link/ManifestFixer.cpp b/tools/aapt2/link/ManifestFixer.cpp
index a418fc8..36a3494 100644
--- a/tools/aapt2/link/ManifestFixer.cpp
+++ b/tools/aapt2/link/ManifestFixer.cpp
@@ -309,10 +309,12 @@
   if ((options_.min_sdk_version_default ||
        options_.target_sdk_version_default) &&
       root->FindChild({}, "uses-sdk") == nullptr) {
-    // Auto insert a <uses-sdk> element.
+    // Auto insert a <uses-sdk> element. This must be inserted before the
+    // <application> tag. The device runtime PackageParser will make SDK version
+    // decisions while parsing <application>.
     std::unique_ptr<xml::Element> uses_sdk = util::make_unique<xml::Element>();
     uses_sdk->name = "uses-sdk";
-    root->AddChild(std::move(uses_sdk));
+    root->InsertChild(0, std::move(uses_sdk));
   }
 
   xml::XmlActionExecutor executor;
@@ -327,7 +329,8 @@
 
   if (options_.rename_manifest_package) {
     // Rename manifest package outside of the XmlActionExecutor.
-    // We need to extract the old package name and FullyQualify all class names.
+    // We need to extract the old package name and FullyQualify all class
+    // names.
     if (!RenameManifestPackage(options_.rename_manifest_package.value(),
                                root)) {
       return false;
diff --git a/tools/aapt2/link/ManifestFixer_test.cpp b/tools/aapt2/link/ManifestFixer_test.cpp
index 0e29ba6..e9bc64a 100644
--- a/tools/aapt2/link/ManifestFixer_test.cpp
+++ b/tools/aapt2/link/ManifestFixer_test.cpp
@@ -168,6 +168,50 @@
   EXPECT_EQ("22", attr->value);
 }
 
+TEST_F(ManifestFixerTest, UsesSdkMustComeBeforeApplication) {
+  ManifestFixerOptions options = {std::string("8"), std::string("22")};
+  std::unique_ptr<xml::XmlResource> doc = VerifyWithOptions(R"EOF(
+          <manifest xmlns:android="http://schemas.android.com/apk/res/android"
+                    package="android">
+            <application android:name=".MainApplication" />
+          </manifest>)EOF",
+                                                            options);
+  ASSERT_NE(nullptr, doc);
+
+  xml::Element* manifest_el = xml::FindRootElement(doc.get());
+  ASSERT_NE(nullptr, manifest_el);
+  ASSERT_EQ("manifest", manifest_el->name);
+
+  xml::Element* application_el = manifest_el->FindChild("", "application");
+  ASSERT_NE(nullptr, application_el);
+
+  xml::Element* uses_sdk_el = manifest_el->FindChild("", "uses-sdk");
+  ASSERT_NE(nullptr, uses_sdk_el);
+
+  // Check that the uses_sdk_el comes before application_el in the children
+  // vector.
+  // Since there are no namespaces here, these children are direct descendants
+  // of manifest.
+  auto uses_sdk_iter =
+      std::find_if(manifest_el->children.begin(), manifest_el->children.end(),
+                   [&](const std::unique_ptr<xml::Node>& child) {
+                     return child.get() == uses_sdk_el;
+                   });
+
+  auto application_iter =
+      std::find_if(manifest_el->children.begin(), manifest_el->children.end(),
+                   [&](const std::unique_ptr<xml::Node>& child) {
+                     return child.get() == application_el;
+                   });
+
+  ASSERT_NE(manifest_el->children.end(), uses_sdk_iter);
+  ASSERT_NE(manifest_el->children.end(), application_iter);
+
+  // The distance should be positive, meaning uses_sdk_iter comes before
+  // application_iter.
+  EXPECT_GT(std::distance(uses_sdk_iter, application_iter), 0);
+}
+
 TEST_F(ManifestFixerTest, RenameManifestPackageAndFullyQualifyClasses) {
   ManifestFixerOptions options;
   options.rename_manifest_package = std::string("com.android");
diff --git a/tools/aapt2/xml/XmlDom.cpp b/tools/aapt2/xml/XmlDom.cpp
index 567418e..960d361 100644
--- a/tools/aapt2/xml/XmlDom.cpp
+++ b/tools/aapt2/xml/XmlDom.cpp
@@ -66,7 +66,7 @@
 
   Node* this_node = node.get();
   if (!stack->node_stack.empty()) {
-    stack->node_stack.top()->AddChild(std::move(node));
+    stack->node_stack.top()->AppendChild(std::move(node));
   } else {
     stack->root = std::move(node);
   }
@@ -325,7 +325,7 @@
         root = std::move(new_node);
       } else {
         CHECK(!node_stack.empty()) << "node stack should not be empty";
-        node_stack.top()->AddChild(std::move(new_node));
+        node_stack.top()->AppendChild(std::move(new_node));
       }
 
       if (!NodeCast<Text>(this_node)) {
@@ -346,7 +346,7 @@
 
   ns->children.reserve(children.size());
   for (const std::unique_ptr<xml::Node>& child : children) {
-    ns->AddChild(child->Clone());
+    ns->AppendChild(child->Clone());
   }
   return std::move(ns);
 }
@@ -372,11 +372,16 @@
   return el;
 }
 
-void Node::AddChild(std::unique_ptr<Node> child) {
+void Node::AppendChild(std::unique_ptr<Node> child) {
   child->parent = this;
   children.push_back(std::move(child));
 }
 
+void Node::InsertChild(size_t index, std::unique_ptr<Node> child) {
+  child->parent = this;
+  children.insert(children.begin() + index, std::move(child));
+}
+
 Attribute* Element::FindAttribute(const StringPiece& ns,
                                   const StringPiece& name) {
   for (auto& attr : attributes) {
@@ -456,7 +461,7 @@
 
   el->children.reserve(children.size());
   for (const std::unique_ptr<xml::Node>& child : children) {
-    el->AddChild(child->Clone());
+    el->AppendChild(child->Clone());
   }
   return std::move(el);
 }
diff --git a/tools/aapt2/xml/XmlDom.h b/tools/aapt2/xml/XmlDom.h
index e771d87..720fe35 100644
--- a/tools/aapt2/xml/XmlDom.h
+++ b/tools/aapt2/xml/XmlDom.h
@@ -47,7 +47,8 @@
 
   virtual ~Node() = default;
 
-  void AddChild(std::unique_ptr<Node> child);
+  void AppendChild(std::unique_ptr<Node> child);
+  void InsertChild(size_t index, std::unique_ptr<Node> child);
   virtual void Accept(RawVisitor* visitor) = 0;
   virtual std::unique_ptr<Node> Clone() = 0;
 };