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