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