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

5 files changed, 393 insertions, 65 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;
diff --git a/include/androidfw/AttributeFinder.h b/include/androidfw/AttributeFinder.h
new file mode 100644
index 0000000..a0ffeb3
--- /dev/null
+++ b/include/androidfw/AttributeFinder.h
@@ -0,0 +1,201 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#ifndef H_ATTRIBUTE_FINDER
+#define H_ATTRIBUTE_FINDER
+
+#include <stdint.h>
+#include <utils/KeyedVector.h>
+
+namespace android {
+
+static inline uint32_t getPackage(uint32_t attr) {
+    return attr >> 24;
+}
+
+/**
+ * A helper class to search linearly for the requested
+ * attribute, maintaining it's position and optimizing for
+ * the case that subsequent searches will involve an attribute with
+ * a higher attribute ID.
+ *
+ * In the case that a subsequent attribute has a different package ID,
+ * its resource ID may not be larger than the preceding search, so
+ * back tracking is supported for this case. This
+ * back tracking requirement is mainly for shared library
+ * resources, whose package IDs get assigned at runtime
+ * and thus attributes from a shared library may
+ * be out of order.
+ *
+ * We make two assumptions about the order of attributes:
+ * 1) The input has the same sorting rules applied to it as
+ *    the attribute data contained by this class.
+ * 2) Attributes are grouped by package ID.
+ * 3) Among attributes with the same package ID, the attributes are
+ *    sorted by increasing resource ID.
+ *
+ * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003
+ *
+ * The total order of attributes (including package ID) can not be linear
+ * as shared libraries get assigned dynamic package IDs at runtime, which
+ * may break the sort order established at build time.
+ */
+template <typename Derived, typename Iterator>
+class BackTrackingAttributeFinder {
+public:
+    BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end);
+
+    Iterator find(uint32_t attr);
+
+private:
+    void jumpToClosestAttribute(uint32_t packageId);
+    void markCurrentPackageId(uint32_t packageId);
+
+    Iterator mBegin;
+    Iterator mEnd;
+    Iterator mCurrent;
+    Iterator mLargest;
+    uint32_t mLastPackageId;
+    uint32_t mCurrentAttr;
+
+    // Package Offsets (best-case, fast look-up).
+    Iterator mFrameworkStart;
+    Iterator mAppStart;
+
+    // Worst case, we have shared-library resources.
+    KeyedVector<uint32_t, Iterator> mPackageOffsets;
+};
+
+template <typename Derived, typename Iterator> inline
+BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end)
+    : mBegin(begin)
+    , mEnd(end)
+    , mCurrent(begin)
+    , mLargest(begin)
+    , mLastPackageId(0)
+    , mCurrentAttr(0)
+    , mFrameworkStart(end)
+    , mAppStart(end) {
+}
+
+template <typename Derived, typename Iterator>
+void BackTrackingAttributeFinder<Derived, Iterator>::jumpToClosestAttribute(const uint32_t packageId) {
+    switch (packageId) {
+        case 0x01:
+            mCurrent = mFrameworkStart;
+            break;
+        case 0x7f:
+            mCurrent = mAppStart;
+            break;
+        default: {
+            ssize_t idx = mPackageOffsets.indexOfKey(packageId);
+            if (idx >= 0) {
+                // We have seen this package ID before, so jump to the first
+                // attribute with this package ID.
+                mCurrent = mPackageOffsets[idx];
+            } else {
+                mCurrent = mEnd;
+            }
+            break;
+        }
+    }
+
+    // We have never seen this package ID yet, so jump to the
+    // latest/largest index we have processed so far.
+    if (mCurrent == mEnd) {
+        mCurrent = mLargest;
+    }
+
+    if (mCurrent != mEnd) {
+        mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
+    }
+}
+
+template <typename Derived, typename Iterator>
+void BackTrackingAttributeFinder<Derived, Iterator>::markCurrentPackageId(const uint32_t packageId) {
+    switch (packageId) {
+        case 0x01:
+            mFrameworkStart = mCurrent;
+            break;
+        case 0x7f:
+            mAppStart = mCurrent;
+            break;
+        default:
+            mPackageOffsets.add(packageId, mCurrent);
+            break;
+    }
+}
+
+template <typename Derived, typename Iterator>
+Iterator BackTrackingAttributeFinder<Derived, Iterator>::find(uint32_t attr) {
+    if (!(mBegin < mEnd)) {
+        return mEnd;
+    }
+
+    if (mCurrentAttr == 0) {
+        // One-time initialization.
+        mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mBegin);
+        mLastPackageId = getPackage(mCurrentAttr);
+        markCurrentPackageId(mLastPackageId);
+    }
+
+    // Looking for the needle (attribute we're looking for)
+    // in the haystack (the attributes we're searching through)
+    const uint32_t needlePackageId = getPackage(attr);
+    if (mLastPackageId != needlePackageId) {
+        jumpToClosestAttribute(needlePackageId);
+        mLastPackageId = needlePackageId;
+    }
+
+    // Walk through the xml attributes looking for the requested attribute.
+    while (mCurrent != mEnd) {
+        const uint32_t haystackPackageId = getPackage(mCurrentAttr);
+        if (needlePackageId == haystackPackageId && attr < mCurrentAttr) {
+            // The attribute we are looking was not found.
+            break;
+        }
+        const uint32_t prevAttr = mCurrentAttr;
+
+        // Move to the next attribute in the XML.
+        ++mCurrent;
+        if (mCurrent != mEnd) {
+            mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
+            const uint32_t newHaystackPackageId = getPackage(mCurrentAttr);
+            if (haystackPackageId != newHaystackPackageId) {
+                // We've moved to the next group of attributes
+                // with a new package ID, so we should record
+                // the offset of this new package ID.
+                markCurrentPackageId(newHaystackPackageId);
+            }
+        }
+
+        if (mCurrent > mLargest) {
+            // We've moved past the latest attribute we've
+            // seen.
+            mLargest = mCurrent;
+        }
+
+        if (attr == prevAttr) {
+            // We found the attribute we were looking for.
+            return mCurrent - 1;
+        }
+    }
+    return mEnd;
+}
+
+} // namespace android
+
+#endif // H_ATTRIBUTE_FINDER
diff --git a/libs/androidfw/ResourceTypes.cpp b/libs/androidfw/ResourceTypes.cpp
index f1e4858..420fe38 100644
--- a/libs/androidfw/ResourceTypes.cpp
+++ b/libs/androidfw/ResourceTypes.cpp
@@ -1185,7 +1185,11 @@ uint32_t ResXMLParser::getAttributeNameResID(size_t idx) const
 {
     int32_t id = getAttributeNameID(idx);
     if (id >= 0 && (size_t)id < mTree.mNumResIds) {
-        return dtohl(mTree.mResIds[id]);
+        uint32_t resId = dtohl(mTree.mResIds[id]);
+        if (mTree.mDynamicRefTable != NULL) {
+            mTree.mDynamicRefTable->lookupResourceId(&resId);
+        }
+        return resId;
     }
     return 0;
 }
