Find transitive closure for given constraints on type variables. Transitive closure gives maximal set of lower/upper bounds for each type variable, such that we cannot deduce any further bounds by chaining other existing bounds. The transitive closure is represented by: * A set o
(
tvars: list[TypeVarId], constraints: list[Constraint]
)
| 404 | |
| 405 | |
| 406 | def transitive_closure( |
| 407 | tvars: list[TypeVarId], constraints: list[Constraint] |
| 408 | ) -> tuple[Graph, Bounds, Bounds]: |
| 409 | """Find transitive closure for given constraints on type variables. |
| 410 | |
| 411 | Transitive closure gives maximal set of lower/upper bounds for each type variable, |
| 412 | such that we cannot deduce any further bounds by chaining other existing bounds. |
| 413 | |
| 414 | The transitive closure is represented by: |
| 415 | * A set of lower and upper bounds for each type variable, where only constant and |
| 416 | non-linear terms are included in the bounds. |
| 417 | * A graph of linear constraints between type variables (represented as a set of pairs) |
| 418 | Such separation simplifies reasoning, and allows an efficient and simple incremental |
| 419 | transitive closure algorithm that we use here. |
| 420 | |
| 421 | For example if we have initial constraints [T <: S, S <: U, U <: int], the transitive |
| 422 | closure is given by: |
| 423 | * {} <: T <: {int} |
| 424 | * {} <: S <: {int} |
| 425 | * {} <: U <: {int} |
| 426 | * {T <: S, S <: U, T <: U} |
| 427 | """ |
| 428 | uppers: Bounds = defaultdict(set) |
| 429 | lowers: Bounds = defaultdict(set) |
| 430 | graph: Graph = {(tv, tv) for tv in tvars} |
| 431 | |
| 432 | remaining = set(constraints) |
| 433 | while remaining: |
| 434 | c = remaining.pop() |
| 435 | # Note that ParamSpec constraint P <: Q may be considered linear only if Q has no prefix, |
| 436 | # for cases like P <: Concatenate[T, Q] we should consider this non-linear and put {P} and |
| 437 | # {T, Q} into separate SCCs. Similarly, Ts <: Tuple[*Us] considered linear, while |
| 438 | # Ts <: Tuple[*Us, U] is non-linear. |
| 439 | is_linear, target_id = find_linear(c) |
| 440 | if is_linear and target_id in tvars: |
| 441 | assert target_id is not None |
| 442 | if c.op == SUBTYPE_OF: |
| 443 | lower, upper = c.type_var, target_id |
| 444 | else: |
| 445 | lower, upper = target_id, c.type_var |
| 446 | if (lower, upper) in graph: |
| 447 | continue |
| 448 | graph |= { |
| 449 | (l, u) for l in tvars for u in tvars if (l, lower) in graph and (upper, u) in graph |
| 450 | } |
| 451 | for u in tvars: |
| 452 | if (upper, u) in graph: |
| 453 | lowers[u] |= lowers[lower] |
| 454 | for l in tvars: |
| 455 | if (l, lower) in graph: |
| 456 | uppers[l] |= uppers[upper] |
| 457 | for lt in lowers[lower]: |
| 458 | for ut in uppers[upper]: |
| 459 | add_secondary_constraints(remaining, lt, ut) |
| 460 | elif c.op == SUBTYPE_OF: |
| 461 | if c.target in uppers[c.type_var]: |
| 462 | continue |
| 463 | for l in tvars: |
searching dependent graphs…