<commit_before>//*****************************************************************************
// Copyright 2017-2019 Intel Corporation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//*****************************************************************************

#pragma once

#include <deque>
#include <functional>
#include <list>
#include <memory>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "ngraph/check.hpp"
#include "ngraph/function.hpp"
#include "ngraph/node.hpp"
#include "ngraph/placement.hpp"

namespace ngraph
{
    namespace descriptor
    {
        class Input;
        class Output;
    }

    namespace op
    {
        class Parameter;
    }

    void traverse_nodes(const std::shared_ptr<const Function> p,
                        std::function<void(std::shared_ptr<Node>)> f,
                        bool include_control_deps = false);

    void traverse_nodes(const Function* p,
                        std::function<void(std::shared_ptr<Node>)> f,
                        bool include_control_deps);

    /// \brief Visit each node in a sub-graph of the entire graph
    /// \param subgraph_results The output nodes of the sub-graph
    /// \param f Function to execute at each node in the traversal
    /// \param include_control_deps Whether to include control deps
    ///        while traversing the sub-graph
    /// \param subgraph_params Input nodes of the sub-graph (optional)
    ///
    /// Traverses a sub-graph starting from subgraph_results moving up
    /// towards parameter nodes. Traversal stops if it hits a node in
    /// subgraph_params.
    ///
    /// Most useful for finding parameters of a graph directly from the
    /// result nodes and not from function parameters or extracting a
    /// subgraph relevant to the computation of certain outputs
    void traverse_nodes(const NodeVector& subgraph_results,
                        std::function<void(std::shared_ptr<Node>)> f,
                        bool include_control_deps,
                        const NodeVector& subgraph_params = {});

    inline void traverse_functions(std::shared_ptr<Function> p,
                                   std::function<void(std::shared_ptr<Function>)> f)
        NGRAPH_DEPRECATED("Replace with f(p)")
    {
        f(p);
    };

    /// All users (inputs and control dependencies) of target are replace with replacement
    void replace_node(std::shared_ptr<Node> target, std::shared_ptr<Node> replacement);

    NodeVector find_common_args(std::shared_ptr<Node> target, std::shared_ptr<Node> replacement);

    /// Topological sort of nodes needed to compute root_nodes
    template <typename T>
    std::list<std::shared_ptr<Node>> topological_sort(T root_nodes,<commit_msg>Some docstrings for replace_node (#3244)<commit_after>//*****************************************************************************
// Copyright 2017-2019 Intel Corporation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//*****************************************************************************

#pragma once

#include <deque>
#include <functional>
#include <list>
#include <memory>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "ngraph/check.hpp"
#include "ngraph/function.hpp"
#include "ngraph/node.hpp"
#include "ngraph/placement.hpp"

namespace ngraph
{
    namespace descriptor
    {
        class Input;
        class Output;
    }

    namespace op
    {
        class Parameter;
    }

    void traverse_nodes(const std::shared_ptr<const Function> p,
                        std::function<void(std::shared_ptr<Node>)> f,
                        bool include_control_deps = false);

    void traverse_nodes(const Function* p,
                        std::function<void(std::shared_ptr<Node>)> f,
                        bool include_control_deps);

    /// \brief Visit each node in a sub-graph of the entire graph
    /// \param subgraph_results The output nodes of the sub-graph
    /// \param f Function to execute at each node in the traversal
    /// \param include_control_deps Whether to include control deps
    ///        while traversing the sub-graph
    /// \param subgraph_params Input nodes of the sub-graph (optional)
    ///
    /// Traverses a sub-graph starting from subgraph_results moving up
    /// towards parameter nodes. Traversal stops if it hits a node in
    /// subgraph_params.
    ///
    /// Most useful for finding parameters of a graph directly from the
    /// result nodes and not from function parameters or extracting a
    /// subgraph relevant to the computation of certain outputs
    void traverse_nodes(const NodeVector& subgraph_results,
                        std::function<void(std::shared_ptr<Node>)> f,
                        bool include_control_deps,
                        const NodeVector& subgraph_params = {});

    inline void traverse_functions(std::shared_ptr<Function> p,
                                   std::function<void(std::shared_ptr<Function>)> f)
        NGRAPH_DEPRECATED("Replace with f(p)")
    {
        f(p);
    };

    /// \brief Replace the node `target` with the node `replacement`, i.e.,
    ///        redirect all users and control dependencies of `target` to
    ///        `replacement`.
    ///
    /// \param target Node to be replaced.
    /// \param replacement Node to replace `target` with.
    ///
    /// This is primarily used in graph-rewriting passes. For example, we
    /// might "fuse" two Concat operations as follows:
    ///
    /// (Step 0: Original graph)
    ///
    ///   A                       B
    ///   |                       |
    ///   v                       v
    /// N0[Concat, concatenation_axis=3]     C
    ///          |                           |
    ///          v                           v
    ///        N1[Concat, concatenation_axis=3]
    ///          |                |
    ///          v                v
    ///       some_user         another_user
    ///
    /// (Step 1: Construct replacement)
    ///
    ///    shared_ptr<Node> new_N1 = make_shared<op::Concat>({A,B,C},3);
    ///
    ///   A----------------------------------------.
    ///   |                                        |
    ///   |                       B----------------)--.
    ///   |                       |                |  |
    ///   v                       v                |  |
    /// N0[Concat, concatenation_axis=3]     C-----)--)--.
    ///          |                           |     |  |  |
    ///          v                           v     v  v  v
    ///        N1[Concat, concatenation_axis=3]   new_N1[Concat, concatenation_axis=3]
    ///          |                |
    ///          v                v
    ///       some_user         another_user
    ///
    /// (Step 2: Replace N1 with new_N1)
    ///
    ///    replace_node(N1, new_N1);
    ///
    ///   A----------------------------------------.
    ///   |                                        |
    ///   |                       B----------------)--.
    ///   |                       |                |  |
    ///   v                       v                |  |
    /// N0[Concat, concatenation_axis=3]     C-----)--)--.
    ///          |                           |     |  |  |
    ///          v                           v     v  v  v
    ///        N1[Concat, concatenation_axis=3]   new_N1[Concat, concatenation_axis=3]
    ///                                                  |                |
    ///                                                  v                v
    ///                                               some_user         another_user
    ///
    /// (Step 3: N0 and N1 are now dead, nodes will be freed)
    ///
    ///    [happens automatically, once all shared_ptrs to N1 are released]
    ///
    ///   A----------------------------------------.
    ///                                            |
    ///                           B----------------)--.
    ///                                            |  |
    ///                                            |  |
    ///                                      C-----)--)--.
    ///                                            |  |  |
    ///                                            v  v  v
    ///                                           new_N1[Concat, concatenation_axis=3]
    ///                                                  |                |
    ///                                                  v                v
    ///                                               some_user         another_user
    ///
    /// NOTE 1: replace_node is not type-safe (the graph is not revalidated).
    /// For example, the following is allowed, even if node `some_user`
    /// requires an input of shape 2x2:
    ///
    /// (Before)
    ///      A(shape=2x2)  B(shape=3x3)
    ///      |
    ///      v
    ///   some_user(requires 2x2 input)
    ///
    /// (After -- graph is now invalid)
    ///
    ///      replace_node(A, B);
    ///
    ///      A(shape=2x2)  B(shape=3x3)
    ///                    |
    ///                    v
    ///                 some_user(requires 2x2 input)
    ///
    /// NOTE 2: it is possible to insert a cycle into the graph with
    /// replace_node, resulting in an invalid graph. Care must be taken to
    /// avoid this. One common example is when you are attempting to insert a
    /// new node `M` "after"` a node `N`. For example, you might expect this
    /// to work:
    ///
    ///    shared_ptr<Node> M = make_shared<SomeUnaryOp>(N);
    ///    replace_node(M, N);
    ///
    /// The problem is that at replacement time, N itself is a user of M. So
    /// we end up introducing a cycle as follows:
    ///
    ///       N
    ///       |
    ///       v
    ///  other users...
    ///
    ///      |||
    ///      vvv
    ///
    ///       N------------>M
    ///       |
    ///       v
    ///  other users...
    ///
    ///      |||
    ///      vvv
    ///
    ///               .----.
    ///              |      |
    ///              |      |
    ///       N      `----->M
    ///                     |
    ///                     v
    ///                other users...
    ///
    /// To avoid the cycle, a valid way to perform the above desired insertion would be,
    ///
    ///        auto new_N = N->copy_with_new_args(N->get_arguments());
    ///        shared_ptr<Node> M = make_shared<SomeUnaryOp>(new_N);
    ///        replace_node(N, M);
    void replace_node(std::shared_ptr<Node> target, std::shared_ptr<Node> replacement);

    NodeVector find_common_args(std::shared_ptr<Node> target, std::shared_ptr<Node> replacement);

    /// Topological sort of nodes needed to compute root_nodes
    template <typename T>
    std::list<std::shared_ptr<Node>> topological_sort(T root_nodes,
{'fraction_non_alphanumeric': 0.15194227703666416, 'fraction_numerical': 0.006292474200855777, 'mean_word_length': 1.316362223085892, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 65, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 54, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4505939', 'n_tokens_mistral': 3115, 'n_tokens_neox': 2977, 'n_words': 905}