]> git.saurik.com Git - bison.git/blob - src/output.c
Fix push parsing memory leak reported by Brandon Lucia at
[bison.git] / src / output.c
1 /* Output the generated parsing program for Bison.
2
3 Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002, 2003, 2004,
4 2005, 2006, 2007 Free Software Foundation, Inc.
5
6 This file is part of Bison, the GNU Compiler Compiler.
7
8 Bison is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 Bison is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with Bison; see the file COPYING. If not, write to the Free
20 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA. */
22
23 #include <config.h>
24 #include "system.h"
25
26 #include <configmake.h>
27 #include <error.h>
28 #include <get-errno.h>
29 #include <quotearg.h>
30 #include <subpipe.h>
31 #include <timevar.h>
32
33 #include "complain.h"
34 #include "files.h"
35 #include "getargs.h"
36 #include "gram.h"
37 #include "muscle_tab.h"
38 #include "output.h"
39 #include "reader.h"
40 #include "scan-code.h" /* max_left_semantic_context */
41 #include "scan-skel.h"
42 #include "symtab.h"
43 #include "tables.h"
44
45
46 static struct obstack format_obstack;
47
48
49 /*-------------------------------------------------------------------.
50 | Create a function NAME which associates to the muscle NAME the |
51 | result of formatting the FIRST and then TABLE_DATA[BEGIN..END[ (of |
52 | TYPE), and to the muscle NAME_max, the max value of the |
53 | TABLE_DATA. |
54 `-------------------------------------------------------------------*/
55
56
57 #define GENERATE_MUSCLE_INSERT_TABLE(Name, Type) \
58 \
59 static void \
60 Name (char const *name, \
61 Type *table_data, \
62 Type first, \
63 int begin, \
64 int end) \
65 { \
66 Type min = first; \
67 Type max = first; \
68 long int lmin; \
69 long int lmax; \
70 int i; \
71 int j = 1; \
72 \
73 obstack_fgrow1 (&format_obstack, "%6d", first); \
74 for (i = begin; i < end; ++i) \
75 { \
76 obstack_1grow (&format_obstack, ','); \
77 if (j >= 10) \
78 { \
79 obstack_sgrow (&format_obstack, "\n "); \
80 j = 1; \
81 } \
82 else \
83 ++j; \
84 obstack_fgrow1 (&format_obstack, "%6d", table_data[i]); \
85 if (table_data[i] < min) \
86 min = table_data[i]; \
87 if (max < table_data[i]) \
88 max = table_data[i]; \
89 } \
90 obstack_1grow (&format_obstack, 0); \
91 muscle_insert (name, obstack_finish (&format_obstack)); \
92 \
93 lmin = min; \
94 lmax = max; \
95 /* Build `NAME_min' and `NAME_max' in the obstack. */ \
96 obstack_fgrow1 (&format_obstack, "%s_min", name); \
97 obstack_1grow (&format_obstack, 0); \
98 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmin); \
99 obstack_fgrow1 (&format_obstack, "%s_max", name); \
100 obstack_1grow (&format_obstack, 0); \
101 MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack), lmax); \
102 }
103
104 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table, unsigned int)
105 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_int_table, int)
106 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_base_table, base_number)
107 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_rule_number_table, rule_number)
108 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table, symbol_number)
109 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_item_number_table, item_number)
110 GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_state_number_table, state_number)
111
112
113 /*--------------------------------------------------------------------.
114 | Print to OUT a representation of STRING escaped both for C and M4. |
115 `--------------------------------------------------------------------*/
116
117 static void
118 escaped_output (FILE *out, char const *string)
119 {
120 char const *p;
121 fprintf (out, "[[");
122
123 for (p = quotearg_style (c_quoting_style, string); *p; p++)
124 switch (*p)
125 {
126 case '$': fputs ("$][", out); break;
127 case '@': fputs ("@@", out); break;
128 case '[': fputs ("@{", out); break;
129 case ']': fputs ("@}", out); break;
130 default: fputc (*p, out); break;
131 }
132
133 fprintf (out, "]]");
134 }
135
136
137 /*------------------------------------------------------------------.
138 | Prepare the muscles related to the symbols: translate, tname, and |
139 | toknum. |
140 `------------------------------------------------------------------*/
141
142 static void
143 prepare_symbols (void)
144 {
145 MUSCLE_INSERT_BOOL ("token_table", token_table_flag);
146 MUSCLE_INSERT_INT ("tokens_number", ntokens);
147 MUSCLE_INSERT_INT ("nterms_number", nvars);
148 MUSCLE_INSERT_INT ("undef_token_number", undeftoken->number);
149 MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number);
150
151 muscle_insert_symbol_number_table ("translate",
152 token_translations,
153 token_translations[0],
154 1, max_user_token_number + 1);
155
156 /* tname -- token names. */
157 {
158 int i;
159 /* We assume that the table will be output starting at column 2. */
160 int j = 2;
161 for (i = 0; i < nsyms; i++)
162 {
163 char const *cp = quotearg_style (c_quoting_style, symbols[i]->tag);
164 /* Width of the next token, including the two quotes, the
165 comma and the space. */
166 int width = strlen (cp) + 2;
167
168 if (j + width > 75)
169 {
170 obstack_sgrow (&format_obstack, "\n ");
171 j = 1;
172 }
173
174 if (i)
175 obstack_1grow (&format_obstack, ' ');
176 MUSCLE_OBSTACK_SGROW (&format_obstack, cp);
177 obstack_1grow (&format_obstack, ',');
178 j += width;
179 }
180 obstack_sgrow (&format_obstack, " ]b4_null[");
181
182 /* Finish table and store. */
183 obstack_1grow (&format_obstack, 0);
184 muscle_insert ("tname", obstack_finish (&format_obstack));
185 }
186
187 /* Output YYTOKNUM. */
188 {
189 int i;
190 int *values = xnmalloc (ntokens, sizeof *values);
191 for (i = 0; i < ntokens; ++i)
192 values[i] = symbols[i]->user_token_number;
193 muscle_insert_int_table ("toknum", values,
194 values[0], 1, ntokens);
195 free (values);
196 }
197 }
198
199
200 /*-------------------------------------------------------------.
201 | Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
202 | rline, dprec, merger. |
203 `-------------------------------------------------------------*/
204
205 static void
206 prepare_rules (void)
207 {
208 rule_number r;
209 unsigned int i = 0;
210 item_number *rhs = xnmalloc (nritems, sizeof *rhs);
211 unsigned int *prhs = xnmalloc (nrules, sizeof *prhs);
212 unsigned int *rline = xnmalloc (nrules, sizeof *rline);
213 symbol_number *r1 = xnmalloc (nrules, sizeof *r1);
214 unsigned int *r2 = xnmalloc (nrules, sizeof *r2);
215 int *dprec = xnmalloc (nrules, sizeof *dprec);
216 int *merger = xnmalloc (nrules, sizeof *merger);
217
218 for (r = 0; r < nrules; ++r)
219 {
220 item_number *rhsp = NULL;
221 /* Index of rule R in RHS. */
222 prhs[r] = i;
223 /* RHS of the rule R. */
224 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
225 rhs[i++] = *rhsp;
226 /* LHS of the rule R. */
227 r1[r] = rules[r].lhs->number;
228 /* Length of rule R's RHS. */
229 r2[r] = i - prhs[r];
230 /* Separator in RHS. */
231 rhs[i++] = -1;
232 /* Line where rule was defined. */
233 rline[r] = rules[r].location.start.line;
234 /* Dynamic precedence (GLR). */
235 dprec[r] = rules[r].dprec;
236 /* Merger-function index (GLR). */
237 merger[r] = rules[r].merger;
238 }
239 aver (i == nritems);
240
241 muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
242 muscle_insert_unsigned_int_table ("prhs", prhs, 0, 0, nrules);
243 muscle_insert_unsigned_int_table ("rline", rline, 0, 0, nrules);
244 muscle_insert_symbol_number_table ("r1", r1, 0, 0, nrules);
245 muscle_insert_unsigned_int_table ("r2", r2, 0, 0, nrules);
246 muscle_insert_int_table ("dprec", dprec, 0, 0, nrules);
247 muscle_insert_int_table ("merger", merger, 0, 0, nrules);
248
249 MUSCLE_INSERT_INT ("rules_number", nrules);
250 MUSCLE_INSERT_INT ("max_left_semantic_context", max_left_semantic_context);
251
252 free (rhs);
253 free (prhs);
254 free (rline);
255 free (r1);
256 free (r2);
257 free (dprec);
258 free (merger);
259 }
260
261 /*--------------------------------------------.
262 | Prepare the muscles related to the states. |
263 `--------------------------------------------*/
264
265 static void
266 prepare_states (void)
267 {
268 state_number i;
269 symbol_number *values = xnmalloc (nstates, sizeof *values);
270 for (i = 0; i < nstates; ++i)
271 values[i] = states[i]->accessing_symbol;
272 muscle_insert_symbol_number_table ("stos", values,
273 0, 1, nstates);
274 free (values);
275
276 MUSCLE_INSERT_INT ("last", high);
277 MUSCLE_INSERT_INT ("final_state_number", final_state->number);
278 MUSCLE_INSERT_INT ("states_number", nstates);
279 }
280
281
282
283 /*---------------------------------.
284 | Output the user actions to OUT. |
285 `---------------------------------*/
286
287 static void
288 user_actions_output (FILE *out)
289 {
290 rule_number r;
291
292 fputs ("m4_define([b4_actions], \n[", out);
293 for (r = 0; r < nrules; ++r)
294 if (rules[r].action)
295 {
296 fprintf (out, "b4_case(%d, [b4_syncline(%d, ", r + 1,
297 rules[r].action_location.start.line);
298 escaped_output (out, rules[r].action_location.start.file);
299 fprintf (out, ")\n[ %s]])\n\n", rules[r].action);
300 }
301 fputs ("])\n\n", out);
302 }
303
304 /*--------------------------------------.
305 | Output the merge functions to OUT. |
306 `--------------------------------------*/
307
308 static void
309 merger_output (FILE *out)
310 {
311 int n;
312 merger_list* p;
313
314 fputs ("m4_define([b4_mergers], \n[[", out);
315 for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
316 {
317 if (p->type[0] == '\0')
318 fprintf (out, " case %d: *yy0 = %s (*yy0, *yy1); break;\n",
319 n, p->name);
320 else
321 fprintf (out, " case %d: yy0->%s = %s (*yy0, *yy1); break;\n",
322 n, p->type, p->name);
323 }
324 fputs ("]])\n\n", out);
325 }
326
327 /*--------------------------------------.
328 | Output the tokens definition to OUT. |
329 `--------------------------------------*/
330
331 static void
332 token_definitions_output (FILE *out)
333 {
334 int i;
335 char const *sep = "";
336
337 fputs ("m4_define([b4_tokens], \n[", out);
338 for (i = 0; i < ntokens; ++i)
339 {
340 symbol *sym = symbols[i];
341 int number = sym->user_token_number;
342
343 /* At this stage, if there are literal aliases, they are part of
344 SYMBOLS, so we should not find symbols which are the aliases
345 here. */
346 aver (number != USER_NUMBER_ALIAS);
347
348 /* Skip error token. */
349 if (sym == errtoken)
350 continue;
351
352 /* If this string has an alias, then it is necessarily the alias
353 which is to be output. */
354 if (sym->alias)
355 sym = sym->alias;
356
357 /* Don't output literal chars or strings (when defined only as a
358 string). Note that must be done after the alias resolution:
359 think about `%token 'f' "f"'. */
360 if (sym->tag[0] == '\'' || sym->tag[0] == '\"')
361 continue;
362
363 /* Don't #define nonliteral tokens whose names contain periods
364 or '$' (as does the default value of the EOF token). */
365 if (strchr (sym->tag, '.') || strchr (sym->tag, '$'))
366 continue;
367
368 fprintf (out, "%s[[[%s]], %d]",
369 sep, sym->tag, number);
370 sep = ",\n";
371 }
372 fputs ("])\n\n", out);
373 }
374
375
376 /*---------------------------------------------------.
377 | Output the symbol destructors or printers to OUT. |
378 `---------------------------------------------------*/
379
380 static void
381 symbol_code_props_output (FILE *out, char const *what,
382 code_props const *(*get)(symbol const *))
383 {
384 int i;
385 char const *sep = "";
386
387 fputs ("m4_define([b4_symbol_", out);
388 fputs (what, out);
389 fputs ("], \n[", out);
390 for (i = 0; i < nsyms; ++i)
391 {
392 symbol *sym = symbols[i];
393 char const *code = (*get) (sym)->code;
394 if (code)
395 {
396 location loc = (*get) (sym)->location;
397 /* Filename, lineno,
398 Symbol-name, Symbol-number,
399 code, optional typename. */
400 fprintf (out, "%s[", sep);
401 sep = ",\n";
402 escaped_output (out, loc.start.file);
403 fprintf (out, ", %d, ", loc.start.line);
404 escaped_output (out, sym->tag);
405 fprintf (out, ", %d, [[%s]]", sym->number, code);
406 if (sym->type_name)
407 fprintf (out, ", [[%s]]", sym->type_name);
408 fputc (']', out);
409 }
410 }
411 fputs ("])\n\n", out);
412 }
413
414
415 static void
416 prepare_actions (void)
417 {
418 /* Figure out the actions for the specified state, indexed by
419 lookahead token type. */
420
421 muscle_insert_rule_number_table ("defact", yydefact,
422 yydefact[0], 1, nstates);
423
424 /* Figure out what to do after reducing with each rule, depending on
425 the saved state from before the beginning of parsing the data
426 that matched this rule. */
427 muscle_insert_state_number_table ("defgoto", yydefgoto,
428 yydefgoto[0], 1, nsyms - ntokens);
429
430
431 /* Output PACT. */
432 muscle_insert_base_table ("pact", base,
433 base[0], 1, nstates);
434 MUSCLE_INSERT_INT ("pact_ninf", base_ninf);
435
436 /* Output PGOTO. */
437 muscle_insert_base_table ("pgoto", base,
438 base[nstates], nstates + 1, nvectors);
439
440 muscle_insert_base_table ("table", table,
441 table[0], 1, high + 1);
442 MUSCLE_INSERT_INT ("table_ninf", table_ninf);
443
444 muscle_insert_base_table ("check", check,
445 check[0], 1, high + 1);
446
447 /* GLR parsing slightly modifies YYTABLE and YYCHECK (and thus
448 YYPACT) so that in states with unresolved conflicts, the default
449 reduction is not used in the conflicted entries, so that there is
450 a place to put a conflict pointer.
451
452 This means that YYCONFLP and YYCONFL are nonsense for a non-GLR
453 parser, so we could avoid accidents by not writing them out in
454 that case. Nevertheless, it seems even better to be able to use
455 the GLR skeletons even without the non-deterministic tables. */
456 muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
457 conflict_table[0], 1, high + 1);
458 muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
459 0, 1, conflict_list_cnt);
460 }
461
462 \f
463 /*---------------------------.
464 | Call the skeleton parser. |
465 `---------------------------*/
466
467 static void
468 output_skeleton (void)
469 {
470 FILE *in;
471 FILE *out;
472 int filter_fd[2];
473 char const *argv[7];
474 pid_t pid;
475
476 /* Compute the names of the package data dir and skeleton file.
477 Test whether m4sugar.m4 is readable, to check for proper
478 installation. A faulty installation can cause deadlock, so a
479 cheap sanity check is worthwhile. */
480 char const m4sugar[] = "m4sugar/m4sugar.m4";
481 char const m4bison[] = "bison.m4";
482 char *full_m4sugar;
483 char *full_m4bison;
484 char *full_skeleton;
485 char const *p;
486 char const *m4 = (p = getenv ("M4")) ? p : M4;
487 char const *pkgdatadir = (p = getenv ("BISON_PKGDATADIR")) ? p : PKGDATADIR;
488 size_t skeleton_size = strlen (skeleton) + 1;
489 size_t pkgdatadirlen = strlen (pkgdatadir);
490 while (pkgdatadirlen && pkgdatadir[pkgdatadirlen - 1] == '/')
491 pkgdatadirlen--;
492 full_skeleton = xmalloc (pkgdatadirlen + 1
493 + (skeleton_size < sizeof m4sugar
494 ? sizeof m4sugar : skeleton_size));
495 strncpy (full_skeleton, pkgdatadir, pkgdatadirlen);
496 full_skeleton[pkgdatadirlen] = '/';
497 strcpy (full_skeleton + pkgdatadirlen + 1, m4sugar);
498 full_m4sugar = xstrdup (full_skeleton);
499 strcpy (full_skeleton + pkgdatadirlen + 1, m4bison);
500 full_m4bison = xstrdup (full_skeleton);
501 if (strchr (skeleton, '/'))
502 strcpy (full_skeleton, skeleton);
503 else
504 strcpy (full_skeleton + pkgdatadirlen + 1, skeleton);
505 xfclose (xfopen (full_m4sugar, "r"));
506
507 /* Create an m4 subprocess connected to us via two pipes. */
508
509 if (trace_flag & trace_tools)
510 fprintf (stderr, "running: %s %s - %s %s\n",
511 m4, full_m4sugar, full_m4bison, full_skeleton);
512
513 argv[0] = m4;
514 argv[1] = full_m4sugar;
515 argv[2] = "-";
516 argv[3] = full_m4bison;
517 argv[4] = full_skeleton;
518 argv[5] = trace_flag & trace_m4 ? "-dV" : NULL;
519 argv[6] = NULL;
520
521 init_subpipe ();
522 pid = create_subpipe (argv, filter_fd);
523 free (full_m4bison);
524 free (full_m4sugar);
525 free (full_skeleton);
526
527 out = fdopen (filter_fd[0], "w");
528 if (! out)
529 error (EXIT_FAILURE, get_errno (),
530 "fdopen");
531
532 /* Output the definitions of all the muscles. */
533 fputs ("m4_init()\n", out);
534
535 user_actions_output (out);
536 merger_output (out);
537 token_definitions_output (out);
538 symbol_code_props_output (out, "destructors", &symbol_destructor_get);
539 symbol_code_props_output (out, "printers", &symbol_printer_get);
540
541 muscles_m4_output (out);
542 xfclose (out);
543
544 /* Read and process m4's output. */
545 timevar_push (TV_M4);
546 end_of_output_subpipe (pid, filter_fd);
547 in = fdopen (filter_fd[1], "r");
548 if (! in)
549 error (EXIT_FAILURE, get_errno (),
550 "fdopen");
551 scan_skel (in);
552 xfclose (in);
553 reap_subpipe (pid, m4);
554 timevar_pop (TV_M4);
555 }
556
557 static void
558 prepare (void)
559 {
560 /* BISON_USE_PUSH_FOR_PULL is for the test suite and should not be documented
561 for the user. */
562 char const *use_push_for_pull_env = getenv ("BISON_USE_PUSH_FOR_PULL");
563 bool use_push_for_pull_flag = false;
564 if (use_push_for_pull_env != NULL
565 && use_push_for_pull_env[0] != '\0'
566 && 0 != strcmp (use_push_for_pull_env, "0"))
567 use_push_for_pull_flag = true;
568
569 /* Flags. */
570 MUSCLE_INSERT_BOOL ("debug_flag", debug_flag);
571 MUSCLE_INSERT_BOOL ("defines_flag", defines_flag);
572 MUSCLE_INSERT_BOOL ("error_verbose_flag", error_verbose);
573 MUSCLE_INSERT_BOOL ("glr_flag", glr_parser);
574 MUSCLE_INSERT_BOOL ("locations_flag", locations_flag);
575 MUSCLE_INSERT_BOOL ("nondeterministic_flag", nondeterministic_parser);
576 MUSCLE_INSERT_BOOL ("pull_flag", pull_parser);
577 MUSCLE_INSERT_BOOL ("pure_flag", pure_parser);
578 MUSCLE_INSERT_BOOL ("push_flag", push_parser);
579 MUSCLE_INSERT_BOOL ("synclines_flag", !no_lines_flag);
580 MUSCLE_INSERT_BOOL ("tag_seen_flag", tag_seen);
581 MUSCLE_INSERT_BOOL ("use_push_for_pull_flag", use_push_for_pull_flag);
582 MUSCLE_INSERT_BOOL ("yacc_flag", yacc_flag);
583
584 /* File names. */
585 if (spec_name_prefix)
586 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix);
587
588 MUSCLE_INSERT_STRING ("file_name_all_but_ext", all_but_ext);
589
590 #define DEFINE(Name) MUSCLE_INSERT_STRING (#Name, Name ? Name : "")
591 DEFINE (dir_prefix);
592 DEFINE (parser_file_name);
593 DEFINE (spec_defines_file);
594 DEFINE (spec_file_prefix);
595 DEFINE (spec_graph_file);
596 DEFINE (spec_name_prefix);
597 DEFINE (spec_outfile);
598 DEFINE (spec_verbose_file);
599 #undef DEFINE
600
601 /* Find the right skeleton file, and add muscles about the skeletons. */
602 if (skeleton)
603 MUSCLE_INSERT_C_STRING ("skeleton", skeleton);
604 else
605 skeleton = language->skeleton;
606
607 /* About the skeletons. */
608 {
609 char const *pkgdatadir = getenv ("BISON_PKGDATADIR");
610 /* b4_pkgdatadir is used inside m4_include in the skeletons, so digraphs
611 would never be expanded. Hopefully no one has M4-special characters in
612 his Bison installation path. */
613 MUSCLE_INSERT_STRING_RAW ("pkgdatadir",
614 pkgdatadir ? pkgdatadir : PKGDATADIR);
615 }
616 }
617
618
619 /*----------------------------------------------------------.
620 | Output the parsing tables and the parser code to ftable. |
621 `----------------------------------------------------------*/
622
623 void
624 output (void)
625 {
626 obstack_init (&format_obstack);
627
628 prepare_symbols ();
629 prepare_rules ();
630 prepare_states ();
631 prepare_actions ();
632
633 prepare ();
634
635 /* Process the selected skeleton file. */
636 output_skeleton ();
637
638 obstack_free (&format_obstack, NULL);
639 }