contrib/mdocml/eqn.c

   1 /*      $Id: eqn.c,v 1.56 2014/10/25 15:06:30 schwarze Exp $ */
   2 /*
   3  * Copyright (c) 2011, 2014 Kristaps Dzonsons <kristaps@bsd.lv>
   4  * Copyright (c) 2014 Ingo Schwarze <schwarze@openbsd.org>
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18 #include "config.h"
  19
  20 #include <sys/types.h>
  21
  22 #include <assert.h>
  23 #include <limits.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <time.h>
  28
  29 #include "mandoc.h"
  30 #include "mandoc_aux.h"
  31 #include "libmandoc.h"
  32 #include "libroff.h"
  33
  34 #define EQN_MSG(t, x) \
  35         mandoc_msg((t), (x)->parse, (x)->eqn.ln, (x)->eqn.pos, NULL)
  36 #define EQN_NEST_MAX     128 /* maximum nesting of defines */
  37 #define STRNEQ(p1, sz1, p2, sz2) \
  38         ((sz1) == (sz2) && 0 == strncmp((p1), (p2), (sz1)))
  39
  40 enum    eqn_tok {
  41         EQN_TOK_DYAD = 0,
  42         EQN_TOK_VEC,
  43         EQN_TOK_UNDER,
  44         EQN_TOK_BAR,
  45         EQN_TOK_TILDE,
  46         EQN_TOK_HAT,
  47         EQN_TOK_DOT,
  48         EQN_TOK_DOTDOT,
  49         EQN_TOK_FWD,
  50         EQN_TOK_BACK,
  51         EQN_TOK_DOWN,
  52         EQN_TOK_UP,
  53         EQN_TOK_FAT,
  54         EQN_TOK_ROMAN,
  55         EQN_TOK_ITALIC,
  56         EQN_TOK_BOLD,
  57         EQN_TOK_SIZE,
  58         EQN_TOK_SUB,
  59         EQN_TOK_SUP,
  60         EQN_TOK_SQRT,
  61         EQN_TOK_OVER,
  62         EQN_TOK_FROM,
  63         EQN_TOK_TO,
  64         EQN_TOK_BRACE_OPEN,
  65         EQN_TOK_BRACE_CLOSE,
  66         EQN_TOK_GSIZE,
  67         EQN_TOK_GFONT,
  68         EQN_TOK_MARK,
  69         EQN_TOK_LINEUP,
  70         EQN_TOK_LEFT,
  71         EQN_TOK_RIGHT,
  72         EQN_TOK_PILE,
  73         EQN_TOK_LPILE,
  74         EQN_TOK_RPILE,
  75         EQN_TOK_CPILE,
  76         EQN_TOK_MATRIX,
  77         EQN_TOK_CCOL,
  78         EQN_TOK_LCOL,
  79         EQN_TOK_RCOL,
  80         EQN_TOK_DELIM,
  81         EQN_TOK_DEFINE,
  82         EQN_TOK_TDEFINE,
  83         EQN_TOK_NDEFINE,
  84         EQN_TOK_UNDEF,
  85         EQN_TOK_EOF,
  86         EQN_TOK_ABOVE,
  87         EQN_TOK__MAX
  88 };
  89
  90 static  const char *eqn_toks[EQN_TOK__MAX] = {
  91         "dyad", /* EQN_TOK_DYAD */
  92         "vec", /* EQN_TOK_VEC */
  93         "under", /* EQN_TOK_UNDER */
  94         "bar", /* EQN_TOK_BAR */
  95         "tilde", /* EQN_TOK_TILDE */
  96         "hat", /* EQN_TOK_HAT */
  97         "dot", /* EQN_TOK_DOT */
  98         "dotdot", /* EQN_TOK_DOTDOT */
  99         "fwd", /* EQN_TOK_FWD * */
 100         "back", /* EQN_TOK_BACK */
 101         "down", /* EQN_TOK_DOWN */
 102         "up", /* EQN_TOK_UP */
 103         "fat", /* EQN_TOK_FAT */
 104         "roman", /* EQN_TOK_ROMAN */
 105         "italic", /* EQN_TOK_ITALIC */
 106         "bold", /* EQN_TOK_BOLD */
 107         "size", /* EQN_TOK_SIZE */
 108         "sub", /* EQN_TOK_SUB */
 109         "sup", /* EQN_TOK_SUP */
 110         "sqrt", /* EQN_TOK_SQRT */
 111         "over", /* EQN_TOK_OVER */
 112         "from", /* EQN_TOK_FROM */
 113         "to", /* EQN_TOK_TO */
 114         "{", /* EQN_TOK_BRACE_OPEN */
 115         "}", /* EQN_TOK_BRACE_CLOSE */
 116         "gsize", /* EQN_TOK_GSIZE */
 117         "gfont", /* EQN_TOK_GFONT */
 118         "mark", /* EQN_TOK_MARK */
 119         "lineup", /* EQN_TOK_LINEUP */
 120         "left", /* EQN_TOK_LEFT */
 121         "right", /* EQN_TOK_RIGHT */
 122         "pile", /* EQN_TOK_PILE */
 123         "lpile", /* EQN_TOK_LPILE */
 124         "rpile", /* EQN_TOK_RPILE */
 125         "cpile", /* EQN_TOK_CPILE */
 126         "matrix", /* EQN_TOK_MATRIX */
 127         "ccol", /* EQN_TOK_CCOL */
 128         "lcol", /* EQN_TOK_LCOL */
 129         "rcol", /* EQN_TOK_RCOL */
 130         "delim", /* EQN_TOK_DELIM */
 131         "define", /* EQN_TOK_DEFINE */
 132         "tdefine", /* EQN_TOK_TDEFINE */
 133         "ndefine", /* EQN_TOK_NDEFINE */
 134         "undef", /* EQN_TOK_UNDEF */
 135         NULL, /* EQN_TOK_EOF */
 136         "above", /* EQN_TOK_ABOVE */
 137 };
 138
 139 enum    eqn_symt {
 140         EQNSYM_alpha,
 141         EQNSYM_beta,
 142         EQNSYM_chi,
 143         EQNSYM_delta,
 144         EQNSYM_epsilon,
 145         EQNSYM_eta,
 146         EQNSYM_gamma,
 147         EQNSYM_iota,
 148         EQNSYM_kappa,
 149         EQNSYM_lambda,
 150         EQNSYM_mu,
 151         EQNSYM_nu,
 152         EQNSYM_omega,
 153         EQNSYM_omicron,
 154         EQNSYM_phi,
 155         EQNSYM_pi,
 156         EQNSYM_ps,
 157         EQNSYM_rho,
 158         EQNSYM_sigma,
 159         EQNSYM_tau,
 160         EQNSYM_theta,
 161         EQNSYM_upsilon,
 162         EQNSYM_xi,
 163         EQNSYM_zeta,
 164         EQNSYM_DELTA,
 165         EQNSYM_GAMMA,
 166         EQNSYM_LAMBDA,
 167         EQNSYM_OMEGA,
 168         EQNSYM_PHI,
 169         EQNSYM_PI,
 170         EQNSYM_PSI,
 171         EQNSYM_SIGMA,
 172         EQNSYM_THETA,
 173         EQNSYM_UPSILON,
 174         EQNSYM_XI,
 175         EQNSYM_inter,
 176         EQNSYM_union,
 177         EQNSYM_prod,
 178         EQNSYM_int,
 179         EQNSYM_sum,
 180         EQNSYM_grad,
 181         EQNSYM_del,
 182         EQNSYM_times,
 183         EQNSYM_cdot,
 184         EQNSYM_nothing,
 185         EQNSYM_approx,
 186         EQNSYM_prime,
 187         EQNSYM_half,
 188         EQNSYM_partial,
 189         EQNSYM_inf,
 190         EQNSYM_muchgreat,
 191         EQNSYM_muchless,
 192         EQNSYM_larrow,
 193         EQNSYM_rarrow,
 194         EQNSYM_pm,
 195         EQNSYM_nequal,
 196         EQNSYM_equiv,
 197         EQNSYM_lessequal,
 198         EQNSYM_moreequal,
 199         EQNSYM__MAX
 200 };
 201
 202 struct  eqnsym {
 203         const char      *str;
 204         const char      *sym;
 205 };
 206
 207 static  const struct eqnsym eqnsyms[EQNSYM__MAX] = {
 208         { "alpha", "*a" }, /* EQNSYM_alpha */
 209         { "beta", "*b" }, /* EQNSYM_beta */
 210         { "chi", "*x" }, /* EQNSYM_chi */
 211         { "delta", "*d" }, /* EQNSYM_delta */
 212         { "epsilon", "*e" }, /* EQNSYM_epsilon */
 213         { "eta", "*y" }, /* EQNSYM_eta */
 214         { "gamma", "*g" }, /* EQNSYM_gamma */
 215         { "iota", "*i" }, /* EQNSYM_iota */
 216         { "kappa", "*k" }, /* EQNSYM_kappa */
 217         { "lambda", "*l" }, /* EQNSYM_lambda */
 218         { "mu", "*m" }, /* EQNSYM_mu */
 219         { "nu", "*n" }, /* EQNSYM_nu */
 220         { "omega", "*w" }, /* EQNSYM_omega */
 221         { "omicron", "*o" }, /* EQNSYM_omicron */
 222         { "phi", "*f" }, /* EQNSYM_phi */
 223         { "pi", "*p" }, /* EQNSYM_pi */
 224         { "psi", "*q" }, /* EQNSYM_psi */
 225         { "rho", "*r" }, /* EQNSYM_rho */
 226         { "sigma", "*s" }, /* EQNSYM_sigma */
 227         { "tau", "*t" }, /* EQNSYM_tau */
 228         { "theta", "*h" }, /* EQNSYM_theta */
 229         { "upsilon", "*u" }, /* EQNSYM_upsilon */
 230         { "xi", "*c" }, /* EQNSYM_xi */
 231         { "zeta", "*z" }, /* EQNSYM_zeta */
 232         { "DELTA", "*D" }, /* EQNSYM_DELTA */
 233         { "GAMMA", "*G" }, /* EQNSYM_GAMMA */
 234         { "LAMBDA", "*L" }, /* EQNSYM_LAMBDA */
 235         { "OMEGA", "*W" }, /* EQNSYM_OMEGA */
 236         { "PHI", "*F" }, /* EQNSYM_PHI */
 237         { "PI", "*P" }, /* EQNSYM_PI */
 238         { "PSI", "*Q" }, /* EQNSYM_PSI */
 239         { "SIGMA", "*S" }, /* EQNSYM_SIGMA */
 240         { "THETA", "*H" }, /* EQNSYM_THETA */
 241         { "UPSILON", "*U" }, /* EQNSYM_UPSILON */
 242         { "XI", "*C" }, /* EQNSYM_XI */
 243         { "inter", "ca" }, /* EQNSYM_inter */
 244         { "union", "cu" }, /* EQNSYM_union */
 245         { "prod", "product" }, /* EQNSYM_prod */
 246         { "int", "integral" }, /* EQNSYM_int */
 247         { "sum", "sum" }, /* EQNSYM_sum */
 248         { "grad", "gr" }, /* EQNSYM_grad */
 249         { "del", "gr" }, /* EQNSYM_del */
 250         { "times", "mu" }, /* EQNSYM_times */
 251         { "cdot", "pc" }, /* EQNSYM_cdot */
 252         { "nothing", "&" }, /* EQNSYM_nothing */
 253         { "approx", "~~" }, /* EQNSYM_approx */
 254         { "prime", "aq" }, /* EQNSYM_prime */
 255         { "half", "12" }, /* EQNSYM_half */
 256         { "partial", "pd" }, /* EQNSYM_partial */
 257         { "inf", "if" }, /* EQNSYM_inf */
 258         { ">>", ">>" }, /* EQNSYM_muchgreat */
 259         { "<<", "<<" }, /* EQNSYM_muchless */
 260         { "<-", "<-" }, /* EQNSYM_larrow */
 261         { "->", "->" }, /* EQNSYM_rarrow */
 262         { "+-", "+-" }, /* EQNSYM_pm */
 263         { "!=", "!=" }, /* EQNSYM_nequal */
 264         { "==", "==" }, /* EQNSYM_equiv */
 265         { "<=", "<=" }, /* EQNSYM_lessequal */
 266         { ">=", ">=" }, /* EQNSYM_moreequal */
 267 };
 268
 269 enum rofferr
 270 eqn_read(struct eqn_node **epp, int ln,
 271                 const char *p, int pos, int *offs)
 272 {
 273         size_t           sz;
 274         struct eqn_node *ep;
 275         enum rofferr     er;
 276
 277         ep = *epp;
 278
 279         /*
 280          * If we're the terminating mark, unset our equation status and
 281          * validate the full equation.
 282          */
 283
 284         if (0 == strncmp(p, ".EN", 3)) {
 285                 er = eqn_end(epp);
 286                 p += 3;
 287                 while (' ' == *p || '\t' == *p)
 288                         p++;
 289                 if ('\0' == *p)
 290                         return(er);
 291                 mandoc_vmsg(MANDOCERR_ARG_SKIP, ep->parse,
 292                     ln, pos, "EN %s", p);
 293                 return(er);
 294         }
 295
 296         /*
 297          * Build up the full string, replacing all newlines with regular
 298          * whitespace.
 299          */
 300
 301         sz = strlen(p + pos) + 1;
 302         ep->data = mandoc_realloc(ep->data, ep->sz + sz + 1);
 303
 304         /* First invocation: nil terminate the string. */
 305
 306         if (0 == ep->sz)
 307                 *ep->data = '\0';
 308
 309         ep->sz += sz;
 310         strlcat(ep->data, p + pos, ep->sz + 1);
 311         strlcat(ep->data, " ", ep->sz + 1);
 312         return(ROFF_IGN);
 313 }
 314
 315 struct eqn_node *
 316 eqn_alloc(int pos, int line, struct mparse *parse)
 317 {
 318         struct eqn_node *p;
 319
 320         p = mandoc_calloc(1, sizeof(struct eqn_node));
 321
 322         p->parse = parse;
 323         p->eqn.ln = line;
 324         p->eqn.pos = pos;
 325         p->gsize = EQN_DEFSIZE;
 326
 327         return(p);
 328 }
 329
 330 /*
 331  * Find the key "key" of the give size within our eqn-defined values.
 332  */
 333 static struct eqn_def *
 334 eqn_def_find(struct eqn_node *ep, const char *key, size_t sz)
 335 {
 336         int              i;
 337
 338         for (i = 0; i < (int)ep->defsz; i++)
 339                 if (ep->defs[i].keysz && STRNEQ(ep->defs[i].key,
 340                     ep->defs[i].keysz, key, sz))
 341                         return(&ep->defs[i]);
 342
 343         return(NULL);
 344 }
 345
 346 /*
 347  * Get the next token from the input stream using the given quote
 348  * character.
 349  * Optionally make any replacements.
 350  */
 351 static const char *
 352 eqn_next(struct eqn_node *ep, char quote, size_t *sz, int repl)
 353 {
 354         char            *start, *next;
 355         int              q, diff, lim;
 356         size_t           ssz, dummy;
 357         struct eqn_def  *def;
 358
 359         if (NULL == sz)
 360                 sz = &dummy;
 361
 362         lim = 0;
 363         ep->rew = ep->cur;
 364 again:
 365         /* Prevent self-definitions. */
 366
 367         if (lim >= EQN_NEST_MAX) {
 368                 EQN_MSG(MANDOCERR_ROFFLOOP, ep);
 369                 return(NULL);
 370         }
 371
 372         ep->cur = ep->rew;
 373         start = &ep->data[(int)ep->cur];
 374         q = 0;
 375
 376         if ('\0' == *start)
 377                 return(NULL);
 378
 379         if (quote == *start) {
 380                 ep->cur++;
 381                 q = 1;
 382         }
 383
 384         start = &ep->data[(int)ep->cur];
 385
 386         if ( ! q) {
 387                 if ('{' == *start || '}' == *start)
 388                         ssz = 1;
 389                 else
 390                         ssz = strcspn(start + 1, " ^~\"{}\t") + 1;
 391                 next = start + (int)ssz;
 392                 if ('\0' == *next)
 393                         next = NULL;
 394         } else
 395                 next = strchr(start, quote);
 396
 397         if (NULL != next) {
 398                 *sz = (size_t)(next - start);
 399                 ep->cur += *sz;
 400                 if (q)
 401                         ep->cur++;
 402                 while (' ' == ep->data[(int)ep->cur] ||
 403                     '\t' == ep->data[(int)ep->cur] ||
 404                     '^' == ep->data[(int)ep->cur] ||
 405                     '~' == ep->data[(int)ep->cur])
 406                         ep->cur++;
 407         } else {
 408                 if (q)
 409                         EQN_MSG(MANDOCERR_ARG_QUOTE, ep);
 410                 next = strchr(start, '\0');
 411                 *sz = (size_t)(next - start);
 412                 ep->cur += *sz;
 413         }
 414
 415         /* Quotes aren't expanded for values. */
 416
 417         if (q || ! repl)
 418                 return(start);
 419
 420         if (NULL != (def = eqn_def_find(ep, start, *sz))) {
 421                 diff = def->valsz - *sz;
 422
 423                 if (def->valsz > *sz) {
 424                         ep->sz += diff;
 425                         ep->data = mandoc_realloc(ep->data, ep->sz + 1);
 426                         ep->data[ep->sz] = '\0';
 427                         start = &ep->data[(int)ep->rew];
 428                 }
 429
 430                 diff = def->valsz - *sz;
 431                 memmove(start + *sz + diff, start + *sz,
 432                     (strlen(start) - *sz) + 1);
 433                 memcpy(start, def->val, def->valsz);
 434                 goto again;
 435         }
 436
 437         return(start);
 438 }
 439
 440 /*
 441  * Get the next delimited token using the default current quote
 442  * character.
 443  */
 444 static const char *
 445 eqn_nexttok(struct eqn_node *ep, size_t *sz)
 446 {
 447
 448         return(eqn_next(ep, '"', sz, 1));
 449 }
 450
 451 /*
 452  * Get next token without replacement.
 453  */
 454 static const char *
 455 eqn_nextrawtok(struct eqn_node *ep, size_t *sz)
 456 {
 457
 458         return(eqn_next(ep, '"', sz, 0));
 459 }
 460
 461 /*
 462  * Parse a token from the stream of text.
 463  * A token consists of one of the recognised eqn(7) strings.
 464  * Strings are separated by delimiting marks.
 465  * This returns EQN_TOK_EOF when there are no more tokens.
 466  * If the token is an unrecognised string literal, then it returns
 467  * EQN_TOK__MAX and sets the "p" pointer to an allocated, nil-terminated
 468  * string.
 469  * This must be later freed with free(3).
 470  */
 471 static enum eqn_tok
 472 eqn_tok_parse(struct eqn_node *ep, char **p)
 473 {
 474         const char      *start;
 475         size_t           i, sz;
 476         int              quoted;
 477
 478         if (NULL != p)
 479                 *p = NULL;
 480
 481         quoted = ep->data[ep->cur] == '"';
 482
 483         if (NULL == (start = eqn_nexttok(ep, &sz)))
 484                 return(EQN_TOK_EOF);
 485
 486         if (quoted) {
 487                 if (p != NULL)
 488                         *p = mandoc_strndup(start, sz);
 489                 return(EQN_TOK__MAX);
 490         }
 491
 492         for (i = 0; i < EQN_TOK__MAX; i++) {
 493                 if (NULL == eqn_toks[i])
 494                         continue;
 495                 if (STRNEQ(start, sz, eqn_toks[i], strlen(eqn_toks[i])))
 496                         break;
 497         }
 498
 499         if (i == EQN_TOK__MAX && NULL != p)
 500                 *p = mandoc_strndup(start, sz);
 501
 502         return(i);
 503 }
 504
 505 static void
 506 eqn_box_free(struct eqn_box *bp)
 507 {
 508
 509         if (bp->first)
 510                 eqn_box_free(bp->first);
 511         if (bp->next)
 512                 eqn_box_free(bp->next);
 513
 514         free(bp->text);
 515         free(bp->left);
 516         free(bp->right);
 517         free(bp->top);
 518         free(bp->bottom);
 519         free(bp);
 520 }
 521
 522 /*
 523  * Allocate a box as the last child of the parent node.
 524  */
 525 static struct eqn_box *
 526 eqn_box_alloc(struct eqn_node *ep, struct eqn_box *parent)
 527 {
 528         struct eqn_box  *bp;
 529
 530         bp = mandoc_calloc(1, sizeof(struct eqn_box));
 531         bp->parent = parent;
 532         bp->parent->args++;
 533         bp->expectargs = UINT_MAX;
 534         bp->size = ep->gsize;
 535
 536         if (NULL != parent->first) {
 537                 parent->last->next = bp;
 538                 bp->prev = parent->last;
 539         } else
 540                 parent->first = bp;
 541
 542         parent->last = bp;
 543         return(bp);
 544 }
 545
 546 /*
 547  * Reparent the current last node (of the current parent) under a new
 548  * EQN_SUBEXPR as the first element.
 549  * Then return the new parent.
 550  * The new EQN_SUBEXPR will have a two-child limit.
 551  */
 552 static struct eqn_box *
 553 eqn_box_makebinary(struct eqn_node *ep,
 554         enum eqn_post pos, struct eqn_box *parent)
 555 {
 556         struct eqn_box  *b, *newb;
 557
 558         assert(NULL != parent->last);
 559         b = parent->last;
 560         if (parent->last == parent->first)
 561                 parent->first = NULL;
 562         parent->args--;
 563         parent->last = b->prev;
 564         b->prev = NULL;
 565         newb = eqn_box_alloc(ep, parent);
 566         newb->pos = pos;
 567         newb->type = EQN_SUBEXPR;
 568         newb->expectargs = 2;
 569         newb->args = 1;
 570         newb->first = newb->last = b;
 571         newb->first->next = NULL;
 572         b->parent = newb;
 573         return(newb);
 574 }
 575
 576 /*
 577  * Parse the "delim" control statement.
 578  */
 579 static void
 580 eqn_delim(struct eqn_node *ep)
 581 {
 582         const char      *start;
 583         size_t           sz;
 584
 585         if ((start = eqn_nextrawtok(ep, &sz)) == NULL)
 586                 mandoc_msg(MANDOCERR_REQ_EMPTY, ep->parse,
 587                     ep->eqn.ln, ep->eqn.pos, "delim");
 588         else if (strncmp(start, "off", 3) == 0)
 589                 ep->delim = 0;
 590         else if (strncmp(start, "on", 2) == 0) {
 591                 if (ep->odelim && ep->cdelim)
 592                         ep->delim = 1;
 593         } else if (start[1] != '\0') {
 594                 ep->odelim = start[0];
 595                 ep->cdelim = start[1];
 596                 ep->delim = 1;
 597         }
 598 }
 599
 600 /*
 601  * Undefine a previously-defined string.
 602  */
 603 static int
 604 eqn_undef(struct eqn_node *ep)
 605 {
 606         const char      *start;
 607         struct eqn_def  *def;
 608         size_t           sz;
 609
 610         if (NULL == (start = eqn_nextrawtok(ep, &sz))) {
 611                 EQN_MSG(MANDOCERR_EQNEOF, ep);
 612                 return(0);
 613         } else if (NULL != (def = eqn_def_find(ep, start, sz)))
 614                 def->keysz = 0;
 615
 616         return(1);
 617 }
 618
 619 static int
 620 eqn_def(struct eqn_node *ep)
 621 {
 622         const char      *start;
 623         size_t           sz;
 624         struct eqn_def  *def;
 625         int              i;
 626
 627         if (NULL == (start = eqn_nextrawtok(ep, &sz))) {
 628                 EQN_MSG(MANDOCERR_EQNEOF, ep);
 629                 return(0);
 630         }
 631
 632         /*
 633          * Search for a key that already exists.
 634          * Create a new key if none is found.
 635          */
 636         if (NULL == (def = eqn_def_find(ep, start, sz))) {
 637                 /* Find holes in string array. */
 638                 for (i = 0; i < (int)ep->defsz; i++)
 639                         if (0 == ep->defs[i].keysz)
 640                                 break;
 641
 642                 if (i == (int)ep->defsz) {
 643                         ep->defsz++;
 644                         ep->defs = mandoc_reallocarray(ep->defs,
 645                             ep->defsz, sizeof(struct eqn_def));
 646                         ep->defs[i].key = ep->defs[i].val = NULL;
 647                 }
 648
 649                 ep->defs[i].keysz = sz;
 650                 ep->defs[i].key = mandoc_realloc(
 651                     ep->defs[i].key, sz + 1);
 652
 653                 memcpy(ep->defs[i].key, start, sz);
 654                 ep->defs[i].key[(int)sz] = '\0';
 655                 def = &ep->defs[i];
 656         }
 657
 658         start = eqn_next(ep, ep->data[(int)ep->cur], &sz, 0);
 659
 660         if (NULL == start) {
 661                 EQN_MSG(MANDOCERR_EQNEOF, ep);
 662                 return(-1);
 663         }
 664
 665         def->valsz = sz;
 666         def->val = mandoc_realloc(def->val, sz + 1);
 667         memcpy(def->val, start, sz);
 668         def->val[(int)sz] = '\0';
 669         return(1);
 670 }
 671
 672 /*
 673  * Recursively parse an eqn(7) expression.
 674  */
 675 static int
 676 eqn_parse(struct eqn_node *ep, struct eqn_box *parent)
 677 {
 678         char            *p;
 679         enum eqn_tok     tok, subtok;
 680         enum eqn_post    pos;
 681         struct eqn_box  *cur;
 682         int              rc, size;
 683         size_t           i, sz;
 684         char             sym[64];
 685         const char      *start;
 686
 687         assert(parent != NULL);
 688         if (ep->data == NULL)
 689                 return(-1);
 690
 691 next_tok:
 692         tok = eqn_tok_parse(ep, &p);
 693
 694 this_tok:
 695         switch (tok) {
 696         case (EQN_TOK_UNDEF):
 697                 if ((rc = eqn_undef(ep)) <= 0)
 698                         return(rc);
 699                 break;
 700         case (EQN_TOK_NDEFINE):
 701         case (EQN_TOK_DEFINE):
 702                 if ((rc = eqn_def(ep)) <= 0)
 703                         return(rc);
 704                 break;
 705         case (EQN_TOK_TDEFINE):
 706                 if (NULL == eqn_nextrawtok(ep, NULL))
 707                         EQN_MSG(MANDOCERR_EQNEOF, ep);
 708                 else if (NULL == eqn_next(ep,
 709                                 ep->data[(int)ep->cur], NULL, 0))
 710                         EQN_MSG(MANDOCERR_EQNEOF, ep);
 711                 break;
 712         case (EQN_TOK_DELIM):
 713                 eqn_delim(ep);
 714                 break;
 715         case (EQN_TOK_GFONT):
 716                 if (eqn_nextrawtok(ep, NULL) == NULL)
 717                         mandoc_msg(MANDOCERR_REQ_EMPTY, ep->parse,
 718                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 719                 break;
 720         case (EQN_TOK_MARK):
 721         case (EQN_TOK_LINEUP):
 722                 /* Ignore these. */
 723                 break;
 724         case (EQN_TOK_DYAD):
 725         case (EQN_TOK_VEC):
 726         case (EQN_TOK_UNDER):
 727         case (EQN_TOK_BAR):
 728         case (EQN_TOK_TILDE):
 729         case (EQN_TOK_HAT):
 730         case (EQN_TOK_DOT):
 731         case (EQN_TOK_DOTDOT):
 732                 if (parent->last == NULL) {
 733                         mandoc_msg(MANDOCERR_EQN_NOBOX, ep->parse,
 734                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 735                         cur = eqn_box_alloc(ep, parent);
 736                         cur->type = EQN_TEXT;
 737                         cur->text = mandoc_strdup("");
 738                 }
 739                 parent = eqn_box_makebinary(ep, EQNPOS_NONE, parent);
 740                 parent->type = EQN_LISTONE;
 741                 parent->expectargs = 1;
 742                 switch (tok) {
 743                 case (EQN_TOK_DOTDOT):
 744                         strlcpy(sym, "\\[ad]", sizeof(sym));
 745                         break;
 746                 case (EQN_TOK_VEC):
 747                         strlcpy(sym, "\\[->]", sizeof(sym));
 748                         break;
 749                 case (EQN_TOK_DYAD):
 750                         strlcpy(sym, "\\[<>]", sizeof(sym));
 751                         break;
 752                 case (EQN_TOK_TILDE):
 753                         strlcpy(sym, "\\[a~]", sizeof(sym));
 754                         break;
 755                 case (EQN_TOK_UNDER):
 756                         strlcpy(sym, "\\[ul]", sizeof(sym));
 757                         break;
 758                 case (EQN_TOK_BAR):
 759                         strlcpy(sym, "\\[rl]", sizeof(sym));
 760                         break;
 761                 case (EQN_TOK_DOT):
 762                         strlcpy(sym, "\\[a.]", sizeof(sym));
 763                         break;
 764                 case (EQN_TOK_HAT):
 765                         strlcpy(sym, "\\[ha]", sizeof(sym));
 766                         break;
 767                 default:
 768                         abort();
 769                 }
 770
 771                 switch (tok) {
 772                 case (EQN_TOK_DOTDOT):
 773                 case (EQN_TOK_VEC):
 774                 case (EQN_TOK_DYAD):
 775                 case (EQN_TOK_TILDE):
 776                 case (EQN_TOK_BAR):
 777                 case (EQN_TOK_DOT):
 778                 case (EQN_TOK_HAT):
 779                         parent->top = mandoc_strdup(sym);
 780                         break;
 781                 case (EQN_TOK_UNDER):
 782                         parent->bottom = mandoc_strdup(sym);
 783                         break;
 784                 default:
 785                         abort();
 786                 }
 787                 parent = parent->parent;
 788                 break;
 789         case (EQN_TOK_FWD):
 790         case (EQN_TOK_BACK):
 791         case (EQN_TOK_DOWN):
 792         case (EQN_TOK_UP):
 793                 subtok = eqn_tok_parse(ep, NULL);
 794                 if (subtok != EQN_TOK__MAX) {
 795                         mandoc_msg(MANDOCERR_REQ_EMPTY, ep->parse,
 796                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 797                         tok = subtok;
 798                         goto this_tok;
 799                 }
 800                 break;
 801         case (EQN_TOK_FAT):
 802         case (EQN_TOK_ROMAN):
 803         case (EQN_TOK_ITALIC):
 804         case (EQN_TOK_BOLD):
 805                 while (parent->args == parent->expectargs)
 806                         parent = parent->parent;
 807                 /*
 808                  * These values apply to the next word or sequence of
 809                  * words; thus, we mark that we'll have a child with
 810                  * exactly one of those.
 811                  */
 812                 parent = eqn_box_alloc(ep, parent);
 813                 parent->type = EQN_LISTONE;
 814                 parent->expectargs = 1;
 815                 switch (tok) {
 816                 case (EQN_TOK_FAT):
 817                         parent->font = EQNFONT_FAT;
 818                         break;
 819                 case (EQN_TOK_ROMAN):
 820                         parent->font = EQNFONT_ROMAN;
 821                         break;
 822                 case (EQN_TOK_ITALIC):
 823                         parent->font = EQNFONT_ITALIC;
 824                         break;
 825                 case (EQN_TOK_BOLD):
 826                         parent->font = EQNFONT_BOLD;
 827                         break;
 828                 default:
 829                         abort();
 830                 }
 831                 break;
 832         case (EQN_TOK_SIZE):
 833         case (EQN_TOK_GSIZE):
 834                 /* Accept two values: integral size and a single. */
 835                 if (NULL == (start = eqn_nexttok(ep, &sz))) {
 836                         mandoc_msg(MANDOCERR_REQ_EMPTY, ep->parse,
 837                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 838                         break;
 839                 }
 840                 size = mandoc_strntoi(start, sz, 10);
 841                 if (-1 == size) {
 842                         mandoc_msg(MANDOCERR_IT_NONUM, ep->parse,
 843                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 844                         break;
 845                 }
 846                 if (EQN_TOK_GSIZE == tok) {
 847                         ep->gsize = size;
 848                         break;
 849                 }
 850                 parent = eqn_box_alloc(ep, parent);
 851                 parent->type = EQN_LISTONE;
 852                 parent->expectargs = 1;
 853                 parent->size = size;
 854                 break;
 855         case (EQN_TOK_FROM):
 856         case (EQN_TOK_TO):
 857         case (EQN_TOK_SUB):
 858         case (EQN_TOK_SUP):
 859                 /*
 860                  * We have a left-right-associative expression.
 861                  * Repivot under a positional node, open a child scope
 862                  * and keep on reading.
 863                  */
 864                 if (parent->last == NULL) {
 865                         mandoc_msg(MANDOCERR_EQN_NOBOX, ep->parse,
 866                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 867                         cur = eqn_box_alloc(ep, parent);
 868                         cur->type = EQN_TEXT;
 869                         cur->text = mandoc_strdup("");
 870                 }
 871                 /* Handle the "subsup" and "fromto" positions. */
 872                 if (EQN_TOK_SUP == tok && parent->pos == EQNPOS_SUB) {
 873                         parent->expectargs = 3;
 874                         parent->pos = EQNPOS_SUBSUP;
 875                         break;
 876                 }
 877                 if (EQN_TOK_TO == tok && parent->pos == EQNPOS_FROM) {
 878                         parent->expectargs = 3;
 879                         parent->pos = EQNPOS_FROMTO;
 880                         break;
 881                 }
 882                 switch (tok) {
 883                 case (EQN_TOK_FROM):
 884                         pos = EQNPOS_FROM;
 885                         break;
 886                 case (EQN_TOK_TO):
 887                         pos = EQNPOS_TO;
 888                         break;
 889                 case (EQN_TOK_SUP):
 890                         pos = EQNPOS_SUP;
 891                         break;
 892                 case (EQN_TOK_SUB):
 893                         pos = EQNPOS_SUB;
 894                         break;
 895                 default:
 896                         abort();
 897                 }
 898                 parent = eqn_box_makebinary(ep, pos, parent);
 899                 break;
 900         case (EQN_TOK_SQRT):
 901                 while (parent->args == parent->expectargs)
 902                         parent = parent->parent;
 903                 /*
 904                  * Accept a left-right-associative set of arguments just
 905                  * like sub and sup and friends but without rebalancing
 906                  * under a pivot.
 907                  */
 908                 parent = eqn_box_alloc(ep, parent);
 909                 parent->type = EQN_SUBEXPR;
 910                 parent->pos = EQNPOS_SQRT;
 911                 parent->expectargs = 1;
 912                 break;
 913         case (EQN_TOK_OVER):
 914                 /*
 915                  * We have a right-left-associative fraction.
 916                  * Close out anything that's currently open, then
 917                  * rebalance and continue reading.
 918                  */
 919                 if (parent->last == NULL) {
 920                         mandoc_msg(MANDOCERR_EQN_NOBOX, ep->parse,
 921                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 922                         cur = eqn_box_alloc(ep, parent);
 923                         cur->type = EQN_TEXT;
 924                         cur->text = mandoc_strdup("");
 925                 }
 926                 while (EQN_SUBEXPR == parent->type)
 927                         parent = parent->parent;
 928                 parent = eqn_box_makebinary(ep, EQNPOS_OVER, parent);
 929                 break;
 930         case (EQN_TOK_RIGHT):
 931         case (EQN_TOK_BRACE_CLOSE):
 932                 /*
 933                  * Close out the existing brace.
 934                  * FIXME: this is a shitty sentinel: we should really
 935                  * have a native EQN_BRACE type or whatnot.
 936                  */
 937                 for (cur = parent; cur != NULL; cur = cur->parent)
 938                         if (cur->type == EQN_LIST &&
 939                             (tok == EQN_TOK_BRACE_CLOSE ||
 940                              cur->left != NULL))
 941                                 break;
 942                 if (cur == NULL) {
 943                         mandoc_msg(MANDOCERR_BLK_NOTOPEN, ep->parse,
 944                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 945                         break;
 946                 }
 947                 parent = cur;
 948                 if (EQN_TOK_RIGHT == tok) {
 949                         if (NULL == (start = eqn_nexttok(ep, &sz))) {
 950                                 mandoc_msg(MANDOCERR_REQ_EMPTY,
 951                                     ep->parse, ep->eqn.ln,
 952                                     ep->eqn.pos, eqn_toks[tok]);
 953                                 break;
 954                         }
 955                         /* Handling depends on right/left. */
 956                         if (STRNEQ(start, sz, "ceiling", 7)) {
 957                                 strlcpy(sym, "\\[rc]", sizeof(sym));
 958                                 parent->right = mandoc_strdup(sym);
 959                         } else if (STRNEQ(start, sz, "floor", 5)) {
 960                                 strlcpy(sym, "\\[rf]", sizeof(sym));
 961                                 parent->right = mandoc_strdup(sym);
 962                         } else
 963                                 parent->right = mandoc_strndup(start, sz);
 964                 }
 965                 parent = parent->parent;
 966                 if (EQN_TOK_BRACE_CLOSE == tok && parent &&
 967                     (parent->type == EQN_PILE ||
 968                      parent->type == EQN_MATRIX))
 969                         parent = parent->parent;
 970                 /* Close out any "singleton" lists. */
 971                 while (parent->type == EQN_LISTONE &&
 972                     parent->args == parent->expectargs)
 973                         parent = parent->parent;
 974                 break;
 975         case (EQN_TOK_BRACE_OPEN):
 976         case (EQN_TOK_LEFT):
 977                 /*
 978                  * If we already have something in the stack and we're
 979                  * in an expression, then rewind til we're not any more
 980                  * (just like with the text node).
 981                  */
 982                 while (parent->args == parent->expectargs)
 983                         parent = parent->parent;
 984                 if (EQN_TOK_LEFT == tok &&
 985                     (start = eqn_nexttok(ep, &sz)) == NULL) {
 986                         mandoc_msg(MANDOCERR_REQ_EMPTY, ep->parse,
 987                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
 988                         break;
 989                 }
 990                 parent = eqn_box_alloc(ep, parent);
 991                 parent->type = EQN_LIST;
 992                 if (EQN_TOK_LEFT == tok) {
 993                         if (STRNEQ(start, sz, "ceiling", 7)) {
 994                                 strlcpy(sym, "\\[lc]", sizeof(sym));
 995                                 parent->left = mandoc_strdup(sym);
 996                         } else if (STRNEQ(start, sz, "floor", 5)) {
 997                                 strlcpy(sym, "\\[lf]", sizeof(sym));
 998                                 parent->left = mandoc_strdup(sym);
 999                         } else
1000                                 parent->left = mandoc_strndup(start, sz);
1001                 }
1002                 break;
1003         case (EQN_TOK_PILE):
1004         case (EQN_TOK_LPILE):
1005         case (EQN_TOK_RPILE):
1006         case (EQN_TOK_CPILE):
1007         case (EQN_TOK_CCOL):
1008         case (EQN_TOK_LCOL):
1009         case (EQN_TOK_RCOL):
1010                 while (parent->args == parent->expectargs)
1011                         parent = parent->parent;
1012                 parent = eqn_box_alloc(ep, parent);
1013                 parent->type = EQN_PILE;
1014                 parent->expectargs = 1;
1015                 break;
1016         case (EQN_TOK_ABOVE):
1017                 for (cur = parent; cur != NULL; cur = cur->parent)
1018                         if (cur->type == EQN_PILE)
1019                                 break;
1020                 if (cur == NULL) {
1021                         mandoc_msg(MANDOCERR_IT_STRAY, ep->parse,
1022                             ep->eqn.ln, ep->eqn.pos, eqn_toks[tok]);
1023                         break;
1024                 }
1025                 parent = eqn_box_alloc(ep, cur);
1026                 parent->type = EQN_LIST;
1027                 break;
1028         case (EQN_TOK_MATRIX):
1029                 while (parent->args == parent->expectargs)
1030                         parent = parent->parent;
1031                 parent = eqn_box_alloc(ep, parent);
1032                 parent->type = EQN_MATRIX;
1033                 parent->expectargs = 1;
1034                 break;
1035         case (EQN_TOK_EOF):
1036                 /*
1037                  * End of file!
1038                  * TODO: make sure we're not in an open subexpression.
1039                  */
1040                 return(0);
1041         default:
1042                 assert(tok == EQN_TOK__MAX);
1043                 assert(NULL != p);
1044                 /*
1045                  * If we already have something in the stack and we're
1046                  * in an expression, then rewind til we're not any more.
1047                  */
1048                 while (parent->args == parent->expectargs)
1049                         parent = parent->parent;
1050                 cur = eqn_box_alloc(ep, parent);
1051                 cur->type = EQN_TEXT;
1052                 for (i = 0; i < EQNSYM__MAX; i++)
1053                         if (0 == strcmp(eqnsyms[i].str, p)) {
1054                                 (void)snprintf(sym, sizeof(sym),
1055                                         "\\[%s]", eqnsyms[i].sym);
1056                                 cur->text = mandoc_strdup(sym);
1057                                 free(p);
1058                                 break;
1059                         }
1060
1061                 if (i == EQNSYM__MAX)
1062                         cur->text = p;
1063                 /*
1064                  * Post-process list status.
1065                  */
1066                 while (parent->type == EQN_LISTONE &&
1067                     parent->args == parent->expectargs)
1068                         parent = parent->parent;
1069                 break;
1070         }
1071         goto next_tok;
1072 }
1073
1074 enum rofferr
1075 eqn_end(struct eqn_node **epp)
1076 {
1077         struct eqn_node *ep;
1078
1079         ep = *epp;
1080         *epp = NULL;
1081
1082         ep->eqn.root = mandoc_calloc(1, sizeof(struct eqn_box));
1083         ep->eqn.root->expectargs = UINT_MAX;
1084         return(0 == eqn_parse(ep, ep->eqn.root) ? ROFF_EQN : ROFF_IGN);
1085 }
1086
1087 void
1088 eqn_free(struct eqn_node *p)
1089 {
1090         int              i;
1091
1092         eqn_box_free(p->eqn.root);
1093
1094         for (i = 0; i < (int)p->defsz; i++) {
1095                 free(p->defs[i].key);
1096                 free(p->defs[i].val);
1097         }
1098
1099         free(p->data);
1100         free(p->defs);
1101         free(p);
1102 }