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_obj_list.h>
   7 #include <barvinok/barvinok.h>
   8 #include <bound_common.h>
   9
  10 #include "config.h"
  11
  12 static int isl_bool_false = 0;
  13 static int isl_bool_true = 1;
  14 static int isl_bool_error = -1;
  15
  16 static enum isl_token_type read_op;
  17
  18 struct isl_arg_choice iscc_format[] = {
  19         {"isl",         ISL_FORMAT_ISL},
  20         {"omega",       ISL_FORMAT_OMEGA},
  21         {"polylib",     ISL_FORMAT_POLYLIB},
  22         {"latex",       ISL_FORMAT_LATEX},
  23         {"C",           ISL_FORMAT_C},
  24         {0}
  25 };
  26
  27 struct iscc_options {
  28         struct isl_options      *isl;
  29         unsigned                 format;
  30 };
  31
  32 struct isl_arg iscc_options_arg[] = {
  33 ISL_ARG_CHILD(struct iscc_options, isl, "isl", isl_options_arg)
  34 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
  35         iscc_format,    ISL_FORMAT_ISL)
  36 ISL_ARG_END
  37 };
  38
  39 ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_arg)
  40
  41 static void *isl_obj_bool_copy(void *v)
  42 {
  43         return v;
  44 }
  45
  46 static void isl_obj_bool_free(void *v)
  47 {
  48 }
  49
  50 static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
  51         void *v)
  52 {
  53         if (v == &isl_bool_true)
  54                 return isl_printer_print_str(p, "True");
  55         else if (v == &isl_bool_false)
  56                 return isl_printer_print_str(p, "False");
  57         else
  58                 return isl_printer_print_str(p, "Error");
  59 }
  60
  61 static void *isl_obj_bool_add(void *v1, void *v2)
  62 {
  63         return v1;
  64 }
  65
  66 struct isl_obj_vtable isl_obj_bool_vtable = {
  67         isl_obj_bool_copy,
  68         isl_obj_bool_add,
  69         isl_obj_bool_print,
  70         isl_obj_bool_free
  71 };
  72 #define isl_obj_bool            (&isl_obj_bool_vtable)
  73
  74 int *isl_bool_from_int(int res)
  75 {
  76         return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
  77 }
  78
  79 int *map_is_equal(__isl_take isl_map *map1, __isl_take isl_map *map2)
  80 {
  81         int res = isl_map_is_equal(map1, map2);
  82         isl_map_free(map1);
  83         isl_map_free(map2);
  84         return isl_bool_from_int(res);
  85 }
  86 int *set_is_equal(__isl_take isl_set *set1, __isl_take isl_set *set2)
  87 {
  88         return map_is_equal((isl_map *)set1, (isl_map *)set2);
  89 }
  90
  91 int *map_is_subset(__isl_take isl_map *map1, __isl_take isl_map *map2)
  92 {
  93         int res = isl_map_is_subset(map1, map2);
  94         isl_map_free(map1);
  95         isl_map_free(map2);
  96         return isl_bool_from_int(res);
  97 }
  98 int *set_is_subset(__isl_take isl_set *set1, __isl_take isl_set *set2)
  99 {
 100         return map_is_subset((isl_map *)set1, (isl_map *)set2);
 101 }
 102
 103 int *map_is_strict_subset(__isl_take isl_map *map1, __isl_take isl_map *map2)
 104 {
 105         int res = isl_map_is_strict_subset(map1, map2);
 106         isl_map_free(map1);
 107         isl_map_free(map2);
 108         return isl_bool_from_int(res);
 109 }
 110 int *set_is_strict_subset(__isl_take isl_set *set1, __isl_take isl_set *set2)
 111 {
 112         return map_is_strict_subset((isl_map *)set1, (isl_map *)set2);
 113 }
 114
 115 int *map_is_superset(__isl_take isl_map *map1, __isl_take isl_map *map2)
 116 {
 117         return map_is_subset(map2, map1);
 118 }
 119 int *set_is_superset(__isl_take isl_set *set1, __isl_take isl_set *set2)
 120 {
 121         return set_is_subset(set2, set1);
 122 }
 123
 124 int *map_is_strict_superset(__isl_take isl_map *map1, __isl_take isl_map *map2)
 125 {
 126         return map_is_strict_subset(map2, map1);
 127 }
 128 int *set_is_strict_superset(__isl_take isl_set *set1, __isl_take isl_set *set2)
 129 {
 130         return set_is_strict_subset(set2, set1);
 131 }
 132
 133 extern struct isl_obj_vtable isl_obj_list_vtable;
 134 #define isl_obj_list            (&isl_obj_list_vtable)
 135
 136 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
 137 struct isc_bin_op {
 138         enum isl_token_type     op;
 139         isl_obj_type            lhs;
 140         isl_obj_type            rhs;
 141         isl_obj_type            res;
 142         isc_bin_op_fn           fn;
 143 };
 144 struct isc_named_bin_op {
 145         char                    *name;
 146         struct isc_bin_op       op;
 147 };
 148
 149 struct iscc_at {
 150         isl_pw_qpolynomial *pwqp;
 151         isl_pw_qpolynomial *res;
 152 };
 153
 154 static int eval_at(__isl_take isl_point *pnt, void *user)
 155 {
 156         struct iscc_at *at = (struct iscc_at *) user;
 157         isl_qpolynomial *qp;
 158         isl_set *set;
 159
 160         set = isl_set_from_point(isl_point_copy(pnt));
 161         qp = isl_pw_qpolynomial_eval(isl_pw_qpolynomial_copy(at->pwqp), pnt);
 162
 163         at->res = isl_pw_qpolynomial_add_disjoint(at->res,
 164                         isl_pw_qpolynomial_alloc(set, qp));
 165
 166         return 0;
 167 }
 168
 169 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_at(
 170         __isl_take isl_pw_qpolynomial *pwqp, __isl_take isl_set *set)
 171 {
 172         struct iscc_at at;
 173
 174         at.pwqp = pwqp;
 175         at.res = isl_pw_qpolynomial_zero(isl_set_get_dim(set));
 176
 177         isl_set_foreach_point(set, eval_at, &at);
 178
 179         isl_pw_qpolynomial_free(pwqp);
 180         isl_set_free(set);
 181
 182         return at.res;
 183 }
 184
 185 struct iscc_fold_at {
 186         isl_pw_qpolynomial_fold *pwf;
 187         isl_pw_qpolynomial *res;
 188 };
 189
 190 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
 191 {
 192         struct iscc_fold_at *at = (struct iscc_fold_at *) user;
 193         isl_qpolynomial *qp;
 194         isl_set *set;
 195
 196         set = isl_set_from_point(isl_point_copy(pnt));
 197         qp = isl_pw_qpolynomial_fold_eval(isl_pw_qpolynomial_fold_copy(at->pwf),
 198                                                 pnt);
 199
 200         at->res = isl_pw_qpolynomial_add_disjoint(at->res,
 201                         isl_pw_qpolynomial_alloc(set, qp));
 202
 203         return 0;
 204 }
 205
 206 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_fold_at(
 207         __isl_take isl_pw_qpolynomial_fold *pwf, __isl_take isl_set *set)
 208 {
 209         struct iscc_fold_at at;
 210
 211         at.pwf = pwf;
 212         at.res = isl_pw_qpolynomial_zero(isl_set_get_dim(set));
 213
 214         isl_set_foreach_point(set, eval_fold_at, &at);
 215
 216         isl_pw_qpolynomial_fold_free(pwf);
 217         isl_set_free(set);
 218
 219         return at.res;
 220 }
 221
 222 struct isc_bin_op bin_ops[] = {
 223         { '+',  isl_obj_set,    isl_obj_set,
 224                 isl_obj_set,
 225                 (isc_bin_op_fn) &isl_set_union },
 226         { '+',  isl_obj_map,    isl_obj_map,
 227                 isl_obj_map,
 228                 (isc_bin_op_fn) &isl_map_union },
 229         { '-',  isl_obj_set,    isl_obj_set,
 230                 isl_obj_set,
 231                 (isc_bin_op_fn) &isl_set_subtract },
 232         { '-',  isl_obj_map,    isl_obj_map,
 233                 isl_obj_map,
 234                 (isc_bin_op_fn) &isl_map_subtract },
 235         { '*',  isl_obj_set,    isl_obj_set,
 236                 isl_obj_set,
 237                 (isc_bin_op_fn) &isl_set_intersect },
 238         { '*',  isl_obj_map,    isl_obj_map,
 239                 isl_obj_map,
 240                 (isc_bin_op_fn) &isl_map_intersect },
 241         { '*',  isl_obj_map,    isl_obj_set,
 242                 isl_obj_map,
 243                 (isc_bin_op_fn) &isl_map_intersect_domain },
 244         { '.',  isl_obj_map,    isl_obj_map,
 245                 isl_obj_map,
 246                 (isc_bin_op_fn) &isl_map_apply_range },
 247         { ISL_TOKEN_TO, isl_obj_set,    isl_obj_set,    isl_obj_map,
 248                 (isc_bin_op_fn) &isl_map_from_domain_and_range },
 249         { '=', isl_obj_set,     isl_obj_set,    isl_obj_bool,
 250                 (isc_bin_op_fn) &set_is_equal },
 251         { '=', isl_obj_map,     isl_obj_map,    isl_obj_bool,
 252                 (isc_bin_op_fn) &map_is_equal },
 253         { ISL_TOKEN_LE, isl_obj_set,    isl_obj_set,    isl_obj_bool,
 254                 (isc_bin_op_fn) &set_is_subset },
 255         { ISL_TOKEN_LE, isl_obj_map,    isl_obj_map,    isl_obj_bool,
 256                 (isc_bin_op_fn) &map_is_subset },
 257         { ISL_TOKEN_LT, isl_obj_set,    isl_obj_set,    isl_obj_bool,
 258                 (isc_bin_op_fn) &set_is_strict_subset },
 259         { ISL_TOKEN_LT, isl_obj_map,    isl_obj_map,    isl_obj_bool,
 260                 (isc_bin_op_fn) &map_is_strict_subset },
 261         { ISL_TOKEN_GE, isl_obj_set,    isl_obj_set,    isl_obj_bool,
 262                 (isc_bin_op_fn) &set_is_superset },
 263         { ISL_TOKEN_GE, isl_obj_map,    isl_obj_map,    isl_obj_bool,
 264                 (isc_bin_op_fn) &map_is_superset },
 265         { ISL_TOKEN_GT, isl_obj_set,    isl_obj_set,    isl_obj_bool,
 266                 (isc_bin_op_fn) &set_is_strict_superset },
 267         { ISL_TOKEN_GT, isl_obj_map,    isl_obj_map,    isl_obj_bool,
 268                 (isc_bin_op_fn) &map_is_strict_superset },
 269         { '+',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 270                 isl_obj_pw_qpolynomial,
 271                 (isc_bin_op_fn) &isl_pw_qpolynomial_add },
 272         { '-',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 273                 isl_obj_pw_qpolynomial,
 274                 (isc_bin_op_fn) &isl_pw_qpolynomial_sub },
 275         { '*',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 276                 isl_obj_pw_qpolynomial,
 277                 (isc_bin_op_fn) &isl_pw_qpolynomial_mul },
 278         { '*',  isl_obj_pw_qpolynomial, isl_obj_set,
 279                 isl_obj_pw_qpolynomial,
 280                 (isc_bin_op_fn) &isl_pw_qpolynomial_intersect_domain },
 281         { '*',  isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 282                 isl_obj_pw_qpolynomial_fold,
 283                 (isc_bin_op_fn) &isl_pw_qpolynomial_fold_intersect_domain },
 284         { '@',  isl_obj_pw_qpolynomial, isl_obj_set,
 285                 isl_obj_pw_qpolynomial,
 286                 (isc_bin_op_fn) &isl_pw_qpolynomial_at },
 287         { '@',  isl_obj_pw_qpolynomial_fold, isl_obj_set,
 288                 isl_obj_pw_qpolynomial,
 289                 (isc_bin_op_fn) &isl_pw_qpolynomial_fold_at },
 290         { '%',  isl_obj_set,    isl_obj_set,
 291                 isl_obj_set,
 292                 (isc_bin_op_fn) &isl_set_gist },
 293         { '%',  isl_obj_map,    isl_obj_map,
 294                 isl_obj_map,
 295                 (isc_bin_op_fn) &isl_map_gist },
 296         { '%',  isl_obj_pw_qpolynomial, isl_obj_set,
 297                 isl_obj_pw_qpolynomial,
 298                 (isc_bin_op_fn) &isl_pw_qpolynomial_gist },
 299         { '%',  isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 300                 isl_obj_pw_qpolynomial_fold,
 301                 (isc_bin_op_fn) &isl_pw_qpolynomial_fold_gist },
 302         0
 303 };
 304 struct isc_named_bin_op named_bin_ops[] = {
 305         { "cross",      { -1,   isl_obj_set,    isl_obj_set,    isl_obj_set,
 306                 (isc_bin_op_fn) &isl_set_product } },
 307         { "cross",      { -1,   isl_obj_map,    isl_obj_map,    isl_obj_map,
 308                 (isc_bin_op_fn) &isl_map_product } },
 309         NULL
 310 };
 311
 312 __isl_give isl_set *set_sample(__isl_take isl_set *set)
 313 {
 314         return isl_set_from_basic_set(isl_set_sample(set));
 315 }
 316
 317 __isl_give isl_map *map_sample(__isl_take isl_map *map)
 318 {
 319         return isl_map_from_basic_map(isl_map_sample(map));
 320 }
 321
 322 static __isl_give isl_set *set_affine_hull(__isl_take isl_set *set)
 323 {
 324         return isl_set_from_basic_set(isl_set_affine_hull(set));
 325 }
 326
 327 static __isl_give isl_map *map_affine_hull(__isl_take isl_map *map)
 328 {
 329         return isl_map_from_basic_map(isl_map_affine_hull(map));
 330 }
 331
 332 static __isl_give isl_pw_qpolynomial_fold *pw_qpolynomial_upper_bound(
 333         __isl_take isl_pw_qpolynomial *pwqp)
 334 {
 335 #ifdef HAVE_GINAC
 336         return isl_pw_qpolynomial_bound(pwqp, isl_fold_max, BV_BOUND_BERNSTEIN);
 337 #else
 338         return isl_pw_qpolynomial_bound(pwqp, isl_fold_max, BV_BOUND_RANGE);
 339 #endif
 340 }
 341
 342 typedef void *(*isc_un_op_fn)(void *arg);
 343 struct isc_un_op {
 344         enum isl_token_type     op;
 345         isl_obj_type            arg;
 346         isl_obj_type            res;
 347         isc_un_op_fn            fn;
 348 };
 349 struct isc_named_un_op {
 350         char                    *name;
 351         struct isc_un_op        op;
 352 };
 353 struct isc_named_un_op named_un_ops[] = {
 354         {"aff", { -1,   isl_obj_map,    isl_obj_map,
 355                 (isc_un_op_fn) &map_affine_hull } },
 356         {"aff", { -1,   isl_obj_set,    isl_obj_set,
 357                 (isc_un_op_fn) &set_affine_hull } },
 358         {"card",        { -1,   isl_obj_set,    isl_obj_pw_qpolynomial,
 359                 (isc_un_op_fn) &isl_set_card } },
 360         {"card",        { -1,   isl_obj_map,    isl_obj_pw_qpolynomial,
 361                 (isc_un_op_fn) &isl_map_card } },
 362         {"coalesce",    { -1,   isl_obj_set,    isl_obj_set,
 363                 (isc_un_op_fn) &isl_set_coalesce } },
 364         {"coalesce",    { -1,   isl_obj_map,    isl_obj_map,
 365                 (isc_un_op_fn) &isl_map_coalesce } },
 366         {"coalesce",    { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 367                 (isc_un_op_fn) &isl_pw_qpolynomial_coalesce } },
 368         {"coalesce",    { -1,   isl_obj_pw_qpolynomial_fold,
 369                 isl_obj_pw_qpolynomial_fold,
 370                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_coalesce } },
 371         {"deltas",      { -1,   isl_obj_map,    isl_obj_set,
 372                 (isc_un_op_fn) &isl_map_deltas } },
 373         {"dom", { -1,   isl_obj_map,    isl_obj_set,
 374                 (isc_un_op_fn) &isl_map_domain } },
 375         {"dom", { -1,   isl_obj_pw_qpolynomial, isl_obj_set,
 376                 (isc_un_op_fn) &isl_pw_qpolynomial_domain } },
 377         {"dom", { -1,   isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 378                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_domain } },
 379         {"ran", { -1,   isl_obj_map,    isl_obj_set,
 380                 (isc_un_op_fn) &isl_map_range } },
 381         {"lexmin",      { -1,   isl_obj_map,    isl_obj_map,
 382                 (isc_un_op_fn) &isl_map_lexmin } },
 383         {"lexmax",      { -1,   isl_obj_map,    isl_obj_map,
 384                 (isc_un_op_fn) &isl_map_lexmax } },
 385         {"lexmin",      { -1,   isl_obj_set,    isl_obj_set,
 386                 (isc_un_op_fn) &isl_set_lexmin } },
 387         {"lexmax",      { -1,   isl_obj_set,    isl_obj_set,
 388                 (isc_un_op_fn) &isl_set_lexmax } },
 389         {"sample",      { -1,   isl_obj_set,    isl_obj_set,
 390                 (isc_un_op_fn) &set_sample } },
 391         {"sample",      { -1,   isl_obj_map,    isl_obj_map,
 392                 (isc_un_op_fn) &map_sample } },
 393         {"sum",         { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 394                 (isc_un_op_fn) &isl_pw_qpolynomial_sum } },
 395         {"ub",          { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial_fold,
 396                 (isc_un_op_fn) &pw_qpolynomial_upper_bound } },
 397         NULL
 398 };
 399
 400 struct isl_named_obj {
 401         char            *name;
 402         struct isl_obj  obj;
 403 };
 404
 405 static void free_obj(struct isl_obj obj)
 406 {
 407         obj.type->free(obj.v);
 408 }
 409
 410 static int same_name(const void *entry, const void *val)
 411 {
 412         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 413
 414         return !strcmp(named->name, val);
 415 }
 416
 417 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 418         char *name, struct isl_obj obj)
 419 {
 420         struct isl_hash_table_entry *entry;
 421         uint32_t name_hash;
 422         struct isl_named_obj *named;
 423
 424         name_hash = isl_hash_string(isl_hash_init(), name);
 425         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 426         if (!entry)
 427                 goto error;
 428         if (entry->data) {
 429                 named = entry->data;
 430                 free_obj(named->obj);
 431                 free(name);
 432         } else {
 433                 named = isl_alloc_type(ctx, struct isl_named_obj);
 434                 if (!named)
 435                         goto error;
 436                 named->name = name;
 437                 entry->data = named;
 438         }
 439         named->obj = obj;
 440
 441         return 0;
 442 error:
 443         free_obj(obj);
 444         free(name);
 445         return -1;
 446 }
 447
 448 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 449         struct isl_hash_table *table, char *name)
 450 {
 451         struct isl_obj obj = { isl_obj_none, NULL };
 452         struct isl_hash_table_entry *entry;
 453         uint32_t name_hash;
 454
 455         name_hash = isl_hash_string(isl_hash_init(), name);
 456         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 457         if (entry) {
 458                 struct isl_named_obj *named;
 459                 named = entry->data;
 460                 obj = named->obj;
 461         }
 462
 463         free(name);
 464         obj.v = obj.type->copy(obj.v);
 465         return obj;
 466 }
 467
 468 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 469         isl_obj_type lhs)
 470 {
 471         int i;
 472         struct isl_token *tok;
 473
 474         tok = isl_stream_next_token(s);
 475         if (!tok)
 476                 return NULL;
 477
 478         for (i = 0; ; ++i) {
 479                 if (!bin_ops[i].op)
 480                         break;
 481                 if (bin_ops[i].op != tok->type)
 482                         continue;
 483                 if (bin_ops[i].lhs != lhs)
 484                         continue;
 485
 486                 isl_token_free(tok);
 487                 return &bin_ops[i];
 488         }
 489
 490         for (i = 0; ; ++i) {
 491                 if (!named_bin_ops[i].name)
 492                         break;
 493                 if (named_bin_ops[i].op.op != tok->type)
 494                         continue;
 495                 if (named_bin_ops[i].op.lhs != lhs)
 496                         continue;
 497
 498                 isl_token_free(tok);
 499                 return &named_bin_ops[i].op;
 500         }
 501
 502         isl_stream_push_token(s, tok);
 503
 504         return NULL;
 505 }
 506
 507 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 508 {
 509         int i;
 510         struct isl_token *tok;
 511
 512         tok = isl_stream_next_token(s);
 513         if (!tok)
 514                 return NULL;
 515
 516         for (i = 0; ; ++i) {
 517                 if (!named_un_ops[i].name)
 518                         break;
 519                 if (named_un_ops[i].op.op != tok->type)
 520                         continue;
 521
 522                 isl_token_free(tok);
 523                 return &named_un_ops[i].op;
 524         }
 525
 526         isl_stream_push_token(s, tok);
 527
 528         return NULL;
 529 }
 530
 531 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 532         isl_obj_type arg)
 533 {
 534         int i;
 535
 536         for (i = 0; ; ++i) {
 537                 if (!named_un_ops[i].name)
 538                         break;
 539                 if (named_un_ops[i].op.op != like->op)
 540                         continue;
 541                 if (named_un_ops[i].op.arg != arg)
 542                         continue;
 543
 544                 return &named_un_ops[i].op;
 545         }
 546
 547         return NULL;
 548 }
 549
 550 static int is_assign(struct isl_stream *s)
 551 {
 552         struct isl_token *tok;
 553         struct isl_token *tok2;
 554         int assign;
 555
 556         tok = isl_stream_next_token(s);
 557         if (!tok)
 558                 return 0;
 559         if (tok->type != ISL_TOKEN_IDENT) {
 560                 isl_stream_push_token(s, tok);
 561                 return 0;
 562         }
 563
 564         tok2 = isl_stream_next_token(s);
 565         if (!tok2) {
 566                 isl_stream_push_token(s, tok);
 567                 return 0;
 568         }
 569         assign = tok2->type == ISL_TOKEN_DEF;
 570         isl_stream_push_token(s, tok2);
 571         isl_stream_push_token(s, tok);
 572
 573         return assign;
 574 }
 575
 576 static struct isl_obj read_obj(struct isl_stream *s,
 577         struct isl_hash_table *table);
 578 static struct isl_obj read_expr(struct isl_stream *s,
 579         struct isl_hash_table *table);
 580
 581 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 582         struct isl_hash_table *table, struct isc_un_op *op)
 583 {
 584         struct isl_obj obj = { isl_obj_none, NULL };
 585
 586         obj = read_obj(s, table);
 587
 588         op = find_matching_un_op(op, obj.type);
 589
 590         isl_assert(s->ctx, op, goto error);
 591         obj.v = op->fn(obj.v);
 592         obj.type = op->res;
 593
 594         return obj;
 595 error:
 596         free_obj(obj);
 597         obj.type = isl_obj_none;
 598         obj.v = NULL;
 599         return obj;
 600 }
 601
 602 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 603 {
 604         struct isl_list *list;
 605         int exact;
 606
 607         isl_assert(ctx, obj.type == isl_obj_map, goto error);
 608         list = isl_list_alloc(ctx, 2);
 609         if (!list)
 610                 goto error;
 611
 612         list->obj[0].type = isl_obj_map;
 613         list->obj[0].v = isl_map_transitive_closure(obj.v, &exact);
 614         list->obj[1].type = isl_obj_bool;
 615         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 616         obj.v = list;
 617         obj.type = isl_obj_list;
 618         if (exact < 0 || !list->obj[0].v)
 619                 goto error;
 620
 621         return obj;
 622 error:
 623         free_obj(obj);
 624         obj.type = isl_obj_none;
 625         obj.v = NULL;
 626         return obj;
 627 }
 628
 629 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 630 {
 631         struct isl_list *list = obj.v;
 632         struct isl_token *tok;
 633         int i;
 634
 635         tok = isl_stream_next_token(s);
 636         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 637                 isl_stream_error(s, tok, "expecting index");
 638                 if (tok)
 639                         isl_stream_push_token(s, tok);
 640                 goto error;
 641         }
 642         i = isl_int_get_si(tok->u.v);
 643         isl_token_free(tok);
 644         isl_assert(s, i < list->n, goto error);
 645         if (isl_stream_eat(s, ']'))
 646                 goto error;
 647
 648         obj = list->obj[i];
 649         obj.v = obj.type->copy(obj.v);
 650
 651         isl_list_free(list);
 652
 653         return obj;
 654 error:
 655         free_obj(obj);
 656         obj.type = isl_obj_none;
 657         obj.v = NULL;
 658         return obj;
 659 }
 660
 661 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_map *map,
 662         struct isl_hash_table *table)
 663 {
 664         struct isl_obj obj;
 665
 666         obj = read_expr(s, table);
 667         isl_assert(s->ctx, obj.type == isl_obj_set || obj.type == isl_obj_map,
 668                 goto error);
 669
 670         if (obj.type == isl_obj_set) {
 671                 obj.v = isl_set_apply(obj.v, map);
 672         } else
 673                 obj.v = isl_map_apply_range(obj.v, map);
 674         if (!obj.v)
 675                 goto error;
 676
 677         if (isl_stream_eat(s, ')'))
 678                 goto error;
 679
 680         return obj;
 681 error:
 682         free_obj(obj);
 683         obj.type = isl_obj_none;
 684         obj.v = NULL;
 685         return obj;
 686 }
 687
 688 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
 689 {
 690         struct isl_token *tok;
 691
 692         if (isl_stream_eat_if_available(s, '+'))
 693                 return transitive_closure(s->ctx, obj);
 694
 695         tok = isl_stream_next_token(s);
 696         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
 697                 isl_stream_error(s, tok, "expecting -1");
 698                 if (tok)
 699                         isl_stream_push_token(s, tok);
 700                 goto error;
 701         }
 702         isl_token_free(tok);
 703         isl_assert(s->ctx, obj.type == isl_obj_map, goto error);
 704
 705         obj.v = isl_map_reverse(obj.v);
 706         if (!obj.v)
 707                 goto error;
 708
 709         return obj;
 710 error:
 711         free_obj(obj);
 712         obj.type = isl_obj_none;
 713         obj.v = NULL;
 714         return obj;
 715 }
 716
 717 static struct isl_obj read_from_file(struct isl_stream *s)
 718 {
 719         struct isl_obj obj;
 720         struct isl_token *tok;
 721         struct isl_stream *s_file;
 722         FILE *file;
 723
 724         tok = isl_stream_next_token(s);
 725         if (!tok || tok->type != ISL_TOKEN_STRING) {
 726                 isl_stream_error(s, tok, "expecting filename");
 727                 isl_token_free(tok);
 728                 goto error;
 729         }
 730
 731         file = fopen(tok->u.s, "r");
 732         isl_token_free(tok);
 733         isl_assert(s->ctx, file, goto error);
 734
 735         s_file = isl_stream_new_file(s->ctx, file);
 736         if (!s_file) {
 737                 fclose(file);
 738                 goto error;
 739         }
 740
 741         obj = isl_stream_read_obj(s_file);
 742
 743         isl_stream_free(s_file);
 744         fclose(file);
 745
 746         return obj;
 747 error:
 748         obj.type = isl_obj_none;
 749         obj.v = NULL;
 750         return obj;
 751 }
 752
 753 static struct isl_obj read_obj(struct isl_stream *s,
 754         struct isl_hash_table *table)
 755 {
 756         struct isl_obj obj = { isl_obj_none, NULL };
 757         char *name = NULL;
 758         struct isc_un_op *op = NULL;
 759
 760         if (isl_stream_eat_if_available(s, '(')) {
 761                 obj = read_expr(s, table);
 762                 if (isl_stream_eat(s, ')'))
 763                         goto error;
 764         } else {
 765                 op = read_prefix_un_op_if_available(s);
 766                 if (op)
 767                         return read_un_op_expr(s, table, op);
 768
 769                 if (isl_stream_eat_if_available(s, read_op))
 770                         return read_from_file(s);
 771
 772                 name = isl_stream_read_ident_if_available(s);
 773                 if (name) {
 774                         obj = stored_obj(s->ctx, table, name);
 775                 } else {
 776                         obj = isl_stream_read_obj(s);
 777                         assert(obj.v);
 778                 }
 779         }
 780
 781         if (isl_stream_eat_if_available(s, '^'))
 782                 obj = power(s, obj);
 783         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
 784                 obj = obj_at_index(s, obj);
 785         else if (obj.type == isl_obj_map && isl_stream_eat_if_available(s, '('))
 786                 obj = apply(s, obj.v, table);
 787
 788         return obj;
 789 error:
 790         free_obj(obj);
 791         obj.type = isl_obj_none;
 792         obj.v = NULL;
 793         return obj;
 794 }
 795
 796 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
 797         isl_obj_type lhs, isl_obj_type rhs)
 798 {
 799         int i;
 800
 801         for (i = 0; ; ++i) {
 802                 if (!bin_ops[i].op)
 803                         break;
 804                 if (bin_ops[i].op != like->op)
 805                         continue;
 806                 if (bin_ops[i].lhs != lhs)
 807                         continue;
 808                 if (bin_ops[i].rhs != rhs)
 809                         continue;
 810
 811                 return &bin_ops[i];
 812         }
 813
 814         for (i = 0; ; ++i) {
 815                 if (!named_bin_ops[i].name)
 816                         break;
 817                 if (named_bin_ops[i].op.op != like->op)
 818                         continue;
 819                 if (named_bin_ops[i].op.lhs != lhs)
 820                         continue;
 821                 if (named_bin_ops[i].op.rhs != rhs)
 822                         continue;
 823
 824                 return &named_bin_ops[i].op;
 825         }
 826
 827         return NULL;
 828 }
 829
 830 static struct isl_obj read_expr(struct isl_stream *s,
 831         struct isl_hash_table *table)
 832 {
 833         struct isl_obj obj = { isl_obj_none, NULL };
 834         struct isl_obj right_obj = { isl_obj_none, NULL };
 835
 836         obj = read_obj(s, table);
 837         for (;;) {
 838                 struct isc_bin_op *op = NULL;
 839
 840                 op = read_bin_op_if_available(s, obj.type);
 841                 if (!op)
 842                         break;
 843
 844                 right_obj = read_obj(s, table);
 845
 846                 op = find_matching_bin_op(op, obj.type, right_obj.type);
 847
 848                 isl_assert(s->ctx, op, goto error);
 849                 obj.v = op->fn(obj.v, right_obj.v);
 850                 obj.type = op->res;
 851         }
 852
 853         return obj;
 854 error:
 855         free_obj(right_obj);
 856         free_obj(obj);
 857         obj.type = isl_obj_none;
 858         obj.v = NULL;
 859         return obj;
 860 }
 861
 862 static __isl_give isl_printer *read_line(struct isl_stream *s,
 863         struct isl_hash_table *table, __isl_take isl_printer *p)
 864 {
 865         struct isl_obj obj = { isl_obj_none, NULL };
 866         char *lhs = NULL;
 867         int assign = 0;
 868         struct isc_bin_op *op = NULL;
 869
 870         if (!p)
 871                 return NULL;
 872         if (isl_stream_is_empty(s))
 873                 return p;
 874
 875         assign = is_assign(s);
 876         if (assign) {
 877                 lhs = isl_stream_read_ident_if_available(s);
 878                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
 879                         goto error;
 880         }
 881
 882         obj = read_expr(s, table);
 883         if (obj.type == isl_obj_none || obj.v == NULL)
 884                 goto error;
 885         if (isl_stream_eat(s, ';'))
 886                 goto error;
 887
 888         if (assign) {
 889                 if (do_assign(s->ctx, table, lhs, obj))
 890                         return;
 891         } else {
 892                 p = obj.type->print(p, obj.v);
 893                 p = isl_printer_end_line(p);
 894                 free_obj(obj);
 895         }
 896
 897         return p;
 898 error:
 899         free(lhs);
 900         free_obj(obj);
 901         return p;
 902 }
 903
 904 int free_cb(void *entry)
 905 {
 906         struct isl_named_obj *named = entry;
 907
 908         free_obj(named->obj);
 909         free(named->name);
 910         free(named);
 911
 912         return 0;
 913 }
 914
 915 static void register_named_ops(struct isl_stream *s)
 916 {
 917         int i;
 918
 919         read_op = isl_stream_register_keyword(s, "read");
 920         assert(read_op != ISL_TOKEN_ERROR);
 921
 922         for (i = 0; ; ++i) {
 923                 if (!named_un_ops[i].name)
 924                         break;
 925                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
 926                                                         named_un_ops[i].name);
 927                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
 928         }
 929
 930         for (i = 0; ; ++i) {
 931                 if (!named_bin_ops[i].name)
 932                         break;
 933                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
 934                                                         named_bin_ops[i].name);
 935                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
 936         }
 937 }
 938
 939 int main(int argc, char **argv)
 940 {
 941         struct isl_ctx *ctx;
 942         struct isl_stream *s;
 943         struct isl_hash_table *table;
 944         struct iscc_options *options;
 945         isl_printer *p;
 946
 947         options = iscc_options_new_with_defaults();
 948         assert(options);
 949         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
 950
 951         ctx = isl_ctx_alloc_with_options(options->isl);
 952         options->isl = NULL;
 953         s = isl_stream_new_file(ctx, stdin);
 954         assert(s);
 955         table = isl_hash_table_alloc(ctx, 10);
 956         assert(table);
 957         p = isl_printer_to_file(ctx, stdout);
 958         p = isl_printer_set_output_format(p, options->format);
 959         assert(p);
 960
 961         register_named_ops(s);
 962
 963         while (!s->eof) {
 964                 p = read_line(s, table, p);
 965         }
 966
 967         isl_printer_free(p);
 968         isl_hash_table_foreach(ctx, table, free_cb);
 969         isl_hash_table_free(ctx, table);
 970         isl_stream_free(s);
 971         isl_ctx_free(ctx);
 972         free(options);
 973
 974         return 0;
 975 }