www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 12104] New: std.algorithm.copy misses some length bugs at compile-time

https://d.puremagic.com/issues/show_bug.cgi?id=12104

           Summary: std.algorithm.copy misses some length bugs at
                    compile-time
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: diagnostic
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc


--- Comment #0 from bearophile_hugs eml.cc 2014-02-07 17:16:25 PST ---
This issue asks for is a diagnostic Phobos enhancement.

This not much idiomatic Python function copies the items from the first
iterable to the second object that supports the random access:


def copy_in_place(a, b):
    if len(b) < len(a):
        raise IndexError()
    for i, x in enumerate(a):
        b[i] = x

A = [10, 20, 30, 40]
B = [0, 0]
copy_in_place(A, B)
print B


Python is dynamic typed, so that program has to raise IndexError at run-time. D
is statically typed so its type system could and should be used to catch at
compile-time as many errors as possible. If we pay for having a static type
system, it's right to ask it to give us back as much as possible.

Let's see how D+Phobos acts. This can't work because A and B are of different
type, so for efficiency reasons this operation is statically forbidden:


void main() {
    import std.algorithm: copy;
    int[12] A;
    long[12] B;
    B[] = A[]; // Error, OK.
}


This works:

void main() {
    import std.algorithm: copy;
    int[12] A;
    long[12] B;
    A[].copy(B[]); // OK
}


This doesn't work because the std.algorithm.copy refuses fixed-sized arrays by
design:

void main() {
    import std.algorithm: copy;
    int[12] A;
    long[12] B;
    A.copy(B); // Error
}


Despite D is statically typed, and its type system is strong enough to support
fixed-sized arrays and templates well, this bug is not caught at compile-time:

void main() {
    import std.algorithm: copy;
    int[12] A;
    int[10] C;
    A[].copy(C[]); // Run-time exception.
}


So to catch some bugs at compile-time I suggest to support fixed-sized arrays
in std.algorithm.copy:

void main() {
    import std.algorithm: copy;
    int[12] A;
    int[10] C;
    A.copy(C); // Should give a compile-time error.
}


A disadvantage of this (beside the disadvantage of a little more complex copy
function, because it has to handle more input cases) is that the copy()
template gets instantiated not just for every pair of input types (here int and
long) but also for every pair of lengths if you use fixed-sized arrays. This
could lead to template bloat.

One way to reduce most of the template bloat is to create just a light wrapper
of copy() that accepts the fixed sized arrays (and verifies their length at
compile-time) and internally calls the version of copy() that works with
dynamic arrays. This way only the light wrapper is instantiated for every pair
of lengths if you use fixed-sized arrays. (A small disadvantage of this
strategy is that when you compile the code without inlining if one of your
arguments is a fixed-size array your copy() performs two function calls. But
this is not a significant problem).

Despite I have tagged this issue as a Phobos one, a better solution to this
template bloat is to improve the D language, introducing a syntax to manage
ghost types (in this case ghost values of the lenght) that do not induce
different template instantiations. I think this problem will eventually need to
be solved in D.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 07 2014