path: root/src/mongo/db/matcher/expression_leaf.h

// expression_leaf.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/>.
 *
 *    As a special exception, the copyright holders give permission to link the
 *    code of portions of this program with the OpenSSL library under certain
 *    conditions as described in each individual source file and distribute
 *    linked combinations including the program with the OpenSSL library. You
 *    must comply with the GNU Affero General Public License in all respects for
 *    all of the code used other than as permitted herein. If you modify file(s)
 *    with this exception, you may extend this exception to your version of the
 *    file(s), but you are not obligated to do so. If you do not wish to do so,
 *    delete this exception statement from your version. If you delete this
 *    exception statement from all source files in the program, then also delete
 *    it in the license file.
 */

#pragma once


#include "mongo/bson/bsonobj.h"
#include "mongo/bson/bsonmisc.h"
#include "mongo/db/matcher/expression.h"

namespace pcrecpp {
    class RE;
} // namespace pcrecpp;

namespace mongo {

    /**
     * This file contains leaves in the parse tree that are not array-based.
     *
     * LeafMatchExpression: REGEX MOD EXISTS MATCH_IN
     * ComparisonMatchExpression: EQ LTE LT GT GTE
     * MatchExpression: TYPE_OPERATOR
     */

    /**
     * Many operators subclass from this:
     * REGEX, MOD, EXISTS, IN
     * Everything that inherits from ComparisonMatchExpression.
     */
    class LeafMatchExpression : public MatchExpression {
    public:
        LeafMatchExpression( MatchType matchType )
            : MatchExpression( matchType ) {
        }

        virtual ~LeafMatchExpression(){}

        virtual bool matches( const MatchableDocument* doc, MatchDetails* details = 0 ) const;

        virtual bool matchesSingleElement( const BSONElement& e ) const = 0;

        virtual const StringData path() const { return _path; }

    protected:
        Status initPath( StringData path );

    private:
        StringData _path;
        ElementPath _elementPath;
    };

    /**
     * EQ, LTE, LT, GT, GTE subclass from ComparisonMatchExpression.
     */
    class ComparisonMatchExpression : public LeafMatchExpression {
    public:
        ComparisonMatchExpression( MatchType type ) : LeafMatchExpression( type ){}

        Status init( StringData path, const BSONElement& rhs );

        virtual ~ComparisonMatchExpression(){}

        virtual bool matchesSingleElement( const BSONElement& e ) const;

        virtual const BSONElement& getRHS() const { return _rhs; }

        virtual void debugString( StringBuilder& debug, int level = 0 ) const;

        virtual void toBSON(BSONObjBuilder* out) const;

        virtual bool equivalent( const MatchExpression* other ) const;

        const BSONElement& getData() const { return _rhs; }

    protected:
        BSONElement _rhs;
    };

    //
    // ComparisonMatchExpression inheritors
    //

    class EqualityMatchExpression : public ComparisonMatchExpression {
    public:
        EqualityMatchExpression() : ComparisonMatchExpression( EQ ){}
        virtual LeafMatchExpression* shallowClone() const {
            ComparisonMatchExpression* e = new EqualityMatchExpression();
            e->init( path(), _rhs  );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }
    };

    class LTEMatchExpression : public ComparisonMatchExpression {
    public:
        LTEMatchExpression() : ComparisonMatchExpression( LTE ){}
        virtual LeafMatchExpression* shallowClone() const {
            ComparisonMatchExpression* e = new LTEMatchExpression();
            e->init( path(), _rhs  );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

    };

    class LTMatchExpression : public ComparisonMatchExpression {
    public:
        LTMatchExpression() : ComparisonMatchExpression( LT ){}
        virtual LeafMatchExpression* shallowClone() const {
            ComparisonMatchExpression* e = new LTMatchExpression();
            e->init( path(), _rhs  );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

    };

    class GTMatchExpression : public ComparisonMatchExpression {
    public:
        GTMatchExpression() : ComparisonMatchExpression( GT ){}
        virtual LeafMatchExpression* shallowClone() const {
            ComparisonMatchExpression* e = new GTMatchExpression();
            e->init( path(), _rhs  );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

    };

    class GTEMatchExpression : public ComparisonMatchExpression {
    public:
        GTEMatchExpression() : ComparisonMatchExpression( GTE ){}
        virtual LeafMatchExpression* shallowClone() const {
            ComparisonMatchExpression* e = new GTEMatchExpression();
            e->init( path(), _rhs  );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

    };

    //
    // LeafMatchExpression inheritors
    //

    class RegexMatchExpression : public LeafMatchExpression {
    public:
        /**
         * Maximum pattern size which pcre v8.3 can do matches correctly with
         * LINK_SIZE define macro set to 2 @ pcre's config.h (based on
         * experiments)
         */
        static const size_t MaxPatternSize = 32764;

        RegexMatchExpression();
        ~RegexMatchExpression();

        Status init( StringData path, StringData regex, StringData options );
        Status init( StringData path, const BSONElement& e );

