0 | module Core.Case.CaseBuilder
   1 |
   2 | import Core.Case.CaseTree
   3 | import Core.Case.Util
   4 | import Core.Context.Log
   5 | import Core.Env
   6 | import Core.Normalise
   7 | import Core.Options
   8 | import Core.Value
   9 |
  10 | import Idris.Pretty.Annotations
  11 |
  12 | import Data.DPair
  13 | import Data.List.Quantifiers
  14 | import Data.SortedSet
  15 | import Data.String
  16 | import Data.Vect
  17 | import Libraries.Data.IMaybe
  18 | import Libraries.Data.List.SizeOf
  19 | import Libraries.Data.List.LengthMatch
  20 | import Libraries.Data.List01
  21 | import Libraries.Data.List01.Quantifiers
  22 |
  23 | import Decidable.Equality
  24 |
  25 | import Libraries.Text.PrettyPrint.Prettyprinter
  26 |
  27 | %default covering
  28 |
  29 | %hide Symbols.equals
  30 |
  31 | public export
  32 | data Phase = CompileTime RigCount | RunTime
  33 |
  34 | Eq Phase where
  35 |   CompileTime r == CompileTime r' = r == r'
  36 |   RunTime == RunTime = True
  37 |   _ == _ = False
  38 |
  39 | data ArgType : Scoped where
  40 |      Known : RigCount -> (ty : Term vars) -> ArgType vars -- arg has type 'ty'
  41 |      Stuck : (fty : Term vars) -> ArgType vars
  42 |          -- ^ arg will have argument type of 'fty' when we know enough to
  43 |          -- calculate it
  44 |      Unknown : ArgType vars
  45 |          -- arg's type is not yet known due to a previously stuck argument
  46 |
  47 | HasNames (ArgType vars) where
  48 |   full gam (Known c ty) = Known c <$> full gam ty
  49 |   full gam (Stuck ty) = Stuck <$> full gam ty
  50 |   full gam Unknown = pure Unknown
  51 |
  52 |   resolved gam (Known c ty) = Known c <$> resolved gam ty
  53 |   resolved gam (Stuck ty) = Stuck <$> resolved gam ty
  54 |   resolved gam Unknown = pure Unknown
  55 |
  56 | covering
  57 | {ns : _} -> Show (ArgType ns) where
  58 |   show (Known c t) = "Known " ++ show c ++ " " ++ show t
  59 |   show (Stuck t) = "Stuck " ++ show t
  60 |   show Unknown = "Unknown"
  61 |
  62 | record PatInfo (pvar : Name) (vars : Scope) where
  63 |   constructor MkInfo
  64 |   {idx : Nat}
  65 |   {name : Name}
  66 |   pat : Pat
  67 |   0 loc : IsVar name idx vars
  68 |   argType : ArgType vars -- Type of the argument being inspected (i.e.
  69 |                          -- *not* refined by this particular pattern)
  70 |
  71 | covering
  72 | {vars : _} -> Show (PatInfo n vars) where
  73 |   show pi = show (pat pi) ++ " : " ++ show (argType pi)
  74 |
  75 | HasNames (PatInfo n vars) where
  76 |   full gam (MkInfo pat loc argType)
  77 |      = do pat <- full gam pat
  78 |           argType <- full gam argType
  79 |           pure $ MkInfo pat loc argType
  80 |
  81 |   resolved gam (MkInfo pat loc argType)
  82 |      = do pat <- resolved gam pat
  83 |           argType <- resolved gam argType
  84 |           pure $ MkInfo pat loc argType
  85 |
  86 | {-
  87 | NamedPats is a list of patterns on the LHS of a clause. Each entry in
  88 | the list gives a pattern, and a proof that there is a variable we can
  89 | inspect to see if it matches the pattern.
  90 |
  91 | A definition consists of a list of clauses, which are a 'NamedPats' and
  92 | a term on the RHS. There is an assumption that corresponding positions in
  93 | NamedPats always have the same 'Elem' proof, though this isn't expressed in
  94 | a type anywhere.
  95 | -}
  96 |
  97 | data NamedPats : List Name -> -- the pattern variables still to process, in order
  98 |                  Scoped where
  99 |      Nil : NamedPats [] vars
 100 |      (::) : PatInfo pvar vars ->
 101 |             -- ^ a pattern, where its variable appears in the vars list,
 102 |             -- and its type. The type has no variable names; any names it
 103 |             -- refers to are explicit
 104 |             NamedPats ns vars -> NamedPats (pvar :: ns) vars
 105 |
 106 | getPatInfo : NamedPats todo vars -> List Pat
 107 | getPatInfo [] = []
 108 | getPatInfo (x :: xs) = pat x :: getPatInfo xs
 109 |
 110 | updatePats : {vars, todo : _} ->
 111 |              {auto c : Ref Ctxt Defs} ->
 112 |              Env Term vars ->
 113 |              NF vars -> NamedPats todo vars -> Core (NamedPats todo vars)
 114 | updatePats env nf [] = pure []
 115 | updatePats {todo = pvar :: ns} env (NBind fc _ (Pi _ c _ farg) fsc) (p :: ps)
 116 |   = case argType p of
 117 |          Unknown =>
 118 |             do defs <- get Ctxt
 119 |                empty <- clearDefs defs
 120 |                pure ({ argType := Known c !(quote empty env farg) } p
 121 |                           :: !(updatePats env !(fsc defs (toClosure defaultOpts env (Ref fc Bound pvar))) ps))
 122 |          _ => pure (p :: ps)
 123 | updatePats env nf (p :: ps)
 124 |   = case argType p of
 125 |          Unknown =>
 126 |             do defs <- get Ctxt
 127 |                empty <- clearDefs defs
 128 |                pure ({ argType := Stuck !(quote empty env nf) } p :: ps)
 129 |          _ => pure (p :: ps)
 130 |
 131 | substInPatInfo : {pvar, vars, todo : _} ->
 132 |                  {auto c : Ref Ctxt Defs} ->
 133 |                  FC -> Name -> Term vars -> PatInfo pvar vars ->
 134 |                  NamedPats todo vars ->
 135 |                  Core (PatInfo pvar vars, NamedPats todo vars)
 136 | substInPatInfo fc n tm p ps
 137 |     = case argType p of
 138 |            Known c ty =>
 139 |                 do defs <- get Ctxt
 140 |                    tynf <- nf defs (mkEnv fc vars) ty
 141 |                    case tynf of
 142 |                         NApp {} =>
 143 |                            pure ({ argType := Known c (substName n tm ty) } p, ps)
 144 |                         -- Got a concrete type, and that's all we need, so stop
 145 |                         _ => pure (p, ps)
 146 |            Stuck fty =>
 147 |              do defs <- get Ctxt
 148 |                 empty <- clearDefs defs
 149 |                 let env = mkEnv fc vars
 150 |                 case !(nf defs env (substName n tm fty)) of
 151 |                      NBind pfc _ (Pi _ c _ farg) fsc =>
 152 |                        pure ({ argType := Known c !(quote empty env farg) } p,
 153 |                                  !(updatePats env
 154 |                                        !(fsc defs (toClosure defaultOpts env
 155 |                                              (Ref pfc Bound pvar))) ps))
 156 |                      _ => pure (p, ps)
 157 |            Unknown => pure (p, ps)
 158 |
 159 | -- Substitute the name with a term in the pattern types, and reduce further
 160 | -- (this aims to resolve any 'Stuck' pattern types)
 161 | substInPats : {vars, todo : _} ->
 162 |               {auto c : Ref Ctxt Defs} ->
 163 |               FC -> Name -> Term vars -> NamedPats todo vars ->
 164 |               Core (NamedPats todo vars)
 165 | substInPats fc n tm [] = pure []
 166 | substInPats fc n tm (p :: ps)
 167 |     = do (p', ps') <- substInPatInfo fc n tm p ps
 168 |          pure (p' :: !(substInPats fc n tm ps'))
 169 |
 170 | getPat : {idx : Nat} ->
 171 |          (0 el : IsVar nm idx ps) -> NamedPats ps ns -> PatInfo nm ns
 172 | getPat First (x :: xs) = x
 173 | getPat (Later p) (x :: xs) = getPat p xs
 174 |
 175 | dropPat : {idx : Nat} ->
 176 |           (0 el : IsVar nm idx ps) ->
 177 |           NamedPats ps ns -> NamedPats (dropIsVar ps el) ns
 178 | dropPat First (x :: xs) = xs
 179 | dropPat (Later p) (x :: xs) = x :: dropPat p xs
 180 |
 181 | HasNames (NamedPats todo vars) where
 182 |   full gam [] = pure []
 183 |   full gam (x::xs) = [| (::) (full gam x) (full gam xs) |]
 184 |
 185 |   resolved gam [] = pure []
 186 |   resolved gam (x::xs) = [| (::) (resolved gam x) (resolved gam xs) |]
 187 |
 188 | covering
 189 | {vars : _} -> {todo : _} -> Show (NamedPats todo vars) where
 190 |   show xs = "[" ++ showAll xs ++ "]"
 191 |     where
 192 |       showAll : {vs, ts : _} -> NamedPats ts vs -> String
 193 |       showAll [] = ""
 194 |       showAll {ts = t :: _} [x]
 195 |           = show t ++ " " ++ show (pat x) ++ " [" ++ show (argType x) ++ "]"
 196 |       showAll {ts = t :: _} (x :: xs)
 197 |           = show t ++ " " ++ show (pat x) ++ " [" ++ show (argType x) ++ "]"
 198 |                      ++ ", " ++ showAll xs
 199 |
 200 | {vars : _} -> {todo : _} -> Pretty IdrisSyntax (NamedPats todo vars) where
 201 |   pretty xs = hsep $ prettyAll xs
 202 |     where
 203 |       prettyAll : {vs, ts : _} -> NamedPats ts vs -> List (Doc IdrisSyntax)
 204 |       prettyAll [] = []
 205 |       prettyAll {ts = t :: _} (x :: xs)
 206 |           = parens (pretty0 t <++> equals <++> pretty (pat x))
 207 |           :: prettyAll xs
 208 |
 209 | Weaken ArgType where
 210 |   weaken (Known c ty) = Known c (weaken ty)
 211 |   weaken (Stuck fty) = Stuck (weaken fty)
 212 |   weaken Unknown = Unknown
 213 |
 214 |   weakenNs s (Known c ty) = Known c (weakenNs s ty)
 215 |   weakenNs s (Stuck fty) = Stuck (weakenNs s fty)
 216 |   weakenNs s Unknown = Unknown
 217 |
 218 | Weaken (PatInfo p) where
 219 |   weakenNs s (MkInfo p el fty) = MkInfo p (weakenIsVar s el) (weakenNs s fty)
 220 |
 221 | Weaken (NamedPats todo) where
 222 |   weaken [] = []
 223 |   weaken (p :: ps) = weaken p :: weaken ps
 224 |
 225 |   weakenNs ns [] = []
 226 |   weakenNs ns (p :: ps) = weakenNs ns p :: weakenNs ns ps
 227 |
 228 | (++) : NamedPats ms vars -> NamedPats ns vars -> NamedPats (ms ++ ns) vars
 229 | (++) [] ys = ys
 230 | (++) (x :: xs) ys = x :: xs ++ ys
 231 |
 232 | tail : NamedPats (p :: ps) vars -> NamedPats ps vars
 233 | tail (x :: xs) = xs
 234 |
 235 | data PatClause : (todo : List Name) -> Scoped where
 236 |      MkPatClause : List Name -> -- names matched so far (from original lhs)
 237 |                    NamedPats todo vars ->
 238 |                    Int -> (rhs : Term vars) -> PatClause todo vars
 239 |
 240 | getNPs : PatClause todo vars -> NamedPats todo vars
 241 | getNPs (MkPatClause _ lhs pid rhs) = lhs
 242 |
 243 | covering
 244 | {vars : _} -> {todo : _} -> Show (PatClause todo vars) where
 245 |   show (MkPatClause _ ps pid rhs)
 246 |      = show ps ++ " => " ++ show rhs
 247 |
 248 | {vars : _} -> {todo : _} -> Pretty IdrisSyntax (PatClause todo vars) where
 249 |   pretty (MkPatClause _ ps _ rhs)
 250 |      = pretty ps <++> fatArrow <++> byShow rhs
 251 |
 252 | HasNames (PatClause todo vars) where
 253 |   full gam (MkPatClause ns nps i rhs)
 254 |      = [| MkPatClause (traverse (full gam) ns) (full gam nps) (pure i) (full gam rhs) |]
 255 |
 256 |   resolved gam (MkPatClause ns nps i rhs)
 257 |      = [| MkPatClause (traverse (resolved gam) ns) (resolved gam nps) (pure i) (resolved gam rhs) |]
 258 |
 259 | 0 IsConClause : PatClause (a :: todo) vars -> Type
 260 | IsConClause (MkPatClause _ (MkInfo pat _ _ :: _) _ _) = IsConPat pat
 261 |
 262 | substInClause : {a, vars, todo : _} ->
 263 |                 {auto c : Ref Ctxt Defs} ->
 264 |                 FC -> Subset (PatClause (a :: todo) vars) IsConClause ->
 265 |                 Core (Subset (PatClause (a :: todo) vars) IsConClause)
 266 | substInClause fc (Element (MkPatClause pvars (MkInfo pat pprf fty :: pats) pid rhs) isCons)
 267 |     = do pats' <- substInPats fc a (mkTerm vars pat) pats
 268 |          pure $ Element (MkPatClause pvars (MkInfo pat pprf fty :: pats') pid rhs) isCons
 269 |
 270 | data Partitions : List01 ne (PatClause (a :: todo) vars) -> Type where
 271 |      ConClauses : {a, todo, vars : _} ->
 272 |                   {ps : List01 ne   (PatClause (a :: todo) vars)} ->
 273 |                   (cs : List01 True (PatClause (a :: todo) vars )) ->
 274 |                   (0 isCons : All IsConClause cs) =>
 275 |                   Partitions ps -> Partitions (cs ++ ps)
 276 |      VarClauses : {a, todo, vars : _} ->
 277 |                   {ps : List01 ne   (PatClause (a :: todo) vars)} ->
 278 |                   (vs : List01 True (PatClause (a :: todo) vars)) ->
 279 |                   Partitions ps -> Partitions (vs ++ ps)
 280 |      NoClauses : Partitions []
 281 |
 282 | covering
 283 | {ps : _} -> Show (Partitions ps) where
 284 |   show (ConClauses cs rest)
 285 |     = unlines ("CON" :: map (("  " ++) . show) (forget cs))
 286 |     ++ "\n, " ++ show rest
 287 |   show (VarClauses vs rest)
 288 |     = unlines ("VAR" :: map (("  " ++) . show) (forget vs))
 289 |     ++ "\n, " ++ show rest
 290 |   show NoClauses = "NONE"
 291 |
 292 | data ClauseType : PatClause (a :: todo) vars -> Type where
 293 |      ConClause : (0 isCon : IsConClause p) => ClauseType p
 294 |      VarClause : ClauseType p
 295 |
 296 | namesIn : List Name -> Pat -> Bool
 297 | namesIn pvars (PAs _ n p) = (n `elem` pvars) && namesIn pvars p
 298 | namesIn pvars (PCon _ _ _ _ ps) = all (namesIn pvars) ps
 299 | namesIn pvars (PTyCon _ _ _ ps) = all (namesIn pvars) ps
 300 | namesIn pvars (PArrow _ _ s t) = namesIn pvars s && namesIn pvars t
 301 | namesIn pvars (PDelay _ _ t p) = namesIn pvars t && namesIn pvars p
 302 | namesIn pvars (PLoc _ n) = n `elem` pvars
 303 | namesIn pvars _ = True
 304 |
 305 | namesFrom : Pat -> List Name
 306 | namesFrom (PAs _ n p) = n :: namesFrom p
 307 | namesFrom (PCon _ _ _ _ ps) = concatMap namesFrom ps
 308 | namesFrom (PTyCon _ _ _ ps) = concatMap namesFrom ps
 309 | namesFrom (PArrow _ _ s t) = namesFrom s ++ namesFrom t
 310 | namesFrom (PDelay _ _ t p) = namesFrom t ++ namesFrom p
 311 | namesFrom (PLoc _ n) = [n]
 312 | namesFrom _ = []
 313 |
 314 | clauseType : Phase -> (p : PatClause (a :: as) vars) -> ClauseType p
 315 | -- If it's irrelevant, a constructor, and there's no names we haven't seen yet
 316 | -- and don't see later, treat it as a variable
 317 | -- Or, if we're compiling for runtime we won't be able to split on it, so
 318 | -- also treat it as a variable
 319 | -- Or, if it's an under-applied constructor then do NOT attempt to split on it!
 320 | clauseType phase (MkPatClause pvars (MkInfo arg _ ty :: rest) pid rhs)
 321 |     = maybe VarClause (\isCon => ConClause @{isCon}) $ getClauseType phase arg ty
 322 |   where
 323 |     -- used when we are tempted to split on a constructor: is
 324 |     -- this actually a fully applied one?
 325 |     splitCon : Nat -> List Pat -> Maybe (So True)
 326 |     splitCon arity xs = toMaybe (arity == length xs) Oh
 327 |
 328 |     -- used to get the remaining clause types
 329 |     clauseType' : (p : Pat) -> Maybe (IsConPat p)
 330 |     clauseType' (PCon _ _ _ a xs) = splitCon a xs
 331 |     clauseType' (PTyCon _ _ a xs) = splitCon a xs
 332 |     clauseType' (PConst _ x)      = Just Oh
 333 |     clauseType' (PArrow _ _ s t)  = Just Oh
 334 |     clauseType' (PDelay {})       = Just Oh
 335 |     clauseType' _                 = Nothing
 336 |
 337 |     getClauseType : Phase -> (p : Pat) -> ArgType vars -> Maybe (IsConPat p)
 338 |     getClauseType (CompileTime cr) (PCon _ _ _ a xs) (Known r t)
 339 |         = if (isErased r && not (isErased cr) &&
 340 |              all (namesIn (pvars ++ concatMap namesFrom (getPatInfo rest))) xs)
 341 |              then Nothing
 342 |              else splitCon a xs
 343 |     getClauseType phase (PAs _ _ p) t = getClauseType phase p t
 344 |     getClauseType (CompileTime cr) l (Known r t)
 345 |         = if isErased r && not (isErased cr)
 346 |              then Nothing
 347 |              else clauseType' l
 348 |     getClauseType phase l (Known r t)
 349 |         = if isErased r
 350 |              then Nothing
 351 |              else clauseType' l
 352 |     getClauseType phase l _ = clauseType' l
 353 |
 354 | partition : {a, as, vars : _} ->
 355 |             Phase -> (ps : List01 ne (PatClause (a :: as) vars)) -> Partitions ps
 356 | partition phase [] = NoClauses
 357 | partition phase (x :: xs) with (partition phase xs)
 358 |   partition phase (x :: .(cs ++ ps)) | (ConClauses cs rest)
 359 |         = case clauseType phase x of
 360 |                ConClause => ConClauses (x :: cs) rest
 361 |                VarClause => VarClauses [x] (ConClauses cs rest)
 362 |   partition phase (x :: .(vs ++ ps)) | (VarClauses vs rest)
 363 |         = case clauseType phase x of
 364 |                ConClause => ConClauses [x] (VarClauses vs rest)
 365 |                VarClause => VarClauses (x :: vs) rest
 366 |   partition phase [x] | NoClauses
 367 |         = case clauseType phase x of
 368 |                ConClause => ConClauses [x] NoClauses
 369 |                VarClause => VarClauses [x] NoClauses
 370 |
 371 | data ConType : Type where
 372 |      CName : Name -> (tag : Int) -> ConType
 373 |      CDelay : ConType
 374 |      CConst : Constant -> ConType
 375 |
 376 | data Group : List Name -> -- pattern variables still to process
 377 |              Scoped where
 378 |      ConGroup : {newargs : _} ->
 379 |                 Name -> (tag : Int) ->
 380 |                 List01 True (PatClause (newargs ++ todo) (newargs ++ vars)) ->
 381 |                 Group todo vars
 382 |      DelayGroup : {tyarg, valarg : _} ->
 383 |                   List01 True (PatClause (tyarg :: valarg :: todo)
 384 |                                          (tyarg :: valarg :: vars)) ->
 385 |                   Group todo vars
 386 |      ConstGroup : Constant -> List01 True (PatClause todo vars) ->
 387 |                   Group todo vars
 388 |
 389 | covering
 390 | {vars : _} -> {todo : _} -> Show (Group todo vars) where
 391 |   show (ConGroup c t cs) = "Con " ++ show c ++ ": " ++ show cs
 392 |   show (DelayGroup cs) = "Delay: " ++ show cs
 393 |   show (ConstGroup c cs) = "Const " ++ show c ++ ": " ++ show cs
 394 |
 395 | data GroupMatch : ConType -> List Pat -> Group todo vars -> Type where
 396 |      ConMatch : {tag : Int} -> LengthMatch ps newargs ->
 397 |                 GroupMatch (CName n tag) ps
 398 |                   (ConGroup {newargs} n tag (MkPatClause pvs pats pid rhs :: rest))
 399 |      DelayMatch : GroupMatch CDelay []
 400 |                     (DelayGroup {tyarg} {valarg} (MkPatClause pvs pats pid rhs :: rest))
 401 |      ConstMatch : GroupMatch (CConst c) []
 402 |                     (ConstGroup c (MkPatClause pvs pats pid rhs :: rest))
 403 |      NoMatch : GroupMatch ct ps g
 404 |
 405 | checkGroupMatch : (c : ConType) -> (ps : List Pat) -> (g : Group todo vars) ->
 406 |                   GroupMatch c ps g
 407 | checkGroupMatch (CName x tag) ps (ConGroup {newargs} x' tag' (MkPatClause pvs pats pid rhs :: rest))
 408 |     = case checkLengthMatch ps newargs of
 409 |            Nothing => NoMatch
 410 |            Just prf => case (nameEq x x', decEq tag tag') of
 411 |                             (Just Refl, Yes Refl) => ConMatch prf
 412 |                             _ => NoMatch
 413 | checkGroupMatch (CName x tag) ps _ = NoMatch
 414 | checkGroupMatch CDelay [] (DelayGroup (MkPatClause pvs pats pid rhs :: rest))
 415 |     = DelayMatch
 416 | checkGroupMatch (CConst c) [] (ConstGroup c' (MkPatClause pvs pats pid rhs :: rest))
 417 |     = case constantEq c c' of
 418 |            Nothing => NoMatch
 419 |            Just Refl => ConstMatch
 420 | checkGroupMatch _ _ _ = NoMatch
 421 |
 422 | data PName : Type where
 423 |
 424 | nextName : {auto i : Ref PName Int} ->
 425 |            String -> Core Name
 426 | nextName root
 427 |     = do x <- get PName
 428 |          put PName (x + 1)
 429 |          pure (MN root x)
 430 |
 431 | nextNames : {vars : _} ->
 432 |             {auto i : Ref PName Int} ->
 433 |             {auto c : Ref Ctxt Defs} ->
 434 |             FC -> String -> List Pat -> Maybe (NF vars) ->
 435 |             Core (args ** (SizeOf args, NamedPats args (args ++ vars)))
 436 | nextNames fc root [] fty = pure ([] ** (zero, []))
 437 | nextNames fc root (p :: pats) fty
 438 |      = do defs <- get Ctxt
 439 |           empty <- clearDefs defs
 440 |           n <- nextName root
 441 |           let env = mkEnv fc vars
 442 |           fa_tys <- the (Core (Maybe (NF vars), ArgType vars)) $
 443 |               case fty of
 444 |                    Nothing => pure (Nothing, Unknown)
 445 |                    Just (NBind pfc _ (Pi _ c _ fargc) fsc) =>
 446 |                       do farg <- evalClosure defs fargc
 447 |                          case farg of
 448 |                               NErased {} =>
 449 |                                 pure (Just !(fsc defs (toClosure defaultOpts env (Ref pfc Bound n))),
 450 |                                       Unknown)
 451 |                               _ => pure (Just !(fsc defs (toClosure defaultOpts env (Ref pfc Bound n))),
 452 |                                          Known c !(quote empty env farg))
 453 |                    Just t =>
 454 |                       pure (Nothing, Stuck !(quote empty env t))
 455 |           (args ** (l, ps)) <- nextNames fc root pats (fst fa_tys)
 456 |           let argTy = case snd fa_tys of
 457 |                            Unknown => Unknown
 458 |                            Known rig t => Known rig (weakenNs (suc l) t)
 459 |                            Stuck t => Stuck (weakenNs (suc l) t)
 460 |           pure (n :: args ** (suc l, MkInfo p First argTy :: weaken ps))
 461 |
 462 | -- replace the prefix of patterns with 'pargs'
 463 | newPats : (pargs : List Pat) -> LengthMatch pargs ns ->
 464 |           NamedPats (ns ++ todo) vars ->
 465 |           NamedPats ns vars
 466 | newPats [] NilMatch rest = []
 467 | newPats (newpat :: xs) (ConsMatch w) (pi :: rest)
 468 |   = { pat := newpat } pi :: newPats xs w rest
 469 |
 470 | updateNames : List (Name, Pat) -> List (Name, Name)
 471 | updateNames = mapMaybe update
 472 |   where
 473 |     update : (Name, Pat) -> Maybe (Name, Name)
 474 |     update (n, PLoc fc p) = Just (p, n)
 475 |     update _ = Nothing
 476 |
 477 | updatePatNames : List (Name, Name) -> NamedPats todo vars -> NamedPats todo vars
 478 | updatePatNames _ [] = []
 479 | updatePatNames ns (pi :: ps)
 480 |     = { pat $= update } pi :: updatePatNames ns ps
 481 |   where
 482 |     update : Pat -> Pat
 483 |     update (PAs fc n p)
 484 |         = case lookup n ns of
 485 |                Nothing => PAs fc n (update p)
 486 |                Just n' => PAs fc n' (update p)
 487 |     update (PCon fc n i a ps) = PCon fc n i a (map update ps)
 488 |     update (PTyCon fc n a ps) = PTyCon fc n a (map update ps)
 489 |     update (PArrow fc x s t) = PArrow fc x (update s) (update t)
 490 |     update (PDelay fc r t p) = PDelay fc r (update t) (update p)
 491 |     update (PLoc fc n)
 492 |         = case lookup n ns of
 493 |                Nothing => PLoc fc n
 494 |                Just n' => PLoc fc n'
 495 |     update p = p
 496 |
 497 | groupCons : {a, vars, todo : _} ->
 498 |             {auto i : Ref PName Int} ->
 499 |             {auto ct : Ref Ctxt Defs} ->
 500 |             FC -> Name ->
 501 |             List Name ->
 502 |             (cs : List01 True (PatClause (a :: todo) vars)) ->
 503 |             (0 isCons : All IsConClause cs) =>
 504 |             Core (List01 True (Group todo vars))
 505 | groupCons fc fn pvars (x :: xs) {isCons = p :: ps}
 506 |     = foldlC (uncurry . gc) !(gc [] x p) $ pushIn xs ps
 507 |   where
 508 |     addConG : {vars', todo' : _} ->
 509 |               Name -> (tag : Int) ->
 510 |               List Pat -> NamedPats todo' vars' ->
 511 |               Int -> (rhs : Term vars') ->
 512 |               (acc : List01 ne (Group todo' vars')) ->
 513 |               Core (List01 True (Group todo' vars'))
 514 |     -- Group all the clauses that begin with the same constructor, and
 515 |     -- add new pattern arguments for each of that constructor's arguments.
 516 |     -- The type of 'ConGroup' ensures that we refer to the arguments by
 517 |     -- the same name in each of the clauses
 518 |     addConG n tag pargs pats pid rhs []
 519 |         = do cty <- if n == UN (Basic "->")
 520 |                       then pure $ NBind fc (MN "_" 0) (Pi fc top Explicit (MkNFClosure defaultOpts (mkEnv fc vars') (NType fc (MN "top" 0)))) $
 521 |                               (\d, a => pure $ NBind fc (MN "_" 1) (Pi fc top Explicit (MkNFClosure defaultOpts (mkEnv fc vars') (NErased fc Placeholder)))
 522 |                                 (\d, a => pure $ NType fc (MN "top" 0)))
 523 |                       else do defs <- get Ctxt
 524 |                               Just t <- lookupTyExact n (gamma defs)
 525 |                                    | Nothing => pure (NErased fc Placeholder)
 526 |                               nf defs (mkEnv fc vars') (embed t)
 527 |              (patnames ** (l, newargs)) <- nextNames fc "e" pargs (Just cty)
 528 |              -- Update non-linear names in remaining patterns (to keep
 529 |              -- explicit dependencies in types accurate)
 530 |              let pats' = updatePatNames (updateNames (zip patnames pargs))
 531 |                                         (weakenNs l pats)
 532 |              let clause = MkPatClause pvars (newargs ++ pats') pid (weakenNs l rhs)
 533 |              pure [ConGroup n tag [clause]]
 534 |     addConG n tag pargs pats pid rhs (g :: gs) with (checkGroupMatch (CName n tag) pargs g)
 535 |       addConG n tag pargs pats pid rhs
 536 |               (ConGroup n tag (MkPatClause pvars ps tid tm :: rest) :: gs) | ConMatch {newargs} lprf
 537 |         = do let newps = newPats pargs lprf ps
 538 |              let l = mkSizeOf newargs
 539 |              let pats' = updatePatNames (updateNames (zip newargs pargs))
 540 |                                         (weakenNs l pats)
 541 |              let newclause = MkPatClause pvars (newps ++ pats') pid (weakenNs l rhs)
 542 |              -- put the new clause at the end of the group, since we
 543 |              -- match the clauses top to bottom.
 544 |              pure $ ConGroup n tag (MkPatClause pvars ps tid tm :: rest ++ [newclause]) :: gs
 545 |       addConG n tag pargs pats pid rhs (g :: gs) | NoMatch
 546 |         = (g ::) <$> addConG n tag pargs pats pid rhs gs
 547 |
 548 |     -- This rather ugly special case is to deal with laziness, where Delay
 549 |     -- is like a constructor, but with a special meaning that it forces
 550 |     -- evaluation when case analysis reaches it (dealt with in the evaluator
 551 |     -- and compiler)
 552 |     addDelayG : {vars', todo' : _} ->
 553 |                 Pat -> Pat -> NamedPats todo' vars' ->
 554 |                 Int -> (rhs : Term vars') ->
 555 |                 (acc : List01 ne (Group todo' vars')) ->
 556 |                 Core (List01 True (Group todo' vars'))
 557 |     addDelayG pty parg pats pid rhs []
 558 |         = do let dty = NBind fc (MN "a" 0) (Pi fc erased Explicit (MkNFClosure defaultOpts (mkEnv fc vars') (NType fc (MN "top" 0)))) $
 559 |                         (\d, a =>
 560 |                             do a' <- evalClosure d a
 561 |                                pure (NBind fc (MN "x" 0) (Pi fc top Explicit a)
 562 |                                        (\dv, av => pure (NDelayed fc LUnknown a'))))
 563 |              ([tyname, argname] ** (l, newargs)) <- nextNames fc "e" [pty, parg]
 564 |                                                   (Just dty)
 565 |                 | _ => throw (InternalError "Error compiling Delay pattern match")
 566 |              let pats' = updatePatNames (updateNames [(tyname, pty),
 567 |                                                       (argname, parg)])
 568 |                                         (weakenNs l pats)
 569 |              let clause = MkPatClause pvars (newargs ++ pats') pid (weakenNs l rhs)
 570 |              pure [DelayGroup [clause]]
 571 |     addDelayG pty parg pats pid rhs (g :: gs) with (checkGroupMatch CDelay [] g)
 572 |       addDelayG pty parg pats pid rhs
 573 |           (DelayGroup (MkPatClause pvars ps tid tm :: rest) :: gs) | DelayMatch {tyarg} {valarg}
 574 |         = do let l = mkSizeOf [tyarg, valarg]
 575 |              let newps = newPats [pty, parg] (ConsMatch (ConsMatch NilMatch)) ps
 576 |              let pats' = updatePatNames (updateNames [(tyarg, pty),
 577 |                                                       (valarg, parg)])
 578 |                                         (weakenNs l pats)
 579 |              let newclause = MkPatClause pvars (newps ++ pats') pid (weakenNs l rhs)
 580 |              pure $ DelayGroup (MkPatClause pvars ps tid tm :: rest ++ [newclause]) :: gs
 581 |       addDelayG pty parg pats pid rhs (g :: gs) | NoMatch
 582 |         = (g ::) <$> addDelayG pty parg pats pid rhs gs
 583 |
 584 |     addConstG : {vars', todo' : _} ->
 585 |                 Constant -> NamedPats todo' vars' ->
 586 |                 Int -> (rhs : Term vars') ->
 587 |                 (acc : List01 ne (Group todo' vars')) ->
 588 |                 Core (List01 True (Group todo' vars'))
 589 |     addConstG c pats pid rhs []
 590 |           = pure [ConstGroup c [MkPatClause pvars pats pid rhs]]
 591 |     addConstG c pats pid rhs (g :: gs) with (checkGroupMatch (CConst c) [] g)
 592 |       addConstG c pats pid rhs
 593 |               (ConstGroup c (MkPatClause pvars ps tid tm :: rest) :: gs) | ConstMatch
 594 |         = do let newclause = MkPatClause pvars pats pid rhs
 595 |              pure $ ConstGroup c (MkPatClause pvars ps tid tm :: rest ++ [newclause]) :: gs
 596 |       addConstG c pats pid rhs (g :: gs) | NoMatch
 597 |         = (g ::) <$> addConstG c pats pid rhs gs
 598 |
 599 |     addGroup : {vars, todo, idx : _} ->
 600 |                (pat : Pat) -> (0 _ : IsConPat pat) =>
 601 |                (0 p : IsVar nm idx vars) ->
 602 |                NamedPats todo vars -> Int -> Term vars ->
 603 |                List01 ne (Group todo vars) ->
 604 |                Core (List01 True (Group todo vars))
 605 |     -- In 'As' replace the name on the RHS with a reference to the
 606 |     -- variable we're doing the case split on
 607 |     addGroup (PAs fc n p) pprf pats pid rhs acc
 608 |          = addGroup p pprf pats pid (substName n (Local fc (Just True) idx pprf) rhs) acc
 609 |     addGroup (PCon cfc n t a pargs) pprf pats pid rhs acc
 610 |          = if a == length pargs
 611 |               then addConG n t pargs pats pid rhs acc
 612 |               else throw (CaseCompile cfc fn (NotFullyApplied n))
 613 |     addGroup (PTyCon cfc n a pargs) pprf pats pid rhs acc
 614 |          = if a == length pargs
 615 |            then addConG n 0 pargs pats pid rhs acc
 616 |            else throw (CaseCompile cfc fn (NotFullyApplied n))
 617 |     addGroup (PArrow _ _ s t) pprf pats pid rhs acc
 618 |          = addConG (UN $ Basic "->") 0 [s, t] pats pid rhs acc
 619 |     -- Go inside the delay; we'll flag the case as needing to force its
 620 |     -- scrutinee (need to check in 'caseGroups below)
 621 |     addGroup (PDelay _ _ pty parg) pprf pats pid rhs acc
 622 |          = addDelayG pty parg pats pid rhs acc
 623 |     addGroup (PConst _ c) pprf pats pid rhs acc
 624 |          = addConstG c pats pid rhs acc
 625 |
 626 |     gc : {a, vars, todo : _} ->
 627 |          List01 ne (Group todo vars) ->
 628 |          (p : PatClause (a :: todo) vars) ->
 629 |          (0 _ : IsConClause p) ->
 630 |          Core (List01 True (Group todo vars))
 631 |     gc acc (MkPatClause _ (MkInfo pat pprf _ :: pats) pid rhs) isCon
 632 |         = addGroup pat pprf pats pid rhs acc
 633 |
 634 | getFirstPat : NamedPats (p :: ps) ns -> Pat
 635 | getFirstPat (p :: _) = pat p
 636 |
 637 | getFirstArgType : NamedPats (p :: ps) ns -> ArgType ns
 638 | getFirstArgType (p :: _) = argType p
 639 |
 640 | ||| Store scores alongside rows of named patterns. These scores are used to determine
 641 | ||| which column of patterns to switch on first. One score per column.
 642 | data ScoredPats : List Name -> Scoped where
 643 |      Scored : List01 True (NamedPats (p :: ps) ns) -> Vect (length (p :: ps)) Int -> ScoredPats (p :: ps) ns
 644 |
 645 | {ps : _} -> Show (ScoredPats ps ns) where
 646 |   show (Scored xs ys) = (show ps) ++ "//" ++ (show ys)
 647 |
 648 | zeroedScore : {ps : _} -> List01 True (NamedPats (p :: ps) ns) -> ScoredPats (p :: ps) ns
 649 | zeroedScore nps = Scored nps (replicate (S $ length ps) 0)
 650 |
 651 | ||| Helper to find a single highest scoring name (or none at all) while
 652 | ||| retaining the context of all names processed.
 653 | highScore : {prev : List Name} ->
 654 |             (names : Scope) ->
 655 |             (scores : Vect (length names) Int) ->
 656 |             (highVal : Int) ->
 657 |             (highIdx : (n ** NVar n (prev ++ names))) -> -- TODO should be `names <>< prev`
 658 |             (duped : Bool) ->
 659 |             Maybe (n ** NVar n (prev ++ names))
 660 | highScore [] [] high idx True = Nothing
 661 | highScore [] [] high idx False = Just idx
 662 | highScore (x :: xs) (y :: ys) high idx duped =
 663 |   let next = highScore {prev = prev `snoc` x} xs ys
 664 |       prf = appendAssociative prev [x] xs
 665 |   in  rewrite prf in
 666 |         case compare y high of
 667 |              LT => next high (rewrite sym $ prf in idx) duped
 668 |              EQ => next high (rewrite sym $ prf in idx) True
 669 |              GT => next y (x ** rewrite sym $ prf in weakenNVar (mkSizeOf prev) (MkNVar First)) False
 670 |
 671 | ||| Get the index of the highest scoring column if there is one.
 672 | ||| If no column has a higher score than all other columns then
 673 | ||| the result is Nothing indicating we need to apply more scoring
 674 | ||| to break the tie.
 675 | ||| Suggested heuristic application order: f, b, a.
 676 | highScoreIdx : {p : _} -> {ps : _} -> ScoredPats (p :: ps) ns -> Maybe (n ** NVar n (p :: ps))
 677 | highScoreIdx (Scored xs (y :: ys)) = highScore {prev = []} (p :: ps) (y :: ys) (y - 1) (p ** MkNVar First) False
 678 |
 679 | ||| Apply the penalty function to the head constructor's
 680 | ||| arity. Produces 0 for all non-head-constructors.
 681 | headConsPenalty : (penality : Nat -> Int) -> Pat -> Int
 682 | headConsPenalty p (PAs _ _ w)             = headConsPenalty p w
 683 | headConsPenalty p (PCon _ n _ arity pats) = p arity
 684 | headConsPenalty p (PTyCon _ _ arity _)    = p arity
 685 | headConsPenalty _ (PConst {})             = 0
 686 | headConsPenalty _ (PArrow {})             = 0
 687 | headConsPenalty p (PDelay _ _ _ w)        = headConsPenalty p w
 688 | headConsPenalty _ (PLoc {})               = 0
 689 | headConsPenalty _ (PUnmatchable {})       = 0
 690 |
 691 | splitColumn : (nps : List01 True (NamedPats (p :: ps) ns)) -> (Vect (length nps) (PatInfo p ns), List01 True (NamedPats ps ns))
 692 | splitColumn [(w :: ws)] = ([w], [ws])
 693 | splitColumn ((w :: ws) :: nps@(_ :: _)) = bimap (w ::) (ws ::) $ splitColumn nps
 694 |
 695 | ||| Apply the given function that scores a pattern to all patterns and then
 696 | ||| sum up the column scores and add to the ScoredPats passed in.
 697 | consScoreHeuristic : {ps : _} -> (scorePat : Pat -> Int) -> ScoredPats ps ns -> ScoredPats ps ns
 698 | consScoreHeuristic scorePat (Scored xs ys) =
 699 |   let columnScores = scoreColumns xs
 700 |       ys' = zipWith (+) ys columnScores
 701 |   in  Scored xs ys'
 702 |   where
 703 |     scoreColumns : {ps' : _} -> (nps : List01 True (NamedPats ps' ns)) -> Vect (length ps') Int
 704 |     scoreColumns {ps' = []} nps = []
 705 |     scoreColumns {ps' = w :: ws} nps =
 706 |       let (col, nps') = splitColumn nps
 707 |        in sum (scorePat . pat <$> col) :: scoreColumns nps'
 708 |
 709 | ||| Add 1 to each non-default pat in the first row.
 710 | ||| This favors constructive matching first and reduces tree depth on average.
 711 | heuristicF : {ps : _} -> ScoredPats (p :: ps) ns -> ScoredPats (p :: ps) ns
 712 | heuristicF (Scored (x :: xs) ys) =
 713 |   let columnScores = scores x
 714 |       ys' = zipWith (+) ys columnScores
 715 |   in  Scored (x :: xs) ys'
 716 |   where
 717 |     isBlank : Pat -> Bool
 718 |     isBlank (PLoc {}) = True
 719 |     isBlank _ = False
 720 |
 721 |     scores : NamedPats ps' ns' -> Vect (length ps') Int
 722 |     scores [] = []
 723 |     scores (y :: ys) = let score : Int = if isBlank (pat y) then 0 else 1
 724 |                        in  score :: scores ys
 725 |
 726 | ||| Subtract 1 from each column for each pat that represents a head constructor.
 727 | ||| This favors pats that produce less branching.
 728 | heuristicB : {ps : _} -> ScoredPats ps ns -> ScoredPats ps ns
 729 | heuristicB = consScoreHeuristic (headConsPenalty (\arity => if arity == 0 then 0 else -1))
 730 |
 731 | ||| Subtract the sum of the arities of constructors in each column.
 732 | heuristicA : {ps : _} -> ScoredPats ps ns -> ScoredPats ps ns
 733 | heuristicA = consScoreHeuristic (headConsPenalty (negate . cast))
 734 |
 735 | applyHeuristics : {p : _} ->
 736 |                   {ps : _} ->
 737 |                   ScoredPats (p :: ps) ns ->
 738 |                   List (ScoredPats (p :: ps) ns -> ScoredPats (p :: ps) ns) ->
 739 |                   Maybe (n ** NVar n (p :: ps))
 740 | applyHeuristics x [] = highScoreIdx x
 741 | applyHeuristics x (f :: fs) = highScoreIdx x <|> applyHeuristics (f x) fs
 742 |
 743 | ||| Based only on the heuristic-score of columns, get the index of
 744 | ||| the column that should be processed next.
 745 | |||
 746 | ||| The scoring is inspired by results from the paper:
 747 | ||| http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf
 748 | nextIdxByScore : {p : _} ->
 749 |                  {ps : _} ->
 750 |                  (useHeuristics : Bool) ->
 751 |                  Phase ->
 752 |                  List01 True (NamedPats (p :: ps) ns) ->
 753 |                  (n ** NVar n (p :: ps))
 754 | nextIdxByScore False _ _            = (_ ** (MkNVar First))
 755 | nextIdxByScore _ (CompileTime _) _  = (_ ** (MkNVar First))
 756 | nextIdxByScore True RunTime xs      =
 757 |   fromMaybe (_ ** (MkNVar First)) $
 758 |     applyHeuristics (zeroedScore xs) [heuristicF, heuristicB, heuristicA]
 759 |
 760 | -- Check whether all the initial patterns have the same concrete, known
 761 | -- and matchable type, which is multiplicity > 0.
 762 | -- If so, it's okay to match on it
 763 | sameType : {ns : _} ->
 764 |            {auto c : Ref Ctxt Defs} ->
 765 |            FC -> Phase -> Name ->
 766 |            Env Term ns -> List01 ne (NamedPats (p :: ps) ns) ->
 767 |            Core ()
 768 | sameType fc phase fn env [] = pure ()
 769 | sameType {ns} fc phase fn env (p :: xs)
 770 |     = do defs <- get Ctxt
 771 |          case getFirstArgType p of
 772 |               Known _ t => sameTypeAs phase
 773 |                                       !(nf defs env t)
 774 |                                       (map getFirstArgType xs)
 775 |               ty => throw (CaseCompile fc fn DifferingTypes)
 776 |   where
 777 |     firstPat : NamedPats (np :: nps) ns -> Pat
 778 |     firstPat (pinf :: _) = pat pinf
 779 |
 780 |     headEq : NF ns -> NF ns -> Phase -> Bool
 781 |     headEq (NBind _ _ (Pi {}) _) (NBind _ _ (Pi {}) _) _ = True
 782 |     headEq (NTCon _ n _ _) (NTCon _ n' _ _) _ = n == n'
 783 |     headEq (NPrimVal _ c) (NPrimVal _ c') _ = c == c'
 784 |     headEq (NType {}) (NType {}) _ = True
 785 |     headEq (NApp _ (NRef _ n) _) (NApp _ (NRef _ n') _) RunTime = n == n'
 786 |     headEq (NErased _ (Dotted x)) y ph = headEq x y ph
 787 |     headEq x (NErased _ (Dotted y)) ph = headEq x y ph
 788 |     headEq (NErased {}) _ RunTime = True
 789 |     headEq _ (NErased {}) RunTime = True
 790 |     headEq _ _ _ = False
 791 |
 792 |     sameTypeAs : forall ne. Phase -> NF ns -> List01 ne (ArgType ns) -> Core ()
 793 |     sameTypeAs _ ty [] = pure ()
 794 |     sameTypeAs ph ty (Known r t :: xs) =
 795 |          do defs <- get Ctxt
 796 |             if headEq ty !(nf defs env t) phase
 797 |                then sameTypeAs ph ty xs
 798 |                else throw (CaseCompile fc fn DifferingTypes)
 799 |     sameTypeAs p ty _ = throw (CaseCompile fc fn DifferingTypes)
 800 |
 801 | -- Check whether all the initial patterns are the same, or are all a variable.
 802 | -- If so, we'll match it to refine later types and move on
 803 | samePat : List01 True (NamedPats (p :: ps) ns) -> Bool
 804 | samePat (pi :: xs)
 805 |     = samePatAs (dropAs (getFirstPat pi))
 806 |                 (map (dropAs . getFirstPat) xs)
 807 |   where
 808 |     dropAs : Pat -> Pat
 809 |     dropAs (PAs _ _ p) = p
 810 |     dropAs p = p
 811 |
 812 |     samePatAs : Pat -> List01 ne Pat -> Bool
 813 |     samePatAs p [] = True
 814 |     samePatAs (PTyCon fc n a args) (PTyCon _ n' _ _ :: ps)
 815 |         = n == n' && samePatAs (PTyCon fc n a args) ps
 816 |     samePatAs (PCon fc n t a args) (PCon _ n' t' _ _ :: ps)
 817 |         = n == n' && t == t' && samePatAs (PCon fc n t a args) ps
 818 |     samePatAs (PConst fc c) (PConst _ c' :: ps)
 819 |         = c == c' && samePatAs (PConst fc c) ps
 820 |     samePatAs (PArrow fc x s t) (PArrow _ _ s' t' :: ps)
 821 |         = samePatAs (PArrow fc x s t) ps
 822 |     samePatAs (PDelay fc r t p) (PDelay _ _ _ _ :: ps)
 823 |         = samePatAs (PDelay fc r t p) ps
 824 |     samePatAs (PLoc fc n) (PLoc _ _ :: ps) = samePatAs (PLoc fc n) ps
 825 |     samePatAs x y = False
 826 |
 827 | getScore : {ns : _} ->
 828 |            {auto c : Ref Ctxt Defs} ->
 829 |            FC -> Phase -> Name ->
 830 |            List01 True (NamedPats (p :: ps) ns) ->
 831 |            Core (Either CaseError ())
 832 | getScore fc phase name npss
 833 |     = catch (Right () <$ sameType fc phase name (mkEnv fc ns) npss)
 834 |             $ \case
 835 |               CaseCompile _ _ err => pure $ Left err
 836 |               err => throw err
 837 |
 838 | ||| Pick the leftmost matchable thing with all constructors in the
 839 | ||| same family, or all variables, or all the same type constructor.
 840 | pickNextViable : {p, ns, ps : _} ->
 841 |                  {auto c : Ref Ctxt Defs} ->
 842 |                  FC -> Phase -> Name -> List01 True (NamedPats (p :: ps) ns) ->
 843 |                  Core (n ** NVar n (p :: ps))
 844 | -- last possible variable
 845 | pickNextViable {ps = []} fc phase fn npss
 846 |     = if samePat npss
 847 |          then pure (_ ** MkNVar First)
 848 |          else do Right () <- getScore fc phase fn npss
 849 |                        | Left err => throw (CaseCompile fc fn err)
 850 |                  pure (_ ** MkNVar First)
 851 | pickNextViable {ps = q :: qs} fc phase fn npss
 852 |     = if samePat npss
 853 |          then pure (_ ** MkNVar First)
 854 |          else case !(getScore fc phase fn npss) of
 855 |                    Right () => pure (_ ** MkNVar First)
 856 |                    _ => do (_ ** MkNVar var) <- pickNextViable fc phase fn (map tail npss)
 857 |                            pure (_ ** MkNVar (Later var))
 858 |
 859 | moveFirst : {idx : Nat} -> (0 el : IsVar nm idx ps) -> NamedPats ps ns ->
 860 |             NamedPats (nm :: dropIsVar ps el) ns
 861 | moveFirst el nps = getPat el nps :: dropPat el nps
 862 |
 863 | shuffleVars : {idx : Nat} -> (0 el : IsVar nm idx todo) -> PatClause todo vars ->
 864 |               PatClause (nm :: dropIsVar todo el) vars
 865 | shuffleVars First orig@(MkPatClause pvars lhs pid rhs) = orig -- no-op
 866 | shuffleVars el (MkPatClause pvars lhs pid rhs)
 867 |     = MkPatClause pvars (moveFirst el lhs) pid rhs
 868 |
 869 | mutual
 870 |   {- 'PatClause' contains a list of patterns still to process (that's the
 871 |      "todo") and a right hand side with the variables we know about "vars".
 872 |      So "match" builds the remainder of the case tree for
 873 |      the unprocessed patterns. "err" is the tree for when the patterns don't
 874 |      cover the input (i.e. the "fallthrough" pattern, which at the top
 875 |      level will be an error). -}
 876 |   match : {vars, todo : _} ->
 877 |           {auto i : Ref PName Int} ->
 878 |           {auto c : Ref Ctxt Defs} ->
 879 |           FC -> Name -> Phase ->
 880 |           List01 True (PatClause todo vars) ->
 881 |           IMaybe ne (CaseTree vars) ->
 882 |           Core (CaseTree vars)
 883 |   -- Before 'partition', reorder the arguments so that the one we
 884 |   -- inspect next has a concrete type that is the same in all cases, and
 885 |   -- has the most distinct constructors (via pickNextViable)
 886 |   match {todo = _ :: _} fc fn phase clauses err
 887 |       = do let nps = getNPs <$> clauses
 888 |            let (_ ** (MkNVar next)) = nextIdxByScore (caseTreeHeuristics !getSession) phase nps
 889 |            let prioritizedClauses = shuffleVars next <$> clauses
 890 |            (n ** MkNVar next') <- pickNextViable fc phase fn (getNPs <$> prioritizedClauses)
 891 |            log "compile.casetree.pick" 25 $ "Picked " ++ show n ++ " as the next split"
 892 |            let clauses' = shuffleVars next' <$> prioritizedClauses
 893 |            log "compile.casetree.clauses" 25 $
 894 |              unlines ("Using clauses:" :: map (("  " ++) . show) (forget clauses'))
 895 |            let ps = partition phase clauses'
 896 |            log "compile.casetree.partition" 25 $ "Got Partition:\n" ++ show ps
 897 |            Just mix <- mixture fc fn phase ps err
 898 |            log "compile.casetree.intermediate" 25 $ "match: new case tree " ++ show mix
 899 |            pure mix
 900 |   match {todo = []} fc fn phase (MkPatClause pvars [] pid (Erased _ Impossible) :: _) err
 901 |        = pure Impossible
 902 |   match {todo = []} fc fn phase (MkPatClause pvars [] pid rhs :: _) err
 903 |        = pure $ STerm pid rhs
 904 |
 905 |   caseGroups : {pvar, vars, todo : _} ->
 906 |                {auto i : Ref PName Int} ->
 907 |                {auto c : Ref Ctxt Defs} ->
 908 |                FC -> Name -> Phase ->
 909 |                {idx : Nat} -> (0 p : IsVar pvar idx vars) -> Term vars ->
 910 |                List01 True (Group todo vars) -> IMaybe ne (CaseTree vars) ->
 911 |                Core (CaseTree vars)
 912 |   caseGroups fc fn phase el ty gs errorCase
 913 |       = Case idx el (resolveNames vars ty) <$> altGroups gs
 914 |     where
 915 |       altGroups : forall ne. List01 ne (Group todo vars) -> Core (List (CaseAlt vars))
 916 |       altGroups [] = pure $ toList $ DefaultCase <$> errorCase
 917 |       altGroups (ConGroup {newargs} cn tag rest :: cs)
 918 |           = do crest <- match fc fn phase rest (map (weakenNs (mkSizeOf newargs)) errorCase)
 919 |                cs' <- altGroups cs
 920 |                pure (ConCase cn tag newargs crest :: cs')
 921 |       altGroups (DelayGroup {tyarg} {valarg} rest :: cs)
 922 |           = do crest <- match fc fn phase rest (map (weakenNs (mkSizeOf [tyarg, valarg])) errorCase)
 923 |                cs' <- altGroups cs
 924 |                pure (DelayCase tyarg valarg crest :: cs')
 925 |       altGroups (ConstGroup c rest :: cs)
 926 |           = do crest <- match fc fn phase rest errorCase
 927 |                cs' <- altGroups cs
 928 |                pure (ConstCase c crest :: cs')
 929 |
 930 |   conRule : {a, vars, todo : _} ->
 931 |             {auto i : Ref PName Int} ->
 932 |             {auto c : Ref Ctxt Defs} ->
 933 |             FC -> Name -> Phase ->
 934 |             (cs : List01 True (PatClause (a :: todo) vars)) ->
 935 |             (0 isCons : All IsConClause cs) =>
 936 |             IMaybe ne (CaseTree vars) ->
 937 |             Core (CaseTree vars)
 938 |   -- ASSUMPTION, not expressed in the type, that the patterns all have
 939 |   -- the same variable (pprf) for the first argument. If not, the result
 940 |   -- will be a broken case tree... so we should find a way to express this
 941 |   -- in the type if we can.
 942 |   conRule {a} fc fn phase cs@(MkPatClause pvars (MkInfo pat pprf fty :: pats) pid rhs :: rest) err
 943 |       = do Element refinedcs _ <- pullOut <$> traverseList01 (substInClause fc) (pushIn cs isCons)
 944 |            groups <- groupCons fc fn pvars refinedcs
 945 |            ty <- case fty of
 946 |                       Known _ t => pure t
 947 |                       _ => throw (CaseCompile fc fn UnknownType)
 948 |            caseGroups fc fn phase pprf ty groups err
 949 |
 950 |   varRule : {a, vars, todo : _} ->
 951 |             {auto i : Ref PName Int} ->
 952 |             {auto c : Ref Ctxt Defs} ->
 953 |             FC -> Name -> Phase ->
 954 |             List01 True (PatClause (a :: todo) vars) ->
 955 |             IMaybe ne (CaseTree vars) ->
 956 |             Core (CaseTree vars)
 957 |   varRule fc fn phase cs err
 958 |       = do alts' <- traverseList01 updateVar cs
 959 |            match fc fn phase alts' err
 960 |     where
 961 |       updateVar : PatClause (a :: todo) vars -> Core (PatClause todo vars)
 962 |       -- replace the name with the relevant variable on the rhs
 963 |       updateVar (MkPatClause pvars (MkInfo (PLoc pfc n) prf fty :: pats) pid rhs)
 964 |           = pure $ MkPatClause (n :: pvars)
 965 |                         !(substInPats fc a (Local pfc (Just False) _ prf) pats)
 966 |                         pid (substName n (Local pfc (Just False) _ prf) rhs)
 967 |       -- If it's an as pattern, replace the name with the relevant variable on
 968 |       -- the rhs then continue with the inner pattern
 969 |       updateVar (MkPatClause pvars (MkInfo (PAs pfc n pat) prf fty :: pats) pid rhs)
 970 |           = do pats' <- substInPats fc a (mkTerm _ pat) pats
 971 |                let rhs' = substName n (Local pfc (Just True) _ prf) rhs
 972 |                updateVar (MkPatClause pvars (MkInfo pat prf fty :: pats') pid rhs')
 973 |       -- match anything, name won't appear in rhs but need to update
 974 |       -- LHS pattern types based on what we've learned
 975 |       updateVar (MkPatClause pvars (MkInfo pat prf fty :: pats) pid rhs)
 976 |           = pure $ MkPatClause pvars
 977 |                         !(substInPats fc a (mkTerm vars pat) pats) pid rhs
 978 |
 979 |   mixture : {a, vars, todo : _} ->
 980 |             {auto i : Ref PName Int} ->
 981 |             {auto c : Ref Ctxt Defs} ->
 982 |             {ps : List01 ne (PatClause (a :: todo) vars)} ->
 983 |             FC -> Name -> Phase ->
 984 |             Partitions ps ->
 985 |             IMaybe neErr (CaseTree vars) ->
 986 |             Core (IMaybe (ne || neErr) (CaseTree vars))
 987 |   mixture fc fn phase (ConClauses cs rest) err
 988 |       = do fallthrough <- mixture fc fn phase rest err
 989 |            Just <$> conRule fc fn phase cs fallthrough
 990 |   mixture fc fn phase (VarClauses vs rest) err
 991 |       = do fallthrough <- mixture fc fn phase rest err
 992 |            Just <$> varRule fc fn phase vs fallthrough
 993 |   mixture fc fn phase NoClauses err
 994 |       = pure err
 995 |
 996 | export
 997 | mkPat : {auto c : Ref Ctxt Defs} ->
 998 |         (matchable : Bool) -> List Pat -> ClosedTerm -> ClosedTerm -> Core Pat
 999 | mkPat _ [] orig (Ref fc Bound n) = pure $ PLoc fc n
1000 | mkPat True args orig (Ref fc (DataCon t a) n) = pure $ PCon fc n t a args
1001 | mkPat True args orig (Ref fc (TyCon a) n) = pure $ PTyCon fc n a args
1002 | mkPat True args orig (Ref fc Func n)
1003 |   = do prims <- getPrimitiveNames
1004 |        mtm <- normalisePrims (const True) isPConst True prims n args orig Env.empty
1005 |        case mtm of
1006 |          Just tm => if tm /= orig -- check we made progress; if there's an
1007 |                                   -- unresolved interface, we might be stuck
1008 |                                   -- and we'd loop forever
1009 |                        then mkPat True [] tm tm
1010 |                        else -- Possibly this should be an error instead?
1011 |                             pure $ PUnmatchable (getLoc orig) orig
1012 |          Nothing =>
1013 |            do log "compile.casetree" 10 $
1014 |                 "Unmatchable function: " ++ show n
1015 |               pure $ PUnmatchable (getLoc orig) orig
1016 | mkPat True args orig (Bind fc x (Pi _ _ _ s) t)
1017 |     -- For (b:Nat) -> b, the codomain looks like b [__], but we want `b` as the pattern
1018 |     = case subst (Erased fc Placeholder) t of
1019 |         App _ t'@(Ref fc Bound n) (Erased {}) => pure $ PArrow fc x !(mkPat True [] s s) !(mkPat False [] t' t')
1020 |         t' => pure $ PArrow fc x !(mkPat True [] s s) !(mkPat False [] t' t')
1021 | mkPat True args orig (App fc fn arg)
1022 |     = do parg <- mkPat True [] arg arg
1023 |          mkPat True (parg :: args) orig fn
1024 | mkPat True args orig (As fc _ (Ref _ Bound n) ptm)
1025 |     = pure $ PAs fc n !(mkPat True [] ptm ptm)
1026 | mkPat True args orig (As fc _ _ ptm)
1027 |     = mkPat True [] orig ptm
1028 | mkPat True args orig (TDelay fc r ty p)
1029 |     = pure $ PDelay fc r !(mkPat True [] orig ty) !(mkPat True [] orig p)
1030 | mkPat True args orig (PrimVal fc $ PrT c) -- Primitive type constant
1031 |     = pure $ PTyCon fc (UN (Basic $ show c)) 0 []
1032 | mkPat True args orig (PrimVal fc c) = pure $ PConst fc c -- Non-type constant
1033 | mkPat True args orig (TType fc _) = pure $ PTyCon fc (UN $ Basic "Type") 0 []
1034 | mkPat _ args orig tm
1035 |    = do log "compile.casetree" 10 $
1036 |           "Catchall: marking " ++ show tm ++ " as unmatchable"
1037 |         pure $ PUnmatchable (getLoc orig) orig
1038 |
1039 | export
1040 | argToPat : {auto c : Ref Ctxt Defs} -> ClosedTerm -> Core Pat
1041 | argToPat tm = mkPat True [] tm tm
1042 |
1043 | mkPatClause : {auto c : Ref Ctxt Defs} ->
1044 |               FC -> Name ->
1045 |               (args : Scope) -> ClosedTerm ->
1046 |               Int -> (List Pat, ClosedTerm) ->
1047 |               Core (PatClause args args)
1048 | mkPatClause fc fn args ty pid (ps, rhs)
1049 |     = maybe (throw (CaseCompile fc fn DifferingArgNumbers))
1050 |             (\eq =>
1051 |                do defs <- get Ctxt
1052 |                   nty <- nf defs Env.empty ty
1053 |                   ns <- mkNames args ps eq (Just nty)
1054 |                   log "compile.casetree" 20 $
1055 |                     "Make pat clause for names " ++ show ns
1056 |                      ++ " in LHS " ++ show ps
1057 |                   pure (MkPatClause [] ns pid
1058 |                           (rewrite sym (appendNilRightNeutral args) in
1059 |                                    (weakenNs (mkSizeOf args) rhs))))
1060 |             (checkLengthMatch args ps)
1061 |   where
1062 |     mkNames : (vars : Scope) -> (ps : List Pat) ->
1063 |               LengthMatch vars ps -> Maybe (NF []) ->
1064 |               Core (NamedPats vars vars)
1065 |     mkNames [] [] NilMatch fty = pure []
1066 |     mkNames (arg :: args) (p :: ps) (ConsMatch eq) fty
1067 |         = do defs <- get Ctxt
1068 |              empty <- clearDefs defs
1069 |              fa_tys <- the (Core (Maybe _, ArgType _)) $
1070 |                 case fty of
1071 |                      Nothing => pure (Nothing, CaseBuilder.Unknown)
1072 |                      Just (NBind pfc _ (Pi _ c _ farg) fsc) =>
1073 |                         pure (Just !(fsc defs (toClosure defaultOpts [] (Ref pfc Bound arg))),
1074 |                               Known c (embed !(quote empty [] farg)))
1075 |                      Just t =>
1076 |                         pure (Nothing, Stuck (embed !(quote empty [] t)))
1077 |              pure (MkInfo p First (Builtin.snd fa_tys)
1078 |                       :: weaken !(mkNames args ps eq (Builtin.fst fa_tys)))
1079 |
1080 | export
1081 | patCompile : {auto c : Ref Ctxt Defs} ->
1082 |              FC -> Name -> Phase ->
1083 |              ClosedTerm -> List01 True (List Pat, ClosedTerm) ->
1084 |              Core (args ** CaseTree args)
1085 | patCompile fc fn phase ty (p :: ps)
1086 |     = do let (ns ** n) = getNames 0 (fst p)
1087 |          pats <- mkPatClausesFrom 0 ns (p :: ps)
1088 |          -- low verbosity level: pretty print fully resolved names
1089 |          logC "compile.casetree" 5 $ do
1090 |            pats <- traverse toFullNames $ forget pats
1091 |            pure $ "Pattern clauses:\n"
1092 |                 ++ show (indent 2 $ vcat $ pretty <$> pats)
1093 |          -- higher verbosity: dump the raw data structure
1094 |          log "compile.casetree" 10 $ show pats
1095 |          i <- newRef PName (the Int 0)
1096 |          cases <- match fc fn phase pats Nothing
1097 |          pure (_ ** cases)
1098 |   where
1099 |     mkPatClausesFrom : Int -> (args : Scope) ->
1100 |                        List01 ne (List Pat, ClosedTerm) ->
1101 |                        Core (List01 ne (PatClause args args))
1102 |     mkPatClausesFrom i ns [] = pure []
1103 |     mkPatClausesFrom i ns (p :: ps)
1104 |         = do p' <- mkPatClause fc fn ns ty i p
1105 |              ps' <- mkPatClausesFrom (i + 1) ns ps
1106 |              pure (p' :: ps')
1107 |
1108 |     getNames : Int -> List Pat -> (ns : Scope ** SizeOf ns)
1109 |     getNames i [] = ([] ** zero)
1110 |     getNames i (x :: xs) =
1111 |       let (ns ** n) = getNames (i + 1) xs
1112 |       in (MN "arg" i :: ns ** suc n)
1113 |
1114 | toPatClause : {auto c : Ref Ctxt Defs} ->
1115 |               FC -> Name -> (ClosedTerm, ClosedTerm) ->
1116 |               Core (List Pat, ClosedTerm)
1117 | toPatClause fc n (lhs, rhs)
1118 |     = case getFnArgs lhs of
1119 |            (Ref ffc Func fn, args)
1120 |               => do defs <- get Ctxt
1121 |                     (np, _) <- getPosition n (gamma defs)
1122 |                     (fnp, _) <- getPosition fn (gamma defs)
1123 |                     if np == fnp
1124 |                        then pure (!(traverse argToPat args), rhs)
1125 |                        else throw (GenericMsg ffc ("Wrong function name in pattern LHS " ++ show (n, fn)))
1126 |            (f, args) => throw (GenericMsg fc "Not a function name in pattern LHS")
1127 |
1128 | -- Assumption (given 'ClosedTerm') is that the pattern variables are
1129 | -- explicitly named. We'll assign de Bruijn indices when we're done, and
1130 | -- the names of the top level variables we created are returned in 'args'
1131 | export
1132 | simpleCase : {auto c : Ref Ctxt Defs} ->
1133 |              FC -> Phase -> Name -> ClosedTerm ->
1134 |              (clauses : List01 True (ClosedTerm, ClosedTerm)) ->
1135 |              Core (args ** CaseTree args)
1136 | simpleCase fc phase fn ty clauses
1137 |     = do logC "compile.casetree" 5 $
1138 |                 do cs <- traverse (\ (c,d) => [| MkPair (toFullNames c) (toFullNames d) |]) (forget clauses)
1139 |                    pure $ "simpleCase: Clauses:\n" ++ show (
1140 |                      indent 2 $ vcat $ flip map cs $ \ lrhs =>
1141 |                        byShow (fst lrhs) <++> pretty "=" <++> byShow (snd lrhs))
1142 |          ps <- traverseList01 (toPatClause fc fn) clauses
1143 |          defs <- get Ctxt
1144 |          patCompile fc fn phase ty ps
1145 |
1146 | mutual
1147 |   findReachedAlts : CaseAlt ns' -> List Int
1148 |   findReachedAlts (ConCase _ _ _ t) = findReached t
1149 |   findReachedAlts (DelayCase _ _ t) = findReached t
1150 |   findReachedAlts (ConstCase _ t) = findReached t
1151 |   findReachedAlts (DefaultCase t) = findReached t
1152 |
1153 |   findReached : CaseTree ns -> List Int
1154 |   findReached (Case _ _ _ alts) = concatMap findReachedAlts alts
1155 |   findReached (STerm i _) = [i]
1156 |   findReached _ = []
1157 |
1158 | -- Replace a default case with explicit branches for the constructors.
1159 | -- This is easier than checking whether a default is needed when traversing
1160 | -- the tree (just one constructor lookup up front).
1161 | -- Unreachable defaults are those that when replaced by all possible constructors
1162 | -- followed by a removal of duplicate cases there is one _fewer_ total case alts.
1163 | identifyUnreachableDefaults : {auto c : Ref Ctxt Defs} ->
1164 |                               {vars : _} ->
1165 |                               FC -> Defs -> NF vars -> List (CaseAlt vars) ->
1166 |                               Core (SortedSet Int)
1167 | -- Leave it alone if it's a primitive type though, since we need the catch
1168 | -- all case there
1169 | identifyUnreachableDefaults fc defs (NPrimVal {}) cs = pure empty
1170 | identifyUnreachableDefaults fc defs (NType {}) cs = pure empty
1171 | identifyUnreachableDefaults fc defs nfty cs
1172 |     = do cs' <- traverse rep cs
1173 |          let (cs'', extraClauseIdxs) = dropRep (concat cs') empty
1174 |          let extraClauseIdxs' =
1175 |            if (length cs == (length cs'' + 1))
1176 |               then extraClauseIdxs
1177 |               else empty
1178 |          -- if a clause is unreachable under all the branches it can be found under
1179 |          -- then it is entirely unreachable.
1180 |          when (not $ null extraClauseIdxs') $
1181 |            log "compile.casetree.clauses" 25 $
1182 |              "Marking the following clause indices as unreachable under the current branch of the tree: " ++ (show extraClauseIdxs')
1183 |          pure extraClauseIdxs'
1184 |   where
1185 |     rep : CaseAlt vars -> Core (List (CaseAlt vars))
1186 |     rep (DefaultCase sc)
1187 |         = do allCons <- getCons defs nfty
1188 |              pure (map (mkAlt fc sc) allCons)
1189 |     rep c = pure [c]
1190 |
1191 |     dropRep : List (CaseAlt vars) -> SortedSet Int -> (List (CaseAlt vars), SortedSet Int)
1192 |     dropRep [] extra = ([], extra)
1193 |     dropRep (c@(ConCase n t args sc) :: rest) extra
1194 |           -- assumption is that there's no defaultcase in 'rest' because
1195 |           -- we've just removed it
1196 |         = let (filteredClauses, extraCases) = partition (not . tagIs t) rest
1197 |               extraClauses = extraCases >>= findReachedAlts
1198 |               (rest', extra') = dropRep filteredClauses $ fromList extraClauses
1199 |           in  (c :: rest', extra `union` extra')
1200 |     dropRep (c :: rest) extra
1201 |         = let (rest', extra') = dropRep rest extra
1202 |           in  (c :: rest', extra')
1203 |
1204 | ||| Find unreachable default paths through the tree for each clause.
1205 | ||| This is accomplished by expanding default clases into all concrete constructions
1206 | ||| and then listing the clauses reached.
1207 | ||| This list of clauses can be substracted from the list of "reachable" clauses
1208 | ||| and if it turns out that the number of unreachable ways to use a clause is equal
1209 | ||| to the number of ways to reach a RHS for that clause then the clause is totally
1210 | ||| superfluous (it will never be reached).
1211 | findExtraDefaults : {auto c : Ref Ctxt Defs} ->
1212 |                     {vars : _} ->
1213 |                     FC -> Defs -> CaseTree vars ->
1214 |                     Core (List Int)
1215 | findExtraDefaults fc defs (Case idx el ty altsIn)
1216 |   = do let fenv = mkEnv fc vars
1217 |        nfty <- nf defs fenv ty
1218 |        extraCases <- identifyUnreachableDefaults fc defs nfty altsIn
1219 |        extraCases' <- concat <$> traverse findExtraAlts altsIn
1220 |        pure (Prelude.toList extraCases ++ extraCases')
1221 |   where
1222 |     findExtraAlts : CaseAlt vars -> Core (List Int)
1223 |     findExtraAlts (ConCase x tag args ctree) = findExtraDefaults fc defs ctree
1224 |     findExtraAlts (DelayCase x arg ctree) = findExtraDefaults fc defs ctree
1225 |     findExtraAlts (ConstCase x ctree) = findExtraDefaults fc defs ctree
1226 |     -- already handled defaults by elaborating them to all possible cons
1227 |     findExtraAlts (DefaultCase ctree) = pure []
1228 |
1229 | findExtraDefaults fc defs ctree = pure []
1230 |
1231 | -- Returns the case tree, and a list of the clauses that aren't reachable
1232 | export
1233 | getPMDef : {auto c : Ref Ctxt Defs} ->
1234 |            FC -> Phase -> Name -> ClosedTerm -> List Clause ->
1235 |            Core (args ** (CaseTree args, List Clause))
1236 | -- If there's no clauses, make a definition with the right number of arguments
1237 | -- for the type, which we can use in coverage checking to ensure that one of
1238 | -- the arguments has an empty type
1239 | getPMDef fc phase fn ty []
1240 |     = do log "compile.casetree.getpmdef" 20 "getPMDef: No clauses!"
1241 |          defs <- get Ctxt
1242 |          pure (!(getArgs 0 !(nf defs Env.empty ty)) ** (Unmatched "No clauses in \{show fn}", []))
1243 |   where
1244 |     getArgs : Int -> ClosedNF -> Core (List Name)
1245 |     getArgs i (NBind fc x (Pi {}) sc)
1246 |         = do defs <- get Ctxt
1247 |              sc' <- sc defs (toClosure defaultOpts Env.empty (Erased fc Placeholder))
1248 |              pure (MN "arg" i :: !(getArgs i sc'))
1249 |     getArgs i _ = pure []
1250 | getPMDef fc phase fn ty clauses@(_ :: _)
1251 |     = do defs <- get Ctxt
1252 |          let cs = map (toClosed defs) (labelPat 0 $ fromList clauses)
1253 |          (_ ** t) <- simpleCase fc phase fn ty cs
1254 |          logC "compile.casetree.getpmdef" 20 $
1255 |            pure $ "Compiled to: " ++ show !(toFullNames t)
1256 |          let reached = findReached t
1257 |          log "compile.casetree.clauses" 25 $
1258 |            "Reached clauses: " ++ (show reached)
1259 |          extraDefaults <- findExtraDefaults fc defs t
1260 |          let unreachable = getUnreachable 0 (reached \\ extraDefaults) clauses
1261 |          pure (_ ** (t, unreachable))
1262 |   where
1263 |     getUnreachable : Int -> List Int -> List Clause -> List Clause
1264 |     getUnreachable i is [] = []
1265 |     getUnreachable i is (c :: cs)
1266 |         = if i `elem` is
1267 |              then getUnreachable (i + 1) is cs
1268 |              else c :: getUnreachable (i + 1) is cs
1269 |
1270 |     labelPat : Int -> List01 ne a -> List01 ne (String, a)
1271 |     labelPat i [] = []
1272 |     labelPat i (x :: xs) = ("pat" ++ show i ++ ":", x) :: labelPat (i + 1) xs
1273 |
1274 |     toClosed : Defs -> (String, Clause) -> (ClosedTerm, ClosedTerm)
1275 |     toClosed defs (pname, MkClause env lhs rhs)
1276 |           = (close fc pname env lhs, close fc pname env rhs)
1277 |