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