stubgen.py

#!/usr/bin/env python3
"""Generator of dynamically typed draft stubs for arbitrary modules.

The logic of this script can be split in three steps:
* parsing options and finding sources:
  - use runtime imports be default (to find also C modules)
  - or use mypy's mechanisms, if importing is prohibited
* (optionally) semantically analysing the sources using mypy (as a single set)
* emitting the stubs text:
  - for Python modules: from ASTs using ASTStubGenerator
  - for C modules using runtime introspection and (optionally) Sphinx docs

During first and third steps some problematic files can be skipped, but any
blocking error during second step will cause the whole program to stop.

Basic usage:

  $ stubgen foo.py bar.py some_directory
  => Generate out/foo.pyi, out/bar.pyi, and stubs for some_directory (recursively).

  $ stubgen -m urllib.parse
  => Generate out/urllib/parse.pyi.

  $ stubgen -p urllib
  => Generate stubs for whole urllib package (recursively).

For C modules, you can get more precise function signatures by parsing .rst (Sphinx)
documentation for extra information. For this, use the --doc-dir option:

  $ stubgen --doc-dir <DIR>/Python-3.4.2/Doc/library -m curses

Note: The generated stubs should be verified manually.

TODO:
 - maybe use .rst docs also for Python modules
 - maybe export more imported names if there is no __all__ (this affects ssl.SSLError, for example)
   - a quick and dirty heuristic would be to turn this on if a module has something like
     'from x import y as _y'
 - we don't seem to always detect properties ('closed' in 'io', for example)
"""

from __future__ import annotations

import argparse
import keyword
import os
import os.path
import sys
import traceback
from typing import Final, Iterable

import mypy.build
import mypy.mixedtraverser
import mypy.parse
import mypy.traverser
import mypy.util
from mypy.build import build
from mypy.errors import CompileError, Errors
from mypy.find_sources import InvalidSourceList, create_source_list
from mypy.modulefinder import (
    BuildSource,
    FindModuleCache,
    ModuleNotFoundReason,
    SearchPaths,
    default_lib_path,
)
from mypy.moduleinspect import ModuleInspect, is_pyc_only
from mypy.nodes import (
    ARG_NAMED,
    ARG_POS,
    ARG_STAR,
    ARG_STAR2,
    IS_ABSTRACT,
    NOT_ABSTRACT,
    AssignmentStmt,
    Block,
    BytesExpr,
    CallExpr,
    ClassDef,
    ComparisonExpr,
    ComplexExpr,
    Decorator,
    DictExpr,
    EllipsisExpr,
    Expression,
    ExpressionStmt,
    FloatExpr,
    FuncBase,
    FuncDef,
    IfStmt,
    Import,
    ImportAll,
    ImportFrom,
    IndexExpr,
    IntExpr,
    ListExpr,
    MemberExpr,
    MypyFile,
    NameExpr,
    OpExpr,
    OverloadedFuncDef,
    SetExpr,
    StarExpr,
    Statement,
    StrExpr,
    TempNode,
    TupleExpr,
    TypeInfo,
    UnaryExpr,
    Var,
)
from mypy.options import Options as MypyOptions
from mypy.stubdoc import ArgSig, FunctionSig
from mypy.stubgenc import InspectionStubGenerator, generate_stub_for_c_module
from mypy.stubutil import (
    BaseStubGenerator,
    CantImport,
    ClassInfo,
    FunctionContext,
    common_dir_prefix,
    fail_missing,
    find_module_path_and_all_py3,
    generate_guarded,
    infer_method_arg_types,
    infer_method_ret_type,
    remove_misplaced_type_comments,
    report_missing,
    walk_packages,
)
from mypy.traverser import (
    all_yield_expressions,
    has_return_statement,
    has_yield_expression,
    has_yield_from_expression,
)
from mypy.types import (
    OVERLOAD_NAMES,
    TPDICT_NAMES,
    TYPED_NAMEDTUPLE_NAMES,
    AnyType,
    CallableType,
    Instance,
    TupleType,
    Type,
    UnboundType,
    get_proper_type,
)
from mypy.visitor import NodeVisitor

# Common ways of naming package containing vendored modules.
VENDOR_PACKAGES: Final = ["packages", "vendor", "vendored", "_vendor", "_vendored_packages"]

# Avoid some file names that are unnecessary or likely to cause trouble (\n for end of path).
BLACKLIST: Final = [
    "/six.py\n",  # Likely vendored six; too dynamic for us to handle
    "/vendored/",  # Vendored packages
    "/vendor/",  # Vendored packages
    "/_vendor/",
    "/_vendored_packages/",
]

# These methods are expected to always return a non-trivial value.
METHODS_WITH_RETURN_VALUE: Final = {
    "__ne__",
    "__eq__",
    "__lt__",
    "__le__",
    "__gt__",
    "__ge__",
    "__hash__",
    "__iter__",
}


class Options:
    """Represents stubgen options.

    This class is mutable to simplify testing.
    """

    def __init__(
        self,
        pyversion: tuple[int, int],
        no_import: bool,
        inspect: bool,
        doc_dir: str,
        search_path: list[str],
        interpreter: str,
        parse_only: bool,
        ignore_errors: bool,
        include_private: bool,
        output_dir: str,
        modules: list[str],
        packages: list[str],
        files: list[str],
        verbose: bool,
        quiet: bool,
        export_less: bool,
        include_docstrings: bool,
    ) -> None:
        # See parse_options for descriptions of the flags.
        self.pyversion = pyversion
        self.no_import = no_import
        self.inspect = inspect
        self.doc_dir = doc_dir
        self.search_path = search_path
        self.interpreter = interpreter
        self.decointerpreter = interpreter
        self.parse_only = parse_only
        self.ignore_errors = ignore_errors
        self.include_private = include_private
        self.output_dir = output_dir
        self.modules = modules
        self.packages = packages
        self.files = files
        self.verbose = verbose
        self.quiet = quiet
        self.export_less = export_less
        self.include_docstrings = include_docstrings


class StubSource:
    """A single source for stub: can be a Python or C module.

    A simple extension of BuildSource that also carries the AST and
    the value of __all__ detected at runtime.
    """

    def __init__(
        self, module: str, path: str | None = None, runtime_all: list[str] | None = None
    ) -> None:
        self.source = BuildSource(path, module, None)
        self.runtime_all = runtime_all
        self.ast: MypyFile | None = None

    def __repr__(self) -> str:
        return f"StubSource({self.source})"

    @property
    def module(self) -> str:
        return self.source.module

    @property
    def path(self) -> str | None:
        return self.source.path


# What was generated previously in the stub file. We keep track of these to generate
# nicely formatted output (add empty line between non-empty classes, for example).
EMPTY: Final = "EMPTY"
FUNC: Final = "FUNC"
CLASS: Final = "CLASS"
EMPTY_CLASS: Final = "EMPTY_CLASS"
VAR: Final = "VAR"
NOT_IN_ALL: Final = "NOT_IN_ALL"

# Indicates that we failed to generate a reasonable output
# for a given node. These should be manually replaced by a user.

ERROR_MARKER: Final = "<ERROR>"


