/******************************************************************************\
* Copyright (c) 2019, Robert van Engelen, Genivia Inc. All rights reserved. *
* *
* 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) The name of the author may not be used to endorse or promote products *
* derived from this software without specific prior written permission. *
* *
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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. *
\******************************************************************************/
/**
@file cnf.cpp
@brief CNF class for normalization of Boolean search queries
@author Robert van Engelen - engelen@genivia.com
@copyright (c) 2019-2025, Robert van Engelen, Genivia Inc. All rights reserved.
@copyright (c) BSD-3 License - see LICENSE.txt
*/
#include "ugrep.hpp"
#include <reflex/fuzzymatcher.h>
// parse a pattern into an operator tree using a recursive descent parser
void CNF::OpTree::parse(const char *& pattern)
{
do
parse1(pattern);
while (*pattern != '\0');
}
// <parse1> -> <parse2> { <space>+ [ 'AND' <space>+ ] <parse2> }*
void CNF::OpTree::parse1(const char *& pattern)
{
skip_space(pattern);
if (*pattern == '\0' && flag_line_regexp)
pattern = "^$";
while (*pattern != '\0')
{
list.emplace_back(OR);
list.back().parse2(pattern);
skip_space(pattern);
if (*pattern == ')')
break;
if (is_oper(AND, pattern))
skip_space(pattern);
}
}
// <parse2> -> <parse3> { [ '|'+ | 'OR' <space>+ ] <parse3> }*
void CNF::OpTree::parse2(const char *& pattern)
{
do
{
list.emplace_back(NONE);
list.back().parse3(pattern);
} while (is_alternation(pattern));
}
// <parse3> -> [ '-' <space>* | 'NOT' <space>+ ] <parse4>
// <parse4> -> '(' <parse1> ')' | <pattern>
// Note: '(' <parse1> ')' is parsed only when not (?...) and when followed by spacing or a |, e.g. to prevent (foo|bar)? to be converted to foo|bar AND ?
void CNF::OpTree::parse3(const char *& pattern)
{
if (*pattern == '-' || is_oper(NOT, pattern))
{
op = NOT;
++pattern;
skip_space(pattern);
}
bool parens = false;
if (*pattern == '(' && (flag_mode == Mode::FIXED || pattern[1] != '?'))
{
// check if matching ending ) is followed by spacing or EOS or |, then it is OK to parse '(' <parse1> ')' and convert to CNF
int level = 0;
const char *lookahead = pattern;
while (*lookahead != '\0')
{
++lookahead;
if (*lookahead == '(')
{
++level;
}
else if (*lookahead == ')')
{
if (level == 0)
{
++lookahead;
parens = *lookahead == '\0' || *lookahead == '|' || *lookahead == ')' || isspace(static_cast<unsigned char>(*lookahead));
break;
}
--level;
}
else if (*lookahead == '[' && flag_mode != Mode::FIXED)
{
// skip [...]
++lookahead;
lookahead += *lookahead == '^';
lookahead += *lookahead != '\0';
while (*lookahead != '\0' && *lookahead != ']')
if (*lookahead++ == '\\' && *lookahead != '\0')
++lookahead;
}
else if (*lookahead == '"')
{
// skip "..."
++lookahead;
while (*lookahead != '\0' && *lookahead != '"')
if (*lookahead++ == '\\' && *lookahead != '\0')
++lookahead;
}
else if (*lookahead == '\\')
{
// skip \Q...\E and escaped characters \x such as \(
if (*++lookahead == 'Q')
while (*lookahead != '\0' && (*lookahead != '\\' || lookahead[1] != 'E'))
++lookahead;
}
}
if (parens)
{
// skip ( and spacing
++pattern;
skip_space(pattern);
// new AND term, only parse when pattern isn't an empty ()
list.emplace_back(AND);
if (*pattern != ')')
list.back().parse1(pattern);
if (*pattern == ')')
++pattern;
}
}
if (!parens)
{
int level = 0;
const char *lookahead = pattern;
regex.clear();
while (*lookahead != '\0')
{
if (*lookahead == '"')
{
regex.append(pattern, lookahead - pattern);
pattern = ++lookahead;
while (*lookahead != '\0' && *lookahead != '"')
if (*lookahead++ == '\\' && *lookahead != '\0')
++lookahead;
std::string quoted(pattern, lookahead - pattern);
size_t from = 0;
size_t to;
// replace each \" by "
while ((to = quoted.find("\\\"", from)) != std::string::npos)
{
quoted.erase(to, 1);
from = to + 1;
}
// if not -x then quote the string with \Q and \E
if (flag_mode != Mode::FIXED)
quote(quoted);
regex.append(quoted);
if (*lookahead == '"')
++lookahead;
pattern = lookahead;
}
else if (*lookahead == '[' && flag_mode != Mode::FIXED)
{
// skip [...]
++lookahead;
lookahead += *lookahead == '^';
lookahead += *lookahead != '\0';
while (*lookahead != '\0' && *lookahead != ']')
if (*lookahead++ == '\\' && *lookahead != '\0')
++lookahead;
if (*lookahead == ']')
++lookahead;
}
else if (*lookahead == '\\')
{
// skip \Q...\E and escaped characters \x such as \(
if (*++lookahead == 'Q')
while (*lookahead != '\0' && (*lookahead != '\\' || lookahead[1] != 'E'))
++lookahead;
if (*lookahead != '\0')
++lookahead;
}
else if (*lookahead == '(')
{
++level;
++lookahead;
}
else if (*lookahead == ')' && level > 0)
{
--level;
++lookahead;
}
else
{
++lookahead;
}
if (level == 0 &&
(*lookahead == ')' ||
*lookahead == '|' ||
isspace(static_cast<unsigned char>(*lookahead))))
break;
}
regex.append(pattern, lookahead - pattern);
pattern = lookahead;
if (flag_line_regexp && regex.empty())
regex.assign("^$");
else if (flag_mode == Mode::FIXED)
quote(regex);
// -w and -x
anchor(regex);
}
}
// normalize operator tree to CNF
void CNF::OpTree::normalize(bool invert)
{
invert ^= op == NOT;
if (list.empty())
{
op = invert ? NOT : NONE;
}
else
{
// normalize list terms
for (auto& i : list)
i.normalize(invert);
if (list.empty())
{
op = NONE;
}
else if (list.size() == 1)
{
// (P) => P
std::list<OpTree> newlist;
newlist.swap(list);
*this = newlist.front();
}
else if (invert)
{
// !(P&Q) => !P|!Q
// !(P|Q) => !P&!Q
if (op == AND)
op = OR;
else if (op == OR)
op = AND;
}
// P&(Q&R) => P&Q&R
// P|(Q|R) => P|Q|R
auto i = list.begin();
auto e = list.end();
while (i != e)
{
if (i->op == op)
{
list.insert(e, i->list.begin(), i->list.end());
list.erase(i++);
}
else
{
++i;
}
}
if (op == OR)
{
// (P&Q)|R => (P|R)&(Q|R)
// (P&Q)|(R&S) => (P|R)&(P|S)&(Q|R)&(Q|S)
i = list.begin();
e = list.end();
while (i != e && i->op != AND)
++i;
if (i != e)
{
// isolate (P&Q&...) from ...|(P&Q&...)|...
std::list<OpTree> newlist;
newlist.swap(i->list);
list.erase(i);
// construct nested lists (P|...)&(Q|...)&...
for (auto& j : newlist)
{
OpTree opt(OR);
opt.list.emplace_back(j.op);
opt.list.back().regex.swap(j.regex);
opt.list.back().list.swap(j.list);
j = opt;
}
i = list.begin();
while (i != e)
{
if (i->op == AND)
{
// (P&Q)|(R&S) => (P|R)&(P|S)&(Q|R)&(Q|S)
std::list<OpTree> product;
for (auto& j : i->list)
{
auto duplist = newlist;
for (auto& k : duplist)
k.list.emplace_back(j);
product.insert(product.end(), duplist.begin(), duplist.end());
}
newlist.swap(product);
}
else
{
// (P&Q)|R => (P|R)&(Q|R)
for (auto& j : newlist)
j.list.emplace_back(*i);
}
list.erase(i++);
}
op = AND;
list.swap(newlist);
}
}
}
}
// convert CNF-normalized operator tree to terms, a CNF AND-list of ALT-term lists
void CNF::OpTree::convert(Terms& terms)
{
if (op == OpTree::AND)
{
for (const auto& i : list)
{
if (!terms.back().empty())
terms.emplace_back();
if (i.op == OpTree::OR)
{
auto k = i.list.begin();
auto e = i.list.end();
while (k != e && (k->op != NONE || !k->regex.empty()))
++k;
if (k != e)
{
// empty pattern found, ignore all other patterns
k->add_to(terms);
}
else
{
for (const auto& j : i.list)
j.add_to(terms);
}
}
else
{
i.add_to(terms);
}
if (terms.back().empty())
{
// pop unused ending '|' (or BRE '\|')
terms.pop_back();
if (flag_mode == Mode::BRE)
terms.pop_back();
}
}
}
else if (op == OpTree::OR)
{
for (const auto& i : list)
i.add_to(terms);
}
else
{
add_to(terms);
}
}
// add a [NOT] term of the operator tree to terms
void CNF::OpTree::add_to(Terms& terms) const
{
Term& term = terms.back();
if (op == OpTree::NOT)
{
if (!regex.empty())
{
if (term.empty())
term.emplace_back();
else if (term.front() && term.front()->empty())
return; // empty pattern means anything matches
term.emplace_back(new std::string(regex));
}
}
else
{
if (term.empty())
term.emplace_back(new std::string(regex));
else if (!term.front())
term.front() = Pattern(new std::string(regex));
else if (term.front()->empty())
; // empty pattern means anything matches
else if (regex.empty())
term.front()->clear(); // empty pattern means anything matches
else
term.front()->append(flag_mode == Mode::BRE ? "\\|" : "|").append(regex);
// empty pattern means anything matches
if (term.front()->empty())
{
auto i = term.begin();
term.erase(++i, term.end());
}
}
}
// add an ALT pattern or ALT-NOT pattern, optionally negated (option -N)
void CNF::new_pattern(PATTERN mask, const char *pattern)
{
if (terms.empty())
terms.emplace_back();
if (flag_bool)
{
// --bool: compile to CNF
compile(pattern);
}
else
{
Term& term = terms.back();
// -e PATTERN, -N PATTERN, --and PATTERN, --not PATTERN
std::string spattern(pattern);
// -F
if (flag_mode == Mode::FIXED)
quote(spattern);
// -w and -x
anchor(spattern);
// -N PATTERN
if ((mask & PATTERN::NEG) && !spattern.empty())
spattern.insert(0, "(?^").append(")");
// --not
if ((mask & PATTERN::NOT))
{
if (!spattern.empty())
{
if (term.empty())
term.emplace_back();
else if (term.front() && term.front()->empty())
return; // empty pattern means anything matches
term.emplace_back(new std::string(spattern));
}
}
else
{
if (term.empty())
term.emplace_back(new std::string(spattern));
else if (!term.front())
term.front() = Pattern(new std::string(spattern));
else if (term.front()->empty())
; // empty pattern means anything matches
else if (spattern.empty())
term.front()->clear(); // empty pattern means anything matches
else
term.front()->append(flag_mode == Mode::BRE ? "\\|" : "|").append(spattern);
// empty pattern means anything matches
if (term.front()->empty())
{
auto i = term.begin();
term.erase(++i, term.end());
}
}
}
}
// prune empty ALT terms and ALT terms with empty patterns that match anything
void CNF::prune()
{
// -x: empty patterns match empty lines
if (flag_line_regexp)
return;
auto s = terms.begin();
auto e = terms.end();
auto i = s;
while (i != e)
{
// erase empty term and erase NULL term without ALT-NOT terms, unless the first term and -f FILE is specified
if ((i->empty() || (i->size() == 1 && (!i->front() || i->front()->empty()))) && (i != s || flag_file.empty()))
terms.erase(i++);
else
++i;
}
}
// split the patterns at \n and \r newlines, when present
void CNF::split()
{
// --bool: newlines not present (already converted)
if (flag_bool)
return;
const char *sep = flag_mode == Mode::FIXED ? "\\E|\\Q" : flag_mode == Mode::BRE ? "\\|" : "|";
for (auto& i : terms)
{
for (auto& j : i)
{
if (j)
{
std::string& pattern = *j;
size_t from = 0;
size_t to;
// split pattern at newlines, for -F add \Q \E to each string, separate by |
while ((to = pattern.find_first_of("\n\r", from)) != std::string::npos)
{
if (from < to)
{
size_t next = pattern.find_first_not_of("\n\r", to + 1);
if (next == std::string::npos)
{
pattern.resize(to);
break;
}
if (pattern.compare(next, std::string::npos, "\\E") == 0)
{
pattern.replace(to, std::string::npos, "\\E");
break;
}
pattern.replace(to, next - to, sep);
}
from = to + 1;
}
}
}
}
}
// report the CNF in readable form
void CNF::report(FILE *output) const
{
if (empty() && flag_file.empty())
return;
fprintf(output, flag_files ? "Files " : "Lines ");
if (flag_fuzzy > 0)
{
fprintf(output, "fuzzy-matched ");
if (flag_best_match)
fprintf(output, "as best matching ");
fprintf(output, "with max edit distance ");
if ((flag_fuzzy & reflex::FuzzyMatcher::INS))
fprintf(output, "+");
if ((flag_fuzzy & reflex::FuzzyMatcher::DEL))
fprintf(output, "-");
if ((flag_fuzzy & reflex::FuzzyMatcher::SUB))
fprintf(output, "~");
fprintf(output, "%zu", (flag_fuzzy & 0xff));
}
else
{
fprintf(output, "matched");
}
if (flag_ignore_case)
fprintf(output, " ignoring case");
fprintf(output, " if:" NEWLINESTR " ");
if (!flag_file.empty())
{
// -f FILE is combined with -e, --and, --andnot, --not
bool or_sep = false;
if (flag_mode == Mode::FIXED)
fprintf(output, "a string in ");
else
fprintf(output, "a pattern in ");
for (const auto& filename : flag_file)
{
if (or_sep)
fprintf(output, " or ");
fprintf(output, "%s", filename.c_str());
or_sep = true;
}
if (flag_invert_match)
fprintf(output, " does not match");
else
fprintf(output, " matches");
if (flag_line_regexp)
fprintf(output, " a line");
else if (flag_word_regexp)
fprintf(output, " a word");
if (flag_files)
fprintf(output, " on a line");
if (!terms.empty())
{
// if the first CNF term is left empty then we match -f FILE with additional constraints, i.e. not as an alternation
if (terms.front().empty())
fprintf(output, ", and" NEWLINESTR " ");
else
fprintf(output, " or ");
}
}
bool and_sep = false;
for (auto i = terms.begin(); i != terms.end(); ++i)
{
if (and_sep)
fprintf(output, ", and" NEWLINESTR " ");
bool or_sep = false;
for (auto j = i->begin(); j != i->end(); ++j)
{
if (*j)
{
if (or_sep)
fprintf(output, " or ");
if ((*j)->empty())
fprintf(output, "anything");
else
fprintf(output, "\"%s\"", (*j)->c_str());
if (j != i->begin())
{
fprintf(output, " does not match");
if (flag_files)
fprintf(output, " any line");
}
else
{
if (flag_invert_match)
fprintf(output, " does not match");
else
fprintf(output, " matches");
if (flag_line_regexp)
fprintf(output, " a line");
else if (flag_word_regexp)
fprintf(output, " a word");
if (flag_files)
fprintf(output, " on a line");
}
or_sep = true;
and_sep = true;
}
}
}
fprintf(output, NEWLINESTR);
}
// return all ALT terms of the CNF joined together
std::string CNF::adjoin() const
{
std::string adjoined;
const char *sep = flag_mode == Mode::BRE ? "\\|" : "|";
if (flag_files)
{
// --files: join all ALT and ALT-NOT terms
for (const auto& i : terms)
for (const auto& j : i)
if (j && !j->empty())
adjoined.append(*j).append(sep);
}
else
{
bool allnot = true;
for (const auto& i : terms)
{
if (i.size() <= 1)
{
allnot = false;
break;
}
}
// --lines: join all ALT terms unless all of them are paired with ALT-NOT terms
if (!allnot)
for (const auto& i : terms)
if (i.front() && !i.front()->empty())
adjoined.append(*i.front()).append(sep);
}
if (!adjoined.empty())
{
// pop unused ending '|' (or BRE '\|')
adjoined.pop_back();
if (flag_mode == Mode::BRE)
adjoined.pop_back();
}
return adjoined;
}
// return the first ALT terms of the CNF
std::string CNF::first() const
{
if (!terms.empty() && terms.front().front())
return *terms.front().front();
return "";
}