/* $OpenBSD: keynote.y,v 1.7 2000/06/13 19:03:11 angelos Exp $ */
/*
 * The author of this code is Angelos D. Keromytis (angelos@dsl.cis.upenn.edu)
 *
 * This code was written by Angelos D. Keromytis in Philadelphia, PA, USA,
 * in April-May 1998
 *
 * Copyright (C) 1998, 1999 by Angelos D. Keromytis.
 *	
 * Permission to use, copy, and modify this software without fee
 * is hereby granted, provided that this entire notice is included in
 * all copies of any software which is or includes a copy or
 * modification of this software. 
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTY. IN PARTICULAR, THE AUTHORS MAKES NO
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE
 * MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
 * PURPOSE.
 */
%union {
    char   *string;
    double  doubval;
    int     intval;
    int     bool;
};
%type <bool> stringexp numexp expr floatexp
%type <intval> NUM KOF numex afterhint notemptyprog
%type <intval> notemptykeypredicate prog key keyexp keylist
%type <doubval> FLOAT floatex
%type <string> STRING VARIABLE str strnotconcat 
%token TRUE FALSE NUM FLOAT STRING VARIABLE 
%token OPENPAREN CLOSEPAREN EQQ COMMA ACTSTR LOCINI KOF KEYPRE KNVERSION
%token DOTT SIGNERKEY HINT OPENBLOCK CLOSEBLOCK SIGNATUREENTRY PRIVATEKEY
%token SEMICOLON TRUE FALSE
%nonassoc EQ NE LT GT LE GE REGEXP
%left OR
%left AND
%right NOT
%left PLUS MINUS DOTT
%left MULT DIV MOD
%left EXP
%nonassoc UNARYMINUS DEREF OPENNUM OPENFLT
%start grammarswitch
%{
#if HAVE_CONFIG_H
#include "config.h"
#endif /* HAVE_CONFIG_H */

#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>

#if STDC_HEADERS
#include <string.h>
#endif /* STDC_HEADERS */

#include "header.h"
#include "keynote.h"
#include "assertion.h"

static int *keynote_kth_array = (int *) NULL;
static int keylistcount = 0;

static int   resolve_assertion(char *);
static int   keynote_init_kth(void);
static int   isfloatstring(char *);
static int   checkexception(int);
static char *my_lookup(char *);
static int   intpow(int, int);
static int   get_kth(int);
%}
%%

grammarswitch: LOCINI { keynote_exceptionflag = keynote_donteval = 0; }
                localinit
             | ACTSTR { keynote_exceptionflag = keynote_donteval = 0; } program
   	     | KEYPRE { keynote_exceptionflag = keynote_donteval = 0; }
                keypredicate
             | SIGNERKEY { keynote_exceptionflag = keynote_donteval = 0; } key
             | SIGNATUREENTRY { keynote_exceptionflag = keynote_donteval = 0; }
                key
             | KNVERSION { keynote_exceptionflag = keynote_donteval = 0; }
                        STRING { keynote_lex_remove($3);
				 if (strcmp($3, KEYNOTE_VERSION_STRING))
				   keynote_errno = ERROR_SYNTAX;
				 free($3);
			       }
             | PRIVATEKEY { keynote_exceptionflag = keynote_donteval = 0; }
                        STRING { keynote_lex_remove($3);
			         keynote_privkey = $3;
			       }
    
keypredicate: /* Nothing */   { keynote_returnvalue = 0;
                                return 0; 
                              }
       | notemptykeypredicate { keynote_returnvalue = $1;
				return 0;
                              }

notemptykeypredicate:  key     { $$ = $1; }
       		     | keyexp  { $$ = $1; }

