path: root/db/matcher.cpp

// matcher.cpp

/* JSMatcher is our boolean expression evaluator for "where" clauses */

/**
*    Copyright (C) 2008 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 "stdafx.h"
#include "jsobj.h"
#include "../util/goodies.h"
#include "javajs.h"
#include "../util/unittest.h"

#if defined(_WIN32)

#include <hash_map>
using namespace stdext;

typedef const char * MyStr;
struct less_str {
   bool operator()(const MyStr & x, const MyStr & y) const {
      if ( strcmp(x, y) > 0)
         return true;

      return false;
   }
};

typedef hash_map<const char*, int, hash_compare<const char *, less_str> > strhashmap;

#else

#include <ext/hash_map>
using namespace __gnu_cxx;

typedef const char * MyStr;
struct eq_str {
   bool operator()(const MyStr & x, const MyStr & y) const {
      if ( strcmp(x, y) == 0)
         return true;

      return false;
   }
};

typedef hash_map<const char*, int, hash<const char *>, eq_str > strhashmap;

#endif

//#include "minilex.h"
//MiniLex minilex;

class Where { 
public:
    Where() { jsScope = 0; }
	~Where() {
#if !defined(NOJNI)
		JavaJS->scopeFree(scope);
#endif
		if ( jsScope )
		  delete jsScope;
		scope = 0; func = 0;
	}

	jlong scope, func;
    BSONObj *jsScope;
  
	void setFunc(const char *code) {
#if !defined(NOJNI)
		func = JavaJS->functionCreate( code );
#endif
	}

};

JSMatcher::~JSMatcher() { 
	for( int i = 0; i < nBuilders; i++ )
		delete builders[i];
	delete in;
	delete where;
}

#include "pdfile.h"

/* _jsobj          - the query pattern
   indexKeyPattern - the "key pattern" / template of what is in the keys of the index we are using. 
                     used to set indexMatches return value from matches()
*/
JSMatcher::JSMatcher(BSONObj &_jsobj, BSONObj indexKeyPattern) : 
   in(0), where(0), jsobj(_jsobj), nRegex(0)
{
    checkInIndex = !indexKeyPattern.isEmpty();
	nBuilders = 0;
	BSONObjIterator i(jsobj);
	n = 0;
	while( i.more() ) {
		BSONElement e = i.next();
		if( e.eoo() )
			break;
		
		if( ( e.type() == CodeWScope || e.type() == Code ) && strcmp(e.fieldName(), "$where")==0 ) { 
			// $where: function()...
			uassert( "$where occurs twice?", where == 0 );
			where = new Where();
			uassert( "$where query, but jni is disabled", JavaJS );
#if !defined(NOJNI)
			where->scope = JavaJS->scopeCreate();
			JavaJS->scopeSetString(where->scope, "$client", database->name.c_str());
			
			if ( e.type() == CodeWScope ){
			  where->setFunc( e.codeWScopeCode() );
			  where->jsScope = new BSONObj( e.codeWScopeScopeData() , 0 );
			}
			else {
			  const char *code = e.valuestr();
			  where->setFunc(code);
			}
#endif
			continue;
		}

		if( e.type() == RegEx ) {
			if( nRegex >= 4 ) {
				cout << "ERROR: too many regexes in query" << endl;
			}
			else {
				pcrecpp::RE_Options options;
				options.set_utf8(true);
				const char *flags = e.regexFlags();
				while( flags && *flags ) { 
					if( *flags == 'i' )
						options.set_caseless(true);
					else if( *flags == 'm' )
						options.set_multiline(true);
					else if( *flags == 'x' )
						options.set_extended(true);
					flags++;
				}
                RegexMatcher& rm = regexs[nRegex];
				rm.re = new pcrecpp::RE(e.regex(), options);
				rm.fieldName = e.fieldName();
                rm.inIndex = indexKeyPattern.hasElement(rm.fieldName);

				nRegex++;
			}
			continue;
		}

		// greater than / less than...
		// e.g., e == { a : { $gt : 3 } }
		//       or 
		//            { a : { $in : [1,2,3] } }
		if( e.type() == Object ) {
			// e.g., fe == { $gt : 3 }
			BSONObjIterator j(e.embeddedObject());
			bool ok = false;
			while( j.more() ) {
				BSONElement fe = j.next();
				if( fe.eoo() ) 
					break;
				// BSONElement fe = e.embeddedObject().firstElement();
				const char *fn = fe.fieldName();
                /* TODO: use getGtLtOp() here.  this code repeats ourself */
				if( fn[0] == '$' && fn[1] ) { 
					if( fn[2] == 't' ) { 
						int op = Equality;
						if( fn[1] == 'g' ) { 
							if( fn[3] == 0 ) op = GT;
							else if( fn[3] == 'e' && fn[4] == 0 ) op = GTE;
							else
							  uassert("invalid $operator", false);
						}
						else if( fn[1] == 'l' ) { 
							if( fn[3] == 0 ) op = LT;
							else if( fn[3] == 'e' && fn[4] == 0 ) op = LTE;
							else
							  uassert("invalid $operator", false);
						}
						else
						  uassert("invalid $operator", false);
						if( op ) {
						  uassert("too many items to match in query", nBuilders < 8);
							BSONObjBuilder *b = new BSONObjBuilder();
							builders[nBuilders++] = b;
							b->appendAs(fe, e.fieldName());
                            addBasic(b->done().firstElement(), op, indexKeyPattern);
							ok = true;
						}
					}
                    else if( fn[2] == 'e' ) { 
                        if( fn[1] == 'n' && fn[3] == 0 ) { 
                            // $ne
                            uassert("too many items to match in query", nBuilders < 8);
							BSONObjBuilder *b = new BSONObjBuilder();
							builders[nBuilders++] = b;
							b->appendAs(fe, e.fieldName());
							addBasic(b->done().firstElement(), NE, indexKeyPattern);
							ok = true;
                        }
                        else
                            uassert("invalid $operator", false);
                    }
					else if( fn[1] == 'i' && fn[2] == 'n' && fn[3] == 0 && fe.type() == Array ) {
						// $in
                        uassert( "only 1 $in statement per query supported", in == 0 ); // todo...
						in = new set<BSONElement,element_lt>();
						BSONObjIterator i(fe.embeddedObject());
                        if( i.more() ) {
                            while( 1 ) {
                                BSONElement ie = i.next();
                                if( ie.eoo() ) 
                                    break;
                                in->insert(ie);
                            }
                        }
                        addBasic(e, opIN, indexKeyPattern); // e not actually used at the moment for $in
						ok = true;
					}
					else
					  uassert("invalid $operator", false);
				}
				else {
					ok = false;
					break;
				}
			}
			if( ok ) 
				continue;
		}

        // normal, simple case e.g. { a : "foo" }
        addBasic(e, Equality, indexKeyPattern);
	}
}

