← Back to branch summary

~ubuntu-branches/ubuntu/hoary/malaga/hoary

« back to all changes in this revision

Viewing changes to rule_compiler.c

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Bushnell, BSG
  • Date: 2004-08-20 12:58:50 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20040820125850-rx9s8bn0ep8jgist
Tags: 6.13-4
This should have been urgency=high, because it is an important and
long-delayed accomodation to new upstream with a bajillion bug fixes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
rule_compiler.c
 
1
/* Copyright (C) 1995 Bjoern Beutel. */
 
2
 
 
3
/* Description. =============================================================*/
 
4
 
 
5
/* This module compiles Malaga rule files. */
 
6
 
 
7
/* Includes. ================================================================*/
 
8
 
 
9
#include <stdlib.h>
 
10
#include <stdio.h>
 
11
#include <time.h>
 
12
#include <setjmp.h>
 
13
#include "basic.h"
 
14
#include "pools.h"
 
15
#include "values.h"
 
16
#include "scanner.h"
 
17
#include "rule_type.h"
 
18
#include "rule_code.h"
 
19
#include "rule_parser.h"
 
20
#include "rule_symbols.h"
 
21
#include "files.h"
 
22
#include "rule_compiler.h"
 
23
 
 
24
/* Types. ===================================================================*/
 
25
 
 
26
typedef struct /* A rule's first instruction. */
 
27
{ 
 
28
  int_t number; /* The rule number. */
 
29
  int_t first_instr; /* The index of the first instruction. */
 
30
} rule_instr_t;
 
31
 
 
32
typedef struct /* A rule reference, part of a list. */
 
33
{ 
 
34
  list_node_t *next;
 
35
  int_t rule_number; /* The actual rule number. */
 
36
} reference_t;
 
37
 
 
38
/* Functions. ===============================================================*/
 
39
 
 
40
static string_t
 
41
rule_name( int_t rule_index )
 
42
/* Return the rule name of rule RULE_INDEX. */
 
43
{
 
44
  rule_t *rule;
 
45
 
 
46
  rule = pool_item( code.rule_pool, rule_index );
 
47
  return pool_item( code.string_pool, rule->name );
 
48
}
 
49
 
 
50
/*---------------------------------------------------------------------------*/
 
51
 
 
52
static void 
 
53
mark_reachable( bool_t reachable[], list_t *references, int_t rule )
 
54
/* Mark RULE as reachable in the vector REACHABLE. 
 
55
 * If it has not been reachable before, add it to list NEW_RULES. */
 
56
{
 
57
  reference_t *reference;
 
58
 
 
59
  if (reachable[ rule ]) 
 
60
    return;
 
61
  reachable[ rule ] = TRUE;
 
62
  reference = new_node( references, sizeof( reference_t ), LIST_END );
 
63
  reference->rule_number = rule;
 
64
}
 
65
 
 
66
/*---------------------------------------------------------------------------*/
 
67
 
 
68
static void 
 
69
add_reference( list_t *references, int_t rule )
 
70
/* Add a reference to RULE to *REFERENCES if it is not already there. */
 
71
{
 
72
  reference_t *reference;
 
73
 
 
74
  /* Check if a reference to RULE already exists in <*references>. */
 
75
  FOREACH( reference, *references ) 
 
76
  { 
 
77
    if (reference->rule_number == rule) 
 
78
      return;
 
79
  }
 
80
  /* Add a new reference to the front of the list. */
 
81
  reference = new_node( references, sizeof( reference_t ), LIST_END );
 
82
  reference->rule_number = rule;
 
83
}
 
84
 
 
85
/*---------------------------------------------------------------------------*/
 
86
 
 
87
static void 
 
88
check_all_rules_reachable( int_t rule_count, list_t references[] )
 
89
/* Check if every rule can be reached.
 
90
 * REFERENCES[I] is the reference list for rule I, 
 
91
 * i.e., the list of all rules that may be called from rule I. */
 
92
{
 
93
  bool_t *reachable;
 
94
  int_t *rule_set;
 
95
  list_t new_rules;
 
96
  reference_t *reference;
 
97
  string_t name;
 
98
  int_t i;
 
99
 
 
100
  /* Create a vector initialised with FALSE. */
 
101
  reachable = new_vector( sizeof( bool_t ), rule_count );
 
102
  clear_list( &new_rules );
 
103
  if (code.pruning_rule != -1) 
 
104
    mark_reachable( reachable, &new_rules, code.pruning_rule );
 
105
  if (code.robust_rule != -1) 
 
106
    mark_reachable( reachable, &new_rules, code.robust_rule );
 
107
  if (code.allo_rule != -1) 
 
108
    mark_reachable( reachable, &new_rules, code.allo_rule );
 
109
  if (code.input_filter != -1) 
 
110
    mark_reachable( reachable, &new_rules, code.input_filter ); 
 
111
  if (code.output_filter != -1) 
 
112
    mark_reachable( reachable, &new_rules, code.output_filter );
 
113
 
 
114
  /* Mark the initial rules in the REACHABLE vector. */
 
115
  if (code.initial_rule_set != -1) 
 
116
  { 
 
117
    for (rule_set = pool_item( code.rule_set_pool, code.initial_rule_set );
 
118
         *rule_set != -1;
 
119
         rule_set++) 
 
120
    { 
 
121
      if (*rule_set >= 0) 
 
122
        mark_reachable( reachable, &new_rules, *rule_set );
 
123
    }
 
124
  }
 
125
 
 
126
  /* Mark all rules that may be called by other rules. */
 
127
  while (new_rules.first != NULL) 
 
128
  { 
 
129
    i = ((reference_t *) new_rules.first)->rule_number;
 
130
    free_first_node( &new_rules );
 
131
    FOREACH( reference, references[i] ) 
 
132
      mark_reachable( reachable, &new_rules, reference->rule_number );
 
133
  }
 
134
 
 
135
  /* Check if any rule is not reachable. */
 
136
  for (i = 0; i < rule_count; i++) 
 
137
  { 
 
138
    if (! reachable[i]) 
 
139
    {
 
140
      name = rule_name( i );
 
141
      fprintf( stderr, 
 
142
               "Warning: Rule \"%s\" can't be reached. (\"%s\", line %d)\n", 
 
143
               name, name_in_path( get_rule_file( name ) ), 
 
144
               get_rule_line( name ) );
 
145
    }
 
146
  }
 
147
  free_mem( &reachable );
 
148
}
 
149
 
 
150
/*---------------------------------------------------------------------------*/
 
151
 
 
152
static void 
 
153
check_no_circular_calls( int_t rule_count, list_t calls[] )
 
154
/* Check if there are no circular call chains in the rules.
 
155
 * CALLS[I] is the list of subrules that may be called by rule I. */
 
156
{
 
157
  bool_t *reachable;
 
158
  list_t new_rules;
 
159
  int_t n, i;
 
160
  reference_t *called;
 
161
  string_t name;
 
162
 
 
163
  reachable = new_vector( sizeof( bool_t ), rule_count );
 
164
  clear_list( &new_rules );
 
165
 
 
166
  for (n = 0; n < rule_count; n++) 
 
167
  { 
 
168
    /* Mark all rules as unreachable. */
 
169
    for (i = 0; i < rule_count; i++) 
 
170
      reachable[i] = FALSE;
 
171
 
 
172
    /* Mark all rules called from RULE as reachable. */
 
173
    FOREACH( called, calls[n] ) 
 
174
      mark_reachable( reachable, &new_rules, called->rule_number );
 
175
 
 
176
    /* Mark all rules that are called from rules already marked. */
 
177
    while (new_rules.first != NULL) 
 
178
    {
 
179
      i = ((reference_t *) new_rules.first)->rule_number;
 
180
      free_first_node( &new_rules );
 
181
      FOREACH( called, calls[i] ) 
 
182
        mark_reachable( reachable, &new_rules, called->rule_number );
 
183
    }
 
184
 
 
185
    if (reachable[n]) 
 
186
    {
 
187
      name = rule_name( n );
 
188
      fprintf( stderr, 
 
189
               "Warning: Rule \"%s\" is recursive. (\"%s\", line %d)\n", name, 
 
190
               name_in_path( get_rule_file( name ) ), get_rule_line( name ) );
 
191
    }
 
192
  }
 
193
  free_mem( &reachable );
 
194
}
 
