From f06f499690ef1f5c8659128095a82d6c9b834d68 Mon Sep 17 00:00:00 2001 From: Patrik Nyblom Date: Tue, 20 Apr 2010 17:32:48 +0200 Subject: Add random compare testcase Fix heap-hole when trapping in binary.c Fix boyer more segfaulting when searchstring is longer than haystack --- lib/stdlib/test/Makefile | 2 + lib/stdlib/test/binary_module_SUITE.erl | 72 ++++++++++++++++++++++++++++++++- lib/stdlib/test/binref.erl | 34 ++++++++-------- 3 files changed, 89 insertions(+), 19 deletions(-) (limited to 'lib') diff --git a/lib/stdlib/test/Makefile b/lib/stdlib/test/Makefile index 9beac93eb8..3bbd9ce318 100644 --- a/lib/stdlib/test/Makefile +++ b/lib/stdlib/test/Makefile @@ -9,6 +9,8 @@ MODULES= \ array_SUITE \ base64_SUITE \ beam_lib_SUITE \ + binary_module_SUITE \ + binref \ c_SUITE \ calendar_SUITE \ dets_SUITE \ diff --git a/lib/stdlib/test/binary_module_SUITE.erl b/lib/stdlib/test/binary_module_SUITE.erl index 31d0812cfc..b6d3dde1d4 100644 --- a/lib/stdlib/test/binary_module_SUITE.erl +++ b/lib/stdlib/test/binary_module_SUITE.erl @@ -1,6 +1,6 @@ -module(binary_module_SUITE). --export([all/1, interesting/1]). +-export([all/1, interesting/1,random_ref_comp/1]). -define(STANDALONE,1). @@ -24,7 +24,7 @@ run() -> -endif. -all(suite) -> [interesting]. +all(suite) -> [interesting,random_ref_comp]. interesting(doc) -> @@ -94,3 +94,71 @@ do_interesting(Module) -> [<<"34">>,<<"34">>, <<"12347">>,<<"2346">>]), ok. + +random_ref_comp(doc) -> + ["Test pseudorandomly generated cases against reference imlementation"]; +random_ref_comp(Config) when is_list(Config) -> + put(success_counter,0), + random:seed({1271,769940,559934}), + do_random_match_comp(5000,{1,40},{30,1000}), + io:format("Number of successes: ~p~n",[get(success_counter)]), + do_random_match_comp2(5000,{1,40},{30,1000}), + io:format("Number of successes: ~p~n",[get(success_counter)]), + ok. + +do_random_match_comp(0,_,_) -> + ok; +do_random_match_comp(N,NeedleRange,HaystackRange) -> + Needle = random_string(NeedleRange), + Haystack = random_string(HaystackRange), + true = do_match_comp(Needle,Haystack), + do_random_match_comp(N-1,NeedleRange,HaystackRange). + +do_random_match_comp2(0,_,_) -> + ok; +do_random_match_comp2(N,NeedleRange,HaystackRange) -> + Haystack = random_string(HaystackRange), + Needle = random_substring(NeedleRange,Haystack), + true = do_match_comp(Needle,Haystack), + do_random_match_comp2(N-1,NeedleRange,HaystackRange). + +do_match_comp(N,H) -> + A = binref:match(H,N), + B = binref:match(H,binref:compile_pattern([N])), + C = binary:match(H,N), + D = binary:match(H,binary:compile_pattern([N])), + if + A =/= nomatch -> + put(success_counter,get(success_counter)+1); + true -> + ok + end, + case {(A =:= B), (B =:= C),(C =:= D)} of + {true,true,true} -> + true; + _ -> + io:format("Failed to match ~s (needle) against ~s (haystack)~n", + [N,H]), + io:format("A:~p,~nB:~p,~n,C:~p,~n,D:~p.~n", + [A,B,C,D]), + exit(mismatch) + end. + +one_random(N) -> + M = ((N - 1) rem 68) + 1, + element(M,{$a,$b,$c,$d,$e,$f,$g,$h,$i,$j,$k,$l,$m,$n,$o,$p,$q,$r,$s,$t,$u,$v,$w,$x,$y,$z,$å,$ä,$ö,$A,$B,$C,$D,$E,$F,$G,$H,$I,$J,$K,$L,$M,$N,$O,$P,$Q,$R,$S,$T,$U,$V,$W,$X,$Y,$Z,$Å,$Ä,$Ö,$0,$1,$2,$3,$4,$5,$6,$7,$8,$9}). + +random_string({Min,Max}) -> + X = random:uniform(Max - Min + 1) + Min - 1, + list_to_binary([one_random(random:uniform(68)) || _ <- lists:seq(1,X)]). +random_substring({Min,Max},Hay) -> + X = random:uniform(Max - Min + 1) + Min - 1, + Y = byte_size(Hay), + Z = if + X > Y -> Y; + true -> X + end, + PMax = Y - Z, + Pos = random:uniform(PMax + 1) - 1, + <<_:Pos/binary,Res:Z/binary,_/binary>> = Hay, + Res. diff --git a/lib/stdlib/test/binref.erl b/lib/stdlib/test/binref.erl index 270796c8f9..d93f82fda9 100644 --- a/lib/stdlib/test/binref.erl +++ b/lib/stdlib/test/binref.erl @@ -33,8 +33,8 @@ match(Haystack,{Needles},Options) -> match(Haystack,Needles,Options) -> try true = is_binary(Haystack) and is_list(Needles), % badarg, not function_clause - case get_opts_match(Options,no) of - no -> + case get_opts_match(Options,nomatch) of + nomatch -> mloop(Haystack,Needles); {A,B} when B > 0 -> <<_:A/binary,SubStack:B/binary,_/binary>> = Haystack, @@ -45,7 +45,7 @@ match(Haystack,Needles,Options) -> <<_:Start/binary,SubStack:Len/binary,_/binary>> = Haystack, mloop(SubStack,Needles,Start,Len+Start); _ -> - no + nomatch end catch _:_ -> @@ -60,8 +60,8 @@ matches(Haystack,{Needles},Options) -> matches(Haystack,Needles,Options) -> try true = is_binary(Haystack) and is_list(Needles), % badarg, not function_clause - case get_opts_match(Options,no) of - no -> + case get_opts_match(Options,nomatch) of + nomatch -> msloop(Haystack,Needles); {A,B} when B > 0 -> <<_:A/binary,SubStack:B/binary,_/binary>> = Haystack, @@ -83,10 +83,10 @@ mloop(Haystack,Needles) -> mloop(Haystack,Needles,0,byte_size(Haystack)). mloop(_Haystack,_Needles,N,M) when N >= M -> - no; + nomatch; mloop(Haystack,Needles,N,M) -> - case mloop2(Haystack,Needles,N,no) of - no -> + case mloop2(Haystack,Needles,N,nomatch) of + nomatch -> % Not found <<_:8,NewStack/binary>> = Haystack, mloop(NewStack,Needles,N+1,M); @@ -100,8 +100,8 @@ msloop(Haystack,Needles) -> msloop(_Haystack,_Needles,N,M) when N >= M -> []; msloop(Haystack,Needles,N,M) -> - case mloop2(Haystack,Needles,N,no) of - no -> + case mloop2(Haystack,Needles,N,nomatch) of + nomatch -> % Not found <<_:8,NewStack/binary>> = Haystack, msloop(NewStack,Needles,N+1,M); @@ -123,7 +123,7 @@ mloop2(Haystack,[Needle|Tail],N,Candidate) -> case Haystack of <> -> NewCandidate = case Candidate of - no -> + nomatch -> {N,NS}; {N,ONS} when ONS < NS -> {N,NS}; @@ -145,10 +145,10 @@ split(Haystack,{Needles},Options) -> split(Haystack, Needles, Options); split(Haystack,Needles,Options) -> try - {Part,Global,Trim} = get_opts_split(Options,{no,false,false}), + {Part,Global,Trim} = get_opts_split(Options,{nomatch,false,false}), {Start,End,NewStack} = case Part of - no -> + nomatch -> {0,byte_size(Haystack),Haystack}; {A,B} when B >= 0 -> <<_:A/binary,SubStack:B/binary,_/binary>> = Haystack, @@ -164,7 +164,7 @@ split(Haystack,Needles,Options) -> msloop(NewStack,Needles,Start,End); true -> case mloop(NewStack,Needles,Start,End) of - no -> + nomatch -> []; X -> [X] @@ -206,10 +206,10 @@ replace(Haystack,{Needles},Replacement,Options) -> replace(Haystack,Needles,Replacement,Options) -> try true = is_binary(Replacement), % Make badarg instead of function clause - {Part,Global,Insert} = get_opts_replace(Options,{no,false,[]}), + {Part,Global,Insert} = get_opts_replace(Options,{nomatch,false,[]}), {Start,End,NewStack} = case Part of - no -> + nomatch -> {0,byte_size(Haystack),Haystack}; {A,B} when B >= 0 -> <<_:A/binary,SubStack:B/binary,_/binary>> = Haystack, @@ -225,7 +225,7 @@ replace(Haystack,Needles,Replacement,Options) -> msloop(NewStack,Needles,Start,End); true -> case mloop(NewStack,Needles,Start,End) of - no -> + nomatch -> []; X -> [X] -- cgit v1.2.3