badvpn/ncd/modules/explode.c

/**
 * @file explode.c
 * @author Ambroz Bizjak <ambrop7@gmail.com>
 * 
 * @section LICENSE
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the author nor the
 *    names of its contributors may be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * @section DESCRIPTION
 * 
 * 
 * Synopsis:
 *   compile_search(string str)
 * 
 * Description:
 *   Performs calculations to enable efficient string searches for the
 *   given string (builds the KMP table). The string must be non-empty.
 * 
 * 
 * Synopsis:
 *   explode(string delimiter, string input [, string limit])
 *   compile_search::explode(string input [, string limit])
 * 
 * Description:
 *   Splits the string 'input' into a list of components. The first component
 *   is the part of 'input' until the first occurence of 'delimiter', if any.
 *   If 'delimiter' was found, the remaining components are defined recursively
 *   via the same procedure, starting with the part of 'input' after the first
 *   substring.
 *   'delimiter' must be nonempty.
 *   The compile_search variant uses an precompiled delimiter string for better
 *   performance.
 * 
 * Variables:
 *   list (empty) - the components of 'input', determined based on 'delimiter'
 */

#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include <misc/exparray.h>
#include <misc/string_begins_with.h>
#include <misc/substring.h>
#include <misc/balloc.h>

#include <ncd/module_common.h>

#include <generated/blog_channel_ncd_explode.h>

struct compile_search_instance {
    NCDModuleInst *i;
    MemRef str;
    size_t *table;
};

struct instance {
    NCDModuleInst *i;
    struct ExpArray arr;
    size_t num;
};

struct substring {
    char *data;
    size_t len;
};

static void compile_search_new (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params)
{
    struct compile_search_instance *o = vo;
    o->i = i;
    
    NCDValRef str_arg;
    if (!NCDVal_ListRead(params->args, 1, &str_arg)) {
        ModuleLog(i, BLOG_ERROR, "wrong arity");
        goto fail0;
    }
    if (!NCDVal_IsString(str_arg)) {
        ModuleLog(i, BLOG_ERROR, "wrong type");
        goto fail0;
    }
    
    o->str = NCDVal_StringMemRef(str_arg);
    if (o->str.len == 0) {
        ModuleLog(i, BLOG_ERROR, "string must be nonempty");
        goto fail0;
    }
    
    o->table = BAllocArray(o->str.len, sizeof(o->table[0]));
    if (!o->table) {
        ModuleLog(i, BLOG_ERROR, "BAllocArray failed");
        goto fail0;
    }
    
    build_substring_backtrack_table(o->str.ptr, o->str.len, o->table);
    
    NCDModuleInst_Backend_Up(i);
    return;
    
fail0:
    NCDModuleInst_Backend_DeadError(i);
}

static void compile_search_die (void *vo)
{
    struct compile_search_instance *o = vo;
    
    BFree(o->table);
    
    NCDModuleInst_Backend_Dead(o->i);
}

