sigmatch.nim 95 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713
  1. #
  2. #
  3. # The Nim Compiler
  4. # (c) Copyright 2013 Andreas Rumpf
  5. #
  6. # See the file "copying.txt", included in this
  7. # distribution, for details about the copyright.
  8. #
  9. ## This module implements the signature matching for resolving
  10. ## the call to overloaded procs, generic procs and operators.
  11. import
  12. intsets, ast, astalgo, semdata, types, msgs, renderer, lookups, semtypinst,
  13. magicsys, idents, lexer, options, parampatterns, strutils, trees,
  14. linter, lineinfos, lowerings, modulegraphs
  15. when (defined(booting) or defined(nimsuggest)) and not defined(leanCompiler):
  16. import docgen
  17. type
  18. MismatchKind* = enum
  19. kUnknown, kAlreadyGiven, kUnknownNamedParam, kTypeMismatch, kVarNeeded,
  20. kMissingParam, kExtraArg
  21. MismatchInfo* = object
  22. kind*: MismatchKind # reason for mismatch
  23. arg*: int # position of provided arguments that mismatches
  24. formal*: PSym # parameter that mismatches against provided argument
  25. # its position can differ from `arg` because of varargs
  26. TCandidateState* = enum
  27. csEmpty, csMatch, csNoMatch
  28. CandidateError* = object
  29. sym*: PSym
  30. firstMismatch*: MismatchInfo
  31. diagnostics*: seq[string]
  32. enabled*: bool
  33. CandidateErrors* = seq[CandidateError]
  34. TCandidate* = object
  35. c*: PContext
  36. exactMatches*: int # also misused to prefer iters over procs
  37. genericMatches: int # also misused to prefer constraints
  38. subtypeMatches: int
  39. intConvMatches: int # conversions to int are not as expensive
  40. convMatches: int
  41. state*: TCandidateState
  42. callee*: PType # may not be nil!
  43. calleeSym*: PSym # may be nil
  44. calleeScope*: int # scope depth:
  45. # is this a top-level symbol or a nested proc?
  46. call*: PNode # modified call
  47. bindings*: TIdTable # maps types to types
  48. magic*: TMagic # magic of operation
  49. baseTypeMatch: bool # needed for conversions from T to openarray[T]
  50. # for example
  51. fauxMatch*: TTypeKind # the match was successful only due to the use
  52. # of error or wildcard (unknown) types.
  53. # this is used to prevent instantiations.
  54. genericConverter*: bool # true if a generic converter needs to
  55. # be instantiated
  56. coerceDistincts*: bool # this is an explicit coercion that can strip away
  57. # a distrinct type
  58. typedescMatched*: bool
  59. isNoCall*: bool # misused for generic type instantiations C[T]
  60. inferredTypes: seq[PType] # inferred types during the current signature
  61. # matching. they will be reset if the matching
  62. # is not successful. may replace the bindings
  63. # table in the future.
  64. diagnostics*: seq[string] # \
  65. # when diagnosticsEnabled, the matching process
  66. # will collect extra diagnostics that will be
  67. # displayed to the user.
  68. # triggered when overload resolution fails
  69. # or when the explain pragma is used. may be
  70. # triggered with an idetools command in the
  71. # future.
  72. inheritancePenalty: int # to prefer closest father object type
  73. firstMismatch*: MismatchInfo # mismatch info for better error messages
  74. diagnosticsEnabled*: bool
  75. TTypeRelFlag* = enum
  76. trDontBind
  77. trNoCovariance
  78. TTypeRelFlags* = set[TTypeRelFlag]
  79. TTypeRelation* = enum # order is important!
  80. isNone, isConvertible,
  81. isIntConv,
  82. isSubtype,
  83. isSubrange, # subrange of the wanted type; no type conversion
  84. # but apart from that counts as ``isSubtype``
  85. isBothMetaConvertible # generic proc parameter was matched against
  86. # generic type, e.g., map(mySeq, x=>x+1),
  87. # maybe recoverable by rerun if the parameter is
  88. # the proc's return value
  89. isInferred, # generic proc was matched against a concrete type
  90. isInferredConvertible, # same as above, but requiring proc CC conversion
  91. isGeneric,
  92. isFromIntLit, # conversion *from* int literal; proven safe
  93. isEqual
  94. const
  95. isNilConversion = isConvertible # maybe 'isIntConv' fits better?
  96. proc markUsed*(conf: ConfigRef; info: TLineInfo, s: PSym; usageSym: var PSym)
  97. template hasFauxMatch*(c: TCandidate): bool = c.fauxMatch != tyNone
  98. proc initCandidateAux(ctx: PContext,
  99. c: var TCandidate, callee: PType) {.inline.} =
  100. c.c = ctx
  101. c.exactMatches = 0
  102. c.subtypeMatches = 0
  103. c.convMatches = 0
  104. c.intConvMatches = 0
  105. c.genericMatches = 0
  106. c.state = csEmpty
  107. c.firstMismatch = MismatchInfo()
  108. c.callee = callee
  109. c.call = nil
  110. c.baseTypeMatch = false
  111. c.genericConverter = false
  112. c.inheritancePenalty = 0
  113. proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PType) =
  114. initCandidateAux(ctx, c, callee)
  115. c.calleeSym = nil
  116. initIdTable(c.bindings)
  117. proc put(c: var TCandidate, key, val: PType) {.inline.} =
  118. when false:
  119. let old = PType(idTableGet(c.bindings, key))
  120. if old != nil:
  121. echo "Putting ", typeToString(key), " ", typeToString(val), " and old is ", typeToString(old)
  122. if typeToString(old) == "seq[string]":
  123. writeStackTrace()
  124. if c.c.module.name.s == "temp3":
  125. echo "binding ", key, " -> ", val
  126. idTablePut(c.bindings, key, val.skipIntLit)
  127. proc initCandidate*(ctx: PContext, c: var TCandidate, callee: PSym,
  128. binding: PNode, calleeScope = -1,
  129. diagnosticsEnabled = false) =
  130. initCandidateAux(ctx, c, callee.typ)
  131. c.calleeSym = callee
  132. if callee.kind in skProcKinds and calleeScope == -1:
  133. if callee.originatingModule == ctx.module:
  134. c.calleeScope = 2
  135. var owner = callee
  136. while true:
  137. owner = owner.skipGenericOwner
  138. if owner.kind == skModule: break
  139. inc c.calleeScope
  140. else:
  141. c.calleeScope = 1
  142. else:
  143. c.calleeScope = calleeScope
  144. c.diagnostics = @[] # if diagnosticsEnabled: @[] else: nil
  145. c.diagnosticsEnabled = diagnosticsEnabled
  146. c.magic = c.calleeSym.magic
  147. initIdTable(c.bindings)
  148. if binding != nil and callee.kind in routineKinds:
  149. var typeParams = callee.ast[genericParamsPos]
  150. for i in 1..min(sonsLen(typeParams), sonsLen(binding)-1):
  151. var formalTypeParam = typeParams.sons[i-1].typ
  152. var bound = binding[i].typ
  153. if bound != nil:
  154. if formalTypeParam.kind == tyTypeDesc:
  155. if bound.kind != tyTypeDesc:
  156. bound = makeTypeDesc(ctx, bound)
  157. else:
  158. bound = bound.skipTypes({tyTypeDesc})
  159. put(c, formalTypeParam, bound)
  160. proc newCandidate*(ctx: PContext, callee: PSym,
  161. binding: PNode, calleeScope = -1): TCandidate =
  162. initCandidate(ctx, result, callee, binding, calleeScope)
  163. proc newCandidate*(ctx: PContext, callee: PType): TCandidate =
  164. initCandidate(ctx, result, callee)
  165. proc copyCandidate(a: var TCandidate, b: TCandidate) =
  166. a.c = b.c
  167. a.exactMatches = b.exactMatches
  168. a.subtypeMatches = b.subtypeMatches
  169. a.convMatches = b.convMatches
  170. a.intConvMatches = b.intConvMatches
  171. a.genericMatches = b.genericMatches
  172. a.state = b.state
  173. a.callee = b.callee
  174. a.calleeSym = b.calleeSym
  175. a.call = copyTree(b.call)
  176. a.baseTypeMatch = b.baseTypeMatch
  177. copyIdTable(a.bindings, b.bindings)
  178. proc sumGeneric(t: PType): int =
  179. # count the "genericness" so that Foo[Foo[T]] has the value 3
  180. # and Foo[T] has the value 2 so that we know Foo[Foo[T]] is more
  181. # specific than Foo[T].
  182. var t = t
  183. var isvar = 1
  184. while true:
  185. case t.kind
  186. of tyGenericInst, tyArray, tyRef, tyPtr, tyDistinct, tyUncheckedArray,
  187. tyOpenArray, tyVarargs, tySet, tyRange, tySequence, tyGenericBody,
  188. tyLent, tyOwned:
  189. t = t.lastSon
  190. inc result
  191. of tyOr:
  192. var maxBranch = 0
  193. for branch in t.sons:
  194. let branchSum = sumGeneric(branch)
  195. if branchSum > maxBranch: maxBranch = branchSum
  196. inc result, maxBranch
  197. break
  198. of tyVar:
  199. t = t.sons[0]
  200. inc result
  201. inc isvar
  202. of tyTypeDesc:
  203. t = t.lastSon
  204. if t.kind == tyEmpty: break
  205. inc result
  206. of tyGenericInvocation, tyTuple, tyProc, tyAnd:
  207. result += ord(t.kind in {tyGenericInvocation, tyAnd})
  208. for i in 0 ..< t.len:
  209. if t.sons[i] != nil:
  210. result += sumGeneric(t.sons[i])
  211. break
  212. of tyStatic:
  213. return sumGeneric(t.sons[0]) + 1
  214. of tyGenericParam, tyUntyped, tyTyped: break
  215. of tyAlias, tySink: t = t.lastSon
  216. of tyBool, tyChar, tyEnum, tyObject, tyPointer,
  217. tyString, tyCString, tyInt..tyInt64, tyFloat..tyFloat128,
  218. tyUInt..tyUInt64, tyCompositeTypeClass:
  219. return isvar
  220. else:
  221. return 0
  222. #var ggDebug: bool
  223. proc complexDisambiguation(a, b: PType): int =
  224. # 'a' matches better if *every* argument matches better or equal than 'b'.
  225. var winner = 0
  226. for i in 1 ..< min(a.len, b.len):
  227. let x = a.sons[i].sumGeneric
  228. let y = b.sons[i].sumGeneric
  229. #if ggDebug:
  230. #echo "came herA ", typeToString(a.sons[i]), " ", x
  231. #echo "came herB ", typeToString(b.sons[i]), " ", y
  232. if x != y:
  233. if winner == 0:
  234. if x > y: winner = 1
  235. else: winner = -1
  236. elif x > y:
  237. if winner != 1:
  238. # contradiction
  239. return 0
  240. else:
  241. if winner != -1:
  242. return 0
  243. result = winner
  244. when false:
  245. var x, y: int
  246. for i in 1 ..< a.len: x += a.sons[i].sumGeneric
  247. for i in 1 ..< b.len: y += b.sons[i].sumGeneric
  248. result = x - y
  249. proc writeMatches*(c: TCandidate) =
  250. echo "Candidate '", c.calleeSym.name.s, "' at ", c.c.config $ c.calleeSym.info
  251. echo " exact matches: ", c.exactMatches
  252. echo " generic matches: ", c.genericMatches
  253. echo " subtype matches: ", c.subtypeMatches
  254. echo " intconv matches: ", c.intConvMatches
  255. echo " conv matches: ", c.convMatches
  256. echo " inheritance: ", c.inheritancePenalty
  257. proc cmpCandidates*(a, b: TCandidate): int =
  258. result = a.exactMatches - b.exactMatches
  259. if result != 0: return
  260. result = a.genericMatches - b.genericMatches
  261. if result != 0: return
  262. result = a.subtypeMatches - b.subtypeMatches
  263. if result != 0: return
  264. result = a.intConvMatches - b.intConvMatches
  265. if result != 0: return
  266. result = a.convMatches - b.convMatches
  267. if result != 0: return
  268. # the other way round because of other semantics:
  269. result = b.inheritancePenalty - a.inheritancePenalty
  270. if result != 0: return
  271. # prefer more specialized generic over more general generic:
  272. result = complexDisambiguation(a.callee, b.callee)
  273. # only as a last resort, consider scoping:
  274. if result != 0: return
  275. result = a.calleeScope - b.calleeScope
  276. proc argTypeToString(arg: PNode; prefer: TPreferedDesc): string =
  277. if arg.kind in nkSymChoices:
  278. result = typeToString(arg[0].typ, prefer)
  279. for i in 1 ..< arg.len:
  280. result.add(" | ")
  281. result.add typeToString(arg[i].typ, prefer)
  282. elif arg.typ == nil:
  283. result = "void"
  284. else:
  285. result = arg.typ.typeToString(prefer)
  286. proc describeArgs*(c: PContext, n: PNode, startIdx = 1;
  287. prefer: TPreferedDesc = preferName): string =
  288. result = ""
  289. for i in startIdx ..< n.len:
  290. var arg = n.sons[i]
  291. if n.sons[i].kind == nkExprEqExpr:
  292. add(result, renderTree(n.sons[i].sons[0]))
  293. add(result, ": ")
  294. if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo}:
  295. # XXX we really need to 'tryExpr' here!
  296. arg = c.semOperand(c, n.sons[i].sons[1])
  297. n.sons[i].typ = arg.typ
  298. n.sons[i].sons[1] = arg
  299. else:
  300. if arg.typ.isNil and arg.kind notin {nkStmtList, nkDo, nkElse,
  301. nkOfBranch, nkElifBranch,
  302. nkExceptBranch}:
  303. arg = c.semOperand(c, n.sons[i])
  304. n.sons[i] = arg
  305. if arg.typ != nil and arg.typ.kind == tyError: return
  306. add(result, argTypeToString(arg, prefer))
  307. if i != sonsLen(n) - 1: add(result, ", ")
  308. proc typeRel*(c: var TCandidate, f, aOrig: PType,
  309. flags: TTypeRelFlags = {}): TTypeRelation
  310. proc concreteType(c: TCandidate, t: PType; f: PType = nil): PType =
  311. case t.kind
  312. of tyTypeDesc:
  313. if c.isNoCall: result = t
  314. else: result = nil
  315. of tySequence, tySet:
  316. if t.sons[0].kind == tyEmpty: result = nil
  317. else: result = t
  318. of tyGenericParam, tyAnything:
  319. result = t
  320. while true:
  321. result = PType(idTableGet(c.bindings, t))
  322. if result == nil:
  323. break # it's ok, no match
  324. # example code that triggers it:
  325. # proc sort[T](cmp: proc(a, b: T): int = cmp)
  326. if result.kind != tyGenericParam: break
  327. of tyGenericInvocation:
  328. result = t
  329. doAssert(false, "cannot resolve type: " & typeToString(t))
  330. of tyOwned:
  331. # bug #11257: the comparison system.`==`[T: proc](x, y: T) works
  332. # better without the 'owned' type:
  333. if f != nil and f.len > 0 and f.sons[0].skipTypes({tyBuiltInTypeClass}).kind == tyProc:
  334. result = t.lastSon
  335. else:
  336. result = t
  337. else:
  338. result = t # Note: empty is valid here
  339. proc handleRange(f, a: PType, min, max: TTypeKind): TTypeRelation =
  340. if a.kind == f.kind:
  341. result = isEqual
  342. else:
  343. let ab = skipTypes(a, {tyRange})
  344. let k = ab.kind
  345. if k == f.kind: result = isSubrange
  346. elif k == tyInt and f.kind in {tyRange, tyInt8..tyInt64,
  347. tyUInt..tyUInt64} and
  348. isIntLit(ab) and ab.n.intVal >= firstOrd(nil, f) and
  349. ab.n.intVal <= lastOrd(nil, f):
  350. # passing 'nil' to firstOrd/lastOrd here as type checking rules should
  351. # not depent on the target integer size configurations!
  352. # integer literal in the proper range; we want ``i16 + 4`` to stay an
  353. # ``int16`` operation so we declare the ``4`` pseudo-equal to int16
  354. result = isFromIntLit
  355. elif f.kind == tyInt and k in {tyInt8..tyInt32}:
  356. result = isIntConv
  357. elif f.kind == tyUInt and k in {tyUInt8..tyUInt32}:
  358. result = isIntConv
  359. elif k >= min and k <= max:
  360. result = isConvertible
  361. elif a.kind == tyRange and
  362. # Make sure the conversion happens between types w/ same signedness
  363. (f.kind in {tyInt..tyInt64} and a[0].kind in {tyInt..tyInt64} or
  364. f.kind in {tyUInt8..tyUInt32} and a[0].kind in {tyUInt8..tyInt32}) and
  365. a.n[0].intVal >= firstOrd(nil, f) and a.n[1].intVal <= lastOrd(nil, f):
  366. # passing 'nil' to firstOrd/lastOrd here as type checking rules should
  367. # not depent on the target integer size configurations!
  368. result = isConvertible
  369. else: result = isNone
  370. proc isConvertibleToRange(f, a: PType): bool =
  371. # be less picky for tyRange, as that it is used for array indexing:
  372. if f.kind in {tyInt..tyInt64, tyUInt..tyUInt64} and
  373. a.kind in {tyInt..tyInt64, tyUInt..tyUInt64}:
  374. case f.kind
  375. of tyInt, tyInt64: result = true
  376. of tyInt8: result = a.kind in {tyInt8, tyInt}
  377. of tyInt16: result = a.kind in {tyInt8, tyInt16, tyInt}
  378. of tyInt32: result = a.kind in {tyInt8, tyInt16, tyInt32, tyInt}
  379. of tyUInt, tyUInt64: result = true
  380. of tyUInt8: result = a.kind in {tyUInt8, tyUInt}
  381. of tyUInt16: result = a.kind in {tyUInt8, tyUInt16, tyUInt}
  382. of tyUInt32: result = a.kind in {tyUInt8, tyUInt16, tyUInt32, tyUInt}
  383. else: result = false
  384. elif f.kind in {tyFloat..tyFloat128} and
  385. a.kind in {tyFloat..tyFloat128}:
  386. result = true
  387. proc handleFloatRange(f, a: PType): TTypeRelation =
  388. if a.kind == f.kind:
  389. result = isEqual
  390. else:
  391. let ab = skipTypes(a, {tyRange})
  392. var k = ab.kind
  393. if k == f.kind: result = isSubrange
  394. elif isFloatLit(ab): result = isFromIntLit
  395. elif isIntLit(ab): result = isConvertible
  396. elif k >= tyFloat and k <= tyFloat128:
  397. # conversion to "float32" is not as good:
  398. if f.kind == tyFloat32: result = isConvertible
  399. else: result = isIntConv
  400. else: result = isNone
  401. proc genericParamPut(c: var TCandidate; last, fGenericOrigin: PType) =
  402. if fGenericOrigin != nil and last.kind == tyGenericInst and
  403. last.len-1 == fGenericOrigin.len:
  404. for i in 1 ..< sonsLen(fGenericOrigin):
  405. let x = PType(idTableGet(c.bindings, fGenericOrigin.sons[i]))
  406. if x == nil:
  407. put(c, fGenericOrigin.sons[i], last.sons[i])
  408. proc isObjectSubtype(c: var TCandidate; a, f, fGenericOrigin: PType): int =
  409. var t = a
  410. assert t.kind == tyObject
  411. var depth = 0
  412. var last = a
  413. while t != nil and not sameObjectTypes(f, t):
  414. assert t.kind == tyObject
  415. t = t.sons[0]
  416. if t == nil: break
  417. last = t
  418. t = skipTypes(t, skipPtrs)
  419. inc depth
  420. if t != nil:
  421. genericParamPut(c, last, fGenericOrigin)
  422. result = depth
  423. else:
  424. result = -1
  425. type
  426. SkippedPtr = enum skippedNone, skippedRef, skippedPtr
  427. proc skipToObject(t: PType; skipped: var SkippedPtr): PType =
  428. var r = t
  429. # we're allowed to skip one level of ptr/ref:
  430. var ptrs = 0
  431. while r != nil:
  432. case r.kind
  433. of tyGenericInvocation:
  434. r = r.sons[0]
  435. of tyRef:
  436. inc ptrs
  437. skipped = skippedRef
  438. r = r.lastSon
  439. of tyPtr:
  440. inc ptrs
  441. skipped = skippedPtr
  442. r = r.lastSon
  443. of tyGenericBody, tyGenericInst, tyAlias, tySink, tyOwned:
  444. r = r.lastSon
  445. else:
  446. break
  447. if r.kind == tyObject and ptrs <= 1: result = r
  448. proc isGenericSubtype(c: var TCandidate; a, f: PType, d: var int, fGenericOrigin: PType): bool =
  449. assert f.kind in {tyGenericInst, tyGenericInvocation, tyGenericBody}
  450. var askip = skippedNone
  451. var fskip = skippedNone
  452. var t = a.skipToObject(askip)
  453. let r = f.skipToObject(fskip)
  454. if r == nil: return false
  455. var depth = 0
  456. var last = a
  457. # XXX sameObjectType can return false here. Need to investigate
  458. # why that is but sameObjectType does way too much work here anyway.
  459. while t != nil and r.sym != t.sym and askip == fskip:
  460. t = t.sons[0]
  461. if t == nil: break
  462. last = t
  463. t = t.skipToObject(askip)
  464. inc depth
  465. if t != nil and askip == fskip:
  466. genericParamPut(c, last, fGenericOrigin)
  467. d = depth
  468. result = true
  469. proc minRel(a, b: TTypeRelation): TTypeRelation =
  470. if a <= b: result = a
  471. else: result = b
  472. proc recordRel(c: var TCandidate, f, a: PType): TTypeRelation =
  473. result = isNone
  474. if sameType(f, a):
  475. result = isEqual
  476. elif sonsLen(a) == sonsLen(f):
  477. result = isEqual
  478. let firstField = if f.kind == tyTuple: 0
  479. else: 1
  480. for i in firstField ..< sonsLen(f):
  481. var m = typeRel(c, f.sons[i], a.sons[i])
  482. if m < isSubtype: return isNone
  483. result = minRel(result, m)
  484. if f.n != nil and a.n != nil:
  485. for i in 0 ..< sonsLen(f.n):
  486. # check field names:
  487. if f.n.sons[i].kind != nkSym: return isNone
  488. elif a.n.sons[i].kind != nkSym: return isNone
  489. else:
  490. var x = f.n.sons[i].sym
  491. var y = a.n.sons[i].sym
  492. if f.kind == tyObject and typeRel(c, x.typ, y.typ) < isSubtype:
  493. return isNone
  494. if x.name.id != y.name.id: return isNone
  495. proc allowsNil(f: PType): TTypeRelation {.inline.} =
  496. result = if tfNotNil notin f.flags: isSubtype else: isNone
  497. proc allowsNilDeprecated(c: TCandidate, f: PType): TTypeRelation =
  498. if optNilSeqs in c.c.config.options:
  499. result = allowsNil(f)
  500. else:
  501. result = isNone
  502. proc inconsistentVarTypes(f, a: PType): bool {.inline.} =
  503. result = f.kind != a.kind and (f.kind in {tyVar, tyLent} or a.kind in {tyVar, tyLent})
  504. proc procParamTypeRel(c: var TCandidate, f, a: PType): TTypeRelation =
  505. ## For example we have:
  506. ## .. code-block:: nim
  507. ## proc myMap[T,S](sIn: seq[T], f: proc(x: T): S): seq[S] = ...
  508. ## proc innerProc[Q,W](q: Q): W = ...
  509. ## And we want to match: myMap(@[1,2,3], innerProc)
  510. ## This proc (procParamTypeRel) will do the following steps in
  511. ## three different calls:
  512. ## - matches f=T to a=Q. Since f is metatype, we resolve it
  513. ## to int (which is already known at this point). So in this case
  514. ## Q=int mapping will be saved to c.bindings.
  515. ## - matches f=S to a=W. Both of these metatypes are unknown, so we
  516. ## return with isBothMetaConvertible to ask for rerun.
  517. ## - matches f=S to a=W. At this point the return type of innerProc
  518. ## is known (we get it from c.bindings). We can use that value
  519. ## to match with f, and save back to c.bindings.
  520. var
  521. f = f
  522. a = a
  523. if a.isMetaType:
  524. let aResolved = PType(idTableGet(c.bindings, a))
  525. if aResolved != nil:
  526. a = aResolved
  527. if a.isMetaType:
  528. if f.isMetaType:
  529. # We are matching a generic proc (as proc param)
  530. # to another generic type appearing in the proc
  531. # signature. There is a change that the target
  532. # type is already fully-determined, so we are
  533. # going to try resolve it
  534. if c.call != nil:
  535. f = generateTypeInstance(c.c, c.bindings, c.call.info, f)
  536. else:
  537. f = nil
  538. if f == nil or f.isMetaType:
  539. # no luck resolving the type, so the inference fails
  540. return isBothMetaConvertible
  541. # Note that this typeRel call will save a's resolved type into c.bindings
  542. let reverseRel = typeRel(c, a, f)
  543. if reverseRel >= isGeneric:
  544. result = isInferred
  545. #inc c.genericMatches
  546. else:
  547. # Note that this typeRel call will save f's resolved type into c.bindings
  548. # if f is metatype.
  549. result = typeRel(c, f, a)
  550. if result <= isSubtype or inconsistentVarTypes(f, a):
  551. result = isNone
  552. #if result == isEqual:
  553. # inc c.exactMatches
  554. proc procTypeRel(c: var TCandidate, f, a: PType): TTypeRelation =
  555. case a.kind
  556. of tyProc:
  557. if sonsLen(f) != sonsLen(a): return
  558. result = isEqual # start with maximum; also correct for no
  559. # params at all
  560. template checkParam(f, a) =
  561. result = minRel(result, procParamTypeRel(c, f, a))
  562. if result == isNone: return
  563. # Note: We have to do unification for the parameters before the
  564. # return type!
  565. for i in 1 ..< f.sonsLen:
  566. checkParam(f.sons[i], a.sons[i])
  567. if f.sons[0] != nil:
  568. if a.sons[0] != nil:
  569. checkParam(f.sons[0], a.sons[0])
  570. else:
  571. return isNone
  572. elif a.sons[0] != nil:
  573. return isNone
  574. if tfNoSideEffect in f.flags and tfNoSideEffect notin a.flags:
  575. return isNone
  576. elif tfThread in f.flags and a.flags * {tfThread, tfNoSideEffect} == {} and
  577. optThreadAnalysis in c.c.config.globalOptions:
  578. # noSideEffect implies ``tfThread``!
  579. return isNone
  580. elif f.flags * {tfIterator} != a.flags * {tfIterator}:
  581. return isNone
  582. elif f.callConv != a.callConv:
  583. # valid to pass a 'nimcall' thingie to 'closure':
  584. if f.callConv == ccClosure and a.callConv == ccDefault:
  585. result = if result == isInferred: isInferredConvertible
  586. elif result == isBothMetaConvertible: isBothMetaConvertible
  587. else: isConvertible
  588. else:
  589. return isNone
  590. when useEffectSystem:
  591. if compatibleEffects(f, a) != efCompat: return isNone
  592. of tyNil:
  593. result = f.allowsNil
  594. else: discard
  595. proc typeRangeRel(f, a: PType): TTypeRelation {.noinline.} =
  596. template checkRange[T](a0, a1, f0, f1: T): TTypeRelation =
  597. if a0 == f0 and a1 == f1:
  598. isEqual
  599. elif a0 >= f0 and a1 <= f1:
  600. isConvertible
  601. elif a0 <= f1 and f0 <= a1:
  602. # X..Y and C..D overlap iff (X <= D and C <= Y)
  603. isConvertible
  604. else:
  605. isNone
  606. if f.isOrdinalType:
  607. checkRange(firstOrd(nil, a), lastOrd(nil, a), firstOrd(nil, f), lastOrd(nil, f))
  608. else:
  609. checkRange(firstFloat(a), lastFloat(a), firstFloat(f), lastFloat(f))
  610. proc matchUserTypeClass*(m: var TCandidate; ff, a: PType): PType =
  611. var
  612. c = m.c
  613. typeClass = ff.skipTypes({tyUserTypeClassInst})
  614. body = typeClass.n[3]
  615. matchedConceptContext: TMatchedConcept
  616. prevMatchedConcept = c.matchedConcept
  617. prevCandidateType = typeClass[0][0]
  618. if prevMatchedConcept != nil:
  619. matchedConceptContext.prev = prevMatchedConcept
  620. matchedConceptContext.depth = prevMatchedConcept.depth + 1
  621. if prevMatchedConcept.depth > 4:
  622. localError(m.c.graph.config, body.info, $body & " too nested for type matching")
  623. return nil
  624. openScope(c)
  625. matchedConceptContext.candidateType = a
  626. typeClass[0].sons[0] = a
  627. c.matchedConcept = addr(matchedConceptContext)
  628. defer:
  629. c.matchedConcept = prevMatchedConcept
  630. typeClass[0].sons[0] = prevCandidateType
  631. closeScope(c)
  632. var typeParams: seq[(PSym, PType)]
  633. if ff.kind == tyUserTypeClassInst:
  634. for i in 1 ..< (ff.len - 1):
  635. var
  636. typeParamName = ff.base.sons[i-1].sym.name
  637. typ = ff.sons[i]
  638. param: PSym
  639. alreadyBound = PType(idTableGet(m.bindings, typ))
  640. if alreadyBound != nil: typ = alreadyBound
  641. template paramSym(kind): untyped =
  642. newSym(kind, typeParamName, typeClass.sym, typeClass.sym.info, {})
  643. block addTypeParam:
  644. for prev in typeParams:
  645. if prev[1].id == typ.id:
  646. param = paramSym prev[0].kind
  647. param.typ = prev[0].typ
  648. break addTypeParam
  649. case typ.kind
  650. of tyStatic:
  651. param = paramSym skConst
  652. param.typ = typ.exactReplica
  653. if typ.n == nil:
  654. param.typ.flags.incl tfInferrableStatic
  655. else:
  656. param.ast = typ.n
  657. of tyUnknown:
  658. param = paramSym skVar
  659. param.typ = typ.exactReplica
  660. else:
  661. param = paramSym skType
  662. param.typ = if typ.isMetaType:
  663. c.newTypeWithSons(tyInferred, @[typ])
  664. else:
  665. makeTypeDesc(c, typ)
  666. typeParams.add((param, typ))
  667. addDecl(c, param)
  668. var
  669. oldWriteHook: type(m.c.config.writelnHook)
  670. diagnostics: seq[string]
  671. errorPrefix: string
  672. flags: TExprFlags = {}
  673. collectDiagnostics = m.diagnosticsEnabled or
  674. sfExplain in typeClass.sym.flags
  675. if collectDiagnostics:
  676. oldWriteHook = m.c.config.writelnHook
  677. # XXX: we can't write to m.diagnostics directly, because
  678. # Nim doesn't support capturing var params in closures
  679. diagnostics = @[]
  680. flags = {efExplain}
  681. m.c.config.writelnHook = proc (s: string) =
  682. if errorPrefix.len == 0: errorPrefix = typeClass.sym.name.s & ":"
  683. let msg = s.replace("Error:", errorPrefix)
  684. if oldWriteHook != nil: oldWriteHook msg
  685. diagnostics.add msg
  686. var checkedBody = c.semTryExpr(c, body.copyTree, flags)
  687. if collectDiagnostics:
  688. m.c.config.writelnHook = oldWriteHook
  689. for msg in diagnostics:
  690. m.diagnostics.add msg
  691. m.diagnosticsEnabled = true
  692. if checkedBody == nil: return nil
  693. # The inferrable type params have been identified during the semTryExpr above.
  694. # We need to put them in the current sigmatch's binding table in order for them
  695. # to be resolvable while matching the rest of the parameters
  696. for p in typeParams:
  697. put(m, p[1], p[0].typ)
  698. if ff.kind == tyUserTypeClassInst:
  699. result = generateTypeInstance(c, m.bindings, typeClass.sym.info, ff)
  700. else:
  701. result = copyType(ff, ff.owner, true)
  702. result.n = checkedBody
  703. proc shouldSkipDistinct(m: TCandidate; rules: PNode, callIdent: PIdent): bool =
  704. # XXX This is bad as 'considerQuotedIdent' can produce an error!
  705. if rules.kind == nkWith:
  706. for r in rules:
  707. if considerQuotedIdent(m.c, r) == callIdent: return true
  708. return false
  709. else:
  710. for r in rules:
  711. if considerQuotedIdent(m.c, r) == callIdent: return false
  712. return true
  713. proc maybeSkipDistinct(m: TCandidate; t: PType, callee: PSym): PType =
  714. if t != nil and t.kind == tyDistinct and t.n != nil and
  715. shouldSkipDistinct(m, t.n, callee.name):
  716. result = t.base
  717. else:
  718. result = t
  719. proc tryResolvingStaticExpr(c: var TCandidate, n: PNode,
  720. allowUnresolved = false): PNode =
  721. # Consider this example:
  722. # type Value[N: static[int]] = object
  723. # proc foo[N](a: Value[N], r: range[0..(N-1)])
  724. # Here, N-1 will be initially nkStaticExpr that can be evaluated only after
  725. # N is bound to a concrete value during the matching of the first param.
  726. # This proc is used to evaluate such static expressions.
  727. let instantiated = replaceTypesInBody(c.c, c.bindings, n, nil,
  728. allowMetaTypes = allowUnresolved)
  729. result = c.c.semExpr(c.c, instantiated)
  730. proc inferStaticParam*(c: var TCandidate, lhs: PNode, rhs: BiggestInt): bool =
  731. # This is a simple integer arithimetic equation solver,
  732. # capable of deriving the value of a static parameter in
  733. # expressions such as (N + 5) / 2 = rhs
  734. #
  735. # Preconditions:
  736. #
  737. # * The input of this proc must be semantized
  738. # - all templates should be expanded
  739. # - aby constant folding possible should already be performed
  740. #
  741. # * There must be exactly one unresolved static parameter
  742. #
  743. # Result:
  744. #
  745. # The proc will return true if the static types was successfully
  746. # inferred. The result will be bound to the original static type
  747. # in the TCandidate.
  748. #
  749. if lhs.kind in nkCallKinds and lhs[0].kind == nkSym:
  750. case lhs[0].sym.magic
  751. of mUnaryLt:
  752. return inferStaticParam(c, lhs[1], rhs + 1)
  753. of mAddI, mAddU, mInc, mSucc:
  754. if lhs[1].kind == nkIntLit:
  755. return inferStaticParam(c, lhs[2], rhs - lhs[1].intVal)
  756. elif lhs[2].kind == nkIntLit:
  757. return inferStaticParam(c, lhs[1], rhs - lhs[2].intVal)
  758. of mDec, mSubI, mSubU, mPred:
  759. if lhs[1].kind == nkIntLit:
  760. return inferStaticParam(c, lhs[2], lhs[1].intVal - rhs)
  761. elif lhs[2].kind == nkIntLit:
  762. return inferStaticParam(c, lhs[1], rhs + lhs[2].intVal)
  763. of mMulI, mMulU:
  764. if lhs[1].kind == nkIntLit:
  765. if rhs mod lhs[1].intVal == 0:
  766. return inferStaticParam(c, lhs[2], rhs div lhs[1].intVal)
  767. elif lhs[2].kind == nkIntLit:
  768. if rhs mod lhs[2].intVal == 0:
  769. return inferStaticParam(c, lhs[1], rhs div lhs[2].intVal)
  770. of mDivI, mDivU:
  771. if lhs[1].kind == nkIntLit:
  772. if lhs[1].intVal mod rhs == 0:
  773. return inferStaticParam(c, lhs[2], lhs[1].intVal div rhs)
  774. elif lhs[2].kind == nkIntLit:
  775. return inferStaticParam(c, lhs[1], lhs[2].intVal * rhs)
  776. of mShlI:
  777. if lhs[2].kind == nkIntLit:
  778. return inferStaticParam(c, lhs[1], rhs shr lhs[2].intVal)
  779. of mShrI:
  780. if lhs[2].kind == nkIntLit:
  781. return inferStaticParam(c, lhs[1], rhs shl lhs[2].intVal)
  782. of mAshrI:
  783. if lhs[2].kind == nkIntLit:
  784. return inferStaticParam(c, lhs[1], ashr(rhs, lhs[2].intVal))
  785. of mUnaryMinusI:
  786. return inferStaticParam(c, lhs[1], -rhs)
  787. of mUnaryPlusI, mToInt, mToBiggestInt:
  788. return inferStaticParam(c, lhs[1], rhs)
  789. else: discard
  790. elif lhs.kind == nkSym and lhs.typ.kind == tyStatic and lhs.typ.n == nil:
  791. var inferred = newTypeWithSons(c.c, tyStatic, lhs.typ.sons)
  792. inferred.n = newIntNode(nkIntLit, rhs)
  793. put(c, lhs.typ, inferred)
  794. if c.c.matchedConcept != nil:
  795. # inside concepts, binding is currently done with
  796. # direct mutation of the involved types:
  797. lhs.typ.n = inferred.n
  798. return true
  799. return false
  800. proc failureToInferStaticParam(conf: ConfigRef; n: PNode) =
  801. let staticParam = n.findUnresolvedStatic
  802. let name = if staticParam != nil: staticParam.sym.name.s
  803. else: "unknown"
  804. localError(conf, n.info, "cannot infer the value of the static param '" & name & "'")
  805. proc inferStaticsInRange(c: var TCandidate,
  806. inferred, concrete: PType): TTypeRelation =
  807. let lowerBound = tryResolvingStaticExpr(c, inferred.n[0],
  808. allowUnresolved = true)
  809. let upperBound = tryResolvingStaticExpr(c, inferred.n[1],
  810. allowUnresolved = true)
  811. template doInferStatic(e: PNode, r: BiggestInt) =
  812. var exp = e
  813. var rhs = r
  814. if inferStaticParam(c, exp, rhs):
  815. return isGeneric
  816. else:
  817. failureToInferStaticParam(c.c.config, exp)
  818. if lowerBound.kind == nkIntLit:
  819. if upperBound.kind == nkIntLit:
  820. if lengthOrd(c.c.config, concrete) == upperBound.intVal - lowerBound.intVal + 1:
  821. return isGeneric
  822. else:
  823. return isNone
  824. doInferStatic(upperBound, lengthOrd(c.c.config, concrete) + lowerBound.intVal - 1)
  825. elif upperBound.kind == nkIntLit:
  826. doInferStatic(lowerBound, upperBound.intVal + 1 - lengthOrd(c.c.config, concrete))
  827. template subtypeCheck() =
  828. if result <= isSubrange and f.lastSon.skipTypes(abstractInst).kind in {
  829. tyRef, tyPtr, tyVar, tyLent, tyOwned}:
  830. result = isNone
  831. proc isCovariantPtr(c: var TCandidate, f, a: PType): bool =
  832. # this proc is always called for a pair of matching types
  833. assert f.kind == a.kind
  834. template baseTypesCheck(lhs, rhs: PType): bool =
  835. lhs.kind notin {tyPtr, tyRef, tyVar, tyLent, tyOwned} and
  836. typeRel(c, lhs, rhs, {trNoCovariance}) == isSubtype
  837. case f.kind
  838. of tyRef, tyPtr, tyOwned:
  839. return baseTypesCheck(f.base, a.base)
  840. of tyGenericInst:
  841. let body = f.base
  842. return body == a.base and
  843. a.sonsLen == 3 and
  844. tfWeakCovariant notin body.sons[0].flags and
  845. baseTypesCheck(f.sons[1], a.sons[1])
  846. else:
  847. return false
  848. when false:
  849. proc maxNumericType(prev, candidate: PType): PType =
  850. let c = candidate.skipTypes({tyRange})
  851. template greater(s) =
  852. if c.kind in s: result = c
  853. case prev.kind
  854. of tyInt: greater({tyInt64})
  855. of tyInt8: greater({tyInt, tyInt16, tyInt32, tyInt64})
  856. of tyInt16: greater({tyInt, tyInt32, tyInt64})
  857. of tyInt32: greater({tyInt64})
  858. of tyUInt: greater({tyUInt64})
  859. of tyUInt8: greater({tyUInt, tyUInt16, tyUInt32, tyUInt64})
  860. of tyUInt16: greater({tyUInt, tyUInt32, tyUInt64})
  861. of tyUInt32: greater({tyUInt64})
  862. of tyFloat32: greater({tyFloat64, tyFloat128})
  863. of tyFloat64: greater({tyFloat128})
  864. else: discard
  865. template skipOwned(a) =
  866. if a.kind == tyOwned: a = a.skipTypes({tyOwned, tyGenericInst})
  867. proc typeRel(c: var TCandidate, f, aOrig: PType,
  868. flags: TTypeRelFlags = {}): TTypeRelation =
  869. # typeRel can be used to establish various relationships between types:
  870. #
  871. # 1) When used with concrete types, it will check for type equivalence
  872. # or a subtype relationship.
  873. #
  874. # 2) When used with a concrete type against a type class (such as generic
  875. # signature of a proc), it will check whether the concrete type is a member
  876. # of the designated type class.
  877. #
  878. # 3) When used with two type classes, it will check whether the types
  879. # matching the first type class are a strict subset of the types matching
  880. # the other. This allows us to compare the signatures of generic procs in
  881. # order to give preferrence to the most specific one:
  882. #
  883. # seq[seq[any]] is a strict subset of seq[any] and hence more specific.
  884. result = isNone
  885. assert(f != nil)
  886. if f.kind == tyUntyped:
  887. if aOrig != nil: put(c, f, aOrig)
  888. return isGeneric
  889. assert(aOrig != nil)
  890. var
  891. useTypeLoweringRuleInTypeClass = c.c.matchedConcept != nil and
  892. not c.isNoCall and
  893. f.kind != tyTypeDesc and
  894. tfExplicit notin aOrig.flags and
  895. tfConceptMatchedTypeSym notin aOrig.flags
  896. aOrig = if useTypeLoweringRuleInTypeClass:
  897. aOrig.skipTypes({tyTypeDesc})
  898. else:
  899. aOrig
  900. if aOrig.kind == tyInferred:
  901. let prev = aOrig.previouslyInferred
  902. if prev != nil:
  903. return typeRel(c, f, prev)
  904. else:
  905. var candidate = f
  906. case f.kind
  907. of tyGenericParam:
  908. var prev = PType(idTableGet(c.bindings, f))
  909. if prev != nil: candidate = prev
  910. of tyFromExpr:
  911. let computedType = tryResolvingStaticExpr(c, f.n).typ
  912. case computedType.kind
  913. of tyTypeDesc:
  914. candidate = computedType.base
  915. of tyStatic:
  916. candidate = computedType
  917. else:
  918. # XXX What is this non-sense? Error reporting in signature matching?
  919. discard "localError(f.n.info, errTypeExpected)"
  920. else:
  921. discard
  922. result = typeRel(c, aOrig.base, candidate)
  923. if result != isNone:
  924. c.inferredTypes.add aOrig
  925. aOrig.sons.add candidate
  926. result = isEqual
  927. return
  928. template doBind: bool = trDontBind notin flags
  929. # var, sink and static arguments match regular modifier-free types
  930. var a = maybeSkipDistinct(c, aOrig.skipTypes({tyStatic, tyVar, tyLent, tySink}), c.calleeSym)
  931. # XXX: Theoretically, maybeSkipDistinct could be called before we even
  932. # start the param matching process. This could be done in `prepareOperand`
  933. # for example, but unfortunately `prepareOperand` is not called in certain
  934. # situation when nkDotExpr are rotated to nkDotCalls
  935. if aOrig.kind in {tyAlias, tySink}:
  936. return typeRel(c, f, lastSon(aOrig))
  937. if a.kind == tyGenericInst and
  938. skipTypes(f, {tyVar, tyLent, tySink}).kind notin {
  939. tyGenericBody, tyGenericInvocation,
  940. tyGenericInst, tyGenericParam} + tyTypeClasses:
  941. return typeRel(c, f, lastSon(a))
  942. if a.isResolvedUserTypeClass:
  943. return typeRel(c, f, a.lastSon)
  944. template bindingRet(res) =
  945. if doBind:
  946. let bound = aOrig.skipTypes({tyRange}).skipIntLit
  947. put(c, f, bound)
  948. return res
  949. template considerPreviousT(body: untyped) =
  950. var prev = PType(idTableGet(c.bindings, f))
  951. if prev == nil: body
  952. else: return typeRel(c, prev, a)
  953. case a.kind
  954. of tyOr:
  955. # XXX: deal with the current dual meaning of tyGenericParam
  956. c.typedescMatched = true
  957. # seq[int|string] vs seq[number]
  958. # both int and string must match against number
  959. # but ensure that '[T: A|A]' matches as good as '[T: A]' (bug #2219):
  960. result = isGeneric
  961. for branch in a.sons:
  962. let x = typeRel(c, f, branch, flags + {trDontBind})
  963. if x == isNone: return isNone
  964. if x < result: result = x
  965. return
  966. of tyAnd:
  967. # XXX: deal with the current dual meaning of tyGenericParam
  968. c.typedescMatched = true
  969. # seq[Sortable and Iterable] vs seq[Sortable]
  970. # only one match is enough
  971. for branch in a.sons:
  972. let x = typeRel(c, f, branch, flags + {trDontBind})
  973. if x != isNone:
  974. return if x >= isGeneric: isGeneric else: x
  975. return isNone
  976. of tyNot:
  977. case f.kind
  978. of tyNot:
  979. # seq[!int] vs seq[!number]
  980. # seq[float] matches the first, but not the second
  981. # we must turn the problem around:
  982. # is number a subset of int?
  983. return typeRel(c, a.lastSon, f.lastSon)
  984. else:
  985. # negative type classes are essentially infinite,
  986. # so only the `any` type class is their superset
  987. return if f.kind == tyAnything: isGeneric
  988. else: isNone
  989. of tyAnything:
  990. if f.kind == tyAnything: return isGeneric
  991. else: return isNone
  992. of tyUserTypeClass, tyUserTypeClassInst:
  993. if c.c.matchedConcept != nil and c.c.matchedConcept.depth <= 4:
  994. # consider this: 'var g: Node' *within* a concept where 'Node'
  995. # is a concept too (tgraph)
  996. inc c.c.matchedConcept.depth
  997. let x = typeRel(c, a, f, flags + {trDontBind})
  998. if x >= isGeneric:
  999. return isGeneric
  1000. else: discard
  1001. case f.kind
  1002. of tyEnum:
  1003. if a.kind == f.kind and sameEnumTypes(f, a): result = isEqual
  1004. elif sameEnumTypes(f, skipTypes(a, {tyRange})): result = isSubtype
  1005. of tyBool, tyChar:
  1006. if a.kind == f.kind: result = isEqual
  1007. elif skipTypes(a, {tyRange}).kind == f.kind: result = isSubtype
  1008. of tyRange:
  1009. if a.kind == f.kind:
  1010. if f.base.kind == tyNone: return isGeneric
  1011. result = typeRel(c, base(f), base(a))
  1012. # bugfix: accept integer conversions here
  1013. #if result < isGeneric: result = isNone
  1014. if result notin {isNone, isGeneric}:
  1015. # resolve any late-bound static expressions
  1016. # that may appear in the range:
  1017. for i in 0..1:
  1018. if f.n[i].kind == nkStaticExpr:
  1019. f.n.sons[i] = tryResolvingStaticExpr(c, f.n[i])
  1020. result = typeRangeRel(f, a)
  1021. else:
  1022. if skipTypes(f, {tyRange}).kind == a.kind:
  1023. result = isIntConv
  1024. elif isConvertibleToRange(skipTypes(f, {tyRange}), a):
  1025. result = isConvertible # a convertible to f
  1026. of tyInt: result = handleRange(f, a, tyInt8, tyInt32)
  1027. of tyInt8: result = handleRange(f, a, tyInt8, tyInt8)
  1028. of tyInt16: result = handleRange(f, a, tyInt8, tyInt16)
  1029. of tyInt32: result = handleRange(f, a, tyInt8, tyInt32)
  1030. of tyInt64: result = handleRange(f, a, tyInt, tyInt64)
  1031. of tyUInt: result = handleRange(f, a, tyUInt8, tyUInt32)
  1032. of tyUInt8: result = handleRange(f, a, tyUInt8, tyUInt8)
  1033. of tyUInt16: result = handleRange(f, a, tyUInt8, tyUInt16)
  1034. of tyUInt32: result = handleRange(f, a, tyUInt8, tyUInt32)
  1035. of tyUInt64: result = handleRange(f, a, tyUInt, tyUInt64)
  1036. of tyFloat: result = handleFloatRange(f, a)
  1037. of tyFloat32: result = handleFloatRange(f, a)
  1038. of tyFloat64: result = handleFloatRange(f, a)
  1039. of tyFloat128: result = handleFloatRange(f, a)
  1040. of tyVar, tyLent:
  1041. if aOrig.kind == f.kind: result = typeRel(c, f.base, aOrig.base)
  1042. else: result = typeRel(c, f.base, aOrig, flags + {trNoCovariance})
  1043. subtypeCheck()
  1044. of tyArray:
  1045. case a.kind
  1046. of tyArray:
  1047. var fRange = f.sons[0]
  1048. var aRange = a.sons[0]
  1049. if fRange.kind == tyGenericParam:
  1050. var prev = PType(idTableGet(c.bindings, fRange))
  1051. if prev == nil:
  1052. put(c, fRange, a.sons[0])
  1053. fRange = a
  1054. else:
  1055. fRange = prev
  1056. let ff = f.sons[1].skipTypes({tyTypeDesc})
  1057. # This typeDesc rule is wrong, see bug #7331
  1058. let aa = a.sons[1] #.skipTypes({tyTypeDesc})
  1059. if f.sons[0].kind != tyGenericParam and aa.kind == tyEmpty:
  1060. result = isGeneric
  1061. else:
  1062. result = typeRel(c, ff, aa)
  1063. if result < isGeneric:
  1064. if nimEnableCovariance and
  1065. trNoCovariance notin flags and
  1066. ff.kind == aa.kind and
  1067. isCovariantPtr(c, ff, aa):
  1068. result = isSubtype
  1069. else:
  1070. return isNone
  1071. if fRange.rangeHasUnresolvedStatic:
  1072. return inferStaticsInRange(c, fRange, a)
  1073. elif c.c.matchedConcept != nil and aRange.rangeHasUnresolvedStatic:
  1074. return inferStaticsInRange(c, aRange, f)
  1075. else:
  1076. if lengthOrd(c.c.config, fRange) != lengthOrd(c.c.config, aRange):
  1077. result = isNone
  1078. else: discard
  1079. of tyUncheckedArray:
  1080. if a.kind == tyUncheckedArray:
  1081. result = typeRel(c, base(f), base(a))
  1082. if result < isGeneric: result = isNone
  1083. else: discard
  1084. of tyOpenArray, tyVarargs:
  1085. # varargs[expr] is special too but handled earlier. So we only need to
  1086. # handle varargs[stmt] which is the same as varargs[typed]:
  1087. if f.kind == tyVarargs:
  1088. if tfVarargs in a.flags:
  1089. return typeRel(c, f.base, a.lastSon)
  1090. if f.sons[0].kind == tyTyped: return
  1091. template matchArrayOrSeq(aBase: PType) =
  1092. let ff = f.base
  1093. let aa = aBase
  1094. let baseRel = typeRel(c, ff, aa)
  1095. if baseRel >= isGeneric:
  1096. result = isConvertible
  1097. elif nimEnableCovariance and
  1098. trNoCovariance notin flags and
  1099. ff.kind == aa.kind and
  1100. isCovariantPtr(c, ff, aa):
  1101. result = isConvertible
  1102. case a.kind
  1103. of tyOpenArray, tyVarargs:
  1104. result = typeRel(c, base(f), base(a))
  1105. if result < isGeneric: result = isNone
  1106. of tyArray:
  1107. if (f.sons[0].kind != tyGenericParam) and (a.sons[1].kind == tyEmpty):
  1108. return isSubtype
  1109. matchArrayOrSeq(a.sons[1])
  1110. of tySequence:
  1111. if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty):
  1112. return isConvertible
  1113. matchArrayOrSeq(a.sons[0])
  1114. of tyString:
  1115. if f.kind == tyOpenArray:
  1116. if f.sons[0].kind == tyChar:
  1117. result = isConvertible
  1118. elif f.sons[0].kind == tyGenericParam and a.len > 0 and
  1119. typeRel(c, base(f), base(a)) >= isGeneric:
  1120. result = isConvertible
  1121. else: discard
  1122. of tySequence:
  1123. case a.kind
  1124. of tySequence:
  1125. if (f.sons[0].kind != tyGenericParam) and (a.sons[0].kind == tyEmpty):
  1126. result = isSubtype
  1127. else:
  1128. let ff = f.sons[0]
  1129. let aa = a.sons[0]
  1130. result = typeRel(c, ff, aa)
  1131. if result < isGeneric:
  1132. if nimEnableCovariance and
  1133. trNoCovariance notin flags and
  1134. ff.kind == aa.kind and
  1135. isCovariantPtr(c, ff, aa):
  1136. result = isSubtype
  1137. else:
  1138. result = isNone
  1139. elif tfNotNil in f.flags and tfNotNil notin a.flags:
  1140. result = isNilConversion
  1141. of tyNil: result = allowsNilDeprecated(c, f)
  1142. else: discard
  1143. of tyOrdinal:
  1144. if isOrdinalType(a):
  1145. var x = if a.kind == tyOrdinal: a.sons[0] else: a
  1146. if f.sons[0].kind == tyNone:
  1147. result = isGeneric
  1148. else:
  1149. result = typeRel(c, f.sons[0], x)
  1150. if result < isGeneric: result = isNone
  1151. elif a.kind == tyGenericParam:
  1152. result = isGeneric
  1153. of tyForward:
  1154. #internalError("forward type in typeRel()")
  1155. result = isNone
  1156. of tyNil:
  1157. skipOwned(a)
  1158. if a.kind == f.kind: result = isEqual
  1159. of tyTuple:
  1160. if a.kind == tyTuple: result = recordRel(c, f, a)
  1161. of tyObject:
  1162. if a.kind == tyObject:
  1163. if sameObjectTypes(f, a):
  1164. result = isEqual
  1165. # elif tfHasMeta in f.flags: result = recordRel(c, f, a)
  1166. else:
  1167. var depth = isObjectSubtype(c, a, f, nil)
  1168. if depth > 0:
  1169. inc(c.inheritancePenalty, depth)
  1170. result = isSubtype
  1171. of tyDistinct:
  1172. a = a.skipTypes({tyOwned, tyGenericInst, tyRange})
  1173. if a.kind == tyDistinct:
  1174. if sameDistinctTypes(f, a): result = isEqual
  1175. #elif f.base.kind == tyAnything: result = isGeneric # issue 4435
  1176. elif c.coerceDistincts: result = typeRel(c, f.base, a)
  1177. elif a.kind == tyNil and f.base.kind in NilableTypes:
  1178. result = f.allowsNil # XXX remove this typing rule, it is not in the spec
  1179. elif c.coerceDistincts: result = typeRel(c, f.base, a)
  1180. of tySet:
  1181. if a.kind == tySet:
  1182. if f.sons[0].kind != tyGenericParam and a.sons[0].kind == tyEmpty:
  1183. result = isSubtype
  1184. else:
  1185. result = typeRel(c, f.sons[0], a.sons[0])
  1186. if result <= isConvertible:
  1187. result = isNone # BUGFIX!
  1188. of tyPtr, tyRef:
  1189. skipOwned(a)
  1190. if a.kind == f.kind:
  1191. # ptr[R, T] can be passed to ptr[T], but not the other way round:
  1192. if a.len < f.len: return isNone
  1193. for i in 0..f.len-2:
  1194. if typeRel(c, f.sons[i], a.sons[i]) == isNone: return isNone
  1195. result = typeRel(c, f.lastSon, a.lastSon, flags + {trNoCovariance})
  1196. subtypeCheck()
  1197. if result <= isIntConv: result = isNone
  1198. elif tfNotNil in f.flags and tfNotNil notin a.flags:
  1199. result = isNilConversion
  1200. elif a.kind == tyNil: result = f.allowsNil
  1201. else: discard
  1202. of tyProc:
  1203. skipOwned(a)
  1204. result = procTypeRel(c, f, a)
  1205. if result != isNone and tfNotNil in f.flags and tfNotNil notin a.flags:
  1206. result = isNilConversion
  1207. of tyOwned:
  1208. case a.kind
  1209. of tyOwned:
  1210. result = typeRel(c, lastSon(f), lastSon(a))
  1211. of tyNil: result = f.allowsNil
  1212. else: discard
  1213. of tyPointer:
  1214. skipOwned(a)
  1215. case a.kind
  1216. of tyPointer:
  1217. if tfNotNil in f.flags and tfNotNil notin a.flags:
  1218. result = isNilConversion
  1219. else:
  1220. result = isEqual
  1221. of tyNil: result = f.allowsNil
  1222. of tyProc:
  1223. if a.callConv != ccClosure: result = isConvertible
  1224. of tyPtr:
  1225. # 'pointer' is NOT compatible to regionized pointers
  1226. # so 'dealloc(regionPtr)' fails:
  1227. if a.len == 1: result = isConvertible
  1228. of tyCString: result = isConvertible
  1229. else: discard
  1230. of tyString:
  1231. case a.kind
  1232. of tyString:
  1233. if tfNotNil in f.flags and tfNotNil notin a.flags:
  1234. result = isNilConversion
  1235. else:
  1236. result = isEqual
  1237. of tyNil: result = allowsNilDeprecated(c, f)
  1238. else: discard
  1239. of tyCString:
  1240. # conversion from string to cstring is automatic:
  1241. case a.kind
  1242. of tyCString:
  1243. if tfNotNil in f.flags and tfNotNil notin a.flags:
  1244. result = isNilConversion
  1245. else:
  1246. result = isEqual
  1247. of tyNil: result = f.allowsNil
  1248. of tyString: result = isConvertible
  1249. of tyPtr:
  1250. # ptr[Tag, char] is not convertible to 'cstring' for now:
  1251. if a.len == 1:
  1252. let pointsTo = a.sons[0].skipTypes(abstractInst)
  1253. if pointsTo.kind == tyChar: result = isConvertible
  1254. elif pointsTo.kind == tyUncheckedArray and pointsTo.sons[0].kind == tyChar:
  1255. result = isConvertible
  1256. elif pointsTo.kind == tyArray and firstOrd(nil, pointsTo.sons[0]) == 0 and
  1257. skipTypes(pointsTo.sons[0], {tyRange}).kind in {tyInt..tyInt64} and
  1258. pointsTo.sons[1].kind == tyChar:
  1259. result = isConvertible
  1260. else: discard
  1261. of tyEmpty, tyVoid:
  1262. if a.kind == f.kind: result = isEqual
  1263. of tyAlias, tySink:
  1264. result = typeRel(c, lastSon(f), a)
  1265. of tyGenericInst:
  1266. var prev = PType(idTableGet(c.bindings, f))
  1267. let origF = f
  1268. var f = if prev == nil: f else: prev
  1269. let roota = a.skipGenericAlias
  1270. let rootf = f.skipGenericAlias
  1271. var m = c
  1272. if a.kind == tyGenericInst:
  1273. if roota.base == rootf.base:
  1274. let nextFlags = flags + {trNoCovariance}
  1275. var hasCovariance = false
  1276. # YYYY
  1277. result = isEqual
  1278. for i in 1 .. rootf.sonsLen-2:
  1279. let ff = rootf.sons[i]
  1280. let aa = roota.sons[i]
  1281. let res = typeRel(c, ff, aa, nextFlags)
  1282. if res != isEqual: result = isGeneric
  1283. if res notin {isEqual, isGeneric}:
  1284. if trNoCovariance notin flags and ff.kind == aa.kind:
  1285. let paramFlags = rootf.base.sons[i-1].flags
  1286. hasCovariance =
  1287. if tfCovariant in paramFlags:
  1288. if tfWeakCovariant in paramFlags:
  1289. isCovariantPtr(c, ff, aa)
  1290. else:
  1291. ff.kind notin {tyRef, tyPtr} and res == isSubtype
  1292. else:
  1293. tfContravariant in paramFlags and
  1294. typeRel(c, aa, ff) == isSubtype
  1295. if hasCovariance:
  1296. continue
  1297. return isNone
  1298. if prev == nil: put(c, f, a)
  1299. else:
  1300. let fKind = rootf.lastSon.kind
  1301. if fKind in {tyAnd, tyOr}:
  1302. result = typeRel(c, lastSon(f), a)
  1303. if result != isNone: put(c, f, a)
  1304. return
  1305. var aAsObject = roota.lastSon
  1306. if fKind in {tyRef, tyPtr}:
  1307. if aAsObject.kind == tyObject:
  1308. # bug #7600, tyObject cannot be passed
  1309. # as argument to tyRef/tyPtr
  1310. return isNone
  1311. elif aAsObject.kind == fKind:
  1312. aAsObject = aAsObject.base
  1313. if aAsObject.kind == tyObject:
  1314. let baseType = aAsObject.base
  1315. if baseType != nil:
  1316. c.inheritancePenalty += 1
  1317. let ret = typeRel(c, f, baseType)
  1318. return if ret == isEqual: isSubtype else: ret
  1319. result = isNone
  1320. else:
  1321. assert lastSon(origF) != nil
  1322. result = typeRel(c, lastSon(origF), a)
  1323. if result != isNone and a.kind != tyNil:
  1324. put(c, f, a)
  1325. of tyGenericBody:
  1326. considerPreviousT:
  1327. if a == f or a.kind == tyGenericInst and a.sons[0] == f:
  1328. bindingRet isGeneric
  1329. let ff = lastSon(f)
  1330. if ff != nil:
  1331. result = typeRel(c, ff, a)
  1332. of tyGenericInvocation:
  1333. var x = a.skipGenericAlias
  1334. var preventHack = false
  1335. if x.kind == tyOwned and f.sons[0].kind != tyOwned:
  1336. preventHack = true
  1337. x = x.lastSon
  1338. # XXX: This is very hacky. It should be moved back into liftTypeParam
  1339. if x.kind in {tyGenericInst, tyArray} and
  1340. c.calleeSym != nil and
  1341. c.calleeSym.kind in {skProc, skFunc} and c.call != nil and not preventHack:
  1342. let inst = prepareMetatypeForSigmatch(c.c, c.bindings, c.call.info, f)
  1343. #echo "inferred ", typeToString(inst), " for ", f
  1344. return typeRel(c, inst, a)
  1345. var depth = 0
  1346. if x.kind == tyGenericInvocation or f.sons[0].kind != tyGenericBody:
  1347. #InternalError("typeRel: tyGenericInvocation -> tyGenericInvocation")
  1348. # simply no match for now:
  1349. discard
  1350. elif x.kind == tyGenericInst and f.sons[0] == x.sons[0] and
  1351. sonsLen(x) - 1 == sonsLen(f):
  1352. for i in 1 ..< sonsLen(f):
  1353. if x.sons[i].kind == tyGenericParam:
  1354. internalError(c.c.graph.config, "wrong instantiated type!")
  1355. elif typeRel(c, f.sons[i], x.sons[i]) <= isSubtype:
  1356. # Workaround for regression #4589
  1357. if f.sons[i].kind != tyTypeDesc: return
  1358. result = isGeneric
  1359. elif x.kind == tyGenericInst and isGenericSubtype(c, x, f, depth, f) and
  1360. (sonsLen(x) - 1 == sonsLen(f)):
  1361. # do not recurse here in order to not K bind twice for this code:
  1362. #
  1363. # type
  1364. # BaseFruit[T] = object of RootObj
  1365. # Banana[T] = object of BaseFruit[uint32] # Concrete type here, not T!
  1366. # proc setColor[K](self: var BaseFruit[K])
  1367. # var x: Banana[float64]
  1368. # x.setColor()
  1369. c.inheritancePenalty += depth
  1370. result = isGeneric
  1371. else:
  1372. let genericBody = f.sons[0]
  1373. var askip = skippedNone
  1374. var fskip = skippedNone
  1375. let aobj = x.skipToObject(askip)
  1376. let fobj = genericBody.lastSon.skipToObject(fskip)
  1377. var depth = -1
  1378. if fobj != nil and aobj != nil and askip == fskip:
  1379. depth = isObjectSubtype(c, aobj, fobj, f)
  1380. result = typeRel(c, genericBody, x)
  1381. if result != isNone:
  1382. # see tests/generics/tgeneric3.nim for an example that triggers this
  1383. # piece of code:
  1384. #
  1385. # proc internalFind[T,D](n: PNode[T,D], key: T): ref TItem[T,D]
  1386. # proc internalPut[T,D](ANode: ref TNode[T,D], Akey: T, Avalue: D,
  1387. # Oldvalue: var D): ref TNode[T,D]
  1388. # var root = internalPut[int, int](nil, 312, 312, oldvalue)
  1389. # var it1 = internalFind(root, 312) # cannot instantiate: 'D'
  1390. #
  1391. # we steal the generic parameters from the tyGenericBody:
  1392. for i in 1 ..< sonsLen(f):
  1393. let x = PType(idTableGet(c.bindings, genericBody.sons[i-1]))
  1394. if x == nil:
  1395. discard "maybe fine (for eg. a==tyNil)"
  1396. elif x.kind in {tyGenericInvocation, tyGenericParam}:
  1397. internalError(c.c.graph.config, "wrong instantiated type!")
  1398. else:
  1399. let key = f.sons[i]
  1400. let old = PType(idTableGet(c.bindings, key))
  1401. if old == nil:
  1402. put(c, key, x)
  1403. elif typeRel(c, old, x, flags + {trDontBind}) == isNone:
  1404. return isNone
  1405. if result == isNone:
  1406. # Here object inheriting from generic/specialized generic object
  1407. # crossing path with metatypes/aliases, so we need to separate them
  1408. # by checking sym.id
  1409. let genericSubtype = isGenericSubtype(c, x, f, depth, f)
  1410. if not (genericSubtype and aobj.sym.id != fobj.sym.id) and aOrig.kind != tyGenericBody:
  1411. depth = -1
  1412. if depth >= 0:
  1413. c.inheritancePenalty += depth
  1414. # bug #4863: We still need to bind generic alias crap, so
  1415. # we cannot return immediately:
  1416. result = if depth == 0: isGeneric else: isSubtype
  1417. of tyAnd:
  1418. considerPreviousT:
  1419. result = isEqual
  1420. for branch in f.sons:
  1421. let x = typeRel(c, branch, aOrig)
  1422. if x < isSubtype: return isNone
  1423. # 'and' implies minimum matching result:
  1424. if x < result: result = x
  1425. if result > isGeneric: result = isGeneric
  1426. bindingRet result
  1427. of tyOr:
  1428. considerPreviousT:
  1429. result = isNone
  1430. let oldInheritancePenalty = c.inheritancePenalty
  1431. var maxInheritance = 0
  1432. for branch in f.sons:
  1433. c.inheritancePenalty = 0
  1434. let x = typeRel(c, branch, aOrig)
  1435. maxInheritance = max(maxInheritance, c.inheritancePenalty)
  1436. # 'or' implies maximum matching result:
  1437. if x > result: result = x
  1438. if result >= isSubtype:
  1439. if result > isGeneric: result = isGeneric
  1440. bindingRet result
  1441. else:
  1442. result = isNone
  1443. c.inheritancePenalty = oldInheritancePenalty + maxInheritance
  1444. of tyNot:
  1445. considerPreviousT:
  1446. for branch in f.sons:
  1447. if typeRel(c, branch, aOrig) != isNone:
  1448. return isNone
  1449. bindingRet isGeneric
  1450. of tyAnything:
  1451. considerPreviousT:
  1452. var concrete = concreteType(c, a)
  1453. if concrete != nil and doBind:
  1454. put(c, f, concrete)
  1455. return isGeneric
  1456. of tyBuiltInTypeClass:
  1457. considerPreviousT:
  1458. let targetKind = f.sons[0].kind
  1459. let effectiveArgType = a.skipTypes({tyRange, tyGenericInst,
  1460. tyBuiltInTypeClass, tyAlias, tySink, tyOwned})
  1461. let typeClassMatches = targetKind == effectiveArgType.kind and
  1462. not effectiveArgType.isEmptyContainer
  1463. if typeClassMatches or
  1464. (targetKind in {tyProc, tyPointer} and effectiveArgType.kind == tyNil):
  1465. put(c, f, a)
  1466. return isGeneric
  1467. else:
  1468. return isNone
  1469. of tyUserTypeClassInst, tyUserTypeClass:
  1470. if f.isResolvedUserTypeClass:
  1471. result = typeRel(c, f.lastSon, a)
  1472. else:
  1473. considerPreviousT:
  1474. if aOrig == f: return isEqual
  1475. var matched = matchUserTypeClass(c, f, aOrig)
  1476. if matched != nil:
  1477. bindConcreteTypeToUserTypeClass(matched, a)
  1478. if doBind: put(c, f, matched)
  1479. result = isGeneric
  1480. else:
  1481. result = isNone
  1482. of tyCompositeTypeClass:
  1483. considerPreviousT:
  1484. let roota = a.skipGenericAlias
  1485. let rootf = f.lastSon.skipGenericAlias
  1486. if a.kind == tyGenericInst and roota.base == rootf.base:
  1487. for i in 1 .. rootf.sonsLen-2:
  1488. let ff = rootf.sons[i]
  1489. let aa = roota.sons[i]
  1490. result = typeRel(c, ff, aa)
  1491. if result == isNone: return
  1492. if ff.kind == tyRange and result != isEqual: return isNone
  1493. else:
  1494. result = typeRel(c, rootf.lastSon, a)
  1495. if result != isNone:
  1496. put(c, f, a)
  1497. result = isGeneric
  1498. of tyGenericParam:
  1499. var x = PType(idTableGet(c.bindings, f))
  1500. if x == nil:
  1501. if c.callee.kind == tyGenericBody and
  1502. f.kind == tyGenericParam and not c.typedescMatched:
  1503. # XXX: The fact that generic types currently use tyGenericParam for
  1504. # their parameters is really a misnomer. tyGenericParam means "match
  1505. # any value" and what we need is "match any type", which can be encoded
  1506. # by a tyTypeDesc params. Unfortunately, this requires more substantial
  1507. # changes in semtypinst and elsewhere.
  1508. if tfWildcard in a.flags:
  1509. result = isGeneric
  1510. elif a.kind == tyTypeDesc:
  1511. if f.sonsLen == 0:
  1512. result = isGeneric
  1513. else:
  1514. internalAssert c.c.graph.config, a.len > 0
  1515. c.typedescMatched = true
  1516. var aa = a
  1517. while aa.kind in {tyTypeDesc, tyGenericParam} and aa.len > 0:
  1518. aa = lastSon(aa)
  1519. if aa.kind == tyGenericParam:
  1520. return isGeneric
  1521. result = typeRel(c, f.base, aa)
  1522. if result > isGeneric: result = isGeneric
  1523. elif c.isNoCall:
  1524. if doBind:
  1525. let concrete = concreteType(c, a, f)
  1526. if concrete == nil: return isNone
  1527. put(c, f, concrete)
  1528. result = isGeneric
  1529. else:
  1530. result = isNone
  1531. else:
  1532. # check if 'T' has a constraint as in 'proc p[T: Constraint](x: T)'
  1533. if f.sonsLen > 0 and f.sons[0].kind != tyNone:
  1534. let oldInheritancePenalty = c.inheritancePenalty
  1535. result = typeRel(c, f.sons[0], a, flags + {trDontBind})
  1536. if doBind and result notin {isNone, isGeneric}:
  1537. let concrete = concreteType(c, a, f)
  1538. if concrete == nil: return isNone
  1539. put(c, f, concrete)
  1540. # bug #6526
  1541. if result in {isEqual, isSubtype}:
  1542. # 'T: Class' is a *better* match than just 'T'
  1543. # but 'T: Subclass' is even better:
  1544. c.inheritancePenalty = oldInheritancePenalty - c.inheritancePenalty -
  1545. 100 * ord(result == isEqual)
  1546. result = isGeneric
  1547. else:
  1548. result = isGeneric
  1549. if result == isGeneric:
  1550. var concrete = a
  1551. if tfWildcard in a.flags:
  1552. a.sym.kind = skType
  1553. a.flags.excl tfWildcard
  1554. else:
  1555. concrete = concreteType(c, a, f)
  1556. if concrete == nil:
  1557. return isNone
  1558. if doBind:
  1559. put(c, f, concrete)
  1560. elif result > isGeneric:
  1561. result = isGeneric
  1562. elif a.kind == tyEmpty:
  1563. result = isGeneric
  1564. elif x.kind == tyGenericParam:
  1565. result = isGeneric
  1566. else:
  1567. result = typeRel(c, x, a) # check if it fits
  1568. if result > isGeneric: result = isGeneric
  1569. of tyStatic:
  1570. let prev = PType(idTableGet(c.bindings, f))
  1571. if prev == nil:
  1572. if aOrig.kind == tyStatic:
  1573. if f.base.kind != tyNone:
  1574. result = typeRel(c, f.base, a)
  1575. if result != isNone and f.n != nil:
  1576. if not exprStructuralEquivalent(f.n, aOrig.n):
  1577. result = isNone
  1578. else:
  1579. result = isGeneric
  1580. if result != isNone: put(c, f, aOrig)
  1581. elif aOrig.n != nil and aOrig.n.typ != nil:
  1582. result = if f.base.kind != tyNone: typeRel(c, f.lastSon, aOrig.n.typ)
  1583. else: isGeneric
  1584. if result != isNone:
  1585. var boundType = newTypeWithSons(c.c, tyStatic, @[aOrig.n.typ])
  1586. boundType.n = aOrig.n
  1587. put(c, f, boundType)
  1588. else:
  1589. result = isNone
  1590. elif prev.kind == tyStatic:
  1591. if aOrig.kind == tyStatic:
  1592. result = typeRel(c, prev.lastSon, a)
  1593. if result != isNone and prev.n != nil:
  1594. if not exprStructuralEquivalent(prev.n, aOrig.n):
  1595. result = isNone
  1596. else: result = isNone
  1597. else:
  1598. # XXX endless recursion?
  1599. #result = typeRel(c, prev, aOrig)
  1600. result = isNone
  1601. of tyInferred:
  1602. let prev = f.previouslyInferred
  1603. if prev != nil:
  1604. result = typeRel(c, prev, a)
  1605. else:
  1606. result = typeRel(c, f.base, a)
  1607. if result != isNone:
  1608. c.inferredTypes.add f
  1609. f.sons.add a
  1610. of tyTypeDesc:
  1611. var prev = PType(idTableGet(c.bindings, f))
  1612. if prev == nil:
  1613. # proc foo(T: typedesc, x: T)
  1614. # when `f` is an unresolved typedesc, `a` could be any
  1615. # type, so we should not perform this check earlier
  1616. if a.kind != tyTypeDesc:
  1617. if a.kind == tyGenericParam and tfWildcard in a.flags:
  1618. # TODO: prevent `a` from matching as a wildcard again
  1619. result = isGeneric
  1620. else:
  1621. result = isNone
  1622. elif f.base.kind == tyNone:
  1623. result = isGeneric
  1624. else:
  1625. result = typeRel(c, f.base, a.base)
  1626. if result != isNone:
  1627. put(c, f, a)
  1628. else:
  1629. if tfUnresolved in f.flags:
  1630. result = typeRel(c, prev.base, a)
  1631. elif a.kind == tyTypeDesc:
  1632. result = typeRel(c, prev.base, a.base)
  1633. else:
  1634. result = isNone
  1635. of tyTyped:
  1636. if aOrig != nil:
  1637. put(c, f, aOrig)
  1638. result = isGeneric
  1639. of tyProxy:
  1640. result = isEqual
  1641. of tyFromExpr:
  1642. # fix the expression, so it contains the already instantiated types
  1643. if f.n == nil or f.n.kind == nkEmpty: return isGeneric
  1644. let reevaluated = tryResolvingStaticExpr(c, f.n)
  1645. case reevaluated.typ.kind
  1646. of tyTypeDesc:
  1647. result = typeRel(c, a, reevaluated.typ.base)
  1648. of tyStatic:
  1649. result = typeRel(c, a, reevaluated.typ.base)
  1650. if result != isNone and reevaluated.typ.n != nil:
  1651. if not exprStructuralEquivalent(aOrig.n, reevaluated.typ.n):
  1652. result = isNone
  1653. else:
  1654. localError(c.c.graph.config, f.n.info, "type expected")
  1655. result = isNone
  1656. of tyNone:
  1657. if a.kind == tyNone: result = isEqual
  1658. else:
  1659. internalError c.c.graph.config, " unknown type kind " & $f.kind
  1660. when false:
  1661. var nowDebug = false
  1662. var dbgCount = 0
  1663. proc typeRel(c: var TCandidate, f, aOrig: PType,
  1664. flags: TTypeRelFlags = {}): TTypeRelation =
  1665. if nowDebug:
  1666. echo f, " <- ", aOrig
  1667. inc dbgCount
  1668. if dbgCount == 2:
  1669. writeStackTrace()
  1670. result = typeRelImpl(c, f, aOrig, flags)
  1671. if nowDebug:
  1672. echo f, " <- ", aOrig, " res ", result
  1673. proc cmpTypes*(c: PContext, f, a: PType): TTypeRelation =
  1674. var m: TCandidate
  1675. initCandidate(c, m, f)
  1676. result = typeRel(m, f, a)
  1677. proc getInstantiatedType(c: PContext, arg: PNode, m: TCandidate,
  1678. f: PType): PType =
  1679. result = PType(idTableGet(m.bindings, f))
  1680. if result == nil:
  1681. result = generateTypeInstance(c, m.bindings, arg, f)
  1682. if result == nil:
  1683. internalError(c.graph.config, arg.info, "getInstantiatedType")
  1684. result = errorType(c)
  1685. proc implicitConv(kind: TNodeKind, f: PType, arg: PNode, m: TCandidate,
  1686. c: PContext): PNode =
  1687. result = newNodeI(kind, arg.info)
  1688. if containsGenericType(f):
  1689. if not m.hasFauxMatch:
  1690. result.typ = getInstantiatedType(c, arg, m, f)
  1691. else:
  1692. result.typ = errorType(c)
  1693. else:
  1694. result.typ = f
  1695. if result.typ == nil: internalError(c.graph.config, arg.info, "implicitConv")
  1696. addSon(result, c.graph.emptyNode)
  1697. addSon(result, arg)
  1698. proc userConvMatch(c: PContext, m: var TCandidate, f, a: PType,
  1699. arg: PNode): PNode =
  1700. result = nil
  1701. for i in 0 ..< len(c.converters):
  1702. var src = c.converters[i].typ.sons[1]
  1703. var dest = c.converters[i].typ.sons[0]
  1704. # for generic type converters we need to check 'src <- a' before
  1705. # 'f <- dest' in order to not break the unification:
  1706. # see tests/tgenericconverter:
  1707. let srca = typeRel(m, src, a)
  1708. if srca notin {isEqual, isGeneric, isSubtype}: continue
  1709. # What's done below matches the logic in ``matchesAux``
  1710. let constraint = c.converters[i].typ.n[1].sym.constraint
  1711. if not constraint.isNil and not matchNodeKinds(constraint, arg):
  1712. continue
  1713. if src.kind in {tyVar, tyLent} and not arg.isLValue:
  1714. continue
  1715. let destIsGeneric = containsGenericType(dest)
  1716. if destIsGeneric:
  1717. dest = generateTypeInstance(c, m.bindings, arg, dest)
  1718. let fdest = typeRel(m, f, dest)
  1719. if fdest in {isEqual, isGeneric} and not (dest.kind == tyLent and f.kind == tyVar):
  1720. markUsed(c.config, arg.info, c.converters[i], c.graph.usageSym)
  1721. var s = newSymNode(c.converters[i])
  1722. s.typ = c.converters[i].typ
  1723. s.info = arg.info
  1724. result = newNodeIT(nkHiddenCallConv, arg.info, dest)
  1725. addSon(result, s)
  1726. # We build the call expression by ourselves in order to avoid passing this
  1727. # expression trough the semantic check phase once again so let's make sure
  1728. # it is correct
  1729. var param: PNode = nil
  1730. if srca == isSubtype:
  1731. param = implicitConv(nkHiddenSubConv, src, copyTree(arg), m, c)
  1732. elif src.kind == tyVar:
  1733. # Analyse the converter return type
  1734. param = newNodeIT(nkHiddenAddr, arg.info, s.typ[1])
  1735. param.addSon(copyTree(arg))
  1736. else:
  1737. param = copyTree(arg)
  1738. addSon(result, param)
  1739. if dest.kind in {tyVar, tyLent}:
  1740. dest.flags.incl tfVarIsPtr
  1741. result = newDeref(result)
  1742. inc(m.convMatches)
  1743. if not m.genericConverter:
  1744. m.genericConverter = srca == isGeneric or destIsGeneric
  1745. return result
  1746. proc localConvMatch(c: PContext, m: var TCandidate, f, a: PType,
  1747. arg: PNode): PNode =
  1748. # arg.typ can be nil in 'suggest':
  1749. if isNil(arg.typ): return nil
  1750. # sem'checking for 'echo' needs to be re-entrant:
  1751. # XXX we will revisit this issue after 0.10.2 is released
  1752. if f == arg.typ and arg.kind == nkHiddenStdConv: return arg
  1753. var call = newNodeI(nkCall, arg.info)
  1754. call.add(f.n.copyTree)
  1755. call.add(arg.copyTree)
  1756. result = c.semExpr(c, call)
  1757. if result != nil:
  1758. if result.typ == nil: return nil
  1759. # resulting type must be consistent with the other arguments:
  1760. var r = typeRel(m, f.sons[0], result.typ)
  1761. if r < isGeneric: return nil
  1762. if result.kind == nkCall: result.kind = nkHiddenCallConv
  1763. inc(m.convMatches)
  1764. if r == isGeneric:
  1765. result.typ = getInstantiatedType(c, arg, m, base(f))
  1766. m.baseTypeMatch = true
  1767. proc incMatches(m: var TCandidate; r: TTypeRelation; convMatch = 1) =
  1768. case r
  1769. of isConvertible, isIntConv: inc(m.convMatches, convMatch)
  1770. of isSubtype, isSubrange: inc(m.subtypeMatches)
  1771. of isGeneric, isInferred, isBothMetaConvertible: inc(m.genericMatches)
  1772. of isFromIntLit: inc(m.intConvMatches, 256)
  1773. of isInferredConvertible:
  1774. inc(m.convMatches)
  1775. of isEqual: inc(m.exactMatches)
  1776. of isNone: discard
  1777. template matchesVoidProc(t: PType): bool =
  1778. (t.kind == tyProc and t.len == 1 and t.sons[0] == nil) or
  1779. (t.kind == tyBuiltInTypeClass and t.sons[0].kind == tyProc)
  1780. proc paramTypesMatchAux(m: var TCandidate, f, a: PType,
  1781. argSemantized, argOrig: PNode): PNode =
  1782. var
  1783. fMaybeStatic = f.skipTypes({tyDistinct})
  1784. arg = argSemantized
  1785. a = a
  1786. c = m.c
  1787. if tfHasStatic in fMaybeStatic.flags:
  1788. # XXX: When implicit statics are the default
  1789. # this will be done earlier - we just have to
  1790. # make sure that static types enter here
  1791. # Zahary: weaken tyGenericParam and call it tyGenericPlaceholder
  1792. # and finally start using tyTypedesc for generic types properly.
  1793. # Araq: This would only shift the problems around, in 'proc p[T](x: T)'
  1794. # the T is NOT a typedesc.
  1795. if a.kind == tyGenericParam and tfWildcard in a.flags:
  1796. a.assignType(f)
  1797. # put(m.bindings, f, a)
  1798. return argSemantized
  1799. if a.kind == tyStatic:
  1800. if m.callee.kind == tyGenericBody and
  1801. a.n == nil and
  1802. tfGenericTypeParam notin a.flags:
  1803. return newNodeIT(nkType, argOrig.info, makeTypeFromExpr(c, arg))
  1804. else:
  1805. var evaluated = c.semTryConstExpr(c, arg)
  1806. if evaluated != nil:
  1807. # Don't build the type in-place because `evaluated` and `arg` may point
  1808. # to the same object and we'd end up creating recursive types (#9255)
  1809. let typ = newTypeS(tyStatic, c)
  1810. typ.sons = @[evaluated.typ]
  1811. typ.n = evaluated
  1812. arg.typ = typ
  1813. a = typ
  1814. else:
  1815. if m.callee.kind == tyGenericBody:
  1816. if f.kind == tyStatic and typeRel(m, f.base, a) != isNone:
  1817. result = makeStaticExpr(m.c, arg)
  1818. result.typ.flags.incl tfUnresolved
  1819. result.typ.n = arg
  1820. return
  1821. let oldInheritancePenalty = m.inheritancePenalty
  1822. var r = typeRel(m, f, a)
  1823. # This special typing rule for macros and templates is not documented
  1824. # anywhere and breaks symmetry. It's hard to get rid of though, my
  1825. # custom seqs example fails to compile without this:
  1826. if r != isNone and m.calleeSym != nil and
  1827. m.calleeSym.kind in {skMacro, skTemplate}:
  1828. # XXX: duplicating this is ugly, but we cannot (!) move this
  1829. # directly into typeRel using return-like templates
  1830. incMatches(m, r)
  1831. if f.kind == tyTyped:
  1832. return arg
  1833. elif f.kind == tyTypeDesc:
  1834. return arg
  1835. elif f.kind == tyStatic and arg.typ.n != nil:
  1836. return arg.typ.n
  1837. else:
  1838. return argSemantized # argOrig
  1839. # If r == isBothMetaConvertible then we rerun typeRel.
  1840. # bothMetaCounter is for safety to avoid any infinite loop,
  1841. # I don't have any example when it is needed.
  1842. # lastBindingsLenth is used to check whether m.bindings remains the same,
  1843. # because in that case there is no point in continuing.
  1844. var bothMetaCounter = 0
  1845. var lastBindingsLength = -1
  1846. while r == isBothMetaConvertible and
  1847. lastBindingsLength != m.bindings.counter and
  1848. bothMetaCounter < 100:
  1849. lastBindingsLength = m.bindings.counter
  1850. inc(bothMetaCounter)
  1851. if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds:
  1852. result = c.semInferredLambda(c, m.bindings, arg)
  1853. elif arg.kind != nkSym:
  1854. return nil
  1855. else:
  1856. let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info)
  1857. result = newSymNode(inferred, arg.info)
  1858. inc(m.convMatches)
  1859. arg = result
  1860. r = typeRel(m, f, arg.typ)
  1861. case r
  1862. of isConvertible:
  1863. inc(m.convMatches)
  1864. result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  1865. of isIntConv:
  1866. # I'm too lazy to introduce another ``*matches`` field, so we conflate
  1867. # ``isIntConv`` and ``isIntLit`` here:
  1868. inc(m.intConvMatches)
  1869. result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  1870. of isSubtype:
  1871. inc(m.subtypeMatches)
  1872. if f.kind == tyTypeDesc:
  1873. result = arg
  1874. else:
  1875. result = implicitConv(nkHiddenSubConv, f, arg, m, c)
  1876. of isSubrange:
  1877. inc(m.subtypeMatches)
  1878. if f.kind == tyVar:
  1879. result = arg
  1880. else:
  1881. result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  1882. of isInferred, isInferredConvertible:
  1883. if arg.kind in {nkProcDef, nkFuncDef, nkIteratorDef} + nkLambdaKinds:
  1884. result = c.semInferredLambda(c, m.bindings, arg)
  1885. elif arg.kind != nkSym:
  1886. return nil
  1887. else:
  1888. let inferred = c.semGenerateInstance(c, arg.sym, m.bindings, arg.info)
  1889. result = newSymNode(inferred, arg.info)
  1890. if r == isInferredConvertible:
  1891. inc(m.convMatches)
  1892. result = implicitConv(nkHiddenStdConv, f, result, m, c)
  1893. else:
  1894. inc(m.genericMatches)
  1895. of isGeneric:
  1896. inc(m.genericMatches)
  1897. if arg.typ == nil:
  1898. result = arg
  1899. elif skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple or
  1900. m.inheritancePenalty > oldInheritancePenalty:
  1901. result = implicitConv(nkHiddenSubConv, f, arg, m, c)
  1902. elif arg.typ.isEmptyContainer:
  1903. result = arg.copyTree
  1904. result.typ = getInstantiatedType(c, arg, m, f)
  1905. else:
  1906. result = arg
  1907. of isBothMetaConvertible:
  1908. # This is the result for the 101th time.
  1909. result = nil
  1910. of isFromIntLit:
  1911. # too lazy to introduce another ``*matches`` field, so we conflate
  1912. # ``isIntConv`` and ``isIntLit`` here:
  1913. inc(m.intConvMatches, 256)
  1914. result = implicitConv(nkHiddenStdConv, f, arg, m, c)
  1915. of isEqual:
  1916. inc(m.exactMatches)
  1917. result = arg
  1918. if skipTypes(f, abstractVar-{tyTypeDesc}).kind == tyTuple or
  1919. (arg.typ != nil and skipTypes(arg.typ, abstractVar-{tyTypeDesc}).kind == tyTuple):
  1920. result = implicitConv(nkHiddenSubConv, f, arg, m, c)
  1921. of isNone:
  1922. # do not do this in ``typeRel`` as it then can't infer T in ``ref T``:
  1923. if a.kind in {tyProxy, tyUnknown}:
  1924. inc(m.genericMatches)
  1925. m.fauxMatch = a.kind
  1926. return arg
  1927. elif a.kind == tyVoid and f.matchesVoidProc and argOrig.kind == nkStmtList:
  1928. # lift do blocks without params to lambdas
  1929. let p = c.graph
  1930. let lifted = c.semExpr(c, newProcNode(nkDo, argOrig.info, body = argOrig,
  1931. params = nkFormalParams.newTree(p.emptyNode), name = p.emptyNode, pattern = p.emptyNode,
  1932. genericParams = p.emptyNode, pragmas = p.emptyNode, exceptions = p.emptyNode), {})
  1933. if f.kind == tyBuiltInTypeClass:
  1934. inc m.genericMatches
  1935. put(m, f, lifted.typ)
  1936. inc m.convMatches
  1937. return implicitConv(nkHiddenStdConv, f, lifted, m, c)
  1938. result = userConvMatch(c, m, f, a, arg)
  1939. # check for a base type match, which supports varargs[T] without []
  1940. # constructor in a call:
  1941. if result == nil and f.kind == tyVarargs:
  1942. if f.n != nil:
  1943. # Forward to the varargs converter
  1944. result = localConvMatch(c, m, f, a, arg)
  1945. else:
  1946. r = typeRel(m, base(f), a)
  1947. case r
  1948. of isGeneric:
  1949. inc(m.convMatches)
  1950. result = copyTree(arg)
  1951. result.typ = getInstantiatedType(c, arg, m, base(f))
  1952. m.baseTypeMatch = true
  1953. of isFromIntLit:
  1954. inc(m.intConvMatches, 256)
  1955. result = implicitConv(nkHiddenStdConv, f[0], arg, m, c)
  1956. m.baseTypeMatch = true
  1957. of isEqual:
  1958. inc(m.convMatches)
  1959. result = copyTree(arg)
  1960. m.baseTypeMatch = true
  1961. of isSubtype: # bug #4799, varargs accepting subtype relation object
  1962. inc(m.subtypeMatches)
  1963. if base(f).kind == tyTypeDesc:
  1964. result = arg
  1965. else:
  1966. result = implicitConv(nkHiddenSubConv, base(f), arg, m, c)
  1967. m.baseTypeMatch = true
  1968. else:
  1969. result = userConvMatch(c, m, base(f), a, arg)
  1970. if result != nil: m.baseTypeMatch = true
  1971. proc paramTypesMatch*(m: var TCandidate, f, a: PType,
  1972. arg, argOrig: PNode): PNode =
  1973. if arg == nil or arg.kind notin nkSymChoices:
  1974. result = paramTypesMatchAux(m, f, a, arg, argOrig)
  1975. else:
  1976. # CAUTION: The order depends on the used hashing scheme. Thus it is
  1977. # incorrect to simply use the first fitting match. However, to implement
  1978. # this correctly is inefficient. We have to copy `m` here to be able to
  1979. # roll back the side effects of the unification algorithm.
  1980. let c = m.c
  1981. var x, y, z: TCandidate
  1982. initCandidate(c, x, m.callee)
  1983. initCandidate(c, y, m.callee)
  1984. initCandidate(c, z, m.callee)
  1985. x.calleeSym = m.calleeSym
  1986. y.calleeSym = m.calleeSym
  1987. z.calleeSym = m.calleeSym
  1988. var best = -1
  1989. for i in 0 ..< arg.len:
  1990. if arg.sons[i].sym.kind in {skProc, skFunc, skMethod, skConverter,
  1991. skIterator, skMacro, skTemplate}:
  1992. copyCandidate(z, m)
  1993. z.callee = arg.sons[i].typ
  1994. if tfUnresolved in z.callee.flags: continue
  1995. z.calleeSym = arg.sons[i].sym
  1996. #if arg.sons[i].sym.name.s == "cmp":
  1997. # ggDebug = true
  1998. # echo "CALLLEEEEEEEE A ", typeToString(z.callee)
  1999. # XXX this is still all wrong: (T, T) should be 2 generic matches
  2000. # and (int, int) 2 exact matches, etc. Essentially you cannot call
  2001. # typeRel here and expect things to work!
  2002. let r = typeRel(z, f, arg.sons[i].typ)
  2003. incMatches(z, r, 2)
  2004. #if arg.sons[i].sym.name.s == "cmp": # and arg.info.line == 606:
  2005. # echo "M ", r, " ", arg.info, " ", typeToString(arg.sons[i].sym.typ)
  2006. # writeMatches(z)
  2007. if r != isNone:
  2008. z.state = csMatch
  2009. case x.state
  2010. of csEmpty, csNoMatch:
  2011. x = z
  2012. best = i
  2013. of csMatch:
  2014. let cmp = cmpCandidates(x, z)
  2015. if cmp < 0:
  2016. best = i
  2017. x = z
  2018. elif cmp == 0:
  2019. y = z # z is as good as x
  2020. if x.state == csEmpty:
  2021. result = nil
  2022. elif y.state == csMatch and cmpCandidates(x, y) == 0:
  2023. if x.state != csMatch:
  2024. internalError(m.c.graph.config, arg.info, "x.state is not csMatch")
  2025. # ambiguous: more than one symbol fits!
  2026. # See tsymchoice_for_expr as an example. 'f.kind == tyUntyped' should match
  2027. # anyway:
  2028. if f.kind in {tyUntyped, tyTyped}: result = arg
  2029. else: result = nil
  2030. else:
  2031. # only one valid interpretation found:
  2032. markUsed(m.c.config, arg.info, arg.sons[best].sym, m.c.graph.usageSym)
  2033. onUse(arg.info, arg.sons[best].sym)
  2034. result = paramTypesMatchAux(m, f, arg.sons[best].typ, arg.sons[best],
  2035. argOrig)
  2036. when false:
  2037. if m.calleeSym != nil and m.calleeSym.name.s == "[]":
  2038. echo m.c.config $ arg.info, " for ", m.calleeSym.name.s, " ", m.c.config $ m.calleeSym.info
  2039. writeMatches(m)
  2040. proc setSon(father: PNode, at: int, son: PNode) =
  2041. let oldLen = father.len
  2042. if oldLen <= at:
  2043. setLen(father.sons, at + 1)
  2044. father.sons[at] = son
  2045. # insert potential 'void' parameters:
  2046. #for i in oldLen ..< at:
  2047. # father.sons[i] = newNodeIT(nkEmpty, son.info, getSysType(tyVoid))
  2048. # we are allowed to modify the calling node in the 'prepare*' procs:
  2049. proc prepareOperand(c: PContext; formal: PType; a: PNode): PNode =
  2050. if formal.kind == tyUntyped and formal.len != 1:
  2051. # {tyTypeDesc, tyUntyped, tyTyped, tyProxy}:
  2052. # a.typ == nil is valid
  2053. result = a
  2054. elif a.typ.isNil:
  2055. # XXX This is unsound! 'formal' can differ from overloaded routine to
  2056. # overloaded routine!
  2057. let flags = {efDetermineType, efAllowStmt}
  2058. #if formal.kind == tyIter: {efDetermineType, efWantIterator}
  2059. #else: {efDetermineType, efAllowStmt}
  2060. #elif formal.kind == tyTyped: {efDetermineType, efWantStmt}
  2061. #else: {efDetermineType}
  2062. result = c.semOperand(c, a, flags)
  2063. else:
  2064. result = a
  2065. considerGenSyms(c, result)
  2066. proc prepareOperand(c: PContext; a: PNode): PNode =
  2067. if a.typ.isNil:
  2068. result = c.semOperand(c, a, {efDetermineType})
  2069. else:
  2070. result = a
  2071. considerGenSyms(c, result)
  2072. proc prepareNamedParam(a: PNode; c: PContext) =
  2073. if a.sons[0].kind != nkIdent:
  2074. var info = a.sons[0].info
  2075. a.sons[0] = newIdentNode(considerQuotedIdent(c, a.sons[0]), info)
  2076. proc arrayConstr(c: PContext, n: PNode): PType =
  2077. result = newTypeS(tyArray, c)
  2078. rawAddSon(result, makeRangeType(c, 0, 0, n.info))
  2079. addSonSkipIntLit(result, skipTypes(n.typ,
  2080. {tyGenericInst, tyVar, tyLent, tyOrdinal}))
  2081. proc arrayConstr(c: PContext, info: TLineInfo): PType =
  2082. result = newTypeS(tyArray, c)
  2083. rawAddSon(result, makeRangeType(c, 0, -1, info))
  2084. rawAddSon(result, newTypeS(tyEmpty, c)) # needs an empty basetype!
  2085. proc incrIndexType(t: PType) =
  2086. assert t.kind == tyArray
  2087. inc t.sons[0].n.sons[1].intVal
  2088. template isVarargsUntyped(x): untyped =
  2089. x.kind == tyVarargs and x.sons[0].kind == tyUntyped
  2090. proc matchesAux(c: PContext, n, nOrig: PNode,
  2091. m: var TCandidate, marker: var IntSet) =
  2092. var
  2093. a = 1 # iterates over the actual given arguments
  2094. f = if m.callee.kind != tyGenericBody: 1
  2095. else: 0 # iterates over formal parameters
  2096. arg: PNode # current prepared argument
  2097. formal: PSym # current routine parameter
  2098. defer:
  2099. m.firstMismatch.arg = a
  2100. m.firstMismatch.formal = formal
  2101. template checkConstraint(n: untyped) {.dirty.} =
  2102. if not formal.constraint.isNil:
  2103. if matchNodeKinds(formal.constraint, n):
  2104. # better match over other routines with no such restriction:
  2105. inc(m.genericMatches, 100)
  2106. else:
  2107. m.state = csNoMatch
  2108. return
  2109. if formal.typ.kind == tyVar:
  2110. let argConverter = if arg.kind == nkHiddenDeref: arg[0] else: arg
  2111. if argConverter.kind == nkHiddenCallConv:
  2112. if argConverter.typ.kind != tyVar:
  2113. m.state = csNoMatch
  2114. m.firstMismatch.kind = kVarNeeded
  2115. return
  2116. elif not n.isLValue:
  2117. m.state = csNoMatch
  2118. m.firstMismatch.kind = kVarNeeded
  2119. return
  2120. m.state = csMatch # until proven otherwise
  2121. m.firstMismatch = MismatchInfo()
  2122. m.call = newNodeI(n.kind, n.info)
  2123. m.call.typ = base(m.callee) # may be nil
  2124. var formalLen = m.callee.n.len
  2125. addSon(m.call, n.sons[0])
  2126. var container: PNode = nil # constructed container
  2127. formal = if formalLen > 1: m.callee.n.sons[1].sym else: nil
  2128. while a < n.len:
  2129. if a >= formalLen-1 and f < formalLen and m.callee.n[f].typ.isVarargsUntyped:
  2130. formal = m.callee.n.sons[f].sym
  2131. incl(marker, formal.position)
  2132. if n.sons[a].kind == nkHiddenStdConv:
  2133. doAssert n.sons[a].sons[0].kind == nkEmpty and
  2134. n.sons[a].sons[1].kind in {nkBracket, nkArgList}
  2135. # Steal the container and pass it along
  2136. setSon(m.call, formal.position + 1, n.sons[a].sons[1])
  2137. else:
  2138. if container.isNil:
  2139. container = newNodeIT(nkArgList, n.sons[a].info, arrayConstr(c, n.info))
  2140. setSon(m.call, formal.position + 1, container)
  2141. else:
  2142. incrIndexType(container.typ)
  2143. addSon(container, n.sons[a])
  2144. elif n.sons[a].kind == nkExprEqExpr:
  2145. # named param
  2146. m.firstMismatch.kind = kUnknownNamedParam
  2147. # check if m.callee has such a param:
  2148. prepareNamedParam(n.sons[a], c)
  2149. if n.sons[a].sons[0].kind != nkIdent:
  2150. localError(c.config, n.sons[a].info, "named parameter has to be an identifier")
  2151. m.state = csNoMatch
  2152. return
  2153. formal = getSymFromList(m.callee.n, n.sons[a].sons[0].ident, 1)
  2154. if formal == nil:
  2155. # no error message!
  2156. m.state = csNoMatch
  2157. return
  2158. if containsOrIncl(marker, formal.position):
  2159. m.firstMismatch.kind = kAlreadyGiven
  2160. # already in namedParams, so no match
  2161. # we used to produce 'errCannotBindXTwice' here but see
  2162. # bug #3836 of why that is not sound (other overload with
  2163. # different parameter names could match later on):
  2164. when false: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s)
  2165. m.state = csNoMatch
  2166. return
  2167. m.baseTypeMatch = false
  2168. m.typedescMatched = false
  2169. n.sons[a].sons[1] = prepareOperand(c, formal.typ, n.sons[a].sons[1])
  2170. n.sons[a].typ = n.sons[a].sons[1].typ
  2171. arg = paramTypesMatch(m, formal.typ, n.sons[a].typ,
  2172. n.sons[a].sons[1], n.sons[a].sons[1])
  2173. m.firstMismatch.kind = kTypeMismatch
  2174. if arg == nil:
  2175. m.state = csNoMatch
  2176. return
  2177. checkConstraint(n.sons[a].sons[1])
  2178. if m.baseTypeMatch:
  2179. #assert(container == nil)
  2180. container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg))
  2181. addSon(container, arg)
  2182. setSon(m.call, formal.position + 1, container)
  2183. if f != formalLen - 1: container = nil
  2184. else:
  2185. setSon(m.call, formal.position + 1, arg)
  2186. inc f
  2187. else:
  2188. # unnamed param
  2189. if f >= formalLen:
  2190. # too many arguments?
  2191. if tfVarargs in m.callee.flags:
  2192. # is ok... but don't increment any counters...
  2193. # we have no formal here to snoop at:
  2194. n.sons[a] = prepareOperand(c, n.sons[a])
  2195. if skipTypes(n.sons[a].typ, abstractVar-{tyTypeDesc}).kind==tyString:
  2196. addSon(m.call, implicitConv(nkHiddenStdConv,
  2197. getSysType(c.graph, n.sons[a].info, tyCString),
  2198. copyTree(n.sons[a]), m, c))
  2199. else:
  2200. addSon(m.call, copyTree(n.sons[a]))
  2201. elif formal != nil and formal.typ.kind == tyVarargs:
  2202. m.firstMismatch.kind = kTypeMismatch
  2203. # beware of the side-effects in 'prepareOperand'! So only do it for
  2204. # varargs matching. See tests/metatype/tstatic_overloading.
  2205. m.baseTypeMatch = false
  2206. m.typedescMatched = false
  2207. incl(marker, formal.position)
  2208. n.sons[a] = prepareOperand(c, formal.typ, n.sons[a])
  2209. arg = paramTypesMatch(m, formal.typ, n.sons[a].typ,
  2210. n.sons[a], nOrig.sons[a])
  2211. if arg != nil and m.baseTypeMatch and container != nil:
  2212. addSon(container, arg)
  2213. incrIndexType(container.typ)
  2214. checkConstraint(n.sons[a])
  2215. else:
  2216. m.state = csNoMatch
  2217. return
  2218. else:
  2219. m.firstMismatch.kind = kExtraArg
  2220. m.state = csNoMatch
  2221. return
  2222. else:
  2223. if m.callee.n.sons[f].kind != nkSym:
  2224. internalError(c.config, n.sons[a].info, "matches")
  2225. return
  2226. formal = m.callee.n.sons[f].sym
  2227. m.firstMismatch.kind = kTypeMismatch
  2228. if containsOrIncl(marker, formal.position) and container.isNil:
  2229. m.firstMismatch.kind = kAlreadyGiven
  2230. # already in namedParams: (see above remark)
  2231. when false: localError(n.sons[a].info, errCannotBindXTwice, formal.name.s)
  2232. m.state = csNoMatch
  2233. return
  2234. if formal.typ.isVarargsUntyped:
  2235. if container.isNil:
  2236. container = newNodeIT(nkArgList, n.sons[a].info, arrayConstr(c, n.info))
  2237. setSon(m.call, formal.position + 1, container)
  2238. else:
  2239. incrIndexType(container.typ)
  2240. addSon(container, n.sons[a])
  2241. else:
  2242. m.baseTypeMatch = false
  2243. m.typedescMatched = false
  2244. n.sons[a] = prepareOperand(c, formal.typ, n.sons[a])
  2245. arg = paramTypesMatch(m, formal.typ, n.sons[a].typ,
  2246. n.sons[a], nOrig.sons[a])
  2247. if arg == nil:
  2248. m.state = csNoMatch
  2249. return
  2250. if m.baseTypeMatch:
  2251. assert formal.typ.kind == tyVarargs
  2252. #assert(container == nil)
  2253. if container.isNil:
  2254. container = newNodeIT(nkBracket, n.sons[a].info, arrayConstr(c, arg))
  2255. container.typ.flags.incl tfVarargs
  2256. else:
  2257. incrIndexType(container.typ)
  2258. addSon(container, arg)
  2259. setSon(m.call, formal.position + 1,
  2260. implicitConv(nkHiddenStdConv, formal.typ, container, m, c))
  2261. #if f != formalLen - 1: container = nil
  2262. # pick the formal from the end, so that 'x, y, varargs, z' works:
  2263. f = max(f, formalLen - n.len + a + 1)
  2264. elif formal.typ.kind != tyVarargs or container == nil:
  2265. setSon(m.call, formal.position + 1, arg)
  2266. inc(f)
  2267. container = nil
  2268. else:
  2269. # we end up here if the argument can be converted into the varargs
  2270. # formal (eg. seq[T] -> varargs[T]) but we have already instantiated
  2271. # a container
  2272. #assert arg.kind == nkHiddenStdConv # for 'nim check'
  2273. # this assertion can be off
  2274. localError(c.config, n.sons[a].info, "cannot convert $1 to $2" % [
  2275. typeToString(n.sons[a].typ), typeToString(formal.typ) ])
  2276. m.state = csNoMatch
  2277. return
  2278. checkConstraint(n.sons[a])
  2279. inc(a)
  2280. proc semFinishOperands*(c: PContext, n: PNode) =
  2281. # this needs to be called to ensure that after overloading resolution every
  2282. # argument has been sem'checked:
  2283. for i in 1 ..< n.len:
  2284. n.sons[i] = prepareOperand(c, n.sons[i])
  2285. proc partialMatch*(c: PContext, n, nOrig: PNode, m: var TCandidate) =
  2286. # for 'suggest' support:
  2287. var marker = initIntSet()
  2288. matchesAux(c, n, nOrig, m, marker)
  2289. proc matches*(c: PContext, n, nOrig: PNode, m: var TCandidate) =
  2290. if m.magic in {mArrGet, mArrPut}:
  2291. m.state = csMatch
  2292. m.call = n
  2293. # Note the following doesn't work as it would produce ambiguities.
  2294. # Instead we patch system.nim, see bug #8049.
  2295. when false:
  2296. inc m.genericMatches
  2297. inc m.exactMatches
  2298. return
  2299. var marker = initIntSet()
  2300. matchesAux(c, n, nOrig, m, marker)
  2301. if m.state == csNoMatch: return
  2302. # check that every formal parameter got a value:
  2303. var f = 1
  2304. while f < sonsLen(m.callee.n):
  2305. var formal = m.callee.n.sons[f].sym
  2306. if not containsOrIncl(marker, formal.position):
  2307. if formal.ast == nil:
  2308. if formal.typ.kind == tyVarargs:
  2309. # For consistency with what happens in `matchesAux` select the
  2310. # container node kind accordingly
  2311. let cnKind = if formal.typ.isVarargsUntyped: nkArgList else: nkBracket
  2312. var container = newNodeIT(cnKind, n.info, arrayConstr(c, n.info))
  2313. setSon(m.call, formal.position + 1,
  2314. implicitConv(nkHiddenStdConv, formal.typ, container, m, c))
  2315. else:
  2316. # no default value
  2317. m.state = csNoMatch
  2318. m.firstMismatch.kind = kMissingParam
  2319. m.firstMismatch.formal = formal
  2320. break
  2321. else:
  2322. if formal.ast.kind == nkEmpty:
  2323. # The default param value is set to empty in `instantiateProcType`
  2324. # when the type of the default expression doesn't match the type
  2325. # of the instantiated proc param:
  2326. localError(c.config, m.call.info,
  2327. ("The default parameter '$1' has incompatible type " &
  2328. "with the explicitly requested proc instantiation") %
  2329. formal.name.s)
  2330. if nfDefaultRefsParam in formal.ast.flags:
  2331. m.call.flags.incl nfDefaultRefsParam
  2332. var def = copyTree(formal.ast)
  2333. if def.kind == nkNilLit:
  2334. def = implicitConv(nkHiddenStdConv, formal.typ, def, m, c)
  2335. if {tfImplicitTypeParam, tfGenericTypeParam} * formal.typ.flags != {}:
  2336. put(m, formal.typ, def.typ)
  2337. def.flags.incl nfDefaultParam
  2338. setSon(m.call, formal.position + 1, def)
  2339. inc(f)
  2340. # forget all inferred types if the overload matching failed
  2341. if m.state == csNoMatch:
  2342. for t in m.inferredTypes:
  2343. if t.sonsLen > 1: t.sons.setLen 1
  2344. proc argtypeMatches*(c: PContext, f, a: PType, fromHlo = false): bool =
  2345. var m: TCandidate
  2346. initCandidate(c, m, f)
  2347. let res = paramTypesMatch(m, f, a, c.graph.emptyNode, nil)
  2348. #instantiateGenericConverters(c, res, m)
  2349. # XXX this is used by patterns.nim too; I think it's better to not
  2350. # instantiate generic converters for that
  2351. if not fromHlo:
  2352. res != nil
  2353. else:
  2354. # pattern templates do not allow for conversions except from int literal
  2355. res != nil and m.convMatches == 0 and m.intConvMatches in [0, 256]
  2356. proc instTypeBoundOp*(c: PContext; dc: PSym; t: PType; info: TLineInfo;
  2357. op: TTypeAttachedOp; col: int): PSym {.procvar.} =
  2358. var m: TCandidate
  2359. initCandidate(c, m, dc.typ)
  2360. if col >= dc.typ.len:
  2361. localError(c.config, info, "cannot instantiate: '" & dc.name.s & "'")
  2362. return nil
  2363. var f = dc.typ.sons[col]
  2364. if op == attachedDeepCopy:
  2365. if f.kind in {tyRef, tyPtr}: f = f.lastSon
  2366. else:
  2367. if f.kind == tyVar: f = f.lastSon
  2368. #if c.config.selectedGC == gcDestructors and f.kind == tySequence:
  2369. # use the canonical type to access the =sink and =destroy etc.
  2370. # f = c.graph.sysTypes[tySequence]
  2371. #echo "YUP_---------Formal ", typeToString(f, preferDesc), " real ", typeToString(t, preferDesc), " ", f.id, " ", t.id
  2372. if typeRel(m, f, t) == isNone:
  2373. localError(c.config, info, "cannot instantiate: '" & dc.name.s & "'")
  2374. else:
  2375. result = c.semGenerateInstance(c, dc, m.bindings, info)
  2376. if op == attachedDeepCopy:
  2377. assert sfFromGeneric in result.flags
  2378. include suggest
  2379. when not declared(tests):
  2380. template tests(s: untyped) = discard
  2381. tests:
  2382. var dummyOwner = newSym(skModule, getIdent("test_module"), nil, UnknownLineInfo())
  2383. proc `|` (t1, t2: PType): PType =
  2384. result = newType(tyOr, dummyOwner)
  2385. result.rawAddSon(t1)
  2386. result.rawAddSon(t2)
  2387. proc `&` (t1, t2: PType): PType =
  2388. result = newType(tyAnd, dummyOwner)
  2389. result.rawAddSon(t1)
  2390. result.rawAddSon(t2)
  2391. proc `!` (t: PType): PType =
  2392. result = newType(tyNot, dummyOwner)
  2393. result.rawAddSon(t)
  2394. proc seq(t: PType): PType =
  2395. result = newType(tySequence, dummyOwner)
  2396. result.rawAddSon(t)
  2397. proc array(x: int, t: PType): PType =
  2398. result = newType(tyArray, dummyOwner)
  2399. var n = newNodeI(nkRange, UnknownLineInfo())
  2400. addSon(n, newIntNode(nkIntLit, 0))
  2401. addSon(n, newIntNode(nkIntLit, x))
  2402. let range = newType(tyRange, dummyOwner)
  2403. result.rawAddSon(range)
  2404. result.rawAddSon(t)
  2405. suite "type classes":
  2406. let
  2407. int = newType(tyInt, dummyOwner)
  2408. float = newType(tyFloat, dummyOwner)
  2409. string = newType(tyString, dummyOwner)
  2410. ordinal = newType(tyOrdinal, dummyOwner)
  2411. any = newType(tyAnything, dummyOwner)
  2412. number = int | float
  2413. var TFoo = newType(tyObject, dummyOwner)
  2414. TFoo.sym = newSym(skType, getIdent"TFoo", dummyOwner, UnknownLineInfo())
  2415. var T1 = newType(tyGenericParam, dummyOwner)
  2416. T1.sym = newSym(skType, getIdent"T1", dummyOwner, UnknownLineInfo())
  2417. T1.sym.position = 0
  2418. var T2 = newType(tyGenericParam, dummyOwner)
  2419. T2.sym = newSym(skType, getIdent"T2", dummyOwner, UnknownLineInfo())
  2420. T2.sym.position = 1
  2421. setup:
  2422. var c: TCandidate
  2423. initCandidate(nil, c, nil)
  2424. template yes(x, y) =
  2425. test astToStr(x) & " is " & astToStr(y):
  2426. check typeRel(c, y, x) == isGeneric
  2427. template no(x, y) =
  2428. test astToStr(x) & " is not " & astToStr(y):
  2429. check typeRel(c, y, x) == isNone
  2430. yes seq(any), array(10, int) | seq(any)
  2431. # Sure, seq[any] is directly included
  2432. yes seq(int), seq(any)
  2433. yes seq(int), seq(number)
  2434. # Sure, the int sequence is certainly
  2435. # part of the number sequences (and all sequences)
  2436. no seq(any), seq(float)
  2437. # Nope, seq[any] includes types that are not seq[float] (e.g. seq[int])
  2438. yes seq(int|string), seq(any)
  2439. # Sure
  2440. yes seq(int&string), seq(any)
  2441. # Again
  2442. yes seq(int&string), seq(int)
  2443. # A bit more complicated
  2444. # seq[int&string] is not a real type, but it's analogous to
  2445. # seq[Sortable and Iterable], which is certainly a subset of seq[Sortable]
  2446. no seq(int|string), seq(int|float)
  2447. # Nope, seq[string] is not included in not included in
  2448. # the seq[int|float] set
  2449. no seq(!(int|string)), seq(string)
  2450. # A sequence that is neither seq[int] or seq[string]
  2451. # is obviously not seq[string]
  2452. no seq(!int), seq(number)
  2453. # Now your head should start to hurt a bit
  2454. # A sequence that is not seq[int] is not necessarily a number sequence
  2455. # it could well be seq[string] for example
  2456. yes seq(!(int|string)), seq(!string)
  2457. # all sequnece types besides seq[int] and seq[string]
  2458. # are subset of all sequence types that are not seq[string]
  2459. no seq(!(int|string)), seq(!(string|TFoo))
  2460. # Nope, seq[TFoo] is included in the first set, but not in the second
  2461. no seq(!string), seq(!number)
  2462. # Nope, seq[int] in included in the first set, but not in the second
  2463. yes seq(!number), seq(any)
  2464. yes seq(!int), seq(any)
  2465. no seq(any), seq(!any)
  2466. no seq(!int), seq(!any)
  2467. yes int, ordinal
  2468. no string, ordinal