#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <ctype.h>
#include <sys/types.h>
#include <sys/param.h>

#include <assert.h>

#include "queue.h"

typedef struct _Stream		Stream;
typedef struct _String		String;
typedef struct _Token		Token;
typedef struct _Group		Group;
typedef struct _Definition	Definition;

void fatal(const char *fmt, ...)
{
  va_list ap;
  va_start(ap, fmt);
  fflush(stdout);
  fprintf(stderr, "\n! ");
  vfprintf(stderr, fmt, ap);
  fprintf(stderr, ".\n");
  exit(1);
  va_end(ap);
}

/* ---------------------------------------------------------------- */

void *xmalloc(size_t size)
{
  void *ptr= malloc(size);
  if (!ptr) fatal("Out of memory");
  return ptr;
}

void *xcalloc(size_t count, size_t size)
{
  void *ptr= calloc(count, size);
  if (!ptr) fatal("Out of memory");
  return ptr;
}

#define xnew(type)	((type *)xcalloc(1, sizeof(type)))

void *xrealloc(void *ptr, size_t size)
{
  void *newPtr= realloc(ptr, size);
  if (!newPtr) fatal("Out of memory");
  return newPtr;
}

char *xstrdup(char *string)
{
  size_t len= strlen(string);
  char *copy= (char *)xmalloc(len + 1);
  strcpy(copy, string);
  return copy;
}

void xfree(void *ptr)
{
  if (!ptr) fatal("Freeing NULL pointer");
  free(ptr);
}

/* ---------------------------------------------------------------- */

struct _Stream
{
  FILE			*file;
  char			*name;
  int			 line;
};

Stream *oldStream(char *name, FILE *file)
{
  Stream *stream= xnew(Stream);
  stream->file= file;
  stream->name= xstrdup(name);
  stream->line= 1;
  return stream;
}

void deleteStream(Stream *stream)
{
  xfree(stream->name);
  xfree(stream);
}

int nextChar(Stream *stream)
{
  int c= getc(stream->file);
  if (c == '\n') ++stream->line;
  return c;
}

/* ---------------------------------------------------------------- */

struct _String
{
  size_t		 size;
  char			*chars;
  STAILQ_ENTRY(_String)	 list;
};

typedef STAILQ_HEAD(_StringList, _String) StringList;

StringList freeStrings= STAILQ_HEAD_INITIALIZER(freeStrings);

String *oldString(char *chars)
{
  size_t len= strlen(chars);
  String *string= 0;
  if (STAILQ_EMPTY(&freeStrings))
    string= xnew(String);
  else
    {
      string= STAILQ_FIRST(&freeStrings);
      STAILQ_REMOVE_HEAD(&freeStrings, list);
    }
  if (len >= string->size)
    {
      if (string->chars) xfree(string->chars);
      string->size= len + 1;
      string->chars= xmalloc(string->size);
    }
  strcpy(string->chars, chars);
  return string;
}

void deleteString(String *string)
{
  STAILQ_INSERT_HEAD(&freeStrings, string, list);
}

String *stringAppend(String *head, String *tail)
{
  size_t hlen= strlen(head->chars);
  size_t tlen= strlen(tail->chars);
  if (hlen + tlen >= head->size)
    {
      head->size= (hlen + tlen) * 2;
      head->chars= (char *)xrealloc(head->chars, head->size);
    }
  strcpy(head->chars + hlen, tail->chars);
  return head;
}

/* ---------------------------------------------------------------- */

struct _Token {
  enum
    {
      OTHER= 0,
      SPACE,
      LETTER,
      CSNAME,
      BEGIN,
      END,
      ARG,
      COMMENT
    }			 type;
  String		*string;
  STAILQ_ENTRY(_Token)	 list;
};

typedef STAILQ_HEAD(_TokenList, _Token) TokenList;

TokenList freeTokens= STAILQ_HEAD_INITIALIZER(freeTokens);

TokenList *newTokenList(void)
{
  TokenList *tokenList= xnew(TokenList);
  STAILQ_INIT(tokenList);
  return tokenList;
}

TokenList *tokenListAppend(TokenList *tokenList, Token *token)
{
  STAILQ_INSERT_TAIL(tokenList, token, list);
  return tokenList;
}

Token *newToken(int type, String *string)
{
  Token *token= 0;
  if (STAILQ_EMPTY(&freeTokens))
    token= xnew(Token);
  else
    {
      token= STAILQ_FIRST(&freeTokens);
      STAILQ_REMOVE_HEAD(&freeTokens, list);
    }
  token->type=   type;
  token->string= string;
  return token;
}

void deleteToken(Token *token)
{
  STAILQ_INSERT_HEAD(&freeTokens, token, list);
}

Token *copyToken(Token *old)
{
  return newToken(old->type, old->string);
}

Token *printToken(Token *token)
{
  fputs(token->string->chars, stdout);
  return token;
}

void printTokenList(TokenList *tokens)
{
  Token *token= STAILQ_FIRST(tokens);
  while (token)
    {
      printToken(token);
      token= STAILQ_NEXT(token, list);
    }
}

/* ---------------------------------------------------------------- */

struct _Group {
  TokenList		 tokenList;
  STAILQ_ENTRY(_Group)	 list;
};

typedef STAILQ_HEAD(_GroupList, _Group) GroupList;

GroupList freeGroups= STAILQ_HEAD_INITIALIZER(freeGroups);

GroupList *newGroupList(void)
{
  GroupList *groupList= xnew(GroupList);
  STAILQ_INIT(groupList);
  return groupList;
}

GroupList *groupListAppend(GroupList *groupList, Group *group)
{
  STAILQ_INSERT_TAIL(groupList, group, list);
  return groupList;
}

Group *newGroup(void)
{
  Group *group= 0;
  if (STAILQ_EMPTY(&freeGroups))
    group= xnew(Group);
  else
    {
      group= STAILQ_FIRST(&freeGroups);
      STAILQ_REMOVE_HEAD(&freeGroups, list);
    }
  STAILQ_INIT(&group->tokenList);
  return group;
}

void deleteGroup(Group *token)
{
  STAILQ_INSERT_HEAD(&freeGroups, token, list);
}

void deleteGroupContents(Group *group)
{
  while (!STAILQ_EMPTY(&group->tokenList))
    {
      Token *token= STAILQ_FIRST(&group->tokenList);
      STAILQ_REMOVE_HEAD(&group->tokenList, list);
      deleteToken(token);
    }
}

Group *groupAppendToken(Group *group, Token *token)
{
  STAILQ_INSERT_TAIL(&group->tokenList, token, list);
  return group;
}

Group *printGroup(Group *group)
{
  Token *token= STAILQ_FIRST(&group->tokenList);
  fputc('{', stdout);
  while (token)
    {
      fputs(token->string->chars, stdout);
      token= STAILQ_NEXT(token, list);
      if (token) fputc(' ', stdout);
    }
  fputc('}', stdout);
  return group;
}

/* ---------------------------------------------------------------- */

struct _Definition {
  Token				*name;
  TokenList			*args;
  Group				*body;
  STAILQ_ENTRY(_Definition)	 list;
};

typedef STAILQ_HEAD(_DefinitionList, _Definition) DefinitionList;

DefinitionList definitionList= STAILQ_HEAD_INITIALIZER(definitionList);

DefinitionList freeDefinitions= STAILQ_HEAD_INITIALIZER(freeDefinitions);

Definition *newDefinition(Token *name, TokenList *args, Group *body)
{
  Definition *definition= 0;
  if (STAILQ_EMPTY(&freeDefinitions))
    definition= xnew(Definition);
  else
    {
      definition= STAILQ_FIRST(&freeDefinitions);
      STAILQ_REMOVE_HEAD(&freeDefinitions, list);
    }
  definition->name= name;
  definition->args= args;
  definition->body= body;
  return definition;
}

void deleteDefinition(Definition *definition)
{
  STAILQ_INSERT_HEAD(&freeDefinitions, definition, list);
}

Definition *printDefinition(Definition *definition)
{
  printToken(definition->name);
  printf(" -> ");
  printGroup(definition->body);
  return definition;
}

/* ---------------------------------------------------------------- */

int charClass[256];

Token *nextToken(Stream *input)
{
  char    buf[32];
  int     c= nextChar(input);
  String *string= 0;
  if (c < 1) return 0;
  buf[0]= c;
  buf[1]= '\0';
  string= oldString(buf);
  Token *t= newToken(charClass[c], string);
  return t;
}

void unChomp(TokenList *mouth, Token *token)
{
  STAILQ_INSERT_HEAD(mouth, token, list);
}

Token *chomp(TokenList *mouth)
{
  Token *token= 0;
  if (STAILQ_EMPTY(mouth))
    return 0;
  token= STAILQ_FIRST(mouth);
  STAILQ_REMOVE_HEAD(mouth, list);
  return token;
}

