Repair/RepairInterpreter/dmodel.cc

   1 // defines the sets and the relations used
   2
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include "dmodel.h"
   6 #include "set.h"
   7 #include "Relation.h"
   8 #include "Hashtable.h"
   9 #include "model.h"
  10 #include "Guidance.h"
  11
  12
  13 // class DomainSet
  14
  15 DomainSet::DomainSet(char *name) {
  16   setname=name;
  17   flag=0;
  18   this->type=NULL;
  19   numsubsets=0;
  20   subsets=NULL;
  21   set=new WorkSet();
  22 }
  23
  24 void DomainSet::reset() {
  25   delete(set);
  26   set=new WorkSet();
  27 }
  28
  29 char * DomainSet::getelementtype() {
  30   return type;
  31 }
  32
  33 int DomainSet::gettype() {
  34   return flag%DOMAINSET_TYPED;
  35 }
  36
  37 void DomainSet::settype(char *type) {
  38   this->type=type;
  39   flag|=DOMAINSET_TYPED;
  40 }
  41
  42 void DomainSet::setsubsets(char **subsets, int numsubsets) {
  43   this->subsets=subsets;
  44   this->numsubsets=numsubsets;
  45   flag=DOMAINSET_SUBSET;
  46 }
  47
  48 void DomainSet::setpartition(char **subsets, int numsubsets) {
  49   this->subsets=subsets;
  50   this->numsubsets=numsubsets;
  51   flag=DOMAINSET_PARTITION;
  52 }
  53
  54 void DomainSet::print() {
  55   printf("%s",setname);
  56   if (DOMAINSET_TYPED&flag)
  57     printf("(%s)",type);
  58   printf(":");
  59   if (DOMAINSET_PARTITION&flag)
  60     printf("partition ");
  61   for(int i=0;i<numsubsets;i++)
  62     if (i==0)
  63       printf("%s ",subsets[i]);
  64     else
  65       printf("| %s",subsets[i]);
  66   printf("Size: %d",set->size());
  67 }
  68
  69 char * DomainSet::getname() {
  70   return setname;
  71 }
  72
  73 WorkSet * DomainSet::getset() {
  74   return set;
  75 }
  76
  77 int DomainSet::getnumsubsets() {
  78   return numsubsets;
  79 }
  80
  81 char * DomainSet::getsubset(int i) {
  82   return subsets[i];
  83 }
  84
  85
  86
  87
  88 // class DRelation
  89
  90 DRelation::DRelation(char *n, char *d, char *r, int t, bool b) {
  91   domain=d;range=r;type=t;name=n;
  92   relation=new WorkRelation();
  93   staticrel=b;
  94   tokenrange = NULL;
  95 }
  96
  97 void DRelation::reset() {
  98   delete(relation);
  99   relation=new WorkRelation();
 100 }
 101
 102 bool DRelation::isstatic() {
 103   return staticrel;
 104 }
 105
 106 char * DRelation::getdomain() {
 107   return domain;
 108 }
 109
 110 char * DRelation::getrange() {
 111   return range;
 112 }
 113
 114 WorkSet* DRelation::gettokenrange() {
 115   return tokenrange;
 116 }
 117
 118 void DRelation::settokenrange(WorkSet *ws) {
 119   tokenrange = ws;
 120 }
 121
 122
 123
 124 void DRelation::print() {
 125   printf("%s: %s -> %s (",name,domain,range);
 126   if (type&DRELATION_MANYDOMAIN)
 127     printf("M");
 128   else
 129     printf("1");
 130   printf("->");
 131   if (type&DRELATION_MANYRANGE)
 132     printf("M");
 133   else
 134     printf("1");
 135   printf(")");
 136
 137 }
 138
 139 char * DRelation::getname() {
 140   return name;
 141 }
 142
 143 WorkRelation * DRelation::getrelation() {
 144   return relation;
 145 }
 146
 147
 148
 149
 150
 151 // class DomainRelation
 152
 153 DomainRelation::DomainRelation(DomainSet **s, int ns, DRelation **r,int nr) {
 154   sets=s; numsets=ns;
 155   relations=r;numrelations=nr;
 156   settable=new Hashtable((unsigned int (*)(void *)) & hashstring,(int (*)(void *,void *)) &equivalentstrings);
 157   relationtable=new Hashtable((unsigned int (*)(void *)) & hashstring,(int (*)(void *,void *)) &equivalentstrings);
 158   for(int i=0;i<numsets;i++)
 159     settable->put(sets[i]->getname(),sets[i]);
 160   for(int i=0;i<numrelations;i++)
 161     relationtable->put(relations[i]->getname(),relations[i]);
 162 }
 163
 164 void DomainRelation::reset() {
 165   for(int i=0;i<numsets;i++) {
 166     sets[i]->reset();
 167   }
 168   for(int i=0;i<numrelations;i++) {
 169     relations[i]->reset();
 170   }
 171 }
 172
 173 bool DomainRelation::issupersetof(DomainSet *sub,DomainSet *super) {
 174   while(sub!=NULL) {
 175     if (sub==super)
 176       return true;
 177     sub=getsuperset(sub);
 178   }
 179   return false;
 180 }
 181
 182 void DomainRelation::print() {
 183   for(int i=0;i<numsets;i++) {
 184     sets[i]->print();
 185     printf("\n");
 186   }
 187   printf("\n");
 188   for(int i=0;i<numrelations;i++) {
 189     relations[i]->print();
 190     printf("\n");
 191   }
 192 }
 193
 194 DomainSet * DomainRelation::getset(char * setname) {
 195   if (setname!=NULL)
 196     return (DomainSet *)settable->get(setname);
 197   else return NULL;
 198 }
 199
 200 DRelation * DomainRelation::getrelation(char * relationname) {
 201   if (relationname!=NULL)
 202     return (DRelation *)relationtable->get(relationname);
 203   else
 204     return NULL;
 205 }
 206
 207 DomainRelation::~DomainRelation() {
 208   delete(settable);
 209   delete(relationtable);
 210   for(int i=0;i<numsets;i++)
 211     delete(sets[i]);
 212   for(int i=0;i<numrelations;i++)
 213     delete(relations[i]);
 214   delete(sets);
 215   delete(relations);
 216 }
 217
 218 void DomainRelation::addallsubsets(DomainSet *ds, WorkSet *ws) {
 219   WorkSet *tmp=new WorkSet(true);
 220   tmp->addobject(ds);
 221   while(!tmp->isEmpty()) {
 222     DomainSet *s=(DomainSet *)tmp->firstelement();
 223     tmp->removeobject(s);
 224     ws->addobject(s);
 225     for(int j=0;j<s->getnumsubsets();j++) {
 226       tmp->addobject(getset(s->getsubset(j)));
 227     }
 228   }
 229   delete(tmp);
 230 }
 231
 232 WorkSet * DomainRelation::conflictdelsets(char * setname, char * boundset) {
 233   /* Want to know what set removals insertion into "setname" could cause */
 234   if (equivalentstrings(setname,"int"))
 235     return new WorkSet(true);
 236   if (equivalentstrings(setname,"token"))
 237     return new WorkSet(true);
 238   DomainSet *bs=getset(boundset);
 239   WorkSet *wsret=new WorkSet(true);
 240   WorkSet *ws=new WorkSet(true);
 241   while(bs!=NULL) {
 242     ws->addobject(bs);
 243     bs=getsuperset(bs);
 244   }
 245
 246   DomainSet *oldcs=getset(setname);
 247   DomainSet *cs=getsuperset(oldcs);
 248
 249
 250   while(cs!=NULL) {
 251     if (ws->contains(cs)) {
 252       if (cs->gettype()==DOMAINSET_PARTITION &&
 253           !equivalentstrings(cs->getname(),boundset)) {
 254         delete(ws);
 255         delete(wsret);
 256         ws=new WorkSet(true);
 257
 258         DomainSet *bs=getset(boundset);
 259         addallsubsets(bs,ws);
 260         DomainSet *oldbs=bs;
 261         bs=getsuperset(oldbs);
 262         while(bs!=cs) {
 263           ws->addobject(bs);
 264           if (bs->gettype()!=DOMAINSET_PARTITION) {
 265             for(int i=0;i<bs->getnumsubsets();i++) {
 266               DomainSet *tss=getset(bs->getsubset(i));
 267               if (oldbs!=tss) {
 268                 addallsubsets(tss,ws);
 269               }
 270             }
 271           }
 272           oldbs=bs;
 273           bs=getsuperset(oldbs);
 274         }
 275         return ws;
 276       }
 277       break;
 278     }
 279     if (cs->gettype()==DOMAINSET_PARTITION) {
 280       /* We have a partition...got to look at all other subsets */
 281       for(int i=0;i<cs->getnumsubsets();i++) {
 282         if (!equivalentstrings(cs->getsubset(i),oldcs->getname())) {
 283           addallsubsets(getset(cs->getsubset(i)),wsret);
 284         }
 285       }
 286     }
 287     oldcs=cs;
 288     cs=getsuperset(cs);
 289   }
 290   delete(ws);
 291   return wsret;
 292 }
 293
 294 DomainSet * DomainRelation::getsuperset(DomainSet *s) {
 295   char *name=s->getname();
 296   for(int i=0;i<numsets;i++)
 297     for (int j=0;j<sets[i]->getnumsubsets();j++) {
 298       if(equivalentstrings(name,sets[i]->getsubset(j)))
 299         return sets[i];
 300     }
 301   return NULL;
 302 }
 303
 304 WorkSet * DomainRelation::conflictaddsets(char * setname, char *boundset, model *m) {
 305   /* Want to know what set additions insertion into "setname" could cause */
 306   if (equivalentstrings(setname,"int"))
 307     return new WorkSet(true);
 308   if (equivalentstrings(setname,"token"))
 309     return new WorkSet(true);
 310   DomainSet *bs=getset(boundset);
 311   WorkSet *wsret=new WorkSet(true);
 312   WorkSet *ws=new WorkSet(true);
 313   while(bs!=NULL) {
 314     ws->addobject(bs);
 315     bs=getsuperset(bs);
 316   }
 317
 318   Guidance *g=m->getguidance();
 319   DomainSet *ds=getset(g->insertiontoset(setname));
 320   while(ds!=NULL) {
 321     if (ws->contains(ds))
 322       break;
 323     wsret->addobject(ds);
 324     ds=getsuperset(ds);
 325   }
 326
 327   delete(ws);
 328   return wsret;
 329 }
 330
 331 WorkSet * DomainRelation::removeconflictdelsets(char *setname) {
 332   /* Obviously remove from all subsets*/
 333   WorkSet *tmp=new WorkSet(true);
 334   WorkSet *wsret=new WorkSet(true);
 335   tmp->addobject(getset(setname));
 336   while(!tmp->isEmpty()) {
 337     DomainSet *s=(DomainSet *)tmp->firstelement();
 338     tmp->removeobject(s);
 339     wsret->addobject(s);
 340     for(int j=0;j<s->getnumsubsets();j++)
 341       tmp->addobject(getset(s->getsubset(j)));
 342   }
 343   delete(tmp);
 344   return wsret;
 345 }
 346
 347 WorkSet * DomainRelation::removeconflictaddsets(char *setname, model *m) {
 348   /* Remove could cause addition to a new set...*/
 349   DomainSet *ds=getset(setname);
 350   Guidance *g=m->getguidance();
 351   char *settoputin=g->removefromset(setname);
 352   if (settoputin==NULL)
 353     return new WorkSet(true);
 354   return conflictaddsets(settoputin, setname, m);
 355 }
 356
 357 DomainSet * DomainRelation::getsource(DomainSet *s) {
 358   return getsuperset(s);
 359 }
 360
 361 void DomainRelation::addtoset(Element *ele, DomainSet *settoadd, model *m) {
 362   /* Assumption is that object is not in set*/
 363   if(settoadd->getset()->contains(ele)) /* Already in set-no worries */
 364     return;
 365   if(settoadd->gettype()==DOMAINSET_PARTITION) {
 366     /* Have to find subset to add to */
 367     char *subsettoadd=m->getguidance()->insertiontoset(settoadd->getname());
 368     DomainSet *setptr=getset(subsettoadd);
 369     while(setptr!=settoadd) {
 370       setptr->getset()->addobject(ele);
 371       m->triggerrule(ele,setptr->getname());
 372       setptr=getsuperset(setptr);
 373     }
 374   }
 375   settoadd->getset()->addobject(ele);
 376   m->triggerrule(ele,settoadd->getname());
 377   DomainSet *oldptr=settoadd;
 378   DomainSet *ptr=getsuperset(oldptr);
 379   while((ptr!=NULL)&&(!ptr->getset()->contains(ele))) {
 380     ptr->getset()->addobject(ele);
 381     m->triggerrule(ele,ptr->getname());
 382     oldptr=ptr;
 383     ptr=getsuperset(ptr);
 384   }
 385   if(ptr!=NULL&&
 386      ptr->gettype()==DOMAINSET_PARTITION) {
 387     /* may have to do removes....*/
 388     for(int i=0;i<ptr->getnumsubsets();i++) {
 389       char *subset=ptr->getsubset(i);
 390       DomainSet *ptrsubset=getset(subset);
 391       if (oldptr!=ptrsubset&&
 392           ptrsubset->getset()->contains(ele)) {
 393         /* GOT THE ONE*/
 394         WorkSet *ws=new WorkSet(true);
 395         ws->addobject(ptrsubset);
 396         while(!ws->isEmpty()) {
 397           DomainSet *ds=(DomainSet *)ws->firstelement();
 398           ws->removeobject(ds);
 399           if (ds->getset()->contains(ele)) {
 400             for(int j=0;j<ds->getnumsubsets();j++) {
 401               ws->addobject(getset(ds->getsubset(j)));
 402             }
 403             removefromthisset(ele, ds,m);
 404           }
 405         }
 406         delete(ws);
 407         break;
 408       }
 409     }
 410   }
 411 }
 412
 413 void DomainRelation::abstaddtoset(Element *ele, DomainSet *settoadd, model *m) {
 414   /* Assumption is that object is not in set*/
 415   if(settoadd->getset()->contains(ele)) /* Already in set-no worries */
 416     return;
 417   if(settoadd->gettype()==DOMAINSET_PARTITION) {
 418     /* Have to find subset to add to */
 419     char *subsettoadd=m->getguidance()->insertiontoset(settoadd->getname());
 420     DomainSet *setptr=getset(subsettoadd);
 421     while(setptr!=settoadd) {
 422       setptr->getset()->addobject(ele);
 423       m->triggerrule(ele,setptr->getname());
 424       setptr=getsuperset(setptr);
 425     }
 426   }
 427   settoadd->getset()->addobject(ele);
 428   m->triggerrule(ele,settoadd->getname());
 429   DomainSet *oldptr=settoadd;
 430   DomainSet *ptr=getsuperset(oldptr);
 431   while((ptr!=NULL)&&(!ptr->getset()->contains(ele))) {
 432     ptr->getset()->addobject(ele);
 433     m->triggerrule(ele,ptr->getname());
 434     oldptr=ptr;
 435     ptr=getsuperset(ptr);
 436   }
 437 }
 438
 439 void DomainRelation::removefromthisset(Element *ele, DomainSet *ds, model *m) {
 440   ds->getset()->removeobject(ele); /*removed from set*/
 441   /* Next need to search relations */
 442   for(int i=0;i<numrelations;i++) {
 443     DRelation * relation=relations[i];
 444     if (equivalentstrings(relation->getdomain(),ds->getname()))
 445       for(Element *target=(Element *) relation->getrelation()->getobj(ele);target!=NULL;target=(Element *) relation->getrelation()->getobj(ele)) {
 446         relation->getrelation()->remove(ele,target);
 447         if (relation->isstatic()) {
 448           /* Have to actually remove target*/
 449           DomainSet *targetset=getset(relation->getrange());
 450           delfromsetmovetoset(target,targetset,m);
 451         }
 452       }
 453     if (equivalentstrings(relation->getrange(),ds->getname()))
 454       for(Element *target=(Element *) relation->getrelation()->invgetobj(ele);target!=NULL;target=(Element *) relation->getrelation()->invgetobj(ele)) {
 455         relation->getrelation()->remove(target,ele);
 456         if (relation->isstatic()) {
 457           DomainSet *targetset=getset(relation->getdomain());
 458           delfromsetmovetoset(target,targetset,m);
 459         }
 460       }
 461   }
 462 }
 463
 464 void DomainRelation::delfromsetmovetoset(Element *ele,DomainSet *deletefromset,model *m) {
 465   WorkSet *ws=new WorkSet(true);
 466   ws->addobject(deletefromset);
 467   while(!ws->isEmpty()) {
 468     DomainSet *ds=(DomainSet *)ws->firstelement();
 469     ws->removeobject(ds);
 470     if (ds->getset()->contains(ele)) {
 471       for(int j=0;j<ds->getnumsubsets();j++) {
 472         ws->addobject(getset(ds->getsubset(j)));
 473       }
 474       removefromthisset(ele, ds,m);
 475     }
 476   }
 477   delete(ws);
 478   char *mts=m->getguidance()->removefromset(deletefromset->getname());
 479   DomainSet *movetoset=getset(mts);
 480   addtoset(ele, movetoset, m); //Add to the movetoset now...
 481 }
 482
 483 int DomainRelation::getnumrelation() {
 484   return numrelations;
 485 }
 486
 487 DRelation * DomainRelation::getrelation(int i) {
 488   return relations[i];
 489 }
 490
 491
 492 bool DomainRelation::fixstuff() {
 493   bool anychange=false;
 494   /* Guaranteed fixpoint because we keep removing items...finite # of items */
 495   while(true) {
 496     bool changed=false;
 497     for(int i=0;i<numsets;i++) {
 498       if(checksubset(sets[i])) {
 499         changed=true;
 500         anychange=true;
 501       }
 502     }
 503     for(int i=0;i<numrelations;i++) {
 504       if(checkrelations(relations[i])) {
 505         changed=true;
 506         anychange=true;
 507       }
 508     }
 509 #ifdef REPAIR
 510     /* Fix point only necessary if repairing */
 511     if(!changed)
 512 #endif
 513       break;
 514   }
 515   return anychange;
 516 }
 517
 518
 519
 520
 521 /* propagate the changes so that all the subset inclusion and partition
 522    constraints are satisfied. */
 523 bool DomainRelation::checksubset(DomainSet *ds) {
 524   // remove all elements in ds that are not contained by its superset
 525   bool changed=false;
 526   DomainSet *superset=getsuperset(ds);
 527   WorkSet *ws=ds->getset();
 528   WorkSet *wssuper=ds->getset();
 529
 530   void *ele=ws->firstelement();
 531   while(ele!=NULL) {
 532     if (!wssuper->contains(ele)) {
 533       void *old=ele;
 534       ele=ws->getnextelement(ele);
 535       changed=true;
 536 #ifdef REPAIR
 537       ws->removeobject(old);
 538 #endif
 539     } else
 540       ele=ws->getnextelement(ele);
 541   }
 542   /* Superset inclusion property guaranteed */
 543
 544
 545   /* If an element is contained by more than one subset, remove it from
 546      all subsets but the first one.  If an element is not contained by
 547      any subset, remove it from the superset */
 548   if (ds->gettype()==DOMAINSET_PARTITION) {
 549     ele=ws->firstelement();
 550     while(ele!=NULL) {
 551       int inccount=0;
 552       for(int i=0;i<ds->getnumsubsets();i++) {
 553         char *subsetname=ds->getsubset(i);
 554         DomainSet *subset=getset(subsetname);
 555         if (subset->getset()->contains(ele)) {
 556           if (inccount==0)
 557             inccount++;
 558           else {
 559             /* Partition exclusion property */
 560             changed=true;
 561 #ifdef REPAIR
 562             subset->getset()->removeobject(ele);
 563 #endif
 564           }
 565         }
 566       }
 567       if (inccount==0) {
 568         /* Partition inclusion property */
 569         changed=true;
 570 #ifdef REPAIR
 571         ws->removeobject(ele);
 572 #endif
 573       }
 574       ele=ws->getnextelement(ele);
 575     }
 576   }
 577   return changed;
 578 }
 579
 580
 581
 582 bool DomainRelation::checkrelations(DRelation *dr) {
 583   DomainSet  *range=getset(dr->getrange());
 584   DomainSet *domain=getset(dr->getdomain());
 585   WorkSet *rangeset=NULL,*domainset=NULL;
 586   bool changed=false;
 587   if (range!=NULL)
 588     rangeset=range->getset();
 589   if (domain!=NULL)
 590     domainset=domain->getset();
 591   WorkRelation *rel=dr->getrelation();
 592   Tuple ele=rel->firstelement();
 593   while(!ele.isnull()) {
 594     if((domainset!=NULL&&!domainset->contains(ele.left))||
 595          (rangeset!=NULL&&!rangeset->contains(ele.right))) {
 596       void *l=ele.left;
 597       void *r=ele.right;
 598       ele=rel->getnextelement(l,r);
 599       changed=true;
 600 #ifdef REPAIR
 601       rel->remove(l,r);
 602 #endif
 603     } else {
 604       ele=rel->getnextelement(ele.left,ele.right);
 605     }
 606   }
 607   /* Relation is clean now also */
 608   return changed;
 609 }