Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Bug 316704

Summary: [C++ Parser] Exponential complexity resolving template argument ambiguity
Product: [Tools] CDT Reporter: holgre <cr8>
Component: cdt-parserAssignee: Markus Schorn <mschorn.eclipse>
Status: RESOLVED FIXED QA Contact: Markus Schorn <mschorn.eclipse>
Severity: normal    
Priority: P3    
Version: 7.0   
Target Milestone: 7.0.1   
Hardware: PC   
OS: Linux   
Whiteboard:
Attachments:
Description Flags
thread dump shortly before eclipse recommends to terminate workbench
none
testcase + fix mschorn.eclipse: iplog-

Description holgre CLA 2010-06-13 14:07:46 EDT
Build Identifier: eclipse-cpp-helios-RC4-linux-gtk.tar.gz

I'm working on a project using RCF V1.2 (Remote Call Framework for C++). Unfortunately I cannot make use of the indexer because it seems to eat up all memory whenever it runs over some of the RCF header files (I couldn't figure out which one causes the problem). This problem persists even with the newest version of CDT (also tried ganymede and older). I played around a bit with memory settings for eclipse but this didn't solve the problem. RCF itself has been tested against several compilers including such ancient versions like gcc 3.2.2 without much problems, so I hope there is a solution for this problem.

BTW : thank you all for CDT - it's a pleasure to work with it.

Reproducible: Always

Steps to Reproduce:
1. Import sources from RCF project.
2. Observe the indexer in the task bar (0 % completed but 100 % CPU)
3. Wait until an error message box pops up reporting 'out of memory'
Comment 1 Markus Schorn CLA 2010-06-14 04:04:05 EDT
Please provide a thread dump of the application before it runs out of memory.
See http://wiki.eclipse.org/How_to_report_a_deadlock for details on how to create a thread dump.
Alternatively you may find a stack-trace in your log-file (<workspace>/.metadata/.log).
Comment 2 holgre CLA 2010-06-14 13:46:09 EDT
Created attachment 171852 [details]
thread dump shortly before eclipse recommends to terminate workbench

thread dump created using command line parameters '-consolelog -debug'
Comment 3 Markus Schorn CLA 2010-06-18 09:28:25 EDT
Via macro expansions the following code is constructed:

   typedef
      if_< bool,
      // 50x: if_< bool,
      if_< bool,
      int_<52>,
      int_<51> >::type,
      // 50x int_<n> >::type,
      int_<0> >::type rcf_unique_id_x_V1_4;

Because of the ambiguity of the template arguments ('type' can be a type-id or an expression) we attempt to create 2^50 nodes, for which we do not have the memory.
Comment 4 Markus Schorn CLA 2010-06-18 10:27:21 EDT
Created attachment 172222 [details]
testcase + fix

With the patch the nodes get reused for each variant.
Comment 5 Markus Schorn CLA 2010-06-18 10:38:38 EDT
Fixed in 7.0.1 and 8.0 > 20100618.
Comment 6 CDT Genie CLA 2010-06-18 11:23:04 EDT
*** cdt cvs genie on behalf of mschorn ***
Bug 316704: Exponential complexity resolving template argument ambiguity.

[*] ASTAmbiguousNode.java 1.11.2.1 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTAmbiguousNode.java?root=Tools_Project&r1=1.11&r2=1.11.2.1

[*] CPPASTAmbiguousTemplateArgument.java 1.9.2.1 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTAmbiguousTemplateArgument.java?root=Tools_Project&r1=1.9&r2=1.9.2.1
[*] GNUCPPSourceParser.java 1.231.2.1 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/GNUCPPSourceParser.java?root=Tools_Project&r1=1.231&r2=1.231.2.1

[*] AST2TemplateTests.java 1.184.2.1 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java?root=Tools_Project&r1=1.184&r2=1.184.2.1

[*] AST2TemplateTests.java 1.185 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/core/parser/tests/ast2/AST2TemplateTests.java?root=Tools_Project&r1=1.184&r2=1.185

[*] ASTAmbiguousNode.java 1.12 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/ASTAmbiguousNode.java?root=Tools_Project&r1=1.11&r2=1.12

[*] CPPASTAmbiguousTemplateArgument.java 1.10 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/CPPASTAmbiguousTemplateArgument.java?root=Tools_Project&r1=1.9&r2=1.10
[*] GNUCPPSourceParser.java 1.233 http://dev.eclipse.org/viewcvs/index.cgi/org.eclipse.cdt-core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/parser/cpp/GNUCPPSourceParser.java?root=Tools_Project&r1=1.232&r2=1.233