Implement SQL-standard WITH clauses, including WITH RECURSIVE.

There are some unimplemented aspects: recursive queries must use UNION ALL
(should allow UNION too), and we don't have SEARCH or CYCLE clauses.
These might or might not get done for 8.4, but even without them it's a
pretty useful feature.

There are also a couple of small loose ends and definitional quibbles,
which I'll send a memo about to pgsql-hackers shortly.  But let's land
the patch now so we can get on with other development.

Yoshiyuki Asaba, with lots of help from Tatsuo Ishii and Tom Lane

10 files changed, 1406 insertions, 58 deletions

diff --git a/src/backend/parser/Makefile b/src/backend/parser/Makefile
index 04b9ed61f44..8cefea14ac0 100644
--- a/src/backend/parser/Makefile
+++ b/src/backend/parser/Makefile
@@ -2,7 +2,7 @@
 #
 # Makefile for parser
 #
-# $PostgreSQL: pgsql/src/backend/parser/Makefile,v 1.47 2008/08/29 13:02:32 petere Exp $
+# $PostgreSQL: pgsql/src/backend/parser/Makefile,v 1.48 2008/10/04 21:56:54 tgl Exp $
 #
 #-------------------------------------------------------------------------
 
@@ -12,7 +12,7 @@ include $(top_builddir)/src/Makefile.global
 
 override CPPFLAGS := -I$(srcdir) $(CPPFLAGS)
 
-OBJS= analyze.o gram.o keywords.o parser.o parse_agg.o parse_clause.o \
+OBJS= analyze.o gram.o keywords.o parser.o parse_agg.o parse_cte.o parse_clause.o \
       parse_expr.o parse_func.o parse_node.o parse_oper.o parse_relation.o \
       parse_type.o parse_coerce.o parse_target.o parse_utilcmd.o scansup.o
 
diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c
index 18585b860b4..8934c04bb24 100644
--- a/src/backend/parser/analyze.c
+++ b/src/backend/parser/analyze.c
@@ -17,7 +17,7 @@
  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- *	$PostgreSQL: pgsql/src/backend/parser/analyze.c,v 1.379 2008/09/01 20:42:44 tgl Exp $
+ *	$PostgreSQL: pgsql/src/backend/parser/analyze.c,v 1.380 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -32,6 +32,7 @@
 #include "parser/parse_agg.h"
 #include "parser/parse_clause.h"
 #include "parser/parse_coerce.h"
+#include "parser/parse_cte.h"
 #include "parser/parse_oper.h"
 #include "parser/parse_relation.h"
 #include "parser/parse_target.h"
@@ -309,6 +310,8 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt)
 		pstate->p_relnamespace = NIL;
 		sub_varnamespace = pstate->p_varnamespace;
 		pstate->p_varnamespace = NIL;
+		/* There can't be any outer WITH to worry about */
+		Assert(pstate->p_ctenamespace == NIL);
 	}
 	else
 	{
@@ -447,6 +450,13 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt)
 		List	   *exprsLists = NIL;
 		int			sublist_length = -1;
 
+		/* process the WITH clause */
+		if (selectStmt->withClause)
+		{
+			qry->hasRecursive = selectStmt->withClause->recursive;
+			qry->cteList = transformWithClause(pstate, selectStmt->withClause);
+		}
+
 		foreach(lc, selectStmt->valuesLists)
 		{
 			List	   *sublist = (List *) lfirst(lc);
@@ -540,6 +550,13 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt)
 
 		Assert(list_length(valuesLists) == 1);
 
+		/* process the WITH clause */
+		if (selectStmt->withClause)
+		{
+			qry->hasRecursive = selectStmt->withClause->recursive;
+			qry->cteList = transformWithClause(pstate, selectStmt->withClause);
+		}
+
 		/* Do basic expression transformation (same as a ROW() expr) */
 		exprList = transformExpressionList(pstate,
 										   (List *) linitial(valuesLists));
@@ -694,6 +711,13 @@ transformSelectStmt(ParseState *pstate, SelectStmt *stmt)
 	/* make FOR UPDATE/FOR SHARE info available to addRangeTableEntry */
 	pstate->p_locking_clause = stmt->lockingClause;
 
+	/* process the WITH clause */
+	if (stmt->withClause)
+	{
+		qry->hasRecursive = stmt->withClause->recursive;
+		qry->cteList = transformWithClause(pstate, stmt->withClause);
+	}
+
 	/* process the FROM clause */
 	transformFromClause(pstate, stmt->fromClause);
 
@@ -814,6 +838,13 @@ transformValuesClause(ParseState *pstate, SelectStmt *stmt)
 	Assert(stmt->havingClause == NULL);
 	Assert(stmt->op == SETOP_NONE);
 
+	/* process the WITH clause */
+	if (stmt->withClause)
+	{
+		qry->hasRecursive = stmt->withClause->recursive;
+		qry->cteList = transformWithClause(pstate, stmt->withClause);
+	}
+
 	/*
 	 * For each row of VALUES, transform the raw expressions and gather type
 	 * information.  This is also a handy place to reject DEFAULT nodes, which
@@ -1059,6 +1090,13 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt)
 				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 				 errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT")));
 
+	/* process the WITH clause */
+	if (stmt->withClause)
+	{
+		qry->hasRecursive = stmt->withClause->recursive;
+		qry->cteList = transformWithClause(pstate, stmt->withClause);
+	}
+
 	/*
 	 * Recursively transform the components of the tree.
 	 */
@@ -1101,21 +1139,22 @@ transformSetOperationStmt(ParseState *pstate, SelectStmt *stmt)
 		TargetEntry *lefttle = (TargetEntry *) lfirst(left_tlist);
 		char	   *colName;
 		TargetEntry *tle;
-		Expr	   *expr;
+		Var		   *var;
 
 		Assert(!lefttle->resjunk);
 		colName = pstrdup(lefttle->resname);
-		expr = (Expr *) makeVar(leftmostRTI,
-								lefttle->resno,
-								colType,
-								colTypmod,
-								0);
-		tle = makeTargetEntry(expr,
+		var = makeVar(leftmostRTI,
+					  lefttle->resno,
+					  colType,
+					  colTypmod,
+					  0);
+		var->location = exprLocation((Node *) lefttle->expr);
+		tle = makeTargetEntry((Expr *) var,
 							  (AttrNumber) pstate->p_next_resno++,
 							  colName,
 							  false);
 		qry->targetList = lappend(qry->targetList, tle);
-		targetvars = lappend(targetvars, expr);
+		targetvars = lappend(targetvars, var);
 		targetnames = lappend(targetnames, makeString(colName));
 		left_tlist = lnext(left_tlist);
 	}
@@ -1841,6 +1880,30 @@ transformLockingClause(ParseState *pstate, Query *qry, LockingClause *lc)
 					 */
 					transformLockingClause(pstate, rte->subquery, allrels);
 					break;
+				case RTE_CTE:
+					{
+						/*
+						 * We allow FOR UPDATE/SHARE of a WITH query to be
+						 * propagated into the WITH, but it doesn't seem
+						 * very sane to allow this for a reference to an
+						 * outer-level WITH.  And it definitely wouldn't
+						 * work for a self-reference, since we're not done
+						 * analyzing the CTE anyway.
+						 */
+						CommonTableExpr *cte;
+
+						if (rte->ctelevelsup > 0 || rte->self_reference)
+							ereport(ERROR,
+									(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+									 errmsg("SELECT FOR UPDATE/SHARE cannot be applied to an outer-level WITH query")));
+						cte = GetCTEForRTE(pstate, rte);
+						/* should be analyzed by now */
+						Assert(IsA(cte->ctequery, Query));
+						transformLockingClause(pstate,
+											   (Query *) cte->ctequery,
+											   allrels);
+					}
+					break;
 				default:
 					/* ignore JOIN, SPECIAL, FUNCTION RTEs */
 					break;
@@ -1908,6 +1971,32 @@ transformLockingClause(ParseState *pstate, Query *qry, LockingClause *lc)
 									 errmsg("SELECT FOR UPDATE/SHARE cannot be applied to VALUES"),
 									 parser_errposition(pstate, thisrel->location)));
 							break;
