Implementation of Templates in the CPG

[vfsrfs]

The purpose of this issue is to document the decisions @konradweiss and I made on how to implement CPP Templates.

The implementation of the CPP Templates will be split up into two parts: A first representation of the Template in the Graph and a Pass that refines the Template usage, with the same approach used by the CPP Compiler. The main reason for choosing this approach is the fact, that an extensive resolution of the templates leads to a more refined graph, but it might also increase the size of the graph considerably. Therefore, the refinement is implemented as a pass, in order to make the refinement optional if the graph size is too big.

Java Generics can also be modelled as a subset of CPP Templates and therefore the current Java Generics representation will be modified to be consistent with the CPP Templates approach. The main differences are:

1. Java Generics can only be applied on Classes, whereas CPP Templates can be applied on Classes and Functions

2. In Java the parameters of the classes can only be Types, compared to CPP Templates, where values can also be provided to the Template.

Representation

To explain how Templates will be represented in the graph, we will be using the following snippet as an example. This snippet represent a template applied on a function, but this is sufficient as applying templates to classes is very similar.

Code:

#include <iostream>
using namespace std;

template <class T, int N>
T fixed_multiply (T val)
{
  return val * N;
}

int main() {
  std::cout << fixed_multiply<int,2>(10) << '\n';
  std::cout << fixed_multiply<float,3>(10.0) << '\n';
}

Graph:

As we can see, the graph now includes a new node called Template (exact naming is open for discussion) containing three outgoing edges. The first one is the realization edge to the function, which is implemented by the template. The second and third edges are parameters-Edges pointing towards the two parameters of the template. The first parameter is a ParameterizedType as introduced by #317 and defined in #293. This represents the abstract Type T and contains two edges two both types it has been initialized in the code (int and float). The second argument is a ConstantDeclaration, as the values passed to Templates must be known at compile time and therefore they must be constant. This node also contains possibleInitialization-Edges to the Literals that have been found in the initialization of the Template.

Refinement Pass

As explained before, a more refined graph has a bigger size, since every usage of the Template leads to a custom function/class. However, a more refined graph is useful for the analysis of the code, since it may enable us to have a more exact resolution of the code (e.g. exact resolution of a call is possible since we now have type information).

Therefore, this pass modifies the graph and 'realizes' every usage of the Template following the same approach as the CPP Compiler.

Graph:

As we can see in the graph above, now the template contains two FunctionDeclarations (of the same function) with the different realizations, and each CallExpression invokes the correct realized FunctionDeclaration. Additionally, the FunctionDeclarations now contain pointer to the exact values that were used to realize the template.

[oxisto]

Just for reference, this is the generated clang AST for the example:

|-FunctionTemplateDecl 0x7fc8a1086d58 <line:4:1, line:8:1> line:5:3 fixed_multiply
| |-TemplateTypeParmDecl 0x7fc8a1086ad8 <line:4:11, col:17> col:17 referenced class depth 0 index 0 T
| |-NonTypeTemplateParmDecl 0x7fc8a1086b60 <col:20, col:24> col:24 referenced 'int' depth 0 index 1 N
| |-FunctionDecl 0x7fc8a1086cb8 <line:5:1, line:8:1> line:5:3 fixed_multiply 'T (T)'
| | |-ParmVarDecl 0x7fc8a1086bf0 <col:19, col:21> col:21 referenced val 'T'
| | `-CompoundStmt 0x7fc8a1086e28 <line:6:1, line:8:1>
| |   `-ReturnStmt 0x7fc8a1086e18 <line:7:3, col:16>
| |     `-BinaryOperator 0x7fc8a1086df8 <col:10, col:16> '<dependent type>' '*'
| |       |-DeclRefExpr 0x7fc8a1086db8 <col:10> 'T' lvalue ParmVar 0x7fc8a1086bf0 'val' 'T'
| |       `-DeclRefExpr 0x7fc8a1086dd8 <col:16> 'int' NonTypeTemplateParm 0x7fc8a1086b60 'N' 'int'
| |-FunctionDecl 0x7fc8a1087368 <line:5:1, line:8:1> line:5:3 used fixed_multiply 'int (int)'
| | |-TemplateArgument type 'int'
| | |-TemplateArgument integral 2
| | |-ParmVarDecl 0x7fc8a10872a0 <col:19, col:21> col:21 used val 'int':'int'
| | `-CompoundStmt 0x7fc8a10f4c30 <line:6:1, line:8:1>
| |   `-ReturnStmt 0x7fc8a10f4c20 <line:7:3, col:16>
| |     `-BinaryOperator 0x7fc8a10f4c00 <col:10, col:16> 'int' '*'
| |       |-ImplicitCastExpr 0x7fc8a10f4be8 <col:10> 'int':'int' <LValueToRValue>
| |       | `-DeclRefExpr 0x7fc8a10f4b88 <col:10> 'int':'int' lvalue ParmVar 0x7fc8a10872a0 'val' 'int':'int'
| |       `-SubstNonTypeTemplateParmExpr 0x7fc8a10f4bc8 <col:16> 'int'
| |         `-IntegerLiteral 0x7fc8a10f4ba8 <col:16> 'int' 2
| `-FunctionDecl 0x7fc8a108a318 <line:5:1, line:8:1> line:5:3 used fixed_multiply 'float (float)'
|   |-TemplateArgument type 'float'
|   |-TemplateArgument integral 3
|   |-ParmVarDecl 0x7fc8a108a250 <col:19, col:21> col:21 used val 'float':'float'
|   `-CompoundStmt 0x7fc8a1114960 <line:6:1, line:8:1>
|     `-ReturnStmt 0x7fc8a1114950 <line:7:3, col:16>
|       `-BinaryOperator 0x7fc8a1114930 <col:10, col:16> 'float' '*'
|         |-ImplicitCastExpr 0x7fc8a1114900 <col:10> 'float':'float' <LValueToRValue>
|         | `-DeclRefExpr 0x7fc8a11148a0 <col:10> 'float':'float' lvalue ParmVar 0x7fc8a108a250 'val' 'float':'float'
|         `-ImplicitCastExpr 0x7fc8a1114918 <col:16> 'float' <IntegralToFloating>
|           `-SubstNonTypeTemplateParmExpr 0x7fc8a11148e0 <col:16> 'int'
|             `-IntegerLiteral 0x7fc8a11148c0 <col:16> 'int' 3
`-FunctionDecl 0x7fc8a1086e68 <line:10:1, line:13:1> line:10:5 main 'int ()'
  `-CompoundStmt 0x7fc8a108b3c8 <col:12, line:13:1>
    |-CXXOperatorCallExpr 0x7fc8a1089f20 <line:11:3, col:45> 'basic_ostream<char, std::__1::char_traits<char> >':'std::__1::basic_ostream<char>' lvalue
    | |-ImplicitCastExpr 0x7fc8a1089f08 <col:42> 'basic_ostream<char, std::__1::char_traits<char> > &(*)(basic_ostream<char, std::__1::char_traits<char> > &, char)' <FunctionToPointerDecay>
    | | `-DeclRefExpr 0x7fc8a1089e88 <col:42> 'basic_ostream<char, std::__1::char_traits<char> > &(basic_ostream<char, std::__1::char_traits<char> > &, char)' lvalue Function 0x7fc8a1088038 'operator<<' 'basic_ostream<char, std::__1::char_traits<char> > &(basic_ostream<char, std::__1::char_traits<char> > &, char)'
    | |-CXXOperatorCallExpr 0x7fc8a1089110 <col:3, col:40> 'std::__1::basic_ostream<char>' lvalue
    | | |-ImplicitCastExpr 0x7fc8a10890f8 <col:13> 'std::__1::basic_ostream<char> &(*)(int)' <FunctionToPointerDecay>
    | | | `-DeclRefExpr 0x7fc8a10890a8 <col:13> 'std::__1::basic_ostream<char> &(int)' lvalue CXXMethod 0x7fc8a10347d8 'operator<<' 'std::__1::basic_ostream<char> &(int)'
    | | |-DeclRefExpr 0x7fc8a1086f70 <col:3, col:8> 'std::__1::ostream':'std::__1::basic_ostream<char>' lvalue Var 0x7fc8a10864f0 'cout' 'std::__1::ostream':'std::__1::basic_ostream<char>'
    | | `-CallExpr 0x7fc8a1087560 <col:16, col:40> 'int':'int'
    | |   |-ImplicitCastExpr 0x7fc8a1087548 <col:16, col:36> 'int (*)(int)' <FunctionToPointerDecay>
    | |   | `-DeclRefExpr 0x7fc8a1087480 <col:16, col:36> 'int (int)' lvalue Function 0x7fc8a1087368 'fixed_multiply' 'int (int)' (FunctionTemplate 0x7fc8a1086d58 'fixed_multiply')
    | |   `-IntegerLiteral 0x7fc8a1087090 <col:38> 'int' 10
    | `-CharacterLiteral 0x7fc8a1089148 <col:45> 'char' 10
    `-CXXOperatorCallExpr 0x7fc8a108b390 <line:12:3, col:49> 'basic_ostream<char, std::__1::char_traits<char> >':'std::__1::basic_ostream<char>' lvalue
      |-ImplicitCastExpr 0x7fc8a108b378 <col:46> 'basic_ostream<char, std::__1::char_traits<char> > &(*)(basic_ostream<char, std::__1::char_traits<char> > &, char)' <FunctionToPointerDecay>
      | `-DeclRefExpr 0x7fc8a108b358 <col:46> 'basic_ostream<char, std::__1::char_traits<char> > &(basic_ostream<char, std::__1::char_traits<char> > &, char)' lvalue Function 0x7fc8a1088038 'operator<<' 'basic_ostream<char, std::__1::char_traits<char> > &(basic_ostream<char, std::__1::char_traits<char> > &, char)'
      |-CXXOperatorCallExpr 0x7fc8a108ad80 <col:3, col:44> 'std::__1::basic_ostream<char>' lvalue
      | |-ImplicitCastExpr 0x7fc8a108ad68 <col:13> 'std::__1::basic_ostream<char> &(*)(float)' <FunctionToPointerDecay>
      | | `-DeclRefExpr 0x7fc8a108ad18 <col:13> 'std::__1::basic_ostream<char> &(float)' lvalue CXXMethod 0x7fc8a10350d8 'operator<<' 'std::__1::basic_ostream<char> &(float)'
      | |-DeclRefExpr 0x7fc8a1089fa8 <col:3, col:8> 'std::__1::ostream':'std::__1::basic_ostream<char>' lvalue Var 0x7fc8a10864f0 'cout' 'std::__1::ostream':'std::__1::basic_ostream<char>'
      | `-CallExpr 0x7fc8a108a510 <col:16, col:44> 'float':'float'
      |   |-ImplicitCastExpr 0x7fc8a108a4f8 <col:16, col:38> 'float (*)(float)' <FunctionToPointerDecay>
      |   | `-DeclRefExpr 0x7fc8a108a430 <col:16, col:38> 'float (float)' lvalue Function 0x7fc8a108a318 'fixed_multiply' 'float (float)' (FunctionTemplate 0x7fc8a1086d58 'fixed_multiply')
      |   `-ImplicitCastExpr 0x7fc8a108a538 <col:40> 'float':'float' <FloatingCast>
      |     `-FloatingLiteral 0x7fc8a108a0c8 <col:40> 'double' 1.000000e+01
      `-CharacterLiteral 0x7fc8a108adb8 <col:49> 'char' 10