Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libkeynote/keynote.y	Lines:	0	88	0.0 %
Date:	2017-11-13	Branches:	0	68	0.0 %


/* $OpenBSD: keynote.y,v 1.18 2017/04/27 15:35:36 millert 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 with or 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
%{
#include <sys/types.h>

#include <ctype.h>
#include <math.h>
#include <regex.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

static int *keynote_kth_array = 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) != 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) != 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[10], *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 (regcomp(&preg, $3, REG_EXTENDED))
		  {
		      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)
		      {
			  snprintf(grp, sizeof grp, "%lu",
			        (unsigned long)preg.re_nsub);
			  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 == 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';
			      snprintf(grp, sizeof grp, "_%d", i);
			      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)
			  $$ = NULL;
			else
			{
			    int len = strlen($1) + strlen($3) + 1;
			    $$ = calloc(len, sizeof(char));
			    keynote_lex_remove($1);
			    keynote_lex_remove($3);
			    if ($$ == NULL)
			    {
				free($1);
				free($3);
				keynote_errno = ERROR_MEMORY;
				return -1;
			    }
			    snprintf($$, len, "%s%s", $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)
	                     $$ = NULL;
 	                   else
			   {
			       $$ = my_lookup($1);
			       keynote_lex_remove($1);
			       free($1);
			       if ($$ == NULL)
			       {
				   if (keynote_errno)
				     return -1;
				   $$ = strdup("");
			       }
			       else
				 $$ = strdup($$);

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

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

				if ($$ == 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 != NULL)
    {
	alg = kl->key_alg;
	key = kl->key_key;
    }

    for (i = 0;; i++)
    {
	as = keynote_find_assertion(key, i, alg);
	if (as == 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) */
    if (keynote_temp_list != NULL)
    {
	ret = keynote_env_lookup(s, &keynote_temp_list, 1);
	if (ret != NULL)
	  return ret;
	else
	  if (keynote_errno != 0)
	    return NULL;
    }

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

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

    /* Regex table */
    if ((ks != NULL) && (ks->ks_env_regex != NULL))
    {
	ret = keynote_env_lookup(s, &(ks->ks_env_regex), 1);
	if (ret != NULL)
	{
	    keynote_used_variable = 1;
	    return ret;
	}

	return NULL;
    }

    return NULL;
}

/*
 * 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((unsigned char)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 = calloc(i, sizeof(int));
    if (keynote_kth_array == 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 != NULL)
    {
	free(keynote_kth_array);
	keynote_kth_array = NULL;
    }
}

void
knerror(char *s)
{}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: keynote.y,v 1.18 2017/04/27 15:35:36 millert Exp $ */
2			/*
3			* The author of this code is Angelos D. Keromytis (angelos@dsl.cis.upenn.edu)
4			*
5			* This code was written by Angelos D. Keromytis in Philadelphia, PA, USA,
6			* in April-May 1998
7			*
8			* Copyright (C) 1998, 1999 by Angelos D. Keromytis.
9			*
10			* Permission to use, copy, and modify this software with or without fee
11			* is hereby granted, provided that this entire notice is included in
12			* all copies of any software which is or includes a copy or
13			* modification of this software.
14			*
15			* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR
16			* IMPLIED WARRANTY. IN PARTICULAR, THE AUTHORS MAKES NO
17			* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE
18			* MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR
19			* PURPOSE.
20			*/
21			%union {
22			char *string;
23			double doubval;
24			int intval;
25			int bool;
26			};
27			%type <bool> stringexp numexp expr floatexp
28			%type <intval> NUM KOF numex afterhint notemptyprog
29			%type <intval> notemptykeypredicate prog key keyexp keylist
30			%type <doubval> FLOAT floatex
31			%type <string> STRING VARIABLE str strnotconcat
32			%token TRUE FALSE NUM FLOAT STRING VARIABLE
33			%token OPENPAREN CLOSEPAREN EQQ COMMA ACTSTR LOCINI KOF KEYPRE KNVERSION
34			%token DOTT SIGNERKEY HINT OPENBLOCK CLOSEBLOCK SIGNATUREENTRY PRIVATEKEY
35			%token SEMICOLON TRUE FALSE
36			%nonassoc EQ NE LT GT LE GE REGEXP
37			%left OR
38			%left AND
39			%right NOT
40			%left PLUS MINUS DOTT
41			%left MULT DIV MOD
42			%left EXP
43			%nonassoc UNARYMINUS DEREF OPENNUM OPENFLT
44			%start grammarswitch
45			%{
46			#include <sys/types.h>
47
48			#include <ctype.h>
49			#include <math.h>
50			#include <regex.h>
51			#include <stdio.h>
52			#include <stdlib.h>
53			#include <string.h>
54
55			#include "keynote.h"
56			#include "assertion.h"
57
58			static int *keynote_kth_array = NULL;
59			static int keylistcount = 0;
60
61			static int resolve_assertion(char *);
62			static int keynote_init_kth(void);
63			static int isfloatstring(char *);
64			static int checkexception(int);
65			static char my_lookup(char );
66			static int intpow(int, int);
67			static int get_kth(int);
68			%}
69			%%
70
71			grammarswitch: LOCINI { keynote_exceptionflag = keynote_donteval = 0; }
72			localinit
73			\| ACTSTR { keynote_exceptionflag = keynote_donteval = 0; } program
74			\| KEYPRE { keynote_exceptionflag = keynote_donteval = 0; }
75			keypredicate
76			\| SIGNERKEY { keynote_exceptionflag = keynote_donteval = 0; } key
77			\| SIGNATUREENTRY { keynote_exceptionflag = keynote_donteval = 0; }
78			key
79			\| KNVERSION { keynote_exceptionflag = keynote_donteval = 0; }
80			STRING { keynote_lex_remove($3);
81			if (strcmp($3, KEYNOTE_VERSION_STRING))
82			keynote_errno = ERROR_SYNTAX;
83			free($3);
84			}
85			\| PRIVATEKEY { keynote_exceptionflag = keynote_donteval = 0; }
86			STRING { keynote_lex_remove($3);
87			keynote_privkey = $3;
88			}
89
90			keypredicate: /* Nothing */ { keynote_returnvalue = 0;
91			return 0;
92			}
93			\| notemptykeypredicate { keynote_returnvalue = $1;
94			return 0;
95			}
96
97			notemptykeypredicate: key { $$ = $1; }
98			\| keyexp { $$ = $1; }
99
100			keyexp: notemptykeypredicate AND { if (($1 == 0) && !keynote_justrecord)
101			keynote_donteval = 1;
102			} notemptykeypredicate
103			{ if ($1 > $4)
104			$$ = $4;
105			else
106			$$ = $1;
107			keynote_donteval = 0;
108			} /* Min */
109			\| notemptykeypredicate OR { if (($1 == (keynote_current_session->ks_values_num - 1)) && !keynote_justrecord)
110			keynote_donteval = 1;
111			} notemptykeypredicate
112			{ if ($1 >= $4)
113			$$ = $1;
114			else
115			$$ = $4;
116			keynote_donteval = 0;
117			} /* Max */
118			\| OPENPAREN keyexp CLOSEPAREN { $$ = $2; }
119			\| KOF { keylistcount = 0; } OPENPAREN {
120			if (!keynote_justrecord && !keynote_donteval)
121			if (keynote_init_kth() == -1)
122			return -1;
123			} keylist CLOSEPAREN
124			{
125			if (keylistcount < $1)
126			{
127			keynote_errno = ERROR_SYNTAX;
128			return -1;
129			}
130
131			if (!keynote_justrecord && !keynote_donteval)
132			$$ = get_kth($1);
133			else
134			$$ = 0;
135			} /* K-th */
136
137			keylist: key
138			{ /* Don't do anything if we're just recording */
139			if (!keynote_justrecord && !keynote_donteval)
140			if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0))
141			keynote_kth_array[$1]++;
142
143			keylistcount++;
144			}
145			\| key COMMA keylist
146			{ /* Don't do anything if we're just recording */
147			if (!keynote_justrecord && !keynote_donteval)
148			if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0))
149			keynote_kth_array[$1]++;
150
151			keylistcount++;
152			}
153
154			key: str {
155			if (keynote_donteval)
156			$$ = 0;
157			else
158			{
159			keynote_lex_remove($1);
160			if (keynote_justrecord)
161			{
162			if (keynote_keylist_add(&keynote_keypred_keylist,
163			$1) == -1)
164			{
165			free($1);
166			return -1;
167			}
168
169			$$ = 0;
170			}
171			else
172			switch (keynote_in_action_authorizers($1, KEYNOTE_ALGORITHM_UNSPEC))
173			{
174			case -1:
175			free($1);
176			return -1;
177
178			case RESULT_TRUE:
179			free($1);
180			$$ = keynote_current_session->ks_values_num -
181			1;
182			break;
183
184			default:
185			$$ = resolve_assertion($1);
186			free($1);
187			break;
188			}
189			}
190			}
191
192			localinit: /* Nothing */
193			\| localconstants
194
195			localconstants: VARIABLE EQQ STRING
196			{
197			int i;
198
199			keynote_lex_remove($1);
200			keynote_lex_remove($3);
201
202			/*
203			* Variable names starting with underscores are illegal here.
204			*/
205			if ($1[0] == '_')
206			{
207			free($1);
208			free($3);
209			keynote_errno = ERROR_SYNTAX;
210			return -1;
211			}
212
213			/* If the identifier already exists, report error. */
214			if (keynote_env_lookup($1, &keynote_init_list, 1) != NULL)
215			{
216			free($1);
217			free($3);
218			keynote_errno = ERROR_SYNTAX;
219			return -1;
220			}
221
222			i = keynote_env_add($1, $3, &keynote_init_list, 1, 0);
223			free($1);
224			free($3);
225
226			if (i != RESULT_TRUE)
227			return -1;
228			}
229			\| VARIABLE EQQ STRING
230			{
231			int i;
232
233			keynote_lex_remove($1);
234			keynote_lex_remove($3);
235
236			/*
237			* Variable names starting with underscores are illegal here.
238			*/
239			if ($1[0] == '_')
240			{
241			free($1);
242			free($3);
243			keynote_errno = ERROR_SYNTAX;
244			return -1;
245			}
246
247			/* If the identifier already exists, report error. */
248			if (keynote_env_lookup($1, &keynote_init_list, 1) != NULL)
249			{
250			free($1);
251			free($3);
252			keynote_errno = ERROR_SYNTAX;
253			return -1;
254			}
255
256			i = keynote_env_add($1, $3, &keynote_init_list, 1, 0);
257			free($1);
258			free($3);
259
260			if (i != RESULT_TRUE)
261			return -1;
262			} localconstants
263
264			program: prog {
265			keynote_returnvalue = $1;
266			return 0;
267			}
268
269			prog: /* Nada */ { $$ = 0; }
270			\| notemptyprog {
271			/*
272			* Cleanup envlist of additions such as
273			* regexp results
274			*/
275			keynote_env_cleanup(&keynote_temp_list, 1);
276			} SEMICOLON prog
277			{
278			if ($1 > $4)
279			$$ = $1;
280			else
281			$$ = $4;
282			}
283
284			notemptyprog: expr HINT afterhint
285			{
286			if (checkexception($1))
287			$$ = $3;
288			else
289			$$ = 0;
290			}
291			\| expr
292			{
293			if (checkexception($1))
294			$$ = keynote_current_session->ks_values_num - 1;
295			else
296			$$ = 0;
297			}
298
299			afterhint: str { if (keynote_exceptionflag \|\| keynote_donteval)
300			$$ = 0;
301			else
302			{
303			keynote_lex_remove($1);
304
305			$$ = keynote_retindex($1);
306			if ($$ == -1) /* Invalid return value */
307			$$ = 0;
308
309			free($1);
310			}
311			}
312			\| OPENBLOCK prog CLOSEBLOCK { $$ = $2; }
313
314
315			expr: OPENPAREN expr CLOSEPAREN { $$ = $2; }
316			\| expr AND { if ($1 == 0)
317			keynote_donteval = 1;
318			} expr { $$ = ($1 && $4);
319			keynote_donteval = 0;
320			}
321			\| expr OR { if ($1)
322			keynote_donteval = 1;
323			} expr { $$ = ($1 \|\| $4);
324			keynote_donteval = 0;
325			}
326			\| NOT expr { $$ = !($2); }
327			\| numexp { $$ = $1; }
328			\| floatexp { $$ = $1; }
329			\| stringexp { $$ = $1; }
330			\| TRUE { $$ = 1; }
331			\| FALSE { $$ = 0; }
332
333			numexp: numex LT numex { $$ = $1 < $3; }
334			\| numex GT numex { $$ = $1 > $3; }
335			\| numex EQ numex { $$ = $1 == $3; }
336			\| numex LE numex { $$ = $1 <= $3; }
337			\| numex GE numex { $$ = $1 >= $3; }
338			\| numex NE numex { $$ = $1 != $3; }
339
340			floatexp: floatex LT floatex { $$ = $1 < $3; }
341			\| floatex GT floatex { $$ = $1 > $3; }
342			\| floatex LE floatex { $$ = $1 <= $3; }
343			\| floatex GE floatex { $$ = $1 >= $3; }
344
345			numex: numex PLUS numex { $$ = $1 + $3; }
346			\| numex MINUS numex { $$ = $1 - $3; }
347			\| numex MULT numex { $$ = $1 * $3; }
348			\| numex DIV numex { if ($3 == 0)
349			{
350			if (!keynote_donteval)
351			keynote_exceptionflag = 1;
352			}
353			else
354			$$ = ($1 / $3);
355			}
356			\| numex MOD numex { if ($3 == 0)
357			{
358			if (!keynote_donteval)
359			keynote_exceptionflag = 1;
360			}
361			else
362			$$ = $1 % $3;
363			}
364			\| numex EXP numex { $$ = intpow($1, $3); }
365			\| MINUS numex %prec UNARYMINUS { $$ = -($2); }
366			\| OPENPAREN numex CLOSEPAREN { $$ = $2; }
367			\| NUM { $$ = $1; }
368			\| OPENNUM strnotconcat { if (keynote_exceptionflag \|\|
369			keynote_donteval)
370			$$ = 0;
371			else
372			{
373			keynote_lex_remove($2);
374
375			if (!isfloatstring($2))
376			$$ = 0;
377			else
378			$$ = (int) floor(atof($2));
379			free($2);
380			}
381			}
382
383			floatex: floatex PLUS floatex { $$ = ($1 + $3); }
384			\| floatex MINUS floatex { $$ = ($1 - $3); }
385			\| floatex MULT floatex { $$ = ($1 * $3); }
386			\| floatex DIV floatex { if ($3 == 0)
387			{
388			if (!keynote_donteval)
389			keynote_exceptionflag = 1;
390			}
391			else
392			$$ = ($1 / $3);
393			}
394			\| floatex EXP floatex { if (!keynote_exceptionflag &&
395			!keynote_donteval)
396			$$ = pow($1, $3);
397			}
398			\| MINUS floatex %prec UNARYMINUS { $$ = -($2); }
399			\| OPENPAREN floatex CLOSEPAREN { $$ = $2; }
400			\| FLOAT { $$ = $1; }
401			\| OPENFLT strnotconcat {
402			if (keynote_exceptionflag \|\|
403			keynote_donteval)
404			$$ = 0.0;
405			else
406			{
407			keynote_lex_remove($2);
408
409			if (!isfloatstring($2))
410			$$ = 0.0;
411			else
412			$$ = atof($2);
413			free($2);
414			}
415			}
416
417			stringexp: str EQ str {
418			if (keynote_exceptionflag \|\| keynote_donteval)
419			$$ = 0;
420			else
421			{
422			$$ = strcmp($1, $3) == 0 ? 1 : 0;
423			keynote_lex_remove($1);
424			keynote_lex_remove($3);
425			free($1);
426			free($3);
427			}
428			}
429			\| str NE str {
430			if (keynote_exceptionflag \|\| keynote_donteval)
431			$$ = 0;
432			else
433			{
434			$$ = strcmp($1, $3) != 0 ? 1 : 0;
435			keynote_lex_remove($1);
436			keynote_lex_remove($3);
437			free($1);
438			free($3);
439			}
440			}
441			\| str LT str {
442			if (keynote_exceptionflag \|\| keynote_donteval)
443			$$ = 0;
444			else
445			{
446			$$ = strcmp($1, $3) < 0 ? 1 : 0;
447			keynote_lex_remove($1);
448			keynote_lex_remove($3);
449			free($1);
450			free($3);
451			}
452			}
453			\| str GT str {
454			if (keynote_exceptionflag \|\| keynote_donteval)
455			$$ = 0;
456			else
457			{
458			$$ = strcmp($1, $3) > 0 ? 1 : 0;
459			keynote_lex_remove($1);
460			keynote_lex_remove($3);
461			free($1);
462			free($3);
463			}
464			}
465			\| str LE str {
466			if (keynote_exceptionflag \|\| keynote_donteval)
467			$$ = 0;
468			else
469			{
470			$$ = strcmp($1, $3) <= 0 ? 1 : 0;
471			keynote_lex_remove($1);
472			keynote_lex_remove($3);
473			free($1);
474			free($3);
475			}
476			}
477			\| str GE str {
478			if (keynote_exceptionflag \|\| keynote_donteval)
479			$$ = 0;
480			else
481			{
482			$$ = strcmp($1, $3) >= 0 ? 1 : 0;
483			keynote_lex_remove($1);
484			keynote_lex_remove($3);
485			free($1);
486			free($3);
487			}
488			}
489			\| str REGEXP str
490			{
491			regmatch_t pmatch[32];
492			char grp[10], *gr;
493			regex_t preg;
494			int i;
495
496			if (keynote_exceptionflag \|\| keynote_donteval)
497			$$ = 0;
498			else
499			{
500			keynote_lex_remove($1);
501			keynote_lex_remove($3);
502
503			memset(pmatch, 0, sizeof(pmatch));
504			memset(grp, 0, sizeof(grp));
505
506			if (regcomp(&preg, $3, REG_EXTENDED))
507			{
508			free($1);
509			free($3);
510			keynote_exceptionflag = 1;
511			}
512			else
513			{
514			/* Clean-up residuals from previous regexps */
515			keynote_env_cleanup(&keynote_temp_list, 1);
516
517			free($3);
518			i = regexec(&preg, $1, 32, pmatch, 0);
519			$$ = (i == 0 ? 1 : 0);
520			if (i == 0)
521			{
522			snprintf(grp, sizeof grp, "%lu",
523			(unsigned long)preg.re_nsub);
524			if (keynote_env_add("_0", grp, &keynote_temp_list,
525			1, 0) != RESULT_TRUE)
526			{
527			free($1);
528			regfree(&preg);
529			return -1;
530			}
531
532			for (i = 1; i < 32 && pmatch[i].rm_so != -1; i++)
533			{
534			gr = calloc(pmatch[i].rm_eo - pmatch[i].rm_so +
535			1, sizeof(char));
536			if (gr == NULL)
537			{
538			free($1);
539			regfree(&preg);
540			keynote_errno = ERROR_MEMORY;
541			return -1;
542			}
543
544			strncpy(gr, $1 + pmatch[i].rm_so,
545			pmatch[i].rm_eo - pmatch[i].rm_so);
546			gr[pmatch[i].rm_eo - pmatch[i].rm_so] = '\0';
547			snprintf(grp, sizeof grp, "_%d", i);
548			if (keynote_env_add(grp, gr, &keynote_temp_list,
549			1, 0) == -1)
550			{
551			free($1);
552			regfree(&preg);
553			free(gr);
554			return -1;
555			}
556			else
557			free(gr);
558			}
559			}
560
561			regfree(&preg);
562			free($1);
563			}
564			}
565			}
566
567			str: str DOTT str { if (keynote_exceptionflag \|\| keynote_donteval)
568			$$ = NULL;
569			else
570			{
571			int len = strlen($1) + strlen($3) + 1;
572			$$ = calloc(len, sizeof(char));
573			keynote_lex_remove($1);
574			keynote_lex_remove($3);
575			if ($$ == NULL)
576			{
577			free($1);
578			free($3);
579			keynote_errno = ERROR_MEMORY;
580			return -1;
581			}
582			snprintf($$, len, "%s%s", $1, $3);
583			free($1);
584			free($3);
585			if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
586			return -1;
587			}
588			}
589			\| strnotconcat { $$ = $1; }
590
591			strnotconcat: STRING { $$ = $1; }
592			\| OPENPAREN str CLOSEPAREN { $$ = $2; }
593			\| VARIABLE { if (keynote_exceptionflag \|\| keynote_donteval)
594			$$ = NULL;
595			else
596			{
597			$$ = my_lookup($1);
598			keynote_lex_remove($1);
599			free($1);
600			if ($$ == NULL)
601			{
602			if (keynote_errno)
603			return -1;
604			$$ = strdup("");
605			}
606			else
607			$$ = strdup($$);
608
609			if ($$ == NULL)
610			{
611			keynote_errno = ERROR_MEMORY;
612			return -1;
613			}
614
615			if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
616			return -1;
617			}
618			}
619			\| DEREF str { if (keynote_exceptionflag \|\| keynote_donteval)
620			$$ = NULL;
621			else
622			{
623			$$ = my_lookup($2);
624			keynote_lex_remove($2);
625			free($2);
626			if ($$ == NULL)
627			{
628			if (keynote_errno)
629			return -1;
630			$$ = strdup("");
631			}
632			else
633			$$ = strdup($$);
634
635			if ($$ == NULL)
636			{
637			keynote_errno = ERROR_MEMORY;
638			return -1;
639			}
640
641			if (keynote_lex_add($$, LEXTYPE_CHAR) == -1)
642			return -1;
643			}
644			}
645			%%
646
647			/*
648			* Find all assertions signed by s and give us the one with the highest
649			* return value.
650			*/
651			static int
652			resolve_assertion(char *s)
653			{
654			int i, alg = KEYNOTE_ALGORITHM_NONE, p = 0;
655			void key = (void ) s;
656			struct assertion *as;
657			struct keylist *kl;
658
659			kl = keynote_keylist_find(keynote_current_assertion->as_keylist, s);
660			if (kl != NULL)
661			{
662			alg = kl->key_alg;
663			key = kl->key_key;
664			}
665
666			for (i = 0;; i++)
667			{
668			as = keynote_find_assertion(key, i, alg);
669			if (as == NULL) /* Gone through all of them */
670			return p;
671
672			if (as->as_kresult == KRESULT_DONE)
673			if (p < as->as_result)
674			p = as->as_result;
675
676			/* Short circuit if we find an assertion with maximum return value */
677			if (p == (keynote_current_session->ks_values_num - 1))
678			return p;
679			}
680
681			return 0;
682			}
683
684			/*
685			* Environment variable lookup.
686			*/
687			static char *
688			my_lookup(char *s)
689			{
690			struct keynote_session *ks = keynote_current_session;
691			char *ret;
692
693			if (!strcmp(s, "_MIN_TRUST"))
694			{
695			keynote_used_variable = 1;
696			return ks->ks_values[0];
697			}
698			else
699			{
700			if (!strcmp(s, "_MAX_TRUST"))
701			{
702			keynote_used_variable = 1;
703			return ks->ks_values[ks->ks_values_num - 1];
704			}
705			else
706			{
707			if (!strcmp(s, "_VALUES"))
708			{
709			keynote_used_variable = 1;
710			return keynote_env_lookup("_VALUES", ks->ks_env_table,
711			HASHTABLESIZE);
712			}
713			else
714			{
715			if (!strcmp(s, "_ACTION_AUTHORIZERS"))
716			{
717			keynote_used_variable = 1;
718			return keynote_env_lookup("_ACTION_AUTHORIZERS",
719			ks->ks_env_table, HASHTABLESIZE);
720			}
721			}
722			}
723			}
724
725			/* Temporary list (regexp results) */
726			if (keynote_temp_list != NULL)
727			{
728			ret = keynote_env_lookup(s, &keynote_temp_list, 1);
729			if (ret != NULL)
730			return ret;
731			else
732			if (keynote_errno != 0)
733			return NULL;
734			}
735
736			/* Local-Constants */
737			if (keynote_init_list != NULL)
738			{
739			ret = keynote_env_lookup(s, &keynote_init_list, 1);
740			if (ret != NULL)
741			return ret;
742			else
743			if (keynote_errno != 0)
744			return NULL;
745			}
746
747			if (ks != NULL)
748			{
749			/* Action environment */
750			ret = keynote_env_lookup(s, ks->ks_env_table, HASHTABLESIZE);
751			if (ret != NULL)
752			{
753			keynote_used_variable = 1;
754			return ret;
755			}
756			else
757			if (keynote_errno != 0)
758			return NULL;
759			}
760
761			/* Regex table */
762			if ((ks != NULL) && (ks->ks_env_regex != NULL))
763			{
764			ret = keynote_env_lookup(s, &(ks->ks_env_regex), 1);
765			if (ret != NULL)
766			{
767			keynote_used_variable = 1;
768			return ret;
769			}
770
771			return NULL;
772			}
773
774			return NULL;
775			}
776
777			/*
778			* If we had an exception, the boolean expression should return false.
779			* Otherwise, return the result of the expression (the argument).
780			*/
781			static int
782			checkexception(int i)
783			{
784			if (keynote_exceptionflag)
785			{
786			keynote_exceptionflag = 0;
787			return 0;
788			}
789			else
790			return i;
791			}
792
793
794			/*
795			* Integer exponentation -- copied from Schneier's AC2, page 244.
796			*/
797			static int
798			intpow(int x, int y)
799			{
800			int s = 1;
801
802			/*
803			* x^y with y < 0 is equivalent to 1/(x^y), which for
804			* integer arithmetic is 0.
805			*/
806			if (y < 0)
807			return 0;
808
809			while (y)
810			{
811			if (y & 1)
812			s *= x;
813
814			y >>= 1;
815			x *= x;
816			}
817
818			return s;
819			}
820
821			/*
822			* Check whether the string is a floating point number.
823			*/
824			static int
825			isfloatstring(char *s)
826			{
827			int i, point = 0;
828
829			for (i = strlen(s) - 1; i >= 0; i--)
830			if (!isdigit((unsigned char)s[i]))
831			{
832			if (s[i] == '.')
833			{
834			if (point == 1)
835			return 0;
836			else
837			point = 1;
838			}
839			else
840			return 0;
841			}
842
843			return 1;
844			}
845
846			/*
847			* Initialize array for threshold search.
848			*/
849			static int
850			keynote_init_kth(void)
851			{
852			int i = keynote_current_session->ks_values_num;
853
854			if (i == -1)
855			return -1;
856
857			keynote_kth_array = calloc(i, sizeof(int));
858			if (keynote_kth_array == NULL)
859			{
860			keynote_errno = ERROR_MEMORY;
861			return -1;
862			}
863
864			return RESULT_TRUE;
865			}
866
867			/*
868			* Get the k-th best return value.
869			*/
870			static int
871			get_kth(int k)
872			{
873			int i;
874
875			for (i = keynote_current_session->ks_values_num - 1; i >= 0; i--)
876			{
877			k -= keynote_kth_array[i];
878
879			if (k <= 0)
880			return i;
881			}
882
883			return 0;
884			}
885
886			/*
887			* Cleanup array.
888			*/
889			void
890			keynote_cleanup_kth(void)
891			{
892			if (keynote_kth_array != NULL)
893			{
894			free(keynote_kth_array);
895			keynote_kth_array = NULL;
896			}
897			}
898
899			void
900			knerror(char *s)
901			{}