Implement back-tracking when searching for attributes in XML or resource bag

Shared libraries have their package ID assigned at run-time, so some
of the guarantees we used to have about sort order of attributes in
bags or XML elements no longer hold.

This CL adds back-tracking and can jump to the nearest attribute with the
same package ID and continue searching.

This means that attributes with the same package ID must be sorted by increasing
resource ID, as was the case before.

Attributes with the same package ID must be grouped together, but the groups can
be in any order. Ex: 0x02010001, 0x02010002, 0x01010000, 0x01010010, 0x7f010032

Bug:17666947
Change-Id: I9c198bbb6ca788849aac85b6323606ea5d9550d6

1 files changed, 73 insertions, 62 deletions

diff --git a/core/jni/android_util_AssetManager.cpp b/core/jni/android_util_AssetManager.cpp
index 94098c9..fba7255 100644
--- a/core/jni/android_util_AssetManager.cpp
+++ b/core/jni/android_util_AssetManager.cpp
@@ -33,6 +33,7 @@
 
 #include <androidfw/Asset.h>
 #include <androidfw/AssetManager.h>
+#include <androidfw/AttributeFinder.h>
 #include <androidfw/ResourceTypes.h>
 
 #include <private/android_filesystem_config.h> // for AID_SYSTEM
@@ -999,6 +1000,30 @@ static void android_content_AssetManager_dumpTheme(JNIEnv* env, jobject clazz,
     theme->dumpToLog();
 }
 
+class XmlAttributeFinder : public BackTrackingAttributeFinder<XmlAttributeFinder, jsize> {
+public:
+    XmlAttributeFinder(const ResXMLParser* parser)
+        : BackTrackingAttributeFinder(0, parser != NULL ? parser->getAttributeCount() : 0)
+        , mParser(parser) {}
+
+    inline uint32_t getAttribute(jsize index) const {
+        return mParser->getAttributeNameResID(index);
+    }
+
+private:
+    const ResXMLParser* mParser;
+};
+
+class BagAttributeFinder : public BackTrackingAttributeFinder<BagAttributeFinder, const ResTable::bag_entry*> {
+public:
+    BagAttributeFinder(const ResTable::bag_entry* start, const ResTable::bag_entry* end)
+        : BackTrackingAttributeFinder(start, end) {}
+
+    inline uint32_t getAttribute(const ResTable::bag_entry* entry) const {
+        return entry->map.name.ident;
+    }
+};
+
 static jboolean android_content_AssetManager_resolveAttrs(JNIEnv* env, jobject clazz,
                                                           jlong themeToken,
                                                           jint defStyleAttr,
@@ -1074,13 +1099,13 @@ static jboolean android_content_AssetManager_resolveAttrs(JNIEnv* env, jobject c
     res.lock();
 
     // Retrieve the default style bag, if requested.
-    const ResTable::bag_entry* defStyleEnt = NULL;
+    const ResTable::bag_entry* defStyleStart = NULL;
     uint32_t defStyleTypeSetFlags = 0;
     ssize_t bagOff = defStyleRes != 0
-            ? res.getBagLocked(defStyleRes, &defStyleEnt, &defStyleTypeSetFlags) : -1;
+            ? res.getBagLocked(defStyleRes, &defStyleStart, &defStyleTypeSetFlags) : -1;
     defStyleTypeSetFlags |= defStyleBagTypeSetFlags;
-    const ResTable::bag_entry* endDefStyleEnt = defStyleEnt +
-        (bagOff >= 0 ? bagOff : 0);;
+    const ResTable::bag_entry* const defStyleEnd = defStyleStart + (bagOff >= 0 ? bagOff : 0);
+    BagAttributeFinder defStyleAttrFinder(defStyleStart, defStyleEnd);
 
     // Now iterate through all of the attributes that the client has requested,
     // filling in each with whatever data we can find.
@@ -1108,20 +1133,15 @@ static jboolean android_content_AssetManager_resolveAttrs(JNIEnv* env, jobject c
                     value.dataType, value.data));
         }
 
-        // Skip through the default style values until the end or the next possible match.
-        while (defStyleEnt < endDefStyleEnt && curIdent > defStyleEnt->map.name.ident) {
-            defStyleEnt++;
-        }
-        // Retrieve the current default style attribute if it matches, and step to next.
-        if (defStyleEnt < endDefStyleEnt && curIdent == defStyleEnt->map.name.ident) {
-            if (value.dataType == Res_value::TYPE_NULL) {
-                block = defStyleEnt->stringBlock;
+        if (value.dataType == Res_value::TYPE_NULL) {
+            const ResTable::bag_entry* const defStyleEntry = defStyleAttrFinder.find(curIdent);
+            if (defStyleEntry != defStyleEnd) {
+                block = defStyleEntry->stringBlock;
                 typeSetFlags = defStyleTypeSetFlags;
-                value = defStyleEnt->map.value;
+                value = defStyleEntry->map.value;
                 DEBUG_STYLES(ALOGI("-> From def style: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
-            defStyleEnt++;
         }
 
         uint32_t resid = 0;
@@ -1284,34 +1304,32 @@ static jboolean android_content_AssetManager_applyStyle(JNIEnv* env, jobject cla
     res.lock();
 
     // Retrieve the default style bag, if requested.
-    const ResTable::bag_entry* defStyleEnt = NULL;
+    const ResTable::bag_entry* defStyleAttrStart = NULL;
     uint32_t defStyleTypeSetFlags = 0;
     ssize_t bagOff = defStyleRes != 0
-            ? res.getBagLocked(defStyleRes, &defStyleEnt, &defStyleTypeSetFlags) : -1;
+            ? res.getBagLocked(defStyleRes, &defStyleAttrStart, &defStyleTypeSetFlags) : -1;
     defStyleTypeSetFlags |= defStyleBagTypeSetFlags;
-    const ResTable::bag_entry* endDefStyleEnt = defStyleEnt +
-        (bagOff >= 0 ? bagOff : 0);
+    const ResTable::bag_entry* const defStyleAttrEnd = defStyleAttrStart + (bagOff >= 0 ? bagOff : 0);
+    BagAttributeFinder defStyleAttrFinder(defStyleAttrStart, defStyleAttrEnd);
 
     // Retrieve the style class bag, if requested.
-    const ResTable::bag_entry* styleEnt = NULL;
+    const ResTable::bag_entry* styleAttrStart = NULL;
     uint32_t styleTypeSetFlags = 0;
-    bagOff = style != 0 ? res.getBagLocked(style, &styleEnt, &styleTypeSetFlags) : -1;
+    bagOff = style != 0 ? res.getBagLocked(style, &styleAttrStart, &styleTypeSetFlags) : -1;
     styleTypeSetFlags |= styleBagTypeSetFlags;
-    const ResTable::bag_entry* endStyleEnt = styleEnt +
-        (bagOff >= 0 ? bagOff : 0);
+    const ResTable::bag_entry* const styleAttrEnd = styleAttrStart + (bagOff >= 0 ? bagOff : 0);
+    BagAttributeFinder styleAttrFinder(styleAttrStart, styleAttrEnd);
 
     // Retrieve the XML attributes, if requested.
-    const jsize NX = xmlParser ? xmlParser->getAttributeCount() : 0;
-    jsize ix=0;
-    uint32_t curXmlAttr = xmlParser ? xmlParser->getAttributeNameResID(ix) : 0;
-
     static const ssize_t kXmlBlock = 0x10000000;
+    XmlAttributeFinder xmlAttrFinder(xmlParser);
+    const jsize xmlAttrEnd = xmlParser != NULL ? xmlParser->getAttributeCount() : 0;
 
     // Now iterate through all of the attributes that the client has requested,
     // filling in each with whatever data we can find.
     ssize_t block = 0;
     uint32_t typeSetFlags;
-    for (jsize ii=0; ii<NI; ii++) {
+    for (jsize ii = 0; ii < NI; ii++) {
         const uint32_t curIdent = (uint32_t)src[ii];
 
         DEBUG_STYLES(ALOGI("RETRIEVING ATTR 0x%08x...", curIdent));
@@ -1324,51 +1342,40 @@ static jboolean android_content_AssetManager_applyStyle(JNIEnv* env, jobject cla
         typeSetFlags = 0;
         config.density = 0;
 
-        // Skip through XML attributes until the end or the next possible match.
-        while (ix < NX && curIdent > curXmlAttr) {
-            ix++;
-            curXmlAttr = xmlParser->getAttributeNameResID(ix);
-        }
-        // Retrieve the current XML attribute if it matches, and step to next.
-        if (ix < NX && curIdent == curXmlAttr) {
+        // Walk through the xml attributes looking for the requested attribute.
+        const jsize xmlAttrIdx = xmlAttrFinder.find(curIdent);
+        if (xmlAttrIdx != xmlAttrEnd) {
+            // We found the attribute we were looking for.
             block = kXmlBlock;
-            xmlParser->getAttributeValue(ix, &value);
-            ix++;
-            curXmlAttr = xmlParser->getAttributeNameResID(ix);
+            xmlParser->getAttributeValue(xmlAttrIdx, &value);
             DEBUG_STYLES(ALOGI("-> From XML: type=0x%x, data=0x%08x",
                     value.dataType, value.data));
         }
 
-        // Skip through the style values until the end or the next possible match.
-        while (styleEnt < endStyleEnt && curIdent > styleEnt->map.name.ident) {
-            styleEnt++;
-        }
-        // Retrieve the current style attribute if it matches, and step to next.
-        if (styleEnt < endStyleEnt && curIdent == styleEnt->map.name.ident) {
-            if (value.dataType == Res_value::TYPE_NULL) {
-                block = styleEnt->stringBlock;
+        if (value.dataType == Res_value::TYPE_NULL) {
+            // Walk through the style class values looking for the requested attribute.
+            const ResTable::bag_entry* const styleAttrEntry = styleAttrFinder.find(curIdent);
+            if (styleAttrEntry != styleAttrEnd) {
+                // We found the attribute we were looking for.
+                block = styleAttrEntry->stringBlock;
                 typeSetFlags = styleTypeSetFlags;
-                value = styleEnt->map.value;
+                value = styleAttrEntry->map.value;
                 DEBUG_STYLES(ALOGI("-> From style: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
-            styleEnt++;
         }
 
-        // Skip through the default style values until the end or the next possible match.
-        while (defStyleEnt < endDefStyleEnt && curIdent > defStyleEnt->map.name.ident) {
-            defStyleEnt++;
-        }
-        // Retrieve the current default style attribute if it matches, and step to next.
-        if (defStyleEnt < endDefStyleEnt && curIdent == defStyleEnt->map.name.ident) {
-            if (value.dataType == Res_value::TYPE_NULL) {
-                block = defStyleEnt->stringBlock;
-                typeSetFlags = defStyleTypeSetFlags;
-                value = defStyleEnt->map.value;
+        if (value.dataType == Res_value::TYPE_NULL) {
+            // Walk through the default style values looking for the requested attribute.
+            const ResTable::bag_entry* const defStyleAttrEntry = defStyleAttrFinder.find(curIdent);
+            if (defStyleAttrEntry != defStyleAttrEnd) {
+                // We found the attribute we were looking for.
+                block = defStyleAttrEntry->stringBlock;
+                typeSetFlags = styleTypeSetFlags;
+                value = defStyleAttrEntry->map.value;
                 DEBUG_STYLES(ALOGI("-> From def style: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
-            defStyleEnt++;
         }
 
         uint32_t resid = 0;
@@ -1376,7 +1383,9 @@ static jboolean android_content_AssetManager_applyStyle(JNIEnv* env, jobject cla
             // Take care of resolving the found resource to its final value.
             ssize_t newBlock = theme->resolveAttributeReference(&value, block,
                     &resid, &typeSetFlags, &config);
-            if (newBlock >= 0) block = newBlock;
+            if (newBlock >= 0) {
+                block = newBlock;
+            }
             DEBUG_STYLES(ALOGI("-> Resolved attr: type=0x%x, data=0x%08x",
                     value.dataType, value.data));
         } else {
@@ -1394,7 +1403,9 @@ static jboolean android_content_AssetManager_applyStyle(JNIEnv* env, jobject cla
                     return JNI_FALSE;
                 }
 #endif
-                if (newBlock >= 0) block = newBlock;
+                if (newBlock >= 0) {
+                    block = newBlock;
+                }
                 DEBUG_STYLES(ALOGI("-> Resolved theme: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
@@ -1414,8 +1425,8 @@ static jboolean android_content_AssetManager_applyStyle(JNIEnv* env, jobject cla
         // Write the final value back to Java.
         dest[STYLE_TYPE] = value.dataType;
         dest[STYLE_DATA] = value.data;
-        dest[STYLE_ASSET_COOKIE] =
-            block != kXmlBlock ? reinterpret_cast<jint>(res.getTableCookie(block)) : (jint)-1;
+        dest[STYLE_ASSET_COOKIE] = block != kXmlBlock ?
+            static_cast<jint>(res.getTableCookie(block)) : -1;
         dest[STYLE_RESOURCE_ID] = resid;
         dest[STYLE_CHANGING_CONFIGURATIONS] = typeSetFlags;
         dest[STYLE_DENSITY] = config.density;