/*-------------------------------------------------------------------------

 *

 * prepqual.c

 *    Routines for preprocessing qualification expressions

 *

 *

 * While the parser will produce flattened (N-argument) AND/OR trees from

 * simple sequences of AND'ed or OR'ed clauses, there might be an AND clause

 * directly underneath another AND, or OR underneath OR, if the input was

 * oddly parenthesized.  Also, rule expansion and subquery flattening could

 * produce such parsetrees.  The planner wants to flatten all such cases

 * to ensure consistent optimization behavior.

 *

 * Formerly, this module was responsible for doing the initial flattening,

 * but now we leave it to eval_const_expressions to do that since it has to

 * make a complete pass over the expression tree anyway.  Instead, we just

 * have to ensure that our manipulations preserve AND/OR flatness.

 * pull_ands() and pull_ors() are used to maintain flatness of the AND/OR

 * tree after local transformations that might introduce nested AND/ORs.

 *

 *

 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 *

 * IDENTIFICATION

 *    src/backend/optimizer/prep/prepqual.c

 *

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include "nodes/makefuncs.h"

#include "nodes/nodeFuncs.h"

#include "optimizer/optimizer.h"

#include "utils/lsyscache.h"

static List *pull_ands(List *andlist);

static List *pull_ors(List *orlist);

static Expr *find_duplicate_ors(Expr *qual, bool is_check);

static Expr *process_duplicate_ors(List *orlist);

/*

 * negate_clause

 *    Negate a Boolean expression.

 *

 * Input is a clause to be negated (e.g., the argument of a NOT clause).

 * Returns a new clause equivalent to the negation of the given clause.

 *

 * Although this can be invoked on its own, it's mainly intended as a helper

 * for eval_const_expressions(), and that context drives several design

 * decisions.  In particular, if the input is already AND/OR flat, we must

 * preserve that property.  We also don't bother to recurse in situations

 * where we can assume that lower-level executions of eval_const_expressions

 * would already have simplified sub-clauses of the input.

 *

 * The difference between this and a simple make_notclause() is that this

 * tries to get rid of the NOT node by logical simplification.  It's clearly

 * always a win if the NOT node can be eliminated altogether.  However, our

 * use of DeMorgan's laws could result in having more NOT nodes rather than

 * fewer.  We do that unconditionally anyway, because in WHERE clauses it's

 * important to expose as much top-level AND/OR structure as possible.

 * Also, eliminating an intermediate NOT may allow us to flatten two levels

 * of AND or OR together that we couldn't have otherwise.  Finally, one of

 * the motivations for doing this is to ensure that logically equivalent

 * expressions will be seen as physically equal(), so we should always apply

 * the same transformations.

 */

Node *

negate_clause(Node *node)

{

  if (node == NULL)     /* should not happen */

    elog(ERROR, "can't negate an empty subexpression");

  switch (nodeTag(node))

  {

    case T_Const:

      {

        Const    *c = (Const *) node;

        /* NOT NULL is still NULL */

        if (c->constisnull)

          return makeBoolConst(false, true);

        /* otherwise pretty easy */

        return makeBoolConst(!DatumGetBool(c->constvalue), false);

      }

      break;

    case T_OpExpr:

      {

        /*

         * Negate operator if possible: (NOT (< A B)) => (>= A B)

         */

        OpExpr     *opexpr = (OpExpr *) node;

        Oid     negator = get_negator(opexpr->opno);

        if (negator)

        {

          OpExpr     *newopexpr = makeNode(OpExpr);

          newopexpr->opno = negator;

          newopexpr->opfuncid = InvalidOid;

          newopexpr->opresulttype = opexpr->opresulttype;

          newopexpr->opretset = opexpr->opretset;

          newopexpr->opcollid = opexpr->opcollid;

          newopexpr->inputcollid = opexpr->inputcollid;

          newopexpr->args = opexpr->args;

          newopexpr->location = opexpr->location;

          return (Node *) newopexpr;

        }

      }

      break;

    case T_ScalarArrayOpExpr:

      {

        /*

         * Negate a ScalarArrayOpExpr if its operator has a negator;

         * for example x = ANY (list) becomes x <> ALL (list)

         */

        ScalarArrayOpExpr *saopexpr = (ScalarArrayOpExpr *) node;

        Oid     negator = get_negator(saopexpr->opno);

        if (negator)

        {

          ScalarArrayOpExpr *newopexpr = makeNode(ScalarArrayOpExpr);

          newopexpr->opno = negator;

          newopexpr->opfuncid = InvalidOid;

          newopexpr->hashfuncid = InvalidOid;

          newopexpr->negfuncid = InvalidOid;

          newopexpr->useOr = !saopexpr->useOr;

          newopexpr->inputcollid = saopexpr->inputcollid;

          newopexpr->args = saopexpr->args;

          newopexpr->location = saopexpr->location;

          return (Node *) newopexpr;

        }

      }

      break;

    case T_BoolExpr:

      {

        BoolExpr   *expr = (BoolExpr *) node;

        switch (expr->boolop)

        {

            /*--------------------

             * Apply DeMorgan's Laws:

             *    (NOT (AND A B)) => (OR (NOT A) (NOT B))

             *    (NOT (OR A B))  => (AND (NOT A) (NOT B))

             * i.e., swap AND for OR and negate each subclause.

             *

             * If the input is already AND/OR flat and has no NOT

             * directly above AND or OR, this transformation preserves

             * those properties.  For example, if no direct child of

             * the given AND clause is an AND or a NOT-above-OR, then

             * the recursive calls of negate_clause() can't return any

             * OR clauses.  So we needn't call pull_ors() before

             * building a new OR clause.  Similarly for the OR case.

             *--------------------

             */

          case AND_EXPR:

            {

              List     *nargs = NIL;

              ListCell   *lc;

              foreach(lc, expr->args)

              {

                nargs = lappend(nargs,

                        negate_clause(lfirst(lc)));

              }

              return (Node *) make_orclause(nargs);

            }

            break;

          case OR_EXPR:

            {

              List     *nargs = NIL;

              ListCell   *lc;

              foreach(lc, expr->args)

              {

                nargs = lappend(nargs,

                        negate_clause(lfirst(lc)));

              }

              return (Node *) make_andclause(nargs);

            }

            break;

          case NOT_EXPR:

            /*

             * NOT underneath NOT: they cancel.  We assume the

             * input is already simplified, so no need to recurse.

             */

            return (Node *) linitial(expr->args);

          default:

            elog(ERROR, "unrecognized boolop: %d",

               (int) expr->boolop);

            break;

        }

      }

      break;

    case T_NullTest:

      {

        NullTest   *expr = (NullTest *) node;

        /*

         * In the rowtype case, the two flavors of NullTest are *not*

         * logical inverses, so we can't simplify.  But it does work

         * for scalar datatypes.

         */

        if (!expr->argisrow)

        {

          NullTest   *newexpr = makeNode(NullTest);

          newexpr->arg = expr->arg;

          newexpr->nulltesttype = (expr->nulltesttype == IS_NULL ?

                       IS_NOT_NULL : IS_NULL);

          newexpr->argisrow = expr->argisrow;

          newexpr->location = expr->location;

          return (Node *) newexpr;

        }

      }

      break;

    case T_BooleanTest:

      {

        BooleanTest *expr = (BooleanTest *) node;

        BooleanTest *newexpr = makeNode(BooleanTest);

        newexpr->arg = expr->arg;

        switch (expr->booltesttype)

        {

          case IS_TRUE:

            newexpr->booltesttype = IS_NOT_TRUE;

            break;

          case IS_NOT_TRUE:

            newexpr->booltesttype = IS_TRUE;

            break;

          case IS_FALSE:

            newexpr->booltesttype = IS_NOT_FALSE;

            break;

          case IS_NOT_FALSE:

            newexpr->booltesttype = IS_FALSE;

            break;

          case IS_UNKNOWN:

            newexpr->booltesttype = IS_NOT_UNKNOWN;

            break;

          case IS_NOT_UNKNOWN:

            newexpr->booltesttype = IS_UNKNOWN;

            break;

          default:

            elog(ERROR, "unrecognized booltesttype: %d",

               (int) expr->booltesttype);

            break;

        }

        newexpr->location = expr->location;

        return (Node *) newexpr;

      }

      break;

    default:

      /* else fall through */

      break;

  }

  /*

   * Otherwise we don't know how to simplify this, so just tack on an

   * explicit NOT node.

   */

  return (Node *) make_notclause((Expr *) node);

}

