path: root/ydb/library/yql/minikql/mkql_node.h

#pragma once
#include "defs.h"
#include "mkql_mem_info.h"
#include "mkql_alloc.h"

#include <ydb/library/yql/public/udf/udf_value.h>

#include <util/generic/hash.h>
#include <util/generic/hash_set.h>
#include <util/generic/maybe.h>
#include <library/cpp/deprecated/enum_codegen/enum_codegen.h> 

#include <stack>

namespace NKikimr {
namespace NMiniKQL {

class TType;
class INodeVisitor;
class TNode;
class TListLiteral;

template <typename T>
class TTaggedPointer {
public:
    TTaggedPointer() {}
    TTaggedPointer(T* ptr, bool mark) {
        Y_VERIFY_DEBUG((uintptr_t(ptr) & 1) == 0);
        Raw = (void*)(uintptr_t(ptr) | (mark ? 1 : 0));
    }

    T* GetPtr() const {
        return (T*)(uintptr_t(Raw) & ~uintptr_t(1));
    }

    bool GetMark() const {
        return (uintptr_t(Raw) & 1) != 0;
    }

private:
    void* Raw;
};

struct TRuntimeNode {
    using TList = TSmallVec<TRuntimeNode>;

    TRuntimeNode()
        : Data(nullptr, true)
    {}

    TRuntimeNode(TNode* node, bool isImmediate)
        : Data(node, isImmediate)
    {}

    explicit operator bool() const {
        return Data.GetPtr();
    }

    ~TRuntimeNode() {}

    TType* GetRuntimeType() const;

    TType* GetStaticType() const;

    bool HasValue() const;
    TNode* GetValue() const;
    void Freeze();

    bool operator==(const TRuntimeNode& other) const;
    bool operator!=(const TRuntimeNode& other) const {
        return !(*this == other);
    }

    bool IsImmediate() const {
        return Data.GetMark();
    }

    TNode* GetNode() const {
        return Data.GetPtr();
    }

    TTaggedPointer<TNode> Data;
};

using TRuntimeNodePair = std::array<TRuntimeNode, 2U>;

class TTypeEnvironment;

class TNode : private TNonCopyable {
friend class TTypeEnvironment;
public:
    TType* GetType() const {
        return Type;
    }

    TType* GetGenericType() const {
        return Type;
    }

    // may be used only as temporary storage, should be zero before visitation
    ui64 GetCookie() const {
        return Cookie;
    }

    void SetCookie(ui64 cookie) {
        Cookie = cookie;
    }

    void Accept(INodeVisitor& visitor);
    bool Equals(const TNode& nodeToCompare) const;
    void UpdateLinks(const THashMap<TNode*, TNode*>& links);
    // replace map stored in cookies
    TNode* CloneOnCallableWrite(const TTypeEnvironment& env) const;
    void Freeze(const TTypeEnvironment& env);
    bool IsMergeable() const;

protected:
    TNode(TType* type)
        : Type(type)
        , Cookie(0)
    {}

    TType* Type;
    ui64 Cookie;
};

class TTypeType;
class TTypeEnvironment;

// if kind is above 0xf, it must ends with 0x02 pattern (like Void)
#define MKQL_TYPE_KINDS(XX) \
    XX(Type, 0)             \
    XX(Variant, 1)          \
    XX(Void, 2)             \
    XX(Data, 3)             \
    XX(Stream, 4)           \
    XX(Struct, 5)           \
    XX(List, 6)             \
    XX(Optional, 7)         \
    XX(Dict, 8)             \
    XX(Callable, 9)         \
    XX(Any, 10)             \
    XX(Tuple, 11)           \
    XX(Resource, 12)        \
    XX(Flow, 13)            \
    XX(Null, 14)            \
    XX(ReservedKind, 15)    \
    XX(EmptyList, 16 + 2)   \
    XX(EmptyDict, 32 + 2)   \
    XX(Tagged, 48 + 7)      \
    XX(Block, 16 + 13)

class TType : public TNode {
public:
    enum class EKind : ui8 {
        MKQL_TYPE_KINDS(ENUM_VALUE_GEN)
    };

    inline EKind GetKind() const {
        return Kind;
    }

    static TStringBuf KindAsStr(EKind kind);
    TStringBuf GetKindAsStr() const;

#define MKQL_KIND_ACCESSOR(name, value) \
    inline bool Is##name() const { return Kind == EKind::name; }

    MKQL_TYPE_KINDS(MKQL_KIND_ACCESSOR)

#undef MKQL_KIND_ACCESSOR

    bool IsSameType(const TType& typeToCompare) const;
    bool IsConvertableTo(const TType& typeToCompare, bool ignoreTagged = false) const;
    void Accept(INodeVisitor& visitor);
    void UpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* CloneOnCallableWrite(const TTypeEnvironment& env) const;
    void Freeze(const TTypeEnvironment& env);

protected:
    TType(EKind kind, TTypeType* type);
    TType()
        : TNode(nullptr)
        , Kind(EKind::Type)
    {
    }

private:
    const EKind Kind;
};

class TTypeType : public TType {
friend class TTypeEnvironment;
friend class TType;
public:
    using TType::IsSameType;
    bool IsSameType(const TTypeType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TTypeType& typeToCompare, bool ignoreTagged = false) const;

private:
    TTypeType()
        : TType()
    {
    }

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

    static TTypeType* Create(const TTypeEnvironment& env);
};

template <TType::EKind SingularKind>
class TSingularType : public TType {
friend class TTypeEnvironment;
friend class TType;
public:
    using TType::IsSameType;
    bool IsSameType(const TSingularType<SingularKind>& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TSingularType<SingularKind>& typeToCompare, bool ignoreTagged = false) const;

private:
    TSingularType(TTypeType* type)
        : TType(SingularKind, type)
    {}

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

    static TSingularType<SingularKind>* Create(TTypeType* type, const TTypeEnvironment& env);
};

using TVoidType = TSingularType<TType::EKind::Void>;
using TNullType = TSingularType<TType::EKind::Null>;
using TEmptyListType = TSingularType<TType::EKind::EmptyList>;
using TEmptyDictType = TSingularType<TType::EKind::EmptyDict>;

template <TType::EKind SingularKind>
TType* GetTypeOfSingular(const TTypeEnvironment& env);

template <TType::EKind SingularKind>
class TSingular : public TNode {
    friend class TTypeEnvironment;
    friend class TNode;
public:
    TSingularType<SingularKind>* GetType() const {
        return static_cast<TSingularType<SingularKind>*>(GetGenericType());
    }

private:
    TSingular(const TTypeEnvironment& env)
        : TNode(GetTypeOfSingular<SingularKind>(env))
    {}

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

    using TNode::Equals;
    bool Equals(const TSingular<SingularKind>& nodeToCompare) const;
    static TSingular<SingularKind>* Create(const TTypeEnvironment& env);
};

using TVoid = TSingular<TType::EKind::Void>;
using TNull = TSingular<TType::EKind::Null>;
using TEmptyList = TSingular<TType::EKind::EmptyList>;
using TEmptyDict = TSingular<TType::EKind::EmptyDict>;

class TDataLiteral;
class TStructLiteral;
class TListLiteral;
class TOptionalLiteral;
class TAnyType;
class TTupleLiteral;
class TResourceType;
class TDataType;


// A non-owning reference to internalized string
// Created only by TTypeEnvironment::InternName
class TInternName {
public:
    TInternName()
    {}

    TInternName(const TInternName& other)
        : StrBuf(other.StrBuf)
    {}

    const TInternName& operator = (const TInternName& other) {
        StrBuf = other.StrBuf;
        return *this;
    }

    size_t Hash() const {
        return (size_t)StrBuf.data();
    }

    operator bool() const {
        return (bool)StrBuf;
    }

    const TStringBuf& Str() const {
        return StrBuf;
    }

    // Optimized comparison (only by pointer)
    bool operator == (const TInternName& other) const {
        Y_VERIFY_DEBUG(StrBuf.data() != other.StrBuf.data() || StrBuf.size() == other.StrBuf.size(),
                       "Lengths must be equal if pointers are equal");
        return StrBuf.data() == other.StrBuf.data();
    }

    bool operator != (const TInternName& other) const {
        return !this->operator ==(other);
    }

    // Regular comparison (by content)
    bool operator == (const TStringBuf& other) const {
        return StrBuf == other;
    }

    bool operator != (const TStringBuf& other) const {
        return !this->operator ==(other);
    }

private:
    friend class TTypeEnvironment;

    explicit TInternName(const TStringBuf& strBuf)
        : StrBuf(strBuf)
    {}

private:
    TStringBuf StrBuf;
};

}} // namespaces

