<commit_before>/*
	RGlobCore.cpp - "core" functionality of the RGlob "glob" pattern-matcher

	Copyright(c) 2016, <NAME>
	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.

	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 HOLDER 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 <algorithm>
#include <exception>
#include <iterator>
#include <iostream>
#include <iomanip>
#include "rglob.h"

using namespace std;
using namespace rglob;

static bool validateUTF8String(const char* s);

/*
	compile generates a "finite state machine" able to recognize text matching
	the supplied [UTF-8] pattern.
*/
void compiler::compile(const std::string& pattern)
{
	// make SURE pattern is *structurally* valid UTF8
	if (!validateUTF8String(pattern.c_str()))
		throw invalid_argument("Pattern string is not valid UTF-8.");
	fsm.clear();
	// prep for filling in compiled length of pattern later
	emit('#'), emitPadding(2);
	ptrdiff_t incr = 1;
	// iterate over, compile, and consume pattern elements
	for (auto pi = pattern.cbegin(); pi != pattern.cend(); pi += incr) {
		switch (*pi) {
		case '?':
			emit(*pi), incr = 1;
			break;
		case '*':
			emit(*pi), incr = 1;
			break;
		case '[':
			incr = compileClass(pattern, pi);
			break;
		default:
			incr = compileString(pattern, pi);
		}
		if (emitted() > AllowedMaxFSM)
			throw length_error(string("Exceeded allowed compiled pattern size @ ") + &*pi);
	}
	// NOW fill in length of compiled pattern... IFF there is any actual pattern
	auto const n = emitted();
	if (n > 1 + LengthSize)
		emitLengthAt(1, n - (1 + LengthSize));
	else
		fsm.clear();
}

/*
	match examines and the supplied [UTF-8] target text and attempts to match
	it against the previously compiled pattern, returning success/failure.
*/
bool matcher::match(const std::string& target) const
{
	// make SURE target is *structurally* valid UTF8
	if (!validateUTF8String(target.c_str()))
		throw invalid_argument("Target string is not valid UTF-8.");
	bool anchored = true, invert = false;
	utf8iteratorBare next;
	utf8iterator ti = target.cbegin();
	// iterate over the previously compiled pattern representation, consuming
	// recognized (matched) elements of the target text
	for (auto first = cbegin(), mi = first, last = cend(); mi != last;)
		switch (*mi++) {
		case '#':
			// "no-op" from the perspective of matching
			mi += LengthSize;
			break;
		case '?':
			// accept ("match") single target code point
			anchored = true, ++ti;
			break;
		case '*':
			// set "free" or "floating" match meta state; this MAY involve
			// "skipping over" zero or more target code points
			anchored = false;
			break;
		case '[':
			// prep for full "interpreted" UTF-8 character class recognition
			invert = decodeModifierAt(mi) != 0;
			next = mi + 1 + LengthSize + decodeLengthAt(mi + 1) + 1, mi += 1 + LengthSize;
			break;
		case '{':
			// perform "fast path" (all-ASCII) character class match
			if (anchored) {
				const auto tx = *ti;
				if (!(isascii(tx) && testPackedBitsetAt(mi, tx)))
					return false;
				// (consume target code point(s) and skip to after the ']')
				++ti, mi += 32;
			} else {
				auto i = find_if(ti, utf8iterator(target.cend()), [=](char32_t tx) { return isascii(tx) && testPackedBitsetAt(mi, tx); });
				if (i == target.cend())
					return false;
				// (consume target code point(s) and skip to after the ']')
				ti = ++i, anchored = true, mi += 32;
			}
			break;
		case '+': {
			// attempt to match single "interpreted" character class code point
			const auto p = *mi++;
			if (anchored) {
				const auto tx = *ti;
				if ((p == tx) ^ invert) {
					// (consume target code point(s) and skip to after the ']')
					++ti, mi = next;
					break;
				}
			} else {
				auto i = find_if(ti, utf8iterator(target.cend()), [=](char32_t tx) { return (p == tx) ^ invert; });
				if (i != target.cend()) {
					// (consume target code point(s) and skip to after the ']')
					ti = ++i, anchored = true, mi = next;
					break;
				}
			}
			break;
		}
		case '-': {
			// attempt to match "interpreted" character class "range" code point
			const auto p1 = *mi++, p2 = *mi++;
			if (anchored) {
				const auto tx = *ti;
				if ((p1 <= tx && tx <= p2) ^ invert) {
					// (consume target code point(s) and skip to after the ']')
					++ti, mi = next;
					break;
				}
			} else {
				auto i = find_if(ti, utf8iterator(target.cend()), [=](char32_t tx) { return (p1 <= tx && tx <= p2) ^ invert; });
				if (i != target.cend()) {
					// (consume target code point(s) and skip to after the ']')
					ti = ++i, anchored = true, mi = next;
					break;
				}
			}
			break;
		}
		case ']':
			// end of "interpreted" UTF-8 character class... if we get here, it
			// means we did NOT match ANY target code point - i.e., "failure"
			return false;
		case '=': {
			// attempt an exact sequence of UTF-8 code points match
			const auto n = decodeLengthAt(mi);
			const auto o = ti - target.cbegin();
			const auto i = target.find(mi + LengthSize, o, n);
			// (below means "not found" OR "found, but not where expected")
			if (i == string::npos || (anchored && i != o))
				return false;
			ti = anchored ? ti + n : target.cbegin() + i + n, anchored = true, mi += LengthSize + n;
			break;
		}
		}
	// return whether we [successfully] consumed ALL target text OR the pattern
	// ended in a "free" or "floating" match state (e.g.,  "ab*" matches "abZ")
	return ti == target.cend() || !anchored;
}<commit_msg>Trivial adjustment for yet another case where the Microsoft C++ compiler is more "accepting" than Clang.<commit_after>/*
	RGlobCore.cpp - "core" functionality of the RGlob "glob" pattern-matcher

	Copyright(c) 2016, <NAME>
	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.

	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 HOLDER 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 <algorithm>
#include <exception>
#include <iterator>
#include <iostream>
#include <iomanip>
#include "rglob.h"

using namespace std;
using namespace rglob;

static bool validateUTF8String(const char* s);

/*
	compile generates a "finite state machine" able to recognize text matching
	the supplied [UTF-8] pattern.
*/
void compiler::compile(const std::string& pattern)
{
	// make SURE pattern is *structurally* valid UTF8
	if (!validateUTF8String(pattern.c_str()))
		throw invalid_argument("Pattern string is not valid UTF-8.");
	fsm.clear();
	// prep for filling in compiled length of pattern later
	emit('#'), emitPadding(2);
	ptrdiff_t incr = 1;
	// iterate over, compile, and consume pattern elements
	for (auto pi = pattern.cbegin(); pi != pattern.cend(); pi += incr) {
		switch (*pi) {
		case '?':
			emit(*pi), incr = 1;
			break;
		case '*':
			emit(*pi), incr = 1;
			break;
		case '[':
			incr = compileClass(pattern, pi);
			break;
		default:
			incr = compileString(pattern, pi);
		}
		if (emitted() > AllowedMaxFSM)
			throw length_error(string("Exceeded allowed compiled pattern size @ ") + &*pi);
	}
	// NOW fill in length of compiled pattern... IFF there is any actual pattern
	auto const n = emitted();
	if (n > 1 + LengthSize)
		emitLengthAt(1, n - (1 + LengthSize));
	else
		fsm.clear();
}

