www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Getting a range over a const Container

reply Matthias Walter <xammy xammy.homelinux.net> writes:
Hi,

I have a const std.container object (e.g., a const(Array!int)) of which
I'd like to have a range which can traverse that container having
read-only access. This does not seem to be possible with opSlice(). Is
there an alternative?

Best regards,

Matthias
Jun 15 2012
parent reply Francisco Soulignac <fsoulign dc.uba.ar> writes:
Hi all,

it's been a while since this question, and I don't know how to solve
it either.  The following code passes all the test using the last
version of dmd (2.059).

import std.container, std.algorithm;

//non const case
void assertequal(T)(SList!(T) l, int[] r) {
    assert(equal(l[], r));
}

//const case
void const_assertequal(T)(const SList!(T) l, int[] r) {
    assert(equal(l[], r));
}

unittest{
    SList!(int) l;
    l.insertFront(2);
    l.insertFront(1);
    assertequal (l,   [1,2]);
    assert(!__traits(compiles, const_assertequal(l, [1,2])));
}

The conflict with the last assertion is that opSplice can't be
applied to const.  So, I looked at the container module, and made a
minimal example of a list myself (emulating SList).

struct List {
    struct Node {
        Node* next;
        int val;
    }

    private Node* first;

    struct Range {
//sorry about "actual", it should have been current
        private Node* actual;
        this(Node* first) {actual = first;}
         property front() {return actual.val;}
         property empty() const {return !actual;}
        void popFront() {assert(!empty); actual = actual.next;}
        Range save() {return this;}
    }
    unittest{static assert(isForwardRange!(Range));}

    void add(int v) {
        Node * next = first;
        first = new Node;
        first.val = v;
        first.next = next;
    }

    Range opSlice() {
        return Range(first);
    }

}

void assertequal(L : List)(L l, int[] r) {
    assert(equal(l[], r));
}

void assertequal_const(L : List)(L l, int[] r) {
    assert(equal(l[], r));
}

unittest{
    List l;
    l.add(2);
    l.add(1);
    assert(equal(l[], [1,2]));
    assertequal (l,   [1,2]);
    assert(!__traits(compiles, const_assertequal(l, [1,2])));
}

As far as I know, the problem comes with the transitivity of const.
In assertequal_const, l.first has type const(Node*), thus it can't
be converted to Node* in Range's constructor.  I can't manage to
find a workaround here, because l.first will always have type
const(Node*), but for traversing the list I require to copy l.first
into some node, say actual, whose type is Node* so that I can move
it doing actual = actual.next.  I would be happy to do

actual = cast(Node*)(l.first)
actual = actual.next;

