compilation time explodes for this type of regex

[hanickadot]

trafficstars

0?1?2?3?4?5?6?7?8?9?

[Andersama]

Could it be in part because evaluation.hpp for optional doesn't make compile time forward progess?

template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... Tail> 
constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, R captures, ctll::list<optional<Content...>, Tail...>) noexcept {
	if (auto r1 = evaluate(begin, current, end, captures, ctll::list<sequence<Content...>, Tail...>())) {
		return r1;
	} else if (auto r2 = evaluate(begin, current, end, captures, ctll::list<Tail...>())) {
		return r2;
	} else {
		return not_matched;
	}
}

If there's any optional content it creates a sequence which has to be processed, pretty sure ctll::list<Content...,Tail...>() would also work.

Another thought, memoize the second half of the optional ctll::list<Tail...>, e.g.:

//from this:
template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... Tail> 
constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, R captures, ctll::list<optional<Content...>, Tail...>) noexcept {
	if (auto r1 = evaluate(begin, current, end, captures, ctll::list<Content..., Tail...>())) {
		return r1;
	} else if (auto r2 = evaluate(begin, current, end, captures, ctll::list<Tail...>())) {
		return r2;
	} else {
		return not_matched;
	}
}
//to this:
template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... Tail> 
constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, R captures, ctll::list<optional<Content...>, Tail...>) noexcept {
	if (auto r1 = evaluate(begin, current, end, captures, ctll::list<Content...>())) {
		if (auto r2 = evaluate(begin, r1.get_end_position(), end, captures, ctll::list<Tail...>())) {
			return r2;
		} else if (auto r3 = evaluate(begin, current, end, captures, ctll::list<Tail...>())) {
			return r3;
		} else {
			return not_matched;
		}
	} else if (auto r4 = evaluate(begin, current, end, captures, ctll::list<Tail...>())) {
		return r4;
	} else {
		return not_matched;
	}
}

[Andersama]

I find that the compile time explodes only when in release mode. Suggests to me optimizing the function is what is creating an issue.

[Andersama]

Likely inlining is the core issue, changed functions from their originals to the equivalent:

// matching optional in patterns
template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... Tail> 
constexpr inline R evaluate(const Iterator begin, Iterator current, const EndIterator end, R captures, ctll::list<optional<Content...>, Tail...>) noexcept {
	return evaluate(begin, current, end, captures, ctll::list<select<sequence<Content...,Tail...>,sequence<Tail...>>>());
}

// lazy optional
template <typename R, typename Iterator, typename EndIterator, typename O, typename... Content, typename... Tail> 
constexpr inline R evaluate(const Iterator begin, Iterator current, const EndIterator end, R captures, ctll::list<lazy_optional<Content...>, Tail...>) noexcept {
	return evaluate(begin, current, end, captures, ctll::list<select<sequence<Tail...>, sequence<Content..., Tail...>>>());
}

Removed the force inline, compiled near instantly. If I'm not crazy far off the likely problem is the function per step expands 2^n options but also a crazy amount of additional function signatures, and more than likely the inliner is doing some call graph heuristics between all of those. I guess here is a saving grace that inline is only a "hint".

Possible other approach, if in fact it's inliner hell, delay evaluating optionals by collecting them in a single type, then expand with fold expressions into a single function. EG...

template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... TailContent, typename... Tail>
constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, R captures, ctll::list<optional<Content...>, optional<TailContent...>, Tail...>) noexcept {
return evaluate(begin,current,end,captures,ctll::list<bad_times<sequence<Content...>,sequence<TailContent...>>, Tail...>());
}
//handle bad_times in a single go

That way presumably there's no issue with the inliner because there's only one function body.