src/backend/optimizer/util/clauses.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * clauses.c
   4  *        routines to manipulate qualification clauses
   5  *
   6  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.68 2000/05/30 00:49:49 momjian Exp $
  12  *
  13  * HISTORY
  14  *        AUTHOR                        DATE                    MAJOR EVENT
  15  *        Andrew Yu                     Nov 3, 1994             clause.c and clauses.c combined
  16  *
  17  *-------------------------------------------------------------------------
  18  */
  19
  20 #include "postgres.h"
  21
  22 #include "catalog/pg_operator.h"
  23 #include "catalog/pg_proc.h"
  24 #include "catalog/pg_type.h"
  25 #include "executor/executor.h"
  26 #include "nodes/makefuncs.h"
  27 #include "nodes/nodeFuncs.h"
  28 #include "optimizer/clauses.h"
  29 #include "optimizer/tlist.h"
  30 #include "optimizer/var.h"
  31 #include "parser/parse_type.h"
  32 #include "parser/parsetree.h"
  33 #include "utils/lsyscache.h"
  34 #include "utils/syscache.h"
  35
  36
  37 /* note that pg_type.h hardwires size of bool as 1 ... duplicate it */
  38 #define MAKEBOOLCONST(val,isnull) \
  39         ((Node *) makeConst(BOOLOID, 1, (Datum) (val), \
  40                                                 (isnull), true, false, false))
  41
  42 static bool contain_agg_clause_walker(Node *node, void *context);
  43 static bool pull_agg_clause_walker(Node *node, List **listptr);
  44 static bool contain_subplans_walker(Node *node, void *context);
  45 static bool pull_subplans_walker(Node *node, List **listptr);
  46 static bool check_subplans_for_ungrouped_vars_walker(Node *node,
  47                                                                                  Query *context);
  48 static int      is_single_func(Node *node);
  49 static Node *eval_const_expressions_mutator(Node *node, void *context);
  50 static Expr *simplify_op_or_func(Expr *expr, List *args);
  51
  52
  53 Expr *
  54 make_clause(int type, Node *oper, List *args)
  55 {
  56         Expr       *expr = makeNode(Expr);
  57
  58         switch (type)
  59         {
  60                 case AND_EXPR:
  61                 case OR_EXPR:
  62                 case NOT_EXPR:
  63                         expr->typeOid = BOOLOID;
  64                         break;
  65                 case OP_EXPR:
  66                         expr->typeOid = ((Oper *) oper)->opresulttype;
  67                         break;
  68                 case FUNC_EXPR:
  69                         expr->typeOid = ((Func *) oper)->functype;
  70                         break;
  71                 default:
  72                         elog(ERROR, "make_clause: unsupported type %d", type);
  73                         break;
  74         }
  75         expr->opType = type;
  76         expr->oper = oper;                      /* ignored for AND, OR, NOT */
  77         expr->args = args;
  78         return expr;
  79 }
  80
  81
  82 /*****************************************************************************
  83  *              OPERATOR clause functions
  84  *****************************************************************************/
  85
  86
  87 /*
  88  * is_opclause
  89  *
  90  * Returns t iff the clause is an operator clause:
  91  *                              (op expr expr) or (op expr).
  92  *
  93  * [historical note: is_clause has the exact functionality and is used
  94  *              throughout the code. They're renamed to is_opclause for clarity.
  95  *                                                                                              - ay 10/94.]
  96  */
  97 bool
  98 is_opclause(Node *clause)
  99 {
 100         return (clause != NULL &&
 101                         IsA(clause, Expr) &&
 102                         ((Expr *) clause)->opType == OP_EXPR);
 103 }
 104
 105 /*
 106  * make_opclause
 107  *        Creates a clause given its operator left operand and right
 108  *        operand (if it is non-null).
 109  *
 110  */
 111 Expr *
 112 make_opclause(Oper *op, Var *leftop, Var *rightop)
 113 {
 114         Expr       *expr = makeNode(Expr);
 115
 116         expr->typeOid = op->opresulttype;
 117         expr->opType = OP_EXPR;
 118         expr->oper = (Node *) op;
 119         if (rightop)
 120                 expr->args = lcons(leftop, lcons(rightop, NIL));
 121         else
 122                 expr->args = lcons(leftop, NIL);
 123         return expr;
 124 }
 125
 126 /*
 127  * get_leftop
 128  *
 129  * Returns the left operand of a clause of the form (op expr expr)
 130  *              or (op expr)
 131  *
 132  * NB: for historical reasons, the result is declared Var *, even
 133  * though many callers can cope with results that are not Vars.
 134  * The result really ought to be declared Expr * or Node *.
 135  */
 136 Var *
 137 get_leftop(Expr *clause)
 138 {
 139         if (clause->args != NULL)
 140                 return lfirst(clause->args);
 141         else
 142                 return NULL;
 143 }
 144
 145 /*
 146  * get_rightop
 147  *
 148  * Returns the right operand in a clause of the form (op expr expr).
 149  * NB: result will be NULL if applied to a unary op clause.
 150  */
 151 Var *
 152 get_rightop(Expr *clause)
 153 {
 154         if (clause->args != NULL && lnext(clause->args) != NULL)
 155                 return lfirst(lnext(clause->args));
 156         else
 157                 return NULL;
 158 }
 159
 160 /*****************************************************************************
 161  *              FUNC clause functions
 162  *****************************************************************************/
 163
 164 /*
 165  * is_funcclause
 166  *
 167  * Returns t iff the clause is a function clause: (func { expr }).
 168  *
 169  */
 170 bool
 171 is_funcclause(Node *clause)
 172 {
 173         return (clause != NULL &&
 174                         IsA(clause, Expr) &&
 175                         ((Expr *) clause)->opType == FUNC_EXPR);
 176 }
 177
 178 /*
 179  * make_funcclause
 180  *
 181  * Creates a function clause given the FUNC node and the functional
 182  * arguments.
 183  *
 184  */
 185 Expr *
 186 make_funcclause(Func *func, List *funcargs)
 187 {
 188         Expr       *expr = makeNode(Expr);
 189
 190         expr->typeOid = func->functype;
 191         expr->opType = FUNC_EXPR;
 192         expr->oper = (Node *) func;
 193         expr->args = funcargs;
 194         return expr;
 195 }
 196
 197 /*****************************************************************************
 198  *              OR clause functions
 199  *****************************************************************************/
 200
 201 /*
 202  * or_clause
 203  *
 204  * Returns t iff the clause is an 'or' clause: (OR { expr }).
 205  *
 206  */
 207 bool
 208 or_clause(Node *clause)
 209 {
 210         return (clause != NULL &&
 211                         IsA(clause, Expr) &&
 212                         ((Expr *) clause)->opType == OR_EXPR);
 213 }
 214
 215 /*
 216  * make_orclause
 217  *
 218  * Creates an 'or' clause given a list of its subclauses.
 219  *
 220  */
 221 Expr *
 222 make_orclause(List *orclauses)
 223 {
 224         Expr       *expr = makeNode(Expr);
 225
 226         expr->typeOid = BOOLOID;
 227         expr->opType = OR_EXPR;
 228         expr->oper = NULL;
 229         expr->args = orclauses;
 230         return expr;
 231 }
 232
 233 /*****************************************************************************
 234  *              NOT clause functions
 235  *****************************************************************************/
 236
 237 /*
 238  * not_clause
 239  *
 240  * Returns t iff this is a 'not' clause: (NOT expr).
 241  *
 242  */
 243 bool
 244 not_clause(Node *clause)
 245 {
 246         return (clause != NULL &&
 247                         IsA(clause, Expr) &&
 248                         ((Expr *) clause)->opType == NOT_EXPR);
 249 }
 250
 251 /*
 252  * make_notclause
 253  *
 254  * Create a 'not' clause given the expression to be negated.
 255  *
 256  */
 257 Expr *
 258 make_notclause(Expr *notclause)
 259 {
 260         Expr       *expr = makeNode(Expr);
 261
 262         expr->typeOid = BOOLOID;
 263         expr->opType = NOT_EXPR;
 264         expr->oper = NULL;
 265         expr->args = lcons(notclause, NIL);
 266         return expr;
 267 }
 268
 269 /*
 270  * get_notclausearg
 271  *
 272  * Retrieve the clause within a 'not' clause
 273  *
 274  */
 275 Expr *
 276 get_notclausearg(Expr *notclause)
 277 {
 278         return lfirst(notclause->args);
 279 }
 280
 281 /*****************************************************************************
 282  *              AND clause functions
 283  *****************************************************************************/
 284
 285
 286 /*
 287  * and_clause
 288  *
 289  * Returns t iff its argument is an 'and' clause: (AND { expr }).
 290  *
 291  */
 292 bool
 293 and_clause(Node *clause)
 294 {
 295         return (clause != NULL &&
 296                         IsA(clause, Expr) &&
 297                         ((Expr *) clause)->opType == AND_EXPR);
 298 }
 299
 300 /*
 301  * make_andclause
 302  *
 303  * Create an 'and' clause given its arguments in a list.
 304  *
 305  */
 306 Expr *
 307 make_andclause(List *andclauses)
 308 {
 309         Expr       *expr = makeNode(Expr);
 310
 311         expr->typeOid = BOOLOID;
 312         expr->opType = AND_EXPR;
 313         expr->oper = NULL;
 314         expr->args = andclauses;
 315         return expr;
 316 }
 317
 318 /*
 319  * Sometimes (such as in the result of canonicalize_qual or the input of
 320  * ExecQual), we use lists of expression nodes with implicit AND semantics.
 321  *
 322  * These functions convert between an AND-semantics expression list and the
 323  * ordinary representation of a boolean expression.
 324  *
 325  * Note that an empty list is considered equivalent to TRUE.
 326  */
 327 Expr *
 328 make_ands_explicit(List *andclauses)
 329 {
 330         if (andclauses == NIL)
 331                 return (Expr *) MAKEBOOLCONST(true, false);
 332         else if (lnext(andclauses) == NIL)
 333                 return (Expr *) lfirst(andclauses);
 334         else
 335                 return make_andclause(andclauses);
 336 }
 337
 338 List *
 339 make_ands_implicit(Expr *clause)
 340 {
 341
 342         /*
 343          * NB: because the parser sets the qual field to NULL in a query that
 344          * has no WHERE clause, we must consider a NULL input clause as TRUE,
 345          * even though one might more reasonably think it FALSE.  Grumble. If
 346          * this causes trouble, consider changing the parser's behavior.
 347          */
 348         if (clause == NULL)
 349                 return NIL;                             /* NULL -> NIL list == TRUE */
 350         else if (and_clause((Node *) clause))
 351                 return clause->args;
 352         else if (IsA(clause, Const) &&
 353                          !((Const *) clause)->constisnull &&
 354                          DatumGetInt32(((Const *) clause)->constvalue))
 355                 return NIL;                             /* constant TRUE input -> NIL list */
 356         else
 357                 return lcons(clause, NIL);
 358 }
 359
 360
 361 /*****************************************************************************
 362  *              Aggregate-function clause manipulation
 363  *****************************************************************************/
 364
 365 /*
 366  * contain_agg_clause
 367  *        Recursively search for Aggref nodes within a clause.
 368  *
 369  *        Returns true if any aggregate found.
 370  */
 371 bool
 372 contain_agg_clause(Node *clause)
 373 {
 374         return contain_agg_clause_walker(clause, NULL);
 375 }
 376
 377 static bool
 378 contain_agg_clause_walker(Node *node, void *context)
 379 {
 380         if (node == NULL)
 381                 return false;
 382         if (IsA(node, Aggref))
 383                 return true;                    /* abort the tree traversal and return
 384                                                                  * true */
 385         return expression_tree_walker(node, contain_agg_clause_walker, context);
 386 }
 387
 388 /*
 389  * pull_agg_clause
 390  *        Recursively pulls all Aggref nodes from an expression tree.
 391  *
 392  *        Returns list of Aggref nodes found.  Note the nodes themselves are not
 393  *        copied, only referenced.
 394  *
 395  *        Note: this also checks for nested aggregates, which are an error.
 396  */
 397 List *
 398 pull_agg_clause(Node *clause)
 399 {
 400         List       *result = NIL;
 401
 402         pull_agg_clause_walker(clause, &result);
 403         return result;
 404 }
 405
 406 static bool
 407 pull_agg_clause_walker(Node *node, List **listptr)
 408 {
 409         if (node == NULL)
 410                 return false;
 411         if (IsA(node, Aggref))
 412         {
 413                 *listptr = lappend(*listptr, node);
 414
 415                 /*
 416                  * Complain if the aggregate's argument contains any aggregates;
 417                  * nested agg functions are semantically nonsensical.
 418                  */
 419                 if (contain_agg_clause(((Aggref *) node)->target))
 420                         elog(ERROR, "Aggregate function calls may not be nested");
 421
 422                 /*
 423                  * Having checked that, we need not recurse into the argument.
 424                  */
 425                 return false;
 426         }
 427         return expression_tree_walker(node, pull_agg_clause_walker,
 428                                                                   (void *) listptr);
 429 }
 430
 431
 432 /*****************************************************************************
 433  *              Subplan clause manipulation
 434  *****************************************************************************/
 435
 436 /*
 437  * contain_subplans
 438  *        Recursively search for subplan nodes within a clause.
 439  *
 440  * If we see a SubLink node, we will return TRUE.  This is only possible if
 441  * the expression tree hasn't yet been transformed by subselect.c.  We do not
 442  * know whether the node will produce a true subplan or just an initplan,
 443  * but we make the conservative assumption that it will be a subplan.
 444  *
 445  * Returns true if any subplan found.
 446  */
 447 bool
 448 contain_subplans(Node *clause)
 449 {
 450         return contain_subplans_walker(clause, NULL);
 451 }
 452
 453 static bool
 454 contain_subplans_walker(Node *node, void *context)
 455 {
 456         if (node == NULL)
 457                 return false;
 458         if (is_subplan(node) || IsA(node, SubLink))
 459                 return true;                    /* abort the tree traversal and return
 460                                                                  * true */
 461         return expression_tree_walker(node, contain_subplans_walker, context);
 462 }
 463
 464 /*
 465  * pull_subplans
 466  *        Recursively pulls all subplans from an expression tree.
 467  *
 468  *        Returns list of subplan nodes found.  Note the nodes themselves are not
 469  *        copied, only referenced.
 470  */
 471 List *
 472 pull_subplans(Node *clause)
 473 {
 474         List       *result = NIL;
 475
 476         pull_subplans_walker(clause, &result);
 477         return result;
 478 }
 479
 480 static bool
 481 pull_subplans_walker(Node *node, List **listptr)
 482 {
 483         if (node == NULL)
 484                 return false;
 485         if (is_subplan(node))
 486         {
 487                 *listptr = lappend(*listptr, ((Expr *) node)->oper);
 488                 /* fall through to check args to subplan */
 489         }
 490         return expression_tree_walker(node, pull_subplans_walker,
 491                                                                   (void *) listptr);
 492 }
 493
 494 /*
 495  * check_subplans_for_ungrouped_vars
 496  *              Check for subplans that are being passed ungrouped variables as
 497  *              parameters; generate an error message if any are found.
 498  *
 499  * In most contexts, ungrouped variables will be detected by the parser (see
 500  * parse_agg.c, check_ungrouped_columns()). But that routine currently does
 501  * not check subplans, because the necessary info is not computed until the
 502  * planner runs.  So we do it here, after we have processed sublinks into
 503  * subplans.  This ought to be cleaned up someday.
 504  *
 505  * 'clause' is the expression tree to be searched for subplans.
 506  * 'query' provides the GROUP BY list, the target list that the group clauses
 507  * refer to, and the range table.
 508  */
 509 void
 510 check_subplans_for_ungrouped_vars(Node *clause,
 511                                                                   Query *query)
 512 {
 513
 514         /*
 515          * No special setup needed; context for walker is just the Query
 516          * pointer
 517          */
 518         check_subplans_for_ungrouped_vars_walker(clause, query);
 519 }
 520
 521 static bool
 522 check_subplans_for_ungrouped_vars_walker(Node *node,
 523                                                                                  Query *context)
 524 {
 525         if (node == NULL)
 526                 return false;
 527
 528         /*
 529          * We can ignore Vars other than in subplan args lists, since the
 530          * parser already checked 'em.
 531          */
 532         if (is_subplan(node))
 533         {
 534
 535                 /*
 536                  * The args list of the subplan node represents attributes from
 537                  * outside passed into the sublink.
 538                  */
 539                 List       *t;
 540
 541                 foreach(t, ((Expr *) node)->args)
 542                 {
 543                         Node       *thisarg = lfirst(t);
 544                         Var                *var;
 545                         bool            contained_in_group_clause;
 546                         List       *gl;
 547
 548                         /*
 549                          * We do not care about args that are not local variables;
 550                          * params or outer-level vars are not our responsibility to
 551                          * check.  (The outer-level query passing them to us needs to
 552                          * worry, instead.)
 553                          */
 554                         if (!IsA(thisarg, Var))
 555                                 continue;
 556                         var = (Var *) thisarg;
 557                         if (var->varlevelsup > 0)
 558                                 continue;
 559
 560                         /*
 561                          * Else, see if it is a grouping column.
 562                          */
 563                         contained_in_group_clause = false;
 564                         foreach(gl, context->groupClause)
 565                         {
 566                                 GroupClause *gcl = lfirst(gl);
 567                                 Node       *groupexpr;
 568
 569                                 groupexpr = get_sortgroupclause_expr(gcl,
 570                                                                                                          context->targetList);
 571                                 if (equal(thisarg, groupexpr))
 572                                 {
 573                                         contained_in_group_clause = true;
 574                                         break;
 575                                 }
 576                         }
 577
 578                         if (!contained_in_group_clause)
 579                         {
 580                                 /* Found an ungrouped argument.  Complain. */
 581                                 RangeTblEntry *rte;
 582                                 char       *attname;
 583
 584                                 Assert(var->varno > 0 &&
 585                                            var->varno <= length(context->rtable));
 586                                 rte = rt_fetch(var->varno, context->rtable);
 587                                 attname = get_attname(rte->relid, var->varattno);
 588                                 if (!attname)
 589                                         elog(ERROR, "cache lookup of attribute %d in relation %u failed",
 590                                                  var->varattno, rte->relid);
 591                                 elog(ERROR, "Sub-SELECT uses un-GROUPed attribute %s.%s from outer query",
 592                                          rte->ref->relname, attname);
 593                         }
 594                 }
 595         }
 596         return expression_tree_walker(node,
 597                                                                 check_subplans_for_ungrouped_vars_walker,
 598                                                                   (void *) context);
 599 }
 600
 601
 602 /*****************************************************************************
 603  *                                                                                                                                                       *
 604  *              General clause-manipulating routines                                                             *
 605  *                                                                                                                                                       *
 606  *****************************************************************************/
 607
 608
 609 /*
 610  * pull_constant_clauses
 611  *        Scans through a list of qualifications and find those that
 612  *        contain no variables (of the current query level).
 613  *
 614  * Returns a list of the constant clauses in constantQual and the remaining
 615  * quals as the return value.
 616  *
 617  */
 618 List *
 619 pull_constant_clauses(List *quals, List **constantQual)
 620 {
 621         List       *q;
 622         List       *constqual = NIL;
 623         List       *restqual = NIL;
 624
 625         foreach(q, quals)
 626         {
 627                 if (!contain_var_clause(lfirst(q)))
 628                         constqual = lcons(lfirst(q), constqual);
 629                 else
 630                         restqual = lcons(lfirst(q), restqual);
 631         }
 632         *constantQual = constqual;
 633         return restqual;
 634 }
 635
 636
 637 /*
 638  * clause_relids_vars
 639  *        Retrieves distinct relids and vars appearing within a clause.
 640  *
 641  * '*relids' is set to an integer list of all distinct "varno"s appearing
 642  *              in Vars within the clause.
 643  * '*vars' is set to a list of all distinct Vars appearing within the clause.
 644  *              Var nodes are considered distinct if they have different varno
 645  *              or varattno values.  If there are several occurrences of the same
 646  *              varno/varattno, you get a randomly chosen one...
 647  *
 648  * Note that upper-level vars are ignored, since they normally will
 649  * become Params with respect to this query level.
 650  */
 651 void
 652 clause_get_relids_vars(Node *clause, Relids *relids, List **vars)
 653 {
 654         List       *clvars = pull_var_clause(clause, false);
 655         List       *varno_list = NIL;
 656         List       *var_list = NIL;
 657         List       *i;
 658
 659         foreach(i, clvars)
 660         {
 661                 Var                *var = (Var *) lfirst(i);
 662                 List       *vi;
 663
 664                 if (!intMember(var->varno, varno_list))
 665                         varno_list = lconsi(var->varno, varno_list);
 666                 foreach(vi, var_list)
 667                 {
 668                         Var                *in_list = (Var *) lfirst(vi);
 669
 670                         if (in_list->varno == var->varno &&
 671                                 in_list->varattno == var->varattno)
 672                                 break;
 673                 }
 674                 if (vi == NIL)
 675                         var_list = lcons(var, var_list);
 676         }
 677         freeList(clvars);
 678
 679         *relids = varno_list;
 680         *vars = var_list;
 681 }
 682
 683 /*
 684  * NumRelids
 685  *              (formerly clause_relids)
 686  *
 687  * Returns the number of different relations referenced in 'clause'.
 688  */
 689 int
 690 NumRelids(Node *clause)
 691 {
 692         List       *varno_list = pull_varnos(clause);
 693         int                     result = length(varno_list);
 694
 695         freeList(varno_list);
 696         return result;
 697 }
 698
 699 /*
 700  * get_relattval
 701  *              Extract information from a restriction or join clause for
 702  *              selectivity estimation.  The inputs are an expression
 703  *              and a relation number (which can be 0 if we don't care which
 704  *              relation is used; that'd normally be the case for restriction
 705  *              clauses, where the caller already knows that only one relation
 706  *              is referenced in the clause).  The routine checks that the
 707  *              expression is of the form (var op something) or (something op var)
 708  *              where the var is an attribute of the specified relation, or
 709  *              a function of a var of the specified relation.  If so, it
 710  *              returns the following info:
 711  *                      the found relation number (same as targetrelid unless that is 0)
 712  *                      the found var number (or InvalidAttrNumber if a function)
 713  *                      if the "something" is a constant, the value of the constant
 714  *                      flags indicating whether a constant was found, and on which side.
 715  *              Default values are returned if the expression is too complicated,
 716  *              specifically 0 for the relid and attno, 0 for the constant value.
 717  *
 718  *              Note that negative attno values are *not* invalid, but represent
 719  *              system attributes such as OID.  It's sufficient to check for relid=0
 720  *              to determine whether the routine succeeded.
 721  */
 722 void
 723 get_relattval(Node *clause,
 724                           int targetrelid,
 725                           int *relid,
 726                           AttrNumber *attno,
 727                           Datum *constval,
 728                           int *flag)
 729 {
 730         Var                *left,
 731                            *right,
 732                            *other;
 733         int                     funcvarno;
 734
 735         /* Careful; the passed clause might not be a binary operator at all */
 736
 737         if (!is_opclause(clause))
 738                 goto default_results;
 739
 740         left = get_leftop((Expr *) clause);
 741         right = get_rightop((Expr *) clause);
 742
 743         if (!right)
 744                 goto default_results;
 745
 746         /* First look for the var or func */
 747
 748         if (IsA(left, Var) &&
 749                 (targetrelid == 0 || targetrelid == left->varno))
 750         {
 751                 *relid = left->varno;
 752                 *attno = left->varattno;
 753                 *flag = SEL_RIGHT;
 754         }
 755         else if (IsA(right, Var) &&
 756                          (targetrelid == 0 || targetrelid == right->varno))
 757         {
 758                 *relid = right->varno;
 759                 *attno = right->varattno;
 760                 *flag = 0;
 761         }
 762         else if ((funcvarno = is_single_func((Node *) left)) != 0 &&
 763                          (targetrelid == 0 || targetrelid == funcvarno))
 764         {
 765                 *relid = funcvarno;
 766                 *attno = InvalidAttrNumber;
 767                 *flag = SEL_RIGHT;
 768         }
 769         else if ((funcvarno = is_single_func((Node *) right)) != 0 &&
 770                          (targetrelid == 0 || targetrelid == funcvarno))
 771         {
 772                 *relid = funcvarno;
 773                 *attno = InvalidAttrNumber;
 774                 *flag = 0;
 775         }
 776         else
 777         {
 778                 /* Duh, it's too complicated for me... */
 779 default_results:
 780                 *relid = 0;
 781                 *attno = 0;
 782                 *constval = 0;
 783                 *flag = 0;
 784                 return;
 785         }
 786
 787         /* OK, we identified the var or func; now look at the other side */
 788
 789         other = (*flag == 0) ? left : right;
 790
 791         if (IsA(other, Const) &&
 792                 !((Const *) other)->constisnull)
 793         {
 794                 *constval = ((Const *) other)->constvalue;
 795                 *flag |= SEL_CONSTANT;
 796         }
 797         else
 798                 *constval = 0;
 799 }
 800
 801 /*
 802  * is_single_func
 803  *       If the given expression is a function of a single relation,
 804  *       return the relation number; else return 0
 805  */
 806 static int
 807 is_single_func(Node *node)
 808 {
 809         if (is_funcclause(node))
 810         {
 811                 List       *varnos = pull_varnos(node);
 812
 813                 if (length(varnos) == 1)
 814                 {
 815                         int                     funcvarno = lfirsti(varnos);
 816
 817                         freeList(varnos);
 818                         return funcvarno;
 819                 }
 820                 freeList(varnos);
 821         }
 822         return 0;
 823 }
 824
 825 /*
 826  * get_rels_atts
 827  *
 828  * Returns the info
 829  *                              ( relid1 attno1 relid2 attno2 )
 830  *              for a joinclause.
 831  *
 832  * If the clause is not of the form (var op var) or if any of the vars
 833  * refer to nested attributes, then zeroes are returned.
 834  *
 835  */
 836 void
 837 get_rels_atts(Node *clause,
 838                           int *relid1,
 839                           AttrNumber *attno1,
 840                           int *relid2,
 841                           AttrNumber *attno2)
 842 {
 843         /* set default values */
 844         *relid1 = 0;
 845         *attno1 = 0;
 846         *relid2 = 0;
 847         *attno2 = 0;
 848
 849         if (is_opclause(clause))
 850         {
 851                 Var                *left = get_leftop((Expr *) clause);
 852                 Var                *right = get_rightop((Expr *) clause);
 853
 854                 if (left && right)
 855                 {
 856                         int                     funcvarno;
 857
 858                         if (IsA(left, Var))
 859                         {
 860                                 *relid1 = left->varno;
 861                                 *attno1 = left->varattno;
 862                         }
 863                         else if ((funcvarno = is_single_func((Node *) left)) != 0)
 864                         {
 865                                 *relid1 = funcvarno;
 866                                 *attno1 = InvalidAttrNumber;
 867                         }
 868
 869                         if (IsA(right, Var))
 870                         {
 871                                 *relid2 = right->varno;
 872                                 *attno2 = right->varattno;
 873                         }
 874                         else if ((funcvarno = is_single_func((Node *) right)) != 0)
 875                         {
 876                                 *relid2 = funcvarno;
 877                                 *attno2 = InvalidAttrNumber;
 878                         }
 879                 }
 880         }
 881 }
 882
 883 /*--------------------
 884  * CommuteClause: commute a binary operator clause
 885  *
 886  * XXX the clause is destructively modified!
 887  *--------------------
 888  */
 889 void
 890 CommuteClause(Expr *clause)
 891 {
 892         HeapTuple       heapTup;
 893         Form_pg_operator commuTup;
 894         Oper       *commu;
 895         Node       *temp;
 896
 897         if (!is_opclause((Node *) clause) ||
 898                 length(clause->args) != 2)
 899                 elog(ERROR, "CommuteClause: applied to non-binary-operator clause");
 900
 901         heapTup = (HeapTuple)
 902                 get_operator_tuple(get_commutator(((Oper *) clause->oper)->opno));
 903
 904         if (heapTup == (HeapTuple) NULL)
 905                 elog(ERROR, "CommuteClause: no commutator for operator %u",
 906                          ((Oper *) clause->oper)->opno);
 907
 908         commuTup = (Form_pg_operator) GETSTRUCT(heapTup);
 909
 910         commu = makeOper(heapTup->t_data->t_oid,
 911                                          commuTup->oprcode,
 912                                          commuTup->oprresult,
 913                                          ((Oper *) clause->oper)->opsize,
 914                                          NULL);
 915
 916         /*
 917          * re-form the clause in-place!
 918          */
 919         clause->oper = (Node *) commu;
 920         temp = lfirst(clause->args);
 921         lfirst(clause->args) = lsecond(clause->args);
 922         lsecond(clause->args) = temp;
 923 }
 924
 925
 926 /*--------------------
 927  * eval_const_expressions
 928  *
 929  * Reduce any recognizably constant subexpressions of the given
 930  * expression tree, for example "2 + 2" => "4".  More interestingly,
 931  * we can reduce certain boolean expressions even when they contain
 932  * non-constant subexpressions: "x OR true" => "true" no matter what
 933  * the subexpression x is.      (XXX We assume that no such subexpression
 934  * will have important side-effects, which is not necessarily a good
 935  * assumption in the presence of user-defined functions; do we need a
 936  * pg_proc flag that prevents discarding the execution of a function?)
 937  *
 938  * We do understand that certain functions may deliver non-constant
 939  * results even with constant inputs, "nextval()" being the classic
 940  * example.  Functions that are not marked "proiscachable" in pg_proc
 941  * will not be pre-evaluated here, although we will reduce their
 942  * arguments as far as possible.  Functions that are the arguments
 943  * of Iter nodes are also not evaluated.
 944  *
 945  * We assume that the tree has already been type-checked and contains
 946  * only operators and functions that are reasonable to try to execute.
 947  *
 948  * This routine should be invoked before converting sublinks to subplans
 949  * (subselect.c's SS_process_sublinks()).  The converted form contains
 950  * bogus "Const" nodes that are actually placeholders where the executor
 951  * will insert values from the inner plan, and obviously we mustn't try
 952  * to reduce the expression as though these were really constants.
 953  * As a safeguard, if we happen to find an already-converted SubPlan node,
 954  * we will return it unchanged rather than recursing into it.
 955  *--------------------
 956  */
 957 Node *
 958 eval_const_expressions(Node *node)
 959 {
 960         /* no context or special setup needed, so away we go... */
 961         return eval_const_expressions_mutator(node, NULL);
 962 }
 963
 964 static Node *
 965 eval_const_expressions_mutator(Node *node, void *context)
 966 {
 967         if (node == NULL)
 968                 return NULL;
 969         if (IsA(node, Expr))
 970         {
 971                 Expr       *expr = (Expr *) node;
 972                 List       *args;
 973                 Const      *const_input;
 974                 Expr       *newexpr;
 975
 976                 /*
 977                  * Reduce constants in the Expr's arguments.  We know args is
 978                  * either NIL or a List node, so we can call
 979                  * expression_tree_mutator directly rather than recursing to self.
 980                  */
 981                 args = (List *) expression_tree_mutator((Node *) expr->args,
 982                                                                                   eval_const_expressions_mutator,
 983                                                                                                 (void *) context);
 984
 985                 switch (expr->opType)
 986                 {
 987                         case OP_EXPR:
 988                         case FUNC_EXPR:
 989
 990                                 /*
 991                                  * Code for op/func case is pretty bulky, so split it out
 992                                  * as a separate function.
 993                                  */
 994                                 newexpr = simplify_op_or_func(expr, args);
 995                                 if (newexpr)    /* successfully simplified it */
 996                                         return (Node *) newexpr;
 997
 998                                 /*
 999                                  * else fall out to build new Expr node with simplified
1000                                  * args
1001                                  */
1002                                 break;
1003                         case OR_EXPR:
1004                                 {
1005
1006                                         /*
1007                                          * OR arguments are handled as follows: non constant:
1008                                          * keep FALSE: drop (does not affect result) TRUE:
1009                                          * force result to TRUE NULL: keep only one We keep
1010                                          * one NULL input because ExecEvalOr returns NULL when
1011                                          * no input is TRUE and at least one is NULL.
1012                                          */
1013                                         List       *newargs = NIL;
1014                                         List       *arg;
1015                                         bool            haveNull = false;
1016                                         bool            forceTrue = false;
1017
1018                                         foreach(arg, args)
1019                                         {
1020                                                 if (!IsA(lfirst(arg), Const))
1021                                                 {
1022                                                         newargs = lappend(newargs, lfirst(arg));
1023                                                         continue;
1024                                                 }
1025                                                 const_input = (Const *) lfirst(arg);
1026                                                 if (const_input->constisnull)
1027                                                         haveNull = true;
1028                                                 else if (DatumGetInt32(const_input->constvalue))
1029                                                         forceTrue = true;
1030                                                 /* otherwise, we can drop the constant-false input */
1031                                         }
1032
1033                                         /*
1034                                          * We could return TRUE before falling out of the
1035                                          * loop, but this coding method will be easier to
1036                                          * adapt if we ever add a notion of non-removable
1037                                          * functions. We'd need to check all the inputs for
1038                                          * non-removability.
1039                                          */
1040                                         if (forceTrue)
1041                                                 return MAKEBOOLCONST(true, false);
1042                                         if (haveNull)
1043                                                 newargs = lappend(newargs, MAKEBOOLCONST(false, true));
1044                                         /* If all the inputs are FALSE, result is FALSE */
1045                                         if (newargs == NIL)
1046                                                 return MAKEBOOLCONST(false, false);
1047                                         /* If only one nonconst-or-NULL input, it's the result */
1048                                         if (lnext(newargs) == NIL)
1049                                                 return (Node *) lfirst(newargs);
1050                                         /* Else we still need an OR node */
1051                                         return (Node *) make_orclause(newargs);
1052                                 }
1053                         case AND_EXPR:
1054                                 {
1055
1056                                         /*
1057                                          * AND arguments are handled as follows: non constant:
1058                                          * keep TRUE: drop (does not affect result) FALSE:
1059                                          * force result to FALSE NULL: keep only one We keep
1060                                          * one NULL input because ExecEvalAnd returns NULL
1061                                          * when no input is FALSE and at least one is NULL.
1062                                          */
1063                                         List       *newargs = NIL;
1064                                         List       *arg;
1065                                         bool            haveNull = false;
1066                                         bool            forceFalse = false;
1067
1068                                         foreach(arg, args)
1069                                         {
1070                                                 if (!IsA(lfirst(arg), Const))
1071                                                 {
1072                                                         newargs = lappend(newargs, lfirst(arg));
1073                                                         continue;
1074                                                 }
1075                                                 const_input = (Const *) lfirst(arg);
1076                                                 if (const_input->constisnull)
1077                                                         haveNull = true;
1078                                                 else if (!DatumGetInt32(const_input->constvalue))
1079                                                         forceFalse = true;
1080                                                 /* otherwise, we can drop the constant-true input */
1081                                         }
1082
1083                                         /*
1084                                          * We could return FALSE before falling out of the
1085                                          * loop, but this coding method will be easier to
1086                                          * adapt if we ever add a notion of non-removable
1087                                          * functions. We'd need to check all the inputs for
1088                                          * non-removability.
1089                                          */
1090                                         if (forceFalse)
1091                                                 return MAKEBOOLCONST(false, false);
1092                                         if (haveNull)
1093                                                 newargs = lappend(newargs, MAKEBOOLCONST(false, true));
1094                                         /* If all the inputs are TRUE, result is TRUE */
1095                                         if (newargs == NIL)
1096                                                 return MAKEBOOLCONST(true, false);
1097                                         /* If only one nonconst-or-NULL input, it's the result */
1098                                         if (lnext(newargs) == NIL)
1099                                                 return (Node *) lfirst(newargs);
1100                                         /* Else we still need an AND node */
1101                                         return (Node *) make_andclause(newargs);
1102                                 }
1103                         case NOT_EXPR:
1104                                 Assert(length(args) == 1);
1105                                 if (!IsA(lfirst(args), Const))
1106                                         break;
1107                                 const_input = (Const *) lfirst(args);
1108                                 /* NOT NULL => NULL */
1109                                 if (const_input->constisnull)
1110                                         return MAKEBOOLCONST(false, true);
1111                                 /* otherwise pretty easy */
1112                                 return MAKEBOOLCONST(!DatumGetInt32(const_input->constvalue),
1113                                                                          false);
1114                         case SUBPLAN_EXPR:
1115
1116                                 /*
1117                                  * Safety measure per notes at head of this routine:
1118                                  * return a SubPlan unchanged.  Too late to do anything
1119                                  * with it.  The arglist simplification above was wasted
1120                                  * work (the list probably only contains Var nodes
1121                                  * anyway).
1122                                  */
1123                                 return (Node *) expr;
1124                         default:
1125                                 elog(ERROR, "eval_const_expressions: unexpected opType %d",
1126                                          (int) expr->opType);
1127                                 break;
1128                 }
1129
1130                 /*
1131                  * If we break out of the above switch on opType, then the
1132                  * expression cannot be simplified any further, so build and
1133                  * return a replacement Expr node using the possibly-simplified
1134                  * arguments and the original oper node. Can't use make_clause()
1135                  * here because we want to be sure the typeOid field is
1136                  * preserved...
1137                  */
1138                 newexpr = makeNode(Expr);
1139                 newexpr->typeOid = expr->typeOid;
1140                 newexpr->opType = expr->opType;
1141                 newexpr->oper = expr->oper;
1142                 newexpr->args = args;
1143                 return (Node *) newexpr;
1144         }
1145         if (IsA(node, RelabelType))
1146         {
1147
1148                 /*
1149                  * If we can simplify the input to a constant, then we don't need
1150                  * the RelabelType node anymore: just change the type field of the
1151                  * Const node.  Otherwise, copy the RelabelType node.
1152                  */
1153                 RelabelType *relabel = (RelabelType *) node;
1154                 Node       *arg;
1155
1156                 arg = eval_const_expressions_mutator(relabel->arg, context);
1157                 if (arg && IsA(arg, Const))
1158                 {
1159                         Const      *con = (Const *) arg;
1160
1161                         con->consttype = relabel->resulttype;
1162
1163                         /*
1164                          * relabel's resulttypmod is discarded, which is OK for now;
1165                          * if the type actually needs a runtime length coercion then
1166                          * there should be a function call to do it just above this
1167                          * node.
1168                          */
1169                         return (Node *) con;
1170                 }
1171                 else
1172                 {
1173                         RelabelType *newrelabel = makeNode(RelabelType);
1174
1175                         newrelabel->arg = arg;
1176                         newrelabel->resulttype = relabel->resulttype;
1177                         newrelabel->resulttypmod = relabel->resulttypmod;
1178                         return (Node *) newrelabel;
1179                 }
1180         }
1181         if (IsA(node, CaseExpr))
1182         {
1183
1184                 /*
1185                  * CASE expressions can be simplified if there are constant
1186                  * condition clauses: FALSE (or NULL): drop the alternative TRUE:
1187                  * drop all remaining alternatives If the first non-FALSE
1188                  * alternative is a constant TRUE, we can simplify the entire CASE
1189                  * to that alternative's expression. If there are no non-FALSE
1190                  * alternatives, we simplify the entire CASE to the default result
1191                  * (ELSE result).
1192                  */
1193                 CaseExpr   *caseexpr = (CaseExpr *) node;
1194                 CaseExpr   *newcase;
1195                 List       *newargs = NIL;
1196                 Node       *defresult;
1197                 Const      *const_input;
1198                 List       *arg;
1199
1200                 foreach(arg, caseexpr->args)
1201                 {
1202                         /* Simplify this alternative's condition and result */
1203                         CaseWhen   *casewhen = (CaseWhen *)
1204                         expression_tree_mutator((Node *) lfirst(arg),
1205                                                                         eval_const_expressions_mutator,
1206                                                                         (void *) context);
1207
1208                         Assert(IsA(casewhen, CaseWhen));
1209                         if (casewhen->expr == NULL ||
1210                                 !IsA(casewhen->expr, Const))
1211                         {
1212                                 newargs = lappend(newargs, casewhen);
1213                                 continue;
1214                         }
1215                         const_input = (Const *) casewhen->expr;
1216                         if (const_input->constisnull ||
1217                                 !DatumGetInt32(const_input->constvalue))
1218                                 continue;               /* drop alternative with FALSE condition */
1219
1220                         /*
1221                          * Found a TRUE condition.      If it's the first (un-dropped)
1222                          * alternative, the CASE reduces to just this alternative.
1223                          */
1224                         if (newargs == NIL)
1225                                 return casewhen->result;
1226
1227                         /*
1228                          * Otherwise, add it to the list, and drop all the rest.
1229                          */
1230                         newargs = lappend(newargs, casewhen);
1231                         break;
1232                 }
1233
1234                 /* Simplify the default result */
1235                 defresult = eval_const_expressions_mutator(caseexpr->defresult,
1236                                                                                                    context);
1237
1238                 /*
1239                  * If no non-FALSE alternatives, CASE reduces to the default
1240                  * result
1241                  */
1242                 if (newargs == NIL)
1243                         return defresult;
1244                 /* Otherwise we need a new CASE node */
1245                 newcase = makeNode(CaseExpr);
1246                 newcase->casetype = caseexpr->casetype;
1247                 newcase->arg = NULL;
1248                 newcase->args = newargs;
1249                 newcase->defresult = defresult;
1250                 return (Node *) newcase;
1251         }
1252         if (IsA(node, Iter))
1253         {
1254
1255                 /*
1256                  * The argument of an Iter is normally a function call. We must
1257                  * not try to eliminate the function, but we can try to simplify
1258                  * its arguments.  If, by chance, the arg is NOT a function then
1259                  * we go ahead and try to simplify it (by falling into
1260                  * expression_tree_mutator). Is that the right thing?
1261                  */
1262                 Iter       *iter = (Iter *) node;
1263
1264                 if (is_funcclause(iter->iterexpr))
1265                 {
1266                         Expr       *func = (Expr *) iter->iterexpr;
1267                         Expr       *newfunc;
1268                         Iter       *newiter;
1269
1270                         newfunc = makeNode(Expr);
1271                         newfunc->typeOid = func->typeOid;
1272                         newfunc->opType = func->opType;
1273                         newfunc->oper = func->oper;
1274                         newfunc->args = (List *)
1275                                 expression_tree_mutator((Node *) func->args,
1276                                                                                 eval_const_expressions_mutator,
1277                                                                                 (void *) context);
1278                         newiter = makeNode(Iter);
1279                         newiter->iterexpr = (Node *) newfunc;
1280                         newiter->itertype = iter->itertype;
1281                         return (Node *) newiter;
1282                 }
1283         }
1284
1285         /*
1286          * For any node type not handled above, we recurse using
1287          * expression_tree_mutator, which will copy the node unchanged but try
1288          * to simplify its arguments (if any) using this routine. For example:
1289          * we cannot eliminate an ArrayRef node, but we might be able to
1290          * simplify constant expressions in its subscripts.
1291          */
1292         return expression_tree_mutator(node, eval_const_expressions_mutator,
1293                                                                    (void *) context);
1294 }
1295
1296 /*
1297  * Subroutine for eval_const_expressions: try to evaluate an op or func
1298  *
1299  * Inputs are the op or func Expr node, and the pre-simplified argument list.
1300  * Returns a simplified expression if successful, or NULL if cannot
1301  * simplify the op/func.
1302  *
1303  * XXX Possible future improvement: if the func is SQL-language, and its
1304  * definition is simply "SELECT expression", we could parse and substitute
1305  * the expression here.  This would avoid much runtime overhead, and perhaps
1306  * expose opportunities for constant-folding within the expression even if
1307  * not all the func's input args are constants.  It'd be appropriate to do
1308  * that here, not in the parser, since we wouldn't want it to happen until
1309  * after rule substitution/rewriting.
1310  */
1311 static Expr *
1312 simplify_op_or_func(Expr *expr, List *args)
1313 {
1314         List       *arg;
1315         Oid                     funcid;
1316         Oid                     result_typeid;
1317         HeapTuple       func_tuple;
1318         Form_pg_proc funcform;
1319         Type            resultType;
1320         Expr       *newexpr;
1321         Datum           const_val;
1322         bool            has_nonconst_input = false;
1323         bool            has_null_input = false;
1324         bool            const_is_null;
1325         bool            isDone;
1326
1327         /*
1328          * Check for constant inputs and especially constant-NULL inputs.
1329          */
1330         foreach(arg, args)
1331         {
1332                 if (IsA(lfirst(arg), Const))
1333                         has_null_input |= ((Const *) lfirst(arg))->constisnull;
1334                 else
1335                         has_nonconst_input = true;
1336         }
1337
1338         /*
1339          * If the function is strict and has a constant-NULL input, it will
1340          * never be called at all, so we can replace the call by a NULL
1341          * constant even if there are other inputs that aren't constant.
1342          * Otherwise, we can only simplify if all inputs are constants.
1343          * We can skip the function lookup if neither case applies.
1344          */
1345         if (has_nonconst_input && !has_null_input)
1346                 return NULL;
1347
1348         /*
1349          * Get the function procedure's OID and look to see whether it is
1350          * marked proiscachable.
1351          *
1352          * XXX would it be better to take the result type from the pg_proc tuple,
1353          * rather than the Oper or Func node?
1354          */
1355         if (expr->opType == OP_EXPR)
1356         {
1357                 Oper       *oper = (Oper *) expr->oper;
1358
1359                 replace_opid(oper);             /* OK to scribble on input to this extent */
1360                 funcid = oper->opid;
1361                 result_typeid = oper->opresulttype;
1362         }
1363         else
1364         {
1365                 Func       *func = (Func *) expr->oper;
1366
1367                 funcid = func->funcid;
1368                 result_typeid = func->functype;
1369         }
1370         /* Someday lsyscache.c might provide a function for this */
1371         func_tuple = SearchSysCacheTuple(PROCOID,
1372                                                                          ObjectIdGetDatum(funcid),
1373                                                                          0, 0, 0);
1374         if (!HeapTupleIsValid(func_tuple))
1375                 elog(ERROR, "Function OID %u does not exist", funcid);
1376         funcform = (Form_pg_proc) GETSTRUCT(func_tuple);
1377         if (!funcform->proiscachable)
1378                 return NULL;
1379
1380         /*
1381          * Also check to make sure it doesn't return a set.
1382          */
1383         if (funcform->proretset)
1384                 return NULL;
1385
1386         /*
1387          * Now that we know if the function is strict, we can finish the
1388          * checks for simplifiable inputs that we started above.
1389          */
1390         if (funcform->proisstrict && has_null_input)
1391         {
1392                 /*
1393                  * It's strict and has NULL input, so must produce NULL output.
1394                  * Return a NULL constant of the right type.
1395                  */
1396                 resultType = typeidType(result_typeid);
1397                 return (Expr *) makeConst(result_typeid, typeLen(resultType),
1398                                                                   (Datum) 0, true,
1399                                                                   typeByVal(resultType),
1400                                                                   false, false);
1401         }
1402
1403         /*
1404          * Otherwise, can simplify only if all inputs are constants.
1405          * (For a non-strict function, constant NULL inputs are treated
1406          * the same as constant non-NULL inputs.)
1407          */
1408         if (has_nonconst_input)
1409                 return NULL;
1410
1411         /*
1412          * OK, looks like we can simplify this operator/function.
1413          *
1414          * We use the executor's routine ExecEvalExpr() to avoid duplication of
1415          * code and ensure we get the same result as the executor would get.
1416          *
1417          * Build a new Expr node containing the already-simplified arguments. The
1418          * only other setup needed here is the replace_opid() that we already
1419          * did for the OP_EXPR case.
1420          */
1421         newexpr = makeNode(Expr);
1422         newexpr->typeOid = expr->typeOid;
1423         newexpr->opType = expr->opType;
1424         newexpr->oper = expr->oper;
1425         newexpr->args = args;
1426
1427         /*
1428          * It is OK to pass econtext = NULL because none of the ExecEvalExpr()
1429          * code used in this situation will use econtext.  That might seem
1430          * fortuitous, but it's not so unreasonable --- a constant expression
1431          * does not depend on context, by definition, n'est ce pas?
1432          */
1433         const_val = ExecEvalExpr((Node *) newexpr, NULL,
1434                                                          &const_is_null, &isDone);
1435         Assert(isDone);                         /* if this isn't set, we blew it... */
1436         pfree(newexpr);
1437
1438         /*
1439          * Make the constant result node.
1440          */
1441         resultType = typeidType(result_typeid);
1442         return (Expr *) makeConst(result_typeid, typeLen(resultType),
1443                                                           const_val, const_is_null,
1444                                                           typeByVal(resultType),
1445                                                           false, false);
1446 }
1447
1448
1449 /*
1450  * Standard expression-tree walking support
1451  *
1452  * We used to have near-duplicate code in many different routines that
1453  * understood how to recurse through an expression node tree.  That was
1454  * a pain to maintain, and we frequently had bugs due to some particular
1455  * routine neglecting to support a particular node type.  In most cases,
1456  * these routines only actually care about certain node types, and don't
1457  * care about other types except insofar as they have to recurse through
1458  * non-primitive node types.  Therefore, we now provide generic tree-walking
1459  * logic to consolidate the redundant "boilerplate" code.  There are
1460  * two versions: expression_tree_walker() and expression_tree_mutator().
1461  */
1462
1463 /*--------------------
1464  * expression_tree_walker() is designed to support routines that traverse
1465  * a tree in a read-only fashion (although it will also work for routines
1466  * that modify nodes in-place but never add/delete/replace nodes).
1467  * A walker routine should look like this:
1468  *
1469  * bool my_walker (Node *node, my_struct *context)
1470  * {
1471  *              if (node == NULL)
1472  *                      return false;
1473  *              // check for nodes that special work is required for, eg:
1474  *              if (IsA(node, Var))
1475  *              {
1476  *                      ... do special actions for Var nodes
1477  *              }
1478  *              else if (IsA(node, ...))
1479  *              {
1480  *                      ... do special actions for other node types
1481  *              }
1482  *              // for any node type not specially processed, do:
1483  *              return expression_tree_walker(node, my_walker, (void *) context);
1484  * }
1485  *
1486  * The "context" argument points to a struct that holds whatever context
1487  * information the walker routine needs --- it can be used to return data
1488  * gathered by the walker, too.  This argument is not touched by
1489  * expression_tree_walker, but it is passed down to recursive sub-invocations
1490  * of my_walker.  The tree walk is started from a setup routine that
1491  * fills in the appropriate context struct, calls my_walker with the top-level
1492  * node of the tree, and then examines the results.
1493  *
1494  * The walker routine should return "false" to continue the tree walk, or
1495  * "true" to abort the walk and immediately return "true" to the top-level
1496  * caller.      This can be used to short-circuit the traversal if the walker
1497  * has found what it came for.  "false" is returned to the top-level caller
1498  * iff no invocation of the walker returned "true".
1499  *
1500  * The node types handled by expression_tree_walker include all those
1501  * normally found in target lists and qualifier clauses during the planning
1502  * stage.  In particular, it handles List nodes since a cnf-ified qual clause
1503  * will have List structure at the top level, and it handles TargetEntry nodes
1504  * so that a scan of a target list can be handled without additional code.
1505  * (But only the "expr" part of a TargetEntry is examined, unless the walker
1506  * chooses to process TargetEntry nodes specially.)
1507  *
1508  * expression_tree_walker will handle a SUBPLAN_EXPR node by recursing into
1509  * the args and slink->oper lists (which belong to the outer plan), but it
1510  * will *not* visit the inner plan, since that's typically what expression
1511  * tree walkers want.  A walker that wants to visit the subplan can force
1512  * appropriate behavior by recognizing subplan expression nodes and doing
1513  * the right thing.
1514  *
1515  * Bare SubLink nodes (without a SUBPLAN_EXPR) are handled by recursing into
1516  * the "lefthand" argument list only.  (A bare SubLink should be seen only if
1517  * the tree has not yet been processed by subselect.c.)  Again, this can be
1518  * overridden by the walker, but it seems to be the most useful default
1519  * behavior.
1520  *--------------------
1521  */
1522
1523 bool
1524                         expression_tree_walker(Node *node, bool (*walker) (), void *context)
1525 {
1526         List       *temp;
1527
1528         /*
1529          * The walker has already visited the current node, and so we need
1530          * only recurse into any sub-nodes it has.
1531          *
1532          * We assume that the walker is not interested in List nodes per se, so
1533          * when we expect a List we just recurse directly to self without
1534          * bothering to call the walker.
1535          */
1536         if (node == NULL)
1537                 return false;
1538         switch (nodeTag(node))
1539         {
1540                 case T_Ident:
1541                 case T_Const:
1542                 case T_Var:
1543                 case T_Param:
1544                         /* primitive node types with no subnodes */
1545                         break;
1546                 case T_Expr:
1547                         {
1548                                 Expr       *expr = (Expr *) node;
1549
1550                                 if (expr->opType == SUBPLAN_EXPR)
1551                                 {
1552                                         /* recurse to the SubLink node (skipping SubPlan!) */
1553                                         if (walker((Node *) ((SubPlan *) expr->oper)->sublink,
1554                                                            context))
1555                                                 return true;
1556                                 }
1557                                 /* for all Expr node types, examine args list */
1558                                 if (expression_tree_walker((Node *) expr->args,
1559                                                                                    walker, context))
1560                                         return true;
1561                         }
1562                         break;
1563                 case T_Aggref:
1564                         return walker(((Aggref *) node)->target, context);
1565                 case T_Iter:
1566                         return walker(((Iter *) node)->iterexpr, context);
1567                 case T_ArrayRef:
1568                         {
1569                                 ArrayRef   *aref = (ArrayRef *) node;
1570
1571                                 /* recurse directly for upper/lower array index lists */
1572                                 if (expression_tree_walker((Node *) aref->refupperindexpr,
1573                                                                                    walker, context))
1574                                         return true;
1575                                 if (expression_tree_walker((Node *) aref->reflowerindexpr,
1576                                                                                    walker, context))
1577                                         return true;
1578                                 /* walker must see the refexpr and refassgnexpr, however */
1579                                 if (walker(aref->refexpr, context))
1580                                         return true;
1581                                 if (walker(aref->refassgnexpr, context))
1582                                         return true;
1583                         }
1584                         break;
1585                 case T_RelabelType:
1586                         return walker(((RelabelType *) node)->arg, context);
1587                 case T_CaseExpr:
1588                         {
1589                                 CaseExpr   *caseexpr = (CaseExpr *) node;
1590
1591                                 /* we assume walker doesn't care about CaseWhens, either */
1592                                 foreach(temp, caseexpr->args)
1593                                 {
1594                                         CaseWhen   *when = (CaseWhen *) lfirst(temp);
1595
1596                                         Assert(IsA(when, CaseWhen));
1597                                         if (walker(when->expr, context))
1598                                                 return true;
1599                                         if (walker(when->result, context))
1600                                                 return true;
1601                                 }
1602                                 /* caseexpr->arg should be null, but we'll check it anyway */
1603                                 if (walker(caseexpr->arg, context))
1604                                         return true;
1605                                 if (walker(caseexpr->defresult, context))
1606                                         return true;
1607                         }
1608                         break;
1609                 case T_SubLink:
1610                         {
1611                                 SubLink    *sublink = (SubLink *) node;
1612
1613                                 /*
1614                                  * If the SubLink has already been processed by
1615                                  * subselect.c, it will have lefthand=NIL, and we only
1616                                  * need to look at the oper list.  Otherwise we only need
1617                                  * to look at lefthand (the Oper nodes in the oper list
1618                                  * are deemed uninteresting).
1619                                  */
1620                                 if (sublink->lefthand)
1621                                         return walker((Node *) sublink->lefthand, context);
1622                                 else
1623                                         return walker((Node *) sublink->oper, context);
1624                         }
1625                         break;
1626                 case T_List:
1627                         foreach(temp, (List *) node)
1628                         {
1629                                 if (walker((Node *) lfirst(temp), context))
1630                                         return true;
1631                         }
1632                         break;
1633                 case T_TargetEntry:
1634                         return walker(((TargetEntry *) node)->expr, context);
1635                 default:
1636                         elog(ERROR, "expression_tree_walker: Unexpected node type %d",
1637                                  nodeTag(node));
1638                         break;
1639         }
1640         return false;
1641 }
1642
1643 /*--------------------
1644  * expression_tree_mutator() is designed to support routines that make a
1645  * modified copy of an expression tree, with some nodes being added,
1646  * removed, or replaced by new subtrees.  The original tree is (normally)
1647  * not changed.  Each recursion level is responsible for returning a copy of
1648  * (or appropriately modified substitute for) the subtree it is handed.
1649  * A mutator routine should look like this:
1650  *
1651  * Node * my_mutator (Node *node, my_struct *context)
1652  * {
1653  *              if (node == NULL)
1654  *                      return NULL;
1655  *              // check for nodes that special work is required for, eg:
1656  *              if (IsA(node, Var))
1657  *              {
1658  *                      ... create and return modified copy of Var node
1659  *              }
1660  *              else if (IsA(node, ...))
1661  *              {
1662  *                      ... do special transformations of other node types
1663  *              }
1664  *              // for any node type not specially processed, do:
1665  *              return expression_tree_mutator(node, my_mutator, (void *) context);
1666  * }
1667  *
1668  * The "context" argument points to a struct that holds whatever context
1669  * information the mutator routine needs --- it can be used to return extra
1670  * data gathered by the mutator, too.  This argument is not touched by
1671  * expression_tree_mutator, but it is passed down to recursive sub-invocations
1672  * of my_mutator.  The tree walk is started from a setup routine that
1673  * fills in the appropriate context struct, calls my_mutator with the
1674  * top-level node of the tree, and does any required post-processing.
1675  *
1676  * Each level of recursion must return an appropriately modified Node.
1677  * If expression_tree_mutator() is called, it will make an exact copy
1678  * of the given Node, but invoke my_mutator() to copy the sub-node(s)
1679  * of that Node.  In this way, my_mutator() has full control over the
1680  * copying process but need not directly deal with expression trees
1681  * that it has no interest in.
1682  *
1683  * Just as for expression_tree_walker, the node types handled by
1684  * expression_tree_mutator include all those normally found in target lists
1685  * and qualifier clauses during the planning stage.
1686  *
1687  * expression_tree_mutator will handle a SUBPLAN_EXPR node by recursing into
1688  * the args and slink->oper lists (which belong to the outer plan), but it
1689  * will simply copy the link to the inner plan, since that's typically what
1690  * expression tree mutators want.  A mutator that wants to modify the subplan
1691  * can force appropriate behavior by recognizing subplan expression nodes
1692  * and doing the right thing.
1693  *
1694  * Bare SubLink nodes (without a SUBPLAN_EXPR) are handled by recursing into
1695  * the "lefthand" argument list only.  (A bare SubLink should be seen only if
1696  * the tree has not yet been processed by subselect.c.)  Again, this can be
1697  * overridden by the mutator, but it seems to be the most useful default
1698  * behavior.
1699  *--------------------
1700  */
1701
1702 Node *
1703                         expression_tree_mutator(Node *node, Node *(*mutator) (), void *context)
1704 {
1705
1706         /*
1707          * The mutator has already decided not to modify the current node, but
1708          * we must call the mutator for any sub-nodes.
1709          */
1710
1711 #define FLATCOPY(newnode, node, nodetype)  \
1712         ( (newnode) = makeNode(nodetype), \
1713           memcpy((newnode), (node), sizeof(nodetype)) )
1714
1715 #define CHECKFLATCOPY(newnode, node, nodetype)  \
1716         ( AssertMacro(IsA((node), nodetype)), \
1717           (newnode) = makeNode(nodetype), \
1718           memcpy((newnode), (node), sizeof(nodetype)) )
1719
1720 #define MUTATE(newfield, oldfield, fieldtype)  \
1721                 ( (newfield) = (fieldtype) mutator((Node *) (oldfield), context) )
1722
1723         if (node == NULL)
1724                 return NULL;
1725         switch (nodeTag(node))
1726         {
1727                 case T_Ident:
1728                 case T_Const:
1729                 case T_Var:
1730                 case T_Param:
1731                         /* primitive node types with no subnodes */
1732                         return (Node *) copyObject(node);
1733                 case T_Expr:
1734                         {
1735                                 Expr       *expr = (Expr *) node;
1736                                 Expr       *newnode;
1737
1738                                 FLATCOPY(newnode, expr, Expr);
1739
1740                                 if (expr->opType == SUBPLAN_EXPR)
1741                                 {
1742                                         SubLink    *oldsublink = ((SubPlan *) expr->oper)->sublink;
1743                                         SubPlan    *newsubplan;
1744
1745                                         /* flat-copy the oper node, which is a SubPlan */
1746                                         CHECKFLATCOPY(newsubplan, expr->oper, SubPlan);
1747                                         newnode->oper = (Node *) newsubplan;
1748                                         /* likewise its SubLink node */
1749                                         CHECKFLATCOPY(newsubplan->sublink, oldsublink, SubLink);
1750
1751                                         /*
1752                                          * transform args list (params to be passed to
1753                                          * subplan)
1754                                          */
1755                                         MUTATE(newnode->args, expr->args, List *);
1756                                         /* transform sublink's oper list as well */
1757                                         MUTATE(newsubplan->sublink->oper, oldsublink->oper, List *);
1758
1759                                         /*
1760                                          * but not the subplan itself, which is referenced
1761                                          * as-is
1762                                          */
1763                                 }
1764                                 else
1765                                 {
1766
1767                                         /*
1768                                          * for other Expr node types, just transform args
1769                                          * list, linking to original oper node (OK?)
1770                                          */
1771                                         MUTATE(newnode->args, expr->args, List *);
1772                                 }
1773                                 return (Node *) newnode;
1774                         }
1775                         break;
1776                 case T_Aggref:
1777                         {
1778                                 Aggref     *aggref = (Aggref *) node;
1779                                 Aggref     *newnode;
1780
1781                                 FLATCOPY(newnode, aggref, Aggref);
1782                                 MUTATE(newnode->target, aggref->target, Node *);
1783                                 return (Node *) newnode;
1784                         }
1785                         break;
1786                 case T_Iter:
1787                         {
1788                                 Iter       *iter = (Iter *) node;
1789                                 Iter       *newnode;
1790
1791                                 FLATCOPY(newnode, iter, Iter);
1792                                 MUTATE(newnode->iterexpr, iter->iterexpr, Node *);
1793                                 return (Node *) newnode;
1794                         }
1795                         break;
1796                 case T_ArrayRef:
1797                         {
1798                                 ArrayRef   *arrayref = (ArrayRef *) node;
1799                                 ArrayRef   *newnode;
1800
1801                                 FLATCOPY(newnode, arrayref, ArrayRef);
1802                                 MUTATE(newnode->refupperindexpr, arrayref->refupperindexpr,
1803                                            List *);
1804                                 MUTATE(newnode->reflowerindexpr, arrayref->reflowerindexpr,
1805                                            List *);
1806                                 MUTATE(newnode->refexpr, arrayref->refexpr,
1807                                            Node *);
1808                                 MUTATE(newnode->refassgnexpr, arrayref->refassgnexpr,
1809                                            Node *);
1810                                 return (Node *) newnode;
1811                         }
1812                         break;
1813                 case T_RelabelType:
1814                         {
1815                                 RelabelType *relabel = (RelabelType *) node;
1816                                 RelabelType *newnode;
1817
1818                                 FLATCOPY(newnode, relabel, RelabelType);
1819                                 MUTATE(newnode->arg, relabel->arg, Node *);
1820                                 return (Node *) newnode;
1821                         }
1822                         break;
1823                 case T_CaseExpr:
1824                         {
1825                                 CaseExpr   *caseexpr = (CaseExpr *) node;
1826                                 CaseExpr   *newnode;
1827
1828                                 FLATCOPY(newnode, caseexpr, CaseExpr);
1829                                 MUTATE(newnode->args, caseexpr->args, List *);
1830                                 /* caseexpr->arg should be null, but we'll check it anyway */
1831                                 MUTATE(newnode->arg, caseexpr->arg, Node *);
1832                                 MUTATE(newnode->defresult, caseexpr->defresult, Node *);
1833                                 return (Node *) newnode;
1834                         }
1835                         break;
1836                 case T_CaseWhen:
1837                         {
1838                                 CaseWhen   *casewhen = (CaseWhen *) node;
1839                                 CaseWhen   *newnode;
1840
1841                                 FLATCOPY(newnode, casewhen, CaseWhen);
1842                                 MUTATE(newnode->expr, casewhen->expr, Node *);
1843                                 MUTATE(newnode->result, casewhen->result, Node *);
1844                                 return (Node *) newnode;
1845                         }
1846                         break;
1847                 case T_SubLink:
1848                         {
1849
1850                                 /*
1851                                  * A "bare" SubLink (note we will not come here if we
1852                                  * found a SUBPLAN_EXPR node above it).  Transform the
1853                                  * lefthand side, but not the oper list nor the subquery.
1854                                  */
1855                                 SubLink    *sublink = (SubLink *) node;
1856                                 SubLink    *newnode;
1857
1858                                 FLATCOPY(newnode, sublink, SubLink);
1859                                 MUTATE(newnode->lefthand, sublink->lefthand, List *);
1860                                 return (Node *) newnode;
1861                         }
1862                         break;
1863                 case T_List:
1864                         {
1865
1866                                 /*
1867                                  * We assume the mutator isn't interested in the list
1868                                  * nodes per se, so just invoke it on each list element.
1869                                  * NOTE: this would fail badly on a list with integer
1870                                  * elements!
1871                                  */
1872                                 List       *resultlist = NIL;
1873                                 List       *temp;
1874
1875                                 foreach(temp, (List *) node)
1876                                 {
1877                                         resultlist = lappend(resultlist,
1878                                                                                  mutator((Node *) lfirst(temp),
1879                                                                                                  context));
1880                                 }
1881                                 return (Node *) resultlist;
1882                         }
1883                         break;
1884                 case T_TargetEntry:
1885                         {
1886
1887                                 /*
1888                                  * We mutate the expression, but not the resdom, by
1889                                  * default.
1890                                  */
1891                                 TargetEntry *targetentry = (TargetEntry *) node;
1892                                 TargetEntry *newnode;
1893
1894                                 FLATCOPY(newnode, targetentry, TargetEntry);
1895                                 MUTATE(newnode->expr, targetentry->expr, Node *);
1896                                 return (Node *) newnode;
1897                         }
1898                         break;
1899                 default:
1900                         elog(ERROR, "expression_tree_mutator: Unexpected node type %d",
1901                                  nodeTag(node));
1902                         break;
1903         }
1904         /* can't get here, but keep compiler happy */
1905         return NULL;
1906 }