but that code is suppose to be undefined, isn't it?
(http://dlang.org/const3.html : Removing Immutable With A Cast).

So, my question is how can I (correctly) traverse a const SList,
const DList, etc?

Best,
Francisco.
PS: sorry for the long mail.
Jul 18 2012
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, July 19, 2012 04:39:26 Francisco Soulignac wrote:

 So, my question is how can I (correctly) traverse a const SList,
 const DList, etc?


Right now? I'm pretty sure that that's impossible. Hopefully that will change, 
but getting const and ranges to work together can be rather difficult, and 
std.container needs more work in that regard.

- Jonathan M Davis
Jul 18 2012
prev sibling next sibling parent reply Artur Skawina <art.08.09 gmail.com> writes:
On 07/19/12 06:39, Francisco Soulignac wrote:

 it's been a while since this question, and I don't know how to solve
 it either.  The following code passes all the test using the last
 version of dmd (2.059).
 
 import std.container, std.algorithm;
 
 //non const case
 void assertequal(T)(SList!(T) l, int[] r) {
     assert(equal(l[], r));
 }
 
 //const case
 void const_assertequal(T)(const SList!(T) l, int[] r) {
     assert(equal(l[], r));
 }
 
 unittest{
     SList!(int) l;
     l.insertFront(2);
     l.insertFront(1);
     assertequal (l,   [1,2]);
     assert(!__traits(compiles, const_assertequal(l, [1,2])));
 }
 
 The conflict with the last assertion is that opSplice can't be
 applied to const.  So, I looked at the container module, and made a
 minimal example of a list myself (emulating SList).
 
 struct List {
     struct Node {
         Node* next;
         int val;
     }
 
     private Node* first;
 
     struct Range {
 //sorry about "actual", it should have been current
         private Node* actual;
         this(Node* first) {actual = first;}
          property front() {return actual.val;}
          property empty() const {return !actual;}
         void popFront() {assert(!empty); actual = actual.next;}
         Range save() {return this;}
     }
     unittest{static assert(isForwardRange!(Range));}
 
     void add(int v) {
         Node * next = first;
         first = new Node;
         first.val = v;
         first.next = next;
     }
 
     Range opSlice() {
         return Range(first);
     }
 
 }
 
 void assertequal(L : List)(L l, int[] r) {
     assert(equal(l[], r));
 }
 
 void assertequal_const(L : List)(L l, int[] r) {
     assert(equal(l[], r));
 }
 
 unittest{
     List l;
     l.add(2);
     l.add(1);
     assert(equal(l[], [1,2]));
     assertequal (l,   [1,2]);
     assert(!__traits(compiles, const_assertequal(l, [1,2])));
 }
 
 As far as I know, the problem comes with the transitivity of const.
 In assertequal_const, l.first has type const(Node*), thus it can't
 be converted to Node* in Range's constructor.  I can't manage to
 find a workaround here, because l.first will always have type
 const(Node*), but for traversing the list I require to copy l.first
 into some node, say actual, whose type is Node* so that I can move
 it doing actual = actual.next.  I would be happy to do
 
 actual = cast(Node*)(l.first)
 actual = actual.next;
 
 but that code is suppose to be undefined, isn't it?
 (http://dlang.org/const3.html : Removing Immutable With A Cast).
 
 So, my question is how can I (correctly) traverse a const SList,
 const DList, etc?


   import std.algorithm, std.range;

   struct List {
       static struct Node {
           Node* next;
           int val;
       }

       private Node* first;

       static struct Range(E) {
           private E* current;
           this(FE:const E)(FE* first) {current = first;}
            property front() {return current.val;}
            property empty() const {return !current;}
           void popFront() {assert(!empty); current = current.next;}
            property Range save() {return this;}
       }
       static assert(isForwardRange!(Range!Node));

       void add(int v) {
           Node * next = first;
           first = new Node;
           first.val = v;
           first.next = next;
        }

       Range!Node opSlice() { return Range!Node(first); }
       Range!(const Node) opSlice() const { return Range!(const Node)(first); }
   }

   void assertequal(L : List)(L l, int[] r) {
       assert(equal(l[], r));
   }

   void assertequal_const(L : List)(const L l, int[] r) {
       assert(equal(l[], r));
   }

   void main() {
       List l;
       l.add(2);
       l.add(1);
       assert(equal(l[], [1,2]));
       assertequal (l,   [1,2]);
       assertequal_const(l, [1,2]);
   }

artur
Jul 19 2012
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 07/19/2012 02:51 AM, Artur Skawina wrote:

         Range!Node opSlice() { return Range!Node(first); }
         Range!(const Node) opSlice() const { return Range!(const Node)(first);
}



anyone mind cluing me in on why this is possible?
Jul 19 2012
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 07/19/2012 06:09 PM, Ellery Newcomer wrote:

 On 07/19/2012 02:51 AM, Artur Skawina wrote:

 Range!Node opSlice() { return Range!Node(first); }
 Range!(const Node) opSlice() const { return Range!(const Node)(first); }



 anyone mind cluing me in on why this is possible?


It is the same as in C++. Considering the hidden non-const this and 
const this parameters, one of the member functions is a better match for 
each call:

import std.stdio;

struct S
{
     void foo(string name)
     {
         writeln("Called on ", name);
         assert(typeid(this) == typeid(S));
     }

     void foo(string name) const
     {
         writeln("Called on ", name);
         assert(typeid(this) == typeid(const S));
     }
}

void main()
{
     auto a = S();
     const b = S();

     a.foo("a");    // matches non-const foo()
     b.foo("b");    // matches const foo()
}

The output:

Called on a
Called on b

Ali
Jul 19 2012
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 07/19/2012 06:16 PM, Ali Çehreli wrote:

 On 07/19/2012 06:09 PM, Ellery Newcomer wrote:

 On 07/19/2012 02:51 AM, Artur Skawina wrote:

 Range!Node opSlice() { return Range!Node(first); }
 Range!(const Node) opSlice() const { return Range!(const Node)(first); }



 anyone mind cluing me in on why this is possible?


 It is the same as in C++. Considering the hidden non-const this and
 const this parameters, one of the member functions is a better match for
 each call:


Ha ha! The output is worthless when both functions print the same thing. :)

This is better:

import std.stdio;

struct S
{
     void foo(string name)
     {
         writeln("non-const foo called on ", name);
         assert(typeid(this) == typeid(S));
     }

     void foo(string name) const
     {
         writeln("const foo called on ", name);
         assert(typeid(this) == typeid(const S));
     }
}

void main()
{
     auto a = S();
     const b = S();

     a.foo("a");    // matches non-const foo()
     b.foo("b");    // matches const foo()
}

Now the output is different:

non-const foo called on a
const foo called on b

Ali
Jul 19 2012
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 07/19/2012 06:18 PM, Ali Çehreli wrote:

 Now the output is different:

 non-const foo called on a
 const foo called on b

 Ali



cool beans, thanks.
Jul 19 2012
prev sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 07/19/2012 06:09 PM, Ellery Newcomer wrote:

 On 07/19/2012 02:51 AM, Artur Skawina wrote:

         Range!Node opSlice() { return Range!Node(first); }
         Range!(const Node) opSlice() const { return Range!(const
 Node)(first); }





it looks like you could almost merge these two into one using inout, but 
I'm not sure what you do about selecting the return type.
Jul 20 2012
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, July 20, 2012 17:15:53 Ellery Newcomer wrote:

 On 07/19/2012 06:09 PM, Ellery Newcomer wrote:

 On 07/19/2012 02:51 AM, Artur Skawina wrote:

 Range!Node opSlice() { return Range!Node(first); }
 Range!(const Node) opSlice() const { return Range!(const
 
 Node)(first); }




 
 it looks like you could almost merge these two into one using inout, but
 I'm not sure what you do about selecting the return type.


If everywhere that you use const, you can use inout, then it may work. But the 
return type is not only a difference in constness. It's a completely different 
type.

The other problem is that the const opSlice is actually _very_ broken as far 
as range-based functions typically go. Whil opSlice doesn't technically 
require it (though it probably should), it's _very_ common for function using 
opSlice to assign the result to the original range, and that's not possible 
with this code.

I keep meaning to bring it up for discussion in the newsgroup, but it's a big 
problem. You basically need tail-const, and I don't know of any way to 
implement it, because the only way to get implicit conversions is to use alias 
this, and that results in a recursive template instantiation, which kills the 
compiler. I don't think that it's actually possible to properly implement a 
const opSlice for many ranges right now.

- Jonathan M Davis
Jul 20 2012
prev sibling parent Matthias Walter <xammy xammy.info> writes:
On 07/19/2012 06:44 AM, Jonathan M Davis wrote:

 On Thursday, July 19, 2012 04:39:26 Francisco Soulignac wrote:

 So, my question is how can I (correctly) traverse a const SList,
 const DList, etc?


 
 Right now? I'm pretty sure that that's impossible. Hopefully that will change, 
 but getting const and ranges to work together can be rather difficult, and 
 std.container needs more work in that regard.


Well it doesn't work yet. But in principle it could since we can always
copy a const pointer to a non-const one to const data:

Node* actual; // but 'this' is const and hence the type is const(Node*)

const(Node)* i_will_traverse = actual;

Best regards,

Matthias
Jul 18 2012