Fixed return type of design_matrix_get_case_count.
[pspp-builds.git] / src / language / expressions / optimize.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 #include <config.h>
18 #include "private.h"
19 #include <math.h>
20 #include <ctype.h>
21 #include <errno.h>
22 #include <stdlib.h>
23 #include <libpspp/assertion.h>
24 #include <data/calendar.h>
25 #include <data/data-in.h>
26 #include <libpspp/message.h>
27 #include "evaluate.h"
28 #include "helpers.h"
29 #include <libpspp/misc.h>
30 #include <libpspp/pool.h>
31 #include "public.h"
32 #include <libpspp/str.h>
33 #include <data/variable.h>
34
35 #include "xalloc.h"
36
37 static union any_node *evaluate_tree (struct composite_node *,
38                                       struct expression *);
39 static union any_node *optimize_tree (union any_node *, struct expression *);
40
41 union any_node *
42 expr_optimize (union any_node *node, struct expression *e)
43 {
44   int nonconst_cnt = 0; /* Number of nonconstant children. */
45   int sysmis_cnt = 0;   /* Number of system-missing children. */
46   const struct operation *op;
47   struct composite_node *c;
48   int i;
49
50   /* We can't optimize an atom. */
51   if (is_atom (node->type))
52     return node;
53
54   /* Start by optimizing all the children. */
55   c = &node->composite;
56   for (i = 0; i < c->arg_cnt; i++)
57     {
58       c->args[i] = expr_optimize (c->args[i], e);
59       if (c->args[i]->type == OP_number)
60         {
61           if (c->args[i]->number.n == SYSMIS)
62             sysmis_cnt++;
63         }
64
65       if (!is_atom (c->args[i]->type))
66         nonconst_cnt++;
67     }
68
69   op = &operations[c->type];
70   if (sysmis_cnt && (op->flags & OPF_ABSORB_MISS) == 0)
71     {
72       /* Most operations produce SYSMIS given any SYSMIS
73          argument. */
74       assert (op->returns == OP_number || op->returns == OP_boolean);
75       if (op->returns == OP_number)
76         return expr_allocate_number (e, SYSMIS);
77       else
78         return expr_allocate_boolean (e, SYSMIS);
79     }
80   else if (!nonconst_cnt && (op->flags & OPF_NONOPTIMIZABLE) == 0)
81     {
82       /* Evaluate constant expressions. */
83       return evaluate_tree (&node->composite, e);
84     }
85   else
86     {
87       /* A few optimization possibilities are still left. */
88       return optimize_tree (node, e);
89     }
90 }
91
92 static int
93 eq_double (union any_node *node, double n)
94 {
95   return node->type == OP_number && node->number.n == n;
96 }
97
98 static union any_node *
99 optimize_tree (union any_node *node, struct expression *e)
100 {
101   struct composite_node *n = &node->composite;
102   assert (is_composite (node->type));
103
104   /* If you add to these optimizations, please also add a
105      correctness test in tests/expressions/expressions.sh. */
106
107   /* x+0, x-0, 0+x => x. */
108   if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.))
109     return n->args[0];
110   else if (n->type == OP_ADD && eq_double (n->args[0], 0.))
111     return n->args[1];
112
113   /* x*1, x/1, 1*x => x. */
114   else if ((n->type == OP_MUL || n->type == OP_DIV)
115            && eq_double (n->args[1], 1.))
116     return n->args[0];
117   else if (n->type == OP_MUL && eq_double (n->args[0], 1.))
118     return n->args[1];
119
120   /* 0*x, 0/x, x*0, MOD(0,x) => 0. */
121   else if (((n->type == OP_MUL || n->type == OP_DIV || n->type == OP_MOD_nn)
122             && eq_double (n->args[0], 0.))
123            || (n->type == OP_MUL && eq_double (n->args[1], 0.)))
124     return expr_allocate_number (e, 0.);
125
126   /* x**1 => x. */
127   else if (n->type == OP_POW && eq_double (n->args[1], 1))
128     return n->args[0];
129
130   /* x**2 => SQUARE(x). */
131   else if (n->type == OP_POW && eq_double (n->args[1], 2))
132     return expr_allocate_unary (e, OP_SQUARE, n->args[0]);
133
134   /* Otherwise, nothing to do. */
135   else
136     return node;
137 }
138
139 static double get_number_arg (struct composite_node *, size_t arg_idx);
140 static double *get_number_args (struct composite_node *,
141                                  size_t arg_idx, size_t arg_cnt,
142                                  struct expression *);
143 static struct substring get_string_arg (struct composite_node *,
144                                            size_t arg_idx);
145 static struct substring *get_string_args (struct composite_node *,
146                                              size_t arg_idx, size_t arg_cnt,
147                                              struct expression *);
148 static const struct fmt_spec *get_format_arg (struct composite_node *,
149                                               size_t arg_idx);
150
151 static union any_node *
152 evaluate_tree (struct composite_node *node, struct expression *e)
153 {
154   switch (node->type)
155     {
156 #include "optimize.inc"
157
158     default:
159       NOT_REACHED ();
160     }
161
162   NOT_REACHED ();
163 }
164
165 static double
166 get_number_arg (struct composite_node *c, size_t arg_idx)
167 {
168   assert (arg_idx < c->arg_cnt);
169   assert (c->args[arg_idx]->type == OP_number
170           || c->args[arg_idx]->type == OP_boolean);
171   return c->args[arg_idx]->number.n;
172 }
173
174 static double *
175 get_number_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
176                  struct expression *e)
177 {
178   double *d;
179   size_t i;
180
181   d = pool_alloc (e->expr_pool, sizeof *d * arg_cnt);
182   for (i = 0; i < arg_cnt; i++)
183     d[i] = get_number_arg (c, i + arg_idx);
184   return d;
185 }
186
187 static struct substring
188 get_string_arg (struct composite_node *c, size_t arg_idx)
189 {
190   assert (arg_idx < c->arg_cnt);
191   assert (c->args[arg_idx]->type == OP_string);
192   return c->args[arg_idx]->string.s;
193 }
194
195 static struct substring *
196 get_string_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
197                  struct expression *e)
198 {
199   struct substring *s;
200   size_t i;
201
202   s = pool_alloc (e->expr_pool, sizeof *s * arg_cnt);
203   for (i = 0; i < arg_cnt; i++)
204     s[i] = get_string_arg (c, i + arg_idx);
205   return s;
206 }
207
208 static const struct fmt_spec *
209 get_format_arg (struct composite_node *c, size_t arg_idx)
210 {
211   assert (arg_idx < c->arg_cnt);
212   assert (c->args[arg_idx]->type == OP_ni_format
213           || c->args[arg_idx]->type == OP_no_format);
214   return &c->args[arg_idx]->format.f;
215 }
216 \f
217 /* Expression flattening. */
218
219 static union operation_data *allocate_aux (struct expression *,
220                                                 operation_type);
221 static void flatten_node (union any_node *, struct expression *);
222
223 static void
224 emit_operation (struct expression *e, operation_type type)
225 {
226   allocate_aux (e, OP_operation)->operation = type;
227 }
228
229 static void
230 emit_number (struct expression *e, double n)
231 {
232   allocate_aux (e, OP_number)->number = n;
233 }
234
235 static void
236 emit_string (struct expression *e, struct substring s)
237 {
238   allocate_aux (e, OP_string)->string = s;
239 }
240
241 static void
242 emit_format (struct expression *e, const struct fmt_spec *f)
243 {
244   allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool,
245                                                     f, sizeof *f);
246 }
247
248 static void
249 emit_variable (struct expression *e, const struct variable *v)
250 {
251   allocate_aux (e, OP_variable)->variable = v;
252 }
253
254 static void
255 emit_vector (struct expression *e, const struct vector *v)
256 {
257   allocate_aux (e, OP_vector)->vector = v;
258 }
259
260 static void
261 emit_integer (struct expression *e, int i)
262 {
263   allocate_aux (e, OP_integer)->integer = i;
264 }
265
266 void
267 expr_flatten (union any_node *n, struct expression *e)
268 {
269   flatten_node (n, e);
270   e->type = expr_node_returns (n);
271   emit_operation (e, (e->type == OP_string
272                       ? OP_return_string : OP_return_number));
273 }
274
275 static void
276 flatten_atom (union any_node *n, struct expression *e)
277 {
278   switch (n->type)
279     {
280     case OP_number:
281     case OP_boolean:
282       emit_operation (e, OP_number);
283       emit_number (e, n->number.n);
284       break;
285
286     case OP_string:
287       emit_operation (e, OP_string);
288       emit_string (e, n->string.s);
289       break;
290
291     case OP_num_var:
292     case OP_str_var:
293     case OP_vector:
294     case OP_no_format:
295     case OP_ni_format:
296     case OP_pos_int:
297       /* These are passed as aux data following the
298          operation. */
299       break;
300
301     default:
302       NOT_REACHED ();
303     }
304 }
305
306 static void
307 flatten_composite (union any_node *n, struct expression *e)
308 {
309   const struct operation *op = &operations[n->type];
310   size_t i;
311
312   for (i = 0; i < n->composite.arg_cnt; i++)
313     flatten_node (n->composite.args[i], e);
314
315   if (n->type != OP_BOOLEAN_TO_NUM)
316     emit_operation (e, n->type);
317
318   for (i = 0; i < n->composite.arg_cnt; i++)
319     {
320       union any_node *arg = n->composite.args[i];
321       switch (arg->type)
322         {
323         case OP_num_var:
324         case OP_str_var:
325           emit_variable (e, arg->variable.v);
326           break;
327
328         case OP_vector:
329           emit_vector (e, arg->vector.v);
330           break;
331
332         case OP_ni_format:
333         case OP_no_format:
334           emit_format (e, &arg->format.f);
335           break;
336
337         case OP_pos_int:
338           emit_integer (e, arg->integer.i);
339           break;
340
341         default:
342           /* Nothing to do. */
343           break;
344         }
345     }
346
347   if (op->flags & OPF_ARRAY_OPERAND)
348     emit_integer (e, n->composite.arg_cnt - op->arg_cnt + 1);
349   if (op->flags & OPF_MIN_VALID)
350     emit_integer (e, n->composite.min_valid);
351 }
352
353 void
354 flatten_node (union any_node *n, struct expression *e)
355 {
356   assert (is_operation (n->type));
357
358   if (is_atom (n->type))
359     flatten_atom (n, e);
360   else if (is_composite (n->type))
361     flatten_composite (n, e);
362   else
363     NOT_REACHED ();
364 }
365
366 static union operation_data *
367 allocate_aux (struct expression *e, operation_type type)
368 {
369   if (e->op_cnt >= e->op_cap)
370     {
371       e->op_cap = (e->op_cap + 8) * 3 / 2;
372       e->ops = pool_realloc (e->expr_pool, e->ops, sizeof *e->ops * e->op_cap);
373       e->op_types = pool_realloc (e->expr_pool, e->op_types,
374                                   sizeof *e->op_types * e->op_cap);
375     }
376
377   e->op_types[e->op_cnt] = type;
378   return &e->ops[e->op_cnt++];
379 }