195
 
 
196
/*---------------------------------------------------------------------------*/
 
197
 
 
198
static int 
 
199
compare_first_instr( const void *key1, const void *key2 )
 
200
/* Returns (-1/0/1) when the first instruction KEY1 is
 
201
 * (lower than/same as/higher than) the first instruction KEY2. */
 
202
{
 
203
  rule_instr_t *rule_1, *rule_2;
 
204
 
 
205
  rule_1 = (rule_instr_t *) key1;
 
206
  rule_2 = (rule_instr_t *) key2;
 
207
  if (rule_1->first_instr < rule_2->first_instr) 
 
208
    return -1;
 
209
  else if (rule_1->first_instr > rule_2->first_instr) 
 
210
    return 1;
 
211
  else 
 
212
    return 0;
 
213
}
 
214
 
 
215
/*---------------------------------------------------------------------------*/
 
216
 
 
217
static void 
 
218
check_rule_calls( void )
 
219
/* Report a warning if the rules in CODE contain a circular call chain.
 
220
 * Report a warning if a rule can't be reached. */
 
221
{
 
222
  int_t rule_count, i, rule_index, rule_index2;
 
223
  rule_instr_t *rules;
 
224
  list_t *references, *calls; /* Vectors for references and calls. */
 
225
  reference_t *reference;
 
226
  rule_t *rule;
 
227
  instr_t instr;
 
228
  int_t *rule_set;    
 
229
 
 
230
  /* Initialise RULES and sort them for FIRST_INSTR. */
 
231
  rule_count = pool_item_count( code.rule_pool );
 
232
  rules = new_vector( sizeof( rule_instr_t ), rule_count );
 
233
  for (i = 0; i < rule_count; i++) 
 
234
  { 
 
235
    rule = pool_item( code.rule_pool, i );
 
236
    rules[i].number = i;
 
237
    rules[i].first_instr = rule->first_instr;
 
238
  }
 
239
  qsort( rules, rule_count, sizeof( rule_instr_t ), compare_first_instr );
 
240
 
 
241
  /* Allocate a vector of rule references and a vector of calls.
 
242
   * The structs are NULL-initialised, so we don't need to use "clear_list". */
 
243
  references = new_vector( sizeof( list_t ), rule_count );
 
244
  calls = new_vector( sizeof( list_t ), rule_count );
 
245
 
 
246
  /* Fill references. */
 
247
  rule_index = 0;
 
248
  for (i = 0; i < pool_item_count( code.instr_pool ); i++) 
 
249
  { 
 
250
    /* Increment RULE if instruction belongs to next rule. */
 
251
    while (rule_index + 1 < rule_count 
 
252
           && rules[ rule_index + 1 ].first_instr <= i) 
 
253
    {
 
254
      rule_index++;
 
255
    }
 
256
    rule_index2 = rules[ rule_index ].number;
 
257
    instr = *((instr_t *) pool_item( code.instr_pool, i ));
 
258
 
 
259
    /* Check each instruction: is it a add_state instruction? */
 
260
    if (OPCODE( instr ) == INS_ADD_STATE && INSTR_INFO( instr ) != -1) 
 
261
    { 
 
262
      /* Examine the rule set of this result statement. */
 
263
      for (rule_set = pool_item( code.rule_set_pool, INSTR_INFO( instr ) );
 
264
           *rule_set != -1;
 
265
           rule_set++) 
 
266
      { 
 
267
        if (*rule_set >= 0) 
 
268
          add_reference( &references[ rule_index2 ], *rule_set );
 
269
      }
 
270
    } 
 
271
    else if (OPCODE( instr ) == INS_JUMP_SUBRULE) 
 
272
    { 
 
273
      add_reference( &references[ rule_index2 ], INSTR_INFO( instr ) );
 
274
      add_reference( &calls[ rule_index2 ], INSTR_INFO( instr ) );
 
275
    }
 
276
  }
 
277
  check_all_rules_reachable( rule_count, references );
 
278
  check_no_circular_calls( rule_count, calls );
 
279
  free_mem( &rules );
 
280
  for (i = 0; i < rule_count; i++) 
 
281
  { 
 
282
    FOREACH_FREE( reference, references[i] ) 
 
283
      ; /* empty */
 
284
    FOREACH_FREE( reference, calls[i] ) 
 
285
      ; /* empty */
 
286
  }
 
287
  free_mem( &references );
 
288
  free_mem( &calls );
 
289
}
 