class AliasPrinter(NodeVisitor[str]):
    """Visitor used to collect type aliases _and_ type variable definitions.

    Visit r.h.s of the definition to get the string representation of type alias.
    """

    def __init__(self, stubgen: ASTStubGenerator) -> None:
        self.stubgen = stubgen
        super().__init__()

    def visit_call_expr(self, node: CallExpr) -> str:
        # Call expressions are not usually types, but we also treat `X = TypeVar(...)` as a
        # type alias that has to be preserved (even if TypeVar is not the same as an alias)
        callee = node.callee.accept(self)
        args = []
        for name, arg, kind in zip(node.arg_names, node.args, node.arg_kinds):
            if kind == ARG_POS:
                args.append(arg.accept(self))
            elif kind == ARG_STAR:
                args.append("*" + arg.accept(self))
            elif kind == ARG_STAR2:
                args.append("**" + arg.accept(self))
            elif kind == ARG_NAMED:
                args.append(f"{name}={arg.accept(self)}")
            else:
                raise ValueError(f"Unknown argument kind {kind} in call")
        return f"{callee}({', '.join(args)})"

    def visit_name_expr(self, node: NameExpr) -> str:
        self.stubgen.import_tracker.require_name(node.name)
        return node.name

    def visit_member_expr(self, o: MemberExpr) -> str:
        node: Expression = o
        trailer = ""
        while isinstance(node, MemberExpr):
            trailer = "." + node.name + trailer
            node = node.expr
        if not isinstance(node, NameExpr):
            return ERROR_MARKER
        self.stubgen.import_tracker.require_name(node.name)
        return node.name + trailer

    def visit_str_expr(self, node: StrExpr) -> str:
        return repr(node.value)

    def visit_index_expr(self, node: IndexExpr) -> str:
        base_fullname = self.stubgen.get_fullname(node.base)
        if base_fullname == "typing.Union":
            if isinstance(node.index, TupleExpr):
                return " | ".join([item.accept(self) for item in node.index.items])
            return node.index.accept(self)
        if base_fullname == "typing.Optional":
            return f"{node.index.accept(self)} | None"
        base = node.base.accept(self)
        index = node.index.accept(self)
        if len(index) > 2 and index.startswith("(") and index.endswith(")"):
            index = index[1:-1]
        return f"{base}[{index}]"

    def visit_tuple_expr(self, node: TupleExpr) -> str:
        return f"({', '.join(n.accept(self) for n in node.items)})"

    def visit_list_expr(self, node: ListExpr) -> str:
        return f"[{', '.join(n.accept(self) for n in node.items)}]"

    def visit_dict_expr(self, o: DictExpr) -> str:
        dict_items = []
        for key, value in o.items:
            # This is currently only used for TypedDict where all keys are strings.
            assert isinstance(key, StrExpr)
            dict_items.append(f"{key.accept(self)}: {value.accept(self)}")
        return f"{{{', '.join(dict_items)}}}"

    def visit_ellipsis(self, node: EllipsisExpr) -> str:
        return "..."

    def visit_op_expr(self, o: OpExpr) -> str:
        return f"{o.left.accept(self)} {o.op} {o.right.accept(self)}"

    def visit_star_expr(self, o: StarExpr) -> str:
        return f"*{o.expr.accept(self)}"


def find_defined_names(file: MypyFile) -> set[str]:
    finder = DefinitionFinder()
    file.accept(finder)
    return finder.names


class DefinitionFinder(mypy.traverser.TraverserVisitor):
    """Find names of things defined at the top level of a module."""

    # TODO: Assignment statements etc.

    def __init__(self) -> None:
        # Short names of things defined at the top level.
        self.names: set[str] = set()

    def visit_class_def(self, o: ClassDef) -> None:
        # Don't recurse into classes, as we only keep track of top-level definitions.
        self.names.add(o.name)

    def visit_func_def(self, o: FuncDef) -> None:
        # Don't recurse, as we only keep track of top-level definitions.
        self.names.add(o.name)


def find_referenced_names(file: MypyFile) -> set[str]:
    finder = ReferenceFinder()
    file.accept(finder)
    return finder.refs


def is_none_expr(expr: Expression) -> bool:
    return isinstance(expr, NameExpr) and expr.name == "None"


class ReferenceFinder(mypy.mixedtraverser.MixedTraverserVisitor):
    """Find all name references (both local and global)."""

    # TODO: Filter out local variable and class attribute references

    def __init__(self) -> None:
        # Short names of things defined at the top level.
        self.refs: set[str] = set()

    def visit_block(self, block: Block) -> None:
        if not block.is_unreachable:
            super().visit_block(block)

    def visit_name_expr(self, e: NameExpr) -> None:
        self.refs.add(e.name)

    def visit_instance(self, t: Instance) -> None:
        self.add_ref(t.type.name)
        super().visit_instance(t)

    def visit_unbound_type(self, t: UnboundType) -> None:
        if t.name:
            self.add_ref(t.name)

    def visit_tuple_type(self, t: TupleType) -> None:
        # Ignore fallback
        for item in t.items:
            item.accept(self)

    def visit_callable_type(self, t: CallableType) -> None:
        # Ignore fallback
        for arg in t.arg_types:
            arg.accept(self)
        t.ret_type.accept(self)

    def add_ref(self, fullname: str) -> None:
        self.refs.add(fullname)
        while "." in fullname:
            fullname = fullname.rsplit(".", 1)[0]
            self.refs.add(fullname)


class ASTStubGenerator(BaseStubGenerator, mypy.traverser.TraverserVisitor):
    """Generate stub text from a mypy AST."""

    def __init__(
        self,
        _all_: list[str] | None = None,
        include_private: bool = False,
        analyzed: bool = False,
        export_less: bool = False,
        include_docstrings: bool = False,
    ) -> None:
        super().__init__(_all_, include_private, export_less, include_docstrings)
        self._decorators: list[str] = []
        # Stack of defined variables (per scope).
        self._vars: list[list[str]] = [[]]
        # What was generated previously in the stub file.
        self._state = EMPTY
        self._current_class: ClassDef | None = None
        # Was the tree semantically analysed before?
        self.analyzed = analyzed
        # Short names of methods defined in the body of the current class
        self.method_names: set[str] = set()
        self.processing_dataclass = False

    def visit_mypy_file(self, o: MypyFile) -> None:
        self.module_name = o.fullname  # Current module being processed
        self.path = o.path
        self.set_defined_names(find_defined_names(o))
        self.referenced_names = find_referenced_names(o)
        super().visit_mypy_file(o)
        self.check_undefined_names()

    def visit_overloaded_func_def(self, o: OverloadedFuncDef) -> None:
        """@property with setters and getters, @overload chain and some others."""
        overload_chain = False
        for item in o.items:
            if not isinstance(item, Decorator):
                continue
            if self.is_private_name(item.func.name, item.func.fullname):
                continue

            self.process_decorator(item)
            if not overload_chain:
                self.visit_func_def(item.func)
                if item.func.is_overload:
                    overload_chain = True
            elif item.func.is_overload:
                self.visit_func_def(item.func)
            else:
                # skip the overload implementation and clear the decorator we just processed
                self.clear_decorators()

    def get_default_function_sig(self, func_def: FuncDef, ctx: FunctionContext) -> FunctionSig:
        args = self._get_func_args(func_def, ctx)
        retname = self._get_func_return(func_def, ctx)
        return FunctionSig(func_def.name, args, retname)

    def _get_func_args(self, o: FuncDef, ctx: FunctionContext) -> list[ArgSig]:
        args: list[ArgSig] = []

        for i, arg_ in enumerate(o.arguments):
            var = arg_.variable
            kind = arg_.kind
            name = var.name
            annotated_type = (
                o.unanalyzed_type.arg_types[i]
                if isinstance(o.unanalyzed_type, CallableType)
                else None
            )
            # I think the name check is incorrect: there are libraries which
            # name their 0th argument other than self/cls
            is_self_arg = i == 0 and name == "self"
            is_cls_arg = i == 0 and name == "cls"
            typename: str | None = None
            if annotated_type and not is_self_arg and not is_cls_arg:
                # Luckily, an argument explicitly annotated with "Any" has
                # type "UnboundType" and will not match.
                if not isinstance(get_proper_type(annotated_type), AnyType):
                    typename = self.print_annotation(annotated_type)

            if kind.is_named() and not any(arg.name.startswith("*") for arg in args):
                args.append(ArgSig("*"))

            default = "..."
            if arg_.initializer:
                if not typename:
                    typename = self.get_str_type_of_node(arg_.initializer, True, False)
                potential_default, valid = self.get_str_default_of_node(arg_.initializer)
                if valid and len(potential_default) <= 200:
                    default = potential_default
            elif kind == ARG_STAR:
                name = f"*{name}"
            elif kind == ARG_STAR2:
                name = f"**{name}"

            args.append(
                ArgSig(name, typename, default=bool(arg_.initializer), default_value=default)
            )

        if ctx.class_info is not None and all(
            arg.type is None and arg.default is False for arg in args
        ):
            new_args = infer_method_arg_types(
                ctx.name, ctx.class_info.self_var, [arg.name for arg in args]
            )
            if new_args is not None:
                args = new_args

        is_dataclass_generated = (
            self.analyzed and self.processing_dataclass and o.info.names[o.name].plugin_generated
        )
        if o.name == "__init__" and is_dataclass_generated and "**" in [a.name for a in args]:
            # The dataclass plugin generates invalid nameless "*" and "**" arguments
            new_name = "".join(a.name.strip("*") for a in args)
            for arg in args:
                if arg.name == "*":
                    arg.name = f"*{new_name}_"  # this name is guaranteed to be unique
                elif arg.name == "**":
                    arg.name = f"**{new_name}__"  # same here
        return args

    def _get_func_return(self, o: FuncDef, ctx: FunctionContext) -> str | None:
        if o.name != "__init__" and isinstance(o.unanalyzed_type, CallableType):
            if isinstance(get_proper_type(o.unanalyzed_type.ret_type), AnyType):
                # Luckily, a return type explicitly annotated with "Any" has
                # type "UnboundType" and will enter the else branch.
                return None  # implicit Any
            else:
                return self.print_annotation(o.unanalyzed_type.ret_type)
        if o.abstract_status == IS_ABSTRACT or o.name in METHODS_WITH_RETURN_VALUE:
            # Always assume abstract methods return Any unless explicitly annotated. Also
            # some dunder methods should not have a None return type.
            return None  # implicit Any
        retname = infer_method_ret_type(o.name)
        if retname is not None:
            return retname
        if has_yield_expression(o) or has_yield_from_expression(o):
            generator_name = self.add_name("collections.abc.Generator")
            yield_name = "None"
            send_name = "None"
            return_name = "None"
            if has_yield_from_expression(o):
                yield_name = send_name = self.add_name("_typeshed.Incomplete")
            else:
                for expr, in_assignment in all_yield_expressions(o):
                    if expr.expr is not None and not is_none_expr(expr.expr):
                        yield_name = self.add_name("_typeshed.Incomplete")
                    if in_assignment:
                        send_name = self.add_name("_typeshed.Incomplete")
            if has_return_statement(o):
                return_name = self.add_name("_typeshed.Incomplete")
            return f"{generator_name}[{yield_name}, {send_name}, {return_name}]"
        if not has_return_statement(o) and o.abstract_status == NOT_ABSTRACT:
            return "None"
        return None

    def _get_func_docstring(self, node: FuncDef) -> str | None:
        if not node.body.body:
            return None
        expr = node.body.body[0]
        if isinstance(expr, ExpressionStmt) and isinstance(expr.expr, StrExpr):
            return expr.expr.value
        return None

    def visit_func_def(self, o: FuncDef) -> None:
        is_dataclass_generated = (
            self.analyzed and self.processing_dataclass and o.info.names[o.name].plugin_generated
        )
        if is_dataclass_generated and o.name != "__init__":
            # Skip methods generated by the @dataclass decorator (except for __init__)
            return
        if (
            self.is_private_name(o.name, o.fullname)
            or self.is_not_in_all(o.name)
            or (self.is_recorded_name(o.name) and not o.is_overload)
        ):
            self.clear_decorators()
            return
        if self.is_top_level() and self._state not in (EMPTY, FUNC):
            self.add("\n")
        if not self.is_top_level():
            self_inits = find_self_initializers(o)
            for init, value in self_inits:
                if init in self.method_names:
                    # Can't have both an attribute and a method/property with the same name.
                    continue
                init_code = self.get_init(init, value)
                if init_code:
                    self.add(init_code)

        if self._current_class is not None:
            if len(o.arguments):
                self_var = o.arguments[0].variable.name
            else:
                self_var = "self"
            class_info = ClassInfo(self._current_class.name, self_var)
        else:
            class_info = None

        ctx = FunctionContext(
            module_name=self.module_name,
            name=o.name,
            docstring=self._get_func_docstring(o),
            is_abstract=o.abstract_status != NOT_ABSTRACT,
            class_info=class_info,
        )

        self.record_name(o.name)

        default_sig = self.get_default_function_sig(o, ctx)
        sigs = self.get_signatures(default_sig, self.sig_generators, ctx)

        for output in self.format_func_def(
            sigs, is_coroutine=o.is_coroutine, decorators=self._decorators, docstring=ctx.docstring
        ):
            self.add(output + "\n")

        self.clear_decorators()
        self._state = FUNC

    def visit_decorator(self, o: Decorator) -> None:
        if self.is_private_name(o.func.name, o.func.fullname):
            return
        self.process_decorator(o)
        self.visit_func_def(o.func)

    def process_decorator(self, o: Decorator) -> None:
        """Process a series of decorators.

        Only preserve certain special decorators such as @abstractmethod.
        """
        o.func.is_overload = False
        for decorator in o.original_decorators:
            if not isinstance(decorator, (NameExpr, MemberExpr)):
                continue
            qualname = get_qualified_name(decorator)
            fullname = self.get_fullname(decorator)
            if fullname in (
                "builtins.property",
                "builtins.staticmethod",
                "builtins.classmethod",
                "functools.cached_property",
            ):
                self.add_decorator(qualname, require_name=True)
            elif fullname in (
                "asyncio.coroutine",
                "asyncio.coroutines.coroutine",
                "types.coroutine",
            ):
                o.func.is_awaitable_coroutine = True
                self.add_decorator(qualname, require_name=True)
            elif fullname == "abc.abstractmethod":
                self.add_decorator(qualname, require_name=True)
                o.func.abstract_status = IS_ABSTRACT
            elif fullname in (
                "abc.abstractproperty",
                "abc.abstractstaticmethod",
                "abc.abstractclassmethod",
            ):
                abc_module = qualname.rpartition(".")[0]
                if not abc_module:
                    self.import_tracker.add_import("abc")
                builtin_decorator_replacement = fullname[len("abc.abstract") :]
                self.add_decorator(builtin_decorator_replacement, require_name=False)
                self.add_decorator(f"{abc_module or 'abc'}.abstractmethod", require_name=True)
                o.func.abstract_status = IS_ABSTRACT
            elif fullname in OVERLOAD_NAMES:
                self.add_decorator(qualname, require_name=True)
                o.func.is_overload = True
            elif qualname.endswith((".setter", ".deleter")):
                self.add_decorator(qualname, require_name=False)

    def get_fullname(self, expr: Expression) -> str:
        """Return the expression's full name."""
        if (
            self.analyzed
            and isinstance(expr, (NameExpr, MemberExpr))
            and expr.fullname
            and not (isinstance(expr.node, Var) and expr.node.is_suppressed_import)
        ):
            return expr.fullname
        name = get_qualified_name(expr)
        return self.resolve_name(name)

    def visit_class_def(self, o: ClassDef) -> None:
        self._current_class = o
        self.method_names = find_method_names(o.defs.body)
        sep: int | None = None
        if self.is_top_level() and self._state != EMPTY:
            sep = len(self._output)
            self.add("\n")
        decorators = self.get_class_decorators(o)
        for d in decorators:
            self.add(f"{self._indent}@{d}\n")
        self.record_name(o.name)
        base_types = self.get_base_types(o)
        if base_types:
            for base in base_types:
                self.import_tracker.require_name(base)
        if isinstance(o.metaclass, (NameExpr, MemberExpr)):
            meta = o.metaclass.accept(AliasPrinter(self))
            base_types.append("metaclass=" + meta)
        elif self.analyzed and o.info.is_abstract and not o.info.is_protocol:
            base_types.append("metaclass=abc.ABCMeta")
            self.import_tracker.add_import("abc")
            self.import_tracker.require_name("abc")
        bases = f"({', '.join(base_types)})" if base_types else ""
        self.add(f"{self._indent}class {o.name}{bases}:\n")
        self.indent()
        if self._include_docstrings and o.docstring:
            docstring = mypy.util.quote_docstring(o.docstring)
            self.add(f"{self._indent}{docstring}\n")
        n = len(self._output)
        self._vars.append([])
        super().visit_class_def(o)
        self.dedent()
        self._vars.pop()
        self._vars[-1].append(o.name)
        if len(self._output) == n:
            if self._state == EMPTY_CLASS and sep is not None:
                self._output[sep] = ""
            if not (self._include_docstrings and o.docstring):
                self._output[-1] = self._output[-1][:-1] + " ...\n"
            self._state = EMPTY_CLASS
        else:
            self._state = CLASS
        self.method_names = set()
        self.processing_dataclass = False
        self._current_class = None

    def get_base_types(self, cdef: ClassDef) -> list[str]:
        """Get list of base classes for a class."""
        base_types: list[str] = []
        p = AliasPrinter(self)
        for base in cdef.base_type_exprs + cdef.removed_base_type_exprs:
            if isinstance(base, (NameExpr, MemberExpr)):
                if self.get_fullname(base) != "builtins.object":
                    base_types.append(get_qualified_name(base))
            elif isinstance(base, IndexExpr):
                base_types.append(base.accept(p))
            elif isinstance(base, CallExpr):
                # namedtuple(typename, fields), NamedTuple(typename, fields) calls can
                # be used as a base class. The first argument is a string literal that
                # is usually the same as the class name.
                #
                # Note:
                # A call-based named tuple as a base class cannot be safely converted to
                # a class-based NamedTuple definition because class attributes defined
                # in the body of the class inheriting from the named tuple call are not
                # namedtuple fields at runtime.
                if self.is_namedtuple(base):
                    nt_fields = self._get_namedtuple_fields(base)
                    assert isinstance(base.args[0], StrExpr)
                    typename = base.args[0].value
                    if nt_fields is None:
                        # Invalid namedtuple() call, cannot determine fields
                        base_types.append(self.add_name("_typeshed.Incomplete"))
                        continue
                    fields_str = ", ".join(f"({f!r}, {t})" for f, t in nt_fields)
                    namedtuple_name = self.add_name("typing.NamedTuple")
                    base_types.append(f"{namedtuple_name}({typename!r}, [{fields_str}])")
                elif self.is_typed_namedtuple(base):
                    base_types.append(base.accept(p))
                else:
                    # At this point, we don't know what the base class is, so we
                    # just use Incomplete as the base class.
                    base_types.append(self.add_name("_typeshed.Incomplete"))
        for name, value in cdef.keywords.items():
            if name == "metaclass":
                continue  # handled separately
            base_types.append(f"{name}={value.accept(p)}")
        return base_types

    def get_class_decorators(self, cdef: ClassDef) -> list[str]:
        decorators: list[str] = []
        p = AliasPrinter(self)
        for d in cdef.decorators:
            if self.is_dataclass(d):
                decorators.append(d.accept(p))
                self.import_tracker.require_name(get_qualified_name(d))
                self.processing_dataclass = True
        return decorators

    def is_dataclass(self, expr: Expression) -> bool:
        if isinstance(expr, CallExpr):
            expr = expr.callee
        return self.get_fullname(expr) == "dataclasses.dataclass"

    def visit_block(self, o: Block) -> None:
        # Unreachable statements may be partially uninitialized and that may
        # cause trouble.
        if not o.is_unreachable:
            super().visit_block(o)

    def visit_assignment_stmt(self, o: AssignmentStmt) -> None:
        foundl = []

        for lvalue in o.lvalues:
            if isinstance(lvalue, NameExpr) and isinstance(o.rvalue, CallExpr):
                if self.is_namedtuple(o.rvalue) or self.is_typed_namedtuple(o.rvalue):
                    self.process_namedtuple(lvalue, o.rvalue)
                    foundl.append(False)  # state is updated in process_namedtuple
                    continue
                if self.is_typeddict(o.rvalue):
                    self.process_typeddict(lvalue, o.rvalue)
                    foundl.append(False)  # state is updated in process_typeddict
                    continue
            if (
                isinstance(lvalue, NameExpr)
                and not self.is_private_name(lvalue.name)
                # it is never an alias with explicit annotation
                and not o.unanalyzed_type
                and self.is_alias_expression(o.rvalue)
            ):
                self.process_typealias(lvalue, o.rvalue)
                continue
            if isinstance(lvalue, (TupleExpr, ListExpr)):
                items = lvalue.items
                if isinstance(o.unanalyzed_type, TupleType):  # type: ignore[misc]
                    annotations: Iterable[Type | None] = o.unanalyzed_type.items
                else:
                    annotations = [None] * len(items)
            else:
                items = [lvalue]
                annotations = [o.unanalyzed_type]
            sep = False
            found = False
            for item, annotation in zip(items, annotations):
                if isinstance(item, NameExpr):
                    init = self.get_init(item.name, o.rvalue, annotation)
                    if init:
                        found = True
                        if not sep and self.is_top_level() and self._state not in (EMPTY, VAR):
                            init = "\n" + init
                            sep = True
                        self.add(init)
                        self.record_name(item.name)
            foundl.append(found)

        if all(foundl):
            self._state = VAR

    def is_namedtuple(self, expr: CallExpr) -> bool:
        return self.get_fullname(expr.callee) == "collections.namedtuple"

    def is_typed_namedtuple(self, expr: CallExpr) -> bool:
        return self.get_fullname(expr.callee) in TYPED_NAMEDTUPLE_NAMES

    def _get_namedtuple_fields(self, call: CallExpr) -> list[tuple[str, str]] | None:
        if self.is_namedtuple(call):
            fields_arg = call.args[1]
            if isinstance(fields_arg, StrExpr):
                field_names = fields_arg.value.replace(",", " ").split()
            elif isinstance(fields_arg, (ListExpr, TupleExpr)):
                field_names = []
                for field in fields_arg.items:
                    if not isinstance(field, StrExpr):
                        return None
                    field_names.append(field.value)
            else:
                return None  # Invalid namedtuple fields type
            if field_names:
                incomplete = self.add_name("_typeshed.Incomplete")
                return [(field_name, incomplete) for field_name in field_names]
            else:
                return []

        elif self.is_typed_namedtuple(call):
            fields_arg = call.args[1]
            if not isinstance(fields_arg, (ListExpr, TupleExpr)):
                return None
            fields: list[tuple[str, str]] = []
            p = AliasPrinter(self)
            for field in fields_arg.items:
                if not (isinstance(field, TupleExpr) and len(field.items) == 2):
                    return None
                field_name, field_type = field.items
                if not isinstance(field_name, StrExpr):
                    return None
                fields.append((field_name.value, field_type.accept(p)))
            return fields
        else:
            return None  # Not a named tuple call

    def process_namedtuple(self, lvalue: NameExpr, rvalue: CallExpr) -> None:
        if self._state == CLASS:
            self.add("\n")

        if not isinstance(rvalue.args[0], StrExpr):
            self.annotate_as_incomplete(lvalue)
            return

        fields = self._get_namedtuple_fields(rvalue)
        if fields is None:
            self.annotate_as_incomplete(lvalue)
            return
        bases = self.add_name("typing.NamedTuple")
        # TODO: Add support for generic NamedTuples. Requires `Generic` as base class.
        class_def = f"{self._indent}class {lvalue.name}({bases}):"
        if len(fields) == 0:
            self.add(f"{class_def} ...\n")
            self._state = EMPTY_CLASS
        else:
            if self._state not in (EMPTY, CLASS):
                self.add("\n")
            self.add(f"{class_def}\n")
            for f_name, f_type in fields:
                self.add(f"{self._indent}    {f_name}: {f_type}\n")
            self._state = CLASS

    def is_typeddict(self, expr: CallExpr) -> bool:
        return self.get_fullname(expr.callee) in TPDICT_NAMES

    def process_typeddict(self, lvalue: NameExpr, rvalue: CallExpr) -> None:
        if self._state == CLASS:
            self.add("\n")

        if not isinstance(rvalue.args[0], StrExpr):
            self.annotate_as_incomplete(lvalue)
            return

        items: list[tuple[str, Expression]] = []
        total: Expression | None = None
        if len(rvalue.args) > 1 and rvalue.arg_kinds[1] == ARG_POS:
            if not isinstance(rvalue.args[1], DictExpr):
                self.annotate_as_incomplete(lvalue)
                return
            for attr_name, attr_type in rvalue.args[1].items:
                if not isinstance(attr_name, StrExpr):
                    self.annotate_as_incomplete(lvalue)
                    return
                items.append((attr_name.value, attr_type))
            if len(rvalue.args) > 2:
                if rvalue.arg_kinds[2] != ARG_NAMED or rvalue.arg_names[2] != "total":
                    self.annotate_as_incomplete(lvalue)
                    return
                total = rvalue.args[2]
        else:
            for arg_name, arg in zip(rvalue.arg_names[1:], rvalue.args[1:]):
                if not isinstance(arg_name, str):
                    self.annotate_as_incomplete(lvalue)
                    return
                if arg_name == "total":
                    total = arg
                else:
                    items.append((arg_name, arg))
        p = AliasPrinter(self)
        if any(not key.isidentifier() or keyword.iskeyword(key) for key, _ in items):
            # Keep the call syntax if there are non-identifier or reserved keyword keys.
            self.add(f"{self._indent}{lvalue.name} = {rvalue.accept(p)}\n")
            self._state = VAR
        else:
            bases = self.add_name("typing_extensions.TypedDict")
            # TODO: Add support for generic TypedDicts. Requires `Generic` as base class.
            if total is not None:
                bases += f", total={total.accept(p)}"
            class_def = f"{self._indent}class {lvalue.name}({bases}):"
            if len(items) == 0:
                self.add(f"{class_def} ...\n")
                self._state = EMPTY_CLASS
            else:
                if self._state not in (EMPTY, CLASS):
                    self.add("\n")
                self.add(f"{class_def}\n")
                for key, key_type in items:
                    self.add(f"{self._indent}    {key}: {key_type.accept(p)}\n")
                self._state = CLASS

    def annotate_as_incomplete(self, lvalue: NameExpr) -> None:
        incomplete = self.add_name("_typeshed.Incomplete")
        self.add(f"{self._indent}{lvalue.name}: {incomplete}\n")
        self._state = VAR

    def is_alias_expression(self, expr: Expression, top_level: bool = True) -> bool:
        """Return True for things that look like target for an alias.

        Used to know if assignments look like type aliases, function alias,
        or module alias.
        """
        # Assignment of TypeVar(...)  and other typevar-likes are passed through
        if isinstance(expr, CallExpr) and self.get_fullname(expr.callee) in (
            "typing.TypeVar",
            "typing_extensions.TypeVar",
            "typing.ParamSpec",
            "typing_extensions.ParamSpec",
            "typing.TypeVarTuple",
            "typing_extensions.TypeVarTuple",
        ):
            return True
        elif isinstance(expr, EllipsisExpr):
            return not top_level
        elif isinstance(expr, NameExpr):
            if expr.name in ("True", "False"):
                return False
            elif expr.name == "None":
                return not top_level
            else:
                return not self.is_private_name(expr.name)
        elif isinstance(expr, MemberExpr) and self.analyzed:
            # Also add function and module aliases.
            return (
                top_level
                and isinstance(expr.node, (FuncDef, Decorator, MypyFile))
                or isinstance(expr.node, TypeInfo)
            ) and not self.is_private_member(expr.node.fullname)
        elif (
            isinstance(expr, IndexExpr)
            and isinstance(expr.base, NameExpr)
            and not self.is_private_name(expr.base.name)
        ):
            if isinstance(expr.index, TupleExpr):
                indices = expr.index.items
            else:
                indices = [expr.index]
            if expr.base.name == "Callable" and len(indices) == 2:
                args, ret = indices
                if isinstance(args, EllipsisExpr):
                    indices = [ret]
                elif isinstance(args, ListExpr):
                    indices = args.items + [ret]
                else:
                    return False
            return all(self.is_alias_expression(i, top_level=False) for i in indices)
        else:
            return False

    def process_typealias(self, lvalue: NameExpr, rvalue: Expression) -> None:
        p = AliasPrinter(self)
        self.add(f"{self._indent}{lvalue.name} = {rvalue.accept(p)}\n")
        self.record_name(lvalue.name)
        self._vars[-1].append(lvalue.name)

    def visit_if_stmt(self, o: IfStmt) -> None:
        # Ignore if __name__ == '__main__'.
        expr = o.expr[0]
        if (
            isinstance(expr, ComparisonExpr)
            and isinstance(expr.operands[0], NameExpr)
            and isinstance(expr.operands[1], StrExpr)
            and expr.operands[0].name == "__name__"
            and "__main__" in expr.operands[1].value
        ):
            return
        super().visit_if_stmt(o)

    def visit_import_all(self, o: ImportAll) -> None:
        self.add_import_line(f"from {'.' * o.relative}{o.id} import *\n")

    def visit_import_from(self, o: ImportFrom) -> None:
        exported_names: set[str] = set()
        import_names = []
        module, relative = translate_module_name(o.id, o.relative)
        if self.module_name:
            full_module, ok = mypy.util.correct_relative_import(
                self.module_name, relative, module, self.path.endswith(".__init__.py")
            )
            if not ok:
                full_module = module
        else:
            full_module = module
        if module == "__future__":
            return  # Not preserved
        for name, as_name in o.names:
            if name == "six":
                # Vendored six -- translate into plain 'import six'.
                self.visit_import(Import([("six", None)]))
                continue
            if self.should_reexport(name, full_module, as_name is not None):
                self.import_tracker.reexport(name)
                as_name = name
            import_names.append((name, as_name))
        self.import_tracker.add_import_from("." * relative + module, import_names)
        self._vars[-1].extend(alias or name for name, alias in import_names)
        for name, alias in import_names:
            self.record_name(alias or name)

        if self._all_:
            # Include "import from"s that import names defined in __all__.
            names = [
                name
                for name, alias in o.names
                if name in self._all_ and alias is None and name not in self.IGNORED_DUNDERS
            ]
            exported_names.update(names)

    def visit_import(self, o: Import) -> None:
        for id, as_id in o.ids:
            self.import_tracker.add_import(id, as_id)
            if as_id is None:
                target_name = id.split(".")[0]
            else:
                target_name = as_id
            self._vars[-1].append(target_name)
            self.record_name(target_name)

    def get_init(
        self, lvalue: str, rvalue: Expression, annotation: Type | None = None
    ) -> str | None:
        """Return initializer for a variable.

        Return None if we've generated one already or if the variable is internal.
        """
        if lvalue in self._vars[-1]:
            # We've generated an initializer already for this variable.
            return None
        # TODO: Only do this at module top level.
        if self.is_private_name(lvalue) or self.is_not_in_all(lvalue):
            return None
        self._vars[-1].append(lvalue)
        if annotation is not None:
            typename = self.print_annotation(annotation)
            if (
                isinstance(annotation, UnboundType)
                and not annotation.args
                and annotation.name == "Final"
                and self.import_tracker.module_for.get("Final") in self.TYPING_MODULE_NAMES
            ):
                # Final without type argument is invalid in stubs.
                final_arg = self.get_str_type_of_node(rvalue)
                typename += f"[{final_arg}]"
        elif self.processing_dataclass:
            # attribute without annotation is not a dataclass field, don't add annotation.
            return f"{self._indent}{lvalue} = ...\n"
        else:
            typename = self.get_str_type_of_node(rvalue)
        initializer = self.get_assign_initializer(rvalue)
        return f"{self._indent}{lvalue}: {typename}{initializer}\n"

    def get_assign_initializer(self, rvalue: Expression) -> str:
        """Does this rvalue need some special initializer value?"""
        if not self._current_class:
            return ""
        # Current rules
        # 1. Return `...` if we are dealing with `NamedTuple` or `dataclass` field and
        #    it has an existing default value
        if (
            self._current_class.info
            and self._current_class.info.is_named_tuple
            and not isinstance(rvalue, TempNode)
        ):
            return " = ..."
        if self.processing_dataclass and not (isinstance(rvalue, TempNode) and rvalue.no_rhs):
            return " = ..."
        # TODO: support other possible cases, where initializer is important

        # By default, no initializer is required:
        return ""

    def add_decorator(self, name: str, require_name: bool = False) -> None:
        if require_name:
            self.import_tracker.require_name(name)
        self._decorators.append(f"@{name}")

    def clear_decorators(self) -> None:
        self._decorators.clear()

    def is_private_member(self, fullname: str) -> bool:
        parts = fullname.split(".")
        return any(self.is_private_name(part) for part in parts)

    def get_str_type_of_node(
        self, rvalue: Expression, can_infer_optional: bool = False, can_be_any: bool = True
    ) -> str:
        rvalue = self.maybe_unwrap_unary_expr(rvalue)

        if isinstance(rvalue, IntExpr):
            return "int"
        if isinstance(rvalue, StrExpr):
            return "str"
        if isinstance(rvalue, BytesExpr):
            return "bytes"
        if isinstance(rvalue, FloatExpr):
            return "float"
        if isinstance(rvalue, ComplexExpr):  # 1j
            return "complex"
        if isinstance(rvalue, OpExpr) and rvalue.op in ("-", "+"):  # -1j + 1
            if isinstance(self.maybe_unwrap_unary_expr(rvalue.left), ComplexExpr) or isinstance(
                self.maybe_unwrap_unary_expr(rvalue.right), ComplexExpr
            ):
                return "complex"
        if isinstance(rvalue, NameExpr) and rvalue.name in ("True", "False"):
            return "bool"
        if can_infer_optional and isinstance(rvalue, NameExpr) and rvalue.name == "None":
            return f"{self.add_name('_typeshed.Incomplete')} | None"
        if can_be_any:
            return self.add_name("_typeshed.Incomplete")
        else:
            return ""

    def maybe_unwrap_unary_expr(self, expr: Expression) -> Expression:
        """Unwrap (possibly nested) unary expressions.

        But, some unary expressions can change the type of expression.
        While we want to preserve it. For example, `~True` is `int`.
        So, we only allow a subset of unary expressions to be unwrapped.
        """
        if not isinstance(expr, UnaryExpr):
            return expr

        # First, try to unwrap `[+-]+ (int|float|complex)` expr:
        math_ops = ("+", "-")
        if expr.op in math_ops:
            while isinstance(expr, UnaryExpr):
                if expr.op not in math_ops or not isinstance(
                    expr.expr, (IntExpr, FloatExpr, ComplexExpr, UnaryExpr)
                ):
                    break
                expr = expr.expr
            return expr

        # Next, try `not bool` expr:
        if expr.op == "not":
            while isinstance(expr, UnaryExpr):
                if expr.op != "not" or not isinstance(expr.expr, (NameExpr, UnaryExpr)):
                    break
                if isinstance(expr.expr, NameExpr) and expr.expr.name not in ("True", "False"):
                    break
                expr = expr.expr
            return expr

        # This is some other unary expr, we cannot do anything with it (yet?).
        return expr

    def get_str_default_of_node(self, rvalue: Expression) -> tuple[str, bool]:
        """Get a string representation of the default value of a node.

        Returns a 2-tuple of the default and whether or not it is valid.
        """
        if isinstance(rvalue, NameExpr):
            if rvalue.name in ("None", "True", "False"):
                return rvalue.name, True
        elif isinstance(rvalue, (IntExpr, FloatExpr)):
            return f"{rvalue.value}", True
        elif isinstance(rvalue, UnaryExpr):
            if isinstance(rvalue.expr, (IntExpr, FloatExpr)):
                return f"{rvalue.op}{rvalue.expr.value}", True
        elif isinstance(rvalue, StrExpr):
            return repr(rvalue.value), True
        elif isinstance(rvalue, BytesExpr):
            return "b" + repr(rvalue.value).replace("\\\\", "\\"), True
        elif isinstance(rvalue, TupleExpr):
            items_defaults = []
            for e in rvalue.items:
                e_default, valid = self.get_str_default_of_node(e)
                if not valid:
                    break
                items_defaults.append(e_default)
            else:
                closing = ",)" if len(items_defaults) == 1 else ")"
                default = "(" + ", ".join(items_defaults) + closing
                return default, True
        elif isinstance(rvalue, ListExpr):
            items_defaults = []
            for e in rvalue.items:
                e_default, valid = self.get_str_default_of_node(e)
                if not valid:
                    break
                items_defaults.append(e_default)
            else:
                default = "[" + ", ".join(items_defaults) + "]"
                return default, True
        elif isinstance(rvalue, SetExpr):
            items_defaults = []
            for e in rvalue.items:
                e_default, valid = self.get_str_default_of_node(e)
                if not valid:
                    break
                items_defaults.append(e_default)
            else:
                if items_defaults:
                    default = "{" + ", ".join(items_defaults) + "}"
                    return default, True
        elif isinstance(rvalue, DictExpr):
            items_defaults = []
            for k, v in rvalue.items:
                if k is None:
                    break
                k_default, k_valid = self.get_str_default_of_node(k)
                v_default, v_valid = self.get_str_default_of_node(v)
                if not (k_valid and v_valid):
                    break
                items_defaults.append(f"{k_default}: {v_default}")
            else:
                default = "{" + ", ".join(items_defaults) + "}"
                return default, True
        return "...", False

    def should_reexport(self, name: str, full_module: str, name_is_alias: bool) -> bool:
        is_private = self.is_private_name(name, full_module + "." + name)
        if (
            not name_is_alias
            and name not in self.referenced_names
            and (not self._all_ or name in self.IGNORED_DUNDERS)
            and not is_private
            and full_module not in ("abc", "asyncio") + self.TYPING_MODULE_NAMES
        ):
            # An imported name that is never referenced in the module is assumed to be
            # exported, unless there is an explicit __all__. Note that we need to special
            # case 'abc' since some references are deleted during semantic analysis.
            return True
        return super().should_reexport(name, full_module, name_is_alias)


