xref: /freebsd/contrib/bc/include/lang.h (revision 3332f1b444d4a73238e9f59cca27bfc95fe936bd)
1 /*
2  * *****************************************************************************
3  *
4  * SPDX-License-Identifier: BSD-2-Clause
5  *
6  * Copyright (c) 2018-2021 Gavin D. Howard and contributors.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions are met:
10  *
11  * * Redistributions of source code must retain the above copyright notice, this
12  *   list of conditions and the following disclaimer.
13  *
14  * * Redistributions in binary form must reproduce the above copyright notice,
15  *   this list of conditions and the following disclaimer in the documentation
16  *   and/or other materials provided with the distribution.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28  * POSSIBILITY OF SUCH DAMAGE.
29  *
30  * *****************************************************************************
31  *
32  * Definitions for program data.
33  *
34  */
35 
36 #ifndef BC_LANG_H
37 #define BC_LANG_H
38 
39 #include <stdbool.h>
40 
41 #include <status.h>
42 #include <vector.h>
43 #include <num.h>
44 
45 /// The instructions for bytecode.
46 typedef enum BcInst {
47 
48 #if BC_ENABLED
49 
50 	/// Postfix increment and decrement. Prefix are translated into
51 	/// BC_INST_ONE with either BC_INST_ASSIGN_PLUS or BC_INST_ASSIGN_MINUS.
52 	BC_INST_INC = 0,
53 	BC_INST_DEC,
54 #endif // BC_ENABLED
55 
56 	/// Unary negation.
57 	BC_INST_NEG,
58 
59 	/// Boolean not.
60 	BC_INST_BOOL_NOT,
61 #if BC_ENABLE_EXTRA_MATH
62 	/// Truncation operator.
63 	BC_INST_TRUNC,
64 #endif // BC_ENABLE_EXTRA_MATH
65 
66 	/// These should be self-explanatory.
67 	BC_INST_POWER,
68 	BC_INST_MULTIPLY,
69 	BC_INST_DIVIDE,
70 	BC_INST_MODULUS,
71 	BC_INST_PLUS,
72 	BC_INST_MINUS,
73 
74 #if BC_ENABLE_EXTRA_MATH
75 
76 	/// Places operator.
77 	BC_INST_PLACES,
78 
79 	/// Shift operators.
80 	BC_INST_LSHIFT,
81 	BC_INST_RSHIFT,
82 #endif // BC_ENABLE_EXTRA_MATH
83 
84 	/// Comparison operators.
85 	BC_INST_REL_EQ,
86 	BC_INST_REL_LE,
87 	BC_INST_REL_GE,
88 	BC_INST_REL_NE,
89 	BC_INST_REL_LT,
90 	BC_INST_REL_GT,
91 
92 	/// Boolean or and and.
93 	BC_INST_BOOL_OR,
94 	BC_INST_BOOL_AND,
95 
96 #if BC_ENABLED
97 	/// Same as the normal operators, but assigment. So ^=, *=, /=, etc.
98 	BC_INST_ASSIGN_POWER,
99 	BC_INST_ASSIGN_MULTIPLY,
100 	BC_INST_ASSIGN_DIVIDE,
101 	BC_INST_ASSIGN_MODULUS,
102 	BC_INST_ASSIGN_PLUS,
103 	BC_INST_ASSIGN_MINUS,
104 #if BC_ENABLE_EXTRA_MATH
105 	/// Places and shift assignment operators.
106 	BC_INST_ASSIGN_PLACES,
107 	BC_INST_ASSIGN_LSHIFT,
108 	BC_INST_ASSIGN_RSHIFT,
109 #endif // BC_ENABLE_EXTRA_MATH
110 
111 	/// Normal assignment.
112 	BC_INST_ASSIGN,
113 
114 	/// bc and dc detect when the value from an assignment is not necessary.
115 	/// For example, a plain assignment statement means the value is never used.
116 	/// In those cases, we can get lots of performance back by not even creating
117 	/// a copy at all. In fact, it saves a copy, a push onto the results stack,
118 	/// a pop from the results stack, and a free. Definitely worth it to detect.
119 	BC_INST_ASSIGN_POWER_NO_VAL,
120 	BC_INST_ASSIGN_MULTIPLY_NO_VAL,
121 	BC_INST_ASSIGN_DIVIDE_NO_VAL,
122 	BC_INST_ASSIGN_MODULUS_NO_VAL,
123 	BC_INST_ASSIGN_PLUS_NO_VAL,
124 	BC_INST_ASSIGN_MINUS_NO_VAL,
125 #if BC_ENABLE_EXTRA_MATH
126 	/// Same as above.
127 	BC_INST_ASSIGN_PLACES_NO_VAL,
128 	BC_INST_ASSIGN_LSHIFT_NO_VAL,
129 	BC_INST_ASSIGN_RSHIFT_NO_VAL,
130 #endif // BC_ENABLE_EXTRA_MATH
131 #endif // BC_ENABLED
132 
133 	/// Normal assignment that pushes no value on the stack.
134 	BC_INST_ASSIGN_NO_VAL,
135 
136 	/// Push a constant onto the results stack.
137 	BC_INST_NUM,
138 
139 	/// Push a variable onto the results stack.
140 	BC_INST_VAR,
141 
142 	/// Push an array element onto the results stack.
143 	BC_INST_ARRAY_ELEM,
144 
145 	/// Push an array onto the results stack. This is different from pushing an
146 	/// array *element* onto the results stack; it pushes a reference to the
147 	/// whole array. This is needed in bc for function arguments that are
148 	/// arrays. It is also needed for returning the length of an array.
149 	BC_INST_ARRAY,
150 
151 	/// Push a zero or a one onto the stack. These are special cased because it
152 	/// does help performance, particularly for one since inc/dec operators
153 	/// use it.
154 	BC_INST_ZERO,
155 	BC_INST_ONE,
156 
157 #if BC_ENABLED
158 	/// Push the last printed value onto the stack.
159 	BC_INST_LAST,
160 #endif // BC_ENABLED
161 
162 	/// Push the value of any of the globals onto the stack.
163 	BC_INST_IBASE,
164 	BC_INST_OBASE,
165 	BC_INST_SCALE,
166 
167 #if BC_ENABLE_EXTRA_MATH
168 	/// Push the value of the seed global onto the stack.
169 	BC_INST_SEED,
170 #endif // BC_ENABLE_EXTRA_MATH
171 
172 	/// These are builtin functions.
173 	BC_INST_LENGTH,
174 	BC_INST_SCALE_FUNC,
175 	BC_INST_SQRT,
176 	BC_INST_ABS,
177 
178 #if BC_ENABLE_EXTRA_MATH
179 	/// Another builtin function.
180 	BC_INST_IRAND,
181 #endif // BC_ENABLE_EXTRA_MATH
182 
183 	/// Asciify.
184 	BC_INST_ASCIIFY,
185 
186 	/// Another builtin function.
187 	BC_INST_READ,
188 
189 #if BC_ENABLE_EXTRA_MATH
190 	/// Another builtin function.
191 	BC_INST_RAND,
192 #endif // BC_ENABLE_EXTRA_MATH
193 
194 	/// Return the max for the various globals.
195 	BC_INST_MAXIBASE,
196 	BC_INST_MAXOBASE,
197 	BC_INST_MAXSCALE,
198 #if BC_ENABLE_EXTRA_MATH
199 	/// Return the max value returned by rand().
200 	BC_INST_MAXRAND,
201 #endif // BC_ENABLE_EXTRA_MATH
202 
203 	/// bc line_length() builtin function.
204 	BC_INST_LINE_LENGTH,
205 
206 #if BC_ENABLED
207 
208 	/// bc global_stacks() builtin function.
209 	BC_INST_GLOBAL_STACKS,
210 
211 #endif // BC_ENABLED
212 
213 	/// bc leading_zero() builtin function.
214 	BC_INST_LEADING_ZERO,
215 
216 	/// This is slightly misnamed versus BC_INST_PRINT_POP. Well, it is in bc.
217 	/// dc uses this instruction to print, but not pop. That's valid in dc.
218 	/// However, in bc, it is *never* valid to print without popping. In bc,
219 	/// BC_INST_PRINT_POP is used to indicate when a string should be printed
220 	/// because of a print statement or whether it should be printed raw. The
221 	/// reason for this is because a print statement handles escaped characters.
222 	/// So BC_INST_PRINT_POP is for printing a string from a print statement,
223 	/// BC_INST_PRINT_STR is for printing a string by itself.
224 	///
225 	/// In dc, BC_INST_PRINT_POP prints and pops, and BC_INST_PRINT just prints.
226 	///
227 	/// Oh, and BC_INST_STR pushes a string onto the results stack.
228 	BC_INST_PRINT,
229 	BC_INST_PRINT_POP,
230 	BC_INST_STR,
231 #if BC_ENABLED
232 	BC_INST_PRINT_STR,
233 
234 	/// Jumps unconditionally.
235 	BC_INST_JUMP,
236 
237 	/// Jumps if the top of the results stack is zero (condition failed). It
238 	/// turns out that we only want to jump when conditions fail to "skip" code.
239 	BC_INST_JUMP_ZERO,
240 
241 	/// Call a function.
242 	BC_INST_CALL,
243 
244 	/// Return the top of the stack to the caller.
245 	BC_INST_RET,
246 
247 	/// Return 0 to the caller.
248 	BC_INST_RET0,
249 
250 	/// Special return instruction for void functions.
251 	BC_INST_RET_VOID,
252 
253 	/// Special halt instruction.
254 	BC_INST_HALT,
255 #endif // BC_ENABLED
256 
257 	/// Pop an item off of the results stack.
258 	BC_INST_POP,
259 
260 	/// Swaps the top two items on the results stack.
261 	BC_INST_SWAP,
262 
263 	/// Modular exponentiation.
264 	BC_INST_MODEXP,
265 
266 	/// Do divide and modulus at the same time.
267 	BC_INST_DIVMOD,
268 
269 	/// Turns a number into a string and prints it.
270 	BC_INST_PRINT_STREAM,
271 
272 #if DC_ENABLED
273 
274 	/// dc's return; it pops an executing string off of the stack.
275 	BC_INST_POP_EXEC,
276 
277 	/// Unconditionally execute a string.
278 	BC_INST_EXECUTE,
279 
280 	/// Conditionally execute a string.
281 	BC_INST_EXEC_COND,
282 
283 	/// Prints each item on the results stack, separated by newlines.
284 	BC_INST_PRINT_STACK,
285 
286 	/// Pops everything off of the results stack.
287 	BC_INST_CLEAR_STACK,
288 
289 	/// Pushes the current length of a register stack onto the results stack.
290 	BC_INST_REG_STACK_LEN,
291 
292 	/// Pushes the current length of the results stack onto the results stack.
293 	BC_INST_STACK_LEN,
294 
295 	/// Pushes a copy of the item on the top of the results stack onto the
296 	/// results stack.
297 	BC_INST_DUPLICATE,
298 
299 	/// Copies the value in a register and pushes the copy onto the results
300 	/// stack.
301 	BC_INST_LOAD,
302 
303 	/// Pops an item off of a register stack and pushes it onto the results
304 	/// stack.
305 	BC_INST_PUSH_VAR,
306 
307 	/// Pops an item off of the results stack and pushes it onto a register's
308 	/// stack.
309 	BC_INST_PUSH_TO_VAR,
310 
311 	/// Quit.
312 	BC_INST_QUIT,
313 
314 	/// Quit executing some number of strings.
315 	BC_INST_NQUIT,
316 
317 	/// Push the depth of the execution stack onto the stack.
318 	BC_INST_EXEC_STACK_LEN,
319 
320 #endif // DC_ENABLED
321 
322 	/// Invalid instruction.
323 	BC_INST_INVALID,
324 
325 } BcInst;
326 
327 /// Used by maps to identify where items are in the array.
328 typedef struct BcId {
329 
330 	/// The name of the item.
331 	char *name;
332 
333 	/// The index into the array where the item is.
334 	size_t idx;
335 
336 } BcId;
337 
338 /// The location of a var, array, or array element.
339 typedef struct BcLoc {
340 
341 	/// The index of the var or array.
342 	size_t loc;
343 
344 	/// The index of the array element. Only used for array elements.
345 	size_t idx;
346 
347 } BcLoc;
348 
349 /// An entry for a constant.
350 typedef struct BcConst {
351 
352 	/// The original string as parsed from the source code.
353 	char *val;
354 
355 	/// The last base that the constant was parsed in.
356 	BcBigDig base;
357 
358 	/// The parsed constant.
359 	BcNum num;
360 
361 } BcConst;
362 
363 /// A function. This is also used in dc, not just bc. The reason is that strings
364 /// are executed in dc, and they are converted to functions in order to be
365 /// executed.
366 typedef struct BcFunc {
367 
368 	/// The bytecode instructions.
369 	BcVec code;
370 
371 #if BC_ENABLED
372 
373 	/// The labels. This is a vector of indices. The index is the index into
374 	/// the bytecode vector where the label is.
375 	BcVec labels;
376 
377 	/// The autos for the function. The first items are the parameters, and the
378 	/// arguments to the parameters must match the types in this vector.
379 	BcVec autos;
380 
381 	/// The number of parameters the function takes.
382 	size_t nparams;
383 
384 #endif // BC_ENABLED
385 
386 	/// The strings encountered in the function.
387 	BcVec strs;
388 
389 	/// The constants encountered in the function.
390 	BcVec consts;
391 
392 	/// The function's name.
393 	const char *name;
394 
395 #if BC_ENABLED
396 	/// True if the function is a void function.
397 	bool voidfn;
398 #endif // BC_ENABLED
399 
400 } BcFunc;
401 
402 /// Types of results that can be pushed onto the results stack.
403 typedef enum BcResultType {
404 
405 	/// Result is a variable.
406 	BC_RESULT_VAR,
407 
408 	/// Result is an array element.
409 	BC_RESULT_ARRAY_ELEM,
410 
411 	/// Result is an array. This is only allowed for function arguments or
412 	/// returning the length of the array.
413 	BC_RESULT_ARRAY,
414 
415 	/// Result is a string.
416 	BC_RESULT_STR,
417 
418 	/// Result is a temporary. This is used for the result of almost all
419 	/// expressions.
420 	BC_RESULT_TEMP,
421 
422 	/// Special casing the two below gave performance improvements.
423 
424 	/// Result is a 0.
425 	BC_RESULT_ZERO,
426 
427 	/// Result is a 1. Useful for inc/dec operators.
428 	BC_RESULT_ONE,
429 
430 #if BC_ENABLED
431 
432 	/// Result is the special "last" variable.
433 	BC_RESULT_LAST,
434 
435 	/// Result is the return value of a void function.
436 	BC_RESULT_VOID,
437 #endif // BC_ENABLED
438 
439 	/// Result is the value of ibase.
440 	BC_RESULT_IBASE,
441 
442 	/// Result is the value of obase.
443 	BC_RESULT_OBASE,
444 
445 	/// Result is the value of scale.
446 	BC_RESULT_SCALE,
447 
448 #if BC_ENABLE_EXTRA_MATH
449 
450 	/// Result is the value of seed.
451 	BC_RESULT_SEED,
452 
453 #endif // BC_ENABLE_EXTRA_MATH
454 
455 } BcResultType;
456 
457 /// A union to store data for various result types.
458 typedef union BcResultData {
459 
460 	/// A number. Strings are stored here too; they are numbers with
461 	/// cap == 0 && num == NULL. The string's index into the strings vector is
462 	/// stored in the scale field. But this is only used for strings stored in
463 	/// variables.
464 	BcNum n;
465 
466 	/// A vector.
467 	BcVec v;
468 
469 	/// A variable, array, or array element reference. This could also be a
470 	/// string if a string is not stored in a variable (dc only).
471 	BcLoc loc;
472 
473 } BcResultData;
474 
475 /// A tagged union for results.
476 typedef struct BcResult {
477 
478 	/// The tag. The type of the result.
479 	BcResultType t;
480 
481 	/// The data. The data for the result.
482 	BcResultData d;
483 
484 } BcResult;
485 
486 /// An instruction pointer. This is how bc knows where in the bytecode vector,
487 /// and which function, the current execution is.
488 typedef struct BcInstPtr {
489 
490 	/// The index of the currently executing function in the fns vector.
491 	size_t func;
492 
493 	/// The index into the bytecode vector of the *next* instruction.
494 	size_t idx;
495 
496 	/// The length of the results vector when this function started executing.
497 	/// This is mostly used for bc where functions should not affect the results
498 	/// of their callers.
499 	size_t len;
500 
501 } BcInstPtr;
502 
503 /// Types of identifiers.
504 typedef enum BcType {
505 
506 	/// Variable.
507 	BC_TYPE_VAR,
508 
509 	/// Array.
510 	BC_TYPE_ARRAY,
511 
512 #if BC_ENABLED
513 
514 	/// Array reference.
515 	BC_TYPE_REF,
516 
517 #endif // BC_ENABLED
518 
519 } BcType;
520 
521 #if BC_ENABLED
522 /// An auto variable in bc.
523 typedef struct BcAuto {
524 
525 	/// The index of the variable in the vars or arrs vectors.
526 	size_t idx;
527 
528 	/// The type of the variable.
529 	BcType type;
530 
531 } BcAuto;
532 #endif // BC_ENABLED
533 
534 /// Forward declaration.
535 struct BcProgram;
536 
537 /**
538  * Initializes a function.
539  * @param f     The function to initialize.
540  * @param name  The name of the function. The string is assumed to be owned by
541  *              some other entity.
542  */
543 void bc_func_init(BcFunc *f, const char* name);
544 
545 /**
546  * Inserts an auto into the function.
547  * @param f     The function to insert into.
548  * @param p     The program. This is to search for the variable or array name.
549  * @param name  The name of the auto to insert.
550  * @param type  The type of the auto.
551  * @param line  The line in the source code where the insert happened. This is
552  *              solely for error reporting.
553  */
554 void bc_func_insert(BcFunc *f, struct BcProgram* p, char* name,
555                     BcType type, size_t line);
556 
557 /**
558  * Resets a function in preparation for it to be reused. This can happen in bc
559  * because it is a dynamic language and functions can be redefined.
560  * @param f  The functio to reset.
561  */
562 void bc_func_reset(BcFunc *f);
563 
564 #ifndef NDEBUG
565 /**
566  * Frees a function. This is a destructor. This is only used in debug builds
567  * because all functions are freed at exit. We free them in debug builds to
568  * check for memory leaks.
569  * @param func  The function to free as a void pointer.
570  */
571 void bc_func_free(void *func);
572 #endif // NDEBUG
573 
574 /**
575  * Initializes an array, which is the array type in bc and dc source code. Since
576  * variables and arrays are both arrays (see the development manual,
577  * manuals/development.md#execution, for more information), the @a nums
578  * parameter tells bc whether to initialize an array of numbers or an array of
579  * arrays of numbers. If the latter, it does a recursive call with nums set to
580  * true.
581  * @param a     The array to initialize.
582  * @param nums  True if the array should be for numbers, false if it should be
583  *              for vectors.
584  */
585 void bc_array_init(BcVec *a, bool nums);
586 
587 /**
588  * Copies an array to another array. This is used to do pass arrays to functions
589  * that do not take references to arrays. The arrays are passed entirely by
590  * value, which means that they need to be copied.
591  * @param d  The destination array.
592  * @param s  The source array.
593  */
594 void bc_array_copy(BcVec *d, const BcVec *s);
595 
596 /**
597  * Frees a string stored in a function. This is a destructor.
598  * @param string  The string to free as a void pointer.
599  */
600 void bc_string_free(void *string);
601 
602 /**
603  * Frees a constant stored in a function. This is a destructor.
604  * @param constant  The constant to free as a void pointer.
605  */
606 void bc_const_free(void *constant);
607 
608 /**
609  * Clears a result. It sets the type to BC_RESULT_TEMP and clears the union by
610  * clearing the BcNum in the union. This is to ensure that bc does not use
611  * uninitialized data.
612  * @param r  The result to clear.
613  */
614 void bc_result_clear(BcResult *r);
615 
616 /**
617  * Copies a result into another. This is done for things like duplicating the
618  * top of the results stack or copying the result of an assignment to put back
619  * on the results stack.
620  * @param d    The destination result.
621  * @param src  The source result.
622  */
623 void bc_result_copy(BcResult *d, BcResult *src);
624 
625 /**
626  * Frees a result. This is a destructor.
627  * @param result  The result to free as a void pointer.
628  */
629 void bc_result_free(void *result);
630 
631 /**
632  * Expands an array to @a len. This can happen because in bc, you do not have to
633  * explicitly initialize elements of an array. If you access an element that is
634  * not initialized, the array is expanded to fit it, and all missing elements
635  * are initialized to 0 if they are numbers, or arrays with one element of 0.
636  * This function does that expansion.
637  * @param a    The array to expand.
638  * @param len  The length to expand to.
639  */
640 void bc_array_expand(BcVec *a, size_t len);
641 
642 /**
643  * Compare two BcId's and return the result. Since they are just comparing the
644  * names in the BcId, I return the result from strcmp() exactly. This is used by
645  * maps in their binary search.
646  * @param e1  The first id.
647  * @param e2  The second id.
648  * @return    The result of strcmp() on the BcId's names.
649  */
650 int bc_id_cmp(const BcId *e1, const BcId *e2);
651 
652 #if BC_ENABLED
653 
654 /**
655  * Returns non-zero if the bytecode instruction i is an assignment instruction.
656  * @param i  The instruction to test.
657  * @return   Non-zero if i is an assignment instruction, zero otherwise.
658  */
659 #define BC_INST_IS_ASSIGN(i) \
660 	((i) == BC_INST_ASSIGN || (i) == BC_INST_ASSIGN_NO_VAL)
661 
662 /**
663  * Returns true if the bytecode instruction @a i requires the value to be
664  * returned for use.
665  * @param i  The instruction to test.
666  * @return   True if @a i requires the value to be returned for use, false
667  *           otherwise.
668  */
669 #define BC_INST_USE_VAL(i) ((i) <= BC_INST_ASSIGN)
670 
671 #else // BC_ENABLED
672 
673 /**
674  * Returns non-zero if the bytecode instruction i is an assignment instruction.
675  * @param i  The instruction to test.
676  * @return   Non-zero if i is an assignment instruction, zero otherwise.
677  */
678 #define BC_INST_IS_ASSIGN(i) ((i) == BC_INST_ASSIGN_NO_VAL)
679 
680 /**
681  * Returns true if the bytecode instruction @a i requires the value to be
682  * returned for use.
683  * @param i  The instruction to test.
684  * @return   True if @a i requires the value to be returned for use, false
685  *           otherwise.
686  */
687 #define BC_INST_USE_VAL(i) (false)
688 
689 #endif // BC_ENABLED
690 
691 #if BC_DEBUG_CODE
692 /// Reference to string names for all of the instructions. For debugging.
693 extern const char* bc_inst_names[];
694 #endif // BC_DEBUG_CODE
695 
696 /// References to the names of the main and read functions.
697 extern const char bc_func_main[];
698 extern const char bc_func_read[];
699 
700 #endif // BC_LANG_H
701