Reduce memory and time consumption on certain malformed input files

[mandoc.git] / tbl_layout.c

diff --git a/tbl_layout.c b/tbl_layout.c
index 05018f3e884a9f5ea010aa4ba424388cb8e6719a..033074afbb107bf7e9105014d6d481a6ce2eb543 100644 (file)
--- a/tbl_layout.c
+++ b/tbl_layout.c
@@ -1,6 +1,7 @@
-/*     $Id: tbl_layout.c,v 1.5 2011/01/01 22:19:15 kristaps Exp $ */
+/*     $Id: tbl_layout.c,v 1.30 2014/11/25 21:41:47 schwarze Exp $ */

 /*
 /*

- * Copyright (c) 2009, 2010 Kristaps Dzonsons <kristaps@bsd.lv>
+ * Copyright (c) 2009, 2010, 2011 Kristaps Dzonsons <kristaps@bsd.lv>
+ * Copyright (c) 2012, 2014 Ingo Schwarze <schwarze@openbsd.org>

  *
  * Permission to use, copy, modify, and distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
  *
  * Permission to use, copy, modify, and distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above


@@ -14,13 +15,17 @@
  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */

-#include <assert.h>
+#include "config.h"
+
+#include <sys/types.h>
+

 #include <ctype.h>
 #include <stdlib.h>
 #include <string.h>
 #include <time.h>
 
 #include "mandoc.h"
 #include <ctype.h>
 #include <stdlib.h>
 #include <string.h>
 #include <time.h>
 
 #include "mandoc.h"

+#include "mandoc_aux.h"

 #include "libmandoc.h"
 #include "libroff.h"
 
 #include "libmandoc.h"
 #include "libroff.h"
 


@@ -29,6 +34,12 @@ struct       tbl_phrase {
        enum tbl_cellt   key;
 };
 
        enum tbl_cellt   key;
 };
 

