pintos-os.org Git - pspp/blob - 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 "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 struct expr_node *evaluate_tree (struct expr_node *, struct expression *);
  41 static struct expr_node *optimize_tree (struct expr_node *, struct expression *);
  42
  43 struct expr_node *
  44 expr_optimize (struct expr_node *node, struct expression *e)
  45 {
  46   int n_nonconst = 0; /* Number of nonconstant children. */
  47   int n_sysmis = 0;   /* Number of system-missing children. */
  48   const struct operation *op;
  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   for (i = 0; i < node->n_args; i++)
  57     {
  58       node->args[i] = expr_optimize (node->args[i], e);
  59       if (node->args[i]->type == OP_number)
  60         {
  61           if (node->args[i]->number == SYSMIS)
  62             n_sysmis++;
  63         }
  64
  65       if (!is_atom (node->args[i]->type))
  66         n_nonconst++;
  67     }
  68
  69   op = &operations[node->type];
  70   if (n_sysmis && (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 (!n_nonconst && (op->flags & OPF_NONOPTIMIZABLE) == 0)
  81     {
  82       /* Evaluate constant expressions. */
  83       return evaluate_tree (node, 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 (struct expr_node *node, double n)
  94 {
  95   return node->type == OP_number && node->number == n;
  96 }
  97
  98 static struct expr_node *
  99 optimize_tree (struct expr_node *n, struct expression *e)
 100 {
 101   assert (is_composite (n->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 n;
 136 }
 137
 138 static double
 139 get_number_arg (struct expr_node *n, size_t arg_idx)
 140 {
 141   assert (arg_idx < n->n_args);
 142   assert (n->args[arg_idx]->type == OP_number
 143           || n->args[arg_idx]->type == OP_boolean
 144           || n->args[arg_idx]->type == OP_integer);
 145   return n->args[arg_idx]->number;
 146 }
 147
 148 static double *
 149 get_number_args (struct expr_node *n, size_t arg_idx, size_t n_args,
 150                  struct expression *e)
 151 {
 152   double *d = pool_alloc (e->expr_pool, sizeof *d * n_args);
 153   for (size_t i = 0; i < n_args; i++)
 154     d[i] = get_number_arg (n, i + arg_idx);
 155   return d;
 156 }
 157
 158 static struct substring
 159 get_string_arg (struct expr_node *n, size_t arg_idx)
 160 {
 161   assert (arg_idx < n->n_args);
 162   assert (n->args[arg_idx]->type == OP_string);
 163   return n->args[arg_idx]->string;
 164 }
 165
 166 static struct substring *
 167 get_string_args (struct expr_node *n, size_t arg_idx, size_t n_args,
 168                  struct expression *e)
 169 {
 170   struct substring *s;
 171   size_t i;
 172
 173   s = pool_alloc (e->expr_pool, sizeof *s * n_args);
 174   for (i = 0; i < n_args; i++)
 175     s[i] = get_string_arg (n, i + arg_idx);
 176   return s;
 177 }
 178
 179 static const struct fmt_spec *
 180 get_format_arg (struct expr_node *n, size_t arg_idx)
 181 {
 182   assert (arg_idx < n->n_args);
 183   assert (n->args[arg_idx]->type == OP_ni_format
 184           || n->args[arg_idx]->type == OP_no_format);
 185   return &n->args[arg_idx]->format;
 186 }
 187
 188 static struct expr_node *
 189 evaluate_tree (struct expr_node *node, struct expression *e)
 190 {
 191   switch (node->type)
 192     {
 193 #include "optimize.inc"
 194
 195     default:
 196       NOT_REACHED ();
 197     }
 198
 199   NOT_REACHED ();
 200 }
 201 \f
 202 /* Expression flattening. */
 203
 204 static union operation_data *allocate_aux (struct expression *,
 205                                                 operation_type);
 206 static void flatten_node (struct expr_node *, struct expression *);
 207
 208 static void
 209 emit_operation (struct expression *e, operation_type type)
 210 {
 211   allocate_aux (e, OP_operation)->operation = type;
 212 }
 213
 214 static void
 215 emit_number (struct expression *e, double n)
 216 {
 217   allocate_aux (e, OP_number)->number = n;
 218 }
 219
 220 static void
 221 emit_string (struct expression *e, struct substring s)
 222 {
 223   allocate_aux (e, OP_string)->string = s;
 224 }
 225
 226 static void
 227 emit_format (struct expression *e, const struct fmt_spec *f)
 228 {
 229   allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool,
 230                                                     f, sizeof *f);
 231 }
 232
 233 static void
 234 emit_variable (struct expression *e, const struct variable *v)
 235 {
 236   allocate_aux (e, OP_variable)->variable = v;
 237 }
 238
 239 static void
 240 emit_vector (struct expression *e, const struct vector *v)
 241 {
 242   allocate_aux (e, OP_vector)->vector = v;
 243 }
 244
 245 static void
 246 emit_integer (struct expression *e, int i)
 247 {
 248   allocate_aux (e, OP_integer)->integer = i;
 249 }
 250
 251 void
 252 expr_flatten (struct expr_node *n, struct expression *e)
 253 {
 254   flatten_node (n, e);
 255   e->type = expr_node_returns (n);
 256   emit_operation (e, (e->type == OP_string
 257                       ? OP_return_string : OP_return_number));
 258 }
 259
 260 static void
 261 flatten_atom (struct expr_node *n, struct expression *e)
 262 {
 263   switch (n->type)
 264     {
 265     case OP_number:
 266     case OP_boolean:
 267       emit_operation (e, OP_number);
 268       emit_number (e, n->number);
 269       break;
 270
 271     case OP_string:
 272       emit_operation (e, OP_string);
 273       emit_string (e, n->string);
 274       break;
 275
 276     case OP_num_var:
 277     case OP_str_var:
 278     case OP_vector:
 279     case OP_no_format:
 280     case OP_ni_format:
 281     case OP_pos_int:
 282       /* These are passed as aux data following the
 283          operation. */
 284       break;
 285
 286     default:
 287       NOT_REACHED ();
 288     }
 289 }
 290
 291 static void
 292 flatten_composite (struct expr_node *n, struct expression *e)
 293 {
 294   const struct operation *op = &operations[n->type];
 295   size_t i;
 296
 297   for (i = 0; i < n->n_args; i++)
 298     flatten_node (n->args[i], e);
 299
 300   if (n->type != OP_BOOLEAN_TO_NUM)
 301     emit_operation (e, n->type);
 302
 303   for (i = 0; i < n->n_args; i++)
 304     {
 305       struct expr_node *arg = n->args[i];
 306       switch (arg->type)
 307         {
 308         case OP_num_var:
 309         case OP_str_var:
 310           emit_variable (e, arg->variable);
 311           break;
 312
 313         case OP_vector:
 314           emit_vector (e, arg->vector);
 315           break;
 316
 317         case OP_ni_format:
 318         case OP_no_format:
 319           emit_format (e, &arg->format);
 320           break;
 321
 322         case OP_pos_int:
 323           emit_integer (e, arg->integer);
 324           break;
 325
 326         default:
 327           /* Nothing to do. */
 328           break;
 329         }
 330     }
 331
 332   if (op->flags & OPF_ARRAY_OPERAND)
 333     emit_integer (e, n->n_args - op->n_args + 1);
 334   if (op->flags & OPF_MIN_VALID)
 335     emit_integer (e, n->min_valid);
 336   if (op->flags & OPF_EXPR_NODE)
 337     allocate_aux (e, OP_exprnode)->node = n;
 338 }
 339
 340 void
 341 flatten_node (struct expr_node *n, struct expression *e)
 342 {
 343   assert (is_operation (n->type));
 344
 345   if (is_atom (n->type))
 346     flatten_atom (n, e);
 347   else if (is_composite (n->type))
 348     flatten_composite (n, e);
 349   else
 350     NOT_REACHED ();
 351 }
 352
 353 static union operation_data *
 354 allocate_aux (struct expression *e, operation_type type)
 355 {
 356   if (e->n_ops >= e->allocated_ops)
 357     {
 358       e->allocated_ops = (e->allocated_ops + 8) * 3 / 2;
 359       e->ops = pool_realloc (e->expr_pool, e->ops,
 360                              sizeof *e->ops * e->allocated_ops);
 361       e->op_types = pool_realloc (e->expr_pool, e->op_types,
 362                                   sizeof *e->op_types * e->allocated_ops);
 363     }
 364
 365   e->op_types[e->n_ops] = type;
 366   return &e->ops[e->n_ops++];
 367 }