/* Copyright (C) 1995 Bjoern Beutel. */

/* Description. =============================================================*/

/* This module compiles Malaga rule files. */

/* Includes. ================================================================*/

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <setjmp.h>
#include <glib.h>
#include "basic.h"
#include "pools.h"
#include "values.h"
#include "scanner.h"
#include "rule_type.h"
#include "rule_code.h"
#include "rule_parser.h"
#include "rule_symbols.h"
#include "files.h"
#include "rule_compiler.h"

/* Types. ===================================================================*/

typedef struct /* A rule's first instruction. */
{ 
  int_t number; /* The rule number. */
  int_t first_instr; /* The index of the first instruction. */
} rule_instr_t;

typedef struct /* A rule reference, part of a list. */
{ 
  list_node_t *next;
  int_t rule_number; /* The actual rule number. */
} reference_t;

/* Functions. ===============================================================*/

static string_t
rule_name( int_t rule_index )
/* Return the rule name of rule RULE_INDEX. */
{
  rule_t *rule;

  rule = pool_item( code.rule_pool, rule_index );
  return pool_item( code.string_pool, rule->name );
}

/*---------------------------------------------------------------------------*/

static void 
mark_reachable( bool_t reachable[], list_t *references, int_t rule )
/* Mark RULE as reachable in the vector REACHABLE. 
 * If it has not been reachable before, add it to list NEW_RULES. */
{
  reference_t *reference;

  if (reachable[ rule ]) 
    return;
  reachable[ rule ] = TRUE;
  reference = new_node( references, sizeof( reference_t ), LIST_END );
  reference->rule_number = rule;
}

/*---------------------------------------------------------------------------*/

static void 
add_reference( list_t *references, int_t rule )
/* Add a reference to RULE to *REFERENCES if it is not already there. */
{
  reference_t *reference;

  /* Check if a reference to RULE already exists in <*references>. */
  FOREACH( reference, *references ) 
  { 
    if (reference->rule_number == rule) 
      return;
  }
  /* Add a new reference to the front of the list. */
  reference = new_node( references, sizeof( reference_t ), LIST_END );
  reference->rule_number = rule;
}

/*---------------------------------------------------------------------------*/

static void 
check_all_rules_reachable( int_t rule_count, list_t references[] )
/* Check if every rule can be reached.
 * REFERENCES[I] is the reference list for rule	I, 
 * i.e., the list of all rules that may be called from rule I. */
{
  bool_t *reachable;
  int_t *rule_set;
  list_t new_rules;
  reference_t *reference;
  string_t name;
  int_t i;

  /* Create a vector initialised with FALSE. */
  reachable = new_vector( sizeof( bool_t ), rule_count );
  clear_list( &new_rules );
  if (code.pruning_rule != -1) 
    mark_reachable( reachable, &new_rules, code.pruning_rule );
  if (code.robust_rule != -1) 
    mark_reachable( reachable, &new_rules, code.robust_rule );
  if (code.allo_rule != -1) 
    mark_reachable( reachable, &new_rules, code.allo_rule );
  if (code.input_filter != -1) 
    mark_reachable( reachable, &new_rules, code.input_filter ); 
  if (code.output_filter != -1) 
    mark_reachable( reachable, &new_rules, code.output_filter );

  /* Mark the initial rules in the REACHABLE vector. */
  if (code.initial_rule_set != -1) 
  { 
    for (rule_set = pool_item( code.rule_set_pool, code.initial_rule_set );
         *rule_set != -1;
         rule_set++) 
    { 
      if (*rule_set >= 0) 
	mark_reachable( reachable, &new_rules, *rule_set );
    }
  }

  /* Mark all rules that may be called by other rules. */
  while (new_rules.first != NULL) 
  { 
    i = ((reference_t *) new_rules.first)->rule_number;
    free_first_node( &new_rules );
    FOREACH( reference, references[i] ) 
      mark_reachable( reachable, &new_rules, reference->rule_number );
  }

  /* Check if any rule is not reachable. */
  for (i = 0; i < rule_count; i++) 
  { 
    if (! reachable[i]) 
    {
      name = rule_name( i );
      fprintf( stderr, 
	       "Warning: Rule \"%s\" can't be reached. (\"%s\", line %d)\n", 
	       name, name_in_path( get_rule_file( name ) ), 
	       get_rule_line( name ) );
    }
  }
  free_mem( &reachable );
}

/*---------------------------------------------------------------------------*/

static void 
check_no_circular_calls( int_t rule_count, list_t calls[] )
/* Check if there are no circular call chains in the rules.
 * CALLS[I] is the list of subrules that may be called by rule I. */
{
  bool_t *reachable;
  list_t new_rules;
  int_t n, i;
  reference_t *called;
  string_t name;

  reachable = new_vector( sizeof( bool_t ), rule_count );
  clear_list( &new_rules );

  for (n = 0; n < rule_count; n++) 
  { 
    /* Mark all rules as unreachable. */
    for (i = 0; i < rule_count; i++) 
      reachable[i] = FALSE;

    /* Mark all rules called from RULE as reachable. */
    FOREACH( called, calls[n] ) 
      mark_reachable( reachable, &new_rules, called->rule_number );

    /* Mark all rules that are called from rules already marked. */
    while (new_rules.first != NULL) 
    {
      i = ((reference_t *) new_rules.first)->rule_number;
      free_first_node( &new_rules );
      FOREACH( called, calls[i] ) 
	mark_reachable( reachable, &new_rules, called->rule_number );
    }

    if (reachable[n]) 
    {
      name = rule_name( n );
      fprintf( stderr, 
	       "Warning: Rule \"%s\" is recursive. (\"%s\", line %d)\n", name, 
	       name_in_path( get_rule_file( name ) ), get_rule_line( name ) );
    }
  }
  free_mem( &reachable );
}

