btparse/src/tex_tree.c

/* ------------------------------------------------------------------------
@NAME       : tex_tree.c
@DESCRIPTION: Functions for dealing with strings of TeX code: converting
              them to tree representation, traversing the trees to glean
              useful information, and converting back to string form.
@GLOBALS    :
@CALLS      :
@CALLERS    :
@CREATED    : 1997/05/29, Greg Ward
@MODIFIED   :
@VERSION    : $Id$
@COPYRIGHT  : Copyright (c) 1996-99 by Gregory P. Ward.  All rights reserved.

              This file is part of the btparse library.  This library is
              free software; you can redistribute it and/or modify it under
              the terms of the GNU Library General Public License as
              published by the Free Software Foundation; either version 2
              of the License, or (at your option) any later version.
-------------------------------------------------------------------------- */

#include "bt_config.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "error.h"
#include "btparse.h"
#include "my_dmalloc.h"

/* blech! temp hack until I make error.c perfect and magical */
#define string_warning(w) fprintf (stderr, w);

typedef struct treestack_s
{
   bt_tex_tree * node;
   struct treestack_s
               * prev,
               * next;
} treestack;


/* ----------------------------------------------------------------------
 * Stack manipulation functions
 */

/* ------------------------------------------------------------------------
@NAME       : push_treestack()
@INPUT      : *stack
              node
@OUTPUT     : *stack
@RETURNS    :
@DESCRIPTION: Creates and initializes new node in a stack, and pushes it
              onto the stack.
@GLOBALS    :
@CALLS      :
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
static void
push_treestack (treestack **stack, bt_tex_tree *node)
{
   treestack  *newtop;

   newtop = (treestack *) malloc (sizeof (treestack));
   newtop->node = node;
   newtop->next = NULL;
   newtop->prev = *stack;

   if (*stack != NULL)                  /* stack already has some entries */
   {
      (*stack)->next = newtop;
      *stack = newtop;
   }

   *stack = newtop;

} /* push_treestack() */


/* ------------------------------------------------------------------------
@NAME       : pop_treestack
@INPUT      : *stack
@OUTPUT     : *stack
@RETURNS    :
@DESCRIPTION: Pops an entry off of a stack of tex_tree nodes, frees up
              the wrapper treestack node, and returns the popped tree node.
@GLOBALS    :
@CALLS      :
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
static bt_tex_tree *
pop_treestack (treestack **stack)
{
   treestack *   oldtop;
   bt_tex_tree * node;

   if (*stack == NULL)
      internal_error ("attempt to pop off empty stack");
   oldtop = (*stack)->prev;
   node = (*stack)->node;
   free (*stack);
   if (oldtop != NULL)
      oldtop->next = NULL;
   *stack = oldtop;
   return node;

} /* pop_treestack() */


/* ----------------------------------------------------------------------
 * Tree creation/destruction functions
 */

/* ------------------------------------------------------------------------
@NAME       : new_tex_tree
@INPUT      : start
@OUTPUT     :
@RETURNS    : pointer to newly-allocated node
@DESCRIPTION: Allocates and initializes a bt_tex_tree node.
@GLOBALS    :
@CALLS      :
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
static bt_tex_tree *
new_tex_tree (char *start)
{
   bt_tex_tree * node;

   node = (bt_tex_tree *) malloc (sizeof (bt_tex_tree));
   node->start = start;
   node->len = 0;
   node->child = node->next = NULL;
   return node;
}


/* ------------------------------------------------------------------------
@NAME       : bt_build_tex_tree
@INPUT      : string
@OUTPUT     :
@RETURNS    : pointer to a complete tree; call bt_free_tex_tree() to free
              the entire tree
@DESCRIPTION: Traverses a string looking for TeX groups ({...}), and builds
              a tree containing pointers into the string and describing
              its brace-structure.
@GLOBALS    :
@CALLS      :
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
bt_tex_tree *
bt_build_tex_tree (char * string)
{
   int     i;
   int     depth;
   int     len;
   bt_tex_tree
         * top,
         * cur,
         * new;
   treestack
         * stack;

   i = 0;
   depth = 0;
   len = strlen (string);
   top = new_tex_tree (string);
   stack = NULL;

   cur = top;

   while (i < len)
   {
      switch (string[i])
      {
         case '{':                      /* go one level deeper */
         {
            if (i == len-1)             /* open brace in last character? */
            {
               string_warning ("unbalanced braces: { at end of string");
               goto error;
            }

            new = new_tex_tree (string+i+1);
            cur->child = new;
            push_treestack (&stack, cur);
            cur = new;
            depth++;
            break;
         }
         case '}':                      /* pop level(s) off */
         {
            while (i < len && string[i] == '}')
            {
               if (stack == NULL)
               {
                  string_warning ("unbalanced braces: extra }");
                  goto error;
               }
               cur = pop_treestack (&stack);
               depth--;
               i++;
            }
            i--;

            if (i == len-1)             /* reached end of string? */
            {
               if (depth > 0)           /* but not at depth 0 */
               {
                  string_warning ("unbalanced braces: not enough }'s");
                  goto error;
               }

               /*
                * if we get here, do nothing -- we've reached the end of
                * the string and are at depth 0, so will just fall out
                * of the while loop at the end of this iteration
                */
            }
            else                        /* still have characters left */
            {                           /* to worry about */
               new = new_tex_tree (string+i+1);
               cur->next = new;
               cur = new;
            }

            break;
         }
         default:
         {
            cur->len++;
         }

      } /* switch */

      i++;

   } /* while i */

   if (depth > 0)
   {
      string_warning ("unbalanced braces (not enough }'s)");
      goto error;
   }

   return top;

error:
   bt_free_tex_tree (&top);
   return NULL;

} /* bt_build_tex_tree() */


/* ------------------------------------------------------------------------
@NAME       : bt_free_tex_tree
@INPUT      : *top
@OUTPUT     : *top (set to NULL after it's free()'d)
@RETURNS    :
@DESCRIPTION: Frees up an entire tree created by bt_build_tex_tree().
@GLOBALS    :
@CALLS      : itself, free()
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
void
bt_free_tex_tree (bt_tex_tree **top)
{
   if ((*top)->child) bt_free_tex_tree (&(*top)->child);
   if ((*top)->next) bt_free_tex_tree (&(*top)->next);
   free (*top);
   *top = NULL;
}


/* ----------------------------------------------------------------------
 * Tree traversal functions
 */

/* ------------------------------------------------------------------------
@NAME       : bt_dump_tex_tree
@INPUT      : node
              depth
              stream
@OUTPUT     :
@RETURNS    :
@DESCRIPTION: Dumps a TeX tree: one node per line, depth indented according
              to depth.
@GLOBALS    :
@CALLS      : itself
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
void
bt_dump_tex_tree (bt_tex_tree *node, int depth, FILE *stream)
{
   char  buf[256];

   if (node == NULL)
      return;

   if (node->len > 255)
      internal_error ("augughgh! buf too small");
   strncpy (buf, node->start, node->len);
   buf[node->len] = (char) 0;

   fprintf (stream, "%*s[%s]\n", depth*2, "", buf);

   bt_dump_tex_tree (node->child, depth+1, stream);
   bt_dump_tex_tree (node->next, depth, stream);

}


/* ------------------------------------------------------------------------
@NAME       : count_length
@INPUT      : node
@OUTPUT     :
@RETURNS    :
@DESCRIPTION: Counts the total number of characters that will be needed
              to print a string reconstructed from a TeX tree.  (Length
              of string in each node, plus two [{ and }] for each down
              edge.)
@GLOBALS    :
@CALLS      : itself
@CALLERS    : bt_flatten_tex_tree
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
static int
count_length (bt_tex_tree *node)
{
   if (node == NULL) return 0;
   return
      node->len +
      (node->child ? 2 : 0) +
      count_length (node->child) +
      count_length (node->next);
}


/* ------------------------------------------------------------------------
@NAME       : flatten_tree
@INPUT      : node
              *offset
@OUTPUT     : *buf
              *offset
@RETURNS    :
@DESCRIPTION: Dumps a reconstructed string ("flat" representation of the
              tree) into a pre-allocated buffer, starting at a specified
              offset.
@GLOBALS    :
@CALLS      : itself
@CALLERS    : bt_flatten_tex_tree
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
static void
flatten_tree (bt_tex_tree *node, char *buf, int *offset)
{
   strncpy (buf + *offset, node->start, node->len);
   *offset += node->len;

   if (node->child)
   {
      buf[(*offset)++] = '{';
      flatten_tree (node->child, buf, offset);
      buf[(*offset)++] = '}';
   }

   if (node->next)
   {
      flatten_tree (node->next, buf, offset);
   }
}


/* ------------------------------------------------------------------------
@NAME       : bt_flatten_tex_tree
@INPUT      : top
@OUTPUT     :
@RETURNS    : flattened string representation of the tree (as a string
              allocated with malloc(), so you should free() it when
              you're done with it)
@DESCRIPTION: Counts the number of characters needed for a "flat"
              string representation of a tree, allocates a string of
              that size, and generates the string.
@GLOBALS    :
@CALLS      : count_length, flatten_tree
@CALLERS    :
@CREATED    : 1997/05/29, GPW
@MODIFIED   :
-------------------------------------------------------------------------- */
char *
bt_flatten_tex_tree (bt_tex_tree *top)
{
   int    len;
   int    offset;
   char * buf;

   len = count_length (top);
   buf = (char *) malloc (sizeof (char) * (len+1));
   offset = 0;
   flatten_tree (top, buf, &offset);
   return buf;
}