inline int JSMatcher::valuesMatch(BSONElement& l, BSONElement& r, int op) { 
	if( op == 0 ) 
		return l.valuesEqual(r);

    if( op == NE ) {
        return !l.valuesEqual(r);
    }

	if( op == opIN ) {
		// { $in : [1,2,3] }
        int c = in->count(l);
        return c;
	}

	/* check LT, GTE, ... */
	if( l.type() != r.type() )
		return false;
	int c = compareElementValues(l, r);
	if( c < -1 ) c = -1;
	if( c > 1 ) c = 1;
	int z = 1 << (c+1); 
	return (op & z);
}

/* Check if a particular field matches.

   fieldName - field to match "a.b" if we are reaching into an embedded object.
   toMatch   - element we want to match.
   obj       - database object to check against
   compareOp - Equality, LT, GT, etc.
   deep      - out param.  set to true/false if we scanned an array
   isArr     - 

   Special forms:

     { "a.b" : 3 }             means       obj.a.b == 3
     { a : { $lt : 3 } }       means       obj.a < 3
	 { a : { $in : [1,2] } }   means       [1,2].contains(obj.a)

   return value
   -1 mismatch
    0 missing element
    1 match
*/
int JSMatcher::matchesDotted(const char *fieldName, BSONElement& toMatch, BSONObj& obj, int compareOp, bool *deep, bool isArr) { 
	{
		const char *p = strchr(fieldName, '.');
		if( p ) { 
			string left(fieldName, p-fieldName);

			BSONElement e = obj.getField(left.c_str());
			if( e.eoo() )
				return 0;
			if( e.type() != Object && e.type() != Array )
				return -1;

			BSONObj eo = e.embeddedObject();
			return matchesDotted(p+1, toMatch, eo, compareOp, deep, e.type() == Array);
		}
	}

	BSONElement e = obj.getField(fieldName);

	if( valuesMatch(e, toMatch, compareOp) ) {
		return 1;
	}
	else if( e.type() == Array ) {
		BSONObjIterator ai(e.embeddedObject());
		while( ai.more() ) { 
			BSONElement z = ai.next();
			if( valuesMatch( z, toMatch, compareOp) ) {
				if( deep )
					*deep = true;
				return 1;
			}
		}
	}
	else if( isArr ) { 
		BSONObjIterator ai(obj);
		while( ai.more() ) { 
			BSONElement z = ai.next();
			if( z.type() == Object ) {
				BSONObj eo = z.embeddedObject();
				int cmp = matchesDotted(fieldName, toMatch, eo, compareOp, deep);
				if( cmp > 0 ) { 
					if( deep ) *deep = true;
					return 1;
				}
			}
		}
	}
	else if( e.eoo() ) { 
        // 0 indicatse "missing element"
        return 0;
	}
	return -1;
}

extern int dump;

