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 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 typedef void *(*isc_un_op_fn)(void *arg);
 333 struct isc_un_op {
 334         enum isl_token_type     op;
 335         isl_obj_type            arg;
 336         isl_obj_type            res;
 337         isc_un_op_fn            fn;
 338 };
 339 struct isc_named_un_op {
 340         char                    *name;
 341         struct isc_un_op        op;
 342 };
 343 struct isc_named_un_op named_un_ops[] = {
 344         {"aff", { -1,   isl_obj_map,    isl_obj_map,
 345                 (isc_un_op_fn) &map_affine_hull } },
 346         {"aff", { -1,   isl_obj_set,    isl_obj_set,
 347                 (isc_un_op_fn) &set_affine_hull } },
 348         {"card",        { -1,   isl_obj_set,    isl_obj_pw_qpolynomial,
 349                 (isc_un_op_fn) &isl_set_card } },
 350         {"card",        { -1,   isl_obj_map,    isl_obj_pw_qpolynomial,
 351                 (isc_un_op_fn) &isl_map_card } },
 352         {"coalesce",    { -1,   isl_obj_set,    isl_obj_set,
 353                 (isc_un_op_fn) &isl_set_coalesce } },
 354         {"coalesce",    { -1,   isl_obj_map,    isl_obj_map,
 355                 (isc_un_op_fn) &isl_map_coalesce } },
 356         {"coalesce",    { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 357                 (isc_un_op_fn) &isl_pw_qpolynomial_coalesce } },
 358         {"coalesce",    { -1,   isl_obj_pw_qpolynomial_fold,
 359                 isl_obj_pw_qpolynomial_fold,
 360                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_coalesce } },
 361         {"deltas",      { -1,   isl_obj_map,    isl_obj_set,
 362                 (isc_un_op_fn) &isl_map_deltas } },
 363         {"dom", { -1,   isl_obj_map,    isl_obj_set,
 364                 (isc_un_op_fn) &isl_map_domain } },
 365         {"dom", { -1,   isl_obj_pw_qpolynomial, isl_obj_set,
 366                 (isc_un_op_fn) &isl_pw_qpolynomial_domain } },
 367         {"dom", { -1,   isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 368                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_domain } },
 369         {"ran", { -1,   isl_obj_map,    isl_obj_set,
 370                 (isc_un_op_fn) &isl_map_range } },
 371         {"lexmin",      { -1,   isl_obj_map,    isl_obj_map,
 372                 (isc_un_op_fn) &isl_map_lexmin } },
 373         {"lexmax",      { -1,   isl_obj_map,    isl_obj_map,
 374                 (isc_un_op_fn) &isl_map_lexmax } },
 375         {"lexmin",      { -1,   isl_obj_set,    isl_obj_set,
 376                 (isc_un_op_fn) &isl_set_lexmin } },
 377         {"lexmax",      { -1,   isl_obj_set,    isl_obj_set,
 378                 (isc_un_op_fn) &isl_set_lexmax } },
 379         {"sample",      { -1,   isl_obj_set,    isl_obj_set,
 380                 (isc_un_op_fn) &set_sample } },
 381         {"sample",      { -1,   isl_obj_map,    isl_obj_map,
 382                 (isc_un_op_fn) &map_sample } },
 383         {"sum",         { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 384                 (isc_un_op_fn) &isl_pw_qpolynomial_sum } },
 385 #ifdef HAVE_GINAC
 386         {"ub",          { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial_fold,
 387                 (isc_un_op_fn) &isl_pw_qpolynomial_upper_bound } },
 388 #endif
 389         NULL
 390 };
 391
 392 struct isl_named_obj {
 393         char            *name;
 394         struct isl_obj  obj;
 395 };
 396
 397 static void free_obj(struct isl_obj obj)
 398 {
 399         obj.type->free(obj.v);
 400 }
 401
 402 static int same_name(const void *entry, const void *val)
 403 {
 404         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 405
 406         return !strcmp(named->name, val);
 407 }
 408
 409 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 410         char *name, struct isl_obj obj)
 411 {
 412         struct isl_hash_table_entry *entry;
 413         uint32_t name_hash;
 414         struct isl_named_obj *named;
 415
 416         name_hash = isl_hash_string(isl_hash_init(), name);
 417         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 418         if (!entry)
 419                 goto error;
 420         if (entry->data) {
 421                 named = entry->data;
 422                 free_obj(named->obj);
 423                 free(name);
 424         } else {
 425                 named = isl_alloc_type(ctx, struct isl_named_obj);
 426                 if (!named)
 427                         goto error;
 428                 named->name = name;
 429                 entry->data = named;
 430         }
 431         named->obj = obj;
 432
 433         return 0;
 434 error:
 435         free_obj(obj);
 436         free(name);
 437         return -1;
 438 }
 439
 440 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 441         struct isl_hash_table *table, char *name)
 442 {
 443         struct isl_obj obj = { isl_obj_none, NULL };
 444         struct isl_hash_table_entry *entry;
 445         uint32_t name_hash;
 446
 447         name_hash = isl_hash_string(isl_hash_init(), name);
 448         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 449         if (entry) {
 450                 struct isl_named_obj *named;
 451                 named = entry->data;
 452                 obj = named->obj;
 453         }
 454
 455         free(name);
 456         obj.v = obj.type->copy(obj.v);
 457         return obj;
 458 }
 459
 460 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 461         isl_obj_type lhs)
 462 {
 463         int i;
 464         struct isl_token *tok;
 465
 466         tok = isl_stream_next_token(s);
 467         if (!tok)
 468                 return NULL;
 469
 470         for (i = 0; ; ++i) {
 471                 if (!bin_ops[i].op)
 472                         break;
 473                 if (bin_ops[i].op != tok->type)
 474                         continue;
 475                 if (bin_ops[i].lhs != lhs)
 476                         continue;
 477
 478                 isl_token_free(tok);
 479                 return &bin_ops[i];
 480         }
 481
 482         for (i = 0; ; ++i) {
 483                 if (!named_bin_ops[i].name)
 484                         break;
 485                 if (named_bin_ops[i].op.op != tok->type)
 486                         continue;
 487                 if (named_bin_ops[i].op.lhs != lhs)
 488                         continue;
 489
 490                 isl_token_free(tok);
 491                 return &named_bin_ops[i].op;
 492         }
 493
 494         isl_stream_push_token(s, tok);
 495
 496         return NULL;
 497 }
 498
 499 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 500 {
 501         int i;
 502         struct isl_token *tok;
 503
 504         tok = isl_stream_next_token(s);
 505         if (!tok)
 506                 return NULL;
 507
 508         for (i = 0; ; ++i) {
 509                 if (!named_un_ops[i].name)
 510                         break;
 511                 if (named_un_ops[i].op.op != tok->type)
 512                         continue;
 513
 514                 isl_token_free(tok);
 515                 return &named_un_ops[i].op;
 516         }
 517
 518         isl_stream_push_token(s, tok);
 519
 520         return NULL;
 521 }
 522
 523 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 524         isl_obj_type arg)
 525 {
 526         int i;
 527
 528         for (i = 0; ; ++i) {
 529                 if (!named_un_ops[i].name)
 530                         break;
 531                 if (named_un_ops[i].op.op != like->op)
 532                         continue;
 533                 if (named_un_ops[i].op.arg != arg)
 534                         continue;
 535
 536                 return &named_un_ops[i].op;
 537         }
 538
 539         return NULL;
 540 }
 541
 542 static int is_assign(struct isl_stream *s)
 543 {
 544         struct isl_token *tok;
 545         struct isl_token *tok2;
 546         int assign;
 547
 548         tok = isl_stream_next_token(s);
 549         if (!tok)
 550                 return 0;
 551         if (tok->type != ISL_TOKEN_IDENT) {
 552                 isl_stream_push_token(s, tok);
 553                 return 0;
 554         }
 555
 556         tok2 = isl_stream_next_token(s);
 557         if (!tok2) {
 558                 isl_stream_push_token(s, tok);
 559                 return 0;
 560         }
 561         assign = tok2->type == ISL_TOKEN_DEF;
 562         isl_stream_push_token(s, tok2);
 563         isl_stream_push_token(s, tok);
 564
 565         return assign;
 566 }
 567
 568 static struct isl_obj read_obj(struct isl_stream *s,
 569         struct isl_hash_table *table);
 570 static struct isl_obj read_expr(struct isl_stream *s,
 571         struct isl_hash_table *table);
 572
 573 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 574         struct isl_hash_table *table, struct isc_un_op *op)
 575 {
 576         struct isl_obj obj = { isl_obj_none, NULL };
 577
 578         obj = read_obj(s, table);
 579
 580         op = find_matching_un_op(op, obj.type);
 581
 582         isl_assert(s->ctx, op, goto error);
 583         obj.v = op->fn(obj.v);
 584         obj.type = op->res;
 585
 586         return obj;
 587 error:
 588         free_obj(obj);
 589         obj.type = isl_obj_none;
 590         obj.v = NULL;
 591         return obj;
 592 }
 593
 594 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 595 {
 596         struct isl_list *list;
 597         int exact;
 598
 599         isl_assert(ctx, obj.type == isl_obj_map, goto error);
 600         list = isl_list_alloc(ctx, 2);
 601         if (!list)
 602                 goto error;
 603
 604         list->obj[0].type = isl_obj_map;
 605         list->obj[0].v = isl_map_transitive_closure(obj.v, &exact);
 606         list->obj[1].type = isl_obj_bool;
 607         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 608         obj.v = list;
 609         obj.type = isl_obj_list;
 610         if (exact < 0 || !list->obj[0].v)
 611                 goto error;
 612
 613         return obj;
 614 error:
 615         free_obj(obj);
 616         obj.type = isl_obj_none;
 617         obj.v = NULL;
 618         return obj;
 619 }
 620
 621 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 622 {
 623         struct isl_list *list = obj.v;
 624         struct isl_token *tok;
 625         int i;
 626
 627         tok = isl_stream_next_token(s);
 628         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 629                 isl_stream_error(s, tok, "expecting index");
 630                 if (tok)
 631                         isl_stream_push_token(s, tok);
 632                 goto error;
 633         }
 634         i = isl_int_get_si(tok->u.v);
 635         isl_token_free(tok);
 636         isl_assert(s, i < list->n, goto error);
 637         if (isl_stream_eat(s, ']'))
 638                 goto error;
 639
 640         obj = list->obj[i];
 641         obj.v = obj.type->copy(obj.v);
 642
 643         isl_list_free(list);
 644
 645         return obj;
 646 error:
 647         free_obj(obj);
 648         obj.type = isl_obj_none;
 649         obj.v = NULL;
 650         return obj;
 651 }
 652
 653 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
 654 {
 655         struct isl_token *tok;
 656
 657         if (isl_stream_eat_if_available(s, '+'))
 658                 return transitive_closure(s->ctx, obj);
 659
 660         tok = isl_stream_next_token(s);
 661         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
 662                 isl_stream_error(s, tok, "expecting -1");
 663                 if (tok)
 664                         isl_stream_push_token(s, tok);
 665                 goto error;
 666         }
 667         isl_token_free(tok);
 668         isl_assert(s->ctx, obj.type == isl_obj_map, goto error);
 669
 670         obj.v = isl_map_reverse(obj.v);
 671         if (!obj.v)
 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 read_obj(struct isl_stream *s,
 683         struct isl_hash_table *table)
 684 {
 685         struct isl_obj obj = { isl_obj_none, NULL };
 686         char *name = NULL;
 687         struct isc_un_op *op = NULL;
 688
 689         if (isl_stream_eat_if_available(s, '(')) {
 690                 obj = read_expr(s, table);
 691                 if (isl_stream_eat(s, ')'))
 692                         goto error;
 693         } else {
 694                 op = read_prefix_un_op_if_available(s);
 695                 if (op)
 696                         return read_un_op_expr(s, table, op);
 697
 698                 name = isl_stream_read_ident_if_available(s);
 699                 if (name) {
 700                         obj = stored_obj(s->ctx, table, name);
 701                 } else {
 702                         obj = isl_stream_read_obj(s);
 703                         assert(obj.v);
 704                 }
 705         }
 706
 707         if (isl_stream_eat_if_available(s, '^'))
 708                 obj = power(s, obj);
 709         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
 710                 obj = obj_at_index(s, obj);
 711
 712         return obj;
 713 error:
 714         free_obj(obj);
 715         obj.type = isl_obj_none;
 716         obj.v = NULL;
 717         return obj;
 718 }
 719
 720 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
 721         isl_obj_type lhs, isl_obj_type rhs)
 722 {
 723         int i;
 724
 725         for (i = 0; ; ++i) {
 726                 if (!bin_ops[i].op)
 727                         break;
 728                 if (bin_ops[i].op != like->op)
 729                         continue;
 730                 if (bin_ops[i].lhs != lhs)
 731                         continue;
 732                 if (bin_ops[i].rhs != rhs)
 733                         continue;
 734
 735                 return &bin_ops[i];
 736         }
 737
 738         for (i = 0; ; ++i) {
 739                 if (!named_bin_ops[i].name)
 740                         break;
 741                 if (named_bin_ops[i].op.op != like->op)
 742                         continue;
 743                 if (named_bin_ops[i].op.lhs != lhs)
 744                         continue;
 745                 if (named_bin_ops[i].op.rhs != rhs)
 746                         continue;
 747
 748                 return &named_bin_ops[i].op;
 749         }
 750
 751         return NULL;
 752 }
 753
 754 static struct isl_obj read_expr(struct isl_stream *s,
 755         struct isl_hash_table *table)
 756 {
 757         struct isl_obj obj = { isl_obj_none, NULL };
 758         struct isl_obj right_obj = { isl_obj_none, NULL };
 759
 760         obj = read_obj(s, table);
 761         for (;;) {
 762                 struct isc_bin_op *op = NULL;
 763
 764                 op = read_bin_op_if_available(s, obj.type);
 765                 if (!op)
 766                         break;
 767
 768                 right_obj = read_obj(s, table);
 769
 770                 op = find_matching_bin_op(op, obj.type, right_obj.type);
 771
 772                 isl_assert(s->ctx, op, goto error);
 773                 obj.v = op->fn(obj.v, right_obj.v);
 774                 obj.type = op->res;
 775         }
 776
 777         return obj;
 778 error:
 779         free_obj(right_obj);
 780         free_obj(obj);
 781         obj.type = isl_obj_none;
 782         obj.v = NULL;
 783         return obj;
 784 }
 785
 786 static __isl_give isl_printer *read_line(struct isl_stream *s,
 787         struct isl_hash_table *table, __isl_take isl_printer *p)
 788 {
 789         struct isl_obj obj = { isl_obj_none, NULL };
 790         char *lhs = NULL;
 791         int assign = 0;
 792         struct isc_bin_op *op = NULL;
 793
 794         if (!p)
 795                 return NULL;
 796         if (isl_stream_is_empty(s))
 797                 return p;
 798
 799         assign = is_assign(s);
 800         if (assign) {
 801                 lhs = isl_stream_read_ident_if_available(s);
 802                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
 803                         goto error;
 804         }
 805
 806         obj = read_expr(s, table);
 807         if (obj.type == isl_obj_none || obj.v == NULL)
 808                 goto error;
 809         if (isl_stream_eat(s, ';'))
 810                 goto error;
 811
 812         if (assign) {
 813                 if (do_assign(s->ctx, table, lhs, obj))
 814                         return;
 815         } else {
 816                 p = obj.type->print(p, obj.v);
 817                 p = isl_printer_end_line(p);
 818                 free_obj(obj);
 819         }
 820
 821         return p;
 822 error:
 823         free(lhs);
 824         free_obj(obj);
 825         return p;
 826 }
 827
 828 int free_cb(void *entry)
 829 {
 830         struct isl_named_obj *named = entry;
 831
 832         free_obj(named->obj);
 833         free(named->name);
 834         free(named);
 835
 836         return 0;
 837 }
 838
 839 static void register_named_ops(struct isl_stream *s)
 840 {
 841         int i;
 842
 843         for (i = 0; ; ++i) {
 844                 if (!named_un_ops[i].name)
 845                         break;
 846                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
 847                                                         named_un_ops[i].name);
 848                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
 849         }
 850
 851         for (i = 0; ; ++i) {
 852                 if (!named_bin_ops[i].name)
 853                         break;
 854                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
 855                                                         named_bin_ops[i].name);
 856                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
 857         }
 858 }
 859
 860 int main(int argc, char **argv)
 861 {
 862         struct isl_ctx *ctx;
 863         struct isl_stream *s;
 864         struct isl_hash_table *table;
 865         struct iscc_options *options;
 866         isl_printer *p;
 867
 868         options = iscc_options_new_with_defaults();
 869         assert(options);
 870         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
 871
 872         ctx = isl_ctx_alloc_with_options(options->isl);
 873         options->isl = NULL;
 874         s = isl_stream_new_file(ctx, stdin);
 875         assert(s);
 876         table = isl_hash_table_alloc(ctx, 10);
 877         assert(table);
 878         p = isl_printer_to_file(ctx, stdout);
 879         p = isl_printer_set_output_format(p, options->format);
 880         assert(p);
 881
 882         register_named_ops(s);
 883
 884         while (!s->eof) {
 885                 p = read_line(s, table, p);
 886         }
 887
 888         isl_printer_free(p);
 889         isl_hash_table_foreach(ctx, table, free_cb);
 890         isl_hash_table_free(ctx, table);
 891         isl_stream_free(s);
 892         isl_ctx_free(ctx);
 893         free(options);
 894
 895         return 0;
 896 }