2 # PSPP - a program for statistical analysis.
3 # Copyright (C) 2017, 2021 Free Software Foundation, Inc.
5 # This program is free software: you can redistribute it and/or modify
6 # it under the terms of the GNU General Public License as published by
7 # the Free Software Foundation, either version 3 of the License, or
8 # (at your option) any later version.
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
15 # You should have received a copy of the GNU General Public License
16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
26 Defines all our types.
28 Initializes 'types' global.
34 # Common user-visible types used throughout evaluation trees.
35 init_type(Type.new_any('number', 'double', 'number', 'n', 'number', 'ns', 'SYSMIS'))
36 init_type(Type.new_any('string', 'struct substring', 'string', 's', 'string', 'ss', 'empty_string'))
37 init_type(Type.new_any('boolean', 'double', 'number', 'n', 'boolean', 'ns', 'SYSMIS'))
40 init_type(Type.new_atom('format'))
41 init_type(Type.new_leaf('ni_format', 'const struct fmt_spec *', 'format', 'f', 'num_input_format'))
42 init_type(Type.new_leaf('no_format', 'const struct fmt_spec *', 'format', 'f', 'num_output_format'))
45 init_type(Type.new_leaf('integer', 'int', 'integer', 'n', 'integer'))
46 init_type(Type.new_leaf('pos_int', 'int', 'integer', 'n', 'positive_integer_constant'))
49 init_type(Type.new_atom('variable'))
50 init_type(Type.new_leaf('num_var', 'const struct variable *', 'variable', 'Vn', 'num_variable'))
51 init_type(Type.new_leaf('str_var', 'const struct variable *', 'variable', 'Vs', 'string_variable'))
52 init_type(Type.new_leaf('var', 'const struct variable *', 'variable', 'V', 'variable'))
55 init_type(Type.new_leaf('vector', 'const struct vector *', 'vector', 'v', 'vector'))
58 init_type(Type.new_fixed('expression', 'struct expression *', 'e'))
59 init_type(Type.new_fixed('case', 'const struct ccase *', 'c'))
60 init_type(Type.new_fixed('case_idx', 'size_t', 'case_idx'))
61 init_type(Type.new_fixed('dataset', 'struct dataset *', 'ds'))
63 # One of these is emitted at the end of each expression as a sentinel
64 # that tells expr_evaluate() to return the value on the stack.
65 init_type(Type.new_atom('return_number'))
66 init_type(Type.new_atom('return_string'))
68 # Used only for debugging purposes.
69 init_type(Type.new_atom('operation'))
72 init_type has 2 required arguments:
76 'name' is the type's name in operations.def.
78 `OP_$name' is the terminal's type in operations.h.
80 `expr_allocate_$name()' allocates a node of the given type.
82 ROLE: How the type may be used:
84 "any": Usable as operands and function arguments, and
85 function and operator results.
87 "leaf": Usable as operands and function arguments, but not
88 results. (Thus, they appear only in leaf nodes in the parse
91 "fixed": Not allowed either as an operand or argument
92 type or a result type. Used only as auxiliary data.
94 "atom": Not allowed anywhere; just adds the name to
97 All types except those with "atom" as their role also require:
99 C_TYPE: The C type that represents this abstract type.
101 Types with "any" or "leaf" role require:
105 `$atom' is the `struct operation_data' member name.
107 get_$atom_name() obtains the corresponding data from a
110 MANGLE: Short string for name mangling. Use identical strings
111 if two types should not be overloaded.
113 HUMAN_NAME: Name for a type when we describe it to the user.
115 Types with role "any" require:
117 STACK: Name of the local variable in expr_evaluate(), used for
118 maintaining the stack for this type.
120 MISSING_VALUE: Expression used for the missing value of this
123 Types with role "fixed" require:
125 FIXED_VALUE: Expression used for the value of this type.
128 def __init__(self, name, role, human_name, c_type=None):
131 self.human_name = human_name
133 if c_type.endswith('*'):
136 self.c_type = c_type + ' '
139 return Type(name, 'atom', name)
141 def new_any(name, c_type, atom, mangle, human_name, stack, missing_value):
142 new = Type(name, 'any', human_name, c_type)
146 new.missing_value = missing_value
149 def new_leaf(name, c_type, atom, mangle, human_name):
150 new = Type(name, 'leaf', human_name, c_type)
155 def new_fixed(name, c_type, fixed_value):
156 new = Type(name, 'fixed', name, c_type)
157 new.fixed_value = fixed_value
161 """If the current token is an identifier that names a type, returns
162 the type and skips to the next token. Otherwise, returns
166 for type_ in types.values():
167 if type_.name == token:
172 def init_type(type_):
174 types[type_.name] = type_
185 optimizable, unimplemented, extension, perm_only, absorb_miss, no_abbrev):
187 self.category = category
188 self.returns = returns
191 self.expression = expression
193 self.min_valid = min_valid
194 self.optimizable = optimizable
195 self.unimplemented = unimplemented
196 self.extension = extension
197 self.perm_only = perm_only
198 self.absorb_miss = absorb_miss
199 self.no_abbrev = no_abbrev
201 self.opname = ('OP_%s' % name).replace('.', '_')
202 if category == 'function':
203 self.mangle = ''.join([a.type_.mangle for a in args])
204 self.opname += '_%s' % self.mangle
207 """If this operation has an array argument, returns it. Otherwise,
210 if self.args and self.args[-1].idx is not None:
215 def sysmis_decl(self, min_valid_src):
216 """Returns a declaration for a boolean variable called `force_sysmis',
217 which will be true when this operation should be
218 system-missing. Returns None if there are no such
221 If this operation has a minimum number of valid arguments,
222 'min_valid_src' should be an an expression that evaluates to
223 the minimum number of valid arguments for this operation.
227 if not self.absorb_miss:
228 for arg in self.args:
229 arg_name = 'arg_%s' % arg.name
231 if arg.type_.name in ['number', 'boolean']:
232 sysmis_cond += ["!is_valid (%s)" % arg_name]
233 elif arg.type_.name == 'number':
235 n = 'arg_%s' % arg.idx
236 sysmis_cond += ['count_valid (%s, %s) < %s' % (a, n, n)]
237 elif self.min_valid > 0:
240 a = 'arg_%s' % arg.name
241 n = 'arg_%s' % arg.idx
242 sysmis_cond += ["count_valid (%s, %s) < %s" % (a, n, min_valid_src)]
243 for arg in self.args:
244 if arg.condition is not None:
245 sysmis_cond += ['!(%s)' % arg.condition]
247 return 'bool force_sysmis = %s' % ' || '.join(sysmis_cond)
251 """Parses the entire input.
253 Initializes ops, funcs, opers."""
272 while toktype != 'eof':
274 unimplemented = False
280 if match('extension'):
282 elif match('no_opt'):
284 elif match('absorb_miss'):
286 elif match('perm_only'):
288 elif match('no_abbrev'):
293 return_type = Type.parse()
294 if return_type is None:
295 return_type = types['number']
296 if return_type.name not in ['number', 'string', 'boolean']:
297 sys.stderr.write('%s is not a valid return type\n' % return_type.name)
301 if category not in ['operator', 'function']:
302 sys.stderr.write("'operator' or 'function' expected at '%s'" % token)
307 if category == 'function' and '_' in name:
308 sys.stderr.write("function name '%s' may not contain underscore\n" % name)
310 elif category == 'operator' and '.' in name:
311 sys.stderr.write("operator name '%s' may not contain period\n" % name)
314 m = re.match(r'(.*)\.(\d+)$', name)
316 prefix, suffix = m.groups()
318 min_valid = int(suffix)
325 while not match(')'):
328 if arg.idx is not None:
331 sys.stderr.write('array must be last argument\n')
338 if arg.condition is not None:
339 any_arg = '|'.join([a.name for a in args])
340 arg.condition = re.sub(r'\b(%s)\b' % any_arg, r'arg_\1', arg.condition)
343 while toktype == 'id':
346 sys.stderr.write('parse error\n')
348 if type_.role not in ['leaf', 'fixed']:
349 sys.stderr.write("'%s' is not allowed as auxiliary data\n" % type_.name)
351 aux_name = force('id')
352 aux += [{'TYPE': type_, 'NAME': aux_name}]
356 if name.startswith('RV.'):
357 sys.stderr.write("random variate functions must be marked 'no_opt'\n")
359 for key in ['CASE', 'CASE_IDX']:
361 sys.stderr.write("operators with %s aux data must be marked 'no_opt'\n" % key)
364 if return_type.name == 'string' and not absorb_miss:
366 if arg.type_.name in ['number', 'boolean']:
367 sys.stderr.write("'%s' returns string and has double or bool "
368 "argument, but is not marked ABSORB_MISS\n"
371 if arg.condition is not None:
372 sys.stderr.write("'%s' returns string but has argument with condition\n")
375 if toktype == 'block':
376 block = force('block')
378 elif toktype == 'expression':
379 if token == 'unimplemented':
386 sys.stderr.write("block or expression expected\n")
389 op = Op(name, category,
390 return_type, args, aux,
393 optimizable, unimplemented, extension, perm_only, absorb_miss,
396 sys.stderr.write("duplicate operation name %s\n" % op.opname)
402 sys.stderr.write("can't have minimum valid count without array arg\n")
404 if aa.type_.name != 'number':
405 sys.stderr.write('minimum valid count allowed only with double array\n')
408 sys.stderr.write("can't have minimu valid count if array has multiplication factor\n")
412 if category == 'function':
419 funcs = sorted(funcs, key=lambda name: (ops[name].name, ops[name].opname))
420 opers = sorted(opers, key=lambda name: ops[name].name)
421 order = funcs + opers
424 """Reads the next token into 'token' and 'toktype'."""
434 m = re.match(r'([a-zA-Z_][a-zA-Z_.0-9]*)(.*)$', line)
436 token, line = m.groups()
440 m = re.match(r'([0-9]+)(.*)$', line)
442 token, line = m.groups()
447 m = re.match(r'([][(),*;.])(.*)$', line)
449 token, line = m.groups()
453 m = re.match(r'=\s*(.*)$', line)
455 toktype = 'expression'
457 token = accumulate_balanced(';')
460 m = re.match(r'{(.*)$', line)
464 token = accumulate_balanced('}')
465 token = token.rstrip('\n')
468 sys.stderr.write("bad character '%s' in input\n" % line[0])
472 """Skip whitespace."""
475 sys.stderr.write("unexpected end of file\n")
490 def accumulate_balanced(end, swallow_end=True):
491 """Accumulates input until a character in 'end' is encountered,
492 except that balanced pairs of (), [], or {} cause 'end' to be
493 ignored. Returns the input read.
499 for idx, c in enumerate(line):
500 if c in end and nest == 0:
512 sys.stderr.write('unbalanced parentheses\n')
519 """Reads the next line from INPUT into 'line'."""
522 line = in_file.readline()
527 line = line.rstrip('\r\n')
528 comment_ofs = line.find('//')
530 line = line[:comment_ofs]
533 """Makes sure that 'toktype' equals 'type', reads the next token, and
534 returns the previous 'token'.
538 sys.stderr.write("parse error at `%s' expecting %s\n" % (token, type_))
545 """If 'token' equals 'tok', reads the next token and returns true.
546 Otherwise, returns false."""
553 def force_match(tok):
554 """If 'token' equals 'tok', reads the next token. Otherwise, flags an
558 sys.stderr.write("parse error at `%s' expecting `%s'\n" % (token, tok))
562 def __init__(self, name, type_, idx, times, condition):
567 self.condition = condition
570 """Parses and returns a function argument."""
573 type_ = types['number']
576 sys.stderr.write("argument name expected at `%s'\n" % token)
589 if type_.name not in ('number', 'string'):
590 sys.stderr.write('only double and string arrays supported\n')
596 sys.stderr.write('multiplication factor must be two\n')
601 condition = name + ' ' + accumulate_balanced(',)', swallow_end=False)
604 return Arg(name, type_, idx, times, condition)
607 """Prints the output file header."""
610 Generated from %s by generate.py.
613 """ % (out_file_name, in_file_name))
616 """Prints the output file trailer."""
627 def generate_evaluate_h():
628 out_file.write("#include \"helpers.h\"\n\n")
638 args += [arg.type_.c_type + arg.name]
640 args += [arg.type_.c_type + arg.name + '[]']
641 args += ['size_t %s' % arg.idx]
643 args += [aux['TYPE'].c_type + aux['NAME']]
648 statements = op.block + '\n'
650 statements = " return %s;\n" % op.expression
652 out_file.write("static inline %s\n" % op.returns.c_type)
653 out_file.write("eval_%s (%s)\n" % (opname, ', '.join(args)))
654 out_file.write("{\n")
655 out_file.write(statements)
656 out_file.write("}\n\n")
658 def generate_evaluate_inc():
662 out_file.write("case %s:\n" % opname)
663 out_file.write(" NOT_REACHED ();\n\n")
670 c_type = type_.c_type
671 args += ['arg_%s' % arg.name]
673 decl = '%sarg_%s' % (c_type, arg.name)
674 if type_.role == 'any':
675 decls = ['%s = *--%s' % (decl, type_.stack)] + decls
676 elif type_.role == 'leaf':
677 decls += ['%s = op++->%s' % (decl, type_.atom)]
682 decls = ['%s*arg_%s = %s -= arg_%s' % (c_type, arg.name, type_.stack, idx)] + decls
683 decls = ['size_t arg_%s = op++->integer' % idx] + decls
687 idx += ' / %s' % arg.times
692 if type_.role == 'leaf':
693 decls += ['%saux_%s = op++->%s' % (type_.c_type, name, type_.atom)]
694 args += ['aux_%s' % name]
695 elif type_.role == 'fixed':
696 args += [type_.fixed_value]
698 sysmis_cond = op.sysmis_decl('op++->integer')
699 if sysmis_cond is not None:
700 decls += [sysmis_cond]
702 result = 'eval_%s (%s)' % (op.opname, ', '.join(args))
704 stack = op.returns.stack
706 out_file.write("case %s:\n" % opname)
708 out_file.write(" {\n")
710 out_file.write(" %s;\n" % decl)
711 if sysmis_cond is not None:
712 miss_ret = op.returns.missing_value
713 out_file.write(" *%s++ = force_sysmis ? %s : %s;\n" % (stack, miss_ret, result))
715 out_file.write(" *%s++ = %s;\n" % (stack, result))
716 out_file.write(" }\n")
718 out_file.write(" *%s++ = %s;\n" % (stack, result))
719 out_file.write(" break;\n\n")
721 def generate_operations_h():
722 out_file.write("#include <stdlib.h>\n")
723 out_file.write("#include <stdbool.h>\n\n")
725 out_file.write("typedef enum")
726 out_file.write(" {\n")
728 for type_ in types.values():
729 if type_.role != 'fixed':
730 atoms += ["OP_%s" % type_.name]
732 print_operations('atom', 1, atoms)
733 print_operations('function', "OP_atom_last + 1", funcs)
734 print_operations('operator', "OP_function_last + 1", opers)
735 print_range("OP_composite", "OP_function_first", "OP_operator_last")
736 out_file.write(",\n\n")
737 print_range("OP", "OP_atom_first", "OP_composite_last")
738 out_file.write("\n }\n")
739 out_file.write("operation_type, atom_type;\n")
741 print_predicate('is_operation', 'OP')
742 for key in ('atom', 'composite', 'function', 'operator'):
743 print_predicate("is_%s" % key, "OP_%s" % key)
745 def print_operations(type_, first, names):
746 out_file.write(" /* %s types. */\n" % type_.title())
747 out_file.write(" %s = %s,\n" % (names[0], first))
748 for name in names[1:]:
749 out_file.write(" %s,\n" % name)
750 print_range("OP_%s" % type_, names[0], names[len(names) - 1])
751 out_file.write(",\n\n")
753 def print_range(prefix, first, last):
754 out_file.write(" %s_first = %s,\n" % (prefix, first))
755 out_file.write(" %s_last = %s,\n" % (prefix, last))
756 out_file.write(" n_%s = %s_last - %s_first + 1" % (prefix, prefix, prefix))
758 def print_predicate(function, category):
761 out_file.write("\nstatic inline bool\n")
762 out_file.write("%s (operation_type op)\n" % function)
763 out_file.write("{\n")
764 if function != 'is_operation':
765 out_file.write(" assert (is_operation (op));\n")
766 out_file.write(" return op >= %s_first && op <= %s_last;\n" % (category, category))
767 out_file.write("}\n")
769 def generate_optimize_inc():
773 if not op.optimizable or op.unimplemented:
774 out_file.write("case %s:\n" % opname)
775 out_file.write(" NOT_REACHED ();\n\n")
783 c_type = type_.c_type
785 func = "get_%s_arg" % type_.atom
786 decls += ["%sarg_%s = %s (node, %s)" % (c_type, name, func, arg_idx)]
788 decl = "size_t arg_%s = node->n_args" % arg.idx
790 decl += " - %s" % arg_idx
793 decls += ["%s*arg_%s = get_%s_args (node, %s, arg_%s, e)" % (c_type, name, type_.atom, arg_idx, arg.idx)]
796 sysmis_cond = op.sysmis_decl("node->min_valid")
797 if sysmis_cond is not None:
798 decls += [sysmis_cond]
802 args += ["arg_%s" % arg.name]
803 if arg.idx is not None:
804 idx = 'arg_%s' % arg.idx
806 idx += " / %s" % arg.times
811 if type_.role == 'leaf':
812 func = "get_%s_arg" % type_.atom
813 args += "%s (node, %s)" % (func, arg_idx)
815 elif type_.role == 'fixed':
816 args += [type_.fixed_value]
820 result = "eval_%s (%s)" % (op.opname, ', '.join(args))
821 if decls and sysmis_cond is not None:
822 miss_ret = op.returns.missing_value
823 decls += ['%sresult = force_sysmis ? %s : %s' % (op.returns.c_type, miss_ret, result)]
826 out_file.write("case %s:\n" % opname)
827 alloc_func = "expr_allocate_%s" % op.returns.name
829 out_file.write(" {\n")
831 out_file.write(" %s;\n" % decl)
832 out_file.write(" return %s (e, %s);\n" % (alloc_func, result))
833 out_file.write(" }\n")
835 out_file.write(" return %s (e, %s);\n" % (alloc_func, result))
838 def generate_parse_inc():
839 members = ['""', '""', '0', '0', '0', "{}", '0', '0']
840 out_file.write("{%s},\n" % ', '.join(members))
842 for type_ in types.values():
843 if type_.role != 'fixed':
844 members = ('"%s"' % type_.name, '"%s"' % type_.human_name, '0', "OP_%s" % type_.name, '0', "{}", '0', '0')
845 out_file.write("{%s},\n" % ', '.join(members))
851 members += ['"%s"' % op.name]
853 if op.category == 'function':
858 args += [arg.type_.human_name]
860 array = op.array_arg()
861 if array is not None:
862 if op.min_valid == 0:
864 for i in range(array.times):
865 array_args += [array.type_.human_name]
867 opt_args = array_args
869 for i in range(op.min_valid):
870 args += [array.type_.human_name]
871 opt_args += [array.type_.human_name]
872 human = "%s(%s" % (op.name, ', '.join(args))
874 human += '[, %s]...' % ', '.join(opt_args)
876 members += ['"%s"' % human]
882 flags += ['OPF_ABSORB_MISS']
884 flags += ['OPF_ARRAY_OPERAND']
886 flags += ['OPF_MIN_VALID']
887 if not op.optimizable:
888 flags += ['OPF_NONOPTIMIZABLE']
890 flags += ['OPF_EXTENSION']
892 flags += ['OPF_UNIMPLEMENTED']
894 flags += ['OPF_PERM_ONLY']
896 flags += ['OPF_NO_ABBREV']
897 members += [' | '.join(flags) if flags else '0']
899 members += ['OP_%s' % op.returns.name]
901 members += ['%s' % len(op.args)]
903 arg_types = ["OP_%s" % arg.type_.name for arg in op.args]
904 members += ['{%s}' % ', '.join(arg_types)]
906 members += ['%s' % op.min_valid]
908 members += ['%s' % (op.array_arg().times if op.array_arg() else 0)]
910 out_file.write('{%s},\n' % ', '.join(members))
916 %(argv0)s, for generating expression parsers and evaluators from definitions
917 usage: generate.pl -o OUTPUT [-i INPUT] [-h]
918 -i INPUT input file containing definitions (default: operations.def)
919 -o OUTPUT output file
920 -h display this help message
921 """ % {'argv0': argv0})
924 if __name__ == "__main__":
926 options, args = getopt.gnu_getopt(sys.argv[1:], 'hi:o:',
930 except getopt.GetoptError as geo:
931 sys.stderr.write("%s: %s\n" % (argv0, geo.msg))
934 in_file_name = 'operations.def'
936 for key, value in options:
937 if key in ['-h', '--help']:
939 elif key in ['-i', '--input']:
941 elif key in ['-o', '--output']:
942 out_file_name = value
946 if out_file_name is None:
947 sys.stderr.write("%(argv0)s: output file must be specified "
948 "(use --help for help)\n" % {'argv0': argv0})
951 in_file = open(in_file_name, 'r')
952 out_file = open(out_file_name, 'w')
958 if out_file_name.endswith('evaluate.h'):
959 generate_evaluate_h()
960 elif out_file_name.endswith('evaluate.inc'):
961 generate_evaluate_inc()
962 elif out_file_name.endswith('operations.h'):
963 generate_operations_h()
964 elif out_file_name.endswith('optimize.inc'):
965 generate_optimize_inc()
966 elif out_file_name.endswith('parse.inc'):
969 sys.stderr.write("%(argv0)s: unknown output type\n")