keyexp: notemptykeypredicate AND { if (($1 == 0) && !keynote_justrecord)
                                     keynote_donteval = 1;
                                 } notemptykeypredicate 
                 { if ($1 > $4)
		     $$ = $4;
		   else
	       	     $$ = $1;
		   keynote_donteval = 0;
                 }  /* Min */
      | notemptykeypredicate OR { if (($1 == (keynote_current_session->ks_values_num - 1)) && !keynote_justrecord)
	                             keynote_donteval = 1;
       	                         } notemptykeypredicate
                 { if ($1 >= $4)
		     $$ = $1;
		   else
		     $$ = $4;
		   keynote_donteval = 0;
                 }  /* Max */
       | OPENPAREN keyexp CLOSEPAREN { $$ = $2; }
       | KOF { keylistcount = 0; } OPENPAREN {
			 if (!keynote_justrecord && !keynote_donteval)
 	                   if (keynote_init_kth() == -1)
			     return -1;
                       } keylist CLOSEPAREN 
                          {
			      if (keylistcount < $1)
			      {
				  keynote_errno = ERROR_SYNTAX;
				  return -1;
			      }

			    if (!keynote_justrecord && !keynote_donteval)
			      $$ = get_kth($1);
			    else
			      $$ = 0;
			  }  /* K-th */

keylist: key
	    { /* Don't do anything if we're just recording */ 
              if (!keynote_justrecord && !keynote_donteval)
		if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0))
		  keynote_kth_array[$1]++;

	      keylistcount++;
            }
        | key COMMA keylist
            { /* Don't do anything if we're just recording */ 
	      if (!keynote_justrecord && !keynote_donteval)
		if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0))
		  keynote_kth_array[$1]++;

	      keylistcount++;
            }

key: str        {
		   if (keynote_donteval)
		     $$ = 0;
		   else
		   {
		       keynote_lex_remove($1);
		       if (keynote_justrecord)
		       {
			   if (keynote_keylist_add(&keynote_keypred_keylist,
						   $1) == -1)
			   {
			       free($1);
			       return -1;
			   }

			   $$ = 0;
		       }
		       else
			 switch (keynote_in_action_authorizers($1, KEYNOTE_ALGORITHM_UNSPEC))
			 {
			     case -1:
				 free($1);
				 return -1;
				 
			     case RESULT_TRUE:
				 free($1);
				 $$ = keynote_current_session->ks_values_num -
				      1;
				 break;
				 
			     default:
				 $$ = resolve_assertion($1);
				 free($1);
				 break;
			 }
		   }
                 }

localinit: /* Nothing */
         | localconstants

localconstants: VARIABLE EQQ STRING 
	  {
            int i;

            keynote_lex_remove($1);
	    keynote_lex_remove($3);
 
	    /*
	     * Variable names starting with underscores are illegal here.
	     */
	    if ($1[0] == '_')
	    {
		free($1);
		free($3);
		keynote_errno = ERROR_SYNTAX;
		return -1;
	    }
	    
	    /* If the identifier already exists, report error. */
	    if (keynote_env_lookup($1, &keynote_init_list, 1) != (char *) NULL)
	    {
		free($1);
		free($3);
		keynote_errno = ERROR_SYNTAX;
		return -1;
	    }

	    i = keynote_env_add($1, $3, &keynote_init_list, 1, 0);
	    free($1);
	    free($3);

	    if (i != RESULT_TRUE)
	      return -1;
	  }
         | VARIABLE EQQ STRING
	  {
            int i;

	    keynote_lex_remove($1);
	    keynote_lex_remove($3);

	    /*
	     * Variable names starting with underscores are illegal here.
	     */
	    if ($1[0] == '_')
	    {
		free($1);
		free($3);
		keynote_errno = ERROR_SYNTAX;
		return -1;
	    }
	 
	    /* If the identifier already exists, report error. */
	    if (keynote_env_lookup($1, &keynote_init_list, 1) != (char *) NULL)
	    {
		free($1);
		free($3);
		keynote_errno = ERROR_SYNTAX;
		return -1;
	    }

	    i = keynote_env_add($1, $3, &keynote_init_list, 1, 0);
	    free($1);
	    free($3);

	    if (i != RESULT_TRUE)
	      return -1;
	  } localconstants

program: prog { 
	        keynote_returnvalue = $1;
		return 0;
	      }

