/*___INFO__MARK_BEGIN__*/
/*************************************************************************
 *
 *  The Contents of this file are made available subject to the terms of
 *  the Sun Industry Standards Source License Version 1.2
 *
 *  Sun Microsystems Inc., March, 2001
 *
 *
 *  Sun Industry Standards Source License Version 1.2
 *  =================================================
 *  The contents of this file are subject to the Sun Industry Standards
 *  Source License Version 1.2 (the "License"); You may not use this file
 *  except in compliance with the License. You may obtain a copy of the
 *  License at http://gridengine.sunsource.net/Gridengine_SISSL_license.html
 *
 *  Software provided under this License is provided on an "AS IS" basis,
 *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
 *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
 *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
 *  See the License for the specific provisions governing your rights and
 *  obligations concerning the Software.
 *
 *   The Initial Developer of the Original Code is: Sun Microsystems, Inc.
 *
 *   Copyright: 2001 by Sun Microsystems, Inc.
 *
 *   All Rights Reserved.
 *
 ************************************************************************/
/*___INFO__MARK_END__*/
                            
/*----------------------------------------------------
 * Evaluate a boolean expression according to the following grammar
 *
 * Expression      -> And-Expression {'|' And-Expression}
 * And-Expression  -> Simple-Expression {'&' Simple-Expression}
 * Simple-Expression -> '(' Expression ')'
 * Simple-Expression -> 1
 * Simple-Expression -> 0
 * Simple-Expression -> '!' Simple-Expression
 *
 *
 * The litte test program matches an "attribute" against
 * a regular exression which follows the above grammer and the
 * regular expression from the Grid Engine complex(5) man page
 * and prints "match" or "no match"
 * Examples (make sure to use proper quotes depending on your shell)
 * (in "sh" you have to remove the "\")
 * 
 *     % a.out solaris solaris
 *     match
 *     % a.out solaris '\!solaris'
 *     no match
 *     % a.out sol-amd64 '*amd64&sol*'
 *     match
 *     % a.out hp11 '(sol-*64|linux|hp*)&\!sol-sparc'
 *     match
 *     % a.out sol-sparc64 '(sol-*64|linux|hp*)&\!sol-sparc'
 *     match
 *     % a.out sol-sparc '(sol-*64|linux|hp*)&\!sol-sparc'
 *     no match
 *----------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdlib.h>
#include <fnmatch.h>
#include <string.h>

int Expression(void);
int OrExpression(void);
int AndExpression(void);
int SimpleExpression(void);
void NextToken(void);
void Error(void);

char attribute[256];
char expression[256];
char *tokenstring = NULL;
int  token;

enum { T_NONE, T_NOT, T_AND, T_OR, T_BRACEOPEN, T_BRACECLOSE, T_EXP };

char *tokentypes[] = { "T_NONE", "T_NOT", "T_AND", "T_OR", 
                       "T_BRACEOPEN", "T_BRACECLOSE", "T_EXP" };

/*-----------------------------------------------------------
 * call:   a.out attribute  expression
 * Result: print "match"    if "expression" matches  "attribute"
 *         print "no match" if no match
 *-----------------------------------------------------------*/
int main(int argc, char *argv[])
{
   int match;
   
   if (argc != 3 || ((argc == 2) && !strcmp(argv[1], "-h"))) {
      printf("usage: %s <attribute> <expression>\n", argv[0]);
      exit(1);
   } else {
      strcpy(attribute, argv[1]);
      strcpy(expression, argv[2]);
   }
     
   NextToken();
   if (token != T_NONE) {
      match = Expression();
      printf("%s\n", match ? "match" : "no match");
   } else
      Error();
   return 0;
}

/*-----------------------------------------------------------
 * NextToken
 *    set "s" to next token
 *    set "token" to T_NOT, T_AND, T_OR, T_BRACEOPEN, T_BRACECLOSE, T_EXP
 *    set "s" to NULL and "token" to T_NONE of string is completely read
 *-----------------------------------------------------------*/
void NextToken()
{
   static int first = 1;
   static char *s = NULL;
   if (first) {
      s = expression;
      first = 0;
   }

   while (*s == ' ')
      s++;
      
   if (s == NULL || s[0] == '\0') {
      token = T_NONE;
      tokenstring = "<NULL>";
   } else if (s[0] == '!') {
      token = T_NOT;
      tokenstring = strdup("!");
      s++;
   } else if (s[0] == '&') {
      token = T_AND;
      tokenstring = strdup("&");
      s++;
   } else if (s[0] == '|') { 
      token = T_OR;
      tokenstring = strdup("|");
      s++;
   } else if (s[0] == '(') {
      token = T_BRACEOPEN;
      tokenstring = strdup("(");
      s++;
   } else if (s[0] == ')') {
      token = T_BRACECLOSE;
      tokenstring = strdup(")");
      s++;
   } else {
      token = T_EXP;
      if (tokenstring)
         free(tokenstring);
      tokenstring = strdup(s);
      tokenstring = strtok(tokenstring, "!|&() ");
      s++;

      while (s) {
         if (s[0] == '!' || s[0] == '&' || s[0] == '|' || 
             s[0] == '(' || s[0] == ')' || s[0] == '\0')
            break;
         s++;
      }      
   }
}  

/*-----------------------------------------------------------
 * Error 
 *    print simple error message and exit
 *-----------------------------------------------------------*/
void Error()
{
   fprintf(stderr, "Parse Error. Token: %s, string: %s\n", 
           tokentypes[token], tokenstring);
   exit(1);
}

/*----------------------------------------------------------
 * Expression
 *   return 1 if expression is true or 0 otherwise
 *----------------------------------------------------------*/
int Expression()
{
   int match;

   match = OrExpression();
   
   /* after the expression has been evaluated the input stream must be empty */
   if (token != T_NONE)
      Error();
   
   return match; 
}

/*----------------------------------------------------------
 * OrExpression
 * Evaluate an OR expression
 * same input/output parameters as for Expression()
 *----------------------------------------------------------*/
int OrExpression()
{
   int match;
   
   match = AndExpression();
   while (token == T_OR) {
      NextToken();
      match = (match | AndExpression());
   }
   return match;
}

/*----------------------------------------------------------
 * AndExpression
 * Evaluate an AND expression
 *----------------------------------------------------------*/
int AndExpression()
{
   int match;
   
   match = SimpleExpression();
   while (token == T_AND) {
      NextToken();
      match = (match & SimpleExpression());
   }
   return match;
}

/*----------------------------------------------------------
 * SimpleExpression
 *    Evalute a simple expression
 *    this can be a "expression"
 *         1) we can match with fnmatch()
 *         2) !expression
 *         3) (exp)
 *----------------------------------------------------------*/
int SimpleExpression()
{
   int match;
   if (token == T_BRACEOPEN) {
      NextToken();
      match = OrExpression();
      if (token != T_BRACECLOSE)
         Error();
      NextToken();
      return match;
   } else if (token == T_EXP)  {
      match = (fnmatch(tokenstring, attribute, 0) == 0);
      NextToken();
      return match;
   } else if (token == T_NOT) {
      NextToken();
      match = SimpleExpression();
      return !match;
   } else
      Error();
}