def find_method_names(defs: list[Statement]) -> set[str]:
    # TODO: Traverse into nested definitions
    result = set()
    for defn in defs:
        if isinstance(defn, FuncDef):
            result.add(defn.name)
        elif isinstance(defn, Decorator):
            result.add(defn.func.name)
        elif isinstance(defn, OverloadedFuncDef):
            for item in defn.items:
                result.update(find_method_names([item]))
    return result


class SelfTraverser(mypy.traverser.TraverserVisitor):
    def __init__(self) -> None:
        self.results: list[tuple[str, Expression]] = []

    def visit_assignment_stmt(self, o: AssignmentStmt) -> None:
        lvalue = o.lvalues[0]
        if (
            isinstance(lvalue, MemberExpr)
            and isinstance(lvalue.expr, NameExpr)
            and lvalue.expr.name == "self"
        ):
            self.results.append((lvalue.name, o.rvalue))


def find_self_initializers(fdef: FuncBase) -> list[tuple[str, Expression]]:
    """Find attribute initializers in a method.

    Return a list of pairs (attribute name, r.h.s. expression).
    """
    traverser = SelfTraverser()
    fdef.accept(traverser)
    return traverser.results


def get_qualified_name(o: Expression) -> str:
    if isinstance(o, NameExpr):
        return o.name
    elif isinstance(o, MemberExpr):
        return f"{get_qualified_name(o.expr)}.{o.name}"
    else:
        return ERROR_MARKER


