text: from collections import defaultdict, OrderedDict
  from contextlib import contextmanager
  import sys
  
  import gast as ast
  
  
  class ordered_set(object):
      def __init__(self, elements=None):
          self.values = OrderedDict.fromkeys(elements or [])
  
      def add(self, value):
          self.values[value] = None
  
      def update(self, values):
          self.values.update((k, None) for k in values)
  
      def __iter__(self):
          return iter(self.values.keys())
  
      def __contains__(self, value):
          return value in self.values
  
      def __add__(self, other):
          out = self.values.copy()
          out.update(other.values)
          return out
  
      def __len__(self):
          return len(self.values)
  
  
  class Ancestors(ast.NodeVisitor):
      """
      Build the ancestor tree, that associates a node to the list of node visited
      from the root node (the Module) to the current node
  
      >>> import gast as ast
      >>> code = 'def foo(x): return x + 1'
      >>> module = ast.parse(code)
  
      >>> from beniget import Ancestors
      >>> ancestors = Ancestors()
      >>> ancestors.visit(module)
  
      >>> binop = module.body[0].body[0].value
      >>> for n in ancestors.parents(binop):
      ...    print(type(n))
      <class 'gast.gast.Module'>
      <class 'gast.gast.FunctionDef'>
      <class 'gast.gast.Return'>
      """
  
      def __init__(self):
          self._parents = dict()
          self._current = list()
  
      def generic_visit(self, node):
          self._parents[node] = list(self._current)
          self._current.append(node)
          super(Ancestors, self).generic_visit(node)
          self._current.pop()
  
      def parent(self, node):
          return self._parents[node][-1]
  
      def parents(self, node):
          return self._parents[node]
  
      def parentInstance(self, node, cls):
          for n in reversed(self._parents[node]):
              if isinstance(n, cls):
                  return n
          raise ValueError("{} has no parent of type {}".format(node, cls))
  
      def parentFunction(self, node):
          return self.parentInstance(node, (ast.FunctionDef,
                                            ast.AsyncFunctionDef))
  
      def parentStmt(self, node):
          return self.parentInstance(node, ast.stmt)
  
  
  class Def(object):
      """
      Model a definition, either named or unnamed, and its users.
      """
  
      __slots__ = "node", "_users"
  
      def __init__(self, node):
          self.node = node
          self._users = ordered_set()
  
      def add_user(self, node):
          assert isinstance(node, Def)
          self._users.add(node)
  
      def name(self):
          """
          If the node associated to this Def has a name, returns this name.
          Otherwise returns its type
          """
          if isinstance(self.node, (ast.ClassDef,
                                    ast.FunctionDef,
                                    ast.AsyncFunctionDef)):
              return self.node.name
          elif isinstance(self.node, ast.Name):
              return self.node.id
          elif isinstance(self.node, ast.alias):
              base = self.node.name.split(".", 1)[0]
              return self.node.asname or base
          elif isinstance(self.node, tuple):
              return self.node[1]
          else:
              return type(self.node).__name__
  
      def users(self):
          """
          The list of ast entity that holds a reference to this node
          """
          return self._users
  
      def __repr__(self):
          return self._repr({})
  
      def _repr(self, nodes):
          if self in nodes:
              return "(#{})".format(nodes[self])
          else:
              nodes[self] = len(nodes)
              return "{} -> ({})".format(
                  self.node, ", ".join(u._repr(nodes.copy())
                                       for u in self._users)
              )
  
      def __str__(self):
          return self._str({})
  
      def _str(self, nodes):
          if self in nodes:
              return "(#{})".format(nodes[self])
          else:
              nodes[self] = len(nodes)
              return "{} -> ({})".format(
                  self.name(), ", ".join(u._str(nodes.copy())
                                         for u in self._users)
              )
  
  
  Builtins = {}
  
  if sys.version_info.major == 2:
      BuiltinsSrc = __builtins__
  else:
      import builtins
  
      BuiltinsSrc = builtins.__dict__
  
  Builtins = {k: v for k, v in BuiltinsSrc.items()}
  
  Builtins["__file__"] = __file__
  
  DeclarationStep, DefinitionStep = object(), object()
  
  
  class CollectGlobals(ast.NodeVisitor):
      def __init__(self):
          self.Globals = defaultdict(list)
  
      def visit_Global(self, node):
          for name in node.names:
              self.Globals[name].append((node, name))
  
  
  class DefUseChains(ast.NodeVisitor):
      """
      Module visitor that gathers two kinds of informations:
          - locals: Dict[node, List[Def]], a mapping between a node and the list
            of variable defined in this node,
          - chains: Dict[node, Def], a mapping between nodes and their chains.
  
      >>> import gast as ast
      >>> module = ast.parse("from b import c, d; c()")
      >>> duc = DefUseChains()
      >>> duc.visit(module)
      >>> for head in duc.locals[module]:
      ...     print("{}: {}".format(head.name(), len(head.users())))
      c: 1
      d: 0
      >>> alias_def = duc.chains[module.body[0].names[0]]
      >>> print(alias_def)
      c -> (c -> (Call -> ()))
      """
  
      def __init__(self, filename=None):
          """
              - filename: str, included in error messages if specified
          """
          self.chains = {}
          self.locals = defaultdict(list)
          self.filename = filename
  
          # deep copy of builtins, to remain reentrant
          self._builtins = {k: Def(v) for k, v in Builtins.items()}
  
          # function body are not executed when the function definition is met
          # this holds a stack of the functions met during body processing
          self._defered = []
  
          # stack of mapping between an id and Names
          self._definitions = []
  
          # stack of variable defined with the global keywords
          self._promoted_locals = []
  
          # stack of variable that were undefined when we met them, but that may
          # be defined in another path of the control flow (esp. in loop)
          self._undefs = []
  
          # stack of current node holding definitions: class, module, function...
          self._currenthead = []
  
          self._breaks = []
          self._continues = []
  
          # dead code levels
          self.deadcode = 0
  
      # helpers
  
      def dump_definitions(self, node, ignore_builtins=True):
          if isinstance(node, ast.Module) and not ignore_builtins:
              builtins = {d for d in self._builtins.values()}
              return sorted(d.name()
                            for d in self.locals[node] if d not in builtins)
          else:
              return sorted(d.name() for d in self.locals[node])
  
      def dump_chains(self, node):
          chains = []
          for d in self.locals[node]:
              chains.append(str(d))
          return chains
  
      def unbound_identifier(self, name, node):
          if hasattr(node, "lineno"):
              filename = "{}:".format(
                  "<unknown>" if self.filename is None else self.filename
              )
              location = " at {}{}:{}".format(filename,
                                              node.lineno,
                                              node.col_offset)
          else:
              location = ""
          print("W: unbound identifier '{}'{}".format(name, location))
  
      def lookup_identifier(self, name):
          for d in reversed(self._definitions):
              if name in d:
                  return d[name]
          return []
  
      def defs(self, node):
          name = node.id
          stars = []
          for d in reversed(self._definitions):
              if name in d:
                  return d[name] if not stars else stars + list(d[name])
              if "*" in d:
                  stars.extend(d["*"])
  
          d = self.chains.setdefault(node, Def(node))
  
          if self._undefs:
              self._undefs[-1][name].append((d, stars))
  
          if stars:
              return stars + [d]
          else:
              if not self._undefs:
                  self.unbound_identifier(name, node)
              return [d]
  
      def process_body(self, stmts):
          deadcode = False
          for stmt in stmts:
              if isinstance(stmt, (ast.Break, ast.Continue, ast.Raise)):
                  if not deadcode:
                      deadcode = True
                      self.deadcode += 1
              self.visit(stmt)
          if deadcode:
              self.deadcode -= 1
  
      def process_undefs(self):
          for undef_name, _undefs in self._undefs[-1].items():
              if undef_name in self._definitions[-1]:
                  for newdef in self._definitions[-1][undef_name]:
                      for undef, _ in _undefs:
                          for user in undef.users():
                              newdef.add_user(user)
              else:
                  for undef, stars in _undefs:
                      if not stars:
                          self.unbound_identifier(undef_name, undef.node)
          self._undefs.pop()
  
      @contextmanager
      def DefinitionContext(self, node):
          self._currenthead.append(node)
          self._definitions.append(defaultdict(ordered_set))
          self._promoted_locals.append(set())
          yield
          self._promoted_locals.pop()
          self._definitions.pop()
          self._currenthead.pop()
  
      @contextmanager
      def CompDefinitionContext(self, node):
          if sys.version_info.major >= 3:
              self._currenthead.append(node)
              self._definitions.append(defaultdict(ordered_set))
              self._promoted_locals.append(set())
          yield
          if sys.version_info.major >= 3:
              self._promoted_locals.pop()
              self._definitions.pop()
              self._currenthead.pop()
  
      # stmt
      def visit_Module(self, node):
          self.module = node
          with self.DefinitionContext(node):
  
              self._definitions[-1].update(
                  {k: ordered_set((v,)) for k, v in self._builtins.items()}
              )
  
              self._defered.append([])
              self.process_body(node.body)
  
              # handle `global' keyword specifically
              cg = CollectGlobals()
              cg.visit(node)
              for nodes in cg.Globals.values():
                  for n, name in nodes:
                      if name not in self._definitions[-1]:
                          dnode = Def((n, name))
                          self.set_definition(name, dnode)
                          self.locals[node].append(dnode)
  
              # handle function bodies
              for fnode, ctx in self._defered[-1]:
                  visitor = getattr(self,
                                    "visit_{}".format(type(fnode).__name__))
                  defs, self._definitions = self._definitions, ctx
                  visitor(fnode, step=DefinitionStep)
                  self._definitions = defs
              self._defered.pop()
  
              # various sanity checks
              if __debug__:
                  overloaded_builtins = set()
                  for d in self.locals[node]:
                      name = d.name()
                      if name in self._builtins:
                          overloaded_builtins.add(name)
                      assert name in self._definitions[0], (name, d.node)
  
                  nb_defs = len(self._definitions[0])
                  nb_bltns = len(self._builtins)
                  nb_overloaded_bltns = len(overloaded_builtins)
                  nb_heads = len({d.name() for d in self.locals[node]})
                  assert nb_defs == nb_heads + nb_bltns - nb_overloaded_bltns
  
          assert not self._definitions
          assert not self._defered
  
      def set_definition(self, name, dnode_or_dnodes):
          if self.deadcode:
              return
          if isinstance(dnode_or_dnodes, Def):
              self._definitions[-1][name] = ordered_set((dnode_or_dnodes,))
          else:
              self._definitions[-1][name] = ordered_set(dnode_or_dnodes)
  
      @staticmethod
      def add_to_definition(definition, name, dnode_or_dnodes):
          if isinstance(dnode_or_dnodes, Def):
              definition[name].add(dnode_or_dnodes)
          else:
              definition[name].update(dnode_or_dnodes)
  
      def extend_definition(self, name, dnode_or_dnodes):
          if self.deadcode:
              return
          DefUseChains.add_to_definition(self._definitions[-1], name,
                                         dnode_or_dnodes)
  
      def visit_FunctionDef(self, node, step=DeclarationStep):
          if step is DeclarationStep:
              dnode = self.chains.setdefault(node, Def(node))
              self.set_definition(node.name, dnode)
              self.locals[self._currenthead[-1]].append(dnode)
  
              for kw_default in filter(None, node.args.kw_defaults):
                  self.visit(kw_default).add_user(dnode)
              for default in node.args.defaults:
                  self.visit(default).add_user(dnode)
              for decorator in node.decorator_list:
                  self.visit(decorator)
  
              definitions = list(self._definitions)
              if isinstance(self._currenthead[-1], ast.ClassDef):
                  definitions.pop()
              self._defered[-1].append((node, definitions))
          elif step is DefinitionStep:
              # function is not considered as defined when evaluating returns
              if node.returns:
                  self.visit(node.returns)
              with self.DefinitionContext(node):
                  self.visit(node.args)
                  self.process_body(node.body)
          else:
              raise NotImplementedError()
  
      visit_AsyncFunctionDef = visit_FunctionDef
  
      def visit_ClassDef(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.locals[self._currenthead[-1]].append(dnode)
          self.set_definition(node.name, dnode)
          for base in node.bases:
              self.visit(base).add_user(dnode)
          for keyword in node.keywords:
              self.visit(keyword.value).add_user(dnode)
          for decorator in node.decorator_list:
              self.visit(decorator).add_user(dnode)
  
          with self.DefinitionContext(node):
              self.set_definition("__class__", Def("__class__"))
              self.process_body(node.body)
  
      def visit_Return(self, node):
          if node.value:
              self.visit(node.value)
  
      def visit_Break(self, _):
          for k, v in self._definitions[-1].items():
              DefUseChains.add_to_definition(self._breaks[-1], k, v)
          self._definitions[-1].clear()
  
      def visit_Continue(self, _):
          for k, v in self._definitions[-1].items():
              DefUseChains.add_to_definition(self._continues[-1], k, v)
          self._definitions[-1].clear()
  
      def visit_Delete(self, node):
          for target in node.targets:
              self.visit(target)
  
      def visit_Assign(self, node):
          # link is implicit through ctx
          self.visit(node.value)
          for target in node.targets:
              self.visit(target)
  
      def visit_AnnAssign(self, node):
          if node.value:
              dvalue = self.visit(node.value)
          dannotation = self.visit(node.annotation)
          dtarget = self.visit(node.target)
          dtarget.add_user(dannotation)
          if node.value:
              dvalue.add_user(dtarget)
  
      def visit_AugAssign(self, node):
          dvalue = self.visit(node.value)
          if isinstance(node.target, ast.Name):
              ctx, node.target.ctx = node.target.ctx, ast.Load()
              dtarget = self.visit(node.target)
              dvalue.add_user(dtarget)
              node.target.ctx = ctx
              if node.target.id in self._promoted_locals[-1]:
                  self.extend_definition(node.target.id, dtarget)
              else:
                  loaded_from = [d.name() for d in self.defs(node.target)]
                  self.set_definition(node.target.id, dtarget)
                  # If we augassign from a value that comes from '*', let's use
                  # this node as the definition point.
                  if '*' in loaded_from:
                      self.locals[self._currenthead[-1]].append(dtarget)
          else:
              self.visit(node.target).add_user(dvalue)
  
      def visit_Print(self, node):
          if node.dest:
              self.visit(node.dest)
          for value in node.values:
              self.visit(value)
  
      def visit_For(self, node):
          self.visit(node.iter)
  
          self._breaks.append(defaultdict(ordered_set))
          self._continues.append(defaultdict(ordered_set))
  
          self._undefs.append(defaultdict(list))
          self._definitions.append(self._definitions[-1].copy())
          self.visit(node.target)
          self.process_body(node.body)
          self.process_undefs()
  
          continue_defs = self._continues.pop()
          for d, u in continue_defs.items():
              self.extend_definition(d, u)
          self._continues.append(defaultdict(ordered_set))
  
          # extra round to ``emulate'' looping
          self.visit(node.target)
          self.process_body(node.body)
  
          # process else clause in case of late break
          self._definitions.append(defaultdict(ordered_set))
          self.process_body(node.orelse)
          orelse_defs = self._definitions.pop()
  
          break_defs = self._breaks.pop()
          continue_defs = self._continues.pop()
  
          body_defs = self._definitions.pop()
  
          for d, u in orelse_defs.items():
              self.extend_definition(d, u)
  
          for d, u in continue_defs.items():
              self.extend_definition(d, u)
  
          for d, u in break_defs.items():
              self.extend_definition(d, u)
  
          for d, u in body_defs.items():
              self.extend_definition(d, u)
  
      visit_AsyncFor = visit_For
  
      def visit_While(self, node):
  
          self._definitions.append(self._definitions[-1].copy())
          self._undefs.append(defaultdict(list))
          self._breaks.append(defaultdict(ordered_set))
          self._continues.append(defaultdict(ordered_set))
  
          self.process_body(node.orelse)
  
          self._definitions.pop()
  
          self._definitions.append(self._definitions[-1].copy())
  
          self.visit(node.test)
          self.process_body(node.body)
  
          self.process_undefs()
  
          continue_defs = self._continues.pop()
          for d, u in continue_defs.items():
              self.extend_definition(d, u)
          self._continues.append(defaultdict(ordered_set))
  
          # extra round to simulate loop
          self.visit(node.test)
          self.process_body(node.body)
  
          # the false branch of the eval
          self.visit(node.test)
  
          self._definitions.append(self._definitions[-1].copy())
          self.process_body(node.orelse)
  
          orelse_defs = self._definitions.pop()
          body_defs = self._definitions.pop()
          break_defs = self._breaks.pop()
          continue_defs = self._continues.pop()
  
          for d, u in continue_defs.items():
              self.extend_definition(d, u)
  
          for d, u in break_defs.items():
              self.extend_definition(d, u)
  
          for d, u in orelse_defs.items():
              self.extend_definition(d, u)
  
          for d, u in body_defs.items():
              self.extend_definition(d, u)
  
      def visit_If(self, node):
          self.visit(node.test)
  
          # putting a copy of current level to handle nested conditions
          self._definitions.append(self._definitions[-1].copy())
          self.process_body(node.body)
          body_defs = self._definitions.pop()
  
          self._definitions.append(self._definitions[-1].copy())
          self.process_body(node.orelse)
          orelse_defs = self._definitions.pop()
          for d in body_defs:
              if d in orelse_defs:
                  self.set_definition(d, body_defs[d] + orelse_defs[d])
              else:
                  self.extend_definition(d, body_defs[d])
  
          for d in orelse_defs:
              if d in body_defs:
                  pass  # already done in the previous loop
              else:
                  self.extend_definition(d, orelse_defs[d])
  
      def visit_With(self, node):
          for withitem in node.items:
              self.visit(withitem)
          self.process_body(node.body)
  
      visit_AsyncWith = visit_With
  
      def visit_Raise(self, node):
          if node.exc:
              self.visit(node.exc)
          if node.cause:
              self.visit(node.cause)
  
      def visit_Try(self, node):
          self._definitions.append(self._definitions[-1].copy())
          self.process_body(node.body)
          self.process_body(node.orelse)
          failsafe_defs = self._definitions.pop()
  
          # handle the fact that definitions may have fail
          for d in failsafe_defs:
              self.extend_definition(d, failsafe_defs[d])
  
          for excepthandler in node.handlers:
              self._definitions.append(defaultdict(ordered_set))
              self.visit(excepthandler)
              handler_def = self._definitions.pop()
              for hd in handler_def:
                  self.extend_definition(hd, handler_def[hd])
  
          self.process_body(node.finalbody)
  
      def visit_Assert(self, node):
          self.visit(node.test)
          if node.msg:
              self.visit(node.msg)
  
      def visit_Import(self, node):
          for alias in node.names:
              dalias = self.chains.setdefault(alias, Def(alias))
              base = alias.name.split(".", 1)[0]
              self.set_definition(alias.asname or base, dalias)
              self.locals[self._currenthead[-1]].append(dalias)
  
      def visit_ImportFrom(self, node):
          for alias in node.names:
              dalias = self.chains.setdefault(alias, Def(alias))
              self.set_definition(alias.asname or alias.name, dalias)
              self.locals[self._currenthead[-1]].append(dalias)
  
      def visit_Exec(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.body)
  
          if node.globals:
              self.visit(node.globals)
          else:
              # any global may be used by this exec!
              for defs in self._definitions[0].values():
                  for d in defs:
                      d.add_user(dnode)
  
          if node.locals:
              self.visit(node.locals)
          else:
              # any local may be used by this exec!
              visible_locals = set()
              for _definitions in reversed(self._definitions[1:]):
                  for dname, defs in _definitions.items():
                      if dname not in visible_locals:
                          visible_locals.add(dname)
                          for d in defs:
                              d.add_user(dnode)
  
          self.extend_definition("*", dnode)
  
      def visit_Global(self, node):
          for name in node.names:
              self._promoted_locals[-1].add(name)
  
      def visit_Nonlocal(self, node):
          for name in node.names:
              for d in reversed(self._definitions[:-1]):
                  if name not in d:
                      continue
                  else:
                      # this rightfully creates aliasing
                      self.set_definition(name, d[name])
                      break
              else:
                  self.unbound_identifier(name, node)
  
      def visit_Expr(self, node):
          self.generic_visit(node)
  
      # expr
      def visit_BoolOp(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          for value in node.values:
              self.visit(value).add_user(dnode)
          return dnode
  
      def visit_BinOp(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.left).add_user(dnode)
          self.visit(node.right).add_user(dnode)
          return dnode
  
      def visit_UnaryOp(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.operand).add_user(dnode)
          return dnode
  
      def visit_Lambda(self, node, step=DeclarationStep):
          if step is DeclarationStep:
              dnode = self.chains.setdefault(node, Def(node))
              self._defered[-1].append((node, list(self._definitions)))
              return dnode
          elif step is DefinitionStep:
              dnode = self.chains[node]
              with self.DefinitionContext(node):
                  self.visit(node.args)
                  self.visit(node.body).add_user(dnode)
              return dnode
          else:
              raise NotImplementedError()
  
      def visit_IfExp(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.test).add_user(dnode)
          self.visit(node.body).add_user(dnode)
          self.visit(node.orelse).add_user(dnode)
          return dnode
  
      def visit_Dict(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          for key in filter(None, node.keys):
              self.visit(key).add_user(dnode)
          for value in node.values:
              self.visit(value).add_user(dnode)
          return dnode
  
      def visit_Set(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          for elt in node.elts:
              self.visit(elt).add_user(dnode)
          return dnode
  
      def visit_ListComp(self, node):
          dnode = self.chains.setdefault(node, Def(node))
  
          with self.CompDefinitionContext(node):
              for comprehension in node.generators:
                  self.visit(comprehension).add_user(dnode)
              self.visit(node.elt).add_user(dnode)
  
          return dnode
  
      visit_SetComp = visit_ListComp
  
      def visit_DictComp(self, node):
          dnode = self.chains.setdefault(node, Def(node))
  
          with self.CompDefinitionContext(node):
              for comprehension in node.generators:
                  self.visit(comprehension).add_user(dnode)
              self.visit(node.key).add_user(dnode)
              self.visit(node.value).add_user(dnode)
  
          return dnode
  
      visit_GeneratorExp = visit_ListComp
  
      def visit_Await(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.value).add_user(dnode)
          return dnode
  
      def visit_Yield(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          if node.value:
              self.visit(node.value).add_user(dnode)
          return dnode
  
      visit_YieldFrom = visit_Await
  
      def visit_Compare(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.left).add_user(dnode)
          for expr in node.comparators:
              self.visit(expr).add_user(dnode)
          return dnode
  
      def visit_Call(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.func).add_user(dnode)
          for arg in node.args:
              self.visit(arg).add_user(dnode)
          for kw in node.keywords:
              self.visit(kw.value).add_user(dnode)
          return dnode
  
      visit_Repr = visit_Await
  
      def visit_Constant(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          return dnode
  
      def visit_FormattedValue(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.value).add_user(dnode)
          if node.format_spec:
              self.visit(node.format_spec).add_user(dnode)
          return dnode
  
      def visit_JoinedStr(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          for value in node.values:
              self.visit(value).add_user(dnode)
          return dnode
  
      visit_Attribute = visit_Await
  
      def visit_Subscript(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.value).add_user(dnode)
          self.visit(node.slice).add_user(dnode)
          return dnode
  
      visit_Starred = visit_Await
  
      def visit_NamedExpr(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.value).add_user(dnode)
          self.visit(node.target)
          return dnode
  
      def visit_Name(self, node):
  
          if isinstance(node.ctx, (ast.Param, ast.Store)):
              dnode = self.chains.setdefault(node, Def(node))
              if node.id in self._promoted_locals[-1]:
                  self.extend_definition(node.id, dnode)
                  if dnode not in self.locals[self.module]:
                      self.locals[self.module].append(dnode)
              else:
                  self.set_definition(node.id, dnode)
                  if dnode not in self.locals[self._currenthead[-1]]:
                      self.locals[self._currenthead[-1]].append(dnode)
  
              if node.annotation is not None:
                  self.visit(node.annotation)
  
          elif isinstance(node.ctx, (ast.Load, ast.Del)):
              node_in_chains = node in self.chains
              if node_in_chains:
                  dnode = self.chains[node]
              else:
                  dnode = Def(node)
              for d in self.defs(node):
                  d.add_user(dnode)
              if not node_in_chains:
                  self.chains[node] = dnode
              # currently ignore the effect of a del
          else:
              raise NotImplementedError()
          return dnode
  
      def visit_Destructured(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          tmp_store = ast.Store()
          for elt in node.elts:
              if isinstance(elt, ast.Name):
                  tmp_store, elt.ctx = elt.ctx, tmp_store
                  self.visit(elt)
                  tmp_store, elt.ctx = elt.ctx, tmp_store
              elif isinstance(elt, ast.Subscript):
                  self.visit(elt)
              elif isinstance(elt, (ast.List, ast.Tuple)):
                  self.visit_Destructured(elt)
          return dnode
  
      def visit_List(self, node):
          if isinstance(node.ctx, ast.Load):
              dnode = self.chains.setdefault(node, Def(node))
              for elt in node.elts:
                  self.visit(elt).add_user(dnode)
              return dnode
          # unfortunately, destructured node are marked as Load,
          # only the parent List/Tuple is marked as Store
          elif isinstance(node.ctx, ast.Store):
              return self.visit_Destructured(node)
  
      visit_Tuple = visit_List
  
      # slice
  
      def visit_Slice(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          if node.lower:
              self.visit(node.lower).add_user(dnode)
          if node.upper:
              self.visit(node.upper).add_user(dnode)
          if node.step:
              self.visit(node.step).add_user(dnode)
          return dnode
  
      # misc
  
      def visit_comprehension(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.iter).add_user(dnode)
          self.visit(node.target)
          for if_ in node.ifs:
              self.visit(if_).add_user(dnode)
          return dnode
  
      def visit_excepthandler(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          if node.type:
              self.visit(node.type).add_user(dnode)
          if node.name:
              self.visit(node.name).add_user(dnode)
          self.process_body(node.body)
          return dnode
  
      def visit_arguments(self, node):
          for arg in node.args:
              self.visit(arg)
  
          for arg in node.posonlyargs:
              self.visit(arg)
  
          if node.vararg:
              self.visit(node.vararg)
  
          for arg in node.kwonlyargs:
              self.visit(arg)
          if node.kwarg:
              self.visit(node.kwarg)
  
      def visit_withitem(self, node):
          dnode = self.chains.setdefault(node, Def(node))
          self.visit(node.context_expr).add_user(dnode)
          if node.optional_vars:
              self.visit(node.optional_vars)
          return dnode
  
  
  class UseDefChains(object):
      """
      DefUseChains adaptor that builds a mapping between each user
      and the Def that defines this user:
          - chains: Dict[node, List[Def]], a mapping between nodes and the Defs
            that define it.
      """
  
      def __init__(self, defuses):
          self.chains = {}
          for chain in defuses.chains.values():
              if isinstance(chain.node, ast.Name):
                  self.chains.setdefault(chain.node, [])
              for use in chain.users():
                  self.chains.setdefault(use.node, []).append(chain)
  
          for chain in defuses._builtins.values():
              for use in chain.users():
                  self.chains.setdefault(use.node, []).append(chain)
  
      def __str__(self):
          out = []
          for k, uses in self.chains.items():
              kname = Def(k).name()
              kstr = "{} <- {{{}}}".format(
                  kname, ", ".join(sorted(use.name() for use in uses))
              )
              out.append((kname, kstr))
          out.sort()
          return ", ".join(s for k, s in out)
  
  
  if __name__ == "__main__":
      import sys
  
      class Beniget(ast.NodeVisitor):
          def __init__(self, filename, module):
              super(Beniget, self).__init__()
  
              self.filename = filename or "<stdin>"
  
              self.ancestors = Ancestors()
              self.ancestors.visit(module)
  
              self.defuses = DefUseChains(self.filename)
              self.defuses.visit(module)
  
              self.visit(module)
  
          def check_unused(self, node, skipped_types=()):
              for local_def in self.defuses.locals[node]:
                  if not local_def.users():
                      if local_def.name() == "_":
                          continue  # typical naming by-pass
                      if isinstance(local_def.node, skipped_types):
                          continue
  
                      location = local_def.node
                      while not hasattr(location, "lineno"):
                          location = self.ancestors.parent(location)
  
                      if isinstance(location, ast.ImportFrom):
                          if location.module == "__future__":
                              continue
  
                      print(
                          "W: '{}' is defined but not used at {}:{}:{}".format(
                              local_def.name(),
                              self.filename,
                              location.lineno,
                              location.col_offset,
                          )
                      )
  
          def visit_Module(self, node):
              self.generic_visit(node)
              if self.filename.endswith("__init__.py"):
                  return
              self.check_unused(
                  node, skipped_types=(ast.FunctionDef, ast.AsyncFunctionDef,
                                       ast.ClassDef, ast.Name)
              )
  
          def visit_FunctionDef(self, node):
              self.generic_visit(node)
              self.check_unused(node)
  
      paths = sys.argv[1:] or (None,)
  
      for path in paths:
          with open(path) if path else sys.stdin as target:
              module = ast.parse(target.read())
              Beniget(path, module)
  