+						case RTE_CTE:
+							{
+								/*
+								 * We allow FOR UPDATE/SHARE of a WITH query
+								 * to be propagated into the WITH, but it
+								 * doesn't seem very sane to allow this for a
+								 * reference to an outer-level WITH.  And it
+								 * definitely wouldn't work for a
+								 * self-reference, since we're not done
+								 * analyzing the CTE anyway.
+								 */
+								CommonTableExpr *cte;
+
+								if (rte->ctelevelsup > 0 || rte->self_reference)
+									ereport(ERROR,
+											(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+											 errmsg("SELECT FOR UPDATE/SHARE cannot be applied to an outer-level WITH query"),
+											 parser_errposition(pstate, thisrel->location)));
+								cte = GetCTEForRTE(pstate, rte);
+								/* should be analyzed by now */
+								Assert(IsA(cte->ctequery, Query));
+								transformLockingClause(pstate,
+													   (Query *) cte->ctequery,
+													   allrels);
+							}
+							break;
 						default:
 							elog(ERROR, "unrecognized RTE type: %d",
 								 (int) rte->rtekind);
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index d487e59fd72..5ee06996241 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -11,7 +11,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/gram.y,v 2.624 2008/09/23 09:20:35 heikki Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/gram.y,v 2.625 2008/10/04 21:56:54 tgl Exp $
  *
  * HISTORY
  *	  AUTHOR			DATE			MAJOR EVENT
@@ -119,7 +119,8 @@ static List *extractArgTypes(List *parameters);
 static SelectStmt *findLeftmostSelect(SelectStmt *node);
 static void insertSelectOptions(SelectStmt *stmt,
 								List *sortClause, List *lockingClause,
-								Node *limitOffset, Node *limitCount);
+								Node *limitOffset, Node *limitCount,
+								WithClause *withClause);
 static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg);
 static Node *doNegate(Node *n, int location);
 static void doNegateFloat(Value *v);
@@ -160,6 +161,7 @@ static TypeName *TableFuncTypeName(List *columns);
 	Alias				*alias;
 	RangeVar			*range;
 	IntoClause			*into;
+	WithClause			*with;
 	A_Indices			*aind;
 	ResTarget			*target;
 	PrivTarget			*privtarget;
@@ -377,6 +379,10 @@ static TypeName *TableFuncTypeName(List *columns);
 %type <ival>	document_or_content
 %type <boolean> xml_whitespace_option
 
