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

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

Open
jerith666 opened this Issue Jan 13, 2019 · 3 comments

Comments

Projects
None yet
2 participants
@jerith666
Copy link
Contributor

jerith666 commented Jan 13, 2019

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
@jerith666

This comment has been minimized.

Copy link
Contributor Author

jerith666 commented Jan 13, 2019

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

@jerith666

This comment has been minimized.

Copy link
Contributor Author

jerith666 commented Jan 13, 2019

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

This comment has been minimized.

Copy link

harrysarson commented Jan 13, 2019

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 } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }

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

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

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

@jerith666 jerith666 referenced this issue Feb 8, 2019

Closed

Run local tests #1

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

avoid attempts to access properties of undefined in _Utils_eqHelp
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment