Incorrect aliasing of iso when using match

[scwunch]

I don't think a field should be consumable, but this code compiles and gives rise to arbitrarily many copies of an iso reference to one object, breaking the isolation guarantees.

The particular function that should be caught by the function is this one:

fun ref take(): Foo iso^ =>
    // consume _foo  // <- compiler error
    match _foo
    | let b: Foo => consume b   // ... no compiler error?
    end

$ ponyc -v
0.58.9-cabe71e [release]
Compiled with: LLVM 15.0.7 -- Clang-18.1.3-x86_64
Defaults: pic=true

[SeanTAllen]

Code in question from the playground:

actor Main
  new create(env: Env) =>
    var fbox = FooBox(recover iso Foo("original") end)
    let one_foo = fbox.take()
    let same_foo = fbox.take()
    let w1 = WantFoo(consume one_foo)
    w1(env)
    same_foo.data = "changed"
    let w2 = WantFoo(consume same_foo)
    w2(env)

class iso Foo
  var data: String
  new create(data': String) =>
    data = data'

class iso FooBox
  var _foo: Foo iso

  new iso create(foo: Foo iso) =>
    _foo = consume foo

  fun ref take(): Foo iso^ =>
    // consume _foo  // <- compiler error
    match _foo
    | let b: Foo => consume b   // ... no compiler error?
    end

actor WantFoo
  var foo: Foo

  new create(foo': Foo iso) =>
    foo = consume foo'

  be apply(env: Env) =>
    env.out.print(foo.data)

[SeanTAllen]

Minimal reproduction:

class Bad
  let _s: String iso

  new iso create(s: String iso) =>
    _s = consume s

  fun ref take(): String iso^ =>
    match _s
    | let s': String iso => consume s'
    end

[SeanTAllen]

A variation to also test based on the consume code:

class Bad
  var _s: String iso

  new iso create(s: String iso) =>
    _s = consume s

  fun ref take(): String iso^ =>
    match _s
    | let s': String iso => consume s'
    end

[SeanTAllen]

If we had:

  fun ref take(): String iso^ =>
    consume _s

this would get caught. Because we would have this in the ast:

(consume x (. this (id _s))) which would fall through into the TK_DOT code in refer_consume, but we don't have that ast, we have (consume x (letref (id s')))

The code that handles TK_VARREF, TK_LETREF, and TK_PARAMREF needs to handle for varref and letref the possibility that have a field and do a check like TK_DOT has:

      if(ast_id(left) == TK_THIS)
      {
        def = (ast_t*)ast_data(term);
        name = ast_name(right);

        // check it's not a let or embed if it's a this variable
        if((ast_id(def) == TK_FLET) || (ast_id(def) == TK_EMBED))
        {
          ast_error(opt->check.errors, ast,
            "can't consume a let or embed field");
          return false;
        }

It is important to note that var fields aren't handled by the above code. but instead this code later in the TK_DOT case:

      if(!check_assigned_same_expression(opt, ast, name, &assign_ast))
      {
        ast_error(opt->check.errors, ast,
          "consuming a field is only allowed if it is reassigned in the same"
          " expression");
        return false;
      }

Thus we need two test both minimal cases, with let and with var. Additionally we need to test embed as well.

[SeanTAllen]

@jemc do you agree with this as a "general approach" or do you think there is an alternate approach we should be taking?

[dipinhora]

not sure if it's helpful, but the minimal reproduction from #4579 (comment) used to fail to compile through pony 0.40.0.. error details can be seen on godbolt: https://godbolt.org/z/W8brMzr8d

selecting pony 0.41.2 on godbolt allows it to compile successfully..

[SeanTAllen]

Thanks @dipinhora. I was already really confident this was broken in #3643 which went in with 0.41.0

[redvers]

I hesitate to stumble into areas of the theory or compiler that I don't fully understand, but it looks to me more like match on an iso breaks iso's guarantees as opposed to having anything to do with a class field:

For example:

actor Main
  new create(env: Env) =>
    let a: (String iso | None) = recover iso "Hello World".clone() end
    var b: String iso = recover iso String end
    
    match a
    | let dup: String iso => b = consume dup
    | let no: None => None
    end
    
    if (a is b) then env.out.print("Identity Equality") end

If that's the case, I guess we should ensure that we don't allow match on isos and force consumption?

[redvers]

Even more minimal example:

actor Main
  new create(env: Env) =>
    let a: String iso = recover iso "Hello World".clone() end
    var b: String iso = recover iso String end
    
    match a
    | let x: String iso => b = consume x
    end
    
    if (a is b) then env.out.print("Identity match of two isos") end

[SeanTAllen]

@redvers

If that's the case, I guess we should ensure that we don't allow match on isos and force consumption?

No, there's nothing wrong with matching on an iso. There's nothing wrong with consuming it, but we need to properly track aliasing and get the refcaps correct.

It makes sense that @redvers found what he did. Match and aliasing appears to have been broken when we moved to our current implementation of the type system when we switched to the Stead model.

[SeanTAllen]

Here's the correct error for red's minimal example.

Building builtin -> /opt/compiler-explorer/ponyc-0.40.0/packages/builtin
Building /app -> /app
Error:
<source>:7:7: this capture violates capabilities, because the match would need to differentiate by capability at runtime instead of matching on type alone
    | let x: String iso => b = consume x
      ^
    Info:
    <source>:3:12: the match type allows for more than one possibility with the same type as pattern type, but different capabilities. match type: String iso!
        let a: String iso = recover iso "Hello World".clone() end
               ^
    <source>:7:7: pattern type: String iso
        | let x: String iso => b = consume x
          ^
    <source>:7:14: matching String iso! with String iso could violate capabilities: iso! isn't a subcap of iso
        | let x: String iso => b = consume x

We appear to have lost some proper aliasing.

[SeanTAllen]

My minimal example should have:

Building builtin -> /opt/compiler-explorer/ponyc-0.40.0/packages/builtin
Building /app -> /app
Error:
<source>:9:7: this capture violates capabilities, because the match would need to differentiate by capability at runtime instead of matching on type alone
    | let s': String iso => consume s'
      ^
    Info:
    <source>:2:11: the match type allows for more than one possibility with the same type as pattern type, but different capabilities. match type: String iso!
      let _s: String iso
              ^
    <source>:9:7: pattern type: String iso
        | let s': String iso => consume s'
          ^
    <source>:9:15: matching String iso! with String iso could violate capabilities: iso! isn't a subcap of iso
        | let s': String iso => consume s'

So yes, my initial solution was incorrect. I missed that we were in fact aliasing again and that it should be iso! unless you do match consume foo.

@jemc that isn't something that changed in the Stead model is it?

[jasoncarr0]

Oh yeah this is a longstanding issue that's very hard to fix without breaking valid code:
#3596
This example is a little bit simpler though

[jemc]

So what was the match expression aliasing behavior prior to PR #3643?

I'm confused as to why this was working properly in older versions of ponyc (as mentioned in above comments in this ticket).

[SeanTAllen]

So what was the match expression aliasing behavior prior to PR #3643?

Beyond the basics that I did for run with previous to verify basic behavior, I think we need to crack open the code together @jemc and go spelunking. It very much looks like that the let was correctly aliasing the binding (as should happen based on my discussions with Sylvan).

[jasoncarr0]

Presumably it's just https://github.com/ponylang/ponyc/pull/3643/files#diff-5c1159210a17e5115177c6e16b9eecb3f0dc0a56b6d0fc564dac282b5604ba0cL509
But I'm a bit surprised at both that change, as well as code that would rely on the lack of aliasing. The issue I linked is before #3643

The correct change for this line of code is to make the pattern_type of the branches ephemeral when checking to match the other changes to aliasing (i.e. instead of A! <= B, check A <= B^)

[SeanTAllen]

@jemc here is the patch for what you and i did during sync that we want to pick up from or at least save for posterity.
patch.txt

[jemc]

During the sync call, we explored the above patch, which did bring back the desired error for the hole in this ticket, but it also invalidated other valid match statements in the standard library, such as a match statement in string.pony where the iso^ returned by String.from was used as the match expression, and compared for equality against string literals (val).

More work is needed to create a correct patch.

[SeanTAllen]

@jemc I think perhaps we are approaching this slightly wrong. We are thinking about this from a "pre-steed" model. Consider the following code:

actor Main
  new create(env: Env) =>
    let x = recover iso "h".clone() end
    let a = A
    a.f(x)
    
actor A
  new create() => None
  be f(a: String iso) =>
    None

The error we get now is:

main.pony:5:9: argument not assignable to parameter
    a.f(x)
        ^
    Info:
    main.pony:5:9: argument type is String iso
        a.f(x)
            ^
    main.pony:9:8: parameter type requires String iso^
      be f(a: String iso) =>
           ^
    /root/.local/share/ponyup/ponyc-release-0.58.9-x86_64-linux-musl/packages/builtin/string.pony:604:16: String iso is not a subtype of String iso^: iso is not a subcap of iso^
      fun clone(): String iso^ =>
                   ^
    /root/.local/share/ponyup/ponyc-release-0.58.9-x86_64-linux-musl/packages/builtin/string.pony:604:23: this would be possible if the subcap were more ephemeral. Perhaps you meant to consume a variable here
      fun clone(): String iso^ =>

Prior to the steed change, this was:

Error:
<source>:5:9: argument not a subtype of parameter
    a.f(x)
        ^
    Info:
    <source>:5:9: argument type is String iso!
        a.f(x)
            ^
    <source>:9:8: parameter type is String iso
      be f(a: String iso) =>
           ^
    /opt/compiler-explorer/ponyc-0.40.0/packages/builtin/string.pony:604:16: String iso! is not a subtype of String iso: iso! is not a subcap of iso
      fun clone(): String iso^ =>
                   ^
    /opt/compiler-explorer/ponyc-0.40.0/packages/builtin/string.pony:604:23: this would be possible if the subcap were more ephemeral
      fun clone(): String iso^ =>

So I think what we want is perhaps that the match requires a iso^ rather than it doing aliasing. Therefore we have to consume it. To use in the match. I haven't fully thought this through, but based on our discussions during sync, perhaps we should be approaching from that "same thing, different angle"?

To match on an iso field we would need to do something like (pre or post stead)

class Bad
  var _s: String iso

  new iso create(s: String iso) =>
    _s = consume s

  fun ref take(): String iso^ =>
  
    let old = _s = recover iso _s.clone() end
    
    match consume old
    | let s': String iso => consume s'
    end

Note, the above change makes it compile pre-steed.

Also note all this still leaves the (iso | None) issue. I am approaching this from "let's fix the hole then address the union type usability issue with iso".

I think this is how you would need to address (right now) the | None problem with a field. It's ugly but it puts together the dynamics we need:

class Bad
  var _s: (String iso | None) = None

  new iso create(s: String iso) =>
    _s = consume s

  fun ref take(): String iso^ =>
    let o = _s = None
    _s = match (consume o)
    | let x: String iso => x.append(" there")
    | None => recover iso "hello".clone() end
    end
  
    "a".clone()

[SeanTAllen]

@jemc and i got one of the use cases correct (no tests for them yet) but there's two interesting failing runner tests we haven't had time to look at. We need to add tests for the identified cases above plus look into the failing:

[  FAILED  ] codegen-trace-tuple-boxed
[  FAILED  ] codegen-trace-tuple-dynamic

runner tests.

The current patch is attached.
patch.txt

[jemc]

Poked around a bit looking for places where tracing code interacts with the presence or absence of ephemerality. Found this, and mentioned it in the sync call, but haven't analyzed it in depth:

ponyc/src/libponyc/codegen/gentrace.c

Lines 805 to 808 in e46038b

	ast_setid(dst_cap_ast, dst_cap);
	ast_t* dst_eph = ast_sibling(dst_cap_ast);
	if(ast_id(dst_eph) == TK_EPHEMERAL)
	ast_setid(dst_eph, TK_NONE);

[jemc]

Looking at git blame for that chunk, I found this commit which may have introduced the issue with failing tests on Sean/I's patch (though it didn't introduce the particular tests that are failing). In that commit I found this line, which may be the culprit: 05bf6e4#diff-34c41e0c3a458d9f470cf12b33900913104fce664c69b0c19816a3f2620dabeaR543

