# Copyright (c) Meta Platforms, Inc. and affiliates.

schema python.4 {
import builtin.1
import src

predicate Name: string
predicate Type: string

# Records that a class exists with the given fully qualified name.
predicate ClassDeclaration:
  {
    name: Name,
    bases: maybe [Name],  # unused, see ClassDefinition below
  }
# Records that a function exists with the given fully qualified name.
# The function can be a global, local, or a class method.
predicate FunctionDeclaration: { name: Name }
# Records that a variable exists with the given fully qualified name.
# This variable can be global, or scoped to a class.
predicate VariableDeclaration: { name: Name }
# Records that a Python module exists with a given fully qualified name.
predicate Module: { name: Name }

# A structured name.
predicate SName:
  {
    local_name: Name,
    parent: maybe SName,
  }

# Unstructured dotted qualified names to structured names
predicate NameToSName: Name -> SName

predicate SNameToName: SName -> Name
  stored SN -> N where NameToSName N -> SN

# Allows efficient queries for modules by structured name.
predicate ModuleBySName: SName -> Module
  stored SN -> M where Module {name = N} = M; NameToSName N -> SN

predicate ModuleDefinition:
  {
    module: Module,
  }

# Allows efficient queries for classes by structured name
predicate ClassBySName: SName -> ClassDeclaration
  stored SN -> C where ClassDeclaration {name = N} = C; NameToSName N -> SN

# Represents details about a class with a particular name.
predicate ClassDefinition:
  {
    declaration: ClassDeclaration,
    # nothing means the indexer doesn't support detecting these features
    bases: maybe [ClassDeclaration],
    keywords: maybe [Parameter],  # metaclass parameters
    decorators: maybe [Decorator],
    container: maybe DeclarationContainer,
  }

predicate DerivedClassToBase:
  {
    derived: ClassDeclaration,
    base: ClassDeclaration,
  }
  {Derived, Base} where
    ClassDefinition { declaration = Derived, bases = { just = Bases } };
    Bases[..] = Base;

predicate BaseClassToDerived:
  {
    base: ClassDeclaration,
    derived: ClassDeclaration,
  }
  stored {Base, Derived} where
    DerivedClassToBase { Derived, Base};

# Allows efficient queries for functions by structured name.
predicate FunctionBySName: SName -> FunctionDeclaration
  stored SN -> F where FunctionDeclaration {name = N} = F; NameToSName N -> SN

# Represents details about a function with a particular name.
predicate FunctionDefinition:
  {
    declaration: FunctionDeclaration,
    is_async: bool,
    returnsInfo: maybe TypeInfo,
    params: [Parameter],  # "regular" parameters (can be pos or kwarg)
    # nothing means the indexer doesn't support detecting these features
    posonly_params: maybe [Parameter],
    kwonly_params: maybe [Parameter],
    star_arg: maybe Parameter,  # *args
    star_kwarg: maybe Parameter,  # **kwargs
    decorators: maybe [Decorator],
    container: maybe DeclarationContainer,
  }

# Allows efficient queries for variables by structured name.
predicate VariableBySName: SName -> VariableDeclaration
  stored SN -> V where VariableDeclaration {name = N} = V; NameToSName N -> SN;

# Represents details about a variable.
predicate VariableDefinition:
  {
    declaration: VariableDeclaration,
    typeInfo: maybe TypeInfo,
    container: maybe DeclarationContainer,
  }

type DeclarationContainer =
  {
    module: Module |
    cls: ClassDeclaration |
    func: FunctionDeclaration
  }

type Parameter =
  {
    name: Name,
    typeInfo: maybe TypeInfo,
    # value is filled out for:
    # - metaclass parameters (see the `keywords` field in `ClassDefinition`)
    # - default values of function parameters (see `FunctionDefinition`)
    value: maybe string,
  }

type TypeInfo =
  {
    displayType: Type,
    xrefs: [XRefViaName],
  }

# Decorators can be arbitrary expressions, this just records their string
# representation.
type Decorator = string

predicate DeclarationDocstring:
  {
    declaration: Declaration,
    location: src.ByteSpan, # raw docstring location
    pretty_text: string, # pretty printed docstring
  }

# A concrete symbol being imported.
# A single import statement that pulls in multiple names generates multiple
# facts of this predicate. Star imports are not represented.
predicate ImportStatement:
  {
    # fully qualified name of the imported symbol
    from_name: Name,
    # fully qualified name that is the effect of the import statement
    as_name: Name,
  }

type Declaration =
  {
    cls: ClassDeclaration |
    func: FunctionDeclaration |
    variable: VariableDeclaration |
    imp: ImportStatement |
    module: Module |
  }

# The location of a Declaration relative to the repo root.
predicate DeclarationLocation:
  {
    declaration: Declaration,
    file: src.File,
    span: src.ByteSpan,
  }

# A cross reference, or access to a symbol.
# This type captures a variable access with the LOAD expression
# context in the Python AST. This type is only valid in the context
# of a FileXRefs predicate. `target` is a fully qualified name.
type XRefViaName =
    {
        target: Name,
        source: src.ByteSpan,
    }

# Collects all reference to names in a single file.
# There is only one fact of this predicate per source file in the repo.
predicate XRefsViaNameByFile:
    {
        file: src.File,
        xrefs: [XRefViaName],
    }

# Uses of a reference via name in a particular file.
predicate XRefsViaName:
    {
      xref: Name,
      file: src.File,
      span: src.ByteSpan,
    }

# Uses of a reference via name in a particular file.
predicate XRefsViaNameByTarget:
    {
        target: Name,
        file: src.File,
        spans: [src.ByteSpan],
    }

# All uses of a declaration in a particular file.
# This predicate does not follow references, so if a symbol is used through
# a chain of imports, only the first hop will be present as a fact.
# Querying this predicate by declaration is an efficient way to find immediate
# references to
predicate DeclarationUses:
  {
    declaration: Declaration,
    file: src.File,
    span: src.ByteSpan,
  }
  {Decl, File, Span} where
  DeclarationToName Decl -> Name;
  XRefsViaNameByTarget {Name, File, Spans};
  Span = Spans[..];


predicate DirectXRefsByFile:
  {
    file: src.File,
    xref: DirectXRef,
  }
  {File, XRef} where
  XRefsViaNameByFile { File, XRefsViaName };
  { target = Name, source = Source } = XRefsViaName[..];
  DeclarationWithName {Name, Decl};
  XRef = DirectXRef {target = Decl, source = Source};

type DirectXRef =
  {
    target: Declaration,
    source: src.ByteSpan,
  }

# String literals that occur in expression context, rather than as the
# definition of a top-level or class constant.  These must be escaped
# if they are not valid UTF-8.
predicate StringLiteral : string

# Context-free information about an expression argument
type Argument =
  {
    # the indexer may choose to include only a prefix of the string literal
    lit: StringLiteral |
    # xrefs: [XRefViaName]  # FUTURE WORK
  }

# An argument to a particular call.
type CallArgument =
  {
    label: maybe Name,
    span: src.ByteSpan,
    argument: maybe Argument,
  }

# Information for all calls, organized by file and callee_span
predicate FileCall :
  {
    file: src.File,
    callee_span: src.ByteSpan,
    call_args: [CallArgument],
  }

# Callee function to caller function
predicate CalleeToCaller :
  {
    callee: Name,
    caller: Name,
  }

predicate DeclarationToName: Declaration -> Name
  D -> N where
    ({cls = { name = N }} = D) |
    ({func = { name = N }} = D) |
    ({variable = { name = N }} = D) |
    ({imp = { as_name = N }} = D) |
    ({module = { name = N }} = D)


# This is a variant of DeclarationLocation. It allows for efficient queries
# by file.
predicate DeclarationsByFile:
  {
    file: src.File,
    span: src.ByteSpan,
    declaration: Declaration,
  }
  stored {File, Span, Declaration} where
  DeclarationLocation { Declaration, File, Span }

# Search for a declaration by (fully qualified) name.
predicate DeclarationWithName:
  {
    name: Name,
    declaration: Declaration,
  }
  {N, D} where
  D = (
    Declaration { cls = { name = N }}
  ) | (
    Declaration { func = { name = N }}
  ) | (
    Declaration { variable = { name = N }}
  ) | (
    ImportStatementByAsName { name = N, import_ = I };
    Declaration { imp = I }
  ) | (
    Declaration { module = { name = N }}
  )

# Used to filter out imp decls when looking for definition occurences
predicate NonImportDeclaration: Declaration
  D where
  { cls = _ } |
  { func = _ } |
  { variable = _ } |
  { module = _ } = D


# This is the inverse of ImportStatement. It allows for efficient queries
# by alias. Note that multiple ImportStatements might have the same
# alias, so this must be a record and not Name -> ImportStatement.
predicate ImportStatementByAsName:
  {
    name: Name,
    import_: ImportStatement
  } stored { Name, I } where
  ImportStatement { as_name = Name } = I

# Same as ImportStatementByAsName, but for structured names.
predicate ImportStatementByAsSName:
  {
     sname: SName,
     import_: ImportStatement
  }
  { AsSName, I } where
  SNameToName AsSName -> AsName;
  ImportStatementByAsName { AsName, I }

# Look up declarations with exact SNames
predicate DeclarationWithSName:
  {
    sname: SName,
    declaration: Declaration,
  }
  { SName, Decl } where
    SNameToName SName -> Name;
    DeclarationWithName { Name, Decl };

# Look up SNames using Declarations
predicate SNameWithDeclaration:
  {
    declaration: Declaration,
    sname: SName,
  }
  { Decl, SName } where
    python.DeclarationToName Decl -> Name;
    python.NameToSName Name -> SName

# map from a declaration to the closest top level declaration
# useful as we operate a lot of analysis on the top level declarations
predicate ContainingTopLevelDeclaration:
  {
    declaration: Declaration,
    container: Declaration,
  }

# Reverse containment mapping
predicate ContainedByTopLevelDeclaration:
  {
    container: Declaration,
    declaration: Declaration,
  }
  stored { container = C, declaration = D} where
  python.ContainingTopLevelDeclaration {
    declaration = D,
    container = C
  }

# Quickly find declarations defined at the module level
# The dead code automation operates at this level
predicate IsTopLevelDeclaration: Declaration
  D where
    ContainingTopLevelDeclaration {D, C};
    {module = _} = C;

# Find which  declaration references declaration
predicate DeclarationReference:
  {
    target : Declaration,
    source : Declaration
  }
  { target = T, source = S } where
    python.DeclarationUses {declaration=T, file=F, span=LittleSpan};
    DeclarationsByFile {declaration=S, file=F, span=BigSpan};
    src.ByteSpanContains {byteSpan=BigSpan, contains=LittleSpan}

predicate DeclarationWithLocalName:
  {
    local_name: Name,
    declaration: Declaration,
  }
  {LN, D} where
  SN = SName {local_name = LN};
  DeclarationWithSName {SN, D};

type Definition =
  {
    cls: ClassDefinition |
    func: FunctionDefinition |
    variable: VariableDefinition |
    module: ModuleDefinition |
  }

# The location of a Definition relative to the repo root.
# The span here includes the body and the decorators (if present)
predicate DefinitionLocation:
  {
    definition: Definition,
    file: src.File,
    span: src.ByteSpan,
  }

# This is a variant of DefinitionLocation. It allows for efficient queries
# by file.
predicate DefinitionsByFile:
  {
    file: src.File,
    span: src.ByteSpan,
    definition: Definition,
  }
  stored {File, Span, Definition} where
  DefinitionLocation { Definition, File, Span }

# Map from a Definition to the corresponding Declaration
predicate DefinitionDeclaration:
  {
    definition: Definition,
    declaration: Declaration,
  }
  {Def, Decl} where
  ({ cls = { declaration = CD } } = Def; Decl = python.Declaration { cls = CD }) |
  ({ func = { declaration = FD } } = Def; Decl = python.Declaration { func = FD }) |
  ({ module = { module = MD } } = Def; Decl = python.Declaration { module = MD }) |
  ({ variable = { declaration = VD } } = Def; Decl = python.Declaration { variable = VD });

# Inverse of DefinitionDeclaration, maps the Declaration to a corresponding Definition
predicate DeclarationDefinition:
  {
    declaration: Declaration,
    definition: Definition,
  }
  stored { Decl, Def } where
  python.DefinitionDeclaration { Def, Decl };

# Quickly find definitions defined at the module level
# The dead code automation operates at this level
predicate IsTopLevelDefinition: Definition
  D where
    python.DefinitionDeclaration {D, Decl};
    python.IsTopLevelDeclaration Decl;

predicate ImportStarStatement:
  {
    from_name: Name,
    into_module: Module,
  }

predicate ImportStarLocation:
  {
    import_star: ImportStarStatement,
    file: src.File,
    span: src.ByteSpan,
  }

# This is the variant of ImportStarLocation which allows us for querying by file.
predicate ImportStarsByFile:
  {
    file: src.File,
    span: src.ByteSpan,
    declaration: ImportStarStatement,
  }
  stored {File, Span, ImportStarStatement} where
  ImportStarLocation { ImportStarStatement, File, Span };

#
# Even more efficient searching, names and scopes
# We have to do a bit of work to get dotted names in to searchable prefix form
#
# This duplicates some of the work in ClassBySName since we can't rely on
# constructing SNames in search being cheap
#
predicate SearchClassByName:
  {
    name: string,
    parent: maybe SName,
    decl : ClassDeclaration
  } stored { NameStr, Parent, Decl } where
    ClassDeclaration { name = N } = Decl;
    NameToSName N -> { Name NameStr, Parent }

predicate SearchClassByLowerCaseName:
  {
    name_lowercase: string,
    name: string
  } stored { prim.toLower NameStr, NameStr } where
    ClassDeclaration { name = N };
    NameToSName N -> { local_name = Name NameStr }

predicate SearchModuleByName:
  {
    name: string,
    parent: maybe SName,
    decl: Module
  } stored  { NameStr, Parent, Decl } where
    Module { name = N } = Decl;
    NameToSName N -> { Name NameStr, Parent }

predicate SearchModuleByLowerCaseName:
  {
    name_lowercase: string,
    name: string
  } stored { prim.toLower NameStr, NameStr } where
    Module { name = N };
    NameToSName N -> { local_name = Name NameStr }

# free or local functions are those functions not contained by a class
predicate SearchFunctionByName:
  {
    name: string,
    parent: maybe SName,
    decl : FunctionDeclaration
  } stored { NameStr, Parent, Decl } where
    FunctionDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { func = Decl }, Container };
    ( { module = _ } | { func = _ } ) = Container; # check container for kind "function"
    NameToSName N -> { Name NameStr, Parent }

predicate SearchFunctionByLowerCaseName:
  {
    name_lowercase: string,
    name: string
  } stored { prim.toLower NameStr, NameStr } where
    FunctionDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { func = Decl }, Container };
    ( { module = _ } | { func = _ } ) = Container;
    NameToSName N -> { local_name = Name NameStr }

# class-contained function declarations are "methods"
predicate SearchMethodByName:
  {
    name: string,
    parent: maybe SName,
    decl : FunctionDeclaration
  } stored { NameStr, Parent, Decl } where
    FunctionDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { func = Decl }, { cls = _ } };
    NameToSName N -> { Name NameStr, Parent }

predicate SearchMethodByLowerCaseName:
  {
    name_lowercase: string,
    name: string
  } stored { prim.toLower NameStr, NameStr } where
    FunctionDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { func = Decl }, { cls = _ } };
    NameToSName N -> { local_name = Name NameStr }

# similar to functions, variables can be distinguished by kind using the parent
predicate SearchFieldByName:
  {
    name: string,
    parent: maybe SName,
    decl: VariableDeclaration
  } stored { NameStr, Parent, Decl } where
    VariableDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { variable = Decl }, { cls = _ } };
    NameToSName N -> { Name NameStr, Parent }

predicate SearchFieldByLowerCaseName:
  {
    name_lowercase: string,
    name: string
  } stored { prim.toLower NameStr, NameStr } where
    VariableDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { variable = Decl }, { cls = _ } };
    NameToSName N -> { local_name = Name NameStr }

