erloerl

pike.erl

-module (pike).
-export ([match/2, test/0]).

% Erlang version of R. Pike's beautiful regex matcher (modified).
% Modification lies in changing behaviour of `matchStar`, so even
% regexs like /.*b/ can be handled.
% For more information please see
% http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
% P.S.: special thanks to @dewitt for his tests.

match([$^|Re], Str) -> matchHere(Re, Str);
match(Re, Str = [_C|S]) -> case Result = matchHere(Re, Str) of
	false when S =/= [] ->
		match(Re, S);
	_ ->
		Result
end;
match(Re, []) -> matchHere(Re, []);
match(_, _) -> true.

matchHere([$$|[]], Str) -> Str == [];
matchHere([C|[$*|Re]], Str) -> matchStar(C, Re, Str);
matchHere([C|Re], [C|Str]) -> matchHere(Re, Str);
matchHere([$.|Re], [_C|Str]) -> matchHere(Re, Str);
matchHere([], _Str) -> true;
matchHere(_Re, _Str) -> false.

matchStar(C, Re, [C|Str]) -> matchHere(Re, Str);
matchStar($., Re, [_C|Str]) -> matchHere(Re, Str);
matchStar(_Ch, _Re, _Str) -> true.


test() ->
	true = match(".*", "aaaaabbbb"),
	true = match(".*b", "aaaaabbbb"),
	false = match("aa^b", "aaaaabbbb"),
	true = match(".ab.ba.*", "cabcbac"),
	true = match("", ""),
	true = match("", "a"),
	true = match("", "abc"),
	true = match("a", "a"),
	true = match("a", "ab"),
	true = match("b", "ab"),
	true = match("b", "abc"),
	true = match("c", "abc"),
	false = match("a", ""),
	false = match("d", "abc"),
	true = match("ab", "ab"),
	true = match("ab", "abc"),
	true = match("bc", "abc"),
	false = match("cd", "abc"),
	true = match("^a", "a"),
	true = match("^a", "ab"),
	false = match("^a", ""),
	false = match("^b", "a"),
	false = match("^b", "ab"),
	true = match("^ab", "ab"),
	true = match("^ab", "abc"),
	true = match("a$", "a"),
	true = match("b$", "ab"),
	false = match("a$", ""),
	false = match("b$", "a"),
	false = match("a$", "ab"),
	true = match("ab$", "ab"),
	true = match("bc$", "abc"),
	false = match(".", ""),
	true = match("^ab$", "ab"),
	false = match("^ab$", "abc"),
	false = match("^bc$", "abc"),
	true = match(".", "a"),
	true = match(".", "ab"),
	true = match("a.", "ab"),
	true = match(".b", "ab"),
	false = match("a.", "a"),
	true = match("a.c", "abc"),
	true = match("..", "ab"),
	true = match("..c", "abc"),
	true = match("a..d", "abcd"),
	true = match("a.c.e", "abcde"),
	true = match("a.c.e", "abcde"),
	false = match("...", "ab"),
	true = match("^.", "a"),
	true = match(".$", "a"),
	true = match("^.$", "a"),
	true = match("^..$", "ab"),
	false = match("^.$", "ab"),
	false = match("*", ""),
	false = match("*", "a"),
	true = match("a*", ""),
	true = match("a*", "a"),
	true = match("a*", "aa"),
	true = match("a*", "ab"),
	true = match("a*", "b"),
	true = match(".*", "a"),
	true = match(".*", "abc"),
	true = match("ab*", "abb"),
	true = match("^a*", "a"),
	true = match("^a*", "ab"),
	true = match("^.*", "a"),
	true = match("^.*", "ab"),
	true = match("a*$", "a"),
	true = match("ab*$", "a"),
	true = match("ab*$", "ab"),
	true = match("^.*", "a"),
	true = match("^.*", "ab"),
	true = match("^a*$", "a"),
	true = match("^ab*$", "a"),
	true = match("^.*$", "a"),
	{ok}.