00001
00002
00003
00004 #include "typing.h"
00005 #include "functions.h"
00006 #define RE_ERROR(x) if(x) {goto error;}
00007 #define RE_ERROR2(x,y) if(x) {localErrorMsg=(y);goto error;}
00008 #define N_BASE_TYPES 6
00009 NodeType baseTypes[N_BASE_TYPES] = {
00010 T_INT,
00011 T_BOOL,
00012 T_DOUBLE,
00013 T_DATETIME,
00014 T_STRING,
00015 T_IRODS,
00016 };
00017 void doNarrow(Node **l, Node **r, int ln, int rn, int flex, Node **nl, Node **nr, int *nln, int *nrn);
00018 Satisfiability createSimpleConstraint(ExprType *a, ExprType *b, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r);
00019 ExprType *createType(ExprType *t, Node **nc, int nn, Hashtable *typingEnv, Hashtable *equivalence, Region *r);
00020 ExprType *getFullyBoundedVar(Region *r);
00021
00022
00023
00024
00025
00026 int typeParameters(ExprType** paramTypes, int len, Node** subtrees, int dynamictyping, Env* funcDesc, Hashtable *symbol_type_table, List *typingConstraints, rError_t *errmsg, Node **errnode, Region *r) {
00027 int i;
00028 for(i=0;i<len;i++) {
00029 paramTypes[i] = dereference(typeExpression3(subtrees[i], dynamictyping, funcDesc, symbol_type_table, typingConstraints, errmsg, errnode, r), symbol_type_table, r);
00030 if(getNodeType(paramTypes[i]) == T_ERROR) {
00031 return i;
00032 }
00033 }
00034 return -1;
00035 }
00036
00037 int tautologyLt(ExprType *type, ExprType *expected) {
00038
00039 if(typeEqSyntatic(type, expected)) {
00040 return 1;
00041 }
00042 if(getNodeType(type)==T_DYNAMIC) {
00043 return 0;
00044 }
00045 if(getNodeType(expected)==T_DYNAMIC) {
00046 return 1;
00047 }
00048 int i;
00049 ExprType a, b;
00050 if (getNodeType(type) == T_VAR) {
00051 if(T_VAR_NUM_DISJUNCTS(type) > 0) {
00052 for(i=0;i<T_VAR_NUM_DISJUNCTS(type);i++) {
00053 setNodeType(&a, getNodeType(T_VAR_DISJUNCT(type,i)));
00054 if(!tautologyLt(&a, expected)) {
00055 return 0;
00056 }
00057 }
00058 return 1;
00059 } else {
00060 return 0;
00061 }
00062
00063 } else if (getNodeType(expected) == T_VAR) {
00064 if(T_VAR_NUM_DISJUNCTS(expected) > 0) {
00065 for(i=0;i<T_VAR_NUM_DISJUNCTS(expected);i++) {
00066 setNodeType(&b, getNodeType(T_VAR_DISJUNCT(expected,i)));
00067 if(!tautologyLt(type, &b)) {
00068 return 0;
00069 }
00070 }
00071 return 1;
00072 } else {
00073 return 0;
00074 }
00075 } else if ((getNodeType(type) == T_CONS && getNodeType(expected) == T_CONS) || (getNodeType(type) == T_TUPLE && getNodeType(expected) == T_TUPLE) ) {
00076 if(getNodeType(type) == T_CONS && strcmp(T_CONS_TYPE_NAME(type), T_CONS_TYPE_NAME(expected))!=0) {
00077 return 0;
00078 }
00079 int i;
00080 for(i=0;i<T_CONS_ARITY(type);i++) {
00081 if(tautologyLt(T_CONS_TYPE_ARG(type, 0), T_CONS_TYPE_ARG(expected, 0))==0) {
00082 return 0;
00083 }
00084 }
00085 return 1;
00086 } else {
00087 return tautologyLtBase(type, expected);
00088 }
00089 }
00090 char *getBaseTypeOrTVarId(ExprType *a, char buf[128]) {
00091 if(isBaseType(a)) {
00092 snprintf(buf, 128, "%s", typeName_ExprType(a));
00093 } else {
00094 getTVarName(T_VAR_ID(a), buf);
00095 }
00096 return buf;
00097 }
00098 int tautologyLtBase(ExprType *a, ExprType *b) {
00099 if(getNodeType(a) == getNodeType(b)) {
00100 return 1;
00101 }
00102 switch(getNodeType(a)) {
00103 case T_INT:
00104 return getNodeType(b) == T_INT ||
00105 getNodeType(b) == T_DOUBLE;
00106 case T_DOUBLE:
00107 case T_BOOL:
00108 case T_STRING:
00109 return getNodeType(a)==getNodeType(b);
00110 case T_IRODS:
00111 return getNodeType(b)==T_IRODS && (a->text==NULL || b->text == NULL || strcmp(a->text, b->text) == 0) ? 1 : 0;
00112 default:
00113 return 0;
00114 }
00115 }
00116 int occursIn(ExprType *var, ExprType *type) {
00117 if(getNodeType(type) == T_VAR) {
00118 return T_VAR_ID(var) == T_VAR_ID(type);
00119 } else {
00120 int i;
00121 for(i=0;i<type->degree;i++) {
00122 if(occursIn(var, type->subtrees[i])) {
00123 return 1;
00124 }
00125 }
00126 return 0;
00127 }
00128 }
00129 ExprType* getEquivalenceClassRep(ExprType *varOrBase, Hashtable *equivalence) {
00130 ExprType *equiv1 = NULL, *equiv2;
00131 char name[128];
00132 equiv2 = varOrBase;
00133 int ref = 0;
00134 while(equiv2 != NULL) {
00135 equiv1 = equiv2;
00136 equiv2 = (ExprType *) lookupFromHashTable(equivalence, getBaseTypeOrTVarId(equiv1, name));
00137 ref ++;
00138 }
00139 if(ref > 1) {
00140 updateInHashTable(equivalence, getBaseTypeOrTVarId(varOrBase, name), equiv1);
00141 }
00142 return equiv1;
00143
00144 }
00145
00146
00147 int occursInEquiv(ExprType *var, ExprType *type, Hashtable *equivalence) {
00148 if(getNodeType(type) == T_VAR && isBaseType(type)) {
00149 ExprType *varEquiv = getEquivalenceClassRep(var, equivalence);
00150 ExprType *typeEquiv = getEquivalenceClassRep(type, equivalence);
00151 return typeEqSyntatic(varEquiv, typeEquiv);
00152 } else {
00153 int i;
00154 for(i=0;i<type->degree;i++) {
00155 if(occursInEquiv(var, type->subtrees[i], equivalence)) {
00156 return 1;
00157 }
00158 }
00159 return 0;
00160 }
00161 }
00162
00163 Satisfiability splitVarR(ExprType *consTuple, ExprType *var, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00164 if(occursInEquiv(var, consTuple, equivalence) || isBaseType(getEquivalenceClassRep(var, equivalence))) {
00165 return ABSURDITY;
00166 }
00167 char tvarname[128];
00168 ExprType **typeArgs = (ExprType **) region_alloc(r, sizeof(ExprType *) * T_CONS_ARITY(consTuple));
00169 int i;
00170 ExprType *type;
00171 for(i=0;i<T_CONS_ARITY(consTuple);i++) {
00172 typeArgs[i] = newTVar(r);
00173 }
00174 if(getNodeType(consTuple) == T_CONS) {
00175 type = newConsType(T_CONS_ARITY(consTuple), T_CONS_TYPE_NAME(consTuple), typeArgs, r);
00176 } else {
00177 type = newTupleType(T_CONS_ARITY(consTuple), typeArgs, r);
00178 }
00179 insertIntoHashTable(typingEnv, getTVarName(T_VAR_ID(var), tvarname), type);
00180 return splitConsOrTuple(consTuple, type, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00181
00182 }
00183 Satisfiability splitVarL(ExprType *var, ExprType *consTuple, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00184 if(occursInEquiv(var, consTuple, equivalence) || isBaseType(getEquivalenceClassRep(var, equivalence))) {
00185 return ABSURDITY;
00186 }
00187 char tvarname[128];
00188 ExprType **typeArgs = (ExprType **) region_alloc(r, sizeof(ExprType *) * T_CONS_ARITY(consTuple));
00189 int i;
00190 ExprType *type;
00191 for(i=0;i<T_CONS_ARITY(consTuple);i++) {
00192 typeArgs[i] = newTVar(r);
00193 }
00194 if(getNodeType(consTuple) == T_CONS) {
00195 type = newConsType(T_CONS_ARITY(consTuple), T_CONS_TYPE_NAME(consTuple), typeArgs, r);
00196 } else {
00197 type = newTupleType(T_CONS_ARITY(consTuple), typeArgs, r);
00198 }
00199 insertIntoHashTable(typingEnv, getTVarName(T_VAR_ID(var), tvarname), type);
00200 return splitConsOrTuple(type, consTuple, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00201
00202 }
00203
00204
00205
00206
00207
00208
00209
00210 Satisfiability simplifyR(ExprType *a, ExprType *b, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00211 ExprType *bm;
00212 if(T_VAR_NUM_DISJUNCTS(b) == 0) {
00213 bm = getFullyBoundedVar(r);
00214 } else {
00215 bm = b;
00216 }
00217 Node *cl[MAX_NUM_DISJUNCTS], *cr[MAX_NUM_DISJUNCTS];
00218 int nln, nrn;
00219 doNarrow(&a, T_VAR_DISJUNCTS(bm), 1, T_VAR_NUM_DISJUNCTS(bm), flex, cl, cr, &nln, &nrn);
00220 ExprType *bn;
00221 if(nrn == 0) {
00222 return ABSURDITY;
00223 } else {
00224 bn = createType(b, cr, nrn, typingEnv, equivalence, r);
00225 if(bn == b) {
00226 return TAUTOLOGY;
00227 }
00228 return createSimpleConstraint(a, bn, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00229 }
00230 }
00231
00232 ExprType *getFullyBoundedVar(Region *r) {
00233 ExprType **ds = (ExprType **) region_alloc(r, sizeof(ExprType *) * N_BASE_TYPES);
00234 int i;
00235 for(i=0;i<N_BASE_TYPES;i++) {
00236 ds[i] = newSimpType(baseTypes[i], r);
00237 }
00238 ExprType *var = newTVar2(N_BASE_TYPES, ds, r);
00239 return var;
00240 }
00241
00242 Satisfiability simplifyL(ExprType *a, ExprType *b, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00243 ExprType *am;
00244 if(T_VAR_NUM_DISJUNCTS(a) == 0) {
00245 am = getFullyBoundedVar(r);
00246 } else {
00247 am = a;
00248 }
00249 Node *cl[MAX_NUM_DISJUNCTS], *cr[MAX_NUM_DISJUNCTS];
00250 int nln, nrn;
00251 doNarrow(T_VAR_DISJUNCTS(am), &b, T_VAR_NUM_DISJUNCTS(am), 1, flex, cl, cr, &nln, &nrn);
00252 ExprType *an;
00253 if(nln == 0) {
00254 return ABSURDITY;
00255 } else {
00256 an = createType(a, cl, nln, typingEnv, equivalence, r);
00257 if(an == a) {
00258 return TAUTOLOGY;
00259 }
00260 return createSimpleConstraint(an, b, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00261 }
00262
00263 }
00264
00265 void addToEquivalenceClass(ExprType *a, ExprType *b, Hashtable *equivalence) {
00266 char name[128];
00267 ExprType *an = getEquivalenceClassRep(a, equivalence);
00268 ExprType *bn = getEquivalenceClassRep(b, equivalence);
00269 if(!typeEqSyntatic(an, bn)) {
00270 if(isBaseType(an)) {
00271 insertIntoHashTable(equivalence, getTVarName(T_VAR_ID(bn), name), an);
00272 } else {
00273 insertIntoHashTable(equivalence, getTVarName(T_VAR_ID(an), name), bn);
00274 }
00275 }
00276 }
00277 void doNarrow(Node **l, Node **r, int ln, int rn, int flex, Node **nl, Node **nr, int *nln, int *nrn) {
00278 Node *retl[MAX_NUM_DISJUNCTS], *retr[MAX_NUM_DISJUNCTS];
00279 int i,k;
00280 for(i=0;i<ln;i++) {
00281 retl[i] = NULL;
00282 }
00283 for(k=0;k<rn;k++) {
00284 retr[k] = NULL;
00285 }
00286 for(k=0;k<rn;k++) {
00287 for(i=0;i<ln;i++) {
00288 if(splitBaseType(l[i], r[k], flex) == TAUTOLOGY) {
00289 retl[i] = l[i];
00290 retr[k] = r[k];
00291 if(getNodeType(l[i]) == T_IRODS && l[i]->text == NULL) {
00292 retl[i] = retr[k];
00293 }
00294 if(getNodeType(r[k]) == T_IRODS && r[k]->text == NULL) {
00295 retr[k] = retl[i];
00296 }
00297
00298 }
00299 }
00300 }
00301 *nln = 0;
00302 for(i=0;i<ln;i++) {
00303 if(retl[i]!=NULL) {
00304 nl[(*nln)++] = retl[i];
00305 }
00306 }
00307 *nrn = 0;
00308 for(k=0;k<rn;k++) {
00309 if(retr[k]!=NULL) {
00310 nr[(*nrn)++] = retr[k];
00311 }
00312 }
00313 }
00314
00315 Satisfiability createSimpleConstraint(ExprType *a, ExprType *b, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00316 char name[128];
00317 if(isBaseType(a) && isBaseType(b)) {
00318 return TAUTOLOGY;
00319 } else {
00320 addToEquivalenceClass(a, b, equivalence);
00321 if(flex) {
00322 listAppend(simpleTypingConstraints, newTypingConstraint(a, newUnaryType(T_FLEX, b, r), TC_LT, node, r), r);
00323 return CONTINGENCY;
00324 } else {
00325 if((getNodeType(a) == T_VAR && T_VAR_NUM_DISJUNCTS(a)==0) || isBaseType(b)) {
00326 insertIntoHashTable(typingEnv, getTVarName(T_VAR_ID(a), name), b);
00327 } else if((getNodeType(b) == T_VAR && T_VAR_NUM_DISJUNCTS(b)==0) || isBaseType(a)) {
00328 insertIntoHashTable(typingEnv, getTVarName(T_VAR_ID(b), name), a);
00329 } else {
00330 insertIntoHashTable(typingEnv, getTVarName(T_VAR_ID(a), name), b);
00331 }
00332 return TAUTOLOGY;
00333 }
00334 }
00335 }
00336 ExprType *createType(ExprType *t, Node **nc, int nn, Hashtable *typingEnv, Hashtable *equivalence, Region *r) {
00337 char name[128];
00338 ExprType *gcd;
00339 if (nn == T_VAR_NUM_DISJUNCTS(t)) {
00340 gcd = t;
00341 } else {
00342 if(nn==1) {
00343 gcd = *nc;
00344 } else {
00345 gcd = newTVar2(nn, nc, r);
00346 }
00347 insertIntoHashTable(typingEnv, getTVarName(T_VAR_ID(t), name), gcd);
00348 addToEquivalenceClass(t, gcd, equivalence);
00349 }
00350 return gcd;
00351 }
00352 Satisfiability narrow(ExprType *type, ExprType *expected, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00353
00354 if(T_VAR_ID(type) == T_VAR_ID(expected)) {
00355 return TAUTOLOGY;
00356 } else if(T_VAR_NUM_DISJUNCTS(type) > 0 && T_VAR_NUM_DISJUNCTS(expected) > 0) {
00357 int nln, nrn;
00358 Node *cl[100], *cr[100];
00359 doNarrow(T_VAR_DISJUNCTS(type), T_VAR_DISJUNCTS(expected), T_VAR_NUM_DISJUNCTS(type), T_VAR_NUM_DISJUNCTS(expected), flex, cl, cr, &nln, &nrn);
00360 ExprType *an;
00361 ExprType *bn;
00362 if(nln == 0 || nrn == 0) {
00363 return ABSURDITY;
00364 } else {
00365 an = createType(type, cl, nln, typingEnv, equivalence, r);
00366 bn = createType(expected, cr, nrn, typingEnv, equivalence, r);
00367 }
00368 return createSimpleConstraint(an, bn, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00369 } else if(T_VAR_NUM_DISJUNCTS(type)==0) {
00370 return createSimpleConstraint(type, expected, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00371 } else {
00372 return createSimpleConstraint(type, expected, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00373 }
00374 }
00375 Satisfiability splitConsOrTuple(ExprType *a, ExprType *b, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00376
00377 if((getNodeType(a) == T_CONS && strcmp(T_CONS_TYPE_NAME(a), T_CONS_TYPE_NAME(b)) != 0) ||
00378 T_CONS_ARITY(a) != T_CONS_ARITY(b)) {
00379 return ABSURDITY;
00380 } else {
00381 int i;
00382 Satisfiability ret = TAUTOLOGY;
00383 for(i=0;i<T_CONS_ARITY(a);i++) {
00384 ExprType *simpa = T_CONS_TYPE_ARG(a, i);
00385 ExprType *simpb = T_CONS_TYPE_ARG(b, i);
00386 Satisfiability sat = simplifyLocally(simpa, simpb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00387 switch(sat) {
00388 case ABSURDITY:
00389 return ABSURDITY;
00390 case TAUTOLOGY:
00391 break;
00392 case CONTINGENCY:
00393 ret = CONTINGENCY;
00394 break;
00395 }
00396
00397 }
00398 return ret;
00399 }
00400 }
00401
00402
00403 int isBaseType(ExprType *t) {
00404 int i;
00405 for(i=0;i<N_BASE_TYPES;i++) {
00406 if(getNodeType(t) == baseTypes[i]) {
00407 return 1;
00408 }
00409 }
00410 return 0;
00411 }
00412
00413 Satisfiability splitBaseType(ExprType *tca, ExprType *tcb, int flex)
00414 {
00415 return (flex && tautologyLtBase(tca, tcb)) ||
00416 (!flex && ((getNodeType(tca) == T_IRODS && getNodeType(tcb) == T_IRODS && (tca->text == NULL || tcb->text == NULL)) ||
00417 typeEqSyntatic(tca, tcb))) ? TAUTOLOGY : ABSURDITY;
00418 }
00419
00420 Satisfiability simplifyLocally(ExprType *tca, ExprType *tcb, int flex, Node *node, Hashtable *typingEnv, Hashtable *equivalence, List *simpleTypingConstraints, Region *r) {
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434 if(getNodeType(tcb) == T_FLEX) {
00435 tcb = tcb->subtrees[0];
00436 flex = 1;
00437 } else if(getNodeType(tcb) == T_FIXD) {
00438 tcb = tcb->subtrees[0];
00439 }
00440 tca = dereference(tca, typingEnv, r);
00441 tcb = dereference(tcb, typingEnv, r);
00442
00443 if(getNodeType(tca) == T_UNSPECED || getNodeType(tca) == T_DYNAMIC || getNodeType(tcb) == T_DYNAMIC) {
00444 return TAUTOLOGY;
00445 }
00446 else if(isBaseType(tca) && isBaseType(tcb)) {
00447 return splitBaseType(tca, tcb, flex);
00448 } else if(getNodeType(tca) == T_VAR && getNodeType(tcb) == T_VAR) {
00449 return narrow(tca, tcb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00450
00451 } else if(getNodeType(tca)==T_VAR && isBaseType(tcb)) {
00452 return simplifyL(tca, tcb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00453
00454 } else if(getNodeType(tcb)==T_VAR && isBaseType(tca)) {
00455 return simplifyR(tca, tcb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00456
00457 } else if(getNodeType(tca)==T_VAR && (getNodeType(tcb) == T_CONS || getNodeType(tcb) == T_TUPLE)) {
00458 return splitVarL(tca, tcb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00459
00460 } else if(getNodeType(tcb)==T_VAR && (getNodeType(tca) == T_CONS || getNodeType(tca) == T_TUPLE)) {
00461 return splitVarR(tca, tcb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00462
00463 } else if((getNodeType(tca) == T_CONS && getNodeType(tcb) == T_CONS)
00464 || (getNodeType(tca) == T_TUPLE && getNodeType(tcb) == T_TUPLE)) {
00465 return splitConsOrTuple(tca, tcb, flex, node, typingEnv, equivalence, simpleTypingConstraints, r);
00466 } else {
00467 return ABSURDITY;
00468 }
00469 }
00470
00471
00472
00473
00474 Satisfiability solveConstraints(List *typingConstraints, Hashtable *typingEnv, rError_t *errmsg, Node ** errnode, Region *r) {
00475
00476
00477
00478
00479
00480 ListNode *nextNode = NULL;
00481 do {
00482 Satisfiability sat = simplify(typingConstraints, typingEnv, errmsg, errnode, r);
00483 if(sat == ABSURDITY) {
00484 return ABSURDITY;
00485 }
00486 int changed = 0;
00487 nextNode = typingConstraints->head;
00488 while(nextNode!=NULL && !changed) {
00489 TypingConstraint *tc = (TypingConstraint *)nextNode->value;
00490
00491
00492
00493
00494 ExprType *a = dereference(TC_A(tc), typingEnv, r);
00495 ExprType *b = dereference(TC_B(tc), typingEnv, r);
00496 if(getNodeType(b) == T_FLEX || getNodeType(b) == T_FIXD) {
00497 b = b->subtrees[0];
00498 }
00499
00500
00501
00502
00503 if (getNodeType(a) == T_VAR && getNodeType(b) == T_VAR && T_VAR_ID(a) == T_VAR_ID(b)) {
00504 listRemove(typingConstraints, nextNode);
00505 nextNode = typingConstraints->head;
00506 changed = 1;
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529 } else if (getNodeType(a) != T_VAR && getNodeType(b) != T_VAR) {
00530 printf("error: simplified type does not have variable on either side.\n");
00531 } else {
00532 nextNode = nextNode->next;
00533 }
00534
00535 }
00536 } while(nextNode != NULL);
00537 if(!consistent(typingConstraints, typingEnv, r)) {
00538 return ABSURDITY;
00539 }
00540 return typingConstraints->head == NULL ? TAUTOLOGY : CONTINGENCY;
00541 }
00542
00543 int consistent(List *typingConstraints, Hashtable *typingEnv, Region *r) {
00544 return 1;
00545 }
00546 Satisfiability simplify(List *typingConstraints, Hashtable *typingEnv, rError_t *errmsg, Node **errnode, Region *r) {
00547 ListNode *ln;
00548 int changed;
00549 Hashtable *equivalence = newHashTable2(10, r);
00550 List *simpleTypingConstraints = newList(r);
00551
00552
00553
00554 Satisfiability ret = TAUTOLOGY;
00555 do {
00556 changed = typingEnv->len;
00557 ln = typingConstraints->head;
00558
00559
00560 while(ln!=NULL) {
00561 TypingConstraint *tc = (TypingConstraint *)ln->value;
00562 switch(simplifyLocally(TC_A(tc), TC_B(tc), 0, TC_NODE(tc), typingEnv, equivalence, simpleTypingConstraints, r)) {
00563 case TAUTOLOGY:
00564 break;
00565 case CONTINGENCY:
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576 ret = CONTINGENCY;
00577 break;
00578 case ABSURDITY:
00579 *errnode = TC_NODE(tc);
00580 char errmsgbuf1[ERR_MSG_LEN], errmsgbuf2[ERR_MSG_LEN], buf2[1024], buf3[1024];
00581 snprintf(errmsgbuf1, ERR_MSG_LEN, "simplify: unsolvable typing constraint %s < %s.\n", typeToString(TC_A(tc), typingEnv, buf2, 1024), typeToString(TC_B(tc), typingEnv, buf3, 1024));
00582 generateErrMsg(errmsgbuf1, NODE_EXPR_POS((*errnode)), (*errnode)->base, errmsgbuf2);
00583 addRErrorMsg(errmsg, RE_TYPE_ERROR, errmsgbuf2);
00584
00585
00586 return ABSURDITY;
00587 }
00588 ln = ln->next;
00589 }
00590
00591
00592
00593
00594 typingConstraints->head = simpleTypingConstraints->head;
00595 typingConstraints->tail = simpleTypingConstraints->tail;
00596 simpleTypingConstraints->head = simpleTypingConstraints->tail = NULL;
00597 } while(changed < typingEnv->len);
00598
00599 return ret;
00600 }
00601
00602 ExprType* typeFunction3(Node* node, int dynamictyping, Env* funcDesc, Hashtable* var_type_table, List *typingConstraints, rError_t *errmsg, Node **errnode, Region *r) {
00603
00604 int i;
00605 char *localErrorMsg;
00606 ExprType *res3 = NULL;
00607
00608
00609
00610 Node *fn = node->subtrees[0];
00611 Node *arg = node->subtrees[1];
00612
00613
00614 if(getNodeType(fn) == TK_TEXT && strcmp(fn->text, "foreach") == 0) {
00615 RE_ERROR2(getNodeType(arg) != N_TUPLE || arg->degree != 3,"wrong number of arguments to microservice");
00616 RE_ERROR2(getNodeType(arg->subtrees[0])!=TK_VAR,"argument form error");
00617 char* varname = arg->subtrees[0]->text;
00618 ExprType *varType = (ExprType *)lookupFromHashTable(var_type_table, varname);
00619 ExprType *collType = varType == NULL? NULL:dereference(varType, var_type_table, r);
00620 if(collType!=NULL) {
00621
00622 switch(getNodeType(collType)) {
00623 case T_CONS:
00624
00625 updateInHashTable(var_type_table, varname, dereference(T_CONS_TYPE_ARG(collType, 0), var_type_table, r));
00626 break;
00627 case T_VAR:
00628 if(T_VAR_NUM_DISJUNCTS(collType)!=0) {
00629 Node *disjuncts[2] = {newSimpType(T_STRING, r), newIRODSType(CollInp_MS_T, r)};
00630 Res *unified = unifyTVarL(collType, newTVar2(2, disjuncts, r), var_type_table, r);
00631 RE_ERROR2(getNodeType(unified) == T_ERROR, "foreach is applied to a non collection type");
00632 collType = dereference(collType, var_type_table, r);
00633 updateInHashTable(var_type_table, varname, newIRODSType(DataObjInp_MS_T, r));
00634 break;
00635 } else {
00636
00637
00638 unifyTVarL(collType, newCollType(newTVar(r), r), var_type_table, r);
00639 collType = dereference(collType, var_type_table, r);
00640 updateInHashTable(var_type_table, varname, dereference(T_CONS_TYPE_ARG(collType, 0), var_type_table, r));
00641 break;
00642 }
00643 case T_TUPLE:
00644 RE_ERROR2(T_CONS_ARITY(collType)!=2 ||
00645 getNodeType(T_CONS_TYPE_ARG(collType, 0)) != T_IRODS ||
00646 strcmp(T_CONS_TYPE_NAME(T_CONS_TYPE_ARG(collType, 0)), GenQueryInp_MS_T) !=0 ||
00647 getNodeType(T_CONS_TYPE_ARG(collType, 1)) != T_IRODS ||
00648 strcmp(T_CONS_TYPE_NAME(T_CONS_TYPE_ARG(collType, 0)), GenQueryOut_MS_T) !=0, "foreach is applied to a non collection type");
00649 updateInHashTable(var_type_table, varname, newIRODSType(KeyValPair_MS_T, r));
00650 break;
00651 case T_IRODS:
00652 RE_ERROR2(strcmp(T_CONS_TYPE_NAME(collType), CollInp_MS_T)!=0, "foreach is applied to a non collection type");
00653 updateInHashTable(var_type_table, varname, newIRODSType(DataObjInp_MS_T, r));
00654 break;
00655 case T_STRING:
00656 updateInHashTable(var_type_table, varname, newIRODSType(DataObjInp_MS_T, r));
00657 break;
00658 default:
00659 RE_ERROR2(TRUE, "foreach is applied to a non collection type");
00660 break;
00661 }
00662
00663
00664 } else {
00665 ExprType *elemType;
00666 insertIntoHashTable(var_type_table, varname, elemType = newTVar(r));
00667 collType = newCollType(elemType, r);
00668 }
00669 arg->subtrees[0]->exprType = collType;
00670 res3 = typeExpression3(arg->subtrees[1], dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00671 RE_ERROR2(getNodeType(res3) == T_ERROR, "foreach loop type error");
00672 res3 = typeExpression3(arg->subtrees[2], dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00673 RE_ERROR2(getNodeType(res3) == T_ERROR, "foreach recovery type error");
00674 setIOType(arg->subtrees[0], IO_TYPE_EXPRESSION);
00675 for(i = 1;i<3;i++) {
00676 setIOType(arg->subtrees[i], IO_TYPE_ACTIONS);
00677 }
00678 ExprType **typeArgs = allocSubtrees(r, 3);
00679 typeArgs[0] = collType;
00680 typeArgs[1] = newTVar(r);
00681 typeArgs[2] = newTVar(r);
00682 arg->coercionType = newTupleType(3, typeArgs, r);
00683
00684 updateInHashTable(var_type_table, varname, collType);
00685 return res3;
00686 } else {
00687 ExprType *fnType = typeExpression3(fn, dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00688 if(getNodeType(fnType) == T_ERROR) return fnType;
00689 N_TUPLE_CONSTRUCT_TUPLE(arg) = 1;
00690 ExprType *argType = typeExpression3(arg, dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00691 if(getNodeType(argType) == T_ERROR) return argType;
00692
00693 ExprType *fType = getNodeType(fnType) == T_CONS && strcmp(fnType->text, FUNC) == 0 ? fnType : unifyWith(fnType, newFuncType(newTVar(r), newTVar(r), r), var_type_table, r);
00694
00695 RE_ERROR2(getNodeType(fType) == T_ERROR, "the first component of a function application does not have a function type");
00696 ExprType *paramType = dereference(fType->subtrees[0], var_type_table, r);
00697 ExprType *retType = dereference(fType->subtrees[1], var_type_table, r);
00698
00699 RE_ERROR2(getNodeType(fn) == TK_TEXT && strcmp(fn->text, "assign") == 0 &&
00700 arg->degree>0 &&
00701 !isPattern(arg->subtrees[0]), "the first argument of microservice assign is not a variable or a pattern");
00702 RE_ERROR2(getNodeType(fn) == TK_TEXT && strcmp(fn->text, "let") == 0 &&
00703 arg->degree>0 &&
00704 !isPattern(arg->subtrees[0]), "the first argument of microservice let is not a variable or a pattern");
00705
00706
00707
00708
00709
00710
00711
00712 char buf[ERR_MSG_LEN];
00713
00714 char typebuf[ERR_MSG_LEN];
00715 char typebuf2[ERR_MSG_LEN];ExprType *t = NULL;
00716 if(getVararg(fType) != OPTION_VARARG_ONCE) {
00717
00718 int fixParamN = paramType->degree - 1;
00719 int argN = node->subtrees[1] ->degree;
00720 int copyN = argN - fixParamN;
00721 ExprType **subtrees = paramType->subtrees;
00722 if(copyN < (getVararg(fType) == OPTION_VARARG_PLUS ? 1 : 0) || (getVararg(fType) == OPTION_VARARG_OPTIONAL && copyN > 1)) {
00723 snprintf(buf, 1024, "unsolvable vararg typing constraint %s < %s %s",
00724 typeToString(argType, var_type_table, typebuf, ERR_MSG_LEN),
00725 typeToString(paramType, var_type_table, typebuf2, ERR_MSG_LEN),
00726 getVararg(fType) == OPTION_VARARG_PLUS ? "*" : getVararg(fType) == OPTION_VARARG_OPTIONAL? "?" : "+");
00727 RE_ERROR2(1, buf);
00728 }
00729 ExprType **paramTypes = allocSubtrees(r, argN);
00730 int i;
00731 for(i = 0;i<fixParamN;i++) {
00732 paramTypes[i] = subtrees[i];
00733 }
00734 for(i=0;i<copyN;i++) {
00735 paramTypes[i+fixParamN] = subtrees[fixParamN];
00736 }
00737 t = newTupleType(argN, paramTypes, r);
00738 } else {
00739 t = paramType;
00740 }
00741
00742
00743 int ret = typeFuncParam(node->subtrees[1], argType, t, var_type_table, typingConstraints, errmsg, r);
00744 if(ret!=0) {
00745 *errnode = node->subtrees[1];
00746 RE_ERROR2(ret != 0, "parameter type error");
00747 }
00748 int i;
00749 for(i=0;i<node->subtrees[1]->degree;i++) {
00750 setIOType(node->subtrees[1]->subtrees[i], getIOType(t->subtrees[i]));
00751 }
00752
00753 arg->coercionType = t;
00754
00755
00756
00757
00758
00759 return instantiate(replaceDynamicWithNewTVar(retType, r), var_type_table, 0, r);
00760 }
00761 char errbuf[ERR_MSG_LEN];
00762 char errmsgbuf[ERR_MSG_LEN];
00763 error:
00764 *errnode = node;
00765 snprintf(errmsgbuf, ERR_MSG_LEN, "type error: %s in %s", localErrorMsg, fn->text);
00766 generateErrMsg(errmsgbuf, NODE_EXPR_POS((*errnode)), (*errnode)->base, errbuf);
00767 addRErrorMsg(errmsg, RE_TYPE_ERROR, errbuf);
00768 return newSimpType(T_ERROR,r);
00769 }
00770 ExprType *replaceDynamicWithNewTVar(ExprType *type, Region *r) {
00771 ExprType *newt = (ExprType *)region_alloc(r, sizeof(ExprType));
00772 *newt = *type;
00773 if(getNodeType(type) == T_DYNAMIC) {
00774 setNodeType(newt, T_VAR);
00775 T_VAR_ID(newt) = newTVarId();
00776 }
00777 int i;
00778 for(i=0;i<type->degree;i++) {
00779 newt->subtrees[i] = replaceDynamicWithNewTVar(type->subtrees[i], r);
00780 }
00781 return newt;
00782 }
00783 int typeFuncParam(Node *param, Node *paramType, Node *formalParamType, Hashtable *var_type_table, List *typingConstraints, rError_t *errmsg, Region *r) {
00784
00785
00786
00787
00788
00789
00790
00791
00792
00793 TypingConstraint *tc = newTypingConstraint(paramType, formalParamType, TC_LT, param, r);
00794 listAppend(typingConstraints, tc, r);
00795 Node *errnode;
00796 Satisfiability tcons = simplify(typingConstraints, var_type_table, errmsg, &errnode, r);
00797 switch(tcons) {
00798 case TAUTOLOGY:
00799 break;
00800 case CONTINGENCY:
00801 break;
00802 case ABSURDITY:
00803 return -1;
00804 }
00805 return 0;
00806 }
00807
00808 ExprType* typeExpression3(Node *expr, int dynamictyping, Env *funcDesc, Hashtable *varTypes, List *typingConstraints, rError_t *errmsg, Node **errnode, Region *r) {
00809 ExprType *res;
00810 ExprType **components;
00811 ExprType* t = NULL;
00812 int i;
00813 expr->option |= OPTION_TYPED;
00814 if(dynamictyping) {
00815 switch(getNodeType(expr)) {
00816 case TK_TEXT:
00817 if(strcmp(expr->text,"nop")==0) {
00818 return expr->exprType = newFuncType(newTupleType(0, NULL, r), newSimpType(T_INT, r), r);
00819 } else {
00820
00821 FunctionDesc *fDesc;
00822
00823 if(funcDesc != NULL && (fDesc = (FunctionDesc*)lookupFromEnv(funcDesc, expr->text))!=NULL && fDesc->exprType!=NULL) {
00824 return expr->exprType = dupType(fDesc->exprType, r);
00825 } else {
00826 ExprType *paramType = newSimpType(T_DYNAMIC, r);
00827 setIOType(paramType, IO_TYPE_DYNAMIC);
00828 ExprType *fType = newFuncType(newUnaryType(T_TUPLE, paramType, r), newSimpType(T_DYNAMIC, r), r);
00829 setVararg(fType, OPTION_VARARG_STAR);
00830 return expr->exprType = fType;
00831 }
00832 }
00833 case N_TUPLE:
00834 components = (ExprType **) region_alloc(r, sizeof(ExprType *) * expr->degree);
00835 for(i=0;i<expr->degree;i++) {
00836 components[i] = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00837 if(getNodeType(components[i]) == T_ERROR) {
00838 return expr->exprType = components[i];
00839 }
00840 }
00841 if(N_TUPLE_CONSTRUCT_TUPLE(expr) || expr->degree != 1) {
00842 return expr->exprType = newTupleType(expr->degree, components, r);
00843 } else {
00844 return expr->exprType = components[0];
00845 }
00846
00847 case N_APPLICATION:
00848
00849
00850 return expr->exprType = typeFunction3(expr, dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00851 case N_ACTIONS:
00852 if(expr->degree == 0) {
00853
00854 return expr->exprType = newSimpType(T_INT, r);
00855 }
00856 for(i=0;i<expr->degree;i++) {
00857
00858 res = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00859
00860 if(getNodeType(res) == T_ERROR) {
00861 return expr->exprType = res;
00862 }
00863 }
00864 return expr->exprType = res;
00865 case N_ACTIONS_RECOVERY:
00866 res = typeExpression3(expr->subtrees[0], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00867 if(getNodeType(res) == T_ERROR) {
00868 return expr->exprType = res;
00869 }
00870 res = typeExpression3(expr->subtrees[1], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00871 return expr->exprType = res;
00872 default:
00873 return expr->exprType = newSimpType(T_DYNAMIC, r);
00874
00875 }
00876 } else {
00877 switch(getNodeType(expr)) {
00878 case TK_BOOL:
00879 return expr->exprType = newSimpType(T_BOOL, r);
00880 case TK_INT:
00881 return expr->exprType = newSimpType(T_INT,r);
00882 case TK_DOUBLE:
00883 return expr->exprType = newSimpType(T_DOUBLE,r);
00884 case TK_STRING:
00885 return expr->exprType = newSimpType(T_STRING,r);
00886 case TK_VAR:
00887 t = (ExprType *)lookupFromHashTable(varTypes, expr->text);
00888 if(t==NULL) {
00889
00890 t = newTVar(r);
00891 insertIntoHashTable(varTypes, expr->text, t);
00892 }
00893 t = dereference(t, varTypes, r);
00894 return expr->exprType = t;
00895 case TK_TEXT:
00896 if(strcmp(expr->text,"nop")==0) {
00897 return expr->exprType = newFuncType(newTupleType(0, NULL, r), newSimpType(T_INT, r), r);
00898 } else {
00899
00900 FunctionDesc *fDesc = (FunctionDesc*)lookupFromEnv(funcDesc, expr->text);
00901 if(fDesc!=NULL && fDesc->exprType!=NULL) {
00902 return expr->exprType = dupType(fDesc->exprType, r);
00903 } else {
00904 ExprType *paramType = newSimpType(T_DYNAMIC, r);
00905 setIOType(paramType, IO_TYPE_DYNAMIC);
00906 ExprType *fType = newFuncType(newUnaryType(T_TUPLE, paramType, r), newSimpType(T_DYNAMIC, r), r);
00907 setVararg(fType, OPTION_VARARG_STAR);
00908 return expr->exprType = fType;
00909 }
00910 }
00911 case N_TUPLE:
00912 components = (ExprType **) region_alloc(r, sizeof(ExprType *) * expr->degree);
00913 for(i=0;i<expr->degree;i++) {
00914 components[i] = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00915 if(getNodeType(components[i]) == T_ERROR) {
00916 return expr->exprType = components[i];
00917 }
00918 }
00919 if(N_TUPLE_CONSTRUCT_TUPLE(expr) || expr->degree != 1) {
00920 return expr->exprType = newTupleType(expr->degree, components, r);
00921 } else {
00922 return expr->exprType = components[0];
00923 }
00924
00925 case N_APPLICATION:
00926
00927
00928 return expr->exprType = typeFunction3(expr, dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00929 case N_ACTIONS:
00930 if(expr->degree == 0) {
00931
00932 return expr->exprType = newSimpType(T_INT, r);
00933 }
00934 for(i=0;i<expr->degree;i++) {
00935
00936 res = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00937
00938 if(getNodeType(res) == T_ERROR) {
00939 return expr->exprType = res;
00940 }
00941 }
00942 return expr->exprType = res;
00943 case N_ACTIONS_RECOVERY:
00944 res = typeExpression3(expr->subtrees[0], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00945 if(getNodeType(res) == T_ERROR) {
00946 return expr->exprType = res;
00947 }
00948 res = typeExpression3(expr->subtrees[1], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00949 return expr->exprType = res;
00950 case N_ATTR:
00951
00952 for(i=0;i<expr->degree;i++) {
00953 res = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00954 if(getNodeType(res) == T_ERROR) {
00955 return expr->exprType = res;
00956 }
00957 }
00958 return expr->exprType = newSimpType(T_DYNAMIC, r);
00959 case N_QUERY_COND:
00960
00961 for(i=0;i<expr->degree;i++) {
00962 res = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00963 if(getNodeType(res) == T_ERROR) {
00964 return expr->exprType = res;
00965 }
00966 }
00967 return expr->exprType = newSimpType(T_DYNAMIC, r);
00968 case TK_COL:
00969
00970 return expr->exprType = newSimpType(T_DYNAMIC, r);
00971
00972 default:
00973 break;
00974 }
00975 *errnode = expr;
00976 char errbuf[ERR_MSG_LEN], errbuf0[ERR_MSG_LEN];
00977 snprintf(errbuf0, ERR_MSG_LEN, "error: unsupported ast node %d", getNodeType(expr));
00978 generateErrMsg(errbuf0, NODE_EXPR_POS(expr), expr->base, errbuf);
00979 addRErrorMsg(errmsg, RE_TYPE_ERROR, errbuf);
00980 return expr->exprType = newSimpType(T_ERROR,r);
00981 }
00982 }
00983
00984
00985
00986
00987
00988
00989 void postProcessCoercion(Node *expr, Hashtable *varTypes, rError_t *errmsg, Node **errnode, Region *r) {
00990 expr->coercionType = expr->coercionType==NULL?NULL:instantiate(expr->coercionType, varTypes, 0, r);
00991 expr->exprType = expr->exprType==NULL?NULL:instantiate(expr->exprType, varTypes, 0, r);
00992 int i;
00993 for(i=0;i<expr->degree;i++) {
00994 postProcessCoercion(expr->subtrees[i], varTypes, errmsg, errnode, r);
00995 }
00996 if(expr->coercionType!=NULL && expr->exprType!=NULL) {
00997
00998
00999
01000 if(getNodeType(expr) == N_TUPLE) {
01001 ExprType **csubtrees = expr->coercionType->subtrees;
01002 int i;
01003 for(i=0;i<expr->degree;i++) {
01004 if(typeEqSyntatic(expr->subtrees[i]->exprType, csubtrees[i])) {
01005 expr->subtrees[i]->option &= ~OPTION_COERCE;
01006 } else {
01007 expr->subtrees[i]->option |= OPTION_COERCE;
01008 }
01009 }
01010 }
01011 }
01012 }
01013
01014
01015
01016 void postProcessActions(Node *expr, Env *systemFunctionTables, rError_t *errmsg, Node **errnode, Region *r) {
01017 int i;
01018 switch(getNodeType(expr)) {
01019 case N_TUPLE:
01020 for(i=0;i<expr->degree;i++) {
01021 if(getIOType(expr->subtrees[i]) == IO_TYPE_ACTIONS && getNodeType(expr->subtrees[i]) != N_ACTIONS) {
01022 setIOType(expr->subtrees[i], IO_TYPE_INPUT);
01023 Node **params = (Node **)region_alloc(r, sizeof(Node *)*1);
01024 params[0] = expr->subtrees[i];
01025 Label pos;
01026 pos.base = expr->base;
01027 pos.exprloc = NODE_EXPR_POS(expr);
01028 expr->subtrees[i] = createActionsNode(params, 1, &pos, r);
01029 setIOType(expr->subtrees[i], IO_TYPE_ACTIONS);
01030 expr->subtrees[i]->exprType = params[0]->exprType;
01031 }
01032 }
01033 break;
01034 default:
01035 break;
01036 }
01037 for(i=0;i<expr->degree;i++) {
01038 postProcessActions(expr->subtrees[i], systemFunctionTables, errmsg, errnode, r);
01039 }
01040 }