<commit_before>/* 
 * searchmodule.c 
 *
 * C version of `tsurf.utils.search`.
 *
 * TODO: Use a struct instead of a python dictionary for
 * storing info about a possible match.
 *
 */

#include "searchmodule.h"


static char py_search_doc[] = "To search for `needle` in `haystack`.\n"
    "Returns a tuple of two elements: a number and another tuple."
    "The number is a measure of the similarity between `needle` and "
    "`haystack`, whereas the other tuple contains the positions where "
    "the match occurs in `haystack`.";

static PyObject *
py_search(PyObject *self, PyObject *args)
{
    const char *needle;
    const int needle_len;
    const char *haystack;
    const int haystack_len;
    const int smart_case;

    if (!PyArg_ParseTuple(args, "s#s#i", 
            &needle, &needle_len, &haystack, &haystack_len, &smart_case))
        return NULL;

    if (needle_len == 0) {
        return Py_BuildValue("(i,())", -1);        
    }

    // If `haystack` has only uppercase characters then it makes no sense
    // to treat an uppercase letter as a word-boundary character
    int uppercase_is_word_boundary = 0;
    for (int i = 0; i < haystack_len; i++) {
        if (haystack[i] >= 97 && haystack[i] <= 122)
            // non-uppercase letter is found
            uppercase_is_word_boundary = 1;
    }

    // Initialize the return values
    PyObject *best_positions = Py_BuildValue("()");
    float best_similarity = -1;    

    // Utilities variables
    PyObject *needle_pyobj = Py_BuildValue("s", needle);  // new ref    
    Py_ssize_t needle_pyobj_len = PySequence_Length(needle_pyobj);

    // Declarations
    PyObject *matcher, *fork;
    PyObject *consumed, *positions, *boundaries;
    int needle_idx;

    // `matchers` keeps track of all possible matches of `needle` in `haystack`
    PyObject *matchers = PyList_New(1);  // new ref

    // Add the first matcher
    matcher = PyDict_New();  // new ref
    PyDict_SetItemString(matcher, "needle_idx", Py_BuildValue("i", 0));
    PyDict_SetItemString(matcher, "consumed", PyList_New(0));
    PyDict_SetItemString(matcher, "boundaries", PyList_New(0));
    PyDict_SetItemString(matcher, "positions", PyList_New(0));
    // Note: PyList_SetItem don't increment the reference count
    PyList_SetItem(matchers, 0, matcher);

    for (int i = 0; i < haystack_len; i++) {

        // create forks of current matches if needed

        Py_ssize_t matchers_len = PyList_Size(matchers);
        for (int j = 0; j < matchers_len; j++) {

            // get matchers[j] and its values
            matcher = PyList_GetItem(matchers, j);
            /*assert(PyDict_Check(matcher));*/
            consumed = PyDict_GetItemString(matcher, "consumed");
            /*assert(PyList_Check(consumed));*/
            positions = PyDict_GetItemString(matcher, "positions");
            /*assert(PyList_Check(positions));*/
            boundaries = PyDict_GetItemString(matcher, "boundaries");
            /*assert(PyList_Check(boundaries));*/

            // Check if the current character in `haystack` has been matched 
            // before by matchers[j]. If so, we crate a fork of matcher[j].
            int c;
            int idx = -1;
            for (int k = 0; k < PyList_Size(consumed); k++) {
                c = PyInt_AsLong(PyList_GetItem(consumed, k));
                if (tolower(haystack[i]) == c) { 
                    idx = k;
                    break;
                }
            }
            if (idx >= 0) {           
                PyObject *slice = PySequence_GetSlice(needle_pyobj, idx, needle_pyobj_len);  // new ref
                // The slice contains all characters that remains to be matched
                // by this possible fork in `haystack`. If there is room for
                // this remaining characters to be matched in `haystack` then
                // we create a fork, otherwise there is no need to since the
                // match won't certainly succeed.
                if (PySequence_Length(slice) <= haystack_len - i) {
                    // create a new fork
                    fork = PyDict_New();  // new ref
                    PyDict_SetItemString(fork, "needle_idx", Py_BuildValue("i", idx));
                    PyDict_SetItemString(fork, "consumed", PySequence_GetSlice(consumed, 0, idx));
                    PyDict_SetItemString(fork, "boundaries", PySequence_GetSlice(boundaries, 0, idx));
                    PyDict_SetItemString(fork, "positions", PySequence_GetSlice(positions, 0, idx));
                    // append the new fork to matchers pool
                    PyList_Append(matchers, fork);  // PyList_append increment the ref counter
                    Py_DECREF(fork);
                }
                Py_DECREF(slice);
            }
        }

        // update each matcher
        
        int cond;
        PyObject *pos, *c;

        for (int j = 0; j < PyList_Size(matchers); j++) {
            
            matcher = PyList_GetItem(matchers, j);  // borrowed ref
            /*assert(PyDict_Check(matcher));*/
            needle_idx = PyInt_AsLong(PyDict_GetItemString(matcher, "needle_idx"));
            consumed = PyDict_GetItemString(matcher, "consumed");
            /*assert(PyList_Check(consumed));*/
            positions = PyDict_GetItemString(matcher, "positions");
            /*assert(PyList_Check(positions));*/
            boundaries = PyDict_GetItemString(matcher, "boundaries");
            /*assert(PyList_Check(boundaries));*/

            if (needle_idx == needle_len)
                continue;

            if (smart_case && isupper(needle[needle_idx]))
                cond = haystack[i] == needle[needle_idx];
            else
                cond = tolower(haystack[i]) == tolower(needle[needle_idx]);           

            if (cond) {

                if ((uppercase_is_word_boundary && isupper(haystack[i])) || i == 0 || 
                    (i > 0 && (haystack[i-1] == '-' || haystack[i-1] == '_'))) {
                    pos = Py_BuildValue("i", 1);  // new ref
                    PyList_Append(boundaries, pos);
                } else {
                    pos = Py_BuildValue("i", 0);  // new ref
                    PyList_Append(boundaries, pos);
                }
                Py_DECREF(pos);

                pos = Py_BuildValue("i", i);  // new ref
                PyList_Append(positions, pos);
                Py_DECREF(pos);

                c = Py_BuildValue("i", tolower(needle[needle_idx]));  // new ref
                PyList_Append(consumed, c);
                Py_DECREF(c);

                needle_idx++;
                PyDict_SetItemString(matcher, "needle_idx", Py_BuildValue("i", needle_idx));

                if (needle_idx == needle_len) {
                    int boundaries_count = 0;
                    for (int k = 0; k < PyList_Size(boundaries); k++) {
                        if (PyInt_AsLong(PyList_GetItem(boundaries, k)))
                            boundaries_count++;
                    }
                    float s = similarity(haystack_len, positions, boundaries_count);
                    if (best_similarity < 0 || s < best_similarity) {
                        best_similarity = s;
                        Py_DECREF(best_positions);  // TODO: correct right ??
                        best_positions = PySequence_Tuple(positions);
                    }
                }
            }
        }
    }
    Py_DECREF(needle_pyobj);
    Py_XDECREF(matchers);
    return Py_BuildValue("(f,N)", best_similarity, best_positions);
}


