Visitar URL original
[ty] Compact reachable binding and declaration histories (#28349) · astral-sh/ruff@94efeaa · GitHub
Skip to content

Commit 94efeaa

Browse files
[ty] Compact reachable binding and declaration histories (#28349)
## Summary We retain duplicate binding and declaration lists because reachable histories include implicit unbound/undeclared entries that end-of-scope histories can discard. We now store those initial entries as one reachability constraint per place and intern the remaining definitions, reusing the corresponding end-of-scope declaration list when it matches.
1 parent 50020fb commit 94efeaa

2 files changed

Lines changed: 135 additions & 62 deletions

File tree

‎crates/ty_python_core/src/use_def.rs‎

Lines changed: 128 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -558,6 +558,16 @@ impl RetainedDeclarationsBuilder {
558558
self.ends.push(end)
559559
}
560560

561+
fn get(&self, index: InternedDeclarationsId) -> &[LiveDeclaration] {
562+
let end = self.ends[index];
563+
let start = if index.index() == 0 {
564+
0
565+
} else {
566+
self.ends[InternedDeclarationsId::new(index.index() - 1)]
567+
};
568+
&self.live_declarations[start as usize..end as usize]
569+
}
570+
561571
fn finish(
562572
self,
563573
reachability_constraints: &mut ReachabilityConstraintsBuilder,
@@ -587,9 +597,12 @@ impl Index<InternedDeclarationsId> for RetainedDeclarations {
587597
}
588598

589599
#[derive(Clone, Debug, Eq, PartialEq, get_size2::GetSize)]
590-
struct RetainedPlaceStates<T> {
591-
end_of_scope: T,
592-
reachable: T,
600+
struct RetainedPlaceStates {
601+
end_of_scope: InternedPlaceStateId,
602+
/// The reachable histories exclude their implicit initial unbound/undeclared entries.
603+
reachable: InternedPlaceStateId,
604+
/// Both initial entries have this reachability constraint and are reconstructed by iterators.
605+
initial_reachability: ScopedReachabilityConstraintId,
593606
}
594607

595608
#[derive(Debug, PartialEq, Eq, get_size2::GetSize, salsa::SalsaValue)]
@@ -665,7 +678,7 @@ struct UseDefMapExtra {
665678
multi_bindings_by_use: MultiBindingsByUse,
666679

667680
/// Retained [`PlaceState`] values for each member.
668-
member_states: FrozenIndexVec<ScopedMemberId, RetainedPlaceStates<InternedPlaceStateId>>,
681+
member_states: FrozenIndexVec<ScopedMemberId, RetainedPlaceStates>,
669682

670683
/// Snapshots of bindings used to resolve references from nested scopes.
671684
enclosing_snapshots: FrozenIndexVec<ScopedEnclosingSnapshotId, InternedEnclosingSnapshotId>,
@@ -808,7 +821,7 @@ pub struct UseDefMap<'db> {
808821
>,
809822

810823
/// Retained [`PlaceState`] values for each symbol.
811-
symbol_states: FrozenIndexVec<ScopedSymbolId, RetainedPlaceStates<InternedPlaceStateId>>,
824+
symbol_states: FrozenIndexVec<ScopedSymbolId, RetainedPlaceStates>,
812825

813826
/// Collection fields omitted when they would all be empty.
814827
extra: Option<Box<UseDefMapExtra>>,
@@ -1117,28 +1130,29 @@ impl<'db> UseDefMap<'db> {
11171130
&self,
11181131
place: ScopedPlaceId,
11191132
) -> BindingWithConstraintsIterator<'_, 'db> {
1120-
match place {
1121-
ScopedPlaceId::Symbol(symbol) => self.reachable_symbol_bindings(symbol),
1122-
ScopedPlaceId::Member(member) => self.reachable_member_bindings(member),
1133+
let state = match place {
1134+
ScopedPlaceId::Symbol(symbol) => &self.symbol_states[symbol],
1135+
ScopedPlaceId::Member(member) => &self.extra().member_states[member],
1136+
};
1137+
let bindings = &self.interned_bindings[state.reachable.bindings_id()];
1138+
BindingWithConstraintsIterator {
1139+
initial_unbound: Some(state.initial_reachability),
1140+
..self.bindings_iterator(bindings, BoundnessAnalysis::AssumeBound)
11231141
}
11241142
}
11251143

11261144
pub fn reachable_symbol_bindings(
11271145
&self,
11281146
symbol: ScopedSymbolId,
11291147
) -> BindingWithConstraintsIterator<'_, 'db> {
1130-
let place_state_id = self.symbol_states[symbol].reachable;
1131-
let bindings = &self.interned_bindings[place_state_id.bindings_id()];
1132-
self.bindings_iterator(bindings, BoundnessAnalysis::AssumeBound)
1148+
self.reachable_bindings(symbol.into())
11331149
}
11341150

11351151
pub fn reachable_member_bindings(
11361152
&self,
11371153
member: ScopedMemberId,
11381154
) -> BindingWithConstraintsIterator<'_, 'db> {
1139-
let place_state_id = self.extra().member_states[member].reachable;
1140-
let bindings = &self.interned_bindings[place_state_id.bindings_id()];
1141-
self.bindings_iterator(bindings, BoundnessAnalysis::AssumeBound)
1155+
self.reachable_bindings(member.into())
11421156
}
11431157

11441158
pub(crate) fn enclosing_snapshot(
@@ -1231,24 +1245,25 @@ impl<'db> UseDefMap<'db> {
12311245
&self,
12321246
symbol: ScopedSymbolId,
12331247
) -> DeclarationsIterator<'_, 'db> {
1234-
let place_state_id = self.symbol_states[symbol].reachable;
1235-
let declarations = &self.interned_declarations[place_state_id.declarations_id()];
1236-
self.declarations_iterator(declarations, BoundnessAnalysis::AssumeBound)
1248+
self.reachable_declarations(symbol.into())
12371249
}
12381250

12391251
pub fn reachable_member_declarations(
12401252
&self,
12411253
member: ScopedMemberId,
12421254
) -> DeclarationsIterator<'_, 'db> {
1243-
let place_state_id = self.extra().member_states[member].reachable;
1244-
let declarations = &self.interned_declarations[place_state_id.declarations_id()];
1245-
self.declarations_iterator(declarations, BoundnessAnalysis::AssumeBound)
1255+
self.reachable_declarations(member.into())
12461256
}
12471257

12481258
pub fn reachable_declarations(&self, place: ScopedPlaceId) -> DeclarationsIterator<'_, 'db> {
1249-
match place {
1250-
ScopedPlaceId::Symbol(symbol) => self.reachable_symbol_declarations(symbol),
1251-
ScopedPlaceId::Member(member) => self.reachable_member_declarations(member),
1259+
let state = match place {
1260+
ScopedPlaceId::Symbol(symbol) => &self.symbol_states[symbol],
1261+
ScopedPlaceId::Member(member) => &self.extra().member_states[member],
1262+
};
1263+
let declarations = &self.interned_declarations[state.reachable.declarations_id()];
1264+
DeclarationsIterator {
1265+
initial_undeclared: Some(state.initial_reachability),
1266+
..self.declarations_iterator(declarations, BoundnessAnalysis::AssumeBound)
12521267
}
12531268
}
12541269

@@ -1278,19 +1293,13 @@ impl<'db> UseDefMap<'db> {
12781293
BindingWithConstraintsIterator<'map, 'db>,
12791294
),
12801295
> + 'map {
1281-
self.symbol_states.iter_enumerated().map(
1282-
|(symbol_id, RetainedPlaceStates { reachable, .. })| {
1283-
let declarations = self.declarations_iterator(
1284-
&self.interned_declarations[reachable.declarations_id()],
1285-
BoundnessAnalysis::AssumeBound,
1286-
);
1287-
let bindings = self.bindings_iterator(
1288-
&self.interned_bindings[reachable.bindings_id()],
1289-
BoundnessAnalysis::AssumeBound,
1290-
);
1291-
(symbol_id, declarations, bindings)
1292-
},
1293-
)
1296+
self.symbol_states.indices().map(|symbol_id| {
1297+
(
1298+
symbol_id,
1299+
self.reachable_symbol_declarations(symbol_id),
1300+
self.reachable_symbol_bindings(symbol_id),
1301+
)
1302+
})
12941303
}
12951304

12961305
fn bindings_iterator<'map>(
@@ -1302,6 +1311,7 @@ impl<'db> UseDefMap<'db> {
13021311
all_definitions: &self.all_definitions,
13031312
constraint_tables: self.constraint_tables(),
13041313
boundness_analysis,
1314+
initial_unbound: None,
13051315
inner: bindings.iter(),
13061316
}
13071317
}
@@ -1315,6 +1325,7 @@ impl<'db> UseDefMap<'db> {
13151325
all_definitions: &self.all_definitions,
13161326
constraint_tables: self.constraint_tables(),
13171327
boundness_analysis,
1328+
initial_undeclared: None,
13181329
inner: declarations.iter(),
13191330
}
13201331
}
@@ -1355,6 +1366,7 @@ pub struct BindingWithConstraintsIterator<'map, 'db> {
13551366
all_definitions: &'map RetainedDefinitions<'db>,
13561367
constraint_tables: &'map ConstraintTables<'db>,
13571368
boundness_analysis: BoundnessAnalysis,
1369+
initial_unbound: Option<ScopedReachabilityConstraintId>,
13581370
inner: LiveBindingsIterator<'map>,
13591371
}
13601372

@@ -1376,6 +1388,18 @@ impl<'map, 'db> Iterator for BindingWithConstraintsIterator<'map, 'db> {
13761388
type Item = BindingWithConstraints<'map, 'db>;
13771389

13781390
fn next(&mut self) -> Option<Self::Item> {
1391+
if let Some(reachability_constraint) = self.initial_unbound.take() {
1392+
return Some(BindingWithConstraints {
1393+
binding: DefinitionState::Undefined,
1394+
binding_order: ScopedDefinitionId::UNBOUND,
1395+
narrowing_constraint: NarrowingEvaluator {
1396+
constraint: ScopedNarrowingConstraint::ALWAYS_TRUE,
1397+
constraint_tables: self.constraint_tables,
1398+
},
1399+
reachability_constraint,
1400+
});
1401+
}
1402+
13791403
self.inner
13801404
.next()
13811405
.map(|live_binding| BindingWithConstraints {
@@ -1428,6 +1452,7 @@ pub struct DeclarationsIterator<'map, 'db> {
14281452
all_definitions: &'map RetainedDefinitions<'db>,
14291453
constraint_tables: &'map ConstraintTables<'db>,
14301454
boundness_analysis: BoundnessAnalysis,
1455+
initial_undeclared: Option<ScopedReachabilityConstraintId>,
14311456
inner: LiveDeclarationsIterator<'map>,
14321457
}
14331458

@@ -1457,6 +1482,14 @@ impl<'db> Iterator for DeclarationsIterator<'_, 'db> {
14571482
type Item = DeclarationWithConstraint<'db>;
14581483

14591484
fn next(&mut self) -> Option<Self::Item> {
1485+
if let Some(reachability_constraint) = self.initial_undeclared.take() {
1486+
return Some(DeclarationWithConstraint {
1487+
declaration: DefinitionState::Undefined,
1488+
declaration_order: ScopedDefinitionId::UNBOUND,
1489+
reachability_constraint,
1490+
});
1491+
}
1492+
14601493
self.inner.next().map(
14611494
|LiveDeclaration {
14621495
declaration,
@@ -1476,10 +1509,24 @@ impl std::iter::FusedIterator for DeclarationsIterator<'_, '_> {}
14761509

14771510
#[derive(Clone, Debug, PartialEq, Eq, Hash, get_size2::GetSize)]
14781511
struct ReachableDefinitions {
1512+
/// Reachability when the place was first encountered. Reachable histories always retain this
1513+
/// initial unbound/undeclared state. End-of-scope histories can discard it when a later
1514+
/// definition shadows it. Keeping it separate lets the remaining definitions share storage.
1515+
initial_reachability: ScopedReachabilityConstraintId,
14791516
bindings: Bindings,
14801517
declarations: Declarations,
14811518
}
14821519

1520+
impl ReachableDefinitions {
1521+
fn new(initial_reachability: ScopedReachabilityConstraintId) -> Self {
1522+
Self {
1523+
initial_reachability,
1524+
bindings: Bindings::default(),
1525+
declarations: Declarations::default(),
1526+
}
1527+
}
1528+
}
1529+
14831530
/// A snapshot of the definitions and constraints state at a particular point in control flow.
14841531
#[derive(Clone, Debug)]
14851532
pub(super) struct FlowSnapshot {
@@ -2033,10 +2080,7 @@ impl<'db> UseDefMapBuilder<'db> {
20332080
debug_assert_eq!(symbol, new_place);
20342081
let new_place = self
20352082
.reachable_symbol_definitions
2036-
.push(ReachableDefinitions {
2037-
bindings: Bindings::unbound(self.reachability),
2038-
declarations: Declarations::undeclared(self.reachability),
2039-
});
2083+
.push(ReachableDefinitions::new(self.reachability));
20402084
debug_assert_eq!(symbol, new_place);
20412085
}
20422086
ScopedPlaceId::Member(member) => {
@@ -2047,10 +2091,7 @@ impl<'db> UseDefMapBuilder<'db> {
20472091
debug_assert_eq!(member, new_place);
20482092
let new_place = self
20492093
.reachable_member_definitions
2050-
.push(ReachableDefinitions {
2051-
bindings: Bindings::unbound(self.reachability),
2052-
declarations: Declarations::undeclared(self.reachability),
2053-
});
2094+
.push(ReachableDefinitions::new(self.reachability));
20542095
debug_assert_eq!(member, new_place);
20552096
}
20562097
}
@@ -3022,15 +3063,17 @@ impl<'db> UseDefMapBuilder<'db> {
30223063
);
30233064
let end_of_scope_members =
30243065
Self::intern_end_of_scope_members(member_states, &mut place_state_interner);
3025-
let reachable_definitions_by_symbol = Self::intern_place_states(
3066+
let symbol_states = Self::intern_reachable_place_states(
3067+
end_of_scope_symbols,
30263068
self.reachable_symbol_definitions,
3027-
|definitions| (definitions.bindings, definitions.declarations),
30283069
&mut place_state_interner,
3070+
&mut self.reachability_constraints,
30293071
);
3030-
let reachable_definitions_by_member = Self::intern_place_states(
3072+
let member_states = Self::intern_reachable_place_states(
3073+
end_of_scope_members,
30313074
self.reachable_member_definitions,
3032-
|definitions| (definitions.bindings, definitions.declarations),
30333075
&mut place_state_interner,
3076+
&mut self.reachability_constraints,
30343077
);
30353078
let enclosing_snapshots =
30363079
Self::intern_enclosing_snapshots(self.enclosing_snapshots, &mut place_state_interner);
@@ -3069,10 +3112,6 @@ impl<'db> UseDefMapBuilder<'db> {
30693112
}
30703113
}
30713114
self.reachability_constraints.mark_used(self.reachability);
3072-
let symbol_states =
3073-
Self::zip_place_states(end_of_scope_symbols, reachable_definitions_by_symbol);
3074-
let member_states =
3075-
Self::zip_place_states(end_of_scope_members, reachable_definitions_by_member);
30763115
let multi_bindings_by_use = MultiBindingsByUse::from_map(self.multi_bindings_by_use);
30773116
let loop_headers = self.loop_headers;
30783117
let mut boolean_test_roots = self.boolean_test_roots;
@@ -3125,18 +3164,48 @@ impl<'db> UseDefMapBuilder<'db> {
31253164
}
31263165
}
31273166

3128-
fn zip_place_states<I: Idx, T>(
3129-
end_of_scope: IndexVec<I, T>,
3130-
reachable: IndexVec<I, T>,
3131-
) -> FrozenIndexVec<I, RetainedPlaceStates<T>> {
3167+
/// Retains reachable definitions without duplicating their initial unbound/undeclared entries.
3168+
fn intern_reachable_place_states<I: Idx>(
3169+
end_of_scope: IndexVec<I, InternedPlaceStateId>,
3170+
reachable: IndexVec<I, ReachableDefinitions>,
3171+
place_state_interner: &mut PlaceStateInterner,
3172+
reachability_constraints: &mut ReachabilityConstraintsBuilder,
3173+
) -> FrozenIndexVec<I, RetainedPlaceStates> {
31323174
assert_eq!(end_of_scope.len(), reachable.len());
31333175

31343176
end_of_scope
31353177
.into_iter()
31363178
.zip(reachable)
3137-
.map(|(end_of_scope, reachable)| RetainedPlaceStates {
3138-
end_of_scope,
3139-
reachable,
3179+
.map(|(end_of_scope, definitions)| {
3180+
let ReachableDefinitions {
3181+
initial_reachability,
3182+
bindings,
3183+
declarations,
3184+
} = definitions;
3185+
// The implicit entries are reconstructed by iterators, so their constraint does
3186+
// not appear in the binding/declaration tables visited during compaction.
3187+
reachability_constraints.mark_used(initial_reachability);
3188+
3189+
// A place with one declaration commonly has identical end-of-scope and reachable
3190+
// declarations after removing the initial undeclared entry. Compare this pair
3191+
// directly because end-of-scope declarations are not all interned.
3192+
let declarations_id = if place_state_interner
3193+
.interned_declarations
3194+
.get(end_of_scope.declarations_id())
3195+
== declarations.as_slice()
3196+
{
3197+
end_of_scope.declarations_id()
3198+
} else {
3199+
place_state_interner.intern_declarations(declarations)
3200+
};
3201+
RetainedPlaceStates {
3202+
end_of_scope,
3203+
reachable: InternedPlaceStateId(
3204+
place_state_interner.intern_bindings(&bindings),
3205+
declarations_id,
3206+
),
3207+
initial_reachability,
3208+
}
31403209
})
31413210
.collect()
31423211
}

‎crates/ty_python_core/src/use_def/place_state.rs‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -62,7 +62,7 @@ impl ScopedDefinitionId {
6262
/// unbound or undeclared at a given usage site.
6363
/// When creating a use-def-map builder, we always add an empty `DefinitionState::Undefined` definition
6464
/// at index 0, so this ID is always present.
65-
const UNBOUND: ScopedDefinitionId = ScopedDefinitionId::from_u32(0);
65+
pub(super) const UNBOUND: ScopedDefinitionId = ScopedDefinitionId::from_u32(0);
6666

6767
pub(crate) fn is_unbound(self) -> bool {
6868
self == Self::UNBOUND
@@ -369,8 +369,12 @@ impl Bindings {
369369
) {
370370
// If we are in a class scope, and the unbound name binding was previously visible, but we will
371371
// now replace it, record the narrowing constraints on it:
372-
if is_class_scope && is_place_name && self.live_bindings[0].binding().is_unbound() {
373-
self.unbound_narrowing_constraint = Some(self.live_bindings[0].narrowing_constraint);
372+
if is_class_scope
373+
&& is_place_name
374+
&& let Some(binding) = self.live_bindings.first()
375+
&& binding.binding().is_unbound()
376+
{
377+
self.unbound_narrowing_constraint = Some(binding.narrowing_constraint);
374378
}
375379
// If the new binding is a shadowing type, it replaces previous live bindings in this path
376380
// (unless they're marked as not shadowable), and has no constraints.

0 commit comments

Comments
 (0)