/*******************************************************************************
+
+  LEDA 3.5
+
+  _gml_parser.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
//------------------------------------------------------------------- //
// class gmlparser, extendible parser for the GML format              //
//                                                                    //
// by David Alberts (1997)                                            //
//------------------------------------------------------------------- //

#include<LEDA/impl/gml_parser.h>


// ------------------------ class gml_object ------------------------ //

gml_object::~gml_object()
{
  if(the_type == gml_list)
  {
    gml_object* g;
    forall(g,the_list) delete g;
  }
}

static int gml_indent = 0;

ostream& operator<<(ostream& out, const gml_object& g)
{
  for(int i=0; i<gml_indent; i++) out << ' ';
  out << g.the_key << " ";

  switch(g.the_type)
  {
    case gml_int:    { out << g.the_int; break; }
    case gml_double: { out << g.the_double; break; }
    case gml_string: { out << '"' << g.the_string << '"'; break; }
    case gml_list:
    {
      gml_indent +=2;

      out << "[";

      gml_object* h;
      forall(h,g.the_list)
      {
        out << "\n";
        out << *h;
      }

      gml_indent -=2;

      if(g.the_list.size())
      {
        out << "\n";
        for(int i=0; i<gml_indent; i++) out << ' ';
        out << "]";
      }
      else out << " ]";

      break;
    }
    default:         { out << 42; break; }
  }

  return out;
}



// ------------------------ class gml_objecttree ----------------------- //

bool gml_objecttree::read(istream& ins, int chunk_size)
// reads from ins.
{
  root_key = string("istream");

  if(in_chars)  delete[] in_chars;

  if(ins.fail()) return false;

  in_chars = new char[chunk_size];

  pos = 0;

  char* buf;
  char c;
  bool reading = true;
  while(reading)
  {
    if(ins.fail()) return false;
    ins.get(&(in_chars[pos]),chunk_size-pos,'\0');
    if(ins.fail()) return false;
    ins.get(c);
    if(!ins.eof())
    {
      // in_chars is too small...
      pos = chunk_size;
      chunk_size = chunk_size << 1;
      buf = new char[chunk_size];
      strcpy(buf,in_chars);
      delete[] in_chars;
      in_chars = buf;
      in_chars[pos-1] = c;    // ... care about last character
    }
    else reading = false;
  }

  in_length = int(ins.tellg());

  // initialize line brake structure and object tree
  init_lines();
  init_tree();

  return build();
}


bool gml_objecttree::read(char* filename)
// reads from filename.
{
  root_key = string(filename);

  if(in_chars)  delete[] in_chars;

  ifstream ins(filename);

  if(!ins || ins.fail()) return false;

  // get length of file
  int buffer_size;
  struct stat st;
  int rv = stat(filename,&st);

  if(!rv)  // stat successful
  {
    buffer_size = int(st.st_size)+2;
    in_chars = new char[buffer_size];
    ins.get(in_chars,buffer_size,'\0');
    in_length = int(ins.tellg());

    // initialize line brake structure and object tree
    init_lines();
    init_tree();

    return build();
  }
  else     // cannot stat, try stream
  {    
    return read(ins);
  }
}

void gml_objecttree::init_lines()
{
  lines.clear();
  line_starts.clear();

  lines.insert(0,1);
  line_starts.insert(1,0);

  int line_counter = 2;

  for(pos = 0; pos < in_length; pos++)
  {
    if(current_char() == '\n')
    {
      lines.insert(pos+1,line_counter);
      line_starts.insert(line_counter,pos+1);
      line_counter++;
    }
  }

  pos = 0;
}

void gml_objecttree::init_tree()
{
  // initialize root object
  objects.the_key = root_key.cstring();
  objects.the_type = gml_list;
  objects.the_list.clear();
  objects.parent = 0;

  // initialize context
  syntax_errors = false;
  bracket_level = 0;
  current_context = &objects;
  current_object = new gml_object;
} 


bool gml_objecttree::build()
{
  while(!syntax_errors && (pos < in_length))
    if(read_key()) read_value();

  delete current_object;
  current_object = 0;

  if(!syntax_errors && bracket_level) print_error("unterminated list");

  return !syntax_errors;
}

bool gml_objecttree::read_key()
{
  bool context_switch = false;

  do
  {
    skip_white();
    if(current_char() == ']')
    {
      context_switch = true;
      current_context = current_context->parent;
      if(--bracket_level < 0)
      {
        print_error("too many closing ]");
        return false;
      }
      advance();
    }
    else context_switch = false;

  } while(context_switch);

  if(!isalpha(current_char()))
  {
    if(pos < in_length - 1)  // EOF otherwise
    {
      if(current_char() == '[')
        print_error("list without key word");
      else
        print_error("key word does not start with a letter");
    }
    return false;
  }

  // find delimiter
  int delim = next_white();
  if(delim == -1) return false;

  // delimit and store key
  in_chars[delim] = '\0';
  current_object->the_key = &(in_chars[pos]);
  current_object->key_pos = pos;

  // skip past key
  advance(delim-pos+1);

  return true;
}


void gml_objecttree::read_value()
{
  skip_white();
  switch(current_char())
  {
    case '"':
    {
      // we are reading a string...
      advance();
      int delim = next_quot();
      if(delim == -1)
      {
        print_error("unterminated string");
      }
      else
      {
        current_object->the_type = gml_string;
        in_chars[delim] = '\0';
        current_object->the_string = &(in_chars[pos]);
        current_object->where =
          current_context->the_list.append(current_object);
        current_object->parent = current_context;
        current_object = new gml_object;
        advance(delim-pos+1);
      }
      break;
    }

    case '0': case '1': case '2': case '3': case '4': case '5':
    case '6': case '7': case '8': case '9': case '+': case '-': case '.':
    {
      // we are reading a number...
      int delim = next_white();
      if(delim == -1)
      {
        print_error("unterminated number");
        return;
      }
      in_chars[delim] = '\0';
      char* nval = &(in_chars[pos]);

      // check whether nval is an integer...
      char* rest;
      long l = strtol(nval,&rest,10);

      if(!strlen(rest))     // ...yes, it is
      {
        current_object->the_type = gml_int;
        current_object->the_int = int(l);
        current_object->where = 
          current_context->the_list.append(current_object);
        current_object->parent = current_context;
        current_object = new gml_object;
      }
      else                  // ...no, it is not
      {
        // check whether nval is a double...
        double d = strtod(nval,&rest);

        if(!strlen(rest))   // ...yes, it is
        {
          current_object->the_type = gml_double;
          current_object->the_double = d;
          current_object->where =
            current_context->the_list.append(current_object);
          current_object->parent = current_context;
          current_object = new gml_object;
        }
        else                // ...no, it is not
        {
          print_error("malformed number");
          return;
        }
      }

      advance(delim-pos+1);
      break;
    }

    case '[':
    {
      // we are reading a list...
      bracket_level++;
      current_object->the_type = gml_list;
      current_object->where =
        current_context->the_list.append(current_object);
      current_object->parent = current_context;

      // switch context...
      current_context = current_object;
      current_object = new gml_object;

      advance();
      break;
    }

    case '\0':
    {
      print_error("missing value");
      break;
    }

    default:
    {
      print_error("malformed value");
      break;
    }
  }
}

void gml_objecttree::advance(int n)
// advances the current position by n characters
{
  if(pos + n > in_length)
  {
    pos = in_length;
    print_error("unexpected end of file");
  }
  else pos += n;
}

void gml_objecttree::skip_white()
// skips white space.
{
  bool keep_on = true;
  do
  {
    while(isspace(current_char())) advance();
    if(current_char() == '#')  // beginning of a comment...
      while(current_char() != '\n') advance();
    else keep_on = false;
  } while(keep_on);
}

int gml_objecttree::next_white()
// returns position of next white space character in in_chars or -1
{
  int p = pos;
  while(!isspace(in_chars[p]) && (p < in_length)) p++;

  return (p < in_length) ? p : -1;
}

int gml_objecttree::next_quot()
// returns position of next " or -1
{
  int p = pos;
  while((in_chars[p] != '"') && (p < in_length)) p++;

  return (p < in_length) ? p : -1;
}

void gml_objecttree::line_col(int position, int& line, int& col)
{
  line = lines.inf(lines.locate_pred(position));
  int start = line_starts.inf(line_starts.lookup(line));
  col = position - start + 1;
}

void gml_objecttree::print_error(char* type)
{
  int line, col;
  line_col(pos,line,col);

  string msg("%s(line %d, column %d): %s\n",get_root_key(),line,col,type);
  error_handler(0,msg.cstring());

  syntax_errors = true;
}


gml_object* gml_objecttree::first_object()
{
  current_context = &objects;
  current_object = current_context->the_list.head();
  return current_object;
}


gml_object* gml_objecttree::next_object()
{
  if(!current_object) return first_object();

  slist_item lit = current_context->the_list.succ(current_object->where);
  if(!lit) return 0;
  current_object = current_context->the_list.inf(lit);
  return current_object;
}

gml_object* gml_objecttree::down()
{
  if(   (current_object->the_type == gml_list)
     && (current_object->the_list.size())      )
  {
    current_context = current_object;
    current_object = current_object->the_list.head();
    return current_object;
  }
  else return 0;
}

gml_object* gml_objecttree::up()
{
  if(current_context == &objects) return 0;

  slist_item lit = 
    current_context->parent->the_list.succ(current_context->where);
  if(!lit) return 0;
  current_context = current_context->parent;
  current_object = current_context->the_list.inf(lit);
  return current_object;
}

gml_object* gml_objecttree::parent()
{
  if(current_context == &objects) return 0;

  current_object = current_context;
  current_context = current_context->parent;

  return current_object;
}

bool gml_objecttree::last_in_list()
{
  if(!current_object) return true;
  return (current_object->where == current_context->the_list.last());
}


// ------------------------ class gml_pattern ----------------------- //

gml_pattern::~gml_pattern()
{
  dic_item d;
  forall_items(d,children) delete children.inf(d);
}


// ------------------------ class gml_parser ------------------------ //

void gml_parser::add_rule(const slist<char*>& cont,
                          gml_rule r, gml_value_type t)
{
  reset_path();
  make_context(cont);
  current_pattern->add_rule(r,t);
}

void gml_parser::make_context(const slist<char*>& cont)
{
  char* key;
  forall(key,cont) append(key);
}

void gml_parser::append(char* key)
{
  dic_item there = current_pattern->children.lookup(key);
  if(there)
  {
    current_pattern = current_pattern->children.inf(there);
  }
  else
  {
    gml_pattern* pat;
    pat = new gml_pattern();
    pat->the_key = key;
    current_pattern->children.insert(key,pat);
    pat->parent = current_pattern;
    current_pattern = pat;
  }
}


void gml_parser::goback()
{
  if(current_pattern != &patterns)
    current_pattern = current_pattern->parent;
}


bool gml_parser::parse(char* filename)
{
  bool result = false;
  T = new gml_objecttree;
  T->read(filename);
  if(!T->errors())
  {
    reset_path();
    init_rules();
    result = parse();
    cleanup();
  }
  delete T;
  return result;
}

bool gml_parser::parse(istream& ins)
{
  bool result = false;
  T = new gml_objecttree;
  T->read(ins);
  if(!T->errors())
  {
    reset_path();
    init_rules();
    result = parse();
    cleanup();
  }
  delete T;
  return result;
}

bool gml_parser::parse(gml_objecttree& obj)
{
  bool result = false;
  T = &obj;
  if(!T->errors())
  {
    reset_path();
    init_rules();
    result = parse();
    cleanup();
  }
  return result;
}


bool gml_parser::parse()
{
  if(!patterns.children.size()) return true;   // nothing to be done

  reset_path();
  current_object = T->first_object();
  parse_error = false;
  bool down;

  while(current_object && !parse_error)
  {
    parse_object();

    down = false;

    if(current_object->get_type() == gml_list)
    {
      if(current_pattern->children.size())
      {
        dic_item dit = 
          current_pattern->children.lookup(current_object->get_key());
        if(dit)
        {
          gml_pattern* below = current_pattern->children.inf(dit);
          if(below->children.size())
          {
            current_object = T->down();
            current_pattern = below;
            down = true;
          }
        }
      }
    }

    if(!down)
    {
      if(T->last_in_list()) list_end();
      else current_object = T->next_object();
    }

  }

  return !parse_error;
}

void gml_parser::parse_object()
{
  dic_item dit = current_pattern->children.lookup(current_object->get_key());
  if(!dit) return;
  else
  {
    gml_value_type object_type = current_object->get_type();
    if(object_type == gml_none) return;

    gml_pattern* pat = current_pattern->children.inf(dit);

    gml_rule r;
    forall(r,pat->rules[object_type])
      parse_error = parse_error || !interpret(r,current_object);
  }
}

void gml_parser::list_end()
{
  while((current_pattern != &patterns) && T->last_in_list())
  {
    current_object = T->parent();

    gml_rule r;
    forall(r,current_pattern->rules[gml_list])
      parse_error = parse_error || !list_end(r,current_object);

    current_pattern = current_pattern->parent;
  }

  current_object = T->next_object();
}


void gml_parser::print_error(const gml_object& gobj, char* type)
{
  int line, col;
  T->line_col(gobj,line,col);

  string msg("%s(line %d, column %d): %s\n",T->get_root_key(),line,col,type);
  error_handler(0,msg.cstring());

  parse_error = true;
}


