/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the utils of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:GPL-EXCEPT$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3 as published by the Free Software
** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/

#ifndef LALR_H
#define LALR_H

#include <QtCore/qset.h>
#include <QtCore/qstack.h>
#include <QtCore/qmap.h>
#include <QtCore/qlinkedlist.h>
#include <QtCore/qstring.h>
#include <QtCore/qtextstream.h>
#include <QtCore/qpair.h>

#include <algorithm>
#include <functional>
#include <set>

class Rule;
class State;
class Grammar;
class Item;
class State;
class Arrow;
class Automaton;


// names
typedef std::list<QString>::iterator Name;
typedef std::list<Name> NameList;
typedef std::set<Name> NameSet;

// items
typedef std::list<Item> ItemList;
typedef ItemList::iterator ItemPointer;

// rules
typedef std::list<Rule> debug_infot;
typedef debug_infot::iterator RulePointer;
typedef QMultiMap<Name, RulePointer> RuleMap;

// states
typedef std::list<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 std::set<Node<_Tp> > Repository;
  typedef typename Repository::iterator iterator;
  typedef typename std::list<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 std::list<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 std::list<typename Node<_Tp>::iterator>::iterator, bool> Node<_Tp>::insertEdge(typename Node<_Tp>::iterator other) const
{
  edge_iterator it = std::find (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);
  Name intern (const char *id) { return intern(QString::fromUtf8(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;
  std::list<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;
};

namespace std {
bool operator < (Name a, Name b);
bool operator < (StatePointer a, StatePointer b);
bool operator < (ItemPointer a, ItemPointer b);
}

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
QTextStream &qerr();
QTextStream &qout();
QT_END_NAMESPACE

#endif // LALR_H