float 
similarity(int haystack_len, PyObject *positions, int boundaries_count) 
{
    /*assert(PyList_Check(positions));*/

    Py_ssize_t positions_len = PyList_Size(positions);
    if (positions_len == 0)
        return -1;

    int n = 0;
    float diffs_sum = .0;
    int contiguous_sets = 1;
<commit_msg>Minor fix in "searchmodule.c"<commit_after>/* 
 * searchmodule.c 
 *
 * C version of `tsurf.utils.search`.
 *
 */

#include "searchmodule.h"


static char py_search_doc[] = "To search for `needle` in `haystack`.\n"
    "Returns a tuple of two elements: a number and another tuple."
    "The number is a measure of the similarity between `needle` and "
    "`haystack`, whereas the other tuple contains the positions where "
    "the match occurs in `haystack`.";

static PyObject *
py_search(PyObject *self, PyObject *args)
{
    const char *needle;
    const int needle_len;
    const char *haystack;
    const int haystack_len;
    const int smart_case;

    if (!PyArg_ParseTuple(args, "s#s#i", 
            &needle, &needle_len, &haystack, &haystack_len, &smart_case))
        return NULL;

    if (needle_len == 0) {
        return Py_BuildValue("(i,())", -1);        
    }

    // If `haystack` has only uppercase characters then it makes no sense
    // to treat an uppercase letter as a word-boundary character
    int uppercase_is_word_boundary = 0;
    for (int i = 0; i < haystack_len; i++) {
        if (haystack[i] >= 97 && haystack[i] <= 122)
            // non-uppercase letter is found
            uppercase_is_word_boundary = 1;
    }

    // Initialize the return values
    PyObject *best_positions = Py_BuildValue("()");
    float best_similarity = -1;    

    // Utilities variables
    PyObject *needle_pyobj = Py_BuildValue("s", needle);  // new ref    
    Py_ssize_t needle_pyobj_len = PySequence_Length(needle_pyobj);

    // Declarations
    PyObject *matcher, *fork;
    PyObject *consumed, *positions, *boundaries;
    int needle_idx;

    // `matchers` keeps track of all possible matches of `needle` in `haystack`
    PyObject *matchers = PyList_New(1);  // new ref

    // Add the first matcher
    matcher = PyDict_New();  // new ref
    PyDict_SetItemString(matcher, "needle_idx", Py_BuildValue("i", 0));
    PyDict_SetItemString(matcher, "consumed", PyList_New(0));
    PyDict_SetItemString(matcher, "boundaries", PyList_New(0));
    PyDict_SetItemString(matcher, "positions", PyList_New(0));
    // Note: PyList_SetItem don't increment the reference count
    PyList_SetItem(matchers, 0, matcher);

    for (int i = 0; i < haystack_len; i++) {

        // create forks of current matches if needed

        Py_ssize_t matchers_len = PyList_Size(matchers);
        for (int j = 0; j < matchers_len; j++) {

            // get matchers[j] and its values
            matcher = PyList_GetItem(matchers, j);
            /*assert(PyDict_Check(matcher));*/
            consumed = PyDict_GetItemString(matcher, "consumed");
            /*assert(PyList_Check(consumed));*/
            positions = PyDict_GetItemString(matcher, "positions");
            /*assert(PyList_Check(positions));*/
            boundaries = PyDict_GetItemString(matcher, "boundaries");
            /*assert(PyList_Check(boundaries));*/

            // Check if the current character in `haystack` has been matched 
            // before by matchers[j]. If so, we crate a fork of matcher[j].
            int c;
            int idx = -1;
            for (int k = 0; k < PyList_Size(consumed); k++) {
                c = PyInt_AsLong(PyList_GetItem(consumed, k));
                if (tolower(haystack[i]) == c) { 
                    idx = k;
                    break;
                }
            }
            if (idx >= 0) {           
                PyObject *slice = PySequence_GetSlice(needle_pyobj, idx, needle_pyobj_len);  // new ref
                // The slice contains all characters that remains to be matched
                // by this possible fork in `haystack`. If there is room for
                // this remaining characters to be matched in `haystack` then
                // we create a fork, otherwise there is no need to since the
                // match won't certainly succeed.
                if (PySequence_Length(slice) <= haystack_len - i) {
                    // create a new fork
                    fork = PyDict_New();  // new ref
                    PyDict_SetItemString(fork, "needle_idx", Py_BuildValue("i", idx));
                    PyDict_SetItemString(fork, "consumed", PySequence_GetSlice(consumed, 0, idx));
                    PyDict_SetItemString(fork, "boundaries", PySequence_GetSlice(boundaries, 0, idx));
                    PyDict_SetItemString(fork, "positions", PySequence_GetSlice(positions, 0, idx));
                    // append the new fork to matchers pool
                    PyList_Append(matchers, fork);  // PyList_append increment the ref counter
                    Py_DECREF(fork);
                }
                Py_DECREF(slice);
            }
        }

        // update each matcher
        
        int cond;
        PyObject *pos, *c;

        for (int j = 0; j < PyList_Size(matchers); j++) {
            
            matcher = PyList_GetItem(matchers, j);  // borrowed ref
            /*assert(PyDict_Check(matcher));*/
            needle_idx = PyInt_AsLong(PyDict_GetItemString(matcher, "needle_idx"));
            consumed = PyDict_GetItemString(matcher, "consumed");
            /*assert(PyList_Check(consumed));*/
            positions = PyDict_GetItemString(matcher, "positions");
            /*assert(PyList_Check(positions));*/
            boundaries = PyDict_GetItemString(matcher, "boundaries");
            /*assert(PyList_Check(boundaries));*/

            if (needle_idx == needle_len)
                continue;

            if (smart_case && isupper(needle[needle_idx]))
                cond = haystack[i] == needle[needle_idx];
            else
                cond = tolower(haystack[i]) == tolower(needle[needle_idx]);           

            if (cond) {

                if ((uppercase_is_word_boundary && isupper(haystack[i])) || i == 0 || 
                    (i > 0 && (haystack[i-1] == '-' || haystack[i-1] == '_'))) {
                    pos = Py_BuildValue("i", 1);  // new ref
                    PyList_Append(boundaries, pos);
                } else {
                    pos = Py_BuildValue("i", 0);  // new ref
                    PyList_Append(boundaries, pos);
                }
                Py_DECREF(pos);

                pos = Py_BuildValue("i", i);  // new ref
                PyList_Append(positions, pos);
                Py_DECREF(pos);

                c = Py_BuildValue("i", tolower(needle[needle_idx]));  // new ref
                PyList_Append(consumed, c);
                Py_DECREF(c);

                needle_idx++;
                PyDict_SetItemString(matcher, "needle_idx", Py_BuildValue("i", needle_idx));

                if (needle_idx == needle_len) {
                    int boundaries_count = 0;
                    for (int k = 0; k < PyList_Size(boundaries); k++) {
                        if (PyInt_AsLong(PyList_GetItem(boundaries, k)))
                            boundaries_count++;
                    }
                    float s = similarity(haystack_len, positions, boundaries_count);
                    if (best_similarity < 0 || s < best_similarity) {
                        best_similarity = s;
                        Py_DECREF(best_positions);  // TODO: correct right ??
                        best_positions = PySequence_Tuple(positions);
                    }
                }
            }
        }
    }
    Py_DECREF(needle_pyobj);
    Py_DECREF(matchers);
    return Py_BuildValue("(f,N)", best_similarity, best_positions);
}


float 
similarity(int haystack_len, PyObject *positions, int boundaries_count) 
{
    /*assert(PyList_Check(positions));*/

    Py_ssize_t positions_len = PyList_Size(positions);
    if (positions_len == 0)
        return -1;

    int n = 0;
    float diffs_sum = .0;
    int contiguous_sets = 1;

{'fraction_non_alphanumeric': 0.11083445061610164, 'fraction_numerical': 0.005107578369405606, 'mean_word_length': 1.9136904761904763, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4101994', 'n_tokens_mistral': 4822, 'n_tokens_neox': 4520, 'n_words': 1145}