2963 lines · plain
1/*2 * Copyright 2020 Cerebras Systems. All rights reserved.3 *4 * Redistribution and use in source and binary forms, with or without5 * modification, are permitted provided that the following conditions6 * are met:7 *8 * 1. Redistributions of source code must retain the above copyright9 * notice, this list of conditions and the following disclaimer.10 *11 * 2. Redistributions in binary form must reproduce the above12 * copyright notice, this list of conditions and the following13 * disclaimer in the documentation and/or other materials provided14 * with the distribution.15 *16 * THIS SOFTWARE IS PROVIDED BY CEREBRAS SYSTEMS ''AS IS'' AND ANY17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CEREBRAS SYSTEMS OR20 * 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 ANY24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.27 *28 * The views and conclusions contained in the software and documentation29 * are those of the authors and should not be interpreted as30 * representing official policies, either expressed or implied, of31 * 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 */51std::string TupleKind::to_string() const52{53 return name;54}55 56/* Return the parameters of this tuple kind.57 *58 * By default, there are no parameters.59 */60std::vector<std::string> TupleKind::params() const61{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 */72TupleKindPtr TupleKind::apply(const Substitution &subs,73 const TupleKindPtr &self) const74{75 if (subs.count(name) != 0)76 return subs.at(name);77 return self;78}79 80/* Apply the substitution "subs" to "tuple" and return the result.81 */82static TupleKindPtr apply(const TupleKindPtr tuple, const Substitution &subs)83{84 return tuple->apply(subs, 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 */91TupleKindPtr TupleKind::left() const92{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 */100TupleKindPtr TupleKind::right() const101{102 return TupleKindPtr();103}104 105/* Helper class used to construct a pointer to a tuple kind106 * that refers to a non-template type.107 */108struct 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 */116TupleKindPtr::TupleKindPtr(Fixed) : Base(std::make_shared<TupleKind>(""))117{118}119 120/* Tuple pointers for non-template types.121 */122static TupleKindPtr Ctx{Fixed()};123static TupleKindPtr Integer{Fixed()};124static TupleKindPtr Str{Fixed()};125static TupleKindPtr Res{Fixed()};126 127/* Special tuple pointers.128 * Anonymous appears in the generated code but cannot be unified129 * with anything else since it is a predefined template argument.130 * Leaf can only be unified with something that is not a pair and131 * does not appear in the generated code.132 */133static TupleKindPtr Anonymous("Anonymous");134static TupleKindPtr Leaf("Leaf");135 136/* Placeholder tuple pointers that refer to (part of) the domain or range.137 */138static TupleKindPtr Domain("Domain");139static TupleKindPtr Domain2("Domain2");140static TupleKindPtr Domain3("Domain3");141static TupleKindPtr Range("Range");142static TupleKindPtr Range2("Range2");143static TupleKindPtr Range3("Range3");144 145/* A representation of a proper tuple kind that is used as a template146 * parameter or a template argument.147 */148struct 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 Anonymous157 * predefined template argument.158 */159std::vector<std::string> ProperTupleKind::params() const160{161 if (Anonymous.get() == this)162 return { };163 return { name };164}165 166/* Construct a pointer to a tuple kind that refers167 * to a proper tuple kind with the given name.168 */169TupleKindPtr::TupleKindPtr(const std::string &name) :170 Base(std::make_shared<ProperTupleKind>(name))171{172}173 174/* A tuple kind that represents an anonymous pair of nested tuple kinds.175 */176struct 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 */195std::string Pair::to_string() const196{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 */207static 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(vec1.begin(), vec1.end(), s) == vec1.end())212 vec1.emplace_back(s);213}214 215/* Return the parameters of this tuple kind.216 *217 * Combine the parameters of the two nested tuple kinds.218 */219std::vector<std::string> Pair::params() const220{221 auto names1 = tuple1->params();222 auto names2 = tuple2->params();223 224 combine(names1, 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 applying233 * the substitution to the two nested tuple kinds.234 */235TupleKindPtr Pair::apply(const Substitution &subs, const TupleKindPtr &self)236 const237{238 return TupleKindPtr(::apply(tuple1, subs), ::apply(tuple2, subs));239}240 241/* Return the left child of this tuple kind.242 */243TupleKindPtr Pair::left() const244{245 return tuple1;246}247 248/* Return the right child of this tuple kind.249 */250TupleKindPtr Pair::right() const251{252 return tuple2;253}254 255/* Construct a pointer to a tuple kind that refers256 * to the given pair of nested tuple kinds.257 */258TupleKindPtr::TupleKindPtr(const TupleKindPtr &left, const TupleKindPtr &right)259 : Base(std::make_shared<Pair>(left, right))260{261}262 263/* Is this a kind of object representing an anonymous function?264 */265bool Kind::is_anon() const266{267 return size() != 0 && back() == Anonymous;268}269 270/* Is this a kind of object with a single tuple?271 */272bool Kind::is_set() const273{274 return size() == 1;275}276 277/* Is this a kind of object with a single, anonymous tuple?278 */279bool Kind::is_anon_set() const280{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 */288std::vector<std::string> Kind::params() const289{290 std::vector<std::string> params;291 292 for (const auto &tuple : *this)293 combine(params, 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 */302Kind Kind::apply(const Substitution &subs) const303{304 Kind applied;305 306 for (const auto &tuple : *this)307 applied.emplace_back(::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 */315struct 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 */327std::vector<std::string> Signature::params() const328{329 std::vector<std::string> params;330 331 for (const auto &arg : args)332 combine(params, arg.params());333 combine(params, 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 */342Signature Signature::apply(const Substitution &subs) const343{344 std::vector<Kind> applied_args;345 346 for (const auto &arg : args)347 applied_args.emplace_back(arg.apply(subs));348 349 return { ret.apply(subs), applied_args };350}351 352/* Return a renaming substitution that renames the elements of "params"353 * using names starting with "prefix".354 */355static Substitution param_renamer(const std::vector<std::string> ¶ms,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(++n);363 auto arg_name = prefix + suffix;364 auto arg = TupleKindPtr(arg_name);365 366 if (name == Leaf->name)367 generator::die("Leaf cannot be renamed");368 369 renamer.emplace(name, arg);370 }371 372 return renamer;373}374 375/* Does the vector "v" contain the element "el"?376 */377static bool contains(const std::vector<std::string> &v, const std::string &el)378{379 return find(v.begin(), v.end(), el) != v.end();380 }381 382 383/* Return the shared elements of "v1" and "v2", preserving the order384 * of those elements in "v1".385 */386static 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(v2, el))393 intersection.push_back(el);394 395 return intersection;396}397 398/* Return a renaming substitution that renames399 * any parameters that appears in both "sig" and "kind".400 */401static Substitution shared_param_renamer(const Signature &sig, const Kind &kind)402{403 return param_renamer(intersect(sig.params(), kind.params()), "Arg");404}405 406/* Signatures for unary operations.407 * Functions have at least one tuple.408 */409static Signature un_params = { { }, { { } } };410static Signature un_set = { { Domain }, { { Domain } } };411static Signature un_map = { { Domain, Range }, { { Domain, Range } } };412static std::vector<Signature> un_op = { un_params, un_set, un_map };413static std::vector<Signature> fn_un_op = { un_set, un_map };414 415/* Signatures for binary operations, with the second argument416 * possibly referring to part of the first argument.417 * Functions have at least one tuple.418 */419static Signature bin_params = { { }, { { }, { } } };420static Signature bin_set = { { Domain }, { { Domain }, { Domain } } };421static Signature bin_map =422 { { Domain, Range }, { { Domain, Range }, { Domain, Range } } };423static std::vector<Signature> bin_op = { bin_params, bin_set, bin_map };424static std::vector<Signature> fn_bin_op = { bin_set, bin_map };425static Signature bin_set_params = { { Domain }, { { Domain }, { } } };426static Signature bin_map_params =427 { { Domain, Range }, { { Domain, Range }, { } } };428static Signature bin_map_domain =429 { { Domain, Range }, { { Domain, Range }, { Domain } } };430static Signature bin_map_range =431 { { Domain, Range }, { { Domain, Range }, { Range } } };432static Signature bin_map_domain_wrapped_domain =433 { { { Domain, Domain2 }, Range },434 { { { Domain, Domain2 }, Range }, { Domain } } };435static Signature bin_map_range_wrapped_domain =436 { { Domain, { Range, Range2 } },437 { { Domain, { Range, Range2 } }, { Range } } };438 439/* Signatures for binary operations, where the second argument440 * is an identifier (with an anonymous tuple).441 */442static Signature bin_params_anon = { { }, { { }, { Anonymous } } };443static Signature bin_set_anon = { { Domain }, { { Domain }, { Anonymous } } };444static Signature bin_map_anon =445 { { Domain, Range }, { { Domain, Range }, { Anonymous } } };446static 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 */451static Signature ter_params_int_int =452 { { }, { { }, { Integer }, { Integer } } };453static Signature ter_set_int_int =454 { { Domain }, { { Domain }, { Integer }, { Integer } } };455static Signature ter_map_int_int =456 { { Domain, Range }, { { Domain, Range }, { Integer }, { Integer } } };457static 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 */463static Signature ter_set =464 { { Domain }, { { Domain }, { Domain }, { Domain } } };465static Signature ter_map =466 { { Domain, Range },467 { { Domain, Range }, { Domain, Range }, { Domain, Range } } };468static std::vector<Signature> fn_ter_op = { ter_set, ter_map };469 470/* Signatures for naming a leaf tuple using an identifier (with an anonymous471 * tuple).472 */473static Signature update_set = { { Domain2 }, { { Leaf }, { Anonymous } } };474static Signature update_domain =475 { { Domain2, Range }, { { Leaf, Range }, { Anonymous } } };476static Signature update_range =477 { { Domain, Range2 }, { { Domain, Leaf }, { Anonymous } } };478 479/* Signatures for the functions "min" and "max", which can be either480 * unary or binary operations.481 */482static 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 */486static Signature to_set = { { Domain }, { { }, { Integer } } };487static Signature add_range = { { Domain, Range }, { { Domain }, { Integer } } };488/* Signatures for adding a named tuple to an object with zero or one tuple.489 */490static Signature to_set_named =491 { { Domain }, { { }, { Anonymous }, { Integer } } };492static Signature add_range_named =493 { { Domain, Range }, { { Domain }, { Anonymous }, { Integer } } };494 495/* Signatures for methods applying a map to a set, a function or496 * part of a map.497 */498static Signature set_forward = { { Range }, { { Domain }, { Domain, Range } } };499static Signature domain_forward =500 { { Domain2, Range }, { { Domain, Range }, { Domain, Domain2 } } };501static Signature range_forward =502 { { Domain, Range2 }, { { Domain, Range }, { Range, Range2 } } };503 504/* Signatures for methods plugging in a function into a set, a function or505 * part of a map.506 */507static Signature set_backward =508 { { Domain2 }, { { Domain }, { Domain2, Domain } } };509static Signature domain_backward =510 { { Domain2, Range }, { { Domain, Range }, { Domain2, Domain } } };511static Signature range_backward =512 { { Domain, Range2 }, { { Domain, Range }, { Range2, Range } } };513static Signature domain_wrapped_domain_backward =514 { { { Domain3, Domain2 }, Range },515 { { { 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 */520static Signature bind_set = { { }, { { Domain }, { Domain } } };521static Signature bind_domain = { { Range }, { { Domain, Range }, { Domain } } };522static Signature bind_range = { { Domain }, { { Domain, Range }, { Range } } };523static Signature bind_domain_wrapped_domain =524 { { Range2, Range }, { { { Domain2, Range2 }, Range }, { Domain2 } } };525 526/* Signatures for functions that take a callback accepting527 * objects of the same kind (but a different type).528 *529 * The return and argument kinds of the callback appear530 * at the position of the callback.531 */532static Signature each_params = { { Res }, { { }, { Res }, { } } };533static Signature each_set = { { Res }, { { Domain }, { Res }, { Domain } } };534static Signature each_map =535 { { Res }, { { Domain, Range }, { Res }, { Domain, Range } } };536static 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 */543static Signature each_scc_params =544 { { Res }, { { }, { Res }, { }, { }, { Res }, { } } };545static Signature each_scc_set =546 { { Res }, { { Domain },547 { Res }, { Domain }, { Domain },548 { Res }, { Domain } } };549static Signature each_scc_map =550 { { Res }, { { Domain, Range },551 { Res }, { Domain, Range }, { Domain, Range },552 { Res }, { Domain, Range } } };553static 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 */559static Signature map_from_range_and_domain =560 { { Domain, Range }, { { Range }, { Domain } } };561 562/* Signature for creating a map from a domain,563 * where the range is given by an extra argument.564 */565static Signature map_from_domain_and_range =566 { { Domain, Range }, { { Domain }, { Range } } };567 568/* Signatures for creating an anonymous set from a parameter set569 * or a map from a domain, where the range is anonymous.570 */571static Signature anonymous_set_from_params = { { Anonymous }, { { } } };572static Signature anonymous_map_from_domain =573 { { Domain, Anonymous }, { { Domain } } };574static 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 */580static Signature set_from_params = { { Domain }, { { }, { 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 */585static Signature anonymous_set_from_params_bin_anon =586 { { Anonymous }, { { }, { Anonymous } } };587static Signature anonymous_map_from_domain_bin_anon =588 { { Domain, Anonymous }, { { Domain }, { Anonymous } } };589static std::vector<Signature> anonymous_from_domain_bin_anon = {590 anonymous_set_from_params_bin_anon,591 anonymous_map_from_domain_bin_anon592 };593 594/* Signature for creating a map from a domain,595 * where the range tuple is equal to the domain tuple.596 */597static Signature set_to_map = { { Domain, Domain }, { { 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 */602static Signature domain = { { Domain }, { { Domain, Range } } };603static Signature range = { { Range }, { { Domain, Range } } };604static Signature transformation_domain = { { Domain }, { { Domain, Domain } } };605 606/* Signatures for obtaining the parameter domain of a set or map.607 */608static Signature set_params = { { }, { { Domain } } };609static Signature map_params = { { }, { { Domain, Range } } };610 611/* Signatures for obtaining the domain of a function.612 */613static std::vector<Signature> fn_domain = { domain, set_params };614 615/* Signatures for interchanging (wrapped) domain and range.616 */617static Signature map_reverse = { { Range, Domain }, { { Domain, Range } } };618static Signature map_range_reverse =619 { { Domain, { Range2, Range } }, { { Domain, { Range, Range2 } } } };620 621/* Signatures for constructing products.622 */623static Signature set_product =624 { { { Domain, Range } }, { { Domain }, { Range } } };625static Signature map_product =626 { { { Domain, Domain2 }, { Range, Range2 } },627 { { Domain, Range }, { Domain2, Range2 } } };628static Signature domain_product =629 { { { Domain, Domain2 }, Range },630 { { Domain, Range }, { Domain2, Range } } };631static Signature range_product =632 { { Domain, { Range, Range2 } },633 { { Domain, Range }, { Domain, Range2 } } };634 635/* Signatures for obtaining factors from a product.636 */637static Signature domain_factor_domain =638 { { Domain, Range }, { { { Domain, Domain2 }, Range } } };639static Signature domain_factor_range =640 { { Domain2, Range }, { { { Domain, Domain2 }, Range } } };641static Signature range_factor_domain =642 { { Domain, Range }, { { Domain, { Range, Range2 } } } };643static Signature range_factor_range =644 { { Domain, Range2 }, { { Domain, { Range, Range2 } } } };645 646/* Signatures for (un)currying.647 */648static Signature curry =649 { { Domain, { Range, Range2 } },650 { { { Domain, Range }, Range2 } } };651static Signature uncurry =652 { { { Domain, Range }, Range2 },653 { { Domain, { Range, Range2 } } } };654 655/* Signatures for (un)wrapping.656 */657static Signature wrap = { { { Domain, Range } }, { { Domain, Range } } };658static Signature unwrap = { { Domain, Range }, { { { Domain, Range } } } };659 660/* Signatures for constructing objects that map to the domain or range661 * of a map.662 */663static Signature domain_map =664 { { { Domain, Range }, Domain }, { { Domain, Range } } };665static Signature range_map =666 { { { Domain, Range }, Range }, { { Domain, Range } } };667 668/* Signature for applying a comparison between the domain and the range669 * of a map.670 */671static Signature map_cmp =672 { { Domain, Domain }, { { Domain, Domain }, { Domain, Range } } };673 674/* Signature for creating a set corresponding to the domains675 * of two functions.676 */677static Signature set_join =678 { { Domain }, { { 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 */683static Signature anonymize_nested_domain =684 { { Anonymous, Range2 }, { { { Domain, Range }, Range2 } } };685static Signature anonymize_nested_range =686 { { Domain, Anonymous }, { { Domain, { Range, Range2 } } } };687static Signature replace_nested_domain =688 { { Domain2, Range2 },689 { { { Domain, Range }, Range2 }, { Anonymous} } };690static Signature replace_nested_range =691 { { Domain, Range3 }, { { Domain, { Range, Range2 } }, { Anonymous} } };692static std::vector<Signature> flatten_domain =693 { anonymize_nested_domain, replace_nested_domain };694static std::vector<Signature> flatten_range =695 { anonymize_nested_range, replace_nested_range };696 697/* Signatures for "set_at" methods.698 */699static Signature set_at_set =700 { { Domain }, { { Domain }, { Integer }, { Anonymous } } };701static Signature set_at_map =702 { { Domain, Range },703 { { Domain, Range }, { Integer }, { Domain, Anonymous } } };704static std::vector<Signature> set_at = { set_at_set, set_at_map };705 706/* Signatures for "list" methods, extracting a list707 * from a multi-expression.708 */709static Signature to_list_set = { { Anonymous }, { { Domain } } };710static Signature to_list_map = { { Domain, Anonymous }, { { Domain, Range } } };711 712/* Signatures for functions constructing an object from only an isl::ctx.713 */714static Signature ctx_params = { { }, { { Ctx } } };715static Signature ctx_set = { { Domain }, { { Ctx } } };716static Signature ctx_map = { { Domain, Range }, { { Ctx } } };717 718/* Helper structure for sorting the keys of static_methods and719 * special_member_methods such that the larger keys appear first.720 * In particular, a key should appear before any key that appears721 * as a substring in the key.722 * Note that this sorting is currently only important723 * for special_member_methods.724 */725struct 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 */735typedef 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 name738 * to a sequence of signatures.739 */740typedef 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 relevant747 * number of tuples.748 *749 * The "universe" static methods create objects from the corresponding spaces.750 */751static 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 space771 * and return something in the same space or take something in a map space772 * and return something in the range of that space.773 */774static std::vector<Signature> range_op = { un_set, range };775 776/* Signatures for binary operations where the second argument777 * is a (multi-)value.778 */779static 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 */784static const std::unordered_map<std::string, std::vector<Signature>>785member_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 substring918 * that override the default signatures, where larger substrings919 * appear first.920 *921 * In particular, "gist" is usually a regular binary operation,922 * but for any type derived from "aff", the argument refers923 * to the domain of the function.924 *925 * The "size" method can usually simply be inherited from926 * 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 operation930 * 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 and933 * therefore its space only refers to the symbolic constants and934 * 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 object936 * 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 */940static 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 */958static Kind params{};959static Kind set_type{ Domain };960static Kind set_anon{ Anonymous };961static Kind map_type{ Domain, Range };962static Kind map_anon{ Domain, Anonymous };963 964/* The initial sequence of specialization kinds for base types.965 * The specialization kinds for other types are derived966 * from the corresponding base types.967 *968 * In particular, this sequence specifies how many tuples969 * 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 that977 * they can form the basis of "multi_val" and "multi_id".978 */979static 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 */992static 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 */1002static std::string drop_list(const std::string &type)1003{1004 size_t pos = type.rfind('_');1005 1006 if (pos == std::string::npos)1007 return type;1008 if (type.substr(pos + 1) == "list")1009 return type.substr(0, pos);1010 return type;1011}1012 1013/* Given the name of a plain C++ type, return the base type1014 * from which it was derived using type constructors.1015 *1016 * In particular, drop any "list" suffix and1017 * drop any prefixes from type_prefixes, stopping1018 * as soon as a base type is found for which kinds have been registered1019 * in base_kinds.1020 */1021static std::string base_type(const std::string &type)1022{1023 auto base = type;1024 size_t pos;1025 1026 base = drop_list(base);1027 while (base_kinds.count(base) == 0 &&1028 (pos = base.find('_')) != std::string::npos &&1029 type_prefixes.count(base.substr(0, pos)) != 0) {1030 base = base.substr(pos + 1);1031 }1032 1033 return base;1034}1035 1036/* A mapping from anonymous kinds to named kinds.1037 */1038static 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 them1044 * by the corresponding named kinds.1045 */1046static 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(anon_to_named.at(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 derived1061 * from an anonymous function type. Replace the final Anonymous1062 * tuple kind by a placeholder in this case.1063 */1064static std::vector<Kind> lookup_class_tuples(const std::string &name)1065{1066 std::string base = base_type(name);1067 1068 if (base_kinds.count(base) == 0)1069 return { };1070 if (name.find("multi_") != std::string::npos)1071 return add_name(base_kinds.at(base));1072 return base_kinds.at(base);1073}1074 1075/* Add a template class called "name", of which the methods are described1076 * by "clazz" and the initial specializations by "class_tuples".1077 */1078void 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(name,1085 template_class{name, super, clazz, class_tuples});1086}1087 1088/* Construct a templated C++ bindings generator from1089 * the exported types and functions and the set of all declared functions.1090 *1091 * On top of the initialization of the shared parts1092 * of C++ bindings generators, add a template class1093 * for each plain C++ class for which template kinds1094 * have been defined.1095 * In particular, determine the base type from which the plain C++ class1096 * was derived using type constructors and check if any template kinds1097 * have been registered for this base type.1098 */1099template_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, name, class_tuples);1114 }1115}1116 1117/* Call "fn" on each template class.1118 */1119void template_cpp_generator::foreach_template_class(1120 const std::function<void(const template_class &)> &fn) const1121{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 function1129 * that can also have a domain tuple, provide an <name>_on alias1130 * that adds the fixed Anonymous tuple kind.1131 */1132void template_cpp_generator::print_forward_declarations(std::ostream &os)1133{1134 foreach_template_class([&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 */1155void template_cpp_generator::print_friends(std::ostream &os)1156{1157 foreach_template_class([&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 parameter1165 * that needs to be declared.1166 */1167static 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 */1175static 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) or1181 * arguments (TupleKindPtr) "args", without the enclosing angle brackets.1182 */1183template <typename List>1184static 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) or1194 * arguments (TupleKindPtr) "args".1195 */1196template <typename List>1197static 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 */1206static void print_template(std::ostream &os,1207 const std::vector<std::string> ¶ms)1208{1209 os << "template ";1210 print_template_args(os, params);1211 os << "\n";1212}1213 1214/* Print a declaration of the template parameters "params",1215 * if there are any.1216 */1217static void print_non_empty_template(std::ostream &os,1218 const std::vector<std::string> ¶ms)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 arguments1228 * as specified by "kind".1229 */1230static 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, kind);1235}1236 1237/* A specific instance of "template_class", with tuple kinds given by "kind".1238 */1239struct 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 class1248 * from which this template class (instance) derives.1249 */1250const std::string &specialization::base_name() const1251{1252 return template_class.super_name;1253}1254 1255/* The name of the template class.1256 */1257const std::string &specialization::class_name() const1258{1259 return template_class.class_name;1260}1261 1262/* Helper class for printing the specializations of template classes1263 * 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 */1268struct 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 and1285 * these are added at the end of the list of specializations.1286 * That is, class_tuples.size() may change during the execution1287 * of the loop.1288 *1289 * For each specialization of a template class, call1290 * the print_class virtual method.1291 */1292void specialization_printer::print_classes() const1293{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({ template_class, class_tuples[i] });1300 }1301}1302 1303/* A helper class for printing method declarations and definitions1304 * of a template class specialization.1305 *1306 * "instance" is the template class specialization for which methods1307 * are printed.1308 * "generator" is the templated C++ interface generator printing the classes.1309 */1310struct 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 specialization1351 * for which methods are printed and1352 * the printer of the template class.1353 *1354 * The template class printer is only used to obtain the output stream and1355 * the templated C++ interface generator printing the classes.1356 */1357template_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 obtaining1369 * the argument kind is specified by the subclasses.1370 */1371struct 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 */1383std::string template_cpp_type_printer::base(const std::string &type,1384 const Kind &kind) const1385{1386 std::ostringstream ss;1387 1388 ss << "typed::";1389 print_bare_template_type(ss, type, kind);1390 return ss.str();1391}1392 1393/* Return the qualified form of the given C++ isl type name appearing1394 * 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 print1399 * the corresponding template type.1400 */1401std::string template_cpp_type_printer::qualified(int arg,1402 const std::string &cpp_type) const1403{1404 if (cpp_type == "ctx")1405 return cpp_type_printer::qualified(arg, cpp_type);1406 1407 return base(cpp_type, 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 */1414struct 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 */1428Kind template_cpp_kind_type_printer::kind(int arg) const1429{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 */1437struct 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 */1451Kind template_cpp_arg_type_printer::kind(int arg) const1452{1453 int n_args = sig.args.size();1454 1455 if (arg < 0)1456 return sig.ret;1457 if (arg >= n_args)1458 generator::die("argument out of bounds");1459 return sig.args[arg];1460}1461 1462/* A template type printer for printing a method with a given signature1463 * as part of a template class specialization of a given kind.1464 *1465 * "class_kind" is the template class specialization kind.1466 */1467struct 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 */1483std::string template_method_type_printer::class_type(1484 const std::string &cpp_name) const1485{1486 return base(cpp_name, 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 and1492 * use it to print the return type.1493 */1494void template_cpp_generator::class_printer::print_return_type(1495 const Method &method, const Kind &return_kind) const1496{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 */1504template <typename T>1505static 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 parameters1511 * 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 parameters1516 * 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 */1520void 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(method_params, sig.params());1528 1529 if (class_params.size() == method_params.size())1530 return;1531 1532 drop_initial(method_params, class_params.size());1533 1534 if (declarations)1535 os << " ";1536 print_template(os, 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 and1542 * then print a regular method header, using a template type printer.1543 */1544void 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 arguments1556 * those types that can be converted to the original argument type1557 * through a unary constructor?1558 *1559 * Since type deduction does not consider implicit conversions,1560 * these extra methods should always be printed.1561 */1562bool 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 forward1569 * to the corresponding methods in the plain C++ interface class.1570 */1571void template_cpp_generator::class_printer::print_all_methods()1572{1573 print_constructors();1574 print_methods();1575}1576 1577/* A helper class for printing method declarations1578 * of a template class specialization.1579 */1580struct 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 */1594void 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 position1608 * of the callback and the kinds of the arguments (except1609 * the user pointer argument) appear in the following positions.1610 * The user pointer argument that follows the callback argument1611 * is also removed.1612 */1613static 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 */1630static 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 { instance.kind, 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 */1645void 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, instance_sig(method, instance), true);1651}1652 1653/* A helper class for printing method definitions1654 * of a template class specialization.1655 */1656struct 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 corresponding1674 * plain type.1675 */1676void 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, [&] (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 positions1694 * shifted by "shift".1695 * None of the arguments should be skipped.1696 */1697static 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, 0, n_arg, [&] (int i) {1706 auto type = callback->getArgType(i);1707 auto name = "arg" + std::to_string(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 and1720 * calls the callback of "method" with templated arguments.1721 */1722static 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 21752 * with respect to the arguments of the signature1753 * (one for the position of the callback argument plus1754 * one for the return kind of the callback).1755 * The arguments of a subsequent callback are shifted by1756 * the number of arguments of the previous callback minus one1757 * for the user pointer plus one for the return kind.1758 */1759static 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("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 known1775 * to have a callback argument, with signature "sig".1776 *1777 * First print lambdas for passing to the corresponding plain method and1778 * calling the callback of "method" with templated arguments.1779 * Then call the plain method, replacing the original callbacks1780 * by the lambdas.1781 *1782 * The return value is assumed to be isl_bool or isl_stat1783 * so that no conversion to a template type is required.1784 */1785void 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("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, [&] (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 class1816 * in the plain interface and1817 * then casts the result to the templated result type.1818 */1819void 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, [&] (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, 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 declaration1842 * 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 or1847 * takes any callbacks.1848 */1849void 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, 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 else1864 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'd1871 * so no definition needs to be printed.1872 */1873void 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 */1881void template_cpp_generator::class_printer::print_static_method(1882 const Method &method)1883{1884 print_special_method(method, static_methods);1885}1886 1887/* Signatures for constructors of multi-expressions1888 * from a space and a list.1889 */1890static Signature from_list_set = { { Domain }, { { Domain }, { Anonymous } } };1891static Signature from_list_map =1892 { { Domain, Range }, { { Domain, Range }, { Domain, Anonymous } } };1893 1894/* Signatures for constructors from a string.1895 */1896static Signature params_from_str = { { }, { { Ctx }, { Str } } };1897static Signature set_from_str = { { Domain }, { { Ctx }, { Str } } };1898static Signature map_from_str = { { Domain, Range }, { { Ctx }, { Str } } };1899static 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 */1904static Signature int_from_si = { { Anonymous }, { { Ctx }, { Integer } } };1905 1906/* Signatures for constructors of lists from the initial number1907 * of elements.1908 */1909static Signature alloc_params = { { }, { { Ctx }, { Integer } } };1910static Signature alloc_set = { { Domain }, { { Ctx }, { Integer } } };1911static Signature alloc_map = { { Domain, Range }, { { Ctx }, { Integer } } };1912 1913/* Signatures for constructors and methods named after some other class.1914 *1915 * Two forms of constructors are handled1916 * - conversion from another object1917 * - construction of a multi-expression from a space and a list1918 *1919 * Methods named after some other class also come in two forms1920 * - extraction of information such as the space or a list1921 * - construction of a multi-expression from a space and a list1922 *1923 * In both cases, the first form is a unary operation and1924 * the second has an extra argument with a kind that is equal1925 * to that of the first argument, except that the final tuple is anonymous.1926 */1927static 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 methods1936 * with the given names that override the default signatures.1937 */1938static const std::unordered_map<std::string, std::vector<Signature>>1939special_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 */1947void template_cpp_generator::class_printer::print_constructor(1948 const Method &method)1949{1950 if (special_constructors.count(method.name) != 0) {1951 const auto &sigs = special_constructors.at(method.name);1952 return print_matching_method(method, sigs);1953 }1954 print_matching_method(method, 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 check1961 * the first specialization.1962 */1963bool template_class::is_anon() const1964{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 moreover1971 * has a single, anonymous tuple?1972 */1973bool template_class::is_anon_set() const1974{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 */1988static bool update_sub_base(Substitution &sub, const TupleKindPtr &general,1989 const TupleKindPtr &specific)1990{1991 auto name = general->name;1992 1993 if (sub.count(name) != 0 && sub.at(name) != specific)1994 return false;1995 sub.emplace(name, 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 based2007 * 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 */2013static 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->left(), specific->left()) &&2020 update_sub(sub, general->right(), 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 substitution2031 * 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 it2036 * for each pair of tuple kinds, checking that each update succeeds.2037 */2038static 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(specializer, general[i], 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 */2059static bool equivalent(const Kind &kind1, const Kind &kind2)2060{2061 return specializer(kind1, kind2).first &&2062 specializer(kind2, 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 */2068void template_class::add_specialization(const Kind &kind)2069{2070 for (const auto &special : class_tuples)2071 if (equivalent(special, kind))2072 return;2073 class_tuples.emplace_back(kind);2074}2075 2076/* A type printer that prints the plain interface type,2077 * without namespace.2078 */2079struct 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 appearing2087 * in argument position "arg" (-1 for return type).2088 *2089 * For printing the plain type without namespace, no modifications2090 * are required.2091 */2092std::string plain_cpp_type_printer::qualified(int arg,2093 const std::string &cpp_type) const2094{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 */2103static 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 */2110static 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 match2116 * 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 */2122static 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 else2127 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 */2136static 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 */2152bool 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(return_type) == 0)2159 return return_kind.params().size() == 0;2160 return has_kind(template_classes.at(return_type), return_kind);2161}2162 2163/* Is "kind" a placeholder that can be assigned something else2164 * in a substitution?2165 *2166 * Anonymous can only be mapped to itself. This is taken care of2167 * by assign().2168 * Leaf can only be assigned a placeholder, but there is no need2169 * to handle this specifically since Leaf can still be assigned2170 * to the placeholder.2171 */2172static 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 or2181 * if "kind1" and "kind2" are identical.2182 * The latter case handles mapping Anonymous to itself.2183 */2184static Substitution assign(const TupleKindPtr &kind1, const TupleKindPtr &kind2)2185{2186 Substitution res;2187 2188 if (assignable(kind1) || kind1 == kind2)2189 res.emplace(kind1->name, 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 */2197static Substitution compose(const Substitution &first,2198 const Substitution &second)2199{2200 Substitution res = second;2201 2202 for (const auto &kvp : first)2203 res.emplace(kvp.first, apply(kvp.second, second));2204 2205 return res;2206}2207 2208static 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 and2217 * combine it with "unifier".2218 */2219static Substitution combine_unifiers(const TupleKindPtr &kind1,2220 const TupleKindPtr &kind2, const Substitution &unifier)2221{2222 auto k1 = apply(kind1, unifier);2223 auto k2 = apply(kind2, unifier);2224 auto u = compute_unifier(k1, k2);2225 if (u.size() == 0)2226 return Substitution();2227 return compose(unifier, u);2228}2229 2230/* Try and compute a unifier of "kind1" and "kind2",2231 * i.e., a substitution that produces the same result when2232 * 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 */2240static Substitution compute_pair_unifier(const TupleKindPtr &kind1,2241 const TupleKindPtr &kind2)2242{2243 auto unifier_left = compute_unifier(kind1->left(), kind2->left());2244 if (unifier_left.size() == 0)2245 return Substitution();2246 return combine_unifiers(kind1->right(), kind2->right(), unifier_left);2247}2248 2249/* Try and compute a unifier of "kind1" and "kind2",2250 * i.e., a substitution that produces the same result when2251 * 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 it2256 * 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 even2261 * if "kind1" and "kind2" are identical.2262 * This ensures that a successful substitution is never empty.2263 */2264static Substitution compute_unifier(const TupleKindPtr &kind1,2265 const TupleKindPtr &kind2)2266{2267 if (kind1->left() && !kind2->left())2268 return assign(kind2, kind1);2269 if (!kind1->left() && kind2->left())2270 return assign(kind1, kind2);2271 if (!kind1->left() && !kind2->left()) {2272 if (assignable(kind1))2273 return assign(kind1, kind2);2274 else2275 return assign(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 when2283 * 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 for2288 * each pair of tuple kinds, combining the results.2289 * If no combined unifier can be found or2290 * if the numbers of tuple kinds are different, then return2291 * 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 */2295static 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[i], kind2[i], unifier);2304 2305 return unifier;2306}2307 2308/* Try and construct a Kind that is a specialization of both "general" and2309 * "specific", where "specific" is known _not_ to be a specialization2310 * 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 and2315 * try and compute a unifier.2316 * If this succeeds, then return the result of applying the unifier.2317 */2318static std::pair<bool, Kind> unify(const Kind &general, const Kind &specific)2319{2320 if (specializer(specific, general).first) {2321 return { true, general };2322 } else {2323 auto rename = param_renamer(specific.params(), "T");2324 auto renamed = specific.apply(rename);2325 auto unifier = compute_unifier(general, renamed);2326 2327 if (unifier.size() == 0)2328 return { false, { } };2329 2330 return { true, general.apply(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 both2336 * the current specialization and "kind".2337 *2338 * The current template class specialization is known not to be a special case2339 * of "kind".2340 *2341 * Try and unify the two kinds and, if this succeeds, add the result2342 * to this list of template class specializations.2343 */2344void template_cpp_generator::class_printer::add_specialization(2345 const Kind &kind)2346{2347 auto maybe_unified = unify(kind, instance.kind);2348 2349 if (!maybe_unified.first)2350 return;2351 instance.template_class.add_specialization(maybe_unified.second);2352}2353 2354/* Does the type of the parameter at position "i" of "method" necessarily2355 * have a final Anonymous tuple?2356 *2357 * If the parameter is not of an isl type or if no specializations2358 * 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 check2361 * the first specialization.2362 */2363static 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" and2382 * return the update signature,2383 * unless this would affect the class instance "instance_kind".2384 *2385 * If the original "instance_kind" is a special case2386 * of the result of the substitution, then "instance_kind"2387 * is not affected and the substitution can be applied2388 * to the entire signature.2389 */2390static Signature specialize_anonymous_arg(const Signature &sig,2391 const Kind &arg_kind, const Kind &instance_kind)2392{2393 const auto &subs = compute_unifier(arg_kind.back(), Anonymous);2394 const auto &specialized_instance = instance_kind.apply(subs);2395 2396 if (!specializer(specialized_instance, 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 necessarily2403 * has a final Anonymous tuple, but the corresponding entry2404 * in the signature "sig" is not Anonymous, then replace2405 * that entry by Anonymous and return the updated signature,2406 * unless this would affect the class instance "instance_kind".2407 */2408static 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([&] (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(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" refers2431 * to the first argument or the return type.2432 *2433 * Since "sig" may have parameters with the same names as2434 * those in instance.kind, rename them apart first.2435 *2436 * If the template class specialization is a special case of2437 * (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 specializations2445 * of the template class.2446 */2447bool 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, instance.kind);2451 auto renamed_arg = match_arg.apply(rename);2452 auto maybe_specializer = specializer(renamed_arg, instance.kind);2453 if (maybe_specializer.first) {2454 const auto &specializer = maybe_specializer.second;2455 auto specialized_sig = sig.apply(rename).apply(specializer);2456 specialized_sig = specialize_anonymous_args(specialized_sig,2457 method, instance.kind);2458 if (!is_return_kind(method, specialized_sig.ret))2459 return false;2460 2461 print_method_sig(method, specialized_sig, false);2462 } else {2463 add_specialization(match_arg);2464 }2465 return maybe_specializer.first;2466}2467 2468/* Is the first argument of "method" of type "isl_ctx *"?2469 */2470static 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 */2477static 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 match2487 * the template class specialization and2488 * check that it has the same number of template arguments.2489 * Also check that the number of arguments of the signature2490 * matches that of the method.2491 * If there is at least one argument, then check that the first method argument2492 * 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 */2496bool 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 on2517 * the specialization) so that it is not inherited from the base class.2518 */2519void 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, instance_sig(method, instance), true);2530}2531 2532/* Signatures for "at" methods applied to a multi-expression,2533 * which make the final tuple anonymous.2534 */2535static Signature select_set = { { Anonymous }, { { Domain }, { Integer } } };2536static Signature select_map =2537 { { Domain, Anonymous }, { { Domain, Range }, { Integer } } };2538static 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 */2543static Signature bin_set_int = { { Domain }, { { Domain }, { Integer } } };2544static Signature bin_map_int =2545 { { Domain, Range }, { { Domain, Range }, { Integer } } };2546static 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 and2552 * the other extracts an element from a list.2553 *2554 * In the first case, the return type is an anonymous function2555 * while the object type is not. In this case, the return kind2556 * should have a final Anonymous tuple.2557 * Otherwise, the return kind should be the same as the object kind.2558 */2559void 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(return_type);2565 2566 if (!anon && return_class.is_anon())2567 return print_matching_method(method, at_select);2568 else2569 return print_matching_method(method, at_keep);2570}2571 2572/* Does the string "s" contain "sub" as a substring?2573 */2574static bool contains(const std::string &s, const std::string &sub)2575{2576 return s.find(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 and2584 * 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 match2586 * since the largest keys appear first.2587 */2588bool template_cpp_generator::class_printer::print_special_method(2589 const Method &method, const infix_map_map &special_methods)2590{2591 if (special_methods.count(method.name) == 0)2592 return false;2593 2594 for (const auto &kvp : special_methods.at(method.name)) {2595 if (!contains(instance.template_class.class_name, kvp.first))2596 continue;2597 print_matching_method(method, 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 */2608bool template_cpp_generator::class_printer::print_special_member_method(2609 const Method &method)2610{2611 return print_special_method(method, 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 */2617bool template_cpp_generator::class_printer::print_type_named_member_method(2618 const Method &method)2619{2620 if (generator.template_classes.count(method.name) == 0)2621 return false;2622 2623 print_matching_method(method, 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 */2632bool template_cpp_generator::class_printer::print_member_method_with_name(2633 const Method &method, const std::string &name)2634{2635 if (member_methods.count(name) == 0)2636 return false;2637 2638 print_matching_method(method, member_methods.at(name));2639 return true;2640}2641 2642/* If "sub" appears inside "str", then remove the first occurrence and2643 * return the result. Otherwise, simply return "str".2644 */2645static std::string drop_occurrence(const std::string &str,2646 const std::string &sub)2647{2648 auto res = str;2649 auto pos = str.find(sub);2650 2651 if (pos != std::string::npos)2652 res.erase(pos, 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 */2660static std::string drop_underscore_occurrence(const std::string &str,2661 const std::string &sub)2662{2663 auto res = drop_occurrence(str, sub + "_");2664 if (res != str)2665 return res;2666 return drop_occurrence(res, 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 */2673const std::string name_without_return(const Method &method)2674{2675 auto return_infix = plain_return_type(method);2676 return drop_underscore_occurrence(method.name, return_infix);2677}2678 2679/* If this method has a callback, then remove the type2680 * of the first argument of the first callback from the name of the method.2681 * Otherwise, simply return the name of the method.2682 */2683const 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(method.name, "_" + 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 or2698 * if the method is named after some other type.2699 * Otherwise look for an appropriate signature using different variations2700 * of the method name. First try the method name itself,2701 * then the method name with the return type removed and2702 * finally the method name with the callback argument type removed.2703 */2704void 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, method.name))2714 return;2715 if (print_member_method_with_name(method, name_without_return(method)))2716 return;2717 if (print_member_method_with_name(method, callback_name(method)))2718 return;2719}2720 2721/* Print a declaration or definition of "method" based on its type.2722 */2723void 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 */2743void 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 marked2751 * as not requiring copies of the arguments.2752 */2753void 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 for2760 * template class specializations.2761 */2762struct template_cpp_generator::class_decl_printer :2763 public specialization_printer2764{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> ¶ms) 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 constructor2776 * for the template class specialization "instance" taking2777 * 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 otherwise2780 * there are no template arguments to be specialized and2781 * no constructor needs to be printed.2782 *2783 * In particular, the constructor takes an object of the same instance where2784 * for each template parameter, the corresponding template argument2785 * of the input object is a subclass of the template argument2786 * of the constructed object.2787 *2788 * Pick fresh names for all template parameters and2789 * add a constructor with these fresh names as extra template parameters and2790 * a constraint requiring that each of them is a subclass2791 * of the corresponding class template parameter.2792 * The plain C++ interface object of the constructed object is initialized with2793 * the plain C++ interface object of the constructor argument.2794 */2795void template_cpp_generator::class_decl_printer::print_arg_subclass_constructor(2796 const specialization &instance,2797 const std::vector<std::string> ¶ms) const2798{2799 const auto &class_name = instance.class_name();2800 auto rename = param_renamer(params, "Arg");2801 auto derived = instance.kind.apply(rename);2802 2803 os << " template ";2804 os << "<";2805 print_pure_template_args(os, 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(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, class_name, derived);2820 os << " &obj) : " << instance.base_name() << "(obj) {}\n";2821}2822 2823/* Print the declaration and definition of a constructor2824 * for the template class specialization "instance" taking2825 * an instance of the base class.2826 *2827 * If the instance kind is that of an anonymous set2828 * (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 and2831 * isl::typed::val<Anonymous> interchangeably and similarly for isl::id.2832 *2833 * If the instance is of any other kind, then make this constructor private2834 * to avoid objects of the plain interface being converted automatically.2835 * Also make sure that it does not apply to any type derived2836 * from the base class. In particular, this makes sure it does2837 * not apply to any other specializations of this template class as2838 * otherwise any conflict in specializations would simply point2839 * 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 */2844void template_cpp_generator::class_decl_printer::print_super_constructor(2845 const specialization &instance) const2846{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_name2856 << ">{}, 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 names2873 * in the instance kind.2874 *2875 * Each instance of the template class derives from the corresponding2876 * plain C++ interface class.2877 *2878 * All (other) template classes are made friends of this template class2879 * to allow them to call the private constructor taking an object2880 * of the plain interface.2881 *2882 * Besides the constructors and methods that forward2883 * 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 declaring2886 * a variable that only gets assigned a value at a later stage.2887 * The constructor taking an instance with more specialized2888 * template arguments is useful for lifting the class hierarchy2889 * of the template arguments to the template class.2890 * The constructor taking an instance of the base class2891 * is useful for (explicitly) constructing a template type2892 * from a plain type.2893 */2894void template_cpp_generator::class_decl_printer::print_class(2895 const specialization &instance) const2896{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, class_name, 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 */2922struct template_cpp_generator::class_impl_printer :2923 public specialization_printer2924{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 definitions2935 * for the constructors and methods that forward2936 * to the corresponding methods in the plain C++ interface class.2937 * The extra constructors declared in the class definition2938 * are defined inline.2939 */2940void template_cpp_generator::class_impl_printer::print_class(2941 const specialization &instance) const2942{2943 method_impl_printer(instance, *this).print_all_methods();2944}2945 2946/* Generate a templated cpp interface2947 * 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 all2951 * method implementations.2952 */2953void 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