prop-src/infgen.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.6),
   3 //  last updated on Nov 2, 1999.
   4 //  The original source file is "infgen.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #define PROP_STRCMP_USED
   8 #include <propdefs.h>
   9 #line 1 "infgen.pcc"
  10 ///////////////////////////////////////////////////////////////////////////////
  11 //
  12 //  This file implements the inference rules compiler of Prop.
  13 //
  14 ///////////////////////////////////////////////////////////////////////////////
  15 #include <iostream>
  16 #include <AD/memory/mempool.h>
  17 #include <AD/generic/ordering.h>
  18 #include "ir.h"
  19 #include "ast.h"
  20 #include "type.h"
  21 #include "hashtab.h"
  22 #include "config.h"
  23 #include "infgen.h"
  24 #include "datagen.h"
  25 #include "datatype.h"
  26 #include "list.h"
  27
  28 ///////////////////////////////////////////////////////////////////////////////
  29 //
  30 //  Constructor and destructor for the inference compiler
  31 //
  32 ///////////////////////////////////////////////////////////////////////////////
  33 InferenceCompiler:: InferenceCompiler() {}
  34 InferenceCompiler::~InferenceCompiler() {}
  35
  36 ///////////////////////////////////////////////////////////////////////////////
  37 //
  38 //  Import some type definitions.
  39 //
  40 ///////////////////////////////////////////////////////////////////////////////
  41 typedef HashTable::Key   Key;
  42 typedef HashTable::Value Value;
  43
  44 ///////////////////////////////////////////////////////////////////////////////
  45 //
  46 //  Method to create an inference class.
  47 //
  48 ///////////////////////////////////////////////////////////////////////////////
  49 InferenceClass::InferenceClass(Id id, Inherits i, TyQual qual, Decls body)
  50    : ClassDefinition(INFERENCE_CLASS,id,
  51 #line 41 "infgen.pcc"
  52 #line 41 "infgen.pcc"
  53 nil_1_
  54 #line 41 "infgen.pcc"
  55 #line 41 "infgen.pcc"
  56 ,
  57                      add_inherit("Rete",
  58 #line 42 "infgen.pcc"
  59 #line 42 "infgen.pcc"
  60 nil_1_
  61 #line 42 "infgen.pcc"
  62 #line 42 "infgen.pcc"
  63 ,i),qual,body) {}
  64 InferenceClass::~InferenceClass() {}
  65
  66 ///////////////////////////////////////////////////////////////////////////////
  67 //
  68 //  Method to generate the interface for an inference class.
  69 //
  70 ///////////////////////////////////////////////////////////////////////////////
  71 void InferenceClass::gen_class_interface (CodeGen& C)
  72 {
  73    C.pr
  74       ("%^%s(const %s&);"
  75        "%^void operator = (const %s&);%-"
  76        "%^public:%+"
  77        "%^static const Node          network_table[];"
  78        "%^static const RelationTable relation_table[];%-"
  79        "%^public:%+"
  80        "%^%s();"
  81        "%^virtual const char * name_of() const;"
  82        "%^void initialise_axioms();%-"
  83        "%^protected:%+"
  84        "%^virtual void alpha_test (int, int, Fact *);"
  85        "%^virtual int  beta_test  (Join, Fact * []);"
  86        "%^virtual void action     (RuleId, Fact * []);%-"
  87        "%^private:%+",
  88        class_name, class_name, class_name, class_name);
  89 }
  90
  91 ///////////////////////////////////////////////////////////////////////////////
  92 //
  93 //  Forward declarations.
  94 //
  95 ///////////////////////////////////////////////////////////////////////////////
  96 Bool partition(Exp e1, Exp e2, int &obj);
  97 Bool partition(Exps exp, int &obj);
  98 Bool partition(LabExps exp, int &obj);
  99 int  partition_inference_rules
 100         (int n, InferenceRule Rs[], HashTable& rule_map, HashTable& join_map);
 101
 102 ///////////////////////////////////////////////////////////////////////////////
 103 //
 104 //  Flatten an expression into conjuncts.  Also try to push down negation
 105 //  as much as possible.  Notice that C++ short circuited ands and ors are not
 106 //  commutative (but they are associative.)
 107 //
 108 ///////////////////////////////////////////////////////////////////////////////
 109 Exp * flatten (Exp exp, Exp * cnf, Bool neg)
 110 {
 111 #line 89 "infgen.pcc"
 112 #line 101 "infgen.pcc"
 113 {
 114    for (;;) {
 115       if (exp) {
 116          switch (exp->tag__) {
 117             case a_Exp::tag_BINOPexp: {
 118                if (
 119 #line 100 "infgen.pcc"
 120                neg
 121 #line 100 "infgen.pcc"
 122 ) {
 123
 124                   if (_less_string(((Exp_BINOPexp *)exp)->_1,"==")) {
 125                      if (_equal_string(((Exp_BINOPexp *)exp)->_1,"!=")) {
 126                      if (
 127 #line 99 "infgen.pcc"
 128                      neg
 129 #line 99 "infgen.pcc"
 130 ) {
 131
 132                         L2:;
 133 #line 99 "infgen.pcc"
 134                        *cnf = BINOPexp("==",((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3); return cnf+1;
 135 #line 99 "infgen.pcc"
 136                      } else {
 137
 138                         L3:;
 139 #line 100 "infgen.pcc"
 140                        *cnf = PREFIXexp("!",exp); return cnf+1;
 141 #line 100 "infgen.pcc"
 142                      }
 143 }
 144                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"&&")) {
 145                      if (
 146 #line 92 "infgen.pcc"
 147                      (! neg)
 148 #line 92 "infgen.pcc"
 149 ) {
 150
 151                         L4:;
 152 #line 92 "infgen.pcc"
 153                        cnf = flatten(((Exp_BINOPexp *)exp)->_2,cnf,neg); exp = ((Exp_BINOPexp *)exp)->_3;
 154 #line 92 "infgen.pcc"
 155                      } else {
 156                          goto L3; }
 157 }
 158                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"<")) {
 159                      if (
 160 #line 96 "infgen.pcc"
 161                      neg
 162 #line 96 "infgen.pcc"
 163 ) {
 164
 165                         L5:;
 166 #line 96 "infgen.pcc"
 167                        *cnf = BINOPexp(">=",((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3); return cnf+1;
 168 #line 96 "infgen.pcc"
 169                      } else {
 170                          goto L3; }
 171 }
 172                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"<=")) {
 173                      if (
 174 #line 97 "infgen.pcc"
 175                      neg
 176 #line 97 "infgen.pcc"
 177 ) {
 178
 179                         L6:;
 180 #line 97 "infgen.pcc"
 181                        *cnf = BINOPexp(">",((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3);  return cnf+1;
 182 #line 97 "infgen.pcc"
 183                      } else {
 184                          goto L3; }
 185 }
 186                      else { goto L3; }
 187                   } else {
 188                      if (_equal_string(((Exp_BINOPexp *)exp)->_1,"==")) {
 189                      if (
 190 #line 98 "infgen.pcc"
 191                      neg
 192 #line 98 "infgen.pcc"
 193 ) {
 194
 195                         L7:;
 196 #line 98 "infgen.pcc"
 197                        *cnf = BINOPexp("!=",((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3); return cnf+1;
 198 #line 98 "infgen.pcc"
 199                      } else {
 200                          goto L3; }
 201 }
 202                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,">")) {
 203                      if (
 204 #line 94 "infgen.pcc"
 205                      neg
 206 #line 94 "infgen.pcc"
 207 ) {
 208
 209                         L8:;
 210 #line 94 "infgen.pcc"
 211                        *cnf = BINOPexp("<=",((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3); return cnf+1;
 212 #line 94 "infgen.pcc"
 213                      } else {
 214                          goto L3; }
 215 }
 216                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,">=")) {
 217                      if (
 218 #line 95 "infgen.pcc"
 219                      neg
 220 #line 95 "infgen.pcc"
 221 ) {
 222
 223                         L9:;
 224 #line 95 "infgen.pcc"
 225                        *cnf = BINOPexp("<",((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3);  return cnf+1;
 226 #line 95 "infgen.pcc"
 227                      } else {
 228                          goto L3; }
 229 }
 230                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"||")) {
 231                      if (
 232 #line 93 "infgen.pcc"
 233                      neg
 234 #line 93 "infgen.pcc"
 235 ) {
 236
 237                         L10:;
 238 #line 93 "infgen.pcc"
 239                        cnf = flatten(((Exp_BINOPexp *)exp)->_2,cnf,neg); exp = ((Exp_BINOPexp *)exp)->_3;
 240 #line 93 "infgen.pcc"
 241                      } else {
 242                          goto L3; }
 243 }
 244                      else { goto L3; }
 245                   }
 246                } else {
 247
 248                   if (_less_string(((Exp_BINOPexp *)exp)->_1,"==")) {
 249                      if (_equal_string(((Exp_BINOPexp *)exp)->_1,"!=")) {
 250                      if (
 251 #line 99 "infgen.pcc"
 252                      neg
 253 #line 99 "infgen.pcc"
 254 ) {
 255                          goto L2; } else {
 256
 257                         L11:;
 258 #line 101 "infgen.pcc"
 259                        *cnf = exp; return cnf+1;
 260 #line 101 "infgen.pcc"
 261                      }
 262 }
 263                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"&&")) {
 264                      if (
 265 #line 92 "infgen.pcc"
 266                      (! neg)
 267 #line 92 "infgen.pcc"
 268 ) {
 269                          goto L4; } else {
 270                          goto L11; }
 271 }
 272                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"<")) {
 273                      if (
 274 #line 96 "infgen.pcc"
 275                      neg
 276 #line 96 "infgen.pcc"
 277 ) {
 278                          goto L5; } else {
 279                          goto L11; }
 280 }
 281                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"<=")) {
 282                      if (
 283 #line 97 "infgen.pcc"
 284                      neg
 285 #line 97 "infgen.pcc"
 286 ) {
 287                          goto L6; } else {
 288                          goto L11; }
 289 }
 290                      else { goto L11; }
 291                   } else {
 292                      if (_equal_string(((Exp_BINOPexp *)exp)->_1,"==")) {
 293                      if (
 294 #line 98 "infgen.pcc"
 295                      neg
 296 #line 98 "infgen.pcc"
 297 ) {
 298                          goto L7; } else {
 299                          goto L11; }
 300 }
 301                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,">")) {
 302                      if (
 303 #line 94 "infgen.pcc"
 304                      neg
 305 #line 94 "infgen.pcc"
 306 ) {
 307                          goto L8; } else {
 308                          goto L11; }
 309 }
 310                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,">=")) {
 311                      if (
 312 #line 95 "infgen.pcc"
 313                      neg
 314 #line 95 "infgen.pcc"
 315 ) {
 316                          goto L9; } else {
 317                          goto L11; }
 318 }
 319                      else if (_equal_string(((Exp_BINOPexp *)exp)->_1,"||")) {
 320                      if (
 321 #line 93 "infgen.pcc"
 322                      neg
 323 #line 93 "infgen.pcc"
 324 ) {
 325                          goto L10; } else {
 326                          goto L11; }
 327 }
 328                      else { goto L11; }
 329                   }
 330                }
 331                } break;
 332             case a_Exp::tag_PREFIXexp: {
 333                if (
 334 #line 100 "infgen.pcc"
 335                neg
 336 #line 100 "infgen.pcc"
 337 ) {
 338
 339                   if (_equal_string(((Exp_PREFIXexp *)exp)->_1,"!")) {
 340                   L12:;
 341 #line 91 "infgen.pcc"
 342                  exp = ((Exp_PREFIXexp *)exp)->_2; neg = !neg;
 343 #line 91 "infgen.pcc"
 344 }
 345                   else { goto L3; }
 346                } else {
 347
 348                   if (_equal_string(((Exp_PREFIXexp *)exp)->_1,"!")) { goto L12; }
 349                   else { goto L11; }
 350                }
 351                } break;
 352             case a_Exp::tag_MARKEDexp: {
 353 #line 90 "infgen.pcc"
 354               exp = ((Exp_MARKEDexp *)exp)->_2;
 355 #line 90 "infgen.pcc"
 356                } break;
 357             default: {
 358                L13:;
 359                if (
 360 #line 100 "infgen.pcc"
 361                neg
 362 #line 100 "infgen.pcc"
 363 ) {
 364                    goto L3; } else {
 365                    goto L11; }
 366                } break;
 367          }
 368       } else { goto L13; }
 369    }
 370 }
 371 #line 102 "infgen.pcc"
 372 #line 102 "infgen.pcc"
 373
 374 }
 375
 376 ///////////////////////////////////////////////////////////////////////////////
 377 //
 378 //  Returns true if an expression involves only one object.
 379 //  Also returns the highest numbered object involved.
 380 //  As a convention, the object number is -1 if the expression is a constant.
 381 //
 382 ///////////////////////////////////////////////////////////////////////////////
 383 Bool partition(Exp exp, int &obj)
 384 {
 385 #line 113 "infgen.pcc"
 386 #line 140 "infgen.pcc"
 387 {
 388    if (exp) {
 389       switch (exp->tag__) {
 390          case a_Exp::tag_RELexp: {
 391 #line 124 "infgen.pcc"
 392            obj = ((Exp_RELexp *)exp)->RELexp; return true;
 393 #line 124 "infgen.pcc"
 394             } break;
 395          case a_Exp::tag_DOTexp: {
 396 #line 119 "infgen.pcc"
 397            return partition(((Exp_DOTexp *)exp)->_1,obj);
 398 #line 119 "infgen.pcc"
 399             } break;
 400          case a_Exp::tag_SELECTORexp: {
 401 #line 118 "infgen.pcc"
 402            return partition(((Exp_SELECTORexp *)exp)->_1,obj);
 403 #line 118 "infgen.pcc"
 404             } break;
 405          case a_Exp::tag_DEREFexp: {
 406 #line 117 "infgen.pcc"
 407            return partition(((Exp_DEREFexp *)exp)->DEREFexp,obj);
 408 #line 117 "infgen.pcc"
 409             } break;
 410          case a_Exp::tag_ARROWexp: {
 411 #line 120 "infgen.pcc"
 412            return partition(((Exp_ARROWexp *)exp)->_1,obj);
 413 #line 120 "infgen.pcc"
 414             } break;
 415          case a_Exp::tag_INDEXexp: {
 416 #line 126 "infgen.pcc"
 417            return partition(((Exp_INDEXexp *)exp)->_1,((Exp_INDEXexp *)exp)->_2,obj);
 418 #line 126 "infgen.pcc"
 419             } break;
 420          case a_Exp::tag_BINOPexp: {
 421 #line 128 "infgen.pcc"
 422            return partition(((Exp_BINOPexp *)exp)->_2,((Exp_BINOPexp *)exp)->_3,obj);
 423 #line 128 "infgen.pcc"
 424             } break;
 425          case a_Exp::tag_PREFIXexp: {
 426 #line 115 "infgen.pcc"
 427            return partition(((Exp_PREFIXexp *)exp)->_2,obj);
 428 #line 115 "infgen.pcc"
 429             } break;
 430          case a_Exp::tag_POSTFIXexp: {
 431 #line 116 "infgen.pcc"
 432            return partition(((Exp_POSTFIXexp *)exp)->_2,obj);
 433 #line 116 "infgen.pcc"
 434             } break;
 435          case a_Exp::tag_APPexp: {
 436 #line 125 "infgen.pcc"
 437            return partition(((Exp_APPexp *)exp)->_1,((Exp_APPexp *)exp)->_2,obj);
 438 #line 125 "infgen.pcc"
 439             } break;
 440          case a_Exp::tag_ASSIGNexp: {
 441 #line 127 "infgen.pcc"
 442            return partition(((Exp_ASSIGNexp *)exp)->_1,((Exp_ASSIGNexp *)exp)->_2,obj);
 443 #line 127 "infgen.pcc"
 444             } break;
 445          case a_Exp::tag_IFexp: {
 446 #line 138 "infgen.pcc"
 447            return partition(
 448 #line 138 "infgen.pcc"
 449 #line 138 "infgen.pcc"
 450             list_1_(((Exp_IFexp *)exp)->_1,list_1_(((Exp_IFexp *)exp)->_2,list_1_(((Exp_IFexp *)exp)->_3)))
 451 #line 138 "infgen.pcc"
 452 #line 138 "infgen.pcc"
 453             ,obj);
 454 #line 138 "infgen.pcc"
 455             } break;
 456          case a_Exp::tag_TUPLEexp: {
 457 #line 132 "infgen.pcc"
 458            return partition(((Exp_TUPLEexp *)exp)->TUPLEexp,obj);
 459 #line 132 "infgen.pcc"
 460             } break;
 461          case a_Exp::tag_RECORDexp: {
 462 #line 133 "infgen.pcc"
 463            return partition(((Exp_RECORDexp *)exp)->RECORDexp,obj);
 464 #line 133 "infgen.pcc"
 465             } break;
 466          case a_Exp::tag_LISTexp: {
 467 #line 136 "infgen.pcc"
 468            return partition(
 469 #line 136 "infgen.pcc"
 470 #line 136 "infgen.pcc"
 471             list_1_(((Exp_LISTexp *)exp)->_4,((Exp_LISTexp *)exp)->_3)
 472 #line 136 "infgen.pcc"
 473 #line 136 "infgen.pcc"
 474             , obj);
 475 #line 136 "infgen.pcc"
 476             } break;
 477          case a_Exp::tag_VECTORexp: {
 478 #line 135 "infgen.pcc"
 479            return partition(((Exp_VECTORexp *)exp)->_2,obj);
 480 #line 135 "infgen.pcc"
 481             } break;
 482          case a_Exp::tag_CONSexp: {
 483 #line 121 "infgen.pcc"
 484            return partition(((Exp_CONSexp *)exp)->_3,obj);
 485 #line 121 "infgen.pcc"
 486             } break;
 487          case a_Exp::tag_CASTexp: {
 488 #line 123 "infgen.pcc"
 489            return partition(((Exp_CASTexp *)exp)->_2,obj);
 490 #line 123 "infgen.pcc"
 491             } break;
 492          case a_Exp::tag_EQexp: {
 493 #line 129 "infgen.pcc"
 494            return partition(((Exp_EQexp *)exp)->_2,((Exp_EQexp *)exp)->_3,obj);
 495 #line 129 "infgen.pcc"
 496             } break;
 497          case a_Exp::tag_UNIFYexp: {
 498 #line 130 "infgen.pcc"
 499            return partition(((Exp_UNIFYexp *)exp)->_2,((Exp_UNIFYexp *)exp)->_3,obj);
 500 #line 130 "infgen.pcc"
 501             } break;
 502          case a_Exp::tag_LTexp: {
 503 #line 131 "infgen.pcc"
 504            return partition(((Exp_LTexp *)exp)->_2,((Exp_LTexp *)exp)->_3,obj);
 505 #line 131 "infgen.pcc"
 506             } break;
 507          case a_Exp::tag_HASHexp: {
 508 #line 122 "infgen.pcc"
 509            return partition(((Exp_HASHexp *)exp)->_2,obj);
 510 #line 122 "infgen.pcc"
 511             } break;
 512          case a_Exp::tag_SENDexp: {
 513 #line 134 "infgen.pcc"
 514            return partition(((Exp_SENDexp *)exp)->_2,obj);
 515 #line 134 "infgen.pcc"
 516             } break;
 517          case a_Exp::tag_SETLexp: {
 518 #line 137 "infgen.pcc"
 519            return partition(((Exp_SETLexp *)exp)->_2,obj);
 520 #line 137 "infgen.pcc"
 521             } break;
 522          case a_Exp::tag_MARKEDexp: {
 523 #line 114 "infgen.pcc"
 524            return partition(((Exp_MARKEDexp *)exp)->_2,obj);
 525 #line 114 "infgen.pcc"
 526             } break;
 527          case a_Exp::tag_LITERALexp:
 528          case a_Exp::tag_IDexp: {
 529             L14:;
 530 #line 139 "infgen.pcc"
 531            obj = -1; return true;
 532 #line 139 "infgen.pcc"
 533             } break;
 534          default: {
 535 #line 140 "infgen.pcc"
 536            bug("partition: %e", exp); return false;
 537 #line 140 "infgen.pcc"
 538             } break;
 539       }
 540    } else { goto L14; }
 541 }
 542 #line 141 "infgen.pcc"
 543 #line 141 "infgen.pcc"
 544
 545 }
 546
 547 ///////////////////////////////////////////////////////////////////////////////
 548 //
 549 //  Categorize two expressions.
 550 //
 551 ///////////////////////////////////////////////////////////////////////////////
 552 Bool partition(Exp e1, Exp e2, int &obj) { return partition(
 553 #line 149 "infgen.pcc"
 554 #line 149 "infgen.pcc"
 555 list_1_(e1,list_1_(e2))
 556 #line 149 "infgen.pcc"
 557 #line 149 "infgen.pcc"
 558 ,obj); }
 559
 560 ///////////////////////////////////////////////////////////////////////////////
 561 //
 562 //  Categorize an list of expressions.
 563 //
 564 ///////////////////////////////////////////////////////////////////////////////
 565 Bool partition(Exps es, int &obj)
 566 {  obj = -1;
 567    Bool single = true;
 568    for_each(Exp, e, es)
 569    {  int obj1 = -1;
 570       if (! partition(e,obj1) || (obj >= 0 && obj1 >= 0 && obj1 != obj))
 571          single = false;
 572       if (obj1 > obj) obj = obj1;
 573    }
 574    return single;
 575 }
 576
 577 ///////////////////////////////////////////////////////////////////////////////
 578 //
 579 //  Categorize an labeled list of expressions.
 580 //
 581 ///////////////////////////////////////////////////////////////////////////////
 582 Bool partition(LabExps es, int &obj)
 583 {  obj = -1;
 584    Bool single = true;
 585    for_each(LabExp, e, es) {
 586       int obj1 = -1;
 587       if (! partition(e.exp,obj1) || (obj >= 0 && obj1 >= 0 && obj1 != obj))
 588          single = false;
 589       if (obj1 > obj) obj = obj1;
 590    }
 591    return single;
 592 }
 593
 594 ///////////////////////////////////////////////////////////////////////////////
 595 //  Create an and expression.
 596 ///////////////////////////////////////////////////////////////////////////////
 597 Exp mkandexp(Exp a, Exp b)
 598 {  if (a == NOexp) return b;
 599    if (b == NOexp) return a;
 600    return BINOPexp("&&",a, b);
 601 }
 602
 603 ///////////////////////////////////////////////////////////////////////////////
 604 //
 605 //  Decompose guard expressions in conjunctive normal form into
 606 //  selections and (theta) joins.
 607 //
 608 //  We are given $n$ objects and $n$ booleans expressions.
 609 //  We want to decompose these $n$ expressions into (at most)
 610 //  $n$ single object selects and (at most) $n$ joins.
 611 //
 612 ///////////////////////////////////////////////////////////////////////////////
 613 int decompose (int n, Exp exps[], Exp selects[], Exp joins[])
 614 {  int i;
 615    int max_object = 0;
 616    for (i = 0; i < n; i++) selects[i] = joins[i] = NOexp;
 617    for (i = 0; i < n; i++) {
 618       debug_msg ("decomposing: %e\n", exps[i]);
 619       Exp cnf[MAX_CONJUNCTS];  // assume we don't have more than 256 conjuncts.
 620       Exp * last = flatten(exps[i], cnf, false); // flatten expression.
 621       int conjuncts = last - cnf;
 622       if (conjuncts > MAX_CONJUNCTS)
 623          bug ("Conjuncts exceeded %i in decompose()", MAX_CONJUNCTS);
 624       for (int j = 0; j < conjuncts; j++) {
 625          int obj;
 626          //////////////////////////////////////////////////////////////////////
 627          // Checks whether the conjunct depends on only one variable.
 628          // If so it can be executed as a guard during pattern matching.
 629          // Otherwise, it is a join and must be executed by the
 630          // RETE engine.  In any case hoist the conjunct as far up as possible
 631          // to minimize the sizes of intermediate relations.
 632          //////////////////////////////////////////////////////////////////////
 633          debug_msg ("partitioning: %e\n", cnf[j]);
 634          Bool depends_on_one_variable = partition(cnf[j],obj);
 635          if (obj < 0) obj = 0;
 636          if (depends_on_one_variable) { // expression is a select
 637             if (selects[obj] == NOexp) selects[obj] = cnf[j];
 638             else selects[obj] = mkandexp(selects[obj],cnf[j]);
 639             debug_msg ("select: %e\n", cnf[j]);
 640          } else { // expression is a join
 641             if (joins[obj] == NOexp) joins[obj] = cnf[j];
 642             else joins[obj] = mkandexp(joins[obj],cnf[j]);
 643             debug_msg ("join: %e\n", cnf[j]);
 644          }
 645          if (obj > max_object) max_object = obj;
 646       }
 647    }
 648    return max_object;
 649 }
 650
 651 ///////////////////////////////////////////////////////////////////////////////
 652 //
 653 //  Decompose a set of pattern matching rules and extract out the joins
 654 //  from each of the guards.
 655 //
 656 ///////////////////////////////////////////////////////////////////////////////
 657 int decompose (MatchRules rules, Exp joins[], Exp guard_exp)
 658 {  Exp guards  [MAX_INFERENCE_RULE_ARITY];
 659    Exp selects [MAX_INFERENCE_RULE_ARITY];
 660    int n = 0;
 661
 662    {  for_each (MatchRule, r, rules)
 663       {
 664 #line 254 "infgen.pcc"
 665 #line 255 "infgen.pcc"
 666 {
 667 #line 255 "infgen.pcc"
 668   guards[n++] = r->_3;
 669 #line 255 "infgen.pcc"
 670 }
 671 #line 255 "infgen.pcc"
 672 #line 255 "infgen.pcc"
 673
 674       }
 675    }
 676    guards[n++] = guard_exp;
 677
 678    if (n >= MAX_INFERENCE_RULE_ARITY)
 679       bug ("%Linference rule arity exceeds %i in decompose()",
 680            MAX_INFERENCE_RULE_ARITY);
 681
 682    // take all the guard expressions and decompose them.
 683    int max_object = decompose(n, guards, selects, joins);
 684
 685    // rebuild the guards.  Now they must all involve at most one
 686    // single object.
 687    {  int i = 0;
 688       for_each (MatchRule, r, rules)
 689       {
 690 #line 271 "infgen.pcc"
 691 #line 272 "infgen.pcc"
 692 {
 693 #line 272 "infgen.pcc"
 694   r->_3 = selects[i]; i++;
 695 #line 272 "infgen.pcc"
 696 }
 697 #line 272 "infgen.pcc"
 698 #line 272 "infgen.pcc"
 699
 700       }
 701    }
 702
 703    return n;
 704 }
 705
 706 ///////////////////////////////////////////////////////////////////////////////
 707 //
 708 //  Top level method to compile a set of inference rules.
 709 //
 710 ///////////////////////////////////////////////////////////////////////////////
 711 void InferenceCompiler::gen_inference_rules(Id id, InferenceRules rules)
 712 {  MemPoolMark marker = mem_pool.getMark(); // get heap marker
 713
 714    ////////////////////////////////////////////////////////////////////////////
 715    // Mapping from type id to list of rules.
 716    ////////////////////////////////////////////////////////////////////////////
 717    HashTable rule_map(string_hash, string_equal, 129);
 718    HashTable join_map(integer_hash, integer_equal);
 719
 720    ////////////////////////////////////////////////////////////////////////////
 721    // Map the rules into an array
 722    ////////////////////////////////////////////////////////////////////////////
 723    int             n  = length(rules);
 724    int      max_arity;
 725    InferenceRule * Rs = (InferenceRule *)mem_pool[n * sizeof(InferenceRule)];
 726    { int i = 0; for_each (InferenceRule,r,rules) Rs[i++] = r; }
 727
 728    max_arity = partition_inference_rules(n, Rs, rule_map, join_map);
 729    pr ("const char * %s::name_of() const { return \"%s\"; }\n\n", id, id);
 730    gen_alpha_tests           (id, max_arity, rule_map);
 731    gen_beta_tests            (id, n, Rs, join_map);
 732    gen_inference_actions     (id, rules);
 733    gen_dispatch_table        (id, rule_map);
 734    int m = gen_network_table (id, n, Rs, join_map);
 735    gen_inference_axioms      (id, rules);
 736    gen_inference_constructor (id, m, rule_map);
 737
 738    ////////////////////////////////////////////////////////////////////////////
 739    //  Clean up
 740    ////////////////////////////////////////////////////////////////////////////
 741    mem_pool.setMark(marker); // reclaim memory
 742 }
 743
 744 ///////////////////////////////////////////////////////////////////////////////
 745 //
 746 //  Method to partition the left hand side of each inference rule according
 747 //  to the type of the pattern.  Patterns of the same type are grouped
 748 //  together and compiled using the pattern matching compiler.  The steps are:
 749 //    (a) Decompose the guard expression into selections (predicates on a
 750 //        single object object) and joins (predicates on 2 or more objects.)
 751 //        Both of these are hoisted upward as much as possible.
 752 //    (b) Perform type inference on the pattern.
 753 //    (c) Enter all the rules of the same type in the same entry of the rule
 754 //        map
 755 //
 756 ///////////////////////////////////////////////////////////////////////////////
 757 int partition_inference_rules
 758    (int n, InferenceRule Rs[], HashTable& rule_map, HashTable& join_map)
 759 {  int max_arity = 0;
 760    int node_number = 0;  // node number in network table.
 761    for (int rule_no = 0; rule_no < n; rule_no++)
 762    {  int positive_clauses = 0;
 763       int negative_clauses = 0;
 764
 765 #line 337 "infgen.pcc"
 766 #line 387 "infgen.pcc"
 767 {
 768    InferenceRule _V1 = Rs[rule_no];
 769 #line 339 "infgen.pcc"
 770  int object_count = 0;
 771    Exp joins[MAX_INFERENCE_RULE_ARITY];
 772    // decompose multi-object test
 773    int n = decompose (_V1->_1, joins, _V1->_2);
 774    int i = 0;
 775    for_each (MatchRule, r, _V1->_1)
 776    {  r->set_loc();
 777
 778 #line 346 "infgen.pcc"
 779 #line 380 "infgen.pcc"
 780    {
 781 #line 348 "infgen.pcc"
 782
 783 #line 348 "infgen.pcc"
 784 #line 378 "infgen.pcc"
 785       {
 786          Ty _V2 = (r->ty = type_of(r->_2));
 787          if (_V2) {
 788             switch (_V2->tag__) {
 789                case a_Ty::tag_TYCONty: {
 790                   if (boxed(((Ty_TYCONty *)_V2)->_1)) {
 791                      switch (((Ty_TYCONty *)_V2)->_1->tag__) {
 792                         case a_TyCon::tag_DATATYPEtycon: {
 793                            if (
 794 #line 350 "infgen.pcc"
 795                            (((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->qualifiers & QUALrelation)
 796 #line 350 "infgen.pcc"
 797 ) {
 798
 799 #line 351 "infgen.pcc"
 800                             // add to table
 801                               HashTable::Entry * e = rule_map.lookup(((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->id);
 802                               if (e) rule_map.insert(((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->id,
 803 #line 353 "infgen.pcc"
 804 #line 353 "infgen.pcc"
 805                               list_1_(r,MatchRules(rule_map.value(e)))
 806 #line 353 "infgen.pcc"
 807 #line 353 "infgen.pcc"
 808                               );
 809                               else rule_map.insert(((TyCon_DATATYPEtycon *)((Ty_TYCONty *)_V2)->_1)->id,
 810 #line 354 "infgen.pcc"
 811 #line 354 "infgen.pcc"
 812                               list_1_(r)
 813 #line 354 "infgen.pcc"
 814 #line 354 "infgen.pcc"
 815                               );
 816                               r->rule_number = node_number;
 817                               if (joins[i] != NOexp) {
 818                                  HashTable::Entry * e =
 819                                     join_map.lookup((HashTable::Key)node_number);
 820                                  if (e) {
 821                                     join_map.insert((HashTable::Key)node_number,
 822                                        BINOPexp("&&",(Exp)join_map.value(e),joins[i]));
 823                                  } else {
 824                                     join_map.insert((HashTable::Key)node_number,
 825                                                     joins[i]);
 826                                  }
 827                               }
 828                               if (positive_clauses == 0 && !r->negated) {
 829                                  r->_5 =
 830 #line 368 "infgen.pcc"
 831 #line 368 "infgen.pcc"
 832                               list_1_(INJECTdecl(node_number,LEFTdirection))
 833 #line 368 "infgen.pcc"
 834 #line 368 "infgen.pcc"
 835                               ;
 836                               } else {
 837                                  r->_5 =
 838 #line 370 "infgen.pcc"
 839 #line 370 "infgen.pcc"
 840                               list_1_(INJECTdecl(node_number,RIGHTdirection))
 841 #line 370 "infgen.pcc"
 842 #line 370 "infgen.pcc"
 843                               ;
 844                               node_number++;
 845                               }
 846                               if (r->negated) negative_clauses++;
 847                               else            positive_clauses++;
 848
 849 #line 375 "infgen.pcc"
 850                            } else {
 851
 852                               L15:;
 853 #line 378 "infgen.pcc"
 854                             error("%Lnon-relation type %T in pattern: %p\n", _V2, r->_2);
 855 #line 378 "infgen.pcc"
 856                            }
 857                            } break;
 858                         default: { goto L15; } break;
 859                      }
 860                   } else { goto L15; }
 861                   } break;
 862                default: { goto L15; } break;
 863             }
 864          } else {}
 865       }
 866 #line 379 "infgen.pcc"
 867 #line 379 "infgen.pcc"
 868
 869
 870 #line 380 "infgen.pcc"
 871    }
 872 #line 381 "infgen.pcc"
 873 #line 381 "infgen.pcc"
 874
 875    i++;
 876    object_count++;
 877    }
 878    node_number++;
 879    if (max_arity < object_count) max_arity = object_count;
 880
 881 #line 387 "infgen.pcc"
 882 }
 883 #line 388 "infgen.pcc"
 884 #line 388 "infgen.pcc"
 885
 886    }
 887    return max_arity;
 888 }
 889
 890 ///////////////////////////////////////////////////////////////////////////////
 891 //
 892 //  Method to generate the alpha (single object) tests.
 893 //
 894 ///////////////////////////////////////////////////////////////////////////////
 895 void InferenceCompiler::gen_alpha_tests
 896    (Id id, int max_arity, HashTable& rule_map)
 897 {  pr ("%^%/%^//  Single object tests for inference class %s%^%/"
 898        "%^void %s::alpha_test(int predicate__, int i__, Fact * fact__)"
 899        "%^{%+"
 900        "%^Fact * f__[%i];"
 901        "%^switch (predicate__) {%+", id, id, max_arity);
 902    {  Bool save = same_selectors;
 903       same_selectors = true;
 904       int type_number = 1;
 905       foreach_entry(e, rule_map)
 906       {  Id         ty_name = (Id)rule_map.key(e);
 907          MatchRules rules   = (MatchRules)rule_map.value(e);
 908          pr ("%^case %i: {%+"
 909              "%^%s _0 = (%s)(f__[0] = fact__);",
 910              type_number, ty_name, ty_name);
 911          gen_match_stmt (
 912 #line 414 "infgen.pcc"
 913 #line 414 "infgen.pcc"
 914 nil_1_
 915 #line 414 "infgen.pcc"
 916 #line 414 "infgen.pcc"
 917 , rules, MATCHall | MATCHnocheck);
 918          pr ("} break; %-");
 919          type_number++;
 920       }
 921       same_selectors = save;
 922    }
 923    pr ("%-%^}"
 924        "%-%^}\n\n");
 925 }
 926
 927 ///////////////////////////////////////////////////////////////////////////////
 928 //
 929 //  Method to generate the beta tests(joins)
 930 //
 931 ///////////////////////////////////////////////////////////////////////////////
 932 void InferenceCompiler::gen_beta_tests
 933    (Id id, int n, InferenceRule rules[], HashTable& join_map)
 934 {  pr ("%^%/%^//  Joins for inference class %s%^%/"
 935        "%^int %s::beta_test(Join join__, Fact * f__[])"
 936        "%^{%+"
 937        "%^switch (join__) {%+", id, id);
 938
 939    for (int i = 0; i < n; i++)
 940    {
 941 #line 437 "infgen.pcc"
 942 #line 460 "infgen.pcc"
 943 {
 944    InferenceRule _V3 = rules[i];
 945 #line 439 "infgen.pcc"
 946  for(MatchRules rs = _V3->_1; rs; rs = rs->_2)
 947    {  if (rs->_2 ==
 948 #line 440 "infgen.pcc"
 949 #line 440 "infgen.pcc"
 950    nil_1_
 951 #line 440 "infgen.pcc"
 952 #line 440 "infgen.pcc"
 953   ||
 954    rs->_1->rule_number != rs->_2->_1->rule_number)
 955    {  MatchRule r = rs->_1;
 956    int rule_no = r->rule_number;
 957    HashTable::Entry * e =
 958      join_map.lookup((HashTable::Key)rule_no);
 959    if (e)
 960    {  Exp join = (Exp)join_map.value(e);
 961      int j = 0;
 962      pr ("%^case %i: {%+", rule_no);
 963      for_each (MatchRule, mr, _V3->_1)
 964      {  pr ("%^%t _%i = (%t)f__[%i];",
 965             mr->ty, "", j, mr->ty, "", j);
 966         j++;
 967         if (mr == r) break;
 968      }
 969      pr ("%^return %e;%-%^}", join);
 970    }
 971    }
 972    }
 973
 974 #line 460 "infgen.pcc"
 975 }
 976 #line 461 "infgen.pcc"
 977 #line 461 "infgen.pcc"
 978
 979    }
 980
 981    pr ("%^default: return 0;"
 982        "%-%^}"
 983        "%-%^}\n\n");
 984 }
 985
 986 ///////////////////////////////////////////////////////////////////////////////
 987 //
 988 //  Generate the dispatch table.
 989 //
 990 ///////////////////////////////////////////////////////////////////////////////
 991 void InferenceCompiler::gen_dispatch_table(Id id, HashTable& rule_map)
 992 {  pr ("%^%/%^//  Dispatch table for inference class %s%^%/"
 993        "%^const %s::RelationTable %s::relation_table[] = {%+",
 994        id, id, id);
 995    {  int type_number = 1;
 996       Bool comma = false;
 997       foreach_entry(e, rule_map)
 998       {  Id ty_name = (Id)rule_map.key(e);
 999          if (comma) pr (",");
1000          pr ("%^{ &a_%s::relation_tag, %i, \"%s\" }",
1001              ty_name, type_number, ty_name);
1002          comma = true;
1003          type_number++;
1004       }
1005    }
1006    pr ("%-%^};\n\n");
1007 }
1008
1009 ///////////////////////////////////////////////////////////////////////////////
1010 //
1011 //  Generate the network table.
1012 //
1013 ///////////////////////////////////////////////////////////////////////////////
1014 int InferenceCompiler::gen_network_table
1015    (Id id, int n, InferenceRule rules[], HashTable& join_table)
1016 {  pr ("%^%/%^//  Network table for inference class %s%^%/"
1017        "%^const %s::Node %s::network_table[] = {%+",
1018        id, id, id);
1019
1020    int entries = 0;
1021    Bool comma = false;
1022    for (int i = 0; i < n; i++)
1023    {
1024 #line 506 "infgen.pcc"
1025 #line 532 "infgen.pcc"
1026 {
1027    InferenceRule _V4 = rules[i];
1028 #line 508 "infgen.pcc"
1029  int max_arity = length(_V4->_1);
1030    int last_rule_number = -1;
1031    int arity = 1;
1032    for_each (MatchRule, r, _V4->_1)
1033    {  if (last_rule_number != r->rule_number
1034           && (max_arity > 1 || r->negated) ) {
1035          if (comma) pr (",");
1036          Id  typ  = r->negated ? "Not" : "And";
1037          int join =
1038             join_table.contains((HashTable::Key)r->rule_number)
1039                         ? r->rule_number : 0;
1040          pr ("%^{ %i, %i, ReteNet::Node::%s, %i, %i } /* %i */",
1041              arity, max_arity, typ, join, r->rule_number + 1, entries);
1042          comma = true;
1043          arity++;
1044          entries++;
1045       }
1046       last_rule_number = r->rule_number;
1047    }
1048    if (comma) pr (",");
1049    pr ("%^{ 0, %i, ReteNet::Node::Bot, %i, %i } /* %i */",
1050        max_arity, 0, i, entries);
1051    entries++;
1052    comma = true;
1053
1054 #line 532 "infgen.pcc"
1055 }
1056 #line 533 "infgen.pcc"
1057 #line 533 "infgen.pcc"
1058
1059    }
1060
1061    pr ("%-%^};\n\n");
1062
1063    return entries;
1064 }
1065
1066 ///////////////////////////////////////////////////////////////////////////////
1067 //
1068 //  Generate the axioms of the inference class.
1069 //
1070 ///////////////////////////////////////////////////////////////////////////////
1071 void InferenceCompiler::gen_inference_axioms(Id id, InferenceRules rules)
1072 {
1073    pr ("%^%/%^//  Axioms for inference class %s%^%/"
1074        "%^void %s::initialise_axioms()"
1075        "%^{%+",
1076        id, id);
1077    for_each(InferenceRule, r, rules)
1078    {
1079 #line 553 "infgen.pcc"
1080 #line 556 "infgen.pcc"
1081 {
1082    if (r->_1) {} else {
1083 #line 554 "infgen.pcc"
1084      gen_conclusions(r->_3);
1085 #line 554 "infgen.pcc"
1086    }
1087 }
1088 #line 556 "infgen.pcc"
1089 #line 556 "infgen.pcc"
1090
1091    }
1092    pr ("%-%^}\n\n");
1093 }
1094
1095 ///////////////////////////////////////////////////////////////////////////////
1096 //
1097 //  Generate the action routine of the inference class
1098 //
1099 ///////////////////////////////////////////////////////////////////////////////
1100 void InferenceCompiler::gen_inference_actions(Id id, InferenceRules rules)
1101 {
1102    pr ("%^%/%^//  Actions for inference class %s%^%/"
1103        "%^void %s::action(%s::RuleId r__, Fact * f__[])"
1104        "%^{%+"
1105        "%^switch (r__) {%+",
1106        id, id, id);
1107
1108    int rule_no = 0;
1109    for_each(InferenceRule, r, rules)
1110    {
1111 #line 576 "infgen.pcc"
1112 #line 588 "infgen.pcc"
1113 {
1114    if (r->_1) {
1115 #line 578 "infgen.pcc"
1116    pr ("%^case %i: {%+", rule_no);
1117       int i = 0;
1118       for_each (MatchRule, mr, r->_1)
1119       {  pr ("%^%t _%i = (%t)f__[%i];", mr->ty, "", i, mr->ty, "", i);
1120          i++;
1121       }
1122       gen_conclusions(r->_3);
1123       pr ("%-%^} break;");
1124
1125 #line 586 "infgen.pcc"
1126    } else {}
1127 }
1128 #line 588 "infgen.pcc"
1129 #line 588 "infgen.pcc"
1130
1131       rule_no++;
1132    }
1133    pr ("%-%^}"
1134        "%-%^}\n\n");
1135 }
1136
1137 ///////////////////////////////////////////////////////////////////////////////
1138 //
1139 //  Generate the conclusions of the inference class.
1140 //
1141 ///////////////////////////////////////////////////////////////////////////////
1142 void InferenceCompiler::gen_conclusions(Conclusions cs)
1143 {  for_each (Conclusion, c, cs) gen_conclusion(c); }
1144
1145 ///////////////////////////////////////////////////////////////////////////////
1146 //
1147 //  Generate one conclusion of the inference class.
1148 //
1149 ///////////////////////////////////////////////////////////////////////////////
1150 void InferenceCompiler::gen_conclusion(Conclusion c)
1151 {
1152 #line 609 "infgen.pcc"
1153 #line 612 "infgen.pcc"
1154 {
1155    switch (untagp(c)) {
1156       case a_Conclusion::tag_ASSERTaction: {
1157 #line 610 "infgen.pcc"
1158         pr ("%^assert_fact(%e);\n", ((Conclusion_ASSERTaction *)c)->ASSERTaction);
1159 #line 610 "infgen.pcc"
1160          } break;
1161       case a_Conclusion::tag_RETRACTaction: {
1162 #line 611 "infgen.pcc"
1163         pr ("%^retract_fact(%e);\n", ((Conclusion_RETRACTaction *)derefp(c))->RETRACTaction);
1164 #line 611 "infgen.pcc"
1165          } break;
1166       default: {
1167 #line 612 "infgen.pcc"
1168         pr ("%^%&", ((Conclusion_STMTaction *)derefp(c))->STMTaction);
1169 #line 612 "infgen.pcc"
1170          } break;
1171    }
1172 }
1173 #line 613 "infgen.pcc"
1174 #line 613 "infgen.pcc"
1175
1176 }
1177
1178 ///////////////////////////////////////////////////////////////////////////////
1179 //
1180 //  Generate the constructor of the inference class.
1181 //
1182 ///////////////////////////////////////////////////////////////////////////////
1183 void InferenceCompiler::gen_inference_constructor
1184    (Id id, int entries, HashTable& rule_map)
1185 {
1186    pr ("%^%/%^//  Constructor for inference class %s%^%/"
1187        "%^%s::%s()%+"
1188        "%^: Rete(%i,%s::network_table,%i,%s::relation_table)%+"
1189        "%^{ initialise_axioms(); }%-%-\n\n",
1190        id, id, id,
1191        entries, id, rule_map.size(), id);
1192 }
1193
1194 ///////////////////////////////////////////////////////////////////////////////
1195 //
1196 //  Generate the interface of a relation object.
1197 //
1198 ///////////////////////////////////////////////////////////////////////////////
1199 void DatatypeClass::generate_inference_interface(CodeGen& C)
1200 {
1201    if (this != root) return;
1202
1203    C.pr("%^%/"
1204         "%^//"
1205         "%^// Inference methods"
1206         "%^//"
1207         "%^%/"
1208         "%^static RelTag relation_tag;"
1209         "%^virtual RelTag get_tag() const;"
1210        );
1211 }
1212
1213 ///////////////////////////////////////////////////////////////////////////////
1214 //
1215 //  Generate the implementation of a relation object.
1216 //
1217 ///////////////////////////////////////////////////////////////////////////////
1218 void DatatypeClass::generate_inference_implementation
1219    (CodeGen& C, Tys tys, DefKind k)
1220 {
1221    if (this != root) return;
1222
1223    C.pr("%^%/"
1224         "%^//"
1225         "%^// Relation datatype %s%P"
1226         "%^//"
1227         "%^%/"
1228         "%^Fact::RelTag %s%P::relation_tag = 0;"
1229         "%^static InitialiseFact %s_dummy__(%s%P::relation_tag);"
1230         "%^Fact::RelTag %s%P::get_tag() const"
1231         " { return %s%P::relation_tag; }\n \n",
1232         root->datatype_name, tys,
1233         class_name, tys,
1234         DatatypeCompiler::temp_vars.new_label(), class_name, tys,
1235         class_name, tys,
1236         class_name, tys
1237        );
1238 }
1239 #line 677 "infgen.pcc"
1240 /*
1241 ------------------------------- Statistics -------------------------------
1242 Merge matching rules         = yes
1243 Number of DFA nodes merged   = 169
1244 Number of ifs generated      = 46
1245 Number of switches generated = 5
1246 Number of labels             = 14
1247 Number of gotos              = 36
1248 Adaptive matching            = enabled
1249 Fast string matching         = disabled
1250 Inline downcasts             = enabled
1251 --------------------------------------------------------------------------
1252 */