first steps of making 'opt' a first class type for Nim

11 files changed, 147 insertions, 17 deletions

diff --git a/compiler/ast.nim b/compiler/ast.nim
index 8237c161e..0a87e9615 100644
--- a/compiler/ast.nim
+++ b/compiler/ast.nim
@@ -354,7 +354,7 @@ type
     tyInt, tyInt8, tyInt16, tyInt32, tyInt64, # signed integers
     tyFloat, tyFloat32, tyFloat64, tyFloat128,
     tyUInt, tyUInt8, tyUInt16, tyUInt32, tyUInt64,
-    tyUnused0, tyUnused1, tyUnused2,
+    tyOptAsRef, tyUnused1, tyUnused2,
     tyVarargs,
     tyUnused,
     tyProxy # used as errornous type (for idetools)
diff --git a/compiler/ccgtrav.nim b/compiler/ccgtrav.nim
index fa228ff04..4215a84b1 100644
--- a/compiler/ccgtrav.nim
+++ b/compiler/ccgtrav.nim
@@ -121,7 +121,8 @@ proc genTraverseProc(m: BModule, origTyp: PType; sig: SigHash;
   var c: TTraversalClosure
   var p = newProc(nil, m)
   result = "Marker_" & getTypeName(m, origTyp, sig)
-  let typ = origTyp.skipTypes(abstractInst)
+  var typ = origTyp.skipTypes(abstractInst)
+  if typ.kind == tyOpt: typ = optLowering(typ)
 
   case reason
   of tiNew: c.visitorFrmt = "#nimGCvisit((void*)$1, op);$n"
diff --git a/compiler/ccgtypes.nim b/compiler/ccgtypes.nim
index 1ca001b42..254b13429 100644
--- a/compiler/ccgtypes.nim
+++ b/compiler/ccgtypes.nim
@@ -183,7 +183,7 @@ proc mapType(typ: PType): TCTypeKind =
       of 8: result = ctInt64
       else: internalError("mapType")
   of tyRange: result = mapType(typ.sons[0])
-  of tyPtr, tyVar, tyRef:
+  of tyPtr, tyVar, tyRef, tyOptAsRef:
     var base = skipTypes(typ.lastSon, typedescInst)
     case base.kind
     of tyOpenArray, tyArray, tyVarargs: result = ctPtrToArray
@@ -194,6 +194,13 @@ proc mapType(typ: PType): TCTypeKind =
     else: result = ctPtr
   of tyPointer: result = ctPtr
   of tySequence: result = ctNimSeq
+  of tyOpt:
+    case optKind(typ)
+    of oBool: result = ctStruct
+    of oNil, oPtr: result = ctPtr
+    of oEnum:
+      # The 'nil' value is always negative, so we always use a signed integer
+      result = if getSize(typ.sons[0]) == 8: ctInt64 else: ctInt32
   of tyProc: result = if typ.callConv != ccClosure: ctProc else: ctStruct
   of tyString: result = ctNimStr
   of tyCString: result = ctCString
@@ -350,7 +357,7 @@ proc getTypeForward(m: BModule, typ: PType; sig: SigHash): Rope =
   if result != nil: return
   result = getTypePre(m, typ, sig)
   if result != nil: return
-  let concrete = typ.skipTypes(abstractInst)
+  let concrete = typ.skipTypes(abstractInst + {tyOpt})
   case concrete.kind
   of tySequence, tyTuple, tyObject:
     result = getTypeName(m, typ, sig)
@@ -376,6 +383,12 @@ proc getTypeDescWeak(m: BModule; t: PType; check: var IntSet): Rope =
   of tySequence:
     result = getTypeForward(m, t, hashType(t)) & "*"
     pushType(m, t)
+  of tyOpt:
+    if optKind(etB) == oPtr:
+      result = getTypeForward(m, t, hashType(t)) & "*"
+      pushType(m, t)
+    else:
+      result = getTypeDescAux(m, t, check)
   else:
     result = getTypeDescAux(m, t, check)
 
@@ -506,7 +519,7 @@ proc genRecordFieldsAux(m: BModule, n: PNode,
       if fieldType.kind == tyArray and tfUncheckedArray in fieldType.flags:
         addf(result, "$1 $2[SEQ_DECL_SIZE];$n",
             [getTypeDescAux(m, fieldType.elemType, check), sname])
-      elif fieldType.kind == tySequence:
+      elif fieldType.kind in {tySequence, tyOpt}:
         # we need to use a weak dependency here for trecursive_table.
         addf(result, "$1 $2;$n", [getTypeDescWeak(m, field.loc.t, check), sname])
       elif field.bitsize != 0:
@@ -625,7 +638,7 @@ proc getTypeDescAux(m: BModule, origTyp: PType, check: var IntSet): Rope =
     excl(check, t.id)
     return
   case t.kind
-  of tyRef, tyPtr, tyVar:
+  of tyRef, tyOptAsRef, tyPtr, tyVar:
     var star = if t.kind == tyVar and tfVarIsPtr notin origTyp.flags and
                     compileToCpp(m): "&" else: "*"
     var et = origTyp.skipTypes(abstractInst).lastSon
@@ -652,6 +665,21 @@ proc getTypeDescAux(m: BModule, origTyp: PType, check: var IntSet): Rope =
       result = name & "*" & star
       m.typeCache[sig] = result
       pushType(m, et)
+    of tyOpt:
+      if etB.sons[0].kind in {tyObject, tyTuple}:
+        let name = getTypeForward(m, et, hashType et)
+        result = name & "*" & star
+        m.typeCache[sig] = result
+        pushType(m, et)
+      elif optKind(etB) == oBool:
+        let name = getTypeForward(m, et, hashType et)
+        result = name & "*"
+        m.typeCache[sig] = result
+        pushType(m, et)
+      else:
+        # else we have a strong dependency  :-(
+        result = getTypeDescAux(m, et, check) & star
+        m.typeCache[sig] = result
     else:
       # else we have a strong dependency  :-(
       result = getTypeDescAux(m, et, check) & star
@@ -727,6 +755,38 @@ proc getTypeDescAux(m: BModule, origTyp: PType, check: var IntSet): Rope =
       else:
         result = rope("TGenericSeq")
     add(result, "*")
+  of tyOpt:
+    result = cacheGetType(m.typeCache, sig)
+    if result == nil:
+      case optKind(t)
+      of oBool:
+        result = cacheGetType(m.forwTypeCache, sig)
+        if result == nil:
+          result = getTypeName(m, origTyp, sig)
+          addf(m.s[cfsForwardTypes], getForwardStructFormat(m),
+              [structOrUnion(t), result])
+          m.forwTypeCache[sig] = result
+        appcg(m, m.s[cfsSeqTypes], "struct $2 {$n" &
+           "  NIM_BOOL Field0;$n" &
+           "  $1 Field1;$n" &
+           "};$n", [getTypeDescAux(m, t.sons[0], check), result])
+      of oPtr:
+        let et = t.sons[0]
+        if et.kind in {tyTuple, tyObject}:
+          let name = getTypeForward(m, et, hashType et)
+          result = name & "*"
+          pushType(m, et)
+        else:
+          result = getTypeDescAux(m, t.sons[0], check) & "*"
+      of oNil:
+        result = getTypeDescAux(m, t.sons[0], check)
+      of oEnum:
+        result = getTypeName(m, origTyp, sig)
+        if getSize(t.sons[0]) == 8:
+          addf(m.s[cfsTypes], "typedef NI64 $1;$n", [result])
+        else:
+          addf(m.s[cfsTypes], "typedef NI32 $1;$n", [result])
+      m.typeCache[sig] = result
   of tyArray:
     var n: BiggestInt = lengthOrd(t)
     if n <= 0: n = 1   # make an array of at least one element
@@ -1114,6 +1174,8 @@ proc genDeepCopyProc(m: BModule; s: PSym; result: Rope) =
 proc genTypeInfo(m: BModule, t: PType): Rope =
   let origType = t
   var t = skipTypes(origType, irrelevantForBackend + tyUserTypeClasses)
+  if t.kind == tyOpt:
+    return genTypeInfo(m, optLowering(t))
 
   let sig = hashType(origType)
   result = m.typeInfoMarker.getOrDefault(sig)
@@ -1159,7 +1221,7 @@ proc genTypeInfo(m: BModule, t: PType): Rope =
     else:
       let x = fakeClosureType(t.owner)
       genTupleInfo(m, x, x, result)
-  of tySequence, tyRef:
+  of tySequence, tyRef, tyOptAsRef:
     genTypeInfoAux(m, t, t, result)
     if gSelectedGC >= gcMarkAndSweep:
       let markerProc = genTraverseProc(m, origType, sig, tiNew)
diff --git a/compiler/ccgutils.nim b/compiler/ccgutils.nim
index 315efbd64..4cfeeb3c3 100644
--- a/compiler/ccgutils.nim
+++ b/compiler/ccgutils.nim
@@ -157,7 +157,7 @@ proc getUniqueType*(key: PType): PType =
       else:
         # ugh, we need the canon here:
         result = slowSearch(key, k)
-    of tyUnused, tyUnused0, tyUnused1, tyUnused2: internalError("getUniqueType")
+    of tyUnused, tyOptAsRef, tyUnused1, tyUnused2: internalError("getUniqueType")
 
 proc makeSingleLineCString*(s: string): string =
   result = "\""
diff --git a/compiler/condsyms.nim b/compiler/condsyms.nim
index dc97e3648..9863e90bb 100644
--- a/compiler/condsyms.nim
+++ b/compiler/condsyms.nim
@@ -107,3 +107,4 @@ proc initDefines*() =
   defineSymbol("nimDistros")
   defineSymbol("nimHasCppDefine")
   defineSymbol("nimGenericInOutFlags")
+  when false: defineSymbol("nimHasOpt")
diff --git a/compiler/jsgen.nim b/compiler/jsgen.nim
index 0f8d763c2..7b1c43817 100644
--- a/compiler/jsgen.nim
+++ b/compiler/jsgen.nim
@@ -202,7 +202,7 @@ proc mapType(typ: PType): TJSTypeKind =
     else: result = etyNone
   of tyProc: result = etyProc
   of tyCString: result = etyString
-  of tyUnused, tyUnused0, tyUnused1, tyUnused2: internalError("mapType")
+  of tyUnused, tyOptAsRef, tyUnused1, tyUnused2: internalError("mapType")
 
 proc mapType(p: PProc; typ: PType): TJSTypeKind =
   if p.target == targetPHP: result = etyObject
diff --git a/compiler/semasgn.nim b/compiler/semasgn.nim
index b51d7167b..dbb2a140b 100644
--- a/compiler/semasgn.nim
+++ b/compiler/semasgn.nim
@@ -229,7 +229,7 @@ proc liftBodyAux(c: var TLiftCtx; t: PType; body, x, y: PNode) =
   of tyOrdinal, tyRange, tyInferred,
      tyGenericInst, tyStatic, tyVar, tyAlias:
     liftBodyAux(c, lastSon(t), body, x, y)
-  of tyUnused, tyUnused0, tyUnused1, tyUnused2: internalError("liftBodyAux")
+  of tyUnused, tyOptAsRef, tyUnused1, tyUnused2: internalError("liftBodyAux")
 
 proc newProcType(info: TLineInfo; owner: PSym): PType =
   result = newType(tyProc, owner)
diff --git a/compiler/semtypes.nim b/compiler/semtypes.nim
index c44f94db6..fbb5d0b6b 100644
--- a/compiler/semtypes.nim
+++ b/compiler/semtypes.nim
@@ -1393,6 +1393,7 @@ proc semTypeNode(c: PContext, n: PNode, prev: PType): PType =
     of mSet: result = semSet(c, n, prev)
     of mOrdinal: result = semOrdinal(c, n, prev)
     of mSeq: result = semContainer(c, n, tySequence, "seq", prev)
+    of mOpt: result = semContainer(c, n, tyOpt, "opt", prev)
     of mVarargs: result = semVarargs(c, n, prev)
     of mTypeDesc: result = makeTypeDesc(c, semTypeNode(c, n[1], nil))
     of mExpr:
diff --git a/compiler/types.nim b/compiler/types.nim
index 12c10a4a3..3dbf6fd18 100644
--- a/compiler/types.nim
+++ b/compiler/types.nim
@@ -45,8 +45,6 @@ type
 
 proc equalParams*(a, b: PNode): TParamsEquality
   # returns whether the parameter lists of the procs a, b are exactly the same
-proc isOrdinalType*(t: PType): bool
-proc enumHasHoles*(t: PType): bool
 
 const
   # TODO: Remove tyTypeDesc from each abstractX and (where necessary)
@@ -129,7 +127,7 @@ proc elemType*(t: PType): PType =
   else: result = t.lastSon
   assert(result != nil)
 
-proc isOrdinalType(t: PType): bool =
+proc isOrdinalType*(t: PType): bool =
   assert(t != nil)
   const
     # caution: uint, uint64 are no ordinal types!
@@ -137,7 +135,7 @@ proc isOrdinalType(t: PType): bool =
     parentKinds = {tyRange, tyOrdinal, tyGenericInst, tyAlias, tyDistinct}
   t.kind in baseKinds or (t.kind in parentKinds and isOrdinalType(t.sons[0]))
 
-proc enumHasHoles(t: PType): bool =
+proc enumHasHoles*(t: PType): bool =
   var b = t
   while b.kind in {tyRange, tyGenericInst, tyAlias}: b = b.sons[0]
   result = b.kind == tyEnum and tfEnumHasHoles in b.flags
@@ -995,7 +993,7 @@ proc sameTypeAux(x, y: PType, c: var TSameTypeClosure): bool =
     cycleCheck()
     result = sameTypeAux(a.lastSon, b.lastSon, c)
   of tyNone: result = false
-  of tyUnused, tyUnused0, tyUnused1, tyUnused2: internalError("sameFlags")
+  of tyUnused, tyOptAsRef, tyUnused1, tyUnused2: internalError("sameFlags")
 
 proc sameBackendType*(x, y: PType): bool =
   var c = initSameTypeClosure()
@@ -1176,7 +1174,7 @@ proc typeAllowedAux(marker: var IntSet, typ: PType, kind: TSymKind,
     # for now same as error node; we say it's a valid type as it should
     # prevent cascading errors:
     result = nil
-  of tyUnused, tyUnused0, tyUnused1, tyUnused2: internalError("typeAllowedAux")
+  of tyUnused, tyOptAsRef, tyUnused1, tyUnused2: internalError("typeAllowedAux")
 
 proc typeAllowed*(t: PType, kind: TSymKind): PType =
   # returns 'nil' on success and otherwise the part of the type that is
@@ -1187,6 +1185,63 @@ proc typeAllowed*(t: PType, kind: TSymKind): PType =
 proc align(address, alignment: BiggestInt): BiggestInt =
   result = (address + (alignment - 1)) and not (alignment - 1)
 
+type
+  OptKind* = enum  ## What to map 'opt T' to internally.
+    oBool      ## opt[T] requires an additional 'bool' field
+    oNil       ## opt[T] has no overhead since 'nil'
+               ## is available
+    oEnum      ## We can use some enum value that is not yet
+               ## used for opt[T]
+    oPtr       ## opt[T] actually introduces a hidden pointer
+               ## in order for the type recursion to work
+
+proc optKind*(typ: PType): OptKind =
+  ## return true iff 'opt[T]' can be mapped to 'T' internally
+  ## because we have a 'nil' value available:
+  assert typ.kind == tyOpt
+  case typ.sons[0].skipTypes(abstractInst).kind
+  of tyRef, tyPtr, tyProc:
+    result = oNil
+  of tyArray, tyObject, tyTuple:
+    result = oPtr
+  of tyBool: result = oEnum
+  of tyEnum:
+    assert(typ.n.sons[0].kind == nkSym)
+    if typ.n.sons[0].sym.position != low(int):
+      result = oEnum
+    else:
+      result = oBool
+  else:
+    result = oBool
+
+proc optLowering*(typ: PType): PType =
+  case optKind(typ)
+  of oNil: result = typ.sons[0]
+  of oPtr:
+    result = newType(tyOptAsRef, typ.owner)
+    result.rawAddSon typ.sons[0]
+  of oBool:
+    result = newType(tyTuple, typ.owner)
+    result.rawAddSon newType(tyBool, typ.owner)
+    result.rawAddSon typ.sons[0]
+  of oEnum:
+    if lastOrd(typ) + 1 < `shl`(BiggestInt(1), 32):
+      result = newType(tyInt32, typ.owner)
+    else:
+      result = newType(tyInt64, typ.owner)
+
+proc optEnumValue*(typ: PType): BiggestInt =
+  assert typ.kind == tyOpt
+  assert optKind(typ) == oEnum
+  let elem = typ.sons[0].skipTypes(abstractInst).kind
+  if elem == tyBool:
+    result = 2
+  else:
+    assert elem == tyEnum
+    assert typ.n.sons[0].sym.position != low(int)
+    result = typ.n.sons[0].sym.position - 1
+
+
 const
   szNonConcreteType* = -3
   szIllegalRecursion* = -2
@@ -1341,6 +1396,14 @@ proc computeSizeAux(typ: PType, a: var BiggestInt): BiggestInt =
   of tyStatic:
     result = if typ.n != nil: computeSizeAux(typ.lastSon, a)
              else: szUnknownSize
+  of tyOpt:
+    case optKind(typ)
+    of oBool: result = computeSizeAux(lastSon(typ), a) + 1
+    of oEnum:
+      if lastOrd(typ) + 1 < `shl`(BiggestInt(1), 32): result = 4
+      else: result = 8
+    of oNil: result = computeSizeAux(lastSon(typ), a)
+    of oPtr: result = ptrSize
   else:
     #internalError("computeSizeAux()")
     result = szUnknownSize
diff --git a/compiler/vmdeps.nim b/compiler/vmdeps.nim
index 12fc455bd..2b3cfeeeb 100644
--- a/compiler/vmdeps.nim
+++ b/compiler/vmdeps.nim
@@ -314,7 +314,7 @@ proc mapTypeToAstX(t: PType; info: TLineInfo;
       result.add atomicType("static", mNone)
       if t.n != nil:
         result.add t.n.copyTree
-  of tyUnused, tyUnused0, tyUnused1, tyUnused2: internalError("mapTypeToAstX")
+  of tyUnused, tyOptAsRef, tyUnused1, tyUnused2: internalError("mapTypeToAstX")
 
 proc opMapTypeToAst*(t: PType; info: TLineInfo): PNode =
   result = mapTypeToAstX(t, info, false, true)
diff --git a/compiler/vmgen.nim b/compiler/vmgen.nim
index 6f9d70495..ee9af7de2 100644
--- a/compiler/vmgen.nim
+++ b/compiler/vmgen.nim
@@ -1537,6 +1537,8 @@ proc getNullValue(typ: PType, info: TLineInfo): PNode =
       addSon(result, getNullValue(t.sons[i], info))
   of tySet:
     result = newNodeIT(nkCurly, info, t)
+  of tyOpt:
+    result = newNodeIT(nkNilLit, info, t)
   else:
     globalError(info, "cannot create null element for: " & $t.kind)