prog:   /* Nada */ { $$ = 0; }
       | notemptyprog {
			  /* 
			   * Cleanup envlist of additions such as 
			   * regexp results
			   */
			  keynote_env_cleanup(&keynote_temp_list, 1);
                    } SEMICOLON prog
                    {
		      if ($1 > $4)
			$$ = $1;
		      else
			$$ = $4;
                    } 

notemptyprog: expr HINT afterhint
              {
		if (checkexception($1))
		  $$ = $3;
		else
		  $$ = 0;
	      }
       |  expr 
              {
		if (checkexception($1))
		  $$ = keynote_current_session->ks_values_num - 1;
		else
		  $$ = 0;
	      }

afterhint: str {  if (keynote_exceptionflag || keynote_donteval)
		    $$ = 0;
		  else
		  {
		      keynote_lex_remove($1);

		      $$ = keynote_retindex($1);
		      if ($$ == -1)   /* Invalid return value */
			$$ = 0;

		      free($1);
		  }
                }
         | OPENBLOCK prog CLOSEBLOCK { $$ = $2; }


expr:     OPENPAREN expr CLOSEPAREN 	{ $$ = $2; }
	| expr AND { if ($1 == 0)
	               keynote_donteval = 1;
	           } expr               { $$ = ($1 && $4);
		                          keynote_donteval = 0;
		                        }
	| expr OR { if ($1)
	              keynote_donteval = 1; 
	          } expr 		{ $$ = ($1 || $4);
		                          keynote_donteval = 0;
                                        }
	| NOT expr 			{ $$ = !($2); }
	| numexp 			{ $$ = $1; }
	| floatexp			{ $$ = $1; }
	| stringexp 			{ $$ = $1; }
        | TRUE	  		        { $$ = 1; }
        | FALSE	  		        { $$ = 0; }

numexp:	  numex LT numex { $$ = $1 < $3; }
	| numex GT numex { $$ = $1 > $3; }
	| numex EQ numex { $$ = $1 == $3; }
	| numex LE numex { $$ = $1 <= $3; }
	| numex GE numex { $$ = $1 >= $3; }
	| numex NE numex { $$ = $1 != $3; }

floatexp: floatex LT floatex { $$ = $1 < $3; }
	| floatex GT floatex { $$ = $1 > $3; }
	| floatex LE floatex { $$ = $1 <= $3; }
	| floatex GE floatex { $$ = $1 >= $3; }

numex:	  numex PLUS numex  { $$ = $1 + $3; }
	| numex MINUS numex { $$ = $1 - $3; }
	| numex MULT numex  { $$ = $1 * $3; }
        | numex DIV numex   { if ($3 == 0)
	                      {
				  if (!keynote_donteval)
				    keynote_exceptionflag = 1;
			      }
	                      else
			        $$ = ($1 / $3);
			    }
	| numex MOD numex   { if ($3 == 0)
	                      {
				  if (!keynote_donteval)
				    keynote_exceptionflag = 1;
			      }
	                      else
			        $$ = $1 % $3;
			    }
	| numex EXP numex   		{ $$ = intpow($1, $3); }
	| MINUS numex %prec UNARYMINUS 	{ $$ = -($2); }
	| OPENPAREN numex CLOSEPAREN   	{ $$ = $2; }
	| NUM 			       	{ $$ = $1; }
        | OPENNUM strnotconcat         	{ if (keynote_exceptionflag ||
					      keynote_donteval)
	                                    $$ = 0;
 	                                  else
					  {
					      keynote_lex_remove($2);

					      if (!isfloatstring($2))
						$$ = 0;
					      else
						$$ = (int) floor(atof($2));
					      free($2);
					  }
					}

