/****************************************************************************
* bfs *
* Copyright (C) 2017-2020 Tavian Barnes <tavianator@tavianator.com> *
* *
* Permission to use, copy, modify, and/or distribute this software for any *
* purpose with or without fee is hereby granted. *
* *
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
****************************************************************************/
/**
* The expression optimizer. Different optimization levels are supported:
*
* -O1: basic logical simplifications, like folding (-true -and -foo) to -foo.
*
* -O2: dead code elimination and data flow analysis. struct opt_facts is used
* to record data flow facts that are true at various points of evaluation.
* Specifically, struct opt_facts records the facts that must be true before an
* expression is evaluated (state->facts), and those that must be true after the
* expression is evaluated, given that it returns true (state->facts_when_true)
* or false (state->facts_when_true). Additionally, state->facts_when_impure
* records the possible data flow facts before any expressions with side effects
* are evaluated.
*
* -O3: expression re-ordering to reduce expected cost. In an expression like
* (-foo -and -bar), if both -foo and -bar are pure (no side effects), they can
* be re-ordered to (-bar -and -foo). This is profitable if the expected cost
* is lower for the re-ordered expression, for example if -foo is very slow or
* -bar is likely to return false.
*
* -O4/-Ofast: aggressive optimizations that may affect correctness in corner
* cases. The main effect is to use facts_when_impure to determine if any side-
* effects are reachable at all, and skipping the traversal if not.
*/
#include "opt.h"
#include "color.h"
#include "ctx.h"
#include "diag.h"
#include "eval.h"
#include "expr.h"
#include "pwcache.h"
#include "util.h"
#include <assert.h>
#include <limits.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <unistd.h>
static char *fake_and_arg = "-a";
static char *fake_or_arg = "-o";
static char *fake_not_arg = "!";
/**
* A contrained integer range.
*/
struct range {
/** The (inclusive) minimum value. */
long long min;
/** The (inclusive) maximum value. */
long long max;
};
/** Compute the minimum of two values. */
static long long min_value(long long a, long long b) {
if (a < b) {
return a;
} else {
return b;
}
}
/** Compute the maximum of two values. */
static long long max_value(long long a, long long b) {
if (a > b) {
return a;
} else {
return b;
}
}
/** Constrain the minimum of a range. */
static void constrain_min(struct range *range, long long value) {
range->min = max_value(range->min, value);
}
/** Contrain the maximum of a range. */
static void constrain_max(struct range *range, long long value) {
range->max = min_value(range->max, value);
}
/** Remove a single value from a range. */
static void range_remove(struct range *range, long long value) {
if (range->min == value) {
if (range->min == LLONG_MAX) {
range->max = LLONG_MIN;
} else {
++range->min;
}
}
if (range->max == value) {
if (range->max == LLONG_MIN) {
range->min = LLONG_MAX;
} else {
--range->max;
}
}
}
/** Compute the union of two ranges. */
static void range_union(struct range *result, const struct range *lhs, const struct range *rhs) {
result->min = min_value(lhs->min, rhs->min);
result->max = max_value(lhs->max, rhs->max);
}
/** Check if a range contains no values. */
static bool range_is_impossible(const struct range *range) {
return range->min > range->max;
}
/** Set a range to contain no values. */
static void set_range_impossible(struct range *range) {
range->min = LLONG_MAX;
range->max = LLONG_MIN;
}
/**
* Types of ranges we track.
*/
enum range_type {
/** Search tree depth. */
DEPTH_RANGE,
/** Group ID. */
GID_RANGE,
/** Inode number. */
INUM_RANGE,
/** Hard link count. */
LINKS_RANGE,
/** File size. */
SIZE_RANGE,
/** User ID. */
UID_RANGE,
/** The number of range_types. */
RANGE_TYPES,
};
/**
* A possibly-known value of a predicate.
*/
enum known_pred {
/** The state is impossible to reach. */
PRED_IMPOSSIBLE = -2,
/** The value of the predicate is not known. */
PRED_UNKNOWN = -1,
/** The predicate is known to be false. */
PRED_FALSE = false,