iscc.c: union_pw_qpolynomial_upper_bound: fix memory leak in error path

[barvinok.git] / iscc.c

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <isl_obj.h>
#include <isl_stream.h>
#include <isl_vertices.h>
#include <isl_obj_list.h>
#include <barvinok/barvinok.h>

#include "config.h"

#ifdef HAVE_CLOOG
#include <cloog/isl/cloog.h>
#endif

static int isl_bool_false = 0;
static int isl_bool_true = 1;
static int isl_bool_error = -1;

static enum isl_token_type read_op;
static enum isl_token_type vertices_op;

struct isl_arg_choice iscc_format[] = {
        {"isl",         ISL_FORMAT_ISL},
        {"omega",       ISL_FORMAT_OMEGA},
        {"polylib",     ISL_FORMAT_POLYLIB},
        {"latex",       ISL_FORMAT_LATEX},
        {"C",           ISL_FORMAT_C},
        {0}
};

struct iscc_options {
        struct barvinok_options *barvinok;
        unsigned                 format;
};

struct isl_arg iscc_options_arg[] = {
ISL_ARG_CHILD(struct iscc_options, barvinok, "barvinok", barvinok_options_arg,
        "barvinok options")
ISL_ARG_CHOICE(struct iscc_options, format, 0, "format", \
        iscc_format,    ISL_FORMAT_ISL, "output format")
ISL_ARG_END
};

ISL_ARG_DEF(iscc_options, struct iscc_options, iscc_options_arg)

static void *isl_obj_bool_copy(void *v)
{
        return v;
}

static void isl_obj_bool_free(void *v)
{
}

static __isl_give isl_printer *isl_obj_bool_print(__isl_take isl_printer *p,
        void *v)
{
        if (v == &isl_bool_true)
                return isl_printer_print_str(p, "True");
        else if (v == &isl_bool_false)
                return isl_printer_print_str(p, "False");
        else
                return isl_printer_print_str(p, "Error");
}

static void *isl_obj_bool_add(void *v1, void *v2)
{
        return v1;
}

struct isl_obj_vtable isl_obj_bool_vtable = {
        isl_obj_bool_copy,
        isl_obj_bool_add,
        isl_obj_bool_print,
        isl_obj_bool_free
};
#define isl_obj_bool            (&isl_obj_bool_vtable)

int *isl_bool_from_int(int res)
{
        return res < 0 ? &isl_bool_error : res ? &isl_bool_true : &isl_bool_false;
}

int *union_map_is_equal(__isl_take isl_union_map *map1,
        __isl_take isl_union_map *map2)
{
        int res = isl_union_map_is_equal(map1, map2);
        isl_union_map_free(map1);
        isl_union_map_free(map2);
        return isl_bool_from_int(res);
}
int *union_set_is_equal(__isl_take isl_union_set *set1,
        __isl_take isl_union_set *set2)
{
        return union_map_is_equal((isl_union_map *)set1, (isl_union_map *)set2);
}

int *union_map_is_subset(__isl_take isl_union_map *map1,
        __isl_take isl_union_map *map2)
{
        int res = isl_union_map_is_subset(map1, map2);
        isl_union_map_free(map1);
        isl_union_map_free(map2);
        return isl_bool_from_int(res);
}
int *union_set_is_subset(__isl_take isl_union_set *set1,
        __isl_take isl_union_set *set2)
{
        return union_map_is_subset((isl_union_map *)set1, (isl_union_map *)set2);
}

int *union_map_is_strict_subset(__isl_take isl_union_map *map1,
        __isl_take isl_union_map *map2)
{
        int res = isl_union_map_is_strict_subset(map1, map2);
        isl_union_map_free(map1);
        isl_union_map_free(map2);
        return isl_bool_from_int(res);
}
int *union_set_is_strict_subset(__isl_take isl_union_set *set1,
        __isl_take isl_union_set *set2)
{
        return union_map_is_strict_subset((isl_union_map *)set1,
                                          (isl_union_map *)set2);
}

int *union_map_is_superset(__isl_take isl_union_map *map1,
        __isl_take isl_union_map *map2)
{
        return union_map_is_subset(map2, map1);
}
int *union_set_is_superset(__isl_take isl_union_set *set1,
        __isl_take isl_union_set *set2)
{
        return union_set_is_subset(set2, set1);
}

int *union_map_is_strict_superset(__isl_take isl_union_map *map1,
        __isl_take isl_union_map *map2)
{
        return union_map_is_strict_subset(map2, map1);
}
int *union_set_is_strict_superset(__isl_take isl_union_set *set1,
        __isl_take isl_union_set *set2)
{
        return union_set_is_strict_subset(set2, set1);
}

extern struct isl_obj_vtable isl_obj_list_vtable;
#define isl_obj_list            (&isl_obj_list_vtable)

typedef void *(*isc_bin_op_fn)(void *lhs, void *rhs);
struct isc_bin_op {
        enum isl_token_type     op;
        isl_obj_type            lhs;
        isl_obj_type            rhs;
        isl_obj_type            res;
        isc_bin_op_fn           fn;
};
struct isc_named_bin_op {
        char                    *name;
        struct isc_bin_op       op;
};

struct iscc_at {
        isl_union_pw_qpolynomial *upwqp;
        isl_union_pw_qpolynomial *res;
};

