Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

duckmap can recurse indefinitely under some circumstances #5686

Closed
p6rt opened this issue Sep 20, 2016 · 7 comments
Closed

duckmap can recurse indefinitely under some circumstances #5686

p6rt opened this issue Sep 20, 2016 · 7 comments

Comments

@p6rt
Copy link

p6rt commented Sep 20, 2016

Migrated from rt.perl.org#129321 (status was 'resolved')

Searchable as RT129321$

@p6rt
Copy link
Author

p6rt commented Sep 20, 2016

From @dogbert17

# tested with

dogbert@​dogbert-VirtualBox ~ $ perl6 -v
This is Rakudo version 2016.09-19-g8be36b1 built on MoarVM version 2016.09
implementing Perl 6.c

# the following two examples behave quite differently

dogbert@​dogbert-VirtualBox ~ $ perl6 -e 'my @​a = [1,[2,3],4]; dd
@​a.duckmap({ $_ ~~ Int ?? $_ !! Any })' # this works as expected
(1, (2, 3), 4)

dogbert@​dogbert-VirtualBox ~ $ perl6 -e 'my @​a = [1,[2,3],"a"]; dd
@​a.duckmap({ $_ ~~ Int ?? $_ !! Any })' # this will hang or return 'Memory
allocation failed; could not allocate xxxxxx bytes'

/dogbert17

@p6rt
Copy link
Author

p6rt commented Sep 23, 2016

From @zoffixznet

On Tue Sep 20 13​:54​:33 2016, jan-olof.hendig@​bredband.net wrote​:

# tested with

dogbert@​dogbert-VirtualBox ~ $ perl6 -v
This is Rakudo version 2016.09-19-g8be36b1 built on MoarVM version 2016.09
implementing Perl 6.c

# the following two examples behave quite differently

dogbert@​dogbert-VirtualBox ~ $ perl6 -e 'my @​a = [1,[2,3],4]; dd
@​a.duckmap({ $_ ~~ Int ?? $_ !! Any })' # this works as expected
(1, (2, 3), 4)

dogbert@​dogbert-VirtualBox ~ $ perl6 -e 'my @​a = [1,[2,3],"a"]; dd
@​a.duckmap({ $_ ~~ Int ?? $_ !! Any })' # this will hang or return 'Memory
allocation failed; could not allocate xxxxxx bytes'

/dogbert17

I see why the issue occurs, but have no idea what the correct behaviour should be.

The docs for .duckmap read "For undefined return values, duckmap will try to descend into the element if that element implements Iterable." but when would an undefined Iterable would ever be descendable?

The hang itself happens here​: https://github.com/rakudo/rakudo/blob/e12ebb9/src/core/metaops.pm#L685
The Any returned from your condition is undefined, so duckmap calls the block with it again, resulting in an infiniloop.

Based on the docs, a check for an Iterable is missing, but it feels wrong to me that we'd be attempting to "descend" into an undefined Iterable :S

@p6rt
Copy link
Author

p6rt commented Sep 23, 2016

The RT System itself - Status changed from 'new' to 'open'

@p6rt
Copy link
Author

p6rt commented Sep 24, 2016

From @dogbert17

Here's what I found in S32​:

deepmap

  multi method deepmap ( @​values​: Code *&expression --> Any )
  multi deepmap ( Code $expression, *@​values --> Any )

  Like map and duckmap, deepmap evaluates the expression for each of the values you give it. Unlike map and duckmap, an element is considered a value only if it does not do the Iterable role. If the element is iterable, the algorithm recurses to produce an identical structure to its input. Elements that are not iterable are considered leaf values and mapped through the supplied expression.

  Because deepmap is defined as a recursive implicit loop, loop controls apply only to the current level of the tree.

/dogbert17

-----Original Message-----
From​: Zoffix Znet via RT [mailto​:perl6-bugs-followup@​perl.org]
Sent​: den 23 september 2016 18​:39
To​: jan-olof.hendig@​bredband.net
Subject​: [perl #​129321] [BUG] deepmap can recurse indefinitely under some circumstances

On Tue Sep 20 13​:54​:33 2016, jan-olof.hendig@​bredband.net wrote​:

# tested with

dogbert@​dogbert-VirtualBox ~ $ perl6 -v This is Rakudo version
2016.09-19-g8be36b1 built on MoarVM version 2016.09 implementing Perl
6.c

# the following two examples behave quite differently

dogbert@​dogbert-VirtualBox ~ $ perl6 -e 'my @​a = [1,[2,3],4]; dd
@​a.duckmap({ $_ ~~ Int ?? $_ !! Any })' # this works as expected
(1, (2, 3), 4)

dogbert@​dogbert-VirtualBox ~ $ perl6 -e 'my @​a = [1,[2,3],"a"]; dd
@​a.duckmap({ $_ ~~ Int ?? $_ !! Any })' # this will hang or return
'Memory allocation failed; could not allocate xxxxxx bytes'

/dogbert17

I see why the issue occurs, but have no idea what the correct behaviour should be.

The docs for .duckmap read "For undefined return values, duckmap will try to descend into the element if that element implements Iterable." but when would an undefined Iterable would ever be descendable?

The hang itself happens here​: https://github.com/rakudo/rakudo/blob/e12ebb9/src/core/metaops.pm#L685
The Any returned from your condition is undefined, so duckmap calls the block with it again, resulting in an infiniloop.

Based on the docs, a check for an Iterable is missing, but it feels wrong to me that we'd be attempting to "descend" into an undefined Iterable :S

@p6rt
Copy link
Author

p6rt commented Sep 26, 2016

From @smls

Based on the docs, a check for an Iterable is missing, but it feels
wrong to me that we'd be attempting to "descend" into an undefined
Iterable :S

"Try to descend" probably means that it should call .list on the element to remove any Scalar container, and then iterate over it like any other `map` or `for` loop.

But I agree that it is not clear if the case of an undefined Iterable was considered by the authors of that design doc. There would be three possible ways to handle such an element​:

1) Simply allow `.list` to treat it as a list of one element, which may be technically the most consistent behavior but also gives the most weird/unexpected result​:

  ➜ say List.list.map({ $_ }).perl;
  (List,).Seq

2) Throw an error, like a normal top-level `map` would​:

  ➜ say List.map({ $_ }).perl;
  Invocant requires an instance of type List, but a type object was passed. Did you forget a .new?

3) Treat them as non-iterables, which would be another special case but possibly the most DWIM​:

  ➜ say List.perl
  List

@p6rt
Copy link
Author

p6rt commented Oct 6, 2016

From @zoffixznet

Tests added in Raku/roast@ce3050e

@p6rt
Copy link
Author

p6rt commented Oct 6, 2016

@zoffixznet - Status changed from 'open' to 'resolved'

@p6rt p6rt closed this as completed Oct 6, 2016
@p6rt p6rt added the testneeded label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant