Adding FoldedType as a new type

Once D116203 and D116280 have been submitted to main, I’d like to focus on introducing an nary type transformations like __common_type, __common_reference, and __common_comparison_category to replace their corresponding non-underscored standard type names.

I checked with Richard Smith, and it’s apparently beneficial for __common_comparison_category to be a builtin as opposed to something like this:

template<class... Ts>
consteval auto __common_comparison_category() {
  if constexpr ((same_as<partially_ordered, Ts> or ...)) {
    return partial_ordering{};
  else if constexpr ((same_as<weakly_ordered{}, Ts> or ...)) {
    return weak_ordering{};
  else {
    return strong_ordering{};

template<class... Ts>
using common_comparison_category = decltype(__common_comparison_category<Ts...>());

If something as simple as __common_comparison_category can benefit from being a builtin, I expect common_type and common_reference to also benefit, given that they’re substantially more complex to implement and are recursive in nature. D116203 is lucky in that __underlying_type already exists, and its authors have been able to use UnaryTransformType to implement unary transforms. I don’t see an nary equivalent :frowning:

As such, I’d like to implement a type I’m calling FoldingType, since the type is essentially a fold operation: it takes a sequence of types as input, and returns exactly zero or one types as output. The zero case is for things like std::common_type<int, std::vector<int>>, which doesn’t have a a member type. Rather than forcing the library to do a workaround for the type not existing, I think it might just be easier for the compiler to say that __common_type(int, std::vector<int>) has “nothing”, and that any alias that uses __common_type(int, std::vector<int>) don’t exist when someone tries to use it.

// Example
template<class... Ts>
struct common_type {
  using type = __common_type(Ts...);

common_type<int, int>::type x; // okay, x's type is int
common_type<>::type y; // error: common_type<>::type doesn't exist
common_type<int, std::vector<int>>::type z; // error: common_type<int, std::vector<int>>::type doesn't exist

If there is indeed no fitting type, are there any objections to me adding FoldingType? If not, are there any design considerations or tips that I might want to take on board? Looking at UnaryTransformType, I understand adding a new type to be a pretty full-on thing to do.

(This effort sounds really-useful. Re-reading my post it looks harsh, it’s just a braindump of concerns, sorry!)

This seems very similar to UnaryTransformType. Can we generalize it to TransformType (or TraitType or so) instead of adding a separate thing? Even if this means a slightly larger representation of the type for __underlying_type, I doubt these are common enough that it’s critical.

Is it the new sugar type that provides the benefit, or avoiding the template instantiation costs?
i.e. would it be OK if common_type<short, int> referred (efficiently) to BuiltinType int, or is it important that it’s a FoldingType wrapping int?

(If the sugar itself isn’t desirable, you’d only need the dependent, canonical version, right?)

FWIW, I’d really like to see a less abstract name, and particularly avoiding adding a second abstract name for the same thing as UnaryTransformType. Most node names refer pretty closely to the language features they model, and exceptions (like UnaryTransform) are things I need to look up every time.

If the idea is to refuse to build AST nodes for this code, and drop all AST nodes that recursively refer to it, this is going to be very bad for tools that want to work on broken code (e.g. IDEs), and somewhat bad for clang error recovery.
I think it’s important that common_type<int, vector<int>> has a sensible TemplateSpecializationType node, even if its underlying type is int or something used for recovery.

Yeah, I’ve done this only once, so with a pinch of salt and maybe this is obvious…

The only nice thing about modifying a type instead of adding a new one is that it’s more obvious everywhere you need to update :slight_smile:

You have a choice to add one new FoldingType or both FoldingType and DependentFoldingType. The latter seems ugly at first but I actually prefer it, because a unified FoldingType is canonical-when-dependent and it’s IMO easier if you can statically tell from an AST node whether it’s canonical or not.

For me, the unexpected surprise was I forgot to update ASTImporter. The build didn’t break (which is how I found most places to update), but one LLDB test did (in a way that was hard to track down). So don’t forget that!

Also it took me too long to realize that creating a typedef is how you get clang -ast-dump to print a sugared type, which seems often like the clearest way to test.

1 Like