Merge topic branch t/ff-compat into master

[paraslash.git] / mood.c

/* Copyright (C) 2007 Andre Noll <maan@tuebingen.mpg.de>, see file COPYING. */

/** \file mood.c Paraslash's mood handling functions. */

#include <regex.h>
#include <osl.h>
#include <lopsub.h>

#include "para.h"
#include "error.h"
#include "string.h"
#include "afh.h"
#include "afs.h"
#include "list.h"
#include "mood.h"

/*
 * Mood parser API. It's overkill to have an own header file for
 * these declarations as they are only needed in this .c file.
 */
struct mp_context;
int mp_init(const char *definition, int nbytes, struct mp_context **result,
                 char **errmsg);
bool mp_eval_row(const struct osl_row *aft_row, struct mp_context *ctx);
void mp_shutdown(struct mp_context *ctx);

/**
 * Contains statistical data of the currently admissible audio files.
 *
 * It is used to assign normalized score values to each admissible audio file.
 */
struct afs_statistics {
        /** Sum of num played over all admissible files. */
        int64_t num_played_sum;
        /** Sum of last played times over all admissible files. */
        int64_t last_played_sum;
        /** Quadratic deviation of num played count. */
        int64_t num_played_qd;
        /** Quadratic deviation of last played time. */
        int64_t last_played_qd;
        /** Correction factor for the num played score. */
        int64_t num_played_correction;
        /** Correction factor for the last played score. */
        int64_t last_played_correction;
        /** Common divisor of the correction factors. */
        int64_t normalization_divisor;
        /** Number of admissible files */
        unsigned num;
};
static struct afs_statistics statistics = {.normalization_divisor = 1};

struct mood {
        /** The name of this mood. */
        char *name;
        /** Info for the bison parser. */
        struct mp_context *parser_context;
};

/*
 * If current_mood is NULL then no mood is currently open. If
 * current_mood->name is NULL, the dummy mood is currently open.
 */
static struct mood *current_mood;

/*
 * Find the position of the most-significant set bit.
 *
 * Copied and slightly adapted from the linux source tree, version 4.9.39
 * (2017-07).
 */
__a_const static uint32_t fls64(uint64_t v)
{
        int n = 63;
        const uint64_t ones = ~(uint64_t)0U;

        if ((v & (ones << 32)) == 0) {
                n -= 32;
                v <<= 32;
        }
        if ((v & (ones << (64 - 16))) == 0) {
                n -= 16;
                v <<= 16;
        }
        if ((v & (ones << (64 - 8))) == 0) {
                n -= 8;
                v <<= 8;
        }
        if ((v & (ones << (64 - 4))) == 0) {
                n -= 4;
                v <<= 4;
        }
        if ((v & (ones << (64 - 2))) == 0) {
                n -= 2;
                v <<= 2;
        }
        if ((v & (ones << (64 - 1))) == 0)
                n -= 1;
        return n;
}

/*
 * Compute the integer square root floor(sqrt(x)).
 *
 * Taken 2007 from the linux source tree.
 */
__a_const static uint64_t int_sqrt(uint64_t x)
{
        uint64_t op = x, res = 0, one = 1;

        one = one << (fls64(x) & ~one);
        while (one != 0) {
                if (op >= res + one) {
                        op = op - (res + one);
                        res = res + 2 * one;
                }
                res /= 2;
                one /= 4;
        }
        return res;
}

/* returns 1 if row admissible, 0 if not, negative on errors */
static int row_is_admissible(const struct osl_row *aft_row, struct mood *m)
{
        if (!m)
                return -E_NO_MOOD;
        return mp_eval_row(aft_row, m->parser_context);
}

static void destroy_mood(struct mood *m)
{
        if (!m)
                return;
        mp_shutdown(m->parser_context);
        free(m->name);
        free(m);
}

static struct mood *alloc_new_mood(const char *name)
{
        struct mood *m = para_calloc(sizeof(struct mood));
        if (name)
                m->name = para_strdup(name);
        return m;
}

