eqn.c

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