// 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