//---------------------------------------------------------------------------
//	Greenplum Database
//	Copyright 2011 EMC Corp.
//
//	@filename:
//		CPredicateUtils.h
//
//	@doc:
//		Utility functions for normalizing scalar predicates
//---------------------------------------------------------------------------
#ifndef GPOPT_CPredicateUtils_H
#define GPOPT_CPredicateUtils_H

#include "gpos/base.h"

#include "gpopt/base/CUtils.h"
#include "gpopt/mdcache/CMDAccessor.h"
#include "gpopt/operators/CExpression.h"
#include "gpopt/operators/CScalarBoolOp.h"
#include "gpopt/operators/CScalarIdent.h"
#include "naucrates/md/IMDIndex.h"

namespace gpopt
{
using namespace gpos;

// fwd decl
class CConstraintInterval;

//---------------------------------------------------------------------------
//	@class:
//		CPredicateUtils
//
//	@doc:
//		Utility functions for normalizing scalar predicates
//
//---------------------------------------------------------------------------
class CPredicateUtils
{
private:
	// collect conjuncts recursively
	static void CollectConjuncts(CExpression *pexpr,
								 CExpressionArray *pdrgpexpr);

	// collect disjuncts recursively
	static void CollectDisjuncts(CExpression *pexpr,
								 CExpressionArray *pdrgpexpr);

	// check if a conjunct/disjunct can be skipped
	static BOOL FSkippable(CExpression *pexpr, BOOL fConjunction);

	// check if a conjunction/disjunction can be reduced to a constant True/False
	static BOOL FReducible(CExpression *pexpr, BOOL fConjunction);

	// check if given expression is a comparison over the given column
	static BOOL FComparison(CExpression *pexpr, CColRef *colref,
							CColRefSet *pcrsAllowedRefs);

	// check whether the given expression contains references to only the given
	// columns. If pcrsAllowedRefs is NULL, then check whether the expression has
	// no column references and no volatile functions
	static BOOL FValidRefsOnly(CExpression *pexprScalar,
							   CColRefSet *pcrsAllowedRefs);

	// determine which predicates we should test implication for
	static BOOL FCheckPredicateImplication(CExpression *pexprPred);

	// check if predicate is implied by given equivalence classes
	static BOOL FImpliedPredicate(CExpression *pexprPred,
								  CColRefSetArray *pdrgpcrsEquivClasses);

	// helper to create index lookup comparison predicate with index key on left side
	static CExpression *PexprIndexLookupKeyOnLeft(
		CMemoryPool *mp, CMDAccessor *md_accessor, CExpression *pexprScalar,
		const IMDIndex *pmdindex, CColRefArray *pdrgpcrIndex,
		CColRefSet *outer_refs, BOOL allowArrayCmpIndexQual);

	// helper to create index lookup comparison predicate with index key on right side
	static CExpression *PexprIndexLookupKeyOnRight(
		CMemoryPool *mp, CMDAccessor *md_accessor, CExpression *pexprScalar,
		const IMDIndex *pmdindex, CColRefArray *pdrgpcrIndex,
		CColRefSet *outer_refs, BOOL allowArrayCmpIndexQual);

	// for all columns that appear in the given expression and are members
	// of the given set, replace these columns with NULL constants
	static CExpression *PexprReplaceColsWithNulls(CMemoryPool *mp,
												  CExpression *pexprScalar,
												  CColRefSet *pcrs);

public:
	// private dtor
	virtual ~CPredicateUtils() = delete;

	// private ctor
	CPredicateUtils() = delete;

	CPredicateUtils(const CPredicateUtils &) = delete;

	// reverse the comparison, for example "<" => ">", "<=" => "=>
	static IMDType::ECmpType EcmptReverse(IMDType::ECmpType cmp_type);

	// check if the expression is a boolean scalar identifier
	static BOOL FBooleanScalarIdent(CExpression *pexprPred);

	// check if the expression is a negated boolean scalar identifier
	static BOOL FNegatedBooleanScalarIdent(CExpression *pexprPred);

	// is the given expression an equality comparison
	static BOOL IsEqualityOp(CExpression *pexpr);

	// is the given expression a scalar comparison
	static BOOL FComparison(CExpression *pexpr);

	// is the given expression a conjunction of equality comparisons
	static BOOL FConjunctionOfEqComparisons(CMemoryPool *mp,
											CExpression *pexpr);

	// is the given expression a comparison of the given type
	static BOOL FComparison(CExpression *pexpr, IMDType::ECmpType cmp_type);

	// is the given array of expressions contain a volatile function like random()
	static BOOL FContainsVolatileFunction(CExpressionArray *pdrgpexpr);

	// is the given expressions contain a volatile function like random()
	static BOOL FContainsVolatileFunction(CExpression *pexpr);

	// is the given expression an equality comparison over two scalar identifiers
	static BOOL FPlainEquality(CExpression *pexpr);

	// is the given expression a self comparison on some column
	static BOOL FSelfComparison(CExpression *pexpr, IMDType::ECmpType *pecmpt,
								CColRefSet *pcrsNotNull);

	// eliminate self comparison if possible
	static CExpression *PexprEliminateSelfComparison(CMemoryPool *mp,
													 CExpression *pexpr,
													 CColRefSet *pcrsNotNull);

	// is the given expression in the form (col1 Is NOT DISTINCT FROM col2)
	static BOOL FINDFScalarIdents(CExpression *pexpr);

	// is the given expression in the form (col1 IS DISTINCT FROM col2)
	static BOOL FIDFScalarIdents(CExpression *pexpr);

	// check if expression is an Is DISTINCT FROM FALSE expression
	static BOOL FIDFFalse(CExpression *pexpr);

	static BOOL FCompareScalarIdentToConstAndScalarIdentArray(
		CExpression *pexpr);

	// is the given expression in the form (expr IS DISTINCT FROM expr)
	static BOOL FIDF(CExpression *pexpr);

	// is the given expression in the form (expr IS NOT DISTINCT FROM expr)
	static BOOL FINDF(CExpression *pexpr);

	// generate a conjunction of INDF expressions between corresponding columns in the given arrays
	static CExpression *PexprINDFConjunction(CMemoryPool *mp,
											 CColRefArray *pdrgpcrFirst,
											 CColRefArray *pdrgpcrSecond);

	// is the given expression of the form (col CMP/IS DISTINCT/IS NOT DISTINCT FROM constant)
	// either the constant or the column can be casted
	static BOOL FIdentCompareConstIgnoreCast(CExpression *pexpr,
											 COperator::EOperatorId);

	// check if a given expression is a comparison between a column and an expression
	// using only constants and one or more outer references from a given ColRefSet,
	// it optionally returns the colref of the local table
	static BOOL FIdentCompareOuterRefExprIgnoreCast(
		CExpression *pexpr, CColRefSet *pcrsOuterRefs,
		CColRef **localColRef = nullptr);

	// is the given expression a comparison between scalar ident and a const array
	// either the ident or constant array can be casted
	static BOOL FArrayCompareIdentToConstIgnoreCast(CExpression *pexpr);

	// is the given expression of the form (col IS DISTINCT FROM constant)
	// either the constant or the column can be casted
	static BOOL FIdentIDFConstIgnoreCast(CExpression *pexpr);

	// is the given expression of the form NOT (col IS DISTINCT FROM constant)
	// either the constant or the column can be casted
	static BOOL FIdentINDFConstIgnoreCast(CExpression *pexpr);

	// is the given expression a comparison between a scalar ident and a constant
	static BOOL FCompareIdentToConst(CExpression *pexpr);

	// is the given expression an equality between ident/const without cast
	static BOOL FPlainEqualityIdentConstWithoutCast(CExpression *pexpr);

	// is the given expression a comparison between a const and a const
	static BOOL FCompareConstToConstIgnoreCast(CExpression *pexpr);

	// is the given expression of the form (col IS DISTINCT FROM const)
	static BOOL FIdentIDFConst(CExpression *pexpr);

	static BOOL FEqIdentsOfSameType(CExpression *pexpr);

	// checks if comparison is between two columns, or a column and a const
	static BOOL FCompareColToConstOrCol(CExpression *pexprScalar);

	// is the given expression a comparison between a scalar ident under a scalar cast and a constant array
	static BOOL FCompareCastIdentToConstArray(CExpression *pexpr);

	// is the given expression a comparison between a scalar ident and a constant array
	static BOOL FCompareIdentToConstArray(CExpression *pexpr);

	// is the given ScalarArrayCmp a valid index qual
	static BOOL IsScalarArrayCmpValidIndexQual(CExpression *pexpr,
											   CColRefArray *pdrgpcrIndex);

	// is the given expression an AND
	static BOOL
	FAnd(CExpression *pexpr)
	{
		return CUtils::FScalarBoolOp(pexpr, CScalarBoolOp::EboolopAnd);
	}

	// is the given expression an OR
	static BOOL
	FOr(CExpression *pexpr)
	{
		return CUtils::FScalarBoolOp(pexpr, CScalarBoolOp::EboolopOr);
	}

	// does the given expression have any NOT children?
	// is the given expression a NOT
	static BOOL
	FNot(CExpression *pexpr)
	{
		return CUtils::FScalarBoolOp(pexpr, CScalarBoolOp::EboolopNot);
	}

	// returns true iff the given expression is a Not operator whose child is a
	// scalar identifier
	static BOOL FNotIdent(CExpression *pexpr);

	// does the given expression have any NOT children?
	static BOOL FHasNegatedChild(CExpression *pexpr);

	// is the given expression an inner join or NAry join
	static BOOL
	FInnerOrNAryJoin(CExpression *pexpr)
	{
		return COperator::EopLogicalInnerJoin == pexpr->Pop()->Eopid() ||
			   COperator::EopLogicalNAryJoin == pexpr->Pop()->Eopid();
	}

	static BOOL
	FLeftOuterJoin(CExpression *pexpr)
	{
		return COperator::EopLogicalLeftOuterJoin == pexpr->Pop()->Eopid();
	}

	// is the given expression either a union or union all operator
	static BOOL
	FUnionOrUnionAll(CExpression *pexpr)
	{
		return COperator::EopLogicalUnion == pexpr->Pop()->Eopid() ||
			   COperator::EopLogicalUnionAll == pexpr->Pop()->Eopid();
	}

	// check if we can collapse the nth child of the given union / union all operator
	static BOOL FCollapsibleChildUnionUnionAll(CExpression *pexprParent,
											   ULONG child_index);

	// if the nth child of the given union/union all expression is also an union / union all expression,
	// then collect the later's children and set the input columns of the new n-ary union/unionall operator
	static void CollectGrandChildrenUnionUnionAll(
		CMemoryPool *mp, CExpression *pexpr, ULONG child_index,
		CExpressionArray *pdrgpexprResult, CColRef2dArray *pdrgdrgpcrResult);

	// extract conjuncts from a scalar tree
	static CExpressionArray *PdrgpexprConjuncts(CMemoryPool *mp,
												CExpression *pexpr);

	// extract disjuncts from a scalar tree
	static CExpressionArray *PdrgpexprDisjuncts(CMemoryPool *mp,
												CExpression *pexpr);

	// extract equality predicates on scalar identifier from a list of scalar expressions
	static CExpressionArray *PdrgpexprPlainEqualities(
		CMemoryPool *mp, CExpressionArray *pdrgpexpr);

	// create conjunction/disjunction
	static CExpression *PexprConjDisj(CMemoryPool *mp,
									  CExpressionArray *Pdrgpexpr,
									  BOOL fConjunction);

	// create conjunction/disjunction of two expressions
	static CExpression *PexprConjDisj(CMemoryPool *mp, CExpression *pexprOne,
									  CExpression *pexprTwo, BOOL fConjunction);

	// create conjunction
	static CExpression *PexprConjunction(CMemoryPool *mp,
										 CExpressionArray *pdrgpexpr);

	// create conjunction of two expressions
	static CExpression *PexprConjunction(CMemoryPool *mp, CExpression *pexprOne,
										 CExpression *pexprTwo);

	// create disjunction of two expressions
	static CExpression *PexprDisjunction(CMemoryPool *mp, CExpression *pexprOne,
										 CExpression *pexprTwo);

	// expand disjuncts in the given array by converting ArrayComparison to AND/OR tree and deduplicating resulting disjuncts
	static CExpressionArray *PdrgpexprExpandDisjuncts(
		CMemoryPool *mp, CExpressionArray *pdrgpexprDisjuncts);

	// expand conjuncts in the given array by converting ArrayComparison to AND/OR tree and deduplicating resulting conjuncts
	static CExpressionArray *PdrgpexprExpandConjuncts(
		CMemoryPool *mp, CExpressionArray *pdrgpexprConjuncts);

	// check if the given expression is a boolean expression on the
	// given column, e.g. if its of the form "ScalarIdent(colref)" or
	// "Not(ScalarIdent(colref))"
	static BOOL FBoolPredicateOnColumn(CExpression *pexpr, CColRef *colref);

	// check if the given expression is a scalar array cmp expression on the
	// given column
	static BOOL FScArrayCmpOnColumn(CExpression *pexpr, CColRef *colref,
									BOOL fConstOnly);

	// check if the given expression is a null check on the given column
	// i.e. "is null" or "is not null"
	static BOOL FNullCheckOnColumn(CExpression *pexpr, CColRef *colref);

	// check if the given expression of the form "col is not null"
	static BOOL FNotNullCheckOnColumn(CExpression *pexpr, CColRef *colref);

	// create disjunction
	static CExpression *PexprDisjunction(CMemoryPool *mp,
										 CExpressionArray *Pdrgpexpr);

	static CExpression *ValidatePartPruningExpr(CMemoryPool *mp,
												CExpression *expr,
												CColRef *pcrPartKey,
												CColRefSet *pcrsAllowedRefs,
												BOOL allow_not_equals_preds);

	// find a predicate that can be used for partition pruning with the given part key
	static CExpression *PexprPartPruningPredicate(
		CMemoryPool *mp, const CExpressionArray *pdrgpexpr, CColRef *pcrPartKey,
		CExpression *pexprCol, CColRefSet *pcrsAllowedRefs,
		BOOL allowNotEqualPreds);

	// append the conjuncts from the given expression to the given array, removing
	// any duplicates, and return the resulting array
	static CExpressionArray *PdrgpexprAppendConjunctsDedup(
		CMemoryPool *mp, CExpressionArray *pdrgpexpr, CExpression *pexpr);

	// extract interesting conditions involving the partitioning keys
	static CExpression *PexprExtractPredicatesOnPartKeys(
		CMemoryPool *mp, CExpression *pexprScalar,
		CColRef2dArray *pdrgpdrgpcrPartKeys, CColRefSet *pcrsAllowedRefs,
		BOOL fUseConstraints, const IMDRelation *pmdrel = nullptr);

	// checks if the operator belongs to the column's opfamily
	static BOOL FOpInOpfamily(CColRef *colref, CExpression *pexpr,
							  IMDIndex::EmdindexType access_method);

	// checks if the operator belongs to the scalar expression's opfamily
	static BOOL FOpInOpfamily(CExpression *pexprScalar, CExpression *pexpr,
							  IMDIndex::EmdindexType access_method);

	// checks if the operator belongs to the column's opfamily
	static BOOL FOpInOpfamily(IMDId *col_mdid, CExpression *pexpr,
							  IMDIndex::EmdindexType access_method);

	// extract the constraint on the given column and return the corresponding
	// scalar expression
	static CExpression *PexprPredicateCol(CMemoryPool *mp, CConstraint *pcnstr,
										  CColRef *colref,
										  BOOL fUseConstraints);

	// extract components of a comparison expression on the given key
	static void ExtractComponents(CExpression *pexprScCmp, CColRef *pcrKey,
								  CExpression **ppexprKey,
								  CExpression **ppexprOther,
								  IMDType::ECmpType *pecmpt);

	// Expression is a comparison with a simple identifer on at least one side
	static BOOL FIdentCompare(CExpression *pexpr, IMDType::ECmpType pecmpt,
							  CColRef *colref);

	// check if given column is a constant
	static BOOL FConstColumn(CConstraint *pcnstr, const CColRef *colref);

	// check if given column is a disjunction of constants
	static BOOL FColumnDisjunctionOfConst(CConstraint *pcnstr,
										  const CColRef *colref);

	// check if given column is a disjunction of constants
	static BOOL FColumnDisjunctionOfConst(CConstraintInterval *pcnstr,
										  const CColRef *colref);

	// split predicates into those that refer to an index key, and those that don't
	static void ExtractIndexPredicates(
		CMemoryPool *mp, CMDAccessor *md_accessor,
		CExpressionArray *pdrgpexprPredicate, const IMDIndex *pmdindex,
		CColRefArray *pdrgpcrIndex, CExpressionArray *pdrgpexprIndex,
		CExpressionArray *pdrgpexprResidual, ULONG &ulUnindexedPredColCount,
		CColRefSet *pcrsAcceptedOuterRefs =
			nullptr,  // outer refs that are acceptable in an index predicate
		BOOL allowArrayCmpIndexQual = false);

