Unnecessary default in a pattern match

[jiribenes]

From #769 (comment), example taken directly from the failing test there: list_tail from are_we_fast_yet.

The following program gets compiled to a pattern match with an unnecessary else { ... } clause (a default clause).

def isShorterThan(x: List[Int], y: List[Int]): Bool =
  (x, y) match {
    case (_, Nil()) => false
    case (Nil(), _) => true
    case (Cons(_, xs),Cons(_, ys)) => isShorterThan(xs, ys)
  }

gets compiled to the following Core IR without opts:

def isShorterThan2379(x2377: List910[BoxedInt296], y2378: List910[BoxedInt296]) = {
  let v_r_24453438 = make Tuple2249[List910[BoxedInt296], List910[BoxedInt296]] Tuple2330(x2377, y2378)
  def b_k_24463439() = return false
  def b_k_24473440() = return true
  def b_k_24493441(xs2391: List910[BoxedInt296], ys2392: List910[BoxedInt296]) = {
    val v_r_24483444: Bool389 = isShorterThan2379(xs2391, ys2392);
    return v_r_24483444
  }
  val v_r_24623449: Bool389 = v_r_24453438 match {
    case Tuple2330 { (v_y_24502453: List910[BoxedInt296], v_y_24512452: List910[BoxedInt296]) => 
      v_y_24512452 match {
        case Nil1118 { () => 
          b_k_24463439()
        }
        case Cons1119 { (v_coe_36343658: BoxedInt296, v_coe_36353659: List910[BoxedInt296]) => 
          def b_tmp_36363654(v_y_24542457: Int398, v_y_24552456: List910[BoxedInt296]) = v_y_24502453 match {
            case Nil1118 { () => 
              b_k_24473440()
            }
            case Cons1119 { (v_coe_36313656: BoxedInt296, v_coe_36323657: List910[BoxedInt296]) => 
              def b_tmp_36333655(v_y_24582461: Int398, v_y_24592460: List910[BoxedInt296]) = b_k_24493441(v_y_24592460, v_y_24552456)
              b_tmp_36333655(unboxInt300(v_coe_36313656), v_coe_36323657)
            }
          }
          b_tmp_36363654(unboxInt300(v_coe_36343658), v_coe_36353659)
        }
      } else {
        v_y_24502453 match {
          case Nil1118 { () => 
            b_k_24473440()
          }
        }}
    }
  };
  return v_r_24623449
};

with Core opts, it's perhaps more readable:

def isShorterThan2379(x2377: List910[BoxedInt296], y2378: List910[BoxedInt296]) = y2378 match {
  case Nil1118 { () => 
    return false
  }
  case Cons1119 { (v_coe_5398_36316: BoxedInt296, v_coe_5399_46311: List910[BoxedInt296]) => 
    x2377 match {
      case Nil1118 { () => 
        return true
      }
      case Cons1119 { (v_coe_5395_8_36327: BoxedInt296, v_coe_5396_9_46330: List910[BoxedInt296]) => 
        isShorterThan2379(v_coe_5396_9_46330, v_coe_5399_46311)
      }
    }
  }
} else {
  x2377 match {
    case Nil1118 { () => 
      return true
    }
  }};

Now it should be somewhat clear to see that the else branch never occurs. So why are we generating it? 🤔

Source Tree

FunDef(
      IdDef(isShorterThan),
      Nil,
      List(
        ValueParam(
          IdDef(x),
          Some(
            ValueTypeRef(
              IdRef(Nil, List),
              List(ValueTypeRef(IdRef(Nil, Int), Nil))
            )
          )
        ),
        ValueParam(
          IdDef(y),
          Some(
            ValueTypeRef(
              IdRef(Nil, List),
              List(ValueTypeRef(IdRef(Nil, Int), Nil))
            )
          )
        )
      ),
      Nil,
      Some(Effectful(ValueTypeRef(IdRef(Nil, Bool), Nil), Effects(Nil))),
      Return(
        Match(
          Call(
            IdTarget(IdRef(List(effekt), Tuple2)),
            Nil,
            List(Var(IdRef(Nil, x)), Var(IdRef(Nil, y))),
            Nil
          ),
          List(
            MatchClause(
              TagPattern(
                IdRef(List(effekt), Tuple2),
                List(IgnorePattern(), TagPattern(IdRef(Nil, Nil), Nil))
              ),
              Nil,
              Return(Literal(false, ValueTypeApp(Bool_389, Nil)))
            ),
            MatchClause(
              TagPattern(
                IdRef(List(effekt), Tuple2),
                List(TagPattern(IdRef(Nil, Nil), Nil), IgnorePattern())
              ),
              Nil,
              Return(Literal(true, ValueTypeApp(Bool_389, Nil)))
            ),
            MatchClause(
              TagPattern(
                IdRef(List(effekt), Tuple2),
                List(
                  TagPattern(
                    IdRef(Nil, Cons),
                    List(IgnorePattern(), AnyPattern(IdDef(xs)))
                  ),
                  TagPattern(
                    IdRef(Nil, Cons),
                    List(IgnorePattern(), AnyPattern(IdDef(ys)))
                  )
                )
              ),
              Nil,
              Return(
                Call(
                  IdTarget(IdRef(Nil, isShorterThan)),
                  Nil,
                  List(Var(IdRef(Nil, xs)), Var(IdRef(Nil, ys))),
                  Nil
                )
              )
            )
          ),
          None()
        )
      )
    ),

[jiribenes]

Here's a self-contained, simpler test case (no recursion, no inner patterns):

type Answer { Yes(); No() }

def println(ans: Answer): Unit = ans match {
  case Yes() => println("y")
  case No()  => println("n")
}

def join(left: Answer, right: Answer): Answer = (left, right) match {
  case (Yes(), Yes()) => Yes()
  case (No() ,     _) => No()
  case (_    , No() ) => No()
}

def main() = println(join(Yes(), No()))

And its Core:

def join2368(left2366: Answer2363, right2367: Answer2363) = {
  let v_r_23953300 = make Tuple2252[Answer2363, Answer2363] Tuple2334(left2366, right2367)
  def b_k_23963301() = return make Answer2363 Yes2370()
  def b_k_23973302() = return make Answer2363 No2371()
  def b_k_23983303() = return make Answer2363 No2371()
  val v_r_24033304: Answer2363 = v_r_23953300 match {
    case Tuple2334 { (v_y_23992402: Answer2363, v_y_24002401: Answer2363) => 
      v_y_23992402 match {
        case Yes2370 { () => 
          v_y_24002401 match {
            case Yes2370 { () => 
              b_k_23963301()
            }
            case No2371 { () => 
              b_k_23983303()
            }
          }
        }
        case No2371 { () => 
          b_k_23973302()
        }
      } else { // Here's the redundant `else` / `default`!
        v_y_24002401 match {
          case No2371 { () => 
            b_k_23983303()
          }
        }}
    }
  };
  return v_r_24033304
};