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 void isl_obj_bool_print(void *v, FILE *out)
  28 {
  29         if (v == &isl_bool_true)
  30                 fprintf(out, "True");
  31         else if (v == &isl_bool_false)
  32                 fprintf(out, "False");
  33         else
  34                 fprintf(out, "Error");
  35 }
  36
  37 static void *isl_obj_bool_add(void *v1, void *v2)
  38 {
  39         return v1;
  40 }
  41
  42 struct isl_obj_vtable isl_obj_bool_vtable = {
  43         isl_obj_bool_copy,
  44         isl_obj_bool_add,
  45         isl_obj_bool_print,
  46         isl_obj_bool_free
  47 };
  48 #define isl_obj_bool            (&isl_obj_bool_vtable)
  49
  50 extern struct isl_obj_vtable isl_obj_list_vtable;
  51 #define isl_obj_list            (&isl_obj_list_vtable)
  52
  53 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
  54 struct isc_bin_op {
  55         enum isl_token_type     op;
  56         isl_obj_type            lhs;
  57         isl_obj_type            rhs;
  58         isl_obj_type            res;
  59         isc_bin_op_fn           fn;
  60 };
  61
  62 struct iscc_at {
  63         isl_pw_qpolynomial *pwqp;
  64         isl_pw_qpolynomial *res;
  65 };
  66
  67 static int eval_at(__isl_take isl_point *pnt, void *user)
  68 {
  69         struct iscc_at *at = (struct iscc_at *) user;
  70         isl_qpolynomial *qp;
  71         isl_set *set;
  72
  73         set = isl_set_from_point(isl_point_copy(pnt));
  74         qp = isl_pw_qpolynomial_eval(isl_pw_qpolynomial_copy(at->pwqp), pnt);
  75
  76         at->res = isl_pw_qpolynomial_add_disjoint(at->res,
  77                         isl_pw_qpolynomial_alloc(set, qp));
  78
  79         return 0;
  80 }
  81
  82 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_at(
  83         __isl_take isl_pw_qpolynomial *pwqp, __isl_take isl_set *set)
  84 {
  85         struct iscc_at at;
  86
  87         at.pwqp = pwqp;
  88         at.res = isl_pw_qpolynomial_zero(isl_set_get_dim(set));
  89
  90         isl_set_foreach_point(set, eval_at, &at);
  91
  92         isl_pw_qpolynomial_free(pwqp);
  93         isl_set_free(set);
  94
  95         return at.res;
  96 }
  97
  98 struct iscc_fold_at {
  99         isl_pw_qpolynomial_fold *pwf;
 100         isl_pw_qpolynomial *res;
 101 };
 102
 103 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
 104 {
 105         struct iscc_fold_at *at = (struct iscc_fold_at *) user;
 106         isl_qpolynomial *qp;
 107         isl_set *set;
 108
 109         set = isl_set_from_point(isl_point_copy(pnt));
 110         qp = isl_pw_qpolynomial_fold_eval(isl_pw_qpolynomial_fold_copy(at->pwf),
 111                                                 pnt);
 112
 113         at->res = isl_pw_qpolynomial_add_disjoint(at->res,
 114                         isl_pw_qpolynomial_alloc(set, qp));
 115
 116         return 0;
 117 }
 118
 119 __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_fold_at(
 120         __isl_take isl_pw_qpolynomial_fold *pwf, __isl_take isl_set *set)
 121 {
 122         struct iscc_fold_at at;
 123
 124         at.pwf = pwf;
 125         at.res = isl_pw_qpolynomial_zero(isl_set_get_dim(set));
 126
 127         isl_set_foreach_point(set, eval_fold_at, &at);
 128
 129         isl_pw_qpolynomial_fold_free(pwf);
 130         isl_set_free(set);
 131
 132         return at.res;
 133 }
 134
 135 struct isc_bin_op bin_ops[] = {
 136         { '+',  isl_obj_set,    isl_obj_set,
 137                 isl_obj_set,
 138                 (isc_bin_op_fn) &isl_set_union },
 139         { '+',  isl_obj_map,    isl_obj_map,
 140                 isl_obj_map,
 141                 (isc_bin_op_fn) &isl_map_union },
 142         { '-',  isl_obj_set,    isl_obj_set,
 143                 isl_obj_set,
 144                 (isc_bin_op_fn) &isl_set_subtract },
 145         { '-',  isl_obj_map,    isl_obj_map,
 146                 isl_obj_map,
 147                 (isc_bin_op_fn) &isl_map_subtract },
 148         { '*',  isl_obj_set,    isl_obj_set,
 149                 isl_obj_set,
 150                 (isc_bin_op_fn) &isl_set_intersect },
 151         { '*',  isl_obj_map,    isl_obj_map,
 152                 isl_obj_map,
 153                 (isc_bin_op_fn) &isl_map_intersect },
 154         { '+',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 155                 isl_obj_pw_qpolynomial,
 156                 (isc_bin_op_fn) &isl_pw_qpolynomial_add },
 157         { '-',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 158                 isl_obj_pw_qpolynomial,
 159                 (isc_bin_op_fn) &isl_pw_qpolynomial_sub },
 160         { '*',  isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 161                 isl_obj_pw_qpolynomial,
 162                 (isc_bin_op_fn) &isl_pw_qpolynomial_mul },
 163         { '@',  isl_obj_pw_qpolynomial, isl_obj_set,
 164                 isl_obj_pw_qpolynomial,
 165                 (isc_bin_op_fn) &isl_pw_qpolynomial_at },
 166         { '@',  isl_obj_pw_qpolynomial_fold, isl_obj_set,
 167                 isl_obj_pw_qpolynomial,
 168                 (isc_bin_op_fn) &isl_pw_qpolynomial_fold_at },
 169         0
 170 };
 171
 172 __isl_give isl_set *set_sample(__isl_take isl_set *set)
 173 {
 174         return isl_set_from_basic_set(isl_set_sample(set));
 175 }
 176
 177 __isl_give isl_map *map_sample(__isl_take isl_map *map)
 178 {
 179         return isl_map_from_basic_map(isl_map_sample(map));
 180 }
 181
 182 typedef void *(*isc_un_op_fn)(void *arg);
 183 struct isc_un_op {
 184         enum isl_token_type     op;
 185         isl_obj_type            arg;
 186         isl_obj_type            res;
 187         isc_un_op_fn            fn;
 188 };
 189 struct isc_named_un_op {
 190         char                    *name;
 191         struct isc_un_op        op;
 192 };
 193 struct isc_named_un_op named_un_ops[] = {
 194         {"card",        { -1,   isl_obj_set,    isl_obj_pw_qpolynomial,
 195                 (isc_un_op_fn) &isl_set_card } },
 196         {"card",        { -1,   isl_obj_map,    isl_obj_pw_qpolynomial,
 197                 (isc_un_op_fn) &isl_map_card } },
 198         {"dom", { -1,   isl_obj_map,    isl_obj_set,
 199                 (isc_un_op_fn) &isl_map_domain } },
 200         {"ran", { -1,   isl_obj_map,    isl_obj_set,
 201                 (isc_un_op_fn) &isl_map_range } },
 202         {"lexmin",      { -1,   isl_obj_map,    isl_obj_map,
 203                 (isc_un_op_fn) &isl_map_lexmin } },
 204         {"lexmax",      { -1,   isl_obj_map,    isl_obj_map,
 205                 (isc_un_op_fn) &isl_map_lexmax } },
 206         {"lexmin",      { -1,   isl_obj_set,    isl_obj_set,
 207                 (isc_un_op_fn) &isl_set_lexmin } },
 208         {"lexmax",      { -1,   isl_obj_set,    isl_obj_set,
 209                 (isc_un_op_fn) &isl_set_lexmax } },
 210         {"sample",      { -1,   isl_obj_set,    isl_obj_set,
 211                 (isc_un_op_fn) &set_sample } },
 212         {"sample",      { -1,   isl_obj_map,    isl_obj_map,
 213                 (isc_un_op_fn) &map_sample } },
 214         {"sum",         { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 215                 (isc_un_op_fn) &isl_pw_qpolynomial_sum } },
 216 #ifdef HAVE_GINAC
 217         {"ub",          { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial_fold,
 218                 (isc_un_op_fn) &isl_pw_qpolynomial_upper_bound } },
 219 #endif
 220         NULL
 221 };
 222
 223 struct isl_named_obj {
 224         char            *name;
 225         struct isl_obj  obj;
 226 };
 227
 228 static void free_obj(struct isl_obj obj)
 229 {
 230         obj.type->free(obj.v);
 231 }
 232
 233 static int same_name(const void *entry, const void *val)
 234 {
 235         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 236
 237         return !strcmp(named->name, val);
 238 }
 239
 240 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 241         char *name, struct isl_obj obj)
 242 {
 243         struct isl_hash_table_entry *entry;
 244         uint32_t name_hash;
 245         struct isl_named_obj *named;
 246
 247         name_hash = isl_hash_string(isl_hash_init(), name);
 248         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 249         if (!entry)
 250                 goto error;
 251         if (entry->data) {
 252                 named = entry->data;
 253                 free_obj(named->obj);
 254                 free(name);
 255         } else {
 256                 named = isl_alloc_type(ctx, struct isl_named_obj);
 257                 if (!named)
 258                         goto error;
 259                 named->name = name;
 260                 entry->data = named;
 261         }
 262         named->obj = obj;
 263
 264         return 0;
 265 error:
 266         free_obj(obj);
 267         free(name);
 268         return -1;
 269 }
 270
 271 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 272         struct isl_hash_table *table, char *name)
 273 {
 274         struct isl_obj obj = { isl_obj_none, NULL };
 275         struct isl_hash_table_entry *entry;
 276         uint32_t name_hash;
 277
 278         name_hash = isl_hash_string(isl_hash_init(), name);
 279         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 280         if (entry) {
 281                 struct isl_named_obj *named;
 282                 named = entry->data;
 283                 obj = named->obj;
 284         }
 285
 286         free(name);
 287         obj.v = obj.type->copy(obj.v);
 288         return obj;
 289 }
 290
 291 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 292         isl_obj_type lhs)
 293 {
 294         int i;
 295         struct isl_token *tok;
 296
 297         tok = isl_stream_next_token(s);
 298         if (!tok)
 299                 return NULL;
 300
 301         for (i = 0; ; ++i) {
 302                 if (!bin_ops[i].op)
 303                         break;
 304                 if (bin_ops[i].op != tok->type)
 305                         continue;
 306                 if (bin_ops[i].lhs != lhs)
 307                         continue;
 308
 309                 isl_token_free(tok);
 310                 return &bin_ops[i];
 311         }
 312
 313         isl_stream_push_token(s, tok);
 314
 315         return NULL;
 316 }
 317
 318 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 319 {
 320         int i;
 321         struct isl_token *tok;
 322
 323         tok = isl_stream_next_token(s);
 324         if (!tok)
 325                 return NULL;
 326
 327         for (i = 0; ; ++i) {
 328                 if (!named_un_ops[i].op.op)
 329                         break;
 330                 if (named_un_ops[i].op.op != tok->type)
 331                         continue;
 332
 333                 isl_token_free(tok);
 334                 return &named_un_ops[i].op;
 335         }
 336
 337         isl_stream_push_token(s, tok);
 338
 339         return NULL;
 340 }
 341
 342 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 343         isl_obj_type arg)
 344 {
 345         int i;
 346
 347         for (i = 0; ; ++i) {
 348                 if (!named_un_ops[i].op.op)
 349                         break;
 350                 if (named_un_ops[i].op.op != like->op)
 351                         continue;
 352                 if (named_un_ops[i].op.arg != arg)
 353                         continue;
 354
 355                 return &named_un_ops[i].op;
 356         }
 357
 358         return NULL;
 359 }
 360
 361 static int is_assign(struct isl_stream *s)
 362 {
 363         struct isl_token *tok;
 364         struct isl_token *tok2;
 365         int assign;
 366
 367         tok = isl_stream_next_token(s);
 368         if (!tok)
 369                 return 0;
 370         if (tok->type != ISL_TOKEN_IDENT) {
 371                 isl_stream_push_token(s, tok);
 372                 return 0;
 373         }
 374
 375         tok2 = isl_stream_next_token(s);
 376         if (!tok2) {
 377                 isl_stream_push_token(s, tok);
 378                 return 0;
 379         }
 380         assign = tok2->type == ISL_TOKEN_DEF;
 381         isl_stream_push_token(s, tok2);
 382         isl_stream_push_token(s, tok);
 383
 384         return assign;
 385 }
 386
 387 static struct isl_obj read_obj(struct isl_stream *s,
 388         struct isl_hash_table *table);
 389 static struct isl_obj read_expr(struct isl_stream *s,
 390         struct isl_hash_table *table);
 391
 392 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 393         struct isl_hash_table *table, struct isc_un_op *op)
 394 {
 395         struct isl_obj obj = { isl_obj_none, NULL };
 396
 397         obj = read_obj(s, table);
 398
 399         op = find_matching_un_op(op, obj.type);
 400
 401         isl_assert(s->ctx, op, goto error);
 402         obj.v = op->fn(obj.v);
 403         obj.type = op->res;
 404
 405         return obj;
 406 error:
 407         free_obj(obj);
 408         obj.type = isl_obj_none;
 409         obj.v = NULL;
 410         return obj;
 411 }
 412
 413 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 414 {
 415         struct isl_list *list;
 416         int exact;
 417
 418         isl_assert(ctx, obj.type == isl_obj_map, goto error);
 419         list = isl_list_alloc(ctx, 2);
 420         if (!list)
 421                 goto error;
 422
 423         list->obj[0].type = isl_obj_map;
 424         list->obj[0].v = isl_map_transitive_closure(obj.v, &exact);
 425         list->obj[1].type = isl_obj_bool;
 426         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 427         obj.v = list;
 428         obj.type = isl_obj_list;
 429         if (exact < 0 || !list->obj[0].v)
 430                 goto error;
 431
 432         return obj;
 433 error:
 434         free_obj(obj);
 435         obj.type = isl_obj_none;
 436         obj.v = NULL;
 437         return obj;
 438 }
 439
 440 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 441 {
 442         struct isl_list *list = obj.v;
 443         struct isl_token *tok;
 444         int i;
 445
 446         tok = isl_stream_next_token(s);
 447         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 448                 isl_stream_error(s, tok, "expecting index");
 449                 if (tok)
 450                         isl_stream_push_token(s, tok);
 451                 goto error;
 452         }
 453         i = isl_int_get_si(tok->u.v);
 454         isl_token_free(tok);
 455         isl_assert(s, i < list->n, goto error);
 456         if (isl_stream_eat(s, ']'))
 457                 goto error;
 458
 459         obj = list->obj[i];
 460         obj.v = obj.type->copy(obj.v);
 461
 462         isl_list_free(list);
 463
 464         return obj;
 465 error:
 466         free_obj(obj);
 467         obj.type = isl_obj_none;
 468         obj.v = NULL;
 469         return obj;
 470 }
 471
 472 static struct isl_obj read_obj(struct isl_stream *s,
 473         struct isl_hash_table *table)
 474 {
 475         struct isl_obj obj = { isl_obj_none, NULL };
 476         char *name = NULL;
 477         struct isc_un_op *op = NULL;
 478
 479         if (isl_stream_eat_if_available(s, '(')) {
 480                 obj = read_expr(s, table);
 481                 if (isl_stream_eat(s, ')'))
 482                         goto error;
 483         } else {
 484                 op = read_prefix_un_op_if_available(s);
 485                 if (op)
 486                         return read_un_op_expr(s, table, op);
 487
 488                 name = isl_stream_read_ident_if_available(s);
 489                 if (name) {
 490                         obj = stored_obj(s->ctx, table, name);
 491                 } else {
 492                         obj = isl_stream_read_obj(s);
 493                         assert(obj.v);
 494                 }
 495         }
 496
 497         if (isl_stream_eat_if_available(s, '^')) {
 498                 if (isl_stream_eat(s, '+'))
 499                         goto error;
 500                 obj = transitive_closure(s->ctx, obj);
 501         } else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
 502                 obj = obj_at_index(s, obj);
 503
 504         return obj;
 505 error:
 506         free_obj(obj);
 507         obj.type = isl_obj_none;
 508         obj.v = NULL;
 509         return obj;
 510 }
 511
 512 static struct isl_obj read_expr(struct isl_stream *s,
 513         struct isl_hash_table *table)
 514 {
 515         struct isl_obj obj = { isl_obj_none, NULL };
 516         struct isl_obj right_obj = { isl_obj_none, NULL };
 517
 518         obj = read_obj(s, table);
 519         for (;;) {
 520                 struct isc_bin_op *op = NULL;
 521
 522                 op = read_bin_op_if_available(s, obj.type);
 523                 if (!op)
 524                         break;
 525
 526                 right_obj = read_obj(s, table);
 527
 528                 isl_assert(s->ctx, right_obj.type == op->rhs, goto error);
 529                 obj.v = op->fn(obj.v, right_obj.v);
 530                 obj.type = op->res;
 531         }
 532
 533         return obj;
 534 error:
 535         free_obj(right_obj);
 536         free_obj(obj);
 537         obj.type = isl_obj_none;
 538         obj.v = NULL;
 539         return obj;
 540 }
 541
 542 static void read_line(struct isl_stream *s, struct isl_hash_table *table)
 543 {
 544         struct isl_obj obj = { isl_obj_none, NULL };
 545         char *lhs = NULL;
 546         int assign = 0;
 547         struct isc_bin_op *op = NULL;
 548
 549         if (isl_stream_is_empty(s))
 550                 return;
 551
 552         assign = is_assign(s);
 553         if (assign) {
 554                 lhs = isl_stream_read_ident_if_available(s);
 555                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
 556                         goto error;
 557         }
 558
 559         obj = read_expr(s, table);
 560         if (obj.type == isl_obj_none || obj.v == NULL)
 561                 goto error;
 562         if (isl_stream_eat(s, ';'))
 563                 goto error;
 564
 565         if (assign) {
 566                 if (do_assign(s->ctx, table, lhs, obj))
 567                         return;
 568         } else {
 569                 obj.type->print(obj.v, stdout);
 570                 printf("\n");
 571                 free_obj(obj);
 572         }
 573
 574         return;
 575 error:
 576         free(lhs);
 577         free_obj(obj);
 578 }
 579
 580 int free_cb(void *entry)
 581 {
 582         struct isl_named_obj *named = entry;
 583
 584         free_obj(named->obj);
 585         free(named->name);
 586         free(named);
 587
 588         return 0;
 589 }
 590
 591 static void register_named_ops(struct isl_stream *s)
 592 {
 593         int i;
 594
 595         for (i = 0; ; ++i) {
 596                 if (!named_un_ops[i].name)
 597                         break;
 598                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
 599                                                         named_un_ops[i].name);
 600                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
 601         }
 602 }
 603
 604 int main(int argc, char **argv)
 605 {
 606         struct isl_ctx *ctx;
 607         struct isl_stream *s;
 608         struct isl_hash_table *table;
 609
 610         ctx = isl_ctx_alloc();
 611         s = isl_stream_new_file(ctx, stdin);
 612         assert(s);
 613         table = isl_hash_table_alloc(ctx, 10);
 614         assert(table);
 615
 616         register_named_ops(s);
 617
 618         while (!feof(stdin)) {
 619                 read_line(s, table);
 620         }
 621
 622         isl_hash_table_foreach(ctx, table, free_cb);
 623         isl_hash_table_free(ctx, table);
 624         isl_stream_free(s);
 625         isl_ctx_free(ctx);
 626
 627         return 0;
 628 }