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 RE_ERROR2(getNodeType(collType) != T_CONS && (getNodeType(collType) != T_VAR || T_VAR_NUM_DISJUNCTS(collType)!=0 ), "foreach is applied to a non collection type");
00623
00624 if(getNodeType(collType) == T_VAR) {
00625 unifyTVarL(collType, newCollType(newTVar(r), r), var_type_table, r);
00626 collType = dereference(collType, var_type_table, r);
00627 }
00628
00629 updateInHashTable(var_type_table, varname, dereference(T_CONS_TYPE_ARG(collType, 0), var_type_table, r));
00630 } else {
00631 ExprType *elemType;
00632 insertIntoHashTable(var_type_table, varname, elemType = newTVar(r));
00633 collType = newCollType(elemType, r);
00634 }
00635 arg->subtrees[0]->exprType = collType;
00636 res3 = typeExpression3(arg->subtrees[1], dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00637 RE_ERROR2(getNodeType(res3) == T_ERROR, "foreach loop type error");
00638 res3 = typeExpression3(arg->subtrees[2], dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00639 RE_ERROR2(getNodeType(res3) == T_ERROR, "foreach recovery type error");
00640 setIOType(arg->subtrees[0], IO_TYPE_EXPRESSION);
00641 for(i = 1;i<3;i++) {
00642 setIOType(arg->subtrees[i], IO_TYPE_ACTIONS);
00643 }
00644 ExprType **typeArgs = allocSubtrees(r, 3);
00645 typeArgs[0] = collType;
00646 typeArgs[1] = newTVar(r);
00647 typeArgs[2] = newTVar(r);
00648 arg->coercionType = newTupleType(3, typeArgs, r);
00649
00650 updateInHashTable(var_type_table, varname, collType);
00651 return res3;
00652 } else {
00653 ExprType *fnType = typeExpression3(fn, dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00654 if(getNodeType(fnType) == T_ERROR) return fnType;
00655 N_TUPLE_CONSTRUCT_TUPLE(arg) = 1;
00656 ExprType *argType = typeExpression3(arg, dynamictyping, funcDesc, var_type_table,typingConstraints,errmsg,errnode,r);
00657 if(getNodeType(argType) == T_ERROR) return argType;
00658
00659 ExprType *fType = getNodeType(fnType) == T_CONS && strcmp(fnType->text, FUNC) == 0 ? fnType : unifyWith(fnType, newFuncType(newTVar(r), newTVar(r), r), var_type_table, r);
00660
00661 RE_ERROR2(getNodeType(fType) == T_ERROR, "the first component of a function application does not have a function type");
00662 ExprType *paramType = dereference(fType->subtrees[0], var_type_table, r);
00663 ExprType *retType = dereference(fType->subtrees[1], var_type_table, r);
00664
00665 RE_ERROR2(getNodeType(fn) == TK_TEXT && strcmp(fn->text, "assign") == 0 &&
00666 arg->degree>0 &&
00667 !isPattern(arg->subtrees[0]), "the first argument of microservice assign is not a variable or a pattern");
00668 RE_ERROR2(getNodeType(fn) == TK_TEXT && strcmp(fn->text, "let") == 0 &&
00669 arg->degree>0 &&
00670 !isPattern(arg->subtrees[0]), "the first argument of microservice let is not a variable or a pattern");
00671
00672
00673
00674
00675
00676
00677
00678 char buf[ERR_MSG_LEN];
00679
00680 char typebuf[ERR_MSG_LEN];
00681 char typebuf2[ERR_MSG_LEN];ExprType *t = NULL;
00682 if(getVararg(fType) != OPTION_VARARG_ONCE) {
00683
00684 int fixParamN = paramType->degree - 1;
00685 int argN = node->subtrees[1] ->degree;
00686 int copyN = argN - fixParamN;
00687 ExprType **subtrees = paramType->subtrees;
00688 if(copyN < (getVararg(fType) == OPTION_VARARG_PLUS ? 1 : 0) || (getVararg(fType) == OPTION_VARARG_OPTIONAL && copyN > 1)) {
00689 snprintf(buf, 1024, "unsolvable vararg typing constraint %s < %s %s",
00690 typeToString(argType, var_type_table, typebuf, ERR_MSG_LEN),
00691 typeToString(paramType, var_type_table, typebuf2, ERR_MSG_LEN),
00692 getVararg(fType) == OPTION_VARARG_PLUS ? "*" : getVararg(fType) == OPTION_VARARG_OPTIONAL? "?" : "+");
00693 RE_ERROR2(1, buf);
00694 }
00695 ExprType **paramTypes = allocSubtrees(r, argN);
00696 int i;
00697 for(i = 0;i<fixParamN;i++) {
00698 paramTypes[i] = subtrees[i];
00699 }
00700 for(i=0;i<copyN;i++) {
00701 paramTypes[i+fixParamN] = subtrees[fixParamN];
00702 }
00703 t = newTupleType(argN, paramTypes, r);
00704 } else {
00705 t = paramType;
00706 }
00707
00708
00709 int ret = typeFuncParam(node->subtrees[1], argType, t, var_type_table, typingConstraints, errmsg, r);
00710 if(ret!=0) {
00711 *errnode = node->subtrees[1];
00712 RE_ERROR2(ret != 0, "parameter type error");
00713 }
00714 int i;
00715 for(i=0;i<node->subtrees[1]->degree;i++) {
00716 setIOType(node->subtrees[1]->subtrees[i], getIOType(t->subtrees[i]));
00717 }
00718
00719 arg->coercionType = t;
00720
00721
00722
00723
00724
00725 return instantiate(replaceDynamicWithNewTVar(retType, r), var_type_table, 0, r);
00726 }
00727 char errbuf[ERR_MSG_LEN];
00728 char errmsgbuf[ERR_MSG_LEN];
00729 error:
00730 *errnode = node;
00731 snprintf(errmsgbuf, ERR_MSG_LEN, "type error: %s in %s", localErrorMsg, fn->text);
00732 generateErrMsg(errmsgbuf, NODE_EXPR_POS((*errnode)), (*errnode)->base, errbuf);
00733 addRErrorMsg(errmsg, RE_TYPE_ERROR, errbuf);
00734 return newSimpType(T_ERROR,r);
00735 }
00736 ExprType *replaceDynamicWithNewTVar(ExprType *type, Region *r) {
00737 ExprType *newt = (ExprType *)region_alloc(r, sizeof(ExprType));
00738 *newt = *type;
00739 if(getNodeType(type) == T_DYNAMIC) {
00740 setNodeType(newt, T_VAR);
00741 T_VAR_ID(newt) = newTVarId();
00742 }
00743 int i;
00744 for(i=0;i<type->degree;i++) {
00745 newt->subtrees[i] = replaceDynamicWithNewTVar(type->subtrees[i], r);
00746 }
00747 return newt;
00748 }
00749 int typeFuncParam(Node *param, Node *paramType, Node *formalParamType, Hashtable *var_type_table, List *typingConstraints, rError_t *errmsg, Region *r) {
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759 TypingConstraint *tc = newTypingConstraint(paramType, formalParamType, TC_LT, param, r);
00760 listAppend(typingConstraints, tc, r);
00761 Node *errnode;
00762 Satisfiability tcons = simplify(typingConstraints, var_type_table, errmsg, &errnode, r);
00763 switch(tcons) {
00764 case TAUTOLOGY:
00765 break;
00766 case CONTINGENCY:
00767 break;
00768 case ABSURDITY:
00769 return -1;
00770 }
00771 return 0;
00772 }
00773
00774 ExprType* typeExpression3(Node *expr, int dynamictyping, Env *funcDesc, Hashtable *varTypes, List *typingConstraints, rError_t *errmsg, Node **errnode, Region *r) {
00775 ExprType *res;
00776 ExprType **components;
00777 ExprType* t = NULL;
00778 int i;
00779 expr->option |= OPTION_TYPED;
00780 if(dynamictyping) {
00781 switch(getNodeType(expr)) {
00782 case TK_TEXT:
00783 if(strcmp(expr->text,"nop")==0) {
00784 return expr->exprType = newFuncType(newTupleType(0, NULL, r), newSimpType(T_INT, r), r);
00785 } else {
00786
00787 FunctionDesc *fDesc;
00788
00789 if(funcDesc != NULL && (fDesc = (FunctionDesc*)lookupFromEnv(funcDesc, expr->text))!=NULL && fDesc->exprType!=NULL) {
00790 return expr->exprType = dupType(fDesc->exprType, r);
00791 } else {
00792 ExprType *paramType = newSimpType(T_DYNAMIC, r);
00793 setIOType(paramType, IO_TYPE_DYNAMIC);
00794 ExprType *fType = newFuncType(newUnaryType(T_TUPLE, paramType, r), newSimpType(T_DYNAMIC, r), r);
00795 setVararg(fType, OPTION_VARARG_STAR);
00796 return expr->exprType = fType;
00797 }
00798 }
00799 case N_TUPLE:
00800 components = (ExprType **) region_alloc(r, sizeof(ExprType *) * expr->degree);
00801 for(i=0;i<expr->degree;i++) {
00802 components[i] = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00803 if(getNodeType(components[i]) == T_ERROR) {
00804 return expr->exprType = components[i];
00805 }
00806 }
00807 if(N_TUPLE_CONSTRUCT_TUPLE(expr) || expr->degree != 1) {
00808 return expr->exprType = newTupleType(expr->degree, components, r);
00809 } else {
00810 return expr->exprType = components[0];
00811 }
00812
00813 case N_APPLICATION:
00814
00815
00816 return expr->exprType = typeFunction3(expr, dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00817 case N_ACTIONS:
00818 if(expr->degree == 0) {
00819
00820 return expr->exprType = newSimpType(T_INT, r);
00821 }
00822 for(i=0;i<expr->degree;i++) {
00823
00824 res = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00825
00826 if(getNodeType(res) == T_ERROR) {
00827 return expr->exprType = res;
00828 }
00829 }
00830 return expr->exprType = res;
00831 case N_ACTIONS_RECOVERY:
00832 res = typeExpression3(expr->subtrees[0], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00833 if(getNodeType(res) == T_ERROR) {
00834 return expr->exprType = res;
00835 }
00836 res = typeExpression3(expr->subtrees[1], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00837 return expr->exprType = res;
00838 default:
00839 return expr->exprType = newSimpType(T_DYNAMIC, r);
00840
00841 }
00842 } else {
00843 switch(getNodeType(expr)) {
00844 case TK_BOOL:
00845 return expr->exprType = newSimpType(T_BOOL, r);
00846 case TK_INT:
00847 return expr->exprType = newSimpType(T_INT,r);
00848 case TK_DOUBLE:
00849 return expr->exprType = newSimpType(T_DOUBLE,r);
00850 case TK_STRING:
00851 return expr->exprType = newSimpType(T_STRING,r);
00852 case TK_VAR:
00853 t = (ExprType *)lookupFromHashTable(varTypes, expr->text);
00854 if(t==NULL) {
00855
00856 t = newTVar(r);
00857 insertIntoHashTable(varTypes, expr->text, t);
00858 }
00859 t = dereference(t, varTypes, r);
00860 return expr->exprType = t;
00861 case TK_TEXT:
00862 if(strcmp(expr->text,"nop")==0) {
00863 return expr->exprType = newFuncType(newTupleType(0, NULL, r), newSimpType(T_INT, r), r);
00864 } else {
00865
00866 FunctionDesc *fDesc = (FunctionDesc*)lookupFromEnv(funcDesc, expr->text);
00867 if(fDesc!=NULL && fDesc->exprType!=NULL) {
00868 return expr->exprType = dupType(fDesc->exprType, r);
00869 } else {
00870 ExprType *paramType = newSimpType(T_DYNAMIC, r);
00871 setIOType(paramType, IO_TYPE_DYNAMIC);
00872 ExprType *fType = newFuncType(newUnaryType(T_TUPLE, paramType, r), newSimpType(T_DYNAMIC, r), r);
00873 setVararg(fType, OPTION_VARARG_STAR);
00874 return expr->exprType = fType;
00875 }
00876 }
00877 case N_TUPLE:
00878 components = (ExprType **) region_alloc(r, sizeof(ExprType *) * expr->degree);
00879 for(i=0;i<expr->degree;i++) {
00880 components[i] = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00881 if(getNodeType(components[i]) == T_ERROR) {
00882 return expr->exprType = components[i];
00883 }
00884 }
00885 if(N_TUPLE_CONSTRUCT_TUPLE(expr) || expr->degree != 1) {
00886 return expr->exprType = newTupleType(expr->degree, components, r);
00887 } else {
00888 return expr->exprType = components[0];
00889 }
00890
00891 case N_APPLICATION:
00892
00893
00894 return expr->exprType = typeFunction3(expr, dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00895 case N_ACTIONS:
00896 if(expr->degree == 0) {
00897
00898 return expr->exprType = newSimpType(T_INT, r);
00899 }
00900 for(i=0;i<expr->degree;i++) {
00901
00902 res = typeExpression3(expr->subtrees[i], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode,r);
00903
00904 if(getNodeType(res) == T_ERROR) {
00905 return expr->exprType = res;
00906 }
00907 }
00908 return expr->exprType = res;
00909 case N_ACTIONS_RECOVERY:
00910 res = typeExpression3(expr->subtrees[0], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00911 if(getNodeType(res) == T_ERROR) {
00912 return expr->exprType = res;
00913 }
00914 res = typeExpression3(expr->subtrees[1], dynamictyping, funcDesc, varTypes, typingConstraints, errmsg, errnode, r);
00915 return expr->exprType = res;
00916 default:
00917 break;
00918 }
00919 *errnode = expr;
00920 char errbuf[ERR_MSG_LEN], errbuf0[ERR_MSG_LEN];
00921 snprintf(errbuf0, ERR_MSG_LEN, "error: unsupported ast node %d", getNodeType(expr));
00922 generateErrMsg(errbuf0, NODE_EXPR_POS(expr), expr->base, errbuf);
00923 addRErrorMsg(errmsg, RE_TYPE_ERROR, errbuf);
00924 return expr->exprType = newSimpType(T_ERROR,r);
00925 }
00926 }
00927
00928
00929
00930
00931
00932
00933 void postProcessCoercion(Node *expr, Hashtable *varTypes, rError_t *errmsg, Node **errnode, Region *r) {
00934 expr->coercionType = expr->coercionType==NULL?NULL:instantiate(expr->coercionType, varTypes, 0, r);
00935 expr->exprType = expr->exprType==NULL?NULL:instantiate(expr->exprType, varTypes, 0, r);
00936 int i;
00937 for(i=0;i<expr->degree;i++) {
00938 postProcessCoercion(expr->subtrees[i], varTypes, errmsg, errnode, r);
00939 }
00940 if(expr->coercionType!=NULL && expr->exprType!=NULL) {
00941
00942
00943
00944 if(getNodeType(expr) == N_TUPLE) {
00945 ExprType **csubtrees = expr->coercionType->subtrees;
00946 int i;
00947 for(i=0;i<expr->degree;i++) {
00948 if(typeEqSyntatic(expr->subtrees[i]->exprType, csubtrees[i])) {
00949 expr->subtrees[i]->option &= ~OPTION_COERCE;
00950 } else {
00951 expr->subtrees[i]->option |= OPTION_COERCE;
00952 }
00953 }
00954 }
00955 }
00956 }
00957
00958
00959
00960 void postProcessActions(Node *expr, Env *systemFunctionTables, rError_t *errmsg, Node **errnode, Region *r) {
00961 int i;
00962 switch(getNodeType(expr)) {
00963 case N_TUPLE:
00964 for(i=0;i<expr->degree;i++) {
00965 if(getIOType(expr->subtrees[i]) == IO_TYPE_ACTIONS && getNodeType(expr->subtrees[i]) != N_ACTIONS) {
00966 setIOType(expr->subtrees[i], IO_TYPE_INPUT);
00967 Node **params = (Node **)region_alloc(r, sizeof(Node *)*1);
00968 params[0] = expr->subtrees[i];
00969 Label pos;
00970 pos.base = expr->base;
00971 pos.exprloc = NODE_EXPR_POS(expr);
00972 expr->subtrees[i] = createActionsNode(params, 1, &pos, r);
00973 setIOType(expr->subtrees[i], IO_TYPE_ACTIONS);
00974 expr->subtrees[i]->exprType = params[0]->exprType;
00975 }
00976 }
00977 break;
00978 default:
00979 break;
00980 }
00981 for(i=0;i<expr->degree;i++) {
00982 postProcessActions(expr->subtrees[i], systemFunctionTables, errmsg, errnode, r);
00983 }
00984 }