5 #include <isl_stream.h>
6 #include <isl_obj_list.h>
7 #include <barvinok/barvinok.h>
11 #include <barvinok/bernstein.h>
14 static int isl_bool_false
= 0;
15 static int isl_bool_true
= 1;
16 static int isl_bool_error
= -1;
18 static void *isl_obj_bool_copy(void *v
)
23 static void isl_obj_bool_free(void *v
)
27 static __isl_give isl_printer
*isl_obj_bool_print(__isl_take isl_printer
*p
,
30 if (v
== &isl_bool_true
)
31 return isl_printer_print_str(p
, "True");
32 else if (v
== &isl_bool_false
)
33 return isl_printer_print_str(p
, "False");
35 return isl_printer_print_str(p
, "Error");
38 static void *isl_obj_bool_add(void *v1
, void *v2
)
43 struct isl_obj_vtable isl_obj_bool_vtable
= {
49 #define isl_obj_bool (&isl_obj_bool_vtable)
51 int *isl_bool_from_int(int res
)
53 return res
< 0 ? &isl_bool_error
: res
? &isl_bool_true
: &isl_bool_false
;
56 int *map_is_equal(__isl_take isl_map
*map1
, __isl_take isl_map
*map2
)
58 int res
= isl_map_is_equal(map1
, map2
);
61 return isl_bool_from_int(res
);
63 int *set_is_equal(__isl_take isl_set
*set1
, __isl_take isl_set
*set2
)
65 return map_is_equal((isl_map
*)set1
, (isl_map
*)set2
);
68 int *map_is_subset(__isl_take isl_map
*map1
, __isl_take isl_map
*map2
)
70 int res
= isl_map_is_subset(map1
, map2
);
73 return isl_bool_from_int(res
);
75 int *set_is_subset(__isl_take isl_set
*set1
, __isl_take isl_set
*set2
)
77 return map_is_subset((isl_map
*)set1
, (isl_map
*)set2
);
80 int *map_is_strict_subset(__isl_take isl_map
*map1
, __isl_take isl_map
*map2
)
82 int res
= isl_map_is_strict_subset(map1
, map2
);
85 return isl_bool_from_int(res
);
87 int *set_is_strict_subset(__isl_take isl_set
*set1
, __isl_take isl_set
*set2
)
89 return map_is_strict_subset((isl_map
*)set1
, (isl_map
*)set2
);
92 int *map_is_superset(__isl_take isl_map
*map1
, __isl_take isl_map
*map2
)
94 return map_is_subset(map2
, map1
);
96 int *set_is_superset(__isl_take isl_set
*set1
, __isl_take isl_set
*set2
)
98 return set_is_subset(set2
, set1
);
101 int *map_is_strict_superset(__isl_take isl_map
*map1
, __isl_take isl_map
*map2
)
103 return map_is_strict_subset(map2
, map1
);
105 int *set_is_strict_superset(__isl_take isl_set
*set1
, __isl_take isl_set
*set2
)
107 return set_is_strict_subset(set2
, set1
);
110 extern struct isl_obj_vtable isl_obj_list_vtable
;
111 #define isl_obj_list (&isl_obj_list_vtable)
113 typedef void *(*isc_bin_op_fn
)(void *lhs
, void *rhs
);
115 enum isl_token_type op
;
123 isl_pw_qpolynomial
*pwqp
;
124 isl_pw_qpolynomial
*res
;
127 static int eval_at(__isl_take isl_point
*pnt
, void *user
)
129 struct iscc_at
*at
= (struct iscc_at
*) user
;
133 set
= isl_set_from_point(isl_point_copy(pnt
));
134 qp
= isl_pw_qpolynomial_eval(isl_pw_qpolynomial_copy(at
->pwqp
), pnt
);
136 at
->res
= isl_pw_qpolynomial_add_disjoint(at
->res
,
137 isl_pw_qpolynomial_alloc(set
, qp
));
142 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_at(
143 __isl_take isl_pw_qpolynomial
*pwqp
, __isl_take isl_set
*set
)
148 at
.res
= isl_pw_qpolynomial_zero(isl_set_get_dim(set
));
150 isl_set_foreach_point(set
, eval_at
, &at
);
152 isl_pw_qpolynomial_free(pwqp
);
158 struct iscc_fold_at
{
159 isl_pw_qpolynomial_fold
*pwf
;
160 isl_pw_qpolynomial
*res
;
163 static int eval_fold_at(__isl_take isl_point
*pnt
, void *user
)
165 struct iscc_fold_at
*at
= (struct iscc_fold_at
*) user
;
169 set
= isl_set_from_point(isl_point_copy(pnt
));
170 qp
= isl_pw_qpolynomial_fold_eval(isl_pw_qpolynomial_fold_copy(at
->pwf
),
173 at
->res
= isl_pw_qpolynomial_add_disjoint(at
->res
,
174 isl_pw_qpolynomial_alloc(set
, qp
));
179 __isl_give isl_pw_qpolynomial
*isl_pw_qpolynomial_fold_at(
180 __isl_take isl_pw_qpolynomial_fold
*pwf
, __isl_take isl_set
*set
)
182 struct iscc_fold_at at
;
185 at
.res
= isl_pw_qpolynomial_zero(isl_set_get_dim(set
));
187 isl_set_foreach_point(set
, eval_fold_at
, &at
);
189 isl_pw_qpolynomial_fold_free(pwf
);
195 static __isl_give isl_set
*set_gist(__isl_take isl_set
*set
,
196 __isl_take isl_set
*context
)
198 return isl_set_gist(set
, isl_set_convex_hull(context
));
201 static __isl_give isl_map
*map_gist(__isl_take isl_map
*map
,
202 __isl_take isl_map
*context
)
204 return isl_map_gist(map
, isl_map_convex_hull(context
));
207 struct isc_bin_op bin_ops
[] = {
208 { '+', isl_obj_set
, isl_obj_set
,
210 (isc_bin_op_fn
) &isl_set_union
},
211 { '+', isl_obj_map
, isl_obj_map
,
213 (isc_bin_op_fn
) &isl_map_union
},
214 { '-', isl_obj_set
, isl_obj_set
,
216 (isc_bin_op_fn
) &isl_set_subtract
},
217 { '-', isl_obj_map
, isl_obj_map
,
219 (isc_bin_op_fn
) &isl_map_subtract
},
220 { '*', isl_obj_set
, isl_obj_set
,
222 (isc_bin_op_fn
) &isl_set_intersect
},
223 { '*', isl_obj_map
, isl_obj_map
,
225 (isc_bin_op_fn
) &isl_map_intersect
},
226 { '*', isl_obj_map
, isl_obj_set
,
228 (isc_bin_op_fn
) &isl_map_intersect_domain
},
229 { '.', isl_obj_map
, isl_obj_map
,
231 (isc_bin_op_fn
) &isl_map_apply_range
},
232 { ISL_TOKEN_TO
, isl_obj_set
, isl_obj_set
, isl_obj_map
,
233 (isc_bin_op_fn
) &isl_map_from_domain_and_range
},
234 { '=', isl_obj_set
, isl_obj_set
, isl_obj_bool
,
235 (isc_bin_op_fn
) &set_is_equal
},
236 { '=', isl_obj_map
, isl_obj_map
, isl_obj_bool
,
237 (isc_bin_op_fn
) &map_is_equal
},
238 { ISL_TOKEN_LE
, isl_obj_set
, isl_obj_set
, isl_obj_bool
,
239 (isc_bin_op_fn
) &set_is_subset
},
240 { ISL_TOKEN_LE
, isl_obj_map
, isl_obj_map
, isl_obj_bool
,
241 (isc_bin_op_fn
) &map_is_subset
},
242 { ISL_TOKEN_LT
, isl_obj_set
, isl_obj_set
, isl_obj_bool
,
243 (isc_bin_op_fn
) &set_is_strict_subset
},
244 { ISL_TOKEN_LT
, isl_obj_map
, isl_obj_map
, isl_obj_bool
,
245 (isc_bin_op_fn
) &map_is_strict_subset
},
246 { ISL_TOKEN_GE
, isl_obj_set
, isl_obj_set
, isl_obj_bool
,
247 (isc_bin_op_fn
) &set_is_superset
},
248 { ISL_TOKEN_GE
, isl_obj_map
, isl_obj_map
, isl_obj_bool
,
249 (isc_bin_op_fn
) &map_is_superset
},
250 { ISL_TOKEN_GT
, isl_obj_set
, isl_obj_set
, isl_obj_bool
,
251 (isc_bin_op_fn
) &set_is_strict_superset
},
252 { ISL_TOKEN_GT
, isl_obj_map
, isl_obj_map
, isl_obj_bool
,
253 (isc_bin_op_fn
) &map_is_strict_superset
},
254 { '+', isl_obj_pw_qpolynomial
, isl_obj_pw_qpolynomial
,
255 isl_obj_pw_qpolynomial
,
256 (isc_bin_op_fn
) &isl_pw_qpolynomial_add
},
257 { '-', isl_obj_pw_qpolynomial
, isl_obj_pw_qpolynomial
,
258 isl_obj_pw_qpolynomial
,
259 (isc_bin_op_fn
) &isl_pw_qpolynomial_sub
},
260 { '*', isl_obj_pw_qpolynomial
, isl_obj_pw_qpolynomial
,
261 isl_obj_pw_qpolynomial
,
262 (isc_bin_op_fn
) &isl_pw_qpolynomial_mul
},
263 { '*', isl_obj_pw_qpolynomial
, isl_obj_set
,
264 isl_obj_pw_qpolynomial
,
265 (isc_bin_op_fn
) &isl_pw_qpolynomial_intersect_domain
},
266 { '*', isl_obj_pw_qpolynomial_fold
, isl_obj_set
,
267 isl_obj_pw_qpolynomial_fold
,
268 (isc_bin_op_fn
) &isl_pw_qpolynomial_fold_intersect_domain
},
269 { '@', isl_obj_pw_qpolynomial
, isl_obj_set
,
270 isl_obj_pw_qpolynomial
,
271 (isc_bin_op_fn
) &isl_pw_qpolynomial_at
},
272 { '@', isl_obj_pw_qpolynomial_fold
, isl_obj_set
,
273 isl_obj_pw_qpolynomial
,
274 (isc_bin_op_fn
) &isl_pw_qpolynomial_fold_at
},
275 { '%', isl_obj_set
, isl_obj_set
,
277 (isc_bin_op_fn
) &set_gist
},
278 { '%', isl_obj_map
, isl_obj_map
,
280 (isc_bin_op_fn
) &map_gist
},
281 { '%', isl_obj_pw_qpolynomial
, isl_obj_set
,
282 isl_obj_pw_qpolynomial
,
283 (isc_bin_op_fn
) &isl_pw_qpolynomial_gist
},
284 { '%', isl_obj_pw_qpolynomial_fold
, isl_obj_set
,
285 isl_obj_pw_qpolynomial_fold
,
286 (isc_bin_op_fn
) &isl_pw_qpolynomial_fold_gist
},
290 __isl_give isl_set
*set_sample(__isl_take isl_set
*set
)
292 return isl_set_from_basic_set(isl_set_sample(set
));
295 __isl_give isl_map
*map_sample(__isl_take isl_map
*map
)
297 return isl_map_from_basic_map(isl_map_sample(map
));
300 static __isl_give isl_set
*set_affine_hull(__isl_take isl_set
*set
)
302 return isl_set_from_basic_set(isl_set_affine_hull(set
));
305 static __isl_give isl_map
*map_affine_hull(__isl_take isl_map
*map
)
307 return isl_map_from_basic_map(isl_map_affine_hull(map
));
310 typedef void *(*isc_un_op_fn
)(void *arg
);
312 enum isl_token_type op
;
317 struct isc_named_un_op
{
321 struct isc_named_un_op named_un_ops
[] = {
322 {"aff", { -1, isl_obj_map
, isl_obj_map
,
323 (isc_un_op_fn
) &map_affine_hull
} },
324 {"aff", { -1, isl_obj_set
, isl_obj_set
,
325 (isc_un_op_fn
) &set_affine_hull
} },
326 {"card", { -1, isl_obj_set
, isl_obj_pw_qpolynomial
,
327 (isc_un_op_fn
) &isl_set_card
} },
328 {"card", { -1, isl_obj_map
, isl_obj_pw_qpolynomial
,
329 (isc_un_op_fn
) &isl_map_card
} },
330 {"dom", { -1, isl_obj_map
, isl_obj_set
,
331 (isc_un_op_fn
) &isl_map_domain
} },
332 {"dom", { -1, isl_obj_pw_qpolynomial
, isl_obj_set
,
333 (isc_un_op_fn
) &isl_pw_qpolynomial_domain
} },
334 {"dom", { -1, isl_obj_pw_qpolynomial_fold
, isl_obj_set
,
335 (isc_un_op_fn
) &isl_pw_qpolynomial_fold_domain
} },
336 {"ran", { -1, isl_obj_map
, isl_obj_set
,
337 (isc_un_op_fn
) &isl_map_range
} },
338 {"lexmin", { -1, isl_obj_map
, isl_obj_map
,
339 (isc_un_op_fn
) &isl_map_lexmin
} },
340 {"lexmax", { -1, isl_obj_map
, isl_obj_map
,
341 (isc_un_op_fn
) &isl_map_lexmax
} },
342 {"lexmin", { -1, isl_obj_set
, isl_obj_set
,
343 (isc_un_op_fn
) &isl_set_lexmin
} },
344 {"lexmax", { -1, isl_obj_set
, isl_obj_set
,
345 (isc_un_op_fn
) &isl_set_lexmax
} },
346 {"sample", { -1, isl_obj_set
, isl_obj_set
,
347 (isc_un_op_fn
) &set_sample
} },
348 {"sample", { -1, isl_obj_map
, isl_obj_map
,
349 (isc_un_op_fn
) &map_sample
} },
350 {"sum", { -1, isl_obj_pw_qpolynomial
, isl_obj_pw_qpolynomial
,
351 (isc_un_op_fn
) &isl_pw_qpolynomial_sum
} },
353 {"ub", { -1, isl_obj_pw_qpolynomial
, isl_obj_pw_qpolynomial_fold
,
354 (isc_un_op_fn
) &isl_pw_qpolynomial_upper_bound
} },
359 struct isl_named_obj
{
364 static void free_obj(struct isl_obj obj
)
366 obj
.type
->free(obj
.v
);
369 static int same_name(const void *entry
, const void *val
)
371 const struct isl_named_obj
*named
= (const struct isl_named_obj
*)entry
;
373 return !strcmp(named
->name
, val
);
376 static int do_assign(struct isl_ctx
*ctx
, struct isl_hash_table
*table
,
377 char *name
, struct isl_obj obj
)
379 struct isl_hash_table_entry
*entry
;
381 struct isl_named_obj
*named
;
383 name_hash
= isl_hash_string(isl_hash_init(), name
);
384 entry
= isl_hash_table_find(ctx
, table
, name_hash
, same_name
, name
, 1);
389 free_obj(named
->obj
);
392 named
= isl_alloc_type(ctx
, struct isl_named_obj
);
407 static struct isl_obj
stored_obj(struct isl_ctx
*ctx
,
408 struct isl_hash_table
*table
, char *name
)
410 struct isl_obj obj
= { isl_obj_none
, NULL
};
411 struct isl_hash_table_entry
*entry
;
414 name_hash
= isl_hash_string(isl_hash_init(), name
);
415 entry
= isl_hash_table_find(ctx
, table
, name_hash
, same_name
, name
, 0);
417 struct isl_named_obj
*named
;
423 obj
.v
= obj
.type
->copy(obj
.v
);
427 static struct isc_bin_op
*read_bin_op_if_available(struct isl_stream
*s
,
431 struct isl_token
*tok
;
433 tok
= isl_stream_next_token(s
);
440 if (bin_ops
[i
].op
!= tok
->type
)
442 if (bin_ops
[i
].lhs
!= lhs
)
449 isl_stream_push_token(s
, tok
);
454 static struct isc_un_op
*read_prefix_un_op_if_available(struct isl_stream
*s
)
457 struct isl_token
*tok
;
459 tok
= isl_stream_next_token(s
);
464 if (!named_un_ops
[i
].op
.op
)
466 if (named_un_ops
[i
].op
.op
!= tok
->type
)
470 return &named_un_ops
[i
].op
;
473 isl_stream_push_token(s
, tok
);
478 static struct isc_un_op
*find_matching_un_op(struct isc_un_op
*like
,
484 if (!named_un_ops
[i
].op
.op
)
486 if (named_un_ops
[i
].op
.op
!= like
->op
)
488 if (named_un_ops
[i
].op
.arg
!= arg
)
491 return &named_un_ops
[i
].op
;
497 static int is_assign(struct isl_stream
*s
)
499 struct isl_token
*tok
;
500 struct isl_token
*tok2
;
503 tok
= isl_stream_next_token(s
);
506 if (tok
->type
!= ISL_TOKEN_IDENT
) {
507 isl_stream_push_token(s
, tok
);
511 tok2
= isl_stream_next_token(s
);
513 isl_stream_push_token(s
, tok
);
516 assign
= tok2
->type
== ISL_TOKEN_DEF
;
517 isl_stream_push_token(s
, tok2
);
518 isl_stream_push_token(s
, tok
);
523 static struct isl_obj
read_obj(struct isl_stream
*s
,
524 struct isl_hash_table
*table
);
525 static struct isl_obj
read_expr(struct isl_stream
*s
,
526 struct isl_hash_table
*table
);
528 static struct isl_obj
read_un_op_expr(struct isl_stream
*s
,
529 struct isl_hash_table
*table
, struct isc_un_op
*op
)
531 struct isl_obj obj
= { isl_obj_none
, NULL
};
533 obj
= read_obj(s
, table
);
535 op
= find_matching_un_op(op
, obj
.type
);
537 isl_assert(s
->ctx
, op
, goto error
);
538 obj
.v
= op
->fn(obj
.v
);
544 obj
.type
= isl_obj_none
;
549 static struct isl_obj
transitive_closure(struct isl_ctx
*ctx
, struct isl_obj obj
)
551 struct isl_list
*list
;
554 isl_assert(ctx
, obj
.type
== isl_obj_map
, goto error
);
555 list
= isl_list_alloc(ctx
, 2);
559 list
->obj
[0].type
= isl_obj_map
;
560 list
->obj
[0].v
= isl_map_transitive_closure(obj
.v
, &exact
);
561 list
->obj
[1].type
= isl_obj_bool
;
562 list
->obj
[1].v
= exact
? &isl_bool_true
: &isl_bool_false
;
564 obj
.type
= isl_obj_list
;
565 if (exact
< 0 || !list
->obj
[0].v
)
571 obj
.type
= isl_obj_none
;
576 static struct isl_obj
obj_at_index(struct isl_stream
*s
, struct isl_obj obj
)
578 struct isl_list
*list
= obj
.v
;
579 struct isl_token
*tok
;
582 tok
= isl_stream_next_token(s
);
583 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
) {
584 isl_stream_error(s
, tok
, "expecting index");
586 isl_stream_push_token(s
, tok
);
589 i
= isl_int_get_si(tok
->u
.v
);
591 isl_assert(s
, i
< list
->n
, goto error
);
592 if (isl_stream_eat(s
, ']'))
596 obj
.v
= obj
.type
->copy(obj
.v
);
603 obj
.type
= isl_obj_none
;
608 static struct isl_obj
power(struct isl_stream
*s
, struct isl_obj obj
)
610 struct isl_token
*tok
;
612 if (isl_stream_eat_if_available(s
, '+'))
613 return transitive_closure(s
->ctx
, obj
);
615 tok
= isl_stream_next_token(s
);
616 if (!tok
|| tok
->type
!= ISL_TOKEN_VALUE
|| isl_int_cmp_si(tok
->u
.v
, -1)) {
617 isl_stream_error(s
, tok
, "expecting -1");
619 isl_stream_push_token(s
, tok
);
623 isl_assert(s
->ctx
, obj
.type
== isl_obj_map
, goto error
);
625 obj
.v
= isl_map_reverse(obj
.v
);
632 obj
.type
= isl_obj_none
;
637 static struct isl_obj
read_obj(struct isl_stream
*s
,
638 struct isl_hash_table
*table
)
640 struct isl_obj obj
= { isl_obj_none
, NULL
};
642 struct isc_un_op
*op
= NULL
;
644 if (isl_stream_eat_if_available(s
, '(')) {
645 obj
= read_expr(s
, table
);
646 if (isl_stream_eat(s
, ')'))
649 op
= read_prefix_un_op_if_available(s
);
651 return read_un_op_expr(s
, table
, op
);
653 name
= isl_stream_read_ident_if_available(s
);
655 obj
= stored_obj(s
->ctx
, table
, name
);
657 obj
= isl_stream_read_obj(s
);
662 if (isl_stream_eat_if_available(s
, '^'))
664 else if (obj
.type
== isl_obj_list
&& isl_stream_eat_if_available(s
, '['))
665 obj
= obj_at_index(s
, obj
);
670 obj
.type
= isl_obj_none
;
675 static struct isc_bin_op
*find_matching_bin_op(struct isc_bin_op
*like
,
676 isl_obj_type lhs
, isl_obj_type rhs
)
683 if (bin_ops
[i
].op
!= like
->op
)
685 if (bin_ops
[i
].lhs
!= lhs
)
687 if (bin_ops
[i
].rhs
!= rhs
)
696 static struct isl_obj
read_expr(struct isl_stream
*s
,
697 struct isl_hash_table
*table
)
699 struct isl_obj obj
= { isl_obj_none
, NULL
};
700 struct isl_obj right_obj
= { isl_obj_none
, NULL
};
702 obj
= read_obj(s
, table
);
704 struct isc_bin_op
*op
= NULL
;
706 op
= read_bin_op_if_available(s
, obj
.type
);
710 right_obj
= read_obj(s
, table
);
712 op
= find_matching_bin_op(op
, obj
.type
, right_obj
.type
);
714 isl_assert(s
->ctx
, op
, goto error
);
715 obj
.v
= op
->fn(obj
.v
, right_obj
.v
);
723 obj
.type
= isl_obj_none
;
728 static __isl_give isl_printer
*read_line(struct isl_stream
*s
,
729 struct isl_hash_table
*table
, __isl_take isl_printer
*p
)
731 struct isl_obj obj
= { isl_obj_none
, NULL
};
734 struct isc_bin_op
*op
= NULL
;
738 if (isl_stream_is_empty(s
))
741 assign
= is_assign(s
);
743 lhs
= isl_stream_read_ident_if_available(s
);
744 if (isl_stream_eat(s
, ISL_TOKEN_DEF
))
748 obj
= read_expr(s
, table
);
749 if (obj
.type
== isl_obj_none
|| obj
.v
== NULL
)
751 if (isl_stream_eat(s
, ';'))
755 if (do_assign(s
->ctx
, table
, lhs
, obj
))
758 p
= obj
.type
->print(p
, obj
.v
);
759 p
= isl_printer_end_line(p
);
770 int free_cb(void *entry
)
772 struct isl_named_obj
*named
= entry
;
774 free_obj(named
->obj
);
781 static void register_named_ops(struct isl_stream
*s
)
786 if (!named_un_ops
[i
].name
)
788 named_un_ops
[i
].op
.op
= isl_stream_register_keyword(s
,
789 named_un_ops
[i
].name
);
790 assert(named_un_ops
[i
].op
.op
!= ISL_TOKEN_ERROR
);
794 int main(int argc
, char **argv
)
797 struct isl_stream
*s
;
798 struct isl_hash_table
*table
;
801 ctx
= isl_ctx_alloc();
802 s
= isl_stream_new_file(ctx
, stdin
);
804 table
= isl_hash_table_alloc(ctx
, 10);
806 p
= isl_printer_to_file(ctx
, stdout
);
809 register_named_ops(s
);
811 while (!feof(stdin
)) {
812 p
= read_line(s
, table
, p
);
816 isl_hash_table_foreach(ctx
, table
, free_cb
);
817 isl_hash_table_free(ctx
, table
);