find

#!/usr/bin/env escript

%% this is the pascal code diagram
%% --
%% find
%%   getpat
%%     makepat
%%       getccl
%%         dodash
%%       stclose
%%   match
%%     amatch
%%       omatch
%%         locate
%%       patsize

%% find -- find patterns in text
%%
%% for each line, if a match is found, return line

%% this is a mock version, should `getlines` first
find(Pattern, Input) ->
    case match(Pattern, Input) of
        true -> Input;
        false -> []
    end.

%% match -- find match anywhere on line
%%
%% returns true for match, false for mismatch
match(Pattern, Line) ->
    case amatch(Pattern, Line) of
        [] -> false;
        _ -> true
    end.

%% amatch -- look for match of pattern at line
%%
%% returns the position of all matches as a list
%%
%% General cases should be lower in order, metacharacters and classes 
%% need to check pattern matching first.
amatch(Pattern, Line) ->
    amatch({Pattern, Pattern}, Line, 1, []).

%% Test before base case for $ -- end of line
amatch({Pattern, [PH|PT]}, [], Pos, PosList) when PH =:= $$ ->
    amatch({Pattern, PT}, {[], []}, Pos, PosList);
amatch({Pattern, [PH|[]]}, {[], []}, Pos, PosList) when PH =:= $$ ->
                                                % test case example: true = match("a$", [$b, $\n, $a]),
    amatch({Pattern, Pattern}, [], Pos+1, lists:concat([PosList, [Pos]]));

%% Base cases
amatch(_, [], _, PosList) ->
    PosList;
amatch({_, []}, {[], []}, Pos, PosList) ->
    lists:concat([PosList, [Pos]]);
amatch(_, {[], []}, _, PosList) ->
    PosList;

%% $ -- match the end of line
%% we detect the end of the line by an empty Head
amatch({Pattern, [PH|_]}, {InitT, []}, Pos, PosList) when PH =:= $$ ->
    amatch({Pattern, Pattern}, InitT, Pos+1, lists:concat([PosList, [Pos]]));
%% if there is a endline as the last sequential match, it's a match
amatch({Pattern, [PH|PT]}, {InitT, [$\n|T]}, Pos, PosList) when PH =:= $$ ->
    case T =:= [] of
        true -> amatch({Pattern, PT}, {InitT, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, InitT, Pos+1, PosList)
    end;

%% % -- match the beginning of line
%% 1) if it's the beginning of line, keep position and
%%    test sequentially starting from the same position
%%    hence {[H|T], [H|T]} instead of {T, T}.
%% 2) if isn't the beginning of line, go to next position and
%%    test same pattern in Tail, it will obviously never match
%%    since Tail isn't the beginning anymore.
%%
%% Further tests is needed for this behavior.
amatch({Pattern, [PH|PT]}, [H|T], Pos, PosList) when PH =:= $% ->
    case Pos =:= 1 of
        true -> amatch({Pattern, PT}, {[H|T], [H|T]}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, T, Pos+1, PosList)
    end;


%% [^...] -- match character "not in" class
%% i.e. [^a-z] matches everything that it's not a lower case letter
amatch({Pattern, [$[, $^, $]|PT]}, Line, Pos, PosList) ->
    amatch({Pattern, PT, {parse, not_class, [$]]}}, Line, Pos, PosList);

amatch({Pattern, [$[, $^|PT]}, Line, Pos, PosList) ->
    amatch({Pattern, PT, {parse, not_class, []}}, Line, Pos, PosList);

%% [...] -- match character class
%% i.e. [a-z], [A-Z], [a-zA-Z], [0-9], [0-9a-zA-Z]
amatch({Pattern, [$[|PT]}, Line, Pos, PosList) ->
    amatch({Pattern, PT, {parse, in_class, []}}, Line, Pos, PosList);

amatch({Pattern, [$], $]|PT], {parse, ClassType, Class}}, Line, Pos, PosList) ->
    NewClass = lists:concat([Class, "]"]),
    amatch({Pattern, PT, {class, ClassType, NewClass}}, Line, Pos, PosList);
amatch({Pattern, [$]|PT], {parse, ClassType, Class}}, Line, Pos, PosList) ->
    amatch({Pattern, PT, {class, ClassType, Class}}, Line, Pos, PosList);

amatch({Pattern, [C1, $-, $]|PT], {parse, ClassType, Class}}, Line, Pos, PosList) ->
    NewClass = lists:concat([Class, [C1, $-]]),  % case for not-ranged dash i.e. [b-]
    amatch({Pattern, [$]|PT], {parse, ClassType, NewClass}}, Line, Pos, PosList);

amatch({Pattern, [C1, $-, C2|PT], {parse, ClassType, Class}}, Line, Pos, PosList) ->
    NewClass = lists:concat([Class, lists:seq(C1, C2)]),
    amatch({Pattern, PT, {parse, ClassType, NewClass}}, Line, Pos, PosList);
amatch({Pattern, [PH|PT], {parse, ClassType, Class}}, Line, Pos, PosList) ->
    NewClass = lists:concat([Class, [PH]]), % case for a single char i.e. [a], [ab], [a-zb]
    amatch({Pattern, PT, {parse, ClassType, NewClass}}, Line, Pos, PosList);

amatch({Pattern, PT, {class, in_class, Class}}, [H|T], Pos, PosList) ->
    case lists:member(H, Class) of
        true -> amatch({Pattern, PT}, {T, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, T, Pos+1, PosList)
    end;
amatch({Pattern, PT, {class, not_class, Class}}, [H|T], Pos, PosList) ->
    case not lists:member(H, Class) of
        true -> amatch({Pattern, PT}, {T, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, T, Pos+1, PosList)
    end;
amatch({Pattern, PT, {class, in_class, Class}}, {InitT, [H|T]}, Pos, PosList) ->
    case lists:member(H, Class) of
        true -> amatch({Pattern, PT}, {InitT, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, InitT, Pos+1, PosList)
    end;
amatch({Pattern, PT, {class, not_class, Class}}, {InitT, [H|T]}, Pos, PosList) ->
    case not lists:member(H, Class) of
        true -> amatch({Pattern, PT}, {InitT, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, InitT, Pos+1, PosList)
    end;

%% ? -- match any single character except newline
amatch({Pattern, [PH|PT]}, [H|T], Pos, PosList) when PH =:= $? ->
    case H =/= $\n of
        true -> amatch({Pattern, PT}, {T, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, T, Pos+1, PosList)
    end;
amatch({Pattern, [PH|PT]}, {InitT, [H|T]}, Pos, PosList) when PH =:= $? ->
    case H =/= $\n of
        true -> amatch({Pattern, PT}, {InitT, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, InitT, Pos+1, PosList)
    end;

%% sequence of literal characters
amatch({Pattern, []}, {InitT, _}, Pos, PosList) ->
    amatch({Pattern, Pattern}, InitT, Pos+1, lists:concat([PosList, [Pos]]));
amatch({Pattern, [PH|PT]}, {InitT, [H|T]}, Pos, PosList) ->
    case H =:= PH of
        true -> amatch({Pattern, PT}, {InitT, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, InitT, Pos+1, PosList)
    end;

%% if a single match is found, will test a sequential match
%% a single literal is a sequence of a literal + empty list,
%% so we can reuse code from a sequence of literal characters
amatch({Pattern, [PH|PT]}, [H|T], Pos, PosList) ->
    case H =:= PH of
        true -> amatch({Pattern, PT}, {T, T}, Pos, PosList);
        false -> amatch({Pattern, Pattern}, T, Pos+1, PosList)
    end.

main([Pattern, File|_]) ->
    {Pattern, File};
main(["-t"|_]) ->
    test().

test() ->
    %% test 1 -- lines are properly read and written
    Input1 = "This is a single input.",
    Input1 = find("i", Input1),
    [] = find("z", Input1),

    %% test 2 -- find single character 'x' in text
    %%        -- find literal sequence 'xx' in text
    [] = amatch("z", "this is a single input"),

    [3, 6, 12] = amatch([$i], "This is a line"),
    [1,2,3,4,5,6] = amatch("a", "aaaaaa"),

    [6] = amatch("et", "Two letters"),
    [1,2,3,4,5] = amatch("aa", "aaaaaa"),

    %% test 3 -- match returns true or false
    true = match("et", "Two letters"),
    false = match("foobar", "foo bar"),

    %% test 4 -- ? matches any character except newline
    true = match("?", [32]), % ASCII 32 = whitespace
    true = match("?", " "),
    false = match("?", ""),
    true = match("?", "aaa"),
    false = match("?", [$\n]),

    AnyInput = "Match everything",
    AnyRange = lists:seq(1, erlang:length(AnyInput)),

    true = match("?", AnyInput),
    false = match("?z", AnyInput),
    AnyRange = amatch("?", AnyInput),
    AnyRange = amatch("?", AnyInput++[$\n]),
    [2, 11, 18, 27] = amatch("?t", AnyInput++AnyInput),
    [2, 11, 19, 28] = amatch("?t", AnyInput++[$\n]++AnyInput),

    true = match("?t?", AnyInput),
    [2, 11] = amatch("?t?", AnyInput),

    %% test 5 -- % beginning of line
    true = match("%abc", "abcc"),
    true = match("%", "abc"),
    true = match("%?", "abc"),
    true = match("%a?", "abc"),
    true = match("%a?c", "abc"),
    false = match("%a?b", "abc"),
    false = match("%bc", "abc"),
    false = match("%?c", "abc"),
    true = match("%?b", "abc"),
    false = match("%b", [$a, $\n, $b, $\n, $c]),

    [1] = amatch("%abc", "abcc"),
    [1] = amatch("%?", "abc"),
    [1] = amatch("%?b", "abc"),
    [] = amatch("%?c", "abc"),

    %% test 6 -- $ end of line
    true = match("abc$", "abc"),
    true = match("$", "abc"),
    true = match("abc$", "aabc"),
    false = match("abc$", "aabcd"),

    true = match("%abc$", "abc"),
    false = match("%abc$", "abcc"),
    false = match("%abc$", "aabc"),

    true = match("$", [$a, $\n, $b, $\n]),
    true = match("$", [$a, $\n, $b]),
    false = match("a$", [$a, $\n, $b, $\n]),
    true = match("a$", [$b, $\n, $a, $\n]),
    true = match("a$", [$b, $\n, $a]),

    false = match("aa$", [$a, $a, $\n, $b, $\n]),
    true = match("aa$", [$b, $\n, $a, $a, $\n]),
    true = match("aa$", [$b, $\n, $a, $a]),

    %% test 7 - character class
    false = match("[k]", "ab"),
    false = match("a[bc]d", "abc"),
    true = match("a[bc]d", "abd"),
    true = match("a[b]d", "abd"),
    true = match("[a][b][d]", "abd"),
    true = match("?[b]?", "abd"),
    false = match("?[b]?", "aBd"),

    false = match("a[a-d]e", "abd"),
    true = match("a[b-d]e", "ace"),
    true = match("a[b-d]", "aac"),
    true = match("a[-b]", "a-"),  % means "dash or b"
    true = match("a[b-]", "a-"),  % means "b or dash"

    %% TODO -- are those cases correct?
    false = match("[b-a]", "-"),  % should return error (perl) but will behave as empty class
    false = match("a[]b", "-"),  % should return error (perl), but will behave as empty class
    false = match("a[", "-"),  % should return error (perl), unknown behavior (not covered)
    true = match("a]", "a]"),
    true = match("a[]]b", "a]b"),

    true = match("a[a-cz]", "ab"),
    true = match("a[a-cz]", "az"),
    false = match("a[a-cz]", "ad"),
    true = match("[a-zA-Z_][a-zA-Z0-9_]", "alpha"),
    false = match("[_A-Z]", "}"),
    true = match("[89]", "9"),
    true = match("[3-6]", "5"),
    false = match("[1-57-9]", "6"),
    true = match("[1-57-9]", "4"),
    true = match("[1-57-9]", "9"),

    %% test 8 - "not in" character class
    true = match("a[^bc]d", "aed"),
    false = match("a[^bc]d", "abd"),
    true = match("a[^-b]c", "adc"),
    false = match("a[^-b]c", "a-c"),
    false = match("a[^]b]c", "a]c"),
    true = match("a[^]b]c", "adc"),

    ok.

%% TODO
%%
%% * closure (zero or more occurrences of previous pattern)
%%
%% @c escaped character (@%, @[, @*, @^, @-, @@, @])
%% an escape sequence consist of @n (newline), @t (tab)
%% or @c (escaped character)