static int eval_at(__isl_take isl_point *pnt, void *user)
{
        struct iscc_at *at = (struct iscc_at *) user;
        isl_qpolynomial *qp;
        isl_set *set;

        set = isl_set_from_point(isl_point_copy(pnt));
        qp = isl_union_pw_qpolynomial_eval(
                                isl_union_pw_qpolynomial_copy(at->upwqp), pnt);

        at->res = isl_union_pw_qpolynomial_add(at->res,
                        isl_union_pw_qpolynomial_from_pw_qpolynomial(
                                isl_pw_qpolynomial_alloc(set, qp)));

        return 0;
}

__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_at(
        __isl_take isl_union_pw_qpolynomial *upwqp,
        __isl_take isl_union_set *uset)
{
        struct iscc_at at;

        at.upwqp = upwqp;
        at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));

        isl_union_set_foreach_point(uset, eval_at, &at);

        isl_union_pw_qpolynomial_free(upwqp);
        isl_union_set_free(uset);

        return at.res;
}

struct iscc_fold_at {
        isl_union_pw_qpolynomial_fold *upwf;
        isl_union_pw_qpolynomial *res;
};

static int eval_fold_at(__isl_take isl_point *pnt, void *user)
{
        struct iscc_fold_at *at = (struct iscc_fold_at *) user;
        isl_qpolynomial *qp;
        isl_set *set;

        set = isl_set_from_point(isl_point_copy(pnt));
        qp = isl_union_pw_qpolynomial_fold_eval(
                            isl_union_pw_qpolynomial_fold_copy(at->upwf), pnt);

        at->res = isl_union_pw_qpolynomial_add(at->res,
                        isl_union_pw_qpolynomial_from_pw_qpolynomial(
                                isl_pw_qpolynomial_alloc(set, qp)));

        return 0;
}

__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_fold_at(
        __isl_take isl_union_pw_qpolynomial_fold *upwf,
        __isl_take isl_union_set *uset)
{
        struct iscc_fold_at at;

        at.upwf = upwf;
        at.res = isl_union_pw_qpolynomial_zero(isl_union_set_get_dim(uset));

        isl_union_set_foreach_point(uset, eval_fold_at, &at);

        isl_union_pw_qpolynomial_fold_free(upwf);
        isl_union_set_free(uset);

        return at.res;
}

struct isc_bin_op bin_ops[] = {
        { '+',  isl_obj_union_set,      isl_obj_union_set,
                isl_obj_union_set,
                (isc_bin_op_fn) &isl_union_set_union },
        { '+',  isl_obj_union_map,      isl_obj_union_map,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_union },
        { '-',  isl_obj_union_set,      isl_obj_union_set,
                isl_obj_union_set,
                (isc_bin_op_fn) &isl_union_set_subtract },
        { '-',  isl_obj_union_map,      isl_obj_union_map,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_subtract },
        { '*',  isl_obj_union_set,      isl_obj_union_set,
                isl_obj_union_set,
                (isc_bin_op_fn) &isl_union_set_intersect },
        { '*',  isl_obj_union_map,      isl_obj_union_map,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_intersect },
        { '*',  isl_obj_union_map,      isl_obj_union_set,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_intersect_domain },
        { '.',  isl_obj_union_map,      isl_obj_union_map,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_apply_range },
        { '.',  isl_obj_union_map,      isl_obj_union_pw_qpolynomial,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_map_apply_union_pw_qpolynomial },
        { ISL_TOKEN_TO, isl_obj_union_set,      isl_obj_union_set,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_from_domain_and_range },
        { '=', isl_obj_union_set,       isl_obj_union_set,      isl_obj_bool,
                (isc_bin_op_fn) &union_set_is_equal },
        { '=', isl_obj_union_map,       isl_obj_union_map,      isl_obj_bool,
                (isc_bin_op_fn) &union_map_is_equal },
        { ISL_TOKEN_LE, isl_obj_union_set,      isl_obj_union_set,
                isl_obj_bool, (isc_bin_op_fn) &union_set_is_subset },
        { ISL_TOKEN_LE, isl_obj_union_map,      isl_obj_union_map,
                isl_obj_bool, (isc_bin_op_fn) &union_map_is_subset },
        { ISL_TOKEN_LT, isl_obj_union_set,      isl_obj_union_set,
                isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_subset },
        { ISL_TOKEN_LT, isl_obj_union_map,      isl_obj_union_map,
                isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_subset },
        { ISL_TOKEN_GE, isl_obj_union_set,      isl_obj_union_set,
                isl_obj_bool, (isc_bin_op_fn) &union_set_is_superset },
        { ISL_TOKEN_GE, isl_obj_union_map,      isl_obj_union_map,
                isl_obj_bool, (isc_bin_op_fn) &union_map_is_superset },
        { ISL_TOKEN_GT, isl_obj_union_set,      isl_obj_union_set,
                isl_obj_bool, (isc_bin_op_fn) &union_set_is_strict_superset },
        { ISL_TOKEN_GT, isl_obj_union_map,      isl_obj_union_map,
                isl_obj_bool, (isc_bin_op_fn) &union_map_is_strict_superset },
        { '+',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_add },
        { '-',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_sub },
        { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_union_pw_qpolynomial,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_mul },
        { '*',  isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_intersect_domain },
        { '*',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_union_set,
                isl_obj_union_pw_qpolynomial_fold,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_intersect_domain },
        { '@',  isl_obj_union_pw_qpolynomial, isl_obj_union_set,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_at },
        { '@',  isl_obj_union_pw_qpolynomial_fold, isl_obj_union_set,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_at },
        { '%',  isl_obj_union_set,      isl_obj_union_set,
                isl_obj_union_set,
                (isc_bin_op_fn) &isl_union_set_gist },
        { '%',  isl_obj_union_map,      isl_obj_union_map,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_gist },
        { '%',  isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
                isl_obj_union_pw_qpolynomial,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_gist },
        { '%',  isl_obj_union_pw_qpolynomial_fold,      isl_obj_union_set,
                isl_obj_union_pw_qpolynomial_fold,
                (isc_bin_op_fn) &isl_union_pw_qpolynomial_fold_gist },
        0
};
struct isc_named_bin_op named_bin_ops[] = {
        { "cross",      { -1,   isl_obj_union_set,      isl_obj_union_set,
                isl_obj_union_set,
                (isc_bin_op_fn) &isl_union_set_product } },
        { "cross",      { -1,   isl_obj_union_map,      isl_obj_union_map,
                isl_obj_union_map,
                (isc_bin_op_fn) &isl_union_map_product } },
        NULL
};

__isl_give isl_set *union_set_sample(__isl_take isl_union_set *uset)
{
        return isl_set_from_basic_set(isl_union_set_sample(uset));
}

__isl_give isl_map *union_map_sample(__isl_take isl_union_map *umap)
{
        return isl_map_from_basic_map(isl_union_map_sample(umap));
}

static __isl_give struct isl_list *union_pw_qpolynomial_upper_bound(
        __isl_take isl_union_pw_qpolynomial *upwqp)
{
        isl_ctx *ctx;
        struct isl_list *list;
        int tight;

        ctx = isl_union_pw_qpolynomial_get_ctx(upwqp);
        list = isl_list_alloc(ctx, 2);
        if (!list)
                goto error2;

        list->obj[0].type = isl_obj_union_pw_qpolynomial_fold;
        list->obj[0].v = isl_union_pw_qpolynomial_bound(upwqp,
                                                        isl_fold_max, &tight);
        list->obj[1].type = isl_obj_bool;
        list->obj[1].v = tight ? &isl_bool_true : &isl_bool_false;
        if (tight < 0 || !list->obj[0].v)
                goto error;

        return list;
error2:
        isl_union_pw_qpolynomial_free(upwqp);
error:
        isl_list_free(list);
        return NULL;
}

#ifdef HAVE_CLOOG
struct iscc_codegen_data {
        int nr;
        int nparam;
        int max_iter;
        int n_scat;
        isl_set *context;
        CloogState *state;
        CloogLoop **next;
        CloogBlockList **nextBL;
        CloogScatteringList *scatterings;
        CloogScatteringList **nextScat;
};

static int add_domain(__isl_take isl_map *map, void *user)
{
        struct iscc_codegen_data *data = (struct iscc_codegen_data *)user;
        isl_ctx *ctx = isl_map_get_ctx(map);
        isl_dim *dim;
        isl_set *domain;
        CloogStatement *statement;
        CloogLoop *l;
        CloogScatteringList *s;
        int n_in;

        n_in = isl_map_dim(map, isl_dim_in);
        if (data->nr == 0) {
                isl_dim *dim = isl_map_get_dim(map);
                data->nparam = isl_map_dim(map, isl_dim_param);
                data->n_scat = isl_map_dim(map, isl_dim_out);
                dim = isl_dim_drop_inputs(dim, 0, n_in);
                dim = isl_dim_drop_outputs(dim, 0, data->n_scat);
                data->context = isl_set_universe(dim);
        } else {
                isl_assert(ctx, data->nparam == isl_map_dim(map, isl_dim_param),
                           goto error);
                isl_assert(ctx, data->n_scat == isl_map_dim(map, isl_dim_out),
                           goto error);
        }
        if (n_in > data->max_iter)
                data->max_iter = n_in;

        l = cloog_loop_malloc(data->state);
        if (!l)
                goto error;
        l->next = NULL;
        l->inner = NULL;
        domain = isl_map_domain(isl_map_copy(map));
        l->domain = cloog_domain_from_isl_set(domain);

        statement = cloog_statement_alloc(data->state, data->nr);
        statement->usr = NULL;
        dim = isl_map_get_dim(map);
        statement->name = strdup(isl_dim_get_tuple_name(dim, isl_dim_in));
        isl_dim_free(dim);
        l->block = cloog_block_alloc(statement, 0, NULL, n_in);

        s = isl_alloc_type(ctx, CloogScatteringList);
        s->scatt = cloog_scattering_from_isl_map(map);
        s->next = NULL;

        *data->next = l;
        *data->nextBL = cloog_block_list_alloc((*data->next)->block);
        data->next = &(*data->next)->next;
        data->nextBL = &(*data->nextBL)->next;
        *data->nextScat = s;
        data->nextScat = &(s->next);

        data->nr++;

        return 0;
error:
        return -1;
}

char **generate_names(isl_ctx *ctx, int n, const char *prefix)
{
        int i;
        char **names;
    
        names = isl_alloc_array(ctx, char *, n);
        for (i = 0; i < n; i++) {
                names[i] = isl_alloc_array(ctx, char, 50);
                sprintf(names[i], "%s%d", prefix, i);
        }
  
        return names;
}

void *codegen(void *arg)
{
        int i;
        struct iscc_codegen_data data;
        isl_dim *dim;
        isl_union_map *umap = (isl_union_map *)arg;
        isl_ctx *ctx = isl_union_map_get_ctx(umap);
        CloogOptions *options;
        CloogProgram *p;
        struct clast_stmt *stmt;

        data.state = cloog_isl_state_malloc(ctx);
        options = cloog_options_malloc(data.state);
        options->language = LANGUAGE_C;
        p = cloog_program_malloc();

        isl_assert(ctx, p, goto error);
        p->names = cloog_names_malloc();
        isl_assert(ctx, p->names, goto error2);
        p->language = 'c';

        data.context = NULL;
        data.nr = 0;
        data.nparam = -1;
        data.max_iter = 0;
        data.n_scat = -1;
        data.next = &p->loop;
        data.nextBL = &p->blocklist;
        data.scatterings = NULL;
        data.nextScat = &data.scatterings;

        if (isl_union_map_foreach_map(umap, &add_domain, &data) < 0)
                goto error3;

        if (data.nr == 0)
                goto error3;

        p->names->nb_parameters = data.nparam;
        p->names->parameters = isl_alloc_array(ctx, char *, data.nparam);
        dim = isl_set_get_dim(data.context);
        p->context = cloog_domain_from_isl_set(data.context);
        for (i = 0; i < data.nparam; ++i) {
                const char *s = isl_dim_get_name(dim, isl_dim_param, i);
                p->names->parameters[i] = strdup(s);
        }
        isl_dim_free(dim);

        p->names->nb_iterators = data.max_iter;
        p->names->iterators = generate_names(ctx, data.max_iter, "i");

        p->names->nb_scattering = data.n_scat;
        p->names->scattering = generate_names(ctx, data.n_scat, "c");
        p->names->nb_scalars = 0;
        p->nb_scattdims = data.n_scat;
        p->scaldims = (int *)malloc(p->nb_scattdims*(sizeof(int)));
        for (i = 0; i < p->nb_scattdims; i++)
                p->scaldims[i] = 0;

        cloog_program_scatter(p, data.scatterings, options);
        p = cloog_program_generate(p, options);

        stmt = cloog_clast_create(p, options);
        clast_pprint(stdout, stmt, 0, options);
        cloog_clast_free(stmt);

error3:
        cloog_scattering_list_free(data.scatterings);
error2:
        cloog_program_free(p);
error:
        cloog_options_free(options);
        cloog_state_free(data.state);
        isl_union_map_free(umap);
        return NULL;
}
#endif

typedef void *(*isc_un_op_fn)(void *arg);
struct isc_un_op {
        enum isl_token_type     op;
        isl_obj_type            arg;
        isl_obj_type            res;
        isc_un_op_fn            fn;
};
struct isc_named_un_op {
        char                    *name;
        struct isc_un_op        op;
};
struct isc_named_un_op named_un_ops[] = {
        {"aff", { -1,   isl_obj_union_map,      isl_obj_union_map,
                (isc_un_op_fn) &isl_union_map_affine_hull } },
        {"aff", { -1,   isl_obj_union_set,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_set_affine_hull } },
        {"card",        { -1,   isl_obj_union_set,
                isl_obj_union_pw_qpolynomial,
                (isc_un_op_fn) &isl_union_set_card } },
        {"card",        { -1,   isl_obj_union_map,
                isl_obj_union_pw_qpolynomial,
                (isc_un_op_fn) &isl_union_map_card } },
        {"coalesce",    { -1,   isl_obj_union_set,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_set_coalesce } },
        {"coalesce",    { -1,   isl_obj_union_map,      isl_obj_union_map,
                (isc_un_op_fn) &isl_union_map_coalesce } },
        {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial,
                isl_obj_union_pw_qpolynomial,
                (isc_un_op_fn) &isl_union_pw_qpolynomial_coalesce } },
        {"coalesce",    { -1,   isl_obj_union_pw_qpolynomial_fold,
                isl_obj_union_pw_qpolynomial_fold,
                (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_coalesce } },
#ifdef HAVE_CLOOG
        {"codegen",     { -1,   isl_obj_union_map, isl_obj_none, &codegen } },
#endif
        {"deltas",      { -1,   isl_obj_union_map,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_map_deltas } },
        {"dom", { -1,   isl_obj_union_map,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_map_domain } },
        {"dom", { -1,   isl_obj_union_pw_qpolynomial,   isl_obj_union_set,
                (isc_un_op_fn) &isl_union_pw_qpolynomial_domain } },
        {"dom", { -1,   isl_obj_union_pw_qpolynomial_fold,
                isl_obj_union_set,
                (isc_un_op_fn) &isl_union_pw_qpolynomial_fold_domain } },
        {"ran", { -1,   isl_obj_union_map,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_map_range } },
        {"lexmin",      { -1,   isl_obj_union_map,      isl_obj_union_map,
                (isc_un_op_fn) &isl_union_map_lexmin } },
        {"lexmax",      { -1,   isl_obj_union_map,      isl_obj_union_map,
                (isc_un_op_fn) &isl_union_map_lexmax } },
        {"lexmin",      { -1,   isl_obj_union_set,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_set_lexmin } },
        {"lexmax",      { -1,   isl_obj_union_set,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_set_lexmax } },
        {"sample",      { -1,   isl_obj_union_set,      isl_obj_set,
                (isc_un_op_fn) &union_set_sample } },
        {"sample",      { -1,   isl_obj_union_map,      isl_obj_map,
                (isc_un_op_fn) &union_map_sample } },
        {"sum",         { -1,   isl_obj_union_pw_qpolynomial,
                isl_obj_union_pw_qpolynomial,
                (isc_un_op_fn) &isl_union_pw_qpolynomial_sum } },
        {"ub",          { -1,   isl_obj_union_pw_qpolynomial, isl_obj_list,
                (isc_un_op_fn) &union_pw_qpolynomial_upper_bound } },
        {"unwrap",      { -1,   isl_obj_union_set,      isl_obj_union_map,
                (isc_un_op_fn) &isl_union_set_unwrap } },
        {"wrap",        { -1,   isl_obj_union_map,      isl_obj_union_set,
                (isc_un_op_fn) &isl_union_map_wrap } },
        NULL
};

struct isl_named_obj {
        char            *name;
        struct isl_obj  obj;
};

static void free_obj(struct isl_obj obj)
{
        obj.type->free(obj.v);
}

static int same_name(const void *entry, const void *val)
{
        const struct isl_named_obj *named = (const struct isl_named_obj *)entry;

        return !strcmp(named->name, val);
}

static int do_assign(struct isl_ctx *ctx, struct isl_hash_table *table,
        char *name, struct isl_obj obj)
{
        struct isl_hash_table_entry *entry;
        uint32_t name_hash;
        struct isl_named_obj *named;

        name_hash = isl_hash_string(isl_hash_init(), name);
        entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 1);
        if (!entry)
                goto error;
        if (entry->data) {
                named = entry->data;
                free_obj(named->obj);
                free(name);
        } else {
                named = isl_alloc_type(ctx, struct isl_named_obj);
                if (!named)
                        goto error;
                named->name = name;
                entry->data = named;
        }
        named->obj = obj;

        return 0;
error:
        free_obj(obj);
        free(name);
        return -1;
}

static struct isl_obj stored_obj(struct isl_ctx *ctx,
        struct isl_hash_table *table, char *name)
{
        struct isl_obj obj = { isl_obj_none, NULL };
        struct isl_hash_table_entry *entry;
        uint32_t name_hash;

        name_hash = isl_hash_string(isl_hash_init(), name);
        entry = isl_hash_table_find(ctx, table, name_hash, same_name, name, 0);
        if (entry) {
                struct isl_named_obj *named;
                named = entry->data;
                obj = named->obj;
        }

        free(name);
        obj.v = obj.type->copy(obj.v);
        return obj;
}

static int is_subtype(struct isl_obj obj, isl_obj_type super)
{
        if (obj.type == super)
                return 1;
        if (obj.type == isl_obj_map && super == isl_obj_union_map)
                return 1;
        if (obj.type == isl_obj_set && super == isl_obj_union_set)
                return 1;
        if (obj.type == isl_obj_pw_qpolynomial &&
            super == isl_obj_union_pw_qpolynomial)
                return 1;
        if (obj.type == isl_obj_pw_qpolynomial_fold &&
            super == isl_obj_union_pw_qpolynomial_fold)
                return 1;
        if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v))
                return 1;
        return 0;
}

static struct isl_obj convert(struct isl_obj obj, isl_obj_type type)
{
        if (obj.type == type)
                return obj;
        if (obj.type == isl_obj_map && type == isl_obj_union_map) {
                obj.type = isl_obj_union_map;
                obj.v = isl_union_map_from_map(obj.v);
                return obj;
        }
        if (obj.type == isl_obj_set && type == isl_obj_union_set) {
                obj.type = isl_obj_union_set;
                obj.v = isl_union_set_from_set(obj.v);
                return obj;
        }
        if (obj.type == isl_obj_pw_qpolynomial &&
            type == isl_obj_union_pw_qpolynomial) {
                obj.type = isl_obj_union_pw_qpolynomial;
                obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
                return obj;
        }
        if (obj.type == isl_obj_pw_qpolynomial_fold &&
            type == isl_obj_union_pw_qpolynomial_fold) {
                obj.type = isl_obj_union_pw_qpolynomial_fold;
                obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
                return obj;
        }
        if (obj.type == isl_obj_union_set && isl_union_set_is_empty(obj.v)) {
                if (type == isl_obj_union_map) {
                        obj.type = isl_obj_union_map;
                        return obj;
                }
                if (type == isl_obj_union_pw_qpolynomial) {
                        isl_dim *dim = isl_union_set_get_dim(obj.v);
                        isl_union_set_free(obj.v);
                        obj.v = isl_union_pw_qpolynomial_zero(dim);
                        obj.type = isl_obj_union_pw_qpolynomial;
                        return obj;
                }
                if (type == isl_obj_union_pw_qpolynomial_fold) {
                        isl_dim *dim = isl_union_set_get_dim(obj.v);
                        isl_union_set_free(obj.v);
                        obj.v = isl_union_pw_qpolynomial_fold_zero(dim);
                        obj.type = isl_obj_union_pw_qpolynomial_fold;
                        return obj;
                }
        }
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isc_bin_op *read_bin_op_if_available(struct isl_stream *s,
        struct isl_obj lhs)
{
        int i;
        struct isl_token *tok;

        tok = isl_stream_next_token(s);
        if (!tok)
                return NULL;

        for (i = 0; ; ++i) {
                if (!bin_ops[i].op)
                        break;
                if (bin_ops[i].op != tok->type)
                        continue;
                if (!is_subtype(lhs, bin_ops[i].lhs))
                        continue;

                isl_token_free(tok);
                return &bin_ops[i];
        }

        for (i = 0; ; ++i) {
                if (!named_bin_ops[i].name)
                        break;
                if (named_bin_ops[i].op.op != tok->type)
                        continue;
                if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
                        continue;

                isl_token_free(tok);
                return &named_bin_ops[i].op;
        }

        isl_stream_push_token(s, tok);

        return NULL;
}

static struct isc_un_op *read_prefix_un_op_if_available(struct isl_stream *s)
{
        int i;
        struct isl_token *tok;

        tok = isl_stream_next_token(s);
        if (!tok)
                return NULL;

        for (i = 0; ; ++i) {
                if (!named_un_ops[i].name)
                        break;
                if (named_un_ops[i].op.op != tok->type)
                        continue;

                isl_token_free(tok);
                return &named_un_ops[i].op;
        }

        isl_stream_push_token(s, tok);

        return NULL;
}

static struct isc_un_op *find_matching_un_op(struct isc_un_op *like,
        struct isl_obj arg)
{
        int i;

        for (i = 0; ; ++i) {
                if (!named_un_ops[i].name)
                        break;
                if (named_un_ops[i].op.op != like->op)
                        continue;
                if (!is_subtype(arg, named_un_ops[i].op.arg))
                        continue;

                return &named_un_ops[i].op;
        }

        return NULL;
}

static int is_assign(struct isl_stream *s)
{
        struct isl_token *tok;
        struct isl_token *tok2;
        int assign;

        tok = isl_stream_next_token(s);
        if (!tok)
                return 0;
        if (tok->type != ISL_TOKEN_IDENT) {
                isl_stream_push_token(s, tok);
                return 0;
        }

        tok2 = isl_stream_next_token(s);
        if (!tok2) {
                isl_stream_push_token(s, tok);
                return 0;
        }
        assign = tok2->type == ISL_TOKEN_DEF;
        isl_stream_push_token(s, tok2);
        isl_stream_push_token(s, tok);

        return assign;
}

static struct isl_obj read_obj(struct isl_stream *s,
        struct isl_hash_table *table);
static struct isl_obj read_expr(struct isl_stream *s,
        struct isl_hash_table *table);

static struct isl_obj read_un_op_expr(struct isl_stream *s,
        struct isl_hash_table *table, struct isc_un_op *op)
{
        struct isl_obj obj = { isl_obj_none, NULL };

        obj = read_obj(s, table);
        if (!obj.v)
                goto error;

        op = find_matching_un_op(op, obj);

        isl_assert(s->ctx, op, goto error);
        obj = convert(obj, op->arg);
        obj.v = op->fn(obj.v);
        obj.type = op->res;

        return obj;
error:
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isl_obj transitive_closure(struct isl_ctx *ctx, struct isl_obj obj)
{
        struct isl_list *list;
        int exact;

        if (obj.type == isl_obj_map)
                obj = convert(obj, isl_obj_union_map);
        isl_assert(ctx, obj.type == isl_obj_union_map, goto error);
        list = isl_list_alloc(ctx, 2);
        if (!list)
                goto error;

        list->obj[0].type = isl_obj_union_map;
        list->obj[0].v = isl_union_map_transitive_closure(obj.v, &exact);
        list->obj[1].type = isl_obj_bool;
        list->obj[1].v = exact ? &isl_bool_true : &isl_bool_false;
        obj.v = list;
        obj.type = isl_obj_list;
        if (exact < 0 || !list->obj[0].v)
                goto error;

        return obj;
error:
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isl_obj obj_at_index(struct isl_stream *s, struct isl_obj obj)
{
        struct isl_list *list = obj.v;
        struct isl_token *tok;
        int i;

        tok = isl_stream_next_token(s);
        if (!tok || tok->type != ISL_TOKEN_VALUE) {
                isl_stream_error(s, tok, "expecting index");
                if (tok)
                        isl_stream_push_token(s, tok);
                goto error;
        }
        i = isl_int_get_si(tok->u.v);
        isl_token_free(tok);
        isl_assert(s->ctx, i < list->n, goto error);
        if (isl_stream_eat(s, ']'))
                goto error;

        obj = list->obj[i];
        obj.v = obj.type->copy(obj.v);

        isl_list_free(list);

        return obj;
error:
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isl_obj apply(struct isl_stream *s, __isl_take isl_union_map *umap,
        struct isl_hash_table *table)
{
        struct isl_obj obj;

        obj = read_expr(s, table);
        isl_assert(s->ctx, is_subtype(obj, isl_obj_union_set) ||
                           is_subtype(obj, isl_obj_union_map), goto error);

        if (obj.type == isl_obj_set)
                obj = convert(obj, isl_obj_union_set);
        else if (obj.type == isl_obj_map)
                obj = convert(obj, isl_obj_union_map);
        if (obj.type == isl_obj_union_set) {
                obj.v = isl_union_set_apply(obj.v, umap);
        } else
                obj.v = isl_union_map_apply_range(obj.v, umap);
        if (!obj.v)
                goto error2;

        if (isl_stream_eat(s, ')'))
                goto error2;

        return obj;
error:
        isl_union_map_free(umap);
error2:
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

struct add_vertex_data {
        struct isl_list *list;
        int i;
};

static int add_vertex(__isl_take isl_vertex *vertex, void *user)
{
        struct add_vertex_data *data = (struct add_vertex_data *)user;
        isl_basic_set *expr;

        expr = isl_vertex_get_expr(vertex);

        data->list->obj[data->i].type = isl_obj_set;
        data->list->obj[data->i].v = isl_set_from_basic_set(expr);
        data->i++;

        isl_vertex_free(vertex);

        return 0;
}

static struct isl_obj vertices(struct isl_stream *s,
        struct isl_hash_table *table)
{
        isl_ctx *ctx;
        struct isl_obj obj;
        isl_set *set;
        isl_basic_set *hull;
        isl_vertices *vertices = NULL;
        struct isl_list *list = NULL;
        struct add_vertex_data data;

        obj = read_expr(s, table);
        isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
        set = obj.v;
        obj.v = NULL;
        set = isl_set_remove_divs(set);
        hull = isl_set_convex_hull(set);
        vertices = isl_basic_set_compute_vertices(hull);
        isl_basic_set_free(hull);

        ctx = isl_vertices_get_ctx(vertices);
        list = isl_list_alloc(ctx, isl_vertices_get_n_vertices(vertices));
        if (!list)
                goto error;

        data.list = list;
        data.i = 0;

        if (isl_vertices_foreach_vertex(vertices, &add_vertex, &data) < 0)
                goto error;

        isl_vertices_free(vertices);

        obj.type = isl_obj_list;
        obj.v = list;

        return obj;
error:
        isl_vertices_free(vertices);
        isl_list_free(list);
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isl_obj power(struct isl_stream *s, struct isl_obj obj)
{
        struct isl_token *tok;

        if (isl_stream_eat_if_available(s, '+'))
                return transitive_closure(s->ctx, obj);

        tok = isl_stream_next_token(s);
        if (!tok || tok->type != ISL_TOKEN_VALUE || isl_int_cmp_si(tok->u.v, -1)) {
                isl_stream_error(s, tok, "expecting -1");
                if (tok)
                        isl_stream_push_token(s, tok);
                goto error;
        }
        isl_token_free(tok);
        isl_assert(s->ctx, is_subtype(obj, isl_obj_union_map), goto error);
        if (obj.type != isl_obj_union_map)
                obj = convert(obj, isl_obj_union_map);

        obj.v = isl_union_map_reverse(obj.v);
        if (!obj.v)
                goto error;

        return obj;
error:
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isl_obj read_from_file(struct isl_stream *s)
{
        struct isl_obj obj;
        struct isl_token *tok;
        struct isl_stream *s_file;
        FILE *file;

        tok = isl_stream_next_token(s);
        if (!tok || tok->type != ISL_TOKEN_STRING) {
                isl_stream_error(s, tok, "expecting filename");
                isl_token_free(tok);
                goto error;
        }

        file = fopen(tok->u.s, "r");
        isl_token_free(tok);
        isl_assert(s->ctx, file, goto error);

        s_file = isl_stream_new_file(s->ctx, file);
        if (!s_file) {
                fclose(file);
                goto error;
        }

        obj = isl_stream_read_obj(s_file);

        isl_stream_free(s_file);
        fclose(file);

        return obj;
error:
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isl_obj read_obj(struct isl_stream *s,
        struct isl_hash_table *table)
{
        struct isl_obj obj = { isl_obj_none, NULL };
        char *name = NULL;
        struct isc_un_op *op = NULL;

        if (isl_stream_eat_if_available(s, '(')) {
                obj = read_expr(s, table);
                if (!obj.v || isl_stream_eat(s, ')'))
                        goto error;
        } else {
                op = read_prefix_un_op_if_available(s);
                if (op)
                        return read_un_op_expr(s, table, op);

                if (isl_stream_eat_if_available(s, read_op))
                        return read_from_file(s);
                if (isl_stream_eat_if_available(s, vertices_op))
                        return vertices(s, table);

                name = isl_stream_read_ident_if_available(s);
                if (name)
                        obj = stored_obj(s->ctx, table, name);
                else
                        obj = isl_stream_read_obj(s);
                if (!obj.v)
                        goto error;
        }

        if (isl_stream_eat_if_available(s, '^'))
                obj = power(s, obj);
        else if (obj.type == isl_obj_list && isl_stream_eat_if_available(s, '['))
                obj = obj_at_index(s, obj);
        else if (is_subtype(obj, isl_obj_union_map) &&
                 isl_stream_eat_if_available(s, '(')) {
                obj = convert(obj, isl_obj_union_map);
                obj = apply(s, obj.v, table);
        }

        return obj;
error:
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static struct isc_bin_op *find_matching_bin_op(struct isc_bin_op *like,
        struct isl_obj lhs, struct isl_obj rhs)
{
        int i;

        for (i = 0; ; ++i) {
                if (!bin_ops[i].op)
                        break;
                if (bin_ops[i].op != like->op)
                        continue;
                if (!is_subtype(lhs, bin_ops[i].lhs))
                        continue;
                if (!is_subtype(rhs, bin_ops[i].rhs))
                        continue;

                return &bin_ops[i];
        }

        for (i = 0; ; ++i) {
                if (!named_bin_ops[i].name)
                        break;
                if (named_bin_ops[i].op.op != like->op)
                        continue;
                if (!is_subtype(lhs, named_bin_ops[i].op.lhs))
                        continue;
                if (!is_subtype(rhs, named_bin_ops[i].op.rhs))
                        continue;

                return &named_bin_ops[i].op;
        }

        return NULL;
}

static struct isl_obj read_expr(struct isl_stream *s,
        struct isl_hash_table *table)
{
        struct isl_obj obj = { isl_obj_none, NULL };
        struct isl_obj right_obj = { isl_obj_none, NULL };

        obj = read_obj(s, table);
        for (; obj.v;) {
                struct isc_bin_op *op = NULL;

                op = read_bin_op_if_available(s, obj);
                if (!op)
                        break;

                right_obj = read_obj(s, table);

                op = find_matching_bin_op(op, obj, right_obj);

                isl_assert(s->ctx, op, goto error);
                obj = convert(obj, op->lhs);
                right_obj = convert(right_obj, op->rhs);
                obj.v = op->fn(obj.v, right_obj.v);
                obj.type = op->res;
        }

        return obj;
error:
        free_obj(right_obj);
        free_obj(obj);
        obj.type = isl_obj_none;
        obj.v = NULL;
        return obj;
}

static __isl_give isl_printer *read_line(struct isl_stream *s,
        struct isl_hash_table *table, __isl_take isl_printer *p)
{
        struct isl_obj obj = { isl_obj_none, NULL };
        char *lhs = NULL;
        int assign = 0;
        struct isc_bin_op *op = NULL;

        if (!p)
                return NULL;
        if (isl_stream_is_empty(s))
                return p;

        assign = is_assign(s);
        if (assign) {
                lhs = isl_stream_read_ident_if_available(s);
                if (isl_stream_eat(s, ISL_TOKEN_DEF))
                        goto error;
        }

        obj = read_expr(s, table);
        if (obj.type == isl_obj_none || obj.v == NULL)
                goto error;
        if (isl_stream_eat(s, ';'))
                goto error;

        if (assign) {
                if (do_assign(s->ctx, table, lhs, obj))
                        return;
        } else {
                p = obj.type->print(p, obj.v);
                p = isl_printer_end_line(p);
                free_obj(obj);
        }

        return p;
error:
        isl_stream_flush_tokens(s);
        isl_stream_skip_line(s);
        free(lhs);
        free_obj(obj);
        return p;
}

int free_cb(void **entry, void *user)
{
        struct isl_named_obj *named = *entry;

        free_obj(named->obj);
        free(named->name);
        free(named);

        return 0;
}

static void register_named_ops(struct isl_stream *s)
{
        int i;

        read_op = isl_stream_register_keyword(s, "read");
        assert(read_op != ISL_TOKEN_ERROR);
        vertices_op = isl_stream_register_keyword(s, "vertices");
        assert(vertices_op != ISL_TOKEN_ERROR);

        for (i = 0; ; ++i) {
                if (!named_un_ops[i].name)
                        break;
                named_un_ops[i].op.op = isl_stream_register_keyword(s,
                                                        named_un_ops[i].name);
                assert(named_un_ops[i].op.op != ISL_TOKEN_ERROR);
        }

        for (i = 0; ; ++i) {
                if (!named_bin_ops[i].name)
                        break;
                named_bin_ops[i].op.op = isl_stream_register_keyword(s,
                                                        named_bin_ops[i].name);
                assert(named_bin_ops[i].op.op != ISL_TOKEN_ERROR);
        }
}

int main(int argc, char **argv)
{
        struct isl_ctx *ctx;
        struct isl_stream *s;
        struct isl_hash_table *table;
        struct iscc_options *options;
        isl_printer *p;

        options = iscc_options_new_with_defaults();
        assert(options);
        argc = iscc_options_parse(options, argc, argv, ISL_ARG_ALL);

        ctx = isl_ctx_alloc_with_options(iscc_options_arg, options);
        s = isl_stream_new_file(ctx, stdin);
        assert(s);
        table = isl_hash_table_alloc(ctx, 10);
        assert(table);
        p = isl_printer_to_file(ctx, stdout);
        p = isl_printer_set_output_format(p, options->format);
        assert(p);

        register_named_ops(s);

        while (!s->eof) {
                p = read_line(s, table, p);
        }

        isl_printer_free(p);
        isl_hash_table_foreach(ctx, table, free_cb, NULL);
        isl_hash_table_free(ctx, table);
        isl_stream_free(s);
        isl_ctx_free(ctx);

        return 0;
}