summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNathan Ridge2018-05-02 01:36:46 -0400
committerNathan Ridge2018-05-11 00:02:02 -0400
commite533381b755faadf8f1a7f7329f32a7102a0c950 (patch)
treedc5e6a616539da0456e3a654a1b5b00f4f6c72ed
parent45bbb2bb5b5e4e9c93d4103a9c5e5c24db71d752 (diff)
downloadorg.eclipse.cdt-e533381b755faadf8f1a7f7329f32a7102a0c950.tar.gz
org.eclipse.cdt-e533381b755faadf8f1a7f7329f32a7102a0c950.tar.xz
org.eclipse.cdt-e533381b755faadf8f1a7f7329f32a7102a0c950.zip
Bug 534126 - Cache instantiations of alias template instances
This avoid runtime that's exponential in the nesting depth of alias template instances. Change-Id: Ibde6a6d98753df54e8e495a8b4547a90e8313191
-rw-r--r--core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java108
-rw-r--r--core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTTranslationUnit.java11
-rw-r--r--core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/semantics/CPPTemplates.java49
3 files changed, 163 insertions, 5 deletions
diff --git a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java
index 496f8958f6..48a9cd6539 100644
--- a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java
+++ b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java
@@ -10826,4 +10826,112 @@ public class AST2TemplateTests extends AST2CPPTestBase {
public void testOverloadResolutionWithInitializerList_531322() throws Exception {
parseAndCheckBindings();
}
+
+ // using size_t = decltype(sizeof(int));
+ //
+ // template <class Fn, class... Ts>
+ // using MetaApply = typename Fn::template apply<Ts...>;
+ //
+ // template <class... Ts>
+ // struct TypeList {
+ // using type = TypeList;
+ //
+ // template <class Fn>
+ // using apply = MetaApply<Fn, Ts...>;
+ // };
+ //
+ // struct Empty {};
+ //
+ // namespace impl {
+ // template <bool B>
+ // struct If_ {
+ // template <class T, class U>
+ // using apply = T;
+ // };
+ // template <>
+ // struct If_<false> {
+ // template <class T, class U>
+ // using apply = U;
+ // };
+ // }
+ //
+ // template <bool If_, class Then, class Else>
+ // using If = MetaApply<impl::If_<If_>, Then, Else>;
+ //
+ // template <template <class...> class C, class... Ts>
+ // class MetaDefer {
+ // template <template <class...> class D = C, class = D<Ts...>>
+ // static char(&try_(int))[1];
+ // static char(&try_(long))[2];
+ // struct Result {
+ // using type = C<Ts...>;
+ // };
+ //
+ // public:
+ // template <class... Us>
+ // using apply = typename If<sizeof(try_(0)) - 1 || sizeof...(Us), Empty, Result>::type;
+ // };
+ //
+ // struct MetaIdentity {
+ // template <class T>
+ // using apply = T;
+ // };
+ //
+ // template <template <class...> class C>
+ // struct MetaQuote {
+ // template <class... Ts>
+ // using apply = MetaApply<MetaDefer<C, Ts...>>;
+ // };
+ //
+ // template <>
+ // struct MetaQuote<TypeList> {
+ // template <class... Ts>
+ // using apply = TypeList<Ts...>;
+ // };
+ //
+ // template <class Fn>
+ // struct MetaFlip {
+ // template <class A, class B>
+ // using apply = MetaApply<Fn, B, A>;
+ // };
+ //
+ // namespace impl {
+ // template <class Fn>
+ // struct FoldL_ {
+ // template <class... Ts>
+ // struct Lambda : MetaIdentity {};
+ // template <class A, class... Ts>
+ // struct Lambda<A, Ts...> {
+ // template <class State>
+ // using apply = MetaApply<Lambda<Ts...>, MetaApply<Fn, State, A>>;
+ // };
+ // template <class... Ts>
+ // using apply = Lambda<Ts...>;
+ // };
+ // }
+ //
+ // template <class List, class State, class Fn>
+ // using TypeReverseFold = MetaApply<MetaApply<List, impl::FoldL_<Fn>>, State>;
+ //
+ // template <class Car, class Cdr = Empty>
+ // struct Cons {};
+ // using Fn = MetaQuote<Cons>;
+ // using T4 = TypeReverseFold<
+ // // Make it long enough to be sure that if the runtime is exponential
+ // // in the length of the list, the test suite times out.
+ // TypeList<int, short, void, float, double, long, char
+ // int*, short*, void*, float*, double*, long*, char*>,
+ // Empty,
+ // MetaFlip<Fn>>;
+ //
+ // template <class T>
+ // struct Dummy {
+ // static const bool value = true;
+ // };
+ // int main() {
+ // static_assert(Dummy<T4>::value, "");
+ // }
+ public void testMetaprogrammingWithAliasTemplates_534126() throws Exception {
+ parseAndCheckBindings();
+ }
}
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTTranslationUnit.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTTranslationUnit.java
index 9ff0ec7ae5..1d0410f50b 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTTranslationUnit.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTTranslationUnit.java
@@ -41,6 +41,7 @@ import org.eclipse.cdt.internal.core.dom.parser.ASTTranslationUnit;
import org.eclipse.cdt.internal.core.dom.parser.IASTAmbiguityParent;
import org.eclipse.cdt.internal.core.dom.parser.cpp.semantics.CPPInheritance.FinalOverriderMap;
import org.eclipse.cdt.internal.core.dom.parser.cpp.semantics.CPPVisitor;
+import org.eclipse.cdt.internal.core.dom.parser.cpp.semantics.TypeInstantiationRequest;
import org.eclipse.cdt.internal.core.index.IIndexScope;
import org.eclipse.cdt.internal.core.parser.scanner.InternalFileContent;
@@ -55,6 +56,12 @@ public class CPPASTTranslationUnit extends ASTTranslationUnit implements ICPPAST
// Caches.
private final Map<ICPPClassType, FinalOverriderMap> fFinalOverriderMapCache = new HashMap<>();
+ // Cache for type instantiations. This is currently only used for instantiations of
+ // alias template instances, but its use could potentially be expanded to cover other
+ // instantiations. Note that class template instances are already cached by the
+ // template definition, so we wouldn't want to double-cache those. (But we could e.g.
+ // cache instantiations of function types if we found it worthwhile.)
+ private final Map<TypeInstantiationRequest, IType> fInstantiationCache = new HashMap<>();
public CPPASTTranslationUnit() {
fScopeMapper= new CPPScopeMapper(this);
@@ -249,6 +256,10 @@ public class CPPASTTranslationUnit extends ASTTranslationUnit implements ICPPAST
public Map<ICPPClassType, FinalOverriderMap> getFinalOverriderMapCache() {
return fFinalOverriderMapCache;
}
+
+ public Map<TypeInstantiationRequest, IType> getInstantiationCache() {
+ return fInstantiationCache;
+ }
public void recordPartialSpecialization(ICPPClassTemplatePartialSpecialization indexSpec,
ICPPClassTemplatePartialSpecialization astSpec) {
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/semantics/CPPTemplates.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/semantics/CPPTemplates.java
index 379abee791..ed26f0a81d 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/semantics/CPPTemplates.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/semantics/CPPTemplates.java
@@ -26,6 +26,7 @@ import static org.eclipse.cdt.internal.core.dom.parser.cpp.semantics.SemanticUti
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import org.eclipse.cdt.core.CCorePlugin;
@@ -45,6 +46,7 @@ import org.eclipse.cdt.core.dom.ast.IASTName;
import org.eclipse.cdt.core.dom.ast.IASTNameOwner;
import org.eclipse.cdt.core.dom.ast.IASTNode;
import org.eclipse.cdt.core.dom.ast.IASTSimpleDeclaration;
+import org.eclipse.cdt.core.dom.ast.IASTTranslationUnit;
import org.eclipse.cdt.core.dom.ast.IASTTypeId;
import org.eclipse.cdt.core.dom.ast.IArrayType;
import org.eclipse.cdt.core.dom.ast.IBinding;
@@ -134,6 +136,7 @@ import org.eclipse.cdt.internal.core.dom.parser.ProblemBinding;
import org.eclipse.cdt.internal.core.dom.parser.ProblemFunctionType;
import org.eclipse.cdt.internal.core.dom.parser.ProblemType;
import org.eclipse.cdt.internal.core.dom.parser.cpp.CPPASTName;
+import org.eclipse.cdt.internal.core.dom.parser.cpp.CPPASTTranslationUnit;
import org.eclipse.cdt.internal.core.dom.parser.cpp.CPPAliasTemplateInstance;
import org.eclipse.cdt.internal.core.dom.parser.cpp.CPPAliasTemplateSpecialization;
import org.eclipse.cdt.internal.core.dom.parser.cpp.CPPArrayType;
@@ -1607,21 +1610,34 @@ public class CPPTemplates {
// to the target type but can SFINAE out during instantiation, so it's not
// sufficient to handle it in the ITypeContainer case.
if (type instanceof ICPPAliasTemplateInstance) {
+ // Cache instantiations of alias templates. This is necessary because below we can
+ // potentially instantiate types that appear in the arguments of an alias template
+ // instance up to three times (once in instantiateArguments(), once in
+ // instantiateArgumentMap(), and if the argument appears in the aliased type, then
+ // a third time in instantiateType()), leading to exponential runtime in cases of
+ // nested alias template instances (which can be common in metaprogramming code
+ // implemented using alias templates).
+ IType result = getCachedInstantiation(instantiationRequest);
+ if (result != null) {
+ return result;
+ }
ICPPAliasTemplateInstance instance = (ICPPAliasTemplateInstance) type;
ICPPAliasTemplate template = instance.getTemplateDefinition();
ICPPTemplateArgument[] args = instance.getTemplateArguments();
ICPPTemplateArgument[] newArgs = instantiateArguments(args, context, true);
if (newArgs == null) {
- return (IType) createProblem(template,
+ result = (IType) createProblem(template,
IProblemBinding.SEMANTIC_INVALID_TEMPLATE_ARGUMENTS);
- }
- if (args != newArgs) {
+ } else if (args != newArgs) {
IType target = instantiateType(instance.getType(), context);
CPPTemplateParameterMap map =
instantiateArgumentMap(instance.getTemplateParameterMap(), context);
- return new CPPAliasTemplateInstance(template, target, instance.getOwner(), map, newArgs);
+ result = new CPPAliasTemplateInstance(template, target, instance.getOwner(), map, newArgs);
+ } else {
+ result = type;
}
- return type;
+ putCachedInstantiation(instantiationRequest, result);
+ return result;
}
if (type instanceof ITypeContainer) {
@@ -3342,4 +3358,27 @@ public class CPPTemplates {
}
return true;
}
+
+ private static Map<TypeInstantiationRequest, IType> getInstantiationCache() {
+ IASTNode lookupPoint = CPPSemantics.getCurrentLookupPoint();
+ if (lookupPoint != null) {
+ IASTTranslationUnit tu = lookupPoint.getTranslationUnit();
+ if (tu instanceof CPPASTTranslationUnit) {
+ return ((CPPASTTranslationUnit) tu).getInstantiationCache();
+ }
+ }
+ return null;
+ }
+
+ private static IType getCachedInstantiation(TypeInstantiationRequest instantiationRequest) {
+ Map<TypeInstantiationRequest, IType> cache = getInstantiationCache();
+ return cache != null ? cache.get(instantiationRequest) : null;
+ }
+
+ private static void putCachedInstantiation(TypeInstantiationRequest instantiationRequest, IType result) {
+ Map<TypeInstantiationRequest, IType> cache = getInstantiationCache();
+ if (cache != null) {
+ cache.put(instantiationRequest, result);
+ }
+ }
}