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_vertices.h>
   7 #include <isl_obj_list.h>
   8 #include <barvinok/barvinok.h>
   9
  10 #include "config.h"
  11
  12 static int isl_bool_false = 0;
  13 static int isl_bool_true = 1;
  14 static int isl_bool_error = -1;
  15
  16 static enum isl_token_type read_op;
  17 static enum isl_token_type vertices_op;
  18
  19 struct isl_arg_choice iscc_format[] = {
  20         {"isl",         ISL_FORMAT_ISL},
  21         {"omega",       ISL_FORMAT_OMEGA},
  22         {"polylib",     ISL_FORMAT_POLYLIB},
  23         {"latex",       ISL_FORMAT_LATEX},
  24         {"C",           ISL_FORMAT_C},
  25         {0}
  26 };
  27
  28 struct iscc_options {
  29         struct barvinok_options *barvinok;
  30         unsigned                 format;
  31 };
  32
  33 struct isl_arg iscc_options_arg[] = {
  34 ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", barvinok_options_arg,
  35         "barvinok options")
  36 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
  37         iscc_format,    ISL_FORMAT_ISL, "output format")
  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 static __isl_give struct isl_list *pw_qpolynomial_upper_bound(
 335         __isl_take isl_pw_qpolynomial *pwqp)
 336 {
 337         isl_ctx *ctx;
 338         struct isl_list *list;
 339         int tight;
 340
 341         ctx = isl_pw_qpolynomial_get_ctx(pwqp);
 342         list = isl_list_alloc(ctx, 2);
 343         if (!list)
 344                 goto error;
 345
 346         list->obj[0].type = isl_obj_pw_qpolynomial_fold;
 347         list->obj[0].v = isl_pw_qpolynomial_bound(pwqp, isl_fold_max, &tight);
 348         list->obj[1].type = isl_obj_bool;
 349         list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
 350         if (tight < 0 || !list->obj[0].v)
 351                 goto error;
 352
 353         return list;
 354 error:
 355         isl_list_free(list);
 356         return NULL;
 357 }
 358
 359 typedef void *(*isc_un_op_fn)(void *arg);
 360 struct isc_un_op {
 361         enum isl_token_type     op;
 362         isl_obj_type            arg;
 363         isl_obj_type            res;
 364         isc_un_op_fn            fn;
 365 };
 366 struct isc_named_un_op {
 367         char                    *name;
 368         struct isc_un_op        op;
 369 };
 370 struct isc_named_un_op named_un_ops[] = {
 371         {"aff", { -1,   isl_obj_map,    isl_obj_map,
 372                 (isc_un_op_fn) &map_affine_hull } },
 373         {"aff", { -1,   isl_obj_set,    isl_obj_set,
 374                 (isc_un_op_fn) &set_affine_hull } },
 375         {"card",        { -1,   isl_obj_set,    isl_obj_pw_qpolynomial,
 376                 (isc_un_op_fn) &isl_set_card } },
 377         {"card",        { -1,   isl_obj_map,    isl_obj_pw_qpolynomial,
 378                 (isc_un_op_fn) &isl_map_card } },
 379         {"coalesce",    { -1,   isl_obj_set,    isl_obj_set,
 380                 (isc_un_op_fn) &isl_set_coalesce } },
 381         {"coalesce",    { -1,   isl_obj_map,    isl_obj_map,
 382                 (isc_un_op_fn) &isl_map_coalesce } },
 383         {"coalesce",    { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 384                 (isc_un_op_fn) &isl_pw_qpolynomial_coalesce } },
 385         {"coalesce",    { -1,   isl_obj_pw_qpolynomial_fold,
 386                 isl_obj_pw_qpolynomial_fold,
 387                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_coalesce } },
 388         {"deltas",      { -1,   isl_obj_map,    isl_obj_set,
 389                 (isc_un_op_fn) &isl_map_deltas } },
 390         {"dom", { -1,   isl_obj_map,    isl_obj_set,
 391                 (isc_un_op_fn) &isl_map_domain } },
 392         {"dom", { -1,   isl_obj_pw_qpolynomial, isl_obj_set,
 393                 (isc_un_op_fn) &isl_pw_qpolynomial_domain } },
 394         {"dom", { -1,   isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 395                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_domain } },
 396         {"ran", { -1,   isl_obj_map,    isl_obj_set,
 397                 (isc_un_op_fn) &isl_map_range } },
 398         {"lexmin",      { -1,   isl_obj_map,    isl_obj_map,
 399                 (isc_un_op_fn) &isl_map_lexmin } },
 400         {"lexmax",      { -1,   isl_obj_map,    isl_obj_map,
 401                 (isc_un_op_fn) &isl_map_lexmax } },
 402         {"lexmin",      { -1,   isl_obj_set,    isl_obj_set,
 403                 (isc_un_op_fn) &isl_set_lexmin } },
 404         {"lexmax",      { -1,   isl_obj_set,    isl_obj_set,
 405                 (isc_un_op_fn) &isl_set_lexmax } },
 406         {"sample",      { -1,   isl_obj_set,    isl_obj_set,
 407                 (isc_un_op_fn) &set_sample } },
 408         {"sample",      { -1,   isl_obj_map,    isl_obj_map,
 409                 (isc_un_op_fn) &map_sample } },
 410         {"sum",         { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 411                 (isc_un_op_fn) &isl_pw_qpolynomial_sum } },
 412         {"ub",          { -1,   isl_obj_pw_qpolynomial, isl_obj_list,
 413                 (isc_un_op_fn) &pw_qpolynomial_upper_bound } },
 414         NULL
 415 };
 416
 417 struct isl_named_obj {
 418         char            *name;
 419         struct isl_obj  obj;
 420 };
 421
 422 static void free_obj(struct isl_obj obj)
 423 {
 424         obj.type->free(obj.v);
 425 }
 426
 427 static int same_name(const void *entry, const void *val)
 428 {
 429         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 430
 431         return !strcmp(named->name, val);
 432 }
 433
 434 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 435         char *name, struct isl_obj obj)
 436 {
 437         struct isl_hash_table_entry *entry;
 438         uint32_t name_hash;
 439         struct isl_named_obj *named;
 440
 441         name_hash = isl_hash_string(isl_hash_init(), name);
 442         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 443         if (!entry)
 444                 goto error;
 445         if (entry->data) {
 446                 named = entry->data;
 447                 free_obj(named->obj);
 448                 free(name);
 449         } else {
 450                 named = isl_alloc_type(ctx, struct isl_named_obj);
 451                 if (!named)
 452                         goto error;
 453                 named->name = name;
 454                 entry->data = named;
 455         }
 456         named->obj = obj;
 457
 458         return 0;
 459 error:
 460         free_obj(obj);
 461         free(name);
 462         return -1;
 463 }
 464
 465 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 466         struct isl_hash_table *table, char *name)
 467 {
 468         struct isl_obj obj = { isl_obj_none, NULL };
 469         struct isl_hash_table_entry *entry;
 470         uint32_t name_hash;
 471
 472         name_hash = isl_hash_string(isl_hash_init(), name);
 473         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 474         if (entry) {
 475                 struct isl_named_obj *named;
 476                 named = entry->data;
 477                 obj = named->obj;
 478         }
 479
 480         free(name);
 481         obj.v = obj.type->copy(obj.v);
 482         return obj;
 483 }
 484
 485 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 486         isl_obj_type lhs)
 487 {
 488         int i;
 489         struct isl_token *tok;
 490
 491         tok = isl_stream_next_token(s);
 492         if (!tok)
 493                 return NULL;
 494
 495         for (i = 0; ; ++i) {
 496                 if (!bin_ops[i].op)
 497                         break;
 498                 if (bin_ops[i].op != tok->type)
 499                         continue;
 500                 if (bin_ops[i].lhs != lhs)
 501                         continue;
 502
 503                 isl_token_free(tok);
 504                 return &bin_ops[i];
 505         }
 506
 507         for (i = 0; ; ++i) {
 508                 if (!named_bin_ops[i].name)
 509                         break;
 510                 if (named_bin_ops[i].op.op != tok->type)
 511                         continue;
 512                 if (named_bin_ops[i].op.lhs != lhs)
 513                         continue;
 514
 515                 isl_token_free(tok);
 516                 return &named_bin_ops[i].op;
 517         }
 518
 519         isl_stream_push_token(s, tok);
 520
 521         return NULL;
 522 }
 523
 524 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 525 {
 526         int i;
 527         struct isl_token *tok;
 528
 529         tok = isl_stream_next_token(s);
 530         if (!tok)
 531                 return NULL;
 532
 533         for (i = 0; ; ++i) {
 534                 if (!named_un_ops[i].name)
 535                         break;
 536                 if (named_un_ops[i].op.op != tok->type)
 537                         continue;
 538
 539                 isl_token_free(tok);
 540                 return &named_un_ops[i].op;
 541         }
 542
 543         isl_stream_push_token(s, tok);
 544
 545         return NULL;
 546 }
 547
 548 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 549         isl_obj_type arg)
 550 {
 551         int i;
 552
 553         for (i = 0; ; ++i) {
 554                 if (!named_un_ops[i].name)
 555                         break;
 556                 if (named_un_ops[i].op.op != like->op)
 557                         continue;
 558                 if (named_un_ops[i].op.arg != arg)
 559                         continue;
 560
 561                 return &named_un_ops[i].op;
 562         }
 563
 564         return NULL;
 565 }
 566
 567 static int is_assign(struct isl_stream *s)
 568 {
 569         struct isl_token *tok;
 570         struct isl_token *tok2;
 571         int assign;
 572
 573         tok = isl_stream_next_token(s);
 574         if (!tok)
 575                 return 0;
 576         if (tok->type != ISL_TOKEN_IDENT) {
 577                 isl_stream_push_token(s, tok);
 578                 return 0;
 579         }
 580
 581         tok2 = isl_stream_next_token(s);
 582         if (!tok2) {
 583                 isl_stream_push_token(s, tok);
 584                 return 0;
 585         }
 586         assign = tok2->type == ISL_TOKEN_DEF;
 587         isl_stream_push_token(s, tok2);
 588         isl_stream_push_token(s, tok);
 589
 590         return assign;
 591 }
 592
 593 static struct isl_obj read_obj(struct isl_stream *s,
 594         struct isl_hash_table *table);
 595 static struct isl_obj read_expr(struct isl_stream *s,
 596         struct isl_hash_table *table);
 597
 598 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 599         struct isl_hash_table *table, struct isc_un_op *op)
 600 {
 601         struct isl_obj obj = { isl_obj_none, NULL };
 602
 603         obj = read_obj(s, table);
 604         if (!obj.v)
 605                 goto error;
 606
 607         op = find_matching_un_op(op, obj.type);
 608
 609         isl_assert(s->ctx, op, goto error);
 610         obj.v = op->fn(obj.v);
 611         obj.type = op->res;
 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 transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 622 {
 623         struct isl_list *list;
 624         int exact;
 625
 626         isl_assert(ctx, obj.type == isl_obj_map, goto error);
 627         list = isl_list_alloc(ctx, 2);
 628         if (!list)
 629                 goto error;
 630
 631         list->obj[0].type = isl_obj_map;
 632         list->obj[0].v = isl_map_transitive_closure(obj.v, &exact);
 633         list->obj[1].type = isl_obj_bool;
 634         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 635         obj.v = list;
 636         obj.type = isl_obj_list;
 637         if (exact < 0 || !list->obj[0].v)
 638                 goto error;
 639
 640         return obj;
 641 error:
 642         free_obj(obj);
 643         obj.type = isl_obj_none;
 644         obj.v = NULL;
 645         return obj;
 646 }
 647
 648 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 649 {
 650         struct isl_list *list = obj.v;
 651         struct isl_token *tok;
 652         int i;
 653
 654         tok = isl_stream_next_token(s);
 655         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 656                 isl_stream_error(s, tok, "expecting index");
 657                 if (tok)
 658                         isl_stream_push_token(s, tok);
 659                 goto error;
 660         }
 661         i = isl_int_get_si(tok->u.v);
 662         isl_token_free(tok);
 663         isl_assert(s->ctx, i < list->n, goto error);
 664         if (isl_stream_eat(s, ']'))
 665                 goto error;
 666
 667         obj = list->obj[i];
 668         obj.v = obj.type->copy(obj.v);
 669
 670         isl_list_free(list);
 671
 672         return obj;
 673 error:
 674         free_obj(obj);
 675         obj.type = isl_obj_none;
 676         obj.v = NULL;
 677         return obj;
 678 }
 679
 680 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_map *map,
 681         struct isl_hash_table *table)
 682 {
 683         struct isl_obj obj;
 684
 685         obj = read_expr(s, table);
 686         isl_assert(s->ctx, obj.type == isl_obj_set || obj.type == isl_obj_map,
 687                 goto error);
 688
 689         if (obj.type == isl_obj_set) {
 690                 obj.v = isl_set_apply(obj.v, map);
 691         } else
 692                 obj.v = isl_map_apply_range(obj.v, map);
 693         if (!obj.v)
 694                 goto error;
 695
 696         if (isl_stream_eat(s, ')'))
 697                 goto error;
 698
 699         return obj;
 700 error:
 701         free_obj(obj);
 702         obj.type = isl_obj_none;
 703         obj.v = NULL;
 704         return obj;
 705 }
 706
 707 struct add_vertex_data {
 708         struct isl_list *list;
 709         int i;
 710 };
 711
 712 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
 713 {
 714         struct add_vertex_data *data = (struct add_vertex_data *)user;
 715         isl_basic_set *expr;
 716
 717         expr = isl_vertex_get_expr(vertex);
 718
 719         data->list->obj[data->i].type = isl_obj_set;
 720         data->list->obj[data->i].v = isl_set_from_basic_set(expr);
 721         data->i++;
 722
 723         isl_vertex_free(vertex);
 724
 725         return 0;
 726 }
 727
 728 static struct isl_obj vertices(struct isl_stream *s,
 729         struct isl_hash_table *table)
 730 {
 731         isl_ctx *ctx;
 732         struct isl_obj obj;
 733         isl_set *set;
 734         isl_basic_set *hull;
 735         isl_vertices *vertices = NULL;
 736         struct isl_list *list = NULL;
 737         struct add_vertex_data data;
 738
 739         obj = read_expr(s, table);
 740         isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
 741         set = obj.v;
 742         obj.v = NULL;
 743         set = isl_set_remove_divs(set);
 744         hull = isl_set_convex_hull(set);
 745         vertices = isl_basic_set_compute_vertices(hull);
 746         isl_basic_set_free(hull);
 747
 748         ctx = isl_vertices_get_ctx(vertices);
 749         list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
 750         if (!list)
 751                 goto error;
 752
 753         data.list = list;
 754         data.i = 0;
 755
 756         if (isl_vertices_foreach_vertex(vertices, &add_vertex, &data) < 0)
 757                 goto error;
 758
 759         isl_vertices_free(vertices);
 760
 761         obj.type = isl_obj_list;
 762         obj.v = list;
 763
 764         return obj;
 765 error:
 766         isl_vertices_free(vertices);
 767         isl_list_free(list);
 768         free_obj(obj);
 769         obj.type = isl_obj_none;
 770         obj.v = NULL;
 771         return obj;
 772 }
 773
 774 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
 775 {
 776         struct isl_token *tok;
 777
 778         if (isl_stream_eat_if_available(s, '+'))
 779                 return transitive_closure(s->ctx, obj);
 780
 781         tok = isl_stream_next_token(s);
 782         if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
 783                 isl_stream_error(s, tok, "expecting -1");
 784                 if (tok)
 785                         isl_stream_push_token(s, tok);
 786                 goto error;
 787         }
 788         isl_token_free(tok);
 789         isl_assert(s->ctx, obj.type == isl_obj_map, goto error);
 790
 791         obj.v = isl_map_reverse(obj.v);
 792         if (!obj.v)
 793                 goto error;
 794
 795         return obj;
 796 error:
 797         free_obj(obj);
 798         obj.type = isl_obj_none;
 799         obj.v = NULL;
 800         return obj;
 801 }
 802
 803 static struct isl_obj read_from_file(struct isl_stream *s)
 804 {
 805         struct isl_obj obj;
 806         struct isl_token *tok;
 807         struct isl_stream *s_file;
 808         FILE *file;
 809
 810         tok = isl_stream_next_token(s);
 811         if (!tok || tok->type != ISL_TOKEN_STRING) {
 812                 isl_stream_error(s, tok, "expecting filename");
 813                 isl_token_free(tok);
 814                 goto error;
 815         }
 816
 817         file = fopen(tok->u.s, "r");
 818         isl_token_free(tok);
 819         isl_assert(s->ctx, file, goto error);
 820
 821         s_file = isl_stream_new_file(s->ctx, file);
 822         if (!s_file) {
 823                 fclose(file);
 824                 goto error;
 825         }
 826
 827         obj = isl_stream_read_obj(s_file);
 828
 829         isl_stream_free(s_file);
 830         fclose(file);
 831
 832         return obj;
 833 error:
 834         obj.type = isl_obj_none;
 835         obj.v = NULL;
 836         return obj;
 837 }
 838
 839 static struct isl_obj read_obj(struct isl_stream *s,
 840         struct isl_hash_table *table)
 841 {
 842         struct isl_obj obj = { isl_obj_none, NULL };
 843         char *name = NULL;
 844         struct isc_un_op *op = NULL;
 845
 846         if (isl_stream_eat_if_available(s, '(')) {
 847                 obj = read_expr(s, table);
 848                 if (!obj.v || isl_stream_eat(s, ')'))
 849                         goto error;
 850         } else {
 851                 op = read_prefix_un_op_if_available(s);
 852                 if (op)
 853                         return read_un_op_expr(s, table, op);
 854
 855                 if (isl_stream_eat_if_available(s, read_op))
 856                         return read_from_file(s);
 857                 if (isl_stream_eat_if_available(s, vertices_op))
 858                         return vertices(s, table);
 859
 860                 name = isl_stream_read_ident_if_available(s);
 861                 if (name)
 862                         obj = stored_obj(s->ctx, table, name);
 863                 else
 864                         obj = isl_stream_read_obj(s);
 865                 if (!obj.v)
 866                         goto error;
 867         }
 868
 869         if (isl_stream_eat_if_available(s, '^'))
 870                 obj = power(s, obj);
 871         else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
 872                 obj = obj_at_index(s, obj);
 873         else if (obj.type == isl_obj_map && isl_stream_eat_if_available(s, '('))
 874                 obj = apply(s, obj.v, table);
 875
 876         return obj;
 877 error:
 878         free_obj(obj);
 879         obj.type = isl_obj_none;
 880         obj.v = NULL;
 881         return obj;
 882 }
 883
 884 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
 885         isl_obj_type lhs, isl_obj_type rhs)
 886 {
 887         int i;
 888
 889         for (i = 0; ; ++i) {
 890                 if (!bin_ops[i].op)
 891                         break;
 892                 if (bin_ops[i].op != like->op)
 893                         continue;
 894                 if (bin_ops[i].lhs != lhs)
 895                         continue;
 896                 if (bin_ops[i].rhs != rhs)
 897                         continue;
 898
 899                 return &bin_ops[i];
 900         }
 901
 902         for (i = 0; ; ++i) {
 903                 if (!named_bin_ops[i].name)
 904                         break;
 905                 if (named_bin_ops[i].op.op != like->op)
 906                         continue;
 907                 if (named_bin_ops[i].op.lhs != lhs)
 908                         continue;
 909                 if (named_bin_ops[i].op.rhs != rhs)
 910                         continue;
 911
 912                 return &named_bin_ops[i].op;
 913         }
 914
 915         return NULL;
 916 }
 917
 918 static struct isl_obj read_expr(struct isl_stream *s,
 919         struct isl_hash_table *table)
 920 {
 921         struct isl_obj obj = { isl_obj_none, NULL };
 922         struct isl_obj right_obj = { isl_obj_none, NULL };
 923
 924         obj = read_obj(s, table);
 925         for (; obj.v;) {
 926                 struct isc_bin_op *op = NULL;
 927
 928                 op = read_bin_op_if_available(s, obj.type);
 929                 if (!op)
 930                         break;
 931
 932                 right_obj = read_obj(s, table);
 933
 934                 op = find_matching_bin_op(op, obj.type, right_obj.type);
 935
 936                 isl_assert(s->ctx, op, goto error);
 937                 obj.v = op->fn(obj.v, right_obj.v);
 938                 obj.type = op->res;
 939         }
 940
 941         return obj;
 942 error:
 943         free_obj(right_obj);
 944         free_obj(obj);
 945         obj.type = isl_obj_none;
 946         obj.v = NULL;
 947         return obj;
 948 }
 949
 950 static __isl_give isl_printer *read_line(struct isl_stream *s,
 951         struct isl_hash_table *table, __isl_take isl_printer *p)
 952 {
 953         struct isl_obj obj = { isl_obj_none, NULL };
 954         char *lhs = NULL;
 955         int assign = 0;
 956         struct isc_bin_op *op = NULL;
 957
 958         if (!p)
 959                 return NULL;
 960         if (isl_stream_is_empty(s))
 961                 return p;
 962
 963         assign = is_assign(s);
 964         if (assign) {
 965                 lhs = isl_stream_read_ident_if_available(s);
 966                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
 967                         goto error;
 968         }
 969
 970         obj = read_expr(s, table);
 971         if (obj.type == isl_obj_none || obj.v == NULL)
 972                 goto error;
 973         if (isl_stream_eat(s, ';'))
 974                 goto error;
 975
 976         if (assign) {
 977                 if (do_assign(s->ctx, table, lhs, obj))
 978                         return;
 979         } else {
 980                 p = obj.type->print(p, obj.v);
 981                 p = isl_printer_end_line(p);
 982                 free_obj(obj);
 983         }
 984
 985         return p;
 986 error:
 987         isl_stream_flush_tokens(s);
 988         isl_stream_skip_line(s);
 989         free(lhs);
 990         free_obj(obj);
 991         return p;
 992 }
 993
 994 int free_cb(void **entry, void *user)
 995 {
 996         struct isl_named_obj *named = *entry;
 997
 998         free_obj(named->obj);
 999         free(named->name);
1000         free(named);
1001
1002         return 0;
1003 }
1004
1005 static void register_named_ops(struct isl_stream *s)
1006 {
1007         int i;
1008
1009         read_op = isl_stream_register_keyword(s, "read");
1010         assert(read_op != ISL_TOKEN_ERROR);
1011         vertices_op = isl_stream_register_keyword(s, "vertices");
1012         assert(vertices_op != ISL_TOKEN_ERROR);
1013
1014         for (i = 0; ; ++i) {
1015                 if (!named_un_ops[i].name)
1016                         break;
1017                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
1018                                                         named_un_ops[i].name);
1019                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
1020         }
1021
1022         for (i = 0; ; ++i) {
1023                 if (!named_bin_ops[i].name)
1024                         break;
1025                 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
1026                                                         named_bin_ops[i].name);
1027                 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
1028         }
1029 }
1030
1031 int main(int argc, char **argv)
1032 {
1033         struct isl_ctx *ctx;
1034         struct isl_stream *s;
1035         struct isl_hash_table *table;
1036         struct iscc_options *options;
1037         isl_printer *p;
1038
1039         options = iscc_options_new_with_defaults();
1040         assert(options);
1041         argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
1042
1043         ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
1044         s = isl_stream_new_file(ctx, stdin);
1045         assert(s);
1046         table = isl_hash_table_alloc(ctx, 10);
1047         assert(table);
1048         p = isl_printer_to_file(ctx, stdout);
1049         p = isl_printer_set_output_format(p, options->format);
1050         assert(p);
1051
1052         register_named_ops(s);
1053
1054         while (!s->eof) {
1055                 p = read_line(s, table, p);
1056         }
1057
1058         isl_printer_free(p);
1059         isl_hash_table_foreach(ctx, table, free_cb, NULL);
1060         isl_hash_table_free(ctx, table);
1061         isl_stream_free(s);
1062         isl_ctx_free(ctx);
1063
1064         return 0;
1065 }