def remove_blacklisted_modules(modules: list[StubSource]) -> list[StubSource]:
    return [
        module for module in modules if module.path is None or not is_blacklisted_path(module.path)
    ]


def split_pyc_from_py(modules: list[StubSource]) -> tuple[list[StubSource], list[StubSource]]:
    py_modules = []
    pyc_modules = []
    for mod in modules:
        if is_pyc_only(mod.path):
            pyc_modules.append(mod)
        else:
            py_modules.append(mod)
    return pyc_modules, py_modules


def is_blacklisted_path(path: str) -> bool:
    return any(substr in (normalize_path_separators(path) + "\n") for substr in BLACKLIST)


def normalize_path_separators(path: str) -> str:
    if sys.platform == "win32":
        return path.replace("\\", "/")
    return path


def collect_build_targets(
    options: Options, mypy_opts: MypyOptions
) -> tuple[list[StubSource], list[StubSource], list[StubSource]]:
    """Collect files for which we need to generate stubs.

    Return list of py modules, pyc modules, and C modules.
    """
    if options.packages or options.modules:
        if options.no_import:
            py_modules = find_module_paths_using_search(
                options.modules, options.packages, options.search_path, options.pyversion
            )
            c_modules: list[StubSource] = []
        else:
            # Using imports is the default, since we can also find C modules.
            py_modules, c_modules = find_module_paths_using_imports(
                options.modules, options.packages, options.verbose, options.quiet
            )
    else:
        # Use mypy native source collection for files and directories.
        try:
            source_list = create_source_list(options.files, mypy_opts)
        except InvalidSourceList as e:
            raise SystemExit(str(e)) from e
        py_modules = [StubSource(m.module, m.path) for m in source_list]
        c_modules = []

    py_modules = remove_blacklisted_modules(py_modules)
    pyc_mod, py_mod = split_pyc_from_py(py_modules)
    return py_mod, pyc_mod, c_modules


