path: root/contrib/libs/hyperscan/src/parser/logical_combination.cpp

/* 
 * Copyright (c) 2018-2020, Intel Corporation 
 * 
 * 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. 
 *  * Neither the name of Intel Corporation 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 COPYRIGHT OWNER 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. 
 */ 
 
/** \file 
 * \brief Parse and build ParsedLogical::logicalTree and combInfoMap. 
 */ 
#include "logical_combination.h" 
#include "parser/parse_error.h" 
#include "util/container.h" 
#include "hs_compile.h" 
#include "allocator.h" 
 
#include <vector> 
 
using namespace std; 
 
namespace ue2 { 
 
u32 ParsedLogical::getLogicalKey(u32 a) { 
    auto it = toLogicalKeyMap.find(a); 
    if (it == toLogicalKeyMap.end()) { 
        // get size before assigning to avoid wacky LHS shenanigans 
        u32 size = toLogicalKeyMap.size(); 
        bool inserted; 
        tie(it, inserted) = toLogicalKeyMap.emplace(a, size); 
        assert(inserted); 
    } 
    DEBUG_PRINTF("%u -> lkey %u\n", it->first, it->second); 
    return it->second; 
} 
 
u32 ParsedLogical::getCombKey(u32 a) { 
    auto it = toCombKeyMap.find(a); 
    if (it == toCombKeyMap.end()) { 
        u32 size = toCombKeyMap.size(); 
        bool inserted; 
        tie(it, inserted) = toCombKeyMap.emplace(a, size); 
        assert(inserted); 
    } 
    DEBUG_PRINTF("%u -> ckey %u\n", it->first, it->second); 
    return it->second; 
} 
 
void ParsedLogical::addRelateCKey(u32 lkey, u32 ckey) { 
    auto it = lkey2ckeys.find(lkey); 
    if (it == lkey2ckeys.end()) { 
        bool inserted; 
        tie(it, inserted) = lkey2ckeys.emplace(lkey, set<u32>()); 
        assert(inserted); 
    } 
    it->second.insert(ckey); 
    DEBUG_PRINTF("lkey %u belongs to combination key %u\n", 
                 it->first, ckey); 
} 
 
#define TRY_RENUM_OP(ckey)                                                   \ 
do {                                                                         \ 
    if (ckey & LOGICAL_OP_BIT) {                                             \ 
        ckey = (ckey & ~LOGICAL_OP_BIT) + toLogicalKeyMap.size();            \ 
    }                                                                        \ 
} while(0) 
 
u32 ParsedLogical::logicalTreeAdd(u32 op, u32 left, u32 right) { 
    LogicalOp lop; 
    assert((LOGICAL_OP_BIT & (u32)logicalTree.size()) == 0); 
    lop.id = LOGICAL_OP_BIT | (u32)logicalTree.size(); 
    lop.op = op; 
    lop.lo = left; 
    lop.ro = right; 
    logicalTree.push_back(lop); 
    return lop.id; 
} 
 
void ParsedLogical::combinationInfoAdd(UNUSED u32 ckey, u32 id, u32 ekey, 
                                       u32 lkey_start, u32 lkey_result, 
                                       u64a min_offset, u64a max_offset) { 
    assert(ckey == combInfoMap.size()); 
    CombInfo ci; 
    ci.id = id; 
    ci.ekey = ekey; 
    ci.start = lkey_start; 
    ci.result = lkey_result; 
    ci.min_offset = min_offset; 
    ci.max_offset = max_offset; 
    combInfoMap.push_back(ci); 
 
    DEBUG_PRINTF("ckey %u (id %u) -> lkey %u..%u, ekey=0x%x\n", ckey, ci.id, 
                 ci.start, ci.result, ci.ekey); 
} 
 
void ParsedLogical::validateSubIDs(const unsigned *ids, 
                                   const char *const *expressions, 
                                   const unsigned *flags, 
                                   unsigned elements) { 
    for (const auto &it : toLogicalKeyMap) { 
        bool unknown = true; 
        u32 i = 0; 
        for (i = 0; i < elements; i++) { 
            if ((ids ? ids[i] : 0) == it.first) { 
                unknown = false; 
                break; 
            } 
        } 
        if (unknown) { 
            throw CompileError("Unknown sub-expression id."); 
        } 
        if (contains(toCombKeyMap, it.first)) { 
            throw CompileError("Have combination of combination."); 
        } 
        if (flags && (flags[i] & HS_FLAG_SOM_LEFTMOST)) { 
            throw CompileError("Have SOM flag in sub-expression."); 
        } 
        if (flags && (flags[i] & HS_FLAG_PREFILTER)) { 
            throw CompileError("Have PREFILTER flag in sub-expression."); 
        } 
        hs_compile_error_t *compile_err = NULL; 
        hs_expr_info_t *info = NULL; 
        hs_error_t err = hs_expression_info(expressions[i], flags[i], &info, 
                                            &compile_err); 
        if (err != HS_SUCCESS) { 
            hs_free_compile_error(compile_err); 
            throw CompileError("Run hs_expression_info() failed."); 
        } 
        if (!info) { 
            throw CompileError("Get hs_expr_info_t failed."); 
        } else { 
            if (info->unordered_matches) { 
                throw CompileError("Have unordered match in sub-expressions."); 
            } 
            hs_misc_free(info); 
        } 
    } 
} 
 
void ParsedLogical::logicalKeyRenumber() { 
    // renumber operation lkey in op vector 
    for (auto &op : logicalTree) { 
        TRY_RENUM_OP(op.id); 
        TRY_RENUM_OP(op.lo); 
        TRY_RENUM_OP(op.ro); 
    } 
    // renumber operation lkey in info map 
    for (auto &ci : combInfoMap) { 
        TRY_RENUM_OP(ci.start); 
        TRY_RENUM_OP(ci.result); 
    } 
} 
 
struct LogicalOperator { 
    LogicalOperator(u32 op_in, u32 paren_in) 
        : op(op_in), paren(paren_in) {} 
    u32 op; 
    u32 paren; 
}; 
 
static 
u32 toOperator(char c) { 
    u32 op = UNKNOWN_OP; 
    switch (c) { 
    case '!' : 
        op = LOGICAL_OP_NOT; 
        break; 
    case '&' : 
        op = LOGICAL_OP_AND; 
        break; 
    case '|' : 
        op = LOGICAL_OP_OR; 
        break; 
    default: 
        break; 
    }; 
    return op; 
} 
 
static 
bool cmpOperator(const LogicalOperator &op1, const LogicalOperator &op2) { 
    if (op1.paren < op2.paren) { 
        return false; 
    } 
    if (op1.paren > op2.paren) { 
        return true; 
    } 
    assert(op1.paren == op2.paren); 
    if (op1.op > op2.op) { 
        return false; 
    } 
    if (op1.op < op2.op) { 
        return true; 
    } 
    return true; 
} 
 
static 
u32 fetchSubID(const char *logical, u32 &digit, u32 end) { 
    if (digit == (u32)-1) { // no digit parsing in progress 
        return (u32)-1; 
    } 
    assert(end > digit); 
    if (end - digit > 9) { 
        throw LocatedParseError("Expression id too large"); 
    } 
    u32 mult = 1; 
    u32 sum = 0; 
    for (u32 j = end - 1; (j >= digit) && (j != (u32)-1) ; j--) { 
        assert(isdigit(logical[j])); 
        sum += (logical[j] - '0') * mult; 
        mult *= 10; 
    } 
    digit = (u32)-1; 
    return sum; 
} 
 
static 
void popOperator(vector<LogicalOperator> &op_stack, vector<u32> &subid_stack, 
                 ParsedLogical &pl) { 
    if (subid_stack.empty()) { 
        throw LocatedParseError("Not enough operand"); 
    } 
    u32 right = subid_stack.back(); 
    subid_stack.pop_back(); 
    u32 left = 0; 
    if (op_stack.back().op != LOGICAL_OP_NOT) { 
        if (subid_stack.empty()) { 
            throw LocatedParseError("Not enough operand"); 
        } 
        left = subid_stack.back(); 
        subid_stack.pop_back(); 
    } 
    subid_stack.push_back(pl.logicalTreeAdd(op_stack.back().op, left, right)); 
    op_stack.pop_back(); 
} 
 
void ParsedLogical::parseLogicalCombination(unsigned id, const char *logical, 
                                            u32 ekey, u64a min_offset, 
                                            u64a max_offset) { 
    u32 ckey = getCombKey(id); 
    vector<LogicalOperator> op_stack; 
    vector<u32> subid_stack; 
    u32 lkey_start = INVALID_LKEY; // logical operation's lkey 
    u32 paren = 0; // parentheses 
    u32 digit = (u32)-1; // digit start offset, invalid offset is -1 
    u32 subid = (u32)-1; 
    u32 i; 
    try { 
        for (i = 0; logical[i]; i++) { 
            if (isdigit(logical[i])) { 
                if (digit == (u32)-1) { // new digit start 
                    digit = i; 
                } 
            } else { 
                if ((subid = fetchSubID(logical, digit, i)) != (u32)-1) { 
                    subid_stack.push_back(getLogicalKey(subid)); 
                    addRelateCKey(subid_stack.back(), ckey); 
                } 
                if (logical[i] == ' ') { // skip whitespace 
                    continue; 
                } 
                if (logical[i] == '(') { 
                    paren += 1; 
                } else if (logical[i] == ')') { 
                    if (paren <= 0) { 
                        throw LocatedParseError("Not enough left parentheses"); 
                    } 
                    paren -= 1; 
                } else { 
                    u32 prio = toOperator(logical[i]); 
                    if (prio != UNKNOWN_OP) { 
                        LogicalOperator op(prio, paren); 
                        while (!op_stack.empty() 
                               && cmpOperator(op_stack.back(), op)) { 
                            popOperator(op_stack, subid_stack, *this); 
                            if (lkey_start == INVALID_LKEY) { 
                                lkey_start = subid_stack.back(); 
                            } 
                        } 
                        op_stack.push_back(op); 
                    } else { 
                        throw LocatedParseError("Unknown character"); 
                    } 
                } 
            } 
        } 
        if (paren != 0) { 
            throw LocatedParseError("Not enough right parentheses"); 
        } 
        if ((subid = fetchSubID(logical, digit, i)) != (u32)-1) { 
            subid_stack.push_back(getLogicalKey(subid)); 
            addRelateCKey(subid_stack.back(), ckey); 
        } 
        while (!op_stack.empty()) { 
            popOperator(op_stack, subid_stack, *this); 
            if (lkey_start == INVALID_LKEY) { 
                lkey_start = subid_stack.back(); 
            } 
        } 
        if (subid_stack.size() != 1) { 
            throw LocatedParseError("Not enough operator"); 
        } 
    } catch (LocatedParseError &error) { 
        error.locate(i); 
        throw; 
    } 
    u32 lkey_result = subid_stack.back(); // logical operation's lkey 
    if (lkey_start == INVALID_LKEY) { 
        throw CompileError("No logical operation."); 
    } 
    combinationInfoAdd(ckey, id, ekey, lkey_start, lkey_result, 
                       min_offset, max_offset); 
} 
 
} // namespace ue2