static void func_new_common (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params, struct compile_search_instance *compiled)
{
    struct instance *o = vo;
    o->i = i;
    
    int arg_start;
    MemRef del;
    size_t const *table;
    
    if (compiled) {
        arg_start = 0;
        del = compiled->str;
        table = compiled->table;
    } else {
        NCDValRef delimiter_arg;
        if (!NCDVal_ListReadHead(params->args, 1, &delimiter_arg)) {
            ModuleLog(i, BLOG_ERROR, "missing delimiter argument");
            goto fail0;
        }
        if (!NCDVal_IsString(delimiter_arg)) {
            ModuleLog(i, BLOG_ERROR, "wrong delimiter type");
            goto fail0;
        }
        arg_start = 1;
        
        del = NCDVal_StringMemRef(delimiter_arg);
        if (del.len == 0) {
            ModuleLog(i, BLOG_ERROR, "delimiter must be nonempty");
            goto fail0;
        }
        
        table = BAllocArray(del.len, sizeof(table[0]));
        if (!table) {
            ModuleLog(i, BLOG_ERROR, "ExpArray_init failed");
            goto fail0;
        }
        
        build_substring_backtrack_table(del.ptr, del.len, (size_t *)table);
    }
    
    // read arguments
    NCDValRef input_arg;
    NCDValRef limit_arg = NCDVal_NewInvalid();
    if (!NCDVal_ListReadStart(params->args, arg_start, 1, &input_arg) && !NCDVal_ListReadStart(params->args, arg_start, 2, &input_arg, &limit_arg)) {
        ModuleLog(i, BLOG_ERROR, "wrong arity");
        goto fail1;
    }
    if (!NCDVal_IsString(input_arg)) {
        ModuleLog(i, BLOG_ERROR, "wrong type");
        goto fail1;
    }
    
    size_t limit = SIZE_MAX;
    if (!NCDVal_IsInvalid(limit_arg)) {
        uintmax_t n;
        if (!ncd_read_uintmax(limit_arg, &n) || n == 0) {
            ModuleLog(i, BLOG_ERROR, "bad limit argument");
            goto fail1;
        }
        n--;
        limit = (n <= SIZE_MAX ? n : SIZE_MAX);
    }
    
    if (!ExpArray_init(&o->arr, sizeof(struct substring), 8)) {
        ModuleLog(i, BLOG_ERROR, "ExpArray_init failed");
        goto fail1;
    }
    o->num = 0;
    
    MemRef data = NCDVal_StringMemRef(input_arg);
    
    while (1) {
        size_t start;
        int is_end = 0;
        if (limit == 0 || !find_substring(data.ptr, data.len, del.ptr, del.len, table, &start)) {
            start = data.len;
            is_end = 1;
        }
        
        if (!ExpArray_resize(&o->arr, o->num + 1)) {
            ModuleLog(i, BLOG_ERROR, "ExpArray_init failed");
            goto fail2;
        }
        
        struct substring *elem = &((struct substring *)o->arr.v)[o->num];
        
        if (!(elem->data = BAlloc(start))) {
            ModuleLog(i, BLOG_ERROR, "BAlloc failed");
            goto fail2;
        }
        
        memcpy(elem->data, data.ptr, start);
        elem->len = start;
        o->num++;
        
        if (is_end) {
            break;
        }
        
        data = MemRef_SubFrom(data, start + del.len);
        limit--;
    }
    
    if (!compiled) {
        BFree((size_t *)table);
    }
    
    // signal up
    NCDModuleInst_Backend_Up(i);
    return;

fail2:
    while (o->num-- > 0) {
        BFree(((struct substring *)o->arr.v)[o->num].data);
    }
    free(o->arr.v);
fail1:
    if (!compiled) {
        BFree((size_t *)table);
    }
fail0:
    NCDModuleInst_Backend_DeadError(i);
}

static void func_new (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params)
{
    return func_new_common(vo, i, params, NULL);
}

static void func_new_compiled (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params)
{
    struct compile_search_instance *compiled = NCDModuleInst_Backend_GetUser((NCDModuleInst *)params->method_user);
    
    return func_new_common(vo, i, params, compiled);
}

static void func_die (void *vo)
{
    struct instance *o = vo;
    
    while (o->num-- > 0) {
        BFree(((struct substring *)o->arr.v)[o->num].data);
    }
    free(o->arr.v);
    
    NCDModuleInst_Backend_Dead(o->i);
}

static int func_getvar2 (void *vo, NCD_string_id_t name, NCDValMem *mem, NCDValRef *out)
{
    struct instance *o = vo;
    
    if (name == NCD_STRING_EMPTY) {
        *out = NCDVal_NewList(mem, o->num);
        if (NCDVal_IsInvalid(*out)) {
            goto fail;
        }
        for (size_t j = 0; j < o->num; j++) {
            struct substring *elem = &((struct substring *)o->arr.v)[j];
            NCDValRef str = NCDVal_NewStringBin(mem, (uint8_t *)elem->data, elem->len);
            if (NCDVal_IsInvalid(str)) {
                goto fail;
            }
            if (!NCDVal_ListAppend(*out, str)) {
                goto fail;
            }
        }
        return 1;
    }
    
    return 0;
    
fail:
    *out = NCDVal_NewInvalid();
    return 1;
}

static struct NCDModule modules[] = {
    {
        .type = "compile_search",
        .func_new2 = compile_search_new,
        .func_die = compile_search_die,
        .alloc_size = sizeof(struct compile_search_instance)
    }, {
        .type = "explode",
        .func_new2 = func_new,
        .func_die = func_die,
        .func_getvar2 = func_getvar2,
        .alloc_size = sizeof(struct instance)
    }, {
        .type = "compile_search::explode",
        .func_new2 = func_new_compiled,
        .func_die = func_die,
        .func_getvar2 = func_getvar2,
        .alloc_size = sizeof(struct instance)
    }, {
        .type = NULL
    }
};

const struct NCDModuleGroup ncdmodule_explode = {
    .modules = modules
};