comparing lists with lengths just above and below 100 produces TypeError: y is undefined in Utils.eqHelp #1011

jerith666 · 2019-01-13T22:14:50Z

Discussion

In src/Elm/Kernel/Utils.js, functions _Utils_eq() and _Utils_eqHelp() work together to implement the == operator. In order to avoid stack overflows, eqHelp will push pairs of values it's asked to test below a depth of 100 onto a stack as 2-tuples.

If the lists being compared are shorter than 100 elements, then the for (var key in x) loop will examine the $ key and find one side's value is "::" while the other's is "[]". This will prevent it from trying to test the a and b keys, which will be undefined in the "[]" (tail of the shorter list).

However, when the shorter list's length is exactly 100, then the "::" == "[]" comparison is not actually performed -- instead it's put onto the stack and true is returned unconditionally. That means that the values of the a and b keys are put onto the stack as well, so you end up with tuples on the stack that contain undefined as one of their two values. Since eqHelp does not expect that, it crashes.

Test Code

This code is structured to allow easy experimentation with the structure of the objects in the list and the number of elements in the lists being compared. If the two numbers passed to List.range are both above or both below 100, the bug is not reproduced.

module EqTest exposing (main)

import Html exposing (..)


oneThing =
    True


someThings n =
    List.repeat n oneThing


main =
    let
        r =
            List.range 100 102

        cp =
            List.concatMap (\i -> List.map (\j -> ( i, j )) r) r

        test ( i, j ) =
            let
                l =
                    String.fromInt i ++ " ?= " ++ String.fromInt j
            in
            case Debug.log ("testing " ++ l) <| someThings i == someThings j of
                True ->
                    l ++ ": True"

                False ->
                    l ++ ": False"

        rs =
            List.map test cp
    in
    div [] <| List.intersperse (br [] []) <| List.map text rs

Error Produced

TypeError: y is undefined[Learn More] dest:678:7
_Utils_eqHelp               http://matt.mchenryfamily.org/elbum/test-albums/dest/:678:7
_Utils_eq                   http://matt.mchenryfamily.org/elbum/test-albums/dest/:629:13
test                        http://matt.mchenryfamily.org/elbum/test-albums/dest/:4516:4
elm$core$List$map</<        http://matt.mchenryfamily.org/elbum/test-albums/dest/:4095:7
A2                          http://matt.mchenryfamily.org/elbum/test-albums/dest/:66:24
elm$core$List$foldrHelper<  http://matt.mchenryfamily.org/elbum/test-albums/dest/:4063:9
A4                          http://matt.mchenryfamily.org/elbum/test-albums/dest/:72:24
elm$core$List$foldrHelper<  http://matt.mchenryfamily.org/elbum/test-albums/dest/:4056:37
A4                          http://matt.mchenryfamily.org/elbum/test-albums/dest/:72:24
elm$core$List$foldr<        http://matt.mchenryfamily.org/elbum/test-albums/dest/:4074:10
A3                          http://matt.mchenryfamily.org/elbum/test-albums/dest/:69:24
elm$core$List$map<          http://matt.mchenryfamily.org/elbum/test-albums/dest/:4089:10
A2                          http://matt.mchenryfamily.org/elbum/test-albums/dest/:66:24
author$project$EqTest$main< http://matt.mchenryfamily.org/elbum/test-albums/dest/:4537:11
<anonymous>                 http://matt.mchenryfamily.org/elbum/test-albums/dest/:4508:34
<anonymous>                 http://matt.mchenryfamily.org/elbum/test-albums/dest/:11:2

The text was updated successfully, but these errors were encountered:

jerith666 · 2019-01-13T22:26:16Z

This looks similar to, and maybe the same root cause as, #945

jerith666 · 2019-01-13T22:32:01Z

The following is a work-around, if you can manage to hunt down and replace all the places in your code that might test long lists for equality:

safeEq : List a -> List a -> Bool
safeEq l1 l2 =
    let
        ll1 =
            List.length l1

        ll2 =
            List.length l2
    in
    case max ll1 ll2 >= 100 of
        False ->
            l1 == l2

        True ->
            (ll1 == ll2)
                && (List.all identity <| List.map2 (==) l1 l2)

