nsz Git - libfirm/blob - ir/be/grgen/action.c

   1 /*
   2  * Project:     libFIRM/extension module/GRS-matcher
   3  * File name:   ext/action.c
   4  * Purpose:     funcytions to construct for libfirm grs actions
   5  * Author:      Veit Batz
   6  * Modified by: Andreas Schoesser
   7  * Created:             29. August 2005
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2005 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #include "common_t.h"
  14 #include "action_t.h"
  15
  16
  17 #define ext_grs_PSEUDO_PREFIX "_pseudo__"
  18 #undef MAX
  19 #define MAX(a,b) (a)>=(b) ? (a) : (b)
  20
  21
  22 /* counter to create action ids from */
  23 static int action_counter = 0;
  24
  25 /* obstack to store actions on */
  26 static struct obstack obst;
  27 /* tells whether the obstack has already been initialized */
  28 static int obst_init = 0;
  29
  30
  31
  32 static int not_injective = 0;
  33 static int multiple_entry = 0;
  34 static int already_exists = 0;
  35
  36
  37 /* a pointer to pointer map elem */
  38 typedef struct {
  39         /* kind */
  40         ext_grs_elem_kind_t kind;
  41         /* the preimage */
  42         void *pre;
  43         /* the image */
  44         void *img;
  45 }
  46 ext_grs_ptr_map_entry_t;
  47
  48 int ptr_map_cmp_func(const void *elt, const void *key) {
  49
  50         ext_grs_ptr_map_entry_t *entry1 = (ext_grs_ptr_map_entry_t *) elt;
  51         ext_grs_ptr_map_entry_t *entry2 = (ext_grs_ptr_map_entry_t *) key;
  52
  53         if (entry1->pre != entry2->pre && entry1->img == entry2->img)
  54                 not_injective = 1;
  55
  56         if (entry1->pre == entry2->pre && entry1->img != entry2->img)
  57                 multiple_entry = 1;
  58
  59         if (entry1->pre == entry2->pre && entry1->img == entry2->img)
  60                 already_exists = 1;
  61
  62         return entry1->pre != entry2->pre;
  63 }
  64
  65
  66
  67
  68 static void init_graph(ext_grs_graph_t *graph,
  69 ext_grs_action_t *act, ext_grs_graph_kind_t kind)
  70 {
  71         memset(graph, 0, sizeof(*graph));
  72
  73         graph->kind = kind;
  74         graph->action = act;
  75         LC_INIT_LIST_HEAD(& graph->nodes);
  76         LC_INIT_LIST_HEAD(& graph->edges);
  77 }
  78
  79
  80 /*
  81  *  Copy all nodes into the action and gen pseudo edges
  82  *  modeling the explicit matching of a node
  83  *  PseudoEdge == Edge modelled as a node
  84  */
  85 static int import_graph_info(ext_grs_action_t *action, ext_grs_graph_t *graph)
  86 {
  87         int edge_aiid = action->max_edge_aiid;
  88
  89         lc_list_t *pos, *n;
  90
  91         assert (action->kind != ext_grs_k_replacement &&
  92                 "import_graph_info() is not meant for calling on replacement graphs");
  93
  94
  95         /* init the graphs root node */
  96         graph->root_node.kind = ext_grs_k_pseudo_node;
  97         graph->root_node.graph = graph;
  98         LC_INIT_LIST_HEAD(& graph->root_node.edges[ext_grs_in]);
  99         LC_INIT_LIST_HEAD(& graph->root_node.edges[ext_grs_out]);
 100         graph->root_node.name = ext_grs_PSEUDO_PREFIX "root_node";
 101
 102         lc_list_for_each (pos, & graph->nodes) {
 103
 104                 ext_grs_node_t *node = lc_list_entry(pos, ext_grs_node_t, node_list);
 105                 ext_grs_edge_t *pseudo_edge = obstack_alloc(&obst, sizeof(*pseudo_edge));
 106
 107                 memset(pseudo_edge, 0, sizeof(*pseudo_edge));
 108
 109                 /* store the node in the actions node array */
 110                 if (action->nodes[node->aiid] == NULL) {
 111                         action->nodes[node->aiid] = node;
 112                 }
 113                 else {
 114                         printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 115                         printf("  Multiple assigned node id encountered.\n");
 116                         printf("  You may have added nodes with the same id via ext_grs_act_add_node().\n\n");
 117                         return 0;
 118                 }
 119
 120                 /* for each node setup the pseudo edge modeling the
 121                  * explicit matching of that node */
 122                 pseudo_edge->graph = graph;
 123                 pseudo_edge->kind = ext_grs_k_pseudo_edge;
 124                 pseudo_edge->aiid = ++edge_aiid;
 125                 pseudo_edge->arg = node;
 126                 pseudo_edge->func = & graph->root_node;
 127                 pseudo_edge->genuine_elem.kind = ext_grs_k_node;
 128                 pseudo_edge->genuine_elem.val.n = node;
 129                 pseudo_edge->name = obstack_alloc(
 130                         & obst,
 131                         (1 + strlen(ext_grs_PSEUDO_PREFIX) + strlen(node->name)) * sizeof(char)
 132                 );
 133                 strcpy(pseudo_edge->name, ext_grs_PSEUDO_PREFIX);
 134                 strcat(pseudo_edge->name, node->name);
 135
 136                 /* add the pseudo edge to the graphs edge list */
 137                 lc_list_add(& pseudo_edge->edge_list, & graph->edges);
 138                 /* add the pseudo edge to the tgt- and src-nodes  in- and out-lists */
 139                 lc_list_add(& pseudo_edge->list[ext_grs_in],
 140                         & pseudo_edge->func->edges[ext_grs_in]);
 141                 lc_list_add(& pseudo_edge->list[ext_grs_out],
 142                         & pseudo_edge->arg->edges[ext_grs_out]);
 143                 /* add the pseudo edge to the action */
 144                 action->edges[edge_aiid] = pseudo_edge;
 145         }
 146
 147         /* copy all pattern edges into the action and for every
 148          * edge gen a pseudo edge modeling the traversal of the original edge
 149          * against its direction */
 150         lc_list_for_each_safe (pos, n, & graph->edges) {
 151
 152                 ext_grs_edge_t *edge = lc_list_entry(pos, ext_grs_edge_t, edge_list);
 153                 ext_grs_edge_t *pseudo_edge;
 154
 155                 if (edge->kind == ext_grs_k_pseudo_edge)
 156                         continue;
 157
 158                 pseudo_edge = obstack_alloc(&obst, sizeof(*pseudo_edge));
 159                 memset(pseudo_edge, 0, sizeof(*pseudo_edge));
 160
 161                 /* store the node in the actions node array */
 162                 action->edges[edge->aiid] = edge;
 163
 164                 /* for each edge setup the pseudo edge modelling the
 165                  * against-direction-traversal of that edge  */
 166                 pseudo_edge->graph = edge->graph;
 167                 pseudo_edge->kind = ext_grs_k_pseudo_edge;
 168                 pseudo_edge->aiid = ++edge_aiid;
 169                 pseudo_edge->arg = edge->func;
 170                 pseudo_edge->func = edge->arg;
 171                 pseudo_edge->genuine_elem.kind = ext_grs_k_edge;
 172                 pseudo_edge->genuine_elem.val.e = edge;
 173                 pseudo_edge->name = obstack_alloc(
 174                         & obst,
 175                         (1 + strlen(ext_grs_PSEUDO_PREFIX) + strlen(edge->name)) * sizeof(char)
 176                 );
 177                 strcpy(pseudo_edge->name, ext_grs_PSEUDO_PREFIX);
 178                 strcat(pseudo_edge->name, edge->name);
 179
 180                 /* add the pseudo edge to the graphs edge list */
 181                 lc_list_add(& pseudo_edge->edge_list, & graph->edges);
 182                 /* add the pseudo edge to the tgt- and src-nodes  in- and out-lists */
 183                 lc_list_add(& pseudo_edge->list[ext_grs_in],
 184                         & pseudo_edge->func->edges[ext_grs_in]);
 185                 lc_list_add(& pseudo_edge->list[ext_grs_out],
 186                         & pseudo_edge->arg->edges[ext_grs_out]);
 187                 /* add the pseudo edge to the action */
 188                 action->edges[edge_aiid] = pseudo_edge;
 189                 /* each actual edge knows the respective pseudo edge */
 190                 edge->backward_edge = pseudo_edge;
 191         }
 192
 193         action->max_edge_aiid = edge_aiid;
 194
 195         return 1;
 196 }
 197
 198
 199
 200 static void set_up_condition_stuff(ext_grs_action_t *action) {
 201
 202         lc_list_t *pos;
 203         int i;
 204
 205         /* alloc space for bitsets telling which (pattern or negative) nodes and edges
 206          * are involved in which conditions and vice versa wich conditions are refered
 207          * by which nodes or edges */
 208         action->conditions =
 209                 obstack_alloc(&obst, action->n_conditions * sizeof(*action->conditions));
 210         action->conds_involved_nodes =
 211                 obstack_alloc(&obst, action->n_conditions * sizeof(*action->conds_involved_nodes));
 212         action->conds_involved_edges =
 213                 obstack_alloc(&obst, action->n_conditions * sizeof(*action->conds_involved_edges));
 214
 215         action->nodes_refering_conds =
 216                 obstack_alloc(&obst, (action->max_node_aiid+1) * sizeof(*action->nodes_refering_conds));
 217         action->edges_refering_conds =
 218                 obstack_alloc(&obst, (action->max_edge_aiid+1) * sizeof(*action->edges_refering_conds));
 219
 220         /* alloc a bitset for every (pattern or negative) node and edge */
 221         for(i = 0; i <= action->max_node_aiid; i++)
 222                 action->nodes_refering_conds[i] =
 223                         lc_bitset_obstack_alloc(&obst, action->n_conditions);
 224         for(i = 0; i <= action->max_edge_aiid; i++)
 225                 action->edges_refering_conds[i] =
 226                         lc_bitset_obstack_alloc(&obst, action->n_conditions);
 227
 228         /* alloc two bitset for every condition (telling which nodes and edges are involved),
 229          * and setup the hole condition information */
 230         i = 0;
 231         lc_list_for_each(pos, & action->listed_conditions) {
 232
 233                 int j;
 234                 lc_bitset_t *bs;
 235                 ext_grs_cond_descr_t *cond_descr =
 236                         lc_list_entry(pos, ext_grs_cond_descr_t, condition_list);
 237
 238                 action->conditions[i] = cond_descr->condition;
 239
 240                 /* alloc the bitset, which represents the information about the
 241                  * (pattern or negative) nodes involved in the current condition */
 242                 bs = action->conds_involved_nodes[i] =
 243                                 lc_bitset_obstack_alloc(&obst, action->max_node_aiid+1);
 244
 245                 /* store that info in the bitset */
 246                 for (j = 0; j < cond_descr->n_nodes; j++) {
 247                         int aiid = cond_descr->nodes[j]->aiid;
 248                         lc_bitset_set(bs, aiid);
 249                         lc_bitset_set(action->nodes_refering_conds[aiid], i);   // CRASH!!!
 250                 }
 251
 252                 /* alloc the bitset, which represents the information about the
 253                  * (pattern or negative) edges involved in the current condition */
 254                 bs = action->conds_involved_edges[i] =
 255                                 lc_bitset_obstack_alloc(&obst, action->max_edge_aiid+1);
 256
 257                 /* store that info in the bitset */
 258                 for (j = 0; j < cond_descr->n_edges; j++) {
 259                         int aiid = cond_descr->edges[j]->aiid;
 260                         lc_bitset_set(bs, aiid);
 261                         lc_bitset_set(action->edges_refering_conds[aiid], i);
 262                 }
 263
 264                 i++;
 265         }
 266
 267         assert(i == action->n_conditions && "inconsistent number of registered condition functions");
 268 }
 269
 270
 271
 272
 273
 274 /** create a new graph action of the given kind */
 275 ext_grs_action_t *ext_grs_new_action(ext_grs_action_kind_t kind, char *name) {
 276
 277         ext_grs_action_t *action;
 278
 279         /* allocate a new action */
 280         action = (ext_grs_action_t *) obstack_alloc(&obst, sizeof(*action));
 281         if (action == NULL)     {
 282                 printf("module ext/grs: internal ERROR in function ext_grs_act_allow_nodes_hom()\n");
 283                 printf("  Failed to allocate a new action.\n\n");
 284                 return NULL;
 285         }
 286         memset(action, 0, sizeof(*action));
 287         /* set the actions kind and id */
 288         action->kind = kind;
 289         action->id = action_counter++;
 290         action->name = name;
 291         action->max_node_aiid = -1;
 292         action->max_edge_aiid = -1;
 293         action->max_repl_node_aiid = -1;
 294         action->max_repl_edge_aiid = -1;
 295
 296         LC_INIT_LIST_HEAD(& action->negatives);
 297         LC_INIT_LIST_HEAD(& action->listed_conditions);
 298         LC_INIT_LIST_HEAD(& action->listed_evals);
 299
 300
 301         /* allocate this actions pattern graph */
 302         action->pattern = (ext_grs_graph_t *)
 303                 obstack_alloc(&obst, sizeof(*(action->pattern)));
 304         if (action->pattern == NULL) {
 305                 printf("module ext/grs: internal ERROR in function ext_grs_new_action()\n");
 306                 printf("  Failed to allocate a pattern graph for the new action.\n\n");
 307                 obstack_free(&obst, action);
 308                 return NULL;
 309         }
 310         init_graph(action->pattern, action, ext_grs_k_pattern);
 311
 312         /* if action is a rule, allocate a replacemant graph */
 313         if (kind == ext_grs_k_rule) {
 314                 action->replacement = (ext_grs_graph_t *)
 315                         obstack_alloc(&obst, sizeof(*(action->replacement)));
 316                 if (action->replacement == NULL) {
 317                         printf("module ext/grs: internal ERROR in function ext_grs_new_action()\n");
 318                         printf("  Failed to allocate a replacement graph for the new action.\n\n");
 319                         obstack_free(&obst, action);
 320                         return NULL;
 321                 }
 322                 init_graph(action->replacement, action, ext_grs_k_replacement);
 323         }
 324
 325         action->kept_elems = lc_pset_new(ptr_map_cmp_func, 256);
 326
 327         return action;
 328 }
 329
 330 /** get the kind of an action */
 331 ext_grs_action_kind_t ext_grs_act_get_kind(ext_grs_action_t *act) {
 332         return act->kind;
 333 }
 334
 335 /** impose a new negative graph pattern on the given action */
 336 ext_grs_graph_t *ext_grs_act_impose_negative(ext_grs_action_t *action) {
 337
 338         ext_grs_graph_t *negative;
 339
 340         /* if action is already mature no further changes are allowed */
 341         if (action->mature) return NULL;
 342
 343         /* create new graph */
 344         negative = (ext_grs_graph_t *) obstack_alloc(&obst, sizeof(*negative));
 345         if (negative == NULL) {
 346                 printf("module ext/grs: ERROR in function ext_grs_act_impose_negative()\n");
 347                 printf("  failed to allocate a new action!\n");
 348                 return NULL;
 349         }
 350         init_graph(negative, action, ext_grs_k_negative);
 351
 352         /* store the new graph in the given action
 353          * as a negative pattern graph */
 354         lc_list_add(& negative->negative_list, & action->negatives);
 355
 356         return negative;
 357 }
 358
 359
 360 /** get the pattern graph of an action */
 361 ext_grs_graph_t *ext_grs_act_get_pattern(ext_grs_action_t *action) {
 362         return action->pattern;
 363 }
 364
 365 /** get the replacement graph of an action */
 366 ext_grs_graph_t *ext_grs_act_get_replacement(ext_grs_action_t *action) {
 367
 368         if (action->kind == ext_grs_k_rule) {
 369                 assert (action->replacement->kind == ext_grs_k_replacement &&
 370                         "replacement graph has wrong kind");
 371                 return action->replacement;
 372         }
 373
 374         /* if action is no rule, no replacement can be returned */
 375         return NULL;
 376 }
 377
 378 /** add a node to a given pattern graph */
 379 ext_grs_node_t *ext_grs_act_add_node(
 380         ext_grs_graph_t *graph, char *name, ir_op *op, ir_mode *mode, int id)
 381 {
 382         ext_grs_node_t *new_node;
 383
 384         if (!graph) {
 385                 printf("module ext/grs: ERROR in function ext_grs_add_node()\n");
 386                 printf("  Given graph was NULL!\n");
 387                 return NULL;
 388         }
 389         if (!name) {
 390                 printf("module ext/grs: ERROR in function ext_grs_add_node()\n");
 391                 printf("  Given name was NULL!\n");
 392                 return NULL;
 393         }
 394         if (!op) {
 395                 printf("module ext/grs: ERROR in function ext_grs_add_node()\n");
 396                 printf("  Given op was NULL!\n");
 397                 return NULL;
 398         }
 399         if (!mode) {
 400                 printf("module ext/grs: ERROR in function ext_grs_add_node()\n");
 401                 printf("  Given mode was NULL!\n");
 402                 return NULL;
 403         }
 404         if (id < 0) {
 405                 printf("module ext/grs: ERROR in function ext_grs_add_node()\n");
 406                 printf("  Negative node id was given.\n");
 407                 return NULL;
 408         }
 409         if (graph->action->mature) {
 410                 printf("module ext/grs: ERROR in function ext_grs_add_node()\n");
 411                 printf("  Given graph belongs to a mature action.\n");
 412                 return NULL;
 413         }
 414
 415         new_node = obstack_alloc(&obst, sizeof(*new_node));
 416         memset(new_node, 0, sizeof(*new_node));
 417
 418         new_node->kind = ext_grs_k_node;
 419         new_node->graph = graph;
 420         new_node->name = name;
 421         new_node->mode = mode;
 422         new_node->op = op;
 423         new_node->aiid = id;
 424         new_node->related_node = NULL;
 425         LC_INIT_LIST_HEAD(& new_node->edges[ext_grs_in]);
 426         LC_INIT_LIST_HEAD(& new_node->edges[ext_grs_out]);
 427
 428         /* add node to the graph */
 429         graph->n_nodes++;
 430         lc_list_add(& new_node->node_list, & graph->nodes);
 431
 432         /* add node to the graphs action...? */
 433         /* ...this is done by the the mature function when
 434          * pseudo nodes and edges are created! */
 435
 436         if (graph->kind == ext_grs_k_replacement) {
 437                 graph->action->max_repl_node_aiid = MAX(id, graph->action->max_repl_node_aiid);
 438         }
 439         else {
 440                 assert((graph->kind == ext_grs_k_pattern || graph->kind == ext_grs_k_negative)
 441                         && "given graph has invalid kind");
 442                 graph->action->max_node_aiid = MAX(id, graph->action->max_node_aiid);
 443         }
 444
 445         return new_node;
 446 }
 447
 448 ext_grs_node_t *ext_grs_act_add_related_node(ext_grs_graph_t *graph,
 449                  char *name, ir_op *op, ir_mode *mode, int id, ext_grs_node_t *positive_node)
 450 {
 451         ext_grs_node_t *added_node = ext_grs_act_add_node(graph, name, op, mode, id);
 452         ext_grs_act_relate_neg_node(positive_node, added_node);
 453         return(added_node);
 454 }
 455
 456 ext_grs_node_t *ext_grs_act_add_node_to_keep(ext_grs_graph_t *graph,
 457                                                                                          char *name, ir_op *op, ir_mode *mode, int id, ext_grs_node_t *pattern_node)
 458 {
 459         ext_grs_node_t *added_node = ext_grs_act_add_node(graph, name, op, mode, id);
 460         ext_grs_act_announce_kept_node(pattern_node, added_node);
 461         return(added_node);
 462 }
 463
 464
 465 /** add an edge to a given pattern graph */
 466 ext_grs_edge_t *ext_grs_act_add_edge(ext_grs_graph_t *graph,
 467         char *name, int pos, ext_grs_node_t *arg, ext_grs_node_t *func, int id)
 468 {
 469         ext_grs_edge_t *new_edge;
 470
 471         if (!graph) {
 472                 printf("module ext/grs: ERROR in function ext_grs_add_edge()\n");
 473                 printf("  Given graph was NULL.\n\n");
 474                 return NULL;
 475         }
 476         if (!name) {
 477                 printf("module ext/grs: ERROR in function ext_grs_add_edge()\n");
 478                 printf("  Given name was NULL.\n\n");
 479                 return NULL;
 480         }
 481         if (!arg) {
 482                 printf("module ext/grs: ERROR in function ext_grs_add_edge()\n");
 483                 printf("  Given argument node was NULL.\n\n");
 484                 return NULL;
 485         }
 486         if (!func) {
 487                 printf("module ext/grs: ERROR in function ext_grs_add_edge()\n");
 488                 printf("  Given function node was NULL.\n\n");
 489                 return NULL;
 490         }
 491         if (id < 0) {
 492                 printf("module ext/grs: ERROR in function ext_grs_add_edge()\n");
 493                 printf("  Given edge id was negative.\n\n");
 494                 return NULL;
 495         }
 496         if (graph->action->mature) {
 497                 printf("module ext/grs: ERROR in function ext_grs_add_edge()\n");
 498                 printf("  Tried to add an edge to a graph of a mature action.\n\n");
 499                 return NULL;
 500         }
 501
 502         if (func->op == op_Bad) {
 503                 printf("module ext/grs: WARNING in function ext_grs_add_edge()\n");
 504                 printf("  Added an incoming edge to a Bad node, this leads\n");
 505                 printf("  to a malformed graph.\n\n");
 506         }
 507
 508
 509         new_edge = obstack_alloc(&obst, sizeof(*new_edge));
 510         memset(new_edge, 0, sizeof(*new_edge));
 511
 512         new_edge->kind = ext_grs_k_edge;
 513         new_edge->graph = graph;
 514         new_edge->name = name;
 515         new_edge->pos = pos;
 516         new_edge->func = func;
 517         new_edge->arg = arg;
 518         new_edge->aiid = id;
 519         new_edge->related_edge = 0;
 520
 521         /* add edge to the graph */
 522         graph->n_edges++;
 523         lc_list_add(& new_edge->edge_list, & graph->edges);
 524
 525         /* add edge to tgt- and src-nodes in and out lists */
 526         lc_list_add(&new_edge->list[ext_grs_in], & new_edge->func->edges[ext_grs_in]);
 527         lc_list_add(&new_edge->list[ext_grs_out], & new_edge->arg->edges[ext_grs_out]);
 528
 529         /* add edge to the graphs action...? */
 530         /* ...this is done by the the mature function when
 531          * pseudo nodes and edges are created! */
 532
 533         if (graph->kind == ext_grs_k_replacement) {
 534                 graph->action->max_repl_edge_aiid = MAX(id, graph->action->max_repl_edge_aiid);
 535         }
 536         else {
 537                 assert((graph->kind == ext_grs_k_pattern || graph->kind == ext_grs_k_negative)
 538                         && "given graph has invalid kind");
 539                 graph->action->max_edge_aiid = MAX(id, graph->action->max_edge_aiid);
 540         }
 541
 542         return new_edge;
 543 }
 544
 545 ext_grs_edge_t *ext_grs_act_add_related_edge(ext_grs_graph_t *graph,
 546                                                          char *name, int pos, ext_grs_node_t *arg, ext_grs_node_t *func, int id, ext_grs_edge_t *positive_edge)
 547 {
 548         ext_grs_edge_t *added_edge = ext_grs_act_add_edge(graph, name, pos, arg, func, id);
 549         ext_grs_act_relate_neg_edge(positive_edge, added_edge);
 550         return(added_edge);
 551 }
 552
 553 ext_grs_edge_t *ext_grs_act_add_edge_to_keep(ext_grs_graph_t *graph,
 554                                                                                          char *name, int pos, ext_grs_node_t *arg, ext_grs_node_t *func, int id, ext_grs_edge_t *pattern_edge)
 555 {
 556         ext_grs_edge_t *added_edge = ext_grs_act_add_edge(graph, name, pos, arg, func, id);
 557         ext_grs_act_announce_kept_edge(pattern_edge, added_edge);
 558         return(added_edge);
 559 }
 560
 561 /** mature an action, it is not possible to make any
 562  *  changes to this actions pattern afterwards */
 563
 564 int ext_grs_act_mature(ext_grs_action_t *action) {
 565
 566         int i;
 567         lc_list_t *pos, *pos1;
 568
 569         int n_nodes = 0;
 570         int n_edges = 0;
 571         int n_neg_nodes = 0;
 572         int n_neg_edges = 0;
 573         int n_pseudo_nodes = 0;
 574         int n_pseudo_edges = 0;
 575
 576
 577         if (action->mature) {
 578                 printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 579                 printf("  given action is already mature!\n");
 580                 return 0;
 581         }
 582
 583 /* ................ 1 ................................................. */
 584
 585         /* compute the overall number of real nodes and negative nodes */
 586         n_nodes = action->pattern->n_nodes;
 587         lc_list_for_each(pos, &action->negatives) {
 588                 ext_grs_graph_t *neg =
 589                         lc_list_entry(pos, ext_grs_graph_t, negative_list);
 590                 n_neg_nodes += neg->n_nodes;
 591         }
 592         /* compute the overall number of real edges and negative edges */
 593         n_edges = action->pattern->n_edges;
 594         lc_list_for_each(pos, &action->negatives) {
 595                 ext_grs_graph_t *neg =
 596                         lc_list_entry(pos, ext_grs_graph_t, negative_list);
 597                 n_neg_edges += neg->n_edges;
 598         }
 599
 600         /* alloc space for real and negative nodes */
 601         action->nodes =
 602                 obstack_alloc(&obst, (action->max_node_aiid+1) * sizeof(ext_grs_node_t));
 603         memset(action->nodes, 0 , (action->max_node_aiid+1) * sizeof(ext_grs_node_t));
 604         /* alloc space for real, negative and pseudo edges */
 605         action->edges =
 606                 obstack_alloc(&obst,
 607                         (action->max_edge_aiid+1 + n_nodes + n_neg_nodes + n_edges) * sizeof(ext_grs_edge_t));
 608         memset(action->edges, 0,
 609                 (action->max_edge_aiid+1 + n_nodes + n_neg_nodes + n_edges) * sizeof(ext_grs_edge_t));
 610
 611
 612 /* ................ 2 ................................................. */
 613         {
 614                 int ret = 0;
 615                 ret = import_graph_info(action, action->pattern);
 616                 if (!ret) return 0;
 617         }
 618         lc_list_for_each(pos, &action->negatives) {
 619                 int ret = 0;
 620                 ext_grs_graph_t *neg =
 621                         lc_list_entry(pos, ext_grs_graph_t, negative_list);
 622                 ret = import_graph_info(action, neg);
 623                 if (!ret) return 0;
 624         }
 625
 626 /* ................ 3 ................................................. */
 627
 628         /* there's a pseudo edge for each node and a backward pseudo edge
 629          * for each real and each negative edge */
 630         n_pseudo_edges = n_nodes + n_edges + n_neg_edges;
 631         n_pseudo_nodes = 0;
 632
 633         /* setup space for information about homomorphic node matching and about critical
 634          * nodes and edges. A node or edge is critical when it multiple matching may be
 635          * harmful for parallel rule application */
 636         if (action->max_node_aiid >= 0) {
 637                 action->hom =
 638                         obstack_alloc(&obst, (action->max_node_aiid+1) * sizeof(*(action->hom)));
 639                 action->node_critical = obstack_alloc(&obst,
 640                         (action->max_node_aiid+1) * sizeof(*(action->node_critical)));
 641         }
 642         if (n_nodes > 0)
 643                 action->pattern_node_kept =
 644                         obstack_alloc(&obst, (action->max_node_aiid+1) * sizeof(*action->pattern_node_kept));
 645
 646         for (i=0; i <= action->max_node_aiid; i++) {
 647
 648                 action->hom[i] = obstack_alloc(
 649                         &obst, (action->max_node_aiid+1) * sizeof(**(action->hom)));
 650                 memset(action->hom[i], 0,
 651                         (action->max_node_aiid+1) * sizeof(*(action->hom[i])));
 652
 653                 if (!action->nodes[i]) continue;
 654
 655                 /* by default every node is critical (unless it can be
 656                  * proofen that it is not) */
 657                 action->node_critical[i] = 1;
 658                 /* by default no node is kept */
 659                 action->pattern_node_kept[i] = -1;
 660         }
 661
 662         if (action->max_edge_aiid >= 0) {
 663                 action->edge_critical = obstack_alloc(&obst,
 664                         (action->max_edge_aiid+1) * sizeof(*(action->edge_critical)));
 665                 action->pattern_edge_kept =
 666                         obstack_alloc(&obst, (action->max_edge_aiid+1) * sizeof(*action->pattern_edge_kept));
 667         }
 668
 669         for (i=0; i <= action->max_edge_aiid; i++) {
 670                 /* by default each node is critical (unless it can be
 671                  * proofen that it is not) */
 672                 action->edge_critical[i] = 1;
 673
 674                 if (!action->edges[i]) continue;
 675
 676                 /* by default no edge is kept */
 677                 action->pattern_edge_kept[i] = -1;
 678         }
 679
 680
 681         /* .................................... 4 .................................. */
 682         set_up_condition_stuff(action);
 683
 684         action->n_nodes = n_nodes;
 685         action->n_edges = n_edges;
 686
 687         action->n_neg_nodes = n_neg_nodes;
 688         action->n_neg_edges = n_neg_edges;
 689
 690         action->n_pseudo_nodes = n_pseudo_nodes;
 691         action->n_pseudo_edges = n_pseudo_edges;
 692
 693
 694
 695
 696         /* if the action is of kind test, no replacement information has to be set up */
 697         if (action->kind == ext_grs_k_test) {
 698                 /* set mature flag */
 699                 action->mature = 1;
 700                 return 1;
 701         }
 702
 703
 704
 705
 706         /* setup replacement information */
 707
 708         /* first: nodes */
 709         if (action->max_repl_node_aiid >= 0) {
 710                 action->replacement_nodes = obstack_alloc(&obst,
 711                         (action->max_repl_node_aiid+1) * sizeof(*action->replacement_nodes));
 712                 memset(action->replacement_nodes, 0,
 713                         (action->max_repl_node_aiid+1) * sizeof(*action->replacement_nodes));
 714                 action->replacement_node_kept = obstack_alloc(&obst,
 715                         (action->max_repl_node_aiid+1) * sizeof(*action->replacement_node_kept));
 716         }
 717         for (i = 0; i <= action->max_repl_node_aiid; i++)
 718                 /* by default ALL nodea are newly inserted */
 719                 action->replacement_node_kept[i] = -1;
 720
 721         lc_list_for_each(pos1, & action->replacement->nodes) {
 722
 723                 ext_grs_node_t *node = lc_list_entry(pos1, ext_grs_node_t, node_list);
 724
 725                 if (action->replacement_nodes[node->aiid] == NULL) {
 726                         action->replacement_nodes[node->aiid] = node;
 727                 }
 728                 else {
 729                         printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 730                         printf("  Multiply assigned id of a replacement node encountered!\n\n");
 731                         return 0;
 732                 }
 733         }
 734         action->n_replacement_nodes = action->replacement->n_nodes;
 735
 736         /* second: edges */
 737         if (action->max_repl_edge_aiid >= 0) {
 738                 action->replacement_edges = obstack_alloc(&obst,
 739                         (action->max_repl_edge_aiid+1) * sizeof(*action->replacement_edges));
 740                 memset(action->replacement_edges, 0,
 741                         (action->max_repl_edge_aiid+1) * sizeof(*action->replacement_edges));
 742                 action->replacement_edge_kept = obstack_alloc(&obst,
 743                         (action->max_repl_edge_aiid+1) * sizeof(*action->replacement_edge_kept));
 744         }
 745         /* iterate over all replace edges */
 746         for (i = 0; i <= action->max_repl_edge_aiid; i++)
 747                 /* by default ALL nodes are newly inserted */
 748                 action->replacement_edge_kept[i] = -1;
 749
 750         lc_list_for_each(pos, & action->replacement->edges) {
 751                 ext_grs_edge_t *edge = lc_list_entry(pos, ext_grs_edge_t, edge_list);
 752
 753                 if (action->replacement_edges[edge->aiid] == NULL) {
 754                         action->replacement_edges[edge->aiid] = edge;
 755                 }
 756                 else {
 757                         printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 758                         printf("  Multiply assigned id of a replacement edge encountered!\n\n");
 759                         return 0;
 760                 }
 761         }
 762         action->n_replacement_edges = action->replacement->n_edges;
 763
 764
 765
 766
 767
 768         /* setup information about the nodes and edges, which have to be kept by
 769          * the rewriting step */
 770         {
 771                 /* for this reason iterate over all pairs of nodes/edges stored in the ptr
 772                  *  to ptr map representing the association of pattern ans replacement elements */
 773                 ext_grs_ptr_map_entry_t *entry = lc_pset_first(action->kept_elems);
 774                 for ( ; entry; entry = lc_pset_next(action->kept_elems) ) {
 775
 776                         if (entry->kind == ext_grs_k_node) {
 777
 778                                 ext_grs_node_t *n1 = (ext_grs_node_t *) entry->pre;
 779                                 ext_grs_node_t *n2 = (ext_grs_node_t *) entry->img;
 780
 781                                 assert(n1->kind == ext_grs_k_node && n2->kind == ext_grs_k_node);
 782                                 action->pattern_node_kept[n1->aiid] = n2->aiid;
 783                                 action->replacement_node_kept[n2->aiid] = n1->aiid;
 784                         }
 785
 786                         else if (entry->kind == ext_grs_k_edge) {
 787
 788                                 ext_grs_edge_t *e1 = (ext_grs_edge_t *) entry->pre;
 789                                 ext_grs_edge_t *e2 = (ext_grs_edge_t *) entry->img;
 790
 791                                 assert(e1->kind == ext_grs_k_edge && e2->kind == ext_grs_k_edge);
 792                                 action->pattern_edge_kept[e1->aiid] = e2->aiid;
 793                                 action->replacement_edge_kept[e2->aiid] = e1->aiid;
 794                         }
 795
 796                         else assert(0 && "found an invalid entry in the ptr to ptr map");
 797                 }
 798         }
 799
 800         /* for all replacement nodes count the number of incoming edges having
 801          * no given position and not being associated with a pattern edge and
 802          * having no position function. This
 803          * number is stored in each replacement nodes and represents the number
 804          * of edges to appended to the matched host nodes in array without a
 805          * specific order.
 806          */
 807         for (i = 0; i <= action->max_repl_node_aiid; i++) {
 808                 ext_grs_node_t *node = action->replacement_nodes[i];
 809
 810                 if (!node) continue;
 811
 812
 813                 node->n_append_edges = 0;
 814                 lc_list_for_each (pos, & node->edges[ext_grs_in]) {
 815
 816                         ext_grs_edge_t *in_edge = lc_list_entry(pos, ext_grs_edge_t, list[ext_grs_in]);
 817                         assert(in_edge->aiid >= 0 && "invalid aiid encountered");
 818
 819                         if (in_edge->position_func) {
 820
 821                                 if (in_edge->pos != ext_grs_NO_EDGE_POS) {
 822                                         assert(in_edge->pos >= 0 && "bad edge position");
 823                                         printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 824                                         printf("  There is a position function associated with an edge,\n");
 825                                         printf("  which has a given postion.\n\n");
 826                                         return 0;
 827                                 }
 828                                 if (action->replacement_node_kept[in_edge->aiid] >= 0) {
 829                                         printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 830                                         printf("  There is a position function associated with an edge,\n");
 831                                         printf("  which is not to be newly inserted but kept.\n\n");
 832                                         return 0;
 833                                 }
 834
 835                         }
 836                         else {
 837
 838                                 if
 839                                 (
 840                                         in_edge->pos == ext_grs_NO_EDGE_POS &&
 841                                         action->replacement_edge_kept[in_edge->aiid] == -1
 842                                 )
 843                                 {
 844                                         node->n_append_edges++;
 845                                 }
 846
 847                         }
 848
 849                 }
 850         }
 851
 852
 853
 854
 855         /* ensure that there is no edge, which has to be preserved while the rewriting
 856          * and is incident to a pattern node, which has to be removed and, if not,
 857          * ensure that associated edges are incident to associated nodes */
 858         lc_list_for_each(pos, & action->pattern->edges) {
 859
 860                 ext_grs_edge_t *edge = lc_list_entry(pos, ext_grs_edge_t, edge_list);
 861
 862                 if (
 863                         edge->kind == ext_grs_k_edge &&
 864                         action->pattern_edge_kept[edge->aiid] > -1
 865                 )
 866                 {
 867                         if (action->pattern_node_kept[edge->func->aiid] == -1 ||
 868                                 action->pattern_node_kept[edge->arg->aiid] == -1)
 869                         {
 870                                 printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 871                                 printf("  Action contains a pattern edge which is announced as to\n");
 872                                 printf("  be kept in rewrite steps, but this edge is incident to\n");
 873                                 printf("  a pattern node which must be deleted.\n\n");
 874
 875                                 return 0;
 876                         }
 877                         else {
 878                                 ext_grs_edge_t *rpl_edge;
 879                                 ext_grs_node_t *rpl_arg_node, *rpl_func_node;
 880
 881                                 assert(
 882                                         action->pattern_node_kept[edge->func->aiid] > -1 &&
 883                                         action->pattern_node_kept[edge->arg->aiid] > -1 &&
 884                                         "there should be no entry less than -1");
 885
 886                                 rpl_edge = action->replacement_edges[action->pattern_edge_kept[edge->aiid]];
 887                                 rpl_func_node =
 888                                         action->replacement_nodes[action->pattern_node_kept[edge->func->aiid]];
 889                                 rpl_arg_node =
 890                                         action->replacement_nodes[action->pattern_node_kept[edge->arg->aiid]];
 891
 892                                 if (rpl_edge->func != rpl_func_node || rpl_edge->arg != rpl_arg_node) {
 893                                         printf("module ext/grs: ERROR in function ext_grs_act_mature()\n");
 894                                         printf("  Action contains a pattern edge which is announced as to\n");
 895                                         printf("  be kept in rewrite steps, but at least one of the replacement\n");
 896                                         printf("  nodes incident to the associated replacement edge is not\n");
 897                                         printf("  associated with the respective pattern nodes.\n\n");
 898
 899                                         return 0;
 900                                 }
 901                         }
 902
 903                 }
 904         }
 905
 906
 907 #if 0
 908         /* prepare relation between pattern nodes and negative nodes by
 909          * initializing with 0 which means that there is no relation yet */
 910         action->neg_node_related = obstack_alloc(&obst,
 911                         (action->max_node_aiid+1) * sizeof(*action->neg_node_related));
 912         memset(action->neg_node_related, 0,
 913                         (action->max_node_aiid+1) * sizeof(*action->neg_node_related));
 914
 915         action->neg_edge_related = obstack_alloc(&obst,
 916                         (action->max_edge_aiid+1) * sizeof(*action->neg_edge_related));
 917         memset(action->neg_edge_related, 0,
 918                         (action->max_edge_aiid+1) * sizeof(*action->neg_edge_related));
 919 #endif
 920
 921
 922         /* set mature flag */
 923         action->mature = 1;
 924
 925         return 1;
 926 }
 927
 928
 929 /** get a pattern node by its name */
 930 ext_grs_node_t *ext_grs_act_get_node(ext_grs_action_t *action, char *name) {
 931
 932         ext_grs_node_t *node;
 933         int i;
 934
 935         if (action->mature == 0) {
 936                 printf("module ext/grs: ERROR in function ext_grs_act_get_node()\n");
 937                 printf("  The given action is NOT mature!\n\n");
 938                 return NULL;
 939         }
 940
 941         // Look for the name in the pattern node array
 942         for(i = 0; i <= action->max_node_aiid; i++) {
 943                 node = action->nodes[i];
 944                 if(node)
 945                         if ( strcmp(name, node->name) == 0 )
 946                                 return node;
 947         }
 948
 949         // Look for the name in the replace node array
 950         for(i = 0; i <= action->max_repl_node_aiid; i++) {
 951                 node = action->replacement_nodes[i];
 952                 if(node)
 953                         if (strcmp(name, node->name) == 0)
 954                                 return node;
 955         }
 956
 957         return NULL;
 958 }
 959
 960
 961 /** Same as ext_grs_act_get_node, but compares only the first n bytes of the node name */
 962 ext_grs_node_t *ext_grs_act_get_node_n(ext_grs_action_t *action, char *name, int n) {
 963
 964         ext_grs_node_t *node;
 965         int i;
 966
 967         if (action->mature == 0) {
 968                 printf("module ext/grs: ERROR in function ext_grs_act_get_node()\n");
 969                 printf("  The given action is NOT mature!\n\n");
 970                 return NULL;
 971         }
 972
 973         // Look for the name in the pattern node array
 974         for(i = 0; i <= action->max_node_aiid; i++) {
 975                 node = action->nodes[i];
 976                 if(node)
 977                         if ( strncmp(name, node->name, n) == 0 )
 978                                 return node;
 979         }
 980
 981         // Look for the name in the replace node array
 982         for(i = 0; i <= action->max_repl_node_aiid; i++) {
 983                 node = action->replacement_nodes[i];
 984                 if(node)
 985                         if (strncmp(name, node->name, n) == 0)
 986                                 return node;
 987         }
 988
 989         return NULL;
 990 }
 991
 992
 993 /** Get a pattern node aiid by its name. */
 994 int ext_grs_act_get_node_aiid(ext_grs_action_t *action, char *name)
 995 {
 996         ext_grs_node_t *node = ext_grs_act_get_node(action, name);
 997         if(node)
 998                 return(node->aiid);
 999         else
1000                 return(-1);
1001 }
1002
1003 /** Same as ext_grs_act_get_nodes_aiid, but compares only the first n bytes of the nodes name */
1004 int ext_grs_act_get_node_aiid_n(ext_grs_action_t *action, char *name, int n)
1005 {
1006         ext_grs_node_t *node = ext_grs_act_get_node_n(action, name, n);
1007         if(node)
1008                 return(node->aiid);
1009         else
1010                 return(-1);
1011 }
1012
1013
1014
1015 /** get a pattern edge by its name */
1016 ext_grs_edge_t *ext_grs_act_get_edge(ext_grs_action_t *action, char *name) {
1017
1018         ext_grs_edge_t *edge;
1019         int i;
1020
1021         if (action->mature == 0) {
1022                 printf("module ext/grs: ERROR in function ext_grs_act_get_edge()\n");
1023                 printf("  The given action is NOT mature\n\n");
1024                 return NULL;
1025         }
1026
1027         for(i = 0; i < action->n_edges; i++) {
1028                 edge = action->edges[i];
1029                 if ( strcmp(name, edge->name) == 0 )
1030                         return edge;
1031         }
1032         return NULL;
1033 }
1034
1035
1036 /** allows homomorphic matching of two pattern nodes,
1037  *  note that these two nodes MUST have the same op and mode
1038  *  (including mode ANY) and belong tp the same acion
1039  *  @returns zero if fails and nonzero otherwise
1040  *  @note the action the given nodes belong to has to be mature */
1041 int ext_grs_act_allow_nodes_hom(ext_grs_node_t *n1, ext_grs_node_t *n2)
1042 {
1043         ext_grs_action_t *act;
1044
1045         if (!n1 || !n2) {
1046                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1047                 printf("  NULL node(s) has/have been given.\n\n");
1048                 return 0;
1049         }
1050
1051         assert(n1->graph && n2->graph && "every node should belong to a graph");
1052         assert(n1->graph->action && n2->graph->action &&
1053                 "every graph should belong to an action");
1054         act = n1->graph->action;
1055
1056         /* check wether the given nodes are not replacement nodes nodes */
1057         if (
1058                 n1->graph->kind == ext_grs_k_replacement ||
1059                 n2->graph->kind == ext_grs_k_replacement
1060         )
1061         {
1062                 assert(n1->graph == act->replacement);
1063                 assert(n2->graph == act->replacement);
1064
1065                 printf("module ext/grs: ERROR in function ext_grs_act_allow_nodes_hom()\n");
1066                 printf("  At least one given node belongs to a replacement graph.\n\n");
1067                 return 0;
1068         }
1069
1070         /* check wether the given nodes belong to the given action */
1071         if (n1->graph->action != n2->graph->action) {
1072                 printf("module ext/grs: ERROR in function ext_grs_act_allow_nodes_hom()\n");
1073                 printf("  Given nodes belong to different actions.\n\n");
1074                 return 0;
1075         }
1076         /* action has to be mature */
1077         if (! act->mature) {
1078                 printf("module ext/grs: ERROR in function ext_grs_act_allow_nodes_hom()\n");
1079                 printf("  Given action is not mature.\n\n");
1080                 return 0;
1081         }
1082         /* check wether the given nodes have the same firm op and firm mode */
1083         if (n1->op != n2->op  ||  n1->mode != n2->mode) {
1084                 printf("module ext/grs: ERROR in function ext_grs_act_allow_nodes_hom()\n");
1085                 printf("  Given nodes have different Firm op and/or different Firm mode.\n\n");
1086                 return 0;
1087         }
1088         /* if the given pattern nodes are BOTH associated with replacement
1089          * nodes, check wether the ops and modes of the replacement nodes are equal */
1090         if (act->pattern_node_kept[n1->aiid] >= 0 && act->pattern_node_kept[n2->aiid] >= 0) {
1091
1092                 ext_grs_node_t *rpl_n1, *rpl_n2;
1093
1094                 assert(n1->graph->kind != ext_grs_k_negative &&
1095                         "a negative node should not be marked as kept");
1096                 assert(n2->graph->kind != ext_grs_k_negative &&
1097                         "a negative node should not be marked as kept");
1098
1099                 rpl_n1 = act->replacement_nodes[act->pattern_node_kept[n1->aiid]];
1100                 rpl_n2 = act->replacement_nodes[act->pattern_node_kept[n2->aiid]];
1101                 if (rpl_n1->op != rpl_n2->op || rpl_n1->mode != rpl_n2->mode)
1102                 {
1103                         printf("module ext/grs: ERROR in function ext_grs_act_allow_nodes_hom()\n");
1104                         printf("  Given pattern nodes are assiciated with replacement nodes of\n");
1105                         printf("  different op or mode, this may cause undefined behaviour of\n");
1106                         printf("  the replacement when the nodes are matched homomorphic.\n\n");
1107                         return 0;
1108                 }
1109         }
1110
1111
1112         /* allow homomorphic matching of the given node */
1113         act->hom[n1->aiid][n2->aiid] = 1;
1114
1115         return 1;
1116 }
1117
1118
1119 int ext_grs_act_announce_kept_node(ext_grs_node_t *n1, ext_grs_node_t *n2)
1120 {
1121         ext_grs_action_t *act;
1122         ext_grs_ptr_map_entry_t *new_entry = obstack_alloc(&obst, sizeof(*new_entry));
1123
1124         if (! new_entry) {
1125                 printf("module ext/grs: Internal ERROR in function ext_grs_act_announce_kept_node()\n");
1126                 printf("  Failed to allocate a new node pair representative.\n\n");
1127                 return 0;
1128         }
1129
1130         if (!n1 || !n2) {
1131                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1132                 printf("  NULL node(s) has/have been given.\n\n");
1133                 obstack_free(&obst, new_entry);
1134                 return 0;
1135         }
1136
1137
1138         assert(n1->graph->action && n2->graph->action &&
1139                 "every graph should belong to an action");
1140         act = n1->graph->action;
1141
1142         /* check wether the given nodes belong to the given action */
1143         if (n1->graph->action != n2->graph->action) {
1144                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1145                 printf("  Given nodes belong to different actions.\n\n");
1146                 obstack_free(&obst, new_entry);
1147                 return 0;
1148         }
1149         /* action must not be mature */
1150         if (act->mature) {
1151                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1152                 printf("  Given action must not be mature.\n\n");
1153                 obstack_free(&obst, new_entry);
1154                 return 0;
1155         }
1156         /* check wether n1 belongs to pattern and n2 to the replacement graph */
1157         if (n1->graph != act->pattern || n2->graph != act->replacement) {
1158                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1159                 printf("  A pattern node and a replacement node must be given.\n\n");
1160                 obstack_free(&obst, new_entry);
1161                 return 0;
1162         }
1163
1164         new_entry->kind = ext_grs_k_node;
1165         new_entry->pre = n1;
1166         new_entry->img = n2;
1167
1168         not_injective = 0;
1169         multiple_entry = 0;
1170         already_exists = 0;
1171         lc_pset_insert(act->kept_elems, new_entry, LC_HASH_PTR(new_entry));
1172
1173         if (not_injective) {
1174                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1175                 printf("  The given replacement node has already been\n");
1176                 printf("  associated with another pattern node.\n\n");
1177                 obstack_free(&obst, new_entry);
1178                 return 0;
1179         }
1180
1181         if (multiple_entry) {
1182                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1183                 printf("  The given pattern node has already been\n");
1184                 printf("  associated with another replacement node.\n\n");
1185                 obstack_free(&obst, new_entry);
1186                 return 0;
1187         }
1188
1189         if (already_exists) {
1190                 printf("module ext/grs: WARNING in function ext_grs_act_announce_kept_node()\n");
1191                 printf("  The given association has already been announced.\n\n");
1192                 obstack_free(&obst, new_entry);
1193                 return 0;
1194         }
1195
1196         return 1;
1197 }
1198
1199 int ext_grs_act_announce_kept_edge(ext_grs_edge_t *e1, ext_grs_edge_t *e2)
1200 {
1201         ext_grs_action_t *act;
1202         ext_grs_ptr_map_entry_t *new_entry = obstack_alloc(&obst, sizeof(*new_entry));
1203
1204         if (! new_entry) {
1205                 printf("module ext/grs: Internal ERROR in function ext_grs_act_announce_kept_node()\n");
1206                 printf("  Failed to allocate a new edge pair representative.\n\n");
1207                 return 0;
1208         }
1209
1210         if (!e1 || !e2) {
1211                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_edge()\n");
1212                 printf("  NULL edge(s) has/have been given.\n\n");
1213                 obstack_free(&obst, new_entry);
1214                 return 0;
1215         }
1216
1217         if (!e1->graph || !e2->graph || !e1->graph->action || !e2->graph->action) {
1218                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_edge()\n");
1219                 printf("  At least one of the given edges is corrupted.\n\n");
1220                 obstack_free(&obst, new_entry);
1221                 return 0;
1222         }
1223
1224         act = e1->graph->action;
1225
1226         /* check wether the given nodes belong to the given action */
1227         if (e1->graph->action != e2->graph->action) {
1228                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_edge()\n");
1229                 printf("  Given edges belong to different actions.\n\n");
1230                 obstack_free(&obst, new_entry);
1231                 return 0;
1232         }
1233         /* action has to be mature */
1234         if (act->mature) {
1235                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_edge()\n");
1236                 printf("  Given action must not be mature.\n\n");
1237                 obstack_free(&obst, new_entry);
1238                 return 0;
1239         }
1240         /* check wether n1 belongs to pattern and n2 to the replacement graph */
1241         if (e1->graph != act->pattern || e2->graph != act->replacement) {
1242                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_edge()\n");
1243                 printf("  A pattern edge and a replacement edge must be given.\n\n");
1244                 obstack_free(&obst, new_entry);
1245                 return 0;
1246         }
1247
1248         if (e1->pos != e2->pos) {
1249                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_edge()\n");
1250                 printf("  The pattern and the replacemnt edge must have the same position OR\n");
1251                 printf("  both no position at all.\n\n");
1252                 obstack_free(&obst, new_entry);
1253                 return 0;
1254         }
1255
1256         new_entry->kind = ext_grs_k_edge;
1257         new_entry->pre = e1;
1258         new_entry->img = e2;
1259
1260         not_injective = 0;
1261         multiple_entry = 0;
1262         already_exists = 0;
1263         lc_pset_insert(act->kept_elems, new_entry, LC_HASH_PTR(new_entry));
1264
1265         if (not_injective) {
1266                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1267                 printf("  The given replacement node has already been\n");
1268                 printf("  associated with another pattern node.\n\n");
1269                 obstack_free(&obst, new_entry);
1270                 return 0;
1271         }
1272
1273         if (multiple_entry) {
1274                 printf("module ext/grs: ERROR in function ext_grs_act_announce_kept_node()\n");
1275                 printf("  The given pattern node has already been\n");
1276                 printf("  associated with another replacement node.\n\n");
1277                 obstack_free(&obst, new_entry);
1278                 return 0;
1279         }
1280
1281         if (already_exists) {
1282                 printf("module ext/grs: WARNING in function ext_grs_act_announce_kept_node()\n");
1283                 printf("  The given association has already been announced.\n\n");
1284                 obstack_free(&obst, new_entry);
1285                 return 0;
1286         }
1287
1288         return 1;
1289 }
1290
1291 int ext_grs_act_relate_neg_node(ext_grs_node_t *pat_node, ext_grs_node_t *neg_node) {
1292
1293         if (pat_node->graph->action != neg_node->graph->action) {
1294                 printf("module ext/grs: ERROR in function ext_grs_act_relate_neg_node()\n");
1295                 printf("  The given nodes do not belong to the same action.\n\n");
1296                 return 0;
1297         }
1298
1299         if (pat_node->graph->kind != ext_grs_k_pattern) {
1300                 printf("module ext/grs: ERROR in function ext_grs_act_relate_neg_node()\n");
1301                 printf("  The given pattern node does not belong to a pattern graph.\n\n");
1302                 return 0;
1303         }
1304
1305         if (neg_node->graph->kind != ext_grs_k_negative) {
1306                 printf("module ext/grs: ERROR in function ext_grs_act_relate_neg_node()\n");
1307                 printf("  The given negative node does not belong to a negative pattern graph.\n\n");
1308                 return 0;
1309         }
1310
1311         neg_node->related_node = pat_node;
1312         return(1);
1313 }
1314
1315 int ext_grs_act_relate_neg_edge(ext_grs_edge_t *pat_edge, ext_grs_edge_t *neg_edge) {
1316
1317         if (pat_edge->graph->action != neg_edge->graph->action) {
1318                 printf("module ext/grs: ERROR in function ext_grs_act_relate_neg_edge()\n");
1319                 printf("  The given edges do not belong to the same action.\n\n");
1320                 return 0;
1321         }
1322
1323         if (pat_edge->graph->kind != ext_grs_k_pattern) {
1324                 printf("module ext/grs: ERROR in function ext_grs_act_relate_neg_edge()\n");
1325                 printf("  The given pattern edge does not belong to a pattern graph.\n\n");
1326                 return 0;
1327         }
1328
1329         if (neg_edge->graph->kind != ext_grs_k_negative) {
1330                 printf("module ext/grs: ERROR in function ext_grs_act_relate_neg_edge()\n");
1331                 printf("  The given negative edge does not belong to a negative pattern graph.\n\n");
1332                 return 0;
1333         }
1334
1335         neg_edge->related_edge = pat_edge;
1336         return(1);
1337 }
1338
1339
1340
1341 int ext_grs_act_register_condition(
1342                 ext_grs_condition_func_t func,
1343                 ext_grs_graph_t *graph,
1344                 int n_nodes, ext_grs_node_t **nodes,
1345                 int n_edges, ext_grs_edge_t **edges)
1346 {
1347         int i;
1348         ext_grs_cond_descr_t *cond_descr;
1349         ext_grs_node_t **nodes_copied = obstack_alloc(&obst, n_nodes * sizeof(*nodes_copied));
1350         ext_grs_edge_t **edges_copied = obstack_alloc(&obst, n_edges * sizeof(*edges_copied));
1351
1352         if (!func) {
1353                 printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1354                 printf("  The given condition function was NULL.\n\n");
1355                 return 0;
1356         }
1357
1358         if (!graph) {
1359                 printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1360                 printf("  The given (pattern or negative graph) was NULL.\n\n");
1361                 return 0;
1362         }
1363
1364         if (graph->action->mature) {
1365                 printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1366                 printf("  The given action is already mature, no condition registered.\n\n");
1367                 return 0;
1368         }
1369
1370         /* check whether the given nodes and edges are really nodes and edges, AND check
1371          * whether these nodes and edges all belong to the given action */
1372         for (i = 0; i < n_nodes; i++) {
1373
1374                 if (!nodes[i]) {
1375                         printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1376                         printf("  A given node was NULL.\n\n");
1377                         return 0;
1378                 }
1379                 if (nodes[i]->kind != ext_grs_k_node) {
1380                         printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1381                         printf("  A given node was not a valid node.\n\n");
1382                         return 0;
1383                 }
1384                 if (nodes[i]->graph->action != graph->action) {
1385                         printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1386                         printf("  A given node belongs to an action different from the one of the given\n");
1387                         printf("  (pattern or negative) graph.\n\n");
1388                         return 0;
1389                 }
1390
1391                 nodes_copied[i] = nodes[i];
1392         }
1393         for (i = 0; i < n_edges; i++) {
1394
1395                 if (!edges[i]) {
1396                         printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1397                         printf("  A given edge was NULL.\n\n");
1398                         return 0;
1399                 }
1400                 if (edges[i]->kind != ext_grs_k_edge) {
1401                         printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1402                         printf("  A given edge was not a valid edge.\n\n");
1403                         return 0;
1404                 }
1405                 if (edges[i]->graph->action != graph->action) {
1406                         printf("module ext/grs: ERROR in function ext_grs_act_register_condition()\n");
1407                         printf("  A given edge belongs to an action different from one of the given\n");
1408                         printf("  (pattern or negative) graph.\n\n");
1409                         return 0;
1410                 }
1411
1412                 edges_copied[i] = edges[i];
1413         }
1414
1415         /* allocate space for a condition descriptor */
1416         cond_descr = obstack_alloc(&obst, sizeof(*cond_descr));
1417         memset(cond_descr, 0, sizeof(cond_descr));
1418
1419         /* init the condition descriptor */
1420         cond_descr->graph = graph;
1421         cond_descr->condition = func;
1422
1423         cond_descr->n_nodes = n_nodes;
1424         cond_descr->nodes = nodes_copied;
1425         cond_descr->n_edges = n_edges;
1426         cond_descr->edges = edges_copied;
1427
1428         /* add the condition descriptor to the list */
1429         lc_list_add(&cond_descr->condition_list, & graph->action->listed_conditions);
1430         /* increment the number of conditions */
1431         graph->n_conditions++;
1432         graph->action->n_conditions++; // AS
1433         return 1;
1434 }
1435
1436
1437 int ext_grs_act_register_eval(ext_grs_action_t *action,
1438                 ext_grs_eval_in_func_t in_func, ext_grs_eval_out_func_t out_func)
1439 {
1440         ext_grs_eval_descr_t *eval_descr;
1441
1442         /*if (!in_func) {
1443                 printf("module ext/grs: ERROR in function ext_grs_act_register_eval()\n");
1444                 printf("  The given eval-in function function was NULL.\n\n");
1445                 return 0;
1446         }
1447         if (!out_func) {
1448                 printf("module ext/grs: ERROR in function ext_grs_act_register_eval()\n");
1449                 printf("  The given eval-out function function was NULL.\n\n");
1450                 return 0;
1451         }*/
1452         if (action->mature) {
1453                 printf("module ext/grs: ERROR in function ext_grs_act_register_eval_out_func()\n");
1454                 printf("  The given action is already mature, no eval function registered.\n\n");
1455                 return 0;
1456         }
1457
1458         eval_descr = obstack_alloc(&obst, sizeof(*eval_descr));
1459         memset(eval_descr, 0, sizeof(*eval_descr));
1460         eval_descr->eval_in = in_func;
1461         eval_descr->eval_out = out_func;
1462         eval_descr->data = NULL;
1463         lc_list_add_tail(& eval_descr->eval_list, & action->listed_evals);
1464         return 1;
1465 }
1466
1467
1468
1469 int ext_grs_act_set_op_condition(
1470         ext_grs_node_t *node, ext_grs_op_condition_func_t func)
1471 {
1472         if (!node) {
1473                 printf("module ext/grs: ERROR in function ext_grs_act_set_op_condition()\n");
1474                 printf("  The given node was NULL.\n\n");
1475                 return 0;
1476         }
1477         if (!func) {
1478                 printf("module ext/grs: ERROR in function ext_grs_act_set_op_condition()\n");
1479                 printf("  The given op condition function was NULL.\n\n");
1480                 return 0;
1481         }
1482
1483         node->op_condition = func;
1484         return 1;
1485 }
1486
1487 int ext_grs_act_set_mode_condition(
1488                 ext_grs_node_t *node, ext_grs_mode_condition_func_t func)
1489 {
1490         if (!node) {
1491                 printf("module ext/grs: ERROR in function ext_grs_act_set_mode_condition()\n");
1492                 printf("  The given node was NULL.\n\n");
1493                 return 0;
1494         }
1495         if (!func) {
1496                 printf("module ext/grs: ERROR in function ext_grs_act_set_mode_condition()\n");
1497                 printf("  The given mode condition function was NULL.\n\n");
1498                 return 0;
1499         }
1500
1501         node->mode_condition = func;
1502         return 1;
1503 }
1504
1505 int ext_grs_act_set_pos_func(ext_grs_edge_t *edge, ext_grs_edge_pos_func_t func)
1506 {
1507         if (!edge) {
1508                 printf("module ext/grs: ERROR in function ext_grs_act_set_pos_func()\n");
1509                 printf("  The given edge was NULL.\n\n");
1510                 return 0;
1511         }
1512         if (!edge) {
1513                 printf("module ext/grs: ERROR in function ext_grs_act_set_pos_func()\n");
1514                 printf("  The given position function was NULL.\n\n");
1515                 return 0;
1516         }
1517         assert(edge->graph && "every edge should have a graph");
1518         if (edge->graph->kind != ext_grs_k_replacement) {
1519                 printf("module ext/grs: ERROR in function ext_grs_act_set_pos_func()\n");
1520                 printf("  The given edge belongs to a graph, which is not a replacement graph.\n\n");
1521                 return 0;
1522         }
1523         assert(edge->graph->action && "every graph should have an action");
1524         if (edge->graph->action->mature) {
1525                 printf("module ext/grs: ERROR in function ext_grs_act_set_pos_func()\n");
1526                 printf("  The given edge belongs to an action, which is already mature.\n\n");
1527                 return 0;
1528         }
1529
1530         edge->position_func = func;
1531         return 1;
1532 }
1533
1534
1535 /* Initilize the action part of the exr/grs module of the libfirm.
1536  * This is an internal function. */
1537 void _ext_grs_act_init() {
1538         /* init obstack if necesarry */
1539         if (obst_init == 0) {
1540                 obstack_init(&obst);
1541         }
1542         obst_init = 1;
1543 }
1544
1545 /* Finalize the action part of the exr/grs module of the libfirm.
1546  * This is an internal function */
1547 void _ext_grs_act_finalize() {
1548
1549         /* finalize the action obstack */
1550         obstack_free(&obst, NULL);
1551         obstack_finish(&obst);
1552 }