<commit_before>#include "parlex/detail/parser.hpp"

#include <iterator>
#include <stack>

#include "parlex/post_processor.hpp"

#include "parlex/detail/context.hpp"
#include "parlex/detail/grammar_base.hpp"
#include "parlex/detail/job.hpp"
#include "parlex/detail/permutation.hpp"
#include "parlex/detail/producer.hpp"
#include "parlex/detail/subjob.hpp"

#include "utils.hpp"
#include "bits.hpp"

namespace parlex {
namespace detail {

void parser::start_workers(int threadCount) {
	for (; threadCount > 0; --threadCount) {
		workers.emplace_back([=]() {
			//DBG("thread ", threadCount, " started");
			std::unique_lock<std::mutex> lock(mutex);
			goto wait;
			while (!terminating) {
				{
					//DBG("THREAD ", threadCount, " POPPING ITEM");
					auto item = work.back();
					work.pop_back();
					lock.unlock();
					auto const & c = *std::get<0>(item);
					auto const nextDfaState = std::get<1>(item);
					update_progress(c);
					//INF("thread ", threadCount, " executing DFA state");	
					c.owner.machine.process(c, nextDfaState);
					c.owner.end_work_queue_reference();
					if (--active_count == 0) {
						halt_cv.notify_one();
					}
					lock.lock();
				}
			wait:
				work_cv.wait(lock, [this]() { return work.size() > 0 || terminating; });
			}
		});
	}
}

parser::parser(unsigned const threadCount) : single_thread_mode(threadCount == 1), active_count(0), terminating(false) {
	if (!single_thread_mode) {
		start_workers(threadCount);
	}
}

parser::~parser() {
	terminating = true;
	work_cv.notify_all();
	for (auto & thread : workers) {
		thread.join();
	}
}

abstract_syntax_semilattice parser::construct_result_and_postprocess(size_t const overrideRootRecognizerIndex, std::vector<post_processor> const & posts, std::u32string const & document, job & j) {
	auto result = construct_result(j, match(match_class(0, overrideRootRecognizerIndex, 0), document.size()));
	if (!posts.empty()) {
		for (auto const & post : posts) {
			post(result);
		}
		if (result.is_rooted()) {
			result.prune_detached();
		}
	}
	return result;
}

void parser::complete_progress_handler(job & j) {
	j.update_progress(j.document.length());
}

void parser::update_progress(context const & context) {
	context.owner.owner.update_progress(context.current_document_position);
}

abstract_syntax_semilattice parser::single_thread_parse(grammar_base const & g, size_t const overrideRootRecognizerIndex, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const progressHandler) {
	//perf_timer timer("parse");
	job j(*this, document, g, overrideRootRecognizerIndex, progressHandler);
	throw_assert(active_count > 0);
	while (true) {
		while (work.size() > 0) {
			auto item = work.back();
			work.pop_back();
			auto const & c = *std::get<0>(item);
			auto const nextDfaState = std::get<1>(item);
			update_progress(c);	
			//INF("thread ", threadCount, " executing DFA state");
			c.owner.machine.process(c, nextDfaState);
			c.owner.end_work_queue_reference();
			--active_count;
		}
		throw_assert(active_count == 0);
		//DBG("parser is idle; checking for deadlocks");
		if (handle_deadlocks(j)) {
			break;
		}
	}
	throw_assert(active_count == 0);
	complete_progress_handler(j);
	return construct_result_and_postprocess(overrideRootRecognizerIndex, posts, document, j);
}

abstract_syntax_semilattice parser::multi_thread_parse(grammar_base const & g, size_t const overrideRootRecognizerIndex, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const progressHandler) {
	//perf_timer timer("parse");
	std::unique_lock<std::mutex> lock(mutex); //use the lock to make sure we see activeCount != 0
	job j(*this, document, g, overrideRootRecognizerIndex, progressHandler);
	throw_assert(active_count > 0);
	while (true) {
		halt_cv.wait(lock, [this]() { return active_count == 0; });
		//DBG("parser is idle; checking for deadlocks");
		if (handle_deadlocks(j)) {
			break;
		}
	}
	throw_assert(active_count == 0);
	complete_progress_handler(j);
	return construct_result_and_postprocess(overrideRootRecognizerIndex, posts, document, j);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, recognizer const & overrideMain, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const & progressHandler) {
	auto const overrideRootRecognizerIndex = g.lookup_recognizer_index(overrideMain);
	if (single_thread_mode) {
		return single_thread_parse(g, overrideRootRecognizerIndex, posts, document, progressHandler);
	}
	return multi_thread_parse(g, overrideRootRecognizerIndex, posts, document, progressHandler);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, recognizer const & overrideMain, std::u32string const & document, progress_handler_t const & progressHandler) {
	return parse(g, overrideMain, std::vector<post_processor>(), document, progressHandler);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const & progressHandler) {
	return parse(g, g.get_root_state_machine(), posts, document, progressHandler);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, std::u32string const & document, progress_handler_t const & progressHandler) {
	return parse(g, g.get_root_state_machine(), document, progressHandler);
}

void parser::schedule(context const & c, int nextDfaState) {
	//DBG("scheduling m: ", c.owner().machine.name, " b:", c.owner().documentPosition, " s:", nextDfaState, " p:", c.current_document_position());
	c.owner.begin_work_queue_reference();
	++active_count;
	std::unique_lock<std::mutex> lock(mutex);
	work.emplace_back(&c, nextDfaState);
	work_cv.notify_one();
}

bool parser::handle_deadlocks(job const & j) const {
	throw_assert(active_count == 0);
	//perf_timer timer("handle_deadlocks");

	//build a dependency graph and detect cyclical portions that should be halted
	//if no subjobs remain, return true
	//otherwise return false (still work to be done)

	std::stack<std::pair<match_class, match_class>> s;

	//Examine subscriptions from one subjob to another to construct the graph
	std::map<match_class, std::set<match_class>> directSubscriptions;
	std::map<match_class, std::set<match_class>> allSubscriptions;
	for (size_t documentPosition = 0; documentPosition < j.producers->document_length; ++documentPosition) {
		for (size_t recognizerIndex = 0; recognizerIndex < j.producers->recognizer_count; ++recognizerIndex) {
			match_class const matchClass(documentPosition, recognizerIndex, 0);
			auto const & storage = (*j.producers)(matchClass);
			if (!storage) {
				continue;
			}
			auto const & producer = *storage;
			auto const & recognizer = j.g.get_recognizer(producer.recognizer_index);
			if (recognizer.is_terminal() || producer.completed) {
				continue;
			}
			for (auto const & subscription : producer.consumers) {
				auto const & c = subscription.c;
				match_class temp(c.owner.document_position, c.owner.recognizer_index, 0);
				allSubscriptions[matchClass].insert(temp);
				directSubscriptions[matchClass].insert(temp);
				s.push(std::pair<match_class, match_class>(matchClass, temp));
			}
		}
	}

	//Apply transitivity to the graph
	while (s.size() > 0) {
		auto entry = s.top();
		s.pop();
		for (auto const & next : directSubscriptions[entry.first]) {
			if (allSubscriptions[entry.first].insert(next).second) {
				s.push(std::pair<match_class, match_class>(entry.first, next));
			}
		}
	}

	auto anyHalted = false;
	//halt subjobs that are subscribed to themselves (in)directly
	for (auto const & i : allSubscriptions) {
		auto const & matchClass = i.first;
		auto & p = *(*j.producers)(matchClass);
		if (i.second.count(matchClass) > 0) {
			p.terminate();
			anyHalted = true;
		}
	}
	return !anyHalted;
}

struct node_props_t {
	match const m;
	std::set<permutation> & permutations;
	std::map<match, std::set<permutation>> parent_permutations_by_match;
	size_t height;
	std::set<match> all_descendents;
	std::set<match> all_ancestors;
	std::set<match> all_descendents_and_ancestors;
	std::set<match> all_unrelated_intersections;