+/*
+ * FIXME: we can make this parse a lot nicer by, when an error is
+ * encountered in a layout key, bailing to the next key (i.e. to the
+ * next whitespace then continuing).
+ */
+

 #define        KEYS_MAX         11
 
 static const struct tbl_phrase keys[KEYS_MAX] = {
 #define        KEYS_MAX         11
 
 static const struct tbl_phrase keys[KEYS_MAX] = {


@@ -41,49 +52,76 @@ static      const struct tbl_phrase keys[KEYS_MAX] = {
        { '^',           TBL_CELL_DOWN },
        { '-',           TBL_CELL_HORIZ },
        { '_',           TBL_CELL_HORIZ },
        { '^',           TBL_CELL_DOWN },
        { '-',           TBL_CELL_HORIZ },
        { '_',           TBL_CELL_HORIZ },

-       { '=',           TBL_CELL_DHORIZ },
-       { '|',           TBL_CELL_VERT }
+       { '=',           TBL_CELL_DHORIZ }

 };
 
 };
 

-static int              mods(struct tbl *, struct tbl_cell *, 
+static int              mods(struct tbl_node *, struct tbl_cell *,

                                int, const char *, int *);
                                int, const char *, int *);

-static int              cell(struct tbl *, struct tbl_row *, 
+static int              cell(struct tbl_node *, struct tbl_row *,

                                int, const char *, int *);
                                int, const char *, int *);

-static void             row(struct tbl *, int, const char *, int *);
-static struct tbl_cell *cell_alloc(struct tbl *, 
-                               struct tbl_row *, enum tbl_cellt);
-static void             head_adjust(const struct tbl_cell *, 
-                               struct tbl_head *);
+static struct tbl_cell *cell_alloc(struct tbl_node *, struct tbl_row *,
+                               enum tbl_cellt, int vert);
+

 
 static int
 
 static int

-mods(struct tbl *tbl, struct tbl_cell *cp, 
+mods(struct tbl_node *tbl, struct tbl_cell *cp,

                int ln, const char *p, int *pos)
 {
        char             buf[5];
        int              i;
 
                int ln, const char *p, int *pos)
 {
        char             buf[5];
        int              i;
 

+       /* Not all types accept modifiers. */
+
+       switch (cp->pos) {
+       case TBL_CELL_DOWN:
+               /* FALLTHROUGH */
+       case TBL_CELL_HORIZ:
+               /* FALLTHROUGH */
+       case TBL_CELL_DHORIZ:
+               return(1);
+       default:
+               break;
+       }
+

 mod:
 mod:

-       /* 
+       /*

         * XXX: since, at least for now, modifiers are non-conflicting
         * (are separable by value, regardless of position), we let
         * modifiers come in any order.  The existing tbl doesn't let
         * this happen.
         */
        switch (p[*pos]) {
         * XXX: since, at least for now, modifiers are non-conflicting
         * (are separable by value, regardless of position), we let
         * modifiers come in any order.  The existing tbl doesn't let
         * this happen.
         */
        switch (p[*pos]) {

-       case ('\0'):
+       case '\0':
+               /* FALLTHROUGH */
+       case ' ':

                /* FALLTHROUGH */
                /* FALLTHROUGH */

-       case (' '):
+       case '\t':

                /* FALLTHROUGH */
                /* FALLTHROUGH */

-       case ('\t'):
+       case ',':

                /* FALLTHROUGH */
                /* FALLTHROUGH */

-       case (','):
+       case '.':

                /* FALLTHROUGH */
                /* FALLTHROUGH */

-       case ('.'):
+       case '|':

                return(1);
        default:
                break;
        }
 
                return(1);
        default:
                break;
        }
 

+       /* Throw away parenthesised expression. */
+
+       if ('(' == p[*pos]) {
+               (*pos)++;
+               while (p[*pos] && ')' != p[*pos])
+                       (*pos)++;
+               if (')' == p[*pos]) {
+                       (*pos)++;
+                       goto mod;
+               }
+               mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse,
+                   ln, *pos, NULL);
+               return(0);
+       }
+

        /* Parse numerical spacing from modifier string. */
 
        if (isdigit((unsigned char)p[*pos])) {
        /* Parse numerical spacing from modifier string. */
 
        if (isdigit((unsigned char)p[*pos])) {


@@ -97,170 +135,223 @@ mod:
                /* No greater than 4 digits. */
 
                if (4 == i) {
                /* No greater than 4 digits. */
 
                if (4 == i) {

-                       TBL_MSG(tbl, MANDOCERR_TBLLAYOUT, ln, *pos);
+                       mandoc_msg(MANDOCERR_TBLLAYOUT,
+                           tbl->parse, ln, *pos, NULL);

                        return(0);
                }
 
                *pos += i;
                        return(0);
                }
 
                *pos += i;

-               cp->spacing = atoi(buf);
+               cp->spacing = (size_t)atoi(buf);

 
                goto mod;
                /* NOTREACHED */
 
                goto mod;
                /* NOTREACHED */

-       } 
+       }

 
        /* TODO: GNU has many more extensions. */
 
 
        /* TODO: GNU has many more extensions. */
 

-       switch (tolower(p[(*pos)++])) {
-       case ('z'):
+       switch (tolower((unsigned char)p[(*pos)++])) {
+       case 'z':

                cp->flags |= TBL_CELL_WIGN;
                goto mod;
                cp->flags |= TBL_CELL_WIGN;
                goto mod;

-       case ('u'):
+       case 'u':

                cp->flags |= TBL_CELL_UP;
                goto mod;
                cp->flags |= TBL_CELL_UP;
                goto mod;

-       case ('e'):
+       case 'e':

                cp->flags |= TBL_CELL_EQUAL;
                goto mod;
                cp->flags |= TBL_CELL_EQUAL;
                goto mod;

-       case ('t'):
+       case 't':

                cp->flags |= TBL_CELL_TALIGN;
                goto mod;
                cp->flags |= TBL_CELL_TALIGN;
                goto mod;

-       case ('d'):
+       case 'd':

                cp->flags |= TBL_CELL_BALIGN;
                goto mod;
                cp->flags |= TBL_CELL_BALIGN;
                goto mod;

-       case ('f'):
+       case 'w':  /* XXX for now, ignore minimal column width */
+               goto mod;
+       case 'x':
+               cp->flags |= TBL_CELL_WMAX;
+               goto mod;
+       case 'f':

                break;
                break;

-       case ('b'):
+       case 'r':

                /* FALLTHROUGH */
                /* FALLTHROUGH */

-       case ('i'):
+       case 'b':
+               /* FALLTHROUGH */
+       case 'i':

                (*pos)--;
                break;
        default:
                (*pos)--;
                break;
        default:

-               TBL_MSG(tbl, MANDOCERR_TBLLAYOUT, ln, *pos - 1);
+               mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse,
+                   ln, *pos - 1, NULL);

                return(0);
        }
 
                return(0);
        }
 

-       switch (tolower(p[(*pos)++])) {
-       case ('b'):
+       switch (tolower((unsigned char)p[(*pos)++])) {
+       case '3':
+               /* FALLTHROUGH */
+       case 'b':

                cp->flags |= TBL_CELL_BOLD;
                goto mod;
                cp->flags |= TBL_CELL_BOLD;
                goto mod;

-       case ('i'):
+       case '2':
+               /* FALLTHROUGH */
+       case 'i':

                cp->flags |= TBL_CELL_ITALIC;
                goto mod;
                cp->flags |= TBL_CELL_ITALIC;
                goto mod;

+       case '1':
+               /* FALLTHROUGH */
+       case 'r':
+               goto mod;

        default:
                break;
        }
        default:
                break;
        }

+       if (isalnum((unsigned char)p[*pos - 1])) {
+               mandoc_vmsg(MANDOCERR_FT_BAD, tbl->parse,
+                   ln, *pos - 1, "TS f%c", p[*pos - 1]);
+               goto mod;
+       }

 
 

-       TBL_MSG(tbl, MANDOCERR_TBLLAYOUT, ln, *pos - 1);
+       mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse,
+           ln, *pos - 1, NULL);

        return(0);
 }
 
 static int
        return(0);
 }
 
 static int

-cell(struct tbl *tbl, struct tbl_row *rp, 
+cell(struct tbl_node *tbl, struct tbl_row *rp,

                int ln, const char *p, int *pos)
 {
                int ln, const char *p, int *pos)
 {

-       int              i;
+       int              vert, i;

        enum tbl_cellt   c;
 
        enum tbl_cellt   c;
 

-       /* Parse the column position (`r', `R', `|', ...). */
+       /* Handle vertical lines. */
+
+       for (vert = 0; '|' == p[*pos]; ++*pos)
+               vert++;
+       while (' ' == p[*pos])
+               (*pos)++;
+
+       /* Handle trailing vertical lines */
+
+       if ('.' == p[*pos] || '\0' == p[*pos]) {
+               rp->vert = vert;
+               return(1);
+       }
+
+       /* Parse the column position (`c', `l', `r', ...). */

 
        for (i = 0; i < KEYS_MAX; i++)
 
        for (i = 0; i < KEYS_MAX; i++)

-               if (tolower(p[*pos]) == keys[i].name)
+               if (tolower((unsigned char)p[*pos]) == keys[i].name)

                        break;
 
        if (KEYS_MAX == i) {
                        break;
 
        if (KEYS_MAX == i) {

-               TBL_MSG(tbl, MANDOCERR_TBLLAYOUT, ln, *pos);
+               mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse,
+                   ln, *pos, NULL);

                return(0);
        }
 
                return(0);
        }
 

-       (*pos)++;

        c = keys[i].key;
 
        c = keys[i].key;
 

-       /* Extra check for the double-vertical. */
-
-       if (TBL_CELL_VERT == c && '|' == p[*pos]) {
-               (*pos)++;
-               c = TBL_CELL_DVERT;
-       } 
-       
-       /* Disallow adjacent spacers. */
+       /*
+        * If a span cell is found first, raise a warning and abort the
+        * parse.  If a span cell is found and the last layout element
+        * isn't a "normal" layout, bail.
+        *
+        * FIXME: recover from this somehow?
+        */

 
 

-       if (rp->last && (TBL_CELL_VERT == c || TBL_CELL_DVERT == c) &&
-                       (TBL_CELL_VERT == rp->last->pos || 
-                        TBL_CELL_DVERT == rp->last->pos)) {
-               TBL_MSG(tbl, MANDOCERR_TBLLAYOUT, ln, *pos - 1);
-               return(0);
+       if (TBL_CELL_SPAN == c) {
+               if (NULL == rp->first) {
+                       mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse,
+                           ln, *pos, NULL);
+                       return(0);
+               } else if (rp->last)
+                       switch (rp->last->pos) {
+                       case TBL_CELL_HORIZ:
+                               /* FALLTHROUGH */
+                       case TBL_CELL_DHORIZ:
+                               mandoc_msg(MANDOCERR_TBLLAYOUT,
+                                   tbl->parse, ln, *pos, NULL);
+                               return(0);
+                       default:
+                               break;
+                       }

        }
 
        }
 

-       /* Allocate cell then parse its modifiers. */
-
-       return(mods(tbl, cell_alloc(tbl, rp, c), ln, p, pos));
-}
-
-
-static void
-row(struct tbl *tbl, int ln, const char *p, int *pos)
-{
-       struct tbl_row  *rp;
-
-row:   /*
-        * EBNF describing this section:
-        *
-        * row          ::= row_list [:space:]* [.]?[\n]
-        * row_list     ::= [:space:]* row_elem row_tail
-        * row_tail     ::= [:space:]*[,] row_list |
-        *                  epsilon
-        * row_elem     ::= [\t\ ]*[:alpha:]+
+       /*
+        * If a vertical spanner is found, we may not be in the first
+        * row.

         */
 
         */
 

-       rp = mandoc_calloc(1, sizeof(struct tbl_row));
-       if (tbl->last_row) {
-               tbl->last_row->next = rp;
-               tbl->last_row = rp;
-       } else
-               tbl->last_row = tbl->first_row = rp;
+       if (TBL_CELL_DOWN == c && rp == tbl->first_row) {
+               mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse, ln, *pos, NULL);
+               return(0);
+       }

 
 

-cell:
-       while (isspace((unsigned char)p[*pos]))
-               (*pos)++;
+       (*pos)++;

 
 

-       /* Safely exit layout context. */
+       /* Disallow adjacent spacers. */

 
 

-       if ('.' == p[*pos]) {
-               tbl->part = TBL_PART_DATA;
-               if (NULL == tbl->first_row) 
-                       TBL_MSG(tbl, MANDOCERR_TBLNOLAYOUT, ln, *pos);
-               (*pos)++;
-               return;
+       if (vert > 2) {
+               mandoc_msg(MANDOCERR_TBLLAYOUT, tbl->parse, ln, *pos - 1, NULL);
+               return(0);

        }
 
        }
 

-       /* End (and possibly restart) a row. */
-
-       if (',' == p[*pos]) {
-               (*pos)++;
-               goto row;
-       } else if ('\0' == p[*pos])
-               return;
-
-       if ( ! cell(tbl, rp, ln, p, pos))
-               return;
+       /* Allocate cell then parse its modifiers. */

 
 

-       goto cell;
-       /* NOTREACHED */
+       return(mods(tbl, cell_alloc(tbl, rp, c, vert), ln, p, pos));

 }
 
 int
 }
 
 int

-tbl_layout(struct tbl *tbl, int ln, const char *p)
+tbl_layout(struct tbl_node *tbl, int ln, const char *p)

 {
 {

+       struct tbl_row  *rp;

        int              pos;
 
        pos = 0;
        int              pos;
 
        pos = 0;

-       row(tbl, ln, p, &pos);
+       rp = NULL;
+
+       for (;;) {
+               /* Skip whitespace before and after each cell. */
+
+               while (isspace((unsigned char)p[pos]))
+                       pos++;
+
+               switch (p[pos]) {
+               case ',':  /* Next row on this input line. */
+                       pos++;
+                       rp = NULL;
+                       continue;
+               case '\0':  /* Next row on next input line. */
+                       return(1);
+               case '.':  /* End of layout. */
+                       pos++;
+                       tbl->part = TBL_PART_DATA;
+                       if (tbl->first_row != NULL)
+                               return(1);
+                       mandoc_msg(MANDOCERR_TBLNOLAYOUT,
+                           tbl->parse, ln, pos, NULL);
+                       rp = mandoc_calloc(1, sizeof(*rp));
+                       cell_alloc(tbl, rp, TBL_CELL_LEFT, 0);
+                       tbl->first_row = tbl->last_row = rp;
+                       return(1);
+               default:  /* Cell. */
+                       break;
+               }

 
 

-       /* Always succeed. */
-       return(1);
+               if (rp == NULL) {  /* First cell on this line. */
+                       rp = mandoc_calloc(1, sizeof(*rp));
+                       if (tbl->last_row)
+                               tbl->last_row->next = rp;
+                       else
+                               tbl->first_row = rp;
+                       tbl->last_row = rp;
+               }
+               if ( ! cell(tbl, rp, ln, p, &pos))
+                       return(1);
+       }

 }
 
 static struct tbl_cell *
 }
 
 static struct tbl_cell *

-cell_alloc(struct tbl *tbl, struct tbl_row *rp, enum tbl_cellt pos)
+cell_alloc(struct tbl_node *tbl, struct tbl_row *rp, enum tbl_cellt pos,
+               int vert)

 {
        struct tbl_cell *p, *pp;
        struct tbl_head *h, *hp;
 {
        struct tbl_cell *p, *pp;
        struct tbl_head *h, *hp;


@@ -268,104 +359,35 @@ cell_alloc(struct tbl *tbl, struct tbl_row *rp, enum tbl_cellt pos)
        p = mandoc_calloc(1, sizeof(struct tbl_cell));
 
        if (NULL != (pp = rp->last)) {
        p = mandoc_calloc(1, sizeof(struct tbl_cell));
 
        if (NULL != (pp = rp->last)) {

-               rp->last->next = p;
-               rp->last = p;
-       } else
-               rp->last = rp->first = p;
+               pp->next = p;
+               h = pp->head->next;
+       } else {
+               rp->first = p;
+               h = tbl->first_head;
+       }
+       rp->last = p;

 
        p->pos = pos;
 
        p->pos = pos;

+       p->vert = vert;

 
 

-       /*
-        * This is a little bit complicated.  Here we determine the
-        * header the corresponds to a cell.  We add headers dynamically
-        * when need be or re-use them, otherwise.  As an example, given
-        * the following:
-        *
-        *      1  c || l 
-        *      2  | c | l
-        *      3  l l
-        *      3  || c | l |.
-        *
-        * We first add the new headers (as there are none) in (1); then
-        * in (2) we insert the first spanner (as it doesn't match up
-        * with the header); then we re-use the prior data headers,
-        * skipping over the spanners; then we re-use everything and add
-        * a last spanner.  Note that VERT headers are made into DVERT
-        * ones.
-        */
-
-       h = pp ? pp->head->prev : tbl->first_head;
+       /* Re-use header. */

 
        if (h) {
 
        if (h) {

-               /* Re-use data header. */
-               if (TBL_HEAD_DATA == h->pos && 
-                               (TBL_CELL_VERT != p->pos &&
-                                TBL_CELL_DVERT != p->pos)) {
-                       p->head = h;
-                       return(p);
-               }
-
-               /* Re-use spanner header. */
-               if (TBL_HEAD_DATA != h->pos && 
-                               (TBL_CELL_VERT == p->pos ||
-                                TBL_CELL_DVERT == p->pos)) {
-                       head_adjust(p, h);
-                       p->head = h;
-                       return(p);
-               }
-
-               /* Right-shift headers with a new spanner. */
-               if (TBL_HEAD_DATA == h->pos && 
-                               (TBL_CELL_VERT == p->pos ||
-                                TBL_CELL_DVERT == p->pos)) {
-                       hp = mandoc_calloc(1, sizeof(struct tbl_head));
-                       hp->prev = h->prev;
-                       if (h->prev)
-                               h->prev->next = hp;
-                       h->prev = hp;
-                       hp->next = h;
-                       head_adjust(p, hp);
-                       p->head = hp;
-                       return(p);
-               }
-
-               if (NULL != (h = h->next)) {
-                       head_adjust(p, h);
-                       p->head = h;
-                       return(p);
-               }
-
-               /* Fall through to default case... */
+               p->head = h;
+               return(p);

        }
 
        hp = mandoc_calloc(1, sizeof(struct tbl_head));
        }
 
        hp = mandoc_calloc(1, sizeof(struct tbl_head));

+       hp->ident = tbl->opts.cols++;
+       hp->vert = vert;

 
        if (tbl->last_head) {
                hp->prev = tbl->last_head;
                tbl->last_head->next = hp;
 
        if (tbl->last_head) {
                hp->prev = tbl->last_head;
                tbl->last_head->next = hp;

-               tbl->last_head = hp;

        } else
        } else

-               tbl->last_head = tbl->first_head = hp;
+               tbl->first_head = hp;
+       tbl->last_head = hp;

 
 

-       head_adjust(p, hp);

        p->head = hp;
        return(p);
 }
        p->head = hp;
        return(p);
 }

-
-static void
-head_adjust(const struct tbl_cell *cell, struct tbl_head *head)
-{
-       if (TBL_CELL_VERT != cell->pos &&
-                       TBL_CELL_DVERT != cell->pos) {
-               head->pos = TBL_HEAD_DATA;
-               return;
-       }
-
-       if (TBL_CELL_VERT == cell->pos)
-               if (TBL_HEAD_DVERT != head->pos)
-                       head->pos = TBL_HEAD_VERT;
-
-       if (TBL_CELL_DVERT == cell->pos)
-               head->pos = TBL_HEAD_DVERT;
-}
-