Function HashSubgraphImpl

tensorflow/core/kernels/data/dataset_utils.cc:200–267

This function hashes a subgraph (rooted at node) by traversing all possible dependency paths from that node.

// This function hashes a subgraph (rooted at node) by traversing all possible
// dependency paths from that node.
uint64 HashSubgraphImpl(const grappler::GraphView& g, const NodeDef* node,
                        std::vector<std::string>* visited,
                        absl::flat_hash_map<std::string, uint64>* cache) {
  uint64 input_hash = 0;
  uint64 control_dep_hash = 0;

  std::string canonical_node_name = absl::StrCat("node-", node->name());
  auto it = cache->find(canonical_node_name);
  if (it != cache->end()) {
    return it->second;
  }

  uint64 op_hash = Hash64(node->op());

  // Checks to make sure we won't get stuck in an infinite loop (especially in
  // loops with control dependencies).
  for (const std::string& visited_node_name : *visited) {
    if (visited_node_name == canonical_node_name) {
      uint64 final_hash =
          Hash64Combine(DefaultDependencyLoopNodeHash(), op_hash);
      (*cache)[canonical_node_name] = final_hash;
      return final_hash;
    }
  }
  visited->push_back(canonical_node_name);

  for (int i = 0; i < node->input_size(); ++i) {
    DCHECK_GT(node->input(i).length(), 0);
    if (node->input(i)[0] == '^') {
      // TODO(frankchn): Investigate if control dependencies are necessary
      // inputs to the hash.
      // Control dependency node names start with '^', and order of appearance
      // for the control dependencies does not matter.
      control_dep_hash = Hash64CombineUnordered(
          control_dep_hash,
          HashSubgraphImpl(g, g.GetNode(node->input(i).substr(1)), visited,
                           cache));
    } else {
      // The output port is significant and is optionally delimited by a ':'
      // for non-zero ports.
      std::pair<std::string, std::string> node_spec =
          absl::StrSplit(node->input(i), absl::MaxSplits(':', 1));
      uint64 child_node_hash =
          HashSubgraphImpl(g, g.GetNode(node_spec.first), visited, cache);
      uint64 child_port_hash = Hash64(node_spec.second);
      input_hash = Hash64Combine(
          input_hash, Hash64Combine(child_node_hash, child_port_hash));
    }
  }

  uint64 attr_hash = 0;
  for (const auto& attr : node->attr()) {
    attr_hash = Hash64CombineUnordered(
        attr_hash, HashAttr(g.graph()->library(), attr.first, attr.second,
                            visited, cache));
  }

  uint64 device_hash = Hash64(node->device());