#include <stdio.h>
#include <string.h>
#include <ctype.h>

#ifndef FALSE
#define FALSE 0
#endif
#ifndef TRUE
#define TRUE (!0)
#endif
typedef struct scrap_node {
  struct scrap_node *next;
  int scrap;
} Scrap_Node;
typedef struct name {
  char *spelling;
  struct name *llink;
  struct name *rlink;
  Scrap_Node *defs;
  Scrap_Node *uses;
  int mark;
  char tab_flag;
  char indent_flag;
  char debug_flag;
} Name;

int tex_flag;      /* if FALSE, don't emit the .tex file */
int output_flag;   /* if FALSE, don't emit the output files */
int compare_flag;  /* if FALSE, overwrite without comparison */
char *command_name;
char *source_name;  /* name of the current file */
int source_line;    /* current line in the source file */
Name *file_names;
Name *macro_names;
Name *user_names;

void pass1();
void write_tex();
void write_files();
void source_open(); /* pass in the name of the source file */
int source_get();   /* no args; returns the next char or EOF */
void init_scraps();
int collect_scrap();
int write_scraps();
Name *collect_file_name();
Name *collect_macro_name();
Name *collect_scrap_name();
Name *name_add();
Name *prefix_add();
char *save_string();
void reverse_lists();
void *arena_getmem();
void arena_free();


#define SLAB_SIZE 500

typedef struct slab {
  struct slab *next;
  char chars[SLAB_SIZE];
} Slab;
typedef struct {
  char *file_name;
  int file_line;
  Slab *slab;
} ScrapEntry;
ScrapEntry *SCRAP[256];

#define scrap_array(i) SCRAP[(i) >> 8][(i) & 255]

int scraps;
void init_scraps()
{
  scraps = 1;
  SCRAP[0] = (ScrapEntry *) arena_getmem(256 * sizeof(ScrapEntry));
}
typedef struct {
  Slab *scrap;
  int index;
} Manager;
static void push(c, manager)
     char c;
     Manager *manager;
{
  Slab *scrap = manager->scrap;
  int index = manager->index;
  scrap->chars[index++] = c;
  if (index == SLAB_SIZE) {
    Slab *new = (Slab *) arena_getmem(sizeof(Slab));
    scrap->next = new;
    manager->scrap = new;
    index = 0;
  }
  manager->index = index;
}
static void pushs(s, manager)
     char *s;
     Manager *manager;
{
  while (*s)
    push(*s++, manager);
}
int collect_scrap()
{
  Manager writer;
  {
    Slab *scrap = (Slab *) arena_getmem(sizeof(Slab));
    if ((scraps & 255) == 0)
      SCRAP[scraps >> 8] = (ScrapEntry *) arena_getmem(256 * sizeof(ScrapEntry));
    scrap_array(scraps).slab = scrap;
    scrap_array(scraps).file_name = save_string(source_name);
    scrap_array(scraps).file_line = source_line;
    writer.scrap = scrap;
    writer.index = 0;
  }
  {
    int c = source_get();
    while (1) {
      switch (c) {
        case EOF: fprintf(stderr, "%s: unexpect EOF in scrap (%s, %d)\n",
                          command_name, scrap_array(scraps).file_name,
                          scrap_array(scraps).file_line);
                  exit(-1);
        case '@': {
                    c = source_get();
                    switch (c) {
                      case '@': pushs("@@", &writer);
                                c = source_get();
                                break;
                      case '|': {
                                  do {
                                    char new_name[100];
                                    char *p = new_name;
                                    do 
                                      c = source_get();
                                    while (isspace(c));
                                    if (c != '@') {
                                      Name *name;
                                      do {
                                        *p++ = c;
                                        c = source_get();
                                      } while (c != '@' && !isspace(c));
                                      *p = '\0';
                                      name = name_add(&user_names, new_name);
                                      if (!name->defs || name->defs->scrap != scraps) {
                                        Scrap_Node *def = (Scrap_Node *) arena_getmem(sizeof(Scrap_Node));
                                        def->scrap = scraps;
                                        def->next = name->defs;
                                        name->defs = def;
                                      }
                                    }
                                  } while (c != '@');
                                  c = source_get();
                                  if (c != '}') {
                                    fprintf(stderr, "%s: unexpected @%c in scrap (%s, %d)\n",
                                            command_name, c, source_name, source_line);
                                    exit(-1);
                                  }
                                }
                      case '}': push('\0', &writer);
                                return scraps++;
                      case '<': {
                                  Name *name = collect_scrap_name();
                                  {
                                    char *s = name->spelling;
                                    int len = strlen(s) - 1;
                                    pushs("@<", &writer);
                                    while (len > 0) {
                                      push(*s++, &writer);
                                      len--;
                                    }
                                    if (*s == ' ')
                                      pushs("...", &writer);
                                    else
                                      push(*s, &writer);
                                    pushs("@>", &writer);
                                  }
                                  {
                                    if (!name->uses || name->uses->scrap != scraps) {
                                      Scrap_Node *use = (Scrap_Node *) arena_getmem(sizeof(Scrap_Node));
                                      use->scrap = scraps;
                                      use->next = name->uses;
                                      name->uses = use;
                                    }
                                  }
                                  c = source_get();
                                }
                                break;
                      default : fprintf(stderr, "%s: unexpected @%c in scrap (%s, %d)\n",
                                        command_name, c, source_name, source_line);
                                exit(-1);
                    }
                  }
                  break;
        default:  push(c, &writer);
                  c = source_get();
                  break;
      }
    }
  }
}
static char pop(manager)
     Manager *manager;
{
  Slab *scrap = manager->scrap;
  int index = manager->index;
  char c = scrap->chars[index++];
  if (index == SLAB_SIZE) {
    manager->scrap = scrap->next;
    index = 0;
  }
  manager->index = index;
  return c;
}
static Name *pop_scrap_name(manager)
     Manager *manager;
{
  char name[100];
  char *p = name;
  int c = pop(manager);
  while (TRUE) {
    if (c == '@')
      {
        c = pop(manager);
        if (c == '@') {
          *p++ = c;
          c = pop(manager);
        }
        else if (c == '>') {
          if (p - name > 3 && p[-1] == '.' && p[-2] == '.' && p[-3] == '.') {
            p[-3] = ' ';
            p -= 2;
          }
          *p = '\0';
          return prefix_add(&macro_names, name);
        }
        else {
          fprintf(stderr, "%s: found an internal problem (1)\n", command_name);
          exit(-1);
        }
      }
    else {
      *p++ = c;
      c = pop(manager);
    }
  }
}
int write_scraps(file, defs, global_indent, indent_chars,
                   debug_flag, tab_flag, indent_flag)
     FILE *file;
     Scrap_Node *defs;
     int global_indent;
     char *indent_chars;
     char debug_flag;
     char tab_flag;
     char indent_flag;
{
  int indent = 0;
  while (defs) {
    {
      char c;
      Manager reader;
      int line_number = scrap_array(defs->scrap).file_line;
      if (debug_flag) {
        fprintf(file, "\n#line %d \"%s\"\n",
                line_number, scrap_array(defs->scrap).file_name);
        {
          if (indent_flag) {
            if (tab_flag)
              for (indent=0; indent<global_indent; indent++)
                putc(' ', file);
            else
              for (indent=0; indent<global_indent; indent++)
                putc(indent_chars[indent], file);
          }
          indent = 0;
        }
      }
      reader.scrap = scrap_array(defs->scrap).slab;
      reader.index = 0;
      c = pop(&reader);
      while (c) {
        switch (c) {
          case '@':  {
                       c = pop(&reader);
                       switch (c) {
                         case '@': putc(c, file);
                                   indent_chars[global_indent + indent] = ' ';
                                   indent++;
                                   break;
                         case '<': {
                                     Name *name = pop_scrap_name(&reader);
                                     if (name->mark) {
                                       fprintf(stderr, "%s: recursive macro discovered involving <%s>\n",
                                               command_name, name->spelling);
                                       exit(-1);
                                     }
                                     if (name->defs) {
                                       name->mark = TRUE;
                                       indent = write_scraps(file, name->defs, global_indent + indent,
                                                             indent_chars, debug_flag, tab_flag, indent_flag);
                                       indent -= global_indent;
                                       name->mark = FALSE;
                                     }
                                     else if (!tex_flag)
                                       fprintf(stderr, "%s: macro never defined <%s>\n",
                                               command_name, name->spelling);
                                   }
                                   if (debug_flag) {
                                     fprintf(file, "\n#line %d \"%s\"\n",
                                             line_number, scrap_array(defs->scrap).file_name);
                                     {
                                       if (indent_flag) {
                                         if (tab_flag)
                                           for (indent=0; indent<global_indent; indent++)
                                             putc(' ', file);
                                         else
                                           for (indent=0; indent<global_indent; indent++)
                                             putc(indent_chars[indent], file);
                                       }
                                       indent = 0;
                                     }
                                   }
                                   break;
                         default:  /* ignore, since we should already have a warning */
                                   break;
                       }
                     }
                     break;
          case '\n': putc(c, file);
                     line_number++;
                     {
                       if (indent_flag) {
                         if (tab_flag)
                           for (indent=0; indent<global_indent; indent++)
                             putc(' ', file);
                         else
                           for (indent=0; indent<global_indent; indent++)
                             putc(indent_chars[indent], file);
                       }
                       indent = 0;
                     }
                     break;
          case '\t': {
                       if (tab_flag)
                         {
                           int delta = 8 - (indent % 8);
                           indent += delta;
                           while (delta > 0) {
                             putc(' ', file);
                             delta--;
                           }
                         }
                       else {
                         putc('\t', file);
                         indent_chars[global_indent + indent] = '\t';
                         indent++;
                       }
                     }
                     break;
          default:   putc(c, file);
                     indent_chars[global_indent + indent] = ' ';
                     indent++;
                     break;
        }
        c = pop(&reader);
      }
    }
    defs = defs->next;
  }
  return indent + global_indent;
}

typedef struct name_node {
  struct name_node *next;
  Name *name;
} Name_Node;

typedef struct goto_node {
  struct goto_node *next;       /* next goto node with same depth */
  struct goto_node *fail;
  struct move_node *moves;
  Name_Node *output;
} Goto_Node;

typedef struct move_node {
  struct move_node *next;
  Goto_Node *state;
  char c;
} Move_Node;

static Goto_Node *root[128];
static int max_depth;
static Goto_Node **depths;
static Goto_Node *goto_lookup(c, g)
     char c;
     Goto_Node *g;
{
  Move_Node *m = g->moves;
  while (m && m->c != c)
    m = m->next;
  if (m)
    return m->state;
  else
    return NULL;
}

static void build_gotos();

void search()
{
  int i;
  for (i=0; i<128; i++)
    root[i] = NULL;
  max_depth = 10;
  depths = (Goto_Node **) arena_getmem(max_depth * sizeof(Goto_Node *));
  for (i=0; i<max_depth; i++)
    depths[i] = NULL;
  build_gotos(user_names);
  {
    int depth;
    for (depth=1; depth<max_depth; depth++) {
      Goto_Node *r = depths[depth];
      while (r) {
        Move_Node *m = r->moves;
        while (m) {
          char a = m->c;
          Goto_Node *s = m->state;
          Goto_Node *state = r->fail;
          while (state && !goto_lookup(a, state))
            state = state->fail;
          if (state)
            s->fail = goto_lookup(a, state);
          else
            s->fail = root[a];
          if (s->fail) {
            Name_Node *p = s->fail->output;
            while (p) {
              Name_Node *q = (Name_Node *) arena_getmem(sizeof(Name_Node));
              q->name = p->name;
              q->next = s->output;
              s->output = q;
              p = p->next;
            }
          }
          m = m->next;
        }
        r = r->next;
      }
    }
  }
  {
    for (i=1; i<scraps; i++) {
      char c;
      Manager reader;
      Goto_Node *state = NULL;
      reader.scrap = scrap_array(i).slab;
      reader.index = 0;
      c = pop(&reader);
      while (c) {
        while (state && !goto_lookup(c, state))
          state = state->fail;
        if (state)
          state = goto_lookup(c, state);
        else
          state = root[c];
        if (state && state->output) {
          Name_Node *p = state->output;
          do {
            Name *name = p->name;
            if (!name->uses || name->uses->scrap != i) {
              Scrap_Node *new_use =
                  (Scrap_Node *) arena_getmem(sizeof(Scrap_Node));
              new_use->scrap = i;
              new_use->next = name->uses;
              name->uses = new_use;
            }
            p = p->next;
          } while (p);
        }
        c = pop(&reader);
      }
    }
  }
}
static void build_gotos(tree)
     Name *tree;
{
  while (tree) {
    {
      int depth = 2;
      char *p = tree->spelling;
      char c = *p++;
      Goto_Node *q = root[c];
      if (!q) {
        q = (Goto_Node *) arena_getmem(sizeof(Goto_Node));
        root[c] = q;
        q->moves = NULL;
        q->fail = NULL;
        q->moves = NULL;
        q->output = NULL;
        q->next = depths[1];
        depths[1] = q;
      }
      while (c = *p++) {
        Goto_Node *new = goto_lookup(c, q);
        if (!new) {
          Move_Node *new_move = (Move_Node *) arena_getmem(sizeof(Move_Node));
          new = (Goto_Node *) arena_getmem(sizeof(Goto_Node));
          new->moves = NULL;
          new->fail = NULL;
          new->moves = NULL;
          new->output = NULL;
          new_move->state = new;
          new_move->c = c;
          new_move->next = q->moves;
          q->moves = new_move;
          if (depth == max_depth) {
            int i;
            Goto_Node **new_depths =
                (Goto_Node **) arena_getmem(2*depth*sizeof(Goto_Node *));
            max_depth = 2 * depth;
            for (i=0; i<depth; i++)
              new_depths[i] = depths[i];
            depths = new_depths;
            for (i=depth; i<max_depth; i++)
              depths[i] = NULL;
          }
          new->next = depths[depth];
          depths[depth] = new;
        }
        q = new;
        depth++;
      }
      q->output = (Name_Node *) arena_getmem(sizeof(Name_Node));
      q->output->next = NULL;
      q->output->name = tree;
    }
    build_gotos(tree->rlink);
    tree = tree->llink;
  }
}