/*

 * canonicalize_qual

 *    Convert a qualification expression to the most useful form.

 *

 * This is primarily intended to be used on top-level WHERE (or JOIN/ON)

 * clauses.  It can also be used on top-level CHECK constraints, for which

 * pass is_check = true.  DO NOT call it on any expression that is not known

 * to be one or the other, as it might apply inappropriate simplifications.

 *

 * The name of this routine is a holdover from a time when it would try to

 * force the expression into canonical AND-of-ORs or OR-of-ANDs form.

 * Eventually, we recognized that that had more theoretical purity than

 * actual usefulness, and so now the transformation doesn't involve any

 * notion of reaching a canonical form.

 *

 * NOTE: we assume the input has already been through eval_const_expressions

 * and therefore possesses AND/OR flatness.  Formerly this function included

 * its own flattening logic, but that requires a useless extra pass over the

 * tree.

 *

 * Returns the modified qualification.

 */

Expr *

canonicalize_qual(Expr *qual, bool is_check)

{

  Expr     *newqual;

  /* Quick exit for empty qual */

  if (qual == NULL)

    return NULL;

  /* This should not be invoked on quals in implicit-AND format */

  Assert(!IsA(qual, List));

  /*

   * Pull up redundant subclauses in OR-of-AND trees.  We do this only

   * within the top-level AND/OR structure; there's no point in looking

   * deeper.  Also remove any NULL constants in the top-level structure.

   */

  newqual = find_duplicate_ors(qual, is_check);

  return newqual;

}

/*

 * pull_ands

 *    Recursively flatten nested AND clauses into a single and-clause list.

 *

 * Input is the arglist of an AND clause.

 * Returns the rebuilt arglist (note original list structure is not touched).

 */

static List *

pull_ands(List *andlist)

{

  List     *out_list = NIL;

  ListCell   *arg;

  foreach(arg, andlist)

  {

    Node     *subexpr = (Node *) lfirst(arg);

    if (is_andclause(subexpr))

      out_list = list_concat(out_list,

                   pull_ands(((BoolExpr *) subexpr)->args));

    else

      out_list = lappend(out_list, subexpr);

  }

  return out_list;

}

/*

 * pull_ors

 *    Recursively flatten nested OR clauses into a single or-clause list.

 *

 * Input is the arglist of an OR clause.

 * Returns the rebuilt arglist (note original list structure is not touched).

 */

static List *

pull_ors(List *orlist)

{

  List     *out_list = NIL;

  ListCell   *arg;

  foreach(arg, orlist)

  {

    Node     *subexpr = (Node *) lfirst(arg);

    if (is_orclause(subexpr))

      out_list = list_concat(out_list,

                   pull_ors(((BoolExpr *) subexpr)->args));

    else

      out_list = lappend(out_list, subexpr);

  }

  return out_list;

}

/*--------------------

 * The following code attempts to apply the inverse OR distributive law:

 *    ((A AND B) OR (A AND C))  =>  (A AND (B OR C))

 * That is, locate OR clauses in which every subclause contains an

 * identical term, and pull out the duplicated terms.

 *

 * This may seem like a fairly useless activity, but it turns out to be

 * applicable to many machine-generated queries, and there are also queries

 * in some of the TPC benchmarks that need it.  This was in fact almost the

 * sole useful side-effect of the old prepqual code that tried to force

 * the query into canonical AND-of-ORs form: the canonical equivalent of

 *    ((A AND B) OR (A AND C))

 * is

 *    ((A OR A) AND (A OR C) AND (B OR A) AND (B OR C))

 * which the code was able to simplify to

 *    (A AND (A OR C) AND (B OR A) AND (B OR C))

 * thus successfully extracting the common condition A --- but at the cost

 * of cluttering the qual with many redundant clauses.

 *--------------------

 */