def find_module_paths_using_imports(
    modules: list[str], packages: list[str], verbose: bool, quiet: bool
) -> tuple[list[StubSource], list[StubSource]]:
    """Find path and runtime value of __all__ (if possible) for modules and packages.

    This function uses runtime Python imports to get the information.
    """
    with ModuleInspect() as inspect:
        py_modules: list[StubSource] = []
        c_modules: list[StubSource] = []
        found = list(walk_packages(inspect, packages, verbose))
        modules = modules + found
        modules = [
            mod for mod in modules if not is_non_library_module(mod)
        ]  # We don't want to run any tests or scripts
        for mod in modules:
            try:
                result = find_module_path_and_all_py3(inspect, mod, verbose)
            except CantImport as e:
                tb = traceback.format_exc()
                if verbose:
                    sys.stdout.write(tb)
                if not quiet:
                    report_missing(mod, e.message, tb)
                continue
            if not result:
                c_modules.append(StubSource(mod))
            else:
                path, runtime_all = result
                py_modules.append(StubSource(mod, path, runtime_all))
        return py_modules, c_modules


def is_non_library_module(module: str) -> bool:
    """Does module look like a test module or a script?"""
    if module.endswith(
        (
            ".tests",
            ".test",
            ".testing",
            "_tests",
            "_test_suite",
            "test_util",
            "test_utils",
            "test_base",
            ".__main__",
            ".conftest",  # Used by pytest
            ".setup",  # Typically an install script
        )
    ):
        return True
    if module.split(".")[-1].startswith("test_"):
        return True
    if (
        ".tests." in module
        or ".test." in module
        or ".testing." in module
        or ".SelfTest." in module
    ):
        return True
    return False


