<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html> <head> <!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ --> <title>types/InstEnv.lhs</title> <link type='text/css' rel='stylesheet' href='hscolour.css' /> </head> <body> % % (c) The University of Glasgow 2006 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998 % \section[InstEnv]{Utilities for typechecking instance declarations} The bits common to TcInstDcls and TcDeriv. \begin{code} <pre><a name="line-1"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>InstEnv</span> <span class='hs-layout'>(</span> <a name="line-2"></a> <span class='hs-conid'>DFunId</span><span class='hs-layout'>,</span> <span class='hs-conid'>OverlapFlag</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <a name="line-3"></a> <span class='hs-conid'>Instance</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>pprInstance</span><span class='hs-layout'>,</span> <span class='hs-varid'>pprInstanceHdr</span><span class='hs-layout'>,</span> <span class='hs-varid'>pprInstances</span><span class='hs-layout'>,</span> <a name="line-4"></a> <span class='hs-varid'>instanceHead</span><span class='hs-layout'>,</span> <span class='hs-varid'>mkLocalInstance</span><span class='hs-layout'>,</span> <span class='hs-varid'>mkImportedInstance</span><span class='hs-layout'>,</span> <a name="line-5"></a> <span class='hs-varid'>instanceDFunId</span><span class='hs-layout'>,</span> <span class='hs-varid'>setInstanceDFunId</span><span class='hs-layout'>,</span> <span class='hs-varid'>instanceRoughTcs</span><span class='hs-layout'>,</span> <a name="line-6"></a> <a name="line-7"></a> <span class='hs-conid'>InstEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyInstEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>extendInstEnv</span><span class='hs-layout'>,</span> <a name="line-8"></a> <span class='hs-varid'>extendInstEnvList</span><span class='hs-layout'>,</span> <span class='hs-varid'>lookupInstEnv</span><span class='hs-layout'>,</span> <span class='hs-varid'>instEnvElts</span><span class='hs-layout'>,</span> <a name="line-9"></a> <span class='hs-varid'>classInstances</span><span class='hs-layout'>,</span> <span class='hs-varid'>instanceBindFun</span><span class='hs-layout'>,</span> <a name="line-10"></a> <span class='hs-varid'>instanceCantMatch</span><span class='hs-layout'>,</span> <span class='hs-varid'>roughMatchTcs</span> <a name="line-11"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span> <a name="line-12"></a> <a name="line-13"></a><span class='hs-cpp'>#include "HsVersions.h"</span> <a name="line-14"></a> <a name="line-15"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Class</span> <a name="line-16"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Var</span> <a name="line-17"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>VarSet</span> <a name="line-18"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Name</span> <a name="line-19"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>TcType</span> <a name="line-20"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>TyCon</span> <a name="line-21"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Unify</span> <a name="line-22"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Outputable</span> <a name="line-23"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>BasicTypes</span> <a name="line-24"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqFM</span> <a name="line-25"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Id</span> <a name="line-26"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>FastString</span> <a name="line-27"></a> <a name="line-28"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span> <span class='hs-varid'>isJust</span><span class='hs-layout'>,</span> <span class='hs-varid'>isNothing</span> <span class='hs-layout'>)</span> </pre>\end{code} %************************************************************************ %* * \subsection{The key types} %* * %************************************************************************ \begin{code} <pre><a name="line-1"></a><a name="DFunId"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>DFunId</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Id</span> <a name="line-2"></a><a name="Instance"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Instance</span> <a name="line-3"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Instance</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_cls</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Name</span> <span class='hs-comment'>-- Class name</span> <a name="line-4"></a> <a name="line-5"></a> <span class='hs-comment'>-- Used for "rough matching"; see Note [Rough-match field]</span> <a name="line-6"></a> <span class='hs-comment'>-- INVARIANT: is_tcs = roughMatchTcs is_tys</span> <a name="line-7"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>is_tcs</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Name</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- Top of type args</span> <a name="line-8"></a> <a name="line-9"></a> <span class='hs-comment'>-- Used for "proper matching"; see Note [Proper-match fields]</span> <a name="line-10"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>is_tvs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TyVarSet</span> <span class='hs-comment'>-- Template tyvars for full match</span> <a name="line-11"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>is_tys</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Type</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- Full arg types</span> <a name="line-12"></a> <span class='hs-comment'>-- INVARIANT: is_dfun Id has type </span> <a name="line-13"></a> <span class='hs-comment'>-- forall is_tvs. (...) => is_cls is_tys</span> <a name="line-14"></a> <a name="line-15"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>is_dfun</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>DFunId</span> <a name="line-16"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>is_flag</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>OverlapFlag</span> <span class='hs-comment'>-- See detailed comments with</span> <a name="line-17"></a> <span class='hs-comment'>-- the decl of BasicTypes.OverlapFlag</span> <a name="line-18"></a> <span class='hs-layout'>}</span> </pre>\end{code} Note [Rough-match field] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ The is_cls, is_tcs fields allow a "rough match" to be done without poking inside the DFunId. Poking the DFunId forces us to suck in all the type constructors etc it involves, which is a total waste of time if it has no chance of matching So the Name, [Maybe Name] fields allow us to say "definitely does not match", based only on the Name. In is_tcs, Nothing means that this type arg is a type variable (Just n) means that this type arg is a TyConApp with a type constructor of n. This is always a real tycon, never a synonym! (Two different synonyms might match, but two different real tycons can't.) NB: newtypes are not transparent, though! Note [Proper-match fields] ~~~~~~~~~~~~~~~~~~~~~~~~~ The is_tvs, is_tys fields are simply cached values, pulled out (lazily) from the dfun id. They are cached here simply so that we don't need to decompose the DFunId each time we want to match it. The hope is that the fast-match fields mean that we often never poke th proper-match fields However, note that: * is_tvs must be a superset of the free vars of is_tys * The is_dfun must itself be quantified over exactly is_tvs (This is so that we can use the matching substitution to instantiate the dfun's context.) \begin{code} <pre><a name="line-1"></a><a name="instanceDFunId"></a><span class='hs-definition'>instanceDFunId</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>DFunId</span> <a name="line-2"></a><span class='hs-definition'>instanceDFunId</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>is_dfun</span> <a name="line-3"></a> <a name="line-4"></a><a name="setInstanceDFunId"></a><span class='hs-definition'>setInstanceDFunId</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>DFunId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Instance</span> <a name="line-5"></a><span class='hs-definition'>setInstanceDFunId</span> <span class='hs-varid'>ispec</span> <span class='hs-varid'>dfun</span> <a name="line-6"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ASSERT</span><span class='hs-layout'>(</span> <span class='hs-varid'>idType</span> <span class='hs-varid'>dfun</span> <span class='hs-varop'>`tcEqType`</span> <span class='hs-varid'>idType</span> <span class='hs-layout'>(</span><span class='hs-varid'>is_dfun</span> <span class='hs-varid'>ispec</span><span class='hs-layout'>)</span> <span class='hs-layout'>)</span> <a name="line-7"></a> <span class='hs-comment'>-- We need to create the cached fields afresh from</span> <a name="line-8"></a> <span class='hs-comment'>-- the new dfun id. In particular, the is_tvs in</span> <a name="line-9"></a> <span class='hs-comment'>-- the Instance must match those in the dfun!</span> <a name="line-10"></a> <span class='hs-comment'>-- We assume that the only thing that changes is</span> <a name="line-11"></a> <span class='hs-comment'>-- the quantified type variables, so the other fields</span> <a name="line-12"></a> <span class='hs-comment'>-- are ok; hence the assert</span> <a name="line-13"></a> <span class='hs-varid'>ispec</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_dfun</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tvs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkVarSet</span> <span class='hs-varid'>tvs</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tys</span> <span class='hs-layout'>}</span> <a name="line-14"></a> <span class='hs-keyword'>where</span> <a name="line-15"></a> <span class='hs-layout'>(</span><span class='hs-varid'>tvs</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-varid'>tys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tcSplitDFunTy</span> <span class='hs-layout'>(</span><span class='hs-varid'>idType</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>)</span> <a name="line-16"></a> <a name="line-17"></a><a name="instanceRoughTcs"></a><span class='hs-definition'>instanceRoughTcs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Name</span><span class='hs-keyglyph'>]</span> <a name="line-18"></a><span class='hs-definition'>instanceRoughTcs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>is_tcs</span> </pre>\end{code} \begin{code} <pre><a name="line-1"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>NamedThing</span> <span class='hs-conid'>Instance</span> <span class='hs-keyword'>where</span> <a name="line-2"></a> <span class='hs-varid'>getName</span> <span class='hs-varid'>ispec</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getName</span> <span class='hs-layout'>(</span><span class='hs-varid'>is_dfun</span> <span class='hs-varid'>ispec</span><span class='hs-layout'>)</span> <a name="line-3"></a> <a name="line-4"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Outputable</span> <span class='hs-conid'>Instance</span> <span class='hs-keyword'>where</span> <a name="line-5"></a> <span class='hs-varid'>ppr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprInstance</span> <a name="line-6"></a> <a name="line-7"></a><a name="pprInstance"></a><span class='hs-definition'>pprInstance</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span> <a name="line-8"></a><span class='hs-comment'>-- Prints the Instance as an instance declaration</span> <a name="line-9"></a><span class='hs-definition'>pprInstance</span> <span class='hs-varid'>ispec</span> <a name="line-10"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>hang</span> <span class='hs-layout'>(</span><span class='hs-varid'>pprInstanceHdr</span> <span class='hs-varid'>ispec</span><span class='hs-layout'>)</span> <a name="line-11"></a> <span class='hs-num'>2</span> <span class='hs-layout'>(</span><span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"--"</span><span class='hs-layout'>)</span> <span class='hs-varop'><+></span> <span class='hs-varid'>pprNameLoc</span> <span class='hs-layout'>(</span><span class='hs-varid'>getName</span> <span class='hs-varid'>ispec</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <a name="line-12"></a> <a name="line-13"></a><a name="pprInstanceHdr"></a><span class='hs-comment'>-- * pprInstanceHdr is used in VStudio to populate the ClassView tree</span> <a name="line-14"></a><span class='hs-definition'>pprInstanceHdr</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span> <a name="line-15"></a><span class='hs-comment'>-- Prints the Instance as an instance declaration</span> <a name="line-16"></a><span class='hs-definition'>pprInstanceHdr</span> <span class='hs-varid'>ispec</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Instance</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_flag</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>flag</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span> <a name="line-17"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"instance"</span><span class='hs-layout'>)</span> <span class='hs-varop'><+></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>flag</span> <a name="line-18"></a> <span class='hs-varop'><+></span> <span class='hs-varid'>sep</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>pprThetaArrow</span> <span class='hs-varid'>theta</span><span class='hs-layout'>,</span> <span class='hs-varid'>pprClassPred</span> <span class='hs-varid'>clas</span> <span class='hs-varid'>tys</span><span class='hs-keyglyph'>]</span> <a name="line-19"></a> <span class='hs-keyword'>where</span> <a name="line-20"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-varid'>theta</span><span class='hs-layout'>,</span> <span class='hs-varid'>clas</span><span class='hs-layout'>,</span> <span class='hs-varid'>tys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>instanceHead</span> <span class='hs-varid'>ispec</span> <a name="line-21"></a> <span class='hs-comment'>-- Print without the for-all, which the programmer doesn't write</span> <a name="line-22"></a> <a name="line-23"></a><a name="pprInstances"></a><span class='hs-definition'>pprInstances</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Instance</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span> <a name="line-24"></a><span class='hs-definition'>pprInstances</span> <span class='hs-varid'>ispecs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>vcat</span> <span class='hs-layout'>(</span><span class='hs-varid'>map</span> <span class='hs-varid'>pprInstance</span> <span class='hs-varid'>ispecs</span><span class='hs-layout'>)</span> <a name="line-25"></a> <a name="line-26"></a><a name="instanceHead"></a><span class='hs-definition'>instanceHead</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-conid'>TyVar</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>PredType</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-conid'>Class</span><span class='hs-layout'>,</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Type</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <a name="line-27"></a><span class='hs-definition'>instanceHead</span> <span class='hs-varid'>ispec</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tcSplitDFunTy</span> <span class='hs-layout'>(</span><span class='hs-varid'>idType</span> <span class='hs-layout'>(</span><span class='hs-varid'>is_dfun</span> <span class='hs-varid'>ispec</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <a name="line-28"></a> <a name="line-29"></a><a name="mkLocalInstance"></a><span class='hs-definition'>mkLocalInstance</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>DFunId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>OverlapFlag</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Instance</span> <a name="line-30"></a><span class='hs-comment'>-- Used for local instances, where we can safely pull on the DFunId</span> <a name="line-31"></a><span class='hs-definition'>mkLocalInstance</span> <span class='hs-varid'>dfun</span> <span class='hs-varid'>oflag</span> <a name="line-32"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Instance</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_flag</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>oflag</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_dfun</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>,</span> <a name="line-33"></a> <span class='hs-varid'>is_tvs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkVarSet</span> <span class='hs-varid'>tvs</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tys</span><span class='hs-layout'>,</span> <a name="line-34"></a> <span class='hs-varid'>is_cls</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>className</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tcs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>roughMatchTcs</span> <span class='hs-varid'>tys</span> <span class='hs-layout'>}</span> <a name="line-35"></a> <span class='hs-keyword'>where</span> <a name="line-36"></a> <span class='hs-layout'>(</span><span class='hs-varid'>tvs</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-varid'>tys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tcSplitDFunTy</span> <span class='hs-layout'>(</span><span class='hs-varid'>idType</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>)</span> <a name="line-37"></a> <a name="line-38"></a><a name="mkImportedInstance"></a><span class='hs-definition'>mkImportedInstance</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Name</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Name</span><span class='hs-keyglyph'>]</span> <a name="line-39"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>DFunId</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>OverlapFlag</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Instance</span> <a name="line-40"></a><span class='hs-comment'>-- Used for imported instances, where we get the rough-match stuff</span> <a name="line-41"></a><span class='hs-comment'>-- from the interface file</span> <a name="line-42"></a><span class='hs-definition'>mkImportedInstance</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>mb_tcs</span> <span class='hs-varid'>dfun</span> <span class='hs-varid'>oflag</span> <a name="line-43"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Instance</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_flag</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>oflag</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_dfun</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>,</span> <a name="line-44"></a> <span class='hs-varid'>is_tvs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkVarSet</span> <span class='hs-varid'>tvs</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tys</span><span class='hs-layout'>,</span> <a name="line-45"></a> <span class='hs-varid'>is_cls</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>cls</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tcs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mb_tcs</span> <span class='hs-layout'>}</span> <a name="line-46"></a> <span class='hs-keyword'>where</span> <a name="line-47"></a> <span class='hs-layout'>(</span><span class='hs-varid'>tvs</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-varid'>tys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tcSplitDFunTy</span> <span class='hs-layout'>(</span><span class='hs-varid'>idType</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>)</span> <a name="line-48"></a> <a name="line-49"></a><a name="roughMatchTcs"></a><span class='hs-definition'>roughMatchTcs</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Type</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Name</span><span class='hs-keyglyph'>]</span> <a name="line-50"></a><span class='hs-definition'>roughMatchTcs</span> <span class='hs-varid'>tys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-varid'>rough</span> <span class='hs-varid'>tys</span> <a name="line-51"></a> <span class='hs-keyword'>where</span> <a name="line-52"></a> <span class='hs-varid'>rough</span> <span class='hs-varid'>ty</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>tcSplitTyConApp_maybe</span> <span class='hs-varid'>ty</span> <span class='hs-keyword'>of</span> <a name="line-53"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>tc</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>tyConName</span> <span class='hs-varid'>tc</span><span class='hs-layout'>)</span> <a name="line-54"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Nothing</span> <a name="line-55"></a> <a name="line-56"></a><a name="instanceCantMatch"></a><span class='hs-definition'>instanceCantMatch</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Name</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Maybe</span> <span class='hs-conid'>Name</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span> <a name="line-57"></a><span class='hs-comment'>-- (instanceCantMatch tcs1 tcs2) returns True if tcs1 cannot</span> <a name="line-58"></a><span class='hs-comment'>-- possibly be instantiated to actual, nor vice versa; </span> <a name="line-59"></a><span class='hs-comment'>-- False is non-committal</span> <a name="line-60"></a><span class='hs-definition'>instanceCantMatch</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>t</span> <span class='hs-conop'>:</span> <span class='hs-varid'>ts</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>a</span> <span class='hs-conop'>:</span> <span class='hs-keyword'>as</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>t</span><span class='hs-varop'>/=</span><span class='hs-varid'>a</span> <span class='hs-varop'>||</span> <span class='hs-varid'>instanceCantMatch</span> <span class='hs-varid'>ts</span> <span class='hs-keyword'>as</span> <a name="line-61"></a><span class='hs-definition'>instanceCantMatch</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span> <span class='hs-comment'>-- Safe</span> </pre>\end{code} Note [Overlapping instances] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Overlap is permitted, but only in such a way that one can make a unique choice when looking up. That is, overlap is only permitted if one template matches the other, or vice versa. So this is ok: [a] [Int] but this is not (Int,a) (b,Int) If overlap is permitted, the list is kept most specific first, so that the first lookup is the right choice. For now we just use association lists. \subsection{Avoiding a problem with overlapping} Consider this little program: \begin{pseudocode} class C a where c :: a class C a => D a where d :: a instance C Int where c = 17 instance D Int where d = 13 instance C a => C [a] where c = [c] instance ({- C [a], -} D a) => D [a] where d = c instance C [Int] where c = [37] main = print (d :: [Int]) \end{pseudocode} What do you think `main' prints (assuming we have overlapping instances, and all that turned on)? Well, the instance for `D' at type `[a]' is defined to be `c' at the same type, and we've got an instance of `C' at `[Int]', so the answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because the `C [Int]' instance is more specific). Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That was easy ;-) Let's just consult hugs for good measure. Wait - if I use old hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it doesn't even compile! What's going on!? What hugs complains about is the `D [a]' instance decl. \begin{pseudocode} ERROR "mj.hs" (line 10): Cannot build superclass instance *** Instance : D [a] *** Context supplied : D a *** Required superclass : C [a] \end{pseudocode} You might wonder what hugs is complaining about. It's saying that you need to add `C [a]' to the context of the `D [a]' instance (as appears in comments). But there's that `C [a]' instance decl one line above that says that I can reduce the need for a `C [a]' instance to the need for a `C a' instance, and in this case, I already have the necessary `C a' instance (since we have `D a' explicitly in the context, and `C' is a superclass of `D'). Unfortunately, the above reasoning indicates a premature commitment to the generic `C [a]' instance. I.e., it prematurely rules out the more specific instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to add the context that hugs suggests (uncomment the `C [a]'), effectively deferring the decision about which instance to use. Now, interestingly enough, 4.04 has this same bug, but it's covered up in this case by a little known `optimization' that was disabled in 4.06. Ghc-4.04 silently inserts any missing superclass context into an instance declaration. In this case, it silently inserts the `C [a]', and everything happens to work out. (See `basicTypes/MkId:mkDictFunId' for the code in question. Search for `Mark Jones', although Mark claims no credit for the `optimization' in question, and would rather it stopped being called the `Mark Jones optimization' ;-) So, what's the fix? I think hugs has it right. Here's why. Let's try something else out with ghc-4.04. Let's add the following line: d' :: D a => [a] d' = c Everyone raise their hand who thinks that `d :: [Int]' should give a different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The `optimization' only applies to instance decls, not to regular bindings, giving inconsistent behavior. Old hugs had this same bug. Here's how we fixed it: like GHC, the list of instances for a given class is ordered, so that more specific instances come before more generic ones. For example, the instance list for C might contain: ..., C Int, ..., C a, ... When we go to look for a `C Int' instance we'll get that one first. But what if we go looking for a `C b' (`b' is unconstrained)? We'll pass the `C Int' instance, and keep going. But if `b' is unconstrained, then we don't know yet if the more specific instance will eventually apply. GHC keeps going, and matches on the generic `C a'. The fix is to, at each step, check to see if there's a reverse match, and if so, abort the search. This prevents hugs from prematurely chosing a generic instance when a more specific one exists. --Jeff BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in this test. Suppose the instance envt had ..., forall a b. C a a b, ..., forall a b c. C a b c, ... (still most specific first) Now suppose we are looking for (C x y Int), where x and y are unconstrained. C x y Int doesn't match the template {a,b} C a a b but neither does C a a b match the template {x,y} C x y Int But still x and y might subsequently be unified so they *do* match. Simple story: unify, don't match. %************************************************************************ %* * InstEnv, ClsInstEnv %* * %************************************************************************ A @ClsInstEnv@ all the instances of that class. The @Id@ inside a ClsInstEnv mapping is the dfun for that instance. If class C maps to a list containing the item ([a,b], [t1,t2,t3], dfun), then forall a b, C t1 t2 t3 can be constructed by dfun or, to put it another way, we have instance (...) => C t1 t2 t3, witnessed by dfun \begin{code} <pre><a name="line-1"></a><a name="InstEnv"></a><span class='hs-comment'>---------------------------------------------------</span> <a name="line-2"></a><a name="InstEnv"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>InstEnv</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>UniqFM</span> <span class='hs-conid'>ClsInstEnv</span> <span class='hs-comment'>-- Maps Class to instances for that class</span> <a name="line-3"></a> <a name="line-4"></a><a name="ClsInstEnv"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ClsInstEnv</span> <a name="line-5"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ClsIE</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Instance</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- The instances for a particular class, in any order</span> <a name="line-6"></a> <span class='hs-conid'>Bool</span> <span class='hs-comment'>-- True <=> there is an instance of form C a b c</span> <a name="line-7"></a> <span class='hs-comment'>-- If *not* then the common case of looking up</span> <a name="line-8"></a> <span class='hs-comment'>-- (C a b c) can fail immediately</span> <a name="line-9"></a> <a name="line-10"></a><span class='hs-comment'>-- INVARIANTS:</span> <a name="line-11"></a><span class='hs-comment'>-- * The is_tvs are distinct in each Instance</span> <a name="line-12"></a><span class='hs-comment'>-- of a ClsInstEnv (so we can safely unify them)</span> <a name="line-13"></a> <a name="line-14"></a><span class='hs-comment'>-- Thus, the @ClassInstEnv@ for @Eq@ might contain the following entry:</span> <a name="line-15"></a><span class='hs-comment'>-- [a] ===> dfun_Eq_List :: forall a. Eq a => Eq [a]</span> <a name="line-16"></a><span class='hs-comment'>-- The "a" in the pattern must be one of the forall'd variables in</span> <a name="line-17"></a><span class='hs-comment'>-- the dfun type.</span> <a name="line-18"></a> <a name="line-19"></a><a name="emptyInstEnv"></a><span class='hs-definition'>emptyInstEnv</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>InstEnv</span> <a name="line-20"></a><span class='hs-definition'>emptyInstEnv</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>emptyUFM</span> <a name="line-21"></a> <a name="line-22"></a><a name="instEnvElts"></a><span class='hs-definition'>instEnvElts</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>InstEnv</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Instance</span><span class='hs-keyglyph'>]</span> <a name="line-23"></a><span class='hs-definition'>instEnvElts</span> <span class='hs-varid'>ie</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>elt</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>ClsIE</span> <span class='hs-varid'>elts</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>eltsUFM</span> <span class='hs-varid'>ie</span><span class='hs-layout'>,</span> <span class='hs-varid'>elt</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>elts</span><span class='hs-keyglyph'>]</span> <a name="line-24"></a> <a name="line-25"></a><a name="classInstances"></a><span class='hs-definition'>classInstances</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>InstEnv</span><span class='hs-layout'>,</span><span class='hs-conid'>InstEnv</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Class</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Instance</span><span class='hs-keyglyph'>]</span> <a name="line-26"></a><span class='hs-definition'>classInstances</span> <span class='hs-layout'>(</span><span class='hs-varid'>pkg_ie</span><span class='hs-layout'>,</span> <span class='hs-varid'>home_ie</span><span class='hs-layout'>)</span> <span class='hs-varid'>cls</span> <a name="line-27"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>get</span> <span class='hs-varid'>home_ie</span> <span class='hs-varop'>++</span> <span class='hs-varid'>get</span> <span class='hs-varid'>pkg_ie</span> <a name="line-28"></a> <span class='hs-keyword'>where</span> <a name="line-29"></a> <span class='hs-varid'>get</span> <span class='hs-varid'>env</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>env</span> <span class='hs-varid'>cls</span> <span class='hs-keyword'>of</span> <a name="line-30"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>ClsIE</span> <span class='hs-varid'>insts</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>insts</span> <a name="line-31"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>[]</span> <a name="line-32"></a> <a name="line-33"></a><a name="extendInstEnvList"></a><span class='hs-definition'>extendInstEnvList</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>InstEnv</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Instance</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>InstEnv</span> <a name="line-34"></a><span class='hs-definition'>extendInstEnvList</span> <span class='hs-varid'>inst_env</span> <span class='hs-varid'>ispecs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldl</span> <span class='hs-varid'>extendInstEnv</span> <span class='hs-varid'>inst_env</span> <span class='hs-varid'>ispecs</span> <a name="line-35"></a> <a name="line-36"></a><a name="extendInstEnv"></a><span class='hs-definition'>extendInstEnv</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>InstEnv</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Instance</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>InstEnv</span> <a name="line-37"></a><span class='hs-definition'>extendInstEnv</span> <span class='hs-varid'>inst_env</span> <span class='hs-varid'>ins_item</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Instance</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_cls</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>cls_nm</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tcs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mb_tcs</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span> <a name="line-38"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>addToUFM_C</span> <span class='hs-varid'>add</span> <span class='hs-varid'>inst_env</span> <span class='hs-varid'>cls_nm</span> <span class='hs-layout'>(</span><span class='hs-conid'>ClsIE</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>ins_item</span><span class='hs-keyglyph'>]</span> <span class='hs-varid'>ins_tyvar</span><span class='hs-layout'>)</span> <a name="line-39"></a> <span class='hs-keyword'>where</span> <a name="line-40"></a> <span class='hs-varid'>add</span> <span class='hs-layout'>(</span><span class='hs-conid'>ClsIE</span> <span class='hs-varid'>cur_insts</span> <span class='hs-varid'>cur_tyvar</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ClsIE</span> <span class='hs-layout'>(</span><span class='hs-varid'>ins_item</span> <span class='hs-conop'>:</span> <span class='hs-varid'>cur_insts</span><span class='hs-layout'>)</span> <a name="line-41"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ins_tyvar</span> <span class='hs-varop'>||</span> <span class='hs-varid'>cur_tyvar</span><span class='hs-layout'>)</span> <a name="line-42"></a> <span class='hs-varid'>ins_tyvar</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>not</span> <span class='hs-layout'>(</span><span class='hs-varid'>any</span> <span class='hs-varid'>isJust</span> <span class='hs-varid'>mb_tcs</span><span class='hs-layout'>)</span> </pre>\end{code} %************************************************************************ %* * Looking up an instance %* * %************************************************************************ @lookupInstEnv@ looks up in a @InstEnv@, using a one-way match. Since the env is kept ordered, the first match must be the only one. The thing we are looking up can have an arbitrary "flexi" part. \begin{code} <pre><a name="line-1"></a><a name="InstTypes"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>InstTypes</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Either</span> <span class='hs-conid'>TyVar</span> <span class='hs-conid'>Type</span><span class='hs-keyglyph'>]</span> <a name="line-2"></a> <span class='hs-comment'>-- Right ty => Instantiate with this type</span> <a name="line-3"></a> <span class='hs-comment'>-- Left tv => Instantiate with any type of this tyvar's kind</span> <a name="line-4"></a> <a name="line-5"></a><a name="InstMatch"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>InstMatch</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>Instance</span><span class='hs-layout'>,</span> <span class='hs-conid'>InstTypes</span><span class='hs-layout'>)</span> </pre>\end{code} Note [InstTypes: instantiating types] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A successful match is an Instance, together with the types at which the dfun_id in the Instance should be instantiated The instantiating types are (Mabye Type)s because the dfun might have some tyvars that *only* appear in arguments dfun :: forall a b. C a b, Ord b => D [a] When we match this against D [ty], we return the instantiating types [Right ty, Left b] where the Nothing indicates that 'b' can be freely instantiated. (The caller instantiates it to a flexi type variable, which will presumably presumably later become fixed via functional dependencies.) \begin{code} <pre><a name="line-1"></a><a name="lookupInstEnv"></a><span class='hs-definition'>lookupInstEnv</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>InstEnv</span><span class='hs-layout'>,</span> <span class='hs-conid'>InstEnv</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- External and home package inst-env</span> <a name="line-2"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Class</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Type</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- What we are looking for</span> <a name="line-3"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>[</span><span class='hs-conid'>InstMatch</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span> <span class='hs-comment'>-- Successful matches</span> <a name="line-4"></a> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Instance</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- These don't match but do unify</span> <a name="line-5"></a> <a name="line-6"></a><span class='hs-comment'>-- The second component of the result pair happens when we look up</span> <a name="line-7"></a><span class='hs-comment'>-- Foo [a]</span> <a name="line-8"></a><span class='hs-comment'>-- in an InstEnv that has entries for</span> <a name="line-9"></a><span class='hs-comment'>-- Foo [Int]</span> <a name="line-10"></a><span class='hs-comment'>-- Foo [b]</span> <a name="line-11"></a><span class='hs-comment'>-- Then which we choose would depend on the way in which 'a'</span> <a name="line-12"></a><span class='hs-comment'>-- is instantiated. So we report that Foo [b] is a match (mapping b->a)</span> <a name="line-13"></a><span class='hs-comment'>-- but Foo [Int] is a unifier. This gives the caller a better chance of</span> <a name="line-14"></a><span class='hs-comment'>-- giving a suitable error messagen</span> <a name="line-15"></a> <a name="line-16"></a><span class='hs-definition'>lookupInstEnv</span> <span class='hs-layout'>(</span><span class='hs-varid'>pkg_ie</span><span class='hs-layout'>,</span> <span class='hs-varid'>home_ie</span><span class='hs-layout'>)</span> <span class='hs-varid'>cls</span> <span class='hs-varid'>tys</span> <a name="line-17"></a> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>pruned_matches</span><span class='hs-layout'>,</span> <span class='hs-varid'>all_unifs</span><span class='hs-layout'>)</span> <a name="line-18"></a> <span class='hs-keyword'>where</span> <a name="line-19"></a> <span class='hs-varid'>rough_tcs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>roughMatchTcs</span> <span class='hs-varid'>tys</span> <a name="line-20"></a> <span class='hs-varid'>all_tvs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>all</span> <span class='hs-varid'>isNothing</span> <span class='hs-varid'>rough_tcs</span> <a name="line-21"></a> <span class='hs-layout'>(</span><span class='hs-varid'>home_matches</span><span class='hs-layout'>,</span> <span class='hs-varid'>home_unifs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lookup</span> <span class='hs-varid'>home_ie</span> <a name="line-22"></a> <span class='hs-layout'>(</span><span class='hs-varid'>pkg_matches</span><span class='hs-layout'>,</span> <span class='hs-varid'>pkg_unifs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lookup</span> <span class='hs-varid'>pkg_ie</span> <a name="line-23"></a> <span class='hs-varid'>all_matches</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>home_matches</span> <span class='hs-varop'>++</span> <span class='hs-varid'>pkg_matches</span> <a name="line-24"></a> <span class='hs-varid'>all_unifs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>home_unifs</span> <span class='hs-varop'>++</span> <span class='hs-varid'>pkg_unifs</span> <a name="line-25"></a> <span class='hs-varid'>pruned_matches</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldr</span> <span class='hs-varid'>insert_overlapping</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>all_matches</span> <a name="line-26"></a> <span class='hs-comment'>-- Even if the unifs is non-empty (an error situation)</span> <a name="line-27"></a> <span class='hs-comment'>-- we still prune the matches, so that the error message isn't</span> <a name="line-28"></a> <span class='hs-comment'>-- misleading (complaining of multiple matches when some should be</span> <a name="line-29"></a> <span class='hs-comment'>-- overlapped away)</span> <a name="line-30"></a> <a name="line-31"></a> <span class='hs-comment'>--------------</span> <a name="line-32"></a> <span class='hs-varid'>lookup</span> <span class='hs-varid'>env</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>env</span> <span class='hs-varid'>cls</span> <span class='hs-keyword'>of</span> <a name="line-33"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- No instances for this class</span> <a name="line-34"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-conid'>ClsIE</span> <span class='hs-varid'>insts</span> <span class='hs-varid'>has_tv_insts</span><span class='hs-layout'>)</span> <a name="line-35"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>all_tvs</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>not</span> <span class='hs-varid'>has_tv_insts</span> <a name="line-36"></a> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- Short cut for common case</span> <a name="line-37"></a> <span class='hs-comment'>-- The thing we are looking up is of form (C a b c), and</span> <a name="line-38"></a> <span class='hs-comment'>-- the ClsIE has no instances of that form, so don't bother to search</span> <a name="line-39"></a> <a name="line-40"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <a name="line-41"></a> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>find</span> <span class='hs-conid'>[]</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>insts</span> <a name="line-42"></a> <a name="line-43"></a> <span class='hs-comment'>--------------</span> <a name="line-44"></a> <span class='hs-varid'>lookup_tv</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TvSubst</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>TyVar</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Either</span> <span class='hs-conid'>TyVar</span> <span class='hs-conid'>Type</span> <a name="line-45"></a> <span class='hs-comment'>-- See Note [InstTypes: instantiating types]</span> <a name="line-46"></a> <span class='hs-varid'>lookup_tv</span> <span class='hs-varid'>subst</span> <span class='hs-varid'>tv</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupTyVar</span> <span class='hs-varid'>subst</span> <span class='hs-varid'>tv</span> <span class='hs-keyword'>of</span> <a name="line-47"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>ty</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-varid'>ty</span> <a name="line-48"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>tv</span> <a name="line-49"></a> <a name="line-50"></a> <span class='hs-varid'>find</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>us</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>ms</span><span class='hs-layout'>,</span> <span class='hs-varid'>us</span><span class='hs-layout'>)</span> <a name="line-51"></a> <span class='hs-varid'>find</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>us</span> <span class='hs-layout'>(</span><span class='hs-varid'>item</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Instance</span> <span class='hs-layout'>{</span> <span class='hs-varid'>is_tcs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mb_tcs</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_tvs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tpl_tvs</span><span class='hs-layout'>,</span> <a name="line-52"></a> <span class='hs-varid'>is_tys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tpl_tys</span><span class='hs-layout'>,</span> <span class='hs-varid'>is_flag</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>oflag</span><span class='hs-layout'>,</span> <a name="line-53"></a> <span class='hs-varid'>is_dfun</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>dfun</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>rest</span><span class='hs-layout'>)</span> <a name="line-54"></a> <span class='hs-comment'>-- Fast check for no match, uses the "rough match" fields</span> <a name="line-55"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>instanceCantMatch</span> <span class='hs-varid'>rough_tcs</span> <span class='hs-varid'>mb_tcs</span> <a name="line-56"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>find</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>us</span> <span class='hs-varid'>rest</span> <a name="line-57"></a> <a name="line-58"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>subst</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>tcMatchTys</span> <span class='hs-varid'>tpl_tvs</span> <span class='hs-varid'>tpl_tys</span> <span class='hs-varid'>tys</span> <a name="line-59"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <a name="line-60"></a> <span class='hs-layout'>(</span><span class='hs-varid'>dfun_tvs</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>tcSplitForAllTys</span> <span class='hs-layout'>(</span><span class='hs-varid'>idType</span> <span class='hs-varid'>dfun</span><span class='hs-layout'>)</span> <a name="line-61"></a> <span class='hs-keyword'>in</span> <a name="line-62"></a> <span class='hs-conid'>ASSERT</span><span class='hs-layout'>(</span> <span class='hs-varid'>all</span> <span class='hs-layout'>(</span><span class='hs-varop'>`elemVarSet`</span> <span class='hs-varid'>tpl_tvs</span><span class='hs-layout'>)</span> <span class='hs-varid'>dfun_tvs</span> <span class='hs-layout'>)</span> <span class='hs-comment'>-- Check invariant</span> <a name="line-63"></a> <span class='hs-varid'>find</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>item</span><span class='hs-layout'>,</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-varid'>lookup_tv</span> <span class='hs-varid'>subst</span><span class='hs-layout'>)</span> <span class='hs-varid'>dfun_tvs</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>ms</span><span class='hs-layout'>)</span> <span class='hs-varid'>us</span> <span class='hs-varid'>rest</span> <a name="line-64"></a> <a name="line-65"></a> <span class='hs-comment'>-- Does not match, so next check whether the things unify</span> <a name="line-66"></a> <span class='hs-comment'>-- See Note [overlapping instances] above</span> <a name="line-67"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Incoherent</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>oflag</span> <a name="line-68"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>find</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>us</span> <span class='hs-varid'>rest</span> <a name="line-69"></a> <a name="line-70"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <a name="line-71"></a> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ASSERT2</span><span class='hs-layout'>(</span> <span class='hs-varid'>tyVarsOfTypes</span> <span class='hs-varid'>tys</span> <span class='hs-varop'>`disjointVarSet`</span> <span class='hs-varid'>tpl_tvs</span><span class='hs-layout'>,</span> <a name="line-72"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ppr</span> <span class='hs-varid'>cls</span> <span class='hs-varop'><+></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>tys</span> <span class='hs-varop'><+></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>all_tvs</span><span class='hs-layout'>)</span> <span class='hs-varop'>$$</span> <a name="line-73"></a> <span class='hs-layout'>(</span><span class='hs-varid'>ppr</span> <span class='hs-varid'>dfun</span> <span class='hs-varop'><+></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>tpl_tvs</span> <span class='hs-varop'><+></span> <span class='hs-varid'>ppr</span> <span class='hs-varid'>tpl_tys</span><span class='hs-layout'>)</span> <a name="line-74"></a> <span class='hs-layout'>)</span> <a name="line-75"></a> <span class='hs-comment'>-- Unification will break badly if the variables overlap</span> <a name="line-76"></a> <span class='hs-comment'>-- They shouldn't because we allocate separate uniques for them</span> <a name="line-77"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>tcUnifyTys</span> <span class='hs-varid'>instanceBindFun</span> <span class='hs-varid'>tpl_tys</span> <span class='hs-varid'>tys</span> <span class='hs-keyword'>of</span> <a name="line-78"></a> <span class='hs-conid'>Just</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>find</span> <span class='hs-varid'>ms</span> <span class='hs-layout'>(</span><span class='hs-varid'>item</span><span class='hs-conop'>:</span><span class='hs-varid'>us</span><span class='hs-layout'>)</span> <span class='hs-varid'>rest</span> <a name="line-79"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>find</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>us</span> <span class='hs-varid'>rest</span> <a name="line-80"></a> <a name="line-81"></a><a name="insert_overlapping"></a><span class='hs-comment'>---------------</span> <a name="line-82"></a><span class='hs-comment'>---------------</span> <a name="line-83"></a><span class='hs-definition'>insert_overlapping</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>InstMatch</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>InstMatch</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>InstMatch</span><span class='hs-keyglyph'>]</span> <a name="line-84"></a><span class='hs-comment'>-- Add a new solution, knocking out strictly less specific ones</span> <a name="line-85"></a><span class='hs-definition'>insert_overlapping</span> <span class='hs-varid'>new_item</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>new_item</span><span class='hs-keyglyph'>]</span> <a name="line-86"></a><span class='hs-definition'>insert_overlapping</span> <span class='hs-varid'>new_item</span> <span class='hs-layout'>(</span><span class='hs-varid'>item</span><span class='hs-conop'>:</span><span class='hs-varid'>items</span><span class='hs-layout'>)</span> <a name="line-87"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>new_beats_old</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>old_beats_new</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>item</span> <span class='hs-conop'>:</span> <span class='hs-varid'>insert_overlapping</span> <span class='hs-varid'>new_item</span> <span class='hs-varid'>items</span> <a name="line-88"></a> <span class='hs-comment'>-- Duplicate => keep both for error report</span> <a name="line-89"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>new_beats_old</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>insert_overlapping</span> <span class='hs-varid'>new_item</span> <span class='hs-varid'>items</span> <a name="line-90"></a> <span class='hs-comment'>-- Keep new one</span> <a name="line-91"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>old_beats_new</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>item</span> <span class='hs-conop'>:</span> <span class='hs-varid'>items</span> <a name="line-92"></a> <span class='hs-comment'>-- Keep old one</span> <a name="line-93"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>item</span> <span class='hs-conop'>:</span> <span class='hs-varid'>insert_overlapping</span> <span class='hs-varid'>new_item</span> <span class='hs-varid'>items</span> <a name="line-94"></a> <span class='hs-comment'>-- Keep both</span> <a name="line-95"></a> <span class='hs-keyword'>where</span> <a name="line-96"></a> <span class='hs-varid'>new_beats_old</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>new_item</span> <span class='hs-varop'>`beats`</span> <span class='hs-varid'>item</span> <a name="line-97"></a> <span class='hs-varid'>old_beats_new</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>item</span> <span class='hs-varop'>`beats`</span> <span class='hs-varid'>new_item</span> <a name="line-98"></a> <a name="line-99"></a> <span class='hs-layout'>(</span><span class='hs-varid'>instA</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-varop'>`beats`</span> <span class='hs-layout'>(</span><span class='hs-varid'>instB</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <a name="line-100"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>overlap_ok</span> <span class='hs-varop'>&&</span> <a name="line-101"></a> <span class='hs-varid'>isJust</span> <span class='hs-layout'>(</span><span class='hs-varid'>tcMatchTys</span> <span class='hs-layout'>(</span><span class='hs-varid'>is_tvs</span> <span class='hs-varid'>instB</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>is_tys</span> <span class='hs-varid'>instB</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>is_tys</span> <span class='hs-varid'>instA</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <a name="line-102"></a> <span class='hs-comment'>-- A beats B if A is more specific than B, and B admits overlap</span> <a name="line-103"></a> <span class='hs-comment'>-- I.e. if B can be instantiated to match A</span> <a name="line-104"></a> <span class='hs-keyword'>where</span> <a name="line-105"></a> <span class='hs-varid'>overlap_ok</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>is_flag</span> <span class='hs-varid'>instB</span> <span class='hs-keyword'>of</span> <a name="line-106"></a> <span class='hs-conid'>NoOverlap</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>False</span> <a name="line-107"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span> </pre>\end{code} %************************************************************************ %* * Binding decisions %* * %************************************************************************ \begin{code} <pre><a name="line-1"></a><a name="instanceBindFun"></a><span class='hs-definition'>instanceBindFun</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>TyVar</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>BindFlag</span> <a name="line-2"></a><span class='hs-definition'>instanceBindFun</span> <span class='hs-varid'>tv</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>isTcTyVar</span> <span class='hs-varid'>tv</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>isExistentialTyVar</span> <span class='hs-varid'>tv</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Skolem</span> <a name="line-3"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>BindMe</span> <a name="line-4"></a> <span class='hs-comment'>-- Note [Binding when looking up instances]</span> </pre>\end{code} Note [Binding when looking up instances] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When looking up in the instance environment, or family-instance environment, we are careful about multiple matches, as described above in Note [Overlapping instances] The key_tys can contain skolem constants, and we can guarantee that those are never going to be instantiated to anything, so we should not involve them in the unification test. Example: class Foo a where { op :: a -> Int } instance Foo a => Foo [a] -- NB overlap instance Foo [Int] -- NB overlap data T = forall a. Foo a => MkT a f :: T -> Int f (MkT x) = op [x,x] The op [x,x] means we need (Foo [a]). Without the filterVarSet we'd complain, saying that the choice of instance depended on the instantiation of 'a'; but of course it isn't *going* to be instantiated. We do this only for pattern-bound skolems. For example we reject g :: forall a => [a] -> Int g x = op x on the grounds that the correct instance depends on the instantiation of 'a' </body> </html>