	// return the inverse of given comparison expression
	static CExpression *PexprInverseComparison(CMemoryPool *mp,
											   CExpression *pexprCmp);

	// prune unnecessary equality operations
	static CExpression *PexprPruneSuperfluosEquality(CMemoryPool *mp,
													 CExpression *pexpr);

	// remove conjuncts that are implied based on child columns equivalence classes
	static CExpression *PexprRemoveImpliedConjuncts(CMemoryPool *mp,
													CExpression *pexprScalar,
													CExpressionHandle &exprhdl);

	//	check if given correlations are valid for semi join operator;
	static BOOL FValidSemiJoinCorrelations(
		CMemoryPool *mp, CExpression *pexprOuter, CExpression *pexprInner,
		CExpressionArray *pdrgpexprCorrelations);

	// check if given expression is composed of simple column equalities that use columns from given column set
	static BOOL FSimpleEqualityUsingCols(CMemoryPool *mp,
										 CExpression *pexprScalar,
										 CColRefSet *pcrs);

	// check if given expression is a valid index lookup predicate
	// return (modified) predicate suited for index lookup
	static CExpression *PexprIndexLookup(
		CMemoryPool *mp, CMDAccessor *md_accessor, CExpression *pexpPred,
		const IMDIndex *pmdindex, CColRefArray *pdrgpcrIndex,
		CColRefSet *outer_refs, BOOL allowArrayCmpIndexQual);

	// split given scalar expression into two conjunctions; without and with outer references
	static void SeparateOuterRefs(CMemoryPool *mp, CExpression *pexprScalar,
								  CColRefSet *outer_refs,
								  CExpression **ppexprLocal,
								  CExpression **ppexprOuterRef);

	// is the condition a LIKE predicate
	static BOOL FLikePredicate(IMDId *mdid);

	// is the condition a LIKE predicate
	static BOOL FLikePredicate(CExpression *pexprPred);

	// extract the components of a LIKE predicate
	static void ExtractLikePredComponents(CExpression *pexprPred,
										  CExpression **ppexprScIdent,
										  CExpression **ppexprConst);

	// check if scalar expression is null-rejecting and uses columns from given column set
	static BOOL FNullRejecting(CMemoryPool *mp, CExpression *pexprScalar,
							   CColRefSet *pcrs);

	// returns true iff the given predicate pexprPred is compatible with the given index pmdindex
	static BOOL FCompatibleIndexPredicate(CExpression *pexprPred,
										  const IMDIndex *pmdindex,
										  CColRefArray *pdrgpcrIndex,
										  CMDAccessor *md_accessor);

	// returns true iff all predicates in the given array are compatible with the given index
	static BOOL FCompatiblePredicates(CExpressionArray *pdrgpexprPred,
									  const IMDIndex *pmdindex,
									  CColRefArray *pdrgpcrIndex,
									  CMDAccessor *md_accessor);

	// check if the expensive CNF conversion is beneficial in finding predicate for hash join
	static BOOL FConvertToCNF(CExpression *pexpr, CExpression *pexprOuter,
							  CExpression *pexprInner);

	// check if the predicate is a simple scalar cmp or a simple conjuct that can be used directly
	// for bitmap index looup without breaking it down.
	static BOOL FBitmapLookupSupportedPredicateOrConjunct(
		CExpression *pexpr, CColRefSet *outer_refs);

	// Check if a given comparison operator is "very strict", meaning that it is strict
	// (NULL operands result in NULL result) and that it never produces a NULL result on
	// non-null operands. Note that this check may return false negatives (some operators
	// may have very strict behavior, yet this method returns false).
	static BOOL FBuiltInComparisonIsVeryStrict(IMDId *mdid);

	// Check if the given expr only contains conjuncts of strict comparison operators
	// NB: This does NOT recurse into Boolean AND/OR operations
	static BOOL ExprContainsOnlyStrictComparisons(CMemoryPool *mp,
												  CExpression *expr);

	// Check if the given exprs only contains conjuncts of strict comparison operators
	// NB: This does NOT recurse into Boolean AND/OR operations
	static BOOL ExprsContainsOnlyStrictComparisons(CExpressionArray *conjuncts);

};	// class CPredicateUtils
}  // namespace gpopt


#endif	// !GPOPT_CPredicateUtils_H

// EOF
