1#!./perl 2$|=1; 3 4BEGIN { 5 chdir 't' if -d 't'; 6 require './test.pl'; 7 set_up_inc('../lib'); 8} 9use warnings; 10plan(tests => 203); 11use Tie::Array; # we need to test sorting tied arrays 12 13# these shouldn't hang 14{ 15 no warnings; 16 sort { for ($_ = 0;; $_++) {} } @a; 17 sort { while(1) {} } @a; 18 sort { while(1) { last; } } @a; 19 sort { while(0) { last; } } @a; 20 21 # Change 26011: Re: A surprising segfault 22 map scalar(sort(+())), ('')x68; 23} 24 25sub Backwards { $a lt $b ? 1 : $a gt $b ? -1 : 0 } 26sub Backwards_stacked($$) { my($a,$b) = @_; $a lt $b ? 1 : $a gt $b ? -1 : 0 } 27sub Backwards_other { $a lt $b ? 1 : $a gt $b ? -1 : 0 } 28 29my $upperfirst = 'A' lt 'a'; 30 31# Beware: in future this may become hairier because of possible 32# collation complications: qw(A a B b) can be sorted at least as 33# any of the following 34# 35# A a B b 36# A B a b 37# a b A B 38# a A b B 39# 40# All the above orders make sense. 41# 42# That said, EBCDIC sorts all small letters first, as opposed 43# to ASCII which sorts all big letters first. 44 45@harry = ('dog','cat','x','Cain','Abel'); 46@george = ('gone','chased','yz','punished','Axed'); 47 48$x = join('', sort @harry); 49$expected = $upperfirst ? 'AbelCaincatdogx' : 'catdogxAbelCain'; 50 51cmp_ok($x,'eq',$expected,'upper first 1'); 52 53$x = join('', sort( Backwards @harry)); 54$expected = $upperfirst ? 'xdogcatCainAbel' : 'CainAbelxdogcat'; 55 56cmp_ok($x,'eq',$expected,'upper first 2'); 57 58$x = join('', sort( Backwards_stacked @harry)); 59$expected = $upperfirst ? 'xdogcatCainAbel' : 'CainAbelxdogcat'; 60 61cmp_ok($x,'eq',$expected,'upper first 3'); 62 63$x = join('', sort @george, 'to', @harry); 64$expected = $upperfirst ? 65 'AbelAxedCaincatchaseddoggonepunishedtoxyz' : 66 'catchaseddoggonepunishedtoxyzAbelAxedCain' ; 67 68my @initially_sorted = ( 0 .. 260, 69 0x3FF, 0x400, 0x401, 70 0x7FF, 0x800, 0x801, 71 0x3FFF, 0x4000, 0x4001, 72 0xFFFF, 0x10000, 0x10001, 73 ); 74# It makes things easier below if there are an even number of elements in the 75# array. 76if (scalar(@initially_sorted) % 2 == 1) { 77 push @initially_sorted, $initially_sorted[-1] + 1; 78} 79 80# We convert to a chr(), but prepend a constant string to make sure things can 81# work on more than a single character. 82my $prefix = "a\xb6"; 83my $prefix_len = length $prefix; 84 85my @chr_initially_sorted = @initially_sorted; 86$_ = $prefix . chr($_) for @chr_initially_sorted; 87 88# Create a very unsorted version by reversing it, and then pushing the same 89# code points again, but pair-wise reversed. 90my @initially_unsorted = reverse @chr_initially_sorted; 91for (my $i = 0; $i < @chr_initially_sorted - 1; $i += 2) { 92 push @initially_unsorted, $chr_initially_sorted[$i+1], 93 $chr_initially_sorted[$i]; 94} 95 96# And, an all-UTF-8 version 97my @utf8_initialy_unsorted = @initially_unsorted; 98utf8::upgrade($_) for @utf8_initialy_unsorted; 99 100# Sort the non-UTF-8 version 101my @non_utf8_result = sort @initially_unsorted; 102my @wrongly_utf8; 103my $ordered_correctly = 1; 104for my $i (0 .. @chr_initially_sorted -1) { 105 if ( $chr_initially_sorted[$i] ne $non_utf8_result[2*$i] 106 || $chr_initially_sorted[$i] ne $non_utf8_result[2*$i+1]) 107 { 108 $ordered_correctly = 0; 109 last; 110 } 111 push @wrongly_utf8, $i if $i < 256 && utf8::is_utf8($non_utf8_result[$i]); 112} 113if (! ok($ordered_correctly, "sort of non-utf8 list worked")) { 114 diag ("This should be in numeric order (with 2 instances of every code point):\n" 115 . join " ", map { sprintf "%02x", ord substr $_, $prefix_len, 1 } @non_utf8_result); 116} 117if (! is(@wrongly_utf8, 0, 118 "No elements were wrongly converted to utf8 in sorting")) 119{ 120 diag "For code points " . join " ", @wrongly_utf8; 121} 122 123# And then the UTF-8 one 124my @wrongly_non_utf8; 125$ordered_correctly = 1; 126my @utf8_result = sort @utf8_initialy_unsorted; 127for my $i (0 .. @chr_initially_sorted -1) { 128 if ( $chr_initially_sorted[$i] ne $utf8_result[2*$i] 129 || $chr_initially_sorted[$i] ne $utf8_result[2*$i+1]) 130 { 131 $ordered_correctly = 0; 132 last; 133 } 134 push @wrongly_non_utf8, $i unless utf8::is_utf8($utf8_result[$i]); 135} 136if (! ok($ordered_correctly, "sort of utf8 list worked")) { 137 diag ("This should be in numeric order (with 2 instances of every code point):\n" 138 . join " ", map { sprintf "%02x", ord substr $_, $prefix_len, 1 } @utf8_result); 139} 140if (! is(@wrongly_non_utf8, 0, 141 "No elements were wrongly converted from utf8 in sorting")) 142{ 143 diag "For code points " . join " ", @wrongly_non_utf8; 144} 145 146cmp_ok($x,'eq',$expected,'upper first 4'); 147$" = ' '; 148@a = (); 149@b = reverse @a; 150cmp_ok("@b",'eq',"",'reverse 1'); 151 152@a = (1); 153@b = reverse @a; 154cmp_ok("@b",'eq',"1",'reverse 2'); 155 156@a = (1,2); 157@b = reverse @a; 158cmp_ok("@b",'eq',"2 1",'reverse 3'); 159 160@a = (1,2,3); 161@b = reverse @a; 162cmp_ok("@b",'eq',"3 2 1",'reverse 4'); 163 164@a = (1,2,3,4); 165@b = reverse @a; 166cmp_ok("@b",'eq',"4 3 2 1",'reverse 5'); 167 168@a = (10,2,3,4); 169@b = sort {$a <=> $b;} @a; 170cmp_ok("@b",'eq',"2 3 4 10",'sort numeric'); 171 172$sub = 'Backwards'; 173$x = join('', sort $sub @harry); 174$expected = $upperfirst ? 'xdogcatCainAbel' : 'CainAbelxdogcat'; 175 176cmp_ok($x,'eq',$expected,'sorter sub name in var 1'); 177 178$sub = 'Backwards_stacked'; 179$x = join('', sort $sub @harry); 180$expected = $upperfirst ? 'xdogcatCainAbel' : 'CainAbelxdogcat'; 181 182cmp_ok($x,'eq',$expected,'sorter sub name in var 2'); 183 184# literals, combinations 185 186@b = sort (4,1,3,2); 187cmp_ok("@b",'eq','1 2 3 4','just sort'); 188 189 190@b = sort grep { $_ } (4,1,3,2); 191cmp_ok("@b",'eq','1 2 3 4','grep then sort'); 192 193 194@b = sort map { $_ } (4,1,3,2); 195cmp_ok("@b",'eq','1 2 3 4','map then sort'); 196 197 198@b = sort reverse (4,1,3,2); 199cmp_ok("@b",'eq','1 2 3 4','reverse then sort'); 200 201 202@b = sort CORE::reverse (4,1,3,2); 203cmp_ok("@b",'eq','1 2 3 4','CORE::reverse then sort'); 204 205eval { @b = sort CORE::revers (4,1,3,2); }; 206like($@, qr/^Undefined sort subroutine "CORE::revers" called at /); 207 208 209sub twoface { no warnings 'redefine'; *twoface = sub { $a <=> $b }; &twoface } 210eval { @b = sort twoface 4,1,3,2 }; 211cmp_ok("@b",'eq','1 2 3 4','redefine sort sub inside the sort sub'); 212 213 214eval { no warnings 'redefine'; *twoface = sub { &Backwards } }; 215ok(!$@,"redefining sort subs outside the sort \$@=[$@]"); 216 217eval { @b = sort twoface 4,1,3,2 }; 218cmp_ok("@b",'eq','4 3 2 1','twoface redefinition'); 219 220{ 221 no warnings 'redefine'; 222 *twoface = sub { *twoface = *Backwards_other; $a <=> $b }; 223} 224 225eval { @b = sort twoface 4,1,9,5 }; 226ok(($@ eq "" && "@b" eq "1 4 5 9"),'redefinition should not take effect during the sort'); 227 228{ 229 no warnings 'redefine'; 230 *twoface = sub { 231 eval 'sub twoface { $a <=> $b }'; 232 die($@ eq "" ? "good\n" : "bad\n"); 233 $a <=> $b; 234 }; 235} 236eval { @b = sort twoface 4,1 }; 237cmp_ok(substr($@,0,4), 'eq', 'good', 'twoface eval'); 238 239eval <<'CODE'; 240 no warnings qw(deprecated syntax); 241 my @result = sort main'Backwards 'one', 'two'; 242CODE 243cmp_ok($@,'eq','',q(old skool package)); 244 245eval <<'CODE'; 246 # "sort 'one', 'two'" should not try to parse "'one" as a sort sub 247 my @result = sort 'one', 'two'; 248CODE 249cmp_ok($@,'eq','',q(one is not a sub)); 250 251{ 252 my $sortsub = \&Backwards; 253 my $sortglob = *Backwards; 254 my $sortglobr = \*Backwards; 255 my $sortname = 'Backwards'; 256 @b = sort $sortsub 4,1,3,2; 257 cmp_ok("@b",'eq','4 3 2 1','sortname 1'); 258 @b = sort $sortglob 4,1,3,2; 259 cmp_ok("@b",'eq','4 3 2 1','sortname 2'); 260 @b = sort $sortname 4,1,3,2; 261 cmp_ok("@b",'eq','4 3 2 1','sortname 3'); 262 @b = sort $sortglobr 4,1,3,2; 263 cmp_ok("@b",'eq','4 3 2 1','sortname 4'); 264} 265 266{ 267 my $sortsub = \&Backwards_stacked; 268 my $sortglob = *Backwards_stacked; 269 my $sortglobr = \*Backwards_stacked; 270 my $sortname = 'Backwards_stacked'; 271 @b = sort $sortsub 4,1,3,2; 272 cmp_ok("@b",'eq','4 3 2 1','sortname 5'); 273 @b = sort $sortglob 4,1,3,2; 274 cmp_ok("@b",'eq','4 3 2 1','sortname 6'); 275 @b = sort $sortname 4,1,3,2; 276 cmp_ok("@b",'eq','4 3 2 1','sortname 7'); 277 @b = sort $sortglobr 4,1,3,2; 278 cmp_ok("@b",'eq','4 3 2 1','sortname 8'); 279} 280 281{ 282 local $sortsub = \&Backwards; 283 local $sortglob = *Backwards; 284 local $sortglobr = \*Backwards; 285 local $sortname = 'Backwards'; 286 @b = sort $sortsub 4,1,3,2; 287 cmp_ok("@b",'eq','4 3 2 1','sortname local 1'); 288 @b = sort $sortglob 4,1,3,2; 289 cmp_ok("@b",'eq','4 3 2 1','sortname local 2'); 290 @b = sort $sortname 4,1,3,2; 291 cmp_ok("@b",'eq','4 3 2 1','sortname local 3'); 292 @b = sort $sortglobr 4,1,3,2; 293 cmp_ok("@b",'eq','4 3 2 1','sortname local 4'); 294} 295 296{ 297 local $sortsub = \&Backwards_stacked; 298 local $sortglob = *Backwards_stacked; 299 local $sortglobr = \*Backwards_stacked; 300 local $sortname = 'Backwards_stacked'; 301 @b = sort $sortsub 4,1,3,2; 302 cmp_ok("@b",'eq','4 3 2 1','sortname local 5'); 303 @b = sort $sortglob 4,1,3,2; 304 cmp_ok("@b",'eq','4 3 2 1','sortname local 6'); 305 @b = sort $sortname 4,1,3,2; 306 cmp_ok("@b",'eq','4 3 2 1','sortname local 7'); 307 @b = sort $sortglobr 4,1,3,2; 308 cmp_ok("@b",'eq','4 3 2 1','sortname local 8'); 309} 310 311## exercise sort builtins... ($a <=> $b already tested) 312@a = ( 5, 19, 1996, 255, 90 ); 313@b = sort { 314 my $dummy; # force blockness 315 return $b <=> $a 316} @a; 317cmp_ok("@b",'eq','1996 255 90 19 5','force blockness'); 318 319$x = join('', sort { $a cmp $b } @harry); 320$expected = $upperfirst ? 'AbelCaincatdogx' : 'catdogxAbelCain'; 321cmp_ok($x,'eq',$expected,'a cmp b'); 322 323$x = join('', sort { $b cmp $a } @harry); 324$expected = $upperfirst ? 'xdogcatCainAbel' : 'CainAbelxdogcat'; 325cmp_ok($x,'eq',$expected,'b cmp a'); 326 327{ 328 use integer; 329 @b = sort { $a <=> $b } @a; 330 cmp_ok("@b",'eq','5 19 90 255 1996','integer a <=> b'); 331 332 @b = sort { $b <=> $a } @a; 333 cmp_ok("@b",'eq','1996 255 90 19 5','integer b <=> a'); 334 335 $x = join('', sort { $a cmp $b } @harry); 336 $expected = $upperfirst ? 'AbelCaincatdogx' : 'catdogxAbelCain'; 337 cmp_ok($x,'eq',$expected,'integer a cmp b'); 338 339 $x = join('', sort { $b cmp $a } @harry); 340 $expected = $upperfirst ? 'xdogcatCainAbel' : 'CainAbelxdogcat'; 341 cmp_ok($x,'eq',$expected,'integer b cmp a'); 342 343} 344 345 346 347$x = join('', sort { $a <=> $b } 3, 1, 2); 348cmp_ok($x,'eq','123',q(optimized-away comparison block doesn't take any other arguments away with it)); 349 350# test sorting in non-main package 351{ 352 package Foo; 353 @a = ( 5, 19, 1996, 255, 90 ); 354 @b = sort { $b <=> $a } @a; 355 ::cmp_ok("@b",'eq','1996 255 90 19 5','not in main:: 1'); 356 357 @b = sort ::Backwards_stacked @a; 358 ::cmp_ok("@b",'eq','90 5 255 1996 19','not in main:: 2'); 359 360 # check if context for sort arguments is handled right 361 sub test_if_list { 362 my $gimme = wantarray; 363 ::is($gimme,1,'wantarray 1'); 364 } 365 my $m = sub { $a <=> $b }; 366 367 sub cxt_one { sort $m test_if_list() } 368 cxt_one(); 369 sub cxt_two { sort { $a <=> $b } test_if_list() } 370 cxt_two(); 371 sub cxt_three { sort &test_if_list() } 372 cxt_three(); 373 sub cxt_three_anna_half { sort 0, test_if_list() } 374 cxt_three_anna_half(); 375 376 sub test_if_scalar { 377 my $gimme = wantarray; 378 ::is(!($gimme or !defined($gimme)),1,'wantarray 2'); 379 } 380 381 $m = \&test_if_scalar; 382 sub cxt_four { sort $m 1,2 } 383 @x = cxt_four(); 384 sub cxt_five { sort { test_if_scalar($a,$b); } 1,2 } 385 @x = cxt_five(); 386 sub cxt_six { sort test_if_scalar 1,2 } 387 @x = cxt_six(); 388} 389 390 391# test against a reentrancy bug 392{ 393 package Bar; 394 sub compare { $a cmp $b } 395 sub reenter { my @force = sort compare qw/a b/ } 396} 397{ 398 my($def, $init) = (0, 0); 399 @b = sort { 400 $def = 1 if defined $Bar::a; 401 Bar::reenter() unless $init++; 402 $a <=> $b 403 } qw/4 3 1 2/; 404 cmp_ok("@b",'eq','1 2 3 4','reenter 1'); 405 406 ok(!$def,'reenter 2'); 407} 408 409 410{ 411 sub routine { "one", "two" }; 412 @a = sort(routine(1)); 413 cmp_ok("@a",'eq',"one two",'bug id 19991001.003 (#1549)'); 414} 415 416 417# check for in-place optimisation of @a = sort @a 418{ 419 my ($r1,$r2,@a); 420 our @g; 421 @g = (3,2,1); $r1 = \$g[2]; @g = sort @g; $r2 = \$g[0]; 422 is "$$r1-$$r2-@g", "1-1-1 2 3", "inplace sort of global"; 423 424 @a = qw(b a c); $r1 = \$a[1]; @a = sort @a; $r2 = \$a[0]; 425 is "$$r1-$$r2-@a", "a-a-a b c", "inplace sort of lexical"; 426 427 @g = (2,3,1); $r1 = \$g[1]; @g = sort { $b <=> $a } @g; $r2 = \$g[0]; 428 is "$$r1-$$r2-@g", "3-3-3 2 1", "inplace reversed sort of global"; 429 430 @g = (2,3,1); 431 $r1 = \$g[1]; @g = sort { $a<$b?1:$a>$b?-1:0 } @g; $r2 = \$g[0]; 432 is "$$r1-$$r2-@g", "3-3-3 2 1", "inplace custom sort of global"; 433 434 sub mysort { $b cmp $a }; 435 @a = qw(b c a); $r1 = \$a[1]; @a = sort mysort @a; $r2 = \$a[0]; 436 is "$$r1-$$r2-@a", "c-c-c b a", "inplace sort with function of lexical"; 437 438 my @t; 439 tie @t, 'Tie::StdArray'; 440 441 @t = qw(b c a); @t = sort @t; 442 is "@t", "a b c", "inplace sort of tied array"; 443 444 @t = qw(b c a); @t = sort mysort @t; 445 is "@t", "c b a", "inplace sort of tied array with function"; 446 447 # [perl #29790] don't optimise @a = ('a', sort @a) ! 448 449 @g = (3,2,1); @g = ('0', sort @g); 450 is "@g", "0 1 2 3", "un-inplace sort of global"; 451 @g = (3,2,1); @g = (sort(@g),'4'); 452 is "@g", "1 2 3 4", "un-inplace sort of global 2"; 453 454 @a = qw(b a c); @a = ('x', sort @a); 455 is "@a", "x a b c", "un-inplace sort of lexical"; 456 @a = qw(b a c); @a = ((sort @a), 'x'); 457 is "@a", "a b c x", "un-inplace sort of lexical 2"; 458 459 @g = (2,3,1); @g = ('0', sort { $b <=> $a } @g); 460 is "@g", "0 3 2 1", "un-inplace reversed sort of global"; 461 @g = (2,3,1); @g = ((sort { $b <=> $a } @g),'4'); 462 is "@g", "3 2 1 4", "un-inplace reversed sort of global 2"; 463 464 @g = (2,3,1); @g = ('0', sort { $a<$b?1:$a>$b?-1:0 } @g); 465 is "@g", "0 3 2 1", "un-inplace custom sort of global"; 466 @g = (2,3,1); @g = ((sort { $a<$b?1:$a>$b?-1:0 } @g),'4'); 467 is "@g", "3 2 1 4", "un-inplace custom sort of global 2"; 468 469 @a = qw(b c a); @a = ('x', sort mysort @a); 470 is "@a", "x c b a", "un-inplace sort with function of lexical"; 471 @a = qw(b c a); @a = ((sort mysort @a),'x'); 472 is "@a", "c b a x", "un-inplace sort with function of lexical 2"; 473 474 # RT#54758. Git 62b40d2474e7487e6909e1872b6bccdf812c6818 475 no warnings 'void'; 476 my @m; push @m, 0 for 1 .. 1024; $#m; @m = sort @m; 477 ::pass("in-place sorting segfault"); 478 479 # RT #39358 - array should be preserved during sort 480 481 { 482 my @aa = qw(b c a); 483 my @copy; 484 @aa = sort { @copy = @aa; $a cmp $b } @aa; 485 is "@aa", "a b c", "RT 39358 - aa"; 486 is "@copy", "b c a", "RT 39358 - copy"; 487 } 488 489 # RT #128340: in-place sort incorrectly preserves element lvalue identity 490 491 @a = (5, 4, 3); 492 my $r = \$a[2]; 493 @a = sort { $a <=> $b } @a; 494 $$r = "z"; 495 is ("@a", "3 4 5", "RT #128340"); 496 497} 498{ 499 @Tied_Array_EXTEND_Test::ISA= 'Tie::StdArray'; 500 my $extend_count; 501 sub Tied_Array_EXTEND_Test::EXTEND { 502 $extend_count= $_[1]; 503 return; 504 } 505 my @t; 506 tie @t, "Tied_Array_EXTEND_Test"; 507 is($extend_count, undef, "test that EXTEND has not been called prior to initialization"); 508 $t[0]=3; 509 $t[1]=1; 510 $t[2]=2; 511 is($extend_count, undef, "test that EXTEND has not been called during initialization"); 512 @t= sort @t; 513 is($extend_count, 3, "test that EXTEND was called with an argument of 3 by pp_sort()"); 514 is("@t","1 2 3","test that sorting the tied array worked even though EXTEND is a no-op"); 515} 516 517 518# Test optimisations of reversed sorts. As we now guarantee stability by 519# default, # optimisations which do not provide this are bogus. 520 521{ 522 package Oscalar; 523 use overload (qw("" stringify 0+ numify fallback 1)); 524 525 sub new { 526 bless [$_[1], $_[2]], $_[0]; 527 } 528 529 sub stringify { $_[0]->[0] } 530 531 sub numify { $_[0]->[1] } 532} 533 534sub generate { 535 my $count = 0; 536 map {new Oscalar $_, $count++} qw(A A A B B B C C C); 537} 538 539my @input = &generate; 540my @output = sort @input; 541is join(" ", map {0+$_} @output), "0 1 2 3 4 5 6 7 8", "Simple stable sort"; 542 543@input = &generate; 544@input = sort @input; 545is join(" ", map {0+$_} @input), "0 1 2 3 4 5 6 7 8", 546 "Simple stable in place sort"; 547 548# This won't be very interesting 549@input = &generate; 550@output = sort {$a <=> $b} @input; 551is "@output", "A A A B B B C C C", 'stable $a <=> $b sort'; 552 553@input = &generate; 554@output = sort {$a cmp $b} @input; 555is join(" ", map {0+$_} @output), "0 1 2 3 4 5 6 7 8", 'stable $a cmp $b sort'; 556 557@input = &generate; 558@input = sort {$a cmp $b} @input; 559is join(" ", map {0+$_} @input), "0 1 2 3 4 5 6 7 8", 560 'stable $a cmp $b in place sort'; 561 562@input = &generate; 563@output = sort {$b cmp $a} @input; 564is join(" ", map {0+$_} @output), "6 7 8 3 4 5 0 1 2", 'stable $b cmp $a sort'; 565 566@input = &generate; 567@input = sort {$b cmp $a} @input; 568is join(" ", map {0+$_} @input), "6 7 8 3 4 5 0 1 2", 569 'stable $b cmp $a in place sort'; 570 571@input = &generate; 572@output = reverse sort @input; 573is join(" ", map {0+$_} @output), "8 7 6 5 4 3 2 1 0", "Reversed stable sort"; 574 575@input = &generate; 576@input = reverse sort @input; 577is join(" ", map {0+$_} @input), "8 7 6 5 4 3 2 1 0", 578 "Reversed stable in place sort"; 579 580@input = &generate; 581my $output = reverse sort @input; 582is $output, "CCCBBBAAA", "Reversed stable sort in scalar context"; 583 584 585@input = &generate; 586@output = reverse sort {$a cmp $b} @input; 587is join(" ", map {0+$_} @output), "8 7 6 5 4 3 2 1 0", 588 'reversed stable $a cmp $b sort'; 589 590@input = &generate; 591@input = reverse sort {$a cmp $b} @input; 592is join(" ", map {0+$_} @input), "8 7 6 5 4 3 2 1 0", 593 'revesed stable $a cmp $b in place sort'; 594 595@input = &generate; 596$output = reverse sort {$a cmp $b} @input; 597is $output, "CCCBBBAAA", 'Reversed stable $a cmp $b sort in scalar context'; 598 599@input = &generate; 600@output = reverse sort {$b cmp $a} @input; 601is join(" ", map {0+$_} @output), "2 1 0 5 4 3 8 7 6", 602 'reversed stable $b cmp $a sort'; 603 604@input = &generate; 605@input = reverse sort {$b cmp $a} @input; 606is join(" ", map {0+$_} @input), "2 1 0 5 4 3 8 7 6", 607 'revesed stable $b cmp $a in place sort'; 608 609@input = &generate; 610$output = reverse sort {$b cmp $a} @input; 611is $output, "AAABBBCCC", 'Reversed stable $b cmp $a sort in scalar context'; 612 613sub stuff { 614 # Something complex enough to defeat any constant folding optimiser 615 $$ - $$; 616} 617 618@input = &generate; 619@output = reverse sort {stuff || $a cmp $b} @input; 620is join(" ", map {0+$_} @output), "8 7 6 5 4 3 2 1 0", 621 'reversed stable complex sort'; 622 623@input = &generate; 624@input = reverse sort {stuff || $a cmp $b} @input; 625is join(" ", map {0+$_} @input), "8 7 6 5 4 3 2 1 0", 626 'revesed stable complex in place sort'; 627 628@input = &generate; 629$output = reverse sort {stuff || $a cmp $b } @input; 630is $output, "CCCBBBAAA", 'Reversed stable complex sort in scalar context'; 631 632sub sortr { 633 reverse sort @_; 634} 635 636@output = sortr &generate; 637is join(" ", map {0+$_} @output), "8 7 6 5 4 3 2 1 0", 638 'reversed stable sort return list context'; 639$output = sortr &generate; 640is $output, "CCCBBBAAA", 641 'reversed stable sort return scalar context'; 642 643sub sortcmpr { 644 reverse sort {$a cmp $b} @_; 645} 646 647@output = sortcmpr &generate; 648is join(" ", map {0+$_} @output), "8 7 6 5 4 3 2 1 0", 649 'reversed stable $a cmp $b sort return list context'; 650$output = sortcmpr &generate; 651is $output, "CCCBBBAAA", 652 'reversed stable $a cmp $b sort return scalar context'; 653 654sub sortcmprba { 655 reverse sort {$b cmp $a} @_; 656} 657 658@output = sortcmprba &generate; 659is join(" ", map {0+$_} @output), "2 1 0 5 4 3 8 7 6", 660 'reversed stable $b cmp $a sort return list context'; 661$output = sortcmprba &generate; 662is $output, "AAABBBCCC", 663'reversed stable $b cmp $a sort return scalar context'; 664 665sub sortcmprq { 666 reverse sort {stuff || $a cmp $b} @_; 667} 668 669@output = sortcmpr &generate; 670is join(" ", map {0+$_} @output), "8 7 6 5 4 3 2 1 0", 671 'reversed stable complex sort return list context'; 672$output = sortcmpr &generate; 673is $output, "CCCBBBAAA", 674 'reversed stable complex sort return scalar context'; 675 676# And now with numbers 677 678sub generate1 { 679 my $count = 'A'; 680 map {new Oscalar $count++, $_} 0, 0, 0, 1, 1, 1, 2, 2, 2; 681} 682 683# This won't be very interesting 684@input = &generate1; 685@output = sort {$a cmp $b} @input; 686is "@output", "A B C D E F G H I", 'stable $a cmp $b sort'; 687 688@input = &generate1; 689@output = sort {$a <=> $b} @input; 690is "@output", "A B C D E F G H I", 'stable $a <=> $b sort'; 691 692@input = &generate1; 693@input = sort {$a <=> $b} @input; 694is "@input", "A B C D E F G H I", 'stable $a <=> $b in place sort'; 695 696@input = &generate1; 697@output = sort {$b <=> $a} @input; 698is "@output", "G H I D E F A B C", 'stable $b <=> $a sort'; 699 700@input = &generate1; 701@input = sort {$b <=> $a} @input; 702is "@input", "G H I D E F A B C", 'stable $b <=> $a in place sort'; 703 704# test that optimized {$b cmp $a} and {$b <=> $a} remain stable 705# (new in 5.9) without overloading 706{ no warnings; 707@b = sort { $b <=> $a } @input = qw/5first 6first 5second 6second/; 708is "@b" , "6first 6second 5first 5second", "optimized {$b <=> $a} without overloading" ; 709@input = sort {$b <=> $a} @input; 710is "@input" , "6first 6second 5first 5second","inline optimized {$b <=> $a} without overloading" ; 711}; 712 713# These two are actually doing string cmp on 0 1 and 2 714@input = &generate1; 715@output = reverse sort @input; 716is "@output", "I H G F E D C B A", "Reversed stable sort"; 717 718@input = &generate1; 719@input = reverse sort @input; 720is "@input", "I H G F E D C B A", "Reversed stable in place sort"; 721 722@input = &generate1; 723$output = reverse sort @input; 724is $output, "IHGFEDCBA", "Reversed stable sort in scalar context"; 725 726@input = &generate1; 727@output = reverse sort {$a <=> $b} @input; 728is "@output", "I H G F E D C B A", 'reversed stable $a <=> $b sort'; 729 730@input = &generate1; 731@input = reverse sort {$a <=> $b} @input; 732is "@input", "I H G F E D C B A", 'revesed stable $a <=> $b in place sort'; 733 734@input = &generate1; 735$output = reverse sort {$a <=> $b} @input; 736is $output, "IHGFEDCBA", 'reversed stable $a <=> $b sort in scalar context'; 737 738@input = &generate1; 739@output = reverse sort {$b <=> $a} @input; 740is "@output", "C B A F E D I H G", 'reversed stable $b <=> $a sort'; 741 742@input = &generate1; 743@input = reverse sort {$b <=> $a} @input; 744is "@input", "C B A F E D I H G", 'revesed stable $b <=> $a in place sort'; 745 746@input = &generate1; 747$output = reverse sort {$b <=> $a} @input; 748is $output, "CBAFEDIHG", 'reversed stable $b <=> $a sort in scalar context'; 749 750@input = &generate1; 751@output = reverse sort {stuff || $a <=> $b} @input; 752is "@output", "I H G F E D C B A", 'reversed stable complex sort'; 753 754@input = &generate1; 755@input = reverse sort {stuff || $a <=> $b} @input; 756is "@input", "I H G F E D C B A", 'revesed stable complex in place sort'; 757 758@input = &generate1; 759$output = reverse sort {stuff || $a <=> $b} @input; 760is $output, "IHGFEDCBA", 'reversed stable complex sort in scalar context'; 761 762sub sortnumr { 763 reverse sort {$a <=> $b} @_; 764} 765 766@output = sortnumr &generate1; 767is "@output", "I H G F E D C B A", 768 'reversed stable $a <=> $b sort return list context'; 769$output = sortnumr &generate1; 770is $output, "IHGFEDCBA", 'reversed stable $a <=> $b sort return scalar context'; 771 772sub sortnumrba { 773 reverse sort {$b <=> $a} @_; 774} 775 776@output = sortnumrba &generate1; 777is "@output", "C B A F E D I H G", 778 'reversed stable $b <=> $a sort return list context'; 779$output = sortnumrba &generate1; 780is $output, "CBAFEDIHG", 'reversed stable $b <=> $a sort return scalar context'; 781 782sub sortnumrq { 783 reverse sort {stuff || $a <=> $b} @_; 784} 785 786@output = sortnumrq &generate1; 787is "@output", "I H G F E D C B A", 788 'reversed stable complex sort return list context'; 789$output = sortnumrq &generate1; 790is $output, "IHGFEDCBA", 'reversed stable complex sort return scalar context'; 791 792@output = reverse (sort(qw(C A B)), 0); 793is "@output", "0 C B A", 'reversed sort with trailing argument'; 794 795@output = reverse (0, sort(qw(C A B))); 796is "@output", "C B A 0", 'reversed sort with leading argument'; 797 798eval { @output = sort {goto sub {}} 1,2; }; 799$fail_msg = q(Can't goto subroutine outside a subroutine); 800cmp_ok(substr($@,0,length($fail_msg)),'eq',$fail_msg,'goto subr outside subr'); 801 802 803 804sub goto_sub {goto sub{}} 805eval { @output = sort goto_sub 1,2; }; 806$fail_msg = q(Can't goto subroutine from a sort sub); 807cmp_ok(substr($@,0,length($fail_msg)),'eq',$fail_msg,'goto subr from a sort sub'); 808 809 810 811eval { @output = sort {goto label} 1,2; }; 812$fail_msg = q(Can't "goto" out of a pseudo block); 813cmp_ok(substr($@,0,length($fail_msg)),'eq',$fail_msg,'goto out of a pseudo block 1'); 814 815 816 817sub goto_label {goto label} 818label: eval { @output = sort goto_label 1,2; }; 819$fail_msg = q(Can't "goto" out of a pseudo block); 820cmp_ok(substr($@,0,length($fail_msg)),'eq',$fail_msg,'goto out of a pseudo block 2'); 821 822 823 824sub self_immolate {undef &self_immolate; $a<=>$b} 825eval { @output = sort self_immolate 1,2,3 }; 826$fail_msg = q(Can't undef active subroutine); 827cmp_ok(substr($@,0,length($fail_msg)),'eq',$fail_msg,'undef active subr'); 828 829 830for(1,2) # We run this twice, to make sure sort does not lower the ref 831{ # count. See bug 71076. 832 my $failed = 0; 833 834 sub rec { 835 my $n = shift; 836 if (!defined($n)) { # No arg means we're being called by sort() 837 return 1; 838 } 839 if ($n<5) { rec($n+1); } 840 else { () = sort rec 1,2; } 841 842 $failed = 1 if !defined $n; 843 } 844 845 rec(1); 846 ok(!$failed, "sort from active sub"); 847} 848 849# $a and $b are set in the package the sort() is called from, 850# *not* the package the sort sub is in. This is longstanding 851# de facto behaviour that shouldn't be broken. 852my $answer = "good"; 853() = sort OtherPack::foo 1,2,3,4; 854 855{ 856 package OtherPack; 857 no warnings 'once'; 858 sub foo { 859 $answer = "something was unexpectedly defined or undefined" if 860 defined($a) || defined($b) || !defined($main::a) || !defined($main::b); 861 $main::a <=> $main::b; 862 } 863} 864 865cmp_ok($answer,'eq','good','sort subr called from other package'); 866 867 868# Bug 36430 - sort called in package2 while a 869# sort in package1 is active should set $package2::a/b. 870{ 871 my $answer = "good"; 872 my @list = sort { A::min(@$a) <=> A::min(@$b) } 873 [3, 1, 5], [2, 4], [0]; 874 875 cmp_ok($answer,'eq','good','bug 36430'); 876 877 package A; 878 sub min { 879 my @list = sort { 880 $answer = '$a and/or $b are not defined ' if !defined($a) || !defined($b); 881 $a <=> $b; 882 } @_; 883 $list[0]; 884 } 885} 886 887 888 889# I commented out this TODO test because messing with FREEd scalars on the 890# stack can have all sorts of strange side-effects, not made safe by eval 891# - DAPM. 892# 893#{ 894# local $TODO = "sort should make sure elements are not freed in the sort block"; 895# eval { @nomodify_x=(1..8); 896# our @copy = sort { undef @nomodify_x; 1 } (@nomodify_x, 3); }; 897# is($@, ""); 898#} 899 900 901# Sorting shouldn't increase the refcount of a sub 902{ 903 sub sportello {(1+$a) <=> (1+$b)} 904 # + 1 to account for prototype-defeating &... calling convention 905 my $refcnt = &Internals::SvREFCNT(\&sportello) + 1; 906 @output = sort sportello 3,7,9; 907 908 { 909 package Doc; 910 ::refcount_is \&::sportello, $refcnt, "sort sub refcnt"; 911 $fail_msg = q(Modification of a read-only value attempted); 912 # Sorting a read-only array in-place shouldn't be allowed 913 my @readonly = (1..10); 914 Internals::SvREADONLY(@readonly, 1); 915 eval { @readonly = sort @readonly; }; 916 ::cmp_ok(substr($@,0,length($fail_msg)),'eq',$fail_msg,'in-place sort of read-only array'); 917 } 918} 919 920 921# Using return() should be okay even in a deeper context 922@b = sort {while (1) {return ($a <=> $b)} } 1..10; 923is("@b", "1 2 3 4 5 6 7 8 9 10", "return within loop"); 924 925# Using return() should be okay even if there are other items 926# on the stack at the time. 927@b = sort {$_ = ($a<=>$b) + do{return $b<=> $a}} 1..10; 928is("@b", "10 9 8 7 6 5 4 3 2 1", "return with SVs on stack"); 929 930# As above, but with a sort sub rather than a sort block. 931sub ret_with_stacked { $_ = ($a<=>$b) + do {return $b <=> $a} } 932@b = sort ret_with_stacked 1..10; 933is("@b", "10 9 8 7 6 5 4 3 2 1", "return with SVs on stack"); 934 935# Comparison code should be able to give result in non-integer representation. 936sub cmp_as_string($$) { $_[0] < $_[1] ? "-1" : $_[0] == $_[1] ? "0" : "+1" } 937@b = sort { cmp_as_string($a, $b) } (1,5,4,7,3,2,3); 938is("@b", "1 2 3 3 4 5 7", "comparison result as string"); 939@b = sort cmp_as_string (1,5,4,7,3,2,3); 940is("@b", "1 2 3 3 4 5 7", "comparison result as string"); 941 942# RT #34604: sort didn't honour overloading if the overloaded elements 943# were retrieved via tie 944 945{ 946 package RT34604; 947 948 sub TIEHASH { bless { 949 p => bless({ val => 2 }), 950 q => bless({ val => 1 }), 951 } 952 } 953 sub FETCH { $_[0]{$_[1] } } 954 955 my $cc = 0; 956 sub compare { $cc++; $_[0]{val} cmp $_[1]{val} } 957 my $cs = 0; 958 sub str { $cs++; $_[0]{val} } 959 960 use overload 'cmp' => \&compare, '""' => \&str; 961 962 package main; 963 964 tie my %h, 'RT34604'; 965 my @sorted = sort @h{qw(p q)}; 966 is($cc, 1, 'overload compare called once'); 967 is("@sorted","1 2", 'overload sort result'); 968 is($cs, 2, 'overload string called twice'); 969} 970 971fresh_perl_is('sub w ($$) {my ($l, $r) = @_; my $v = \@_; undef @_; $l <=> $r}; print join q{ }, sort w 3, 1, 2, 0', 972 '0 1 2 3', 973 {stderr => 1, switches => ['-w']}, 974 'RT #72334'); 975 976fresh_perl_is('sub w ($$) {my ($l, $r) = @_; my $v = \@_; undef @_; @_ = 0..2; $l <=> $r}; print join q{ }, sort w 3, 1, 2, 0', 977 '0 1 2 3', 978 {stderr => 1, switches => ['-w']}, 979 'RT #72334'); 980 981{ 982 my $count = 0; 983 { 984 package Counter; 985 986 sub new { 987 ++$count; 988 bless []; 989 } 990 991 sub DESTROY { 992 --$count; 993 } 994 } 995 996 sub sorter ($$) { 997 my ($l, $r) = @_; 998 my $q = \@_; 999 $l <=> $r; 1000 } 1001 1002 is($count, 0, 'None before we start'); 1003 my @a = map { Counter->new() } 0..1; 1004 is($count, 2, '2 here'); 1005 1006 my @b = sort sorter @a; 1007 1008 is(scalar @b, 2); 1009 cmp_ok($b[0], '<', $b[1], 'sorted!'); 1010 1011 is($count, 2, 'still the same 2 here'); 1012 1013 @a = (); @b = (); 1014 1015 is($count, 0, 'all gone'); 1016} 1017 1018# [perl #77930] The context stack may be reallocated during a sort, as a 1019# result of deeply-nested (or not-so-deeply-nested) calls 1020# from a custom sort subroutine. 1021fresh_perl_is 1022 ' 1023 $sub = sub { 1024 local $count = $count+1; 1025 ()->$sub if $count < 1000; 1026 $a cmp $b 1027 }; 1028 () = sort $sub qw<a b c d e f g>; 1029 print "ok" 1030 ', 1031 'ok', 1032 {}, 1033 '[perl #77930] cx_stack reallocation during sort' 1034; 1035 1036# [perl #76026] 1037# Match vars should not leak from one sort sub call to the next 1038{ 1039 my $output = ''; 1040 sub soarter { 1041 $output .= $1; 1042 "Leakage" =~ /(.*)/; 1043 1 1044 } 1045 sub soarterdd($$) { 1046 $output .= $1; 1047 "Leakage" =~ /(.*)/; 1048 1 1049 } 1050 1051 "Win" =~ /(.*)/; 1052 my @b = sort soarter 0..2; 1053 1054 like $output, qr/^(?:Win)+\z/, 1055 "Match vars do not leak from one plain sort sub to the next"; 1056 1057 $output = ''; 1058 1059 "Win" =~ /(.*)/; 1060 @b = sort soarterdd 0..2; 1061 1062 like $output, qr/^(?:Win)+\z/, 1063 'Match vars do not leak from one $$ sort sub to the next'; 1064} 1065 1066# [perl #30661] autoloading 1067AUTOLOAD { $b <=> $a } 1068sub stubbedsub; 1069is join("", sort stubbedsub split//, '04381091'), '98431100', 1070 'stubborn AUTOLOAD'; 1071is join("", sort hopefullynonexistent split//, '04381091'), '98431100', 1072 'AUTOLOAD without stub'; 1073my $stubref = \&givemeastub; 1074is join("", sort $stubref split//, '04381091'), '98431100', 1075 'AUTOLOAD with stubref'; 1076 1077 1078# this happened while the padrange op was being added. Sort blocks 1079# are executed in void context, and the padrange op was skipping pushing 1080# the item in void cx. The net result was that the return value was 1081# whatever was on the stack last. 1082 1083{ 1084 my @a = sort { 1085 my $r = $a <=> $b; 1086 if ($r) { 1087 undef; # this got returned by mistake 1088 return $r 1089 } 1090 return 0; 1091 } 5,1,3,6,0; 1092 is "@a", "0 1 3 5 6", "padrange and void context"; 1093} 1094 1095# Fatal warnings an sort sub returning a non-number 1096# We need two evals, because the panic used to happen on scope exit. 1097eval { eval { use warnings FATAL => 'all'; () = sort { undef } 1,2 } }; 1098is $@, "", 1099 'no panic/crash with fatal warnings when sort sub returns undef'; 1100eval { eval { use warnings FATAL => 'all'; () = sort { "no thin" } 1,2 } }; 1101is $@, "", 1102 'no panic/crash with fatal warnings when sort sub returns string'; 1103sub notdef($$) { undef } 1104eval { eval { use warnings FATAL => 'all'; () = sort notdef 1,2 } }; 1105is $@, "", 1106 'no panic/crash with fatal warnings when sort sub($$) returns undef'; 1107sub yarn($$) { "no thinking aloud" } 1108eval { eval { use warnings FATAL => 'all'; () = sort yarn 1,2 } }; 1109is $@, "", 1110 'no panic/crash with fatal warnings when sort sub($$) returns string'; 1111 1112$#a = -1; 1113() = [sort { $a = 10; $b = 10; 0 } $#a, $#a]; 1114is $#a, 10, 'sort block modifying $a and $b'; 1115 1116() = sort { 1117 is \$a, \$a, '[perl #78194] op return values passed to sort'; 0 1118} "${\''}", "${\''}"; 1119 1120package deletions { 1121 @_=sort { delete $deletions::{a}; delete $deletions::{b}; 3 } 1..3; 1122} 1123pass "no crash when sort block deletes *a and *b"; 1124 1125# make sure return args are always evaluated in scalar context 1126 1127{ 1128 package Ret; 1129 no warnings 'void'; 1130 sub f0 { } 1131 sub f1 { $b <=> $a, $a <=> $b } 1132 sub f2 { return ($b <=> $a, $a <=> $b) } 1133 sub f3 { for ($b <=> $a) { return ($b <=> $a, $a <=> $b) } } 1134 1135 { 1136 no warnings 'uninitialized'; 1137 ::is (join('-', sort { () } 3,1,2,4), '3-1-2-4', "Ret: null blk"); 1138 } 1139 ::is (join('-', sort { $b <=> $a, $a <=> $b } 3,1,2,4), '1-2-3-4', "Ret: blk"); 1140 ::is (join('-', sort { for($b <=> $a) { return ($b <=> $a, $a <=> $b) } } 1141 3,1,2,4), '1-2-3-4', "Ret: blk ret"); 1142 { 1143 no warnings 'uninitialized'; 1144 ::is (join('-', sort f0 3,1,2,4), '3-1-2-4', "Ret: f0"); 1145 } 1146 ::is (join('-', sort f1 3,1,2,4), '1-2-3-4', "Ret: f1"); 1147 ::is (join('-', sort f2 3,1,2,4), '1-2-3-4', "Ret: f2"); 1148 ::is (join('-', sort f3 3,1,2,4), '1-2-3-4', "Ret: f3"); 1149} 1150 1151{ 1152 @a = sort{ *a=0; 1} 0..1; 1153 pass "No crash when GP deleted out from under us [perl 124097]"; 1154 1155 no warnings 'redefine'; 1156 # some alternative non-solutions localized modifications to *a and *b 1157 sub a { 0 }; 1158 @a = sort { *a = sub { 1 }; $a <=> $b } 0 .. 1; 1159 ok(a(), "*a wasn't localized inadvertantly"); 1160} 1161 1162SKIP: 1163{ 1164 eval { require Config; 1 } 1165 or skip "Cannot load Config", 1; 1166 $Config::Config{ivsize} == 8 1167 or skip "this test can only fail with 64-bit integers", 1; 1168 # sort's built-in numeric comparison wasn't careful enough in a world 1169 # of integers with more significant digits than NVs 1170 my @in = ( "0", "20000000000000001", "20000000000000000" ); 1171 my @out = sort { $a <=> $b } @in; 1172 is($out[1], "20000000000000000", "check sort order"); 1173} 1174 1175# [perl #92264] refcounting of GvSV slot of *a and *b 1176{ 1177 my $act; 1178 package ReportDestruction { 1179 sub new { bless({ p => $_[1] }, $_[0]) } 1180 sub DESTROY { $act .= $_[0]->{p}; } 1181 } 1182 $act = ""; 1183 my $filla = \(ReportDestruction->new("[filla]")); 1184 () = sort { my $r = $a cmp $b; $act .= "0"; *a = \$$filla; $act .= "1"; $r } 1185 ReportDestruction->new("[sorta]"), "foo"; 1186 $act .= "2"; 1187 $filla = undef; 1188 is $act, "01[sorta]2[filla]"; 1189 $act = ""; 1190 my $fillb = \(ReportDestruction->new("[fillb]")); 1191 () = sort { my $r = $a cmp $b; $act .= "0"; *b = \$$fillb; $act .= "1"; $r } 1192 "foo", ReportDestruction->new("[sortb]"); 1193 $act .= "2"; 1194 $fillb = undef; 1195 is $act, "01[sortb]2[fillb]"; 1196} 1197 1198# GH #18081 1199# sub call via return in sort block was called in void rather than scalar 1200# context 1201 1202{ 1203 sub sort18081 { $a + 1 <=> $b + 1 } 1204 my @a = sort { return &sort18081 } 6,1,2; 1205 is "@a", "1 2 6", "GH #18081"; 1206} 1207 1208# make a physically empty sort a compile-time error 1209# Note that it was a wierd compile time error until 1210# [perl #90030], v5.15.6-390-ga46b39a853 1211# which made it a NOOP. 1212# Then in Jan 2022 it was made an error again, to allow future 1213# use of attribuute-like syntax, e.g. 1214# @a = $cond ? sort :num 1,2,3 : ....; 1215# See http://nntp.perl.org/group/perl.perl5.porters/262425 1216 1217{ 1218 my @empty = (); 1219 my @sorted = sort @empty; 1220 is "@sorted", "", 'sort @empty'; 1221 1222 eval 'my @s = sort'; 1223 like($@, qr/Not enough arguments for sort/, 'empty sort not allowed'); 1224 1225 eval '{my @s = sort}'; 1226 like($@, qr/Not enough arguments for sort/, 'empty {sort} not allowed'); 1227 1228 eval 'my @s = sort; 1'; 1229 like($@, qr/Not enough arguments for sort/, 'empty sort; not allowed'); 1230 1231 eval 'my @s = (sort); 1'; 1232 like($@, qr/Not enough arguments for sort/, 'empty (sort); not allowed'); 1233} 1234