1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 1997-9, 2000, 2011 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 #include "language/expressions/private.h"
26 #include "data/calendar.h"
27 #include "data/data-in.h"
28 #include "data/variable.h"
30 #include "language/expressions/helpers.h"
31 #include "language/expressions/public.h"
32 #include "libpspp/assertion.h"
33 #include "libpspp/message.h"
34 #include "libpspp/misc.h"
35 #include "libpspp/pool.h"
36 #include "libpspp/str.h"
38 #include "gl/xalloc.h"
40 static struct expr_node *evaluate_tree (struct expr_node *, struct expression *);
41 static struct expr_node *optimize_tree (struct expr_node *, struct expression *);
44 expr_optimize (struct expr_node *node, struct expression *e)
46 int n_nonconst = 0; /* Number of nonconstant children. */
47 int n_sysmis = 0; /* Number of system-missing children. */
48 const struct operation *op;
51 /* We can't optimize an atom. */
52 if (is_atom (node->type))
55 /* Start by optimizing all the children. */
56 for (i = 0; i < node->n_args; i++)
58 node->args[i] = expr_optimize (node->args[i], e);
59 if (node->args[i]->type == OP_number)
61 if (node->args[i]->number == SYSMIS)
65 if (!is_atom (node->args[i]->type))
69 op = &operations[node->type];
70 if (n_sysmis && (op->flags & OPF_ABSORB_MISS) == 0)
72 /* Most operations produce SYSMIS given any SYSMIS
74 assert (op->returns == OP_number || op->returns == OP_boolean);
75 if (op->returns == OP_number)
76 return expr_allocate_number (e, SYSMIS);
78 return expr_allocate_boolean (e, SYSMIS);
80 else if (!n_nonconst && (op->flags & OPF_NONOPTIMIZABLE) == 0)
82 /* Evaluate constant expressions. */
83 return evaluate_tree (node, e);
87 /* A few optimization possibilities are still left. */
88 return optimize_tree (node, e);
93 eq_double (struct expr_node *node, double n)
95 return node->type == OP_number && node->number == n;
98 static struct expr_node *
99 optimize_tree (struct expr_node *n, struct expression *e)
101 assert (is_composite (n->type));
103 /* If you add to these optimizations, please also add a
104 correctness test in tests/expressions/expressions.sh. */
106 /* x+0, x-0, 0+x => x. */
107 if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.))
109 else if (n->type == OP_ADD && eq_double (n->args[0], 0.))
112 /* x*1, x/1, 1*x => x. */
113 else if ((n->type == OP_MUL || n->type == OP_DIV)
114 && eq_double (n->args[1], 1.))
116 else if (n->type == OP_MUL && eq_double (n->args[0], 1.))
119 /* 0*x, 0/x, x*0, MOD(0,x) => 0. */
120 else if (((n->type == OP_MUL || n->type == OP_DIV || n->type == OP_MOD_nn)
121 && eq_double (n->args[0], 0.))
122 || (n->type == OP_MUL && eq_double (n->args[1], 0.)))
123 return expr_allocate_number (e, 0.);
126 else if (n->type == OP_POW && eq_double (n->args[1], 1))
129 /* x**2 => SQUARE(x). */
130 else if (n->type == OP_POW && eq_double (n->args[1], 2))
131 return expr_allocate_unary (e, OP_SQUARE, n->args[0]);
133 /* Otherwise, nothing to do. */
138 static double get_number_arg (struct expr_node *, size_t arg_idx);
139 static double *get_number_args (struct expr_node *,
140 size_t arg_idx, size_t n_args,
141 struct expression *);
142 static struct substring get_string_arg (struct expr_node *,
144 static struct substring *get_string_args (struct expr_node *,
145 size_t arg_idx, size_t n_args,
146 struct expression *);
147 static const struct fmt_spec *get_format_arg (struct expr_node *,
150 static struct expr_node *
151 evaluate_tree (struct expr_node *node, struct expression *e)
155 #include "optimize.inc"
165 get_number_arg (struct expr_node *n, size_t arg_idx)
167 assert (arg_idx < n->n_args);
168 assert (n->args[arg_idx]->type == OP_number
169 || n->args[arg_idx]->type == OP_boolean);
170 return n->args[arg_idx]->number;
174 get_number_args (struct expr_node *n, size_t arg_idx, size_t n_args,
175 struct expression *e)
177 double *d = pool_alloc (e->expr_pool, sizeof *d * n_args);
178 for (size_t i = 0; i < n_args; i++)
179 d[i] = get_number_arg (n, i + arg_idx);
183 static struct substring
184 get_string_arg (struct expr_node *n, size_t arg_idx)
186 assert (arg_idx < n->n_args);
187 assert (n->args[arg_idx]->type == OP_string);
188 return n->args[arg_idx]->string;
191 static struct substring *
192 get_string_args (struct expr_node *n, size_t arg_idx, size_t n_args,
193 struct expression *e)
198 s = pool_alloc (e->expr_pool, sizeof *s * n_args);
199 for (i = 0; i < n_args; i++)
200 s[i] = get_string_arg (n, i + arg_idx);
204 static const struct fmt_spec *
205 get_format_arg (struct expr_node *n, size_t arg_idx)
207 assert (arg_idx < n->n_args);
208 assert (n->args[arg_idx]->type == OP_ni_format
209 || n->args[arg_idx]->type == OP_no_format);
210 return &n->args[arg_idx]->format;
213 /* Expression flattening. */
215 static union operation_data *allocate_aux (struct expression *,
217 static void flatten_node (struct expr_node *, struct expression *);
220 emit_operation (struct expression *e, operation_type type)
222 allocate_aux (e, OP_operation)->operation = type;
226 emit_number (struct expression *e, double n)
228 allocate_aux (e, OP_number)->number = n;
232 emit_string (struct expression *e, struct substring s)
234 allocate_aux (e, OP_string)->string = s;
238 emit_format (struct expression *e, const struct fmt_spec *f)
240 allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool,
245 emit_variable (struct expression *e, const struct variable *v)
247 allocate_aux (e, OP_variable)->variable = v;
251 emit_vector (struct expression *e, const struct vector *v)
253 allocate_aux (e, OP_vector)->vector = v;
257 emit_integer (struct expression *e, int i)
259 allocate_aux (e, OP_integer)->integer = i;
263 expr_flatten (struct expr_node *n, struct expression *e)
266 e->type = expr_node_returns (n);
267 emit_operation (e, (e->type == OP_string
268 ? OP_return_string : OP_return_number));
272 flatten_atom (struct expr_node *n, struct expression *e)
278 emit_operation (e, OP_number);
279 emit_number (e, n->number);
283 emit_operation (e, OP_string);
284 emit_string (e, n->string);
293 /* These are passed as aux data following the
303 flatten_composite (struct expr_node *n, struct expression *e)
305 const struct operation *op = &operations[n->type];
308 for (i = 0; i < n->n_args; i++)
309 flatten_node (n->args[i], e);
311 if (n->type != OP_BOOLEAN_TO_NUM)
312 emit_operation (e, n->type);
314 for (i = 0; i < n->n_args; i++)
316 struct expr_node *arg = n->args[i];
321 emit_variable (e, arg->variable);
325 emit_vector (e, arg->vector);
330 emit_format (e, &arg->format);
334 emit_integer (e, arg->integer);
343 if (op->flags & OPF_ARRAY_OPERAND)
344 emit_integer (e, n->n_args - op->n_args + 1);
345 if (op->flags & OPF_MIN_VALID)
346 emit_integer (e, n->min_valid);
350 flatten_node (struct expr_node *n, struct expression *e)
352 assert (is_operation (n->type));
354 if (is_atom (n->type))
356 else if (is_composite (n->type))
357 flatten_composite (n, e);
362 static union operation_data *
363 allocate_aux (struct expression *e, operation_type type)
365 if (e->n_ops >= e->allocated_ops)
367 e->allocated_ops = (e->allocated_ops + 8) * 3 / 2;
368 e->ops = pool_realloc (e->expr_pool, e->ops,
369 sizeof *e->ops * e->allocated_ops);
370 e->op_types = pool_realloc (e->expr_pool, e->op_types,
371 sizeof *e->op_types * e->allocated_ops);
374 e->op_types[e->n_ops] = type;
375 return &e->ops[e->n_ops++];