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