List.walk corrupts memory when using another list as state

Qqwy commented 2 years ago

When having two lists, and mutating one while walking over the other, there are situations where elements in the output list might point to uninitialized memory.

Minimal counterexample:

app "listwalkbug"
    packages { pf: "cli-platform" }
    imports [pf.Stdout, pf.Task.{ Task, await, loop, succeed }]
    provides [main] to pf

main =
     list1 = ["Camembert", "Brie", "Roquefort"]
     list2 = ["Brie"]

     badList =
         # This implementation works correctly:
         # List.set list1 1 "Gorgonzola"

         # But this implementation triggers the bug:
          list2
          |> List.walk list1 \state, _element ->
               List.set state 1 "Gorgonzola"

     _ <- await (badList |> listToString |> Stdout.line)

     succeed {}

listToString : List Str -> Str
listToString = \list ->
    elementsStr =
        list
        |> List.walk "" (\str, value -> "\(str)\(value), ")
    "[\(elementsStr)]"

(Save this as one of the examples in examples/interactive)

Expected output

[Camembert, Gorgonzola, Roquefort, ]

Actual output

[@▒�kUt, Gorgonzola, Roquefort, ]

The characters of the first element are random.

It looks like we are reading from uninitialized memory here.

Strangely enough, the bug only shows up when using List.walk. When doing a List.set directly, the problem does not show.

(I am aware that the way List.walk is used in this example is a bit odd, as list2 is not really used for anything anymore. It is what I ended up with after making the original example from #3258 as simple as possible).

Qqwy commented 2 years ago

I managed to reduce the minimal example even further:

main =
     list1 = ["Camembert", "Brie", "Roquefort"]
     emptylist : List Str
     emptylist = [] 

     badList =
          List.walk emptylist list1 \state, _element ->
               List.set state 1 "Gorgonzola"

     _ <- await (badList |> listToString |> Stdout.line)

     succeed {}

(The other functions and module header are the same).

We now walk over an empty list. The output now should expected to be ["Camembert", "Brie", "Roquefort", ] (i.e., list1, unchanged).

However, also here, the first element of the list that is print is instead some undefined memory:

[�&�.Vt, Brie, Roquefort, ]

Qqwy commented 2 years ago

Simplifying it even further, the following even produces the undefined memory output in the repl:

list1 = ["Camembert", "Brie", "Roquefort"]
emptylist : List Str
emptylist = []

List.walk emptylist list1 (\state, _element -> List.set state 1 "Gorgonzola")

rtfeldman commented 2 years ago

I tried this out in Hello World:

app "hello"
    packages { pf: "c-platform/main.roc" }
    imports []
    provides [main] to pf

main =
    answer = List.walk [] ["Camembert", "Brie", "Roquefort"] \state, _element ->
        List.set state 1 "Gorgonzola"

    "Hello, World!\n"

roc check passed:

However, running it crashed with an intentionally-generated runtime exception:

This suggests to me that it's a monomorphization bug.

We should never have a situation where type-checking passes, but then monomorphization intentionally generates a runtime error - the latter should only happen when there was a type mismatch!

Qqwy commented 2 years ago

We should never have a situation where type-checking passes, but then monomorphization intentionally generates a runtime error - the latter should only happen when there was a type mismatch!

But this seems only to happen if you do not specify an explicit type for emptyList (the first parameter of List.walk). If you do, there is not even an 'intentional runtime error' currently.

So is the cause of this problem a monomorphization bug? Or is there also a monomorphization bug?

rtfeldman commented 2 years ago

Could definitely be two different problems, yes! 😄

ayazhafiz commented 2 years ago

this seems like possibly a bug related to borrow/own in the higher-order low-levels. @folkertdev has done some work around this recently.

folkertdev commented 2 years ago

at least on https://github.com/rtfeldman/roc/pull/3452 I cannot reproduce this issue any more, and valgrind is all happy

Anton-4 commented 2 years ago

Can you try this again on the latest trunk @Qqwy ?

Qqwy commented 2 years ago

@Anton-4 I have merged in 43b152809246cc44f17a9ac8ced5ea2a4b6c8a0a to PR #3258 to test it fully. The issue has indeed been resolved :partying_face:

roc-lang / roc