1/* util.c: Utility routines for bc. */
2
3/*  This file is part of GNU bc.
4    Copyright (C) 1991-1994, 1997, 2000 Free Software Foundation, Inc.
5
6    This program is free software; you can redistribute it and/or modify
7    it under the terms of the GNU General Public License as published by
8    the Free Software Foundation; either version 2 of the License , or
9    (at your option) any later version.
10
11    This program is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14    GNU General Public License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with this program; see the file COPYING.  If not, write to
18      The Free Software Foundation, Inc.
19      59 Temple Place, Suite 330
20      Boston, MA 02111 USA
21
22    You may contact the author by:
23       e-mail:  philnelson@acm.org
24      us-mail:  Philip A. Nelson
25                Computer Science Department, 9062
26                Western Washington University
27                Bellingham, WA 98226-9062
28
29*************************************************************************/
30
31#ifdef __APPLE__
32#include <get_compat.h>
33#else  /* !__APPLE__ */
34#define COMPAT_MODE(a,b) (1)
35#endif /* __APPLE__ */
36
37#include "bcdefs.h"
38#ifndef VARARGS
39#include <stdarg.h>
40#else
41#include <varargs.h>
42#endif
43#include "global.h"
44#include "proto.h"
45
46
47/* strcopyof mallocs new memory and copies a string to to the new
48   memory. */
49
50char *
51strcopyof (str)
52     char *str;
53{
54  char *temp;
55
56  temp = (char *) bc_malloc (strlen (str)+1);
57  return (strcpy (temp,str));
58}
59
60
61/* nextarg adds another value to the list of arguments. */
62
63arg_list *
64nextarg (args, val, is_var)
65     arg_list *args;
66     int val;
67     int is_var;
68{ arg_list *temp;
69
70  temp = (arg_list *) bc_malloc (sizeof (arg_list));
71  temp->av_name = val;
72  temp->arg_is_var = is_var;
73  temp->next = args;
74
75  return (temp);
76}
77
78
79/* For generate, we must produce a string in the form
80    "val,val,...,val".  We also need a couple of static variables
81   for retaining old generated strings.  It also uses a recursive
82   function that builds the string. */
83
84static char *arglist1 = NULL, *arglist2 = NULL;
85
86
87/* make_arg_str does the actual construction of the argument string.
88   ARGS is the pointer to the list and LEN is the maximum number of
89   characters needed.  1 char is the minimum needed.
90 */
91
92_PROTOTYPE (static char *make_arg_str, (arg_list *args, int len));
93
94static char *
95make_arg_str (args, len)
96      arg_list *args;
97      int len;
98{
99  char *temp;
100  char sval[20];
101
102  /* Recursive call. */
103  if (args != NULL)
104    temp = make_arg_str (args->next, len+12);
105  else
106    {
107      temp = (char *) bc_malloc (len);
108      *temp = 0;
109      return temp;
110    }
111
112  /* Add the current number to the end of the string. */
113  if (args->arg_is_var)
114    if (len != 1)
115      sprintf (sval, "*%d,", args->av_name);
116    else
117      sprintf (sval, "*%d", args->av_name);
118  else
119    if (len != 1)
120      sprintf (sval, "%d,", args->av_name);
121    else
122      sprintf (sval, "%d", args->av_name);
123  temp = strcat (temp, sval);
124  return (temp);
125}
126
127char *
128arg_str (args)
129     arg_list *args;
130{
131  if (arglist2 != NULL)
132    free (arglist2);
133  arglist2 = arglist1;
134  arglist1 = make_arg_str (args, 1);
135  return (arglist1);
136}
137
138char *
139call_str (args)
140     arg_list *args;
141{
142  arg_list *temp;
143  int       arg_count;
144  int       ix;
145
146  if (arglist2 != NULL)
147    free (arglist2);
148  arglist2 = arglist1;
149
150  /* Count the number of args and add the 0's and 1's. */
151  for (temp = args, arg_count = 0; temp != NULL; temp = temp->next)
152    arg_count++;
153  arglist1 = (char *) bc_malloc(arg_count+1);
154  for (temp = args, ix=0; temp != NULL; temp = temp->next)
155    arglist1[ix++] = ( temp->av_name ? '1' : '0');
156  arglist1[ix] = 0;
157
158  return (arglist1);
159}
160
161/* free_args frees an argument list ARGS. */
162
163void
164free_args (args)
165      arg_list *args;
166{
167  arg_list *temp;
168
169  temp = args;
170  while (temp != NULL)
171    {
172      args = args->next;
173      free (temp);
174      temp = args;
175    }
176}
177
178
179/* Check for valid parameter (PARAMS) and auto (AUTOS) lists.
180   There must be no duplicates any where.  Also, this is where
181   warnings are generated for array parameters. */
182
183void
184check_params ( params, autos )
185     arg_list *params, *autos;
186{
187  arg_list *tmp1, *tmp2;
188
189  /* Check for duplicate parameters. */
190  if (params != NULL)
191    {
192      tmp1 = params;
193      while (tmp1 != NULL)
194	{
195	  tmp2 = tmp1->next;
196	  while (tmp2 != NULL)
197	    {
198	      if (tmp2->av_name == tmp1->av_name)
199		yyerror ("duplicate parameter names");
200	      tmp2 = tmp2->next;
201	    }
202	  if (tmp1->arg_is_var)
203	    warn ("Variable array parameter");
204	  tmp1 = tmp1->next;
205	}
206    }
207
208  /* Check for duplicate autos. */
209  if (autos != NULL)
210    {
211      tmp1 = autos;
212      while (tmp1 != NULL)
213	{
214	  tmp2 = tmp1->next;
215	  while (tmp2 != NULL)
216	    {
217	      if (tmp2->av_name == tmp1->av_name)
218		yyerror ("duplicate auto variable names");
219	      tmp2 = tmp2->next;
220	    }
221	  if (tmp1->arg_is_var)
222	    yyerror ("* not allowed here");
223	  tmp1 = tmp1->next;
224	}
225    }
226
227  /* Check for duplicate between parameters and autos. */
228  if ((params != NULL) && (autos != NULL))
229    {
230      tmp1 = params;
231      while (tmp1 != NULL)
232	{
233	  tmp2 = autos;
234	  while (tmp2 != NULL)
235	    {
236	      if (tmp2->av_name == tmp1->av_name)
237		yyerror ("variable in both parameter and auto lists");
238	      tmp2 = tmp2->next;
239	    }
240	  tmp1 = tmp1->next;
241	}
242    }
243}
244
245
246/* Initialize the code generator the parser. */
247
248void
249init_gen ()
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}
263
264
265/* generate code STR for the machine. */
266
267void
268generate (str)
269      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
289void
290run_code()
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
316void
317out_char (ch)
318     int ch;
319{
320  if (ch == '\n')
321    {
322      out_col = 0;
323      putchar ('\n');
324    }
325  else
326    {
327      out_col++;
328      if (out_col == line_size-1)
329	{
330	  putchar ('\\');
331	  putchar ('\n');
332	  out_col = 1;
333	}
334      putchar (ch);
335    }
336}
337
338/* Output routines: Write a character CH to the standard output.
339   It keeps track of the number of characters output and may
340   break the output with a "\<cr>".  This one is for strings.
341   In POSIX bc, strings are not broken across lines. */
342
343void
344out_schar (ch)
345     int ch;
346{
347  if (ch == '\n')
348    {
349      out_col = 0;
350      putchar ('\n');
351    }
352  else
353    {
354      if (!std_only && !COMPAT_MODE("bin/bc", "Unix2003"))
355	{
356	  out_col++;
357	  if (out_col == line_size-1)
358	    {
359	      putchar ('\\');
360	      putchar ('\n');
361	      out_col = 1;
362	    }
363	}
364      putchar (ch);
365    }
366}
367
368
369/* The following are "Symbol Table" routines for the parser. */
370
371/*  find_id returns a pointer to node in TREE that has the correct
372    ID.  If there is no node in TREE with ID, NULL is returned. */
373
374id_rec *
375find_id (tree, id)
376     id_rec *tree;
377     char   *id;
378{
379  int cmp_result;
380
381  /* Check for an empty tree. */
382  if (tree == NULL)
383    return NULL;
384
385  /* Recursively search the tree. */
386  cmp_result = strcmp (id, tree->id);
387  if (cmp_result == 0)
388    return tree;  /* This is the item. */
389  else if (cmp_result < 0)
390    return find_id (tree->left, id);
391  else
392    return find_id (tree->right, id);
393}
394
395
396/* insert_id_rec inserts a NEW_ID rec into the tree whose ROOT is
397   provided.  insert_id_rec returns TRUE if the tree height from
398   ROOT down is increased otherwise it returns FALSE.  This is a
399   recursive balanced binary tree insertion algorithm. */
400
401int insert_id_rec (root, new_id)
402     id_rec **root;
403     id_rec *new_id;
404{
405  id_rec *A, *B;
406
407  /* If root is NULL, this where it is to be inserted. */
408  if (*root == NULL)
409    {
410      *root = new_id;
411      new_id->left = NULL;
412      new_id->right = NULL;
413      new_id->balance = 0;
414      return (TRUE);
415    }
416
417  /* We need to search for a leaf. */
418  if (strcmp (new_id->id, (*root)->id) < 0)
419    {
420      /* Insert it on the left. */
421      if (insert_id_rec (&((*root)->left), new_id))
422	{
423	  /* The height increased. */
424	  (*root)->balance --;
425
426      switch ((*root)->balance)
427	{
428	case  0:  /* no height increase. */
429	  return (FALSE);
430	case -1:  /* height increase. */
431	  return (FALSE);
432	case -2:  /* we need to do a rebalancing act. */
433	  A = *root;
434	  B = (*root)->left;
435	  if (B->balance <= 0)
436	    {
437	      /* Single Rotate. */
438	      A->left = B->right;
439	      B->right = A;
440	      *root = B;
441	      A->balance = 0;
442	      B->balance = 0;
443	    }
444	  else
445	    {
446	      /* Double Rotate. */
447	      *root = B->right;
448	      B->right = (*root)->left;
449	      A->left = (*root)->right;
450	      (*root)->left = B;
451	      (*root)->right = A;
452	      switch ((*root)->balance)
453		{
454		case -1:
455		  A->balance = 1;
456		  B->balance = 0;
457		  break;
458		case  0:
459		  A->balance = 0;
460		  B->balance = 0;
461		  break;
462		case  1:
463		  A->balance = 0;
464		  B->balance = -1;
465		  break;
466		}
467	      (*root)->balance = 0;
468	    }
469	}
470	}
471    }
472  else
473    {
474      /* Insert it on the right. */
475      if (insert_id_rec (&((*root)->right), new_id))
476	{
477	  /* The height increased. */
478	  (*root)->balance ++;
479	  switch ((*root)->balance)
480	    {
481	    case 0:  /* no height increase. */
482	      return (FALSE);
483	    case 1:  /* height increase. */
484	      return (FALSE);
485	    case 2:  /* we need to do a rebalancing act. */
486	      A = *root;
487	      B = (*root)->right;
488	      if (B->balance >= 0)
489		{
490		  /* Single Rotate. */
491		  A->right = B->left;
492		  B->left = A;
493		  *root = B;
494		  A->balance = 0;
495		  B->balance = 0;
496		}
497	      else
498		{
499		  /* Double Rotate. */
500		  *root = B->left;
501		  B->left = (*root)->right;
502		  A->right = (*root)->left;
503		  (*root)->left = A;
504		  (*root)->right = B;
505		  switch ((*root)->balance)
506		    {
507		    case -1:
508		      A->balance = 0;
509		      B->balance = 1;
510		      break;
511		    case  0:
512		      A->balance = 0;
513		      B->balance = 0;
514		      break;
515		    case  1:
516		      A->balance = -1;
517		      B->balance = 0;
518		      break;
519		    }
520		  (*root)->balance = 0;
521		}
522	    }
523	}
524    }
525
526  /* If we fall through to here, the tree did not grow in height. */
527  return (FALSE);
528}
529
530
531/* Initialize variables for the symbol table tree. */
532
533void
534init_tree()
535{
536  name_tree  = NULL;
537  next_array = 1;
538  next_func  = 1;
539  /* 0 => ibase, 1 => obase, 2 => scale, 3 => history, 4 => last. */
540  next_var   = 5;
541}
542
543
544/* Lookup routines for symbol table names. */
545
546int
547lookup (name, namekind)
548     char *name;
549     int  namekind;
550{
551  id_rec *id;
552
553  /* Warn about non-standard name. */
554  if (strlen(name) != 1)
555    warn ("multiple letter name - %s", name);
556
557  /* Look for the id. */
558  id = find_id (name_tree, name);
559  if (id == NULL)
560    {
561      /* We need to make a new item. */
562      id = (id_rec *) bc_malloc (sizeof (id_rec));
563      id->id = strcopyof (name);
564      id->a_name = 0;
565      id->f_name = 0;
566      id->v_name = 0;
567      insert_id_rec (&name_tree, id);
568    }
569
570  /* Return the correct value. */
571  switch (namekind)
572    {
573
574    case ARRAY:
575      /* ARRAY variable numbers are returned as negative numbers. */
576      if (id->a_name != 0)
577	{
578	  free (name);
579	  return (-id->a_name);
580	}
581      id->a_name = next_array++;
582      a_names[id->a_name] = name;
583      if (id->a_name < MAX_STORE)
584	{
585	  if (id->a_name >= a_count)
586	    more_arrays ();
587	  return (-id->a_name);
588	}
589      yyerror ("Too many array variables");
590      exit (1);
591
592    case FUNCT:
593    case FUNCTDEF:
594      if (id->f_name != 0)
595	{
596	  free(name);
597	  /* Check to see if we are redefining a math lib function. */
598	  if (use_math && namekind == FUNCTDEF && id->f_name <= 6)
599	    id->f_name = next_func++;
600	  return (id->f_name);
601	}
602      id->f_name = next_func++;
603      f_names[id->f_name] = name;
604      if (id->f_name < MAX_STORE)
605	{
606	  if (id->f_name >= f_count)
607	    more_functions ();
608	  return (id->f_name);
609	}
610      yyerror ("Too many functions");
611      exit (1);
612
613    case SIMPLE:
614      if (id->v_name != 0)
615	{
616	  free(name);
617	  return (id->v_name);
618	}
619      id->v_name = next_var++;
620      v_names[id->v_name - 1] = name;
621      if (id->v_name <= MAX_STORE)
622	{
623	  if (id->v_name >= v_count)
624	    more_variables ();
625	  return (id->v_name);
626	}
627      yyerror ("Too many variables");
628      exit (1);
629    }
630
631  yyerror ("End of util.c/lookup() reached.  Please report this bug.");
632  exit (1);
633  /* not reached */
634}
635
636
637/* Print the welcome banner. */
638
639void
640welcome()
641{
642  printf ("This is free software with ABSOLUTELY NO WARRANTY.\n");
643  printf ("For details type `warranty'. \n");
644}
645
646/* Print out the version information. */
647void
648show_bc_version()
649{
650  printf("%s %s\n%s\n", PACKAGE, VERSION, BC_COPYRIGHT);
651}
652
653
654/* Print out the warranty information. */
655
656void
657warranty(prefix)
658     char *prefix;
659{
660  printf ("\n%s", prefix);
661  show_bc_version ();
662  printf ("\n"
663"    This program is free software; you can redistribute it and/or modify\n"
664"    it under the terms of the GNU General Public License as published by\n"
665"    the Free Software Foundation; either version 2 of the License , or\n"
666"    (at your option) any later version.\n\n"
667"    This program is distributed in the hope that it will be useful,\n"
668"    but WITHOUT ANY WARRANTY; without even the implied warranty of\n"
669"    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n"
670"    GNU General Public License for more details.\n\n"
671"    You should have received a copy of the GNU General Public License\n"
672"    along with this program. If not, write to\n\n"
673"       The Free Software Foundation, Inc.\n"
674"       59 Temple Place, Suite 330\n"
675"       Boston, MA 02111, USA.\n\n");
676}
677
678/* Print out the limits of this program. */
679
680void
681limits()
682{
683  printf ("BC_BASE_MAX     = %d\n",  BC_BASE_MAX);
684  printf ("BC_DIM_MAX      = %ld\n", (long) BC_DIM_MAX);
685  printf ("BC_SCALE_MAX    = %d\n",  BC_SCALE_MAX);
686  printf ("BC_STRING_MAX   = %d\n",  BC_STRING_MAX);
687  printf ("MAX Exponent    = %ld\n", (long) LONG_MAX);
688  printf ("Number of vars  = %ld\n", (long) MAX_STORE);
689#ifdef OLD_EQ_OP
690  printf ("Old assignment operatiors are valid. (=-, =+, ...)\n");
691#endif
692}
693
694/* bc_malloc will check the return value so all other places do not
695   have to do it!  SIZE is the number of bytes to allocate. */
696
697char *
698bc_malloc (size)
699     int size;
700{
701  char *ptr;
702
703  ptr = (char *) malloc (size);
704  if (ptr == NULL)
705    out_of_memory ();
706
707  return ptr;
708}
709
710
711/* The following routines are error routines for various problems. */
712
713/* Malloc could not get enought memory. */
714
715void
716out_of_memory()
717{
718  fprintf (stderr, "Fatal error: Out of memory for malloc.\n");
719  exit (1);
720}
721
722
723
724/* The standard yyerror routine.  Built with variable number of argumnets. */
725
726#ifndef VARARGS
727#ifdef __STDC__
728void
729yyerror (char *str, ...)
730#else
731void
732yyerror (str)
733     char *str;
734#endif
735#else
736void
737yyerror (str, va_alist)
738     char *str;
739#endif
740{
741  char *name;
742  va_list args;
743
744#ifndef VARARGS
745   va_start (args, str);
746#else
747   va_start (args);
748#endif
749  if (is_std_in)
750    name = "(standard_in)";
751  else
752    name = file_name;
753  fprintf (stderr,"%s %d: ",name,line_no);
754  vfprintf (stderr, str, args);
755  fprintf (stderr, "\n");
756  had_error = TRUE;
757  va_end (args);
758}
759
760
761/* The routine to produce warnings about non-standard features
762   found during parsing. */
763
764#ifndef VARARGS
765#ifdef __STDC__
766void
767warn (char *mesg, ...)
768#else
769void
770warn (mesg)
771     char *mesg;
772#endif
773#else
774void
775warn (mesg, va_alist)
776     char *mesg;
777#endif
778{
779  char *name;
780  va_list args;
781
782#ifndef VARARGS
783  va_start (args, mesg);
784#else
785  va_start (args);
786#endif
787  if (std_only)
788    {
789      if (is_std_in)
790	name = "(standard_in)";
791      else
792	name = file_name;
793      fprintf (stderr,"%s %d: ",name,line_no);
794      vfprintf (stderr, mesg, args);
795      fprintf (stderr, "\n");
796      had_error = TRUE;
797    }
798  else
799    if (warn_not_std)
800      {
801	if (is_std_in)
802	  name = "(standard_in)";
803	else
804	  name = file_name;
805	fprintf (stderr,"%s %d: (Warning) ",name,line_no);
806	vfprintf (stderr, mesg, args);
807	fprintf (stderr, "\n");
808      }
809  va_end (args);
810}
811
812/* Runtime error will  print a message and stop the machine. */
813
814#ifndef VARARGS
815#ifdef __STDC__
816void
817rt_error (char *mesg, ...)
818#else
819void
820rt_error (mesg)
821     char *mesg;
822#endif
823#else
824void
825rt_error (mesg, va_alist)
826     char *mesg;
827#endif
828{
829  va_list args;
830
831  fprintf (stderr, "Runtime error (func=%s, adr=%d): ",
832	   f_names[pc.pc_func], pc.pc_addr);
833#ifndef VARARGS
834  va_start (args, mesg);
835#else
836  va_start (args);
837#endif
838  vfprintf (stderr, mesg, args);
839  va_end (args);
840
841  fprintf (stderr, "\n");
842  runtime_error = TRUE;
843}
844
845
846/* A runtime warning tells of some action taken by the processor that
847   may change the program execution but was not enough of a problem
848   to stop the execution. */
849
850#ifndef VARARGS
851#ifdef __STDC__
852void
853rt_warn (char *mesg, ...)
854#else
855void
856rt_warn (mesg)
857     char *mesg;
858#endif
859#else
860void
861rt_warn (mesg, va_alist)
862     char *mesg;
863#endif
864{
865  va_list args;
866
867  fprintf (stderr, "Runtime warning (func=%s, adr=%d): ",
868	   f_names[pc.pc_func], pc.pc_addr);
869#ifndef VARARGS
870  va_start (args, mesg);
871#else
872  va_start (args);
873#endif
874  vfprintf (stderr, mesg, args);
875  va_end (args);
876
877  fprintf (stderr, "\n");
878}
879