Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/libcst/metadata/scope_provider.py: 31%
620 statements
« prev ^ index » next coverage.py v7.2.7, created at 2023-06-07 07:09 +0000
1# Copyright (c) Meta Platforms, Inc. and affiliates.
2#
3# This source code is licensed under the MIT license found in the
4# LICENSE file in the root directory of this source tree.
7import abc
8import builtins
9from collections import defaultdict
10from contextlib import contextmanager
11from dataclasses import dataclass
12from enum import auto, Enum
13from typing import (
14 Collection,
15 Dict,
16 Iterator,
17 List,
18 Mapping,
19 MutableMapping,
20 Optional,
21 Set,
22 Tuple,
23 Type,
24 Union,
25)
27import libcst as cst
28from libcst import ensure_type
29from libcst._add_slots import add_slots
30from libcst.helpers import get_full_name_for_node
31from libcst.metadata.base_provider import BatchableMetadataProvider
32from libcst.metadata.expression_context_provider import (
33 ExpressionContext,
34 ExpressionContextProvider,
35)
37# Comprehensions are handled separately in _visit_comp_alike due to
38# the complexity of the semantics
39_ASSIGNMENT_LIKE_NODES = (
40 cst.AnnAssign,
41 cst.AsName,
42 cst.Assign,
43 cst.AugAssign,
44 cst.ClassDef,
45 cst.CompFor,
46 cst.FunctionDef,
47 cst.Global,
48 cst.Import,
49 cst.ImportFrom,
50 cst.NamedExpr,
51 cst.Nonlocal,
52 cst.Parameters,
53 cst.WithItem,
54)
57@add_slots
58@dataclass(frozen=False)
59class Access:
60 """
61 An Access records an access of an assignment.
63 .. note::
64 This scope analysis only analyzes access via a :class:`~libcst.Name` or a :class:`~libcst.Name`
65 node embedded in other node like :class:`~libcst.Call` or :class:`~libcst.Attribute`.
66 It doesn't support type annontation using :class:`~libcst.SimpleString` literal for forward
67 references. E.g. in this example, the ``"Tree"`` isn't parsed as an access::
69 class Tree:
70 def __new__(cls) -> "Tree":
71 ...
72 """
74 #: The node of the access. A name is an access when the expression context is
75 #: :attr:`ExpressionContext.LOAD`. This is usually the name node representing the
76 #: access, except for: 1) dotted imports, when it might be the attribute that
77 #: represents the most specific part of the imported symbol; and 2) string
78 #: annotations, when it is the entire string literal
79 node: Union[cst.Name, cst.Attribute, cst.BaseString]
81 #: The scope of the access. Note that a access could be in a child scope of its
82 #: assignment.
83 scope: "Scope"
85 is_annotation: bool
87 is_type_hint: bool
89 __assignments: Set["BaseAssignment"]
90 __index: int
92 def __init__(
93 self, node: cst.Name, scope: "Scope", is_annotation: bool, is_type_hint: bool
94 ) -> None:
95 self.node = node
96 self.scope = scope
97 self.is_annotation = is_annotation
98 self.is_type_hint = is_type_hint
99 self.__assignments = set()
100 self.__index = scope._assignment_count
102 def __hash__(self) -> int:
103 return id(self)
105 @property
106 def referents(self) -> Collection["BaseAssignment"]:
107 """Return all assignments of the access."""
108 return self.__assignments
110 @property
111 def _index(self) -> int:
112 return self.__index
114 def record_assignment(self, assignment: "BaseAssignment") -> None:
115 if assignment.scope != self.scope or assignment._index < self.__index:
116 self.__assignments.add(assignment)
118 def record_assignments(self, name: str) -> None:
119 assignments = self.scope[name]
120 # filter out assignments that happened later than this access
121 previous_assignments = {
122 assignment
123 for assignment in assignments
124 if assignment.scope != self.scope or assignment._index < self.__index
125 }
126 if not previous_assignments and assignments and self.scope.parent != self.scope:
127 previous_assignments = self.scope.parent[name]
128 self.__assignments |= previous_assignments
131class QualifiedNameSource(Enum):
132 IMPORT = auto()
133 BUILTIN = auto()
134 LOCAL = auto()
137@add_slots
138@dataclass(frozen=True)
139class QualifiedName:
140 #: Qualified name, e.g. ``a.b.c`` or ``fn.<locals>.var``.
141 name: str
143 #: Source of the name, either :attr:`QualifiedNameSource.IMPORT`, :attr:`QualifiedNameSource.BUILTIN`
144 #: or :attr:`QualifiedNameSource.LOCAL`.
145 source: QualifiedNameSource
148class BaseAssignment(abc.ABC):
149 """Abstract base class of :class:`Assignment` and :class:`BuitinAssignment`."""
151 #: The name of assignment.
152 name: str
154 #: The scope associates to assignment.
155 scope: "Scope"
156 __accesses: Set[Access]
158 def __init__(self, name: str, scope: "Scope") -> None:
159 self.name = name
160 self.scope = scope
161 self.__accesses = set()
163 def record_access(self, access: Access) -> None:
164 if access.scope != self.scope or self._index < access._index:
165 self.__accesses.add(access)
167 def record_accesses(self, accesses: Set[Access]) -> None:
168 later_accesses = {
169 access
170 for access in accesses
171 if access.scope != self.scope or self._index < access._index
172 }
173 self.__accesses |= later_accesses
174 earlier_accesses = accesses - later_accesses
175 if earlier_accesses and self.scope.parent != self.scope:
176 # Accesses "earlier" than the relevant assignment should be attached
177 # to assignments of the same name in the parent
178 for shadowed_assignment in self.scope.parent[self.name]:
179 shadowed_assignment.record_accesses(earlier_accesses)
181 @property
182 def references(self) -> Collection[Access]:
183 """Return all accesses of the assignment."""
184 # we don't want to publicly expose the mutable version of this
185 return self.__accesses
187 def __hash__(self) -> int:
188 return id(self)
190 @property
191 def _index(self) -> int:
192 """Return an integer that represents the order of assignments in `scope`"""
193 return -1
195 @abc.abstractmethod
196 def get_qualified_names_for(self, full_name: str) -> Set[QualifiedName]:
197 ...
200class Assignment(BaseAssignment):
201 """An assignment records the name, CSTNode and its accesses."""
203 #: The node of assignment, it could be a :class:`~libcst.Import`, :class:`~libcst.ImportFrom`,
204 #: :class:`~libcst.Name`, :class:`~libcst.FunctionDef`, or :class:`~libcst.ClassDef`.
205 node: cst.CSTNode
206 __index: int
208 def __init__(
209 self, name: str, scope: "Scope", node: cst.CSTNode, index: int
210 ) -> None:
211 self.node = node
212 self.__index = index
213 super().__init__(name, scope)
215 @property
216 def _index(self) -> int:
217 return self.__index
219 def get_qualified_names_for(self, full_name: str) -> Set[QualifiedName]:
220 return {
221 QualifiedName(
222 f"{self.scope._name_prefix}.{full_name}"
223 if self.scope._name_prefix
224 else full_name,
225 QualifiedNameSource.LOCAL,
226 )
227 }
230# even though we don't override the constructor.
231class BuiltinAssignment(BaseAssignment):
232 """
233 A BuiltinAssignment represents an value provide by Python as a builtin, including
234 `functions <https://docs.python.org/3/library/functions.html>`_,
235 `constants <https://docs.python.org/3/library/constants.html>`_, and
236 `types <https://docs.python.org/3/library/stdtypes.html>`_.
237 """
239 def get_qualified_names_for(self, full_name: str) -> Set[QualifiedName]:
240 return {QualifiedName(f"builtins.{self.name}", QualifiedNameSource.BUILTIN)}
243class ImportAssignment(Assignment):
244 """An assignment records the import node and it's alias"""
246 as_name: cst.CSTNode
248 def __init__(
249 self,
250 name: str,
251 scope: "Scope",
252 node: cst.CSTNode,
253 index: int,
254 as_name: cst.CSTNode,
255 ) -> None:
256 super().__init__(name, scope, node, index)
257 self.as_name = as_name
259 def get_module_name_for_import(self) -> str:
260 module = ""
261 if isinstance(self.node, cst.ImportFrom):
262 module_attr = self.node.module
263 relative = self.node.relative
264 if module_attr:
265 module = get_full_name_for_node(module_attr) or ""
266 if relative:
267 module = "." * len(relative) + module
268 return module
270 def get_qualified_names_for(self, full_name: str) -> Set[QualifiedName]:
271 module = self.get_module_name_for_import()
272 results = set()
273 assert isinstance(self.node, (cst.ImportFrom, cst.Import))
274 import_names = self.node.names
275 if not isinstance(import_names, cst.ImportStar):
276 for name in import_names:
277 real_name = get_full_name_for_node(name.name)
278 if not real_name:
279 continue
280 # real_name can contain `.` for dotted imports
281 # for these we want to find the longest prefix that matches full_name
282 parts = real_name.split(".")
283 real_names = [".".join(parts[:i]) for i in range(len(parts), 0, -1)]
284 for real_name in real_names:
285 as_name = real_name
286 if module and module.endswith("."):
287 # from . import a
288 # real_name should be ".a"
289 real_name = f"{module}{real_name}"
290 elif module:
291 real_name = f"{module}.{real_name}"
292 if name and name.asname:
293 eval_alias = name.evaluated_alias
294 if eval_alias is not None:
295 as_name = eval_alias
296 if full_name.startswith(as_name):
297 remaining_name = full_name.split(as_name, 1)[1]
298 if remaining_name and not remaining_name.startswith("."):
299 continue
300 remaining_name = remaining_name.lstrip(".")
301 results.add(
302 QualifiedName(
303 f"{real_name}.{remaining_name}"
304 if remaining_name
305 else real_name,
306 QualifiedNameSource.IMPORT,
307 )
308 )
309 break
310 return results
313class Assignments:
314 """A container to provide all assignments in a scope."""
316 def __init__(self, assignments: Mapping[str, Collection[BaseAssignment]]) -> None:
317 self._assignments = assignments
319 def __iter__(self) -> Iterator[BaseAssignment]:
320 """Iterate through all assignments by ``for i in scope.assignments``."""
321 for assignments in self._assignments.values():
322 for assignment in assignments:
323 yield assignment
325 def __getitem__(self, node: Union[str, cst.CSTNode]) -> Collection[BaseAssignment]:
326 """Get assignments given a name str or :class:`~libcst.CSTNode` by ``scope.assignments[node]``"""
327 name = _NameUtil.get_name_for(node)
328 return set(self._assignments[name]) if name in self._assignments else set()
330 def __contains__(self, node: Union[str, cst.CSTNode]) -> bool:
331 """Check if a name str or :class:`~libcst.CSTNode` has any assignment by ``node in scope.assignments``"""
332 return len(self[node]) > 0
335class Accesses:
336 """A container to provide all accesses in a scope."""
338 def __init__(self, accesses: Mapping[str, Collection[Access]]) -> None:
339 self._accesses = accesses
341 def __iter__(self) -> Iterator[Access]:
342 """Iterate through all accesses by ``for i in scope.accesses``."""
343 for accesses in self._accesses.values():
344 for access in accesses:
345 yield access
347 def __getitem__(self, node: Union[str, cst.CSTNode]) -> Collection[Access]:
348 """Get accesses given a name str or :class:`~libcst.CSTNode` by ``scope.accesses[node]``"""
349 name = _NameUtil.get_name_for(node)
350 return self._accesses[name] if name in self._accesses else set()
352 def __contains__(self, node: Union[str, cst.CSTNode]) -> bool:
353 """Check if a name str or :class:`~libcst.CSTNode` has any access by ``node in scope.accesses``"""
354 return len(self[node]) > 0
357class _NameUtil:
358 @staticmethod
359 def get_name_for(node: Union[str, cst.CSTNode]) -> Optional[str]:
360 """A helper function to retrieve simple name str from a CSTNode or str"""
361 if isinstance(node, cst.Name):
362 return node.value
363 elif isinstance(node, str):
364 return node
365 elif isinstance(node, cst.Call):
366 return _NameUtil.get_name_for(node.func)
367 elif isinstance(node, cst.Subscript):
368 return _NameUtil.get_name_for(node.value)
369 elif isinstance(node, (cst.FunctionDef, cst.ClassDef)):
370 return _NameUtil.get_name_for(node.name)
371 return None
374class Scope(abc.ABC):
375 """
376 Base class of all scope classes. Scope object stores assignments from imports,
377 variable assignments, function definition or class definition.
378 A scope has a parent scope which represents the inheritance relationship. That means
379 an assignment in parent scope is viewable to the child scope and the child scope may
380 overwrites the assignment by using the same name.
382 Use ``name in scope`` to check whether a name is viewable in the scope.
383 Use ``scope[name]`` to retrieve all viewable assignments in the scope.
385 .. note::
386 This scope analysis module only analyzes local variable names and it doesn't handle
387 attribute names; for example, given ``a.b.c = 1``, local variable name ``a`` is recorded
388 as an assignment instead of ``c`` or ``a.b.c``. To analyze the assignment/access of
389 arbitrary object attributes, we leave the job to type inference metadata provider
390 coming in the future.
391 """
393 #: Parent scope. Note the parent scope of a GlobalScope is itself.
394 parent: "Scope"
396 #: Refers to the GlobalScope.
397 globals: "GlobalScope"
398 _assignments: MutableMapping[str, Set[BaseAssignment]]
399 _assignment_count: int
400 _accesses_by_name: MutableMapping[str, Set[Access]]
401 _accesses_by_node: MutableMapping[cst.CSTNode, Set[Access]]
402 _name_prefix: str
404 def __init__(self, parent: "Scope") -> None:
405 super().__init__()
406 self.parent = parent
407 self.globals = parent.globals
408 self._assignments = defaultdict(set)
409 self._assignment_count = 0
410 self._accesses_by_name = defaultdict(set)
411 self._accesses_by_node = defaultdict(set)
412 self._name_prefix = ""
414 def record_assignment(self, name: str, node: cst.CSTNode) -> None:
415 target = self._find_assignment_target(name)
416 target._assignments[name].add(
417 Assignment(
418 name=name, scope=target, node=node, index=target._assignment_count
419 )
420 )
422 def record_import_assignment(
423 self, name: str, node: cst.CSTNode, as_name: cst.CSTNode
424 ) -> None:
425 target = self._find_assignment_target(name)
426 target._assignments[name].add(
427 ImportAssignment(
428 name=name,
429 scope=target,
430 node=node,
431 as_name=as_name,
432 index=target._assignment_count,
433 )
434 )
436 def _find_assignment_target(self, name: str) -> "Scope":
437 return self
439 def _find_assignment_target_parent(self, name: str) -> "Scope":
440 return self
442 def record_access(self, name: str, access: Access) -> None:
443 self._accesses_by_name[name].add(access)
444 self._accesses_by_node[access.node].add(access)
446 def _getitem_from_self_or_parent(self, name: str) -> Set[BaseAssignment]:
447 """Overridden by ClassScope to hide it's assignments from child scopes."""
448 return self[name]
450 def _contains_in_self_or_parent(self, name: str) -> bool:
451 """Overridden by ClassScope to hide it's assignments from child scopes."""
452 return name in self
454 @abc.abstractmethod
455 def __contains__(self, name: str) -> bool:
456 """Check if the name str exist in current scope by ``name in scope``."""
457 ...
459 @abc.abstractmethod
460 def __getitem__(self, name: str) -> Set[BaseAssignment]:
461 """
462 Get assignments given a name str by ``scope[name]``.
464 .. note::
465 *Why does it return a list of assignments given a name instead of just one assignment?*
467 Many programming languages differentiate variable declaration and assignment.
468 Further, those programming languages often disallow duplicate declarations within
469 the same scope, and will often hoist the declaration (without its assignment) to
470 the top of the scope. These design decisions make static analysis much easier,
471 because it's possible to match a name against its single declaration for a given scope.
473 As an example, the following code would be valid in JavaScript::
475 function fn() {
476 console.log(value); // value is defined here, because the declaration is hoisted, but is currently 'undefined'.
477 var value = 5; // A function-scoped declaration.
478 }
479 fn(); // prints 'undefined'.
481 In contrast, Python's declaration and assignment are identical and are not hoisted::
483 if conditional_value:
484 value = 5
485 elif other_conditional_value:
486 value = 10
487 print(value) # possibly valid, depending on conditional execution
489 This code may throw a ``NameError`` if both conditional values are falsy.
490 It also means that depending on the codepath taken, the original declaration
491 could come from either ``value = ...`` assignment node.
492 As a result, instead of returning a single declaration,
493 we're forced to return a collection of all of the assignments we think could have
494 defined a given name by the time a piece of code is executed.
495 For the above example, value would resolve to a set of both assignments.
496 """
497 ...
499 def __hash__(self) -> int:
500 return id(self)
502 @abc.abstractmethod
503 def record_global_overwrite(self, name: str) -> None:
504 ...
506 @abc.abstractmethod
507 def record_nonlocal_overwrite(self, name: str) -> None:
508 ...
510 def get_qualified_names_for(
511 self, node: Union[str, cst.CSTNode]
512 ) -> Collection[QualifiedName]:
513 """Get all :class:`~libcst.metadata.QualifiedName` in current scope given a
514 :class:`~libcst.CSTNode`.
515 The source of a qualified name can be either :attr:`QualifiedNameSource.IMPORT`,
516 :attr:`QualifiedNameSource.BUILTIN` or :attr:`QualifiedNameSource.LOCAL`.
517 Given the following example, ``c`` has qualified name ``a.b.c`` with source ``IMPORT``,
518 ``f`` has qualified name ``Cls.f`` with source ``LOCAL``, ``a`` has qualified name
519 ``Cls.f.<locals>.a``, ``i`` has qualified name ``Cls.f.<locals>.<comprehension>.i``,
520 and the builtin ``int`` has qualified name ``builtins.int`` with source ``BUILTIN``::
522 from a.b import c
523 class Cls:
524 def f(self) -> "c":
525 c()
526 a = int("1")
527 [i for i in c()]
529 We extends `PEP-3155 <https://www.python.org/dev/peps/pep-3155/>`_
530 (defines ``__qualname__`` for class and function only; function namespace is followed
531 by a ``<locals>``) to provide qualified name for all :class:`~libcst.CSTNode`
532 recorded by :class:`~libcst.metadata.Assignment` and :class:`~libcst.metadata.Access`.
533 The namespace of a comprehension (:class:`~libcst.ListComp`, :class:`~libcst.SetComp`,
534 :class:`~libcst.DictComp`) is represented with ``<comprehension>``.
536 An imported name may be used for type annotation with :class:`~libcst.SimpleString` and
537 currently resolving the qualified given :class:`~libcst.SimpleString` is not supported
538 considering it could be a complex type annotation in the string which is hard to
539 resolve, e.g. ``List[Union[int, str]]``.
540 """
541 # if this node is an access we know the assignment and we can use that name
542 node_accesses = (
543 self._accesses_by_node.get(node) if isinstance(node, cst.CSTNode) else None
544 )
545 if node_accesses:
546 return {
547 qname
548 for access in node_accesses
549 for referent in access.referents
550 for qname in referent.get_qualified_names_for(referent.name)
551 }
553 full_name = get_full_name_for_node(node)
554 if full_name is None:
555 return set()
557 assignments = set()
558 prefix = full_name
559 while prefix:
560 if prefix in self:
561 assignments = self[prefix]
562 break
563 idx = prefix.rfind(".")
564 prefix = None if idx == -1 else prefix[:idx]
566 if not isinstance(node, str):
567 for assignment in assignments:
568 if isinstance(assignment, Assignment) and _is_assignment(
569 node, assignment.node
570 ):
571 return assignment.get_qualified_names_for(full_name)
573 results = set()
574 for assignment in assignments:
575 results |= assignment.get_qualified_names_for(full_name)
576 return results
578 @property
579 def assignments(self) -> Assignments:
580 """Return an :class:`~libcst.metadata.Assignments` contains all assignmens in current scope."""
581 return Assignments(self._assignments)
583 @property
584 def accesses(self) -> Accesses:
585 """Return an :class:`~libcst.metadata.Accesses` contains all accesses in current scope."""
586 return Accesses(self._accesses_by_name)
589class BuiltinScope(Scope):
590 """
591 A BuiltinScope represents python builtin declarations. See https://docs.python.org/3/library/builtins.html
592 """
594 def __init__(self, globals: Scope) -> None:
595 self.globals: Scope = globals # must be defined before Scope.__init__ is called
596 super().__init__(parent=self)
598 def __contains__(self, name: str) -> bool:
599 return hasattr(builtins, name)
601 def __getitem__(self, name: str) -> Set[BaseAssignment]:
602 if name in self._assignments:
603 return self._assignments[name]
604 if hasattr(builtins, name):
605 # note - we only see the builtin assignments during the deferred
606 # access resolution. unfortunately that means we have to create the
607 # assignment here, which can cause the set to mutate during iteration
608 self._assignments[name].add(BuiltinAssignment(name, self))
609 return self._assignments[name]
610 return set()
612 def record_global_overwrite(self, name: str) -> None:
613 raise NotImplementedError("global overwrite in builtin scope are not allowed")
615 def record_nonlocal_overwrite(self, name: str) -> None:
616 raise NotImplementedError("declarations in builtin scope are not allowed")
618 def _find_assignment_target(self, name: str) -> "Scope":
619 raise NotImplementedError("assignments in builtin scope are not allowed")
622class GlobalScope(Scope):
623 """
624 A GlobalScope is the scope of module. All module level assignments are recorded in GlobalScope.
625 """
627 def __init__(self) -> None:
628 super().__init__(parent=BuiltinScope(self))
630 def __contains__(self, name: str) -> bool:
631 if name in self._assignments:
632 return len(self._assignments[name]) > 0
633 return self.parent._contains_in_self_or_parent(name)
635 def __getitem__(self, name: str) -> Set[BaseAssignment]:
636 if name in self._assignments:
637 return self._assignments[name]
638 else:
639 return self.parent._getitem_from_self_or_parent(name)
641 def record_global_overwrite(self, name: str) -> None:
642 pass
644 def record_nonlocal_overwrite(self, name: str) -> None:
645 raise NotImplementedError("nonlocal declaration not allowed at module level")
648class LocalScope(Scope, abc.ABC):
649 _scope_overwrites: Dict[str, Scope]
651 #: Name of function. Used as qualified name.
652 name: Optional[str]
654 #: The :class:`~libcst.CSTNode` node defines the current scope.
655 node: cst.CSTNode
657 def __init__(
658 self, parent: Scope, node: cst.CSTNode, name: Optional[str] = None
659 ) -> None:
660 super().__init__(parent)
661 self.name = name
662 self.node = node
663 self._scope_overwrites = {}
664 # pyre-fixme[4]: Attribute `_name_prefix` of class `LocalScope` has type `str` but no type is specified.
665 self._name_prefix = self._make_name_prefix()
667 def record_global_overwrite(self, name: str) -> None:
668 self._scope_overwrites[name] = self.globals
670 def record_nonlocal_overwrite(self, name: str) -> None:
671 self._scope_overwrites[name] = self.parent
673 def _find_assignment_target(self, name: str) -> "Scope":
674 if name in self._scope_overwrites:
675 return self._scope_overwrites[name]._find_assignment_target_parent(name)
676 else:
677 return super()._find_assignment_target(name)
679 def __contains__(self, name: str) -> bool:
680 if name in self._scope_overwrites:
681 return name in self._scope_overwrites[name]
682 if name in self._assignments:
683 return len(self._assignments[name]) > 0
684 return self.parent._contains_in_self_or_parent(name)
686 def __getitem__(self, name: str) -> Set[BaseAssignment]:
687 if name in self._scope_overwrites:
688 return self._scope_overwrites[name]._getitem_from_self_or_parent(name)
689 if name in self._assignments:
690 return self._assignments[name]
691 else:
692 return self.parent._getitem_from_self_or_parent(name)
694 def _make_name_prefix(self) -> str:
695 # filter falsey strings out
696 return ".".join(filter(None, [self.parent._name_prefix, self.name, "<locals>"]))
699# even though we don't override the constructor.
700class FunctionScope(LocalScope):
701 """
702 When a function is defined, it creates a FunctionScope.
703 """
705 pass
708# even though we don't override the constructor.
709class ClassScope(LocalScope):
710 """
711 When a class is defined, it creates a ClassScope.
712 """
714 def _find_assignment_target_parent(self, name: str) -> "Scope":
715 """
716 Forward the assignment to parent.
718 def outer_fn():
719 v = ... # outer_fn's declaration
720 class InnerCls:
721 v = ... # shadows outer_fn's declaration
722 def inner_fn():
723 nonlocal v
724 v = ... # this should actually refer to outer_fn's declaration
725 # and not to InnerCls's, because InnerCls's scope is
726 # hidden from its children.
728 """
729 return self.parent._find_assignment_target_parent(name)
731 def _getitem_from_self_or_parent(self, name: str) -> Set[BaseAssignment]:
732 """
733 Class variables are only accessible using ClassName.attribute, cls.attribute, or
734 self.attribute in child scopes. They cannot be accessed with their bare names.
735 """
736 return self.parent._getitem_from_self_or_parent(name)
738 def _contains_in_self_or_parent(self, name: str) -> bool:
739 """
740 See :meth:`_getitem_from_self_or_parent`
741 """
742 return self.parent._contains_in_self_or_parent(name)
744 def _make_name_prefix(self) -> str:
745 # filter falsey strings out
746 return ".".join(filter(None, [self.parent._name_prefix, self.name]))
749# even though we don't override the constructor.
750class ComprehensionScope(LocalScope):
751 """
752 Comprehensions and generator expressions create their own scope. For example, in
754 [i for i in range(10)]
756 The variable ``i`` is only viewable within the ComprehensionScope.
757 """
759 # TODO: Assignment expressions (Python 3.8) will complicate ComprehensionScopes,
760 # and will require us to handle such assignments as non-local.
761 # https://www.python.org/dev/peps/pep-0572/#scope-of-the-target
763 def _make_name_prefix(self) -> str:
764 # filter falsey strings out
765 return ".".join(filter(None, [self.parent._name_prefix, "<comprehension>"]))
768# Generates dotted names from an Attribute or Name node:
769# Attribute(value=Name(value="a"), attr=Name(value="b")) -> ("a.b", "a")
770# each string has the corresponding CSTNode attached to it
771def _gen_dotted_names(
772 node: Union[cst.Attribute, cst.Name]
773) -> Iterator[Tuple[str, Union[cst.Attribute, cst.Name]]]:
774 if isinstance(node, cst.Name):
775 yield node.value, node
776 else:
777 value = node.value
778 if isinstance(value, cst.Call):
779 value = value.func
780 if isinstance(value, (cst.Attribute, cst.Name)):
781 name_values = _gen_dotted_names(value)
782 try:
783 next_name, next_node = next(name_values)
784 except StopIteration:
785 return
786 else:
787 yield next_name, next_node
788 yield from name_values
789 elif isinstance(value, (cst.Attribute, cst.Name)):
790 name_values = _gen_dotted_names(value)
791 try:
792 next_name, next_node = next(name_values)
793 except StopIteration:
794 return
795 else:
796 yield f"{next_name}.{node.attr.value}", node
797 yield next_name, next_node
798 yield from name_values
801def _is_assignment(node: cst.CSTNode, assignment_node: cst.CSTNode) -> bool:
802 """
803 Returns true if ``node`` is part of the assignment at ``assignment_node``.
805 Normally this is just a simple identity check, except for imports where the
806 assignment is attached to the entire import statement but we are interested in
807 ``Name`` nodes inside the statement.
808 """
809 if node is assignment_node:
810 return True
811 if isinstance(assignment_node, (cst.Import, cst.ImportFrom)):
812 aliases = assignment_node.names
813 if isinstance(aliases, cst.ImportStar):
814 return False
815 for alias in aliases:
816 if alias.name is node:
817 return True
818 asname = alias.asname
819 if asname is not None:
820 if asname.name is node:
821 return True
822 return False
825@dataclass(frozen=True)
826class DeferredAccess:
827 access: Access
828 enclosing_attribute: Optional[cst.Attribute]
829 enclosing_string_annotation: Optional[cst.BaseString]
832class ScopeVisitor(cst.CSTVisitor):
833 # since it's probably not useful. That can makes this visitor cleaner.
834 def __init__(self, provider: "ScopeProvider") -> None:
835 self.provider: ScopeProvider = provider
836 self.scope: Scope = GlobalScope()
837 self.__deferred_accesses: List[DeferredAccess] = []
838 self.__top_level_attribute_stack: List[Optional[cst.Attribute]] = [None]
839 self.__in_annotation_stack: List[bool] = [False]
840 self.__in_type_hint_stack: List[bool] = [False]
841 self.__in_ignored_subscript: Set[cst.Subscript] = set()
842 self.__last_string_annotation: Optional[cst.BaseString] = None
843 self.__ignore_annotation: int = 0
845 @contextmanager
846 def _new_scope(
847 self, kind: Type[LocalScope], node: cst.CSTNode, name: Optional[str] = None
848 ) -> Iterator[None]:
849 parent_scope = self.scope
850 self.scope = kind(parent_scope, node, name)
851 try:
852 yield
853 finally:
854 self.scope = parent_scope
856 @contextmanager
857 def _switch_scope(self, scope: Scope) -> Iterator[None]:
858 current_scope = self.scope
859 self.scope = scope
860 try:
861 yield
862 finally:
863 self.scope = current_scope
865 def _visit_import_alike(self, node: Union[cst.Import, cst.ImportFrom]) -> bool:
866 names = node.names
867 if isinstance(names, cst.ImportStar):
868 return False
870 # make sure node.names is Sequence[ImportAlias]
871 for name in names:
872 self.provider.set_metadata(name, self.scope)
873 asname = name.asname
874 if asname is not None:
875 name_values = _gen_dotted_names(cst.ensure_type(asname.name, cst.Name))
876 import_node_asname = asname.name
877 else:
878 name_values = _gen_dotted_names(name.name)
879 import_node_asname = name.name
881 for name_value, _ in name_values:
882 self.scope.record_import_assignment(
883 name_value, node, import_node_asname
884 )
885 return False
887 def visit_Import(self, node: cst.Import) -> Optional[bool]:
888 return self._visit_import_alike(node)
890 def visit_ImportFrom(self, node: cst.ImportFrom) -> Optional[bool]:
891 return self._visit_import_alike(node)
893 def visit_Attribute(self, node: cst.Attribute) -> Optional[bool]:
894 if self.__top_level_attribute_stack[-1] is None:
895 self.__top_level_attribute_stack[-1] = node
896 node.value.visit(self) # explicitly not visiting attr
897 if self.__top_level_attribute_stack[-1] is node:
898 self.__top_level_attribute_stack[-1] = None
899 return False
901 def visit_Call(self, node: cst.Call) -> Optional[bool]:
902 self.__top_level_attribute_stack.append(None)
903 self.__in_type_hint_stack.append(False)
904 qnames = {qn.name for qn in self.scope.get_qualified_names_for(node)}
905 if "typing.NewType" in qnames or "typing.TypeVar" in qnames:
906 node.func.visit(self)
907 self.__in_type_hint_stack[-1] = True
908 for arg in node.args[1:]:
909 arg.visit(self)
910 return False
911 if "typing.cast" in qnames:
912 node.func.visit(self)
913 if len(node.args) > 0:
914 self.__in_type_hint_stack.append(True)
915 node.args[0].visit(self)
916 self.__in_type_hint_stack.pop()
917 for arg in node.args[1:]:
918 arg.visit(self)
919 return False
920 return True
922 def leave_Call(self, original_node: cst.Call) -> None:
923 self.__top_level_attribute_stack.pop()
924 self.__in_type_hint_stack.pop()
926 def visit_Annotation(self, node: cst.Annotation) -> Optional[bool]:
927 self.__in_annotation_stack.append(True)
929 def leave_Annotation(self, original_node: cst.Annotation) -> None:
930 self.__in_annotation_stack.pop()
932 def visit_SimpleString(self, node: cst.SimpleString) -> Optional[bool]:
933 self._handle_string_annotation(node)
934 return False
936 def visit_ConcatenatedString(self, node: cst.ConcatenatedString) -> Optional[bool]:
937 return not self._handle_string_annotation(node)
939 def _handle_string_annotation(
940 self, node: Union[cst.SimpleString, cst.ConcatenatedString]
941 ) -> bool:
942 """Returns whether it successfully handled the string annotation"""
943 if (
944 self.__in_type_hint_stack[-1] or self.__in_annotation_stack[-1]
945 ) and not self.__in_ignored_subscript:
946 value = node.evaluated_value
947 if value:
948 top_level_annotation = self.__last_string_annotation is None
949 if top_level_annotation:
950 self.__last_string_annotation = node
951 try:
952 mod = cst.parse_module(value)
953 mod.visit(self)
954 except cst.ParserSyntaxError:
955 # swallow string annotation parsing errors
956 # this is the same behavior as cPython
957 pass
958 if top_level_annotation:
959 self.__last_string_annotation = None
960 return True
961 return False
963 def visit_Subscript(self, node: cst.Subscript) -> Optional[bool]:
964 in_type_hint = False
965 if isinstance(node.value, cst.Name):
966 qnames = {qn.name for qn in self.scope.get_qualified_names_for(node.value)}
967 if any(qn.startswith(("typing.", "typing_extensions.")) for qn in qnames):
968 in_type_hint = True
969 if "typing.Literal" in qnames or "typing_extensions.Literal" in qnames:
970 self.__in_ignored_subscript.add(node)
972 self.__in_type_hint_stack.append(in_type_hint)
973 return True
975 def leave_Subscript(self, original_node: cst.Subscript) -> None:
976 self.__in_type_hint_stack.pop()
977 self.__in_ignored_subscript.discard(original_node)
979 def visit_Name(self, node: cst.Name) -> Optional[bool]:
980 # not all Name have ExpressionContext
981 context = self.provider.get_metadata(ExpressionContextProvider, node, None)
982 if context == ExpressionContext.STORE:
983 self.scope.record_assignment(node.value, node)
984 elif context in (ExpressionContext.LOAD, ExpressionContext.DEL, None):
985 access = Access(
986 node,
987 self.scope,
988 is_annotation=bool(
989 self.__in_annotation_stack[-1] and not self.__ignore_annotation
990 ),
991 is_type_hint=bool(self.__in_type_hint_stack[-1]),
992 )
993 self.__deferred_accesses.append(
994 DeferredAccess(
995 access=access,
996 enclosing_attribute=self.__top_level_attribute_stack[-1],
997 enclosing_string_annotation=self.__last_string_annotation,
998 )
999 )
1001 def visit_FunctionDef(self, node: cst.FunctionDef) -> Optional[bool]:
1002 self.scope.record_assignment(node.name.value, node)
1003 self.provider.set_metadata(node.name, self.scope)
1005 with self._new_scope(FunctionScope, node, get_full_name_for_node(node.name)):
1006 node.params.visit(self)
1007 node.body.visit(self)
1009 for decorator in node.decorators:
1010 decorator.visit(self)
1011 returns = node.returns
1012 if returns:
1013 returns.visit(self)
1015 return False
1017 def visit_Lambda(self, node: cst.Lambda) -> Optional[bool]:
1018 with self._new_scope(FunctionScope, node):
1019 node.params.visit(self)
1020 node.body.visit(self)
1021 return False
1023 def visit_Param(self, node: cst.Param) -> Optional[bool]:
1024 self.scope.record_assignment(node.name.value, node)
1025 self.provider.set_metadata(node.name, self.scope)
1026 with self._switch_scope(self.scope.parent):
1027 for field in [node.default, node.annotation]:
1028 if field:
1029 field.visit(self)
1031 return False
1033 def visit_Arg(self, node: cst.Arg) -> bool:
1034 # The keyword of Arg is neither an Assignment nor an Access and we explicitly don't visit it.
1035 value = node.value
1036 if value:
1037 value.visit(self)
1038 return False
1040 def visit_ClassDef(self, node: cst.ClassDef) -> Optional[bool]:
1041 self.scope.record_assignment(node.name.value, node)
1042 self.provider.set_metadata(node.name, self.scope)
1043 for decorator in node.decorators:
1044 decorator.visit(self)
1045 for base in node.bases:
1046 base.visit(self)
1047 for keyword in node.keywords:
1048 keyword.visit(self)
1050 with self._new_scope(ClassScope, node, get_full_name_for_node(node.name)):
1051 for statement in node.body.body:
1052 statement.visit(self)
1053 return False
1055 def visit_ClassDef_bases(self, node: cst.ClassDef) -> None:
1056 self.__ignore_annotation += 1
1058 def leave_ClassDef_bases(self, node: cst.ClassDef) -> None:
1059 self.__ignore_annotation -= 1
1061 def visit_Global(self, node: cst.Global) -> Optional[bool]:
1062 for name_item in node.names:
1063 self.scope.record_global_overwrite(name_item.name.value)
1064 return False
1066 def visit_Nonlocal(self, node: cst.Nonlocal) -> Optional[bool]:
1067 for name_item in node.names:
1068 self.scope.record_nonlocal_overwrite(name_item.name.value)
1069 return False
1071 def visit_ListComp(self, node: cst.ListComp) -> Optional[bool]:
1072 return self._visit_comp_alike(node)
1074 def visit_SetComp(self, node: cst.SetComp) -> Optional[bool]:
1075 return self._visit_comp_alike(node)
1077 def visit_DictComp(self, node: cst.DictComp) -> Optional[bool]:
1078 return self._visit_comp_alike(node)
1080 def visit_GeneratorExp(self, node: cst.GeneratorExp) -> Optional[bool]:
1081 return self._visit_comp_alike(node)
1083 def _visit_comp_alike(
1084 self, node: Union[cst.ListComp, cst.SetComp, cst.DictComp, cst.GeneratorExp]
1085 ) -> bool:
1086 """
1087 Cheat sheet: `[elt for target in iter if ifs]`
1089 Terminology:
1090 target: The variable or pattern we're storing each element of the iter in.
1091 iter: The thing we're iterating over.
1092 ifs: A list of conditions provided
1093 elt: The value that will be computed and "yielded" each time the loop
1094 iterates. For most comprehensions, this is just the `node.elt`, but
1095 DictComp has `key` and `value`, which behave like `node.elt` would.
1098 Nested Comprehension: ``[a for b in c for a in b]`` is a "nested" ListComp.
1099 The outer iterator is in ``node.for_in`` and the inner iterator is in
1100 ``node.for_in.inner_for_in``.
1103 The first comprehension object's iter in generators is evaluated
1104 outside of the ComprehensionScope. Every other comprehension's iter is
1105 evaluated inside the ComprehensionScope. Even though that doesn't seem very sane,
1106 but that appears to be how it works.
1108 non_flat = [ [1,2,3], [4,5,6], [7,8]
1109 flat = [y for x in non_flat for y in x] # this works fine
1111 # This will give a "NameError: name 'x' is not defined":
1112 flat = [y for x in x for y in x]
1113 # x isn't defined, because the first iter is evaluted outside the scope.
1115 # This will give an UnboundLocalError, indicating that the second
1116 # comprehension's iter value is evaluated inside the scope as its elt.
1117 # UnboundLocalError: local variable 'y' referenced before assignment
1118 flat = [y for x in non_flat for y in y]
1119 """
1120 for_in = node.for_in
1121 for_in.iter.visit(self)
1122 self.provider.set_metadata(for_in, self.scope)
1123 with self._new_scope(ComprehensionScope, node):
1124 for_in.target.visit(self)
1125 # Things from here on can refer to the target.
1126 self.scope._assignment_count += 1
1127 for condition in for_in.ifs:
1128 condition.visit(self)
1129 inner_for_in = for_in.inner_for_in
1130 if inner_for_in:
1131 inner_for_in.visit(self)
1132 if isinstance(node, cst.DictComp):
1133 node.key.visit(self)
1134 node.value.visit(self)
1135 else:
1136 node.elt.visit(self)
1137 return False
1139 def visit_For(self, node: cst.For) -> Optional[bool]:
1140 node.target.visit(self)
1141 self.scope._assignment_count += 1
1142 for child in [node.iter, node.body, node.orelse, node.asynchronous]:
1143 if child is not None:
1144 child.visit(self)
1145 return False
1147 def infer_accesses(self) -> None:
1148 # Aggregate access with the same name and batch add with set union as an optimization.
1149 # In worst case, all accesses (m) and assignments (n) refer to the same name,
1150 # the time complexity is O(m x n), this optimizes it as O(m + n).
1151 scope_name_accesses = defaultdict(set)
1152 for def_access in self.__deferred_accesses:
1153 access, enclosing_attribute, enclosing_string_annotation = (
1154 def_access.access,
1155 def_access.enclosing_attribute,
1156 def_access.enclosing_string_annotation,
1157 )
1158 name = ensure_type(access.node, cst.Name).value
1159 if enclosing_attribute is not None:
1160 # if _gen_dotted_names doesn't generate any values, fall back to
1161 # the original name node above
1162 for attr_name, node in _gen_dotted_names(enclosing_attribute):
1163 if attr_name in access.scope:
1164 access.node = node
1165 name = attr_name
1166 break
1168 if enclosing_string_annotation is not None:
1169 access.node = enclosing_string_annotation
1171 scope_name_accesses[(access.scope, name)].add(access)
1172 access.record_assignments(name)
1173 access.scope.record_access(name, access)
1175 for (scope, name), accesses in scope_name_accesses.items():
1176 for assignment in scope[name]:
1177 assignment.record_accesses(accesses)
1179 self.__deferred_accesses = []
1181 def on_leave(self, original_node: cst.CSTNode) -> None:
1182 self.provider.set_metadata(original_node, self.scope)
1183 if isinstance(original_node, _ASSIGNMENT_LIKE_NODES):
1184 self.scope._assignment_count += 1
1185 super().on_leave(original_node)
1188class ScopeProvider(BatchableMetadataProvider[Optional[Scope]]):
1189 """
1190 :class:`ScopeProvider` traverses the entire module and creates the scope inheritance
1191 structure. It provides the scope of name assignment and accesses. It is useful for
1192 more advanced static analysis. E.g. given a :class:`~libcst.FunctionDef`
1193 node, we can check the type of its Scope to figure out whether it is a class method
1194 (:class:`ClassScope`) or a regular function (:class:`GlobalScope`).
1196 Scope metadata is available for most node types other than formatting information nodes
1197 (whitespace, parentheses, etc.).
1198 """
1200 METADATA_DEPENDENCIES = (ExpressionContextProvider,)
1202 def visit_Module(self, node: cst.Module) -> Optional[bool]:
1203 visitor = ScopeVisitor(self)
1204 node.visit(visitor)
1205 visitor.infer_accesses()