src/Psalm/Type/Algebra.php
public static function simplifyCNF(array $clauses)
    {
        $cloned_clauses = [];

        // avoid strict duplicates
        foreach ($clauses as $clause) {
            $unique_clause = clone $clause;
            foreach ($unique_clause->possibilities as $var_id => $possibilities) {
                if (count($possibilities)) {
                    $unique_clause->possibilities[$var_id] = array_unique($possibilities);
                }
            }
            $cloned_clauses[$clause->getHash()] = $unique_clause;
        }

        // remove impossible types
        foreach ($cloned_clauses as $clause_a) {
            if (count($clause_a->possibilities) !== 1 || count(array_values($clause_a->possibilities)[0]) !== 1) {
                continue;
            }

            if (!$clause_a->reconcilable || $clause_a->wedge) {
                continue;
            }

            $clause_var = array_keys($clause_a->possibilities)[0];
            $only_type = array_pop(array_values($clause_a->possibilities)[0]);
            $negated_clause_type = self::negateType($only_type);

            foreach ($cloned_clauses as $clause_b) {
                if ($clause_a === $clause_b || !$clause_b->reconcilable || $clause_b->wedge) {
                    continue;
                }

                if (isset($clause_b->possibilities[$clause_var]) &&
                    in_array($negated_clause_type, $clause_b->possibilities[$clause_var], true)
                ) {
                    $clause_b->possibilities[$clause_var] = array_filter(
                        $clause_b->possibilities[$clause_var],
                        /**
                         * @param string $possible_type
                         *
                         * @return bool
                         */
                        function ($possible_type) use ($negated_clause_type) {
                            return $possible_type !== $negated_clause_type;
                        }
                    );

                    if (count($clause_b->possibilities[$clause_var]) === 0) {
                        unset($clause_b->possibilities[$clause_var]);
                        $clause_b->impossibilities = null;
                    }
                }
            }
        }

        $deduped_clauses = [];

        // avoid strict duplicates
        foreach ($cloned_clauses as $clause) {
            $deduped_clauses[$clause->getHash()] = clone $clause;
        }

        $deduped_clauses = array_filter(
            $deduped_clauses,
            /**
             * @return bool
             */
            function (Clause $clause) {
                return count($clause->possibilities) || $clause->wedge;
            }
        );

        $simplified_clauses = [];

        foreach ($deduped_clauses as $clause_a) {
            $is_redundant = false;

            foreach ($deduped_clauses as $clause_b) {
                if ($clause_a === $clause_b
                    || !$clause_b->reconcilable
                    || $clause_b->wedge
                    || $clause_a->wedge
                ) {
                    continue;
                }

                if ($clause_a->contains($clause_b)) {
                    $is_redundant = true;
                    break;
                }
            }

            if (!$is_redundant) {
                $simplified_clauses[] = $clause_a;
            }
        }

        return $simplified_clauses;
    }
public static function simplifyCNF(array $clauses)
    {
        $cloned_clauses = [];

        // avoid strict duplicates
        foreach ($clauses as $clause) {
            $unique_clause = clone $clause;
            foreach ($unique_clause->possibilities as $var_id => $possibilities) {
                if (count($possibilities)) {
                    $unique_clause->possibilities[$var_id] = array_unique($possibilities);
                }
            }
            $cloned_clauses[$clause->getHash()] = $unique_clause;
        }

        // remove impossible types
        foreach ($cloned_clauses as $clause_a) {
            if (count($clause_a->possibilities) !== 1 || count(array_values($clause_a->possibilities)[0]) !== 1) {
                continue;
            }

            if (!$clause_a->reconcilable || $clause_a->wedge) {
                continue;
            }

            $clause_var = array_keys($clause_a->possibilities)[0];
            $only_type = array_pop(array_values($clause_a->possibilities)[0]);
            $negated_clause_type = self::negateType($only_type);

            foreach ($cloned_clauses as $clause_b) {
                if ($clause_a === $clause_b || !$clause_b->reconcilable || $clause_b->wedge) {
                    continue;
                }

                if (isset($clause_b->possibilities[$clause_var]) &&
                    in_array($negated_clause_type, $clause_b->possibilities[$clause_var], true)
                ) {
                    $clause_b->possibilities[$clause_var] = array_filter(
                        $clause_b->possibilities[$clause_var],
                        /**
                         * @param string $possible_type
                         *
                         * @return bool
                         */
                        function ($possible_type) use ($negated_clause_type) {
                            return $possible_type !== $negated_clause_type;
                        }
                    );

                    if (count($clause_b->possibilities[$clause_var]) === 0) {
                        unset($clause_b->possibilities[$clause_var]);
                        $clause_b->impossibilities = null;
                    }
                }
            }
        }

        $deduped_clauses = [];

        // avoid strict duplicates
        foreach ($cloned_clauses as $clause) {
            $deduped_clauses[$clause->getHash()] = clone $clause;
        }

        $deduped_clauses = array_filter(
            $deduped_clauses,
            /**
             * @return bool
             */
            function (Clause $clause) {
                return count($clause->possibilities) || $clause->wedge;
            }
        );

        $simplified_clauses = [];

        foreach ($deduped_clauses as $clause_a) {
            $is_redundant = false;

            foreach ($deduped_clauses as $clause_b) {
                if ($clause_a === $clause_b
                    || !$clause_b->reconcilable
                    || $clause_b->wedge
                    || $clause_a->wedge
                ) {
                    continue;
                }

                if ($clause_a->contains($clause_b)) {
                    $is_redundant = true;
                    break;
                }
            }

            if (!$is_redundant) {
                $simplified_clauses[] = $clause_a;
            }
        }

        return $simplified_clauses;
    }