void gobbleSpaces(TokenList *mouth)
{
  Token *token= 0;
  while ((token= chomp(mouth)) && (SPACE == token->type))
    ;
  if (token)
    unChomp(mouth, token);
}

Token *munch(TokenList *mouth)
{
  while (!STAILQ_EMPTY(mouth))
    {
      Token *token= chomp(mouth);
      if (token)
	{
	  switch (token->type)
	    {
	    case CSNAME:
	      {
		Token *next= chomp(mouth);
		if (!next) fatal("File ended while scanning control sequence name");
		if (LETTER != next->type)
		  {
		    deleteToken(token);
		    next->type= OTHER;
		    return next;
		  }
		do
		  {
		    stringAppend(token->string, next->string);
		    deleteToken(next);
		  } while ((next= chomp(mouth)) && (LETTER == next->type));
		if (next)
		  unChomp(mouth, next);
	      }
	      gobbleSpaces(mouth);
	      return token;

	    case END:
	      /*gobbleSpaces(mouth);*/
	      return token;

	    case COMMENT:
	      while ((token= chomp(mouth)) && strcmp("\n", token->string->chars))
		;
	      break;

	    default:
	      return token;
	    }
	} /* if (token) */
    } /* while (!empty(mouth)) */
  return 0;
}

Token *swallow(TokenList *throat, TokenList *mouth)
{
  Token *token= 0;
  if (STAILQ_EMPTY(throat))
    token= munch(mouth);
  else
    {
      token= STAILQ_FIRST(throat);
      STAILQ_REMOVE_HEAD(throat, list);
    }
  return token;
}

Group *swallowGroup(TokenList *throat, TokenList *mouth)
{
  Group *group= newGroup();
  Token *token= swallow(throat, mouth);
  if (token && (BEGIN == token->type))
    {
      int depth= 1;
      while ((token= swallow(throat, mouth)))
	{
	  if (BEGIN == token->type)
	    ++depth;
	  else if (END == token->type)
	    {
	      if (!--depth)
		break;
	    }
	  else if (ARG == token->type)
	    {
	      int argInd;
	      deleteToken(token);
	      if (!(token= swallow(throat, mouth)))
		return 0;
	      if (!(argInd= atoi(token->string->chars)))
		fatal("Parameters must be numbered");
	      if ((argInd < 1) || (argInd > 9))
		fatal("Parameters must be numbered");
	      token->type= ARG;
	    }
	  groupAppendToken(group, token);
	}
      if (depth) return 0;
    }
  else
    groupAppendToken(group, token);
  return group;
}

Token *swallowSpaces(TokenList *throat, TokenList *mouth)
{
  Token *token= swallow(throat, mouth);
  if (token && SPACE == token->type)
    {
      Token *space= 0;
      while ((space= swallow(throat, mouth)) && (SPACE == space->type))
	deleteToken(space);
      if (space)
	unChomp(throat, space);
    }
  return token;
}

TokenList *swallowArgs(TokenList *throat, TokenList *mouth)
{
  TokenList *tokenList= newTokenList();
  Token     *token=     0;
  int        argInd=    1;

  while ((token= swallowSpaces(throat, mouth)))
    switch (token->type)
      {
      case BEGIN:
	unChomp(throat, token);
	return tokenList;

      case END:
	fatal("Missing {");
	break;

      case ARG:
	deleteToken(token);
	if (!(token= swallow(throat, mouth))) return 0;
	if (argInd != atoi(token->string->chars))
	  fatal("Parameters must be numbered consecutively");
	if (argInd > 9)
	  fatal("Too many parameters");
	++argInd;
	token->type= ARG;
	tokenListAppend(tokenList, token);
	continue;
	/* fall through... */

      default:
	tokenListAppend(tokenList, token);
	continue;
      }
  return 0;
}

void copyPushArguments(TokenList *tokenList, Token *head, Group *arguments[])
{
  if (head)
    {
      copyPushArguments(tokenList, STAILQ_NEXT(head, list), arguments);
      if (ARG == head->type)
	{
	  int    argInd= atoi(head->string->chars);
	  Group *actual= 0;
	  if (!argInd)
	    fatal("Cannot use # in macro argument");
	  assert(argInd > 0 && argInd < 10);
	  actual= arguments[argInd - 1];
	  copyPushArguments(tokenList, STAILQ_FIRST(&actual->tokenList), arguments);
	}
      else
	{
	  head= copyToken(head);
	  STAILQ_INSERT_HEAD(tokenList, head, list);
	}
    }
}

void expand(Token *csname, TokenList *throat, TokenList *mouth)
{
  Definition *definition= STAILQ_FIRST(&definitionList);

  while (definition)
    {
      if (!strcmp(definition->name->string->chars, csname->string->chars))
	break;
      definition= STAILQ_NEXT(definition, list);
    }

  if (definition)
    {
      Token     *formal=  STAILQ_FIRST(definition->args);
      Group     *actuals[10];
      int        argInd=  0;

      while (formal)
	{
	  Group *actual= 0;
	  Token *token=  0;
	  switch (formal->type)
	    {
	    case ARG:
	      if (!(token= swallowSpaces(throat, mouth)))  fatal("use");
	      unChomp(throat, token);
	      actual= swallowGroup(throat, mouth);
	      if (!actuals)
		fatal("File ended while scanning use of %s", csname->string->chars);
	      actuals[argInd++]= actual;
	      break;

	    case SPACE:
	      token= swallowSpaces(throat, mouth);
	      if ((!token) || (SPACE != token->type))
		fatal("[1] Use of %s does not match its definition", csname->string->chars);
	      break;

	    default:
	      token= swallowSpaces(throat, mouth);
	      if ((!token) || strcmp(token->string->chars, formal->string->chars))
		fatal("[2] Use of %s does not match its definition", csname->string->chars);
	      break;
	    }
	  formal= STAILQ_NEXT(formal, list);
	}
      copyPushArguments(throat, STAILQ_FIRST(&definition->body->tokenList), actuals);
      while (argInd--)
	{
	  deleteGroupContents(actuals[argInd]);
	  deleteGroup(actuals[argInd]);
	}
      return;
    }

  if (!strcmp(csname->string->chars, "\\def"))
    {
      Token      *name= 0;
      TokenList  *args= newTokenList();
      Group      *body= 0;
      Definition *defn= 0;
      if (!(name= swallow(throat, mouth)))	fatal("File ended while scanning definition");
      if (CSNAME != name->type)			fatal("Missing control sequence: \\def %s", name->string->chars);
      if (!(args= swallowArgs(throat, mouth)))	fatal("File ended while scanning definition of %s", name->string->chars);
      if (!(body= swallowGroup(throat, mouth)))	fatal("File ended while scanning definition of %s", name->string->chars);
      defn= newDefinition(name, args, body);
      STAILQ_INSERT_TAIL(&definitionList, defn, list);
      return;
    }

  fatal("Undefined control sequence: %s", csname->string->chars);
}

Token *digest(TokenList *throat, TokenList *mouth)
{
  Token *token= 0;

  while ((token= swallow(throat, mouth)))
    {
      //printf("DIGEST: ");  printTokenList(throat);  printf(" <#> ");  printTokenList(mouth);  printf("\n");
      switch (token->type)
	{
	case CSNAME:
	  expand(token, throat, mouth);
	  //printf("BURP: ");  printTokenList(throat);  printf(" <#> ");  printTokenList(mouth);  printf("\n");
	  deleteToken(token);
	  continue;

	case BEGIN:
	case END:
	  deleteToken(token);
	  continue;

	default:
	  return token;
	}
    }
  return 0;
}

/* ---------------------------------------------------------------- */

void initClass(int type, char *chars)
{
  if (!chars)
    memset(charClass, type, sizeof(charClass));
  else    
    while (*chars)
      charClass[(int)*chars++]= type;
}

int main(int argc, char **argv)
{
  Stream    *stream= oldStream("<stdin>", stdin);
  Token     *token=  0;
  TokenList  mouth=  STAILQ_HEAD_INITIALIZER(mouth);
  TokenList  throat= STAILQ_HEAD_INITIALIZER(throat);

  initClass(OTHER,   0);
  initClass(SPACE,   " \t\n");
  initClass(LETTER,  "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
  initClass(CSNAME,  "\\");
  initClass(BEGIN,   "{");
  initClass(END,     "}");
  initClass(ARG,     "#");
  initClass(COMMENT, "%");

  while ((token= nextToken(stream)))
    STAILQ_INSERT_TAIL(&mouth, token, list);

  while ((token= digest(&throat, &mouth)))
    {
      if (CSNAME == token->type) putchar('<');
      fputs(token->string->chars, stdout);
      if (CSNAME == token->type) putchar('>');
      deleteToken(token);
    }

  return 0;
}