1 /* $NetBSD: util.c,v 1.2 2017/04/18 04:35:18 maya Exp $ */
2
3 /*
4 * Copyright (C) 1991-1994, 1997, 2006, 2008, 2012-2017 Free Software Foundation, Inc.
5 * Copyright (C) 2016-2017 Philip A. Nelson.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. The names Philip A. Nelson and Free Software Foundation may not be
18 * used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY PHILIP A. NELSON ``AS IS'' AND ANY EXPRESS OR
22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 * IN NO EVENT SHALL PHILIP A. NELSON OR THE FREE SOFTWARE FOUNDATION BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
31 * THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 /* util.c: Utility routines for bc. */
35
36 #include "bcdefs.h"
37 #ifndef VARARGS
38 #include <stdarg.h>
39 #else
40 #include <varargs.h>
41 #endif
42 #include "proto.h"
43
44
45 /* strcopyof mallocs new memory and copies a string to to the new
46 memory. */
47
48 char *
strcopyof(const char * str)49 strcopyof (const char *str)
50 {
51 char *temp;
52
53 temp = bc_malloc (strlen (str)+1);
54 return (strcpy (temp,str));
55 }
56
57
58 /* nextarg adds another value to the list of arguments. */
59
60 arg_list *
nextarg(arg_list * args,int val,int is_var)61 nextarg (arg_list *args, int val, int is_var)
62 { arg_list *temp;
63
64 temp = bc_malloc (sizeof (arg_list));
65 temp->av_name = val;
66 temp->arg_is_var = is_var;
67 temp->next = args;
68
69 return (temp);
70 }
71
72
73 /* For generate, we must produce a string in the form
74 "val,val,...,val". We also need a couple of static variables
75 for retaining old generated strings. It also uses a recursive
76 function that builds the string. */
77
78 static char *arglist1 = NULL, *arglist2 = NULL;
79
80
81 /* make_arg_str does the actual construction of the argument string.
82 ARGS is the pointer to the list and LEN is the maximum number of
83 characters needed. 1 char is the minimum needed.
84 */
85
86 static char *make_arg_str (arg_list *args, int len);
87
88 static char *
make_arg_str(arg_list * args,int len)89 make_arg_str (arg_list *args, int len)
90 {
91 char *temp;
92 char sval[30];
93
94 /* Recursive call. */
95 if (args != NULL)
96 temp = make_arg_str (args->next, len+12);
97 else
98 {
99 temp = bc_malloc (len);
100 *temp = 0;
101 return temp;
102 }
103
104 /* Add the current number to the end of the string. */
105 if (args->arg_is_var)
106 if (len != 1)
107 snprintf (sval, sizeof(sval), "*%d,", args->av_name);
108 else
109 snprintf (sval, sizeof(sval), "*%d", args->av_name);
110 else
111 if (len != 1)
112 snprintf (sval, sizeof(sval), "%d,", args->av_name);
113 else
114 snprintf (sval, sizeof(sval), "%d", args->av_name);
115 temp = strcat (temp, sval);
116 return (temp);
117 }
118
119 char *
arg_str(arg_list * args)120 arg_str (arg_list *args)
121 {
122 if (arglist2 != NULL)
123 free (arglist2);
124 arglist2 = arglist1;
125 arglist1 = make_arg_str (args, 1);
126 return (arglist1);
127 }
128
129 char *
call_str(arg_list * args)130 call_str (arg_list *args)
131 {
132 arg_list *temp;
133 int arg_count;
134 int ix;
135
136 if (arglist2 != NULL)
137 free (arglist2);
138 arglist2 = arglist1;
139
140 /* Count the number of args and add the 0's and 1's. */
141 for (temp = args, arg_count = 0; temp != NULL; temp = temp->next)
142 arg_count++;
143 arglist1 = bc_malloc(arg_count+1);
144 for (temp = args, ix=0; temp != NULL; temp = temp->next)
145 arglist1[ix++] = ( temp->av_name ? '1' : '0');
146 arglist1[ix] = 0;
147
148 return (arglist1);
149 }
150
151 /* free_args frees an argument list ARGS. */
152
153 void
free_args(arg_list * args)154 free_args (arg_list *args)
155 {
156 arg_list *temp;
157
158 temp = args;
159 while (temp != NULL)
160 {
161 args = args->next;
162 free (temp);
163 temp = args;
164 }
165 }
166
167
168 /* Check for valid parameter (PARAMS) and auto (AUTOS) lists.
169 There must be no duplicates any where. Also, this is where
170 warnings are generated for array parameters. */
171
172 void
check_params(arg_list * params,arg_list * autos)173 check_params (arg_list *params, arg_list *autos)
174 {
175 arg_list *tmp1, *tmp2;
176
177 /* Check for duplicate parameters. */
178 if (params != NULL)
179 {
180 tmp1 = params;
181 while (tmp1 != NULL)
182 {
183 tmp2 = tmp1->next;
184 while (tmp2 != NULL)
185 {
186 if (tmp2->av_name == tmp1->av_name)
187 yyerror ("duplicate parameter names");
188 tmp2 = tmp2->next;
189 }
190 if (tmp1->arg_is_var)
191 ct_warn ("Variable array parameter");
192 tmp1 = tmp1->next;
193 }
194 }
195
196 /* Check for duplicate autos. */
197 if (autos != NULL)
198 {
199 tmp1 = autos;
200 while (tmp1 != NULL)
201 {
202 tmp2 = tmp1->next;
203 while (tmp2 != NULL)
204 {
205 if (tmp2->av_name == tmp1->av_name)
206 yyerror ("duplicate auto variable names");
207 tmp2 = tmp2->next;
208 }
209 if (tmp1->arg_is_var)
210 yyerror ("* not allowed here");
211 tmp1 = tmp1->next;
212 }
213 }
214
215 /* Check for duplicate between parameters and autos. */
216 if ((params != NULL) && (autos != NULL))
217 {
218 tmp1 = params;
219 while (tmp1 != NULL)
220 {
221 tmp2 = autos;
222 while (tmp2 != NULL)
223 {
224 if (tmp2->av_name == tmp1->av_name)
225 yyerror ("variable in both parameter and auto lists");
226 tmp2 = tmp2->next;
227 }
228 tmp1 = tmp1->next;
229 }
230 }
231 }
232
233 /* genstr management to avoid buffer overflow. */
234 void
set_genstr_size(int size)235 set_genstr_size (int size)
236 {
237 if (size > genlen) {
238 if (genstr != NULL)
239 free(genstr);
240 genstr = bc_malloc (size);
241 genlen = size;
242 }
243 }
244
245
246 /* Initialize the code generator the parser. */
247
248 void
init_gen(void)249 init_gen (void)
250 {
251 /* Get things ready. */
252 break_label = 0;
253 continue_label = 0;
254 next_label = 1;
255 out_count = 2;
256 if (compile_only)
257 printf ("@i");
258 else
259 init_load ();
260 had_error = FALSE;
261 did_gen = FALSE;
262 set_genstr_size (64);
263 }
264
265
266 /* generate code STR for the machine. */
267
268 void
generate(const char * str)269 generate (const char *str)
270 {
271 did_gen = TRUE;
272 if (compile_only)
273 {
274 printf ("%s",str);
275 out_count += strlen(str);
276 if (out_count > 60)
277 {
278 printf ("\n");
279 out_count = 0;
280 }
281 }
282 else
283 load_code (str);
284 }
285
286
287 /* Execute the current code as loaded. */
288
289 void
run_code(void)290 run_code(void)
291 {
292 /* If no compile errors run the current code. */
293 if (!had_error && did_gen)
294 {
295 if (compile_only)
296 {
297 printf ("@r\n");
298 out_count = 0;
299 }
300 else
301 execute ();
302 }
303
304 /* Reinitialize the code generation and machine. */
305 if (did_gen)
306 init_gen();
307 else
308 had_error = FALSE;
309 }
310
311
312 /* Output routines: Write a character CH to the standard output.
313 It keeps track of the number of characters output and may
314 break the output with a "\<cr>". Always used for numbers. */
315
316 void
out_char(int ch)317 out_char (int ch)
318 {
319 if (ch == '\n')
320 {
321 out_col = 0;
322 putchar ('\n');
323 }
324 else
325 {
326 out_col++;
327 if (out_col == line_size-1 && line_size != 0)
328 {
329 putchar ('\\');
330 putchar ('\n');
331 out_col = 1;
332 }
333 putchar (ch);
334 }
335 }
336
337 /* Output routines: Write a character CH to the standard output.
338 It keeps track of the number of characters output and may
339 break the output with a "\<cr>". This one is for strings.
340 In POSIX bc, strings are not broken across lines. */
341
342 void
out_schar(int ch)343 out_schar (int ch)
344 {
345 if (ch == '\n')
346 {
347 out_col = 0;
348 putchar ('\n');
349 }
350 else
351 {
352 if (!std_only)
353 {
354 out_col++;
355 if (out_col == line_size-1 && line_size != 0)
356 {
357 putchar ('\\');
358 putchar ('\n');
359 out_col = 1;
360 }
361 }
362 putchar (ch);
363 }
364 }
365
366
367 /* The following are "Symbol Table" routines for the parser. */
368
369 /* find_id returns a pointer to node in TREE that has the correct
370 ID. If there is no node in TREE with ID, NULL is returned. */
371
372 id_rec *
find_id(id_rec * tree,const char * id)373 find_id (id_rec *tree, const char *id)
374 {
375 int cmp_result;
376
377 /* Check for an empty tree. */
378 if (tree == NULL)
379 return NULL;
380
381 /* Recursively search the tree. */
382 cmp_result = strcmp (id, tree->id);
383 if (cmp_result == 0)
384 return tree; /* This is the item. */
385 else if (cmp_result < 0)
386 return find_id (tree->left, id);
387 else
388 return find_id (tree->right, id);
389 }
390
391
392 /* insert_id_rec inserts a NEW_ID rec into the tree whose ROOT is
393 provided. insert_id_rec returns TRUE if the tree height from
394 ROOT down is increased otherwise it returns FALSE. This is a
395 recursive balanced binary tree insertion algorithm. */
396
insert_id_rec(id_rec ** root,id_rec * new_id)397 int insert_id_rec (id_rec **root, id_rec *new_id)
398 {
399 id_rec *A, *B;
400
401 /* If root is NULL, this where it is to be inserted. */
402 if (*root == NULL)
403 {
404 *root = new_id;
405 new_id->left = NULL;
406 new_id->right = NULL;
407 new_id->balance = 0;
408 return (TRUE);
409 }
410
411 /* We need to search for a leaf. */
412 if (strcmp (new_id->id, (*root)->id) < 0)
413 {
414 /* Insert it on the left. */
415 if (insert_id_rec (&((*root)->left), new_id))
416 {
417 /* The height increased. */
418 (*root)->balance --;
419
420 switch ((*root)->balance)
421 {
422 case 0: /* no height increase. */
423 return (FALSE);
424 case -1: /* height increase. */
425 return (TRUE);
426 case -2: /* we need to do a rebalancing act. */
427 A = *root;
428 B = (*root)->left;
429 if (B->balance <= 0)
430 {
431 /* Single Rotate. */
432 A->left = B->right;
433 B->right = A;
434 *root = B;
435 A->balance = 0;
436 B->balance = 0;
437 }
438 else
439 {
440 /* Double Rotate. */
441 *root = B->right;
442 B->right = (*root)->left;
443 A->left = (*root)->right;
444 (*root)->left = B;
445 (*root)->right = A;
446 switch ((*root)->balance)
447 {
448 case -1:
449 A->balance = 1;
450 B->balance = 0;
451 break;
452 case 0:
453 A->balance = 0;
454 B->balance = 0;
455 break;
456 case 1:
457 A->balance = 0;
458 B->balance = -1;
459 break;
460 }
461 (*root)->balance = 0;
462 }
463 }
464 }
465 }
466 else
467 {
468 /* Insert it on the right. */
469 if (insert_id_rec (&((*root)->right), new_id))
470 {
471 /* The height increased. */
472 (*root)->balance ++;
473
474 switch ((*root)->balance)
475 {
476 case 0: /* no height increase. */
477 return (FALSE);
478 case 1: /* height increase. */
479 return (TRUE);
480 case 2: /* we need to do a rebalancing act. */
481 A = *root;
482 B = (*root)->right;
483 if (B->balance >= 0)
484 {
485 /* Single Rotate. */
486 A->right = B->left;
487 B->left = A;
488 *root = B;
489 A->balance = 0;
490 B->balance = 0;
491 }
492 else
493 {
494 /* Double Rotate. */
495 *root = B->left;
496 B->left = (*root)->right;
497 A->right = (*root)->left;
498 (*root)->left = A;
499 (*root)->right = B;
500 switch ((*root)->balance)
501 {
502 case -1:
503 A->balance = 0;
504 B->balance = 1;
505 break;
506 case 0:
507 A->balance = 0;
508 B->balance = 0;
509 break;
510 case 1:
511 A->balance = -1;
512 B->balance = 0;
513 break;
514 }
515 (*root)->balance = 0;
516 }
517 }
518 }
519 }
520
521 /* If we fall through to here, the tree did not grow in height. */
522 return (FALSE);
523 }
524
525
526 /* Initialize variables for the symbol table tree. */
527
528 void
init_tree(void)529 init_tree(void)
530 {
531 name_tree = NULL;
532 next_array = 1;
533 next_func = 1;
534 /* 0 => ibase, 1 => obase, 2 => scale, 3 => history, 4 => last. */
535 next_var = 5;
536 }
537
538
539 /* Lookup routines for symbol table names. */
540
541 int
lookup(char * name,int namekind)542 lookup (char *name, int namekind)
543 {
544 id_rec *id;
545
546 /* Warn about non-standard name. */
547 if (strlen(name) != 1)
548 ct_warn ("multiple letter name - %s", name);
549
550 /* Look for the id. */
551 id = find_id (name_tree, name);
552 if (id == NULL)
553 {
554 /* We need to make a new item. */
555 id = bc_malloc (sizeof (id_rec));
556 id->id = strcopyof (name);
557 id->a_name = 0;
558 id->f_name = 0;
559 id->v_name = 0;
560 insert_id_rec (&name_tree, id);
561 }
562
563 /* Return the correct value. */
564 switch (namekind)
565 {
566
567 case ARRAY:
568 /* ARRAY variable numbers are returned as negative numbers. */
569 if (id->a_name != 0)
570 {
571 free (name);
572 return (-id->a_name);
573 }
574 id->a_name = next_array++;
575 if (id->a_name < MAX_STORE)
576 {
577 if (id->a_name >= a_count)
578 more_arrays ();
579 a_names[id->a_name] = name;
580 return (-id->a_name);
581 }
582 yyerror ("Too many array variables");
583 bc_exit (1);
584 /*NOTREACHED*/
585
586 case FUNCT:
587 case FUNCTDEF:
588 if (id->f_name != 0)
589 {
590 free(name);
591 /* Check to see if we are redefining a math lib function. */
592 if (use_math && namekind == FUNCTDEF && id->f_name <= 6)
593 id->f_name = next_func++;
594 return (id->f_name);
595 }
596 id->f_name = next_func++;
597 if (id->f_name < MAX_STORE)
598 {
599 if (id->f_name >= f_count)
600 more_functions ();
601 f_names[id->f_name] = name;
602 return (id->f_name);
603 }
604 yyerror ("Too many functions");
605 bc_exit (1);
606 /*NOTREACHED*/
607
608 case SIMPLE:
609 if (id->v_name != 0)
610 {
611 free(name);
612 return (id->v_name);
613 }
614 id->v_name = next_var++;
615 if (id->v_name <= MAX_STORE)
616 {
617 if (id->v_name >= v_count)
618 more_variables ();
619 v_names[id->v_name - 1] = name;
620 return (id->v_name);
621 }
622 yyerror ("Too many variables");
623 bc_exit (1);
624 /*NOTREACHED*/
625
626 }
627
628 yyerror ("End of util.c/lookup() reached. Please report this bug.");
629 bc_exit (1);
630 /*NOTREACHED*/
631 }
632
633 /* Print out the limits of this program. */
634
635 void
limits(void)636 limits(void)
637 {
638 printf ("BC_BASE_MAX = %d\n", BC_BASE_MAX);
639 printf ("BC_DIM_MAX = %ld\n", (long) BC_DIM_MAX);
640 printf ("BC_SCALE_MAX = %d\n", BC_SCALE_MAX);
641 printf ("BC_STRING_MAX = %d\n", BC_STRING_MAX);
642 printf ("MAX Exponent = %ld\n", (long) LONG_MAX);
643 printf ("Number of vars = %ld\n", (long) MAX_STORE);
644 #ifdef OLD_EQ_OP
645 printf ("Old assignment operatiors are valid. (=-, =+, ...)\n");
646 #endif
647 }
648
649 /* bc_malloc will check the return value so all other places do not
650 have to do it! SIZE is the number of bytes to allocate. */
651
652 void *
bc_malloc(size_t size)653 bc_malloc (size_t size)
654 {
655 void *ptr;
656
657 ptr = (void *) malloc (size);
658 if (ptr == NULL)
659 out_of_memory ();
660
661 return ptr;
662 }
663
664
665 /* The following routines are error routines for various problems. */
666
667 /* Malloc could not get enought memory. */
668
669 void
out_of_memory(void)670 out_of_memory(void)
671 {
672 fprintf (stderr, "Fatal error: Out of memory for malloc.\n");
673 bc_exit (1);
674 /*NOTREACHED*/
675 }
676
677
678
679 /* The standard yyerror routine. Built with variable number of argumnets. */
680
681 #ifndef VARARGS
682 #ifdef __STDC__
683 void
yyerror(const char * str,...)684 yyerror (const char *str, ...)
685 #else
686 void
687 yyerror (str)
688 const char *str;
689 #endif
690 #else
691 void
692 yyerror (str, va_alist)
693 const char *str;
694 #endif
695 {
696 const char *name;
697 va_list args;
698
699 #ifndef VARARGS
700 va_start (args, str);
701 #else
702 va_start (args);
703 #endif
704 if (is_std_in)
705 name = "(standard_in)";
706 else
707 name = file_name;
708 fprintf (stderr,"%s %d: ",name,line_no);
709 vfprintf (stderr, str, args);
710 fprintf (stderr, "\n");
711 had_error = TRUE;
712 va_end (args);
713 }
714
715
716 /* The routine to produce warnings about non-standard features
717 found during parsing. */
718
719 #ifndef VARARGS
720 #ifdef __STDC__
721 void
ct_warn(const char * mesg,...)722 ct_warn (const char *mesg, ...)
723 #else
724 void
725 ct_warn (mesg)
726 const char *mesg;
727 #endif
728 #else
729 void
730 ct_warn (mesg, va_alist)
731 const char *mesg;
732 #endif
733 {
734 const char *name;
735 va_list args;
736
737 #ifndef VARARGS
738 va_start (args, mesg);
739 #else
740 va_start (args);
741 #endif
742 if (std_only)
743 {
744 if (is_std_in)
745 name = "(standard_in)";
746 else
747 name = file_name;
748 fprintf (stderr,"%s %d: Error: ",name,line_no);
749 vfprintf (stderr, mesg, args);
750 fprintf (stderr, "\n");
751 had_error = TRUE;
752 }
753 else
754 if (warn_not_std)
755 {
756 if (is_std_in)
757 name = "(standard_in)";
758 else
759 name = file_name;
760 fprintf (stderr,"%s %d: (Warning) ",name,line_no);
761 vfprintf (stderr, mesg, args);
762 fprintf (stderr, "\n");
763 }
764 va_end (args);
765 }
766
767 /* Runtime error will print a message and stop the machine. */
768
769 #ifndef VARARGS
770 #ifdef __STDC__
771 void
rt_error(const char * mesg,...)772 rt_error (const char *mesg, ...)
773 #else
774 void
775 rt_error (mesg)
776 const char *mesg;
777 #endif
778 #else
779 void
780 rt_error (mesg, va_alist)
781 const char *mesg;
782 #endif
783 {
784 va_list args;
785
786 fprintf (stderr, "Runtime error (func=%s, adr=%d): ",
787 f_names[pc.pc_func], pc.pc_addr);
788 #ifndef VARARGS
789 va_start (args, mesg);
790 #else
791 va_start (args);
792 #endif
793 vfprintf (stderr, mesg, args);
794 va_end (args);
795
796 fprintf (stderr, "\n");
797 runtime_error = TRUE;
798 }
799
800
801 /* A runtime warning tells of some action taken by the processor that
802 may change the program execution but was not enough of a problem
803 to stop the execution. */
804
805 #ifndef VARARGS
806 #ifdef __STDC__
807 void
rt_warn(const char * mesg,...)808 rt_warn (const char *mesg, ...)
809 #else
810 void
811 rt_warn (const char *mesg)
812 #endif
813 #else
814 void
815 rt_warn (const char *mesg)
816 #endif
817 {
818 va_list args;
819
820 fprintf (stderr, "Runtime warning (func=%s, adr=%d): ",
821 f_names[pc.pc_func], pc.pc_addr);
822 #ifndef VARARGS
823 va_start (args, mesg);
824 #else
825 va_start (args);
826 #endif
827 vfprintf (stderr, mesg, args);
828 va_end (args);
829
830 fprintf (stderr, "\n");
831 }
832
833 /* bc_exit: Make sure to reset the edit state. */
834
bc_exit(int val)835 void bc_exit(int val)
836 {
837 #if defined(LIBEDIT)
838 if (edit != NULL)
839 el_end(edit);
840 #endif
841 exit(val);
842 /*NOTREACHED*/
843 }
844