deps/theft/theft.c

#include <string.h>

#include "theft.h"
#include "theft_types_internal.h"
#include "theft_bloom.h"
#include "theft_mt.h"

/* Initialize a theft test runner.
 * BLOOM_BITS sets the size of the table used for detecting
 * combinations of arguments that have already been tested.
 * If 0, a default size will be chosen based on trial count.
 * (This will only be used if all property types have hash
 * callbacks defined.) The bloom filter can also be disabled
 * by setting BLOOM_BITS to THEFT_BLOOM_DISABLE.
 *
 * Returns a NULL if malloc fails or BLOOM_BITS is out of bounds. */
struct theft *theft_init(uint8_t bloom_bits) {
    if ((bloom_bits != 0 && (bloom_bits < THEFT_BLOOM_BITS_MIN))
        || ((bloom_bits > THEFT_BLOOM_BITS_MAX) &&
            bloom_bits != THEFT_BLOOM_DISABLE)) {
        return NULL;
    }

    theft *t = malloc(sizeof(*t));
    if (t == NULL) { return NULL; }
    memset(t, 0, sizeof(*t));

    t->mt = theft_mt_init(DEFAULT_THEFT_SEED);
    if (t->mt == NULL) {
        free(t);
        return NULL;
    } else {
        t->out = stdout;
        t->requested_bloom_bits = bloom_bits;
        return t;
    }
}

/* (Re-)initialize the random number generator with a specific seed. */
void theft_set_seed(struct theft *t, uint64_t seed) {
    t->seed = seed;
    theft_mt_reset(t->mt, seed);
}

/* Get a random 64-bit integer from the test runner's PRNG. */
theft_seed theft_random(struct theft *t) {
    theft_seed ns = (theft_seed)theft_mt_random(t->mt);
    return ns;
}

/* Get a random double from the test runner's PRNG. */
double theft_random_double(struct theft *t) {
    return theft_mt_random_double(t->mt);
}

/* Change T's output stream handle to OUT. (Default: stdout.) */
void theft_set_output_stream(struct theft *t, FILE *out) { t->out = out; }

/* Check if all argument info structs have all required callbacks. */
static bool
check_all_args(struct theft_propfun_info *info, bool *all_hashable) {
    bool ah = true;
    for (int i = 0; i < info->arity; i++) {
        struct theft_type_info *ti = info->type_info[i];
        if (ti->alloc == NULL) { return false; }
        if (ti->hash == NULL) { ah = false; }
    }
    *all_hashable = ah;
    return true;
}

static theft_progress_callback_res
default_progress_cb(struct theft_trial_info *info, void *env) {
    (void)info;
    (void)env;
    return THEFT_PROGRESS_CONTINUE;
}

static void infer_arity(struct theft_propfun_info *info) {
    for (int i = 0; i < THEFT_MAX_ARITY; i++) {
        if (info->type_info[i] == NULL) {
            info->arity = i;
            break;
        }
    }
}

/* Run a series of randomized trials of a property function.
 *
 * Configuration is specified in CFG; many fields are optional.
 * See the type definition in `theft_types.h`. */
theft_run_res
theft_run(struct theft *t, struct theft_cfg *cfg) {
    if (t == NULL || cfg == NULL) {
        return THEFT_RUN_ERROR_BAD_ARGS;
    }

    struct theft_propfun_info info;
    memset(&info, 0, sizeof(info));
    info.name = cfg->name;
    info.fun = cfg->fun;
    memcpy(info.type_info, cfg->type_info, sizeof(info.type_info));
    info.always_seed_count = cfg->always_seed_count;
    info.always_seeds = cfg->always_seeds;

    if (cfg->seed) {
        theft_set_seed(t, cfg->seed);
    } else {
        theft_set_seed(t, DEFAULT_THEFT_SEED);
    }

    if (cfg->trials == 0) { cfg->trials = THEFT_DEF_TRIALS; }

    return theft_run_internal(t, &info, cfg->trials, cfg->progress_cb,
        cfg->env, cfg->report);
}

/* Actually run the trials, with all arguments made explicit. */
static theft_run_res
theft_run_internal(struct theft *t, struct theft_propfun_info *info,
        int trials, theft_progress_cb *cb, void *env,
        struct theft_trial_report *r) {

    struct theft_trial_report fake_report;
    if (r == NULL) { r = &fake_report; }
    memset(r, 0, sizeof(*r));

    infer_arity(info);
    if (info->arity == 0) {
        return THEFT_RUN_ERROR_BAD_ARGS;
    }

    if (t == NULL || info == NULL || info->fun == NULL
        || info->arity == 0) {
        return THEFT_RUN_ERROR_BAD_ARGS;
    }

    bool all_hashable = false;
    if (!check_all_args(info, &all_hashable)) {
        return THEFT_RUN_ERROR_MISSING_CALLBACK;
    }

    if (cb == NULL) { cb = default_progress_cb; }

    /* If all arguments are hashable, then attempt to use
     * a bloom filter to avoid redundant checking. */
    if (all_hashable) {
        if (t->requested_bloom_bits == 0) {
            t->requested_bloom_bits = theft_bloom_recommendation(trials);
        }
        if (t->requested_bloom_bits != THEFT_BLOOM_DISABLE) {
            t->bloom = theft_bloom_init(t->requested_bloom_bits);
        }
    }

    theft_seed seed = t->seed;
    theft_seed initial_seed = t->seed;
    int always_seeds = info->always_seed_count;
    if (info->always_seeds == NULL) { always_seeds = 0; }

    void *args[THEFT_MAX_ARITY];

    theft_progress_callback_res cres = THEFT_PROGRESS_CONTINUE;

    for (int trial = 0; trial < trials; trial++) {
        memset(args, 0xFF, sizeof(args));
        if (cres == THEFT_PROGRESS_HALT) { break; }

        /* If any seeds to always run were specified, use those before
         * reverting to the specified starting seed. */
        if (trial < always_seeds) {
            seed = info->always_seeds[trial];
        } else if ((always_seeds > 0) && (trial == always_seeds)) {
            seed = initial_seed;
        }

        struct theft_trial_info ti = {
            .name = info->name,
            .trial = trial,
            .seed = seed,
            .arity = info->arity,
            .args = args
        };

        theft_set_seed(t, seed);
        all_gen_res_t gres = gen_all_args(t, info, seed, args, env);
        switch (gres) {
        case ALL_GEN_SKIP:
            /* skip generating these args */
            ti.status = THEFT_TRIAL_SKIP;
            r->skip++;
            cres = cb(&ti, env);
            break;
        case ALL_GEN_DUP:
            /* skip these args -- probably already tried */
            ti.status = THEFT_TRIAL_DUP;
            r->dup++;
            cres = cb(&ti, env);
            break;
        default:
        case ALL_GEN_ERROR:
            /* Error while generating args */
            ti.status = THEFT_TRIAL_ERROR;
            cres = cb(&ti, env);
            return THEFT_RUN_ERROR;
        case ALL_GEN_OK:
            /* (Extracted function to avoid deep nesting here.) */
            if (!run_trial(t, info, args, cb, env, r, &ti, &cres)) {
                return THEFT_RUN_ERROR;
            }
        }

        free_args(info, args, env);

        /* Restore last known seed and generate next. */
        theft_set_seed(t, seed);
        seed = theft_random(t);
    }

    if (r->fail > 0) {
        return THEFT_RUN_FAIL;
    } else {
        return THEFT_RUN_PASS;
    }
}

/* Now that arguments have been generated, run the trial and update
 * counters, call cb with results, etc. */
static bool run_trial(struct theft *t, struct theft_propfun_info *info,
        void **args, theft_progress_cb *cb, void *env,
        struct theft_trial_report *r, struct theft_trial_info *ti,
        theft_progress_callback_res *cres) {
    if (t->bloom) { mark_called(t, info, args, env); }
    theft_trial_res tres = call_fun(info, args);
    ti->status = tres;
    switch (tres) {
    case THEFT_TRIAL_PASS:
        r->pass++;
        *cres = cb(ti, env);
        break;
    case THEFT_TRIAL_FAIL:
        if (!attempt_to_shrink(t, info, args, env)) {
            ti->status = THEFT_TRIAL_ERROR;
            *cres = cb(ti, env);
            return false;
        }
        r->fail++;
        *cres = report_on_failure(t, info, ti, cb, env);
        break;
    case THEFT_TRIAL_SKIP:
        *cres = cb(ti, env);
        r->skip++;
        break;
    case THEFT_TRIAL_DUP:
        /* user callback should not return this; fall through */
    case THEFT_TRIAL_ERROR:
        *cres = cb(ti, env);
        free_args(info, args, env);
        return false;
    }
    return true;
}

static void free_args(struct theft_propfun_info *info,
        void **args, void *env) {
    for (int i = 0; i < info->arity; i++) {
        theft_free_cb *fcb = info->type_info[i]->free;
        if (fcb && args[i] != THEFT_SKIP) {
            fcb(args[i], env);
        }
    }
}

void theft_free(struct theft *t) {
    if (t->bloom) {
        theft_bloom_dump(t->bloom);
        theft_bloom_free(t->bloom);
        t->bloom = NULL;
    }
    theft_mt_free(t->mt);
    free(t);
}

/* Actually call the property function. Its number of arguments is not
 * constrained by the typedef, but will be defined at the call site
 * here. (If info->arity is wrong, it will probably crash.) */
static theft_trial_res
call_fun(struct theft_propfun_info *info, void **args) {
    theft_trial_res res = THEFT_TRIAL_ERROR;
    switch (info->arity) {
    case 1:
        res = info->fun(args[0]);
        break;
    case 2:
        res = info->fun(args[0], args[1]);
        break;
    case 3:
        res = info->fun(args[0], args[1], args[2]);
        break;
    case 4:
        res = info->fun(args[0], args[1], args[2], args[3]);
        break;
    case 5:
        res = info->fun(args[0], args[1], args[2], args[3], args[4]);
        break;
    case 6:
        res = info->fun(args[0], args[1], args[2], args[3], args[4],
            args[5]);
        break;
    case 7:
        res = info->fun(args[0], args[1], args[2], args[3], args[4],
            args[5], args[6]);
        break;
    case 8:
        res = info->fun(args[0], args[1], args[2], args[3], args[4],
            args[5], args[6], args[7]);
        break;
    case 9:
        res = info->fun(args[0], args[1], args[2], args[3], args[4],
            args[5], args[6], args[7], args[8]);
        break;
    case 10:
        res = info->fun(args[0], args[1], args[2], args[3], args[4],
            args[5], args[6], args[7], args[8], args[9]);
        break;
    /* ... */
    default:
        return THEFT_TRIAL_ERROR;
    }
    return res;
}

/* Attempt to instantiate arguments, starting with the current seed. */
static all_gen_res_t
gen_all_args(theft *t, struct theft_propfun_info *info,
        theft_seed seed, void *args[THEFT_MAX_ARITY], void *env) {
    for (int i = 0; i < info->arity; i++) {
        struct theft_type_info *ti = info->type_info[i];
        void *p = ti->alloc(t, seed, env);
        if (p == THEFT_SKIP || p == THEFT_ERROR) {
            for (int j = 0; j < i; j++) {
                ti->free(args[j], env);
            }
            if (p == THEFT_SKIP) {
                return ALL_GEN_SKIP;
            } else {
                return ALL_GEN_ERROR;
            }
        } else {
            args[i] = p;
        }
        seed = theft_random(t);
    }

    /* check bloom filter */
    if (t->bloom && check_called(t, info, args, env)) {
        return ALL_GEN_DUP;
    }

    return ALL_GEN_OK;
}

/* Attempt to simplify all arguments, breadth first. Continue as long as
 * progress is made, i.e., until a local minima is reached. */
static bool
attempt_to_shrink(theft *t, struct theft_propfun_info *info,
        void *args[], void *env) {
    bool progress = false;
    do {
        progress = false;
        for (int ai = 0; ai < info->arity; ai++) {
            struct theft_type_info *ti = info->type_info[ai];
            if (ti->shrink) {
                /* attempt to simplify this argument by one step */
                shrink_res rres = attempt_to_shrink_arg(t, info, args, env, ai);
                switch (rres) {
                case SHRINK_OK:
                    progress = true;
                    break;
                case SHRINK_DEAD_END:
                    break;
                default:
                case SHRINK_ERROR:
                    return false;
                }
            }
        }
    } while (progress);

    return true;
}

