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         {"dom", { -1,   isl_obj_pw_qpolynomial, isl_obj_set,
 201                 (isc_un_op_fn) &isl_pw_qpolynomial_domain } },
 202         {"dom", { -1,   isl_obj_pw_qpolynomial_fold,    isl_obj_set,
 203                 (isc_un_op_fn) &isl_pw_qpolynomial_fold_domain } },
 204         {"ran", { -1,   isl_obj_map,    isl_obj_set,
 205                 (isc_un_op_fn) &isl_map_range } },
 206         {"lexmin",      { -1,   isl_obj_map,    isl_obj_map,
 207                 (isc_un_op_fn) &isl_map_lexmin } },
 208         {"lexmax",      { -1,   isl_obj_map,    isl_obj_map,
 209                 (isc_un_op_fn) &isl_map_lexmax } },
 210         {"lexmin",      { -1,   isl_obj_set,    isl_obj_set,
 211                 (isc_un_op_fn) &isl_set_lexmin } },
 212         {"lexmax",      { -1,   isl_obj_set,    isl_obj_set,
 213                 (isc_un_op_fn) &isl_set_lexmax } },
 214         {"sample",      { -1,   isl_obj_set,    isl_obj_set,
 215                 (isc_un_op_fn) &set_sample } },
 216         {"sample",      { -1,   isl_obj_map,    isl_obj_map,
 217                 (isc_un_op_fn) &map_sample } },
 218         {"sum",         { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial,
 219                 (isc_un_op_fn) &isl_pw_qpolynomial_sum } },
 220 #ifdef HAVE_GINAC
 221         {"ub",          { -1,   isl_obj_pw_qpolynomial, isl_obj_pw_qpolynomial_fold,
 222                 (isc_un_op_fn) &isl_pw_qpolynomial_upper_bound } },
 223 #endif
 224         NULL
 225 };
 226
 227 struct isl_named_obj {
 228         char            *name;
 229         struct isl_obj  obj;
 230 };
 231
 232 static void free_obj(struct isl_obj obj)
 233 {
 234         obj.type->free(obj.v);
 235 }
 236
 237 static int same_name(const void *entry, const void *val)
 238 {
 239         const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
 240
 241         return !strcmp(named->name, val);
 242 }
 243
 244 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
 245         char *name, struct isl_obj obj)
 246 {
 247         struct isl_hash_table_entry *entry;
 248         uint32_t name_hash;
 249         struct isl_named_obj *named;
 250
 251         name_hash = isl_hash_string(isl_hash_init(), name);
 252         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
 253         if (!entry)
 254                 goto error;
 255         if (entry->data) {
 256                 named = entry->data;
 257                 free_obj(named->obj);
 258                 free(name);
 259         } else {
 260                 named = isl_alloc_type(ctx, struct isl_named_obj);
 261                 if (!named)
 262                         goto error;
 263                 named->name = name;
 264                 entry->data = named;
 265         }
 266         named->obj = obj;
 267
 268         return 0;
 269 error:
 270         free_obj(obj);
 271         free(name);
 272         return -1;
 273 }
 274
 275 static struct isl_obj stored_obj(struct isl_ctx *ctx,
 276         struct isl_hash_table *table, char *name)
 277 {
 278         struct isl_obj obj = { isl_obj_none, NULL };
 279         struct isl_hash_table_entry *entry;
 280         uint32_t name_hash;
 281
 282         name_hash = isl_hash_string(isl_hash_init(), name);
 283         entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
 284         if (entry) {
 285                 struct isl_named_obj *named;
 286                 named = entry->data;
 287                 obj = named->obj;
 288         }
 289
 290         free(name);
 291         obj.v = obj.type->copy(obj.v);
 292         return obj;
 293 }
 294
 295 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
 296         isl_obj_type lhs)
 297 {
 298         int i;
 299         struct isl_token *tok;
 300
 301         tok = isl_stream_next_token(s);
 302         if (!tok)
 303                 return NULL;
 304
 305         for (i = 0; ; ++i) {
 306                 if (!bin_ops[i].op)
 307                         break;
 308                 if (bin_ops[i].op != tok->type)
 309                         continue;
 310                 if (bin_ops[i].lhs != lhs)
 311                         continue;
 312
 313                 isl_token_free(tok);
 314                 return &bin_ops[i];
 315         }
 316
 317         isl_stream_push_token(s, tok);
 318
 319         return NULL;
 320 }
 321
 322 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
 323 {
 324         int i;
 325         struct isl_token *tok;
 326
 327         tok = isl_stream_next_token(s);
 328         if (!tok)
 329                 return NULL;
 330
 331         for (i = 0; ; ++i) {
 332                 if (!named_un_ops[i].op.op)
 333                         break;
 334                 if (named_un_ops[i].op.op != tok->type)
 335                         continue;
 336
 337                 isl_token_free(tok);
 338                 return &named_un_ops[i].op;
 339         }
 340
 341         isl_stream_push_token(s, tok);
 342
 343         return NULL;
 344 }
 345
 346 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
 347         isl_obj_type arg)
 348 {
 349         int i;
 350
 351         for (i = 0; ; ++i) {
 352                 if (!named_un_ops[i].op.op)
 353                         break;
 354                 if (named_un_ops[i].op.op != like->op)
 355                         continue;
 356                 if (named_un_ops[i].op.arg != arg)
 357                         continue;
 358
 359                 return &named_un_ops[i].op;
 360         }
 361
 362         return NULL;
 363 }
 364
 365 static int is_assign(struct isl_stream *s)
 366 {
 367         struct isl_token *tok;
 368         struct isl_token *tok2;
 369         int assign;
 370
 371         tok = isl_stream_next_token(s);
 372         if (!tok)
 373                 return 0;
 374         if (tok->type != ISL_TOKEN_IDENT) {
 375                 isl_stream_push_token(s, tok);
 376                 return 0;
 377         }
 378
 379         tok2 = isl_stream_next_token(s);
 380         if (!tok2) {
 381                 isl_stream_push_token(s, tok);
 382                 return 0;
 383         }
 384         assign = tok2->type == ISL_TOKEN_DEF;
 385         isl_stream_push_token(s, tok2);
 386         isl_stream_push_token(s, tok);
 387
 388         return assign;
 389 }
 390
 391 static struct isl_obj read_obj(struct isl_stream *s,
 392         struct isl_hash_table *table);
 393 static struct isl_obj read_expr(struct isl_stream *s,
 394         struct isl_hash_table *table);
 395
 396 static struct isl_obj read_un_op_expr(struct isl_stream *s,
 397         struct isl_hash_table *table, struct isc_un_op *op)
 398 {
 399         struct isl_obj obj = { isl_obj_none, NULL };
 400
 401         obj = read_obj(s, table);
 402
 403         op = find_matching_un_op(op, obj.type);
 404
 405         isl_assert(s->ctx, op, goto error);
 406         obj.v = op->fn(obj.v);
 407         obj.type = op->res;
 408
 409         return obj;
 410 error:
 411         free_obj(obj);
 412         obj.type = isl_obj_none;
 413         obj.v = NULL;
 414         return obj;
 415 }
 416
 417 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
 418 {
 419         struct isl_list *list;
 420         int exact;
 421
 422         isl_assert(ctx, obj.type == isl_obj_map, goto error);
 423         list = isl_list_alloc(ctx, 2);
 424         if (!list)
 425                 goto error;
 426
 427         list->obj[0].type = isl_obj_map;
 428         list->obj[0].v = isl_map_transitive_closure(obj.v, &exact);
 429         list->obj[1].type = isl_obj_bool;
 430         list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
 431         obj.v = list;
 432         obj.type = isl_obj_list;
 433         if (exact < 0 || !list->obj[0].v)
 434                 goto error;
 435
 436         return obj;
 437 error:
 438         free_obj(obj);
 439         obj.type = isl_obj_none;
 440         obj.v = NULL;
 441         return obj;
 442 }
 443
 444 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
 445 {
 446         struct isl_list *list = obj.v;
 447         struct isl_token *tok;
 448         int i;
 449
 450         tok = isl_stream_next_token(s);
 451         if (!tok || tok->type != ISL_TOKEN_VALUE) {
 452                 isl_stream_error(s, tok, "expecting index");
 453                 if (tok)
 454                         isl_stream_push_token(s, tok);
 455                 goto error;
 456         }
 457         i = isl_int_get_si(tok->u.v);
 458         isl_token_free(tok);
 459         isl_assert(s, i < list->n, goto error);
 460         if (isl_stream_eat(s, ']'))
 461                 goto error;
 462
 463         obj = list->obj[i];
 464         obj.v = obj.type->copy(obj.v);
 465
 466         isl_list_free(list);
 467
 468         return obj;
 469 error:
 470         free_obj(obj);
 471         obj.type = isl_obj_none;
 472         obj.v = NULL;
 473         return obj;
 474 }
 475
 476 static struct isl_obj read_obj(struct isl_stream *s,
 477         struct isl_hash_table *table)
 478 {
 479         struct isl_obj obj = { isl_obj_none, NULL };
 480         char *name = NULL;
 481         struct isc_un_op *op = NULL;
 482
 483         if (isl_stream_eat_if_available(s, '(')) {
 484                 obj = read_expr(s, table);
 485                 if (isl_stream_eat(s, ')'))
 486                         goto error;
 487         } else {
 488                 op = read_prefix_un_op_if_available(s);
 489                 if (op)
 490                         return read_un_op_expr(s, table, op);
 491
 492                 name = isl_stream_read_ident_if_available(s);
 493                 if (name) {
 494                         obj = stored_obj(s->ctx, table, name);
 495                 } else {
 496                         obj = isl_stream_read_obj(s);
 497                         assert(obj.v);
 498                 }
 499         }
 500
 501         if (isl_stream_eat_if_available(s, '^')) {
 502                 if (isl_stream_eat(s, '+'))
 503                         goto error;
 504                 obj = transitive_closure(s->ctx, obj);
 505         } else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
 506                 obj = obj_at_index(s, obj);
 507
 508         return obj;
 509 error:
 510         free_obj(obj);
 511         obj.type = isl_obj_none;
 512         obj.v = NULL;
 513         return obj;
 514 }
 515
 516 static struct isc_un_op *find_matching_bin_op(struct isc_un_op *like,
 517         isl_obj_type lhs, isl_obj_type rhs)
 518 {
 519         int i;
 520
 521         for (i = 0; ; ++i) {
 522                 if (!bin_ops[i].op)
 523                         break;
 524                 if (bin_ops[i].op != like->op)
 525                         continue;
 526                 if (bin_ops[i].lhs != lhs)
 527                         continue;
 528                 if (bin_ops[i].rhs != rhs)
 529                         continue;
 530
 531                 return &bin_ops[i].op;
 532         }
 533
 534         return NULL;
 535 }
 536
 537 static struct isl_obj read_expr(struct isl_stream *s,
 538         struct isl_hash_table *table)
 539 {
 540         struct isl_obj obj = { isl_obj_none, NULL };
 541         struct isl_obj right_obj = { isl_obj_none, NULL };
 542
 543         obj = read_obj(s, table);
 544         for (;;) {
 545                 struct isc_bin_op *op = NULL;
 546
 547                 op = read_bin_op_if_available(s, obj.type);
 548                 if (!op)
 549                         break;
 550
 551                 right_obj = read_obj(s, table);
 552
 553                 op = find_matching_bin_op(op, obj.type, right_obj.type);
 554
 555                 isl_assert(s->ctx, op, goto error);
 556                 obj.v = op->fn(obj.v, right_obj.v);
 557                 obj.type = op->res;
 558         }
 559
 560         return obj;
 561 error:
 562         free_obj(right_obj);
 563         free_obj(obj);
 564         obj.type = isl_obj_none;
 565         obj.v = NULL;
 566         return obj;
 567 }
 568
 569 static void read_line(struct isl_stream *s, struct isl_hash_table *table)
 570 {
 571         struct isl_obj obj = { isl_obj_none, NULL };
 572         char *lhs = NULL;
 573         int assign = 0;
 574         struct isc_bin_op *op = NULL;
 575
 576         if (isl_stream_is_empty(s))
 577                 return;
 578
 579         assign = is_assign(s);
 580         if (assign) {
 581                 lhs = isl_stream_read_ident_if_available(s);
 582                 if (isl_stream_eat(s, ISL_TOKEN_DEF))
 583                         goto error;
 584         }
 585
 586         obj = read_expr(s, table);
 587         if (obj.type == isl_obj_none || obj.v == NULL)
 588                 goto error;
 589         if (isl_stream_eat(s, ';'))
 590                 goto error;
 591
 592         if (assign) {
 593                 if (do_assign(s->ctx, table, lhs, obj))
 594                         return;
 595         } else {
 596                 obj.type->print(obj.v, stdout);
 597                 printf("\n");
 598                 free_obj(obj);
 599         }
 600
 601         return;
 602 error:
 603         free(lhs);
 604         free_obj(obj);
 605 }
 606
 607 int free_cb(void *entry)
 608 {
 609         struct isl_named_obj *named = entry;
 610
 611         free_obj(named->obj);
 612         free(named->name);
 613         free(named);
 614
 615         return 0;
 616 }
 617
 618 static void register_named_ops(struct isl_stream *s)
 619 {
 620         int i;
 621
 622         for (i = 0; ; ++i) {
 623                 if (!named_un_ops[i].name)
 624                         break;
 625                 named_un_ops[i].op.op = isl_stream_register_keyword(s,
 626                                                         named_un_ops[i].name);
 627                 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
 628         }
 629 }
 630
 631 int main(int argc, char **argv)
 632 {
 633         struct isl_ctx *ctx;
 634         struct isl_stream *s;
 635         struct isl_hash_table *table;
 636
 637         ctx = isl_ctx_alloc();
 638         s = isl_stream_new_file(ctx, stdin);
 639         assert(s);
 640         table = isl_hash_table_alloc(ctx, 10);
 641         assert(table);
 642
 643         register_named_ops(s);
 644
 645         while (!feof(stdin)) {
 646                 read_line(s, table);
 647         }
 648
 649         isl_hash_table_foreach(ctx, table, free_cb);
 650         isl_hash_table_free(ctx, table);
 651         isl_stream_free(s);
 652         isl_ctx_free(ctx);
 653
 654         return 0;
 655 }