/*
	match examines and the supplied [UTF-8] target text and attempts to match
	it against the previously compiled pattern, returning success/failure.
*/
bool matcher::match(const std::string& target) const
{
	// make SURE target is *structurally* valid UTF8
	if (!validateUTF8String(target.c_str()))
		throw invalid_argument("Target string is not valid UTF-8.");
	bool anchored = true, invert = false;
	utf8iteratorBare next;
	utf8iterator ti = target.cbegin();
	// iterate over the previously compiled pattern representation, consuming
	// recognized (matched) elements of the target text
	for (auto first = cbegin(), mi = first, last = cend(); mi != last;)
		switch (*mi++) {
		case '#':
			// "no-op" from the perspective of matching
			mi += LengthSize;
			break;
		case '?':
			// accept ("match") single target code point
			anchored = true, ++ti;
			break;
		case '*':
			// set "free" or "floating" match meta state; this MAY involve
			// "skipping over" zero or more target code points
			anchored = false;
			break;
		case '[':
			// prep for full "interpreted" UTF-8 character class recognition
			invert = decodeModifierAt(mi) != 0;
			next = mi + 1 + LengthSize + decodeLengthAt(mi + 1) + 1, mi += 1 + LengthSize;
			break;
		case '{':
			// perform "fast path" (all-ASCII) character class match
			if (anchored) {
				const auto tx = *ti;
				if (!(isascii(tx) && testPackedBitsetAt(mi, tx)))
					return false;
				// (consume target code point(s) and skip to after the ']')
				++ti, mi += 32;
			} else {
				auto i = find_if(ti, utf8iterator(target.cend()), [=](char32_t tx) { return isascii(tx) && testPackedBitsetAt(mi, tx); });
				if (i == target.cend())
					return false;
				// (consume target code point(s) and skip to after the ']')
				ti = ++i, anchored = true, mi += 32;
			}
			break;
		case '+': {
			// attempt to match single "interpreted" character class code point
			const auto p = *mi++;
			if (anchored) {
				const auto tx = *ti;
				if ((p == tx) ^ invert) {
					// (consume target code point(s) and skip to after the ']')
					++ti, mi = next;
					break;
				}
			} else {
				auto i = find_if(ti, utf8iterator(target.cend()), [=](char32_t tx) { return (p == tx) ^ invert; });
				if (i != target.cend()) {
					// (consume target code point(s) and skip to after the ']')
					ti = ++i, anchored = true, mi = next;
					break;
				}
			}
			break;
		}
		case '-': {
			// attempt to match "interpreted" character class "range" code point
			const auto p1 = *mi++, p2 = *mi++;
			if (anchored) {
				const auto tx = *ti;
				if ((p1 <= tx && tx <= p2) ^ invert) {
					// (consume target code point(s) and skip to after the ']')
					++ti, mi = next;
					break;
				}
			} else {
				auto i = find_if(ti, utf8iterator(target.cend()), [=](char32_t tx) { return (p1 <= tx && tx <= p2) ^ invert; });
				if (i != target.cend()) {
					// (consume target code point(s) and skip to after the ']')
					ti = ++i, anchored = true, mi = next;
					break;
				}
			}
			break;
		}
		case ']':
			// end of "interpreted" UTF-8 character class... if we get here, it
			// means we did NOT match ANY target code point - i.e., "failure"
			return false;
		case '=': {
			// attempt an exact sequence of UTF-8 code points match
			const auto n = decodeLengthAt(mi);
			const auto o = ti - target.cbegin();
			const auto i = target.find(mi + LengthSize, o, n);
			// (below means "not found" OR "found, but not where expected")
			if (i == string::npos || (anchored && i != o))
				return false;
			ti = anchored ? ti + n : utf8iterator(target.cbegin() + i + n), anchored = true, mi += LengthSize + n;
			break;
		}
		}
	// return whether we [successfully] consumed ALL target text OR the pattern
	// ended in a "free" or "floating" match state (e.g.,  "ab*" matches "abZ")
	return ti == target.cend() || !anchored;
}
{'fraction_non_alphanumeric': 0.12578378786734154, 'fraction_numerical': 0.0077812193095112185, 'mean_word_length': 3.3162699706553633, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 19, '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': '7408981', 'n_tokens_mistral': 4795, 'n_tokens_neox': 4088, 'n_words': 1625}