        virtual LeafMatchExpression* shallowClone() const {
            RegexMatchExpression* e = new RegexMatchExpression();
            e->init( path(), _regex, _flags );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

        virtual bool matchesSingleElement( const BSONElement& e ) const;

        virtual void debugString( StringBuilder& debug, int level ) const;

        virtual void toBSON(BSONObjBuilder* out) const;

        void shortDebugString( StringBuilder& debug ) const;

        virtual bool equivalent( const MatchExpression* other ) const;

        const std::string& getString() const { return _regex; }
        const std::string& getFlags() const { return _flags; }

    private:
        std::string _regex;
        std::string _flags;
        std::unique_ptr<pcrecpp::RE> _re;
    };

    class ModMatchExpression : public LeafMatchExpression {
    public:
        ModMatchExpression() : LeafMatchExpression( MOD ){}

        Status init( StringData path, int divisor, int remainder );

        virtual LeafMatchExpression* shallowClone() const {
            ModMatchExpression* m = new ModMatchExpression();
            m->init( path(), _divisor, _remainder );
            if ( getTag() ) {
                m->setTag(getTag()->clone());
            }
            return m;
        }

        virtual bool matchesSingleElement( const BSONElement& e ) const;

        virtual void debugString( StringBuilder& debug, int level ) const;

        virtual void toBSON(BSONObjBuilder* out) const;

        virtual bool equivalent( const MatchExpression* other ) const;

        int getDivisor() const { return _divisor; }
        int getRemainder() const { return _remainder; }

    private:
        int _divisor;
        int _remainder;
    };

    class ExistsMatchExpression : public LeafMatchExpression {
    public:
        ExistsMatchExpression() : LeafMatchExpression( EXISTS ){}

        Status init( StringData path );

        virtual LeafMatchExpression* shallowClone() const {
            ExistsMatchExpression* e = new ExistsMatchExpression();
            e->init( path() );
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

        virtual bool matchesSingleElement( const BSONElement& e ) const;

        virtual void debugString( StringBuilder& debug, int level ) const;

        virtual void toBSON(BSONObjBuilder* out) const;

        virtual bool equivalent( const MatchExpression* other ) const;
    };

    /**
     * INTERNAL
     * terrible name
     * holds the entries of an $in or $all
     * either scalars or regex
     */
    class ArrayFilterEntries {
        MONGO_DISALLOW_COPYING( ArrayFilterEntries );
    public:
        ArrayFilterEntries();
        ~ArrayFilterEntries();

        Status addEquality( const BSONElement& e );
        Status addRegex( RegexMatchExpression* expr );

        const BSONElementSet& equalities() const { return _equalities; }
        bool contains( const BSONElement& elem ) const { return _equalities.count(elem) > 0; }

        size_t numRegexes() const { return _regexes.size(); }
        RegexMatchExpression* regex( int idx ) const { return _regexes[idx]; }

        bool hasNull() const { return _hasNull; }
        bool singleNull() const { return size() == 1 && _hasNull; }
        bool hasEmptyArray() const { return _hasEmptyArray; }
        int size() const { return _equalities.size() + _regexes.size(); }

        bool equivalent( const ArrayFilterEntries& other ) const;

        void copyTo( ArrayFilterEntries& toFillIn ) const;

        void debugString( StringBuilder& debug ) const;

        void toBSON(BSONArrayBuilder* out) const;

    private:
        bool _hasNull; // if _equalities has a jstNULL element in it
        bool _hasEmptyArray;
        BSONElementSet _equalities;
        std::vector<RegexMatchExpression*> _regexes;
    };

    /**
     * query operator: $in
     */
    class InMatchExpression : public LeafMatchExpression {
    public:
        InMatchExpression() : LeafMatchExpression( MATCH_IN ){}
        Status init( 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 void toBSON(BSONObjBuilder* out) const;

        virtual bool equivalent( const MatchExpression* other ) const;

        void copyTo( InMatchExpression* toFillIn ) const;

        const ArrayFilterEntries& getData() const { return _arrayEntries; }

    private:
        bool _matchesRealElement( const BSONElement& e ) const;
        ArrayFilterEntries _arrayEntries;
    };

    //
    // The odd duck out, TYPE_OPERATOR.
    //

    /**
     * Type has some odd semantics with arrays and as such it can't inherit from
     * LeafMatchExpression.
     */
    class TypeMatchExpression : public MatchExpression {
    public:
        TypeMatchExpression() : MatchExpression( TYPE_OPERATOR ){}

        Status init( StringData path, int type );

        virtual MatchExpression* shallowClone() const {
            TypeMatchExpression* e = new TypeMatchExpression();
            e->init(_path, _type);
            if ( getTag() ) {
                e->setTag(getTag()->clone());
            }
            return e;
        }

        virtual bool matchesSingleElement( const BSONElement& e ) const;

        virtual bool matches( const MatchableDocument* doc, MatchDetails* details = 0 ) const;

        virtual void debugString( StringBuilder& debug, int level ) const;

        virtual void toBSON(BSONObjBuilder* out) const;

        virtual bool equivalent( const MatchExpression* other ) const;

        /**
         * What is the type we're matching against?
         */
        int getData() const { return _type; }

        virtual const StringData path() const { return _path; }

    private:
        bool _matches( StringData path,
                       const MatchableDocument* doc,
                       MatchDetails* details = 0 ) const;

        StringData _path;
        ElementPath _elementPath;
        int _type;
    };

}  // namespace mongo