brintos / llvm-project-archived public Read only

1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 * Copyright 2010      INRIA Saclay4 * Copyright 2013-2014 Ecole Normale Superieure5 * Copyright 2018-2019 Cerebras Systems6 *7 * Use of this software is governed by the MIT license8 *9 * Written by Sven Verdoolaege, K.U.Leuven, Departement10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France14 * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA15 */16 17#include <stdlib.h>18#include <string.h>19#include <isl_space_private.h>20#include <isl_id_private.h>21#include <isl_reordering.h>22 23isl_ctx *isl_space_get_ctx(__isl_keep isl_space *space)24{25	return space ? space->ctx : NULL;26}27 28__isl_give isl_space *isl_space_alloc(isl_ctx *ctx,29			unsigned nparam, unsigned n_in, unsigned n_out)30{31	isl_space *space;32 33	space = isl_alloc_type(ctx, struct isl_space);34	if (!space)35		return NULL;36 37	space->ctx = ctx;38	isl_ctx_ref(ctx);39	space->ref = 1;40	space->nparam = nparam;41	space->n_in = n_in;42	space->n_out = n_out;43 44	space->tuple_id[0] = NULL;45	space->tuple_id[1] = NULL;46 47	space->nested[0] = NULL;48	space->nested[1] = NULL;49 50	space->n_id = 0;51	space->ids = NULL;52 53	return space;54}55 56/* Mark the space as being that of a set, by setting the domain tuple57 * to isl_id_none.58 */59static __isl_give isl_space *mark_as_set(__isl_take isl_space *space)60{61	space = isl_space_cow(space);62	if (!space)63		return NULL;64	space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);65	return space;66}67 68/* Is the space that of a set?69 */70isl_bool isl_space_is_set(__isl_keep isl_space *space)71{72	if (!space)73		return isl_bool_error;74	if (space->n_in != 0 || space->nested[0])75		return isl_bool_false;76	if (space->tuple_id[0] != &isl_id_none)77		return isl_bool_false;78	return isl_bool_true;79}80 81/* Check that "space" is a set space.82 */83isl_stat isl_space_check_is_set(__isl_keep isl_space *space)84{85	isl_bool is_set;86 87	is_set = isl_space_is_set(space);88	if (is_set < 0)89		return isl_stat_error;90	if (!is_set)91		isl_die(isl_space_get_ctx(space), isl_error_invalid,92			"space is not a set", return isl_stat_error);93	return isl_stat_ok;94}95 96/* Is the given space that of a map?97 */98isl_bool isl_space_is_map(__isl_keep isl_space *space)99{100	int r;101 102	if (!space)103		return isl_bool_error;104	r = space->tuple_id[0] != &isl_id_none &&105	    space->tuple_id[1] != &isl_id_none;106	return isl_bool_ok(r);107}108 109/* Check that "space" is the space of a map.110 */111static isl_stat isl_space_check_is_map(__isl_keep isl_space *space)112{113	isl_bool is_space;114 115	is_space = isl_space_is_map(space);116	if (is_space < 0)117		return isl_stat_error;118	if (!is_space)119		isl_die(isl_space_get_ctx(space), isl_error_invalid,120			"expecting map space", return isl_stat_error);121	return isl_stat_ok;122}123 124/* Check that "space" is the space of a map125 * where the domain is a wrapped map space.126 */127isl_stat isl_space_check_domain_is_wrapping(__isl_keep isl_space *space)128{129	isl_bool wrapping;130 131	wrapping = isl_space_domain_is_wrapping(space);132	if (wrapping < 0)133		return isl_stat_error;134	if (!wrapping)135		isl_die(isl_space_get_ctx(space), isl_error_invalid,136			"domain not a product", return isl_stat_error);137	return isl_stat_ok;138}139 140/* Check that "space" is the space of a map141 * where the range is a wrapped map space.142 */143isl_stat isl_space_check_range_is_wrapping(__isl_keep isl_space *space)144{145	isl_bool wrapping;146 147	wrapping = isl_space_range_is_wrapping(space);148	if (wrapping < 0)149		return isl_stat_error;150	if (!wrapping)151		isl_die(isl_space_get_ctx(space), isl_error_invalid,152			"range not a product", return isl_stat_error);153	return isl_stat_ok;154}155 156__isl_give isl_space *isl_space_set_alloc(isl_ctx *ctx,157			unsigned nparam, unsigned dim)158{159	isl_space *space;160	space = isl_space_alloc(ctx, nparam, 0, dim);161	space = mark_as_set(space);162	return space;163}164 165/* Mark the space as being that of a parameter domain, by setting166 * both tuples to isl_id_none.167 */168static __isl_give isl_space *mark_as_params(isl_space *space)169{170	if (!space)171		return NULL;172	space = isl_space_set_tuple_id(space, isl_dim_in, &isl_id_none);173	space = isl_space_set_tuple_id(space, isl_dim_out, &isl_id_none);174	return space;175}176 177/* Is the space that of a parameter domain?178 */179isl_bool isl_space_is_params(__isl_keep isl_space *space)180{181	if (!space)182		return isl_bool_error;183	if (space->n_in != 0 || space->nested[0] ||184	    space->n_out != 0 || space->nested[1])185		return isl_bool_false;186	if (space->tuple_id[0] != &isl_id_none)187		return isl_bool_false;188	if (space->tuple_id[1] != &isl_id_none)189		return isl_bool_false;190	return isl_bool_true;191}192 193/* Create a space for a parameter domain.194 */195__isl_give isl_space *isl_space_params_alloc(isl_ctx *ctx, unsigned nparam)196{197	isl_space *space;198	space = isl_space_alloc(ctx, nparam, 0, 0);199	space = mark_as_params(space);200	return space;201}202 203/* Create a space for a parameter domain, without any parameters.204 */205__isl_give isl_space *isl_space_unit(isl_ctx *ctx)206{207	return isl_space_params_alloc(ctx, 0);208}209 210static isl_size global_pos(__isl_keep isl_space *space,211				 enum isl_dim_type type, unsigned pos)212{213	if (isl_space_check_range(space, type, pos, 1) < 0)214		return isl_size_error;215 216	switch (type) {217	case isl_dim_param:218		return pos;219	case isl_dim_in:220		return pos + space->nparam;221	case isl_dim_out:222		return pos + space->nparam + space->n_in;223	default:224		isl_assert(isl_space_get_ctx(space), 0, return isl_size_error);225	}226	return isl_size_error;227}228 229/* Extend length of ids array to the total number of dimensions.230 */231static __isl_give isl_space *extend_ids(__isl_take isl_space *space)232{233	isl_id **ids;234	int i;235	isl_size dim;236 237	dim = isl_space_dim(space, isl_dim_all);238	if (dim < 0)239		return isl_space_free(space);240	if (dim <= space->n_id)241		return space;242 243	if (!space->ids) {244		space->ids = isl_calloc_array(space->ctx, isl_id *, dim);245		if (!space->ids)246			goto error;247	} else {248		ids = isl_realloc_array(space->ctx, space->ids, isl_id *, dim);249		if (!ids)250			goto error;251		space->ids = ids;252		for (i = space->n_id; i < dim; ++i)253			space->ids[i] = NULL;254	}255 256	space->n_id = dim;257 258	return space;259error:260	isl_space_free(space);261	return NULL;262}263 264static __isl_give isl_space *set_id(__isl_take isl_space *space,265	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)266{267	isl_size gpos;268 269	space = isl_space_cow(space);270 271	gpos = global_pos(space, type, pos);272	if (gpos < 0)273		goto error;274 275	if (gpos >= space->n_id) {276		if (!id)277			return space;278		space = extend_ids(space);279		if (!space)280			goto error;281	}282 283	space->ids[gpos] = id;284 285	return space;286error:287	isl_id_free(id);288	isl_space_free(space);289	return NULL;290}291 292static __isl_keep isl_id *get_id(__isl_keep isl_space *space,293				 enum isl_dim_type type, unsigned pos)294{295	isl_size gpos;296 297	gpos = global_pos(space, type, pos);298	if (gpos < 0)299		return NULL;300	if (gpos >= space->n_id)301		return NULL;302	return space->ids[gpos];303}304 305/* Return the nested space at the given position.306 */307static __isl_keep isl_space *isl_space_peek_nested(__isl_keep isl_space *space,308	int pos)309{310	if (!space)311		return NULL;312	if (!space->nested[pos])313		isl_die(isl_space_get_ctx(space), isl_error_invalid,314			"no nested space", return NULL);315	return space->nested[pos];316}317 318static unsigned offset(__isl_keep isl_space *space, enum isl_dim_type type)319{320	switch (type) {321	case isl_dim_param:	return 0;322	case isl_dim_in:	return space->nparam;323	case isl_dim_out:	return space->nparam + space->n_in;324	default:		return 0;325	}326}327 328static unsigned n(__isl_keep isl_space *space, enum isl_dim_type type)329{330	switch (type) {331	case isl_dim_param:	return space->nparam;332	case isl_dim_in:	return space->n_in;333	case isl_dim_out:	return space->n_out;334	case isl_dim_all:335		return space->nparam + space->n_in + space->n_out;336	default:		return 0;337	}338}339 340isl_size isl_space_dim(__isl_keep isl_space *space, enum isl_dim_type type)341{342	if (!space)343		return isl_size_error;344	return n(space, type);345}346 347/* Return the dimensionality of tuple "inner" within the wrapped relation348 * inside tuple "outer".349 */350isl_size isl_space_wrapped_dim(__isl_keep isl_space *space,351	enum isl_dim_type outer, enum isl_dim_type inner)352{353	int pos;354 355	if (!space)356		return isl_size_error;357	if (outer != isl_dim_in && outer != isl_dim_out)358		isl_die(isl_space_get_ctx(space), isl_error_invalid,359			"only input, output and set tuples "360			"can have nested relations", return isl_size_error);361	pos = outer - isl_dim_in;362	return isl_space_dim(isl_space_peek_nested(space, pos), inner);363}364 365unsigned isl_space_offset(__isl_keep isl_space *space, enum isl_dim_type type)366{367	if (!space)368		return 0;369	return offset(space, type);370}371 372static __isl_give isl_space *copy_ids(__isl_take isl_space *dst,373	enum isl_dim_type dst_type, unsigned offset, __isl_keep isl_space *src,374	enum isl_dim_type src_type)375{376	int i;377	isl_id *id;378 379	if (!dst)380		return NULL;381 382	for (i = 0; i < n(src, src_type); ++i) {383		id = get_id(src, src_type, i);384		if (!id)385			continue;386		dst = set_id(dst, dst_type, offset + i, isl_id_copy(id));387		if (!dst)388			return NULL;389	}390	return dst;391}392 393__isl_give isl_space *isl_space_dup(__isl_keep isl_space *space)394{395	isl_space *dup;396	if (!space)397		return NULL;398	dup = isl_space_alloc(space->ctx,399				space->nparam, space->n_in, space->n_out);400	if (!dup)401		return NULL;402	if (space->tuple_id[0] &&403	    !(dup->tuple_id[0] = isl_id_copy(space->tuple_id[0])))404		goto error;405	if (space->tuple_id[1] &&406	    !(dup->tuple_id[1] = isl_id_copy(space->tuple_id[1])))407		goto error;408	if (space->nested[0] &&409	    !(dup->nested[0] = isl_space_copy(space->nested[0])))410		goto error;411	if (space->nested[1] &&412	    !(dup->nested[1] = isl_space_copy(space->nested[1])))413		goto error;414	if (!space->ids)415		return dup;416	dup = copy_ids(dup, isl_dim_param, 0, space, isl_dim_param);417	dup = copy_ids(dup, isl_dim_in, 0, space, isl_dim_in);418	dup = copy_ids(dup, isl_dim_out, 0, space, isl_dim_out);419	return dup;420error:421	isl_space_free(dup);422	return NULL;423}424 425__isl_give isl_space *isl_space_cow(__isl_take isl_space *space)426{427	if (!space)428		return NULL;429 430	if (space->ref == 1)431		return space;432	space->ref--;433	return isl_space_dup(space);434}435 436__isl_give isl_space *isl_space_copy(__isl_keep isl_space *space)437{438	if (!space)439		return NULL;440 441	space->ref++;442	return space;443}444 445__isl_null isl_space *isl_space_free(__isl_take isl_space *space)446{447	int i;448 449	if (!space)450		return NULL;451 452	if (--space->ref > 0)453		return NULL;454 455	isl_id_free(space->tuple_id[0]);456	isl_id_free(space->tuple_id[1]);457 458	isl_space_free(space->nested[0]);459	isl_space_free(space->nested[1]);460 461	for (i = 0; i < space->n_id; ++i)462		isl_id_free(space->ids[i]);463	free(space->ids);464	isl_ctx_deref(space->ctx);465	466	free(space);467 468	return NULL;469}470 471/* Check if "s" is a valid dimension or tuple name.472 * We currently only forbid names that look like a number.473 *474 * s is assumed to be non-NULL.475 */476static int name_ok(isl_ctx *ctx, const char *s)477{478	char *p;479 480	strtol(s, &p, 0);481	if (p != s)482		isl_die(ctx, isl_error_invalid, "name looks like a number",483			return 0);484 485	return 1;486}487 488/* Return a copy of the nested space at the given position.489 */490static __isl_keep isl_space *isl_space_get_nested(__isl_keep isl_space *space,491	int pos)492{493	return isl_space_copy(isl_space_peek_nested(space, pos));494}495 496/* Return the nested space at the given position.497 * This may be either a copy or the nested space itself498 * if there is only one reference to "space".499 * This allows the nested space to be modified inplace500 * if both "space" and the nested space have only a single reference.501 * The caller is not allowed to modify "space" between this call and502 * a subsequent call to isl_space_restore_nested.503 * The only exception is that isl_space_free can be called instead.504 */505static __isl_give isl_space *isl_space_take_nested(__isl_keep isl_space *space,506	int pos)507{508	isl_space *nested;509 510	if (!space)511		return NULL;512	if (space->ref != 1)513		return isl_space_get_nested(space, pos);514	nested = space->nested[pos];515	space->nested[pos] = NULL;516	return nested;517}518 519/* Replace the nested space at the given position by "nested",520 * where this nested space of "space" may be missing521 * due to a preceding call to isl_space_take_nested.522 * However, in this case, "space" only has a single reference and523 * then the call to isl_space_cow has no effect.524 */525static __isl_give isl_space *isl_space_restore_nested(526	__isl_take isl_space *space, int pos, __isl_take isl_space *nested)527{528	if (!space || !nested)529		goto error;530 531	if (space->nested[pos] == nested) {532		isl_space_free(nested);533		return space;534	}535 536	space = isl_space_cow(space);537	if (!space)538		goto error;539	isl_space_free(space->nested[pos]);540	space->nested[pos] = nested;541 542	return space;543error:544	isl_space_free(space);545	isl_space_free(nested);546	return NULL;547}548 549/* Is it possible for the given dimension type to have a tuple id?550 */551static int space_can_have_id(__isl_keep isl_space *space,552	enum isl_dim_type type)553{554	if (!space)555		return 0;556	if (isl_space_is_params(space))557		isl_die(space->ctx, isl_error_invalid,558			"parameter spaces don't have tuple ids", return 0);559	if (isl_space_is_set(space) && type != isl_dim_set)560		isl_die(space->ctx, isl_error_invalid,561			"set spaces can only have a set id", return 0);562	if (type != isl_dim_in && type != isl_dim_out)563		isl_die(space->ctx, isl_error_invalid,564			"only input, output and set tuples can have ids",565			return 0);566 567	return 1;568}569 570/* Does the tuple have an id?571 */572isl_bool isl_space_has_tuple_id(__isl_keep isl_space *space,573	enum isl_dim_type type)574{575	if (!space_can_have_id(space, type))576		return isl_bool_error;577	return isl_bool_ok(space->tuple_id[type - isl_dim_in] != NULL);578}579 580/* Does the domain tuple of the map space "space" have an identifier?581 */582isl_bool isl_space_has_domain_tuple_id(__isl_keep isl_space *space)583{584	if (isl_space_check_is_map(space) < 0)585		return isl_bool_error;586	return isl_space_has_tuple_id(space, isl_dim_in);587}588 589/* Does the range tuple of the map space "space" have an identifier?590 */591isl_bool isl_space_has_range_tuple_id(__isl_keep isl_space *space)592{593	if (isl_space_check_is_map(space) < 0)594		return isl_bool_error;595	return isl_space_has_tuple_id(space, isl_dim_out);596}597 598__isl_give isl_id *isl_space_get_tuple_id(__isl_keep isl_space *space,599	enum isl_dim_type type)600{601	int has_id;602 603	if (!space)604		return NULL;605	has_id = isl_space_has_tuple_id(space, type);606	if (has_id < 0)607		return NULL;608	if (!has_id)609		isl_die(space->ctx, isl_error_invalid,610			"tuple has no id", return NULL);611	return isl_id_copy(space->tuple_id[type - isl_dim_in]);612}613 614/* Return the identifier of the domain tuple of the map space "space",615 * assuming it has one.616 */617__isl_give isl_id *isl_space_get_domain_tuple_id(618	__isl_keep isl_space *space)619{620	if (isl_space_check_is_map(space) < 0)621		return NULL;622	return isl_space_get_tuple_id(space, isl_dim_in);623}624 625/* Return the identifier of the range tuple of the map space "space",626 * assuming it has one.627 */628__isl_give isl_id *isl_space_get_range_tuple_id(629	__isl_keep isl_space *space)630{631	if (isl_space_check_is_map(space) < 0)632		return NULL;633	return isl_space_get_tuple_id(space, isl_dim_out);634}635 636__isl_give isl_space *isl_space_set_tuple_id(__isl_take isl_space *space,637	enum isl_dim_type type, __isl_take isl_id *id)638{639	space = isl_space_cow(space);640	if (!space || !id)641		goto error;642	if (type != isl_dim_in && type != isl_dim_out)643		isl_die(space->ctx, isl_error_invalid,644			"only input, output and set tuples can have names",645			goto error);646 647	isl_id_free(space->tuple_id[type - isl_dim_in]);648	space->tuple_id[type - isl_dim_in] = id;649 650	return space;651error:652	isl_id_free(id);653	isl_space_free(space);654	return NULL;655}656 657/* Replace the identifier of the domain tuple of the map space "space"658 * by "id".659 */660__isl_give isl_space *isl_space_set_domain_tuple_id(661	__isl_take isl_space *space, __isl_take isl_id *id)662{663	if (isl_space_check_is_map(space) < 0)664		space = isl_space_free(space);665	return isl_space_set_tuple_id(space, isl_dim_in, id);666}667 668/* Replace the identifier of the range tuple of the map space "space"669 * by "id".670 */671__isl_give isl_space *isl_space_set_range_tuple_id(672	__isl_take isl_space *space, __isl_take isl_id *id)673{674	if (isl_space_check_is_map(space) < 0)675		space = isl_space_free(space);676	return isl_space_set_tuple_id(space, isl_dim_out, id);677}678 679__isl_give isl_space *isl_space_reset_tuple_id(__isl_take isl_space *space,680	enum isl_dim_type type)681{682	space = isl_space_cow(space);683	if (!space)684		return NULL;685	if (type != isl_dim_in && type != isl_dim_out)686		isl_die(space->ctx, isl_error_invalid,687			"only input, output and set tuples can have names",688			goto error);689 690	isl_id_free(space->tuple_id[type - isl_dim_in]);691	space->tuple_id[type - isl_dim_in] = NULL;692 693	return space;694error:695	isl_space_free(space);696	return NULL;697}698 699/* Set the id of the given dimension of "space" to "id".700 * If the dimension already has an id, then it is replaced.701 * If the dimension is a parameter, then we need to change it702 * in the nested spaces (if any) as well.703 */704__isl_give isl_space *isl_space_set_dim_id(__isl_take isl_space *space,705	enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)706{707	space = isl_space_cow(space);708	if (!space || !id)709		goto error;710 711	if (type == isl_dim_param) {712		int i;713 714		for (i = 0; i < 2; ++i) {715			if (!space->nested[i])716				continue;717			space->nested[i] =718				isl_space_set_dim_id(space->nested[i],719						type, pos, isl_id_copy(id));720			if (!space->nested[i])721				goto error;722		}723	}724 725	isl_id_free(get_id(space, type, pos));726	return set_id(space, type, pos, id);727error:728	isl_id_free(id);729	isl_space_free(space);730	return NULL;731}732 733/* Reset the id of the given dimension of "space".734 * If the dimension already has an id, then it is removed.735 * If the dimension is a parameter, then we need to reset it736 * in the nested spaces (if any) as well.737 */738__isl_give isl_space *isl_space_reset_dim_id(__isl_take isl_space *space,739	enum isl_dim_type type, unsigned pos)740{741	space = isl_space_cow(space);742	if (!space)743		goto error;744 745	if (type == isl_dim_param) {746		int i;747 748		for (i = 0; i < 2; ++i) {749			if (!space->nested[i])750				continue;751			space->nested[i] =752				isl_space_reset_dim_id(space->nested[i],753							type, pos);754			if (!space->nested[i])755				goto error;756		}757	}758 759	isl_id_free(get_id(space, type, pos));760	return set_id(space, type, pos, NULL);761error:762	isl_space_free(space);763	return NULL;764}765 766isl_bool isl_space_has_dim_id(__isl_keep isl_space *space,767	enum isl_dim_type type, unsigned pos)768{769	if (!space)770		return isl_bool_error;771	return isl_bool_ok(get_id(space, type, pos) != NULL);772}773 774__isl_give isl_id *isl_space_get_dim_id(__isl_keep isl_space *space,775	enum isl_dim_type type, unsigned pos)776{777	if (!space)778		return NULL;779	if (!get_id(space, type, pos))780		isl_die(space->ctx, isl_error_invalid,781			"dim has no id", return NULL);782	return isl_id_copy(get_id(space, type, pos));783}784 785__isl_give isl_space *isl_space_set_tuple_name(__isl_take isl_space *space,786	enum isl_dim_type type, const char *s)787{788	isl_id *id;789 790	if (!space)791		return NULL;792 793	if (!s)794		return isl_space_reset_tuple_id(space, type);795 796	if (!name_ok(space->ctx, s))797		goto error;798 799	id = isl_id_alloc(space->ctx, s, NULL);800	return isl_space_set_tuple_id(space, type, id);801error:802	isl_space_free(space);803	return NULL;804}805 806/* Does the tuple have a name?807 */808isl_bool isl_space_has_tuple_name(__isl_keep isl_space *space,809	enum isl_dim_type type)810{811	isl_id *id;812 813	if (!space_can_have_id(space, type))814		return isl_bool_error;815	id = space->tuple_id[type - isl_dim_in];816	return isl_bool_ok(id && id->name);817}818 819__isl_keep const char *isl_space_get_tuple_name(__isl_keep isl_space *space,820	 enum isl_dim_type type)821{822	isl_id *id;823	if (!space)824		return NULL;825	if (type != isl_dim_in && type != isl_dim_out)826		return NULL;827	id = space->tuple_id[type - isl_dim_in];828	return id ? id->name : NULL;829}830 831__isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space,832				 enum isl_dim_type type, unsigned pos,833				 const char *s)834{835	isl_id *id;836 837	if (!space)838		return NULL;839	if (!s)840		return isl_space_reset_dim_id(space, type, pos);841	if (!name_ok(space->ctx, s))842		goto error;843	id = isl_id_alloc(space->ctx, s, NULL);844	return isl_space_set_dim_id(space, type, pos, id);845error:846	isl_space_free(space);847	return NULL;848}849 850/* Does the given dimension have a name?851 */852isl_bool isl_space_has_dim_name(__isl_keep isl_space *space,853	enum isl_dim_type type, unsigned pos)854{855	isl_id *id;856 857	if (!space)858		return isl_bool_error;859	id = get_id(space, type, pos);860	return isl_bool_ok(id && id->name);861}862 863__isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space,864				 enum isl_dim_type type, unsigned pos)865{866	isl_id *id = get_id(space, type, pos);867	return id ? id->name : NULL;868}869 870int isl_space_find_dim_by_id(__isl_keep isl_space *space,871	enum isl_dim_type type, __isl_keep isl_id *id)872{873	int i;874	int offset;875	isl_size n;876 877	n = isl_space_dim(space, type);878	if (n < 0 || !id)879		return -1;880 881	offset = isl_space_offset(space, type);882	for (i = 0; i < n && offset + i < space->n_id; ++i)883		if (space->ids[offset + i] == id)884			return i;885 886	return -1;887}888 889int isl_space_find_dim_by_name(__isl_keep isl_space *space,890	enum isl_dim_type type, const char *name)891{892	int i;893	int offset;894	isl_size n;895 896	n = isl_space_dim(space, type);897	if (n < 0 || !name)898		return -1;899 900	offset = isl_space_offset(space, type);901	for (i = 0; i < n && offset + i < space->n_id; ++i) {902		isl_id *id = get_id(space, type, i);903		if (id && id->name && !strcmp(id->name, name))904			return i;905	}906 907	return -1;908}909 910/* Reset the user pointer on all identifiers of parameters and tuples911 * of "space".912 */913__isl_give isl_space *isl_space_reset_user(__isl_take isl_space *space)914{915	int i;916	isl_ctx *ctx;917	isl_id *id;918	const char *name;919 920	if (!space)921		return NULL;922 923	ctx = isl_space_get_ctx(space);924 925	for (i = 0; i < space->nparam && i < space->n_id; ++i) {926		if (!isl_id_get_user(space->ids[i]))927			continue;928		space = isl_space_cow(space);929		if (!space)930			return NULL;931		name = isl_id_get_name(space->ids[i]);932		id = isl_id_alloc(ctx, name, NULL);933		isl_id_free(space->ids[i]);934		space->ids[i] = id;935		if (!id)936			return isl_space_free(space);937	}938 939	for (i = 0; i < 2; ++i) {940		if (!space->tuple_id[i])941			continue;942		if (!isl_id_get_user(space->tuple_id[i]))943			continue;944		space = isl_space_cow(space);945		if (!space)946			return NULL;947		name = isl_id_get_name(space->tuple_id[i]);948		id = isl_id_alloc(ctx, name, NULL);949		isl_id_free(space->tuple_id[i]);950		space->tuple_id[i] = id;951		if (!id)952			return isl_space_free(space);953	}954 955	for (i = 0; i < 2; ++i) {956		isl_space *nested;957 958		if (!space->nested[i])959			continue;960		nested = isl_space_take_nested(space, i);961		nested = isl_space_reset_user(nested);962		space = isl_space_restore_nested(space, i, nested);963		if (!space)964			return NULL;965	}966 967	return space;968}969 970static __isl_keep isl_id *tuple_id(__isl_keep isl_space *space,971	enum isl_dim_type type)972{973	if (!space)974		return NULL;975	if (type == isl_dim_in)976		return space->tuple_id[0];977	if (type == isl_dim_out)978		return space->tuple_id[1];979	return NULL;980}981 982static __isl_keep isl_space *nested(__isl_keep isl_space *space,983	enum isl_dim_type type)984{985	if (!space)986		return NULL;987	if (type == isl_dim_in)988		return space->nested[0];989	if (type == isl_dim_out)990		return space->nested[1];991	return NULL;992}993 994/* Are the two spaces the same, apart from positions and names of parameters?995 */996isl_bool isl_space_has_equal_tuples(__isl_keep isl_space *space1,997	__isl_keep isl_space *space2)998{999	if (!space1 || !space2)1000		return isl_bool_error;1001	if (space1 == space2)1002		return isl_bool_true;1003	return isl_space_tuple_is_equal(space1, isl_dim_in,1004					space2, isl_dim_in) &&1005	       isl_space_tuple_is_equal(space1, isl_dim_out,1006					space2, isl_dim_out);1007}1008 1009/* Check that a match involving "space" was successful.1010 * That is, check that "match" is equal to isl_bool_true.1011 */1012static isl_stat check_match(__isl_keep isl_space *space, isl_bool match)1013{1014	if (match < 0)1015		return isl_stat_error;1016	if (!match)1017		isl_die(isl_space_get_ctx(space), isl_error_invalid,1018			"incompatible spaces", return isl_stat_error);1019 1020	return isl_stat_ok;1021}1022 1023/* Check that the two spaces are the same,1024 * apart from positions and names of parameters.1025 */1026isl_stat isl_space_check_equal_tuples(__isl_keep isl_space *space1,1027	__isl_keep isl_space *space2)1028{1029	isl_bool is_equal;1030 1031	is_equal = isl_space_has_equal_tuples(space1, space2);1032	return check_match(space1, is_equal);1033}1034 1035/* Check if the tuple of type "type1" of "space1" is the same as1036 * the tuple of type "type2" of "space2".1037 *1038 * That is, check if the tuples have the same identifier, the same dimension1039 * and the same internal structure.1040 * The identifiers of the dimensions inside the tuples do not affect the result.1041 *1042 * Note that this function only checks the tuples themselves.1043 * If nested tuples are involved, then we need to be careful not1044 * to have result affected by possibly differing parameters1045 * in those nested tuples.1046 */1047isl_bool isl_space_tuple_is_equal(__isl_keep isl_space *space1,1048	enum isl_dim_type type1, __isl_keep isl_space *space2,1049	enum isl_dim_type type2)1050{1051	isl_id *id1, *id2;1052	isl_space *nested1, *nested2;1053 1054	if (!space1 || !space2)1055		return isl_bool_error;1056 1057	if (space1 == space2 && type1 == type2)1058		return isl_bool_true;1059 1060	if (n(space1, type1) != n(space2, type2))1061		return isl_bool_false;1062	id1 = tuple_id(space1, type1);1063	id2 = tuple_id(space2, type2);1064	if (!id1 ^ !id2)1065		return isl_bool_false;1066	if (id1 && id1 != id2)1067		return isl_bool_false;1068	nested1 = nested(space1, type1);1069	nested2 = nested(space2, type2);1070	if (!nested1 ^ !nested2)1071		return isl_bool_false;1072	if (nested1 && !isl_space_has_equal_tuples(nested1, nested2))1073		return isl_bool_false;1074	return isl_bool_true;1075}1076 1077/* Is the tuple "inner" within the wrapped relation inside tuple "outer"1078 * of "space1" equal to tuple "type2" of "space2"?1079 */1080isl_bool isl_space_wrapped_tuple_is_equal(__isl_keep isl_space *space1,1081	enum isl_dim_type outer, enum isl_dim_type inner,1082	__isl_keep isl_space *space2, enum isl_dim_type type2)1083{1084	int pos;1085	isl_space *nested;1086 1087	if (!space1)1088		return isl_bool_error;1089	if (outer != isl_dim_in && outer != isl_dim_out)1090		isl_die(isl_space_get_ctx(space1), isl_error_invalid,1091			"only input, output and set tuples "1092			"can have nested relations", return isl_bool_error);1093	pos = outer - isl_dim_in;1094	nested = isl_space_peek_nested(space1, pos);1095	return isl_space_tuple_is_equal(nested, inner, space2, type2);1096}1097 1098/* Check that the tuple "inner" within the wrapped relation inside tuple "outer"1099 * of "space1" is equal to tuple "type2" of "space2".1100 */1101isl_stat isl_space_check_wrapped_tuple_is_equal(__isl_keep isl_space *space1,1102	enum isl_dim_type outer, enum isl_dim_type inner,1103	__isl_keep isl_space *space2, enum isl_dim_type type2)1104{1105	isl_bool is_equal;1106 1107	is_equal = isl_space_wrapped_tuple_is_equal(space1, outer, inner,1108							space2, type2);1109	return check_match(space1, is_equal);1110}1111 1112static isl_bool match(__isl_keep isl_space *space1, enum isl_dim_type type1,1113	__isl_keep isl_space *space2, enum isl_dim_type type2)1114{1115	int i;1116	isl_bool equal;1117 1118	if (!space1 || !space2)1119		return isl_bool_error;1120 1121	if (space1 == space2 && type1 == type2)1122		return isl_bool_true;1123 1124	equal = isl_space_tuple_is_equal(space1, type1, space2, type2);1125	if (equal < 0 || !equal)1126		return equal;1127 1128	if (!space1->ids && !space2->ids)1129		return isl_bool_true;1130 1131	for (i = 0; i < n(space1, type1); ++i) {1132		if (get_id(space1, type1, i) != get_id(space2, type2, i))1133			return isl_bool_false;1134	}1135	return isl_bool_true;1136}1137 1138/* Do "space1" and "space2" have the same parameters?1139 */1140isl_bool isl_space_has_equal_params(__isl_keep isl_space *space1,1141	__isl_keep isl_space *space2)1142{1143	return match(space1, isl_dim_param, space2, isl_dim_param);1144}1145 1146/* Do "space1" and "space2" have the same identifiers for all1147 * the tuple variables?1148 */1149isl_bool isl_space_has_equal_ids(__isl_keep isl_space *space1,1150	__isl_keep isl_space *space2)1151{1152	isl_bool equal;1153 1154	equal = match(space1, isl_dim_in, space2, isl_dim_in);1155	if (equal < 0 || !equal)1156		return equal;1157	return match(space1, isl_dim_out, space2, isl_dim_out);1158}1159 1160isl_bool isl_space_match(__isl_keep isl_space *space1, enum isl_dim_type type1,1161	__isl_keep isl_space *space2, enum isl_dim_type type2)1162{1163	return match(space1, type1, space2, type2);1164}1165 1166static void get_ids(__isl_keep isl_space *space, enum isl_dim_type type,1167	unsigned first, unsigned n, __isl_keep isl_id **ids)1168{1169	int i;1170 1171	for (i = 0; i < n ; ++i)1172		ids[i] = get_id(space, type, first + i);1173}1174 1175static __isl_give isl_space *space_extend(__isl_take isl_space *space,1176			unsigned nparam, unsigned n_in, unsigned n_out)1177{1178	isl_id **ids = NULL;1179 1180	if (!space)1181		return NULL;1182	if (space->nparam == nparam &&1183	    space->n_in == n_in && space->n_out == n_out)1184		return space;1185 1186	isl_assert(space->ctx, space->nparam <= nparam, goto error);1187	isl_assert(space->ctx, space->n_in <= n_in, goto error);1188	isl_assert(space->ctx, space->n_out <= n_out, goto error);1189 1190	space = isl_space_cow(space);1191	if (!space)1192		goto error;1193 1194	if (space->ids) {1195		unsigned n;1196		n = nparam + n_in + n_out;1197		if (n < nparam || n < n_in || n < n_out)1198			isl_die(isl_space_get_ctx(space), isl_error_invalid,1199				"overflow in total number of dimensions",1200				goto error);1201		ids = isl_calloc_array(space->ctx, isl_id *, n);1202		if (!ids)1203			goto error;1204		get_ids(space, isl_dim_param, 0, space->nparam, ids);1205		get_ids(space, isl_dim_in, 0, space->n_in, ids + nparam);1206		get_ids(space, isl_dim_out, 0, space->n_out,1207			ids + nparam + n_in);1208		free(space->ids);1209		space->ids = ids;1210		space->n_id = nparam + n_in + n_out;1211	}1212	space->nparam = nparam;1213	space->n_in = n_in;1214	space->n_out = n_out;1215 1216	return space;1217error:1218	free(ids);1219	isl_space_free(space);1220	return NULL;1221}1222 1223__isl_give isl_space *isl_space_extend(__isl_take isl_space *space,1224	unsigned nparam, unsigned n_in, unsigned n_out)1225{1226	return space_extend(space, nparam, n_in, n_out);1227}1228 1229__isl_give isl_space *isl_space_add_dims(__isl_take isl_space *space,1230	enum isl_dim_type type, unsigned n)1231{1232	space = isl_space_reset(space, type);1233	if (!space)1234		return NULL;1235	switch (type) {1236	case isl_dim_param:1237		space = space_extend(space,1238				space->nparam + n, space->n_in, space->n_out);1239		if (space && space->nested[0] &&1240		    !(space->nested[0] = isl_space_add_dims(space->nested[0],1241						    isl_dim_param, n)))1242			goto error;1243		if (space && space->nested[1] &&1244		    !(space->nested[1] = isl_space_add_dims(space->nested[1],1245						    isl_dim_param, n)))1246			goto error;1247		return space;1248	case isl_dim_in:1249		return space_extend(space,1250				space->nparam, space->n_in + n, space->n_out);1251	case isl_dim_out:1252		return space_extend(space,1253				space->nparam, space->n_in, space->n_out + n);1254	default:1255		isl_die(space->ctx, isl_error_invalid,1256			"cannot add dimensions of specified type", goto error);1257	}1258error:1259	isl_space_free(space);1260	return NULL;1261}1262 1263/* Add a parameter with identifier "id" to "space", provided1264 * it does not already appear in "space".1265 */1266__isl_give isl_space *isl_space_add_param_id(__isl_take isl_space *space,1267	__isl_take isl_id *id)1268{1269	isl_size pos;1270 1271	if (!space || !id)1272		goto error;1273 1274	if (isl_space_find_dim_by_id(space, isl_dim_param, id) >= 0) {1275		isl_id_free(id);1276		return space;1277	}1278 1279	pos = isl_space_dim(space, isl_dim_param);1280	if (pos < 0)1281		goto error;1282	space = isl_space_add_dims(space, isl_dim_param, 1);1283	space = isl_space_set_dim_id(space, isl_dim_param, pos, id);1284 1285	return space;1286error:1287	isl_space_free(space);1288	isl_id_free(id);1289	return NULL;1290}1291 1292static int valid_dim_type(enum isl_dim_type type)1293{1294	switch (type) {1295	case isl_dim_param:1296	case isl_dim_in:1297	case isl_dim_out:1298		return 1;1299	default:1300		return 0;1301	}1302}1303 1304#undef TYPE1305#define TYPE	isl_space1306#include "check_type_range_templ.c"1307 1308/* Insert "n" dimensions of type "type" at position "pos".1309 * If we are inserting parameters, then they are also inserted in1310 * any nested spaces.1311 */1312__isl_give isl_space *isl_space_insert_dims(__isl_take isl_space *space,1313	enum isl_dim_type type, unsigned pos, unsigned n)1314{1315	isl_ctx *ctx;1316	isl_id **ids = NULL;1317 1318	if (!space)1319		return NULL;1320	if (n == 0)1321		return isl_space_reset(space, type);1322 1323	ctx = isl_space_get_ctx(space);1324	if (!valid_dim_type(type))1325		isl_die(ctx, isl_error_invalid,1326			"cannot insert dimensions of specified type",1327			goto error);1328 1329	if (isl_space_check_range(space, type, pos, 0) < 0)1330		return isl_space_free(space);1331 1332	space = isl_space_cow(space);1333	if (!space)1334		return NULL;1335 1336	if (space->ids) {1337		enum isl_dim_type t, o = isl_dim_param;1338		int off;1339		int s[3];1340		ids = isl_calloc_array(ctx, isl_id *,1341			     space->nparam + space->n_in + space->n_out + n);1342		if (!ids)1343			goto error;1344		off = 0;1345		s[isl_dim_param - o] = space->nparam;1346		s[isl_dim_in - o] = space->n_in;1347		s[isl_dim_out - o] = space->n_out;1348		for (t = isl_dim_param; t <= isl_dim_out; ++t) {1349			if (t != type) {1350				get_ids(space, t, 0, s[t - o], ids + off);1351				off += s[t - o];1352			} else {1353				get_ids(space, t, 0, pos, ids + off);1354				off += pos + n;1355				get_ids(space, t, pos, s[t - o] - pos,1356					ids + off);1357				off += s[t - o] - pos;1358			}1359		}1360		free(space->ids);1361		space->ids = ids;1362		space->n_id = space->nparam + space->n_in + space->n_out + n;1363	}1364	switch (type) {1365	case isl_dim_param:	space->nparam += n; break;1366	case isl_dim_in:	space->n_in += n; break;1367	case isl_dim_out:	space->n_out += n; break;1368	default:		;1369	}1370	space = isl_space_reset(space, type);1371 1372	if (type == isl_dim_param) {1373		if (space && space->nested[0] &&1374		    !(space->nested[0] = isl_space_insert_dims(space->nested[0],1375						    isl_dim_param, pos, n)))1376			goto error;1377		if (space && space->nested[1] &&1378		    !(space->nested[1] = isl_space_insert_dims(space->nested[1],1379						    isl_dim_param, pos, n)))1380			goto error;1381	}1382 1383	return space;1384error:1385	isl_space_free(space);1386	return NULL;1387}1388 1389__isl_give isl_space *isl_space_move_dims(__isl_take isl_space *space,1390	enum isl_dim_type dst_type, unsigned dst_pos,1391	enum isl_dim_type src_type, unsigned src_pos, unsigned n)1392{1393	int i;1394 1395	space = isl_space_reset(space, src_type);1396	space = isl_space_reset(space, dst_type);1397	if (!space)1398		return NULL;1399	if (n == 0)1400		return space;1401 1402	if (isl_space_check_range(space, src_type, src_pos, n) < 0)1403		return isl_space_free(space);1404 1405	if (dst_type == src_type && dst_pos == src_pos)1406		return space;1407 1408	isl_assert(space->ctx, dst_type != src_type, goto error);1409 1410	space = isl_space_cow(space);1411	if (!space)1412		return NULL;1413 1414	if (space->ids) {1415		isl_id **ids;1416		enum isl_dim_type t, o = isl_dim_param;1417		int off;1418		int s[3];1419		ids = isl_calloc_array(space->ctx, isl_id *,1420				 space->nparam + space->n_in + space->n_out);1421		if (!ids)1422			goto error;1423		off = 0;1424		s[isl_dim_param - o] = space->nparam;1425		s[isl_dim_in - o] = space->n_in;1426		s[isl_dim_out - o] = space->n_out;1427		for (t = isl_dim_param; t <= isl_dim_out; ++t) {1428			if (t == dst_type) {1429				get_ids(space, t, 0, dst_pos, ids + off);1430				off += dst_pos;1431				get_ids(space, src_type, src_pos, n, ids + off);1432				off += n;1433				get_ids(space, t, dst_pos, s[t - o] - dst_pos,1434						ids + off);1435				off += s[t - o] - dst_pos;1436			} else if (t == src_type) {1437				get_ids(space, t, 0, src_pos, ids + off);1438				off += src_pos;1439				get_ids(space, t, src_pos + n,1440					    s[t - o] - src_pos - n, ids + off);1441				off += s[t - o] - src_pos - n;1442			} else {1443				get_ids(space, t, 0, s[t - o], ids + off);1444				off += s[t - o];1445			}1446		}1447		free(space->ids);1448		space->ids = ids;1449		space->n_id = space->nparam + space->n_in + space->n_out;1450	}1451 1452	switch (dst_type) {1453	case isl_dim_param:	space->nparam += n; break;1454	case isl_dim_in:	space->n_in += n; break;1455	case isl_dim_out:	space->n_out += n; break;1456	default:		;1457	}1458 1459	switch (src_type) {1460	case isl_dim_param:	space->nparam -= n; break;1461	case isl_dim_in:	space->n_in -= n; break;1462	case isl_dim_out:	space->n_out -= n; break;1463	default:		;1464	}1465 1466	if (dst_type != isl_dim_param && src_type != isl_dim_param)1467		return space;1468 1469	for (i = 0; i < 2; ++i) {1470		isl_space *nested;1471 1472		if (!space->nested[i])1473			continue;1474		nested = isl_space_take_nested(space, i);1475		nested = isl_space_replace_params(nested, space);1476		space = isl_space_restore_nested(space, i, nested);1477		if (!space)1478			return NULL;1479	}1480 1481	return space;1482error:1483	isl_space_free(space);1484	return NULL;1485}1486 1487/* Check that "space1" and "space2" have the same parameters,1488 * reporting an error if they do not.1489 */1490isl_stat isl_space_check_equal_params(__isl_keep isl_space *space1,1491	__isl_keep isl_space *space2)1492{1493	isl_bool equal;1494 1495	equal = isl_space_has_equal_params(space1, space2);1496	if (equal < 0)1497		return isl_stat_error;1498	if (!equal)1499		isl_die(isl_space_get_ctx(space1), isl_error_invalid,1500			"parameters need to match", return isl_stat_error);1501	return isl_stat_ok;1502}1503 1504__isl_give isl_space *isl_space_join(__isl_take isl_space *left,1505	__isl_take isl_space *right)1506{1507	isl_space *space;1508 1509	if (isl_space_check_equal_params(left, right) < 0)1510		goto error;1511 1512	isl_assert(left->ctx,1513		isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_in),1514		goto error);1515 1516	space = isl_space_alloc(left->ctx,1517				left->nparam, left->n_in, right->n_out);1518	if (!space)1519		goto error;1520 1521	space = copy_ids(space, isl_dim_param, 0, left, isl_dim_param);1522	space = copy_ids(space, isl_dim_in, 0, left, isl_dim_in);1523	space = copy_ids(space, isl_dim_out, 0, right, isl_dim_out);1524 1525	if (space && left->tuple_id[0] &&1526	    !(space->tuple_id[0] = isl_id_copy(left->tuple_id[0])))1527		goto error;1528	if (space && right->tuple_id[1] &&1529	    !(space->tuple_id[1] = isl_id_copy(right->tuple_id[1])))1530		goto error;1531	if (space && left->nested[0] &&1532	    !(space->nested[0] = isl_space_copy(left->nested[0])))1533		goto error;1534	if (space && right->nested[1] &&1535	    !(space->nested[1] = isl_space_copy(right->nested[1])))1536		goto error;1537 1538	isl_space_free(left);1539	isl_space_free(right);1540 1541	return space;1542error:1543	isl_space_free(left);1544	isl_space_free(right);1545	return NULL;1546}1547 1548/* Given two map spaces { A -> C } and { B -> D }, construct the space1549 * { [A -> B] -> [C -> D] }.1550 * Given two set spaces { A } and { B }, construct the space { [A -> B] }.1551 */1552__isl_give isl_space *isl_space_product(__isl_take isl_space *left,1553	__isl_take isl_space *right)1554{1555	isl_space *dom1, *dom2, *nest1, *nest2;1556	int is_set;1557 1558	if (!left || !right)1559		goto error;1560 1561	is_set = isl_space_is_set(left);1562	if (is_set != isl_space_is_set(right))1563		isl_die(isl_space_get_ctx(left), isl_error_invalid,1564			"expecting either two set spaces or two map spaces",1565			goto error);1566	if (is_set)1567		return isl_space_range_product(left, right);1568 1569	if (isl_space_check_equal_params(left, right) < 0)1570		goto error;1571 1572	dom1 = isl_space_domain(isl_space_copy(left));1573	dom2 = isl_space_domain(isl_space_copy(right));1574	nest1 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));1575 1576	dom1 = isl_space_range(left);1577	dom2 = isl_space_range(right);1578	nest2 = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));1579 1580	return isl_space_join(isl_space_reverse(nest1), nest2);1581error:1582	isl_space_free(left);1583	isl_space_free(right);1584	return NULL;1585}1586 1587/* Given two spaces { A -> C } and { B -> C }, construct the space1588 * { [A -> B] -> C }1589 */1590__isl_give isl_space *isl_space_domain_product(__isl_take isl_space *left,1591	__isl_take isl_space *right)1592{1593	isl_space *ran, *dom1, *dom2, *nest;1594 1595	if (isl_space_check_equal_params(left, right) < 0)1596		goto error;1597 1598	if (!isl_space_tuple_is_equal(left, isl_dim_out, right, isl_dim_out))1599		isl_die(left->ctx, isl_error_invalid,1600			"ranges need to match", goto error);1601 1602	ran = isl_space_range(isl_space_copy(left));1603 1604	dom1 = isl_space_domain(left);1605	dom2 = isl_space_domain(right);1606	nest = isl_space_wrap(isl_space_join(isl_space_reverse(dom1), dom2));1607 1608	return isl_space_join(isl_space_reverse(nest), ran);1609error:1610	isl_space_free(left);1611	isl_space_free(right);1612	return NULL;1613}1614 1615__isl_give isl_space *isl_space_range_product(__isl_take isl_space *left,1616	__isl_take isl_space *right)1617{1618	isl_space *dom, *ran1, *ran2, *nest;1619 1620	if (isl_space_check_equal_params(left, right) < 0)1621		goto error;1622 1623	if (!isl_space_tuple_is_equal(left, isl_dim_in, right, isl_dim_in))1624		isl_die(left->ctx, isl_error_invalid,1625			"domains need to match", goto error);1626 1627	dom = isl_space_domain(isl_space_copy(left));1628 1629	ran1 = isl_space_range(left);1630	ran2 = isl_space_range(right);1631	nest = isl_space_wrap(isl_space_join(isl_space_reverse(ran1), ran2));1632 1633	return isl_space_join(isl_space_reverse(dom), nest);1634error:1635	isl_space_free(left);1636	isl_space_free(right);1637	return NULL;1638}1639 1640/* Given a space of the form [A -> B] -> C, return the space A -> C.1641 */1642__isl_give isl_space *isl_space_domain_factor_domain(1643	__isl_take isl_space *space)1644{1645	isl_space *nested;1646	isl_space *domain;1647 1648	if (isl_space_check_domain_is_wrapping(space) < 0)1649		return isl_space_free(space);1650 1651	nested = space->nested[0];1652	domain = isl_space_copy(space);1653	domain = isl_space_drop_dims(domain, isl_dim_in,1654					nested->n_in, nested->n_out);1655	if (!domain)1656		return isl_space_free(space);1657	if (nested->tuple_id[0]) {1658		domain->tuple_id[0] = isl_id_copy(nested->tuple_id[0]);1659		if (!domain->tuple_id[0])1660			goto error;1661	}1662	if (nested->nested[0]) {1663		domain->nested[0] = isl_space_copy(nested->nested[0]);1664		if (!domain->nested[0])1665			goto error;1666	}1667 1668	isl_space_free(space);1669	return domain;1670error:1671	isl_space_free(space);1672	isl_space_free(domain);1673	return NULL;1674}1675 1676/* Given a space of the form [A -> B] -> C, return the space B -> C.1677 */1678__isl_give isl_space *isl_space_domain_factor_range(1679	__isl_take isl_space *space)1680{1681	isl_space *nested;1682	isl_space *range;1683 1684	if (isl_space_check_domain_is_wrapping(space) < 0)1685		return isl_space_free(space);1686 1687	nested = space->nested[0];1688	range = isl_space_copy(space);1689	range = isl_space_drop_dims(range, isl_dim_in, 0, nested->n_in);1690	if (!range)1691		return isl_space_free(space);1692	if (nested->tuple_id[1]) {1693		range->tuple_id[0] = isl_id_copy(nested->tuple_id[1]);1694		if (!range->tuple_id[0])1695			goto error;1696	}1697	if (nested->nested[1]) {1698		range->nested[0] = isl_space_copy(nested->nested[1]);1699		if (!range->nested[0])1700			goto error;1701	}1702 1703	isl_space_free(space);1704	return range;1705error:1706	isl_space_free(space);1707	isl_space_free(range);1708	return NULL;1709}1710 1711/* Internal function that selects the domain of the map that is1712 * embedded in either a set space or the range of a map space.1713 * In particular, given a space of the form [A -> B], return the space A.1714 * Given a space of the form A -> [B -> C], return the space A -> B.1715 */1716static __isl_give isl_space *range_factor_domain(__isl_take isl_space *space)1717{1718	isl_space *nested;1719	isl_space *domain;1720 1721	if (!space)1722		return NULL;1723 1724	nested = space->nested[1];1725	domain = isl_space_copy(space);1726	domain = isl_space_drop_dims(domain, isl_dim_out,1727					nested->n_in, nested->n_out);1728	if (!domain)1729		return isl_space_free(space);1730	if (nested->tuple_id[0]) {1731		domain->tuple_id[1] = isl_id_copy(nested->tuple_id[0]);1732		if (!domain->tuple_id[1])1733			goto error;1734	}1735	if (nested->nested[0]) {1736		domain->nested[1] = isl_space_copy(nested->nested[0]);1737		if (!domain->nested[1])1738			goto error;1739	}1740 1741	isl_space_free(space);1742	return domain;1743error:1744	isl_space_free(space);1745	isl_space_free(domain);1746	return NULL;1747}1748 1749/* Given a space of the form A -> [B -> C], return the space A -> B.1750 */1751__isl_give isl_space *isl_space_range_factor_domain(1752	__isl_take isl_space *space)1753{1754	if (isl_space_check_range_is_wrapping(space) < 0)1755		return isl_space_free(space);1756 1757	return range_factor_domain(space);1758}1759 1760/* Given a space of the form [A -> B], return the space A.1761 */1762static __isl_give isl_space *set_factor_domain(__isl_take isl_space *space)1763{1764	if (!space)1765		return NULL;1766	if (!isl_space_is_wrapping(space))1767		isl_die(isl_space_get_ctx(space), isl_error_invalid,1768			"not a product", return isl_space_free(space));1769 1770	return range_factor_domain(space);1771}1772 1773/* Given a space of the form [A -> B] -> [C -> D], return the space A -> C.1774 * Given a space of the form [A -> B], return the space A.1775 */1776__isl_give isl_space *isl_space_factor_domain(__isl_take isl_space *space)1777{1778	if (!space)1779		return NULL;1780	if (isl_space_is_set(space))1781		return set_factor_domain(space);1782	space = isl_space_domain_factor_domain(space);1783	space = isl_space_range_factor_domain(space);1784	return space;1785}1786 1787/* Internal function that selects the range of the map that is1788 * embedded in either a set space or the range of a map space.1789 * In particular, given a space of the form [A -> B], return the space B.1790 * Given a space of the form A -> [B -> C], return the space A -> C.1791 */1792static __isl_give isl_space *range_factor_range(__isl_take isl_space *space)1793{1794	isl_space *nested;1795	isl_space *range;1796 1797	if (!space)1798		return NULL;1799 1800	nested = space->nested[1];1801	range = isl_space_copy(space);1802	range = isl_space_drop_dims(range, isl_dim_out, 0, nested->n_in);1803	if (!range)1804		return isl_space_free(space);1805	if (nested->tuple_id[1]) {1806		range->tuple_id[1] = isl_id_copy(nested->tuple_id[1]);1807		if (!range->tuple_id[1])1808			goto error;1809	}1810	if (nested->nested[1]) {1811		range->nested[1] = isl_space_copy(nested->nested[1]);1812		if (!range->nested[1])1813			goto error;1814	}1815 1816	isl_space_free(space);1817	return range;1818error:1819	isl_space_free(space);1820	isl_space_free(range);1821	return NULL;1822}1823 1824/* Given a space of the form A -> [B -> C], return the space A -> C.1825 */1826__isl_give isl_space *isl_space_range_factor_range(1827	__isl_take isl_space *space)1828{1829	if (isl_space_check_range_is_wrapping(space) < 0)1830		return isl_space_free(space);1831 1832	return range_factor_range(space);1833}1834 1835/* Given a space of the form [A -> B], return the space B.1836 */1837static __isl_give isl_space *set_factor_range(__isl_take isl_space *space)1838{1839	if (!space)1840		return NULL;1841	if (!isl_space_is_wrapping(space))1842		isl_die(isl_space_get_ctx(space), isl_error_invalid,1843			"not a product", return isl_space_free(space));1844 1845	return range_factor_range(space);1846}1847 1848/* Given a space of the form [A -> B] -> [C -> D], return the space B -> D.1849 * Given a space of the form [A -> B], return the space B.1850 */1851__isl_give isl_space *isl_space_factor_range(__isl_take isl_space *space)1852{1853	if (!space)1854		return NULL;1855	if (isl_space_is_set(space))1856		return set_factor_range(space);1857	space = isl_space_domain_factor_range(space);1858	space = isl_space_range_factor_range(space);1859	return space;1860}1861 1862/* Given a space of the form [A -> B] -> C, return the space A.1863 */1864__isl_give isl_space *isl_space_domain_wrapped_domain(1865	__isl_take isl_space *space)1866{1867	return isl_space_factor_domain(isl_space_domain(space));1868}1869 1870/* Given a space of the form [A -> B] -> C, return the space B.1871 */1872__isl_give isl_space *isl_space_domain_wrapped_range(1873	__isl_take isl_space *space)1874{1875	return isl_space_factor_range(isl_space_domain(space));1876}1877 1878/* Given a space of the form A -> [B -> C], return the space B.1879 */1880__isl_give isl_space *isl_space_range_wrapped_domain(1881	__isl_take isl_space *space)1882{1883	return isl_space_factor_domain(isl_space_range(space));1884}1885 1886/* Given a space of the form A -> [B -> C], return the space C.1887 */1888__isl_give isl_space *isl_space_range_wrapped_range(1889	__isl_take isl_space *space)1890{1891	return isl_space_factor_range(isl_space_range(space));1892}1893 1894__isl_give isl_space *isl_space_map_from_set(__isl_take isl_space *space)1895{1896	isl_ctx *ctx;1897	isl_id **ids = NULL;1898	int n_id;1899 1900	if (!space)1901		return NULL;1902	ctx = isl_space_get_ctx(space);1903	if (!isl_space_is_set(space))1904		isl_die(ctx, isl_error_invalid, "not a set space", goto error);1905	space = isl_space_cow(space);1906	if (!space)1907		return NULL;1908	n_id = space->nparam + space->n_out + space->n_out;1909	if (n_id > 0 && space->ids) {1910		ids = isl_calloc_array(space->ctx, isl_id *, n_id);1911		if (!ids)1912			goto error;1913		get_ids(space, isl_dim_param, 0, space->nparam, ids);1914		get_ids(space, isl_dim_out, 0, space->n_out,1915			ids + space->nparam);1916	}1917	space->n_in = space->n_out;1918	if (ids) {1919		free(space->ids);1920		space->ids = ids;1921		space->n_id = n_id;1922		space = copy_ids(space, isl_dim_out, 0, space, isl_dim_in);1923	}1924	isl_id_free(space->tuple_id[0]);1925	space->tuple_id[0] = isl_id_copy(space->tuple_id[1]);1926	isl_space_free(space->nested[0]);1927	space->nested[0] = isl_space_copy(space->nested[1]);1928	return space;1929error:1930	isl_space_free(space);1931	return NULL;1932}1933 1934__isl_give isl_space *isl_space_map_from_domain_and_range(1935	__isl_take isl_space *domain, __isl_take isl_space *range)1936{1937	if (!domain || !range)1938		goto error;1939	if (!isl_space_is_set(domain))1940		isl_die(isl_space_get_ctx(domain), isl_error_invalid,1941			"domain is not a set space", goto error);1942	if (!isl_space_is_set(range))1943		isl_die(isl_space_get_ctx(range), isl_error_invalid,1944			"range is not a set space", goto error);1945	return isl_space_join(isl_space_reverse(domain), range);1946error:1947	isl_space_free(domain);1948	isl_space_free(range);1949	return NULL;1950}1951 1952static __isl_give isl_space *set_ids(__isl_take isl_space *space,1953	enum isl_dim_type type,1954	unsigned first, unsigned n, __isl_take isl_id **ids)1955{1956	int i;1957 1958	for (i = 0; i < n ; ++i)1959		space = set_id(space, type, first + i, ids[i]);1960 1961	return space;1962}1963 1964__isl_give isl_space *isl_space_reverse(__isl_take isl_space *space)1965{1966	unsigned t;1967	isl_bool equal;1968	isl_space *nested;1969	isl_id **ids = NULL;1970	isl_id *id;1971 1972	equal = match(space, isl_dim_in, space, isl_dim_out);1973	if (equal < 0)1974		return isl_space_free(space);1975	if (equal)1976		return space;1977 1978	space = isl_space_cow(space);1979	if (!space)1980		return NULL;1981 1982	id = space->tuple_id[0];1983	space->tuple_id[0] = space->tuple_id[1];1984	space->tuple_id[1] = id;1985 1986	nested = space->nested[0];1987	space->nested[0] = space->nested[1];1988	space->nested[1] = nested;1989 1990	if (space->ids) {1991		int n_id = space->n_in + space->n_out;1992		ids = isl_alloc_array(space->ctx, isl_id *, n_id);1993		if (n_id && !ids)1994			goto error;1995		get_ids(space, isl_dim_in, 0, space->n_in, ids);1996		get_ids(space, isl_dim_out, 0, space->n_out, ids + space->n_in);1997	}1998 1999	t = space->n_in;2000	space->n_in = space->n_out;2001	space->n_out = t;2002 2003	if (space->ids) {2004		space = set_ids(space, isl_dim_out, 0, space->n_out, ids);2005		space = set_ids(space, isl_dim_in, 0, space->n_in,2006				ids + space->n_out);2007		free(ids);2008	}2009 2010	return space;2011error:2012	free(ids);2013	isl_space_free(space);2014	return NULL;2015}2016 2017/* Given a space A -> (B -> C), return the corresponding space2018 * A -> (C -> B).2019 *2020 * If the range tuple is named, then the name is only preserved2021 * if B and C are equal tuples, in which case the output2022 * of this function is identical to the input.2023 */2024__isl_give isl_space *isl_space_range_reverse(__isl_take isl_space *space)2025{2026	isl_space *nested;2027	isl_bool equal;2028 2029	if (isl_space_check_range_is_wrapping(space) < 0)2030		return isl_space_free(space);2031 2032	nested = isl_space_peek_nested(space, 1);2033	equal = isl_space_tuple_is_equal(nested, isl_dim_in,2034					nested, isl_dim_out);2035	if (equal < 0)2036		return isl_space_free(space);2037 2038	nested = isl_space_take_nested(space, 1);2039	nested = isl_space_reverse(nested);2040	space = isl_space_restore_nested(space, 1, nested);2041	if (!equal)2042		space = isl_space_reset_tuple_id(space, isl_dim_out);2043 2044	return space;2045}2046 2047__isl_give isl_space *isl_space_drop_dims(__isl_take isl_space *space,2048	enum isl_dim_type type, unsigned first, unsigned num)2049{2050	int i;2051 2052	if (!space)2053		return NULL;2054 2055	if (num == 0)2056		return isl_space_reset(space, type);2057 2058	if (!valid_dim_type(type))2059		isl_die(space->ctx, isl_error_invalid,2060			"cannot drop dimensions of specified type", goto error);2061 2062	if (isl_space_check_range(space, type, first, num) < 0)2063		return isl_space_free(space);2064	space = isl_space_cow(space);2065	if (!space)2066		goto error;2067	if (space->ids) {2068		space = extend_ids(space);2069		if (!space)2070			goto error;2071		for (i = 0; i < num; ++i)2072			isl_id_free(get_id(space, type, first + i));2073		for (i = first+num; i < n(space, type); ++i)2074			set_id(space, type, i - num, get_id(space, type, i));2075		switch (type) {2076		case isl_dim_param:2077			get_ids(space, isl_dim_in, 0, space->n_in,2078				space->ids + offset(space, isl_dim_in) - num);2079		case isl_dim_in:2080			get_ids(space, isl_dim_out, 0, space->n_out,2081				space->ids + offset(space, isl_dim_out) - num);2082		default:2083			;2084		}2085		space->n_id -= num;2086	}2087	switch (type) {2088	case isl_dim_param:	space->nparam -= num; break;2089	case isl_dim_in:	space->n_in -= num; break;2090	case isl_dim_out:	space->n_out -= num; break;2091	default:		;2092	}2093	space = isl_space_reset(space, type);2094	if (type == isl_dim_param) {2095		if (space && space->nested[0] &&2096		    !(space->nested[0] = isl_space_drop_dims(space->nested[0],2097						    isl_dim_param, first, num)))2098			goto error;2099		if (space && space->nested[1] &&2100		    !(space->nested[1] = isl_space_drop_dims(space->nested[1],2101						    isl_dim_param, first, num)))2102			goto error;2103	}2104	return space;2105error:2106	isl_space_free(space);2107	return NULL;2108}2109 2110__isl_give isl_space *isl_space_drop_inputs(__isl_take isl_space *space,2111		unsigned first, unsigned n)2112{2113	if (!space)2114		return NULL;2115	return isl_space_drop_dims(space, isl_dim_in, first, n);2116}2117 2118__isl_give isl_space *isl_space_drop_outputs(__isl_take isl_space *space,2119		unsigned first, unsigned n)2120{2121	if (!space)2122		return NULL;2123	return isl_space_drop_dims(space, isl_dim_out, first, n);2124}2125 2126/* Remove all parameters from "space".2127 */2128__isl_give isl_space *isl_space_drop_all_params(__isl_take isl_space *space)2129{2130	isl_size nparam;2131 2132	nparam = isl_space_dim(space, isl_dim_param);2133	if (nparam < 0)2134		return isl_space_free(space);2135	return isl_space_drop_dims(space, isl_dim_param, 0, nparam);2136}2137 2138__isl_give isl_space *isl_space_domain(__isl_take isl_space *space)2139{2140	if (!space)2141		return NULL;2142	space = isl_space_drop_dims(space, isl_dim_out, 0, space->n_out);2143	space = isl_space_reverse(space);2144	space = mark_as_set(space);2145	return space;2146}2147 2148__isl_give isl_space *isl_space_from_domain(__isl_take isl_space *space)2149{2150	if (!space)2151		return NULL;2152	if (!isl_space_is_set(space))2153		isl_die(isl_space_get_ctx(space), isl_error_invalid,2154			"not a set space", goto error);2155	space = isl_space_reverse(space);2156	space = isl_space_reset(space, isl_dim_out);2157	return space;2158error:2159	isl_space_free(space);2160	return NULL;2161}2162 2163__isl_give isl_space *isl_space_range(__isl_take isl_space *space)2164{2165	if (!space)2166		return NULL;2167	space = isl_space_drop_dims(space, isl_dim_in, 0, space->n_in);2168	space = mark_as_set(space);2169	return space;2170}2171 2172__isl_give isl_space *isl_space_from_range(__isl_take isl_space *space)2173{2174	if (!space)2175		return NULL;2176	if (!isl_space_is_set(space))2177		isl_die(isl_space_get_ctx(space), isl_error_invalid,2178			"not a set space", goto error);2179	return isl_space_reset(space, isl_dim_in);2180error:2181	isl_space_free(space);2182	return NULL;2183}2184 2185/* Given a map space A -> B, return the map space [A -> B] -> A.2186 */2187__isl_give isl_space *isl_space_domain_map(__isl_take isl_space *space)2188{2189	isl_space *domain;2190 2191	domain = isl_space_from_range(isl_space_domain(isl_space_copy(space)));2192	space = isl_space_from_domain(isl_space_wrap(space));2193	space = isl_space_join(space, domain);2194 2195	return space;2196}2197 2198/* Given a map space A -> B, return the map space [A -> B] -> B.2199 */2200__isl_give isl_space *isl_space_range_map(__isl_take isl_space *space)2201{2202	isl_space *range;2203 2204	range = isl_space_from_range(isl_space_range(isl_space_copy(space)));2205	space = isl_space_from_domain(isl_space_wrap(space));2206	space = isl_space_join(space, range);2207 2208	return space;2209}2210 2211__isl_give isl_space *isl_space_params(__isl_take isl_space *space)2212{2213	isl_size n_in, n_out;2214 2215	if (isl_space_is_params(space))2216		return space;2217	n_in = isl_space_dim(space, isl_dim_in);2218	n_out = isl_space_dim(space, isl_dim_out);2219	if (n_in < 0 || n_out < 0)2220		return isl_space_free(space);2221	space = isl_space_drop_dims(space, isl_dim_in, 0, n_in);2222	space = isl_space_drop_dims(space, isl_dim_out, 0, n_out);2223	space = mark_as_params(space);2224	return space;2225}2226 2227__isl_give isl_space *isl_space_set_from_params(__isl_take isl_space *space)2228{2229	if (!space)2230		return NULL;2231	if (!isl_space_is_params(space))2232		isl_die(isl_space_get_ctx(space), isl_error_invalid,2233			"not a parameter space", goto error);2234	return isl_space_reset(space, isl_dim_set);2235error:2236	isl_space_free(space);2237	return NULL;2238}2239 2240/* Add an unnamed tuple of dimension "dim" to "space".2241 * This requires "space" to be a parameter or set space.2242 *2243 * In particular, if "space" is a parameter space, then return2244 * a set space with the given dimension.2245 * If "space" is a set space, then return a map space2246 * with "space" as domain and a range of the given dimension.2247 */2248__isl_give isl_space *isl_space_add_unnamed_tuple_ui(2249	__isl_take isl_space *space, unsigned dim)2250{2251	isl_bool is_params, is_set;2252 2253	is_params = isl_space_is_params(space);2254	is_set = isl_space_is_set(space);2255	if (is_params < 0 || is_set < 0)2256		return isl_space_free(space);2257	if (!is_params && !is_set)2258		isl_die(isl_space_get_ctx(space), isl_error_invalid,2259			"cannot add tuple to map space",2260			return isl_space_free(space));2261	if (is_params)2262		space = isl_space_set_from_params(space);2263	else2264		space = isl_space_from_domain(space);2265	space = isl_space_add_dims(space, isl_dim_out, dim);2266	return space;2267}2268 2269/* Add a tuple of dimension "dim" and with tuple identifier "tuple_id"2270 * to "space".2271 * This requires "space" to be a parameter or set space.2272 */2273__isl_give isl_space *isl_space_add_named_tuple_id_ui(2274	__isl_take isl_space *space, __isl_take isl_id *tuple_id, unsigned dim)2275{2276	space = isl_space_add_unnamed_tuple_ui(space, dim);2277	space = isl_space_set_tuple_id(space, isl_dim_out, tuple_id);2278	return space;2279}2280 2281/* Check that the identifiers in "tuple" do not appear as parameters2282 * in "space".2283 */2284static isl_stat check_fresh_params(__isl_keep isl_space *space,2285	__isl_keep isl_multi_id *tuple)2286{2287	int i;2288	isl_size n;2289 2290	n = isl_multi_id_size(tuple);2291	if (n < 0)2292		return isl_stat_error;2293	for (i = 0; i < n; ++i) {2294		isl_id *id;2295		int pos;2296 2297		id = isl_multi_id_get_at(tuple, i);2298		if (!id)2299			return isl_stat_error;2300		pos = isl_space_find_dim_by_id(space, isl_dim_param, id);2301		isl_id_free(id);2302		if (pos >= 0)2303			isl_die(isl_space_get_ctx(space), isl_error_invalid,2304				"parameters not unique", return isl_stat_error);2305	}2306 2307	return isl_stat_ok;2308}2309 2310/* Add the identifiers in "tuple" as parameters of "space"2311 * that are known to be fresh.2312 */2313static __isl_give isl_space *add_bind_params(__isl_take isl_space *space,2314	__isl_keep isl_multi_id *tuple)2315{2316	int i;2317	isl_size first, n;2318 2319	first = isl_space_dim(space, isl_dim_param);2320	n = isl_multi_id_size(tuple);2321	if (first < 0 || n < 0)2322		return isl_space_free(space);2323	space = isl_space_add_dims(space, isl_dim_param, n);2324	for (i = 0; i < n; ++i) {2325		isl_id *id;2326 2327		id = isl_multi_id_get_at(tuple, i);2328		space = isl_space_set_dim_id(space,2329						isl_dim_param, first + i, id);2330	}2331 2332	return space;2333}2334 2335/* Internal function that removes the set tuple of "space",2336 * which is assumed to correspond to the range space of "tuple", and2337 * adds the identifiers in "tuple" as fresh parameters.2338 * In other words, the set dimensions of "space" are reinterpreted2339 * as parameters, but stay in the same global positions.2340 */2341__isl_give isl_space *isl_space_bind_set(__isl_take isl_space *space,2342	__isl_keep isl_multi_id *tuple)2343{2344	isl_space *tuple_space;2345 2346	if (isl_space_check_is_set(space) < 0)2347		return isl_space_free(space);2348	tuple_space = isl_multi_id_peek_space(tuple);2349	if (isl_space_check_equal_tuples(tuple_space, space) < 0)2350		return isl_space_free(space);2351	if (check_fresh_params(space, tuple) < 0)2352		return isl_space_free(space);2353	space = isl_space_params(space);2354	space = add_bind_params(space, tuple);2355	return space;2356}2357 2358/* Internal function that removes the domain tuple of the map space "space",2359 * which is assumed to correspond to the range space of "tuple", and2360 * adds the identifiers in "tuple" as fresh parameters.2361 * In other words, the domain dimensions of "space" are reinterpreted2362 * as parameters, but stay in the same global positions.2363 */2364__isl_give isl_space *isl_space_bind_map_domain(__isl_take isl_space *space,2365	__isl_keep isl_multi_id *tuple)2366{2367	isl_space *tuple_space;2368 2369	if (isl_space_check_is_map(space) < 0)2370		return isl_space_free(space);2371	tuple_space = isl_multi_id_peek_space(tuple);2372	if (isl_space_check_domain_tuples(tuple_space, space) < 0)2373		return isl_space_free(space);2374	if (check_fresh_params(space, tuple) < 0)2375		return isl_space_free(space);2376	space = isl_space_range(space);2377	space = add_bind_params(space, tuple);2378	return space;2379}2380 2381/* Internal function that, given a space of the form [A -> B] -> C and2382 * a tuple of identifiers in A, returns a space B -> C with2383 * the identifiers in "tuple" added as fresh parameters.2384 * In other words, the domain dimensions of the wrapped relation2385 * in the domain of "space" are reinterpreted2386 * as parameters, but stay in the same global positions.2387 */2388__isl_give isl_space *isl_space_bind_domain_wrapped_domain(2389	__isl_take isl_space *space, __isl_keep isl_multi_id *tuple)2390{2391	isl_space *tuple_space;2392 2393	if (isl_space_check_is_map(space) < 0)2394		return isl_space_free(space);2395	tuple_space = isl_multi_id_peek_space(tuple);2396	if (isl_space_check_domain_wrapped_domain_tuples(tuple_space,2397							space) < 0)2398		  return isl_space_free(space);2399	if (check_fresh_params(space, tuple) < 0)2400		return isl_space_free(space);2401	space = isl_space_domain_factor_range(space);2402	space = add_bind_params(space, tuple);2403	return space;2404}2405 2406/* Insert a domain tuple in "space" corresponding to the set space "domain".2407 * In particular, if "space" is a parameter space, then the result2408 * is the set space "domain" combined with the parameters of "space".2409 * If "space" is a set space, then the result2410 * is a map space with "domain" as domain and the original space as range.2411 */2412static __isl_give isl_space *isl_space_insert_domain(2413	__isl_take isl_space *space, __isl_take isl_space *domain)2414{2415	isl_bool is_params;2416 2417	domain = isl_space_replace_params(domain, space);2418 2419	is_params = isl_space_is_params(space);2420	if (is_params < 0) {2421		isl_space_free(domain);2422		space = isl_space_free(space);2423	} else if (is_params) {2424		isl_space_free(space);2425		space = domain;2426	} else {2427		space = isl_space_map_from_domain_and_range(domain, space);2428	}2429	return space;2430}2431 2432/* Internal function that introduces a domain in "space"2433 * corresponding to the range space of "tuple".2434 * In particular, if "space" is a parameter space, then the result2435 * is a set space.  If "space" is a set space, then the result2436 * is a map space with the original space as range.2437 * Parameters that correspond to the identifiers in "tuple" are removed.2438 *2439 * The parameters are removed in reverse order (under the assumption2440 * that they appear in the same order in "multi") because2441 * it is slightly more efficient to remove parameters at the end.2442 *2443 * For pretty-printing purposes, the identifiers of the set dimensions2444 * of the introduced domain are set to the identifiers in "tuple".2445 */2446__isl_give isl_space *isl_space_unbind_params_insert_domain(2447	__isl_take isl_space *space, __isl_keep isl_multi_id *tuple)2448{2449	int i;2450	isl_size n;2451	isl_space *tuple_space;2452 2453	n = isl_multi_id_size(tuple);2454	if (!space || n < 0)2455		return isl_space_free(space);2456	for (i = n - 1; i >= 0; --i) {2457		isl_id *id;2458		int pos;2459 2460		id = isl_multi_id_get_id(tuple, i);2461		if (!id)2462			return isl_space_free(space);2463		pos = isl_space_find_dim_by_id(space, isl_dim_param, id);2464		isl_id_free(id);2465		if (pos < 0)2466			continue;2467		space = isl_space_drop_dims(space, isl_dim_param, pos, 1);2468	}2469	tuple_space = isl_multi_id_get_space(tuple);2470	for (i = 0; i < n; ++i) {2471		isl_id *id;2472 2473		id = isl_multi_id_get_id(tuple, i);2474		tuple_space = isl_space_set_dim_id(tuple_space,2475						    isl_dim_set, i, id);2476	}2477	return isl_space_insert_domain(space, tuple_space);2478}2479 2480__isl_give isl_space *isl_space_underlying(__isl_take isl_space *space,2481	unsigned n_div)2482{2483	int i;2484	isl_bool is_set;2485 2486	is_set = isl_space_is_set(space);2487	if (is_set < 0)2488		return isl_space_free(space);2489	if (n_div == 0 && is_set &&2490	    space->nparam == 0 && space->n_in == 0 && space->n_id == 0)2491		return isl_space_reset(space, isl_dim_out);2492	space = isl_space_cow(space);2493	if (!space)2494		return NULL;2495	space->n_out += space->nparam + space->n_in + n_div;2496	space->nparam = 0;2497	space->n_in = 0;2498 2499	for (i = 0; i < space->n_id; ++i)2500		isl_id_free(get_id(space, isl_dim_out, i));2501	space->n_id = 0;2502	space = isl_space_reset(space, isl_dim_in);2503	space = isl_space_reset(space, isl_dim_out);2504	space = mark_as_set(space);2505 2506	return space;2507}2508 2509/* Are the two spaces the same, including positions and names of parameters?2510 */2511isl_bool isl_space_is_equal(__isl_keep isl_space *space1,2512	__isl_keep isl_space *space2)2513{2514	isl_bool equal;2515 2516	if (!space1 || !space2)2517		return isl_bool_error;2518	if (space1 == space2)2519		return isl_bool_true;2520	equal = isl_space_has_equal_params(space1, space2);2521	if (equal < 0 || !equal)2522		return equal;2523	return isl_space_has_equal_tuples(space1, space2);2524}2525 2526/* Do the tuples of "space1" correspond to those of the domain of "space2"?2527 * That is, is "space1" equal to the domain of "space2", ignoring parameters.2528 *2529 * "space2" is allowed to be a set space, in which case "space1"2530 * should be a parameter space.2531 */2532isl_bool isl_space_has_domain_tuples(__isl_keep isl_space *space1,2533	__isl_keep isl_space *space2)2534{2535	isl_bool is_set;2536 2537	is_set = isl_space_is_set(space1);2538	if (is_set < 0 || !is_set)2539		return is_set;2540	return isl_space_tuple_is_equal(space1, isl_dim_set,2541					space2, isl_dim_in);2542}2543 2544/* Do the tuples of "space1" correspond to those of the range of "space2"?2545 * That is, is "space1" equal to the range of "space2", ignoring parameters.2546 *2547 * "space2" is allowed to be the space of a set,2548 * in which case it should be equal to "space1", ignoring parameters.2549 */2550isl_bool isl_space_has_range_tuples(__isl_keep isl_space *space1,2551	__isl_keep isl_space *space2)2552{2553	isl_bool is_set;2554 2555	is_set = isl_space_is_set(space1);2556	if (is_set < 0 || !is_set)2557		return is_set;2558	return isl_space_tuple_is_equal(space1, isl_dim_set,2559					space2, isl_dim_out);2560}2561 2562/* Check that the tuples of "space1" correspond to those2563 * of the domain of "space2".2564 * That is, check that "space1" is equal to the domain of "space2",2565 * ignoring parameters.2566 */2567isl_stat isl_space_check_domain_tuples(__isl_keep isl_space *space1,2568	__isl_keep isl_space *space2)2569{2570	isl_bool is_equal;2571 2572	is_equal = isl_space_has_domain_tuples(space1, space2);2573	return check_match(space1, is_equal);2574}2575 2576/* Check that the tuples of "space1" correspond to those2577 * of the domain of the wrapped relation in the domain of "space2".2578 * That is, check that "space1" is equal to this domain,2579 * ignoring parameters.2580 */2581isl_stat isl_space_check_domain_wrapped_domain_tuples(2582	__isl_keep isl_space *space1, __isl_keep isl_space *space2)2583{2584	isl_space *domain;2585	isl_stat r;2586 2587	domain = isl_space_unwrap(isl_space_domain(isl_space_copy(space2)));2588	r = isl_space_check_domain_tuples(space1, domain);2589	isl_space_free(domain);2590 2591	return r;2592}2593 2594/* Is space1 equal to the domain of space2?2595 *2596 * In the internal version we also allow space2 to be the space of a set,2597 * provided space1 is a parameter space.2598 */2599isl_bool isl_space_is_domain_internal(__isl_keep isl_space *space1,2600	__isl_keep isl_space *space2)2601{2602	isl_bool equal_params;2603 2604	if (!space1 || !space2)2605		return isl_bool_error;2606	equal_params = isl_space_has_equal_params(space1, space2);2607	if (equal_params < 0 || !equal_params)2608		return equal_params;2609	return isl_space_has_domain_tuples(space1, space2);2610}2611 2612/* Is space1 equal to the domain of space2?2613 */2614isl_bool isl_space_is_domain(__isl_keep isl_space *space1,2615	__isl_keep isl_space *space2)2616{2617	if (!space2)2618		return isl_bool_error;2619	if (!isl_space_is_map(space2))2620		return isl_bool_false;2621	return isl_space_is_domain_internal(space1, space2);2622}2623 2624/* Is space1 equal to the range of space2?2625 *2626 * In the internal version, space2 is allowed to be the space of a set,2627 * in which case it should be equal to space1.2628 */2629isl_bool isl_space_is_range_internal(__isl_keep isl_space *space1,2630	__isl_keep isl_space *space2)2631{2632	isl_bool equal_params;2633 2634	if (!space1 || !space2)2635		return isl_bool_error;2636	equal_params = isl_space_has_equal_params(space1, space2);2637	if (equal_params < 0 || !equal_params)2638		return equal_params;2639	return isl_space_has_range_tuples(space1, space2);2640}2641 2642/* Is space1 equal to the range of space2?2643 */2644isl_bool isl_space_is_range(__isl_keep isl_space *space1,2645	__isl_keep isl_space *space2)2646{2647	if (!space2)2648		return isl_bool_error;2649	if (!isl_space_is_map(space2))2650		return isl_bool_false;2651	return isl_space_is_range_internal(space1, space2);2652}2653 2654/* Update "hash" by hashing in the parameters of "space".2655 */2656static uint32_t isl_hash_params(uint32_t hash, __isl_keep isl_space *space)2657{2658	int i;2659	isl_id *id;2660 2661	if (!space)2662		return hash;2663 2664	isl_hash_byte(hash, space->nparam % 256);2665 2666	for (i = 0; i < space->nparam; ++i) {2667		id = get_id(space, isl_dim_param, i);2668		hash = isl_hash_id(hash, id);2669	}2670 2671	return hash;2672}2673 2674/* Update "hash" by hashing in the tuples of "space".2675 * Changes in this function should be reflected in isl_hash_tuples_domain.2676 */2677static uint32_t isl_hash_tuples(uint32_t hash, __isl_keep isl_space *space)2678{2679	isl_id *id;2680 2681	if (!space)2682		return hash;2683 2684	isl_hash_byte(hash, space->n_in % 256);2685	isl_hash_byte(hash, space->n_out % 256);2686 2687	id = tuple_id(space, isl_dim_in);2688	hash = isl_hash_id(hash, id);2689	id = tuple_id(space, isl_dim_out);2690	hash = isl_hash_id(hash, id);2691 2692	hash = isl_hash_tuples(hash, space->nested[0]);2693	hash = isl_hash_tuples(hash, space->nested[1]);2694 2695	return hash;2696}2697 2698/* Update "hash" by hashing in the domain tuple of "space".2699 * The result of this function is equal to the result of applying2700 * isl_hash_tuples to the domain of "space".2701 */2702static uint32_t isl_hash_tuples_domain(uint32_t hash,2703	__isl_keep isl_space *space)2704{2705	isl_id *id;2706 2707	if (!space)2708		return hash;2709 2710	isl_hash_byte(hash, 0);2711	isl_hash_byte(hash, space->n_in % 256);2712 2713	hash = isl_hash_id(hash, &isl_id_none);2714	id = tuple_id(space, isl_dim_in);2715	hash = isl_hash_id(hash, id);2716 2717	hash = isl_hash_tuples(hash, space->nested[0]);2718 2719	return hash;2720}2721 2722/* Return a hash value that digests the tuples of "space",2723 * i.e., that ignores the parameters.2724 * Changes in this function should be reflected2725 * in isl_space_get_tuple_domain_hash.2726 */2727uint32_t isl_space_get_tuple_hash(__isl_keep isl_space *space)2728{2729	uint32_t hash;2730 2731	if (!space)2732		return 0;2733 2734	hash = isl_hash_init();2735	hash = isl_hash_tuples(hash, space);2736 2737	return hash;2738}2739 2740/* Return the hash value of "space".2741 */2742uint32_t isl_space_get_full_hash(__isl_keep isl_space *space)2743{2744	uint32_t hash;2745 2746	if (!space)2747		return 0;2748 2749	hash = isl_hash_init();2750	hash = isl_hash_params(hash, space);2751	hash = isl_hash_tuples(hash, space);2752 2753	return hash;2754}2755 2756/* Return the hash value of the domain tuple of "space".2757 * That is, isl_space_get_tuple_domain_hash(space) is equal to2758 * isl_space_get_tuple_hash(isl_space_domain(space)).2759 */2760uint32_t isl_space_get_tuple_domain_hash(__isl_keep isl_space *space)2761{2762	uint32_t hash;2763 2764	if (!space)2765		return 0;2766 2767	hash = isl_hash_init();2768	hash = isl_hash_tuples_domain(hash, space);2769 2770	return hash;2771}2772 2773/* Is "space" the space of a set wrapping a map space?2774 */2775isl_bool isl_space_is_wrapping(__isl_keep isl_space *space)2776{2777	if (!space)2778		return isl_bool_error;2779 2780	if (!isl_space_is_set(space))2781		return isl_bool_false;2782 2783	return isl_bool_ok(space->nested[1] != NULL);2784}2785 2786/* Is "space" the space of a map where the domain is a wrapped map space?2787 */2788isl_bool isl_space_domain_is_wrapping(__isl_keep isl_space *space)2789{2790	if (!space)2791		return isl_bool_error;2792 2793	if (isl_space_is_set(space))2794		return isl_bool_false;2795 2796	return isl_bool_ok(space->nested[0] != NULL);2797}2798 2799/* Is "space" the space of a map where the range is a wrapped map space?2800 */2801isl_bool isl_space_range_is_wrapping(__isl_keep isl_space *space)2802{2803	if (!space)2804		return isl_bool_error;2805 2806	if (isl_space_is_set(space))2807		return isl_bool_false;2808 2809	return isl_bool_ok(space->nested[1] != NULL);2810}2811 2812/* Is "space" a product of two spaces?2813 * That is, is it a wrapping set space or a map space2814 * with wrapping domain and range?2815 */2816isl_bool isl_space_is_product(__isl_keep isl_space *space)2817{2818	isl_bool is_set;2819	isl_bool is_product;2820 2821	is_set = isl_space_is_set(space);2822	if (is_set < 0)2823		return isl_bool_error;2824	if (is_set)2825		return isl_space_is_wrapping(space);2826	is_product = isl_space_domain_is_wrapping(space);2827	if (is_product < 0 || !is_product)2828		return is_product;2829	return isl_space_range_is_wrapping(space);2830}2831 2832__isl_give isl_space *isl_space_wrap(__isl_take isl_space *space)2833{2834	isl_space *wrap;2835 2836	if (!space)2837		return NULL;2838 2839	wrap = isl_space_set_alloc(space->ctx,2840				    space->nparam, space->n_in + space->n_out);2841 2842	wrap = copy_ids(wrap, isl_dim_param, 0, space, isl_dim_param);2843	wrap = copy_ids(wrap, isl_dim_set, 0, space, isl_dim_in);2844	wrap = copy_ids(wrap, isl_dim_set, space->n_in, space, isl_dim_out);2845 2846	if (!wrap)2847		goto error;2848 2849	wrap->nested[1] = space;2850 2851	return wrap;2852error:2853	isl_space_free(space);2854	return NULL;2855}2856 2857__isl_give isl_space *isl_space_unwrap(__isl_take isl_space *space)2858{2859	isl_space *unwrap;2860 2861	if (!space)2862		return NULL;2863 2864	if (!isl_space_is_wrapping(space))2865		isl_die(space->ctx, isl_error_invalid, "not a wrapping space",2866			goto error);2867 2868	unwrap = isl_space_copy(space->nested[1]);2869	isl_space_free(space);2870 2871	return unwrap;2872error:2873	isl_space_free(space);2874	return NULL;2875}2876 2877isl_bool isl_space_is_named_or_nested(__isl_keep isl_space *space,2878	enum isl_dim_type type)2879{2880	if (type != isl_dim_in && type != isl_dim_out)2881		return isl_bool_false;2882	if (!space)2883		return isl_bool_error;2884	if (space->tuple_id[type - isl_dim_in])2885		return isl_bool_true;2886	if (space->nested[type - isl_dim_in])2887		return isl_bool_true;2888	return isl_bool_false;2889}2890 2891isl_bool isl_space_may_be_set(__isl_keep isl_space *space)2892{2893	isl_bool nested;2894	isl_size n_in;2895 2896	if (!space)2897		return isl_bool_error;2898	if (isl_space_is_set(space))2899		return isl_bool_true;2900	n_in = isl_space_dim(space, isl_dim_in);2901	if (n_in < 0)2902		return isl_bool_error;2903	if (n_in != 0)2904		return isl_bool_false;2905	nested = isl_space_is_named_or_nested(space, isl_dim_in);2906	if (nested < 0 || nested)2907		return isl_bool_not(nested);2908	return isl_bool_true;2909}2910 2911__isl_give isl_space *isl_space_reset(__isl_take isl_space *space,2912	enum isl_dim_type type)2913{2914	if (!isl_space_is_named_or_nested(space, type))2915		return space;2916 2917	space = isl_space_cow(space);2918	if (!space)2919		return NULL;2920 2921	isl_id_free(space->tuple_id[type - isl_dim_in]);2922	space->tuple_id[type - isl_dim_in] = NULL;2923	isl_space_free(space->nested[type - isl_dim_in]);2924	space->nested[type - isl_dim_in] = NULL;2925 2926	return space;2927}2928 2929__isl_give isl_space *isl_space_flatten(__isl_take isl_space *space)2930{2931	if (!space)2932		return NULL;2933	if (!space->nested[0] && !space->nested[1])2934		return space;2935 2936	if (space->nested[0])2937		space = isl_space_reset(space, isl_dim_in);2938	if (space && space->nested[1])2939		space = isl_space_reset(space, isl_dim_out);2940 2941	return space;2942}2943 2944__isl_give isl_space *isl_space_flatten_domain(__isl_take isl_space *space)2945{2946	if (!space)2947		return NULL;2948	if (!space->nested[0])2949		return space;2950 2951	return isl_space_reset(space, isl_dim_in);2952}2953 2954__isl_give isl_space *isl_space_flatten_range(__isl_take isl_space *space)2955{2956	if (!space)2957		return NULL;2958	if (!space->nested[1])2959		return space;2960 2961	return isl_space_reset(space, isl_dim_out);2962}2963 2964/* Replace the parameters of dst by those of src.2965 */2966__isl_give isl_space *isl_space_replace_params(__isl_take isl_space *dst,2967	__isl_keep isl_space *src)2968{2969	isl_size dst_dim, src_dim;2970	isl_bool equal_params;2971	enum isl_dim_type type = isl_dim_param;2972 2973	equal_params = isl_space_has_equal_params(dst, src);2974	if (equal_params < 0)2975		return isl_space_free(dst);2976	if (equal_params)2977		return dst;2978 2979	dst = isl_space_cow(dst);2980 2981	dst_dim = isl_space_dim(dst, type);2982	src_dim = isl_space_dim(src, type);2983	if (dst_dim < 0 || src_dim < 0)2984		goto error;2985 2986	dst = isl_space_drop_dims(dst, type, 0, dst_dim);2987	dst = isl_space_add_dims(dst, type, src_dim);2988	dst = copy_ids(dst, type, 0, src, type);2989 2990	if (dst) {2991		int i;2992		for (i = 0; i <= 1; ++i) {2993			isl_space *nested;2994 2995			if (!dst->nested[i])2996				continue;2997			nested = isl_space_take_nested(dst, i);2998			nested = isl_space_replace_params(nested, src);2999			dst = isl_space_restore_nested(dst, i, nested);3000			if (!dst)3001				return NULL;3002		}3003	}3004 3005	return dst;3006error:3007	isl_space_free(dst);3008	return NULL;3009}3010 3011/* Given two tuples ("dst_type" in "dst" and "src_type" in "src")3012 * of the same size, check if any of the dimensions in the "dst" tuple3013 * have no identifier, while the corresponding dimensions in "src"3014 * does have an identifier,3015 * If so, copy the identifier over to "dst".3016 */3017__isl_give isl_space *isl_space_copy_ids_if_unset(__isl_take isl_space *dst,3018	enum isl_dim_type dst_type, __isl_keep isl_space *src,3019	enum isl_dim_type src_type)3020{3021	int i;3022	isl_size n;3023 3024	n = isl_space_dim(dst, dst_type);3025	if (n < 0)3026		return isl_space_free(dst);3027	for (i = 0; i < n; ++i) {3028		isl_bool set;3029		isl_id *id;3030 3031		set = isl_space_has_dim_id(dst, dst_type, i);3032		if (set < 0)3033			return isl_space_free(dst);3034		if (set)3035			continue;3036 3037		set = isl_space_has_dim_id(src, src_type, i);3038		if (set < 0)3039			return isl_space_free(dst);3040		if (!set)3041			continue;3042 3043		id = isl_space_get_dim_id(src, src_type, i);3044		dst = isl_space_set_dim_id(dst, dst_type, i, id);3045	}3046 3047	return dst;3048}3049 3050/* Given a space "space" of a set, create a space3051 * for the lift of the set.  In particular, the result3052 * is of the form lifted[space -> local[..]], with n_local variables in the3053 * range of the wrapped map.3054 */3055__isl_give isl_space *isl_space_lift(__isl_take isl_space *space,3056	unsigned n_local)3057{3058	isl_space *local_space;3059 3060	if (!space)3061		return NULL;3062 3063	local_space = isl_space_dup(space);3064	local_space = isl_space_drop_dims(local_space, isl_dim_set, 0,3065					space->n_out);3066	local_space = isl_space_add_dims(local_space, isl_dim_set, n_local);3067	local_space = isl_space_set_tuple_name(local_space,3068						isl_dim_set, "local");3069	space = isl_space_join(isl_space_from_domain(space),3070			    isl_space_from_range(local_space));3071	space = isl_space_wrap(space);3072	space = isl_space_set_tuple_name(space, isl_dim_set, "lifted");3073 3074	return space;3075}3076 3077isl_bool isl_space_can_zip(__isl_keep isl_space *space)3078{3079	isl_bool is_set;3080 3081	is_set = isl_space_is_set(space);3082	if (is_set < 0)3083		return isl_bool_error;3084	if (is_set)3085		return isl_bool_false;3086	return isl_space_is_product(space);3087}3088 3089__isl_give isl_space *isl_space_zip(__isl_take isl_space *space)3090{3091	isl_space *dom, *ran;3092	isl_space *dom_dom, *dom_ran, *ran_dom, *ran_ran;3093 3094	if (!isl_space_can_zip(space))3095		isl_die(space->ctx, isl_error_invalid, "space cannot be zipped",3096			goto error);3097 3098	if (!space)3099		return NULL;3100	dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));3101	ran = isl_space_unwrap(isl_space_range(space));3102	dom_dom = isl_space_domain(isl_space_copy(dom));3103	dom_ran = isl_space_range(dom);3104	ran_dom = isl_space_domain(isl_space_copy(ran));3105	ran_ran = isl_space_range(ran);3106	dom = isl_space_join(isl_space_from_domain(dom_dom),3107			   isl_space_from_range(ran_dom));3108	ran = isl_space_join(isl_space_from_domain(dom_ran),3109			   isl_space_from_range(ran_ran));3110	return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),3111			    isl_space_from_range(isl_space_wrap(ran)));3112error:3113	isl_space_free(space);3114	return NULL;3115}3116 3117/* Can we apply isl_space_curry to "space"?3118 * That is, does is it have a map space with a nested relation in its domain?3119 */3120isl_bool isl_space_can_curry(__isl_keep isl_space *space)3121{3122	return isl_space_domain_is_wrapping(space);3123}3124 3125/* Given a space (A -> B) -> C, return the corresponding space3126 * A -> (B -> C).3127 */3128__isl_give isl_space *isl_space_curry(__isl_take isl_space *space)3129{3130	isl_space *dom, *ran;3131	isl_space *dom_dom, *dom_ran;3132 3133	if (!space)3134		return NULL;3135 3136	if (!isl_space_can_curry(space))3137		isl_die(space->ctx, isl_error_invalid,3138			"space cannot be curried", goto error);3139 3140	dom = isl_space_unwrap(isl_space_domain(isl_space_copy(space)));3141	ran = isl_space_range(space);3142	dom_dom = isl_space_domain(isl_space_copy(dom));3143	dom_ran = isl_space_range(dom);3144	ran = isl_space_join(isl_space_from_domain(dom_ran),3145			   isl_space_from_range(ran));3146	return isl_space_join(isl_space_from_domain(dom_dom),3147			    isl_space_from_range(isl_space_wrap(ran)));3148error:3149	isl_space_free(space);3150	return NULL;3151}3152 3153/* Can isl_space_range_curry be applied to "space"?3154 * That is, does it have a nested relation in its range,3155 * the domain of which is itself a nested relation?3156 */3157isl_bool isl_space_can_range_curry(__isl_keep isl_space *space)3158{3159	isl_bool can;3160 3161	if (!space)3162		return isl_bool_error;3163	can = isl_space_range_is_wrapping(space);3164	if (can < 0 || !can)3165		return can;3166	return isl_space_can_curry(space->nested[1]);3167}3168 3169/* Given a space A -> ((B -> C) -> D), return the corresponding space3170 * A -> (B -> (C -> D)).3171 */3172__isl_give isl_space *isl_space_range_curry(__isl_take isl_space *space)3173{3174	isl_space *nested;3175 3176	if (!space)3177		return NULL;3178 3179	if (!isl_space_can_range_curry(space))3180		isl_die(isl_space_get_ctx(space), isl_error_invalid,3181			"space range cannot be curried",3182			return isl_space_free(space));3183 3184	nested = isl_space_take_nested(space, 1);3185	nested = isl_space_curry(nested);3186	space = isl_space_restore_nested(space, 1, nested);3187 3188	return space;3189}3190 3191/* Can we apply isl_space_uncurry to "space"?3192 * That is, does it have a map space with a nested relation in its range?3193 */3194isl_bool isl_space_can_uncurry(__isl_keep isl_space *space)3195{3196	return isl_space_range_is_wrapping(space);3197}3198 3199/* Given a space A -> (B -> C), return the corresponding space3200 * (A -> B) -> C.3201 */3202__isl_give isl_space *isl_space_uncurry(__isl_take isl_space *space)3203{3204	isl_space *dom, *ran;3205	isl_space *ran_dom, *ran_ran;3206 3207	if (!space)3208		return NULL;3209 3210	if (!isl_space_can_uncurry(space))3211		isl_die(space->ctx, isl_error_invalid,3212			"space cannot be uncurried",3213			return isl_space_free(space));3214 3215	dom = isl_space_domain(isl_space_copy(space));3216	ran = isl_space_unwrap(isl_space_range(space));3217	ran_dom = isl_space_domain(isl_space_copy(ran));3218	ran_ran = isl_space_range(ran);3219	dom = isl_space_join(isl_space_from_domain(dom),3220			   isl_space_from_range(ran_dom));3221	return isl_space_join(isl_space_from_domain(isl_space_wrap(dom)),3222			    isl_space_from_range(ran_ran));3223}3224 3225isl_bool isl_space_has_named_params(__isl_keep isl_space *space)3226{3227	int i;3228	unsigned off;3229 3230	if (!space)3231		return isl_bool_error;3232	if (space->nparam == 0)3233		return isl_bool_true;3234	off = isl_space_offset(space, isl_dim_param);3235	if (off + space->nparam > space->n_id)3236		return isl_bool_false;3237	for (i = 0; i < space->nparam; ++i)3238		if (!space->ids[off + i])3239			return isl_bool_false;3240	return isl_bool_true;3241}3242 3243/* Check that "space" has only named parameters, reporting an error3244 * if it does not.3245 */3246isl_stat isl_space_check_named_params(__isl_keep isl_space *space)3247{3248	isl_bool named;3249 3250	named = isl_space_has_named_params(space);3251	if (named < 0)3252		return isl_stat_error;3253	if (!named)3254		isl_die(isl_space_get_ctx(space), isl_error_invalid,3255			"unexpected unnamed parameters", return isl_stat_error);3256 3257	return isl_stat_ok;3258}3259 3260/* Align the initial parameters of space1 to match the order in space2.3261 */3262__isl_give isl_space *isl_space_align_params(__isl_take isl_space *space1,3263	__isl_take isl_space *space2)3264{3265	isl_reordering *exp;3266 3267	if (isl_space_check_named_params(space1) < 0 ||3268	    isl_space_check_named_params(space2) < 0)3269		goto error;3270 3271	exp = isl_parameter_alignment_reordering(space1, space2);3272	isl_space_free(space1);3273	isl_space_free(space2);3274	space1 = isl_reordering_get_space(exp);3275	isl_reordering_free(exp);3276	return space1;3277error:3278	isl_space_free(space1);3279	isl_space_free(space2);3280	return NULL;3281}3282 3283/* Given the space of set (domain), construct a space for a map3284 * with as domain the given space and as range the range of "model".3285 */3286__isl_give isl_space *isl_space_extend_domain_with_range(3287	__isl_take isl_space *space, __isl_take isl_space *model)3288{3289	isl_size n_out;3290 3291	if (!model)3292		goto error;3293 3294	space = isl_space_from_domain(space);3295	n_out = isl_space_dim(model, isl_dim_out);3296	if (n_out < 0)3297		goto error;3298	space = isl_space_add_dims(space, isl_dim_out, n_out);3299	if (isl_space_has_tuple_id(model, isl_dim_out))3300		space = isl_space_set_tuple_id(space, isl_dim_out,3301				isl_space_get_tuple_id(model, isl_dim_out));3302	if (!space)3303		goto error;3304	if (model->nested[1]) {3305		isl_space *nested = isl_space_copy(model->nested[1]);3306		isl_size n_nested, n_space;3307		nested = isl_space_align_params(nested, isl_space_copy(space));3308		n_nested = isl_space_dim(nested, isl_dim_param);3309		n_space = isl_space_dim(space, isl_dim_param);3310		if (n_nested < 0 || n_space < 0)3311			goto error;3312		if (n_nested > n_space)3313			nested = isl_space_drop_dims(nested, isl_dim_param,3314						n_space, n_nested - n_space);3315		if (!nested)3316			goto error;3317		space->nested[1] = nested;3318	}3319	isl_space_free(model);3320	return space;3321error:3322	isl_space_free(model);3323	isl_space_free(space);3324	return NULL;3325}3326 3327/* Compare the "type" dimensions of two isl_spaces.3328 *3329 * The order is fairly arbitrary.3330 */3331static int isl_space_cmp_type(__isl_keep isl_space *space1,3332	__isl_keep isl_space *space2, enum isl_dim_type type)3333{3334	int cmp;3335	isl_size dim1, dim2;3336	isl_space *nested1, *nested2;3337 3338	dim1 = isl_space_dim(space1, type);3339	dim2 = isl_space_dim(space2, type);3340	if (dim1 < 0 || dim2 < 0)3341		return 0;3342	if (dim1 != dim2)3343		return dim1 - dim2;3344 3345	cmp = isl_id_cmp(tuple_id(space1, type), tuple_id(space2, type));3346	if (cmp != 0)3347		return cmp;3348 3349	nested1 = nested(space1, type);3350	nested2 = nested(space2, type);3351	if (!nested1 != !nested2)3352		return !nested1 - !nested2;3353 3354	if (nested1)3355		return isl_space_cmp(nested1, nested2);3356 3357	return 0;3358}3359 3360/* Compare two isl_spaces.3361 *3362 * The order is fairly arbitrary.3363 */3364int isl_space_cmp(__isl_keep isl_space *space1, __isl_keep isl_space *space2)3365{3366	int i;3367	int cmp;3368 3369	if (space1 == space2)3370		return 0;3371	if (!space1)3372		return -1;3373	if (!space2)3374		return 1;3375 3376	cmp = isl_space_cmp_type(space1, space2, isl_dim_param);3377	if (cmp != 0)3378		return cmp;3379	cmp = isl_space_cmp_type(space1, space2, isl_dim_in);3380	if (cmp != 0)3381		return cmp;3382	cmp = isl_space_cmp_type(space1, space2, isl_dim_out);3383	if (cmp != 0)3384		return cmp;3385 3386	if (!space1->ids && !space2->ids)3387		return 0;3388 3389	for (i = 0; i < n(space1, isl_dim_param); ++i) {3390		cmp = isl_id_cmp(get_id(space1, isl_dim_param, i),3391				 get_id(space2, isl_dim_param, i));3392		if (cmp != 0)3393			return cmp;3394	}3395 3396	return 0;3397}3398