2 % (c) The University of Glasgow 2006
3 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
10 -- The above warning supression flag is a temporary kludge.
11 -- While working on this module you are encouraged to remove it and fix
12 -- any warnings in the module. See
13 -- http://hackage.haskell.org/trac/ghc/wiki/Commentary/CodingStyle#Warnings
16 module Match ( match, matchEquations, matchWrapper, matchSimply, matchSinglePat ) where
18 #include "HsVersions.h"
20 import {-#SOURCE#-} DsExpr (dsLExpr)
49 This function is a wrapper of @match@, it must be called from all the parts where
50 it was called match, but only substitutes the firs call, ....
51 if the associated flags are declared, warnings will be issued.
52 It can not be called matchWrapper because this name already exists :-(
57 matchCheck :: DsMatchContext
58 -> [Id] -- Vars rep'ing the exprs we're matching with
59 -> Type -- Type of the case expression
60 -> [EquationInfo] -- Info about patterns, etc. (type synonym below)
61 -> DsM MatchResult -- Desugared result!
63 matchCheck ctx vars ty qs = do
65 matchCheck_really dflags ctx vars ty qs
67 matchCheck_really dflags ctx vars ty qs
68 | incomplete && shadow = do
69 dsShadowWarn ctx eqns_shadow
70 dsIncompleteWarn ctx pats
73 dsIncompleteWarn ctx pats
76 dsShadowWarn ctx eqns_shadow
80 where (pats, eqns_shadow) = check qs
81 incomplete = want_incomplete && (notNull pats)
82 want_incomplete = case ctx of
83 DsMatchContext RecUpd _ ->
84 dopt Opt_WarnIncompletePatternsRecUpd dflags
86 dopt Opt_WarnIncompletePatterns dflags
87 shadow = dopt Opt_WarnOverlappingPatterns dflags
88 && not (null eqns_shadow)
91 This variable shows the maximum number of lines of output generated for warnings.
92 It will limit the number of patterns/equations displayed to@ maximum_output@.
94 (ToDo: add command-line option?)
100 The next two functions create the warning message.
103 dsShadowWarn :: DsMatchContext -> [EquationInfo] -> DsM ()
104 dsShadowWarn ctx@(DsMatchContext kind loc) qs
105 = putSrcSpanDs loc (warnDs warn)
107 warn | qs `lengthExceeds` maximum_output
108 = pp_context ctx (ptext SLIT("are overlapped"))
109 (\ f -> vcat (map (ppr_eqn f kind) (take maximum_output qs)) $$
112 = pp_context ctx (ptext SLIT("are overlapped"))
113 (\ f -> vcat $ map (ppr_eqn f kind) qs)
116 dsIncompleteWarn :: DsMatchContext -> [ExhaustivePat] -> DsM ()
117 dsIncompleteWarn ctx@(DsMatchContext kind loc) pats
118 = putSrcSpanDs loc (warnDs warn)
120 warn = pp_context ctx (ptext SLIT("are non-exhaustive"))
121 (\f -> hang (ptext SLIT("Patterns not matched:"))
122 4 ((vcat $ map (ppr_incomplete_pats kind)
123 (take maximum_output pats))
126 dots | pats `lengthExceeds` maximum_output = ptext SLIT("...")
129 pp_context (DsMatchContext kind _loc) msg rest_of_msg_fun
130 = vcat [ptext SLIT("Pattern match(es)") <+> msg,
131 sep [ptext SLIT("In") <+> ppr_match <> char ':', nest 4 (rest_of_msg_fun pref)]]
135 FunRhs fun _ -> (pprMatchContext kind, \ pp -> ppr fun <+> pp)
136 other -> (pprMatchContext kind, \ pp -> pp)
138 ppr_pats pats = sep (map ppr pats)
140 ppr_shadow_pats kind pats
141 = sep [ppr_pats pats, matchSeparator kind, ptext SLIT("...")]
143 ppr_incomplete_pats kind (pats,[]) = ppr_pats pats
144 ppr_incomplete_pats kind (pats,constraints) =
145 sep [ppr_pats pats, ptext SLIT("with"),
146 sep (map ppr_constraint constraints)]
149 ppr_constraint (var,pats) = sep [ppr var, ptext SLIT("`notElem`"), ppr pats]
151 ppr_eqn prefixF kind eqn = prefixF (ppr_shadow_pats kind (eqn_pats eqn))
155 %************************************************************************
157 The main matching function
159 %************************************************************************
161 The function @match@ is basically the same as in the Wadler chapter,
162 except it is monadised, to carry around the name supply, info about
165 Notes on @match@'s arguments, assuming $m$ equations and $n$ patterns:
168 A list of $n$ variable names, those variables presumably bound to the
169 $n$ expressions being matched against the $n$ patterns. Using the
170 list of $n$ expressions as the first argument showed no benefit and
174 The second argument, a list giving the ``equation info'' for each of
178 the $n$ patterns for that equation, and
180 a list of Core bindings [@(Id, CoreExpr)@ pairs] to be ``stuck on
181 the front'' of the matching code, as in:
187 and finally: (ToDo: fill in)
189 The right way to think about the ``after-match function'' is that it
190 is an embryonic @CoreExpr@ with a ``hole'' at the end for the
191 final ``else expression''.
194 There is a type synonym, @EquationInfo@, defined in module @DsUtils@.
196 An experiment with re-ordering this information about equations (in
197 particular, having the patterns available in column-major order)
201 A default expression---what to evaluate if the overall pattern-match
202 fails. This expression will (almost?) always be
203 a measly expression @Var@, unless we know it will only be used once
204 (as we do in @glue_success_exprs@).
206 Leaving out this third argument to @match@ (and slamming in lots of
207 @Var "fail"@s) is a positively {\em bad} idea, because it makes it
208 impossible to share the default expressions. (Also, it stands no
209 chance of working in our post-upheaval world of @Locals@.)
212 Note: @match@ is often called via @matchWrapper@ (end of this module),
213 a function that does much of the house-keeping that goes with a call
216 It is also worth mentioning the {\em typical} way a block of equations
217 is desugared with @match@. At each stage, it is the first column of
218 patterns that is examined. The steps carried out are roughly:
221 Tidy the patterns in column~1 with @tidyEqnInfo@ (this may add
222 bindings to the second component of the equation-info):
225 Remove the `as' patterns from column~1.
227 Make all constructor patterns in column~1 into @ConPats@, notably
228 @ListPats@ and @TuplePats@.
230 Handle any irrefutable (or ``twiddle'') @LazyPats@.
233 Now {\em unmix} the equations into {\em blocks} [w/ local function
234 @unmix_eqns@], in which the equations in a block all have variable
235 patterns in column~1, or they all have constructor patterns in ...
236 (see ``the mixture rule'' in SLPJ).
238 Call @matchEqnBlock@ on each block of equations; it will do the
239 appropriate thing for each kind of column-1 pattern, usually ending up
240 in a recursive call to @match@.
243 We are a little more paranoid about the ``empty rule'' (SLPJ, p.~87)
244 than the Wadler-chapter code for @match@ (p.~93, first @match@ clause).
245 And gluing the ``success expressions'' together isn't quite so pretty.
247 This (more interesting) clause of @match@ uses @tidy_and_unmix_eqns@
248 (a)~to get `as'- and `twiddle'-patterns out of the way (tidying), and
249 (b)~to do ``the mixture rule'' (SLPJ, p.~88) [which really {\em
250 un}mixes the equations], producing a list of equation-info
251 blocks, each block having as its first column of patterns either all
252 constructors, or all variables (or similar beasts), etc.
254 @match_unmixed_eqn_blks@ simply takes the place of the @foldr@ in the
255 Wadler-chapter @match@ (p.~93, last clause), and @match_unmixed_blk@
256 corresponds roughly to @matchVarCon@.
259 match :: [Id] -- Variables rep'ing the exprs we're matching with
260 -> Type -- Type of the case expression
261 -> [EquationInfo] -- Info about patterns, etc. (type synonym below)
262 -> DsM MatchResult -- Desugared result!
265 = ASSERT2( not (null eqns), ppr ty )
266 return (foldr1 combineMatchResults match_results)
268 match_results = [ ASSERT( null (eqn_pats eqn) )
272 match vars@(v:_) ty eqns
273 = ASSERT( not (null eqns ) )
274 do { -- Tidy the first pattern, generating
275 -- auxiliary bindings if necessary
276 (aux_binds, tidy_eqns) <- mapAndUnzipM (tidyEqnInfo v) eqns
278 -- Group the equations and match each group in turn
280 ; let grouped = (groupEquations tidy_eqns)
282 -- print the view patterns that are commoned up to help debug
283 ; ifOptM Opt_D_dump_view_pattern_commoning (debug grouped)
285 ; match_results <- mapM match_group grouped
286 ; return (adjustMatchResult (foldr1 (.) aux_binds) $
287 foldr1 combineMatchResults match_results) }
289 dropGroup :: [(PatGroup,EquationInfo)] -> [EquationInfo]
292 match_group :: [(PatGroup,EquationInfo)] -> DsM MatchResult
293 match_group eqns@((group,_) : _)
295 PgAny -> matchVariables vars ty (dropGroup eqns)
296 PgCon _ -> matchConFamily vars ty (subGroups eqns)
297 PgLit _ -> matchLiterals vars ty (subGroups eqns)
298 PgN lit -> matchNPats vars ty (subGroups eqns)
299 PgNpK lit -> matchNPlusKPats vars ty (dropGroup eqns)
300 PgBang -> matchBangs vars ty (dropGroup eqns)
301 PgCo _ -> matchCoercion vars ty (dropGroup eqns)
302 PgView _ _ -> matchView vars ty (dropGroup eqns)
304 -- FIXME: we should also warn about view patterns that should be
305 -- commoned up but are not
307 -- print some stuff to see what's getting grouped
308 -- use -dppr-debug to see the resolution of overloaded lits
310 let gs = map (\group -> foldr (\ (p,_) -> \acc ->
311 case p of PgView e _ -> e:acc
312 _ -> acc) [] group) eqns
313 maybeWarn [] = return ()
314 maybeWarn l = warnDs (vcat l)
316 maybeWarn $ (map (\g -> text "Putting these view expressions into the same case:" <+> (ppr g))
317 (filter (not . null) gs))
319 matchVariables :: [Id] -> Type -> [EquationInfo] -> DsM MatchResult
320 -- Real true variables, just like in matchVar, SLPJ p 94
321 -- No binding to do: they'll all be wildcards by now (done in tidy)
322 matchVariables (var:vars) ty eqns = match vars ty (shiftEqns eqns)
324 matchBangs :: [Id] -> Type -> [EquationInfo] -> DsM MatchResult
325 matchBangs (var:vars) ty eqns
326 = do { match_result <- match (var:vars) ty (map decomposeFirst_Bang eqns)
327 ; return (mkEvalMatchResult var ty match_result) }
329 matchCoercion :: [Id] -> Type -> [EquationInfo] -> DsM MatchResult
330 -- Apply the coercion to the match variable and then match that
331 matchCoercion (var:vars) ty (eqns@(eqn1:_))
332 = do { let CoPat co pat _ = firstPat eqn1
333 ; var' <- newUniqueId (idName var) (hsPatType pat)
334 ; match_result <- match (var':vars) ty (map decomposeFirst_Coercion eqns)
335 ; rhs <- dsCoercion co (return (Var var))
336 ; return (mkCoLetMatchResult (NonRec var' rhs) match_result) }
338 matchView :: [Id] -> Type -> [EquationInfo] -> DsM MatchResult
339 -- Apply the view function to the match variable and then match that
340 matchView (var:vars) ty (eqns@(eqn1:_))
341 = do { -- we could pass in the expr from the PgView,
342 -- but this needs to extract the pat anyway
343 -- to figure out the type of the fresh variable
344 let ViewPat viewExpr (L _ pat) _ = firstPat eqn1
345 -- do the rest of the compilation
346 ; var' <- newUniqueId (idName var) (hsPatType pat)
347 ; match_result <- match (var':vars) ty (map decomposeFirst_View eqns)
348 -- compile the view expressions
349 ; viewExpr' <- dsLExpr viewExpr
350 ; return (mkViewMatchResult var' viewExpr' var match_result) }
352 -- decompose the first pattern and leave the rest alone
353 decomposeFirstPat extractpat (eqn@(EqnInfo { eqn_pats = pat : pats }))
354 = eqn { eqn_pats = extractpat pat : pats}
356 decomposeFirst_Coercion = decomposeFirstPat (\ (CoPat _ pat _) -> pat)
357 decomposeFirst_Bang = decomposeFirstPat (\ (BangPat pat ) -> unLoc pat)
358 decomposeFirst_View = decomposeFirstPat (\ (ViewPat _ pat _) -> unLoc pat)
362 %************************************************************************
366 %************************************************************************
368 Tidy up the leftmost pattern in an @EquationInfo@, given the variable @v@
369 which will be scrutinised. This means:
372 Replace variable patterns @x@ (@x /= v@) with the pattern @_@,
373 together with the binding @x = v@.
375 Replace the `as' pattern @xp@ with the pattern p and a binding @x = do v@.
377 Removing lazy (irrefutable) patterns (you don't want to know...).
379 Converting explicit tuple-, list-, and parallel-array-pats into ordinary
382 Convert the literal pat "" to [].
385 The result of this tidying is that the column of patterns will include
389 The @VarPat@ information isn't needed any more after this.
392 @ListPats@, @TuplePats@, etc., are all converted into @ConPats@.
394 \item[@LitPats@ and @NPats@:]
395 @LitPats@/@NPats@ of ``known friendly types'' (Int, Char,
396 Float, Double, at least) are converted to unboxed form; e.g.,
397 \tr{(NPat (HsInt i) _ _)} is converted to:
399 (ConPat I# _ _ [LitPat (HsIntPrim i)])
404 tidyEqnInfo :: Id -> EquationInfo
405 -> DsM (DsWrapper, EquationInfo)
406 -- DsM'd because of internal call to dsLHsBinds
407 -- and mkSelectorBinds.
408 -- "tidy1" does the interesting stuff, looking at
409 -- one pattern and fiddling the list of bindings.
411 -- POST CONDITION: head pattern in the EqnInfo is
419 tidyEqnInfo v eqn@(EqnInfo { eqn_pats = pat : pats }) = do
420 (wrap, pat') <- tidy1 v pat
421 return (wrap, eqn { eqn_pats = do pat' : pats })
423 tidy1 :: Id -- The Id being scrutinised
424 -> Pat Id -- The pattern against which it is to be matched
425 -> DsM (DsWrapper, -- Extra bindings to do before the match
426 Pat Id) -- Equivalent pattern
428 -------------------------------------------------------
429 -- (pat', mr') = tidy1 v pat mr
430 -- tidies the *outer level only* of pat, giving pat'
431 -- It eliminates many pattern forms (as-patterns, variable patterns,
432 -- list patterns, etc) yielding one of:
439 tidy1 v (ParPat pat) = tidy1 v (unLoc pat)
440 tidy1 v (SigPatOut pat _) = tidy1 v (unLoc pat)
441 tidy1 v (WildPat ty) = return (idDsWrapper, WildPat ty)
443 -- case v of { x -> mr[] }
444 -- = case v of { _ -> let x=v in mr[] }
446 = return (wrapBind var v, WildPat (idType var))
448 tidy1 v (VarPatOut var binds)
449 = do { prs <- dsLHsBinds binds
450 ; return (wrapBind var v . mkDsLet (Rec prs),
451 WildPat (idType var)) }
453 -- case v of { x@p -> mr[] }
454 -- = case v of { p -> let x=v in mr[] }
455 tidy1 v (AsPat (L _ var) pat)
456 = do { (wrap, pat') <- tidy1 v (unLoc pat)
457 ; return (wrapBind var v . wrap, pat') }
459 {- now, here we handle lazy patterns:
460 tidy1 v ~p bs = (v, v1 = case v of p -> v1 :
461 v2 = case v of p -> v2 : ... : bs )
463 where the v_i's are the binders in the pattern.
465 ToDo: in "v_i = ... -> v_i", are the v_i's really the same thing?
467 The case expr for v_i is just: match [v] [(p, [], \ x -> Var v_i)] any_expr
470 tidy1 v (LazyPat pat)
471 = do { sel_prs <- mkSelectorBinds pat (Var v)
472 ; let sel_binds = [NonRec b rhs | (b,rhs) <- sel_prs]
473 ; return (mkDsLets sel_binds, WildPat (idType v)) }
475 tidy1 v (ListPat pats ty)
476 = return (idDsWrapper, unLoc list_ConPat)
478 list_ty = mkListTy ty
479 list_ConPat = foldr (\ x y -> mkPrefixConPat consDataCon [x, y] list_ty)
483 -- Introduce fake parallel array constructors to be able to handle parallel
484 -- arrays with the existing machinery for constructor pattern
485 tidy1 v (PArrPat pats ty)
486 = return (idDsWrapper, unLoc parrConPat)
489 parrConPat = mkPrefixConPat (parrFakeCon arity) pats (mkPArrTy ty)
491 tidy1 v (TuplePat pats boxity ty)
492 = return (idDsWrapper, unLoc tuple_ConPat)
495 tuple_ConPat = mkPrefixConPat (tupleCon boxity arity) pats ty
497 -- LitPats: we *might* be able to replace these w/ a simpler form
499 = return (idDsWrapper, tidyLitPat lit)
501 -- NPats: we *might* be able to replace these w/ a simpler form
502 tidy1 v (NPat lit mb_neg eq)
503 = return (idDsWrapper, tidyNPat lit mb_neg eq)
505 -- Everything else goes through unchanged...
507 tidy1 v non_interesting_pat
508 = return (idDsWrapper, non_interesting_pat)
512 {\bf Previous @matchTwiddled@ stuff:}
514 Now we get to the only interesting part; note: there are choices for
515 translation [from Simon's notes]; translation~1:
522 s = case w of [s,t] -> s
523 t = case w of [s,t] -> t
527 Here \tr{w} is a fresh variable, and the \tr{w}-binding prevents multiple
528 evaluation of \tr{e}. An alternative translation (No.~2):
530 [ w = case e of [s,t] -> (s,t)
531 s = case w of (s,t) -> s
532 t = case w of (s,t) -> t
536 %************************************************************************
538 \subsubsection[improved-unmixing]{UNIMPLEMENTED idea for improved unmixing}
540 %************************************************************************
542 We might be able to optimise unmixing when confronted by
543 only-one-constructor-possible, of which tuples are the most notable
551 This definition would normally be unmixed into four equation blocks,
552 one per equation. But it could be unmixed into just one equation
553 block, because if the one equation matches (on the first column),
554 the others certainly will.
556 You have to be careful, though; the example
564 {\em must} be broken into two blocks at the line shown; otherwise, you
565 are forcing unnecessary evaluation. In any case, the top-left pattern
566 always gives the cue. You could then unmix blocks into groups of...
568 \item[all variables:]
570 \item[constructors or variables (mixed):]
571 Need to make sure the right names get bound for the variable patterns.
572 \item[literals or variables (mixed):]
573 Presumably just a variant on the constructor case (as it is now).
576 %************************************************************************
578 %* matchWrapper: a convenient way to call @match@ *
580 %************************************************************************
581 \subsection[matchWrapper]{@matchWrapper@: a convenient interface to @match@}
583 Calls to @match@ often involve similar (non-trivial) work; that work
584 is collected here, in @matchWrapper@. This function takes as
588 Typchecked @Matches@ (of a function definition, or a case or lambda
589 expression)---the main input;
591 An error message to be inserted into any (runtime) pattern-matching
595 As results, @matchWrapper@ produces:
598 A list of variables (@Locals@) that the caller must ``promise'' to
599 bind to appropriate values; and
601 a @CoreExpr@, the desugared output (main result).
604 The main actions of @matchWrapper@ include:
607 Flatten the @[TypecheckedMatch]@ into a suitable list of
610 Create as many new variables as there are patterns in a pattern-list
611 (in any one of the @EquationInfo@s).
613 Create a suitable ``if it fails'' expression---a call to @error@ using
614 the error-string input; the {\em type} of this fail value can be found
615 by examining one of the RHS expressions in one of the @EquationInfo@s.
617 Call @match@ with all of this information!
621 matchWrapper :: HsMatchContext Name -- For shadowing warning messages
622 -> MatchGroup Id -- Matches being desugared
623 -> DsM ([Id], CoreExpr) -- Results
626 There is one small problem with the Lambda Patterns, when somebody
627 writes something similar to:
631 he/she don't want a warning about incomplete patterns, that is done with
632 the flag @opt_WarnSimplePatterns@.
633 This problem also appears in the:
635 \item @do@ patterns, but if the @do@ can fail
636 it creates another equation if the match can fail
637 (see @DsExpr.doDo@ function)
638 \item @let@ patterns, are treated by @matchSimply@
639 List Comprension Patterns, are treated by @matchSimply@ also
642 We can't call @matchSimply@ with Lambda patterns,
643 due to the fact that lambda patterns can have more than
644 one pattern, and match simply only accepts one pattern.
649 matchWrapper ctxt (MatchGroup matches match_ty)
650 = ASSERT( notNull matches )
651 do { eqns_info <- mapM mk_eqn_info matches
652 ; new_vars <- selectMatchVars arg_pats
653 ; result_expr <- matchEquations ctxt new_vars eqns_info rhs_ty
654 ; return (new_vars, result_expr) }
656 arg_pats = map unLoc (hsLMatchPats (head matches))
657 n_pats = length arg_pats
658 (_, rhs_ty) = splitFunTysN n_pats match_ty
660 mk_eqn_info (L _ (Match pats _ grhss))
661 = do { let upats = map unLoc pats
662 ; match_result <- dsGRHSs ctxt upats grhss rhs_ty
663 ; return (EqnInfo { eqn_pats = upats, eqn_rhs = match_result}) }
666 matchEquations :: HsMatchContext Name
667 -> [Id] -> [EquationInfo] -> Type
669 matchEquations ctxt vars eqns_info rhs_ty
670 = do { dflags <- getDOptsDs
671 ; locn <- getSrcSpanDs
672 ; let ds_ctxt = DsMatchContext ctxt locn
673 error_string = matchContextErrString ctxt
675 ; match_result <- match_fun dflags ds_ctxt vars rhs_ty eqns_info
677 ; fail_expr <- mkErrorAppDs pAT_ERROR_ID rhs_ty error_string
678 ; extractMatchResult match_result fail_expr }
680 match_fun dflags ds_ctxt
682 LambdaExpr | dopt Opt_WarnSimplePatterns dflags -> matchCheck ds_ctxt
684 _ -> matchCheck ds_ctxt
687 %************************************************************************
689 \subsection[matchSimply]{@matchSimply@: match a single expression against a single pattern}
691 %************************************************************************
693 @mkSimpleMatch@ is a wrapper for @match@ which deals with the
694 situation where we want to match a single expression against a single
695 pattern. It returns an expression.
698 matchSimply :: CoreExpr -- Scrutinee
699 -> HsMatchContext Name -- Match kind
700 -> LPat Id -- Pattern it should match
701 -> CoreExpr -- Return this if it matches
702 -> CoreExpr -- Return this if it doesn't
705 matchSimply scrut hs_ctx pat result_expr fail_expr = do
707 match_result = cantFailMatchResult result_expr
708 rhs_ty = exprType fail_expr
709 -- Use exprType of fail_expr, because won't refine in the case of failure!
710 match_result' <- matchSinglePat scrut hs_ctx pat rhs_ty match_result
711 extractMatchResult match_result' fail_expr
714 matchSinglePat :: CoreExpr -> HsMatchContext Name -> LPat Id
715 -> Type -> MatchResult -> DsM MatchResult
716 matchSinglePat (Var var) hs_ctx (L _ pat) ty match_result = do
721 | dopt Opt_WarnSimplePatterns dflags = matchCheck ds_ctx
724 ds_ctx = DsMatchContext hs_ctx locn
725 match_fn dflags [var] ty [EqnInfo { eqn_pats = [pat], eqn_rhs = match_result }]
727 matchSinglePat scrut hs_ctx pat ty match_result = do
728 var <- selectSimpleMatchVarL pat
729 match_result' <- matchSinglePat (Var var) hs_ctx pat ty match_result
730 return (adjustMatchResult (bindNonRec var scrut) match_result')
734 %************************************************************************
736 Pattern classification
738 %************************************************************************
742 = PgAny -- Immediate match: variables, wildcards,
744 | PgCon DataCon -- Constructor patterns (incl list, tuple)
745 | PgLit Literal -- Literal patterns
746 | PgN Literal -- Overloaded literals
747 | PgNpK Literal -- n+k patterns
748 | PgBang -- Bang patterns
749 | PgCo Type -- Coercion patterns; the type is the type
750 -- of the pattern *inside*
751 | PgView (LHsExpr Id) -- view pattern (e -> p):
752 -- the LHsExpr is the expression e
753 Type -- the Type is the type of p (equivalently, the result type of e)
755 groupEquations :: [EquationInfo] -> [[(PatGroup, EquationInfo)]]
756 -- If the result is of form [g1, g2, g3],
757 -- (a) all the (pg,eq) pairs in g1 have the same pg
758 -- (b) none of the gi are empty
760 = runs same_gp [(patGroup (firstPat eqn), eqn) | eqn <- eqns]
762 same_gp :: (PatGroup,EquationInfo) -> (PatGroup,EquationInfo) -> Bool
763 (pg1,_) `same_gp` (pg2,_) = pg1 `sameGroup` pg2
765 subGroups :: [(PatGroup, EquationInfo)] -> [[EquationInfo]]
766 -- Input is a particular group. The result sub-groups the
767 -- equations by with particular constructor, literal etc they match.
768 -- The order may be swizzled, so the matching should be order-independent
769 subGroups groups = map (map snd) (equivClasses cmp groups)
771 (pg1, _) `cmp` (pg2, _) = pg1 `cmp_pg` pg2
772 (PgCon c1) `cmp_pg` (PgCon c2) = c1 `compare` c2
773 (PgLit l1) `cmp_pg` (PgLit l2) = l1 `compare` l2
774 (PgN l1) `cmp_pg` (PgN l2) = l1 `compare` l2
775 -- These are the only cases that are every sub-grouped
777 sameGroup :: PatGroup -> PatGroup -> Bool
778 -- Same group means that a single case expression
779 -- or test will suffice to match both, *and* the order
780 -- of testing within the group is insignificant.
781 sameGroup PgAny PgAny = True
782 sameGroup PgBang PgBang = True
783 sameGroup (PgCon _) (PgCon _) = True -- One case expression
784 sameGroup (PgLit _) (PgLit _) = True -- One case expression
785 sameGroup (PgN l1) (PgN l2) = True -- Needs conditionals
786 sameGroup (PgNpK l1) (PgNpK l2) = l1==l2 -- Order is significant
787 -- See Note [Order of n+k]
788 sameGroup (PgCo t1) (PgCo t2) = t1 `coreEqType` t2
789 -- CoPats are in the same goup only if the type of the
790 -- enclosed pattern is the same. The patterns outside the CoPat
791 -- always have the same type, so this boils down to saying that
792 -- the two coercions are identical.
793 sameGroup (PgView e1 t1) (PgView e2 t2) = viewLExprEq (e1,t1) (e2,t2)
794 -- ViewPats are in the same gorup iff the expressions
795 -- are "equal"---conservatively, we use syntactic equality
796 sameGroup _ _ = False
798 -- an approximation of syntactic equality used for determining when view
799 -- exprs are in the same group.
800 -- this function can always safely return false;
801 -- but doing so will result in the application of the view function being repeated.
803 -- currently: compare applications of literals and variables
804 -- and anything else that we can do without involving other
805 -- HsSyn types in the recursion
807 -- NB we can't assume that the two view expressions have the same type. Consider
808 -- f (e1 -> True) = ...
809 -- f (e2 -> "hi") = ...
810 viewLExprEq :: (LHsExpr Id,Type) -> (LHsExpr Id,Type) -> Bool
811 viewLExprEq (e1,t1) (e2,t2) =
813 -- short name for recursive call on unLoc
814 lexp e e' = exp (unLoc e) (unLoc e')
816 -- check that two lists have the same length
817 -- and that they match up pairwise
819 lexps [] (_:_) = False
820 lexps (_:_) [] = False
821 lexps (x:xs) (y:ys) = lexp x y && lexps xs ys
823 -- conservative, in that it demands that wrappers be
824 -- syntactically identical and doesn't look under binders
826 -- coarser notions of equality are possible
827 -- (e.g., reassociating compositions,
828 -- equating different ways of writing a coercion)
829 wrap WpHole WpHole = True
830 wrap (WpCompose w1 w2) (WpCompose w1' w2') = wrap w1 w1' && wrap w2 w2'
831 wrap (WpCo c) (WpCo c') = tcEqType c c'
832 wrap (WpApp d) (WpApp d') = d == d'
833 wrap (WpTyApp t) (WpTyApp t') = tcEqType t t'
834 -- Enhancement: could implement equality for more wrappers
835 -- if it seems useful (lams and lets)
838 -- real comparison is on HsExpr's
840 exp (HsPar (L _ e)) e' = exp e e'
841 exp e (HsPar (L _ e')) = exp e e'
842 -- because the expressions do not necessarily have the same type,
843 -- we have to compare the wrappers
844 exp (HsWrap h e) (HsWrap h' e') = wrap h h' && exp e e'
845 exp (HsVar i) (HsVar i') = i == i'
846 -- the instance for IPName derives using the id, so this works if the
848 exp (HsIPVar i) (HsIPVar i') = i == i'
849 exp (HsOverLit l) (HsOverLit l') =
850 -- overloaded lits are equal if they have the same type
851 -- and the data is the same.
852 -- this is coarser than comparing the SyntaxExpr's in l and l',
853 -- which resolve the overloading (e.g., fromInteger 1),
854 -- because these expressions get written as a bunch of different variables
855 -- (presumably to improve sharing)
856 tcEqType (overLitType l) (overLitType l') && l == l'
857 -- comparing the constants seems right
858 exp (HsLit l) (HsLit l') = l == l'
859 exp (HsApp e1 e2) (HsApp e1' e2') = lexp e1 e1' && lexp e2 e2'
860 -- the fixities have been straightened out by now, so it's safe
862 exp (OpApp l o _ ri) (OpApp l' o' _ ri') =
863 lexp l l' && lexp o o' && lexp ri ri'
864 exp (NegApp e n) (NegApp e' n') = lexp e e' && exp n n'
865 exp (SectionL e1 e2) (SectionL e1' e2') =
866 lexp e1 e1' && lexp e2 e2'
867 exp (SectionR e1 e2) (SectionR e1' e2') =
868 lexp e1 e1' && lexp e2 e2'
869 exp (HsIf e e1 e2) (HsIf e' e1' e2') =
870 lexp e e' && lexp e1 e1' && lexp e2 e2'
871 exp (ExplicitList _ ls) (ExplicitList _ ls') = lexps ls ls'
872 exp (ExplicitPArr _ ls) (ExplicitPArr _ ls') = lexps ls ls'
873 exp (ExplicitTuple ls _) (ExplicitTuple ls' _) = lexps ls ls'
874 -- Enhancement: could implement equality for more expressions
875 -- if it seems useful
880 patGroup :: Pat Id -> PatGroup
881 patGroup (WildPat {}) = PgAny
882 patGroup (BangPat {}) = PgBang
883 patGroup (ConPatOut { pat_con = dc }) = PgCon (unLoc dc)
884 patGroup (LitPat lit) = PgLit (hsLitKey lit)
885 patGroup (NPat olit mb_neg _) = PgN (hsOverLitKey olit (isJust mb_neg))
886 patGroup (NPlusKPat _ olit _ _) = PgNpK (hsOverLitKey olit False)
887 patGroup (CoPat _ p _) = PgCo (hsPatType p) -- Type of innelexp pattern
888 patGroup (ViewPat expr p _) = PgView expr (hsPatType (unLoc p))
889 patGroup pat = pprPanic "patGroup" (ppr pat)
900 We can't group the first and third together, because the second may match
901 the same thing as the first. Contrast
905 where we can group the first and third. Hence we don't regard (n+1) and
906 (n+2) as part of the same group.