/* Simplify an argument by trying all of its simplification tactics, in
 * order, and checking whether the property still fails. If it passes,
 * then revert the simplification and try another tactic.
 *
 * If the bloom filter is being used (i.e., if all arguments have hash
 * callbacks defined), then use it to skip over areas of the state
 * space that have probably already been tried. */
static shrink_res
attempt_to_shrink_arg(theft *t, struct theft_propfun_info *info,
        void *args[], void *env, int ai) {
    struct theft_type_info *ti = info->type_info[ai];

    for (uint32_t tactic = 0; tactic < THEFT_MAX_TACTICS; tactic++) {
        void *cur = args[ai];
        void *nv = ti->shrink(cur, tactic, env);
        if (nv == THEFT_NO_MORE_TACTICS) {
            return SHRINK_DEAD_END;
        } else if (nv == THEFT_ERROR) {
            return SHRINK_ERROR;
        } else if (nv == THEFT_DEAD_END) {
            continue;   /* try next tactic */
        }

        args[ai] = nv;
        if (t->bloom) {
            if (check_called(t, info, args, env)) {
                /* probably redundant */
                if (ti->free) { ti->free(nv, env); }
                args[ai] = cur;
                continue;
            } else {
                mark_called(t, info, args, env);
            }
        }
        theft_trial_res res = call_fun(info, args);

        switch (res) {
        case THEFT_TRIAL_PASS:
        case THEFT_TRIAL_SKIP:
            /* revert */
            args[ai] = cur;
            if (ti->free) { ti->free(nv, env); }
            break;
        case THEFT_TRIAL_FAIL:
            if (ti->free) { ti->free(cur, env); }
            return SHRINK_OK;
        case THEFT_TRIAL_DUP:  /* user callback should not return this */
        case THEFT_TRIAL_ERROR:
            return SHRINK_ERROR;
        }
    }
    (void)t;
    return SHRINK_DEAD_END;
}

/* Populate a buffer with hashes of all the arguments. */
static void get_arg_hash_buffer(theft_hash *buffer,
        struct theft_propfun_info *info, void **args, void *env) {
    for (int i = 0; i < info->arity; i++) {
        buffer[i] = info->type_info[i]->hash(args[i], env);
    }
}

/* Mark the tuple of argument instances as called in the bloom filter. */
static void mark_called(theft *t, struct theft_propfun_info *info,
        void **args, void *env) {
    theft_hash buffer[THEFT_MAX_ARITY];
    get_arg_hash_buffer(buffer, info, args, env);
    theft_bloom_mark(t->bloom, (uint8_t *)buffer,
        info->arity * sizeof(theft_hash));
}

/* Check if this combination of argument instances has been called. */
static bool check_called(theft *t, struct theft_propfun_info *info,
        void **args, void *env) {
    theft_hash buffer[THEFT_MAX_ARITY];
    get_arg_hash_buffer(buffer, info, args, env);
    return theft_bloom_check(t->bloom, (uint8_t *)buffer,
        info->arity * sizeof(theft_hash));
}

/* Print info about a failure. */
static theft_progress_callback_res report_on_failure(theft *t,
        struct theft_propfun_info *info,
        struct theft_trial_info *ti, theft_progress_cb *cb, void *env) {
    static theft_progress_callback_res cres;

    int arity = info->arity;
    fprintf(t->out, "\n\n -- Counter-Example: %s\n",
        info->name ? info-> name : "");
    fprintf(t->out, "    Trial %u, Seed 0x%016llx\n", ti->trial,
        (uint64_t)ti->seed);
    for (int i = 0; i < arity; i++) {
        theft_print_cb *print = info->type_info[i]->print;
        if (print) {
            fprintf(t->out, "    Argument %d:\n", i);
            print(t->out, ti->args[i], env);
            fprintf(t->out, "\n");
        }
   }

    cres = cb(ti, env);
    return cres;
}