1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
6 The @match@ function
7 -}
9 {-# LANGUAGE CPP #-}
11 module Match ( match, matchEquations, matchWrapper, matchSimply, matchSinglePat ) where
13 #include "HsVersions.h"
15 import {-#SOURCE#-} DsExpr (dsLExpr, dsSyntaxExpr)
17 import DynFlags
18 import HsSyn
19 import TcHsSyn
20 import TcEvidence
22 import Check
23 import CoreSyn
24 import Literal
25 import CoreUtils
26 import MkCore
28 import DsBinds
29 import DsGRHSs
30 import DsUtils
31 import Id
32 import ConLike
33 import DataCon
34 import PatSyn
35 import MatchCon
36 import MatchLit
37 import Type
38 import Coercion ( eqCoercion )
39 import TcType ( toTcTypeBag )
40 import TyCon( isNewTyCon )
41 import TysWiredIn
42 import ListSetOps
43 import SrcLoc
44 import Maybes
45 import Util
46 import Name
47 import Outputable
48 import BasicTypes ( isGenerated, fl_value )
49 import FastString
50 import Unique
51 import UniqDFM
53 import Control.Monad( when, unless )
54 import qualified Data.Map as Map
56 {-
57 ************************************************************************
58 * *
59 The main matching function
60 * *
61 ************************************************************************
63 The function @match@ is basically the same as in the Wadler chapter,
64 except it is monadised, to carry around the name supply, info about
65 annotations, etc.
67 Notes on @match@'s arguments, assuming $m$ equations and $n$ patterns:
68 \begin{enumerate}
69 \item
70 A list of $n$ variable names, those variables presumably bound to the
71 $n$ expressions being matched against the $n$ patterns. Using the
72 list of $n$ expressions as the first argument showed no benefit and
73 some inelegance.
75 \item
76 The second argument, a list giving the equation info'' for each of
77 the $m$ equations:
78 \begin{itemize}
79 \item
80 the $n$ patterns for that equation, and
81 \item
82 a list of Core bindings [@(Id, CoreExpr)@ pairs] to be stuck on
83 the front'' of the matching code, as in:
84 \begin{verbatim}
85 let <binds>
86 in <matching-code>
87 \end{verbatim}
88 \item
89 and finally: (ToDo: fill in)
91 The right way to think about the after-match function'' is that it
92 is an embryonic @CoreExpr@ with a hole'' at the end for the
93 final else expression''.
94 \end{itemize}
96 There is a data type, @EquationInfo@, defined in module @DsMonad@.
98 An experiment with re-ordering this information about equations (in
99 particular, having the patterns available in column-major order)
100 showed no benefit.
102 \item
103 A default expression---what to evaluate if the overall pattern-match
104 fails. This expression will (almost?) always be
105 a measly expression @Var@, unless we know it will only be used once
106 (as we do in @glue_success_exprs@).
108 Leaving out this third argument to @match@ (and slamming in lots of
109 @Var "fail"@s) is a positively {\em bad} idea, because it makes it
110 impossible to share the default expressions. (Also, it stands no
111 chance of working in our post-upheaval world of @Locals@.)
112 \end{enumerate}
114 Note: @match@ is often called via @matchWrapper@ (end of this module),
115 a function that does much of the house-keeping that goes with a call
116 to @match@.
118 It is also worth mentioning the {\em typical} way a block of equations
119 is desugared with @match@. At each stage, it is the first column of
120 patterns that is examined. The steps carried out are roughly:
121 \begin{enumerate}
122 \item
123 Tidy the patterns in column~1 with @tidyEqnInfo@ (this may add
124 bindings to the second component of the equation-info):
125 \begin{itemize}
126 \item
127 Remove the as' patterns from column~1.
128 \item
129 Make all constructor patterns in column~1 into @ConPats@, notably
130 @ListPats@ and @TuplePats@.
131 \item
132 Handle any irrefutable (or twiddle'') @LazyPats@.
133 \end{itemize}
134 \item
135 Now {\em unmix} the equations into {\em blocks} [w\/ local function
136 @unmix_eqns@], in which the equations in a block all have variable
137 patterns in column~1, or they all have constructor patterns in ...
138 (see the mixture rule'' in SLPJ).
139 \item
140 Call @matchEqnBlock@ on each block of equations; it will do the
141 appropriate thing for each kind of column-1 pattern, usually ending up
142 in a recursive call to @match@.
143 \end{enumerate}
145 We are a little more paranoid about the empty rule'' (SLPJ, p.~87)
146 than the Wadler-chapter code for @match@ (p.~93, first @match@ clause).
147 And gluing the success expressions'' together isn't quite so pretty.
149 This (more interesting) clause of @match@ uses @tidy_and_unmix_eqns@
150 (a)~to get as'- and twiddle'-patterns out of the way (tidying), and
151 (b)~to do the mixture rule'' (SLPJ, p.~88) [which really {\em
152 un}mixes the equations], producing a list of equation-info
153 blocks, each block having as its first column of patterns either all
154 constructors, or all variables (or similar beasts), etc.
156 @match_unmixed_eqn_blks@ simply takes the place of the @foldr@ in the
157 Wadler-chapter @match@ (p.~93, last clause), and @match_unmixed_blk@
158 corresponds roughly to @matchVarCon@.
160 Note [Match Ids]
161 ~~~~~~~~~~~~~~~~
162 Most of the matching fuctions take an Id or [Id] as argument. This Id
163 is the scrutinee(s) of the match. The desugared expression may
164 sometimes use that Id in a local binding or as a case binder. So it
165 should not have an External name; Lint rejects non-top-level binders
166 with External names (Trac #13043).
167 -}
169 type MatchId = Id -- See Note [Match Ids]
171 match :: [MatchId] -- Variables rep\'ing the exprs we\'re matching with
172 -- See Note [Match Ids]
173 -> Type -- Type of the case expression
174 -> [EquationInfo] -- Info about patterns, etc. (type synonym below)
175 -> DsM MatchResult -- Desugared result!
177 match [] ty eqns
178 = ASSERT2( not (null eqns), ppr ty )
179 return (foldr1 combineMatchResults match_results)
180 where
181 match_results = [ ASSERT( null (eqn_pats eqn) )
182 eqn_rhs eqn
183 | eqn <- eqns ]
185 match vars@(v:_) ty eqns -- Eqns *can* be empty
186 = ASSERT2( all (isInternalName . idName) vars, ppr vars )
187 do { dflags <- getDynFlags
188 -- Tidy the first pattern, generating
189 -- auxiliary bindings if necessary
190 ; (aux_binds, tidy_eqns) <- mapAndUnzipM (tidyEqnInfo v) eqns
192 -- Group the equations and match each group in turn
193 ; let grouped = groupEquations dflags tidy_eqns
195 -- print the view patterns that are commoned up to help debug
196 ; whenDOptM Opt_D_dump_view_pattern_commoning (debug grouped)
198 ; match_results <- match_groups grouped
199 ; return (adjustMatchResult (foldr (.) id aux_binds) $200 foldr1 combineMatchResults match_results) } 201 where 202 dropGroup :: [(PatGroup,EquationInfo)] -> [EquationInfo] 203 dropGroup = map snd 205 match_groups :: [[(PatGroup,EquationInfo)]] -> DsM [MatchResult] 206 -- Result list of [MatchResult] is always non-empty 207 match_groups [] = matchEmpty v ty 208 match_groups gs = mapM match_group gs 210 match_group :: [(PatGroup,EquationInfo)] -> DsM MatchResult 211 match_group [] = panic "match_group" 212 match_group eqns@((group,_) : _) 213 = case group of 214 PgCon {} -> matchConFamily vars ty (subGroupUniq [(c,e) | (PgCon c, e) <- eqns]) 215 PgSyn {} -> matchPatSyn vars ty (dropGroup eqns) 216 PgLit {} -> matchLiterals vars ty (subGroupOrd [(l,e) | (PgLit l, e) <- eqns]) 217 PgAny -> matchVariables vars ty (dropGroup eqns) 218 PgN {} -> matchNPats vars ty (dropGroup eqns) 219 PgOverS {}-> matchNPats vars ty (dropGroup eqns) 220 PgNpK {} -> matchNPlusKPats vars ty (dropGroup eqns) 221 PgBang -> matchBangs vars ty (dropGroup eqns) 222 PgCo {} -> matchCoercion vars ty (dropGroup eqns) 223 PgView {} -> matchView vars ty (dropGroup eqns) 224 PgOverloadedList -> matchOverloadedList vars ty (dropGroup eqns) 226 -- FIXME: we should also warn about view patterns that should be 227 -- commoned up but are not 229 -- print some stuff to see what's getting grouped 230 -- use -dppr-debug to see the resolution of overloaded literals 231 debug eqns = 232 let gs = map (\group -> foldr (\ (p,_) -> \acc -> 233 case p of PgView e _ -> e:acc 234 _ -> acc) [] group) eqns 235 maybeWarn [] = return () 236 maybeWarn l = warnDs NoReason (vcat l) 237 in 238 maybeWarn$ (map (\g -> text "Putting these view expressions into the same case:" <+> (ppr g))
239 (filter (not . null) gs))
241 matchEmpty :: MatchId -> Type -> DsM [MatchResult]
242 -- See Note [Empty case expressions]
243 matchEmpty var res_ty
244 = return [MatchResult CanFail mk_seq]
245 where
246 mk_seq fail = return $mkWildCase (Var var) (idType var) res_ty 247 [(DEFAULT, [], fail)] 249 matchVariables :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult 250 -- Real true variables, just like in matchVar, SLPJ p 94 251 -- No binding to do: they'll all be wildcards by now (done in tidy) 252 matchVariables (_:vars) ty eqns = match vars ty (shiftEqns eqns) 253 matchVariables [] _ _ = panic "matchVariables" 255 matchBangs :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult 256 matchBangs (var:vars) ty eqns 257 = do { match_result <- match (var:vars) ty$
258 map (decomposeFirstPat getBangPat) eqns
259 ; return (mkEvalMatchResult var ty match_result) }
260 matchBangs [] _ _ = panic "matchBangs"
262 matchCoercion :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
263 -- Apply the coercion to the match variable and then match that
264 matchCoercion (var:vars) ty (eqns@(eqn1:_))
265 = do { let CoPat co pat _ = firstPat eqn1
266 ; let pat_ty' = hsPatType pat
267 ; var' <- newUniqueId var pat_ty'
268 ; match_result <- match (var':vars) ty $269 map (decomposeFirstPat getCoPat) eqns 270 ; core_wrap <- dsHsWrapper co 271 ; let bind = NonRec var' (core_wrap (Var var)) 272 ; return (mkCoLetMatchResult bind match_result) } 273 matchCoercion _ _ _ = panic "matchCoercion" 275 matchView :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult 276 -- Apply the view function to the match variable and then match that 277 matchView (var:vars) ty (eqns@(eqn1:_)) 278 = do { -- we could pass in the expr from the PgView, 279 -- but this needs to extract the pat anyway 280 -- to figure out the type of the fresh variable 281 let ViewPat viewExpr (L _ pat) _ = firstPat eqn1 282 -- do the rest of the compilation 283 ; let pat_ty' = hsPatType pat 284 ; var' <- newUniqueId var pat_ty' 285 ; match_result <- match (var':vars) ty$
286 map (decomposeFirstPat getViewPat) eqns
287 -- compile the view expressions
288 ; viewExpr' <- dsLExpr viewExpr
289 ; return (mkViewMatchResult var'
290 (mkCoreAppDs (text "matchView") viewExpr' (Var var))
291 match_result) }
292 matchView _ _ _ = panic "matchView"
294 matchOverloadedList :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
296 -- Since overloaded list patterns are treated as view patterns,
297 -- the code is roughly the same as for matchView
298 = do { let ListPat _ elt_ty (Just (_,e)) = firstPat eqn1
299 ; var' <- newUniqueId var (mkListTy elt_ty) -- we construct the overall type by hand
300 ; match_result <- match (var':vars) ty $301 map (decomposeFirstPat getOLPat) eqns -- getOLPat builds the pattern inside as a non-overloaded version of the overloaded list pattern 302 ; e' <- dsSyntaxExpr e [Var var] 303 ; return (mkViewMatchResult var' e' match_result) } 304 matchOverloadedList _ _ _ = panic "matchOverloadedList" 306 -- decompose the first pattern and leave the rest alone 307 decomposeFirstPat :: (Pat Id -> Pat Id) -> EquationInfo -> EquationInfo 308 decomposeFirstPat extractpat (eqn@(EqnInfo { eqn_pats = pat : pats })) 309 = eqn { eqn_pats = extractpat pat : pats} 310 decomposeFirstPat _ _ = panic "decomposeFirstPat" 312 getCoPat, getBangPat, getViewPat, getOLPat :: Pat Id -> Pat Id 313 getCoPat (CoPat _ pat _) = pat 314 getCoPat _ = panic "getCoPat" 315 getBangPat (BangPat pat ) = unLoc pat 316 getBangPat _ = panic "getBangPat" 317 getViewPat (ViewPat _ pat _) = unLoc pat 318 getViewPat _ = panic "getViewPat" 319 getOLPat (ListPat pats ty (Just _)) = ListPat pats ty Nothing 320 getOLPat _ = panic "getOLPat" 322 {- 323 Note [Empty case alternatives] 324 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 325 The list of EquationInfo can be empty, arising from 326 case x of {} or \case {} 327 In that situation we desugar to 328 case x of { _ -> error "pattern match failure" } 329 The *desugarer* isn't certain whether there really should be no 330 alternatives, so it adds a default case, as it always does. A later 331 pass may remove it if it's inaccessible. (See also Note [Empty case 332 alternatives] in CoreSyn.) 334 We do *not* desugar simply to 335 error "empty case" 336 or some such, because 'x' might be bound to (error "hello"), in which 337 case we want to see that "hello" exception, not (error "empty case"). 338 See also Note [Case elimination: lifted case] in Simplify. 341 ************************************************************************ 342 * * 343 Tidying patterns 344 * * 345 ************************************************************************ 347 Tidy up the leftmost pattern in an @EquationInfo@, given the variable @v@ 348 which will be scrutinised. This means: 349 \begin{itemize} 350 \item 351 Replace variable patterns @x@ (@x /= v@) with the pattern @_@, 352 together with the binding @x = v@. 353 \item 354 Replace the as' pattern @x@@p@ with the pattern p and a binding @x = v@. 355 \item 356 Removing lazy (irrefutable) patterns (you don't want to know...). 357 \item 358 Converting explicit tuple-, list-, and parallel-array-pats into ordinary 359 @ConPats@. 360 \item 361 Convert the literal pat "" to []. 362 \end{itemize} 364 The result of this tidying is that the column of patterns will include 365 {\em only}: 366 \begin{description} 367 \item[@WildPats@:] 368 The @VarPat@ information isn't needed any more after this. 370 \item[@ConPats@:] 371 @ListPats@, @TuplePats@, etc., are all converted into @ConPats@. 373 \item[@LitPats@ and @NPats@:] 374 @LitPats@/@NPats@ of known friendly types'' (Int, Char, 375 Float, Double, at least) are converted to unboxed form; e.g., 376 \tr{(NPat (HsInt i) _ _)} is converted to: 377 \begin{verbatim} 378 (ConPat I# _ _ [LitPat (HsIntPrim i)]) 379 \end{verbatim} 380 \end{description} 381 -} 383 tidyEqnInfo :: Id -> EquationInfo 384 -> DsM (DsWrapper, EquationInfo) 385 -- DsM'd because of internal call to dsLHsBinds 386 -- and mkSelectorBinds. 387 -- "tidy1" does the interesting stuff, looking at 388 -- one pattern and fiddling the list of bindings. 389 -- 390 -- POST CONDITION: head pattern in the EqnInfo is 391 -- WildPat 392 -- ConPat 393 -- NPat 394 -- LitPat 395 -- NPlusKPat 396 -- but no other 398 tidyEqnInfo _ (EqnInfo { eqn_pats = [] }) 399 = panic "tidyEqnInfo" 401 tidyEqnInfo v eqn@(EqnInfo { eqn_pats = pat : pats }) 402 = do { (wrap, pat') <- tidy1 v pat 403 ; return (wrap, eqn { eqn_pats = do pat' : pats }) } 405 tidy1 :: Id -- The Id being scrutinised 406 -> Pat Id -- The pattern against which it is to be matched 407 -> DsM (DsWrapper, -- Extra bindings to do before the match 408 Pat Id) -- Equivalent pattern 410 ------------------------------------------------------- 411 -- (pat', mr') = tidy1 v pat mr 412 -- tidies the *outer level only* of pat, giving pat' 413 -- It eliminates many pattern forms (as-patterns, variable patterns, 414 -- list patterns, etc) yielding one of: 415 -- WildPat 416 -- ConPatOut 417 -- LitPat 418 -- NPat 419 -- NPlusKPat 421 tidy1 v (ParPat pat) = tidy1 v (unLoc pat) 422 tidy1 v (SigPatOut pat _) = tidy1 v (unLoc pat) 423 tidy1 _ (WildPat ty) = return (idDsWrapper, WildPat ty) 424 tidy1 v (BangPat (L l p)) = tidy_bang_pat v l p 426 -- case v of { x -> mr[] } 427 -- = case v of { _ -> let x=v in mr[] } 428 tidy1 v (VarPat (L _ var)) 429 = return (wrapBind var v, WildPat (idType var)) 431 -- case v of { x@p -> mr[] } 432 -- = case v of { p -> let x=v in mr[] } 433 tidy1 v (AsPat (L _ var) pat) 434 = do { (wrap, pat') <- tidy1 v (unLoc pat) 435 ; return (wrapBind var v . wrap, pat') } 437 {- now, here we handle lazy patterns: 438 tidy1 v ~p bs = (v, v1 = case v of p -> v1 : 439 v2 = case v of p -> v2 : ... : bs ) 441 where the v_i's are the binders in the pattern. 443 ToDo: in "v_i = ... -> v_i", are the v_i's really the same thing? 445 The case expr for v_i is just: match [v] [(p, [], \ x -> Var v_i)] any_expr 446 -} 448 tidy1 v (LazyPat pat) 449 -- This is a convenient place to check for unlifted types under a lazy pattern. 450 -- Doing this check during type-checking is unsatisfactory because we may 451 -- not fully know the zonked types yet. We sure do here. 452 = do { let unlifted_bndrs = filter (isUnliftedType . idType) (collectPatBinders pat) 453 ; unless (null unlifted_bndrs)$
454 putSrcSpanDs (getLoc pat) $455 errDs (hang (text "A lazy (~) pattern cannot bind variables of unlifted type."$$456 text "Unlifted variables:") 457 2 (vcat (map (\id -> ppr id <+> dcolon <+> ppr (idType id)) 458 unlifted_bndrs))) 460 ; (_,sel_prs) <- mkSelectorBinds [] pat (Var v) 461 ; let sel_binds = [NonRec b rhs | (b,rhs) <- sel_prs] 462 ; return (mkCoreLets sel_binds, WildPat (idType v)) } 464 tidy1 _ (ListPat pats ty Nothing) 465 = return (idDsWrapper, unLoc list_ConPat) 466 where 467 list_ConPat = foldr (\ x y -> mkPrefixConPat consDataCon [x, y] [ty]) 468 (mkNilPat ty) 469 pats 471 -- Introduce fake parallel array constructors to be able to handle parallel 472 -- arrays with the existing machinery for constructor pattern 473 tidy1 _ (PArrPat pats ty) 474 = return (idDsWrapper, unLoc parrConPat) 475 where 476 arity = length pats 477 parrConPat = mkPrefixConPat (parrFakeCon arity) pats [ty] 479 tidy1 _ (TuplePat pats boxity tys) 480 = return (idDsWrapper, unLoc tuple_ConPat) 481 where 482 arity = length pats 483 tuple_ConPat = mkPrefixConPat (tupleDataCon boxity arity) pats tys 485 tidy1 _ (SumPat pat alt arity tys) 486 = return (idDsWrapper, unLoc sum_ConPat) 487 where 488 sum_ConPat = mkPrefixConPat (sumDataCon alt arity) [pat] tys 490 -- LitPats: we *might* be able to replace these w/ a simpler form 491 tidy1 _ (LitPat lit) 492 = return (idDsWrapper, tidyLitPat lit) 494 -- NPats: we *might* be able to replace these w/ a simpler form 495 tidy1 _ (NPat (L _ lit) mb_neg eq ty) 496 = return (idDsWrapper, tidyNPat tidyLitPat lit mb_neg eq ty) 498 -- Everything else goes through unchanged... 500 tidy1 _ non_interesting_pat 501 = return (idDsWrapper, non_interesting_pat) 503 -------------------- 504 tidy_bang_pat :: Id -> SrcSpan -> Pat Id -> DsM (DsWrapper, Pat Id) 506 -- Discard par/sig under a bang 507 tidy_bang_pat v _ (ParPat (L l p)) = tidy_bang_pat v l p 508 tidy_bang_pat v _ (SigPatOut (L l p) _) = tidy_bang_pat v l p 510 -- Push the bang-pattern inwards, in the hope that 511 -- it may disappear next time 512 tidy_bang_pat v l (AsPat v' p) = tidy1 v (AsPat v' (L l (BangPat p))) 513 tidy_bang_pat v l (CoPat w p t) = tidy1 v (CoPat w (BangPat (L l p)) t) 515 -- Discard bang around strict pattern 516 tidy_bang_pat v _ p@(LitPat {}) = tidy1 v p 517 tidy_bang_pat v _ p@(ListPat {}) = tidy1 v p 518 tidy_bang_pat v _ p@(TuplePat {}) = tidy1 v p 519 tidy_bang_pat v _ p@(SumPat {}) = tidy1 v p 520 tidy_bang_pat v _ p@(PArrPat {}) = tidy1 v p 522 -- Data/newtype constructors 523 tidy_bang_pat v l p@(ConPatOut { pat_con = L _ (RealDataCon dc) 524 , pat_args = args 525 , pat_arg_tys = arg_tys }) 526 -- Newtypes: push bang inwards (Trac #9844) 527 = 528 if isNewTyCon (dataConTyCon dc) 529 then tidy1 v (p { pat_args = push_bang_into_newtype_arg l ty args }) 530 else tidy1 v p -- Data types: discard the bang 531 where 532 (ty:_) = dataConInstArgTys dc arg_tys 534 ------------------- 535 -- Default case, leave the bang there: 536 -- VarPat, 537 -- LazyPat, 538 -- WildPat, 539 -- ViewPat, 540 -- pattern synonyms (ConPatOut with PatSynCon) 541 -- NPat, 542 -- NPlusKPat 543 -- 544 -- For LazyPat, remember that it's semantically like a VarPat 545 -- i.e. !(~p) is not like ~p, or p! (Trac #8952) 546 -- 547 -- NB: SigPatIn, ConPatIn should not happen 549 tidy_bang_pat _ l p = return (idDsWrapper, BangPat (L l p)) 551 ------------------- 552 push_bang_into_newtype_arg :: SrcSpan 553 -> Type -- The type of the argument we are pushing 554 -- onto 555 -> HsConPatDetails Id -> HsConPatDetails Id 556 -- See Note [Bang patterns and newtypes] 557 -- We are transforming !(N p) into (N !p) 558 push_bang_into_newtype_arg l _ty (PrefixCon (arg:args)) 559 = ASSERT( null args) 560 PrefixCon [L l (BangPat arg)] 561 push_bang_into_newtype_arg l _ty (RecCon rf) 562 | HsRecFields { rec_flds = L lf fld : flds } <- rf 563 , HsRecField { hsRecFieldArg = arg } <- fld 564 = ASSERT( null flds) 565 RecCon (rf { rec_flds = [L lf (fld { hsRecFieldArg = L l (BangPat arg) })] }) 566 push_bang_into_newtype_arg l ty (RecCon rf) -- If a user writes !(T {}) 567 | HsRecFields { rec_flds = [] } <- rf 568 = PrefixCon [L l (BangPat (noLoc (WildPat ty)))] 569 push_bang_into_newtype_arg _ _ cd 570 = pprPanic "push_bang_into_newtype_arg" (pprConArgs cd) 572 {- 573 Note [Bang patterns and newtypes] 574 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 575 For the pattern !(Just pat) we can discard the bang, because 576 the pattern is strict anyway. But for !(N pat), where 577 newtype NT = N Int 578 we definitely can't discard the bang. Trac #9844. 580 So what we do is to push the bang inwards, in the hope that it will 581 get discarded there. So we transform 582 !(N pat) into (N !pat) 584 But what if there is nothing to push the bang onto? In at least one instance 585 a user has written !(N {}) which we translate into (N !_). See #13215 588 \noindent 589 {\bf Previous @matchTwiddled@ stuff:} 591 Now we get to the only interesting part; note: there are choices for 592 translation [from Simon's notes]; translation~1: 593 \begin{verbatim} 594 deTwiddle [s,t] e 595 \end{verbatim} 596 returns 597 \begin{verbatim} 598 [ w = e, 599 s = case w of [s,t] -> s 600 t = case w of [s,t] -> t 601 ] 602 \end{verbatim} 604 Here \tr{w} is a fresh variable, and the \tr{w}-binding prevents multiple 605 evaluation of \tr{e}. An alternative translation (No.~2): 606 \begin{verbatim} 607 [ w = case e of [s,t] -> (s,t) 608 s = case w of (s,t) -> s 609 t = case w of (s,t) -> t 610 ] 611 \end{verbatim} 613 ************************************************************************ 614 * * 615 \subsubsection[improved-unmixing]{UNIMPLEMENTED idea for improved unmixing} 616 * * 617 ************************************************************************ 619 We might be able to optimise unmixing when confronted by 620 only-one-constructor-possible, of which tuples are the most notable 621 examples. Consider: 622 \begin{verbatim} 623 f (a,b,c) ... = ... 624 f d ... (e:f) = ... 625 f (g,h,i) ... = ... 626 f j ... = ... 627 \end{verbatim} 628 This definition would normally be unmixed into four equation blocks, 629 one per equation. But it could be unmixed into just one equation 630 block, because if the one equation matches (on the first column), 631 the others certainly will. 633 You have to be careful, though; the example 634 \begin{verbatim} 635 f j ... = ... 636 ------------------- 637 f (a,b,c) ... = ... 638 f d ... (e:f) = ... 639 f (g,h,i) ... = ... 640 \end{verbatim} 641 {\em must} be broken into two blocks at the line shown; otherwise, you 642 are forcing unnecessary evaluation. In any case, the top-left pattern 643 always gives the cue. You could then unmix blocks into groups of... 644 \begin{description} 645 \item[all variables:] 646 As it is now. 647 \item[constructors or variables (mixed):] 648 Need to make sure the right names get bound for the variable patterns. 649 \item[literals or variables (mixed):] 650 Presumably just a variant on the constructor case (as it is now). 651 \end{description} 653 ************************************************************************ 654 * * 655 * matchWrapper: a convenient way to call @match@ * 656 * * 657 ************************************************************************ 658 \subsection[matchWrapper]{@matchWrapper@: a convenient interface to @match@} 660 Calls to @match@ often involve similar (non-trivial) work; that work 661 is collected here, in @matchWrapper@. This function takes as 662 arguments: 663 \begin{itemize} 664 \item 665 Typchecked @Matches@ (of a function definition, or a case or lambda 666 expression)---the main input; 667 \item 668 An error message to be inserted into any (runtime) pattern-matching 669 failure messages. 670 \end{itemize} 672 As results, @matchWrapper@ produces: 673 \begin{itemize} 674 \item 675 A list of variables (@Locals@) that the caller must promise'' to 676 bind to appropriate values; and 677 \item 678 a @CoreExpr@, the desugared output (main result). 679 \end{itemize} 681 The main actions of @matchWrapper@ include: 682 \begin{enumerate} 683 \item 684 Flatten the @[TypecheckedMatch]@ into a suitable list of 685 @EquationInfo@s. 686 \item 687 Create as many new variables as there are patterns in a pattern-list 688 (in any one of the @EquationInfo@s). 689 \item 690 Create a suitable if it fails'' expression---a call to @error@ using 691 the error-string input; the {\em type} of this fail value can be found 692 by examining one of the RHS expressions in one of the @EquationInfo@s. 693 \item 694 Call @match@ with all of this information! 695 \end{enumerate} 696 -} 698 matchWrapper :: HsMatchContext Name -- For shadowing warning messages 699 -> Maybe (LHsExpr Id) -- The scrutinee, if we check a case expr 700 -> MatchGroup Id (LHsExpr Id) -- Matches being desugared 701 -> DsM ([Id], CoreExpr) -- Results 703 {- 704 There is one small problem with the Lambda Patterns, when somebody 705 writes something similar to: 706 \begin{verbatim} 707 (\ (x:xs) -> ...) 708 \end{verbatim} 709 he/she don't want a warning about incomplete patterns, that is done with 710 the flag @opt_WarnSimplePatterns@. 711 This problem also appears in the: 712 \begin{itemize} 713 \item @do@ patterns, but if the @do@ can fail 714 it creates another equation if the match can fail 715 (see @DsExpr.doDo@ function) 716 \item @let@ patterns, are treated by @matchSimply@ 717 List Comprension Patterns, are treated by @matchSimply@ also 718 \end{itemize} 720 We can't call @matchSimply@ with Lambda patterns, 721 due to the fact that lambda patterns can have more than 722 one pattern, and match simply only accepts one pattern. 724 JJQC 30-Nov-1997 725 -} 727 matchWrapper ctxt mb_scr (MG { mg_alts = L _ matches 728 , mg_arg_tys = arg_tys 729 , mg_res_ty = rhs_ty 730 , mg_origin = origin }) 731 = do { dflags <- getDynFlags 732 ; locn <- getSrcSpanDs 734 ; new_vars <- case matches of 735 [] -> mapM newSysLocalDsNoLP arg_tys 736 (m:_) -> selectMatchVars (map unLoc (hsLMatchPats m)) 738 ; eqns_info <- mapM (mk_eqn_info new_vars) matches 740 -- pattern match check warnings 741 ; unless (isGenerated origin)$
742 when (isAnyPmCheckEnabled dflags (DsMatchContext ctxt locn)) $743 addTmCsDs (genCaseTmCs1 mb_scr new_vars)$
744 -- See Note [Type and Term Equality Propagation]
745 checkMatches dflags (DsMatchContext ctxt locn) new_vars matches
747 ; result_expr <- handleWarnings $748 matchEquations ctxt new_vars eqns_info rhs_ty 749 ; return (new_vars, result_expr) } 750 where 751 mk_eqn_info vars (L _ (Match _ pats _ grhss)) 752 = do { dflags <- getDynFlags 753 ; let upats = map (unLoc . decideBangHood dflags) pats 754 dicts = toTcTypeBag (collectEvVarsPats upats) -- Only TcTyVars 755 ; tm_cs <- genCaseTmCs2 mb_scr upats vars 756 ; match_result <- addDictsDs dicts$ -- See Note [Type and Term Equality Propagation]
757 addTmCsDs tm_cs $-- See Note [Type and Term Equality Propagation] 758 dsGRHSs ctxt upats grhss rhs_ty 759 ; return (EqnInfo { eqn_pats = upats, eqn_rhs = match_result}) } 761 handleWarnings = if isGenerated origin 762 then discardWarningsDs 763 else id 766 matchEquations :: HsMatchContext Name 767 -> [MatchId] -> [EquationInfo] -> Type 768 -> DsM CoreExpr 769 matchEquations ctxt vars eqns_info rhs_ty 770 = do { let error_doc = matchContextErrString ctxt 772 ; match_result <- match vars rhs_ty eqns_info 774 ; fail_expr <- mkErrorAppDs pAT_ERROR_ID rhs_ty error_doc 775 ; extractMatchResult match_result fail_expr } 777 {- 778 ************************************************************************ 779 * * 780 \subsection[matchSimply]{@matchSimply@: match a single expression against a single pattern} 781 * * 782 ************************************************************************ 784 @mkSimpleMatch@ is a wrapper for @match@ which deals with the 785 situation where we want to match a single expression against a single 786 pattern. It returns an expression. 787 -} 789 matchSimply :: CoreExpr -- Scrutinee 790 -> HsMatchContext Name -- Match kind 791 -> LPat Id -- Pattern it should match 792 -> CoreExpr -- Return this if it matches 793 -> CoreExpr -- Return this if it doesn't 794 -> DsM CoreExpr 795 -- Do not warn about incomplete patterns; see matchSinglePat comments 796 matchSimply scrut hs_ctx pat result_expr fail_expr = do 797 let 798 match_result = cantFailMatchResult result_expr 799 rhs_ty = exprType fail_expr 800 -- Use exprType of fail_expr, because won't refine in the case of failure! 801 match_result' <- matchSinglePat scrut hs_ctx pat rhs_ty match_result 802 extractMatchResult match_result' fail_expr 804 matchSinglePat :: CoreExpr -> HsMatchContext Name -> LPat Id 805 -> Type -> MatchResult -> DsM MatchResult 806 -- matchSinglePat ensures that the scrutinee is a variable 807 -- and then calls match_single_pat_var 808 -- 809 -- matchSinglePat does not warn about incomplete patterns 810 -- Used for things like [ e | pat <- stuff ], where 811 -- incomplete patterns are just fine 813 matchSinglePat (Var var) ctx pat ty match_result 814 | not (isExternalName (idName var)) 815 = match_single_pat_var var ctx pat ty match_result 817 matchSinglePat scrut hs_ctx pat ty match_result 818 = do { var <- selectSimpleMatchVarL pat 819 ; match_result' <- match_single_pat_var var hs_ctx pat ty match_result 820 ; return (adjustMatchResult (bindNonRec var scrut) match_result') } 822 match_single_pat_var :: Id -- See Note [Match Ids] 823 -> HsMatchContext Name -> LPat Id 824 -> Type -> MatchResult -> DsM MatchResult 825 match_single_pat_var var ctx pat ty match_result 826 = ASSERT2( isInternalName (idName var), ppr var ) 827 do { dflags <- getDynFlags 828 ; locn <- getSrcSpanDs 830 -- Pattern match check warnings 831 ; checkSingle dflags (DsMatchContext ctx locn) var (unLoc pat) 833 ; let eqn_info = EqnInfo { eqn_pats = [unLoc (decideBangHood dflags pat)] 834 , eqn_rhs = match_result } 835 ; match [var] ty [eqn_info] } 838 {- 839 ************************************************************************ 840 * * 841 Pattern classification 842 * * 843 ************************************************************************ 844 -} 846 data PatGroup 847 = PgAny -- Immediate match: variables, wildcards, 848 -- lazy patterns 849 | PgCon DataCon -- Constructor patterns (incl list, tuple) 850 | PgSyn PatSyn [Type] -- See Note [Pattern synonym groups] 851 | PgLit Literal -- Literal patterns 852 | PgN Rational -- Overloaded numeric literals; 853 -- see Note [Don't use Literal for PgN] 854 | PgOverS FastString -- Overloaded string literals 855 | PgNpK Integer -- n+k patterns 856 | PgBang -- Bang patterns 857 | PgCo Type -- Coercion patterns; the type is the type 858 -- of the pattern *inside* 859 | PgView (LHsExpr Id) -- view pattern (e -> p): 860 -- the LHsExpr is the expression e 861 Type -- the Type is the type of p (equivalently, the result type of e) 862 | PgOverloadedList 864 {- Note [Don't use Literal for PgN] 865 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 866 Previously we had, as PatGroup constructors 868 | ... 869 | PgN Literal -- Overloaded literals 870 | PgNpK Literal -- n+k patterns 871 | ... 873 But Literal is really supposed to represent an *unboxed* literal, like Int#. 874 We were sticking the literal from, say, an overloaded numeric literal pattern 875 into a MachInt constructor. This didn't really make sense; and we now have 876 the invariant that value in a MachInt must be in the range of the target 877 machine's Int# type, and an overloaded literal could meaningfully be larger. 879 Solution: For pattern grouping purposes, just store the literal directly in 880 the PgN constructor as a Rational if numeric, and add a PgOverStr constructor 881 for overloaded strings. 882 -} 884 groupEquations :: DynFlags -> [EquationInfo] -> [[(PatGroup, EquationInfo)]] 885 -- If the result is of form [g1, g2, g3], 886 -- (a) all the (pg,eq) pairs in g1 have the same pg 887 -- (b) none of the gi are empty 888 -- The ordering of equations is unchanged 889 groupEquations dflags eqns 890 = runs same_gp [(patGroup dflags (firstPat eqn), eqn) | eqn <- eqns] 891 where 892 same_gp :: (PatGroup,EquationInfo) -> (PatGroup,EquationInfo) -> Bool 893 (pg1,_) same_gp (pg2,_) = pg1 sameGroup pg2 895 subGroup :: (m -> [[EquationInfo]]) -- Map.elems 896 -> m -- Map.empty 897 -> (a -> m -> Maybe [EquationInfo]) -- Map.lookup 898 -> (a -> [EquationInfo] -> m -> m) -- Map.insert 899 -> [(a, EquationInfo)] -> [[EquationInfo]] 900 -- Input is a particular group. The result sub-groups the 901 -- equations by with particular constructor, literal etc they match. 902 -- Each sub-list in the result has the same PatGroup 903 -- See Note [Take care with pattern order] 904 -- Parameterized by map operations to allow different implementations 905 -- and constraints, eg. types without Ord instance. 906 subGroup elems empty lookup insert group 907 = map reverse$ elems \$ foldl accumulate empty group
908 where
909 accumulate pg_map (pg, eqn)
910 = case lookup pg pg_map of
911 Just eqns -> insert pg (eqn:eqns) pg_map
912 Nothing -> insert pg [eqn] pg_map
913 -- pg_map :: Map a [EquationInfo]
914 -- Equations seen so far in reverse order of appearance
916 subGroupOrd :: Ord a => [(a, EquationInfo)] -> [[EquationInfo]]
917 subGroupOrd = subGroup Map.elems Map.empty Map.lookup Map.insert
919 subGroupUniq :: Uniquable a => [(a, EquationInfo)] -> [[EquationInfo]]
920 subGroupUniq =
921 subGroup eltsUDFM emptyUDFM (flip lookupUDFM) (\k v m -> addToUDFM m k v)
923 {- Note [Pattern synonym groups]
924 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
925 If we see
926 f (P a) = e1
927 f (P b) = e2
928 ...
929 where P is a pattern synonym, can we put (P a -> e1) and (P b -> e2) in the
930 same group? We can if P is a constructor, but /not/ if P is a pattern synonym.
931 Consider (Trac #11224)
933 pattern PRead :: Read a => () => a -> String
936 f (PRead (x::Int)) = e1
937 f (PRead (y::Bool)) = e2
938 This is all fine: we match the string by trying to read an Int; if that
939 fails we try to read a Bool. But clearly we can't combine the two into a single
940 match.
942 Conclusion: we can combine when we invoke PRead /at the same type/. Hence
943 in PgSyn we record the instantiaing types, and use them in sameGroup.
945 Note [Take care with pattern order]
946 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
947 In the subGroup function we must be very careful about pattern re-ordering,
948 Consider the patterns [ (True, Nothing), (False, x), (True, y) ]
949 Then in bringing together the patterns for True, we must not
950 swap the Nothing and y!
951 -}
953 sameGroup :: PatGroup -> PatGroup -> Bool
954 -- Same group means that a single case expression
955 -- or test will suffice to match both, *and* the order
956 -- of testing within the group is insignificant.
957 sameGroup PgAny PgAny = True
958 sameGroup PgBang PgBang = True
959 sameGroup (PgCon _) (PgCon _) = True -- One case expression
960 sameGroup (PgSyn p1 t1) (PgSyn p2 t2) = p1==p2 && eqTypes t1 t2
961 -- eqTypes: See Note [Pattern synonym groups]
962 sameGroup (PgLit _) (PgLit _) = True -- One case expression
963 sameGroup (PgN l1) (PgN l2) = l1==l2 -- Order is significant
964 sameGroup (PgOverS s1) (PgOverS s2) = s1==s2
965 sameGroup (PgNpK l1) (PgNpK l2) = l1==l2 -- See Note [Grouping overloaded literal patterns]
966 sameGroup (PgCo t1) (PgCo t2) = t1 eqType t2
967 -- CoPats are in the same goup only if the type of the
968 -- enclosed pattern is the same. The patterns outside the CoPat
969 -- always have the same type, so this boils down to saying that
970 -- the two coercions are identical.
971 sameGroup (PgView e1 t1) (PgView e2 t2) = viewLExprEq (e1,t1) (e2,t2)
972 -- ViewPats are in the same group iff the expressions
973 -- are "equal"---conservatively, we use syntactic equality
974 sameGroup _ _ = False
976 -- An approximation of syntactic equality used for determining when view
977 -- exprs are in the same group.
978 -- This function can always safely return false;
979 -- but doing so will result in the application of the view function being repeated.
980 --
981 -- Currently: compare applications of literals and variables
982 -- and anything else that we can do without involving other
983 -- HsSyn types in the recursion
984 --
985 -- NB we can't assume that the two view expressions have the same type. Consider
986 -- f (e1 -> True) = ...
987 -- f (e2 -> "hi") = ...
988 viewLExprEq :: (LHsExpr Id,Type) -> (LHsExpr Id,Type) -> Bool
989 viewLExprEq (e1,_) (e2,_) = lexp e1 e2
990 where
991 lexp :: LHsExpr Id -> LHsExpr Id -> Bool
992 lexp e e' = exp (unLoc e) (unLoc e')
994 ---------
995 exp :: HsExpr Id -> HsExpr Id -> Bool
996 -- real comparison is on HsExpr's
997 -- strip parens
998 exp (HsPar (L _ e)) e' = exp e e'
999 exp e (HsPar (L _ e')) = exp e e'
1000 -- because the expressions do not necessarily have the same type,
1001 -- we have to compare the wrappers
1002 exp (HsWrap h e) (HsWrap h' e') = wrap h h' && exp e e'
1003 exp (HsVar i) (HsVar i') = i == i'
1004 exp (HsConLikeOut c) (HsConLikeOut c') = c == c'
1005 -- the instance for IPName derives using the id, so this works if the
1006 -- above does
1007 exp (HsIPVar i) (HsIPVar i') = i == i'
1008 exp (HsOverLabel l x) (HsOverLabel l' x') = l == l' && x == x'
1009 exp (HsOverLit l) (HsOverLit l') =
1010 -- Overloaded lits are equal if they have the same type
1011 -- and the data is the same.
1012 -- this is coarser than comparing the SyntaxExpr's in l and l',
1014 -- because these expressions get written as a bunch of different variables
1015 -- (presumably to improve sharing)
1016 eqType (overLitType l) (overLitType l') && l == l'
1017 exp (HsApp e1 e2) (HsApp e1' e2') = lexp e1 e1' && lexp e2 e2'
1018 -- the fixities have been straightened out by now, so it's safe
1019 -- to ignore them?
1020 exp (OpApp l o _ ri) (OpApp l' o' _ ri') =
1021 lexp l l' && lexp o o' && lexp ri ri'
1022 exp (NegApp e n) (NegApp e' n') = lexp e e' && syn_exp n n'
1023 exp (SectionL e1 e2) (SectionL e1' e2') =
1024 lexp e1 e1' && lexp e2 e2'
1025 exp (SectionR e1 e2) (SectionR e1' e2') =
1026 lexp e1 e1' && lexp e2 e2'
1027 exp (ExplicitTuple es1 _) (ExplicitTuple es2 _) =
1028 eq_list tup_arg es1 es2
1029 exp (ExplicitSum _ _ e _) (ExplicitSum _ _ e' _) = lexp e e'
1030 exp (HsIf _ e e1 e2) (HsIf _ e' e1' e2') =
1031 lexp e e' && lexp e1 e1' && lexp e2 e2'
1033 -- Enhancement: could implement equality for more expressions
1034 -- if it seems useful
1035 -- But no need for HsLit, ExplicitList, ExplicitTuple,
1036 -- because they cannot be functions
1037 exp _ _ = False
1039 ---------
1040 syn_exp :: SyntaxExpr Id -> SyntaxExpr Id -> Bool
1041 syn_exp (SyntaxExpr { syn_expr = expr1
1042 , syn_arg_wraps = arg_wraps1
1043 , syn_res_wrap = res_wrap1 })
1044 (SyntaxExpr { syn_expr = expr2
1045 , syn_arg_wraps = arg_wraps2
1046 , syn_res_wrap = res_wrap2 })
1047 = exp expr1 expr2 &&
1048 and (zipWithEqual "viewLExprEq" wrap arg_wraps1 arg_wraps2) &&
1049 wrap res_wrap1 res_wrap2
1051 ---------
1052 tup_arg (L _ (Present e1)) (L _ (Present e2)) = lexp e1 e2
1053 tup_arg (L _ (Missing t1)) (L _ (Missing t2)) = eqType t1 t2
1054 tup_arg _ _ = False
1056 ---------
1057 wrap :: HsWrapper -> HsWrapper -> Bool
1058 -- Conservative, in that it demands that wrappers be
1059 -- syntactically identical and doesn't look under binders
1060 --
1061 -- Coarser notions of equality are possible
1062 -- (e.g., reassociating compositions,
1063 -- equating different ways of writing a coercion)
1064 wrap WpHole WpHole = True
1065 wrap (WpCompose w1 w2) (WpCompose w1' w2') = wrap w1 w1' && wrap w2 w2'
1066 wrap (WpFun w1 w2 _ _) (WpFun w1' w2' _ _) = wrap w1 w1' && wrap w2 w2'
1067 wrap (WpCast co) (WpCast co') = co eqCoercion co'
1068 wrap (WpEvApp et1) (WpEvApp et2) = et1 ev_term et2
1069 wrap (WpTyApp t) (WpTyApp t') = eqType t t'
1070 -- Enhancement: could implement equality for more wrappers
1071 -- if it seems useful (lams and lets)
1072 wrap _ _ = False
1074 ---------
1075 ev_term :: EvTerm -> EvTerm -> Bool
1076 ev_term (EvId a) (EvId b) = a==b
1077 ev_term (EvCoercion a) (EvCoercion b) = a eqCoercion b
1078 ev_term _ _ = False
1080 ---------
1081 eq_list :: (a->a->Bool) -> [a] -> [a] -> Bool
1082 eq_list _ [] [] = True
1083 eq_list _ [] (_:_) = False
1084 eq_list _ (_:_) [] = False
1085 eq_list eq (x:xs) (y:ys) = eq x y && eq_list eq xs ys
1087 patGroup :: DynFlags -> Pat Id -> PatGroup
1088 patGroup _ (ConPatOut { pat_con = L _ con
1089 , pat_arg_tys = tys })
1090 | RealDataCon dcon <- con = PgCon dcon
1091 | PatSynCon psyn <- con = PgSyn psyn tys
1092 patGroup _ (WildPat {}) = PgAny
1093 patGroup _ (BangPat {}) = PgBang
1094 patGroup _ (NPat (L _ OverLit {ol_val=oval}) mb_neg _ _) =
1095 case (oval, isJust mb_neg) of
1096 (HsIntegral _ i, False) -> PgN (fromInteger i)
1097 (HsIntegral _ i, True ) -> PgN (-fromInteger i)
1098 (HsFractional r, False) -> PgN (fl_value r)
1099 (HsFractional r, True ) -> PgN (-fl_value r)
1100 (HsIsString _ s, _) -> ASSERT(isNothing mb_neg)
1101 PgOverS s
1102 patGroup _ (NPlusKPat _ (L _ OverLit {ol_val=oval}) _ _ _ _) =
1103 case oval of
1104 HsIntegral _ i -> PgNpK i
1105 _ -> pprPanic "patGroup NPlusKPat" (ppr oval)
1106 patGroup _ (CoPat _ p _) = PgCo (hsPatType p) -- Type of innelexp pattern
1107 patGroup _ (ViewPat expr p _) = PgView expr (hsPatType (unLoc p))
1108 patGroup _ (ListPat _ _ (Just _)) = PgOverloadedList
1109 patGroup dflags (LitPat lit) = PgLit (hsLitKey dflags lit)
1110 patGroup _ pat = pprPanic "patGroup" (ppr pat)
1112 {-
1113 Note [Grouping overloaded literal patterns]
1114 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1115 WATCH OUT! Consider
1117 f (n+1) = ...
1118 f (n+2) = ...
1119 f (n+1) = ...
1121 We can't group the first and third together, because the second may match
1122 the same thing as the first. Same goes for *overloaded* literal patterns
1123 f 1 True = ...
1124 f 2 False = ...
1125 f 1 False = ...
1126 If the first arg matches '1' but the second does not match 'True', we
1127 cannot jump to the third equation! Because the same argument might
1128 match '2'!
1129 Hence we don't regard 1 and 2, or (n+1) and (n+2), as part of the same group.
1130 -}