Checker seems to lose type information from extension

[kortschak]

Describe the bug

I have a program that I believe should compile but does not.

[
  "one",
  "two",
].map(k, state[k].map(e, {
  k: e,
})).flatten().map(d, d.with({
  "aye": state.aye,
  "bee": state.bee,
}))

The two helpers' types in this program are defined with the following Go:

cel.Function("flatten",
    cel.MemberOverload(
        "list_flatten",
        []*cel.Type{listV},
        listV,
        cel.UnaryBinding(flatten),
    ),
),

cel.Function("with",
    cel.MemberOverload(
        "map_with_map",
        []*cel.Type{mapKV, mapKV},
        mapKV,
        cel.BinaryBinding(withAll),
    ),
),

and

var (
    typeV = cel.TypeParamType("V")
    typeK = cel.TypeParamType("K")
    mapKV = cel.MapType(typeK, typeV)
    listV = cel.ListType(typeV)
)

Output for the bad program:

bad: failed compilation: ERROR: <input>:7:28: found no matching
overload for 'with' applied to 'list(map(string, dyn)).(map(string,
dyn))'
 | })).flatten().map(d, d.with({
 | ...........................^
exit status 1

The program is not the most efficient approach (and the more efficient approach does work), but it was surprising to me that it did not work; flatten returns a list or objects and with accepts an object, but the error is complaining that d is a list. Removing the .with… shows this is not the case, as does injecting type debugging into the runtime.

To Reproduce Check which components this affects:

• [ ] parser
• [x] checker
• [ ] interpreter

Sample expression and input that reproduces the issue:

[
  "one",
  "two",
].map(k, state[k].map(e, {
  k: e,
})).flatten().map(d, d.with({
  "aye": state.aye,
  "bee": state.bee,
}))

Test setup:

https://go.dev/play/p/7KBvbCXNcnW

Expected behavior

The output of the program should be the same for both the good and bad cases. Good case here

[
  "one",
  "two",
].map(k, state[k].map(e, {
  k: e,
  "aye": state.aye,
  "bee": state.bee,
})).flatten().map(d, d)

[TristonianJones]

@kortschak I think the issue is that the flatten signature is takes a listV as input and returns listV as output. In this case the parameterized type for V is expected to be list(map(string, dyn)).

You might have to update the flatten signature to list(V) -> V or to list(list(V)) to list(V), I'm not sure which would be better since you'd get a collision with the type parameter V and any other type.

[kortschak]

If I decompose the program, I get these steps. The first generates a list of objects

[
  "one",
  "two",
].map(k, state[k].map(e, {
  k: e,
}) -> list(map(string,dyn))

which is essentially untransformed in type by flatten

flatten(list(map(string,dyn))) -> list(map(string,dyn))

so the map should see each d as a map(string,dyn).

list(map(string,dyn)).map(d (map(string,dyn)), d.with({
  "aye": state.aye,
  "bee": state.bee,
}))

But it sees them as a list. This is confirmed by running just the program up until the flatten call

[
  "one",
  "two",
].map(k, state[k].map(e, {
  k: e,
})).flatten()

which gives me

[
    {
        "one": {
            "value": 1
        }
    },
    {
        "one": {
            "value": "two"
        }
    },
    {
        "two": {
            "value": 3
        }
    },
    {
        "two": {
            "value": "four"
        }
    }
]

Also with this program

[
  "one",
  "two",
].map(k, state[k].map(e, {
  k: e,
})).flatten().map(d, 
    type(d) == type({})
)

which outputs

[
    true,
    true,
    true,
    true
]

[TristonianJones]

@kortschak the problem isn't the runtime behavior, but rather how types are declared and identified within the type-checker.

For a type of list(list(map(string, dyn))) and a type declaration of list(V), the type of V will be identified as list(map(string, dyn)). So if you declare the flatten function as taking list(V) as input and providing list(V) as output, the type-checker will think that flatten will produce a list(list(map(string, dyn))) even though the runtime type would be list(map(string, dyn)).

Your best bet would probably be to convert the type signature from taking list(V) to list(dyn) so as to avoid confusing the type-checker as to the type emitted by flatten.

-Tristan

[kortschak]

Thanks. I'll make it list(dyn) -> list(dyn). Sorry for the noise.