diff options
author | Qingyang Chen <qingyang.chen@10gen.com> | 2015-06-10 13:52:38 -0400 |
---|---|---|
committer | Qingyang Chen <qingyang.chen@10gen.com> | 2015-07-14 14:16:40 -0400 |
commit | 8d34c171bb7d636c479d508937fe748377afc55a (patch) | |
tree | eaaa83dd40aee203487a79277bc9f809b5afa3c0 /src/mongo/db/matcher | |
parent | 2f631e87fc531b905605dc93f4d1a0dab26e28f9 (diff) | |
download | mongo-8d34c171bb7d636c479d508937fe748377afc55a.tar.gz |
SERVER-3518 Bit test query operators
Diffstat (limited to 'src/mongo/db/matcher')
-rw-r--r-- | src/mongo/db/matcher/expression.h | 4 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_leaf.cpp | 224 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_leaf.h | 117 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_leaf_test.cpp | 554 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_parser.cpp | 168 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_parser.h | 11 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_parser_leaf_test.cpp | 269 |
7 files changed, 1345 insertions, 2 deletions
diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h index bc2a0410839..52f026d589e 100644 --- a/src/mongo/db/matcher/expression.h +++ b/src/mongo/db/matcher/expression.h @@ -67,6 +67,10 @@ public: MOD, EXISTS, MATCH_IN, + BITS_ALL_SET, + BITS_ALL_CLEAR, + BITS_ANY_SET, + BITS_ANY_CLEAR, // Negations. NOT, diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp index f826b95ecb3..208f2f67630 100644 --- a/src/mongo/db/matcher/expression_leaf.cpp +++ b/src/mongo/db/matcher/expression_leaf.cpp @@ -661,4 +661,228 @@ void InMatchExpression::copyTo(InMatchExpression* toFillIn) const { toFillIn->init(path()); _arrayEntries.copyTo(toFillIn->_arrayEntries); } + +// ----------- + +const double BitTestMatchExpression::kLongLongMaxPlusOneAsDouble = + scalbn(1, std::numeric_limits<long long>::digits); + +Status BitTestMatchExpression::init(StringData path, std::vector<uint32_t> bitPositions) { + _bitPositions = std::move(bitPositions); + return initPath(path); +} + +Status BitTestMatchExpression::init(StringData path, uint64_t bitMask) { + for (int bit = 0; bit < 64; bit++) { + if (bitMask & (1LL << bit)) { + _bitPositions.push_back(bit); + } + } + + return initPath(path); +} + +Status BitTestMatchExpression::init(StringData path, + const char* bitMaskBinary, + uint32_t bitMaskLen) { + for (uint32_t byte = 0; byte < bitMaskLen; byte++) { + char byteAt = bitMaskBinary[byte]; + if (!byteAt) { + continue; + } + + for (int bit = 0; bit < 8; bit++) { + if (byteAt & (1 << bit)) { + _bitPositions.push_back(8 * byte + bit); + } + } + } + + return initPath(path); +} + +bool BitTestMatchExpression::needFurtherBitTests(bool isBitSet) const { + const MatchType mt = matchType(); + + return (isBitSet && (mt == BITS_ALL_SET || mt == BITS_ANY_CLEAR)) || + (!isBitSet && (mt == BITS_ALL_CLEAR || mt == BITS_ANY_SET)); +} + +bool BitTestMatchExpression::performBitTest(long long eValue) const { + const MatchType mt = matchType(); + + // Test each bit position. + for (auto bitPosition : _bitPositions) { + bool isBitSet; + if (bitPosition >= 63) { + // If position to test is longer than 64 bits, sign-extend. + isBitSet = eValue < 0; + } else { + isBitSet = eValue & (1LL << bitPosition); + } + + if (!needFurtherBitTests(isBitSet)) { + // If we can skip the rest of the tests, that means we succeeded with _ANY_ or failed + // with _ALL_. + return mt == BITS_ANY_SET || mt == BITS_ANY_CLEAR; + } + } + + // If we finished all the tests, that means we succeeded with _ALL_ or failed with _ANY_. + return mt == BITS_ALL_SET || mt == BITS_ALL_CLEAR; +} + +bool BitTestMatchExpression::performBitTest(const char* eBinary, uint32_t eBinaryLen) const { + const MatchType mt = matchType(); + + // Test each bit position. + for (auto bitPosition : _bitPositions) { + bool isBitSet; + if (bitPosition >= eBinaryLen * 8) { + // If position to test is longer than the data to test against, zero-extend. + isBitSet = false; + } else { + // Map to byte position and bit position within that byte. Note that byte positions + // start at position 0 in the char array, and bit positions start at the least + // significant bit. + int bytePosition = bitPosition / 8; + int bit = bitPosition % 8; + char byte = eBinary[bytePosition]; + + isBitSet = byte & (1 << bit); + } + + if (!needFurtherBitTests(isBitSet)) { + // If we can skip the rest fo the tests, that means we succeeded with _ANY_ or failed + // with _ALL_. + return mt == BITS_ANY_SET || mt == BITS_ANY_CLEAR; + } + } + + // If we finished all the tests, that means we succeeded with _ALL_ or failed with _ANY_. + return mt == BITS_ALL_SET || mt == BITS_ALL_CLEAR; +} + +bool BitTestMatchExpression::matchesSingleElement(const BSONElement& e) const { + // Validate 'e' is a number or a BinData. + if (!e.isNumber() && e.type() != BSONType::BinData) { + return false; + } + + if (e.type() == BSONType::BinData) { + int eBinaryLen; // Length of eBinary (in bytes). + const char* eBinary = e.binData(eBinaryLen); + return performBitTest(eBinary, eBinaryLen); + } + + invariant(e.isNumber()); + + if (e.type() == BSONType::NumberDouble) { + double eDouble = e.numberDouble(); + + // NaN doubles are rejected. + if (std::isnan(eDouble)) { + return false; + } + + // Integral doubles that are too large or small to be represented as a 64-bit signed + // integer are treated as 0. We use 'kLongLongMaxAsDouble' because if we just did + // eDouble > 2^63-1, it would be compared against 2^63. eDouble=2^63 would not get caught + // that way. + if (eDouble >= kLongLongMaxPlusOneAsDouble || + eDouble < std::numeric_limits<long long>::min()) { + return false; + } + + // This checks if e is an integral double. + if (eDouble != static_cast<double>(static_cast<long long>(eDouble))) { + return false; + } + } + + long long eValue = e.numberLong(); + return performBitTest(eValue); +} + +void BitTestMatchExpression::debugString(StringBuilder& debug, int level) const { + _debugAddSpace(debug, level); + + debug << path() << " "; + + switch (matchType()) { + case BITS_ALL_SET: + debug << "$bitsAllSet:"; + break; + case BITS_ALL_CLEAR: + debug << "$bitsAllClear:"; + break; + case BITS_ANY_SET: + debug << "$bitsAnySet:"; + break; + case BITS_ANY_CLEAR: + debug << "$bitsAnyClear:"; + break; + default: + invariant(false); + } + + debug << " ["; + for (size_t i = 0; i < _bitPositions.size(); i++) { + debug << _bitPositions[i]; + if (i != _bitPositions.size() - 1) { + debug << ", "; + } + } + debug << "]"; + + MatchExpression::TagData* td = getTag(); + if (td) { + debug << " "; + td->debugString(&debug); + } +} + +void BitTestMatchExpression::toBSON(BSONObjBuilder* out) const { + string opString = ""; + + switch (matchType()) { + case BITS_ALL_SET: + opString = "$bitsAllSet"; + break; + case BITS_ALL_CLEAR: + opString = "$bitsAllClear"; + break; + case BITS_ANY_SET: + opString = "$bitsAnySet"; + break; + case BITS_ANY_CLEAR: + opString = "$bitsAnyClear"; + break; + default: + invariant(false); + } + + BSONArrayBuilder arrBob; + for (auto bitPosition : _bitPositions) { + arrBob.append(bitPosition); + } + arrBob.doneFast(); + + out->append(path(), BSON(opString << arrBob.arr())); +} + +bool BitTestMatchExpression::equivalent(const MatchExpression* other) const { + if (matchType() != other->matchType()) { + return false; + } + + const BitTestMatchExpression* realOther = static_cast<const BitTestMatchExpression*>(other); + + std::vector<uint32_t> myBitPositions = getBitPositions(); + std::vector<uint32_t> otherBitPositions = realOther->getBitPositions(); + std::sort(myBitPositions.begin(), myBitPositions.end()); + std::sort(otherBitPositions.begin(), otherBitPositions.end()); + + return path() == realOther->path() && myBitPositions == otherBitPositions; +} } diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h index 5de55766b44..4ccb2f01102 100644 --- a/src/mongo/db/matcher/expression_leaf.h +++ b/src/mongo/db/matcher/expression_leaf.h @@ -455,4 +455,121 @@ private: BSONType _type; }; +/** + * Bit test query operators include $bitsAllSet, $bitsAllClear, $bitsAnySet, and $bitsAnyClear. + */ +class BitTestMatchExpression : public LeafMatchExpression { +public: + // Constant used in matchesSingleElement() and MatchExpressionParser::_parseBitTest. Is a + // double representation of 2^63. + static const double kLongLongMaxPlusOneAsDouble; + + BitTestMatchExpression(MatchType type) : LeafMatchExpression(type) {} + virtual ~BitTestMatchExpression() {} + + /** + * Initialize with either bit positions, a 64-bit numeric bitmask, or a char array + * bitmask. + */ + Status init(StringData path, std::vector<uint32_t> bitPositions); + Status init(StringData path, uint64_t bitMask); + Status init(StringData path, const char* bitMaskBinary, uint32_t bitMaskLen); + + virtual bool matchesSingleElement(const BSONElement& e) const; + + virtual void debugString(StringBuilder& debug, int level) const; + + virtual void toBSON(BSONObjBuilder* out) const; + + virtual bool equivalent(const MatchExpression* other) const; + + size_t numBitPositions() const { + return _bitPositions.size(); + } + + const std::vector<uint32_t>& getBitPositions() const { + return _bitPositions; + } + +protected: + /** + * Used to copy this match expression to another BitTestMatchExpression. Does not take + * ownership. + */ + void initClone(BitTestMatchExpression* clone) const { + clone->init(path(), _bitPositions); + if (getTag()) { + clone->setTag(getTag()->clone()); + } + } + +private: + /** + * Performs bit test using bit positions on 'eValue' and returns whether or not the bit test + * passes. + */ + bool performBitTest(long long eValue) const; + + /** + * Performs bit test using bit positions on 'eBinary' with length (in bytes) 'eBinaryLen' and + * returns whether or not the bit test passes. + */ + bool performBitTest(const char* eBinary, uint32_t eBinaryLen) const; + + /** + * Helper function for performBitTest(...). + * + * needFurtherBitTests() determines if the result of a bit-test ('isBitSet') is enough + * information to skip the rest of the bit tests. + **/ + bool needFurtherBitTests(bool isBitSet) const; + + // Vector of bit positions to test, with bit position 0 being the least significant bit. + std::vector<uint32_t> _bitPositions; +}; + +class BitsAllSetMatchExpression : public BitTestMatchExpression { +public: + BitsAllSetMatchExpression() : BitTestMatchExpression(BITS_ALL_SET) {} + virtual std::unique_ptr<MatchExpression> shallowClone() const { + std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression = + stdx::make_unique<BitsAllSetMatchExpression>(); + initClone(bitTestMatchExpression.get()); + return std::move(bitTestMatchExpression); + } +}; + +class BitsAllClearMatchExpression : public BitTestMatchExpression { +public: + BitsAllClearMatchExpression() : BitTestMatchExpression(BITS_ALL_CLEAR) {} + virtual std::unique_ptr<MatchExpression> shallowClone() const { + std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression = + stdx::make_unique<BitsAllClearMatchExpression>(); + initClone(bitTestMatchExpression.get()); + return std::move(bitTestMatchExpression); + } +}; + +class BitsAnySetMatchExpression : public BitTestMatchExpression { +public: + BitsAnySetMatchExpression() : BitTestMatchExpression(BITS_ANY_SET) {} + virtual std::unique_ptr<MatchExpression> shallowClone() const { + std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression = + stdx::make_unique<BitsAnySetMatchExpression>(); + initClone(bitTestMatchExpression.get()); + return std::move(bitTestMatchExpression); + } +}; + +class BitsAnyClearMatchExpression : public BitTestMatchExpression { +public: + BitsAnyClearMatchExpression() : BitTestMatchExpression(BITS_ANY_CLEAR) {} + virtual std::unique_ptr<MatchExpression> shallowClone() const { + std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression = + stdx::make_unique<BitsAnyClearMatchExpression>(); + initClone(bitTestMatchExpression.get()); + return std::move(bitTestMatchExpression); + } +}; + } // namespace mongo diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp index ff3f65efb34..efe64befcd3 100644 --- a/src/mongo/db/matcher/expression_leaf_test.cpp +++ b/src/mongo/db/matcher/expression_leaf_test.cpp @@ -1716,4 +1716,558 @@ TEST( InMatchExpression, MatchesIndexKeyArrayValue ) { "" << BSON_ARRAY( 8 << "ac" ) ), indexSpec ) ); } */ + +std::vector<uint32_t> bsonArrayToBitPositions(const BSONArray& ba) { + std::vector<uint32_t> bitPositions; + + // Convert BSONArray of bit positions to int vector + for (const auto& elt : ba) { + bitPositions.push_back(elt._numberInt()); + } + + return bitPositions; +} + +TEST(BitTestMatchExpression, DoesNotMatchOther) { + std::vector<uint32_t> bitPositions; + + BSONObj notMatch1 = fromjson("{a: {}}"); // Object + BSONObj notMatch2 = fromjson("{a: null}"); // Null + BSONObj notMatch3 = fromjson("{a: []}"); // Array + BSONObj notMatch4 = fromjson("{a: true}"); // Boolean + BSONObj notMatch5 = fromjson("{a: ''}"); // String + BSONObj notMatch6 = fromjson("{a: 5.5}"); // Non-integral Double + BSONObj notMatch7 = fromjson("{a: NaN}"); // NaN + BSONObj notMatch8 = fromjson("{a: 1e100}"); // Too-Large Double + BSONObj notMatch9 = fromjson("{a: ObjectId('000000000000000000000000')}"); // OID + BSONObj notMatch10 = fromjson("{a: Date(54)}"); // Date + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositions)); + ASSERT_OK(ballc.init("a", bitPositions)); + ASSERT_OK(banys.init("a", bitPositions)); + ASSERT_OK(banyc.init("a", bitPositions)); + ASSERT_EQ((size_t)0, balls.numBitPositions()); + ASSERT_EQ((size_t)0, ballc.numBitPositions()); + ASSERT_EQ((size_t)0, banys.numBitPositions()); + ASSERT_EQ((size_t)0, banyc.numBitPositions()); + ASSERT(!balls.matchesSingleElement(notMatch1["a"])); + ASSERT(!balls.matchesSingleElement(notMatch2["a"])); + ASSERT(!balls.matchesSingleElement(notMatch3["a"])); + ASSERT(!balls.matchesSingleElement(notMatch4["a"])); + ASSERT(!balls.matchesSingleElement(notMatch5["a"])); + ASSERT(!balls.matchesSingleElement(notMatch6["a"])); + ASSERT(!balls.matchesSingleElement(notMatch7["a"])); + ASSERT(!balls.matchesSingleElement(notMatch8["a"])); + ASSERT(!balls.matchesSingleElement(notMatch9["a"])); + ASSERT(!balls.matchesSingleElement(notMatch10["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch1["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch2["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch3["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch4["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch5["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch6["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch7["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch8["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch9["a"])); + ASSERT(!ballc.matchesSingleElement(notMatch10["a"])); + ASSERT(!banys.matchesSingleElement(notMatch1["a"])); + ASSERT(!banys.matchesSingleElement(notMatch2["a"])); + ASSERT(!banys.matchesSingleElement(notMatch3["a"])); + ASSERT(!banys.matchesSingleElement(notMatch4["a"])); + ASSERT(!banys.matchesSingleElement(notMatch5["a"])); + ASSERT(!banys.matchesSingleElement(notMatch6["a"])); + ASSERT(!banys.matchesSingleElement(notMatch7["a"])); + ASSERT(!banys.matchesSingleElement(notMatch8["a"])); + ASSERT(!banys.matchesSingleElement(notMatch9["a"])); + ASSERT(!banys.matchesSingleElement(notMatch10["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch1["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch2["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch3["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch4["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch5["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch6["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch7["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch8["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch9["a"])); + ASSERT(!banyc.matchesSingleElement(notMatch10["a"])); +} + +TEST(BitTestMatchExpression, MatchBinaryWithLongBitMask) { + long long bitMask = 54; + + BSONObj match = fromjson("{a: {$binary: 'NgAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitMask)); + ASSERT_OK(ballc.init("a", bitMask)); + ASSERT_OK(banys.init("a", bitMask)); + ASSERT_OK(banyc.init("a", bitMask)); + std::vector<uint32_t> bitPositions = balls.getBitPositions(); + ASSERT(balls.matchesSingleElement(match["a"])); + ASSERT(!ballc.matchesSingleElement(match["a"])); + ASSERT(banys.matchesSingleElement(match["a"])); + ASSERT(!banyc.matchesSingleElement(match["a"])); +} + +TEST(BitTestMatchExpression, MatchLongWithBinaryBitMask) { + const char* bitMask = "\x36\x00\x00\x00"; + + BSONObj match = fromjson("{a: 54}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitMask, 4)); + ASSERT_OK(ballc.init("a", bitMask, 4)); + ASSERT_OK(banys.init("a", bitMask, 4)); + ASSERT_OK(banyc.init("a", bitMask, 4)); + ASSERT(balls.matchesSingleElement(match["a"])); + ASSERT(!ballc.matchesSingleElement(match["a"])); + ASSERT(banys.matchesSingleElement(match["a"])); + ASSERT(!banyc.matchesSingleElement(match["a"])); +} + +TEST(BitTestMatchExpression, MatchesEmpty) { + std::vector<uint32_t> bitPositions; + + BSONObj match1 = fromjson("{a: NumberInt(54)}"); + BSONObj match2 = fromjson("{a: NumberLong(54)}"); + BSONObj match3 = fromjson("{a: 54.0}"); + BSONObj match4 = fromjson("{a: {$binary: '2AAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositions)); + ASSERT_OK(ballc.init("a", bitPositions)); + ASSERT_OK(banys.init("a", bitPositions)); + ASSERT_OK(banyc.init("a", bitPositions)); + ASSERT_EQ((size_t)0, balls.numBitPositions()); + ASSERT_EQ((size_t)0, ballc.numBitPositions()); + ASSERT_EQ((size_t)0, banys.numBitPositions()); + ASSERT_EQ((size_t)0, banyc.numBitPositions()); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(balls.matchesSingleElement(match3["a"])); + ASSERT(balls.matchesSingleElement(match4["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match3["a"])); + ASSERT(ballc.matchesSingleElement(match4["a"])); + ASSERT(!banys.matchesSingleElement(match1["a"])); + ASSERT(!banys.matchesSingleElement(match2["a"])); + ASSERT(!banys.matchesSingleElement(match3["a"])); + ASSERT(!banys.matchesSingleElement(match4["a"])); + ASSERT(!banyc.matchesSingleElement(match1["a"])); + ASSERT(!banyc.matchesSingleElement(match2["a"])); + ASSERT(!banyc.matchesSingleElement(match3["a"])); + ASSERT(!banyc.matchesSingleElement(match4["a"])); +} + +TEST(BitTestMatchExpression, MatchesInteger) { + BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5); + BSONArray bac = BSON_ARRAY(0 << 3 << 600); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: NumberInt(54)}"); + BSONObj match2 = fromjson("{a: NumberLong(54)}"); + BSONObj match3 = fromjson("{a: 54.0}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)4, balls.numBitPositions()); + ASSERT_EQ((size_t)3, ballc.numBitPositions()); + ASSERT_EQ((size_t)4, banys.numBitPositions()); + ASSERT_EQ((size_t)3, banyc.numBitPositions()); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(balls.matchesSingleElement(match3["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match3["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match3["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match3["a"])); +} + +TEST(BitTestMatchExpression, MatchesNegativeInteger) { + BSONArray bas = BSON_ARRAY(1 << 3 << 6 << 7 << 33); + BSONArray bac = BSON_ARRAY(0 << 2 << 4 << 5); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: NumberInt(-54)}"); + BSONObj match2 = fromjson("{a: NumberLong(-54)}"); + BSONObj match3 = fromjson("{a: -54.0}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)5, balls.numBitPositions()); + ASSERT_EQ((size_t)4, ballc.numBitPositions()); + ASSERT_EQ((size_t)5, banys.numBitPositions()); + ASSERT_EQ((size_t)4, banyc.numBitPositions()); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(balls.matchesSingleElement(match3["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match3["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match3["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match3["a"])); +} + +TEST(BitTestMatchExpression, MatchesIntegerWithBitMask) { + long long bitMaskSet = 54; + long long bitMaskClear = 201; + + BSONObj match1 = fromjson("{a: NumberInt(54)}"); + BSONObj match2 = fromjson("{a: NumberLong(54)}"); + BSONObj match3 = fromjson("{a: 54.0}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitMaskSet)); + ASSERT_OK(ballc.init("a", bitMaskClear)); + ASSERT_OK(banys.init("a", bitMaskSet)); + ASSERT_OK(banyc.init("a", bitMaskClear)); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(balls.matchesSingleElement(match3["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match3["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match3["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match3["a"])); +} + +TEST(BitTestMatchExpression, MatchesNegativeIntegerWithBitMask) { + long long bitMaskSet = 10; + long long bitMaskClear = 5; + + BSONObj match1 = fromjson("{a: NumberInt(-54)}"); + BSONObj match2 = fromjson("{a: NumberLong(-54)}"); + BSONObj match3 = fromjson("{a: -54.0}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitMaskSet)); + ASSERT_OK(ballc.init("a", bitMaskClear)); + ASSERT_OK(banys.init("a", bitMaskSet)); + ASSERT_OK(banyc.init("a", bitMaskClear)); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(balls.matchesSingleElement(match3["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match3["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match3["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match3["a"])); +} + +TEST(BitTestMatchExpression, DoesNotMatchInteger) { + BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5 << 6); + BSONArray bac = BSON_ARRAY(0 << 3 << 1); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: NumberInt(54)}"); + BSONObj match2 = fromjson("{a: NumberLong(54)}"); + BSONObj match3 = fromjson("{a: 54.0}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)5, balls.numBitPositions()); + ASSERT_EQ((size_t)3, ballc.numBitPositions()); + ASSERT_EQ((size_t)5, banys.numBitPositions()); + ASSERT_EQ((size_t)3, banyc.numBitPositions()); + ASSERT(!balls.matchesSingleElement(match1["a"])); + ASSERT(!balls.matchesSingleElement(match2["a"])); + ASSERT(!balls.matchesSingleElement(match3["a"])); + ASSERT(!ballc.matchesSingleElement(match1["a"])); + ASSERT(!ballc.matchesSingleElement(match2["a"])); + ASSERT(!ballc.matchesSingleElement(match3["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match3["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match3["a"])); +} + +TEST(BitTestMatchExpression, DoesNotMatchIntegerWithBitMask) { + long long bitMaskSet = 118; + long long bitMaskClear = 11; + + BSONObj match1 = fromjson("{a: NumberInt(54)}"); + BSONObj match2 = fromjson("{a: NumberLong(54)}"); + BSONObj match3 = fromjson("{a: 54.0}"); + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitMaskSet)); + ASSERT_OK(ballc.init("a", bitMaskClear)); + ASSERT_OK(banys.init("a", bitMaskSet)); + ASSERT_OK(banyc.init("a", bitMaskClear)); + ASSERT(!balls.matchesSingleElement(match1["a"])); + ASSERT(!balls.matchesSingleElement(match2["a"])); + ASSERT(!balls.matchesSingleElement(match3["a"])); + ASSERT(!ballc.matchesSingleElement(match1["a"])); + ASSERT(!ballc.matchesSingleElement(match2["a"])); + ASSERT(!ballc.matchesSingleElement(match3["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match3["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match3["a"])); +} + +TEST(BitTestMatchExpression, MatchesBinary1) { + BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5); + BSONArray bac = BSON_ARRAY(0 << 3 << 600); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: {$binary: 'NgAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + // Base64 to Binary: 00110110... + BSONObj match2 = fromjson("{a: {$binary: 'NgAjqwetkqwklEWRbWERKKJREtbq', $type: '00'}}"); + // Base64 to Binary: 00110110... + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)4, balls.numBitPositions()); + ASSERT_EQ((size_t)3, ballc.numBitPositions()); + ASSERT_EQ((size_t)4, banys.numBitPositions()); + ASSERT_EQ((size_t)3, banyc.numBitPositions()); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); +} + +TEST(BitTestMatchExpression, MatchesBinary2) { + BSONArray bas = BSON_ARRAY(21 << 22 << 8 << 9); + BSONArray bac = BSON_ARRAY(20 << 23 << 612); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + // Base64 to Binary: 00000000 00000011 01100000 + BSONObj match2 = fromjson("{a: {$binary: 'JANgqwetkqwklEWRbWERKKJREtbq', $type: '00'}}"); + // Base64 to Binary: ........ 00000011 01100000 + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)4, balls.numBitPositions()); + ASSERT_EQ((size_t)3, ballc.numBitPositions()); + ASSERT_EQ((size_t)4, banys.numBitPositions()); + ASSERT_EQ((size_t)3, banyc.numBitPositions()); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); +} + +TEST(BitTestMatchExpression, MatchesBinaryWithBitMask) { + const char* bas = "\0\x03\x60\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"; + const char* bac = "\0\xFC\x9F\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"; + + BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + // Base64 to Binary: 00000000 00000011 01100000 + BSONObj match2 = fromjson("{a: {$binary: 'JANgAwetkqwklEWRbWERKKJREtbq', $type: '00'}}"); + // Base64 to Binary: ........ 00000011 01100000 + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + ASSERT_OK(balls.init("a", bas, 21)); + ASSERT_OK(ballc.init("a", bac, 21)); + ASSERT_OK(banys.init("a", bas, 21)); + ASSERT_OK(banyc.init("a", bac, 21)); + ASSERT(balls.matchesSingleElement(match1["a"])); + ASSERT(balls.matchesSingleElement(match2["a"])); + ASSERT(ballc.matchesSingleElement(match1["a"])); + ASSERT(ballc.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); +} + +TEST(BitTestMatchExpression, DoesNotMatchBinary1) { + BSONArray bas = BSON_ARRAY(1 << 2 << 4 << 5 << 6); + BSONArray bac = BSON_ARRAY(0 << 3 << 1); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: {$binary: 'NgAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + // Base64 to Binary: 00110110... + BSONObj match2 = fromjson("{a: {$binary: 'NgAjqwetkqwklEWRbWERKKJREtbq', $type: '00'}}"); + // Base64 to Binary: 00110110... + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)5, balls.numBitPositions()); + ASSERT_EQ((size_t)3, ballc.numBitPositions()); + ASSERT_EQ((size_t)5, banys.numBitPositions()); + ASSERT_EQ((size_t)3, banyc.numBitPositions()); + ASSERT(!balls.matchesSingleElement(match1["a"])); + ASSERT(!balls.matchesSingleElement(match2["a"])); + ASSERT(!ballc.matchesSingleElement(match1["a"])); + ASSERT(!ballc.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); +} + +TEST(BitTestMatchExpression, DoesNotMatchBinary2) { + BSONArray bas = BSON_ARRAY(21 << 22 << 23 << 24 << 25); + BSONArray bac = BSON_ARRAY(20 << 23 << 21); + std::vector<uint32_t> bitPositionsSet = bsonArrayToBitPositions(bas); + std::vector<uint32_t> bitPositionsClear = bsonArrayToBitPositions(bac); + + BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + // Base64 to Binary: 00000000 00000011 01100000 + BSONObj match2 = fromjson("{a: {$binary: 'JANgqwetkqwklEWRbWERKKJREtbq', $type: '00'}}"); + // Base64 to Binary: ........ 00000011 01100000 + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + + ASSERT_OK(balls.init("a", bitPositionsSet)); + ASSERT_OK(ballc.init("a", bitPositionsClear)); + ASSERT_OK(banys.init("a", bitPositionsSet)); + ASSERT_OK(banyc.init("a", bitPositionsClear)); + ASSERT_EQ((size_t)5, balls.numBitPositions()); + ASSERT_EQ((size_t)3, ballc.numBitPositions()); + ASSERT_EQ((size_t)5, banys.numBitPositions()); + ASSERT_EQ((size_t)3, banyc.numBitPositions()); + ASSERT(!balls.matchesSingleElement(match1["a"])); + ASSERT(!balls.matchesSingleElement(match2["a"])); + ASSERT(!ballc.matchesSingleElement(match1["a"])); + ASSERT(!ballc.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); +} + +TEST(BitTestMatchExpression, DoesNotMatchBinaryWithBitMask) { + const char* bas = "\0\x03\x60\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\xFF"; + const char* bac = "\0\xFD\x9F\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\xFF"; + + BSONObj match1 = fromjson("{a: {$binary: 'AANgAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}"); + // Base64 to Binary: 00000000 00000011 01100000 + BSONObj match2 = fromjson("{a: {$binary: 'JANgAwetkqwklEWRbWERKKJREtbq', $type: '00'}}"); + // Base64 to Binary: ........ 00000011 01100000 + + BitsAllSetMatchExpression balls; + BitsAllClearMatchExpression ballc; + BitsAnySetMatchExpression banys; + BitsAnyClearMatchExpression banyc; + ASSERT_OK(balls.init("a", bas, 22)); + ASSERT_OK(ballc.init("a", bac, 22)); + ASSERT_OK(banys.init("a", bas, 22)); + ASSERT_OK(banyc.init("a", bac, 22)); + ASSERT(!balls.matchesSingleElement(match1["a"])); + ASSERT(!balls.matchesSingleElement(match2["a"])); + ASSERT(!ballc.matchesSingleElement(match1["a"])); + ASSERT(!ballc.matchesSingleElement(match2["a"])); + ASSERT(banys.matchesSingleElement(match1["a"])); + ASSERT(banys.matchesSingleElement(match2["a"])); + ASSERT(banyc.matchesSingleElement(match1["a"])); + ASSERT(banyc.matchesSingleElement(match2["a"])); +} } diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp index 46a0c8520cf..b0091234bc9 100644 --- a/src/mongo/db/matcher/expression_parser.cpp +++ b/src/mongo/db/matcher/expression_parser.cpp @@ -64,6 +64,7 @@ bool hasNode(const MatchExpression* root, MatchExpression::MatchType type) { namespace mongo { using std::string; +using stdx::make_unique; StatusWithMatchExpression MatchExpressionParser::_parseComparison(const char* name, ComparisonMatchExpression* cmp, @@ -73,9 +74,9 @@ StatusWithMatchExpression MatchExpressionParser::_parseComparison(const char* na // Non-equality comparison match expressions cannot have // a regular expression as the argument (e.g. {a: {$gt: /b/}} is illegal). if (MatchExpression::EQ != cmp->matchType() && RegEx == e.type()) { - std::stringstream ss; + mongoutils::str::stream ss; ss << "Can't have RegEx as arg to predicate over field '" << name << "'."; - return {Status(ErrorCodes::BadValue, ss.str())}; + return {Status(ErrorCodes::BadValue, ss)}; } Status s = temp->init(name, e); @@ -249,6 +250,24 @@ StatusWithMatchExpression MatchExpressionParser::_parseSubField(const BSONObj& c case BSONObj::opWITHIN: case BSONObj::opGEO_INTERSECTS: return expressionParserGeoCallback(name, x, context); + + // Handles bitwise query operators. + + case BSONObj::opBITS_ALL_SET: { + return _parseBitTest<BitsAllSetMatchExpression>(name, e); + } + + case BSONObj::opBITS_ALL_CLEAR: { + return _parseBitTest<BitsAllClearMatchExpression>(name, e); + } + + case BSONObj::opBITS_ANY_SET: { + return _parseBitTest<BitsAnySetMatchExpression>(name, e); + } + + case BSONObj::opBITS_ANY_CLEAR: { + return _parseBitTest<BitsAnyClearMatchExpression>(name, e); + } } return {Status(ErrorCodes::BadValue, @@ -789,6 +808,151 @@ StatusWithMatchExpression MatchExpressionParser::_parseAll(const char* name, return {std::move(myAnd)}; } +template <class T> +StatusWithMatchExpression MatchExpressionParser::_parseBitTest(const char* name, + const BSONElement& e) { + std::unique_ptr<BitTestMatchExpression> bitTestMatchExpression = stdx::make_unique<T>(); + + if (e.type() == BSONType::Array) { + // Array of bit positions provided as value. + auto statusWithBitPositions = _parseBitPositionsArray(e.Obj()); + if (!statusWithBitPositions.isOK()) { + return statusWithBitPositions.getStatus(); + } + + std::vector<uint32_t> bitPositions = statusWithBitPositions.getValue(); + Status s = bitTestMatchExpression->init(name, bitPositions); + if (!s.isOK()) { + return s; + } + } else if (e.isNumber()) { + // Integer bitmask provided as value. + + if (e.type() == BSONType::NumberDouble) { + double eDouble = e.numberDouble(); + + // NaN doubles are rejected. + if (std::isnan(eDouble)) { + mongoutils::str::stream ss; + ss << name << " cannot take a NaN"; + return Status(ErrorCodes::BadValue, ss); + } + + // No integral doubles that are too large to be represented as a 64 bit signed integer. + // We use 'kLongLongMaxAsDouble' because if we just did eDouble > 2^63-1, it would be + // compared against 2^63. eDouble=2^63 would not get caught that way. + if (eDouble >= BitTestMatchExpression::kLongLongMaxPlusOneAsDouble || + eDouble < std::numeric_limits<long long>::min()) { + mongoutils::str::stream ss; + ss << name << " cannot be represented as a 64-bit integer: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + // This checks if e is an integral double. + if (eDouble != static_cast<double>(static_cast<long long>(eDouble))) { + mongoutils::str::stream ss; + ss << name << " cannot have a fractional part but received: " << e; + return Status(ErrorCodes::BadValue, ss); + } + } + + long long bitMask = e.numberLong(); + + // No negatives. + if (bitMask < 0) { + mongoutils::str::stream ss; + ss << name << " cannot take a negative number: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + Status s = bitTestMatchExpression->init(name, bitMask); + if (!s.isOK()) { + return s; + } + } else if (e.type() == BSONType::BinData) { + // Binary bitmask provided as value. + + int eBinaryLen; + const char* eBinary = e.binData(eBinaryLen); + + Status s = bitTestMatchExpression->init(name, eBinary, eBinaryLen); + if (!s.isOK()) { + return s; + } + } else { + mongoutils::str::stream ss; + ss << name << " takes an Array, a number, or a BinData but received: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + return {std::move(bitTestMatchExpression)}; +} + +StatusWith<std::vector<uint32_t>> MatchExpressionParser::_parseBitPositionsArray( + const BSONObj& theArray) { + std::vector<uint32_t> bitPositions; + + // Fill temporary bit position array with integers read from the BSON array. + for (const BSONElement& e : theArray) { + if (!e.isNumber()) { + mongoutils::str::stream ss; + ss << "bit positions must be an integer but got: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + if (e.type() == BSONType::NumberDouble) { + double eDouble = e.numberDouble(); + + // NaN doubles are rejected. + if (std::isnan(eDouble)) { + mongoutils::str::stream ss; + ss << "bit positions cannot take a NaN: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + // This makes sure e does not overflow a 32-bit integer container. + if (eDouble > std::numeric_limits<int>::max() || + eDouble < std::numeric_limits<int>::min()) { + mongoutils::str::stream ss; + ss << "bit positions cannot be represented as a 32-bit signed integer: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + // This checks if e is integral. + if (eDouble != static_cast<double>(static_cast<long long>(eDouble))) { + mongoutils::str::stream ss; + ss << "bit positions must be an integer but got: " << e; + return Status(ErrorCodes::BadValue, ss); + } + } + + if (e.type() == BSONType::NumberLong) { + long long eLong = e.numberLong(); + + // This makes sure e does not overflow a 32-bit integer container. + if (eLong > std::numeric_limits<int>::max() || + eLong < std::numeric_limits<int>::min()) { + mongoutils::str::stream ss; + ss << "bit positions cannot be represented as a 32-bit signed integer: " << e; + return Status(ErrorCodes::BadValue, ss); + } + } + + int eValue = e.numberInt(); + + // No negatives. + if (eValue < 0) { + mongoutils::str::stream ss; + ss << "bit positions must be >= 0 but got: " << e; + return Status(ErrorCodes::BadValue, ss); + } + + bitPositions.push_back(eValue); + } + + return bitPositions; +} + StatusWithMatchExpression MatchExpressionParser::WhereCallback::parseWhere( const BSONElement& where) const { return {Status(ErrorCodes::NoWhereParseContext, "no context for parsing $where")}; diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h index e9bb3cf7200..fd9500801b4 100644 --- a/src/mongo/db/matcher/expression_parser.h +++ b/src/mongo/db/matcher/expression_parser.h @@ -148,6 +148,17 @@ private: StatusWithMatchExpression _parseNot(const char* name, const BSONElement& e, int level); + /** + * Parses 'e' into a BitTestMatchExpression. + */ + template <class T> + StatusWithMatchExpression _parseBitTest(const char* name, const BSONElement& e); + + /** + * Converts 'theArray', a BSONArray of integers, into a std::vector of integers. + */ + StatusWith<std::vector<uint32_t>> _parseBitPositionsArray(const BSONObj& theArray); + // The maximum allowed depth of a query tree. Just to guard against stack overflow. static const int kMaximumTreeDepth; diff --git a/src/mongo/db/matcher/expression_parser_leaf_test.cpp b/src/mongo/db/matcher/expression_parser_leaf_test.cpp index 2d1dd80cc26..e6cad775ad7 100644 --- a/src/mongo/db/matcher/expression_parser_leaf_test.cpp +++ b/src/mongo/db/matcher/expression_parser_leaf_test.cpp @@ -750,4 +750,273 @@ TEST(MatchExpressionParserLeafTest, TypeStringnameNumber) { ASSERT_TRUE(tmeNumber->matchesBSON(BSON("a" << -1LL))); ASSERT_FALSE(tmeNumber->matchesBSON(fromjson("{a: ''}"))); } + +TEST(MatchExpressionParserTest, BitTestMatchExpressionValidMask) { + const double k2Power53 = scalbn(1, 32); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << 54))).getStatus()); + ASSERT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllSet" << std::numeric_limits<long long>::max()))).getStatus()); + ASSERT_OK( + MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << k2Power53))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << k2Power53 - 1))) + .getStatus()); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << 54))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllClear" << std::numeric_limits<long long>::max()))) + .getStatus()); + ASSERT_OK( + MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << k2Power53))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << k2Power53 - 1))) + .getStatus()); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << 54))).getStatus()); + ASSERT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnySet" << std::numeric_limits<long long>::max()))).getStatus()); + ASSERT_OK( + MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << k2Power53))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << k2Power53 - 1))) + .getStatus()); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << 54))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnyClear" << std::numeric_limits<long long>::max()))) + .getStatus()); + ASSERT_OK( + MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << k2Power53))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << k2Power53 - 1))) + .getStatus()); +} + +TEST(MatchExpressionParserTest, BitTestMatchExpressionValidArray) { + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(0)))) + .getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(std::numeric_limits<int>::max())))) + .getStatus()); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(0)))) + .getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(std::numeric_limits<int>::max())))) + .getStatus()); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(0)))) + .getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(std::numeric_limits<int>::max())))) + .getStatus()); + + ASSERT_OK(MatchExpressionParser::parse(BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(0)))) + .getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(0 << 1 << 2 << 3)))).getStatus()); + ASSERT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(std::numeric_limits<int>::max())))) + .getStatus()); +} + +TEST(MatchExpressionParserTest, BitTestMatchExpressionValidBinData) { + ASSERT_OK( + MatchExpressionParser::parse( + fromjson("{a: {$bitsAllSet: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}")) + .getStatus()); + + ASSERT_OK( + MatchExpressionParser::parse( + fromjson( + "{a: {$bitsAllClear: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}")) + .getStatus()); + + ASSERT_OK( + MatchExpressionParser::parse( + fromjson("{a: {$bitsAnySet: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}")) + .getStatus()); + + ASSERT_OK( + MatchExpressionParser::parse( + fromjson( + "{a: {$bitsAnyClear: {$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}}}")) + .getStatus()); +} + +TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidMaskType) { + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: null}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: true}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: {}}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: ''}}")).getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: null}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: true}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: {}}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: ''}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson("{a: {$bitsAllClear: ObjectId('000000000000000000000000')}}")).getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: null}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: true}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: {}}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: ''}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson("{a: {$bitsAnySet: ObjectId('000000000000000000000000')}}")).getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: null}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: true}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: {}}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: ''}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson("{a: {$bitsAnyClear: ObjectId('000000000000000000000000')}}")).getStatus()); +} + +TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidMaskValue) { + const double kLongLongMaxAsDouble = scalbn(1, std::numeric_limits<long long>::digits); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: NaN}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: -54}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllSet" << std::numeric_limits<double>::max()))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllSet" << kLongLongMaxAsDouble))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: 2.5}}")).getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: NaN}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: -54}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllClear" << std::numeric_limits<double>::max()))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllClear" << kLongLongMaxAsDouble))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: 2.5}}")).getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: NaN}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: -54}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnySet" << std::numeric_limits<double>::max()))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnySet" << kLongLongMaxAsDouble))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: 2.5}}")).getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: NaN}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: -54}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnyClear" << std::numeric_limits<double>::max()))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnyClear" << kLongLongMaxAsDouble))).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: 2.5}}")).getStatus()); +} + +TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidArray) { + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [null]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [true]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: ['']}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [{}]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [[]]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [-1]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson( + "{a: {$bitsAllSet: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}")) + .getStatus()); + + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [null]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [true]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: ['']}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [{}]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [[]]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [-1]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson( + "{a: {$bitsAllClear: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}")) + .getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [null]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [true]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: ['']}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [{}]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [[]]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [-1]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson( + "{a: {$bitsAnySet: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}")) + .getStatus()); + + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [null]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [true]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: ['']}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [{}]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [[]]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [-1]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + fromjson( + "{a: {$bitsAnyClear: [{$binary: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAA', $type: '00'}]}}")) + .getStatus()); +} + +TEST(MatchExpressionParserTest, BitTestMatchExpressionInvalidArrayValue) { + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [-54]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [NaN]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAllSet: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllSet" << BSON_ARRAY(std::numeric_limits<long long>::max())))) + .getStatus()); + + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [-54]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [NaN]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAllClear: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAllClear" << BSON_ARRAY(std::numeric_limits<long long>::max())))) + .getStatus()); + + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [-54]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [NaN]}}")).getStatus()); + ASSERT_NOT_OK(MatchExpressionParser::parse(fromjson("{a: {$bitsAnySet: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnySet" << BSON_ARRAY(std::numeric_limits<long long>::max())))) + .getStatus()); + + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [-54]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [NaN]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse(fromjson("{a: {$bitsAnyClear: [2.5]}}")).getStatus()); + ASSERT_NOT_OK( + MatchExpressionParser::parse( + BSON("a" << BSON("$bitsAnyClear" << BSON_ARRAY(std::numeric_limits<long long>::max())))) + .getStatus()); +} } |