1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4//
5// File: generics.cpp
6//
7
8
9//
10// Helper functions for generics prototype
11//
12
13//
14// ============================================================================
15
16#ifndef _GENERICS_H
17#define _GENERICS_H
18
19#include "typehandle.h"
20#include "arraylist.h"
21
22class CrawlFrame;
23class DictionaryEntryLayout;
24
25// Generics helper functions
26namespace Generics
27{
28 // Part of the recursive inheritance graph as defined by ECMA part.II Section 9.2.
29 //
30 // code:MethodTable.DoFullyLoad and code:TypeDesc.DoFullyLoad declare local variable of
31 // this type and initialize it with:
32 // - pointer to the previous (in terms of callstack) RecursionGraph instance,
33 // - the type handle representing the type that is being fully-loaded.
34 //
35 // By walking the RecursionGraph chain, it is possible to tell whether the same type is
36 // not being fully-loaded already. So far this could as well be a description of the
37 // code:TypeHandleList. But aside from the "owner type", RecursionGraph can also hold
38 // part of a directed graph in which nodes are generic variables and edges represent the
39 // is-substituted-by relation. In particular, one RecursionGraph instance maintains nodes
40 // corresponding to generic variables declared by the owner type, and all edges going
41 // out of these nodes.
42 //
43 // As an example consider:
44 // class B<U> { }
45 // class A<T> : B<T> { }
46 //
47 // B's RecursionGraph has one node (U) and no edges. A's RecursionGraph has one node (T)
48 // and one edge from T to U.
49 //
50 // This is how it looks like on the stack:
51 //
52 // A's DoFullyLoad activation - RecursionGraph(NULL, A<>) -> [T]
53 // ^-------- |
54 // | v
55 // B's DoFullyLoad activation - RecursionGraph( | , B<>) -> [U]
56 //
57 // The edges are obviously not real pointers because the destination may not yet be
58 // present on the stack when the edge is being added. Instead the edge end points are
59 // identified by TypeVarTypeDesc pointers. Edges come in two flavors - non-expanding
60 // and expanding, please see ECMA for detailed explanation. Finding an expanding cycle
61 // (i.e. cycle with at least one expanding edge) in the graph means that the types
62 // currently on stack are defined recursively and should be refused by the loader.
63 // Reliable detection of this condition is the ultimate purpose of this class.
64 //
65 // We do not always see all dependencies of a type on the stack. If the dependencies
66 // have been loaded earlier, loading stops there and part of the graph may be missing.
67 // However, this is of no concern because we are only interested in types with cyclic
68 // dependencies, and loading any type from such a closure will cause loading the rest
69 // of it. If part of the rest had been loaded earlier, it would have triggered loading
70 // the current type so there's really no way how expanding cycles can go undetected.
71 //
72 // Observation: if there is a cycle in type dependencies, there will be a moment when
73 // we'll have all the types participating in the cycle on the stack.
74 //
75 // Note that having a cycle in type dependencies is OK as long as it is not an expanding
76 // cycle. The simplest example of a cycle that is not expanding is A<T> : B<A<T>>. That
77 // is a perfectly valid type.
78 //
79 // The most interesting methods in this class are:
80 // * code:RecursionGraph.AddDependency - adds edges according to a type's instantiation.
81 // * code:RecursionGraph.HasExpandingCycle - looks for expanding cycles in the graph.
82 //
83 class RecursionGraph
84 {
85 public:
86 // Just records the owner and links to the previous graph. To actually construct the
87 // graph, call CheckForIllegalRecursion. Without CheckForIllegalRecursion, the
88 // functionality is limited to that of code:TypeHandleList.
89 RecursionGraph(RecursionGraph *pPrev, TypeHandle thOwner);
90 ~RecursionGraph();
91
92 // Adds edges generated by the parent and implemented interfaces; returns TRUE iff
93 // an expanding cycle was found after adding the edges.
94 BOOL CheckForIllegalRecursion();
95
96 // Returns TRUE iff the given type is already on the stack (in fact an analogue of
97 // code:TypeHandleList.Exists). This is to prevent recursively loading exactly the
98 // same type.
99 static BOOL HasSeenType(RecursionGraph *pDepGraph, TypeHandle thType);
100
101#ifndef DACCESS_COMPILE
102 protected:
103 // Adds the specified MT as a dependency (parent or interface) of the owner.
104 // pExpansionVars used internally.
105 void AddDependency(MethodTable *pMT, TypeHandleList *pExpansionVars = NULL);
106
107 // Adds an edge from pFromVar to pToVar, non-expanding or expanding.
108 void AddEdge(TypeVarTypeDesc *pFromVar, TypeVarTypeDesc *pToVar, BOOL fExpanding);
109
110 // Represents a node (a generic variable).
111 class Node
112 {
113 friend class RecursionGraph;
114
115 union
116 {
117 TypeVarTypeDesc *m_pFromVar; // The generic variable represented by this node.
118 ULONG_PTR m_pFromVarAsPtr; // The lowest bit determines the is-visited state.
119 };
120 ArrayList m_edges; // The outgoing edges (pointers to TypeVarTypeDesc).
121
122 enum
123 {
124 NODE_VISITED_FLAG = 0x1, // ORed with m_pFromVar if this node is currently being visited.
125 EDGE_EXPANDING_FLAG = 0x1 // ORed with an m_edges element if the edge is expanding.
126 };
127
128 public:
129 Node() : m_pFromVar(NULL)
130 { LIMITED_METHOD_CONTRACT; }
131
132 inline ArrayList *GetEdges() { LIMITED_METHOD_CONTRACT; return &m_edges; }
133 inline TypeVarTypeDesc *GetSourceVar() { LIMITED_METHOD_CONTRACT; return ((TypeVarTypeDesc *)(m_pFromVarAsPtr & ~NODE_VISITED_FLAG)); }
134 inline void SetSourceVar(TypeVarTypeDesc *pVar) { LIMITED_METHOD_CONTRACT; _ASSERTE(!m_pFromVar); m_pFromVar = pVar; }
135
136 inline BOOL IsVisited() { LIMITED_METHOD_CONTRACT; return (m_pFromVarAsPtr & NODE_VISITED_FLAG); }
137 inline void SetVisited() { LIMITED_METHOD_CONTRACT; m_pFromVarAsPtr |= NODE_VISITED_FLAG; }
138 inline void ClearVisited() { LIMITED_METHOD_CONTRACT; m_pFromVarAsPtr &= ~NODE_VISITED_FLAG; }
139 };
140
141 // Recursive worker that checks whether a node is part of an expanding cycle.
142 BOOL HasExpandingCycle(Node *pCurrentNode, Node *pStartNode, BOOL fExpanded = FALSE);
143
144 protected:
145 // Array of nodes, each representing a generic variable owned by m_thOwner. The
146 // number of nodes is m_thOwner.GetNumGenericArgs() and the order corresponds
147 // to m_thOwner's instantiation.
148 Node *m_pNodes;
149#endif // !DACCESS_COMPILE
150
151 protected:
152 RecursionGraph *m_pPrev;
153 TypeHandle m_thOwner;
154 };
155
156 // Check for legal instantiations. Returns true if the instantiation is legal.
157 BOOL CheckInstantiation(Instantiation inst);
158
159 BOOL GetExactInstantiationsOfMethodAndItsClassFromCallInformation(
160 /* in */ MethodDesc *pRepMethod,
161 /* in */ OBJECTREF pThis,
162 /* in */ PTR_VOID pParamTypeArg,
163 /* out*/ TypeHandle *pSpecificClass,
164 /* out*/ MethodDesc** pSpecificMethod);
165
166 BOOL GetExactInstantiationsOfMethodAndItsClassFromCallInformation(
167 /* in */ MethodDesc *pRepMethod,
168 /* in */ PTR_VOID pExactGenericArgsToken,
169 /* out*/ TypeHandle *pSpecificClass,
170 /* out*/ MethodDesc** pSpecificMethod);
171
172 inline void DetermineCCWTemplateAndGUIDPresenceOnNonCanonicalMethodTable(
173 // Input
174 MethodTable *pOldMT,
175 BOOL fNewMTContainsGenericVariables,
176 // Output
177 BOOL *pfHasGuidInfo, BOOL *pfHasCCWTemplate);
178};
179
180#endif
181