EXTEND changes visible size of file and array. [rt.cpan.org #39196]

[toddr]

Migrated from rt.cpan.org#39196 (status was 'new')

Requestors:

• IKEGAMI@cpan.org

From ikegami@cpan.org on 2008-09-12 00:19:06
:

Bug present in at least Tie::File 0.97 and 0.97_02.

EXTEND is used to expand the internal buffer.
STORESIZE is used to actually change the visible size of the array.
Tie::File incorrectly treats EXTEND as STORESIZE.

When sorting in place (@a = sort @a) on a magical array (such as one
tied to Tie::File), sort EXTENDs the array to scalar(@a)+1 elements.

This is meant to extend the internal storage size, but it has visible
effects when the array is tied to Tie::File. The reported number of
elements is different than it should be, and a blank line is appended to
the file (in the sort example).

See http://www.perlmonks.org/?node_id=710580 for runnable code and some
extra details.

[toddr]

I'm transferring this issue to https://github.com/Perl/perl5 since it is issue with a module in dist.

[jkeenan]

The bug is still present in 5.30.1. It can be demonstrated with the following program:

$ cat perlmonks-710580-tie-file.pl 
#!/usr/bin/env perl
use 5.14.0;
use warnings;
use Data::Dumper; $Data::Dumper::Indent=1;
use Carp;
use Tie::File;

my $g = 'tiefile';
unlink $g if -f $g;

tie my @tied_array, 'Tie::File', $g  or die "Could not tie to $g: $!";

push(@tied_array, $_) for (1..3);

print "\@tied_array has " . scalar @tied_array . " elements before sorting\n";
@tied_array = sort {uc($a) cmp uc($b)} @tied_array;

print "\@tied_array has " . scalar @tied_array . " elements after sorting\n";
say Dumper (\@tied_array);
untie @tied_array;

Results:

$ perl perlmonks-710580-tie-file.pl 
@tied_array has 3 elements before sorting
@tied_array has 4 elements after sorting
$VAR1 = [
  '1',
  '2',
  '3',
  ''
];

See perlmonks 710580 for good analysis by @ikegami.

Thank you very much.
Jim Keenan

[demerphq]

On Thu, 30 Jan 2020, 05:46 James E Keenan, ***@***.***> wrote: The bug is still present in 5.30.1. It can be demonstrated with the following program: $ cat perlmonks-710580-tie-file.pl #!/usr/bin/env perl use 5.14.0; use warnings; use Data::Dumper; $Data::Dumper::Indent=1; use Carp; use Tie::File; my $g = 'tiefile'; unlink $g if -f $g; tie my @tied_array, 'Tie::File', $g or die "Could not tie to $g: $!"; ***@***.***_array, $_) for (1..3); print ***@***.***_array has " . scalar @tied_array . " elements before sorting\n"; @tied_array = sort {uc($a) cmp uc($b)} @tied_array; print ***@***.***_array has " . scalar @tied_array . " elements after sorting\n"; say Dumper ***@***.***_array); untie @tied_array; Results: $ perl perlmonks-710580-tie-file.pl @tied_array has 3 elements before sorting @tied_array has 4 elements after sorting $VAR1 = [ '1', '2', '3', '' ]; See perlmonks 710580 <http://www.perlmonks.org/?node_id=710580> for good analysis by @ikegami <https://github.com/ikegami>

Imo this is a bug in perl not in Tie::File. I can imagine why the sort code might want to extend the array, but the fact that it breaks tie modules shows it's not correct to do so. Yves

…

[ikegami]

It doesn't break tie modules in general. The linked post above shows that the bug is to specific to Tie::File by demonstrating that Tie::StdArray is not affected. (I didn't analyze the problem de novo since I'm on my phone.) On Wed., Jan. 29, 2020, 8:26 p.m. Yves Orton, <notifications@github.com> wrote:

…

On Thu, 30 Jan 2020, 05:46 James E Keenan, ***@***.***> wrote: > The bug is still present in 5.30.1. It can be demonstrated with the > following program: > > $ cat perlmonks-710580-tie-file.pl > #!/usr/bin/env perl > use 5.14.0; > use warnings; > use Data::Dumper; $Data::Dumper::Indent=1; > use Carp; > use Tie::File; > > my $g = 'tiefile'; > unlink $g if -f $g; > > tie my @tied_array, 'Tie::File', $g or die "Could not tie to $g: $!"; > > ***@***.***_array, $_) for (1..3); > > print ***@***.***_array has " . scalar @tied_array . " elements before sorting\n"; > @tied_array = sort {uc($a) cmp uc($b)} @tied_array; > > print ***@***.***_array has " . scalar @tied_array . " elements after sorting\n"; > say Dumper ***@***.***_array); > untie @tied_array; > > Results: > > $ perl perlmonks-710580-tie-file.pl > @tied_array has 3 elements before sorting > @tied_array has 4 elements after sorting > $VAR1 = [ > '1', > '2', > '3', > '' > ]; > > See perlmonks 710580 <http://www.perlmonks.org/?node_id=710580> for good > analysis by @ikegami <https://github.com/ikegami> > Imo this is a bug in perl not in Tie::File. I can imagine why the sort code might want to extend the array, but the fact that it breaks tie modules shows it's not correct to do so. Yves > — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#17496?email_source=notifications&email_token=AAFK2ZJ7A263WJSHBA3GLLTRAIUFRA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJL27Y#issuecomment-580042111>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAFK2ZI4AVXSFOFBP4DJQLDRAIUFRANCNFSM4KL355LA> .

[demerphq]

I don't think that really settles this. EXTEND implies in memory semantics where the size of the allocated buffer differs from what is visible to the user of the array. A tie to some kind of external store, like Tie::File, cannot support this distinction. Whatever is allocated is necessarily "visible". So arguably calling EXTEND as part of sort() is a bug. I imagine it is done to provide oinline space for swaps (but I havent checked), but this means it expects to be able to store into an element that has not been properly made part of the array which seems pretty dodgy to me. If after the sort it "de-extended" the array then it might be ok, but then Tie::File wouldn't be broken either. So imo this is a perl bug as we are subtly assuming the array implementation is capable of over allocating invisible elements of the array which are usable but not visible which imo is not possible with any "hard storage" type Tie. Yves

…

On Thu, 30 Jan 2020, 11:19 Eric Brine, ***@***.***> wrote: It doesn't break tie modules in general. The linked post above shows that the bug is to specific to Tie::File by demonstrating that Tie::StdArray is not affected. (I didn't analyze the problem de novo since I'm on my phone.) On Wed., Jan. 29, 2020, 8:26 p.m. Yves Orton, ***@***.***> wrote: > On Thu, 30 Jan 2020, 05:46 James E Keenan, ***@***.***> > wrote: > > > The bug is still present in 5.30.1. It can be demonstrated with the > > following program: > > > > $ cat perlmonks-710580-tie-file.pl > > #!/usr/bin/env perl > > use 5.14.0; > > use warnings; > > use Data::Dumper; $Data::Dumper::Indent=1; > > use Carp; > > use Tie::File; > > > > my $g = 'tiefile'; > > unlink $g if -f $g; > > > > tie my @tied_array, 'Tie::File', $g or die "Could not tie to $g: $!"; > > > > ***@***.***_array, $_) for (1..3); > > > > print ***@***.***_array has " . scalar @tied_array . " elements before > sorting\n"; > > @tied_array = sort {uc($a) cmp uc($b)} @tied_array; > > > > print ***@***.***_array has " . scalar @tied_array . " elements after > sorting\n"; > > say Dumper ***@***.***_array); > > untie @tied_array; > > > > Results: > > > > $ perl perlmonks-710580-tie-file.pl > > @tied_array has 3 elements before sorting > > @tied_array has 4 elements after sorting > > $VAR1 = [ > > '1', > > '2', > > '3', > > '' > > ]; > > > > See perlmonks 710580 <http://www.perlmonks.org/?node_id=710580> for good > > analysis by @ikegami <https://github.com/ikegami> > > > > Imo this is a bug in perl not in Tie::File. > > I can imagine why the sort code might want to extend the array, but the > fact that it breaks tie modules shows it's not correct to do so. > > Yves > > > > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > < #17496?email_source=notifications&email_token=AAFK2ZJ7A263WJSHBA3GLLTRAIUFRA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJL27Y#issuecomment-580042111 >, > or unsubscribe > < https://github.com/notifications/unsubscribe-auth/AAFK2ZI4AVXSFOFBP4DJQLDRAIUFRANCNFSM4KL355LA > > . > — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#17496?email_source=notifications&email_token=AAAZ5R5YDLT4QONZULIQMMLRAJBNBA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJRTLI#issuecomment-580065709>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAAZ5RZPNCF3DGQ7776QHHDRAJBNBANCNFSM4KL355LA> .

[demerphq]

To add to this, imo any tied array should function perfectly fine if EXTEND is a noop. EXTEND is essentially an optimization that says "preallocate space efficiently in a chunk so that later I can efficiently allocate in piecemeal fashion without a penalty each time". If sort breaks or accesses an element outside of the actually allocated space because it has called EXTEND then it is making unwarranted assumptions about the internal implementation of the array. Yves

…

On Thu, 30 Jan 2020, 11:33 demerphq, ***@***.***> wrote: I don't think that really settles this. EXTEND implies in memory semantics where the size of the allocated buffer differs from what is visible to the user of the array. A tie to some kind of external store, like Tie::File, cannot support this distinction. Whatever is allocated is necessarily "visible". So arguably calling EXTEND as part of sort() is a bug. I imagine it is done to provide oinline space for swaps (but I havent checked), but this means it expects to be able to store into an element that has not been properly made part of the array which seems pretty dodgy to me. If after the sort it "de-extended" the array then it might be ok, but then Tie::File wouldn't be broken either. So imo this is a perl bug as we are subtly assuming the array implementation is capable of over allocating invisible elements of the array which are usable but not visible which imo is not possible with any "hard storage" type Tie. Yves On Thu, 30 Jan 2020, 11:19 Eric Brine, ***@***.***> wrote: > It doesn't break tie modules in general. The linked post above shows that > the bug is to specific to Tie::File by demonstrating that Tie::StdArray is > not affected. > > (I didn't analyze the problem de novo since I'm on my phone.) > > On Wed., Jan. 29, 2020, 8:26 p.m. Yves Orton, ***@***.***> > wrote: > > > On Thu, 30 Jan 2020, 05:46 James E Keenan, ***@***.***> > > wrote: > > > > > The bug is still present in 5.30.1. It can be demonstrated with the > > > following program: > > > > > > $ cat perlmonks-710580-tie-file.pl > > > #!/usr/bin/env perl > > > use 5.14.0; > > > use warnings; > > > use Data::Dumper; $Data::Dumper::Indent=1; > > > use Carp; > > > use Tie::File; > > > > > > my $g = 'tiefile'; > > > unlink $g if -f $g; > > > > > > tie my @tied_array, 'Tie::File', $g or die "Could not tie to $g: $!"; > > > > > > ***@***.***_array, $_) for (1..3); > > > > > > print ***@***.***_array has " . scalar @tied_array . " elements before > > sorting\n"; > > > @tied_array = sort {uc($a) cmp uc($b)} @tied_array; > > > > > > print ***@***.***_array has " . scalar @tied_array . " elements after > > sorting\n"; > > > say Dumper ***@***.***_array); > > > untie @tied_array; > > > > > > Results: > > > > > > $ perl perlmonks-710580-tie-file.pl > > > @tied_array has 3 elements before sorting > > > @tied_array has 4 elements after sorting > > > $VAR1 = [ > > > '1', > > > '2', > > > '3', > > > '' > > > ]; > > > > > > See perlmonks 710580 <http://www.perlmonks.org/?node_id=710580> for > good > > > analysis by @ikegami <https://github.com/ikegami> > > > > > > > Imo this is a bug in perl not in Tie::File. > > > > I can imagine why the sort code might want to extend the array, but the > > fact that it breaks tie modules shows it's not correct to do so. > > > > Yves > > > > > > > > > — > > You are receiving this because you were mentioned. > > Reply to this email directly, view it on GitHub > > < > #17496?email_source=notifications&email_token=AAFK2ZJ7A263WJSHBA3GLLTRAIUFRA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJL27Y#issuecomment-580042111 > >, > > or unsubscribe > > < > https://github.com/notifications/unsubscribe-auth/AAFK2ZI4AVXSFOFBP4DJQLDRAIUFRANCNFSM4KL355LA > > > > . > > > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#17496?email_source=notifications&email_token=AAAZ5R5YDLT4QONZULIQMMLRAJBNBA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJRTLI#issuecomment-580065709>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AAAZ5RZPNCF3DGQ7776QHHDRAJBNBANCNFSM4KL355LA> > . >

[demerphq]

So after instrumenting a tied array I slightly modify my position. Both Perl and the tied module are buggy. 😀 I claim both are buggy because there doesnt seem to be any reason to do the EXTEND at all, *and* the perltie sample code for EXTEND incorrectly conflates it with STORESIZE when it shouldn't. Tie::File is buggy presumably because it followed that broken example. Yves

…

On Thu, 30 Jan 2020, 11:38 demerphq, ***@***.***> wrote: To add to this, imo any tied array should function perfectly fine if EXTEND is a noop. EXTEND is essentially an optimization that says "preallocate space efficiently in a chunk so that later I can efficiently allocate in piecemeal fashion without a penalty each time". If sort breaks or accesses an element outside of the actually allocated space because it has called EXTEND then it is making unwarranted assumptions about the internal implementation of the array. Yves On Thu, 30 Jan 2020, 11:33 demerphq, ***@***.***> wrote: > I don't think that really settles this. > > EXTEND implies in memory semantics where the size of the allocated buffer > differs from what is visible to the user of the array. > > A tie to some kind of external store, like Tie::File, cannot support this > distinction. Whatever is allocated is necessarily "visible". > > So arguably calling EXTEND as part of sort() is a bug. I imagine it is > done to provide oinline space for swaps (but I havent checked), but this > means it expects to be able to store into an element that has not been > properly made part of the array which seems pretty dodgy to me. If after > the sort it "de-extended" the array then it might be ok, but then Tie::File > wouldn't be broken either. > > So imo this is a perl bug as we are subtly assuming the array > implementation is capable of over allocating invisible elements of the > array which are usable but not visible which imo is not possible with any > "hard storage" type Tie. > > Yves > > On Thu, 30 Jan 2020, 11:19 Eric Brine, ***@***.***> wrote: > >> It doesn't break tie modules in general. The linked post above shows that >> the bug is to specific to Tie::File by demonstrating that Tie::StdArray >> is >> not affected. >> >> (I didn't analyze the problem de novo since I'm on my phone.) >> >> On Wed., Jan. 29, 2020, 8:26 p.m. Yves Orton, ***@***.***> >> wrote: >> >> > On Thu, 30 Jan 2020, 05:46 James E Keenan, ***@***.***> >> > wrote: >> > >> > > The bug is still present in 5.30.1. It can be demonstrated with the >> > > following program: >> > > >> > > $ cat perlmonks-710580-tie-file.pl >> > > #!/usr/bin/env perl >> > > use 5.14.0; >> > > use warnings; >> > > use Data::Dumper; $Data::Dumper::Indent=1; >> > > use Carp; >> > > use Tie::File; >> > > >> > > my $g = 'tiefile'; >> > > unlink $g if -f $g; >> > > >> > > tie my @tied_array, 'Tie::File', $g or die "Could not tie to $g: $!"; >> > > >> > > ***@***.***_array, $_) for (1..3); >> > > >> > > print ***@***.***_array has " . scalar @tied_array . " elements before >> > sorting\n"; >> > > @tied_array = sort {uc($a) cmp uc($b)} @tied_array; >> > > >> > > print ***@***.***_array has " . scalar @tied_array . " elements after >> > sorting\n"; >> > > say Dumper ***@***.***_array); >> > > untie @tied_array; >> > > >> > > Results: >> > > >> > > $ perl perlmonks-710580-tie-file.pl >> > > @tied_array has 3 elements before sorting >> > > @tied_array has 4 elements after sorting >> > > $VAR1 = [ >> > > '1', >> > > '2', >> > > '3', >> > > '' >> > > ]; >> > > >> > > See perlmonks 710580 <http://www.perlmonks.org/?node_id=710580> for >> good >> > > analysis by @ikegami <https://github.com/ikegami> >> > > >> > >> > Imo this is a bug in perl not in Tie::File. >> > >> > I can imagine why the sort code might want to extend the array, but the >> > fact that it breaks tie modules shows it's not correct to do so. >> > >> > Yves >> > >> > > >> > >> > — >> > You are receiving this because you were mentioned. >> > Reply to this email directly, view it on GitHub >> > < >> #17496?email_source=notifications&email_token=AAFK2ZJ7A263WJSHBA3GLLTRAIUFRA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJL27Y#issuecomment-580042111 >> >, >> > or unsubscribe >> > < >> https://github.com/notifications/unsubscribe-auth/AAFK2ZI4AVXSFOFBP4DJQLDRAIUFRANCNFSM4KL355LA >> > >> > . >> > >> >> — >> You are receiving this because you commented. >> Reply to this email directly, view it on GitHub >> <#17496?email_source=notifications&email_token=AAAZ5R5YDLT4QONZULIQMMLRAJBNBA5CNFSM4KL355LKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKJRTLI#issuecomment-580065709>, >> or unsubscribe >> <https://github.com/notifications/unsubscribe-auth/AAAZ5RZPNCF3DGQ7776QHHDRAJBNBANCNFSM4KL355LA> >> . >> >

[ikegami]

On Wed, Jan 29, 2020 at 10:33 PM Yves Orton ***@***.***> wrote: EXTEND implies in memory semantics where the size of the allocated buffer differs from what is visible to the user of the array. A tie to some kind of external store, like Tie::File, cannot support this distinction. Whatever is allocated is necessarily "visible".

I see what you're saying. Is one allowed to access allocated elements beyond the length of the array? If so, then Tie::File is screwed. If not, then Tie::File could use STORESIZE instead of EXTEND (which would truly be just a *hint* that memory will be needed), and there's no reason for sort to extend the array.

[demerphq]

On Thu, 30 Jan 2020 at 05:54, Eric Brine ***@***.***> wrote: On Wed, Jan 29, 2020 at 10:33 PM Yves Orton ***@***.***> wrote: > EXTEND implies in memory semantics where the size of the allocated buffer > differs from what is visible to the user of the array. > > A tie to some kind of external store, like Tie::File, cannot support this > distinction. Whatever is allocated is necessarily "visible". > I see what you're saying. Is one allowed to access allocated elements beyond the length of the array?

Exactly what I was trying to say. But from the trace output (code attached as files): TiedArray_Test::TIEARRAY - TiedArray_Test::PUSH - 1 TiedArray_Test::PUSH - 2 TiedArray_Test::PUSH - 3 TiedArray_Test::FETCHSIZE - @tied_array has 3 elements before sorting TiedArray_Test::FETCHSIZE - TiedArray_Test::FETCH - 0 TiedArray_Test::FETCH - 1 TiedArray_Test::FETCH - 2 TiedArray_Test::CLEAR - TiedArray_Test::EXTEND - 4 TiedArray_Test::STORE - 0 1 TiedArray_Test::STORE - 1 2 TiedArray_Test::STORE - 2 3 TiedArray_Test::FETCHSIZE - @tied_array has 3 elements after sorting TiedArray_Test::FETCHSIZE - TiedArray_Test::FETCH - 0 TiedArray_Test::FETCH - 1 TiedArray_Test::FETCH - 2 $VAR1 = [ 1, 2, 3 ]; It seems like the EXTEND is not even used.

If so, then Tie::File is screwed. If not, then Tie::File could use STORESIZE instead of EXTEND (which would truly be just a *hint* that memory will be needed), and there's no reason for sort to extend the array.

Yes, exactly my point. I think Tie::File just needs to make EXTEND a no-op, and we need to change the documentation for EXTEND in perltie to specifically say "it is a bug to make EXTEND map to STORESIZE" and change the sample code to be a no-op. I will try to get such a patch pushed today or tomorrow. Yves

[demerphq]

On Thu, 30 Jan 2020 at 07:12, demerphq ***@***.***> wrote: Exactly what I was trying to say. But from the trace output (code attached as files): TiedArray_Test::TIEARRAY - TiedArray_Test::PUSH - 1 TiedArray_Test::PUSH - 2 TiedArray_Test::PUSH - 3 TiedArray_Test::FETCHSIZE - @tied_array has 3 elements before sorting TiedArray_Test::FETCHSIZE - TiedArray_Test::FETCH - 0 TiedArray_Test::FETCH - 1 TiedArray_Test::FETCH - 2 TiedArray_Test::CLEAR - TiedArray_Test::EXTEND - 4 TiedArray_Test::STORE - 0 1 TiedArray_Test::STORE - 1 2 TiedArray_Test::STORE - 2 3 TiedArray_Test::FETCHSIZE - @tied_array has 3 elements after sorting TiedArray_Test::FETCHSIZE - TiedArray_Test::FETCH - 0 TiedArray_Test::FETCH - 1 TiedArray_Test::FETCH - 2 $VAR1 = [ 1, 2, 3 ];

Doh, forgot the files....

[demerphq]

As far as the perltie change goes: ```diff diff --git a/pod/perltie.pod b/pod/perltie.pod index 2d433e8204..239a28e979 100644 --- a/pod/perltie.pod +++ b/pod/perltie.pod @@ -301,7 +301,7 @@ spaces so we have a little more work to do here: croak "length of $value is greater than $self->{ELEMSIZE}"; } # fill in the blanks - $self->EXTEND( $index ) if $index > $self->FETCHSIZE(); + $self->STORESIZE( $index ) if $index > $self->FETCHSIZE(); # right justify to keep element size for smaller elements $self->{ARRAY}->[$index] = sprintf "%$self->{ELEMSIZE}s", $value; } @@ -351,16 +351,24 @@ X<EXTEND> Informative call that array is likely to grow to have I<count> entries. Can be used to optimize allocation. This method need do nothing.

…

-In our example, we want to make sure there are no blank (C<undef>) -entries, so C<EXTEND> will make use of C<STORESIZE> to fill elements -as needed: +In our example there is no reason to implement this method, so we leave +it as a no-op. Most pure-perl tied array implementations will not need +to implement this, it is mostly present for low level implementations +where a call to EXTEND might be triggered by something like PUSH when +pushing multiple items into the array. sub EXTEND { my $self = shift; my $count = shift; - $self->STORESIZE( $count ); + # nothing to see here, move along. } +B<NOTE:> It is generally an error to make this equivalent to STORESIZE. +Perl may from time to time call EXTEND without wanting to actually change +the array size directly. Any tied array should function correctly if this +method is a no-op, if perhaps not be as efficient as it would if it +implemented this method. + =item EXISTS this, key X<EXISTS> ``` Yves

-- perl -Mre=debug -e "/just|another|perl|hacker/"