floatex:  floatex PLUS floatex  	{ $$ = ($1 + $3); }
	| floatex MINUS floatex 	{ $$ = ($1 - $3); }
	| floatex MULT floatex          { $$ = ($1 * $3); }
        | floatex DIV floatex   	{ if ($3 == 0)
	                                  {
					      if (!keynote_donteval)
						keynote_exceptionflag = 1;
					  }
	                                  else
			        	   $$ = ($1 / $3);
					}
	| floatex EXP floatex  			{ if (!keynote_exceptionflag &&
						      !keynote_donteval)
	                                            $$ = pow($1, $3);
	                                        }
	| MINUS floatex %prec UNARYMINUS 	{ $$ = -($2); }
	| OPENPAREN floatex CLOSEPAREN	 	{ $$ = $2; }
	| FLOAT			       		{ $$ = $1; }
        | OPENFLT strnotconcat          {
	                                  if (keynote_exceptionflag ||
					      keynote_donteval)
					    $$ = 0.0;
					  else
					  {
					      keynote_lex_remove($2);
					  
					      if (!isfloatstring($2))
						$$ = 0.0;
					      else
						$$ = atof($2);
					      free($2);
					  }
	                                }

stringexp: str EQ str {
                        if (keynote_exceptionflag || keynote_donteval)
			  $$ = 0;
			else
			{
			    $$ = strcmp($1, $3) == 0 ? 1 : 0;
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    free($1);
			    free($3);
			}
		      }
	 | str NE str {
	                if (keynote_exceptionflag || keynote_donteval)
			  $$ = 0;
			else
			{
			    $$ = strcmp($1, $3) != 0 ? 1 : 0;
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    free($1);
			    free($3);
			}
		      }
	 | str LT str {
	                if (keynote_exceptionflag || keynote_donteval)
			  $$ = 0;
			else
			{
			    $$ = strcmp($1, $3) < 0 ? 1 : 0;
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    free($1);
			    free($3);
			}
		      }
	 | str GT str {
	                if (keynote_exceptionflag || keynote_donteval)
			  $$ = 0;
			else
			{
			    $$ = strcmp($1, $3) > 0 ? 1 : 0;
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    free($1);
			    free($3);
			}
		      }
	 | str LE str {
	                if (keynote_exceptionflag || keynote_donteval)
			  $$ = 0;
			else
			{
			    $$ = strcmp($1, $3) <= 0 ? 1 : 0;
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    free($1);
			    free($3);
			}
		      }
	 | str GE str {
	                if (keynote_exceptionflag || keynote_donteval)
			  $$ = 0;
			else
			{
			    $$ = strcmp($1, $3) >= 0 ? 1 : 0;
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    free($1);
			    free($3);
			}
		      }
	 | str REGEXP str 
            {
	      regmatch_t pmatch[32];
	      char grp[4], *gr;
	      regex_t preg;
	      int i;

	      if (keynote_exceptionflag || keynote_donteval)
		$$ = 0;
	      else
	      {
		  keynote_lex_remove($1);
		  keynote_lex_remove($3);

		  memset(pmatch, 0, sizeof(pmatch));
		  memset(grp, 0, sizeof(grp));

#if HAVE_REGCOMP
		  if (regcomp(&preg, $3, REG_EXTENDED))
		  {
#else /* HAVE_REGCOMP */
#error "This system does not have regcomp()."
#endif /* HAVE_REGCOMP */
		      free($1);
		      free($3);
		      keynote_exceptionflag = 1;
		  }
		  else
		  {
		      /* Clean-up residuals from previous regexps */
		      keynote_env_cleanup(&keynote_temp_list, 1);

		      free($3);
		      i = regexec(&preg, $1, 32, pmatch, 0);
		      $$ = (i == 0 ? 1 : 0);
		      if (i == 0)
		      {
#if !defined(HAVE_SNPRINTF)
			  sprintf(grp, "%d", preg.re_nsub);
#else /* !HAVE_SNPRINTF */
			  snprintf(grp, 3, "%d", preg.re_nsub);
#endif /* !HAVE_SNPRINTF */
			  if (keynote_env_add("_0", grp, &keynote_temp_list,
					      1, 0) != RESULT_TRUE)
			  {
			      free($1);
			      regfree(&preg);
			      return -1;
			  }

			  for (i = 1; i < 32 && pmatch[i].rm_so != -1; i++)
			  {
			      gr = calloc(pmatch[i].rm_eo - pmatch[i].rm_so +
					  1, sizeof(char));
			      if (gr == (char *) NULL)
			      {
				  free($1);
				  regfree(&preg);
				  keynote_errno = ERROR_MEMORY;
				  return -1;
			      }

			      strncpy(gr, $1 + pmatch[i].rm_so,
				      pmatch[i].rm_eo - pmatch[i].rm_so);
			      gr[pmatch[i].rm_eo - pmatch[i].rm_so] = '\0';
#if !defined(HAVE_SNPRINTF)
			      sprintf(grp, "_%d", i);
#else /* !HAVE_SNPRINTF */
			      snprintf(grp, 3, "_%d", i);
#endif /* !HAVE_SNPRINTF */
			      if (keynote_env_add(grp, gr, &keynote_temp_list,
						  1, 0) == -1)
			      {
				  free($1);
				  regfree(&preg);
				  free(gr);
				  return -1;
			      }
			      else
				free(gr);
			  }
		      }

		      regfree(&preg);
		      free($1);
		  }
	      }
	    }

