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