# similar to functions, variables can be distinguished by kind using the parent
predicate SearchVariableByName:
  {
    name: string,
    parent: maybe SName,
    decl: VariableDeclaration
  } stored { NameStr, Parent, Decl } where
    VariableDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { variable = Decl }, Container };
    { module = _ } = Container; # exclude local variables, whose parent is a function, from search
    NameToSName N -> { Name NameStr, Parent }

predicate SearchVariableByLowerCaseName:
  {
    name_lowercase: string,
    name: string
  } stored { prim.toLower NameStr, NameStr } where
    VariableDeclaration { name = N } = Decl;
    ContainingTopLevelDeclaration { { variable = Decl }, { module = _ } };
    NameToSName N -> { local_name = Name NameStr }

# Mapping between declarations and their **immediate** containers.
# - a module is the container for everything declared at module level and submodules
# - a class is the container for its methods, variables and inner classes
# - a function is the container for variables, functions and classes
  predicate ContainedBy:
    {
      containee: Declaration,
      container: Declaration,
    }
    {ContaineeDecl, ContainerDecl} where
      (
        # we don't have definitions for empty modules in the module chain,
        # but we can define relations between them using names
        { module = _ } = ContaineeDecl;
        python.SNameWithDeclaration { ContaineeDecl, { parent = { just = SName } } };
        python.DeclarationWithSName { SName, ContainerDecl };
        { module = _ } = ContainerDecl;
      ) | (
        (
          { cls = ClassDecl } = ContaineeDecl;
          python.ClassDefinition { declaration = ClassDecl, container = { just = Container } };
        ) | (
          { func = FuncDecl } = ContaineeDecl;
          python.FunctionDefinition { declaration = FuncDecl, container = { just = Container } };
        ) | (
          { variable = VarDecl } = ContaineeDecl;
          python.VariableDefinition { declaration = VarDecl, container = { just = Container } };
        );
        Container = Container; # hack to make this variable available inside or patterns below
        (
          { module = ModuleDecl } = Container;
          { module = ModuleDecl } = ContainerDecl;
        ) | (
          { cls = ClassDecl } = Container ;
          { cls = ClassDecl } = ContainerDecl;
        ) | (
          { func = FuncDecl } = Container;
          { func = FuncDecl } = ContainerDecl;
        );
      );

# Reverse mapping of ContainedBy
  predicate Contains:
    {
      container: Declaration,
      containee: Declaration,
    }
    stored {ContainerDecl, ContaineeDecl} where
      ContainedBy { ContaineeDecl, ContainerDecl}


predicate IsAbstract: Declaration
  Decl where
  (
    { cls = ClassDecl } = Decl;
    # A class is abstract if it was based on "abc.ABC"
    DerivedClassToBase { ClassDecl, Base };
    { name = "abc.ABC" } = Base;
    # ABCMeta is not supported, because doesn't have this data
    # (perf note): find the base classes first and then check to see
    # whether the name is "abc.ABC", don't find all the "abc.ABC"
    # classes first.
  ) | (
    { func = FuncDecl } = Decl;
    python.FunctionDefinition { declaration = FuncDecl, decorators = { just = Decorators } };
    # decorators are plain text, so we have to guess how they were imported
    Decorators[..] = "@abc.abstractmethod" | "@abstractmethod";
  )

# manually traverse 10 layers of inheritance
predicate MethodOverrides :
  {
    derived: FunctionDeclaration,
    base: FunctionDeclaration,
  }
  { DerivedMethodDecl, BaseMethodDecl } where
    # find class where method is defined
    ContainedBy { { func = DerivedMethodDecl }, { cls = DerivedClassDecl } };
    # find local name of method {module_name}.{class_name}.{method_local_name}
    SNameWithDeclaration { { func = DerivedMethodDecl}, { local_name = python.Name MethodNameStr } };

    DerivedClassToBase { DerivedClassDecl, BaseClassDeclL1 };
    MaybeBaseMethodDecl = if (
      MethodByLocalNameStr { BaseClassDeclL1, MethodNameStr, BaseMethodDeclL1 };
    ) then (
      { just = BaseMethodDeclL1 }
    ) else (
      DerivedClassToBase { BaseClassDeclL1, BaseClassDeclL2 };
      if (
        MethodByLocalNameStr { BaseClassDeclL2, MethodNameStr, BaseMethodDeclL2 };
      ) then (
        { just = BaseMethodDeclL2 }
      ) else (
        DerivedClassToBase { BaseClassDeclL2, BaseClassDeclL3 };
        if (
          MethodByLocalNameStr { BaseClassDeclL3, MethodNameStr, BaseMethodDeclL3 };
        ) then (
          { just = BaseMethodDeclL3 }
        ) else (
          DerivedClassToBase { BaseClassDeclL3, BaseClassDeclL4 };
          if (
            MethodByLocalNameStr { BaseClassDeclL4, MethodNameStr, BaseMethodDeclL4 };
          ) then (
            { just = BaseMethodDeclL4 }
          ) else (
            DerivedClassToBase { BaseClassDeclL4, BaseClassDeclL5 };
            if (
              MethodByLocalNameStr { BaseClassDeclL5, MethodNameStr, BaseMethodDeclL5 };
            ) then (
              { just = BaseMethodDeclL5 }
            ) else (
              DerivedClassToBase { BaseClassDeclL5, BaseClassDeclL6 };
              if (
                MethodByLocalNameStr { BaseClassDeclL6, MethodNameStr, BaseMethodDeclL6 };
              ) then (
                { just = BaseMethodDeclL6 }
              ) else (
                DerivedClassToBase { BaseClassDeclL6, BaseClassDeclL7 };
                if (
                  MethodByLocalNameStr { BaseClassDeclL7, MethodNameStr, BaseMethodDeclL7 };
                ) then (
                  { just = BaseMethodDeclL7 }
                ) else (
                  DerivedClassToBase { BaseClassDeclL7, BaseClassDeclL8 };
                  if (
                    MethodByLocalNameStr { BaseClassDeclL8, MethodNameStr, BaseMethodDeclL8 };
                  ) then (
                    { just = BaseMethodDeclL8 }
                  ) else (
                    DerivedClassToBase { BaseClassDeclL8, BaseClassDeclL9 };
                    if (
                      MethodByLocalNameStr { BaseClassDeclL9, MethodNameStr, BaseMethodDeclL9 };
                    ) then (
                      { just = BaseMethodDeclL9 }
                    ) else (
                      DerivedClassToBase { BaseClassDeclL9, BaseClassDeclL10 };
                      if (
                        MethodByLocalNameStr { BaseClassDeclL10, MethodNameStr, BaseMethodDeclL10 };
                      ) then (
                        { just = BaseMethodDeclL10 }
                      ) else (
                        { nothing = {} }
                      )
                    )
                  )
                )
              )
            )
          )
        )
      )
    );
    MaybeBaseMethodDecl = { just = BaseMethodDecl };

