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
160 def init_type(type_):
162 types[type_.name] = type_
173 optimizable, unimplemented, extension, perm_only, absorb_miss, no_abbrev):
175 self.category = category
176 self.returns = returns
179 self.expression = expression
181 self.min_valid = min_valid
182 self.optimizable = optimizable
183 self.unimplemented = unimplemented
184 self.extension = extension
185 self.perm_only = perm_only
186 self.absorb_miss = absorb_miss
187 self.no_abbrev = no_abbrev
189 self.opname = ('OP_%s' % name).replace('.', '_')
190 if category == 'function':
191 self.mangle = ''.join([a.type_.mangle for a in args])
192 self.opname += '_%s' % self.mangle
195 """Parses the entire input.
197 Initializes ops, funcs, opers."""
216 while toktype != 'eof':
218 unimplemented = False
224 if match('extension'):
226 elif match('no_opt'):
228 elif match('absorb_miss'):
230 elif match('perm_only'):
232 elif match('no_abbrev'):
237 return_type = parse_type()
238 if return_type is None:
239 return_type = types['number']
240 if return_type.name not in ['number', 'string', 'boolean']:
241 sys.stderr.write('%s is not a valid return type\n' % return_type.name)
245 if category not in ['operator', 'function']:
246 sys.stderr.write("'operator' or 'function' expected at '%s'" % token)
251 if category == 'function' and '_' in name:
252 sys.stderr.write("function name '%s' may not contain underscore\n" % name)
254 elif category == 'operator' and '.' in name:
255 sys.stderr.write("operator name '%s' may not contain period\n" % name)
258 m = re.match(r'(.*)\.(\d+)$', name)
260 prefix, suffix = m.groups()
262 min_valid = int(suffix)
269 while not match(')'):
272 if arg.idx is not None:
275 sys.stderr.write('array must be last argument\n')
282 if arg.condition is not None:
283 any_arg = '|'.join([a.name for a in args])
284 arg.condition = re.sub(r'\b(%s)\b' % any_arg, r'arg_\1', arg.condition)
287 while toktype == 'id':
290 sys.stderr.write('parse error\n')
292 if type_.role not in ['leaf', 'fixed']:
293 sys.stderr.write("'%s' is not allowed as auxiliary data\n" % type_.name)
295 aux_name = force('id')
296 aux += [{'TYPE': type_, 'NAME': aux_name}]
300 if name.startswith('RV.'):
301 sys.stderr.write("random variate functions must be marked 'no_opt'\n")
303 for key in ['CASE', 'CASE_IDX']:
305 sys.stderr.write("operators with %s aux data must be marked 'no_opt'\n" % key)
308 if return_type.name == 'string' and not absorb_miss:
310 if arg.type_.name in ['number', 'boolean']:
311 sys.stderr.write("'%s' returns string and has double or bool "
312 "argument, but is not marked ABSORB_MISS\n"
315 if arg.condition is not None:
316 sys.stderr.write("'%s' returns string but has argument with condition\n")
319 if toktype == 'block':
320 block = force('block')
322 elif toktype == 'expression':
323 if token == 'unimplemented':
330 sys.stderr.write("block or expression expected\n")
333 op = Op(name, category,
334 return_type, args, aux,
337 optimizable, unimplemented, extension, perm_only, absorb_miss,
340 sys.stderr.write("duplicate operation name %s\n" % op.opname)
346 sys.stderr.write("can't have minimum valid count without array arg\n")
348 if aa.type_.name != 'number':
349 sys.stderr.write('minimum valid count allowed only with double array\n')
352 sys.stderr.write("can't have minimu valid count if array has multiplication factor\n")
356 if category == 'function':
363 funcs = sorted(funcs, key=lambda name: (ops[name].name, ops[name].opname))
364 opers = sorted(opers, key=lambda name: ops[name].name)
365 order = funcs + opers
368 """Reads the next token into 'token' and 'toktype'."""
378 m = re.match(r'([a-zA-Z_][a-zA-Z_.0-9]*)(.*)$', line)
380 token, line = m.groups()
384 m = re.match(r'([0-9]+)(.*)$', line)
386 token, line = m.groups()
391 m = re.match(r'([][(),*;.])(.*)$', line)
393 token, line = m.groups()
397 m = re.match(r'=\s*(.*)$', line)
399 toktype = 'expression'
401 token = accumulate_balanced(';')
404 m = re.match(r'{(.*)$', line)
408 token = accumulate_balanced('}')
409 token = token.rstrip('\n')
412 sys.stderr.write("bad character '%s' in input\n" % line[0])
416 """Skip whitespace."""
419 sys.stderr.write("unexpected end of file\n")
434 def accumulate_balanced(end, swallow_end=True):
435 """Accumulates input until a character in 'end' is encountered,
436 except that balanced pairs of (), [], or {} cause 'end' to be
437 ignored. Returns the input read.
443 for idx, c in enumerate(line):
444 if c in end and nest == 0:
456 sys.stderr.write('unbalanced parentheses\n')
463 """Reads the next line from INPUT into 'line'."""
466 line = in_file.readline()
471 line = line.rstrip('\r\n')
472 comment_ofs = line.find('//')
474 line = line[:comment_ofs]
477 """If the current token is an identifier that names a type, returns
478 the type and skips to the next token. Otherwise, returns
482 for type_ in types.values():
483 if type_.name == token:
489 """Makes sure that 'toktype' equals 'type', reads the next token, and
490 returns the previous 'token'.
494 sys.stderr.write("parse error at `%s' expecting %s\n" % (token, type_))
501 """If 'token' equals 'tok', reads the next token and returns true.
502 Otherwise, returns false."""
509 def force_match(tok):
510 """If 'token' equals 'tok', reads the next token. Otherwise, flags an
514 sys.stderr.write("parse error at `%s' expecting `%s'\n" % (token, tok))
518 def __init__(self, name, type_, idx, times, condition):
523 self.condition = condition
526 """Parses and returns a function argument."""
529 type_ = types['number']
532 sys.stderr.write("argument name expected at `%s'\n" % token)
545 if type_.name not in ('number', 'string'):
546 sys.stderr.write('only double and string arrays supported\n')
552 sys.stderr.write('multiplication factor must be two\n')
557 condition = name + ' ' + accumulate_balanced(',)', swallow_end=False)
560 return Arg(name, type_, idx, times, condition)
563 """Prints the output file header."""
566 Generated from %s by generate.py.
569 """ % (out_file_name, in_file_name))
572 """Prints the output file trailer."""
583 def generate_evaluate_h():
584 out_file.write("#include \"helpers.h\"\n\n")
594 args += [arg.type_.c_type + arg.name]
596 args += [arg.type_.c_type + arg.name + '[]']
597 args += ['size_t %s' % arg.idx]
599 args += [aux['TYPE'].c_type + aux['NAME']]
604 statements = op.block + '\n'
606 statements = " return %s;\n" % op.expression
608 out_file.write("static inline %s\n" % op.returns.c_type)
609 out_file.write("eval_%s (%s)\n" % (opname, ', '.join(args)))
610 out_file.write("{\n")
611 out_file.write(statements)
612 out_file.write("}\n\n")
614 def generate_evaluate_inc():
618 out_file.write("case %s:\n" % opname)
619 out_file.write(" NOT_REACHED ();\n\n")
626 c_type = type_.c_type
627 args += ['arg_%s' % arg.name]
629 decl = '%sarg_%s' % (c_type, arg.name)
630 if type_.role == 'any':
631 decls = ['%s = *--%s' % (decl, type_.stack)] + decls
632 elif type_.role == 'leaf':
633 decls += ['%s = op++->%s' % (decl, type_.atom)]
638 decls = ['%s*arg_%s = %s -= arg_%s' % (c_type, arg.name, type_.stack, idx)] + decls
639 decls = ['size_t arg_%s = op++->integer' % idx] + decls
643 idx += ' / %s' % arg.times
648 if type_.role == 'leaf':
649 decls += ['%saux_%s = op++->%s' % (type_.c_type, name, type_.atom)]
650 args += ['aux_%s' % name]
651 elif type_.role == 'fixed':
652 args += [type_.fixed_value]
654 sysmis_cond = make_sysmis_decl(op, 'op++->integer')
655 if sysmis_cond is not None:
656 decls += [sysmis_cond]
658 result = 'eval_%s (%s)' % (op.opname, ', '.join(args))
660 stack = op.returns.stack
662 out_file.write("case %s:\n" % opname)
664 out_file.write(" {\n")
666 out_file.write(" %s;\n" % decl)
667 if sysmis_cond is not None:
668 miss_ret = op.returns.missing_value
669 out_file.write(" *%s++ = force_sysmis ? %s : %s;\n" % (stack, miss_ret, result))
671 out_file.write(" *%s++ = %s;\n" % (stack, result))
672 out_file.write(" }\n")
674 out_file.write(" *%s++ = %s;\n" % (stack, result))
675 out_file.write(" break;\n\n")
677 def generate_operations_h():
678 out_file.write("#include <stdlib.h>\n")
679 out_file.write("#include <stdbool.h>\n\n")
681 out_file.write("typedef enum")
682 out_file.write(" {\n")
684 for type_ in types.values():
685 if type_.role != 'fixed':
686 atoms += ["OP_%s" % type_.name]
688 print_operations('atom', 1, atoms)
689 print_operations('function', "OP_atom_last + 1", funcs)
690 print_operations('operator', "OP_function_last + 1", opers)
691 print_range("OP_composite", "OP_function_first", "OP_operator_last")
692 out_file.write(",\n\n")
693 print_range("OP", "OP_atom_first", "OP_composite_last")
694 out_file.write("\n }\n")
695 out_file.write("operation_type, atom_type;\n")
697 print_predicate('is_operation', 'OP')
698 for key in ('atom', 'composite', 'function', 'operator'):
699 print_predicate("is_%s" % key, "OP_%s" % key)
701 def print_operations(type_, first, names):
702 out_file.write(" /* %s types. */\n" % type_.title())
703 out_file.write(" %s = %s,\n" % (names[0], first))
704 for name in names[1:]:
705 out_file.write(" %s,\n" % name)
706 print_range("OP_%s" % type_, names[0], names[len(names) - 1])
707 out_file.write(",\n\n")
709 def print_range(prefix, first, last):
710 out_file.write(" %s_first = %s,\n" % (prefix, first))
711 out_file.write(" %s_last = %s,\n" % (prefix, last))
712 out_file.write(" n_%s = %s_last - %s_first + 1" % (prefix, prefix, prefix))
714 def print_predicate(function, category):
717 out_file.write("\nstatic inline bool\n")
718 out_file.write("%s (operation_type op)\n" % function)
719 out_file.write("{\n")
720 if function != 'is_operation':
721 out_file.write(" assert (is_operation (op));\n")
722 out_file.write(" return op >= %s_first && op <= %s_last;\n" % (category, category))
723 out_file.write("}\n")
725 def generate_optimize_inc():
729 if not op.optimizable or op.unimplemented:
730 out_file.write("case %s:\n" % opname)
731 out_file.write(" NOT_REACHED ();\n\n")
739 c_type = type_.c_type
741 func = "get_%s_arg" % type_.atom
742 decls += ["%sarg_%s = %s (node, %s)" % (c_type, name, func, arg_idx)]
744 decl = "size_t arg_%s = node->n_args" % arg.idx
746 decl += " - %s" % arg_idx
749 decls += ["%s*arg_%s = get_%s_args (node, %s, arg_%s, e)" % (c_type, name, type_.atom, arg_idx, arg.idx)]
752 sysmis_cond = make_sysmis_decl (op, "node->min_valid")
753 if sysmis_cond is not None:
754 decls += [sysmis_cond]
758 args += ["arg_%s" % arg.name]
759 if arg.idx is not None:
760 idx = 'arg_%s' % arg.idx
762 idx += " / %s" % arg.times
767 if type_.role == 'leaf':
768 func = "get_%s_arg" % type_.atom
769 args += "%s (node, %s)" % (func, arg_idx)
771 elif type_.role == 'fixed':
772 args += [type_.fixed_value]
776 result = "eval_%s (%s)" % (op.opname, ', '.join(args))
777 if decls and sysmis_cond is not None:
778 miss_ret = op.returns.missing_value
779 decls += ['%sresult = force_sysmis ? %s : %s' % (op.returns.c_type, miss_ret, result)]
782 out_file.write("case %s:\n" % opname)
783 alloc_func = "expr_allocate_%s" % op.returns.name
785 out_file.write(" {\n")
787 out_file.write(" %s;\n" % decl)
788 out_file.write(" return %s (e, %s);\n" % (alloc_func, result))
789 out_file.write(" }\n")
791 out_file.write(" return %s (e, %s);\n" % (alloc_func, result))
794 def generate_parse_inc():
795 members = ['""', '""', '0', '0', '0', "{}", '0', '0']
796 out_file.write("{%s},\n" % ', '.join(members))
798 for type_ in types.values():
799 if type_.role != 'fixed':
800 members = ('"%s"' % type_.name, '"%s"' % type_.human_name, '0', "OP_%s" % type_.name, '0', "{}", '0', '0')
801 out_file.write("{%s},\n" % ', '.join(members))
807 members += ['"%s"' % op.name]
809 if op.category == 'function':
814 args += [arg.type_.human_name]
816 array = array_arg(op)
817 if array is not None:
818 if op.min_valid == 0:
820 for i in range(array.times):
821 array_args += [array.type_.human_name]
823 opt_args = array_args
825 for i in range(op.min_valid):
826 args += [array.type_.human_name]
827 opt_args += [array.type_.human_name]
828 human = "%s(%s" % (op.name, ', '.join(args))
830 human += '[, %s]...' % ', '.join(opt_args)
832 members += ['"%s"' % human]
838 flags += ['OPF_ABSORB_MISS']
840 flags += ['OPF_ARRAY_OPERAND']
842 flags += ['OPF_MIN_VALID']
843 if not op.optimizable:
844 flags += ['OPF_NONOPTIMIZABLE']
846 flags += ['OPF_EXTENSION']
848 flags += ['OPF_UNIMPLEMENTED']
850 flags += ['OPF_PERM_ONLY']
852 flags += ['OPF_NO_ABBREV']
853 members += [' | '.join(flags) if flags else '0']
855 members += ['OP_%s' % op.returns.name]
857 members += ['%s' % len(op.args)]
859 arg_types = ["OP_%s" % arg.type_.name for arg in op.args]
860 members += ['{%s}' % ', '.join(arg_types)]
862 members += ['%s' % op.min_valid]
864 members += ['%s' % (array_arg(op).times if array_arg(op) else 0)]
866 out_file.write('{%s},\n' % ', '.join(members))
870 def make_sysmis_decl(op, min_valid_src):
871 """Returns a declaration for a boolean variable called `force_sysmis',
872 which will be true when operation 'op' should be system-missing.
873 Returns None if there are no such circumstances.
875 If 'op' has a minimum number of valid arguments, 'min_valid_src'
876 should be an an expression that evaluates to the minimum number of
877 valid arguments for 'op'.
881 if not op.absorb_miss:
883 arg_name = 'arg_%s' % arg.name
885 if arg.type_.name in ['number', 'boolean']:
886 sysmis_cond += ["!is_valid (%s)" % arg_name]
887 elif arg.type_.name == 'number':
889 n = 'arg_%s' % arg.idx
890 sysmis_cond += ['count_valid (%s, %s) < %s' % (a, n, n)]
891 elif op.min_valid > 0:
894 a = 'arg_%s' % arg.name
895 n = 'arg_%s' % arg.idx
896 sysmis_cond += ["count_valid (%s, %s) < %s" % (a, n, min_valid_src)]
898 if arg.condition is not None:
899 sysmis_cond += ['!(%s)' % arg.condition]
901 return 'bool force_sysmis = %s' % ' || '.join(sysmis_cond)
905 """If 'op' has an array argument, returns it. Otherwise, returns
911 if last_arg.idx is not None:
917 %(argv0)s, for generating expression parsers and evaluators from definitions
918 usage: generate.pl -o OUTPUT [-i INPUT] [-h]
919 -i INPUT input file containing definitions (default: operations.def)
920 -o OUTPUT output file
921 -h display this help message
922 """ % {'argv0': argv0})
925 if __name__ == "__main__":
927 options, args = getopt.gnu_getopt(sys.argv[1:], 'hi:o:',
931 except getopt.GetoptError as geo:
932 sys.stderr.write("%s: %s\n" % (argv0, geo.msg))
935 in_file_name = 'operations.def'
937 for key, value in options:
938 if key in ['-h', '--help']:
940 elif key in ['-i', '--input']:
942 elif key in ['-o', '--output']:
943 out_file_name = value
947 if out_file_name is None:
948 sys.stderr.write("%(argv0)s: output file must be specified "
949 "(use --help for help)\n" % {'argv0': argv0})
952 in_file = open(in_file_name, 'r')
953 out_file = open(out_file_name, 'w')
959 if out_file_name.endswith('evaluate.h'):
960 generate_evaluate_h()
961 elif out_file_name.endswith('evaluate.inc'):
962 generate_evaluate_inc()
963 elif out_file_name.endswith('operations.h'):
964 generate_operations_h()
965 elif out_file_name.endswith('optimize.inc'):
966 generate_optimize_inc()
967 elif out_file_name.endswith('parse.inc'):
970 sys.stderr.write("%(argv0)s: unknown output type\n")