1 /* $Id: eqn.c,v 1.38 2011/07/25 15:37:00 kristaps Exp $ */
3 * Copyright (c) 2011 Kristaps Dzonsons <kristaps@bsd.lv>
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
29 #include "libmandoc.h"
32 #define EQN_NEST_MAX 128 /* maximum nesting of defines */
33 #define EQN_MSG(t, x) mandoc_msg((t), (x)->parse, (x)->eqn.ln, (x)->eqn.pos, NULL)
125 #define STRNEQ(p1, sz1, p2, sz2) \
126 ((sz1) == (sz2) && 0 == strncmp((p1), (p2), (sz1)))
127 #define EQNSTREQ(x, p, sz) \
128 STRNEQ((x)->name, (x)->sz, (p), (sz))
132 int (*fp)(struct eqn_node *);
141 static enum eqn_rest eqn_box(struct eqn_node *, struct eqn_box *);
142 static struct eqn_box *eqn_box_alloc(struct eqn_node *,
144 static void eqn_box_free(struct eqn_box *);
145 static struct eqn_def *eqn_def_find(struct eqn_node *,
146 const char *, size_t);
147 static int eqn_do_gfont(struct eqn_node *);
148 static int eqn_do_gsize(struct eqn_node *);
149 static int eqn_do_define(struct eqn_node *);
150 static int eqn_do_ign1(struct eqn_node *);
151 static int eqn_do_ign2(struct eqn_node *);
152 static int eqn_do_tdefine(struct eqn_node *);
153 static int eqn_do_undef(struct eqn_node *);
154 static enum eqn_rest eqn_eqn(struct eqn_node *, struct eqn_box *);
155 static enum eqn_rest eqn_list(struct eqn_node *, struct eqn_box *);
156 static enum eqn_rest eqn_matrix(struct eqn_node *, struct eqn_box *);
157 static const char *eqn_nexttok(struct eqn_node *, size_t *);
158 static const char *eqn_nextrawtok(struct eqn_node *, size_t *);
159 static const char *eqn_next(struct eqn_node *,
160 char, size_t *, int);
161 static void eqn_rewind(struct eqn_node *);
163 static const struct eqnpart eqnparts[EQN__MAX] = {
164 { { "define", 6 }, eqn_do_define }, /* EQN_DEFINE */
165 { { "ndefine", 7 }, eqn_do_define }, /* EQN_NDEFINE */
166 { { "tdefine", 7 }, eqn_do_tdefine }, /* EQN_TDEFINE */
167 { { "set", 3 }, eqn_do_ign2 }, /* EQN_SET */
168 { { "undef", 5 }, eqn_do_undef }, /* EQN_UNDEF */
169 { { "gfont", 5 }, eqn_do_gfont }, /* EQN_GFONT */
170 { { "gsize", 5 }, eqn_do_gsize }, /* EQN_GSIZE */
171 { { "back", 4 }, eqn_do_ign1 }, /* EQN_BACK */
172 { { "fwd", 3 }, eqn_do_ign1 }, /* EQN_FWD */
173 { { "up", 2 }, eqn_do_ign1 }, /* EQN_UP */
174 { { "down", 4 }, eqn_do_ign1 }, /* EQN_DOWN */
177 static const struct eqnstr eqnmarks[EQNMARK__MAX] = {
178 { "", 0 }, /* EQNMARK_NONE */
179 { "dot", 3 }, /* EQNMARK_DOT */
180 { "dotdot", 6 }, /* EQNMARK_DOTDOT */
181 { "hat", 3 }, /* EQNMARK_HAT */
182 { "tilde", 5 }, /* EQNMARK_TILDE */
183 { "vec", 3 }, /* EQNMARK_VEC */
184 { "dyad", 4 }, /* EQNMARK_DYAD */
185 { "bar", 3 }, /* EQNMARK_BAR */
186 { "under", 5 }, /* EQNMARK_UNDER */
189 static const struct eqnstr eqnfonts[EQNFONT__MAX] = {
190 { "", 0 }, /* EQNFONT_NONE */
191 { "roman", 5 }, /* EQNFONT_ROMAN */
192 { "bold", 4 }, /* EQNFONT_BOLD */
193 { "fat", 3 }, /* EQNFONT_FAT */
194 { "italic", 6 }, /* EQNFONT_ITALIC */
197 static const struct eqnstr eqnposs[EQNPOS__MAX] = {
198 { "", 0 }, /* EQNPOS_NONE */
199 { "over", 4 }, /* EQNPOS_OVER */
200 { "sup", 3 }, /* EQNPOS_SUP */
201 { "sub", 3 }, /* EQNPOS_SUB */
202 { "to", 2 }, /* EQNPOS_TO */
203 { "from", 4 }, /* EQNPOS_FROM */
206 static const struct eqnstr eqnpiles[EQNPILE__MAX] = {
207 { "", 0 }, /* EQNPILE_NONE */
208 { "pile", 4 }, /* EQNPILE_PILE */
209 { "cpile", 5 }, /* EQNPILE_CPILE */
210 { "rpile", 5 }, /* EQNPILE_RPILE */
211 { "lpile", 5 }, /* EQNPILE_LPILE */
212 { "col", 3 }, /* EQNPILE_COL */
213 { "ccol", 4 }, /* EQNPILE_CCOL */
214 { "rcol", 4 }, /* EQNPILE_RCOL */
215 { "lcol", 4 }, /* EQNPILE_LCOL */
218 static const struct eqnsym eqnsyms[EQNSYM__MAX] = {
219 { { "alpha", 5 }, "*a" }, /* EQNSYM_alpha */
220 { { "beta", 4 }, "*b" }, /* EQNSYM_beta */
221 { { "chi", 3 }, "*x" }, /* EQNSYM_chi */
222 { { "delta", 5 }, "*d" }, /* EQNSYM_delta */
223 { { "epsilon", 7 }, "*e" }, /* EQNSYM_epsilon */
224 { { "eta", 3 }, "*y" }, /* EQNSYM_eta */
225 { { "gamma", 5 }, "*g" }, /* EQNSYM_gamma */
226 { { "iota", 4 }, "*i" }, /* EQNSYM_iota */
227 { { "kappa", 5 }, "*k" }, /* EQNSYM_kappa */
228 { { "lambda", 6 }, "*l" }, /* EQNSYM_lambda */
229 { { "mu", 2 }, "*m" }, /* EQNSYM_mu */
230 { { "nu", 2 }, "*n" }, /* EQNSYM_nu */
231 { { "omega", 5 }, "*w" }, /* EQNSYM_omega */
232 { { "omicron", 7 }, "*o" }, /* EQNSYM_omicron */
233 { { "phi", 3 }, "*f" }, /* EQNSYM_phi */
234 { { "pi", 2 }, "*p" }, /* EQNSYM_pi */
235 { { "psi", 2 }, "*q" }, /* EQNSYM_psi */
236 { { "rho", 3 }, "*r" }, /* EQNSYM_rho */
237 { { "sigma", 5 }, "*s" }, /* EQNSYM_sigma */
238 { { "tau", 3 }, "*t" }, /* EQNSYM_tau */
239 { { "theta", 5 }, "*h" }, /* EQNSYM_theta */
240 { { "upsilon", 7 }, "*u" }, /* EQNSYM_upsilon */
241 { { "xi", 2 }, "*c" }, /* EQNSYM_xi */
242 { { "zeta", 4 }, "*z" }, /* EQNSYM_zeta */
243 { { "DELTA", 5 }, "*D" }, /* EQNSYM_DELTA */
244 { { "GAMMA", 5 }, "*G" }, /* EQNSYM_GAMMA */
245 { { "LAMBDA", 6 }, "*L" }, /* EQNSYM_LAMBDA */
246 { { "OMEGA", 5 }, "*W" }, /* EQNSYM_OMEGA */
247 { { "PHI", 3 }, "*F" }, /* EQNSYM_PHI */
248 { { "PI", 2 }, "*P" }, /* EQNSYM_PI */
249 { { "PSI", 3 }, "*Q" }, /* EQNSYM_PSI */
250 { { "SIGMA", 5 }, "*S" }, /* EQNSYM_SIGMA */
251 { { "THETA", 5 }, "*H" }, /* EQNSYM_THETA */
252 { { "UPSILON", 7 }, "*U" }, /* EQNSYM_UPSILON */
253 { { "XI", 2 }, "*C" }, /* EQNSYM_XI */
254 { { "inter", 5 }, "ca" }, /* EQNSYM_inter */
255 { { "union", 5 }, "cu" }, /* EQNSYM_union */
256 { { "prod", 4 }, "product" }, /* EQNSYM_prod */
257 { { "int", 3 }, "integral" }, /* EQNSYM_int */
258 { { "sum", 3 }, "sum" }, /* EQNSYM_sum */
259 { { "grad", 4 }, "gr" }, /* EQNSYM_grad */
260 { { "del", 3 }, "gr" }, /* EQNSYM_del */
261 { { "times", 5 }, "mu" }, /* EQNSYM_times */
262 { { "cdot", 4 }, "pc" }, /* EQNSYM_cdot */
263 { { "nothing", 7 }, "&" }, /* EQNSYM_nothing */
264 { { "approx", 6 }, "~~" }, /* EQNSYM_approx */
265 { { "prime", 5 }, "aq" }, /* EQNSYM_prime */
266 { { "half", 4 }, "12" }, /* EQNSYM_half */
267 { { "partial", 7 }, "pd" }, /* EQNSYM_partial */
268 { { "inf", 3 }, "if" }, /* EQNSYM_inf */
269 { { ">>", 2 }, ">>" }, /* EQNSYM_muchgreat */
270 { { "<<", 2 }, "<<" }, /* EQNSYM_muchless */
271 { { "<-", 2 }, "<-" }, /* EQNSYM_larrow */
272 { { "->", 2 }, "->" }, /* EQNSYM_rarrow */
273 { { "+-", 2 }, "+-" }, /* EQNSYM_pm */
274 { { "!=", 2 }, "!=" }, /* EQNSYM_nequal */
275 { { "==", 2 }, "==" }, /* EQNSYM_equiv */
276 { { "<=", 2 }, "<=" }, /* EQNSYM_lessequal */
277 { { ">=", 2 }, ">=" }, /* EQNSYM_moreequal */
282 eqn_read(struct eqn_node **epp, int ln,
283 const char *p, int pos, int *offs)
292 * If we're the terminating mark, unset our equation status and
293 * validate the full equation.
296 if (0 == strncmp(p, ".EN", 3)) {
299 while (' ' == *p || '\t' == *p)
303 mandoc_msg(MANDOCERR_ARGSLOST, ep->parse, ln, pos, NULL);
308 * Build up the full string, replacing all newlines with regular
312 sz = strlen(p + pos) + 1;
313 ep->data = mandoc_realloc(ep->data, ep->sz + sz + 1);
315 /* First invocation: nil terminate the string. */
321 strlcat(ep->data, p + pos, ep->sz + 1);
322 strlcat(ep->data, " ", ep->sz + 1);
327 eqn_alloc(const char *name, int pos, int line, struct mparse *parse)
333 p = mandoc_calloc(1, sizeof(struct eqn_node));
335 if (name && '\0' != *name) {
340 end = name + (int)sz;
341 } while (' ' == *end || '\t' == *end);
342 p->eqn.name = mandoc_strndup(name, sz + 1);
348 p->gsize = EQN_DEFSIZE;
354 eqn_end(struct eqn_node **epp)
357 struct eqn_box *root;
363 ep->eqn.root = mandoc_calloc(1, sizeof(struct eqn_box));
366 root->type = EQN_ROOT;
371 if (EQN_DESCOPE == (c = eqn_eqn(ep, root))) {
372 EQN_MSG(MANDOCERR_EQNNSCOPE, ep);
376 return(EQN_EOF == c ? ROFF_EQN : ROFF_IGN);
380 eqn_eqn(struct eqn_node *ep, struct eqn_box *last)
385 bp = eqn_box_alloc(ep, last);
386 bp->type = EQN_SUBEXPR;
388 while (EQN_OK == (c = eqn_box(ep, bp)))
395 eqn_matrix(struct eqn_node *ep, struct eqn_box *last)
402 bp = eqn_box_alloc(ep, last);
403 bp->type = EQN_MATRIX;
405 if (NULL == (start = eqn_nexttok(ep, &sz))) {
406 EQN_MSG(MANDOCERR_EQNEOF, ep);
409 if ( ! STRNEQ(start, sz, "{", 1)) {
410 EQN_MSG(MANDOCERR_EQNSYNT, ep);
414 while (EQN_OK == (c = eqn_box(ep, bp)))
415 switch (bp->last->pile) {
423 EQN_MSG(MANDOCERR_EQNSYNT, ep);
427 if (EQN_DESCOPE != c) {
429 EQN_MSG(MANDOCERR_EQNEOF, ep);
434 start = eqn_nexttok(ep, &sz);
436 if (STRNEQ(start, sz, "}", 1))
439 EQN_MSG(MANDOCERR_EQNBADSCOPE, ep);
444 eqn_list(struct eqn_node *ep, struct eqn_box *last)
451 bp = eqn_box_alloc(ep, last);
454 if (NULL == (start = eqn_nexttok(ep, &sz))) {
455 EQN_MSG(MANDOCERR_EQNEOF, ep);
458 if ( ! STRNEQ(start, sz, "{", 1)) {
459 EQN_MSG(MANDOCERR_EQNSYNT, ep);
463 while (EQN_DESCOPE == (c = eqn_eqn(ep, bp))) {
465 start = eqn_nexttok(ep, &sz);
467 if ( ! STRNEQ(start, sz, "above", 5))
471 if (EQN_DESCOPE != c) {
473 EQN_MSG(MANDOCERR_EQNSCOPE, ep);
478 start = eqn_nexttok(ep, &sz);
480 if (STRNEQ(start, sz, "}", 1))
483 EQN_MSG(MANDOCERR_EQNBADSCOPE, ep);
488 eqn_box(struct eqn_node *ep, struct eqn_box *last)
498 if (NULL == (start = eqn_nexttok(ep, &sz)))
501 if (STRNEQ(start, sz, "}", 1))
503 else if (STRNEQ(start, sz, "right", 5))
505 else if (STRNEQ(start, sz, "above", 5))
507 else if (STRNEQ(start, sz, "mark", 4))
509 else if (STRNEQ(start, sz, "lineup", 6))
512 for (i = 0; i < (int)EQN__MAX; i++) {
513 if ( ! EQNSTREQ(&eqnparts[i].str, start, sz))
515 return((*eqnparts[i].fp)(ep) ?
519 if (STRNEQ(start, sz, "{", 1)) {
520 if (EQN_DESCOPE != (c = eqn_eqn(ep, last))) {
522 EQN_MSG(MANDOCERR_EQNSCOPE, ep);
526 start = eqn_nexttok(ep, &sz);
528 if (STRNEQ(start, sz, "}", 1))
530 EQN_MSG(MANDOCERR_EQNBADSCOPE, ep);
534 for (i = 0; i < (int)EQNPILE__MAX; i++) {
535 if ( ! EQNSTREQ(&eqnpiles[i], start, sz))
537 if (EQN_OK == (c = eqn_list(ep, last)))
538 last->last->pile = (enum eqn_pilet)i;
542 if (STRNEQ(start, sz, "matrix", 6))
543 return(eqn_matrix(ep, last));
545 if (STRNEQ(start, sz, "left", 4)) {
546 if (NULL == (start = eqn_nexttok(ep, &sz))) {
547 EQN_MSG(MANDOCERR_EQNEOF, ep);
550 left = mandoc_strndup(start, sz);
551 c = eqn_eqn(ep, last);
553 last->last->left = left;
556 if (EQN_DESCOPE != c)
560 start = eqn_nexttok(ep, &sz);
562 if ( ! STRNEQ(start, sz, "right", 5))
564 if (NULL == (start = eqn_nexttok(ep, &sz))) {
565 EQN_MSG(MANDOCERR_EQNEOF, ep);
568 last->last->right = mandoc_strndup(start, sz);
572 for (i = 0; i < (int)EQNPOS__MAX; i++) {
573 if ( ! EQNSTREQ(&eqnposs[i], start, sz))
575 if (NULL == last->last) {
576 EQN_MSG(MANDOCERR_EQNSYNT, ep);
579 last->last->pos = (enum eqn_post)i;
580 if (EQN_EOF == (c = eqn_box(ep, last))) {
581 EQN_MSG(MANDOCERR_EQNEOF, ep);
587 for (i = 0; i < (int)EQNMARK__MAX; i++) {
588 if ( ! EQNSTREQ(&eqnmarks[i], start, sz))
590 if (NULL == last->last) {
591 EQN_MSG(MANDOCERR_EQNSYNT, ep);
594 last->last->mark = (enum eqn_markt)i;
595 if (EQN_EOF == (c = eqn_box(ep, last))) {
596 EQN_MSG(MANDOCERR_EQNEOF, ep);
602 for (i = 0; i < (int)EQNFONT__MAX; i++) {
603 if ( ! EQNSTREQ(&eqnfonts[i], start, sz))
605 if (EQN_EOF == (c = eqn_box(ep, last))) {
606 EQN_MSG(MANDOCERR_EQNEOF, ep);
608 } else if (EQN_OK == c)
609 last->last->font = (enum eqn_fontt)i;
613 if (STRNEQ(start, sz, "size", 4)) {
614 if (NULL == (start = eqn_nexttok(ep, &sz))) {
615 EQN_MSG(MANDOCERR_EQNEOF, ep);
618 size = mandoc_strntoi(start, sz, 10);
619 if (EQN_EOF == (c = eqn_box(ep, last))) {
620 EQN_MSG(MANDOCERR_EQNEOF, ep);
622 } else if (EQN_OK != c)
624 last->last->size = size;
627 bp = eqn_box_alloc(ep, last);
629 for (i = 0; i < (int)EQNSYM__MAX; i++)
630 if (EQNSTREQ(&eqnsyms[i].str, start, sz)) {
632 snprintf(sym, 62, "\\[%s]", eqnsyms[i].sym);
633 bp->text = mandoc_strdup(sym);
637 bp->text = mandoc_strndup(start, sz);
642 eqn_free(struct eqn_node *p)
646 eqn_box_free(p->eqn.root);
648 for (i = 0; i < (int)p->defsz; i++) {
649 free(p->defs[i].key);
650 free(p->defs[i].val);
659 static struct eqn_box *
660 eqn_box_alloc(struct eqn_node *ep, struct eqn_box *parent)
664 bp = mandoc_calloc(1, sizeof(struct eqn_box));
666 bp->size = ep->gsize;
668 if (NULL == parent->first)
671 parent->last->next = bp;
678 eqn_box_free(struct eqn_box *bp)
682 eqn_box_free(bp->first);
684 eqn_box_free(bp->next);
693 eqn_nextrawtok(struct eqn_node *ep, size_t *sz)
696 return(eqn_next(ep, '"', sz, 0));
700 eqn_nexttok(struct eqn_node *ep, size_t *sz)
703 return(eqn_next(ep, '"', sz, 1));
707 eqn_rewind(struct eqn_node *ep)
714 eqn_next(struct eqn_node *ep, char quote, size_t *sz, int repl)
727 /* Prevent self-definitions. */
729 if (lim >= EQN_NEST_MAX) {
730 EQN_MSG(MANDOCERR_ROFFLOOP, ep);
735 start = &ep->data[(int)ep->cur];
741 if (quote == *start) {
746 start = &ep->data[(int)ep->cur];
749 if ('{' == *start || '}' == *start)
752 ssz = strcspn(start + 1, " ^~\"{}\t") + 1;
753 next = start + (int)ssz;
757 next = strchr(start, quote);
760 *sz = (size_t)(next - start);
764 while (' ' == ep->data[(int)ep->cur] ||
765 '\t' == ep->data[(int)ep->cur] ||
766 '^' == ep->data[(int)ep->cur] ||
767 '~' == ep->data[(int)ep->cur])
771 EQN_MSG(MANDOCERR_BADQUOTE, ep);
772 next = strchr(start, '\0');
773 *sz = (size_t)(next - start);
777 /* Quotes aren't expanded for values. */
782 if (NULL != (def = eqn_def_find(ep, start, *sz))) {
783 diff = def->valsz - *sz;
785 if (def->valsz > *sz) {
787 ep->data = mandoc_realloc(ep->data, ep->sz + 1);
788 ep->data[ep->sz] = '\0';
789 start = &ep->data[(int)ep->rew];
792 diff = def->valsz - *sz;
793 memmove(start + *sz + diff, start + *sz,
794 (strlen(start) - *sz) + 1);
795 memcpy(start, def->val, def->valsz);
803 eqn_do_ign1(struct eqn_node *ep)
806 if (NULL == eqn_nextrawtok(ep, NULL))
807 EQN_MSG(MANDOCERR_EQNEOF, ep);
815 eqn_do_ign2(struct eqn_node *ep)
818 if (NULL == eqn_nextrawtok(ep, NULL))
819 EQN_MSG(MANDOCERR_EQNEOF, ep);
820 else if (NULL == eqn_nextrawtok(ep, NULL))
821 EQN_MSG(MANDOCERR_EQNEOF, ep);
829 eqn_do_tdefine(struct eqn_node *ep)
832 if (NULL == eqn_nextrawtok(ep, NULL))
833 EQN_MSG(MANDOCERR_EQNEOF, ep);
834 else if (NULL == eqn_next(ep, ep->data[(int)ep->cur], NULL, 0))
835 EQN_MSG(MANDOCERR_EQNEOF, ep);
843 eqn_do_define(struct eqn_node *ep)
850 if (NULL == (start = eqn_nextrawtok(ep, &sz))) {
851 EQN_MSG(MANDOCERR_EQNEOF, ep);
856 * Search for a key that already exists.
857 * Create a new key if none is found.
860 if (NULL == (def = eqn_def_find(ep, start, sz))) {
861 /* Find holes in string array. */
862 for (i = 0; i < (int)ep->defsz; i++)
863 if (0 == ep->defs[i].keysz)
866 if (i == (int)ep->defsz) {
868 ep->defs = mandoc_realloc
869 (ep->defs, ep->defsz *
870 sizeof(struct eqn_def));
871 ep->defs[i].key = ep->defs[i].val = NULL;
874 ep->defs[i].keysz = sz;
875 ep->defs[i].key = mandoc_realloc
876 (ep->defs[i].key, sz + 1);
878 memcpy(ep->defs[i].key, start, sz);
879 ep->defs[i].key[(int)sz] = '\0';
883 start = eqn_next(ep, ep->data[(int)ep->cur], &sz, 0);
886 EQN_MSG(MANDOCERR_EQNEOF, ep);
891 def->val = mandoc_realloc(def->val, sz + 1);
892 memcpy(def->val, start, sz);
893 def->val[(int)sz] = '\0';
898 eqn_do_gfont(struct eqn_node *ep)
901 if (NULL == eqn_nextrawtok(ep, NULL)) {
902 EQN_MSG(MANDOCERR_EQNEOF, ep);
909 eqn_do_gsize(struct eqn_node *ep)
914 if (NULL == (start = eqn_nextrawtok(ep, &sz))) {
915 EQN_MSG(MANDOCERR_EQNEOF, ep);
918 ep->gsize = mandoc_strntoi(start, sz, 10);
923 eqn_do_undef(struct eqn_node *ep)
929 if (NULL == (start = eqn_nextrawtok(ep, &sz))) {
930 EQN_MSG(MANDOCERR_EQNEOF, ep);
932 } else if (NULL != (def = eqn_def_find(ep, start, sz)))
938 static struct eqn_def *
939 eqn_def_find(struct eqn_node *ep, const char *key, size_t sz)
943 for (i = 0; i < (int)ep->defsz; i++)
944 if (ep->defs[i].keysz && STRNEQ(ep->defs[i].key,
945 ep->defs[i].keysz, key, sz))
946 return(&ep->defs[i]);