def translate_module_name(module: str, relative: int) -> tuple[str, int]:
    for pkg in VENDOR_PACKAGES:
        for alt in "six.moves", "six":
            substr = f"{pkg}.{alt}"
            if module.endswith("." + substr) or (module == substr and relative):
                return alt, 0
            if "." + substr + "." in module:
                return alt + "." + module.partition("." + substr + ".")[2], 0
    return module, relative


def find_module_paths_using_search(
    modules: list[str], packages: list[str], search_path: list[str], pyversion: tuple[int, int]
) -> list[StubSource]:
    """Find sources for modules and packages requested.

    This function just looks for source files at the file system level.
    This is used if user passes --no-import, and will not find C modules.
    Exit if some of the modules or packages can't be found.
    """
    result: list[StubSource] = []
    typeshed_path = default_lib_path(mypy.build.default_data_dir(), pyversion, None)
    search_paths = SearchPaths((".",) + tuple(search_path), (), (), tuple(typeshed_path))
    cache = FindModuleCache(search_paths, fscache=None, options=None)
    for module in modules:
        m_result = cache.find_module(module)
        if isinstance(m_result, ModuleNotFoundReason):
            fail_missing(module, m_result)
            module_path = None
        else:
            module_path = m_result
        result.append(StubSource(module, module_path))
    for package in packages:
        p_result = cache.find_modules_recursive(package)
        if p_result:
            fail_missing(package, ModuleNotFoundReason.NOT_FOUND)
        sources = [StubSource(m.module, m.path) for m in p_result]
        result.extend(sources)

    result = [m for m in result if not is_non_library_module(m.module)]

    return result


def mypy_options(stubgen_options: Options) -> MypyOptions:
    """Generate mypy options using the flag passed by user."""
    options = MypyOptions()
    options.follow_imports = "skip"
    options.incremental = False
    options.ignore_errors = True
    options.semantic_analysis_only = True
    options.python_version = stubgen_options.pyversion
    options.show_traceback = True
    options.transform_source = remove_misplaced_type_comments
    options.preserve_asts = True
    options.include_docstrings = stubgen_options.include_docstrings

    # Override cache_dir if provided in the environment
    environ_cache_dir = os.getenv("MYPY_CACHE_DIR", "")
    if environ_cache_dir.strip():
        options.cache_dir = environ_cache_dir
    options.cache_dir = os.path.expanduser(options.cache_dir)

    return options


def parse_source_file(mod: StubSource, mypy_options: MypyOptions) -> None:
    """Parse a source file.

    On success, store AST in the corresponding attribute of the stub source.
    If there are syntax errors, print them and exit.
    """
    assert mod.path is not None, "Not found module was not skipped"
    with open(mod.path, "rb") as f:
        data = f.read()
    source = mypy.util.decode_python_encoding(data)
    errors = Errors(mypy_options)
    mod.ast = mypy.parse.parse(
        source, fnam=mod.path, module=mod.module, errors=errors, options=mypy_options
    )
    mod.ast._fullname = mod.module
    if errors.is_blockers():
        # Syntax error!
        for m in errors.new_messages():
            sys.stderr.write(f"{m}\n")
        sys.exit(1)


def generate_asts_for_modules(
    py_modules: list[StubSource], parse_only: bool, mypy_options: MypyOptions, verbose: bool
) -> None:
    """Use mypy to parse (and optionally analyze) source files."""
    if not py_modules:
        return  # Nothing to do here, but there may be C modules
    if verbose:
        print(f"Processing {len(py_modules)} files...")
    if parse_only:
        for mod in py_modules:
            parse_source_file(mod, mypy_options)
        return
    # Perform full semantic analysis of the source set.
    try:
        res = build([module.source for module in py_modules], mypy_options)
    except CompileError as e:
        raise SystemExit(f"Critical error during semantic analysis: {e}") from e

    for mod in py_modules:
        mod.ast = res.graph[mod.module].tree
        # Use statically inferred __all__ if there is no runtime one.
        if mod.runtime_all is None:
            mod.runtime_all = res.manager.semantic_analyzer.export_map[mod.module]


