gistfile1.js

/*

Copy this code into the console and execute Query.analyzeQuery(q1) for a start.
Check the Query object for its properties...

If an error occured while parsing, Query.tokenTree.error will give an explanation.

Execute Query.recordMatchesQuery(r1) to see validation of example record.

Execute Query.analyzeQuery(q2) followed by
Query.recordMatchesQuery(r1,['John',2008]) for example with wild-cards.

For an example with ANY, execute Query.analyzeQuery(q3), then test records
with Query.recordMatchesQuery(r1,w2) -> true
and Query.recordMatchesQuery(r1,w3) -> false

Syntax could be changed to accept recordMatchesQuery(r1,'John',2008).

Does not work with Store records, rec.get('property') is not implemented yet
for case of needRecord.

*/

//---------- test Data

var r1 = {name: 'John', year: 2007, check: 'nsjs'};
var r2 = {name: 'John', year: 2008, check: 'nsjs'};
var q1 = "name = 'John' AND ( year < 2008 OR NOT check = 'nsjs')";
var q2 = "name ANY @% AND ( year < @% OR NOT check = 'nsjs')";
var q3 = "name ANY @%";
var w1 = ['John',2008];
var w2 = [['Jane','Joe','John']];
var w3 = [['Jane','Joe','James']];


//---------- actual Code

