<commit_before>/*
 * Copyright 2007-2017 Content Management AG
 * All rights reserved.
 *
 * author: <NAME> <<EMAIL>>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * - 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.
 *
 * 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
 * FOUNDATION OR CONTRIBUTORS 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.
 */

#include "istream_subst.hxx"
#include "FacadeIstream.hxx"
#include "UnusedPtr.hxx"
#include "pool/pool.hxx"
#include "util/DestructObserver.hxx"
#include "util/StringView.hxx"

#include <assert.h>
#include <string.h>

/* ternary search tree */
struct SubstNode {
    SubstNode *parent, *left, *right, *equals;
    char ch;

    struct {
        const char *a;
        size_t b_length;
        char b[1];
    } leaf;
};

class SubstIstream final : public FacadeIstream, DestructAnchor {
    bool had_input, had_output;

    bool send_first;

    SubstTree tree;

    const SubstNode *match;
    StringView mismatch = nullptr;

    enum class State {
        /** searching the first matching character */
        NONE,

        /** at least the first character was found, checking for the
            rest */
        MATCH,

        /** inserting the substitution */
        INSERT,
    } state = State::NONE;
    size_t a_match, b_sent;

 public:
    SubstIstream(struct pool &p, UnusedIstreamPtr &&_input, SubstTree &&_tree) noexcept
        :FacadeIstream(p, std::move(_input)), tree(std::move(_tree)) {}

private:
    /** find the first occurence of a "first character" in the buffer */
    const char *FindFirstChar(const char *data, size_t length) noexcept;

    /**
     * Write data from "b".
     *
     * @return the number of bytes remaining
     */
    size_t TryWriteB() noexcept;

    bool FeedMismatch() noexcept;
    bool WriteMismatch() noexcept;

    /**
     * Forwards source data to the istream handler.
     *
     * @return (size_t)-1 when everything has been consumed, or the
     * correct return value for the data() callback.
     */
    size_t ForwardSourceData(const char *start,
                             const char *p, size_t length) noexcept;
    size_t ForwardSourceDataFinal(const char *start,
                                  const char *end, const char *p) noexcept;

    size_t Feed(const void *data, size_t length) noexcept;

public:
    /* virtual methods from class Istream */

    void _Read() noexcept override;
    void _Close() noexcept override;

    /* istream handler */

    size_t OnData(const void *data, size_t length) noexcept override;

    void OnEof() noexcept override;
    void OnError(std::exception_ptr ep) noexcept override;
};

/*
 * helper functions
 *
 */

/** iterates over the current depth */
static SubstNode *
subst_next_non_leaf_node(SubstNode *node, SubstNode *root)
{
    /* dive into left wing first */
    if (node->left != nullptr && node->left->ch != 0)
        return node->left;

    /* if left does not exist, go right */
    if (node->right != nullptr && node->right->ch != 0)
        return node->right;

    /* this subtree is finished, go up */
    while (true) {
        /* don't go above our root */
        if (node == root)
            return nullptr;

        assert(node->parent != nullptr);

        if (node->parent->left == node) {
            node = node->parent;

            /* only go to parent->right if we came from
               parent->left */
            if (node->right != nullptr && node->right->ch != 0)
                return node;
        } else {
            node = node->parent;
        }
    }
}

inline std::pair<const SubstNode *, const char *>
SubstTree::FindFirstChar(const char *data, size_t length) const noexcept
{
    SubstNode *n = root;
    const SubstNode *match = nullptr;
    const char *min = nullptr;

    while (n != nullptr) {
        assert(n->ch != 0);

        auto *p = (const char *)memchr(data, n->ch, length);
        if (p != nullptr && (min == nullptr || p < min)) {
            assert(n->equals != nullptr);
            match = n->equals;
            min = p;
        }

        n = subst_next_non_leaf_node(n, root);
    }

    return std::make_pair(match, min);
}
<commit_msg>istream/subst: pass const pointers to subst_next_non_leaf_node()<commit_after>/*
 * Copyright 2007-2017 Content Management AG
 * All rights reserved.
 *
 * author: <NAME> <<EMAIL>>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * - 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.
 *
 * 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
 * FOUNDATION OR CONTRIBUTORS 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.
 */