290
 
 
291
/*---------------------------------------------------------------------------*/
 
292
 
 
293
void
 
294
compile_rule_file( string_t source_file_name,  string_t object_file_name,
 
295
                   int_t file_type )
 
296
/* Compile file SOURCE_FILE_NAME.
 
297
 * Save compiled data in a file OBJECT_FILE_NAME. */
 
298
{
 
299
  string_t file_name;
 
300
  int_t file_name_index; 
 
301
 
 
302
  init_rule_code( file_type );
 
303
  enter_function( "atoms", FUNC_TO_ATOMS );
 
304
  enter_function( "capital", FUNC_IS_CAPITAL );
 
305
  enter_function( "length", FUNC_GET_LENGTH );
 
306
  enter_function( "multi", FUNC_TO_MULTI );
 
307
  enter_function( "set", FUNC_TO_SET );
 
308
  enter_function( "switch", FUNC_GET_SWITCH );
 
309
  enter_function( "value_type", FUNC_GET_VALUE_TYPE );
 
310
  enter_function( "value_string", FUNC_GET_VALUE_STRING );
 
311
  enter_function( "transmit", FUNC_TRANSMIT );
 
312
  enter_function( "floor", FUNC_FLOOR );
 
313
  enter_function( "substring", FUNC_SUBSTRING );
 
314
 
 
315
  /* Copy file name into string pool. */
 
316
  file_name = copy_string_to_pool( code.string_pool, source_file_name, 
 
317
                                   &file_name_index );
 
318
 
 
319
  /* Parse the rule file (and all included files). */
 
320
  begin_include( file_name );
 
321
  TRY 
 
322
    parse_rule_file();
 
323
  IF_ERROR 
 
324
  { 
 
325
    print_text( error_text, " (\"%s\", line %d, column %d)", 
 
326
                name_in_path( current_file_name() ), current_line_number(),
 
327
                current_column() );
 
328
    if (in_emacs_malaga_mode) 
 
329
    { 
 
330
      printf( "SHOW \"%s\":%d:%d\n", current_file_name(), 
 
331
              current_line_number(), current_column() );
 
332
    }
 
333
  } 
 
334
  FINALLY 
 
335
    end_includes();
 
336
  END_TRY;
 
337
 
 
338
  check_rules_defined(); /* Check if all used rules are also defined. */
 
339
  check_rule_calls(); /* Check for recursive and/or unreachable rules. */
 
340
  dump_variables_and_constants();
 
341
 
 
342
  write_code( object_file_name );
 
343
 
 
344
  free_symbols();
 
345
  terminate_rule_code();
 
346
}
 
347
 
 
348
/* End of file. =============================================================*/