summaryrefslogtreecommitdiff
path: root/src/vm/generics.h
blob: dfd91ef829a931db78de9106c72f2f4614a4e8f6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
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