Update.
[pspp-builds.git] / src / expressions / optimize.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
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.
9
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.
14
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., 59 Temple Place - Suite 330, Boston, MA
18    02111-1307, USA. */
19
20 #include <config.h>
21 #include "private.h"
22 #include <math.h>
23 #include <ctype.h>
24 #include <errno.h>
25 #include <stdlib.h>
26 #include "alloc.h"
27 #include "calendar.h"
28 #include "data-in.h"
29 #include "error.h"
30 #include "evaluate.h"
31 #include "helpers.h"
32 #include "misc.h"
33 #include "pool.h"
34 #include "public.h"
35 #include "str.h"
36 #include "var.h"
37
38 static union any_node *evaluate_tree (struct composite_node *,
39                                       struct expression *);
40 static union any_node *optimize_tree (union any_node *, struct expression *);
41
42 union any_node *
43 expr_optimize (union any_node *node, struct expression *e)
44 {
45   int nonconst_cnt = 0; /* Number of nonconstant children. */
46   int sysmis_cnt = 0;   /* Number of system-missing children. */
47   struct operation *op;
48   struct composite_node *c;
49   int i;
50
51   /* We can't optimize an atom. */
52   if (is_atom (node->type))
53     return node;
54
55   /* Start by optimizing all the children. */
56   c = &node->composite;
57   for (i = 0; i < c->arg_cnt; i++)
58     {
59       c->args[i] = expr_optimize (c->args[i], e);
60       if (c->args[i]->type == OP_number)
61         {
62           if (c->args[i]->number.n == SYSMIS)
63             sysmis_cnt++;
64         }
65
66       if (!is_atom (c->args[i]->type))
67         nonconst_cnt++;
68     }
69
70   op = &operations[c->type];
71   if (sysmis_cnt && (op->flags & OPF_ABSORB_MISS) == 0)
72     {
73       /* Most operations produce SYSMIS given any SYSMIS
74          argument. */
75       assert (op->returns == OP_number || op->returns == OP_boolean);
76       if (op->returns == OP_number)
77         return expr_allocate_number (e, SYSMIS);
78       else
79         return expr_allocate_boolean (e, SYSMIS);
80     }
81   else if (!nonconst_cnt && (op->flags & OPF_NONOPTIMIZABLE) == 0) 
82     {
83       /* Evaluate constant expressions. */
84       return evaluate_tree (&node->composite, e);
85     }
86   else 
87     {
88       /* A few optimization possibilities are still left. */
89       return optimize_tree (node, e); 
90     }
91 }
92
93 static int
94 eq_double (union any_node *node, double n) 
95 {
96   return node->type == OP_number && node->number.n == n;
97 }
98
99 static union any_node *
100 optimize_tree (union any_node *node, struct expression *e)
101 {
102   struct composite_node *n = &node->composite;
103   assert (is_composite (node->type));
104
105   /* x+0, x-0, 0+x => x. */
106   if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.))
107     return n->args[0];
108   else if (n->type == OP_ADD && eq_double (n->args[0], 0.)) 
109     return n->args[1];
110
111   /* x*1, x/1, 1*x => x. */
112   else if ((n->type == OP_MUL || n->type == OP_DIV)
113            && eq_double (n->args[1], 1.))
114     return n->args[0];
115   else if (n->type == OP_MUL && eq_double (n->args[0], 1.))
116     return n->args[1];
117   
118   /* 0*x, 0/x, x*0, MOD(0,x) => x. */
119   else if (((n->type == OP_MUL || n->type == OP_DIV || n->type == OP_MOD_nn)
120             && eq_double (n->args[0], 0.))
121            || (n->type == OP_MUL && eq_double (n->args[1], 0.)))
122     return expr_allocate_number (e, 0.);
123
124   /* x**1 => x. */
125   else if (n->type == OP_POW && eq_double (n->args[1], 1))
126     return n->args[0];
127   
128   /* x**2 => SQUARE(x). */
129   else if (n->type == OP_POW && eq_double (n->args[2], 2))
130     return expr_allocate_unary (e,OP_SQUARE, node);
131
132   /* Otherwise, nothing to do. */
133   else
134     return node;
135 }
136
137 static double get_number_arg (struct composite_node *, size_t arg_idx);
138 static double *get_number_args (struct composite_node *,
139                                  size_t arg_idx, size_t arg_cnt,
140                                  struct expression *);
141 static struct fixed_string get_string_arg (struct composite_node *,
142                                            size_t arg_idx);
143 static struct fixed_string *get_string_args (struct composite_node *,
144                                              size_t arg_idx, size_t arg_cnt,
145                                              struct expression *);
146 static const struct fmt_spec *get_format_arg (struct composite_node *,
147                                               size_t arg_idx);
148
149 static union any_node *
150 evaluate_tree (struct composite_node *node, struct expression *e)
151 {
152   switch (node->type) 
153     {
154 #include "optimize.inc"
155
156     default:
157       assert (0);
158     }
159
160   /* Not reached. */
161   assert (0);
162   abort ();
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 fixed_string
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 fixed_string *
196 get_string_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
197                  struct expression *e) 
198 {
199   struct fixed_string *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 fixed_string 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, 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       abort ();
303     }
304 }
305
306 static void
307 flatten_composite (union any_node *n, struct expression *e)
308 {
309   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     abort ();
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 }