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

2 files changed, 112 insertions, 0 deletions

diff --git a/libs/androidfw/tests/Android.mk b/libs/androidfw/tests/Android.mk
index 2d7906f28ba3..c1014be1a74b 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 000000000000..664709c4ae8c
--- /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));
+}