/*---------------------------------------------------------------------------*/

static int 
compare_first_instr( const void *key1, const void *key2 )
/* Returns (-1/0/1) when the first instruction KEY1 is
 * (lower than/same as/higher than) the first instruction KEY2. */
{
  rule_instr_t *rule_1, *rule_2;

  rule_1 = (rule_instr_t *) key1;
  rule_2 = (rule_instr_t *) key2;
  if (rule_1->first_instr < rule_2->first_instr) 
    return -1;
  else if (rule_1->first_instr > rule_2->first_instr) 
    return 1;
  else 
    return 0;
}

/*---------------------------------------------------------------------------*/

static void 
check_rule_calls( void )
/* Report a warning if the rules in CODE contain a circular call chain.
 * Report a warning if a rule can't be reached. */
{
  int_t rule_count, i, rule_index, rule_index2;
  rule_instr_t *rules;
  list_t *references, *calls; /* Vectors for references and calls. */
  reference_t *reference;
  rule_t *rule;
  instr_t instr;
  int_t *rule_set;    

  /* Initialise RULES and sort them for FIRST_INSTR. */
  rule_count = pool_item_count( code.rule_pool );
  rules = new_vector( sizeof( rule_instr_t ), rule_count );
  for (i = 0; i < rule_count; i++) 
  { 
    rule = pool_item( code.rule_pool, i );
    rules[i].number = i;
    rules[i].first_instr = rule->first_instr;
  }
  qsort( rules, rule_count, sizeof( rule_instr_t ), compare_first_instr );

  /* Allocate a vector of rule references and a vector of calls.
   * The structs are NULL-initialised, so we don't need to use "clear_list". */
  references = new_vector( sizeof( list_t ), rule_count );
  calls = new_vector( sizeof( list_t ), rule_count );

  /* Fill references. */
  rule_index = 0;
  for (i = 0; i < pool_item_count( code.instr_pool ); i++) 
  { 
    /* Increment RULE if instruction belongs to next rule. */
    while (rule_index + 1 < rule_count 
	   && rules[ rule_index + 1 ].first_instr <= i) 
    {
      rule_index++;
    }
    rule_index2 = rules[ rule_index ].number;
    instr = *((instr_t *) pool_item( code.instr_pool, i ));

    /* Check each instruction: is it a add_state instruction? */
    if (OPCODE( instr ) == INS_ADD_STATE && INSTR_INFO( instr ) != -1) 
    { 
      /* Examine the rule set of this result statement. */
      for (rule_set = pool_item( code.rule_set_pool, INSTR_INFO( instr ) );
           *rule_set != -1;
           rule_set++) 
      { 
	if (*rule_set >= 0) 
	  add_reference( &references[ rule_index2 ], *rule_set );
      }
    } 
    else if (OPCODE( instr ) == INS_JUMP_SUBRULE) 
    { 
      add_reference( &references[ rule_index2 ], INSTR_INFO( instr ) );
      add_reference( &calls[ rule_index2 ], INSTR_INFO( instr ) );
    }
  }
  check_all_rules_reachable( rule_count, references );
  check_no_circular_calls( rule_count, calls );
  free_mem( &rules );
  for (i = 0; i < rule_count; i++) 
  { 
    FOREACH_FREE( reference, references[i] ) 
      ; /* empty */
    FOREACH_FREE( reference, calls[i] ) 
      ; /* empty */
  }
  free_mem( &references );
  free_mem( &calls );
}

/*---------------------------------------------------------------------------*/

void
compile_rule_file( string_t source_file_name,  string_t object_file_name,
                   int_t file_type )
/* Compile file SOURCE_FILE_NAME.
 * Save compiled data in a file OBJECT_FILE_NAME. */
{
  string_t file_name;
  int_t file_name_index; 

  init_rule_code( file_type );
  enter_function( "atoms", FUNC_TO_ATOMS );
  enter_function( "capital", FUNC_IS_CAPITAL );
  enter_function( "length", FUNC_GET_LENGTH );
  enter_function( "multi", FUNC_TO_MULTI );
  enter_function( "set", FUNC_TO_SET );
  enter_function( "switch", FUNC_GET_SWITCH );
  enter_function( "value_type", FUNC_GET_VALUE_TYPE );
  enter_function( "value_string", FUNC_GET_VALUE_STRING );
  enter_function( "transmit", FUNC_TRANSMIT );
  enter_function( "floor", FUNC_FLOOR );
  enter_function( "substring", FUNC_SUBSTRING );

  /* Copy file name into string pool. */
  file_name = copy_string_to_pool( code.string_pool, source_file_name, 
				   &file_name_index );

  /* Parse the rule file (and all included files). */
  begin_include( file_name );
  TRY 
    parse_rule_file();
  IF_ERROR 
  { 
    print_text( error_text, " (\"%s\", line %d, column %d)", 
		name_in_path( current_file_name() ), current_line_number(),
		current_column() );
    if (in_emacs_malaga_mode) 
    { 
      printf( "SHOW \"%s\":%d:%d\n", current_file_name(), 
	      current_line_number(), current_column() );
    }
  } 
  FINALLY 
    end_includes();
  END_TRY;

  check_rules_defined(); /* Check if all used rules are also defined. */
  check_rule_calls(); /* Check for recursive and/or unreachable rules. */
  dump_variables_and_constants();

  write_code( object_file_name );

  free_symbols();
  terminate_rule_code();
}

/* End of file. =============================================================*/