Specifically, I think I recall that our patch messes with is_matchtype in a way that could cause different code paths here for the tracing generation code.

[SeanTAllen]

The above is at line 547 in gentrace.c now

[SeanTAllen]

@jemc looking at our patch, i don't see how anything in match.c that we changed could cause the "spooky action at a distance". i'm going to look at the changes in matchtype.c

[SeanTAllen]

@jemc so do you think cap_aliasing calling cap_aliasing could be our trigger for spooky action at a distance?

[SeanTAllen]

@jemc the following in our patch for a change in matchtype.c is indeed the cause of the spooky action at a distance:

  // If the operand does provide the pattern, but the operand refcap can't
  // match the pattern refcap, deny the match.
  //if(!is_cap_sub_cap(ast_id(o_cap), TK_EPHEMERAL,
  if(!is_cap_sub_cap(ast_id(o_cap), ast_id(o_eph),
     ast_id(p_cap), ast_id(p_eph)))

ie the change from TK_EPHEMERAL to ast_id(o_eph)

[SeanTAllen]

Ok I see some spooky action like thing @jemc.

With our change, when i do a build for the full program runner, we fall into the else that does the printout here in matchtype.c:

    if(errorf != NULL)
    {
      ast_error_frame(errorf, pattern,
        "matching %s with %s could violate capabilities: "
        "%s%s isn't a subcap of %s%s",
        ast_print_type(operand), ast_print_type(pattern),
        ast_print_type(o_cap), ast_print_type(o_eph),
        ast_print_type(p_cap), ast_print_type(p_eph));

        if(is_cap_sub_cap(ast_id(o_cap), TK_EPHEMERAL, ast_id(p_cap),
          ast_id(p_eph)))
          ast_error_frame(errorf, o_cap,
            "this would be possible if the subcap were more ephemeral. "
            "Perhaps you meant to consume this variable");
    }
    else
    {
      printf("----> errorf is NULL\n");
    }

    return MATCHTYPE_DENY_CAP;