static int load_mood(const struct osl_row *mood_row, struct mood **m,
                char **errmsg)
{
        char *mood_name;
        struct osl_object mood_def;
        int ret;

        ret = mood_get_name_and_def_by_row(mood_row, &mood_name, &mood_def);
        if (ret < 0) {
                if (errmsg)
                        *errmsg = make_message(
                                "could not read mood definition");
                return ret;
        }
        assert(*mood_name);
        *m = alloc_new_mood(mood_name);
        PARA_INFO_LOG("opening mood %s\n", mood_name);
        ret = mp_init(mood_def.data, mood_def.size, &(*m)->parser_context, errmsg);
        osl_close_disk_object(&mood_def);
        if (ret < 0)
                destroy_mood(*m);
        return ret;
}

static int check_mood(struct osl_row *mood_row, void *data)
{
        struct para_buffer *pb = data;
        char *mood_name, *errmsg;
        struct osl_object mood_def;
        struct mood *m;
        int ret = mood_get_name_and_def_by_row(mood_row, &mood_name, &mood_def);

        if (ret < 0) {
                para_printf(pb, "cannot read mood\n");
                return ret;
        }
        if (!*mood_name) /* ignore dummy row */
                goto out;
        m = alloc_new_mood("check");
        ret = mp_init(mood_def.data, mood_def.size, &m->parser_context,
                &errmsg);
        if (ret < 0) {
                para_printf(pb, "%s: %s\n", mood_name, errmsg);
                free(errmsg);
                para_printf(pb, "%s\n", para_strerror(-ret));
        } else
                destroy_mood(m);
        ret = 1; /* don't fail the loop on invalid mood definitions */
out:
        osl_close_disk_object(&mood_def);
        return ret;
}

/**
 * Check all moods for syntax errors.
 *
 * \param aca Only ->pbout is used for diagnostics.
 *
 * \return Negative on fatal errors. Inconsistent mood definitions are not
 * considered an error.
 */
int mood_check_callback(struct afs_callback_arg *aca)
{
        para_printf(&aca->pbout, "checking moods...\n");
        return osl(osl_rbtree_loop(moods_table, BLOBCOL_ID, &aca->pbout,
                check_mood));
}

/*
 * The normalized num_played and last_played values are defined as
 *
 *      nn := -(np - mean_n) / sigma_n and nl := -(lp - mean_l) / sigma_l
 *
 *  For a (hypothetical) file with np = 0 and lp = now we thus have
 *
 *      nn =  mean_n / sigma_n =: hn > 0
 *      nl = -(now - mean_l) / sigma_l =: hl < 0
 *
 * We design the score function so that both contributions get the same
 * weight. Define the np and lp score of an arbitrary file as
 *
 *      sn := nn * -hl and sl := nl * hn
 *
 * Example:
 *      num_played mean/sigma: 87/14
 *      last_played mean/sigma: 45/32 days
 *
 *      We have hn = 87 / 14 = 6.21 and hl = -45 / 32 = -1.41. Multiplying
 *      nn of every file with the correction factor 1.41 and nl with
 *      6.21 makes the weight of the two contributions equal.
 *
 * The total score s := sn + sl has the representation
 *
 *      s = -cn * (np - mean_n) - cl * (lp - mean_l)
 *
 * with positive correction factors
 *
 *      cn = (now - mean_l) / (sqrt(ql) * sqrt(qn) / n)
 *      cl = mean_n / (sqrt(ql) * sqrt(qn) / n)
 *
 * where ql and qn are the quadratic deviations stored in the statistics
 * structure and n is the number of admissible files. To avoid integer
 * overflows and rounding errors we store the common divisor of the
 * correction factors separately.
 */
static int64_t normalized_value(int64_t x, int64_t n, int64_t sum, int64_t qd)
{
        if (!n || !qd)
                return 0;
        return 100 * (n * x - sum) / (int64_t)int_sqrt(n) / (int64_t)int_sqrt(qd);
}

static long compute_score(struct afs_info *afsi)
{
        long score = -normalized_value(afsi->num_played, statistics.num,
                statistics.num_played_sum, statistics.num_played_qd);
        score -= normalized_value(afsi->last_played, statistics.num,
                statistics.last_played_sum, statistics.last_played_qd);
        return score / 2;
}