/*

 * find_duplicate_ors

 *    Given a qualification tree with the NOTs pushed down, search for

 *    OR clauses to which the inverse OR distributive law might apply.

 *    Only the top-level AND/OR structure is searched.

 *

 * While at it, we remove any NULL constants within the top-level AND/OR

 * structure, eg in a WHERE clause, "x OR NULL::boolean" is reduced to "x".

 * In general that would change the result, so eval_const_expressions can't

 * do it; but at top level of WHERE, we don't need to distinguish between

 * FALSE and NULL results, so it's valid to treat NULL::boolean the same

 * as FALSE and then simplify AND/OR accordingly.  Conversely, in a top-level

 * CHECK constraint, we may treat a NULL the same as TRUE.

 *

 * Returns the modified qualification.  AND/OR flatness is preserved.

 */

static Expr *

find_duplicate_ors(Expr *qual, bool is_check)

{

  if (is_orclause(qual))

  {

    List     *orlist = NIL;

    ListCell   *temp;

    /* Recurse */

    foreach(temp, ((BoolExpr *) qual)->args)

    {

      Expr     *arg = (Expr *) lfirst(temp);

      arg = find_duplicate_ors(arg, is_check);

      /* Get rid of any constant inputs */

      if (arg && IsA(arg, Const))

      {

        Const    *carg = (Const *) arg;

        if (is_check)

        {

          /* Within OR in CHECK, drop constant FALSE */

          if (!carg->constisnull && !DatumGetBool(carg->constvalue))

            continue;

          /* Constant TRUE or NULL, so OR reduces to TRUE */

          return (Expr *) makeBoolConst(true, false);

        }

        else

        {

          /* Within OR in WHERE, drop constant FALSE or NULL */

          if (carg->constisnull || !DatumGetBool(carg->constvalue))

            continue;

          /* Constant TRUE, so OR reduces to TRUE */

          return arg;

        }

      }

      orlist = lappend(orlist, arg);

    }

    /* Flatten any ORs pulled up to just below here */

    orlist = pull_ors(orlist);

    /* Now we can look for duplicate ORs */

    return process_duplicate_ors(orlist);

  }

  else if (is_andclause(qual))

  {

    List     *andlist = NIL;

    ListCell   *temp;

    /* Recurse */

    foreach(temp, ((BoolExpr *) qual)->args)

    {

      Expr     *arg = (Expr *) lfirst(temp);

      arg = find_duplicate_ors(arg, is_check);

      /* Get rid of any constant inputs */

      if (arg && IsA(arg, Const))

      {

        Const    *carg = (Const *) arg;

        if (is_check)

        {

          /* Within AND in CHECK, drop constant TRUE or NULL */

          if (carg->constisnull || DatumGetBool(carg->constvalue))

            continue;

          /* Constant FALSE, so AND reduces to FALSE */

          return arg;

        }

        else

        {

          /* Within AND in WHERE, drop constant TRUE */

          if (!carg->constisnull && DatumGetBool(carg->constvalue))

            continue;

          /* Constant FALSE or NULL, so AND reduces to FALSE */

          return (Expr *) makeBoolConst(false, false);

        }

      }

      andlist = lappend(andlist, arg);

    }

    /* Flatten any ANDs introduced just below here */

    andlist = pull_ands(andlist);

    /* AND of no inputs reduces to TRUE */

    if (andlist == NIL)

      return (Expr *) makeBoolConst(true, false);

    /* Single-expression AND just reduces to that expression */

    if (list_length(andlist) == 1)

      return (Expr *) linitial(andlist);

    /* Else we still need an AND node */

    return make_andclause(andlist);

  }

  else

    return qual;

}

/*

 * process_duplicate_ors

 *    Given a list of exprs which are ORed together, try to apply

 *    the inverse OR distributive law.

 *

 * Returns the resulting expression (could be an AND clause, an OR

 * clause, or maybe even a single subexpression).

 */