	node_props_t(abstract_syntax_semilattice & asg, match const & m) : m(m), permutations(asg.permutations_of_matches[m]), height(0) {
	}
};

static bool can_prune(abstract_syntax_semilattice & asg, std::map<match, node_props_t> const & nodes, node_props_t const & props) {
	if (!(props.m < asg.root || asg.root < props.m)) {
		return false;
	}
	for (auto const & parentMatchAndPermutations : props.parent_permutations_by_match) {
		auto const & parentMatch = parentMatchAndPermutations.first;
		auto const i = nodes.find(parentMatch);
		throw_assert(i != nodes.end());
		auto const & parentProps = i->second;
		auto const & parentPermutations = parentMatchAndPermutations.second;
		if (parentProps.permutations.size() == parentPermutations.size()) { //if all parent permutations depend on this, then we can only prune if the parent can be pruned
			if (!can_prune(asg, nodes, parentProps)) {
				return false;
			}
		}
	}
	return true;
}

static void prune(abstract_syntax_semilattice & asg, std::map<match, node_props_t> & nodes, node_props_t & props) {
	std::queue<match> toPrune;
	std::set<match> completed;
	std::function<void(match const &)> const add = [&](match const & m) {
		if (completed.insert(m).second) {
			toPrune.push(m);
		}
	};
	add(props.m);
	while (!toPrune.empty()) {
		auto const thisMatch = toPrune.front();
		auto & thisNode = nodes.find(thisMatch)->second;
		toPrune.pop();
		for (auto const & parentMatchAndPermutations : thisNode.parent_permutations_by_match) {
			auto const & parentMatch = parentMatchAndPermutations.first;
			auto const i = nodes.find(parentMatch);
			throw_assert(i != nodes.end());
			auto & parentProps = i->second;
			auto const & parentPermutations = parentMatchAndPermutations.second;
			for (auto const & perm : parentPermutations) {
				parentProps.permutations.erase(perm);
			}
			if (parentProps.permutations.size() == 0) {
				add(parentMatch);
			}
		}
		for (auto const & descendentMatch : thisNode.all_descendents) {
			auto const i = nodes.find(descendentMatch);
			throw_assert(i != nodes.end());
			auto & descendent = i->second;
			descendent.all_ancestors.erase(thisMatch);
			if (descendent.all_ancestors.empty()) {
				add(descendentMatch);
			}
			descendent.all_descendents_and_ancestors.erase(thisMatch);
			descendent.parent_permutations_by_match.erase(thisMatch);
		}
		for (auto const & ancestorMatch : thisNode.all_ancestors) {
			auto const i = nodes.find(ancestorMatch);
			throw_assert(i != nodes.end());
			auto & ancestor = i->second;
			ancestor.all_descendents.erase(thisMatch);
			ancestor.all_descendents_and_ancestors.erase(thisMatch);
		}
		for (auto const & intersectorMatch : thisNode.all_unrelated_intersections) {
			auto const i = nodes.find(intersectorMatch);
			throw_assert(i != nodes.end());
			auto & intersector = i->second;
			intersector.all_unrelated_intersections.erase(thisMatch);
		}
	}

	for (auto const & i : completed) {
		nodes.erase(i);
		asg.permutations_of_matches.erase(i);
	}
}

static void construct_nodes(abstract_syntax_semilattice & asg, std::map<match, node_props_t> & nodes, std::vector<std::set<node_props_t *>> & flattened) {
	for (auto const & matchAndPermutations : asg.permutations_of_matches) {
		auto const & m = matchAndPermutations.first;
		auto & nodeProps = nodes.emplace(std::piecewise_construct, std::forward_as_tuple(m), std::forward_as_tuple(asg, m)).first->second;

		for (auto const & perm : nodeProps.permutations) {
			for (match const & child : perm) {
				auto & childProps = nodes.emplace(std::piecewise_construct, std::forward_as_tuple(child), std::forward_as_tuple(asg, child)).first->second;
				if (childProps.permutations.empty()) {
					childProps.height = 0;
				}
				childProps.parent_permutations_by_match[nodeProps.m].insert(perm);
			}
		}
		auto const afterIndex = nodeProps.m.document_position + nodeProps.m.consumed_character_count;
		for (auto i = nodeProps.m.document_position; i < afterIndex; ++i) {
			flattened[i].insert(&nodeProps);
		}
	}
}

static void resolve_nodes(std::map<match, node_props_t> & nodes) {
	//work queue for the algorithm
	std::queue<std::tuple<node_props_t *, node_props_t *, int>> propertyResolveQueue;

	for (auto & entry : nodes) {
		auto & props = entry.second;
		//seed algorithm with "match A has all of match A's permutation's matches as descendants"
		propertyResolveQueue.push(std::make_tuple(&props, &props, 0));
	}

	//containment algorithm
	//match A contains all of match B's permutation's matches
	while (!propertyResolveQueue.empty()) {
		auto entry = propertyResolveQueue.front();
		propertyResolveQueue.pop();
		auto & left = *std::get<0>(entry);
		auto & right = *std::get<1>(entry);
		size_t const leftsHeightMinusRightsHeight = std::get<2>(entry);
		if (right.height == 0) { //if right is a leaf
			left.height = std::max(leftsHeightMinusRightsHeight, left.height);
		}
		for (auto const & perm : right.permutations) {
			for (match const & containedMatch : perm) {
				auto & childProps = nodes.find(containedMatch)->second;
				if (left.all_descendents.insert(childProps.m).second) {
					propertyResolveQueue.push(std::make_tuple(&left, &nodes.find(containedMatch)->second, leftsHeightMinusRightsHeight + 1));
				}
				childProps.all_ancestors.insert(left.m);
				childProps.all_descendents_and_ancestors.insert(left.m);
				left.all_descendents_and_ancestors.insert(childProps.m);
			}
		}
	}
}

//Algorithm for quickly getting the `matches` that are present in a range of document indices
struct intersection_lookup {
	explicit intersection_lookup(std::vector<std::set<node_props_t *>> const & flattened) {
		auto const docLen = flattened.size();
		auto const lookupDepth = sizeof(int32_t) * 8 - clz(uint32_t(docLen));
		lookup.resize(lookupDepth);
		auto & lowestRow = lookup[lookupDepth - 1];
		lowestRow.resize(docLen);
		for (size_t i = 0; i < docLen; ++i) {
			for (auto const & node : flattened[i]) {
				lowestRow[i].insert(node->m);
			}
		}
		for (int depth = lookupDepth - 2; depth >= 0; --depth) {
			auto const antiDepth = (lookupDepth - 1) - depth;
			auto const rowWidth = docLen >> antiDepth;
			auto & row = lookup[depth];
			row.resize(rowWidth);
			auto & lowerRow = lookup[depth + 1];
			for (size_t i = 0; i + 1 < lowerRow.size(); i += 2) {
				auto const column = i / 2;
				auto & cell = row[column];
				cell.insert(lowerRow[i].begin(), lowerRow[i].end());
				cell.insert(lowerRow[i + 1].begin(), lowerRow[i + 1].end());
			}
		}
	}

	void query(int const first, int const last, std::set<match> & results) {
		int const lookupDepth = lookup.size();
		// common higher-order bits identify the row and column fully containing the span
		auto const containmentAntiRow = sizeof(int32_t) * 8 - clz(first ^ last);
		int const containmentBreadth = 1 << containmentAntiRow;
		int const containmentColumn = first >> containmentAntiRow;
		int const containmentFirst = containmentColumn << containmentAntiRow;
		auto const containmentLast = containmentFirst + containmentBreadth - 1;
		int const containmentRow = int(lookupDepth - 1) - containmentAntiRow;
		if (containmentRow >= 0 && int(lookup[containmentRow].size()) > containmentColumn && first == containmentFirst && last == containmentLast) {
			auto resolved = lookup[containmentRow][containmentColumn];
			std::set<match> temp;
			std::set_union(
				results.begin(), results.end(),
				resolved.begin(), resolved.end(),
				std::inserter(temp, temp.end())
			);
			results.swap(temp);
		} else {
			int const divisionAntiRow = containmentAntiRow - 1;
			auto const divisionColumn = (containmentColumn << 1) + 1;
			auto const divisionIndex = divisionColumn << divisionAntiRow;
			query(first, divisionIndex - 1, results);
			query(divisionIndex, last, results);
		}
	}

private:
	std::vector<std::vector<std::set<match>>> lookup;	
};

static void compute_intersections(std::map<match, node_props_t> & nodes, std::vector<std::set<node_props_t *>> const & flattened) {
	intersection_lookup lookup(flattened);
	for (auto & matchAndProps : nodes) {		
		auto const & m = matchAndProps.first;
		auto & props = matchAndProps.second;
		auto const first = m.document_position;
		auto const last = first + m.consumed_character_count - 1;
		std::set<match> temp;
		lookup.query(first, last, temp);
		temp.erase(m);
		auto const & remove = props.all_descendents_and_ancestors;
		std::set_difference(
			temp.begin(), temp.end(),
			remove.begin(), remove.end(),
			std::inserter(props.all_unrelated_intersections, props.all_unrelated_intersections.end())
		);
	}
}

static std::vector<std::set<match>> ordered_matches_by_height(std::map<match, node_props_t> & nodes) {
	std::vector<std::set<match>> orderedMatchesByHeight;
	for (auto & entry : nodes) {
		auto & node = entry.second;
		if (orderedMatchesByHeight.size() <= node.height) {
			orderedMatchesByHeight.resize(node.height + 1);
		}
		orderedMatchesByHeight[node.height].insert(node.m);
	}
	return orderedMatchesByHeight;
}

static bool does_precede(grammar_base const & g, node_props_t & a, node_props_t & b) {
	if (a.m.recognizer_index == b.m.recognizer_index) {
		return false;
	}
	return g.does_precede(a.m.recognizer_index, b.m.recognizer_index);
}
<commit_msg>Change node_props_t from std::set to collections::coherent_set<commit_after>#include "parlex/detail/parser.hpp"

#include <iterator>
#include <stack>

#include "parlex/post_processor.hpp"

#include "parlex/detail/context.hpp"
#include "parlex/detail/grammar_base.hpp"
#include "parlex/detail/job.hpp"
#include "parlex/detail/permutation.hpp"
#include "parlex/detail/producer.hpp"
#include "parlex/detail/subjob.hpp"

#include "utils.hpp"
#include "bits.hpp"

namespace parlex {
namespace detail {

void parser::start_workers(int threadCount) {
	for (; threadCount > 0; --threadCount) {
		workers.emplace_back([=]() {
			//DBG("thread ", threadCount, " started");
			std::unique_lock<std::mutex> lock(mutex);
			goto wait;
			while (!terminating) {
				{
					//DBG("THREAD ", threadCount, " POPPING ITEM");
					auto item = work.back();
					work.pop_back();
					lock.unlock();
					auto const & c = *std::get<0>(item);
					auto const nextDfaState = std::get<1>(item);
					update_progress(c);
					//INF("thread ", threadCount, " executing DFA state");	
					c.owner.machine.process(c, nextDfaState);
					c.owner.end_work_queue_reference();
					if (--active_count == 0) {
						halt_cv.notify_one();
					}
					lock.lock();
				}
			wait:
				work_cv.wait(lock, [this]() { return work.size() > 0 || terminating; });
			}
		});
	}
}

parser::parser(unsigned const threadCount) : single_thread_mode(threadCount == 1), active_count(0), terminating(false) {
	if (!single_thread_mode) {
		start_workers(threadCount);
	}
}

parser::~parser() {
	terminating = true;
	work_cv.notify_all();
	for (auto & thread : workers) {
		thread.join();
	}
}

abstract_syntax_semilattice parser::construct_result_and_postprocess(size_t const overrideRootRecognizerIndex, std::vector<post_processor> const & posts, std::u32string const & document, job & j) {
	auto result = construct_result(j, match(match_class(0, overrideRootRecognizerIndex, 0), document.size()));
	if (!posts.empty()) {
		for (auto const & post : posts) {
			post(result);
		}
		if (result.is_rooted()) {
			result.prune_detached();
		}
	}
	return result;
}

void parser::complete_progress_handler(job & j) {
	j.update_progress(j.document.length());
}

void parser::update_progress(context const & context) {
	context.owner.owner.update_progress(context.current_document_position);
}

abstract_syntax_semilattice parser::single_thread_parse(grammar_base const & g, size_t const overrideRootRecognizerIndex, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const progressHandler) {
	//perf_timer timer("parse");
	job j(*this, document, g, overrideRootRecognizerIndex, progressHandler);
	throw_assert(active_count > 0);
	while (true) {
		while (work.size() > 0) {
			auto item = work.back();
			work.pop_back();
			auto const & c = *std::get<0>(item);
			auto const nextDfaState = std::get<1>(item);
			update_progress(c);	
			//INF("thread ", threadCount, " executing DFA state");
			c.owner.machine.process(c, nextDfaState);
			c.owner.end_work_queue_reference();
			--active_count;
		}
		throw_assert(active_count == 0);
		//DBG("parser is idle; checking for deadlocks");
		if (handle_deadlocks(j)) {
			break;
		}
	}
	throw_assert(active_count == 0);
	complete_progress_handler(j);
	return construct_result_and_postprocess(overrideRootRecognizerIndex, posts, document, j);
}

abstract_syntax_semilattice parser::multi_thread_parse(grammar_base const & g, size_t const overrideRootRecognizerIndex, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const progressHandler) {
	//perf_timer timer("parse");
	std::unique_lock<std::mutex> lock(mutex); //use the lock to make sure we see activeCount != 0
	job j(*this, document, g, overrideRootRecognizerIndex, progressHandler);
	throw_assert(active_count > 0);
	while (true) {
		halt_cv.wait(lock, [this]() { return active_count == 0; });
		//DBG("parser is idle; checking for deadlocks");
		if (handle_deadlocks(j)) {
			break;
		}
	}
	throw_assert(active_count == 0);
	complete_progress_handler(j);
	return construct_result_and_postprocess(overrideRootRecognizerIndex, posts, document, j);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, recognizer const & overrideMain, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const & progressHandler) {
	auto const overrideRootRecognizerIndex = g.lookup_recognizer_index(overrideMain);
	if (single_thread_mode) {
		return single_thread_parse(g, overrideRootRecognizerIndex, posts, document, progressHandler);
	}
	return multi_thread_parse(g, overrideRootRecognizerIndex, posts, document, progressHandler);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, recognizer const & overrideMain, std::u32string const & document, progress_handler_t const & progressHandler) {
	return parse(g, overrideMain, std::vector<post_processor>(), document, progressHandler);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, std::vector<post_processor> const & posts, std::u32string const & document, progress_handler_t const & progressHandler) {
	return parse(g, g.get_root_state_machine(), posts, document, progressHandler);
}

abstract_syntax_semilattice parser::parse(grammar_base const & g, std::u32string const & document, progress_handler_t const & progressHandler) {
	return parse(g, g.get_root_state_machine(), document, progressHandler);
}

void parser::schedule(context const & c, int nextDfaState) {
	//DBG("scheduling m: ", c.owner().machine.name, " b:", c.owner().documentPosition, " s:", nextDfaState, " p:", c.current_document_position());
	c.owner.begin_work_queue_reference();
	++active_count;
	std::unique_lock<std::mutex> lock(mutex);
	work.emplace_back(&c, nextDfaState);
	work_cv.notify_one();
}

bool parser::handle_deadlocks(job const & j) const {
	throw_assert(active_count == 0);
	//perf_timer timer("handle_deadlocks");

	//build a dependency graph and detect cyclical portions that should be halted
	//if no subjobs remain, return true
	//otherwise return false (still work to be done)

	std::stack<std::pair<match_class, match_class>> s;

	//Examine subscriptions from one subjob to another to construct the graph
	std::map<match_class, std::set<match_class>> directSubscriptions;
	std::map<match_class, std::set<match_class>> allSubscriptions;
	for (size_t documentPosition = 0; documentPosition < j.producers->document_length; ++documentPosition) {
		for (size_t recognizerIndex = 0; recognizerIndex < j.producers->recognizer_count; ++recognizerIndex) {
			match_class const matchClass(documentPosition, recognizerIndex, 0);
			auto const & storage = (*j.producers)(matchClass);
			if (!storage) {
				continue;
			}
			auto const & producer = *storage;
			auto const & recognizer = j.g.get_recognizer(producer.recognizer_index);
			if (recognizer.is_terminal() || producer.completed) {
				continue;
			}
			for (auto const & subscription : producer.consumers) {
				auto const & c = subscription.c;
				match_class temp(c.owner.document_position, c.owner.recognizer_index, 0);
				allSubscriptions[matchClass].insert(temp);
				directSubscriptions[matchClass].insert(temp);
				s.push(std::pair<match_class, match_class>(matchClass, temp));
			}
		}
	}

	//Apply transitivity to the graph
	while (s.size() > 0) {
		auto entry = s.top();
		s.pop();
		for (auto const & next : directSubscriptions[entry.first]) {
			if (allSubscriptions[entry.first].insert(next).second) {
				s.push(std::pair<match_class, match_class>(entry.first, next));
			}
		}
	}

	auto anyHalted = false;
	//halt subjobs that are subscribed to themselves (in)directly
	for (auto const & i : allSubscriptions) {
		auto const & matchClass = i.first;
		auto & p = *(*j.producers)(matchClass);
		if (i.second.count(matchClass) > 0) {
			p.terminate();
			anyHalted = true;
		}
	}
	return !anyHalted;
}

struct node_props_t {
	match const m;
	std::set<permutation> & permutations;
	std::map<match, std::set<permutation>> parent_permutations_by_match;
	size_t height;
	std::set<match> all_descendents;
	std::set<match> all_ancestors;
	std::set<match> all_descendents_and_ancestors;
	collections::coherent_set<match> all_unrelated_intersections;

	node_props_t(abstract_syntax_semilattice & asg, match const & m) : m(m), permutations(asg.permutations_of_matches[m]), height(0) {
	}
};

static bool can_prune(abstract_syntax_semilattice & asg, std::map<match, node_props_t> const & nodes, node_props_t const & props) {
	if (!(props.m < asg.root || asg.root < props.m)) {
		return false;
	}
	for (auto const & parentMatchAndPermutations : props.parent_permutations_by_match) {
		auto const & parentMatch = parentMatchAndPermutations.first;
		auto const i = nodes.find(parentMatch);
		throw_assert(i != nodes.end());
		auto const & parentProps = i->second;
		auto const & parentPermutations = parentMatchAndPermutations.second;
		if (parentProps.permutations.size() == parentPermutations.size()) { //if all parent permutations depend on this, then we can only prune if the parent can be pruned
			if (!can_prune(asg, nodes, parentProps)) {
				return false;
			}
		}
	}
	return true;
}

static void prune(abstract_syntax_semilattice & asg, std::map<match, node_props_t> & nodes, node_props_t & props) {
	std::queue<match> toPrune;
	std::set<match> completed;
	std::function<void(match const &)> const add = [&](match const & m) {
		if (completed.insert(m).second) {
			toPrune.push(m);
		}
	};
	add(props.m);
	while (!toPrune.empty()) {
		auto const thisMatch = toPrune.front();
		auto & thisNode = nodes.find(thisMatch)->second;
		toPrune.pop();
		for (auto const & parentMatchAndPermutations : thisNode.parent_permutations_by_match) {
			auto const & parentMatch = parentMatchAndPermutations.first;
			auto const i = nodes.find(parentMatch);
			throw_assert(i != nodes.end());
			auto & parentProps = i->second;
			auto const & parentPermutations = parentMatchAndPermutations.second;
			for (auto const & perm : parentPermutations) {
				parentProps.permutations.erase(perm);
			}
			if (parentProps.permutations.size() == 0) {
				add(parentMatch);
			}
		}
		for (auto const & descendentMatch : thisNode.all_descendents) {
			auto const i = nodes.find(descendentMatch);
			throw_assert(i != nodes.end());
			auto & descendent = i->second;
			descendent.all_ancestors.erase(thisMatch);
			if (descendent.all_ancestors.empty()) {
				add(descendentMatch);
			}
			descendent.all_descendents_and_ancestors.erase(thisMatch);
			descendent.parent_permutations_by_match.erase(thisMatch);
		}
		for (auto const & ancestorMatch : thisNode.all_ancestors) {
			auto const i = nodes.find(ancestorMatch);
			throw_assert(i != nodes.end());
			auto & ancestor = i->second;
			ancestor.all_descendents.erase(thisMatch);
			ancestor.all_descendents_and_ancestors.erase(thisMatch);
		}
		for (auto const & intersectorMatch : thisNode.all_unrelated_intersections) {
			auto const i = nodes.find(intersectorMatch);
			throw_assert(i != nodes.end());
			auto & intersector = i->second;
			intersector.all_unrelated_intersections.erase(thisMatch);
		}
	}

	for (auto const & i : completed) {
		nodes.erase(i);
		asg.permutations_of_matches.erase(i);
	}
}

static void construct_nodes(abstract_syntax_semilattice & asg, std::map<match, node_props_t> & nodes, std::vector<std::set<node_props_t *>> & flattened) {
	for (auto const & matchAndPermutations : asg.permutations_of_matches) {
		auto const & m = matchAndPermutations.first;
		auto & nodeProps = nodes.emplace(std::piecewise_construct, std::forward_as_tuple(m), std::forward_as_tuple(asg, m)).first->second;

		for (auto const & perm : nodeProps.permutations) {
			for (match const & child : perm) {
				auto & childProps = nodes.emplace(std::piecewise_construct, std::forward_as_tuple(child), std::forward_as_tuple(asg, child)).first->second;
				if (childProps.permutations.empty()) {
					childProps.height = 0;
				}
				childProps.parent_permutations_by_match[nodeProps.m].insert(perm);
			}
		}
		auto const afterIndex = nodeProps.m.document_position + nodeProps.m.consumed_character_count;
		for (auto i = nodeProps.m.document_position; i < afterIndex; ++i) {
			flattened[i].insert(&nodeProps);
		}
	}
}

static void resolve_nodes(std::map<match, node_props_t> & nodes) {
	//work queue for the algorithm
	std::queue<std::tuple<node_props_t *, node_props_t *, int>> propertyResolveQueue;

	for (auto & entry : nodes) {
		auto & props = entry.second;
		//seed algorithm with "match A has all of match A's permutation's matches as descendants"
		propertyResolveQueue.push(std::make_tuple(&props, &props, 0));
	}

	//containment algorithm
	//match A contains all of match B's permutation's matches
	while (!propertyResolveQueue.empty()) {
		auto entry = propertyResolveQueue.front();
		propertyResolveQueue.pop();
		auto & left = *std::get<0>(entry);
		auto & right = *std::get<1>(entry);
		size_t const leftsHeightMinusRightsHeight = std::get<2>(entry);
		if (right.height == 0) { //if right is a leaf
			left.height = std::max(leftsHeightMinusRightsHeight, left.height);
		}
		for (auto const & perm : right.permutations) {
			for (match const & containedMatch : perm) {
				auto & childProps = nodes.find(containedMatch)->second;
				if (left.all_descendents.insert(childProps.m).second) {
					propertyResolveQueue.push(std::make_tuple(&left, &nodes.find(containedMatch)->second, leftsHeightMinusRightsHeight + 1));
				}
				childProps.all_ancestors.insert(left.m);
				childProps.all_descendents_and_ancestors.insert(left.m);
				left.all_descendents_and_ancestors.insert(childProps.m);
			}
		}
	}
}

//Algorithm for quickly getting the `matches` that are present in a range of document indices
struct intersection_lookup {
	explicit intersection_lookup(std::vector<std::set<node_props_t *>> const & flattened) {
		auto const docLen = flattened.size();
		auto const lookupDepth = sizeof(int32_t) * 8 - clz(uint32_t(docLen));
		lookup.resize(lookupDepth);
		auto & lowestRow = lookup[lookupDepth - 1];
		lowestRow.resize(docLen);
		for (size_t i = 0; i < docLen; ++i) {
			for (auto const & node : flattened[i]) {
				lowestRow[i].insert(node->m);
			}
		}
		for (int depth = lookupDepth - 2; depth >= 0; --depth) {
			auto const antiDepth = (lookupDepth - 1) - depth;
			auto const rowWidth = docLen >> antiDepth;
			auto & row = lookup[depth];
			row.resize(rowWidth);
			auto & lowerRow = lookup[depth + 1];
			for (size_t i = 0; i + 1 < lowerRow.size(); i += 2) {
				auto const column = i / 2;
				auto & cell = row[column];
				cell.insert_many(lowerRow[i].begin(), lowerRow[i].end());
				cell.insert_many(lowerRow[i + 1].begin(), lowerRow[i + 1].end());
			}
		}
	}

	void query(int const first, int const last, collections::coherent_set<match> & results) {
		int const lookupDepth = lookup.size();
		// common higher-order bits identify the row and column fully containing the span
		auto const containmentAntiRow = sizeof(int32_t) * 8 - clz(first ^ last);
		int const containmentBreadth = 1 << containmentAntiRow;
		int const containmentColumn = first >> containmentAntiRow;
		int const containmentFirst = containmentColumn << containmentAntiRow;
		auto const containmentLast = containmentFirst + containmentBreadth - 1;
		int const containmentRow = int(lookupDepth - 1) - containmentAntiRow;
		if (containmentRow >= 0 && int(lookup[containmentRow].size()) > containmentColumn && first == containmentFirst && last == containmentLast) {
			auto resolved = lookup[containmentRow][containmentColumn];
			results.insert_many(resolved.begin(), resolved.end());
		} else {
			int const divisionAntiRow = containmentAntiRow - 1;
			auto const divisionColumn = (containmentColumn << 1) + 1;
			auto const divisionIndex = divisionColumn << divisionAntiRow;
			query(first, divisionIndex - 1, results);
			query(divisionIndex, last, results);
		}
	}

private:
	std::vector<std::vector<collections::coherent_set<match>>> lookup;	
};

static void compute_intersections(std::map<match, node_props_t> & nodes, std::vector<std::set<node_props_t *>> const & flattened) {
	intersection_lookup lookup(flattened);
	for (auto & matchAndProps : nodes) {		
		auto const & m = matchAndProps.first;
		auto & props = matchAndProps.second;
		auto const first = m.document_position;
		auto const last = first + m.consumed_character_count - 1;
		lookup.query(first, last, props.all_unrelated_intersections);
		props.all_unrelated_intersections.erase(m);
		auto const & remove = props.all_descendents_and_ancestors;
		props.all_unrelated_intersections.erase_many(remove.begin(), remove.end());
	}
}

static std::vector<std::set<match>> ordered_matches_by_height(std::map<match, node_props_t> & nodes) {
	std::vector<std::set<match>> orderedMatchesByHeight;
	for (auto & entry : nodes) {
		auto & node = entry.second;
		if (orderedMatchesByHeight.size() <= node.height) {
			orderedMatchesByHeight.resize(node.height + 1);
		}
		orderedMatchesByHeight[node.height].insert(node.m);
	}
	return orderedMatchesByHeight;
}

static bool does_precede(grammar_base const & g, node_props_t & a, node_props_t & b) {
	if (a.m.recognizer_index == b.m.recognizer_index) {
		return false;
	}
	return g.does_precede(a.m.recognizer_index, b.m.recognizer_index);
}

{'fraction_non_alphanumeric': 0.13250475805986506, 'fraction_numerical': 0.00455620277986043, 'mean_word_length': 5.01752559430852, 'pattern_counts': {'":': 0, '<': 153, '<?xml version=': 0, '>': 175, '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': '333626', 'n_tokens_mistral': 12586, 'n_tokens_neox': 11340, 'n_words': 2436}