Repository: astral-sh/ruff
File: crates/ty_python_semantic/src/types/constraints.rs (Rust)

Code before:
        #[derive(Default)]
        struct Bounds<'db> {
            lower: FxIndexSet<Type<'db>>,
            upper: FxIndexSet<Type<'db>>,
        }

        impl<'db> Bounds<'db> {
            fn add_lower(&mut self, _db: &'db dyn Db, ty: Type<'db>) {
                // Lower bounds are unioned. Our type representation is in DNF, so unioning a new
                // element is typically cheap (in that it does not involve a combinatorial
                // explosion from distributing the clause through an existing disjunction). So we
                // don't need to be as clever here as in `add_upper`.
                self.lower.insert(ty);
            }

            fn add_upper(&mut self, db: &'db dyn Db, ty: Type<'db>) {
                // Upper bounds are intersectioned. If `ty` is a union, that involves distributing
                // the union elements through the existing type. That makes it worth checking first
                // whether any of the types in the upper bound are redundant.

                // First check if there's an existing upper bound clause that is a subtype of the
                // new type. If so, adding the new type does nothing to the intersection.
                if self
                    .upper
                    .iter()
                    .any(|existing| existing.is_subtype_of(db, ty))
                {
                    return;
                }

                // Otherwise remove any existing clauses that are a supertype of the new type,
                // since the intersection will clip them to the new type.
                self.upper
                    .retain(|existing| !ty.is_subtype_of(db, *existing));
                self.upper.insert(ty);
            }
        }

        #[salsa::tracked(returns(ref), heap_size=ruff_memory_usage::heap_size)]
        fn solutions_inner<'db>(
            db: &'db dyn Db,
            interior: InteriorNode<'db>,
        ) -> Vec<Solution<'db>> {
            // Sort the constraints in each path by their `source_order`s, to ensure that we construct
            // any unions or intersections in our type mappings in a stable order. Constraints might
            // come out of `PathAssignment`s with identical `source_order`s, but if they do, those
            // "tied" constraints will still be ordered in a stable way. So we need a stable sort to
            // retain that stable per-tie ordering.
            let mut sorted_paths = Vec::new();
            Node::Interior(interior).for_each_path(db, |path| {
                let mut path: Vec<_> = path.positive_constraints().collect();

Review comment (performance):
We also have `Type::is_redundant_with`, which is more aggressive in some cases with considering gradual types redundant if they are "gradually equivalent" to another gradual type (e.g. `Any` is not a subtype of `Any`, but it is redundant with `Any`).

And perhaps even more usefully, `is_redundant_with` is Salsa-cached, where `is_subtype_of` is not. Meaning you could share this judgment with other places (mostly union simplification) where `is_redundant_with` is already used.

So it might be worth seeing what the impact is of switching to that here?

Code after:
        #[derive(Default)]
        struct Bounds<'db> {
            lower: FxIndexSet<Type<'db>>,
            upper: FxIndexSet<Type<'db>>,
        }

        impl<'db> Bounds<'db> {
            fn add_lower(&mut self, _db: &'db dyn Db, ty: Type<'db>) {
                // Lower bounds are unioned. Our type representation is in DNF, so unioning a new
                // element is typically cheap (in that it does not involve a combinatorial
                // explosion from distributing the clause through an existing disjunction). So we
                // don't need to be as clever here as in `add_upper`.
                self.lower.insert(ty);
            }

            fn add_upper(&mut self, db: &'db dyn Db, ty: Type<'db>) {
                // Upper bounds are intersectioned. If `ty` is a union, that involves distributing
                // the union elements through the existing type. That makes it worth checking first
                // whether any of the types in the upper bound are redundant.

                // First check if there's an existing upper bound clause that is a subtype of the
                // new type. If so, adding the new type does nothing to the intersection.
                if self
                    .upper
                    .iter()
                    .any(|existing| existing.is_redundant_with(db, ty))
                {
                    return;
                }

                // Otherwise remove any existing clauses that are a supertype of the new type,
                // since the intersection will clip them to the new type.
                self.upper
                    .retain(|existing| !ty.is_redundant_with(db, *existing));
                self.upper.insert(ty);
            }
        }

        #[salsa::tracked(returns(ref), heap_size=ruff_memory_usage::heap_size)]
        fn solutions_inner<'db>(
            db: &'db dyn Db,
            interior: InteriorNode<'db>,
        ) -> Vec<Solution<'db>> {
            // Sort the constraints in each path by their `source_order`s, to ensure that we construct
            // any unions or intersections in our type mappings in a stable order. Constraints might
            // come out of `PathAssignment`s with identical `source_order`s, but if they do, those
            // "tied" constraints will still be ordered in a stable way. So we need a stable sort to
            // retain that stable per-tie ordering.
            let mut sorted_paths = Vec::new();
            Node::Interior(interior).for_each_path(db, |path| {
                let mut path: Vec<_> = path.positive_constraints().collect();