X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flanguage%2Fexpressions%2Foptimize.c;h=7d683d0181f55d5dcff4355eaadc0d4548d76c5f;hb=6d03bf519dac51a4869f9cc3ef71fef5778f1eed;hp=b280b6d737485527d92e5fde4b6d48af97d63e99;hpb=dcf9b154cbcaa35c3d8459a201b77eec8bcb30bd;p=pspp diff --git a/src/language/expressions/optimize.c b/src/language/expressions/optimize.c index b280b6d737..7d683d0181 100644 --- a/src/language/expressions/optimize.c +++ b/src/language/expressions/optimize.c @@ -1,51 +1,51 @@ -/* PSPP - computes sample statistics. - Copyright (C) 1997-9, 2000 Free Software Foundation, Inc. - Written by Ben Pfaff . +/* PSPP - a program for statistical analysis. + Copyright (C) 1997-9, 2000, 2011 Free Software Foundation, Inc. - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of the - License, or (at your option) any later version. + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - This program is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - 02110-1301, USA. */ + along with this program. If not, see . */ #include -#include "private.h" + +#include "language/expressions/private.h" + #include #include #include #include -#include "alloc.h" -#include "calendar.h" -#include "data-in.h" -#include "message.h" + +#include "data/calendar.h" +#include "data/data-in.h" +#include "data/variable.h" #include "evaluate.h" -#include "helpers.h" -#include "misc.h" -#include "pool.h" -#include "public.h" -#include "str.h" -#include "variable.h" - -static union any_node *evaluate_tree (struct composite_node *, - struct expression *); -static union any_node *optimize_tree (union any_node *, struct expression *); - -union any_node * -expr_optimize (union any_node *node, struct expression *e) +#include "language/expressions/helpers.h" +#include "language/expressions/public.h" +#include "libpspp/assertion.h" +#include "libpspp/message.h" +#include "libpspp/misc.h" +#include "libpspp/pool.h" +#include "libpspp/str.h" + +#include "gl/xalloc.h" + +static struct expr_node *evaluate_tree (struct expr_node *, struct expression *); +static struct expr_node *optimize_tree (struct expr_node *, struct expression *); + +struct expr_node * +expr_optimize (struct expr_node *node, struct expression *e) { - int nonconst_cnt = 0; /* Number of nonconstant children. */ - int sysmis_cnt = 0; /* Number of system-missing children. */ - struct operation *op; - struct composite_node *c; + int n_nonconst = 0; /* Number of nonconstant children. */ + int n_sysmis = 0; /* Number of system-missing children. */ + const struct operation *op; int i; /* We can't optimize an atom. */ @@ -53,54 +53,60 @@ expr_optimize (union any_node *node, struct expression *e) return node; /* Start by optimizing all the children. */ - c = &node->composite; - for (i = 0; i < c->arg_cnt; i++) + for (i = 0; i < node->n_args; i++) { - c->args[i] = expr_optimize (c->args[i], e); - if (c->args[i]->type == OP_number) + node->args[i] = expr_optimize (node->args[i], e); + if (node->args[i]->type == OP_number) { - if (c->args[i]->number.n == SYSMIS) - sysmis_cnt++; + if (node->args[i]->number == SYSMIS) + n_sysmis++; } - if (!is_atom (c->args[i]->type)) - nonconst_cnt++; + if (!is_atom (node->args[i]->type)) + n_nonconst++; } - op = &operations[c->type]; - if (sysmis_cnt && (op->flags & OPF_ABSORB_MISS) == 0) + op = &operations[node->type]; + + struct expr_node *new; + if (n_sysmis && (op->flags & OPF_ABSORB_MISS) == 0) { /* Most operations produce SYSMIS given any SYSMIS argument. */ assert (op->returns == OP_number || op->returns == OP_boolean); - if (op->returns == OP_number) - return expr_allocate_number (e, SYSMIS); - else - return expr_allocate_boolean (e, SYSMIS); + new = (op->returns == OP_number + ? expr_allocate_number (e, SYSMIS) + : expr_allocate_boolean (e, SYSMIS)); } - else if (!nonconst_cnt && (op->flags & OPF_NONOPTIMIZABLE) == 0) + else if (!n_nonconst && (op->flags & OPF_NONOPTIMIZABLE) == 0) { /* Evaluate constant expressions. */ - return evaluate_tree (&node->composite, e); + new = evaluate_tree (node, e); } - else + else { /* A few optimization possibilities are still left. */ - return optimize_tree (node, e); + new = optimize_tree (node, e); + } + + if (new != node && !new->location) + { + const struct msg_location *loc = expr_location (e, node); + new->location = CONST_CAST (struct msg_location *, loc); } + return new; } static int -eq_double (union any_node *node, double n) +eq_double (struct expr_node *node, double n) { - return node->type == OP_number && node->number.n == n; + return node->type == OP_number && node->number == n; } -static union any_node * -optimize_tree (union any_node *node, struct expression *e) +static struct expr_node * +optimize_tree (struct expr_node *n, struct expression *e) { - struct composite_node *n = &node->composite; - assert (is_composite (node->type)); + assert (is_composite (n->type)); /* If you add to these optimizations, please also add a correctness test in tests/expressions/expressions.sh. */ @@ -108,7 +114,7 @@ optimize_tree (union any_node *node, struct expression *e) /* x+0, x-0, 0+x => x. */ if ((n->type == OP_ADD || n->type == OP_SUB) && eq_double (n->args[1], 0.)) return n->args[0]; - else if (n->type == OP_ADD && eq_double (n->args[0], 0.)) + else if (n->type == OP_ADD && eq_double (n->args[0], 0.)) return n->args[1]; /* x*1, x/1, 1*x => x. */ @@ -117,7 +123,7 @@ optimize_tree (union any_node *node, struct expression *e) return n->args[0]; else if (n->type == OP_MUL && eq_double (n->args[0], 1.)) return n->args[1]; - + /* 0*x, 0/x, x*0, MOD(0,x) => 0. */ else if (((n->type == OP_MUL || n->type == OP_DIV || n->type == OP_MOD_nn) && eq_double (n->args[0], 0.)) @@ -127,147 +133,139 @@ optimize_tree (union any_node *node, struct expression *e) /* x**1 => x. */ else if (n->type == OP_POW && eq_double (n->args[1], 1)) return n->args[0]; - + /* x**2 => SQUARE(x). */ else if (n->type == OP_POW && eq_double (n->args[1], 2)) return expr_allocate_unary (e, OP_SQUARE, n->args[0]); /* Otherwise, nothing to do. */ else - return node; -} - -static double get_number_arg (struct composite_node *, size_t arg_idx); -static double *get_number_args (struct composite_node *, - size_t arg_idx, size_t arg_cnt, - struct expression *); -static struct fixed_string get_string_arg (struct composite_node *, - size_t arg_idx); -static struct fixed_string *get_string_args (struct composite_node *, - size_t arg_idx, size_t arg_cnt, - struct expression *); -static const struct fmt_spec *get_format_arg (struct composite_node *, - size_t arg_idx); - -static union any_node * -evaluate_tree (struct composite_node *node, struct expression *e) -{ - switch (node->type) - { -#include "optimize.inc" - - default: - assert (0); - } - - /* Not reached. */ - assert (0); - abort (); + return n; } static double -get_number_arg (struct composite_node *c, size_t arg_idx) +get_number_arg (struct expr_node *n, size_t arg_idx) { - assert (arg_idx < c->arg_cnt); - assert (c->args[arg_idx]->type == OP_number - || c->args[arg_idx]->type == OP_boolean); - return c->args[arg_idx]->number.n; + assert (arg_idx < n->n_args); + assert (n->args[arg_idx]->type == OP_number + || n->args[arg_idx]->type == OP_boolean + || n->args[arg_idx]->type == OP_integer); + return n->args[arg_idx]->number; } static double * -get_number_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt, - struct expression *e) +get_number_args (struct expr_node *n, size_t arg_idx, size_t n_args, + struct expression *e) { - double *d; - size_t i; - - d = pool_alloc (e->expr_pool, sizeof *d * arg_cnt); - for (i = 0; i < arg_cnt; i++) - d[i] = get_number_arg (c, i + arg_idx); + double *d = pool_alloc (e->expr_pool, sizeof *d * n_args); + for (size_t i = 0; i < n_args; i++) + d[i] = get_number_arg (n, i + arg_idx); return d; } -static struct fixed_string -get_string_arg (struct composite_node *c, size_t arg_idx) +static struct substring +get_string_arg (struct expr_node *n, size_t arg_idx) { - assert (arg_idx < c->arg_cnt); - assert (c->args[arg_idx]->type == OP_string); - return c->args[arg_idx]->string.s; + assert (arg_idx < n->n_args); + assert (n->args[arg_idx]->type == OP_string); + return n->args[arg_idx]->string; } -static struct fixed_string * -get_string_args (struct composite_node *c, size_t arg_idx, size_t arg_cnt, - struct expression *e) +static struct substring * +get_string_args (struct expr_node *n, size_t arg_idx, size_t n_args, + struct expression *e) { - struct fixed_string *s; + struct substring *s; size_t i; - s = pool_alloc (e->expr_pool, sizeof *s * arg_cnt); - for (i = 0; i < arg_cnt; i++) - s[i] = get_string_arg (c, i + arg_idx); + s = pool_alloc (e->expr_pool, sizeof *s * n_args); + for (i = 0; i < n_args; i++) + s[i] = get_string_arg (n, i + arg_idx); return s; } static const struct fmt_spec * -get_format_arg (struct composite_node *c, size_t arg_idx) +get_format_arg (struct expr_node *n, size_t arg_idx) +{ + assert (arg_idx < n->n_args); + assert (n->args[arg_idx]->type == OP_ni_format + || n->args[arg_idx]->type == OP_no_format); + return &n->args[arg_idx]->format; +} + +static const struct expr_node * +get_expr_node_arg (struct expr_node *n, size_t arg_idx) { - assert (arg_idx < c->arg_cnt); - assert (c->args[arg_idx]->type == OP_ni_format - || c->args[arg_idx]->type == OP_no_format); - return &c->args[arg_idx]->format.f; + assert (arg_idx < n->n_args); + assert (n->args[arg_idx]->type == OP_expr_node); + return n->args[arg_idx]->expr_node; +} + +static struct expr_node * +evaluate_tree (struct expr_node *node, struct expression *e) +{ + switch (node->type) + { +#include "optimize.inc" + + default: + NOT_REACHED (); + } + + NOT_REACHED (); } /* Expression flattening. */ static union operation_data *allocate_aux (struct expression *, operation_type); -static void flatten_node (union any_node *, struct expression *); +static void flatten_node (struct expr_node *, struct expression *); static void -emit_operation (struct expression *e, operation_type type) +emit_operation (struct expression *e, operation_type type) { allocate_aux (e, OP_operation)->operation = type; } static void -emit_number (struct expression *e, double n) +emit_number (struct expression *e, double n) { allocate_aux (e, OP_number)->number = n; } static void -emit_string (struct expression *e, struct fixed_string s) +emit_string (struct expression *e, struct substring s) { allocate_aux (e, OP_string)->string = s; } static void -emit_format (struct expression *e, const struct fmt_spec *f) +emit_format (struct expression *e, const struct fmt_spec *f) { allocate_aux (e, OP_format)->format = pool_clone (e->expr_pool, f, sizeof *f); } static void -emit_variable (struct expression *e, struct variable *v) +emit_variable (struct expression *e, const struct variable *v) { allocate_aux (e, OP_variable)->variable = v; } static void -emit_vector (struct expression *e, const struct vector *v) +emit_vector (struct expression *e, const struct vector *v) { allocate_aux (e, OP_vector)->vector = v; } static void -emit_integer (struct expression *e, int i) +emit_integer (struct expression *e, int i) { allocate_aux (e, OP_integer)->integer = i; } -void -expr_flatten (union any_node *n, struct expression *e) +void +expr_flatten (struct expr_node *n, struct expression *e) { flatten_node (n, e); e->type = expr_node_returns (n); @@ -276,19 +274,19 @@ expr_flatten (union any_node *n, struct expression *e) } static void -flatten_atom (union any_node *n, struct expression *e) +flatten_atom (struct expr_node *n, struct expression *e) { - switch (n->type) + switch (n->type) { case OP_number: case OP_boolean: emit_operation (e, OP_number); - emit_number (e, n->number.n); + emit_number (e, n->number); break; case OP_string: emit_operation (e, OP_string); - emit_string (e, n->string.s); + emit_string (e, n->string); break; case OP_num_var: @@ -297,50 +295,55 @@ flatten_atom (union any_node *n, struct expression *e) case OP_no_format: case OP_ni_format: case OP_pos_int: + case OP_expr_node: /* These are passed as aux data following the operation. */ break; default: - abort (); + NOT_REACHED (); } } static void -flatten_composite (union any_node *n, struct expression *e) +flatten_composite (struct expr_node *n, struct expression *e) { - struct operation *op = &operations[n->type]; + const struct operation *op = &operations[n->type]; size_t i; - - for (i = 0; i < n->composite.arg_cnt; i++) - flatten_node (n->composite.args[i], e); + + for (i = 0; i < n->n_args; i++) + flatten_node (n->args[i], e); if (n->type != OP_BOOLEAN_TO_NUM) emit_operation (e, n->type); - for (i = 0; i < n->composite.arg_cnt; i++) + for (i = 0; i < n->n_args; i++) { - union any_node *arg = n->composite.args[i]; - switch (arg->type) + struct expr_node *arg = n->args[i]; + switch (arg->type) { case OP_num_var: case OP_str_var: - emit_variable (e, arg->variable.v); + emit_variable (e, arg->variable); break; case OP_vector: - emit_vector (e, arg->vector.v); + emit_vector (e, arg->vector); break; case OP_ni_format: case OP_no_format: - emit_format (e, &arg->format.f); + emit_format (e, &arg->format); break; case OP_pos_int: - emit_integer (e, arg->integer.i); + emit_integer (e, arg->integer); + break; + + case OP_expr_node: + allocate_aux (e, OP_expr_node)->expr_node = arg->expr_node; break; - + default: /* Nothing to do. */ break; @@ -348,13 +351,15 @@ flatten_composite (union any_node *n, struct expression *e) } if (op->flags & OPF_ARRAY_OPERAND) - emit_integer (e, n->composite.arg_cnt - op->arg_cnt + 1); + emit_integer (e, n->n_args - op->n_args + 1); if (op->flags & OPF_MIN_VALID) - emit_integer (e, n->composite.min_valid); + emit_integer (e, n->min_valid); + if (op->flags & OPF_EXPR_NODE) + allocate_aux (e, OP_expr_node)->expr_node = n; } void -flatten_node (union any_node *n, struct expression *e) +flatten_node (struct expr_node *n, struct expression *e) { assert (is_operation (n->type)); @@ -362,21 +367,22 @@ flatten_node (union any_node *n, struct expression *e) flatten_atom (n, e); else if (is_composite (n->type)) flatten_composite (n, e); - else - abort (); + else + NOT_REACHED (); } static union operation_data * -allocate_aux (struct expression *e, operation_type type) +allocate_aux (struct expression *e, operation_type type) { - if (e->op_cnt >= e->op_cap) + if (e->n_ops >= e->allocated_ops) { - e->op_cap = (e->op_cap + 8) * 3 / 2; - e->ops = pool_realloc (e->expr_pool, e->ops, sizeof *e->ops * e->op_cap); + e->allocated_ops = (e->allocated_ops + 8) * 3 / 2; + e->ops = pool_realloc (e->expr_pool, e->ops, + sizeof *e->ops * e->allocated_ops); e->op_types = pool_realloc (e->expr_pool, e->op_types, - sizeof *e->op_types * e->op_cap); + sizeof *e->op_types * e->allocated_ops); } - e->op_types[e->op_cnt] = type; - return &e->ops[e->op_cnt++]; + e->op_types[e->n_ops] = type; + return &e->ops[e->n_ops++]; }