Fix bug in TreeIndex erase().
erase() is supposed to avoid accessing the row that is being erased. This is important in particular when rolling back an insertion due to a later index reporting an insertion failure.
diff --git a/c++/src/kj/table-test.c++ b/c++/src/kj/table-test.c++
index 77f6d9c..acde654 100644
--- a/c++/src/kj/table-test.c++
+++ b/c++/src/kj/table-test.c++
@@ -1317,6 +1317,94 @@
KJ_EXPECT(iter == range.end());
}
+// =======================================================================================
+// Test bug where insertion failure on a later index in the table would not be rolled back
+// correctly if a previous index was TreeIndex.
+
+class StringLengthCompare {
+ // Considers two strings equal if they have the same length.
+public:
+ inline size_t keyForRow(StringPtr entry) const {
+ return entry.size();
+ }
+
+ inline bool matches(StringPtr e, size_t key) const {
+ return e.size() == key;
+ }
+
+ inline bool isBefore(StringPtr e, size_t key) const {
+ return e.size() < key;
+ }
+
+ uint hashCode(size_t size) const {
+ return size;
+ }
+};
+
+KJ_TEST("HashIndex rollback on insertion failure") {
+ // Test that when an insertion produces a duplicate on a later index, changes to previous indexes
+ // are properly rolled back.
+
+ Table<StringPtr, HashIndex<StringHasher>, HashIndex<StringLengthCompare>> table;
+ table.insert("a"_kj);
+ table.insert("ab"_kj);
+ table.insert("abc"_kj);
+
+ {
+ // We use upsert() so that we don't throw an exception from the duplicate, but this exercises
+ // the same logic as a duplicate insert() other than throwing.
+ kj::StringPtr& found = table.upsert("xyz"_kj, [&](StringPtr& existing, StringPtr&& param) {
+ KJ_EXPECT(existing == "abc");
+ KJ_EXPECT(param == "xyz");
+ });
+ KJ_EXPECT(found == "abc");
+
+ table.erase(found);
+ }
+
+ table.insert("xyz"_kj);
+
+ {
+ kj::StringPtr& found = table.upsert("tuv"_kj, [&](StringPtr& existing, StringPtr&& param) {
+ KJ_EXPECT(existing == "xyz");
+ KJ_EXPECT(param == "tuv");
+ });
+ KJ_EXPECT(found == "xyz");
+ }
+}
+
+KJ_TEST("TreeIndex rollback on insertion failure") {
+ // Test that when an insertion produces a duplicate on a later index, changes to previous indexes
+ // are properly rolled back.
+
+ Table<StringPtr, TreeIndex<StringCompare>, TreeIndex<StringLengthCompare>> table;
+ table.insert("a"_kj);
+ table.insert("ab"_kj);
+ table.insert("abc"_kj);
+
+ {
+ // We use upsert() so that we don't throw an exception from the duplicate, but this exercises
+ // the same logic as a duplicate insert() other than throwing.
+ kj::StringPtr& found = table.upsert("xyz"_kj, [&](StringPtr& existing, StringPtr&& param) {
+ KJ_EXPECT(existing == "abc");
+ KJ_EXPECT(param == "xyz");
+ });
+ KJ_EXPECT(found == "abc");
+
+ table.erase(found);
+ }
+
+ table.insert("xyz"_kj);
+
+ {
+ kj::StringPtr& found = table.upsert("tuv"_kj, [&](StringPtr& existing, StringPtr&& param) {
+ KJ_EXPECT(existing == "xyz");
+ KJ_EXPECT(param == "tuv");
+ });
+ KJ_EXPECT(found == "xyz");
+ }
+}
+
} // namespace
} // namespace _
} // namespace kj
diff --git a/c++/src/kj/table.h b/c++/src/kj/table.h
index 7af8409..630b79c 100644
--- a/c++/src/kj/table.h
+++ b/c++/src/kj/table.h
@@ -1484,7 +1484,7 @@
template <typename Row, typename... Params>
void erase(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
- impl.erase(pos, searchKey(table, params...));
+ impl.erase(pos, searchKeyForErase(table, pos, params...));
}
template <typename Row, typename... Params>
@@ -1537,6 +1537,16 @@
auto predicate = [&](uint i) { return cb.isBefore(table[i], params...); };
return SearchKeyImpl<decltype(predicate)>(kj::mv(predicate));
}
+
+ template <typename Row, typename... Params>
+ inline auto searchKeyForErase(kj::ArrayPtr<Row>& table, uint pos, Params&... params) const {
+ // When erasing, the table entry for the erased row may already be invalid, so we must avoid
+ // accessing it.
+ auto predicate = [&,pos](uint i) {
+ return i != pos && cb.isBefore(table[i], params...);
+ };
+ return SearchKeyImpl<decltype(predicate)>(kj::mv(predicate));
+ }
};
// -----------------------------------------------------------------------------
