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

Zig stage2 erroneous backwards branch evaluation/segfault with recursive function #13013

Open
jwhear opened this issue Sep 29, 2022 · 8 comments
Labels
bug Observed behavior contradicts documented or intended behavior frontend Tokenization, parsing, AstGen, Sema, and Liveness.
Milestone

Comments

@jwhear
Copy link
Contributor

jwhear commented Sep 29, 2022

Zig Version

0.10.0-dev.4198+5e0d8a435

Steps to Reproduce

Run zig test on the following code (heavily reduced to minimize surface area):

const std = @import("std");
const swap = std.mem.swap;

pub fn stablePartition(comptime T: type, slice: []T, predicate: fn(T) bool) i8 {
    if (slice.len == 0)
        return 0;
    _ = stablePartition(T, slice[1..], predicate);
    return 1;
}
test "stablePartition" {
    var items = [_]i8{0,1,2,3,4,5,6};
    _=stablePartition(i8, &items, isOdd);
}

fn isOdd(val: i8) bool {
    return val & 1 == 1;
}

By default this produces the following error:

min.zig:7:24: error: evaluation exceeded 1000 backwards branches
    _ = stablePartition(T, slice[1..], predicate);
        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
min.zig:7:24: note: use @setEvalBranchQuota() to raise the branch limit from 1000
min.zig:7:24: note: called from here (999 times)
min.zig:14:22: note: called from here
    _=stablePartition(i8, &items, isOdd);
      ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Using @setEvalBranchQuota(5000) as suggested causes the compiler to crash on my machine. Note that this is during compilation, not runtime.

Expected Behavior

Running zig test -fstage1 min.zig compiles and runs successfully with all tests passing.

Actual Behavior

Backwards branches error or segfault if the branch quota is increased. There appears to be some kind of infinite recursion, perhaps in type inference/resolution.

@jwhear jwhear added the bug Observed behavior contradicts documented or intended behavior label Sep 29, 2022
@Vexu
Copy link
Member

Vexu commented Sep 29, 2022

Duplicate of #12973

@Vexu Vexu marked this as a duplicate of #12973 Sep 29, 2022
@Vexu Vexu closed this as completed Sep 29, 2022
@topolarity
Copy link
Contributor

I'm not sure this is a duplicate of #12973, since stablePartition should only be instantiated once.

I think we're missing "error: parameter of type 'fn (i8) bool' must be declared comptime"

@jwhear The example works if you update the function pointer for stage2:

pub fn stablePartition(comptime T: type, slice: []T, predicate: std.meta.FnPtr(fn(T) bool)) i8

std.meta.FnPtr returns fn(...) for stage1, and *const fn(...) for stage2

@topolarity topolarity reopened this Sep 30, 2022
@jwhear
Copy link
Contributor Author

jwhear commented Sep 30, 2022

Ah, good catch. I distantly remember reading this in the transition guide a while ago, but had forgotten all about it. Using FnPtr should unblock my code, though the compiler bug remains.

@Vexu
Copy link
Member

Vexu commented Oct 1, 2022

This is then related to #13022 and probably caused by 8e4d0ae

@Vexu Vexu added the frontend Tokenization, parsing, AstGen, Sema, and Liveness. label Oct 1, 2022
@Vexu Vexu added this to the 0.10.0 milestone Oct 1, 2022
@Vexu Vexu added error message This issue points out an error message that is unhelpful and should be improved. bug Observed behavior contradicts documented or intended behavior and removed bug Observed behavior contradicts documented or intended behavior error message This issue points out an error message that is unhelpful and should be improved. labels Oct 3, 2022
@andrewrk andrewrk modified the milestones: 0.10.0, 0.10.1 Oct 12, 2022
@andrewrk andrewrk modified the milestones: 0.10.1, 0.11.0 Jan 10, 2023
@andrewrk andrewrk modified the milestones: 0.11.0, 0.11.1 Jul 20, 2023
@andrewrk andrewrk modified the milestones: 0.11.1, 0.12.0 Jan 29, 2024
@perillo
Copy link
Contributor

perillo commented Jan 30, 2024

@Vexu with 0.12.0-dev.2341+92211135 the example compiles correctly, without the need to use @setEvalBranchQuota.

@Vexu
Copy link
Member

Vexu commented Jan 30, 2024

The original example works when converting the test into an exported function but the version with a test hits an assertion failure.

@Vexu Vexu modified the milestones: 0.12.0, 0.13.0 Jan 30, 2024
@perillo
Copy link
Contributor

perillo commented Jan 30, 2024

The original example works when converting the test into an exported function but the version with a test hits an assertion failure.

Strange, since I ran zig test on the original example, getting

All 1 tests passed.

I'm on Linux.

@Vexu
Copy link
Member

Vexu commented Jan 30, 2024

My mistake, I wasn't using master branch. On a positive note, I figured out why #18712 isn't passing CI. Nope.

It does compile now but probably shouldn't as noted by topolarity above.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Observed behavior contradicts documented or intended behavior frontend Tokenization, parsing, AstGen, Sema, and Liveness.
Projects
None yet
Development

No branches or pull requests

5 participants