1/*
2 * Copyright 2011      Sven Verdoolaege
3 * Copyright 2012-2014 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France
9 */
10
11#include <isl/id.h>
12#include <isl_space_private.h>
13#include <isl/set.h>
14#include <isl_reordering.h>
15
16#include <isl_multi_macro.h>
17
18#define MULTI_NAME(BASE) "isl_multi_" #BASE
19
20isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
21{
22	return multi ? isl_space_get_ctx(multi->space) : NULL;
23}
24
25/* Return the space of "multi".
26 */
27__isl_keep isl_space *FN(MULTI(BASE),peek_space)(__isl_keep MULTI(BASE) *multi)
28{
29	return multi ? multi->space : NULL;
30}
31
32__isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
33{
34	return isl_space_copy(FN(MULTI(BASE),peek_space)(multi));
35}
36
37__isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
38	__isl_keep MULTI(BASE) *multi)
39{
40	return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;
41}
42
43/* Allocate a multi expression living in "space".
44 *
45 * If the number of base expressions is zero, then make sure
46 * there is enough room in the structure for the explicit domain,
47 * in case the type supports such an explicit domain.
48 */
49__isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
50{
51	isl_ctx *ctx;
52	isl_size n;
53	MULTI(BASE) *multi;
54
55	n = isl_space_dim(space, isl_dim_out);
56	if (n < 0)
57		goto error;
58
59	ctx = isl_space_get_ctx(space);
60	if (n > 0)
61		multi = isl_calloc(ctx, MULTI(BASE),
62			 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
63	else
64		multi = isl_calloc(ctx, MULTI(BASE), sizeof(MULTI(BASE)));
65	if (!multi)
66		goto error;
67
68	multi->space = space;
69	multi->n = n;
70	multi->ref = 1;
71	if (FN(MULTI(BASE),has_explicit_domain)(multi))
72		multi = FN(MULTI(BASE),init_explicit_domain)(multi);
73	return multi;
74error:
75	isl_space_free(space);
76	return NULL;
77}
78
79__isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
80{
81	int i;
82	MULTI(BASE) *dup;
83
84	if (!multi)
85		return NULL;
86
87	dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
88	if (!dup)
89		return NULL;
90
91	for (i = 0; i < multi->n; ++i)
92		dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
93						    FN(EL,copy)(multi->u.p[i]));
94	if (FN(MULTI(BASE),has_explicit_domain)(multi))
95		dup = FN(MULTI(BASE),copy_explicit_domain)(dup, multi);
96
97	return dup;
98}
99
100__isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
101{
102	if (!multi)
103		return NULL;
104
105	if (multi->ref == 1)
106		return multi;
107
108	multi->ref--;
109	return FN(MULTI(BASE),dup)(multi);
110}
111
112__isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
113{
114	if (!multi)
115		return NULL;
116
117	multi->ref++;
118	return multi;
119}
120
121__isl_null MULTI(BASE) *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
122{
123	int i;
124
125	if (!multi)
126		return NULL;
127
128	if (--multi->ref > 0)
129		return NULL;
130
131	isl_space_free(multi->space);
132	for (i = 0; i < multi->n; ++i)
133		FN(EL,free)(multi->u.p[i]);
134	if (FN(MULTI(BASE),has_explicit_domain)(multi))
135		FN(MULTI(BASE),free_explicit_domain)(multi);
136	free(multi);
137
138	return NULL;
139}
140
141/* Return the space of "multi".
142 * The caller is not allowed to modify "multi" between this call
143 * and the call to *_restore_space because the number
144 * of references needs to stay the same.
145 * The only exception is that isl_multi_*_free can be called instead.
146 * No copy is taken of multi->space if "multi" has only one reference
147 * such that it can be modified inplace if both have only a single reference.
148 */
149__isl_give isl_space *FN(MULTI(BASE),take_space)(__isl_keep MULTI(BASE) *multi)
150{
151	isl_space *space;
152
153	if (!multi)
154		return NULL;
155	if (multi->ref != 1)
156		return FN(MULTI(BASE),get_space)(multi);
157	space = multi->space;
158	multi->space = NULL;
159	return space;
160}
161
162/* Set the space of "multi" to "space", where the space of "multi"
163 * may be missing due to a preceding call to isl_multi_*_take_space.
164 * However, in this case, "multi" only has a single reference and
165 * then the call to isl_multi_*_cow has no effect.
166 */
167__isl_give MULTI(BASE) *FN(MULTI(BASE),restore_space)(
168	__isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
169{
170	if (!multi || !space)
171		goto error;
172
173	if (multi->space == space) {
174		isl_space_free(space);
175		return multi;
176	}
177
178	multi = FN(MULTI(BASE),cow)(multi);
179	if (!multi)
180		goto error;
181	isl_space_free(multi->space);
182	multi->space = space;
183
184	return multi;
185error:
186	FN(MULTI(BASE),free)(multi);
187	isl_space_free(space);
188	return NULL;
189}
190
191isl_size FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
192	enum isl_dim_type type)
193{
194	return isl_space_dim(FN(MULTI(BASE),peek_space)(multi), type);
195}
196
197/* Return the number of base expressions in "multi".
198 */
199isl_size FN(MULTI(BASE),size)(__isl_keep MULTI(BASE) *multi)
200{
201	return multi ? multi->n : isl_size_error;
202}
203
204#undef TYPE
205#define TYPE	MULTI(BASE)
206static
207#include "check_type_range_templ.c"
208
209/* Return the base expression at position "pos" in "multi".
210 */
211static __isl_give EL *FN(MULTI(BASE),peek_at)(__isl_keep MULTI(BASE) *multi,
212	int pos)
213{
214	if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)
215		return NULL;
216	return multi->u.p[pos];
217}
218
219/* Return a copy of the base expression at position "pos" in "multi".
220 */
221__isl_give EL *FN(MULTI(BASE),get_at)(__isl_keep MULTI(BASE) *multi, int pos)
222{
223	return FN(EL,copy)(FN(MULTI(BASE),peek_at)(multi, pos));
224}
225
226/* This is an alternative name for the function above.
227 */
228__isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
229	int pos)
230{
231	return FN(MULTI(BASE),get_at)(multi, pos);
232}
233
234/* Return the base expression at position "pos" in "multi".
235 * This may be either a copy or the base expression itself
236 * if there is only one reference to "multi".
237 * This allows the base expression to be modified inplace
238 * if both the multi expression and this base expression
239 * have only a single reference.
240 * The caller is not allowed to modify "multi" between this call and
241 * the subsequent call to isl_multi_*_restore_at_*.
242 * The only exception is that isl_multi_*_free can be called instead.
243 */
244static __isl_give EL *FN(MULTI(BASE),take_at)(__isl_keep MULTI(BASE) *multi,
245	int pos)
246{
247	EL *el;
248
249	if (!multi)
250		return NULL;
251	if (multi->ref != 1)
252		return FN(MULTI(BASE),get_at)(multi, pos);
253	if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0)
254		return NULL;
255	el = multi->u.p[pos];
256	multi->u.p[pos] = NULL;
257	return el;
258}
259
260/* Set the element at position "pos" of "multi" to "el",
261 * where the position may be empty if "multi" has only a single reference.
262 */
263static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_at)(
264	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
265{
266	if (FN(MULTI(BASE),check_range)(multi, isl_dim_out, pos, 1) < 0 || !el)
267		goto error;
268
269	if (multi->u.p[pos] == el) {
270		FN(EL,free)(el);
271		return multi;
272	}
273
274	multi = FN(MULTI(BASE),cow)(multi);
275	if (!multi)
276		goto error;
277
278	FN(EL,free)(multi->u.p[pos]);
279	multi->u.p[pos] = el;
280
281	return multi;
282error:
283	FN(MULTI(BASE),free)(multi);
284	FN(EL,free)(el);
285	return NULL;
286}
287
288/* Set the element at position "pos" of "multi" to "el",
289 * where the position may be empty if "multi" has only a single reference.
290 * However, the space of "multi" is available and is checked
291 * for compatibility with "el".
292 */
293static __isl_give MULTI(BASE) *FN(MULTI(BASE),restore_check_space)(
294	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
295{
296	isl_space *space;
297
298	space = FN(MULTI(BASE),peek_space)(multi);
299	if (FN(EL,check_match_domain_space)(el, space) < 0)
300		multi = FN(MULTI(BASE),free)(multi);
301	return FN(MULTI(BASE),restore_at)(multi, pos, el);
302}
303
304/* Replace the base expression at position "pos" in "multi" with "el".
305 */
306__isl_give MULTI(BASE) *FN(MULTI(BASE),set_at)(
307	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
308{
309	isl_space *multi_space = NULL;
310	isl_space *el_space = NULL;
311	isl_bool match;
312
313	multi_space = FN(MULTI(BASE),get_space)(multi);
314	match = FN(EL,matching_params)(el, multi_space);
315	if (match < 0)
316		goto error;
317	if (!match) {
318		multi = FN(MULTI(BASE),align_params)(multi,
319						    FN(EL,get_space)(el));
320		isl_space_free(multi_space);
321		multi_space = FN(MULTI(BASE),get_space)(multi);
322		el = FN(EL,align_params)(el, isl_space_copy(multi_space));
323	}
324
325	multi = FN(MULTI(BASE),restore_check_space)(multi, pos, el);
326
327	isl_space_free(multi_space);
328	isl_space_free(el_space);
329
330	return multi;
331error:
332	FN(MULTI(BASE),free)(multi);
333	FN(EL,free)(el);
334	isl_space_free(multi_space);
335	isl_space_free(el_space);
336	return NULL;
337}
338
339/* This is an alternative name for the function above.
340 */
341__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
342	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
343{
344	return FN(MULTI(BASE),set_at)(multi, pos, el);
345}
346
347/* Return the base expressions of "multi" as a list.
348 */
349__isl_give LIST(EL) *FN(MULTI(BASE),get_list)(
350	__isl_keep MULTI(BASE) *multi)
351{
352	isl_size n;
353	int i;
354	LIST(EL) *list;
355
356	n = FN(MULTI(BASE),size)(multi);
357	if (n < 0)
358		return NULL;
359	list = FN(LIST(EL),alloc)(FN(MULTI(BASE),get_ctx(multi)), n);
360	for (i = 0; i < n; ++i) {
361		EL *el = FN(MULTI(BASE),get_at)(multi, i);
362		list = FN(LIST(EL),add)(list, el);
363	}
364
365	return list;
366}
367
368/* Reset the space of "multi".  This function is called from isl_pw_templ.c
369 * and doesn't know if the space of an element object is represented
370 * directly or through its domain.  It therefore passes along both,
371 * which we pass along to the element function since we don't know how
372 * that is represented either.
373 *
374 * If "multi" has an explicit domain, then the caller is expected
375 * to make sure that any modification that would change the dimensions
376 * of the explicit domain has bee applied before this function is called.
377 */
378__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
379	__isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
380	__isl_take isl_space *domain)
381{
382	isl_size n;
383	int i;
384
385	n = FN(MULTI(BASE),size)(multi);
386	if (n < 0 || !space || !domain)
387		goto error;
388
389	for (i = 0; i < n; ++i) {
390		EL *el;
391
392		el = FN(MULTI(BASE),take_at)(multi, i);
393		el = FN(EL,reset_domain_space)(el, isl_space_copy(domain));
394		multi = FN(MULTI(BASE),restore_at)(multi, i, el);
395	}
396	if (FN(MULTI(BASE),has_explicit_domain)(multi))
397		multi = FN(MULTI(BASE),reset_explicit_domain_space)(multi,
398							isl_space_copy(domain));
399	isl_space_free(domain);
400
401	multi = FN(MULTI(BASE),restore_space)(multi, space);
402
403	return multi;
404error:
405	isl_space_free(domain);
406	isl_space_free(space);
407	FN(MULTI(BASE),free)(multi);
408	return NULL;
409}
410
411__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
412	__isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
413{
414	isl_space *space, *multi_space;
415
416	multi_space = FN(MULTI(BASE),get_space)(multi);
417	space = isl_space_extend_domain_with_range(isl_space_copy(domain),
418						multi_space);
419	return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
420}
421
422__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
423	__isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
424{
425	isl_space *domain;
426
427	domain = isl_space_domain(isl_space_copy(space));
428	return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
429}
430
431/* Reset the user pointer on all identifiers of parameters and tuples
432 * of the space of "multi".
433 */
434__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_user)(
435	__isl_take MULTI(BASE) *multi)
436{
437	isl_space *space;
438
439	space = FN(MULTI(BASE),get_space)(multi);
440	space = isl_space_reset_user(space);
441
442	return FN(MULTI(BASE),reset_space)(multi, space);
443}
444
445__isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
446	__isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
447{
448	int i;
449	isl_size n;
450	isl_space *space;
451
452	n = FN(MULTI(BASE),size)(multi);
453	if (n < 0 || !exp)
454		goto error;
455
456	for (i = 0; i < n; ++i) {
457		EL *el;
458
459		el = FN(MULTI(BASE),take_at)(multi, i);
460		el = FN(EL,realign_domain)(el, isl_reordering_copy(exp));
461		multi = FN(MULTI(BASE),restore_at)(multi, i, el);
462	}
463
464	space = isl_reordering_get_space(exp);
465	multi = FN(MULTI(BASE),reset_domain_space)(multi, space);
466
467	isl_reordering_free(exp);
468	return multi;
469error:
470	isl_reordering_free(exp);
471	FN(MULTI(BASE),free)(multi);
472	return NULL;
473}
474
475/* Align the parameters of "multi" to those of "model".
476 *
477 * If "multi" has an explicit domain, then align the parameters
478 * of the domain first.
479 */
480__isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
481	__isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
482{
483	isl_ctx *ctx;
484	isl_bool equal_params;
485	isl_space *domain_space;
486	isl_reordering *exp;
487
488	if (!multi || !model)
489		goto error;
490
491	equal_params = isl_space_has_equal_params(multi->space, model);
492	if (equal_params < 0)
493		goto error;
494	if (equal_params) {
495		isl_space_free(model);
496		return multi;
497	}
498
499	ctx = isl_space_get_ctx(model);
500	if (!isl_space_has_named_params(model))
501		isl_die(ctx, isl_error_invalid,
502			"model has unnamed parameters", goto error);
503	if (!isl_space_has_named_params(multi->space))
504		isl_die(ctx, isl_error_invalid,
505			"input has unnamed parameters", goto error);
506
507	if (FN(MULTI(BASE),has_explicit_domain)(multi)) {
508		multi = FN(MULTI(BASE),align_explicit_domain_params)(multi,
509							isl_space_copy(model));
510		if (!multi)
511			goto error;
512	}
513	domain_space = FN(MULTI(BASE),get_domain_space)(multi);
514	exp = isl_parameter_alignment_reordering(domain_space, model);
515	isl_space_free(domain_space);
516	multi = FN(MULTI(BASE),realign_domain)(multi, exp);
517
518	isl_space_free(model);
519	return multi;
520error:
521	isl_space_free(model);
522	FN(MULTI(BASE),free)(multi);
523	return NULL;
524}
525
526/* Create a multi expression in the given space with the elements of "list"
527 * as base expressions.
528 *
529 * Since isl_multi_*_restore_* assumes that the element and
530 * the multi expression have matching spaces, the alignment
531 * (if any) needs to be performed beforehand.
532 */
533__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
534	__isl_take isl_space *space, __isl_take LIST(EL) *list)
535{
536	int i;
537	isl_size n, dim;
538	isl_ctx *ctx;
539	MULTI(BASE) *multi;
540
541	dim = isl_space_dim(space, isl_dim_out);
542	n = FN(FN(LIST(EL),n),BASE)(list);
543	if (dim < 0 || n < 0)
544		goto error;
545
546	ctx = isl_space_get_ctx(space);
547	if (n != dim)
548		isl_die(ctx, isl_error_invalid,
549			"invalid number of elements in list", goto error);
550
551	for (i = 0; i < n; ++i) {
552		EL *el = FN(LIST(EL),peek)(list, i);
553		space = isl_space_align_params(space, FN(EL,get_space)(el));
554	}
555	multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
556	for (i = 0; i < n; ++i) {
557		EL *el = FN(FN(LIST(EL),get),BASE)(list, i);
558		el = FN(EL,align_params)(el, isl_space_copy(space));
559		multi = FN(MULTI(BASE),restore_check_space)(multi, i, el);
560	}
561
562	isl_space_free(space);
563	FN(LIST(EL),free)(list);
564	return multi;
565error:
566	isl_space_free(space);
567	FN(LIST(EL),free)(list);
568	return NULL;
569}
570
571/* This function performs the same operation as isl_multi_*_from_*_list,
572 * but is considered as a function on an isl_space when exported.
573 */
574__isl_give MULTI(BASE) *FN(isl_space_multi,BASE)(__isl_take isl_space *space,
575	__isl_take LIST(EL) *list)
576{
577	return FN(FN(MULTI(BASE),from),LIST(BASE))(space, list);
578}
579
580/* Drop the "n" output dimensions of "multi" starting at "first",
581 * where the space is assumed to have been adjusted already.
582 */
583static __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_output_dims)(
584	__isl_take MULTI(BASE) *multi, unsigned first, unsigned n)
585{
586	int i;
587
588	multi = FN(MULTI(BASE),cow)(multi);
589	if (!multi)
590		return NULL;
591
592	for (i = 0; i < n; ++i)
593		FN(EL,free)(multi->u.p[first + i]);
594	for (i = first; i + n < multi->n; ++i)
595		multi->u.p[i] = multi->u.p[i + n];
596	multi->n -= n;
597	if (n > 0 && FN(MULTI(BASE),has_explicit_domain)(multi))
598		multi = FN(MULTI(BASE),init_explicit_domain)(multi);
599
600	return multi;
601}
602
603__isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
604	__isl_take MULTI(BASE) *multi,
605	enum isl_dim_type type, unsigned first, unsigned n)
606{
607	isl_space *space;
608	isl_size size;
609	int i;
610
611	if (FN(MULTI(BASE),check_range)(multi, type, first, n) < 0)
612		return FN(MULTI(BASE),free)(multi);
613
614	space = FN(MULTI(BASE),take_space)(multi);
615	space = isl_space_drop_dims(space, type, first, n);
616	multi = FN(MULTI(BASE),restore_space)(multi, space);
617
618	if (type == isl_dim_out)
619		return FN(MULTI(BASE),drop_output_dims)(multi, first, n);
620
621	if (FN(MULTI(BASE),has_explicit_domain)(multi))
622		multi = FN(MULTI(BASE),drop_explicit_domain_dims)(multi,
623								type, first, n);
624
625	size = FN(MULTI(BASE),size)(multi);
626	if (size < 0)
627		return FN(MULTI(BASE),free)(multi);
628	for (i = 0; i < size; ++i) {
629		EL *el;
630
631		el = FN(MULTI(BASE),take_at)(multi, i);
632		el = FN(EL,drop_dims)(el, type, first, n);
633		multi = FN(MULTI(BASE),restore_at)(multi, i, el);
634	}
635
636	return multi;
637}
638
639#undef TYPE
640#define TYPE MULTI(BASE)
641
642#include "isl_check_named_params_templ.c"
643static
644#include "isl_align_params_bin_templ.c"
645
646/* Given two MULTI(BASE)s A -> B and C -> D,
647 * construct a MULTI(BASE) (A * C) -> [B -> D].
648 *
649 * If "multi1" and/or "multi2" has an explicit domain, then
650 * intersect the domain of the result with these explicit domains.
651 */
652__isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
653	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
654{
655	int i;
656	isl_size n1, n2;
657	EL *el;
658	isl_space *space;
659	MULTI(BASE) *res;
660
661	FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
662	n1 = FN(MULTI(BASE),size)(multi1);
663	n2 = FN(MULTI(BASE),size)(multi2);
664	if (n1 < 0 || n2 < 0)
665		goto error;
666
667	space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
668					FN(MULTI(BASE),get_space)(multi2));
669	res = FN(MULTI(BASE),alloc)(space);
670
671	for (i = 0; i < n1; ++i) {
672		el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
673		res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
674	}
675
676	for (i = 0; i < n2; ++i) {
677		el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
678		res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
679	}
680
681	if (FN(MULTI(BASE),has_explicit_domain)(multi1))
682		res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi1);
683	if (FN(MULTI(BASE),has_explicit_domain)(multi2))
684		res = FN(MULTI(BASE),intersect_explicit_domain)(res, multi2);
685
686	FN(MULTI(BASE),free)(multi1);
687	FN(MULTI(BASE),free)(multi2);
688	return res;
689error:
690	FN(MULTI(BASE),free)(multi1);
691	FN(MULTI(BASE),free)(multi2);
692	return NULL;
693}
694
695/* Is the range of "multi" a wrapped relation?
696 */
697isl_bool FN(MULTI(BASE),range_is_wrapping)(__isl_keep MULTI(BASE) *multi)
698{
699	if (!multi)
700		return isl_bool_error;
701	return isl_space_range_is_wrapping(multi->space);
702}
703
704/* Given a function A -> [B -> C], extract the function A -> B.
705 */
706__isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_domain)(
707	__isl_take MULTI(BASE) *multi)
708{
709	isl_space *space;
710	isl_size total, keep;
711
712	total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
713	if (total < 0)
714		return FN(MULTI(BASE),free)(multi);
715	if (!isl_space_range_is_wrapping(multi->space))
716		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
717			"range is not a product",
718			return FN(MULTI(BASE),free)(multi));
719
720	space = FN(MULTI(BASE),get_space)(multi);
721	space = isl_space_range_factor_domain(space);
722	keep = isl_space_dim(space, isl_dim_out);
723	if (keep < 0)
724		multi = FN(MULTI(BASE),free)(multi);
725	multi = FN(MULTI(BASE),drop_dims)(multi,
726					isl_dim_out, keep, total - keep);
727	multi = FN(MULTI(BASE),reset_space)(multi, space);
728
729	return multi;
730}
731
732/* Given a function A -> [B -> C], extract the function A -> C.
733 */
734__isl_give MULTI(BASE) *FN(MULTI(BASE),range_factor_range)(
735	__isl_take MULTI(BASE) *multi)
736{
737	isl_space *space;
738	isl_size total, keep;
739
740	total = FN(MULTI(BASE),dim)(multi, isl_dim_out);
741	if (total < 0)
742		return FN(MULTI(BASE),free)(multi);
743	if (!isl_space_range_is_wrapping(multi->space))
744		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
745			"range is not a product",
746			return FN(MULTI(BASE),free)(multi));
747
748	space = FN(MULTI(BASE),get_space)(multi);
749	space = isl_space_range_factor_range(space);
750	keep = isl_space_dim(space, isl_dim_out);
751	if (keep < 0)
752		multi = FN(MULTI(BASE),free)(multi);
753	multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_out, 0, total - keep);
754	multi = FN(MULTI(BASE),reset_space)(multi, space);
755
756	return multi;
757}
758
759/* Given a function [B -> C], extract the function C.
760 */
761__isl_give MULTI(BASE) *FN(MULTI(BASE),factor_range)(
762	__isl_take MULTI(BASE) *multi)
763{
764	isl_space *space;
765	isl_size total, keep;
766
767	total = FN(MULTI(BASE),dim)(multi, isl_dim_set);
768	if (total < 0)
769		return FN(MULTI(BASE),free)(multi);
770	if (!isl_space_is_wrapping(multi->space))
771		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
772			"not a product", return FN(MULTI(BASE),free)(multi));
773
774	space = FN(MULTI(BASE),get_space)(multi);
775	space = isl_space_factor_range(space);
776	keep = isl_space_dim(space, isl_dim_set);
777	if (keep < 0)
778		multi = FN(MULTI(BASE),free)(multi);
779	multi = FN(MULTI(BASE),drop_dims)(multi, isl_dim_set, 0, total - keep);
780	multi = FN(MULTI(BASE),reset_space)(multi, space);
781
782	return multi;
783}
784
785__isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
786	__isl_take MULTI(BASE) *multi)
787{
788	isl_space *space;
789
790	space = FN(MULTI(BASE),take_space)(multi);
791	space = isl_space_flatten_range(space);
792	multi = FN(MULTI(BASE),restore_space)(multi, space);
793
794	return multi;
795}
796
797/* Given two MULTI(BASE)s A -> B and C -> D,
798 * construct a MULTI(BASE) (A * C) -> (B, D).
799 */
800__isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
801	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
802{
803	MULTI(BASE) *multi;
804
805	multi = FN(MULTI(BASE),range_product)(multi1, multi2);
806	multi = FN(MULTI(BASE),flatten_range)(multi);
807	return multi;
808}
809
810/* Given two multi expressions, "multi1"
811 *
812 *	[A] -> [B1 B2]
813 *
814 * where B2 starts at position "pos", and "multi2"
815 *
816 *	[A] -> [D]
817 *
818 * return the multi expression
819 *
820 *	[A] -> [B1 D B2]
821 */
822__isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
823	__isl_take MULTI(BASE) *multi1, unsigned pos,
824	__isl_take MULTI(BASE) *multi2)
825{
826	MULTI(BASE) *res;
827	isl_size dim;
828
829	dim = FN(MULTI(BASE),size)(multi1);
830	if (dim < 0 || !multi2)
831		goto error;
832
833	if (FN(MULTI(BASE),check_range)(multi1, isl_dim_out, pos, 0) < 0)
834		goto error;
835
836	res = FN(MULTI(BASE),copy)(multi1);
837	res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
838	multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
839
840	res = FN(MULTI(BASE),flat_range_product)(res, multi2);
841	res = FN(MULTI(BASE),flat_range_product)(res, multi1);
842
843	return res;
844error:
845	FN(MULTI(BASE),free)(multi1);
846	FN(MULTI(BASE),free)(multi2);
847	return NULL;
848}
849
850#undef TYPE
851#define TYPE	MULTI(BASE)
852
853static
854#include "isl_type_has_equal_space_bin_templ.c"
855static
856#include "isl_type_check_equal_space_templ.c"
857
858/* This function is currently only used from isl_aff.c
859 */
860static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
861	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
862	__isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
863	__attribute__ ((unused));
864
865/* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
866 * return the result.
867 *
868 * If "multi2" has an explicit domain, then
869 * intersect the domain of the result with this explicit domain.
870 */
871static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
872	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
873	__isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
874{
875	isl_size n;
876	int i;
877
878	FN(MULTI(BASE),align_params_bin)(&multi1, &multi2);
879	n = FN(MULTI(BASE),size)(multi1);
880	if (n < 0 || FN(MULTI(BASE),check_equal_space)(multi1, multi2) < 0)
881		goto error;
882
883	for (i = 0; i < n; ++i) {
884		EL *el1, *el2;
885
886		el2 = FN(MULTI(BASE),get_at)(multi2, i);
887		el1 = FN(MULTI(BASE),take_at)(multi1, i);
888		el1 = fn(el1, el2);
889		multi1 = FN(MULTI(BASE),restore_at)(multi1, i, el1);
890	}
891
892	if (FN(MULTI(BASE),has_explicit_domain)(multi2))
893		multi1 = FN(MULTI(BASE),intersect_explicit_domain)(multi1,
894								    multi2);
895
896	FN(MULTI(BASE),free)(multi2);
897	return multi1;
898error:
899	FN(MULTI(BASE),free)(multi1);
900	FN(MULTI(BASE),free)(multi2);
901	return NULL;
902}
903
904/* Only used on some multi-expressions.
905 */
906static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
907	isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
908
909/* Does "test" succeed on any base expression of "multi"?
910 */
911static isl_bool FN(MULTI(BASE),any)(__isl_keep MULTI(BASE) *multi,
912	isl_bool (*test)(__isl_keep EL *))
913{
914	isl_size n;
915	int i;
916
917	n = FN(MULTI(BASE),size)(multi);
918	if (n < 0)
919		return isl_bool_error;
920
921	for (i = 0; i < n; ++i) {
922		isl_bool any = test(multi->u.p[i]);
923		if (any < 0 || any)
924			return any;
925	}
926
927	return isl_bool_false;
928}
929
930/* Only used on some multi-expressions.
931 */
932static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
933	isl_bool (*test)(__isl_keep EL *)) __attribute__ ((unused));
934
935/* Does "test" succeed on every base expression of "multi"?
936 */
937static isl_bool FN(MULTI(BASE),every)(__isl_keep MULTI(BASE) *multi,
938	isl_bool (*test)(__isl_keep EL *))
939{
940	isl_size n;
941	int i;
942
943	n = FN(MULTI(BASE),size)(multi);
944	if (n < 0)
945		return isl_bool_error;
946
947	for (i = 0; i < n; ++i) {
948		isl_bool every = test(multi->u.p[i]);
949		if (every < 0 || !every)
950			return every;
951	}
952
953	return isl_bool_true;
954}
955
956#undef TYPE
957#define TYPE MULTI(BASE)
958#include "isl_from_range_templ.c"
959
960/* Are "multi1" and "multi2" obviously equal?
961 */
962isl_bool FN(MULTI(BASE),plain_is_equal)(__isl_keep MULTI(BASE) *multi1,
963	__isl_keep MULTI(BASE) *multi2)
964{
965	int i;
966	isl_bool equal;
967
968	if (!multi1 || !multi2)
969		return isl_bool_error;
970	if (multi1->n != multi2->n)
971		return isl_bool_false;
972	equal = isl_space_is_equal(multi1->space, multi2->space);
973	if (equal < 0 || !equal)
974		return equal;
975
976	for (i = 0; i < multi1->n; ++i) {
977		equal = FN(EL,plain_is_equal)(multi1->u.p[i], multi2->u.p[i]);
978		if (equal < 0 || !equal)
979			return equal;
980	}
981
982	if (FN(MULTI(BASE),has_explicit_domain)(multi1) ||
983	    FN(MULTI(BASE),has_explicit_domain)(multi2)) {
984		equal = FN(MULTI(BASE),equal_explicit_domain)(multi1, multi2);
985		if (equal < 0 || !equal)
986			return equal;
987	}
988
989	return isl_bool_true;
990}
991