diff options
Diffstat (limited to 'src/vm/generics.h')
| -rw-r--r-- | src/vm/generics.h | 180 |
1 files changed, 180 insertions, 0 deletions
diff --git a/src/vm/generics.h b/src/vm/generics.h new file mode 100644 index 0000000000..dfd91ef829 --- /dev/null +++ b/src/vm/generics.h @@ -0,0 +1,180 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. +// +// File: generics.cpp +// + + +// +// Helper functions for generics prototype +// + +// +// ============================================================================ + +#ifndef _GENERICS_H +#define _GENERICS_H + +#include "typehandle.h" +#include "arraylist.h" + +class CrawlFrame; +class DictionaryEntryLayout; + +// Generics helper functions +namespace Generics +{ + // Part of the recursive inheritance graph as defined by ECMA part.II Section 9.2. + // + // code:MethodTable.DoFullyLoad and code:TypeDesc.DoFullyLoad declare local variable of + // this type and initialize it with: + // - pointer to the previous (in terms of callstack) RecursionGraph instance, + // - the type handle representing the type that is being fully-loaded. + // + // By walking the RecursionGraph chain, it is possible to tell whether the same type is + // not being fully-loaded already. So far this could as well be a description of the + // code:TypeHandleList. But aside from the "owner type", RecursionGraph can also hold + // part of a directed graph in which nodes are generic variables and edges represent the + // is-substituted-by relation. In particular, one RecursionGraph instance maintains nodes + // corresponding to generic variables declared by the owner type, and all edges going + // out of these nodes. + // + // As an example consider: + // class B<U> { } + // class A<T> : B<T> { } + // + // B's RecursionGraph has one node (U) and no edges. A's RecursionGraph has one node (T) + // and one edge from T to U. + // + // This is how it looks like on the stack: + // + // A's DoFullyLoad activation - RecursionGraph(NULL, A<>) -> [T] + // ^-------- | + // | v + // B's DoFullyLoad activation - RecursionGraph( | , B<>) -> [U] + // + // The edges are obviously not real pointers because the destination may not yet be + // present on the stack when the edge is being added. Instead the edge end points are + // identified by TypeVarTypeDesc pointers. Edges come in two flavors - non-expanding + // and expanding, please see ECMA for detailed explanation. Finding an expanding cycle + // (i.e. cycle with at least one expanding edge) in the graph means that the types + // currently on stack are defined recursively and should be refused by the loader. + // Reliable detection of this condition is the ultimate purpose of this class. + // + // We do not always see all dependencies of a type on the stack. If the dependencies + // have been loaded earlier, loading stops there and part of the graph may be missing. + // However, this is of no concern because we are only interested in types with cyclic + // dependencies, and loading any type from such a closure will cause loading the rest + // of it. If part of the rest had been loaded earlier, it would have triggered loading + // the current type so there's really no way how expanding cycles can go undetected. + // + // Observation: if there is a cycle in type dependencies, there will be a moment when + // we'll have all the types participating in the cycle on the stack. + // + // Note that having a cycle in type dependencies is OK as long as it is not an expanding + // cycle. The simplest example of a cycle that is not expanding is A<T> : B<A<T>>. That + // is a perfectly valid type. + // + // The most interesting methods in this class are: + // * code:RecursionGraph.AddDependency - adds edges according to a type's instantiation. + // * code:RecursionGraph.HasExpandingCycle - looks for expanding cycles in the graph. + // + class RecursionGraph + { + public: + // Just records the owner and links to the previous graph. To actually construct the + // graph, call CheckForIllegalRecursion. Without CheckForIllegalRecursion, the + // functionality is limited to that of code:TypeHandleList. + RecursionGraph(RecursionGraph *pPrev, TypeHandle thOwner); + ~RecursionGraph(); + + // Adds edges generated by the parent and implemented interfaces; returns TRUE iff + // an expanding cycle was found after adding the edges. + BOOL CheckForIllegalRecursion(); + + // Returns TRUE iff the given type is already on the stack (in fact an analogue of + // code:TypeHandleList.Exists). This is to prevent recursively loading exactly the + // same type. + static BOOL HasSeenType(RecursionGraph *pDepGraph, TypeHandle thType); + +#ifndef DACCESS_COMPILE + protected: + // Adds the specified MT as a dependency (parent or interface) of the owner. + // pExpansionVars used internally. + void AddDependency(MethodTable *pMT, TypeHandleList *pExpansionVars = NULL); + + // Adds an edge from pFromVar to pToVar, non-expanding or expanding. + void AddEdge(TypeVarTypeDesc *pFromVar, TypeVarTypeDesc *pToVar, BOOL fExpanding); + + // Represents a node (a generic variable). + class Node + { + friend class RecursionGraph; + + union + { + TypeVarTypeDesc *m_pFromVar; // The generic variable represented by this node. + ULONG_PTR m_pFromVarAsPtr; // The lowest bit determines the is-visited state. + }; + ArrayList m_edges; // The outgoing edges (pointers to TypeVarTypeDesc). + + enum + { + NODE_VISITED_FLAG = 0x1, // ORed with m_pFromVar if this node is currently being visited. + EDGE_EXPANDING_FLAG = 0x1 // ORed with an m_edges element if the edge is expanding. + }; + + public: + Node() : m_pFromVar(NULL) + { LIMITED_METHOD_CONTRACT; } + + inline ArrayList *GetEdges() { LIMITED_METHOD_CONTRACT; return &m_edges; } + inline TypeVarTypeDesc *GetSourceVar() { LIMITED_METHOD_CONTRACT; return ((TypeVarTypeDesc *)(m_pFromVarAsPtr & ~NODE_VISITED_FLAG)); } + inline void SetSourceVar(TypeVarTypeDesc *pVar) { LIMITED_METHOD_CONTRACT; _ASSERTE(!m_pFromVar); m_pFromVar = pVar; } + + inline BOOL IsVisited() { LIMITED_METHOD_CONTRACT; return (m_pFromVarAsPtr & NODE_VISITED_FLAG); } + inline void SetVisited() { LIMITED_METHOD_CONTRACT; m_pFromVarAsPtr |= NODE_VISITED_FLAG; } + inline void ClearVisited() { LIMITED_METHOD_CONTRACT; m_pFromVarAsPtr &= ~NODE_VISITED_FLAG; } + }; + + // Recursive worker that checks whether a node is part of an expanding cycle. + BOOL HasExpandingCycle(Node *pCurrentNode, Node *pStartNode, BOOL fExpanded = FALSE); + + protected: + // Array of nodes, each representing a generic variable owned by m_thOwner. The + // number of nodes is m_thOwner.GetNumGenericArgs() and the order corresponds + // to m_thOwner's instantiation. + Node *m_pNodes; +#endif // !DACCESS_COMPILE + + protected: + RecursionGraph *m_pPrev; + TypeHandle m_thOwner; + }; + + // Check for legal instantiations. Returns true if the instantiation is legal. + BOOL CheckInstantiation(Instantiation inst); + + BOOL GetExactInstantiationsOfMethodAndItsClassFromCallInformation( + /* in */ MethodDesc *pRepMethod, + /* in */ OBJECTREF pThis, + /* in */ PTR_VOID pParamTypeArg, + /* out*/ TypeHandle *pSpecificClass, + /* out*/ MethodDesc** pSpecificMethod); + + BOOL GetExactInstantiationsOfMethodAndItsClassFromCallInformation( + /* in */ MethodDesc *pRepMethod, + /* in */ PTR_VOID pExactGenericArgsToken, + /* out*/ TypeHandle *pSpecificClass, + /* out*/ MethodDesc** pSpecificMethod); + + inline void DetermineCCWTemplateAndGUIDPresenceOnNonCanonicalMethodTable( + // Input + MethodTable *pOldMT, + BOOL fNewMTContainsGenericVariables, + // Output + BOOL *pfHasGuidInfo, BOOL *pfHasCCWTemplate); +}; + +#endif |