+%type <node> 	common_table_expr
+%type <with> 	with_clause
+%type <list>	cte_list
+
 
 /*
  * If you make any token changes, update the keyword table in
@@ -443,9 +449,9 @@ static TypeName *TableFuncTypeName(List *columns);
 
 	QUOTE
 
-	READ REAL REASSIGN RECHECK REFERENCES REINDEX RELATIVE_P RELEASE RENAME
-	REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS REVOKE
-	RIGHT ROLE ROLLBACK ROW ROWS RULE
+	READ REAL REASSIGN RECHECK RECURSIVE REFERENCES REINDEX RELATIVE_P RELEASE
+	RENAME REPEATABLE REPLACE REPLICA RESET RESTART RESTRICT RETURNING RETURNS
+	REVOKE RIGHT ROLE ROLLBACK ROW ROWS RULE
 
 	SAVEPOINT SCHEMA SCROLL SEARCH SECOND_P SECURITY SELECT SEQUENCE
 	SERIALIZABLE SESSION SESSION_USER SET SETOF SHARE
@@ -6276,6 +6282,10 @@ select_with_parens:
 		;
 
 /*
+ * This rule parses the equivalent of the standard's <query expression>.
+ * The duplicative productions are annoying, but hard to get rid of without
+ * creating shift/reduce conflicts.
+ *
  *	FOR UPDATE/SHARE may be before or after LIMIT/OFFSET.
  *	In <=7.2.X, LIMIT/OFFSET had to be after FOR UPDATE
  *	We now support both orderings, but prefer LIMIT/OFFSET before FOR UPDATE/SHARE
@@ -6286,21 +6296,51 @@ select_no_parens:
 			| select_clause sort_clause
 				{
 					insertSelectOptions((SelectStmt *) $1, $2, NIL,
-										NULL, NULL);
+										NULL, NULL, NULL);
 					$$ = $1;
 				}
 			| select_clause opt_sort_clause for_locking_clause opt_select_limit
 				{
 					insertSelectOptions((SelectStmt *) $1, $2, $3,
-										list_nth($4, 0), list_nth($4, 1));
+										list_nth($4, 0), list_nth($4, 1),
+										NULL);
 					$$ = $1;
 				}
 			| select_clause opt_sort_clause select_limit opt_for_locking_clause
 				{
 					insertSelectOptions((SelectStmt *) $1, $2, $4,
-										list_nth($3, 0), list_nth($3, 1));
+										list_nth($3, 0), list_nth($3, 1),
+										NULL);
 					$$ = $1;
 				}
+			| with_clause simple_select
+				{
+					insertSelectOptions((SelectStmt *) $2, NULL, NIL,
+										NULL, NULL,
+										$1);
+					$$ = $2;
+				}
+			| with_clause select_clause sort_clause
+				{
+					insertSelectOptions((SelectStmt *) $2, $3, NIL,
+										NULL, NULL,
+										$1);
+					$$ = $2;
+				}
+			| with_clause select_clause opt_sort_clause for_locking_clause opt_select_limit
+				{
+					insertSelectOptions((SelectStmt *) $2, $3, $4,
+										list_nth($5, 0), list_nth($5, 1),
+										$1);
+					$$ = $2;
+				}
+			| with_clause select_clause opt_sort_clause select_limit opt_for_locking_clause
+				{
+					insertSelectOptions((SelectStmt *) $2, $3, $5,
+										list_nth($4, 0), list_nth($4, 1),
+										$1);
+					$$ = $2;
+				}
 		;
 
 select_clause:
@@ -6323,10 +6363,10 @@ select_clause:
  *		(SELECT foo UNION SELECT bar) ORDER BY baz
  * not
  *		SELECT foo UNION (SELECT bar ORDER BY baz)
- * Likewise FOR UPDATE and LIMIT.  Therefore, those clauses are described
- * as part of the select_no_parens production, not simple_select.
- * This does not limit functionality, because you can reintroduce sort and
- * limit clauses inside parentheses.
+ * Likewise for WITH, FOR UPDATE and LIMIT.  Therefore, those clauses are
+ * described as part of the select_no_parens production, not simple_select.
+ * This does not limit functionality, because you can reintroduce these
+ * clauses inside parentheses.
  *
  * NOTE: only the leftmost component SelectStmt should have INTO.
  * However, this is not checked by the grammar; parse analysis must check it.
@@ -6361,6 +6401,47 @@ simple_select:
 				}
 		;
 
+/*
+ * SQL standard WITH clause looks like:
+ *
+ * WITH [ RECURSIVE ] <query name> [ (<column>,...) ]
+ *		AS (query) [ SEARCH or CYCLE clause ]
+ *
+ * We don't currently support the SEARCH or CYCLE clause.
+ */
+with_clause:
+		WITH cte_list
+			{
+				$$ = makeNode(WithClause);
+				$$->ctes = $2;
+				$$->recursive = false;
+				$$->location = @1;
+			}
+		| WITH RECURSIVE cte_list
+			{
+				$$ = makeNode(WithClause);
+				$$->ctes = $3;
+				$$->recursive = true;
+				$$->location = @1;
+			}
+		;
+
+cte_list:
+		common_table_expr						{ $$ = list_make1($1); }
+		| cte_list ',' common_table_expr		{ $$ = lappend($1, $3); }
+		;
+
+common_table_expr:  name opt_name_list AS select_with_parens
+			{
+				CommonTableExpr *n = makeNode(CommonTableExpr);
+				n->ctename = $1;
+				n->aliascolnames = $2;
+				n->ctequery = $4;
+				n->location = @1;
+				$$ = (Node *) n;
+			}
+		;
+
 into_clause:
 			INTO OptTempTableName
 				{
@@ -9349,6 +9430,7 @@ unreserved_keyword:
 			| READ
 			| REASSIGN
 			| RECHECK
+			| RECURSIVE
 			| REINDEX
 			| RELATIVE_P
 			| RELEASE
@@ -9416,7 +9498,6 @@ unreserved_keyword:
 			| VIEW
 			| VOLATILE
 			| WHITESPACE_P
-			| WITH
 			| WITHOUT
 			| WORK
 			| WRITE
@@ -9599,6 +9680,7 @@ reserved_keyword:
 			| VARIADIC
 			| WHEN
 			| WHERE
+			| WITH
 		;
 
 
@@ -9922,8 +10004,11 @@ findLeftmostSelect(SelectStmt *node)
 static void
 insertSelectOptions(SelectStmt *stmt,
 					List *sortClause, List *lockingClause,
-					Node *limitOffset, Node *limitCount)
+					Node *limitOffset, Node *limitCount,
+					WithClause *withClause)
 {
+	Assert(IsA(stmt, SelectStmt));
+
 	/*
 	 * Tests here are to reject constructs like
 	 *	(SELECT foo ORDER BY bar) ORDER BY baz
@@ -9957,6 +10042,15 @@ insertSelectOptions(SelectStmt *stmt,
 					 scanner_errposition(exprLocation(limitCount))));
 		stmt->limitCount = limitCount;
 	}
+	if (withClause)
+	{
+		if (stmt->withClause)
+			ereport(ERROR,
+					(errcode(ERRCODE_SYNTAX_ERROR),
+					 errmsg("multiple WITH clauses not allowed"),
+					 scanner_errposition(exprLocation((Node *) withClause))));
+		stmt->withClause = withClause;
+	}
 }
 
 static Node *
diff --git a/src/backend/parser/keywords.c b/src/backend/parser/keywords.c
index 0f17aa131eb..c55bfd8b5cd 100644
--- a/src/backend/parser/keywords.c
+++ b/src/backend/parser/keywords.c
@@ -11,7 +11,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/keywords.c,v 1.201 2008/09/23 09:20:36 heikki Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/keywords.c,v 1.202 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -305,6 +305,7 @@ const ScanKeyword ScanKeywords[] = {
 	{"real", REAL, COL_NAME_KEYWORD},
 	{"reassign", REASSIGN, UNRESERVED_KEYWORD},
 	{"recheck", RECHECK, UNRESERVED_KEYWORD},
+	{"recursive", RECURSIVE, UNRESERVED_KEYWORD},
 	{"references", REFERENCES, RESERVED_KEYWORD},
 	{"reindex", REINDEX, UNRESERVED_KEYWORD},
 	{"relative", RELATIVE_P, UNRESERVED_KEYWORD},
@@ -403,15 +404,6 @@ const ScanKeyword ScanKeywords[] = {
 	{"when", WHEN, RESERVED_KEYWORD},
 	{"where", WHERE, RESERVED_KEYWORD},
 	{"whitespace", WHITESPACE_P, UNRESERVED_KEYWORD},
-
-	/*
-	 * XXX we mark WITH as reserved to force it to be quoted in dumps, even
-	 * though it is currently unreserved according to gram.y.  This is because
-	 * we expect we'll have to make it reserved to implement SQL WITH clauses.
-	 * If that patch manages to do without reserving WITH, adjust this entry
-	 * at that time; in any case this should be back in sync with gram.y after
-	 * WITH clauses are implemented.
-	 */
 	{"with", WITH, RESERVED_KEYWORD},
 	{"without", WITHOUT, UNRESERVED_KEYWORD},
 	{"work", WORK, UNRESERVED_KEYWORD},
diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index d85f64c7abc..e2645462d57 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/parse_agg.c,v 1.83 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_agg.c,v 1.84 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -102,6 +102,7 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
 	bool		have_non_var_grouping;
 	ListCell   *l;
 	bool		hasJoinRTEs;
+	bool		hasSelfRefRTEs;
 	PlannerInfo *root;
 	Node	   *clause;
 
@@ -109,6 +110,21 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
 	Assert(pstate->p_hasAggs || qry->groupClause || qry->havingQual);
 
 	/*
+	 * Scan the range table to see if there are JOIN or self-reference CTE
+	 * entries.  We'll need this info below.
+	 */
+	hasJoinRTEs = hasSelfRefRTEs = false;
+	foreach(l, pstate->p_rtable)
+	{
+		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
+
+		if (rte->rtekind == RTE_JOIN)
+			hasJoinRTEs = true;
+		else if (rte->rtekind == RTE_CTE && rte->self_reference)
+			hasSelfRefRTEs = true;
+	}
+
+	/*
 	 * Aggregates must never appear in WHERE or JOIN/ON clauses.
 	 *
 	 * (Note this check should appear first to deliver an appropriate error
@@ -157,20 +173,6 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
 	 * underlying vars, so that aliased and unaliased vars will be correctly
 	 * taken as equal.	We can skip the expense of doing this if no rangetable
 	 * entries are RTE_JOIN kind.
-	 */
-	hasJoinRTEs = false;
-	foreach(l, pstate->p_rtable)
-	{
-		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
-
-		if (rte->rtekind == RTE_JOIN)
-		{
-			hasJoinRTEs = true;
-			break;
-		}
-	}
-
-	/*
 	 * We use the planner's flatten_join_alias_vars routine to do the
 	 * flattening; it wants a PlannerInfo root node, which fortunately can be
 	 * mostly dummy.
@@ -217,6 +219,16 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
 		clause = flatten_join_alias_vars(root, clause);
 	check_ungrouped_columns(clause, pstate,
 							groupClauses, have_non_var_grouping);
+
+	/*
+	 * Per spec, aggregates can't appear in a recursive term.
+	 */
+	if (pstate->p_hasAggs && hasSelfRefRTEs)
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_RECURSION),
+				 errmsg("aggregates not allowed in a recursive query's recursive term"),
+				 parser_errposition(pstate,
+									locate_agg_of_level((Node *) qry, 0))));
 }
 
 
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 2f547f29be6..dbf17759617 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/parse_clause.c,v 1.179 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_clause.c,v 1.180 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -54,6 +54,8 @@ static Node *transformJoinOnClause(ParseState *pstate, JoinExpr *j,
 					  List *relnamespace,
 					  Relids containedRels);
 static RangeTblEntry *transformTableEntry(ParseState *pstate, RangeVar *r);
+static RangeTblEntry *transformCTEReference(ParseState *pstate, RangeVar *r,
+					  CommonTableExpr *cte, Index levelsup);
 static RangeTblEntry *transformRangeSubselect(ParseState *pstate,
 						RangeSubselect *r);
 static RangeTblEntry *transformRangeFunction(ParseState *pstate,
@@ -422,6 +424,20 @@ transformTableEntry(ParseState *pstate, RangeVar *r)
 	return rte;
 }
 
+/*
+ * transformCTEReference --- transform a RangeVar that references a common
+ * table expression (ie, a sub-SELECT defined in a WITH clause)
+ */
+static RangeTblEntry *
+transformCTEReference(ParseState *pstate, RangeVar *r,
+					  CommonTableExpr *cte, Index levelsup)
+{
+	RangeTblEntry *rte;
+
+	rte = addRangeTableEntryForCTE(pstate, cte, levelsup, r->alias, true);
+
+	return rte;
+}
 
 /*
  * transformRangeSubselect --- transform a sub-SELECT appearing in FROM
@@ -609,12 +625,46 @@ transformFromClauseItem(ParseState *pstate, Node *n,
 {
 	if (IsA(n, RangeVar))
 	{
-		/* Plain relation reference */
+		/* Plain relation reference, or perhaps a CTE reference */
+		RangeVar *rv = (RangeVar *) n;
 		RangeTblRef *rtr;
-		RangeTblEntry *rte;
+		RangeTblEntry *rte = NULL;
 		int			rtindex;
 
-		rte = transformTableEntry(pstate, (RangeVar *) n);
+		/*
+		 * If it is an unqualified name, it might be a reference to some
+		 * CTE visible in this or a parent query.
+		 */
+		if (!rv->schemaname)
+		{
+			ParseState *ps;
+			Index	levelsup;
+
+			for (ps = pstate, levelsup = 0;
+				 ps != NULL;
+				 ps = ps->parentParseState, levelsup++)
+			{
+				ListCell *lc;
+
+				foreach(lc, ps->p_ctenamespace)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+					if (strcmp(rv->relname, cte->ctename) == 0)
+					{
+						rte = transformCTEReference(pstate, rv, cte, levelsup);
+						break;
+					}
+				}
+				if (rte)
+					break;
+			}
+		}
+
+		/* if not found as a CTE, must be a table reference */
+		if (!rte)
+			rte = transformTableEntry(pstate, rv);
+
 		/* assume new rte is at end */
 		rtindex = list_length(pstate->p_rtable);
 		Assert(rte == rt_fetch(rtindex, pstate->p_rtable));