str: str DOTT str    {  if (keynote_exceptionflag || keynote_donteval)
			  $$ = (char *) NULL;
			else
			{
			    $$ = calloc(strlen($1) + strlen($3) + 1,
					sizeof(char));
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    if ($$ == (char *) NULL)
			    {
				free($1);
				free($3);
				keynote_errno = ERROR_MEMORY;
				return -1;
			    }
 
			    strcpy($$, $1);
			    strcpy($$ + strlen($1), $3);
			    free($1);
			    free($3);
			    if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
			      return -1;
			}
		      }
	| strnotconcat { $$ = $1; }

strnotconcat: STRING 	                { $$ = $1; }
        | OPENPAREN str CLOSEPAREN 	{ $$ = $2; }
        | VARIABLE      {  if (keynote_exceptionflag || keynote_donteval)
	                     $$ = (char *) NULL;
 	                   else
			   {
			       $$ = my_lookup($1);
			       keynote_lex_remove($1);
			       free($1);
			       if ($$ == (char *) NULL)
			       {
				   if (keynote_errno)
				     return -1;
				   $$ = strdup("");
			       }
			       else
				 $$ = strdup($$);

			       if ($$ == (char *) NULL)
			       {
				   keynote_errno = ERROR_MEMORY;
				   return -1;
			       }

			       if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
				 return -1;
			   }
	                 }
	| DEREF str      {  if (keynote_exceptionflag || keynote_donteval)
			      $$ = (char *) NULL;
			    else
			    {
				$$ = my_lookup($2);
				keynote_lex_remove($2);
				free($2);
				if ($$ == (char *) NULL)
				{
				    if (keynote_errno)
				      return -1;
				    $$ = strdup("");
				}
				else
				  $$ = strdup($$);

				if ($$ == (char *) NULL)
				{
				    keynote_errno = ERROR_MEMORY;
				    return -1;
				}

				if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
				  return -1;
			    }
			 }
%%

/*
 * Find all assertions signed by s and give us the one with the highest
 * return value.
 */
static int
resolve_assertion(char *s)
{
    int i, alg = KEYNOTE_ALGORITHM_NONE, p = 0;
    void *key = (void *) s;
    struct assertion *as;
    struct keylist *kl;

    kl = keynote_keylist_find(keynote_current_assertion->as_keylist, s);
    if (kl != (struct keylist *) NULL)
    {
	alg = kl->key_alg;
	key = kl->key_key;
    }

    for (i = 0;; i++)
    {
	as = keynote_find_assertion(key, i, alg);
	if (as == (struct assertion *) NULL)  /* Gone through all of them */
	  return p;

	if (as->as_kresult == KRESULT_DONE)
	  if (p < as->as_result)
	    p = as->as_result;

	/* Short circuit if we find an assertion with maximum return value */
	if (p == (keynote_current_session->ks_values_num - 1))
	  return p;
    }

    return 0;
}

/* 
 * Environment variable lookup. 
 */
