Type equality

Nim uses structural type equivalence for most types. Only for objects, enumerations and distinct types name equivalence is used. The following algorithm, in pseudo-code, determines type equality:

proc typeEqualsAux(a, b: PType,
                   s: var HashSet[(PType, PType)]): bool =
  if (a,b) in s: return true
  incl(s, (a,b))
  if a.kind == b.kind:
    case a.kind
    of int, intXX, float, floatXX, char, string, cstring, pointer,
        bool, nil, void:
      # leaf type: kinds identical; nothing more to check
      result = true
    of ref, ptr, var, set, seq, openarray:
      result = typeEqualsAux(a.baseType, b.baseType, s)
    of range:
      result = typeEqualsAux(a.baseType, b.baseType, s) and
        (a.rangeA == b.rangeA) and (a.rangeB == b.rangeB)
    of array:
      result = typeEqualsAux(a.baseType, b.baseType, s) and
               typeEqualsAux(a.indexType, b.indexType, s)
    of tuple:
      if a.tupleLen == b.tupleLen:
        for i in 0..a.tupleLen-1:
          if not typeEqualsAux(a[i], b[i], s): return false
        result = true
    of object, enum, distinct:
      result = a == b
    of proc:
      result = typeEqualsAux(a.parameterTuple, b.parameterTuple, s) and
               typeEqualsAux(a.resultType, b.resultType, s) and
               a.callingConvention == b.callingConvention
proc typeEquals(a, b: PType): bool =
  var s: HashSet[(PType, PType)] = {}
  result = typeEqualsAux(a, b, s)

Since types are graphs which can have cycles, the above algorithm needs an auxiliary set s to detect this case.