Query = {
  
  queryString:    null,
  tokenList:      null,
  usedProperties: null,
  needRecord:     false,
  tokenTree:      null,
  
  
  // functions you will use
  
  analyzeQuery: function (queryString) {
    this.queryString    = queryString;
    this.tokenList      = this.tokenizeString(queryString, this.queryGrammar);
    this.usedProperties = this.propertiesUsedInQuery(this.tokenList);
    this.needRecord     = false; // this.willNeedRecord(usedProperties)
    this.tokenTree      = this.buildTokenTree(this.tokenList, this.queryLogic);
  },
  
  recordMatchesQuery: function (record, wildCardValues) {
    return this.tokenTree.evaluate(record, wildCardValues);
  },
  


  // grammar definitions

  queryGrammar: {
  
    generalTypes        : {
      'UNKNOWN'         : {
        firstCharacter  : /\S/,
        notAllowed      : /[\s'"\w\d\(\)]/
                        },
      'WORD'            : {
        firstCharacter  : /[a-zA-Z_]/,
        notAllowed      : /[^a-zA-Z_0-9]/
                        },
      'NUMBER'          : {
        firstCharacter  : /\d/,
        notAllowed      : /[^\d\.]/,
        format          : /^\d+$|^\d+\.\d+$/
                        },
      'STRING'          : {
        firstCharacter  : /['"]/,
        delimeted       : true
                        },
      'OPEN_PAREN'      : {
        firstCharacter  : /\(/,
        singleCharacter : true
                        },
      'CLOSE_PAREN'     : {
        firstCharacter  : /\)/,
        singleCharacter : true
                        },
      'WILD_CARD'       : {
        rememberCount   : true
                        }
                        },
    reservedTypes       : {
      'WILD_CARD'       : ['@%'],
      'COMPARATOR'      : ['=','!=','<','<=','>','>=','BEGINS_WITH','ENDS_WITH','CONTAINS', 'ANY'],
      'BOOL_OP'         : ['NOT','AND','OR']
                        }
  },

  queryLogic: {
    'STRING'          : {
      evalType        : 'PRIMITIVE',
      evaluate        : function (r,w) { return this.tokenValue }
                      },
    'WORD'            : {
      evalType        : 'PRIMITIVE',
      evaluate        : function (r,w) { return r[this.tokenValue] }
                      },
    'NUMBER'          : {
      evalType        : 'PRIMITIVE',
      evaluate        : function (r,w) { return parseFloat(this.tokenValue) }
                      },
    'WILD_CARD'       : {
      evalType        : 'PRIMITIVE',
      evaluate        : function (r,w) { return w[this.tokenValue] }
                      },
    'COMPARATOR'      : {
      dependsOnValue  : true,
      '='             : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) == this.rightSide.evaluate(r,w) ) }
                      },
      '!='            : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) != this.rightSide.evaluate(r,w) ) }
                      },
      '<'             : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) < this.rightSide.evaluate(r,w) ) }
                      },
      '<='            : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) <= this.rightSide.evaluate(r,w) ) }
                      },
      '>'             : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) > this.rightSide.evaluate(r,w) ) }
                      },
      'BEGINS_WITH'   : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) {
                          var all = this.leftSide.evaluate(r,w);
                          var start = this.rightSide.evaluate(r,w);
                          return ( all.slice(0,start.length) == start ) }
                      },
      'ANY'   : {
        leftType      : 'PRIMITIVE',
        rightType     : 'PRIMITIVE',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) {
                          var prop = this.leftSide.evaluate(r,w);
                          var values = this.rightSide.evaluate(r,w);
                          var found = false;
                          var i = 0;
                          while ( found==false && i < values.length ) {
                            if ( prop == values[i] ) found = true;
                            i++;
                          }
                          return found }
                      },
                      },                
    'BOOL_OP'         : {
      dependsOnValue  : true,
      'AND'           : {
        leftType      : 'BOOLEAN',
        rightType     : 'BOOLEAN',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) && this.rightSide.evaluate(r,w) ) }
                      },
      'OR'            : {
        leftType      : 'BOOLEAN',
        rightType     : 'BOOLEAN',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( this.leftSide.evaluate(r,w) || this.rightSide.evaluate(r,w) ) }
                      },
      'NOT'           : {
        rightType     : 'BOOLEAN',
        evalType      : 'BOOLEAN',
        evaluate      : function (r,w) { return ( ! this.rightSide.evaluate(r,w) ) }
                      },
                      },
    'OPEN_PAREN'      : 'nothing',
    'CLOSE_PAREN'     : 'nothing'
  },



  


  tokenizeString: function (inputString, grammar) {
	
  	// takes a string and returns an array of tokens
  	// depending on the grammar specified
	
  	// currently there is no form of syntax validation !
	
	
    var tokenList           = [];
    var c                   = null;
  	var t                   = null;
    var tokenType           = null;
    var currentTokenType    = null;
    var currentTokenValue   = null;
    var currentDelimeter    = null;
    var endOfString         = false;
    var belongsToToken      = false;
    var skipThisCharacter   = false;
    var rememberCount       = {};
  
  
    // helper function that adds tokens to the tokenList
  
    function addToken (tokenType, tokenValue) {
      t = grammar.generalTypes[tokenType];

      // handling of special cases
      if ( t.format && !t.format.test(tokenValue) ) 
        tokenType = "UNKNOWN";

      if ( t.delimeted ) 
        skipThisCharacter = true;

      if ( !t.delimeted ) {
        for ( reservedType in grammar.reservedTypes ) {
          if ( grammar.reservedTypes[reservedType].indexOf(tokenValue) >= 0 ) {
            tokenType = reservedType;
            t = grammar.generalTypes[tokenType];
          }
        }
      };

      if ( t && t.rememberCount ) {
        if (!rememberCount[tokenType]) rememberCount[tokenType] = 0;
        tokenValue = rememberCount[tokenType];
        rememberCount[tokenType] += 1;
      };

      // push token to list
      tokenList.push( {tokenType: tokenType, tokenValue: tokenValue} );

      // and clean up currentToken
      currentTokenType  = null;
      currentTokenValue = null;
    };
  
  
    // stepping through the string:
    
    for (var i=0; i < inputString.length; i++) {
      endOfString = (i==inputString.length-1);
      // current character
      c = inputString[i];
    
      // set true after end of delimeted token so that final delimeter is not catched again
      skipThisCharacter = false;
    
      //if ( i == inputString.length-1 ) endOfString = true;
    
    
      // if currently inside a token
    
      if ( currentTokenType ) {
      
        // some helpers
        t           = grammar.generalTypes[currentTokenType];
        endOfToken  = (t.delimeted) ? (c==currentDelimeter) : (t.notAllowed.test(c));
      
        // if stil in token
        if ( !endOfToken )
          currentTokenValue += c;
      
        // if end of token reached
        if ( endOfToken || endOfString )
          addToken(currentTokenType, currentTokenValue);
      
        // if end of string don't check again
        if ( endOfString && !endOfToken )
          skipThisCharacter = true;
      };
    
 
    
      // if not inside a token, look for next one
    
      if ( !currentTokenType && !skipThisCharacter ) {
        // look for matching tokenType
        for ( tokenType in grammar.generalTypes ) {
          t = grammar.generalTypes[tokenType];
          if ( t.firstCharacter && t.firstCharacter.test(c) )
            currentTokenType = tokenType;
        };
        // if tokenType found
        if ( currentTokenType ) {
          t = grammar.generalTypes[currentTokenType];
          currentTokenValue = c;
          // handling of special cases
          if ( t.delimeted ) {
            currentTokenValue = "";
            currentDelimeter = c;
          };
          if ( t.singleCharacter || endOfString )
            addToken(currentTokenType, currentTokenValue);
        };
      
      };
    
    };
  
    return tokenList;
  },





  buildTokenTree: function (tokenList, treeLogic) {
  
    var l                    = tokenList.slice();
    var i                    = 0;
    var openParenthesisStack = [];
    var shouldCheckAgain     = false;
    var error                = [];

  
  
    // some helper functions
  
    function tokenLogic (position) {
      var p = position;
      if ( p < 0 ) return false;
      var tl = treeLogic[l[p].tokenType];
      if ( ! tl ) {
        error.push("logic for token '"+l[p].tokenType+"' is not defined");
        return false;
      };
      if ( tl.dependsOnValue ) tl=tl[l[p].tokenValue];
      if ( ! tl ) {
        error.push("logic for token '"+l[p].tokenType+"':'"+l[p].tokenValue+"' is not defined");
        return false;
      };
      l[p].evaluate = tl.evaluate;
      return tl;
    };
  
    function expectedType (side, position) {
      var p = position;
      var tl = tokenLogic(p);
      if ( !tl )            return false;
      if (side == 'left')   return tl.leftType;
      if (side == 'right')  return tl.rightType;
    };
  
    function evalType (position) {
      var p = position;
      var tl = tokenLogic(p);
      if ( !tl )  return false;
      else        return tl.evalType;
    };
  
    function removeToken (position) {
      l.splice(position, 1);
      if ( position <= i ) i--;
    };
  
    function preceedingTokenExists (position) {
      var p = position || i;
      if ( p > 0 )  return true;
      else          return false;
    };
  
    function tokenIsMissingChilds (position) {
      var p = position;
      if ( p < 0 )  return true;
      if (( expectedType('left',p) && !l[p].leftSide )
              || ( expectedType('right',p) && !l[p].rightSide ))
                    return true;
      else          return false;
    };
  
    function typesAreMatching (parent, child) {
      var side = (child < parent) ? 'left' : 'right';
      if ( parent < 0 || child < 0 )    return false;
      if ( !expectedType(side,parent) ) return false;
      if ( !evalType(child) )           return false;
      else                              return (expectedType(side,parent) == evalType(child));
    };
  
    function preceedingTokenCanBeMadeChild (position) {
      var p = position;
      if ( !tokenIsMissingChilds(p) )   return false;
      if ( !preceedingTokenExists(p) )  return false;
      if ( typesAreMatching(p,p-1) )    return true;
      else                              return false;
    };
  
    function preceedingTokenCanBeMadeParent (position) {
      var p = position;
      if ( tokenIsMissingChilds(p) )    return false;
      if ( !preceedingTokenExists(p) )  return false;
      if ( !tokenIsMissingChilds(p-1) ) return false;
      if ( typesAreMatching(p-1,p) )    return true;
      else                              return false;
    };
  
    function makeChild (position) {
      var p = position;
      if (p<1) return false;
      l[p].leftSide = l[p-1];
      removeToken(p-1);
    };
  
    function makeParent (position) {
      var p = position;
      if (p<1) return false;
      l[p-1].rightSide = l[p];
      removeToken(p);
    };
  
    function removeParenthesesPair (position) {
      removeToken(position);
      removeToken(openParenthesisStack.pop());
    };
  
    // step through the tokenList
  
    for (i=0; i < l.length; i++) {
      shouldCheckAgain = false;
    
      if ( l[i].tokenType == 'UNKNOWN' )          error.push('found unknown token: '+l[i].tokenValue);
      if ( l[i].tokenType == 'OPEN_PAREN' )       openParenthesisStack.push(i);
      if ( l[i].tokenType == 'CLOSE_PAREN' )      removeParenthesesPair(i);
      if ( preceedingTokenCanBeMadeChild(i) )     makeChild(i);
      if ( preceedingTokenCanBeMadeParent(i) )  { makeParent(i);
                                                  shouldCheckAgain = true; }; 
      if ( shouldCheckAgain )                     i--;
    
    
    };
  
    // error if tokenList l is not a single token
    if (l.length == 1) l = l[0];
    else error.push('string did not resolve to a single tree');
  
    // return tree or error
    if (error.length > 0) return {error: error.join(',\n'), tree: l};
    else return l;
  
  },


  
  propertiesUsedInQuery: function (tokenList) {
    var propertyList = [];
    for (var i=0; i < tokenList.length; i++) {
      if (tokenList[i].tokenType == 'WORD') propertyList.push(tokenList[i].tokenValue);
    };
    return propertyList;
  }
  

}