/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the utils of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#ifndef LALR_H

#define LALR_H

#include <functional>

#include <QtCore/QSet>

#include <QtCore/QStack>

#include <QtCore/QMap>

#include <QtCore/QLinkedList>

#include <QtCore/QString>

#include <QtCore/QTextStream>

#include <QtCore/QPair>

class Rule;

class State;

class Grammar;

class Item;

class State;

class Arrow;

class Automaton;

template <typename _Tp >

class OrderedSet : protected QMap<_Tp, bool>

{

  typedef QMap<_Tp, bool> _Base;

public:

  class const_iterator

  {

    typename _Base::const_iterator _M_iterator;

  public:

    const_iterator () {}

    const_iterator (const typename _Base::const_iterator &it):

      _M_iterator (it) {}

    const _Tp &operator * () const

    { return _M_iterator.key (); }

    const _Tp *operator -> () const

    { return &_M_iterator.key (); }

    const_iterator &operator ++ ()

    { ++_M_iterator; return *this; }

    const_iterator operator ++ (int) const

    {

      const_iterator me (*this);

      ++_M_iterator;

      return me;

    }

    bool operator == (const const_iterator &other) const

    { return _M_iterator == other._M_iterator; }

    bool operator != (const const_iterator &other) const

    { return _M_iterator != other._M_iterator; }

  };

  typedef const_iterator iterator;

public:

  OrderedSet () {}

  const_iterator begin () const

  { return const_iterator (_Base::begin ()); }

  const_iterator end () const

  { return const_iterator (_Base::end ()); }

  bool isEmpty () const

  { return _Base::isEmpty (); }

  int size () const

  { return _Base::size (); }

  const_iterator find (const _Tp &elt) const

  { return const_iterator (_Base::find (elt)); }

  QPair<const_iterator, bool> insert (const _Tp &elt)

  {

    int elts = _Base::size ();

    const_iterator it (_Base::insert (typename _Base::key_type (elt), true));

    return qMakePair (it, elts != _Base::size ());

  }

  QPair<const_iterator, bool> insert (const_iterator, const _Tp &elt)

  {

    int elts = _Base::size ();

    const_iterator it (_Base::insert (typename _Base::key_type (elt), true));

    return qMakePair (it, elts != _Base::size ());

  }

  const _Tp &operator [] (const _Tp &elt)

  { return *insert (elt)->first; }

  template <typename _InputIterator>

  void insert (_InputIterator first, _InputIterator last)

  {

    for (; first != last; ++first)

      insert (*first);

  }

};

// names

typedef QLinkedList<QString>::iterator Name;

typedef QLinkedList<Name> NameList;

typedef OrderedSet<Name> NameSet;

// items

typedef QLinkedList<Item> ItemList;

typedef ItemList::iterator ItemPointer;

// rules

typedef QLinkedList<Rule> debug_infot;

typedef debug_infot::iterator RulePointer;

typedef QMultiMap<Name, RulePointer> RuleMap;

// states

typedef QLinkedList<State> StateList;

typedef StateList::iterator StatePointer;

// arrows

typedef QMap<Name, StatePointer> Bundle;

class Rule

{

public:

  void clear ()

  {

    lhs = Name ();

    rhs.clear ();

    prec = Name ();

  }

public:

  Name lhs;

  NameList rhs;

  Name prec;

};

class Lookback

{

public:

  Lookback (StatePointer s, Name n):

    state (s), nt (n) {}

  inline bool operator == (const Lookback &other) const

  { return state == other.state && nt == other.nt; }

  inline bool operator != (const Lookback &other) const

  { return state != other.state || nt != other.nt; }

  bool operator < (const Lookback &other) const;

public:

  StatePointer state;

  Name nt;

};

class Item

{

public:

  inline NameList::iterator begin_rhs () const

  { return rule->rhs.begin (); }

  inline NameList::iterator end_rhs () const

  { return rule->rhs.end (); }

  inline bool operator == (const Item &other) const

  { return rule == other.rule && dot == other.dot; }

  inline bool operator != (const Item &other) const

  { return rule != other.rule || dot != other.dot; }

  inline bool isReduceItem () const

  { return dot == rule->rhs.end (); }

  Item next () const;

public:

  RulePointer rule;

  NameList::iterator dot;

};

class State

{

public:

  State (Grammar *grammar);

  inline bool operator == (const State &other) const

  { return kernel == other.kernel; }

  inline bool operator != (const State &other) const

  { return kernel != other.kernel; }

  QPair<ItemPointer, bool> insert (const Item &item);

  QPair<ItemPointer, bool> insertClosure (const Item &item);

public: // attributes

  ItemList kernel;

  ItemList closure;

  Bundle bundle;

  QMap<Name, NameSet> reads;

  QMap<Name, NameSet> follows;

  RulePointer defaultReduce;

};

/////////////////////////////////////////////////////////////

// digraph

/////////////////////////////////////////////////////////////

template <typename _Tp>

class Node

{

public:

  typedef OrderedSet<Node<_Tp> > Repository;

  typedef typename Repository::iterator iterator;

  typedef typename QLinkedList<iterator>::iterator edge_iterator;

public:

  static iterator get (_Tp data);

  QPair<edge_iterator, bool> insertEdge (iterator other) const;

  inline edge_iterator begin () const

  { return outs.begin (); }

  inline edge_iterator end () const

  { return outs.end (); }

  inline bool operator == (const Node<_Tp> &other) const

  { return data == other.data; }

  inline bool operator != (const Node<_Tp> &other) const

  { return data != other.data; }

  inline bool operator < (const Node<_Tp> &other) const

  { return data < other.data; }

  static inline iterator begin_nodes ()

  { return repository ().begin (); }

  static inline iterator end_nodes ()

  { return repository ().end (); }

  static Repository &repository ()

  {

    static Repository r;

    return r;

  }

public: // attributes

  mutable bool root;

  mutable int dfn;

  mutable _Tp data;

  mutable QLinkedList<iterator> outs;

protected:

  inline Node () {}

  inline Node (_Tp d):

    root (true), dfn (0), data (d) {}

};

template <typename _Tp>

typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data)

{

  Node<_Tp> tmp (data);

  iterator it = repository ().find (tmp);

  if (it != repository ().end ())

    return it;

  return repository ().insert (tmp).first;

}

template <typename _Tp>

QPair<typename QLinkedList<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge (typename Node<_Tp>::iterator other) const

{

  edge_iterator it = qFind (outs.begin (), outs.end (), other);

  if (it != outs.end ())

    return qMakePair (it, false);

  other->root = false;

  return qMakePair (outs.insert (outs.end (), other), true);

}

/////////////////////////////////////////////////////////////

// Grammar

/////////////////////////////////////////////////////////////

class Grammar

{

public:

  Grammar ();

  Name intern (const QString &id);

  inline bool isTerminal (Name name) const

  { return terminals.find (name) != terminals.end (); }

  inline bool isNonTerminal (Name name) const

  { return non_terminals.find (name) != non_terminals.end (); }

  void buildRuleMap ();

  void buildExtendedGrammar ();

public:

  QString merged_output;

  QString table_name;

  QString decl_file_name;

  QString impl_file_name;

  QString token_prefix;

  QLinkedList<QString> names;

  Name start;

  NameSet terminals;

  NameSet non_terminals;

  QMap<Name, QString> spells;

  debug_infot rules;

  RuleMap rule_map;

  RulePointer goal;

  Name tk_end;

  Name accept_symbol;

  NameSet declared_lhs;

  int expected_shift_reduce;

  int expected_reduce_reduce;

  enum Assoc {

    NonAssoc,

    Left,

    Right

  };

  struct TokenInfo {

    Assoc assoc;

    int prec;

  };

  QMap<Name, TokenInfo> token_info;

  Assoc current_assoc;

  int current_prec;

};

class Read

{

public:

  inline Read () {}

  inline Read (StatePointer s, Name n):

    state (s), nt (n) {}

  inline bool operator == (const Read &other) const

  { return state == other.state && nt == other.nt; }

  inline bool operator != (const Read &other) const

  { return state != other.state || nt != other.nt; }

  bool operator < (const Read &other) const;

public:

  StatePointer state;

  Name nt;

};

class Include

{

public:

  inline Include () {}

  inline Include (StatePointer s, Name n):

    state (s), nt (n) {}

  inline bool operator == (const Include &other) const

  { return state == other.state && nt == other.nt; }

  inline bool operator != (const Include &other) const

  { return state != other.state || nt != other.nt; }

  bool operator < (const Include &other) const;

public:

  StatePointer state;

  Name nt;

};

class Automaton

{

public:

  Automaton (Grammar *g);

  QPair<StatePointer, bool> internState (const State &state);

  typedef Node<Read> ReadsGraph;

  typedef ReadsGraph::iterator ReadNode;

  typedef Node<Include> IncludesGraph;

  typedef IncludesGraph::iterator IncludeNode;

  void build ();

  void buildNullables ();

  void buildLookbackSets ();

  void buildDirectReads ();

  void buildReadsDigraph ();

  void buildReads ();

  void visitReadNode (ReadNode node);

  void buildIncludesAndFollows ();

  void buildIncludesDigraph ();

  void visitIncludeNode (IncludeNode node);

  void buildLookaheads ();

  void buildDefaultReduceActions ();

  void closure (StatePointer state);

  int id (RulePointer rule);

  int id (StatePointer state);

  int id (Name name);

  void dump (QTextStream &out, IncludeNode incl);

  void dump (QTextStream &out, ReadNode rd);

  void dump (QTextStream &out, const Lookback &lp);

public: // ### private

  Grammar *_M_grammar;

  StateList states;

  StatePointer start;

  NameSet nullables;

  QMultiMap<ItemPointer, Lookback> lookbacks;

  QMap<ItemPointer, NameSet> lookaheads;

private:

  QStack<ReadsGraph::iterator> _M_reads_stack;

  int _M_reads_dfn;

  QStack<IncludesGraph::iterator> _M_includes_stack;

  int _M_includes_dfn;

};

QT_BEGIN_NAMESPACE

bool operator < (Name a, Name b);

bool operator < (StatePointer a, StatePointer b);

bool operator < (ItemPointer a, ItemPointer b);

QT_END_NAMESPACE

QTextStream &operator << (QTextStream &out, const Name &n);

QTextStream &operator << (QTextStream &out, const Rule &r);

QTextStream &operator << (QTextStream &out, const Item &item);

QTextStream &operator << (QTextStream &out, const NameSet &ns);

QT_BEGIN_NAMESPACE

// ... hmm

extern QTextStream qerr;

extern QTextStream qout;

QT_END_NAMESPACE

#endif // LALR_H