utils/Burg/table.c

   1 char rcsid_table[] = "$Id$";
   2
   3 #include "b.h"
   4 #include <string.h>
   5 #include <stdio.h>
   6
   7 static void growIndex_Map ARGS((Index_Map *));
   8 static Relevant newRelevant ARGS((void));
   9 static Dimension newDimension ARGS((Operator, int));
  10 static void GT_1 ARGS((Table));
  11 static void GT_2_0 ARGS((Table));
  12 static void GT_2_1 ARGS((Table));
  13 static void growTransition ARGS((Table, int));
  14 static Item_Set restrict ARGS((Dimension, Item_Set));
  15 static void addHP_1 ARGS((Table, Item_Set));
  16 static void addHP_2_0 ARGS((Table, Item_Set));
  17 static void addHP_2_1 ARGS((Table, Item_Set));
  18 static void addHyperPlane ARGS((Table, int, Item_Set));
  19
  20 static void
  21 growIndex_Map(r) Index_Map *r;
  22 {
  23         Index_Map new;
  24
  25         new.max_size = r->max_size + STATES_INCR;
  26         new.class = (Item_Set*) zalloc(new.max_size * sizeof(Item_Set));
  27         assert(new.class);
  28         memcpy(new.class, r->class, r->max_size * sizeof(Item_Set));
  29         zfree(r->class);
  30         *r = new;
  31 }
  32
  33 static Relevant
  34 newRelevant()
  35 {
  36         Relevant r = (Relevant) zalloc(max_nonterminal * sizeof(*r));
  37         return r;
  38 }
  39
  40 void
  41 addRelevant(r, nt) Relevant r; NonTerminalNum nt;
  42 {
  43         int i;
  44
  45         for (i = 0; r[i]; i++) {
  46                 if (r[i] == nt) {
  47                         break;
  48                 }
  49         }
  50         if (!r[i]) {
  51                 r[i] = nt;
  52         }
  53 }
  54
  55 static Dimension
  56 newDimension(op, index) Operator op; ArityNum index;
  57 {
  58         Dimension d;
  59         List pl;
  60         Relevant r;
  61
  62         assert(op);
  63         assert(index >= 0 && index < op->arity);
  64         d = (Dimension) zalloc(sizeof(struct dimension));
  65         assert(d);
  66
  67         r = d->relevant = newRelevant();
  68         for (pl = rules; pl; pl = pl->next) {
  69                 Rule pr = (Rule) pl->x;
  70                 if (pr->pat->op == op) {
  71                         addRelevant(r, pr->pat->children[index]->num);
  72                 }
  73         }
  74
  75         d->index_map.max_size = STATES_INCR;
  76         d->index_map.class = (Item_Set*)
  77                         zalloc(d->index_map.max_size * sizeof(Item_Set));
  78         d->map = newMapping(DIM_MAP_SIZE);
  79         d->max_size = TABLE_INCR;
  80
  81         return d;
  82 }
  83
  84 Table
  85 newTable(op) Operator op;
  86 {
  87         Table t;
  88         int i, size;
  89
  90         assert(op);
  91
  92         t = (Table) zalloc(sizeof(struct table));
  93         assert(t);
  94
  95         t->op = op;
  96
  97         for (i = 0; i < op->arity; i++) {
  98                 t->dimen[i] = newDimension(op, i);
  99         }
 100
 101         size = 1;
 102         for (i = 0; i < op->arity; i++) {
 103                 size *= t->dimen[i]->max_size;
 104         }
 105         t->transition = (Item_Set*) zalloc(size * sizeof(Item_Set));
 106         t->relevant = newRelevant();
 107         assert(t->transition);
 108
 109         return t;
 110 }
 111
 112 static void
 113 GT_1(t) Table t;
 114 {
 115         Item_Set        *ts;
 116         ItemSetNum      oldsize = t->dimen[0]->max_size;
 117         ItemSetNum      newsize = t->dimen[0]->max_size + TABLE_INCR;
 118
 119         t->dimen[0]->max_size = newsize;
 120
 121         ts = (Item_Set*) zalloc(newsize * sizeof(Item_Set));
 122         assert(ts);
 123         memcpy(ts, t->transition, oldsize * sizeof(Item_Set));
 124         zfree(t->transition);
 125         t->transition = ts;
 126 }
 127
 128 static void
 129 GT_2_0(t) Table t;
 130 {
 131         Item_Set        *ts;
 132         ItemSetNum      oldsize = t->dimen[0]->max_size;
 133         ItemSetNum      newsize = t->dimen[0]->max_size + TABLE_INCR;
 134         int             size;
 135
 136         t->dimen[0]->max_size = newsize;
 137
 138         size = newsize * t->dimen[1]->max_size;
 139
 140         ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
 141         assert(ts);
 142         memcpy(ts, t->transition, oldsize*t->dimen[1]->max_size * sizeof(Item_Set));
 143         zfree(t->transition);
 144         t->transition = ts;
 145 }
 146
 147 static void
 148 GT_2_1(t) Table t;
 149 {
 150         Item_Set        *ts;
 151         ItemSetNum      oldsize = t->dimen[1]->max_size;
 152         ItemSetNum      newsize = t->dimen[1]->max_size + TABLE_INCR;
 153         int             size;
 154         Item_Set        *from;
 155         Item_Set        *to;
 156         int             i1, i2;
 157
 158         t->dimen[1]->max_size = newsize;
 159
 160         size = newsize * t->dimen[0]->max_size;
 161
 162         ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
 163         assert(ts);
 164
 165         from = t->transition;
 166         to = ts;
 167         for (i1 = 0; i1 < t->dimen[0]->max_size; i1++) {
 168                 for (i2 = 0; i2 < oldsize; i2++) {
 169                         to[i2] = from[i2];
 170                 }
 171                 to += newsize;
 172                 from += oldsize;
 173         }
 174         zfree(t->transition);
 175         t->transition = ts;
 176 }
 177
 178 static void
 179 growTransition(t, dim) Table t; ArityNum dim;
 180 {
 181
 182         assert(t);
 183         assert(t->op);
 184         assert(dim < t->op->arity);
 185
 186         switch (t->op->arity) {
 187         default:
 188                 assert(0);
 189                 break;
 190         case 1:
 191                 GT_1(t);
 192                 return;
 193         case 2:
 194                 switch (dim) {
 195                 default:
 196                         assert(0);
 197                         break;
 198                 case 0:
 199                         GT_2_0(t);
 200                         return;
 201                 case 1:
 202                         GT_2_1(t);
 203                         return;
 204                 }
 205         }
 206 }
 207
 208 static Item_Set
 209 restrict(d, ts) Dimension d; Item_Set ts;
 210 {
 211         DeltaCost       base;
 212         Item_Set        r;
 213         int found;
 214         register Relevant r_ptr = d->relevant;
 215         register Item *ts_current = ts->closed;
 216         register Item *r_current;
 217         register int i;
 218         register int nt;
 219
 220         ZEROCOST(base);
 221         found = 0;
 222         r = newItem_Set(d->relevant);
 223         r_current = r->virgin;
 224         for (i = 0; (nt = r_ptr[i]) != 0; i++) {
 225                 if (ts_current[nt].rule) {
 226                         r_current[nt].rule = &stub_rule;
 227                         if (!found) {
 228                                 found = 1;
 229                                 ASSIGNCOST(base, ts_current[nt].delta);
 230                         } else {
 231                                 if (LESSCOST(ts_current[nt].delta, base)) {
 232                                         ASSIGNCOST(base, ts_current[nt].delta);
 233                                 }
 234                         }
 235                 }
 236         }
 237
 238         /* zero align */
 239         for (i = 0; (nt = r_ptr[i]) != 0; i++) {
 240                 if (r_current[nt].rule) {
 241                         ASSIGNCOST(r_current[nt].delta, ts_current[nt].delta);
 242                         MINUSCOST(r_current[nt].delta, base);
 243                 }
 244         }
 245         assert(!r->closed);
 246         r->representative = ts;
 247         return r;
 248 }
 249
 250 static void
 251 addHP_1(t, ts) Table t; Item_Set ts;
 252 {
 253         List pl;
 254         Item_Set e;
 255         Item_Set tmp;
 256         int new;
 257
 258         e = newItem_Set(t->relevant);
 259         assert(e);
 260         e->kids[0] = ts->representative;
 261         for (pl = t->rules; pl; pl = pl->next) {
 262                 Rule p = (Rule) pl->x;
 263                 if (t->op == p->pat->op && ts->virgin[p->pat->children[0]->num].rule) {
 264                         DeltaCost dc;
 265                         ASSIGNCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
 266                         ADDCOST(dc, p->delta);
 267                         if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
 268                                 e->virgin[p->lhs->num].rule = p;
 269                                 ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
 270                                 e->op = t->op;
 271                         }
 272                 }
 273         }
 274         trim(e);
 275         zero(e);
 276         tmp = encode(globalMap, e, &new);
 277         assert(ts->num < t->dimen[0]->map->max_size);
 278         t->transition[ts->num] = tmp;
 279         if (new) {
 280                 closure(e);
 281                 addQ(globalQ, tmp);
 282         } else {
 283                 freeItem_Set(e);
 284         }
 285 }
 286
 287 static void
 288 addHP_2_0(t, ts) Table t; Item_Set ts;
 289 {
 290         List pl;
 291         register Item_Set e;
 292         Item_Set tmp;
 293         int new;
 294         int i2;
 295
 296         assert(t->dimen[1]->map->count <= t->dimen[1]->map->max_size);
 297         for (i2 = 0; i2 < t->dimen[1]->map->count; i2++) {
 298                 e = newItem_Set(t->relevant);
 299                 assert(e);
 300                 e->kids[0] = ts->representative;
 301                 e->kids[1] = t->dimen[1]->map->set[i2]->representative;
 302                 for (pl = t->rules; pl; pl = pl->next) {
 303                         register Rule p = (Rule) pl->x;
 304
 305                         if (t->op == p->pat->op
 306                                         && ts->virgin[p->pat->children[0]->num].rule
 307                                         && t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].rule){
 308                                 DeltaCost dc;
 309                                 ASSIGNCOST(dc, p->delta);
 310                                 ADDCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
 311                                 ADDCOST(dc, t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].delta);
 312
 313                                 if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
 314                                         e->virgin[p->lhs->num].rule = p;
 315                                         ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
 316                                         e->op = t->op;
 317                                 }
 318                         }
 319                 }
 320                 trim(e);
 321                 zero(e);
 322                 tmp = encode(globalMap, e, &new);
 323                 assert(ts->num < t->dimen[0]->map->max_size);
 324                 t->transition[ts->num * t->dimen[1]->max_size + i2] = tmp;
 325                 if (new) {
 326                         closure(e);
 327                         addQ(globalQ, tmp);
 328                 } else {
 329                         freeItem_Set(e);
 330                 }
 331         }
 332 }
 333
 334 static void
 335 addHP_2_1(t, ts) Table t; Item_Set ts;
 336 {
 337         List pl;
 338         register Item_Set e;
 339         Item_Set tmp;
 340         int new;
 341         int i1;
 342
 343         assert(t->dimen[0]->map->count <= t->dimen[0]->map->max_size);
 344         for (i1 = 0; i1 < t->dimen[0]->map->count; i1++) {
 345                 e = newItem_Set(t->relevant);
 346                 assert(e);
 347                 e->kids[0] = t->dimen[0]->map->set[i1]->representative;
 348                 e->kids[1] = ts->representative;
 349                 for (pl = t->rules; pl; pl = pl->next) {
 350                         register Rule p = (Rule) pl->x;
 351
 352                         if (t->op == p->pat->op
 353                                         && ts->virgin[p->pat->children[1]->num].rule
 354                                         && t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].rule){
 355                                 DeltaCost dc;
 356                                 ASSIGNCOST(dc, p->delta );
 357                                 ADDCOST(dc, ts->virgin[p->pat->children[1]->num].delta);
 358                                 ADDCOST(dc, t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].delta);
 359                                 if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
 360                                         e->virgin[p->lhs->num].rule = p;
 361                                         ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
 362                                         e->op = t->op;
 363                                 }
 364                         }
 365                 }
 366                 trim(e);
 367                 zero(e);
 368                 tmp = encode(globalMap, e, &new);
 369                 assert(ts->num < t->dimen[1]->map->max_size);
 370                 t->transition[i1 * t->dimen[1]->max_size + ts->num] = tmp;
 371                 if (new) {
 372                         closure(e);
 373                         addQ(globalQ, tmp);
 374                 } else {
 375                         freeItem_Set(e);
 376                 }
 377         }
 378 }
 379
 380 static void
 381 addHyperPlane(t, i, ts) Table t; ArityNum i; Item_Set ts;
 382 {
 383         switch (t->op->arity) {
 384         default:
 385                 assert(0);
 386                 break;
 387         case 1:
 388                 addHP_1(t, ts);
 389                 return;
 390         case 2:
 391                 switch (i) {
 392                 default:
 393                         assert(0);
 394                         break;
 395                 case 0:
 396                         addHP_2_0(t, ts);
 397                         return;
 398                 case 1:
 399                         addHP_2_1(t, ts);
 400                         return;
 401                 }
 402         }
 403 }
 404
 405 void
 406 addToTable(t, ts) Table t; Item_Set ts;
 407 {
 408         ArityNum i;
 409
 410         assert(t);
 411         assert(ts);
 412         assert(t->op);
 413
 414         for (i = 0; i < t->op->arity; i++) {
 415                 Item_Set r;
 416                 Item_Set tmp;
 417                 int new;
 418
 419                 r = restrict(t->dimen[i], ts);
 420                 tmp = encode(t->dimen[i]->map, r, &new);
 421                 if (t->dimen[i]->index_map.max_size <= ts->num) {
 422                         growIndex_Map(&t->dimen[i]->index_map);
 423                 }
 424                 assert(ts->num < t->dimen[i]->index_map.max_size);
 425                 t->dimen[i]->index_map.class[ts->num] = tmp;
 426                 if (new) {
 427                         if (t->dimen[i]->max_size <= r->num) {
 428                                 growTransition(t, i);
 429                         }
 430                         addHyperPlane(t, i, r);
 431                 } else {
 432                         freeItem_Set(r);
 433                 }
 434         }
 435 }
 436
 437 Item_Set *
 438 transLval(t, row, col) Table t; int row; int col;
 439 {
 440         switch (t->op->arity) {
 441         case 0:
 442                 assert(row == 0);
 443                 assert(col == 0);
 444                 return t->transition;
 445         case 1:
 446                 assert(col == 0);
 447                 return t->transition + row;
 448         case 2:
 449                 return t->transition + row * t->dimen[1]->max_size + col;
 450         default:
 451                 assert(0);
 452         }
 453         return 0;
 454 }
 455
 456 void
 457 dumpRelevant(r) Relevant r;
 458 {
 459         for (; *r; r++) {
 460                 printf("%4d", *r);
 461         }
 462 }
 463
 464 void
 465 dumpIndex_Map(r) Index_Map *r;
 466 {
 467         int i;
 468
 469         printf("BEGIN Index_Map: MaxSize (%d)\n", r->max_size);
 470         for (i = 0; i < globalMap->count; i++) {
 471                 printf("\t#%d: -> %d\n", i, r->class[i]->num);
 472         }
 473         printf("END Index_Map:\n");
 474 }
 475
 476 void
 477 dumpDimension(d) Dimension d;
 478 {
 479         printf("BEGIN Dimension:\n");
 480         printf("Relevant: ");
 481         dumpRelevant(d->relevant);
 482         printf("\n");
 483         dumpIndex_Map(&d->index_map);
 484         dumpMapping(d->map);
 485         printf("MaxSize of dimension = %d\n", d->max_size);
 486         printf("END Dimension\n");
 487 }
 488
 489 void
 490 dumpTable(t, full) Table t; int full;
 491 {
 492         int i;
 493
 494         if (!t) {
 495                 printf("NO Table yet.\n");
 496                 return;
 497         }
 498         printf("BEGIN Table:\n");
 499         if (full) {
 500                 dumpOperator(t->op, 0);
 501         }
 502         for (i = 0; i < t->op->arity; i++) {
 503                 printf("BEGIN dimension(%d)\n", i);
 504                 dumpDimension(t->dimen[i]);
 505                 printf("END dimension(%d)\n", i);
 506         }
 507         dumpTransition(t);
 508         printf("END Table:\n");
 509 }
 510
 511 void
 512 dumpTransition(t) Table t;
 513 {
 514         int i,j;
 515
 516         switch (t->op->arity) {
 517         case 0:
 518                 printf("{ %d }", t->transition[0]->num);
 519                 break;
 520         case 1:
 521                 printf("{");
 522                 for (i = 0; i < t->dimen[0]->map->count; i++) {
 523                         if (i > 0) {
 524                                 printf(",");
 525                         }
 526                         printf("%5d", t->transition[i]->num);
 527                 }
 528                 printf("}");
 529                 break;
 530         case 2:
 531                 printf("{");
 532                 for (i = 0; i < t->dimen[0]->map->count; i++) {
 533                         if (i > 0) {
 534                                 printf(",");
 535                         }
 536                         printf("\n");
 537                         printf("{");
 538                         for (j = 0; j < t->dimen[1]->map->count; j++) {
 539                                 Item_Set *ts = transLval(t, i, j);
 540                                 if (j > 0) {
 541                                         printf(",");
 542                                 }
 543                                 printf("%5d", (*ts)->num);
 544                         }
 545                         printf("}");
 546                 }
 547                 printf("\n}\n");
 548                 break;
 549         default:
 550                 assert(0);
 551         }
 552 }