src/language/expressions/optimize.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    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, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 #include <config.h>
  20 #include "private.h"
  21 #include <math.h>
  22 #include <ctype.h>
  23 #include <errno.h>
  24 #include <stdlib.h>
  25 #include <libpspp/alloc.h>
  26 #include <libpspp/assertion.h>
  27 #include <data/calendar.h>
  28 #include <data/data-in.h>
  29 #include <libpspp/message.h>
  30 #include "evaluate.h"
  31 #include "helpers.h"
  32 #include <libpspp/misc.h>
  33 #include <libpspp/pool.h>
  34 #include "public.h"
  35 #include <libpspp/str.h>
  36 #include <data/variable.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   const 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 substring get_string_arg (struct composite_node *,
 145                                            size_t arg_idx);
 146 static struct substring *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       NOT_REACHED ();
 161     }
 162
 163   NOT_REACHED ();
 164 }
 165
 166 static double
 167 get_number_arg (struct composite_node *c, size_t arg_idx)
 168 {
 169   assert (arg_idx < c->arg_cnt);
 170   assert (c->args[arg_idx]->type == OP_number
 171           || c->args[arg_idx]->type == OP_boolean);
 172   return c->args[arg_idx]->number.n;
 173 }
 174
 175 static double *
 176 get_number_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
 177                  struct expression *e)
 178 {
 179   double *d;
 180   size_t i;
 181
 182   d = pool_alloc (e->expr_pool, sizeof *d * arg_cnt);
 183   for (i = 0; i < arg_cnt; i++)
 184     d[i] = get_number_arg (c, i + arg_idx);
 185   return d;
 186 }
 187
 188 static struct substring
 189 get_string_arg (struct composite_node *c, size_t arg_idx)
 190 {
 191   assert (arg_idx < c->arg_cnt);
 192   assert (c->args[arg_idx]->type == OP_string);
 193   return c->args[arg_idx]->string.s;
 194 }
 195
 196 static struct substring *
 197 get_string_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
 198                  struct expression *e)
 199 {
 200   struct substring *s;
 201   size_t i;
 202
 203   s = pool_alloc (e->expr_pool, sizeof *s * arg_cnt);
 204   for (i = 0; i < arg_cnt; i++)
 205     s[i] = get_string_arg (c, i + arg_idx);
 206   return s;
 207 }
 208
 209 static const struct fmt_spec *
 210 get_format_arg (struct composite_node *c, size_t arg_idx)
 211 {
 212   assert (arg_idx < c->arg_cnt);
 213   assert (c->args[arg_idx]->type == OP_ni_format
 214           || c->args[arg_idx]->type == OP_no_format);
 215   return &c->args[arg_idx]->format.f;
 216 }
 217 \f
 218 /* Expression flattening. */
 219
 220 static union operation_data *allocate_aux (struct expression *,
 221                                                 operation_type);
 222 static void flatten_node (union any_node *, struct expression *);
 223
 224 static void
 225 emit_operation (struct expression *e, operation_type type)
 226 {
 227   allocate_aux (e, OP_operation)->operation = type;
 228 }
 229
 230 static void
 231 emit_number (struct expression *e, double n)
 232 {
 233   allocate_aux (e, OP_number)->number = n;
 234 }
 235
 236 static void
 237 emit_string (struct expression *e, struct substring s)
 238 {
 239   allocate_aux (e, OP_string)->string = s;
 240 }
 241
 242 static void
 243 emit_format (struct expression *e, const struct fmt_spec *f)
 244 {
 245   allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool,
 246                                                     f, sizeof *f);
 247 }
 248
 249 static void
 250 emit_variable (struct expression *e, struct variable *v)
 251 {
 252   allocate_aux (e, OP_variable)->variable = v;
 253 }
 254
 255 static void
 256 emit_vector (struct expression *e, const struct vector *v)
 257 {
 258   allocate_aux (e, OP_vector)->vector = v;
 259 }
 260
 261 static void
 262 emit_integer (struct expression *e, int i)
 263 {
 264   allocate_aux (e, OP_integer)->integer = i;
 265 }
 266
 267 void
 268 expr_flatten (union any_node *n, struct expression *e)
 269 {
 270   flatten_node (n, e);
 271   e->type = expr_node_returns (n);
 272   emit_operation (e, (e->type == OP_string
 273                       ? OP_return_string : OP_return_number));
 274 }
 275
 276 static void
 277 flatten_atom (union any_node *n, struct expression *e)
 278 {
 279   switch (n->type)
 280     {
 281     case OP_number:
 282     case OP_boolean:
 283       emit_operation (e, OP_number);
 284       emit_number (e, n->number.n);
 285       break;
 286
 287     case OP_string:
 288       emit_operation (e, OP_string);
 289       emit_string (e, n->string.s);
 290       break;
 291
 292     case OP_num_var:
 293     case OP_str_var:
 294     case OP_vector:
 295     case OP_no_format:
 296     case OP_ni_format:
 297     case OP_pos_int:
 298       /* These are passed as aux data following the
 299          operation. */
 300       break;
 301
 302     default:
 303       NOT_REACHED ();
 304     }
 305 }
 306
 307 static void
 308 flatten_composite (union any_node *n, struct expression *e)
 309 {
 310   const struct operation *op = &operations[n->type];
 311   size_t i;
 312
 313   for (i = 0; i < n->composite.arg_cnt; i++)
 314     flatten_node (n->composite.args[i], e);
 315
 316   if (n->type != OP_BOOLEAN_TO_NUM)
 317     emit_operation (e, n->type);
 318
 319   for (i = 0; i < n->composite.arg_cnt; i++)
 320     {
 321       union any_node *arg = n->composite.args[i];
 322       switch (arg->type)
 323         {
 324         case OP_num_var:
 325         case OP_str_var:
 326           emit_variable (e, arg->variable.v);
 327           break;
 328
 329         case OP_vector:
 330           emit_vector (e, arg->vector.v);
 331           break;
 332
 333         case OP_ni_format:
 334         case OP_no_format:
 335           emit_format (e, &arg->format.f);
 336           break;
 337
 338         case OP_pos_int:
 339           emit_integer (e, arg->integer.i);
 340           break;
 341
 342         default:
 343           /* Nothing to do. */
 344           break;
 345         }
 346     }
 347
 348   if (op->flags & OPF_ARRAY_OPERAND)
 349     emit_integer (e, n->composite.arg_cnt - op->arg_cnt + 1);
 350   if (op->flags & OPF_MIN_VALID)
 351     emit_integer (e, n->composite.min_valid);
 352 }
 353
 354 void
 355 flatten_node (union any_node *n, struct expression *e)
 356 {
 357   assert (is_operation (n->type));
 358
 359   if (is_atom (n->type))
 360     flatten_atom (n, e);
 361   else if (is_composite (n->type))
 362     flatten_composite (n, e);
 363   else
 364     NOT_REACHED ();
 365 }
 366
 367 static union operation_data *
 368 allocate_aux (struct expression *e, operation_type type)
 369 {
 370   if (e->op_cnt >= e->op_cap)
 371     {
 372       e->op_cap = (e->op_cap + 8) * 3 / 2;
 373       e->ops = pool_realloc (e->expr_pool, e->ops, sizeof *e->ops * e->op_cap);
 374       e->op_types = pool_realloc (e->expr_pool, e->op_types,
 375                                   sizeof *e->op_types * e->op_cap);
 376     }
 377
 378   e->op_types[e->op_cnt] = type;
 379   return &e->ops[e->op_cnt++];
 380 }