www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How do you safely deal with range.front?

reply aliak <something something.com> writes:
Hi,

So when I'm dealing with ranges, there're a number of times where 
I get the front of the returned result of a set of operations, 
but of course there is no front so you get an runtime access 
error.

In some other languages the concept of "front" or "first" returns 
a safe referece, or optional value that calling methods on will 
not crash the program.

I'm thinking of maybe making something like

safeFront(R)(R r) {
   return r.empty ? SafeRef!(ElementType!R) : SafeRef(r.front);
}

Where SafeRef, I think, can provide an overload for opDispatch 
and just forward the calls to the stored reference of r.front. If 
the stored reference is null then it can return a SafeRef to the 
return value of whatever was being dispatched to.

Is there another way to go about this? Maybe through naturally 
using r.front instead of making a r.safeFront alternative?

Cheers
Dec 29 2017
next sibling parent reply Seb <seb wilzba.ch> writes:
On Friday, 29 December 2017 at 19:38:44 UTC, aliak wrote:

 Hi,

 So when I'm dealing with ranges, there're a number of times 
 where I get the front of the returned result of a set of 
 operations, but of course there is no front so you get an 
 runtime access error.

 [...]


Do you know about the proposed `orElse`?

https://github.com/dlang/phobos/pull/5154
Dec 29 2017
parent aliak <something something.com> writes:
On Friday, 29 December 2017 at 20:11:03 UTC, Seb wrote:

 On Friday, 29 December 2017 at 19:38:44 UTC, aliak wrote:

 Hi,

 So when I'm dealing with ranges, there're a number of times 
 where I get the front of the returned result of a set of 
 operations, but of course there is no front so you get an 
 runtime access error.

 [...]


 Do you know about the proposed `orElse`?

 https://github.com/dlang/phobos/pull/5154


Oh cool. No I did not. Seems like a nice approach. It would incur 
the creation of a new object when one doesn't exist, which I 
guess would be fine for many situations, and would work for this 
as well probably, but it'd be nice to avoid it as well in some 
situations.

Just going thought std a bit now and I found this: 
https://dlang.org/library/std/typecons/black_hole.html

That would be pretty cool to have 
range.op!f.blackHoleFront.call() - though blackHoleFront sounds 
horrible :p
Dec 30 2017
prev sibling next sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Friday, December 29, 2017 19:38:44 aliak via Digitalmars-d-learn wrote:

 Hi,

 So when I'm dealing with ranges, there're a number of times where
 I get the front of the returned result of a set of operations,
 but of course there is no front so you get an runtime access
 error.


You don't necessarily get a runtime access error. It is undefined behavior
to call front on a range that's empty, and what happens depends entirely on
how the range is implemented. In plenty of cases, you'll get really weird
stuff happening and no obvious error. It is a bug for any code to call front
when empty is true.


 In some other languages the concept of "front" or "first" returns
 a safe referece, or optional value that calling methods on will
 not crash the program.

 I'm thinking of maybe making something like

 safeFront(R)(R r) {
    return r.empty ? SafeRef!(ElementType!R) : SafeRef(r.front);
 }

 Where SafeRef, I think, can provide an overload for opDispatch
 and just forward the calls to the stored reference of r.front. If
 the stored reference is null then it can return a SafeRef to the
 return value of whatever was being dispatched to.

 Is there another way to go about this? Maybe through naturally
 using r.front instead of making a r.safeFront alternative?


Well, I don't know what you're really doing in code here, but in general,
you'd write your code in a way that it checks empty and simply doesn't try
to do anything with front if the range is empty. If you're trying to require
that there's a front regardless of whether there is one, that sounds to me
like you're just asking for trouble, and if it were me, I'd refactor my code
so that that sort of thing wasn't happening. But if you have a use case
where that really does make sense, then there are a few options.

You could wrap the range in a range that returns a Nullable!(ElementType!R)
and return null when there is no front, which would then require the calling
code to check whether the Nullable was null rather than checking the range
for empty.

You could wrap the range in a range that specifically returns some default
element when the wrapped range is empty, meaning that the range would then
be infinite.

You could just use a wrapper function to call front and have it return a
Nullable or a default value if the range is empty, but that wouldn't work
when passing the range to other functions.

