effekt
effekt copied to clipboard
effekt-lang
Miscompilation with opts in JS: ReferenceError: b_k_0 is not defined
The Effekt program below (minimised from ~300 LoC) produces invalid JavaScript when compiled with optimisations, specifically:
ReferenceError: b_k_0 is not defined
import ref
type TVar {
Bound(t: Type)
Unbound(id: Int)
}
record Type(ref: Ref[TVar])
def pretty(tpe: Type): String = tpe.ref.get match {
case Bound(t) => panic("got here 1")
case Unbound(id) => "?" ++ show(id)
}
def occurs(tid: Int, inside: Type): Bool = {
panic("occ? " ++ show(tid)++ " in? " ++ pretty(inside))
inside match {
case Type(x) => x.get match {
case Bound(t) => occurs(tid, t)
case Unbound(bid) => true
}
}
}
def unify(t1: Type, t2: Type): Unit = {
println(pretty(t1) ++ " ~?~ " ++ pretty(t2))
(t1, t2) match {
case (Type(x), b) and x.get is Bound(t) => unify(t, b)
case (a, Type(x)) and x.get is Bound(t) => unify(a, t)
case (Type(x), b) and x.get is Unbound(tid) =>
if (t1.equals(t2)) ()
else if (occurs(tid, b)) panic(pretty(Type(x)) ++ " occurs in " ++ pretty(b))
else x.set(Bound(b))
case (a, Type(x)) and x.get is Unbound(tid) =>
if (t1.equals(t2)) ()
else if (occurs(tid, a)) panic(pretty(Type(x)) ++ " occurs in " ++ pretty(a))
else x.set(Bound(a))
case _ =>
panic("cannot unify: " ++ pretty(t1) ++ " with " ++ pretty(t2))
}
}
def main() = {
def mkVar(n: Int): Type = Type(ref::ref(Unbound(n)))
unify(mkVar(0), mkVar(1))
}
I tried to minimise the example further, but all semantic changes already seem to make the code work again, sorry. What I tried:
- removing
ref( ~> program starts working) - removing
ref::setonly ( ~> program starts working) - reordering cases in pattern matches
- writing
equalsby hand aseq(~> program still crashes [!], but now runs also on LLVM where it doesn't crash) - removing the
Boundcase (funnily enough, the IR and resulting JS both eliminate it!)
It seems that the b_k_? are inlined, but not reachable and still being referred to?
Core IR (opt)
def main3431() = {
let tmp9521 = ref3413[TVar3421](make TVar3421 Unbound3435(0))
let tmp9522 = make Type3422 Type3438(tmp9521)
let tmp9524 = ref3413[TVar3421](make TVar3421 Unbound3435(1))
let tmp9525 = make Type3422 Type3438(tmp9524)
let tmp_4_211593 = get3416[TVar3421](tmp9521)
tmp_4_211593 match {
case Unbound3435 { (id_6_432_43011946: Int405) =>
let tmp_3_436_434_213036 = get3416[TVar3421](tmp9524)
tmp_3_436_434_213036 match {
case Unbound3435 { (id_6_215_648_646_21413165: Int405) =>
let tmp_4_220_653_651_21913211 = println1(infixConcat35(infixConcat35(infixConcat35("?", show14(id_6_432_43011946)), " ~?~ "), infixConcat35("?", show14(id_6_215_648_646_21413165))))
def b_k2_3529_5_221_654_652_22013083(x_6_222_655_653_22113212: Ref3407[TVar3421], b_7_223_656_654_22213119: Type3422, tid_8_224_657_655_22313196: Int405) = if (equals62[Type3422](tmp9522, tmp9525)) {
return ()
} else {
b_7_223_656_654_22213119 match {
case Type3438 { (x_2_2_10_226_659_657_22513156: Ref3407[TVar3421]) =>
let tmp_11_227_660_658_22613095 = get3416[TVar3421](x_2_2_10_226_659_657_22513156)
tmp_11_227_660_658_22613095 match {
case Unbound3435 { (id_6_6_19_235_668_666_23413186: Int405) =>
let tmp_6_26_242_675_673_24113018 = panic557(infixConcat35(infixConcat35(infixConcat35("occ? ", show14(tid_8_224_657_655_22313196)), " in? "), infixConcat35("?", show14(id_6_6_19_235_668_666_23413186))))
return tmp_6_26_242_675_673_24113018
}
}
}
}
}
def b_k3_3539_27_243_676_674_24213195(a_28_244_677_675_24312835: Type3422, x_29_245_678_676_24413213: Ref3407[TVar3421], tid_30_246_679_677_24512810: Int405) = if (equals62[Type3422](tmp9522, tmp9525)) {
return ()
} else {
a_28_244_677_675_24312835 match {
case Type3438 { (x_2_2_32_248_681_679_24713023: Ref3407[TVar3421]) =>
let tmp_33_249_682_680_24813188 = get3416[TVar3421](x_2_2_32_248_681_679_24713023)
tmp_33_249_682_680_24813188 match {
case Unbound3435 { (id_6_6_41_257_690_688_25612827: Int405) =>
let tmp_6_48_264_697_695_26312829 = panic557(infixConcat35(infixConcat35(infixConcat35("occ? ", show14(tid_30_246_679_677_24512810)), " in? "), infixConcat35("?", show14(id_6_6_41_257_690_688_25612827))))
return tmp_6_48_264_697_695_26312829
}
}
}
}
}
let tmp_50_266_699_697_265_213483 = get3416[TVar3421](tmp9521)
tmp_50_266_699_697_265_213483 match {
} else {
let tmp_52_268_701_699_267_4_213522 = get3416[TVar3421](tmp9524)
tmp_52_268_701_699_267_4_213522 match {
} else {
let tmp_53_269_702_700_268_5_313493 = get3416[TVar3421](tmp9521)
tmp_53_269_702_700_268_5_313493 match {
case Unbound3435 { (tid_10_54_270_703_701_269_6_413498: Int405) =>
b_k2_3529_5_221_654_652_22013083(tmp9521, tmp9525, tid_10_54_270_703_701_269_6_413498)
}
} else {
let tmp_55_271_704_702_270_7_513515 = get3416[TVar3421](tmp9524)
tmp_55_271_704_702_270_7_513515 match {
case Unbound3435 { (tid_12_56_272_705_703_271_8_613494: Int405) =>
b_k3_3539_27_243_676_674_24213195(tmp9522, tmp9524, tid_12_56_272_705_703_271_8_613494)
}
} else {
let tmp_58_274_707_705_273_10_8_213553 = get3416[TVar3421](tmp9521)
tmp_58_274_707_705_273_10_8_213553 match {
case Unbound3435 { (id_6_76_292_725_723_291_28_26_2013569: Int405) =>
let tmp_3_80_296_729_727_295_32_30_24_213590 = get3416[TVar3421](tmp9524)
tmp_3_80_296_729_727_295_32_30_24_213590 match {
case Unbound3435 { (id_6_10_87_303_736_734_302_39_37_31_913587: Int405) =>
let tmp_5_16_93_309_742_740_308_45_43_37_1513594 = panic557(infixConcat35(infixConcat35(infixConcat35("cannot unify: ", infixConcat35("?", show14(id_6_76_292_725_723_291_28_26_2013569))), " with "), infixConcat35("?", show14(id_6_10_87_303_736_734_302_39_37_31_913587))))
return tmp_5_16_93_309_742_740_308_45_43_37_1513594
}
}
}
}}}}}
}
}
}
}
}
Resulting JS (search for !!!)
function main_0(ks_0, k_0) {
const tmp_0 = { value: (new Unbound_0(0)) };
const tmp_1 = new Type_0(tmp_0);
const tmp_2 = { value: (new Unbound_0(1)) };
const tmp_3 = new Type_0(tmp_2);
const tmp_4 = tmp_0.value;
const id_1 = tmp_4.id_0;
const tmp_5 = tmp_2.value;
const id_2 = tmp_5.id_0;
const tmp_6 = $effekt.println(((((((((("?") + (('' + id_1))))) + (" ~?~ ")))) + (((("?") + (('' + id_2))))))));
let x_0 = undefined;
let b_0 = undefined;
let tid_0 = undefined;
let a_0 = undefined;
let x_1 = undefined;
let tid_1 = undefined;
const tmp_7 = tmp_0.value;
switch (tmp_7.__tag) {
default:
const tmp_8 = tmp_2.value;
switch (tmp_8.__tag) {
default:
const tmp_9 = tmp_0.value;
switch (tmp_9.__tag) {
case 0:
const tid_2 = tmp_9.id_0;
return () => b_k_0(tmp_0, tmp_3, tid_2, ks_0); // !!!
default:
const tmp_10 = tmp_2.value;
switch (tmp_10.__tag) {
case 0:
const tid_3 = tmp_10.id_0;
a_0 = tmp_1;
x_1 = tmp_2;
tid_1 = tid_3;
break;
default:
const tmp_11 = tmp_0.value;
const id_3 = tmp_11.id_0;
const tmp_12 = tmp_2.value;
const id_4 = tmp_12.id_0;
const tmp_13 = (function() { throw ((((((((("cannot unify: ") + (((("?") + (('' + id_3)))))))) + (" with ")))) + (((("?") + (('' + id_4))))))) })();
return () => k_0(tmp_13, ks_0);
}
}
}
}
if ($effekt.equals(tmp_1, tmp_3)) {
return () => k_0($effekt.unit, ks_0);
} else {
const x_2 = a_0.ref_0;
const tmp_14 = x_2.value;
const id_5 = tmp_14.id_0;
const tmp_15 = (function() { throw ((((((((("occ? ") + (('' + tid_1))))) + (" in? ")))) + (((("?") + (('' + id_5))))))) })();
return () => k_0(tmp_15, ks_0);
}
if ($effekt.equals(tmp_1, tmp_3)) {
return () => k_0($effekt.unit, ks_0);
} else {
const x_3 = b_0.ref_0;
const tmp_16 = x_3.value;
const id_6 = tmp_16.id_0;
const tmp_17 = (function() { throw ((((((((("occ? ") + (('' + tid_0))))) + (" in? ")))) + (((("?") + (('' + id_6))))))) })();
return () => k_0(tmp_17, ks_0);
}
}
In the optimized core b_k2_3529_5_221_654_652_22013083 is clearly defined. b_k_0 is the shortened version of it (the JS backend renames and shortens ids for readability).
I thus assume the problem is introduced after optimizer.
As always these days (after performing contification on CPS to help the LLVM backend), the problem is in Contify. This can be verified by commenting out this line:
https://github.com/effekt-lang/effekt/blob/28ad596b9d03d24191ccc6b7b2ea2e7155401160/effekt/shared/src/main/scala/effekt/generator/js/JavaScript.scala#L55
Here is the contified version
module repro
def main3431 = { | ks9117, k9118 =>
let tmp5036 = ref3413(make TVar3421 Unbound3435(0))
let tmp5037 = make Type3422 Type3438(tmp5036)
let tmp5039 = ref3413(make TVar3421 Unbound3435(1))
let tmp5040 = make Type3422 Type3438(tmp5039)
let tmp_4_26932 = get3416(tmp5036)
tmp_4_26932 match {
case Unbound3435 (id_6_432_4307409) => {
let tmp_3_436_434_28493 = get3416(tmp5039)
tmp_3_436_434_28493 match {
case Unbound3435 (id_6_215_648_646_2148311) => {
let tmp_4_220_653_651_2198726 = println1(infixConcat35(infixConcat35(infixConcat35("?", show14(id_6_432_4307409)), " ~?~ "), infixConcat35("?", show14(id_6_215_648_646_2148311))))
let b_k2_3529_5_221_654_652_2208484 = { (x_6_222_655_653_2218727, b_7_223_656_654_2228658, tid_8_224_657_655_2238564) | ks9120 =>
if (equals62(tmp5037, tmp5040)) {
jump k9118(()) @ ks9120
} else {
b_7_223_656_654_2228658 match {
case Type3438 (x_2_2_10_226_659_657_2258595) => {
let tmp_11_227_660_658_2268491 = get3416(x_2_2_10_226_659_657_2258595)
tmp_11_227_660_658_2268491 match {
case Unbound3435 (id_6_6_19_235_668_666_2348714) => {
let tmp_6_26_242_675_673_2418380 = panic557(infixConcat35(infixConcat35(infixConcat35("occ? ", show14(tid_8_224_657_655_2238564)), " in? "), infixConcat35("?", show14(id_6_6_19_235_668_666_2348714))))
jump k9118(tmp_6_26_242_675_673_2418380) @ ks9120
}
}
}
}
}
}
let b_k3_3539_27_243_676_674_2428717 = { (a_28_244_677_675_2438312, x_29_245_678_676_2448728, tid_30_246_679_677_2458415) | ks9119 =>
if (equals62(tmp5037, tmp5040)) {
jump k9118(()) @ ks9119
} else {
a_28_244_677_675_2438312 match {
case Type3438 (x_2_2_32_248_681_679_2478502) => {
let tmp_33_249_682_680_2488496 = get3416(x_2_2_32_248_681_679_2478502)
tmp_33_249_682_680_2488496 match {
case Unbound3435 (id_6_6_41_257_690_688_2568677) => {
let tmp_6_48_264_697_695_2638396 = panic557(infixConcat35(infixConcat35(infixConcat35("occ? ", show14(tid_30_246_679_677_2458415)), " in? "), infixConcat35("?", show14(id_6_6_41_257_690_688_2568677))))
jump k9118(tmp_6_48_264_697_695_2638396) @ ks9119
}
}
}
}
}
}
let tmp_50_266_699_697_265_29001 = get3416(tmp5036)
tmp_50_266_699_697_265_29001 match {
} else {
let tmp_52_268_701_699_267_4_29043 = get3416(tmp5039)
tmp_52_268_701_699_267_4_29043 match {
} else {
let tmp_53_269_702_700_268_5_39007 = get3416(tmp5036)
tmp_53_269_702_700_268_5_39007 match {
case Unbound3435 (tid_10_54_270_703_701_269_6_49032) => {
jump b_k2_3529_5_221_654_652_2208484(tmp5036, tmp5040, tid_10_54_270_703_701_269_6_49032) @ ks9117
}
} else {
let tmp_55_271_704_702_270_7_59009 = get3416(tmp5039)
tmp_55_271_704_702_270_7_59009 match {
case Unbound3435 (tid_12_56_272_705_703_271_8_69023) => {
jump b_k3_3539_27_243_676_674_2428717(tmp5037, tmp5039, tid_12_56_272_705_703_271_8_69023) @ ks9117
}
} else {
let tmp_58_274_707_705_273_10_8_29076 = get3416(tmp5036)
tmp_58_274_707_705_273_10_8_29076 match {
case Unbound3435 (id_6_76_292_725_723_291_28_26_209080) => {
let tmp_3_80_296_729_727_295_32_30_24_29116 = get3416(tmp5039)
tmp_3_80_296_729_727_295_32_30_24_29116 match {
case Unbound3435 (id_6_10_87_303_736_734_302_39_37_31_99104) => {
let tmp_5_16_93_309_742_740_308_45_43_37_159109 = panic557(infixConcat35(infixConcat35(infixConcat35("cannot unify: ", infixConcat35("?", show14(id_6_76_292_725_723_291_28_26_209080))), " with "), infixConcat35("?", show14(id_6_10_87_303_736_734_302_39_37_31_99104))))
jump k9118(tmp_5_16_93_309_742_740_308_45_43_37_159109) @ ks9117
}
}
}
}
}
}
}
}
}
}
}
}
}
Before contification:
def b_k2_3529_5_221_654_652_2208484 = { (x_6_222_655_653_2218727, b_7_223_656_654_2228658, tid_8_224_657_655_2238564) | ks9120, k9121 =>
...
case Unbound3435 (tid_10_54_270_703_701_269_6_49032) => {
b_k2_3529_5_221_654_652_2208484(tmp5036, tmp5040, tid_10_54_270_703_701_269_6_49032) @ ks9117, k9118
}
After
...
let b_k2_3529_5_221_654_652_2208484 = { (x_6_222_655_653_2218727, b_7_223_656_654_2228658, tid_8_224_657_655_2238564) | ks9120 =>
...
case Unbound3435 (tid_10_54_270_703_701_269_6_49032) => {
jump b_k2_3529_5_221_654_652_2208484(tmp5036, tmp5040, tid_10_54_270_703_701_269_6_49032) @ ks9117
}
This does look alright, though.
I could trace it to this case:
https://github.com/effekt-lang/effekt/blob/28ad596b9d03d24191ccc6b7b2ea2e7155401160/effekt/shared/src/main/scala/effekt/generator/js/TransformerCps.scala#L218-L223
Commenting it out fixes the issue. Looks like we perform a direct style translation, but seem to forget the continuation.
Further analysis:
At the let cont for b_k2, we deem the body can be in direct style. Here is the body
let b_k3_3539_27_243_676_674_2428717 = { (a_28_244_677_675_2438312, x_29_245_678_676_2448728, tid_30_246_679_677_2458415) | ks9119 =>
if (equals62(tmp5037, tmp5040)) {
jump k9118(()) @ ks9119
} else {
a_28_244_677_675_2438312 match {
case Type3438 (x_2_2_32_248_681_679_2478502) => {
let tmp_33_249_682_680_2488496 = get3416(x_2_2_32_248_681_679_2478502)
tmp_33_249_682_680_2488496 match {
case Unbound3435 (id_6_6_41_257_690_688_2568677) => {
let tmp_6_48_264_697_695_2638396 = panic557(infixConcat35(infixConcat35(infixConcat35("occ? ", show14(tid_30_246_679_677_2458415)), " in? "), infixConcat35("?", show14(id_6_6_41_257_690_688_2568677))))
jump k9118(tmp_6_48_264_697_695_2638396) @ ks9119
}
}
}
}
}
}
let tmp_50_266_699_697_265_29001 = get3416(tmp5036)
tmp_50_266_699_697_265_29001 match {
} else {
let tmp_52_268_701_699_267_4_29043 = get3416(tmp5039)
tmp_52_268_701_699_267_4_29043 match {
} else {
let tmp_53_269_702_700_268_5_39007 = get3416(tmp5036)
tmp_53_269_702_700_268_5_39007 match {
case Unbound3435 (tid_10_54_270_703_701_269_6_49032) => {
jump b_k2_3529_5_221_654_652_2208484(tmp5036, tmp5040, tid_10_54_270_703_701_269_6_49032) @ ks9117
}
} else {
let tmp_55_271_704_702_270_7_59009 = get3416(tmp5039)
tmp_55_271_704_702_270_7_59009 match {
case Unbound3435 (tid_12_56_272_705_703_271_8_69023) => {
jump b_k3_3539_27_243_676_674_2428717(tmp5037, tmp5039, tid_12_56_272_705_703_271_8_69023) @ ks9117
}
} else {
let tmp_58_274_707_705_273_10_8_29076 = get3416(tmp5036)
tmp_58_274_707_705_273_10_8_29076 match {
case Unbound3435 (id_6_76_292_725_723_291_28_26_209080) => {
let tmp_3_80_296_729_727_295_32_30_24_29116 = get3416(tmp5039)
tmp_3_80_296_729_727_295_32_30_24_29116 match {
case Unbound3435 (id_6_10_87_303_736_734_302_39_37_31_99104) => {
let tmp_5_16_93_309_742_740_308_45_43_37_159109 = panic557(infixConcat35(infixConcat35(infixConcat35("cannot unify: ", infixConcat35("?", show14(id_6_76_292_725_723_291_28_26_209080))), " with "), infixConcat35("?", show14(id_6_10_87_303_736_734_302_39_37_31_99104))))
jump k9118(tmp_5_16_93_309_742_740_308_45_43_37_159109) @ ks9117
}
}
}
}
}
}
}
}
However, the next statement is a continuation binder for b_k3, now we also deem this binder's body to be in direct style, but in b_k3, causing this problem.
This also appears every time I try to use map/set union for non-trivial data, which is a shame -- this prevents me from writing some nice programs :(
https://github.com/effekt-lang/effekt/blob/8f9f5f0ef67749e12cddbff5d4b4cb1f5857e251/libraries/common/map.effekt#L707-L739