/******************************************************************************\
* Copyright (c) 2016, 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 pattern.h
@brief RE/flex regular expression pattern compiler
@author Robert van Engelen - engelen@genivia.com
@copyright (c) 2016-2025, Robert van Engelen, Genivia Inc. All rights reserved.
@copyright (c) BSD-3 License - see LICENSE.txt
*/
#ifndef REFLEX_PATTERN_H
#define REFLEX_PATTERN_H
#include <reflex/bits.h>
#include <reflex/debug.h>
#include <reflex/error.h>
#include <reflex/input.h>
#include <reflex/ranges.h>
#include <reflex/setop.h>
#include <cstdint>
#include <cctype>
#include <cstring>
#include <iostream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <array>
#include <bitset>
#include <vector>
#include <stack>
// ugrep 7.0: use vectorized bitap (hashed) with AVX2, but it is not faster (in our extensive emperical testing)
// #define WITH_BITAP_AVX2
// ugrep 3.7.0a: use a map to construct fixed string pattern trees
// #define WITH_TREE_MAP
// ugrep 3.7.0b: use a DFA as a tree to bypass DFA construction step when possible
#define WITH_TREE_DFA
// Predict-match PM3+PM5 or PM4+PM4 chains (default PM4), benchmarking results favor PM3+PM5
#define WITH_PM3_PM5
// #define WITH_PM4_PM4
#if (defined(__WIN32__) || defined(_WIN32) || defined(WIN32) || defined(_WIN64) || defined(__BORLANDC__)) && !defined(__CYGWIN__) && !defined(__MINGW32__) && !defined(__MINGW64__)
# pragma warning( disable : 4290 )
#endif
namespace reflex {
/// Pattern class holds a regex pattern and its compiled FSM opcode table or code for the reflex::Matcher engine.
class Pattern {
friend class Matcher; ///< permit access by the reflex::Matcher engine
friend class FuzzyMatcher; ///< permit access by the reflex::FuzzyMatcher engine
public:
typedef uint8_t Bitap; ///< bitap bitmask, unsigned 8, 16 or 32 bit for 8, 16 or 32 BITS (number of characters matched)
typedef uint16_t Pred; ///< predict match bits for PM3+PM5 or PM4+PM4 to store 2x8 bits
typedef uint16_t Hash; ///< hash value type, max value is Const::HASH
typedef uint32_t Index; ///< index into opcodes array Pattern::opc_ and subpattern indexing
typedef uint32_t Accept; ///< group capture index
typedef uint32_t Opcode; ///< 32 bit opcode word
typedef void (*FSM)(class Matcher&); ///< function pointer to FSM code
/// Common constants.
struct Const {
static const Index IMAX = 0xffffffff; ///< max index, also serves as a marker
static const Index GMAX = 0xfeffff; ///< max goto index
static const Accept AMAX = 0xfdffff; ///< max accept
static const Index LMAX = 0xfaffff; ///< max lookahead index
static const Index LONG = 0xfffe; ///< LONG marker for 64 bit opcodes, must be HALT-1
static const Index HALT = 0xffff; ///< HALT marker for GOTO opcodes, must be 16 bit max
static const Hash HASH = 0x2000; ///< size of the predict match array (16K bytes)
static const Hash BTAP = 0x4000; ///< size of the bitap hashed character pairs array (16K bytes)
static const Bitap BITS = 8; ///< number of bitap bits <= 8*sizeof(Bitap) >= PM_M, may change in a future update
#if defined(WITH_PM3_PM5)
static const Pred PM_K = 3; ///< first predict-match step
static const Pred PM_M = 8; ///< total predict-match length 3+5 of PM3+PM5
#elif defined(WITH_PM4_PM4)
static const Pred PM_K = 4; ///< first predict-match step
static const Pred PM_M = 8; ///< total predict-match length 4+4 of PM4+PM4
#else
static const Pred PM_K = 4; ///< first predict-match step
static const Pred PM_M = 4; ///< total predict-match length 4 of PM4
#endif
};
/// Construct an unset pattern.
Pattern()
:
opc_(NULL),
fsm_(NULL),
nop_(0)
{
init(NULL);
}
/// Construct a pattern object given a regex string.
explicit Pattern(
const char *regex,
const char *options = NULL)
:
rex_(regex),
opc_(NULL),
fsm_(NULL)
{
init(options);
}
/// Construct a pattern object given a regex string.
Pattern(
const char *regex,
const std::string& options)
:
rex_(regex),
opc_(NULL),
fsm_(NULL)
{
init(options.c_str());
}
/// Construct a pattern object given a regex string.
explicit Pattern(
const std::string& regex,
const char *options = NULL)
:
rex_(regex),
opc_(NULL),
fsm_(NULL)
{
init(options);
}
/// Construct a pattern object given a regex string.
Pattern(
const std::string& regex,
const std::string& options)
:
rex_(regex),
opc_(NULL),
fsm_(NULL)
{
init(options.c_str());
}
/// Construct a pattern object given a FSM opcode table and predictor table.
explicit Pattern(
const Opcode *code,
const char *pred = NULL)
:
opc_(code),
fsm_(NULL)
{
init(NULL, pred);
}
/// Construct a pattern object given a function pointer to FSM code and predictor table.
explicit Pattern(
FSM fsm,
const char *pred = NULL)
:
opc_(NULL),
fsm_(fsm)
{
init(NULL, pred);
}
/// Copy constructor.
Pattern(const Pattern& pattern) ///< pattern to copy
{
operator=(pattern);
}
/// Destructor, deletes internal code array when owned and allocated.
virtual ~Pattern()
{
clear();
}
/// Clear and delete pattern data.
void clear()
{
rex_.clear();
if (nop_ > 0 && opc_ != NULL)
delete[] opc_;
opc_ = NULL;
nop_ = 0;
fsm_ = NULL;
}
/// Assign a (new) pattern.
Pattern& assign(
const char *regex,
const char *options = NULL)
{
clear();
rex_ = regex;
init(options);
return *this;
}
/// Assign a (new) pattern.
Pattern& assign(
const char *regex,
const std::string& options)
{
return assign(regex, options.c_str());
}
/// Assign a (new) pattern.
Pattern& assign(
const std::string& regex,
const char *options = NULL)
{
return assign(regex.c_str(), options);
}
/// Assign a (new) pattern.
Pattern& assign(
const std::string& regex,
const std::string& options)
{
return assign(regex.c_str(), options.c_str());
}
/// Assign a (new) pattern given a FSM opcode table and predictor table.
Pattern& assign(
const Opcode *code,
const char *pred = NULL)
{
clear();
opc_ = code;
init(NULL, pred);
return *this;
}
/// Assign a (new) pattern given a function pointer to FSM code and predictor table.
Pattern& assign(
FSM fsm,
const char *pred = NULL)
{
clear();
fsm_ = fsm;
init(NULL, pred);
return *this;
}
/// Assign a (new) pattern.
Pattern& operator=(const Pattern& pattern)
{
clear();
opt_ = pattern.opt_;
rex_ = pattern.rex_;
end_ = pattern.end_;
acc_ = pattern.acc_;
vno_ = pattern.vno_;
eno_ = pattern.eno_;
pms_ = pattern.pms_;
vms_ = pattern.vms_;
ems_ = pattern.ems_;
wms_ = pattern.wms_;
if (pattern.nop_ > 0 && pattern.opc_ != NULL)
{
nop_ = pattern.nop_;
Opcode *code = new Opcode[nop_];
for (size_t i = 0; i < nop_; ++i)
code[i] = pattern.opc_[i];
opc_ = code;
}
else
{
fsm_ = pattern.fsm_;
}
return *this;
}
/// Assign a (new) pattern.
Pattern& operator=(const char *regex)
{
return assign(regex);
}
/// Assign a (new) pattern.
Pattern& operator=(const std::string& regex)
{
return assign(regex);
}
/// Assign a (new) pattern.
Pattern& operator=(const Opcode *code)
{
return assign(code);
}
/// Assign a (new) pattern.
Pattern& operator=(FSM fsm)
{
return assign(fsm);
}
/// Get the number of subpatterns of this pattern object.
Accept size() const
/// @returns number of subpatterns
{
return static_cast<Accept>(end_.size());
}
/// Return true if this pattern is not assigned.
bool empty() const
/// @return true if this pattern is not assigned
{
return opc_ == NULL && fsm_ == NULL;
}
/// Get subpattern regex of this pattern object or the whole regex with index 0.
const std::string operator[](Accept choice) const
/// @returns subpattern string or "" when not set
;
/// Check if subpattern is reachable by a match.
bool reachable(Accept choice) const
/// @returns true if subpattern is reachable
{
return choice >= 1 && choice <= size() && acc_.at(choice - 1);
}
/// Get the number of finite state machine nodes (vertices).
size_t nodes() const
/// @returns number of nodes or 0 when no finite state machine was constructed by this pattern
{
return nop_ > 0 ? vno_ : 0;
}
/// Get the number of finite state machine edges (transitions on input characters).
size_t edges() const
/// @returns number of edges or 0 when no finite state machine was constructed by this pattern
{
return nop_ > 0 ? eno_ : 0;
}
/// Get the code size in number of words.
size_t words() const
/// @returns number of words or 0 when no code was generated by this pattern
{
return nop_;
}
/// Get the total number of indexing hash tables constructed for the optional HFA.
size_t hashes() const
/// @returns number of HFA hashes total for all HFA edges
{
return hno_;
}
/// Get elapsed regex parsing and analysis time.
float parse_time() const
/// @returns time in ms
{
return pms_;
}
/// Get elapsed DFA vertices construction time.
float nodes_time() const
/// @returns time in ms
{
return vms_;
}
/// Get elapsed DFA edges construction time.
float edges_time() const
/// @returns time in ms
{
return ems_;
}
/// Get elapsed code words assembly time.
float words_time() const
/// @returns time in ms
{
return wms_;
}
/// Get elapsed time of DFA analysis to predict matches and construct an optional HFA.
float analysis_time() const
/// @returns time in ms
{
return ams_;
}
#if defined(WITH_PM3_PM5)
/// Returns true when match is predicted using my PM3+PM5 logic for min>=1.
inline bool predict_match(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00);
Pred m0 = ((((p0 >> 2) | p0) >> 1) | p0);
if (m0 >= 0xfc00)
return false;
if (m0 != 0xf680)
return true;
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint8_t c4 = static_cast<uint8_t>(s[4]);
uint8_t c5 = static_cast<uint8_t>(s[5]);
uint8_t c6 = static_cast<uint8_t>(s[6]);
uint8_t c7 = static_cast<uint8_t>(s[7]);
uint32_t h3 = hash(h2, c3);
uint32_t h4 = hash(h3, c4);
uint32_t h5 = hash(h4, c5);
uint32_t h6 = hash(h5, c6);
uint32_t h7 = hash(h6, c7);
Pred p1 = (pma_[h3] & 0x0300) | (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);
Pred m1 = ((((((((p1 >> 2) | p1) >> 2) | p1) >> 2) | p1) >> 1) | p1);
return m1 != 0x03ff;
}
/// Returns true when match is predicted using my PM3 logic for min>=1 prior to PM3+PM5.
inline bool predict_match_quick(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00);
Pred m0 = ((((p0 >> 2) | p0) >> 1) | p0);
return m0 < 0xfc00;
}
/// Returns true when match is predicted using my PM3+PM5 logic for min>=3.
inline bool predict_match_min(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
Pred p0 = (pma_[c0] & 0x4000) | (pma_[h1] & 0x1000) | (pma_[h2] & 0x0c00);
if (p0 > 0x0400)
return false;
if (p0 == 0)
return true;
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint8_t c4 = static_cast<uint8_t>(s[4]);
uint8_t c5 = static_cast<uint8_t>(s[5]);
uint8_t c6 = static_cast<uint8_t>(s[6]);
uint8_t c7 = static_cast<uint8_t>(s[7]);
uint32_t h3 = hash(h2, c3);
uint32_t h4 = hash(h3, c4);
uint32_t h5 = hash(h4, c5);
uint32_t h6 = hash(h5, c6);
uint32_t h7 = hash(h6, c7);
Pred p1 = (pma_[h3] & 0x0300) | (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);
Pred m1 = ((((((((p1 >> 2) | p1) >> 2) | p1) >> 2) | p1) >> 1) | p1);
return m1 != 0x03ff;
}
#elif defined(WITH_PM4_PM4)
/// Returns true when match is predicted using my PM4+PM4 logic for min>=1.
inline bool predict_match(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
uint32_t h3 = hash(h2, c3);
Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00) | (pma_[h3] & 0x0300);
Pred m0 = ((((((p0 >> 2) | p0) >> 2) | p0) >> 1) | p0);
if (m0 >= 0xff00)
return false;
if (m0 != 0xfde8)
return true;
uint8_t c4 = static_cast<uint8_t>(s[4]);
uint8_t c5 = static_cast<uint8_t>(s[5]);
uint8_t c6 = static_cast<uint8_t>(s[6]);
uint8_t c7 = static_cast<uint8_t>(s[7]);
uint32_t h4 = hash(h3, c4);
uint32_t h5 = hash(h4, c5);
uint32_t h6 = hash(h5, c6);
uint32_t h7 = hash(h6, c7);
Pred p1 = (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);
Pred m1 = ((((((p1 >> 2) | p1) >> 2) | p1) >> 1) | p1);
return m1 != 0x00ff;
}
/// Returns true when match is predicted using my PM4 logic for min>=1 prior to PM4+PM4.
inline bool predict_match_quick(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
uint32_t h3 = hash(h2, c3);
Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00) | (pma_[h3] & 0x0300);
Pred m0 = ((((((p0 >> 2) | p0) >> 2) | p0) >> 1) | p0);
return m0 < 0xff00;
}
/// Returns true when match is predicted using my PM4+PM4 logic for min>=4.
inline bool predict_match_min(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
uint32_t h3 = hash(h2, c3);
Pred p0 = (pma_[c0] & 0x4000) | (pma_[h1] & 0x1000) | (pma_[h2] & 0x0400) | (pma_[h3] & 0x0300);
if (p0 > 0x0100)
return false;
if (p0 == 0)
return true;
uint8_t c4 = static_cast<uint8_t>(s[4]);
uint8_t c5 = static_cast<uint8_t>(s[5]);
uint8_t c6 = static_cast<uint8_t>(s[6]);
uint8_t c7 = static_cast<uint8_t>(s[7]);
uint32_t h4 = hash(h3, c4);
uint32_t h5 = hash(h4, c5);
uint32_t h6 = hash(h5, c6);
uint32_t h7 = hash(h6, c7);
Pred p1 = (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);
Pred m1 = ((((((p1 >> 2) | p1) >> 2) | p1) >> 1) | p1);
return m1 != 0x00ff;
}
#else
/// Returns true when match is predicted using my PM4 logic for min>=1.
inline bool predict_match(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
uint32_t h3 = hash(h2, c3);
Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00) | (pma_[h3] & 0x0300);
Pred m0 = ((((((p0 >> 2) | p0) >> 2) | p0) >> 1) | p0);
return m0 < 0xff00;
}
/// Returns true when match is predicted (not used)
inline bool predict_match_quick(const char *) const
{
return true;
}
/// Returns true when match is predicted using my PM4 logic for min>=4.
inline bool predict_match_min(const char *s) const
{
uint8_t c0 = static_cast<uint8_t>(s[0]);
uint8_t c1 = static_cast<uint8_t>(s[1]);
uint8_t c2 = static_cast<uint8_t>(s[2]);
uint8_t c3 = static_cast<uint8_t>(s[3]);
uint32_t h1 = hash(c0, c1);
uint32_t h2 = hash(h1, c2);
uint32_t h3 = hash(h2, c3);
Pred p0 = (pma_[c0] & 0x4000) | (pma_[h1] & 0x1000) | (pma_[h2] & 0x0400) | (pma_[h3] & 0x0300);
return p0 <= 0x0100;
}
#endif
/// Relative frequency of English letters with upper/lower-case ratio = 0.0563, punctuation and UTF-8 bytes.
static uint8_t frequency(uint8_t c)
{
static unsigned char freq[256] =
// x64 binary frequencies combined with ASCII TAB/LF/CR control code frequencies
"\377\101\14\22\15\21\10\10\24\73\41\10\11\41\6\51"
"\16\4\3\3\3\3\3\3\6\3\3\2\3\4\4\12"
// TAB/LF/CR control code frequencies in text
// "\0\0\0\0\0\0\0\0\0\73\41\0\0\41\0\0"
// "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
// ASCII frequencies
"\377\0\1\1\0\0\16\33\6\6\7\0\27\11\27\14"
"\13\14\10\5\4\5\4\4\4\7\12\21\10\14\10\0"
"\0\11\2\3\5\16\2\2\7\10\0\1\4\3\7\10"
"\2\0\6\7\12\3\1\3\0\2\0\70\1\70\0\1"
"\0\237\35\64\133\373\53\47\170\205\3\20\115\64\202\227"
"\45\2\162\170\272\64\23\56\3\47\2\3\15\3\0\0"
// upper half with UTF-8 multibyte frequencies (synthesized from Unicode tables)
"\47\47\47\47\47\47\47\47\47\47\47\47\47\47\47\47"
"\45\45\45\45\45\45\45\45\45\45\45\45\45\45\45\45"
"\45\45\45\45\45\45\45\45\45\45\45\45\45\45\45\45"
"\42\44\42\44\44\44\44\44\44\44\44\44\42\44\44\44"
"\0\0\5\5\5\5\0\5\5\5\5\5\5\5\0\5"
"\0\5\5\5\0\5\5\5\5\5\5\5\5\5\5\5"
"\40\72\76\100\100\100\100\100\100\100\76\100\100\40\100\77"
"\73\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
return freq[c];
}
protected:
/// Throw an error.
virtual void error(
regex_error_type code, ///< error code
size_t pos = 0) ///< optional location of the error in regex string Pattern::rex_
const;
private:
typedef uint8_t Mod;
typedef uint16_t Char; // 8 bit char and meta chars up to META_MAX-1
typedef uint8_t Lazy;
typedef uint16_t Iter;
typedef uint16_t Lookahead;
typedef std::set<Lookahead> Lookaheads;
typedef uint32_t Location;
typedef ORanges<Location> Locations;
typedef std::map<int,Locations> Map;
typedef Locations Mods[10];
/// Modifiers 'i', 'm', 'q', 's', 'u' (enable) 'I', 'M', 'Q', 'S', 'U' (disable)
struct ModConst {
static const Mod i = 0;
static const Mod I = 1;
static const Mod m = 2;
static const Mod M = 3;
static const Mod q = 4;
static const Mod Q = 5;
static const Mod s = 6;
static const Mod S = 7;
static const Mod u = 8;
static const Mod U = 9;
};
/// Set of chars and meta chars
struct Chars {
Chars() { clear(); }
Chars(const Chars& c) { b[0] = c.b[0]; b[1] = c.b[1]; b[2] = c.b[2]; b[3] = c.b[3]; b[4] = c.b[4]; }
Chars(const uint64_t c[5]) { b[0] = c[0]; b[1] = c[1]; b[2] = c[2]; b[3] = c[3]; b[4] = c[4]; }
void clear() { b[0] = b[1] = b[2] = b[3] = b[4] = 0ULL; }
bool any() const { return b[0] | b[1] | b[2] | b[3] | b[4]; }
bool intersects(const Chars& c) const { return (b[0] & c.b[0]) | (b[1] & c.b[1]) | (b[2] & c.b[2]) | (b[3] & c.b[3]) | (b[4] & c.b[4]); }
bool contains(const Chars& c) const { return !(c - *this).any(); }
bool contains(Char c) const { return b[c >> 6] & (1ULL << (c & 0x3f)); }
Chars& add(Char c) { b[c >> 6] |= 1ULL << (c & 0x3f); return *this; }
Chars& add(Char lo, Char hi) { while (lo <= hi) add(lo++); return *this; }
Chars& flip() { b[0] = ~b[0]; b[1] = ~b[1]; b[2] = ~b[2]; b[3] = ~b[3]; b[4] = ~b[4]; return *this; }
Chars& flip256() { b[0] = ~b[0]; b[1] = ~b[1]; b[2] = ~b[2]; b[3] = ~b[3]; return *this; }
Chars& swap(Chars& c) { Chars t = c; c = *this; return *this = t; }
Chars& operator+=(const Chars& c) { return operator|=(c); }
Chars& operator-=(const Chars& c) { b[0] &=~c.b[0]; b[1] &=~c.b[1]; b[2] &=~c.b[2]; b[3] &=~c.b[3]; b[4] &=~c.b[4]; return *this; }
Chars& operator|=(const Chars& c) { b[0] |= c.b[0]; b[1] |= c.b[1]; b[2] |= c.b[2]; b[3] |= c.b[3]; b[4] |= c.b[4]; return *this; }
Chars& operator&=(const Chars& c) { b[0] &= c.b[0]; b[1] &= c.b[1]; b[2] &= c.b[2]; b[3] &= c.b[3]; b[4] &= c.b[4]; return *this; }
Chars& operator^=(const Chars& c) { b[0] ^= c.b[0]; b[1] ^= c.b[1]; b[2] ^= c.b[2]; b[3] ^= c.b[3]; b[4] ^= c.b[4]; return *this; }
Chars operator+(const Chars& c) const { return Chars(*this) += c; }
Chars operator-(const Chars& c) const { return Chars(*this) -= c; }
Chars operator|(const Chars& c) const { return Chars(*this) |= c; }
Chars operator&(const Chars& c) const { return Chars(*this) &= c; }
Chars operator^(const Chars& c) const { return Chars(*this) ^= c; }
Chars operator~() const { return Chars(*this).flip(); }
operator bool() const { return any(); }
Chars& operator=(const Chars& c) { b[0] = c.b[0]; b[1] = c.b[1]; b[2] = c.b[2]; b[3] = c.b[3]; b[4] = c.b[4]; return *this; }
bool operator!=(const Chars& c) const { return (b[0] ^ c.b[0]) | (b[1] ^ c.b[1]) | (b[2] ^ c.b[2]) | (b[3] ^ c.b[3]) | (b[4] ^ c.b[4]); }
bool operator==(const Chars& c) const { return !(c != *this); }
bool operator<(const Chars& c) const { return b[0] < c.b[0] || (b[0] == c.b[0] && (b[1] < c.b[1] || (b[1] == c.b[1] && (b[2] < c.b[2] || (b[2] == c.b[2] && (b[3] < c.b[3] || (b[3] == c.b[3] && b[4] < c.b[4]))))))); }
bool operator>(const Chars& c) const { return c < *this; }
bool operator<=(const Chars& c) const { return !(c < *this); }
bool operator>=(const Chars& c) const { return !(*this < c); }
Char lo() const { for (Char i = 0; i < 5; ++i) if (b[i]) for (Char j = 0; j < 64; ++j) if (b[i] & (1ULL << j)) return (i << 6) + j; return 0; }
Char hi() const { for (Char i = 0; i < 5; ++i) if (b[4-i]) for (Char j = 0; j < 64; ++j) if (b[4-i] & (1ULL << (63-j))) return ((4-i) << 6) + (63-j); return 0; }
uint64_t b[5]; ///< 256 bits to store a set of 8-bit chars + extra bits for meta
};
/// Finite state machine construction position information.
struct Position {
typedef uint64_t value_type;
static const Iter MAXITER = 0xffff;
static const Location MAXLOC = 0xffffffffUL;
static const value_type NPOS = 0xffffffffffffffffULL;
static const value_type RES1 = 1ULL << 48; ///< reserved
static const value_type RES2 = 1ULL << 49; ///< reserved
static const value_type RES3 = 1ULL << 50; ///< reserved
static const value_type NEGATE = 1ULL << 51; ///< marks negative patterns
static const value_type TICKED = 1ULL << 52; ///< marks lookahead ending ) in (?=X)
static const value_type RES4 = 1ULL << 53; ///< reserved
static const value_type ANCHOR = 1ULL << 54; ///< marks begin of word (\b,\<,\>) and buffer (\A,^) anchors
static const value_type ACCEPT = 1ULL << 55; ///< accept, not a regex position
Position() : k(NPOS) { }
Position(value_type k) : k(k) { }
Position(const Position& p) : k(p.k) { }
Position& operator=(const Position& p) { k = p.k; return *this; }
operator value_type() const { return k; }
Position iter(Iter i) const { return Position(k + (static_cast<value_type>(i) << 32)); }
Position negate(bool b) const { return b ? Position(k | NEGATE) : Position(k & ~NEGATE); }
Position ticked(bool b) const { return b ? Position(k | TICKED) : Position(k & ~TICKED); }
Position anchor(bool b) const { return b ? Position(k | ANCHOR) : Position(k & ~ANCHOR); }
Position accept(bool b) const { return b ? Position(k | ACCEPT) : Position(k & ~ACCEPT); }
Position lazy(Lazy l) const { return Position((k & 0x00ffffffffffffffULL) | static_cast<value_type>(l) << 56); }
Position pos() const { return Position(k & 0x0000ffffffffffffULL); }
Location loc() const { return static_cast<Location>(k); }
Accept accepts() const { return static_cast<Accept>(k); }
Iter iter() const { return static_cast<Index>((k >> 32) & 0xffff); }
bool negate() const { return (k & NEGATE) != 0; }
bool ticked() const { return (k & TICKED) != 0; }
bool anchor() const { return (k & ANCHOR) != 0; }
bool accept() const { return (k & ACCEPT) != 0; }
Lazy lazy() const { return static_cast<Lazy>(k >> 56); }
value_type k;
};
typedef std::vector<Position> Lazypos;
typedef std::vector<Position> Positions;
typedef std::map<Position,Positions> Follow;
typedef std::pair<Chars,Positions> Move;
typedef std::list<Move> Moves;
static inline void pos_insert(Positions& s1, const Positions& s2) { s1.insert(s1.end(), s2.begin(), s2.end()); }
static inline void pos_add(Positions& s, const Position& e) { s.insert(s.end(), e); }
static inline void lazy_insert(Lazypos& s1, const Lazypos& s2) { s1.insert(s1.end(), s2.begin(), s2.end()); }
static inline void lazy_add(Lazypos& s, const Lazy i, Location p) { s.insert(s.end(), Position(p).lazy(i)); }
#ifndef WITH_TREE_DFA
/// Tree DFA constructed from string patterns.
struct Tree {
#ifdef WITH_TREE_MAP
struct Node {
Node()
:
accept(0)
{ }
std::map<Char,Node> edges; ///< edges to next tree nodes
Accept accept; ///< nonzero if final state, the index of an accepted/captured subpattern
};
Tree()
:
tree(NULL)
{ }
~Tree()
{
clear();
}
/// delete the tree and all subnodes.
void clear()
{
if (tree != NULL)
delete tree;
tree = NULL;
}
/// return the root of the tree.
Node *root()
{
return tree != NULL ? tree : (tree = new Node);
}
/// create an edge from a tree node to a target tree node, return the target tree node.
Node *edge(Node *node, Char c)
{
return &node->edges[c];
}
Node *tree; ///< root of the tree or NULL
#else
struct Node {
Node()
:
accept(0)
{
for (int i = 0; i < 16; ++i)
edge[i] = NULL;
}
~Node()
{
for (int i = 0; i < 16; ++i)
if (edge[i] != NULL)
delete[] edge[i];
}
Node **edge[16]; ///< 16x16 edges, one per 8-bit char
Accept accept; ///< nonzero if final state, the index of an accepted/captured subpattern
};
typedef std::list<Node*> List;
static const uint16_t ALLOC = 1024; ///< allocate 1024 nodes at a time, to improve performance
Tree()
:
tree(NULL),
next(ALLOC)
{ }
~Tree()
{
clear();
}
/// delete the tree DFA and reset to the intial state.
void clear()
{
for (List::iterator i = list.begin(); i != list.end(); ++i)
delete[] *i;
list.clear();
tree = NULL;
next = ALLOC;
}
/// return the root of the tree.
Node *root()
{
return tree != NULL ? tree : (tree = leaf());
}
/// create an edge from a tree node to a target tree node, return the target tree node.
Node *edge(Node *node, Char c)
{
Node **p = node->edge[c >> 4];
if (p != NULL)
return p[c & 0xf] != NULL ? p[c & 0xf] : (p[c & 0xf] = leaf());
p = node->edge[c >> 4] = new Node*[16];
for (int i = 0; i < 16; ++i)
p[i] = NULL;
return p[c & 0xf] = leaf();
}
/// create a new leaf node.
Node *leaf()
{
if (next >= ALLOC)
{
list.push_back(new Node[ALLOC]);
next = 0;
}
return &list.back()[next++];
}
Node *tree; ///< root of the tree or NULL
List list; ///< block allocation list
uint16_t next; ///< block allocation, next available slot in last block
#endif
};
#endif
/// DFA created by subset construction from regex patterns.
struct DFA {
struct State : Positions {
typedef std::pair<Char,State*> Edge; ///< hi of char range [lo,hi] and state to transition to
typedef std::map<Char,Edge> Edges; ///< maps lo to hi and state to transition to on char in range [lo,hi]
State()
:
next(NULL),
left(NULL),
right(NULL),
tnode(NULL),
first(0),
index(0),
accept(0),
redo(false)
{ }
#ifndef WITH_TREE_DFA
State *assign(Tree::Node *node)
{
tnode = node;
return this;
}
State *assign(Tree::Node *node, Positions& pos)
{
tnode = node;
this->swap(pos);
return this;
}
#endif
State *next; ///< points to next state in the list of states allocated depth-first by subset construction
State *left; ///< left pointer for O(log N) node insertion in the hash table overflow tree
State *right; ///< right pointer for O(log N) node insertion in the hash table overflow tree
#ifdef WITH_TREE_DFA
State *tnode; ///< the corresponding tree DFA node, when applicable
#else
Tree::Node *tnode; ///< the corresponding tree DFA node, when applicable
#endif
Edges edges; ///< state transitions
Lookaheads heads; ///< lookahead head set
Lookaheads tails; ///< lookahead tail set
Index first; ///< index of this state in the opcode table in the first assembly pass, also used in breadth-first search to cut DFA for predict match
Index index; ///< index of this state in the opcode table, also used in HFA construction
Accept accept; ///< nonzero if final state, the index of an accepted/captured subpattern
bool redo; ///< true if this is a final state of a negative pattern
};
// transitive closure of DFA meta edges; no follow metas to accepting states and no follow cycles
struct MetaEdgesClosure {
MetaEdgesClosure(State& state)
{
edge = state.edges.begin();
end = state.edges.end();
accept = state.accept > 0 || state.edges.empty();
walk();
}
MetaEdgesClosure(State *state)
{
edge = state->edges.begin();
end = state->edges.end();
accept = state->accept > 0 || state->edges.empty();
walk();
}
~MetaEdgesClosure()
{
// clean up markers
while (!done())
++edge;
}
MetaEdgesClosure& operator++()
{
++edge;
walk();
return *this;
}
Char lo() const
{
return edge->first;
}
Char hi() const
{
return edge->second.first;
}
State *state() const
{
return edge->second.second; // target state is non-NULL by walk()
}
bool accepting() const
{
return accept;
}
bool next_accepting() const
{
if (state() == NULL || state()->accept > 0 || state()->edges.empty())
return true;
return is_meta(state()->edges.rbegin()->first) && MetaEdgesClosure(state()).find_accepting();
}
bool find_accepting()
{
while (!done() && !accepting())
{
++edge;
walk();
}
return accepting();
}
bool done()
{
while (edge == end)
{
if (stack.empty())
return true;
// restore previous iterators
edge = stack.top().first;
end = stack.top().second;
stack.pop();
// unmark state visited
state()->index = 0;
++edge;
}
return false;
}
void walk()
{
if (done())
return;
// walk the DFA graph acyclicly until non-meta edge to a non-NULL state
while (is_meta(lo()) || state() == NULL)
{
// find non-empty non-visited non-accepting state on a meta edge
State *next_state;
do
{
next_state = state();
if (next_state == NULL || next_state->accept > 0 || next_state->edges.empty())
accept = true;
else if (next_state->index != 1)
break;
++edge;
if (done())
return;
} while (is_meta(lo()) || next_state == NULL);
// save current iterators
stack.push(std::pair<State::Edges::const_iterator,State::Edges::const_iterator>(edge,end));
// mark state as visited
next_state->index = 1;
// new iterators
edge = next_state->edges.begin();
end = next_state->edges.end();
}
}
std::stack<std::pair<State::Edges::const_iterator,State::Edges::const_iterator> > stack;
State::Edges::const_iterator edge;
State::Edges::const_iterator end;
bool accept;
};
typedef std::list<State*> List;
static const uint16_t ALLOC = 1024; ///< allocate 1024 DFA states at a time, to improve performance
static const uint16_t MAX_DEPTH = 256; ///< analyze DFA up to states this deep to improve predict match
static const Index MAX_STATES = Const::GMAX/3;///< maximum number of DFA states is constrained by opcode table size
static const Index MAX_EDGES = 16*Const::GMAX;///< maximum number of DFA edges is constrained by opcode table size
static const Index MAX_POSITIONS = 4194304; ///< maximum accumulated positions over all DFA states
static const Index DEAD_PATH = 1; ///< state marker "path always and only reaches backedges" (a dead end)
static const Index KEEP_PATH = MAX_DEPTH; ///< state marker "required path" (from a newline edge)
static const Index LOOP_PATH = MAX_DEPTH + 1; ///< state marker "path reaches a backedge" (collect lookback chars)
DFA()
:
next(ALLOC),
pno(0)
{ }
~DFA()
{
clear();
}
/// delete DFA and reset to initial state.
void clear()
{
for (List::iterator i = list.begin(); i != list.end(); ++i)
delete[] *i;
list.clear();
next = ALLOC;
pno = 0;
}
#ifdef WITH_TREE_DFA
/// new DFA state.
State *state()
{
if (next >= ALLOC)
{
list.push_back(new State[ALLOC]);
next = 0;
}
return &list.back()[next++];
}
/// new DFA state with positions, destroys pos.
State *state(Positions& pos)
{
State *s = state();
pno += pos.size();
s->swap(pos);
return s;
}
/// new DFA state with optional tree DFA node and positions.
State *state(State *tnode)
{
State *s = state();
s->tnode = tnode;
return s;
}
/// new DFA state with optional tree DFA node and positions, destroys pos.
State *state(State *tnode, Positions& pos)
{
State *s = state(tnode);
pno += pos.size();
s->swap(pos);
return s;
}
/// root of the DFA is the first state created or NULL.
State *root()
{
return list.empty() ? NULL : list.front();
}
/// start state the DFA is the first state created.
State *start()
{
return list.empty() ? state() : list.front();
}
#else
/// new DFA state with optional tree DFA node.
State *state(Tree::Node *node)
{
if (next >= ALLOC)
{
list.push_back(new State[ALLOC]);
next = 0;
}
return list.back()[next++].assign(node);
}
/// new DFA state with optional tree DFA node and positions, destroys pos.
State *state(Tree::Node *node, Positions& pos)
{
if (next >= ALLOC)
{
list.push_back(new State[ALLOC]);
next = 0;
}
pno += pos.size();
return list.back()[next++].assign(node, pos);
}
#endif
List list; ///< block allocation list
uint16_t next; ///< block allocation, next available slot in last block
size_t pno; ///< total positions accumulated in DFA states, to check against MAX_POSITIONS
};
/// Indexing hash finite state automaton for indexed file search.
struct HFA {
static const size_t MAX_DEPTH = 16; ///< max hashed pattern length must be between 3 and 16, long is accurate
static const size_t MAX_CHAIN = 8; ///< max length of hashed chars chain must be between 2 and 8 (8 is optimal)
static const size_t MAX_STATES = 1024; ///< max number of states must be 256 or greater
static const size_t MAX_RANGES = 262144; ///< max number of hashes ranges on an edge to the next state
typedef ORanges<Hash> HashRange;
typedef std::array<HashRange,MAX_DEPTH> HashRanges;
typedef std::map<DFA::State*,HashRanges> StateHashes;
typedef Index State;
typedef std::map<State,HashRanges> Hashes;
typedef std::set<State> StateSet;
typedef std::map<State,StateSet> States;
typedef std::bitset<MAX_STATES> VisitSet;
Hashes hashes[MAX_DEPTH];
States states;
};
/// Global modifier modes, syntax flags, and compiler options.
struct Option {
Option() : b(), h(), e(), f(), g(0), i(), m(), n(), o(), p(), q(), r(), s(), w(), x(), z() { }
bool b; ///< disable escapes in bracket lists
bool h; ///< construct indexing hash finite state automaton
Char e; ///< escape character, or > 255 for none, a backslash by default
std::vector<std::string> f; ///< output the patterns and/or DFA to files(s)
int g; ///< debug level 0,1,2: output a cut DFA graphviz file with option f, predict match and HFA states
bool i; ///< case insensitive mode, also `(?i:X)`
bool m; ///< multi-line mode, also `(?m:X)`
std::string n; ///< pattern name (for use in generated code)
bool o; ///< generate optimized FSM code with option f
bool p; ///< with option f also output predict match array for fast search with find()
bool q; ///< enable "X" quotation of verbatim content, also `(?q:X)`
bool r; ///< raise syntax errors as exceptions
bool s; ///< single-line mode (dotall mode), also `(?s:X)`
bool w; ///< write error message to stderr
bool x; ///< free-spacing mode, also `(?x:X)`
std::string z; ///< namespace (NAME1.NAME2.NAME3)
};
/// Meta characters.
enum Meta {
META_MIN = 0x100,
// word boundaries
META_WBB = 0x101, ///< word boundary at begin `\bx`
META_WBE = 0x102, ///< word boundary at end `x\b`
META_NWB = 0x103, ///< non-word boundary at begin `\Bx`
META_NWE = 0x104, ///< non-word boundary at end `x\B`
META_BWB = 0x105, ///< begin of word at begin `\<x`
META_EWB = 0x106, ///< end of word at begin `\>x`
META_BWE = 0x107, ///< begin of word at end `x\<`
META_EWE = 0x108, ///< end of word at end `x\>`
// line and buffer boundaries
META_BOL = 0x109, ///< begin of line `^`
META_EOL = 0x10a, ///< end of line `$`
META_BOB = 0x10b, ///< begin of buffer `\A`
META_EOB = 0x10c, ///< end of buffer `\Z`
// indent boundaries
META_UND = 0x10d, ///< undent boundary `\k`
META_IND = 0x10e, ///< indent boundary `\i` (must be one but the largest META code)
META_DED = 0x10f, ///< dedent boundary `\j` (must be the largest META code)
// end of boundaries
META_MAX ///< max meta characters
};
/// Initialize the pattern at construction.
void init(
const char *options,
const char *pred = NULL);
void init_options(const char *options);
void parse(
Positions& startpos,
Follow& followpos,
Lazypos& lazypos,
Mods modifiers,
Map& lookahead);
void parse1(
bool begin,
Location& loc,
Positions& firstpos,
Positions& lastpos,
bool& nullable,
Follow& followpos,
Lazy& lazyidx,
Lazypos& lazypos,
Mods modifiers,
Locations& lookahead,
Iter& iter);
void parse2(
bool begin,
Location& loc,
Positions& firstpos,
Positions& lastpos,
bool& nullable,
Follow& followpos,
Lazy& lazyidx,
Lazypos& lazypos,
Mods modifiers,
Locations& lookahead,
Iter& iter);
void parse3(
bool begin,
Location& loc,
Positions& firstpos,
Positions& lastpos,
bool& nullable,
Follow& followpos,
Lazy& lazyidx,
Lazypos& lazypos,
Mods modifiers,
Locations& lookahead,
Iter& iter);
void parse4(
bool begin,
Location& loc,
Positions& firstpos,
Positions& lastpos,
bool& nullable,
Follow& followpos,
Lazy& lazyidx,
Lazypos& lazypos,
Mods modifiers,
Locations& lookahead,
Iter& iter);
Char parse_esc(
Location& loc,
Chars *chars = NULL) const;
void compile(
DFA::State *start,
Follow& followpos,
const Lazypos& lazypos,
const Mods modifiers,
const Map& lookahead);
void lazy(
const Lazypos& lazypos,
Positions& pos) const;
void lazy(
const Lazypos& lazypos,
const Positions& pos,
Positions& pos1) const;
void greedy(Positions& pos) const;
void trim_anchors(Positions& follow) const;
void trim_lazy(Positions *pos, const Lazypos& lazypos) const;
void compile_transition(
DFA::State *state,
Follow& followpos,
const Lazypos& lazypos,
const Mods modifiers,
const Map& lookahead,
Moves& moves) const;
void transition(
Moves& moves,
Chars& chars,
const Positions& follow) const;
void compile_list(
Location loc,
Chars& chars,
const Mods modifiers) const;
void posix(
size_t index,
Chars& chars) const;
void flip(Chars& chars) const;
void assemble(DFA::State *start);
void compact_dfa(DFA::State *start);
void encode_dfa(DFA::State *start);
void gencode_dfa(const DFA::State *start) const;
void check_dfa_closure(
const DFA::State *state,
int nest,
bool& peek) const;
void gencode_dfa_closure(
FILE *fd,
const DFA::State *start,
int nest,
bool peek) const;
void graph_dfa(const DFA::State *start) const;
void export_code() const;
void analyze_dfa(DFA::State *start);
void gen_min(std::set<DFA::State*>& states);
void gen_predict_match(std::set<DFA::State*>& states);
void gen_predict_match_start(std::set<DFA::State*>& states, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& first_hashes);
void gen_predict_match_transitions(uint16_t level, DFA::State *state, const std::pair<ORanges<Hash>,ORanges<Char> >& previous, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& level_hashes, bool& saturated);
void gen_match_hfa(DFA::State *start);
void gen_match_hfa_start(DFA::State *start, HFA::State& index, HFA::StateHashes& hashes);
bool gen_match_hfa_transitions(size_t level, size_t& max_level, DFA::State *state, const HFA::HashRanges& previous, HFA::State& index, HFA::StateHashes& hashes);
public:
bool has_hfa() const
{
return !hfa_.states.empty();
}
bool match_hfa(const uint8_t *indexed, size_t size) const;
private:
bool match_hfa_transitions(size_t level, const HFA::Hashes& hashes, const uint8_t *indexed, size_t size, HFA::VisitSet& visit, HFA::VisitSet& next_visit, bool& accept) const;
void write_predictor(FILE *fd) const;
void write_namespace_open(FILE *fd) const;
void write_namespace_close(FILE *fd) const;
size_t find_at(
Location loc,
char c) const
{
return rex_.find_first_of(c, loc);
}
Char at(Location k) const
{
return static_cast<unsigned char>(rex_[k]);
}
bool eq_at(
Location loc,
const char *s) const
{
return rex_.compare(loc, strlen(s), s) == 0;
}
Char escape_at(Location loc) const
{
if (at(loc) == opt_.e)
return at(loc + 1);
return '\0';
}
Char escapes_at(
Location loc,
const char *escapes) const
{
if (at(loc) == opt_.e && std::strchr(escapes, at(loc + 1)))
return at(loc + 1);
return '\0';
}
static inline bool is_modified(
Mod mod,
const Mods modifiers,
Location loc)
{
return modifiers[mod].find(loc) != modifiers[mod].end();
}
static inline void update_modified(
Mod mod,
Mods modifiers,
Location from,
Location to)
{
// modifiers i, m, s, u
Locations modified(from, to);
modified -= modifiers[mod ^ 1];
modifiers[mod] += modified;
}
static inline uint16_t hash_pos(const Positions *pos)
{
uint16_t h = 0;
for (Positions::const_iterator i = pos->begin(); i != pos->end(); ++i)
h += h + static_cast<uint16_t>(*i ^ (*i >> 24));
return h;
}
static inline bool valid_goto_index(Index index)
{
return index <= Const::GMAX;
}
static inline bool valid_take_index(Index index)
{
return index <= Const::AMAX;
}
static inline bool valid_lookahead_index(Index index)
{
return index <= Const::LMAX;
}
static inline bool is_meta(Char c)
{
return c > META_MIN;
}
static inline Opcode opcode_long(Index index)
{
return 0xff000000 | (index & 0xffffff); // index <= Const::GMAX (0xfeffff max)
}
static inline Opcode opcode_take(Index index)
{
return 0xfe000000 | (index & 0xffffff); // index <= Const::AMAX (0xfdffff max)
}
static inline Opcode opcode_redo()
{
return 0xfd000000;
}
static inline Opcode opcode_tail(Index index)
{
return 0xfc000000 | (index & 0xffffff); // index <= Const::LMAX (0xfaffff max)
}
static inline Opcode opcode_head(Index index)
{
return 0xfb000000 | (index & 0xffffff); // index <= Const::LMAX (0xfaffff max)
}
static inline Opcode opcode_goto(
Char lo,
Char hi,
Index index)
{
return is_meta(lo) ? (static_cast<Opcode>(lo) << 24) | index : (static_cast<Opcode>(lo) << 24) | (hi << 16) | index;
}
static inline Opcode opcode_halt()
{
return 0x00ffffff;
}
static inline bool is_opcode_long(Opcode opcode)
{
return (opcode & 0xff000000) == 0xff000000;
}
static inline bool is_opcode_take(Opcode opcode)
{
return (opcode & 0xfe000000) == 0xfe000000;
}
static inline bool is_opcode_redo(Opcode opcode)
{
return opcode == 0xfd000000;
}
static inline bool is_opcode_tail(Opcode opcode)
{
return (opcode & 0xff000000) == 0xfc000000;
}
static inline bool is_opcode_head(Opcode opcode)
{
return (opcode & 0xff000000) == 0xfb000000;
}
static inline bool is_opcode_halt(Opcode opcode)
{
return opcode == 0x00ffffff;
}
static inline bool is_opcode_goto(Opcode opcode)
{
return (opcode << 8) >= (opcode & 0xff000000);
}
static inline bool is_opcode_meta(Opcode opcode)
{
return (opcode & 0x00ff0000) == 0x00000000 && (opcode >> 24) > 0;
}
static inline bool is_opcode_goto(
Opcode opcode,
unsigned char c)
{
return c >= (opcode >> 24) && c <= ((opcode >> 16) & 0xff);
}
static inline Char meta_of(Opcode opcode)
{
return META_MIN + (opcode >> 24);
}
static inline Char lo_of(Opcode opcode)
{
return is_opcode_meta(opcode) ? meta_of(opcode) : opcode >> 24;
}
static inline Char hi_of(Opcode opcode)
{
return is_opcode_meta(opcode) ? meta_of(opcode) : (opcode >> 16) & 0xff;
}
static inline Index index_of(Opcode opcode)
{
return opcode & 0xffff;
}
static inline Index long_index_of(Opcode opcode)
{
return opcode & 0xffffff;
}
static inline Lookahead lookahead_of(Opcode opcode)
{
return opcode & 0xffff;
}
/// check if lower case
static inline bool islowercase(Char c)
{
return (c >= 'a' && c <= 'z');
}
/// check if upper case
static inline bool isuppercase(Char c)
{
return (c >= 'A' && c <= 'Z');
}
/// check if lower or upper case
static inline bool isanycase(Char c)
{
return islowercase(c) || isuppercase(c);
}
/// convert to lower case if c is a letter a-z, A-Z.
static inline Char lowercase(Char c)
{
return static_cast<unsigned char>(c | 0x20);
}
/// convert to upper case if c is a letter a-z, A-Z.
static inline Char uppercase(Char c)
{
return static_cast<unsigned char>(c & ~0x20);
}
/// predict match hash 0 <= hash() < Const::HASH, must be additive: hash(h,b+1) = hash(h,b)+1 modulo Const::HASH.
static inline uint32_t hash(uint32_t h, uint8_t b)
{
return ((h << 3) - h + b) & (Const::HASH - 1);
}
/// bitap character pairs hash.
static inline uint32_t bihash(uint8_t a, uint8_t b)
{
return (a ^ (static_cast<uint32_t>(b) << 6)) & (Const::BTAP - 1);
}
/// file indexing hash 0 <= indexhash() < 65536, must be additive: indexhash(x,b+1) = indexhash(x,b)+1 modulo 2^16.
static inline uint32_t indexhash(Hash h, uint8_t b)
{
return static_cast<uint16_t>((h << 6) - h - h - h + b);
}
Option opt_; ///< pattern compiler options
HFA hfa_; ///< indexing hash finite state automaton
#ifdef WITH_TREE_DFA
DFA tfa_; ///< tree DFA constructed from strings
#else
Tree tfa_; ///< tree DFA constructed from strings
#endif
DFA dfa_; ///< DFA constructed from regex with subset construction using firstpos/lastpos/followpos
std::string rex_; ///< regular expression string
std::vector<Location> end_; ///< entries point to the subpattern's ending '|' or '\0'
std::vector<bool> acc_; ///< true if subpattern n is accepting (state is reachable)
uint32_t vno_; ///< number of finite state machine vertices |V| (nodes)
uint32_t eno_; ///< number of finite state machine edges |E| (arrows)
uint32_t hno_; ///< number of indexing hash tables (HFA edges)
const Opcode *opc_; ///< points to the table with compiled finite state machine opcodes
FSM fsm_; ///< function pointer to FSM code
Index nop_; ///< number of opcodes generated
Index cut_; ///< DFA s-t cut to improve predict match and HFA accuracy with lbk_ and cbk_
uint16_t len_; ///< length of chr_[], less or equal to 255
uint16_t min_; ///< patterns after the prefix are at least this long but no more than Const::BITS
uint16_t pin_; ///< number of needles, 0 to 16
std::bitset<256> cbk_; ///< characters to look back over when lbk_ > 0, never includes \n
std::bitset<256> fst_; ///< the beginning characters of the pattern
char chr_[256]; ///< pattern prefix string or character needles for needle-based search
Bitap bit_[256]; ///< bitsets of characters for the first positions (one position per bit)
Bitap tap_[Const::BTAP]; ///< bitap hashed character pairs array
#ifdef WITH_BITAP_AVX2 // in case vectorized bitap (hashed) is faster than serial version (typically not!)
#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)
uint16_t vtp_[Const::BTAP * 4]; ///< AVX2 vectorized bitap hashed character pairs array
#endif
#endif
Pred pma_[Const::HASH]; ///< predict-match array
uint16_t lbk_; ///< lookback distance or 0xffff unlimited lookback or 0 for no lookback (empty cbk_)
uint16_t lbm_; ///< loopback minimum distance when lbk_ > 0
uint16_t lcp_; ///< primary least common character position in the pattern or 0xffff
uint16_t lcs_; ///< secondary least common character position in the pattern or 0xffff
uint16_t bmd_; ///< Boyer-Moore jump distance on mismatch, B-M is enabled when bmd_ > 0 (<= 255)
uint8_t bms_[256]; ///< Boyer-Moore skip array
float pms_; ///< ms elapsed time to parse regex
float vms_; ///< ms elapsed time to compile DFA vertices
float ems_; ///< ms elapsed time to compile DFA edges
float wms_; ///< ms elapsed time to assemble code words
float ams_; ///< ms elapsed time to analyze DFA for predict match and HFA
uint16_t npy_; ///< entropy derived from the bitap array bit_[]
bool one_; ///< true if matching one string stored in chr_[] without meta/anchors
bool bol_; ///< true if matching all patterns at the begin of a line with anchor ^
};
} // namespace reflex
#endif