sys

determine.ha (8974B)

---

 // DFA transition table
 type dfa_transition = struct {
 	trans_states: []*dfa_transition_state,
 };
 
 // DFA transition state (row)
 type dfa_transition_state = struct {
 	states: []*state,
 	transitions: []*dfa_transition_trans,
 };
 
 // DFA transition transition (col)
 type dfa_transition_trans = struct {
 	from: *dfa_transition_state,
 	to: *dfa_transition_state,
 	input: dfa_input,
 };
 
 type dfa_input = (dfa_accept | dfa_negate | dfa_dot);
 type dfa_accept = rune;
 type dfa_negate = []rune;
 type dfa_dot = void; // only when gathering inputs, then use negate empty
 
 fn dfa_transition_finish(dfa: *dfa_transition) void = {
 	for (let state .. dfa.trans_states) {
 		dfa_transition_state_finish(state);
 		free(state);
 	};
 	free(dfa.trans_states);
 };
 
 fn dfa_transition_state_finish(dfa_state: *dfa_transition_state) void = {
 	for (let trans .. dfa_state.transitions) {
 		dfa_transition_trans_finish(trans);
 		free(trans);
 	};
 	free(dfa_state.transitions);
 	free(dfa_state.states);
 };
 
 fn dfa_transition_trans_finish(dfa_trans: *dfa_transition_trans) void = {
 	if (dfa_trans.input is dfa_negate)
 		free(dfa_trans.input as dfa_negate);
 };
 
 // Build a DFA from an NDFA. The input automata can then be finished.
 export fn determine(mata: *automata) (automata | nomem) = {
 	let dfa = dfa_transition { ... };
 	defer dfa_transition_finish(&dfa);
 
 	fill_dfa_transition(&dfa, mata.start)?;
 
 	const new = automata {
 		curindex = 0z,
 		curtree = 1z,
 		start = null: *state,
 		deterministic = true,
 		...
 	};
 	append(new.results, mata.results...)?;
 
 	fill_states(&new, &dfa)?;
 	new.start = new.states[0];
 
 	return new;
 };
 
 // Build a dfa transition table from a group of state.
 fn fill_dfa_transition(
 	dfa: *dfa_transition,
 	states: *state...
 ) (*dfa_transition_state | nomem) = {
 	let states = crawl_elipsis(states...)?;
 	defer free(states);
 
 	match (get_state(dfa, states)) {
 	case null => void;
 	case let out: *dfa_transition_state => return out;
 	};
 
 	const dfa_state = alloc(dfa_transition_state {
 		...
 	})?;
 	append(dfa_state.states, states...)?;
 	append(dfa.trans_states, dfa_state)?;
 
 	const all_trans = gather_trans(states)?;
 	defer free(all_trans);
 
 	const inputs = trans_inputs(all_trans)?;
 	defer free(inputs);
 
 	const groups = group_trans_input(all_trans, inputs)?;
 	defer {
 		for (let group .. groups) {
 			free(group.1);
 		};
 		free(groups);
 	};
 
 	for (let group .. groups) {
 		const next_states: []*state = [];
 		defer free(next_states);
 		for (let trans .. group.1) {
 			append(next_states, trans.to)?;
 		};
 		const next = fill_dfa_transition(dfa, next_states...)?;
 		const new = alloc(dfa_transition_trans {
 			from = dfa_state,
 			to = next,
 			input = group.0,
 		})?;
 		append(dfa_state.transitions, new)?;
 	};
 
 	return dfa_state;
 };
 
 // Gather all reachable states through elipsises.
 fn crawl_elipsis(locs: *state...) ([]*state | nomem) = {
 	let out: []*state = [];
 	for: root (let loc .. locs) {
 		for (let out .. out) if (out == loc) continue: root;
 		append(out, loc)?;
 		for: trans (let trans .. loc.transitions) {
 			if (0 != len(trans.accepts)) continue;
 			for (let out .. out) if (out == trans.to) continue: trans;
 			let new = crawl_elipsis(trans.to)?;
 			defer free(new);
 			for: new (let new .. new)
 				for (let out .. out) if (out == new) continue: new;
 			append(out, new...)?;
 		};
 	};
 	return out;
 };
 
 // Return the dfa transition state for a group of state when already builded.
 fn get_state(
 	dfa: *dfa_transition,
 	exp_states: []*state,
 ) nullable *dfa_transition_state = {
 	for (let trans_state .. dfa.trans_states) {
 		if (len(trans_state.states) != len(exp_states))
 			continue;
 		let matched = 0z;
 		for : root (let state .. trans_state.states) {
 			for (let _state .. exp_states) {
 				if (state == _state) {
 					matched += 1;
 					continue : root;
 				};
 			};
 		};
 		if (matched == len(exp_states)) return trans_state;
 	};
 	return null;
 };
 
 // All trans from a group of state that are not elipsises.
 fn gather_trans(states: []*state) ([]*transition | nomem) = {
 	let trans: []*transition = [];
 	for (let state .. states) {
 		for (let _trans .. state.transitions) {
 			if (len(_trans.accepts) == 0) {
 				continue;
 			};
 			append(trans, _trans)?;
 		};
 	};
 	return trans;
 };
 
 // Gather all inputs from a group of trans.
 fn trans_inputs(trans: []*transition) ([]dfa_input | nomem) = {
 	let out: []dfa_input = [];
 
 	for (let trans .. trans) {
 		for: accept (let accept .. trans.accepts) {
 			match (accept) {
 			case dot =>
 				append(out, dfa_dot)?;
 				continue;
 			case let r: rune =>
 				// check already appended
 				for (let out .. out) {
 					match (out) {
 					case let out: dfa_accept =>
 						if (out == r)
 							continue: accept;
 					case => void;
 					};
 				};
 				append(out, r)?;
 			case let r: (rune, rune) =>
 				const a = r.0: u32;
 				const b = r.1: u32;
 				const min = if (a < b) a else b;
 				const max = if (a < b) b else a;
 				for: range (let i = min; i <= max; i += 1) {
 					let r = i: rune;
 					// check already appended
 					for (let out .. out) {
 						match (out) {
 						case let out: dfa_accept =>
 							if (out == r)
 								continue: range;
 						case => void;
 						};
 					};
 					append(out, r)?;
 				};
 			};
 		};
 	};
 
 	return out;
 };
 
 // Group all accepted transitions per input.
 fn group_trans_input(
 	trans: []*transition,
 	inputs: []dfa_input
 ) ([](dfa_input, []*transition) | nomem) = {
 	let out: [](dfa_input, []*transition) = [];
 
 	let neg: dfa_negate = [];
 	defer free(neg);
 
 	let work: []*transition = [];
 	defer free(work);
 
 	for (let input .. inputs) {
 		match (input) {
 		case dfa_dot => void;
 		case dfa_negate => abort("unreachable");
 		case let input: dfa_accept =>
 			for (let trans .. trans) {
 				if (accept(trans, input)) {
 					append(work, trans)?;
 				};
 			};
 			append(neg, input)?;
 		};
 		if (len(work) != 0) {
 			append(out, (input, []))?;
 			let new = &out[len(out) - 1];
 			append(new.1, work...)?;
 			delete(work[..]);
 		};
 	};
 	for: trans (let trans .. trans) {
 		for (let a .. trans.accepts) {
 			if (!(a is dot)) continue;
 			append(work, trans)?;
 			continue: trans;
 		};
 		if (!(trans.negate)) continue;
 		let allfound = true;
 		for (let a .. trans.accepts) {
 			let found = false;
 			match (a) {
 			case let a: rune =>
 				for (let input .. neg) {
 					if (input == a) {
 						found = true;
 						break;
 					};
 				};
 			case => found = false;
 			};
 			if (!found) {
 				allfound = false;
 				break;
 			};
 		};
 		if (allfound) {
 			append(work, trans)?;
 		};
 	};
 	if (len(work) != 0) {
 		let newneg: dfa_negate = [];
 		append(newneg, neg...)?;
 		append(out, (newneg, []))?;
 		let new = &out[len(out) - 1];
 		append(new.1, work...)?;
 	};
 
 	return out;
 };
 
 // Build states from a dfa transition table.
 fn fill_states(
 	mata: *automata,
 	dfa: *dfa_transition,
 ) (void | nomem) = {
 	// Produce a hashmap (dfa_state -> state).
 	let dfa2mata: [](*dfa_transition_state, *state) = [];
 	defer free(dfa2mata);
 	for (let dfa_state .. dfa.trans_states) {
 		const state = alloc(state {
 			index = mata.curindex,
 			result = void,
 			...
 		})?;
 		mata.curindex += 1;
 		for (let _state .. dfa_state.states) {
 			if (_state.result is size) {
 				state.result = _state.result;
 				break;
 			};
 		};
 		append(dfa2mata, (dfa_state, state))?;
 		append(mata.states, state)?;
 	};
 
 	// Add all states linearly
 	for (let i = 0z; i < len(dfa.trans_states); i += 1) {
 		const dfa_state = dfa.trans_states[i];
 		const from = dfa2mata[i].1;
 		for: trans (let dfa_trans .. dfa_state.transitions) {
 			let to: nullable *state = null;
 			for (let dfa2mata .. dfa2mata) {
 				if (dfa2mata.0 == dfa_trans.to) {
 					to = dfa2mata.1;
 					break;
 				};
 			};
 			let to = to as *state;
 
 			// Append accepts to existing trans.
 			for (let trans .. from.transitions) {
 				if (trans.to != to) continue;
 				match (dfa_trans.input) {
 				case let acc: dfa_accept =>
 					if (trans.negate) continue;
 					append_to_accepts(&trans.accepts, acc)?;
 				case let neg: dfa_negate =>
 					if (!trans.negate) continue;
 					for (let neg .. neg) {
 						append_to_accepts(&trans.accepts, neg)?;
 					};
 				};
 				continue: trans;
 			};
 
 			// Or create a new trans.
 			const trans = alloc(transition {
 				from = from,
 				to = to,
 				tree = 0,
 				...
 			})?;
 			match (dfa_trans.input) {
 			case let acc: dfa_accept =>
 				append(trans.accepts, acc)?;
 			case let neg: dfa_negate =>
 				trans.negate = true;
 				for (let neg .. neg)
 					append(trans.accepts, neg)?;
 			};
 			append(mata.transitions, trans)?;
 			append(from.transitions, trans)?;
 		};
 	};
 };
 
 fn append_to_accepts(accepts: *[]runeset, r: rune) (void | nomem) = {
 	assert(len(accepts) != 0);
 	match (&accepts[len(accepts) - 1]) {
 	case let lastr: *rune =>
 		if (*lastr: u32 == r: u32 - 1) {
 			const lastr = *lastr;
 			delete(accepts[len(accepts) - 1]);
 			append(accepts, (lastr, r))?;
 			return;
 		};
 	case let lastrange: *(rune, rune) =>
 		if (lastrange.1: u32 == r: u32 - 1) {
 			lastrange.1 = r;
 			return;
 		};
 	};
 	append(accepts, r)?;
 };