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

Code before:
                Node::AlwaysTrue,
                self_interior.source_order(db),
            ),
            (Node::AlwaysFalse, _) => other.with_adjusted_source_order(db, other_offset),
            (_, Node::AlwaysFalse) => self,
            (Node::Interior(self_interior), Node::Interior(other_interior)) => {
                self_interior.or(db, other_interior, other_offset)
            }
        }
    }

    /// Combine an iterator of nodes into a single node using an associative operator.
    ///
    /// Because the operator is associative, we don't have to combine the nodes left to right; we
    /// can instead combine them in a "tree-like" way:
    ///
    /// ```text
    /// linear:  (((((a ∨ b) ∨ c) ∨ d) ∨ e) ∨ f) ∨ g
    /// tree:    ((a ∨ b) ∨ (c ∨ d)) ∨ ((e ∨ f) ∨ g)
    /// ```
    ///
    /// We have to invoke the operator the same number of times. But BDD operators are often much
    /// cheaper when the operands are small, and with the tree shape, many more of the invocations
    /// are performed on small BDDs.
    ///
    /// You must also provide the "zero" and "one" units of the operator. The "zero" is the value
    /// that has no effect (`0 ∨ a = a`). It is returned if the iterator is empty. The "one" is the
    /// value that saturates (`1 ∨ a = 1`). We use this to short-circuit; if any element BDD or any
    /// intermediate result evaluates to "one", we can return early.
    fn tree_fold(
        db: &'db dyn Db,
        nodes: impl Iterator<Item = Self>,
        zero: Self,
        one: Self,
        mut combine: impl FnMut(Self, &'db dyn Db, Self) -> Self,
    ) -> Self {
        // If the iterator is small enough, we don't have to be clever; just fold the elements
        // using the operator and return.
        let (_, max_size) = nodes.size_hint();
        #[expect(clippy::items_after_statements)]
        const MIN_SIZE_TO_BE_CLEVER: usize = 4;
        if max_size.is_some_and(|size| size <= MIN_SIZE_TO_BE_CLEVER) {
            return nodes.fold(zero, |result, node| combine(result, db, node));
        }

        // To implement the "linear" shape described above, we could collect the iterator elements
        // into a vector, and then use the fold at the bottom of this method to combine the
        // elements using the operator.
        //
        // To implement the "tree" shape, we also maintain a "depth" for each element of the
        // vector, which indicates how many times the operator has been applied to the element.

Review comment (suggestion):
It's unclear to me why this is algorithmically cheaper. If the constraint sets are all disjoint, this is equivalent (modulo node ordering, which we can really control here). The worst case is also equivalent. In any case, both BDD constructions operate on the same set of pairs of nodes — so we end up ORing two medium sized constraint sets instead of a large constraint set with a small one, which should end up being equivalent? I may be missing something here, given that the benchmarks agree this is an improvement.

Code after:
                Node::AlwaysTrue,
                other_interior.source_order(db) + other_offset,
            ),
            (Node::Interior(self_interior), Node::AlwaysTrue) => Node::new(
                db,
                self_interior.constraint(db),
                Node::AlwaysTrue,
                Node::AlwaysTrue,
                self_interior.source_order(db),
            ),
            (Node::AlwaysFalse, _) => other.with_adjusted_source_order(db, other_offset),
            (_, Node::AlwaysFalse) => self,
            (Node::Interior(self_interior), Node::Interior(other_interior)) => {
                self_interior.or(db, other_interior, other_offset)
            }
        }
    }

    /// Combine an iterator of nodes into a single node using an associative operator.
    ///
    /// Because the operator is associative, we don't have to combine the nodes left to right; we
    /// can instead combine them in a "tree-like" way:
    ///
    /// ```text
    /// linear:  (((((a ∨ b) ∨ c) ∨ d) ∨ e) ∨ f) ∨ g
    /// tree:    ((a ∨ b) ∨ (c ∨ d)) ∨ ((e ∨ f) ∨ g)
    /// ```
    ///
    /// We have to invoke the operator the same number of times. But BDD operators are often much
    /// cheaper when the operands are small, and with the tree shape, many more of the invocations
    /// are performed on small BDDs.
    ///
    /// You must also provide the "zero" and "one" units of the operator. The "zero" is the value
    /// that has no effect (`0 ∨ a = a`). It is returned if the iterator is empty. The "one" is the
    /// value that saturates (`1 ∨ a = 1`). We use this to short-circuit; if any element BDD or any
    /// intermediate result evaluates to "one", we can return early.
    fn tree_fold(
        db: &'db dyn Db,
        nodes: impl Iterator<Item = Self>,
        zero: Self,
        one: Self,
        mut combine: impl FnMut(Self, &'db dyn Db, Self) -> Self,
    ) -> Self {
        // To implement the "linear" shape described above, we could collect the iterator elements
        // into a vector, and then use the fold at the bottom of this method to combine the
        // elements using the operator.
        //
        // To implement the "tree" shape, we also maintain a "depth" for each element of the
        // vector, which indicates how many times the operator has been applied to the element.
        // As we collect elements into the vector, we keep it capped at a length `O(log n)` of the
        // number of elements seen so far. To do that, whenever the last two elements of the vector