#pragma once // receiverevidence.h — FE-B (test/receiverevidencecheck.sh): what proves a call's RECEIVER, and what does not. // // A member call `x.m()` (or, where the receiver is implicit, a bare `m()`) used to bind to every in-repo definition // spelled `m` that the name ladder reached, and the answer showed each such row as a plain edge — a confident claim // with nothing behind it but the name. This header holds the two halves of the fix: // // 1. ReceiverEvidence::narrow — a RESOLVE rule for receivers the source types: `this`/`self`/`cls` inside a class (and // the language's base-class receiver, isSuperRoot, through the bases only), a parameter or local whose class is // written (a TS/Python/Go annotation, a Go method receiver, a JS `new Foo()` / Python `Foo()` / Go `Foo{}` initializer), a constructed receiver // (`new Foo().m()`), a class-name receiver (`Foo.m()`), and a chain of fields whose classes are stated // (`this.bucket = new Schemas()`, Python `self.x = Foo()`, a Go struct field, a Go EMBEDDED field whose methods // are promoted). A hit is the call's whole answer, exactly like Rule 2. Ruby's own method lookup (mixins, typed and // class receivers) is deliberately NOT modelled here: Ruby keeps only the language-neutral proof below. // 2. ReceiverEvidence::ladderProves — for a call the rules above did not answer, which name-ladder candidates the // language's own lookup can PROVE: an implicit receiver's own class and its bases, a free function in scope, a // definition in the module a receiver alias names. A call left with no proven candidate is NAME-ONLY: its rows // are kept, marked via="name" on every surface (graph.h Graph::outNameOnly), never dropped and never proven. // // What it does NOT do: infer a function's return type (`s = self.get_screen(); s.refresh()`), follow a property, or type // a value that crossed a call boundary. Those receivers stay name-only — the honest answer, not a guess. #include "externalnames.h" // kRustStdReceiverTypes / kRustStdDerefTypes / kRustPreludeTypes (lane std-namesake) #include "infra/hashutil.h" // packPair: the chain tables' ( file, byte ) keys #include "infra/idkeyedmap.h" // IdKeyedCsr: localType's packed ( scope, name ) → facts table (K1a LOCALTYPE-PACK) #include "infra/sortutil.h" // svLess: the explicit byte order the operatorResult sort takes (portablebuildcheck #6) #include "langfacts.h" // langFacts(l).overloadsWithoutArity — overloadedAbove's language column #include "model.h" #include "resolve.h" // includerDir; HashMap / SmallVec through it; extent::inSet (extentsuspect.h) through it #include "smallvec.h" #include #include #include #include #include #include #include #include #include namespace rw { // The languages whose name-ladder rows the hedge covers. Every other language keeps its ladder unchanged (a disclosed // floor in test/receiverevidencecheck.sh: Objective-C, PHP, Lua, Zig, Dart, Elixir, Scala, Bash and the rest). inline bool receiverHedgeLang( Lang l ) noexcept { switch( l ) { case Lang::JavaScript: case Lang::TypeScript: case Lang::Python: case Lang::Go: case Lang::Rust: case Lang::C: case Lang::Cpp: case Lang::Java: case Lang::Kotlin: case Lang::CSharp: case Lang::Swift: case Lang::Ruby: return true; default: return false; } } // FE-B: each Go file's package import paths, built by graph.h collectGoModules — the nearest go.mod's module path plus the // directory below it, and the path a LOCAL `replace L => ./D` gives a file under D (L plus the directory below D). A // module-alias call proves a candidate by one of these paths EXACTLY. The directory-tail rule is left only for a candidate // with no path when no in-tree file carries the import path either (a tree with no module facts for it at all). struct GoPackagePaths { std::vector nearest; // fileId → "" when no go.mod with a module line sits at or above the file std::vector replaced; // fileId → "" when no local replace maps the file's directory HashMap known; // every non-empty path in either table // file `f`'s entry in `table` ("" when none) static std::string_view pathIn( const std::vector& table, std::uint32_t f ) noexcept { return f < table.size() ? std::string_view( table[ f ] ) : std::string_view{}; } bool hasPath( std::uint32_t f ) const noexcept { return !pathIn( nearest, f ).empty() || !pathIn( replaced, f ).empty(); } // does `path` name file `f`'s package exactly bool names( std::uint32_t f, std::string_view path ) const noexcept { return !path.empty() && ( pathIn( nearest, f ) == path || pathIn( replaced, f ) == path ); } void note( std::vector& table, std::uint32_t f, std::string path ) { EXPECTS( f < table.size(), "collectGoModules sizes both tables to ing.files" ); if( !path.empty() ) { known.try_emplace( path, '\0' ); } table[ f ] = std::move( path ); } }; // Slice 6c: implicitReceiver, memberNeverReachesFreeFunction, moduleCallReachesFunctionsOnly moved to langFacts(l) in langfacts.h // (L) the languages whose own receiver rule (Rule 1) answers `self.m()`, so receiver evidence adds only a LOCAL whose class a // binding states and the field paths below it or below `self` (ReceiverEvidence::narrowTypedLocal): Rust, whose locals are // typed by the call results graph.h's resolve loop records (train 29) and, since rust-receivers, by a written parameter / // `let x: T` / `let x = T { .. }` / `T::default()` type and a struct field's written type. Not typed (stated floors): a // generic `T: Bound`, `dyn Trait` / `impl Trait`, a trait written as a type, a value behind Option / Result / Rc / Arc / // RefCell / Cell / Mutex / RwLock, a tuple-struct field (`self.0`), a pattern other than a plain name. inline bool receiverLocalsOnly( Lang l ) noexcept { switch( l ) { case Lang::Rust: return true; default: return false; } } // (L) which members a call-result-typed local's CLASS owns (fix round 1: the typed fact carries the class's id, and a member // call on the local reaches that class's own members, never a same-named class's): Lexical — the class whose span holds the // member (Java, Kotlin, TS; a member outside every class, a Kotlin extension, belongs to the class's own file); PackageDir — // Go, whose methods sit beside the type in its package's directory; FileOrUnique — Rust, whose `impl` blocks sit in the // type's own file, or anywhere when no other in-tree type shares its name. enum class MemberOwnerRule : std::uint8_t { Lexical, PackageDir, FileOrUnique }; inline MemberOwnerRule memberOwnerRuleOf( Lang l ) noexcept { switch( l ) { case Lang::Go: return MemberOwnerRule::PackageDir; case Lang::Rust: return MemberOwnerRule::FileOrUnique; default: return MemberOwnerRule::Lexical; } } // Lane h1-annot: how a written type's QUALIFIER (`pkg.T`, `mod.T`, `ns.T<…>`: the capture's RecvType / MemberType importedName) // is checked before its final segment may name an in-tree class. GoPackage — the import path names an in-tree package that // defines T (CallResultTypes::goQualifiedClass). FileImport — Python and TS: the qualifier's ROOT is bound by the file's // imports to an in-tree module, package or relative path (graph.h buildQualifierVerdicts), or, bound by no import, names an // in-tree class (`Outer.Inner`) or a TS namespace; T itself is then read by its final segment as before. None — a family whose // capture writes no qualifier: the written type proves nothing. enum class WrittenQualifierRule : std::uint8_t { None, GoPackage, FileImport }; inline WrittenQualifierRule writtenQualifierRuleOf( Lang l ) noexcept { switch( l ) { case Lang::Go: return WrittenQualifierRule::GoPackage; case Lang::Python: case Lang::TypeScript: return WrittenQualifierRule::FileImport; default: return WrittenQualifierRule::None; } } // Slice 6c: classNameReceiver moved to langFacts(l) in langfacts.h // a call written ON a receiver — every language's member shape: Python/C++/Ruby record a RecvKind, the rest memberCall inline bool isMemberCallRef( const Reference& r ) noexcept { return r.recv != RecvKind::None || r.memberCall; } inline bool isThisRoot( std::string_view root ) noexcept { return root == "this" || root == "self" || root == "Self"; } // Is `root` (the call's receiver root, ReceiverEvidence::chainOf) the language's BASE-CLASS receiver — a lookup that walks // the caller's bases only? Each spelling counts only where the grammar makes it that keyword: C# `base`; `super` in // Java, Kotlin, Swift, JS and TS; Python's `super()` / `super(C, self)` call, which ingest records as RecvKind::SuperObj. // Everywhere else the same text is an ordinary name — a Python/JS/Go/Java/… local `base`, a Go or C# local `super`, a // Python name `super` that shadows the builtin — and proves nothing about the bases (its own type, if any, decides). inline bool isSuperRoot( const Reference& r, std::string_view root ) noexcept { if( r.recv == RecvKind::SuperObj ) { return true; } switch( r.lang ) { case Lang::CSharp: return root == "base"; case Lang::Java: case Lang::Kotlin: case Lang::Swift: case Lang::JavaScript: case Lang::TypeScript: return root == "super"; default: return false; } } // The innermost function/method of `id`'s file whose span strictly holds `id`'s span; kNoNode when none. `byFile` is // fileId → that file's functions/methods sorted by sigStartByte. Shared by ReceiverEvidence and graph.h FalseEdgeRules. inline NodeId innermostEnclosingFn( const IngestResult& ing, const std::vector>& byFile, NodeId id ) { const Symbol& inner = ing.symbols[ id ]; if( inner.fileId >= byFile.size() ) { return kNoNode; } NodeId best = kNoNode; for( NodeId c : byFile[ inner.fileId ] ) { const Symbol& s = ing.symbols[ c ]; if( s.sigStartByte > inner.sigStartByte ) { break; // sorted by start: nothing later can hold it } if( c != id && s.endByte >= inner.endByte && ( s.sigStartByte < inner.sigStartByte || s.endByte > inner.endByte ) ) { best = c; // later starts are more inner } } return best; } // (L) fix round 3 — how a bare type name is looked up, per family (data rows read by CallResultTypes::bareClassAt): which // scopes are levels of the lexical chain, where a family's imports bind, and which tiers follow the file. Every other // family (Go: its package directory; C++: namespaces and includes, cppUnqualifiedClass) has its own reader. struct BareNameRules { CallResultFamily family; bool itemScopesOnly; // Rust: only an item scope is a level (rustScopesItems) — a struct / trait / impl scopes none bool modIsBarrier; // Rust: a `mod` (the file is one) is a fresh scope: no level outside it is read bool importsAtAnyLevel; // Rust: a `use` binds at the level it is written at (JVM / TS imports: the file level) bool levelWildcards; // Rust: a level's globs are read after its named bindings bool inheritedMembers; // JVM: a member type a base of an enclosing class declares (not followed: unresolved) bool packageTier; // JVM: past the file, the declared package's top-level classes and aliases bool fileWildcards; // JVM: last, the file's on-demand / star imports }; // Rust: the symbols whose body is an item scope (a nested item, `use` or macro there is in force for what it holds) — a fn // body, a `mod` (Other), and (fix round 6) a `const` / `static` item's value block (`const _: () = { … impl … };`, Var) inline constexpr std::array kRustItemScopeKinds = { SymKind::Function, SymKind::Method, SymKind::Var, SymKind::Other }; inline bool rustScopesItems( SymKind k ) noexcept { return extent::inSet( kRustItemScopeKinds, k ); } // the shared membership test inline constexpr BareNameRules kBareNameRules[] = { { CallResultFamily::Rust, true, true, true, true, false, false, false }, { CallResultFamily::Jvm, false, false, false, false, true, true, true }, { CallResultFamily::TypeScript, false, false, false, false, false, false, false }, }; // (L) fix round 1 — CallResultTypes: what a declared result type names, decided in its callee's file. // A type is recorded for a call result only when its written text RESOLVES, through the callee file's own context — // its imports, its qualifier, its own file, then its package / module / namespace — to exactly ONE in-tree class; // the typed local then carries that class (LocalFact::cls), never its name alone. A name imported from outside, an // outside qualifier, a global, a name that resolves nowhere or to two classes: kNoNode, nothing recorded. The import // and qualifier readers differ per family (the rows below); the rule is one. struct CallResultTypes { const IngestResult& ing; HashMap> classDefsByName; // class-like name → its definitions, id order std::vector> importsByFile; // fileId → its TypeImport / JsImport records const HashMap* moduleAlias = nullptr; // ReceiverEvidence's "#name" → module const GoPackagePaths* goPackages = nullptr; // graph.h FalseEdgeRules::goPackages const HashMap* jsPinnedClasses = nullptr; // graph.h: "#" → the class a TS import pins const HashMap* jsImportModules = nullptr; // graph.h (lane L6): "#" → the file a TS import's module resolved to const ClassIdentity* classIds = nullptr; // graph.h: C-family class identity (resolve.h) const rw::FileSetStore* fileIncludes = nullptr; // graph.h: C-family transitive include set per file (sorted) const HashMap>* chaUp = nullptr; // class name → its direct base names // fix round 2: the Namespace records (scopes the index has no symbol for) in (file, start) order, the C++ files holding a // namespace- or file-scope using (sorted), and each class's innermost enclosing symbol as first asked (kNoNode: file scope) std::vector namespaces; std::vector cppUsingFiles; HashMap jvmPackages; // the Java / Kotlin packages the tree declares mutable HashMap enclosingMemo; // fix round 3: each JVM file's declared package ("" none), the files of each declared package, and every TypeAlias row // by the name it binds (a C++ base class's member alias) std::vector filePackage; HashMap> packageFiles; HashMap> aliasesByName; HashMap> goReceiverWitness; // GO-CALLRESULT-LOCAL: Go receiver type name → one method per package directory (goDeclLessType) // RULE3-MEMBER-GUARD: the package directory of a Rust source path (`crates/settings/src/file.rs` → `crates/settings`), empty for a path outside src/, tests/, benches/, examples/ static std::string_view rustPackageDirOf( std::string_view path ) { std::size_t cut = path.size(); for( const std::string_view part : { std::string_view( "/src/" ), std::string_view( "/tests/" ), std::string_view( "/benches/" ), std::string_view( "/examples/" ) } ) { cut = std::min( cut, path.find( part ) ); } return cut == path.size() ? std::string_view{} : path.substr( 0, cut ); } // Rust crate/module layout, built on the first Rust resolution: a file's crate (its nearest `lib.rs` / `main.rs` // directory) and module path (`a::b` for src/a/b.rs or src/a/b/mod.rs), the crates by name (`mdbook_core` for // crates/mdbook-core/src), and each module's files struct RustLayout { bool built = false; std::vector crateOf; // fileId → crate index, kNoCrate when none std::vector moduleOf; // fileId → module path ("" = the crate root) HashMap crateByName; HashMap> filesOf; // "#" → its files HashMap inlineMods; // fix round 3: "#" → an inline `mod` symbol HashMap packageNames; // RULE3-MEMBER-GUARD: every package directory's name (`-` as `_`), lib.rs or not }; static constexpr std::uint32_t kNoCrate = 0xFFFFFFFFu; mutable RustLayout rust; mutable std::string nameKey; // classesNamed's lookup buffer mutable std::string aliasKey; // importPathOf's / the TS pin lookup's mutable std::vector usingPath; // forEachCppUsing's per-row namespace path mutable std::string moduleKey; // rustModuleKey's buffer mutable bool pathCut = false; // fc1 fix 3: a rustPathOutside walk hit its depth cap — its false then means "cut", not "stays in the tree" explicit CallResultTypes( const IngestResult& i ) : ing( i ) {} // the index build: every class-like definition by name, and each file's import records void noteClass( const Symbol& s ) { classDefsByName[ s.name ].push_back( s.id ); } void noteImport( const Binding& b ) { if( b.kind == LocalBindKind::Namespace && b.spanEnd == 0 ) { jvmPackages.try_emplace( b.var, char( 1 ) ); // a Java / Kotlin `package` declaration (model.h) if( b.fileId < filePackage.size() ) { filePackage[ b.fileId ] = b.var; packageFiles[ b.var ].push_back( b.fileId ); } return; } if( b.kind == LocalBindKind::Namespace ) { namespaces.push_back( &b ); return; } const bool alias = b.kind == LocalBindKind::TypeAlias; if( ( b.kind == LocalBindKind::TypeImport || b.kind == LocalBindKind::JsImport || alias ) && b.fileId < importsByFile.size() && !b.var.empty() ) { importsByFile[ b.fileId ].push_back( &b ); if( alias ) { aliasesByName[ b.var ].push_back( &b ); } if( isCppScopeRow( b ) && ( cppUsingFiles.empty() || cppUsingFiles.back() != b.fileId ) ) { cppUsingFiles.push_back( b.fileId ); } } } // a C++ using-directive / using-declaration, or (fix round 3) a C++ alias: the rows that carry their scope's span (model.h) static bool isCppScopeRow( const Binding& b ) noexcept { constexpr LocalBindKind kSpanned[] = { LocalBindKind::TypeImport, LocalBindKind::TypeAlias }; // the kinds a C++ scope span rides on return b.spanEnd != 0 && std::ranges::find( kSpanned, b.kind ) != std::end( kSpanned ); } // fix round 4: a TypeAlias row that binds its spelling with no alias target — a forward declaration, a type declaration // the index keeps no class for, an unparsed region (model.h kTypeBind* constants) static bool bindsWithoutTarget( const Binding& b ) noexcept { constexpr std::string_view kMarks[] = { kTypeBindForward, kTypeBindShadow, kTypeBindUnparsed }; return b.kind == LocalBindKind::TypeAlias && std::ranges::find( kMarks, std::string_view( b.typeName ) ) != std::end( kMarks ); } // after the last noteImport: the two lists in (file, start) / file order void finishIndex() { std::stable_sort( namespaces.begin(), namespaces.end(), []( const Binding* a, const Binding* b ) { return a->fileId != b->fileId ? a->fileId < b->fileId : a->startByte < b->startByte; } ); std::sort( cppUsingFiles.begin(), cppUsingFiles.end() ); cppUsingFiles.erase( std::unique( cppUsingFiles.begin(), cppUsingFiles.end() ), cppUsingFiles.end() ); } // the import path the file-scope name `name` binds in file `fileId` ("" when none, or rebound) std::string_view importPathOf( std::uint32_t fileId, std::string_view name ) const { if( moduleAlias == nullptr ) { return {}; } aliasKey.assign( std::to_string( fileId ) ).append( 1, '#' ).append( name ); const auto it = moduleAlias->find( aliasKey ); return it == moduleAlias->end() ? std::string_view{} : std::string_view( it->second ); } std::string_view dirOf( std::uint32_t fileId ) const { return includerDir( rootRelPath( ing, fileId ) ); } // is `dir` the directory `tail` names, read from its end and segment-aligned (`a/b/model` ends `b/model`, not `del`): // resolve.h's tsimport::fileNamed, refusing an empty tail (the repository root names no package) static bool endsWithDir( std::string_view dir, std::string_view tail ) noexcept { return !tail.empty() && tsimport::fileNamed( dir, tail ); } // the in-tree class-likes named `name` of family `fam` that `keep` admits: their count, and the last one in `one` template std::size_t classesNamed( std::string_view name, CallResultFamily fam, Keep&& keep, NodeId& one ) const { one = kNoNode; nameKey.assign( name ); const auto it = classDefsByName.find( nameKey ); if( it == classDefsByName.end() ) { return 0; } std::size_t n = 0; for( NodeId c : it->second ) { if( callResultFamilyOf( ing.symbols[ c ].lang ) == fam && keep( c ) ) { one = c; ++n; } } return n; } template NodeId onlyClass( std::string_view name, CallResultFamily fam, Keep&& keep ) const { NodeId one = kNoNode; return classesNamed( name, fam, keep, one ) == 1 ? one : kNoNode; } // the import records of file `fileId` binding the local name `var` (TypeImport / JsImport) template void forEachImport( std::uint32_t fileId, std::string_view var, Fn&& fn ) const { if( fileId < importsByFile.size() ) { for( const Binding* b : importsByFile[ fileId ] ) { if( b->var == var ) { fn( *b ); } } } } // ── lexical scope (fix round 2): is a class in scope, by its bare name, where the callee is declared ── // the Namespace records of file `f`, outermost first std::span namespacesOf( std::uint32_t f ) const { const auto run = std::ranges::equal_range( namespaces, f, std::ranges::less{}, []( const Binding* b ) { return b->fileId; } ); return { run.begin(), run.end() }; } // the innermost symbol of `c`'s file whose span strictly holds `c`'s — the class, module or function it is nested in; // kNoNode at file scope. Symbol ids ascend by (file, line), so a holder sits before `c` or after it on `c`'s own line. NodeId enclosingSymbol( NodeId c ) const { if( const auto it = enclosingMemo.find( c ); it != enclosingMemo.end() ) { return it->second; } const Symbol& cs = ing.symbols[ c ]; NodeId best = kNoNode; const auto consider = [ & ]( NodeId s ) { const Symbol& o = ing.symbols[ s ]; const bool holds = o.sigStartByte <= cs.sigStartByte && o.endByte >= cs.endByte && ( o.sigStartByte < cs.sigStartByte || o.endByte > cs.endByte ); best = holds && ( best == kNoNode || o.sigStartByte > ing.symbols[ best ].sigStartByte ) ? s : best; }; for( NodeId s = c; s > 0 && ing.symbols[ s - 1 ].fileId == cs.fileId; --s ) { consider( s - 1 ); } for( NodeId s = c + 1; s < ing.symbols.size() && ing.symbols[ s ].fileId == cs.fileId && ing.symbols[ s ].line == cs.line; ++s ) { consider( s ); } enclosingMemo.try_emplace( c, best ); return best; } // Rust: the innermost item scope — a `mod` (SymKind::Other) or a fn body — enclosing symbol `s`; kNoNode at its file's // own level (through enclosingSymbol: an `impl` block is no symbol, so its methods sit in the scope that holds it) NodeId innermostItemScope( NodeId s ) const { NodeId up = enclosingSymbol( s ); for( int guard = 0; guard < 64 && up != kNoNode && ing.symbols[ up ].kind != SymKind::Other && ing.symbols[ up ].kind != SymKind::Function && ing.symbols[ up ].kind != SymKind::Method; ++guard ) { up = enclosingSymbol( up ); } return up; } // does a Namespace record of `c`'s file hold `c` bool inNamespace( NodeId c ) const { const Symbol& cs = ing.symbols[ c ]; for( const Binding* ns : namespacesOf( cs.fileId ) ) { if( ns->spanStart <= cs.sigStartByte && cs.sigStartByte < ns->spanEnd ) { return true; } } return false; } // does C-family symbol `c`'s scope (Symbol::scope, the innermost segment) name a class rather than a namespace? C++ keeps // no Namespace record (callResultFamilyOf is None for it), so the scope is read against the tree's classes: a template // specialization's scope (`formatter`) or the name of an in-tree C-family class-like is a class; any other // non-empty scope is the namespace around the definition. A namespace namesake of some class reads as a class: the // caller decides nothing then (CPP-FREE-VS-MEMBER, graph.h FreeDeclReach) bool cppScopeNamesClass( NodeId c ) const { const std::string_view scope = ing.symbols[ c ].scope; if( scope.empty() ) { return false; } if( scope.find( '<' ) != std::string_view::npos ) { return true; } nameKey.assign( scope ); const auto it = classDefsByName.find( nameKey ); return it != classDefsByName.end() && std::ranges::any_of( it->second, [ & ]( NodeId k ) { return langFacts( ing.symbols[ k ].lang ).transitiveIncludes; } ); } // Is class `c` in scope by its bare name at byte `at` of file `f` (a callee's declaration)? In its own file every scope // enclosing it — an indexed symbol (class, module, function) or a Namespace record — must hold `at` too (inside, not at, // the scope's own start: a function's local class is not in scope in its own signature); from another file — its package, // its module — it must sit at file scope: a nested class is reached through its outer name, never bare. bool visibleAt( NodeId c, std::uint32_t f, std::uint32_t at ) const { const Symbol& cs = ing.symbols[ c ]; const NodeId outer = enclosingSymbol( c ); if( cs.fileId != f ) { return outer == kNoNode && !inNamespace( c ); } if( outer != kNoNode && !( ing.symbols[ outer ].sigStartByte < at && at < ing.symbols[ outer ].endByte ) ) { return false; } for( const Binding* ns : namespacesOf( f ) ) { const bool holdsClass = ns->spanStart <= cs.sigStartByte && cs.sigStartByte < ns->spanEnd; if( holdsClass && !( ns->spanStart <= at && at < ns->spanEnd ) ) { return false; } } return true; } // ── fix round 3: ONE rule for a bare type name — every binding of the spelling visible where it is written decides ── // A level of the lexical chain: a symbol's span (`sym`), a Namespace record's body (sym kNoNode), or the whole file. struct Level { std::uint32_t start = 0; std::uint32_t end = 0xFFFFFFFFu; NodeId sym = kNoNode; bool wholeFile() const noexcept { return start == 0 && end == 0xFFFFFFFFu && sym == kNoNode; } bool operator==( const Level& ) const = default; }; // The votes of one level (or tier): each binding of the spelling there names one in-tree class, or kNoNode (outside, // unresolved, an alias). ONE class decides; anything else — an outside or unresolved binding, two that disagree — names // nothing. struct Ballot { bool any = false; bool split = false; NodeId cls = kNoNode; void vote( NodeId c ) noexcept { split = split || c == kNoNode || ( any && c != cls ); cls = c; any = true; } NodeId verdict() const noexcept { return any && !split ? cls : kNoNode; } }; // the symbol ids of file `f` (ids ascend by file) std::pair symbolsOf( std::uint32_t f ) const { const auto byFile = []( const Symbol& o ) { return o.fileId; }; const auto run = std::ranges::equal_range( ing.symbols, f, std::ranges::less{}, byFile ); return { NodeId( run.begin() - ing.symbols.begin() ), NodeId( run.end() - ing.symbols.begin() ) }; } // the innermost symbol of file `f` that `keep` admits and whose span strictly holds byte `pos`; kNoNode when none template NodeId innermostHolding( std::uint32_t f, std::uint32_t pos, Keep&& keep ) const { NodeId best = kNoNode; const auto [ lo, hi ] = symbolsOf( f ); for( NodeId s = lo; s < hi; ++s ) { const Symbol& o = ing.symbols[ s ]; const bool holds = o.sigStartByte < pos && pos < o.endByte && keep( o.kind ); best = holds && ( best == kNoNode || o.sigStartByte > ing.symbols[ best ].sigStartByte ) ? s : best; } return best; } // the innermost level of file `f` holding byte `pos` — a symbol (strictly inside it) or a Namespace body; the file when none Level levelAt( std::uint32_t f, std::uint32_t pos ) const { const NodeId s = innermostHolding( f, pos, []( SymKind k ) { return k != SymKind::ModuleScope; } ); Level best = s == kNoNode ? Level{} : Level{ ing.symbols[ s ].sigStartByte, ing.symbols[ s ].endByte, s }; for( const Binding* ns : namespacesOf( f ) ) { if( ns->spanStart <= pos && pos < ns->spanEnd && ( best.wholeFile() || ns->spanStart > best.start ) ) { best = { ns->spanStart, ns->spanEnd, kNoNode }; } } return best; } // every level holding byte `at` of file `f`, innermost first, the file last void chainAt( std::uint32_t f, std::uint32_t at, std::vector& out ) const { out.clear(); const auto [ lo, hi ] = symbolsOf( f ); for( NodeId s = lo; s < hi; ++s ) { const Symbol& o = ing.symbols[ s ]; if( o.kind != SymKind::ModuleScope && o.sigStartByte < at && at < o.endByte ) { out.push_back( { o.sigStartByte, o.endByte, s } ); } } for( const Binding* ns : namespacesOf( f ) ) { if( ns->spanStart <= at && at < ns->spanEnd ) { out.push_back( { ns->spanStart, ns->spanEnd, kNoNode } ); } } std::ranges::sort( out, []( const Level& a, const Level& b ) { return a.start != b.start ? a.start > b.start : a.end < b.end; } ); out.push_back( Level{} ); } // the level class `c` is declared in: its enclosing symbol, or a Namespace record holding it, whichever is innermost Level levelOfClass( NodeId c ) const { const Symbol& cs = ing.symbols[ c ]; const NodeId outer = enclosingSymbol( c ); Level best = outer == kNoNode ? Level{} : Level{ ing.symbols[ outer ].sigStartByte, ing.symbols[ outer ].endByte, outer }; for( const Binding* ns : namespacesOf( cs.fileId ) ) { if( ns->spanStart <= cs.sigStartByte && cs.sigStartByte < ns->spanEnd && ( best.wholeFile() || ns->spanStart > best.start ) ) { best = { ns->spanStart, ns->spanEnd, kNoNode }; } } return best; } static bool notModule( SymKind k ) noexcept { return k != SymKind::ModuleScope; } static bool classKind( SymKind k ) noexcept { constexpr SymKind kClassKinds[] = { SymKind::Class, SymKind::Struct, SymKind::Interface }; // the class-like kinds return std::ranges::find( kClassKinds, k ) != std::end( kClassKinds ); } // the innermost class of file `f` whose span holds byte `pos` (a member declaration's class); kNoNode when none NodeId classHolding( std::uint32_t f, std::uint32_t pos ) const { return innermostHolding( f, pos, &classKind ); } // JVM / C++: does a base of class `holder` — through in-tree bases, transitively (a visited set: a diamond is walked // once) — declare a member type `name` (a nested class, or a C++ member alias)? Such a member type is in scope inside // `holder` and is not followed here: the spelling names nothing. bool inheritsMemberType( NodeId holder, std::string_view name, CallResultFamily fam ) const { if( chaUp == nullptr ) { return false; } std::vector cone; nameKey.assign( ing.symbols[ holder ].name ); if( const auto it = chaUp->find( nameKey ); it != chaUp->end() ) { cone.assign( it->second.begin(), it->second.end() ); } for( std::size_t i = 0; i < cone.size() && cone.size() < 64; ++i ) { nameKey.assign( cone[ i ] ); if( const auto it = chaUp->find( nameKey ); it != chaUp->end() ) { for( const std::string& b : it->second ) { if( std::ranges::find( cone, std::string_view( b ) ) == cone.end() ) { cone.push_back( b ); } } } } if( cone.empty() ) { return false; } const auto inCone = [ & ]( NodeId owner ) { return owner != kNoNode && std::ranges::find( cone, std::string_view( ing.symbols[ owner ].name ) ) != cone.end(); }; NodeId one = kNoNode; if( classesNamed( name, fam, [ & ]( NodeId c ) { return inCone( enclosingSymbol( c ) ); }, one ) > 0 ) { return true; } nameKey.assign( name ); const auto aliases = aliasesByName.find( nameKey ); return aliases != aliasesByName.end() && std::ranges::any_of( aliases->second, [ & ]( const Binding* b ) { const NodeId holder = classHolding( b->fileId, b->startByte ); // fix round 4: a member of the class, not of one of its bodies return inCone( holder ) && innermostHolding( b->fileId, b->startByte, ¬Module ) == holder; } ); } // the JVM files of one package as `f` sees it: the same declared package, or (neither declares one) the same directory bool samePackage( std::uint32_t f, std::uint32_t g ) const { const std::string_view pf = f < filePackage.size() ? filePackage[ f ] : std::string_view{}; const std::string_view pg = g < filePackage.size() ? filePackage[ g ] : std::string_view{}; return pf.empty() && pg.empty() ? dirOf( f ) == dirOf( g ) : pf == pg; } // the ONE in-tree class a named import row `b` of file `f` binds (kNoNode: outside, unresolved, or two) NodeId importedClass( CallResultFamily fam, std::uint32_t f, const Binding& b ) const { switch( fam ) { case CallResultFamily::Rust: { const auto [ modPath, item ] = splitLast( b.importedName, "::" ); return modPath.empty() ? kNoNode : rustClassAt( f, b.startByte, modPath, item ); } case CallResultFamily::Jvm: return jvmClassIn( b.importedName, b.typeName ); case CallResultFamily::TypeScript: { if( jsPinnedClasses == nullptr ) { return kNoNode; } aliasKey.assign( std::to_string( f ) ).append( 1, '#' ).append( b.var ); const auto it = jsPinnedClasses->find( aliasKey ); return it == jsPinnedClasses->end() ? kNoNode : it->second; } default: return kNoNode; } } // a named (non-wildcard) import row of the family static bool namedImport( CallResultFamily fam, const Binding& b ) noexcept { return fam == CallResultFamily::TypeScript ? b.kind == LocalBindKind::JsImport : b.kind == LocalBindKind::TypeImport && b.var != "*"; } // a wildcard row `b` (Rust `use m::*`, JVM `import p.*`) seen from file `f`: the class `name` it supplies; `supplies` // false when it supplies none — an outside or unresolved wildcard MAY supply it (kNoNode, supplies true) NodeId wildcardSupplies( CallResultFamily fam, std::uint32_t f, const Binding& b, std::string_view name, bool& supplies ) const { supplies = true; if( fam == CallResultFamily::Rust ) { std::uint32_t crate = kNoCrate; std::string module; if( !rustModuleOf( f, b.startByte, b.importedName, crate, module, 0 ) ) { return kNoNode; } RustItemWalk walk; return rustModuleItem( crate, module, name, walk, supplies ); // rust-receivers: `supplies` when the module has the item, re-exports it or globs it in } nameKey.assign( b.importedName ); const auto files = packageFiles.find( nameKey ); if( files == packageFiles.end() ) { return kNoNode; // a package the tree does not declare (or a class's members: `import p.Obj.*`) } NodeId one = kNoNode; const std::size_t n = classesNamed( name, CallResultFamily::Jvm, [ & ]( NodeId c ) { return std::ranges::find( files->second, ing.symbols[ c ].fileId ) != files->second.end() && levelOfClass( c ).wholeFile(); }, one ); supplies = n > 0; return n == 1 ? one : kNoNode; } // THE RULE (fix round 3). The bare type name `name` written at byte `at` of file `f` (a callee's declared result, or a // JVM class-name receiver at its call) names the ONE in-tree class the language's own lookup reaches: walk the lexical // chain innermost first; at each level collect EVERY binding of the spelling there — a class declared in it, an alias // (always kNoNode: not followed), a named import binding there (Rust: at any level; JVM / TS: the file), a member type a // base of the level's class declares (JVM: kNoNode) — and the first level with any binding decides by its Ballot; a // level's wildcards (Rust globs) vote only when its named bindings are silent. Rust stops at its module (a fresh // scope); past the file the JVM reads its package's top-level classes and aliases, then the file's on-demand imports. NodeId bareClassAt( CallResultFamily fam, std::uint32_t f, std::uint32_t at, std::string_view name ) const { const auto rules = std::ranges::find( kBareNameRules, fam, &BareNameRules::family ); // the family's data row if( rules == std::end( kBareNameRules ) || f >= importsByFile.size() ) { return kNoNode; } std::vector chain; chainAt( f, at, chain ); for( const Level& lv : chain ) { const SymKind kind = lv.sym == kNoNode ? SymKind::Other : ing.symbols[ lv.sym ].kind; if( rules->itemScopesOnly && lv.sym != kNoNode && !rustScopesItems( kind ) ) { continue; // a Rust struct / trait / enum declares no item in scope (an associated type is `Self::T`) } Ballot named; NodeId one = kNoNode; classesNamed( name, fam, [ & ]( NodeId c ) { if( ing.symbols[ c ].fileId == f && levelOfClass( c ) == lv ) { named.vote( c ); } return false; }, one ); forEachImport( f, name, [ & ]( const Binding& b ) { const bool here = rules->importsAtAnyLevel || b.kind == LocalBindKind::TypeAlias ? levelAt( f, b.startByte ) == lv : lv.wholeFile(); if( here && b.kind == LocalBindKind::TypeAlias ) { named.vote( kNoNode ); } else if( here && namedImport( fam, b ) ) { named.vote( importedClass( fam, f, b ) ); } } ); if( !named.any && rules->inheritedMembers && lv.sym != kNoNode && classKind( kind ) && inheritsMemberType( lv.sym, name, fam ) ) { named.vote( kNoNode ); } if( !named.any ) // fix round 4: an unparsed region of this level (a Rust block's macro) may declare the name here { forEachImport( f, "!", [ & ]( const Binding& b ) { if( bindsWithoutTarget( b ) && levelAt( f, b.startByte ) == lv ) { named.vote( kNoNode ); } } ); } if( named.any ) { return named.verdict(); } if( rules->levelWildcards ) { Ballot globs; forEachImport( f, "*", [ & ]( const Binding& b ) { bool supplies = false; const NodeId c = b.kind == LocalBindKind::TypeImport && levelAt( f, b.startByte ) == lv ? wildcardSupplies( fam, f, b, name, supplies ) : kNoNode; if( supplies ) { globs.vote( c ); } } ); if( globs.any ) { return globs.verdict(); } } if( rules->modIsBarrier && ( lv.wholeFile() || kind == SymKind::Other ) ) { return kNoNode; // a Rust module: the name is the prelude's, an outside crate's, or unresolved } } if( rules->packageTier ) { Ballot pkg; NodeId one = kNoNode; classesNamed( name, fam, [ & ]( NodeId c ) { const std::uint32_t g = ing.symbols[ c ].fileId; if( g != f && samePackage( f, g ) && levelOfClass( c ).wholeFile() ) { pkg.vote( c ); } return false; }, one ); nameKey.assign( name ); if( const auto aliases = aliasesByName.find( nameKey ); aliases != aliasesByName.end() ) { for( const Binding* b : aliases->second ) { const bool declared = b->fileId < filePackage.size() && !filePackage[ b->fileId ].empty(); // a JVM file's own package if( b->fileId != f && declared && samePackage( f, b->fileId ) && levelAt( b->fileId, b->startByte ).wholeFile() ) { pkg.vote( kNoNode ); // a Kotlin `typealias` of the package } } } if( pkg.any ) { return pkg.verdict(); } } if( rules->fileWildcards ) { Ballot wild; forEachImport( f, "*", [ & ]( const Binding& b ) { bool supplies = false; const NodeId c = b.kind == LocalBindKind::TypeImport ? wildcardSupplies( fam, f, b, name, supplies ) : kNoNode; if( supplies ) { wild.vote( c ); } } ); return wild.verdict(); } return kNoNode; } // Go: `pkg.T` names a class of THIS tree only when `pkg` imports an in-tree package and that package defines exactly one // `T` — the exact package path when the tree has module facts (go.mod), else a directory that ends the path, // segment-aligned. Shared by written types (a local, parameter or field `f *os.File`) and call results. // Go `pkg.T` written in file `fileId` (`whole` = "pkg.T", `cls` = "T"): `find( inPackage )` with inPackage( f ) true for // the files of the package the file's import of `pkg` names; kNoNode when the spelling names no import template NodeId inGoImportedPackage( std::uint32_t fileId, std::string_view whole, std::string_view cls, Find&& find ) const { const std::size_t dot = whole.find( '.' ); if( dot == std::string_view::npos || cls.empty() ) { return kNoNode; } const std::string path( importPathOf( fileId, whole.substr( 0, dot ) ) ); if( path.empty() ) { return kNoNode; } const bool modules = goPackages != nullptr && !goPackages->known.empty(); return find( [ & ]( std::uint32_t f ) { return modules ? goPackages->names( f, path ) : endsWithDir( path, dirOf( f ) ); } ); } NodeId goQualifiedClass( std::uint32_t fileId, std::string_view whole, std::string_view cls ) const { return inGoImportedPackage( fileId, whole, cls, [ & ]( auto&& inPackage ) { return onlyPackageClass( cls, [ & ]( NodeId c ) { return inPackage( ing.symbols[ c ].fileId ) && enclosingSymbol( c ) == kNoNode; // a package-level type, never one local to a function } ); } ); } NodeId goResultClass( std::uint32_t fileId, std::uint32_t at, std::string_view whole, std::string_view cls ) const { if( !whole.empty() ) { return goQualifiedClass( fileId, whole, cls ); } const std::string_view dir = dirOf( fileId ); // one package is one directory return onlyPackageClass( cls, [ & ]( NodeId c ) { return dirOf( ing.symbols[ c ].fileId ) == dir && visibleAt( c, fileId, at ); } ); } // GO-CALLRESULT-LOCAL: a Go type the tree holds METHODS of and no declaration for — the declaration sits in a generated file // the tree leaves out (cockroach's `.pb.go`: `TenantID` is a proto message, its hand-written methods are in tenant.go). Go // declares a method only in its receiver type's own package, so a method `func ( t T ) m()` in package directory D proves // D.T exists, and T's methods in D are that type's own. The WITNESS — the first such method — stands for the type where // a class definition would (LocalFact::cls): ownedBy reads only its package directory, sameNamedClasses reads 0 for it (no // base walk, no field path), and no dispatch tier takes it for a type (it is not class-like). // `keep`: the files the written type's package admits. kNoNode when no kept method has that receiver, when two kept // directories do, or when a kept directory DECLARES a class of the name (then the declaration decides, refusals included). template NodeId goDeclLessType( std::string_view cls, Keep&& keep ) const { nameKey.assign( cls ); const auto it = goReceiverWitness.find( nameKey ); if( it == goReceiverWitness.end() ) { return kNoNode; } NodeId witness = kNoNode; for( NodeId m : it->second ) // one per package directory { if( !keep( ing.symbols[ m ].fileId ) ) { continue; } if( witness != kNoNode ) { return kNoNode; // two packages the spelling could name } witness = m; } if( witness == kNoNode ) { return kNoNode; } const std::string_view dir = dirOf( ing.symbols[ witness ].fileId ); NodeId declared = kNoNode; return classesNamed( cls, CallResultFamily::Go, [ & ]( NodeId c ) { return dirOf( ing.symbols[ c ].fileId ) == dir; }, declared ) == 0 ? witness : kNoNode; } // the build, after every noteClass: `method` has the Go receiver type `recvType` — kept once per package directory (binding // order), and only where that directory declares no class of the name, so a tree that holds its declarations keeps no row void noteGoReceiver( std::string_view recvType, NodeId method ) { const std::string_view dir = dirOf( ing.symbols[ method ].fileId ); NodeId declared = kNoNode; if( classesNamed( recvType, CallResultFamily::Go, [ & ]( NodeId c ) { return dirOf( ing.symbols[ c ].fileId ) == dir; }, declared ) != 0 ) { return; } rw::SmallVec& witnesses = goReceiverWitness[ std::string( recvType ) ]; if( std::ranges::none_of( witnesses, [ & ]( NodeId w ) { return dirOf( ing.symbols[ w ].fileId ) == dir; } ) ) { witnesses.push_back( method ); } } // does `id` stand for a declaration-less Go type (goDeclLessType's witness, a method), not a class definition bool standsForDeclLessType( NodeId id ) const noexcept { return id < ing.symbols.size() && !classKind( ing.symbols[ id ].kind ) && !isStructOrNamedType( ing.symbols[ id ].kind ); } // a declared result type (`rt`, a ReturnType) or a written qualified type naming such a type: its witness, else kNoNode NodeId goDeclLessResult( const Binding& rt, Lang lang ) const { if( callResultFamilyOf( lang ) != CallResultFamily::Go || rt.typeName.empty() ) { return kNoNode; } const std::string_view whole = rt.importedName; if( whole.empty() ) { const std::string_view dir = dirOf( rt.fileId ); // an unqualified result: the callee's own package return goDeclLessType( rt.typeName, [ & ]( std::uint32_t f ) { return dirOf( f ) == dir; } ); } return goDeclLessQualified( rt.fileId, whole, rt.typeName ); } NodeId goDeclLessQualified( std::uint32_t fileId, std::string_view whole, std::string_view cls ) const { return inGoImportedPackage( fileId, whole, cls, [ & ]( auto&& inPackage ) { return goDeclLessType( cls, inPackage ); } ); } // Go: the class `cls` of the ONE package directory `keep` admits — a type a package defines once per build-tag file // (`Executor` in util_unix.go and util_windows.go) is one class to the member rule (PackageDir), so its first // definition stands for it; two packages' namesakes are kNoNode template NodeId onlyPackageClass( std::string_view cls, Keep&& keep ) const { NodeId first = kNoNode; std::string_view dir; bool one = true; NodeId last = kNoNode; classesNamed( cls, CallResultFamily::Go, [ & ]( NodeId c ) { if( !keep( c ) ) { return false; } const std::string_view d = dirOf( ing.symbols[ c ].fileId ); one = one && ( first == kNoNode || d == dir ); first = first == kNoNode ? c : first; dir = first == c ? d : dir; return true; }, last ); return one ? first : kNoNode; } // Java / Kotlin: an imported or qualified `a.b.T` names the in-tree top-level class `T` of the package `a.b` the tree // DECLARES (fix round 3: a Kotlin file's package need not match its directory); a tree that declares no package reads // the directory ending `a/b`. A nested `a.b.Outer.T` is not followed (kNoNode). NodeId jvmClassIn( std::string_view path, std::string_view cls ) const { const std::size_t dot = path.rfind( '.' ); if( dot == std::string_view::npos ) { return kNoNode; } if( !jvmPackages.empty() ) { nameKey.assign( path.substr( 0, dot ) ); const auto files = packageFiles.find( nameKey ); if( files == packageFiles.end() ) { return kNoNode; // a package the tree does not declare: outside } return onlyClass( cls, CallResultFamily::Jvm, [ & ]( NodeId c ) { return std::ranges::find( files->second, ing.symbols[ c ].fileId ) != files->second.end() && levelOfClass( c ).wholeFile(); } ); } std::string pkgDir( path.substr( 0, dot ) ); std::replace( pkgDir.begin(), pkgDir.end(), '.', '/' ); return onlyClass( cls, CallResultFamily::Jvm, [ & ]( NodeId c ) { return endsWithDir( dirOf( ing.symbols[ c ].fileId ), pkgDir ) && levelOfClass( c ).wholeFile(); // a top-level class } ); } // Java / Kotlin (fix round 3: bareClassAt's rows), the order the languages scope a simple type name in: a class nested in // a scope that holds the callee or a member type its classes inherit, the file's single-type imports / own top-level // classes / aliases, the package's top-level classes and aliases, then the on-demand imports. NodeId jvmResultClass( std::uint32_t fileId, std::uint32_t at, std::string_view whole, std::string_view cls ) const { return whole.empty() ? bareClassAt( CallResultFamily::Jvm, fileId, at, cls ) : jvmClassIn( whole, cls ); } // D3 / D6: a JVM class-name receiver spelled `name` at byte `at` of the caller's file `fileId` names an in-tree class only // when the caller's file SEES one by that name (bareClassAt: its package, a single-type import naming it, an on-demand // import of its package, a nested class in scope): `import ext.Util;` or `import ext.*;` alone hides every in-tree // Util. True when the tree defines a class `name` the caller does not see. bool jvmHides( std::uint32_t fileId, std::uint32_t at, std::string_view name ) const { NodeId one = kNoNode; return classesNamed( name, CallResultFamily::Jvm, []( NodeId ) { return true; }, one ) > 0 && bareClassAt( CallResultFamily::Jvm, fileId, at, name ) == kNoNode; } // TypeScript: a name imported by name (`import { T }`, `import { U as T }`) names the ONE in-tree class graph.h's import // tables pin for it (buildJsImportTables: the module resolved, the export found) — an outside module, a type-only import // the tables do not pin, or a re-export they cannot follow names nothing; else a class of the file itself; else nothing: // a module neighbour is never in scope without an import, and an unimported name is a global (`Response`). A class inside // a `namespace` or a function is in scope only within it, and an alias there (`type T = …`, `import T = n.U`) hides any // outer class (bareClassAt). A namespace-qualified `ns.T` is not resolved (a floor). NodeId tsResultClass( std::uint32_t fileId, std::uint32_t at, std::string_view whole, std::string_view cls ) const { return whole.empty() ? bareClassAt( CallResultFamily::TypeScript, fileId, at, cls ) : kNoNode; } // Rust: the crate layout (RustLayout above), then a path's module seen from a file — `crate::`, `self::`, `super::`, an // in-tree crate's name, a `use`d module, or a child module of the file's own; any other root (`std`, an outside crate) // leaves the tree. void buildRustLayout() const { rust.built = true; const std::size_t files = ing.files.size(); rust.crateOf.assign( files, kNoCrate ); rust.moduleOf.assign( files, {} ); HashMap rootIndex; // crate root directory → crate index for( std::uint32_t f = 0; f < files; ++f ) { const std::string_view path = rootRelPath( ing, f ); if( path.ends_with( "lib.rs" ) || path.ends_with( "main.rs" ) ) { const std::string_view base = path.substr( includerDir( path ).empty() ? 0 : includerDir( path ).size() + 1 ); if( base != "lib.rs" && base != "main.rs" ) { continue; } const std::string dir( includerDir( path ) ); if( rootIndex.try_emplace( dir, std::uint32_t( rootIndex.size() ) ).second ) { // the crate's name: its package directory (`crates/mdbook-core/src` → mdbook_core), `-` read as `_` std::string_view pkg = dir; if( pkg == "src" || pkg.ends_with( "/src" ) ) { pkg = includerDir( pkg ); } std::string name( pkg.substr( includerDir( pkg ).empty() ? 0 : includerDir( pkg ).size() + 1 ) ); std::replace( name.begin(), name.end(), '-', '_' ); if( !name.empty() ) { const auto [ it, fresh ] = rust.crateByName.try_emplace( name, rootIndex[ dir ] ); if( !fresh ) { it->second = kNoCrate; // two crates of one name: the name decides nothing } } } } } for( std::uint32_t f = 0; f < files; ++f ) { const std::string_view path = rootRelPath( ing, f ); if( !path.ends_with( ".rs" ) ) { continue; } if( const std::string_view pkg = rustPackageDirOf( path ); !pkg.empty() ) { std::string name( pkg.substr( pkg.rfind( '/' ) == std::string_view::npos ? 0 : pkg.rfind( '/' ) + 1 ) ); std::replace( name.begin(), name.end(), '-', '_' ); rust.packageNames.try_emplace( std::move( name ), '\1' ); } for( std::string_view dir = includerDir( path );; dir = includerDir( dir ) ) { if( const auto it = rootIndex.find( std::string( dir ) ); it != rootIndex.end() ) { std::string module( path.substr( dir.empty() ? 0 : dir.size() + 1 ) ); module.resize( module.size() - 3 ); // ".rs" if( module == "lib" || module == "main" || module == "mod" ) { module.clear(); } else if( module.ends_with( "/mod" ) ) { module.resize( module.size() - 4 ); } for( std::size_t at = module.find( '/' ); at != std::string::npos; at = module.find( '/', at + 2 ) ) { module.replace( at, 1, "::" ); } rust.crateOf[ f ] = it->second; rust.moduleOf[ f ] = module; rust.filesOf[ std::to_string( it->second ) + "#" + module ].push_back( f ); break; } if( dir.empty() ) { break; } } } // fix round 3: every inline `mod m { … }` (SymKind::Other) is a module of its own, `::…::m` — never the // file of a `mod m;` declaration, whose module is that file's for( const Symbol& m : ing.symbols ) { if( m.kind != SymKind::Other || callResultFamilyOf( m.lang ) != CallResultFamily::Rust || m.fileId >= files || rust.crateOf[ m.fileId ] == kNoCrate ) { continue; } std::string module; rustModuleAt( m.fileId, m.sigStartByte, module ); module = joinModule( module, m.name ); if( !rust.filesOf.contains( rustModuleKey( rust.crateOf[ m.fileId ], module ) ) ) { rust.inlineMods.try_emplace( rustModuleKey( rust.crateOf[ m.fileId ], module ), m.id ); } } } // the module byte `at` of Rust file `f` sits in: the file's module, then each inline `mod` holding `at`, outermost first void rustModuleAt( std::uint32_t f, std::uint32_t at, std::string& module ) const { module = f < rust.moduleOf.size() ? rust.moduleOf[ f ] : std::string{}; const auto [ lo, hi ] = symbolsOf( f ); for( NodeId s = lo; s < hi; ++s ) // ids ascend by line: an outer mod precedes the mods it holds { const Symbol& o = ing.symbols[ s ]; if( o.kind == SymKind::Other && o.sigStartByte < at && at < o.endByte ) { module = joinModule( module, o.name ); } } } // the level of a module's own items: an inline mod's span, or (a file module) the file Level rustModuleLevel( NodeId inlineMod ) const { return inlineMod == kNoNode ? Level{} : Level{ ing.symbols[ inlineMod ].sigStartByte, ing.symbols[ inlineMod ].endByte, inlineMod }; } // `a::b` + `c` → `a::b::c`; the crate root ("") + `c` → `c` static std::string joinModule( std::string_view module, std::string_view seg ) { return module.empty() ? std::string( seg ) : std::string( module ).append( "::" ).append( seg ); } // "#", RustLayout::filesOf's key, built in the reused buffer const std::string& rustModuleKey( std::uint32_t crate, std::string_view module ) const { buildShadowKey( moduleKey, crate, module ); // model.h's "#" key, the layout's own spelling return moduleKey; } bool rustModuleExists( std::uint32_t crate, const std::string& module ) const { return rust.filesOf.contains( rustModuleKey( crate, module ) ) || rust.inlineMods.contains( rustModuleKey( crate, module ) ); } // each level of the chain at byte `at` of Rust file `f` that scopes items (a fn body, then the module it sits in: an // inline `mod`, or the file), innermost first, until `fn( level )` returns true or the module level is passed template void forEachRustScopeAt( std::uint32_t f, std::uint32_t at, Fn&& fn ) const { std::vector chain; chainAt( f, at, chain ); for( const Level& lv : chain ) { const SymKind kind = lv.sym == kNoNode ? SymKind::Other : ing.symbols[ lv.sym ].kind; if( lv.sym != kNoNode && !rustScopesItems( kind ) ) { continue; } if( fn( lv ) || lv.wholeFile() || kind == SymKind::Other ) { return; } } } // the `use` rows binding `name` in force at byte `at` of file `f`: those of the innermost level (a fn body, then the // module) that holds one — a `use` binds where it is written (fix round 3), never file-wide template void forEachRustUseAt( std::uint32_t f, std::uint32_t at, std::string_view name, Fn&& fn ) const { forEachRustScopeAt( f, at, [ & ]( const Level& lv ) { bool found = false; forEachImport( f, name, [ & ]( const Binding& b ) { if( b.kind == LocalBindKind::TypeImport && levelAt( f, b.startByte ) == lv ) { found = true; fn( b ); } } ); return found; } ); } // RUST-PATH-OWNER: the crate (RustLayout) file `f` belongs to, kNoCrate when the layout places it in none std::uint32_t rustCrateOfFile( std::uint32_t f ) const { if( !rust.built ) { buildRustLayout(); } return f < rust.crateOf.size() ? rust.crateOf[ f ] : kNoCrate; } // the (crate, module) `modPath` (`crate::model`, `super::x`, `mdbook_core::book`, a `use`d `model`) names at byte `at` of // file `f` — relative to the module `at` sits in, an inline `mod` included (fix round 3: `super::` inside `mod m` is the // file's module, `self::` is m); a segment that is a `use`d module, not a child one, is followed (rustAliasedModuleOf) bool rustModuleOf( std::uint32_t f, std::uint32_t at, std::string_view modPath, std::uint32_t& crate, std::string& module, int depth ) const { if( !rust.built ) { buildRustLayout(); } if( f >= rust.crateOf.size() || rust.crateOf[ f ] == kNoCrate || modPath.empty() || depth > 4 ) { return false; } std::vector segs; for( std::size_t at = 0;; ) { const std::size_t sep = modPath.find( "::", at ); segs.push_back( modPath.substr( at, sep == std::string_view::npos ? std::string_view::npos : sep - at ) ); if( sep == std::string_view::npos ) { break; } at = sep + 2; } crate = rust.crateOf[ f ]; rustModuleAt( f, at, module ); std::size_t i = 1; if( segs[ 0 ] == "crate" ) { module.clear(); } else if( segs[ 0 ] == "super" ) { for( i = 0; i < segs.size() && segs[ i ] == "super"; ++i ) { if( module.empty() ) { return false; } const std::size_t up = module.rfind( "::" ); module.resize( up == std::string::npos ? 0 : up ); } } else if( segs[ 0 ] != "self" ) { // a `use` binding of the name in force there shadows a crate of that name; two `use`s of one name decide nothing std::size_t uses = 0; std::string usedPath; std::uint32_t usedAt = 0; forEachRustUseAt( f, at, segs[ 0 ], [ & ]( const Binding& b ) { ++uses; usedPath = b.importedName; usedAt = b.startByte; } ); const auto byName = rust.crateByName.find( std::string( segs[ 0 ] ) ); if( uses > 1 ) { return false; } if( uses == 1 ) { if( !rustModuleOf( f, usedAt, usedPath, crate, module, depth + 1 ) ) { return false; } } else if( byName != rust.crateByName.end() && byName->second != kNoCrate ) { crate = byName->second; module.clear(); } else if( rustModuleExists( crate, joinModule( module, segs[ 0 ] ) ) ) { module = joinModule( module, segs[ 0 ] ); } else { return false; // `std`, an outside crate, an unknown name } } const std::string from = module; for( std::size_t s = i; s < segs.size(); ++s ) { module = joinModule( module, segs[ s ] ); } if( rustModuleExists( crate, module ) ) { return true; } module = from; return rustAliasedModuleOf( crate, module, std::span( segs ).subspan( i ), depth ); } // RUST-MODALIAS-GLOB: rustModuleOf's tail when the path names no module of the layout as written: each segment that is no // child module of the module reached so far is followed through the ONE `use` binding that name at that module's own level // (axum-extra lib.rs `pub(crate) use axum::test_helpers;` makes `crate::test_helpers` axum's module, and a glob of it the // items that module declares and re-exports). The `use` path reads from where it is written (rustModuleOf, one hop deeper: // a chain of aliases and a cycle stop at its depth cap). A segment no module and no `use` (or two `use`s) binds, or a `use` // that leads outside the tree, names nothing. A module only a glob brings in is not followed (stated floor). bool rustAliasedModuleOf( std::uint32_t& crate, std::string& module, std::span segs, int depth ) const { for( const std::string_view seg : segs ) { if( std::string child = joinModule( module, seg ); rustModuleExists( crate, child ) ) { module = std::move( child ); continue; } NodeId inlineMod = kNoNode; std::uint32_t ownFile = 0; const auto mfs = rustModuleFiles( crate, module, inlineMod, ownFile ); const Level level = rustModuleLevel( inlineMod ); const Binding* alias = nullptr; std::size_t uses = 0; for( const std::uint32_t mf : mfs ) { forEachImport( mf, seg, [ & ]( const Binding& b ) { if( b.kind == LocalBindKind::TypeImport && levelAt( mf, b.startByte ) == level ) { ++uses; alias = &b; } } ); } if( uses != 1 || !rustModuleOf( alias->fileId, alias->startByte, alias->importedName, crate, module, depth + 1 ) ) { return false; } } return true; } // the ONE Rust class `cls` module `modPath` (seen from byte `at` of `f`) defines — or re-exports: a `use` of the name at // the module's own level (`pub use mdbook::MDBook;` in lib.rs) is followed to the module it names (depth-bounded), and // (RUST-PARAM-GLOB-REEXPORT) so is a glob there (`pub use engine_state::*;` in engine/mod.rs) NodeId rustClassAt( std::uint32_t f, std::uint32_t at, std::string_view modPath, std::string_view cls ) const { RustItemWalk walk; return rustItemOfPath( { f, at }, modPath, cls, walk ).id; } // One walk from a written path to the item it names: which kind of item is asked for, how deep the walk is, and the // questions it already asked. struct RustItemWalk { int depth = 0; // re-export hops taken so far (capped at 4: a cut walk names nothing) std::span fns; // empty: a class-like item; else the Rust free functions of the name asked for (graph.h's candidates) std::vector seen; // the "##" questions already asked: asked again (a cycle, a diamond), one brings nothing new std::uint32_t reasked = 0; // how often that happened: a step that found nothing below a re-asked question says nothing either way }; // What a module answers for an item name: the ONE in-tree item (kNoNode: outside the tree, ambiguous, an alias), and // whether the module has the name at all (`found` false: it declares, re-exports and globs in no such item). struct RustItem { NodeId id = kNoNode; bool found = false; }; mutable HashMap rustClassMemo; // rustModuleItem: "##" → what the module answers for a class name // where a path is written: a byte of a file struct RustSite { std::uint32_t file = 0; std::uint32_t at = 0; }; // a module's own level: the file level of its files, or an inline mod's body struct RustModuleRef { std::uint32_t crate = kNoCrate; const std::string& module; NodeId inlineMod = kNoNode; Level level; }; // is byte `pos` of `file` at module `m`'s own level (never inside a mod or fn it holds)? bool rustAtModuleLevel( const RustModuleRef& m, std::uint32_t file, std::uint32_t pos ) const { return m.inlineMod == kNoNode ? file < rust.crateOf.size() && rust.crateOf[ file ] == m.crate && rust.moduleOf[ file ] == m.module && levelAt( file, pos ).wholeFile() : file == ing.symbols[ m.inlineMod ].fileId && levelAt( file, pos ) == m.level; } // is symbol `c` an item of module `m`'s own level, never of a mod or fn in it? bool rustOwnsItem( const RustModuleRef& m, NodeId c ) const { const std::uint32_t cf = ing.symbols[ c ].fileId; return m.inlineMod == kNoNode ? cf < rust.crateOf.size() && rust.crateOf[ cf ] == m.crate && rust.moduleOf[ cf ] == m.module && enclosingSymbol( c ) == kNoNode : enclosingSymbol( c ) == m.inlineMod; } // the item `item` of the module `modPath` names at `site`, under a walk already begun (a re-export hop, a function lookup) RustItem rustItemOfPath( RustSite site, std::string_view modPath, std::string_view item, RustItemWalk& walk ) const { std::uint32_t crate = kNoCrate; std::string module; RustItem hit; if( walk.depth <= 4 && rustModuleOf( site.file, site.at, modPath, crate, module, 0 ) ) { hit.id = rustModuleItem( crate, module, item, walk, hit.found ); } return hit; } // RUST-PARAM-GLOB-REEXPORT: the ONE in-tree free function the `use` bindings of a bare call's name, in force at the call, reach // through the module tree and its re-exports (`use nu_engine::redirect_env;` over lib.rs's `pub use eval::{redirect_env};`), out // of `fns` (the Rust free functions of that name). kNoNode when no `use` binds the name there, one leads outside or nowhere, // two disagree, or a function nested in a fn body of the caller's file may shadow the binding: the call then resolves as before. NodeId rustUseBoundFn( const Reference& r, std::span fns ) const { const bool nestedNamesake = std::ranges::any_of( fns, [ & ]( NodeId c ) { const NodeId outer = ing.symbols[ c ].fileId == r.fileId ? enclosingSymbol( c ) : kNoNode; return outer != kNoNode && ing.symbols[ outer ].kind != SymKind::Other; // an item of a fn body: in scope there, over any `use` } ); Ballot bound; if( fns.empty() || nestedNamesake ) { return kNoNode; } forEachRustUseAt( r.fileId, r.startByte, r.calleeName, [ & ]( const Binding& b ) { const auto [ modPath, item ] = splitLast( b.importedName, "::" ); RustItemWalk walk{ 0, fns, {}, 0 }; bound.vote( modPath.empty() ? kNoNode : rustItemOfPath( { r.fileId, b.startByte }, modPath, item, walk ).id ); } ); return bound.verdict(); } // RUST-PARAM-GLOB-REEXPORT, on top of FE-A's verdict `kinds` for the call (graph.h FalseEdgeRules::decide, whose kindDecide has // already dropped what a bare call cannot name: a bare Rust path call never names a method). Where a `use` in force binds the // name, the ONE free function that `use` reaches is the only candidate left (`kept`, Narrow): `use nu_engine::redirect_env;` // over lib.rs's `pub use eval::{redirect_env};` is eval.rs's, never a private `eval_ir::redirect_env` of the same crate, which // Rule 3's included-file closure cannot tell apart. Any other call, a verdict that is no Keep / Narrow, a name a local of the // caller hides (`localOfCaller`, asked only for a bare Rust call), a `use` that decides nothing: `kinds`, unchanged. template Verdict rustBareNarrow( const Reference& r, Verdict kinds, std::span ids, rw::SmallVec& kept, LocalOfCaller&& localOfCaller ) const { const bool bare = callResultFamilyOf( r.lang ) == CallResultFamily::Rust && r.role == RefRole::Call && r.qualifier.empty() && r.recv == RecvKind::None && !r.memberCall && r.fromSymbol < ing.symbols.size(); if( !bare || ( kinds != Verdict::Keep && kinds != Verdict::Narrow ) || localOfCaller() ) { return kinds; } rw::SmallVec freeFns; for( const NodeId c : kinds == Verdict::Narrow ? std::span( kept.begin(), kept.end() ) : ids ) { if( ing.symbols[ c ].kind == SymKind::Function && ing.symbols[ c ].lang == r.lang ) { freeFns.push_back( c ); } } const NodeId bound = rustUseBoundFn( r, std::span( freeFns.begin(), freeFns.end() ) ); if( bound == kNoNode ) { return kinds; } kept.clear(); kept.push_back( bound ); return Verdict::Narrow; } // rustItemAt, asked once: a class asked from outside any walk (a `use` row, a glob row, a written path) is a function of // the layout alone, so each (module, name) is walked once (rustClassMemo: engine/mod.rs's twenty globs, asked per typed // parameter); and inside one walk a question asked again brings nothing new — a module's private `use` of the name often // leads back to the module that globs it (closure.rs `use crate::engine::EngineState;` under engine/mod.rs `pub use closure::*;`). NodeId rustModuleItem( std::uint32_t crate, const std::string& module, std::string_view cls, RustItemWalk& walk, bool& found ) const { const bool outermost = walk.seen.empty() && walk.fns.empty(); std::string asked = rustModuleKey( crate, module ); asked.append( 1, '#' ).append( cls ); if( const auto memo = rustClassMemo.find( asked ); outermost && memo != rustClassMemo.end() ) { found = memo->second.found; return memo->second.id; } found = false; if( std::ranges::find( walk.seen, asked ) != walk.seen.end() ) { ++walk.reasked; return kNoNode; } walk.seen.push_back( asked ); const NodeId item = rustItemAt( crate, module, cls, walk, found ); if( outermost ) { rustClassMemo.try_emplace( std::move( asked ), RustItem{ item, found } ); } return item; } // the item `cls` of module (crate, module): a class (or, on a function walk, a free function) declared at the module's own // level (a file module's file level, an inline mod's body), else a re-export there, else (RUST-PARAM-GLOB-REEXPORT) what the // globs there supply; an alias there names nothing. `found` false when the module has none. NodeId rustItemAt( std::uint32_t crate, const std::string& module, std::string_view cls, RustItemWalk& walk, bool& found ) const { const auto inl = rust.inlineMods.find( rustModuleKey( crate, module ) ); const NodeId inlineMod = inl == rust.inlineMods.end() ? kNoNode : inl->second; const RustModuleRef m{ crate, module, inlineMod, rustModuleLevel( inlineMod ) }; const auto atLevel = [ & ]( std::uint32_t file, std::uint32_t pos ) { return rustAtModuleLevel( m, file, pos ); }; const int depth = walk.depth; if( const RustItem own = rustDeclaredItem( m, cls, walk ); own.found ) { found = true; return own.id; } const auto files = rust.filesOf.find( rustModuleKey( crate, module ) ); const std::vector none; const std::vector& of = inlineMod != kNoNode ? none : files == rust.filesOf.end() ? none : files->second; ReexportPick pick; pick.walk = &walk; for( std::uint32_t mf : of ) // by reference: the layout's own list, never a copy { rustFollowReexports( mf, atLevel, cls, depth, pick ); } if( inlineMod != kNoNode ) { rustFollowReexports( ing.symbols[ inlineMod ].fileId, atLevel, cls, depth, pick ); } if( !pick.bound ) // a named `use` of the name shadows every glob of its level { rustGlobsSupply( pick, cls ); } found = found || pick.bound || pick.globbed; return pick.clash ? kNoNode : pick.one; } // rustItemAt's first step: the item module `m` declares at its own level under the name. On a function walk, the module's // own free functions of the name; a class of the name declared there (a tuple struct's constructor is a value too) decides // nothing when no function does. On a class walk, an alias of the name there names nothing. RustItem rustDeclaredItem( const RustModuleRef& m, std::string_view cls, const RustItemWalk& walk ) const { const auto owned = [ & ]( NodeId c ) { return rustOwnsItem( m, c ); }; NodeId one = kNoNode; const std::size_t classes = classesNamed( cls, CallResultFamily::Rust, owned, one ); if( !walk.fns.empty() ) { const std::size_t fns = static_cast( std::ranges::count_if( walk.fns, owned ) ); return { fns == 1 ? *std::ranges::find_if( walk.fns, owned ) : kNoNode, fns + classes > 0 }; } bool aliased = false; nameKey.assign( cls ); if( const auto aliases = aliasesByName.find( nameKey ); aliases != aliasesByName.end() ) { aliased = std::ranges::any_of( aliases->second, [ & ]( const Binding* b ) { return rustAtModuleLevel( m, b->fileId, b->startByte ); } ); // a Rust file's } return { classes == 1 && !aliased ? one : kNoNode, classes > 0 || aliased }; } // What the module-level `use … cls` bindings rustFollowReexports read name, across the module's files and its inline mod. struct ReexportPick { NodeId one = kNoNode; // the in-tree class the resolving bindings agree on bool bound = false; // some binding spells the name (it may resolve outside the tree) bool clash = false; // two bindings resolve to DIFFERENT in-tree classes: ambiguous, no class bool globbed = false; // rust-receivers: a glob at the module's level may bring the name in unseen (not followed) // RUST-PARAM-GLOB-REEXPORT: the walk these bindings are read under, and the globs at the module's level, which // rustGlobsSupply follows when no binding spells the name (`globbed` is then a glob it could not follow) RustItemWalk* walk = nullptr; std::vector globs; // one binding that spells the name, resolving to `c` (kNoNode: outside the tree, which carries no class) void take( NodeId c ) { bound = true; clash = clash || ( c != kNoNode && one != kNoNode && one != c ); one = one == kNoNode ? c : one; } }; // rustItemAt's re-export step for one file `mf` of the module: each `use … cls` at the module's own level (`atLevel`) names // the class its path reaches, and a glob there sets `globbed`. #610 (@soarkit): a binding that resolves to no in-tree class // (`#[cfg(feature = "x")] pub use external_crate::Config;`) carries no class, and two cfg-exclusive re-exports of ONE class // agree; only two bindings resolving to different in-tree classes are ambiguous. // RUST-PARAM-GLOB-REEXPORT: a glob there is kept in `pick.globs` (rustGlobsSupply follows it, and sets `globbed` only for one // it cannot follow); a binding whose path only leads back into this walk is a binding of what is being asked and says nothing. template void rustFollowReexports( std::uint32_t mf, const AtLevel& atLevel, std::string_view cls, int depth, ReexportPick& pick ) const { if( mf >= importsByFile.size() ) { return; } for( const Binding* b : importsByFile[ mf ] ) { if( b->kind != LocalBindKind::TypeImport || ( b->var != cls && b->var != "*" ) || !atLevel( mf, b->startByte ) ) { continue; } if( b->var == "*" ) { pick.globs.push_back( b ); continue; } const auto [ modPath, item ] = splitLast( b->importedName, "::" ); RustItemWalk& walk = *pick.walk; const std::uint32_t reaskedBefore = walk.reasked; walk.depth = depth + 1; const RustItem hit = modPath.empty() ? RustItem{} : rustItemOfPath( { mf, b->startByte }, modPath, item, walk ); walk.depth = depth; if( hit.found || walk.reasked == reaskedBefore ) { pick.take( hit.id ); } } } // RUST-PARAM-GLOB-REEXPORT: what the globs at a module's level supply for the item `cls` (`pub use engine_state::*;` in // engine/mod.rs), read into the pick when no binding spells the name. A glob of an in-tree module supplies what that module // declares or re-exports under the name (rustModuleItem, one hop deeper), and nothing when the module has no such item. A glob // the layout cannot place (an outside crate, an enum's variants, a cut walk) MAY supply the name unseen: `globbed`. So ONE // item is named only when every glob that can supply the name agrees on it; two same-named types behind two globs, an // ambiguous module below, or an in-tree glob beside one that cannot be followed, name nothing (`clash`). void rustGlobsSupply( ReexportPick& pick, std::string_view cls ) const { RustItemWalk& walk = *pick.walk; std::uint32_t gc = kNoCrate; std::string gm; for( const Binding* g : pick.globs ) { if( walk.depth >= 4 || !rustModuleOf( g->fileId, g->startByte, g->importedName, gc, gm, 0 ) ) { pick.globbed = true; continue; } bool supplies = false; ++walk.depth; const NodeId c = rustModuleItem( gc, gm, cls, walk, supplies ); --walk.depth; if( supplies ) { pick.take( c ); pick.clash = pick.clash || c == kNoNode; } } pick.clash = pick.clash || ( pick.globbed && pick.bound ); } // (L) a qualified Rust call whose qualifier is a module path reaching `target`'s own module (`model::load()`, // `crate::nest::holder()`, a `use`d `nest::holder()`): the evidence the canonical tier, keyed by type scopes, lacks bool rustQualifierReaches( const Reference& r, NodeId target ) const { std::uint32_t crate = kNoCrate; std::string module; if( callResultFamilyOf( r.lang ) != CallResultFamily::Rust || r.qualifier.empty() || !rustModuleOf( r.fileId, r.startByte, r.qualifier, crate, module, 0 ) ) { return false; } const std::uint32_t tf = ing.symbols[ target ].fileId; std::string targetModule; rustModuleAt( tf, ing.symbols[ target ].sigStartByte, targetModule ); return tf < rust.crateOf.size() && rust.crateOf[ tf ] == crate && targetModule == module; } // RULE3-MEMBER-GUARD: what written binding proves `target` for a Rust call Rule 3 narrowed to it, an allowlist. A bare call: a `use` // of the name written into the target's crate that does not provably leave the tree (the item it names in that crate is not compared), // or a glob `use` of the module holding the target. A qualified call: the qualifier, read whole from its written root // (model.h rustWrittenQualifierOf), names the module holding the target, or its last segment the target's own type (`owner`). "Holding" takes a module's descendants too // and a crate root takes its whole crate, because a `pub use` re-export places an item below the path written. Not proven, counted // as via="name": `Ok(..)`, `assert!(..)`, a name only a glob of an unrelated module is near, `oneshot::channel()`, `String::new()` (those two then read as outside the tree, external=; graph.h). bool rustRule3Proves( const Reference& r, NodeId target, std::string_view owner ) const { if( !rust.built ) { buildRustLayout(); } const std::uint32_t tf = ing.symbols[ target ].fileId; if( tf >= rust.crateOf.size() || r.fileId >= rust.crateOf.size() ) { return false; } std::string targetModule; rustModuleAt( tf, ing.symbols[ target ].sigStartByte, targetModule ); std::uint32_t crate = kNoCrate; std::string module; // The module layout knows a crate only by a lib.rs or main.rs: a crate with `[lib] path = "src/x.rs"` (all of zed's) has none. There the written root reads // against the package directory: `crate`/`self`/`super` the caller's own, any other root that directory's name (`-` as `_`). `use serde_json::json` names no tree directory. const auto packageOf = []( std::string_view path ) { return rustPackageDirOf( path ); }; const auto rootNamesTargetPackage = [ & ]( std::string_view path ) { const std::string_view root = path.substr( 0, path.find( "::" ) ); const std::string_view pkg = packageOf( rootRelPath( ing, tf ) ); if( root == "crate" || root == "self" || root == "super" ) { // only where the layout cannot see the caller's crate: where it can, a path it cannot follow (`self::f` through a `use … as f`) proves nothing return rust.crateOf[ r.fileId ] == kNoCrate && pkg == packageOf( rootRelPath( ing, r.fileId ) ); } const std::size_t slash = pkg.rfind( '/' ); const std::string_view leaf = slash == std::string_view::npos ? pkg : pkg.substr( slash + 1 ); return !leaf.empty() && leaf.size() == root.size() && std::ranges::equal( leaf, root, []( char a, char b ) { return ( a == '-' ? '_' : a ) == b; } ); }; const auto holdsTarget = [ & ]( std::string_view path, std::uint32_t at ) { if( !rustModuleOf( r.fileId, at, path, crate, module, 0 ) ) { return rootNamesTargetPackage( path ); } if( rust.crateOf[ tf ] != crate ) { return false; } return module.empty() || targetModule == module || ( targetModule.starts_with( module ) && std::string_view( targetModule ).substr( module.size() ).starts_with( "::" ) ); }; if( !r.qualifier.empty() ) { const std::string_view written = rustWrittenQualifierOf( r ); // from its root: `crate::a` of `crate::a::helper()` const std::size_t sep = written.rfind( "::" ); const std::string_view last = written.substr( sep == std::string::npos ? 0 : sep + 2 ); if( !owner.empty() && last == owner ) { return true; } bool aliased = false; // `use nu_protocol::Value as NuValue; NuValue::nothing()`: a `use` binds a ONE-segment qualifier only forEachRustUseAt( r.fileId, r.startByte, sep == std::string::npos ? last : std::string_view{}, [ & ]( const Binding& b ) { const std::size_t at = b.importedName.str().rfind( "::" ); aliased = aliased || ( !owner.empty() && std::string_view( b.importedName ).substr( at == std::string::npos ? 0 : at + 2 ) == owner ); } ); return aliased || holdsTarget( written, r.startByte ); } // a `use` of the name in file `f` whose module path is written into the target's crate and that does not provably leave the tree (`pub use // ext::helper` re-exported by the module named): an unknown root, a duplicate crate name or an outside crate proves nothing. WHICH item of // that crate it names is not compared with the target (card RUST-USE-TARGET): a second in-crate namesake the `use` reaches still proves it. const auto usesIntoTargetCrate = [ & ]( std::uint32_t f, const Binding& b ) { if( b.kind != LocalBindKind::TypeImport ) { return false; } const std::size_t at = b.importedName.str().rfind( "::" ); if( at == std::string::npos ) { return false; } const std::string_view modPath = std::string_view( b.importedName ).substr( 0, at ); if( rustPathProvablyOutside( f, b.startByte, b.importedName ) ) { return false; } return rustModuleOf( f, b.startByte, modPath, crate, module, 0 ) ? rust.crateOf[ tf ] == crate : rootNamesTargetPackage( modPath ); }; bool proven = false; forEachImport( r.fileId, r.calleeName, [ & ]( const Binding& b ) { proven = proven || usesIntoTargetCrate( r.fileId, b ); } ); // any level: `mod tests { use super::*; }` sees its parent's if( !proven ) { forEachImport( r.fileId, "*", [ & ]( const Binding& b ) { if( proven || b.kind != LocalBindKind::TypeImport ) { return; } proven = holdsTarget( b.importedName, b.startByte ); if( !proven && rustModuleOf( r.fileId, b.startByte, b.importedName, crate, module, 0 ) ) { // `use super::*` over a module that itself `use`s the name (a `mod tests` calling what its parent imports) const auto files = rust.filesOf.find( rustModuleKey( crate, module ) ); if( files != rust.filesOf.end() ) { for( const std::uint32_t mf : files->second ) { forEachImport( mf, r.calleeName, [ & ]( const Binding& used ) { proven = proven || usesIntoTargetCrate( mf, used ); } ); } } } } ); } return proven; } // fc1: does the Rust path `path` (a call's written qualifier, a `use`'s path) written at byte `at` of `f` PROVABLY lead out of // the tree — std / core / alloc, an external crate, an unknown root, the prelude, or an in-tree re-export of one? false // when it reaches an in-tree module or item, and whenever the walk cannot tell: two `use`s of the root, an in-tree glob // or an unparsed region of the file that may bring the name in, a depth cap. A file outside every crate's module tree // (a bench target) resolves no module: only a std / core / alloc root (by a `use` too) leads out there. bool rustPathOutside( std::uint32_t f, std::uint32_t at, std::string_view path, int depth = 0 ) const { if( !rust.built ) { buildRustLayout(); } if( depth > 4 ) { pathCut = true; // a cut, not an answer: a caller that would PROVE from "stays in the tree" reads this flag return false; } if( f >= rust.crateOf.size() || path.empty() ) { return false; } const auto [ modPath, item ] = splitLast( path, "::" ); std::uint32_t crate = kNoCrate; std::string module; if( modPath.empty() || rust.crateOf[ f ] == kNoCrate || !rustModuleOf( f, at, modPath, crate, module, 0 ) ) { return rustRootOutside( f, at, modPath.empty() ? item : modPath.substr( 0, modPath.find( "::" ) ), depth ); } return rustReexportOutside( crate, module, item, depth ); } // rustPathOutside, as a verdict: the path provably leaves the tree (an `impl other_crate::Renderer for X` names ANOTHER crate's // trait, not the in-tree one of that name). A cut walk, an empty path or a path into the tree is false. bool rustPathProvablyOutside( std::uint32_t f, std::uint32_t at, std::string_view path ) const { pathCut = false; return rustPathOutside( f, at, path ) && !pathCut; } // RULE3-MEMBER-GUARD: does the root a written path starts from (its head, or where the head's `use` begins) name a package directory of the tree? A crate with // `[lib] path` has no lib.rs for the layout to know it by, so rustPathOutside reads a `use agent_settings::AgentSettings` from a crate it does know as an // unknown, outside root; naming a package directory of the tree, the root is not provably outside. bool rustRootNamesTreePackage( std::uint32_t f, std::uint32_t at, std::string_view path ) const { if( !rust.built ) { buildRustLayout(); } const std::string head( path.substr( 0, path.find( "::" ) ) ); std::string root = head; forEachRustUseAt( f, at, head, [ & ]( const Binding& b ) { root = b.importedName.substr( 0, b.importedName.str().find( "::" ) ); } ); return rust.packageNames.contains( root ); } // the files holding module (crate, module)'s own level: a file module's files, or (`inlineMod` set) the one file of an // inline `mod`, kept in `ownFile`; empty when no such module std::span rustModuleFiles( std::uint32_t crate, const std::string& module, NodeId& inlineMod, std::uint32_t& ownFile ) const { const auto inl = rust.inlineMods.find( rustModuleKey( crate, module ) ); inlineMod = inl == rust.inlineMods.end() ? kNoNode : inl->second; if( inlineMod != kNoNode ) { ownFile = ing.symbols[ inlineMod ].fileId; return { &ownFile, 1 }; } const auto files = rust.filesOf.find( rustModuleKey( crate, module ) ); return files == rust.filesOf.end() ? std::span{} : std::span( files->second ); } // rustPathOutside's in-tree module step: an item of module (crate, module) — a file module, or an inline `mod` (its // body) — leads out only through a named re-export at the module's own level (`pub use std::ffi::OsString;`), each // followed; an item declared there, or no such `use` (a glob, an unparsed region), never does bool rustReexportOutside( std::uint32_t crate, const std::string& module, std::string_view item, int depth ) const { NodeId inlineMod = kNoNode; std::uint32_t ownFile = 0; const auto mfs = rustModuleFiles( crate, module, inlineMod, ownFile ); const Level level = rustModuleLevel( inlineMod ); bool any = false; bool out = true; for( std::uint32_t mf : mfs ) { NodeId one = kNoNode; if( classesNamed( item, CallResultFamily::Rust, [ & ]( NodeId c ) { return ing.symbols[ c ].fileId == mf && enclosingSymbol( c ) == inlineMod; }, one ) > 0 ) { return false; } forEachImport( mf, item, [ & ]( const Binding& b ) { if( b.kind == LocalBindKind::TypeImport && levelAt( mf, b.startByte ) == level ) { any = true; out = out && rustPathOutside( mf, b.startByte, b.importedName, depth + 1 ); } } ); } return any && out; } // rustPathOutside's root step: the first segment `seg` of a path (or a bare type name) at byte `at` of `f` bool rustRootOutside( std::uint32_t f, std::uint32_t at, std::string_view seg, int depth ) const { if( seg == "crate" || seg == "self" || seg == "super" || seg == "Self" || rust.crateByName.contains( std::string( seg ) ) ) { return false; } bool any = false; bool out = true; // every `use` of the root in force (cfg-gated duplicates) leads out, or the walk keeps the row forEachRustUseAt( f, at, seg, [ & ]( const Binding& b ) { any = true; out = out && rustPathOutside( f, b.startByte, b.importedName, depth + 1 ); } ); if( any ) { return out; } std::string module; rustModuleAt( f, at, module ); NodeId one = kNoNode; const bool inTree = rust.crateOf[ f ] != kNoCrate; if( ( inTree && rustModuleExists( rust.crateOf[ f ], joinModule( module, seg ) ) ) || classesNamed( seg, CallResultFamily::Rust, [ & ]( NodeId c ) { return ing.symbols[ c ].fileId == f; }, one ) > 0 ) { return false; // a child module, or an item of this file } bool mayBring = rustGlobMayBring( f, at, seg, depth ); // a glob in force there, or an unparsed region of this file forEachImport( f, "!", [ & ]( const Binding& b ) { mayBring = mayBring || bindsWithoutTarget( b ); } ); constexpr std::string_view kStdRoots[] = { "std", "core", "alloc" }; // the sysroot crates every target sees return !mayBring && ( inTree || std::ranges::find( kStdRoots, seg ) != std::end( kStdRoots ) ); } // fc1 fix 1: may a glob `use` in force at byte `at` of `f` — one at a level of its chain (a fn body, then the module it // sits in; an outer module's globs never reach an inline `mod`) — bring the name `seg`? Only an in-tree glob whose // target module declares or re-exports `seg` in-tree (rustModuleMayBring); `mod tests { use super::*; }` never brings `std` struct GlobWalk { int depth; // the glob chain's stack bound int base; // the depth of the rustPathOutside walk this query runs under (a `use` it follows starts one deeper, so nesting stays bounded) std::vector seen; // fc1 fix 2: the (crate, module) keys this query already entered — a cycle brings nothing new }; bool rustGlobMayBring( std::uint32_t f, std::uint32_t at, std::string_view seg, int depth ) const { GlobWalk walk{ 0, depth, {} }; bool may = false; forEachRustScopeAt( f, at, [ & ]( const Level& lv ) { forEachImport( f, "*", [ & ]( const Binding& b ) { may = may || ( levelAt( f, b.startByte ) == lv && rustGlobBrings( f, b, seg, walk ) ); } ); return may; } ); return may; } // does the glob row `b` of file `f` — an in-tree one — bring `seg` (rustModuleMayBring of its target)? bool rustGlobBrings( std::uint32_t f, const Binding& b, std::string_view seg, GlobWalk& walk ) const { std::uint32_t gc = kNoCrate; std::string gm; if( b.kind != LocalBindKind::TypeImport || !rustModuleOf( f, b.startByte, b.importedName, gc, gm, 0 ) ) { return false; } ++walk.depth; const bool brings = rustModuleMayBring( gc, gm, seg, walk ); --walk.depth; return brings; } // fc1 fix 3: does a named `use` of `seg` at `level` of file `mf` bring an in-tree binding (one that does not lead out)? // `named` is set when the level has one at all; a walk cut at rustPathOutside's depth cap proves nothing, so it is hedged bool rustNamedUsesBring( std::uint32_t mf, const Level& level, std::string_view seg, const GlobWalk& walk, bool& named ) const { bool brings = false; const bool outer = pathCut; // a cut already taken by the enclosing walk (an earlier sibling glob) must survive this probe (CR #434) bool cut = false; forEachImport( mf, seg, [ & ]( const Binding& b ) { if( b.kind == LocalBindKind::TypeImport && levelAt( mf, b.startByte ) == level ) { named = true; pathCut = false; const bool out = rustPathOutside( mf, b.startByte, b.importedName, walk.base + 1 ); brings = brings || ( !out && !pathCut ); cut = cut || pathCut; // a later `use` of the name must not clear an earlier one's cut either } } ); pathCut = outer || cut; return brings; } // does module (crate, module) declare, or re-export from the tree, an item `seg` a glob of it brings — a child module, a // class or a `use` of the name at its own level that does not lead out (fc1 fix 2: a `use` of std's name there brings std's // binding, which is what the call sees; a private one reaches a child module's `super::*`), or a glob there whose target // does? fc1 fix 3: a named `use` of the name at a level shadows that level's globs (Rust's rule), so the named uses decide // alone and the globs are consulted only when there is none; a `use` whose walk was cut at rustPathOutside's depth cap does // not count as in-tree. Each module is entered once per query (`seen`: a glob cycle terminates with the true answer); the // depth cap is only a stack bound and answers "brings nothing" — the row is hedged, never proven onto an in-tree type bool rustModuleMayBring( std::uint32_t crate, const std::string& module, std::string_view seg, GlobWalk& walk ) const { if( walk.depth > 32 ) { return false; } const std::string key = rustModuleKey( crate, module ); if( std::ranges::find( walk.seen, key ) != walk.seen.end() ) { return false; } walk.seen.push_back( key ); if( rustModuleExists( crate, joinModule( module, seg ) ) ) { return true; } NodeId inlineMod = kNoNode; std::uint32_t ownFile = 0; const auto mfs = rustModuleFiles( crate, module, inlineMod, ownFile ); const Level level = rustModuleLevel( inlineMod ); bool may = false; for( std::uint32_t mf : mfs ) { NodeId one = kNoNode; may = may || classesNamed( seg, CallResultFamily::Rust, [ & ]( NodeId c ) { return ing.symbols[ c ].fileId == mf && enclosingSymbol( c ) == inlineMod; }, one ) > 0; bool named = false; // fc1 fix 3: a named `use` of `seg` at this level shadows the level's globs (Rust's rule) and decides alone may = rustNamedUsesBring( mf, level, seg, walk, named ) || may; if( !named ) { forEachImport( mf, "*", [ & ]( const Binding& b ) { may = may || ( levelAt( mf, b.startByte ) == level && rustGlobBrings( mf, b, seg, walk ) ); } ); } } return may; } // `a::b::C` → ( `a::b`, `C` ); `C` → ( "", `C` ) — the last segment is namesplit::afterLast's static std::pair splitLast( std::string_view path, std::string_view sep ) noexcept { const std::size_t at = path.rfind( sep ); return { at == std::string_view::npos ? std::string_view{} : path.substr( 0, at ), namesplit::afterLast( path, sep ) }; } // Rust (fix round 3: bareClassAt's rows): a bare name resolves at the callee's own level — its fn bodies, then its // module (a file, or an inline `mod`: a fresh scope, never the file's) — items, aliases and `use`s there first, then // the level's globs; a written path is relative to the module the callee sits in. NodeId rustResultClass( std::uint32_t fileId, std::uint32_t at, std::string_view whole, std::string_view cls ) const { if( !whole.empty() ) { return rustClassAt( fileId, at, splitLast( whole, "::" ).first, cls ); } if( !rust.built ) { buildRustLayout(); } return bareClassAt( CallResultFamily::Rust, fileId, at, cls ); } // C++: the ONLY in-tree class named `cls` — none when two are, or (fix round 5) when a declaration only a macro can have // written (`class API cls {…}`) spells the name: the tree holds a class of it the index does not record NodeId onlyCppClass( std::string_view cls ) const { const std::string key( cls ); const auto it = classIds->classesByName.find( key ); const auto rec = aliasesByName.find( key ); // the "unrecorded" rows ride the alias index (no span: no scope row) const bool unrecorded = rec != aliasesByName.end() && std::ranges::any_of( rec->second, []( const Binding* b ) { return b->typeName == kTypeBindUnrecorded; } ); return it == classIds->classesByName.end() || it->second.size() != 1 || unrecorded ? kNoNode : it->second[ 0 ]; } // C++ / ObjC: Rule 2 keys a member by its class's NAME, so the class must be the ONLY in-tree class definition of that // name; a qualified result (`ns::T`) must also name its scope — an enclosing class of that name, the namespace path the // class is declared in, or a namespace its file declares non-members in — so an outside `ext::Config` never names the // in-tree `cfg::Config`. An unqualified result is cppUnqualifiedClass's. NodeId cppResultClass( std::string_view whole, std::string_view cls ) const { if( classIds == nullptr ) { return kNoNode; } const NodeId c = onlyCppClass( cls ); if( c == kNoNode ) { return kNoNode; } const auto [ scope, last ] = splitLast( whole, "::" ); if( last != cls || scope.empty() ) { return kNoNode; } const NodeId outer = c < classIds->enclosingClass.size() ? classIds->enclosingClass[ c ] : kNoNode; if( outer != kNoNode && ing.symbols[ outer ].name == splitLast( scope, "::" ).second ) { return c; } // (fix round 2) the class's own namespace path (its file's Namespace records) ends with the written scope, // segment-aligned: `net::wire::Frame` or `wire::Frame` for a Frame declared in namespace net::wire std::vector classPath; std::vector written; namespacePathAt( ing.symbols[ c ].fileId, ing.symbols[ c ].sigStartByte, classPath ); appendSegments( scope, written ); if( outer == kNoNode && written.size() <= classPath.size() && std::equal( written.rbegin(), written.rend(), classPath.rbegin() ) ) { return c; } std::string nsKey; buildShadowKey( nsKey, ing.symbols[ c ].fileId, scope ); return classIds->fileNamespaces.contains( nsKey ) ? c : kNoNode; } // `a::b::c` → a, b, c appended to `path` static void appendSegments( std::string_view qualified, std::vector& path ) { for( std::string_view rest = qualified;; ) { const std::size_t sep = rest.find( "::" ); path.push_back( rest.substr( 0, sep ) ); if( sep == std::string_view::npos ) { return; } rest.remove_prefix( sep + 2 ); } } // C++ (fix round 2): the namespace path at byte `at` of file `f` — the Namespace records holding it, outermost first, // each name split at `::` (`namespace a::b` is two) void namespacePathAt( std::uint32_t f, std::uint32_t at, std::vector& path ) const { path.clear(); for( const Binding* ns : namespacesOf( f ) ) { if( ns->spanStart <= at && at < ns->spanEnd ) { appendSegments( ns->var, path ); } } } // the namespace- and file-scope usings in force at byte `at` of file `f`: the file's own, declared before `at` in a scope // that holds it, and those of every in-tree header `f` includes (transitively) whose namespace path leads to `at`'s // (`calleePath`) — a header's `namespace cfg { using ext::Config; }` is in force in `namespace cfg` of the includer template void forEachCppUsing( std::uint32_t f, std::uint32_t at, const std::vector& calleePath, Fn&& fn ) const { const auto rowsOf = [ & ]( std::uint32_t file, bool own ) { if( file >= importsByFile.size() ) { return; } for( const Binding* b : importsByFile[ file ] ) { if( !isCppScopeRow( *b ) ) { continue; } if( own && !( b->startByte < at && b->spanStart <= at && at < b->spanEnd ) ) { continue; // declared after the callee, or in a namespace that does not hold it } if( !own && innermostHolding( file, b->startByte, ¬Module ) != kNoNode ) { continue; // a class-scope alias (fix round 3) or a block-scope row (fix round 4) is in force in its own class / body only } if( !own ) { namespacePathAt( file, b->startByte, usingPath ); if( std::mismatch( usingPath.begin(), usingPath.end(), calleePath.begin(), calleePath.end() ).first != usingPath.end() ) { continue; } } fn( *b ); } }; rowsOf( f, true ); if( fileIncludes == nullptr ) { return; } if( fileIncludes->cardinalityHint( f ) < cppUsingFiles.size() ) { fileIncludes->forEach( f, [ & ]( const std::uint32_t h ) { if( std::binary_search( cppUsingFiles.begin(), cppUsingFiles.end(), h ) ) { rowsOf( h, false ); } } ); return; } for( std::uint32_t h : cppUsingFiles ) { if( fileIncludes->contains( f, h ) ) { rowsOf( h, false ); } } } // C++ (fix round 2): an UNQUALIFIED result `T` declared at byte `at` of file `f` names the ONLY in-tree class `T` only // where C++'s own lookup reaches it: a using-declaration of `T` in force there decides (its path resolves as a written // `ns::T` would — an outside `using ext::T;` names nothing); else a nested or local class must enclose the declaration // (visibleAt), and a namespace-scope class's namespace must enclose the declaration's own namespace or be named by a // using-directive in force there. An outside using-directive cannot make the in-tree class wrong — `T` would then be // ambiguous — so it never needs a refusal of its own. Fix round 4: then a binding of `T` the index keeps no class for // (cppHiddenAt) may still hide the class. NodeId cppUnqualifiedClass( std::uint32_t f, std::uint32_t at, std::string_view cls ) const { if( classIds == nullptr ) { return kNoNode; } const NodeId c = onlyCppClass( cls ); if( c == kNoNode ) { return kNoNode; } // fix round 3: a member type a base of an enclosing class declares (a nested class, a member alias) is in scope // there and is not followed — the spelling names nothing std::vector chain; chainAt( f, at, chain ); for( const Level& lv : chain ) { if( lv.sym != kNoNode && classKind( ing.symbols[ lv.sym ].kind ) && inheritsMemberType( lv.sym, cls, CallResultFamily::Cpp ) ) { return kNoNode; } } std::vector calleePath; namespacePathAt( f, at, calleePath ); const CppReach reach = cppReach( f, at, c, calleePath ); return reach == CppReach::None || cppHiddenAt( f, at, c, calleePath, reach ) ? kNoNode : c; } // how the class `c` (the only in-tree class of its name) is reached from byte `at` of file `f` (cppUnqualifiedClass): through a // using-declaration of `cls` in force, as a nested / local class enclosing `at`, from a namespace leading the callee's, // through a using-directive — or not at all enum class CppReach : std::uint8_t { None, Declared, Nested, Leads, Directive }; CppReach cppReach( std::uint32_t f, std::uint32_t at, NodeId c, const std::vector& calleePath ) const { const std::string_view cls = ing.symbols[ c ].name; bool declared = false; NodeId byDecl = kNoNode; forEachCppUsing( f, at, calleePath, [ & ]( const Binding& b ) { if( b.var == cls && !bindsWithoutTarget( b ) ) // a using-declaration resolves as a written `ns::T`; an alias (fix round 3) names nothing { const NodeId named = b.kind == LocalBindKind::TypeAlias ? kNoNode : cppResultClass( b.importedName, cls ); byDecl = declared && named != byDecl ? kNoNode : named; declared = true; } } ); if( declared ) { return byDecl == c ? CppReach::Declared : CppReach::None; } if( enclosingSymbol( c ) != kNoNode ) { return visibleAt( c, f, at ) ? CppReach::Nested : CppReach::None; } std::vector classPath; namespacePathAt( ing.symbols[ c ].fileId, ing.symbols[ c ].sigStartByte, classPath ); if( std::mismatch( classPath.begin(), classPath.end(), calleePath.begin(), calleePath.end() ).first == classPath.end() ) // it leads the callee's { return CppReach::Leads; } bool named = false; forEachCppUsing( f, at, calleePath, [ & ]( const Binding& b ) { if( b.var != "*" || named ) { return; } // `using namespace a::b;` names the class's path itself, or its tail relative to a namespace enclosing the callee std::vector dir; appendSegments( b.importedName, dir ); if( dir.size() <= classPath.size() && std::equal( dir.rbegin(), dir.rend(), classPath.rbegin() ) ) { const std::vector head( classPath.begin(), classPath.end() - std::ptrdiff_t( dir.size() ) ); named = std::mismatch( head.begin(), head.end(), calleePath.begin(), calleePath.end() ).first == head.end(); } } ); return named ? CppReach::Directive : CppReach::None; } // fix round 4: is the class `c` that `reach` found HIDDEN at byte `at` of file `f` by a binding of its name the index keeps // no class for, in force there (forEachCppUsing's scope rule): a union, a forward declaration of `cls`, or a macro / parse // error, which may declare any name. Such a binding hides `c` when it is in an inner scope: a class or function body (unless it is a forward // declaration of `c` itself, inside it), or — for a namespace-scope `c` that leads the callee's namespace — a namespace // deeper than `c`'s own. A forward declaration in `c`'s own namespace declares `c`; a binding outside the scope `c` is // nested in is hidden BY `c`. A class reached through a using-declaration or a using-directive is hidden by any such // binding in force (C++ puts a directive's names at a namespace this reader does not compute). bool cppHiddenAt( std::uint32_t f, std::uint32_t at, NodeId c, const std::vector& calleePath, CppReach reach ) const { const Symbol& cs = ing.symbols[ c ]; const std::string_view cls = cs.name; std::vector classPath; std::vector rowPath; namespacePathAt( cs.fileId, cs.sigStartByte, classPath ); bool hidden = false; forEachCppUsing( f, at, calleePath, [ & ]( const Binding& b ) { if( hidden || !bindsWithoutTarget( b ) || ( b.typeName != kTypeBindUnparsed && b.var != cls ) ) // an unparsed region may declare any name { return; } const bool forward = b.typeName == kTypeBindForward; if( innermostHolding( b.fileId, b.startByte, ¬Module ) != kNoNode ) // a class or function body (own file only) { hidden = !( forward && b.fileId == cs.fileId && b.spanStart <= cs.sigStartByte && cs.sigStartByte < b.spanEnd ); return; } namespacePathAt( b.fileId, b.startByte, rowPath ); switch( reach ) { case CppReach::Nested: return; // `c` is nested in a class or body: deeper than any namespace case CppReach::Leads: hidden = rowPath.size() > classPath.size(); return; // both lead the callee's: longer is deeper default: hidden = !( forward && rowPath == classPath ); return; } } ); return hidden; } // C++ (fix round 3): does the first segment of a qualified result (`lib` in `lib::T`) name a namespace alias (or any // alias) in force at byte `at` of `f` — `namespace lib = ext;` makes `lib::T` ext's, never an in-tree namespace lib's bool cppQualifierAliased( std::uint32_t f, std::uint32_t at, std::string_view whole ) const { const std::string_view head = whole.substr( 0, whole.find( "::" ) ); std::vector calleePath; namespacePathAt( f, at, calleePath ); bool aliased = false; forEachCppUsing( f, at, calleePath, [ & ]( const Binding& b ) { aliased = aliased || ( b.kind == LocalBindKind::TypeAlias && b.var == head ); } ); return aliased; } // the class a ReturnType record's written type resolves to in its own (the callee's) file — kNoNode for none or several NodeId resultClassOf( const Binding& rt, Lang lang ) const { switch( callResultFamilyOf( lang ) ) { case CallResultFamily::Go: return goResultClass( rt.fileId, rt.startByte, rt.importedName, rt.typeName ); case CallResultFamily::Jvm: return jvmResultClass( rt.fileId, rt.startByte, rt.importedName, rt.typeName ); case CallResultFamily::TypeScript: return tsResultClass( rt.fileId, rt.startByte, rt.importedName, rt.typeName ); case CallResultFamily::Rust: return rustResultClass( rt.fileId, rt.startByte, rt.importedName, rt.typeName ); case CallResultFamily::Cpp: return rt.importedName.empty() ? cppUnqualifiedClass( rt.fileId, rt.startByte, rt.typeName ) : cppQualifierAliased( rt.fileId, rt.startByte, rt.importedName ) ? kNoNode : cppResultClass( rt.importedName, rt.typeName ); default: return kNoNode; } } // lane L6: the class (or interface) a bare type NAME spelled at byte `at` of file `fileId` resolves to in language `lang`'s // scopes — resultClassOf's rows for a written, unqualified type; kNoNode for none, several, or a family with no rows NodeId classAtSite( Lang lang, std::uint32_t fileId, std::uint32_t at, std::string_view cls ) const { switch( callResultFamilyOf( lang ) ) { case CallResultFamily::Go: return goResultClass( fileId, at, {}, cls ); case CallResultFamily::Jvm: return jvmResultClass( fileId, at, {}, cls ); case CallResultFamily::TypeScript: return tsResultClass( fileId, at, {}, cls ); case CallResultFamily::Rust: return rustResultClass( fileId, at, {}, cls ); default: return kNoNode; } } // the in-tree class-likes of `cls`'s language sharing its name (cls included) std::size_t sameNamedClasses( NodeId cls ) const { if( standsForDeclLessType( cls ) ) { return 0; // a witness is no class definition: its type has no bases or fields the tree can read by name } NodeId one = kNoNode; return classesNamed( ing.symbols[ cls ].name, callResultFamilyOf( ing.symbols[ cls ].lang ), []( NodeId ) { return true; }, one ); } }; struct ReceiverEvidence { static constexpr std::size_t kWalkCap = 64; // classes visited per base walk; deterministic (sorted chaUp) const IngestResult& ing; const HashMap>& chaUp; // class name → its direct base names (sorted) const HashMap& classNames; // every in-repo class-like name std::vector ownerClass; // per symbol: the class that owns it, "" none std::vector staticMember; // per symbol: 1 = a JS/TS `static` member (the CLASS side) HashMap> methodsByType; // "Class::name" → its callables HashMap> abstractByType; // "Class::name" → its BODYLESS callables (the contract a call dispatches through) HashMap abstractNames; // every name some class declares without a body (the gate of the two walks below) HashMap memberType; // "Class#field" → field class ("" = tombstone) HashMap memberTypeClass; // lane overload-split: "Class#field" → the ONE class every record of it resolved to (kNoNode = disagree; only qualified fields have a row) HashMap memberClass; // rust-receivers: "#field" → the ONE class its written type resolved to (kNoNode = unknown) HashMap memberIface; // lane L6: "#field" → the trait a `Box` field dispatches through (kNoNode = disagree) HashMap> embeds; // "Class" → its other bases: Go embedded classes (promotion) // lane std-namesake: a Rust struct field WRITTEN as a standard type — "#field" → the type's spine (ingest_binds.h // rustStdSpine) and the file that declares it (the spine's names are proven there). Only a field with ONE declaration: build() // drops an entry a second declaration of the field shares (a `#[cfg]` twin may be written as an in-tree type). struct RustStdField { rw::InternedText spine; std::uint32_t fileId = 0; std::uint32_t decls = 0; // the MemberType records of this key, counted once every record is in }; HashMap memberStd; mutable HashMap rustStdSpineMemo; // "#spine" → the proven final type name ("" unproven) mutable HashMap rustStdNamesakeMemo; // type name → are its in-tree namesakes all std aliases mutable HashMap rustStdOwnerMemo; // owner name → may a std receiver reach its methods mutable std::vector rustForeignGlob; // fileId → 0 unread, 1 no foreign glob import, 2 one HashMap nameAlias; // "#local" → the class name it imports // FE-B (review B4): one binding of a local name — the class it names ("" = unknown: it hides an outer binding of the // name and proves nothing) and the bytes it is visible in. end == 0: a record with no span (a Python name, a reassignment, // a base pass Type record): somewhere in its definition, extent unknown. K1a LOCALTYPE-PACK: six 4 B fields, 24 B (the two // texts were std::string, 64 B a fact); ~600 K facts on cockroach and vscode are live at buildGraph's resolve-loop peak. struct LocalFact { std::uint32_t start = 0; std::uint32_t end = 0; rw::InternedText type; // "" = a tombstone NodeId cls = kNoNode; // (L) fix round 1: the ONE in-tree class `type` resolved to (kNoNode: the name alone); Go: or the witness of a type the tree declares no class for (CallResultTypes::goDeclLessType) NodeId iface = kNoNode; // lane L6: a binding typed only as SOME implementor of this trait (type stays "") rw::InternedText bound; // lane L6: a generic bound's text (`R: Renderer`), "" otherwise. Lane std-namesake: on a // TOMBSTONE with no iface (type "", cls and iface kNoNode) the SPINE of the standard type // the binding is written as (ingest_binds.h rustStdSpine; rustStdWrittenReceiver reads it) bool operator==( const LocalFact& ) const = default; }; static_assert( sizeof( LocalFact ) == 24, "K1a: a local fact is six 4 B fields" ); // ( fromSymbol scope, var ) → its bindings in record order: a CSR behind a packed u64 key (K1a LOCALTYPE-PACK; it was a // HashMap#var", std::vector>, 107 MiB on cockroach). Lookup-only: build() seals it. rw::IdKeyedCsr localType; HashMap> methodAlias; // "#var" → ( object var, method ) HashMap moduleAlias; // "#name" → module as written ("" = tombstone) std::vector> fnsByFile; // fileId → functions/methods sorted by start (enclosing walk) std::vector> classesByFile; // fileId → class-like symbols sorted by start mutable std::string key; mutable std::vector frontier; mutable rw::SmallVec found; bool active = false; const HashMap* localNames = nullptr; // graph.h FieldNarrowTables::localNameSet const GoPackagePaths* goPackages = nullptr; // graph.h FalseEdgeRules::goPackages const HashMap* qualifierVerdicts = nullptr; // graph.h buildQualifierVerdicts (h1-annot) mutable HashMap namespaceNames; // every Namespace record's name and its roots, on first use mutable bool namespaceNamesBuilt = false; std::vector> operatorResult; // OperatorResult methods → "self" / their class, sorted (h1-annot) std::vector augDropped; // AugAssign records that dropped their name's class: // graph.h tombstones Rule 2's varType entry too HashMap callResultDecls; // "#var" → its CallResult records (typeCallResult) CallResultTypes types; // (L) fix round 1: a declared result type's ONE class ReceiverEvidence( const IngestResult& i, const HashMap>& up, const HashMap& classes ) : ing( i ), chaUp( up ), classNames( classes ), types( i ) {} static bool classLike( SymKind k ) noexcept { return CallResultTypes::classKind( k ); } static bool callableKind( SymKind k ) noexcept { return k == SymKind::Method || k == SymKind::Function; } const std::string& keyOf( std::uint32_t id, char sep, std::string_view name ) const { key.clear(); key.append( std::to_string( id ) ); key.push_back( sep ); key.append( name ); return key; } const std::string& typeKey( std::string_view type, std::string_view sep, std::string_view name ) const { key.assign( type ); key.append( sep ); key.append( name ); return key; } // ── build ───────────────────────────────────────────────────────────────────────────────────────────────────────── static void tombstoneInsert( HashMap& m, const std::string& k, std::string_view v ) { const auto [ it, fresh ] = m.try_emplace( k, std::string( v ) ); if( !fresh && it->second != v ) { it->second.clear(); // two different classes for one name: decide nothing } } // a binding's fact under ( scope, b.var ): its own written type void addLocalFact( NodeId scope, const Binding& b ) { addTypedFact( scope, b, b.typeName, kNoNode ); } // the same fact naming `type` instead of the binding's own (a qualified written type refused: ""), and the one class it // resolved to (kNoNode: the name alone). Staged: build() seals the table, which keeps the first of equal facts of one name // (the old "push unless present"). void addTypedFact( NodeId scope, const Binding& b, std::string_view type, NodeId cls ) { LocalFact f = factOf( b, cls ); f.type.assign( type ); localType.addUnique( scope, b.var, f ); } // the fact a binding states over its span ({0,0}: no span), naming class `cls` (its type text set by the caller) static LocalFact factOf( const Binding& b, NodeId cls ) { const bool spanned = b.spanEnd > b.spanStart; LocalFact f; f.start = spanned ? b.spanStart : 0u; f.end = spanned ? b.spanEnd : 0u; f.cls = cls; return f; } void buildOwners() { const std::size_t N = ing.symbols.size(); ownerClass.assign( N, {} ); // the classes of each file by start; a symbol's owner is the innermost class whose span holds it classesByFile.assign( ing.files.size(), {} ); fnsByFile.assign( ing.files.size(), {} ); for( const Symbol& s : ing.symbols ) { if( s.fileId >= ing.files.size() ) { continue; } if( classLike( s.kind ) ) { classesByFile[ s.fileId ].push_back( s.id ); } if( classLike( s.kind ) || s.kind == SymKind::NamedType ) { types.noteClass( s ); // a Go `type N int` has methods too: a result or field type may name it } if( callableKind( s.kind ) ) { fnsByFile[ s.fileId ].push_back( s.id ); } } const auto byStart = [ & ]( NodeId a, NodeId b ) { return ing.symbols[ a ].sigStartByte != ing.symbols[ b ].sigStartByte ? ing.symbols[ a ].sigStartByte < ing.symbols[ b ].sigStartByte : a < b; }; for( std::vector& v : classesByFile ) { std::sort( v.begin(), v.end(), byStart ); } for( std::vector& v : fnsByFile ) { std::sort( v.begin(), v.end(), byStart ); } for( const Symbol& s : ing.symbols ) { if( !s.scope.empty() ) { ownerClass[ s.id ] = s.scope; // the extractor's own scope (Python, C++, Kotlin, Ruby, JS prototype members) continue; } if( s.fileId >= ing.files.size() || classLike( s.kind ) ) { continue; } if( const NodeId best = classAt( s.fileId, s.sigStartByte, s.endByte, s.id ); best != kNoNode ) { ownerClass[ s.id ] = ing.symbols[ best ].name; } } // Go spells a method's class only on its receiver: the RecvType record that sets isFromAssignment for( const Binding& b : ing.bindings ) { if( b.kind == LocalBindKind::RecvType && b.isFromAssignment && b.fromSymbol < N && !b.typeName.empty() ) { ownerClass[ b.fromSymbol ] = b.typeName; if( callResultFamilyOf( ing.symbols[ b.fromSymbol ].lang ) == CallResultFamily::Go && callableKind( ing.symbols[ b.fromSymbol ].kind ) ) { types.noteGoReceiver( b.typeName, b.fromSymbol ); } } } ENSURES( ownerClass.size() == N && fnsByFile.size() == ing.files.size() && classesByFile.size() == ing.files.size(), "one owner per symbol, one sorted list per file" ); } // the innermost class-like symbol of `fileId` whose span holds [start, end) (never `self`); kNoNode when none NodeId classAt( std::uint32_t fileId, std::uint32_t start, std::uint32_t end, NodeId self = kNoNode ) const { NodeId best = kNoNode; if( fileId >= classesByFile.size() ) { return best; } for( NodeId c : classesByFile[ fileId ] ) { const Symbol& cs = ing.symbols[ c ]; if( cs.sigStartByte > start ) { break; } if( cs.id != self && cs.endByte >= end ) { best = c; // later starts are more inner } } return best; } void addBase( const std::string& owner, std::string_view base ) { std::vector& e = embeds[ owner ]; if( std::find( e.begin(), e.end(), base ) == e.end() ) { e.emplace_back( base ); std::sort( e.begin(), e.end() ); } } void build() { buildOwners(); staticMember.assign( ing.symbols.size(), 0u ); for( const Symbol& s : ing.symbols ) { // a BODIED callable only: an interface's or an abstract class's bodyless signature is the contract a call // dispatches through, never the body it reaches — that call stays with the ladder (declined_iface= reads it) if( callableKind( s.kind ) && !ownerClass[ s.id ].empty() && receiverHedgeLang( s.lang ) ) { ( s.endByte > s.sigEndByte ? methodsByType : abstractByType )[ typeKey( ownerClass[ s.id ], "::", s.name ) ].push_back( s.id ); if( s.endByte <= s.sigEndByte ) { abstractNames.try_emplace( std::string_view( s.name ), char( 1 ) ); } } } const std::size_t N = ing.symbols.size(); std::vector qualified; // locals, parameters and fields written `pkg.T`: decided once every import alias is known std::vector written; // rust-receivers: Rust locals, parameters and fields written (or constructed) as a type std::vector dispatch; // lane L6: Rust locals, parameters and fields typed only through a trait (DispatchType) std::vector augAssigns; // Python `x op= v`: decided once every fact and method is known (h1-annot) types.importsByFile.assign( ing.files.size(), {} ); types.filePackage.assign( ing.files.size(), {} ); types.moduleAlias = &moduleAlias; types.goPackages = goPackages; for( const Binding& b : ing.bindings ) { noteCallResultFacts( b ); if( b.kind == LocalBindKind::ModuleAlias && b.fromSymbol == kNoNode && !b.var.empty() && !b.isFromAssignment ) { tombstoneInsert( moduleAlias, keyOf( b.fileId, '#', b.var ), b.typeName ); continue; } if( b.kind == LocalBindKind::NameAlias && !b.var.empty() ) { tombstoneInsert( nameAlias, keyOf( b.fileId, '#', b.var ), b.typeName ); continue; } if( b.kind == LocalBindKind::JsImport && !b.var.empty() && !b.importedName.empty() && b.importedName != b.var ) { tombstoneInsert( nameAlias, keyOf( b.fileId, '#', b.var ), b.importedName ); // `import { Context as Ctx }` continue; } if( b.fromSymbol >= N ) { continue; } const NodeId from = factScope( b ); const bool typedLocal = b.kind == LocalBindKind::RecvType || ( b.kind == LocalBindKind::Type && ( ing.symbols[ b.fromSymbol ].lang == Lang::TypeScript || ing.symbols[ b.fromSymbol ].lang == Lang::Python ) ); if( b.kind == LocalBindKind::DispatchType ) { if( !b.var.empty() && !b.typeName.empty() ) { dispatch.push_back( &b ); } } else if( b.kind == LocalBindKind::StaticMember ) { if( ing.symbols[ from ].name == b.var ) // recorded inside the member's body: the member itself { staticMember[ from ] = 1; } } else if( ( b.kind == LocalBindKind::RecvType || b.kind == LocalBindKind::MemberType ) && !b.var.empty() && !b.typeName.empty() && callResultFamilyOf( ing.symbols[ b.fromSymbol ].lang ) == CallResultFamily::Rust ) { written.push_back( &b ); // rust-receivers: a written Rust type resolves like a declared result, once imports are known } else if( ( b.kind == LocalBindKind::RecvType || b.kind == LocalBindKind::MemberType ) && !b.var.empty() && !b.importedName.empty() && callResultFamilyOf( ing.symbols[ b.fromSymbol ].lang ) == CallResultFamily::Rust ) { noteRustStdWritten( from, b, b.importedName, false ); // std-namesake: a tombstone carrying a standard type's spine } else if( ( b.kind == LocalBindKind::RecvType || b.kind == LocalBindKind::MemberType ) && !b.var.empty() && !b.importedName.empty() ) { qualified.push_back( &b ); } else if( typedLocal && !b.var.empty() ) { addLocalFact( from, b ); } else if( b.kind == LocalBindKind::MemberType && !b.var.empty() ) { noteMemberType( b, b.typeName ); } else if( b.kind == LocalBindKind::MethodAlias && !b.var.empty() ) { const auto [ it, fresh ] = methodAlias.try_emplace( keyOf( from, '#', b.var ), b.typeName, b.importedName ); if( !fresh && ( it->second.first != b.typeName || it->second.second != b.importedName ) ) { it->second.first.clear(); // rebound to something else: decide nothing } } else if( b.kind == LocalBindKind::AugAssign && !b.var.empty() ) { augAssigns.push_back( &b ); } else if( b.kind == LocalBindKind::OperatorResult ) { operatorResult.emplace_back( b.fromSymbol, b.typeName ); } } types.finishIndex(); for( const Binding* q : qualified ) { noteQualifiedWritten( *q ); } for( const Binding* w : written ) { noteResolvedWritten( *w ); } for( const Binding* d : dispatch ) { noteDispatchWritten( *d ); } sealRustStdFields(); std::ranges::sort( operatorResult, []( const std::pair& a, const std::pair& b ) { return a.first != b.first ? a.first < b.first : sortutil::svLess( a.second, b.second ); } ); localType.seal(); // every fact but the AugAssign drops below: their reads see the sealed table active = true; std::vector dropped; for( const Binding* a : augAssigns ) { if( augDropsClass( *a ) ) // reads methodOf: after `active` { dropped.push_back( a ); } } // K1a: the drops are added after every read. Equivalent to adding each as it is decided: a drop is a tombstone // (type ""), and augDropsClass reads only the typed facts of a name. for( const Binding* a : dropped ) { addTypedFact( factScope( *a ), *a, {}, kNoNode ); augDropped.push_back( a ); } localType.seal(); } // Lane h1-annot: a Python `x op= v` rebinds `x` to what the operator returns. The class C `x` holds in its scope — every // typed fact of the name agreeing on ONE class — survives only when the method Python calls is ONE definition whose // OperatorResult record names "self" or C: C's in-place method `a.typeName` (`__iadd__`; its own, else the shallowest // base's: methodOf), else — C defines none in its cone — its binary method `a.importedName` (`__add__`: `x = x + v`). // Otherwise (a result that is not provably C, two definitions, neither method) `x` gets a tombstone, as a plain // reassignment does. A name with no typed fact is left alone (nothing to drop). True: `a` drops the class (build() adds // the tombstone and records it in augDropped). // test/receiverevidencecheck.sh (Q) AugNotSelf / AugNoDunder / AugOtherOp [N], AugSelf / AugIorSelf / AugInherited / // AugBinaryAnnotated [P]. bool augDropsClass( const Binding& a ) const { std::string_view cls; NodeId id = kNoNode; bool one = true; const std::span facts = localType.find( factScope( a ), a.var ); // const member: the sealed table's view for( const LocalFact& f : facts ) { if( f.type.empty() ) { continue; } one = one && ( cls.empty() || ( f.type == cls && f.cls == id ) ); if( cls.empty() ) { cls = f.type; id = f.cls; } } return !cls.empty() && !( one && operatorKeepsClass( cls, id, a.typeName, a.importedName ) ); } // (L) the call-result facts one binding feeds: the file's imports (CallResultTypes) and the function's call-initialised // bindings of each name (typeCallResult's TS guess rule) void noteCallResultFacts( const Binding& b ) { types.noteImport( b ); if( b.kind == LocalBindKind::CallResult && b.fromSymbol < ing.symbols.size() && !b.var.empty() ) { ++callResultDecls[ keyOf( factScope( b ), '#', b.var ) ]; } } // a field's class on its owner (`type` "": unknown, a tombstone); an embedded field (Go) is also a base. `cls`: the ONE // class a QUALIFIED written type resolved to (noteQualifiedWritten), kept beside the name only while every record of the // key agrees on it — a same-named owner whose field names no class (or another) leaves kNoNode, the name alone void noteMemberType( const Binding& b, std::string_view type, NodeId cls = kNoNode ) { const Symbol& from = ing.symbols[ b.fromSymbol ]; const std::string& owner = classLike( from.kind ) ? from.name : ownerClass[ b.fromSymbol ]; if( owner.empty() ) { return; } const std::string& fieldKey = typeKey( owner, "#", b.var ); if( const auto known = memberTypeClass.find( fieldKey ); known != memberTypeClass.end() ) { known->second = known->second == cls ? cls : kNoNode; // a record that disagrees (or names no class) hides it } else if( cls != kNoNode && !memberType.contains( fieldKey ) ) { memberTypeClass.emplace( fieldKey, cls ); // the key's first record: an earlier one without a class leaves no entry } tombstoneInsert( memberType, fieldKey, type ); if( b.isFromAssignment && !type.empty() ) { addBase( owner, type ); } } // a local, parameter or field written `pkg.T` (importedName = the qualified text: the Go, Python and TS captures write it) // names a class of THIS tree only when its qualifier passes the language's WrittenQualifierRule: Go — `pkg` imports an // in-tree package defining it (CallResultTypes::goQualifiedClass): `f *os.File` beside an in-tree `File` is os's File, // never ours (test/receiverevidencecheck.sh (L) NearOSParam, NearOSField); Python / TS (h1-annot) — the qualifier is an // in-tree module or namespace (qualifierInTree): `s: requests.Session`, `s: ext.Session` beside an in-tree Session // prove nothing ((Q) PyModT, TsNsT). Anything else keeps the name as a tombstone. A Go local carries the class it resolved to. void noteQualifiedWritten( const Binding& q ) { EXPECTS( q.fromSymbol < ing.symbols.size() && !q.importedName.empty(), "build() queues only attributed records that carry a qualifier" ); NodeId cls = kNoNode; bool keep = false; switch( writtenQualifierRuleOf( ing.symbols[ q.fromSymbol ].lang ) ) { case WrittenQualifierRule::GoPackage: cls = types.goQualifiedClass( q.fileId, q.importedName, q.typeName ); if( cls == kNoNode && q.kind != LocalBindKind::MemberType ) // a field's class is kept by NAME (memberType): no witness there { cls = types.goDeclLessQualified( q.fileId, q.importedName, q.typeName ); // a type the tree has only methods of } keep = cls != kNoNode; break; case WrittenQualifierRule::FileImport: keep = qualifierInTree( q.fileId, q.importedName ); break; case WrittenQualifierRule::None: break; } const std::string_view type = keep ? std::string_view( q.typeName ) : std::string_view{}; if( q.kind == LocalBindKind::MemberType ) { noteMemberType( q, type, keep ? cls : kNoNode ); // a Go field `addrs.Set[addrs.Module]`: addrs' Set, not every Set return; } addTypedFact( factScope( q ), q, type, cls ); } // rust-receivers: a Rust local, parameter or field WRITTEN as a type (or constructed: `T { .. }`, `T::default()`) names the // ONE in-tree class that spelling resolves to at its own site, by the call-result rule (CallResultTypes::resultClassOf: the // item scopes innermost first with their `use`s, items and aliases, then a path from crate / self / super / an in-tree crate // or module; an outside, unresolved or doubly bound spelling names nothing). Never a TRAIT (`&Renderer`, a bare trait // object: which impl runs is dispatch, lane L6). Anything else keeps the binding as a tombstone: it hides an outer binding // of the name and proves nothing. A field carries its class into memberClass, which the path walk reads. void noteResolvedWritten( const Binding& w ) { NodeId cls = types.resultClassOf( w, ing.symbols[ w.fromSymbol ].lang ); // std-namesake: a spelling that resolved to nothing in the tree and names a standard receiver type (`Vec`, `String`, // `std::collections::HashMap`) keeps its tombstone, carrying the spelling as a one-name spine if( cls == kNoNode && externalnames::inSortedTable( externalnames::kRustStdReceiverTypes, std::string_view( w.typeName ) ) ) { noteRustStdWritten( factScope( w ), w, w.importedName.empty() ? std::string_view( w.typeName ) : std::string_view( w.importedName ), true ); return; } if( cls != kNoNode && ing.symbols[ cls ].kind == SymKind::Interface ) { cls = kNoNode; } const std::string_view type = cls != kNoNode ? std::string_view( ing.symbols[ cls ].name ) : std::string_view{}; if( w.kind == LocalBindKind::MemberType ) { if( classLike( ing.symbols[ w.fromSymbol ].kind ) ) // the struct declaring the field, by its own definition { const auto [ it, fresh ] = memberClass.try_emplace( keyOf( w.fromSymbol, '#', w.var ), cls ); if( !fresh && it->second != cls ) { it->second = kNoNode; // two declarations of the field disagree: decide nothing } } return; } addTypedFact( factScope( w ), w, type, cls ); } // lane L6: a Rust parameter, local or field typed only as SOME implementor of a trait (model.h LocalBindKind::DispatchType) // — `&dyn T`, `Box`, `impl T`, a generic bounded by T. The trait resolves at the binding's own site like a written // type (resultClassOf's Rust rows) and must be a trait (SymKind::Interface); the binding then types no class: a local or // parameter is the tombstone it replaces, carrying the trait beside it, and a field its memberIface entry (the field's // memberClass tombstone was recorded by its own MemberType). Read by dispatchReceiverOf, for the dispatch tier alone. void noteDispatchWritten( const Binding& d ) { const std::string_view imported = d.importedName; const std::size_t colon = imported.find( ": " ); const std::string_view bound = colon == std::string_view::npos ? std::string_view{} : imported; const std::string_view written = colon == std::string_view::npos ? imported : imported.substr( colon + 2 ); const std::string_view whole = written.find( "::" ) == std::string_view::npos ? std::string_view{} : written; NodeId trait = types.rustResultClass( d.fileId, d.startByte, whole, d.typeName ); if( trait != kNoNode && ing.symbols[ trait ].kind != SymKind::Interface ) { trait = kNoNode; // a class of that name: `dyn` / `impl` / a bound name a trait, never a class } if( d.isFromAssignment ) // a struct's field { if( classLike( ing.symbols[ d.fromSymbol ].kind ) ) { const auto [ it, fresh ] = memberIface.try_emplace( keyOf( d.fromSymbol, '#', d.var ), trait ); if( !fresh && it->second != trait ) { it->second = kNoNode; // two declarations of the field disagree: decide nothing } } return; } LocalFact f = factOf( d, kNoNode ); // the tombstone it stands in for, carrying the trait f.iface = trait; f.bound.assign( bound ); localType.addUnique( factScope( d ), d.var, f ); } // ── lane std-namesake (STD-RECEIVER-NAMESAKE): a Rust receiver WRITTEN as a standard type ────────────────────────────────── // A local, parameter or field whose written type spells a standard type (`m: &HashMap`, `opt: Option`, `s: &str`, // the payload of `if let Some( x ) = v`) is the tombstone it was — it names no in-tree class — carrying the type's SPINE // (ingest_binds.h rustStdSpine). A field is a memberClass tombstone with its spine in memberStd. // `typedRecord`: the binding came through noteResolvedWritten (a spelling with a class NAME that resolved to nothing), which // records a field's memberClass tombstone; a record that never named a class records what it did before the lane. void noteRustStdWritten( NodeId scope, const Binding& b, std::string_view spine, bool typedRecord ) { if( b.kind == LocalBindKind::MemberType ) { if( !typedRecord ) { noteMemberType( b, {} ); // the name tables' tombstone, as for any field that names no class } if( classLike( ing.symbols[ b.fromSymbol ].kind ) ) { if( typedRecord ) { const auto [ it, fresh ] = memberClass.try_emplace( keyOf( b.fromSymbol, '#', b.var ), kNoNode ); if( !fresh ) { it->second = kNoNode; // two declarations of the field disagree: decide nothing (noteResolvedWritten's rule) } } RustStdField field; field.spine.assign( spine ); field.fileId = b.fileId; memberStd.try_emplace( keyOf( b.fromSymbol, '#', b.var ), field ); } return; } LocalFact f = factOf( b, kNoNode ); f.bound.assign( spine ); localType.addUnique( scope, b.var, f ); } // a std field is read only when its struct declares the field ONCE: count every MemberType record of each kept key void sealRustStdFields() { if( memberStd.empty() ) { return; } for( const Binding& b : ing.bindings ) { if( b.kind == LocalBindKind::MemberType && !b.var.empty() && b.fromSymbol < ing.symbols.size() && classLike( ing.symbols[ b.fromSymbol ].kind ) ) { if( const auto it = memberStd.find( keyOf( b.fromSymbol, '#', b.var ) ); it != memberStd.end() ) { ++it->second.decls; } } } std::erase_if( memberStd, []( const auto& kv ) { return kv.second.decls != 1; } ); } static bool rustPathRootedInStd( std::string_view path ) noexcept { const std::string_view root = path.substr( 0, path.find( "::" ) ); return root == "std" || root == "core" || root == "alloc"; } // The tree's own Rust types named `name`: None; StdAliases when every one is an ALIAS of the standard type of that name (`pub // type Result = std::result::Result;`); Foreign when one is a struct, enum, union or trait, or an alias of // anything else (or of a path not rooted in std / core / alloc) — an in-tree namesake a written `name` may mean. enum class RustNamesakes : char { Foreign, None, StdAliases }; RustNamesakes rustNamesakesOf( std::string_view name ) const { const auto [ memo, fresh ] = rustStdNamesakeMemo.try_emplace( std::string( name ), char( 0 ) ); if( !fresh ) { return RustNamesakes( memo->second ); } NodeId one = kNoNode; const std::size_t classes = types.classesNamed( name, CallResultFamily::Rust, []( NodeId ) { return true; }, one ); std::size_t stdAliases = 0; if( classes != 0 ) { if( const auto rows = types.aliasesByName.find( std::string( name ) ); rows != types.aliasesByName.end() ) { for( const Binding* b : rows->second ) { const std::string_view target = std::string_view( b->importedName ); const std::string_view head = target.substr( 0, target.find( '<' ) ); const bool rustFile = b->fileId < ing.files.size() && std::string_view( ing.files[ b->fileId ] ).ends_with( ".rs" ); stdAliases += rustFile && rustPathRootedInStd( head ) && head.find( "::" ) != std::string_view::npos && namesplit::afterLast( head, "::" ) == name ? 1u : 0u; } } } const RustNamesakes verdict = classes != stdAliases ? RustNamesakes::Foreign : classes == 0 ? RustNamesakes::None : RustNamesakes::StdAliases; rustStdNamesakeMemo.find( std::string( name ) )->second = char( verdict ); return verdict; } // Does file `f` glob-import a module that is neither the standard library's nor the tree's (`use rayon::prelude::*`)? Such a // glob may bring in a type that hides a prelude name, which no record shows: a bare prelude spelling proves nothing there. bool rustHasForeignGlob( std::uint32_t f ) const { if( rustForeignGlob.size() < ing.files.size() ) { rustForeignGlob.resize( ing.files.size(), 0 ); } if( f >= rustForeignGlob.size() ) { return true; } if( rustForeignGlob[ f ] == 0 ) { bool foreign = false; types.forEachImport( f, "*", [ & ]( const Binding& b ) { const std::string_view path = std::string_view( b.importedName ); const std::string_view root = path.substr( 0, path.find( "::" ) ); const bool ours = root == "crate" || root == "self" || root == "super" || types.rustRootNamesTreePackage( f, b.startByte, path ); foreign = foreign || ( b.kind == LocalBindKind::TypeImport && !ours && !rustPathRootedInStd( path ) ); } ); rustForeignGlob[ f ] = foreign ? 2 : 1; } return rustForeignGlob[ f ] == 2; } // Is `written` — one name of a spine, as the source spells it (`Option`, `HashMap`, `std::sync::Mutex`, `io::Result`) — provably // the STANDARD type in file `f`? `str` and "[]" always (no declaration can shadow a primitive). Otherwise the tree must define // no namesake but an alias of the standard type itself (rustNamesakesAreStd), and the spelling must reach std: a path rooted // in std / core / alloc; a path whose first segment the file imports from there (`use std::io;` … `io::Result`); a bare name // the file imports from there, or from `crate` / `self` / `super` where the tree aliases the standard type under that name; or a bare PRELUDE name the // file neither imports from elsewhere nor may receive from a foreign glob. A renamed or outside import of the name, and a // non-prelude name the file does not import (it came through a glob or a macro), prove nothing. bool rustStdNameProven( std::uint32_t f, std::string_view written ) const { if( written == "str" || written == "[]" ) { return true; } const std::size_t sep = written.find( "::" ); const std::string_view name = namesplit::afterLast( written, "::" ); if( !( externalnames::inSortedTable( externalnames::kRustStdReceiverTypes, name ) || externalnames::inSortedTable( externalnames::kRustStdDerefTypes, name ) ) || name == "str" || name == "[]" || rustNamesakesOf( "Box" ) == RustNamesakes::Foreign ) // Box: a typed record's `Box>` was read through unseen { return false; } const RustNamesakes namesakes = rustNamesakesOf( name ); if( namesakes == RustNamesakes::Foreign ) { return false; } const std::string_view probe = sep == std::string_view::npos ? name : written.substr( 0, sep ); // the name the file must bind bool good = false, bad = false; types.forEachImport( f, probe, [ & ]( const Binding& b ) { if( b.kind != LocalBindKind::TypeImport ) { return; // the file's own alias of the name: rustNamesakesAreStd answered for it } const std::string_view path = std::string_view( b.importedName ); const std::string_view root = path.substr( 0, path.find( "::" ) ); const bool fromStd = rustPathRootedInStd( path ) && !types.rustRootNamesTreePackage( f, b.startByte, path ); const bool fromTree = sep == std::string_view::npos && namesakes == RustNamesakes::StdAliases && b.typeName == probe && ( root == "crate" || root == "self" || root == "super" ); ( fromStd || fromTree ? good : bad ) = true; } ); if( bad ) { return false; } if( sep != std::string_view::npos ) { return good || ( rustPathRootedInStd( written ) && !types.rustRootNamesTreePackage( f, 0, written ) ); } return good || ( externalnames::inSortedTable( externalnames::kRustPreludeTypes, name ) && !rustHasForeignGlob( f ) ); } // The final type name a spine proves its binding to be — "Vec", "Mutex", "[]" — when EVERY name on it is the standard type in // file `f` (rustStdNameProven), else "". Memoised per ( file, spine ). std::string_view rustStdSpineHead( std::uint32_t f, std::string_view spine ) const { const auto [ memo, fresh ] = rustStdSpineMemo.try_emplace( std::string( keyOf( f, '#', spine ) ), std::string_view{} ); if( !fresh ) { return memo->second; } std::string_view head; for( std::string_view rest = spine; ; ) { const std::size_t cut = rest.find( '<' ); const std::string_view seg = rest.substr( 0, cut ); if( seg.empty() || !rustStdNameProven( f, seg ) ) { head = {}; break; } head = namesplit::afterLast( seg, "::" ); if( cut == std::string_view::npos ) { break; } rest.remove_prefix( cut + 1 ); } if( !externalnames::inSortedTable( externalnames::kRustStdReceiverTypes, head ) ) { head = {}; // a spine must END in a receiver type (a bare `Arc` proves nothing) } rustStdSpineMemo.find( std::string( keyOf( f, '#', spine ) ) )->second = head; return head; } // The standard type a Rust member call's receiver is WRITTEN as, proven (rustStdSpineHead), else "": a local or parameter // (`m.get( k )`), a field of `self` or of a local typed as an in-tree class, each field above the last by its resolved class // (`self.opt.map( .. )`, `s.inner.names.get( 0 )`). The receiver is the ROOT or the last FIELD itself — never a call result, // an index, a `?` or an `.await` on it (chainOf reads none of those as a path). A local is read lexically (localSeenAt): a // shadowing binding of the name, typed or not, hides the standard one. std::string_view rustStdWrittenReceiver( const Reference& r ) const { if( !active || langFacts( r.lang ).writtenStdReceiver != WrittenStdReceiver::RustSpine || r.fromSymbol >= ing.symbols.size() || !r.qualifier.empty() || !isMemberCallRef( r ) ) { return {}; } const Chain ch = chainOf( r ); if( !ch.valid || !ch.ctor.empty() || ch.root.empty() ) { return {}; } NodeId cls = kNoNode; if( ch.root == "self" ) { cls = ch.path.empty() ? kNoNode : selfClass( r.fromSymbol ); } else if( const std::optional t = localSeenAt( r.fromSymbol, ch.root, r.startByte ); t.has_value() ) { if( ch.path.empty() ) { const bool stdTombstone = t->type.empty() && t->cls == kNoNode && t->iface == kNoNode && !t->bound.empty(); return stdTombstone ? rustStdSpineHead( r.fileId, t->bound ) : std::string_view{}; } cls = t->cls; } for( std::string_view rest = ch.path; cls != kNoNode; ) { const std::size_t dot = rest.find( '.' ); const std::string_view field = rest.substr( 0, dot ); if( dot == std::string_view::npos ) // the last field: the receiver itself { const auto it = memberStd.find( keyOf( cls, '#', field ) ); return it == memberStd.end() ? std::string_view{} : rustStdSpineHead( it->second.fileId, std::string_view( it->second.spine ) ); } rest.remove_prefix( dot + 1 ); const auto it = memberClass.find( keyOf( cls, '#', field ) ); cls = it == memberClass.end() ? kNoNode : it->second; } return {}; } // May a receiver proven to be the standard type `head` run a method OWNED by the in-tree type-like name `owner`? Only through // a trait: `owner` is a trait (its default method, or the declaration an `impl Trait for Vec` answers), an alias (`impl Ext // for Table` under `type Table = HashMap<..>` is an impl for the standard type), or the type's own name. A struct, enum or // union of another name never: std's types deref to no user type and take no inherent impl outside std. bool rustStdReceiverMayReach( std::string_view owner, std::string_view head ) const { if( owner == head ) { return true; } const auto [ memo, fresh ] = rustStdOwnerMemo.try_emplace( std::string( owner ), char( 0 ) ); if( fresh ) { NodeId one = kNoNode; const bool trait = types.classesNamed( owner, CallResultFamily::Rust, [ & ]( NodeId c ) { return ing.symbols[ c ].kind == SymKind::Interface; }, one ) != 0; const bool known = types.classesNamed( owner, CallResultFamily::Rust, []( NodeId ) { return true; }, one ) != 0; const bool reach = trait || !known || types.aliasesByName.contains( std::string( owner ) ); rustStdOwnerMemo.find( std::string( owner ) )->second = char( reach ? 1 : 0 ); return reach; } return memo->second != 0; } // is the result of the operator Python calls on a `cls` receiver (`inPlace`, else `binary`) provably `cls` (augDropsClass) bool operatorKeepsClass( std::string_view cls, NodeId id, std::string_view inPlace, std::string_view binary ) const { if( !methodOf( cls, inPlace, false, id ) && ( binary.empty() || !methodOf( cls, binary, false, id ) ) ) { return false; } if( found.size() != 1 ) { return false; } const auto row = std::ranges::lower_bound( operatorResult, found[ 0 ], []( NodeId a, NodeId b ) { return a < b; }, &std::pair::first ); return row != operatorResult.end() && row->first == found[ 0 ] && ( row->second == "self" || row->second == cls ); } // Python / TS (h1-annot): is the qualifier of the written type `whole` (`requests.Session`, `a.b.T`, `ns.T`) — its ROOT, // the name the file binds — an in-tree module, package or namespace as file `f` sees it: an import binding it decides // (buildQualifierVerdicts: 'i' in the tree, 'x' outside); bound by no import, an in-tree class (`Outer.Inner`) or a // namespace some file declares (TS `namespace Local`) passes, anything else (`NodeJS.T`, an unbound name) does not. bool qualifierInTree( std::uint32_t f, std::string_view whole ) const { const std::size_t dot = whole.find( '.' ); if( dot == std::string_view::npos || dot == 0 ) { return false; } const std::string_view root = whole.substr( 0, dot ); if( qualifierVerdicts != nullptr ) { if( const auto it = qualifierVerdicts->find( keyOf( f, '#', root ) ); it != qualifierVerdicts->end() ) { return it->second == 'i'; } } key.assign( root ); if( classNames.contains( key ) ) { return true; } if( !namespaceNamesBuilt ) { namespaceNamesBuilt = true; for( const Binding* ns : types.namespaces ) { namespaceNames.try_emplace( std::string( ns->var.substr( 0, ns->var.str().find( '.' ) ) ), char( 1 ) ); // `a.b` declares `a` } } return namespaceNames.contains( key ); } // the definition a local binding belongs to: a typed local the extractor also indexed as a symbol of its own (a Go // `var c T` inside a function) belongs to the function that declares it NodeId factScope( const Binding& b ) const { NodeId from = b.fromSymbol; if( from < ing.symbols.size() && !callableKind( ing.symbols[ from ].kind ) && !classLike( ing.symbols[ from ].kind ) ) { if( const NodeId fn = enclosingFn( from ); fn != kNoNode ) { from = fn; } } return from; } // (L) call-result typing: the local `b` (a LocalBindKind::CallResult) holds class `cls` (the definition `id`) over its // span — the class REPLACES the empty tombstone its own declaration recorded there (the same span), so no other binding // of the name changes. TS: the declaration records no tombstone; its base-pass Type record (unspanned) read the call // initializer as a constructor naming the CALLEE (`const c = makeConfig()` → `makeConfig`). When no class has that name // that guess is replaced — but an unspanned record has no span to tell two declarations apart, so only when this is the // function's ONLY call-initialised binding of the name (callResultDecls): sibling blocks' `const c = a.make()` / `const c // = b.make()` type neither. False when nothing was replaced. bool typeCallResult( const Binding& b, std::string_view cls, NodeId id ) { const NodeId scope = factScope( b ); const std::span facts = localType.find( scope, b.var ); if( facts.empty() || cls.empty() ) { return false; } const bool spanned = b.spanEnd > b.spanStart; for( LocalFact& f : facts ) { if( f.start == ( spanned ? b.spanStart : 0u ) && f.end == ( spanned ? b.spanEnd : 0u ) && f.type.empty() ) { f.type.assign( cls ); f.cls = id; return true; } } const auto decls = callResultDecls.find( keyOf( scope, '#', b.var ) ); for( LocalFact& f : facts ) { if( f.type == b.typeName && !classNames.contains( f.type.str() ) && decls != callResultDecls.end() && decls->second == 1 ) { f.type.assign( cls ); f.cls = id; return true; } } return false; } // the call-result local `b` whose callee declares result `rt`: typed by `cls` (resultClassOf's class), else — Go — by the // witness of a type the tree holds only methods of (GO-CALLRESULT-LOCAL, CallResultTypes::goDeclLessResult) void typeCallResultOf( const Binding& b, const Binding& rt, NodeId cls, Lang lang ) { if( cls != kNoNode ) { typeCallResult( b, ing.symbols[ cls ].name, cls ); } else if( const NodeId witness = types.goDeclLessResult( rt, lang ); witness != kNoNode ) { typeCallResult( b, rt.typeName, witness ); } } // lane iface-peel (LangFacts::returnTypedDispatchLet): the local `b` (a CallResult) holds the result of a call whose ONE // proven callee declares `-> &dyn T` / `Box` / `impl T` (`rt`, a ReturnType carrying kDispatchResultBit). The trait // resolves in the CALLEE's file like a written type (noteDispatchWritten's rule) and must be a trait; the local's own // untyped tombstone (same span) then carries it, exactly as `let x: &dyn T` would. False when nothing was typed: no // tombstone, a class of that name, an unresolved or ambiguous trait. bool typeCallResultDispatch( const Binding& b, const Binding& rt ) { const std::span facts = localType.find( factScope( b ), b.var ); if( facts.empty() ) { return false; } const std::string_view written = rt.importedName; const NodeId trait = types.rustResultClass( rt.fileId, rt.startByte, written.find( "::" ) == std::string_view::npos ? std::string_view{} : written, rt.typeName ); if( trait == kNoNode || ing.symbols[ trait ].kind != SymKind::Interface ) { return false; } const bool spanned = b.spanEnd > b.spanStart; for( LocalFact& f : facts ) { if( f.start == ( spanned ? b.spanStart : 0u ) && f.end == ( spanned ? b.spanEnd : 0u ) && f.type.empty() && f.iface == kNoNode ) { f.iface = trait; return true; } } return false; } // ── queries ─────────────────────────────────────────────────────────────────────────────────────────────────────── // the innermost function/method of the same file whose span strictly holds `id`; kNoNode when none NodeId enclosingFn( NodeId id ) const { return innermostEnclosingFn( ing, fnsByFile, id ); } // visit `from`, then each function enclosing it, innermost first (at most 8 scopes): `visit( scope )` returns true // to stop there. Returns the scope it stopped at, kNoNode when no visit stopped the walk. template NodeId walkScopes( NodeId from, Visit&& visit ) const { NodeId cur = from; for( int depth = 0; depth < 8 && cur != kNoNode; ++depth ) { if( visit( cur ) ) { return cur; } cur = enclosingFn( cur ); } return kNoNode; } // FE-B (review B4): the class local `var` holds at byte `site` of definition `scope`, by lexical scope — the innermost // spanned binding that holds the site (a later start is more inner; a tie of two classes is unknown), checked against // every binding with no span (its extent is unknown, so a disagreement is unknown). nullopt: no binding of `var` is // visible there; "": one is, and it names no single class. SeenLocal::cls (fix round 1): the ONE class definition the // binding resolved to (a call result's), kNoNode for a name alone — two facts that agree on the name but not on the // definition disagree. struct SeenLocal { std::string_view type; NodeId cls = kNoNode; NodeId iface = kNoNode; // lane L6: typed only as SOME implementor of this trait (LocalFact::iface) std::string_view bound; // lane L6: that typing's generic bound text, "" when none bool operator==( const SeenLocal& ) const = default; }; static SeenLocal seenOf( const LocalFact& f ) noexcept { SeenLocal seen; seen.type = std::string_view( f.type ); // pool texts never move: the views outlive the table seen.cls = f.cls; seen.iface = f.iface; // lane L6 seen.bound = std::string_view( f.bound ); return seen; } std::optional seenLocal( NodeId scope, std::string_view var, std::uint32_t site ) const { const std::optional name = rw::InternedText::ifInterned( var ); return name.has_value() ? seenLocal( scope, *name, site ) : std::nullopt; } // the same, for a name already looked up (a never-interned name has no binding: the caller stops before) std::optional seenLocal( NodeId scope, rw::InternedText var, std::uint32_t site ) const { const std::span facts = localType.find( scope, var ); if( facts.empty() ) { return std::nullopt; } const LocalFact* inner = nullptr; bool innerSplit = false; std::optional whole; for( const LocalFact& f : facts ) { if( f.end == 0 ) { whole = ( whole.has_value() && *whole != seenOf( f ) ) ? SeenLocal{} : seenOf( f ); continue; } if( site < f.start || site >= f.end ) { continue; } if( inner == nullptr || f.start > inner->start || ( f.start == inner->start && f.end < inner->end ) ) { inner = &f; innerSplit = false; } else if( f.start == inner->start && f.end == inner->end && seenOf( f ) != seenOf( *inner ) ) { innerSplit = true; } } if( inner == nullptr ) { return whole; } const SeenLocal seen = innerSplit ? SeenLocal{} : seenOf( *inner ); return ( whole.has_value() && *whole != seen ) ? SeenLocal{} : seen; } static std::optional typeOf( const std::optional& seen ) noexcept { return seen.has_value() ? std::optional( seen->type ) : std::nullopt; } std::optional visibleLocal( NodeId scope, std::string_view var, std::uint32_t site ) const { return typeOf( seenLocal( scope, var, site ) ); } // the local `var` visible at byte `site` of `from` or of a function enclosing it (the innermost that has one) std::optional localSeenAt( NodeId from, std::string_view var, std::uint32_t site ) const { std::optional hit; const std::optional name = rw::InternedText::ifInterned( var ); // once, not per scope (hoisted) if( !name.has_value() ) { return hit; // never interned: no binding anywhere } walkScopes( from, [ & ]( NodeId scope ) { hit = seenLocal( scope, *name, site ); return hit.has_value(); } ); return hit; } std::optional localAt( NodeId from, std::string_view var, std::uint32_t site ) const { return typeOf( localSeenAt( from, var, site ) ); } // the ( object var, method ) a method alias `var` names in `from` or a function enclosing it; `scope` = where it is bound const std::pair* aliasedMethod( NodeId from, std::string_view var, NodeId& scope ) const { const std::pair* hit = nullptr; if( const NodeId at = walkScopes( from, [ & ]( NodeId s ) { const auto it = methodAlias.find( keyOf( s, '#', var ) ); if( it == methodAlias.end() ) { return false; } hit = it->second.first.empty() ? nullptr : &it->second; return true; } ); at != kNoNode ) { scope = at; } return hit; } // is `name` a parameter or local of `from` or of a function enclosing it (any binding the extractor recorded) bool isLocalName( NodeId from, std::string_view name ) const { if( localNames == nullptr ) { return false; } const std::optional typed = rw::InternedText::ifInterned( name ); // once, not per scope (hoisted) return walkScopes( from, [ & ]( NodeId s ) { return localNames->contains( keyOf( s, '#', name ) ) || ( typed.has_value() && localType.contains( s, *typed ) ); } ) != kNoNode; } // does `from` or a function enclosing it DECLARE `name` (a parameter or a local, typed or not) — not merely bind it: Java // copies each field name onto its class's methods as a bound-only name (graph.h shadowJavaFieldsOntoMethods), which must // not hide the field itself bool declaresLocal( NodeId from, std::string_view name, std::uint32_t site ) const { return walkScopes( from, [ & ]( NodeId s ) { if( visibleLocal( s, name, site ).has_value() ) { return true; // a binding of the name is visible at the site (review B4: by its span) } if( localNames == nullptr ) { return false; } const auto it = localNames->find( keyOf( s, '#', name ) ); return it != localNames->end() && ( it->second & kLocalNameDeclared ) != 0; } ) != kNoNode; } // a receiver root that names a CLASS at this site: a class-name receiver language, a class of that name, and no local // of the caller hiding it (`Interval = make(); Interval.validate( v )`) // (L) fix round 2 / 3 (D3, D6): a JVM caller that does not SEE an in-tree class `root` (an import of an outside one, an // outside on-demand import alone, no import at all) names an outside class — never an in-tree namesake bool namesClass( const Reference& r, std::string_view root, std::string_view cls ) const { return langFacts( r.lang ).classNameReceiver && classNames.contains( std::string( cls ) ) && !isLocalName( r.fromSymbol, root ) && !( callResultFamilyOf( r.lang ) == CallResultFamily::Jvm && types.jvmHides( r.fileId, r.startByte, root ) ); } // the class owning the caller — the caller's own owner, else the nearest enclosing function's (a closure in a method) std::string_view callerClass( NodeId from ) const { const NodeId at = walkScopes( from, [ & ]( NodeId s ) { return !ownerClass[ s ].empty(); } ); return at == kNoNode ? std::string_view{} : std::string_view( ownerClass[ at ] ); } // `type`'s direct bases: the inheritance names, then (Go) its embedded classes template void forEachBase( std::string_view type, Fn&& fn ) const { if( const auto it = chaUp.find( std::string( type ) ); it != chaUp.end() ) { for( const std::string& b : it->second ) { fn( std::string_view( b ) ); } } if( const auto it = embeds.find( std::string( type ) ); it != embeds.end() ) { for( const std::string& b : it->second ) { fn( std::string_view( b ) ); } } } // is `ancestor` the class `type` or one of its (transitive) bases bool inCone( std::string_view type, std::string_view ancestor ) const { if( type.empty() || ancestor.empty() ) { return false; } frontier.clear(); frontier.push_back( type ); for( std::size_t i = 0; i < frontier.size() && i < kWalkCap; ++i ) { if( frontier[ i ] == ancestor ) { return true; } forEachBase( frontier[ i ], [ & ]( std::string_view b ) { if( std::find( frontier.begin(), frontier.end(), b ) == frontier.end() ) { frontier.push_back( b ); } } ); } return false; } // visit `type`'s level (depth 0), then its base levels shallowest first, each class once: `visit( level, depth )` // returns true to stop. Returns whether a visit stopped the walk. template bool walkBaseLevels( std::string_view type, Visit&& visit ) const { std::vector level{ type }; std::vector seen{ type }; for( std::size_t depth = 0; depth < kWalkCap && !level.empty(); ++depth ) { if( visit( level, depth ) ) { return true; } std::vector next; for( std::string_view t : level ) { forEachBase( t, [ & ]( std::string_view b ) { if( std::find( seen.begin(), seen.end(), b ) == seen.end() ) { seen.push_back( b ); next.push_back( b ); } } ); } level.swap( next ); } return false; } // `type`'s own `name`, else the shallowest base level defining it (several bases at one level: their union). The // answer is in `found`; false when nothing in the cone defines it. superOnly skips `type` itself (`super.m()`). // `cls` (fix round 1): the ONE definition `type` resolved to — its own level keeps only the members that class owns // (memberOwnerRuleOf), and its bases, which are known by NAME only, are walked only when no other in-tree class of its // language shares that name. bool methodOf( std::string_view type, std::string_view name, bool superOnly, NodeId cls = kNoNode ) const { EXPECTS( active, "methodOf reads the tables build() fills" ); found.clear(); if( type.empty() ) { return false; } const bool basesByName = cls == kNoNode || types.sameNamedClasses( cls ) == 1; bool redeclared = false; // a nearer level declared the name WITHOUT a body: the nearest declaration wins, no ancestor body runs std::size_t foundDepth = 0; const bool gated = abstractNames.contains( name ); // no class declares the name bodyless: neither walk below can matter const bool stopped = walkBaseLevels( type, [ & ]( const std::vector& level, std::size_t depth ) { if( ( superOnly && depth == 0 ) || ( depth > 0 && !basesByName ) ) { return depth > 0; } for( std::string_view t : level ) { const std::size_t before = found.size(); collectMethods( t, name, depth == 0 ? cls : kNoNode ); redeclared = redeclared || ( gated && found.size() == before && abstractOn( t, name, depth == 0 ? cls : kNoNode ) ); } foundDepth = depth; return redeclared || !found.empty(); } ); if( redeclared || ( stopped && !found.empty() && gated && overloadedAbove( type, name, foundDepth ) ) ) { found.clear(); // EXACT OR NO ROW: an abstract re-declaration on the path is no body (the dispatch tier answers) } return stopped && !found.empty(); // a walk stopped at an unwalkable base level found nothing } // Kotlin and C# keep no call-comparable arity (ingest_metrics.h cc_paramShape's language gate; Java has one, which the name tiers' // arity rule reads): `found` (bodies at depth `at`) is not the call's answer when a base level ABOVE // declares the name without a body at a parameter count NO found body has: the call may mean that overload (Sub { override fun // ap() } over Mid { fun ap( x: Int ): Int }). A count a found body has is the ordinary override of it. bool overloadedAbove( std::string_view type, std::string_view name, std::size_t at ) const { const Lang lang = ing.symbols[ found[ 0 ] ].lang; if( !langFacts( lang ).overloadsWithoutArity ) { return false; } return walkBaseLevels( type, [ & ]( const std::vector& level, std::size_t depth ) { for( std::string_view t : level ) { const auto it = depth > at ? abstractByType.find( typeKey( t, "::", name ) ) : abstractByType.end(); if( it != abstractByType.end() && std::ranges::any_of( it->second, [ & ]( NodeId a ) { return std::ranges::all_of( found, [ & ]( NodeId f ) { return ing.symbols[ f ].params != ing.symbols[ a ].params; } ); } ) ) { return true; } } return false; } ); } // does `type` declare a callable `name` with NO body (`cls`: only the one class owns it), and own no body of it (collectMethods // found none): an interface's or abstract class's re-declaration of an inherited member bool abstractOn( std::string_view type, std::string_view name, NodeId cls ) const { const auto it = abstractByType.find( typeKey( type, "::", name ) ); return it != abstractByType.end() && ( cls == kNoNode || std::ranges::any_of( it->second, [ & ]( NodeId c ) { return ownedBy( c, cls ); } ) ); } // `type`'s own callables named `name` into `found` — only those class `cls` owns, when it is a definition void collectMethods( std::string_view type, std::string_view name, NodeId cls ) const { if( const auto it = methodsByType.find( typeKey( type, "::", name ) ); it != methodsByType.end() ) { for( NodeId c : it->second ) { if( cls == kNoNode || ownedBy( c, cls ) ) { found.push_back( c ); } } } } // does class `cls` own member `m` (memberOwnerRuleOf) bool ownedBy( NodeId m, NodeId cls ) const { const Symbol& ms = ing.symbols[ m ]; const Symbol& cs = ing.symbols[ cls ]; switch( memberOwnerRuleOf( cs.lang ) ) { case MemberOwnerRule::PackageDir: return types.dirOf( ms.fileId ) == types.dirOf( cs.fileId ); case MemberOwnerRule::FileOrUnique: // fix round 3: in the type's own file, the impl sits in the type's own item scope return ( ms.fileId == cs.fileId && types.innermostItemScope( m ) == types.innermostItemScope( cls ) ) || types.sameNamedClasses( cls ) == 1; case MemberOwnerRule::Lexical: default: { const NodeId at = classAt( ms.fileId, ms.sigStartByte, ms.endByte, m ); return at == cls || ( at == kNoNode && ms.fileId == cs.fileId ); } } } // the class of field `field` on `type` (or the shallowest base declaring it); "" unknown std::string_view fieldOf( std::string_view type, std::string_view field ) const { std::string_view fieldType; walkBaseLevels( type, [ & ]( const std::vector& level, std::size_t ) { for( std::string_view t : level ) { if( const auto it = memberType.find( typeKey( t, "#", field ) ); it != memberType.end() ) { fieldType = it->second; // "" = tombstone: unknown return true; } } return false; } ); return fieldType; } // The receiver chain of a member call as ( root, path, constructed class ), in every language's spelling. struct Chain { std::string_view root; std::string_view path; std::string_view ctor; bool valid = false; }; static Chain chainOf( const Reference& r ) noexcept { Chain c; if( r.memberCall ) { c.root = r.memberRoot; c.path = r.memberPath(); c.ctor = r.memberCtor(); c.valid = !c.root.empty() || !c.ctor.empty(); return c; } switch( r.recv ) // Python / C++ / Ruby shapes (ingest_binds.h receiverOf) { case RecvKind::ThisObj: c.root = "self"; c.valid = true; break; case RecvKind::NamedVar: c.root = r.recvVar; c.valid = !r.recvVar.empty(); break; case RecvKind::FieldOfThis: c.root = "self"; c.path = r.fieldName(); c.valid = !r.fieldName().empty(); break; case RecvKind::FieldOfVar: c.root = r.recvVar; c.path = r.fieldName(); c.valid = !r.recvVar.empty() && !r.fieldName().empty(); break; case RecvKind::SuperObj: c.root = "super"; c.valid = true; break; default: break; } return c; } // The class the receiver ROOT names at this site; static/super set for a class-name or super receiver. "" unknown. // a class name as the caller's FILE spells it, read through that file's import alias (`Ctx` → `Context`) std::string_view unalias( std::uint32_t fileId, std::string_view name ) const { if( const auto it = nameAlias.find( keyOf( fileId, '#', name ) ); it != nameAlias.end() && !it->second.empty() ) { return it->second; } return name; } // `rootCls` (when asked, and left as the caller set it otherwise): the ONE class a call-result-typed local resolved to // a typed local's class as the caller reads it: a call result's resolved class as it is (its callee's file decided it, // so the caller's import aliases do not apply), any other through the caller's import alias std::string_view typedLocalClass( const Reference& r, const SeenLocal& t, NodeId* rootCls ) const { if( rootCls != nullptr && t.cls != kNoNode ) { *rootCls = t.cls; } return t.cls != kNoNode ? t.type : unalias( r.fileId, t.type ); } std::string_view rootClass( const Reference& r, const Chain& ch, bool& isStatic, bool& superOnly, NodeId* rootCls = nullptr ) const { isStatic = false; superOnly = false; if( !ch.ctor.empty() ) { return unalias( r.fileId, ch.ctor ); } const std::string_view root = ch.root; if( isThisRoot( root ) || ( r.lang == Lang::Python && root == "cls" ) ) { return callerClass( r.fromSymbol ); } if( isSuperRoot( r, root ) ) { superOnly = true; return callerClass( r.fromSymbol ); } if( const std::optional t = localSeenAt( r.fromSymbol, root, r.startByte ); t.has_value() && !t->type.empty() ) { return typedLocalClass( r, *t, rootCls ); } // Java/C#/Kotlin/Swift (the implicit-receiver languages but C++, whose Rule 2b reads fields, and Ruby, whose fields // are @ivars): a bare `field.m()` inside a method is `this.field.m()` — the field the caller's class (or a base) // declares, when no parameter or local of that name hides it if( langFacts( r.lang ).implicitReceiver && r.lang != Lang::Cpp && r.lang != Lang::Ruby && !declaresLocal( r.fromSymbol, root, r.startByte ) ) { const std::string_view owner = callerClass( r.fromSymbol ); if( const std::string_view ft = owner.empty() ? std::string_view{} : fieldOf( owner, root ); !ft.empty() ) { return unalias( r.fileId, ft ); } } const std::string_view cls = unalias( r.fileId, root ); if( namesClass( r, root, cls ) ) { isStatic = true; return cls; } return {}; } // The two SIDES of a JS/TS class lookup (#373's Ruby class-object rule, here): a call on the CLASS object reaches its // `static` members only, a call on an INSTANCE its other members only. True for every target in another language. bool onSide( const Reference& r, NodeId target, bool classSide ) const noexcept { if( r.lang != Lang::JavaScript && r.lang != Lang::TypeScript ) { return true; } return target < staticMember.size() && ( staticMember[ target ] != 0 ) == classSide; } // Does `this` inside the caller name the CLASS? Only inside a static member. bool callerIsStatic( NodeId from ) const noexcept { return from < staticMember.size() && staticMember[ from ] != 0; } // the class the stated field path `path` below `type` names (fieldOf, by name), "" once a field's class is unknown. `lastCls` // (lane overload-split): the LAST field's ONE class when its QUALIFIED written type resolved to one (memberTypeClass, a field // declared on its owner itself), else kNoNode — narrow() answers with that class's OWN members first (terraform's // `d.suppressedModules.Add` is addrs.Set's Add, not every Set's) and, when it owns none (an interface, a method promoted from // an embedded type), reads the field by name exactly as before. std::string_view walkFields( std::string_view type, std::string_view path, NodeId& lastCls ) const { while( !path.empty() && !type.empty() ) { const std::size_t dot = path.find( '.' ); const std::string_view field = path.substr( 0, dot ); path = dot == std::string_view::npos ? std::string_view{} : path.substr( dot + 1 ); const auto known = memberTypeClass.find( typeKey( type, "#", field ) ); lastCls = known == memberTypeClass.end() ? kNoNode : known->second; type = fieldOf( type, field ); } return type; } // RESOLVE: the definitions this member call's typed receiver reaches, in `found`; false when the receiver proves // nothing (untyped, a type this tree does not define, or a type that defines no such member anywhere in its cone). // `spellingDecides` false: the receiver root is a name WRITTEN in its scope (graph.h JsWrittenRoot), so the class its SPELLING names // is not its class — only a stated type (a typed local, a constructed receiver, `this`) may decide. bool narrow( const Reference& r, bool spellingDecides = true ) const { // C++, Ruby, Rust and C keep their own receiver rules (Rules 1, 2, 2b, 2c): this one adds the languages that had none const bool typedLang = r.lang == Lang::JavaScript || r.lang == Lang::TypeScript || r.lang == Lang::Python || r.lang == Lang::Go || r.lang == Lang::Java || r.lang == Lang::Kotlin || r.lang == Lang::CSharp || r.lang == Lang::Swift; const bool localsOnly = receiverLocalsOnly( r.lang ); if( !active || r.fromSymbol >= ing.symbols.size() || !r.qualifier.empty() || !( typedLang || localsOnly ) ) { return false; } if( localsOnly ) { return narrowTypedLocal( r ); } if( !isMemberCallRef( r ) ) { return r.lang == Lang::Python && narrowAliasedMethod( r ); } const Chain ch = chainOf( r ); if( !ch.valid ) { return false; } bool isStatic = false, superOnly = false; NodeId cls = kNoNode; std::string_view type = rootClass( r, ch, isStatic, superOnly, &cls ); if( type.empty() || ( isStatic && !spellingDecides ) || ( cls != kNoNode && !ch.path.empty() && types.sameNamedClasses( cls ) != 1 ) ) { return false; // a field path is read by NAME (memberType): below a class another in-tree class names too, a floor } // the side the receiver names: the class object (a class-name receiver, or `this`/`super` inside a static member), // else an instance; a stated field below always holds an instance bool classSide = isStatic || ( ch.ctor.empty() && ( isThisRoot( ch.root ) || isSuperRoot( r, ch.root ) ) && callerIsStatic( r.fromSymbol ) ); NodeId fieldCls = kNoNode; // the last field's ONE class (walkFields) if( !ch.path.empty() ) // walk the stated field classes: a field always holds an instance { type = walkFields( type, ch.path, fieldCls ); superOnly = false; classSide = false; if( type.empty() ) { return false; } } if( !( fieldCls != kNoNode && methodOf( type, r.calleeName, superOnly, fieldCls ) ) && !methodOf( type, r.calleeName, superOnly, cls ) ) { return false; } // a wrong-side definition is never the answer: what is left is, and nothing left proves nothing (the ladder hedges) std::size_t kept = 0; for( std::size_t i = 0; i < found.size(); ++i ) { if( onSide( r, found[ i ], classSide ) ) { found[ kept++ ] = found[ i ]; } } found.resize( kept ); return !found.empty(); } // (L) a language whose own receiver rules answer `self.m()` (receiverLocalsOnly: Rust's Rule 1): a member call on a typed // LOCAL — a call result graph.h's resolve loop typed, or (rust-receivers) a parameter / `let` written or constructed as an // in-tree type — or on a field path below one or below `self` (`self.book.iter()`, `s.inner.book.m()`), each field by the // ONE class its written type resolved to (memberClass), reaches that class's own members. `self.m()` itself stays Rule 1's. bool narrowTypedLocal( const Reference& r ) const { if( !isMemberCallRef( r ) ) { return false; } const Chain ch = chainOf( r ); if( !ch.valid && callResultFamilyOf( r.lang ) == CallResultFamily::Rust ) { const NodeId cls = rustChainReceiverClass( r ); // lane rust-self-chain: the receiver is another call's result return cls != kNoNode && methodOf( ing.symbols[ cls ].name, r.calleeName, false, cls ); } if( !ch.valid || !ch.ctor.empty() || ch.root.empty() || ( ch.root == "self" && ch.path.empty() ) ) { return false; // `self.m()`: the language's own rule (Rule 1) answers it } const NodeId cls = typedReceiverClass( r, ch ); return cls != kNoNode && methodOf( ing.symbols[ cls ].name, r.calleeName, false, cls ); } // the ONE class a Rust member call's NAMED receiver holds (narrowTypedLocal's reading): `self` (Rust's receiver keyword: `this` / // `Self` are ordinary names, read by their own binding), a typed local or parameter, and the stated fields below either, each by // the ONE class its written type resolved to (memberClass); kNoNode when unknown NodeId typedReceiverClass( const Reference& r, const Chain& ch ) const { NodeId cls = kNoNode; if( ch.root == "self" ) { cls = selfClass( r.fromSymbol ); } else if( const std::optional t = localSeenAt( r.fromSymbol, ch.root, r.startByte ); t.has_value() && !t->type.empty() ) { cls = t->cls; } for( std::string_view rest = ch.path; !rest.empty() && cls != kNoNode; ) // the stated fields, each by its resolved class { const std::size_t dot = rest.find( '.' ); const std::string_view field = rest.substr( 0, dot ); rest = dot == std::string_view::npos ? std::string_view{} : rest.substr( dot + 1 ); const auto it = memberClass.find( keyOf( cls, '#', field ) ); cls = it == memberClass.end() ? kNoNode : it->second; } return cls; } // ── lane rust-self-chain (test/receiverevidencecheck.sh RUST-SELF-CHAIN): a member call on another call's result ──────────── // `Router::new().route( a ).layer( b )`: each hop's receiver is the value the call below it returns. The value is walked from // the chain's ROOT — a path call `T::f()` whose written qualifier resolves to the class owning f (rustQualifierClass, as a // call-result local's `T::f()` is read), or a member call on a named receiver (typedReceiverClass; `self` itself included) — // through each hop's ONE callee (methodOf on the class the hop's receiver holds: the same lookup that proves that hop's own // edge, so a hop the resolve loop leaves hedged or split stops the walk) and that callee's declared whole result // (CallResultTypes::resultClassOf in its file; `Self` must name the very class the callee was found on). `?` / `.unwrap()` / // `.expect( … )` strip one Result / Option layer each; `.await` takes an `async fn`'s declared result, or the `Output` an // in-tree `impl IntoFuture` / `impl Future` states for the class (rustAwaitOutput). Anything else — a trait object or `impl // Trait` result, a generic `-> T`, a future used without its `.await`, a layer left unstripped, two records of one call that // disagree — is no class, and the call keeps its base reading. struct ChainValue { NodeId cls = kNoNode; std::uint8_t layers = 0; // Result / Option layers still to strip bool future = false; // an `async fn`'s call: the value is its future until `.await` bool operator==( const ChainValue& ) const = default; }; static constexpr int kChainHopCap = 64; // hops walked below one call; a longer chain is a floor (no class) struct KeyedRecord { std::uint64_t key = 0; // fileId << 32 | startByte const Binding* b = nullptr; }; mutable std::vector chainRecvCalls; // RecvCall records by the call's start mutable std::vector chainReturnTypes; // Rust ReturnType records by their def's start mutable std::vector> chainAwaitOutputs; // class → its `.await` value (cls kNoNode: two impls disagree) mutable std::vector> chainRootRefs; // the references at a chain root's start: ( key, index ) mutable bool chainTablesBuilt = false; static std::uint64_t chainKey( std::uint32_t fileId, std::uint32_t at ) noexcept { return hashutil::packPair( fileId, at ); } static std::span recordsAt( const std::vector& list, std::uint64_t key ) { const auto lo = std::ranges::lower_bound( list, key, {}, &KeyedRecord::key ); const auto hi = std::upper_bound( lo, list.end(), key, []( std::uint64_t k, const KeyedRecord& e ) { return k < e.key; } ); return { lo, hi }; } // the records a chain walk reads, in one pass over the bindings: RecvCall, Rust whole-result ReturnType, and the // `impl IntoFuture / Future for C` blocks with their `type Output = U;` items void collectChainRecords( std::vector& impls, std::vector& outputs ) const { for( const Binding& b : ing.bindings ) { const std::string_view var = b.var; if( b.kind == LocalBindKind::RecvCall ) // Rust records it alone (ingest_binds.h captureRustRecvCall) { chainRecvCalls.push_back( { chainKey( b.fileId, b.startByte ), &b } ); } else if( b.kind == LocalBindKind::ReturnType && b.resultIndex == kWholeResult && !b.typeName.empty() && b.fromSymbol < ing.symbols.size() && callResultFamilyOf( ing.symbols[ b.fromSymbol ].lang ) == CallResultFamily::Rust ) { chainReturnTypes.push_back( { chainKey( b.fileId, b.startByte ), &b } ); } else if( b.kind == LocalBindKind::ImplBlock && ( var == "IntoFuture" || var == "Future" ) && !b.typeName.empty() ) { impls.push_back( &b ); } else if( b.kind == LocalBindKind::TypeAlias && var == "Output" && !b.importedName.empty() ) { outputs.push_back( &b ); } } const auto byKey = []( const KeyedRecord& a, const KeyedRecord& b ) { return a.key < b.key; }; std::stable_sort( chainRecvCalls.begin(), chainRecvCalls.end(), byKey ); std::stable_sort( chainReturnTypes.begin(), chainReturnTypes.end(), byKey ); } // the references at a chain ROOT's start (where a depth-1 record's inner call starts), by key void indexChainRoots() const { std::vector rootKeys; for( const KeyedRecord& e : chainRecvCalls ) { if( e.b->resultIndex == 1 ) { rootKeys.push_back( chainKey( e.b->fileId, e.b->spanStart ) ); } } std::ranges::sort( rootKeys ); for( std::uint32_t i = 0; i < ing.references.size() && !rootKeys.empty(); ++i ) { const std::uint64_t k = chainKey( ing.references[ i ].fileId, ing.references[ i ].startByte ); if( std::ranges::binary_search( rootKeys, k ) ) { chainRootRefs.emplace_back( k, i ); } } std::ranges::sort( chainRootRefs ); } // an IntoFuture / Future impl's own `type Output` (the item its span holds), resolved like a written result type when it is a // plain path; no class for anything else (a generic, a reference, a tuple) ChainValue implAwaitOutput( const Binding& impl, std::span outputs ) const { const auto inImpl = [ & ]( const Binding* o ) { return o->fileId == impl.fileId && o->startByte >= impl.spanStart && o->startByte < impl.spanEnd; }; const auto it = std::ranges::find_if( outputs, inImpl ); if( it == outputs.end() ) { return {}; } const Binding& o = **it; const std::string_view text = o.importedName; const bool plainPath = std::ranges::all_of( text, []( char c ) { return std::isalnum( static_cast( c ) ) || c == '_' || c == ':'; } ); const auto [ path, last ] = CallResultTypes::splitLast( text, "::" ); return { plainPath ? types.rustResultClass( o.fileId, o.startByte, path.empty() ? std::string_view{} : text, last ) : kNoNode, 0, false }; } // class → its `.await` value; a class with two impls whose outputs disagree awaits to nothing known (cls kNoNode) void buildAwaitOutputs( std::span impls, std::span outputs ) const { for( const Binding* impl : impls ) { const NodeId cls = types.rustResultClass( impl->fileId, impl->spanStart, {}, impl->typeName ); if( cls != kNoNode ) { chainAwaitOutputs.emplace_back( cls, implAwaitOutput( *impl, outputs ) ); } } std::ranges::sort( chainAwaitOutputs, {}, &std::pair::first ); std::size_t kept = 0; for( std::size_t i = 0; i < chainAwaitOutputs.size(); ++i ) { const bool sameClass = kept > 0 && chainAwaitOutputs[ kept - 1 ].first == chainAwaitOutputs[ i ].first; if( sameClass && chainAwaitOutputs[ kept - 1 ].second != chainAwaitOutputs[ i ].second ) { chainAwaitOutputs[ kept - 1 ].second = ChainValue{}; } if( !sameClass ) { chainAwaitOutputs[ kept++ ] = chainAwaitOutputs[ i ]; } } chainAwaitOutputs.resize( kept ); } void buildChainTables() const { chainTablesBuilt = true; std::vector impls; std::vector outputs; collectChainRecords( impls, outputs ); indexChainRoots(); // `.await` reads std's IntoFuture: an in-tree TRAIT of either name makes every such impl unknown (an impl's own associated // `type IntoFuture = …` is no trait) NodeId one = kNoNode; const auto isTrait = [ & ]( NodeId c ) { return ing.symbols[ c ].kind == SymKind::Interface; }; if( types.classesNamed( "IntoFuture", CallResultFamily::Rust, isTrait, one ) == 0 && types.classesNamed( "Future", CallResultFamily::Rust, isTrait, one ) == 0 ) { buildAwaitOutputs( impls, outputs ); } } // the value `.await` yields on a `cls` (no layer, not a future): its in-tree IntoFuture / Future impl's `Output` std::optional rustAwaitOutput( NodeId cls ) const { if( !chainTablesBuilt ) { buildChainTables(); } const auto it = std::ranges::lower_bound( chainAwaitOutputs, cls, {}, &std::pair::first ); if( it == chainAwaitOutputs.end() || it->first != cls || it->second.cls == kNoNode ) { return std::nullopt; } return it->second; } // the value a call to `callee` returns, by its declared WHOLE result (`owner`: the class it was found on, which a written `Self` must be) std::optional declaredResult( NodeId callee, NodeId owner ) const { const Symbol& cs = ing.symbols[ callee ]; const Binding* one = nullptr; for( const KeyedRecord& e : recordsAt( chainReturnTypes, chainKey( cs.fileId, cs.sigStartByte ) ) ) { if( one != nullptr ) { return std::nullopt; } one = e.b; } if( one == nullptr || ( one->unwrapDepth & kDispatchResultBit ) != 0 ) { return std::nullopt; // no declared class: a unit, a generic `-> T`, a trait object / `impl Trait` } const NodeId cls = types.resultClassOf( *one, cs.lang ); if( cls == kNoNode || ( one->isFromAssignment && cls != owner ) ) { return std::nullopt; } return ChainValue{ cls, std::uint8_t( one->unwrapDepth & kUnwrapLayersMask ), ( one->unwrapDepth & kAwaitResultBit ) != 0 }; } // the operators a RecvCall record states between its inner call's value `v` and the receiver: `.await` first, then each `?` std::optional afterOperators( ChainValue v, const Binding& rec ) const { if( rec.isFromAssignment ) { if( v.future ) { v.future = false; } else if( v.layers == 0 ) { const std::optional out = rustAwaitOutput( v.cls ); if( !out.has_value() ) { return std::nullopt; } v = *out; } else { return std::nullopt; } } if( v.future || rec.unwrapDepth > v.layers ) { return std::nullopt; // a method on a future, or more `?` than layers } v.layers = std::uint8_t( v.layers - rec.unwrapDepth ); return v; } // the ONE member `name` class `cls` itself owns (rustQualifiedTypeOwns' reading of `T::f`), kNoNode when none or several NodeId ownedMember( NodeId cls, std::string_view name ) const { const auto m = methodsByType.find( typeKey( ing.symbols[ cls ].name, "::", name ) ); if( m == methodsByType.end() ) { return kNoNode; } NodeId one = kNoNode; std::size_t count = 0; for( NodeId c : m->second ) { if( ownedBy( c, cls ) ) { one = c; ++count; } } return count == 1 ? one : kNoNode; } // the ONE callee of member `name` on `cls` (methodOf's lookup), kNoNode when none or several NodeId uniqueMember( NodeId cls, std::string_view name ) const { return methodOf( ing.symbols[ cls ].name, name, false, cls ) && found.size() == 1 ? found[ 0 ] : kNoNode; } // the value the chain's ROOT call (`name` at byte `at`: a path call or a member call on a named receiver) returns. Every // Reference of that (file, byte, name) in that shape must agree. std::optional chainRootValue( const Reference& r, std::uint32_t at, std::string_view name ) const { const std::uint64_t key = chainKey( r.fileId, at ); std::optional agreed; for( auto it = std::ranges::lower_bound( chainRootRefs, std::pair{ key, 0u } ); it != chainRootRefs.end() && it->first == key; ++it ) { const Reference& root = ing.references[ it->second ]; if( root.role != RefRole::Call || std::string_view( root.calleeName ) != name || root.lang != r.lang ) { continue; } NodeId cls = kNoNode; NodeId callee = kNoNode; if( !root.qualifier.empty() ) // `T::f()`: the class the written qualifier names owns f (a path call: no member receiver) { cls = rustQualifierClass( root, rustWrittenQualifierOf( root ) ); callee = cls == kNoNode ? kNoNode : ownedMember( cls, name ); } else if( root.memberCall && !root.memberRoot.empty() ) // `x.f()` / `self.f()` / `self.a.f()` { const Chain ch = chainOf( root ); cls = ch.ctor.empty() ? typedReceiverClass( root, ch ) : kNoNode; callee = cls == kNoNode ? kNoNode : uniqueMember( cls, name ); } else { continue; // a hop (its own receiver is a call) or a bare call: no root } const std::optional v = callee == kNoNode ? std::nullopt : declaredResult( callee, cls ); if( !v.has_value() || ( agreed.has_value() && *agreed != *v ) ) { return std::nullopt; } agreed = v; } return agreed; } // the value the RECEIVER of the call `name` at byte `at` holds: its RecvCall records at hop `depth` (0: any — a Reference cannot // tell which of two same-named hops sharing a start byte it is, so all of them must agree), each read through its inner call std::optional rustChainReceiver( const Reference& r, std::uint32_t at, std::string_view name, std::uint8_t depth, int budget ) const { if( budget <= 0 ) { return std::nullopt; } if( !chainTablesBuilt ) { buildChainTables(); } std::optional agreed; for( const KeyedRecord& e : recordsAt( chainRecvCalls, chainKey( r.fileId, at ) ) ) { const Binding& rec = *e.b; if( std::string_view( rec.typeName ) != name || ( depth != 0 && rec.resultIndex != depth ) ) { continue; } std::optional v; if( rec.resultIndex <= 1 ) { v = chainRootValue( r, rec.spanStart, rec.var ); } else if( const std::optional recv = rustChainReceiver( r, rec.spanStart, rec.var, std::uint8_t( rec.resultIndex - 1 ), budget - 1 ); recv.has_value() ) { const bool unwrapCall = std::string_view( rec.var ) == "unwrap" || std::string_view( rec.var ) == "expect"; if( unwrapCall && recv->layers > 0 && !recv->future ) { v = ChainValue{ recv->cls, std::uint8_t( recv->layers - 1 ), false }; // `.unwrap()` strips a layer, as `?` does } else if( recv->layers == 0 && !recv->future ) { const NodeId callee = uniqueMember( recv->cls, rec.var ); v = callee == kNoNode ? std::nullopt : declaredResult( callee, recv->cls ); } } v = v.has_value() ? afterOperators( *v, rec ) : std::nullopt; if( !v.has_value() || ( agreed.has_value() && *agreed != *v ) ) { return std::nullopt; } agreed = v; } return agreed; } // the ONE class a Rust member call's receiver holds when that receiver is another call's result; kNoNode otherwise NodeId rustChainReceiverClass( const Reference& r ) const { const std::optional v = rustChainReceiver( r, r.startByte, r.calleeName, 0, kChainHopCap ); return v.has_value() && v->layers == 0 && !v->future ? v->cls : kNoNode; } // graph.h typeCallResults: a `let x = f().await` whose callee `f` is no `async fn` (`rt` states no await) awaits the class its // result names through that class's in-tree IntoFuture / Future impl (rustAwaitOutput); the class x then holds, kNoNode for none NodeId rustAwaitedCallResult( const Binding& cr, const Binding& rt, Lang lang ) const { if( ( cr.unwrapDepth & kAwaitResultBit ) == 0 || rt.unwrapDepth != 0 || callResultFamilyOf( lang ) != CallResultFamily::Rust ) { return kNoNode; } const NodeId cls = types.resultClassOf( rt, lang ); const std::optional out = cls == kNoNode ? std::nullopt : rustAwaitOutput( cls ); return out.has_value() && out->layers == ( cr.unwrapDepth & kUnwrapLayersMask ) ? out->cls : kNoNode; } // graph.h typeCallResults, per ReturnType record `rt` of the ONE proven callee: does it describe what the call result `cr` // binds — the same position, the unwrap depth the binding applies (a C++ rule-2 sink: the value or one pointer), and for a // Rust `T::f()` a T that reaches the callee's class (rustQualifierTypes) — and the class the local then holds (kNoNode: matched, // nothing to type). lane rust-self-chain: a Rust `let x = f().await` on a callee that is no `async fn` matches through the // class's IntoFuture / Future `Output` (rustAwaitedCallResult). struct CallResultMatch { bool matched = false; NodeId cls = kNoNode; }; CallResultMatch matchCallResult( const Reference& r, const Binding& cr, const Binding& rt, NodeId callee, bool rule2Sink ) const { if( rt.resultIndex != cr.resultIndex ) { return {}; } const Lang lang = ing.symbols[ callee ].lang; const bool direct = rule2Sink ? rt.unwrapDepth <= 1 : rt.unwrapDepth == cr.unwrapDepth; const NodeId awaited = direct ? kNoNode : rustAwaitedCallResult( cr, rt, lang ); if( ( !direct && awaited == kNoNode ) || !rustQualifierTypes( r, cr.importedName, callee, rt.isFromAssignment ) ) { return {}; } return { true, direct ? types.resultClassOf( rt, lang ) : awaited }; } // lane L6 (interface-typed dispatch): the TYPE a member call's receiver is recorded as — the one class or interface the // dispatch tier (ifacedispatch.h) asks about — and, for a Rust generic, the bound that typed it. `type` kNoNode: nothing // recorded. Rust (receiverLocalsOnly): a parameter, local or field typed only through a trait (noteDispatchWritten), reached // from a local or from `self` through the fields' resolved classes. The typed languages: the receiver root's written type // (rootClass: a typed parameter or local, a field of the caller's class) and its stated fields (fieldOf), resolved to ONE // in-tree class at the call site (classAtSite) — a field path only below a class no other in-tree class names. Never a bare // `this` / `self` / `super` or a class-name receiver: those name the caller's own class or a static call, no dispatch; // `this.f.m()` (lane receiver-fixes, TS-FIELD-SELF) is f's stated type, as for any other root. struct DispatchReceiver { NodeId type = kNoNode; std::string_view bound; }; DispatchReceiver dispatchReceiverOf( const Reference& r ) const { if( !active || r.fromSymbol >= ing.symbols.size() || !r.qualifier.empty() || !isMemberCallRef( r ) ) { return {}; } const Chain ch = chainOf( r ); if( !ch.valid || !ch.ctor.empty() || ch.root.empty() ) { return {}; } if( receiverLocalsOnly( r.lang ) ) { return traitDispatchReceiver( r, ch ); } // TS-FIELD-SELF: `this.f.m()` is a call on f's stated type, as `f.m()` on a typed local is; a bare `this.m()` (or one inside a // static member, whose `this` is the class object) names the caller's own class, no dispatch if( ( isThisRoot( ch.root ) && ( ch.path.empty() || ch.root != langFacts( r.lang ).instanceReceiver || callerIsStatic( r.fromSymbol ) ) ) || isSuperRoot( r, ch.root ) ) { return {}; } bool isStatic = false, superOnly = false; NodeId cls = kNoNode; std::string_view type = rootClass( r, ch, isStatic, superOnly, &cls ); if( type.empty() || isStatic || superOnly ) { return {}; } for( std::string_view rest = ch.path; !rest.empty(); ) // the stated field classes, by name { const std::size_t dot = rest.find( '.' ); const std::string_view field = rest.substr( 0, dot ); rest = dot == std::string_view::npos ? std::string_view{} : rest.substr( dot + 1 ); type = fieldOf( type, field ); cls = kNoNode; if( type.empty() ) { return {}; } } if( cls == kNoNode ) { cls = types.classAtSite( r.lang, r.fileId, r.startByte, type ); cls = cls != kNoNode ? cls : importedTypeClass( r, type ); if( cls != kNoNode && !ch.path.empty() && types.sameNamedClasses( cls ) != 1 ) { cls = kNoNode; // a field's type is known by NAME: below a name two in-tree classes share, a floor } } return { cls, {} }; } // lane receiver-fixes (TS-FIELD-SELF, PY-CTOR-ANNOT; dispatch classes #10 receiver peeling, #11 name-keyed identity): the // caller's own class when a member call's receiver is `this.` / `self.` whose last field the classes state as // an in-tree class or interface T (fieldOf: a written or constructed type, never a tombstone) that is neither the caller's // class nor one of its bases (inCone). The object such a call reaches is a T, so the caller's OWN definition of the callee // is no candidate: graph.h cuts it from the name tiers (before, `this.pub.provide()` with `pub: Provider` bound the // caller's own `provide` by name, and with that one same-file candidate the self-loop then vanished). kNoNode otherwise: // no path, a static side, an unknown field, a T the tree does not define, or no one class owning the caller. NodeId foreignFieldOwner( const Reference& r ) const { if( !active || r.fromSymbol >= ing.symbols.size() || !r.qualifier.empty() || !isMemberCallRef( r ) || receiverLocalsOnly( r.lang ) ) { return kNoNode; } const Chain ch = chainOf( r ); if( !ch.valid || !ch.ctor.empty() || ch.path.empty() || ch.root != langFacts( r.lang ).instanceReceiver || callerIsStatic( r.fromSymbol ) ) { return kNoNode; } const std::string_view own = callerClass( r.fromSymbol ); std::string_view type = own; for( std::string_view rest = ch.path; !rest.empty() && !type.empty(); ) { const std::size_t dot = rest.find( '.' ); type = fieldOf( type, rest.substr( 0, dot ) ); rest = dot == std::string_view::npos ? std::string_view{} : rest.substr( dot + 1 ); } if( own.empty() || type.empty() || type == own || inCone( own, type ) ) { return kNoNode; } key.assign( type ); return classNames.contains( key ) && !namesTypeAlias( r.lang, type ) ? selfClass( r.fromSymbol ) : kNoNode; } // a TypeScript `type T = …` is indexed as a Struct (queries/typescript/tags.scm @definition.type), and TS has no struct of its // own: T then names whatever the alias spells (a union, a base class), not "a class that is not the caller's". Any alias of the // name in the tree keeps foreignFieldOwner from cutting (a union holds the caller's class too; `type B = Base` may hold a D). bool namesTypeAlias( Lang lang, std::string_view name ) const { NodeId one = kNoNode; return callResultFamilyOf( lang ) == CallResultFamily::TypeScript && types.classesNamed( name, CallResultFamily::TypeScript, [ & ]( NodeId c ) { return ing.symbols[ c ].kind == SymKind::Struct; }, one ) != 0; } // TypeScript: a type name the caller's file imports by name from a module (`import { Router } from "./fmt/router"`) that the // import tables pin to no class — their export table holds functions and classes, never an interface — names the ONE // top-level INTERFACE of that name in the file the specifier resolved to, else a class of the caller's own file; kNoNode for none // or several (a re-export barrel: a floor), and for every other family (classAtSite's rows answer them) NodeId importedTypeClass( const Reference& r, std::string_view type ) const { if( callResultFamilyOf( r.lang ) != CallResultFamily::TypeScript ) { return kNoNode; } std::uint32_t module = UINT32_MAX; if( types.jsImportModules != nullptr ) { if( const auto it = types.jsImportModules->find( keyOf( r.fileId, '#', type ) ); it != types.jsImportModules->end() ) { module = it->second; } } return types.onlyClass( type, CallResultFamily::TypeScript, [ & ]( NodeId c ) { const std::uint32_t f = ing.symbols[ c ].fileId; return ( f == r.fileId || ( f == module && ing.symbols[ c ].kind == SymKind::Interface ) ) && types.levelOfClass( c ).wholeFile(); } ); } // Rust: a local or parameter typed through a trait, or `self.f` / `x.f.g` whose LAST field is a `Box` one (each // field above it read by its resolved class, as narrowTypedLocal reads them) DispatchReceiver traitDispatchReceiver( const Reference& r, const Chain& ch ) const { NodeId cls = kNoNode; if( isThisRoot( ch.root ) ) { if( ch.path.empty() ) { return {}; } cls = selfClass( r.fromSymbol ); } else if( const std::optional t = localSeenAt( r.fromSymbol, ch.root, r.startByte ); t.has_value() ) { if( ch.path.empty() ) { return { t->iface, t->bound }; } cls = t->cls; } for( std::string_view rest = ch.path; !rest.empty() && cls != kNoNode; ) { const std::size_t dot = rest.find( '.' ); const std::string_view field = rest.substr( 0, dot ); rest = dot == std::string_view::npos ? std::string_view{} : rest.substr( dot + 1 ); const std::string& k = keyOf( cls, '#', field ); if( rest.empty() ) { const auto it = memberIface.find( k ); return { it == memberIface.end() ? kNoNode : it->second, {} }; } const auto it = memberClass.find( k ); cls = it == memberClass.end() ? kNoNode : it->second; } return {}; } // rust-receivers (fix round 1): may a Rust call written `T::f()` type the locals its result binds through `to`, a member // whose declared result is written `Self` (graph.h typeCallResults asks only for those: a result the base read already // typed keeps its base rule)? Only when the qualifier as WRITTEN at the call site (`written`: the CallResult record's // whole path — the Reference keeps only its last segment), resolved like a written `x: T` (`Self` the impl's own class), // is the in-tree class that owns `to`. The canonical tier matches the callee's scope NAME alone, so std's `Path::new( p )`, // `fs::File::open()`, `std::path::PathBuf::from()`, a glob's or the prelude's `String::new()` all commit to an in-tree // type's member of that name (a base edge this does not change); an outside root, a std module, a glob that may supply, // a prelude name with no in-tree item in scope resolve to no class, and that `-> Self` types nothing. bool rustQualifiedTypeOwns( const Reference& r, std::string_view written, NodeId to ) const { if( r.qualifier.empty() && written.empty() ) { return true; // a bare or member call (no path written): the language's own lookup } const NodeId cls = rustQualifierClass( r, written ); if( cls == kNoNode ) { return false; } const auto it = methodsByType.find( typeKey( ing.symbols[ cls ].name, "::", ing.symbols[ to ].name ) ); return it != methodsByType.end() && std::ranges::find( it->second, to ) != it->second.end() && ownedBy( to, cls ); } // the ONE in-tree class a Rust call's written qualifier names, resolved like a written `x: T` (`Self`: the impl's class) NodeId rustQualifierClass( const Reference& r, std::string_view written ) const { const auto [ path, last ] = CallResultTypes::splitLast( written, "::" ); return path.empty() && last == "Self" ? selfClass( r.fromSymbol ) : types.rustResultClass( r.fileId, r.startByte, path.empty() ? std::string_view{} : written, last ); } // fc1: may the call `r` (written with qualifier `written`) type the locals its result binds through `to`? Another family's // own rules decided the edge, and so did a Rust bare call's and a free function's (an inline `mod`'s too). A Rust MEMBER // call `T::f()` whose result is written `Self` types them only when T reaches f's class (rustQualifiedTypeOwns). One // whose result is written by the type's own name (`-> PathBuf`, a path, inside Result / Option / Box) keeps the base // rule unless T resolves to ANOTHER in-tree class or provably leaves the tree (rustPathOutside): `std::path::PathBuf::from()` // never types a local onto an in-tree PathBuf whose `from` returns `PathBuf`, while a T the walk cannot follow (a module // a glob re-exports, a file outside every crate's tree) keeps the row base proved. bool rustQualifierTypes( const Reference& r, std::string_view written, NodeId to, bool spelledSelf ) const { if( callResultFamilyOf( r.lang ) != CallResultFamily::Rust ) { return true; } if( spelledSelf ) { return rustQualifiedTypeOwns( r, written, to ); } NodeId one = kNoNode; if( r.qualifier.empty() || ownerClass[ to ].empty() || types.classesNamed( ownerClass[ to ], CallResultFamily::Rust, []( NodeId ) { return true; }, one ) == 0 || rustQualifiedTypeOwns( r, written, to ) ) { return true; } if( rustQualifierClass( r, written ) != kNoNode ) { return false; } types.pathCut = false; // the top-level walk's own cut: a cut walk is no proof that the path stays in the tree const bool out = types.rustPathOutside( r.fileId, r.startByte, written ); return !out && !types.pathCut; } // RUST-PATH-OWNER: does the Rust path `path` written at byte `at` of `f` name an item outside the tree by what the file writes? Its // root bound by a `use` in force there, every one leading out (rustPathProvablyOutside, its root no package directory: a bare call's // reading of its `use`), else by such a `use` at the own level of a placed module a glob in force there names (`mod tests { use // super::*; }` over the file's `use std::path::PathBuf;`). A path of two or more segments may also start at an outside root no // `use` binds (`std::`, an extern crate) when no glob in force there is one the walk cannot place. A one-segment path no `use` // binds — a generic parameter `T::f()`, a name only a glob the walk cannot follow brings — is not. bool rustPathHeadLeavesTree( std::uint32_t f, std::uint32_t at, std::string_view path ) const { const auto leadsOut = [ & ]( std::uint32_t file, std::uint32_t pos, std::string_view p ) { return types.rustPathProvablyOutside( file, pos, p ) && !types.rustRootNamesTreePackage( file, pos, p ); }; const std::string_view head = path.substr( 0, path.find( "::" ) ); bool any = false; bool out = true; types.forEachRustUseAt( f, at, head, [ & ]( const Binding& b ) { any = true; out = out && leadsOut( f, b.startByte, b.importedName ); } ); if( any ) { return out && leadsOut( f, at, path ); } bool unplaced = false; // a glob in force the walk cannot place (`use crate::alias::*;` through a module re-exported by a `use`) bool viaGlob = false; types.forEachRustScopeAt( f, at, [ & ]( const CallResultTypes::Level& lv ) { types.forEachImport( f, "*", [ & ]( const Binding& g ) { if( g.kind != LocalBindKind::TypeImport || types.levelAt( f, g.startByte ) != lv || leadsOut( f, g.startByte, g.importedName ) ) { return; } std::uint32_t crate = CallResultTypes::kNoCrate; std::string module; if( !types.rustModuleOf( f, g.startByte, g.importedName, crate, module, 0 ) ) { unplaced = true; return; } NodeId inlineMod = kNoNode; std::uint32_t ownFile = 0; const auto mfs = types.rustModuleFiles( crate, module, inlineMod, ownFile ); const auto level = types.rustModuleLevel( inlineMod ); for( const std::uint32_t mf : mfs ) { types.forEachImport( mf, head, [ & ]( const Binding& b ) { if( b.kind == LocalBindKind::TypeImport && types.levelAt( mf, b.startByte ) == level ) { any = true; viaGlob = true; out = out && leadsOut( mf, b.startByte, b.importedName ); } } ); } } ); return any || unplaced; } ); if( unplaced ) { return false; } if( viaGlob ) { return out && leadsOut( f, at, path ); } return head.size() != path.size() && leadsOut( f, at, path ); } // RUST-PATH-OWNER: is the Rust path `path`'s head, at byte `at` of `f`, bound by a `use` in force there whose every path starts // in the tree (`crate::` / `self::` / `super::`, an in-tree crate's name): `pub use crate::wit::process::Command; impl Command {}` bool rustPathHeadUsedInTree( std::uint32_t f, std::uint32_t at, std::string_view path ) const { const std::string_view head = path.substr( 0, path.find( "::" ) ); bool any = false; bool inTree = true; types.forEachRustUseAt( f, at, head, [ & ]( const Binding& b ) { const std::string_view root = std::string_view( b.importedName ).substr( 0, std::string_view( b.importedName ).find( "::" ) ); any = true; inTree = inTree && ( root == "crate" || root == "self" || root == "super" || types.rustRootNamesTreePackage( f, b.startByte, b.importedName ) ); } ); return any && inTree; } // RUST-PATH-OWNER: what the canonical tier's answer to a Rust path call `T::m( .. )` proves. The tier holds every in-tree `m` // whose impl scope is NAMED T; the path names the ONE type T resolves to where it is written (the file's `use`s, its module // path), resolved like a written `x: T` (rustQualifierClass), and each candidate's owner is the in-tree class its impl is for // (selfClass). The invariant: two types, one name, never one `m`. // A candidate whose impl writes a type name that leads out of the tree where the impl is written (`use std::path::PathBuf; // impl From for PathBuf`, read like a call's path: rustPathHeadLeavesTree) is owned by that outside type, whatever in-tree // class shares the name. // * T names an in-tree class: its own candidates are the answer. With none of them placed, a candidate another class owns // (in the tree or outside it) leaves and one the walk cannot place stays; nothing left (the class's `m` is no indexed // definition) is declined, `cand` untouched so the decline lists the namesakes. // * T provably leads out of the tree, its root no package directory (`use std::path::PathBuf; PathBuf::from( s )`, the same // reading a bare call's `use` gets): an in-tree type's namesake is never it (one with no indexed class too, its impl's type // name a `use` into the tree). A candidate the outside type owns is a trait impl FOR it (`impl From for PathBuf`), // reached only when the argument is an X, which is not read: hedged. Nothing left: external=. // * T names no class the walk can place (two globs bring it, a glob it cannot follow): two owners among the candidates in the // caller's own crate, or a member there it cannot place beside another, split: every candidate stays (rustLadderSplit: // the ladder's own split when locality would keep them all, else hedged) — never a locality pick. One there, a crate the layout cannot // place, or a module's item among the candidates (`util::tool()`: the module path decides it) keeps the tier as before. enum class RustPathOwners : std::uint8_t { Keep, Hedge, Split, External, Decline }; static constexpr NodeId kRustOwnerUnread = kNoNode - 1; // rustPathOwnerMemo: not read yet static constexpr NodeId kRustOwnerOutside = kNoNode - 2; // an owner: the impl's own type name leads out of the tree where the impl is written static constexpr NodeId kRustOwnerInTree = kNoNode - 3; // an owner: no indexed class, but the impl's type name is a `use` into the tree mutable std::vector rustPathOwnerMemo; // per symbol: its owner as rustPathOwners reads it (sized on first use) RustPathOwners rustPathOwners( const Reference& r, std::vector& cand, bool canonical ) const { if( !canonical || callResultFamilyOf( r.lang ) != CallResultFamily::Rust || r.qualifier.empty() || cand.empty() ) { return RustPathOwners::Keep; } const std::string_view written = rustWrittenQualifierOf( r ); const NodeId cls = rustQualifierClass( r, written ); rw::SmallVec owners; // per candidate, in cand's order: its impl's in-tree class, kRustOwnerOutside, kRustOwnerInTree, or kNoNode (unplaced) if( rustPathOwnerMemo.size() != ing.symbols.size() ) { rustPathOwnerMemo.assign( ing.symbols.size(), kRustOwnerUnread ); } for( const NodeId c : cand ) { NodeId& owner = rustPathOwnerMemo[ c ]; // a candidate's owner is the candidate's own fact: read once per run if( owner == kRustOwnerUnread ) { const Symbol& cs = ing.symbols[ c ]; owner = rustPathHeadLeavesTree( cs.fileId, cs.sigStartByte, ownerClass[ c ] ) ? kRustOwnerOutside : selfClass( c ); owner = owner == kNoNode && rustPathHeadUsedInTree( cs.fileId, cs.sigStartByte, ownerClass[ c ] ) ? kRustOwnerInTree : owner; } owners.push_back( owner ); } const auto keepWhere = [ & ]( auto&& keep ) // cand narrowed to the candidates `keep( index )` holds, in order { std::size_t kept = 0; for( std::size_t i = 0; i < cand.size(); ++i ) { if( keep( i ) ) { cand[ kept++ ] = cand[ i ]; } } cand.resize( kept ); }; if( cls != kNoNode ) { const bool own = std::ranges::find( owners, cls ) != owners.end(); const auto mine = [ & ]( std::size_t i ) { return own ? owners[ i ] == cls : owners[ i ] == kNoNode || owners[ i ] == kRustOwnerInTree; }; bool any = false; for( std::size_t i = 0; i < cand.size() && !any; ++i ) { any = mine( i ); } if( !any ) { return RustPathOwners::Decline; // cand untouched: the declined site lists the namesakes it refused } keepWhere( mine ); return RustPathOwners::Keep; } if( rustPathHeadLeavesTree( r.fileId, r.startByte, written ) ) { // an in-tree class's member stays only as a trait's the path may name: `http_body::Body::size_hint( &s )` runs s's impl of // the trait Body. The inheritance names keep a base by its last segment, so `impl std::error::Error for Error` stays under // `std::io::Error::from( e )` too: hedged, a floor, never bound const std::string_view tail = CallResultTypes::splitLast( written, "::" ).second; keepWhere( [ & ]( std::size_t i ) { bool implementsTail = false; forEachBase( ownerClass[ cand[ i ] ], [ & ]( std::string_view b ) { implementsTail = implementsTail || CallResultTypes::splitLast( b, "::" ).second == tail; } ); return owners[ i ] == kRustOwnerOutside || owners[ i ] == kNoNode || implementsTail; } ); return cand.empty() ? RustPathOwners::External : RustPathOwners::Hedge; } // a module's item among them (`util::tool()`, an inline mod's fn) is the module path's question, not a type's: the tier as before if( cand.size() < 2 || std::ranges::any_of( cand, [ & ]( NodeId c ) { return ownerClass[ c ].empty(); } ) ) { return RustPathOwners::Keep; } // the types a path no `use` chooses may mean are the caller's own crate's (another crate's needs a `use` or its name); a crate the // layout cannot place, or one of them in it, leaves the tier as before const std::uint32_t crate = types.rustCrateOfFile( r.fileId ); if( crate == CallResultTypes::kNoCrate ) { return RustPathOwners::Keep; } std::size_t inCrate = 0; NodeId first = kNoNode; bool differ = false; for( std::size_t i = 0; i < cand.size(); ++i ) { if( types.rustCrateOfFile( ing.symbols[ cand[ i ] ].fileId ) != crate ) { continue; } first = inCrate == 0 ? owners[ i ] : first; differ = differ || owners[ i ] != first || owners[ i ] == kNoNode || owners[ i ] == kRustOwnerOutside || owners[ i ] == kRustOwnerInTree; ++inCrate; } return inCrate >= 2 && differ ? rustLadderSplit( r, cand ) : RustPathOwners::Keep; } // RUST-PATH-OWNER: how the ladder keeps a Split's candidates. Tier 1 or 2 holding all of them or none (tier 3's canonical rescue) // is its own split (Split: no locality tie-break narrows it); a strict subset there would be a locality pick among types the path // cannot tell apart, so every candidate is hedged instead (Hedge) RustPathOwners rustLadderSplit( const Reference& r, const std::vector& cand ) const { const std::string_view dir = includerDir( ing.files[ r.fileId ] ); std::size_t inFile = 0; std::size_t inDir = 0; for( const NodeId c : cand ) { const std::uint32_t f = ing.symbols[ c ].fileId; inFile += f == r.fileId ? 1u : 0u; inDir += includerDir( ing.files[ f ] ) == dir ? 1u : 0u; } const bool subset = inFile != 0 ? inFile < cand.size() : inDir != 0 && inDir < cand.size(); return subset ? RustPathOwners::Hedge : RustPathOwners::Split; } // rust-receivers: the ONE class `self` names inside `from` (or the method enclosing it): the in-tree class of the method's // owner name that owns the method (memberOwnerRuleOf — Rust: its own file and item scope, or the only class of the name); // kNoNode when none or several do NodeId selfClass( NodeId from ) const { const NodeId at = walkScopes( from, [ & ]( NodeId s ) { return !ownerClass[ s ].empty(); } ); if( at == kNoNode ) { return kNoNode; } NodeId one = kNoNode; const bool unique = types.classesNamed( ownerClass[ at ], callResultFamilyOf( ing.symbols[ at ].lang ), [ & ]( NodeId c ) { return ownedBy( at, c ); }, one ) == 1; return unique ? one : kNoNode; } // Python `feed = parser.feed; … feed( data )`: the alias names a typed object's method bool narrowAliasedMethod( const Reference& r ) const { if( r.recv != RecvKind::None || r.calleeName.empty() ) { return false; } NodeId scope = kNoNode; const std::pair* alias = aliasedMethod( r.fromSymbol, r.calleeName, scope ); if( alias == nullptr ) { return false; } if( isThisRoot( alias->first ) || alias->first == "cls" ) { return methodOf( callerClass( scope ), alias->second, false ); // `write = self.write`: the class's own member } const std::optional type = localAt( scope, alias->first, r.startByte ); return type.has_value() && !type->empty() && methodOf( unalias( r.fileId, *type ), alias->second, false ); } // the half of a module-alias proof that reads the CALL alone (LADDER-HOIST: once per call, not once per candidate): the module alias // `root` binds in the caller's file, and for a relative JS/TS specifier the in-tree path it joins to from the caller's // directory. nullopt: `root` is no module alias of that file. struct ModuleRoot { std::string_view source; // the alias's import path, as the file wrote it std::string joined; // a relative specifier joined onto the caller's directory; "" otherwise bool relative = false; // a `./` or `../` specifier (Go keeps its own rule) }; std::optional moduleRootOf( const Reference& r, std::string_view root ) const { const auto it = moduleAlias.find( keyOf( r.fileId, '#', root ) ); if( it == moduleAlias.end() || it->second.empty() ) { return std::nullopt; } ModuleRoot m; m.source = it->second; if( !m.source.starts_with( "./" ) && !m.source.starts_with( "../" ) ) { return m; // a package specifier (or a Go import path, which moduleRootNames reads as written) } // join the caller's directory with the relative specifier, then compare without the extension (or /index); // moduleRootNames answers Go before it reads this m.relative = true; std::vector parts; const auto push = [ & ]( std::string_view p ) { while( !p.empty() ) { const std::size_t slash = p.find( '/' ); const std::string_view seg = p.substr( 0, slash ); p = slash == std::string_view::npos ? std::string_view{} : p.substr( slash + 1 ); if( seg.empty() || seg == "." ) { continue; } if( seg == ".." ) { if( !parts.empty() ) { parts.pop_back(); } continue; } parts.push_back( seg ); } }; push( includerDir( rootRelPath( ing, r.fileId ) ) ); push( m.source ); for( std::string_view p : parts ) { if( !m.joined.empty() ) { m.joined.push_back( '/' ); } m.joined.append( p ); } return m; } // does the module alias `m` (moduleRootOf, at call `r`) name the file defining `c` bool moduleRootNames( const ModuleRoot& m, const Reference& r, NodeId c ) const { const std::string_view source = m.source; const std::string_view target = rootRelPath( ing, ing.symbols[ c ].fileId ); if( r.lang == Lang::Go ) { // an import path names a package: the candidate's own package import path (its go.mod's module path and the // directory below it — a nested module's `quoted/lib` is `example.com/qm/lib` — or the path a local replace // maps its directory to) proves it EXACTLY. A candidate with a path, or an import path some in-tree file // carries, is proven by nothing else: a directory that merely ends the path is another package const std::uint32_t cf = ing.symbols[ c ].fileId; if( goPackages != nullptr && ( goPackages->hasPath( cf ) || goPackages->known.contains( key.assign( source ) ) ) ) { return goPackages->names( cf, source ); } // no module facts name this path or the candidate (a tree with no go.mod): its directory must end the path, // segment-aligned const std::string_view dir = includerDir( target ); return !dir.empty() && source.size() >= dir.size() && source.ends_with( dir ) && ( source.size() == dir.size() || source[ source.size() - dir.size() - 1 ] == '/' ); } if( !m.relative ) { return false; // a package specifier: outside the tree, or resolved by a bundler this rule does not model } std::string_view stem = target; if( const std::size_t dot = stem.rfind( '.' ); dot != std::string_view::npos && stem.find( '/', dot ) == std::string_view::npos ) { stem = stem.substr( 0, dot ); } return stem == m.joined || ( stem.ends_with( "/index" ) && stem.substr( 0, stem.size() - 6 ) == m.joined ); } }; } // namespace rw