Repair/RepairCompiler/MCC/IR/AbstractInterferes.java

   1 package MCC.IR;
   2 import java.util.*;
   3
   4 class AbstractInterferes {
   5     Termination termination;
   6
   7     public AbstractInterferes(Termination t) {
   8         termination=t;
   9     }
  10
  11     /** Does performing the AbstractRepair ar satisfy (or falsify if satisfy=false)
  12      * Rule r. */
  13
  14     static public boolean interfereswithrule(AbstractRepair ar, Rule r, boolean satisfy) {
  15         boolean mayadd=false;
  16         boolean mayremove=false;
  17         switch (ar.getType()) {
  18         case AbstractRepair.ADDTOSET:
  19         case AbstractRepair.ADDTORELATION:
  20             if (interferesquantifier(ar.getDescriptor(), true, r, satisfy))
  21                 return true;
  22             mayadd=true;
  23             break;
  24         case AbstractRepair.REMOVEFROMSET:
  25         case AbstractRepair.REMOVEFROMRELATION:
  26             if (interferesquantifier(ar.getDescriptor(), false, r, satisfy))
  27                 return true;
  28             mayremove=true;
  29             break;
  30         case AbstractRepair.MODIFYRELATION:
  31             if (interferesquantifier(ar.getDescriptor(), true, r, satisfy))
  32                 return true;
  33             if (interferesquantifier(ar.getDescriptor(), false, r, satisfy))
  34                 return true;
  35             mayadd=true;
  36             mayremove=true;
  37         break;
  38         default:
  39             throw new Error("Unrecognized Abstract Repair");
  40         }
  41         DNFRule drule=null;
  42         if (satisfy)
  43             drule=r.getDNFGuardExpr();
  44         else
  45             drule=r.getDNFNegGuardExpr();
  46
  47         for(int i=0;i<drule.size();i++) {
  48             RuleConjunction rconj=drule.get(i);
  49             for(int j=0;j<rconj.size();j++) {
  50                 DNFExpr dexpr=rconj.get(j);
  51                 Expr expr=dexpr.getExpr();
  52                 if (expr.usesDescriptor(ar.getDescriptor())) {
  53                     /* Need to check */
  54                     if ((mayadd&&!dexpr.getNegation())||(mayremove&&dexpr.getNegation()))
  55                         return true;
  56                 }
  57             }
  58         }
  59         return false;
  60     }
  61
  62     public boolean checkrelationconstraint(AbstractRepair ar, Constraint c) {
  63         if (c.numQuantifiers()==1&&
  64             (c.getQuantifier(0) instanceof RelationQuantifier)) {
  65             RelationQuantifier rq=(RelationQuantifier)c.getQuantifier(0);
  66             if (rq.getRelation()==ar.getDescriptor()) {
  67                 Hashtable ht=new Hashtable();
  68                 if (ar.getDomainSet()!=null)
  69                     ht.put(rq.x,ar.getDomainSet());
  70                 if (ar.getRangeSet()!=null)
  71                     ht.put(rq.y,ar.getRangeSet());
  72                 DNFConstraint dconst=c.dnfconstraint;
  73             conjloop:
  74                 for(int i=0;i<dconst.size();i++) {
  75                     Conjunction conj=dconst.get(i);
  76                 predloop:
  77                     for(int j=0;j<conj.size();j++) {
  78                         DNFPredicate dpred=conj.get(j);
  79                         Predicate p=dpred.getPredicate();
  80                         if ((p instanceof InclusionPredicate)&&(!dpred.isNegated())) {
  81                             InclusionPredicate ip=(InclusionPredicate)p;
  82                             if (ip.expr instanceof VarExpr&&
  83                                 ip.setexpr.getDescriptor() instanceof SetDescriptor) {
  84                                 VarDescriptor vd=((VarExpr)ip.expr).getVar();
  85                                 if (ht.containsKey(vd)) {
  86                                     SetDescriptor td=(SetDescriptor)ip.setexpr.getDescriptor();
  87                                     SetDescriptor s=(SetDescriptor)ht.get(vd);
  88                                     if (td.isSubset(s))
  89                                         continue predloop;
  90                                 }
  91                             }
  92                         }
  93                         continue conjloop;
  94                     }
  95                     return true;
  96                 }
  97             }
  98         }
  99         return false;
 100     }
 101
 102     /** Does performing the AbstractRepair ar falsify the predicate dp */
 103
 104     public boolean interfereswithpredicate(AbstractRepair ar, DNFPredicate dp) {
 105         if ((ar.getDescriptor()!=dp.getPredicate().getDescriptor()) &&
 106             ((ar.getDescriptor() instanceof SetDescriptor)||
 107              !dp.getPredicate().usesDescriptor((RelationDescriptor)ar.getDescriptor())))
 108             return false;
 109
 110         /* This if handles all the c comparisons in the paper */
 111         if (ar.getDescriptor()==dp.getPredicate().getDescriptor()&&
 112             (ar.getType()==AbstractRepair.ADDTOSET||ar.getType()==AbstractRepair.ADDTORELATION)&&
 113             (ar.getPredicate().getPredicate() instanceof ExprPredicate)&&
 114             (dp.getPredicate() instanceof ExprPredicate)&&
 115             (dp.getPredicate().inverted()==ar.getPredicate().getPredicate().inverted())&&
 116             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 117             boolean neg1=ar.getPredicate().isNegated();
 118             Opcode op1=((ExprPredicate)ar.getPredicate().getPredicate()).getOp();
 119             int size1=((ExprPredicate)ar.getPredicate().getPredicate()).rightSize();
 120             boolean neg2=dp.isNegated();
 121             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 122             int size2=((ExprPredicate)dp.getPredicate()).rightSize();
 123             op1=Opcode.translateOpcode(neg1,op1);
 124             op2=Opcode.translateOpcode(neg2,op2);
 125
 126             if ((op1==Opcode.EQ)||(op1==Opcode.NE)||(op1==Opcode.GT)||op1==Opcode.GE) {
 127                 int size1a=0;
 128                 if((op1==Opcode.EQ)||(op1==Opcode.GE))
 129                     size1a=size1;
 130                 if((op1==Opcode.GT)||(op1==Opcode.NE))
 131                     size1a=size1+1;
 132
 133                 if (((op2==Opcode.EQ)&&(size1a==size2))||
 134                     ((op2==Opcode.NE)&&(size1a!=size2))||
 135                     (op2==Opcode.GE)||
 136                     (op2==Opcode.GT)||
 137                     ((op2==Opcode.LE)&&(size1a<=size2))||
 138                     ((op2==Opcode.LT)&&(size1a<size2)))
 139                     return false;
 140             }
 141         }
 142         if (ar.getDescriptor()==dp.getPredicate().getDescriptor()&&
 143             (ar.getType()==AbstractRepair.ADDTOSET||ar.getType()==AbstractRepair.ADDTORELATION)&&
 144             (dp.getPredicate() instanceof ExprPredicate)&&
 145             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 146             boolean neg2=dp.isNegated();
 147             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 148             int size2=((ExprPredicate)dp.getPredicate()).rightSize();
 149
 150             op2=Opcode.translateOpcode(neg2,op2);
 151
 152             int maxsize=termination.maxsize.getsize(dp.getPredicate().getDescriptor());
 153
 154             if ((maxsize!=-1)&&
 155                 ((op2==Opcode.LT&&size2>maxsize)||
 156                  (op2==Opcode.LE&&size2>=maxsize)||
 157                  (op2==Opcode.EQ&&size2>=maxsize)))
 158                 return false;
 159
 160             if (((op2==Opcode.NE)&&(size2==0))||
 161                 (op2==Opcode.GE)||
 162                 (op2==Opcode.GT))
 163                 return false;
 164         }
 165         if (ar.getDescriptor()==dp.getPredicate().getDescriptor()&&
 166             (ar.getType()==AbstractRepair.MODIFYRELATION)&&
 167             (dp.getPredicate() instanceof ExprPredicate)&&
 168             (dp.getPredicate().inverted()==ar.getPredicate().getPredicate().inverted())&&
 169             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.COMPARISON)) {
 170
 171             boolean neg1=ar.getPredicate().isNegated();
 172             Opcode op1=((ExprPredicate)ar.getPredicate().getPredicate()).getOp();
 173             boolean isInt1=((ExprPredicate)ar.getPredicate().getPredicate()).isRightInt();
 174             int size1=isInt1?((ExprPredicate)ar.getPredicate().getPredicate()).rightSize():0;
 175             Expr expr1=((OpExpr)((ExprPredicate)ar.getPredicate().getPredicate()).expr).right;
 176
 177
 178             boolean neg2=dp.isNegated();
 179             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 180             boolean isInt2=((ExprPredicate)dp.getPredicate()).isRightInt();
 181             int size2=isInt2?((ExprPredicate)dp.getPredicate()).rightSize():0;
 182             Expr expr2=((OpExpr)((ExprPredicate)dp.getPredicate()).expr).right;
 183
 184             {
 185                 Expr lexpr1=((RelationExpr)((OpExpr)((ExprPredicate)ar.getPredicate().getPredicate()).expr).getLeftExpr()).getExpr();
 186                 Expr lexpr2=((RelationExpr)((OpExpr)((ExprPredicate)dp.getPredicate()).expr).getLeftExpr()).getExpr();
 187                 SetDescriptor sd1=lexpr1.getSet();
 188                 SetDescriptor sd2=lexpr2.getSet();
 189                 if (termination.mutuallyexclusive(sd1,sd2))
 190                     return false;
 191             }
 192
 193             /* Translate the opcodes */
 194             op1=Opcode.translateOpcode(neg1,op1);
 195             op2=Opcode.translateOpcode(neg2,op2);
 196
 197             /* Obvious cases which can't interfere */
 198             if (((op1==Opcode.GT)||
 199                 (op1==Opcode.GE))&&
 200                 ((op2==Opcode.GT)||
 201                  (op2==Opcode.GE)))
 202                 return false;
 203             if (((op1==Opcode.LT)||
 204                 (op1==Opcode.LE))&&
 205                 ((op2==Opcode.LT)||
 206                  (op2==Opcode.LE)))
 207                 return false;
 208             if (((op1==Opcode.EQ)||(op1==Opcode.GE)||(op1==Opcode.LE))&&
 209                 ((op2==Opcode.EQ)||(op2==Opcode.GE)||(op2==Opcode.LE))&&
 210                 expr1.equals(null,expr2)) {
 211                 return false;
 212             }
 213             if (isInt1&&isInt2) {
 214                 if (((op1==Opcode.EQ)||(op1==Opcode.GE)||(op1==Opcode.LE))&&
 215                     ((op2==Opcode.EQ)||(op2==Opcode.GE)||(op2==Opcode.LE))&&
 216                     size1==size2)
 217                     return false;
 218                 int size1a=size1;
 219                 int size2a=size2;
 220                 if (op1==Opcode.GT)
 221                     size1a++;
 222                 if (op1==Opcode.LT)
 223                     size1a--;
 224                 if (op1==Opcode.NE)
 225                     size1a++; /*FLAGNE this is current behavior for NE repairs */
 226
 227                 if (op2==Opcode.GT)
 228                     size2a++;
 229                 if (op2==Opcode.LT)
 230                     size2a--;
 231                 if (((op1==Opcode.GE)||(op1==Opcode.GT))&&
 232                     ((op2==Opcode.LE)||(op2==Opcode.EQ)||(op2==Opcode.LT))&&
 233                     (size1a<=size2a))
 234                     return false;
 235                 if (((op1==Opcode.LE)||(op1==Opcode.LT))&&
 236                     ((op2==Opcode.GE)||(op2==Opcode.EQ)||(op2==Opcode.GT))&&
 237                     (size1a>=size2a))
 238                     return false;
 239                 if ((op1==Opcode.EQ)&&(op2==Opcode.EQ)&&
 240                     (size1a==size2a))
 241                     return false;
 242                 if ((op1==Opcode.EQ)&&
 243                     ((op2==Opcode.LE)||(op2==Opcode.LT))&&
 244                     (size1a<=size2a))
 245                     return false;
 246                 if ((op1==Opcode.EQ)&&
 247                     ((op2==Opcode.GE)||(op2==Opcode.GT))&&
 248                     (size1a>=size2a))
 249                     return false;
 250                 if (op2==Opcode.NE)  /*FLAGNE this is current behavior for NE repairs */
 251                     if (size1a!=size2)
 252                         return false;
 253                 if ((op1==Opcode.NE)&&
 254                     (op2==Opcode.EQ)&&
 255                     (size1!=size2))
 256                     return false;
 257                 if ((op1==Opcode.NE)&& /* FLAGNE relies on increasing or decreasing by 1 */
 258                     ((op2==Opcode.GT)||(op2==Opcode.GE))&&
 259                     (size1!=size2a))
 260                     return false;
 261                 if ((op1==Opcode.NE)&& /* FLAGNE relies on increasing or decreasing by 1 */
 262                     ((op2==Opcode.LT)||(op2==Opcode.LE))&&
 263                     (size1!=size2a))
 264                     return false;
 265             }
 266         }
 267         /* This handles all the c comparisons in the paper */
 268         if (ar.getDescriptor()==dp.getPredicate().getDescriptor()&&
 269             (ar.getType()==AbstractRepair.REMOVEFROMSET||ar.getType()==AbstractRepair.REMOVEFROMRELATION)&&
 270             (ar.getPredicate().getPredicate() instanceof ExprPredicate)&&
 271             (dp.getPredicate() instanceof ExprPredicate)&&
 272             (dp.getPredicate().inverted()==ar.getPredicate().getPredicate().inverted())&&
 273             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 274             boolean neg1=ar.getPredicate().isNegated();
 275             Opcode op1=((ExprPredicate)ar.getPredicate().getPredicate()).getOp();
 276             int size1=((ExprPredicate)ar.getPredicate().getPredicate()).rightSize();
 277             boolean neg2=dp.isNegated();
 278             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 279             int size2=((ExprPredicate)dp.getPredicate()).rightSize();
 280             /* Translate the opcodes */
 281             op1=Opcode.translateOpcode(neg1,op1);
 282             op2=Opcode.translateOpcode(neg2,op2);
 283
 284             if (((op1==Opcode.EQ)||(op1==Opcode.LT)||op1==Opcode.LE)||(op1==Opcode.NE)) {
 285                 int size1a=0;
 286
 287                 if((op1==Opcode.EQ)||(op1==Opcode.LE))
 288                     size1a=size1;
 289                 if((op1==Opcode.LT)||(op1==Opcode.NE))
 290                     size1a=size1-1;
 291
 292                 if (((op2==Opcode.EQ)&&(size1a==size2))||
 293                     ((op2==Opcode.NE)&&(size1a!=size2))||
 294                     (op2==Opcode.LE)||
 295                     (op2==Opcode.LT)||
 296                     ((op2==Opcode.GE)&&(size1a>=size2))||
 297                     ((op2==Opcode.GT)&&(size1a>size2)))
 298                     return false;
 299             }
 300         }
 301
 302         if (ar.getDescriptor()==dp.getPredicate().getDescriptor()&&
 303             (ar.getType()==AbstractRepair.REMOVEFROMSET||ar.getType()==AbstractRepair.REMOVEFROMRELATION)&&
 304             (dp.getPredicate() instanceof ExprPredicate)&&
 305             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 306             boolean neg2=dp.isNegated();
 307             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 308             int size2=((ExprPredicate)dp.getPredicate()).rightSize();
 309             op2=Opcode.translateOpcode(neg2,op2);
 310
 311             if (((op2==Opcode.EQ)&&(size2==0))||
 312                 (op2==Opcode.LE)||
 313                 (op2==Opcode.LT))
 314                 return false;
 315         }
 316         if ((ar.getDescriptor()==dp.getPredicate().getDescriptor())&&
 317             (ar.getType()==AbstractRepair.ADDTOSET||ar.getType()==AbstractRepair.ADDTORELATION)&&
 318             (dp.getPredicate() instanceof InclusionPredicate)&&
 319             (dp.isNegated()==false))
 320             return false; /* Could only satisfy this predicate */
 321
 322         if ((ar.getDescriptor()==dp.getPredicate().getDescriptor())&&
 323             (ar.getType()==AbstractRepair.REMOVEFROMSET||ar.getType()==AbstractRepair.REMOVEFROMRELATION)&&
 324             (dp.getPredicate() instanceof InclusionPredicate)&&
 325             (dp.isNegated()==true))
 326             return false; /* Could only satisfy this predicate */
 327         return true;
 328     }
 329
 330     /** Does the increase (or decrease) in scope of a model defintion
 331      * rule represented by sn falsify the predicate dp. */
 332
 333     public boolean scopeinterfereswithpredicate(ScopeNode sn, DNFPredicate dp) {
 334         if (!sn.getSatisfy()&&(sn.getDescriptor() instanceof SetDescriptor)) {
 335             Rule r=sn.getRule();
 336             Set target=r.getInclusion().getTargetDescriptors();
 337             boolean match=false;
 338             for(int i=0;i<r.numQuantifiers();i++) {
 339                 Quantifier q=r.getQuantifier(i);
 340                 if (q instanceof SetQuantifier) {
 341                     SetQuantifier sq=(SetQuantifier) q;
 342                     if (target.contains(sq.getSet())) {
 343                         match=true;
 344                         break;
 345                     }
 346                 }
 347             }
 348             if (match&&
 349                 sn.getDescriptor()==dp.getPredicate().getDescriptor()&&
 350                 (dp.getPredicate() instanceof ExprPredicate)&&
 351                 (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 352                 boolean neg=dp.isNegated();
 353                 Opcode op=((ExprPredicate)dp.getPredicate()).getOp();
 354                 int size=((ExprPredicate)dp.getPredicate()).rightSize();
 355                 op=Opcode.translateOpcode(neg,op);
 356
 357                 if ((op==Opcode.GE)&&
 358                     ((size==0)||(size==1)))
 359                     return false;
 360                 if ((op==Opcode.GT)&&
 361                     (size==0))
 362                     return false;
 363             }
 364         }
 365         return interferes(sn.getDescriptor(), sn.getSatisfy(),dp);
 366     }
 367
 368     /** Does increasing (or decreasing if satisfy=false) the size of
 369      * the set or relation des falsify the predicate dp. */
 370
 371     private boolean interferes(Descriptor des, boolean satisfy, DNFPredicate dp) {
 372         if ((des!=dp.getPredicate().getDescriptor()) &&
 373             ((des instanceof SetDescriptor)||
 374              !dp.getPredicate().usesDescriptor((RelationDescriptor)des)))
 375             return false;
 376
 377         /* This if handles all the c comparisons in the paper */
 378         if (des==dp.getPredicate().getDescriptor()&&
 379             (satisfy)&&
 380             (dp.getPredicate() instanceof ExprPredicate)&&
 381             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 382             boolean neg2=dp.isNegated();
 383             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 384             int size2=((ExprPredicate)dp.getPredicate()).rightSize();
 385             op2=Opcode.translateOpcode(neg2,op2);
 386
 387
 388             int maxsize=termination.maxsize.getsize(dp.getPredicate().getDescriptor());
 389             {
 390                 if ((maxsize!=-1)&&
 391                     ((op2==Opcode.LT&&size2>maxsize)||
 392                      (op2==Opcode.LE&&size2>=maxsize)||
 393                      (op2==Opcode.EQ&&size2>=maxsize)))
 394                     return false;
 395
 396                 if ((op2==Opcode.GE)||
 397                     (op2==Opcode.GT)||
 398                     (op2==Opcode.NE)&&(size2==0))
 399                     return false;
 400             }
 401         }
 402         /* This if handles all the c comparisons in the paper */
 403         if (des==dp.getPredicate().getDescriptor()&&
 404             (!satisfy)&&
 405             (dp.getPredicate() instanceof ExprPredicate)&&
 406             (((ExprPredicate)dp.getPredicate()).getType()==ExprPredicate.SIZE)) {
 407             boolean neg2=dp.isNegated();
 408             Opcode op2=((ExprPredicate)dp.getPredicate()).getOp();
 409             int size2=((ExprPredicate)dp.getPredicate()).rightSize();
 410             op2=Opcode.translateOpcode(neg2,op2);
 411             {
 412                 if (((op2==Opcode.EQ)&&(size2==0))||
 413                     (op2==Opcode.LE)||
 414                     (op2==Opcode.LT))
 415                     return false;
 416             }
 417         }
 418         if ((des==dp.getPredicate().getDescriptor())&&
 419             satisfy&&
 420             (dp.getPredicate() instanceof InclusionPredicate)&&
 421             (dp.isNegated()==false))
 422             return false; /* Could only satisfy this predicate */
 423
 424         if ((des==dp.getPredicate().getDescriptor())&&
 425             (!satisfy)&&
 426             (dp.getPredicate() instanceof InclusionPredicate)&&
 427             (dp.isNegated()==true))
 428             return false; /* Could only satisfy this predicate */
 429
 430         return true;
 431     }
 432
 433     /** This method test whether satisfying (or falsifying depending
 434      * on the flag satisfy) a rule that adds an object(or tuple) to
 435      * the set(or relation) descriptor may increase (or decrease
 436      * depending on the flag satisfyrule) the scope of a constraint or
 437      * model defintion rule r.  */
 438
 439     static private boolean interferesquantifier(Descriptor des, boolean satisfy, Quantifiers r, boolean satisfyrule) {
 440         for(int i=0;i<r.numQuantifiers();i++) {
 441             Quantifier q=r.getQuantifier(i);
 442             if (q instanceof RelationQuantifier||q instanceof SetQuantifier) {
 443                 if (q.getRequiredDescriptors().contains(des)&&(satisfy==satisfyrule))
 444                     return true;
 445             } else if (q instanceof ForQuantifier) {
 446                 if (q.getRequiredDescriptors().contains(des))
 447                     return true;
 448             } else throw new Error("Unrecognized Quantifier");
 449         }
 450         return false;
 451     }
 452
 453     static public boolean interferesquantifier(AbstractRepair ar, Quantifiers q) {
 454         if (ar.getType()==AbstractRepair.ADDTOSET||ar.getType()==AbstractRepair.ADDTORELATION)
 455             return interferesquantifier(ar.getDescriptor(),true,q,true);
 456         return false;
 457     }
 458
 459     static public boolean interfereswithquantifier(Descriptor des, boolean satisfy, Quantifiers q) {
 460         return interferesquantifier(des, satisfy, q,true);
 461     }
 462
 463     static public boolean interfereswithrule(Descriptor des, boolean satisfy, Rule r, boolean satisfyrule) {
 464         if (interferesquantifier(des,satisfy,r,satisfyrule))
 465             return true;
 466         /* Scan DNF form */
 467         DNFRule drule=r.getDNFGuardExpr();
 468         for(int i=0;i<drule.size();i++) {
 469             RuleConjunction rconj=drule.get(i);
 470             for(int j=0;j<rconj.size();j++) {
 471                 DNFExpr dexpr=rconj.get(j);
 472                 Expr expr=dexpr.getExpr();
 473                 boolean negated=dexpr.getNegation();
 474                 /*
 475                   satisfy  negated
 476                   Yes      No             Yes
 477                   Yes      Yes            No
 478                   No       No             No
 479                   No       Yes            Yes
 480                 */
 481                 boolean satisfiesrule=(satisfy^negated);/*XOR of these */
 482                 if (satisfiesrule==satisfyrule) {
 483                     /* Effect is the one being tested for */
 484                     /* Only expr's to be concerned with are TupleOfExpr and
 485                        ElementOfExpr */
 486                     if (expr.getRequiredDescriptors().contains(des)) {
 487                         if (((expr instanceof ElementOfExpr)||
 488                             (expr instanceof TupleOfExpr))&&
 489                             (expr.getRequiredDescriptors().size()==1))
 490                             return true;
 491                         else
 492                             throw new Error("Unrecognized EXPR");
 493                     }
 494                 }
 495             }
 496         }
 497         return false;
 498     }
 499 }