1 /* PSPP - computes sample statistics.
2 Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 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, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
26 #include <libpspp/alloc.h>
27 #include <data/calendar.h>
28 #include <data/data-in.h>
29 #include <libpspp/message.h>
32 #include <libpspp/misc.h>
33 #include <libpspp/pool.h>
35 #include <libpspp/str.h>
36 #include <data/variable.h>
38 static union any_node *evaluate_tree (struct composite_node *,
40 static union any_node *optimize_tree (union any_node *, struct expression *);
43 expr_optimize (union any_node *node, struct expression *e)
45 int nonconst_cnt = 0; /* Number of nonconstant children. */
46 int sysmis_cnt = 0; /* Number of system-missing children. */
48 struct composite_node *c;
51 /* We can't optimize an atom. */
52 if (is_atom (node->type))
55 /* Start by optimizing all the children. */
57 for (i = 0; i < c->arg_cnt; i++)
59 c->args[i] = expr_optimize (c->args[i], e);
60 if (c->args[i]->type == OP_number)
62 if (c->args[i]->number.n == SYSMIS)
66 if (!is_atom (c->args[i]->type))
70 op = &operations[c->type];
71 if (sysmis_cnt && (op->flags & OPF_ABSORB_MISS) == 0)
73 /* Most operations produce SYSMIS given any SYSMIS
75 assert (op->returns == OP_number || op->returns == OP_boolean);
76 if (op->returns == OP_number)
77 return expr_allocate_number (e, SYSMIS);
79 return expr_allocate_boolean (e, SYSMIS);
81 else if (!nonconst_cnt && (op->flags & OPF_NONOPTIMIZABLE) == 0)
83 /* Evaluate constant expressions. */
84 return evaluate_tree (&node->composite, e);
88 /* A few optimization possibilities are still left. */
89 return optimize_tree (node, e);
94 eq_double (union any_node *node, double n)
96 return node->type == OP_number && node->number.n == n;
99 static union any_node *
100 optimize_tree (union any_node *node, struct expression *e)
102 struct composite_node *n = &node->composite;
103 assert (is_composite (node->type));
105 /* If you add to these optimizations, please also add a
106 correctness test in tests/expressions/expressions.sh. */
108 /* x+0, x-0, 0+x => x. */
109 if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.))
111 else if (n->type == OP_ADD && eq_double (n->args[0], 0.))
114 /* x*1, x/1, 1*x => x. */
115 else if ((n->type == OP_MUL || n->type == OP_DIV)
116 && eq_double (n->args[1], 1.))
118 else if (n->type == OP_MUL && eq_double (n->args[0], 1.))
121 /* 0*x, 0/x, x*0, MOD(0,x) => 0. */
122 else if (((n->type == OP_MUL || n->type == OP_DIV || n->type == OP_MOD_nn)
123 && eq_double (n->args[0], 0.))
124 || (n->type == OP_MUL && eq_double (n->args[1], 0.)))
125 return expr_allocate_number (e, 0.);
128 else if (n->type == OP_POW && eq_double (n->args[1], 1))
131 /* x**2 => SQUARE(x). */
132 else if (n->type == OP_POW && eq_double (n->args[1], 2))
133 return expr_allocate_unary (e, OP_SQUARE, n->args[0]);
135 /* Otherwise, nothing to do. */
140 static double get_number_arg (struct composite_node *, size_t arg_idx);
141 static double *get_number_args (struct composite_node *,
142 size_t arg_idx, size_t arg_cnt,
143 struct expression *);
144 static struct fixed_string get_string_arg (struct composite_node *,
146 static struct fixed_string *get_string_args (struct composite_node *,
147 size_t arg_idx, size_t arg_cnt,
148 struct expression *);
149 static const struct fmt_spec *get_format_arg (struct composite_node *,
152 static union any_node *
153 evaluate_tree (struct composite_node *node, struct expression *e)
157 #include "optimize.inc"
169 get_number_arg (struct composite_node *c, size_t arg_idx)
171 assert (arg_idx < c->arg_cnt);
172 assert (c->args[arg_idx]->type == OP_number
173 || c->args[arg_idx]->type == OP_boolean);
174 return c->args[arg_idx]->number.n;
178 get_number_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
179 struct expression *e)
184 d = pool_alloc (e->expr_pool, sizeof *d * arg_cnt);
185 for (i = 0; i < arg_cnt; i++)
186 d[i] = get_number_arg (c, i + arg_idx);
190 static struct fixed_string
191 get_string_arg (struct composite_node *c, size_t arg_idx)
193 assert (arg_idx < c->arg_cnt);
194 assert (c->args[arg_idx]->type == OP_string);
195 return c->args[arg_idx]->string.s;
198 static struct fixed_string *
199 get_string_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
200 struct expression *e)
202 struct fixed_string *s;
205 s = pool_alloc (e->expr_pool, sizeof *s * arg_cnt);
206 for (i = 0; i < arg_cnt; i++)
207 s[i] = get_string_arg (c, i + arg_idx);
211 static const struct fmt_spec *
212 get_format_arg (struct composite_node *c, size_t arg_idx)
214 assert (arg_idx < c->arg_cnt);
215 assert (c->args[arg_idx]->type == OP_ni_format
216 || c->args[arg_idx]->type == OP_no_format);
217 return &c->args[arg_idx]->format.f;
220 /* Expression flattening. */
222 static union operation_data *allocate_aux (struct expression *,
224 static void flatten_node (union any_node *, struct expression *);
227 emit_operation (struct expression *e, operation_type type)
229 allocate_aux (e, OP_operation)->operation = type;
233 emit_number (struct expression *e, double n)
235 allocate_aux (e, OP_number)->number = n;
239 emit_string (struct expression *e, struct fixed_string s)
241 allocate_aux (e, OP_string)->string = s;
245 emit_format (struct expression *e, const struct fmt_spec *f)
247 allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool,
252 emit_variable (struct expression *e, struct variable *v)
254 allocate_aux (e, OP_variable)->variable = v;
258 emit_vector (struct expression *e, const struct vector *v)
260 allocate_aux (e, OP_vector)->vector = v;
264 emit_integer (struct expression *e, int i)
266 allocate_aux (e, OP_integer)->integer = i;
270 expr_flatten (union any_node *n, struct expression *e)
273 e->type = expr_node_returns (n);
274 emit_operation (e, (e->type == OP_string
275 ? OP_return_string : OP_return_number));
279 flatten_atom (union any_node *n, struct expression *e)
285 emit_operation (e, OP_number);
286 emit_number (e, n->number.n);
290 emit_operation (e, OP_string);
291 emit_string (e, n->string.s);
300 /* These are passed as aux data following the
310 flatten_composite (union any_node *n, struct expression *e)
312 struct operation *op = &operations[n->type];
315 for (i = 0; i < n->composite.arg_cnt; i++)
316 flatten_node (n->composite.args[i], e);
318 if (n->type != OP_BOOLEAN_TO_NUM)
319 emit_operation (e, n->type);
321 for (i = 0; i < n->composite.arg_cnt; i++)
323 union any_node *arg = n->composite.args[i];
328 emit_variable (e, arg->variable.v);
332 emit_vector (e, arg->vector.v);
337 emit_format (e, &arg->format.f);
341 emit_integer (e, arg->integer.i);
350 if (op->flags & OPF_ARRAY_OPERAND)
351 emit_integer (e, n->composite.arg_cnt - op->arg_cnt + 1);
352 if (op->flags & OPF_MIN_VALID)
353 emit_integer (e, n->composite.min_valid);
357 flatten_node (union any_node *n, struct expression *e)
359 assert (is_operation (n->type));
361 if (is_atom (n->type))
363 else if (is_composite (n->type))
364 flatten_composite (n, e);
369 static union operation_data *
370 allocate_aux (struct expression *e, operation_type type)
372 if (e->op_cnt >= e->op_cap)
374 e->op_cap = (e->op_cap + 8) * 3 / 2;
375 e->ops = pool_realloc (e->expr_pool, e->ops, sizeof *e->ops * e->op_cap);
376 e->op_types = pool_realloc (e->expr_pool, e->op_types,
377 sizeof *e->op_types * e->op_cap);
380 e->op_types[e->op_cnt] = type;
381 return &e->ops[e->op_cnt++];