AAPT2: Change xml file parsing to DOM based

We modify the XML of layouts and AndroidManifest enough
that it warrants we operate on the tree in memory.
These files are never very large so this should be fine.

Change-Id: I5d597abdb3fca2a203cf7c0b40fcd926aecb3137

1 files changed, 447 insertions, 371 deletions

diff --git a/tools/aapt2/XmlFlattener.cpp b/tools/aapt2/XmlFlattener.cpp
index f78e38d..56b5613 100644
--- a/tools/aapt2/XmlFlattener.cpp
+++ b/tools/aapt2/XmlFlattener.cpp
@@ -34,425 +34,444 @@
 #include <vector>
 
 namespace aapt {
+namespace xml {
 
-constexpr const char16_t* kSchemaAndroid = u"http://schemas.android.com/apk/res/android";
-
-struct AttributeValueFlattener : ValueVisitor {
-    AttributeValueFlattener(
-            std::shared_ptr<IResolver> resolver, SourceLogger* logger,
-            android::Res_value* outValue, std::shared_ptr<XmlPullParser> parser, bool* outError,
-            StringPool::Ref rawValue, std::u16string* defaultPackage,
-            std::vector<std::pair<StringPool::Ref, android::ResStringPool_ref*>>* outStringRefs) :
-            mResolver(resolver), mLogger(logger), mOutValue(outValue), mParser(parser),
-            mError(outError), mRawValue(rawValue), mDefaultPackage(defaultPackage),
-            mStringRefs(outStringRefs) {
+constexpr uint32_t kLowPriority = 0xffffffffu;
+
+// A vector that maps String refs to their final destination in the out buffer.
+using FlatStringRefList = std::vector<std::pair<StringPool::Ref, android::ResStringPool_ref*>>;
+
+struct XmlFlattener : public Visitor {
+    XmlFlattener(BigBuffer* outBuffer, StringPool* pool, FlatStringRefList* stringRefs,
+                 const std::u16string& defaultPackage) :
+            mOut(outBuffer), mPool(pool), mStringRefs(stringRefs),
+            mDefaultPackage(defaultPackage) {
     }
 
-    void visit(Reference& reference, ValueVisitorArgs&) override {
-        // First see if we can convert the package name from a prefix to a real
-        // package name.
-        ResourceName aliasedName = reference.name;
+    // No copying.
+    XmlFlattener(const XmlFlattener&) = delete;
+    XmlFlattener& operator=(const XmlFlattener&) = delete;
+
+    void writeNamespace(Namespace* node, uint16_t type) {
+        const size_t startIndex = mOut->size();
+        android::ResXMLTree_node* flatNode = mOut->nextBlock<android::ResXMLTree_node>();
+        android::ResXMLTree_namespaceExt* flatNs =
+                mOut->nextBlock<android::ResXMLTree_namespaceExt>();
+        mOut->align4();
+
+        flatNode->header = { type, sizeof(*flatNode), (uint32_t)(mOut->size() - startIndex) };
+        flatNode->lineNumber = node->lineNumber;
+        flatNode->comment.index = -1;
+        addString(node->namespacePrefix, kLowPriority, &flatNs->prefix);
+        addString(node->namespaceUri, kLowPriority, &flatNs->uri);
+    }
 
-        if (!reference.name.package.empty()) {
-            // Only if we specified a package do we look for its alias.
-            mParser->applyPackageAlias(&reference.name.package, *mDefaultPackage);
-        } else {
-            reference.name.package = *mDefaultPackage;
+    virtual void visit(Namespace* node) override {
+        // Extract the package/prefix from this namespace node.
+        Maybe<std::u16string> package = util::extractPackageFromNamespace(node->namespaceUri);
+        if (package) {
+            mPackageAliases.emplace_back(
+                    node->namespacePrefix,
+                    package.value().empty() ? mDefaultPackage : package.value());
         }
 
-        Maybe<ResourceId> result = mResolver->findId(reference.name);
-        if (!result || !result.value().isValid()) {
-            std::ostream& out = mLogger->error(mParser->getLineNumber())
-                    << "unresolved reference '"
-                    << aliasedName
-                    << "'";
-            if (aliasedName != reference.name) {
-                out << " (aka '" << reference.name << "')";
-            }
-            out << "'." << std::endl;
-            *mError = true;
-        } else {
-            reference.id = result.value();
-            reference.flatten(*mOutValue);
+        writeNamespace(node, android::RES_XML_START_NAMESPACE_TYPE);
+        for (const auto& child : node->children) {
+            child->accept(this);
         }
-    }
+        writeNamespace(node, android::RES_XML_END_NAMESPACE_TYPE);
 
-    void visit(String& string, ValueVisitorArgs&) override {
-        mOutValue->dataType = android::Res_value::TYPE_STRING;
-        mStringRefs->emplace_back(
-                mRawValue,
-                reinterpret_cast<android::ResStringPool_ref*>(mOutValue->data));
+        if (package) {
+            mPackageAliases.pop_back();
+        }
     }
 
-    void visitItem(Item& item, ValueVisitorArgs&) override {
-        item.flatten(*mOutValue);
+    virtual void visit(Text* node) override {
+        if (util::trimWhitespace(node->text).empty()) {
+            return;
+        }
+
+        const size_t startIndex = mOut->size();
+        android::ResXMLTree_node* flatNode = mOut->nextBlock<android::ResXMLTree_node>();
+        android::ResXMLTree_cdataExt* flatText = mOut->nextBlock<android::ResXMLTree_cdataExt>();
+        mOut->align4();
+
+        const uint16_t type = android::RES_XML_CDATA_TYPE;
+        flatNode->header = { type, sizeof(*flatNode), (uint32_t)(mOut->size() - startIndex) };
+        flatNode->lineNumber = node->lineNumber;
+        flatNode->comment.index = -1;
+        addString(node->text, kLowPriority, &flatText->data);
     }
 
-private:
-    std::shared_ptr<IResolver> mResolver;
-    SourceLogger* mLogger;
-    android::Res_value* mOutValue;
-    std::shared_ptr<XmlPullParser> mParser;
-    bool* mError;
-    StringPool::Ref mRawValue;
-    std::u16string* mDefaultPackage;
-    std::vector<std::pair<StringPool::Ref, android::ResStringPool_ref*>>* mStringRefs;
-};
+    virtual void visit(Element* node) override {
+        const size_t startIndex = mOut->size();
+        android::ResXMLTree_node* flatNode = mOut->nextBlock<android::ResXMLTree_node>();
+        android::ResXMLTree_attrExt* flatElem = mOut->nextBlock<android::ResXMLTree_attrExt>();
 
-struct XmlAttribute {
-    uint32_t resourceId;
-    const XmlPullParser::Attribute* xmlAttr;
-    const Attribute* attr;
-    StringPool::Ref nameRef;
-};
+        const uint16_t type = android::RES_XML_START_ELEMENT_TYPE;
+        flatNode->header = { type, sizeof(*flatNode), 0 };
+        flatNode->lineNumber = node->lineNumber;
+        flatNode->comment.index = -1;
 
-static bool lessAttributeId(const XmlAttribute& a, uint32_t id) {
-    return a.resourceId < id;
-}
+        addString(node->namespaceUri, kLowPriority, &flatElem->ns);
+        addString(node->name, kLowPriority, &flatElem->name);
+        flatElem->attributeStart = sizeof(*flatElem);
+        flatElem->attributeSize = sizeof(android::ResXMLTree_attribute);
+        flatElem->attributeCount = node->attributes.size();
 
-XmlFlattener::XmlFlattener(const std::shared_ptr<ResourceTable>& table,
-                           const std::shared_ptr<IResolver>& resolver) :
-        mTable(table), mResolver(resolver) {
-}
+        if (!writeAttributes(mOut, node, flatElem)) {
+            mError = true;
+        }
 
-/**
- * Reads events from the parser and writes to a BigBuffer. The binary XML file
- * expects the StringPool to appear first, but we haven't collected the strings yet. We
- * write to a temporary BigBuffer while parsing the input, adding strings we encounter
- * to the StringPool. At the end, we write the StringPool to the given BigBuffer and
- * then move the data from the temporary BigBuffer into the given one. This incurs no
- * copies as the given BigBuffer simply takes ownership of the data.
- */
-Maybe<size_t> XmlFlattener::flatten(const Source& source,
-                                    const std::shared_ptr<XmlPullParser>& parser,
-                                    BigBuffer* outBuffer, Options options) {
-    SourceLogger logger(source);
-    StringPool pool;
-    bool error = false;
+        mOut->align4();
+        flatNode->header.size = (uint32_t)(mOut->size() - startIndex);
 
-    size_t smallestStrippedAttributeSdk = std::numeric_limits<size_t>::max();
+        for (const auto& child : node->children) {
+            child->accept(this);
+        }
 
-    // Attribute names are stored without packages, but we use
-    // their StringPool index to lookup their resource IDs.
-    // This will cause collisions, so we can't dedupe
-    // attribute names from different packages. We use separate
-    // pools that we later combine.
-    std::map<std::u16string, StringPool> packagePools;
+        const size_t startEndIndex = mOut->size();
+        android::ResXMLTree_node* flatEndNode = mOut->nextBlock<android::ResXMLTree_node>();
+        android::ResXMLTree_endElementExt* flatEndElem =
+                mOut->nextBlock<android::ResXMLTree_endElementExt>();
+        mOut->align4();
 
-    // Attribute resource IDs are stored in the same order
-    // as the attribute names appear in the StringPool.
-    // Since the StringPool contains more than just attribute
-    // names, to maintain a tight packing of resource IDs,
-    // we must ensure that attribute names appear first
-    // in our StringPool. For this, we assign a low priority
-    // (0xffffffff) to non-attribute strings. Attribute
-    // names will be stored along with a priority equal
-    // to their resource ID so that they are ordered.
-    StringPool::Context lowPriority { 0xffffffffu };
+        const uint16_t endType = android::RES_XML_END_ELEMENT_TYPE;
+        flatEndNode->header = { endType, sizeof(*flatEndNode),
+                (uint32_t)(mOut->size() - startEndIndex) };
+        flatEndNode->lineNumber = node->lineNumber;
+        flatEndNode->comment.index = -1;
 
-    // Once we sort the StringPool, we can assign the updated indices
-    // to the correct data locations.
-    std::vector<std::pair<StringPool::Ref, android::ResStringPool_ref*>> stringRefs;
+        addString(node->namespaceUri, kLowPriority, &flatEndElem->ns);
+        addString(node->name, kLowPriority, &flatEndElem->name);
+    }
 
-    // Since we don't know the size of the final StringPool, we write to this
-    // temporary BigBuffer, which we will append to outBuffer later.
-    BigBuffer out(1024);
-    while (XmlPullParser::isGoodEvent(parser->next())) {
-        XmlPullParser::Event event = parser->getEvent();
-        switch (event) {
-            case XmlPullParser::Event::kStartNamespace:
-            case XmlPullParser::Event::kEndNamespace: {
-                const size_t startIndex = out.size();
-                android::ResXMLTree_node* node = out.nextBlock<android::ResXMLTree_node>();
-                if (event == XmlPullParser::Event::kStartNamespace) {
-                    node->header.type = android::RES_XML_START_NAMESPACE_TYPE;
-                } else {
-                    node->header.type = android::RES_XML_END_NAMESPACE_TYPE;
-                }
+    bool success() const {
+        return !mError;
+    }
 
-                node->header.headerSize = sizeof(*node);
-                node->lineNumber = parser->getLineNumber();
-                node->comment.index = -1;
+protected:
+    void addString(const StringPiece16& str, uint32_t priority, android::ResStringPool_ref* dest) {
+        if (!str.empty()) {
+            mStringRefs->emplace_back(mPool->makeRef(str, StringPool::Context{ priority }), dest);
+        } else {
+            // The device doesn't think a string of size 0 is the same as null.
+            dest->index = -1;
+        }
+    }
 
-                android::ResXMLTree_namespaceExt* ns =
-                        out.nextBlock<android::ResXMLTree_namespaceExt>();
-                stringRefs.emplace_back(
-                        pool.makeRef(parser->getNamespacePrefix(), lowPriority), &ns->prefix);
-                stringRefs.emplace_back(
-                        pool.makeRef(parser->getNamespaceUri(), lowPriority), &ns->uri);
+    void addString(const StringPool::Ref& ref, android::ResStringPool_ref* dest) {
+        mStringRefs->emplace_back(ref, dest);
+    }
 
-                out.align4();
-                node->header.size = out.size() - startIndex;
-                break;
+    Maybe<std::u16string> getPackageAlias(const std::u16string& prefix) {
+        const auto endIter = mPackageAliases.rend();
+        for (auto iter = mPackageAliases.rbegin(); iter != endIter; ++iter) {
+            if (iter->first == prefix) {
+                return iter->second;
             }
+        }
+        return {};
+    }
 
-            case XmlPullParser::Event::kStartElement: {
-                const size_t startIndex = out.size();
-                android::ResXMLTree_node* node = out.nextBlock<android::ResXMLTree_node>();
-                node->header.type = android::RES_XML_START_ELEMENT_TYPE;
-                node->header.headerSize = sizeof(*node);
-                node->lineNumber = parser->getLineNumber();
-                node->comment.index = -1;
-
-                android::ResXMLTree_attrExt* elem = out.nextBlock<android::ResXMLTree_attrExt>();
-                if (!parser->getElementNamespace().empty()) {
-                    stringRefs.emplace_back(
-                            pool.makeRef(parser->getElementNamespace(), lowPriority), &elem->ns);
-                } else {
-                    // The device doesn't think a string of size 0 is the same as null.
-                    elem->ns.index = -1;
-                }
-                stringRefs.emplace_back(
-                        pool.makeRef(parser->getElementName(), lowPriority), &elem->name);
-                elem->attributeStart = sizeof(*elem);
-                elem->attributeSize = sizeof(android::ResXMLTree_attribute);
-
-                // The resource system expects attributes to be sorted by resource ID.
-                std::vector<XmlAttribute> sortedAttributes;
-                uint32_t nextAttributeId = 0;
-                const auto endAttrIter = parser->endAttributes();
-                for (auto attrIter = parser->beginAttributes();
-                        attrIter != endAttrIter;
-                        ++attrIter) {
-                    uint32_t id;
-                    StringPool::Ref nameRef;
-                    const Attribute* attr = nullptr;
-
-                    if (options.maxSdkAttribute && attrIter->namespaceUri == kSchemaAndroid) {
-                        size_t sdkVersion = findAttributeSdkLevel(attrIter->name);
-                        if (sdkVersion > options.maxSdkAttribute.value()) {
-                            // We will silently omit this attribute
-                            smallestStrippedAttributeSdk =
-                                    std::min(smallestStrippedAttributeSdk, sdkVersion);
-                            continue;
-                        }
-                    }
-
-                    ResourceNameRef genIdName;
-                    bool create = false;
-                    bool privateRef = false;
-                    if (mTable && ResourceParser::tryParseReference(attrIter->value, &genIdName,
-                            &create, &privateRef) && create) {
-                        mTable->addResource(genIdName, {}, source.line(parser->getLineNumber()),
-                                            util::make_unique<Id>());
-                    }
+    const std::u16string& getDefaultPackage() const {
+        return mDefaultPackage;
+    }
 
+    /**
+     * Subclasses override this to deal with attributes. Attributes can be flattened as
+     * raw values or as resources.
+     */
+    virtual bool writeAttributes(BigBuffer* out, Element* node,
+                                 android::ResXMLTree_attrExt* flatElem) = 0;
 
-                    Maybe<std::u16string> package = util::extractPackageFromNamespace(
-                            attrIter->namespaceUri);
-                    if (!package || !mResolver) {
-                        // Attributes that have no resource ID (because they don't belong to a
-                        // package) should appear after those that do have resource IDs. Assign
-                        // them some integer value that will appear after.
-                        id = 0x80000000u | nextAttributeId++;
-                        nameRef = pool.makeRef(attrIter->name, StringPool::Context{ id });
-
-                    } else {
-                        // Find the Attribute object via our Resolver.
-                        ResourceName attrName = {
-                                package.value(), ResourceType::kAttr, attrIter->name };
-
-                        if (attrName.package.empty()) {
-                            attrName.package = options.defaultPackage;
-                        }
-
-                        Maybe<IResolver::Entry> result = mResolver->findAttribute(attrName);
-                        if (!result || !result.value().id.isValid()) {
-                            logger.error(parser->getLineNumber())
-                                    << "unresolved attribute '"
-                                    << attrName
-                                    << "'."
-                                    << std::endl;
-                            error = true;
-                            continue;
-                        }
-
-                        if (!result.value().attr) {
-                            logger.error(parser->getLineNumber())
-                                    << "not a valid attribute '"
-                                    << attrName
-                                    << "'."
-                                    << std::endl;
-                            error = true;
-                            continue;
-                        }
-
-                        id = result.value().id.id;
-                        attr = result.value().attr;
-
-                        // Put the attribute name into a package specific pool, since we don't
-                        // want to collapse names from different packages.
-                        nameRef = packagePools[package.value()].makeRef(
-                                attrIter->name, StringPool::Context{ id });
-                    }
+private:
+    BigBuffer* mOut;
+    StringPool* mPool;
+    FlatStringRefList* mStringRefs;
+    std::u16string mDefaultPackage;
+    bool mError = false;
+    std::vector<std::pair<std::u16string, std::u16string>> mPackageAliases;
+};
 
-                    // Insert the attribute into the sorted vector.
-                    auto iter = std::lower_bound(sortedAttributes.begin(), sortedAttributes.end(),
-                                                 id, lessAttributeId);
-                    sortedAttributes.insert(iter, XmlAttribute{ id, &*attrIter, attr, nameRef });
-                }
+/**
+ * Flattens XML, encoding the attributes as raw strings. This is used in the compile phase.
+ */
+struct CompileXmlFlattener : public XmlFlattener {
+    CompileXmlFlattener(BigBuffer* outBuffer, StringPool* pool, FlatStringRefList* stringRefs,
+                        const std::u16string& defaultPackage) :
+            XmlFlattener(outBuffer, pool, stringRefs, defaultPackage) {
+    }
 
-                if (error) {
-                    break;
-                }
+    virtual bool writeAttributes(BigBuffer* out, Element* node,
+                                 android::ResXMLTree_attrExt* flatElem) override {
+        flatElem->attributeCount = node->attributes.size();
+        if (node->attributes.empty()) {
+            return true;
+        }
 
-                // Now that we have filtered out some attributes, get the final count.
-                elem->attributeCount = sortedAttributes.size();
-
-                // Flatten the sorted attributes.
-                uint16_t attributeIndex = 1;
-                for (auto entry : sortedAttributes) {
-                    android::ResXMLTree_attribute* attr =
-                            out.nextBlock<android::ResXMLTree_attribute>();
-                    if (!entry.xmlAttr->namespaceUri.empty()) {
-                        stringRefs.emplace_back(
-                                pool.makeRef(entry.xmlAttr->namespaceUri, lowPriority), &attr->ns);
-                    } else {
-                        attr->ns.index = -1;
-                    }
+        android::ResXMLTree_attribute* flatAttrs = out->nextBlock<android::ResXMLTree_attribute>(
+                node->attributes.size());
+        for (const Attribute& attr : node->attributes) {
+            addString(attr.namespaceUri, kLowPriority, &flatAttrs->ns);
+            addString(attr.name, kLowPriority, &flatAttrs->name);
+            addString(attr.value, kLowPriority, &flatAttrs->rawValue);
+            flatAttrs++;
+        }
+        return true;
+    }
+};
 
-                    StringPool::Ref rawValueRef = pool.makeRef(entry.xmlAttr->value, lowPriority);
+struct AttributeToFlatten {
+    uint32_t resourceId = 0;
+    const Attribute* xmlAttr = nullptr;
+    const ::aapt::Attribute* resourceAttr = nullptr;
+};
 
-                    stringRefs.emplace_back(entry.nameRef, &attr->name);
+static bool lessAttributeId(const AttributeToFlatten& a, uint32_t id) {
+    return a.resourceId < id;
+}
 
-                    if (options.keepRawValues) {
-                        stringRefs.emplace_back(rawValueRef, &attr->rawValue);
-                    } else {
-                        attr->rawValue.index = -1;
-                    }
+/**
+ * Flattens XML, encoding the attributes as resources.
+ */
+struct LinkedXmlFlattener : public XmlFlattener {
+    LinkedXmlFlattener(BigBuffer* outBuffer, StringPool* pool,
+                       std::map<std::u16string, StringPool>* packagePools,
+                       FlatStringRefList* stringRefs,
+                       const std::u16string& defaultPackage,
+                       const std::shared_ptr<IResolver>& resolver,
+                       SourceLogger* logger,
+                       const FlattenOptions& options) :
+            XmlFlattener(outBuffer, pool, stringRefs, defaultPackage), mResolver(resolver),
+            mLogger(logger), mPackagePools(packagePools), mOptions(options) {
+    }
 
-                    // Assign the indices for specific attributes.
-                    if (entry.xmlAttr->namespaceUri == kSchemaAndroid &&
-                            entry.xmlAttr->name == u"id") {
-                        elem->idIndex = attributeIndex;
-                    } else if (entry.xmlAttr->namespaceUri.empty()) {
-                        if (entry.xmlAttr->name == u"class") {
-                            elem->classIndex = attributeIndex;
-                        } else if (entry.xmlAttr->name == u"style") {
-                            elem->styleIndex = attributeIndex;
-                        }
-                    }
-                    attributeIndex++;
-
-                    std::unique_ptr<Item> value;
-                    if (entry.attr) {
-                        value = ResourceParser::parseItemForAttribute(entry.xmlAttr->value,
-                                                                      *entry.attr);
-                    } else {
-                        bool create = false;
-                        value = ResourceParser::tryParseReference(entry.xmlAttr->value, &create);
-                    }
+    virtual bool writeAttributes(BigBuffer* out, Element* node,
+                                 android::ResXMLTree_attrExt* flatElem) override {
+        bool error = false;
+        std::vector<AttributeToFlatten> sortedAttributes;
+        uint32_t nextAttributeId = 0x80000000u;
+
+        // Sort and filter attributes by their resource ID.
+        for (const Attribute& attr : node->attributes) {
+            AttributeToFlatten attrToFlatten;
+            attrToFlatten.xmlAttr = &attr;
+
+            Maybe<std::u16string> package = util::extractPackageFromNamespace(attr.namespaceUri);
+            if (package) {
+                // Find the Attribute object via our Resolver.
+                ResourceName attrName = { package.value(), ResourceType::kAttr, attr.name };
+                if (attrName.package.empty()) {
+                    attrName.package = getDefaultPackage();
+                }
 
-                    if (mResolver && value) {
-                        AttributeValueFlattener flattener(
-                                mResolver,
-                                &logger,
-                                &attr->typedValue,
-                                parser,
-                                &error,
-                                rawValueRef,
-                                &options.defaultPackage,
-                                &stringRefs);
-                        value->accept(flattener, {});
-                    } else if (!value && entry.attr &&
-                            !(entry.attr->typeMask & android::ResTable_map::TYPE_STRING)) {
-                        logger.error(parser->getLineNumber())
-                                << "'"
-                                << *rawValueRef
-                                << "' is not compatible with attribute "
-                                << *entry.attr
-                                << "."
-                                << std::endl;
-                        error = true;
-                    } else {
-                        attr->typedValue.dataType = android::Res_value::TYPE_STRING;
-                        if (!options.keepRawValues) {
-                            // Don't set the string twice.
-                            stringRefs.emplace_back(rawValueRef, &attr->rawValue);
-                        }
-                        stringRefs.emplace_back(rawValueRef,
-                                reinterpret_cast<android::ResStringPool_ref*>(
-                                        &attr->typedValue.data));
+                Maybe<IResolver::Entry> result = mResolver->findAttribute(attrName);
+                if (!result || !result.value().id.isValid() || !result.value().attr) {
+                    error = true;
+                    mLogger->error(node->lineNumber)
+                            << "unresolved attribute '" << attrName << "'."
+                            << std::endl;
+                } else {
+                    attrToFlatten.resourceId = result.value().id.id;
+                    attrToFlatten.resourceAttr = result.value().attr;
+
+                    size_t sdk = findAttributeSdkLevel(attrToFlatten.resourceId);
+                    if (mOptions.maxSdkAttribute && sdk > mOptions.maxSdkAttribute.value()) {
+                        // We need to filter this attribute out.
+                        mSmallestFilteredSdk = std::min(mSmallestFilteredSdk, sdk);
+                        continue;
                     }
-                    attr->typedValue.size = sizeof(attr->typedValue);
                 }
-
-                out.align4();
-                node->header.size = out.size() - startIndex;
-                break;
             }
 
-            case XmlPullParser::Event::kEndElement: {
-                const size_t startIndex = out.size();
-                android::ResXMLTree_node* node = out.nextBlock<android::ResXMLTree_node>();
-                node->header.type = android::RES_XML_END_ELEMENT_TYPE;
-                node->header.headerSize = sizeof(*node);
-                node->lineNumber = parser->getLineNumber();
-                node->comment.index = -1;
-
-                android::ResXMLTree_endElementExt* elem =
-                        out.nextBlock<android::ResXMLTree_endElementExt>();
-                stringRefs.emplace_back(
-                        pool.makeRef(parser->getElementNamespace(), lowPriority), &elem->ns);
-                stringRefs.emplace_back(
-                        pool.makeRef(parser->getElementName(), lowPriority), &elem->name);
-
-                out.align4();
-                node->header.size = out.size() - startIndex;
-                break;
+            if (attrToFlatten.resourceId == 0) {
+                // Attributes that have no resource ID (because they don't belong to a
+                // package) should appear after those that do have resource IDs. Assign
+                // them some integer value that will appear after.
+                attrToFlatten.resourceId = nextAttributeId++;
             }
 
-            case XmlPullParser::Event::kText: {
-                StringPiece16 text = util::trimWhitespace(parser->getText());
-                if (text.empty()) {
-                    break;
+            // Insert the attribute into the sorted vector.
+            auto iter = std::lower_bound(sortedAttributes.begin(), sortedAttributes.end(),
+                                         attrToFlatten.resourceId, lessAttributeId);
+            sortedAttributes.insert(iter, std::move(attrToFlatten));
+        }
+
+        flatElem->attributeCount = sortedAttributes.size();
+        if (sortedAttributes.empty()) {
+            return true;
+        }
+
+        android::ResXMLTree_attribute* flatAttr = out->nextBlock<android::ResXMLTree_attribute>(
+                sortedAttributes.size());
+
+        // Now that we have sorted the attributes into their final encoded order, it's time
+        // to actually write them out.
+        uint16_t attributeIndex = 1;
+        for (const AttributeToFlatten& attrToFlatten : sortedAttributes) {
+            Maybe<std::u16string> package = util::extractPackageFromNamespace(
+                    attrToFlatten.xmlAttr->namespaceUri);
+
+            // Assign the indices for specific attributes.
+            if (package && package.value() == u"android" && attrToFlatten.xmlAttr->name == u"id") {
+                flatElem->idIndex = attributeIndex;
+            } else if (attrToFlatten.xmlAttr->namespaceUri.empty()) {
+                if (attrToFlatten.xmlAttr->name == u"class") {
+                    flatElem->classIndex = attributeIndex;
+                } else if (attrToFlatten.xmlAttr->name == u"style") {
+                    flatElem->styleIndex = attributeIndex;
+                }
+            }
+            attributeIndex++;
+
+            // Add the namespaceUri and name to the list of StringRefs to encode.
+            addString(attrToFlatten.xmlAttr->namespaceUri, kLowPriority, &flatAttr->ns);
+            flatAttr->rawValue.index = -1;
+
+            if (!attrToFlatten.resourceAttr) {
+                addString(attrToFlatten.xmlAttr->name, kLowPriority, &flatAttr->name);
+            } else {
+                // We've already extracted the package successfully before.
+                assert(package);
+
+                // Attribute names are stored without packages, but we use
+                // their StringPool index to lookup their resource IDs.
+                // This will cause collisions, so we can't dedupe
+                // attribute names from different packages. We use separate
+                // pools that we later combine.
+                //
+                // Lookup the StringPool for this package and make the reference there.
+                StringPool::Ref nameRef = (*mPackagePools)[package.value()].makeRef(
+                        attrToFlatten.xmlAttr->name,
+                        StringPool::Context{ attrToFlatten.resourceId });
+
+                // Add it to the list of strings to flatten.
+                addString(nameRef, &flatAttr->name);
+
+                if (mOptions.keepRawValues) {
+                    // Keep raw values (this is for static libraries).
+                    // TODO(with a smarter inflater for binary XML, we can do without this).
+                    addString(attrToFlatten.xmlAttr->value, kLowPriority, &flatAttr->rawValue);
                 }
+            }
 
-                const size_t startIndex = out.size();
-                android::ResXMLTree_node* node = out.nextBlock<android::ResXMLTree_node>();
-                node->header.type = android::RES_XML_CDATA_TYPE;
-                node->header.headerSize = sizeof(*node);
-                node->lineNumber = parser->getLineNumber();
-                node->comment.index = -1;
+            error |= !flattenItem(node, attrToFlatten.xmlAttr->value, attrToFlatten.resourceAttr,
+                                  flatAttr);
+            flatAttr->typedValue.size = sizeof(flatAttr->typedValue);
+            flatAttr++;
+        }
+        return !error;
+    }
 
-                android::ResXMLTree_cdataExt* elem = out.nextBlock<android::ResXMLTree_cdataExt>();
-                stringRefs.emplace_back(pool.makeRef(text, lowPriority), &elem->data);
+    Maybe<size_t> getSmallestFilteredSdk() const {
+        if (mSmallestFilteredSdk == std::numeric_limits<size_t>::max()) {
+            return {};
+        }
+        return mSmallestFilteredSdk;
+    }
 
-                out.align4();
-                node->header.size = out.size() - startIndex;
-                break;
+private:
+    bool flattenItem(const Node* el, const std::u16string& value, const ::aapt::Attribute* attr,
+                     android::ResXMLTree_attribute* flatAttr) {
+        std::unique_ptr<Item> item;
+        if (!attr) {
+            bool create = false;
+            item = ResourceParser::tryParseReference(value, &create);
+            if (!item) {
+                flatAttr->typedValue.dataType = android::Res_value::TYPE_STRING;
+                addString(value, kLowPriority, &flatAttr->rawValue);
+                addString(value, kLowPriority, reinterpret_cast<android::ResStringPool_ref*>(
+                        &flatAttr->typedValue.data));
+                return true;
             }
+        } else {
+            item = ResourceParser::parseItemForAttribute(value, *attr);
+            if (!item) {
+                if (!(attr->typeMask & android::ResTable_map::TYPE_STRING)) {
+                    mLogger->error(el->lineNumber)
+                            << "'"
+                            << value
+                            << "' is not compatible with attribute '"
+                            << *attr
+                            << "'."
+                            << std::endl;
+                    return false;
+                }
 
-            default:
-                break;
+                flatAttr->typedValue.dataType = android::Res_value::TYPE_STRING;
+                addString(value, kLowPriority, &flatAttr->rawValue);
+                addString(value, kLowPriority, reinterpret_cast<android::ResStringPool_ref*>(
+                        &flatAttr->typedValue.data));
+                return true;
+            }
         }
 
-    }
-    out.align4();
+        assert(item);
 
-    if (error) {
-        return {};
-    }
+        bool error = false;
 
-    if (parser->getEvent() == XmlPullParser::Event::kBadDocument) {
-        logger.error(parser->getLineNumber())
-                << parser->getLastError()
-                << std::endl;
-        return {};
-    }
+        // If this is a reference, resolve the name into an ID.
+        visitFunc<Reference>(*item, [&](Reference& reference) {
+            // First see if we can convert the package name from a prefix to a real
+            // package name.
+            ResourceName realName = reference.name;
+            if (!realName.package.empty()) {
+                Maybe<std::u16string> package = getPackageAlias(realName.package);
+                if (package) {
+                    realName.package = package.value();
+                }
+            } else {
+                realName.package = getDefaultPackage();
+            }
 
-    // Merge the package pools into the main pool.
-    for (auto& packagePoolEntry : packagePools) {
-        pool.merge(std::move(packagePoolEntry.second));
+            Maybe<ResourceId> result = mResolver->findId(realName);
+            if (!result || !result.value().isValid()) {
+                std::ostream& out = mLogger->error(el->lineNumber)
+                        << "unresolved reference '"
+                        << reference.name
+                        << "'";
+                if (realName != reference.name) {
+                    out << " (aka '" << realName << "')";
+                }
+                out << "'." << std::endl;
+                error = true;
+            } else {
+                reference.id = result.value();
+            }
+        });
+
+        if (error) {
+            return false;
+        }
+
+        item->flatten(flatAttr->typedValue);
+        return true;
     }
 
-    // Sort so that attribute resource IDs show up first.
-    pool.sort([](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
+    std::shared_ptr<IResolver> mResolver;
+    SourceLogger* mLogger;
+    std::map<std::u16string, StringPool>* mPackagePools;
+    FlattenOptions mOptions;
+    size_t mSmallestFilteredSdk = std::numeric_limits<size_t>::max();
+};
+
+/**
+ * The binary XML file expects the StringPool to appear first, but we haven't collected the
+ * strings yet. We write to a temporary BigBuffer while parsing the input, adding strings
+ * we encounter to the StringPool. At the end, we write the StringPool to the given BigBuffer and
+ * then move the data from the temporary BigBuffer into the given one. This incurs no
+ * copies as the given BigBuffer simply takes ownership of the data.
+ */
+static void flattenXml(StringPool* pool, FlatStringRefList* stringRefs, BigBuffer* outBuffer,
+                       BigBuffer&& xmlTreeBuffer) {
+    // Sort the string pool so that attribute resource IDs show up first.
+    pool->sort([](const StringPool::Entry& a, const StringPool::Entry& b) -> bool {
         return a.context.priority < b.context.priority;
     });
 
     // Now we flatten the string pool references into the correct places.
-    for (const auto& refEntry : stringRefs) {
+    for (const auto& refEntry : *stringRefs) {
         refEntry.second->index = refEntry.first.getIndex();
     }
 
@@ -463,36 +482,93 @@ Maybe<size_t> XmlFlattener::flatten(const Source& source,
     header->header.headerSize = sizeof(*header);
 
     // Flatten the StringPool.
-    StringPool::flattenUtf16(outBuffer, pool);
+    StringPool::flattenUtf16(outBuffer, *pool);
 
     // Write the array of resource IDs, indexed by StringPool order.
     const size_t beforeResIdMapIndex = outBuffer->size();
     android::ResChunk_header* resIdMapChunk = outBuffer->nextBlock<android::ResChunk_header>();
     resIdMapChunk->type = android::RES_XML_RESOURCE_MAP_TYPE;
     resIdMapChunk->headerSize = sizeof(*resIdMapChunk);
-    for (const auto& str : pool) {
+    for (const auto& str : *pool) {
         ResourceId id { str->context.priority };
-        if (!id.isValid()) {
+        if (id.id == kLowPriority || !id.isValid()) {
             // When we see the first non-resource ID,
             // we're done.
             break;
         }
 
-        uint32_t* flatId = outBuffer->nextBlock<uint32_t>();
-        *flatId = id.id;
+        *outBuffer->nextBlock<uint32_t>() = id.id;
     }
     resIdMapChunk->size = outBuffer->size() - beforeResIdMapIndex;
 
     // Move the temporary BigBuffer into outBuffer.
-    outBuffer->appendBuffer(std::move(out));
-
+    outBuffer->appendBuffer(std::move(xmlTreeBuffer));
     header->header.size = outBuffer->size() - beforeXmlTreeIndex;
+}
+
+bool flatten(Node* root, const std::u16string& defaultPackage, BigBuffer* outBuffer) {
+    StringPool pool;
+
+    // This will hold the StringRefs and the location in which to write the index.
+    // Once we sort the StringPool, we can assign the updated indices
+    // to the correct data locations.
+    FlatStringRefList stringRefs;
+
+    // Since we don't know the size of the final StringPool, we write to this
+    // temporary BigBuffer, which we will append to outBuffer later.
+    BigBuffer out(1024);
+
+    CompileXmlFlattener flattener(&out, &pool, &stringRefs, defaultPackage);
+    root->accept(&flattener);
+
+    if (!flattener.success()) {
+        return false;
+    }
+
+    flattenXml(&pool, &stringRefs, outBuffer, std::move(out));
+    return true;
+};
+
+Maybe<size_t> flattenAndLink(const Source& source, Node* root,
+                             const std::u16string& defaultPackage,
+                             const std::shared_ptr<IResolver>& resolver,
+                             const FlattenOptions& options, BigBuffer* outBuffer) {
+    SourceLogger logger(source);
+    StringPool pool;
+
+    // Attribute names are stored without packages, but we use
+    // their StringPool index to lookup their resource IDs.
+    // This will cause collisions, so we can't dedupe
+    // attribute names from different packages. We use separate
+    // pools that we later combine.
+    std::map<std::u16string, StringPool> packagePools;
+
+    FlatStringRefList stringRefs;
+
+    // Since we don't know the size of the final StringPool, we write to this
+    // temporary BigBuffer, which we will append to outBuffer later.
+    BigBuffer out(1024);
+
+    LinkedXmlFlattener flattener(&out, &pool, &packagePools, &stringRefs, defaultPackage, resolver,
+                                 &logger, options);
+    root->accept(&flattener);
+
+    if (!flattener.success()) {
+        return {};
+    }
+
+    // Merge the package pools into the main pool.
+    for (auto& packagePoolEntry : packagePools) {
+        pool.merge(std::move(packagePoolEntry.second));
+    }
+
+    flattenXml(&pool, &stringRefs, outBuffer, std::move(out));
 
-    if (smallestStrippedAttributeSdk == std::numeric_limits<size_t>::max()) {
-        // Nothing was stripped
-        return 0u;
+    if (flattener.getSmallestFilteredSdk()) {
+        return flattener.getSmallestFilteredSdk();
     }
-    return smallestStrippedAttributeSdk;
+    return 0;
 }
 
+} // namespace xml
 } // namespace aapt