import ast
import copy


def _uniqueify_distinct_ast(tree):
  """Returns a version of tree where all nodes have a unique identity.

  i.e. if a given node is in a different position in the tree, it will be given
  a different identity, even if it is equal on every attribute.

  Args:
    tree: An AST node. This is potentially mutated.

  Returns:
    An uniqueified version of tree.
  """

  # Only copy when a duplicate is found, to avoid the O(n^2) worst algorithm.
  seen_ids = set()

  class CopyTransformer(ast.NodeTransformer):

    def visit(self, node):
      node = self.generic_visit(node)
      if id(node) in seen_ids:
        return copy.copy(node)
      else:
        seen_ids.add(id(node))
        return node

  return CopyTransformer().visit(tree)