static int add_afs_statistics(const struct osl_row *row)
{
        uint64_t n, x, s, q;
        struct afs_info afsi;
        int ret;

        ret = get_afsi_of_row(row, &afsi);
        if (ret < 0)
                return ret;
        n = statistics.num;
        x = afsi.last_played;
        s = statistics.last_played_sum;
        if (n > 0) {
                q = (x > s / n)? x - s / n : s / n - x;
                statistics.last_played_qd += q * q * n / (n + 1);
        }
        statistics.last_played_sum += x;

        x = afsi.num_played;
        s = statistics.num_played_sum;
        if (n > 0) {
                q = (x > s / n)? x - s / n : s / n - x;
                statistics.num_played_qd += q * q * n / (n + 1);
        }
        statistics.num_played_sum += x;
        statistics.num++;
        return 1;
}

static int del_afs_statistics(const struct osl_row *row)
{
        uint64_t n, s, q, a, new_s;
        struct afs_info afsi;
        int ret;
        ret = get_afsi_of_row(row, &afsi);
        if (ret < 0)
                return ret;
        n = statistics.num;
        assert(n);
        if (n == 1) {
                memset(&statistics, 0, sizeof(statistics));
                statistics.normalization_divisor = 1;
                return 1;
        }

        s = statistics.last_played_sum;
        q = statistics.last_played_qd;
        a = afsi.last_played;
        new_s = s - a;
        statistics.last_played_sum = new_s;
        statistics.last_played_qd = q + s * s / n - a * a
                - new_s * new_s / (n - 1);

        s = statistics.num_played_sum;
        q = statistics.num_played_qd;
        a = afsi.num_played;
        new_s = s - a;
        statistics.num_played_sum = new_s;
        statistics.num_played_qd = q + s * s / n - a * a
                - new_s * new_s / (n - 1);

        statistics.num--;
        return 1;
}

/*
 * At mood open time we determine the set of admissible files for the given
 * mood where each file is identified by a pointer to a row of the audio file
 * table. In the first pass the pointers are added to a temporary array and
 * statistics are computed. When all admissible files have been processed in
 * this way, the score of each admissible file is computed and the (row, score)
 * pair is added to the score table. This has to be done in a second pass
 * since the score depends on the statistics. Finally, the array is freed.
 */
struct admissible_array {
        /** Files are admissible wrt. this mood. */
        struct mood *m;
        /** The size of the array */
        unsigned size;
        /** Pointer to the array of admissible files. */
        struct osl_row **array;
};

/*
 * Check whether the given audio file is admissible. If it is, add it to array
 * of admissible files.
 */
static int add_if_admissible(struct osl_row *aft_row, void *data)
{
        struct admissible_array *aa = data;
        int ret;

        ret = row_is_admissible(aft_row, aa->m);
        if (ret <= 0)
                return ret;
        if (statistics.num >= aa->size) {
                aa->size *= 2;
                aa->size += 100;
                aa->array = para_realloc(aa->array,
                        aa->size * sizeof(struct osl_row *));
        }
        aa->array[statistics.num] = aft_row;
        return add_afs_statistics(aft_row);
}

/**
 * Compute the new quadratic deviation in case one element changes.
 *
 * \param n Number of elements.
 * \param old_qd The quadratic deviation before the change.
 * \param old_val The value that was replaced.
 * \param new_val The replacement value.
 * \param old_sum The sum of all elements before the update.
 *
 * \return The new quadratic deviation resulting from replacing old_val
 * by new_val.
 *
 * Given n real numbers a_1, ..., a_n, their sum S = a_1 + ... + a_n,
 * their quadratic deviation
 *
 * q = (a_1 - S/n)^2 + ... + (a_n - S/n)^2,
 *
 * and a real number b, the quadratic deviation q' of a_1,...a_{n-1}, b (ie.
 * the last number a_n was replaced by b) may be computed in O(1) time in terms
 * of n, q, a_n, b, and S as
 *
 *      q' = q + d * s - (2 * S + d) * d / n
 *         = q + d * (s - 2 * S / n - d /n),
 *
 * where d = b - a_n, and s = b + a_n.
 *
 * Example: n = 3, a_1 = 3, a_2 = 5, a_3 = 7, b = 10. Then S = 15, q = 8, d = 3,
 * s = 17, so
 *
 *      q + d * s - (2 * S + d) * d / n = 8 + 51 - 33 = 26,
 *
 * which equals q' = (3 - 6)^2 + (5 - 6)^2 + (10 - 6)^2.
 *
 */
