Moved yql/minikql YQL-19206

init

[nodiff:caesar]
commit_hash:d1182ef7d430ccf7e4d37ed933c7126d7bd5d6e4

1 files changed, 659 insertions, 0 deletions

diff --git a/yql/essentials/minikql/mkql_node_visitor.cpp b/yql/essentials/minikql/mkql_node_visitor.cpp
new file mode 100644
index 0000000000..549e26084d
--- /dev/null
+++ b/yql/essentials/minikql/mkql_node_visitor.cpp
@@ -0,0 +1,659 @@
+#include "mkql_node_visitor.h"
+#include "mkql_node.h"
+
+#include <util/generic/algorithm.h>
+
+namespace NKikimr {
+namespace NMiniKQL {
+
+using namespace NDetail;
+
+const ui64 IS_NODE_ENTERED = 1;
+const ui64 IS_NODE_EXITED = 2;
+
+void TThrowingNodeVisitor::Visit(TTypeType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TVoidType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TNullType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TEmptyListType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TEmptyDictType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TDataType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TPgType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TStructType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TListType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TOptionalType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TDictType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TCallableType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TAnyType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TTupleType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TResourceType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TVariantType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TVoid& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TNull& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TEmptyList& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TEmptyDict& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TDataLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TStructLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TListLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TOptionalLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TDictLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TCallable& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TAny& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TTupleLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TVariantLiteral& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TStreamType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TFlowType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TTaggedType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TBlockType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::Visit(TMultiType& node) {
+    Y_UNUSED(node);
+    ThrowUnexpectedNodeType();
+}
+
+void TThrowingNodeVisitor::ThrowUnexpectedNodeType() {
+    THROW yexception() << "Unexpected node type";
+}
+
+void TEmptyNodeVisitor::Visit(TTypeType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TVoidType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TNullType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TEmptyListType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TEmptyDictType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TDataType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TPgType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TStructType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TListType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TOptionalType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TDictType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TCallableType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TAnyType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TTupleType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TResourceType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TVariantType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TVoid& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TNull& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TEmptyList& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TEmptyDict& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TDataLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TStructLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TListLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TOptionalLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TDictLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TCallable& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TAny& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TTupleLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TVariantLiteral& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TStreamType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TFlowType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TTaggedType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TBlockType& node) {
+    Y_UNUSED(node);
+}
+
+void TEmptyNodeVisitor::Visit(TMultiType& node) {
+    Y_UNUSED(node);
+}
+
+void TExploringNodeVisitor::Visit(TTypeType& node) {
+    Y_DEBUG_ABORT_UNLESS(node.GetType() == &node);
+}
+
+void TExploringNodeVisitor::Visit(TVoidType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TNullType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TEmptyListType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TEmptyDictType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TDataType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TPgType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TStructType& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetMembersCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetMemberType(i));
+    }
+}
+
+void TExploringNodeVisitor::Visit(TListType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetItemType());
+}
+
+void TExploringNodeVisitor::Visit(TOptionalType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetItemType());
+}
+
+void TExploringNodeVisitor::Visit(TDictType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetKeyType());
+    AddChildNode(&node, *node.GetPayloadType());
+}
+
+void TExploringNodeVisitor::Visit(TCallableType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetReturnType());
+    for (ui32 i = 0, e = node.GetArgumentsCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetArgumentType(i));
+    }
+
+    if (node.GetPayload()) {
+        AddChildNode(&node, *node.GetPayload());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TAnyType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TTupleType& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetElementsCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetElementType(i));
+    }
+}
+
+void TExploringNodeVisitor::Visit(TResourceType& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TVariantType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetUnderlyingType());
+}
+
+void TExploringNodeVisitor::Visit(TVoid& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TNull& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TEmptyList& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TEmptyDict& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TDataLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+}
+
+void TExploringNodeVisitor::Visit(TStructLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetValuesCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetValue(i).GetNode());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TListLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0; i < node.GetItemsCount(); ++i) {
+        AddChildNode(&node, *node.GetItems()[i].GetNode());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TOptionalLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+    if (node.HasItem()) {
+        AddChildNode(&node, *node.GetItem().GetNode());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TDictLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetItemsCount(); i < e; ++i) {
+        auto item = node.GetItem(i);
+        AddChildNode(&node, *item.first.GetNode());
+        AddChildNode(&node, *item.second.GetNode());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TCallable& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetInputsCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetInput(i).GetNode());
+    }
+
+    if (node.HasResult())
+        AddChildNode(&node, *node.GetResult().GetNode());
+}
+
+void TExploringNodeVisitor::Visit(TAny& node) {
+    AddChildNode(&node, *node.GetType());
+    if (node.HasItem()) {
+        AddChildNode(&node, *node.GetItem().GetNode());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TTupleLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetValuesCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetValue(i).GetNode());
+    }
+}
+
+void TExploringNodeVisitor::Visit(TVariantLiteral& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetItem().GetNode());
+}
+
+void TExploringNodeVisitor::Visit(TStreamType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetItemType());
+}
+
+void TExploringNodeVisitor::Visit(TFlowType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetItemType());
+}
+
+void TExploringNodeVisitor::Visit(TTaggedType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetBaseType());
+}
+
+void TExploringNodeVisitor::Visit(TBlockType& node) {
+    AddChildNode(&node, *node.GetType());
+    AddChildNode(&node, *node.GetItemType());
+}
+
+void TExploringNodeVisitor::Visit(TMultiType& node) {
+    AddChildNode(&node, *node.GetType());
+    for (ui32 i = 0, e = node.GetElementsCount(); i < e; ++i) {
+        AddChildNode(&node, *node.GetElementType(i));
+    }
+}
+
+void TExploringNodeVisitor::AddChildNode(TNode* parent, TNode& child) {
+    Stack->push_back(&child);
+
+    if (BuildConsumersMap) {
+        if (parent != nullptr) {
+            ConsumersMap[&child].push_back(parent);
+        } else {
+            ConsumersMap[&child] = {};
+        }
+    }
+}
+
+void TExploringNodeVisitor::Clear() {
+    NodeList.clear();
+    Stack = nullptr;
+    ConsumersMap.clear();
+}
+
+void TExploringNodeVisitor::Walk(TNode* root, const TTypeEnvironment& env, const std::vector<TNode*>& terminalNodes,
+    bool buildConsumersMap, size_t nodesCountHint)
+{
+    BuildConsumersMap = buildConsumersMap;
+
+    Clear();
+
+    if (BuildConsumersMap && nodesCountHint) {
+        ConsumersMap.reserve(nodesCountHint);
+    }
+
+    Stack = &env.GetNodeStack();
+    Stack->clear();
+    AddChildNode(nullptr, *root);
+    while (!Stack->empty()) {
+        auto node = Stack->back();
+
+        if (node->GetCookie() == 0) {
+            node->SetCookie(IS_NODE_ENTERED);
+
+            if (Find(terminalNodes.begin(), terminalNodes.end(), node) == terminalNodes.end()) {
+                node->Accept(*this);
+            }
+        } else {
+            if (node->GetCookie() == IS_NODE_ENTERED) {
+                NodeList.push_back(node);
+                node->SetCookie(IS_NODE_EXITED);
+            } else {
+                Y_ABORT_UNLESS(node->GetCookie() <= IS_NODE_EXITED, "TNode graph should not be reused");
+            }
+
+            Stack->pop_back();
+            continue;
+        }
+    }
+
+    for (auto node : NodeList) {
+        node->SetCookie(0);
+    }
+
+    Stack = nullptr;
+}
+
+const std::vector<TNode*>& TExploringNodeVisitor::GetNodes() {
+    return NodeList;
+}
+
+const TExploringNodeVisitor::TNodesVec& TExploringNodeVisitor::GetConsumerNodes(TNode& node) {
+    Y_ABORT_UNLESS(BuildConsumersMap);
+    const auto consumers = ConsumersMap.find(&node);
+    Y_ABORT_UNLESS(consumers != ConsumersMap.cend());
+    return consumers->second;
+}
+
+template <bool InPlace>
+TRuntimeNode SinglePassVisitCallablesImpl(TRuntimeNode root, TExploringNodeVisitor& explorer,
+    const TCallableVisitFuncProvider& funcProvider, const TTypeEnvironment& env, bool& wereChanges)
+{
+    auto& nodes = explorer.GetNodes();
+
+    wereChanges = false;
+
+    for (TNode* exploredNode : nodes) {
+        TNode* node;
+        if (!InPlace) {
+            node = exploredNode->CloneOnCallableWrite(env);
+        } else {
+            node = exploredNode;
+            node->Freeze(env);
+        }
+
+        if (node->GetType()->IsCallable()) {
+            auto& callable = static_cast<TCallable&>(*node);
+            if (!callable.HasResult()) {
+                const auto& callableType = callable.GetType();
+                const auto& name = callableType->GetNameStr();
+                const auto& func = funcProvider(name);
+                if (func) {
+                    TRuntimeNode result = func(callable, env);
+                    result.Freeze();
+                    if (result.GetNode() != node) {
+                        if (InPlace) {
+                            callable.SetResult(result, env);
+                            wereChanges = true;
+                        } else {
+                            TNode* wrappedResult = TCallable::Create(result, callable.GetType(), env);
+                            exploredNode->SetCookie((ui64)wrappedResult);
+                        }
+
+                        continue;
+                    }
+                }
+            }
+        }
+
+        if (!InPlace && node != exploredNode) {
+            exploredNode->SetCookie((ui64)node);
+        }
+    }
+
+    if (!InPlace) {
+        auto newRoot = (TNode*)root.GetNode()->GetCookie();
+        if (newRoot) {
+            root = TRuntimeNode(newRoot, root.IsImmediate());
+            wereChanges = true;
+        }
+    }
+
+    root.Freeze();
+    if (!InPlace) {
+        for (TNode* exploredNode : nodes) {
+            exploredNode->SetCookie(0);
+        }
+    }
+
+    return root;
+}
+
+TRuntimeNode SinglePassVisitCallables(TRuntimeNode root, TExploringNodeVisitor& explorer,
+    const TCallableVisitFuncProvider& funcProvider, const TTypeEnvironment& env, bool inPlace, bool& wereChanges) {
+    if (inPlace) {
+        return SinglePassVisitCallablesImpl<true>(root, explorer, funcProvider, env, wereChanges);
+    } else {
+        return SinglePassVisitCallablesImpl<false>(root, explorer, funcProvider, env, wereChanges);
+    }
+}
+
+}
+}