diff --git a/src/backend/parser/parse_cte.c b/src/backend/parser/parse_cte.c
new file mode 100644
index 00000000000..64f5e51c28f
--- /dev/null
+++ b/src/backend/parser/parse_cte.c
@@ -0,0 +1,899 @@
+/*-------------------------------------------------------------------------
+ *
+ * parse_cte.c
+ *	  handle CTEs (common table expressions) in parser
+ *
+ * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_cte.c,v 2.1 2008/10/04 21:56:54 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/nodeFuncs.h"
+#include "parser/analyze.h"
+#include "parser/parse_cte.h"
+#include "utils/builtins.h"
+
+
+/* Enumeration of contexts in which a self-reference is disallowed */
+typedef enum
+{
+	RECURSION_OK,
+	RECURSION_NONRECURSIVETERM,	/* inside the left-hand term */
+	RECURSION_SUBLINK,			/* inside a sublink */
+	RECURSION_OUTERJOIN,		/* inside nullable side of an outer join */
+	RECURSION_INTERSECT,		/* underneath INTERSECT (ALL) */
+	RECURSION_EXCEPT			/* underneath EXCEPT (ALL) */
+} RecursionContext;
+
+/* Associated error messages --- each must have one %s for CTE name */
+static const char * const recursion_errormsgs[] = {
+	/* RECURSION_OK */
+	NULL,
+	/* RECURSION_NONRECURSIVETERM */
+	gettext_noop("recursive reference to query \"%s\" must not appear within its non-recursive term"),
+	/* RECURSION_SUBLINK */
+	gettext_noop("recursive reference to query \"%s\" must not appear within a subquery"),
+	/* RECURSION_OUTERJOIN */
+	gettext_noop("recursive reference to query \"%s\" must not appear within an outer join"),
+	/* RECURSION_INTERSECT */
+	gettext_noop("recursive reference to query \"%s\" must not appear within INTERSECT"),
+	/* RECURSION_EXCEPT */
+	gettext_noop("recursive reference to query \"%s\" must not appear within EXCEPT")
+};
+
+/*
+ * For WITH RECURSIVE, we have to find an ordering of the clause members
+ * with no forward references, and determine which members are recursive
+ * (i.e., self-referential).  It is convenient to do this with an array
+ * of CteItems instead of a list of CommonTableExprs.
+ */
+typedef struct CteItem
+{
+	CommonTableExpr *cte;			/* One CTE to examine */
+	int			id;					/* Its ID number for dependencies */
+	Node	   *non_recursive_term;	/* Its nonrecursive part, if identified */
+	Bitmapset  *depends_on;			/* CTEs depended on (not including self) */
+} CteItem;
+
+/* CteState is what we need to pass around in the tree walkers */
+typedef struct CteState
+{
+	/* global state: */
+	ParseState *pstate;			/* global parse state */
+	CteItem	   *items;			/* array of CTEs and extra data */
+	int			numitems;		/* number of CTEs */
+	/* working state during a tree walk: */
+	int			curitem;		/* index of item currently being examined */
+	List	   *innerwiths;		/* list of lists of CommonTableExpr */
+	/* working state for checkWellFormedRecursion walk only: */
+	int			selfrefcount;	/* number of self-references detected */
+	RecursionContext context;	/* context to allow or disallow self-ref */
+} CteState;
+
+
+static void analyzeCTE(ParseState *pstate, CommonTableExpr *cte);
+static void analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist);
+
+/* Dependency processing functions */
+static void makeDependencyGraph(CteState *cstate);
+static bool makeDependencyGraphWalker(Node *node, CteState *cstate);
+static void TopologicalSort(ParseState *pstate, CteItem *items, int numitems);
+
+/* Recursion validity checker functions */
+static void checkWellFormedRecursion(CteState *cstate);
+static bool checkWellFormedRecursionWalker(Node *node, CteState *cstate);
+static void checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate);
+
+
+/*
+ * transformWithClause -
+ *    Transform the list of WITH clause "common table expressions" into
+ *    Query nodes.
+ *
+ * The result is the list of transformed CTEs to be put into the output
+ * Query.  (This is in fact the same as the ending value of p_ctenamespace,
+ * but it seems cleaner to not expose that in the function's API.)
+ */
+List *
+transformWithClause(ParseState *pstate, WithClause *withClause)
+{
+	ListCell   *lc;
+
+	/* Only one WITH clause per query level */
+	Assert(pstate->p_ctenamespace == NIL);
+
+	/*
+	 * For either type of WITH, there must not be duplicate CTE names in
+	 * the list.  Check this right away so we needn't worry later.
+	 *
+	 * Also, tentatively mark each CTE as non-recursive, and initialize
+	 * its reference count to zero.
+	 */
+	foreach(lc, withClause->ctes)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+		ListCell   *rest;
+
+		for_each_cell(rest, lnext(lc))
+		{
+			CommonTableExpr *cte2 = (CommonTableExpr *) lfirst(rest);
+
+			if (strcmp(cte->ctename, cte2->ctename) == 0)
+				ereport(ERROR,
+						(errcode(ERRCODE_DUPLICATE_ALIAS),
+						 errmsg("WITH query name \"%s\" specified more than once",
+								cte2->ctename),
+						 parser_errposition(pstate, cte2->location)));
+		}
+
+		cte->cterecursive = false;
+		cte->cterefcount = 0;
+	}
+
+	if (withClause->recursive)
+	{
+		/*
+		 * For WITH RECURSIVE, we rearrange the list elements if needed
+		 * to eliminate forward references.  First, build a work array
+		 * and set up the data structure needed by the tree walkers.
+		 */
+		CteState cstate;
+		int		i;
+
+		cstate.pstate = pstate;
+		cstate.numitems = list_length(withClause->ctes);
+		cstate.items = (CteItem *) palloc0(cstate.numitems * sizeof(CteItem));
+		i = 0;
+		foreach(lc, withClause->ctes)
+		{
+			cstate.items[i].cte = (CommonTableExpr *) lfirst(lc);
+			cstate.items[i].id = i;
+			i++;
+		}
+
+		/*
+		 * Find all the dependencies and sort the CteItems into a safe
+		 * processing order.  Also, mark CTEs that contain self-references.
+		 */
+		makeDependencyGraph(&cstate);
+
+		/*
+		 * Check that recursive queries are well-formed.
+		 */
+		checkWellFormedRecursion(&cstate);
+
+		/*
+		 * Set up the ctenamespace for parse analysis.  Per spec, all
+		 * the WITH items are visible to all others, so stuff them all in
+		 * before parse analysis.  We build the list in safe processing
+		 * order so that the planner can process the queries in sequence.
+		 */
+		for (i = 0; i < cstate.numitems; i++)
+		{
+			CommonTableExpr *cte = cstate.items[i].cte;
+
+			pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte);
+		}
+
+		/*
+		 * Do parse analysis in the order determined by the topological sort.
+		 */
+		for (i = 0; i < cstate.numitems; i++)
+		{
+			CommonTableExpr *cte = cstate.items[i].cte;
+
+			/*
+			 * If it's recursive, we have to do a throwaway parse analysis
+			 * of the non-recursive term in order to determine the set of
+			 * output columns for the recursive CTE.
+			 */
+			if (cte->cterecursive)
+			{
+				Node   *nrt;
+				Query  *nrq;
+
+				if (!cstate.items[i].non_recursive_term)
+					elog(ERROR, "could not find non-recursive term for %s",
+						 cte->ctename);
+				/* copy the term to be sure we don't modify original query */
+				nrt = copyObject(cstate.items[i].non_recursive_term);
+				nrq = parse_sub_analyze(nrt, pstate);
+				analyzeCTETargetList(pstate, cte, nrq->targetList);
+			}
+
+			analyzeCTE(pstate, cte);
+		}
+	}
+	else
+	{
+		/*
+		 * For non-recursive WITH, just analyze each CTE in sequence and then
+		 * add it to the ctenamespace.  This corresponds to the spec's
+		 * definition of the scope of each WITH name.
+		 */
+		foreach(lc, withClause->ctes)
+		{
+			CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+			analyzeCTE(pstate, cte);
+			pstate->p_ctenamespace = lappend(pstate->p_ctenamespace, cte);
+		}
+ 	}
+
+	return pstate->p_ctenamespace;
+}
+
+
+/*
+ * Perform the actual parse analysis transformation of one CTE.  All
+ * CTEs it depends on have already been loaded into pstate->p_ctenamespace,
+ * and have been marked with the correct output column names/types.
+ */
+static void
+analyzeCTE(ParseState *pstate, CommonTableExpr *cte)
+{
+	Query  *query;
+
+	/* Analysis not done already */
+	Assert(IsA(cte->ctequery, SelectStmt));
+
+	query = parse_sub_analyze(cte->ctequery, pstate);
+	cte->ctequery = (Node *) query;
+
+	/*
+	 * Check that we got something reasonable.	Many of these conditions are
+	 * impossible given restrictions of the grammar, but check 'em anyway.
+	 * (These are the same checks as in transformRangeSubselect.)
+	 */
+	if (!IsA(query, Query) ||
+		query->commandType != CMD_SELECT ||
+		query->utilityStmt != NULL)
+		elog(ERROR, "unexpected non-SELECT command in subquery in WITH");
+	if (query->intoClause)
+		ereport(ERROR,
+				(errcode(ERRCODE_SYNTAX_ERROR),
+				 errmsg("subquery in WITH cannot have SELECT INTO"),
+				 parser_errposition(pstate,
+									exprLocation((Node *) query->intoClause))));
+
+	if (!cte->cterecursive)
+	{
+		/* Compute the output column names/types if not done yet */
+		analyzeCTETargetList(pstate, cte, query->targetList);
+	}
+	else
+	{
+		/*
+		 * Verify that the previously determined output column types match
+		 * what the query really produced.  We have to check this because
+		 * the recursive term could have overridden the non-recursive term,
+		 * and we don't have any easy way to fix that.
+		 */
+		ListCell   *lctlist,
+				   *lctyp,
+				   *lctypmod;
+		int			varattno;
+
+		lctyp = list_head(cte->ctecoltypes);
+		lctypmod = list_head(cte->ctecoltypmods);
+		varattno = 0;
+		foreach(lctlist, query->targetList)
+		{
+			TargetEntry *te = (TargetEntry *) lfirst(lctlist);
+			Node   *texpr;
+
+			if (te->resjunk)
+				continue;
+			varattno++;
+			Assert(varattno == te->resno);
+			if (lctyp == NULL || lctypmod == NULL)		/* shouldn't happen */
+				elog(ERROR, "wrong number of output columns in WITH");
+			texpr = (Node *) te->expr;
+			if (exprType(texpr) != lfirst_oid(lctyp) ||
+				exprTypmod(texpr) != lfirst_int(lctypmod))
+				ereport(ERROR,
+						(errcode(ERRCODE_DATATYPE_MISMATCH),
+						 errmsg("recursive query \"%s\" column %d has type %s in non-recursive term but type %s overall",
+								cte->ctename, varattno,
+								format_type_with_typemod(lfirst_oid(lctyp),
+														 lfirst_int(lctypmod)),
+								format_type_with_typemod(exprType(texpr),
+														 exprTypmod(texpr))),
+						 errhint("Cast the output of the non-recursive term to the correct type."),
+						 parser_errposition(pstate, exprLocation(texpr))));
+			lctyp = lnext(lctyp);
+			lctypmod = lnext(lctypmod);
+		}
+		if (lctyp != NULL || lctypmod != NULL)		/* shouldn't happen */
+			elog(ERROR, "wrong number of output columns in WITH");
+	}
+}
+
+/*
+ * Compute derived fields of a CTE, given the transformed output targetlist
+ */
+static void
+analyzeCTETargetList(ParseState *pstate, CommonTableExpr *cte, List *tlist)
+{
+	int			numaliases;
+	int			varattno;
+	ListCell   *tlistitem;
+
+	/*
+	 * We need to determine column names and types.  The alias column names
+	 * override anything coming from the query itself.  (Note: the SQL spec
+	 * says that the alias list must be empty or exactly as long as the
+	 * output column set; but we allow it to be shorter for consistency
+	 * with Alias handling.)
+	 */
+	cte->ctecolnames = copyObject(cte->aliascolnames);
+	cte->ctecoltypes = cte->ctecoltypmods = NIL;
+	numaliases = list_length(cte->aliascolnames);
+	varattno = 0;
+	foreach(tlistitem, tlist)
+	{
+		TargetEntry *te = (TargetEntry *) lfirst(tlistitem);
+
+		if (te->resjunk)
+			continue;
+		varattno++;
+		Assert(varattno == te->resno);
+		if (varattno > numaliases)
+		{
+			char	   *attrname;
+
+			attrname = pstrdup(te->resname);
+			cte->ctecolnames = lappend(cte->ctecolnames, makeString(attrname));
+		}
+		cte->ctecoltypes = lappend_oid(cte->ctecoltypes,
+									   exprType((Node *) te->expr));
+		cte->ctecoltypmods = lappend_int(cte->ctecoltypmods,
+										 exprTypmod((Node *) te->expr));
+	}
+	if (varattno < numaliases)
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
+				 errmsg("WITH query \"%s\" has %d columns available but %d columns specified",
+						cte->ctename, varattno, numaliases),
+				 parser_errposition(pstate, cte->location)));
+}
+
+
+/*
+ * Identify the cross-references of a list of WITH RECURSIVE items,
+ * and sort into an order that has no forward references.
+ */
+static void
+makeDependencyGraph(CteState *cstate)
+{
+	int			i;
+
+	for (i = 0; i < cstate->numitems; i++)
+	{
+		CommonTableExpr *cte = cstate->items[i].cte;
+
+		cstate->curitem = i;
+		cstate->innerwiths = NIL;
+		makeDependencyGraphWalker((Node *) cte->ctequery, cstate);
+		Assert(cstate->innerwiths == NIL);
+	}
+
+	TopologicalSort(cstate->pstate, cstate->items, cstate->numitems);
+}
+
+/*
+ * Tree walker function to detect cross-references and self-references of the
+ * CTEs in a WITH RECURSIVE list.
+ */
+static bool
+makeDependencyGraphWalker(Node *node, CteState *cstate)
+{
+	if (node == NULL)
+		return false;
+	if (IsA(node, RangeVar))
+	{
+		RangeVar   *rv = (RangeVar *) node;
+
+		/* If unqualified name, might be a CTE reference */
+		if (!rv->schemaname)
+		{
+			ListCell *lc;
+			int		i;
+
+			/* ... but first see if it's captured by an inner WITH */
+			foreach(lc, cstate->innerwiths)
+			{
+				List   *withlist = (List *) lfirst(lc);
+				ListCell *lc2;
+
+				foreach(lc2, withlist)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2);
+
+					if (strcmp(rv->relname, cte->ctename) == 0)
+						return false;				/* yes, so bail out */
+				}
+			}
+
+			/* No, could be a reference to the query level we are working on */
+			for (i = 0; i < cstate->numitems; i++)
+			{
+				CommonTableExpr *cte = cstate->items[i].cte;
+
+				if (strcmp(rv->relname, cte->ctename) == 0)
+				{
+					int		myindex = cstate->curitem;
+
+					if (i != myindex)
+					{
+						/* Add cross-item dependency */
+						cstate->items[myindex].depends_on =
+							bms_add_member(cstate->items[myindex].depends_on,
+										   cstate->items[i].id);
+					}
+					else
+					{
+						/* Found out this one is self-referential */
+						cte->cterecursive = true;
+					}
+					break;
+				}
+			}
+		}
+		return false;
+	}
+	if (IsA(node, SelectStmt))
+	{
+		SelectStmt *stmt = (SelectStmt *) node;
+		ListCell *lc;
+
+		if (stmt->withClause)
+		{
+			if (stmt->withClause->recursive)
+			{
+				/*
+				 * In the RECURSIVE case, all query names of the WITH are
+				 * visible to all WITH items as well as the main query.
+				 * So push them all on, process, pop them all off.
+				 */
+				cstate->innerwiths = lcons(stmt->withClause->ctes,
+										   cstate->innerwiths);
+				foreach(lc, stmt->withClause->ctes)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+					(void) makeDependencyGraphWalker(cte->ctequery, cstate);
+				}
+				(void) raw_expression_tree_walker(node,
+												  makeDependencyGraphWalker,
+												  (void *) cstate);
+				cstate->innerwiths = list_delete_first(cstate->innerwiths);
+			}
+			else
+			{
+				/*
+				 * In the non-RECURSIVE case, query names are visible to
+				 * the WITH items after them and to the main query.
+				 */
+				ListCell   *cell1;
+
+				cstate->innerwiths = lcons(NIL, cstate->innerwiths);
+				cell1 = list_head(cstate->innerwiths);
+				foreach(lc, stmt->withClause->ctes)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+					(void) makeDependencyGraphWalker(cte->ctequery, cstate);
+					lfirst(cell1) = lappend((List *) lfirst(cell1), cte);
+				}
+				(void) raw_expression_tree_walker(node,
+												  makeDependencyGraphWalker,
+												  (void *) cstate);
+				cstate->innerwiths = list_delete_first(cstate->innerwiths);
+			}
+			/* We're done examining the SelectStmt */
+			return false;
+		}
+		/* if no WITH clause, just fall through for normal processing */
+	}
+	if (IsA(node, WithClause))
+	{
+		/*
+		 * Prevent raw_expression_tree_walker from recursing directly into
+		 * a WITH clause.  We need that to happen only under the control
+		 * of the code above.
+		 */
+		return false;
+	}
+	return raw_expression_tree_walker(node,
+									  makeDependencyGraphWalker,
+									  (void *) cstate);
+}
+
+/*
+ * Sort by dependencies, using a standard topological sort operation
+ */
+static void
+TopologicalSort(ParseState *pstate, CteItem *items, int numitems)
+{
+	int i, j;
+
+	/* for each position in sequence ... */
+	for (i = 0; i < numitems; i++)
+	{
+		/* ... scan the remaining items to find one that has no dependencies */
+		for (j = i; j < numitems; j++)
+		{
+			if (bms_is_empty(items[j].depends_on))
+				break;
+		}
+
+		/* if we didn't find one, the dependency graph has a cycle */
+		if (j >= numitems)
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("mutual recursion between WITH items is not implemented"),
+					 parser_errposition(pstate, items[i].cte->location)));
+
+		/*
+		 * Found one.  Move it to front and remove it from every other
+		 * item's dependencies.
+		 */
+		if (i != j)
+		{
+			CteItem tmp;
+				
+			tmp = items[i];
+			items[i] = items[j];
+			items[j] = tmp;
+		}
+		/*
+		 * Items up through i are known to have no dependencies left,
+		 * so we can skip them in this loop.
+		 */
+		for (j = i + 1; j < numitems; j++)
+		{
+			items[j].depends_on = bms_del_member(items[j].depends_on,
+												 items[i].id);
+		}
+	}
+}
+
+
+/*
+ * Check that recursive queries are well-formed.
+ */
+static void
+checkWellFormedRecursion(CteState *cstate)
+{
+	int			i;
+
+	for (i = 0; i < cstate->numitems; i++)
+	{
+		CommonTableExpr *cte = cstate->items[i].cte;
+		SelectStmt		*stmt = (SelectStmt *) cte->ctequery;
+
+		Assert(IsA(stmt, SelectStmt));				/* not analyzed yet */
+
+		/* Ignore items that weren't found to be recursive */
+		if (!cte->cterecursive)
+			continue;
+
+		/* Must have top-level UNION ALL */
+		if (stmt->op != SETOP_UNION || !stmt->all)
+			ereport(ERROR,
+					(errcode(ERRCODE_INVALID_RECURSION),
+					 errmsg("recursive query \"%s\" does not have the form non-recursive-term UNION ALL recursive-term",
+							cte->ctename),
+					 parser_errposition(cstate->pstate, cte->location)));
+
+		/* The left-hand operand mustn't contain self-reference at all */
+		cstate->curitem = i;
+		cstate->innerwiths = NIL;
+		cstate->selfrefcount = 0;
+		cstate->context = RECURSION_NONRECURSIVETERM;
+		checkWellFormedRecursionWalker((Node *) stmt->larg, cstate);
+		Assert(cstate->innerwiths == NIL);
+
+		/* Right-hand operand should contain one reference in a valid place */
+		cstate->curitem = i;
+		cstate->innerwiths = NIL;
+		cstate->selfrefcount = 0;
+		cstate->context = RECURSION_OK;
+		checkWellFormedRecursionWalker((Node *) stmt->rarg, cstate);
+		Assert(cstate->innerwiths == NIL);
+		if (cstate->selfrefcount != 1)			/* shouldn't happen */
+			elog(ERROR, "missing recursive reference");
+
+		/*
+		 * Disallow ORDER BY and similar decoration atop the UNION ALL.
+		 * These don't make sense because it's impossible to figure out what
+		 * they mean when we have only part of the recursive query's results.
+		 * (If we did allow them, we'd have to check for recursive references
+		 * inside these subtrees.)
+		 */
+		if (stmt->sortClause)
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("ORDER BY in a recursive query is not implemented"),
+					 parser_errposition(cstate->pstate,
+										exprLocation((Node *) stmt->sortClause))));
+		if (stmt->limitOffset)
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("OFFSET in a recursive query is not implemented"),
+					 parser_errposition(cstate->pstate,
+										exprLocation(stmt->limitOffset))));
+		if (stmt->limitCount)
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("LIMIT in a recursive query is not implemented"),
+					 parser_errposition(cstate->pstate,
+										exprLocation(stmt->limitCount))));
+		if (stmt->lockingClause)
+			ereport(ERROR,
+					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+					 errmsg("FOR UPDATE/SHARE in a recursive query is not implemented"),
+					 parser_errposition(cstate->pstate,
+										exprLocation((Node *) stmt->lockingClause))));
+
+		/*
+		 * Save non_recursive_term.
+		 */
+		cstate->items[i].non_recursive_term = (Node *) stmt->larg;
+	}
+}
+
+/*
+ * Tree walker function to detect invalid self-references in a recursive query.
+ */
+static bool
+checkWellFormedRecursionWalker(Node *node, CteState *cstate)
+{
+	RecursionContext save_context = cstate->context;
+
+	if (node == NULL)
+		return false;
+	if (IsA(node, RangeVar))
+	{
+		RangeVar   *rv = (RangeVar *) node;
+
+		/* If unqualified name, might be a CTE reference */
+		if (!rv->schemaname)
+		{
+			ListCell *lc;
+			CommonTableExpr *mycte;
+
+			/* ... but first see if it's captured by an inner WITH */
+			foreach(lc, cstate->innerwiths)
+			{
+				List   *withlist = (List *) lfirst(lc);
+				ListCell *lc2;
+
+				foreach(lc2, withlist)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc2);
+
+					if (strcmp(rv->relname, cte->ctename) == 0)
+						return false;				/* yes, so bail out */
+				}
+			}
+
+			/* No, could be a reference to the query level we are working on */
+			mycte = cstate->items[cstate->curitem].cte;
+			if (strcmp(rv->relname, mycte->ctename) == 0)
+			{
+				/* Found a recursive reference to the active query */
+				if (cstate->context != RECURSION_OK)
+					ereport(ERROR,
+							(errcode(ERRCODE_INVALID_RECURSION),
+							 errmsg(recursion_errormsgs[cstate->context],
+									mycte->ctename),
+							 parser_errposition(cstate->pstate,
+												rv->location)));
+				/* Count references */
+				if (++(cstate->selfrefcount) > 1)
+					ereport(ERROR,
+							(errcode(ERRCODE_INVALID_RECURSION),
+							 errmsg("recursive reference to query \"%s\" must not appear more than once",
+									mycte->ctename),
+							 parser_errposition(cstate->pstate,
+												rv->location)));
+			}
+		}
+		return false;
+	}
+	if (IsA(node, SelectStmt))
+	{
+		SelectStmt *stmt = (SelectStmt *) node;
+		ListCell *lc;
+
+		if (stmt->withClause)
+		{
+			if (stmt->withClause->recursive)
+			{
+				/*
+				 * In the RECURSIVE case, all query names of the WITH are
+				 * visible to all WITH items as well as the main query.
+				 * So push them all on, process, pop them all off.
+				 */
+				cstate->innerwiths = lcons(stmt->withClause->ctes,
+										   cstate->innerwiths);
+				foreach(lc, stmt->withClause->ctes)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+					(void) checkWellFormedRecursionWalker(cte->ctequery, cstate);
+				}
+				checkWellFormedSelectStmt(stmt, cstate);
+				cstate->innerwiths = list_delete_first(cstate->innerwiths);
+			}
+			else
+			{
+				/*
+				 * In the non-RECURSIVE case, query names are visible to
+				 * the WITH items after them and to the main query.
+				 */
+				ListCell   *cell1;
+
+				cstate->innerwiths = lcons(NIL, cstate->innerwiths);
+				cell1 = list_head(cstate->innerwiths);
+				foreach(lc, stmt->withClause->ctes)
+				{
+					CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+					(void) checkWellFormedRecursionWalker(cte->ctequery, cstate);
+					lfirst(cell1) = lappend((List *) lfirst(cell1), cte);
+				}
+				checkWellFormedSelectStmt(stmt, cstate);
+				cstate->innerwiths = list_delete_first(cstate->innerwiths);
+			}
+		}
+		else
+				checkWellFormedSelectStmt(stmt, cstate);
+		/* We're done examining the SelectStmt */
+		return false;
+	}
+	if (IsA(node, WithClause))
+	{
+		/*
+		 * Prevent raw_expression_tree_walker from recursing directly into
+		 * a WITH clause.  We need that to happen only under the control
+		 * of the code above.
+		 */
+		return false;
+	}
+	if (IsA(node, JoinExpr))
+	{
+		JoinExpr *j = (JoinExpr *) node;
+
+		switch (j->jointype)
+		{
+			case JOIN_INNER:
+				checkWellFormedRecursionWalker(j->larg, cstate);
+				checkWellFormedRecursionWalker(j->rarg, cstate);
+				checkWellFormedRecursionWalker(j->quals, cstate);
+				break;
+			case JOIN_LEFT:
+				checkWellFormedRecursionWalker(j->larg, cstate);
+				if (save_context == RECURSION_OK)
+					cstate->context = RECURSION_OUTERJOIN;
+				checkWellFormedRecursionWalker(j->rarg, cstate);
+				cstate->context = save_context;
+				checkWellFormedRecursionWalker(j->quals, cstate);
+				break;
+			case JOIN_FULL:
+				if (save_context == RECURSION_OK)
+					cstate->context = RECURSION_OUTERJOIN;
+				checkWellFormedRecursionWalker(j->larg, cstate);
+				checkWellFormedRecursionWalker(j->rarg, cstate);
+				cstate->context = save_context;
+				checkWellFormedRecursionWalker(j->quals, cstate);
+				break;
+			case JOIN_RIGHT:
+				if (save_context == RECURSION_OK)
+					cstate->context = RECURSION_OUTERJOIN;
+				checkWellFormedRecursionWalker(j->larg, cstate);
+				cstate->context = save_context;
+				checkWellFormedRecursionWalker(j->rarg, cstate);
+				checkWellFormedRecursionWalker(j->quals, cstate);
+				break;
+			default:
+				elog(ERROR, "unrecognized join type: %d",
+					 (int) j->jointype);
+		}
+		return false;
+	}
+	if (IsA(node, SubLink))
+	{
+		SubLink *sl = (SubLink *) node;
+
+		/*
+		 * we intentionally override outer context, since subquery is
+		 * independent
+		 */
+		cstate->context = RECURSION_SUBLINK;
+		checkWellFormedRecursionWalker(sl->subselect, cstate);
+		cstate->context = save_context;
+		checkWellFormedRecursionWalker(sl->testexpr, cstate);
+		return false;
+	}
+	return raw_expression_tree_walker(node,
+									  checkWellFormedRecursionWalker,
+									  (void *) cstate);
+}
+
+/*
+ * subroutine for checkWellFormedRecursionWalker: process a SelectStmt
+ * without worrying about its WITH clause
+ */
+static void
+checkWellFormedSelectStmt(SelectStmt *stmt, CteState *cstate)
+{
+	RecursionContext save_context = cstate->context;
+
+	if (save_context != RECURSION_OK)
+	{
+		/* just recurse without changing state */
+		raw_expression_tree_walker((Node *) stmt,
+								   checkWellFormedRecursionWalker,
+								   (void *) cstate);
+	}
+	else
+	{
+		switch (stmt->op)
+		{
+			case SETOP_NONE:
+			case SETOP_UNION:
+				raw_expression_tree_walker((Node *) stmt,
+										   checkWellFormedRecursionWalker,
+										   (void *) cstate);
+				break;
+			case SETOP_INTERSECT:
+				if (stmt->all)
+					cstate->context = RECURSION_INTERSECT;
+				checkWellFormedRecursionWalker((Node *) stmt->larg,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->rarg,
+											   cstate);
+				cstate->context = save_context;
+				checkWellFormedRecursionWalker((Node *) stmt->sortClause,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->limitOffset,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->limitCount,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->lockingClause,
+											   cstate);
+				break;
+				break;
+			case SETOP_EXCEPT:
+				if (stmt->all)
+					cstate->context = RECURSION_EXCEPT;
+				checkWellFormedRecursionWalker((Node *) stmt->larg,
+											   cstate);
+				cstate->context = RECURSION_EXCEPT;
+				checkWellFormedRecursionWalker((Node *) stmt->rarg,
+											   cstate);
+				cstate->context = save_context;
+				checkWellFormedRecursionWalker((Node *) stmt->sortClause,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->limitOffset,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->limitCount,
+											   cstate);
+				checkWellFormedRecursionWalker((Node *) stmt->lockingClause,
+											   cstate);
+				break;
+			default:
+				elog(ERROR, "unrecognized set op: %d",
+					 (int) stmt->op);
+		}
+	}
+}
diff --git a/src/backend/parser/parse_relation.c b/src/backend/parser/parse_relation.c
index 6accd96f0da..fa2da35c6b7 100644
--- a/src/backend/parser/parse_relation.c
+++ b/src/backend/parser/parse_relation.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/parse_relation.c,v 1.135 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_relation.c,v 1.136 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -319,6 +319,35 @@ GetRTEByRangeTablePosn(ParseState *pstate,
 }
 
 /*
+ * Fetch the CTE for a CTE-reference RTE.
+ */
+CommonTableExpr *
+GetCTEForRTE(ParseState *pstate, RangeTblEntry *rte)
+{
+	Index		levelsup;
+	ListCell   *lc;
+
+	Assert(rte->rtekind == RTE_CTE);
+	levelsup = rte->ctelevelsup;
+	while (levelsup-- > 0)
+	{
+		pstate = pstate->parentParseState;
+		if (!pstate)			/* shouldn't happen */
+			elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
+	}
+	foreach(lc, pstate->p_ctenamespace)
+	{
+		CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
+
+		if (strcmp(cte->ctename, rte->ctename) == 0)
+			return cte;
+	}
+	/* shouldn't happen */
+	elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
+	return NULL;				/* keep compiler quiet */
+}
+
+/*
  * scanRTEForColumn
  *	  Search the column names of a single RTE for the given name.
  *	  If found, return an appropriate Var node, else return NULL.
@@ -1109,6 +1138,88 @@ addRangeTableEntryForJoin(ParseState *pstate,
 }
 
 /*
+ * Add an entry for a CTE reference to the pstate's range table (p_rtable).
+ *
+ * This is much like addRangeTableEntry() except that it makes a CTE RTE.
+ */
+RangeTblEntry *
+addRangeTableEntryForCTE(ParseState *pstate,
+						 CommonTableExpr *cte,
+						 Index levelsup,
+						 Alias *alias,
+						 bool inFromCl)
+{
+	RangeTblEntry *rte = makeNode(RangeTblEntry);
+	char	   *refname = alias ? alias->aliasname : cte->ctename;
+	Alias	   *eref;
+	int			numaliases;
+	int			varattno;
+	ListCell   *lc;
+
+	rte->rtekind = RTE_CTE;
+	rte->ctename = cte->ctename;
+	rte->ctelevelsup = levelsup;
+
+	/* Self-reference if and only if CTE's parse analysis isn't completed */
+	rte->self_reference = !IsA(cte->ctequery, Query);
+	Assert(cte->cterecursive || !rte->self_reference);
+	/* Bump the CTE's refcount if this isn't a self-reference */
+	if (!rte->self_reference)
+		cte->cterefcount++;
+
+	rte->ctecoltypes = cte->ctecoltypes;
+	rte->ctecoltypmods = cte->ctecoltypmods;
+
+	rte->alias = alias;
+	if (alias)
+		eref = copyObject(alias);
+	else
+		eref = makeAlias(refname, NIL);
+	numaliases = list_length(eref->colnames);
+
+	/* fill in any unspecified alias columns */
+	varattno = 0;
+	foreach(lc, cte->ctecolnames)
+	{
+		varattno++;
+		if (varattno > numaliases)
+			eref->colnames = lappend(eref->colnames, lfirst(lc));
+	}
+	if (varattno < numaliases)
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_COLUMN_REFERENCE),
+				 errmsg("table \"%s\" has %d columns available but %d columns specified",
+						refname, varattno, numaliases)));
+
+	rte->eref = eref;
+
+	/*----------
+	 * Flags:
+	 * - this RTE should be expanded to include descendant tables,
+	 * - this RTE is in the FROM clause,
+	 * - this RTE should be checked for appropriate access rights.
+	 *
+	 * Subqueries are never checked for access rights.
+	 *----------
+	 */
+	rte->inh = false;			/* never true for subqueries */
+	rte->inFromCl = inFromCl;
+
+	rte->requiredPerms = 0;
+	rte->checkAsUser = InvalidOid;
+
+	/*
+	 * Add completed RTE to pstate's range table list, but not to join list
+	 * nor namespace --- caller must do that if appropriate.
+	 */
+	if (pstate != NULL)
+		pstate->p_rtable = lappend(pstate->p_rtable, rte);
+
+	return rte;
+}
+
+
+/*
  * Has the specified refname been selected FOR UPDATE/FOR SHARE?
  *
  * Note: we pay no attention to whether it's FOR UPDATE vs FOR SHARE.
@@ -1444,6 +1555,41 @@ expandRTE(RangeTblEntry *rte, int rtindex, int sublevels_up,
 				}
 			}
 			break;
+		case RTE_CTE:
+			{
+				ListCell   *aliasp_item = list_head(rte->eref->colnames);
+				ListCell   *lct;
+				ListCell   *lcm;
+
+				varattno = 0;
+				forboth(lct, rte->ctecoltypes, lcm, rte->ctecoltypmods)
+				{
+					Oid		coltype = lfirst_oid(lct);
+					int32	coltypmod = lfirst_int(lcm);
+
+					varattno++;
+
+					if (colnames)
+					{
+						/* Assume there is one alias per output column */
+						char	   *label = strVal(lfirst(aliasp_item));
+
+						*colnames = lappend(*colnames, makeString(pstrdup(label)));
+						aliasp_item = lnext(aliasp_item);
+					}
+
+					if (colvars)
+					{
+						Var		   *varnode;
+
+						varnode = makeVar(rtindex, varattno,
+										  coltype, coltypmod,
+										  sublevels_up);
+						*colvars = lappend(*colvars, varnode);
+					}
+				}
+			}
+			break;
 		default:
 			elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind);
 	}
@@ -1750,6 +1896,14 @@ get_rte_attribute_type(RangeTblEntry *rte, AttrNumber attnum,
 				*vartypmod = exprTypmod(aliasvar);
 			}
 			break;
+		case RTE_CTE:
+			{
+				/* CTE RTE --- get type info from lists in the RTE */
+				Assert(attnum > 0 && attnum <= list_length(rte->ctecoltypes));
+				*vartype = list_nth_oid(rte->ctecoltypes, attnum - 1);
+				*vartypmod = list_nth_int(rte->ctecoltypmods, attnum - 1);
+			}
+			break;
 		default:
 			elog(ERROR, "unrecognized RTE kind: %d", (int) rte->rtekind);
 	}
@@ -1788,7 +1942,8 @@ get_rte_attribute_is_dropped(RangeTblEntry *rte, AttrNumber attnum)
 			break;
 		case RTE_SUBQUERY:
 		case RTE_VALUES:
-			/* Subselect and Values RTEs never have dropped columns */
+		case RTE_CTE:
+			/* Subselect, Values, CTE RTEs never have dropped columns */
 			result = false;
 			break;
 		case RTE_JOIN:
diff --git a/src/backend/parser/parse_target.c b/src/backend/parser/parse_target.c
index 20d91a142f5..3ead26194e3 100644
--- a/src/backend/parser/parse_target.c
+++ b/src/backend/parser/parse_target.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/parse_target.c,v 1.164 2008/09/01 20:42:44 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_target.c,v 1.165 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -296,6 +296,24 @@ markTargetListOrigin(ParseState *pstate, TargetEntry *tle,
 		case RTE_VALUES:
 			/* not a simple relation, leave it unmarked */
 			break;
+		case RTE_CTE:
+			/* CTE reference: copy up from the subquery */
+			if (attnum != InvalidAttrNumber)
+			{
+				CommonTableExpr *cte = GetCTEForRTE(pstate, rte);
+				TargetEntry *ste;
+
+				/* should be analyzed by now */
+				Assert(IsA(cte->ctequery, Query));
+				ste = get_tle_by_resno(((Query *) cte->ctequery)->targetList,
+									   attnum);
+				if (ste == NULL || ste->resjunk)
+					elog(ERROR, "subquery %s does not have attribute %d",
+						 rte->eref->aliasname, attnum);
+				tle->resorigtbl = ste->resorigtbl;
+				tle->resorigcol = ste->resorigcol;
+			}
+			break;
 	}
 }
 
