text: /*-------------------------------------------------------------------------
   *
   * tlist.c
   *	  Target list manipulation routines
   *
   * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
   *
   *
   * IDENTIFICATION
   *	  src/backend/optimizer/util/tlist.c
   *
   *-------------------------------------------------------------------------
   */
  #include "postgres.h"
  
  #include "nodes/makefuncs.h"
  #include "nodes/nodeFuncs.h"
  #include "optimizer/tlist.h"
  #include "optimizer/var.h"
  
  
  /*****************************************************************************
   *		Target list creation and searching utilities
   *****************************************************************************/
  
  /*
   * tlist_member
   *	  Finds the (first) member of the given tlist whose expression is
   *	  equal() to the given expression.	Result is NULL if no such member.
   */
  TargetEntry *
  tlist_member(Node *node, List *targetlist)
  {
  	ListCell   *temp;
  
  	foreach(temp, targetlist)
  	{
  		TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
  
  		if (equal(node, tlentry->expr))
  			return tlentry;
  	}
  	return NULL;
  }
  
  /*
   * tlist_member_ignore_relabel
   *	  Same as above, except that we ignore top-level RelabelType nodes
   *	  while checking for a match.  This is needed for some scenarios
   *	  involving binary-compatible sort operations.
   */
  TargetEntry *
  tlist_member_ignore_relabel(Node *node, List *targetlist)
  {
  	ListCell   *temp;
  
  	while (node && IsA(node, RelabelType))
  		node = (Node *) ((RelabelType *) node)->arg;
  
  	foreach(temp, targetlist)
  	{
  		TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
  		Expr	   *tlexpr = tlentry->expr;
  
  		while (tlexpr && IsA(tlexpr, RelabelType))
  			tlexpr = ((RelabelType *) tlexpr)->arg;
  
  		if (equal(node, tlexpr))
  			return tlentry;
  	}
  	return NULL;
  }
  
  /*
   * flatten_tlist
   *	  Create a target list that only contains unique variables.
   *
   * Note that Vars with varlevelsup > 0 are not included in the output
   * tlist.  We expect that those will eventually be replaced with Params,
   * but that probably has not happened at the time this routine is called.
   *
   * 'tlist' is the current target list
   *
   * Returns the "flattened" new target list.
   *
   * The result is entirely new structure sharing no nodes with the original.
   * Copying the Var nodes is probably overkill, but be safe for now.
   */
  List *
  flatten_tlist(List *tlist)
  {
  	List	   *vlist = pull_var_clause((Node *) tlist,
  										PVC_INCLUDE_PLACEHOLDERS);
  	List	   *new_tlist;
  
  	new_tlist = add_to_flat_tlist(NIL, vlist);
  	list_free(vlist);
  	return new_tlist;
  }
  
  /*
   * add_to_flat_tlist
   *		Add more items to a flattened tlist (if they're not already in it)
   *
   * 'tlist' is the flattened tlist
   * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
   *
   * Returns the extended tlist.
   */
  List *
  add_to_flat_tlist(List *tlist, List *exprs)
  {
  	int			next_resno = list_length(tlist) + 1;
  	ListCell   *lc;
  
  	foreach(lc, exprs)
  	{
  		Node	   *expr = (Node *) lfirst(lc);
  
  		if (!tlist_member(expr, tlist))
  		{
  			TargetEntry *tle;
  
  			tle = makeTargetEntry(copyObject(expr),		/* copy needed?? */
  								  next_resno++,
  								  NULL,
  								  false);
  			tlist = lappend(tlist, tle);
  		}
  	}
  	return tlist;
  }
  
  
  /*
   * get_tlist_exprs
   *		Get just the expression subtrees of a tlist
   *
   * Resjunk columns are ignored unless includeJunk is true
   */
  List *
  get_tlist_exprs(List *tlist, bool includeJunk)
  {
  	List	   *result = NIL;
  	ListCell   *l;
  
  	foreach(l, tlist)
  	{
  		TargetEntry *tle = (TargetEntry *) lfirst(l);
  
  		if (tle->resjunk && !includeJunk)
  			continue;
  
  		result = lappend(result, tle->expr);
  	}
  	return result;
  }
  
  
  /*
   * Does tlist have same output datatypes as listed in colTypes?
   *
   * Resjunk columns are ignored if junkOK is true; otherwise presence of
   * a resjunk column will always cause a 'false' result.
   *
   * Note: currently no callers care about comparing typmods.
   */
  bool
  tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
  {
  	ListCell   *l;
  	ListCell   *curColType = list_head(colTypes);
  
  	foreach(l, tlist)
  	{
  		TargetEntry *tle = (TargetEntry *) lfirst(l);
  
  		if (tle->resjunk)
  		{
  			if (!junkOK)
  				return false;
  		}
  		else
  		{
  			if (curColType == NULL)
  				return false;	/* tlist longer than colTypes */
  			if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
  				return false;
  			curColType = lnext(curColType);
  		}
  	}
  	if (curColType != NULL)
  		return false;			/* tlist shorter than colTypes */
  	return true;
  }
  
  /*
   * Does tlist have same exposed collations as listed in colCollations?
   *
   * Identical logic to the above, but for collations.
   */
  bool
  tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
  {
  	ListCell   *l;
  	ListCell   *curColColl = list_head(colCollations);
  
  	foreach(l, tlist)
  	{
  		TargetEntry *tle = (TargetEntry *) lfirst(l);
  
  		if (tle->resjunk)
  		{
  			if (!junkOK)
  				return false;
  		}
  		else
  		{
  			if (curColColl == NULL)
  				return false;	/* tlist longer than colCollations */
  			if (exprCollation((Node *) tle->expr) != lfirst_oid(curColColl))
  				return false;
  			curColColl = lnext(curColColl);
  		}
  	}
  	if (curColColl != NULL)
  		return false;			/* tlist shorter than colCollations */
  	return true;
  }
  
  
  /*
   * get_sortgroupref_tle
   *		Find the targetlist entry matching the given SortGroupRef index,
   *		and return it.
   */
  TargetEntry *
  get_sortgroupref_tle(Index sortref, List *targetList)
  {
  	ListCell   *l;
  
  	foreach(l, targetList)
  	{
  		TargetEntry *tle = (TargetEntry *) lfirst(l);
  
  		if (tle->ressortgroupref == sortref)
  			return tle;
  	}
  
  	elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
  	return NULL;				/* keep compiler quiet */
  }
  
  /*
   * get_sortgroupclause_tle
   *		Find the targetlist entry matching the given SortGroupClause
   *		by ressortgroupref, and return it.
   */
  TargetEntry *
  get_sortgroupclause_tle(SortGroupClause *sgClause,
  						List *targetList)
  {
  	return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
  }
  
  /*
   * get_sortgroupclause_expr
   *		Find the targetlist entry matching the given SortGroupClause
   *		by ressortgroupref, and return its expression.
   */
  Node *
  get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
  {
  	TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);
  
  	return (Node *) tle->expr;
  }
  
  /*
   * get_sortgrouplist_exprs
   *		Given a list of SortGroupClauses, build a list
   *		of the referenced targetlist expressions.
   */
  List *
  get_sortgrouplist_exprs(List *sgClauses, List *targetList)
  {
  	List	   *result = NIL;
  	ListCell   *l;
  
  	foreach(l, sgClauses)
  	{
  		SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
  		Node	   *sortexpr;
  
  		sortexpr = get_sortgroupclause_expr(sortcl, targetList);
  		result = lappend(result, sortexpr);
  	}
  	return result;
  }
  
  
  /*****************************************************************************
   *		Functions to extract data from a list of SortGroupClauses
   *
   * These don't really belong in tlist.c, but they are sort of related to the
   * functions just above, and they don't seem to deserve their own file.
   *****************************************************************************/
  
  /*
   * extract_grouping_ops - make an array of the equality operator OIDs
   *		for a SortGroupClause list
   */
  Oid *
  extract_grouping_ops(List *groupClause)
  {
  	int			numCols = list_length(groupClause);
  	int			colno = 0;
  	Oid		   *groupOperators;
  	ListCell   *glitem;
  
  	groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
  
  	foreach(glitem, groupClause)
  	{
  		SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
  
  		groupOperators[colno] = groupcl->eqop;
  		Assert(OidIsValid(groupOperators[colno]));
  		colno++;
  	}
  
  	return groupOperators;
  }
  
  /*
   * extract_grouping_cols - make an array of the grouping column resnos
   *		for a SortGroupClause list
   */
  AttrNumber *
  extract_grouping_cols(List *groupClause, List *tlist)
  {
  	AttrNumber *grpColIdx;
  	int			numCols = list_length(groupClause);
  	int			colno = 0;
  	ListCell   *glitem;
  
  	grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
  
  	foreach(glitem, groupClause)
  	{
  		SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
  		TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
  
  		grpColIdx[colno++] = tle->resno;
  	}
  
  	return grpColIdx;
  }
  
  /*
   * grouping_is_sortable - is it possible to implement grouping list by sorting?
   *
   * This is easy since the parser will have included a sortop if one exists.
   */
  bool
  grouping_is_sortable(List *groupClause)
  {
  	ListCell   *glitem;
  
  	foreach(glitem, groupClause)
  	{
  		SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
  
  		if (!OidIsValid(groupcl->sortop))
  			return false;
  	}
  	return true;
  }
  
  /*
   * grouping_is_hashable - is it possible to implement grouping list by hashing?
   *
   * We rely on the parser to have set the hashable flag correctly.
   */
  bool
  grouping_is_hashable(List *groupClause)
  {
  	ListCell   *glitem;
  
  	foreach(glitem, groupClause)
  	{
  		SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
  
  		if (!groupcl->hashable)
  			return false;
  	}
  	return true;
  }
  