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_pw_qpolynomial_upper_bound(
 565         __isl_take isl_union_pw_qpolynomial *upwqp)
 566 {
 567         isl_ctx *ctx;
 568         struct isl_list *list;
 569         int tight;
 570
 571         ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
 572         list = isl_list_alloc(ctx, 2);
 573         if (!list)
 574                 goto error2;
 575
 576         list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
 577         list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
 578                                                         isl_fold_max, &tight);
 579         list->obj[1].type = isl_obj_bool;
 580         list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
 581         if (tight < 0 || !list->obj[0].v)
 582                 goto error;
 583
 584         return list;
 585 error2:
 586         isl_union_pw_qpolynomial_free(upwqp);
 587 error:
 588         isl_list_free(list);
 589         return NULL;
 590 }
 591
 592 #ifdef HAVE_CLOOG
 593 void *map_codegen(void *arg)
 594 {
 595         isl_dim *dim;
 596         isl_union_map *umap = (isl_union_map *)arg;
 597         isl_ctx *ctx = isl_union_map_get_ctx(umap);
 598         CloogState *state;
 599         CloogOptions *options;
 600         CloogDomain *context;
 601         CloogUnionDomain *ud;
 602         CloogInput *input;
 603         struct clast_stmt *stmt;
 604
 605         state = cloog_isl_state_malloc(ctx);
 606         options = cloog_options_malloc(state);
 607         options->language = LANGUAGE_C;
 608         options->strides = 1;
 609
 610         ud = cloog_union_domain_from_isl_union_map(isl_union_map_copy(umap));
 611
 612         dim = isl_union_map_get_dim(umap);
 613         context = cloog_domain_from_isl_set(isl_set_universe(dim));
 614
 615         input = cloog_input_alloc(context, ud);
 616
 617         stmt = cloog_clast_create_from_input(input, options);
 618         clast_pprint(stdout, stmt, 0, options);
 619         cloog_clast_free(stmt);
 620
 621 error:
 622         cloog_options_free(options);
 623         cloog_state_free(state);
 624         isl_union_map_free(umap);
 625         return NULL;
 626 }
 627
 628 void *set_codegen(void *arg)
 629 {
 630         isl_dim *dim;
 631         isl_union_set *uset = (isl_union_set *)arg;
 632         isl_ctx *ctx = isl_union_set_get_ctx(uset);
 633         CloogState *state;
 634         CloogOptions *options;
 635         CloogDomain *context;
 636         CloogUnionDomain *ud;
 637         CloogInput *input;
 638         struct clast_stmt *stmt;
 639
 640         if (isl_union_set_n_set(uset) > 1)
 641                 isl_die(ctx, isl_error_invalid,
 642                         "code generation for more than one domain "
 643                         "requires a schedule", goto error);
 644
 645         state = cloog_isl_state_malloc(ctx);
 646         options = cloog_options_malloc(state);
 647         options->language = LANGUAGE_C;
 648         options->strides = 1;
 649
 650         ud = cloog_union_domain_from_isl_union_set(isl_union_set_copy(uset));
 651
 652         dim = isl_union_set_get_dim(uset);
 653         context = cloog_domain_from_isl_set(isl_set_universe(dim));
 654
 655         input = cloog_input_alloc(context, ud);
 656
 657         stmt = cloog_clast_create_from_input(input, options);
 658         clast_pprint(stdout, stmt, 0, options);
 659         cloog_clast_free(stmt);
 660
 661         cloog_options_free(options);
 662         cloog_state_free(state);
 663 error:
 664         isl_union_set_free(uset);
 665         return NULL;
 666 }
 667 #endif
 668
 669 static int add_point(__isl_take isl_point *pnt, void *user)
 670 {
 671         isl_union_set **scan = (isl_union_set **) user;
 672
 673         *scan = isl_union_set_add_set(*scan, isl_set_from_point(pnt));
 674
 675         return 0;
 676 }
 677
 678 static __isl_give isl_union_set *union_set_scan(__isl_take isl_union_set *uset)
 679 {
 680         isl_union_set *scan;
 681
 682         scan = isl_union_set_empty(isl_union_set_get_dim(uset));
 683
 684         if (isl_union_set_foreach_point(uset, add_point, &scan) < 0) {
 685                 isl_union_set_free(scan);
 686                 return uset;
 687         }
 688
 689         isl_union_set_free(uset);
 690         return scan;
 691 }
 692
 693 static __isl_give isl_union_map *union_map_scan(__isl_take isl_union_map *umap)
 694 {
 695         return isl_union_set_unwrap(union_set_scan(isl_union_map_wrap(umap)));
 696 }
 697
 698 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_poly(
 699         __isl_take isl_union_pw_qpolynomial *upwqp)
 700 {
 701         return isl_union_pw_qpolynomial_to_polynomial(upwqp, 0);
 702 }
 703
 704 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_lpoly(
 705         __isl_take isl_union_pw_qpolynomial *upwqp)
 706 {
 707         return isl_union_pw_qpolynomial_to_polynomial(upwqp, -1);
 708 }
 709
 710 static __isl_give isl_union_pw_qpolynomial *union_pw_qpolynomial_upoly(
 711         __isl_take isl_union_pw_qpolynomial *upwqp)
 712 {
 713         return isl_union_pw_qpolynomial_to_polynomial(upwqp, 1);
 714 }
 715
 716 typedef void *(*isc_un_op_fn)(void *arg);
 717 struct isc_un_op {
 718         enum isl_token_type     op;
 719         isl_obj_type            arg;
 720         isl_obj_type            res;
 721         isc_un_op_fn            fn;
 722 };
 723 struct isc_named_un_op {
 724         char                    *name;
 725         struct isc_un_op        op;
 726 };
 727 struct isc_named_un_op named_un_ops[] = {
 728         {"aff", { -1,   isl_obj_union_map,      isl_obj_union_map,
 729                 (isc_un_op_fn) &isl_union_map_affine_hull } },
 730         {"aff", { -1,   isl_obj_union_set,      isl_obj_union_set,
 731                 (isc_un_op_fn) &isl_union_set_affine_hull } },
 732         {"card",        { -1,   isl_obj_union_set,
 733                 isl_obj_union_pw_qpolynomial,
 734                 (isc_un_op_fn) &isl_union_set_card } },
 735         {"card",        { -1,   isl_obj_union_map,
 736                 isl_obj_union_pw_qpolynomial,
 737                 (isc_un_op_fn) &isl_union_map_card } },
 738         {"coalesce",    { -1,   isl_obj_union_set,      isl_obj_union_set,
 739                 (isc_un_op_fn) &isl_union_set_coalesce } },
 740         {"coalesce",    { -1,   isl_obj_union_map,      isl_obj_union_map,
 741                 (isc_un_op_fn) &isl_union_map_coalesce } },
 742         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial,
 743                 isl_obj_union_pw_qpolynomial,
 744                 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
 745         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial_fold,
 746                 isl_obj_union_pw_qpolynomial_fold,
 747                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
 748 #ifdef HAVE_CLOOG
 749         {"codegen",     { -1,   isl_obj_union_set, isl_obj_none,
 750                 &set_codegen } },
 751         {"codegen",     { -1,   isl_obj_union_map, isl_obj_none,
 752                 &map_codegen } },
 753 #endif
 754         {"deltas",      { -1,   isl_obj_union_map,      isl_obj_union_set,
 755                 (isc_un_op_fn) &isl_union_map_deltas } },
 756         {"deltas_map",  { -1,   isl_obj_union_map,      isl_obj_union_map,
 757                 (isc_un_op_fn) &isl_union_map_deltas_map } },
 758         {"dom", { -1,   isl_obj_union_map,      isl_obj_union_set,
 759                 (isc_un_op_fn) &isl_union_map_domain } },
 760         {"dom", { -1,   isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 761                 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
 762         {"dom", { -1,   isl_obj_union_pw_qpolynomial_fold,
 763                 isl_obj_union_set,
 764                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
 765         {"domain",      { -1,   isl_obj_union_map,      isl_obj_union_set,
 766                 (isc_un_op_fn) &isl_union_map_domain } },
 767         {"domain",      { -1,   isl_obj_union_pw_qpolynomial,
 768                 isl_obj_union_set,
 769                 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
 770         {"domain",      { -1,   isl_obj_union_pw_qpolynomial_fold,
 771                 isl_obj_union_set,
 772                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
 773         {"domain_map",  { -1,   isl_obj_union_map,      isl_obj_union_map,
 774                 (isc_un_op_fn) &isl_union_map_domain_map } },
 775         {"ran", { -1,   isl_obj_union_map,      isl_obj_union_set,
 776                 (isc_un_op_fn) &isl_union_map_range } },
 777         {"range",       { -1,   isl_obj_union_map,      isl_obj_union_set,
 778                 (isc_un_op_fn) &isl_union_map_range } },
 779         {"range_map",   { -1,   isl_obj_union_map,      isl_obj_union_map,
 780                 (isc_un_op_fn) &isl_union_map_range_map } },
 781         {"identity",    { -1,   isl_obj_union_set,      isl_obj_union_map,
 782                 (isc_un_op_fn) &isl_union_set_identity } },
 783         {"lexmin",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 784                 (isc_un_op_fn) &isl_union_map_lexmin } },
 785         {"lexmax",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 786                 (isc_un_op_fn) &isl_union_map_lexmax } },
 787         {"lexmin",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 788                 (isc_un_op_fn) &isl_union_set_lexmin } },
 789         {"lexmax",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 790                 (isc_un_op_fn) &isl_union_set_lexmax } },
 791         {"poly",        { -1,   isl_obj_union_map,      isl_obj_union_map,
 792                 (isc_un_op_fn) &isl_union_map_polyhedral_hull } },
 793         {"poly",        { -1,   isl_obj_union_set,      isl_obj_union_set,
 794                 (isc_un_op_fn) &isl_union_set_polyhedral_hull } },
 795         {"poly",        { -1,   isl_obj_union_pw_qpolynomial,
 796                 isl_obj_union_pw_qpolynomial,
 797                 (isc_un_op_fn) &union_pw_qpolynomial_poly } },
 798         {"lpoly",       { -1,   isl_obj_union_pw_qpolynomial,
 799                 isl_obj_union_pw_qpolynomial,
 800                 (isc_un_op_fn) &union_pw_qpolynomial_lpoly } },
 801         {"upoly",       { -1,   isl_obj_union_pw_qpolynomial,
 802                 isl_obj_union_pw_qpolynomial,
 803                 (isc_un_op_fn) &union_pw_qpolynomial_upoly } },
 804         {"sample",      { -1,   isl_obj_union_set,      isl_obj_set,
 805                 (isc_un_op_fn) &union_set_sample } },
 806         {"sample",      { -1,   isl_obj_union_map,      isl_obj_map,
 807                 (isc_un_op_fn) &union_map_sample } },
 808         {"scan",        { -1,   isl_obj_union_set,      isl_obj_union_set,
 809                 (isc_un_op_fn) &union_set_scan } },
 810         {"scan",        { -1,   isl_obj_union_map,      isl_obj_union_map,
 811                 (isc_un_op_fn) &union_map_scan } },
 812         {"sum",         { -1,   isl_obj_union_pw_qpolynomial,
 813                 isl_obj_union_pw_qpolynomial,
 814                 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
 815         {"ub",          { -1,   isl_obj_union_pw_qpolynomial, isl_obj_list,
 816                 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
 817         {"unwrap",      { -1,   isl_obj_union_set,      isl_obj_union_map,
 818                 (isc_un_op_fn) &isl_union_set_unwrap } },
 819         {"wrap",        { -1,   isl_obj_union_map,      isl_obj_union_set,
 820                 (isc_un_op_fn) &isl_union_map_wrap } },
 821         NULL
 822 };
 823
 824 struct isl_named_obj {
 825         char            *name;
 826         struct isl_obj  obj;
 827 };
 828
 829 static void free_obj(struct isl_obj obj)
 830 {
 831         obj.type->free(obj.v);
 832 }
 833
 834 static int same_name(const void *entry, const void *val)
 835 {
 836         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 837
 838         return !strcmp(named->name, val);
 839 }
 840
 841 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 842         char *name, struct isl_obj obj)
 843 {
 844         struct isl_hash_table_entry *entry;
 845         uint32_t name_hash;
 846         struct isl_named_obj *named;
 847
 848         name_hash = isl_hash_string(isl_hash_init(), name);
 849         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 850         if (!entry)
 851                 goto error;
 852         if (entry->data) {
 853                 named = entry->data;
 854                 free_obj(named->obj);
 855                 free(name);
 856         } else {
 857                 named = isl_alloc_type(ctx, struct isl_named_obj);
 858                 if (!named)
 859                         goto error;
 860                 named->name = name;
 861                 entry->data = named;
 862         }
 863         named->obj = obj;
 864
 865         return 0;
 866 error:
 867         free_obj(obj);
 868         free(name);
 869         return -1;
 870 }
 871
 872 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 873         struct isl_hash_table *table, char *name)
 874 {
 875         struct isl_obj obj = { isl_obj_none, NULL };
 876         struct isl_hash_table_entry *entry;
 877         uint32_t name_hash;
 878
 879         name_hash = isl_hash_string(isl_hash_init(), name);
 880         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 881         if (entry) {
 882                 struct isl_named_obj *named;
 883                 named = entry->data;
 884                 obj = named->obj;
 885         } else
 886                 fprintf(stderr, "unknown identifier '%s'\n", name);
 887
 888         free(name);
 889         obj.v = obj.type->copy(obj.v);
 890         return obj;
 891 }
 892
 893 static int is_subtype(struct isl_obj obj, isl_obj_type super)
 894 {
 895         if (obj.type == super)
 896                 return 1;
 897         if (obj.type == isl_obj_map && super == isl_obj_union_map)
 898                 return 1;
 899         if (obj.type == isl_obj_set && super == isl_obj_union_set)
 900                 return 1;
 901         if (obj.type == isl_obj_pw_qpolynomial &&
 902             super == isl_obj_union_pw_qpolynomial)
 903                 return 1;
 904         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 905             super == isl_obj_union_pw_qpolynomial_fold)
 906                 return 1;
 907         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
 908                 return 1;
 909         if (obj.type == isl_obj_list) {
 910                 struct isl_list *list = obj.v;
 911                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
 912                         return is_subtype(list->obj[0], super);
 913         }
 914         if (super == isl_obj_str)
 915                 return 1;
 916         return 0;
 917 }
 918
 919 static struct isl_obj obj_at(struct isl_obj obj, int i)
 920 {
 921         struct isl_list *list = obj.v;
 922
 923         obj = list->obj[i];
 924         obj.v = obj.type->copy(obj.v);
 925
 926         isl_list_free(list);
 927
 928         return obj;
 929 }
 930
 931 static struct isl_obj convert(isl_ctx *ctx, struct isl_obj obj,
 932         isl_obj_type type)
 933 {
 934         if (obj.type == type)
 935                 return obj;
 936         if (obj.type == isl_obj_map && type == isl_obj_union_map) {
 937                 obj.type = isl_obj_union_map;
 938                 obj.v = isl_union_map_from_map(obj.v);
 939                 return obj;
 940         }
 941         if (obj.type == isl_obj_set && type == isl_obj_union_set) {
 942                 obj.type = isl_obj_union_set;
 943                 obj.v = isl_union_set_from_set(obj.v);
 944                 return obj;
 945         }
 946         if (obj.type == isl_obj_pw_qpolynomial &&
 947             type == isl_obj_union_pw_qpolynomial) {
 948                 obj.type = isl_obj_union_pw_qpolynomial;
 949                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
 950                 return obj;
 951         }
 952         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 953             type == isl_obj_union_pw_qpolynomial_fold) {
 954                 obj.type = isl_obj_union_pw_qpolynomial_fold;
 955                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
 956                 return obj;
 957         }
 958         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
 959                 if (type == isl_obj_union_map) {
 960                         obj.type = isl_obj_union_map;
 961                         return obj;
 962                 }
 963                 if (type == isl_obj_union_pw_qpolynomial) {
 964                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 965                         isl_union_set_free(obj.v);
 966                         obj.v = isl_union_pw_qpolynomial_zero(dim);
 967                         obj.type = isl_obj_union_pw_qpolynomial;
 968                         return obj;
 969                 }
 970                 if (type == isl_obj_union_pw_qpolynomial_fold) {
 971                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 972                         isl_union_set_free(obj.v);
 973                         obj.v = isl_union_pw_qpolynomial_fold_zero(dim,
 974                                                                 isl_fold_list);
 975                         obj.type = isl_obj_union_pw_qpolynomial_fold;
 976                         return obj;
 977                 }
 978         }
 979         if (obj.type == isl_obj_list) {
 980                 struct isl_list *list = obj.v;
 981                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
 982                         return convert(ctx, obj_at(obj, 0), type);
 983         }
 984         if (type == isl_obj_str) {
 985                 isl_str *str;
 986                 isl_printer *p;
 987                 char *s;
 988
 989                 p = isl_printer_to_str(ctx);
 990                 if (!p)
 991                         goto error;
 992                 p = obj.type->print(p, obj.v);
 993                 s = isl_printer_get_str(p);
 994                 isl_printer_free(p);
 995
 996                 str = isl_str_from_string(ctx, s);
 997                 if (!str)
 998                         goto error;
 999                 free_obj(obj);
1000                 obj.v = str;
1001                 obj.type = isl_obj_str;
1002                 return obj;
1003
1004         }
1005 error:
1006         free_obj(obj);
1007         obj.type = isl_obj_none;
1008         obj.v = NULL;
1009         return obj;
1010 }
1011
1012 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
1013         struct isl_obj lhs)
1014 {
1015         int i;
1016         struct isl_token *tok;
1017
1018         tok = isl_stream_next_token(s);
1019         if (!tok)
1020                 return NULL;
1021
1022         for (i = 0; ; ++i) {
1023                 if (!bin_ops[i].op)
1024                         break;
1025                 if (bin_ops[i].op != tok->type)
1026                         continue;
1027                 if (!is_subtype(lhs, bin_ops[i].lhs))
1028                         continue;
1029
1030                 isl_token_free(tok);
1031                 return &bin_ops[i];
1032         }
1033
1034         for (i = 0; ; ++i) {
1035                 if (!named_bin_ops[i].name)
1036                         break;
1037                 if (named_bin_ops[i].op.op != tok->type)
1038                         continue;
1039                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1040                         continue;
1041
1042                 isl_token_free(tok);
1043                 return &named_bin_ops[i].op;
1044         }
1045
1046         isl_stream_push_token(s, tok);
1047
1048         return NULL;
1049 }
1050
1051 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
1052 {
1053         int i;
1054         struct isl_token *tok;
1055
1056         tok = isl_stream_next_token(s);
1057         if (!tok)
1058                 return NULL;
1059
1060         for (i = 0; ; ++i) {
1061                 if (!named_un_ops[i].name)
1062                         break;
1063                 if (named_un_ops[i].op.op != tok->type)
1064                         continue;
1065
1066                 isl_token_free(tok);
1067                 return &named_un_ops[i].op;
1068         }
1069
1070         isl_stream_push_token(s, tok);
1071
1072         return NULL;
1073 }
1074
1075 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
1076         struct isl_obj arg)
1077 {
1078         int i;
1079
1080         for (i = 0; ; ++i) {
1081                 if (!named_un_ops[i].name)
1082                         break;
1083                 if (named_un_ops[i].op.op != like->op)
1084                         continue;
1085                 if (!is_subtype(arg, named_un_ops[i].op.arg))
1086                         continue;
1087
1088                 return &named_un_ops[i].op;
1089         }
1090
1091         return NULL;
1092 }
1093
1094 static int is_assign(struct isl_stream *s)
1095 {
1096         struct isl_token *tok;
1097         struct isl_token *tok2;
1098         int assign;
1099
1100         tok = isl_stream_next_token(s);
1101         if (!tok)
1102                 return 0;
1103         if (tok->type != ISL_TOKEN_IDENT) {
1104                 isl_stream_push_token(s, tok);
1105                 return 0;
1106         }
1107
1108         tok2 = isl_stream_next_token(s);
1109         if (!tok2) {
1110                 isl_stream_push_token(s, tok);
1111                 return 0;
1112         }
1113         assign = tok2->type == ISL_TOKEN_DEF;
1114         isl_stream_push_token(s, tok2);
1115         isl_stream_push_token(s, tok);
1116
1117         return assign;
1118 }
1119
1120 static struct isl_obj read_obj(struct isl_stream *s,
1121         struct isl_hash_table *table);
1122 static struct isl_obj read_expr(struct isl_stream *s,
1123         struct isl_hash_table *table);
1124
1125 static struct isl_obj read_un_op_expr(struct isl_stream *s,
1126         struct isl_hash_table *table, struct isc_un_op *op)
1127 {
1128         struct isl_obj obj = { isl_obj_none, NULL };
1129
1130         obj = read_obj(s, table);
1131         if (!obj.v)
1132                 goto error;
1133
1134         op = find_matching_un_op(op, obj);
1135
1136         if (!op)
1137                 isl_die(s->ctx, isl_error_invalid,
1138                         "no such unary operator defined on given operand",
1139                         goto error);
1140
1141         obj = convert(s->ctx, obj, op->arg);
1142         obj.v = op->fn(obj.v);
1143         obj.type = op->res;
1144
1145         return obj;
1146 error:
1147         free_obj(obj);
1148         obj.type = isl_obj_none;
1149         obj.v = NULL;
1150         return obj;
1151 }
1152
1153 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
1154 {
1155         struct isl_list *list;
1156         int exact;
1157
1158         if (obj.type != isl_obj_union_map)
1159                 obj = convert(ctx, obj, isl_obj_union_map);
1160         isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
1161         list = isl_list_alloc(ctx, 2);
1162         if (!list)
1163                 goto error;
1164
1165         list->obj[0].type = isl_obj_union_map;
1166         list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
1167         list->obj[1].type = isl_obj_bool;
1168         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
1169         obj.v = list;
1170         obj.type = isl_obj_list;
1171         if (exact < 0 || !list->obj[0].v)
1172                 goto error;
1173
1174         return obj;
1175 error:
1176         free_obj(obj);
1177         obj.type = isl_obj_none;
1178         obj.v = NULL;
1179         return obj;
1180 }
1181
1182 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
1183 {
1184         struct isl_list *list = obj.v;
1185         struct isl_token *tok;
1186         int i;
1187
1188         tok = isl_stream_next_token(s);
1189         if (!tok || tok->type != ISL_TOKEN_VALUE) {
1190                 isl_stream_error(s, tok, "expecting index");
1191                 if (tok)
1192                         isl_stream_push_token(s, tok);
1193                 goto error;
1194         }
1195         i = isl_int_get_si(tok->u.v);
1196         isl_token_free(tok);
1197         isl_assert(s->ctx, i < list->n, goto error);
1198         if (isl_stream_eat(s, ']'))
1199                 goto error;
1200
1201         return obj_at(obj, i);
1202 error:
1203         free_obj(obj);
1204         obj.type = isl_obj_none;
1205         obj.v = NULL;
1206         return obj;
1207 }
1208
1209 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
1210         struct isl_hash_table *table)
1211 {
1212         struct isl_obj obj;
1213
1214         obj = read_expr(s, table);
1215         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
1216                            is_subtype(obj, isl_obj_union_map), goto error);
1217
1218         if (obj.type == isl_obj_list) {
1219                 struct isl_list *list = obj.v;
1220                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1221                         obj = obj_at(obj, 0);
1222         }
1223         if (obj.type == isl_obj_set)
1224                 obj = convert(s->ctx, obj, isl_obj_union_set);
1225         else if (obj.type == isl_obj_map)
1226                 obj = convert(s->ctx, obj, isl_obj_union_map);
1227         if (obj.type == isl_obj_union_set) {
1228                 obj.v = isl_union_set_apply(obj.v, umap);
1229         } else
1230                 obj.v = isl_union_map_apply_range(obj.v, umap);
1231         if (!obj.v)
1232                 goto error2;
1233
1234         if (isl_stream_eat(s, ')'))
1235                 goto error2;
1236
1237         return obj;
1238 error:
1239         isl_union_map_free(umap);
1240 error2:
1241         free_obj(obj);
1242         obj.type = isl_obj_none;
1243         obj.v = NULL;
1244         return obj;
1245 }
1246
1247 static struct isl_obj apply_fun(struct isl_stream *s,
1248         struct isl_obj obj, struct isl_hash_table *table)
1249 {
1250         struct isl_obj arg;
1251
1252         arg = read_expr(s, table);
1253         if (!is_subtype(arg, isl_obj_union_map) &&
1254             !is_subtype(arg, isl_obj_union_set))
1255                 isl_die(s->ctx, isl_error_invalid,
1256                         "expecting set of map argument", goto error);
1257
1258         if (arg.type == isl_obj_list) {
1259                 struct isl_list *list = arg.v;
1260                 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
1261                         arg = obj_at(arg, 0);
1262         }
1263         if (arg.type == isl_obj_set)
1264                 arg = convert(s->ctx, arg, isl_obj_union_set);
1265         else if (arg.type == isl_obj_map)
1266                 arg = convert(s->ctx, arg, isl_obj_union_map);
1267         if (arg.type == isl_obj_union_set) {
1268                 arg.v = isl_union_map_from_range(arg.v);
1269                 arg.type = isl_obj_union_map;
1270         }
1271         if (obj.type == isl_obj_union_pw_qpolynomial) {
1272                 obj.v = isl_union_map_apply_union_pw_qpolynomial(arg.v, obj.v);
1273         } else {
1274                 obj.type = isl_obj_list;
1275                 obj.v = union_map_apply_union_pw_qpolynomial_fold(arg.v, obj.v);
1276         }
1277         if (!obj.v)
1278                 goto error2;
1279
1280         if (isl_stream_eat(s, ')'))
1281                 goto error2;
1282
1283         return obj;
1284 error:
1285         free_obj(arg);
1286 error2:
1287         free_obj(obj);
1288         obj.type = isl_obj_none;
1289         obj.v = NULL;
1290         return obj;
1291 }
1292
1293 struct add_vertex_data {
1294         struct isl_list *list;
1295         int i;
1296 };
1297
1298 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
1299 {
1300         struct add_vertex_data *data = (struct add_vertex_data *)user;
1301         isl_basic_set *expr;
1302
1303         expr = isl_vertex_get_expr(vertex);
1304
1305         data->list->obj[data->i].type = isl_obj_set;
1306         data->list->obj[data->i].v = isl_set_from_basic_set(expr);
1307         data->i++;
1308
1309         isl_vertex_free(vertex);
1310
1311         return 0;
1312 }
1313
1314 static int set_vertices(__isl_take isl_set *set, void *user)
1315 {
1316         isl_ctx *ctx;
1317         isl_basic_set *hull;
1318         isl_vertices *vertices = NULL;
1319         struct isl_list *list = NULL;
1320         int r;
1321         struct add_vertex_data *data = (struct add_vertex_data *)user;
1322
1323         set = isl_set_remove_divs(set);
1324         hull = isl_set_convex_hull(set);
1325         vertices = isl_basic_set_compute_vertices(hull);
1326         isl_basic_set_free(hull);
1327
1328         list = data->list;
1329
1330         ctx = isl_vertices_get_ctx(vertices);
1331         data->list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
1332         if (!data->list)
1333                 goto error;
1334
1335         data->i = 0;
1336         r = isl_vertices_foreach_vertex(vertices, &add_vertex, user);
1337
1338         data->list = isl_list_concat(list, data->list);
1339
1340         isl_vertices_free(vertices);
1341
1342         return r;
1343 error:
1344         data->list = list;
1345         isl_vertices_free(vertices);
1346         return -1;
1347 }
1348
1349 static struct isl_obj vertices(struct isl_stream *s,
1350         struct isl_hash_table *table)
1351 {
1352         isl_ctx *ctx;
1353         struct isl_obj obj;
1354         struct isl_list *list = NULL;
1355         isl_union_set *uset;
1356         struct add_vertex_data data = { NULL };
1357
1358         obj = read_expr(s, table);
1359         obj = convert(s->ctx, obj, isl_obj_union_set);
1360         isl_assert(s->ctx, obj.type == isl_obj_union_set, goto error);
1361         uset = obj.v;
1362         obj.v = NULL;
1363
1364         ctx = isl_union_set_get_ctx(uset);
1365         list = isl_list_alloc(ctx, 0);
1366         if (!list)
1367                 goto error;
1368
1369         data.list = list;
1370
1371         if (isl_union_set_foreach_set(uset, &set_vertices, &data) < 0)
1372                 goto error;
1373
1374         isl_union_set_free(uset);
1375
1376         obj.type = isl_obj_list;
1377         obj.v = data.list;
1378
1379         return obj;
1380 error:
1381         isl_union_set_free(uset);
1382         isl_list_free(data.list);
1383         free_obj(obj);
1384         obj.type = isl_obj_none;
1385         obj.v = NULL;
1386         return obj;
1387 }
1388
1389 static struct isl_obj type_of(struct isl_stream *s,
1390         struct isl_hash_table *table)
1391 {
1392         isl_ctx *ctx;
1393         struct isl_obj obj;
1394         const char *type = "unknown";
1395
1396         obj = read_expr(s, table);
1397
1398         if (obj.type == isl_obj_map ||
1399             obj.type == isl_obj_union_map)
1400                 type = "map";
1401         if (obj.type == isl_obj_set ||
1402             obj.type == isl_obj_union_set)
1403                 type = "set";
1404         if (obj.type == isl_obj_pw_qpolynomial ||
1405             obj.type == isl_obj_union_pw_qpolynomial)
1406                 type = "piecewise quasipolynomial";
1407         if (obj.type == isl_obj_pw_qpolynomial_fold ||
1408             obj.type == isl_obj_union_pw_qpolynomial_fold)
1409                 type = "piecewise quasipolynomial fold";
1410         if (obj.type == isl_obj_list)
1411                 type = "list";
1412         if (obj.type == isl_obj_bool)
1413                 type = "boolean";
1414         if (obj.type == isl_obj_str)
1415                 type = "string";
1416         if (obj.type == isl_obj_int)
1417                 type = "int";
1418
1419         free_obj(obj);
1420         obj.type = isl_obj_str;
1421         obj.v = isl_str_from_string(s->ctx, strdup(type));
1422
1423         return obj;
1424 }
1425
1426 static __isl_give isl_union_map *read_map(struct isl_stream *s,
1427         struct isl_hash_table *table)
1428 {
1429         struct isl_obj obj;
1430
1431         obj = read_obj(s, table);
1432         obj = convert(s->ctx, obj, isl_obj_union_map);
1433         isl_assert(s->ctx, obj.type == isl_obj_union_map, goto error);
1434         return obj.v;
1435 error:
1436         free_obj(obj);
1437         return NULL;
1438 }
1439
1440 static struct isl_obj last_any(struct isl_stream *s,
1441         struct isl_hash_table *table, __isl_take isl_union_map *must_source,
1442         __isl_take isl_union_map *may_source)
1443 {
1444         struct isl_obj obj = { isl_obj_none, NULL };
1445         isl_union_map *sink = NULL;
1446         isl_union_map *schedule = NULL;
1447         isl_union_map *may_dep;
1448         isl_union_map *must_dep;
1449
1450         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1451                 goto error;
1452
1453         sink = read_map(s, table);
1454         if (!sink)
1455                 goto error;
1456
1457         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1458                 goto error;
1459
1460         schedule = read_map(s, table);
1461         if (!schedule)
1462                 goto error;
1463
1464         if (isl_union_map_compute_flow(sink, must_source, may_source,
1465                                        schedule, &must_dep, &may_dep,
1466                                        NULL, NULL) < 0)
1467                 return obj;
1468
1469         obj.type = isl_obj_union_map;
1470         obj.v = isl_union_map_union(must_dep, may_dep);
1471
1472         return obj;
1473 error:
1474         isl_union_map_free(may_source);
1475         isl_union_map_free(must_source);
1476         isl_union_map_free(sink);
1477         isl_union_map_free(schedule);
1478         free_obj(obj);
1479         obj.type = isl_obj_none;
1480         obj.v = NULL;
1481         return obj;
1482 }
1483
1484 static struct isl_obj any(struct isl_stream *s, struct isl_hash_table *table)
1485 {
1486         struct isl_obj obj = { isl_obj_none, NULL };
1487         isl_union_map *must_source = NULL;
1488         isl_union_map *may_source = NULL;
1489         isl_union_map *sink = NULL;
1490         isl_union_map *schedule = NULL;
1491         isl_union_map *may_dep;
1492
1493         may_source = read_map(s, table);
1494         if (!may_source)
1495                 goto error;
1496
1497         if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST])) {
1498                 must_source = read_map(s, table);
1499                 if (!must_source)
1500                         goto error;
1501                 return last_any(s, table, must_source, may_source);
1502         }
1503
1504         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1505                 goto error;
1506
1507         sink = read_map(s, table);
1508         if (!sink)
1509                 goto error;
1510
1511         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1512                 goto error;
1513
1514         schedule = read_map(s, table);
1515         if (!schedule)
1516                 goto error;
1517
1518         must_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1519         if (isl_union_map_compute_flow(sink, must_source, may_source,
1520                                        schedule, NULL, &may_dep,
1521                                        NULL, NULL) < 0)
1522                 return obj;
1523
1524         obj.type = isl_obj_union_map;
1525         obj.v = may_dep;
1526
1527         return obj;
1528 error:
1529         isl_union_map_free(may_source);
1530         isl_union_map_free(must_source);
1531         isl_union_map_free(sink);
1532         isl_union_map_free(schedule);
1533         free_obj(obj);
1534         obj.type = isl_obj_none;
1535         obj.v = NULL;
1536         return obj;
1537 }
1538
1539 static struct isl_obj last(struct isl_stream *s, struct isl_hash_table *table)
1540 {
1541         struct isl_obj obj = { isl_obj_none, NULL };
1542         struct isl_list *list = NULL;
1543         isl_union_map *must_source = NULL;
1544         isl_union_map *may_source = NULL;
1545         isl_union_map *sink = NULL;
1546         isl_union_map *schedule = NULL;
1547         isl_union_map *must_dep;
1548         isl_union_map *must_no_source;
1549
1550         must_source = read_map(s, table);
1551         if (!must_source)
1552                 goto error;
1553
1554         if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY])) {
1555                 may_source = read_map(s, table);
1556                 if (!may_source)
1557                         goto error;
1558                 return last_any(s, table, must_source, may_source);
1559         }
1560
1561         list = isl_list_alloc(s->ctx, 2);
1562         if (!list)
1563                 goto error;
1564
1565         if (isl_stream_eat(s, iscc_op[ISCC_BEFORE]))
1566                 goto error;
1567
1568         sink = read_map(s, table);
1569         if (!sink)
1570                 goto error;
1571
1572         if (isl_stream_eat(s, iscc_op[ISCC_UNDER]))
1573                 goto error;
1574
1575         schedule = read_map(s, table);
1576         if (!schedule)
1577                 goto error;
1578
1579         may_source = isl_union_map_empty(isl_union_map_get_dim(sink));
1580         if (isl_union_map_compute_flow(sink, must_source, may_source,
1581                                        schedule, &must_dep, NULL,
1582                                        &must_no_source, NULL) < 0)
1583                 return obj;
1584
1585         list->obj[0].type = isl_obj_union_map;
1586         list->obj[0].v = must_dep;
1587         list->obj[1].type = isl_obj_union_map;
1588         list->obj[1].v = must_no_source;
1589
1590         obj.v = list;
1591         obj.type = isl_obj_list;
1592
1593         return obj;
1594 error:
1595         isl_list_free(list);
1596         isl_union_map_free(may_source);
1597         isl_union_map_free(must_source);
1598         isl_union_map_free(sink);
1599         isl_union_map_free(schedule);
1600         free_obj(obj);
1601         obj.type = isl_obj_none;
1602         obj.v = NULL;
1603         return obj;
1604 }
1605
1606 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
1607 {
1608         struct isl_token *tok;
1609
1610         if (isl_stream_eat_if_available(s, '+'))
1611                 return transitive_closure(s->ctx, obj);
1612
1613         tok = isl_stream_next_token(s);
1614         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
1615                 isl_stream_error(s, tok, "expecting -1");
1616                 if (tok)
1617                         isl_stream_push_token(s, tok);
1618                 goto error;
1619         }
1620         isl_token_free(tok);
1621         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
1622         if (obj.type != isl_obj_union_map)
1623                 obj = convert(s->ctx, obj, isl_obj_union_map);
1624
1625         obj.v = isl_union_map_reverse(obj.v);
1626         if (!obj.v)
1627                 goto error;
1628
1629         return obj;
1630 error:
1631         free_obj(obj);
1632         obj.type = isl_obj_none;
1633         obj.v = NULL;
1634         return obj;
1635 }
1636
1637 static struct isl_obj read_from_file(struct isl_stream *s)
1638 {
1639         struct isl_obj obj;
1640         struct isl_token *tok;
1641         struct isl_stream *s_file;
1642         struct iscc_options *options;
1643         FILE *file;
1644
1645         tok = isl_stream_next_token(s);
1646         if (!tok || tok->type != ISL_TOKEN_STRING) {
1647                 isl_stream_error(s, tok, "expecting filename");
1648                 isl_token_free(tok);
1649                 goto error;
1650         }
1651
1652         options = isl_ctx_peek_iscc_options(s->ctx);
1653         if (!options || !options->io) {
1654                 isl_token_free(tok);
1655                 isl_die(s->ctx, isl_error_invalid,
1656                         "read operation not allowed", goto error);
1657         }
1658
1659         file = fopen(tok->u.s, "r");
1660         isl_token_free(tok);
1661         isl_assert(s->ctx, file, goto error);
1662
1663         s_file = isl_stream_new_file(s->ctx, file);
1664         if (!s_file) {
1665                 fclose(file);
1666                 goto error;
1667         }
1668
1669         obj = isl_stream_read_obj(s_file);
1670
1671         isl_stream_free(s_file);
1672         fclose(file);
1673
1674         return obj;
1675 error:
1676         obj.type = isl_obj_none;
1677         obj.v = NULL;
1678         return obj;
1679 }
1680
1681 static struct isl_obj write_to_file(struct isl_stream *s,
1682         struct isl_hash_table *table)
1683 {
1684         struct isl_obj obj;
1685         struct isl_token *tok;
1686         struct isl_stream *s_file;
1687         struct iscc_options *options;
1688         FILE *file;
1689         isl_printer *p;
1690
1691         tok = isl_stream_next_token(s);
1692         if (!tok || tok->type != ISL_TOKEN_STRING) {
1693                 isl_stream_error(s, tok, "expecting filename");
1694                 isl_token_free(tok);
1695                 goto error;
1696         }
1697
1698         obj = read_expr(s, table);
1699
1700         options = isl_ctx_peek_iscc_options(s->ctx);
1701         if (!options || !options->io) {
1702                 isl_token_free(tok);
1703                 isl_die(s->ctx, isl_error_invalid,
1704                         "write operation not allowed", goto error);
1705         }
1706
1707         file = fopen(tok->u.s, "w");
1708         isl_token_free(tok);
1709         if (!file)
1710                 isl_die(s->ctx, isl_error_unknown,
1711                         "could not open file for writing", goto error);
1712
1713         p = isl_printer_to_file(s->ctx, file);
1714         p = isl_printer_set_output_format(p, options->format);
1715         p = obj.type->print(p, obj.v);
1716         p = isl_printer_end_line(p);
1717         isl_printer_free(p);
1718
1719         fclose(file);
1720 error:
1721         free_obj(obj);
1722         obj.type = isl_obj_none;
1723         obj.v = NULL;
1724         return obj;
1725 }
1726
1727 static struct isl_obj read_string_if_available(struct isl_stream *s)
1728 {
1729         struct isl_token *tok;
1730         struct isl_obj obj = { isl_obj_none, NULL };
1731
1732         tok = isl_stream_next_token(s);
1733         if (!tok)
1734                 return obj;
1735         if (tok->type == ISL_TOKEN_STRING) {
1736                 isl_str *str;
1737                 str = isl_str_alloc(s->ctx);
1738                 if (!str)
1739                         goto error;
1740                 str->s = strdup(tok->u.s);
1741                 isl_token_free(tok);
1742                 obj.v = str;
1743                 obj.type = isl_obj_str;
1744         } else
1745                 isl_stream_push_token(s, tok);
1746         return obj;
1747 error:
1748         isl_token_free(tok);
1749         return obj;
1750 }
1751
1752 static struct isl_obj read_obj(struct isl_stream *s,
1753         struct isl_hash_table *table)
1754 {
1755         struct isl_obj obj = { isl_obj_none, NULL };
1756         char *name = NULL;
1757         struct isc_un_op *op = NULL;
1758
1759         obj = read_string_if_available(s);
1760         if (obj.v)
1761                 return obj;
1762         if (isl_stream_eat_if_available(s, '(')) {
1763                 obj = read_expr(s, table);
1764                 if (!obj.v || isl_stream_eat(s, ')'))
1765                         goto error;
1766         } else {
1767                 op = read_prefix_un_op_if_available(s);
1768                 if (op)
1769                         return read_un_op_expr(s, table, op);
1770
1771                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_READ]))
1772                         return read_from_file(s);
1773                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_WRITE]))
1774                         return write_to_file(s, table);
1775                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_VERTICES]))
1776                         return vertices(s, table);
1777                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_ANY]))
1778                         return any(s, table);
1779                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_LAST]))
1780                         return last(s, table);
1781                 if (isl_stream_eat_if_available(s, iscc_op[ISCC_TYPEOF]))
1782                         return type_of(s, table);
1783
1784                 name = isl_stream_read_ident_if_available(s);
1785                 if (name)
1786                         obj = stored_obj(s->ctx, table, name);
1787                 else
1788                         obj = isl_stream_read_obj(s);
1789                 if (!obj.v)
1790                         goto error;
1791         }
1792
1793         if (isl_stream_eat_if_available(s, '^'))
1794                 obj = power(s, obj);
1795         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
1796                 obj = obj_at_index(s, obj);
1797         else if (is_subtype(obj, isl_obj_union_map) &&
1798                  isl_stream_eat_if_available(s, '(')) {
1799                 obj = convert(s->ctx, obj, isl_obj_union_map);
1800                 obj = apply(s, obj.v, table);
1801         } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial) &&
1802                    isl_stream_eat_if_available(s, '(')) {
1803                 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial);
1804                 obj = apply_fun(s, obj, table);
1805         } else if (is_subtype(obj, isl_obj_union_pw_qpolynomial_fold) &&
1806                    isl_stream_eat_if_available(s, '(')) {
1807                 obj = convert(s->ctx, obj, isl_obj_union_pw_qpolynomial_fold);
1808                 obj = apply_fun(s, obj, table);
1809         }
1810
1811         return obj;
1812 error:
1813         free_obj(obj);
1814         obj.type = isl_obj_none;
1815         obj.v = NULL;
1816         return obj;
1817 }
1818
1819 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
1820         struct isl_obj lhs, struct isl_obj rhs)
1821 {
1822         int i;
1823
1824         for (i = 0; ; ++i) {
1825                 if (!bin_ops[i].op)
1826                         break;
1827                 if (bin_ops[i].op != like->op)
1828                         continue;
1829                 if (!is_subtype(lhs, bin_ops[i].lhs))
1830                         continue;
1831                 if (!is_subtype(rhs, bin_ops[i].rhs))
1832                         continue;
1833
1834                 return &bin_ops[i];
1835         }
1836
1837         for (i = 0; ; ++i) {
1838                 if (!named_bin_ops[i].name)
1839                         break;
1840                 if (named_bin_ops[i].op.op != like->op)
1841                         continue;
1842                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1843                         continue;
1844                 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
1845                         continue;
1846
1847                 return &named_bin_ops[i].op;
1848         }
1849
1850         return NULL;
1851 }
1852
1853 static int next_is_neg_int(struct isl_stream *s)
1854 {
1855         struct isl_token *tok;
1856         int ret;
1857
1858         tok = isl_stream_next_token(s);
1859         ret = tok && tok->type == ISL_TOKEN_VALUE && isl_int_is_neg(tok->u.v);
1860         isl_stream_push_token(s, tok);
1861
1862         return ret;
1863 }
1864
1865 static struct isl_obj read_expr(struct isl_stream *s,
1866         struct isl_hash_table *table)
1867 {
1868         struct isl_obj obj = { isl_obj_none, NULL };
1869         struct isl_obj right_obj = { isl_obj_none, NULL };
1870
1871         obj = read_obj(s, table);
1872         for (; obj.v;) {
1873                 struct isc_bin_op *op = NULL;
1874
1875                 op = read_bin_op_if_available(s, obj);
1876                 if (!op)
1877                         break;
1878
1879                 right_obj = read_obj(s, table);
1880
1881                 op = find_matching_bin_op(op, obj, right_obj);
1882
1883                 if (!op)
1884                         isl_die(s->ctx, isl_error_invalid,
1885                             "no such binary operator defined on given operands",
1886                             goto error);
1887
1888                 obj = convert(s->ctx, obj, op->lhs);
1889                 right_obj = convert(s->ctx, right_obj, op->rhs);
1890                 obj.v = op->fn(obj.v, right_obj.v);
1891                 obj.type = op->res;
1892         }
1893
1894         if (obj.type == isl_obj_int && next_is_neg_int(s)) {
1895                 right_obj = read_obj(s, table);
1896                 obj.v = isl_int_obj_add(obj.v, right_obj.v);
1897         }
1898
1899         return obj;
1900 error:
1901         free_obj(right_obj);
1902         free_obj(obj);
1903         obj.type = isl_obj_none;
1904         obj.v = NULL;
1905         return obj;
1906 }
1907
1908 static __isl_give isl_printer *source_file(struct isl_stream *s,
1909         struct isl_hash_table *table, __isl_take isl_printer *p);
1910
1911 static __isl_give isl_printer *read_line(struct isl_stream *s,
1912         struct isl_hash_table *table, __isl_take isl_printer *p)
1913 {
1914         struct isl_obj obj = { isl_obj_none, NULL };
1915         char *lhs = NULL;
1916         int assign = 0;
1917         struct isc_bin_op *op = NULL;
1918
1919         if (!p)
1920                 return NULL;
1921         if (isl_stream_is_empty(s))
1922                 return p;
1923
1924         if (isl_stream_eat_if_available(s, iscc_op[ISCC_SOURCE]))
1925                 return source_file(s, table, p);
1926
1927         assign = is_assign(s);
1928         if (assign) {
1929                 lhs = isl_stream_read_ident_if_available(s);
1930                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
1931                         goto error;
1932         }
1933
1934         obj = read_expr(s, table);
1935         if (obj.type == isl_obj_none || obj.v == NULL)
1936                 goto error;
1937         if (isl_stream_eat(s, ';'))
1938                 goto error;
1939
1940         if (assign) {
1941                 if (do_assign(s->ctx, table, lhs, obj))
1942                         return p;
1943         } else {
1944                 p = obj.type->print(p, obj.v);
1945                 p = isl_printer_end_line(p);
1946                 free_obj(obj);
1947         }
1948
1949         return p;
1950 error:
1951         isl_stream_flush_tokens(s);
1952         isl_stream_skip_line(s);
1953         free(lhs);
1954         free_obj(obj);
1955         return p;
1956 }
1957
1958 int free_cb(void **entry, void *user)
1959 {
1960         struct isl_named_obj *named = *entry;
1961
1962         free_obj(named->obj);
1963         free(named->name);
1964         free(named);
1965
1966         return 0;
1967 }
1968
1969 static void register_named_ops(struct isl_stream *s)
1970 {
1971         int i;
1972
1973         for (i = 0; i < ISCC_N_OP; ++i) {
1974                 iscc_op[i] = isl_stream_register_keyword(s, op_name[i]);
1975                 assert(iscc_op[i] != ISL_TOKEN_ERROR);
1976         }
1977
1978         for (i = 0; ; ++i) {
1979                 if (!named_un_ops[i].name)
1980                         break;
1981                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
1982                                                         named_un_ops[i].name);
1983                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
1984         }
1985
1986         for (i = 0; ; ++i) {
1987                 if (!named_bin_ops[i].name)
1988                         break;
1989                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
1990                                                         named_bin_ops[i].name);
1991                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
1992         }
1993 }
1994
1995 static __isl_give isl_printer *source_file(struct isl_stream *s,
1996         struct isl_hash_table *table, __isl_take isl_printer *p)
1997 {
1998         struct isl_token *tok;
1999         struct isl_stream *s_file;
2000         FILE *file;
2001
2002         tok = isl_stream_next_token(s);
2003         if (!tok || tok->type != ISL_TOKEN_STRING) {
2004                 isl_stream_error(s, tok, "expecting filename");
2005                 isl_token_free(tok);
2006                 return p;
2007         }
2008
2009         file = fopen(tok->u.s, "r");
2010         isl_token_free(tok);
2011         isl_assert(s->ctx, file, return p);
2012
2013         s_file = isl_stream_new_file(s->ctx, file);
2014         if (!s_file) {
2015                 fclose(file);
2016                 return p;
2017         }
2018
2019         register_named_ops(s_file);
2020
2021         while (!s_file->eof)
2022                 p = read_line(s_file, table, p);
2023
2024         isl_stream_free(s_file);
2025         fclose(file);
2026
2027         isl_stream_eat(s, ';');
2028
2029         return p;
2030 }
2031
2032 int main(int argc, char **argv)
2033 {
2034         struct isl_ctx *ctx;
2035         struct isl_stream *s;
2036         struct isl_hash_table *table;
2037         struct iscc_options *options;
2038         isl_printer *p;
2039
2040         options = iscc_options_new_with_defaults();
2041         assert(options);
2042         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
2043
2044         ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
2045         s = isl_stream_new_file(ctx, stdin);
2046         assert(s);
2047         table = isl_hash_table_alloc(ctx, 10);
2048         assert(table);
2049         p = isl_printer_to_file(ctx, stdout);
2050         p = isl_printer_set_output_format(p, options->format);
2051         assert(p);
2052
2053         register_named_ops(s);
2054
2055         while (p && !s->eof) {
2056                 p = read_line(s, table, p);
2057         }
2058
2059         isl_printer_free(p);
2060         isl_hash_table_foreach(ctx, table, free_cb, NULL);
2061         isl_hash_table_free(ctx, table);
2062         isl_stream_free(s);
2063         isl_ctx_free(ctx);
2064
2065         return 0;
2066 }