And without our change, we never go down the path of "that didn't match, there was no error, but we do matchtype_deny_cap. Our bug must be something that didn't used to go down that path but does now.

[SeanTAllen]

@jemc I've verified that this test program:

class A

actor Main
  var map_before: Pointer[None] = Pointer[None]
  let _env: Env

  new create(env: Env) =>
    _env = env
    trace((recover A end, recover A end))

  be trace(t: ((A iso, A iso) | A val)) =>
    let t' = t
    match consume t
    | (let t1: A, let t2: A) =>
      _env.out.print("A")
    end

Goes down a different code path in matchtype.c with our code change vs without. The one with our change runs and does nothing. The one without, prints "A" before exiting. The test is catching a legit bug.

[SeanTAllen]

The following "hangs" with our change and then segfaults. It is fine without our patch.

class A

actor Main
  var map_before: Pointer[None] = Pointer[None]
  let _env: Env

  new create(env: Env) =>
    _env = env
    trace((recover A end, recover A end))

  be trace(t: (A iso, A iso)) =>
    match consume t
    | (let t1: A, let t2: A) =>
      _env.out.print("A")
    end

[SeanTAllen]

This also segfaults:

class A

actor Main
  var map_before: Pointer[None] = Pointer[None]
  let _env: Env

  new create(env: Env) =>
    _env = env
    trace(recover A end)

  be trace(t: A iso) =>
    match consume t
    | let t1: A =>
      _env.out.print("A")
    end

[SeanTAllen]

This works with existing. Doesn't work with ours... hangs then segfaults.

class A

actor Main
  var map_before: Pointer[None] = Pointer[None]
  let _env: Env
  var _z: A iso = recover A end

  new create(env: Env) =>
    _env = env

  be trace() =>
    let a = _z = recover A end
    match consume a
    | let t1: A =>
      _env.out.print("A")
    end

[SeanTAllen]

I will be posting a new patch soon that appears to work.

@jemc this sample goes through the "errorf is NULL" but the program works. We should investigate this before saying we are good:

class A

actor Main
  var map_before: Pointer[None] = Pointer[None]
  let _env: Env

  new create(env: Env) =>
    _env = env
    trace((recover A end, recover A end))

  be trace(t: ((A iso, A iso) | A val)) =>
    //let t' = t
    match consume t
    | (let t1: A, let t2: A) =>
      _env.out.print("A")
    end

The other example ones I posted today do not.

[SeanTAllen]

New patch that needs cleanup

patch.txt

[SeanTAllen]

I'm hopefully that we have this fix in place fairly soon. The above patch appears to work but we need more testing.

[SeanTAllen]

@jemc we have tests that fail. a number of them.

This one:

class iso C
  var s: Array[U8] iso
  new iso create() => s = recover s.create() end

actor Main
  new create(env: Env) =>
    let c = C
    var x: (C | None) = None
    try
      c.s = (x as C; consume c.s)
    end

as an example, is expecting:

"can't reassign to a consumed field in an expression if there is a partial call involved"

instead we get a:

/home/sean/pony-scratch/4579-e/main.pony:10:16: this capture violates capabilities
      c.s = (x as C; consume c.s)
               ^
    Info:
    /home/sean/pony-scratch/4579-e/main.pony:10:19: match type: C iso
          c.s = (x as C; consume c.s)
                      ^
    /home/sean/pony-scratch/4579-e/main.pony:10:14: pattern type: (C iso | None val)
          c.s = (x as C; consume c.s)
                 ^
    /home/sean/pony-scratch/4579-e/main.pony:10:19: matching C iso with C iso^ could violate capabilities: iso isn't a subcap of iso^
          c.s = (x as C; consume c.s)
                      ^
    /home/sean/pony-scratch/4579-e/main.pony:8:13: this would be possible if the subcap were more ephemeral. Perhaps you meant to consume this variable
        var x: (C | None) = None
                ^
    /home/sean/pony-scratch/4579-e/main.pony:10:19: matching (C iso | None val) with C iso^ could violate capabilities
          c.s = (x as C; consume c.s)

it appears that most or all of the failures are going down a "----> errorf is NULL" path.

[SeanTAllen]

@jemc i believe this from operator.c is our next culprit:

      const char* name = package_hygienic_id(&opt->check);

      ast_t* expr_type = ast_type(expr);
      errorframe_t info = NULL;
      matchtype_t is_match = is_matchtype(expr_type, type, &info, opt);
      if(is_match == MATCHTYPE_DENY_CAP)
      {
        errorframe_t frame = NULL;
        ast_error_frame(&frame, ast,
          "this capture violates capabilities");
        ast_error_frame(&frame, type,
          "match type: %s", ast_print_type(type));
        ast_error_frame(&frame, expr,
          "pattern type: %s", ast_print_type(expr_type));
        errorframe_append(&frame, &info);
        errorframe_report(&frame, opt->check.errors);

[SeanTAllen]

@jemc so operator.c call to is_matchtype works with the old is_matchtype code. we can discuss how we want to approach once I get everything passing. It would appear that the issue is we don't do an alias before that match check in as. Aliasing there doesn't make sense, but neither does the code we updated to handle iso elsewhere for match.

[SeanTAllen]

New patch that passes all tests but doesn't add a regression test for either of our minimal examples.

patch.txt

The patch has also been pushed to the branch issue-4579.

@jemc feel free to grab and make improvements.

[SeanTAllen]

The patch is now outdated @jemc. Grab the branch to see future changes including the two BadPony tests that I just pushed.

@jemc see the TODO is_matchtype. uncommenting the ast_free_unattached results in a segfault when compiling stdlib tests.

[SeanTAllen]

@jemc the following:

class A

actor Main
  var map_before: Pointer[None] = Pointer[None]
  let _env: Env

  new create(env: Env) =>
    _env = env
    trace((recover A end, recover A end))

  be trace(t: ((A iso, A iso) | A val)) =>
    //let t' = t
    match consume t
    | (let t1: A, let t2: A) =>
      _env.out.print("A")
    end

doesnt end up in the "errorf is NULL" in the pre-change code, but it does in ours. We should look into that and other "errorf is NULL" instances we see when running tests to make sure we didn't introduce an issue that isn't being found in tests.

[SeanTAllen]

@jemc ok so...trace_cap_nominal is one of the NULLs that is ending up going down that path now.

This one:

  if(ast_id(cap) == TK_VAL)
  {
    if(is_matchtype(orig, type, NULL, opt) == MATCHTYPE_ACCEPT)
    {
      ast_setid(cap, orig_cap);
      return PONY_TRACE_IMMUTABLE;
    } else {
      ast_setid(cap, TK_TAG);
    }
  }

Values:

----> o_cap: 91, o_eph: 2, p_cap: 94, p_eph: 57
Process 25349 stopped
* thread #1, name = 'ponyc', stop reason = breakpoint 1.1
    frame #0: 0x0000555555cc15e8 ponyc`is_nominal_match_entity(operand=0x00007ffff37dee40, pattern=0x00007ffff1369440, errorf=0x0000000000000000, report_reject=false, opt=0x00007fffffffe2a8) at matchtype.c:604:7
   601      else
   602      {
   603        printf("----> o_cap: %d, o_eph: %d, p_cap: %d, p_eph: %d\n", ast_id(o_cap), ast_id(o_eph), ast_id(p_cap), ast_id(p_eph));
-> 604        printf("----> errorf is NULL\n");
   605      }
   606
   607      return MATCHTYPE_DENY_CAP;
(lldb) bt

[SeanTAllen]

@jemc running the gentrace is_matchtype calls through is_astype instead fixes the issue. We need to look at those two in the change and decide on proper names.

i've pushed the change that fixes the issue with going down the unexpected path.

Whatever the names we come up with, we'll want tests for "is_astype" functionality and "is_matchtype". there's many for is_matchtype but we need to review those for what is missing.

[SeanTAllen]

In genmatch.c we have:

    ast_t* pattern_type = deferred_reify(reify, ast_type(the_case), c->opt);
    bool ok = true;

    matchtype_t match = is_matchtype(match_type, pattern_type, NULL, c->opt);

    ast_free_unattached(pattern_type);

if we update is_matchtype to:

  if (consumed_pattern != pattern)
    ast_free_unattached(consumed_pattern);

then no boom.

[SeanTAllen]

@jemc question to ask ourselves... now that we have it fixed this way, if we tried to fix it our original way with alias, would that be a better fix.