static char *
my_lookup(char *s)
{
    struct keynote_session *ks = keynote_current_session;
    char *ret;

    if (!strcmp(s, "_MIN_TRUST"))
    {
	keynote_used_variable = 1;
	return ks->ks_values[0];
    }
    else
    {
	if (!strcmp(s, "_MAX_TRUST"))
	{
	    keynote_used_variable = 1;
	    return ks->ks_values[ks->ks_values_num - 1];
	}
	else
	{
	    if (!strcmp(s, "_VALUES"))
	    {
		keynote_used_variable = 1;
		return keynote_env_lookup("_VALUES", ks->ks_env_table,
					  HASHTABLESIZE);
	    }
	    else
	    {
		if (!strcmp(s, "_ACTION_AUTHORIZERS"))
		{
		    keynote_used_variable = 1;
		    return keynote_env_lookup("_ACTION_AUTHORIZERS",
					      ks->ks_env_table, HASHTABLESIZE);
		}
	    }
	}
    }

    /* Temporary list (regexp results) */
    ret = keynote_env_lookup(s, &keynote_temp_list, 1);
    if (ret != (char *) NULL)
      return ret;
    else
      if (keynote_errno != 0)
	return (char *) NULL;

    /* Local-Constants */
    ret = keynote_env_lookup(s, &keynote_init_list, 1);
    if (ret != (char *) NULL)
      return ret;
    else
      if (keynote_errno != 0)
	return (char *) NULL;

    keynote_used_variable = 1;

    /* Action environment */
    ret = keynote_env_lookup(s, ks->ks_env_table, HASHTABLESIZE);
    if (ret != (char *) NULL)
      return ret;
    else
      if (keynote_errno != 0)
	return (char *) NULL;

    /* Regex table */
    return keynote_env_lookup(s, &(ks->ks_env_regex), 1);
}

/*
 * If we had an exception, the boolean expression should return false.
 * Otherwise, return the result of the expression (the argument).
 */
static int
checkexception(int i)
{
    if (keynote_exceptionflag)
    {
	keynote_exceptionflag = 0;
	return 0;
    }
    else
      return i;
}


/* 
 * Integer exponentation -- copied from Schneier's AC2, page 244. 
 */
static int
intpow(int x, int y)
{
    int s = 1;
    
    /* 
     * x^y with y < 0 is equivalent to 1/(x^y), which for
     * integer arithmetic is 0.
     */
    if (y < 0)
      return 0;

    while (y)
    {
	if (y & 1)
	  s *= x;
	
	y >>= 1;
	x *= x;
    }

    return s;
}

/* 
 * Check whether the string is a floating point number. 
 */
static int
isfloatstring(char *s)
{
    int i, point = 0;
    
    for (i = strlen(s) - 1; i >= 0; i--)
      if (!isdigit((int) s[i]))
      {
	  if (s[i] == '.')
	  {
	      if (point == 1)
	        return 0;
	      else
	        point = 1;
	  }
	  else
	    return 0;
      }

    return 1;
}

/*
 * Initialize array for threshold search.
 */
static int
keynote_init_kth(void)
{
    int i = keynote_current_session->ks_values_num;
    
    if (i == -1)
      return -1;
    
    keynote_kth_array = (int *) calloc(i, sizeof(int));
    if (keynote_kth_array == (int *) NULL)
    {
	keynote_errno = ERROR_MEMORY;
	return -1;
    }

    return RESULT_TRUE;
}

/*
 * Get the k-th best return value.
 */
static int
get_kth(int k)
{
    int i;

    for (i = keynote_current_session->ks_values_num - 1; i >= 0; i--)
    {
	k -= keynote_kth_array[i];
	
	if (k <= 0)
	  return i;
    }

    return 0;
}

/*
 * Cleanup array.
 */
void
keynote_cleanup_kth(void)
{
    if (keynote_kth_array != (int *) NULL)
    {
	free(keynote_kth_array);
	keynote_kth_array = (int *) NULL;
    }
}

void
knerror(char *s)
{}