Makefile.am: drop references to obsolete @bv_barvinok_bound@
[barvinok.git] / iscc.c
blobb0f33c3fd31c978791588910bf2a864527a4ad51
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>
10 #include "config.h"
12 #ifdef HAVE_CLOOG
13 #include <cloog/isl/cloog.h>
14 #endif
16 static int isl_bool_false = 0;
17 static int isl_bool_true = 1;
18 static int isl_bool_error = -1;
20 static enum isl_token_type read_op;
21 static enum isl_token_type vertices_op;
23 struct isl_arg_choice iscc_format[] = {
24 {"isl", ISL_FORMAT_ISL},
25 {"omega", ISL_FORMAT_OMEGA},
26 {"polylib", ISL_FORMAT_POLYLIB},
27 {"latex", ISL_FORMAT_LATEX},
28 {"C", ISL_FORMAT_C},
29 {0}
32 struct iscc_options {
33 struct barvinok_options *barvinok;
34 unsigned format;
37 struct isl_arg iscc_options_arg[] = {
38 ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", barvinok_options_arg,
39 "barvinok options")
40 ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
41 iscc_format, ISL_FORMAT_ISL, "output format")
42 ISL_ARG_END
45 ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_arg)
47 static void *isl_obj_bool_copy(void *v)
49 return v;
52 static void isl_obj_bool_free(void *v)
56 static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
57 void *v)
59 if (v == &isl_bool_true)
60 return isl_printer_print_str(p, "True");
61 else if (v == &isl_bool_false)
62 return isl_printer_print_str(p, "False");
63 else
64 return isl_printer_print_str(p, "Error");
67 static void *isl_obj_bool_add(void *v1, void *v2)
69 return v1;
72 struct isl_obj_vtable isl_obj_bool_vtable = {
73 isl_obj_bool_copy,
74 isl_obj_bool_add,
75 isl_obj_bool_print,
76 isl_obj_bool_free
78 #define isl_obj_bool (&isl_obj_bool_vtable)
80 int *isl_bool_from_int(int res)
82 return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
85 int *union_map_is_equal(__isl_take isl_union_map *map1,
86 __isl_take isl_union_map *map2)
88 int res = isl_union_map_is_equal(map1, map2);
89 isl_union_map_free(map1);
90 isl_union_map_free(map2);
91 return isl_bool_from_int(res);
93 int *union_set_is_equal(__isl_take isl_union_set *set1,
94 __isl_take isl_union_set *set2)
96 return union_map_is_equal((isl_union_map *)set1, (isl_union_map *)set2);
99 int *union_map_is_subset(__isl_take isl_union_map *map1,
100 __isl_take isl_union_map *map2)
102 int res = isl_union_map_is_subset(map1, map2);
103 isl_union_map_free(map1);
104 isl_union_map_free(map2);
105 return isl_bool_from_int(res);
107 int *union_set_is_subset(__isl_take isl_union_set *set1,
108 __isl_take isl_union_set *set2)
110 return union_map_is_subset((isl_union_map *)set1, (isl_union_map *)set2);
113 int *union_map_is_strict_subset(__isl_take isl_union_map *map1,
114 __isl_take isl_union_map *map2)
116 int res = isl_union_map_is_strict_subset(map1, map2);
117 isl_union_map_free(map1);
118 isl_union_map_free(map2);
119 return isl_bool_from_int(res);
121 int *union_set_is_strict_subset(__isl_take isl_union_set *set1,
122 __isl_take isl_union_set *set2)
124 return union_map_is_strict_subset((isl_union_map *)set1,
125 (isl_union_map *)set2);
128 int *union_map_is_superset(__isl_take isl_union_map *map1,
129 __isl_take isl_union_map *map2)
131 return union_map_is_subset(map2, map1);
133 int *union_set_is_superset(__isl_take isl_union_set *set1,
134 __isl_take isl_union_set *set2)
136 return union_set_is_subset(set2, set1);
139 int *union_map_is_strict_superset(__isl_take isl_union_map *map1,
140 __isl_take isl_union_map *map2)
142 return union_map_is_strict_subset(map2, map1);
144 int *union_set_is_strict_superset(__isl_take isl_union_set *set1,
145 __isl_take isl_union_set *set2)
147 return union_set_is_strict_subset(set2, set1);
150 extern struct isl_obj_vtable isl_obj_list_vtable;
151 #define isl_obj_list (&isl_obj_list_vtable)
153 typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
154 struct isc_bin_op {
155 enum isl_token_type op;
156 isl_obj_type lhs;
157 isl_obj_type rhs;
158 isl_obj_type res;
159 isc_bin_op_fn fn;
161 struct isc_named_bin_op {
162 char *name;
163 struct isc_bin_op op;
166 struct iscc_at {
167 isl_union_pw_qpolynomial *upwqp;
168 isl_union_pw_qpolynomial *res;
171 static int eval_at(__isl_take isl_point *pnt, void *user)
173 struct iscc_at *at = (struct iscc_at *) user;
174 isl_qpolynomial *qp;
175 isl_set *set;
177 set = isl_set_from_point(isl_point_copy(pnt));
178 qp = isl_union_pw_qpolynomial_eval(
179 isl_union_pw_qpolynomial_copy(at->upwqp), pnt);
181 at->res = isl_union_pw_qpolynomial_add(at->res,
182 isl_union_pw_qpolynomial_from_pw_qpolynomial(
183 isl_pw_qpolynomial_alloc(set, qp)));
185 return 0;
188 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_at(
189 __isl_take isl_union_pw_qpolynomial *upwqp,
190 __isl_take isl_union_set *uset)
192 struct iscc_at at;
194 at.upwqp = upwqp;
195 at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
197 isl_union_set_foreach_point(uset, eval_at, &at);
199 isl_union_pw_qpolynomial_free(upwqp);
200 isl_union_set_free(uset);
202 return at.res;
205 struct iscc_fold_at {
206 isl_union_pw_qpolynomial_fold *upwf;
207 isl_union_pw_qpolynomial *res;
210 static int eval_fold_at(__isl_take isl_point *pnt, void *user)
212 struct iscc_fold_at *at = (struct iscc_fold_at *) user;
213 isl_qpolynomial *qp;
214 isl_set *set;
216 set = isl_set_from_point(isl_point_copy(pnt));
217 qp = isl_union_pw_qpolynomial_fold_eval(
218 isl_union_pw_qpolynomial_fold_copy(at->upwf), pnt);
220 at->res = isl_union_pw_qpolynomial_add(at->res,
221 isl_union_pw_qpolynomial_from_pw_qpolynomial(
222 isl_pw_qpolynomial_alloc(set, qp)));
224 return 0;
227 __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_fold_at(
228 __isl_take isl_union_pw_qpolynomial_fold *upwf,
229 __isl_take isl_union_set *uset)
231 struct iscc_fold_at at;
233 at.upwf = upwf;
234 at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));
236 isl_union_set_foreach_point(uset, eval_fold_at, &at);
238 isl_union_pw_qpolynomial_fold_free(upwf);
239 isl_union_set_free(uset);
241 return at.res;
244 static __isl_give isl_union_pw_qpolynomial_fold *union_pw_qpolynomial_add_union_pw_qpolynomial_fold(
245 __isl_take isl_union_pw_qpolynomial *upwqp,
246 __isl_take isl_union_pw_qpolynomial_fold *upwf)
248 return isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial(upwf,
249 upwqp);
252 static __isl_give struct isl_list *union_map_apply_union_pw_qpolynomial_fold(
253 __isl_take isl_union_map *umap,
254 __isl_take isl_union_pw_qpolynomial_fold *upwf)
256 isl_ctx *ctx;
257 struct isl_list *list;
258 int tight;
260 ctx = isl_union_map_get_ctx(umap);
261 list = isl_list_alloc(ctx, 2);
262 if (!list)
263 goto error2;
265 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
266 list->obj[0].v = isl_union_map_apply_union_pw_qpolynomial_fold(umap,
267 upwf, &tight);
268 list->obj[1].type = isl_obj_bool;
269 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
270 if (tight < 0 || !list->obj[0].v)
271 goto error;
273 return list;
274 error2:
275 isl_union_map_free(umap);
276 isl_union_pw_qpolynomial_fold_free(upwf);
277 error:
278 isl_list_free(list);
279 return NULL;
282 struct isc_bin_op bin_ops[] = {
283 { '+', isl_obj_union_set, isl_obj_union_set,
284 isl_obj_union_set,
285 (isc_bin_op_fn) &isl_union_set_union },
286 { '+', isl_obj_union_map, isl_obj_union_map,
287 isl_obj_union_map,
288 (isc_bin_op_fn) &isl_union_map_union },
289 { '-', isl_obj_union_set, isl_obj_union_set,
290 isl_obj_union_set,
291 (isc_bin_op_fn) &isl_union_set_subtract },
292 { '-', isl_obj_union_map, isl_obj_union_map,
293 isl_obj_union_map,
294 (isc_bin_op_fn) &isl_union_map_subtract },
295 { '*', isl_obj_union_set, isl_obj_union_set,
296 isl_obj_union_set,
297 (isc_bin_op_fn) &isl_union_set_intersect },
298 { '*', isl_obj_union_map, isl_obj_union_map,
299 isl_obj_union_map,
300 (isc_bin_op_fn) &isl_union_map_intersect },
301 { '*', isl_obj_union_map, isl_obj_union_set,
302 isl_obj_union_map,
303 (isc_bin_op_fn) &isl_union_map_intersect_domain },
304 { '.', isl_obj_union_map, isl_obj_union_map,
305 isl_obj_union_map,
306 (isc_bin_op_fn) &isl_union_map_apply_range },
307 { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial,
308 isl_obj_union_pw_qpolynomial,
309 (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial },
310 { '.', isl_obj_union_map, isl_obj_union_pw_qpolynomial_fold,
311 isl_obj_list,
312 (isc_bin_op_fn) &union_map_apply_union_pw_qpolynomial_fold },
313 { ISL_TOKEN_TO, isl_obj_union_set, isl_obj_union_set,
314 isl_obj_union_map,
315 (isc_bin_op_fn) &isl_union_map_from_domain_and_range },
316 { '=', isl_obj_union_set, isl_obj_union_set, isl_obj_bool,
317 (isc_bin_op_fn) &union_set_is_equal },
318 { '=', isl_obj_union_map, isl_obj_union_map, isl_obj_bool,
319 (isc_bin_op_fn) &union_map_is_equal },
320 { ISL_TOKEN_LE, isl_obj_union_set, isl_obj_union_set,
321 isl_obj_bool, (isc_bin_op_fn) &union_set_is_subset },
322 { ISL_TOKEN_LE, isl_obj_union_map, isl_obj_union_map,
323 isl_obj_bool, (isc_bin_op_fn) &union_map_is_subset },
324 { ISL_TOKEN_LT, isl_obj_union_set, isl_obj_union_set,
325 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_subset },
326 { ISL_TOKEN_LT, isl_obj_union_map, isl_obj_union_map,
327 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_subset },
328 { ISL_TOKEN_GE, isl_obj_union_set, isl_obj_union_set,
329 isl_obj_bool, (isc_bin_op_fn) &union_set_is_superset },
330 { ISL_TOKEN_GE, isl_obj_union_map, isl_obj_union_map,
331 isl_obj_bool, (isc_bin_op_fn) &union_map_is_superset },
332 { ISL_TOKEN_GT, isl_obj_union_set, isl_obj_union_set,
333 isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_superset },
334 { ISL_TOKEN_GT, isl_obj_union_map, isl_obj_union_map,
335 isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_superset },
336 { '.', isl_obj_union_pw_qpolynomial_fold,
337 isl_obj_union_pw_qpolynomial_fold,
338 isl_obj_union_pw_qpolynomial_fold,
339 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_fold },
340 { '+', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
341 isl_obj_union_pw_qpolynomial,
342 (isc_bin_op_fn) &isl_union_pw_qpolynomial_add },
343 { '+', isl_obj_union_pw_qpolynomial,
344 isl_obj_union_pw_qpolynomial_fold,
345 isl_obj_union_pw_qpolynomial_fold,
346 (isc_bin_op_fn) &union_pw_qpolynomial_add_union_pw_qpolynomial_fold },
347 { '+', isl_obj_union_pw_qpolynomial_fold,
348 isl_obj_union_pw_qpolynomial,
349 isl_obj_union_pw_qpolynomial_fold,
350 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_add_union_pw_qpolynomial },
351 { '-', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
352 isl_obj_union_pw_qpolynomial,
353 (isc_bin_op_fn) &isl_union_pw_qpolynomial_sub },
354 { '*', isl_obj_union_pw_qpolynomial, isl_obj_union_pw_qpolynomial,
355 isl_obj_union_pw_qpolynomial,
356 (isc_bin_op_fn) &isl_union_pw_qpolynomial_mul },
357 { '*', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
358 isl_obj_union_pw_qpolynomial,
359 (isc_bin_op_fn) &isl_union_pw_qpolynomial_intersect_domain },
360 { '*', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
361 isl_obj_union_pw_qpolynomial_fold,
362 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_intersect_domain },
363 { '@', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
364 isl_obj_union_pw_qpolynomial,
365 (isc_bin_op_fn) &isl_union_pw_qpolynomial_at },
366 { '@', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
367 isl_obj_union_pw_qpolynomial,
368 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_at },
369 { '%', isl_obj_union_set, isl_obj_union_set,
370 isl_obj_union_set,
371 (isc_bin_op_fn) &isl_union_set_gist },
372 { '%', isl_obj_union_map, isl_obj_union_map,
373 isl_obj_union_map,
374 (isc_bin_op_fn) &isl_union_map_gist },
375 { '%', isl_obj_union_pw_qpolynomial, isl_obj_union_set,
376 isl_obj_union_pw_qpolynomial,
377 (isc_bin_op_fn) &isl_union_pw_qpolynomial_gist },
378 { '%', isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
379 isl_obj_union_pw_qpolynomial_fold,
380 (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_gist },
383 struct isc_named_bin_op named_bin_ops[] = {
384 { "cross", { -1, isl_obj_union_set, isl_obj_union_set,
385 isl_obj_union_set,
386 (isc_bin_op_fn) &isl_union_set_product } },
387 { "cross", { -1, isl_obj_union_map, isl_obj_union_map,
388 isl_obj_union_map,
389 (isc_bin_op_fn) &isl_union_map_product } },
390 NULL
393 __isl_give isl_set *union_set_sample(__isl_take isl_union_set *uset)
395 return isl_set_from_basic_set(isl_union_set_sample(uset));
398 __isl_give isl_map *union_map_sample(__isl_take isl_union_map *umap)
400 return isl_map_from_basic_map(isl_union_map_sample(umap));
403 static __isl_give struct isl_list *union_pw_qpolynomial_upper_bound(
404 __isl_take isl_union_pw_qpolynomial *upwqp)
406 isl_ctx *ctx;
407 struct isl_list *list;
408 int tight;
410 ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
411 list = isl_list_alloc(ctx, 2);
412 if (!list)
413 goto error2;
415 list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
416 list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
417 isl_fold_max, &tight);
418 list->obj[1].type = isl_obj_bool;
419 list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
420 if (tight < 0 || !list->obj[0].v)
421 goto error;
423 return list;
424 error2:
425 isl_union_pw_qpolynomial_free(upwqp);
426 error:
427 isl_list_free(list);
428 return NULL;
431 #ifdef HAVE_CLOOG
432 void *map_codegen(void *arg)
434 isl_dim *dim;
435 isl_union_map *umap = (isl_union_map *)arg;
436 isl_ctx *ctx = isl_union_map_get_ctx(umap);
437 CloogState *state;
438 CloogOptions *options;
439 CloogDomain *context;
440 CloogUnionDomain *ud;
441 CloogInput *input;
442 struct clast_stmt *stmt;
444 state = cloog_isl_state_malloc(ctx);
445 options = cloog_options_malloc(state);
446 options->language = LANGUAGE_C;
447 options->strides = 1;
449 ud = cloog_union_domain_from_isl_union_map(isl_union_map_copy(umap));
451 dim = isl_union_map_get_dim(umap);
452 context = cloog_domain_from_isl_set(isl_set_universe(dim));
454 input = cloog_input_alloc(context, ud);
456 stmt = cloog_clast_create_from_input(input, options);
457 clast_pprint(stdout, stmt, 0, options);
458 cloog_clast_free(stmt);
460 error:
461 cloog_options_free(options);
462 cloog_state_free(state);
463 isl_union_map_free(umap);
464 return NULL;
467 void *set_codegen(void *arg)
469 isl_dim *dim;
470 isl_union_set *uset = (isl_union_set *)arg;
471 isl_ctx *ctx = isl_union_set_get_ctx(uset);
472 CloogState *state;
473 CloogOptions *options;
474 CloogDomain *context;
475 CloogUnionDomain *ud;
476 CloogInput *input;
477 struct clast_stmt *stmt;
479 state = cloog_isl_state_malloc(ctx);
480 options = cloog_options_malloc(state);
481 options->language = LANGUAGE_C;
482 options->strides = 1;
484 ud = cloog_union_domain_from_isl_union_set(isl_union_set_copy(uset));
486 dim = isl_union_set_get_dim(uset);
487 context = cloog_domain_from_isl_set(isl_set_universe(dim));
489 input = cloog_input_alloc(context, ud);
491 stmt = cloog_clast_create_from_input(input, options);
492 clast_pprint(stdout, stmt, 0, options);
493 cloog_clast_free(stmt);
495 error:
496 cloog_options_free(options);
497 cloog_state_free(state);
498 isl_union_set_free(uset);
499 return NULL;
501 #endif
503 typedef void *(*isc_un_op_fn)(void *arg);
504 struct isc_un_op {
505 enum isl_token_type op;
506 isl_obj_type arg;
507 isl_obj_type res;
508 isc_un_op_fn fn;
510 struct isc_named_un_op {
511 char *name;
512 struct isc_un_op op;
514 struct isc_named_un_op named_un_ops[] = {
515 {"aff", { -1, isl_obj_union_map, isl_obj_union_map,
516 (isc_un_op_fn) &isl_union_map_affine_hull } },
517 {"aff", { -1, isl_obj_union_set, isl_obj_union_set,
518 (isc_un_op_fn) &isl_union_set_affine_hull } },
519 {"card", { -1, isl_obj_union_set,
520 isl_obj_union_pw_qpolynomial,
521 (isc_un_op_fn) &isl_union_set_card } },
522 {"card", { -1, isl_obj_union_map,
523 isl_obj_union_pw_qpolynomial,
524 (isc_un_op_fn) &isl_union_map_card } },
525 {"coalesce", { -1, isl_obj_union_set, isl_obj_union_set,
526 (isc_un_op_fn) &isl_union_set_coalesce } },
527 {"coalesce", { -1, isl_obj_union_map, isl_obj_union_map,
528 (isc_un_op_fn) &isl_union_map_coalesce } },
529 {"coalesce", { -1, isl_obj_union_pw_qpolynomial,
530 isl_obj_union_pw_qpolynomial,
531 (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
532 {"coalesce", { -1, isl_obj_union_pw_qpolynomial_fold,
533 isl_obj_union_pw_qpolynomial_fold,
534 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
535 #ifdef HAVE_CLOOG
536 {"codegen", { -1, isl_obj_union_set, isl_obj_none,
537 &set_codegen } },
538 {"codegen", { -1, isl_obj_union_map, isl_obj_none,
539 &map_codegen } },
540 #endif
541 {"deltas", { -1, isl_obj_union_map, isl_obj_union_set,
542 (isc_un_op_fn) &isl_union_map_deltas } },
543 {"dom", { -1, isl_obj_union_map, isl_obj_union_set,
544 (isc_un_op_fn) &isl_union_map_domain } },
545 {"dom", { -1, isl_obj_union_pw_qpolynomial, isl_obj_union_set,
546 (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
547 {"dom", { -1, isl_obj_union_pw_qpolynomial_fold,
548 isl_obj_union_set,
549 (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
550 {"ran", { -1, isl_obj_union_map, isl_obj_union_set,
551 (isc_un_op_fn) &isl_union_map_range } },
552 {"lexmin", { -1, isl_obj_union_map, isl_obj_union_map,
553 (isc_un_op_fn) &isl_union_map_lexmin } },
554 {"lexmax", { -1, isl_obj_union_map, isl_obj_union_map,
555 (isc_un_op_fn) &isl_union_map_lexmax } },
556 {"lexmin", { -1, isl_obj_union_set, isl_obj_union_set,
557 (isc_un_op_fn) &isl_union_set_lexmin } },
558 {"lexmax", { -1, isl_obj_union_set, isl_obj_union_set,
559 (isc_un_op_fn) &isl_union_set_lexmax } },
560 {"sample", { -1, isl_obj_union_set, isl_obj_set,
561 (isc_un_op_fn) &union_set_sample } },
562 {"sample", { -1, isl_obj_union_map, isl_obj_map,
563 (isc_un_op_fn) &union_map_sample } },
564 {"sum", { -1, isl_obj_union_pw_qpolynomial,
565 isl_obj_union_pw_qpolynomial,
566 (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
567 {"ub", { -1, isl_obj_union_pw_qpolynomial, isl_obj_list,
568 (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
569 {"unwrap", { -1, isl_obj_union_set, isl_obj_union_map,
570 (isc_un_op_fn) &isl_union_set_unwrap } },
571 {"wrap", { -1, isl_obj_union_map, isl_obj_union_set,
572 (isc_un_op_fn) &isl_union_map_wrap } },
573 NULL
576 struct isl_named_obj {
577 char *name;
578 struct isl_obj obj;
581 static void free_obj(struct isl_obj obj)
583 obj.type->free(obj.v);
586 static int same_name(const void *entry, const void *val)
588 const struct isl_named_obj *named = (const struct isl_named_obj *)entry;
590 return !strcmp(named->name, val);
593 static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
594 char *name, struct isl_obj obj)
596 struct isl_hash_table_entry *entry;
597 uint32_t name_hash;
598 struct isl_named_obj *named;
600 name_hash = isl_hash_string(isl_hash_init(), name);
601 entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
602 if (!entry)
603 goto error;
604 if (entry->data) {
605 named = entry->data;
606 free_obj(named->obj);
607 free(name);
608 } else {
609 named = isl_alloc_type(ctx, struct isl_named_obj);
610 if (!named)
611 goto error;
612 named->name = name;
613 entry->data = named;
615 named->obj = obj;
617 return 0;
618 error:
619 free_obj(obj);
620 free(name);
621 return -1;
624 static struct isl_obj stored_obj(struct isl_ctx *ctx,
625 struct isl_hash_table *table, char *name)
627 struct isl_obj obj = { isl_obj_none, NULL };
628 struct isl_hash_table_entry *entry;
629 uint32_t name_hash;
631 name_hash = isl_hash_string(isl_hash_init(), name);
632 entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
633 if (entry) {
634 struct isl_named_obj *named;
635 named = entry->data;
636 obj = named->obj;
639 free(name);
640 obj.v = obj.type->copy(obj.v);
641 return obj;
644 static int is_subtype(struct isl_obj obj, isl_obj_type super)
646 if (obj.type == super)
647 return 1;
648 if (obj.type == isl_obj_map && super == isl_obj_union_map)
649 return 1;
650 if (obj.type == isl_obj_set && super == isl_obj_union_set)
651 return 1;
652 if (obj.type == isl_obj_pw_qpolynomial &&
653 super == isl_obj_union_pw_qpolynomial)
654 return 1;
655 if (obj.type == isl_obj_pw_qpolynomial_fold &&
656 super == isl_obj_union_pw_qpolynomial_fold)
657 return 1;
658 if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
659 return 1;
660 if (obj.type == isl_obj_list) {
661 struct isl_list *list = obj.v;
662 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
663 return is_subtype(list->obj[0], super);
665 return 0;
668 static struct isl_obj obj_at(struct isl_obj obj, int i)
670 struct isl_list *list = obj.v;
672 obj = list->obj[i];
673 obj.v = obj.type->copy(obj.v);
675 isl_list_free(list);
677 return obj;
680 static struct isl_obj convert(struct isl_obj obj, isl_obj_type type)
682 if (obj.type == type)
683 return obj;
684 if (obj.type == isl_obj_map && type == isl_obj_union_map) {
685 obj.type = isl_obj_union_map;
686 obj.v = isl_union_map_from_map(obj.v);
687 return obj;
689 if (obj.type == isl_obj_set && type == isl_obj_union_set) {
690 obj.type = isl_obj_union_set;
691 obj.v = isl_union_set_from_set(obj.v);
692 return obj;
694 if (obj.type == isl_obj_pw_qpolynomial &&
695 type == isl_obj_union_pw_qpolynomial) {
696 obj.type = isl_obj_union_pw_qpolynomial;
697 obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
698 return obj;
700 if (obj.type == isl_obj_pw_qpolynomial_fold &&
701 type == isl_obj_union_pw_qpolynomial_fold) {
702 obj.type = isl_obj_union_pw_qpolynomial_fold;
703 obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
704 return obj;
706 if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
707 if (type == isl_obj_union_map) {
708 obj.type = isl_obj_union_map;
709 return obj;
711 if (type == isl_obj_union_pw_qpolynomial) {
712 isl_dim *dim = isl_union_set_get_dim(obj.v);
713 isl_union_set_free(obj.v);
714 obj.v = isl_union_pw_qpolynomial_zero(dim);
715 obj.type = isl_obj_union_pw_qpolynomial;
716 return obj;
718 if (type == isl_obj_union_pw_qpolynomial_fold) {
719 isl_dim *dim = isl_union_set_get_dim(obj.v);
720 isl_union_set_free(obj.v);
721 obj.v = isl_union_pw_qpolynomial_fold_zero(dim,
722 isl_fold_list);
723 obj.type = isl_obj_union_pw_qpolynomial_fold;
724 return obj;
727 if (obj.type == isl_obj_list) {
728 struct isl_list *list = obj.v;
729 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
730 return convert(obj_at(obj, 0), type);
732 free_obj(obj);
733 obj.type = isl_obj_none;
734 obj.v = NULL;
735 return obj;
738 static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
739 struct isl_obj lhs)
741 int i;
742 struct isl_token *tok;
744 tok = isl_stream_next_token(s);
745 if (!tok)
746 return NULL;
748 for (i = 0; ; ++i) {
749 if (!bin_ops[i].op)
750 break;
751 if (bin_ops[i].op != tok->type)
752 continue;
753 if (!is_subtype(lhs, bin_ops[i].lhs))
754 continue;
756 isl_token_free(tok);
757 return &bin_ops[i];
760 for (i = 0; ; ++i) {
761 if (!named_bin_ops[i].name)
762 break;
763 if (named_bin_ops[i].op.op != tok->type)
764 continue;
765 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
766 continue;
768 isl_token_free(tok);
769 return &named_bin_ops[i].op;
772 isl_stream_push_token(s, tok);
774 return NULL;
777 static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
779 int i;
780 struct isl_token *tok;
782 tok = isl_stream_next_token(s);
783 if (!tok)
784 return NULL;
786 for (i = 0; ; ++i) {
787 if (!named_un_ops[i].name)
788 break;
789 if (named_un_ops[i].op.op != tok->type)
790 continue;
792 isl_token_free(tok);
793 return &named_un_ops[i].op;
796 isl_stream_push_token(s, tok);
798 return NULL;
801 static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
802 struct isl_obj arg)
804 int i;
806 for (i = 0; ; ++i) {
807 if (!named_un_ops[i].name)
808 break;
809 if (named_un_ops[i].op.op != like->op)
810 continue;
811 if (!is_subtype(arg, named_un_ops[i].op.arg))
812 continue;
814 return &named_un_ops[i].op;
817 return NULL;
820 static int is_assign(struct isl_stream *s)
822 struct isl_token *tok;
823 struct isl_token *tok2;
824 int assign;
826 tok = isl_stream_next_token(s);
827 if (!tok)
828 return 0;
829 if (tok->type != ISL_TOKEN_IDENT) {
830 isl_stream_push_token(s, tok);
831 return 0;
834 tok2 = isl_stream_next_token(s);
835 if (!tok2) {
836 isl_stream_push_token(s, tok);
837 return 0;
839 assign = tok2->type == ISL_TOKEN_DEF;
840 isl_stream_push_token(s, tok2);
841 isl_stream_push_token(s, tok);
843 return assign;
846 static struct isl_obj read_obj(struct isl_stream *s,
847 struct isl_hash_table *table);
848 static struct isl_obj read_expr(struct isl_stream *s,
849 struct isl_hash_table *table);
851 static struct isl_obj read_un_op_expr(struct isl_stream *s,
852 struct isl_hash_table *table, struct isc_un_op *op)
854 struct isl_obj obj = { isl_obj_none, NULL };
856 obj = read_obj(s, table);
857 if (!obj.v)
858 goto error;
860 op = find_matching_un_op(op, obj);
862 isl_assert(s->ctx, op, goto error);
863 obj = convert(obj, op->arg);
864 obj.v = op->fn(obj.v);
865 obj.type = op->res;
867 return obj;
868 error:
869 free_obj(obj);
870 obj.type = isl_obj_none;
871 obj.v = NULL;
872 return obj;
875 static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
877 struct isl_list *list;
878 int exact;
880 if (obj.type != isl_obj_union_map)
881 obj = convert(obj, isl_obj_union_map);
882 isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
883 list = isl_list_alloc(ctx, 2);
884 if (!list)
885 goto error;
887 list->obj[0].type = isl_obj_union_map;
888 list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
889 list->obj[1].type = isl_obj_bool;
890 list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
891 obj.v = list;
892 obj.type = isl_obj_list;
893 if (exact < 0 || !list->obj[0].v)
894 goto error;
896 return obj;
897 error:
898 free_obj(obj);
899 obj.type = isl_obj_none;
900 obj.v = NULL;
901 return obj;
904 static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
906 struct isl_list *list = obj.v;
907 struct isl_token *tok;
908 int i;
910 tok = isl_stream_next_token(s);
911 if (!tok || tok->type != ISL_TOKEN_VALUE) {
912 isl_stream_error(s, tok, "expecting index");
913 if (tok)
914 isl_stream_push_token(s, tok);
915 goto error;
917 i = isl_int_get_si(tok->u.v);
918 isl_token_free(tok);
919 isl_assert(s->ctx, i < list->n, goto error);
920 if (isl_stream_eat(s, ']'))
921 goto error;
923 return obj_at(obj, i);
924 error:
925 free_obj(obj);
926 obj.type = isl_obj_none;
927 obj.v = NULL;
928 return obj;
931 static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
932 struct isl_hash_table *table)
934 struct isl_obj obj;
936 obj = read_expr(s, table);
937 isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
938 is_subtype(obj, isl_obj_union_map), goto error);
940 if (obj.type == isl_obj_list) {
941 struct isl_list *list = obj.v;
942 if (list->n == 2 && list->obj[1].type == isl_obj_bool)
943 obj = obj_at(obj, 0);
945 if (obj.type == isl_obj_set)
946 obj = convert(obj, isl_obj_union_set);
947 else if (obj.type == isl_obj_map)
948 obj = convert(obj, isl_obj_union_map);
949 if (obj.type == isl_obj_union_set) {
950 obj.v = isl_union_set_apply(obj.v, umap);
951 } else
952 obj.v = isl_union_map_apply_range(obj.v, umap);
953 if (!obj.v)
954 goto error2;
956 if (isl_stream_eat(s, ')'))
957 goto error2;
959 return obj;
960 error:
961 isl_union_map_free(umap);
962 error2:
963 free_obj(obj);
964 obj.type = isl_obj_none;
965 obj.v = NULL;
966 return obj;
969 struct add_vertex_data {
970 struct isl_list *list;
971 int i;
974 static int add_vertex(__isl_take isl_vertex *vertex, void *user)
976 struct add_vertex_data *data = (struct add_vertex_data *)user;
977 isl_basic_set *expr;
979 expr = isl_vertex_get_expr(vertex);
981 data->list->obj[data->i].type = isl_obj_set;
982 data->list->obj[data->i].v = isl_set_from_basic_set(expr);
983 data->i++;
985 isl_vertex_free(vertex);
987 return 0;
990 static struct isl_obj vertices(struct isl_stream *s,
991 struct isl_hash_table *table)
993 isl_ctx *ctx;
994 struct isl_obj obj;
995 isl_set *set;
996 isl_basic_set *hull;
997 isl_vertices *vertices = NULL;
998 struct isl_list *list = NULL;
999 struct add_vertex_data data;
1001 obj = read_expr(s, table);
1002 isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
1003 set = obj.v;
1004 obj.v = NULL;
1005 set = isl_set_remove_divs(set);
1006 hull = isl_set_convex_hull(set);
1007 vertices = isl_basic_set_compute_vertices(hull);
1008 isl_basic_set_free(hull);
1010 ctx = isl_vertices_get_ctx(vertices);
1011 list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
1012 if (!list)
1013 goto error;
1015 data.list = list;
1016 data.i = 0;
1018 if (isl_vertices_foreach_vertex(vertices, &add_vertex, &data) < 0)
1019 goto error;
1021 isl_vertices_free(vertices);
1023 obj.type = isl_obj_list;
1024 obj.v = list;
1026 return obj;
1027 error:
1028 isl_vertices_free(vertices);
1029 isl_list_free(list);
1030 free_obj(obj);
1031 obj.type = isl_obj_none;
1032 obj.v = NULL;
1033 return obj;
1036 static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
1038 struct isl_token *tok;
1040 if (isl_stream_eat_if_available(s, '+'))
1041 return transitive_closure(s->ctx, obj);
1043 tok = isl_stream_next_token(s);
1044 if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
1045 isl_stream_error(s, tok, "expecting -1");
1046 if (tok)
1047 isl_stream_push_token(s, tok);
1048 goto error;
1050 isl_token_free(tok);
1051 isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
1052 if (obj.type != isl_obj_union_map)
1053 obj = convert(obj, isl_obj_union_map);
1055 obj.v = isl_union_map_reverse(obj.v);
1056 if (!obj.v)
1057 goto error;
1059 return obj;
1060 error:
1061 free_obj(obj);
1062 obj.type = isl_obj_none;
1063 obj.v = NULL;
1064 return obj;
1067 static struct isl_obj read_from_file(struct isl_stream *s)
1069 struct isl_obj obj;
1070 struct isl_token *tok;
1071 struct isl_stream *s_file;
1072 FILE *file;
1074 tok = isl_stream_next_token(s);
1075 if (!tok || tok->type != ISL_TOKEN_STRING) {
1076 isl_stream_error(s, tok, "expecting filename");
1077 isl_token_free(tok);
1078 goto error;
1081 file = fopen(tok->u.s, "r");
1082 isl_token_free(tok);
1083 isl_assert(s->ctx, file, goto error);
1085 s_file = isl_stream_new_file(s->ctx, file);
1086 if (!s_file) {
1087 fclose(file);
1088 goto error;
1091 obj = isl_stream_read_obj(s_file);
1093 isl_stream_free(s_file);
1094 fclose(file);
1096 return obj;
1097 error:
1098 obj.type = isl_obj_none;
1099 obj.v = NULL;
1100 return obj;
1103 static struct isl_obj read_obj(struct isl_stream *s,
1104 struct isl_hash_table *table)
1106 struct isl_obj obj = { isl_obj_none, NULL };
1107 char *name = NULL;
1108 struct isc_un_op *op = NULL;
1110 if (isl_stream_eat_if_available(s, '(')) {
1111 obj = read_expr(s, table);
1112 if (!obj.v || isl_stream_eat(s, ')'))
1113 goto error;
1114 } else {
1115 op = read_prefix_un_op_if_available(s);
1116 if (op)
1117 return read_un_op_expr(s, table, op);
1119 if (isl_stream_eat_if_available(s, read_op))
1120 return read_from_file(s);
1121 if (isl_stream_eat_if_available(s, vertices_op))
1122 return vertices(s, table);
1124 name = isl_stream_read_ident_if_available(s);
1125 if (name)
1126 obj = stored_obj(s->ctx, table, name);
1127 else
1128 obj = isl_stream_read_obj(s);
1129 if (!obj.v)
1130 goto error;
1133 if (isl_stream_eat_if_available(s, '^'))
1134 obj = power(s, obj);
1135 else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
1136 obj = obj_at_index(s, obj);
1137 else if (is_subtype(obj, isl_obj_union_map) &&
1138 isl_stream_eat_if_available(s, '(')) {
1139 obj = convert(obj, isl_obj_union_map);
1140 obj = apply(s, obj.v, table);
1143 return obj;
1144 error:
1145 free_obj(obj);
1146 obj.type = isl_obj_none;
1147 obj.v = NULL;
1148 return obj;
1151 static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
1152 struct isl_obj lhs, struct isl_obj rhs)
1154 int i;
1156 for (i = 0; ; ++i) {
1157 if (!bin_ops[i].op)
1158 break;
1159 if (bin_ops[i].op != like->op)
1160 continue;
1161 if (!is_subtype(lhs, bin_ops[i].lhs))
1162 continue;
1163 if (!is_subtype(rhs, bin_ops[i].rhs))
1164 continue;
1166 return &bin_ops[i];
1169 for (i = 0; ; ++i) {
1170 if (!named_bin_ops[i].name)
1171 break;
1172 if (named_bin_ops[i].op.op != like->op)
1173 continue;
1174 if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
1175 continue;
1176 if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
1177 continue;
1179 return &named_bin_ops[i].op;
1182 return NULL;
1185 static struct isl_obj read_expr(struct isl_stream *s,
1186 struct isl_hash_table *table)
1188 struct isl_obj obj = { isl_obj_none, NULL };
1189 struct isl_obj right_obj = { isl_obj_none, NULL };
1191 obj = read_obj(s, table);
1192 for (; obj.v;) {
1193 struct isc_bin_op *op = NULL;
1195 op = read_bin_op_if_available(s, obj);
1196 if (!op)
1197 break;
1199 right_obj = read_obj(s, table);
1201 op = find_matching_bin_op(op, obj, right_obj);
1203 isl_assert(s->ctx, op, goto error);
1204 obj = convert(obj, op->lhs);
1205 right_obj = convert(right_obj, op->rhs);
1206 obj.v = op->fn(obj.v, right_obj.v);
1207 obj.type = op->res;
1210 return obj;
1211 error:
1212 free_obj(right_obj);
1213 free_obj(obj);
1214 obj.type = isl_obj_none;
1215 obj.v = NULL;
1216 return obj;
1219 static __isl_give isl_printer *read_line(struct isl_stream *s,
1220 struct isl_hash_table *table, __isl_take isl_printer *p)
1222 struct isl_obj obj = { isl_obj_none, NULL };
1223 char *lhs = NULL;
1224 int assign = 0;
1225 struct isc_bin_op *op = NULL;
1227 if (!p)
1228 return NULL;
1229 if (isl_stream_is_empty(s))
1230 return p;
1232 assign = is_assign(s);
1233 if (assign) {
1234 lhs = isl_stream_read_ident_if_available(s);
1235 if (isl_stream_eat(s, ISL_TOKEN_DEF))
1236 goto error;
1239 obj = read_expr(s, table);
1240 if (obj.type == isl_obj_none || obj.v == NULL)
1241 goto error;
1242 if (isl_stream_eat(s, ';'))
1243 goto error;
1245 if (assign) {
1246 if (do_assign(s->ctx, table, lhs, obj))
1247 return;
1248 } else {
1249 p = obj.type->print(p, obj.v);
1250 p = isl_printer_end_line(p);
1251 free_obj(obj);
1254 return p;
1255 error:
1256 isl_stream_flush_tokens(s);
1257 isl_stream_skip_line(s);
1258 free(lhs);
1259 free_obj(obj);
1260 return p;
1263 int free_cb(void **entry, void *user)
1265 struct isl_named_obj *named = *entry;
1267 free_obj(named->obj);
1268 free(named->name);
1269 free(named);
1271 return 0;
1274 static void register_named_ops(struct isl_stream *s)
1276 int i;
1278 read_op = isl_stream_register_keyword(s, "read");
1279 assert(read_op != ISL_TOKEN_ERROR);
1280 vertices_op = isl_stream_register_keyword(s, "vertices");
1281 assert(vertices_op != ISL_TOKEN_ERROR);
1283 for (i = 0; ; ++i) {
1284 if (!named_un_ops[i].name)
1285 break;
1286 named_un_ops[i].op.op = isl_stream_register_keyword(s,
1287 named_un_ops[i].name);
1288 assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
1291 for (i = 0; ; ++i) {
1292 if (!named_bin_ops[i].name)
1293 break;
1294 named_bin_ops[i].op.op = isl_stream_register_keyword(s,
1295 named_bin_ops[i].name);
1296 assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
1300 int main(int argc, char **argv)
1302 struct isl_ctx *ctx;
1303 struct isl_stream *s;
1304 struct isl_hash_table *table;
1305 struct iscc_options *options;
1306 isl_printer *p;
1308 options = iscc_options_new_with_defaults();
1309 assert(options);
1310 argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);
1312 ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
1313 s = isl_stream_new_file(ctx, stdin);
1314 assert(s);
1315 table = isl_hash_table_alloc(ctx, 10);
1316 assert(table);
1317 p = isl_printer_to_file(ctx, stdout);
1318 p = isl_printer_set_output_format(p, options->format);
1319 assert(p);
1321 register_named_ops(s);
1323 while (!s->eof) {
1324 p = read_line(s, table, p);
1327 isl_printer_free(p);
1328 isl_hash_table_foreach(ctx, table, free_cb, NULL);
1329 isl_hash_table_free(ctx, table);
1330 isl_stream_free(s);
1331 isl_ctx_free(ctx);
1333 return 0;