_static_inline_ int64_t update_quadratic_deviation(int64_t n, int64_t old_qd,
                int64_t old_val, int64_t new_val, int64_t old_sum)
{
        int64_t delta = new_val - old_val;
        int64_t sigma = new_val + old_val;
        return old_qd + delta * (sigma - 2 * old_sum / n - delta / n);
}

static int update_afs_statistics(struct afs_info *old_afsi,
                struct afs_info *new_afsi)
{
        unsigned n;
        int ret = get_num_admissible_files(&n);

        if (ret < 0)
                return ret;
        assert(n);

        statistics.last_played_qd = update_quadratic_deviation(n,
                statistics.last_played_qd, old_afsi->last_played,
                new_afsi->last_played, statistics.last_played_sum);
        statistics.last_played_sum += new_afsi->last_played - old_afsi->last_played;

        statistics.num_played_qd = update_quadratic_deviation(n,
                statistics.num_played_qd, old_afsi->num_played,
                new_afsi->num_played, statistics.num_played_sum);
        statistics.num_played_sum += new_afsi->num_played - old_afsi->num_played;
        return 1;
}

static int add_to_score_table(const struct osl_row *aft_row)
{
        long score;
        struct afs_info afsi;
        int ret = get_afsi_of_row(aft_row, &afsi);

        if (ret < 0)
                return ret;
        score = compute_score(&afsi);
        return score_add(aft_row, score);
}

static int delete_from_statistics_and_score_table(const struct osl_row *aft_row)
{
        int ret = del_afs_statistics(aft_row);
        if (ret < 0)
                return ret;
        return score_delete(aft_row);
}

/**
 * Delete one entry from the statistics and from the score table.
 *
 * \param aft_row The audio file which is no longer admissible.
 *
 * \return Positive on success, negative on errors.
 *
 * \sa \ref score_delete().
 */
static int mood_delete_audio_file(const struct osl_row *aft_row)
{
        int ret;

        ret = row_belongs_to_score_table(aft_row, NULL);
        if (ret < 0)
                return ret;
        if (!ret) /* not admissible, nothing to do */
                return 1;
        return delete_from_statistics_and_score_table(aft_row);
}

/**
 * Compute the new score of an audio file wrt. the current mood.
 *
 * \param aft_row Determines the audio file.
 * \param old_afsi The audio file selector info before updating.
 *
 * The \a old_afsi argument may be \p NULL which indicates that no changes to
 * the audio file info were made.
 *
 * \return Positive on success, negative on errors.
 */
static int mood_update_audio_file(const struct osl_row *aft_row,
                struct afs_info *old_afsi)
{
        long score, percent;
        int ret, is_admissible, was_admissible = 0;
        struct afs_info afsi;
        unsigned rank;

        if (!current_mood)
                return 1; /* nothing to do */
        ret = row_belongs_to_score_table(aft_row, &rank);
        if (ret < 0)
                return ret;
        was_admissible = ret;
        ret = row_is_admissible(aft_row, current_mood);
        if (ret < 0)
                return ret;
        is_admissible = (ret > 0);
        if (!was_admissible && !is_admissible)
                return 1;
        if (was_admissible && !is_admissible)
                return delete_from_statistics_and_score_table(aft_row);
        if (!was_admissible && is_admissible) {
                ret = add_afs_statistics(aft_row);
                if (ret < 0)
                        return ret;
                return add_to_score_table(aft_row);
        }
        /* update score */
        ret = get_afsi_of_row(aft_row, &afsi);
        if (ret < 0)
                return ret;
        if (old_afsi) {
                ret = update_afs_statistics(old_afsi, &afsi);
                if (ret < 0)
                        return ret;
        }
        score = compute_score(&afsi);
        PARA_DEBUG_LOG("score: %li\n", score);
        percent = (score + 100) / 3;
        if (percent > 100)
                percent = 100;
        else if (percent < 0)
                percent = 0;
        PARA_DEBUG_LOG("moving from rank %u to %li%%\n", rank, percent);
        return score_update(aft_row, percent);
}

