diff options
Diffstat (limited to 'src/mongo/db/query/index_bounds_test.cpp')
| -rw-r--r-- | src/mongo/db/query/index_bounds_test.cpp | 1282 |
1 files changed, 642 insertions, 640 deletions
diff --git a/src/mongo/db/query/index_bounds_test.cpp b/src/mongo/db/query/index_bounds_test.cpp index d5cc470b3af..d1613ca0c94 100644 --- a/src/mongo/db/query/index_bounds_test.cpp +++ b/src/mongo/db/query/index_bounds_test.cpp @@ -42,659 +42,661 @@ using namespace mongo; namespace { - // - // Validation - // - - TEST(IndexBoundsTest, ValidBasic) { - OrderedIntervalList list("foo"); - list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - IndexBounds bounds; - bounds.fields.push_back(list); - - // Go forwards with data indexed forwards. - ASSERT(bounds.isValidFor(BSON("foo" << 1), 1)); - // Go backwards with data indexed backwards. - ASSERT(bounds.isValidFor(BSON("foo" << -1), -1)); - // Bounds are not oriented along the direction of traversal. - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), -1)); - - // Bounds must match the index exactly. - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1 << "bar" << 1), 1)); - ASSERT_FALSE(bounds.isValidFor(BSON("bar" << 1), 1)); - } - - TEST(IndexBoundsTest, ValidTwoFields) { - OrderedIntervalList list("foo"); - list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - IndexBounds bounds; - bounds.fields.push_back(list); - - // Let's add another field - OrderedIntervalList otherList("bar"); - otherList.intervals.push_back(Interval(BSON("" << 0 << "" << 3), true, true)); - bounds.fields.push_back(otherList); - - // These are OK. - ASSERT(bounds.isValidFor(BSON("foo" << 1 << "bar" << 1), 1)); - ASSERT(bounds.isValidFor(BSON("foo" << -1 << "bar" << -1), -1)); - - // Direction(s) don't match. - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << -1 << "bar" << 1), -1)); - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1 << "bar" << -1), -1)); - - // Index doesn't match. - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1)); - ASSERT_FALSE(bounds.isValidFor(BSON("bar" << 1 << "foo" << 1), 1)); - } - - TEST(IndexBoundsTest, ValidIntervalsInOrder) { - OrderedIntervalList list("foo"); - // Whether navigated forward or backward, there's no valid ordering for these two intervals. - list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - list.intervals.push_back(Interval(BSON("" << 0 << "" << 5), true, true)); - IndexBounds bounds; - bounds.fields.push_back(list); - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1)); - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << -1), 1)); - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), -1)); - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << -1), -1)); - } - - TEST(IndexBoundsTest, ValidNoOverlappingIntervals) { - OrderedIntervalList list("foo"); - // overlapping intervals not allowed. - list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - list.intervals.push_back(Interval(BSON("" << 19 << "" << 25), true, true)); - IndexBounds bounds; - bounds.fields.push_back(list); - ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1)); - } - - TEST(IndexBoundsTest, ValidOverlapOnlyWhenBothOpen) { - OrderedIntervalList list("foo"); - list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, false)); - list.intervals.push_back(Interval(BSON("" << 20 << "" << 25), false, true)); - IndexBounds bounds; - bounds.fields.push_back(list); - ASSERT(bounds.isValidFor(BSON("foo" << 1), 1)); - } - - // - // Tests for OrderedIntervalList::complement() - // - - /** - * Get a BSONObj which represents the interval from - * MinKey to 'end'. - */ - BSONObj minKeyIntObj(int end) { - BSONObjBuilder bob; - bob.appendMinKey(""); - bob.appendNumber("", end); - return bob.obj(); - } - - /** - * Get a BSONObj which represents the interval from - * 'start' to MaxKey. - */ - BSONObj maxKeyIntObj(int start) { - BSONObjBuilder bob; - bob.appendNumber("", start); - bob.appendMaxKey(""); - return bob.obj(); - } - - /** - * Get a BSONObj which represents the interval - * [MinKey, MaxKey]. - */ - BSONObj allValues() { - BSONObjBuilder bob; - bob.appendMinKey(""); - bob.appendMaxKey(""); - return bob.obj(); - } - - /** - * Test that if we complement the OIL twice, - * we get back the original OIL. - */ - void testDoubleComplement(const OrderedIntervalList* oil) { - OrderedIntervalList clone; - for (size_t i = 0; i < oil->intervals.size(); ++i) { - clone.intervals.push_back(oil->intervals[i]); - } - - clone.complement(); - clone.complement(); - - ASSERT_EQUALS(oil->intervals.size(), clone.intervals.size()); - for (size_t i = 0; i < oil->intervals.size(); ++i) { - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, - oil->intervals[i].compare(clone.intervals[i])); - } - } - - // Complement of empty is [MinKey, MaxKey] - TEST(IndexBoundsTest, ComplementEmptyOil) { - OrderedIntervalList oil; - testDoubleComplement(&oil); - oil.complement(); - ASSERT_EQUALS(oil.intervals.size(), 1U); - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare( - Interval(allValues(), true, true))); - } - - // Complement of [MinKey, MaxKey] is empty - TEST(IndexBoundsTest, ComplementAllValues) { - OrderedIntervalList oil; - oil.intervals.push_back(Interval(allValues(), true, true)); - testDoubleComplement(&oil); - oil.complement(); - ASSERT_EQUALS(oil.intervals.size(), 0U); - } - - // Complement of [MinKey, 3), [5, MaxKey) is - // [3, 5), [MaxKey, MaxKey]. - TEST(IndexBoundsTest, ComplementRanges) { - OrderedIntervalList oil; - oil.intervals.push_back(Interval(minKeyIntObj(3), true, false)); - oil.intervals.push_back(Interval(maxKeyIntObj(5), true, false)); - testDoubleComplement(&oil); - oil.complement(); - ASSERT_EQUALS(oil.intervals.size(), 2U); - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare( - Interval(BSON("" << 3 << "" << 5), true, false))); - - // Make the interval [MaxKey, MaxKey]. - BSONObjBuilder bob; - bob.appendMaxKey(""); - bob.appendMaxKey(""); - BSONObj maxKeyInt = bob.obj(); - - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[1].compare( - Interval(maxKeyInt, true, true))); - } - - // Complement of (MinKey, 3), (3, MaxKey) is - // [MinKey, MinKey], [3, 3], [MaxKey, MaxKey]. - TEST(IndexBoundsTest, ComplementRanges2) { - OrderedIntervalList oil; - oil.intervals.push_back(Interval(minKeyIntObj(3), false, false)); - oil.intervals.push_back(Interval(maxKeyIntObj(3), false, false)); - testDoubleComplement(&oil); - oil.complement(); - ASSERT_EQUALS(oil.intervals.size(), 3U); - - // First interval is [MinKey, MinKey] - BSONObjBuilder minBob; - minBob.appendMinKey(""); - minBob.appendMinKey(""); - BSONObj minObj = minBob.obj(); - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare( - Interval(minObj, true, true))); - - // Second is [3, 3] - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[1].compare( - Interval(BSON("" << 3 << "" << 3), true, true))); - - // Third is [MaxKey, MaxKey] - BSONObjBuilder maxBob; - maxBob.appendMaxKey(""); - maxBob.appendMaxKey(""); - BSONObj maxObj = maxBob.obj(); - ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[2].compare( - Interval(maxObj, true, true))); - } - - // - // Iteration over - // - - TEST(IndexBoundsCheckerTest, StartKey) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); - - IndexSeekPoint seekPoint; - it.getStartSeekPoint(&seekPoint); - - ASSERT_EQUALS(seekPoint.keySuffix[0]->numberInt(), 7); - ASSERT_EQUALS(seekPoint.suffixInclusive[0], true); - ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); - ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); - } - - TEST(IndexBoundsCheckerTest, CheckEnd) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 7 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // Second field moves past the end, but we're not done, since there's still an interval in - // the previous field that the key hasn't advanced to. - state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT(seekPoint.prefixExclusive); - - // The next index key is in the second interval for 'foo' and there is a valid interval for - // 'bar'. - state = it.checkKey(BSON("" << 22 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // The next index key is very close to the end of the open interval for foo, and it's past - // the interval for 'bar'. Since the interval for foo is open, we are asked to move - // forward, since we possibly could. - state = it.checkKey(BSON("" << 29.9 << "" << 5), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT(seekPoint.prefixExclusive); - } - - TEST(IndexBoundsCheckerTest, MoveIntervalForwardToNextInterval) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 7 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // "foo" moves between two intervals. - state = it.checkKey(BSON("" << 20.5 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 0); - // Should be told to move exactly to the next interval's beginning. - ASSERT_EQUALS(seekPoint.prefixExclusive, false); - ASSERT_EQUALS(seekPoint.keySuffix[0]->numberInt(), 21); - ASSERT_EQUALS(seekPoint.suffixInclusive[0], true); - ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); - ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); - } +// +// Validation +// + +TEST(IndexBoundsTest, ValidBasic) { + OrderedIntervalList list("foo"); + list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + IndexBounds bounds; + bounds.fields.push_back(list); + + // Go forwards with data indexed forwards. + ASSERT(bounds.isValidFor(BSON("foo" << 1), 1)); + // Go backwards with data indexed backwards. + ASSERT(bounds.isValidFor(BSON("foo" << -1), -1)); + // Bounds are not oriented along the direction of traversal. + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), -1)); + + // Bounds must match the index exactly. + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1 << "bar" << 1), 1)); + ASSERT_FALSE(bounds.isValidFor(BSON("bar" << 1), 1)); +} + +TEST(IndexBoundsTest, ValidTwoFields) { + OrderedIntervalList list("foo"); + list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + IndexBounds bounds; + bounds.fields.push_back(list); + + // Let's add another field + OrderedIntervalList otherList("bar"); + otherList.intervals.push_back(Interval(BSON("" << 0 << "" << 3), true, true)); + bounds.fields.push_back(otherList); + + // These are OK. + ASSERT(bounds.isValidFor(BSON("foo" << 1 << "bar" << 1), 1)); + ASSERT(bounds.isValidFor(BSON("foo" << -1 << "bar" << -1), -1)); + + // Direction(s) don't match. + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << -1 << "bar" << 1), -1)); + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1 << "bar" << -1), -1)); + + // Index doesn't match. + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1)); + ASSERT_FALSE(bounds.isValidFor(BSON("bar" << 1 << "foo" << 1), 1)); +} + +TEST(IndexBoundsTest, ValidIntervalsInOrder) { + OrderedIntervalList list("foo"); + // Whether navigated forward or backward, there's no valid ordering for these two intervals. + list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + list.intervals.push_back(Interval(BSON("" << 0 << "" << 5), true, true)); + IndexBounds bounds; + bounds.fields.push_back(list); + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1)); + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << -1), 1)); + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), -1)); + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << -1), -1)); +} + +TEST(IndexBoundsTest, ValidNoOverlappingIntervals) { + OrderedIntervalList list("foo"); + // overlapping intervals not allowed. + list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + list.intervals.push_back(Interval(BSON("" << 19 << "" << 25), true, true)); + IndexBounds bounds; + bounds.fields.push_back(list); + ASSERT_FALSE(bounds.isValidFor(BSON("foo" << 1), 1)); +} + +TEST(IndexBoundsTest, ValidOverlapOnlyWhenBothOpen) { + OrderedIntervalList list("foo"); + list.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, false)); + list.intervals.push_back(Interval(BSON("" << 20 << "" << 25), false, true)); + IndexBounds bounds; + bounds.fields.push_back(list); + ASSERT(bounds.isValidFor(BSON("foo" << 1), 1)); +} + +// +// Tests for OrderedIntervalList::complement() +// - TEST(IndexBoundsCheckerTest, MoveIntervalForwardManyIntervals) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false)); - fooList.intervals.push_back(Interval(BSON("" << 31 << "" << 40), true, false)); - fooList.intervals.push_back(Interval(BSON("" << 41 << "" << 50), true, false)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - IndexBoundsChecker it(&bounds, BSON("foo" << 1), 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 7), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); +/** + * Get a BSONObj which represents the interval from + * MinKey to 'end'. + */ +BSONObj minKeyIntObj(int end) { + BSONObjBuilder bob; + bob.appendMinKey(""); + bob.appendNumber("", end); + return bob.obj(); +} - // "foo" moves forward a few intervals. - state = it.checkKey(BSON("" << 42), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - } +/** + * Get a BSONObj which represents the interval from + * 'start' to MaxKey. + */ +BSONObj maxKeyIntObj(int start) { + BSONObjBuilder bob; + bob.appendNumber("", start); + bob.appendMaxKey(""); + return bob.obj(); +} - TEST(IndexBoundsCheckerTest, SimpleCheckKey) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, true)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 7 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // The rightmost key is past the range. We should be told to move past the key before the - // one whose interval we exhausted. - state = it.checkKey(BSON("" << 7 << "" << 5.00001), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT_EQUALS(seekPoint.prefixExclusive, true); - - // Move a little forward, but note that the rightmost key isn't in the interval yet. - state = it.checkKey(BSON("" << 7.2 << "" << 0), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT_EQUALS(seekPoint.prefixExclusive, false); - ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); - ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); - - // Move to the edge of both intervals, 20,5 - state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // And a little beyond. - state = it.checkKey(BSON("" << 20 << "" << 5.1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::DONE); - } +/** + * Get a BSONObj which represents the interval + * [MinKey, MaxKey]. + */ +BSONObj allValues() { + BSONObjBuilder bob; + bob.appendMinKey(""); + bob.appendMaxKey(""); + return bob.obj(); +} - TEST(IndexBoundsCheckerTest, FirstKeyMovedIsOKSecondKeyMustMove) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 0 << "" << 9), true, true)); - fooList.intervals.push_back(Interval(BSON("" << 10 << "" << 20), true, true)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, true)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 0 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // First key moves to next interval, second key needs to be advanced. - state = it.checkKey(BSON("" << 10 << "" << -1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT_EQUALS(seekPoint.prefixExclusive, false); - ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); - ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); +/** + * Test that if we complement the OIL twice, + * we get back the original OIL. + */ +void testDoubleComplement(const OrderedIntervalList* oil) { + OrderedIntervalList clone; + for (size_t i = 0; i < oil->intervals.size(); ++i) { + clone.intervals.push_back(oil->intervals[i]); } - TEST(IndexBoundsCheckerTest, SecondIntervalMustRewind) { - OrderedIntervalList first("first"); - first.intervals.push_back(Interval(BSON("" << 25 << "" << 30), true, true)); - - OrderedIntervalList second("second"); - second.intervals.push_back(Interval(BSON("" << 0 << "" << 0), true, true)); - second.intervals.push_back(Interval(BSON("" << 9 << "" << 9), true, true)); - - IndexBounds bounds; - bounds.fields.push_back(first); - bounds.fields.push_back(second); - - BSONObj idx = BSON("first" << 1 << "second" << 1); - ASSERT(bounds.isValidFor(idx, 1)); - IndexBoundsChecker it(&bounds, idx, 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - state = it.checkKey(BSON("" << 25 << "" << 0), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - state = it.checkKey(BSON("" << 25 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT_EQUALS(seekPoint.prefixExclusive, false); - ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 9); - ASSERT_EQUALS(seekPoint.suffixInclusive[1], true); - - state = it.checkKey(BSON("" << 25 << "" << 9), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + clone.complement(); + clone.complement(); - // First key moved forward. The second key moved back to a valid state but it's behind - // the interval that the checker thought it was in. - state = it.checkKey(BSON("" << 26 << "" << 0), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + ASSERT_EQUALS(oil->intervals.size(), clone.intervals.size()); + for (size_t i = 0; i < oil->intervals.size(); ++i) { + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil->intervals[i].compare(clone.intervals[i])); } +} + +// Complement of empty is [MinKey, MaxKey] +TEST(IndexBoundsTest, ComplementEmptyOil) { + OrderedIntervalList oil; + testDoubleComplement(&oil); + oil.complement(); + ASSERT_EQUALS(oil.intervals.size(), 1U); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[0].compare(Interval(allValues(), true, true))); +} + +// Complement of [MinKey, MaxKey] is empty +TEST(IndexBoundsTest, ComplementAllValues) { + OrderedIntervalList oil; + oil.intervals.push_back(Interval(allValues(), true, true)); + testDoubleComplement(&oil); + oil.complement(); + ASSERT_EQUALS(oil.intervals.size(), 0U); +} + +// Complement of [MinKey, 3), [5, MaxKey) is +// [3, 5), [MaxKey, MaxKey]. +TEST(IndexBoundsTest, ComplementRanges) { + OrderedIntervalList oil; + oil.intervals.push_back(Interval(minKeyIntObj(3), true, false)); + oil.intervals.push_back(Interval(maxKeyIntObj(5), true, false)); + testDoubleComplement(&oil); + oil.complement(); + ASSERT_EQUALS(oil.intervals.size(), 2U); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[0].compare(Interval(BSON("" << 3 << "" << 5), true, false))); + + // Make the interval [MaxKey, MaxKey]. + BSONObjBuilder bob; + bob.appendMaxKey(""); + bob.appendMaxKey(""); + BSONObj maxKeyInt = bob.obj(); + + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[1].compare(Interval(maxKeyInt, true, true))); +} + +// Complement of (MinKey, 3), (3, MaxKey) is +// [MinKey, MinKey], [3, 3], [MaxKey, MaxKey]. +TEST(IndexBoundsTest, ComplementRanges2) { + OrderedIntervalList oil; + oil.intervals.push_back(Interval(minKeyIntObj(3), false, false)); + oil.intervals.push_back(Interval(maxKeyIntObj(3), false, false)); + testDoubleComplement(&oil); + oil.complement(); + ASSERT_EQUALS(oil.intervals.size(), 3U); + + // First interval is [MinKey, MinKey] + BSONObjBuilder minBob; + minBob.appendMinKey(""); + minBob.appendMinKey(""); + BSONObj minObj = minBob.obj(); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[0].compare(Interval(minObj, true, true))); + + // Second is [3, 3] + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[1].compare(Interval(BSON("" << 3 << "" << 3), true, true))); + + // Third is [MaxKey, MaxKey] + BSONObjBuilder maxBob; + maxBob.appendMaxKey(""); + maxBob.appendMaxKey(""); + BSONObj maxObj = maxBob.obj(); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[2].compare(Interval(maxObj, true, true))); +} + +// +// Iteration over +// + +TEST(IndexBoundsCheckerTest, StartKey) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); + + IndexSeekPoint seekPoint; + it.getStartSeekPoint(&seekPoint); + + ASSERT_EQUALS(seekPoint.keySuffix[0]->numberInt(), 7); + ASSERT_EQUALS(seekPoint.suffixInclusive[0], true); + ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); + ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); +} + +TEST(IndexBoundsCheckerTest, CheckEnd) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 7 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // Second field moves past the end, but we're not done, since there's still an interval in + // the previous field that the key hasn't advanced to. + state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT(seekPoint.prefixExclusive); + + // The next index key is in the second interval for 'foo' and there is a valid interval for + // 'bar'. + state = it.checkKey(BSON("" << 22 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // The next index key is very close to the end of the open interval for foo, and it's past + // the interval for 'bar'. Since the interval for foo is open, we are asked to move + // forward, since we possibly could. + state = it.checkKey(BSON("" << 29.9 << "" << 5), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT(seekPoint.prefixExclusive); +} + +TEST(IndexBoundsCheckerTest, MoveIntervalForwardToNextInterval) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 7 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // "foo" moves between two intervals. + state = it.checkKey(BSON("" << 20.5 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 0); + // Should be told to move exactly to the next interval's beginning. + ASSERT_EQUALS(seekPoint.prefixExclusive, false); + ASSERT_EQUALS(seekPoint.keySuffix[0]->numberInt(), 21); + ASSERT_EQUALS(seekPoint.suffixInclusive[0], true); + ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); + ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); +} + +TEST(IndexBoundsCheckerTest, MoveIntervalForwardManyIntervals) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + fooList.intervals.push_back(Interval(BSON("" << 21 << "" << 30), true, false)); + fooList.intervals.push_back(Interval(BSON("" << 31 << "" << 40), true, false)); + fooList.intervals.push_back(Interval(BSON("" << 41 << "" << 50), true, false)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + IndexBoundsChecker it(&bounds, BSON("foo" << 1), 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 7), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // "foo" moves forward a few intervals. + state = it.checkKey(BSON("" << 42), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); +} + +TEST(IndexBoundsCheckerTest, SimpleCheckKey) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 7 << "" << 20), true, true)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, true)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 7 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // The rightmost key is past the range. We should be told to move past the key before the + // one whose interval we exhausted. + state = it.checkKey(BSON("" << 7 << "" << 5.00001), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT_EQUALS(seekPoint.prefixExclusive, true); + + // Move a little forward, but note that the rightmost key isn't in the interval yet. + state = it.checkKey(BSON("" << 7.2 << "" << 0), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT_EQUALS(seekPoint.prefixExclusive, false); + ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); + ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); + + // Move to the edge of both intervals, 20,5 + state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // And a little beyond. + state = it.checkKey(BSON("" << 20 << "" << 5.1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::DONE); +} + +TEST(IndexBoundsCheckerTest, FirstKeyMovedIsOKSecondKeyMustMove) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 0 << "" << 9), true, true)); + fooList.intervals.push_back(Interval(BSON("" << 10 << "" << 20), true, true)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, true)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + IndexBoundsChecker it(&bounds, BSON("foo" << 1 << "bar" << 1), 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 0 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // First key moves to next interval, second key needs to be advanced. + state = it.checkKey(BSON("" << 10 << "" << -1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT_EQUALS(seekPoint.prefixExclusive, false); + ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0); + ASSERT_EQUALS(seekPoint.suffixInclusive[1], false); +} + +TEST(IndexBoundsCheckerTest, SecondIntervalMustRewind) { + OrderedIntervalList first("first"); + first.intervals.push_back(Interval(BSON("" << 25 << "" << 30), true, true)); + + OrderedIntervalList second("second"); + second.intervals.push_back(Interval(BSON("" << 0 << "" << 0), true, true)); + second.intervals.push_back(Interval(BSON("" << 9 << "" << 9), true, true)); + + IndexBounds bounds; + bounds.fields.push_back(first); + bounds.fields.push_back(second); + + BSONObj idx = BSON("first" << 1 << "second" << 1); + ASSERT(bounds.isValidFor(idx, 1)); + IndexBoundsChecker it(&bounds, idx, 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + state = it.checkKey(BSON("" << 25 << "" << 0), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + state = it.checkKey(BSON("" << 25 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT_EQUALS(seekPoint.prefixExclusive, false); + ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 9); + ASSERT_EQUALS(seekPoint.suffixInclusive[1], true); + + state = it.checkKey(BSON("" << 25 << "" << 9), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // First key moved forward. The second key moved back to a valid state but it's behind + // the interval that the checker thought it was in. + state = it.checkKey(BSON("" << 26 << "" << 0), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); +} + +TEST(IndexBoundsCheckerTest, SimpleCheckKeyBackwards) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 20 << "" << 7), true, true)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 5 << "" << 0), true, false)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + + BSONObj idx = BSON("foo" << -1 << "bar" << -1); + ASSERT(bounds.isValidFor(idx, 1)); + IndexBoundsChecker it(&bounds, idx, 1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // The rightmost key is past the range. We should be told to move past the key before the + // one whose interval we exhausted. + state = it.checkKey(BSON("" << 20 << "" << 0), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT_EQUALS(seekPoint.prefixExclusive, true); + + // Move a little forward, but note that the rightmost key isn't in the interval yet. + state = it.checkKey(BSON("" << 19 << "" << 6), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT_EQUALS(seekPoint.prefixExclusive, false); + ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 5); + ASSERT_EQUALS(seekPoint.suffixInclusive[1], true); + + // Move to the edge of both intervals + state = it.checkKey(BSON("" << 7 << "" << 0.01), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // And a little beyond. + state = it.checkKey(BSON("" << 7 << "" << 0), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::DONE); +} + +TEST(IndexBoundsCheckerTest, CheckEndBackwards) { + OrderedIntervalList fooList("foo"); + fooList.intervals.push_back(Interval(BSON("" << 30 << "" << 21), true, true)); + fooList.intervals.push_back(Interval(BSON("" << 20 << "" << 7), true, false)); + + OrderedIntervalList barList("bar"); + barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); + + IndexBounds bounds; + bounds.fields.push_back(fooList); + bounds.fields.push_back(barList); + + BSONObj idx = BSON("foo" << 1 << "bar" << -1); + ASSERT(bounds.isValidFor(idx, -1)); + IndexBoundsChecker it(&bounds, idx, -1); + + IndexSeekPoint seekPoint; + IndexBoundsChecker::KeyState state; + + // Start at something in our range. + state = it.checkKey(BSON("" << 30 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // Second field moves past the end, but we're not done, since there's still an interval in + // the previous field that the key hasn't advanced to. + state = it.checkKey(BSON("" << 30 << "" << 5), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT(seekPoint.prefixExclusive); + + // The next index key is in the second interval for 'foo' and there is a valid interval for + // 'bar'. + state = it.checkKey(BSON("" << 20 << "" << 1), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::VALID); + + // The next index key is very close to the end of the open interval for foo, and it's past + // the interval for 'bar'. Since the interval for foo is open, we are asked to move + // forward, since we possibly could. + state = it.checkKey(BSON("" << 7.001 << "" << 5), &seekPoint); + ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); + ASSERT_EQUALS(seekPoint.prefixLen, 1); + ASSERT(seekPoint.prefixExclusive); +} + +// +// IndexBoundsChecker::findIntervalForField +// - TEST(IndexBoundsCheckerTest, SimpleCheckKeyBackwards) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 20 << "" << 7), true, true)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 5 << "" << 0), true, false)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - - BSONObj idx = BSON("foo" << -1 << "bar" << -1); - ASSERT(bounds.isValidFor(idx, 1)); - IndexBoundsChecker it(&bounds, idx, 1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // The rightmost key is past the range. We should be told to move past the key before the - // one whose interval we exhausted. - state = it.checkKey(BSON("" << 20 << "" << 0), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT_EQUALS(seekPoint.prefixExclusive, true); - - // Move a little forward, but note that the rightmost key isn't in the interval yet. - state = it.checkKey(BSON("" << 19 << "" << 6), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT_EQUALS(seekPoint.prefixExclusive, false); - ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 5); - ASSERT_EQUALS(seekPoint.suffixInclusive[1], true); - - // Move to the edge of both intervals - state = it.checkKey(BSON("" << 7 << "" << 0.01), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // And a little beyond. - state = it.checkKey(BSON("" << 7 << "" << 0), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::DONE); - } - - TEST(IndexBoundsCheckerTest, CheckEndBackwards) { - OrderedIntervalList fooList("foo"); - fooList.intervals.push_back(Interval(BSON("" << 30 << "" << 21), true, true)); - fooList.intervals.push_back(Interval(BSON("" << 20 << "" << 7), true, false)); - - OrderedIntervalList barList("bar"); - barList.intervals.push_back(Interval(BSON("" << 0 << "" << 5), false, false)); - - IndexBounds bounds; - bounds.fields.push_back(fooList); - bounds.fields.push_back(barList); - - BSONObj idx = BSON("foo" << 1 << "bar" << -1); - ASSERT(bounds.isValidFor(idx, -1)); - IndexBoundsChecker it(&bounds, idx, -1); - - IndexSeekPoint seekPoint; - IndexBoundsChecker::KeyState state; - - // Start at something in our range. - state = it.checkKey(BSON("" << 30 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // Second field moves past the end, but we're not done, since there's still an interval in - // the previous field that the key hasn't advanced to. - state = it.checkKey(BSON("" << 30 << "" << 5), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT(seekPoint.prefixExclusive); - - // The next index key is in the second interval for 'foo' and there is a valid interval for - // 'bar'. - state = it.checkKey(BSON("" << 20 << "" << 1), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::VALID); - - // The next index key is very close to the end of the open interval for foo, and it's past - // the interval for 'bar'. Since the interval for foo is open, we are asked to move - // forward, since we possibly could. - state = it.checkKey(BSON("" << 7.001 << "" << 5), &seekPoint); - ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE); - ASSERT_EQUALS(seekPoint.prefixLen, 1); - ASSERT(seekPoint.prefixExclusive); +/** + * Returns string representation of IndexBoundsChecker::Location. + */ +std::string toString(IndexBoundsChecker::Location location) { + switch (location) { + case IndexBoundsChecker::BEHIND: + return "BEHIND"; + case IndexBoundsChecker::WITHIN: + return "WITHIN"; + case IndexBoundsChecker::AHEAD: + return "AHEAD"; } + invariant(0); +} - // - // IndexBoundsChecker::findIntervalForField - // - - /** - * Returns string representation of IndexBoundsChecker::Location. - */ - std::string toString(IndexBoundsChecker::Location location) { - switch(location) { - case IndexBoundsChecker::BEHIND: return "BEHIND"; - case IndexBoundsChecker::WITHIN: return "WITHIN"; - case IndexBoundsChecker::AHEAD: return "AHEAD"; - } - invariant(0); +/** + * Test function for findIntervalForField. + * Constructs a list of point intervals from 'points' and searches for 'key' + * using findIntervalForField(). Verifies expected location and index (if expectedLocation + * is BEHIND or WITHIN). + * 'points' is provided in BSON format: {points: [pt1, pt2, pt4, ...] + */ +void testFindIntervalForField(int key, + const BSONObj& pointsObj, + const int expectedDirection, + IndexBoundsChecker::Location expectedLocation, + size_t expectedIntervalIndex) { + // Create key BSONElement. + BSONObj keyObj = BSON("" << key); + BSONElement keyElt = keyObj.firstElement(); + + // Construct point intervals. + OrderedIntervalList oil("foo"); + BSONObjIterator i(pointsObj.getObjectField("points")); + while (i.more()) { + BSONElement e = i.next(); + int j = e.numberInt(); + oil.intervals.push_back(Interval(BSON("" << j << "" << j), true, true)); } - - /** - * Test function for findIntervalForField. - * Constructs a list of point intervals from 'points' and searches for 'key' - * using findIntervalForField(). Verifies expected location and index (if expectedLocation - * is BEHIND or WITHIN). - * 'points' is provided in BSON format: {points: [pt1, pt2, pt4, ...] - */ - void testFindIntervalForField(int key, const BSONObj& pointsObj, const int expectedDirection, - IndexBoundsChecker::Location expectedLocation, - size_t expectedIntervalIndex) { - // Create key BSONElement. - BSONObj keyObj = BSON("" << key); - BSONElement keyElt = keyObj.firstElement(); - - // Construct point intervals. - OrderedIntervalList oil("foo"); - BSONObjIterator i(pointsObj.getObjectField("points")); - while (i.more()) { - BSONElement e = i.next(); - int j = e.numberInt(); - oil.intervals.push_back(Interval(BSON("" << j << "" << j), true, true)); - } - size_t intervalIndex = 0; - IndexBoundsChecker::Location location = - IndexBoundsChecker::findIntervalForField(keyElt, oil, expectedDirection, &intervalIndex); - if (expectedLocation != location) { - mongoutils::str::stream ss; - ss << "Unexpected location from findIntervalForField: key=" << keyElt - << "; intervals=" << oil.toString() << "; direction=" << expectedDirection - << ". Expected: " << toString(expectedLocation) - << ". Actual: " << toString(location); - FAIL(ss); - } - // Check interval index if location is BEHIND or WITHIN. - if ((IndexBoundsChecker::BEHIND == expectedLocation || - IndexBoundsChecker::WITHIN == expectedLocation) && - expectedIntervalIndex != intervalIndex) { - mongoutils::str::stream ss; - ss << "Unexpected interval index from findIntervalForField: key=" << keyElt - << "; intervals=" << oil.toString() << "; direction=" << expectedDirection - << "; location= " << toString(location) - << ". Expected: " << expectedIntervalIndex - << ". Actual: " << intervalIndex; - FAIL(ss); - } + size_t intervalIndex = 0; + IndexBoundsChecker::Location location = + IndexBoundsChecker::findIntervalForField(keyElt, oil, expectedDirection, &intervalIndex); + if (expectedLocation != location) { + mongoutils::str::stream ss; + ss << "Unexpected location from findIntervalForField: key=" << keyElt + << "; intervals=" << oil.toString() << "; direction=" << expectedDirection + << ". Expected: " << toString(expectedLocation) << ". Actual: " << toString(location); + FAIL(ss); } - - TEST(IndexBoundsCheckerTest, FindIntervalForField) { - // No intervals - BSONObj pointsObj = fromjson("{points: []}"); - testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); - testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); - - // One interval - pointsObj = fromjson("{points: [5]}"); - testFindIntervalForField(4, pointsObj, 1, IndexBoundsChecker::BEHIND, 0U); - testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::WITHIN, 0U); - testFindIntervalForField(6, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); - - // One interval - reverse direction - pointsObj = fromjson("{points: [5]}"); - testFindIntervalForField(6, pointsObj, -1, IndexBoundsChecker::BEHIND, 0U); - testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::WITHIN, 0U); - testFindIntervalForField(4, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); - - // Two intervals - // Verifies off-by-one handling in upper bound of binary search. - pointsObj = fromjson("{points: [5, 7]}"); - testFindIntervalForField(4, pointsObj, 1, IndexBoundsChecker::BEHIND, 0U); - testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::WITHIN, 0U); - testFindIntervalForField(6, pointsObj, 1, IndexBoundsChecker::BEHIND, 1U); - testFindIntervalForField(7, pointsObj, 1, IndexBoundsChecker::WITHIN, 1U); - testFindIntervalForField(8, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); - - // Two intervals - reverse direction - // Verifies off-by-one handling in upper bound of binary search. - pointsObj = fromjson("{points: [7, 5]}"); - testFindIntervalForField(8, pointsObj, -1, IndexBoundsChecker::BEHIND, 0U); - testFindIntervalForField(7, pointsObj, -1, IndexBoundsChecker::WITHIN, 0U); - testFindIntervalForField(6, pointsObj, -1, IndexBoundsChecker::BEHIND, 1U); - testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::WITHIN, 1U); - testFindIntervalForField(4, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); - - // Multiple intervals - odd number of intervals. - pointsObj = fromjson("{points: [1, 3, 5, 7, 9]}"); - testFindIntervalForField(0, pointsObj, 1, IndexBoundsChecker::BEHIND, 0U); - testFindIntervalForField(1, pointsObj, 1, IndexBoundsChecker::WITHIN, 0U); - testFindIntervalForField(2, pointsObj, 1, IndexBoundsChecker::BEHIND, 1U); - testFindIntervalForField(3, pointsObj, 1, IndexBoundsChecker::WITHIN, 1U); - testFindIntervalForField(4, pointsObj, 1, IndexBoundsChecker::BEHIND, 2U); - testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::WITHIN, 2U); - testFindIntervalForField(6, pointsObj, 1, IndexBoundsChecker::BEHIND, 3U); - testFindIntervalForField(7, pointsObj, 1, IndexBoundsChecker::WITHIN, 3U); - testFindIntervalForField(8, pointsObj, 1, IndexBoundsChecker::BEHIND, 4U); - testFindIntervalForField(9, pointsObj, 1, IndexBoundsChecker::WITHIN, 4U); - testFindIntervalForField(10, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); - - // Multiple intervals - even number of intervals, reverse direction - // Interval order has to match direction. - pointsObj = fromjson("{points: [7, 5, 3, 1]}"); - testFindIntervalForField(8, pointsObj, -1, IndexBoundsChecker::BEHIND, 0U); - testFindIntervalForField(7, pointsObj, -1, IndexBoundsChecker::WITHIN, 0U); - testFindIntervalForField(6, pointsObj, -1, IndexBoundsChecker::BEHIND, 1U); - testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::WITHIN, 1U); - testFindIntervalForField(4, pointsObj, -1, IndexBoundsChecker::BEHIND, 2U); - testFindIntervalForField(3, pointsObj, -1, IndexBoundsChecker::WITHIN, 2U); - testFindIntervalForField(2, pointsObj, -1, IndexBoundsChecker::BEHIND, 3U); - testFindIntervalForField(1, pointsObj, -1, IndexBoundsChecker::WITHIN, 3U); - testFindIntervalForField(0, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); + // Check interval index if location is BEHIND or WITHIN. + if ((IndexBoundsChecker::BEHIND == expectedLocation || + IndexBoundsChecker::WITHIN == expectedLocation) && + expectedIntervalIndex != intervalIndex) { + mongoutils::str::stream ss; + ss << "Unexpected interval index from findIntervalForField: key=" << keyElt + << "; intervals=" << oil.toString() << "; direction=" << expectedDirection + << "; location= " << toString(location) << ". Expected: " << expectedIntervalIndex + << ". Actual: " << intervalIndex; + FAIL(ss); } +} + +TEST(IndexBoundsCheckerTest, FindIntervalForField) { + // No intervals + BSONObj pointsObj = fromjson("{points: []}"); + testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); + testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); + + // One interval + pointsObj = fromjson("{points: [5]}"); + testFindIntervalForField(4, pointsObj, 1, IndexBoundsChecker::BEHIND, 0U); + testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::WITHIN, 0U); + testFindIntervalForField(6, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); + + // One interval - reverse direction + pointsObj = fromjson("{points: [5]}"); + testFindIntervalForField(6, pointsObj, -1, IndexBoundsChecker::BEHIND, 0U); + testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::WITHIN, 0U); + testFindIntervalForField(4, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); + + // Two intervals + // Verifies off-by-one handling in upper bound of binary search. + pointsObj = fromjson("{points: [5, 7]}"); + testFindIntervalForField(4, pointsObj, 1, IndexBoundsChecker::BEHIND, 0U); + testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::WITHIN, 0U); + testFindIntervalForField(6, pointsObj, 1, IndexBoundsChecker::BEHIND, 1U); + testFindIntervalForField(7, pointsObj, 1, IndexBoundsChecker::WITHIN, 1U); + testFindIntervalForField(8, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); + + // Two intervals - reverse direction + // Verifies off-by-one handling in upper bound of binary search. + pointsObj = fromjson("{points: [7, 5]}"); + testFindIntervalForField(8, pointsObj, -1, IndexBoundsChecker::BEHIND, 0U); + testFindIntervalForField(7, pointsObj, -1, IndexBoundsChecker::WITHIN, 0U); + testFindIntervalForField(6, pointsObj, -1, IndexBoundsChecker::BEHIND, 1U); + testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::WITHIN, 1U); + testFindIntervalForField(4, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); + + // Multiple intervals - odd number of intervals. + pointsObj = fromjson("{points: [1, 3, 5, 7, 9]}"); + testFindIntervalForField(0, pointsObj, 1, IndexBoundsChecker::BEHIND, 0U); + testFindIntervalForField(1, pointsObj, 1, IndexBoundsChecker::WITHIN, 0U); + testFindIntervalForField(2, pointsObj, 1, IndexBoundsChecker::BEHIND, 1U); + testFindIntervalForField(3, pointsObj, 1, IndexBoundsChecker::WITHIN, 1U); + testFindIntervalForField(4, pointsObj, 1, IndexBoundsChecker::BEHIND, 2U); + testFindIntervalForField(5, pointsObj, 1, IndexBoundsChecker::WITHIN, 2U); + testFindIntervalForField(6, pointsObj, 1, IndexBoundsChecker::BEHIND, 3U); + testFindIntervalForField(7, pointsObj, 1, IndexBoundsChecker::WITHIN, 3U); + testFindIntervalForField(8, pointsObj, 1, IndexBoundsChecker::BEHIND, 4U); + testFindIntervalForField(9, pointsObj, 1, IndexBoundsChecker::WITHIN, 4U); + testFindIntervalForField(10, pointsObj, 1, IndexBoundsChecker::AHEAD, 0U); + + // Multiple intervals - even number of intervals, reverse direction + // Interval order has to match direction. + pointsObj = fromjson("{points: [7, 5, 3, 1]}"); + testFindIntervalForField(8, pointsObj, -1, IndexBoundsChecker::BEHIND, 0U); + testFindIntervalForField(7, pointsObj, -1, IndexBoundsChecker::WITHIN, 0U); + testFindIntervalForField(6, pointsObj, -1, IndexBoundsChecker::BEHIND, 1U); + testFindIntervalForField(5, pointsObj, -1, IndexBoundsChecker::WITHIN, 1U); + testFindIntervalForField(4, pointsObj, -1, IndexBoundsChecker::BEHIND, 2U); + testFindIntervalForField(3, pointsObj, -1, IndexBoundsChecker::WITHIN, 2U); + testFindIntervalForField(2, pointsObj, -1, IndexBoundsChecker::BEHIND, 3U); + testFindIntervalForField(1, pointsObj, -1, IndexBoundsChecker::WITHIN, 3U); + testFindIntervalForField(0, pointsObj, -1, IndexBoundsChecker::AHEAD, 0U); +} } // namespace |