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 <barvinok/barvinok.h>
   9
  10 #include "config.h"
  11
  12 #ifdef HAVE_CLOOG
  13 #include <cloog/isl/cloog.h>
  14 #endif
  15
  16 static int isl_bool_false = 0;
  17 static int isl_bool_true = 1;
  18 static int isl_bool_error = -1;
  19
  20 static enum isl_token_type read_op;
  21 static enum isl_token_type vertices_op;
  22
  23 struct isl_arg_choice iscc_format[] = {
  24         {"isl",         ISL_FORMAT_ISL},
  25         {"omega",       ISL_FORMAT_OMEGA},
  26         {"polylib",     ISL_FORMAT_POLYLIB},
  27         {"latex",       ISL_FORMAT_LATEX},
  28         {"C",           ISL_FORMAT_C},
  29         {0}
  30 };
  31
  32 struct iscc_options {
  33         struct barvinok_options *barvinok;
  34         unsigned                 format;
  35 };
  36
  37 struct isl_arg iscc_options_arg[] = {
  38 ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", barvinok_options_arg,
  39         "barvinok options")
  40 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
  41         iscc_format,    ISL_FORMAT_ISL, "output format")
  42 ISL_ARG_END
  43 };
  44
  45 ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_arg)
  46
  47 static void *isl_obj_bool_copy(void *v)
  48 {
  49         return v;
  50 }
  51
  52 static void isl_obj_bool_free(void *v)
  53 {
  54 }
  55
  56 static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
  57         void *v)
  58 {
  59         if (v == &isl_bool_true)
  60                 return isl_printer_print_str(p, "True");
  61         else if (v == &isl_bool_false)
  62                 return isl_printer_print_str(p, "False");
  63         else
  64                 return isl_printer_print_str(p, "Error");
  65 }
  66
  67 static void *isl_obj_bool_add(void *v1, void *v2)
  68 {
  69         return v1;
  70 }
  71
  72 struct isl_obj_vtable isl_obj_bool_vtable = {
  73         isl_obj_bool_copy,
  74         isl_obj_bool_add,
  75         isl_obj_bool_print,
  76         isl_obj_bool_free
  77 };
  78 #define isl_obj_bool            (&isl_obj_bool_vtable)
  79
  80 int *isl_bool_from_int(int res)
  81 {
  82         return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
  83 }
  84
  85 int *union_map_is_equal(__isl_take isl_union_map *map1,
  86         __isl_take isl_union_map *map2)
  87 {
  88         int res = isl_union_map_is_equal(map1, map2);
  89         isl_union_map_free(map1);
  90         isl_union_map_free(map2);
  91         return isl_bool_from_int(res);
  92 }
  93 int *union_set_is_equal(__isl_take isl_union_set *set1,
  94         __isl_take isl_union_set *set2)
  95 {
  96         return union_map_is_equal((isl_union_map *)set1, (isl_union_map *)set2);
  97 }
  98
  99 int *union_map_is_subset(__isl_take isl_union_map *map1,
 100         __isl_take isl_union_map *map2)
 101 {
 102         int res = isl_union_map_is_subset(map1, map2);
 103         isl_union_map_free(map1);
 104         isl_union_map_free(map2);
 105         return isl_bool_from_int(res);
 106 }
 107 int *union_set_is_subset(__isl_take isl_union_set *set1,
 108         __isl_take isl_union_set *set2)
 109 {
 110         return union_map_is_subset((isl_union_map *)set1, (isl_union_map *)set2);
 111 }
 112
 113 int *union_map_is_strict_subset(__isl_take isl_union_map *map1,
 114         __isl_take isl_union_map *map2)
 115 {
 116         int res = isl_union_map_is_strict_subset(map1, map2);
 117         isl_union_map_free(map1);
 118         isl_union_map_free(map2);
 119         return isl_bool_from_int(res);
 120 }
 121 int *union_set_is_strict_subset(__isl_take isl_union_set *set1,
 122         __isl_take isl_union_set *set2)
 123 {
 124         return union_map_is_strict_subset((isl_union_map *)set1,
 125                                           (isl_union_map *)set2);
 126 }
 127
 128 int *union_map_is_superset(__isl_take isl_union_map *map1,
 129         __isl_take isl_union_map *map2)
 130 {
 131         return union_map_is_subset(map2, map1);
 132 }
 133 int *union_set_is_superset(__isl_take isl_union_set *set1,
 134         __isl_take isl_union_set *set2)
 135 {
 136         return union_set_is_subset(set2, set1);
 137 }
 138
 139 int *union_map_is_strict_superset(__isl_take isl_union_map *map1,
 140         __isl_take isl_union_map *map2)
 141 {
 142         return union_map_is_strict_subset(map2, map1);
 143 }
 144 int *union_set_is_strict_superset(__isl_take isl_union_set *set1,
 145         __isl_take isl_union_set *set2)
 146 {
 147         return union_set_is_strict_subset(set2, set1);
 148 }
 149
 150 extern struct isl_obj_vtable isl_obj_list_vtable;
 151 #define isl_obj_list            (&isl_obj_list_vtable)
 152
 153 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
 154 struct isc_bin_op {
 155         enum isl_token_type     op;
 156         isl_obj_type            lhs;
 157         isl_obj_type            rhs;
 158         isl_obj_type            res;
 159         isc_bin_op_fn           fn;
 160 };
 161 struct isc_named_bin_op {
 162         char                    *name;
 163         struct isc_bin_op       op;
 164 };
 165
 166 struct iscc_at {
 167         isl_union_pw_qpolynomial *upwqp;
 168         isl_union_pw_qpolynomial *res;
 169 };
 170
 171 static int eval_at(__isl_take isl_point *pnt, void *user)
 172 {
 173         struct iscc_at *at = (struct iscc_at *) user;
 174         isl_qpolynomial *qp;
 175         isl_set *set;
 176
 177         set = isl_set_from_point(isl_point_copy(pnt));
 178         qp = isl_union_pw_qpolynomial_eval(
 179                                 isl_union_pw_qpolynomial_copy(at->upwqp), pnt);
 180
 181         at->res = isl_union_pw_qpolynomial_add(at->res,
 182                         isl_union_pw_qpolynomial_from_pw_qpolynomial(
 183                                 isl_pw_qpolynomial_alloc(set, qp)));
 184
 185         return 0;
 186 }
 187
 188 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_at(
 189         __isl_take isl_union_pw_qpolynomial *upwqp,
 190         __isl_take isl_union_set *uset)
 191 {
 192         struct iscc_at at;
 193
 194         at.upwqp = upwqp;
 195         at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
 196
 197         isl_union_set_foreach_point(uset, eval_at, &at);
 198
 199         isl_union_pw_qpolynomial_free(upwqp);
 200         isl_union_set_free(uset);
 201
 202         return at.res;
 203 }
 204
 205 struct iscc_fold_at {
 206         isl_union_pw_qpolynomial_fold *upwf;
 207         isl_union_pw_qpolynomial *res;
 208 };
 209
 210 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
 211 {
 212         struct iscc_fold_at *at = (struct iscc_fold_at *) user;
 213         isl_qpolynomial *qp;
 214         isl_set *set;
 215
 216         set = isl_set_from_point(isl_point_copy(pnt));
 217         qp = isl_union_pw_qpolynomial_fold_eval(
 218                             isl_union_pw_qpolynomial_fold_copy(at->upwf), pnt);
 219
 220         at->res = isl_union_pw_qpolynomial_add(at->res,
 221                         isl_union_pw_qpolynomial_from_pw_qpolynomial(
 222                                 isl_pw_qpolynomial_alloc(set, qp)));
 223
 224         return 0;
 225 }
 226
 227 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_fold_at(
 228         __isl_take isl_union_pw_qpolynomial_fold *upwf,
 229         __isl_take isl_union_set *uset)
 230 {
 231         struct iscc_fold_at at;
 232
 233         at.upwf = upwf;
 234         at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
 235
 236         isl_union_set_foreach_point(uset, eval_fold_at, &at);
 237
 238         isl_union_pw_qpolynomial_fold_free(upwf);
 239         isl_union_set_free(uset);
 240
 241         return at.res;
 242 }
 243
 244 struct isc_bin_op bin_ops[] = {
 245         { '+',  isl_obj_union_set,      isl_obj_union_set,
 246                 isl_obj_union_set,
 247                 (isc_bin_op_fn) &isl_union_set_union },
 248         { '+',  isl_obj_union_map,      isl_obj_union_map,
 249                 isl_obj_union_map,
 250                 (isc_bin_op_fn) &isl_union_map_union },
 251         { '-',  isl_obj_union_set,      isl_obj_union_set,
 252                 isl_obj_union_set,
 253                 (isc_bin_op_fn) &isl_union_set_subtract },
 254         { '-',  isl_obj_union_map,      isl_obj_union_map,
 255                 isl_obj_union_map,
 256                 (isc_bin_op_fn) &isl_union_map_subtract },
 257         { '*',  isl_obj_union_set,      isl_obj_union_set,
 258                 isl_obj_union_set,
 259                 (isc_bin_op_fn) &isl_union_set_intersect },
 260         { '*',  isl_obj_union_map,      isl_obj_union_map,
 261                 isl_obj_union_map,
 262                 (isc_bin_op_fn) &isl_union_map_intersect },
 263         { '*',  isl_obj_union_map,      isl_obj_union_set,
 264                 isl_obj_union_map,
 265                 (isc_bin_op_fn) &isl_union_map_intersect_domain },
 266         { '.',  isl_obj_union_map,      isl_obj_union_map,
 267                 isl_obj_union_map,
 268                 (isc_bin_op_fn) &isl_union_map_apply_range },
 269         { '.',  isl_obj_union_map,      isl_obj_union_pw_qpolynomial,
 270                 isl_obj_union_pw_qpolynomial,
 271                 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial },
 272         { ISL_TOKEN_TO, isl_obj_union_set,      isl_obj_union_set,
 273                 isl_obj_union_map,
 274                 (isc_bin_op_fn) &isl_union_map_from_domain_and_range },
 275         { '=', isl_obj_union_set,       isl_obj_union_set,      isl_obj_bool,
 276                 (isc_bin_op_fn) &union_set_is_equal },
 277         { '=', isl_obj_union_map,       isl_obj_union_map,      isl_obj_bool,
 278                 (isc_bin_op_fn) &union_map_is_equal },
 279         { ISL_TOKEN_LE, isl_obj_union_set,      isl_obj_union_set,
 280                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_subset },
 281         { ISL_TOKEN_LE, isl_obj_union_map,      isl_obj_union_map,
 282                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_subset },
 283         { ISL_TOKEN_LT, isl_obj_union_set,      isl_obj_union_set,
 284                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_subset },
 285         { ISL_TOKEN_LT, isl_obj_union_map,      isl_obj_union_map,
 286                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_subset },
 287         { ISL_TOKEN_GE, isl_obj_union_set,      isl_obj_union_set,
 288                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_superset },
 289         { ISL_TOKEN_GE, isl_obj_union_map,      isl_obj_union_map,
 290                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_superset },
 291         { ISL_TOKEN_GT, isl_obj_union_set,      isl_obj_union_set,
 292                 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_superset },
 293         { ISL_TOKEN_GT, isl_obj_union_map,      isl_obj_union_map,
 294                 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_superset },
 295         { '+',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
 296                 isl_obj_union_pw_qpolynomial,
 297                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_add },
 298         { '-',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
 299                 isl_obj_union_pw_qpolynomial,
 300                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_sub },
 301         { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
 302                 isl_obj_union_pw_qpolynomial,
 303                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_mul },
 304         { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 305                 isl_obj_union_pw_qpolynomial,
 306                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_intersect_domain },
 307         { '*',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_union_set,
 308                 isl_obj_union_pw_qpolynomial_fold,
 309                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_intersect_domain },
 310         { '@',  isl_obj_union_pw_qpolynomial, isl_obj_union_set,
 311                 isl_obj_union_pw_qpolynomial,
 312                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_at },
 313         { '@',  isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
 314                 isl_obj_union_pw_qpolynomial,
 315                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_at },
 316         { '%',  isl_obj_union_set,      isl_obj_union_set,
 317                 isl_obj_union_set,
 318                 (isc_bin_op_fn) &isl_union_set_gist },
 319         { '%',  isl_obj_union_map,      isl_obj_union_map,
 320                 isl_obj_union_map,
 321                 (isc_bin_op_fn) &isl_union_map_gist },
 322         { '%',  isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 323                 isl_obj_union_pw_qpolynomial,
 324                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_gist },
 325         { '%',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_union_set,
 326                 isl_obj_union_pw_qpolynomial_fold,
 327                 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_gist },
 328         0
 329 };
 330 struct isc_named_bin_op named_bin_ops[] = {
 331         { "cross",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 332                 isl_obj_union_set,
 333                 (isc_bin_op_fn) &isl_union_set_product } },
 334         { "cross",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 335                 isl_obj_union_map,
 336                 (isc_bin_op_fn) &isl_union_map_product } },
 337         NULL
 338 };
 339
 340 __isl_give isl_set *union_set_sample(__isl_take isl_union_set *uset)
 341 {
 342         return isl_set_from_basic_set(isl_union_set_sample(uset));
 343 }
 344
 345 __isl_give isl_map *union_map_sample(__isl_take isl_union_map *umap)
 346 {
 347         return isl_map_from_basic_map(isl_union_map_sample(umap));
 348 }
 349
 350 static __isl_give struct isl_list *union_pw_qpolynomial_upper_bound(
 351         __isl_take isl_union_pw_qpolynomial *upwqp)
 352 {
 353         isl_ctx *ctx;
 354         struct isl_list *list;
 355         int tight;
 356
 357         ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
 358         list = isl_list_alloc(ctx, 2);
 359         if (!list)
 360                 goto error2;
 361
 362         list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
 363         list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
 364                                                         isl_fold_max, &tight);
 365         list->obj[1].type = isl_obj_bool;
 366         list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
 367         if (tight < 0 || !list->obj[0].v)
 368                 goto error;
 369
 370         return list;
 371 error2:
 372         isl_union_pw_qpolynomial_free(upwqp);
 373 error:
 374         isl_list_free(list);
 375         return NULL;
 376 }
 377
 378 #ifdef HAVE_CLOOG
 379 void *codegen(void *arg)
 380 {
 381         isl_dim *dim;
 382         isl_union_map *umap = (isl_union_map *)arg;
 383         isl_ctx *ctx = isl_union_map_get_ctx(umap);
 384         CloogState *state;
 385         CloogOptions *options;
 386         CloogDomain *context;
 387         CloogUnionDomain *ud;
 388         CloogInput *input;
 389         struct clast_stmt *stmt;
 390
 391         state = cloog_isl_state_malloc(ctx);
 392         options = cloog_options_malloc(state);
 393         options->language = LANGUAGE_C;
 394
 395         ud = cloog_union_domain_from_isl_union_map(isl_union_map_copy(umap));
 396
 397         dim = isl_union_map_get_dim(umap);
 398         context = cloog_domain_from_isl_set(isl_set_universe(dim));
 399
 400         input = cloog_input_alloc(context, ud);
 401
 402         stmt = cloog_clast_create_from_input(input, options);
 403         clast_pprint(stdout, stmt, 0, options);
 404         cloog_clast_free(stmt);
 405
 406 error:
 407         cloog_options_free(options);
 408         cloog_state_free(state);
 409         isl_union_map_free(umap);
 410         return NULL;
 411 }
 412 #endif
 413
 414 typedef void *(*isc_un_op_fn)(void *arg);
 415 struct isc_un_op {
 416         enum isl_token_type     op;
 417         isl_obj_type            arg;
 418         isl_obj_type            res;
 419         isc_un_op_fn            fn;
 420 };
 421 struct isc_named_un_op {
 422         char                    *name;
 423         struct isc_un_op        op;
 424 };
 425 struct isc_named_un_op named_un_ops[] = {
 426         {"aff", { -1,   isl_obj_union_map,      isl_obj_union_map,
 427                 (isc_un_op_fn) &isl_union_map_affine_hull } },
 428         {"aff", { -1,   isl_obj_union_set,      isl_obj_union_set,
 429                 (isc_un_op_fn) &isl_union_set_affine_hull } },
 430         {"card",        { -1,   isl_obj_union_set,
 431                 isl_obj_union_pw_qpolynomial,
 432                 (isc_un_op_fn) &isl_union_set_card } },
 433         {"card",        { -1,   isl_obj_union_map,
 434                 isl_obj_union_pw_qpolynomial,
 435                 (isc_un_op_fn) &isl_union_map_card } },
 436         {"coalesce",    { -1,   isl_obj_union_set,      isl_obj_union_set,
 437                 (isc_un_op_fn) &isl_union_set_coalesce } },
 438         {"coalesce",    { -1,   isl_obj_union_map,      isl_obj_union_map,
 439                 (isc_un_op_fn) &isl_union_map_coalesce } },
 440         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial,
 441                 isl_obj_union_pw_qpolynomial,
 442                 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
 443         {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial_fold,
 444                 isl_obj_union_pw_qpolynomial_fold,
 445                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
 446 #ifdef HAVE_CLOOG
 447         {"codegen",     { -1,   isl_obj_union_map, isl_obj_none, &codegen } },
 448 #endif
 449         {"deltas",      { -1,   isl_obj_union_map,      isl_obj_union_set,
 450                 (isc_un_op_fn) &isl_union_map_deltas } },
 451         {"dom", { -1,   isl_obj_union_map,      isl_obj_union_set,
 452                 (isc_un_op_fn) &isl_union_map_domain } },
 453         {"dom", { -1,   isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
 454                 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
 455         {"dom", { -1,   isl_obj_union_pw_qpolynomial_fold,
 456                 isl_obj_union_set,
 457                 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
 458         {"ran", { -1,   isl_obj_union_map,      isl_obj_union_set,
 459                 (isc_un_op_fn) &isl_union_map_range } },
 460         {"lexmin",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 461                 (isc_un_op_fn) &isl_union_map_lexmin } },
 462         {"lexmax",      { -1,   isl_obj_union_map,      isl_obj_union_map,
 463                 (isc_un_op_fn) &isl_union_map_lexmax } },
 464         {"lexmin",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 465                 (isc_un_op_fn) &isl_union_set_lexmin } },
 466         {"lexmax",      { -1,   isl_obj_union_set,      isl_obj_union_set,
 467                 (isc_un_op_fn) &isl_union_set_lexmax } },
 468         {"sample",      { -1,   isl_obj_union_set,      isl_obj_set,
 469                 (isc_un_op_fn) &union_set_sample } },
 470         {"sample",      { -1,   isl_obj_union_map,      isl_obj_map,
 471                 (isc_un_op_fn) &union_map_sample } },
 472         {"sum",         { -1,   isl_obj_union_pw_qpolynomial,
 473                 isl_obj_union_pw_qpolynomial,
 474                 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
 475         {"ub",          { -1,   isl_obj_union_pw_qpolynomial, isl_obj_list,
 476                 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
 477         {"unwrap",      { -1,   isl_obj_union_set,      isl_obj_union_map,
 478                 (isc_un_op_fn) &isl_union_set_unwrap } },
 479         {"wrap",        { -1,   isl_obj_union_map,      isl_obj_union_set,
 480                 (isc_un_op_fn) &isl_union_map_wrap } },
 481         NULL
 482 };
 483
 484 struct isl_named_obj {
 485         char            *name;
 486         struct isl_obj  obj;
 487 };
 488
 489 static void free_obj(struct isl_obj obj)
 490 {
 491         obj.type->free(obj.v);
 492 }
 493
 494 static int same_name(const void *entry, const void *val)
 495 {
 496         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 497
 498         return !strcmp(named->name, val);
 499 }
 500
 501 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 502         char *name, struct isl_obj obj)
 503 {
 504         struct isl_hash_table_entry *entry;
 505         uint32_t name_hash;
 506         struct isl_named_obj *named;
 507
 508         name_hash = isl_hash_string(isl_hash_init(), name);
 509         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 510         if (!entry)
 511                 goto error;
 512         if (entry->data) {
 513                 named = entry->data;
 514                 free_obj(named->obj);
 515                 free(name);
 516         } else {
 517                 named = isl_alloc_type(ctx, struct isl_named_obj);
 518                 if (!named)
 519                         goto error;
 520                 named->name = name;
 521                 entry->data = named;
 522         }
 523         named->obj = obj;
 524
 525         return 0;
 526 error:
 527         free_obj(obj);
 528         free(name);
 529         return -1;
 530 }
 531
 532 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 533         struct isl_hash_table *table, char *name)
 534 {
 535         struct isl_obj obj = { isl_obj_none, NULL };
 536         struct isl_hash_table_entry *entry;
 537         uint32_t name_hash;
 538
 539         name_hash = isl_hash_string(isl_hash_init(), name);
 540         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 541         if (entry) {
 542                 struct isl_named_obj *named;
 543                 named = entry->data;
 544                 obj = named->obj;
 545         }
 546
 547         free(name);
 548         obj.v = obj.type->copy(obj.v);
 549         return obj;
 550 }
 551
 552 static int is_subtype(struct isl_obj obj, isl_obj_type super)
 553 {
 554         if (obj.type == super)
 555                 return 1;
 556         if (obj.type == isl_obj_map && super == isl_obj_union_map)
 557                 return 1;
 558         if (obj.type == isl_obj_set && super == isl_obj_union_set)
 559                 return 1;
 560         if (obj.type == isl_obj_pw_qpolynomial &&
 561             super == isl_obj_union_pw_qpolynomial)
 562                 return 1;
 563         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 564             super == isl_obj_union_pw_qpolynomial_fold)
 565                 return 1;
 566         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
 567                 return 1;
 568         return 0;
 569 }
 570
 571 static struct isl_obj convert(struct isl_obj obj, isl_obj_type type)
 572 {
 573         if (obj.type == type)
 574                 return obj;
 575         if (obj.type == isl_obj_map && type == isl_obj_union_map) {
 576                 obj.type = isl_obj_union_map;
 577                 obj.v = isl_union_map_from_map(obj.v);
 578                 return obj;
 579         }
 580         if (obj.type == isl_obj_set && type == isl_obj_union_set) {
 581                 obj.type = isl_obj_union_set;
 582                 obj.v = isl_union_set_from_set(obj.v);
 583                 return obj;
 584         }
 585         if (obj.type == isl_obj_pw_qpolynomial &&
 586             type == isl_obj_union_pw_qpolynomial) {
 587                 obj.type = isl_obj_union_pw_qpolynomial;
 588                 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
 589                 return obj;
 590         }
 591         if (obj.type == isl_obj_pw_qpolynomial_fold &&
 592             type == isl_obj_union_pw_qpolynomial_fold) {
 593                 obj.type = isl_obj_union_pw_qpolynomial_fold;
 594                 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
 595                 return obj;
 596         }
 597         if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
 598                 if (type == isl_obj_union_map) {
 599                         obj.type = isl_obj_union_map;
 600                         return obj;
 601                 }
 602                 if (type == isl_obj_union_pw_qpolynomial) {
 603                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 604                         isl_union_set_free(obj.v);
 605                         obj.v = isl_union_pw_qpolynomial_zero(dim);
 606                         obj.type = isl_obj_union_pw_qpolynomial;
 607                         return obj;
 608                 }
 609                 if (type == isl_obj_union_pw_qpolynomial_fold) {
 610                         isl_dim *dim = isl_union_set_get_dim(obj.v);
 611                         isl_union_set_free(obj.v);
 612                         obj.v = isl_union_pw_qpolynomial_fold_zero(dim);
 613                         obj.type = isl_obj_union_pw_qpolynomial_fold;
 614                         return obj;
 615                 }
 616         }
 617         free_obj(obj);
 618         obj.type = isl_obj_none;
 619         obj.v = NULL;
 620         return obj;
 621 }
 622
 623 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 624         struct isl_obj lhs)
 625 {
 626         int i;
 627         struct isl_token *tok;
 628
 629         tok = isl_stream_next_token(s);
 630         if (!tok)
 631                 return NULL;
 632
 633         for (i = 0; ; ++i) {
 634                 if (!bin_ops[i].op)
 635                         break;
 636                 if (bin_ops[i].op != tok->type)
 637                         continue;
 638                 if (!is_subtype(lhs, bin_ops[i].lhs))
 639                         continue;
 640
 641                 isl_token_free(tok);
 642                 return &bin_ops[i];
 643         }
 644
 645         for (i = 0; ; ++i) {
 646                 if (!named_bin_ops[i].name)
 647                         break;
 648                 if (named_bin_ops[i].op.op != tok->type)
 649                         continue;
 650                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
 651                         continue;
 652
 653                 isl_token_free(tok);
 654                 return &named_bin_ops[i].op;
 655         }
 656
 657         isl_stream_push_token(s, tok);
 658
 659         return NULL;
 660 }
 661
 662 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 663 {
 664         int i;
 665         struct isl_token *tok;
 666
 667         tok = isl_stream_next_token(s);
 668         if (!tok)
 669                 return NULL;
 670
 671         for (i = 0; ; ++i) {
 672                 if (!named_un_ops[i].name)
 673                         break;
 674                 if (named_un_ops[i].op.op != tok->type)
 675                         continue;
 676
 677                 isl_token_free(tok);
 678                 return &named_un_ops[i].op;
 679         }
 680
 681         isl_stream_push_token(s, tok);
 682
 683         return NULL;
 684 }
 685
 686 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 687         struct isl_obj arg)
 688 {
 689         int i;
 690
 691         for (i = 0; ; ++i) {
 692                 if (!named_un_ops[i].name)
 693                         break;
 694                 if (named_un_ops[i].op.op != like->op)
 695                         continue;
 696                 if (!is_subtype(arg, named_un_ops[i].op.arg))
 697                         continue;
 698
 699                 return &named_un_ops[i].op;
 700         }
 701
 702         return NULL;
 703 }
 704
 705 static int is_assign(struct isl_stream *s)
 706 {
 707         struct isl_token *tok;
 708         struct isl_token *tok2;
 709         int assign;
 710
 711         tok = isl_stream_next_token(s);
 712         if (!tok)
 713                 return 0;
 714         if (tok->type != ISL_TOKEN_IDENT) {
 715                 isl_stream_push_token(s, tok);
 716                 return 0;
 717         }
 718
 719         tok2 = isl_stream_next_token(s);
 720         if (!tok2) {
 721                 isl_stream_push_token(s, tok);
 722                 return 0;
 723         }
 724         assign = tok2->type == ISL_TOKEN_DEF;
 725         isl_stream_push_token(s, tok2);
 726         isl_stream_push_token(s, tok);
 727
 728         return assign;
 729 }
 730
 731 static struct isl_obj read_obj(struct isl_stream *s,
 732         struct isl_hash_table *table);
 733 static struct isl_obj read_expr(struct isl_stream *s,
 734         struct isl_hash_table *table);
 735
 736 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 737         struct isl_hash_table *table, struct isc_un_op *op)
 738 {
 739         struct isl_obj obj = { isl_obj_none, NULL };
 740
 741         obj = read_obj(s, table);
 742         if (!obj.v)
 743                 goto error;
 744
 745         op = find_matching_un_op(op, obj);
 746
 747         isl_assert(s->ctx, op, goto error);
 748         obj = convert(obj, op->arg);
 749         obj.v = op->fn(obj.v);
 750         obj.type = op->res;
 751
 752         return obj;
 753 error:
 754         free_obj(obj);
 755         obj.type = isl_obj_none;
 756         obj.v = NULL;
 757         return obj;
 758 }
 759
 760 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 761 {
 762         struct isl_list *list;
 763         int exact;
 764
 765         if (obj.type == isl_obj_map)
 766                 obj = convert(obj, isl_obj_union_map);
 767         isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
 768         list = isl_list_alloc(ctx, 2);
 769         if (!list)
 770                 goto error;
 771
 772         list->obj[0].type = isl_obj_union_map;
 773         list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
 774         list->obj[1].type = isl_obj_bool;
 775         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 776         obj.v = list;
 777         obj.type = isl_obj_list;
 778         if (exact < 0 || !list->obj[0].v)
 779                 goto error;
 780
 781         return obj;
 782 error:
 783         free_obj(obj);
 784         obj.type = isl_obj_none;
 785         obj.v = NULL;
 786         return obj;
 787 }
 788
 789 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 790 {
 791         struct isl_list *list = obj.v;
 792         struct isl_token *tok;
 793         int i;
 794
 795         tok = isl_stream_next_token(s);
 796         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 797                 isl_stream_error(s, tok, "expecting index");
 798                 if (tok)
 799                         isl_stream_push_token(s, tok);
 800                 goto error;
 801         }
 802         i = isl_int_get_si(tok->u.v);
 803         isl_token_free(tok);
 804         isl_assert(s->ctx, i < list->n, goto error);
 805         if (isl_stream_eat(s, ']'))
 806                 goto error;
 807
 808         obj = list->obj[i];
 809         obj.v = obj.type->copy(obj.v);
 810
 811         isl_list_free(list);
 812
 813         return obj;
 814 error:
 815         free_obj(obj);
 816         obj.type = isl_obj_none;
 817         obj.v = NULL;
 818         return obj;
 819 }
 820
 821 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
 822         struct isl_hash_table *table)
 823 {
 824         struct isl_obj obj;
 825
 826         obj = read_expr(s, table);
 827         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
 828                            is_subtype(obj, isl_obj_union_map), goto error);
 829
 830         if (obj.type == isl_obj_set)
 831                 obj = convert(obj, isl_obj_union_set);
 832         else if (obj.type == isl_obj_map)
 833                 obj = convert(obj, isl_obj_union_map);
 834         if (obj.type == isl_obj_union_set) {
 835                 obj.v = isl_union_set_apply(obj.v, umap);
 836         } else
 837                 obj.v = isl_union_map_apply_range(obj.v, umap);
 838         if (!obj.v)
 839                 goto error2;
 840
 841         if (isl_stream_eat(s, ')'))
 842                 goto error2;
 843
 844         return obj;
 845 error:
 846         isl_union_map_free(umap);
 847 error2:
 848         free_obj(obj);
 849         obj.type = isl_obj_none;
 850         obj.v = NULL;
 851         return obj;
 852 }
 853
 854 struct add_vertex_data {
 855         struct isl_list *list;
 856         int i;
 857 };
 858
 859 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
 860 {
 861         struct add_vertex_data *data = (struct add_vertex_data *)user;
 862         isl_basic_set *expr;
 863
 864         expr = isl_vertex_get_expr(vertex);
 865
 866         data->list->obj[data->i].type = isl_obj_set;
 867         data->list->obj[data->i].v = isl_set_from_basic_set(expr);
 868         data->i++;
 869
 870         isl_vertex_free(vertex);
 871
 872         return 0;
 873 }
 874
 875 static struct isl_obj vertices(struct isl_stream *s,
 876         struct isl_hash_table *table)
 877 {
 878         isl_ctx *ctx;
 879         struct isl_obj obj;
 880         isl_set *set;
 881         isl_basic_set *hull;
 882         isl_vertices *vertices = NULL;
 883         struct isl_list *list = NULL;
 884         struct add_vertex_data data;
 885
 886         obj = read_expr(s, table);
 887         isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
 888         set = obj.v;
 889         obj.v = NULL;
 890         set = isl_set_remove_divs(set);
 891         hull = isl_set_convex_hull(set);
 892         vertices = isl_basic_set_compute_vertices(hull);
 893         isl_basic_set_free(hull);
 894
 895         ctx = isl_vertices_get_ctx(vertices);
 896         list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
 897         if (!list)
 898                 goto error;
 899
 900         data.list = list;
 901         data.i = 0;
 902
 903         if (isl_vertices_foreach_vertex(vertices, &add_vertex, &data) < 0)
 904                 goto error;
 905
 906         isl_vertices_free(vertices);
 907
 908         obj.type = isl_obj_list;
 909         obj.v = list;
 910
 911         return obj;
 912 error:
 913         isl_vertices_free(vertices);
 914         isl_list_free(list);
 915         free_obj(obj);
 916         obj.type = isl_obj_none;
 917         obj.v = NULL;
 918         return obj;
 919 }
 920
 921 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
 922 {
 923         struct isl_token *tok;
 924
 925         if (isl_stream_eat_if_available(s, '+'))
 926                 return transitive_closure(s->ctx, obj);
 927
 928         tok = isl_stream_next_token(s);
 929         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
 930                 isl_stream_error(s, tok, "expecting -1");
 931                 if (tok)
 932                         isl_stream_push_token(s, tok);
 933                 goto error;
 934         }
 935         isl_token_free(tok);
 936         isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
 937         if (obj.type != isl_obj_union_map)
 938                 obj = convert(obj, isl_obj_union_map);
 939
 940         obj.v = isl_union_map_reverse(obj.v);
 941         if (!obj.v)
 942                 goto error;
 943
 944         return obj;
 945 error:
 946         free_obj(obj);
 947         obj.type = isl_obj_none;
 948         obj.v = NULL;
 949         return obj;
 950 }
 951
 952 static struct isl_obj read_from_file(struct isl_stream *s)
 953 {
 954         struct isl_obj obj;
 955         struct isl_token *tok;
 956         struct isl_stream *s_file;
 957         FILE *file;
 958
 959         tok = isl_stream_next_token(s);
 960         if (!tok || tok->type != ISL_TOKEN_STRING) {
 961                 isl_stream_error(s, tok, "expecting filename");
 962                 isl_token_free(tok);
 963                 goto error;
 964         }
 965
 966         file = fopen(tok->u.s, "r");
 967         isl_token_free(tok);
 968         isl_assert(s->ctx, file, goto error);
 969
 970         s_file = isl_stream_new_file(s->ctx, file);
 971         if (!s_file) {
 972                 fclose(file);
 973                 goto error;
 974         }
 975
 976         obj = isl_stream_read_obj(s_file);
 977
 978         isl_stream_free(s_file);
 979         fclose(file);
 980
 981         return obj;
 982 error:
 983         obj.type = isl_obj_none;
 984         obj.v = NULL;
 985         return obj;
 986 }
 987
 988 static struct isl_obj read_obj(struct isl_stream *s,
 989         struct isl_hash_table *table)
 990 {
 991         struct isl_obj obj = { isl_obj_none, NULL };
 992         char *name = NULL;
 993         struct isc_un_op *op = NULL;
 994
 995         if (isl_stream_eat_if_available(s, '(')) {
 996                 obj = read_expr(s, table);
 997                 if (!obj.v || isl_stream_eat(s, ')'))
 998                         goto error;
 999         } else {
1000                 op = read_prefix_un_op_if_available(s);
1001                 if (op)
1002                         return read_un_op_expr(s, table, op);
1003
1004                 if (isl_stream_eat_if_available(s, read_op))
1005                         return read_from_file(s);
1006                 if (isl_stream_eat_if_available(s, vertices_op))
1007                         return vertices(s, table);
1008
1009                 name = isl_stream_read_ident_if_available(s);
1010                 if (name)
1011                         obj = stored_obj(s->ctx, table, name);
1012                 else
1013                         obj = isl_stream_read_obj(s);
1014                 if (!obj.v)
1015                         goto error;
1016         }
1017
1018         if (isl_stream_eat_if_available(s, '^'))
1019                 obj = power(s, obj);
1020         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
1021                 obj = obj_at_index(s, obj);
1022         else if (is_subtype(obj, isl_obj_union_map) &&
1023                  isl_stream_eat_if_available(s, '(')) {
1024                 obj = convert(obj, isl_obj_union_map);
1025                 obj = apply(s, obj.v, table);
1026         }
1027
1028         return obj;
1029 error:
1030         free_obj(obj);
1031         obj.type = isl_obj_none;
1032         obj.v = NULL;
1033         return obj;
1034 }
1035
1036 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
1037         struct isl_obj lhs, struct isl_obj rhs)
1038 {
1039         int i;
1040
1041         for (i = 0; ; ++i) {
1042                 if (!bin_ops[i].op)
1043                         break;
1044                 if (bin_ops[i].op != like->op)
1045                         continue;
1046                 if (!is_subtype(lhs, bin_ops[i].lhs))
1047                         continue;
1048                 if (!is_subtype(rhs, bin_ops[i].rhs))
1049                         continue;
1050
1051                 return &bin_ops[i];
1052         }
1053
1054         for (i = 0; ; ++i) {
1055                 if (!named_bin_ops[i].name)
1056                         break;
1057                 if (named_bin_ops[i].op.op != like->op)
1058                         continue;
1059                 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1060                         continue;
1061                 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
1062                         continue;
1063
1064                 return &named_bin_ops[i].op;
1065         }
1066
1067         return NULL;
1068 }
1069
1070 static struct isl_obj read_expr(struct isl_stream *s,
1071         struct isl_hash_table *table)
1072 {
1073         struct isl_obj obj = { isl_obj_none, NULL };
1074         struct isl_obj right_obj = { isl_obj_none, NULL };
1075
1076         obj = read_obj(s, table);
1077         for (; obj.v;) {
1078                 struct isc_bin_op *op = NULL;
1079
1080                 op = read_bin_op_if_available(s, obj);
1081                 if (!op)
1082                         break;
1083
1084                 right_obj = read_obj(s, table);
1085
1086                 op = find_matching_bin_op(op, obj, right_obj);
1087
1088                 isl_assert(s->ctx, op, goto error);
1089                 obj = convert(obj, op->lhs);
1090                 right_obj = convert(right_obj, op->rhs);
1091                 obj.v = op->fn(obj.v, right_obj.v);
1092                 obj.type = op->res;
1093         }
1094
1095         return obj;
1096 error:
1097         free_obj(right_obj);
1098         free_obj(obj);
1099         obj.type = isl_obj_none;
1100         obj.v = NULL;
1101         return obj;
1102 }
1103
1104 static __isl_give isl_printer *read_line(struct isl_stream *s,
1105         struct isl_hash_table *table, __isl_take isl_printer *p)
1106 {
1107         struct isl_obj obj = { isl_obj_none, NULL };
1108         char *lhs = NULL;
1109         int assign = 0;
1110         struct isc_bin_op *op = NULL;
1111
1112         if (!p)
1113                 return NULL;
1114         if (isl_stream_is_empty(s))
1115                 return p;
1116
1117         assign = is_assign(s);
1118         if (assign) {
1119                 lhs = isl_stream_read_ident_if_available(s);
1120                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
1121                         goto error;
1122         }
1123
1124         obj = read_expr(s, table);
1125         if (obj.type == isl_obj_none || obj.v == NULL)
1126                 goto error;
1127         if (isl_stream_eat(s, ';'))
1128                 goto error;
1129
1130         if (assign) {
1131                 if (do_assign(s->ctx, table, lhs, obj))
1132                         return;
1133         } else {
1134                 p = obj.type->print(p, obj.v);
1135                 p = isl_printer_end_line(p);
1136                 free_obj(obj);
1137         }
1138
1139         return p;
1140 error:
1141         isl_stream_flush_tokens(s);
1142         isl_stream_skip_line(s);
1143         free(lhs);
1144         free_obj(obj);
1145         return p;
1146 }
1147
1148 int free_cb(void **entry, void *user)
1149 {
1150         struct isl_named_obj *named = *entry;
1151
1152         free_obj(named->obj);
1153         free(named->name);
1154         free(named);
1155
1156         return 0;
1157 }
1158
1159 static void register_named_ops(struct isl_stream *s)
1160 {
1161         int i;
1162
1163         read_op = isl_stream_register_keyword(s, "read");
1164         assert(read_op != ISL_TOKEN_ERROR);
1165         vertices_op = isl_stream_register_keyword(s, "vertices");
1166         assert(vertices_op != ISL_TOKEN_ERROR);
1167
1168         for (i = 0; ; ++i) {
1169                 if (!named_un_ops[i].name)
1170                         break;
1171                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
1172                                                         named_un_ops[i].name);
1173                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
1174         }
1175
1176         for (i = 0; ; ++i) {
1177                 if (!named_bin_ops[i].name)
1178                         break;
1179                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
1180                                                         named_bin_ops[i].name);
1181                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
1182         }
1183 }
1184
1185 int main(int argc, char **argv)
1186 {
1187         struct isl_ctx *ctx;
1188         struct isl_stream *s;
1189         struct isl_hash_table *table;
1190         struct iscc_options *options;
1191         isl_printer *p;
1192
1193         options = iscc_options_new_with_defaults();
1194         assert(options);
1195         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
1196
1197         ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
1198         s = isl_stream_new_file(ctx, stdin);
1199         assert(s);
1200         table = isl_hash_table_alloc(ctx, 10);
1201         assert(table);
1202         p = isl_printer_to_file(ctx, stdout);
1203         p = isl_printer_set_output_format(p, options->format);
1204         assert(p);
1205
1206         register_named_ops(s);
1207
1208         while (!s->eof) {
1209                 p = read_line(s, table, p);
1210         }
1211
1212         isl_printer_free(p);
1213         isl_hash_table_foreach(ctx, table, free_cb, NULL);
1214         isl_hash_table_free(ctx, table);
1215         isl_stream_free(s);
1216         isl_ctx_free(ctx);
1217
1218         return 0;
1219 }