/* sse: seconds since epoch. */
static void log_statistics(int64_t sse)
{
        unsigned n = statistics.num;
        int mean_days, sigma_days;

        assert(current_mood);
        PARA_NOTICE_LOG("loaded mood %s\n", current_mood->name?
                current_mood->name : "(dummy)");
        if (!n) {
                PARA_WARNING_LOG("no admissible files\n");
                return;
        }
        PARA_NOTICE_LOG("%u admissible files\n", statistics.num);
        mean_days = (sse - statistics.last_played_sum / n) / 3600 / 24;
        sigma_days = int_sqrt(statistics.last_played_qd / n) / 3600 / 24;
        PARA_NOTICE_LOG("last_played mean/sigma: %d/%d days\n", mean_days, sigma_days);
        PARA_NOTICE_LOG("num_played mean/sigma: %" PRId64 "/%" PRIu64 "\n",
                statistics.num_played_sum / n,
                int_sqrt(statistics.num_played_qd / n));
        PARA_NOTICE_LOG("num_played correction factor: %" PRId64 "\n",
                statistics.num_played_correction);
        PARA_NOTICE_LOG("last_played correction factor: %" PRId64 "\n",
                statistics.last_played_correction);
        PARA_NOTICE_LOG("normalization divisor: %" PRId64 "\n",
                statistics.normalization_divisor);
}

/**
 * Close the current mood.
 *
 * Frees all resources of the current mood.
 */
void close_current_mood(void)
{
        destroy_mood(current_mood);
        current_mood = NULL;
        memset(&statistics, 0, sizeof(statistics));
        statistics.normalization_divisor = 1;
}

static void compute_correction_factors(int64_t sse)
{
        struct afs_statistics *s = &statistics;

        if (s->num > 0) {
                s->normalization_divisor = int_sqrt(s->last_played_qd)
                        * int_sqrt(s->num_played_qd) / s->num / 100;
                s->num_played_correction = sse - s->last_played_sum / s->num;
                s->last_played_correction = s->num_played_sum / s->num;
        }
        if (s->num_played_correction == 0)
                s->num_played_correction = 1;
        if (s->normalization_divisor == 0)
                s->normalization_divisor = 1;
        if (s->last_played_correction == 0)
                s->last_played_correction = 1;
}

/**
 * Change the current mood.
 *
 * \param mood_name The name of the mood to open.
 * \param errmsg Error description is returned here.
 *
 * If \a mood_name is \a NULL, load the dummy mood that accepts every audio file
 * and uses a scoring method based only on the \a last_played information.
 *
 * The errmsg pointer may be NULL, in which case no error message will be
 * returned. If a non-NULL pointer is given, the caller must free *errmsg.
 *
 * If there is already an open mood, it will be closed first.
 *
 * \return Positive on success, negative on errors.
 *
 * \sa struct \ref afs_info::last_played, \ref mp_eval_row().
 */
