Tcl Source Code

View Ticket
Login
Ticket UUID: 47ac84309bab4719c58a693f5d63d837887f3b17
Title: more (compiled) lreplace madness
Type: Bug Version: trunk
Submitter: aspect Created on: 2015-06-22 03:24:10
Subsystem: 14. List Object Assigned To: dkf
Priority: 4 Severity: Minor
Status: Closed Last Modified: 2016-04-04 21:43:02
Resolution: Fixed Closed By: dkf
    Closed on: 2016-04-04 21:43:02
Description:

in chasing [44fd4b9a4e], another edge case with compiled lreplace:

% lreplace {a b c} end 0
!! {a b c} != {a b b c}
% lreplace {a b c} end 0 A
!! {a b A c} != {a b A b c}

In each case the LHS is the interpreted & correct answer, RHS compiled & incorrect.

Test script:

proc check {cmd} {
    puts "% $cmd"
    proc t {} $cmd
    set rc [t]
    set ri [uplevel 1 $cmd]
    if {$ri ne $rc} {
        puts "!! [list $ri != $rc]"
    } else {
        puts "ok [list $rc]"
    }
}

foreach {a} { 0 1 2 3 end-3 end-2 end-1 end } { check [list lreplace {a b c} end $a] check [list lreplace {a b c} end $a a] }

User Comments: dkf added on 2016-04-04 21:43:02:

OK, everything should be fixed. I might wish to revisit and reconsider how we compile lreplace, but that'll be entirely new work centred around doing the whole job, and it might only get done in Tcl 9.

Thanks to Alexandre Ferrieux for his assistance with reviewing.


dkf added on 2016-03-30 08:52:39:

I've now imported the changes from the branch on aspect's chiselapp repository into the main Tcl repository, where they are more visible (same name of branch; changes just the total ones except that the bulk testing is done a little bit differently).

They change some existing behaviour so they need a bit wider review than just me, though I'm minded to go with them.


dkf added on 2016-03-27 16:39:06:

Disabled compilation in these cases. Fixing it while keeping everything compiled will require a totally different strategy, probably with new bytecodes.


dkf added on 2016-03-27 15:38:42:

Hmm, I can't read that repository right now; chiselapp is having one of its periodic conniptions.


aspect added on 2015-11-17 08:28:04:
See also [578c2fd960].

Ping?  I could use some feedback on how the
aspect-lreplace-cleanup branch can be brought into
a state suitable for merging.

aspect added on 2015-06-29 12:31:43:
Finally had a chance to be confident enough with my results to commit and push:
see branch "aspect-lreplace-cleanup" in
http://chiselapp.com/user/aspect/repository/tcl/timeline

It's not very tidy I'm afraid as donuts are interfering, but a quick précis:

[0c4a83c31e] fixes the bug raised in this ticket (without introducing a test - oops)

[b820489dec] is a new empty-list bug fixed with a test case introduced in 355706aa97

[0f2c6bc9a8] modifies both compiled and interpreted lreplace to allow appending.
This might still be controversial :-).

[0586ceac09] introduces a "test battery" enumerating over a set of small list
cases ensuring compiled and interpreted both agree with a reference
implementation, for a total of about 1200 "mostly free" tests.  It's not at
all integrated with tcltest, so failures aren't reported usefully for
downstreams to submit, but was tremendously helpful in this exercise.


I hope all but [0f2c6bc9a8] (lreplace can append) and the associated test change 
should be easy to accept, or at least beat into shape.  I'm a little less sure
this one is a good idea recalling now that {[string replace foo 3 3 bar] == "foo"}.

dgp added on 2015-06-25 14:25:39:
"bug #1705" is now

http://core.tcl.tk/tcl/tktview/218675

aspect added on 2015-06-25 03:16:29:

Empty-list behaviour was first documented in [ae7e3132d3602091], which references "bug #1705" from 2000. I can't find bug #1705, but the behaviour has existed since the beginning of available history http://core.tcl.tk/tcl/artifact/7969e2e65bb3ab96?ln=2239? I guess that's not changing!

While spelunking for that I discovered another argument for end+1 indexing. [linsert] has also usefully supported it for a long time:

% linsert 1 2 d 1 d


dgp added on 2015-06-24 18:44:01:
No, [lreplace] was did not become a bytecode compiled
command until Tcl 8.6.

aku added on 2015-06-24 18:04:16:
So, then likely a bug introduced with the bytecode compiler.

dgp added on 2015-06-24 17:20:41:
No. that disparity was in place long before TIP 323:

% info patch
8.0.3
% lreplace {} 2 2
% lreplace 1 2 2
list doesn't contain element 2


But curiously not in Tcl 7:

% info patch
7.6p2
% lreplace {} 2 2
list doesn't contain element 2
% lreplace 1 2 2
list doesn't contain element 2

aku added on 2015-06-24 16:35:07:
> % lreplace {} 2 2
>
> % lreplace 1 2 2
> list doesn't contain element 2

> Perhaps if anyone can come up with a good motivation
> for the error being suppressed for an empty list, I
> can add that to the manual too.

I wonder if that might be due to TIP 323 "Do nothing gracefully", i.e.
http://tip.tcl.tk/323

aspect added on 2015-06-24 13:19:00:
I think it's safe to preserve the compilation of lreplace in simple cases:
both index arguments known and of the same "sign".  Ferrieux has also
advised "drastically reducing the ambition of the optimiser" in [44fd4b9a4e].
I'm very much in agreement that falling back to the interpreted version when it
gets difficult is the path to sanity.

That, and clearly articulating the various cases.  Which is where it gets
interesting (see also [44fd4b9a4e]):


Compiled lreplace has supported end+1 indexing to append since at least
8.6.3:

% lreplace a 1 1 b
a b
% lreplace a end+1 end+1 b
a b

This isn't documented or supported by interpreted lreplace, but it seems to
be useful.  I would like to add this to supported behaviour of [lreplace],
complete with a decent set of tests and an example in the man page.


As an aside, I find the below surprising .. it's documented and consistently
implemented behaviour, but I cannot understand the motivation.

% lreplace {} 2 2

% lreplace 1 2 2
list doesn't contain element 2

Perhaps if anyone can come up with a good motivation for the error being
suppressed for an empty list, I can add that to the manual too.

msofer added on 2015-06-22 17:49:07:
Do we have a good case for compiling lreplace at all?

oehhar added on 2015-06-22 15:39:32:

Exchanged "correct" and "incorrect" in the description. I hope this is correct.

Harald


aspect added on 2015-06-22 07:43:30:

For clarity, the manual's words on $idx2 < $idx1:

If last is less than first, then any specified elements will be inserted into the list at the point specified by first with no elements being deleted.

Clearly in the case of exactly one end-based index, this requires some computation with the length of the list.


aspect added on 2015-06-22 07:41:25:

It looks to me like compiled lreplace as currently implemented cannot correctly deal with indexes of differing sign (ie, one is an end-based index).

here is the code responsible for the "dropRange" case. It compiles as the equivalent of:

concat [lrange $l 0 $idx1-1] [lrange $l $idx2+1 end]

which is fine in ordinary cases, but fails when one of the indices is end-based and $idx2 < $idx1.

To fix this, compiled lreplace needs to be sensitive to the length of the list it is examining. Simplest is probably to emit bytecode for end-based indexes that does the arithmetic to make them positive.

Since that has to be computed on the stack, and INST_LIST_RANGE_IMM seems to need its arguments as immediates, I need advice on what bytecode instructions should be used in this case.


Attachments: