/*

 * Copyright 2008-2009 Katholieke Universiteit Leuven

 * Copyright 2010      INRIA Saclay

 * Copyright 2013-2014 Ecole Normale Superieure

 *

 * Use of this software is governed by the MIT license

 *

 * Written by Sven Verdoolaege, K.U.Leuven, Departement

 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium

 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,

 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 

 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France

 */

#include <stdlib.h>

#include <string.h>

#include <isl_space_private.h>

#include <isl_id_private.h>

#include <isl_reordering.h>

isl_ctx *isl_space_get_ctx(__isl_keep isl_space *dim)

{

	return dim ? dim->ctx : NULL;

}

__isl_give isl_space *isl_space_alloc(isl_ctx *ctx,

			unsigned nparam, unsigned n_in, unsigned n_out)

{

	isl_space *dim;

	dim = isl_alloc_type(ctx, struct isl_space);

	if (!dim)

		return NULL;

	dim->ctx = ctx;

	isl_ctx_ref(ctx);

	dim->ref = 1;

	dim->nparam = nparam;

	dim->n_in = n_in;

	dim->n_out = n_out;

	dim->tuple_id[0] = NULL;

	dim->tuple_id[1] = NULL;

	dim->nested[0] = NULL;

	dim->nested[1] = NULL;

	dim->n_id = 0;

	dim->ids = NULL;

	return dim;

}

/* Mark the space as being that of a set, by setting the domain tuple

 * to isl_id_none.

 */

static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)

{

	space = isl_space_cow(space);

	if (!space)

		return NULL;

	space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);

	return space;

}

/* Is the space that of a set?

 */

int isl_space_is_set(__isl_keep isl_space *space)

{

	if (!space)

		return -1;

	if (space->n_in != 0 || space->nested[0])

		return 0;

	if (space->tuple_id[0] != &isl_id_none)

		return 0;

	return 1;

}

/* Is the given space that of a map?

 */

int isl_space_is_map(__isl_keep isl_space *space)

{

	if (!space)

		return -1;

	return space->tuple_id[0] != &isl_id_none &&

		space->tuple_id[1] != &isl_id_none;

}

__isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,

			unsigned nparam, unsigned dim)

{

	isl_space *space;

	space = isl_space_alloc(ctx, nparam, 0, dim);

	space = mark_as_set(space);

	return space;

}

/* Mark the space as being that of a parameter domain, by setting

 * both tuples to isl_id_none.

 */

static __isl_give isl_space *mark_as_params(isl_space *space)

{

	if (!space)

		return NULL;

	space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);

	space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);

	return space;

}

/* Is the space that of a parameter domain?

 */

int isl_space_is_params(__isl_keep isl_space *space)

{

	if (!space)

		return -1;

	if (space->n_in != 0 || space->nested[0] ||

	    space->n_out != 0 || space->nested[1])

		return 0;

	if (space->tuple_id[0] != &isl_id_none)

		return 0;

	if (space->tuple_id[1] != &isl_id_none)

		return 0;

	return 1;

}

/* Create a space for a parameter domain.

 */

__isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)

{

	isl_space *space;

	space = isl_space_alloc(ctx, nparam, 0, 0);

	space = mark_as_params(space);

	return space;

}

static unsigned global_pos(__isl_keep isl_space *dim,

				 enum isl_dim_type type, unsigned pos)

{

	struct isl_ctx *ctx = dim->ctx;

	switch (type) {

	case isl_dim_param:

		isl_assert(ctx, pos < dim->nparam,

			    return isl_space_dim(dim, isl_dim_all));

		return pos;

	case isl_dim_in:

		isl_assert(ctx, pos < dim->n_in,

			    return isl_space_dim(dim, isl_dim_all));

		return pos + dim->nparam;

	case isl_dim_out:

		isl_assert(ctx, pos < dim->n_out,

			    return isl_space_dim(dim, isl_dim_all));

		return pos + dim->nparam + dim->n_in;

	default:

		isl_assert(ctx, 0, return isl_space_dim(dim, isl_dim_all));

	}

	return isl_space_dim(dim, isl_dim_all);

}

/* Extend length of ids array to the total number of dimensions.

 */

static __isl_give isl_space *extend_ids(__isl_take isl_space *dim)

{

	isl_id **ids;

	int i;

	if (isl_space_dim(dim, isl_dim_all) <= dim->n_id)

		return dim;

	if (!dim->ids) {

		dim->ids = isl_calloc_array(dim->ctx,

				isl_id *, isl_space_dim(dim, isl_dim_all));

		if (!dim->ids)

			goto error;

	} else {

		ids = isl_realloc_array(dim->ctx, dim->ids,

				isl_id *, isl_space_dim(dim, isl_dim_all));

		if (!ids)

			goto error;

		dim->ids = ids;

		for (i = dim->n_id; i < isl_space_dim(dim, isl_dim_all); ++i)

			dim->ids[i] = NULL;

	}

	dim->n_id = isl_space_dim(dim, isl_dim_all);

	return dim;

error:

	isl_space_free(dim);

	return NULL;

}

static __isl_give isl_space *set_id(__isl_take isl_space *dim,

	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)

{

	dim = isl_space_cow(dim);

	if (!dim)

		goto error;

	pos = global_pos(dim, type, pos);

	if (pos == isl_space_dim(dim, isl_dim_all))

		goto error;

	if (pos >= dim->n_id) {

		if (!id)

			return dim;

		dim = extend_ids(dim);

		if (!dim)

			goto error;

	}

	dim->ids[pos] = id;

	return dim;

error:

	isl_id_free(id);

	isl_space_free(dim);

	return NULL;

}

static __isl_keep isl_id *get_id(__isl_keep isl_space *dim,

				 enum isl_dim_type type, unsigned pos)

{

	if (!dim)

		return NULL;

	pos = global_pos(dim, type, pos);

	if (pos == isl_space_dim(dim, isl_dim_all))

		return NULL;

	if (pos >= dim->n_id)

		return NULL;

	return dim->ids[pos];

}

static unsigned offset(__isl_keep isl_space *dim, enum isl_dim_type type)

{

	switch (type) {

	case isl_dim_param:	return 0;

	case isl_dim_in:	return dim->nparam;

	case isl_dim_out:	return dim->nparam + dim->n_in;

	default:		return 0;

	}

}

static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)

{

	switch (type) {

	case isl_dim_param:	return dim->nparam;

	case isl_dim_in:	return dim->n_in;

	case isl_dim_out:	return dim->n_out;

	case isl_dim_all:	return dim->nparam + dim->n_in + dim->n_out;

	default:		return 0;

	}

}

unsigned isl_space_dim(__isl_keep isl_space *dim, enum isl_dim_type type)

{

	if (!dim)

		return 0;

	return n(dim, type);

}

unsigned isl_space_offset(__isl_keep isl_space *dim, enum isl_dim_type type)

{

	if (!dim)

		return 0;

	return offset(dim, type);

}

static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,

	enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,

	enum isl_dim_type src_type)

{

	int i;

	isl_id *id;

	if (!dst)

		return NULL;

	for (i = 0; i < n(src, src_type); ++i) {

		id = get_id(src, src_type, i);

		if (!id)

			continue;

		dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));

		if (!dst)

			return NULL;

	}

	return dst;

}

__isl_take isl_space *isl_space_dup(__isl_keep isl_space *dim)

{

	isl_space *dup;

	if (!dim)

		return NULL;

	dup = isl_space_alloc(dim->ctx, dim->nparam, dim->n_in, dim->n_out);

	if (!dup)

		return NULL;

	if (dim->tuple_id[0] &&

	    !(dup->tuple_id[0] = isl_id_copy(dim->tuple_id[0])))

		goto error;

	if (dim->tuple_id[1] &&

	    !(dup->tuple_id[1] = isl_id_copy(dim->tuple_id[1])))

		goto error;

	if (dim->nested[0] && !(dup->nested[0] = isl_space_copy(dim->nested[0])))

		goto error;

	if (dim->nested[1] && !(dup->nested[1] = isl_space_copy(dim->nested[1])))

		goto error;

	if (!dim->ids)

		return dup;

	dup = copy_ids(dup, isl_dim_param, 0, dim, isl_dim_param);

	dup = copy_ids(dup, isl_dim_in, 0, dim, isl_dim_in);

	dup = copy_ids(dup, isl_dim_out, 0, dim, isl_dim_out);

	return dup;

error:

	isl_space_free(dup);

	return NULL;

}

__isl_give isl_space *isl_space_cow(__isl_take isl_space *dim)

{

	if (!dim)

		return NULL;

	if (dim->ref == 1)

		return dim;

	dim->ref--;

	return isl_space_dup(dim);

}

__isl_give isl_space *isl_space_copy(__isl_keep isl_space *dim)

{

	if (!dim)

		return NULL;

	dim->ref++;

	return dim;

}

__isl_null isl_space *isl_space_free(__isl_take isl_space *space)

{

	int i;

	if (!space)

		return NULL;

	if (--space->ref > 0)

		return NULL;

	isl_id_free(space->tuple_id[0]);

	isl_id_free(space->tuple_id[1]);

	isl_space_free(space->nested[0]);

	isl_space_free(space->nested[1]);

	for (i = 0; i < space->n_id; ++i)

		isl_id_free(space->ids[i]);

	free(space->ids);

	isl_ctx_deref(space->ctx);

	free(space);

	return NULL;

}

/* Check if "s" is a valid dimension or tuple name.

 * We currently only forbid names that look like a number.

 *

 * s is assumed to be non-NULL.

 */

static int name_ok(isl_ctx *ctx, const char *s)

{

	char *p;

	long dummy;

	dummy = strtol(s, &p, 0);

	if (p != s)

		isl_die(ctx, isl_error_invalid, "name looks like a number",

			return 0);

	return 1;

}

/* Is it possible for the given dimension type to have a tuple id?

 */

static int space_can_have_id(__isl_keep isl_space *space,

	enum isl_dim_type type)

{

	if (!space)

		return 0;

	if (isl_space_is_params(space))

		isl_die(space->ctx, isl_error_invalid,

			"parameter spaces don't have tuple ids", return 0);

	if (isl_space_is_set(space) && type != isl_dim_set)

		isl_die(space->ctx, isl_error_invalid,

			"set spaces can only have a set id", return 0);

	if (type != isl_dim_in && type != isl_dim_out)

		isl_die(space->ctx, isl_error_invalid,

			"only input, output and set tuples can have ids",

			return 0);

	return 1;

}

/* Does the tuple have an id?

 */

int isl_space_has_tuple_id(__isl_keep isl_space *dim, enum isl_dim_type type)

{

	if (!space_can_have_id(dim, type))

		return -1;

	return dim->tuple_id[type - isl_dim_in] != NULL;

}

__isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *dim,

	enum isl_dim_type type)

{

	int has_id;

	if (!dim)

		return NULL;

	has_id = isl_space_has_tuple_id(dim, type);

	if (has_id < 0)

		return NULL;

	if (!has_id)

		isl_die(dim->ctx, isl_error_invalid,

			"tuple has no id", return NULL);

	return isl_id_copy(dim->tuple_id[type - isl_dim_in]);

}

__isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *dim,

	enum isl_dim_type type, __isl_take isl_id *id)

{

	dim = isl_space_cow(dim);

	if (!dim || !id)

		goto error;

	if (type != isl_dim_in && type != isl_dim_out)

		isl_die(dim->ctx, isl_error_invalid,

			"only input, output and set tuples can have names",

			goto error);

	isl_id_free(dim->tuple_id[type - isl_dim_in]);

	dim->tuple_id[type - isl_dim_in] = id;

	return dim;

error:

	isl_id_free(id);

	isl_space_free(dim);

	return NULL;

}

__isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *dim,

	enum isl_dim_type type)

{

	dim = isl_space_cow(dim);

	if (!dim)

		return NULL;

	if (type != isl_dim_in && type != isl_dim_out)

		isl_die(dim->ctx, isl_error_invalid,

			"only input, output and set tuples can have names",

			goto error);

	isl_id_free(dim->tuple_id[type - isl_dim_in]);

	dim->tuple_id[type - isl_dim_in] = NULL;

	return dim;

error:

	isl_space_free(dim);

	return NULL;

}

/* Set the id of the given dimension of "space" to "id".

 * If the dimension already has an id, then it is replaced.

 * If the dimension is a parameter, then we need to change it

 * in the nested spaces (if any) as well.

 */

__isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,

	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)

{

	space = isl_space_cow(space);

	if (!space || !id)

		goto error;

	if (type == isl_dim_param) {

		int i;

		for (i = 0; i < 2; ++i) {

			if (!space->nested[i])

				continue;

			space->nested[i] =

				isl_space_set_dim_id(space->nested[i],

						type, pos, isl_id_copy(id));

			if (!space->nested[i])

				goto error;

		}

	}

	isl_id_free(get_id(space, type, pos));

	return set_id(space, type, pos, id);

error:

	isl_id_free(id);

	isl_space_free(space);

	return NULL;

}

/* Reset the id of the given dimension of "space".

 * If the dimension already has an id, then it is removed.

 * If the dimension is a parameter, then we need to reset it

 * in the nested spaces (if any) as well.

 */

__isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,

	enum isl_dim_type type, unsigned pos)

{

	space = isl_space_cow(space);

	if (!space)

		goto error;

	if (type == isl_dim_param) {

		int i;

		for (i = 0; i < 2; ++i) {

			if (!space->nested[i])

				continue;

			space->nested[i] =

				isl_space_reset_dim_id(space->nested[i],

							type, pos);

			if (!space->nested[i])

				goto error;

		}

	}

	isl_id_free(get_id(space, type, pos));

	return set_id(space, type, pos, NULL);

error:

	isl_space_free(space);

	return NULL;

}

int isl_space_has_dim_id(__isl_keep isl_space *dim,

	enum isl_dim_type type, unsigned pos)

{

	if (!dim)

		return -1;

	return get_id(dim, type, pos) != NULL;

}

__isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *dim,

	enum isl_dim_type type, unsigned pos)

{

	if (!dim)

		return NULL;

	if (!get_id(dim, type, pos))

		isl_die(dim->ctx, isl_error_invalid,

			"dim has no id", return NULL);

	return isl_id_copy(get_id(dim, type, pos));

}

__isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *dim,

	enum isl_dim_type type, const char *s)

{

	isl_id *id;

	if (!dim)

		return NULL;

	if (!s)

		return isl_space_reset_tuple_id(dim, type);

	if (!name_ok(dim->ctx, s))

		goto error;

	id = isl_id_alloc(dim->ctx, s, NULL);

	return isl_space_set_tuple_id(dim, type, id);

error:

	isl_space_free(dim);

	return NULL;

}

/* Does the tuple have a name?

 */

int isl_space_has_tuple_name(__isl_keep isl_space *space,

	enum isl_dim_type type)

{

	isl_id *id;

	if (!space_can_have_id(space, type))

		return -1;

	id = space->tuple_id[type - isl_dim_in];

	return id && id->name;

}

const char *isl_space_get_tuple_name(__isl_keep isl_space *dim,

	 enum isl_dim_type type)

{

	isl_id *id;

	if (!dim)

		return NULL;

	if (type != isl_dim_in && type != isl_dim_out)

		return NULL;

	id = dim->tuple_id[type - isl_dim_in];

	return id ? id->name : NULL;

}

__isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *dim,

				 enum isl_dim_type type, unsigned pos,

				 const char *s)

{

	isl_id *id;

	if (!dim)

		return NULL;

	if (!s)

		return isl_space_reset_dim_id(dim, type, pos);

	if (!name_ok(dim->ctx, s))

		goto error;

	id = isl_id_alloc(dim->ctx, s, NULL);

	return isl_space_set_dim_id(dim, type, pos, id);

error:

	isl_space_free(dim);

	return NULL;

}

/* Does the given dimension have a name?

 */

int isl_space_has_dim_name(__isl_keep isl_space *space,

	enum isl_dim_type type, unsigned pos)

{

	isl_id *id;

	if (!space)

		return -1;

	id = get_id(space, type, pos);

	return id && id->name;

}

__isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *dim,

				 enum isl_dim_type type, unsigned pos)

{

	isl_id *id = get_id(dim, type, pos);

	return id ? id->name : NULL;

}

int isl_space_find_dim_by_id(__isl_keep isl_space *dim, enum isl_dim_type type,

	__isl_keep isl_id *id)

{

	int i;

	int offset;

	int n;

	if (!dim || !id)

		return -1;

	offset = isl_space_offset(dim, type);

	n = isl_space_dim(dim, type);

	for (i = 0; i < n && offset + i < dim->n_id; ++i)

		if (dim->ids[offset + i] == id)

			return i;

	return -1;

}

int isl_space_find_dim_by_name(__isl_keep isl_space *space,

	enum isl_dim_type type, const char *name)

{

	int i;

	int offset;

	int n;

	if (!space || !name)

		return -1;

	offset = isl_space_offset(space, type);

	n = isl_space_dim(space, type);

	for (i = 0; i < n && offset + i < space->n_id; ++i)

		if (space->ids[offset + i]->name &&

		    !strcmp(space->ids[offset + i]->name, name))

			return i;

	return -1;

}

/* Reset the user pointer on all identifiers of parameters and tuples

 * of "space".

 */

__isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)

{

	int i;

	isl_ctx *ctx;

	isl_id *id;

	const char *name;

	if (!space)

		return NULL;

	ctx = isl_space_get_ctx(space);

	for (i = 0; i < space->nparam && i < space->n_id; ++i) {

		if (!isl_id_get_user(space->ids[i]))

			continue;

		space = isl_space_cow(space);

		if (!space)

			return NULL;

		name = isl_id_get_name(space->ids[i]);

		id = isl_id_alloc(ctx, name, NULL);

		isl_id_free(space->ids[i]);

		space->ids[i] = id;

		if (!id)

			return isl_space_free(space);

	}

	for (i = 0; i < 2; ++i) {

		if (!space->tuple_id[i])

			continue;

		if (!isl_id_get_user(space->tuple_id[i]))

			continue;

		space = isl_space_cow(space);

		if (!space)

			return NULL;

		name = isl_id_get_name(space->tuple_id[i]);

		id = isl_id_alloc(ctx, name, NULL);

		isl_id_free(space->tuple_id[i]);

		space->tuple_id[i] = id;

		if (!id)

			return isl_space_free(space);

	}

	for (i = 0; i < 2; ++i) {

		if (!space->nested[i])

			continue;

		space = isl_space_cow(space);

		if (!space)

			return NULL;

		space->nested[i] = isl_space_reset_user(space->nested[i]);

		if (!space->nested[i])

			return isl_space_free(space);

	}

	return space;

}

static __isl_keep isl_id *tuple_id(__isl_keep isl_space *dim,

	enum isl_dim_type type)

{

	if (!dim)

		return NULL;

	if (type == isl_dim_in)

		return dim->tuple_id[0];

	if (type == isl_dim_out)

		return dim->tuple_id[1];

	return NULL;

}

static __isl_keep isl_space *nested(__isl_keep isl_space *dim,

	enum isl_dim_type type)

{

	if (!dim)

		return NULL;

	if (type == isl_dim_in)

		return dim->nested[0];

	if (type == isl_dim_out)

		return dim->nested[1];

	return NULL;

}

/* Are the two spaces the same, apart from positions and names of parameters?

 */

static int isl_space_has_equal_tuples(__isl_keep isl_space *space1,

	__isl_keep isl_space *space2)

{

	if (!space1 || !space2)

		return -1;

	if (space1 == space2)

		return 1;

	return isl_space_tuple_is_equal(space1, isl_dim_in,

					space2, isl_dim_in) &&

	       isl_space_tuple_is_equal(space1, isl_dim_out,

					space2, isl_dim_out);

}

/* Check if the tuple of type "type1" of "space1" is the same as

 * the tuple of type "type2" of "space2".

 *

 * That is, check if the tuples have the same identifier, the same dimension

 * and the same internal structure.

 * The identifiers of the dimensions inside the tuples do not affect the result.

 *

 * Note that this function only checks the tuples themselves.

 * If nested tuples are involved, then we need to be careful not

 * to have result affected by possibly differing parameters

 * in those nested tuples.

 */

int isl_space_tuple_is_equal(__isl_keep isl_space *space1,

	enum isl_dim_type type1, __isl_keep isl_space *space2,

	enum isl_dim_type type2)

{

	isl_id *id1, *id2;

	isl_space *nested1, *nested2;

	if (!space1 || !space2)

		return -1;

	if (space1 == space2 && type1 == type2)

		return 1;

	if (n(space1, type1) != n(space2, type2))

		return 0;

	id1 = tuple_id(space1, type1);

	id2 = tuple_id(space2, type2);

	if (!id1 ^ !id2)

		return 0;

	if (id1 && id1 != id2)

		return 0;

	nested1 = nested(space1, type1);

	nested2 = nested(space2, type2);

	if (!nested1 ^ !nested2)

		return 0;

	if (nested1 && !isl_space_has_equal_tuples(nested1, nested2))

		return 0;

	return 1;

}

/* This is the old, undocumented, name for isl_space_tuple_is_equal.

 * It will be removed at some point.

 */

int isl_space_tuple_match(__isl_keep isl_space *space1, enum isl_dim_type type1,

	__isl_keep isl_space *space2, enum isl_dim_type type2)

{

	return isl_space_tuple_is_equal(space1, type1, space2, type2);

}

static int match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,

	__isl_keep isl_space *dim2, enum isl_dim_type dim2_type)

{

	int i;

	if (dim1 == dim2 && dim1_type == dim2_type)

		return 1;

	if (!isl_space_tuple_is_equal(dim1, dim1_type, dim2, dim2_type))

		return 0;

	if (!dim1->ids && !dim2->ids)

		return 1;

	for (i = 0; i < n(dim1, dim1_type); ++i) {

		if (get_id(dim1, dim1_type, i) != get_id(dim2, dim2_type, i))

			return 0;

	}

	return 1;

}

int isl_space_match(__isl_keep isl_space *dim1, enum isl_dim_type dim1_type,

	__isl_keep isl_space *dim2, enum isl_dim_type dim2_type)

{

	if (!dim1 || !dim2)

		return -1;

	return match(dim1, dim1_type, dim2, dim2_type);

}

static void get_ids(__isl_keep isl_space *dim, enum isl_dim_type type,

	unsigned first, unsigned n, __isl_keep isl_id **ids)

{

	int i;

	for (i = 0; i < n ; ++i)

		ids[i] = get_id(dim, type, first + i);

}

__isl_give isl_space *isl_space_extend(__isl_take isl_space *dim,

			unsigned nparam, unsigned n_in, unsigned n_out)

{

	isl_id **ids = NULL;

	if (!dim)

		return NULL;

	if (dim->nparam == nparam && dim->n_in == n_in && dim->n_out == n_out)

		return dim;

	isl_assert(dim->ctx, dim->nparam <= nparam, goto error);