template <>
struct THash<NKikimr::NMiniKQL::TInternName> {
    size_t operator ()(const NKikimr::NMiniKQL::TInternName& val) const {
        return val.Hash();
    }
};

namespace NKikimr {
namespace NMiniKQL {

class TTypeEnvironment : private TNonCopyable {
public:
    explicit TTypeEnvironment(TScopedAlloc& alloc);

    ~TTypeEnvironment();

    template <typename T>
    T* Allocate() const {
        return (T*)Arena.Alloc(sizeof(T));
    }

    void* AllocateBuffer(ui64 size) const {
        return Arena.Alloc(size);
    }

    TInternName InternName(const TStringBuf& name) const {
        auto it = NamesPool.find(name);
        if (it != NamesPool.end()) {
            return TInternName(*it);
        }

        // Copy to arena and null-terminate
        char* data = (char*)AllocateBuffer(name.size()+1);
        memcpy(data, name.data(), name.size());
        data[name.size()] = 0;

        return TInternName(*NamesPool.insert(TStringBuf(data, name.size())).first);
    }

    TTypeType* GetTypeOfType() const {
        return TypeOfType;
    }

    TVoidType* GetTypeOfVoid() const {
        return TypeOfVoid;
    }

    TVoid* GetVoid() const {
        return Void;
    }

    TNullType* GetTypeOfNull() const {
        return TypeOfNull;
    }

    TNull* GetNull() const {
        return Null;
    }

    TEmptyListType* GetTypeOfEmptyList() const {
        return TypeOfEmptyList;
    }

    TEmptyList* GetEmptyList() const {
        return EmptyList;
    }

    TEmptyDictType* GetTypeOfEmptyDict() const {
        return TypeOfEmptyDict;
    }

    TEmptyDict* GetEmptyDict() const {
        return EmptyDict;
    }

    TStructLiteral* GetEmptyStruct() const {
        return EmptyStruct;
    }

    TListLiteral* GetListOfVoid() const {
        return ListOfVoid;
    }

    TAnyType* GetAnyType() const {
        return AnyType;
    }

    TTupleLiteral* GetEmptyTuple() const {
        return EmptyTuple;
    }

    TDataType* GetUi32() const {
        return Ui32;
    }

    TDataType* GetUi64() const {
        return Ui64;
    }


    std::vector<TNode*>& GetNodeStack() const {
        return Stack;
    }

    void ClearCookies() const;

    NUdf::TUnboxedValuePod NewStringValue(const NUdf::TStringRef& data) const {
        if (data.Size() > NUdf::TUnboxedValue::InternalBufferSize) {
            auto value = NewString(data.Size());
            std::memcpy(value.Data(), data.Data(), data.Size());
            return NUdf::TUnboxedValuePod(std::move(value));
        } else {
            return NUdf::TUnboxedValuePod::Embedded(data);
        }
    }

    TGuard<TScopedAlloc> BindAllocator() const {
        return Guard(Alloc);
    }

    TScopedAlloc& GetAllocator() const { return Alloc; }

    const NUdf::TStringValue& NewString(ui32 size) const {
        Strings.emplace(size);
        return Strings.top();
    }

private:
    TScopedAlloc& Alloc;
    mutable TPagedArena Arena;
    mutable std::stack<NUdf::TStringValue> Strings;
    mutable THashSet<TStringBuf> NamesPool;
    mutable std::vector<TNode*> Stack;

    TTypeType* TypeOfType;
    TVoidType* TypeOfVoid;
    TVoid* Void;
    TNullType* TypeOfNull;
    TNull* Null;
    TEmptyListType* TypeOfEmptyList;
    TEmptyList* EmptyList;
    TEmptyDictType* TypeOfEmptyDict;
    TEmptyDict* EmptyDict;
    TDataType* Ui32;
    TDataType* Ui64;
    TAnyType* AnyType;
    TStructLiteral* EmptyStruct;
    TTupleLiteral* EmptyTuple;
    TListLiteral* ListOfVoid;
};

template <>
inline TType* GetTypeOfSingular<TType::EKind::Void>(const TTypeEnvironment& env) {
    return env.GetTypeOfVoid();
}

template <>
inline TType* GetTypeOfSingular<TType::EKind::Null>(const TTypeEnvironment& env) {
    return env.GetTypeOfNull();
}

template <>
inline TType* GetTypeOfSingular<TType::EKind::EmptyList>(const TTypeEnvironment& env) {
    return env.GetTypeOfEmptyList();
}

template <>
inline TType* GetTypeOfSingular<TType::EKind::EmptyDict>(const TTypeEnvironment& env) {
    return env.GetTypeOfEmptyDict();
}

class TDataType : public TType {
friend class TType;
public:
    static TDataType* Create(NUdf::TDataTypeId schemeType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TDataType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TDataType& typeToCompare, bool ignoreTagged = false) const;

    NUdf::TDataTypeId GetSchemeType() const {
        return SchemeType;
    }

    TMaybe<NUdf::EDataSlot> GetDataSlot() const {
        return DataSlot;
    }

protected:
    TDataType(NUdf::TDataTypeId schemeType, const TTypeEnvironment& env);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    const NUdf::TDataTypeId SchemeType;
    const TMaybe<NUdf::EDataSlot> DataSlot;
};

class TDataDecimalType : public TDataType {
friend class TType;
public:
    static TDataDecimalType* Create(ui8 precision, ui8 scale, const TTypeEnvironment& env);

    bool IsSameType(const TDataDecimalType& typeToCompare) const;

    bool IsConvertableTo(const TDataDecimalType& typeToCompare, bool ignoreTagged = false) const;

    std::pair<ui8, ui8> GetParams() const;
private:
    TDataDecimalType(ui8 precision, ui8 scale, const TTypeEnvironment& env);

    const ui8 Precision;
    const ui8 Scale;
};

class TDataLiteral : public TNode, private NUdf::TUnboxedValuePod {
friend class TNode;
public:
    static TDataLiteral* Create(const NUdf::TUnboxedValuePod& value, TDataType* type, const TTypeEnvironment& env);

    TDataType* GetType() const {
        return static_cast<TDataType*>(GetGenericType());
    }

    const NUdf::TUnboxedValuePod& AsValue() const {
        return *this;
    }

private:
    TDataLiteral(const NUdf::TUnboxedValuePod& value, TDataType* type);
    using TNode::Equals;
    bool Equals(const TDataLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);
};

struct TStructMember {
    TStructMember()
        : Type(nullptr)
        , Index(nullptr)
    {
    }

    TStructMember(const TStringBuf& name, TType* type, ui32* index = nullptr)
        : Name(name)
        , Type(type)
        , Index(index)
    {
    }

    bool operator<(const TStructMember& rhs) const {
        return Name < rhs.Name;
    }

    TStringBuf Name;
    TType* Type;
    ui32* Index;
};

class TStructType : public TType {
friend class TType;
public:
    static TStructType* Create(const std::pair<TString, TType*>* members, ui32 membersCount, const TTypeEnvironment& env);
    static TStructType* Create(ui32 membersCount, const TStructMember* members, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TStructType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TStructType& typeToCompare, bool ignoreTagged = false) const;

    ui32 GetMembersCount() const {
        return MembersCount;
    }

    TStringBuf GetMemberName(ui32 index) const {
        Y_VERIFY_DEBUG(index < MembersCount);
        return Members[index].first.Str();
    }

    TInternName GetMemberNameStr(ui32 index) const {
        Y_VERIFY_DEBUG(index < MembersCount);
        return Members[index].first;
    }

    TType* GetMemberType(ui32 index) const {
        Y_VERIFY_DEBUG(index < MembersCount);
        return Members[index].second;
    }

    ui32 GetMemberIndex(const TStringBuf& name) const;
    TMaybe<ui32> FindMemberIndex(const TStringBuf& name) const;

private:
    TStructType(ui32 membersCount, std::pair<TInternName, TType*>* members, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    ui32 MembersCount;
    std::pair<TInternName, TType*>* Members;
};

class TStructLiteral : public TNode {
friend class TNode;
public:
    static TStructLiteral* Create(ui32 valuesCount, const TRuntimeNode* values, TStructType* type, const TTypeEnvironment& env);
    TStructType* GetType() const {
        return static_cast<TStructType*>(GetGenericType());
    }

    ui32 GetValuesCount() const {
        return GetType()->GetMembersCount();
    }

    TRuntimeNode GetValue(ui32 index) const {
        Y_VERIFY_DEBUG(index < GetValuesCount());
        return Values[index];
    }

private:
    TStructLiteral(TRuntimeNode* values, TStructType* type, bool validate = true);
    using TNode::Equals;
    bool Equals(const TStructLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TRuntimeNode* Values;
};

class TListType : public TType {
friend class TType;
public:
    static TListType* Create(TType* itemType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TListType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TListType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetItemType() const {
        return Data;
    }

    TDataType* IndexDictKeyType() const {
        return IndexDictKey;
    }

private:
    TListType(TType* itemType, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* Data;
    TDataType* IndexDictKey;
};

class TListLiteral : public TNode {
friend class TNode;
public:
    static TListLiteral* Create(TRuntimeNode* items, ui32 count, TListType* type, const TTypeEnvironment& env);
    TListType* GetType() const {
        return static_cast<TListType*>(GetGenericType());
    }

    ui32 GetItemsCount() const {
        return Count;
    }

    TRuntimeNode* GetItems() const {
        return Items;
    }

private:
    TListLiteral(TRuntimeNode* items, ui32 count, TListType* type, const TTypeEnvironment& env, bool validate = true);

    using TNode::Equals;
    bool Equals(const TListLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TRuntimeNode* Items;
    ui32 Count;
};

class TStreamType : public TType {
    friend class TType;
public:
    static TStreamType* Create(TType* itemType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TStreamType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TStreamType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetItemType() const {
        return Data;
    }

private:
    TStreamType(TType* itemType, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* Data;
};

class TFlowType : public TType {
    friend class TType;
public:
    static TFlowType* Create(TType* itemType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TFlowType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TFlowType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetItemType() const {
        return Data;
    }

private:
    TFlowType(TType* itemType, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* Data;
};

class TOptionalType : public TType {
friend class TType;
public:
    static TOptionalType* Create(TType* itemType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TOptionalType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TOptionalType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetItemType() const {
        return Data;
    }

private:
    TOptionalType(TType* itemType, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* Data;
};

class TOptionalLiteral : public TNode {
friend class TNode;
public:
    static TOptionalLiteral* Create(TRuntimeNode item, TOptionalType* type, const TTypeEnvironment& env);
    static TOptionalLiteral* Create(TOptionalType* type, const TTypeEnvironment& env);

    TOptionalType* GetType() const {
        return static_cast<TOptionalType*>(GetGenericType());
    }

    bool HasItem() const {
        return !!Item.GetNode();
    }

    TRuntimeNode GetItem() const {
        Y_VERIFY_DEBUG(Item.GetNode());
        return Item;
    }

private:
    TOptionalLiteral(TRuntimeNode item, TOptionalType* type, bool validate = true);
    TOptionalLiteral(TOptionalType* type, bool validate = true);
    using TNode::Equals;
    bool Equals(const TOptionalLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TRuntimeNode Item;
};

class TDictType : public TType {
friend class TType;
public:
    static TDictType* Create(TType* keyType, TType* payloadType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TDictType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TDictType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetKeyType() const {
        return KeyType;
    }

    TType* GetPayloadType() const {
        return PayloadType;
    }

    static void EnsureValidDictKey(TType* keyType);

private:
    TDictType(TType* keyType, TType* payloadType, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* KeyType;
    TType* PayloadType;
};

class TDictLiteral : public TNode {
    friend class TNode;
public:
    static TDictLiteral* Create(ui32 itemsCount, const std::pair<TRuntimeNode, TRuntimeNode>* items, TDictType* type, const TTypeEnvironment& env);
    TDictType* GetType() const {
        return static_cast<TDictType*>(GetGenericType());
    }

    ui32 GetItemsCount() const {
        return ItemsCount;
    }

    std::pair<TRuntimeNode, TRuntimeNode> GetItem(ui32 index) const {
        Y_VERIFY_DEBUG(index < ItemsCount);
        return Items[index];
    }

private:
    TDictLiteral(ui32 itemsCount, std::pair<TRuntimeNode, TRuntimeNode>* items, TDictType* type, bool validate = true);
    using TNode::Equals;
    bool Equals(const TDictLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    ui32 ItemsCount;
    std::pair<TRuntimeNode, TRuntimeNode>* Items;
};

class TCallableType : public TType {
friend class TType;
public:
    static TCallableType* Create(const TString& name, TType* returnType, ui32 argumentsCount,
        TType** arguments, TNode* payload, const TTypeEnvironment& env);
    static TCallableType* Create(TType* returnType, const TStringBuf& name, ui32 argumentsCount,
        TType** arguments, TNode* payload, const TTypeEnvironment& env);
    void SetOptionalArgumentsCount(ui32 count);
    ui32 GetOptionalArgumentsCount() const {
        return OptionalArgs;
    }

    using TType::IsSameType;
    bool IsSameType(const TCallableType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TCallableType& typeToCompare, bool ignoreTagged = false) const;

    TStringBuf GetName() const {
        return Name.Str();
    }

    TInternName GetNameStr() const {
        return Name;
    }

    TType* GetReturnType() const {
        return ReturnType;
    }

    ui32 GetArgumentsCount() const {
        return ArgumentsCount;
    }

    TType* GetArgumentType(ui32 index) const {
        Y_VERIFY_DEBUG(index < ArgumentsCount);
        return Arguments[index];
    }

    void DisableMerge() {
        IsMergeDisabled0 = true;
    }

    bool IsMergeDisabled() const {
        return IsMergeDisabled0;
    }

    TNode* GetPayload() const {
        return Payload;
    }

private:
    TCallableType(const TInternName& name, TType* returnType, ui32 argumentsCount, TType** arguments,
        TNode* payload, const TTypeEnvironment& env);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    bool IsMergeDisabled0;
    ui32 ArgumentsCount;
    TInternName Name;
    TType* ReturnType;
    TType** Arguments;
    TNode* Payload;
    ui32 OptionalArgs;
};

class TCallable : public TNode {
friend class TNode;
public:
    static TCallable* Create(ui32 inputsCount, const TRuntimeNode* inputs, TCallableType* type, const TTypeEnvironment& env);
    static TCallable* Create(TRuntimeNode result, TCallableType* type, const TTypeEnvironment& env);
    TCallableType* GetType() const {
        return static_cast<TCallableType*>(GetGenericType());
    }

    ui32 GetInputsCount() const {
        return InputsCount;
    }

    TRuntimeNode GetInput(ui32 index) const {
        Y_VERIFY_DEBUG(index < InputsCount);
        return Inputs[index];
    }

    bool HasResult() const {
        return !!Result.GetNode();
    }

    TRuntimeNode GetResult() const {
        Y_VERIFY_DEBUG(!!Result.GetNode());
        return Result;
    }

    void SetResult(TRuntimeNode result, const TTypeEnvironment& env);
    ui32 GetUniqueId() const {
        return UniqueId;
    }

    void SetUniqueId(ui32 uniqueId) {
        UniqueId = uniqueId;
    }

private:
    TCallable(ui32 inputsCount, TRuntimeNode* inputs, TCallableType* type, bool validate = true);
    TCallable(TRuntimeNode result, TCallableType* type, bool validate = true);
    using TNode::Equals;
    bool Equals(const TCallable& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    ui32 InputsCount;
    ui32 UniqueId;
    TRuntimeNode* Inputs;
    TRuntimeNode Result;
};

inline TType::TType(EKind kind, TTypeType* type)
    : TNode(type)
    , Kind(kind)
{
    Y_VERIFY_DEBUG(kind != EKind::Type);
}


inline TType* TRuntimeNode::GetStaticType() const {
    if (IsImmediate()) {
        return GetNode()->GetGenericType();
    } else {
        MKQL_ENSURE(GetNode()->GetType()->IsCallable(), "Wrong type");

        const auto& callable = static_cast<const TCallable&>(*GetNode());
        return callable.GetType()->GetReturnType();
    }
}

class TAnyType : public TType {
friend class TTypeEnvironment;
friend class TType;
public:
    using TType::IsSameType;
    bool IsSameType(const TAnyType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TAnyType& typeToCompare, bool ignoreTagged = false) const;

private:
    TAnyType(TTypeType* type)
        : TType(EKind::Any, type)
    {}

    static TAnyType* Create(TTypeType* type, const TTypeEnvironment& env);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);
};

class TAny : public TNode {
friend class TNode;
public:
    static TAny* Create(const TTypeEnvironment& env);
    TAnyType* GetType() const {
        return static_cast<TAnyType*>(GetGenericType());
    }

    bool HasItem() const {
        return !!Item.GetNode();
    }

    TRuntimeNode GetItem() const {
        Y_VERIFY_DEBUG(Item.GetNode());
        return Item;
    }

    void SetItem(TRuntimeNode newItem);
private:
    TAny(TAnyType* type)
        : TNode(type)
    {}

    using TNode::Equals;
    bool Equals(const TAny& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);
private:
    TRuntimeNode Item;
};

class TTupleType : public TType {
friend class TType;
public:
    static TTupleType* Create(ui32 elementsCount, TType* const* elements, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TTupleType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TTupleType& typeToCompare, bool ignoreTagged = false) const;

    ui32 GetElementsCount() const {
        return ElementsCount;
    }

    TType* GetElementType(ui32 index) const {
        Y_VERIFY_DEBUG(index < ElementsCount);
        return Elements[index];
    }

private:
    TTupleType(ui32 elemntsCount, TType** elements, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    ui32 ElementsCount;
    TType** Elements;
};

class TTupleLiteral : public TNode {
    friend class TNode;
public:
    static TTupleLiteral* Create(ui32 valuesCount, const TRuntimeNode* items, TTupleType* type, const TTypeEnvironment& env);
    TTupleType* GetType() const {
        return static_cast<TTupleType*>(GetGenericType());
    }

    ui32 GetValuesCount() const {
        return GetType()->GetElementsCount();
    }

    TRuntimeNode GetValue(ui32 index) const {
        Y_VERIFY_DEBUG(index < GetValuesCount());
        return Values[index];
    }

private:
    TTupleLiteral(TRuntimeNode* values, TTupleType* type, bool validate = true);
    using TNode::Equals;
    bool Equals(const TTupleLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TRuntimeNode* Values;
};

class TResourceType : public TType {
friend class TTypeEnvironment;
friend class TType;
public:
    using TType::IsSameType;
    bool IsSameType(const TResourceType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TResourceType& typeToCompare, bool ignoreTagged = false) const;

    TStringBuf GetTag() const {
        return Tag.Str();
    }

    TInternName GetTagStr() const {
        return Tag;
    }

    static TResourceType* Create(const TStringBuf& tag, const TTypeEnvironment& env);

private:
    TResourceType(TTypeType* type, TInternName tag)
        : TType(EKind::Resource, type)
        , Tag(tag)
    {}

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TInternName const Tag;
};

class TTaggedType : public TType {
friend class TType;
public:
    static TTaggedType* Create(TType* baseType, const TStringBuf& tag, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TTaggedType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TTaggedType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetBaseType() const {
        return BaseType;
    }

    TStringBuf GetTag() const {
        return Tag.Str();
    }

    TInternName GetTagStr() const {
        return Tag;
    }

private:
    TTaggedType(TType* baseType, TInternName tag, const TTypeEnvironment& env);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* BaseType;
    TInternName const Tag;
};

class TVariantType : public TType {
    friend class TType;
public:
    static TVariantType* Create(TType* underlyingType, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TVariantType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TVariantType& typeToCompare, bool ignoreTagged = false) const;

    TType* GetUnderlyingType() const {
        return Data;
    }

    ui32 GetAlternativesCount() const {
        if (Data->IsStruct()) {
            return static_cast<TStructType*>(Data)->GetMembersCount();
        } else {
            return static_cast<TTupleType*>(Data)->GetElementsCount();
        }
    }

    TType* GetAlternativeType(ui32 index) const {
        MKQL_ENSURE(index < GetAlternativesCount(), "Wrong index");
        if (Data->IsStruct()) {
            return static_cast<TStructType*>(Data)->GetMemberType(index);
        } else {
            return static_cast<TTupleType*>(Data)->GetElementType(index);
        }
    }

private:
    TVariantType(TType* underlyingType, const TTypeEnvironment& env, bool validate = true);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* Data;
};

class TVariantLiteral : public TNode {
    friend class TNode;
public:
    static TVariantLiteral* Create(TRuntimeNode item, ui32 index, TVariantType* type, const TTypeEnvironment& env);

    TVariantType* GetType() const {
        return static_cast<TVariantType*>(GetGenericType());
    }

    ui32 GetIndex() const {
        return Index;
    }

    TRuntimeNode GetItem() const {
        return Item;
    }

private:
    TVariantLiteral(TRuntimeNode item, ui32 index, TVariantType* type, bool validate = true);
    using TNode::Equals;
    bool Equals(const TVariantLiteral& nodeToCompare) const;

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TRuntimeNode Item;
    ui32 Index;
};

class TBlockType : public TType {
    friend class TType;

public:
    enum class EShape: ui8 {
        Single = 0,
        Many = 1
    };

public:
    static TBlockType* Create(TType* itemType, EShape shape, const TTypeEnvironment& env);

    using TType::IsSameType;
    bool IsSameType(const TBlockType& typeToCompare) const;

    using TType::IsConvertableTo;
    bool IsConvertableTo(const TBlockType& typeToCompare, bool ignoreTagged = false) const;

    inline TType* GetItemType() const noexcept {
        return ItemType;
    }

    inline EShape GetShape() const noexcept {
        return Shape;
    }

private:
    TBlockType(TType* itemType, EShape shape, const TTypeEnvironment& env);

    void DoUpdateLinks(const THashMap<TNode*, TNode*>& links);
    TNode* DoCloneOnCallableWrite(const TTypeEnvironment& env) const;
    void DoFreeze(const TTypeEnvironment& env);

private:
    TType* ItemType;
    EShape Shape;
};

inline bool TRuntimeNode::operator==(const TRuntimeNode& other) const {
    return IsImmediate() == other.IsImmediate() && GetNode()->Equals(*other.GetNode());
}

inline TType* TRuntimeNode::GetRuntimeType() const {
    return GetNode()->GetGenericType();
}

bool IsNumericType(NUdf::TDataTypeId typeId);
bool IsCommonStringType(NUdf::TDataTypeId typeId);
bool IsDateType(NUdf::TDataTypeId typeId);
bool IsTzDateType(NUdf::TDataTypeId typeId);
bool IsIntervalType(NUdf::TDataTypeId typeId);

enum class EValueRepresentation {
    Embedded = 0,
    String = 1,
    Boxed = 2,
    Any = String | Boxed
};

EValueRepresentation GetValueRepresentation(const TType* type);
EValueRepresentation GetValueRepresentation(NUdf::TDataTypeId typeId);

template <TType::EKind SingularKind>
TSingularType<SingularKind>* TSingularType<SingularKind>::Create(TTypeType* type, const TTypeEnvironment& env) {
    return ::new(env.Allocate<TSingularType<SingularKind>>()) TSingularType<SingularKind>(type);
}

template <TType::EKind SingularKind>
bool TSingularType<SingularKind>::IsSameType(const TSingularType<SingularKind>& typeToCompare) const {
    Y_UNUSED(typeToCompare);
    return true;
}

template <TType::EKind SingularKind>
bool TSingularType<SingularKind>::IsConvertableTo(const TSingularType<SingularKind>& typeToCompare, bool ignoreTagged) const {
    Y_UNUSED(ignoreTagged);
    return IsSameType(typeToCompare);
}

template <TType::EKind SingularKind>
void TSingularType<SingularKind>::DoUpdateLinks(const THashMap<TNode*, TNode*>& links) {
    Y_UNUSED(links);
}

template <TType::EKind SingularKind>
TNode* TSingularType<SingularKind>::DoCloneOnCallableWrite(const TTypeEnvironment& env) const {
    Y_UNUSED(env);
    return const_cast<TSingularType<SingularKind>*>(this);
}

template <TType::EKind SingularKind>
void TSingularType<SingularKind>::DoFreeze(const TTypeEnvironment& env) {
    Y_UNUSED(env);
}

template <TType::EKind SingularKind>
TSingular<SingularKind>* TSingular<SingularKind>::Create(const TTypeEnvironment& env) {
    return ::new(env.Allocate<TSingular<SingularKind>>()) TSingular<SingularKind>(env);
}

template <TType::EKind SingularKind>
bool TSingular<SingularKind>::Equals(const TSingular<SingularKind>& nodeToCompare) const {
    Y_UNUSED(nodeToCompare);
    return true;
}

template <TType::EKind SingularKind>
void TSingular<SingularKind>::DoUpdateLinks(const THashMap<TNode*, TNode*>& links) {
    Y_UNUSED(links);
}

template <TType::EKind SingularKind>
TNode* TSingular<SingularKind>::DoCloneOnCallableWrite(const TTypeEnvironment& env) const {
    Y_UNUSED(env);
    return const_cast<TSingular<SingularKind>*>(this);
}

template <TType::EKind SingularKind>
void TSingular<SingularKind>::DoFreeze(const TTypeEnvironment& env) {
    Y_UNUSED(env);
}

}
}