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