local b={CR=0;LF=1;CRLF=2;ANYRLF=3;ANY=4,NUL=5}local function W(b,W,H)local O=H.newline local z=b[W]if O==0 then return z==13 elseif O==2 then return z==10 and b[W-1]==32 elseif O==3 then return z==10 or z==13 elseif O==4 then return z==10 or z==11 or z==12 or z==13 or z==133 or z==8232 or z==8233 elseif O==5 then return z==0 end return z==10 end local function H(b,O,z,M,S)local C=O[z]if not C then return false elseif M.ignoreCase and(C>=97 and C<=122)then C-=32 end if type(b)=="\110\117\109\098\101\114"then return b==C elseif b[1]=="\099\104\097\114\115\101\116"then for W,C in ipairs(b[3])do if H(C,O,z,M,S)then return not b[2]end end return b[2]elseif b[1]=="\114\097\110\103\101"then return C>=b[2]and C<=b[3]or M.ignoreCase and(C>=65 and(C<=90 and(C+32>=b[2]and C+32<=b[3])))elseif b[1]=="\099\108\097\115\115"then local W=b[2]local H=b[3]local O=false if W=="\120\100\105\103\105\116"then O=C>=48 and C<=57 or C>=65 and C<=70 or C>=97 and C<=102 elseif W=="\097\115\099\105\105"then O=C<=127 elseif W=="\118\101\114\116\105\099\097\108\095\116\097\098"then O=C>=10 and C<=13 or C==8232 or C==8233 elseif M.unicode then local b=u_categories[C]or"\067\110"local H=b:sub(1,1)if W=="\097\108\110\117\109"then O=H=="\076"or b=="\078\108"or b=="\078\100"elseif W=="\097\108\112\104\097"then O=H=="\076"or b=="\078\108"elseif W=="\098\108\097\110\107"then O=b=="\090\115"or C==9 elseif W=="\099\110\116\114\108"then O=b=="\067\099"elseif W=="\100\105\103\105\116"then O=b=="\078\100"elseif W=="\103\114\097\112\104"then O=H~="\080"and H~="\067"elseif W=="\108\111\119\101\114"then O=b=="\076\108"elseif W=="\112\114\105\110\116"then O=H~="\067"elseif W=="\112\117\110\099\116"then O=H=="\080"elseif W=="\115\112\097\099\101"then O=H=="\090"or C>=9 and C<=13 elseif W=="\117\112\112\101\114"then O=b=="\076\117"elseif W=="\119\111\114\100"then O=H=="\076"or b=="\078\108"or b=="\078\100"or b=="\080\099"end elseif W=="\097\108\110\117\109"then O=C>=48 and C<=57 or C>=65 and C<=90 or C>=97 and C<=122 elseif W=="\097\108\112\104\097"then O=C>=65 and C<=90 or C>=97 and C<=122 elseif W=="\098\108\097\110\107"then O=C==9 or C==32 elseif W=="\099\110\116\114\108"then O=C<=31 or C==127 elseif W=="\100\105\103\105\116"then O=C>=48 and C<=57 elseif W=="\103\114\097\112\104"then O=C>=33 and C<=126 elseif W=="\108\111\119\101\114"then O=C>=97 and C<=122 elseif W=="\112\114\105\110\116"then O=C>=32 and C<=126 elseif W=="\112\117\110\099\116"then O=class_ascii_punct[C]elseif W=="\115\112\097\099\101"then O=C>=9 and C<=13 or C==32 elseif W=="\117\112\112\101\114"then O=C>=65 and C<=90 elseif W=="\119\111\114\100"then O=C>=48 and C<=57 or C>=65 and C<=90 or C>=97 and C<=122 or C==95 end if H then return not O end return O elseif b[1]=="\099\097\116\101\103\111\114\121"then local W=u_categories[C]or"\067\110"local k=b[3]local U=#k if U==3 then local U=false if k=="\088\097\110"or k=="\088\119\100"then U=W:find("\094\091\076\078\093")or k=="\088\119\100"and C==95 elseif k=="\088\112\115"or k=="\088\115\112"then U=W:sub(1,1)=="\090"or C>=9 and C<=13 elseif k=="\088\117\099"then U=H(xuc_chr,O,z,M,S)end if b[2]then return not U end return U elseif W:sub(1,U)==k then return not b[2]end return b[2]elseif b[1]==46 then return M.dotAll or not W(O,z,S)elseif b[1]==78 then return not W(O,z,S)elseif b[1]==82 then if S.newline_seq==0 then return C==10 or C==13 end return C==10 or C==11 or C==12 or C==13 or C==133 or C==8232 or C==8233 end return false end local function O(b,W,H)while true do local O=b[W]local z=type(O)=="\116\097\098\108\101"if O==alternation then return W,H elseif z and O[1]==40 then if H then H+=O.count end W=O[3]elseif z and(O[1]=="\113\117\097\110\116\105\102\105\101\114"and(type(O[5])=="\116\097\098\108\101"and O[5][1]==40))then if H then H+=O[5].count end W=O[5][3]elseif not O or z and O[1]==41 then return nil,H elseif H then if z and O[1]=="\113\117\097\110\116\105\102\105\101\114"then H+=O[3]else H+=1 end end W+=1 end end local function z(b,z,M,S,C,k)local U,n,K=0,M,M local r={}while U do if U==0 then U+=1 local W=O(b,U)if W then table.insert(r,1,{"\097\108\116\101\114\110\097\116\105\111\110";W,n})end continue end local P=b[U]local e=type(P)=="\116\097\098\108\101"and P[1]if not P then break elseif P=="\065\067\067\069\080\084"then local W=true local H=U repeat H+=1 local O=type(b[H])=="\116\097\098\108\101"local z=b[H]if O and(z[1]==40 or z[1]=="\113\117\097\110\116\105\102\105\101\114"and(type(z[5])=="\116\097\098\108\101"and z[5][1]==40))then H=z[1]=="\113\117\097\110\116\105\102\105\101\114"and z[5][3]or z[3]elseif O and(z[1]==41 and(z[4]==33 or z[4]==61))then W=false U=H break end until not z if W then break end elseif P=="\080\082\085\078\069"or P=="\083\075\073\080"then table.insert(r,1,{P,n})U+=1 elseif e==40 then table.insert(r,1,{"\103\114\111\117\112";U;n;nil,P[2];P[3];P[4]})U+=1 local W,H=O(b,U,(P[4]==33 or P[4]==61)and(P[5]and 0))if W then table.insert(r,1,{"\097\108\116\101\114\110\097\116\105\111\110";W,n})end if H then n-=H end elseif e==41 and P[4]~=33 then if P[4]==33 or P[4]==61 then while true do local b local W=table.remove(r,1)if W[1]=="\103\114\111\117\112"and W[2]==P[3]then if(P[4]==33 or P[4]==61)and not P[5]then n=W[3]end if b then table.insert(r,1,b)end break elseif W[1]=="\109\097\116\099\104\083\116\097\114\116"and(not b and P[4]==61)then b=W end end elseif P[4]==62 then repeat local b=table.remove(r,1)until not b or b[1]=="\103\114\111\117\112"and b[2]==P[3]else for W,H in ipairs(r)do if H[1]=="\103\114\111\117\112"and H[2]==P[3]then if H.jmp then U=H.jmp end H[4]=n if H[7]=="\113\117\097\110\116\105\102\105\101\114"and H[10]+1<H[9]then if b[P[3]][4]~="\108\097\122\121"or H[10]+1<H[8]then U=P[3]end local W=b[P[3]]local O={"\103\114\111\117\112";H[2],n;nil;W[5][2];W[5][3],"\113\117\097\110\116\105\102\105\101\114";W[2];W[3];H[10]+1;H[11],W[4]}table.insert(r,1,O)if H[11]then table.insert(r,1,{"\097\108\116\101\114\110\097\116\105\111\110",H[11];n})end end break end end end U+=1 elseif e==75 then table.insert(r,1,{"\109\097\116\099\104\083\116\097\114\116",n})U+=1 elseif e==124 then local W=U repeat W+=1 local H=type(b[W])=="\116\097\098\108\101"local O=b[W]if H and(O[1]==40 or O[1]=="\113\117\097\110\116\105\102\105\101\114"and(type(O[5])=="\116\097\098\108\101"and O[5][1]==40))then W=O[1]=="\113\117\097\110\116\105\102\105\101\114"and O[5][3]or O[3]end until H and O[1]==41 or not O if b[W]then for b,H in ipairs(r)do if H[1]=="\103\114\111\117\112"and H[6]==W then U=H[6]break end end else U=W end elseif e=="\114\101\099\117\114\109\097\116\099\104"then table.insert(r,1,{"\103\114\111\117\112",P[3];n;nil;nil,b[P[3]][3];nil;jmp=U})U=P[3]+1 local W,H=O(b,U)if W then table.insert(r,1,{"\097\108\116\101\114\110\097\116\105\111\110",W,n})end else local Z if P=="\070\065\073\076"then Z=false elseif e==41 then repeat local b=table.remove(r,1)until b[1]=="\103\114\111\117\112"and b[2]==P[3]elseif e=="\113\117\097\110\116\105\102\105\101\114"then if type(P[5])=="\116\097\098\108\101"and P[5][1]==40 then local W=O(b,U+1)if W then table.insert(r,1,{"\097\108\116\101\114\110\097\116\105\111\110",W;n})end table.insert(r,W and 2 or 1,{"\103\114\111\117\112",U;n,nil;P[5][2],P[5][3];"\113\117\097\110\116\105\102\105\101\114",P[2],P[3],0,W,P[4]})if P[4]=="\108\097\122\121"and P[2]==0 then U=P[5][3]end Z=true else local b,W local O=1 local M=type(P[5])=="\116\097\098\108\101"and P[5][1]=="\098\097\099\107\114\101\102"if M then O=0 local H=P[5][2]for z,M in ipairs(r)do if M[1]=="\103\114\111\117\112"and M[5]==H then b,W=M[3],M[4]O=W-b break end end end local k=n+P[2]*O local K=0 while K<P[3]do if M then if b and W then local H=n if utf8_sub(z.s,b,W)~=utf8_sub(z.s,H,n+O)then break end else break end elseif not H(P[5],z,n,S,C)then break end n+=O K+=1 end Z=K>=P[2]if Z and P[4]~="\112\111\115\115\101\115\115\105\118\101"then if P[4]=="\108\097\122\121"then k,n=n,k end table.insert(r,1,{"\113\117\097\110\116\105\102\105\101\114",U,n,math.min(k,z.n+1);(P[4]=="\108\097\122\121"and 1 or-1)*O})end end elseif e=="\098\097\099\107\114\101\102"then local b,W local H=P[2]for O,z in ipairs(r)do if z[1]=="\103\114\111\117\112"and z[5]==H then b,W=z[3],z[4]break end end if b and W then local H=n n+=W-b Z=utf8_sub(z.s,b,W)==utf8_sub(z.s,H,n)end else local b=z[n]if e==36 or e==90 or e==122 then Z=n==z.n+1 or e==36 and(S.multiline and W(z,n+1,C))or e==90 and(n==z.n and W(z,n,C))elseif e==94 or e==65 or e==71 then Z=n==1 or e==94 and(S.multiline and W(z,n-1,C))or e==71 and n==M elseif e==66 or e==98 then local O=n==1 or S.multiline and W(z,n-1,C)local M=n==z.n+1 or S.multiline and W(z,n,C)local k=H(P[2],z[n-1],S)and 0 or H(P[2],b,S)and 1 if k==0 then Z=M or not H(P[2],b,S)elseif k then Z=O or not H(P[2],z[n-1],S)end if e==66 then Z=not Z end else Z=H(P,z,n,S,C)n+=1 end end if not Z then while true do local W,H=r[1]and r[1][1],r[1]if not W or W=="\080\082\085\078\069"or W=="\083\075\073\080"then if W then table.clear(r)end if K>z.n then if k then return false end return nil end K=W=="\083\075\073\080"and H[2]or K+1 U,n=0,K break elseif W=="\097\108\116\101\114\110\097\116\105\111\110"then U,n=H[2],H[3]local W,z=O(b,U+1)if W then H[2]=W else table.remove(r,1)end if z then n-=z end break elseif W=="\103\114\111\117\112"then if H[7]=="\113\117\097\110\116\105\102\105\101\114"then if H[12]=="\103\114\101\101\100\121"and H[10]>=H[8]or H[12]=="\108\097\122\121"and(H[10]<H[9]and not H[13])then U,n=H[12]=="\103\114\101\101\100\121"and H[6]or H[2],H[3]if H[12]=="\103\114\101\101\100\121"then table.remove(r,1)break elseif H[10]>=H[8]then H[13]=true break end end elseif H[7]==33 then table.remove(r,1)U,n=H[6],H[3]break end elseif W=="\113\117\097\110\116\105\102\105\101\114"then if math.sign(H[4]-H[3])==math.sign(H[5])then H[3]+=H[5]U,n=H[2],H[3]break end end table.remove(r,1)end end U+=1 end end if k then return true end local P=false local e=table.create(b.group_n)e[0],e.n={K;n},b.group_n for b,W in ipairs(r)do if W[1]=="\109\097\116\099\104\083\116\097\114\116"and not P then e[0][1],P=W[2],true elseif W[1]=="\103\114\111\117\112"and(W[5]and not e[W[5]])then e[W[5]]={W[3],W[4]}end end return e end