static Expr *

process_duplicate_ors(List *orlist)

{

  List     *reference = NIL;

  int     num_subclauses = 0;

  List     *winners;

  List     *neworlist;

  ListCell   *temp;

  /* OR of no inputs reduces to FALSE */

  if (orlist == NIL)

    return (Expr *) makeBoolConst(false, false);

  /* Single-expression OR just reduces to that expression */

  if (list_length(orlist) == 1)

    return (Expr *) linitial(orlist);

  /*

   * Choose the shortest AND clause as the reference list --- obviously, any

   * subclause not in this clause isn't in all the clauses. If we find a

   * clause that's not an AND, we can treat it as a one-element AND clause,

   * which necessarily wins as shortest.

   */

  foreach(temp, orlist)

  {

    Expr     *clause = (Expr *) lfirst(temp);

    if (is_andclause(clause))

    {

      List     *subclauses = ((BoolExpr *) clause)->args;

      int     nclauses = list_length(subclauses);

      if (reference == NIL || nclauses < num_subclauses)

      {

        reference = subclauses;

        num_subclauses = nclauses;

      }

    }

    else

    {

      reference = list_make1(clause);

      break;

    }

  }

  /*

   * Just in case, eliminate any duplicates in the reference list.

   */

  reference = list_union(NIL, reference);

  /*

   * Check each element of the reference list to see if it's in all the OR

   * clauses.  Build a new list of winning clauses.

   */

  winners = NIL;

  foreach(temp, reference)

  {

    Expr     *refclause = (Expr *) lfirst(temp);

    bool    win = true;

    ListCell   *temp2;

    foreach(temp2, orlist)

    {

      Expr     *clause = (Expr *) lfirst(temp2);

      if (is_andclause(clause))

      {

        if (!list_member(((BoolExpr *) clause)->args, refclause))

        {

          win = false;

          break;

        }

      }

      else

      {

        if (!equal(refclause, clause))

        {

          win = false;

          break;

        }

      }

    }

    if (win)

      winners = lappend(winners, refclause);

  }

  /*

   * If no winners, we can't transform the OR

   */

  if (winners == NIL)

    return make_orclause(orlist);

  /*

   * Generate new OR list consisting of the remaining sub-clauses.

   *

   * If any clause degenerates to empty, then we have a situation like (A

   * AND B) OR (A), which can be reduced to just A --- that is, the

   * additional conditions in other arms of the OR are irrelevant.

   *

   * Note that because we use list_difference, any multiple occurrences of a

   * winning clause in an AND sub-clause will be removed automatically.

   */

  neworlist = NIL;

  foreach(temp, orlist)

  {

    Expr     *clause = (Expr *) lfirst(temp);

    if (is_andclause(clause))

    {

      List     *subclauses = ((BoolExpr *) clause)->args;

      subclauses = list_difference(subclauses, winners);

      if (subclauses != NIL)

      {

        if (list_length(subclauses) == 1)

          neworlist = lappend(neworlist, linitial(subclauses));

        else

          neworlist = lappend(neworlist, make_andclause(subclauses));

      }

      else

      {

        neworlist = NIL; /* degenerate case, see above */

        break;

      }

    }

    else

    {

      if (!list_member(winners, clause))

        neworlist = lappend(neworlist, clause);

      else

      {

        neworlist = NIL; /* degenerate case, see above */

        break;

      }

    }

  }

  /*

   * Append reduced OR to the winners list, if it's not degenerate, handling

   * the special case of one element correctly (can that really happen?).

   * Also be careful to maintain AND/OR flatness in case we pulled up a

   * sub-sub-OR-clause.

   */

  if (neworlist != NIL)

  {

    if (list_length(neworlist) == 1)

      winners = lappend(winners, linitial(neworlist));

    else

      winners = lappend(winners, make_orclause(pull_ors(neworlist)));

  }

  /*

   * And return the constructed AND clause, again being wary of a single

   * element and AND/OR flatness.

   */

  if (list_length(winners) == 1)

    return (Expr *) linitial(winners);

  else

    return make_andclause(pull_ands(winners));

}