inline bool _regexMatches(RegexMatcher& rm, BSONElement& e) { 
	char buf[64];
	const char *p = buf;
	if( e.type() == String || e.type() == Symbol )
		p = e.valuestr();
    else if( e.isNumber() ) { 
		sprintf(buf, "%f", e.number());
	}
	else if( e.type() == Date ) { 
		unsigned long long d = e.date();
		time_t t = (d/1000);
		time_t_to_String(t, buf);
	}
	else
		return false;
	return rm.re->PartialMatch(p);
}
/* todo: internal dotted notation scans -- not done yet here. */
inline bool regexMatches(RegexMatcher& rm, BSONElement& e, bool *deep) { 
	if( e.type() != Array ) 
		return _regexMatches(rm, e);

	BSONObjIterator ai(e.embeddedObject());
	while( ai.more() ) { 
		BSONElement z = ai.next();
		if( _regexMatches(rm, z) ) {
			if( deep )
				*deep = true;
			return true;
		}
	}
	return false;
}

/* See if an object matches the query.
   deep - return true when means we looked into arrays for a match 

   Wondering if it would be worth having 
     if( !inIndex && !ok ) continue;
   in each loop to bypass those checks.  probably not worth checking as usually we are ok.
*/
bool JSMatcher::matches(BSONObj& jsobj, bool *deep) {
	if( deep ) 
		*deep = false;

	/* assuming there is usually only one thing to match.  if more this
	could be slow sometimes. */

	// check normal non-regex cases:
	for( int i = 0; i < n; i++ ) {
        BasicMatcher& bm = basics[i];
		BSONElement& m = bm.toMatch;
        // -1=mismatch. 0=missing element. 1=match 
		int cmp = matchesDotted(m.fieldName(), m, jsobj, bm.compareOp, deep);

		if( cmp < 0 )
			return false;
        if( cmp == 0 ) {
            /* missing is ok iff we were looking for null */
            if( m.type() == jstNULL || m.type() == Undefined ) {
                if( bm.compareOp == NE ) {
                    return false;
                }
            } else {
				return false;
            }
        }
	}

	for( int r = 0; r < nRegex; r++ ) { 
		RegexMatcher& rm = regexs[r];
		BSONElement e = jsobj.getFieldDotted(rm.fieldName);
		if( e.eoo() )
			return false;
		if( !regexMatches(rm, e, deep) )
			return false;
	}

    if( where ) { 
        if( where->func == 0 ) {
            uassert("$where compile error", false);
            return false; // didn't compile
        }
#if !defined(NOJNI)		
        /**if( 1 || jsobj.objsize() < 200 || where->fullObject ) */ 
        {
            if ( where->jsScope ){
                JavaJS->scopeInit( where->scope , where->jsScope );
            }
            JavaJS->scopeSetThis(where->scope, &jsobj);		  
            JavaJS->scopeSetObject(where->scope, "obj", &jsobj);		  
        } 
        /*else {
        BSONObjBuilder b;
        where->buildSubset(jsobj, b);
        BSONObj temp = b.done();
        JavaJS->scopeSetObject(where->scope, "obj", &temp);
        }*/
        if( JavaJS->invoke(where->scope, where->func) ) {
            uassert("error in invocation of $where function", false);
            return false;
        }
        return JavaJS->scopeGetBoolean(where->scope, "return") != 0;
#else
        return false;
#endif
    }

    return true;
}

struct JSObj1 js1;

#pragma pack(push,1)
struct JSObj2 {
	JSObj2() {
		totsize=sizeof(JSObj2);
		s = String; strcpy_s(sname, 7, "abcdef"); slen = 10; 
		strcpy_s(sval, 10, "123456789"); eoo = EOO;
	}
	unsigned totsize;
	char s;
	char sname[7];
	unsigned slen;
	char sval[10];
	char eoo;
} js2;

struct JSUnitTest : public UnitTest {
	void run() {

		BSONObj j1((const char *) &js1);
		BSONObj j2((const char *) &js2);
		JSMatcher m(j2, BSONObj());
		assert( m.matches(j1) );
		js2.sval[0] = 'z';
		assert( !m.matches(j1) );
		JSMatcher n(j1, BSONObj());
		assert( n.matches(j1) );
		assert( !n.matches(j2) );

		BSONObj j0 = emptyObj;
//		BSONObj j0((const char *) &js0);
		JSMatcher p(j0, BSONObj());
		assert( p.matches(j1) );
		assert( p.matches(j2) );
	}
} jsunittest;

#pragma pack(pop)

struct RXTest : public UnitTest { 

    RXTest() { 
    }

	void run() { 
		/*
		static const boost::regex e("(\\d{4}[- ]){3}\\d{4}");
		static const boost::regex b(".....");
		cout << "regex result: " << regex_match("hello", e) << endl;
		cout << "regex result: " << regex_match("abcoo", b) << endl;
		*/
		pcrecpp::RE re1(")({a}h.*o");
		pcrecpp::RE re("h.llo");
		assert( re.FullMatch("hello") );
		assert( !re1.FullMatch("hello") );


		pcrecpp::RE_Options options;
		options.set_utf8(true);
		pcrecpp::RE part("dwi", options);
		assert( part.PartialMatch("dwight") );
	}
} rxtest;