You could also do something like an infinite range that simply returns the
same value forever no matter how often front gets popped, and then you could
use chain to combine your range and that range into a single range that
would iterate through your range and then give the same element forever.

Regardless, you'll have to be careful of any solution that involves creating
an infinite range, since while some algorithms will be fine with it, others
will either not compile or result in an infinite loop (e.g. don't use
foreach on it).

Regardless, if you want to return an element when there isn't one, you're
going to have to come up with a value for that. It's not something that's
really going to work well generically. The closest would be the init value
of the element type, but how much that makes sense depends on the element
type and what you're doing.

- Jonathan M Davis
Dec 29 2017
parent reply aliak <something something.com> writes:
On Friday, 29 December 2017 at 20:33:22 UTC, Jonathan M Davis 
wrote:

 Well, I don't know what you're really doing in code here, but 
 in general, you'd write your code in a way that it checks empty 
 and simply doesn't try to do anything with front if the range 
 is empty.


Yes, ideally, if programmers were perfect, this would work. The 
same applies to always checking null before dereferencing a 
pointer. You can of course try and make sure you always do check 
first. Or you can provide a safe way to do it in cases where you 
only want to dereference a pointer if the pointer is not null. 
Granted in some situations you want to crash as well because it 
would indeed be a bug if a pointer was null (or a range was 
empty).

