Update.
[pspp] / 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   /* If you add to these optimizations, please also add a
106      correctness test in tests/expressions/expressions.sh. */
107
108   /* x+0, x-0, 0+x => x. */
109   if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.))
110     return n->args[0];
111   else if (n->type == OP_ADD && eq_double (n->args[0], 0.)) 
112     return n->args[1];
113
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.))
117     return n->args[0];
118   else if (n->type == OP_MUL && eq_double (n->args[0], 1.))
119     return n->args[1];
120   
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.);
126
127   /* x**1 => x. */
128   else if (n->type == OP_POW && eq_double (n->args[1], 1))
129     return n->args[0];
130   
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]);
134
135   /* Otherwise, nothing to do. */
136   else
137     return node;
138 }
139
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 *,
145                                            size_t arg_idx);
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 *,
150                                               size_t arg_idx);
151
152 static union any_node *
153 evaluate_tree (struct composite_node *node, struct expression *e)
154 {
155   switch (node->type) 
156     {
157 #include "optimize.inc"
158
159     default:
160       assert (0);
161     }
162
163   /* Not reached. */
164   assert (0);
165   abort ();
166 }
167
168 static double
169 get_number_arg (struct composite_node *c, size_t arg_idx) 
170 {
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;
175 }
176
177 static double *
178 get_number_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
179                  struct expression *e) 
180 {
181   double *d;
182   size_t i;
183
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);
187   return d;
188 }
189
190 static struct fixed_string
191 get_string_arg (struct composite_node *c, size_t arg_idx) 
192 {
193   assert (arg_idx < c->arg_cnt);
194   assert (c->args[arg_idx]->type == OP_string);
195   return c->args[arg_idx]->string.s;
196 }
197
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) 
201 {
202   struct fixed_string *s;
203   size_t i;
204
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);
208   return s;
209 }
210
211 static const struct fmt_spec *
212 get_format_arg (struct composite_node *c, size_t arg_idx) 
213 {
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;
218 }
219 \f
220 /* Expression flattening. */
221
222 static union operation_data *allocate_aux (struct expression *,
223                                                 operation_type);
224 static void flatten_node (union any_node *, struct expression *);
225
226 static void
227 emit_operation (struct expression *e, operation_type type) 
228 {
229   allocate_aux (e, OP_operation)->operation = type;
230 }
231
232 static void
233 emit_number (struct expression *e, double n) 
234 {
235   allocate_aux (e, OP_number)->number = n;
236 }
237
238 static void
239 emit_string (struct expression *e, struct fixed_string s) 
240 {
241   allocate_aux (e, OP_string)->string = s;
242 }
243
244 static void
245 emit_format (struct expression *e, const struct fmt_spec *f) 
246 {
247   allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool,
248                                                     f, sizeof *f);
249 }
250
251 static void
252 emit_variable (struct expression *e, struct variable *v) 
253 {
254   allocate_aux (e, OP_variable)->variable = v;
255 }
256
257 static void
258 emit_vector (struct expression *e, const struct vector *v) 
259 {
260   allocate_aux (e, OP_vector)->vector = v;
261 }
262
263 static void
264 emit_integer (struct expression *e, int i) 
265 {
266   allocate_aux (e, OP_integer)->integer = i;
267 }
268
269 void 
270 expr_flatten (union any_node *n, struct expression *e) 
271 {
272   flatten_node (n, e);
273   e->type = expr_node_returns (n);
274   emit_operation (e, (e->type == OP_string
275                       ? OP_return_string : OP_return_number));
276 }
277
278 static void
279 flatten_atom (union any_node *n, struct expression *e)
280 {
281   switch (n->type) 
282     {
283     case OP_number:
284     case OP_boolean:
285       emit_operation (e, OP_number);
286       emit_number (e, n->number.n);
287       break;
288
289     case OP_string:
290       emit_operation (e, OP_string);
291       emit_string (e, n->string.s);
292       break;
293
294     case OP_num_var:
295     case OP_str_var:
296     case OP_vector:
297     case OP_no_format:
298     case OP_ni_format:
299     case OP_pos_int:
300       /* These are passed as aux data following the
301          operation. */
302       break;
303
304     default:
305       abort ();
306     }
307 }
308
309 static void
310 flatten_composite (union any_node *n, struct expression *e)
311 {
312   struct operation *op = &operations[n->type];
313   size_t i;
314       
315   for (i = 0; i < n->composite.arg_cnt; i++)
316     flatten_node (n->composite.args[i], e);
317
318   if (n->type != OP_BOOLEAN_TO_NUM)
319     emit_operation (e, n->type);
320
321   for (i = 0; i < n->composite.arg_cnt; i++)
322     {
323       union any_node *arg = n->composite.args[i];
324       switch (arg->type) 
325         {
326         case OP_num_var:
327         case OP_str_var:
328           emit_variable (e, arg->variable.v);
329           break;
330
331         case OP_vector:
332           emit_vector (e, arg->vector.v);
333           break;
334
335         case OP_ni_format:
336         case OP_no_format:
337           emit_format (e, &arg->format.f);
338           break;
339
340         case OP_pos_int:
341           emit_integer (e, arg->integer.i);
342           break;
343               
344         default:
345           /* Nothing to do. */
346           break;
347         }
348     }
349
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);
354 }
355
356 void
357 flatten_node (union any_node *n, struct expression *e)
358 {
359   assert (is_operation (n->type));
360
361   if (is_atom (n->type))
362     flatten_atom (n, e);
363   else if (is_composite (n->type))
364     flatten_composite (n, e);
365   else 
366     abort ();
367 }
368
369 static union operation_data *
370 allocate_aux (struct expression *e, operation_type type) 
371 {
372   if (e->op_cnt >= e->op_cap) 
373     {
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);
378     }
379
380   e->op_types[e->op_cnt] = type;
381   return &e->ops[e->op_cnt++];
382 }