1	/*
2	* Copyright 2020 Cerebras Systems. All rights reserved.
3	*
4	* Redistribution and use in source and binary forms, with or without
5	* modification, are permitted provided that the following conditions
6	* are met:
7	*
8	* 1. Redistributions of source code must retain the above copyright
9	* notice, this list of conditions and the following disclaimer.
10	*
11	* 2. Redistributions in binary form must reproduce the above
12	* copyright notice, this list of conditions and the following
13	* disclaimer in the documentation and/or other materials provided
14	* with the distribution.
15	*
16	* THIS SOFTWARE IS PROVIDED BY CEREBRAS SYSTEMS ''AS IS'' AND ANY
17	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CEREBRAS SYSTEMS OR
20	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
23	* OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*
28	* The views and conclusions contained in the software and documentation
29	* are those of the authors and should not be interpreted as
30	* representing official policies, either expressed or implied, of
31	* Cerebras Systems.
32	*/
33
34	#include <ctype.h>
35
36	#include <algorithm>
37	#include <iostream>
38	#include <set>
39	#include <sstream>
40	#include <string>
41	#include <unordered_map>
42	#include <unordered_set>
43
44	#include "template_cpp.h"
45	#include "isl_config.h"
46
47	/* The textual representation of this tuple kind.
48	*
49	* By default, the textual representation is just the name.
50	*/
51	std::string TupleKind::to_string() const
52	{
53	return name;
54	}
55
56	/* Return the parameters of this tuple kind.
57	*
58	* By default, there are no parameters.
59	*/
60	std::vector<std::string> TupleKind::params() const
61	{
62	return { };
63	}
64
65	/* Apply the substitution "subs" to this tuple kind and return the result.
66	* "self" is a shared pointer to this.
67	*
68	* If the name of this tuple kind appears in the substitution,
69	* then return the corresponding tuple kind pointer.
70	* Otherwise, return "self".
71	*/
72	TupleKindPtr TupleKind::apply(const Substitution &subs,
73	const TupleKindPtr &self) const
74	{
75	if (subs.count(x: name) != 0)
76	return subs.at(k: name);
77	return self;
78	}
79
80	/* Apply the substitution "subs" to "tuple" and return the result.
81	*/
82	static TupleKindPtr apply(const TupleKindPtr tuple, const Substitution &subs)
83	{
84	return tuple->apply(subs, self: tuple);
85	}
86
87	/* Return the left child of this tuple kind.
88	*
89	* Since this is not a pair, there is no left child.
90	*/
91	TupleKindPtr TupleKind::left() const
92	{
93	return TupleKindPtr();
94	}
95
96	/* Return the right child of this tuple kind.
97	*
98	* Since this is not a pair, there is no right child.
99	*/
100	TupleKindPtr TupleKind::right() const
101	{
102	return TupleKindPtr();
103	}
104
105	/* Helper class used to construct a pointer to a tuple kind
106	* that refers to a non-template type.
107	*/
108	struct Fixed {
109	};
110
111	/* Construct a pointer to a tuple kind that refers to a non-template type.
112	*
113	* Use an empty string as name. Since this is a non-template type,
114	* the kind name will never appear in the generated code.
115	*/
116	TupleKindPtr::TupleKindPtr(Fixed) : Base(std::make_shared<TupleKind>(args: ""))
117	{
118	}
119
120	/* Tuple pointers for non-template types.
121	*/
122	static TupleKindPtr Ctx{Fixed()};
123	static TupleKindPtr Integer{Fixed()};
124	static TupleKindPtr Str{Fixed()};
125	static TupleKindPtr Res{Fixed()};
126
127	/* Special tuple pointers.
128	* Anonymous appears in the generated code but cannot be unified
129	* with anything else since it is a predefined template argument.
130	* Leaf can only be unified with something that is not a pair and
131	* does not appear in the generated code.
132	*/
133	static TupleKindPtr Anonymous("Anonymous");
134	static TupleKindPtr Leaf("Leaf");
135
136	/* Placeholder tuple pointers that refer to (part of) the domain or range.
137	*/
138	static TupleKindPtr Domain("Domain");
139	static TupleKindPtr Domain2("Domain2");
140	static TupleKindPtr Domain3("Domain3");
141	static TupleKindPtr Range("Range");
142	static TupleKindPtr Range2("Range2");
143	static TupleKindPtr Range3("Range3");
144
145	/* A representation of a proper tuple kind that is used as a template
146	* parameter or a template argument.
147	*/
148	struct ProperTupleKind : public TupleKind {
149	ProperTupleKind(const std::string &name) : TupleKind(name) {}
150
151	virtual std::vector<std::string> params() const override;
152	};
153
154	/* Return the parameters of this tuple kind.
155	*
156	* Return the name of this tuple kind, unless it is the special Anonymous
157	* predefined template argument.
158	*/
159	std::vector<std::string> ProperTupleKind::params() const
160	{
161	if (Anonymous.get() == this)
162	return { };
163	return { name };
164	}
165
166	/* Construct a pointer to a tuple kind that refers
167	* to a proper tuple kind with the given name.
168	*/
169	TupleKindPtr::TupleKindPtr(const std::string &name) :
170	Base(std::make_shared<ProperTupleKind>(args: name))
171	{
172	}
173
174	/* A tuple kind that represents an anonymous pair of nested tuple kinds.
175	*/
176	struct Pair : public TupleKind {
177	Pair(const TupleKindPtr &tuple1, const TupleKindPtr &tuple2) :
178	TupleKind(""), tuple1(tuple1), tuple2(tuple2) {}
179
180	virtual std::string to_string() const override;
181	virtual std::vector<std::string> params() const override;
182	virtual TupleKindPtr apply(const Substitution &match,
183	const TupleKindPtr &self) const override;
184	virtual TupleKindPtr left() const override;
185	virtual TupleKindPtr right() const override;
186
187	const TupleKindPtr tuple1;
188	const TupleKindPtr tuple2;
189	};
190
191	/* The textual representation of this tuple kind.
192	*
193	* The textual representation of a pair is of the form "pair<tuple1, tuple2>".
194	*/
195	std::string Pair::to_string() const
196	{
197	return std::string("pair<") + tuple1->to_string() + ", " +
198	tuple2->to_string() + ">";
199	}
200
201	/* Add the elements of "vec2" that do not already appear in "vec1"
202	* at the end of "vec1".
203	*
204	* The two vectors are assumed not to have any repeated elements.
205	* The updated vector will then also not have repeated elements.
206	*/
207	static void combine(std::vector<std::string> &vec1,
208	const std::vector<std::string> &vec2)
209	{
210	for (const auto &s : vec2)
211	if (std::find(first: vec1.begin(), last: vec1.end(), val: s) == vec1.end())
212	vec1.emplace_back(args: s);
213	}
214
215	/* Return the parameters of this tuple kind.
216	*
217	* Combine the parameters of the two nested tuple kinds.
218	*/
219	std::vector<std::string> Pair::params() const
220	{
221	auto names1 = tuple1->params();
222	auto names2 = tuple2->params();
223
224	combine(vec1&: names1, vec2: names2);
225
226	return names1;
227	}
228
229	/* Apply the substitution "subs" to this tuple kind and return the result.
230	* "self" is a shared pointer to this.
231	*
232	* Construct a new tuple kind consisting of the result of applying
233	* the substitution to the two nested tuple kinds.
234	*/
235	TupleKindPtr Pair::apply(const Substitution &subs, const TupleKindPtr &self)
236	const
237	{
238	return TupleKindPtr(::apply(tuple: tuple1, subs), ::apply(tuple: tuple2, subs));
239	}
240
241	/* Return the left child of this tuple kind.
242	*/
243	TupleKindPtr Pair::left() const
244	{
245	return tuple1;
246	}
247
248	/* Return the right child of this tuple kind.
249	*/
250	TupleKindPtr Pair::right() const
251	{
252	return tuple2;
253	}
254
255	/* Construct a pointer to a tuple kind that refers
256	* to the given pair of nested tuple kinds.
257	*/
258	TupleKindPtr::TupleKindPtr(const TupleKindPtr &left, const TupleKindPtr &right)
259	: Base(std::make_shared<Pair>(args: left, args: right))
260	{
261	}
262
263	/* Is this a kind of object representing an anonymous function?
264	*/
265	bool Kind::is_anon() const
266	{
267	return size() != 0 && back() == Anonymous;
268	}
269
270	/* Is this a kind of object with a single tuple?
271	*/
272	bool Kind::is_set() const
273	{
274	return size() == 1;
275	}
276
277	/* Is this a kind of object with a single, anonymous tuple?
278	*/
279	bool Kind::is_anon_set() const
280	{
281	return is_set() && is_anon();
282	}
283
284	/* Return the parameters of this kind.
285	*
286	* Collect the parameters of the tuple kinds in the sequence.
287	*/
288	std::vector<std::string> Kind::params() const
289	{
290	std::vector<std::string> params;
291
292	for (const auto &tuple : *this)
293	combine(vec1&: params, vec2: tuple->params());
294
295	return params;
296	}
297
298	/* Apply the substitution "subs" to this kind and return the result.
299	*
300	* Apply the substitution to each of the tuple kinds in the sequence.
301	*/
302	Kind Kind::apply(const Substitution &subs) const
303	{
304	Kind applied;
305
306	for (const auto &tuple : *this)
307	applied.emplace_back(args: ::apply(tuple, subs));
308
309	return applied;
310	}
311
312	/* A signature of a method in terms of kinds,
313	* consisting of a return kind and a sequence of argument kinds.
314	*/
315	struct Signature {
316	Kind ret;
317	std::vector<Kind> args;
318
319	std::vector<std::string> params() const;
320	Signature apply(const Substitution &match) const;
321	};
322
323	/* Return the parameters of this signature.
324	*
325	* Collect the parameters of the argument kinds and the return kind.
326	*/
327	std::vector<std::string> Signature::params() const
328	{
329	std::vector<std::string> params;
330
331	for (const auto &arg : args)
332	combine(vec1&: params, vec2: arg.params());
333	combine(vec1&: params, vec2: ret.params());
334
335	return params;
336	}
337
338	/* Apply the substitution "subs" to this kind and return the result.
339	*
340	* Apply the substitution to the argument kinds and the return kind.
341	*/
342	Signature Signature::apply(const Substitution &subs) const
343	{
344	std::vector<Kind> applied_args;
345
346	for (const auto &arg : args)
347	applied_args.emplace_back(args: arg.apply(subs));
348
349	return { .ret: ret.apply(subs), .args: applied_args };
350	}
351
352	/* Return a renaming substitution that renames the elements of "params"
353	* using names starting with "prefix".
354	*/
355	static Substitution param_renamer(const std::vector<std::string> &params,
356	const std::string &prefix)
357	{
358	Substitution renamer;
359	int n = 0;
360
361	for (const auto &name : params) {
362	auto suffix = std::to_string(val: ++n);
363	auto arg_name = prefix + suffix;
364	auto arg = TupleKindPtr(arg_name);
365
366	if (name == Leaf->name)
367	generator::die(msg: "Leaf cannot be renamed");
368
369	renamer.emplace(args: name, args&: arg);
370	}
371
372	return renamer;
373	}
374
375	/* Does the vector "v" contain the element "el"?
376	*/
377	static bool contains(const std::vector<std::string> &v, const std::string &el)
378	{
379	return find(first: v.begin(), last: v.end(), val: el) != v.end();
380	}
381
382
383	/* Return the shared elements of "v1" and "v2", preserving the order
384	* of those elements in "v1".
385	*/
386	static std::vector<std::string> intersect(const std::vector<std::string> &v1,
387	const std::vector<std::string> &v2)
388	{
389	std::vector<std::string> intersection;
390
391	for (const auto &el : v1)
392	if (contains(v: v2, el))
393	intersection.push_back(x: el);
394
395	return intersection;
396	}
397
398	/* Return a renaming substitution that renames
399	* any parameters that appears in both "sig" and "kind".
400	*/
401	static Substitution shared_param_renamer(const Signature &sig, const Kind &kind)
402	{
403	return param_renamer(params: intersect(v1: sig.params(), v2: kind.params()), prefix: "Arg");
404	}
405
406	/* Signatures for unary operations.
407	* Functions have at least one tuple.
408	*/
409	static Signature un_params = { .ret: { }, .args: { { } } };
410	static Signature un_set = { .ret: { Domain }, .args: { { Domain } } };
411	static Signature un_map = { .ret: { Domain, Range }, .args: { { Domain, Range } } };
412	static std::vector<Signature> un_op = { un_params, un_set, un_map };
413	static std::vector<Signature> fn_un_op = { un_set, un_map };
414
415	/* Signatures for binary operations, with the second argument
416	* possibly referring to part of the first argument.
417	* Functions have at least one tuple.
418	*/
419	static Signature bin_params = { .ret: { }, .args: { { }, { } } };
420	static Signature bin_set = { .ret: { Domain }, .args: { { Domain }, { Domain } } };
421	static Signature bin_map =
422	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Domain, Range } } };
423	static std::vector<Signature> bin_op = { bin_params, bin_set, bin_map };
424	static std::vector<Signature> fn_bin_op = { bin_set, bin_map };
425	static Signature bin_set_params = { .ret: { Domain }, .args: { { Domain }, { } } };
426	static Signature bin_map_params =
427	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { } } };
428	static Signature bin_map_domain =
429	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Domain } } };
430	static Signature bin_map_range =
431	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Range } } };
432	static Signature bin_map_domain_wrapped_domain =
433	{ .ret: { { Domain, Domain2 }, Range },
434	.args: { { { Domain, Domain2 }, Range }, { Domain } } };
435	static Signature bin_map_range_wrapped_domain =
436	{ .ret: { Domain, { Range, Range2 } },
437	.args: { { Domain, { Range, Range2 } }, { Range } } };
438
439	/* Signatures for binary operations, where the second argument
440	* is an identifier (with an anonymous tuple).
441	*/
442	static Signature bin_params_anon = { .ret: { }, .args: { { }, { Anonymous } } };
443	static Signature bin_set_anon = { .ret: { Domain }, .args: { { Domain }, { Anonymous } } };
444	static Signature bin_map_anon =
445	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Anonymous } } };
446	static std::vector<Signature> bin_op_anon =
447	{ bin_params_anon, bin_set_anon, bin_map_anon };
448
449	/* Signatures for ternary operations, where the last two arguments are integers.
450	*/
451	static Signature ter_params_int_int =
452	{ .ret: { }, .args: { { }, { Integer }, { Integer } } };
453	static Signature ter_set_int_int =
454	{ .ret: { Domain }, .args: { { Domain }, { Integer }, { Integer } } };
455	static Signature ter_map_int_int =
456	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Integer }, { Integer } } };
457	static std::vector<Signature> ter_int_int =
458	{ ter_params_int_int, ter_set_int_int, ter_map_int_int };
459
460	/* Signatures for ternary operations.
461	* Functions have at least one tuple.
462	*/
463	static Signature ter_set =
464	{ .ret: { Domain }, .args: { { Domain }, { Domain }, { Domain } } };
465	static Signature ter_map =
466	{ .ret: { Domain, Range },
467	.args: { { Domain, Range }, { Domain, Range }, { Domain, Range } } };
468	static std::vector<Signature> fn_ter_op = { ter_set, ter_map };
469
470	/* Signatures for naming a leaf tuple using an identifier (with an anonymous
471	* tuple).
472	*/
473	static Signature update_set = { .ret: { Domain2 }, .args: { { Leaf }, { Anonymous } } };
474	static Signature update_domain =
475	{ .ret: { Domain2, Range }, .args: { { Leaf, Range }, { Anonymous } } };
476	static Signature update_range =
477	{ .ret: { Domain, Range2 }, .args: { { Domain, Leaf }, { Anonymous } } };
478
479	/* Signatures for the functions "min" and "max", which can be either
480	* unary or binary operations.
481	*/
482	static std::vector<Signature> min_max = { un_set, bin_set, un_map, bin_map };
483
484	/* Signatures for adding an unnamed tuple to an object with zero or one tuple.
485	*/
486	static Signature to_set = { .ret: { Domain }, .args: { { }, { Integer } } };
487	static Signature add_range = { .ret: { Domain, Range }, .args: { { Domain }, { Integer } } };
488	/* Signatures for adding a named tuple to an object with zero or one tuple.
489	*/
490	static Signature to_set_named =
491	{ .ret: { Domain }, .args: { { }, { Anonymous }, { Integer } } };
492	static Signature add_range_named =
493	{ .ret: { Domain, Range }, .args: { { Domain }, { Anonymous }, { Integer } } };
494
495	/* Signatures for methods applying a map to a set, a function or
496	* part of a map.
497	*/
498	static Signature set_forward = { .ret: { Range }, .args: { { Domain }, { Domain, Range } } };
499	static Signature domain_forward =
500	{ .ret: { Domain2, Range }, .args: { { Domain, Range }, { Domain, Domain2 } } };
501	static Signature range_forward =
502	{ .ret: { Domain, Range2 }, .args: { { Domain, Range }, { Range, Range2 } } };
503
504	/* Signatures for methods plugging in a function into a set, a function or
505	* part of a map.
506	*/
507	static Signature set_backward =
508	{ .ret: { Domain2 }, .args: { { Domain }, { Domain2, Domain } } };
509	static Signature domain_backward =
510	{ .ret: { Domain2, Range }, .args: { { Domain, Range }, { Domain2, Domain } } };
511	static Signature range_backward =
512	{ .ret: { Domain, Range2 }, .args: { { Domain, Range }, { Range2, Range } } };
513	static Signature domain_wrapped_domain_backward =
514	{ .ret: { { Domain3, Domain2 }, Range },
515	.args: { { { Domain, Domain2 }, Range }, { Domain3, Domain } } };
516
517	/* Signatures for methods binding a set, a function,
518	* or (part of) a map to parameters or an object of the same kind.
519	*/
520	static Signature bind_set = { .ret: { }, .args: { { Domain }, { Domain } } };
521	static Signature bind_domain = { .ret: { Range }, .args: { { Domain, Range }, { Domain } } };
522	static Signature bind_range = { .ret: { Domain }, .args: { { Domain, Range }, { Range } } };
523	static Signature bind_domain_wrapped_domain =
524	{ .ret: { Range2, Range }, .args: { { { Domain2, Range2 }, Range }, { Domain2 } } };
525
526	/* Signatures for functions that take a callback accepting
527	* objects of the same kind (but a different type).
528	*
529	* The return and argument kinds of the callback appear
530	* at the position of the callback.
531	*/
532	static Signature each_params = { .ret: { Res }, .args: { { }, { Res }, { } } };
533	static Signature each_set = { .ret: { Res }, .args: { { Domain }, { Res }, { Domain } } };
534	static Signature each_map =
535	{ .ret: { Res }, .args: { { Domain, Range }, { Res }, { Domain, Range } } };
536	static std::vector<Signature> each = { each_params, each_set, each_map };
537
538	/* Signatures for isl_*_list_foreach_scc.
539	*
540	* The first callback takes two elements with the same tuple kinds.
541	* The second callback takes a list with the same tuple kinds.
542	*/
543	static Signature each_scc_params =
544	{ .ret: { Res }, .args: { { }, { Res }, { }, { }, { Res }, { } } };
545	static Signature each_scc_set =
546	{ .ret: { Res }, .args: { { Domain },
547	{ Res }, { Domain }, { Domain },
548	{ Res }, { Domain } } };
549	static Signature each_scc_map =
550	{ .ret: { Res }, .args: { { Domain, Range },
551	{ Res }, { Domain, Range }, { Domain, Range },
552	{ Res }, { Domain, Range } } };
553	static std::vector<Signature> each_scc =
554	{ each_scc_params, each_scc_set, each_scc_map };
555
556	/* Signature for creating a map from a range,
557	* where the domain is given by an extra argument.
558	*/
559	static Signature map_from_range_and_domain =
560	{ .ret: { Domain, Range }, .args: { { Range }, { Domain } } };
561
562	/* Signature for creating a map from a domain,
563	* where the range is given by an extra argument.
564	*/
565	static Signature map_from_domain_and_range =
566	{ .ret: { Domain, Range }, .args: { { Domain }, { Range } } };
567
568	/* Signatures for creating an anonymous set from a parameter set
569	* or a map from a domain, where the range is anonymous.
570	*/
571	static Signature anonymous_set_from_params = { .ret: { Anonymous }, .args: { { } } };
572	static Signature anonymous_map_from_domain =
573	{ .ret: { Domain, Anonymous }, .args: { { Domain } } };
574	static std::vector<Signature> anonymous_from_domain =
575	{ anonymous_set_from_params, anonymous_map_from_domain };
576
577	/* Signature for creating a set from a parameter set,
578	* where the domain is given by an extra argument.
579	*/
580	static Signature set_from_params = { .ret: { Domain }, .args: { { }, { Domain } } };
581
582	/* Signatures for creating an anonymous function from a domain,
583	* where the second argument is an identifier (with an anonymous tuple).
584	*/
585	static Signature anonymous_set_from_params_bin_anon =
586	{ .ret: { Anonymous }, .args: { { }, { Anonymous } } };
587	static Signature anonymous_map_from_domain_bin_anon =
588	{ .ret: { Domain, Anonymous }, .args: { { Domain }, { Anonymous } } };
589	static std::vector<Signature> anonymous_from_domain_bin_anon = {
590	anonymous_set_from_params_bin_anon,
591	anonymous_map_from_domain_bin_anon
592	};
593
594	/* Signature for creating a map from a domain,
595	* where the range tuple is equal to the domain tuple.
596	*/
597	static Signature set_to_map = { .ret: { Domain, Domain }, .args: { { Domain } } };
598
599	/* Signatures for obtaining the range or the domain of a map.
600	* In case of a transformation, the domain and range are the same.
601	*/
602	static Signature domain = { .ret: { Domain }, .args: { { Domain, Range } } };
603	static Signature range = { .ret: { Range }, .args: { { Domain, Range } } };
604	static Signature transformation_domain = { .ret: { Domain }, .args: { { Domain, Domain } } };
605
606	/* Signatures for obtaining the parameter domain of a set or map.
607	*/
608	static Signature set_params = { .ret: { }, .args: { { Domain } } };
609	static Signature map_params = { .ret: { }, .args: { { Domain, Range } } };
610
611	/* Signatures for obtaining the domain of a function.
612	*/
613	static std::vector<Signature> fn_domain = { domain, set_params };
614
615	/* Signatures for interchanging (wrapped) domain and range.
616	*/
617	static Signature map_reverse = { .ret: { Range, Domain }, .args: { { Domain, Range } } };
618	static Signature map_range_reverse =
619	{ .ret: { Domain, { Range2, Range } }, .args: { { Domain, { Range, Range2 } } } };
620
621	/* Signatures for constructing products.
622	*/
623	static Signature set_product =
624	{ .ret: { { Domain, Range } }, .args: { { Domain }, { Range } } };
625	static Signature map_product =
626	{ .ret: { { Domain, Domain2 }, { Range, Range2 } },
627	.args: { { Domain, Range }, { Domain2, Range2 } } };
628	static Signature domain_product =
629	{ .ret: { { Domain, Domain2 }, Range },
630	.args: { { Domain, Range }, { Domain2, Range } } };
631	static Signature range_product =
632	{ .ret: { Domain, { Range, Range2 } },
633	.args: { { Domain, Range }, { Domain, Range2 } } };
634
635	/* Signatures for obtaining factors from a product.
636	*/
637	static Signature domain_factor_domain =
638	{ .ret: { Domain, Range }, .args: { { { Domain, Domain2 }, Range } } };
639	static Signature domain_factor_range =
640	{ .ret: { Domain2, Range }, .args: { { { Domain, Domain2 }, Range } } };
641	static Signature range_factor_domain =
642	{ .ret: { Domain, Range }, .args: { { Domain, { Range, Range2 } } } };
643	static Signature range_factor_range =
644	{ .ret: { Domain, Range2 }, .args: { { Domain, { Range, Range2 } } } };
645
646	/* Signatures for (un)currying.
647	*/
648	static Signature curry =
649	{ .ret: { Domain, { Range, Range2 } },
650	.args: { { { Domain, Range }, Range2 } } };
651	static Signature uncurry =
652	{ .ret: { { Domain, Range }, Range2 },
653	.args: { { Domain, { Range, Range2 } } } };
654
655	/* Signatures for (un)wrapping.
656	*/
657	static Signature wrap = { .ret: { { Domain, Range } }, .args: { { Domain, Range } } };
658	static Signature unwrap = { .ret: { Domain, Range }, .args: { { { Domain, Range } } } };
659
660	/* Signatures for constructing objects that map to the domain or range
661	* of a map.
662	*/
663	static Signature domain_map =
664	{ .ret: { { Domain, Range }, Domain }, .args: { { Domain, Range } } };
665	static Signature range_map =
666	{ .ret: { { Domain, Range }, Range }, .args: { { Domain, Range } } };
667
668	/* Signature for applying a comparison between the domain and the range
669	* of a map.
670	*/
671	static Signature map_cmp =
672	{ .ret: { Domain, Domain }, .args: { { Domain, Domain }, { Domain, Range } } };
673
674	/* Signature for creating a set corresponding to the domains
675	* of two functions.
676	*/
677	static Signature set_join =
678	{ .ret: { Domain }, .args: { { Domain, Range }, { Domain, Range } } };
679
680	/* Signatures for flattening the domain or range of a map,
681	* replacing it with either an anonymous tuple or a tuple with a given name.
682	*/
683	static Signature anonymize_nested_domain =
684	{ .ret: { Anonymous, Range2 }, .args: { { { Domain, Range }, Range2 } } };
685	static Signature anonymize_nested_range =
686	{ .ret: { Domain, Anonymous }, .args: { { Domain, { Range, Range2 } } } };
687	static Signature replace_nested_domain =
688	{ .ret: { Domain2, Range2 },
689	.args: { { { Domain, Range }, Range2 }, { Anonymous} } };
690	static Signature replace_nested_range =
691	{ .ret: { Domain, Range3 }, .args: { { Domain, { Range, Range2 } }, { Anonymous} } };
692	static std::vector<Signature> flatten_domain =
693	{ anonymize_nested_domain, replace_nested_domain };
694	static std::vector<Signature> flatten_range =
695	{ anonymize_nested_range, replace_nested_range };
696
697	/* Signatures for "set_at" methods.
698	*/
699	static Signature set_at_set =
700	{ .ret: { Domain }, .args: { { Domain }, { Integer }, { Anonymous } } };
701	static Signature set_at_map =
702	{ .ret: { Domain, Range },
703	.args: { { Domain, Range }, { Integer }, { Domain, Anonymous } } };
704	static std::vector<Signature> set_at = { set_at_set, set_at_map };
705
706	/* Signatures for "list" methods, extracting a list
707	* from a multi-expression.
708	*/
709	static Signature to_list_set = { .ret: { Anonymous }, .args: { { Domain } } };
710	static Signature to_list_map = { .ret: { Domain, Anonymous }, .args: { { Domain, Range } } };
711
712	/* Signatures for functions constructing an object from only an isl::ctx.
713	*/
714	static Signature ctx_params = { .ret: { }, .args: { { Ctx } } };
715	static Signature ctx_set = { .ret: { Domain }, .args: { { Ctx } } };
716	static Signature ctx_map = { .ret: { Domain, Range }, .args: { { Ctx } } };
717
718	/* Helper structure for sorting the keys of static_methods and
719	* special_member_methods such that the larger keys appear first.
720	* In particular, a key should appear before any key that appears
721	* as a substring in the key.
722	* Note that this sorting is currently only important
723	* for special_member_methods.
724	*/
725	struct larger_infix {
726	bool operator()(const std::string &x, const std::string &y) const {
727	if (x.length() > y. length())
728	return true;
729	return x < y;
730	}
731	};
732
733	/* A map from part of a type name to a sequence of signatures.
734	*/
735	typedef std::map<std::string, std::vector<Signature>, larger_infix> infix_map;
736
737	/* A map from a method name to a map from part of a type name
738	* to a sequence of signatures.
739	*/
740	typedef std::map<std::string, infix_map> infix_map_map;
741
742	/* Signatures for static methods.
743	*
744	* The "unit" static method is only available in a 0-tuple space.
745	*
746	* The "empty" static method creates union objects with the relevant
747	* number of tuples.
748	*
749	* The "universe" static methods create objects from the corresponding spaces.
750	*/
751	static const infix_map_map static_methods {
752	{ "unit",
753	{ { "space", { ctx_params } } }
754	},
755	{ "empty",
756	{
757	{ "union_set", { ctx_params, ctx_set } },
758	{ "union_map", { ctx_map } },
759	{ "union_pw_multi_aff", { ctx_set, ctx_map } },
760	}
761	},
762	{ "universe",
763	{
764	{ "set", { un_params, un_set } },
765	{ "map", { un_map } },
766	}
767	},
768	};
769
770	/* Signatures for unary operations that either take something in a set space
771	* and return something in the same space or take something in a map space
772	* and return something in the range of that space.
773	*/
774	static std::vector<Signature> range_op = { un_set, range };
775
776	/* Signatures for binary operations where the second argument
777	* is a (multi-)value.
778	*/
779	static std::vector<Signature> bin_val = { bin_set, bin_map_range };
780
781	/* The (default) signatures for methods with a given name.
782	* Some of these are overridden by special_member_methods.
783	*/
784	static const std::unordered_map<std::string, std::vector<Signature>>
785	member_methods {
786	{ "add", bin_op },
787	{ "add_constant", bin_val },
788	{ "add_named_tuple", { to_set_named, add_range_named } },
789	{ "add_param", bin_op_anon },
790	{ "add_unnamed_tuple", { to_set, add_range } },
791	{ "apply", { set_forward, range_forward } },
792	{ "apply_domain", { domain_forward } },
793	{ "apply_range", { range_forward } },
794	{ "as", un_op },
795	{ "as_map", { un_map } },
796	{ "as_union_map", { un_map } },
797	{ "as_set", { un_set } },
798	{ "bind", { bind_set, bind_range } },
799	{ "bind_domain", { bind_domain } },
800	{ "bind_range", { bind_range } },
801	{ "bind_domain_wrapped_domain",
802	{ bind_domain_wrapped_domain } },
803	{ "ceil", fn_un_op },
804	{ "coalesce", un_op },
805	{ "cond", fn_ter_op },
806	{ "constant", range_op },
807	{ "curry", { curry } },
808	{ "deltas", { transformation_domain } },
809	{ "detect_equalities", un_op },
810	{ "domain", fn_domain },
811	{ "domain_factor_domain",
812	{ domain_factor_domain } },
813	{ "domain_factor_range",
814	{ domain_factor_range } },
815	{ "domain_map", { domain_map } },
816	{ "domain_product", { domain_product } },
817	{ "drop", ter_int_int },
818	{ "eq_at", { map_cmp } },
819	{ "every", each },
820	{ "extract", bin_op },
821	{ "flatten_domain", flatten_domain },
822	{ "flatten_range", flatten_range },
823	{ "floor", fn_un_op },
824	{ "foreach", each },
825	{ "foreach_scc", each_scc },
826	{ "ge_set", { set_join } },
827	{ "gt_set", { set_join } },
828	{ "gist", bin_op },
829	{ "gist_domain", { bin_map_domain } },
830	{ "gist_params", { bin_set_params, bin_map_params } },
831	{ "identity", { un_map, set_to_map } },
832	{ "identity_on_domain", { set_to_map } },
833	{ "indicator_function", anonymous_from_domain },
834	{ "insert_domain", { map_from_range_and_domain } },
835	{ "intersect", bin_op },
836	{ "intersect_params", { bin_set_params, bin_map_params } },
837	{ "intersect_domain", { bin_map_domain } },
838	{ "intersect_domain_wrapped_domain",
839	{ bin_map_domain_wrapped_domain } },
840	{ "intersect_range", { bin_map_range } },
841	{ "intersect_range_wrapped_domain",
842	{ bin_map_range_wrapped_domain } },
843	{ "lattice_tile", { un_set } },
844	{ "le_set", { set_join } },
845	{ "lt_set", { set_join } },
846	{ "lex_le_at", { map_cmp } },
847	{ "lex_lt_at", { map_cmp } },
848	{ "lex_ge_at", { map_cmp } },
849	{ "lex_gt_at", { map_cmp } },
850	{ "lexmin", fn_un_op },
851	{ "lexmax", fn_un_op },
852	{ "list", { to_list_set, to_list_map } },
853	{ "lower_bound", fn_bin_op },
854	{ "map_from_set", { set_to_map } },
855	{ "max", min_max },
856	{ "max_val", range_op },
857	{ "max_multi_val", range_op },
858	{ "min", min_max },
859	{ "min_val", range_op },
860	{ "min_multi_val", range_op },
861	{ "mod", bin_val },
862	{ "on_domain", { map_from_domain_and_range } },
863	{ "neg", fn_un_op },
864	{ "offset", fn_un_op },
865	{ "param_on_domain", anonymous_from_domain_bin_anon },
866	{ "params", { set_params, map_params } },
867	{ "plain_multi_val_if_fixed",
868	{ un_set } },
869	{ "preimage", { set_backward } },
870	{ "preimage_domain", { domain_backward } },
871	{ "preimage_domain_wrapped_domain",
872	{ domain_wrapped_domain_backward } },
873	{ "preimage_range", { range_backward } },
874	{ "product", { set_product, map_product } },
875	{ "project_out_param", bin_op_anon },
876	{ "project_out_all_params",
877	un_op },
878	{ "pullback", { domain_backward, bind_domain } },
879	{ "range", { range } },
880	{ "range_factor_domain",
881	{ range_factor_domain } },
882	{ "range_factor_range", { range_factor_range } },
883	{ "range_lattice_tile", { un_map } },
884	{ "range_map", { range_map } },
885	{ "range_product", { range_product } },
886	{ "range_reverse", { map_range_reverse } },
887	{ "range_simple_fixed_box_hull",
888	{ un_map } },
889	{ "reverse", { map_reverse } },
890	{ "scale", bin_val },
891	{ "scale_down", bin_val },
892	{ "set_at", set_at },
893	{ "set_domain_tuple", { update_domain } },
894	{ "set_range_tuple", { update_set, update_range } },
895	{ "simple_fixed_box_hull",
896	{ un_set } },
897	{ "sub", fn_bin_op },
898	{ "subtract", bin_op },
899	{ "subtract_domain", { bin_map_domain } },
900	{ "subtract_range", { bin_map_range } },
901	{ "translation", { set_to_map } },
902	{ "to", un_op },
903	{ "unbind_params", { set_from_params } },
904	{ "unbind_params_insert_domain",
905	{ map_from_range_and_domain } },
906	{ "uncurry", { uncurry } },
907	{ "union_add", fn_bin_op },
908	{ "unite", bin_op },
909	{ "universe", un_op },
910	{ "unwrap", { unwrap } },
911	{ "upper_bound", fn_bin_op },
912	{ "wrap", { wrap } },
913	{ "zero", fn_un_op },
914	{ "zero_on_domain", { anonymous_map_from_domain } },
915	};
916
917	/* Signatures for methods of types containing a given substring
918	* that override the default signatures, where larger substrings
919	* appear first.
920	*
921	* In particular, "gist" is usually a regular binary operation,
922	* but for any type derived from "aff", the argument refers
923	* to the domain of the function.
924	*
925	* The "size" method can usually simply be inherited from
926	* the corresponding plain C++ type, but for a "fixed_box",
927	* the size lives in the space of the box or its range.
928	*
929	* The "space" method is usually a regular unary operation
930	* that returns the single space of the elements in the object,
931	* with the same number of tuples.
932	* However, a "union" object may contain elements from many spaces and
933	* therefore its space only refers to the symbolic constants and
934	* has zero tuples, except if it is also a "multi_union" object,
935	* in which case it has a fixed range space and the space of the object
936	* has a single tuple.
937	* Note that since "space' is also the name of a template class,
938	* the default space method is handled by print_type_named_member_method.
939	*/
940	static const infix_map_map special_member_methods {
941	{ "gist",
942	{ { "aff", { bin_set_params, bin_map_domain } } }
943	},
944	{ "size",
945	{ { "fixed_box", range_op } },
946	},
947	{ "space",
948	{
949	{ "multi_union", range_op },
950	{ "union", { un_params, set_params, map_params } },
951	}
952	},
953	};
954
955	/* Generic kinds for objects with zero, one or two tuples,
956	* the last of which may be anonymous.
957	*/
958	static Kind params{};
959	static Kind set_type{ Domain };
960	static Kind set_anon{ Anonymous };
961	static Kind map_type{ Domain, Range };
962	static Kind map_anon{ Domain, Anonymous };
963
964	/* The initial sequence of specialization kinds for base types.
965	* The specialization kinds for other types are derived
966	* from the corresponding base types.
967	*
968	* In particular, this sequence specifies how many tuples
969	* a given type can have and whether it is anonymous.
970	*
971	* "space" can have any number of tuples.
972	* "set" and "point" can have zero or one tuple.
973	* "map" can only have two tuples.
974	* "aff" can have one or two tuples, the last of which is anonymous.
975	* "fixed_box" can represent a (proper) set) or a map.
976	* "val" and "id" are treated as anonymous sets so that
977	* they can form the basis of "multi_val" and "multi_id".
978	*/
979	static const std::unordered_map<std::string, std::vector<Kind>> base_kinds {
980	{ "space", { params, set_type, map_type } },
981	{ "set", { params, set_type } },
982	{ "point", { params, set_type } },
983	{ "map", { map_type } },
984	{ "aff", { set_anon, map_anon } },
985	{ "fixed_box", { set_type, map_type } },
986	{ "val", { set_anon } },
987	{ "id", { set_anon } },
988	};
989
990	/* Prefixes introduced by type constructors.
991	*/
992	static const std::unordered_set<std::string> type_prefixes {
993	"basic",
994	"multi",
995	"pw",
996	"union",
997	};
998
999	/* If "type" has a "_list" suffix, then return "type" with this suffix removed.
1000	* Otherwise, simply return "type".
1001	*/
1002	static std::string drop_list(const std::string &type)
1003	{
1004	size_t pos = type.rfind(c: '_');
1005
1006	if (pos == std::string::npos)
1007	return type;
1008	if (type.substr(pos: pos + 1) == "list")
1009	return type.substr(pos: 0, n: pos);
1010	return type;
1011	}
1012
1013	/* Given the name of a plain C++ type, return the base type
1014	* from which it was derived using type constructors.
1015	*
1016	* In particular, drop any "list" suffix and
1017	* drop any prefixes from type_prefixes, stopping
1018	* as soon as a base type is found for which kinds have been registered
1019	* in base_kinds.
1020	*/
1021	static std::string base_type(const std::string &type)
1022	{
1023	auto base = type;
1024	size_t pos;
1025
1026	base = drop_list(type: base);
1027	while (base_kinds.count(x: base) == 0 &&
1028	(pos = base.find(c: '_')) != std::string::npos &&
1029	type_prefixes.count(x: base.substr(pos: 0, n: pos)) != 0) {
1030	base = base.substr(pos: pos + 1);
1031	}
1032
1033	return base;
1034	}
1035
1036	/* A mapping from anonymous kinds to named kinds.
1037	*/
1038	static std::map<Kind, Kind> anon_to_named {
1039	{ set_anon, set_type },
1040	{ map_anon, map_type },
1041	};
1042
1043	/* Given a sequence of anonymous kinds, replace them
1044	* by the corresponding named kinds.
1045	*/
1046	static std::vector<Kind> add_name(const std::vector<Kind> &tuples)
1047	{
1048	std::vector<Kind> named;
1049
1050	for (const auto &tuple : tuples)
1051	named.emplace_back(args&: anon_to_named.at(k: tuple));
1052
1053	return named;
1054	}
1055
1056	/* Look up the (initial) specializations of the class called "name".
1057	* If no specializations have been defined, then return an empty vector.
1058	*
1059	* Start from the initial specializations of the corresponding base type.
1060	* If this template class is a multi-expression, then it was derived
1061	* from an anonymous function type. Replace the final Anonymous
1062	* tuple kind by a placeholder in this case.
1063	*/
1064	static std::vector<Kind> lookup_class_tuples(const std::string &name)
1065	{
1066	std::string base = base_type(type: name);
1067
1068	if (base_kinds.count(x: base) == 0)
1069	return { };
1070	if (name.find(s: "multi_") != std::string::npos)
1071	return add_name(tuples: base_kinds.at(k: base));
1072	return base_kinds.at(k: base);
1073	}
1074
1075	/* Add a template class called "name", of which the methods are described
1076	* by "clazz" and the initial specializations by "class_tuples".
1077	*/
1078	void template_cpp_generator::add_template_class(const isl_class &clazz,
1079	const std::string &name, const std::vector<Kind> &class_tuples)
1080	{
1081	auto isl_namespace = cpp_type_printer().isl_namespace();
1082	auto super = isl_namespace + name;
1083
1084	template_classes.emplace(args: name,
1085	args: template_class{.class_name: name, .super_name: super, .clazz: clazz, .class_tuples: class_tuples});
1086	}
1087
1088	/* Construct a templated C++ bindings generator from
1089	* the exported types and functions and the set of all declared functions.
1090	*
1091	* On top of the initialization of the shared parts
1092	* of C++ bindings generators, add a template class
1093	* for each plain C++ class for which template kinds
1094	* have been defined.
1095	* In particular, determine the base type from which the plain C++ class
1096	* was derived using type constructors and check if any template kinds
1097	* have been registered for this base type.
1098	*/
1099	template_cpp_generator::template_cpp_generator(clang::SourceManager &SM,
1100	std::set<clang::RecordDecl *> &exported_types,
1101	std::set<clang::FunctionDecl *> exported_functions,
1102	std::set<clang::FunctionDecl *> functions) :
1103	cpp_generator(SM, exported_types, exported_functions,
1104	functions)
1105	{
1106	for (const auto &kvp : classes) {
1107	const auto &clazz = kvp.second;
1108	std::string name = type2cpp(clazz);
1109	const auto &class_tuples = lookup_class_tuples(name);
1110
1111	if (class_tuples.empty())
1112	continue;
1113	add_template_class(clazz: clazz, name, class_tuples: class_tuples);
1114	}
1115	}
1116
1117	/* Call "fn" on each template class.
1118	*/
1119	void template_cpp_generator::foreach_template_class(
1120	const std::function<void(const template_class &)> &fn) const
1121	{
1122	for (const auto &kvp : template_classes)
1123	fn(kvp.second);
1124	}
1125
1126	/* Print forward declarations for all template classes to "os".
1127	*
1128	* For template classes that represent an anonymous function
1129	* that can also have a domain tuple, provide an <name>_on alias
1130	* that adds the fixed Anonymous tuple kind.
1131	*/
1132	void template_cpp_generator::print_forward_declarations(std::ostream &os)
1133	{
1134	foreach_template_class(fn: [&os] (const template_class &template_class) {
1135	auto name = template_class.class_name;
1136
1137	os << "\n";
1138	os << "template <typename...>\n";
1139	os << "struct " << name << ";\n";
1140
1141	if (!template_class.is_anon())
1142	return;
1143	if (template_class.is_anon_set())
1144	return;
1145
1146	os << "\n";
1147	os << "template <typename...Ts>\n";
1148	os << "using " << name << "_on = "
1149	<< name << "<Ts..., Anonymous>;\n";
1150	});
1151	}
1152
1153	/* Print friend declarations for all template classes to "os".
1154	*/
1155	void template_cpp_generator::print_friends(std::ostream &os)
1156	{
1157	foreach_template_class(fn: [&os] (const template_class &template_class) {
1158	os << " template <typename...>\n";
1159	os << " friend struct " << template_class.class_name << ";\n";
1160	});
1161	}
1162
1163	/* Print a template parameter or argument.
1164	* In case of a std::string, it's a template parameter
1165	* that needs to be declared.
1166	*/
1167	static void print_template_arg(std::ostream &os, const std::string &arg)
1168	{
1169	os << "typename " << arg;
1170	}
1171
1172	/* Print a template parameter or argument.
1173	* In case of a TupleKindPtr, it's a template argument.
1174	*/
1175	static void print_template_arg(std::ostream &os, const TupleKindPtr &kind)
1176	{
1177	os << kind->to_string();
1178	}
1179
1180	/* Print a sequence of template parameters (std::string) or
1181	* arguments (TupleKindPtr) "args", without the enclosing angle brackets.
1182	*/
1183	template <typename List>
1184	static void print_pure_template_args(std::ostream &os, const List &args)
1185	{
1186	for (size_t i = 0; i < args.size(); ++i) {
1187	if (i != 0)
1188	os << ", ";
1189	print_template_arg(os, args[i]);
1190	}
1191	}
1192
1193	/* Print a sequence of template parameters (std::string) or
1194	* arguments (TupleKindPtr) "args".
1195	*/
1196	template <typename List>
1197	static void print_template_args(std::ostream &os, const List &args)
1198	{
1199	os << "<";
1200	print_pure_template_args(os, args);
1201	os << ">";
1202	}
1203
1204	/* Print a declaration of the template parameters "params".
1205	*/
1206	static void print_template(std::ostream &os,
1207	const std::vector<std::string> &params)
1208	{
1209	os << "template ";
1210	print_template_args(os, args: params);
1211	os << "\n";
1212	}
1213
1214	/* Print a declaration of the template parameters "params",
1215	* if there are any.
1216	*/
1217	static void print_non_empty_template(std::ostream &os,
1218	const std::vector<std::string> &params)
1219	{
1220	if (params.size() > 0)
1221	print_template(os, params);
1222	}
1223
1224	/* Print a bare template type, i.e., without namespace,
1225	* consisting of the type "type" and the kind "kind" to "os".
1226	*
1227	* In particular, print "type" followed by the template arguments
1228	* as specified by "kind".
1229	*/
1230	static void print_bare_template_type(std::ostream &os, const std::string &type,
1231	const Kind &kind)
1232	{
1233	os << type;
1234	print_template_args(os, args: kind);
1235	}
1236
1237	/* A specific instance of "template_class", with tuple kinds given by "kind".
1238	*/
1239	struct specialization {
1240	struct template_class &template_class;
1241	Kind kind;
1242
1243	const std::string &base_name() const;
1244	const std::string &class_name() const;
1245	};
1246
1247	/* The name of the plain C++ interface class
1248	* from which this template class (instance) derives.
1249	*/
1250	const std::string &specialization::base_name() const
1251	{
1252	return template_class.super_name;
1253	}
1254
1255	/* The name of the template class.
1256	*/
1257	const std::string &specialization::class_name() const
1258	{
1259	return template_class.class_name;
1260	}
1261
1262	/* Helper class for printing the specializations of template classes
1263	* that is used to print both the class declarations and the class definitions.
1264	*
1265	* "os" is the stream onto which the classes should be printed.
1266	* "generator" is the templated C++ interface generator printing the classes.
1267	*/
1268	struct specialization_printer {
1269	specialization_printer(std::ostream &os,
1270	template_cpp_generator &generator) :
1271	os(os), generator(generator) {}
1272
1273	virtual void print_class(const specialization &instance) const = 0;
1274	void print_classes() const;
1275
1276	std::ostream &os;
1277	template_cpp_generator &generator;
1278	};
1279
1280	/* Print all specializations of all template classes.
1281	*
1282	* Each class has a predefined set of initial specializations,
1283	* but while such a specialization is being printed,
1284	* the need for other specializations may arise and
1285	* these are added at the end of the list of specializations.
1286	* That is, class_tuples.size() may change during the execution
1287	* of the loop.
1288	*
1289	* For each specialization of a template class, call
1290	* the print_class virtual method.
1291	*/
1292	void specialization_printer::print_classes() const
1293	{
1294	for (auto &kvp : generator.template_classes) {
1295	auto &template_class = kvp.second;
1296	const auto &class_tuples = template_class.class_tuples;
1297
1298	for (size_t i = 0; i < class_tuples.size(); ++i)
1299	print_class(instance: { .template_class: template_class, .kind: class_tuples[i] });
1300	}
1301	}
1302
1303	/* A helper class for printing method declarations and definitions
1304	* of a template class specialization.
1305	*
1306	* "instance" is the template class specialization for which methods
1307	* are printed.
1308	* "generator" is the templated C++ interface generator printing the classes.
1309	*/
1310	struct template_cpp_generator::class_printer :
1311	public cpp_generator::class_printer {
1312	class_printer(const specialization &instance,
1313	const specialization_printer &instance_printer,
1314	bool is_declaration);
1315
1316	void print_return_type(const Method &method, const Kind &kind)
1317	const;
1318	void print_method_template_arguments(const Signature &sig);
1319	void print_method_header(const Method &method, const Signature &sig);
1320	bool print_special_method(const Method &method,
1321	const infix_map_map &special_methods);
1322	void print_static_method(const Method &method);
1323	void print_constructor(const Method &method);
1324	bool is_return_kind(const Method &method, const Kind &return_kind);
1325	void add_specialization(const Kind &kind);
1326	bool print_matching_method(const Method &method, const Signature &sig,
1327	const Kind &match_arg);
1328	bool print_matching_method(const Method &method, const Signature &sig);
1329	void print_matching_method(const Method &method,
1330	const std::vector<Signature> &signatures);
1331	void print_at_method(const Method &method);
1332	bool print_special_member_method(const Method &method);
1333	bool print_type_named_member_method(const Method &method);
1334	bool print_member_method_with_name(const Method &method,
1335	const std::string &name);
1336	void print_member_method(const Method &method);
1337	void print_any_method(const Method &method);
1338	virtual void print_method(const Method &method) override;
1339	virtual void print_method(const ConversionMethod &method) override;
1340	virtual void print_method_sig(const Method &method,
1341	const Signature &sig, bool deleted) = 0;
1342	virtual bool want_descendent_overloads(const function_set &methods)
1343	override;
1344	void print_all_methods();
1345
1346	const specialization &instance;
1347	template_cpp_generator &generator;
1348	};
1349
1350	/* Construct a class_printer from the template class specialization
1351	* for which methods are printed and
1352	* the printer of the template class.
1353	*
1354	* The template class printer is only used to obtain the output stream and
1355	* the templated C++ interface generator printing the classes.
1356	*/
1357	template_cpp_generator::class_printer::class_printer(
1358	const specialization &instance,
1359	const specialization_printer &instance_printer,
1360	bool is_declaration) :
1361	cpp_generator::class_printer(instance_printer.os,
1362	instance.template_class.clazz, instance_printer.generator,
1363	is_declaration),
1364	instance(instance), generator(instance_printer.generator)
1365	{
1366	}
1367
1368	/* An abstract template type printer, where the way of obtaining
1369	* the argument kind is specified by the subclasses.
1370	*/
1371	struct template_cpp_type_printer : public cpp_type_printer {
1372	template_cpp_type_printer() {}
1373
1374	std::string base(const std::string &type, const Kind &kind) const;
1375	virtual Kind kind(int arg) const = 0;
1376	virtual std::string qualified(int arg, const std::string &cpp_type)
1377	const override;
1378	};
1379
1380	/* Print a template type consisting of the type "type" and the kind "kind",
1381	* including the "typed::" namespace specifier.
1382	*/
1383	std::string template_cpp_type_printer::base(const std::string &type,
1384	const Kind &kind) const
1385	{
1386	std::ostringstream ss;
1387
1388	ss << "typed::";
1389	print_bare_template_type(os&: ss, type, kind);
1390	return ss.str();
1391	}
1392
1393	/* Return the qualified form of the given C++ isl type name appearing
1394	* in argument position "arg" (-1 for return type).
1395	*
1396	* isl::ctx is not templated, so if "cpp_type" is "ctx",
1397	* then print a non-templated version.
1398	* Otherwise, look up the kind of the argument and print
1399	* the corresponding template type.
1400	*/
1401	std::string template_cpp_type_printer::qualified(int arg,
1402	const std::string &cpp_type) const
1403	{
1404	if (cpp_type == "ctx")
1405	return cpp_type_printer::qualified(arg, cpp_type);
1406
1407	return base(type: cpp_type, kind: kind(arg));
1408	}
1409
1410	/* A template type printer for printing types with a fixed kind.
1411	*
1412	* "fixed_kind" is the fixed kind.
1413	*/
1414	struct template_cpp_kind_type_printer : public template_cpp_type_printer {
1415	template_cpp_kind_type_printer(const Kind &kind) :
1416	template_cpp_type_printer(), fixed_kind(kind) {}
1417
1418	virtual Kind kind(int arg) const override;
1419
1420	const Kind &fixed_kind;
1421	};
1422
1423	/* Return the kind of the argument at position "arg",
1424	* where position -1 refers to the return type.
1425	*
1426	* Always use the fixed kind.
1427	*/
1428	Kind template_cpp_kind_type_printer::kind(int arg) const
1429	{
1430	return fixed_kind;
1431	}
1432
1433	/* A template type printer for printing a method with a given signature.
1434	*
1435	* "sig" is the signature of the method being printed.
1436	*/
1437	struct template_cpp_arg_type_printer : public template_cpp_type_printer {
1438	template_cpp_arg_type_printer(const Signature &sig) :
1439	template_cpp_type_printer(), sig(sig) {}
1440
1441	virtual Kind kind(int arg) const override;
1442
1443	const Signature &sig;
1444	};
1445
1446	/* Return the kind of the argument at position "arg",
1447	* where position -1 refers to the return type.
1448	*
1449	* Look up the kind in the signature.
1450	*/
1451	Kind template_cpp_arg_type_printer::kind(int arg) const
1452	{
1453	int n_args = sig.args.size();
1454
1455	if (arg < 0)
1456	return sig.ret;
1457	if (arg >= n_args)
1458	generator::die(msg: "argument out of bounds");
1459	return sig.args[arg];
1460	}
1461
1462	/* A template type printer for printing a method with a given signature
1463	* as part of a template class specialization of a given kind.
1464	*
1465	* "class_kind" is the template class specialization kind.
1466	*/
1467	struct template_method_type_printer : public template_cpp_arg_type_printer {
1468	template_method_type_printer(const Signature &sig,
1469	const Kind &class_kind) :
1470	template_cpp_arg_type_printer(sig),
1471	class_kind(class_kind) {}
1472
1473	virtual std::string class_type(const std::string &cpp_name)
1474	const override;
1475
1476	const Kind &class_kind;
1477	};
1478
1479	/* Print the class type "cpp_name".
1480	*
1481	* Print the templated version using the template class specialization kind.
1482	*/
1483	std::string template_method_type_printer::class_type(
1484	const std::string &cpp_name) const
1485	{
1486	return base(type: cpp_name, kind: class_kind);
1487	}
1488
1489	/* Print the templated return type of "method" of the kind "return_kind".
1490	*
1491	* Construct a type printer with "return_kind" as fixed kind and
1492	* use it to print the return type.
1493	*/
1494	void template_cpp_generator::class_printer::print_return_type(
1495	const Method &method, const Kind &return_kind) const
1496	{
1497	template_cpp_kind_type_printer printer(return_kind);
1498
1499	os << printer.return_type(method);
1500	}
1501
1502	/* Remove the initial "n" elements from "v".
1503	*/
1504	template <typename T>
1505	static void drop_initial(std::vector<T> &v, size_t n)
1506	{
1507	v.erase(v.begin(), v.begin() + n);
1508	}
1509
1510	/* If a method with signature "sig" requires additional template parameters
1511	* compared to those of the class, then print a declaration for them.
1512	* If this->declarations is set, then this will be part of a method declaration,
1513	* requiring extra indentation.
1514	*
1515	* Construct the sequence of all required template parameters
1516	* with those of the template class appearing first.
1517	* If this sequence has any parameters not induced by the template class itself,
1518	* then print a declaration for these extra parameters.
1519	*/
1520	void template_cpp_generator::class_printer::print_method_template_arguments(
1521	const Signature &sig)
1522	{
1523	std::vector<std::string> class_params, method_params;
1524
1525	class_params = instance.kind.params();
1526	method_params = class_params;
1527	combine(vec1&: method_params, vec2: sig.params());
1528
1529	if (class_params.size() == method_params.size())
1530	return;
1531
1532	drop_initial(v&: method_params, n: class_params.size());
1533
1534	if (declarations)
1535	os << " ";
1536	print_template(os, params: method_params);
1537	}
1538
1539	/* Print the header for "method" with signature "sig".
1540	*
1541	* First print any additional template parameters that may be required and
1542	* then print a regular method header, using a template type printer.
1543	*/
1544	void template_cpp_generator::class_printer::print_method_header(
1545	const Method &method, const Signature &sig)
1546	{
1547	template_method_type_printer type_printer(sig, instance.kind);
1548
1549	print_method_template_arguments(sig);
1550	cpp_generator::class_printer::print_method_header(method,
1551	type_printer);
1552	}
1553
1554	/* Given a group of methods with the same name,
1555	* should extra methods be added that take as arguments
1556	* those types that can be converted to the original argument type
1557	* through a unary constructor?
1558	*
1559	* Since type deduction does not consider implicit conversions,
1560	* these extra methods should always be printed.
1561	*/
1562	bool template_cpp_generator::class_printer::want_descendent_overloads(
1563	const function_set &methods)
1564	{
1565	return true;
1566	}
1567
1568	/* Print all constructors and methods that forward
1569	* to the corresponding methods in the plain C++ interface class.
1570	*/
1571	void template_cpp_generator::class_printer::print_all_methods()
1572	{
1573	print_constructors();
1574	print_methods();
1575	}
1576
1577	/* A helper class for printing method declarations
1578	* of a template class specialization.
1579	*/
1580	struct template_cpp_generator::method_decl_printer :
1581	public template_cpp_generator::class_printer {
1582	method_decl_printer(const specialization &instance,
1583	const struct specialization_printer &instance_printer) :
1584	class_printer(instance, instance_printer, true) {}
1585
1586	virtual void print_method_sig(const Method &method,
1587	const Signature &sig, bool deleted) override;
1588	virtual void print_get_method(FunctionDecl *fd) override;
1589	};
1590
1591	/* Print a declaration of the method "method" with signature "sig".
1592	* Mark is "delete" if "deleted" is set.
1593	*/
1594	void template_cpp_generator::method_decl_printer::print_method_sig(
1595	const Method &method, const Signature &sig, bool deleted)
1596	{
1597	print_method_header(method, sig);
1598	if (deleted)
1599	os << " = delete";
1600	os << ";\n";
1601	}
1602
1603	/* Return the total number of arguments in the signature for "method",
1604	* taking into account any possible callback arguments.
1605	*
1606	* In particular, if the method has a callback argument,
1607	* then the return kind of the callback appears at the position
1608	* of the callback and the kinds of the arguments (except
1609	* the user pointer argument) appear in the following positions.
1610	* The user pointer argument that follows the callback argument
1611	* is also removed.
1612	*/
1613	static int total_params(const Method &method)
1614	{
1615	int n = method.num_params();
1616
1617	for (const auto &callback : method.callbacks) {
1618	auto callback_type = callback->getType();
1619	auto proto = generator::extract_prototype(callback_type);
1620
1621	n += proto->getNumArgs() - 1;
1622	n -= 1;
1623	}
1624
1625	return n;
1626	}
1627
1628	/* Return a signature for "method" that matches "instance".
1629	*/
1630	static Signature instance_sig(const Method &method,
1631	const specialization &instance)
1632	{
1633	std::vector<Kind> args(total_params(method));
1634
1635	args[0] = instance.kind;
1636	return { .ret: instance.kind, .args: args };
1637	}
1638
1639	/* Print a declaration for the "get" method "fd",
1640	* using a name that includes the "get_" prefix.
1641	*
1642	* These methods are only included in the plain interface.
1643	* Explicitly delete them from the templated interface.
1644	*/
1645	void template_cpp_generator::method_decl_printer::print_get_method(
1646	FunctionDecl *fd)
1647	{
1648	Method method(clazz, fd, clazz.base_method_name(fd));
1649
1650	print_method_sig(method, sig: instance_sig(method, instance), deleted: true);
1651	}
1652
1653	/* A helper class for printing method definitions
1654	* of a template class specialization.
1655	*/
1656	struct template_cpp_generator::method_impl_printer :
1657	public template_cpp_generator::class_printer {
1658	method_impl_printer(const specialization &instance,
1659	const struct specialization_printer &instance_printer) :
1660	class_printer(instance, instance_printer, false) {}
1661
1662	void print_callback_method_body(const Method &method,
1663	const Signature &sig);
1664	void print_method_body(const Method &method, const Signature &sig);
1665	void print_constructor_body(const Method &method, const Signature &sig);
1666	virtual void print_method_sig(const Method &method,
1667	const Signature &sig, bool deleted) override;
1668	virtual void print_get_method(FunctionDecl *fd) override;
1669	};
1670
1671	/* Print a definition of the constructor "method" with signature "sig".
1672	*
1673	* Simply pass all arguments to the constructor of the corresponding
1674	* plain type.
1675	*/
1676	void template_cpp_generator::method_impl_printer::print_constructor_body(
1677	const Method &method, const Signature &sig)
1678	{
1679	const auto &base_name = instance.base_name();
1680
1681	os << " : " << base_name;
1682	method.print_cpp_arg_list(os, print_arg: [&] (int i, int arg) {
1683	os << method.fd->getParamDecl(i)->getName().str();
1684	});
1685	os << "\n";
1686
1687	os << "{\n";
1688	os << "}\n";
1689	}
1690
1691	/* Print the arguments of the callback function "callback" to "os",
1692	* calling "print_arg" with the type and the name of the arguments,
1693	* where the type is obtained from "type_printer" with argument positions
1694	* shifted by "shift".
1695	* None of the arguments should be skipped.
1696	*/
1697	static void print_callback_args(std::ostream &os,
1698	const FunctionProtoType *callback, const cpp_type_printer &type_printer,
1699	int shift,
1700	const std::function<void(const std::string &type,
1701	const std::string &name)> &print_arg)
1702	{
1703	auto n_arg = callback->getNumArgs() - 1;
1704
1705	Method::print_arg_list(os, start: 0, end: n_arg, print_arg_skip_next: [&] (int i) {
1706	auto type = callback->getArgType(i);
1707	auto name = "arg" + std::to_string(val: i);
1708	auto cpptype = type_printer.param(shift + i, type);
1709
1710	print_arg(cpptype, name);
1711
1712	return false;
1713	});
1714	}
1715
1716	/* Print a lambda corresponding to "callback"
1717	* with signature "sig" and argument positions shifted by "shift".
1718	*
1719	* The lambda takes arguments with plain isl types and
1720	* calls the callback of "method" with templated arguments.
1721	*/
1722	static void print_callback_lambda(std::ostream &os, ParmVarDecl *callback,
1723	const Signature &sig, int shift)
1724	{
1725	auto callback_type = callback->getType();
1726	auto callback_name = callback->getName().str();
1727	auto proto = generator::extract_prototype(callback_type);
1728
1729	os << " auto lambda_" << callback_name << " = [&] ";
1730	print_callback_args(os, proto, cpp_type_printer(), shift,
1731	[&] (const std::string &type, const std::string &name) {
1732	os << type << " " << name;
1733	});
1734	os << " {\n";
1735
1736	os << " return " << callback_name;
1737	print_callback_args(os, proto, template_cpp_arg_type_printer(sig),
1738	shift,
1739	[&] (const std::string &type, const std::string &name) {
1740	os << type << "(" << name << ")";
1741	});
1742	os << ";\n";
1743
1744	os << " };\n";
1745	}
1746
1747	/* Print lambdas for passing to the plain method corresponding to "method"
1748	* with signature "sig".
1749	*
1750	* The method is assumed to have only callbacks as argument,
1751	* which means the arguments of the first callback are shifted by 2
1752	* with respect to the arguments of the signature
1753	* (one for the position of the callback argument plus
1754	* one for the return kind of the callback).
1755	* The arguments of a subsequent callback are shifted by
1756	* the number of arguments of the previous callback minus one
1757	* for the user pointer plus one for the return kind.
1758	*/
1759	static void print_callback_lambdas(std::ostream &os, const Method &method,
1760	const Signature &sig)
1761	{
1762	int shift;
1763
1764	if (method.num_params() != 1 + 2 * method.callbacks.size())
1765	generator::die(msg: "callbacks are assumed to be only arguments");
1766
1767	shift = 2;
1768	for (const auto &callback : method.callbacks) {
1769	print_callback_lambda(os, callback, sig, shift);
1770	shift += generator::prototype_n_args(callback->getType());
1771	}
1772	}
1773
1774	/* Print a definition of the member method "method", which is known
1775	* to have a callback argument, with signature "sig".
1776	*
1777	* First print lambdas for passing to the corresponding plain method and
1778	* calling the callback of "method" with templated arguments.
1779	* Then call the plain method, replacing the original callbacks
1780	* by the lambdas.
1781	*
1782	* The return value is assumed to be isl_bool or isl_stat
1783	* so that no conversion to a template type is required.
1784	*/
1785	void template_cpp_generator::method_impl_printer::print_callback_method_body(
1786	const Method &method, const Signature &sig)
1787	{
1788	const auto &base_name = instance.base_name();
1789	auto return_type = method.fd->getReturnType();
1790
1791	if (!is_isl_bool(return_type) && !is_isl_stat(return_type))
1792	die(msg: "only isl_bool and isl_stat return types are supported");
1793
1794	os << "{\n";
1795
1796	print_callback_lambdas(os, method, sig);
1797
1798	os << " return ";
1799	os << base_name << "::" << method.name;
1800	method.print_cpp_arg_list(os, print_arg: [&] (int i, int arg) {
1801	auto param = method.fd->getParamDecl(i);
1802
1803	if (generator::is_callback(param->getType()))
1804	os << "lambda_";
1805	os << param->getName().str();
1806	});
1807	os << ";\n";
1808
1809	os << "}\n";
1810	}
1811
1812	/* Print a definition of the member or static method "method"
1813	* with signature "sig".
1814	*
1815	* The body calls the corresponding method of the base class
1816	* in the plain interface and
1817	* then casts the result to the templated result type.
1818	*/
1819	void template_cpp_generator::method_impl_printer::print_method_body(
1820	const Method &method, const Signature &sig)
1821	{
1822	const auto &base_name = instance.base_name();
1823
1824	os << "{\n";
1825	os << " auto res = ";
1826	os << base_name << "::" << method.name;
1827	method.print_cpp_arg_list(os, print_arg: [&] (int i, int arg) {
1828	os << method.fd->getParamDecl(i)->getName().str();
1829	});
1830	os << ";\n";
1831
1832	os << " return ";
1833	print_return_type(method, return_kind: sig.ret);
1834	os << "(res);\n";
1835	os << "}\n";
1836	}
1837
1838	/* Print a definition of the method "method" with signature "sig",
1839	* if "deleted" is not set.
1840	*
1841	* If "deleted" is set, then the corresponding declaration
1842	* is marked "delete" and no definition needs to be printed.
1843	*
1844	* Otherwise print the method header, preceded by the template parameters,
1845	* if needed.
1846	* The body depends on whether the method is a constructor or
1847	* takes any callbacks.
1848	*/
1849	void template_cpp_generator::method_impl_printer::print_method_sig(
1850	const Method &method, const Signature &sig, bool deleted)
1851	{
1852	if (deleted)
1853	return;
1854
1855	os << "\n";
1856	print_non_empty_template(os, params: instance.kind.params());
1857	print_method_header(method, sig);
1858	os << "\n";
1859	if (method.kind == Method::Kind::constructor)
1860	print_constructor_body(method, sig);
1861	else if (method.callbacks.size() != 0)
1862	print_callback_method_body(method, sig);
1863	else
1864	print_method_body(method, sig);
1865	}
1866
1867	/* Print a definition for the "get" method "fd" in class "clazz",
1868	* using a name that includes the "get_" prefix, to "os".
1869	*
1870	* The declarations of these methods are explicitly delete'd
1871	* so no definition needs to be printed.
1872	*/
1873	void template_cpp_generator::method_impl_printer::print_get_method(
1874	FunctionDecl *fd)
1875	{
1876	}
1877
1878	/* Print a declaration or definition of the static method "method",
1879	* if it has a signature specified by static_methods.
1880	*/
1881	void template_cpp_generator::class_printer::print_static_method(
1882	const Method &method)
1883	{
1884	print_special_method(method, special_methods: static_methods);
1885	}
1886
1887	/* Signatures for constructors of multi-expressions
1888	* from a space and a list.
1889	*/
1890	static Signature from_list_set = { .ret: { Domain }, .args: { { Domain }, { Anonymous } } };
1891	static Signature from_list_map =
1892	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Domain, Anonymous } } };
1893
1894	/* Signatures for constructors from a string.
1895	*/
1896	static Signature params_from_str = { .ret: { }, .args: { { Ctx }, { Str } } };
1897	static Signature set_from_str = { .ret: { Domain }, .args: { { Ctx }, { Str } } };
1898	static Signature map_from_str = { .ret: { Domain, Range }, .args: { { Ctx }, { Str } } };
1899	static std::vector<Signature> from_str =
1900	{ params_from_str, set_from_str, map_from_str };
1901
1902	/* Signature for a constructor from an integer.
1903	*/
1904	static Signature int_from_si = { .ret: { Anonymous }, .args: { { Ctx }, { Integer } } };
1905
1906	/* Signatures for constructors of lists from the initial number
1907	* of elements.
1908	*/
1909	static Signature alloc_params = { .ret: { }, .args: { { Ctx }, { Integer } } };
1910	static Signature alloc_set = { .ret: { Domain }, .args: { { Ctx }, { Integer } } };
1911	static Signature alloc_map = { .ret: { Domain, Range }, .args: { { Ctx }, { Integer } } };
1912
1913	/* Signatures for constructors and methods named after some other class.
1914	*
1915	* Two forms of constructors are handled
1916	* - conversion from another object
1917	* - construction of a multi-expression from a space and a list
1918	*
1919	* Methods named after some other class also come in two forms
1920	* - extraction of information such as the space or a list
1921	* - construction of a multi-expression from a space and a list
1922	*
1923	* In both cases, the first form is a unary operation and
1924	* the second has an extra argument with a kind that is equal
1925	* to that of the first argument, except that the final tuple is anonymous.
1926	*/
1927	static std::vector<Signature> constructor_sig = {
1928	un_params,
1929	un_set,
1930	un_map,
1931	from_list_set,
1932	from_list_map,
1933	};
1934
1935	/* Signatures for constructors derived from methods
1936	* with the given names that override the default signatures.
1937	*/
1938	static const std::unordered_map<std::string, std::vector<Signature>>
1939	special_constructors {
1940	{ "alloc", { alloc_params, alloc_set, alloc_map } },
1941	{ "int_from_si", { int_from_si } },
1942	{ "read_from_str", from_str },
1943	};
1944
1945	/* Print a declaration or definition of the constructor "method".
1946	*/
1947	void template_cpp_generator::class_printer::print_constructor(
1948	const Method &method)
1949	{
1950	if (special_constructors.count(x: method.name) != 0) {
1951	const auto &sigs = special_constructors.at(k: method.name);
1952	return print_matching_method(method, signatures: sigs);
1953	}
1954	print_matching_method(method, signatures: constructor_sig);
1955	}
1956
1957	/* Does this template class represent an anonymous function?
1958	*
1959	* If any specialization represents an anonymous function,
1960	* then every specialization does, so simply check
1961	* the first specialization.
1962	*/
1963	bool template_class::is_anon() const
1964	{
1965	return class_tuples[0].is_anon();
1966	}
1967
1968	/* Does this template class represent an anonymous value?
1969	*
1970	* That is, is there only a single specialization that moreover
1971	* has a single, anonymous tuple?
1972	*/
1973	bool template_class::is_anon_set() const
1974	{
1975	return class_tuples.size() == 1 && class_tuples[0].is_anon_set();
1976	}
1977
1978	/* Update the substitution "sub" to map "general" to "specific"
1979	* if "specific" is a special case of "general" consistent with "sub",
1980	* given that "general" is not a pair and can be assigned "specific".
1981	* Return true if successful.
1982	* Otherwise, return false.
1983	*
1984	* Check whether "general" is already assigned something in "sub".
1985	* If so, it must be assigned "specific".
1986	* Otherwise, there is a conflict.
1987	*/
1988	static bool update_sub_base(Substitution &sub, const TupleKindPtr &general,
1989	const TupleKindPtr &specific)
1990	{
1991	auto name = general->name;
1992
1993	if (sub.count(x: name) != 0 && sub.at(k: name) != specific)
1994	return false;
1995	sub.emplace(args&: name, args: specific);
1996	return true;
1997	}
1998
1999	/* Update the substitution "sub" to map "general" to "specific"
2000	* if "specific" is a special case of "general" consistent with "sub".
2001	* Return true if successful.
2002	* Otherwise, return false.
2003	*
2004	* If "general" is a pair and "specific" is not,
2005	* then "specific" cannot be a special case.
2006	* If both are pairs, then update the substitution based
2007	* on both sides.
2008	* If "general" is Anonymous, then "specific" must be Anonymous as well.
2009	* If "general" is Leaf, then "specific" cannot be a pair.
2010	*
2011	* Otherwise, assign "specific" to "general", if possible.
2012	*/
2013	static bool update_sub(Substitution &sub, const TupleKindPtr &general,
2014	const TupleKindPtr &specific)
2015	{
2016	if (general->left() && !specific->left())
2017	return false;
2018	if (general->left())
2019	return update_sub(sub, general: general->left(), specific: specific->left()) &&
2020	update_sub(sub, general: general->right(), specific: specific->right());
2021	if (general == Anonymous && specific != Anonymous)
2022	return false;
2023	if (general == Leaf && specific->left())
2024	return false;
2025
2026	return update_sub_base(sub, general, specific);
2027	}
2028
2029	/* Check if "specific" is a special case of "general" and,
2030	* if so, return true along with a substitution
2031	* that maps "general" to "specific".
2032	* Otherwise return false.
2033	*
2034	* This can only happen if the number of tuple kinds is the same.
2035	* If so, start with an empty substitution and update it
2036	* for each pair of tuple kinds, checking that each update succeeds.
2037	*/
2038	static std::pair<bool, Substitution> specializer(const Kind &general,
2039	const Kind &specific)
2040	{
2041	Substitution specializer;
2042
2043	if (general.size() != specific.size())
2044	return { false, Substitution() };
2045
2046	for (size_t i = 0; i < general.size(); ++i) {
2047	auto general_tuple = general[i];
2048
2049	if (!update_sub(sub&: specializer, general: general[i], specific: specific[i]))
2050	return { false, Substitution() };
2051	}
2052
2053	return { true, specializer };
2054	}
2055
2056	/* Is "kind1" equivalent to "kind2"?
2057	* That is, is each a special case of the other?
2058	*/
2059	static bool equivalent(const Kind &kind1, const Kind &kind2)
2060	{
2061	return specializer(general: kind1, specific: kind2).first &&
2062	specializer(general: kind2, specific: kind1).first;
2063	}
2064
2065	/* Add the specialization "kind" to the sequence of specializations,
2066	* provided there is no equivalent specialization already in there.
2067	*/
2068	void template_class::add_specialization(const Kind &kind)
2069	{
2070	for (const auto &special : class_tuples)
2071	if (equivalent(kind1: special, kind2: kind))
2072	return;
2073	class_tuples.emplace_back(args: kind);
2074	}
2075
2076	/* A type printer that prints the plain interface type,
2077	* without namespace.
2078	*/
2079	struct plain_cpp_type_printer : public cpp_type_printer {
2080	plain_cpp_type_printer() {}
2081
2082	virtual std::string qualified(int arg, const std::string &cpp_type)
2083	const override;
2084	};
2085
2086	/* Return the qualified form of the given C++ isl type name appearing
2087	* in argument position "arg" (-1 for return type).
2088	*
2089	* For printing the plain type without namespace, no modifications
2090	* are required.
2091	*/
2092	std::string plain_cpp_type_printer::qualified(int arg,
2093	const std::string &cpp_type) const
2094	{
2095	return cpp_type;
2096	}
2097
2098	/* Return a string representation of the plain type "type".
2099	*
2100	* For the plain printer, the argument position is irrelevant,
2101	* so simply pass in -1.
2102	*/
2103	static std::string plain_type(QualType type)
2104	{
2105	return plain_cpp_type_printer().param(-1, type);
2106	}
2107
2108	/* Return a string representation of the plain return type of "method".
2109	*/
2110	static std::string plain_return_type(const Method &method)
2111	{
2112	return plain_type(method.fd->getReturnType());
2113	}
2114
2115	/* Return that part of the signature "sig" that should match
2116	* the template class specialization for the given method.
2117	*
2118	* In particular, if the method is a regular member method,
2119	* then the instance should match the first argument.
2120	* Otherwise, it should match the return kind.
2121	*/
2122	static const Kind &matching_kind(const Method &method, const Signature &sig)
2123	{
2124	if (method.kind == Method::Kind::member_method)
2125	return sig.args[0];
2126	else
2127	return sig.ret;
2128	}
2129
2130	/* Is it possible for "template_class" to have the given kind?
2131	*
2132	* If the template class represents an anonymous function,
2133	* then so must the given kind.
2134	* There should also be specialization with the same number of tuple kinds.
2135	*/
2136	static bool has_kind(const template_class &template_class, const Kind &kind)
2137	{
2138	if (template_class.is_anon() && !kind.is_anon())
2139	return false;
2140	for (const auto &class_tuple : template_class.class_tuples)
2141	if (class_tuple.size() == kind.size())
2142	return true;
2143	return false;
2144	}
2145
2146	/* Is "return_kind" a possible kind for the return type of "method"?
2147	*
2148	* If the return type is not a template class,
2149	* then "return_kind" should not have any template parameters.
2150	* Otherwise, "return_kind" should be a valid kind for the template class.
2151	*/
2152	bool template_cpp_generator::class_printer::is_return_kind(
2153	const Method &method, const Kind &return_kind)
2154	{
2155	const auto &template_classes = generator.template_classes;
2156	auto return_type = plain_return_type(method);
2157
2158	if (template_classes.count(x: return_type) == 0)
2159	return return_kind.params().size() == 0;
2160	return has_kind(template_class: template_classes.at(k: return_type), kind: return_kind);
2161	}
2162
2163	/* Is "kind" a placeholder that can be assigned something else
2164	* in a substitution?
2165	*
2166	* Anonymous can only be mapped to itself. This is taken care of
2167	* by assign().
2168	* Leaf can only be assigned a placeholder, but there is no need
2169	* to handle this specifically since Leaf can still be assigned
2170	* to the placeholder.
2171	*/
2172	static bool assignable(const TupleKindPtr &kind)
2173	{
2174	return kind != Anonymous && kind != Leaf;
2175	}
2176
2177	/* Return a substitution that maps "kind1" to "kind2", if possible.
2178	* Otherwise return an empty substitution.
2179	*
2180	* Check if "kind1" can be assigned anything or
2181	* if "kind1" and "kind2" are identical.
2182	* The latter case handles mapping Anonymous to itself.
2183	*/
2184	static Substitution assign(const TupleKindPtr &kind1, const TupleKindPtr &kind2)
2185	{
2186	Substitution res;
2187
2188	if (assignable(kind: kind1) || kind1 == kind2)
2189	res.emplace(args: kind1->name, args: kind2);
2190	return res;
2191	}
2192
2193	/* Return a substitution that first applies "first" and then "second".
2194	*
2195	* The result consists of "second" and of "second" applied to "first".
2196	*/
2197	static Substitution compose(const Substitution &first,
2198	const Substitution &second)
2199	{
2200	Substitution res = second;
2201
2202	for (const auto &kvp : first)
2203	res.emplace(args: kvp.first, args: apply(tuple: kvp.second, subs: second));
2204
2205	return res;
2206	}
2207
2208	static Substitution compute_unifier(const TupleKindPtr &kind1,
2209	const TupleKindPtr &kind2);
2210
2211	/* Try and extend "unifier" with a unifier for "kind1" and "kind2".
2212	* Return the resulting unifier if successful.
2213	* Otherwise, return an empty substitution.
2214	*
2215	* First apply "unifier" to "kind1" and "kind2".
2216	* Then compute a unifier for the resulting tuple kinds and
2217	* combine it with "unifier".
2218	*/
2219	static Substitution combine_unifiers(const TupleKindPtr &kind1,
2220	const TupleKindPtr &kind2, const Substitution &unifier)
2221	{
2222	auto k1 = apply(tuple: kind1, subs: unifier);
2223	auto k2 = apply(tuple: kind2, subs: unifier);
2224	auto u = compute_unifier(kind1: k1, kind2: k2);
2225	if (u.size() == 0)
2226	return Substitution();
2227	return compose(first: unifier, second: u);
2228	}
2229
2230	/* Try and compute a unifier of "kind1" and "kind2",
2231	* i.e., a substitution that produces the same result when
2232	* applied to both "kind1" and "kind2",
2233	* for the case where both "kind1" and "kind2" are pairs.
2234	* Return this unifier if it was found.
2235	* Return an empty substitution if no unifier can be found.
2236	*
2237	* First compute a unifier for the left parts of the pairs and,
2238	* if successful, combine it with a unifier for the right parts.
2239	*/
2240	static Substitution compute_pair_unifier(const TupleKindPtr &kind1,
2241	const TupleKindPtr &kind2)
2242	{
2243	auto unifier_left = compute_unifier(kind1: kind1->left(), kind2: kind2->left());
2244	if (unifier_left.size() == 0)
2245	return Substitution();
2246	return combine_unifiers(kind1: kind1->right(), kind2: kind2->right(), unifier: unifier_left);
2247	}
2248
2249	/* Try and compute a unifier of "kind1" and "kind2",
2250	* i.e., a substitution that produces the same result when
2251	* applied to both "kind1" and "kind2".
2252	* Return this unifier if it was found.
2253	* Return an empty substitution if no unifier can be found.
2254	*
2255	* If one of the tuple kinds is a pair then assign it
2256	* to the other tuple kind, if possible.
2257	* If neither is a pair, then try and assign one to the other.
2258	* Otherwise, let compute_pair_unifier compute a unifier.
2259	*
2260	* Note that an assignment is added to the unifier even
2261	* if "kind1" and "kind2" are identical.
2262	* This ensures that a successful substitution is never empty.
2263	*/
2264	static Substitution compute_unifier(const TupleKindPtr &kind1,
2265	const TupleKindPtr &kind2)
2266	{
2267	if (kind1->left() && !kind2->left())
2268	return assign(kind1: kind2, kind2: kind1);
2269	if (!kind1->left() && kind2->left())
2270	return assign(kind1, kind2);
2271	if (!kind1->left() && !kind2->left()) {
2272	if (assignable(kind: kind1))
2273	return assign(kind1, kind2);
2274	else
2275	return assign(kind1: kind2, kind2: kind1);
2276	}
2277
2278	return compute_pair_unifier(kind1, kind2);
2279	}
2280
2281	/* Try and compute a unifier of "kind1" and "kind2",
2282	* i.e., a substitution that produces the same result when
2283	* applied to both "kind1" and "kind2".
2284	* Return this unifier if it was found.
2285	* Return an empty substitution if no unifier can be found.
2286	*
2287	* Start with an empty substitution and compute a unifier for
2288	* each pair of tuple kinds, combining the results.
2289	* If no combined unifier can be found or
2290	* if the numbers of tuple kinds are different, then return
2291	* an empty substitution.
2292	* This assumes that the number of tuples is greater than zero,
2293	* as otherwise an empty substitution would be returned as well.
2294	*/
2295	static Substitution compute_unifier(const Kind &kind1, const Kind &kind2)
2296	{
2297	Substitution unifier;
2298
2299	if (kind1.size() != kind2.size())
2300	return Substitution();
2301
2302	for (size_t i = 0; i < kind1.size(); ++i)
2303	unifier = combine_unifiers(kind1: kind1[i], kind2: kind2[i], unifier);
2304
2305	return unifier;
2306	}
2307
2308	/* Try and construct a Kind that is a specialization of both "general" and
2309	* "specific", where "specific" is known _not_ to be a specialization
2310	* of "general" and not to contain any Leaf.
2311	*
2312	* First check whether "general" is a specialization of "specific".
2313	* If so, simply return "general".
2314	* Otherwise, rename the placeholders in the two kinds apart and
2315	* try and compute a unifier.
2316	* If this succeeds, then return the result of applying the unifier.
2317	*/
2318	static std::pair<bool, Kind> unify(const Kind &general, const Kind &specific)
2319	{
2320	if (specializer(general: specific, specific: general).first) {
2321	return { true, general };
2322	} else {
2323	auto rename = param_renamer(params: specific.params(), prefix: "T");
2324	auto renamed = specific.apply(subs: rename);
2325	auto unifier = compute_unifier(kind1: general, kind2: renamed);
2326
2327	if (unifier.size() == 0)
2328	return { false, { } };
2329
2330	return { true, general.apply(subs: unifier) };
2331	}
2332	}
2333
2334	/* Try and add a template class specialization corresponding to "kind".
2335	* The new specialization needs to be a specialization of both
2336	* the current specialization and "kind".
2337	*
2338	* The current template class specialization is known not to be a special case
2339	* of "kind".
2340	*
2341	* Try and unify the two kinds and, if this succeeds, add the result
2342	* to this list of template class specializations.
2343	*/
2344	void template_cpp_generator::class_printer::add_specialization(
2345	const Kind &kind)
2346	{
2347	auto maybe_unified = unify(general: kind, specific: instance.kind);
2348
2349	if (!maybe_unified.first)
2350	return;
2351	instance.template_class.add_specialization(kind: maybe_unified.second);
2352	}
2353
2354	/* Does the type of the parameter at position "i" of "method" necessarily
2355	* have a final Anonymous tuple?
2356	*
2357	* If the parameter is not of an isl type or if no specializations
2358	* have been defined for the type, then it can be considered anonymous.
2359	* Otherwise, if any specialization represents an anonymous function,
2360	* then every specialization does, so simply check
2361	* the first specialization.
2362	*/
2363	static bool param_is_anon(const Method &method, int i)
2364	{
2365	ParmVarDecl *param = method.get_param(i);
2366	QualType type = param->getOriginalType();
2367
2368	if (cpp_generator::is_isl_type(type)) {
2369	const auto &name = type->getPointeeType().getAsString();
2370	const auto &cpp = cpp_generator::type2cpp(name);
2371	const auto &tuples = lookup_class_tuples(cpp);
2372
2373	if (tuples.empty())
2374	return true;
2375	return tuples[0].is_anon();
2376	}
2377
2378	return true;
2379	}
2380
2381	/* Replace the final tuple of "arg_kind" by Anonymous in "sig" and
2382	* return the update signature,
2383	* unless this would affect the class instance "instance_kind".
2384	*
2385	* If the original "instance_kind" is a special case
2386	* of the result of the substitution, then "instance_kind"
2387	* is not affected and the substitution can be applied
2388	* to the entire signature.
2389	*/
2390	static Signature specialize_anonymous_arg(const Signature &sig,
2391	const Kind &arg_kind, const Kind &instance_kind)
2392	{
2393	const auto &subs = compute_unifier(kind1: arg_kind.back(), kind2: Anonymous);
2394	const auto &specialized_instance = instance_kind.apply(subs);
2395
2396	if (!specializer(general: specialized_instance, specific: instance_kind).first)
2397	return sig;
2398
2399	return sig.apply(subs);
2400	}
2401
2402	/* If any of the arguments of "method" is of a type that necessarily
2403	* has a final Anonymous tuple, but the corresponding entry
2404	* in the signature "sig" is not Anonymous, then replace
2405	* that entry by Anonymous and return the updated signature,
2406	* unless this would affect the class instance "instance_kind".
2407	*/
2408	static Signature specialize_anonymous_args(const Signature &sig,
2409	const Method &method, const Kind &instance_kind)
2410	{
2411	auto specialized_sig = sig;
2412
2413	method.on_cpp_arg_list(on_arg: [&] (int i, int arg) {
2414	const auto &arg_kind = sig.args[arg];
2415
2416	if (arg_kind.is_anon())
2417	return;
2418	if (!param_is_anon(method, i))
2419	return;
2420	specialized_sig = specialize_anonymous_arg(sig: specialized_sig,
2421	arg_kind, instance_kind);
2422	});
2423
2424	return specialized_sig;
2425	}
2426
2427	/* Print a declaration or definition of the method "method"
2428	* if the template class specialization matches "match_arg".
2429	* Return true if so.
2430	* "sig" is the complete signature, of which "match_arg" refers
2431	* to the first argument or the return type.
2432	*
2433	* Since "sig" may have parameters with the same names as
2434	* those in instance.kind, rename them apart first.
2435	*
2436	* If the template class specialization is a special case of
2437	* (the renamed) "match_arg"
2438	* then apply the specializer to the complete (renamed) signature,
2439	* specialize any anonymous arguments,
2440	* check that the return kind is allowed and, if so,
2441	* print the declaration or definition using the specialized signature.
2442	*
2443	* If the template class specialization is not a special case of "match_arg"
2444	* then add a further specialization to the list of specializations
2445	* of the template class.
2446	*/
2447	bool template_cpp_generator::class_printer::print_matching_method(
2448	const Method &method, const Signature &sig, const Kind &match_arg)
2449	{
2450	auto rename = shared_param_renamer(sig, kind: instance.kind);
2451	auto renamed_arg = match_arg.apply(subs: rename);
2452	auto maybe_specializer = specializer(general: renamed_arg, specific: instance.kind);
2453	if (maybe_specializer.first) {
2454	const auto &specializer = maybe_specializer.second;
2455	auto specialized_sig = sig.apply(subs: rename).apply(subs: specializer);
2456	specialized_sig = specialize_anonymous_args(sig: specialized_sig,
2457	method, instance_kind: instance.kind);
2458	if (!is_return_kind(method, return_kind: specialized_sig.ret))
2459	return false;
2460
2461	print_method_sig(method, sig: specialized_sig, deleted: false);
2462	} else {
2463	add_specialization(kind: match_arg);
2464	}
2465	return maybe_specializer.first;
2466	}
2467
2468	/* Is the first argument of "method" of type "isl_ctx *"?
2469	*/
2470	static bool first_arg_is_ctx(const Method &method)
2471	{
2472	return generator::first_arg_is_isl_ctx(method.fd);
2473	}
2474
2475	/* Is the first signature argument set to { Ctx }?
2476	*/
2477	static bool first_kind_is_ctx(const Signature &sig)
2478	{
2479	return sig.args[0].size() > 0 && sig.args[0][0] == Ctx;
2480	}
2481
2482	/* Print a declaration or definition of the member method "method"
2483	* if it matches the signature "sig".
2484	* Return true if so.
2485	*
2486	* First determine the part of the signature that needs to match
2487	* the template class specialization and
2488	* check that it has the same number of template arguments.
2489	* Also check that the number of arguments of the signature
2490	* matches that of the method.
2491	* If there is at least one argument, then check that the first method argument
2492	* is an isl_ctx if and only if the first signature argument is Ctx.
2493	*
2494	* If these tests succeed, proceed with the actual matching.
2495	*/
2496	bool template_cpp_generator::class_printer::print_matching_method(
2497	const Method &method, const Signature &sig)
2498	{
2499	auto match_arg = matching_kind(method, sig);
2500	int n_args = sig.args.size();
2501
2502	if (match_arg.size() != instance.kind.size())
2503	return false;
2504	if (n_args != total_params(method))
2505	return false;
2506	if (n_args > 0 && first_arg_is_ctx(method) != first_kind_is_ctx(sig))
2507	return false;
2508
2509	return print_matching_method(method, sig, match_arg);
2510	}
2511
2512	/* Print a declaration or definition of the member method "method"
2513	* for each matching signature in "signatures".
2514	*
2515	* If there is no matching signature in "signatures",
2516	* then explicitly delete the method (using a signature based on
2517	* the specialization) so that it is not inherited from the base class.
2518	*/
2519	void template_cpp_generator::class_printer::print_matching_method(
2520	const Method &method, const std::vector<Signature> &signatures)
2521	{
2522	auto any = false;
2523
2524	for (const auto &sig : signatures)
2525	if (print_matching_method(method, sig))
2526	any = true;
2527
2528	if (!any)
2529	print_method_sig(method, sig: instance_sig(method, instance), deleted: true);
2530	}
2531
2532	/* Signatures for "at" methods applied to a multi-expression,
2533	* which make the final tuple anonymous.
2534	*/
2535	static Signature select_set = { .ret: { Anonymous }, .args: { { Domain }, { Integer } } };
2536	static Signature select_map =
2537	{ .ret: { Domain, Anonymous }, .args: { { Domain, Range }, { Integer } } };
2538	static std::vector<Signature> at_select = { select_set, select_map };
2539
2540	/* Signatures for other "at" methods applied to a list,
2541	* which do not modify the tuple kind.
2542	*/
2543	static Signature bin_set_int = { .ret: { Domain }, .args: { { Domain }, { Integer } } };
2544	static Signature bin_map_int =
2545	{ .ret: { Domain, Range }, .args: { { Domain, Range }, { Integer } } };
2546	static std::vector<Signature> at_keep = { bin_set_int, bin_map_int };
2547
2548	/* Print a declaration or definition of the "at" member method "method".
2549	*
2550	* There are two types of methods called "at".
2551	* One type extracts an element from a multi-expression and
2552	* the other extracts an element from a list.
2553	*
2554	* In the first case, the return type is an anonymous function
2555	* while the object type is not. In this case, the return kind
2556	* should have a final Anonymous tuple.
2557	* Otherwise, the return kind should be the same as the object kind.
2558	*/
2559	void template_cpp_generator::class_printer::print_at_method(
2560	const Method &method)
2561	{
2562	auto anon = instance.template_class.is_anon();
2563	auto return_type = plain_return_type(method);
2564	auto return_class = generator.template_classes.at(k: return_type);
2565
2566	if (!anon && return_class.is_anon())
2567	return print_matching_method(method, signatures: at_select);
2568	else
2569	return print_matching_method(method, signatures: at_keep);
2570	}
2571
2572	/* Does the string "s" contain "sub" as a substring?
2573	*/
2574	static bool contains(const std::string &s, const std::string &sub)
2575	{
2576	return s.find(str: sub) != std::string::npos;
2577	}
2578
2579	/* Print a declaration or definition of the member method "method",
2580	* if it has a special signature in "special_methods".
2581	* Return true if this is the case.
2582	*
2583	* Check if any special signatures are specified for this method and
2584	* if the class name matches any of those with special signatures.
2585	* If so, pick the one with the best match, i.e., the first match
2586	* since the largest keys appear first.
2587	*/
2588	bool template_cpp_generator::class_printer::print_special_method(
2589	const Method &method, const infix_map_map &special_methods)
2590	{
2591	if (special_methods.count(x: method.name) == 0)
2592	return false;
2593
2594	for (const auto &kvp : special_methods.at(k: method.name)) {
2595	if (!contains(s: instance.template_class.class_name, sub: kvp.first))
2596	continue;
2597	print_matching_method(method, signatures: kvp.second);
2598	return true;
2599	}
2600
2601	return false;
2602	}
2603
2604	/* Print a declaration or definition of the member method "method",
2605	* if it has a special signature specified by special_member_methods.
2606	* Return true if this is the case.
2607	*/
2608	bool template_cpp_generator::class_printer::print_special_member_method(
2609	const Method &method)
2610	{
2611	return print_special_method(method, special_methods: special_member_methods);
2612	}
2613
2614	/* Print a declaration or definition of the member method "method",
2615	* if it is named after a template class. Return true if this is the case.
2616	*/
2617	bool template_cpp_generator::class_printer::print_type_named_member_method(
2618	const Method &method)
2619	{
2620	if (generator.template_classes.count(x: method.name) == 0)
2621	return false;
2622
2623	print_matching_method(method, signatures: constructor_sig);
2624
2625	return true;
2626	}
2627
2628	/* Print a declaration or definition of the member method "method"
2629	* using a signature associated to method name "name", if there is any.
2630	* Return true if this is the case.
2631	*/
2632	bool template_cpp_generator::class_printer::print_member_method_with_name(
2633	const Method &method, const std::string &name)
2634	{
2635	if (member_methods.count(x: name) == 0)
2636	return false;
2637
2638	print_matching_method(method, signatures: member_methods.at(k: name));
2639	return true;
2640	}
2641
2642	/* If "sub" appears inside "str", then remove the first occurrence and
2643	* return the result. Otherwise, simply return "str".
2644	*/
2645	static std::string drop_occurrence(const std::string &str,
2646	const std::string &sub)
2647	{
2648	auto res = str;
2649	auto pos = str.find(str: sub);
2650
2651	if (pos != std::string::npos)
2652	res.erase(pos: pos, n: sub.length());
2653
2654	return res;
2655	}
2656
2657	/* If "sub" appears in "str" next to an underscore, then remove the combination.
2658	* Otherwise, simply return "str".
2659	*/
2660	static std::string drop_underscore_occurrence(const std::string &str,
2661	const std::string &sub)
2662	{
2663	auto res = drop_occurrence(str, sub: sub + "_");
2664	if (res != str)
2665	return res;
2666	return drop_occurrence(str: res, sub: std::string("_") + sub);
2667	}
2668
2669	/* Return the name of "method", with the name of the return type,
2670	* along with an underscore, removed, if this combination appears in the name.
2671	* Otherwise, simply return the name.
2672	*/
2673	const std::string name_without_return(const Method &method)
2674	{
2675	auto return_infix = plain_return_type(method);
2676	return drop_underscore_occurrence(str: method.name, sub: return_infix);
2677	}
2678
2679	/* If this method has a callback, then remove the type
2680	* of the first argument of the first callback from the name of the method.
2681	* Otherwise, simply return the name of the method.
2682	*/
2683	const std::string callback_name(const Method &method)
2684	{
2685	if (method.callbacks.size() == 0)
2686	return method.name;
2687
2688	auto type = method.callbacks.at(0)->getType();
2689	auto callback = cpp_generator::extract_prototype(type);
2690	auto arg_type = plain_type(callback->getArgType(0));
2691	return generator::drop_suffix(s: method.name, suffix: "_" + arg_type);
2692	}
2693
2694	/* Print a declaration or definition of the member method "method".
2695	*
2696	* If the method is called "at", then it requires special treatment.
2697	* Otherwise, check if the signature is overridden for this class or
2698	* if the method is named after some other type.
2699	* Otherwise look for an appropriate signature using different variations
2700	* of the method name. First try the method name itself,
2701	* then the method name with the return type removed and
2702	* finally the method name with the callback argument type removed.
2703	*/
2704	void template_cpp_generator::class_printer::print_member_method(
2705	const Method &method)
2706	{
2707	if (method.name == "at")
2708	return print_at_method(method);
2709	if (print_special_member_method(method))
2710	return;
2711	if (print_type_named_member_method(method))
2712	return;
2713	if (print_member_method_with_name(method, name: method.name))
2714	return;
2715	if (print_member_method_with_name(method, name: name_without_return(method)))
2716	return;
2717	if (print_member_method_with_name(method, name: callback_name(method)))
2718	return;
2719	}
2720
2721	/* Print a declaration or definition of "method" based on its type.
2722	*/
2723	void template_cpp_generator::class_printer::print_any_method(
2724	const Method &method)
2725	{
2726	switch (method.kind) {
2727	case Method::Kind::static_method:
2728	print_static_method(method);
2729	break;
2730	case Method::Kind::constructor:
2731	print_constructor(method);
2732	break;
2733	case Method::Kind::member_method:
2734	print_member_method(method);
2735	break;
2736	}
2737	}
2738
2739	/* Print a declaration or definition of "method".
2740	*
2741	* Mark the method as not requiring copies of the arguments.
2742	*/
2743	void template_cpp_generator::class_printer::print_method(const Method &method)
2744	{
2745	print_any_method(NoCopyMethod(method));
2746	}
2747
2748	/* Print a declaration or definition of "method".
2749	*
2750	* Note that a ConversionMethod is already marked
2751	* as not requiring copies of the arguments.
2752	*/
2753	void template_cpp_generator::class_printer::print_method(
2754	const ConversionMethod &method)
2755	{
2756	print_any_method(method);
2757	}
2758
2759	/* Helper class for printing the declarations for
2760	* template class specializations.
2761	*/
2762	struct template_cpp_generator::class_decl_printer :
2763	public specialization_printer
2764	{
2765	class_decl_printer(std::ostream &os,
2766	template_cpp_generator &generator) :
2767	specialization_printer(os, generator) {}
2768
2769	void print_arg_subclass_constructor(const specialization &instance,
2770	const std::vector<std::string> &params) const;
2771	void print_super_constructor(const specialization &instance) const;
2772	virtual void print_class(const specialization &instance) const override;
2773	};
2774
2775	/* Print the declaration and definition of a constructor
2776	* for the template class specialization "instance" taking
2777	* an instance with more specialized template arguments,
2778	* where "params" holds the template parameters of "instance".
2779	* It is assumed that there is at least one template parameter as otherwise
2780	* there are no template arguments to be specialized and
2781	* no constructor needs to be printed.
2782	*
2783	* In particular, the constructor takes an object of the same instance where
2784	* for each template parameter, the corresponding template argument
2785	* of the input object is a subclass of the template argument
2786	* of the constructed object.
2787	*
2788	* Pick fresh names for all template parameters and
2789	* add a constructor with these fresh names as extra template parameters and
2790	* a constraint requiring that each of them is a subclass
2791	* of the corresponding class template parameter.
2792	* The plain C++ interface object of the constructed object is initialized with
2793	* the plain C++ interface object of the constructor argument.
2794	*/
2795	void template_cpp_generator::class_decl_printer::print_arg_subclass_constructor(
2796	const specialization &instance,
2797	const std::vector<std::string> &params) const
2798	{
2799	const auto &class_name = instance.class_name();
2800	auto rename = param_renamer(params, prefix: "Arg");
2801	auto derived = instance.kind.apply(subs: rename);
2802
2803	os << " template ";
2804	os << "<";
2805	print_pure_template_args(os, args: derived.params());
2806	os << ",\n";
2807	os << " typename std::enable_if<\n";
2808	for (size_t i = 0; i < params.size(); ++i) {
2809	if (i != 0)
2810	os << " &&\n";
2811	os << " std::is_base_of<"
2812	<< params[i] << ", "
2813	<< rename.at(k: params[i])->params()[0] << ">{}";
2814	}
2815	os << ",\n";
2816	os << " bool>::type = true>";
2817	os << "\n";
2818	os << " " << class_name << "(const ";
2819	print_bare_template_type(os, type: class_name, kind: derived);
2820	os << " &obj) : " << instance.base_name() << "(obj) {}\n";
2821	}
2822
2823	/* Print the declaration and definition of a constructor
2824	* for the template class specialization "instance" taking
2825	* an instance of the base class.
2826	*
2827	* If the instance kind is that of an anonymous set
2828	* (i.e., it has a single tuple that is set to Anonymous),
2829	* then allow the constructor to be called externally.
2830	* This is mostly useful for being able to use isl::val and
2831	* isl::typed::val<Anonymous> interchangeably and similarly for isl::id.
2832	*
2833	* If the instance is of any other kind, then make this constructor private
2834	* to avoid objects of the plain interface being converted automatically.
2835	* Also make sure that it does not apply to any type derived
2836	* from the base class. In particular, this makes sure it does
2837	* not apply to any other specializations of this template class as
2838	* otherwise any conflict in specializations would simply point
2839	* to the private constructor.
2840	*
2841	* A factory method is added to be able to perform the conversion explicitly,
2842	* with an explicit specification of the template arguments.
2843	*/
2844	void template_cpp_generator::class_decl_printer::print_super_constructor(
2845	const specialization &instance) const
2846	{
2847	bool hide = !instance.kind.is_anon_set();
2848	const auto &base_name = instance.base_name();
2849	const auto &arg_name = hide ? "base" : base_name;
2850
2851	if (hide) {
2852	os << " private:\n";
2853	os << " template <typename base,\n";
2854	os << " typename std::enable_if<\n";
2855	os << " std::is_same<base, " << base_name
2856	<< ">{}, bool>::type = true>\n";
2857	}
2858	os << " " << instance.class_name()
2859	<< "(const " << arg_name << " &obj) : "
2860	<< base_name << "(obj) {}\n";
2861	if (hide)
2862	os << " public:\n";
2863	os << " static " << instance.class_name() << " from"
2864	<< "(const " << base_name << " &obj) {\n";
2865	os << " return " << instance.class_name() << "(obj);\n";
2866	os << " }\n";
2867	}
2868
2869	/* Print a "declaration" for the given template class specialization.
2870	* In particular, print the class definition and the method declarations.
2871	*
2872	* The template parameters are the distinct variable names
2873	* in the instance kind.
2874	*
2875	* Each instance of the template class derives from the corresponding
2876	* plain C++ interface class.
2877	*
2878	* All (other) template classes are made friends of this template class
2879	* to allow them to call the private constructor taking an object
2880	* of the plain interface.
2881	*
2882	* Besides the constructors and methods that forward
2883	* to the corresponding methods in the plain C++ interface class,
2884	* some extra constructors are defined.
2885	* The default zero-argument constructor is useful for declaring
2886	* a variable that only gets assigned a value at a later stage.
2887	* The constructor taking an instance with more specialized
2888	* template arguments is useful for lifting the class hierarchy
2889	* of the template arguments to the template class.
2890	* The constructor taking an instance of the base class
2891	* is useful for (explicitly) constructing a template type
2892	* from a plain type.
2893	*/
2894	void template_cpp_generator::class_decl_printer::print_class(
2895	const specialization &instance) const
2896	{
2897	const auto &class_name = instance.class_name();
2898	auto params = instance.kind.params();
2899
2900	os << "\n";
2901
2902	print_template(os, params);
2903
2904	os << "struct ";
2905	print_bare_template_type(os, type: class_name, kind: instance.kind);
2906	os << " : public " << instance.base_name() << " {\n";
2907
2908	generator.print_friends(os);
2909	os << "\n";
2910
2911	os << " " << class_name << "() = default;\n";
2912	if (params.size() != 0)
2913	print_arg_subclass_constructor(instance, params);
2914	print_super_constructor(instance);
2915	method_decl_printer(instance, *this).print_all_methods();
2916
2917	os << "};\n";
2918	}
2919
2920	/* Helper class for printing the definitions of template class specializations.
2921	*/
2922	struct template_cpp_generator::class_impl_printer :
2923	public specialization_printer
2924	{
2925	class_impl_printer(std::ostream &os,
2926	template_cpp_generator &generator) :
2927	specialization_printer(os, generator) {}
2928
2929	virtual void print_class(const specialization &instance) const override;
2930	};
2931
2932	/* Print a definition for the given template class specialization.
2933	*
2934	* In particular, print definitions
2935	* for the constructors and methods that forward
2936	* to the corresponding methods in the plain C++ interface class.
2937	* The extra constructors declared in the class definition
2938	* are defined inline.
2939	*/
2940	void template_cpp_generator::class_impl_printer::print_class(
2941	const specialization &instance) const
2942	{
2943	method_impl_printer(instance, *this).print_all_methods();
2944	}
2945
2946	/* Generate a templated cpp interface
2947	* based on the extracted types and functions.
2948	*
2949	* First print forward declarations for all template classes,
2950	* then the declarations of the classes, and at the end all
2951	* method implementations.
2952	*/
2953	void template_cpp_generator::generate()
2954	{
2955	ostream &os = std::cout;
2956
2957	os << "\n";
2958
2959	print_forward_declarations(os);
2960	class_decl_printer(os, *this).print_classes();
2961	class_impl_printer(os, *this).print_classes();
2962	}
2963