Bug Summary

File:src/usr.bin/mandoc/eqn.c
Warning:line 527, column 22
Access to field 'next' results in a dereference of a null pointer (loaded from field 'last')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.4 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name eqn.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.bin/mandoc/obj -resource-dir /usr/local/llvm16/lib/clang/16 -internal-isystem /usr/local/llvm16/lib/clang/16/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -fdebug-compilation-dir=/usr/src/usr.bin/mandoc/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fcf-protection=branch -fno-jump-tables -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/scan/2024-01-11-140451-98009-1 -x c /usr/src/usr.bin/mandoc/eqn.c
1/* $OpenBSD: eqn.c,v 1.49 2022/12/26 19:16:02 jmc Exp $ */
2/*
3 * Copyright (c) 2014, 2015, 2017, 2018, 2020, 2022
4 * Ingo Schwarze <schwarze@openbsd.org>
5 * Copyright (c) 2011, 2014 Kristaps Dzonsons <kristaps@bsd.lv>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19#include <sys/types.h>
20
21#include <assert.h>
22#include <ctype.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_aux.h"
30#include "mandoc.h"
31#include "roff.h"
32#include "eqn.h"
33#include "libmandoc.h"
34#include "eqn_parse.h"
35
36#define EQN_NEST_MAX128 128 /* maximum nesting of defines */
37#define STRNEQ(p1, sz1, p2, sz2)((sz1) == (sz2) && 0 == strncmp((p1), (p2), (sz1))) \
38 ((sz1) == (sz2) && 0 == strncmp((p1), (p2), (sz1)))
39
40enum 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_ABOVE,
86 EQN_TOK__MAX,
87 EQN_TOK_FUNC,
88 EQN_TOK_QUOTED,
89 EQN_TOK_SYM,
90 EQN_TOK_EOF
91};
92
93static const char *eqn_toks[EQN_TOK__MAX] = {
94 "dyad", /* EQN_TOK_DYAD */
95 "vec", /* EQN_TOK_VEC */
96 "under", /* EQN_TOK_UNDER */
97 "bar", /* EQN_TOK_BAR */
98 "tilde", /* EQN_TOK_TILDE */
99 "hat", /* EQN_TOK_HAT */
100 "dot", /* EQN_TOK_DOT */
101 "dotdot", /* EQN_TOK_DOTDOT */
102 "fwd", /* EQN_TOK_FWD * */
103 "back", /* EQN_TOK_BACK */
104 "down", /* EQN_TOK_DOWN */
105 "up", /* EQN_TOK_UP */
106 "fat", /* EQN_TOK_FAT */
107 "roman", /* EQN_TOK_ROMAN */
108 "italic", /* EQN_TOK_ITALIC */
109 "bold", /* EQN_TOK_BOLD */
110 "size", /* EQN_TOK_SIZE */
111 "sub", /* EQN_TOK_SUB */
112 "sup", /* EQN_TOK_SUP */
113 "sqrt", /* EQN_TOK_SQRT */
114 "over", /* EQN_TOK_OVER */
115 "from", /* EQN_TOK_FROM */
116 "to", /* EQN_TOK_TO */
117 "{", /* EQN_TOK_BRACE_OPEN */
118 "}", /* EQN_TOK_BRACE_CLOSE */
119 "gsize", /* EQN_TOK_GSIZE */
120 "gfont", /* EQN_TOK_GFONT */
121 "mark", /* EQN_TOK_MARK */
122 "lineup", /* EQN_TOK_LINEUP */
123 "left", /* EQN_TOK_LEFT */
124 "right", /* EQN_TOK_RIGHT */
125 "pile", /* EQN_TOK_PILE */
126 "lpile", /* EQN_TOK_LPILE */
127 "rpile", /* EQN_TOK_RPILE */
128 "cpile", /* EQN_TOK_CPILE */
129 "matrix", /* EQN_TOK_MATRIX */
130 "ccol", /* EQN_TOK_CCOL */
131 "lcol", /* EQN_TOK_LCOL */
132 "rcol", /* EQN_TOK_RCOL */
133 "delim", /* EQN_TOK_DELIM */
134 "define", /* EQN_TOK_DEFINE */
135 "tdefine", /* EQN_TOK_TDEFINE */
136 "ndefine", /* EQN_TOK_NDEFINE */
137 "undef", /* EQN_TOK_UNDEF */
138 "above", /* EQN_TOK_ABOVE */
139};
140
141static const char *const eqn_func[] = {
142 "acos", "acsc", "and", "arc", "asec", "asin", "atan",
143 "cos", "cosh", "coth", "csc", "det", "exp", "for",
144 "if", "lim", "ln", "log", "max", "min",
145 "sec", "sin", "sinh", "tan", "tanh", "Im", "Re",
146};
147
148enum eqn_symt {
149 EQNSYM_alpha = 0,
150 EQNSYM_beta,
151 EQNSYM_chi,
152 EQNSYM_delta,
153 EQNSYM_epsilon,
154 EQNSYM_eta,
155 EQNSYM_gamma,
156 EQNSYM_iota,
157 EQNSYM_kappa,
158 EQNSYM_lambda,
159 EQNSYM_mu,
160 EQNSYM_nu,
161 EQNSYM_omega,
162 EQNSYM_omicron,
163 EQNSYM_phi,
164 EQNSYM_pi,
165 EQNSYM_ps,
166 EQNSYM_rho,
167 EQNSYM_sigma,
168 EQNSYM_tau,
169 EQNSYM_theta,
170 EQNSYM_upsilon,
171 EQNSYM_xi,
172 EQNSYM_zeta,
173 EQNSYM_DELTA,
174 EQNSYM_GAMMA,
175 EQNSYM_LAMBDA,
176 EQNSYM_OMEGA,
177 EQNSYM_PHI,
178 EQNSYM_PI,
179 EQNSYM_PSI,
180 EQNSYM_SIGMA,
181 EQNSYM_THETA,
182 EQNSYM_UPSILON,
183 EQNSYM_XI,
184 EQNSYM_inter,
185 EQNSYM_union,
186 EQNSYM_prod,
187 EQNSYM_int,
188 EQNSYM_sum,
189 EQNSYM_grad,
190 EQNSYM_del,
191 EQNSYM_times,
192 EQNSYM_cdot,
193 EQNSYM_nothing,
194 EQNSYM_approx,
195 EQNSYM_prime,
196 EQNSYM_half,
197 EQNSYM_partial,
198 EQNSYM_inf,
199 EQNSYM_muchgreat,
200 EQNSYM_muchless,
201 EQNSYM_larrow,
202 EQNSYM_rarrow,
203 EQNSYM_pm,
204 EQNSYM_nequal,
205 EQNSYM_equiv,
206 EQNSYM_lessequal,
207 EQNSYM_moreequal,
208 EQNSYM_minus,
209 EQNSYM__MAX
210};
211
212struct eqnsym {
213 const char *str;
214 const char *sym;
215};
216
217static const struct eqnsym eqnsyms[EQNSYM__MAX] = {
218 { "alpha", "*a" }, /* EQNSYM_alpha */
219 { "beta", "*b" }, /* EQNSYM_beta */
220 { "chi", "*x" }, /* EQNSYM_chi */
221 { "delta", "*d" }, /* EQNSYM_delta */
222 { "epsilon", "*e" }, /* EQNSYM_epsilon */
223 { "eta", "*y" }, /* EQNSYM_eta */
224 { "gamma", "*g" }, /* EQNSYM_gamma */
225 { "iota", "*i" }, /* EQNSYM_iota */
226 { "kappa", "*k" }, /* EQNSYM_kappa */
227 { "lambda", "*l" }, /* EQNSYM_lambda */
228 { "mu", "*m" }, /* EQNSYM_mu */
229 { "nu", "*n" }, /* EQNSYM_nu */
230 { "omega", "*w" }, /* EQNSYM_omega */
231 { "omicron", "*o" }, /* EQNSYM_omicron */
232 { "phi", "*f" }, /* EQNSYM_phi */
233 { "pi", "*p" }, /* EQNSYM_pi */
234 { "psi", "*q" }, /* EQNSYM_psi */
235 { "rho", "*r" }, /* EQNSYM_rho */
236 { "sigma", "*s" }, /* EQNSYM_sigma */
237 { "tau", "*t" }, /* EQNSYM_tau */
238 { "theta", "*h" }, /* EQNSYM_theta */
239 { "upsilon", "*u" }, /* EQNSYM_upsilon */
240 { "xi", "*c" }, /* EQNSYM_xi */
241 { "zeta", "*z" }, /* EQNSYM_zeta */
242 { "DELTA", "*D" }, /* EQNSYM_DELTA */
243 { "GAMMA", "*G" }, /* EQNSYM_GAMMA */
244 { "LAMBDA", "*L" }, /* EQNSYM_LAMBDA */
245 { "OMEGA", "*W" }, /* EQNSYM_OMEGA */
246 { "PHI", "*F" }, /* EQNSYM_PHI */
247 { "PI", "*P" }, /* EQNSYM_PI */
248 { "PSI", "*Q" }, /* EQNSYM_PSI */
249 { "SIGMA", "*S" }, /* EQNSYM_SIGMA */
250 { "THETA", "*H" }, /* EQNSYM_THETA */
251 { "UPSILON", "*U" }, /* EQNSYM_UPSILON */
252 { "XI", "*C" }, /* EQNSYM_XI */
253 { "inter", "ca" }, /* EQNSYM_inter */
254 { "union", "cu" }, /* EQNSYM_union */
255 { "prod", "product" }, /* EQNSYM_prod */
256 { "int", "integral" }, /* EQNSYM_int */
257 { "sum", "sum" }, /* EQNSYM_sum */
258 { "grad", "gr" }, /* EQNSYM_grad */
259 { "del", "gr" }, /* EQNSYM_del */
260 { "times", "mu" }, /* EQNSYM_times */
261 { "cdot", "pc" }, /* EQNSYM_cdot */
262 { "nothing", "&" }, /* EQNSYM_nothing */
263 { "approx", "~~" }, /* EQNSYM_approx */
264 { "prime", "fm" }, /* EQNSYM_prime */
265 { "half", "12" }, /* EQNSYM_half */
266 { "partial", "pd" }, /* EQNSYM_partial */
267 { "inf", "if" }, /* EQNSYM_inf */
268 { ">>", ">>" }, /* EQNSYM_muchgreat */
269 { "<<", "<<" }, /* EQNSYM_muchless */
270 { "<-", "<-" }, /* EQNSYM_larrow */
271 { "->", "->" }, /* EQNSYM_rarrow */
272 { "+-", "+-" }, /* EQNSYM_pm */
273 { "!=", "!=" }, /* EQNSYM_nequal */
274 { "==", "==" }, /* EQNSYM_equiv */
275 { "<=", "<=" }, /* EQNSYM_lessequal */
276 { ">=", ">=" }, /* EQNSYM_moreequal */
277 { "-", "mi" }, /* EQNSYM_minus */
278};
279
280enum parse_mode {
281 MODE_QUOTED,
282 MODE_NOSUB,
283 MODE_SUB,
284 MODE_TOK
285};
286
287struct eqn_def {
288 char *key;
289 size_t keysz;
290 char *val;
291 size_t valsz;
292};
293
294static struct eqn_box *eqn_box_alloc(struct eqn_node *, struct eqn_box *);
295static struct eqn_box *eqn_box_makebinary(struct eqn_node *,
296 struct eqn_box *);
297static void eqn_def(struct eqn_node *);
298static struct eqn_def *eqn_def_find(struct eqn_node *);
299static void eqn_delim(struct eqn_node *);
300static enum eqn_tok eqn_next(struct eqn_node *, enum parse_mode);
301static void eqn_undef(struct eqn_node *);
302
303
304struct eqn_node *
305eqn_alloc(void)
306{
307 struct eqn_node *ep;
308
309 ep = mandoc_calloc(1, sizeof(*ep));
310 ep->gsize = EQN_DEFSIZE(-0x7fffffff-1);
311 return ep;
312}
313
314void
315eqn_reset(struct eqn_node *ep)
316{
317 free(ep->data);
318 ep->data = ep->start = ep->end = NULL((void *)0);
319 ep->sz = ep->toksz = 0;
320}
321
322void
323eqn_read(struct eqn_node *ep, const char *p)
324{
325 char *cp;
326
327 if (ep->data == NULL((void *)0)) {
328 ep->sz = strlen(p);
329 ep->data = mandoc_strdup(p);
330 } else {
331 ep->sz = mandoc_asprintf(&cp, "%s %s", ep->data, p);
332 free(ep->data);
333 ep->data = cp;
334 }
335 ep->sz += 1;
336}
337
338/*
339 * Find the key "key" of the give size within our eqn-defined values.
340 */
341static struct eqn_def *
342eqn_def_find(struct eqn_node *ep)
343{
344 int i;
345
346 for (i = 0; i < (int)ep->defsz; i++)
347 if (ep->defs[i].keysz && STRNEQ(ep->defs[i].key,((ep->defs[i].keysz) == (ep->toksz) && 0 == strncmp
((ep->defs[i].key), (ep->start), (ep->defs[i].keysz)
))
348 ep->defs[i].keysz, ep->start, ep->toksz)((ep->defs[i].keysz) == (ep->toksz) && 0 == strncmp
((ep->defs[i].key), (ep->start), (ep->defs[i].keysz)
)))
349 return &ep->defs[i];
350
351 return NULL((void *)0);
352}
353
354/*
355 * Parse a token from the input text. The modes are:
356 * MODE_QUOTED: Use *ep->start as the delimiter; the token ends
357 * before its next occurrence. Do not interpret the token in any
358 * way and return EQN_TOK_QUOTED. All other modes behave like
359 * MODE_QUOTED when *ep->start is '"'.
360 * MODE_NOSUB: If *ep->start is a curly brace, the token ends after it;
361 * otherwise, it ends before the next whitespace or brace.
362 * Do not interpret the token and return EQN_TOK__MAX.
363 * MODE_SUB: Like MODE_NOSUB, but try to interpret the token as an
364 * alias created with define. If it is an alias, replace it with
365 * its string value and reparse.
366 * MODE_TOK: Like MODE_SUB, but also check the token against the list
367 * of tokens, and if there is a match, return that token. Otherwise,
368 * if the token matches a symbol, return EQN_TOK_SYM; if it matches
369 * a function name, EQN_TOK_FUNC, or else EQN_TOK__MAX. Except for
370 * a token match, *ep->start is set to an allocated string that the
371 * caller is expected to free.
372 * All modes skip whitespace following the end of the token.
373 */
374static enum eqn_tok
375eqn_next(struct eqn_node *ep, enum parse_mode mode)
376{
377 struct eqn_def *def;
378 size_t start;
379 int diff, i, newlen, quoted;
380 enum eqn_tok tok;
381
382 /*
383 * Reset the recursion counter after advancing
384 * beyond the end of the rightmost substitution.
385 */
386 if (ep->end - ep->data >= ep->sublen)
387 ep->subcnt = 0;
388
389 ep->start = ep->end;
390 quoted = mode == MODE_QUOTED;
391 for (;;) {
392 switch (*ep->start) {
393 case '\0':
394 ep->toksz = 0;
395 return EQN_TOK_EOF;
396 case '"':
397 quoted = 1;
398 break;
399 case ' ':
400 case '\t':
401 case '~':
402 case '^':
403 if (quoted)
404 break;
405 ep->start++;
406 continue;
407 default:
408 break;
409 }
410 if (quoted) {
411 ep->end = strchr(ep->start + 1, *ep->start);
412 ep->start++; /* Skip opening quote. */
413 if (ep->end == NULL((void *)0)) {
414 mandoc_msg(MANDOCERR_ARG_QUOTE,
415 ep->node->line, ep->node->pos, NULL((void *)0));
416 ep->end = strchr(ep->start, '\0');
417 }
418 } else {
419 ep->end = ep->start + 1;
420 if (*ep->start != '{' && *ep->start != '}')
421 ep->end += strcspn(ep->end, " ^~\"{}\t");
422 }
423 ep->toksz = ep->end - ep->start;
424 if (quoted && *ep->end != '\0')
425 ep->end++; /* Skip closing quote. */
426 while (*ep->end != '\0' && strchr(" \t^~", *ep->end) != NULL((void *)0))
427 ep->end++;
428 if (quoted) /* Cannot return, may have to strndup. */
429 break;
430 if (mode == MODE_NOSUB)
431 return EQN_TOK__MAX;
432 if ((def = eqn_def_find(ep)) == NULL((void *)0))
433 break;
434 if (++ep->subcnt > EQN_NEST_MAX128) {
435 mandoc_msg(MANDOCERR_ROFFLOOP,
436 ep->node->line, ep->node->pos, NULL((void *)0));
437 break;
438 }
439
440 /* Replace a defined name with its string value. */
441 if ((diff = def->valsz - ep->toksz) > 0) {
442 start = ep->start - ep->data;
443 ep->sz += diff;
444 ep->data = mandoc_realloc(ep->data, ep->sz + 1);
445 ep->start = ep->data + start;
446 ep->sublen += diff;
447 }
448 if (diff)
449 memmove(ep->start + def->valsz, ep->start + ep->toksz,
450 strlen(ep->start + ep->toksz) + 1);
451 memcpy(ep->start, def->val, def->valsz);
452 newlen = ep->start - ep->data + def->valsz;
453 if (ep->sublen < newlen)
454 ep->sublen = newlen;
455 }
456 if (mode != MODE_TOK)
457 return quoted ? EQN_TOK_QUOTED : EQN_TOK__MAX;
458 if (quoted) {
459 ep->start = mandoc_strndup(ep->start, ep->toksz);
460 return EQN_TOK_QUOTED;
461 }
462 for (tok = 0; tok < EQN_TOK__MAX; tok++)
463 if (STRNEQ(ep->start, ep->toksz,((ep->toksz) == (strlen(eqn_toks[tok])) && 0 == strncmp
((ep->start), (eqn_toks[tok]), (ep->toksz)))
464 eqn_toks[tok], strlen(eqn_toks[tok]))((ep->toksz) == (strlen(eqn_toks[tok])) && 0 == strncmp
((ep->start), (eqn_toks[tok]), (ep->toksz))))
465 return tok;
466
467 for (i = 0; i < EQNSYM__MAX; i++) {
468 if (STRNEQ(ep->start, ep->toksz,((ep->toksz) == (strlen(eqnsyms[i].str)) && 0 == strncmp
((ep->start), (eqnsyms[i].str), (ep->toksz)))
469 eqnsyms[i].str, strlen(eqnsyms[i].str))((ep->toksz) == (strlen(eqnsyms[i].str)) && 0 == strncmp
((ep->start), (eqnsyms[i].str), (ep->toksz)))) {
470 mandoc_asprintf(&ep->start,
471 "\\[%s]", eqnsyms[i].sym);
472 return EQN_TOK_SYM;
473 }
474 }
475 ep->start = mandoc_strndup(ep->start, ep->toksz);
476 for (i = 0; i < (int)(sizeof(eqn_func)/sizeof(*eqn_func)); i++)
477 if (STRNEQ(ep->start, ep->toksz,((ep->toksz) == (strlen(eqn_func[i])) && 0 == strncmp
((ep->start), (eqn_func[i]), (ep->toksz)))
478 eqn_func[i], strlen(eqn_func[i]))((ep->toksz) == (strlen(eqn_func[i])) && 0 == strncmp
((ep->start), (eqn_func[i]), (ep->toksz))))
479 return EQN_TOK_FUNC;
480 return EQN_TOK__MAX;
481}
482
483void
484eqn_box_free(struct eqn_box *bp)
485{
486 if (bp == NULL((void *)0))
487 return;
488
489 if (bp->first)
490 eqn_box_free(bp->first);
491 if (bp->next)
492 eqn_box_free(bp->next);
493
494 free(bp->text);
495 free(bp->left);
496 free(bp->right);
497 free(bp->top);
498 free(bp->bottom);
499 free(bp);
500}
501
502struct eqn_box *
503eqn_box_new(void)
504{
505 struct eqn_box *bp;
506
507 bp = mandoc_calloc(1, sizeof(*bp));
508 bp->expectargs = UINT_MAX0xffffffffU;
509 return bp;
510}
511
512/*
513 * Allocate a box as the last child of the parent node.
514 */
515static struct eqn_box *
516eqn_box_alloc(struct eqn_node *ep, struct eqn_box *parent)
517{
518 struct eqn_box *bp;
519
520 bp = eqn_box_new();
521 bp->parent = parent;
522 bp->parent->args++;
523 bp->font = bp->parent->font;
524 bp->size = ep->gsize;
525
526 if (NULL((void *)0) != parent->first) {
9
←
Assuming NULL is not equal to field 'first'
→
10
←
Taking true branch
→
527 parent->last->next = bp;
11
←
Access to field 'next' results in a dereference of a null pointer (loaded from field 'last')
528 bp->prev = parent->last;
529 } else
530 parent->first = bp;
531
532 parent->last = bp;
533 return bp;
534}
535
536/*
537 * Reparent the current last node (of the current parent) under a new
538 * EQN_SUBEXPR as the first element.
539 * Then return the new parent.
540 * The new EQN_SUBEXPR will have a two-child limit.
541 */
542static struct eqn_box *
543eqn_box_makebinary(struct eqn_node *ep, struct eqn_box *parent)
544{
545 struct eqn_box *b, *newb;
546
547 assert(NULL != parent->last)((((void *)0) != parent->last) ? (void)0 : __assert2("/usr/src/usr.bin/mandoc/eqn.c"
, 547, __func__, "NULL != parent->last"));
548 b = parent->last;
549 if (parent->last == parent->first)
550 parent->first = NULL((void *)0);
551 parent->args--;
552 parent->last = b->prev;
553 b->prev = NULL((void *)0);
554 newb = eqn_box_alloc(ep, parent);
555 newb->type = EQN_SUBEXPR;
556 newb->expectargs = 2;
557 newb->args = 1;
558 newb->first = newb->last = b;
559 newb->first->next = NULL((void *)0);
560 b->parent = newb;
561 return newb;
562}
563
564/*
565 * Parse the "delim" control statement.
566 */
567static void
568eqn_delim(struct eqn_node *ep)
569{
570 if (ep->end[0] == '\0' || ep->end[1] == '\0') {
571 mandoc_msg(MANDOCERR_REQ_EMPTY,
572 ep->node->line, ep->node->pos, "delim");
573 if (ep->end[0] != '\0')
574 ep->end++;
575 } else if (strncmp(ep->end, "off", 3) == 0) {
576 ep->delim = 0;
577 ep->end += 3;
578 } else if (strncmp(ep->end, "on", 2) == 0) {
579 if (ep->odelim && ep->cdelim)
580 ep->delim = 1;
581 ep->end += 2;
582 } else {
583 ep->odelim = *ep->end++;
584 ep->cdelim = *ep->end++;
585 ep->delim = 1;
586 }
587}
588
589/*
590 * Undefine a previously-defined string.
591 */
592static void
593eqn_undef(struct eqn_node *ep)
594{
595 struct eqn_def *def;
596
597 if (eqn_next(ep, MODE_NOSUB) == EQN_TOK_EOF) {
598 mandoc_msg(MANDOCERR_REQ_EMPTY,
599 ep->node->line, ep->node->pos, "undef");
600 return;
601 }
602 if ((def = eqn_def_find(ep)) == NULL((void *)0))
603 return;
604 free(def->key);
605 free(def->val);
606 def->key = def->val = NULL((void *)0);
607 def->keysz = def->valsz = 0;
608}
609
610static void
611eqn_def(struct eqn_node *ep)
612{
613 struct eqn_def *def;
614 int i;
615
616 if (eqn_next(ep, MODE_NOSUB) == EQN_TOK_EOF) {
617 mandoc_msg(MANDOCERR_REQ_EMPTY,
618 ep->node->line, ep->node->pos, "define");
619 return;
620 }
621
622 /*
623 * Search for a key that already exists.
624 * Create a new key if none is found.
625 */
626 if ((def = eqn_def_find(ep)) == NULL((void *)0)) {
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((void *)0);
637 }
638
639 def = ep->defs + i;
640 free(def->key);
641 def->key = mandoc_strndup(ep->start, ep->toksz);
642 def->keysz = ep->toksz;
643 }
644
645 if (eqn_next(ep, MODE_QUOTED) == EQN_TOK_EOF) {
646 mandoc_msg(MANDOCERR_REQ_EMPTY,
647 ep->node->line, ep->node->pos, "define %s", def->key);
648 free(def->key);
649 free(def->val);
650 def->key = def->val = NULL((void *)0);
651 def->keysz = def->valsz = 0;
652 return;
653 }
654 free(def->val);
655 def->val = mandoc_strndup(ep->start, ep->toksz);
656 def->valsz = ep->toksz;
657}
658
659void
660eqn_parse(struct eqn_node *ep)
661{
662 struct eqn_box *cur, *nbox, *parent, *split;
663 const char *cp, *cpn;
664 char *p;
665 enum eqn_tok tok;
666 enum { CCL_LET, CCL_DIG, CCL_PUN } ccl, ccln;
667 int size;
668
669 parent = ep->node->eqn;
670 assert(parent != NULL)((parent != ((void *)0)) ? (void)0 : __assert2("/usr/src/usr.bin/mandoc/eqn.c"
, 670, __func__, "parent != NULL"));
1
Assuming 'parent' is not equal to null
→
2
←
'?' condition is true
→
671
672 /*
673 * Empty equation.
674 * Do not add it to the high-level syntax tree.
675 */
676
677 if (ep->data == NULL((void *)0))
3
←
Assuming field 'data' is not equal to NULL
→
4
←
Taking false branch
→
678 return;
679
680 ep->start = ep->end = ep->data;
681 ep->sublen = 0;
682 ep->subcnt = 0;
683
684next_tok:
685 tok = eqn_next(ep, MODE_TOK);
686 switch (tok) {
5
←
Control jumps to 'case EQN_TOK_OVER:' at line 895
→
687 case EQN_TOK_UNDEF:
688 eqn_undef(ep);
689 break;
690 case EQN_TOK_NDEFINE:
691 case EQN_TOK_DEFINE:
692 eqn_def(ep);
693 break;
694 case EQN_TOK_TDEFINE:
695 if (eqn_next(ep, MODE_NOSUB) == EQN_TOK_EOF ||
696 eqn_next(ep, MODE_QUOTED) == EQN_TOK_EOF)
697 mandoc_msg(MANDOCERR_REQ_EMPTY,
698 ep->node->line, ep->node->pos, "tdefine");
699 break;
700 case EQN_TOK_DELIM:
701 eqn_delim(ep);
702 break;
703 case EQN_TOK_GFONT:
704 if (eqn_next(ep, MODE_SUB) == EQN_TOK_EOF)
705 mandoc_msg(MANDOCERR_REQ_EMPTY, ep->node->line,
706 ep->node->pos, "%s", eqn_toks[tok]);
707 break;
708 case EQN_TOK_MARK:
709 case EQN_TOK_LINEUP:
710 /* Ignore these. */
711 break;
712 case EQN_TOK_DYAD:
713 case EQN_TOK_VEC:
714 case EQN_TOK_UNDER:
715 case EQN_TOK_BAR:
716 case EQN_TOK_TILDE:
717 case EQN_TOK_HAT:
718 case EQN_TOK_DOT:
719 case EQN_TOK_DOTDOT:
720 if (parent->last == NULL((void *)0)) {
721 mandoc_msg(MANDOCERR_EQN_NOBOX, ep->node->line,
722 ep->node->pos, "%s", eqn_toks[tok]);
723 cur = eqn_box_alloc(ep, parent);
724 cur->type = EQN_TEXT;
725 cur->text = mandoc_strdup("");
726 }
727 parent = eqn_box_makebinary(ep, parent);
728 parent->type = EQN_LIST;
729 parent->expectargs = 1;
730 parent->font = EQNFONT_ROMAN;
731 switch (tok) {
732 case EQN_TOK_DOTDOT:
733 parent->top = mandoc_strdup("\\[ad]");
734 break;
735 case EQN_TOK_VEC:
736 parent->top = mandoc_strdup("\\[->]");
737 break;
738 case EQN_TOK_DYAD:
739 parent->top = mandoc_strdup("\\[<>]");
740 break;
741 case EQN_TOK_TILDE:
742 parent->top = mandoc_strdup("\\[a~]");
743 break;
744 case EQN_TOK_UNDER:
745 parent->bottom = mandoc_strdup("\\[ul]");
746 break;
747 case EQN_TOK_BAR:
748 parent->top = mandoc_strdup("\\[rn]");
749 break;
750 case EQN_TOK_DOT:
751 parent->top = mandoc_strdup("\\[a.]");
752 break;
753 case EQN_TOK_HAT:
754 parent->top = mandoc_strdup("\\[ha]");
755 break;
756 default:
757 abort();
758 }
759 parent = parent->parent;
760 break;
761 case EQN_TOK_FWD:
762 case EQN_TOK_BACK:
763 case EQN_TOK_DOWN:
764 case EQN_TOK_UP:
765 if (eqn_next(ep, MODE_SUB) == EQN_TOK_EOF)
766 mandoc_msg(MANDOCERR_REQ_EMPTY, ep->node->line,
767 ep->node->pos, "%s", eqn_toks[tok]);
768 break;
769 case EQN_TOK_FAT:
770 case EQN_TOK_ROMAN:
771 case EQN_TOK_ITALIC:
772 case EQN_TOK_BOLD:
773 while (parent->args == parent->expectargs)
774 parent = parent->parent;
775 /*
776 * These values apply to the next word or sequence of
777 * words; thus, we mark that we'll have a child with
778 * exactly one of those.
779 */
780 parent = eqn_box_alloc(ep, parent);
781 parent->type = EQN_LIST;
782 parent->expectargs = 1;
783 switch (tok) {
784 case EQN_TOK_FAT:
785 parent->font = EQNFONT_FAT;
786 break;
787 case EQN_TOK_ROMAN:
788 parent->font = EQNFONT_ROMAN;
789 break;
790 case EQN_TOK_ITALIC:
791 parent->font = EQNFONT_ITALIC;
792 break;
793 case EQN_TOK_BOLD:
794 parent->font = EQNFONT_BOLD;
795 break;
796 default:
797 abort();
798 }
799 break;
800 case EQN_TOK_SIZE:
801 case EQN_TOK_GSIZE:
802 /* Accept two values: integral size and a single. */
803 if (eqn_next(ep, MODE_SUB) == EQN_TOK_EOF) {
804 mandoc_msg(MANDOCERR_REQ_EMPTY, ep->node->line,
805 ep->node->pos, "%s", eqn_toks[tok]);
806 break;
807 }
808 size = mandoc_strntoi(ep->start, ep->toksz, 10);
809 if (-1 == size) {
810 mandoc_msg(MANDOCERR_IT_NONUM, ep->node->line,
811 ep->node->pos, "%s", eqn_toks[tok]);
812 break;
813 }
814 if (EQN_TOK_GSIZE == tok) {
815 ep->gsize = size;
816 break;
817 }
818 while (parent->args == parent->expectargs)
819 parent = parent->parent;
820 parent = eqn_box_alloc(ep, parent);
821 parent->type = EQN_LIST;
822 parent->expectargs = 1;
823 parent->size = size;
824 break;
825 case EQN_TOK_FROM:
826 case EQN_TOK_TO:
827 case EQN_TOK_SUB:
828 case EQN_TOK_SUP:
829 /*
830 * We have a left-right-associative expression.
831 * Repivot under a positional node, open a child scope
832 * and keep on reading.
833 */
834 if (parent->last == NULL((void *)0)) {
835 mandoc_msg(MANDOCERR_EQN_NOBOX, ep->node->line,
836 ep->node->pos, "%s", eqn_toks[tok]);
837 cur = eqn_box_alloc(ep, parent);
838 cur->type = EQN_TEXT;
839 cur->text = mandoc_strdup("");
840 }
841 while (parent->expectargs == 1 && parent->args == 1)
842 parent = parent->parent;
843 if (tok == EQN_TOK_FROM || tok == EQN_TOK_TO) {
844 for (cur = parent; cur != NULL((void *)0); cur = cur->parent)
845 if (cur->pos == EQNPOS_SUB ||
846 cur->pos == EQNPOS_SUP ||
847 cur->pos == EQNPOS_SUBSUP ||
848 cur->pos == EQNPOS_SQRT ||
849 cur->pos == EQNPOS_OVER)
850 break;
851 if (cur != NULL((void *)0))
852 parent = cur->parent;
853 }
854 if (tok == EQN_TOK_SUP && parent->pos == EQNPOS_SUB) {
855 parent->expectargs = 3;
856 parent->pos = EQNPOS_SUBSUP;
857 break;
858 }
859 if (tok == EQN_TOK_TO && parent->pos == EQNPOS_FROM) {
860 parent->expectargs = 3;
861 parent->pos = EQNPOS_FROMTO;
862 break;
863 }
864 parent = eqn_box_makebinary(ep, parent);
865 switch (tok) {
866 case EQN_TOK_FROM:
867 parent->pos = EQNPOS_FROM;
868 break;
869 case EQN_TOK_TO:
870 parent->pos = EQNPOS_TO;
871 break;
872 case EQN_TOK_SUP:
873 parent->pos = EQNPOS_SUP;
874 break;
875 case EQN_TOK_SUB:
876 parent->pos = EQNPOS_SUB;
877 break;
878 default:
879 abort();
880 }
881 break;
882 case EQN_TOK_SQRT:
883 while (parent->args == parent->expectargs)
884 parent = parent->parent;
885 /*
886 * Accept a left-right-associative set of arguments just
887 * like sub and sup and friends but without rebalancing
888 * under a pivot.
889 */
890 parent = eqn_box_alloc(ep, parent);
891 parent->type = EQN_SUBEXPR;
892 parent->pos = EQNPOS_SQRT;
893 parent->expectargs = 1;
894 break;
895 case EQN_TOK_OVER:
896 /*
897 * We have a right-left-associative fraction.
898 * Close out anything that's currently open, then
899 * rebalance and continue reading.
900 */
901 if (parent->last == NULL((void *)0)) {
6
←
Assuming field 'last' is equal to NULL
→
7
←
Taking true branch
→
902 mandoc_msg(MANDOCERR_EQN_NOBOX, ep->node->line,
903 ep->node->pos, "%s", eqn_toks[tok]);
904 cur = eqn_box_alloc(ep, parent);
8
←
Calling 'eqn_box_alloc'
→
905 cur->type = EQN_TEXT;
906 cur->text = mandoc_strdup("");
907 }
908 while (parent->args == parent->expectargs)
909 parent = parent->parent;
910 while (EQN_SUBEXPR == parent->type)
911 parent = parent->parent;
912 parent = eqn_box_makebinary(ep, parent);
913 parent->pos = EQNPOS_OVER;
914 break;
915 case EQN_TOK_RIGHT:
916 case EQN_TOK_BRACE_CLOSE:
917 /*
918 * Close out the existing brace.
919 * FIXME: this is a shitty sentinel: we should really
920 * have a native EQN_BRACE type or whatnot.
921 */
922 for (cur = parent; cur != NULL((void *)0); cur = cur->parent)
923 if (cur->type == EQN_LIST &&
924 cur->expectargs > 1 &&
925 (tok == EQN_TOK_BRACE_CLOSE ||
926 cur->left != NULL((void *)0)))
927 break;
928 if (cur == NULL((void *)0)) {
929 mandoc_msg(MANDOCERR_BLK_NOTOPEN, ep->node->line,
930 ep->node->pos, "%s", eqn_toks[tok]);
931 break;
932 }
933 parent = cur;
934 if (EQN_TOK_RIGHT == tok) {
935 if (eqn_next(ep, MODE_SUB) == EQN_TOK_EOF) {
936 mandoc_msg(MANDOCERR_REQ_EMPTY,
937 ep->node->line, ep->node->pos,
938 "%s", eqn_toks[tok]);
939 break;
940 }
941 /* Handling depends on right/left. */
942 if (STRNEQ(ep->start, ep->toksz, "ceiling", 7)((ep->toksz) == (7) && 0 == strncmp((ep->start)
, ("ceiling"), (ep->toksz))))
943 parent->right = mandoc_strdup("\\[rc]");
944 else if (STRNEQ(ep->start, ep->toksz, "floor", 5)((ep->toksz) == (5) && 0 == strncmp((ep->start)
, ("floor"), (ep->toksz))))
945 parent->right = mandoc_strdup("\\[rf]");
946 else
947 parent->right =
948 mandoc_strndup(ep->start, ep->toksz);
949 }
950 parent = parent->parent;
951 if (tok == EQN_TOK_BRACE_CLOSE &&
952 (parent->type == EQN_PILE ||
953 parent->type == EQN_MATRIX))
954 parent = parent->parent;
955 /* Close out any "singleton" lists. */
956 while (parent->type == EQN_LIST &&
957 parent->expectargs == 1 &&
958 parent->args == 1)
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 eqn_next(ep, MODE_SUB) == EQN_TOK_EOF) {
972 mandoc_msg(MANDOCERR_REQ_EMPTY, ep->node->line,
973 ep->node->pos, "%s", 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(ep->start, ep->toksz, "ceiling", 7)((ep->toksz) == (7) && 0 == strncmp((ep->start)
, ("ceiling"), (ep->toksz))))
980 parent->left = mandoc_strdup("\\[lc]");
981 else if (STRNEQ(ep->start, ep->toksz, "floor", 5)((ep->toksz) == (5) && 0 == strncmp((ep->start)
, ("floor"), (ep->toksz))))
982 parent->left = mandoc_strdup("\\[lf]");
983 else
984 parent->left =
985 mandoc_strndup(ep->start, ep->toksz);
986 }
987 break;
988 case EQN_TOK_PILE:
989 case EQN_TOK_LPILE:
990 case EQN_TOK_RPILE:
991 case EQN_TOK_CPILE:
992 case EQN_TOK_CCOL:
993 case EQN_TOK_LCOL:
994 case EQN_TOK_RCOL:
995 while (parent->args == parent->expectargs)
996 parent = parent->parent;
997 parent = eqn_box_alloc(ep, parent);
998 parent->type = EQN_PILE;
999 parent->expectargs = 1;
1000 break;
1001 case EQN_TOK_ABOVE:
1002 for (cur = parent; cur != NULL((void *)0); cur = cur->parent)
1003 if (cur->type == EQN_PILE)
1004 break;
1005 if (cur == NULL((void *)0)) {
1006 mandoc_msg(MANDOCERR_IT_STRAY, ep->node->line,
1007 ep->node->pos, "%s", eqn_toks[tok]);
1008 break;
1009 }
1010 parent = eqn_box_alloc(ep, cur);
1011 parent->type = EQN_LIST;
1012 break;
1013 case EQN_TOK_MATRIX:
1014 while (parent->args == parent->expectargs)
1015 parent = parent->parent;
1016 parent = eqn_box_alloc(ep, parent);
1017 parent->type = EQN_MATRIX;
1018 parent->expectargs = 1;
1019 break;
1020 case EQN_TOK_EOF:
1021 return;
1022 case EQN_TOK__MAX:
1023 case EQN_TOK_FUNC:
1024 case EQN_TOK_QUOTED:
1025 case EQN_TOK_SYM:
1026 p = ep->start;
1027 assert(p != NULL)((p != ((void *)0)) ? (void)0 : __assert2("/usr/src/usr.bin/mandoc/eqn.c"
, 1027, __func__, "p != NULL"));
1028 /*
1029 * If we already have something in the stack and we're
1030 * in an expression, then rewind til we're not any more.
1031 */
1032 while (parent->args == parent->expectargs)
1033 parent = parent->parent;
1034 cur = eqn_box_alloc(ep, parent);
1035 cur->type = EQN_TEXT;
1036 cur->text = p;
1037 switch (tok) {
1038 case EQN_TOK_FUNC:
1039 cur->font = EQNFONT_ROMAN;
1040 break;
1041 case EQN_TOK_QUOTED:
1042 if (cur->font == EQNFONT_NONE)
1043 cur->font = EQNFONT_ITALIC;
1044 break;
1045 case EQN_TOK_SYM:
1046 break;
1047 default:
1048 if (cur->font != EQNFONT_NONE || *p == '\0')
1049 break;
1050 cpn = p - 1;
1051 ccln = CCL_LET;
1052 split = NULL((void *)0);
1053 for (;;) {
1054 /* Advance to next character. */
1055 cp = cpn++;
1056 ccl = ccln;
1057 ccln = isalpha((unsigned char)*cpn) ? CCL_LET :
1058 isdigit((unsigned char)*cpn) ||
1059 (*cpn == '.' && (ccl == CCL_DIG ||
1060 isdigit((unsigned char)cpn[1]))) ?
1061 CCL_DIG : CCL_PUN;
1062 /* No boundary before first character. */
1063 if (cp < p)
1064 continue;
1065 cur->font = ccl == CCL_LET ?
1066 EQNFONT_ITALIC : EQNFONT_ROMAN;
1067 if (*cp == '\\')
1068 mandoc_escape(&cpn, NULL((void *)0), NULL((void *)0));
1069 /* No boundary after last character. */
1070 if (*cpn == '\0')
1071 break;
1072 if (ccln == ccl && *cp != ',' && *cpn != ',')
1073 continue;
1074 /* Boundary found, split the text. */
1075 if (parent->args == parent->expectargs) {
1076 /* Remove the text from the tree. */
1077 if (cur->prev == NULL((void *)0))
1078 parent->first = cur->next;
1079 else
1080 cur->prev->next = NULL((void *)0);
1081 parent->last = cur->prev;
1082 parent->args--;
1083 /* Set up a list instead. */
1084 split = eqn_box_alloc(ep, parent);
1085 split->type = EQN_LIST;
1086 /* Insert the word into the list. */
1087 split->first = split->last = cur;
1088 cur->parent = split;
1089 cur->prev = NULL((void *)0);
1090 parent = split;
1091 }
1092 /* Append a new text box. */
1093 nbox = eqn_box_alloc(ep, parent);
1094 nbox->type = EQN_TEXT;
1095 nbox->text = mandoc_strdup(cpn);
1096 /* Truncate the old box. */
1097 p = mandoc_strndup(cur->text,
1098 cpn - cur->text);
1099 free(cur->text);
1100 cur->text = p;
1101 /* Setup to process the new box. */
1102 cur = nbox;
1103 p = nbox->text;
1104 cpn = p - 1;
1105 ccln = CCL_LET;
1106 }
1107 if (split != NULL((void *)0))
1108 parent = split->parent;
1109 break;
1110 }
1111 break;
1112 default:
1113 abort();
1114 }
1115 goto next_tok;
1116}
1117
1118void
1119eqn_free(struct eqn_node *p)
1120{
1121 int i;
1122
1123 if (p == NULL((void *)0))
1124 return;
1125
1126 for (i = 0; i < (int)p->defsz; i++) {
1127 free(p->defs[i].key);
1128 free(p->defs[i].val);
1129 }
1130
1131 free(p->data);
1132 free(p->defs);
1133 free(p);
1134}