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