Remove goto

Please everyone post links to your zig code that uses goto, so we won't remove the feature. Alternatively, post links to C code that uses goto, so we can assess if there's a more zig-like way to do it, or if goto is really the best solution for those cases.

I want real actual code here, not pseudocode examples. Please link to open source projects.

This discussion started in #346.

For reference, here's how you can do without goto:

use defer for the try-finally pattern.
use %defer for the cleanup-on-error pattern.
use while (true) { switch (state) { ... for cases where you want computed goto. Here's some existing discussion on that: labeled loops, labeled break, labeled continue #346 (comment)
use labeled break to jump forward and labeled continue to jump backward, placing loops where necessary. This is the plan for the C-to-Zig translator. This is the ugliest solution, but should always work when all else fails.

Unless there are local functions with access to parent stack defer cannot do the following:

if (error condition) goto error;
...
if (some other error condition) goto error;
...
if (yet another error condition) goto error;
...

error:
   // nontrivial error handling code

defer would need to duplicate all the error handling code, or one has to create a top level function and pass needed parameters there.

Your example code can be implemented with defer like this:

fn foo() -> %void {
    %defer {
        // nontrivial error handling code
    };
    %return errorCondition();
    %return someOtherErrorCondition();
    %return yetAnotherErrorCondition();
}

Here's another way to write it:

fn foo() {
    e: {
        if (error_condition) return :e;
        if (some_other_error_condition) return :e;
        if (yet_another_error_condition) return :e;
        return;
    }
    // nontrivial error handling code
}

@andrewrk

@andrewrk: these two examples are syntactically very tricky. They move the simple and explicit error checking from its proper place to some unnatural location, or they require creating additional functions (and inventing more names).

They are replacing the most simple and readable flow

do_A();
if (wrong) handle error
do_B();
if (wrong) handle error
do_C();
if (wrong) handle error

with something strange.

The examples also assume that everyone wants to return Zig error when the function gets into internal error situation handling business. The function may try to return some valid substitute, not the error. This also makes %defer not full replacement for traditional error handling.

(I am also unsure whether the examples would work, because of the need to access local variables.)

Here's another real code advantage of goto based error handling:

if (error condition) goto error1;
...
if (some other error condition) goto error2;
...
if (yet another error condition) goto error3;
...

error3:
  // the least common part of error handling
  ...
error2: // fallthrough  
  // error handling code for some scenarios
  ...
error1: // fallthrough
   // error handling code common for all scenarios
    ...

To implement such feature (shared error handling code) is impossible w/o goto (except for certain Forth dialects which offer so called "headless functions", where it is possible to jump inside of a function).

They move the simple and explicit error checking from its proper place to some unnatural location

The second one has the same source locations as your pseudocode.

The examples also assume that everyone wants to return Zig error

Where is the Zig error in the second example?

Please respect the OP's request:

I want real actual code here, not pseudocode examples. Please link to open source projects.

@andrewrk

@andrewrk:

The second one has the same source locations as your pseudocode.

I should had comment the examples separately. The second example is still tricky and creates named block and adds new level of indentation.

These are two local level problems I try to minimize: the need to invent names and the excessive indentation. (That's why I proposed Zig having elif or anonymous tuples and enums.)

Where is the Zig error in the second example?

There's not.

real code

The 3pp code which uses goto in a restricted way (handling errors down the flow) is DL malloc ( ftp://g.oswego.edu/pub/misc/malloc.c ), LZ4 compressor ( https://github.com/lz4/lz4/blob/dev/lib/lz4.c ) or SQLite. These libraries use fairly long functions and goto is the least intrusive way to handle errors (I guess).

A non-simple use is quicksort implementation in MSVC stdlib, it jumps up. This is IME quite rare occurence.

I do not write open source. I use goto occasionally, only for error handling, and only going down. It never caused problems for me.

Btw, the second example could be rewritten as:

fn foo() {
    while (true)
        if (error_condition) break;
        if (some_other_error_condition) break;
        if (yet_another_error_condition) break;
        return;
    }
    // nontrivial error handling code
}

No need for blocks and one artificial name less, but I would not like it either. Unlike occasional goto such trick is also not present in C codebases I know.

I wrote this code today. Made me regret that there is no goto in javascript.

        var file = FileUtils.getFile("Home", comment_path_from.slice(0,1));
        if ( file.exists() ) file = FileUtils.getFile("Home", comment_path_from.slice(0,2));
        if ( file.exists() ) file = FileUtils.getFile("Home", comment_path_from.slice(0,3));
        if ( file.exists() ) file = FileUtils.getFile("Home", comment_path_from.slice(0,4));
        if ( file.exists() ) file = FileUtils.getFile("Home", comment_path_from.slice(0,5));

        if (! file.exists() ) {
            hijack.innerHTML = "NO COMMENTS FOUND"
        } else {

In the worst case it calls file.exists() 4 extra times. Have to create a new variable, but I'm too lazy for that. And I doubt any compiler will optimize it properly.

I honestly don't understand why you want to remove goto so much.

re2c looked like a spam, but I guess it's not. It uses goto heavily, is it?

pluto439, I am not convinced this JavaScript is a good use case. Why don't you just do a loop and use "break"?

Just to add, that solution specifically would be further improved by #8220:

const initial_state = ;
sw: switch (@as(u3, 0)) {
    0 => {
        // logic A
        continue :sw if (condition) 1 else 2;
    },
    1 => {
        // logic B
        continue :sw if (condition2.*) 3 else 0;
    },
    2 => {
        // logic D
        continue :sw 4;
    },
    3 => {
        // logic I
        continue :sw 4;
    },
    4 => {
        // logic C
        continue :sw 2;
    },
    else => unreachable,
}

For reference, here the code I am working on: https://zig.godbolt.org/z/sjzYj7nGG. It is not cleaned up very much yet but what I am doing is trying to find the most optimal way to implement my DynSDT data structure: https://validark.github.io/DynSDT

You can see I have multiple implementations of the topKCompletionsToPrefix function, and I am experimenting with different techniques like using sentinels to avoid boundary checks, storing the data in plain variables, using SIMD techniques, etc. Also I am looking at what the right balance is between inlining more loop iterations where possible or condensing things. A lot of fun stuff, but if it looks messy or unpolished, that is why.

The function topKCompletionsToPrefix on line 806 is the code I was working on most recently. I put some comments in there describing the assembly generation I am seeing that seems suboptimal. Line 9504 in the assembly is what I was alluding to in my previous comment. Although it now is in a different register:

        mov     bpl, 1
        test    bpl, 1
        jne     .LBB16_44
        jmp     .LBB16_50

The goto jump that I was hoping for has to do with do_cur_insertion. This code is what I mean:

if (depq_len == 10 - k and next_i != NULL) {
    do_cur_insertion = false;
    break; // this should skip the if (do_cur_insertion) statement in the following loop
}

It should jump to the second half of this loop:

while (true) {
    if (do_cur_insertion) {
        // ... 
    }

    // please jump here!
    do_cur_insertion = true;

    if (next_i != NULL) {
        // ...
    }

    depq_len -%= 1;
    if (depq_len == std.math.maxInt(@TypeOf(depq_len))) return @intCast(u4, k);
    cur_i = depq[depq_len];
}

Instead, it jumps to code that checks test bpl, 1 (bpl is do_cur_insertion), followed by je .LBB16_50 to potentially skip over the if (do_cur_insertion) section we are guaranteed to skip when coming from the zig source above. Then the end of my second loop ends as shown in the asm above, with writing a 1 to bpl and then testing to see if bpl is 1. Ideally, the compiler should realize that the program never actually needs to check do_cur_insertion at all, so long as we jump to the place after the if (do_cur_insertion) statement from the aforementioned break expression. From then on, we should always run that code when we loop back to the top of the while loop.

More complaints about LLVM

Oddly enough, in that same function, not related to the issue of goto, this code:

k += 1;
if (k == 10) return 10;

translates to this assembly:

        inc     al
        cmp     al, 10
        je      .LBB16_45
        ; ... stuff
.LBB16_45:
        mov     al, 10
        jmp     .LBB16_2

Randomly scrolling through the assembly, I found another example:

        cmp     r11b, 4
        jne     .LBB16_38 ; if (r11b != 4)
        jmp     .LBB16_41 ; if (r11b == 4)

        ; ...
; this is only referenced once in the assembly, so it was generated specifically to go with the previous jmp!
.LBB16_41:
        vpextrd esi, xmm0, 3
        mov     r11b, 4 ; r11b = 4 😔

Maybe this is just a problem in general for LLVM? The emit is also pretty temperamental. Changing the comments in the code can lead to instructions changing order, which is odd (when the instruction order does not matter). My first assembly in this comment sometimes gets one of the other mov instructions from the function logic under its initial mov instruction. It also seems to do some optimizations sometimes but other times it won't. Consider this code from my original version of the first while loop:

if (depq_len == 0) return k;
depq_len -= 1;

This gives me this emit:

.LBB16_38:
        test    r11b, r11b
        je      .LBB16_2
.LBB16_39:
        dec     r11b

However, this same code in the second while loop gives me this emit:

sub     r11b, 1
jb      .LBB16_2

I can ask more forcefully for this optimization by using this code instead:

depq_len -%= 1;
if (depq_len == std.math.maxInt(@TypeOf(depq_len))) return k;

Yes, this is something of a micro-optimization, but it is still weird to me that if you use the exact same code to check if (depq_len == 0) in the second while loop, it gives me the more optimized asm with sub r11b, 1, followed by jb .LBB16_2, but it won't do the same in the first while loop. So it will do the optimization only sometimes, even though the circumstances are roughly the same and the state of depq_len does not matter when returning from the function happens.

Update: I tried changing the code to look more like a state machine by using an enum rather than a boolean, and it translated the end of each block to this instead:
https://zig.godbolt.org/z/1YYxMo9vE

    xor     r9b, 1
    jmp     .LBB16_43

; ...

.LBB16_43:
    test    r9b, 1
    je      .LBB16_51

At the moment, it might be impossible to achieve what I am trying to do. If anyone wants to take a crack at it, I would be happy to be shown there is a way to get the optimized output I am looking for. Otherwise, maybe #8220 will guarantee the jumps I am trying to do?

I also tried implementing this via tail calls: https://zig.godbolt.org/z/Gj9qeahMK
It gave me the jumps I was hoping for, but isn't the cleanest solution in terms of Zig code, IMO. I think Zig should be capable of doing this within a single function. I'm fine with using this solution for the time being, though.

This is a good example of idiomatic goto in a VM dispatch loop: https://github.com/sqmedeiros/lpeglabel/blob/master/lplvm.c

It only stands as an argument for goto if there isn't a better way to write it in Zig.

Is there?

@mnemnion

@mnemnion

The goto fails are easily modeled with either function calls or #8220 depending on specifics. goto pushcapture, either function calls or combining the switch cases.

I really don't see any logic in that file which has a compelling use of goto.

(Regardless, I should note that this part of Zig is essentially as decided as it gets; goto is not coming back.)

I don't have opinions about whether Zig should, or should not, have goto.

I saw this in the first comment:

Please everyone post links to your zig code that uses goto, so we won't remove the feature. Alternatively, post links to C code that uses goto, so we can assess if there's a more zig-like way to do it, or if goto is really the best solution for those cases.

And then read a lot of abstract discussion, with relatively few real-life examples of nontrivial goto, where it might be challenging to produce comparable performance without using the construct. It's clear that the most common pattern, which is a jump to cleanup code, isn't necessary in Zig.

Here is another example, also from the Lua team, where eight gotos are used to structure a VM dispatch loop. Lua is renowned for its relative speed and very small binary. They're using goto because (in C) they need to.

I'm evaluating Zig for writing a VM, so I'm keenly interested in whether it's possible to get the same performance, and a clearer instruction flow, using what Zig has now. If it is, why would anyone want goto? If it isn't, that's a marked lack in a language like Zig, which should certainly be usable to craft an optimal dispatch loop for a VM.

You might look at the question this way: if someone replies with a detailed answer, and demonstration that the machine code generated by a Zig version is broadly equivalent, that's conclusive: Zig doesn't need goto, because there aren't other cases where it's used to good effect. Providing branchless state-machine effects in a hot dispatch loop is it, that's what goto is good for in C, other than making up for some defects which Zig has already remedied.

But I did read all the comments, and code like this wasn't addressed (a related question about computed gotos was). So, given the specific call to action in the first post, I thought it was appropriate to resurrect the discussion.

@mlugg

@mlugg's answer is still applicable. #8220 would allow you to do arbitrary jumps without the normal footguns associated with goto. Right now, you can only do it with tail call optimization, which is a massive pain and doesn't work on some platforms (iirc WASM). Right now, you can write your VM as a regular switch statement, and once #8220 comes out you can switch over.

Otherwise, you might want to use DynAsm or something that allows you to have precise control over register allocation if you really want to write a performant VM. A high level language + LLVM, by itself, is not going to be the ideal choice for a VM if you want to beat LuaJIT.

If you're interested in more ideas, I'd look at https://github.com/luajit-remake/luajit-remake

Thanks for the pointer to that LuaJIT project, definitely the sort of thing I'm interested in generally!

Custom ASM-enhanced VMs have their place, as does tracing. There is also a place for portable platform-independent VMs which perform well: so Lua, not LuaJIT.

Reading #8220 more closely, I'm beginning to see how it would more than likely cover the parts of a VM's state machine which can't be expressed in C without goto or compromises. "You can't yet, but we know that and have a better solution on the roadmap" is a reasonable answer to my question. Thanks for taking the time to reply.

I'd like to note that the use case you bring up is actually very important to the compiler itself. The main loop of semantic analysis in the Zig compiler - our primary bottleneck excluding LLVM - is essentially a VM instruction dispatch loop, which in fact largely motivated #8220 in the first place. Similar loops also exist in all of our code generation backends. So emitting optimal assembly here is definitely something we want to make sure we can do!

(Incidentally, I am actively working on #8220, and expect to have a PR up within days.)

Late to the party, but I think I have an interesting use case for goto in C to contribute: at the end of a switch-case branch to jump to a handful of different 'epilog blocks' (this is code-generated):

https://github.com/floooh/chips/blob/bd1ecff58337574bb46eba5e7e16937899360e56/chips/z80.h#L4706-L4767

The compiler output is exactly as you'd expect (in native code at least): the code branches via a jump-table, and the end of each case-branch has a direct jump to one of the three epilog blocks. Empty case branches are "short-cutted" and directly have the address of the goto target in the jump table.

I didn't inspect WASM output, but performance is close to native code, so I guess it's fine.

Here's a blogpost about how that emulator works in general (only the first couple of sections are interesting): https://floooh.github.io/2021/12/17/cycle-stepped-z80.html

PS: as a special case, the _wait() macro (which implements the Z80's WAIT handling) jumps out of the middle of a switch-case branch to the NMI edge-detection epilog block:

https://github.com/floooh/chips/blob/bd1ecff58337574bb46eba5e7e16937899360e56/chips/z80.h#L1805

...think of it as a giant state machine, not unlike the result of an async/await code transformation.

PPS: I'm planning to do some emulator experiments in Zig soon-ish, and I hope I can somehow emulate this construct without a C-like goto (maybe with nested named blocks and labelled break?) - in any case I kinda like how straightforward the C version is for this sort of low-level "outside-the-box" contraption :)

@floooh

(@floooh) PPS: I'm planning to do some emulator experiments in Zig soon-ish, and I hope I can somehow emulate this construct without a C-like goto (maybe with nested named blocks and labelled break?) - in any case I kinda like how straightforward the C version is for this sort of low-level "outside-the-box" contraption :)

I ported a small amount of the code for you, just enough to get the point across. Here is what I came up with:

fn z80_tick(cpu: *z80_t, pins_: u64) u64 {
    var pins = pins_ & ~(Z80_CTRL_PIN_MASK | Z80_RETI);

    sw: switch (@as(enum { start, fetch_next, step_next, track_int_bits }, .start)) {
        .start => switch (cpu.step) {
            1506 => {
                if (pins & Z80_WAIT) continue :sw .track_int_bits;
                cpu.iff1 = false;
                continue :sw .step_next;
            },
            1515 => continue :sw .step_next,
            1516 => continue :sw .fetch_next,
        },

        .fetch_next => {
            pins = cpu.fetch(pins);
            continue :sw .step_next;
        },

        .step_next => {
            cpu.step += 1;
            continue :sw .track_int_bits;
        },

        .track_int_bits => {
            // track NMI 0 => 1 edge and current INT pin state, this will track the
            // relevant interrupt status up to the last instruction cycle and will
            // be checked in the first M1 cycle (during _fetch)
            const rising_nmi: u64 = (pins ^ cpu.pins) & pins; // NMI 0 => 1
            cpu.pins = pins;
            cpu.int_bits = ((cpu.int_bits | rising_nmi) & Z80_NMI) | (pins & Z80_INT);
        },
    }
}

With the new labeled-switch-continue feature, you can now get the goto control flow that you want!

@Validark

@Validark wow that looks interesting, I hadn't even considered such an "outer switch statement", very neat!

In the meantime I used a slightly different approach using 'labeled break':

https://github.com/floooh/chipz/blob/fdd72d54e3da85604c70ee062e09780437a48d31/src/chips/z80.zig#L1196-L1209

...basically using nested labeled scope blocks, and the labeled break at the end of switch statement controls which 'inner' scope blocks to skip. It works, but I like your approach more. The labeled continue approach immediately looks very useful for building all sorts of 'switch-based state machines' :)

Amazing how much complexity you have to throw at your code just to be able to avoid goto. Is it really worth it?

IMHO the above example isn't any more complex than the original goto-based code in C, and while I'm not a 'goto considered harmful zealot' myself, the C/C++ goto does have a couple of problems that are worth fixing (like being able to skip variable declarations and initializations).

In the long run there might even be some advantages if the compilation target is a 'structured bytecode' like WASM (but that's speculation on my side).

@floooh

@floooh Yes, in this case you could use labeled_breaks as well.

fn z80_tick(cpu: *z80_t, pins_: u64) u64 {
    var pins = pins_ & ~(Z80_CTRL_PIN_MASK | Z80_RETI);

    track_int_bits: {
        step_next: {
            fetch_next: switch (cpu.step) {
                1506 => {
                    if (pins & Z80_WAIT) break :track_int_bits;
                    cpu.iff1 = false;
                    break :step_next;
                },
                1515 => break :step_next,
                1516 => break :fetch_next,
            }

            pins = cpu.fetch(pins);
        }
        cpu.step += 1;
    }

    // track NMI 0 => 1 edge and current INT pin state, this will track the
    // relevant interrupt status up to the last instruction cycle and will
    // be checked in the first M1 cycle (during _fetch)
    const rising_nmi: u64 = (pins ^ cpu.pins) & pins; // NMI 0 => 1
    cpu.pins = pins;
    cpu.int_bits = ((cpu.int_bits | rising_nmi) & Z80_NMI) | (pins & Z80_INT);
}

However, I think this code is more confusing as written above, since I am labeling the block with what happens after it, which doesn't make sense. With labeled breaks you are saying what to break out of, whereas with goto/labeled-continue we are saying what to jump to. If I thought of it as "we can now stop X process", I would write it as a "break", but if I thought of it as "jump to X process", I would write it as a labeled continue. Also the labeled continue version is significantly more powerful, and can express arbitrary control flows that cannot be expressed with the cascading blocks strategy.

Navigation Menu

Repository navigation

Remove goto #630

41 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Remove goto #630

Description

Activity

PavelVozenilek commented on Nov 28, 2017

andrewrk commented on Nov 28, 2017

andrewrk commented on Nov 28, 2017

PavelVozenilek commented on Nov 29, 2017

andrewrk commented on Nov 29, 2017

PavelVozenilek commented on Nov 29, 2017

PavelVozenilek commented on Nov 29, 2017

pluto439 commented on Dec 4, 2017

pluto439 commented on Dec 4, 2017

jido commented on Dec 4, 2017

41 remaining items

InKryption commented on Nov 10, 2022

Validark commented on Nov 11, 2022

Validark commented on Nov 11, 2022

mnemnion commented on Apr 22, 2024

mlugg commented on Apr 22, 2024

mnemnion commented on Apr 25, 2024

Validark commented on Apr 25, 2024

mnemnion commented on Apr 25, 2024

mlugg commented on Apr 25, 2024

floooh commented on May 15, 2024

Validark commented on Sep 25, 2024

floooh commented on Sep 27, 2024

clausecker commented on Sep 27, 2024

floooh commented on Sep 27, 2024

Validark commented on Sep 27, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions