iscc.c

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