public static function simplifyCNF ( array $ clauses ) { $ cloned_clauses = [ ] ; // avoid strict duplicates foreach ( $ clauses as $ clause ) { $ unique_clause = clone $ clause ; foreach ( $ unique_clause -> possibilities as $ var_id => $ possibilities ) { if ( count ( $ possibilities ) ) { $ unique_clause -> possibilities [ $ var_id ] = array_unique ( $ possibilities ) ; } } $ cloned_clauses [ $ clause -> getHash ( ) ] = $ unique_clause ; } // remove impossible types foreach ( $ cloned_clauses as $ clause_a ) { if ( count ( $ clause_a -> possibilities ) !== 1 || count ( array_values ( $ clause_a -> possibilities ) [ 0 ] ) !== 1 ) { continue ; } if ( ! $ clause_a -> reconcilable || $ clause_a -> wedge ) { continue ; } $ clause_var = array_keys ( $ clause_a -> possibilities ) [ 0 ] ; $ only_type = array_pop ( array_values ( $ clause_a -> possibilities ) [ 0 ] ) ; $ negated_clause_type = self :: negateType ( $ only_type ) ; foreach ( $ cloned_clauses as $ clause_b ) { if ( $ clause_a === $ clause_b || ! $ clause_b -> reconcilable || $ clause_b -> wedge ) { continue ; } if ( isset ( $ clause_b -> possibilities [ $ clause_var ] ) && in_array ( $ negated_clause_type , $ clause_b -> possibilities [ $ clause_var ] , true ) ) { $ clause_b -> possibilities [ $ clause_var ] = array_filter ( $ clause_b -> possibilities [ $ clause_var ] , /**
                         * @param string $possible_type
                         *
                         * @return bool
                         */ function ( $ possible_type ) use ( $ negated_clause_type ) { return $ possible_type !== $ negated_clause_type ; } ) ; if ( count ( $ clause_b -> possibilities [ $ clause_var ] ) === 0 ) { unset ( $ clause_b -> possibilities [ $ clause_var ] ) ; $ clause_b -> impossibilities = null ; } } } } $ deduped_clauses = [ ] ; // avoid strict duplicates foreach ( $ cloned_clauses as $ clause ) { $ deduped_clauses [ $ clause -> getHash ( ) ] = clone $ clause ; } $ deduped_clauses = array_filter ( $ deduped_clauses , /**
             * @return bool
             */ function ( Clause $ clause ) { return count ( $ clause -> possibilities ) || $ clause -> wedge ; } ) ; $ simplified_clauses = [ ] ; foreach ( $ deduped_clauses as $ clause_a ) { $ is_redundant = false ; foreach ( $ deduped_clauses as $ clause_b ) { if ( $ clause_a === $ clause_b || ! $ clause_b -> reconcilable || $ clause_b -> wedge || $ clause_a -> wedge ) { continue ; } if ( $ clause_a -> contains ( $ clause_b ) ) { $ is_redundant = true ; break ; } } if ( ! $ is_redundant ) { $ simplified_clauses [ ] = $ clause_a ; } } return $ simplified_clauses ; }
This is a very simple simplification heuristic
for CNF formulae.

It simplifies formulae:
($a) && ($a || $b) => $a
(!$a) && (!$b) && ($a || $b || $c) => $c

@param  array<int, Clause>  $clauses

@return array<int, Clause>
This is a very simple simplification heuristic for CNF formulae .