roc-lang / roc

A fast, friendly, functional language.
https://roc-lang.org
Universal Permissive License v1.0
3.86k stars 284 forks source link

Compiler bug when running reverse polish notation calculator #3827

Open KilianVounckx opened 1 year ago

KilianVounckx commented 1 year ago

This bug could be issued already, but the compiler told me to file a new issue, so I will :)

I translated the RPN calculator from learnyouahaskell to roc. It is not the most performant or idiomatic translation, but it was a first try. Here is the code:

app "echo"
    packages { pf: "cli-platform/main.roc" }
    imports [pf.Stdin, pf.Stdout, pf.Task.{ Task }, pf.Program.{ Program, ExitCode }]
    provides [main] to pf

main : Program
main = Program.noArgs mainTask

mainTask : Task * [] [Write [Stdout], Read [Stdin]]
mainTask =
    Task.forever
        (
            _ <- Task.await (Stdout.line "enter an expression:")
            line <- Task.await Stdin.line
            line |> solveRpn |> Num.toStr |> Stdout.line
        )

solveRpn : Str -> F64
solveRpn = \s -> s
    |> Str.split " "
    |> List.walk [] step
    |> List.first
    |> Result.withDefault 0

step : List F64, Str -> List F64
step = \stack, input ->
    binOp : List F64, (F64, F64 -> F64) -> List F64
    binOp = \s, f ->
        y = s |> List.last |> Result.withDefault 0
        x = s |> List.dropLast |> List.last |> Result.withDefault 0
        s |> List.dropLast |> List.dropLast |> List.append (f x y)

    when input is
        "+" -> binOp stack Num.add
        "-" -> binOp stack Num.sub
        "*" -> binOp stack Num.mul
        "/" -> binOp stack Num.div
        s -> stack |> List.append (s |> Str.toF64 |> Result.withDefault 0)

After running RUST_BACKTRACE=full roc run, I get the following output:

🔨 Rebuilding host...
An internal compiler expectation was broken.
This is definitely a compiler bug.
Please file an issue here: https://github.com/roc-lang/roc/issues/new/choose
thread 'main' panicked at 'Undefined Symbol in relocation, (+6936, Relocation { kind: Relative, encoding: Generic, size: +20, target: Symbol(SymbolIndex(+248)), addend: +fffffffffffffffc, implicit_addend: false }): Ok(Symbol { name: "", address: +0, size: +0, kind: Section, section: Section(SectionIndex(+9)), scope: Compilation, weak: false, flags: Elf { st_info: +3, st_other: +0 } })', crates/linker/src/lib.rs:2708:25
stack backtrace:
   0:     0x55e774aaf106 - std::backtrace_rs::backtrace::libunwind::trace::h22893a5306c091b4
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/../../backtrace/src/backtrace/libunwind.rs:93:5
   1:     0x55e774aaf106 - std::backtrace_rs::backtrace::trace_unsynchronized::h29c3bc6f9e91819d
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x55e774aaf106 - std::sys_common::backtrace::_print_fmt::he497d8a0ec903793
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:66:5
   3:     0x55e774aaf106 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h9c2a9d2774d81873
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:45:22
   4:     0x55e773f8c52c - core::fmt::write::hba4337c43d992f49
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/core/src/fmt/mod.rs:1194:17
   5:     0x55e774aaa50f - std::io::Write::write_fmt::heb73de6e02cfabed
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/io/mod.rs:1655:15
   6:     0x55e774ab0cf5 - std::sys_common::backtrace::_print::h63c8b24acdd8e8ce
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:48:5
   7:     0x55e774ab0cf5 - std::sys_common::backtrace::print::h426700d6240cdcc2
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:35:9
   8:     0x55e774ab0cf5 - std::panicking::default_hook::{{closure}}::hc9a76eed0b18f82b
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:295:22
   9:     0x55e774ab0a6d - std::panicking::default_hook::h2e88d02087fae196
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:314:9
  10:     0x55e774ab11d5 - std::panicking::rust_panic_with_hook::habfdcc2e90f9fd4c
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:698:17
  11:     0x55e774ab10e4 - std::panicking::begin_panic_handler::{{closure}}::he054b2a83a51d2cd
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:588:13
  12:     0x55e774aaf634 - std::sys_common::backtrace::__rust_end_short_backtrace::ha48b94ab49b30915
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:138:18
  13:     0x55e774ab0e3d - rust_begin_unwind
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:584:5
  14:     0x55e773dd49b3 - core::panicking::panic_fmt::h366d3a309ae17c94
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/core/src/panicking.rs:143:14
  15:     0x55e7746279ea - roc_linker::surgery_elf::h29c5dc23e9abb58c
  16:     0x55e77461ca96 - roc_linker::surgery::hff07d7f6f7d52b4a
  17:     0x55e774610083 - roc_linker::link_preprocessed_host::h3809fe0eed793818
  18:     0x55e7742fbaeb - roc_cli::build::build_file::ha61b316ffe2aafac
  19:     0x55e77430a656 - roc_cli::build::haddea3af519b4977
  20:     0x55e77416d31e - roc::main::hdd05643fe19e55ff
  21:     0x55e77416a8d3 - std::sys_common::backtrace::__rust_begin_short_backtrace::hb1a2ee42dbb3fc9f
  22:     0x55e77416a8f1 - std::rt::lang_start::{{closure}}::h7b8d975ac0de2248
  23:     0x55e774aa39d2 - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once::had4f69b3aefb47a8
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/core/src/ops/function.rs:259:13
  24:     0x55e774aa39d2 - std::panicking::try::do_call::hf2ad5355fcafe775
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:492:40
  25:     0x55e774aa39d2 - std::panicking::try::h0a63ac363423e61e
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:456:19
  26:     0x55e774aa39d2 - std::panic::catch_unwind::h18088edcecb8693a
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panic.rs:137:14
  27:     0x55e774aa39d2 - std::rt::lang_start_internal::{{closure}}::ha7dad166dc711761
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/rt.rs:128:48
  28:     0x55e774aa39d2 - std::panicking::try::do_call::hda0c61bf3a57d6e6
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:492:40
  29:     0x55e774aa39d2 - std::panicking::try::hbc940e68560040a9
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:456:19
  30:     0x55e774aa39d2 - std::panic::catch_unwind::haed0df2aeb3fa368
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panic.rs:137:14
  31:     0x55e774aa39d2 - std::rt::lang_start_internal::h9c06694362b5b80c
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/rt.rs:128:20
  32:     0x55e774171192 - main
  33:     0x7f97794e6237 - __libc_start_call_main
  34:     0x7f97794e62f5 - __libc_start_main_impl
  35:     0x55e773ef2bc1 - _start
                               at /build/glibc-2.34/csu/../sysdeps/x86_64/start.S:116
  36:                0x0 - <unknown>

Running roc check does not give any errors, Running roc build gives the same error.

Running roc format gives this error:

thread 'main' panicked at 'not yet implemented: Format string literal: PlainLine("+")', crates/compiler/fmt/src/pattern.rs:150:17
stack backtrace:
   0:     0x556a8a224106 - std::backtrace_rs::backtrace::libunwind::trace::h22893a5306c091b4
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/../../backtrace/src/backtrace/libunwind.rs:93:5
   1:     0x556a8a224106 - std::backtrace_rs::backtrace::trace_unsynchronized::h29c3bc6f9e91819d
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x556a8a224106 - std::sys_common::backtrace::_print_fmt::he497d8a0ec903793
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:66:5
   3:     0x556a8a224106 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h9c2a9d2774d81873
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:45:22
   4:     0x556a8970152c - core::fmt::write::hba4337c43d992f49
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/core/src/fmt/mod.rs:1194:17
   5:     0x556a8a21f50f - std::io::Write::write_fmt::heb73de6e02cfabed
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/io/mod.rs:1655:15
   6:     0x556a8a225cf5 - std::sys_common::backtrace::_print::h63c8b24acdd8e8ce
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:48:5
   7:     0x556a8a225cf5 - std::sys_common::backtrace::print::h426700d6240cdcc2
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:35:9
   8:     0x556a8a225cf5 - std::panicking::default_hook::{{closure}}::hc9a76eed0b18f82b
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:295:22
   9:     0x556a8a225a6d - std::panicking::default_hook::h2e88d02087fae196
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:314:9
  10:     0x556a8a2261d5 - std::panicking::rust_panic_with_hook::habfdcc2e90f9fd4c
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:698:17
  11:     0x556a8a2260e4 - std::panicking::begin_panic_handler::{{closure}}::he054b2a83a51d2cd
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:588:13
  12:     0x556a8a224634 - std::sys_common::backtrace::__rust_end_short_backtrace::ha48b94ab49b30915
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/sys_common/backtrace.rs:138:18
  13:     0x556a8a225e3d - rust_begin_unwind
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:584:5
  14:     0x556a895499b3 - core::panicking::panic_fmt::h366d3a309ae17c94
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/core/src/panicking.rs:143:14
  15:     0x556a89c45521 - roc_fmt::pattern::<impl roc_fmt::annotation::Formattable for roc_parse::ast::Pattern>::format_with_options::h1267d8b68931ea8a
  16:     0x556a89c3c994 - roc_fmt::expr::<impl roc_fmt::annotation::Formattable for roc_parse::ast::Expr>::format_with_options::hc71663cc72938a41
  17:     0x556a89c375d8 - roc_fmt::def::<impl roc_fmt::annotation::Formattable for roc_parse::ast::Defs>::format_with_options::h7a40ae520ab70470
  18:     0x556a89a73fe9 - roc_cli::format::format::hab4acaed20fdc19b
  19:     0x556a898e3f3d - roc::main::hdd05643fe19e55ff
  20:     0x556a898df8d3 - std::sys_common::backtrace::__rust_begin_short_backtrace::hb1a2ee42dbb3fc9f
  21:     0x556a898df8f1 - std::rt::lang_start::{{closure}}::h7b8d975ac0de2248
  22:     0x556a8a2189d2 - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once::had4f69b3aefb47a8
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/core/src/ops/function.rs:259:13
  23:     0x556a8a2189d2 - std::panicking::try::do_call::hf2ad5355fcafe775
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:492:40
  24:     0x556a8a2189d2 - std::panicking::try::h0a63ac363423e61e
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:456:19
  25:     0x556a8a2189d2 - std::panic::catch_unwind::h18088edcecb8693a
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panic.rs:137:14
  26:     0x556a8a2189d2 - std::rt::lang_start_internal::{{closure}}::ha7dad166dc711761
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/rt.rs:128:48
  27:     0x556a8a2189d2 - std::panicking::try::do_call::hda0c61bf3a57d6e6
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:492:40
  28:     0x556a8a2189d2 - std::panicking::try::hbc940e68560040a9
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panicking.rs:456:19
  29:     0x556a8a2189d2 - std::panic::catch_unwind::haed0df2aeb3fa368
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/panic.rs:137:14
  30:     0x556a8a2189d2 - std::rt::lang_start_internal::h9c06694362b5b80c
                               at /rustc/fe5b13d681f25ee6474be29d748c65adcd91f69e/library/std/src/rt.rs:128:20
  31:     0x556a898e6192 - main
  32:     0x7f1868040237 - __libc_start_call_main
  33:     0x7f18680402f5 - __libc_start_main_impl
  34:     0x556a89667bc1 - _start
                               at /build/glibc-2.34/csu/../sysdeps/x86_64/start.S:116
  35:                0x0 - <unknown>

I understand the language is new, and there are still a lot of bugs needed to be fixed. I just hope this issue can help someone fix one bug!

ayazhafiz commented 1 year ago

The format and run panics are likely separate bugs. Can you try passing --linker=legacy to roc run and see if that helps?

KilianVounckx commented 1 year ago