int change_current_mood(const char *mood_name, char **errmsg)
{
        int i, ret;
        struct admissible_array aa = {
                .size = 0,
                .array = NULL
        };
        /*
         * We can not use the "now" pointer from sched.c here because we are
         * called before schedule(), which initializes "now".
         */
        struct timeval rnow;

        if (mood_name) {
                struct mood *m;
                struct osl_row *row;
                struct osl_object obj;

                if (!*mood_name) {
                        *errmsg = make_message("empty mood name");
                        return -ERRNO_TO_PARA_ERROR(EINVAL);
                }
                obj.data = (char *)mood_name;
                obj.size = strlen(mood_name) + 1;
                ret = osl(osl_get_row(moods_table, BLOBCOL_NAME, &obj, &row));
                if (ret < 0) {
                        if (errmsg)
                                *errmsg = make_message("no such mood: %s",
                                        mood_name);
                        return ret;
                }
                ret = load_mood(row, &m, errmsg);
                if (ret < 0)
                        return ret;
                close_current_mood();
                current_mood = m;
        } else { /* load dummy mood */
                close_current_mood();
                current_mood = alloc_new_mood(NULL);
        }
        aa.m = current_mood;
        PARA_NOTICE_LOG("computing statistics of admissible files\n");
        ret = audio_file_loop(&aa, add_if_admissible);
        if (ret < 0) {
                if (errmsg)
                        *errmsg = make_message("audio file loop failed");
                goto out;
        }
        clock_get_realtime(&rnow);
        compute_correction_factors(rnow.tv_sec);
        log_statistics(rnow.tv_sec);
        for (i = 0; i < statistics.num; i++) {
                ret = add_to_score_table(aa.array[i]);
                if (ret < 0) {
                        if (errmsg)
                                *errmsg = make_message(
                                        "could not add row to score table");
                        goto out;
                }
        }
        ret = statistics.num;
out:
        free(aa.array);
        if (ret < 0)
                close_current_mood();
        return ret;
}

/*
 * Close and re-open the current mood.
 *
 * This function is called on events which render the current list of
 * admissible files useless, for example if an attribute is removed from the
 * attribute table.
 *
 * If no mood is currently open, the function returns success.
 */
static int reload_current_mood(void)
{
        int ret;
        char *mood_name = NULL;

        ret = clear_score_table();
        if (ret < 0)
                return ret;
        if (!current_mood)
                return 1;
        PARA_NOTICE_LOG("reloading %s\n", current_mood->name?
                current_mood->name : "(dummy)");
        if (current_mood->name)
                mood_name = para_strdup(current_mood->name);
        close_current_mood();
        ret = change_current_mood(mood_name, NULL);
        free(mood_name);
        return ret;
}

/**
 * Notification callback for the moods table.
 *
 * \param event Type of the event just occurred.
 * \param pb Unused.
 * \param data Its type depends on the event.
 *
 * This function updates the score table according to the event that has
 * occurred. Two actions are possible: (a) reload the current mood, or (b)
 * add/remove/update the row of the score table which corresponds to the audio
 * file that has been modified or whose afs info has been changed. It depends
 * on the type of the event which action (if any) is performed.
 *
 * The callbacks of command handlers such as com_add() or com_touch() which
 * modify the audio file table call this function. The virtual streaming system
 * also calls this after it has updated the afs info of the file it is about to
 * stream (the one with the highest score). If the file stays admissible, its
 * score is recomputed so that a different file is picked next time.
 *
 * \return Standard.
 */
int moods_event_handler(enum afs_events event, __a_unused struct para_buffer *pb,
                void *data)
{
        if (!current_mood)
                return 0;
        switch (event) {
        /*
         * The three blob events might change the set of admissible files,
         * so we must reload the score list.
         */
        case BLOB_RENAME:
        case BLOB_REMOVE:
        case BLOB_ADD:
                if (data == moods_table || data == playlists_table)
                        return 1; /* no reload necessary for these */
                return reload_current_mood();
        /* these also require reload of the score table */
        case ATTRIBUTE_ADD:
        case ATTRIBUTE_REMOVE:
        case ATTRIBUTE_RENAME:
                return reload_current_mood();
        /* changes to the aft only require to re-examine the audio file */
        case AFSI_CHANGE: {
                struct afsi_change_event_data *aced = data;
                return mood_update_audio_file(aced->aft_row, aced->old_afsi);
                }
        case AFHI_CHANGE:
        case AUDIO_FILE_RENAME:
        case AUDIO_FILE_ADD:
                return mood_update_audio_file(data, NULL);
        case AUDIO_FILE_REMOVE:
                return mood_delete_audio_file(data);
        default:
                return 1;
        }
}