/afs/cs.wisc.edu/u/n/w/nwilliam/private/workspace/Quut/src/parser/SqlParser.h

//
// Author: Jignesh M. Patel
//         EECS Department, University of Michigan
// Date:   August 2000
//

#ifndef SQL_PARSE_H
#define SQL_PARSE_H

#include <iostream>
#include <cstring>
#include <cassert>
#include "types.h"

using namespace std;
using namespace badgerdb;

class PxxInterp;
//
// Class encapsulating the Parser support routines
//
// TODO: Pre-allocate an array for each of the Parser Node Types and allocate
//       entries from this array. The allocation of various parser nodes in sqlparser.y
//       could slow down query compilation time considerably.
// TODO: Purify!
//
class PxxParser
{
public:
   static const char* Prompt;
};

//
// Base type for all parser classes
//
class PxxPnode 
{
public:
   
   // The different types of nodes
   enum NodeType 
   {
      Query,
         Create,
         CreateIndex,
         Delete,
         Drop,
         DropIndex,
         Insert,
         AttrName,
         AggrFunc,
         RelName,
         DataType,
         AttrType,
         Value,
         List,
         Predicate,
         PredTree,
         Literal
   };
   
   // Returns the node type
   virtual NodeType MyType() const = 0;
   
   // Print a description of this class instance
   virtual void Write (ostream& os) const 
   {
      os << "Node type: " << (unsigned) MyType();
   };
   
   virtual ~PxxPnode() {};
   // TODO: Add a method typecheck to consult the catalogs and type check the parse nodes.
   // virtual bool TypeCheck() const = 0; 
};

class PxxList; //dummy definition to satiate the compiler

// Generic list node class.
class ListNode
{
   friend class PxxList;
public:
   ListNode(PxxPnode* n) {_data = n; _next = 0;}
   void Write (ostream& os) const   {_data->Write(os);}
   ~ListNode() {if (_data) delete _data;}
   PxxPnode* Data() {return _data;} 
   ListNode* Next() 
   {
      return _next;   
   } 
   
private:
   PxxPnode*   _data;
   ListNode*   _next;
};
//
// Generic list of PxxNodes
//
class PxxList : public PxxPnode
{
public:
   
   PxxList(PxxPnode* n) 
   {
      _head = new ListNode(n);
      _tail = _head;
      _card = 1;
   }
   
   PxxList() {_head = 0; _tail = 0; _card = 0;} 
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return List;}
   void Write (ostream& os) const;
   
   // Add a node 
   PxxList* Add(PxxPnode* n);
   
   // Destructor
   ~PxxList();
   
   unsigned Cardinality() {return _card;}
   
   // get first, used for quickly decting star shorthand in the select list
   ListNode* First() 
   {
      if(_head)
         return _head;
      return 0;
   }

   // iterator
   ListNode* Init() 
   {
      _pos = _head;
      if(_head)
         return _head;
      return 0;
   }
   
   ListNode* Next() 
   {
      if(!_pos) return 0;
      _pos=_pos->_next;
      if (_pos)
         return _pos;
      return 0;
   }
   
private:
   ListNode*   _head;
   ListNode*   _tail;
   ListNode*   _pos;
   unsigned    _card;
};

inline PxxList* PxxList::Add(PxxPnode* n)
{
   if (!_head)
   {
      _head = new ListNode(n);
      _tail = _head;
   }
   else
   {
      _tail->_next = new ListNode(n);
      _tail = _tail->_next;
   }
   
   _card++;
   return this;
}

inline void PxxList::Write (ostream& os) const
{
   const ListNode* cur = _head;
   unsigned idx = 0;
   while (cur)
   {
      os << endl << "\t\t-" << idx++ << "- ";
      cur->Write(os);
      cur = cur->_next;
   }
}

inline PxxList::~PxxList()
{
   ListNode* next;
   ListNode* cur = _head;
   
   while (cur)
   {
      // cout << "Deleting node: "; cur->Write(cout); cout << endl;
      next = cur->_next;
      delete cur;
      cur = next;
   }
}

// 
// SQL data type parse node descriptor
//
class PxxDataType : public PxxPnode
{ 
   
public:
   enum DataType {
         INTEGER=0,
         DOUBLE=1,
         STRING=2
   };
   PxxDataType(DataType type, int param1 = 0, int param2 = 0)
   {
      _type = type;
      _param1 = param1;
      _param2 = param2;
   }
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::DataType;}
   DataType Type() {return _type;} 
   void Write (ostream& os) const;
   
protected:
   DataType _type;
   int _param1, _param2;
};

inline void PxxDataType::Write (ostream& os) const
{
   os << "Type: " << (unsigned) _type ;
   if (_param1) os << "(" << _param1;
   if (_param2) os<< "." << _param2;
   if (_param1) os << ")";
   os << " ";
}

// 
// SQL AttrType parse node; used when parsing create table commands
// 
class PxxAttrType : public PxxDataType
{
public:
   PxxAttrType(DataType type, int param1 = 0, int param2 = 0) 
      : PxxDataType(type, param1, param2), _attrName(0) {}
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::AttrType;}
   void Write (ostream& os) const;
   
   void SetAttrName (char* aname) {_attrName = aname;};
   
   char* AttrName() {return _attrName;}
   DataType Type() {return _type;}
   int  Param1() {return _param1;}
   int  Param2() {return _param2;}
   
private:
   char* _attrName;  // The name of the attribute being created
};

inline void PxxAttrType::Write (ostream& os) const
{
   if (_attrName) os << _attrName << ", ";
   PxxDataType::Write(os);
}

//
// Parse node describing a Relation name with references
// 
class PxxRelName : public PxxPnode
{
public:
   PxxRelName(char* rel, char* ref = 0) : _rel(rel), _ref(ref) {};   
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::RelName;}
   void Write (ostream& os) const;
   
   char* RelName() const { return _rel;}
   char* RefName() const { return _ref;}
   
   void SetRelName(char* rel) {_rel = rel;}
   
private:
   char* _rel;  // The relation name
   char* _ref;  // The name used to refer to this relation in the query
};

inline void PxxRelName::Write (ostream& os) const
{
   os << "RelName: " << _rel;
   if (_ref) os << "(Ref:" << _ref << ")";
}


//
// Parse node describing an Attribute name with references
// 
class PxxAttrName : public PxxPnode
{
public:
   PxxAttrName(bool star) : _attr(0), _rel(0), _star(true), _copy(false) {};
   PxxAttrName(char* attr, char* rel = 0, bool copy = false) : 
                     _attr(attr), _rel(rel), _star(false), _copy(copy) 
   {
      if (copy) 
      {
         _attr = new char[strlen(attr)+1];
         strcpy (_attr, attr);
         _rel = new char[strlen(rel)+1];
         strcpy (_rel, rel);
      }
   }
   ~PxxAttrName() 
   {
      if (_copy)
      {
         delete [] _attr;
         delete [] _rel;
      }
   };
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::AttrName;}
   void Write (ostream& os) const;
   
   char* AttrName() {return _attr;}
   char* RelName() {return _rel;}
   bool Star() {return _star;}
   
private:
   char* _attr;  // The name of the attribute
   char* _rel;   // The name of the relation (may be empty)
   bool  _star;  // Denoting the "special" attribute "*"
   bool  _copy;  // are the attrnames and relnames copied here.
};


inline void PxxAttrName::Write (ostream& os) const
{
   if (_star) os << "*";
   else
   {
      if (_rel) os << _rel << "."; 
      os << _attr;
   }
}

//
// Parse node describing a Literal
// 
class PxxLiteral : public PxxDataType
{
public:
   PxxLiteral(void* lval, DataType type, int param1 = 0, int param2 = 0) 
      : PxxDataType(type, param1, param2)
   {
      _type = type;
      switch (type)
      {
      case STRING:
         {
            _lval.cval = (char*)lval;
            break;
         }
      case INTEGER: 
         {
            _lval.ival = *((int*)lval);
            break;
         }
         
      case DOUBLE:
         {
            _lval.dval = *((double*)lval);
            break;
         }
      default: assert (!"Invalid Data Type");
         
      }
   }
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::Literal;}
   void Write (ostream& os) const;
   
   int* Int() {return &_lval.ival;}
   double* Double() { return &_lval.dval;}
   char* Char() { return _lval.cval;}

   DataType LiteralType () const {return _type;}
   
private:
   DataType _type;

   union
   {
      int    ival;   // An integer literal value
      double dval;   // A real literal value
      char*  cval;   // A character literal value
   } _lval;
   
};

inline void PxxLiteral::Write (ostream& os) const
{
   // os << "Literal: ";
   PxxDataType::Write(os);
   os << ", Val: ";
   switch (_type)
   {
   case STRING:     os << _lval.cval; break;
   case INTEGER:  os << _lval.ival; break;         
   case DOUBLE:   os << _lval.dval; break;
   default: assert (!"Invalid Data Type");         
   }
}


// 
// SQL Aggregate Function parse node
// 
class PxxAggrFunc : public PxxPnode
{
public:
   enum AggrFunc   
   {
      Avg,
         Count,
         Min,
         Max,
         Sum
   };
   
   PxxAggrFunc(PxxAttrName* aname, AggrFunc afunc) : _func(afunc), _attr(aname) {}
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::AggrFunc;}
   void Write (ostream& os) const;
   ~PxxAggrFunc() {if (_attr) delete _attr;}
   
private:
   AggrFunc       _func;  // The aggregate function
   PxxAttrName*   _attr;  // The attribute being aggregated
};

inline void PxxAggrFunc::Write (ostream& os) const
{
   os << "AggrFunc: " << (unsigned) _func << ", ";
   _attr->Write(os);
}

//
// Parse node for create table statements
//
class PxxCreate : public PxxPnode
{
public:
   PxxCreate(char* rname, PxxList* alist, PxxList* plist=0)
   {
      _relName = rname;
      _attrList = alist;
      _primattrs = plist;
   }
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::Create;}
   void Write (ostream& os) const;
   ~PxxCreate() { if (_attrList) delete _attrList; }
   
   char* RelName() {return _relName;}
   PxxList* AttrList() {return _attrList;}
   PxxList* PrimAttrs() {return _primattrs;}
private:
   char*    _relName;   // The relation being created
   PxxList* _attrList;  // A list of PxxAttrTypes 
   PxxList* _primattrs;  // A list of PxxAttrNames denoting the primary 
   // attributes in the relation. If the primary key 
   // is a single attrubute than this list only has 
   // one element (for now assume only single attribute
   // primary keys)
};

inline void PxxCreate::Write (ostream& os) const
{
   os << "Create Table: " << _relName << "\t Attrlist "; _attrList->Write(os);
   if (_primattrs) 
   { 
      os << endl << "\tPrim Attrs: "; 
      _primattrs->Write(os);
   }
}

//
// Parse node for create index statements
//
class PxxCreateIndex : public PxxPnode
{
public:
   
   enum IndexType {
         Hash,
         Btree
   };
   
   PxxCreateIndex(char* rname, char* aname): _type(Hash), 
                                             _relName (rname),
                                             _attrName(aname) 
   {} 
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::CreateIndex;}
   void Write (ostream& os) const 
   {
      os << "Create Index: " << _relName << ", " << _attrName;
   }
   // ~PxxCreateIndex() {}

   char* RelName() const { return _relName;}
   char* AttrName() const { return _attrName;}

private:
   IndexType _type;  // The type of the index
   char* _relName;   // The relation being indexed
   char* _attrName;  // The attribute being indexed
};

//
// Parse node for insert statements
//
class PxxInsert : public PxxPnode
{
public:
   
   PxxInsert(char* rname, PxxList* optAttrList, PxxList* valueList)
   {
      _relName = rname;
      _extFileName = 0;
      _optAttrList = optAttrList;
      _valueList = valueList;
   }
   
   PxxInsert(char* rname, PxxList* optAttrList, char* extFileName)
   {
      _relName = rname;
      _extFileName = extFileName;
      _optAttrList = optAttrList;
      _valueList = 0;
   }
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::Insert;}
   void Write (ostream& os) const;
   ~PxxInsert();
   
   char* RelName() {return _relName;}
   char* FileName() 
   {
      if(_extFileName) return _extFileName;
      return 0;
   }
   PxxList* ValList() { return _valueList;}
   PxxList* OptList() 
   {
      if(_optAttrList) return _optAttrList;
      return 0;
   }
   
private:
   char* _relName;          // Insert into this relation
   char* _extFileName;      // Used only for bulk-inserts 
   PxxList* _valueList;     // A list of PxxLiteral 
   PxxList* _optAttrList;   // An optional list of PxxAttrName
};

inline PxxInsert::~PxxInsert()
{
   if (_valueList)   delete _valueList;
   if (_optAttrList) delete _optAttrList;
}

inline void PxxInsert::Write (ostream& os) const
{
   os << "Insert Command, Table: " << _relName;
   if (_optAttrList) 
   {
      os << endl;
      os << "\tAttrList: ";
      _optAttrList->Write(os);
   }
   
   if (_valueList) 
   {
      os << endl;
      os << "\tValueList: ";
      _valueList->Write(os);
   }
   
   if (_extFileName)  os << endl << "\tBulkload from: " << _extFileName;
}


//
// Parse node for drop table command
//
class PxxDrop : public PxxPnode
{
public:
   PxxDrop(char* rname) : _relName (rname) {}   
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::Drop;}
   void Write (ostream& os) const {os << "Drop Table: " << _relName;}

   // Return the name of the relation being dropped
   char* RelName() {return _relName;}
   
private:
   char* _relName;  // The relation being deleted
};

//
// Parse node for drop Index command
//
class PxxDropIndex : public PxxPnode
{
public:
   PxxDropIndex(char* rname, char* aname):_relName (rname),_attrName(aname) {} 
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::DropIndex;}
   void Write (ostream& os) const 
   {
      os << "Drop Index: " << _relName << ", " << _attrName;
   }
   
   char* RelName() const { return _relName;}
   char* AttrName() const { return _attrName;}

private:
   char* _relName;   // The relation being deleted
   char* _attrName;  // The attribute being indexed
};



class PxxQuery;

//
// A predicate expression. For now a literal or an attribute
// Note: This class is not a sub-class of PxxNode
//
class PxxPredExpr
{
public:
   enum ExprType 
   {
      Literal,
         Attribute,
         SubQuery    // Not supported
   };
   
   void Set(PxxPnode* exprVal); 
   void Write (ostream& os) const;
   ~PxxPredExpr();
   PxxLiteral* Lit() {return _val._literal;}
   PxxAttrName* AttrName() {return  _val._attr;}
   PxxQuery* Sub() {return  _val._subQuery;}
   ExprType Type() {return _type;}
private:
   ExprType _type;              // The type of the literal
   union
   {                            // An expression is either 
      PxxLiteral*  _literal;    //    a literal
      PxxAttrName* _attr;       // or an attribute 
      PxxQuery*    _subQuery;   // or a subquery (not yet supported)
   } _val;
};

inline void PxxPredExpr::Write (ostream& os) const 
{
   // os << "Expr: Type: " << (unsigned) _type << ", Val: " ;
   switch (_type)
   {
   case Literal:   _val._literal->Write(os); break;
   case Attribute: _val._attr->Write(os); break;
   default:        assert(!"Invalid PredExpr Type");
   }
}

inline PxxPredExpr::~PxxPredExpr()
{
   switch (_type)
   {
   case Literal:   delete _val._literal; break;
   case Attribute: delete _val._attr; break;
   default:        assert(!"Invalid PredExpr Type");
   }
}


//
// Parse node for Predicates
//
class PxxPredicate : public PxxPnode
{
public:
   // Legal SQL Comparison operations
   
   PxxPredicate(Operator op, bool notFlag=false) : _op (op), _not(notFlag) {}   
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::Predicate;}
   void Write (ostream& os) const;
   
   PxxPredExpr& operator[] (unsigned idx) 
   {
      assert (idx<2); 
      return _expr[idx];
   }
   
   void Set(PxxPnode* lVal, PxxPnode* rVal);
   ~PxxPredicate() {}
   Operator Oper() {return _op;}
   bool Not() {return _not;}
   PxxPredExpr* Expr() {return _expr;}
   
private:
   Operator       _op;      // Predicate operation
   bool        _not;     // indicate a negation of _op
   PxxPredExpr _expr[2]; // The l and h expression in the predicate 
   //  (assume binary ops only)
};


inline void PxxPredicate::Write (ostream& os) const 
{
   os << "Pred: ["; _expr[0].Write(os);
   os << "] [OP: " << _not << " " << (unsigned) _op << "] [";
   _expr[1].Write(os); os << "]";
}

inline void PxxPredicate::Set(PxxPnode* lVal, PxxPnode* rVal)
{
   _expr[0].Set(lVal);
   _expr[1].Set(rVal);
}


//
// Parse node for Predicates
//
class PxxPredTree : public PxxPnode
{
public:
   enum PredConnector 
   {
      AND,
         OR, 
         NOT   // Not supported.
   };
   
   PxxPredTree(PredConnector con = AND) : _con(con) {}
   PxxPredTree* AddPredicate (PredConnector con, PxxPnode* _newPred);
   
   // Definition of the pure virtual methods
   NodeType MyType() const {return PxxPnode::PredTree;}
   void Write (ostream& os) const;
   ~PxxPredTree() {}
   
   PredConnector Con() {return _con;}
   PxxList*  Preds() {return &_plist;}
   
private:
   PredConnector _con;   // The predicate connector
   
   // List of predicates. The elements in this list are either 
   // PxxPredicate (for a list of predicates connected by only AND or only OR)
   // or PxxPredTeee (for a mix of and/or predicates)
   PxxList   _plist;
   
   static PredConnector Negate(PredConnector con)
   {
      switch (con)
      {
      case AND: return OR;
      case OR: return AND;
      default: assert (!"Not supported");
      }
      return con;
   }
};

inline PxxPredTree* PxxPredTree::AddPredicate (PredConnector con, PxxPnode* _newPred)
{
   if (con == _con)
   {
      // Simply add to the predicate list
      _plist.Add(_newPred);
      return this;
   }
   else if (con == Negate(_con))
   {
      PxxPredTree* newTree = new PxxPredTree(con);
      newTree->_plist.Add(this);
      newTree->_plist.Add(_newPred);
      return newTree;
   }
   else assert (!"Predicate not supported");
   
   return this;
}

inline void PxxPredTree::Write (ostream& os) const 
{
   os << "PredTree, Connector: " << (unsigned) _con;
   _plist.Write (os);
}


//
// Parse node for a Query
//
class PxxQuery : public PxxPnode
{
public:
   PxxQuery (PxxList* proj, PxxList* from)
      : _relname(0), _projList(proj), _fromList(from), _preds(0), _group(0), _having(0) {};
   
   // Add various clauses of an SQL statement
   void AddWhere(PxxPredTree* preds);
   void AddGroupBy(PxxList* grpBy);
   void AddHaving(PxxPredTree* preds); 
   void AddInsertInto(char* relname); 
   
   // Definition of the pure virtual methods
   NodeType MyType() const { return PxxPnode::Query;}
   void Write (ostream& os) const;
   
   ~PxxQuery();
   
   PxxRelName &RelName() { return _relname; }
   PxxList* Projs() { return _projList; }
   PxxList* Froms() { return _fromList; }
   PxxPredTree* Preds() { return _preds; }
   PxxList* Groups() { return _group; }
   PxxPredTree* Havings() { return _having; }
   
protected:
   PxxRelName   _relname;  // The relation to insert into. 
   PxxList*     _projList; // A list of PxxAttrName and PxxAggrFunc. 
   // This list represents the attributes and 
   // aggregates specified in the select clause.
   PxxList*     _fromList; // A list of PxxRelName, from the from clause
   PxxPredTree* _preds;    // A PxxPredTree corresponding to the where clause
   PxxList*     _group;    // The list of PxxAttrName in the group by clause
   PxxPredTree* _having;   // A PxxPredTree corresponding to the having clause
};

inline void PxxQuery::AddWhere(PxxPredTree* preds) 
{
   _preds = preds;
}

inline void PxxQuery::AddGroupBy(PxxList* grpBy) 
{
   _group = grpBy;
}

inline void PxxQuery::AddHaving(PxxPredTree* preds) 
{
   _having = preds;
}

inline void PxxQuery::AddInsertInto(char* relname) 
{
   _relname.SetRelName(relname);
}

inline void PxxQuery::Write (ostream& os) const 
{
   os << "Query:\tProj: "; _projList->Write(os);
   os << endl << "\tFrom: "; _fromList->Write(os);
   if (_preds)
   {
      os << endl << "\tWhere: "; 
      _preds->Write(os);
   }
   if (_group)
   {
      os << endl << "\tGrpBy: "; 
      _group->Write(os);
   }
   if (_having)
   {
      os << endl << "\tHaving: "; 
      _having->Write(os);
   }
   
   if (_relname.RelName())
   {
      os << endl << "\tInsert into: " ; 
      _relname.Write(os);
   }
}

inline PxxQuery::~PxxQuery()
{
   if (_projList)    delete _projList;
   if (_fromList)    delete _fromList;
   if (_preds)       delete _preds;
   if (_group)       delete _group;
   if (_having)      delete _having;
}

class PxxDelete : public PxxQuery
{
public:
   PxxDelete(PxxList *from) : PxxQuery (0, from) {};
   NodeType MyType() const { return PxxPnode::Delete;}
   void Write (ostream& os) const;
};

inline void PxxDelete::Write (ostream& os) const 
{
   os << "Delete:\tFrom: "; _fromList->Write(os);
   if (_preds)
   {
      os << endl << "\tWhere: "; 
      _preds->Write(os);
   }
}



inline ostream& operator<< (ostream& os, const PxxPnode& n)
{
   n.Write(os);
   return os;
}

#endif