It works with the --linker=legacy flag. The compile time is much longer now though. Thanks for the quick response.

ayazhafiz commented 1 year ago

cc @bhansconnect who has implemented the default linker.

bhansconnect commented 1 year ago

I don't have access to my x86 machine for a few days, but will look into this once I do.

folkertdev commented 1 year ago

I did some digging. The relocation in question is

[crates/linker/src/lib.rs:2788] &rel = (
    26934,
    Relocation {
        kind: Relative,
        encoding: Generic,
        size: 32,
        target: Symbol(
            SymbolIndex(
                587,
            ),
        ),
        addend: -4,
        implicit_addend: false,
    },
)

That symbol is

[crates/linker/src/lib.rs:2788] app_obj.symbol_by_index(index) = Ok(
    Symbol {
        name: "",
        address: 0,
        size: 0,
        kind: Section,
        section: Section(
            SectionIndex(
                9,
            ),
        ),
        scope: Compilation,
        weak: false,
        flags: Elf {
            st_info: 3,
            st_other: 0,
        },
    },
)

The symbol name is empty, and that means we can't find it in our hashmap of functions which we know how to relocate.

Looking at the symbol table:

   583: 0000000000001d6c    18 OBJECT  LOCAL  DEFAULT    8 __unnamed_432
   584: 0000000000001d7e    17 OBJECT  LOCAL  DEFAULT    8 __unnamed_433
   585: 0000000000001d8f    18 OBJECT  LOCAL  DEFAULT    8 __unnamed_434
   586: 0000000000001da1    18 OBJECT  LOCAL  DEFAULT    8 __unnamed_435
   587: 0000000000000000     0 SECTION LOCAL  DEFAULT    9
   588: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND roc_alloc
   589: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND memcpy
   590: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND memset
   591: 0000000000003140   486 FUNC    WEAK   DEFAULT    2 __muloti4

Our symbol 587 is of kind SECTION, which is odd. It is in secton 9, which is

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            0000000000000000 000000 000000 00      0   0  0
  [ 1] .strtab           STRTAB          0000000000000000 01ce50 00395a 00      0   0  1
  [ 2] .text             PROGBITS        0000000000000000 000040 00c3b8 00  AX  0   0 16
  [ 3] .rela.text        RELA            0000000000000000 018440 0014b8 18     14   2  8
  [ 4] .rodata.cst16     PROGBITS        0000000000000000 00c400 000100 10  AM  0   0 16
  [ 5] .rodata.cst8      PROGBITS        0000000000000000 00c500 0000a0 08  AM  0   0  8
  [ 6] .rodata           PROGBITS        0000000000000000 00c5a0 003448 00   A  0   0  8
  [ 7] .rela.rodata      RELA            0000000000000000 0198f8 0001f8 18     14   6  8
  [ 8] .rodata.str1.1    PROGBITS        0000000000000000 00f9e8 001dd8 01 AMS  0   0  1
  [ 9] .data.rel.ro      PROGBITS        0000000000000000 0117c0 002880 00  WA  0   0  8
  [10] .rela.data.rel.ro RELA            0000000000000000 019af0 002880 18     14   9  8

This is where my (current) knowledge stops.

bhansconnect commented 1 year ago

So this definitely seems to be the same root issue as #3609. The fix would theoretically be what is mentioned here: https://github.com/roc-lang/roc/issues/3609#issuecomment-1193179430.

In the case the cause is specifically Num.toStr on floats. If you remove that function and just replace it with something silly like (\x -> if x > 0 then "+" else "-"), it will compile with the surgical linker.

What this really means is that the zig builtin creates a constant pointer to constant data. The surgical linker can not yet deal with constant pointers. They need to be converted to a relocation that will happen at run time. Before run time, we don't know the correct address space to setup pointers correctly. Theoretically, we could change the zig builtin in some way to fix this, but really the root issue needs to be addressed.

Anything nested and constant will use section like .data.rel.ro and we currently don't have code to deal with relocations for that.