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