iscc.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <isl/obj.h>
   5 #include <isl/stream.h>
   6 #include <isl/vertices.h>
   7 #include <isl/flow.h>
   8 #include <isl_obj_list.h>
   9 #include <isl_obj_str.h>
  10 #include <barvinok/isl.h>
  11 #include <barvinok/options.h>
  12
  13 #include "config.h"
  14
  15 #ifdef HAVE_CLOOG
  16 #include <cloog/isl/cloog.h>
  17 #endif
  18
  19 static int isl_bool_false = 0;
  20 static int isl_bool_true = 1;
  21 static int isl_bool_error = -1;
  22
  23 enum iscc_op { ISCC_READ, ISCC_WRITE, ISCC_SOURCE, ISCC_VERTICES,
  24                ISCC_LAST, ISCC_ANY, ISCC_BEFORE, ISCC_UNDER,
  25                ISCC_TYPEOF,
  26                ISCC_N_OP };
  27 static const char *op_name[ISCC_N_OP] = {
  28         [ISCC_READ] = "read",
  29         [ISCC_WRITE] = "write",
  30         [ISCC_SOURCE] = "source",
  31         [ISCC_VERTICES] = "vertices",
  32         [ISCC_LAST] = "last",
  33         [ISCC_ANY] = "any",
  34         [ISCC_BEFORE] = "before",
  35         [ISCC_UNDER] = "under",
  36         [ISCC_TYPEOF] = "typeof"
  37 };
  38 static enum isl_token_type iscc_op[ISCC_N_OP];
  39
  40 struct isl_arg_choice iscc_format[] = {
  41         {"isl",         ISL_FORMAT_ISL},
  42         {"omega",       ISL_FORMAT_OMEGA},
  43         {"polylib",     ISL_FORMAT_POLYLIB},
  44         {"ext-polylib", ISL_FORMAT_EXT_POLYLIB},
  45         {"latex",       ISL_FORMAT_LATEX},
  46         {"C",           ISL_FORMAT_C},
  47         {0}
  48 };
  49
  50 struct iscc_options {
  51         struct barvinok_options *barvinok;
  52         unsigned                 format;
  53         int                      io;
  54 };
  55
  56 struct isl_arg iscc_options_arg[] = {
  57 ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", barvinok_options_arg,
  58         "barvinok options")
  59 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
  60         iscc_format,    ISL_FORMAT_ISL, "output format")
  61 ISL_ARG_BOOL(struct iscc_options, io, 0, "io", 1,
  62         "allow read and write operations")
  63 ISL_ARG_END
  64 };
  65
  66 ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_arg)
  67 ISL_ARG_CTX_DEF(iscc_options, struct iscc_options, iscc_options_arg)
  68
  69 static void *isl_obj_bool_copy(void *v)
  70 {
  71         return v;
  72 }
  73
  74 static void isl_obj_bool_free(void *v)
  75 {
  76 }
  77
  78 static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
  79         void *v)
  80 {
  81         if (v == &isl_bool_true)
  82                 return isl_printer_print_str(p, "True");
  83         else if (v == &isl_bool_false)
  84                 return isl_printer_print_str(p, "False");
  85         else
  86                 return isl_printer_print_str(p, "Error");
  87 }
  88
  89 static void *isl_obj_bool_add(void *v1, void *v2)
  90 {
  91         return v1;
  92 }
  93
  94 struct isl_obj_vtable isl_obj_bool_vtable = {
  95         isl_obj_bool_copy,
  96         isl_obj_bool_add,
  97         isl_obj_bool_print,
  98         isl_obj_bool_free
  99 };
 100 #define isl_obj_bool            (&isl_obj_bool_vtable)
 101
 102 int *isl_bool_from_int(int res)
 103 {
 104         return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
 105 }
 106
 107 int *union_map_is_equal(__isl_take isl_union_map *map1,
 108         __isl_take isl_union_map *map2)
 109 {
 110         int res = isl_union_map_is_equal(map1, map2);
 111         isl_union_map_free(map1);
 112         isl_union_map_free(map2);
 113         return isl_bool_from_int(res);
 114 }
 115 int *union_set_is_equal(__isl_take isl_union_set *set1,
 116         __isl_take isl_union_set *set2)
 117 {
 118         return union_map_is_equal((isl_union_map *)set1, (isl_union_map *)set2);
 119 }
 120
 121 int *union_map_is_subset(__isl_take isl_union_map *map1,
 122         __isl_take isl_union_map *map2)
 123 {
 124         int res = isl_union_map_is_subset(map1, map2);
 125         isl_union_map_free(map1);
 126         isl_union_map_free(map2);
 127         return isl_bool_from_int(res);
 128 }
 129 int *union_set_is_subset(__isl_take isl_union_set *set1,
 130         __isl_take isl_union_set *set2)
 131 {
 132         return union_map_is_subset((isl_union_map *)set1, (isl_union_map *)set2);
 133 }
 134
 135 int *union_map_is_strict_subset(__isl_take isl_union_map *map1,
 136         __isl_take isl_union_map *map2)
 137 {
 138         int res = isl_union_map_is_strict_subset(map1, map2);
 139         isl_union_map_free(map1);
 140         isl_union_map_free(map2);
 141         return isl_bool_from_int(res);
 142 }
 143 int *union_set_is_strict_subset(__isl_take isl_union_set *set1,
 144         __isl_take isl_union_set *set2)
 145 {
 146         return union_map_is_strict_subset((isl_union_map *)set1,
 147                                           (isl_union_map *)set2);
 148 }
 149
 150 int *union_map_is_superset(__isl_take isl_union_map *map1,
 151         __isl_take isl_union_map *map2)
 152 {
 153         return union_map_is_subset(map2, map1);
 154 }
 155 int *union_set_is_superset(__isl_take isl_union_set *set1,
 156         __isl_take isl_union_set *set2)
 157 {
 158         return union_set_is_subset(set2, set1);
 159 }
 160
 161 int *union_map_is_strict_superset(__isl_take isl_union_map *map1,
 162         __isl_take isl_union_map *map2)
 163 {
 164         return union_map_is_strict_subset(map2, map1);
 165 }
 166 int *union_set_is_strict_superset(__isl_take isl_union_set *set1,
 167         __isl_take isl_union_set *set2)
 168 {
 169         return union_set_is_strict_subset(set2, set1);
 170 }
 171
 172 extern struct isl_obj_vtable isl_obj_list_vtable;
 173 #define isl_obj_list            (&isl_obj_list_vtable)
 174
 175 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
 176 struct isc_bin_op {
 177         enum isl_token_type     op;
 178         isl_obj_type            lhs;
 179         isl_obj_type            rhs;
 180         isl_obj_type            res;
 181         isc_bin_op_fn           fn;
 182 };
 183 struct isc_named_bin_op {
 184         char                    *name;
 185         struct isc_bin_op       op;
 186 };
 187
 188 struct iscc_at {
 189         isl_union_pw_qpolynomial *upwqp;
 190         isl_union_pw_qpolynomial *res;
 191 };
 192
 193 static int eval_at(__isl_take isl_point *pnt, void *user)
 194 {
 195         struct iscc_at *at = (struct iscc_at *) user;
 196         isl_qpolynomial *qp;
 197         isl_set *set;
 198
 199         set = isl_set_from_point(isl_point_copy(pnt));
 200         qp = isl_union_pw_qpolynomial_eval(
 201                                 isl_union_pw_qpolynomial_copy(at->upwqp), pnt);
 202
 203         at->res = isl_union_pw_qpolynomial_add(at->res,
 204                         isl_union_pw_qpolynomial_from_pw_qpolynomial(
 205                                 isl_pw_qpolynomial_alloc(set, qp)));
 206
 207         return 0;
 208 }
 209
 210 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_at(
 211         __isl_take isl_union_pw_qpolynomial *upwqp,
 212         __isl_take isl_union_set *uset)
 213 {
 214         struct iscc_at at;
 215
 216         at.upwqp = upwqp;
 217         at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
 218
 219         isl_union_set_foreach_point(uset, eval_at, &at);
 220
 221         isl_union_pw_qpolynomial_free(upwqp);
 222         isl_union_set_free(uset);
 223
 224         return at.res;
 225 }
 226
 227 struct iscc_fold_at {
 228         isl_union_pw_qpolynomial_fold *upwf;
 229         isl_union_pw_qpolynomial *res;
 230 };
 231
 232 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
 233 {
 234         struct iscc_fold_at *at = (struct iscc_fold_at *) user;
 235         isl_qpolynomial *qp;
 236         isl_set *set;
 237
 238         set = isl_set_from_point(isl_point_copy(pnt));
 239         qp = isl_union_pw_qpolynomial_fold_eval(
 240                             isl_union_pw_qpolynomial_fold_copy(at->upwf), pnt);
 241
 242         at->res = isl_union_pw_qpolynomial_add(at->res,
 243                         isl_union_pw_qpolynomial_from_pw_qpolynomial(
 244                                 isl_pw_qpolynomial_alloc(set, qp)));
 245
 246         return 0;
 247 }
 248
 249 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_fold_at(
 250         __isl_take isl_union_pw_qpolynomial_fold *upwf,
 251         __isl_take isl_union_set *uset)
 252 {
 253         struct iscc_fold_at at;
 254
 255         at.upwf = upwf;
 256         at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
 257
 258         isl_union_set_foreach_point(uset, eval_fold_at, &at);
 259
 260         isl_union_pw_qpolynomial_fold_free(upwf);
 261         isl_union_set_free(uset);
 262
 263         return at.res;
 264 }
 265
 266 static __isl_give isl_union_pw_qpolynomial_fold *union_pw_qpolynomial_add_union_pw_qpolynomial_fold(
 267         __isl_take isl_union_pw_qpolynomial *upwqp,
 268         __isl_take isl_union_pw_qpolynomial_fold *upwf)
 269 {
 270         return isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(upwf,
 271                                                                         upwqp);
 272 }
 273
 274 static __isl_give struct isl_list *union_map_apply_union_pw_qpolynomial_fold(
 275         __isl_take isl_union_map *umap,
 276         __isl_take isl_union_pw_qpolynomial_fold *upwf)
 277 {
 278         isl_ctx *ctx;
 279         struct isl_list *list;
 280         int tight;
 281
 282         ctx = isl_union_map_get_ctx(umap);
 283         list = isl_list_alloc(ctx, 2);
 284         if (!list)
 285                 goto error2;
 286
 287         list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
 288         list->obj[0].v = isl_union_map_apply_union_pw_qpolynomial_fold(umap,
 289                                                         upwf, &tight);
 290         list->obj[1].type = isl_obj_bool;
 291         list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
 292         if (tight < 0 || !list->obj[0].v)
 293                 goto error;
 294
 295         return list;
 296 error2:
 297         isl_union_map_free(umap);
 298         isl_union_pw_qpolynomial_fold_free(upwf);
 299 error:
 300         isl_list_free(list);
 301         return NULL;
 302 }
 303
 304 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_int_mul(
 305         __isl_take isl_union_pw_qpolynomial *upwqp, __isl_take isl_int_obj *i)
 306 {
 307         isl_int v;
 308
 309         if (!i)
 310                 goto error;
 311
 312         isl_int_init(v);
 313         isl_int_obj_get_int(i, &v);
 314         upwqp = isl_union_pw_qpolynomial_mul_isl_int(upwqp, v);
 315         isl_int_clear(v);
 316
 317         isl_int_obj_free(i);
 318
 319         return upwqp;
 320 error:
 321         isl_union_pw_qpolynomial_free(upwqp);
 322         return NULL;
 323 }
 324
 325 static __isl_give isl_union_pw_qpolynomial *int_union_pw_qpolynomial_mul(
 326         __isl_take isl_int_obj *i, __isl_take isl_union_pw_qpolynomial *upwqp)
 327 {
 328         return union_pw_qpolynomial_int_mul(upwqp, i);
 329 }
 330
 331 static __isl_give isl_union_pw_qpolynomial_fold *union_pw_qpolynomial_fold_int_mul(
 332         __isl_take isl_union_pw_qpolynomial_fold *upwf,
 333         __isl_take isl_int_obj *i)
 334 {
 335         isl_int v;
 336
 337         if (!i)
 338                 goto error;
 339
 340         isl_int_init(v);
 341         isl_int_obj_get_int(i, &v);
 342         upwf = isl_union_pw_qpolynomial_fold_mul_isl_int(upwf, v);
 343         isl_int_clear(v);
 344
 345         isl_int_obj_free(i);
 346
 347         return upwf;
 348 error:
 349         isl_union_pw_qpolynomial_fold_free(upwf);
 350         return NULL;
 351 }
 352
 353 static __isl_give isl_union_pw_qpolynomial_fold *int_union_pw_qpolynomial_fold_mul(
 354         __isl_take isl_int_obj *i,
 355         __isl_take isl_union_pw_qpolynomial_fold *upwf)
 356 {
 357         return union_pw_qpolynomial_fold_int_mul(upwf, i);
 358 }
 359
 360 struct isc_bin_op bin_ops[] = {
 361         { '+',  isl_obj_int,    isl_obj_int, isl_obj_int,
 362                 (isc_bin_op_fn) &isl_int_obj_add },
 363         { '-',  isl_obj_int,    isl_obj_int, isl_obj_int,
 364                 (isc_bin_op_fn) &isl_int_obj_sub },
 365         { '*',  isl_obj_int,    isl_obj_int, isl_obj_int,
 366                 (isc_bin_op_fn) &isl_int_obj_mul },
 367         { '+',  isl_obj_union_set,      isl_obj_union_set,
 368                 isl_obj_union_set,
 369                 (isc_bin_op_fn) &isl_union_set_union },
 370         { '+',  isl_obj_union_map,      isl_obj_union_map,
 371                 isl_obj_union_map,
 372                 (isc_bin_op_fn) &isl_union_map_union },
 373         { '-',  isl_obj_union_set,      isl_obj_union_set,
 374                 isl_obj_union_set,
 375                 (isc_bin_op_fn) &isl_union_set_subtract },
 376         { '-',  isl_obj_union_map,      isl_obj_union_map,
 377                 isl_obj_union_map,
 378                 (isc_bin_op_fn) &isl_union_map_subtract },
 379         { '*',  isl_obj_union_set,      isl_obj_union_set,
 380                 isl_obj_union_set,
 381                 (isc_bin_op_fn) &isl_union_set_intersect },
 382         { '*',  isl_obj_union_map,      isl_obj_union_map,
 383                 isl_obj_union_map,
 384                 (isc_bin_op_fn) &isl_union_map_intersect },
 385         { '*',  isl_obj_union_map,      isl_obj_union_set,
 386                 isl_obj_union_map,
 387                 (isc_bin_op_fn) &isl_union_map_intersect_domain },
 388         { '.',  isl_obj_union_map,      isl_obj_union_map,
 389                 isl_obj_union_map,
 390                 (isc_bin_op_fn) &isl_union_map_apply_range },
 391         { '.',  isl_obj_union_map,      isl_obj_union_pw_qpolynomial,
 392                 isl_obj_union_pw_qpolynomial,
 393                 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial },
 394         { '.',  isl_obj_union_map,      isl_obj_union_pw_qpolynomial_fold,
 395                 isl_obj_list,
 396                 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold },
 397         { ISL_TOKEN_TO, isl_obj_union_set,      isl_obj_union_set,
 398                 isl_obj_union_map,
 399                 (isc_bin_op_fn) &isl_union_map_from_domain_and_range },
 400         { '=', isl_obj_union_set,       isl_obj_union_set,      isl_obj_bool,
 401                 (isc_bin_op_fn) &union_set_is_equal },
 402         { '=', isl_obj_union_map,       isl_obj_union_map,      isl_obj_bool,
 403                 (isc_bin_op_fn) &union_map_is_equal },
 404         { ISL_TOKEN_LE, isl_obj_union_set,      isl_obj_union_set,
 405                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_subset },
 406         { ISL_TOKEN_LE, isl_obj_union_map,      isl_obj_union_map,
 407                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_subset },
 408         { ISL_TOKEN_LT, isl_obj_union_set,      isl_obj_union_set,
 409                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_subset },
 410         { ISL_TOKEN_LT, isl_obj_union_map,      isl_obj_union_map,
 411                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_subset },
 412         { ISL_TOKEN_GE, isl_obj_union_set,      isl_obj_union_set,
 413                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_superset },
 414         { ISL_TOKEN_GE, isl_obj_union_map,      isl_obj_union_map,
 415                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_superset },
 416         { ISL_TOKEN_GT, isl_obj_union_set,      isl_obj_union_set,
 417                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_superset },
 418         { ISL_TOKEN_GT, isl_obj_union_map,      isl_obj_union_map,
 419                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_superset },
 420         { ISL_TOKEN_LEX_LE,     isl_obj_union_set,      isl_obj_union_set,
 421                 isl_obj_union_map,
 422                 (isc_bin_op_fn) &isl_union_set_lex_le_union_set },
 423         { ISL_TOKEN_LEX_LT,     isl_obj_union_set,      isl_obj_union_set,
 424                 isl_obj_union_map,
 425                 (isc_bin_op_fn) &isl_union_set_lex_lt_union_set },
 426         { ISL_TOKEN_LEX_GE,     isl_obj_union_set,      isl_obj_union_set,
 427                 isl_obj_union_map,
 428                 (isc_bin_op_fn) &isl_union_set_lex_ge_union_set },
 429         { ISL_TOKEN_LEX_GT,     isl_obj_union_set,      isl_obj_union_set,
 430                 isl_obj_union_map,
 431                 (isc_bin_op_fn) &isl_union_set_lex_gt_union_set },
 432         { ISL_TOKEN_LEX_LE,     isl_obj_union_map,      isl_obj_union_map,
 433                 isl_obj_union_map,
 434                 (isc_bin_op_fn) &isl_union_map_lex_le_union_map },
 435         { ISL_TOKEN_LEX_LT,     isl_obj_union_map,      isl_obj_union_map,
 436                 isl_obj_union_map,
 437                 (isc_bin_op_fn) &isl_union_map_lex_lt_union_map },
 438         { ISL_TOKEN_LEX_GE,     isl_obj_union_map,      isl_obj_union_map,
 439                 isl_obj_union_map,
 440                 (isc_bin_op_fn) &isl_union_map_lex_ge_union_map },
 441         { ISL_TOKEN_LEX_GT,     isl_obj_union_map,      isl_obj_union_map,
 442                 isl_obj_union_map,
 443                 (isc_bin_op_fn) &isl_union_map_lex_gt_union_map },
 444         { '.',  isl_obj_union_pw_qpolynomial_fold,
 445                 isl_obj_union_pw_qpolynomial_fold,
 446                 isl_obj_union_pw_qpolynomial_fold,
 447                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_fold },
 448         { '+',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
 449                 isl_obj_union_pw_qpolynomial,
 450                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_add },
 451         { '+',  isl_obj_union_pw_qpolynomial,
 452                 isl_obj_union_pw_qpolynomial_fold,
 453                 isl_obj_union_pw_qpolynomial_fold,
 454                 (isc_bin_op_fn) &union_pw_qpolynomial_add_union_pw_qpolynomial_fold },
 455         { '+',  isl_obj_union_pw_qpolynomial_fold,
 456                 isl_obj_union_pw_qpolynomial,
 457                 isl_obj_union_pw_qpolynomial_fold,
 458                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial },
 459         { '-',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
 460                 isl_obj_union_pw_qpolynomial,
 461                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_sub },
 462         { '*',  isl_obj_int,    isl_obj_union_pw_qpolynomial,
 463                 isl_obj_union_pw_qpolynomial,
 464                 (isc_bin_op_fn) &int_union_pw_qpolynomial_mul },
 465         { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_int,
 466                 isl_obj_union_pw_qpolynomial,
 467                 (isc_bin_op_fn) &union_pw_qpolynomial_int_mul },
 468         { '*',  isl_obj_int,    isl_obj_union_pw_qpolynomial_fold,
 469                 isl_obj_union_pw_qpolynomial_fold,
 470                 (isc_bin_op_fn) &int_union_pw_qpolynomial_fold_mul },
 471         { '*',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_int,
 472                 isl_obj_union_pw_qpolynomial_fold,
 473                 (isc_bin_op_fn) &union_pw_qpolynomial_fold_int_mul },
 474         { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
 475                 isl_obj_union_pw_qpolynomial,
 476                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_mul },
 477         { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 478                 isl_obj_union_pw_qpolynomial,
 479                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_intersect_domain },
 480         { '*',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_union_set,
 481                 isl_obj_union_pw_qpolynomial_fold,
 482                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_intersect_domain },
 483         { '@',  isl_obj_union_pw_qpolynomial, isl_obj_union_set,
 484                 isl_obj_union_pw_qpolynomial,
 485                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_at },
 486         { '@',  isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
 487                 isl_obj_union_pw_qpolynomial,
 488                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_at },
 489         { '%',  isl_obj_union_set,      isl_obj_union_set,
 490                 isl_obj_union_set,
 491                 (isc_bin_op_fn) &isl_union_set_gist },
 492         { '%',  isl_obj_union_map,      isl_obj_union_map,
 493                 isl_obj_union_map,
 494                 (isc_bin_op_fn) &isl_union_map_gist },
 495         { '%',  isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 496                 isl_obj_union_pw_qpolynomial,
 497                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_gist },
 498         { '%',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_union_set,
 499                 isl_obj_union_pw_qpolynomial_fold,
 500                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_gist },
 501         { '+',  isl_obj_str,    isl_obj_str,    isl_obj_str,
 502                 (isc_bin_op_fn) &isl_str_concat },
 503         0
 504 };
 505
 506 static __isl_give isl_union_map *map_after_map(__isl_take isl_union_map *umap1,
 507         __isl_take isl_union_map *umap2)
 508 {
 509         return isl_union_map_apply_range(umap2, umap1);
 510 }
 511
 512 static __isl_give isl_union_pw_qpolynomial *qpolynomial_after_map(
 513         __isl_take isl_union_pw_qpolynomial *upwqp,
 514         __isl_take isl_union_map *umap)
 515 {
 516         return isl_union_map_apply_union_pw_qpolynomial(umap, upwqp);
 517 }
 518
 519 static __isl_give struct isl_list *qpolynomial_fold_after_map(
 520         __isl_take isl_union_pw_qpolynomial_fold *upwf,
 521         __isl_take isl_union_map *umap)
 522 {
 523         return union_map_apply_union_pw_qpolynomial_fold(umap, upwf);
 524 }
 525
 526 struct isc_named_bin_op named_bin_ops[] = {
 527         { "after",      { -1, isl_obj_union_map,        isl_obj_union_map,
 528                 isl_obj_union_map,
 529                 (isc_bin_op_fn) &map_after_map } },
 530         { "after",      { -1, isl_obj_union_pw_qpolynomial,
 531                 isl_obj_union_map, isl_obj_union_pw_qpolynomial,
 532                 (isc_bin_op_fn) &qpolynomial_after_map } },
 533         { "after",      { -1, isl_obj_union_pw_qpolynomial_fold,
 534                 isl_obj_union_map, isl_obj_list,
 535                 (isc_bin_op_fn) &qpolynomial_fold_after_map } },
 536         { "before",     { -1, isl_obj_union_map,        isl_obj_union_map,
 537                 isl_obj_union_map,
 538                 (isc_bin_op_fn) &isl_union_map_apply_range } },
 539         { "before",     { -1, isl_obj_union_map,
 540                 isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
 541                 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial } },
 542         { "before",     { -1, isl_obj_union_map,
 543                 isl_obj_union_pw_qpolynomial_fold, isl_obj_list,
 544                 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold } },
 545         { "cross",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 546                 isl_obj_union_set,
 547                 (isc_bin_op_fn) &isl_union_set_product } },
 548         { "cross",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 549                 isl_obj_union_map,
 550                 (isc_bin_op_fn) &isl_union_map_product } },
 551         NULL
 552 };
 553
 554 __isl_give isl_set *union_set_sample(__isl_take isl_union_set *uset)
 555 {
 556         return isl_set_from_basic_set(isl_union_set_sample(uset));
 557 }
 558
 559 __isl_give isl_map *union_map_sample(__isl_take isl_union_map *umap)
 560 {
 561         return isl_map_from_basic_map(isl_union_map_sample(umap));
 562 }
 563
 564 static __isl_give struct isl_list *union_map_power(
 565         __isl_take isl_union_map *umap)
 566 {
 567         isl_ctx *ctx;
 568         struct isl_list *list;
 569         int exact;
 570
 571         ctx = isl_union_map_get_ctx(umap);
 572         list = isl_list_alloc(ctx, 2);
 573         if (!list)
 574                 goto error2;
 575
 576         list->obj[0].type = isl_obj_union_map;
 577         list->obj[0].v = isl_union_map_power(umap, &exact);
 578         list->obj[1].type = isl_obj_bool;
 579         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 580         if (exact < 0 || !list->obj[0].v)
 581                 goto error;
 582
 583         return list;
 584 error2:
 585         isl_union_map_free(umap);
 586 error:
 587         isl_list_free(list);
 588         return NULL;
 589 }
 590
 591 static __isl_give struct isl_list *union_pw_qpolynomial_upper_bound(
 592         __isl_take isl_union_pw_qpolynomial *upwqp)
 593 {
 594         isl_ctx *ctx;
 595         struct isl_list *list;
 596         int tight;
 597
 598         ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
 599         list = isl_list_alloc(ctx, 2);
 600         if (!list)
 601                 goto error2;
 602
 603         list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
 604         list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
 605                                                         isl_fold_max, &tight);
 606         list->obj[1].type = isl_obj_bool;
 607         list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
 608         if (tight < 0 || !list->obj[0].v)
 609                 goto error;
 610
 611         return list;
 612 error2:
 613         isl_union_pw_qpolynomial_free(upwqp);
 614 error:
 615         isl_list_free(list);
 616         return NULL;
 617 }
 618
 619 #ifdef HAVE_CLOOG
 620 void *map_codegen(void *arg)
 621 {
 622         isl_dim *dim;
 623         isl_union_map *umap = (isl_union_map *)arg;
 624         isl_ctx *ctx = isl_union_map_get_ctx(umap);
 625         CloogState *state;
 626         CloogOptions *options;
 627         CloogDomain *context;
 628         CloogUnionDomain *ud;
 629         CloogInput *input;
 630         struct clast_stmt *stmt;
 631
 632         state = cloog_isl_state_malloc(ctx);
 633         options = cloog_options_malloc(state);
 634         options->language = LANGUAGE_C;
 635         options->strides = 1;
 636
 637         ud = cloog_union_domain_from_isl_union_map(isl_union_map_copy(umap));
 638
 639         dim = isl_union_map_get_dim(umap);
 640         context = cloog_domain_from_isl_set(isl_set_universe(dim));
 641
 642         input = cloog_input_alloc(context, ud);
 643
 644         stmt = cloog_clast_create_from_input(input, options);
 645         clast_pprint(stdout, stmt, 0, options);
 646         cloog_clast_free(stmt);
 647
 648 error:
 649         cloog_options_free(options);
 650         cloog_state_free(state);
 651         isl_union_map_free(umap);
 652         return NULL;
 653 }
 654
 655 void *set_codegen(void *arg)
 656 {
 657         isl_dim *dim;
 658         isl_union_set *uset = (isl_union_set *)arg;
 659         isl_ctx *ctx = isl_union_set_get_ctx(uset);
 660         CloogState *state;
 661         CloogOptions *options;
 662         CloogDomain *context;
 663         CloogUnionDomain *ud;
 664         CloogInput *input;
 665         struct clast_stmt *stmt;
 666
 667         if (isl_union_set_n_set(uset) > 1)
 668                 isl_die(ctx, isl_error_invalid,
 669                         "code generation for more than one domain "
 670                         "requires a schedule", goto error);
 671
 672         state = cloog_isl_state_malloc(ctx);
 673         options = cloog_options_malloc(state);
 674         options->language = LANGUAGE_C;
 675         options->strides = 1;
 676
 677         ud = cloog_union_domain_from_isl_union_set(isl_union_set_copy(uset));
 678
 679         dim = isl_union_set_get_dim(uset);
 680         context = cloog_domain_from_isl_set(isl_set_universe(dim));
 681
 682         input = cloog_input_alloc(context, ud);
 683
 684         stmt = cloog_clast_create_from_input(input, options);
 685         clast_pprint(stdout, stmt, 0, options);
 686         cloog_clast_free(stmt);
 687
 688         cloog_options_free(options);
 689         cloog_state_free(state);
 690 error:
 691         isl_union_set_free(uset);
 692         return NULL;
 693 }
 694 #endif
 695
 696 static int add_point(__isl_take isl_point *pnt, void *user)
 697 {
 698         isl_union_set **scan = (isl_union_set **) user;
 699
 700         *scan = isl_union_set_add_set(*scan, isl_set_from_point(pnt));
 701
 702         return 0;
 703 }
 704
 705 static __isl_give isl_union_set *union_set_scan(__isl_take isl_union_set *uset)
 706 {
 707         isl_union_set *scan;
 708
 709         scan = isl_union_set_empty(isl_union_set_get_dim(uset));
 710
 711         if (isl_union_set_foreach_point(uset, add_point, &scan) < 0) {
 712                 isl_union_set_free(scan);
 713                 return uset;
 714         }
 715
 716         isl_union_set_free(uset);
 717         return scan;
 718 }
 719
 720 static __isl_give isl_union_map *union_map_scan(__isl_take isl_union_map *umap)
 721 {
 722         return isl_union_set_unwrap(union_set_scan(isl_union_map_wrap(umap)));
 723 }
 724
 725 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_poly(
 726         __isl_take isl_union_pw_qpolynomial *upwqp)
 727 {
 728         return isl_union_pw_qpolynomial_to_polynomial(upwqp, 0);
 729 }
 730
 731 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_lpoly(
 732         __isl_take isl_union_pw_qpolynomial *upwqp)
 733 {
 734         return isl_union_pw_qpolynomial_to_polynomial(upwqp, -1);
 735 }
 736
 737 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_upoly(
 738         __isl_take isl_union_pw_qpolynomial *upwqp)
 739 {
 740         return isl_union_pw_qpolynomial_to_polynomial(upwqp, 1);
 741 }
 742
 743 typedef void *(*isc_un_op_fn)(void *arg);
 744 struct isc_un_op {
 745         enum isl_token_type     op;
 746         isl_obj_type            arg;
 747         isl_obj_type            res;
 748         isc_un_op_fn            fn;
 749 };
 750 struct isc_named_un_op {
 751         char                    *name;
 752         struct isc_un_op        op;
 753 };
 754 struct isc_named_un_op named_un_ops[] = {
 755         {"aff", { -1,   isl_obj_union_map,      isl_obj_union_map,
 756                 (isc_un_op_fn) &isl_union_map_affine_hull } },
 757         {"aff", { -1,   isl_obj_union_set,      isl_obj_union_set,
 758                 (isc_un_op_fn) &isl_union_set_affine_hull } },
 759         {"card",        { -1,   isl_obj_union_set,
 760                 isl_obj_union_pw_qpolynomial,
 761                 (isc_un_op_fn) &isl_union_set_card } },
 762         {"card",        { -1,   isl_obj_union_map,
 763                 isl_obj_union_pw_qpolynomial,
 764                 (isc_un_op_fn) &isl_union_map_card } },
 765         {"coalesce",    { -1,   isl_obj_union_set,      isl_obj_union_set,
 766                 (isc_un_op_fn) &isl_union_set_coalesce } },
 767         {"coalesce",    { -1,   isl_obj_union_map,      isl_obj_union_map,
 768                 (isc_un_op_fn) &isl_union_map_coalesce } },
 769         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial,
 770                 isl_obj_union_pw_qpolynomial,
 771                 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
 772         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial_fold,
 773                 isl_obj_union_pw_qpolynomial_fold,
 774                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
 775 #ifdef HAVE_CLOOG
 776         {"codegen",     { -1,   isl_obj_union_set, isl_obj_none,
 777                 &set_codegen } },
 778         {"codegen",     { -1,   isl_obj_union_map, isl_obj_none,
 779                 &map_codegen } },
 780 #endif
 781         {"deltas",      { -1,   isl_obj_union_map,      isl_obj_union_set,
 782                 (isc_un_op_fn) &isl_union_map_deltas } },
 783         {"deltas_map",  { -1,   isl_obj_union_map,      isl_obj_union_map,
 784                 (isc_un_op_fn) &isl_union_map_deltas_map } },
 785         {"dom", { -1,   isl_obj_union_map,      isl_obj_union_set,
 786                 (isc_un_op_fn) &isl_union_map_domain } },
 787         {"dom", { -1,   isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 788                 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
 789         {"dom", { -1,   isl_obj_union_pw_qpolynomial_fold,
 790                 isl_obj_union_set,
 791                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
 792         {"domain",      { -1,   isl_obj_union_map,      isl_obj_union_set,
 793                 (isc_un_op_fn) &isl_union_map_domain } },
 794         {"domain",      { -1,   isl_obj_union_pw_qpolynomial,
 795                 isl_obj_union_set,
 796                 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
 797         {"domain",      { -1,   isl_obj_union_pw_qpolynomial_fold,
 798                 isl_obj_union_set,
 799                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
 800         {"domain_map",  { -1,   isl_obj_union_map,      isl_obj_union_map,
 801                 (isc_un_op_fn) &isl_union_map_domain_map } },
 802         {"ran", { -1,   isl_obj_union_map,      isl_obj_union_set,
 803                 (isc_un_op_fn) &isl_union_map_range } },
 804         {"range",       { -1,   isl_obj_union_map,      isl_obj_union_set,
 805                 (isc_un_op_fn) &isl_union_map_range } },
 806         {"range_map",   { -1,   isl_obj_union_map,      isl_obj_union_map,
 807                 (isc_un_op_fn) &isl_union_map_range_map } },
 808         {"identity",    { -1,   isl_obj_union_set,      isl_obj_union_map,
 809                 (isc_un_op_fn) &isl_union_set_identity } },
 810         {"lexmin",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 811                 (isc_un_op_fn) &isl_union_map_lexmin } },
 812         {"lexmax",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 813                 (isc_un_op_fn) &isl_union_map_lexmax } },
 814         {"lexmin",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 815                 (isc_un_op_fn) &isl_union_set_lexmin } },
 816         {"lexmax",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 817                 (isc_un_op_fn) &isl_union_set_lexmax } },
 818         {"poly",        { -1,   isl_obj_union_map,      isl_obj_union_map,
 819                 (isc_un_op_fn) &isl_union_map_polyhedral_hull } },
 820         {"poly",        { -1,   isl_obj_union_set,      isl_obj_union_set,
 821                 (isc_un_op_fn) &isl_union_set_polyhedral_hull } },
 822         {"poly",        { -1,   isl_obj_union_pw_qpolynomial,
 823                 isl_obj_union_pw_qpolynomial,
 824                 (isc_un_op_fn) &union_pw_qpolynomial_poly } },
 825         {"lpoly",       { -1,   isl_obj_union_pw_qpolynomial,
 826                 isl_obj_union_pw_qpolynomial,
 827                 (isc_un_op_fn) &union_pw_qpolynomial_lpoly } },
 828         {"upoly",       { -1,   isl_obj_union_pw_qpolynomial,
 829                 isl_obj_union_pw_qpolynomial,
 830                 (isc_un_op_fn) &union_pw_qpolynomial_upoly } },
 831         {"pow", { -1,   isl_obj_union_map,      isl_obj_list,
 832                 (isc_un_op_fn) &union_map_power } },
 833         {"sample",      { -1,   isl_obj_union_set,      isl_obj_set,
 834                 (isc_un_op_fn) &union_set_sample } },
 835         {"sample",      { -1,   isl_obj_union_map,      isl_obj_map,
 836                 (isc_un_op_fn) &union_map_sample } },
 837         {"scan",        { -1,   isl_obj_union_set,      isl_obj_union_set,
 838                 (isc_un_op_fn) &union_set_scan } },
 839         {"scan",        { -1,   isl_obj_union_map,      isl_obj_union_map,
 840                 (isc_un_op_fn) &union_map_scan } },
 841         {"sum",         { -1,   isl_obj_union_pw_qpolynomial,
 842                 isl_obj_union_pw_qpolynomial,
 843                 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
 844         {"ub",          { -1,   isl_obj_union_pw_qpolynomial, isl_obj_list,
 845                 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
 846         {"unwrap",      { -1,   isl_obj_union_set,      isl_obj_union_map,
 847                 (isc_un_op_fn) &isl_union_set_unwrap } },
 848         {"wrap",        { -1,   isl_obj_union_map,      isl_obj_union_set,
 849                 (isc_un_op_fn) &isl_union_map_wrap } },
 850         {"zip", { -1,   isl_obj_union_map,      isl_obj_union_map,
 851                 (isc_un_op_fn) &isl_union_map_zip } },
 852         NULL
 853 };
 854
 855 struct isl_named_obj {
 856         char            *name;
 857         struct isl_obj  obj;
 858 };
 859
 860 static void free_obj(struct isl_obj obj)
 861 {
 862         obj.type->free(obj.v);
 863 }
 864
 865 static int same_name(const void *entry, const void *val)
 866 {
 867         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 868
 869         return !strcmp(named->name, val);
 870 }
 871
 872 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 873         char *name, struct isl_obj obj)
 874 {
 875         struct isl_hash_table_entry *entry;
 876         uint32_t name_hash;
 877         struct isl_named_obj *named;
 878
 879         name_hash = isl_hash_string(isl_hash_init(), name);
 880         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 881         if (!entry)
 882                 goto error;
 883         if (entry->data) {
 884                 named = entry->data;
 885                 free_obj(named->obj);
 886                 free(name);
 887         } else {
 888                 named = isl_alloc_type(ctx, struct isl_named_obj);
 889                 if (!named)
 890                         goto error;
 891                 named->name = name;
 892                 entry->data = named;
 893         }
 894         named->obj = obj;
 895
 896         return 0;
 897 error:
 898         free_obj(obj);
 899         free(name);
 900         return -1;
 901 }
 902
 903 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 904         struct isl_hash_table *table, char *name)
 905 {
 906         struct isl_obj obj = { isl_obj_none, NULL };
 907         struct isl_hash_table_entry *entry;
 908         uint32_t name_hash;
 909
 910         name_hash = isl_hash_string(isl_hash_init(), name);
 911         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 912         if (entry) {
 913                 struct isl_named_obj *named;
 914                 named = entry->data;
 915                 obj = named->obj;
 916         } else
 917                 fprintf(stderr, "unknown identifier '%s'\n", name);
 918
 919         free(name);
 920         obj.v = obj.type->copy(obj.v);
 921         return obj;
 922 }
 923
 924 static int is_subtype(struct isl_obj obj, isl_obj_type super)
 925 {
 926         if (obj.type == super)
 927                 return 1;
 928         if (obj.type == isl_obj_map && super == isl_obj_union_map)
 929                 return 1;
 930         if (obj.type == isl_obj_set && super == isl_obj_union_set)
 931                 return 1;
 932         if (obj.type == isl_obj_pw_qpolynomial &&
 933             super == isl_obj_union_pw_qpolynomial)
 934                 return 1;
 935         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 936             super == isl_obj_union_pw_qpolynomial_fold)
 937                 return 1;
 938         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
 939                 return 1;
 940         if (obj.type == isl_obj_list) {
 941                 struct isl_list *list = obj.v;
 942                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
 943                         return is_subtype(list->obj[0], super);
 944         }
 945         if (super == isl_obj_str)
 946                 return 1;
 947         return 0;
 948 }
 949
 950 static struct isl_obj obj_at(struct isl_obj obj, int i)
 951 {
 952         struct isl_list *list = obj.v;
 953
 954         obj = list->obj[i];
 955         obj.v = obj.type->copy(obj.v);
 956
 957         isl_list_free(list);
 958
 959         return obj;
 960 }
 961
 962 static struct isl_obj convert(isl_ctx *ctx, struct isl_obj obj,
 963         isl_obj_type type)
 964 {
 965         if (obj.type == type)
 966                 return obj;
 967         if (obj.type == isl_obj_map && type == isl_obj_union_map) {
 968                 obj.type = isl_obj_union_map;
 969                 obj.v = isl_union_map_from_map(obj.v);
 970                 return obj;
 971         }
 972         if (obj.type == isl_obj_set && type == isl_obj_union_set) {
 973                 obj.type = isl_obj_union_set;
 974                 obj.v = isl_union_set_from_set(obj.v);
 975                 return obj;
 976         }
 977         if (obj.type == isl_obj_pw_qpolynomial &&
 978             type == isl_obj_union_pw_qpolynomial) {
 979                 obj.type = isl_obj_union_pw_qpolynomial;
 980                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
 981                 return obj;
 982         }
 983         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 984             type == isl_obj_union_pw_qpolynomial_fold) {
 985                 obj.type = isl_obj_union_pw_qpolynomial_fold;
 986                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
 987                 return obj;
 988         }
 989         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
 990                 if (type == isl_obj_union_map) {
 991                         obj.type = isl_obj_union_map;
 992                         return obj;
 993                 }
 994                 if (type == isl_obj_union_pw_qpolynomial) {
 995                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 996                         isl_union_set_free(obj.v);
 997                         obj.v = isl_union_pw_qpolynomial_zero(dim);
 998                         obj.type = isl_obj_union_pw_qpolynomial;
 999                         return obj;
1000                 }
1001                 if (type == isl_obj_union_pw_qpolynomial_fold) {
1002                         isl_dim *dim = isl_union_set_get_dim(obj.v);
1003                         isl_union_set_free(obj.v);
1004                         obj.v = isl_union_pw_qpolynomial_fold_zero(dim,
1005                                                                 isl_fold_list);
1006                         obj.type = isl_obj_union_pw_qpolynomial_fold;
1007                         return obj;
1008                 }
1009         }
1010         if (obj.type == isl_obj_list) {
1011                 struct isl_list *list = obj.v;
1012                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1013                         return convert(ctx, obj_at(obj, 0), type);
1014         }
1015         if (type == isl_obj_str) {
1016                 isl_str *str;
1017                 isl_printer *p;
1018                 char *s;
1019
1020                 p = isl_printer_to_str(ctx);
1021                 if (!p)
1022                         goto error;
1023                 p = obj.type->print(p, obj.v);
1024                 s = isl_printer_get_str(p);
1025                 isl_printer_free(p);
1026
1027                 str = isl_str_from_string(ctx, s);
1028                 if (!str)
1029                         goto error;
1030                 free_obj(obj);
1031                 obj.v = str;
1032                 obj.type = isl_obj_str;
1033                 return obj;
1034
1035         }
1036 error:
1037         free_obj(obj);
1038         obj.type = isl_obj_none;
1039         obj.v = NULL;
1040         return obj;
1041 }
1042
1043 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
1044         struct isl_obj lhs)
1045 {
1046         int i;
1047         struct isl_token *tok;
1048
1049         tok = isl_stream_next_token(s);
1050         if (!tok)
1051                 return NULL;
1052
1053         for (i = 0; ; ++i) {
1054                 if (!bin_ops[i].op)
1055                         break;
1056                 if (bin_ops[i].op != tok->type)
1057                         continue;
1058                 if (!is_subtype(lhs, bin_ops[i].lhs))
1059                         continue;
1060
1061                 isl_token_free(tok);
1062                 return &bin_ops[i];
1063         }
1064
1065         for (i = 0; ; ++i) {
1066                 if (!named_bin_ops[i].name)
1067                         break;
1068                 if (named_bin_ops[i].op.op != tok->type)
1069                         continue;
1070                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1071                         continue;
1072
1073                 isl_token_free(tok);
1074                 return &named_bin_ops[i].op;
1075         }
1076
1077         isl_stream_push_token(s, tok);
1078
1079         return NULL;
1080 }
1081
1082 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
1083 {
1084         int i;
1085         struct isl_token *tok;
1086
1087         tok = isl_stream_next_token(s);
1088         if (!tok)
1089                 return NULL;
1090
1091         for (i = 0; ; ++i) {
1092                 if (!named_un_ops[i].name)
1093                         break;
1094                 if (named_un_ops[i].op.op != tok->type)
1095                         continue;
1096
1097                 isl_token_free(tok);
1098                 return &named_un_ops[i].op;
1099         }
1100
1101         isl_stream_push_token(s, tok);
1102
1103         return NULL;
1104 }
1105
1106 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
1107         struct isl_obj arg)
1108 {
1109         int i;
1110
1111         for (i = 0; ; ++i) {
1112                 if (!named_un_ops[i].name)
1113                         break;
1114                 if (named_un_ops[i].op.op != like->op)
1115                         continue;
1116                 if (!is_subtype(arg, named_un_ops[i].op.arg))
1117                         continue;
1118
1119                 return &named_un_ops[i].op;
1120         }
1121
1122         return NULL;
1123 }
1124
1125 static int is_assign(struct isl_stream *s)
1126 {
1127         struct isl_token *tok;
1128         struct isl_token *tok2;
1129         int assign;
1130
1131         tok = isl_stream_next_token(s);
1132         if (!tok)
1133                 return 0;
1134         if (tok->type != ISL_TOKEN_IDENT) {
1135                 isl_stream_push_token(s, tok);
1136                 return 0;
1137         }
1138
1139         tok2 = isl_stream_next_token(s);
1140         if (!tok2) {
1141                 isl_stream_push_token(s, tok);
1142                 return 0;
1143         }
1144         assign = tok2->type == ISL_TOKEN_DEF;
1145         isl_stream_push_token(s, tok2);
1146         isl_stream_push_token(s, tok);
1147
1148         return assign;
1149 }
1150
1151 static struct isl_obj read_obj(struct isl_stream *s,
1152         struct isl_hash_table *table);
1153 static struct isl_obj read_expr(struct isl_stream *s,
1154         struct isl_hash_table *table);
1155
1156 static struct isl_obj read_un_op_expr(struct isl_stream *s,
1157         struct isl_hash_table *table, struct isc_un_op *op)
1158 {
1159         struct isl_obj obj = { isl_obj_none, NULL };
1160
1161         obj = read_obj(s, table);
1162         if (!obj.v)
1163                 goto error;
1164
1165         op = find_matching_un_op(op, obj);
1166
1167         if (!op)
1168                 isl_die(s->ctx, isl_error_invalid,
1169                         "no such unary operator defined on given operand",
1170                         goto error);
1171
1172         obj = convert(s->ctx, obj, op->arg);
1173         obj.v = op->fn(obj.v);
1174         obj.type = op->res;
1175
1176         return obj;
1177 error:
1178         free_obj(obj);
1179         obj.type = isl_obj_none;
1180         obj.v = NULL;
1181         return obj;
1182 }
1183
1184 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
1185 {
1186         struct isl_list *list;
1187         int exact;
1188
1189         if (obj.type != isl_obj_union_map)
1190                 obj = convert(ctx, obj, isl_obj_union_map);
1191         isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
1192         list = isl_list_alloc(ctx, 2);
1193         if (!list)
1194                 goto error;
1195
1196         list->obj[0].type = isl_obj_union_map;
1197         list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
1198         list->obj[1].type = isl_obj_bool;
1199         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
1200         obj.v = list;
1201         obj.type = isl_obj_list;
1202         if (exact < 0 || !list->obj[0].v)
1203                 goto error;
1204
1205         return obj;
1206 error:
1207         free_obj(obj);
1208         obj.type = isl_obj_none;
1209         obj.v = NULL;
1210         return obj;
1211 }
1212
1213 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
1214 {
1215         struct isl_list *list = obj.v;
1216         struct isl_token *tok;
1217         int i;
1218
1219         tok = isl_stream_next_token(s);
1220         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1221                 isl_stream_error(s, tok, "expecting index");
1222                 if (tok)
1223                         isl_stream_push_token(s, tok);
1224                 goto error;
1225         }
1226         i = isl_int_get_si(tok->u.v);
1227         isl_token_free(tok);
1228         isl_assert(s->ctx, i < list->n, goto error);
1229         if (isl_stream_eat(s, ']'))
1230                 goto error;
1231
1232         return obj_at(obj, i);
1233 error:
1234         free_obj(obj);
1235         obj.type = isl_obj_none;
1236         obj.v = NULL;
1237         return obj;
1238 }
1239
1240 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
1241         struct isl_hash_table *table)
1242 {
1243         struct isl_obj obj;
1244
1245         obj = read_expr(s, table);
1246         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
1247                            is_subtype(obj, isl_obj_union_map), goto error);
1248
1249         if (obj.type == isl_obj_list) {
1250                 struct isl_list *list = obj.v;
1251                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1252                         obj = obj_at(obj, 0);
1253         }
1254         if (obj.type == isl_obj_set)
1255                 obj = convert(s->ctx, obj, isl_obj_union_set);
1256         else if (obj.type == isl_obj_map)
1257                 obj = convert(s->ctx, obj, isl_obj_union_map);
1258         if (obj.type == isl_obj_union_set) {
1259                 obj.v = isl_union_set_apply(obj.v, umap);
1260         } else
1261                 obj.v = isl_union_map_apply_range(obj.v, umap);
1262         if (!obj.v)
1263                 goto error2;
1264
1265         if (isl_stream_eat(s, ')'))
1266                 goto error2;
1267
1268         return obj;
1269 error:
1270         isl_union_map_free(umap);
1271 error2:
1272         free_obj(obj);
1273         obj.type = isl_obj_none;
1274         obj.v = NULL;
1275         return obj;
1276 }
1277
1278 static struct isl_obj apply_fun(struct isl_stream *s,
1279         struct isl_obj obj, struct isl_hash_table *table)
1280 {
1281         struct isl_obj arg;
1282
1283         arg = read_expr(s, table);
1284         if (!is_subtype(arg, isl_obj_union_map) &&
1285             !is_subtype(arg, isl_obj_union_set))
1286                 isl_die(s->ctx, isl_error_invalid,
1287                         "expecting set of map argument", goto error);
1288
1289         if (arg.type == isl_obj_list) {
1290                 struct isl_list *list = arg.v;
1291                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1292                         arg = obj_at(arg, 0);
1293         }
1294         if (arg.type == isl_obj_set)
1295                 arg = convert(s->ctx, arg, isl_obj_union_set);
1296         else if (arg.type == isl_obj_map)
1297                 arg = convert(s->ctx, arg, isl_obj_union_map);
1298         if (arg.type == isl_obj_union_set) {
1299                 arg.v = isl_union_map_from_range(arg.v);
1300                 arg.type = isl_obj_union_map;
1301         }
1302         if (obj.type == isl_obj_union_pw_qpolynomial) {
1303                 obj.v = isl_union_map_apply_union_pw_qpolynomial(arg.v, obj.v);
1304         } else {
1305                 obj.type = isl_obj_list;
1306                 obj.v = union_map_apply_union_pw_qpolynomial_fold(arg.v, obj.v);
1307         }
1308         if (!obj.v)
1309                 goto error2;
1310
1311         if (isl_stream_eat(s, ')'))
1312                 goto error2;
1313
1314         return obj;
1315 error:
1316         free_obj(arg);
1317 error2:
1318         free_obj(obj);
1319         obj.type = isl_obj_none;
1320         obj.v = NULL;
1321         return obj;
1322 }
1323
1324 struct add_vertex_data {
1325         struct isl_list *list;
1326         int i;
1327 };
1328
1329 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
1330 {
1331         struct add_vertex_data *data = (struct add_vertex_data *)user;
1332         isl_basic_set *expr;
1333
1334         expr = isl_vertex_get_expr(vertex);
1335
1336         data->list->obj[data->i].type = isl_obj_set;
1337         data->list->obj[data->i].v = isl_set_from_basic_set(expr);
1338         data->i++;
1339
1340         isl_vertex_free(vertex);
1341
1342         return 0;
1343 }
1344
1345 static int set_vertices(__isl_take isl_set *set, void *user)
1346 {
1347         isl_ctx *ctx;
1348         isl_basic_set *hull;
1349         isl_vertices *vertices = NULL;
1350         struct isl_list *list = NULL;
1351         int r;
1352         struct add_vertex_data *data = (struct add_vertex_data *)user;
1353
1354         set = isl_set_remove_divs(set);
1355         hull = isl_set_convex_hull(set);
1356         vertices = isl_basic_set_compute_vertices(hull);
1357         isl_basic_set_free(hull);
1358
1359         list = data->list;
1360
1361         ctx = isl_vertices_get_ctx(vertices);
1362         data->list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
1363         if (!data->list)
1364                 goto error;
1365
1366         data->i = 0;
1367         r = isl_vertices_foreach_vertex(vertices, &add_vertex, user);
1368
1369         data->list = isl_list_concat(list, data->list);
1370
1371         isl_vertices_free(vertices);
1372
1373         return r;
1374 error:
1375         data->list = list;
1376         isl_vertices_free(vertices);
1377         return -1;
1378 }
1379
1380 static struct isl_obj vertices(struct isl_stream *s,
1381         struct isl_hash_table *table)
1382 {
1383         isl_ctx *ctx;
1384         struct isl_obj obj;
1385         struct isl_list *list = NULL;
1386         isl_union_set *uset;
1387         struct add_vertex_data data = { NULL };
1388
1389         obj = read_expr(s, table);
1390         obj = convert(s->ctx, obj, isl_obj_union_set);
1391         isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1392         uset = obj.v;
1393         obj.v = NULL;
1394
1395         ctx = isl_union_set_get_ctx(uset);
1396         list = isl_list_alloc(ctx, 0);
1397         if (!list)
1398                 goto error;
1399
1400         data.list = list;
1401
1402         if (isl_union_set_foreach_set(uset, &set_vertices, &data) < 0)
1403                 goto error;
1404
1405         isl_union_set_free(uset);
1406
1407         obj.type = isl_obj_list;
1408         obj.v = data.list;
1409
1410         return obj;
1411 error:
1412         isl_union_set_free(uset);
1413         isl_list_free(data.list);
1414         free_obj(obj);
1415         obj.type = isl_obj_none;
1416         obj.v = NULL;
1417         return obj;
1418 }
1419
1420 static struct isl_obj type_of(struct isl_stream *s,
1421         struct isl_hash_table *table)
1422 {
1423         isl_ctx *ctx;
1424         struct isl_obj obj;
1425         const char *type = "unknown";
1426
1427         obj = read_expr(s, table);
1428
1429         if (obj.type == isl_obj_map ||
1430             obj.type == isl_obj_union_map)
1431                 type = "map";
1432         if (obj.type == isl_obj_set ||
1433             obj.type == isl_obj_union_set)
1434                 type = "set";
1435         if (obj.type == isl_obj_pw_qpolynomial ||
1436             obj.type == isl_obj_union_pw_qpolynomial)
1437                 type = "piecewise quasipolynomial";
1438         if (obj.type == isl_obj_pw_qpolynomial_fold ||
1439             obj.type == isl_obj_union_pw_qpolynomial_fold)
1440                 type = "piecewise quasipolynomial fold";
1441         if (obj.type == isl_obj_list)
1442                 type = "list";
1443         if (obj.type == isl_obj_bool)
1444                 type = "boolean";
1445         if (obj.type == isl_obj_str)
1446                 type = "string";
1447         if (obj.type == isl_obj_int)
1448                 type = "int";
1449
1450         free_obj(obj);
1451         obj.type = isl_obj_str;
1452         obj.v = isl_str_from_string(s->ctx, strdup(type));
1453
1454         return obj;
1455 }
1456
1457 static __isl_give isl_union_map *read_map(struct isl_stream *s,
1458         struct isl_hash_table *table)
1459 {
1460         struct isl_obj obj;
1461
1462         obj = read_obj(s, table);
1463         obj = convert(s->ctx, obj, isl_obj_union_map);
1464         isl_assert(s->ctx, obj.type == isl_obj_union_map, goto error);
1465         return obj.v;
1466 error:
1467         free_obj(obj);
1468         return NULL;
1469 }
1470
1471 static struct isl_obj last_any(struct isl_stream *s,
1472         struct isl_hash_table *table, __isl_take isl_union_map *must_source,
1473         __isl_take isl_union_map *may_source)
1474 {
1475         struct isl_obj obj = { isl_obj_none, NULL };
1476         isl_union_map *sink = NULL;
1477         isl_union_map *schedule = NULL;
1478         isl_union_map *may_dep;
1479         isl_union_map *must_dep;
1480
1481         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1482                 goto error;
1483
1484         sink = read_map(s, table);
1485         if (!sink)
1486                 goto error;
1487
1488         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1489                 goto error;
1490
1491         schedule = read_map(s, table);
1492         if (!schedule)
1493                 goto error;
1494
1495         if (isl_union_map_compute_flow(sink, must_source, may_source,
1496                                        schedule, &must_dep, &may_dep,
1497                                        NULL, NULL) < 0)
1498                 return obj;
1499
1500         obj.type = isl_obj_union_map;
1501         obj.v = isl_union_map_union(must_dep, may_dep);
1502
1503         return obj;
1504 error:
1505         isl_union_map_free(may_source);
1506         isl_union_map_free(must_source);
1507         isl_union_map_free(sink);
1508         isl_union_map_free(schedule);
1509         free_obj(obj);
1510         obj.type = isl_obj_none;
1511         obj.v = NULL;
1512         return obj;
1513 }
1514
1515 static struct isl_obj any(struct isl_stream *s, struct isl_hash_table *table)
1516 {
1517         struct isl_obj obj = { isl_obj_none, NULL };
1518         isl_union_map *must_source = NULL;
1519         isl_union_map *may_source = NULL;
1520         isl_union_map *sink = NULL;
1521         isl_union_map *schedule = NULL;
1522         isl_union_map *may_dep;
1523
1524         may_source = read_map(s, table);
1525         if (!may_source)
1526                 goto error;
1527
1528         if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) {
1529                 must_source = read_map(s, table);
1530                 if (!must_source)
1531                         goto error;
1532                 return last_any(s, table, must_source, may_source);
1533         }
1534
1535         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1536                 goto error;
1537
1538         sink = read_map(s, table);
1539         if (!sink)
1540                 goto error;
1541
1542         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1543                 goto error;
1544
1545         schedule = read_map(s, table);
1546         if (!schedule)
1547                 goto error;
1548
1549         must_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1550         if (isl_union_map_compute_flow(sink, must_source, may_source,
1551                                        schedule, NULL, &may_dep,
1552                                        NULL, NULL) < 0)
1553                 return obj;
1554
1555         obj.type = isl_obj_union_map;
1556         obj.v = may_dep;
1557
1558         return obj;
1559 error:
1560         isl_union_map_free(may_source);
1561         isl_union_map_free(must_source);
1562         isl_union_map_free(sink);
1563         isl_union_map_free(schedule);
1564         free_obj(obj);
1565         obj.type = isl_obj_none;
1566         obj.v = NULL;
1567         return obj;
1568 }
1569
1570 static struct isl_obj last(struct isl_stream *s, struct isl_hash_table *table)
1571 {
1572         struct isl_obj obj = { isl_obj_none, NULL };
1573         struct isl_list *list = NULL;
1574         isl_union_map *must_source = NULL;
1575         isl_union_map *may_source = NULL;
1576         isl_union_map *sink = NULL;
1577         isl_union_map *schedule = NULL;
1578         isl_union_map *must_dep;
1579         isl_union_map *must_no_source;
1580
1581         must_source = read_map(s, table);
1582         if (!must_source)
1583                 goto error;
1584
1585         if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) {
1586                 may_source = read_map(s, table);
1587                 if (!may_source)
1588                         goto error;
1589                 return last_any(s, table, must_source, may_source);
1590         }
1591
1592         list = isl_list_alloc(s->ctx, 2);
1593         if (!list)
1594                 goto error;
1595
1596         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1597                 goto error;
1598
1599         sink = read_map(s, table);
1600         if (!sink)
1601                 goto error;
1602
1603         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1604                 goto error;
1605
1606         schedule = read_map(s, table);
1607         if (!schedule)
1608                 goto error;
1609
1610         may_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1611         if (isl_union_map_compute_flow(sink, must_source, may_source,
1612                                        schedule, &must_dep, NULL,
1613                                        &must_no_source, NULL) < 0)
1614                 return obj;
1615
1616         list->obj[0].type = isl_obj_union_map;
1617         list->obj[0].v = must_dep;
1618         list->obj[1].type = isl_obj_union_map;
1619         list->obj[1].v = must_no_source;
1620
1621         obj.v = list;
1622         obj.type = isl_obj_list;
1623
1624         return obj;
1625 error:
1626         isl_list_free(list);
1627         isl_union_map_free(may_source);
1628         isl_union_map_free(must_source);
1629         isl_union_map_free(sink);
1630         isl_union_map_free(schedule);
1631         free_obj(obj);
1632         obj.type = isl_obj_none;
1633         obj.v = NULL;
1634         return obj;
1635 }
1636
1637 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
1638 {
1639         struct isl_token *tok;
1640
1641         if (isl_stream_eat_if_available(s, '+'))
1642                 return transitive_closure(s->ctx, obj);
1643
1644         tok = isl_stream_next_token(s);
1645         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
1646                 isl_stream_error(s, tok, "expecting -1");
1647                 if (tok)
1648                         isl_stream_push_token(s, tok);
1649                 goto error;
1650         }
1651         isl_token_free(tok);
1652         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
1653         if (obj.type != isl_obj_union_map)
1654                 obj = convert(s->ctx, obj, isl_obj_union_map);
1655
1656         obj.v = isl_union_map_reverse(obj.v);
1657         if (!obj.v)
1658                 goto error;
1659
1660         return obj;
1661 error:
1662         free_obj(obj);
1663         obj.type = isl_obj_none;
1664         obj.v = NULL;
1665         return obj;
1666 }
1667
1668 static struct isl_obj read_from_file(struct isl_stream *s)
1669 {
1670         struct isl_obj obj;
1671         struct isl_token *tok;
1672         struct isl_stream *s_file;
1673         struct iscc_options *options;
1674         FILE *file;
1675
1676         tok = isl_stream_next_token(s);
1677         if (!tok || tok->type != ISL_TOKEN_STRING) {
1678                 isl_stream_error(s, tok, "expecting filename");
1679                 isl_token_free(tok);
1680                 goto error;
1681         }
1682
1683         options = isl_ctx_peek_iscc_options(s->ctx);
1684         if (!options || !options->io) {
1685                 isl_token_free(tok);
1686                 isl_die(s->ctx, isl_error_invalid,
1687                         "read operation not allowed", goto error);
1688         }
1689
1690         file = fopen(tok->u.s, "r");
1691         isl_token_free(tok);
1692         isl_assert(s->ctx, file, goto error);
1693
1694         s_file = isl_stream_new_file(s->ctx, file);
1695         if (!s_file) {
1696                 fclose(file);
1697                 goto error;
1698         }
1699
1700         obj = isl_stream_read_obj(s_file);
1701
1702         isl_stream_free(s_file);
1703         fclose(file);
1704
1705         return obj;
1706 error:
1707         obj.type = isl_obj_none;
1708         obj.v = NULL;
1709         return obj;
1710 }
1711
1712 static struct isl_obj write_to_file(struct isl_stream *s,
1713         struct isl_hash_table *table)
1714 {
1715         struct isl_obj obj;
1716         struct isl_token *tok;
1717         struct isl_stream *s_file;
1718         struct iscc_options *options;
1719         FILE *file;
1720         isl_printer *p;
1721
1722         tok = isl_stream_next_token(s);
1723         if (!tok || tok->type != ISL_TOKEN_STRING) {
1724                 isl_stream_error(s, tok, "expecting filename");
1725                 isl_token_free(tok);
1726                 goto error;
1727         }
1728
1729         obj = read_expr(s, table);
1730
1731         options = isl_ctx_peek_iscc_options(s->ctx);
1732         if (!options || !options->io) {
1733                 isl_token_free(tok);
1734                 isl_die(s->ctx, isl_error_invalid,
1735                         "write operation not allowed", goto error);
1736         }
1737
1738         file = fopen(tok->u.s, "w");
1739         isl_token_free(tok);
1740         if (!file)
1741                 isl_die(s->ctx, isl_error_unknown,
1742                         "could not open file for writing", goto error);
1743
1744         p = isl_printer_to_file(s->ctx, file);
1745         p = isl_printer_set_output_format(p, options->format);
1746         p = obj.type->print(p, obj.v);
1747         p = isl_printer_end_line(p);
1748         isl_printer_free(p);
1749
1750         fclose(file);
1751 error:
1752         free_obj(obj);
1753         obj.type = isl_obj_none;
1754         obj.v = NULL;
1755         return obj;
1756 }
1757
1758 static struct isl_obj read_string_if_available(struct isl_stream *s)
1759 {
1760         struct isl_token *tok;
1761         struct isl_obj obj = { isl_obj_none, NULL };
1762
1763         tok = isl_stream_next_token(s);
1764         if (!tok)
1765                 return obj;
1766         if (tok->type == ISL_TOKEN_STRING) {
1767                 isl_str *str;
1768                 str = isl_str_alloc(s->ctx);
1769                 if (!str)
1770                         goto error;
1771                 str->s = strdup(tok->u.s);
1772                 isl_token_free(tok);
1773                 obj.v = str;
1774                 obj.type = isl_obj_str;
1775         } else
1776                 isl_stream_push_token(s, tok);
1777         return obj;
1778 error:
1779         isl_token_free(tok);
1780         return obj;
1781 }
1782
1783 static struct isl_obj read_obj(struct isl_stream *s,
1784         struct isl_hash_table *table)
1785 {
1786         struct isl_obj obj = { isl_obj_none, NULL };
1787         char *name = NULL;
1788         struct isc_un_op *op = NULL;
1789
1790         obj = read_string_if_available(s);
1791         if (obj.v)
1792                 return obj;
1793         if (isl_stream_eat_if_available(s, '(')) {
1794                 obj = read_expr(s, table);
1795                 if (!obj.v || isl_stream_eat(s, ')'))
1796                         goto error;
1797         } else {
1798                 op = read_prefix_un_op_if_available(s);
1799                 if (op)
1800                         return read_un_op_expr(s, table, op);
1801
1802                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_READ]))
1803                         return read_from_file(s);
1804                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_WRITE]))
1805                         return write_to_file(s, table);
1806                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_VERTICES]))
1807                         return vertices(s, table);
1808                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY]))
1809                         return any(s, table);
1810                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST]))
1811                         return last(s, table);
1812                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_TYPEOF]))
1813                         return type_of(s, table);
1814
1815                 name = isl_stream_read_ident_if_available(s);
1816                 if (name)
1817                         obj = stored_obj(s->ctx, table, name);
1818                 else
1819                         obj = isl_stream_read_obj(s);
1820                 if (!obj.v)
1821                         goto error;
1822         }
1823
1824         if (isl_stream_eat_if_available(s, '^'))
1825                 obj = power(s, obj);
1826         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
1827                 obj = obj_at_index(s, obj);
1828         else if (is_subtype(obj, isl_obj_union_map) &&
1829                  isl_stream_eat_if_available(s, '(')) {
1830                 obj = convert(s->ctx, obj, isl_obj_union_map);
1831                 obj = apply(s, obj.v, table);
1832         } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial) &&
1833                    isl_stream_eat_if_available(s, '(')) {
1834                 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial);
1835                 obj = apply_fun(s, obj, table);
1836         } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial_fold) &&
1837                    isl_stream_eat_if_available(s, '(')) {
1838                 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial_fold);
1839                 obj = apply_fun(s, obj, table);
1840         }
1841
1842         return obj;
1843 error:
1844         free_obj(obj);
1845         obj.type = isl_obj_none;
1846         obj.v = NULL;
1847         return obj;
1848 }
1849
1850 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
1851         struct isl_obj lhs, struct isl_obj rhs)
1852 {
1853         int i;
1854
1855         for (i = 0; ; ++i) {
1856                 if (!bin_ops[i].op)
1857                         break;
1858                 if (bin_ops[i].op != like->op)
1859                         continue;
1860                 if (!is_subtype(lhs, bin_ops[i].lhs))
1861                         continue;
1862                 if (!is_subtype(rhs, bin_ops[i].rhs))
1863                         continue;
1864
1865                 return &bin_ops[i];
1866         }
1867
1868         for (i = 0; ; ++i) {
1869                 if (!named_bin_ops[i].name)
1870                         break;
1871                 if (named_bin_ops[i].op.op != like->op)
1872                         continue;
1873                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1874                         continue;
1875                 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
1876                         continue;
1877
1878                 return &named_bin_ops[i].op;
1879         }
1880
1881         return NULL;
1882 }
1883
1884 static int next_is_neg_int(struct isl_stream *s)
1885 {
1886         struct isl_token *tok;
1887         int ret;
1888
1889         tok = isl_stream_next_token(s);
1890         ret = tok && tok->type == ISL_TOKEN_VALUE && isl_int_is_neg(tok->u.v);
1891         isl_stream_push_token(s, tok);
1892
1893         return ret;
1894 }
1895
1896 static struct isl_obj read_expr(struct isl_stream *s,
1897         struct isl_hash_table *table)
1898 {
1899         struct isl_obj obj = { isl_obj_none, NULL };
1900         struct isl_obj right_obj = { isl_obj_none, NULL };
1901
1902         obj = read_obj(s, table);
1903         for (; obj.v;) {
1904                 struct isc_bin_op *op = NULL;
1905
1906                 op = read_bin_op_if_available(s, obj);
1907                 if (!op)
1908                         break;
1909
1910                 right_obj = read_obj(s, table);
1911
1912                 op = find_matching_bin_op(op, obj, right_obj);
1913
1914                 if (!op)
1915                         isl_die(s->ctx, isl_error_invalid,
1916                             "no such binary operator defined on given operands",
1917                             goto error);
1918
1919                 obj = convert(s->ctx, obj, op->lhs);
1920                 right_obj = convert(s->ctx, right_obj, op->rhs);
1921                 obj.v = op->fn(obj.v, right_obj.v);
1922                 obj.type = op->res;
1923         }
1924
1925         if (obj.type == isl_obj_int && next_is_neg_int(s)) {
1926                 right_obj = read_obj(s, table);
1927                 obj.v = isl_int_obj_add(obj.v, right_obj.v);
1928         }
1929
1930         return obj;
1931 error:
1932         free_obj(right_obj);
1933         free_obj(obj);
1934         obj.type = isl_obj_none;
1935         obj.v = NULL;
1936         return obj;
1937 }
1938
1939 static __isl_give isl_printer *source_file(struct isl_stream *s,
1940         struct isl_hash_table *table, __isl_take isl_printer *p);
1941
1942 static __isl_give isl_printer *read_line(struct isl_stream *s,
1943         struct isl_hash_table *table, __isl_take isl_printer *p)
1944 {
1945         struct isl_obj obj = { isl_obj_none, NULL };
1946         char *lhs = NULL;
1947         int assign = 0;
1948         struct isc_bin_op *op = NULL;
1949
1950         if (!p)
1951                 return NULL;
1952         if (isl_stream_is_empty(s))
1953                 return p;
1954
1955         if (isl_stream_eat_if_available(s, iscc_op[ISCC_SOURCE]))
1956                 return source_file(s, table, p);
1957
1958         assign = is_assign(s);
1959         if (assign) {
1960                 lhs = isl_stream_read_ident_if_available(s);
1961                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
1962                         goto error;
1963         }
1964
1965         obj = read_expr(s, table);
1966         if (obj.type == isl_obj_none || obj.v == NULL)
1967                 goto error;
1968         if (isl_stream_eat(s, ';'))
1969                 goto error;
1970
1971         if (assign) {
1972                 if (do_assign(s->ctx, table, lhs, obj))
1973                         return p;
1974         } else {
1975                 p = obj.type->print(p, obj.v);
1976                 p = isl_printer_end_line(p);
1977                 free_obj(obj);
1978         }
1979
1980         return p;
1981 error:
1982         isl_stream_flush_tokens(s);
1983         isl_stream_skip_line(s);
1984         free(lhs);
1985         free_obj(obj);
1986         return p;
1987 }
1988
1989 int free_cb(void **entry, void *user)
1990 {
1991         struct isl_named_obj *named = *entry;
1992
1993         free_obj(named->obj);
1994         free(named->name);
1995         free(named);
1996
1997         return 0;
1998 }
1999
2000 static void register_named_ops(struct isl_stream *s)
2001 {
2002         int i;
2003
2004         for (i = 0; i < ISCC_N_OP; ++i) {
2005                 iscc_op[i] = isl_stream_register_keyword(s, op_name[i]);
2006                 assert(iscc_op[i] != ISL_TOKEN_ERROR);
2007         }
2008
2009         for (i = 0; ; ++i) {
2010                 if (!named_un_ops[i].name)
2011                         break;
2012                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
2013                                                         named_un_ops[i].name);
2014                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
2015         }
2016
2017         for (i = 0; ; ++i) {
2018                 if (!named_bin_ops[i].name)
2019                         break;
2020                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
2021                                                         named_bin_ops[i].name);
2022                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
2023         }
2024 }
2025
2026 static __isl_give isl_printer *source_file(struct isl_stream *s,
2027         struct isl_hash_table *table, __isl_take isl_printer *p)
2028 {
2029         struct isl_token *tok;
2030         struct isl_stream *s_file;
2031         FILE *file;
2032
2033         tok = isl_stream_next_token(s);
2034         if (!tok || tok->type != ISL_TOKEN_STRING) {
2035                 isl_stream_error(s, tok, "expecting filename");
2036                 isl_token_free(tok);
2037                 return p;
2038         }
2039
2040         file = fopen(tok->u.s, "r");
2041         isl_token_free(tok);
2042         isl_assert(s->ctx, file, return p);
2043
2044         s_file = isl_stream_new_file(s->ctx, file);
2045         if (!s_file) {
2046                 fclose(file);
2047                 return p;
2048         }
2049
2050         register_named_ops(s_file);
2051
2052         while (!s_file->eof)
2053                 p = read_line(s_file, table, p);
2054
2055         isl_stream_free(s_file);
2056         fclose(file);
2057
2058         isl_stream_eat(s, ';');
2059
2060         return p;
2061 }
2062
2063 int main(int argc, char **argv)
2064 {
2065         struct isl_ctx *ctx;
2066         struct isl_stream *s;
2067         struct isl_hash_table *table;
2068         struct iscc_options *options;
2069         isl_printer *p;
2070
2071         options = iscc_options_new_with_defaults();
2072         assert(options);
2073         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
2074
2075         ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
2076         s = isl_stream_new_file(ctx, stdin);
2077         assert(s);
2078         table = isl_hash_table_alloc(ctx, 10);
2079         assert(table);
2080         p = isl_printer_to_file(ctx, stdout);
2081         p = isl_printer_set_output_format(p, options->format);
2082         assert(p);
2083
2084         register_named_ops(s);
2085
2086         while (p && !s->eof) {
2087                 p = read_line(s, table, p);
2088         }
2089
2090         isl_printer_free(p);
2091         isl_hash_table_foreach(ctx, table, free_cb, NULL);
2092         isl_hash_table_free(ctx, table);
2093         isl_stream_free(s);
2094         isl_ctx_free(ctx);
2095
2096         return 0;
2097 }