Btw, it seems that phobos, or at lest some of it, has an 
assert(!empty, "Attempting to fetch the front of an empty 
filter."). I guess probably it's not everywhere so hence the 
weird behavior you say happens sometimes :(  ... ah well.


 You could wrap the range in a range that specifically returns 
 some default element when the wrapped range is empty, meaning 
 that the range would then be infinite.

 You could just use a wrapper function to call front and have it 
 return a Nullable or a default value if the range is empty, but 
 that wouldn't work when passing the range to other functions.

 You could also do something like an infinite range that simply 
 returns the same value forever no matter how often front gets 
 popped, and then you could use chain to combine your range and 
 that range into a single range that would iterate through your 
 range and then give the same element forever.

 Regardless, you'll have to be careful of any solution that 
 involves creating an infinite range, since while some 
 algorithms will be fine with it, others will either not compile 
 or result in an infinite loop (e.g. don't use foreach on it).


True, having to deal with infinite ranges will add to number of 
cases I'd have to worry about. Would prefer not to of course.

I'm going to explore the Nullable approach you mentioned a bit me 
thinks !

Also, I found this now: 
https://forum.dlang.org/post/fshlmahxfaeqtwjbjouz forum.dlang.org 
. Seems to be what I'm looking for!


 Regardless, if you want to return an element when there isn't 
 one, you're going to have to come up with a value for that. 
 It's not something that's really going to work well generically.


The generic constructs would occur ideally before accessing 
front. If not then yes, you're correct. Passing a "safeFront", or 
any other non-range value further down the pipeline would need a 
an undo function the other end of the pipeline.
Dec 30 2017
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Saturday, December 30, 2017 19:11:20 aliak via Digitalmars-d-learn wrote:

 On Friday, 29 December 2017 at 20:33:22 UTC, Jonathan M Davis

 wrote:

 Well, I don't know what you're really doing in code here, but
 in general, you'd write your code in a way that it checks empty
 and simply doesn't try to do anything with front if the range
 is empty.


 Yes, ideally, if programmers were perfect, this would work. The
 same applies to always checking null before dereferencing a
 pointer. You can of course try and make sure you always do check
 first. Or you can provide a safe way to do it in cases where you
 only want to dereference a pointer if the pointer is not null.
 Granted in some situations you want to crash as well because it
 would indeed be a bug if a pointer was null (or a range was
 empty).

 Btw, it seems that phobos, or at lest some of it, has an
 assert(!empty, "Attempting to fetch the front of an empty
 filter."). I guess probably it's not everywhere so hence the
 weird behavior you say happens sometimes :(  ... ah well.


Some ranges do use assertions to check stuff like that, but there is zero
guarantee that a range is going to do that, and the checks won't be there
with -release. So, you might sometimes catch mistakes that way, but you
can't rely on it any more than you can rely on any stray programming bug
being caught. At some point, you simply have to do your best to not write
bugs and write thorough enough unit tests to be reasonably sure that you've
caught whatever you missed. There's nothing special about ranges in that
regard.

- Jonathan M Davis
Dec 30 2017
prev sibling parent reply Dukc <ajieskola gmail.com> writes:
On Friday, 29 December 2017 at 19:38:44 UTC, aliak wrote:

 So when I'm dealing with ranges, there're a number of times 
 where I get the front of the returned result of a set of 
 operations, but of course there is no front so you get an 
 runtime access error.


This could be what you want:

auto makeInfinite(Range)(Range ofThis)
{   import std.range;
     return ofThis.chain(typeof(ofThis.front).init.repeat);
}

void main()
{   import std.stdio, std.range;
     auto testArray = [2, 3, 4].makeInfinite;
     foreach(e; testArray.take(5)) e.writeln;
     readln(); //stops the console from closing immediately;
}

/+
2
3
4
0
0
+/

On the other hand, I really do not recommend using ranges that 
way as a default. Most often you do not want to call front() or 
popFront() of an empty range in the first place. So if you end up 
doing so accidently, you want to know it. If it just returned 
some default value chances would be you never notice you have a 
bug. That's why front() in debug mode is usually programmed to 
termitate the program when it's called incorrectly.
Dec 29 2017
parent reply aliak <something something.com> writes:
On Friday, 29 December 2017 at 20:47:44 UTC, Dukc wrote:

 On Friday, 29 December 2017 at 19:38:44 UTC, aliak wrote:

 So when I'm dealing with ranges, there're a number of times 
 where I get the front of the returned result of a set of 
 operations, but of course there is no front so you get an 
 runtime access error.


 This could be what you want:

 auto makeInfinite(Range)(Range ofThis)
 {   import std.range;
     return ofThis.chain(typeof(ofThis.front).init.repeat);
 }

 void main()
 {   import std.stdio, std.range;
     auto testArray = [2, 3, 4].makeInfinite;
     foreach(e; testArray.take(5)) e.writeln;
     readln(); //stops the console from closing immediately;
 }

 /+
 2
 3
 4
 0
 0
 +/


Hmm, interesting. Not sure that's what I'm looking for but I like 
it anyway :)

I'm more looking to deal with situations like this:

Instead of this:
   auto result = range.op!f;
   if (!result.empty) {
     result.front.method();
   }

This:
   range.op!f.ifFront.method();


In the above scenario I only want method to be called if the 
pipeline resulted in any element left in the range.


 On the other hand, I really do not recommend using ranges that 
 way as a default. Most often you do not want to call front() or 
 popFront() of an empty range in the first place. So if you end 
 up doing so accidently, you want to know it. If it just 
 returned some default value chances would be you never notice 
 you have a bug. That's why front() in debug mode is usually 
 programmed to termitate the program when it's called 
 incorrectly.


True you don't want to call front on empty, but sometimes I only 
care to call a method on front if it's there. Where the situation 
necessitates the existence of front, and not having a front is 
indeed a bug, then you want the program to terminate, yes. But 
not otherwise.
Dec 30 2017
next sibling parent Mengu <mengukagan gmail.com> writes:
On Saturday, 30 December 2017 at 19:00:07 UTC, aliak wrote:

 On Friday, 29 December 2017 at 20:47:44 UTC, Dukc wrote:

 [...]


 Hmm, interesting. Not sure that's what I'm looking for but I 
 like it anyway :)

 I'm more looking to deal with situations like this:

 Instead of this:
   auto result = range.op!f;
   if (!result.empty) {
     result.front.method();
   }

 This:
   range.op!f.ifFront.method();


 In the above scenario I only want method to be called if the 
 pipeline resulted in any element left in the range.


 [...]


 True you don't want to call front on empty, but sometimes I 
 only care to call a method on front if it's there. Where the 
 situation necessitates the existence of front, and not having a 
 front is indeed a bug, then you want the program to terminate, 
 yes. But not otherwise.


it would be actually great in such scenarios if d had a language 
construct for existantial checks. you'd just be able to do 
range.front?.method(). but no, it is not 2017. d does not need it.
Dec 30 2017
prev sibling next sibling parent reply Dukc <ajieskola gmail.com> writes:
On Saturday, 30 December 2017 at 19:00:07 UTC, aliak wrote:

 Instead of this:
   auto result = range.op!f;
   if (!result.empty) {
     result.front.method();
   }

 This:
   range.op!f.ifFront.method();


Ah, so you don't have a problem with checking emptiness but you 
want to do it inside the expression, without having to type the 
range twice? I personally find it useful to define an "use" 
template for cases like this:

import std.typecons : Nullable;

auto ref use(alias how, T)(T what){return how(what);}

void main()
{
     import std.algorithm, std.range, std.stdio;
     auto arr = [2, 3, 4];
     foreach(unused; 0 .. 5)
     {   arr
             .map!(x => (x + 2) * x)
             .use!(x => x.empty? 0: x.front)
             .writeln;
         if (arr.empty){} else arr.popFront;
     }
     readln(); //program termination delayed until pressing enter
}

/+
8
15
24
0
0
+/

Of course, if you want you can also define a more specialized 
template which does not require typing the lambda function.
Dec 30 2017
parent reply Tony <tonytdominguez aol.com> writes:
For me, front() should throw a pre-defined exception when called 
on an empty range in order to eliminate undefined behavior. It 
does take some time to make a check, but D does array bounds 
checking by default. Ideally the front() check could be turned 
off somehow ("-boundschecks=off") by the user for those who want 
maximum speed, but I guess there is no way to do that when using 
pre-compiled functions in a library.
Dec 30 2017
next sibling parent reply aliak <something something.com> writes:
On Sunday, 31 December 2017 at 01:03:17 UTC, Tony wrote:

 For me, front() should throw a pre-defined exception when 
 called on an empty range in order to eliminate undefined 
 behavior. It does take some time to make a check, but D does 
 array bounds checking by default. Ideally the front() check 
 could be turned off somehow ("-boundschecks=off") by the user 
 for those who want maximum speed, but I guess there is no way 
 to do that when using pre-compiled functions in a library.


That sounds like a good idea. Wouldn't the same apply to array 
bounds checking for precompiled functions though?

Also, is going out of array bounds well defined behavior in D 
even with boundscheck off? And any links to docs on UB in D?
Dec 31 2017
next sibling parent Tony <tonytdominguez aol.com> writes:
On Sunday, 31 December 2017 at 13:14:10 UTC, aliak wrote:

 On Sunday, 31 December 2017 at 01:03:17 UTC, Tony wrote:

 For me, front() should throw a pre-defined exception when 
 called on an empty range in order to eliminate undefined 
 behavior. It does take some time to make a check, but D does 
 array bounds checking by default. Ideally the front() check 
 could be turned off somehow ("-boundschecks=off") by the user 
 for those who want maximum speed, but I guess there is no way 
 to do that when using pre-compiled functions in a library.


 That sounds like a good idea. Wouldn't the same apply to array 
 bounds checking for precompiled functions though?


Yeah, seems like the standard library must be doing one or the 
other (bounds checking array indexes or not bounds checking them) 
all the time, depending on how it was compiled.


 Also, is going out of array bounds well-defined behavior in D 
 even with bounds check off?


I'm no expert, but I can't think of how it could be.


 And any links to docs on UB in D?


This thread was the first time I have heard it used with regard 
to D.
Dec 31 2017
prev sibling parent ag0aep6g <anonymous example.com> writes:
On 12/31/2017 02:14 PM, aliak wrote:

 Also, is going out of array bounds well defined behavior in D even with 
 boundscheck off?


No. Without the checks you get undefined behavior. I.e., 
`-boundscheck=off` defeats the ` safe` attribute. For that reason, I'd 
advise against ever using it. Definitely don't think of it as a harmless 
optimization switch.
Dec 31 2017
prev sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Sunday, December 31, 2017 01:03:17 Tony via Digitalmars-d-learn wrote:

 For me, front() should throw a pre-defined exception when called
 on an empty range in order to eliminate undefined behavior. It
 does take some time to make a check, but D does array bounds
 checking by default. Ideally the front() check could be turned
 off somehow ("-boundschecks=off") by the user for those who want
 maximum speed, but I guess there is no way to do that when using
 pre-compiled functions in a library.


Except that the reason for arrays throwing RangeErrors when you try and
index them out-of-bounds is to avoid memory safety issues, which is not
necessarily the case at all when you're talking about ranges. Having ranges
in general be checking empty in front, popFront, back, etc. would add
unnecessary overhead - especially when you consider that ranges often wrap
other ranges. You'd be layering on check after check when the calling code
is already supposed to be checking empty when necessary to make sure that
the range isn't empty. You'd even be layering checks on top of the checks
that arrays already do, since many ranges are ultimately wrapped around a
dynamic array at their core.

The extra checks on arrays avoid nasty memory-related problems and don't
involve layering on extra checks all over the place, whereas ranges in
general do not pose a memory safety problem (those that do should do checks
like dynamic arrays do, but that's not the norm).

As for -boundschecks=off, that arguably shouldn't even exist. It can already
be gotten around using the ptr property if you really want that extra speed,
and the vast majority of programs shouldn't even consider using it, because
skipping the bounds checking in arrays is just begging for memory corruption
problems.

- Jonathan M Davis
Dec 31 2017
parent aliak <something something.com> writes:
On Monday, 1 January 2018 at 02:18:36 UTC, Jonathan M Davis wrote:

 Except that the reason for arrays throwing RangeErrors when you 
 try and index them out-of-bounds is to avoid memory safety 
 issues, which is not necessarily the case at all when you're 
 talking about ranges. Having ranges in general be checking 
 empty in front, popFront, back, etc. would add unnecessary 
 overhead - especially when you consider that ranges often wrap 
 other ranges. You'd be layering on check after check when the 
 calling code is already supposed to be checking empty when 
 necessary to make sure that the range isn't empty. You'd even 
 be layering checks on top of the checks that arrays already do, 
 since many ranges are ultimately wrapped around a dynamic array 
 at their core.

 [...]


Makes sense. Especially after pointing out that ranges are mostly 
arrays at the end. Thanks!
Jan 01 2018
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 12/30/2017 11:00 AM, aliak wrote:


 Instead of this:
    auto result = range.op!f;
    if (!result.empty) {
      result.front.method();
    }
 
 This:
    range.op!f.ifFront.method();
 
 
 In the above scenario I only want method to be called if the pipeline 
 resulted in any element left in the range.


If you're fine with specifying the function as a template argument, the 
following works. (As seen with 's => s.foo()' below, you have to use a 
lambda for member functions anyway.)

auto ifFront(alias func, R)(R range) {
     import std.traits : isArray;
     static if (isArray!R) {
         import std.array : empty, front;
     }
     if (!range.empty) {
         func(range.front);
     }
}

unittest {
     size_t executed;

     struct S {
         size_t *e;
         this(ref size_t e) {
             this.e = &e;
         }

         void foo() {
             ++(*e);
         }
     }

     auto foo(int) {
         ++executed;
     }

     // Non-empty array; should be called
     auto a = [1];
     a.ifFront!foo;
     assert(executed == 1);

     // Empty array; should not be called
     int[] b;
     b.ifFront!foo;
     assert(executed == 1);

     // Non-empty S array; should be called
     auto c = [ S(executed) ];
     c.ifFront!(s => s.foo());
     assert(executed == 2);

     // Empty S array; should not be called
     S[] d;
     d.ifFront!(s => s.foo());
     assert(executed == 2);
}

void main() {
}

Ali
Dec 31 2017
parent aliak <something something.com> writes:
On Monday, 1 January 2018 at 04:18:29 UTC, Ali Çehreli wrote:

 If you're fine with specifying the function as a template 
 argument, the following works. (As seen with 's => s.foo()' 
 below, you have to use a lambda for member functions anyway.)

 Ali


Nice! Thanks :) And I think your usage for something named 
"ifFront" actually makes more sense than using it to return 
"saferef" functionality.

I've basically implemented an optional type for now and the 
"iffront" implementation looks like this:

import std.range: isInputRange;

auto iffront(Range)(Range r) if (isInputRange!Range) {
     import std.range: ElementType, empty, front;
     import optional: no, some;
     return r.empty ? no!(ElementType!Range) : some(r.front);
}

unittest {
     import std.algorithm: filter;
     assert([false].filter!"a".iffront.empty); // because optional 
is a range
}

unittest {
     import std.algorithm: filter;
     import optional: some, none;
     struct A {
         int f() {
             return 7;
         }
     }

     assert([A()].filter!"false".iffront.f == none);
     assert([A()].filter!"true".iffront.f == some(7));
}

And thanks everyone for the input. I'll play around with some of 
the ideas and see what comes of it.
Jan 01 2018