//
// See the file LICENSE for redistribution information.
//
// Copyright (c) 2002-2003
//	Sleepycat Software.  All rights reserved.
//
// $Id: QueryPlan.hpp,v 1.69 2003/12/10 23:27:56 merrells Exp $
//

#ifndef __QUERYPLAN_HPP
#define	__QUERYPLAN_HPP

#include <memory>
#include <string>

#if defined(DBXML_XPATH_PATHAN)
class XPathExpression;
class XPathNSResolver;
#endif

#include "scoped_ptr.hpp"
#include "shared_ptr.hpp"
#include "IDS.hpp"
#include "Key.hpp"
#include "NamespaceMap.hpp"
#include "VariableBindings.hpp"
#include "KeyStatistics.hpp"
#include "Value.hpp"

using namespace std;

namespace DbXml
{

// forward declarations
class QueryPlan;
class QueryPlanNode;
class QueryPlanWalker;
class Container;
class HighResTimer;
class Key;
class XmlQueryContext;
class QueryContext;

/**
 * This function pointer declaration is used by the
 * QueryExecutionContext class to declare a callback
 * to a cost calculation function. There is a feedback
 * mechanism within the query plan execution engine
 * so that candidate set construction can be short
 * circuited once it becomes cheaper to filter.
 */
typedef double (*CostFunctionPointer)(long numDocuments);

/**
 * QueryExecutionContext
 *
 * Note that the costTofilter mechanism below is provided so that
 * during evaluation a query plan node can compare the cost of
 * refining the candidate set further, or giving up and allowing
 * the documents to be retrieved and filtered through a complete
 * XPath to DOM implementation.
 */
class QueryExecutionContext
{
public:
	QueryExecutionContext(const Container &container, QueryContext &context, bool debugging);
	~QueryExecutionContext();
	const Container &getContainer() const;
	void setCostToFilterFunction(CostFunctionPointer cfp);
	double costToFilter(const IDS::SharedPtr &ids) const;
	string toString() const;
	void addExecutionStep(const string &step);
	string getExecutionPath() const;
	const NamespaceMap *getNamespaceMap() const;
	const VariableBindings *getVariableBindings() const;
	QueryContext &getContext() const
	{
		return context;
	}
	bool debugging() const
	{
		return debugging_;
	}
private:
	// no need for copy and assignment
	QueryExecutionContext(const QueryExecutionContext&);
	QueryExecutionContext &operator=(const QueryExecutionContext &);

	const Container &container;
	QueryContext &context;
	CostFunctionPointer costToFilterPointer;

	// For debugging, and testing, keep track of the execution path.
	bool debugging_;
	string executionPath_;
};

/**
 * QueryPlan
 *
 * The base of the class hierarchy used to represent a query plan.
 * The plan describes how a search is to be made against a document
 * container.
 *
 * See 'Optimization of Query Evaluation Algorithms, S. Bing Yao,
 * ACMTODS Vol 4 No 2 June 1979' for background information.
 *
 * The user should call execute to generate a candidate set of
 * document IDs, then call the iteration interface method next()
 * to iterate over the candidate/resultant values.
 */
class QueryPlan
{
public:
	typedef shared_ptr<QueryPlan> SharedPtr; ///< A reference counted pointer to a Query Plan.
	enum Type
	{
	    // Intermediate Query Plan Nodes
	    //
	    AND,
	    OR,
	    GLUE,
	    STEP,
	    PROJECT,
	    //
	    // Query Plan Operators
	    //
	    ROOT,  ///< Returns XmlResults
	    SET_OPERATION_UNION,  ///< Returns IDS
	    SET_OPERATION_INTERSECTION,  ///< Returns IDS
	    RESTRICTION_INDEXING,  ///< Returns IDS
	    RECORD_ACCESS,  ///< Returns Documents
	    METADATA_ACCESS,  ///< Returns XmlResults, containing non-Document Values
	    SEQUENTIAL_SCAN,  ///< Returns IDS
	    RESTRICTION_FILTER,  ///< Returns XmlResults, containing Documents
	    RESTRICTION_FILTER_AND_PROJECT,  ///< Returns XmlResults, containing non-Document Values
	    CONSTANT,  ///< Returns XmlResults
	    GET_DOCUMENT,  ///< Returns a Document
	    ANY = -1
	};
	enum ReturnType
	{
	    RETURNTYPE_ALL,  ///< The query plan returns all the documents in the container.
	    RETURNTYPE_RESULTSET,  ///< The query plan returns a set of documents that contain only matching documents.
	    RETURNTYPE_CANDIDATESET,  ///< The query plan returns a set of documents that contain the matching documents as a proper subset.
	    RETURNTYPE_NONE,  ///< The query plan returns an empty set.
	    RETURNTYPE_INHERIT ///< Node inherits return type from the left and right nodes.
	};
	QueryPlan(Type type);
	virtual ~QueryPlan();
	/**
	 * \brief Reset the query plan before execution.
	 *
	 * This method is called on the root node of the query plan tree
	 * and the exceute call cascades through the whole tree.
	 */
	virtual void reset();
	/**
	 * \brief Generate the candidate set of document IDs.
	 *
	 * This method is called on the root node of the query plan tree
	 * and the exceute call cascades through the whole tree. At each
	 * node the candidate id set is determined and passed back to the
	 * parent.
	 *
	 * Query Plans can be reused, so an implementation of execute() must
	 * tidy up any state left over for next().
	 *
	 * Note that there are BDB calls in some implementations of execute,
	 * so execute could throw.
	 *
	 * \param txn The transaction within which the query is performed.
	 * \param qec The context within which the query is executed.
	 * \param ids The ID set returned to the caller.
	 */
	int execute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	/**
	 * \brief Return the next value.
	 *
	 * Provides an iteration interface over the query results.
	 *
	 * \param qc The Query Context within which the query is performed.
	 * \param value The Xmlvalue returned to the caller.
	 * \return error code
	 */
	virtual int next(QueryContext &qc, XmlValue &value);
	/// Estimate the cost execution in terms of pages accessed.
	double cost(OperationContext &context, QueryExecutionContext &qec);
	/// Optimize the query plan.
	virtual int optimize(DbTxn *txn, const Container &container, XmlQueryContext &context, const IndexSpecification &indexSpecification, int phase);
	/// Estimate the number of values in the result set.
	virtual size_t getResultSize() const
	{
		return 0;
	}
	/// Return the type of query plan.
	Type getType() const
	{
		return type_;
	}
	/// Return the type of return type this query plan has.
	virtual ReturnType getReturnType() const
	{
		return returnType_;
	}
	/// Set the type of return type this query plan has.
	void setReturnType(const ReturnType &returnType)
	{
		returnType_ = returnType;
	}
	/// Test if the query plan is of this type. Static to deal with null pointer.
	static bool is(const QueryPlan::SharedPtr &qp, const Type &type);
	/// Return the rightmost query plan in the subtree.
	virtual QueryPlan &rightmost() { return *this; }
	/// For debgging, render the query plan as a string.
	virtual string toString() const = 0;
	/// Look for a particular type of query plan in the subtree.
	virtual bool contains(const Type &type) const
	{
		return getType()==type;
	}
protected:
	/// For debugging, get the return type as a string.
	std::string getReturnTypeAsString() const;
	/// The return type of this query plan.
	ReturnType returnType_;

private:
	// no need for copy and assignment
	QueryPlan(const QueryPlan&);
	QueryPlan &operator=(const QueryPlan &);

	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids) = 0;
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);
	virtual const char *moniker() const
	{
		return 0;
	}

	Type type_;
	bool costCalculated_;
	double executionCost_; ///< We cache the cost, as multiple calls are made to cost.
};

/**
 * QueryPlanNode
 *
 * A base class for representing query plan nodes that bring
 * together two other query plans.
 */