# manually traverse 10 layers of inheritance
predicate MethodOverriden:
  {
    base: FunctionDeclaration,
    derived: FunctionDeclaration,
  }
  { BaseMethodDecl, DerivedMethodDecl } where
    # find class where method is defined
    ContainedBy { { func = BaseMethodDecl }, { cls = BaseClassDecl } };
    # find local name of method {module_name}.{class_name}.{method_local_name}
    SNameWithDeclaration { { func = BaseMethodDecl}, { local_name = LocalName } };
    LocalName = python.Name MethodNameStr;

    BaseClassToDerived { BaseClassDecl, DerivedClassDeclL1 };
    MaybeDerivedMethodDecl = if (
      MethodByLocalNameStr { DerivedClassDeclL1, MethodNameStr, DerivedMethodDeclL1 };
    ) then (
      { just = DerivedMethodDeclL1 }
    ) else (
      BaseClassToDerived { DerivedClassDeclL1, DerivedClassDeclL2 };
      if (
        MethodByLocalNameStr { DerivedClassDeclL2, MethodNameStr, DerivedMethodDeclL2 };
      ) then (
        { just = DerivedMethodDeclL2 }
      ) else (
        BaseClassToDerived { DerivedClassDeclL2, DerivedClassDeclL3 };
        if (
          MethodByLocalNameStr { DerivedClassDeclL3, MethodNameStr, DerivedMethodDeclL3 };
        ) then (
          { just = DerivedMethodDeclL3 }
        ) else (
          BaseClassToDerived { DerivedClassDeclL3, DerivedClassDeclL4 };
          if (
            MethodByLocalNameStr { DerivedClassDeclL4, MethodNameStr, DerivedMethodDeclL4 };
          ) then (
            { just = DerivedMethodDeclL4 }
          ) else (
            BaseClassToDerived { DerivedClassDeclL4, DerivedClassDeclL5 };
            if (
              MethodByLocalNameStr { DerivedClassDeclL5, MethodNameStr, DerivedMethodDeclL5 };
            ) then (
              { just = DerivedMethodDeclL5 }
            ) else (
              BaseClassToDerived { DerivedClassDeclL5, DerivedClassDeclL6 };
              if (
                MethodByLocalNameStr { DerivedClassDeclL6, MethodNameStr, DerivedMethodDeclL6 };
              ) then (
                { just = DerivedMethodDeclL6 }
              ) else (
                BaseClassToDerived { DerivedClassDeclL6, DerivedClassDeclL7 };
                if (
                  MethodByLocalNameStr { DerivedClassDeclL7, MethodNameStr, DerivedMethodDeclL7 };
                ) then (
                  { just = DerivedMethodDeclL7 }
                ) else (
                  BaseClassToDerived { DerivedClassDeclL7, DerivedClassDeclL8 };
                  if (
                    MethodByLocalNameStr { DerivedClassDeclL8, MethodNameStr, DerivedMethodDeclL8 };
                  ) then (
                    { just = DerivedMethodDeclL8 }
                  ) else (
                    BaseClassToDerived { DerivedClassDeclL8, DerivedClassDeclL9 };
                    if (
                      MethodByLocalNameStr { DerivedClassDeclL9, MethodNameStr, DerivedMethodDeclL9 };
                    ) then (
                      { just = DerivedMethodDeclL9 }
                    ) else (
                      BaseClassToDerived { DerivedClassDeclL9, DerivedClassDeclL10 };
                      if (
                        MethodByLocalNameStr { DerivedClassDeclL10, MethodNameStr, DerivedMethodDeclL10 };
                      ) then (
                        { just = DerivedMethodDeclL10 }
                      ) else (
                        { nothing = {} }
                      )
                    )
                  )
                )
              )
            )
          )
        )
      )
    );
    MaybeDerivedMethodDecl = { just = DerivedMethodDecl };

# (internal) helper for MethodOverrides
predicate MethodByLocalNameStr:
  {
    cls: ClassDeclaration,
    method_local_name: string,
    method: FunctionDeclaration,
  }
  { ClassDecl, NameStr, MethodDecl } where
    Contains { { cls = ClassDecl }, { func = MethodDecl } };
    SearchMethodByName { name = NameStr, parent = _, decl = MethodDecl }; # we specifically don't know the parent yet

# Let's imagine:
# module A has function Foo
# module B imports Foo from A
# module C imports Foo from B
#
# Q: How to find out what Foo is?
# A: Resolve its original name and Find it by its original name
#
# This is the "Resolve" part of the job
#
# manually traverse 5 layers of imports
predicate ResolveOriginalName:
  {
    name: Name,
    original_name: Name,
  }
  { Name, OriginalName } where
    OriginalName = if (
      ImportStatementByAsName{ Name, { from_name = Name1 } };
    ) then (
      if (
        ImportStatementByAsName{ Name1, { from_name = Name2 } };
      ) then (
        if (
          ImportStatementByAsName{ Name2, { from_name = Name3 } };
        ) then (
          if (
            ImportStatementByAsName{ Name3, { from_name = Name4 } };
          ) then (
            if (
              ImportStatementByAsName{ Name4, { from_name = Name5 } };
            ) then (
              Name5 # returns name 5 even if there are other imports
            ) else ( Name4 )
          ) else ( Name3 )
        ) else ( Name2 )
      ) else ( Name1 )
    ) else ( Name );

} # python.4