harrysarson · 2019-01-13T23:25:30Z

I made another SSCCE (https://ellie-app.com/4rSsCjfVgmqa1)

module Main exposing (main)

import Html exposing (..)


main =
    div [] [ text (Debug.toString <| lhs == rhs) ]


rhs =
    generate Nothing


lhs =
    generate (Just { b = 1})

-- Record is nested exactly 100 times
generate x =
    { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = x } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }

do non-recursive tests before the depth check. this ensures that the 'for(key in x)' loop properly short-circuits, and avoids putting Tuple2s containing 'undefined' on the stack. fixes elm#1011 see that issue for further discussion, and the parent commit for test code.

danstn · 2019-08-26T01:45:20Z

FWIW: just had a regression in prod with this error.

Changing the order in comparison "fixes" the issue:

-            newPlan /= currentPlan
+            currentPlan /= newPlan

List len is ~100 when this starts happening.

michaeljones · 2019-09-09T13:46:37Z

I've just encountered this kind of error with a large data structure comparison. Switching the equality check around seems to have worked though I am worried that it will simply move the error to another situation after a different interaction. I'll report back if I have issues. I'm grateful for @danstn suggestion.

It is a distressing bug to get as it is not immediately clear what could be done to avoid it.

do non-recursive tests before the depth check. this ensures that the 'for(key in x)' loop properly short-circuits, and avoids putting Tuple2s containing 'undefined' on the stack. fixes elm#1011; see that issue and elm#1031 for further discussion

@Skinney

do non-recursive tests before the depth check. this ensures that the 'for(key in x)' loop properly short-circuits, and avoids putting Tuple2s containing 'undefined' on the stack. fixes elm#1011; see that issue and elm#1031 for further discussion listTests by @Skinney

jerith666 added a commit to jerith666/elbum that referenced this issue Jan 27, 2019

work-around for elm/core#1011

35b6d10

jerith666 added a commit to jerith666/core that referenced this issue Feb 7, 2019

implement test for elm#1011

025b874

jerith666 added a commit to jerith666/core that referenced this issue Feb 8, 2019

implement test for elm#1011

8e1cc7b

jerith666 mentioned this issue Feb 8, 2019

Run local tests jerith666/core#1

Closed

jerith666 mentioned this issue Feb 9, 2019

avoid attempts to access properties of undefined in _Utils_eqHelp #1018

Closed

harrysarson mentioned this issue Aug 10, 2019

Test failed due to TypeError elm-explorations/test#105

Open

jerith666 mentioned this issue Oct 28, 2019

Fixes runtime exception when comparing inequal lists with over 100 elements #1031

Merged

jerith666 mentioned this issue Nov 10, 2019

add tests for _Utils_eqHelp #1062

Open

evancz closed this as completed in 3520419 Nov 13, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

comparing lists with lengths just above and below 100 produces TypeError: y is undefined in Utils.eqHelp #1011

comparing lists with lengths just above and below 100 produces TypeError: y is undefined in Utils.eqHelp #1011

jerith666 commented Jan 13, 2019 •

edited

Loading

jerith666 commented Jan 13, 2019

jerith666 commented Jan 13, 2019

harrysarson commented Jan 13, 2019

danstn commented Aug 26, 2019

michaeljones commented Sep 9, 2019

comparing lists with lengths just above and below 100 produces TypeError: y is undefined in Utils.eqHelp #1011

comparing lists with lengths just above and below 100 produces TypeError: y is undefined in Utils.eqHelp #1011

Comments

jerith666 commented Jan 13, 2019 • edited Loading

Discussion

Test Code

Error Produced

jerith666 commented Jan 13, 2019

jerith666 commented Jan 13, 2019

harrysarson commented Jan 13, 2019

danstn commented Aug 26, 2019

michaeljones commented Sep 9, 2019

jerith666 commented Jan 13, 2019 •

edited

Loading