class QueryPlanNode : public QueryPlan
{
public:
	QueryPlanNode(Type type, QueryPlan::SharedPtr a, QueryPlan::SharedPtr b);
	virtual ~QueryPlanNode();
	void setLeft(QueryPlan::SharedPtr a);
	void setRight(QueryPlan::SharedPtr b);
	QueryPlan::SharedPtr getLeft();
	QueryPlan::SharedPtr getRight();
	QueryPlan::SharedPtr takeLeft();
	QueryPlan::SharedPtr takeRight();
	const QueryPlan::SharedPtr getLeft() const;
	const QueryPlan::SharedPtr getRight() const;
	string leftToString() const;
	string rightToString() const;
	void replace(QueryPlan::SharedPtr original, QueryPlan::SharedPtr replacement);
	// QueryPlan
	virtual void reset();
	virtual int optimize(DbTxn *txn, const Container &container, XmlQueryContext &context, const IndexSpecification &indexSpecification, int phase);
	virtual QueryPlan &rightmost();
	virtual bool contains(const Type &type) const
	{
		return (getType()==type) || (l_ && l_->contains(type)) || (r_ && r_->contains(type));
	}

private:
	QueryPlan::SharedPtr optimize_node(DbTxn *txn, const Container &container, XmlQueryContext &context, int phase, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int &rulesApplied);
	QueryPlan::SharedPtr optimize_node_phase_one(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int &rulesApplied);
	QueryPlan::SharedPtr optimize_node_phase_two(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int &rulesApplied);
	QueryPlan::SharedPtr optimize_node_phase_three(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, int &rulesApplied);
	QueryPlan::SharedPtr optimize_node_p2r2(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification);
	QueryPlan::SharedPtr optimize_node_p2r4(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification);
	QueryPlan::SharedPtr optimize_node_p2r5(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification);
	QueryPlan::SharedPtr optimize_node_p2r6(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification, int nameIndex, bool edge);
	QueryPlan::SharedPtr optimize_node_presence(DbTxn *txn, const Container &container, XmlQueryContext &context, const QueryPlan::SharedPtr &me, const IndexSpecification &indexSpecification, int nameIndex, bool edge);
	QueryPlan::SharedPtr optimize_node_p2r3(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification);
	QueryPlan::SharedPtr optimize_node_p2r8(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification);
	QueryPlan::SharedPtr optimize_node_p2r9(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, const IndexSpecification &indexSpecification);
	QueryPlan::SharedPtr optimize_node_equality(DbTxn *txn, const Container &container, XmlQueryContext &context, const QueryPlan::SharedPtr &me, const IndexSpecification &indexSpecification, int nameIndex, bool edge, QueryPlan::ReturnType returnType);
	QueryPlan::SharedPtr optimize_node_phase_four(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, int &rulesApplied);
	bool optimize_node_p4r4(QueryPlan::SharedPtr lm, QueryPlan::SharedPtr rc);
	QueryPlan::SharedPtr optimize_node_phase_five(DbTxn *txn, const Container &container, XmlQueryContext &context, QueryPlan::SharedPtr me, int &rulesApplied);

	void logRuleApplication(const Container &container, const char *ruleName, const QueryPlan *original, const QueryPlan *replacement) const;
	void outputToDebug(const Container &container, const char *msg, QueryPlan *qp) const;

	QueryPlan::SharedPtr l_; ///< Left
	QueryPlan::SharedPtr r_; ///< Right
};

//
// RootQP
//
class RootQP : public QueryPlanNode
{
public:
	RootQP(QueryPlan::SharedPtr qp);
	// QueryPlan
	virtual string toString() const;
	virtual int optimize(DbTxn *txn, const Container &container, XmlQueryContext &context, const IndexSpecification &indexSpecification, int phase);
	virtual int next(QueryContext &qc, XmlValue &value);
	virtual size_t getResultSize() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
};

//
// SetOperationUnionQP
//
class SetOperationUnionQP : public QueryPlanNode
{
public:
	SetOperationUnionQP(QueryPlan::SharedPtr a, QueryPlan::SharedPtr b);
	// QueryPlan
	virtual string toString() const;
	virtual ReturnType getReturnType() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);
	virtual const char *moniker() const
	{
		return "u ";
	}
	void execute_union(QueryExecutionContext &qec);
};

//
// SetOperationIntersectionQP
//
class SetOperationIntersectionQP : public QueryPlanNode
{
public:
	SetOperationIntersectionQP(QueryPlan::SharedPtr a, QueryPlan::SharedPtr b);
	// QueryPlanNode
	virtual string toString() const;
	virtual ReturnType getReturnType() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);
	virtual const char *moniker() const
	{
		return "n ";
	}
	void execute_intersection(QueryExecutionContext &qec);
};