local line_verbs = {
	CR = 0, LF = 1, CRLF = 2, ANYRLF = 3, ANY = 4, NUL = 5,
};
local function is_newline(str_arr, i, verb_flags)
	local line_verb_n = verb_flags.newline;
	local chr = str_arr[i];
	if line_verb_n == 0 then
		-- carriage return
		return chr == 0x0D;
	elseif line_verb_n == 2 then
		-- carriage return followed by line feed
		return chr == 0x0A and str_arr[i - 1] == 0x20;
	elseif line_verb_n == 3 then
		-- any of the above
		return chr == 0x0A or chr == 0x0D;
	elseif line_verb_n == 4 then
		-- any of Unicode newlines
		return chr == 0x0A or chr == 0x0B or chr == 0x0C or chr == 0x0D or chr == 0x85 or chr == 0x2028 or chr == 0x2029;
	elseif line_verb_n == 5 then
		-- null
		return chr == 0;
	end;
	-- linefeed
	return chr == 0x0A;
end;


local function tkn_char_match(tkn_part, str_arr, i, flags, verb_flags)
	local chr = str_arr[i];
	if not chr then
		return false;
	elseif flags.ignoreCase and chr >= 0x61 and chr <= 0x7A then
		chr -= 0x20;
	end;
	if type(tkn_part) == "number" then
		return tkn_part == chr;
	elseif tkn_part[1] == "charset" then
		for _, v in ipairs(tkn_part[3]) do
			if tkn_char_match(v, str_arr, i, flags, verb_flags) then
				return not tkn_part[2];
			end;
		end;
		return tkn_part[2];
	elseif tkn_part[1] == "range" then
		return chr >= tkn_part[2] and chr <= tkn_part[3] or flags.ignoreCase and chr >= 0x41 and chr <= 0x5A and (chr + 0x20) >= tkn_part[2] and (chr + 0x20) <= tkn_part[3];
	elseif tkn_part[1] == "class" then
		local char_class = tkn_part[2];
		local negate = tkn_part[3];
		local match = false;
		-- if and elseifs :(
		-- Might make these into tables in the future
		if char_class == "xdigit" then
			match = chr >= 0x30 and chr <= 0x39 or chr >= 0x41 and chr <= 0x46 or chr >= 0x61 and chr <= 0x66;
		elseif char_class == "ascii" then
			match = chr <= 0x7F;
		-- cannot be accessed through POSIX classes
		elseif char_class == "vertical_tab" then
			match = chr >= 0x0A and chr <= 0x0D or chr == 0x2028 or chr == 0x2029;
		--
		elseif flags.unicode then
			local current_category = u_categories[chr] or 'Cn';
			local first_category = current_category:sub(1, 1);
			if char_class == "alnum" then
				match = first_category == 'L' or current_category == 'Nl' or current_category == 'Nd';
			elseif char_class == "alpha" then
				match = first_category == 'L' or current_category == 'Nl';
			elseif char_class == "blank" then
				match = current_category == 'Zs' or chr == 0x09;
			elseif char_class == "cntrl" then
				match = current_category == 'Cc';
			elseif char_class == "digit" then
				match = current_category == 'Nd';
			elseif char_class == "graph" then
				match = first_category ~= 'P' and first_category ~= 'C';
			elseif char_class == "lower" then
				match = current_category == 'Ll';
			elseif char_class == "print" then
				match = first_category ~= 'C';
			elseif char_class == "punct" then
				match = first_category == 'P';
			elseif char_class == "space" then
				match = first_category == 'Z' or chr >= 0x09 and chr <= 0x0D;
			elseif char_class == "upper" then
				match = current_category == 'Lu';
			elseif char_class == "word" then
				match = first_category == 'L' or current_category == 'Nl' or current_category == 'Nd' or current_category == 'Pc';
			end;
		elseif char_class == "alnum" then
			match = chr >= 0x30 and chr <= 0x39 or chr >= 0x41 and chr <= 0x5A or chr >= 0x61 and chr <= 0x7A;
		elseif char_class == "alpha" then
			match = chr >= 0x41 and chr <= 0x5A or chr >= 0x61 and chr <= 0x7A;
		elseif char_class == "blank" then
			match = chr == 0x09 or chr == 0x20;
		elseif char_class == "cntrl" then
			match = chr <= 0x1F or chr == 0x7F;
		elseif char_class == "digit" then
			match = chr >= 0x30 and chr <= 0x39;
		elseif char_class == "graph" then
			match = chr >= 0x21 and chr <= 0x7E;
		elseif char_class == "lower" then
			match = chr >= 0x61 and chr <= 0x7A;
		elseif char_class == "print" then
			match = chr >= 0x20 and chr <= 0x7E;
		elseif char_class == "punct" then
			match = class_ascii_punct[chr];
		elseif char_class == "space" then
			match = chr >= 0x09 and chr <= 0x0D or chr == 0x20;
		elseif char_class == "upper" then
			match = chr >= 0x41 and chr <= 0x5A;
		elseif char_class == "word" then
			match = chr >= 0x30 and chr <= 0x39 or chr >= 0x41 and chr <= 0x5A or chr >= 0x61 and chr <= 0x7A or chr == 0x5F;
		end;
		if negate then
			return not match;
		end;
		return match;
	elseif tkn_part[1] == "category" then
		local chr_category = u_categories[chr] or 'Cn';
		local category_v = tkn_part[3];
		local category_len = #category_v;
		if category_len == 3 then
			local match = false;
			if category_v == "Xan" or category_v == "Xwd" then
				match = chr_category:find("^[LN]") or category_v == "Xwd" and chr == 0x5F;
			elseif category_v == "Xps" or category_v == "Xsp" then
				match = chr_category:sub(1, 1) == 'Z' or chr >= 0x09 and chr <= 0x0D;
			elseif category_v == "Xuc" then
				match = tkn_char_match(xuc_chr, str_arr, i, flags, verb_flags);
			end;
			if tkn_part[2] then
				return not match;
			end
			return match;
		elseif chr_category:sub(1, category_len) == category_v then
			return not tkn_part[2];
		end;
		return tkn_part[2];
	elseif tkn_part[1] == 0x2E then
		return flags.dotAll or not is_newline(str_arr, i, verb_flags);
	elseif tkn_part[1] == 0x4E then
		return not is_newline(str_arr, i, verb_flags);
	elseif tkn_part[1] == 0x52 then
		if verb_flags.newline_seq == 0 then
			-- CR, LF or CRLF
			return chr == 0x0A or chr == 0x0D;
		end;
		-- any unicode newline
		return chr == 0x0A or chr == 0x0B or chr == 0x0C or chr == 0x0D or chr == 0x85 or chr == 0x2028 or chr == 0x2029;
	end;
	return false;
end;

local function find_alternation(token, i, count)
	while true do
		local v = token[i];
		local is_table = type(v) == "table";
		if v == alternation then
			return i, count;
		elseif is_table and v[1] == 0x28 then
			if count then
				count += v.count;
			end;
			i = v[3];
		elseif is_table and v[1] == "quantifier" and type(v[5]) == "table" and v[5][1] == 0x28 then
			if count then
				count += v[5].count;
			end;
			i = v[5][3];
		elseif not v or is_table and v[1] == 0x29 then
			return nil, count;
		elseif count then
			if is_table and v[1] == "quantifier" then
				count += v[3];
			else
				count += 1;
			end;
		end;
		i += 1;
	end;
end;

local function re_rawfind(token, str_arr, init, flags, verb_flags, as_bool)
	local tkn_i, str_i, start_i = 0, init, init;
	local states = { };
	while tkn_i do
		if tkn_i == 0 then
			tkn_i += 1;
			local next_alt = find_alternation(token, tkn_i);
			if next_alt then
				table.insert(states, 1, { "alternation", next_alt, str_i });
			end;
			continue;
		end;
		local ctkn = token[tkn_i];
		local tkn_type = type(ctkn) == "table" and ctkn[1];
		if not ctkn then
			break;
		elseif ctkn == "ACCEPT" then
			local not_lookaround = true;
			local close_i = tkn_i;
			repeat
				close_i += 1;
				local is_table = type(token[close_i]) == "table";
				local close_i_tkn = token[close_i];
				if is_table and (close_i_tkn[1] == 0x28 or close_i_tkn[1] == "quantifier" and type(close_i_tkn[5]) == "table" and close_i_tkn[5][1] == 0x28) then
					close_i = close_i_tkn[1] == "quantifier" and close_i_tkn[5][3] or close_i_tkn[3];
				elseif is_table and close_i_tkn[1] == 0x29 and (close_i_tkn[4] == 0x21 or close_i_tkn[4] == 0x3D) then
					not_lookaround = false;
					tkn_i = close_i;
					break;
				end;
			until not close_i_tkn;
			if not_lookaround then
				break;
			end;
		elseif ctkn == "PRUNE" or ctkn == "SKIP" then
			table.insert(states, 1, { ctkn, str_i });
			tkn_i += 1;
		elseif tkn_type == 0x28 then
			table.insert(states, 1, { "group", tkn_i, str_i, nil, ctkn[2], ctkn[3], ctkn[4] });
			tkn_i += 1;
			local next_alt, count = find_alternation(token, tkn_i, (ctkn[4] == 0x21 or ctkn[4] == 0x3D) and ctkn[5] and 0);
			if next_alt then
				table.insert(states, 1, { "alternation", next_alt, str_i });
			end;
			if count then
				str_i -= count;
			end;
		elseif tkn_type == 0x29 and ctkn[4] ~= 0x21 then
			if ctkn[4] == 0x21 or ctkn[4] == 0x3D then
				while true do
					local selected_match_start;
					local selected_state = table.remove(states, 1);
					if selected_state[1] == "group" and selected_state[2] == ctkn[3] then
						if (ctkn[4] == 0x21 or ctkn[4] == 0x3D) and not ctkn[5] then
							str_i = selected_state[3];
						end;
						if selected_match_start then
							table.insert(states, 1, selected_match_start);
						end;
						break;
					elseif selected_state[1] == "matchStart" and not selected_match_start and ctkn[4] == 0x3D then
						selected_match_start = selected_state;
					end;
				end;
			elseif ctkn[4] == 0x3E then
				repeat
					local selected_state = table.remove(states, 1);
				until not selected_state or selected_state[1] == "group" and selected_state[2] == ctkn[3];
			else
				for i, v in ipairs(states) do
					if v[1] == "group" and v[2] == ctkn[3] then
						if v.jmp then
							-- recursive match
							tkn_i = v.jmp;
						end;
						v[4] = str_i;
						if v[7] == "quantifier" and v[10] + 1 < v[9] then
							if token[ctkn[3]][4] ~= "lazy" or v[10] + 1 < v[8] then
								tkn_i = ctkn[3];
							end;
							local ctkn1 = token[ctkn[3]];
							local new_group = { "group", v[2], str_i, nil, ctkn1[5][2], ctkn1[5][3], "quantifier", ctkn1[2], ctkn1[3], v[10] + 1, v[11], ctkn1[4] };
							table.insert(states, 1, new_group);
							if v[11] then
								table.insert(states, 1, { "alternation", v[11], str_i });
							end;
						end;
						break;
					end;
				end;
			end;
			tkn_i += 1;
		elseif tkn_type == 0x4B then
			table.insert(states, 1, { "matchStart", str_i });
			tkn_i += 1;
		elseif tkn_type == 0x7C then
			local close_i = tkn_i;
			repeat
				close_i += 1;
				local is_table = type(token[close_i]) == "table";
				local close_i_tkn = token[close_i];
				if is_table and (close_i_tkn[1] == 0x28 or close_i_tkn[1] == "quantifier" and type(close_i_tkn[5]) == "table" and close_i_tkn[5][1] == 0x28) then
					close_i = close_i_tkn[1] == "quantifier" and close_i_tkn[5][3] or close_i_tkn[3];
				end;
			until is_table and close_i_tkn[1] == 0x29 or not close_i_tkn;
			if token[close_i] then
				for _, v in ipairs(states) do
					if v[1] == "group" and v[6] == close_i then
						tkn_i = v[6];
						break;
					end;
				end;
			else
				tkn_i = close_i;
			end;
		elseif tkn_type == "recurmatch" then
			table.insert(states, 1, { "group", ctkn[3], str_i, nil, nil, token[ctkn[3]][3], nil, jmp = tkn_i });
			tkn_i = ctkn[3] + 1;
			local next_alt, count = find_alternation(token, tkn_i);
			if next_alt then
				table.insert(states, 1, { "alternation", next_alt, str_i });
			end;
		else
			local match;
			if ctkn == "FAIL" then
				match = false;
			elseif tkn_type == 0x29 then
				repeat
					local selected_state = table.remove(states, 1);
				until selected_state[1] == "group" and selected_state[2] == ctkn[3];
			elseif tkn_type == "quantifier" then
				if type(ctkn[5]) == "table" and ctkn[5][1] == 0x28 then
					local next_alt = find_alternation(token, tkn_i + 1);
					if next_alt then
						table.insert(states, 1, { "alternation", next_alt, str_i });
					end;
					table.insert(states, next_alt and 2 or 1, { "group", tkn_i, str_i, nil, ctkn[5][2], ctkn[5][3], "quantifier", ctkn[2], ctkn[3], 0, next_alt, ctkn[4] });
					if ctkn[4] == "lazy" and ctkn[2] == 0 then
						tkn_i = ctkn[5][3];
					end;
					match = true;
				else
					local start_i, end_i;
					local pattern_count = 1;
					local is_backref = type(ctkn[5]) == "table" and ctkn[5][1] == "backref";
					if is_backref then
						pattern_count = 0;
						local group_n = ctkn[5][2];
						for _, v in ipairs(states) do
							if v[1] == "group" and v[5] == group_n then
								start_i, end_i = v[3], v[4];
								pattern_count = end_i - start_i;
								break;
							end;
						end;
					end;
					local min_max_i = str_i + ctkn[2] * pattern_count;
					local mcount = 0;
					while mcount < ctkn[3] do
						if is_backref then
							if start_i and end_i then
								local org_i = str_i;
								if utf8_sub(str_arr.s, start_i, end_i) ~= utf8_sub(str_arr.s, org_i, str_i + pattern_count) then
									break;
								end;
							else
								break;
							end;
						elseif not tkn_char_match(ctkn[5], str_arr, str_i, flags, verb_flags) then
							break;
						end;
						str_i += pattern_count;
						mcount += 1;
					end;
					match = mcount >= ctkn[2];
					if match and ctkn[4] ~= "possessive" then
						if ctkn[4] == "lazy" then
							min_max_i, str_i = str_i, min_max_i;
						end;
						table.insert(states, 1, { "quantifier", tkn_i, str_i, math.min(min_max_i, str_arr.n + 1), (ctkn[4] == "lazy" and 1 or -1) * pattern_count });
					end;
				end;
			elseif tkn_type == "backref" then
				local start_i, end_i;
				local group_n = ctkn[2];
				for _, v in ipairs(states) do
					if v[1] == "group" and v[5] == group_n then
						start_i, end_i = v[3], v[4];
						break;
					end;
				end;
				if start_i and end_i then
					local org_i = str_i;
					str_i += end_i - start_i;
					match = utf8_sub(str_arr.s, start_i, end_i) == utf8_sub(str_arr.s, org_i, str_i);
				end;
			else
				local chr = str_arr[str_i];
				if tkn_type == 0x24 or tkn_type == 0x5A or tkn_type == 0x7A then
					match = str_i == str_arr.n + 1 or tkn_type == 0x24 and flags.multiline and is_newline(str_arr, str_i + 1, verb_flags) or tkn_type == 0x5A and str_i == str_arr.n and is_newline(str_arr, str_i, verb_flags);
				elseif tkn_type == 0x5E or tkn_type == 0x41 or tkn_type == 0x47 then
					match = str_i == 1 or tkn_type == 0x5E and flags.multiline and is_newline(str_arr, str_i - 1, verb_flags) or tkn_type == 0x47 and str_i == init;
				elseif tkn_type == 0x42 or tkn_type == 0x62 then
					local start_m = str_i == 1 or flags.multiline and is_newline(str_arr, str_i - 1, verb_flags);
					local end_m = str_i == str_arr.n + 1 or flags.multiline and is_newline(str_arr, str_i, verb_flags);
					local w_m = tkn_char_match(ctkn[2], str_arr[str_i - 1], flags) and 0 or tkn_char_match(ctkn[2], chr, flags) and 1;
					if w_m == 0 then
						match = end_m or not tkn_char_match(ctkn[2], chr, flags);
					elseif w_m then
						match = start_m or not tkn_char_match(ctkn[2], str_arr[str_i - 1], flags);
					end;
					if tkn_type == 0x42 then
						match = not match;
					end;
				else
					match = tkn_char_match(ctkn, str_arr, str_i, flags, verb_flags);
					str_i += 1;
				end;
			end;
			if not match then
				while true do
					local prev_type, prev_state = states[1] and states[1][1], states[1];
					if not prev_type or prev_type == "PRUNE" or prev_type == "SKIP" then
						if prev_type then
							table.clear(states);
						end;
						if start_i > str_arr.n then
							if as_bool then
								return false;
							end;
							return nil;
						end;
						start_i = prev_type == "SKIP" and prev_state[2] or start_i + 1;
						tkn_i, str_i = 0, start_i;
						break;
					elseif prev_type == "alternation" then
						tkn_i, str_i = prev_state[2], prev_state[3];
						local next_alt, count = find_alternation(token, tkn_i + 1);
						if next_alt then
							prev_state[2] = next_alt;
						else
							table.remove(states, 1);
						end;
						if count then
							str_i -= count;
						end;
						break;
					elseif prev_type == "group" then
						if prev_state[7] == "quantifier" then
							if prev_state[12] == "greedy" and prev_state[10] >= prev_state[8]
								or prev_state[12] == "lazy" and prev_state[10] < prev_state[9] and not prev_state[13] then
								tkn_i, str_i = prev_state[12] == "greedy" and prev_state[6] or prev_state[2], prev_state[3];
								if prev_state[12] == "greedy" then
									table.remove(states, 1);
									break;
								elseif prev_state[10] >= prev_state[8] then
									prev_state[13] = true;
									break;
								end;
							end;
						elseif prev_state[7] == 0x21 then
							table.remove(states, 1);
							tkn_i, str_i = prev_state[6], prev_state[3];
							break;
						end;
					elseif prev_type == "quantifier" then
						if math.sign(prev_state[4] - prev_state[3]) == math.sign(prev_state[5]) then
							prev_state[3] += prev_state[5];
							tkn_i, str_i = prev_state[2], prev_state[3];
							break;
						end;
					end;
					-- keep match out state and recursive state, can be safely removed
					-- prevents infinite loop
					table.remove(states, 1);
				end;
			end;
			tkn_i += 1;
		end;
	end;
	if as_bool then
		return true;
	end;
	local match_start_ran = false;
	local span = table.create(token.group_n);
	span[0], span.n = { start_i, str_i }, token.group_n;
	for _, v in ipairs(states) do
		if v[1] == "matchStart" and not match_start_ran then
			span[0][1], match_start_ran = v[2], true;
		elseif v[1] == "group" and v[5] and not span[v[5]] then
			span[v[5]] = { v[3], v[4] };
		end;
	end;
	return span;
end;