@@ -5973,11 +5977,11 @@ status_t DynamicRefTable::lookupResourceId(uint32_t* resId) const {
     // Do a proper lookup.
     uint8_t translatedId = mLookupTable[packageId];
     if (translatedId == 0) {
-        ALOGE("DynamicRefTable(0x%02x): No mapping for build-time package ID 0x%02x.",
+        ALOGV("DynamicRefTable(0x%02x): No mapping for build-time package ID 0x%02x.",
                 (uint8_t)mAssignedPackageId, (uint8_t)packageId);
         for (size_t i = 0; i < 256; i++) {
             if (mLookupTable[i] != 0) {
-                ALOGE("e[0x%02x] -> 0x%02x", (uint8_t)i, mLookupTable[i]);
+                ALOGV("e[0x%02x] -> 0x%02x", (uint8_t)i, mLookupTable[i]);
             }
         }
         return UNKNOWN_ERROR;
diff --git a/libs/androidfw/tests/Android.mk b/libs/androidfw/tests/Android.mk
index 2d7906f..c1014be 100644
--- a/libs/androidfw/tests/Android.mk
+++ b/libs/androidfw/tests/Android.mk
@@ -20,6 +20,7 @@
 # ==========================================================
 LOCAL_PATH:= $(call my-dir)
 testFiles := \
+    AttributeFinder_test.cpp \
     ByteBucketArray_test.cpp \
     Config_test.cpp \
     ConfigLocale_test.cpp \
diff --git a/libs/androidfw/tests/AttributeFinder_test.cpp b/libs/androidfw/tests/AttributeFinder_test.cpp
new file mode 100644
index 0000000..664709c
--- /dev/null
+++ b/libs/androidfw/tests/AttributeFinder_test.cpp
@@ -0,0 +1,111 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include <androidfw/AttributeFinder.h>
+
+#include <gtest/gtest.h>
+
+using android::BackTrackingAttributeFinder;
+
+class MockAttributeFinder : public BackTrackingAttributeFinder<MockAttributeFinder, int> {
+public:
+    MockAttributeFinder(const uint32_t* attrs, int len)
+        : BackTrackingAttributeFinder(0, len) {
+        mAttrs = new uint32_t[len];
+        memcpy(mAttrs, attrs, sizeof(*attrs) * len);
+    }
+
+    ~MockAttributeFinder() {
+        delete mAttrs;
+    }
+
+    inline uint32_t getAttribute(const int index) const {
+        return mAttrs[index];
+    }
+
+private:
+    uint32_t* mAttrs;
+};
+
+static const uint32_t sortedAttributes[] = {
+        0x01010000, 0x01010001, 0x01010002, 0x01010004,
+        0x02010001, 0x02010010, 0x7f010001
+};
+
+static const uint32_t packageUnsortedAttributes[] = {
+        0x02010001, 0x02010010, 0x01010000, 0x01010001,
+        0x01010002, 0x01010004, 0x7f010001
+};
+
+TEST(AttributeFinderTest, IteratesSequentially) {
+    const int end = sizeof(sortedAttributes) / sizeof(*sortedAttributes);
+    MockAttributeFinder finder(sortedAttributes, end);
+
+    EXPECT_EQ(0, finder.find(0x01010000));
+    EXPECT_EQ(1, finder.find(0x01010001));
+    EXPECT_EQ(2, finder.find(0x01010002));
+    EXPECT_EQ(3, finder.find(0x01010004));
+    EXPECT_EQ(4, finder.find(0x02010001));
+    EXPECT_EQ(5, finder.find(0x02010010));
+    EXPECT_EQ(6, finder.find(0x7f010001));
+    EXPECT_EQ(end, finder.find(0x7f010002));
+}
+
+TEST(AttributeFinderTest, PackagesAreOutOfOrder) {
+    const int end = sizeof(sortedAttributes) / sizeof(*sortedAttributes);
+    MockAttributeFinder finder(sortedAttributes, end);
+
+    EXPECT_EQ(6, finder.find(0x7f010001));
+    EXPECT_EQ(end, finder.find(0x7f010002));
+    EXPECT_EQ(4, finder.find(0x02010001));
+    EXPECT_EQ(5, finder.find(0x02010010));
+    EXPECT_EQ(0, finder.find(0x01010000));
+    EXPECT_EQ(1, finder.find(0x01010001));
+    EXPECT_EQ(2, finder.find(0x01010002));
+    EXPECT_EQ(3, finder.find(0x01010004));
+}
+
+TEST(AttributeFinderTest, SomeAttributesAreNotFound) {
+    const int end = sizeof(sortedAttributes) / sizeof(*sortedAttributes);
+    MockAttributeFinder finder(sortedAttributes, end);
+
+    EXPECT_EQ(0, finder.find(0x01010000));
+    EXPECT_EQ(1, finder.find(0x01010001));
+    EXPECT_EQ(2, finder.find(0x01010002));
+    EXPECT_EQ(end, finder.find(0x01010003));
+    EXPECT_EQ(3, finder.find(0x01010004));
+    EXPECT_EQ(end, finder.find(0x01010005));
+    EXPECT_EQ(end, finder.find(0x01010006));
+    EXPECT_EQ(4, finder.find(0x02010001));
+    EXPECT_EQ(end, finder.find(0x02010002));
+}
+
+TEST(AttributeFinderTest, FindAttributesInPackageUnsortedAttributeList) {
+    const int end = sizeof(packageUnsortedAttributes) / sizeof(*packageUnsortedAttributes);
+    MockAttributeFinder finder(packageUnsortedAttributes, end);
+
+    EXPECT_EQ(2, finder.find(0x01010000));
+    EXPECT_EQ(3, finder.find(0x01010001));
+    EXPECT_EQ(4, finder.find(0x01010002));
+    EXPECT_EQ(end, finder.find(0x01010003));
+    EXPECT_EQ(5, finder.find(0x01010004));
+    EXPECT_EQ(end, finder.find(0x01010005));
+    EXPECT_EQ(end, finder.find(0x01010006));
+    EXPECT_EQ(0, finder.find(0x02010001));
+    EXPECT_EQ(end, finder.find(0x02010002));
+    EXPECT_EQ(1, finder.find(0x02010010));
+    EXPECT_EQ(6, finder.find(0x7f010001));
+}