Compiler Explorer

Source code

#ifndef GLOB_PARSING_H
#define GLOB_PARSING_H

#include <functional>
#include <optional>
#include <string>
#include <string_view>
#include <tuple>

#include <absl/strings/str_cat.h>
#include <absl/strings/str_join.h>

#include "Combinators.h"
#include "Types.h"

namespace parse {
namespace details {

template<typename Tuple>
std::string tupleCat(Tuple tup) {
	return std::apply(
		[](auto&&... args) {
			return absl::StrCat(args...);
		},
		tup);
}

// Writing this as a lambda makes type inference work for some reason.
const auto vectorStrCat = [](auto&& vec) {
	return absl::StrJoin(vec, "");
};

}  // namespace details

// Matches the empty string. Fails on any non-empty string.
inline ParseResult<Unit> empty(std::string_view in) {
	if(in.empty()) {
		return Parse<Unit>{kUnit, in};
	}
	return std::nullopt;
}

// Matches the given character.
constexpr auto charOf(char c) {
	return [c](std::string_view in) -> ParseResult<std::string> {
		if(in.empty() || in[0] != c) {
			return std::nullopt;
		}
		return Parse<std::string>{std::string(1, c), in.substr(1)};
	};
}

// Matches any single character.
inline ParseResult<std::string> anyChar(std::string_view in) {
	if(in.empty()) {
		return std::nullopt;
	}
	return Parse<std::string>{std::string(1, in[0]), in.substr(1)};
}

// Matches any character except those given.
constexpr auto anyCharBut(std::string_view chars) {
	return [chars](std::string_view in) -> ParseResult<std::string> {
		if(in.empty()) {
			return std::nullopt;
		}
		for(const char c : chars) {
			if(in[0] == c) {
				return std::nullopt;
			}
		}
		return Parse<std::string>{std::string(1, in[0]), in.substr(1)};
	};
}

// Match the given string.
constexpr auto stringOf(std::string_view chars) {
	return [chars](std::string_view in) -> ParseResult<std::string> {
		if(!in.starts_with(chars)) {
			return std::nullopt;
		}
		return Parse<std::string>{std::string(chars), in.substr(chars.size())};
	};
}

constexpr auto escapedChar = takeRight(charOf('\\'), anyChar);

template<typename... Parsers>
constexpr auto strCatSequence(Parsers... parsers) {
	using Tuple = TYPE_OF(sequence(parsers...));

return map(details::tupleCat<Tuple>, sequence(parsers...));
}

template<typename Parser>
constexpr auto strCatRepeated(Parser parser) {
	return map(details::vectorStrCat, repeated(parser));
}

template<typename Parser>
constexpr auto strCatAtLeastOnce(Parser parser) {
	return map(details::vectorStrCat, atLeastOnce(parser));
}

template<typename Parser>
constexpr auto strMaybe(Parser parser) {
	return map(
		[](auto&& opt) -> std::string {
			return opt.value_or("");
		},
		maybe(parser));
}

}  // namespace parse

#endif  // GLOB_PARSING_H

Source code

#ifndef GLOB_COMBINATORS_H
#define GLOB_COMBINATORS_H

#include <string_view>
#include <vector>

#include "Types.h"

namespace parse {

// Matches the given parser and applies func to transform the matched result.
template<typename Func, typename Parser>
constexpr auto map(Func func, Parser parser) {
	return[func, parser](std::string_view in) {
		using T = TYPE_OF(parser);

auto result = parser(in);
		using MapT = decltype(func(result->result));

if(!result) {
			return ParseResult<MapT>(std::nullopt);
		}
		return ParseResult<MapT>(Parse<MapT>{func(result->result), result->rest});
	};
}

// Matches any parsers from the list (from left to right).
template<typename P>
constexpr auto any(P parser) {
	return[parser](std::string_view in) {
		return parser(in);
	};
}

template<typename Parser, typename... Parsers>
constexpr auto any(Parser parser, Parsers... parsers) {
	return[parser, parsers...](std::string_view in) {
		const auto result = parser(in);
		return result ? result : any(parsers...)(in);
	};
}

// Match the given parsers in order, concatenating their results.
template<typename Parser>
constexpr auto sequence(Parser parser)
{
	return[parser](std::string_view in) {
		using T = TYPE_OF(parser);
		using SeqResult = ParseResult<std::tuple<T>>;

const auto result = parser(in);
		if(!result)
		{
			return SeqResult(std::nullopt);
		}
		return SeqResult(Parse<std::tuple<T>>{std::make_tuple(result->result), result->rest});
	};
}

template<typename Parser, typename... Parsers>
constexpr auto sequence(Parser parser, Parsers... parsers) {
	return[parser, parsers...](std::string_view in) {
		using T = TYPE_OF(parser);
		using RestT = TYPE_OF(sequence(parsers...));
        using FooBar = decltype(std::tuple_cat(
				std::declval<std::tuple<T>>(),
				std::declval<RestT>()));
		using SeqResult = ParseResult<FooBar>;

std::string regex;
		const auto result = parser(in);
		if(!result) {
			return SeqResult(std::nullopt);
		}
		const auto restResult = sequence(parsers...)(result->rest);
		if(!restResult) {
			return SeqResult(std::nullopt);
		}
		const auto tup = std::tuple_cat(std::make_tuple(result->result), restResult->result);
		return SeqResult(Parse<FooBar>{tup, restResult->rest});
	};
}

// Repeatedly apply the given parser until it fails.
template<typename Parser>
constexpr auto repeated(Parser parser) {
	return[parser](std::string_view in) {
		using T = TYPE_OF(parser);

Parse<std::vector<T>> parse{std::vector<T>{}, in};
		while(const auto result = parser(parse.rest)) {
			parse.result.push_back(result->result);
			parse.rest = result->rest;
		}
		return std::optional(parse);
	};
}

template<typename Parser>
constexpr auto maybe(Parser parser) {
	return[parser](std::string_view in) {
		using T = TYPE_OF(parser);

const auto result = parser(in);
		if(!result) {
			return std::optional(Parse<std::optional<T>>{std::nullopt, in});
		}
		return std::optional(Parse<std::optional<T>>{result->result, result->rest});
	};
}

// Matches the given parser if it consumes the remaining input.
template<typename Parser>
constexpr auto terminal(Parser parser) {
	return[parser](std::string_view in) {
		using T = TYPE_OF(parser);

const auto result = parser(in);
		if(result->rest.empty()) {
			return ParseResult<T>(result);
		}
		return ParseResult<T>();
	};
}

// Repeatedly apply the given parser until it fails, it must match at least
// once.
template<typename Parser>
constexpr auto atLeastOnce(Parser parser) {
	using T = TYPE_OF(parser);

return map(
		[](auto result) {
			// Return a vector consisting of the head result followd by the rest of
			// the results.
			const auto& head = std::get<0>(result);
			const auto& rest = std::get<1>(result);

std::vector<T> vec{head};
			vec.reserve(rest.size() + 1);
			vec.insert(vec.end(), rest.begin(), rest.end());
			return vec;
		},
		sequence(parser, repeated(parser)));
}

// Matches two parsers, returning the first result and discarding the second.
template<typename Left, typename Right>
constexpr auto takeLeft(Left left, Right right) {
	using T = TYPE_OF(left);

return [left, right](std::string_view in) {
		const auto leftResult = left(in);
		if(!leftResult) {
			return ParseResult<T>(std::nullopt);
		}
		const auto rightResult = right(leftResult->rest);
		if(!rightResult) {
			return ParseResult<T>(std::nullopt);
		}
		return ParseResult<T>(Parse<T>{leftResult->result, rightResult->rest});
	};
}

// Matches two parsers, discarding the first result and returning the second.
template<typename Left, typename Right>
constexpr auto takeRight(Left left, Right right) {
	using T = TYPE_OF(right);

// Matches three parsers, discarding the first and last and returning the
// middle. This may be useful for matching delimited expressions like
// parantheses or quotes.
template<typename Left, typename Middle, typename Right>
constexpr auto takeMiddle(Left left, Middle middle, Right right) {
	return map(
		[](auto&& tup) {
			return std::get<1>(tup);
		},
		sequence(left, middle, right));
}

}  // namespace parse

#endif  // GLOB_COBINATORS_H

Source code

#include "ExpandBrace.h"

#include <algorithm>

#include "Parsing.h"

namespace parse {
namespace {

// Returns the size of the cartesian product of the vector of vectors.
size_t cartesianSize(const std::vector<std::vector<std::string>>& vectors) {
	size_t size = 1;
	for(const auto& vector : vectors) {
		size *= vector.size();
	}
	return size;
}

// Returns the longest string formed by the cartesian product of the vector of
// vectors where string product is taken to be concatenation.
size_t maxStringLength(const std::vector<std::vector<std::string>>& vectors) {
	size_t length = 0;
	for(const auto& vector : vectors) {
		size_t max = 0;
		for(const auto& str : vector) {
			max = std::max(max, str.size());
		}
		length += max;
	}
	return length;
}

// Returns the length of the flattened vector of vectors.
size_t nestedVectorLength(const std::vector<std::vector<std::string>>& vectors) {
	size_t length = 0;
	for(const auto& vector : vectors) {
		length += vector.size();
	}
	return length;
}

// Returns the cartesian product of the vector of vectors of strings, where
// string product is taken to be concatenation.
std::vector<std::string> cartesianCat(const std::vector<std::vector<std::string>>& vectors) {
	// Reserve enough space for the expanded vector and all of it's string ahead
	// of time.
	std::vector<std::string> expanded(cartesianSize(vectors));
	const size_t maxLength = maxStringLength(vectors);
	for(auto& str : expanded) {
		str.reserve(maxLength);
	}

// The expanded vector is divided into strides. Each of these is then
	// divided into vector.size() sections. Each section is appended with the
	// same part from the vector. This pattern is repeated until the entire
	// expanded vector has been traversed. This creates a repeating pattern like
	// this:
	// 
	//     Section
	//       /\
	//     112233112233112233  <- Expanded vector
	//     \    /
	//     Stride
	//
	// The stride length is then increased and the old stride length becomes the
	// new section length and the process is repeated for the next vector.
	size_t sectionLength = 1;
	for(const auto& vector : vectors) {
		const size_t strideLength = sectionLength * vector.size();
		for(size_t start = 0; start < expanded.size(); start += strideLength) {
			for(size_t section = 0; section < vector.size(); ++section) {
				const auto& part = vector[section];
				for(size_t i = 0; i < sectionLength; ++i) {
					expanded[start + section*sectionLength + i] += part;
				}
			}
		}
		sectionLength = strideLength;
	}
	return expanded;
}

// Flattens the given vector of vectors. The input vectors are moved from to
// minimize copying.
std::vector<std::string> vectorCat(std::vector<std::vector<std::string>>& vectors) {
	std::vector<std::string> result;
	result.reserve(nestedVectorLength(vectors));
	for(auto& vector : vectors) {
		for(auto& string : vector) {
			result.emplace_back(std::move(string));
		}
	}
	return result;
}

ParseResult<std::vector<std::string>> braceExpr(std::string_view in) {
	static constexpr auto plainText = map(
		[](const std::string& text) {
			return std::vector<std::string>{text};
		},
		strCatAtLeastOnce(any(
			anyCharBut(R"(\{},)"),
			escapedChar)));

static constexpr auto braceClause = map(
		cartesianCat,
		repeated(any(
			braceExpr,
			plainText)));

static constexpr auto braceExprParser = takeMiddle(
		charOf('{'),
		map(
			[](auto&& tup) {
				auto& vectors = std::get<0>(tup);
				auto& maybe = std::get<1>(tup);
				if(maybe) {
					vectors.emplace_back(std::move(*maybe));
				}
				return vectorCat(vectors);
			},
			sequence(
				atLeastOnce(takeLeft(braceClause, charOf(','))),
				maybe(braceClause))),
		charOf('}'));
	return braceExprParser(in);
}

}  // namespace

ParseResult<std::vector<std::string>> expandBraces(std::string_view in)
{
	static constexpr auto plainText = map(
		[](const std::string& text) {
			return std::vector<std::string>{text};
		},
		strCatAtLeastOnce(any(
			anyCharBut(R"(\{})"),
			escapedChar)));

// TODO: This can repeatedly take empty plaintext.
	static constexpr auto expandBracesParser = map(
		cartesianCat,
		repeated(any(
			braceExpr,
			plainText)));
	return expandBracesParser(in);
}

}  // namespace parse

Source code

#include "GlobParse.h"

#include <string>

#include <absl/strings/str_cat.h>
#include <absl/strings/str_join.h>
#include <absl/strings/substitute.h>

#include "Parsing.h"

namespace parse {
namespace {

// This glob grammar is based on minimatch https://github.com/isaacs/minimatch
// Not all functionality is implemented, and I don't think I agree with all of
// their decisions, but it was the best documented non-trivial glob grammar that
// I could find, and there is a useful testing tool at
// https://www.digitalocean.com/community/tools/glob.

static constexpr char kSeparatorChar[] = R"([/\\])";
static constexpr char kPathChar[] = R"([^/\\])";

// Arbitrary path separators are allowed at the end of any path.
constexpr auto end = map(
	[](auto&&) -> std::string {
		return absl::Substitute("$0*", kSeparatorChar);
	},
	empty);

// Matches one or more path separator characters. (Consecutive path separators
// are allowed in paths, but have no effect.)
constexpr auto separator = map(
	[](auto&&) -> std::string {
		return absl::Substitute("$0+", kSeparatorChar);;
	},
	atLeastOnce(any(charOf('/'), charOf('\\'))));

// Matches any single character except path separators.
constexpr auto question = map(
	[](auto&&) -> std::string {
		return kPathChar;
	},
	charOf('?'));

// Final * in a glob pattern can accept paths that end in path separators.
constexpr auto starTerminal = map(
	[](auto&&) -> std::string {
		return absl::Substitute("$0+$1*", kPathChar, kSeparatorChar);
	},
	terminal(charOf('*')));

// A path segment consisting only of * cannot accept an empty string.
constexpr auto starOnly = map(
	[](auto&&) -> std::string {
		return absl::Substitute("$0+", kPathChar);
	},
	charOf('*'));

// * as part of a path segment accepts 0 or more characters except path
// separators.
constexpr auto star = map(
	[](auto&&) -> std::string {
		return absl::Substitute("$0*", kPathChar);
	},
	charOf('*'));

// A final ** can match anything remaining in the path, including the empty
// string.
constexpr auto recursiveStarTerminal = map(
	[](auto&&) -> std::string {
		// A final ** can match anything, including the empty path.
		return ".*";
	},
	terminal(stringOf("**")));

// ** as a path segment (it must be the entire path segment) can match anything
// that ends with a separator. It can also match the empty string.
constexpr auto recursiveStar = map(
	[](auto&&) -> std::string {
		return absl::Substitute(".*$0+", kSeparatorChar);
	},
	sequence(stringOf("**"), separator));

constexpr auto doPathSegment =
strCatRepeated(any(star, question, anyCharBut(R"(/\)")));

constexpr auto pathSegment = any(starOnly, doPathSegment);
constexpr auto pathSegmentSep = any(recursiveStar, strCatSequence(pathSegment, separator));

}  // namespace

ParseResult<std::string> glob(std::string_view in)
{
	static constexpr auto globParser = terminal(
		strCatSequence(
			strMaybe(separator),
			strCatRepeated(pathSegmentSep),
			strMaybe(any(
				recursiveStarTerminal,
				starTerminal,
				pathSegment))));
	return globParser(in);
}

}  // namespace parse