---

pdl_rule.c

Go to the documentation of this file.

/*
 *   Copyright (c) 2003 EU DataGrid        http://www.eu-datagrid.org/
 *
 *   $Id: pdl_rule.c,v 1.19 2003/09/04 13:47:35 martijn Exp $
 *
 *   Copyright (c) 2003 by
 *      G.M. Venekamp <venekamp@nikhef.nl>
 *      NIKHEF Amsterdam, the Netherlands
 *
 *   This software is distributed under a BSD-style open source
 *   licence. For a complete description of the licence take a look
 *   at: http://eu-datagrid.web.cern.ch/eu-datagrid/license.html
 *
 */


#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lcmaps_log.h"
#include "pdl_rule.h"
#include "pdl_policy.h"
#include "pdl_variable.h"

const rule_t *top_rule=0;
rule_t *last_rule=0;
static BOOL add_new_rules = TRUE;

rule_t* _add_rule(const record_t* state, const record_t* true_branch, const record_t* false_branch);
const rule_t* find_state(const rule_t* rule, const char* state);
recursion_t has_recursion(const rule_t* rule, int* list, int unsigned depth, unsigned int* seen_rules);
int find_insert_position(const int* list, const int rule_number, unsigned int high);
unsigned int rule_number(const rule_t* rule);
BOOL make_list(int* new_list, const int* list, const int rule_number, const unsigned int depth);
unsigned int count_rules(const rule_t* rule);
void update_list(unsigned int* rules, unsigned int rule);
const rule_t* get_rule_number(unsigned int rule_num);


void start_new_rules(void)
{
  //  lcmaps_log_debug(1, "start_new_rule: starting new rules.\n");
  top_rule = last_rule = 0;
}


void allow_new_rules(BOOL allow)
{
  add_new_rules = allow;
}


rule_t* add_rule(record_t* state, record_t* true_branch,
                 record_t* false_branch)
{
  /*
   *  This is for a somewhat dirty hack.
   *
   *  The yacc parser cannot determine the end of expression of the 
   *  form 'a -> b'. This is because 'a -> b' might be followed
   *  by '| c'. Therefore, yacc continues to scan on the next line.
   *  Lex on the other hand simply looks at new lines and increases
   *  the line counter each time it sees one. When an error needs
   *  to be reported, the global line number might be advanced too
   *  far. To counter act this problem, the state variable contains
   *  the right line number, i.e. the line where the current rule
   *  was started. By setting the the global lineno variable to the
   *  correct line number; doing out stuff; and finally setting back
   *  the lineno variable to its original value, we circumvent the
   *  problem of misreported line nubmers.
   */
  rule_t* rule = 0;

  if (!(rule = _add_rule(state, true_branch, false_branch))) {
    free(state->string);
    if (true_branch)  free(true_branch->string);
    if (false_branch) free(false_branch->string);
  }

  free(state);
  if (true_branch)  free(true_branch);
  if (false_branch) free(false_branch);

  return rule;
}


rule_t* _add_rule(const record_t* state, const record_t* true_branch,
                  const record_t* false_branch)
{
  rule_t* rule;
  policy_t* policy;

  if ((policy = find_policy(state->string))) {
    warning(PDL_ERROR, "Left hand side of a rule cannot be a policy; see also line %d.", policy->lineno);
    return 0;
  }

  //  cast away constness.
  if ((rule = (rule_t*)find_state(top_rule, state->string))) {
    warning(PDL_ERROR, "State '%s' is already in use. See line %d.\n", state->string, rule->lineno);
    return 0;
  }

  if ((true_branch && (policy = find_policy(true_branch->string)))
      || (false_branch && (policy = find_policy(false_branch->string))))
    warning(PDL_ERROR, "Rule contians reference to a policy. This is currently not supported.");
  /*  Do not return 0 if a warning has been issued. Ignore the fact that  *
   *  a policy rule has been used. Use its name as a module instead.      */

  //  Check if we just needed to check the rule for errors, or
  //  add the rule after checking as well.
  if (!add_new_rules)
    return 0;

  if (!(rule = (rule_t *)malloc(sizeof(rule_t)))) {
    warning(PDL_ERROR, "out of memory.");
    return 0;
  }

  rule->state        = state->string;
  rule->true_branch  = true_branch  ? true_branch->string  : 0;
  rule->false_branch = false_branch ? false_branch->string : 0;
  rule->lineno       = state->lineno;
  rule->next         = 0;

  if (top_rule)
    last_rule->next = rule;
  else
    top_rule = rule;
  
  last_rule = rule;

  return rule;
}


const rule_t* find_state(const rule_t* rule, const char* state)
{
  if (!rule || !state)
    return 0;

  while (rule && strcmp(state, rule->state))
    rule = rule->next;

  return rule;
}


BOOL check_rule_for_recursion(const rule_t* rule)
{
  unsigned int num_rules = count_rules(rule);
  unsigned int *rules;
  recursion_t rc;
  int i;

  rules = (unsigned int*)calloc((num_rules+1), sizeof(*rules));

  top_rule = rule;

  rc = has_recursion(rule, 0, 0, rules);

  if (rules[0] != num_rules) {
    int j=1;
    for (i=1; i<=num_rules; i++) {
      if (rules[j] != i) {
        lineno = get_rule_number(i-1)->lineno;
        warning(PDL_WARNING, "rule is not part of the chain.");
      } else
        j++;
    }
  }

  free(rules);

  return (rc & RECURSION) ? TRUE : FALSE;
}


unsigned int count_rules(const rule_t* rule)
{
  unsigned int c=0;

  while (rule) {
    c++;
    rule = rule->next;
  }

  return c;
}


const rule_t* get_rule_number(unsigned int rule_num)
{
  unsigned int i;
  const rule_t* r;

  for (i=0, r=top_rule; r && i<rule_num; i++)
    r = r->next;

  return r;
}


recursion_t has_recursion(const rule_t* rule, int* list, unsigned int depth,
                          unsigned int* seen_rules)
{
  unsigned int rule_num;
  recursion_t rc;
  int* new_list = 0;

  ++depth;

  /*
   *  If there is no more rule we have reached the end and hance did
   *  no encounter any recursion.
   */
  if (!rule)
    return NO_RECURSION;

  /*
   *  Allocate memory to hold a new list. The number of elements in
   *  the equals the depth of the tree.
   */
  new_list = (int*)malloc(depth*sizeof(int));
  rc       = NO_RECURSION;
  rule_num = rule_number(rule);

  //  Update the list of visited rules.
  update_list(seen_rules, rule_num);

  /*
   *  First make a new list, this list is based upon the current list.
   *  The list is extended with the current state. If the list cannot
   *  be created, because the current state is already in the list, we
   *  have found recursion and the current path is abandoned.
   */
  if (make_list(new_list, list, rule_num, depth)) {
    //  No recursion yet, keep on looking...
    recursion_t rcl=rc, rcr=rc;

    //  If present, check if the true branch has any recursion.
    if (rule->true_branch) {
      rcl = has_recursion(find_state(top_rule, rule->true_branch), new_list, depth, seen_rules);

      /*
       *  Check the return condition. It tells whether recursion has
       *  been found. If so, it also tells if the recursion has been
       *  reported. This is to prevent multiple error messages on the
       *  same rule for the same path.
       *
       *  NOTE: When the same rule causes a recursion in a different
       *        path, the error is displayed for each of these paths.
       *
       */
      if ((rcl&RECURSION) && !(rcl&RECURSION_HANDLED)) {
        lineno = rule->lineno;
        if (rule->false_branch)
          warning(PDL_ERROR, "rule  %s -> %s | %s causes infinite loop on true transition %s.", rule->state, rule->true_branch, rule->false_branch, rule->true_branch);
        else
          warning(PDL_ERROR, "rule  %s -> %s causes infinite loop on transition %s.", rule->state, rule->true_branch, rule->true_branch);

        /*
         *  Set the handled bit to indicate that the current recursion
         *  has been reported.
         */
        rcl |= RECURSION_HANDLED;
      }
    }
    
    //  If present, check if the false branch has any recursion.
    if (rule->false_branch) {
      rcr = has_recursion(find_state(top_rule, rule->false_branch), new_list, depth, seen_rules);

      if ((rcr&RECURSION) && !(rcr&RECURSION_HANDLED)) {
        lineno = rule->lineno;
        if (rule->true_branch)
          warning(PDL_ERROR, "rule  %s -> %s | %s causes infinite loop on false transition %s.", rule->state, rule->true_branch, rule->false_branch, rule->false_branch);
        else
          warning(PDL_ERROR, "rule ~%s -> %s causes infinite loop on transition %s.", rule->state, rule->false_branch, rule->false_branch);

        rcr |= RECURSION_HANDLED;
      }
    }

    /*
     *  Join the results of both the true branch and false branch
     *  together. This is the result for the current node in the tree.
     */
    rc = rcl|rcr;
  } else
    //  Well, there it is, recursion!
    rc = RECURSION;

  /*
   *  Let's be nice and free the allocated memory to hold the traveled
   *  path.
   */
  free(new_list);

  return rc;
}


unsigned int rule_number(const rule_t* rule)
{
  int n;
  const rule_t* t;

  for (n=0, t=top_rule; t; ++n, t=t->next) {
    if (t==rule) break;
  }

  return n;
}


void update_list(unsigned int* rules, unsigned int rule)
{
  //  Rules in the list start at 1.
  int p = 1 + find_insert_position(rules+1, rule, rules[0]);

  //  Same here, rules in the list start at 1.
  rule++;

  //  Find if the rule number needs to be inserted.
  if (rules[p] != rule) {
    if (p <= rules[0])
      memmove(rules+p+1, rules+p, (1+rules[0]-p)*sizeof(unsigned int));
    rules[p] = rule;

    /*
     *  Do not forget to reflect the fact that a new rule has been
     *  added to the list.
     */
    rules[0]++;
  }
}


int find_insert_position(const int* list, const int rule_number, unsigned int high)
{
  int low=0, mid;

  /*
   *  low and high specify the current part of the list to be
   *  examined. Once the search space has become zero, the insertion
   *  position has been found.
   */
  while (low<high) {
    mid = (low+high)/2;           //  Determine the middle of the list.

    //  Determine on which side of the middle the insertion point lays.
    if (rule_number < list[mid])
      high = mid;
    else
      low = mid + 1;
  }

  //  High points to the correct position now.
  return high;
}


BOOL make_list(int* new_list, const int* list, const int rule_number,
               const unsigned int depth)
{
  int insert;

  if (!list) {
    *new_list = rule_number;
    return TRUE;
  }

  insert = find_insert_position(list, rule_number, depth-1);

  if ((insert>0) && (list[insert-1] == rule_number))
    return FALSE;

  memcpy(new_list, list, insert*sizeof(int));
  if ((depth-insert-1)>0)
    memcpy(new_list+insert+1, list+insert, (depth-insert-1)*sizeof(int));

  new_list[insert] = rule_number;

  return TRUE;
}


void reduce_rule(rule_t* rule)
{
  /*
   *  The state part of the rule can be a variable. It cannot be
   *  another policy rule. Therefore, it can be either reduced
   *  to a variable, or the state part is as it is.
   */
  reduce_to_var(&rule->state, STATE);

  /*
   *  In case of the true branch of a rule, it can be one of three
   *  things:
   *    1 - a variable;
   *    2 - a policy rule;
   *    3 - a state.
   *  Therefore, the value of the true branch is first reduced to
   *  a variable. If not successful, it is reduced to a policy rule;
   *  which is reduced to a set of rules. If it is not a variable or
   *  policy rule, the value is taken as it is.
   */
  reduce_to_var(&rule->true_branch, TRUE_BRANCH);

  //  See comment on the previous statements.
  reduce_to_var(&rule->false_branch, FALSE_BRANCH);
}


const rule_t* get_rule(const char* rule, side_t side)
{
  const rule_t* r = top_rule;

  switch (side) {
  case left_side:
    while (r && (strcmp(r->state, rule)!=0)) {
      r = r->next;
    }
    break;
  case right_side:
    while (r && ((r->true_branch && (strcmp(r->true_branch, rule)!=0)) ||
                ((r->false_branch && strcmp(r->false_branch, rule)!=0)))) {
      r = r->next;
    }
    break;
  default:
    r = 0;
  }

  return r;
}


void show_rules(const rule_t* rule)
{
  while (rule) {
    if (rule->true_branch) {
      if (!rule->false_branch) 
        lcmaps_log_debug(1, " %s -> %s\n", rule->state, rule->true_branch);
      else
        lcmaps_log_debug(1, " %s -> %s | %s\n", rule->state, rule->true_branch, rule->false_branch);
    } else
      lcmaps_log_debug(1, "~%s -> %s\n", rule->state, rule->false_branch);

    rule = rule->next;
  }
}


void free_rules(rule_t* rule)
{
  rule_t* tmp;

  while (rule) {
    tmp = rule->next;
    free((char *)rule->state);
    free((char *)rule->true_branch);
    free((char *)rule->false_branch);
    free((char *)rule);
    rule = tmp;
  }
}


const rule_t* get_top_rule(void)
{
  return top_rule;
}


void set_top_rule(const rule_t* rule)
{
  top_rule = rule;
}

---