def generate_stub_for_py_module(
    mod: StubSource,
    target: str,
    *,
    parse_only: bool = False,
    inspect: bool = False,
    include_private: bool = False,
    export_less: bool = False,
    include_docstrings: bool = False,
    doc_dir: str = "",
    all_modules: list[str],
) -> None:
    """Use analysed (or just parsed) AST to generate type stub for single file.

    If directory for target doesn't exist it will created. Existing stub
    will be overwritten.
    """
    if inspect:
        ngen = InspectionStubGenerator(
            module_name=mod.module,
            known_modules=all_modules,
            _all_=mod.runtime_all,
            doc_dir=doc_dir,
            include_private=include_private,
            export_less=export_less,
            include_docstrings=include_docstrings,
        )
        ngen.generate_module()
        output = ngen.output()

    else:
        gen = ASTStubGenerator(
            mod.runtime_all,
            include_private=include_private,
            analyzed=not parse_only,
            export_less=export_less,
            include_docstrings=include_docstrings,
        )
        assert mod.ast is not None, "This function must be used only with analyzed modules"
        mod.ast.accept(gen)
        output = gen.output()

    # Write output to file.
    subdir = os.path.dirname(target)
    if subdir and not os.path.isdir(subdir):
        os.makedirs(subdir)
    with open(target, "w", encoding="utf-8") as file:
        file.write(output)


def generate_stubs(options: Options) -> None:
    """Main entry point for the program."""
    mypy_opts = mypy_options(options)
    py_modules, pyc_modules, c_modules = collect_build_targets(options, mypy_opts)
    all_modules = py_modules + pyc_modules + c_modules
    all_module_names = sorted(m.module for m in all_modules)
    # Use parsed sources to generate stubs for Python modules.
    generate_asts_for_modules(py_modules, options.parse_only, mypy_opts, options.verbose)
    files = []
    for mod in py_modules + pyc_modules:
        assert mod.path is not None, "Not found module was not skipped"
        target = mod.module.replace(".", "/")
        if os.path.basename(mod.path) in ["__init__.py", "__init__.pyc"]:
            target += "/__init__.pyi"
        else:
            target += ".pyi"
        target = os.path.join(options.output_dir, target)
        files.append(target)
        with generate_guarded(mod.module, target, options.ignore_errors, options.verbose):
            generate_stub_for_py_module(
                mod,
                target,
                parse_only=options.parse_only,
                inspect=options.inspect or mod in pyc_modules,
                include_private=options.include_private,
                export_less=options.export_less,
                include_docstrings=options.include_docstrings,
                doc_dir=options.doc_dir,
                all_modules=all_module_names,
            )

    # Separately analyse C modules using different logic.
    for mod in c_modules:
        if any(py_mod.module.startswith(mod.module + ".") for py_mod in all_modules):
            target = mod.module.replace(".", "/") + "/__init__.pyi"
        else:
            target = mod.module.replace(".", "/") + ".pyi"
        target = os.path.join(options.output_dir, target)
        files.append(target)
        with generate_guarded(mod.module, target, options.ignore_errors, options.verbose):
            generate_stub_for_c_module(
                mod.module,
                target,
                known_modules=all_module_names,
                doc_dir=options.doc_dir,
                include_private=options.include_private,
                export_less=options.export_less,
                include_docstrings=options.include_docstrings,
            )
    num_modules = len(all_modules)
    if not options.quiet and num_modules > 0:
        print("Processed %d modules" % num_modules)
        if len(files) == 1:
            print(f"Generated {files[0]}")
        else:
            print(f"Generated files under {common_dir_prefix(files)}" + os.sep)


HEADER = """%(prog)s [-h] [more options, see -h]
                     [-m MODULE] [-p PACKAGE] [files ...]"""

DESCRIPTION = """
Generate draft stubs for modules.

Stubs are generated in directory ./out, to avoid overriding files with
manual changes.  This directory is assumed to exist.
"""


def parse_options(args: list[str]) -> Options:
    parser = argparse.ArgumentParser(prog="stubgen", usage=HEADER, description=DESCRIPTION)

    parser.add_argument(
        "--ignore-errors",
        action="store_true",
        help="ignore errors when trying to generate stubs for modules",
    )
    parser.add_argument(
        "--no-import",
        action="store_true",
        help="don't import the modules, just parse and analyze them "
        "(doesn't work with C extension modules and might not "
        "respect __all__)",
    )
    parser.add_argument(
        "--no-analysis",
        "--parse-only",
        dest="parse_only",
        action="store_true",
        help="don't perform semantic analysis of sources, just parse them "
        "(only applies to Python modules, might affect quality of stubs. "
        "Not compatible with --inspect)",
    )
    parser.add_argument(
        "--inspect-mode",
        dest="inspect",
        action="store_true",
        help="import and inspect modules instead of parsing source code."
        "This is the default behavior for c modules and pyc-only packages, but "
        "it is also useful for pure python modules with dynamically generated members.",
    )
    parser.add_argument(
        "--include-private",
        action="store_true",
        help="generate stubs for objects and members considered private "
        "(single leading underscore and no trailing underscores)",
    )
    parser.add_argument(
        "--export-less",
        action="store_true",
        help="don't implicitly export all names imported from other modules in the same package",
    )
    parser.add_argument(
        "--include-docstrings",
        action="store_true",
        help="include existing docstrings with the stubs",
    )
    parser.add_argument("-v", "--verbose", action="store_true", help="show more verbose messages")
    parser.add_argument("-q", "--quiet", action="store_true", help="show fewer messages")
    parser.add_argument(
        "--doc-dir",
        metavar="PATH",
        default="",
        help="use .rst documentation in PATH (this may result in "
        "better stubs in some cases; consider setting this to "
        "DIR/Python-X.Y.Z/Doc/library)",
    )
    parser.add_argument(
        "--search-path",
        metavar="PATH",
        default="",
        help="specify module search directories, separated by ':' "
        "(currently only used if --no-import is given)",
    )
    parser.add_argument(
        "-o",
        "--output",
        metavar="PATH",
        dest="output_dir",
        default="out",
        help="change the output directory [default: %(default)s]",
    )
    parser.add_argument(
        "-m",
        "--module",
        action="append",
        metavar="MODULE",
        dest="modules",
        default=[],
        help="generate stub for module; can repeat for more modules",
    )
    parser.add_argument(
        "-p",
        "--package",
        action="append",
        metavar="PACKAGE",
        dest="packages",
        default=[],
        help="generate stubs for package recursively; can be repeated",
    )
    parser.add_argument(
        metavar="files",
        nargs="*",
        dest="files",
        help="generate stubs for given files or directories",
    )

    ns = parser.parse_args(args)

    pyversion = sys.version_info[:2]
    ns.interpreter = sys.executable

    if ns.modules + ns.packages and ns.files:
        parser.error("May only specify one of: modules/packages or files.")
    if ns.quiet and ns.verbose:
        parser.error("Cannot specify both quiet and verbose messages")
    if ns.inspect and ns.parse_only:
        parser.error("Cannot specify both --parse-only/--no-analysis and --inspect-mode")

    # Create the output folder if it doesn't already exist.
    os.makedirs(ns.output_dir, exist_ok=True)

    return Options(
        pyversion=pyversion,
        no_import=ns.no_import,
        inspect=ns.inspect,
        doc_dir=ns.doc_dir,
        search_path=ns.search_path.split(":"),
        interpreter=ns.interpreter,
        ignore_errors=ns.ignore_errors,
        parse_only=ns.parse_only,
        include_private=ns.include_private,
        output_dir=ns.output_dir,
        modules=ns.modules,
        packages=ns.packages,
        files=ns.files,
        verbose=ns.verbose,
        quiet=ns.quiet,
        export_less=ns.export_less,
        include_docstrings=ns.include_docstrings,
    )


def main(args: list[str] | None = None) -> None:
    mypy.util.check_python_version("stubgen")
    # Make sure that the current directory is in sys.path so that
    # stubgen can be run on packages in the current directory.
    if not ("" in sys.path or "." in sys.path):
        sys.path.insert(0, "")

    options = parse_options(sys.argv[1:] if args is None else args)
    generate_stubs(options)


if __name__ == "__main__":
    main()