//
// RestrictionIndexingQP
//
class RestrictionIndexingQP : public QueryPlan
{
public:
	RestrictionIndexingQP(Index index, Database::Operation operation, const string &name1);
	RestrictionIndexingQP(Index index, Database::Operation operation, const string &name1, const string &name2);
	RestrictionIndexingQP(Index index, Database::Operation operation, const string &name1, const XmlValue &value1);
	RestrictionIndexingQP(Index index, const string &name1, Database::Operation gto, const XmlValue &value1, Database::Operation lto, const XmlValue &value2);

	void setValue1(const XmlValue &value1)
	{
		value1_ = value1;
	}
	void setName2(const string &name2)
	{
		name2_ = name2;
	}
	const string &getName1() const
	{
		return name1_;
	}
	const XmlValue &getValue1() const
	{
		return value1_;
	}
	Index getIndex() const
	{
		return index_;
	}
	Database::Operation getOperation() const
	{
		return operation_;
	}

	// QueryPlan
	virtual void reset();
	virtual string toString() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);
	virtual const char *moniker() const
	{
		return "RI";
	}
	void createKeys(DbTxn *txn, QueryExecutionContext &qec);
	void createKey(DbTxn *txn, Key &key, const Container &container, QueryContext &context, XmlValue &value);

	Index index_;
	Database::Operation operation_;
	Database::Operation lessThanOperation_;
	Database::Operation greaterThanOperation_;
	string name1_;
	string name2_;
	XmlValue value1_;
	XmlValue value2_;
	bool keysCreated_;
	Key key1_;
	Key key2_;
	KeyStatistics statistics_;
	double numberOfKeys_;
};

//
// SequentialScanQP
//
class SequentialScanQP : public QueryPlan
{
public:
	SequentialScanQP();
	// QueryPlan
	virtual string toString() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);
	virtual const char *moniker() const
	{
		return "SS";
	}
};

//
// RecordAccessQP
//
class RecordAccessQP : public QueryPlanNode
{
public:
	RecordAccessQP(QueryPlan::SharedPtr qp);
	virtual ~RecordAccessQP();
	// QueryPlan
	virtual string toString() const;
	virtual void reset();
	virtual int next(QueryContext &qc, XmlValue &value);
	virtual size_t getResultSize() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);

	const Container *container_;
	IDS::SharedPtr ids_;
	IDS::const_iterator *pids_;
	HighResTimer *afTimer_;
};

//
// GetDocumentQP
//
class GetDocumentQP : public QueryPlanNode
{
public:
	GetDocumentQP(u_int32_t id );
	virtual ~GetDocumentQP();
	// QueryPlan
	virtual string toString() const;
	virtual size_t getResultSize() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);

	const Container *container_;
	u_int32_t id_;
};

//
// MetaDataAccessQP
//
class MetaDataAccessQP : public QueryPlanNode
{
public:
	MetaDataAccessQP(const string &name);
	virtual ~MetaDataAccessQP();
	// QueryPlan
	virtual string toString() const;
	virtual void reset();
	virtual int next(QueryContext &qc, XmlValue &value);
	virtual size_t getResultSize() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);

	const Container *container_;
	string name_;
	ID nid_;
	IDS::SharedPtr ids_;
	IDS::const_iterator *pids_;
};

/**
 * RestrictionFilterAndOrProjectQP
 *
 * Filters the candidate documents to remove the false positives,
 * and, if requested, will project the XPath expression over the
 * Document to produce a resultant Value.
 */
class RestrictionFilterAndOrProjectQP : public QueryPlanNode
{
public:
	RestrictionFilterAndOrProjectQP(const string& xpath, QueryPlan::SharedPtr qp, bool project);
	virtual ~RestrictionFilterAndOrProjectQP();
	void setProject(bool project)
	{
		project_ = project;
	}
	// QueryPlan
	virtual int next(QueryContext &qc, XmlValue &value);
	virtual size_t getResultSize() const;
	static double costToFilter(long numDocuments);
	virtual string toString() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	virtual double doCost(OperationContext &context, QueryExecutionContext &qec);
	bool applyFilter(QueryContext &qc, const XmlDocument &document, XmlValueVector &vv);

	const Container *container_;
	const string xpath_;
	bool project_;
	IDS::SharedPtr ids_;
	XmlValueVector vv_;
	XmlValueVector::iterator vvi_;
	HighResTimer *afTimer_;
	HighResTimer *afdTimer_;

#if defined(DBXML_XPATH_PATHAN)
	XERCES_CPP_NAMESPACE_QUALIFIER DOMDocument *nsDocument_;
	XPathNSResolver *docNSResolver_;
	XPathExpression *parsedExpression_;
#endif
};

//
// ConstantQP
//
class ConstantQP : public QueryPlan
{
public:
	ConstantQP() : QueryPlan(QueryPlan::CONSTANT), done_(false)
	{}
	ConstantQP(const XmlValue &v) : QueryPlan(QueryPlan::CONSTANT), done_(false), v_(v)
	{}
	virtual ~ConstantQP();
	const XmlValue &getValue() const
	{
		return v_;
	}
	void setValue(const XmlValue &v)
	{
		v_ = v;
	}
	void setBoolean(bool b)
	{
		v_ = b;
	}
	void setNumber(double d)
	{
		v_ = d;
	}
	void setString(const string &s)
	{
		v_ = s;
	}
	// QueryPlan
	virtual void reset();
	virtual int next(QueryContext &qc, XmlValue &value);
	virtual string toString() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	bool done_; // Used by next() to make sure the value is only returned once.
	XmlValue v_;
};

//
// PlaceHolderQP
//
class PlaceHolderQP : public QueryPlanNode
{
public:
	PlaceHolderQP(Type type, const string &name);
	PlaceHolderQP(Type type, const string &name, QueryPlan::SharedPtr a, QueryPlan::SharedPtr b);
	// QueryPlan
	virtual string toString() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	string name_;
};

/**
 * StepQP
 *
 * Operations: equality, inequality, range, prefix
 */
class StepQP : public QueryPlan
{
public:
	enum Axis
	{
	    AXIS_NONE,
	    //		AXIS_ANCESTOR,
	    //		AXIS_ANCESTOR_OR_SELF,
	    AXIS_ATTRIBUTE,
	    AXIS_CHILD,
	    //		AXIS_DESCENDANT,
	    //		AXIS_DESCENDANT_OR_SELF,
	    //		AXIS_FOLLOWING,
	    //		AXIS_FOLLOWING_SIBLING,
	    //		AXIS_NAMESPACE,
	    //		AXIS_PARENT,
	    //		AXIS_PRECEDING,
	    //		AXIS_PRECEDING_SIBLING,
	    //		AXIS_SELF,
	    AXIS_OTHER
	};
	StepQP(Database::Operation operation, const XmlValue &value);
	StepQP(const string &axis, const string &n1, const string &n2);
	void setValue(const XmlValue &value)
	{
		value_ = value;
	}
	void setAxis(Axis axis)
	{
		this->axis_ = axis;
	}
	Axis getAxis() const
	{
		return axis_;
	}
	const string &getName(unsigned int index = 0) const;
	vector<string> getNames() const
	{
		return names_;
	}
	XmlValue getValue() const
	{
		return value_;
	}
	void addName(const string &name);
	void addNames(const vector<string> &names);
	int countNames() const
	{
		return names_.size();
	}
	void setOperation(Database::Operation operation)
	{
		operation_ = operation;
	}
	Database::Operation getOperation() const
	{
		return operation_;
	}
	bool isAnywhere() const
	{
		return anywhere_;
	}
	void setAnywhere(bool anywhere)
	{
		anywhere_ = anywhere;
	}
	void setContextNode(bool contextNode) { contextNode_= contextNode; }
	bool isContextNode() const { return contextNode_; }
	// QueryPlan
	virtual string toString() const;
private:
	virtual int doExecute(OperationContext &context, QueryExecutionContext &qec, IDS::SharedPtr &ids);
	Axis axis_;
	Database::Operation operation_;
	vector<string> names_;
	XmlValue value_;
	// The node can appear anywhere in the document. ie. //*[foo]
	bool anywhere_;
	// The step is a reference to the context node. ie /foo/text(), or /foo[text()]
	bool contextNode_;
};

}

#endif

