]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/bc/include/lang.h
contrib/bc: merge version 5.1.0 from vendor branch
[FreeBSD/FreeBSD.git] / contrib / bc / include / lang.h
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