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

**

** Copyright (C) 2009 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$

**

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

#include "lalr.h"

#include <limits.h>

#include <algorithm>

#define QLALR_NO_DEBUG_NULLABLES

#define QLALR_NO_DEBUG_LOOKBACKS

#define QLALR_NO_DEBUG_DIRECT_READS

#define QLALR_NO_DEBUG_READS

#define QLALR_NO_DEBUG_INCLUDES

#define QLALR_NO_DEBUG_LOOKAHEADS

QT_BEGIN_NAMESPACE

QTextStream qerr (stderr, QIODevice::WriteOnly);

QTextStream qout (stdout, QIODevice::WriteOnly);

bool operator < (Name a, Name b)

{

    return *a < *b;

}

bool operator < (ItemPointer a, ItemPointer b)

{

    return &*a < &*b;

}

bool operator < (StatePointer a, StatePointer b)

{

  return &*a < &*b;

}

QT_END_NAMESPACE

bool Read::operator < (const Read &other) const

{

  if (state == other.state)

    return nt < other.nt;

  return state < other.state;

}

bool Include::operator < (const Include &other) const

{

  if (state == other.state)

    return nt < other.nt;

  return state < other.state;

}

bool Lookback::operator < (const Lookback &other) const

{

  if (state == other.state)

    return nt < other.nt;

  return state < other.state;

}

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

{

  return out << *n;

}

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

{

  out << *r.lhs << " ::=";

  for (NameList::const_iterator name = r.rhs.begin (); name != r.rhs.end (); ++name)

    out << " " << **name;

  return out;

}

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

{

  out << "{";

  for (NameSet::const_iterator n = ns.begin (); n != ns.end (); ++n)

    {

      if (n != ns.begin ())

        out << ", ";

      out << *n;

    }

  return out << "}";

}

Item Item::next () const

{

  Q_ASSERT (! isReduceItem ());

  Item n;

  n.rule = rule;

  n.dot = dot;

  ++n.dot;

  return n;

}

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

{

  RulePointer r = item.rule;

  out << *r->lhs << ":";

  for (NameList::iterator name = r->rhs.begin (); name != r->rhs.end (); ++name)

    {

      out << " ";

      if (item.dot == name)

        out << ". ";

      out << **name;

    }

  if (item.isReduceItem ())

    out << " .";

  return out;

}

State::State (Grammar *g):

  defaultReduce (g->rules.end ())

{

}

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

{

  ItemPointer it = qFind (kernel.begin (), kernel.end (), item);

  if (it != kernel.end ())

    return qMakePair (it, false);

  return qMakePair (kernel.insert (it, item), true);

}

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

{

  ItemPointer it = qFind (closure.begin (), closure.end (), item);

  if (it != closure.end ())

    return qMakePair (it, false);

  return qMakePair (closure.insert (it, item), true);

}

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

// Grammar

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

Grammar::Grammar ():

    start (names.end ())

{

  expected_shift_reduce = 0;

  expected_reduce_reduce = 0;

  current_prec = 0;

  current_assoc = NonAssoc;

  table_name = QLatin1String ("parser_table");

  tk_end = intern ("$end");

  terminals.insert (tk_end);

  spells.insert (tk_end, "end of file");

  /*tk_error= terminals.insert (intern ("error"))*/;

}

Name Grammar::intern (const QString &id)

{

  Name name = qFind (names.begin (), names.end (), id);

  if (name == names.end ())

    name = names.insert (names.end (), id);

  return name;

}

void Grammar::buildRuleMap ()

{

  NameSet undefined;

  for (RulePointer rule = rules.begin (); rule != rules.end (); ++rule)

    {

      for (NameList::iterator it = rule->rhs.begin (); it != rule->rhs.end (); ++it)

        {

          Name name = *it;

          if (isTerminal (name) || declared_lhs.find (name) != declared_lhs.end ()

              || undefined.find (name) != undefined.end ())

            continue;

          undefined.insert(name);

          fprintf (stderr, "*** Warning. Symbol `%s' is not defined\n", qPrintable (*name));

        }

      rule_map.insert (rule->lhs, rule);

    }

}

void Grammar::buildExtendedGrammar ()

{

  accept_symbol = intern ("$accept");

  goal = rules.insert (rules.end (), Rule ());

  goal->lhs = accept_symbol;

  goal->rhs.push_back (start);

  goal->rhs.push_back (tk_end);

  non_terminals.insert (accept_symbol);

}

struct _Nullable: public std::unary_function<Name, bool>

{

  Automaton *_M_automaton;

  _Nullable (Automaton *aut):

    _M_automaton (aut) {}

  bool operator () (Name name) const

  { return _M_automaton->nullables.find (name) != _M_automaton->nullables.end (); }

};

Automaton::Automaton (Grammar *g):

  _M_grammar (g),

  start (states.end ())

{

}

int Automaton::id (RulePointer rule)

{

  return 1 + std::distance (_M_grammar->rules.begin (), rule);

}

int Automaton::id (Name name)

{

  return std::distance (_M_grammar->names.begin (), name);

}

int Automaton::id (StatePointer state)

{

  return std::distance (states.begin (), state);

}

void Automaton::build ()

{

  Item item;

  item.rule = _M_grammar->goal;

  item.dot = _M_grammar->goal->rhs.begin ();

  State tmp (_M_grammar);

  tmp.insert (item);

  start = internState (tmp).first;

  closure (start);

  buildNullables ();

  buildLookbackSets ();

  buildReads ();

  buildIncludesAndFollows ();

  buildLookaheads ();

  buildDefaultReduceActions ();

}

void Automaton::buildNullables ()

{

  bool changed = true;

  while (changed)

    {

      changed = false;

      for (RulePointer rule = _M_grammar->rules.begin (); rule != _M_grammar->rules.end (); ++rule)

        {

          NameList::iterator nn = std::find_if (rule->rhs.begin (), rule->rhs.end (), std::not1 (_Nullable (this)));

          if (nn == rule->rhs.end ())

            changed |= nullables.insert (rule->lhs).second;

        }

    }

#ifndef QLALR_NO_DEBUG_NULLABLES

  qerr << "nullables = {" << nullables << endl;

#endif

}

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

{

  StatePointer it = qFind (states.begin (), states.end (), state);

  if (it != states.end ())

    return qMakePair (it, false);

  return qMakePair (states.insert (it, state), true);

}

struct _Bucket

{

  QLinkedList<ItemPointer> items;

  void insert (ItemPointer item)

  { items.push_back (item); }

  State toState (Automaton *aut)

  {

    State st (aut->_M_grammar);

    for (QLinkedList<ItemPointer>::iterator item = items.begin (); item != items.end (); ++item)

      st.insert ((*item)->next ());

    return st;

  }

};

void Automaton::closure (StatePointer state)

{

  if (! state->closure.empty ()) // ### not true.

    return;

  typedef QMap<Name, _Bucket> bucket_map_type;

  bucket_map_type buckets;

  QStack<ItemPointer> working_list;

  for (ItemPointer item = state->kernel.begin (); item != state->kernel.end (); ++item)

    working_list.push (item);

  state->closure = state->kernel;

  while (! working_list.empty ())

    {

      ItemPointer item = working_list.top ();

      working_list.pop ();

      if (item->isReduceItem ())

        continue;

      buckets [*item->dot].insert (item);

      if (_M_grammar->isNonTerminal (*item->dot))

        {

          foreach (RulePointer rule, _M_grammar->rule_map.values (*item->dot))

            {

              Item ii;

              ii.rule = rule;

              ii.dot = rule->rhs.begin ();

              QPair<ItemPointer, bool> r = state->insertClosure (ii);

              if (r.second)

                working_list.push (r.first);

            }

        }

    }

  QList<StatePointer> todo;

  for (bucket_map_type::iterator bucket = buckets.begin (); bucket != buckets.end (); ++bucket)

    {

      QPair<StatePointer, bool> r = internState (bucket->toState (this));

      StatePointer target = r.first;

      if (r.second)

        todo.push_back (target);

      state->bundle.insert (bucket.key(), target);

    }

  while (! todo.empty ())

    {

      closure (todo.front ());

      todo.pop_front ();

    }

}

void Automaton::buildLookbackSets ()

{

  for (StatePointer p = states.begin (); p != states.end (); ++p)

    {

      for (Bundle::iterator a = p->bundle.begin (); a != p->bundle.end (); ++a)

        {

          Name A = a.key ();

          if (! _M_grammar->isNonTerminal (A))

            continue;

          foreach (RulePointer rule, _M_grammar->rule_map.values (A))

            {

              StatePointer q = p;

              for (NameList::iterator dot = rule->rhs.begin (); dot != rule->rhs.end (); ++dot)

                q = q->bundle.value (*dot, states.end ());

              Q_ASSERT (q != states.end ());

              ItemPointer item = q->closure.begin ();

              for (; item != q->closure.end (); ++item)

                {

                  if (item->rule == rule && item->dot == item->end_rhs ())

                    break;

                }

              if (item == q->closure.end ())

                {

                  Q_ASSERT (q == p);

                  Q_ASSERT (rule->rhs.begin () == rule->rhs.end ());

                  for (item = q->closure.begin (); item != q->closure.end (); ++item)

                    {

                      if (item->rule == rule && item->dot == item->end_rhs ())

                        break;

                    }

                }

              Q_ASSERT (item != q->closure.end ());

              lookbacks.insert (item, Lookback (p, A));

#ifndef QLALR_NO_DEBUG_LOOKBACKS

              qerr << "*** (" << id (q) << ", " << *rule << ") lookback (" << id (p) << ", " << *A << ")" << endl;

#endif

            }

        }

    }

}

void Automaton::buildDirectReads ()

{

  for (StatePointer q = states.begin (); q != states.end (); ++q)

    {

      for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)

        {

          if (! _M_grammar->isNonTerminal (a.key ()))

            continue;

          StatePointer r = a.value ();

          for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)

            {

              Name sym = z.key ();

              if (! _M_grammar->isTerminal (sym))

                continue;

              q->reads [a.key ()].insert (sym);

            }

        }

#ifndef QLALR_NO_DEBUG_DIRECT_READS

      for (QMap<Name, NameSet>::iterator dr = q->reads.begin (); dr != q->reads.end (); ++dr)

        qerr << "*** DR(" << id (q) << ", " << dr.key () << ") = " << dr.value () << endl;

#endif

    }

}

void Automaton::buildReadsDigraph ()

{

  for (StatePointer q = states.begin (); q != states.end (); ++q)

    {

      for (Bundle::iterator a = q->bundle.begin (); a != q->bundle.end (); ++a)

        {

          if (! _M_grammar->isNonTerminal (a.key ()))

            continue;

          StatePointer r = a.value ();

          for (Bundle::iterator z = r->bundle.begin (); z != r->bundle.end (); ++z)

            {

              Name sym = z.key ();

              if (! _M_grammar->isNonTerminal(sym) || nullables.find (sym) == nullables.end ())

                continue;

              ReadsGraph::iterator source = ReadsGraph::get (Read (q, a.key ()));

              ReadsGraph::iterator target = ReadsGraph::get (Read (r, sym));

              source->insertEdge (target);

#ifndef QLALR_NO_DEBUG_READS

              qerr << "*** ";

              dump (qerr, source);

              qerr << " reads ";

              dump (qerr, target);

              qerr << endl;

#endif

            }

        }

    }

}