#include "istream_subst.hxx"
#include "FacadeIstream.hxx"
#include "UnusedPtr.hxx"
#include "pool/pool.hxx"
#include "util/DestructObserver.hxx"
#include "util/StringView.hxx"

#include <assert.h>
#include <string.h>

/* ternary search tree */
struct SubstNode {
    SubstNode *parent, *left, *right, *equals;
    char ch;

    struct {
        const char *a;
        size_t b_length;
        char b[1];
    } leaf;
};

class SubstIstream final : public FacadeIstream, DestructAnchor {
    bool had_input, had_output;

    bool send_first;

    SubstTree tree;

    const SubstNode *match;
    StringView mismatch = nullptr;

    enum class State {
        /** searching the first matching character */
        NONE,

        /** at least the first character was found, checking for the
            rest */
        MATCH,

        /** inserting the substitution */
        INSERT,
    } state = State::NONE;
    size_t a_match, b_sent;

 public:
    SubstIstream(struct pool &p, UnusedIstreamPtr &&_input, SubstTree &&_tree) noexcept
        :FacadeIstream(p, std::move(_input)), tree(std::move(_tree)) {}

private:
    /** find the first occurence of a "first character" in the buffer */
    const char *FindFirstChar(const char *data, size_t length) noexcept;

    /**
     * Write data from "b".
     *
     * @return the number of bytes remaining
     */
    size_t TryWriteB() noexcept;

    bool FeedMismatch() noexcept;
    bool WriteMismatch() noexcept;

    /**
     * Forwards source data to the istream handler.
     *
     * @return (size_t)-1 when everything has been consumed, or the
     * correct return value for the data() callback.
     */
    size_t ForwardSourceData(const char *start,
                             const char *p, size_t length) noexcept;
    size_t ForwardSourceDataFinal(const char *start,
                                  const char *end, const char *p) noexcept;

    size_t Feed(const void *data, size_t length) noexcept;

public:
    /* virtual methods from class Istream */

    void _Read() noexcept override;
    void _Close() noexcept override;

    /* istream handler */

    size_t OnData(const void *data, size_t length) noexcept override;

    void OnEof() noexcept override;
    void OnError(std::exception_ptr ep) noexcept override;
};

/*
 * helper functions
 *
 */

/** iterates over the current depth */
gcc_pure
static const SubstNode *
subst_next_non_leaf_node(const SubstNode *node, const SubstNode *root) noexcept
{
    /* dive into left wing first */
    if (node->left != nullptr && node->left->ch != 0)
        return node->left;

    /* if left does not exist, go right */
    if (node->right != nullptr && node->right->ch != 0)
        return node->right;

    /* this subtree is finished, go up */
    while (true) {
        /* don't go above our root */
        if (node == root)
            return nullptr;

        assert(node->parent != nullptr);

        if (node->parent->left == node) {
            node = node->parent;

            /* only go to parent->right if we came from
               parent->left */
            if (node->right != nullptr && node->right->ch != 0)
                return node;
        } else {
            node = node->parent;
        }
    }
}

inline std::pair<const SubstNode *, const char *>
SubstTree::FindFirstChar(const char *data, size_t length) const noexcept
{
    const SubstNode *n = root;
    const SubstNode *match = nullptr;
    const char *min = nullptr;

    while (n != nullptr) {
        assert(n->ch != 0);

        auto *p = (const char *)memchr(data, n->ch, length);
        if (p != nullptr && (min == nullptr || p < min)) {
            assert(n->equals != nullptr);
            match = n->equals;
            min = p;
        }

        n = subst_next_non_leaf_node(n, root);
    }

    return std::make_pair(match, min);
}

{'fraction_non_alphanumeric': 0.10059563203176704, 'fraction_numerical': 0.0026472534745201853, 'mean_word_length': 2.6690946930280957, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2949498', 'n_tokens_mistral': 3157, 'n_tokens_neox': 2958, 'n_words': 1115}