src/language/expressions/optimize.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 1997-9, 2000, 2011 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
  19 #include "language/expressions/private.h"
  20
  21 #include <math.h>
  22 #include <ctype.h>
  23 #include <errno.h>
  24 #include <stdlib.h>
  25
  26 #include "data/calendar.h"
  27 #include "data/data-in.h"
  28 #include "data/variable.h"
  29 #include "language/expressions/evaluate.h"
  30 #include "language/expressions/helpers.h"
  31 #include "language/expressions/public.h"
  32 #include "libpspp/assertion.h"
  33 #include "libpspp/message.h"
  34 #include "libpspp/misc.h"
  35 #include "libpspp/pool.h"
  36 #include "libpspp/str.h"
  37
  38 #include "gl/xalloc.h"
  39
  40 static union any_node *evaluate_tree (struct composite_node *,
  41                                       struct expression *);
  42 static union any_node *optimize_tree (union any_node *, struct expression *);
  43
  44 union any_node *
  45 expr_optimize (union any_node *node, struct expression *e)
  46 {
  47   int nonconst_cnt = 0; /* Number of nonconstant children. */
  48   int sysmis_cnt = 0;   /* Number of system-missing children. */
  49   const struct operation *op;
  50   struct composite_node *c;
  51   int i;
  52
  53   /* We can't optimize an atom. */
  54   if (is_atom (node->type))
  55     return node;
  56
  57   /* Start by optimizing all the children. */
  58   c = &node->composite;
  59   for (i = 0; i < c->arg_cnt; i++)
  60     {
  61       c->args[i] = expr_optimize (c->args[i], e);
  62       if (c->args[i]->type == OP_number)
  63         {
  64           if (c->args[i]->number.n == SYSMIS)
  65             sysmis_cnt++;
  66         }
  67
  68       if (!is_atom (c->args[i]->type))
  69         nonconst_cnt++;
  70     }
  71
  72   op = &operations[c->type];
  73   if (sysmis_cnt && (op->flags & OPF_ABSORB_MISS) == 0)
  74     {
  75       /* Most operations produce SYSMIS given any SYSMIS
  76          argument. */
  77       assert (op->returns == OP_number || op->returns == OP_boolean);
  78       if (op->returns == OP_number)
  79         return expr_allocate_number (e, SYSMIS);
  80       else
  81         return expr_allocate_boolean (e, SYSMIS);
  82     }
  83   else if (!nonconst_cnt && (op->flags & OPF_NONOPTIMIZABLE) == 0)
  84     {
  85       /* Evaluate constant expressions. */
  86       return evaluate_tree (&node->composite, e);
  87     }
  88   else
  89     {
  90       /* A few optimization possibilities are still left. */
  91       return optimize_tree (node, e);
  92     }
  93 }
  94
  95 static int
  96 eq_double (union any_node *node, double n)
  97 {
  98   return node->type == OP_number && node->number.n == n;
  99 }
 100
 101 static union any_node *
 102 optimize_tree (union any_node *node, struct expression *e)
 103 {
 104   struct composite_node *n = &node->composite;
 105   assert (is_composite (node->type));
 106
 107   /* If you add to these optimizations, please also add a
 108      correctness test in tests/expressions/expressions.sh. */
 109
 110   /* x+0, x-0, 0+x => x. */
 111   if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.))
 112     return n->args[0];
 113   else if (n->type == OP_ADD && eq_double (n->args[0], 0.))
 114     return n->args[1];
 115
 116   /* x*1, x/1, 1*x => x. */
 117   else if ((n->type == OP_MUL || n->type == OP_DIV)
 118            && eq_double (n->args[1], 1.))
 119     return n->args[0];
 120   else if (n->type == OP_MUL && eq_double (n->args[0], 1.))
 121     return n->args[1];
 122
 123   /* 0*x, 0/x, x*0, MOD(0,x) => 0. */
 124   else if (((n->type == OP_MUL || n->type == OP_DIV || n->type == OP_MOD_nn)
 125             && eq_double (n->args[0], 0.))
 126            || (n->type == OP_MUL && eq_double (n->args[1], 0.)))
 127     return expr_allocate_number (e, 0.);
 128
 129   /* x**1 => x. */
 130   else if (n->type == OP_POW && eq_double (n->args[1], 1))
 131     return n->args[0];
 132
 133   /* x**2 => SQUARE(x). */
 134   else if (n->type == OP_POW && eq_double (n->args[1], 2))
 135     return expr_allocate_unary (e, OP_SQUARE, n->args[0]);
 136
 137   /* Otherwise, nothing to do. */
 138   else
 139     return node;
 140 }
 141
 142 static double get_number_arg (struct composite_node *, size_t arg_idx);
 143 static double *get_number_args (struct composite_node *,
 144                                  size_t arg_idx, size_t arg_cnt,
 145                                  struct expression *);
 146 static struct substring get_string_arg (struct composite_node *,
 147                                            size_t arg_idx);
 148 static struct substring *get_string_args (struct composite_node *,
 149                                              size_t arg_idx, size_t arg_cnt,
 150                                              struct expression *);
 151 static const struct fmt_spec *get_format_arg (struct composite_node *,
 152                                               size_t arg_idx);
 153
 154 static union any_node *
 155 evaluate_tree (struct composite_node *node, struct expression *e)
 156 {
 157   switch (node->type)
 158     {
 159 #include "optimize.inc"
 160
 161     default:
 162       NOT_REACHED ();
 163     }
 164
 165   NOT_REACHED ();
 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 substring
 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 substring *
 199 get_string_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt,
 200                  struct expression *e)
 201 {
 202   struct substring *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 substring 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, const 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       NOT_REACHED ();
 306     }
 307 }
 308
 309 static void
 310 flatten_composite (union any_node *n, struct expression *e)
 311 {
 312   const 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     NOT_REACHED ();
 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 }