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 }