@@ -1176,6 +1194,44 @@ expandRecordVariable(ParseState *pstate, Var *var, int levelsup)
 			 * its result columns as RECORD, which is not allowed.
 			 */
 			break;
+		case RTE_CTE:
+			{
+				/* CTE reference: examine subquery's output expr */
+				CommonTableExpr *cte = GetCTEForRTE(pstate, rte);
+				TargetEntry *ste;
+
+				/* should be analyzed by now */
+				Assert(IsA(cte->ctequery, Query));
+				ste = get_tle_by_resno(((Query *) cte->ctequery)->targetList,
+									   attnum);
+				if (ste == NULL || ste->resjunk)
+					elog(ERROR, "subquery %s does not have attribute %d",
+						 rte->eref->aliasname, attnum);
+				expr = (Node *) ste->expr;
+				if (IsA(expr, Var))
+				{
+					/*
+					 * Recurse into the CTE to see what its Var refers to. We
+					 * have to build an additional level of ParseState to keep
+					 * in step with varlevelsup in the CTE; furthermore it
+					 * could be an outer CTE.
+					 */
+					ParseState	mypstate;
+					Index		levelsup;
+
+					MemSet(&mypstate, 0, sizeof(mypstate));
+					/* this loop must work, since GetCTEForRTE did */
+					for (levelsup = 0; levelsup < rte->ctelevelsup; levelsup++)
+						pstate = pstate->parentParseState;
+					mypstate.parentParseState = pstate;
+					mypstate.p_rtable = ((Query *) cte->ctequery)->rtable;
+					/* don't bother filling the rest of the fake pstate */
+
+					return expandRecordVariable(&mypstate, (Var *) expr, 0);
+				}
+				/* else fall through to inspect the expression */
+			}
+			break;
 	}
 
 	/*
diff --git a/src/backend/parser/parse_type.c b/src/backend/parser/parse_type.c
index 960542029fd..0253cfe1593 100644
--- a/src/backend/parser/parse_type.c
+++ b/src/backend/parser/parse_type.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/parser/parse_type.c,v 1.99 2008/09/01 20:42:45 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/parser/parse_type.c,v 1.100 2008/10/04 21:56:54 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -611,6 +611,7 @@ parseTypeString(const char *str, Oid *type_id, int32 *typmod_p)
 		stmt->whereClause != NULL ||
 		stmt->groupClause != NIL ||
 		stmt->havingClause != NULL ||
+		stmt->withClause != NULL ||
 		stmt->valuesLists != NIL ||
 		stmt->sortClause != NIL ||
 		stmt->limitOffset != NULL ||