diff options
author | Eliot Horowitz <eliot@10gen.com> | 2013-05-06 11:22:54 -0400 |
---|---|---|
committer | Eliot Horowitz <eliot@10gen.com> | 2013-05-06 11:22:54 -0400 |
commit | ed3efe444510137cc45e11188e23680656e22ead (patch) | |
tree | dc1d75a66e0f7bb1112adccde2994957845a6f76 /src/mongo/db | |
parent | d6a2d8027f1cbc684d960b8f522e3ffb4043d6d2 (diff) | |
download | mongo-ed3efe444510137cc45e11188e23680656e22ead.tar.gz |
SERVER-6400: MatchExpression version of Matcher code complete.
Diffstat (limited to 'src/mongo/db')
25 files changed, 1531 insertions, 287 deletions
diff --git a/src/mongo/db/matcher.h b/src/mongo/db/matcher.h index a0a383a0004..8c4cf3ab016 100644 --- a/src/mongo/db/matcher.h +++ b/src/mongo/db/matcher.h @@ -206,13 +206,14 @@ namespace mongo { const BSONObj *getQuery() const { return &_jsobj; }; - private: /** * Generate a matcher for the provided index key format using the * provided full doc matcher. */ Matcher( const Matcher &docMatcher, const BSONObj &constrainIndexKey ); + private: + void addBasic(const BSONElement &e, int c, bool isNot) { // TODO May want to selectively ignore these element types based on op type. if ( e.type() == MinKey || e.type() == MaxKey ) diff --git a/src/mongo/db/matcher/expression.cpp b/src/mongo/db/matcher/expression.cpp index 4b9b9f020ba..e2372aa14b6 100644 --- a/src/mongo/db/matcher/expression.cpp +++ b/src/mongo/db/matcher/expression.cpp @@ -25,6 +25,11 @@ namespace mongo { + MatchExpression::MatchExpression( MatchCategory category, MatchType type ) + : _matchCategory( category ), _matchType( type ){ + } + + string MatchExpression::toString() const { StringBuilder buf; debugString( buf, 0 ); @@ -36,6 +41,11 @@ namespace mongo { debug << " "; } + void AtomicMatchExpression::debugString( StringBuilder& debug, int level ) const { + _debugAddSpace( debug, level ); + debug << "$atomic\n"; + } + } diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h index c91f44c1a33..ed4a7f5bf5b 100644 --- a/src/mongo/db/matcher/expression.h +++ b/src/mongo/db/matcher/expression.h @@ -29,9 +29,29 @@ namespace mongo { class MatchExpression { MONGO_DISALLOW_COPYING( MatchExpression ); - public: - MatchExpression(){} + enum MatchType { + // tree types + AND, OR, NOR, NOT, + + // array types + ALL, ELEM_MATCH_OBJECT, ELEM_MATCH_VALUE, SIZE, + + // leaf types + LTE, LT, EQ, GT, GTE, NE, REGEX, MOD, EXISTS, IN, NIN, + + // special types + TYPE_OPERATOR, GEO, WHERE, + + // things that maybe shouldn't even be nodes + ATOMIC + }; + + enum MatchCategory { + LEAF, ARRAY, TREE, TYPE_CATEGORY, SPECIAL + }; + + MatchExpression( MatchCategory category, MatchType type ); virtual ~MatchExpression(){} /** @@ -46,10 +66,45 @@ namespace mongo { */ virtual bool matchesSingleElement( const BSONElement& e ) const = 0; + virtual size_t numChildren() const { return 0; } + virtual const MatchExpression* getChild( size_t i ) const { return NULL; } + + MatchType matchType() const { return _matchType; } + MatchCategory matchCategory() const { return _matchCategory; } + virtual string toString() const; virtual void debugString( StringBuilder& debug, int level = 0 ) const = 0; + + virtual bool equivalent( const MatchExpression* other ) const = 0; protected: void _debugAddSpace( StringBuilder& debug, int level ) const; + + private: + MatchCategory _matchCategory; + MatchType _matchType; }; + /** + * this isn't really an expression, but a hint to other things + * not sure where to put it in the end + */ + class AtomicMatchExpression : public MatchExpression { + public: + AtomicMatchExpression() : MatchExpression( SPECIAL, ATOMIC ){} + + virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const { + return true; + } + + virtual bool matchesSingleElement( const BSONElement& e ) const { + return true; + } + + virtual void debugString( StringBuilder& debug, int level = 0 ) const; + + virtual bool equivalent( const MatchExpression* other ) const { + return other->matchType() == ATOMIC; + } + + }; } diff --git a/src/mongo/db/matcher/expression_array.cpp b/src/mongo/db/matcher/expression_array.cpp index 73be4fb4275..f58655044bf 100644 --- a/src/mongo/db/matcher/expression_array.cpp +++ b/src/mongo/db/matcher/expression_array.cpp @@ -119,6 +119,14 @@ namespace mongo { debug << _path << " $all TODO\n"; } + bool AllMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const AllMatchExpression* realOther = static_cast<const AllMatchExpression*>( other ); + return _path == realOther->_path && _arrayEntries.equivalent( realOther->_arrayEntries ); + } + // ------- bool ArrayMatchingMatchExpression::matches( const BSONObj& doc, MatchDetails* details ) const { @@ -170,6 +178,26 @@ namespace mongo { } + bool ArrayMatchingMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const ArrayMatchingMatchExpression* realOther = + static_cast<const ArrayMatchingMatchExpression*>( other ); + + if ( _path != realOther->_path ) + return false; + + if ( numChildren() != realOther->numChildren() ) + return false; + + for ( unsigned i = 0; i < numChildren(); i++ ) + if ( !getChild(i)->equivalent( realOther->getChild(i) ) ) + return false; + return true; + } + + // ------- Status ElemMatchObjectMatchExpression::init( const StringData& path, const MatchExpression* sub ) { @@ -319,6 +347,24 @@ namespace mongo { } } + bool AllElemMatchOp::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const AllElemMatchOp* realOther = static_cast<const AllElemMatchOp*>( other ); + if ( _path != realOther->_path ) + return false; + + if ( _list.size() != realOther->_list.size() ) + return false; + + for ( unsigned i = 0; i < _list.size(); i++ ) + if ( !_list[i]->equivalent( realOther->_list[i] ) ) + return false; + + return true; + } + // --------- @@ -339,6 +385,14 @@ namespace mongo { debug << _path << " $size : " << _size << "\n"; } + bool SizeMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const SizeMatchExpression* realOther = static_cast<const SizeMatchExpression*>( other ); + return _path == realOther->_path && _size == realOther->_size; + } + // ------------------ diff --git a/src/mongo/db/matcher/expression_array.h b/src/mongo/db/matcher/expression_array.h index 1d467a16ad1..1d7a2f621d5 100644 --- a/src/mongo/db/matcher/expression_array.h +++ b/src/mongo/db/matcher/expression_array.h @@ -42,6 +42,7 @@ namespace mongo { */ class AllMatchExpression : public MatchExpression { public: + AllMatchExpression() : MatchExpression( ARRAY, ALL ){} Status init( const StringData& path ); ArrayFilterEntries* getArrayFilterEntries() { return &_arrayEntries; } @@ -50,6 +51,9 @@ namespace mongo { virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + bool equivalent( const MatchExpression* other ) const; + private: bool _match( const BSONElementSet& all ) const; @@ -60,6 +64,7 @@ namespace mongo { class ArrayMatchingMatchExpression : public MatchExpression { public: + ArrayMatchingMatchExpression( MatchType matchType ) : MatchExpression( ARRAY, matchType ){} virtual ~ArrayMatchingMatchExpression(){} virtual bool matches( const BSONObj& doc, MatchDetails* details ) const; @@ -71,6 +76,8 @@ namespace mongo { virtual bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const = 0; + bool equivalent( const MatchExpression* other ) const; + protected: StringData _path; }; @@ -78,17 +85,23 @@ namespace mongo { class ElemMatchObjectMatchExpression : public ArrayMatchingMatchExpression { public: + ElemMatchObjectMatchExpression() : ArrayMatchingMatchExpression( ELEM_MATCH_OBJECT ){} Status init( const StringData& path, const MatchExpression* sub ); bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual size_t numChildren() const { return 1; } + virtual const MatchExpression* getChild( size_t i ) const { return _sub.get(); } + private: boost::scoped_ptr<const MatchExpression> _sub; }; class ElemMatchValueMatchExpression : public ArrayMatchingMatchExpression { public: + ElemMatchValueMatchExpression() : ArrayMatchingMatchExpression( ELEM_MATCH_VALUE ){} virtual ~ElemMatchValueMatchExpression(); Status init( const StringData& path ); @@ -98,6 +111,10 @@ namespace mongo { bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual size_t numChildren() const { return _subs.size(); } + virtual const MatchExpression* getChild( size_t i ) const { return _subs[i]; } + private: bool _arrayElementMatchesAll( const BSONElement& e ) const; @@ -110,6 +127,7 @@ namespace mongo { */ class AllElemMatchOp : public MatchExpression { public: + AllElemMatchOp() : MatchExpression( ARRAY, ALL ){} virtual ~AllElemMatchOp(); Status init( const StringData& path ); @@ -123,6 +141,9 @@ namespace mongo { virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + private: bool _allMatch( const BSONObj& anArray ) const; @@ -132,11 +153,15 @@ namespace mongo { class SizeMatchExpression : public ArrayMatchingMatchExpression { public: + SizeMatchExpression() : ArrayMatchingMatchExpression( SIZE ){} Status init( const StringData& path, int size ); virtual bool matchesArray( const BSONObj& anArray, MatchDetails* details ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + private: int _size; // >= 0 real, < 0, nothing will match }; diff --git a/src/mongo/db/matcher/expression_array_test.cpp b/src/mongo/db/matcher/expression_array_test.cpp index eceac5a4cde..9b2a0018bb7 100644 --- a/src/mongo/db/matcher/expression_array_test.cpp +++ b/src/mongo/db/matcher/expression_array_test.cpp @@ -183,6 +183,31 @@ namespace mongo { ASSERT( !all.matches( BSON( "a" << 4 ), NULL ) ); } + TEST( AllMatchExpression, Equivalent ) { + BSONObj operand = BSON_ARRAY( 5 << 2 ); + + AllMatchExpression e1; + AllMatchExpression e2; + AllMatchExpression e3; + + e1.init( "a" ); + e1.getArrayFilterEntries()->addEquality( operand[0] ); + e1.getArrayFilterEntries()->addEquality( operand[1] ); + + e2.init( "a" ); + e2.getArrayFilterEntries()->addEquality( operand[0] ); + + e3.init( "b" ); + e3.getArrayFilterEntries()->addEquality( operand[0] ); + e3.getArrayFilterEntries()->addEquality( operand[1] ); + + ASSERT( e1.equivalent( &e1 ) ); + ASSERT( !e1.equivalent( &e2 ) ); + ASSERT( !e1.equivalent( &e3 ) ); + + } + + /** TEST( AllMatchExpression, MatchesIndexKey ) { BSONObj operand = BSON( "$all" << BSON_ARRAY( 5 ) ); @@ -199,8 +224,8 @@ namespace mongo { BSONObj baseOperand = BSON( "b" << 5 ); BSONObj match = BSON( "a" << BSON_ARRAY( BSON( "b" << 5.0 ) ) ); BSONObj notMatch = BSON( "a" << BSON_ARRAY( BSON( "b" << 6 ) ) ); - auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - ASSERT( eq->init( "b", ComparisonMatchExpression::EQ, baseOperand[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + ASSERT( eq->init( "b", baseOperand[ "b" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a", eq.release() ).isOK() ); ASSERT( op.matchesSingleElement( match[ "a" ] ) ); @@ -211,8 +236,8 @@ namespace mongo { BSONObj baseOperand = BSON( "1" << 5 ); BSONObj match = BSON( "a" << BSON_ARRAY( BSON_ARRAY( 's' << 5.0 ) ) ); BSONObj notMatch = BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 << 6 ) ) ); - auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - ASSERT( eq->init( "1", ComparisonMatchExpression::EQ, baseOperand[ "1" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + ASSERT( eq->init( "1", baseOperand[ "1" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a", eq.release() ).isOK() ); ASSERT( op.matchesSingleElement( match[ "a" ] ) ); @@ -228,12 +253,12 @@ namespace mongo { BSONObj notMatch3 = BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 5 << 6 ) ) ) ); BSONObj match = BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 5 << 6 ) << "c" << 7 ) ) ); - auto_ptr<ComparisonMatchExpression> eq1( new ComparisonMatchExpression() ); - ASSERT( eq1->init( "b", ComparisonMatchExpression::EQ, baseOperand1[ "b" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> eq2( new ComparisonMatchExpression() ); - ASSERT( eq2->init( "b", ComparisonMatchExpression::EQ, baseOperand2[ "b" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> eq3( new ComparisonMatchExpression() ); - ASSERT( eq3->init( "c", ComparisonMatchExpression::EQ, baseOperand3[ "c" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq1( new EqualityMatchExpression() ); + ASSERT( eq1->init( "b", baseOperand1[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq2( new EqualityMatchExpression() ); + ASSERT( eq2->init( "b", baseOperand2[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq3( new EqualityMatchExpression() ); + ASSERT( eq3->init( "c", baseOperand3[ "c" ] ).isOK() ); auto_ptr<AndMatchExpression> andOp( new AndMatchExpression() ); andOp->add( eq1.release() ); @@ -250,8 +275,8 @@ namespace mongo { TEST( ElemMatchObjectMatchExpression, MatchesNonArray ) { BSONObj baseOperand = BSON( "b" << 5 ); - auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - ASSERT( eq->init( "b", ComparisonMatchExpression::EQ, baseOperand[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + ASSERT( eq->init( "b", baseOperand[ "b" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a", eq.release() ).isOK() ); // Directly nested objects are not matched with $elemMatch. An intervening array is @@ -263,8 +288,8 @@ namespace mongo { TEST( ElemMatchObjectMatchExpression, MatchesArrayObject ) { BSONObj baseOperand = BSON( "b" << 5 ); - auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - ASSERT( eq->init( "b", ComparisonMatchExpression::EQ, baseOperand[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + ASSERT( eq->init( "b", baseOperand[ "b" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a", eq.release() ).isOK() ); ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 5 ) ) ), NULL ) ); @@ -276,8 +301,8 @@ namespace mongo { TEST( ElemMatchObjectMatchExpression, MatchesMultipleNamedValues ) { BSONObj baseOperand = BSON( "c" << 5 ); - auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - ASSERT( eq->init( "c", ComparisonMatchExpression::EQ, baseOperand[ "c" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + ASSERT( eq->init( "c", baseOperand[ "c" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a.b", eq.release() ).isOK() ); ASSERT( op.matches( BSON( "a" << @@ -297,8 +322,8 @@ namespace mongo { TEST( ElemMatchObjectMatchExpression, ElemMatchKey ) { BSONObj baseOperand = BSON( "c" << 6 ); - auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - ASSERT( eq->init( "c", ComparisonMatchExpression::EQ, baseOperand[ "c" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + ASSERT( eq->init( "c", baseOperand[ "c" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a.b", eq.release() ).isOK() ); MatchDetails details; @@ -342,8 +367,8 @@ namespace mongo { BSONObj baseOperand = BSON( "$gt" << 5 ); BSONObj match = BSON( "a" << BSON_ARRAY( 6 ) ); BSONObj notMatch = BSON( "a" << BSON_ARRAY( 4 ) ); - auto_ptr<ComparisonMatchExpression> gt( new ComparisonMatchExpression() ); - ASSERT( gt->init( "", ComparisonMatchExpression::GT, baseOperand[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt( new GTMatchExpression() ); + ASSERT( gt->init( "", baseOperand[ "$gt" ] ).isOK() ); ElemMatchValueMatchExpression op; ASSERT( op.init( "a", gt.release() ).isOK() ); ASSERT( op.matchesSingleElement( match[ "a" ] ) ); @@ -356,10 +381,10 @@ namespace mongo { BSONObj notMatch1 = BSON( "a" << BSON_ARRAY( 0 << 1 ) ); BSONObj notMatch2 = BSON( "a" << BSON_ARRAY( 10 << 11 ) ); BSONObj match = BSON( "a" << BSON_ARRAY( 0 << 5 << 11 ) ); - auto_ptr<ComparisonMatchExpression> gt( new ComparisonMatchExpression() ); - ASSERT( gt->init( "", ComparisonMatchExpression::GT, baseOperand1[ "$gt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> lt( new ComparisonMatchExpression() ); - ASSERT( lt->init( "", ComparisonMatchExpression::LT, baseOperand2[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt( new GTMatchExpression() ); + ASSERT( gt->init( "", baseOperand1[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> lt( new LTMatchExpression() ); + ASSERT( lt->init( "", baseOperand2[ "$lt" ] ).isOK() ); ElemMatchValueMatchExpression op; ASSERT( op.init( "a" ).isOK() ); @@ -373,8 +398,8 @@ namespace mongo { TEST( ElemMatchValueMatchExpression, MatchesNonArray ) { BSONObj baseOperand = BSON( "$gt" << 5 ); - auto_ptr<ComparisonMatchExpression> gt( new ComparisonMatchExpression() ); - ASSERT( gt->init( "", ComparisonMatchExpression::GT, baseOperand[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt( new GTMatchExpression() ); + ASSERT( gt->init( "", baseOperand[ "$gt" ] ).isOK() ); ElemMatchObjectMatchExpression op; ASSERT( op.init( "a", gt.release() ).isOK() ); // Directly nested objects are not matched with $elemMatch. An intervening array is @@ -385,8 +410,8 @@ namespace mongo { TEST( ElemMatchValueMatchExpression, MatchesArrayScalar ) { BSONObj baseOperand = BSON( "$gt" << 5 ); - auto_ptr<ComparisonMatchExpression> gt( new ComparisonMatchExpression() ); - ASSERT( gt->init( "", ComparisonMatchExpression::GT, baseOperand[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt( new GTMatchExpression() ); + ASSERT( gt->init( "", baseOperand[ "$gt" ] ).isOK() ); ElemMatchValueMatchExpression op; ASSERT( op.init( "a", gt.release() ).isOK() ); ASSERT( op.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) ); @@ -396,8 +421,8 @@ namespace mongo { TEST( ElemMatchValueMatchExpression, MatchesMultipleNamedValues ) { BSONObj baseOperand = BSON( "$gt" << 5 ); - auto_ptr<ComparisonMatchExpression> gt( new ComparisonMatchExpression() ); - ASSERT( gt->init( "", ComparisonMatchExpression::GT, baseOperand[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt( new GTMatchExpression() ); + ASSERT( gt->init( "", baseOperand[ "$gt" ] ).isOK() ); ElemMatchValueMatchExpression op; ASSERT( op.init( "a.b", gt.release() ).isOK() ); ASSERT( op.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << BSON_ARRAY( 6 ) ) ) ), NULL ) ); @@ -409,8 +434,8 @@ namespace mongo { TEST( ElemMatchValueMatchExpression, ElemMatchKey ) { BSONObj baseOperand = BSON( "$gt" << 6 ); - auto_ptr<ComparisonMatchExpression> gt( new ComparisonMatchExpression() ); - ASSERT( gt->init( "", ComparisonMatchExpression::GT, baseOperand[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt( new GTMatchExpression() ); + ASSERT( gt->init( "", baseOperand[ "$gt" ] ).isOK() ); ElemMatchValueMatchExpression op; ASSERT( op.init( "a.b", gt.release() ).isOK() ); MatchDetails details; @@ -452,12 +477,12 @@ namespace mongo { BSONObj baseOperanda1 = BSON( "a" << 1 ); - auto_ptr<ComparisonMatchExpression> eqa1( new ComparisonMatchExpression() ); - ASSERT( eqa1->init( "a", ComparisonMatchExpression::EQ, baseOperanda1[ "a" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eqa1( new EqualityMatchExpression() ); + ASSERT( eqa1->init( "a", baseOperanda1[ "a" ] ).isOK() ); BSONObj baseOperandb1 = BSON( "b" << 1 ); - auto_ptr<ComparisonMatchExpression> eqb1( new ComparisonMatchExpression() ); - ASSERT( eqb1->init( "b", ComparisonMatchExpression::EQ, baseOperandb1[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eqb1( new EqualityMatchExpression() ); + ASSERT( eqb1->init( "b", baseOperandb1[ "b" ] ).isOK() ); auto_ptr<AndMatchExpression> and1( new AndMatchExpression() ); and1->add( eqa1.release() ); @@ -469,12 +494,12 @@ namespace mongo { // elemMatch1 = { x : { $elemMatch : { a : 1, b : 1 } } } BSONObj baseOperanda2 = BSON( "a" << 2 ); - auto_ptr<ComparisonMatchExpression> eqa2( new ComparisonMatchExpression() ); - ASSERT( eqa2->init( "a", ComparisonMatchExpression::EQ, baseOperanda2[ "a" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eqa2( new EqualityMatchExpression() ); + ASSERT( eqa2->init( "a", baseOperanda2[ "a" ] ).isOK() ); BSONObj baseOperandb2 = BSON( "b" << 2 ); - auto_ptr<ComparisonMatchExpression> eqb2( new ComparisonMatchExpression() ); - ASSERT( eqb2->init( "b", ComparisonMatchExpression::EQ, baseOperandb2[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> eqb2( new EqualityMatchExpression() ); + ASSERT( eqb2->init( "b", baseOperandb2[ "b" ] ).isOK() ); auto_ptr<AndMatchExpression> and2( new AndMatchExpression() ); and2->add( eqa2.release() ); @@ -510,12 +535,12 @@ namespace mongo { TEST( AllElemMatchOp, Matches ) { BSONObj baseOperandgt1 = BSON( "$gt" << 1 ); - auto_ptr<ComparisonMatchExpression> gt1( new ComparisonMatchExpression() ); - ASSERT( gt1->init( "", ComparisonMatchExpression::GT, baseOperandgt1[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt1( new GTMatchExpression() ); + ASSERT( gt1->init( "", baseOperandgt1[ "$gt" ] ).isOK() ); BSONObj baseOperandlt1 = BSON( "$lt" << 10 ); - auto_ptr<ComparisonMatchExpression> lt1( new ComparisonMatchExpression() ); - ASSERT( lt1->init( "", ComparisonMatchExpression::LT, baseOperandlt1[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> lt1( new LTMatchExpression() ); + ASSERT( lt1->init( "", baseOperandlt1[ "$lt" ] ).isOK() ); auto_ptr<ElemMatchValueMatchExpression> elemMatch1( new ElemMatchValueMatchExpression() ); elemMatch1->init( "x" ); @@ -523,12 +548,12 @@ namespace mongo { elemMatch1->add( lt1.release() ); BSONObj baseOperandgt2 = BSON( "$gt" << 101 ); - auto_ptr<ComparisonMatchExpression> gt2( new ComparisonMatchExpression() ); - ASSERT( gt2->init( "", ComparisonMatchExpression::GT, baseOperandgt2[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> gt2( new GTMatchExpression() ); + ASSERT( gt2->init( "", baseOperandgt2[ "$gt" ] ).isOK() ); BSONObj baseOperandlt2 = BSON( "$lt" << 110 ); - auto_ptr<ComparisonMatchExpression> lt2( new ComparisonMatchExpression() ); - ASSERT( lt2->init( "", ComparisonMatchExpression::LT, baseOperandlt2[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> lt2( new LTMatchExpression() ); + ASSERT( lt2->init( "", baseOperandlt2[ "$lt" ] ).isOK() ); auto_ptr<ElemMatchValueMatchExpression> elemMatch2( new ElemMatchValueMatchExpression() ); elemMatch2->init( "x" ); @@ -630,6 +655,20 @@ namespace mongo { ASSERT_EQUALS( "1", details.elemMatchKey() ); } + TEST( SizeMatchExpression, Equivalent ) { + SizeMatchExpression e1; + SizeMatchExpression e2; + SizeMatchExpression e3; + + e1.init( "a", 5 ); + e2.init( "a", 6 ); + e3.init( "v", 5 ); + + ASSERT( e1.equivalent( &e1 ) ); + ASSERT( !e1.equivalent( &e2 ) ); + ASSERT( !e1.equivalent( &e3 ) ); + } + /** TEST( SizeMatchExpression, MatchesIndexKey ) { BSONObj operand = BSON( "$size" << 4 ); diff --git a/src/mongo/db/matcher/expression_geo.cpp b/src/mongo/db/matcher/expression_geo.cpp new file mode 100644 index 00000000000..d038a9543ed --- /dev/null +++ b/src/mongo/db/matcher/expression_geo.cpp @@ -0,0 +1,66 @@ +// expression_geo.cpp + +/** + * Copyright (C) 2013 10gen Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "mongo/pch.h" +#include "mongo/db/matcher/expression_geo.h" + +namespace mongo { + + Status GeoMatchExpression::init( const StringData& path, const GeoQuery& query ) { + _path = path; + _query = query; + return Status::OK(); + } + + bool GeoMatchExpression::matchesSingleElement( const BSONElement& e ) const { + if ( !e.isABSONObj()) + return false; + + GeometryContainer container; + if ( !container.parseFrom( e.Obj() ) ) + return false; + + return _query.satisfiesPredicate( container ); + } + + void GeoMatchExpression::debugString( StringBuilder& debug, int level ) const { + _debugAddSpace( debug, level ); + debug << "GEO\n"; + } + + bool GeoMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const GeoMatchExpression* realOther = static_cast<const GeoMatchExpression*>( other ); + + if ( _path != realOther->_path ) + return false; + + // TODO: + // return _query == realOther->_query; + return false; + } + + LeafMatchExpression* GeoMatchExpression::shallowClone() const { + GeoMatchExpression* next = new GeoMatchExpression(); + next->init( _path, _query ); + return next; + } + +} diff --git a/src/mongo/db/matcher/expression_geo.h b/src/mongo/db/matcher/expression_geo.h new file mode 100644 index 00000000000..9808519c586 --- /dev/null +++ b/src/mongo/db/matcher/expression_geo.h @@ -0,0 +1,47 @@ +// expression_geo.h + +/** + * Copyright (C) 2013 10gen Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + + +#pragma once + +#include "mongo/db/geo/geoquery.h" +#include "mongo/db/matcher/expression.h" +#include "mongo/db/matcher/expression_leaf.h" + +namespace mongo { + + class GeoMatchExpression : public LeafMatchExpression { + public: + GeoMatchExpression() : LeafMatchExpression( GEO ){} + virtual ~GeoMatchExpression(){} + + Status init( const StringData& path, const GeoQuery& query ); + + virtual bool matchesSingleElement( const BSONElement& e ) const; + + virtual void debugString( StringBuilder& debug, int level = 0 ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + + virtual LeafMatchExpression* shallowClone() const; + + private: + GeoQuery _query; + }; + +} diff --git a/src/mongo/db/matcher/expression_geo_test.cpp b/src/mongo/db/matcher/expression_geo_test.cpp new file mode 100644 index 00000000000..66404a9aa77 --- /dev/null +++ b/src/mongo/db/matcher/expression_geo_test.cpp @@ -0,0 +1,48 @@ +// expression_geo_test.cpp + +/** + * Copyright (C) 2013 10gen Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +/** Unit tests for MatchExpression operator implementations in match_operators.{h,cpp}. */ + +#include "mongo/unittest/unittest.h" + +#include "mongo/db/jsobj.h" +#include "mongo/db/json.h" +#include "mongo/db/matcher.h" +#include "mongo/db/matcher/expression.h" +#include "mongo/db/matcher/expression_geo.h" + +namespace mongo { + + TEST( ExpressionGeoTest, Geo1 ) { + BSONObj query = fromjson("{loc:{$within:{$box:[{x: 4, y:4},[6,6]]}}}"); + + GeoQuery gq; + ASSERT( gq.parseFrom( query["loc"].Obj() ) ); + + GeoMatchExpression ge; + ASSERT( ge.init( "a", gq ).isOK() ); + + ASSERT(!ge.matches(fromjson("{a: [3,4]}"))); + ASSERT(ge.matches(fromjson("{a: [4,4]}"))); + ASSERT(ge.matches(fromjson("{a: [5,5]}"))); + ASSERT(ge.matches(fromjson("{a: [5,5.1]}"))); + ASSERT(ge.matches(fromjson("{a: {x: 5, y:5.1}}"))); + + } + +} diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp index cad5cd110f1..db78d4eaa85 100644 --- a/src/mongo/db/matcher/expression_leaf.cpp +++ b/src/mongo/db/matcher/expression_leaf.cpp @@ -75,15 +75,39 @@ namespace mongo { // ------------- - Status ComparisonMatchExpression::init( const StringData& path, Type type, const BSONElement& rhs ) { + bool ComparisonMatchExpression::equivalent( const MatchExpression* other ) const { + if ( other->matchType() != matchType() ) + return false; + const ComparisonMatchExpression* realOther = + static_cast<const ComparisonMatchExpression*>( other ); + + return + _path == realOther->_path && + _rhs.valuesEqual( realOther->_rhs ); + } + + + Status ComparisonMatchExpression::init( const StringData& path, const BSONElement& rhs ) { _path = path; - _type = type; _rhs = rhs; if ( rhs.eoo() ) { return Status( ErrorCodes::BadValue, "need a real operand" ); } - _allHaveToMatch = _type == NE; + switch ( matchType() ) { + case NE: + _allHaveToMatch = true; + break; + case LT: + case LTE: + case EQ: + case GT: + case GTE: + _allHaveToMatch = false; + break; + default: + return Status( ErrorCodes::BadValue, "bad match type for ComparisonMatchExpression" ); + } return Status::OK(); } @@ -96,20 +120,20 @@ namespace mongo { // some special cases // jstNULL and undefined are treated the same if ( e.canonicalType() + _rhs.canonicalType() == 5 ) { - return _type == EQ || _type == LTE || _type == GTE; + return matchType() == EQ || matchType() == LTE || matchType() == GTE; } return _invertForNE( false ); } if ( _rhs.type() == Array ) { - if ( _type != EQ && _type != NE ) { + if ( matchType() != EQ && matchType() != NE ) { return false; } } int x = compareElementValues( e, _rhs ); - switch ( _type ) { + switch ( matchType() ) { case LT: return x < 0; case LTE: @@ -122,12 +146,14 @@ namespace mongo { return x >= 0; case NE: return x != 0; + default: + throw 1; } throw 1; } bool ComparisonMatchExpression::_invertForNE( bool normal ) const { - if ( _type == NE ) + if ( matchType() == NE ) return !normal; return normal; } @@ -135,13 +161,14 @@ namespace mongo { void ComparisonMatchExpression::debugString( StringBuilder& debug, int level ) const { _debugAddSpace( debug, level ); debug << _path << " "; - switch ( _type ) { + switch ( matchType() ) { case LT: debug << "$lt"; break; case LTE: debug << "$lte"; break; case EQ: debug << "=="; break; case GT: debug << "$gt"; break; case GTE: debug << "$gte"; break; case NE: debug << "$ne"; break; + default: debug << " UNKNOWN - should be impossible"; break; } debug << " " << _rhs.toString( false ) << "\n"; } @@ -166,6 +193,18 @@ namespace mongo { return options; } + bool RegexMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const RegexMatchExpression* realOther = static_cast<const RegexMatchExpression*>( other ); + return + _path == realOther->_path && + _regex == realOther->_regex + && _flags == realOther->_flags; + } + + Status RegexMatchExpression::init( const StringData& path, const BSONElement& e ) { if ( e.type() != RegEx ) return Status( ErrorCodes::BadValue, "regex not a regex" ); @@ -229,6 +268,17 @@ namespace mongo { debug << _path << " mod " << _divisor << " % x == " << _remainder << "\n"; } + bool ModMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const ModMatchExpression* realOther = static_cast<const ModMatchExpression*>( other ); + return + _path == realOther->_path && + _divisor == realOther->_divisor && + _remainder == realOther->_remainder; + } + // ------------------ @@ -250,6 +300,15 @@ namespace mongo { debug << _path << " exists: " << _exists << "\n"; } + bool ExistsMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const ExistsMatchExpression* realOther = static_cast<const ExistsMatchExpression*>( other ); + return _path == realOther->_path && _exists == realOther->_exists; + } + + // ---- Status TypeMatchExpression::init( const StringData& path, int type ) { @@ -311,6 +370,15 @@ namespace mongo { } + bool TypeMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const TypeMatchExpression* realOther = static_cast<const TypeMatchExpression*>( other ); + return _path == realOther->_path && _type == realOther->_type; + } + + // -------- ArrayFilterEntries::ArrayFilterEntries(){ @@ -345,6 +413,27 @@ namespace mongo { return Status::OK(); } + bool ArrayFilterEntries::equivalent( const ArrayFilterEntries& other ) const { + if ( _hasNull != other._hasNull ) + return false; + + if ( _regexes.size() != other._regexes.size() ) + return false; + for ( unsigned i = 0; i < _regexes.size(); i++ ) + if ( !_regexes[i]->equivalent( other._regexes[i] ) ) + return false; + + return _equalities == other._equalities; + } + + void ArrayFilterEntries::copyTo( ArrayFilterEntries& toFillIn ) const { + toFillIn._hasNull = _hasNull; + toFillIn._equalities = _equalities; + for ( unsigned i = 0; i < _regexes.size(); i++ ) + toFillIn._regexes.push_back( static_cast<RegexMatchExpression*>(_regexes[i]->shallowClone()) ); + } + + // ----------- void InMatchExpression::init( const StringData& path ) { @@ -373,12 +462,35 @@ namespace mongo { debug << _path << " $in: TODO\n"; } + bool InMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + const InMatchExpression* realOther = static_cast<const InMatchExpression*>( other ); + log() << "yo: " << _path << " " << realOther->_path << std::endl; + return + _path == realOther->_path && + _arrayEntries.equivalent( realOther->_arrayEntries ); + } + + LeafMatchExpression* InMatchExpression::shallowClone() const { + InMatchExpression* next = new InMatchExpression(); + copyTo( next ); + return next; + } + + void InMatchExpression::copyTo( InMatchExpression* toFillIn ) const { + toFillIn->init( _path ); + _arrayEntries.copyTo( toFillIn->_arrayEntries ); + } + + // ---------- void NinMatchExpression::init( const StringData& path ) { _path = path; _allHaveToMatch = true; + _in.init( path ); } @@ -392,6 +504,22 @@ namespace mongo { debug << _path << " $nin: TODO\n"; } + bool NinMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + return _in.equivalent( &(static_cast<const NinMatchExpression*>(other)->_in) ); + + } + + LeafMatchExpression* NinMatchExpression::shallowClone() const { + NinMatchExpression* next = new NinMatchExpression(); + next->init( _path ); + _in.copyTo( &next->_in ); + return next; + } + + } diff --git a/src/mongo/db/matcher/expression_leaf.h b/src/mongo/db/matcher/expression_leaf.h index a0aebe7a345..30b3463fcb6 100644 --- a/src/mongo/db/matcher/expression_leaf.h +++ b/src/mongo/db/matcher/expression_leaf.h @@ -30,15 +30,20 @@ namespace mongo { class LeafMatchExpression : public MatchExpression { public: - LeafMatchExpression() { + LeafMatchExpression( MatchType matchType ) : MatchExpression( LEAF, matchType ) { _allHaveToMatch = false; } virtual ~LeafMatchExpression(){} + virtual LeafMatchExpression* shallowClone() const = 0; + virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const; virtual bool matchesSingleElement( const BSONElement& e ) const = 0; + + virtual const StringData getPath() const { return _path; } + protected: StringData _path; bool _allHaveToMatch; @@ -48,25 +53,90 @@ namespace mongo { class ComparisonMatchExpression : public LeafMatchExpression { public: - enum Type { LTE, LT, EQ, GT, GTE, NE }; + ComparisonMatchExpression( MatchType type ) : LeafMatchExpression( type ){} - Status init( const StringData& path, Type type, const BSONElement& rhs ); + Status init( const StringData& path, const BSONElement& rhs ); virtual ~ComparisonMatchExpression(){} - virtual Type getType() const { return _type; } - virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level = 0 ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + protected: bool _invertForNE( bool normal ) const; - private: - Type _type; BSONElement _rhs; }; + class EqualityMatchExpression : public ComparisonMatchExpression { + public: + EqualityMatchExpression() : ComparisonMatchExpression( EQ ){} + virtual LeafMatchExpression* shallowClone() const { + ComparisonMatchExpression* e = new EqualityMatchExpression(); + e->init( _path, _rhs ); + return e; + } + }; + + class LTEMatchExpression : public ComparisonMatchExpression { + public: + LTEMatchExpression() : ComparisonMatchExpression( LTE ){} + virtual LeafMatchExpression* shallowClone() const { + ComparisonMatchExpression* e = new LTEMatchExpression(); + e->init( _path, _rhs ); + return e; + } + + }; + + class LTMatchExpression : public ComparisonMatchExpression { + public: + LTMatchExpression() : ComparisonMatchExpression( LT ){} + virtual LeafMatchExpression* shallowClone() const { + ComparisonMatchExpression* e = new LTMatchExpression(); + e->init( _path, _rhs ); + return e; + } + + }; + + class GTMatchExpression : public ComparisonMatchExpression { + public: + GTMatchExpression() : ComparisonMatchExpression( GT ){} + virtual LeafMatchExpression* shallowClone() const { + ComparisonMatchExpression* e = new GTMatchExpression(); + e->init( _path, _rhs ); + return e; + } + + }; + + class GTEMatchExpression : public ComparisonMatchExpression { + public: + GTEMatchExpression() : ComparisonMatchExpression( GTE ){} + virtual LeafMatchExpression* shallowClone() const { + ComparisonMatchExpression* e = new GTEMatchExpression(); + e->init( _path, _rhs ); + return e; + } + + }; + + class NEMatchExpression : public ComparisonMatchExpression { + public: + NEMatchExpression() : ComparisonMatchExpression( NE ){} + virtual LeafMatchExpression* shallowClone() const { + ComparisonMatchExpression* e = new NEMatchExpression(); + e->init( _path, _rhs ); + return e; + } + + }; + + class RegexMatchExpression : public LeafMatchExpression { public: /** @@ -76,12 +146,23 @@ namespace mongo { */ static const size_t MaxPatternSize = 32764; + RegexMatchExpression() : LeafMatchExpression( REGEX ){} + Status init( const StringData& path, const StringData& regex, const StringData& options ); Status init( const StringData& path, const BSONElement& e ); + virtual LeafMatchExpression* shallowClone() const { + RegexMatchExpression* e = new RegexMatchExpression(); + e->init( _path, _regex, _flags ); + return e; + } + virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + private: std::string _regex; std::string _flags; @@ -90,11 +171,22 @@ namespace mongo { class ModMatchExpression : public LeafMatchExpression { public: + ModMatchExpression() : LeafMatchExpression( MOD ){} + Status init( const StringData& path, int divisor, int remainder ); + virtual LeafMatchExpression* shallowClone() const { + ModMatchExpression* m = new ModMatchExpression(); + m->init( _path, _divisor, _remainder ); + return m; + } + virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + private: int _divisor; int _remainder; @@ -102,17 +194,30 @@ namespace mongo { class ExistsMatchExpression : public LeafMatchExpression { public: + ExistsMatchExpression() : LeafMatchExpression( EXISTS ){} + Status init( const StringData& path, bool exists ); + virtual LeafMatchExpression* shallowClone() const { + ExistsMatchExpression* e = new ExistsMatchExpression(); + e->init( _path, _exists ); + return e; + } + virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + private: bool _exists; }; class TypeMatchExpression : public MatchExpression { public: + TypeMatchExpression() : MatchExpression( TYPE_CATEGORY, TYPE_OPERATOR ){} + Status init( const StringData& path, int type ); virtual bool matchesSingleElement( const BSONElement& e ) const; @@ -120,6 +225,8 @@ namespace mongo { virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; private: bool _matches( const StringData& path, const BSONObj& doc, MatchDetails* details = 0 ) const; @@ -152,36 +259,54 @@ namespace mongo { bool singleNull() const { return size() == 1 && _hasNull; } int size() const { return _equalities.size() + _regexes.size(); } + bool equivalent( const ArrayFilterEntries& other ) const; + + void copyTo( ArrayFilterEntries& toFillIn ) const; private: bool _hasNull; // if _equalities has a jstNULL element in it BSONElementSet _equalities; std::vector<RegexMatchExpression*> _regexes; }; - /** * query operator: $in */ class InMatchExpression : public LeafMatchExpression { public: + InMatchExpression() : LeafMatchExpression( IN ){} void init( const StringData& path ); + + virtual LeafMatchExpression* shallowClone() const; + ArrayFilterEntries* getArrayFilterEntries() { return &_arrayEntries; } virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + + void copyTo( InMatchExpression* toFillIn ) const; + private: ArrayFilterEntries _arrayEntries; }; class NinMatchExpression : public LeafMatchExpression { public: + NinMatchExpression() : LeafMatchExpression( NIN ){} void init( const StringData& path ); + + virtual LeafMatchExpression* shallowClone() const; + ArrayFilterEntries* getArrayFilterEntries() { return _in.getArrayFilterEntries(); } virtual bool matchesSingleElement( const BSONElement& e ) const; virtual void debugString( StringBuilder& debug, int level ) const; + + virtual bool equivalent( const MatchExpression* other ) const; + private: InMatchExpression _in; }; diff --git a/src/mongo/db/matcher/expression_leaf_test.cpp b/src/mongo/db/matcher/expression_leaf_test.cpp index f6db53166c9..e102f92f8c5 100644 --- a/src/mongo/db/matcher/expression_leaf_test.cpp +++ b/src/mongo/db/matcher/expression_leaf_test.cpp @@ -30,39 +30,40 @@ namespace mongo { BSONObj match = BSON( "a" << 5.0 ); BSONObj notMatch = BSON( "a" << 6 ); - ComparisonMatchExpression eq; - eq.init( "", ComparisonMatchExpression::EQ, operand["a"] ); + EqualityMatchExpression eq; + eq.init( "", operand["a"] ); ASSERT( eq.matchesSingleElement( match.firstElement() ) ); ASSERT( !eq.matchesSingleElement( notMatch.firstElement() ) ); - } + ASSERT( eq.equivalent( &eq ) ); + } TEST( EqOp, InvalidEooOperand ) { BSONObj operand; - ComparisonMatchExpression eq; - ASSERT( !eq.init( "", ComparisonMatchExpression::EQ, operand.firstElement() ).isOK() ); + EqualityMatchExpression eq; + ASSERT( !eq.init( "", operand.firstElement() ).isOK() ); } TEST( EqOp, MatchesScalar ) { BSONObj operand = BSON( "a" << 5 ); - ComparisonMatchExpression eq; - eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ); + EqualityMatchExpression eq; + eq.init( "a", operand[ "a" ] ); ASSERT( eq.matches( BSON( "a" << 5.0 ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) ); } TEST( EqOp, MatchesArrayValue ) { BSONObj operand = BSON( "a" << 5 ); - ComparisonMatchExpression eq; - eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ); + EqualityMatchExpression eq; + eq.init( "a", operand[ "a" ] ); ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 5.0 << 6 ) ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) ); } TEST( EqOp, MatchesReferencedObjectValue ) { BSONObj operand = BSON( "a.b" << 5 ); - ComparisonMatchExpression eq; - eq.init( "a.b", ComparisonMatchExpression::EQ, operand[ "a.b" ] ); + EqualityMatchExpression eq; + eq.init( "a.b", operand[ "a.b" ] ); ASSERT( eq.matches( BSON( "a" << BSON( "b" << 5 ) ), NULL ) ); ASSERT( eq.matches( BSON( "a" << BSON( "b" << BSON_ARRAY( 5 ) ) ), NULL ) ); ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( BSON( "b" << 5 ) ) ), NULL ) ); @@ -70,16 +71,16 @@ namespace mongo { TEST( EqOp, MatchesReferencedArrayValue ) { BSONObj operand = BSON( "a.0" << 5 ); - ComparisonMatchExpression eq; - eq.init( "a.0", ComparisonMatchExpression::EQ, operand[ "a.0" ] ); + EqualityMatchExpression eq; + eq.init( "a.0", operand[ "a.0" ] ); ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 5 ) ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( BSON_ARRAY( 5 ) ) ), NULL ) ); } TEST( EqOp, MatchesNull ) { BSONObj operand = BSON( "a" << BSONNULL ); - ComparisonMatchExpression eq; - eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ); + EqualityMatchExpression eq; + eq.init( "a", operand[ "a" ] ); ASSERT( eq.matches( BSONObj(), NULL ) ); ASSERT( eq.matches( BSON( "a" << BSONNULL ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) ); @@ -87,8 +88,8 @@ namespace mongo { TEST( EqOp, MatchesMinKey ) { BSONObj operand = BSON( "a" << MinKey ); - ComparisonMatchExpression eq; - eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ); + EqualityMatchExpression eq; + eq.init( "a", operand[ "a" ] ); ASSERT( eq.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) ); @@ -98,8 +99,8 @@ namespace mongo { TEST( EqOp, MatchesMaxKey ) { BSONObj operand = BSON( "a" << MaxKey ); - ComparisonMatchExpression eq; - ASSERT( eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ).isOK() ); + EqualityMatchExpression eq; + ASSERT( eq.init( "a", operand[ "a" ] ).isOK() ); ASSERT( eq.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << 4 ), NULL ) ); @@ -107,8 +108,8 @@ namespace mongo { TEST( EqOp, MatchesFullArray ) { BSONObj operand = BSON( "a" << BSON_ARRAY( 1 << 2 ) ); - ComparisonMatchExpression eq; - ASSERT( eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ).isOK() ); + EqualityMatchExpression eq; + ASSERT( eq.init( "a", operand[ "a" ] ).isOK() ); ASSERT( eq.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( 1 << 2 << 3 ) ), NULL ) ); ASSERT( !eq.matches( BSON( "a" << BSON_ARRAY( 1 ) ), NULL ) ); @@ -117,8 +118,8 @@ namespace mongo { TEST( EqOp, ElemMatchKey ) { BSONObj operand = BSON( "a" << 5 ); - ComparisonMatchExpression eq; - ASSERT( eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ).isOK() ); + EqualityMatchExpression eq; + ASSERT( eq.init( "a", operand[ "a" ] ).isOK() ); MatchDetails details; details.requestElemMatchKey(); ASSERT( !eq.matches( BSON( "a" << 4 ), &details ) ); @@ -130,11 +131,27 @@ namespace mongo { ASSERT_EQUALS( "2", details.elemMatchKey() ); } + TEST( EqOp, Equality1 ) { + EqualityMatchExpression eq1; + EqualityMatchExpression eq2; + EqualityMatchExpression eq3; + + BSONObj operand = BSON( "a" << 5 << "b" << 5 << "c" << 4 ); + + eq1.init( "a", operand["a"] ); + eq2.init( "a", operand["b"] ); + eq3.init( "c", operand["c"] ); + + ASSERT( eq1.equivalent( &eq1 ) ); + ASSERT( eq1.equivalent( &eq2 ) ); + ASSERT( !eq1.equivalent( &eq3 ) ); + } + /** TEST( EqOp, MatchesIndexKeyScalar ) { BSONObj operand = BSON( "a" << 6 ); - ComparisonMatchExpression eq; - ASSERT( eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ).isOK() ); + EqualityMatchExpression eq; + ASSERT( eq.init( "a", operand[ "a" ] ).isOK() ); IndexSpec indexSpec( BSON( "a" << 1 ) ); ASSERT( MatchMatchExpression::PartialMatchResult_True == eq.matchesIndexKey( BSON( "" << 6 ), indexSpec ) ); @@ -146,8 +163,8 @@ namespace mongo { TEST( EqOp, MatchesIndexKeyMissing ) { BSONObj operand = BSON( "a" << 6 ); - ComparisonMatchExpression eq; - ASSERT( eq.init( "a", ComparisonMatchExpression::EQ, operand[ "a" ] ).isOK() ); + EqualityMatchExpression eq; + ASSERT( eq.init( "a", operand[ "a" ] ).isOK() ); IndexSpec indexSpec( BSON( "b" << 1 ) ); ASSERT( MatchMatchExpression::PartialMatchResult_Unknown == eq.matchesIndexKey( BSON( "" << 6 ), indexSpec ) ); @@ -186,8 +203,8 @@ namespace mongo { BSONObj notMatch = BSON( "a" << 6 ); BSONObj notMatchEqual = BSON( "a" << 5 ); BSONObj notMatchWrongType = BSON( "a" << "foo" ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "", ComparisonMatchExpression::LT, operand[ "$lt" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "", operand[ "$lt" ] ).isOK() ); ASSERT( lt.matchesSingleElement( match.firstElement() ) ); ASSERT( !lt.matchesSingleElement( notMatch.firstElement() ) ); ASSERT( !lt.matchesSingleElement( notMatchEqual.firstElement() ) ); @@ -196,38 +213,38 @@ namespace mongo { TEST( LtOp, InvalidEooOperand ) { BSONObj operand; - ComparisonMatchExpression lt; - ASSERT( !lt.init( "", ComparisonMatchExpression::LT, operand.firstElement() ).isOK() ); + LTMatchExpression lt; + ASSERT( !lt.init( "", operand.firstElement() ).isOK() ); } TEST( LtOp, MatchesScalar ) { BSONObj operand = BSON( "$lt" << 5 ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "$lt" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() ); ASSERT( lt.matches( BSON( "a" << 4.5 ), NULL ) ); ASSERT( !lt.matches( BSON( "a" << 6 ), NULL ) ); } TEST( LtOp, MatchesArrayValue ) { BSONObj operand = BSON( "$lt" << 5 ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "$lt" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() ); ASSERT( lt.matches( BSON( "a" << BSON_ARRAY( 6 << 4.5 ) ), NULL ) ); ASSERT( !lt.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) ); } TEST( LtOp, MatchesWholeArray ) { BSONObj operand = BSON( "$lt" << BSON_ARRAY( 5 ) ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "$lt" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() ); // Arrays are not comparable as inequalities. ASSERT( !lt.matches( BSON( "a" << BSON_ARRAY( 4 ) ), NULL ) ); } TEST( LtOp, MatchesNull ) { BSONObj operand = BSON( "$lt" << BSONNULL ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "$lt" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() ); ASSERT( !lt.matches( BSONObj(), NULL ) ); ASSERT( !lt.matches( BSON( "a" << BSONNULL ), NULL ) ); ASSERT( !lt.matches( BSON( "a" << 4 ), NULL ) ); @@ -235,8 +252,8 @@ namespace mongo { TEST( LtOp, MatchesMinKey ) { BSONObj operand = BSON( "a" << MinKey ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "a" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "a" ] ).isOK() ); ASSERT( !lt.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( !lt.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( !lt.matches( BSON( "a" << 4 ), NULL ) ); @@ -244,8 +261,8 @@ namespace mongo { TEST( LtOp, MatchesMaxKey ) { BSONObj operand = BSON( "a" << MaxKey ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "a" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "a" ] ).isOK() ); ASSERT( !lt.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( lt.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( lt.matches( BSON( "a" << 4 ), NULL ) ); @@ -253,8 +270,8 @@ namespace mongo { TEST( LtOp, ElemMatchKey ) { BSONObj operand = BSON( "$lt" << 5 ); - ComparisonMatchExpression lt; - ASSERT( lt.init( "a", ComparisonMatchExpression::LT, operand[ "$lt" ] ).isOK() ); + LTMatchExpression lt; + ASSERT( lt.init( "a", operand[ "$lt" ] ).isOK() ); MatchDetails details; details.requestElemMatchKey(); ASSERT( !lt.matches( BSON( "a" << 6 ), &details ) ); @@ -322,8 +339,8 @@ namespace mongo { BSONObj equalMatch = BSON( "a" << 5 ); BSONObj notMatch = BSON( "a" << 6 ); BSONObj notMatchWrongType = BSON( "a" << "foo" ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "", ComparisonMatchExpression::LTE, operand[ "$lte" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "", operand[ "$lte" ] ).isOK() ); ASSERT( lte.matchesSingleElement( match.firstElement() ) ); ASSERT( lte.matchesSingleElement( equalMatch.firstElement() ) ); ASSERT( !lte.matchesSingleElement( notMatch.firstElement() ) ); @@ -332,38 +349,38 @@ namespace mongo { TEST( LteOp, InvalidEooOperand ) { BSONObj operand; - ComparisonMatchExpression lte; - ASSERT( !lte.init( "", ComparisonMatchExpression::LTE, operand.firstElement() ).isOK() ); + LTEMatchExpression lte; + ASSERT( !lte.init( "", operand.firstElement() ).isOK() ); } TEST( LteOp, MatchesScalar ) { BSONObj operand = BSON( "$lte" << 5 ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "$lte" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() ); ASSERT( lte.matches( BSON( "a" << 4.5 ), NULL ) ); ASSERT( !lte.matches( BSON( "a" << 6 ), NULL ) ); } TEST( LteOp, MatchesArrayValue ) { BSONObj operand = BSON( "$lte" << 5 ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "$lte" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() ); ASSERT( lte.matches( BSON( "a" << BSON_ARRAY( 6 << 4.5 ) ), NULL ) ); ASSERT( !lte.matches( BSON( "a" << BSON_ARRAY( 6 << 7 ) ), NULL ) ); } TEST( LteOp, MatchesWholeArray ) { BSONObj operand = BSON( "$lte" << BSON_ARRAY( 5 ) ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "$lte" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() ); // Arrays are not comparable as inequalities. ASSERT( !lte.matches( BSON( "a" << BSON_ARRAY( 4 ) ), NULL ) ); } TEST( LteOp, MatchesNull ) { BSONObj operand = BSON( "$lte" << BSONNULL ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "$lte" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() ); ASSERT( lte.matches( BSONObj(), NULL ) ); ASSERT( lte.matches( BSON( "a" << BSONNULL ), NULL ) ); ASSERT( !lte.matches( BSON( "a" << 4 ), NULL ) ); @@ -371,8 +388,8 @@ namespace mongo { TEST( LteOp, MatchesMinKey ) { BSONObj operand = BSON( "a" << MinKey ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "a" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "a" ] ).isOK() ); ASSERT( lte.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( !lte.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( !lte.matches( BSON( "a" << 4 ), NULL ) ); @@ -380,8 +397,8 @@ namespace mongo { TEST( LteOp, MatchesMaxKey ) { BSONObj operand = BSON( "a" << MaxKey ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "a" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "a" ] ).isOK() ); ASSERT( lte.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( lte.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( lte.matches( BSON( "a" << 4 ), NULL ) ); @@ -390,8 +407,8 @@ namespace mongo { TEST( LteOp, ElemMatchKey ) { BSONObj operand = BSON( "$lte" << 5 ); - ComparisonMatchExpression lte; - ASSERT( lte.init( "a", ComparisonMatchExpression::LTE, operand[ "$lte" ] ).isOK() ); + LTEMatchExpression lte; + ASSERT( lte.init( "a", operand[ "$lte" ] ).isOK() ); MatchDetails details; details.requestElemMatchKey(); ASSERT( !lte.matches( BSON( "a" << 6 ), &details ) ); @@ -470,38 +487,38 @@ namespace mongo { TEST( GtOp, InvalidEooOperand ) { BSONObj operand; - ComparisonMatchExpression gt; - ASSERT( !gt.init( "", ComparisonMatchExpression::GT, operand.firstElement() ).isOK() ); + GTMatchExpression gt; + ASSERT( !gt.init( "", operand.firstElement() ).isOK() ); } TEST( GtOp, MatchesScalar ) { BSONObj operand = BSON( "$gt" << 5 ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "$gt" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() ); ASSERT( gt.matches( BSON( "a" << 5.5 ), NULL ) ); ASSERT( !gt.matches( BSON( "a" << 4 ), NULL ) ); } TEST( GtOp, MatchesArrayValue ) { BSONObj operand = BSON( "$gt" << 5 ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "$gt" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() ); ASSERT( gt.matches( BSON( "a" << BSON_ARRAY( 3 << 5.5 ) ), NULL ) ); ASSERT( !gt.matches( BSON( "a" << BSON_ARRAY( 2 << 4 ) ), NULL ) ); } TEST( GtOp, MatchesWholeArray ) { BSONObj operand = BSON( "$gt" << BSON_ARRAY( 5 ) ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "$gt" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() ); // Arrays are not comparable as inequalities. ASSERT( !gt.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) ); } TEST( GtOp, MatchesNull ) { BSONObj operand = BSON( "$gt" << BSONNULL ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "$gt" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() ); ASSERT( !gt.matches( BSONObj(), NULL ) ); ASSERT( !gt.matches( BSON( "a" << BSONNULL ), NULL ) ); ASSERT( !gt.matches( BSON( "a" << 4 ), NULL ) ); @@ -509,8 +526,8 @@ namespace mongo { TEST( GtOp, MatchesMinKey ) { BSONObj operand = BSON( "a" << MinKey ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "a" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "a" ] ).isOK() ); ASSERT( !gt.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( gt.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( gt.matches( BSON( "a" << 4 ), NULL ) ); @@ -518,8 +535,8 @@ namespace mongo { TEST( GtOp, MatchesMaxKey ) { BSONObj operand = BSON( "a" << MaxKey ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "a" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "a" ] ).isOK() ); ASSERT( !gt.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( !gt.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( !gt.matches( BSON( "a" << 4 ), NULL ) ); @@ -527,8 +544,8 @@ namespace mongo { TEST( GtOp, ElemMatchKey ) { BSONObj operand = BSON( "$gt" << 5 ); - ComparisonMatchExpression gt; - ASSERT( gt.init( "a", ComparisonMatchExpression::GT, operand[ "$gt" ] ).isOK() ); + GTMatchExpression gt; + ASSERT( gt.init( "a", operand[ "$gt" ] ).isOK() ); MatchDetails details; details.requestElemMatchKey(); ASSERT( !gt.matches( BSON( "a" << 4 ), &details ) ); @@ -597,8 +614,8 @@ namespace mongo { BSONObj equalMatch = BSON( "a" << 5 ); BSONObj notMatch = BSON( "a" << 4 ); BSONObj notMatchWrongType = BSON( "a" << "foo" ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "", ComparisonMatchExpression::GTE, operand[ "$gte" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "", operand[ "$gte" ] ).isOK() ); ASSERT( gte.matchesSingleElement( match.firstElement() ) ); ASSERT( gte.matchesSingleElement( equalMatch.firstElement() ) ); ASSERT( !gte.matchesSingleElement( notMatch.firstElement() ) ); @@ -607,38 +624,38 @@ namespace mongo { TEST( ComparisonMatchExpression, InvalidEooOperand ) { BSONObj operand; - ComparisonMatchExpression gte; - ASSERT( !gte.init( "", ComparisonMatchExpression::GTE, operand.firstElement() ).isOK() ); + GTEMatchExpression gte; + ASSERT( !gte.init( "", operand.firstElement() ).isOK() ); } TEST( ComparisonMatchExpression, MatchesScalar ) { BSONObj operand = BSON( "$gte" << 5 ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "$gte" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() ); ASSERT( gte.matches( BSON( "a" << 5.5 ), NULL ) ); ASSERT( !gte.matches( BSON( "a" << 4 ), NULL ) ); } TEST( ComparisonMatchExpression, MatchesArrayValue ) { BSONObj operand = BSON( "$gte" << 5 ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "$gte" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() ); ASSERT( gte.matches( BSON( "a" << BSON_ARRAY( 4 << 5.5 ) ), NULL ) ); ASSERT( !gte.matches( BSON( "a" << BSON_ARRAY( 1 << 2 ) ), NULL ) ); } TEST( ComparisonMatchExpression, MatchesWholeArray ) { BSONObj operand = BSON( "$gte" << BSON_ARRAY( 5 ) ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "$gte" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() ); // Arrays are not comparable as inequalities. ASSERT( !gte.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) ); } TEST( ComparisonMatchExpression, MatchesNull ) { BSONObj operand = BSON( "$gte" << BSONNULL ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "$gte" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() ); ASSERT( gte.matches( BSONObj(), NULL ) ); ASSERT( gte.matches( BSON( "a" << BSONNULL ), NULL ) ); ASSERT( !gte.matches( BSON( "a" << 4 ), NULL ) ); @@ -646,8 +663,8 @@ namespace mongo { TEST( ComparisonMatchExpression, MatchesMinKey ) { BSONObj operand = BSON( "a" << MinKey ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "a" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "a" ] ).isOK() ); ASSERT( gte.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( gte.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( gte.matches( BSON( "a" << 4 ), NULL ) ); @@ -655,8 +672,8 @@ namespace mongo { TEST( ComparisonMatchExpression, MatchesMaxKey ) { BSONObj operand = BSON( "a" << MaxKey ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "a" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "a" ] ).isOK() ); ASSERT( gte.matches( BSON( "a" << MaxKey ), NULL ) ); ASSERT( !gte.matches( BSON( "a" << MinKey ), NULL ) ); ASSERT( !gte.matches( BSON( "a" << 4 ), NULL ) ); @@ -664,8 +681,8 @@ namespace mongo { TEST( ComparisonMatchExpression, ElemMatchKey ) { BSONObj operand = BSON( "$gte" << 5 ); - ComparisonMatchExpression gte; - ASSERT( gte.init( "a", ComparisonMatchExpression::GTE, operand[ "$gte" ] ).isOK() ); + GTEMatchExpression gte; + ASSERT( gte.init( "a", operand[ "$gte" ] ).isOK() ); MatchDetails details; details.requestElemMatchKey(); ASSERT( !gte.matches( BSON( "a" << 4 ), &details ) ); @@ -732,30 +749,30 @@ namespace mongo { BSONObj operand = BSON( "$ne" << 5 ); BSONObj match = BSON( "a" << 6 ); BSONObj notMatch = BSON( "a" << 5 ); - ComparisonMatchExpression ne; - ASSERT( ne.init( "", ComparisonMatchExpression::NE, operand[ "$ne" ] ).isOK() ); + NEMatchExpression ne; + ASSERT( ne.init( "", operand[ "$ne" ] ).isOK() ); ASSERT( ne.matchesSingleElement( match.firstElement() ) ); ASSERT( !ne.matchesSingleElement( notMatch.firstElement() ) ); } TEST( NeOp, InvalidEooOperand ) { BSONObj operand; - ComparisonMatchExpression ne; - ASSERT( !ne.init( "", ComparisonMatchExpression::NE, operand.firstElement() ).isOK() ); + NEMatchExpression ne; + ASSERT( !ne.init( "", operand.firstElement() ).isOK() ); } TEST( NeOp, MatchesScalar ) { BSONObj operand = BSON( "$ne" << 5 ); - ComparisonMatchExpression ne; - ASSERT( ne.init( "a", ComparisonMatchExpression::NE, operand[ "$ne" ] ).isOK() ); + NEMatchExpression ne; + ASSERT( ne.init( "a", operand[ "$ne" ] ).isOK() ); ASSERT( ne.matches( BSON( "a" << 4 ), NULL ) ); ASSERT( !ne.matches( BSON( "a" << 5 ), NULL ) ); } TEST( NeOp, MatchesArrayValue ) { BSONObj operand = BSON( "$ne" << 5 ); - ComparisonMatchExpression ne; - ASSERT( ne.init( "a", ComparisonMatchExpression::NE, operand[ "$ne" ] ).isOK() ); + NEMatchExpression ne; + ASSERT( ne.init( "a", operand[ "$ne" ] ).isOK() ); ASSERT( ne.matches( BSON( "a" << BSON_ARRAY( 4 << 6 ) ), NULL ) ); ASSERT( !ne.matches( BSON( "a" << BSON_ARRAY( 4 << 5 ) ), NULL ) ); ASSERT( !ne.matches( BSON( "a" << BSON_ARRAY( 5 << 5 ) ), NULL ) ); @@ -763,8 +780,8 @@ namespace mongo { TEST( NeOp, MatchesNull ) { BSONObj operand = BSON( "$ne" << BSONNULL ); - ComparisonMatchExpression ne; - ASSERT( ne.init( "a", ComparisonMatchExpression::NE, operand[ "$ne" ] ).isOK() ); + NEMatchExpression ne; + ASSERT( ne.init( "a", operand[ "$ne" ] ).isOK() ); ASSERT( ne.matches( BSON( "a" << 4 ), NULL ) ); ASSERT( !ne.matches( BSONObj(), NULL ) ); ASSERT( !ne.matches( BSON( "a" << BSONNULL ), NULL ) ); @@ -772,8 +789,8 @@ namespace mongo { TEST( NeOp, ElemMatchKey ) { BSONObj operand = BSON( "$ne" << 5 ); - ComparisonMatchExpression ne; - ASSERT( ne.init( "a", ComparisonMatchExpression::NE, operand[ "$ne" ] ).isOK() ); + NEMatchExpression ne; + ASSERT( ne.init( "a", operand[ "$ne" ] ).isOK() ); MatchDetails details; details.requestElemMatchKey(); ASSERT( !ne.matches( BSON( "a" << BSON_ARRAY( 2 << 6 << 5 ) ), &details ) ); @@ -975,6 +992,22 @@ namespace mongo { ASSERT_EQUALS( "1", details.elemMatchKey() ); } + TEST( RegexMatchExpression, Equality1 ) { + RegexMatchExpression r1; + RegexMatchExpression r2; + RegexMatchExpression r3; + RegexMatchExpression r4; + ASSERT( r1.init( "a" , "b" ,"" ).isOK() ); + ASSERT( r2.init( "a" , "b" ,"x" ).isOK() ); + ASSERT( r3.init( "a" , "c" ,"" ).isOK() ); + ASSERT( r4.init( "b" , "b" ,"" ).isOK() ); + + ASSERT( r1.equivalent( &r1 ) ); + ASSERT( !r1.equivalent( &r2 ) ); + ASSERT( !r1.equivalent( &r3 ) ); + ASSERT( !r1.equivalent( &r4 ) ); + } + /** TEST( RegexMatchExpression, MatchesIndexKeyScalar ) { RegexMatchExpression regex; @@ -1068,6 +1101,24 @@ namespace mongo { ASSERT( details.hasElemMatchKey() ); ASSERT_EQUALS( "1", details.elemMatchKey() ); } + + TEST( ModMatchExpression, Equality1 ) { + ModMatchExpression m1; + ModMatchExpression m2; + ModMatchExpression m3; + ModMatchExpression m4; + + m1.init( "a" , 1 , 2 ); + m2.init( "a" , 2 , 2 ); + m3.init( "a" , 1 , 1 ); + m4.init( "b" , 1 , 2 ); + + ASSERT( m1.equivalent( &m1 ) ); + ASSERT( !m1.equivalent( &m2 ) ); + ASSERT( !m1.equivalent( &m3 ) ); + ASSERT( !m1.equivalent( &m4 ) ); + } + /** TEST( ModMatchExpression, MatchesIndexKey ) { BSONObj operand = BSON( "$mod" << BSON_ARRAY( 2 << 1 ) ); @@ -1150,6 +1201,20 @@ namespace mongo { ASSERT( details.hasElemMatchKey() ); ASSERT_EQUALS( "1", details.elemMatchKey() ); } + + TEST( ExistsMatchExpression, Equivalent ) { + ExistsMatchExpression e1; + ExistsMatchExpression e2; + ExistsMatchExpression e3; + e1.init( "a" , false ); + e2.init( "a" , true ); + e3.init( "b" , false ); + + ASSERT( e1.equivalent( &e1 ) ); + ASSERT( !e1.equivalent( &e2 ) ); + ASSERT( !e1.equivalent( &e3 ) ); + } + /** TEST( ExistsMatchExpression, MatchesIndexKey ) { BSONObj operand = BSON( "$exists" << true ); @@ -1247,6 +1312,21 @@ namespace mongo { ASSERT( details.hasElemMatchKey() ); ASSERT_EQUALS( "1", details.elemMatchKey() ); } + + TEST( TypeMatchExpression, Equivalent ) { + TypeMatchExpression e1; + TypeMatchExpression e2; + TypeMatchExpression e3; + e1.init( "a", String ); + e2.init( "a", NumberDouble ); + e3.init( "b", String ); + + ASSERT( e1.equivalent( &e1 ) ); + ASSERT( !e1.equivalent( &e2 ) ); + ASSERT( !e1.equivalent( &e3 ) ); + } + + /** TEST( TypeMatchExpression, MatchesIndexKey ) { BSONObj operand = BSON( "$type" << 2 ); @@ -1551,6 +1631,31 @@ namespace mongo { ASSERT( !details.hasElemMatchKey() ); } + TEST( NinMatchExpression, Equivalent ) { + BSONArray operand = BSON_ARRAY( 5 << 2 ); + + NinMatchExpression e1; + NinMatchExpression e2; + NinMatchExpression e3; + + e1.init( "a" ); + e2.init( "a" ); + e3.init( "b" ); + + e1.getArrayFilterEntries()->addEquality( operand[0] ); + e1.getArrayFilterEntries()->addEquality( operand[1] ); + + e2.getArrayFilterEntries()->addEquality( operand[0] ); + + e3.getArrayFilterEntries()->addEquality( operand[0] ); + e3.getArrayFilterEntries()->addEquality( operand[1] ); + + ASSERT( e1.equivalent( &e1 ) ); + ASSERT( !e1.equivalent( &e2 ) ); + ASSERT( !e1.equivalent( &e3 ) ); + } + + /** TEST( NinMatchExpression, MatchesIndexKey ) { BSONObj operand = BSON( "$nin" << BSON_ARRAY( 5 ) ); diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp index e444866d60b..f7de6dd6f5b 100644 --- a/src/mongo/db/matcher/expression_parser.cpp +++ b/src/mongo/db/matcher/expression_parser.cpp @@ -32,24 +32,29 @@ namespace mongo { StatusWithMatchExpression MatchExpressionParser::_parseComparison( const char* name, - ComparisonMatchExpression::Type cmp, - const BSONElement& e ) { - std::auto_ptr<ComparisonMatchExpression> temp( new ComparisonMatchExpression() ); + ComparisonMatchExpression* cmp, + const BSONElement& e ) { + std::auto_ptr<ComparisonMatchExpression> temp( cmp ); - Status s = temp->init( name, cmp, e ); + Status s = temp->init( name, e ); if ( !s.isOK() ) return StatusWithMatchExpression(s); return StatusWithMatchExpression( temp.release() ); } - StatusWithMatchExpression MatchExpressionParser::_parseSubField( const char* name, - const BSONElement& e ) { + StatusWithMatchExpression MatchExpressionParser::_parseSubField( const BSONObj& context, + const char* name, + const BSONElement& e, + int position, + bool* stop ) { + + *stop = false; // TODO: these should move to getGtLtOp, or its replacement if ( mongoutils::str::equals( "$eq", e.fieldName() ) ) - return _parseComparison( name, ComparisonMatchExpression::EQ, e ); + return _parseComparison( name, new EqualityMatchExpression(), e ); if ( mongoutils::str::equals( "$not", e.fieldName() ) ) { return _parseNot( name, e ); @@ -63,17 +68,17 @@ namespace mongo { mongoutils::str::stream() << "unknown operator: " << e.fieldName() ); case BSONObj::LT: - return _parseComparison( name, ComparisonMatchExpression::LT, e ); + return _parseComparison( name, new LTMatchExpression(), e ); case BSONObj::LTE: - return _parseComparison( name, ComparisonMatchExpression::LTE, e ); + return _parseComparison( name, new LTEMatchExpression(), e ); case BSONObj::GT: - return _parseComparison( name, ComparisonMatchExpression::GT, e ); + return _parseComparison( name, new GTMatchExpression(), e ); case BSONObj::GTE: - return _parseComparison( name, ComparisonMatchExpression::GTE, e ); + return _parseComparison( name, new GTEMatchExpression(), e ); case BSONObj::NE: - return _parseComparison( name, ComparisonMatchExpression::NE, e ); + return _parseComparison( name, new NEMatchExpression(), e ); case BSONObj::Equality: - return _parseComparison( name, ComparisonMatchExpression::EQ, e ); + return _parseComparison( name, new EqualityMatchExpression(), e ); case BSONObj::opIN: { if ( e.type() != Array ) @@ -157,19 +162,30 @@ namespace mongo { case BSONObj::opOPTIONS: return StatusWithMatchExpression( ErrorCodes::BadValue, "$options has to be after a $regex" ); + case BSONObj::opREGEX: { + if ( position != 0 ) + return StatusWithMatchExpression( ErrorCodes::BadValue, "$regex has to be first" ); + + *stop = true; + return _parseRegexDocument( name, context ); + } + case BSONObj::opELEM_MATCH: return _parseElemMatch( name, e ); case BSONObj::opALL: return _parseAll( name, e ); + case BSONObj::opWITHIN: + return expressionParserGeoCallback( name, context ); + default: return StatusWithMatchExpression( ErrorCodes::BadValue, "not done" ); } } - StatusWithMatchExpression MatchExpressionParser::parse( const BSONObj& obj ) { + StatusWithMatchExpression MatchExpressionParser::_parse( const BSONObj& obj, bool topLevel ) { std::auto_ptr<AndMatchExpression> root( new AndMatchExpression() ); @@ -211,10 +227,26 @@ namespace mongo { return StatusWithMatchExpression( s ); root->add( temp.release() ); } + else if ( mongoutils::str::equals( "atomic", rest ) ) { + if ( !topLevel ) + return StatusWithMatchExpression( ErrorCodes::BadValue, + "$atomic has to be at the top level" ); + if ( e.trueValue() ) + root->add( new AtomicMatchExpression() ); + } + else if ( mongoutils::str::equals( "where", rest ) ) { + if ( !topLevel ) + return StatusWithMatchExpression( ErrorCodes::BadValue, + "$within has to be at the top level" ); + StatusWithMatchExpression s = expressionParserWhereCallback( e ); + if ( !s.isOK() ) + return s; + root->add( s.getValue() ); + } else { return StatusWithMatchExpression( ErrorCodes::BadValue, mongoutils::str::stream() - << "unkown operator: " + << "unknown top level operator: " << e.fieldName() ); } @@ -236,8 +268,8 @@ namespace mongo { continue; } - std::auto_ptr<ComparisonMatchExpression> eq( new ComparisonMatchExpression() ); - Status s = eq->init( e.fieldName(), ComparisonMatchExpression::EQ, e ); + std::auto_ptr<ComparisonMatchExpression> eq( new EqualityMatchExpression() ); + Status s = eq->init( e.fieldName(), e ); if ( !s.isOK() ) return StatusWithMatchExpression( s ); @@ -251,31 +283,24 @@ namespace mongo { const BSONObj& sub, AndMatchExpression* root ) { - bool first = true; + int position = 0; BSONObjIterator j( sub ); while ( j.more() ) { BSONElement deep = j.next(); - int op = deep.getGtLtOp(); - if ( op == BSONObj::opREGEX ) { - if ( !first ) - return Status( ErrorCodes::BadValue, "$regex has to be first" ); - - StatusWithMatchExpression s = _parseRegexDocument( name, sub ); - if ( !s.isOK() ) - return s.getStatus(); - root->add( s.getValue() ); - return Status::OK(); - } - - StatusWithMatchExpression s = _parseSubField( name, deep ); + bool stop = false; + StatusWithMatchExpression s = _parseSubField( sub, name, deep, position, &stop ); if ( !s.isOK() ) return s.getStatus(); root->add( s.getValue() ); - first = false; + + if ( stop ) + break; + position++; } + return Status::OK(); } @@ -406,8 +431,8 @@ namespace mongo { if ( !s.isOK() ) return StatusWithMatchExpression( s ); - for ( size_t i = 0; i < theAnd.size(); i++ ) { - temp->add( theAnd.get( i ) ); + for ( size_t i = 0; i < theAnd.numChildren(); i++ ) { + temp->add( theAnd.getChild( i ) ); } theAnd.clearAndRelease(); @@ -416,7 +441,7 @@ namespace mongo { // object case - StatusWithMatchExpression sub = parse( obj ); + StatusWithMatchExpression sub = _parse( obj, false ); if ( !sub.isOK() ) return sub; @@ -483,5 +508,18 @@ namespace mongo { return StatusWithMatchExpression( temp.release() ); } + StatusWithMatchExpression expressionParserGeoCallbackDefault( const char* name, + const BSONObj& section ) { + return StatusWithMatchExpression( ErrorCodes::BadValue, "geo not linked in" ); + } + + MatchExpressionParserGeoCallback expressionParserGeoCallback = expressionParserGeoCallbackDefault; + + StatusWithMatchExpression expressionParserWhereCallbackDefault(const BSONElement& where) { + return StatusWithMatchExpression( ErrorCodes::BadValue, "$where not linked in" ); + } + + MatchExpressionParserWhereCallback expressionParserWhereCallback = expressionParserWhereCallbackDefault; + } diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h index b062387102e..b387af9f36e 100644 --- a/src/mongo/db/matcher/expression_parser.h +++ b/src/mongo/db/matcher/expression_parser.h @@ -18,6 +18,8 @@ #pragma once +#include <boost/function.hpp> + #include "mongo/base/status.h" #include "mongo/base/status_with.h" #include "mongo/db/matcher/expression.h" @@ -30,9 +32,12 @@ namespace mongo { class MatchExpressionParser { public: - static StatusWithMatchExpression parse( const BSONObj& obj ); + static StatusWithMatchExpression parse( const BSONObj& obj ) { + return _parse( obj, true ); + } private: + static StatusWithMatchExpression _parse( const BSONObj& obj, bool topLevel ); /** * parses a field in a sub expression @@ -48,12 +53,15 @@ namespace mongo { * if the query is { x : { $gt : 5, $lt : 8 } } * e is $gt : 5 */ - static StatusWithMatchExpression _parseSubField( const char* name, - const BSONElement& e ); + static StatusWithMatchExpression _parseSubField( const BSONObj& context, + const char* name, + const BSONElement& e, + int position, + bool* stop ); static StatusWithMatchExpression _parseComparison( const char* name, - ComparisonMatchExpression::Type cmp, - const BSONElement& e ); + ComparisonMatchExpression* cmp, + const BSONElement& e ); static StatusWithMatchExpression _parseMOD( const char* name, const BSONElement& e ); @@ -84,4 +92,10 @@ namespace mongo { }; + typedef boost::function<StatusWithMatchExpression(const char* name, const BSONObj& section)> MatchExpressionParserGeoCallback; + extern MatchExpressionParserGeoCallback expressionParserGeoCallback; + + typedef boost::function<StatusWithMatchExpression(const BSONElement& where)> MatchExpressionParserWhereCallback; + extern MatchExpressionParserWhereCallback expressionParserWhereCallback; + } diff --git a/src/mongo/db/matcher/expression_parser_geo.cpp b/src/mongo/db/matcher/expression_parser_geo.cpp new file mode 100644 index 00000000000..cbb41731deb --- /dev/null +++ b/src/mongo/db/matcher/expression_parser_geo.cpp @@ -0,0 +1,47 @@ +// expression_parser_geo.cpp + +/** + * Copyright (C) 2013 10gen Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "mongo/db/matcher/expression_parser.h" + +#include "mongo/base/init.h" +#include "mongo/db/jsobj.h" +#include "mongo/db/matcher/expression_geo.h" +#include "mongo/util/log.h" +#include "mongo/util/mongoutils/str.h" + +namespace mongo { + + StatusWithMatchExpression expressionParserGeoCallbackReal( const char* name, + const BSONObj& section ) { + GeoQuery gq; + if ( !gq.parseFrom( section ) ) + return StatusWithMatchExpression( ErrorCodes::BadValue, "bad geo query" ); + + auto_ptr<GeoMatchExpression> e( new GeoMatchExpression() ); + Status s = e->init( name, gq ); + if ( !s.isOK() ) + return StatusWithMatchExpression( s ); + return StatusWithMatchExpression( e.release() ); + } + + MONGO_INITIALIZER( MatchExpressionParserGeo )( ::mongo::InitializerContext* context ) { + expressionParserGeoCallback = expressionParserGeoCallbackReal; + return Status::OK(); + } + +} diff --git a/src/mongo/db/matcher/expression_parser_geo_test.cpp b/src/mongo/db/matcher/expression_parser_geo_test.cpp new file mode 100644 index 00000000000..d8cf7734c17 --- /dev/null +++ b/src/mongo/db/matcher/expression_parser_geo_test.cpp @@ -0,0 +1,43 @@ +// expression_parser_geo_test.cpp + +/** + * Copyright (C) 2013 10gen Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "mongo/unittest/unittest.h" + +#include "mongo/db/matcher/expression_parser.h" + +#include "mongo/db/jsobj.h" +#include "mongo/db/json.h" +#include "mongo/db/matcher/expression.h" +#include "mongo/db/matcher/expression_geo.h" + +namespace mongo { + + TEST( MatchExpressionParserGeo, WithinBox ) { + BSONObj query = fromjson("{a:{$within:{$box:[{x: 4, y:4},[6,6]]}}}"); + + StatusWithMatchExpression result = MatchExpressionParser::parse( query ); + ASSERT_TRUE( result.isOK() ); + + ASSERT(!result.getValue()->matches(fromjson("{a: [3,4]}"))); + ASSERT(result.getValue()->matches(fromjson("{a: [4,4]}"))); + ASSERT(result.getValue()->matches(fromjson("{a: [5,5]}"))); + ASSERT(result.getValue()->matches(fromjson("{a: [5,5.1]}"))); + ASSERT(result.getValue()->matches(fromjson("{a: {x: 5, y:5.1}}"))); + + } +} diff --git a/src/mongo/db/matcher/expression_parser_test.cpp b/src/mongo/db/matcher/expression_parser_test.cpp index f7ee08f3da0..12d9ce553c2 100644 --- a/src/mongo/db/matcher/expression_parser_test.cpp +++ b/src/mongo/db/matcher/expression_parser_test.cpp @@ -48,6 +48,12 @@ namespace mongo { ASSERT( !result.getValue()->matches( BSON( "x" << 5 << "y" << 4 ) ) ); } + TEST( AtomicMatchExpressionTest, Simple1 ) { + BSONObj query = BSON( "x" << 5 << "$atomic" << BSON( "$gt" << 5 << "$lt" << 8 ) ); + StatusWithMatchExpression result = MatchExpressionParser::parse( query ); + ASSERT_TRUE( result.isOK() ); + } + StatusWith<int> fib( int n ) { if ( n < 0 ) return StatusWith<int>( ErrorCodes::BadValue, "paramter to fib has to be >= 0" ); if ( n <= 1 ) return StatusWith<int>( 1 ); diff --git a/src/mongo/db/matcher/expression_parser_tree.cpp b/src/mongo/db/matcher/expression_parser_tree.cpp index d510ecaae1a..e2aa3f1780e 100644 --- a/src/mongo/db/matcher/expression_parser_tree.cpp +++ b/src/mongo/db/matcher/expression_parser_tree.cpp @@ -39,7 +39,7 @@ namespace mongo { return Status( ErrorCodes::BadValue, "$or/$and/$nor entries need to be full objects" ); - StatusWithMatchExpression sub = parse( e.Obj() ); + StatusWithMatchExpression sub = _parse( e.Obj(), false ); if ( !sub.isOK() ) return sub.getStatus(); diff --git a/src/mongo/db/matcher/expression_test.cpp b/src/mongo/db/matcher/expression_test.cpp index 93c1d20af2a..81ab018fbfb 100644 --- a/src/mongo/db/matcher/expression_test.cpp +++ b/src/mongo/db/matcher/expression_test.cpp @@ -35,8 +35,8 @@ namespace mongo { TEST( LeafMatchExpressionTest, Equal1 ) { BSONObj temp = BSON( "x" << 5 ); - ComparisonMatchExpression e; - e.init( "x", ComparisonMatchExpression::EQ, temp["x"] ); + EqualityMatchExpression e; + e.init( "x", temp["x"] ); ASSERT_TRUE( e.matches( fromjson( "{ x : 5 }" ) ) ); ASSERT_TRUE( e.matches( fromjson( "{ x : [5] }" ) ) ); @@ -54,8 +54,8 @@ namespace mongo { BSONObj temp = BSON( "x" << 5 ); { - ComparisonMatchExpression e; - e.init( "x", ComparisonMatchExpression::LTE, temp["x"] ); + LTEMatchExpression e; + e.init( "x", temp["x"] ); ASSERT_TRUE( e.matches( fromjson( "{ x : 5 }" ) ) ); ASSERT_TRUE( e.matches( fromjson( "{ x : 4 }" ) ) ); ASSERT_FALSE( e.matches( fromjson( "{ x : 6 }" ) ) ); @@ -63,8 +63,8 @@ namespace mongo { } { - ComparisonMatchExpression e; - e.init( "x", ComparisonMatchExpression::LT, temp["x"] ); + LTMatchExpression e; + e.init( "x", temp["x"] ); ASSERT_FALSE( e.matches( fromjson( "{ x : 5 }" ) ) ); ASSERT_TRUE( e.matches( fromjson( "{ x : 4 }" ) ) ); ASSERT_FALSE( e.matches( fromjson( "{ x : 6 }" ) ) ); @@ -72,8 +72,8 @@ namespace mongo { } { - ComparisonMatchExpression e; - e.init( "x", ComparisonMatchExpression::GTE, temp["x"] ); + GTEMatchExpression e; + e.init( "x", temp["x"] ); ASSERT_TRUE( e.matches( fromjson( "{ x : 5 }" ) ) ); ASSERT_FALSE( e.matches( fromjson( "{ x : 4 }" ) ) ); ASSERT_TRUE( e.matches( fromjson( "{ x : 6 }" ) ) ); @@ -81,8 +81,8 @@ namespace mongo { } { - ComparisonMatchExpression e; - e.init( "x", ComparisonMatchExpression::GT, temp["x"] ); + GTMatchExpression e; + e.init( "x", temp["x"] ); ASSERT_FALSE( e.matches( fromjson( "{ x : 5 }" ) ) ); ASSERT_FALSE( e.matches( fromjson( "{ x : 4 }" ) ) ); ASSERT_TRUE( e.matches( fromjson( "{ x : 6 }" ) ) ); diff --git a/src/mongo/db/matcher/expression_tree.cpp b/src/mongo/db/matcher/expression_tree.cpp index 840a4fdd96c..94d54ec07ab 100644 --- a/src/mongo/db/matcher/expression_tree.cpp +++ b/src/mongo/db/matcher/expression_tree.cpp @@ -42,11 +42,28 @@ namespace mongo { _expressions[i]->debugString( debug, level + 1 ); } + bool ListOfMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + const ListOfMatchExpression* realOther = static_cast<const ListOfMatchExpression*>( other ); + + if ( _expressions.size() != realOther->_expressions.size() ) + return false; + + // TOOD: order doesn't matter + for ( unsigned i = 0; i < _expressions.size(); i++ ) + if ( !_expressions[i]->equivalent( realOther->_expressions[i] ) ) + return false; + + return true; + } + // ----- bool AndMatchExpression::matches( const BSONObj& doc, MatchDetails* details ) const { - for ( size_t i = 0; i < size(); i++ ) { - if ( !get(i)->matches( doc, details ) ) { + for ( size_t i = 0; i < numChildren(); i++ ) { + if ( !getChild(i)->matches( doc, details ) ) { if ( details ) details->resetOutput(); return false; @@ -56,8 +73,8 @@ namespace mongo { } bool AndMatchExpression::matchesSingleElement( const BSONElement& e ) const { - for ( size_t i = 0; i < size(); i++ ) { - if ( !get(i)->matchesSingleElement( e ) ) { + for ( size_t i = 0; i < numChildren(); i++ ) { + if ( !getChild(i)->matchesSingleElement( e ) ) { return false; } } @@ -74,8 +91,8 @@ namespace mongo { // ----- bool OrMatchExpression::matches( const BSONObj& doc, MatchDetails* details ) const { - for ( size_t i = 0; i < size(); i++ ) { - if ( get(i)->matches( doc, NULL ) ) { + for ( size_t i = 0; i < numChildren(); i++ ) { + if ( getChild(i)->matches( doc, NULL ) ) { return true; } } @@ -83,8 +100,8 @@ namespace mongo { } bool OrMatchExpression::matchesSingleElement( const BSONElement& e ) const { - for ( size_t i = 0; i < size(); i++ ) { - if ( get(i)->matchesSingleElement( e ) ) { + for ( size_t i = 0; i < numChildren(); i++ ) { + if ( getChild(i)->matchesSingleElement( e ) ) { return true; } } @@ -101,8 +118,8 @@ namespace mongo { // ---- bool NorMatchExpression::matches( const BSONObj& doc, MatchDetails* details ) const { - for ( size_t i = 0; i < size(); i++ ) { - if ( get(i)->matches( doc, NULL ) ) { + for ( size_t i = 0; i < numChildren(); i++ ) { + if ( getChild(i)->matches( doc, NULL ) ) { return false; } } @@ -110,8 +127,8 @@ namespace mongo { } bool NorMatchExpression::matchesSingleElement( const BSONElement& e ) const { - for ( size_t i = 0; i < size(); i++ ) { - if ( get(i)->matchesSingleElement( e ) ) { + for ( size_t i = 0; i < numChildren(); i++ ) { + if ( getChild(i)->matchesSingleElement( e ) ) { return false; } } @@ -132,4 +149,11 @@ namespace mongo { _exp->debugString( debug, level + 1 ); } + bool NotMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + + return _exp->equivalent( other->getChild(0) ); + } + } diff --git a/src/mongo/db/matcher/expression_tree.h b/src/mongo/db/matcher/expression_tree.h index 8dd6885d26c..8c826f78769 100644 --- a/src/mongo/db/matcher/expression_tree.h +++ b/src/mongo/db/matcher/expression_tree.h @@ -30,6 +30,7 @@ namespace mongo { class ListOfMatchExpression : public MatchExpression { public: + ListOfMatchExpression( MatchType type ) : MatchExpression( TREE, type ){} virtual ~ListOfMatchExpression(); /** @@ -43,8 +44,10 @@ namespace mongo { */ void clearAndRelease() { _expressions.clear(); } - size_t size() const { return _expressions.size(); } - MatchExpression* get( size_t i ) const { return _expressions[i]; } + virtual size_t numChildren() const { return _expressions.size(); } + virtual const MatchExpression* getChild( size_t i ) const { return _expressions[i]; } + + bool equivalent( const MatchExpression* other ) const; protected: void _debugList( StringBuilder& debug, int level ) const; @@ -55,6 +58,7 @@ namespace mongo { class AndMatchExpression : public ListOfMatchExpression { public: + AndMatchExpression() : ListOfMatchExpression( AND ){} virtual ~AndMatchExpression(){} virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const; @@ -65,6 +69,7 @@ namespace mongo { class OrMatchExpression : public ListOfMatchExpression { public: + OrMatchExpression() : ListOfMatchExpression( OR ){} virtual ~OrMatchExpression(){} virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const; @@ -75,6 +80,7 @@ namespace mongo { class NorMatchExpression : public ListOfMatchExpression { public: + NorMatchExpression() : ListOfMatchExpression( NOR ){} virtual ~NorMatchExpression(){} virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const; @@ -85,6 +91,7 @@ namespace mongo { class NotMatchExpression : public MatchExpression { public: + NotMatchExpression() : MatchExpression( TREE, NOT ){} /** * @param exp - I own it, and will delete */ @@ -102,6 +109,13 @@ namespace mongo { } virtual void debugString( StringBuilder& debug, int level = 0 ) const; + + bool equivalent( const MatchExpression* other ) const; + + virtual size_t numChildren() const { return 1; } + virtual MatchExpression* getChild( size_t i ) const { return _exp.get(); } + + private: boost::scoped_ptr<MatchExpression> _exp; }; diff --git a/src/mongo/db/matcher/expression_tree_test.cpp b/src/mongo/db/matcher/expression_tree_test.cpp index a02d423c621..e2032da14fd 100644 --- a/src/mongo/db/matcher/expression_tree_test.cpp +++ b/src/mongo/db/matcher/expression_tree_test.cpp @@ -28,8 +28,8 @@ namespace mongo { TEST( NotMatchExpression, MatchesScalar ) { BSONObj baseOperand = BSON( "$lt" << 5 ); - auto_ptr<ComparisonMatchExpression> lt( new ComparisonMatchExpression() ); - ASSERT( lt->init( "a", ComparisonMatchExpression::LT, baseOperand[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> lt( new LTMatchExpression() ); + ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() ); NotMatchExpression notOp; ASSERT( notOp.init( lt.release() ).isOK() ); ASSERT( notOp.matches( BSON( "a" << 6 ), NULL ) ); @@ -38,8 +38,8 @@ namespace mongo { TEST( NotMatchExpression, MatchesArray ) { BSONObj baseOperand = BSON( "$lt" << 5 ); - auto_ptr<ComparisonMatchExpression> lt( new ComparisonMatchExpression() ); - ASSERT( lt->init( "a", ComparisonMatchExpression::LT, baseOperand[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> lt( new LTMatchExpression() ); + ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() ); NotMatchExpression notOp; ASSERT( notOp.init( lt.release() ).isOK() ); ASSERT( notOp.matches( BSON( "a" << BSON_ARRAY( 6 ) ), NULL ) ); @@ -50,8 +50,8 @@ namespace mongo { TEST( NotMatchExpression, ElemMatchKey ) { BSONObj baseOperand = BSON( "$lt" << 5 ); - auto_ptr<ComparisonMatchExpression> lt( new ComparisonMatchExpression() ); - ASSERT( lt->init( "a", ComparisonMatchExpression::LT, baseOperand[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> lt( new LTMatchExpression() ); + ASSERT( lt->init( "a", baseOperand[ "$lt" ] ).isOK() ); NotMatchExpression notOp; ASSERT( notOp.init( lt.release() ).isOK() ); MatchDetails details; @@ -107,10 +107,10 @@ namespace mongo { BSONObj notMatch2 = BSON( "a" << "a1" ); BSONObj notMatch3 = BSON( "a" << "r" ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::LT, baseOperand1[ "$lt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "a", ComparisonMatchExpression::GT, baseOperand2[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new LTMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new GTMatchExpression() ); + ASSERT( sub2->init( "a", baseOperand2[ "$gt" ] ).isOK() ); auto_ptr<RegexMatchExpression> sub3( new RegexMatchExpression() ); ASSERT( sub3->init( "a", "1", "" ).isOK() ); @@ -127,8 +127,8 @@ namespace mongo { TEST( AndOp, MatchesSingleClause ) { BSONObj baseOperand = BSON( "$ne" << 5 ); - auto_ptr<ComparisonMatchExpression> ne( new ComparisonMatchExpression() ); - ASSERT( ne->init( "a", ComparisonMatchExpression::NE, baseOperand[ "$ne" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> ne( new NEMatchExpression() ); + ASSERT( ne->init( "a", baseOperand[ "$ne" ] ).isOK() ); AndMatchExpression andOp; andOp.add( ne.release() ); @@ -144,14 +144,14 @@ namespace mongo { BSONObj baseOperand2 = BSON( "$lt" << 10 ); BSONObj baseOperand3 = BSON( "$lt" << 100 ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::GT, baseOperand1[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new GTMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "a", ComparisonMatchExpression::LT, baseOperand2[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new LTMatchExpression() ); + ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub3( new ComparisonMatchExpression() ); - ASSERT( sub3->init( "b", ComparisonMatchExpression::LT, baseOperand3[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub3( new LTMatchExpression() ); + ASSERT( sub3->init( "b", baseOperand3[ "$lt" ] ).isOK() ); AndMatchExpression andOp; andOp.add( sub1.release() ); @@ -169,11 +169,11 @@ namespace mongo { BSONObj baseOperand1 = BSON( "a" << 1 ); BSONObj baseOperand2 = BSON( "b" << 2 ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::EQ, baseOperand1[ "a" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new EqualityMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "a" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "b", ComparisonMatchExpression::EQ, baseOperand2[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new EqualityMatchExpression() ); + ASSERT( sub2->init( "b", baseOperand2[ "b" ] ).isOK() ); AndMatchExpression andOp; andOp.add( sub1.release() ); @@ -290,8 +290,8 @@ namespace mongo { */ TEST( OrOp, MatchesSingleClause ) { BSONObj baseOperand = BSON( "$ne" << 5 ); - auto_ptr<ComparisonMatchExpression> ne( new ComparisonMatchExpression() ); - ASSERT( ne->init( "a", ComparisonMatchExpression::NE, baseOperand[ "$ne" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> ne( new NEMatchExpression() ); + ASSERT( ne->init( "a", baseOperand[ "$ne" ] ).isOK() ); OrMatchExpression orOp; orOp.add( ne.release() ); @@ -306,12 +306,12 @@ namespace mongo { BSONObj baseOperand1 = BSON( "$gt" << 10 ); BSONObj baseOperand2 = BSON( "$lt" << 0 ); BSONObj baseOperand3 = BSON( "b" << 100 ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::GT, baseOperand1[ "$gt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "a", ComparisonMatchExpression::LT, baseOperand2[ "$lt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub3( new ComparisonMatchExpression() ); - ASSERT( sub3->init( "b", ComparisonMatchExpression::EQ, baseOperand3[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new GTMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new LTMatchExpression() ); + ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub3( new EqualityMatchExpression() ); + ASSERT( sub3->init( "b", baseOperand3[ "b" ] ).isOK() ); OrMatchExpression orOp; orOp.add( sub1.release() ); @@ -330,10 +330,10 @@ namespace mongo { TEST( OrOp, ElemMatchKey ) { BSONObj baseOperand1 = BSON( "a" << 1 ); BSONObj baseOperand2 = BSON( "b" << 2 ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::EQ, baseOperand1[ "a" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "b", ComparisonMatchExpression::EQ, baseOperand2[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new EqualityMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "a" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new EqualityMatchExpression() ); + ASSERT( sub2->init( "b", baseOperand2[ "b" ] ).isOK() ); OrMatchExpression orOp; orOp.add( sub1.release() ); @@ -451,8 +451,8 @@ namespace mongo { TEST( NorOp, MatchesSingleClause ) { BSONObj baseOperand = BSON( "$ne" << 5 ); - auto_ptr<ComparisonMatchExpression> ne( new ComparisonMatchExpression() ); - ASSERT( ne->init( "a", ComparisonMatchExpression::NE, baseOperand[ "$ne" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> ne( new NEMatchExpression() ); + ASSERT( ne->init( "a", baseOperand[ "$ne" ] ).isOK() ); NorMatchExpression norOp; norOp.add( ne.release() ); @@ -468,12 +468,12 @@ namespace mongo { BSONObj baseOperand2 = BSON( "$lt" << 0 ); BSONObj baseOperand3 = BSON( "b" << 100 ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::GT, baseOperand1[ "$gt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "a", ComparisonMatchExpression::LT, baseOperand2[ "$lt" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub3( new ComparisonMatchExpression() ); - ASSERT( sub3->init( "b", ComparisonMatchExpression::EQ, baseOperand3[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new GTMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "$gt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new LTMatchExpression() ); + ASSERT( sub2->init( "a", baseOperand2[ "$lt" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub3( new EqualityMatchExpression() ); + ASSERT( sub3->init( "b", baseOperand3[ "b" ] ).isOK() ); NorMatchExpression norOp; norOp.add( sub1.release() ); @@ -492,10 +492,10 @@ namespace mongo { TEST( NorOp, ElemMatchKey ) { BSONObj baseOperand1 = BSON( "a" << 1 ); BSONObj baseOperand2 = BSON( "b" << 2 ); - auto_ptr<ComparisonMatchExpression> sub1( new ComparisonMatchExpression() ); - ASSERT( sub1->init( "a", ComparisonMatchExpression::EQ, baseOperand1[ "a" ] ).isOK() ); - auto_ptr<ComparisonMatchExpression> sub2( new ComparisonMatchExpression() ); - ASSERT( sub2->init( "b", ComparisonMatchExpression::EQ, baseOperand2[ "b" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub1( new EqualityMatchExpression() ); + ASSERT( sub1->init( "a", baseOperand1[ "a" ] ).isOK() ); + auto_ptr<ComparisonMatchExpression> sub2( new EqualityMatchExpression() ); + ASSERT( sub2->init( "b", baseOperand2[ "b" ] ).isOK() ); NorMatchExpression norOp; norOp.add( sub1.release() ); @@ -514,6 +514,26 @@ namespace mongo { ASSERT( !details.hasElemMatchKey() ); } + + TEST( NorOp, Equivalent ) { + BSONObj baseOperand1 = BSON( "a" << 1 ); + BSONObj baseOperand2 = BSON( "b" << 2 ); + EqualityMatchExpression sub1; + ASSERT( sub1.init( "a", baseOperand1[ "a" ] ).isOK() ); + EqualityMatchExpression sub2; + ASSERT( sub2.init( "b", baseOperand2[ "b" ] ).isOK() ); + + NorMatchExpression e1; + e1.add( sub1.shallowClone() ); + e1.add( sub2.shallowClone() ); + + NorMatchExpression e2; + e2.add( sub1.shallowClone() ); + + ASSERT( e1.equivalent( &e1 ) ); + ASSERT( !e1.equivalent( &e2 ) ); + } + /** TEST( NorOp, MatchesIndexKey ) { BSONObj baseOperand = BSON( "a" << 5 ); diff --git a/src/mongo/db/matcher/expression_where.cpp b/src/mongo/db/matcher/expression_where.cpp new file mode 100644 index 00000000000..1bfc74107af --- /dev/null +++ b/src/mongo/db/matcher/expression_where.cpp @@ -0,0 +1,172 @@ +// expression_where.cpp + +/** + * Copyright (C) 2013 10gen Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "mongo/pch.h" +#include "mongo/base/init.h" +#include "mongo/db/namespacestring.h" +#include "mongo/db/client.h" +#include "mongo/db/jsobj.h" +#include "mongo/db/matcher/expression.h" +#include "mongo/db/matcher/expression_parser.h" +#include "mongo/scripting/engine.h" + +namespace mongo { + + class WhereMatchExpression : public MatchExpression { + public: + WhereMatchExpression() : MatchExpression( SPECIAL, WHERE ){ _func = 0; } + virtual ~WhereMatchExpression(){} + + Status init( const StringData& ns, const StringData& theCode, const BSONObj& scope ); + + virtual bool matches( const BSONObj& doc, MatchDetails* details = 0 ) const; + + virtual bool matchesSingleElement( const BSONElement& e ) const { + return false; + } + + virtual void debugString( StringBuilder& debug, int level = 0 ) const; + + virtual bool equivalent( const MatchExpression* other ) const ; + private: + string _ns; + string _code; + BSONObj _userScope; + + auto_ptr<Scope> _scope; + ScriptingFunction _func; + }; + + Status WhereMatchExpression::init( const StringData& ns, + const StringData& theCode, + const BSONObj& scope ) { + + if ( ns.size() == 0 ) + return Status( ErrorCodes::BadValue, "ns for $where cannot be empty" ); + + if ( theCode.size() == 0 ) + return Status( ErrorCodes::BadValue, "code for $where cannot be empty" ); + + _ns = ns.toString(); + _code = theCode.toString(); + _userScope = scope.getOwned(); + + NamespaceString nswrapper( _ns ); + _scope = globalScriptEngine->getPooledScope( nswrapper.db.c_str(), "where" ); + _func = _scope->createFunction( _code.c_str() ); + + if ( !_func ) + return Status( ErrorCodes::BadValue, "$where compile error" ); + + return Status::OK(); + } + + bool WhereMatchExpression::matches( const BSONObj& obj, MatchDetails* details ) const { + verify( _func ); + + if ( ! _userScope.isEmpty() ) { + _scope->init( &_userScope ); + } + _scope->setObject( "obj", const_cast< BSONObj & >( obj ) ); + _scope->setBoolean( "fullObject" , true ); // this is a hack b/c fullObject used to be relevant + + int err = _scope->invoke( _func, 0, &obj, 1000 * 60, false ); + if ( err == -3 ) { // INVOKE_ERROR + stringstream ss; + ss << "error on invocation of $where function:\n" + << _scope->getError(); + uassert( 16812, ss.str(), false); + } + else if ( err != 0 ) { // ! INVOKE_SUCCESS + uassert( 16813, "unknown error in invocation of $where function", false); + } + + return _scope->getBoolean( "__returnValue" ) != 0; + } + + void WhereMatchExpression::debugString( StringBuilder& debug, int level ) const { + _debugAddSpace( debug, level ); + debug << "$where\n"; + + _debugAddSpace( debug, level + 1 ); + debug << "ns: " << _ns << "\n"; + + _debugAddSpace( debug, level + 1 ); + debug << "code: " << _code << "\n"; + + _debugAddSpace( debug, level + 1 ); + debug << "scope: " << _userScope << "\n"; + } + + bool WhereMatchExpression::equivalent( const MatchExpression* other ) const { + if ( matchType() != other->matchType() ) + return false; + const WhereMatchExpression* realOther = static_cast<const WhereMatchExpression*>(other); + return + _ns == realOther->_ns && + _code == realOther->_code && + _userScope == realOther->_userScope; + } + + + // ----------------- + + StatusWithMatchExpression expressionParserWhereCallbackReal(const BSONElement& where) { + if ( !haveClient() ) + return StatusWithMatchExpression( ErrorCodes::BadValue, "no current client needed for $where" ); + + Client::Context* context = cc().getContext(); + if ( !context ) + return StatusWithMatchExpression( ErrorCodes::BadValue, "no context in $where parsing" ); + + const char* ns = context->ns(); + if ( !ns ) + return StatusWithMatchExpression( ErrorCodes::BadValue, "no ns in $where parsing" ); + + if ( !globalScriptEngine ) + return StatusWithMatchExpression( ErrorCodes::BadValue, "no globalScriptEngine in $where parsing" ); + + auto_ptr<WhereMatchExpression> exp( new WhereMatchExpression() ); + if ( where.type() == String || where.type() == Code ) { + Status s = exp->init( ns, where.valuestr(), BSONObj() ); + if ( !s.isOK() ) + return StatusWithMatchExpression( s ); + return StatusWithMatchExpression( exp.release() ); + } + + if ( where.type() == CodeWScope ) { + Status s = exp->init( ns, + where.codeWScopeCode(), + BSONObj( where.codeWScopeScopeDataUnsafe() ) ); + if ( !s.isOK() ) + return StatusWithMatchExpression( s ); + return StatusWithMatchExpression( exp.release() ); + } + + return StatusWithMatchExpression( ErrorCodes::BadValue, "$where got bad type" ); + } + + MONGO_INITIALIZER( MatchExpressionWhere )( ::mongo::InitializerContext* context ) { + expressionParserWhereCallback = expressionParserWhereCallbackReal; + return Status::OK(); + } + + + + +} diff --git a/src/mongo/db/matcher/matcher.cpp b/src/mongo/db/matcher/matcher.cpp index 0db46c3fba2..a427128bf98 100644 --- a/src/mongo/db/matcher/matcher.cpp +++ b/src/mongo/db/matcher/matcher.cpp @@ -18,6 +18,7 @@ #include "mongo/pch.h" +#include "mongo/db/jsobj.h" #include "mongo/db/matcher/expression_parser.h" #include "mongo/db/matcher/matcher.h" #include "mongo/util/mongoutils/str.h" @@ -35,9 +36,138 @@ namespace mongo { _expression.reset( result.getValue() ); } + Matcher2::Matcher2( const Matcher2 &docMatcher, const BSONObj &constrainIndexKey ) { + + MatchExpression* indexExpression = spliceForIndex( constrainIndexKey, + docMatcher._expression.get() ); + if ( indexExpression ) + _expression.reset( indexExpression ); + } + bool Matcher2::matches(const BSONObj& doc, MatchDetails* details ) const { + if ( !_expression ) + return true; return _expression->matches( doc, details ); } + bool Matcher2::atomic() const { + if ( !_expression ) + return false; + + if ( _expression->matchType() == MatchExpression::ATOMIC ) + return true; + + // we only go down one level + for ( unsigned i = 0; i < _expression->numChildren(); i++ ) { + if ( _expression->getChild( i )->matchType() == MatchExpression::ATOMIC ) + return true; + } + + return false; + } + + bool Matcher2::singleSimpleCriterion() const { + if ( !_expression ) + return false; + + if ( _expression->matchType() == MatchExpression::EQ ) + return true; + + if ( _expression->matchType() == MatchExpression::AND && + _expression->numChildren() == 1 && + _expression->getChild(0)->matchType() == MatchExpression::EQ ) + return true; + + return false; + } + + bool Matcher2::keyMatch( const Matcher2 &docMatcher ) const { + if ( !_expression ) + return docMatcher._expression.get() == NULL; + if ( !docMatcher._expression ) + return false; + + return _expression->equivalent( docMatcher._expression.get() ); + } + + MatchExpression* Matcher2::spliceForIndex( const BSONObj& key, + const MatchExpression* full ) { + set<string> keys; + for ( BSONObjIterator i(key); i.more(); ) { + BSONElement e = i.next(); + keys.insert( e.fieldName() ); + } + return _spliceForIndex( keys, full ); + } + + MatchExpression* Matcher2::_spliceForIndex( const set<string>& keys, + const MatchExpression* full ) { + + switch ( full->matchType() ) { + case MatchExpression::NOT: + case MatchExpression::NOR: + // maybe? + return NULL; + + case MatchExpression::AND: + case MatchExpression::OR: { + auto_ptr<ListOfMatchExpression> dup; + for ( unsigned i = 0; i < full->numChildren(); i++ ) { + MatchExpression* sub = _spliceForIndex( keys, full->getChild( i ) ); + if ( !sub ) + continue; + if ( !dup.get() ) { + if ( full->matchType() == MatchExpression::AND ) + dup.reset( new AndMatchExpression() ); + else + dup.reset( new OrMatchExpression() ); + } + dup->add( sub ); + } + if ( dup.get() ) + return dup.release(); + return NULL; + } + + case MatchExpression::LTE: + case MatchExpression::LT: + case MatchExpression::EQ: + case MatchExpression::GT: + case MatchExpression::GTE: + case MatchExpression::NE: + case MatchExpression::REGEX: + case MatchExpression::MOD: + case MatchExpression::IN: { + const LeafMatchExpression* lme = static_cast<const LeafMatchExpression*>( full ); + if ( !keys.count( lme->getPath().toString() ) ) + return NULL; + return lme->shallowClone(); + } + + case MatchExpression::ALL: + // TODO: conver to $in + return NULL; + + case MatchExpression::ELEM_MATCH_OBJECT: + case MatchExpression::ELEM_MATCH_VALUE: + // future + return NULL; + + case MatchExpression::GEO: + case MatchExpression::SIZE: + case MatchExpression::EXISTS: + case MatchExpression::NIN: + case MatchExpression::TYPE_OPERATOR: + case MatchExpression::ATOMIC: + case MatchExpression::WHERE: + // no go + return NULL; + + + } + + return NULL; + } + } diff --git a/src/mongo/db/matcher/matcher.h b/src/mongo/db/matcher/matcher.h index 64201bd5dad..215cb99e592 100644 --- a/src/mongo/db/matcher/matcher.h +++ b/src/mongo/db/matcher/matcher.h @@ -21,6 +21,7 @@ #include <boost/scoped_ptr.hpp> #include "mongo/base/disallow_copying.h" +#include "mongo/base/status.h" #include "mongo/bson/bsonobj.h" #include "mongo/db/matcher/expression.h" #include "mongo/db/matcher/match_details.h" @@ -33,11 +34,43 @@ namespace mongo { public: explicit Matcher2( const BSONObj& pattern ); + /** + * Generate a matcher for the provided index key format using the + * provided full doc matcher. + * THIS API WILL GO AWAY EVENTUALLY + */ + explicit Matcher2( const Matcher2 &docMatcher, const BSONObj &constrainIndexKey ); + + bool matches(const BSONObj& doc, MatchDetails* details = NULL ) const; + bool atomic() const; + + /* + * this is from old mature + * criteria is 1 equality expression, nothing else + */ + bool singleSimpleCriterion() const; + + const BSONObj* getQuery() const { return &_pattern; }; + std::string toString() const { return _pattern.toString(); } + + /** + * @return true if this key matcher will return the same true/false + * value as the provided doc matcher. + */ + bool keyMatch( const Matcher2 &docMatcher ) const; + + static MatchExpression* spliceForIndex( const BSONObj& key, + const MatchExpression* full ); + private: const BSONObj _pattern; // this is owned by who created us boost::scoped_ptr<MatchExpression> _expression; + + static MatchExpression* _spliceForIndex( const set<std::string>& keys, + const MatchExpression* full ); + }; } |