src/backend/parser/parse_cte.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * parse_cte.c
   4  *        handle CTEs (common table expressions) in parser
   5  *
   6  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/parser/parse_cte.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "catalog/pg_collation.h"
  18 #include "catalog/pg_type.h"
  19 #include "nodes/nodeFuncs.h"
  20 #include "parser/analyze.h"
  21 #include "parser/parse_cte.h"
  22 #include "utils/builtins.h"
  23 #include "utils/lsyscache.h"
  24
  25
  26 /* Enumeration of contexts in which a self-reference is disallowed */
  27 typedef enum
  28 {
  29         RECURSION_OK,
  30         RECURSION_NONRECURSIVETERM, /* inside the left-hand term */
  31         RECURSION_SUBLINK,                      /* inside a sublink */
  32         RECURSION_OUTERJOIN,            /* inside nullable side of an outer join */
  33         RECURSION_INTERSECT,            /* underneath INTERSECT (ALL) */
  34         RECURSION_EXCEPT                        /* underneath EXCEPT (ALL) */
  35 } RecursionContext;
  36
  37 /* Associated error messages --- each must have one %s for CTE name */
  38 static const char *const recursion_errormsgs[] = {
  39         /* RECURSION_OK */
  40         NULL,
  41         /* RECURSION_NONRECURSIVETERM */
  42         gettext_noop("recursive reference to query \"%s\" must not appear within its non-recursive term"),
  43         /* RECURSION_SUBLINK */
  44         gettext_noop("recursive reference to query \"%s\" must not appear within a subquery"),
  45         /* RECURSION_OUTERJOIN */
  46         gettext_noop("recursive reference to query \"%s\" must not appear within an outer join"),
  47         /* RECURSION_INTERSECT */
  48         gettext_noop("recursive reference to query \"%s\" must not appear within INTERSECT"),
  49         /* RECURSION_EXCEPT */
  50         gettext_noop("recursive reference to query \"%s\" must not appear within EXCEPT")
  51 };
  52
  53 /*
  54  * For WITH RECURSIVE, we have to find an ordering of the clause members
  55  * with no forward references, and determine which members are recursive
  56  * (i.e., self-referential).  It is convenient to do this with an array
  57  * of CteItems instead of a list of CommonTableExprs.
  58  */
  59 typedef struct CteItem
  60 {
  61         CommonTableExpr *cte;           /* One CTE to examine */
  62         int                     id;                             /* Its ID number for dependencies */
  63         Bitmapset  *depends_on;         /* CTEs depended on (not including self) */
  64 } CteItem;
  65
  66 /* CteState is what we need to pass around in the tree walkers */
  67 typedef struct CteState
  68 {
  69         /* global state: */
  70         ParseState *pstate;                     /* global parse state */
  71         CteItem    *items;                      /* array of CTEs and extra data */
  72         int                     numitems;               /* number of CTEs */
  73         /* working state during a tree walk: */
  74         int                     curitem;                /* index of item currently being examined */
  75         List       *innerwiths;         /* list of lists of CommonTableExpr */
  76         /* working state for checkWellFormedRecursion walk only: */
  77         int                     selfrefcount;   /* number of self-references detected */
  78         RecursionContext context;       /* context to allow or disallow self-ref */
  79 } CteState;
  80
  81
  82 static void analyzeCTE(ParseState *pstate, CommonTableExpr *cte);
  83
  84 /* Dependency processing functions */
  85 static void makeDependencyGraph(CteState *cstate);
  86 static bool makeDependencyGraphWalker(Node *node, CteState *cstate);
  87 static void TopologicalSort(ParseState *pstate, CteItem *items, int numitems);
  88
  89 /* Recursion validity checker functions */
  90 static void checkWellFormedRecursion(CteState *cstate);
  91 static bool checkWellFormedRecursionWalker(Node *node, CteState *cstate);
  92 static void checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate);
  93
  94
  95 /*
  96  * transformWithClause -
  97  *        Transform the list of WITH clause "common table expressions" into
  98  *        Query nodes.
  99  *
 100  * The result is the list of transformed CTEs to be put into the output
 101  * Query.  (This is in fact the same as the ending value of p_ctenamespace,
 102  * but it seems cleaner to not expose that in the function's API.)
 103  */
 104 List *
 105 transformWithClause(ParseState *pstate, WithClause *withClause)
 106 {
 107         ListCell   *lc;
 108
 109         /* Only one WITH clause per query level */
 110         Assert(pstate->p_ctenamespace == NIL);
 111         Assert(pstate->p_future_ctes == NIL);
 112
 113         /*
 114          * For either type of WITH, there must not be duplicate CTE names in the
 115          * list.  Check this right away so we needn't worry later.
 116          *
 117          * Also, tentatively mark each CTE as non-recursive, and initialize its
 118          * reference count to zero, and set pstate->p_hasModifyingCTE if needed.
 119          */
 120         foreach(lc, withClause->ctes)
 121         {
 122                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 123                 ListCell   *rest;
 124
 125                 for_each_cell(rest, lnext(lc))
 126                 {
 127                         CommonTableExpr *cte2 = (CommonTableExpr *) lfirst(rest);
 128
 129                         if (strcmp(cte->ctename, cte2->ctename) == 0)
 130                                 ereport(ERROR,
 131                                                 (errcode(ERRCODE_DUPLICATE_ALIAS),
 132                                         errmsg("WITH query name \"%s\" specified more than once",
 133                                                    cte2->ctename),
 134                                                  parser_errposition(pstate, cte2->location)));
 135                 }
 136
 137                 cte->cterecursive = false;
 138                 cte->cterefcount = 0;
 139
 140                 if (!IsA(cte->ctequery, SelectStmt))
 141                 {
 142                         /* must be a data-modifying statement */
 143                         Assert(IsA(cte->ctequery, InsertStmt) ||
 144                                    IsA(cte->ctequery, UpdateStmt) ||
 145                                    IsA(cte->ctequery, DeleteStmt));
 146
 147                         pstate->p_hasModifyingCTE = true;
 148                 }
 149         }
 150
 151         if (withClause->recursive)
 152         {
 153                 /*
 154                  * For WITH RECURSIVE, we rearrange the list elements if needed to
 155                  * eliminate forward references.  First, build a work array and set up
 156                  * the data structure needed by the tree walkers.
 157                  */
 158                 CteState        cstate;
 159                 int                     i;
 160
 161                 cstate.pstate = pstate;
 162                 cstate.numitems = list_length(withClause->ctes);
 163                 cstate.items = (CteItem *) palloc0(cstate.numitems * sizeof(CteItem));
 164                 i = 0;
 165                 foreach(lc, withClause->ctes)
 166                 {
 167                         cstate.items[i].cte = (CommonTableExpr *) lfirst(lc);
 168                         cstate.items[i].id = i;
 169                         i++;
 170                 }
 171
 172                 /*
 173                  * Find all the dependencies and sort the CteItems into a safe
 174                  * processing order.  Also, mark CTEs that contain self-references.
 175                  */
 176                 makeDependencyGraph(&cstate);
 177
 178                 /*
 179                  * Check that recursive queries are well-formed.
 180                  */
 181                 checkWellFormedRecursion(&cstate);
 182
 183                 /*
 184                  * Set up the ctenamespace for parse analysis.  Per spec, all the WITH
 185                  * items are visible to all others, so stuff them all in before parse
 186                  * analysis.  We build the list in safe processing order so that the
 187                  * planner can process the queries in sequence.
 188                  */
 189                 for (i = 0; i < cstate.numitems; i++)
 190                 {
 191                         CommonTableExpr *cte = cstate.items[i].cte;
 192
 193                         pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte);
 194                 }
 195
 196                 /*
 197                  * Do parse analysis in the order determined by the topological sort.
 198                  */
 199                 for (i = 0; i < cstate.numitems; i++)
 200                 {
 201                         CommonTableExpr *cte = cstate.items[i].cte;
 202
 203                         analyzeCTE(pstate, cte);
 204                 }
 205         }
 206         else
 207         {
 208                 /*
 209                  * For non-recursive WITH, just analyze each CTE in sequence and then
 210                  * add it to the ctenamespace.  This corresponds to the spec's
 211                  * definition of the scope of each WITH name.  However, to allow error
 212                  * reports to be aware of the possibility of an erroneous reference,
 213                  * we maintain a list in p_future_ctes of the not-yet-visible CTEs.
 214                  */
 215                 pstate->p_future_ctes = list_copy(withClause->ctes);
 216
 217                 foreach(lc, withClause->ctes)
 218                 {
 219                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 220
 221                         analyzeCTE(pstate, cte);
 222                         pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte);
 223                         pstate->p_future_ctes = list_delete_first(pstate->p_future_ctes);
 224                 }
 225         }
 226
 227         return pstate->p_ctenamespace;
 228 }
 229
 230
 231 /*
 232  * Perform the actual parse analysis transformation of one CTE.  All
 233  * CTEs it depends on have already been loaded into pstate->p_ctenamespace,
 234  * and have been marked with the correct output column names/types.
 235  */
 236 static void
 237 analyzeCTE(ParseState *pstate, CommonTableExpr *cte)
 238 {
 239         Query      *query;
 240
 241         /* Analysis not done already */
 242         Assert(!IsA(cte->ctequery, Query));
 243
 244         query = parse_sub_analyze(cte->ctequery, pstate, cte, false);
 245         cte->ctequery = (Node *) query;
 246
 247         /*
 248          * Check that we got something reasonable.  These first two cases should
 249          * be prevented by the grammar.
 250          */
 251         if (!IsA(query, Query))
 252                 elog(ERROR, "unexpected non-Query statement in WITH");
 253         if (query->utilityStmt != NULL)
 254                 elog(ERROR, "unexpected utility statement in WITH");
 255
 256         if (query->intoClause)
 257                 ereport(ERROR,
 258                                 (errcode(ERRCODE_SYNTAX_ERROR),
 259                                  errmsg("subquery in WITH cannot have SELECT INTO"),
 260                                  parser_errposition(pstate,
 261                                                                  exprLocation((Node *) query->intoClause))));
 262
 263         /*
 264          * We disallow data-modifying WITH except at the top level of a query,
 265          * because it's not clear when such a modification should be executed.
 266          */
 267         if (query->commandType != CMD_SELECT &&
 268                 pstate->parentParseState != NULL)
 269                 ereport(ERROR,
 270                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 271                                  errmsg("WITH clause containing a data-modifying statement must be at the top level"),
 272                                  parser_errposition(pstate, cte->location)));
 273
 274         /*
 275          * CTE queries are always marked not canSetTag.  (Currently this only
 276          * matters for data-modifying statements, for which the flag will be
 277          * propagated to the ModifyTable plan node.)
 278          */
 279         query->canSetTag = false;
 280
 281         if (!cte->cterecursive)
 282         {
 283                 /* Compute the output column names/types if not done yet */
 284                 analyzeCTETargetList(pstate, cte, GetCTETargetList(cte));
 285         }
 286         else
 287         {
 288                 /*
 289                  * Verify that the previously determined output column types match
 290                  * what the query really produced.      We have to check this because the
 291                  * recursive term could have overridden the non-recursive term, and we
 292                  * don't have any easy way to fix that.
 293                  */
 294                 ListCell   *lctlist,
 295                                    *lctyp,
 296                                    *lctypmod,
 297                                    *lccoll;
 298                 int                     varattno;
 299
 300                 lctyp = list_head(cte->ctecoltypes);
 301                 lctypmod = list_head(cte->ctecoltypmods);
 302                 lccoll = list_head(cte->ctecolcollations);
 303                 varattno = 0;
 304                 foreach(lctlist, GetCTETargetList(cte))
 305                 {
 306                         TargetEntry *te = (TargetEntry *) lfirst(lctlist);
 307                         Node       *texpr;
 308
 309                         if (te->resjunk)
 310                                 continue;
 311                         varattno++;
 312                         Assert(varattno == te->resno);
 313                         if (lctyp == NULL || lctypmod == NULL || lccoll == NULL)                /* shouldn't happen */
 314                                 elog(ERROR, "wrong number of output columns in WITH");
 315                         texpr = (Node *) te->expr;
 316                         if (exprType(texpr) != lfirst_oid(lctyp) ||
 317                                 exprTypmod(texpr) != lfirst_int(lctypmod))
 318                                 ereport(ERROR,
 319                                                 (errcode(ERRCODE_DATATYPE_MISMATCH),
 320                                                  errmsg("recursive query \"%s\" column %d has type %s in non-recursive term but type %s overall",
 321                                                                 cte->ctename, varattno,
 322                                                                 format_type_with_typemod(lfirst_oid(lctyp),
 323                                                                                                            lfirst_int(lctypmod)),
 324                                                                 format_type_with_typemod(exprType(texpr),
 325                                                                                                                  exprTypmod(texpr))),
 326                                                  errhint("Cast the output of the non-recursive term to the correct type."),
 327                                                  parser_errposition(pstate, exprLocation(texpr))));
 328                         if (exprCollation(texpr) != lfirst_oid(lccoll))
 329                                 ereport(ERROR,
 330                                                 (errcode(ERRCODE_COLLATION_MISMATCH),
 331                                                  errmsg("recursive query \"%s\" column %d has collation \"%s\" in non-recursive term but collation \"%s\" overall",
 332                                                                 cte->ctename, varattno,
 333                                                                 get_collation_name(lfirst_oid(lccoll)),
 334                                                                 get_collation_name(exprCollation(texpr))),
 335                                                  errhint("Use the COLLATE clause to set the collation of the non-recursive term."),
 336                                                  parser_errposition(pstate, exprLocation(texpr))));
 337                         lctyp = lnext(lctyp);
 338                         lctypmod = lnext(lctypmod);
 339                         lccoll = lnext(lccoll);
 340                 }
 341                 if (lctyp != NULL || lctypmod != NULL || lccoll != NULL)        /* shouldn't happen */
 342                         elog(ERROR, "wrong number of output columns in WITH");
 343         }
 344 }
 345
 346 /*
 347  * Compute derived fields of a CTE, given the transformed output targetlist
 348  *
 349  * For a nonrecursive CTE, this is called after transforming the CTE's query.
 350  * For a recursive CTE, we call it after transforming the non-recursive term,
 351  * and pass the targetlist emitted by the non-recursive term only.
 352  *
 353  * Note: in the recursive case, the passed pstate is actually the one being
 354  * used to analyze the CTE's query, so it is one level lower down than in
 355  * the nonrecursive case.  This doesn't matter since we only use it for
 356  * error message context anyway.
 357  */
 358 void
 359 analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist)
 360 {
 361         int                     numaliases;
 362         int                     varattno;
 363         ListCell   *tlistitem;
 364
 365         /* Not done already ... */
 366         Assert(cte->ctecolnames == NIL);
 367
 368         /*
 369          * We need to determine column names and types.  The alias column names
 370          * override anything coming from the query itself.      (Note: the SQL spec
 371          * says that the alias list must be empty or exactly as long as the output
 372          * column set; but we allow it to be shorter for consistency with Alias
 373          * handling.)
 374          */
 375         cte->ctecolnames = copyObject(cte->aliascolnames);
 376         cte->ctecoltypes = cte->ctecoltypmods = cte->ctecolcollations = NIL;
 377         numaliases = list_length(cte->aliascolnames);
 378         varattno = 0;
 379         foreach(tlistitem, tlist)
 380         {
 381                 TargetEntry *te = (TargetEntry *) lfirst(tlistitem);
 382                 Oid                     coltype;
 383                 int32           coltypmod;
 384                 Oid                     colcoll;
 385
 386                 if (te->resjunk)
 387                         continue;
 388                 varattno++;
 389                 Assert(varattno == te->resno);
 390                 if (varattno > numaliases)
 391                 {
 392                         char       *attrname;
 393
 394                         attrname = pstrdup(te->resname);
 395                         cte->ctecolnames = lappend(cte->ctecolnames, makeString(attrname));
 396                 }
 397                 coltype = exprType((Node *) te->expr);
 398                 coltypmod = exprTypmod((Node *) te->expr);
 399                 colcoll = exprCollation((Node *) te->expr);
 400
 401                 /*
 402                  * If the CTE is recursive, force the exposed column type of any
 403                  * "unknown" column to "text".  This corresponds to the fact that
 404                  * SELECT 'foo' UNION SELECT 'bar' will ultimately produce text. We
 405                  * might see "unknown" as a result of an untyped literal in the
 406                  * non-recursive term's select list, and if we don't convert to text
 407                  * then we'll have a mismatch against the UNION result.
 408                  */
 409                 if (cte->cterecursive && coltype == UNKNOWNOID)
 410                 {
 411                         coltype = TEXTOID;
 412                         coltypmod = -1;         /* should be -1 already, but be sure */
 413                         colcoll = DEFAULT_COLLATION_OID;
 414                 }
 415                 cte->ctecoltypes = lappend_oid(cte->ctecoltypes, coltype);
 416                 cte->ctecoltypmods = lappend_int(cte->ctecoltypmods, coltypmod);
 417                 cte->ctecolcollations = lappend_oid(cte->ctecolcollations, colcoll);
 418         }
 419         if (varattno < numaliases)
 420                 ereport(ERROR,
 421                                 (errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
 422                                  errmsg("WITH query \"%s\" has %d columns available but %d columns specified",
 423                                                 cte->ctename, varattno, numaliases),
 424                                  parser_errposition(pstate, cte->location)));
 425 }
 426
 427
 428 /*
 429  * Identify the cross-references of a list of WITH RECURSIVE items,
 430  * and sort into an order that has no forward references.
 431  */
 432 static void
 433 makeDependencyGraph(CteState *cstate)
 434 {
 435         int                     i;
 436
 437         for (i = 0; i < cstate->numitems; i++)
 438         {
 439                 CommonTableExpr *cte = cstate->items[i].cte;
 440
 441                 cstate->curitem = i;
 442                 cstate->innerwiths = NIL;
 443                 makeDependencyGraphWalker((Node *) cte->ctequery, cstate);
 444                 Assert(cstate->innerwiths == NIL);
 445         }
 446
 447         TopologicalSort(cstate->pstate, cstate->items, cstate->numitems);
 448 }
 449
 450 /*
 451  * Tree walker function to detect cross-references and self-references of the
 452  * CTEs in a WITH RECURSIVE list.
 453  */
 454 static bool
 455 makeDependencyGraphWalker(Node *node, CteState *cstate)
 456 {
 457         if (node == NULL)
 458                 return false;
 459         if (IsA(node, RangeVar))
 460         {
 461                 RangeVar   *rv = (RangeVar *) node;
 462
 463                 /* If unqualified name, might be a CTE reference */
 464                 if (!rv->schemaname)
 465                 {
 466                         ListCell   *lc;
 467                         int                     i;
 468
 469                         /* ... but first see if it's captured by an inner WITH */
 470                         foreach(lc, cstate->innerwiths)
 471                         {
 472                                 List       *withlist = (List *) lfirst(lc);
 473                                 ListCell   *lc2;
 474
 475                                 foreach(lc2, withlist)
 476                                 {
 477                                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2);
 478
 479                                         if (strcmp(rv->relname, cte->ctename) == 0)
 480                                                 return false;   /* yes, so bail out */
 481                                 }
 482                         }
 483
 484                         /* No, could be a reference to the query level we are working on */
 485                         for (i = 0; i < cstate->numitems; i++)
 486                         {
 487                                 CommonTableExpr *cte = cstate->items[i].cte;
 488
 489                                 if (strcmp(rv->relname, cte->ctename) == 0)
 490                                 {
 491                                         int                     myindex = cstate->curitem;
 492
 493                                         if (i != myindex)
 494                                         {
 495                                                 /* Add cross-item dependency */
 496                                                 cstate->items[myindex].depends_on =
 497                                                         bms_add_member(cstate->items[myindex].depends_on,
 498                                                                                    cstate->items[i].id);
 499                                         }
 500                                         else
 501                                         {
 502                                                 /* Found out this one is self-referential */
 503                                                 cte->cterecursive = true;
 504                                         }
 505                                         break;
 506                                 }
 507                         }
 508                 }
 509                 return false;
 510         }
 511         if (IsA(node, SelectStmt))
 512         {
 513                 SelectStmt *stmt = (SelectStmt *) node;
 514                 ListCell   *lc;
 515
 516                 if (stmt->withClause)
 517                 {
 518                         if (stmt->withClause->recursive)
 519                         {
 520                                 /*
 521                                  * In the RECURSIVE case, all query names of the WITH are
 522                                  * visible to all WITH items as well as the main query. So
 523                                  * push them all on, process, pop them all off.
 524                                  */
 525                                 cstate->innerwiths = lcons(stmt->withClause->ctes,
 526                                                                                    cstate->innerwiths);
 527                                 foreach(lc, stmt->withClause->ctes)
 528                                 {
 529                                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 530
 531                                         (void) makeDependencyGraphWalker(cte->ctequery, cstate);
 532                                 }
 533                                 (void) raw_expression_tree_walker(node,
 534                                                                                                   makeDependencyGraphWalker,
 535                                                                                                   (void *) cstate);
 536                                 cstate->innerwiths = list_delete_first(cstate->innerwiths);
 537                         }
 538                         else
 539                         {
 540                                 /*
 541                                  * In the non-RECURSIVE case, query names are visible to the
 542                                  * WITH items after them and to the main query.
 543                                  */
 544                                 ListCell   *cell1;
 545
 546                                 cstate->innerwiths = lcons(NIL, cstate->innerwiths);
 547                                 cell1 = list_head(cstate->innerwiths);
 548                                 foreach(lc, stmt->withClause->ctes)
 549                                 {
 550                                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 551
 552                                         (void) makeDependencyGraphWalker(cte->ctequery, cstate);
 553                                         lfirst(cell1) = lappend((List *) lfirst(cell1), cte);
 554                                 }
 555                                 (void) raw_expression_tree_walker(node,
 556                                                                                                   makeDependencyGraphWalker,
 557                                                                                                   (void *) cstate);
 558                                 cstate->innerwiths = list_delete_first(cstate->innerwiths);
 559                         }
 560                         /* We're done examining the SelectStmt */
 561                         return false;
 562                 }
 563                 /* if no WITH clause, just fall through for normal processing */
 564         }
 565         if (IsA(node, WithClause))
 566         {
 567                 /*
 568                  * Prevent raw_expression_tree_walker from recursing directly into a
 569                  * WITH clause.  We need that to happen only under the control of the
 570                  * code above.
 571                  */
 572                 return false;
 573         }
 574         return raw_expression_tree_walker(node,
 575                                                                           makeDependencyGraphWalker,
 576                                                                           (void *) cstate);
 577 }
 578
 579 /*
 580  * Sort by dependencies, using a standard topological sort operation
 581  */
 582 static void
 583 TopologicalSort(ParseState *pstate, CteItem *items, int numitems)
 584 {
 585         int                     i,
 586                                 j;
 587
 588         /* for each position in sequence ... */
 589         for (i = 0; i < numitems; i++)
 590         {
 591                 /* ... scan the remaining items to find one that has no dependencies */
 592                 for (j = i; j < numitems; j++)
 593                 {
 594                         if (bms_is_empty(items[j].depends_on))
 595                                 break;
 596                 }
 597
 598                 /* if we didn't find one, the dependency graph has a cycle */
 599                 if (j >= numitems)
 600                         ereport(ERROR,
 601                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 602                         errmsg("mutual recursion between WITH items is not implemented"),
 603                                          parser_errposition(pstate, items[i].cte->location)));
 604
 605                 /*
 606                  * Found one.  Move it to front and remove it from every other item's
 607                  * dependencies.
 608                  */
 609                 if (i != j)
 610                 {
 611                         CteItem         tmp;
 612
 613                         tmp = items[i];
 614                         items[i] = items[j];
 615                         items[j] = tmp;
 616                 }
 617
 618                 /*
 619                  * Items up through i are known to have no dependencies left, so we
 620                  * can skip them in this loop.
 621                  */
 622                 for (j = i + 1; j < numitems; j++)
 623                 {
 624                         items[j].depends_on = bms_del_member(items[j].depends_on,
 625                                                                                                  items[i].id);
 626                 }
 627         }
 628 }
 629
 630
 631 /*
 632  * Check that recursive queries are well-formed.
 633  */
 634 static void
 635 checkWellFormedRecursion(CteState *cstate)
 636 {
 637         int                     i;
 638
 639         for (i = 0; i < cstate->numitems; i++)
 640         {
 641                 CommonTableExpr *cte = cstate->items[i].cte;
 642                 SelectStmt *stmt = (SelectStmt *) cte->ctequery;
 643
 644                 Assert(!IsA(stmt, Query));      /* not analyzed yet */
 645
 646                 /* Ignore items that weren't found to be recursive */
 647                 if (!cte->cterecursive)
 648                         continue;
 649
 650                 /* Must be a SELECT statement */
 651                 if (!IsA(stmt, SelectStmt))
 652                         ereport(ERROR,
 653                                         (errcode(ERRCODE_INVALID_RECURSION),
 654                                          errmsg("recursive query \"%s\" must not contain data-modifying statements",
 655                                                         cte->ctename),
 656                                          parser_errposition(cstate->pstate, cte->location)));
 657
 658                 /* Must have top-level UNION */
 659                 if (stmt->op != SETOP_UNION)
 660                         ereport(ERROR,
 661                                         (errcode(ERRCODE_INVALID_RECURSION),
 662                                          errmsg("recursive query \"%s\" does not have the form non-recursive-term UNION [ALL] recursive-term",
 663                                                         cte->ctename),
 664                                          parser_errposition(cstate->pstate, cte->location)));
 665
 666                 /* The left-hand operand mustn't contain self-reference at all */
 667                 cstate->curitem = i;
 668                 cstate->innerwiths = NIL;
 669                 cstate->selfrefcount = 0;
 670                 cstate->context = RECURSION_NONRECURSIVETERM;
 671                 checkWellFormedRecursionWalker((Node *) stmt->larg, cstate);
 672                 Assert(cstate->innerwiths == NIL);
 673
 674                 /* Right-hand operand should contain one reference in a valid place */
 675                 cstate->curitem = i;
 676                 cstate->innerwiths = NIL;
 677                 cstate->selfrefcount = 0;
 678                 cstate->context = RECURSION_OK;
 679                 checkWellFormedRecursionWalker((Node *) stmt->rarg, cstate);
 680                 Assert(cstate->innerwiths == NIL);
 681                 if (cstate->selfrefcount != 1)  /* shouldn't happen */
 682                         elog(ERROR, "missing recursive reference");
 683
 684                 /*
 685                  * Disallow ORDER BY and similar decoration atop the UNION. These
 686                  * don't make sense because it's impossible to figure out what they
 687                  * mean when we have only part of the recursive query's results. (If
 688                  * we did allow them, we'd have to check for recursive references
 689                  * inside these subtrees.)
 690                  */
 691                 if (stmt->sortClause)
 692                         ereport(ERROR,
 693                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 694                                   errmsg("ORDER BY in a recursive query is not implemented"),
 695                                          parser_errposition(cstate->pstate,
 696                                                                   exprLocation((Node *) stmt->sortClause))));
 697                 if (stmt->limitOffset)
 698                         ereport(ERROR,
 699                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 700                                          errmsg("OFFSET in a recursive query is not implemented"),
 701                                          parser_errposition(cstate->pstate,
 702                                                                                 exprLocation(stmt->limitOffset))));
 703                 if (stmt->limitCount)
 704                         ereport(ERROR,
 705                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 706                                          errmsg("LIMIT in a recursive query is not implemented"),
 707                                          parser_errposition(cstate->pstate,
 708                                                                                 exprLocation(stmt->limitCount))));
 709                 if (stmt->lockingClause)
 710                         ereport(ERROR,
 711                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 712                                          errmsg("FOR UPDATE/SHARE in a recursive query is not implemented"),
 713                                          parser_errposition(cstate->pstate,
 714                                                            exprLocation((Node *) stmt->lockingClause))));
 715         }
 716 }
 717
 718 /*
 719  * Tree walker function to detect invalid self-references in a recursive query.
 720  */
 721 static bool
 722 checkWellFormedRecursionWalker(Node *node, CteState *cstate)
 723 {
 724         RecursionContext save_context = cstate->context;
 725
 726         if (node == NULL)
 727                 return false;
 728         if (IsA(node, RangeVar))
 729         {
 730                 RangeVar   *rv = (RangeVar *) node;
 731
 732                 /* If unqualified name, might be a CTE reference */
 733                 if (!rv->schemaname)
 734                 {
 735                         ListCell   *lc;
 736                         CommonTableExpr *mycte;
 737
 738                         /* ... but first see if it's captured by an inner WITH */
 739                         foreach(lc, cstate->innerwiths)
 740                         {
 741                                 List       *withlist = (List *) lfirst(lc);
 742                                 ListCell   *lc2;
 743
 744                                 foreach(lc2, withlist)
 745                                 {
 746                                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2);
 747
 748                                         if (strcmp(rv->relname, cte->ctename) == 0)
 749                                                 return false;   /* yes, so bail out */
 750                                 }
 751                         }
 752
 753                         /* No, could be a reference to the query level we are working on */
 754                         mycte = cstate->items[cstate->curitem].cte;
 755                         if (strcmp(rv->relname, mycte->ctename) == 0)
 756                         {
 757                                 /* Found a recursive reference to the active query */
 758                                 if (cstate->context != RECURSION_OK)
 759                                         ereport(ERROR,
 760                                                         (errcode(ERRCODE_INVALID_RECURSION),
 761                                                          errmsg(recursion_errormsgs[cstate->context],
 762                                                                         mycte->ctename),
 763                                                          parser_errposition(cstate->pstate,
 764                                                                                                 rv->location)));
 765                                 /* Count references */
 766                                 if (++(cstate->selfrefcount) > 1)
 767                                         ereport(ERROR,
 768                                                         (errcode(ERRCODE_INVALID_RECURSION),
 769                                                          errmsg("recursive reference to query \"%s\" must not appear more than once",
 770                                                                         mycte->ctename),
 771                                                          parser_errposition(cstate->pstate,
 772                                                                                                 rv->location)));
 773                         }
 774                 }
 775                 return false;
 776         }
 777         if (IsA(node, SelectStmt))
 778         {
 779                 SelectStmt *stmt = (SelectStmt *) node;
 780                 ListCell   *lc;
 781
 782                 if (stmt->withClause)
 783                 {
 784                         if (stmt->withClause->recursive)
 785                         {
 786                                 /*
 787                                  * In the RECURSIVE case, all query names of the WITH are
 788                                  * visible to all WITH items as well as the main query. So
 789                                  * push them all on, process, pop them all off.
 790                                  */
 791                                 cstate->innerwiths = lcons(stmt->withClause->ctes,
 792                                                                                    cstate->innerwiths);
 793                                 foreach(lc, stmt->withClause->ctes)
 794                                 {
 795                                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 796
 797                                         (void) checkWellFormedRecursionWalker(cte->ctequery, cstate);
 798                                 }
 799                                 checkWellFormedSelectStmt(stmt, cstate);
 800                                 cstate->innerwiths = list_delete_first(cstate->innerwiths);
 801                         }
 802                         else
 803                         {
 804                                 /*
 805                                  * In the non-RECURSIVE case, query names are visible to the
 806                                  * WITH items after them and to the main query.
 807                                  */
 808                                 ListCell   *cell1;
 809
 810                                 cstate->innerwiths = lcons(NIL, cstate->innerwiths);
 811                                 cell1 = list_head(cstate->innerwiths);
 812                                 foreach(lc, stmt->withClause->ctes)
 813                                 {
 814                                         CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
 815
 816                                         (void) checkWellFormedRecursionWalker(cte->ctequery, cstate);
 817                                         lfirst(cell1) = lappend((List *) lfirst(cell1), cte);
 818                                 }
 819                                 checkWellFormedSelectStmt(stmt, cstate);
 820                                 cstate->innerwiths = list_delete_first(cstate->innerwiths);
 821                         }
 822                 }
 823                 else
 824                         checkWellFormedSelectStmt(stmt, cstate);
 825                 /* We're done examining the SelectStmt */
 826                 return false;
 827         }
 828         if (IsA(node, WithClause))
 829         {
 830                 /*
 831                  * Prevent raw_expression_tree_walker from recursing directly into a
 832                  * WITH clause.  We need that to happen only under the control of the
 833                  * code above.
 834                  */
 835                 return false;
 836         }
 837         if (IsA(node, JoinExpr))
 838         {
 839                 JoinExpr   *j = (JoinExpr *) node;
 840
 841                 switch (j->jointype)
 842                 {
 843                         case JOIN_INNER:
 844                                 checkWellFormedRecursionWalker(j->larg, cstate);
 845                                 checkWellFormedRecursionWalker(j->rarg, cstate);
 846                                 checkWellFormedRecursionWalker(j->quals, cstate);
 847                                 break;
 848                         case JOIN_LEFT:
 849                                 checkWellFormedRecursionWalker(j->larg, cstate);
 850                                 if (save_context == RECURSION_OK)
 851                                         cstate->context = RECURSION_OUTERJOIN;
 852                                 checkWellFormedRecursionWalker(j->rarg, cstate);
 853                                 cstate->context = save_context;
 854                                 checkWellFormedRecursionWalker(j->quals, cstate);
 855                                 break;
 856                         case JOIN_FULL:
 857                                 if (save_context == RECURSION_OK)
 858                                         cstate->context = RECURSION_OUTERJOIN;
 859                                 checkWellFormedRecursionWalker(j->larg, cstate);
 860                                 checkWellFormedRecursionWalker(j->rarg, cstate);
 861                                 cstate->context = save_context;
 862                                 checkWellFormedRecursionWalker(j->quals, cstate);
 863                                 break;
 864                         case JOIN_RIGHT:
 865                                 if (save_context == RECURSION_OK)
 866                                         cstate->context = RECURSION_OUTERJOIN;
 867                                 checkWellFormedRecursionWalker(j->larg, cstate);
 868                                 cstate->context = save_context;
 869                                 checkWellFormedRecursionWalker(j->rarg, cstate);
 870                                 checkWellFormedRecursionWalker(j->quals, cstate);
 871                                 break;
 872                         default:
 873                                 elog(ERROR, "unrecognized join type: %d",
 874                                          (int) j->jointype);
 875                 }
 876                 return false;
 877         }
 878         if (IsA(node, SubLink))
 879         {
 880                 SubLink    *sl = (SubLink *) node;
 881
 882                 /*
 883                  * we intentionally override outer context, since subquery is
 884                  * independent
 885                  */
 886                 cstate->context = RECURSION_SUBLINK;
 887                 checkWellFormedRecursionWalker(sl->subselect, cstate);
 888                 cstate->context = save_context;
 889                 checkWellFormedRecursionWalker(sl->testexpr, cstate);
 890                 return false;
 891         }
 892         return raw_expression_tree_walker(node,
 893                                                                           checkWellFormedRecursionWalker,
 894                                                                           (void *) cstate);
 895 }
 896
 897 /*
 898  * subroutine for checkWellFormedRecursionWalker: process a SelectStmt
 899  * without worrying about its WITH clause
 900  */
 901 static void
 902 checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate)
 903 {
 904         RecursionContext save_context = cstate->context;
 905
 906         if (save_context != RECURSION_OK)
 907         {
 908                 /* just recurse without changing state */
 909                 raw_expression_tree_walker((Node *) stmt,
 910                                                                    checkWellFormedRecursionWalker,
 911                                                                    (void *) cstate);
 912         }
 913         else
 914         {
 915                 switch (stmt->op)
 916                 {
 917                         case SETOP_NONE:
 918                         case SETOP_UNION:
 919                                 raw_expression_tree_walker((Node *) stmt,
 920                                                                                    checkWellFormedRecursionWalker,
 921                                                                                    (void *) cstate);
 922                                 break;
 923                         case SETOP_INTERSECT:
 924                                 if (stmt->all)
 925                                         cstate->context = RECURSION_INTERSECT;
 926                                 checkWellFormedRecursionWalker((Node *) stmt->larg,
 927                                                                                            cstate);
 928                                 checkWellFormedRecursionWalker((Node *) stmt->rarg,
 929                                                                                            cstate);
 930                                 cstate->context = save_context;
 931                                 checkWellFormedRecursionWalker((Node *) stmt->sortClause,
 932                                                                                            cstate);
 933                                 checkWellFormedRecursionWalker((Node *) stmt->limitOffset,
 934                                                                                            cstate);
 935                                 checkWellFormedRecursionWalker((Node *) stmt->limitCount,
 936                                                                                            cstate);
 937                                 checkWellFormedRecursionWalker((Node *) stmt->lockingClause,
 938                                                                                            cstate);
 939                                 break;
 940                                 break;
 941                         case SETOP_EXCEPT:
 942                                 if (stmt->all)
 943                                         cstate->context = RECURSION_EXCEPT;
 944                                 checkWellFormedRecursionWalker((Node *) stmt->larg,
 945                                                                                            cstate);
 946                                 cstate->context = RECURSION_EXCEPT;
 947                                 checkWellFormedRecursionWalker((Node *) stmt->rarg,
 948                                                                                            cstate);
 949                                 cstate->context = save_context;
 950                                 checkWellFormedRecursionWalker((Node *) stmt->sortClause,
 951                                                                                            cstate);
 952                                 checkWellFormedRecursionWalker((Node *) stmt->limitOffset,
 953                                                                                            cstate);
 954                                 checkWellFormedRecursionWalker((Node *) stmt->limitCount,
 955                                                                                            cstate);
 956                                 checkWellFormedRecursionWalker((Node *) stmt->lockingClause,
 957                                                                                            cstate);
 958                                 break;
 959                         default:
 960                                 elog(ERROR, "unrecognized set op: %d",
 961                                          (int) stmt->op);
 962                 }
 963         }
 964 }