diff options
author | Andreas Rumpf <rumpf_a@web.de> | 2017-10-02 08:31:38 +0200 |
---|---|---|
committer | Andreas Rumpf <rumpf_a@web.de> | 2017-10-02 08:31:38 +0200 |
commit | e9243a16167b24899d4fcf051f3252b3a5804811 (patch) | |
tree | dc4733a6f178d4f04ee4da33c50ca807eb7e9dd0 /lib | |
parent | fc7961d4ccd31ab6e7eabbeb7aa22b5488924b4f (diff) | |
parent | 02ff5f596c330b68927f843814ecb9b86c2eee67 (diff) | |
download | Nim-e9243a16167b24899d4fcf051f3252b3a5804811.tar.gz |
Merge branch 'devel' into araq
Diffstat (limited to 'lib')
-rw-r--r-- | lib/core/macros.nim | 10 | ||||
-rw-r--r-- | lib/core/typeinfo.nim | 1 | ||||
-rw-r--r-- | lib/genode_cpp/threads.h | 12 | ||||
-rw-r--r-- | lib/impure/db_sqlite.nim | 3 | ||||
-rw-r--r-- | lib/js/jsffi.nim | 6 | ||||
-rw-r--r-- | lib/nimbase.h | 10 | ||||
-rw-r--r-- | lib/packages/docutils/highlite.nim | 4 | ||||
-rw-r--r-- | lib/pure/basic2d.nim | 855 | ||||
-rw-r--r-- | lib/pure/basic3d.nim | 1040 | ||||
-rw-r--r-- | lib/pure/collections/sets.nim | 98 | ||||
-rw-r--r-- | lib/pure/json.nim | 57 | ||||
-rw-r--r-- | lib/pure/nativesockets.nim | 4 | ||||
-rw-r--r-- | lib/pure/options.nim | 81 | ||||
-rw-r--r-- | lib/pure/osproc.nim | 14 | ||||
-rw-r--r-- | lib/pure/strutils.nim | 2 | ||||
-rw-r--r-- | lib/pure/unittest.nim | 83 | ||||
-rw-r--r-- | lib/system.nim | 30 | ||||
-rw-r--r-- | lib/system/assign.nim | 33 | ||||
-rw-r--r-- | lib/system/channels.nim | 2 | ||||
-rw-r--r-- | lib/system/deepcopy.nim | 2 | ||||
-rw-r--r-- | lib/system/gc.nim | 18 | ||||
-rw-r--r-- | lib/system/gc2.nim | 510 | ||||
-rw-r--r-- | lib/system/gc_common.nim | 20 | ||||
-rw-r--r-- | lib/system/gc_ms.nim | 14 | ||||
-rw-r--r-- | lib/system/hti.nim | 15 | ||||
-rw-r--r-- | lib/system/mmdisp.nim | 6 | ||||
-rw-r--r-- | lib/system/nimscript.nim | 9 | ||||
-rw-r--r-- | lib/system/sysstr.nim | 45 | ||||
-rw-r--r-- | lib/system/threads.nim | 9 |
29 files changed, 545 insertions, 2448 deletions
diff --git a/lib/core/macros.nim b/lib/core/macros.nim index e88002c7b..8c70d2b47 100644 --- a/lib/core/macros.nim +++ b/lib/core/macros.nim @@ -75,7 +75,8 @@ type nnkClosure, nnkGotoState, nnkState, - nnkBreakState + nnkBreakState, + nnkFuncDef NimNodeKinds* = set[NimNodeKind] NimTypeKind* = enum # some types are no longer used, see ast.nim @@ -96,14 +97,14 @@ type ntyError, ntyBuiltinTypeClass, ntyUserTypeClass, ntyUserTypeClassInst, ntyCompositeTypeClass, ntyInferred, ntyAnd, ntyOr, ntyNot, - ntyAnything, ntyStatic, ntyFromExpr, ntyFieldAccessor, ntyVoid + ntyAnything, ntyStatic, ntyFromExpr, ntyOpt, ntyVoid TNimTypeKinds* {.deprecated.} = set[NimTypeKind] NimSymKind* = enum nskUnknown, nskConditional, nskDynLib, nskParam, nskGenericParam, nskTemp, nskModule, nskType, nskVar, nskLet, nskConst, nskResult, - nskProc, nskMethod, nskIterator, + nskProc, nskFunc, nskMethod, nskIterator, nskConverter, nskMacro, nskTemplate, nskField, nskEnumField, nskForVar, nskLabel, nskStub @@ -843,7 +844,8 @@ proc last*(node: NimNode): NimNode {.compileTime.} = node[<node.len] const - RoutineNodes* = {nnkProcDef, nnkMethodDef, nnkDo, nnkLambda, nnkIteratorDef, nnkTemplateDef, nnkConverterDef} + RoutineNodes* = {nnkProcDef, nnkFuncDef, nnkMethodDef, nnkDo, nnkLambda, + nnkIteratorDef, nnkTemplateDef, nnkConverterDef} AtomicNodes* = {nnkNone..nnkNilLit} CallNodes* = {nnkCall, nnkInfix, nnkPrefix, nnkPostfix, nnkCommand, nnkCallStrLit, nnkHiddenCallConv} diff --git a/lib/core/typeinfo.nim b/lib/core/typeinfo.nim index 72b139202..16580b318 100644 --- a/lib/core/typeinfo.nim +++ b/lib/core/typeinfo.nim @@ -54,6 +54,7 @@ type akUInt16 = 42, ## any represents an unsigned in16 akUInt32 = 43, ## any represents an unsigned int32 akUInt64 = 44, ## any represents an unsigned int64 +# akOpt = 44+18 ## the builtin 'opt' type. Any* = object ## can represent any nim value; NOTE: the wrapped ## value can be modified with its wrapper! This means diff --git a/lib/genode_cpp/threads.h b/lib/genode_cpp/threads.h index 043f808f1..a7cb2f17b 100644 --- a/lib/genode_cpp/threads.h +++ b/lib/genode_cpp/threads.h @@ -31,8 +31,12 @@ struct Nim::SysThread void entry() override { (_func)(_arg); } - Thread(Genode::Env &env, Genode::size_t stack_size, Entry func, void *arg) - : Genode::Thread(env, "nim-thread", stack_size), _func(func), _arg(arg) + Thread(Genode::Env &env, Genode::size_t stack_size, Entry func, void *arg, int affinity) + : Genode::Thread(env, "nim-thread", stack_size, + env.cpu().affinity_space().location_of_index(affinity), + Genode::Cpu_session::Weight(Genode::Cpu_session::Weight::DEFAULT_WEIGHT-1), + env.cpu()), + _func(func), _arg(arg) { Genode::Thread::start(); } @@ -40,8 +44,8 @@ struct Nim::SysThread Genode::Constructible<Thread> _thread; - void initThread(Genode::Env *env, Genode::size_t stack_size, Entry func, void *arg) { - _thread.construct(*env, stack_size, func, arg); } + void initThread(Genode::Env *env, Genode::size_t stack_size, Entry func, void *arg, int aff) { + _thread.construct(*env, stack_size, func, arg, aff); } void joinThread() { _thread->join(); } diff --git a/lib/impure/db_sqlite.nim b/lib/impure/db_sqlite.nim index 1633d48f7..53dafdda7 100644 --- a/lib/impure/db_sqlite.nim +++ b/lib/impure/db_sqlite.nim @@ -129,7 +129,8 @@ proc tryExec*(db: DbConn, query: SqlQuery, var q = dbFormat(query, args) var stmt: sqlite3.Pstmt if prepare_v2(db, q, q.len.cint, stmt, nil) == SQLITE_OK: - if step(stmt) == SQLITE_DONE: + let x = step(stmt) + if x in {SQLITE_DONE, SQLITE_ROW}: result = finalize(stmt) == SQLITE_OK proc exec*(db: DbConn, query: SqlQuery, args: varargs[string, `$`]) {. diff --git a/lib/js/jsffi.nim b/lib/js/jsffi.nim index 0d359d9e6..13eb1e759 100644 --- a/lib/js/jsffi.nim +++ b/lib/js/jsffi.nim @@ -300,7 +300,7 @@ macro `.()`*[K: string | cstring, V: proc](obj: JsAssoc[K, V], result = quote do: (`dotOp`(`obj`, `field`))() for elem in args: - result[0].add elem + result.add elem # Iterators: @@ -471,7 +471,7 @@ macro bindMethod*(procedure: typed): auto = # construct the `this` parameter: thisQuote = quote do: var `this` {. nodecl, importc .} : `thisType` - call = newNimNode(nnkCall).add(rawProc[0], thisQuote[0][0][0][0]) + call = newNimNode(nnkCall).add(rawProc[0], thisQuote[0][0][0]) # construct the procedure call inside the method if args.len > 2: for idx in 2..args.len-1: @@ -483,6 +483,6 @@ macro bindMethod*(procedure: typed): auto = params, rawProc[4], rawProc[5], - newTree(nnkStmtList, thisQuote[0], call) + newTree(nnkStmtList, thisQuote, call) ) result = body diff --git a/lib/nimbase.h b/lib/nimbase.h index 70391024f..34a2e43e7 100644 --- a/lib/nimbase.h +++ b/lib/nimbase.h @@ -373,11 +373,13 @@ static N_INLINE(NI32, float32ToInt32)(float x) { #define float64ToInt64(x) ((NI64) (x)) +#define NIM_STRLIT_FLAG ((NU)(1) << ((NIM_INTBITS) - 2)) /* This has to be the same as system.strlitFlag! */ + #define STRING_LITERAL(name, str, length) \ - static const struct { \ - TGenericSeq Sup; \ - NIM_CHAR data[(length) + 1]; \ - } name = {{length, length}, str} + static const struct { \ + TGenericSeq Sup; \ + NIM_CHAR data[(length) + 1]; \ + } name = {{length, (NI) ((NU)length | NIM_STRLIT_FLAG)}, str} typedef struct TStringDesc* string; diff --git a/lib/packages/docutils/highlite.nim b/lib/packages/docutils/highlite.nim index 06b90768c..1d396d9e0 100644 --- a/lib/packages/docutils/highlite.nim +++ b/lib/packages/docutils/highlite.nim @@ -58,8 +58,8 @@ const "interface", "is", "isnot", "iterator", "let", "macro", "method", "mixin", "mod", "nil", "not", "notin", "object", "of", "or", "out", "proc", "ptr", "raise", "ref", "return", "shl", "shr", "static", - "template", "try", "tuple", "type", "using", "var", "when", "while", "with", - "without", "xor", "yield"] + "template", "try", "tuple", "type", "using", "var", "when", "while", + "xor", "yield"] proc getSourceLanguage*(name: string): SourceLanguage = for i in countup(succ(low(SourceLanguage)), high(SourceLanguage)): diff --git a/lib/pure/basic2d.nim b/lib/pure/basic2d.nim deleted file mode 100644 index 31b3814d6..000000000 --- a/lib/pure/basic2d.nim +++ /dev/null @@ -1,855 +0,0 @@ -# -# -# Nim's Runtime Library -# (c) Copyright 2013 Robert Persson -# -# See the file "copying.txt", included in this -# distribution, for details about the copyright. -# - -import math -import strutils - - -## Basic 2d support with vectors, points, matrices and some basic utilities. -## Vectors are implemented as direction vectors, ie. when transformed with a matrix -## the translation part of matrix is ignored. -## Operators `+` , `-` , `*` , `/` , `+=` , `-=` , `*=` and `/=` are implemented for vectors and scalars. -## -## Quick start example: -## -## .. code-block:: nim -## -## # Create a matrix which first rotates, then scales and at last translates -## -## var m:Matrix2d=rotate(DEG90) & scale(2.0) & move(100.0,200.0) -## -## # Create a 2d point at (100,0) and a vector (5,2) -## -## var pt:Point2d=point2d(100.0,0.0) -## -## var vec:Vector2d=vector2d(5.0,2.0) -## -## -## pt &= m # transforms pt in place -## -## var pt2:Point2d=pt & m #concatenates pt with m and returns a new point -## -## var vec2:Vector2d=vec & m #concatenates vec with m and returns a new vector - - -const - DEG360* = PI * 2.0 - ## 360 degrees in radians. - DEG270* = PI * 1.5 - ## 270 degrees in radians. - DEG180* = PI - ## 180 degrees in radians. - DEG90* = PI / 2.0 - ## 90 degrees in radians. - DEG60* = PI / 3.0 - ## 60 degrees in radians. - DEG45* = PI / 4.0 - ## 45 degrees in radians. - DEG30* = PI / 6.0 - ## 30 degrees in radians. - DEG15* = PI / 12.0 - ## 15 degrees in radians. - RAD2DEGCONST = 180.0 / PI - ## used internally by DegToRad and RadToDeg - -type - Matrix2d* = object - ## Implements a row major 2d matrix, which means - ## transformations are applied the order they are concatenated. - ## The rightmost column of the 3x3 matrix is left out since normally - ## not used for geometric transformations in 2d. - ax*,ay*,bx*,by*,tx*,ty*:float - Point2d* = object - ## Implements a non-homogeneous 2d point stored as - ## an `x` coordinate and an `y` coordinate. - x*,y*:float - Vector2d* = object - ## Implements a 2d **direction vector** stored as - ## an `x` coordinate and an `y` coordinate. Direction vector means, - ## that when transforming a vector with a matrix, the translational - ## part of the matrix is ignored. - x*,y*:float -{.deprecated: [TMatrix2d: Matrix2d, TPoint2d: Point2d, TVector2d: Vector2d].} - - -# Some forward declarations... -proc matrix2d*(ax,ay,bx,by,tx,ty:float):Matrix2d {.noInit.} - ## Creates a new matrix. - ## `ax`,`ay` is the local x axis - ## `bx`,`by` is the local y axis - ## `tx`,`ty` is the translation -proc vector2d*(x,y:float):Vector2d {.noInit,inline.} - ## Returns a new vector (`x`,`y`) -proc point2d*(x,y:float):Point2d {.noInit,inline.} - ## Returns a new point (`x`,`y`) - - - -let - IDMATRIX*:Matrix2d=matrix2d(1.0,0.0,0.0,1.0,0.0,0.0) - ## Quick access to an identity matrix - ORIGO*:Point2d=point2d(0.0,0.0) - ## Quick access to point (0,0) - XAXIS*:Vector2d=vector2d(1.0,0.0) - ## Quick access to an 2d x-axis unit vector - YAXIS*:Vector2d=vector2d(0.0,1.0) - ## Quick access to an 2d y-axis unit vector - - -# *************************************** -# Private utils -# *************************************** - -proc rtos(val:float):string= - return formatFloat(val,ffDefault,0) - -proc safeArccos(v:float):float= - ## assumes v is in range 0.0-1.0, but clamps - ## the value to avoid out of domain errors - ## due to rounding issues - return arccos(clamp(v,-1.0,1.0)) - - -template makeBinOpVector(s) = - ## implements binary operators ``+``, ``-``, ``*`` and ``/`` for vectors - proc s*(a,b:Vector2d):Vector2d {.inline,noInit.} = vector2d(s(a.x,b.x),s(a.y,b.y)) - proc s*(a:Vector2d,b:float):Vector2d {.inline,noInit.} = vector2d(s(a.x,b),s(a.y,b)) - proc s*(a:float,b:Vector2d):Vector2d {.inline,noInit.} = vector2d(s(a,b.x),s(a,b.y)) - -template makeBinOpAssignVector(s)= - ## implements inplace binary operators ``+=``, ``-=``, ``/=`` and ``*=`` for vectors - proc s*(a:var Vector2d,b:Vector2d) {.inline.} = s(a.x,b.x) ; s(a.y,b.y) - proc s*(a:var Vector2d,b:float) {.inline.} = s(a.x,b) ; s(a.y,b) - - -# *************************************** -# Matrix2d implementation -# *************************************** - -proc setElements*(t:var Matrix2d,ax,ay,bx,by,tx,ty:float) {.inline.}= - ## Sets arbitrary elements in an existing matrix. - t.ax=ax - t.ay=ay - t.bx=bx - t.by=by - t.tx=tx - t.ty=ty - -proc matrix2d*(ax,ay,bx,by,tx,ty:float):Matrix2d = - result.setElements(ax,ay,bx,by,tx,ty) - -proc `&`*(a,b:Matrix2d):Matrix2d {.noInit.} = #concatenate matrices - ## Concatenates matrices returning a new matrix. - - # | a.AX a.AY 0 | | b.AX b.AY 0 | - # | a.BX a.BY 0 | * | b.BX b.BY 0 | - # | a.TX a.TY 1 | | b.TX b.TY 1 | - result.setElements( - a.ax * b.ax + a.ay * b.bx, - a.ax * b.ay + a.ay * b.by, - a.bx * b.ax + a.by * b.bx, - a.bx * b.ay + a.by * b.by, - a.tx * b.ax + a.ty * b.bx + b.tx, - a.tx * b.ay + a.ty * b.by + b.ty) - - -proc scale*(s:float):Matrix2d {.noInit.} = - ## Returns a new scale matrix. - result.setElements(s,0,0,s,0,0) - -proc scale*(s:float,org:Point2d):Matrix2d {.noInit.} = - ## Returns a new scale matrix using, `org` as scale origin. - result.setElements(s,0,0,s,org.x-s*org.x,org.y-s*org.y) - -proc stretch*(sx,sy:float):Matrix2d {.noInit.} = - ## Returns new a stretch matrix, which is a - ## scale matrix with non uniform scale in x and y. - result.setElements(sx,0,0,sy,0,0) - -proc stretch*(sx,sy:float,org:Point2d):Matrix2d {.noInit.} = - ## Returns a new stretch matrix, which is a - ## scale matrix with non uniform scale in x and y. - ## `org` is used as stretch origin. - result.setElements(sx,0,0,sy,org.x-sx*org.x,org.y-sy*org.y) - -proc move*(dx,dy:float):Matrix2d {.noInit.} = - ## Returns a new translation matrix. - result.setElements(1,0,0,1,dx,dy) - -proc move*(v:Vector2d):Matrix2d {.noInit.} = - ## Returns a new translation matrix from a vector. - result.setElements(1,0,0,1,v.x,v.y) - -proc rotate*(rad:float):Matrix2d {.noInit.} = - ## Returns a new rotation matrix, which - ## represents a rotation by `rad` radians - let - s=sin(rad) - c=cos(rad) - result.setElements(c,s,-s,c,0,0) - -proc rotate*(rad:float,org:Point2d):Matrix2d {.noInit.} = - ## Returns a new rotation matrix, which - ## represents a rotation by `rad` radians around - ## the origin `org` - let - s=sin(rad) - c=cos(rad) - result.setElements(c,s,-s,c,org.x+s*org.y-c*org.x,org.y-c*org.y-s*org.x) - -proc mirror*(v:Vector2d):Matrix2d {.noInit.} = - ## Returns a new mirror matrix, mirroring - ## around the line that passes through origo and - ## has the direction of `v` - let - sqx=v.x*v.x - sqy=v.y*v.y - nd=1.0/(sqx+sqy) #used to normalize invector - xy2=v.x*v.y*2.0*nd - sqd=nd*(sqx-sqy) - - if nd==Inf or nd==NegInf: - return IDMATRIX #mirroring around a zero vector is arbitrary=>just use identity - - result.setElements( - sqd,xy2, - xy2,-sqd, - 0.0,0.0) - -proc mirror*(org:Point2d,v:Vector2d):Matrix2d {.noInit.} = - ## Returns a new mirror matrix, mirroring - ## around the line that passes through `org` and - ## has the direction of `v` - let - sqx=v.x*v.x - sqy=v.y*v.y - nd=1.0/(sqx+sqy) #used to normalize invector - xy2=v.x*v.y*2.0*nd - sqd=nd*(sqx-sqy) - - if nd==Inf or nd==NegInf: - return IDMATRIX #mirroring around a zero vector is arbitrary=>just use identity - - result.setElements( - sqd,xy2, - xy2,-sqd, - org.x-org.y*xy2-org.x*sqd,org.y-org.x*xy2+org.y*sqd) - - - -proc skew*(xskew,yskew:float):Matrix2d {.noInit.} = - ## Returns a new skew matrix, which has its - ## x axis rotated `xskew` radians from the local x axis, and - ## y axis rotated `yskew` radians from the local y axis - result.setElements(cos(yskew),sin(yskew),-sin(xskew),cos(xskew),0,0) - - -proc `$`* (t:Matrix2d):string {.noInit.} = - ## Returns a string representation of the matrix - return rtos(t.ax) & "," & rtos(t.ay) & - "," & rtos(t.bx) & "," & rtos(t.by) & - "," & rtos(t.tx) & "," & rtos(t.ty) - -proc isUniform*(t:Matrix2d,tol=1.0e-6):bool= - ## Checks if the transform is uniform, that is - ## perpendicular axes of equal length, which means (for example) - ## it cannot transform a circle into an ellipse. - ## `tol` is used as tolerance for both equal length comparison - ## and perp. comparison. - - #dot product=0 means perpendicular coord. system: - if abs(t.ax*t.bx+t.ay*t.by)<=tol: - #subtract squared lengths of axes to check if uniform scaling: - if abs((t.ax*t.ax+t.ay*t.ay)-(t.bx*t.bx+t.by*t.by))<=tol: - return true - return false - -proc determinant*(t:Matrix2d):float= - ## Computes the determinant of the matrix. - - #NOTE: equivalent with perp.dot product for two 2d vectors - return t.ax*t.by-t.bx*t.ay - -proc isMirroring* (m:Matrix2d):bool= - ## Checks if the `m` is a mirroring matrix, - ## which means it will reverse direction of a curve transformed with it - return m.determinant<0.0 - -proc inverse*(m:Matrix2d):Matrix2d {.noInit.} = - ## Returns a new matrix, which is the inverse of the matrix - ## If the matrix is not invertible (determinant=0), an EDivByZero - ## will be raised. - let d=m.determinant - if d==0.0: - raise newException(DivByZeroError,"Cannot invert a zero determinant matrix") - - result.setElements( - m.by/d,-m.ay/d, - -m.bx/d,m.ax/d, - (m.bx*m.ty-m.by*m.tx)/d, - (m.ay*m.tx-m.ax*m.ty)/d) - -proc equals*(m1:Matrix2d,m2:Matrix2d,tol=1.0e-6):bool= - ## Checks if all elements of `m1`and `m2` is equal within - ## a given tolerance `tol`. - return - abs(m1.ax-m2.ax)<=tol and - abs(m1.ay-m2.ay)<=tol and - abs(m1.bx-m2.bx)<=tol and - abs(m1.by-m2.by)<=tol and - abs(m1.tx-m2.tx)<=tol and - abs(m1.ty-m2.ty)<=tol - -proc `=~`*(m1,m2:Matrix2d):bool= - ## Checks if `m1`and `m2` is approximately equal, using a - ## tolerance of 1e-6. - equals(m1,m2) - -proc isIdentity*(m:Matrix2d,tol=1.0e-6):bool= - ## Checks is a matrix is approximately an identity matrix, - ## using `tol` as tolerance for each element. - return equals(m,IDMATRIX,tol) - -proc apply*(m:Matrix2d,x,y:var float,translate=false)= - ## Applies transformation `m` onto `x`,`y`, optionally - ## using the translation part of the matrix. - if translate: # positional style transform - let newx=x*m.ax+y*m.bx+m.tx - y=x*m.ay+y*m.by+m.ty - x=newx - else: # delta style transform - let newx=x*m.ax+y*m.bx - y=x*m.ay+y*m.by - x=newx - - - -# *************************************** -# Vector2d implementation -# *************************************** -proc vector2d*(x,y:float):Vector2d = #forward decl. - result.x=x - result.y=y - -proc polarVector2d*(ang:float,len:float):Vector2d {.noInit.} = - ## Returns a new vector with angle `ang` and magnitude `len` - result.x=cos(ang)*len - result.y=sin(ang)*len - -proc slopeVector2d*(slope:float,len:float):Vector2d {.noInit.} = - ## Returns a new vector having slope (dy/dx) given by - ## `slope`, and a magnitude of `len` - let ang=arctan(slope) - result.x=cos(ang)*len - result.y=sin(ang)*len - -proc len*(v:Vector2d):float {.inline.}= - ## Returns the length of the vector. - sqrt(v.x*v.x+v.y*v.y) - -proc `len=`*(v:var Vector2d,newlen:float) {.noInit.} = - ## Sets the length of the vector, keeping its angle. - let fac=newlen/v.len - - if newlen==0.0: - v.x=0.0 - v.y=0.0 - return - - if fac==Inf or fac==NegInf: - #to short for float accuracy - #do as good as possible: - v.x=newlen - v.y=0.0 - else: - v.x*=fac - v.y*=fac - -proc sqrLen*(v:Vector2d):float {.inline.}= - ## Computes the squared length of the vector, which is - ## faster than computing the absolute length. - v.x*v.x+v.y*v.y - -proc angle*(v:Vector2d):float= - ## Returns the angle of the vector. - ## (The counter clockwise plane angle between posetive x axis and `v`) - result=arctan2(v.y,v.x) - if result<0.0: result+=DEG360 - -proc `$` *(v:Vector2d):string= - ## String representation of `v` - result=rtos(v.x) - result.add(",") - result.add(rtos(v.y)) - - -proc `&` *(v:Vector2d,m:Matrix2d):Vector2d {.noInit.} = - ## Concatenate vector `v` with a transformation matrix. - ## Transforming a vector ignores the translational part - ## of the matrix. - - # | AX AY 0 | - # | X Y 1 | * | BX BY 0 | - # | 0 0 1 | - result.x=v.x*m.ax+v.y*m.bx - result.y=v.x*m.ay+v.y*m.by - - -proc `&=`*(v:var Vector2d,m:Matrix2d) {.inline.}= - ## Applies transformation `m` onto `v` in place. - ## Transforming a vector ignores the translational part - ## of the matrix. - - # | AX AY 0 | - # | X Y 1 | * | BX BY 0 | - # | 0 0 1 | - let newx=v.x*m.ax+v.y*m.bx - v.y=v.x*m.ay+v.y*m.by - v.x=newx - - -proc tryNormalize*(v:var Vector2d):bool= - ## Modifies `v` to have a length of 1.0, keeping its angle. - ## If `v` has zero length (and thus no angle), it is left unmodified and - ## false is returned, otherwise true is returned. - - let mag=v.len - - if mag==0.0: - return false - - v.x/=mag - v.y/=mag - return true - - -proc normalize*(v:var Vector2d) {.inline.}= - ## Modifies `v` to have a length of 1.0, keeping its angle. - ## If `v` has zero length, an EDivByZero will be raised. - if not tryNormalize(v): - raise newException(DivByZeroError,"Cannot normalize zero length vector") - -proc transformNorm*(v:var Vector2d,t:Matrix2d)= - ## Applies a normal direction transformation `t` onto `v` in place. - ## The resulting vector is *not* normalized. Transforming a vector ignores the - ## translational part of the matrix. If the matrix is not invertible - ## (determinant=0), an EDivByZero will be raised. - - # transforming a normal is done by transforming - # by the transpose of the inverse of the original matrix - # this can be heavily optimized by precompute and inline - # | | AX AY 0 | ^-1| ^T - # | X Y 1 | * | | BX BY 0 | | - # | | 0 0 1 | | - let d=t.determinant - if(d==0.0): - raise newException(DivByZeroError,"Matrix is not invertible") - let newx = (t.by*v.x-t.ay*v.y)/d - v.y = (t.ax*v.y-t.bx*v.x)/d - v.x = newx - -proc transformInv*(v:var Vector2d,t:Matrix2d)= - ## Applies inverse of a transformation `t` to `v` in place. - ## This is faster than creating an inverse matrix and apply() it. - ## Transforming a vector ignores the translational part - ## of the matrix. If the matrix is not invertible (determinant=0), an EDivByZero - ## will be raised. - let d=t.determinant - - if(d==0.0): - raise newException(DivByZeroError,"Matrix is not invertible") - - let newx=(t.by*v.x-t.bx*v.y)/d - v.y = (t.ax*v.y-t.ay*v.x)/d - v.x = newx - -proc transformNormInv*(v:var Vector2d,t:Matrix2d)= - ## Applies an inverse normal direction transformation `t` onto `v` in place. - ## This is faster than creating an inverse - ## matrix and transformNorm(...) it. Transforming a vector ignores the - ## translational part of the matrix. - - # normal inverse transform is done by transforming - # by the inverse of the transpose of the inverse of the org. matrix - # which is equivalent with transforming with the transpose. - # | | | AX AY 0 |^-1|^T|^-1 | AX BX 0 | - # | X Y 1 | * | | | BX BY 0 | | | = | X Y 1 | * | AY BY 0 | - # | | | 0 0 1 | | | | 0 0 1 | - # This can be heavily reduced to: - let newx=t.ay*v.y+t.ax*v.x - v.y=t.by*v.y+t.bx*v.x - v.x=newx - -proc rotate90*(v:var Vector2d) {.inline.}= - ## Quickly rotates vector `v` 90 degrees counter clockwise, - ## without using any trigonometrics. - swap(v.x,v.y) - v.x= -v.x - -proc rotate180*(v:var Vector2d){.inline.}= - ## Quickly rotates vector `v` 180 degrees counter clockwise, - ## without using any trigonometrics. - v.x= -v.x - v.y= -v.y - -proc rotate270*(v:var Vector2d) {.inline.}= - ## Quickly rotates vector `v` 270 degrees counter clockwise, - ## without using any trigonometrics. - swap(v.x,v.y) - v.y= -v.y - -proc rotate*(v:var Vector2d,rad:float) = - ## Rotates vector `v` `rad` radians in place. - let - s=sin(rad) - c=cos(rad) - newx=c*v.x-s*v.y - v.y=c*v.y+s*v.x - v.x=newx - -proc scale*(v:var Vector2d,fac:float){.inline.}= - ## Scales vector `v` `rad` radians in place. - v.x*=fac - v.y*=fac - -proc stretch*(v:var Vector2d,facx,facy:float){.inline.}= - ## Stretches vector `v` `facx` times horizontally, - ## and `facy` times vertically. - v.x*=facx - v.y*=facy - -proc mirror*(v:var Vector2d,mirrvec:Vector2d)= - ## Mirrors vector `v` using `mirrvec` as mirror direction. - let - sqx=mirrvec.x*mirrvec.x - sqy=mirrvec.y*mirrvec.y - nd=1.0/(sqx+sqy) #used to normalize invector - xy2=mirrvec.x*mirrvec.y*2.0*nd - sqd=nd*(sqx-sqy) - - if nd==Inf or nd==NegInf: - return #mirroring around a zero vector is arbitrary=>keep as is is fastest - - let newx=xy2*v.y+sqd*v.x - v.y=v.x*xy2-sqd*v.y - v.x=newx - - -proc `-` *(v:Vector2d):Vector2d= - ## Negates a vector - result.x= -v.x - result.y= -v.y - -# declare templated binary operators -makeBinOpVector(`+`) -makeBinOpVector(`-`) -makeBinOpVector(`*`) -makeBinOpVector(`/`) -makeBinOpAssignVector(`+=`) -makeBinOpAssignVector(`-=`) -makeBinOpAssignVector(`*=`) -makeBinOpAssignVector(`/=`) - - -proc dot*(v1,v2:Vector2d):float= - ## Computes the dot product of two vectors. - ## Returns 0.0 if the vectors are perpendicular. - return v1.x*v2.x+v1.y*v2.y - -proc cross*(v1,v2:Vector2d):float= - ## Computes the cross product of two vectors, also called - ## the 'perpendicular dot product' in 2d. Returns 0.0 if the vectors - ## are parallel. - return v1.x*v2.y-v1.y*v2.x - -proc equals*(v1,v2:Vector2d,tol=1.0e-6):bool= - ## Checks if two vectors approximately equals with a tolerance. - return abs(v2.x-v1.x)<=tol and abs(v2.y-v1.y)<=tol - -proc `=~` *(v1,v2:Vector2d):bool= - ## Checks if two vectors approximately equals with a - ## hardcoded tolerance 1e-6 - equals(v1,v2) - -proc angleTo*(v1,v2:Vector2d):float= - ## Returns the smallest of the two possible angles - ## between `v1` and `v2` in radians. - var - nv1=v1 - nv2=v2 - if not nv1.tryNormalize or not nv2.tryNormalize: - return 0.0 # zero length vector has zero angle to any other vector - return safeArccos(dot(nv1,nv2)) - -proc angleCCW*(v1,v2:Vector2d):float= - ## Returns the counter clockwise plane angle from `v1` to `v2`, - ## in range 0 - 2*PI - let a=v1.angleTo(v2) - if v1.cross(v2)>=0.0: - return a - return DEG360-a - -proc angleCW*(v1,v2:Vector2d):float= - ## Returns the clockwise plane angle from `v1` to `v2`, - ## in range 0 - 2*PI - let a=v1.angleTo(v2) - if v1.cross(v2)<=0.0: - return a - return DEG360-a - -proc turnAngle*(v1,v2:Vector2d):float= - ## Returns the amount v1 should be rotated (in radians) to equal v2, - ## in range -PI to PI - let a=v1.angleTo(v2) - if v1.cross(v2)<=0.0: - return -a - return a - -proc bisect*(v1,v2:Vector2d):Vector2d {.noInit.}= - ## Computes the bisector between v1 and v2 as a normalized vector. - ## If one of the input vectors has zero length, a normalized version - ## of the other is returned. If both input vectors has zero length, - ## an arbitrary normalized vector is returned. - var - vmag1=v1.len - vmag2=v2.len - - # zero length vector equals arbitrary vector, just change to magnitude to one to - # avoid zero division - if vmag1==0.0: - if vmag2==0: #both are zero length return any normalized vector - return XAXIS - vmag1=1.0 - if vmag2==0.0: vmag2=1.0 - - let - x1=v1.x/vmag1 - y1=v1.y/vmag1 - x2=v2.x/vmag2 - y2=v2.y/vmag2 - - result.x=(x1 + x2) * 0.5 - result.y=(y1 + y2) * 0.5 - - if not result.tryNormalize(): - # This can happen if vectors are colinear. In this special case - # there are actually two bisectors, we select just - # one of them (x1,y1 rotated 90 degrees ccw). - result.x = -y1 - result.y = x1 - - - -# *************************************** -# Point2d implementation -# *************************************** - -proc point2d*(x,y:float):Point2d = - result.x=x - result.y=y - -proc sqrDist*(a,b:Point2d):float= - ## Computes the squared distance between `a` and `b` - let dx=b.x-a.x - let dy=b.y-a.y - result=dx*dx+dy*dy - -proc dist*(a,b:Point2d):float {.inline.}= - ## Computes the absolute distance between `a` and `b` - result=sqrt(sqrDist(a,b)) - -proc angle*(a,b:Point2d):float= - ## Computes the angle of the vector `b`-`a` - let dx=b.x-a.x - let dy=b.y-a.y - result=arctan2(dy,dx) - if result<0: - result += DEG360 - -proc `$` *(p:Point2d):string= - ## String representation of `p` - result=rtos(p.x) - result.add(",") - result.add(rtos(p.y)) - -proc `&`*(p:Point2d,t:Matrix2d):Point2d {.noInit,inline.} = - ## Concatenates a point `p` with a transform `t`, - ## resulting in a new, transformed point. - - # | AX AY 0 | - # | X Y 1 | * | BX BY 0 | - # | TX TY 1 | - result.x=p.x*t.ax+p.y*t.bx+t.tx - result.y=p.x*t.ay+p.y*t.by+t.ty - -proc `&=` *(p:var Point2d,t:Matrix2d) {.inline.}= - ## Applies transformation `t` onto `p` in place. - let newx=p.x*t.ax+p.y*t.bx+t.tx - p.y=p.x*t.ay+p.y*t.by+t.ty - p.x=newx - - -proc transformInv*(p:var Point2d,t:Matrix2d){.inline.}= - ## Applies the inverse of transformation `t` onto `p` in place. - ## If the matrix is not invertable (determinant=0) , EDivByZero will - ## be raised. - - # | AX AY 0 | ^-1 - # | X Y 1 | * | BX BY 0 | - # | TX TY 1 | - let d=t.determinant - if d==0.0: - raise newException(DivByZeroError,"Cannot invert a zero determinant matrix") - let - newx= (t.bx*t.ty-t.by*t.tx+p.x*t.by-p.y*t.bx)/d - p.y = -(t.ax*t.ty-t.ay*t.tx+p.x*t.ay-p.y*t.ax)/d - p.x=newx - - -proc `+`*(p:Point2d,v:Vector2d):Point2d {.noInit,inline.} = - ## Adds a vector `v` to a point `p`, resulting - ## in a new point. - result.x=p.x+v.x - result.y=p.y+v.y - -proc `+=`*(p:var Point2d,v:Vector2d) {.noInit,inline.} = - ## Adds a vector `v` to a point `p` in place. - p.x+=v.x - p.y+=v.y - -proc `-`*(p:Point2d,v:Vector2d):Point2d {.noInit,inline.} = - ## Subtracts a vector `v` from a point `p`, resulting - ## in a new point. - result.x=p.x-v.x - result.y=p.y-v.y - -proc `-`*(p1,p2:Point2d):Vector2d {.noInit,inline.} = - ## Subtracts `p2`from `p1` resulting in a difference vector. - result.x=p1.x-p2.x - result.y=p1.y-p2.y - -proc `-=`*(p:var Point2d,v:Vector2d) {.noInit,inline.} = - ## Subtracts a vector `v` from a point `p` in place. - p.x-=v.x - p.y-=v.y - -proc equals(p1,p2:Point2d,tol=1.0e-6):bool {.inline.}= - ## Checks if two points approximately equals with a tolerance. - return abs(p2.x-p1.x)<=tol and abs(p2.y-p1.y)<=tol - -proc `=~`*(p1,p2:Point2d):bool {.inline.}= - ## Checks if two vectors approximately equals with a - ## hardcoded tolerance 1e-6 - equals(p1,p2) - -proc polar*(p:Point2d,ang,dist:float):Point2d {.noInit.} = - ## Returns a point with a given angle and distance away from `p` - result.x=p.x+cos(ang)*dist - result.y=p.y+sin(ang)*dist - -proc rotate*(p:var Point2d,rad:float)= - ## Rotates a point in place `rad` radians around origo. - let - c=cos(rad) - s=sin(rad) - newx=p.x*c-p.y*s - p.y=p.y*c+p.x*s - p.x=newx - -proc rotate*(p:var Point2d,rad:float,org:Point2d)= - ## Rotates a point in place `rad` radians using `org` as - ## center of rotation. - let - c=cos(rad) - s=sin(rad) - newx=(p.x - org.x) * c - (p.y - org.y) * s + org.x - p.y=(p.y - org.y) * c + (p.x - org.x) * s + org.y - p.x=newx - -proc scale*(p:var Point2d,fac:float) {.inline.}= - ## Scales a point in place `fac` times with world origo as origin. - p.x*=fac - p.y*=fac - -proc scale*(p:var Point2d,fac:float,org:Point2d){.inline.}= - ## Scales the point in place `fac` times with `org` as origin. - p.x=(p.x - org.x) * fac + org.x - p.y=(p.y - org.y) * fac + org.y - -proc stretch*(p:var Point2d,facx,facy:float){.inline.}= - ## Scales a point in place non uniformly `facx` and `facy` times with - ## world origo as origin. - p.x*=facx - p.y*=facy - -proc stretch*(p:var Point2d,facx,facy:float,org:Point2d){.inline.}= - ## Scales the point in place non uniformly `facx` and `facy` times with - ## `org` as origin. - p.x=(p.x - org.x) * facx + org.x - p.y=(p.y - org.y) * facy + org.y - -proc move*(p:var Point2d,dx,dy:float){.inline.}= - ## Translates a point `dx`, `dy` in place. - p.x+=dx - p.y+=dy - -proc move*(p:var Point2d,v:Vector2d){.inline.}= - ## Translates a point with vector `v` in place. - p.x+=v.x - p.y+=v.y - -proc sgnArea*(a,b,c:Point2d):float= - ## Computes the signed area of the triangle thru points `a`,`b` and `c` - ## result>0.0 for counter clockwise triangle - ## result<0.0 for clockwise triangle - ## This is commonly used to determinate side of a point with respect to a line. - return ((b.x - c.x) * (b.y - a.y)-(b.y - c.y) * (b.x - a.x))*0.5 - -proc area*(a,b,c:Point2d):float= - ## Computes the area of the triangle thru points `a`,`b` and `c` - return abs(sgnArea(a,b,c)) - -proc closestPoint*(p:Point2d,pts:varargs[Point2d]):Point2d= - ## Returns a point selected from `pts`, that has the closest - ## euclidean distance to `p` - assert(pts.len>0) # must have at least one point - - var - bestidx=0 - bestdist=p.sqrDist(pts[0]) - curdist:float - - for idx in 1..high(pts): - curdist=p.sqrDist(pts[idx]) - if curdist<bestdist: - bestidx=idx - bestdist=curdist - - result=pts[bestidx] - - -# *************************************** -# Misc. math utilities that should -# probably be in another module. -# *************************************** -proc normAngle*(ang:float):float= - ## Returns an angle in radians, that is equal to `ang`, - ## but in the range 0 to <2*PI - if ang>=0.0 and ang<DEG360: - return ang - - return ang mod DEG360 - -proc degToRad*(deg:float):float {.inline.}= - ## converts `deg` degrees to radians - deg / RAD2DEGCONST - -proc radToDeg*(rad:float):float {.inline.}= - ## converts `rad` radians to degrees - rad * RAD2DEGCONST diff --git a/lib/pure/basic3d.nim b/lib/pure/basic3d.nim deleted file mode 100644 index e2d2464c0..000000000 --- a/lib/pure/basic3d.nim +++ /dev/null @@ -1,1040 +0,0 @@ -# -# -# Nim's Runtime Library -# (c) Copyright 2013 Robert Persson -# -# See the file "copying.txt", included in this -# distribution, for details about the copyright. -# - -import math -import strutils -import times - - -## Basic 3d support with vectors, points, matrices and some basic utilities. -## Vectors are implemented as direction vectors, ie. when transformed with a matrix -## the translation part of matrix is ignored. The coordinate system used is -## right handed, because its compatible with 2d coordinate system (rotation around -## zaxis equals 2d rotation). -## Operators `+` , `-` , `*` , `/` , `+=` , `-=` , `*=` and `/=` are implemented -## for vectors and scalars. -## -## -## Quick start example: -## -## .. code-block:: nim -## -## # Create a matrix which first rotates, then scales and at last translates -## -## var m:Matrix3d=rotate(PI,vector3d(1,1,2.5)) & scale(2.0) & move(100.0,200.0,300.0) -## -## # Create a 3d point at (100,150,200) and a vector (5,2,3) -## -## var pt:Point3d=point3d(100.0,150.0,200.0) -## -## var vec:Vector3d=vector3d(5.0,2.0,3.0) -## -## -## pt &= m # transforms pt in place -## -## var pt2:Point3d=pt & m #concatenates pt with m and returns a new point -## -## var vec2:Vector3d=vec & m #concatenates vec with m and returns a new vector - - - -type - Matrix3d* =object - ## Implements a row major 3d matrix, which means - ## transformations are applied the order they are concatenated. - ## This matrix is stored as an 4x4 matrix: - ## [ ax ay az aw ] - ## [ bx by bz bw ] - ## [ cx cy cz cw ] - ## [ tx ty tz tw ] - ax*,ay*,az*,aw*, bx*,by*,bz*,bw*, cx*,cy*,cz*,cw*, tx*,ty*,tz*,tw*:float - Point3d* = object - ## Implements a non-homogeneous 3d point stored as - ## an `x` , `y` and `z` coordinate. - x*,y*,z*:float - Vector3d* = object - ## Implements a 3d **direction vector** stored as - ## an `x` , `y` and `z` coordinate. Direction vector means, - ## that when transforming a vector with a matrix, the translational - ## part of the matrix is ignored. - x*,y*,z*:float -{.deprecated: [TMatrix3d: Matrix3d, TPoint3d: Point3d, TVector3d: Vector3d].} - - -# Some forward declarations -proc matrix3d*(ax,ay,az,aw,bx,by,bz,bw,cx,cy,cz,cw,tx,ty,tz,tw:float):Matrix3d {.noInit.} - ## Creates a new 4x4 3d transformation matrix. - ## `ax` , `ay` , `az` is the local x axis. - ## `bx` , `by` , `bz` is the local y axis. - ## `cx` , `cy` , `cz` is the local z axis. - ## `tx` , `ty` , `tz` is the translation. -proc vector3d*(x,y,z:float):Vector3d {.noInit,inline.} - ## Returns a new 3d vector (`x`,`y`,`z`) -proc point3d*(x,y,z:float):Point3d {.noInit,inline.} - ## Returns a new 4d point (`x`,`y`,`z`) -proc tryNormalize*(v:var Vector3d):bool - ## Modifies `v` to have a length of 1.0, keeping its angle. - ## If `v` has zero length (and thus no angle), it is left unmodified and false is - ## returned, otherwise true is returned. - - - -let - IDMATRIX*:Matrix3d=matrix3d( - 1.0,0.0,0.0,0.0, - 0.0,1.0,0.0,0.0, - 0.0,0.0,1.0,0.0, - 0.0,0.0,0.0,1.0) - ## Quick access to a 3d identity matrix - ORIGO*:Point3d=point3d(0.0,0.0,0.0) - ## Quick access to point (0,0) - XAXIS*:Vector3d=vector3d(1.0,0.0,0.0) - ## Quick access to an 3d x-axis unit vector - YAXIS*:Vector3d=vector3d(0.0,1.0,0.0) - ## Quick access to an 3d y-axis unit vector - ZAXIS*:Vector3d=vector3d(0.0,0.0,1.0) - ## Quick access to an 3d z-axis unit vector - - - -# *************************************** -# Private utils -# *************************************** - -proc rtos(val:float):string= - return formatFloat(val,ffDefault,0) - -proc safeArccos(v:float):float= - ## assumes v is in range 0.0-1.0, but clamps - ## the value to avoid out of domain errors - ## due to rounding issues - return arccos(clamp(v,-1.0,1.0)) - -template makeBinOpVector(s) = - proc s*(a,b:Vector3d):Vector3d {.inline,noInit.} = - vector3d(s(a.x,b.x),s(a.y,b.y),s(a.z,b.z)) - proc s*(a:Vector3d,b:float):Vector3d {.inline,noInit.} = - vector3d(s(a.x,b),s(a.y,b),s(a.z,b)) - proc s*(a:float,b:Vector3d):Vector3d {.inline,noInit.} = - vector3d(s(a,b.x),s(a,b.y),s(a,b.z)) - -template makeBinOpAssignVector(s) = - proc s*(a:var Vector3d,b:Vector3d) {.inline.} = - s(a.x,b.x); s(a.y,b.y); s(a.z,b.z) - proc s*(a:var Vector3d,b:float) {.inline.} = - s(a.x,b); s(a.y,b); s(a.z,b) - - - -# *************************************** -# Matrix3d implementation -# *************************************** - -proc setElements*(t:var Matrix3d,ax,ay,az,aw,bx,by,bz,bw,cx,cy,cz,cw,tx,ty,tz,tw:float) {.inline.}= - ## Sets arbitrary elements in an exisitng matrix. - t.ax=ax - t.ay=ay - t.az=az - t.aw=aw - t.bx=bx - t.by=by - t.bz=bz - t.bw=bw - t.cx=cx - t.cy=cy - t.cz=cz - t.cw=cw - t.tx=tx - t.ty=ty - t.tz=tz - t.tw=tw - -proc matrix3d*(ax,ay,az,aw,bx,by,bz,bw,cx,cy,cz,cw,tx,ty,tz,tw:float):Matrix3d = - result.setElements(ax,ay,az,aw,bx,by,bz,bw,cx,cy,cz,cw,tx,ty,tz,tw) - -proc `&`*(a,b:Matrix3d):Matrix3d {.noinit.} = - ## Concatenates matrices returning a new matrix. - result.setElements( - a.aw*b.tx+a.az*b.cx+a.ay*b.bx+a.ax*b.ax, - a.aw*b.ty+a.az*b.cy+a.ay*b.by+a.ax*b.ay, - a.aw*b.tz+a.az*b.cz+a.ay*b.bz+a.ax*b.az, - a.aw*b.tw+a.az*b.cw+a.ay*b.bw+a.ax*b.aw, - - a.bw*b.tx+a.bz*b.cx+a.by*b.bx+a.bx*b.ax, - a.bw*b.ty+a.bz*b.cy+a.by*b.by+a.bx*b.ay, - a.bw*b.tz+a.bz*b.cz+a.by*b.bz+a.bx*b.az, - a.bw*b.tw+a.bz*b.cw+a.by*b.bw+a.bx*b.aw, - - a.cw*b.tx+a.cz*b.cx+a.cy*b.bx+a.cx*b.ax, - a.cw*b.ty+a.cz*b.cy+a.cy*b.by+a.cx*b.ay, - a.cw*b.tz+a.cz*b.cz+a.cy*b.bz+a.cx*b.az, - a.cw*b.tw+a.cz*b.cw+a.cy*b.bw+a.cx*b.aw, - - a.tw*b.tx+a.tz*b.cx+a.ty*b.bx+a.tx*b.ax, - a.tw*b.ty+a.tz*b.cy+a.ty*b.by+a.tx*b.ay, - a.tw*b.tz+a.tz*b.cz+a.ty*b.bz+a.tx*b.az, - a.tw*b.tw+a.tz*b.cw+a.ty*b.bw+a.tx*b.aw) - - -proc scale*(s:float):Matrix3d {.noInit.} = - ## Returns a new scaling matrix. - result.setElements(s,0,0,0, 0,s,0,0, 0,0,s,0, 0,0,0,1) - -proc scale*(s:float,org:Point3d):Matrix3d {.noInit.} = - ## Returns a new scaling matrix using, `org` as scale origin. - result.setElements(s,0,0,0, 0,s,0,0, 0,0,s,0, - org.x-s*org.x,org.y-s*org.y,org.z-s*org.z,1.0) - -proc stretch*(sx,sy,sz:float):Matrix3d {.noInit.} = - ## Returns new a stretch matrix, which is a - ## scale matrix with non uniform scale in x,y and z. - result.setElements(sx,0,0,0, 0,sy,0,0, 0,0,sz,0, 0,0,0,1) - -proc stretch*(sx,sy,sz:float,org:Point3d):Matrix3d {.noInit.} = - ## Returns a new stretch matrix, which is a - ## scale matrix with non uniform scale in x,y and z. - ## `org` is used as stretch origin. - result.setElements(sx,0,0,0, 0,sy,0,0, 0,0,sz,0, org.x-sx*org.x,org.y-sy*org.y,org.z-sz*org.z,1) - -proc move*(dx,dy,dz:float):Matrix3d {.noInit.} = - ## Returns a new translation matrix. - result.setElements(1,0,0,0, 0,1,0,0, 0,0,1,0, dx,dy,dz,1) - -proc move*(v:Vector3d):Matrix3d {.noInit.} = - ## Returns a new translation matrix from a vector. - result.setElements(1,0,0,0, 0,1,0,0, 0,0,1,0, v.x,v.y,v.z,1) - - -proc rotate*(angle:float,axis:Vector3d):Matrix3d {.noInit.}= - ## Creates a rotation matrix that rotates `angle` radians over - ## `axis`, which passes through origo. - - # see PDF document http://inside.mines.edu/~gmurray/ArbitraryAxisRotation/ArbitraryAxisRotation.pdf - # for how this is computed - - var normax=axis - if not normax.tryNormalize: #simplifies matrix computation below a lot - raise newException(DivByZeroError,"Cannot rotate around zero length axis") - - let - cs=cos(angle) - si=sin(angle) - omc=1.0-cs - usi=normax.x*si - vsi=normax.y*si - wsi=normax.z*si - u2=normax.x*normax.x - v2=normax.y*normax.y - w2=normax.z*normax.z - uvomc=normax.x*normax.y*omc - uwomc=normax.x*normax.z*omc - vwomc=normax.y*normax.z*omc - - result.setElements( - u2+(1.0-u2)*cs, uvomc+wsi, uwomc-vsi, 0.0, - uvomc-wsi, v2+(1.0-v2)*cs, vwomc+usi, 0.0, - uwomc+vsi, vwomc-usi, w2+(1.0-w2)*cs, 0.0, - 0.0,0.0,0.0,1.0) - -proc rotate*(angle:float,org:Point3d,axis:Vector3d):Matrix3d {.noInit.}= - ## Creates a rotation matrix that rotates `angle` radians over - ## `axis`, which passes through `org`. - - # see PDF document http://inside.mines.edu/~gmurray/ArbitraryAxisRotation/ArbitraryAxisRotation.pdf - # for how this is computed - - var normax=axis - if not normax.tryNormalize: #simplifies matrix computation below a lot - raise newException(DivByZeroError,"Cannot rotate around zero length axis") - - let - u=normax.x - v=normax.y - w=normax.z - u2=u*u - v2=v*v - w2=w*w - cs=cos(angle) - omc=1.0-cs - si=sin(angle) - a=org.x - b=org.y - c=org.z - usi=u*si - vsi=v*si - wsi=w*si - uvomc=normax.x*normax.y*omc - uwomc=normax.x*normax.z*omc - vwomc=normax.y*normax.z*omc - - result.setElements( - u2+(v2+w2)*cs, uvomc+wsi, uwomc-vsi, 0.0, - uvomc-wsi, v2+(u2+w2)*cs, vwomc+usi, 0.0, - uwomc+vsi, vwomc-usi, w2+(u2+v2)*cs, 0.0, - (a*(v2+w2)-u*(b*v+c*w))*omc+(b*w-c*v)*si, - (b*(u2+w2)-v*(a*u+c*w))*omc+(c*u-a*w)*si, - (c*(u2+v2)-w*(a*u+b*v))*omc+(a*v-b*u)*si,1.0) - - -proc rotateX*(angle:float):Matrix3d {.noInit.}= - ## Creates a matrix that rotates around the x-axis with `angle` radians, - ## which is also called a 'roll' matrix. - let - c=cos(angle) - s=sin(angle) - result.setElements( - 1,0,0,0, - 0,c,s,0, - 0,-s,c,0, - 0,0,0,1) - -proc rotateY*(angle:float):Matrix3d {.noInit.}= - ## Creates a matrix that rotates around the y-axis with `angle` radians, - ## which is also called a 'pitch' matrix. - let - c=cos(angle) - s=sin(angle) - result.setElements( - c,0,-s,0, - 0,1,0,0, - s,0,c,0, - 0,0,0,1) - -proc rotateZ*(angle:float):Matrix3d {.noInit.}= - ## Creates a matrix that rotates around the z-axis with `angle` radians, - ## which is also called a 'yaw' matrix. - let - c=cos(angle) - s=sin(angle) - result.setElements( - c,s,0,0, - -s,c,0,0, - 0,0,1,0, - 0,0,0,1) - -proc isUniform*(m:Matrix3d,tol=1.0e-6):bool= - ## Checks if the transform is uniform, that is - ## perpendicular axes of equal length, which means (for example) - ## it cannot transform a sphere into an ellipsoid. - ## `tol` is used as tolerance for both equal length comparison - ## and perpendicular comparison. - - #dot product=0 means perpendicular coord. system, check xaxis vs yaxis and xaxis vs zaxis - if abs(m.ax*m.bx+m.ay*m.by+m.az*m.bz)<=tol and # x vs y - abs(m.ax*m.cx+m.ay*m.cy+m.az*m.cz)<=tol and #x vs z - abs(m.bx*m.cx+m.by*m.cy+m.bz*m.cz)<=tol: #y vs z - - #subtract squared lengths of axes to check if uniform scaling: - let - sqxlen=(m.ax*m.ax+m.ay*m.ay+m.az*m.az) - sqylen=(m.bx*m.bx+m.by*m.by+m.bz*m.bz) - sqzlen=(m.cx*m.cx+m.cy*m.cy+m.cz*m.cz) - if abs(sqxlen-sqylen)<=tol and abs(sqxlen-sqzlen)<=tol: - return true - return false - - - -proc mirror*(planeperp:Vector3d):Matrix3d {.noInit.}= - ## Creates a matrix that mirrors over the plane that has `planeperp` as normal, - ## and passes through origo. `planeperp` does not need to be normalized. - - # https://en.wikipedia.org/wiki/Transformation_matrix - var n=planeperp - if not n.tryNormalize: - raise newException(DivByZeroError,"Cannot mirror over a plane with a zero length normal") - - let - a=n.x - b=n.y - c=n.z - ab=a*b - ac=a*c - bc=b*c - - result.setElements( - 1-2*a*a , -2*ab,-2*ac,0, - -2*ab , 1-2*b*b, -2*bc, 0, - -2*ac, -2*bc, 1-2*c*c,0, - 0,0,0,1) - - -proc mirror*(org:Point3d,planeperp:Vector3d):Matrix3d {.noInit.}= - ## Creates a matrix that mirrors over the plane that has `planeperp` as normal, - ## and passes through `org`. `planeperp` does not need to be normalized. - - # constructs a mirror M like the simpler mirror matrix constructor - # above but premultiplies with the inverse traslation of org - # and postmultiplies with the translation of org. - # With some fiddling this becomes reasonably simple: - var n=planeperp - if not n.tryNormalize: - raise newException(DivByZeroError,"Cannot mirror over a plane with a zero length normal") - - let - a=n.x - b=n.y - c=n.z - ab=a*b - ac=a*c - bc=b*c - aa=a*a - bb=b*b - cc=c*c - tx=org.x - ty=org.y - tz=org.z - - result.setElements( - 1-2*aa , -2*ab,-2*ac,0, - -2*ab , 1-2*bb, -2*bc, 0, - -2*ac, -2*bc, 1-2*cc,0, - 2*(ac*tz+ab*ty+aa*tx), - 2*(bc*tz+bb*ty+ab*tx), - 2*(cc*tz+bc*ty+ac*tx) ,1) - - -proc determinant*(m:Matrix3d):float= - ## Computes the determinant of matrix `m`. - - # This computation is gotten from ratsimp(optimize(determinant(m))) - # in maxima CAS - let - O1=m.cx*m.tw-m.cw*m.tx - O2=m.cy*m.tw-m.cw*m.ty - O3=m.cx*m.ty-m.cy*m.tx - O4=m.cz*m.tw-m.cw*m.tz - O5=m.cx*m.tz-m.cz*m.tx - O6=m.cy*m.tz-m.cz*m.ty - - return (O1*m.ay-O2*m.ax-O3*m.aw)*m.bz+ - (-O1*m.az+O4*m.ax+O5*m.aw)*m.by+ - (O2*m.az-O4*m.ay-O6*m.aw)*m.bx+ - (O3*m.az-O5*m.ay+O6*m.ax)*m.bw - - -proc inverse*(m:Matrix3d):Matrix3d {.noInit.}= - ## Computes the inverse of matrix `m`. If the matrix - ## determinant is zero, thus not invertible, a EDivByZero - ## will be raised. - - # this computation comes from optimize(invert(m)) in maxima CAS - - let - det=m.determinant - O2=m.cy*m.tw-m.cw*m.ty - O3=m.cz*m.tw-m.cw*m.tz - O4=m.cy*m.tz-m.cz*m.ty - O5=m.by*m.tw-m.bw*m.ty - O6=m.bz*m.tw-m.bw*m.tz - O7=m.by*m.tz-m.bz*m.ty - O8=m.by*m.cw-m.bw*m.cy - O9=m.bz*m.cw-m.bw*m.cz - O10=m.by*m.cz-m.bz*m.cy - O11=m.cx*m.tw-m.cw*m.tx - O12=m.cx*m.tz-m.cz*m.tx - O13=m.bx*m.tw-m.bw*m.tx - O14=m.bx*m.tz-m.bz*m.tx - O15=m.bx*m.cw-m.bw*m.cx - O16=m.bx*m.cz-m.bz*m.cx - O17=m.cx*m.ty-m.cy*m.tx - O18=m.bx*m.ty-m.by*m.tx - O19=m.bx*m.cy-m.by*m.cx - - if det==0.0: - raise newException(DivByZeroError,"Cannot normalize zero length vector") - - result.setElements( - (m.bw*O4+m.by*O3-m.bz*O2)/det , (-m.aw*O4-m.ay*O3+m.az*O2)/det, - (m.aw*O7+m.ay*O6-m.az*O5)/det , (-m.aw*O10-m.ay*O9+m.az*O8)/det, - (-m.bw*O12-m.bx*O3+m.bz*O11)/det , (m.aw*O12+m.ax*O3-m.az*O11)/det, - (-m.aw*O14-m.ax*O6+m.az*O13)/det , (m.aw*O16+m.ax*O9-m.az*O15)/det, - (m.bw*O17+m.bx*O2-m.by*O11)/det , (-m.aw*O17-m.ax*O2+m.ay*O11)/det, - (m.aw*O18+m.ax*O5-m.ay*O13)/det , (-m.aw*O19-m.ax*O8+m.ay*O15)/det, - (-m.bx*O4+m.by*O12-m.bz*O17)/det , (m.ax*O4-m.ay*O12+m.az*O17)/det, - (-m.ax*O7+m.ay*O14-m.az*O18)/det , (m.ax*O10-m.ay*O16+m.az*O19)/det) - - -proc equals*(m1:Matrix3d,m2:Matrix3d,tol=1.0e-6):bool= - ## Checks if all elements of `m1`and `m2` is equal within - ## a given tolerance `tol`. - return - abs(m1.ax-m2.ax)<=tol and - abs(m1.ay-m2.ay)<=tol and - abs(m1.az-m2.az)<=tol and - abs(m1.aw-m2.aw)<=tol and - abs(m1.bx-m2.bx)<=tol and - abs(m1.by-m2.by)<=tol and - abs(m1.bz-m2.bz)<=tol and - abs(m1.bw-m2.bw)<=tol and - abs(m1.cx-m2.cx)<=tol and - abs(m1.cy-m2.cy)<=tol and - abs(m1.cz-m2.cz)<=tol and - abs(m1.cw-m2.cw)<=tol and - abs(m1.tx-m2.tx)<=tol and - abs(m1.ty-m2.ty)<=tol and - abs(m1.tz-m2.tz)<=tol and - abs(m1.tw-m2.tw)<=tol - -proc `=~`*(m1,m2:Matrix3d):bool= - ## Checks if `m1` and `m2` is approximately equal, using a - ## tolerance of 1e-6. - equals(m1,m2) - -proc transpose*(m:Matrix3d):Matrix3d {.noInit.}= - ## Returns the transpose of `m` - result.setElements(m.ax,m.bx,m.cx,m.tx,m.ay,m.by,m.cy,m.ty,m.az,m.bz,m.cz,m.tz,m.aw,m.bw,m.cw,m.tw) - -proc getXAxis*(m:Matrix3d):Vector3d {.noInit.}= - ## Gets the local x axis of `m` - result.x=m.ax - result.y=m.ay - result.z=m.az - -proc getYAxis*(m:Matrix3d):Vector3d {.noInit.}= - ## Gets the local y axis of `m` - result.x=m.bx - result.y=m.by - result.z=m.bz - -proc getZAxis*(m:Matrix3d):Vector3d {.noInit.}= - ## Gets the local y axis of `m` - result.x=m.cx - result.y=m.cy - result.z=m.cz - - -proc `$`*(m:Matrix3d):string= - ## String representation of `m` - return rtos(m.ax) & "," & rtos(m.ay) & "," & rtos(m.az) & "," & rtos(m.aw) & - "\n" & rtos(m.bx) & "," & rtos(m.by) & "," & rtos(m.bz) & "," & rtos(m.bw) & - "\n" & rtos(m.cx) & "," & rtos(m.cy) & "," & rtos(m.cz) & "," & rtos(m.cw) & - "\n" & rtos(m.tx) & "," & rtos(m.ty) & "," & rtos(m.tz) & "," & rtos(m.tw) - -proc apply*(m:Matrix3d, x,y,z:var float, translate=false)= - ## Applies transformation `m` onto `x` , `y` , `z` , optionally - ## using the translation part of the matrix. - let - oldx=x - oldy=y - oldz=z - - x=m.cx*oldz+m.bx*oldy+m.ax*oldx - y=m.cy*oldz+m.by*oldy+m.ay*oldx - z=m.cz*oldz+m.bz*oldy+m.az*oldx - - if translate: - x+=m.tx - y+=m.ty - z+=m.tz - -# *************************************** -# Vector3d implementation -# *************************************** -proc vector3d*(x,y,z:float):Vector3d= - result.x=x - result.y=y - result.z=z - -proc len*(v:Vector3d):float= - ## Returns the length of the vector `v`. - sqrt(v.x*v.x+v.y*v.y+v.z*v.z) - -proc `len=`*(v:var Vector3d,newlen:float) {.noInit.} = - ## Sets the length of the vector, keeping its direction. - ## If the vector has zero length before changing it's length, - ## an arbitrary vector of the requested length is returned. - - let fac=newlen/v.len - - if newlen==0.0: - v.x=0.0 - v.y=0.0 - v.z=0.0 - return - - if fac==Inf or fac==NegInf: - #to short for float accuracy - #do as good as possible: - v.x=newlen - v.y=0.0 - v.z=0.0 - else: - v.x*=fac - v.y*=fac - v.z*=fac - - -proc sqrLen*(v:Vector3d):float {.inline.}= - ## Computes the squared length of the vector, which is - ## faster than computing the absolute length. - return v.x*v.x+v.y*v.y+v.z*v.z - -proc `$` *(v:Vector3d):string= - ## String representation of `v` - result=rtos(v.x) - result.add(",") - result.add(rtos(v.y)) - result.add(",") - result.add(rtos(v.z)) - -proc `&` *(v:Vector3d,m:Matrix3d):Vector3d {.noInit.} = - ## Concatenate vector `v` with a transformation matrix. - ## Transforming a vector ignores the translational part - ## of the matrix. - - # | AX AY AZ AW | - # | X Y Z 1 | * | BX BY BZ BW | - # | CX CY CZ CW | - # | 0 0 0 1 | - let - newx=m.cx*v.z+m.bx*v.y+m.ax*v.x - newy=m.cy*v.z+m.by*v.y+m.ay*v.x - result.z=m.cz*v.z+m.bz*v.y+m.az*v.x - result.y=newy - result.x=newx - - -proc `&=` *(v:var Vector3d,m:Matrix3d) {.noInit.} = - ## Applies transformation `m` onto `v` in place. - ## Transforming a vector ignores the translational part - ## of the matrix. - - # | AX AY AZ AW | - # | X Y Z 1 | * | BX BY BZ BW | - # | CX CY CZ CW | - # | 0 0 0 1 | - - let - newx=m.cx*v.z+m.bx*v.y+m.ax*v.x - newy=m.cy*v.z+m.by*v.y+m.ay*v.x - v.z=m.cz*v.z+m.bz*v.y+m.az*v.x - v.y=newy - v.x=newx - -proc transformNorm*(v:var Vector3d,m:Matrix3d)= - ## Applies a normal direction transformation `m` onto `v` in place. - ## The resulting vector is *not* normalized. Transforming a vector ignores the - ## translational part of the matrix. If the matrix is not invertible - ## (determinant=0), an EDivByZero will be raised. - - # transforming a normal is done by transforming - # by the transpose of the inverse of the original matrix - - # Major reason this simple function is here is that this function can be optimized in the future, - # (possibly by hardware) as well as having a consistent API with the 2d version. - v&=transpose(inverse(m)) - -proc transformInv*(v:var Vector3d,m:Matrix3d)= - ## Applies the inverse of `m` on vector `v`. Transforming a vector ignores - ## the translational part of the matrix. Transforming a vector ignores the - ## translational part of the matrix. - ## If the matrix is not invertible (determinant=0), an EDivByZero - ## will be raised. - - # Major reason this simple function is here is that this function can be optimized in the future, - # (possibly by hardware) as well as having a consistent API with the 2d version. - v&=m.inverse - -proc transformNormInv*(vec:var Vector3d,m:Matrix3d)= - ## Applies an inverse normal direction transformation `m` onto `v` in place. - ## This is faster than creating an inverse - ## matrix and transformNorm(...) it. Transforming a vector ignores the - ## translational part of the matrix. - - # see vector2d:s equivalent for a deeper look how/why this works - vec&=m.transpose - -proc tryNormalize*(v:var Vector3d):bool= - ## Modifies `v` to have a length of 1.0, keeping its angle. - ## If `v` has zero length (and thus no angle), it is left unmodified and false is - ## returned, otherwise true is returned. - let mag=v.len - - if mag==0.0: - return false - - v.x/=mag - v.y/=mag - v.z/=mag - - return true - -proc normalize*(v:var Vector3d) {.inline.}= - ## Modifies `v` to have a length of 1.0, keeping its angle. - ## If `v` has zero length, an EDivByZero will be raised. - if not tryNormalize(v): - raise newException(DivByZeroError,"Cannot normalize zero length vector") - -proc rotate*(vec:var Vector3d,angle:float,axis:Vector3d)= - ## Rotates `vec` in place, with `angle` radians over `axis`, which passes - ## through origo. - - # see PDF document http://inside.mines.edu/~gmurray/ArbitraryAxisRotation/ArbitraryAxisRotation.pdf - # for how this is computed - - var normax=axis - if not normax.tryNormalize: - raise newException(DivByZeroError,"Cannot rotate around zero length axis") - - let - cs=cos(angle) - si=sin(angle) - omc=1.0-cs - u=normax.x - v=normax.y - w=normax.z - x=vec.x - y=vec.y - z=vec.z - uxyzomc=(u*x+v*y+w*z)*omc - - vec.x=u*uxyzomc+x*cs+(v*z-w*y)*si - vec.y=v*uxyzomc+y*cs+(w*x-u*z)*si - vec.z=w*uxyzomc+z*cs+(u*y-v*x)*si - -proc scale*(v:var Vector3d,s:float)= - ## Scales the vector in place with factor `s` - v.x*=s - v.y*=s - v.z*=s - -proc stretch*(v:var Vector3d,sx,sy,sz:float)= - ## Scales the vector non uniformly with factors `sx` , `sy` , `sz` - v.x*=sx - v.y*=sy - v.z*=sz - -proc mirror*(v:var Vector3d,planeperp:Vector3d)= - ## Computes the mirrored vector of `v` over the plane - ## that has `planeperp` as normal direction. - ## `planeperp` does not need to be normalized. - - var n=planeperp - n.normalize - - let - x=v.x - y=v.y - z=v.z - a=n.x - b=n.y - c=n.z - ac=a*c - ab=a*b - bc=b*c - - v.x= -2*(ac*z+ab*y+a*a*x)+x - v.y= -2*(bc*z+b*b*y+ab*x)+y - v.z= -2*(c*c*z+bc*y+ac*x)+z - - -proc `-` *(v:Vector3d):Vector3d= - ## Negates a vector - result.x= -v.x - result.y= -v.y - result.z= -v.z - -# declare templated binary operators -makeBinOpVector(`+`) -makeBinOpVector(`-`) -makeBinOpVector(`*`) -makeBinOpVector(`/`) -makeBinOpAssignVector(`+=`) -makeBinOpAssignVector(`-=`) -makeBinOpAssignVector(`*=`) -makeBinOpAssignVector(`/=`) - -proc dot*(v1,v2:Vector3d):float {.inline.}= - ## Computes the dot product of two vectors. - ## Returns 0.0 if the vectors are perpendicular. - return v1.x*v2.x+v1.y*v2.y+v1.z*v2.z - -proc cross*(v1,v2:Vector3d):Vector3d {.inline.}= - ## Computes the cross product of two vectors. - ## The result is a vector which is perpendicular - ## to the plane of `v1` and `v2`, which means - ## cross(xaxis,yaxis)=zaxis. The magnitude of the result is - ## zero if the vectors are colinear. - result.x = (v1.y * v2.z) - (v2.y * v1.z) - result.y = (v1.z * v2.x) - (v2.z * v1.x) - result.z = (v1.x * v2.y) - (v2.x * v1.y) - -proc equals*(v1,v2:Vector3d,tol=1.0e-6):bool= - ## Checks if two vectors approximately equals with a tolerance. - return abs(v2.x-v1.x)<=tol and abs(v2.y-v1.y)<=tol and abs(v2.z-v1.z)<=tol - -proc `=~` *(v1,v2:Vector3d):bool= - ## Checks if two vectors approximately equals with a - ## hardcoded tolerance 1e-6 - equals(v1,v2) - -proc angleTo*(v1,v2:Vector3d):float= - ## Returns the smallest angle between v1 and v2, - ## which is in range 0-PI - var - nv1=v1 - nv2=v2 - if not nv1.tryNormalize or not nv2.tryNormalize: - return 0.0 # zero length vector has zero angle to any other vector - return safeArccos(dot(nv1,nv2)) - -proc arbitraryAxis*(norm:Vector3d):Matrix3d {.noInit.}= - ## Computes the rotation matrix that would transform - ## world z vector into `norm`. The inverse of this matrix - ## is useful to transform a planar 3d object to 2d space. - ## This is the same algorithm used to interpret DXF and DWG files. - const lim=1.0/64.0 - var ax,ay,az:Vector3d - if abs(norm.x)<lim and abs(norm.y)<lim: - ax=cross(YAXIS,norm) - else: - ax=cross(ZAXIS,norm) - - ax.normalize() - ay=cross(norm,ax) - ay.normalize() - az=cross(ax,ay) - - result.setElements( - ax.x,ax.y,ax.z,0.0, - ay.x,ay.y,ay.z,0.0, - az.x,az.y,az.z,0.0, - 0.0,0.0,0.0,1.0) - -proc bisect*(v1,v2:Vector3d):Vector3d {.noInit.}= - ## Computes the bisector between v1 and v2 as a normalized vector. - ## If one of the input vectors has zero length, a normalized version - ## of the other is returned. If both input vectors has zero length, - ## an arbitrary normalized vector `v1` is returned. - var - vmag1=v1.len - vmag2=v2.len - - # zero length vector equals arbitrary vector, just change - # magnitude to one to avoid zero division - if vmag1==0.0: - if vmag2==0: #both are zero length return any normalized vector - return XAXIS - vmag1=1.0 - if vmag2==0.0: vmag2=1.0 - - let - x1=v1.x/vmag1 - y1=v1.y/vmag1 - z1=v1.z/vmag1 - x2=v2.x/vmag2 - y2=v2.y/vmag2 - z2=v2.z/vmag2 - - result.x=(x1 + x2) * 0.5 - result.y=(y1 + y2) * 0.5 - result.z=(z1 + z2) * 0.5 - - if not result.tryNormalize(): - # This can happen if vectors are colinear. In this special case - # there are actually inifinitely many bisectors, we select just - # one of them. - result=v1.cross(XAXIS) - if result.sqrLen<1.0e-9: - result=v1.cross(YAXIS) - if result.sqrLen<1.0e-9: - result=v1.cross(ZAXIS) # now we should be guaranteed to have succeeded - result.normalize - - - -# *************************************** -# Point3d implementation -# *************************************** -proc point3d*(x,y,z:float):Point3d= - result.x=x - result.y=y - result.z=z - -proc sqrDist*(a,b:Point3d):float= - ## Computes the squared distance between `a`and `b` - let dx=b.x-a.x - let dy=b.y-a.y - let dz=b.z-a.z - result=dx*dx+dy*dy+dz*dz - -proc dist*(a,b:Point3d):float {.inline.}= - ## Computes the absolute distance between `a`and `b` - result=sqrt(sqrDist(a,b)) - -proc `$` *(p:Point3d):string= - ## String representation of `p` - result=rtos(p.x) - result.add(",") - result.add(rtos(p.y)) - result.add(",") - result.add(rtos(p.z)) - -proc `&`*(p:Point3d,m:Matrix3d):Point3d= - ## Concatenates a point `p` with a transform `m`, - ## resulting in a new, transformed point. - result.z=m.cz*p.z+m.bz*p.y+m.az*p.x+m.tz - result.y=m.cy*p.z+m.by*p.y+m.ay*p.x+m.ty - result.x=m.cx*p.z+m.bx*p.y+m.ax*p.x+m.tx - -proc `&=` *(p:var Point3d,m:Matrix3d)= - ## Applies transformation `m` onto `p` in place. - let - x=p.x - y=p.y - z=p.z - p.x=m.cx*z+m.bx*y+m.ax*x+m.tx - p.y=m.cy*z+m.by*y+m.ay*x+m.ty - p.z=m.cz*z+m.bz*y+m.az*x+m.tz - -proc transformInv*(p:var Point3d,m:Matrix3d)= - ## Applies the inverse of transformation `m` onto `p` in place. - ## If the matrix is not invertable (determinant=0) , EDivByZero will - ## be raised. - - # can possibly be more optimized in the future so use this function when possible - p&=inverse(m) - - -proc `+`*(p:Point3d,v:Vector3d):Point3d {.noInit,inline.} = - ## Adds a vector `v` to a point `p`, resulting - ## in a new point. - result.x=p.x+v.x - result.y=p.y+v.y - result.z=p.z+v.z - -proc `+=`*(p:var Point3d,v:Vector3d) {.noInit,inline.} = - ## Adds a vector `v` to a point `p` in place. - p.x+=v.x - p.y+=v.y - p.z+=v.z - -proc `-`*(p:Point3d,v:Vector3d):Point3d {.noInit,inline.} = - ## Subtracts a vector `v` from a point `p`, resulting - ## in a new point. - result.x=p.x-v.x - result.y=p.y-v.y - result.z=p.z-v.z - -proc `-`*(p1,p2:Point3d):Vector3d {.noInit,inline.} = - ## Subtracts `p2`from `p1` resulting in a difference vector. - result.x=p1.x-p2.x - result.y=p1.y-p2.y - result.z=p1.z-p2.z - -proc `-=`*(p:var Point3d,v:Vector3d) {.noInit,inline.} = - ## Subtracts a vector `v` from a point `p` in place. - p.x-=v.x - p.y-=v.y - p.z-=v.z - -proc equals(p1,p2:Point3d,tol=1.0e-6):bool {.inline.}= - ## Checks if two points approximately equals with a tolerance. - return abs(p2.x-p1.x)<=tol and abs(p2.y-p1.y)<=tol and abs(p2.z-p1.z)<=tol - -proc `=~`*(p1,p2:Point3d):bool {.inline.}= - ## Checks if two vectors approximately equals with a - ## hardcoded tolerance 1e-6 - equals(p1,p2) - -proc rotate*(p:var Point3d,rad:float,axis:Vector3d)= - ## Rotates point `p` in place `rad` radians about an axis - ## passing through origo. - - var v=vector3d(p.x,p.y,p.z) - v.rotate(rad,axis) # reuse this code here since doing the same thing and quite complicated - p.x=v.x - p.y=v.y - p.z=v.z - -proc rotate*(p:var Point3d,angle:float,org:Point3d,axis:Vector3d)= - ## Rotates point `p` in place `rad` radians about an axis - ## passing through `org` - - # see PDF document http://inside.mines.edu/~gmurray/ArbitraryAxisRotation/ArbitraryAxisRotation.pdf - # for how this is computed - - var normax=axis - normax.normalize - - let - cs=cos(angle) - omc=1.0-cs - si=sin(angle) - u=normax.x - v=normax.y - w=normax.z - a=org.x - b=org.y - c=org.z - x=p.x - y=p.y - z=p.z - uu=u*u - vv=v*v - ww=w*w - ux=u*p.x - vy=v*p.y - wz=w*p.z - au=a*u - bv=b*v - cw=c*w - uxmvymwz=ux-vy-wz - - p.x=(a*(vv+ww)-u*(bv+cw-uxmvymwz))*omc + x*cs + (b*w+v*z-c*v-w*y)*si - p.y=(b*(uu+ww)-v*(au+cw-uxmvymwz))*omc + y*cs + (c*u-a*w+w*x-u*z)*si - p.z=(c*(uu+vv)-w*(au+bv-uxmvymwz))*omc + z*cs + (a*v+u*y-b*u-v*x)*si - -proc scale*(p:var Point3d,fac:float) {.inline.}= - ## Scales a point in place `fac` times with world origo as origin. - p.x*=fac - p.y*=fac - p.z*=fac - -proc scale*(p:var Point3d,fac:float,org:Point3d){.inline.}= - ## Scales the point in place `fac` times with `org` as origin. - p.x=(p.x - org.x) * fac + org.x - p.y=(p.y - org.y) * fac + org.y - p.z=(p.z - org.z) * fac + org.z - -proc stretch*(p:var Point3d,facx,facy,facz:float){.inline.}= - ## Scales a point in place non uniformly `facx` , `facy` , `facz` times - ## with world origo as origin. - p.x*=facx - p.y*=facy - p.z*=facz - -proc stretch*(p:var Point3d,facx,facy,facz:float,org:Point3d){.inline.}= - ## Scales the point in place non uniformly `facx` , `facy` , `facz` times - ## with `org` as origin. - p.x=(p.x - org.x) * facx + org.x - p.y=(p.y - org.y) * facy + org.y - p.z=(p.z - org.z) * facz + org.z - - -proc move*(p:var Point3d,dx,dy,dz:float){.inline.}= - ## Translates a point `dx` , `dy` , `dz` in place. - p.x+=dx - p.y+=dy - p.z+=dz - -proc move*(p:var Point3d,v:Vector3d){.inline.}= - ## Translates a point with vector `v` in place. - p.x+=v.x - p.y+=v.y - p.z+=v.z - -proc area*(a,b,c:Point3d):float {.inline.}= - ## Computes the area of the triangle thru points `a` , `b` and `c` - - # The area of a planar 3d quadliteral is the magnitude of the cross - # product of two edge vectors. Taking this time 0.5 gives the triangle area. - return cross(b-a,c-a).len*0.5 - diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim index d51a5c388..dbdf17514 100644 --- a/lib/pure/collections/sets.nim +++ b/lib/pure/collections/sets.nim @@ -287,8 +287,6 @@ proc exclImpl[A](s: var HashSet[A], key: A) : bool {. inline .} = if i >= 0: result = false - s.data[i].hcode = 0 - s.data[i].key = default(type(s.data[i].key)) dec(s.counter) while true: # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1 var j = i # The correctness of this depends on (h+1) in nextTry, @@ -300,7 +298,7 @@ proc exclImpl[A](s: var HashSet[A], key: A) : bool {. inline .} = if isEmpty(s.data[i].hcode): # end of collision cluster; So all done return r = s.data[i].hcode and msk # "home" location of key@i - shallowCopy(s.data[j], s.data[i]) # data[j] will be marked EMPTY next loop + shallowCopy(s.data[j], s.data[i]) # data[i] will be marked EMPTY next loop proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = ## Excludes `key` in the set `s` and tells if `key` was removed from `s`. @@ -662,9 +660,12 @@ proc card*[A](s: OrderedSet[A]): int {.inline.} = template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} = var h = s.first + var idx = 0 while h >= 0: var nxt = s.data[h].next - if isFilled(s.data[h].hcode): yieldStmt + if isFilled(s.data[h].hcode): + yieldStmt + inc(idx) h = nxt iterator items*[A](s: OrderedSet[A]): A = @@ -689,6 +690,11 @@ iterator items*[A](s: OrderedSet[A]): A = forAllOrderedPairs: yield s.data[h].key +iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = + assert s.isValid, "The set needs to be initialized" + forAllOrderedPairs: + yield (idx, s.data[h].key) + proc rawGetKnownHC[A](s: OrderedSet[A], key: A, hc: Hash): int {.inline.} = rawGetKnownHCImpl() @@ -760,6 +766,67 @@ proc incl*[A](s: var HashSet[A], other: OrderedSet[A]) = assert other.isValid, "The set `other` needs to be initialized." for item in other: incl(s, item) +proc exclImpl[A](s: var OrderedSet[A], key: A) : bool {. inline .} = + assert s.isValid, "The set needs to be initialized." + var hc: Hash + var i = rawGet(s, key, hc) + var msk = high(s.data) + result = true + + if i >= 0: + result = false + # Fix ordering + if s.first == i: + s.first = s.data[i].next + else: + var itr = s.first + while true: + if (s.data[itr].next == i): + s.data[itr].next = s.data[i].next + if s.last == i: + s.last = itr + break + itr = s.data[itr].next + + dec(s.counter) + while true: # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1 + var j = i # The correctness of this depends on (h+1) in nextTry, + var r = j # though may be adaptable to other simple sequences. + s.data[i].hcode = 0 # mark current EMPTY + s.data[i].key = default(type(s.data[i].key)) + s.data[i].next = 0 + doWhile((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): + i = (i + 1) and msk # increment mod table size + if isEmpty(s.data[i].hcode): # end of collision cluster; So all done + return + r = s.data[i].hcode and msk # "home" location of key@i + shallowCopy(s.data[j], s.data[i]) # data[i] will be marked EMPTY next loop + +proc missingOrExcl*[A](s: var OrderedSet[A], key: A): bool = + ## Excludes `key` in the set `s` and tells if `key` was removed from `s`. Efficiency: O(n). + ## + ## The difference with regards to the `excl() <#excl,TOrderedSet[A],A>`_ proc is + ## that this proc returns `true` if `key` was not present in `s`. Example: + ## + ## .. code-block:: + ## var s = toOrderedSet([2, 3, 6, 7]) + ## assert s.missingOrExcl(4) == true + ## assert s.missingOrExcl(6) == false + exclImpl(s, key) + + +proc excl*[A](s: var OrderedSet[A], key: A) = + ## Excludes `key` from the set `s`. Efficiency: O(n). + ## + ## This doesn't do anything if `key` is not found in `s`. Example: + ## + ## .. code-block:: + ## var s = toOrderedSet([2, 3, 6, 7]) + ## s.excl(2) + ## s.excl(2) + ## assert s.len == 3 + discard exclImpl(s, key) + proc containsOrIncl*[A](s: var OrderedSet[A], key: A): bool = ## Includes `key` in the set `s` and tells if `key` was added to `s`. ## @@ -986,6 +1053,24 @@ when isMainModule and not defined(release): assert a.len == b.card assert a.len == 2 + block setPairsIterator: + var s = toOrderedSet([1, 3, 5, 7]) + var items = newSeq[tuple[a: int, b: int]]() + for idx, item in s: items.add((idx, item)) + assert items == @[(0, 1), (1, 3), (2, 5), (3, 7)] + + block exclusions: + var s = toOrderedSet([1, 2, 3, 6, 7, 4]) + + s.excl(3) + s.excl(3) + s.excl(1) + s.excl(4) + + var items = newSeq[int]() + for item in s: items.add item + assert items == @[2, 6, 7] + #block orderedSetIterator: # var a = initOrderedSet[int]() # for value in [9, 2, 1, 5, 1, 8, 4, 2]: @@ -1030,6 +1115,11 @@ when isMainModule and not defined(release): if s <= i or mustRehash(s, i): echo "performance issue: rightSize() will not elide enlarge() at ", i + block missingOrExcl: + var s = toOrderedSet([2, 3, 6, 7]) + assert s.missingOrExcl(4) == true + assert s.missingOrExcl(6) == false + when not defined(testing): echo "Micro tests run successfully." diff --git a/lib/pure/json.nim b/lib/pure/json.nim index 097952588..656114fb1 100644 --- a/lib/pure/json.nim +++ b/lib/pure/json.nim @@ -721,6 +721,16 @@ proc getElems*(n: JsonNode, default: seq[JsonNode] = @[]): seq[JsonNode] = if n.isNil or n.kind != JArray: return default else: return n.elems +proc add*(father, child: JsonNode) = + ## Adds `child` to a JArray node `father`. + assert father.kind == JArray + father.elems.add(child) + +proc add*(obj: JsonNode, key: string, val: JsonNode) = + ## Sets a field from a `JObject`. + assert obj.kind == JObject + obj.fields[key] = val + proc `%`*(s: string): JsonNode = ## Generic constructor for JSON data. Creates a new `JString JsonNode`. new(result) @@ -759,6 +769,19 @@ proc `%`*[T](elements: openArray[T]): JsonNode = result = newJArray() for elem in elements: result.add(%elem) +when false: + # For 'consistency' we could do this, but that only pushes people further + # into that evil comfort zone where they can use Nim without understanding it + # causing problems later on. + proc `%`*(elements: set[bool]): JsonNode = + ## Generic constructor for JSON data. Creates a new `JObject JsonNode`. + ## This can only be used with the empty set ``{}`` and is supported + ## to prevent the gotcha ``%*{}`` which used to produce an empty + ## JSON array. + result = newJObject() + assert false notin elements, "usage error: only empty sets allowed" + assert true notin elements, "usage error: only empty sets allowed" + proc `%`*(o: object): JsonNode = ## Generic constructor for JSON data. Creates a new `JObject JsonNode` result = newJObject() @@ -779,27 +802,25 @@ proc `%`*(o: enum): JsonNode = proc toJson(x: NimNode): NimNode {.compiletime.} = case x.kind of nnkBracket: # array + if x.len == 0: return newCall(bindSym"newJArray") result = newNimNode(nnkBracket) for i in 0 .. <x.len: result.add(toJson(x[i])) - + result = newCall(bindSym"%", result) of nnkTableConstr: # object + if x.len == 0: return newCall(bindSym"newJObject") result = newNimNode(nnkTableConstr) for i in 0 .. <x.len: x[i].expectKind nnkExprColonExpr - result.add(newNimNode(nnkExprColonExpr).add(x[i][0]).add(toJson(x[i][1]))) - + result.add newTree(nnkExprColonExpr, x[i][0], toJson(x[i][1])) + result = newCall(bindSym"%", result) of nnkCurly: # empty object - result = newNimNode(nnkTableConstr) x.expectLen(0) - + result = newCall(bindSym"newJObject") of nnkNilLit: - result = newCall("newJNull") - + result = newCall(bindSym"newJNull") else: - result = x - - result = prefix(result, "%") + result = newCall(bindSym"%", x) macro `%*`*(x: untyped): untyped = ## Convert an expression to a JsonNode directly, without having to specify @@ -909,16 +930,6 @@ proc contains*(node: JsonNode, val: JsonNode): bool = proc existsKey*(node: JsonNode, key: string): bool {.deprecated.} = node.hasKey(key) ## Deprecated for `hasKey` -proc add*(father, child: JsonNode) = - ## Adds `child` to a JArray node `father`. - assert father.kind == JArray - father.elems.add(child) - -proc add*(obj: JsonNode, key: string, val: JsonNode) = - ## Sets a field from a `JObject`. - assert obj.kind == JObject - obj.fields[key] = val - proc `[]=`*(obj: JsonNode, key: string, val: JsonNode) {.inline.} = ## Sets a field from a `JObject`. assert(obj.kind == JObject) @@ -1203,7 +1214,7 @@ proc parseJson(p: var JsonParser): JsonNode = raiseParseErr(p, "{") when not defined(js): - proc parseJson*(s: Stream, filename: string): JsonNode = + proc parseJson*(s: Stream, filename: string = ""): JsonNode = ## Parses from a stream `s` into a `JsonNode`. `filename` is only needed ## for nice error messages. ## If `s` contains extra data, it will raise `JsonParsingError`. @@ -1934,4 +1945,8 @@ when isMainModule: except JsonParsingError: doAssert getCurrentExceptionMsg().contains(errorMessages[errEofExpected]) + # bug #6438 + doAssert($ %*[] == "[]") + doAssert($ %*{} == "{}") + echo("Tests succeeded!") diff --git a/lib/pure/nativesockets.nim b/lib/pure/nativesockets.nim index 1a62c0bf6..98fc62a3b 100644 --- a/lib/pure/nativesockets.nim +++ b/lib/pure/nativesockets.nim @@ -498,7 +498,7 @@ proc getLocalAddr*(socket: SocketHandle, domain: Domain): (string, Port) = # Cannot use INET6_ADDRSTRLEN here, because it's a C define. var buf: array[64, char] if inet_ntop(name.sin6_family.cint, - addr name, buf.cstring, sizeof(buf).int32).isNil: + addr name.sin6_addr, buf.cstring, sizeof(buf).int32).isNil: raiseOSError(osLastError()) result = ($buf, Port(nativesockets.ntohs(name.sin6_port))) else: @@ -534,7 +534,7 @@ proc getPeerAddr*(socket: SocketHandle, domain: Domain): (string, Port) = # Cannot use INET6_ADDRSTRLEN here, because it's a C define. var buf: array[64, char] if inet_ntop(name.sin6_family.cint, - addr name, buf.cstring, sizeof(buf).int32).isNil: + addr name.sin6_addr, buf.cstring, sizeof(buf).int32).isNil: raiseOSError(osLastError()) result = ($buf, Port(nativesockets.ntohs(name.sin6_port))) else: diff --git a/lib/pure/options.nim b/lib/pure/options.nim index 2abb80016..ad63bbcb6 100644 --- a/lib/pure/options.nim +++ b/lib/pure/options.nim @@ -15,7 +15,7 @@ ## A value of type ``Option[T]`` either contains a value `x` (represented as ## ``some(x)``) or is empty (``none(T)``). ## -## This can be useful when you have a value that can be present or not. The +## This can be useful when you have a value that can be present or not. The ## absence of a value is often represented by ``nil``, but it is not always ## available, nor is it always a good solution. ## @@ -67,10 +67,8 @@ ## assert(false) # This will not be reached ## except UnpackError: # Because an exception is raised ## discard - import typetraits - type Option*[T] = object ## An optional type that stores its value and state separately in a boolean. @@ -78,7 +76,6 @@ type has: bool UnpackError* = ref object of ValueError - proc some*[T](val: T): Option[T] = ## Returns a ``Option`` that has this value. result.has = true @@ -88,14 +85,12 @@ proc none*(T: typedesc): Option[T] = ## Returns a ``Option`` for this type that has no value. result.has = false - proc isSome*[T](self: Option[T]): bool = self.has proc isNone*[T](self: Option[T]): bool = not self.has - proc unsafeGet*[T](self: Option[T]): T = ## Returns the value of a ``some``. Behavior is undefined for ``none``. assert self.isSome @@ -110,12 +105,11 @@ proc get*[T](self: Option[T]): T = proc get*[T](self: Option[T], otherwise: T): T = ## Returns the contents of this option or `otherwise` if the option is none. - if self.isSome: + if self.has: self.val else: otherwise - proc map*[T](self: Option[T], callback: proc (input: T)) = ## Applies a callback to the value in this Option if self.has: @@ -123,12 +117,27 @@ proc map*[T](self: Option[T], callback: proc (input: T)) = proc map*[T, R](self: Option[T], callback: proc (input: T): R): Option[R] = ## Applies a callback to the value in this Option and returns an option - ## containing the new value. If this option is None, None will be returned + ## containing the new value. If this option is None, None will be returned. if self.has: - some[R]( callback(self.val) ) + some[R](callback(self.val)) else: none(R) +proc flatten*[A](self: Option[Option[A]]): Option[A] = + ## Remove one level of structure in a nested Option. + if self.has: + self.val + else: + none(A) + +proc flatMap*[A, B](self: Option[A], callback: proc (input: A): Option[B]): Option[B] = + ## Applies a callback to the value in this Option and returns an + ## option containing the new value. If this option is None, None will be + ## returned. Similar to ``map``, with the difference that the callback + ## returns an Option, not a raw value. This allows multiple procs with a + ## signature of ``A -> Option[B]`` (including A = B) to be chained together. + map(self, callback).flatten() + proc filter*[T](self: Option[T], callback: proc (input: T): bool): Option[T] = ## Applies a callback to the value in this Option. If the callback returns ## `true`, the option is returned as a Some. If it returns false, it is @@ -138,21 +147,18 @@ proc filter*[T](self: Option[T], callback: proc (input: T): bool): Option[T] = else: self - proc `==`*(a, b: Option): bool = ## Returns ``true`` if both ``Option``s are ``none``, ## or if they have equal values (a.has and b.has and a.val == b.val) or (not a.has and not b.has) - -proc `$`*[T]( self: Option[T] ): string = +proc `$`*[T](self: Option[T]): string = ## Returns the contents of this option or `otherwise` if the option is none. if self.has: "Some(" & $self.val & ")" else: "None[" & T.name & "]" - when isMainModule: import unittest, sequtils @@ -198,12 +204,12 @@ when isMainModule: check false test "get with a default value": - check( some("Correct").get("Wrong") == "Correct" ) - check( stringNone.get("Correct") == "Correct" ) + check(some("Correct").get("Wrong") == "Correct") + check(stringNone.get("Correct") == "Correct") test "$": - check( $(some("Correct")) == "Some(Correct)" ) - check( $(stringNone) == "None[string]" ) + check($(some("Correct")) == "Some(Correct)") + check($(stringNone) == "None[string]") test "map with a void result": var procRan = 0 @@ -212,11 +218,38 @@ when isMainModule: intNone.map(proc (v: int) = check false) test "map": - check( some(123).map(proc (v: int): int = v * 2) == some(246) ) - check( intNone.map(proc (v: int): int = v * 2).isNone ) + check(some(123).map(proc (v: int): int = v * 2) == some(246)) + check(intNone.map(proc (v: int): int = v * 2).isNone) test "filter": - check( some(123).filter(proc (v: int): bool = v == 123) == some(123) ) - check( some(456).filter(proc (v: int): bool = v == 123).isNone ) - check( intNone.filter(proc (v: int): bool = check false).isNone ) - + check(some(123).filter(proc (v: int): bool = v == 123) == some(123)) + check(some(456).filter(proc (v: int): bool = v == 123).isNone) + check(intNone.filter(proc (v: int): bool = check false).isNone) + + test "flatMap": + proc addOneIfNotZero(v: int): Option[int] = + if v != 0: + result = some(v + 1) + else: + result = none(int) + + check(some(1).flatMap(addOneIfNotZero) == some(2)) + check(some(0).flatMap(addOneIfNotZero) == none(int)) + check(some(1).flatMap(addOneIfNotZero).flatMap(addOneIfNotZero) == some(3)) + + proc maybeToString(v: int): Option[string] = + if v != 0: + result = some($v) + else: + result = none(string) + + check(some(1).flatMap(maybeToString) == some("1")) + + proc maybeExclaim(v: string): Option[string] = + if v != "": + result = some v & "!" + else: + result = none(string) + + check(some(1).flatMap(maybeToString).flatMap(maybeExclaim) == some("1!")) + check(some(0).flatMap(maybeToString).flatMap(maybeExclaim) == none(string)) diff --git a/lib/pure/osproc.nim b/lib/pure/osproc.nim index fa723f593..07429b9a9 100644 --- a/lib/pure/osproc.nim +++ b/lib/pure/osproc.nim @@ -410,13 +410,11 @@ when defined(Windows) and not defined(useNimRtl): result.readDataImpl = hsReadData result.writeDataImpl = hsWriteData - proc buildCommandLine(a: string, args: openArray[string]): cstring = - var res = quoteShell(a) + proc buildCommandLine(a: string, args: openArray[string]): string = + result = quoteShell(a) for i in 0..high(args): - res.add(' ') - res.add(quoteShell(args[i])) - result = cast[cstring](alloc0(res.len+1)) - copyMem(result, cstring(res), res.len) + result.add(' ') + result.add(quoteShell(args[i])) proc buildEnv(env: StringTableRef): tuple[str: cstring, len: int] = var L = 0 @@ -540,11 +538,13 @@ when defined(Windows) and not defined(useNimRtl): result.errHandle = FileHandle(si.hStdError) var cmdl: cstring + var cmdRoot: string if poEvalCommand in options: cmdl = command assert args.len == 0 else: - cmdl = buildCommandLine(command, args) + cmdRoot = buildCommandLine(command, args) + cmdl = cstring(cmdRoot) var wd: cstring = nil var e = (str: nil.cstring, len: -1) if len(workingDir) > 0: wd = workingDir diff --git a/lib/pure/strutils.nim b/lib/pure/strutils.nim index b39d3b691..8b4e6bd05 100644 --- a/lib/pure/strutils.nim +++ b/lib/pure/strutils.nim @@ -888,7 +888,7 @@ proc toHex*(x: BiggestInt, len: Positive): string {.noSideEffect, n = x result = newString(len) for j in countdown(len-1, 0): - result[j] = HexChars[(n and 0xF).int] + result[j] = HexChars[int(n and 0xF)] n = n shr 4 # handle negative overflow if n == 0 and x < 0: n = -1 diff --git a/lib/pure/unittest.nim b/lib/pure/unittest.nim index 28691fcb4..3772a213a 100644 --- a/lib/pure/unittest.nim +++ b/lib/pure/unittest.nim @@ -509,10 +509,6 @@ macro check*(conditions: untyped): untyped = ## "AKB48".toLowerAscii() == "akb48" ## 'C' in teams let checked = callsite()[1] - var - argsAsgns = newNimNode(nnkStmtList) - argsPrintOuts = newNimNode(nnkStmtList) - counter = 0 template asgn(a: untyped, value: typed) = var a = value # XXX: we need "var: var" here in order to @@ -522,66 +518,71 @@ macro check*(conditions: untyped): untyped = when compiles(string($value)): checkpoint(name & " was " & $value) - proc inspectArgs(exp: NimNode): NimNode = - result = copyNimTree(exp) + proc inspectArgs(exp: NimNode): tuple[assigns, check, printOuts: NimNode] = + result.check = copyNimTree(exp) + result.assigns = newNimNode(nnkStmtList) + result.printOuts = newNimNode(nnkStmtList) + + var counter = 0 + if exp[0].kind == nnkIdent and - $exp[0] in ["and", "or", "not", "in", "notin", "==", "<=", + $exp[0] in ["not", "in", "notin", "==", "<=", ">=", "<", ">", "!=", "is", "isnot"]: - for i in countup(1, exp.len - 1): + + for i in 1 ..< exp.len: if exp[i].kind notin nnkLiterals: inc counter - var arg = newIdentNode(":p" & $counter) - var argStr = exp[i].toStrLit - var paramAst = exp[i] + let argStr = exp[i].toStrLit + let paramAst = exp[i] if exp[i].kind == nnkIdent: - argsPrintOuts.add getAst(print(argStr, paramAst)) - if exp[i].kind in nnkCallKinds: - var callVar = newIdentNode(":c" & $counter) - argsAsgns.add getAst(asgn(callVar, paramAst)) - result[i] = callVar - argsPrintOuts.add getAst(print(argStr, callVar)) + result.printOuts.add getAst(print(argStr, paramAst)) + if exp[i].kind in nnkCallKinds + { nnkDotExpr, nnkBracketExpr }: + let callVar = newIdentNode(":c" & $counter) + result.assigns.add getAst(asgn(callVar, paramAst)) + result.check[i] = callVar + result.printOuts.add getAst(print(argStr, callVar)) if exp[i].kind == nnkExprEqExpr: # ExprEqExpr # Ident !"v" # IntLit 2 - result[i] = exp[i][1] + result.check[i] = exp[i][1] if exp[i].typekind notin {ntyTypeDesc}: - argsAsgns.add getAst(asgn(arg, paramAst)) - argsPrintOuts.add getAst(print(argStr, arg)) + let arg = newIdentNode(":p" & $counter) + result.assigns.add getAst(asgn(arg, paramAst)) + result.printOuts.add getAst(print(argStr, arg)) if exp[i].kind != nnkExprEqExpr: - result[i] = arg + result.check[i] = arg else: - result[i][1] = arg + result.check[i][1] = arg case checked.kind of nnkCallKinds: - template rewrite(call, lineInfoLit, callLit, - argAssgs, argPrintOuts) = + + let (assigns, check, printOuts) = inspectArgs(checked) + let lineinfo = newStrLitNode(checked.lineinfo) + let callLit = checked.toStrLit + result = quote do: block: - argAssgs #all callables (and assignments) are run here - if not call: - checkpoint(lineInfoLit & ": Check failed: " & callLit) - argPrintOuts + `assigns` + if not `check`: + checkpoint(`lineinfo` & ": Check failed: " & `callLit`) + `printOuts` fail() - var checkedStr = checked.toStrLit - let parameterizedCheck = inspectArgs(checked) - result = getAst(rewrite(parameterizedCheck, checked.lineinfo, checkedStr, - argsAsgns, argsPrintOuts)) - of nnkStmtList: result = newNimNode(nnkStmtList) - for i in countup(0, checked.len - 1): - if checked[i].kind != nnkCommentStmt: - result.add(newCall(!"check", checked[i])) + for node in checked: + if node.kind != nnkCommentStmt: + result.add(newCall(!"check", node)) else: - template rewrite(exp, lineInfoLit, expLit) = - if not exp: - checkpoint(lineInfoLit & ": Check failed: " & expLit) - fail() + let lineinfo = newStrLitNode(checked.lineinfo) + let callLit = checked.toStrLit - result = getAst(rewrite(checked, checked.lineinfo, checked.toStrLit)) + result = quote do: + if not `checked`: + checkpoint(`lineinfo` & ": Check failed: " & `callLit`) + fail() template require*(conditions: untyped) = ## Same as `check` except any failed test causes the program to quit diff --git a/lib/system.nim b/lib/system.nim index ad958d733..dc3152faf 100644 --- a/lib/system.nim +++ b/lib/system.nim @@ -246,6 +246,9 @@ type UncheckedArray* {.unchecked.}[T] = array[0, T] ## Array with no bounds checking +when defined(nimHasOpt): + type opt*{.magic: "Opt".}[T] + proc high*[T: Ordinal](x: T): T {.magic: "High", noSideEffect.} ## returns the highest possible index of an array, a sequence, a string or ## the highest possible value of an ordinal value `x`. As a special @@ -409,8 +412,7 @@ when not defined(JS): when not defined(JS) and not defined(nimscript): template space(s: PGenericSeq): int {.dirty.} = - s.reserved and not seqShallowFlag - + s.reserved and not (seqShallowFlag or strlitFlag) include "system/hti" type @@ -718,7 +720,7 @@ proc len*[TOpenArray: openArray|varargs](x: TOpenArray): int {. magic: "LengthOpenArray", noSideEffect.} proc len*(x: string): int {.magic: "LengthStr", noSideEffect.} proc len*(x: cstring): int {.magic: "LengthStr", noSideEffect.} -proc len*[I, T](x: array[I, T]): int {.magic: "LengthArray", noSideEffect.} +proc len*(x: (type array)|array): int {.magic: "LengthArray", noSideEffect.} proc len*[T](x: seq[T]): int {.magic: "LengthSeq", noSideEffect.} ## returns the length of an array, an openarray, a sequence or a string. ## This is roughly the same as ``high(T)-low(T)+1``, but its resulting type is @@ -1329,6 +1331,9 @@ const ## "amd64", "mips", "mipsel", "arm", "arm64", "mips64", "mips64el". seqShallowFlag = low(int) + strlitFlag = 1 shl (sizeof(int)*8 - 2) # later versions of the codegen \ + # emit this flag + # for string literals, it allows for some optimizations. {.push profiler: off.} when defined(nimKnowsNimvm): @@ -1435,7 +1440,12 @@ when defined(nimdoc): elif defined(genode): proc quit*(errorcode: int = QuitSuccess) {.magic: "Exit", noreturn, - importcpp: "genodeEnv->parent().exit(@)", header: "<base/env.h>".} + importcpp: "genodeEnv->parent().exit(@); Genode::sleep_forever()", + header: "<base/sleep.h>".} + +elif defined(nodejs): + proc quit*(errorcode: int = QuitSuccess) {.magic: "Exit", + importc: "process.exit", noreturn.} else: proc quit*(errorcode: int = QuitSuccess) {. @@ -3402,10 +3412,10 @@ when hasAlloc or defined(nimscript): proc `[]`*(s: string, x: Slice[int]): string {.inline.} = ## slice operation for strings. ## returns the inclusive range [s[x.a], s[x.b]]: - ## + ## ## .. code-block:: nim ## var s = "abcdef" - ## assert s[1..3] == "bcd" + ## assert s[1..3] == "bcd" result = s.substr(x.a, x.b) proc `[]=`*(s: var string, x: Slice[int], b: string) = @@ -3427,7 +3437,7 @@ when hasAlloc or defined(nimscript): proc `[]`*[Idx, T](a: array[Idx, T], x: Slice[int]): seq[T] = ## slice operation for arrays. ## returns the inclusive range [a[x.a], a[x.b]]: - ## + ## ## .. code-block:: nim ## var a = [1,2,3,4] ## assert a[0..2] == @[1,2,3] @@ -3466,7 +3476,7 @@ proc `[]=`*[Idx, T](a: var array[Idx, T], x: Slice[Idx], b: openArray[T]) = proc `[]`*[T](s: seq[T], x: Slice[int]): seq[T] = ## slice operation for sequences. ## returns the inclusive range [s[x.a], s[x.b]]: - ## + ## ## .. code-block:: nim ## var s = @[1,2,3,4] ## assert s[0..2] == @[1,2,3] @@ -3719,7 +3729,9 @@ proc shallow*(s: var string) {.noSideEffect, inline.} = ## purposes. when not defined(JS) and not defined(nimscript): var s = cast[PGenericSeq](s) - s.reserved = s.reserved or seqShallowFlag + # string literals cannot become 'shallow': + if (s.reserved and strlitFlag) == 0: + s.reserved = s.reserved or seqShallowFlag type NimNodeObj = object diff --git a/lib/system/assign.nim b/lib/system/assign.nim index 61c33e51b..115df61a7 100644 --- a/lib/system/assign.nim +++ b/lib/system/assign.nim @@ -63,12 +63,17 @@ proc genericAssignAux(dest, src: pointer, mt: PNimType, shallow: bool) = sysAssert(dest != nil, "genericAssignAux 3") unsureAsgnRef(x, newSeq(mt, seq.len)) var dst = cast[ByteAddress](cast[PPointer](dest)[]) - for i in 0..seq.len-1: - genericAssignAux( - cast[pointer](dst +% i*% mt.base.size +% GenericSeqSize), - cast[pointer](cast[ByteAddress](s2) +% i *% mt.base.size +% - GenericSeqSize), - mt.base, shallow) + if ntfNoRefs in mt.base.flags: + copyMem(cast[pointer](dst +% GenericSeqSize), + cast[pointer](cast[ByteAddress](s2) +% GenericSeqSize), + seq.len * mt.base.size) + else: + for i in 0..seq.len-1: + genericAssignAux( + cast[pointer](dst +% i*% mt.base.size +% GenericSeqSize), + cast[pointer](cast[ByteAddress](s2) +% i *% mt.base.size +% + GenericSeqSize), + mt.base, shallow) of tyObject: if mt.base != nil: genericAssignAux(dest, src, mt.base, shallow) @@ -89,6 +94,19 @@ proc genericAssignAux(dest, src: pointer, mt: PNimType, shallow: bool) = cast[pointer](s +% i*% mt.base.size), mt.base, shallow) of tyRef: unsureAsgnRef(cast[PPointer](dest), cast[PPointer](s)[]) + of tyOptAsRef: + let s2 = cast[PPointer](src)[] + let d = cast[PPointer](dest) + if s2 == nil: + unsureAsgnRef(d, s2) + else: + when declared(usrToCell): + let realType = usrToCell(s2).typ + else: + let realType = if mt.base.kind == tyObject: cast[ptr PNimType](s2)[] + else: mt.base + var z = newObj(realType, realType.base.size) + genericAssignAux(d, addr z, mt.base, shallow) else: copyMem(dest, src, mt.size) # copy raw bits @@ -115,6 +133,7 @@ when false: of tyPtr: k = "ptr" of tyRef: k = "ref" of tyVar: k = "var" + of tyOptAsRef: k = "optref" of tySequence: k = "seq" of tyProc: k = "proc" of tyPointer: k = "range" @@ -195,7 +214,7 @@ proc genericReset(dest: pointer, mt: PNimType) = var d = cast[ByteAddress](dest) sysAssert(mt != nil, "genericReset 2") case mt.kind - of tyString, tyRef, tySequence: + of tyString, tyRef, tyOptAsRef, tySequence: unsureAsgnRef(cast[PPointer](dest), nil) of tyTuple: genericResetAux(dest, mt.node) diff --git a/lib/system/channels.nim b/lib/system/channels.nim index 1b90e245f..df6c6d41e 100644 --- a/lib/system/channels.nim +++ b/lib/system/channels.nim @@ -144,7 +144,7 @@ proc storeAux(dest, src: pointer, mt: PNimType, t: PRawChannel, for i in 0..(mt.size div mt.base.size)-1: storeAux(cast[pointer](d +% i*% mt.base.size), cast[pointer](s +% i*% mt.base.size), mt.base, t, mode) - of tyRef: + of tyRef, tyOptAsRef: var s = cast[PPointer](src)[] var x = cast[PPointer](dest) if s == nil: diff --git a/lib/system/deepcopy.nim b/lib/system/deepcopy.nim index 65ba2278c..51e138e5e 100644 --- a/lib/system/deepcopy.nim +++ b/lib/system/deepcopy.nim @@ -124,7 +124,7 @@ proc genericDeepCopyAux(dest, src: pointer, mt: PNimType; tab: var PtrTable) = for i in 0..(mt.size div mt.base.size)-1: genericDeepCopyAux(cast[pointer](d +% i*% mt.base.size), cast[pointer](s +% i*% mt.base.size), mt.base, tab) - of tyRef: + of tyRef, tyOptAsRef: let s2 = cast[PPointer](src)[] if s2 == nil: unsureAsgnRef(cast[PPointer](dest), s2) diff --git a/lib/system/gc.nim b/lib/system/gc.nim index 80aa5cf1b..a2ff72a30 100644 --- a/lib/system/gc.nim +++ b/lib/system/gc.nim @@ -349,7 +349,7 @@ proc forAllSlotsAux(dest: pointer, n: ptr TNimNode, op: WalkOp) {.benign.} = for i in 0..n.len-1: # inlined for speed if n.sons[i].kind == nkSlot: - if n.sons[i].typ.kind in {tyRef, tyString, tySequence}: + if n.sons[i].typ.kind in {tyRef, tyOptAsRef, tyString, tySequence}: doOperation(cast[PPointer](d +% n.sons[i].offset)[], op) else: forAllChildrenAux(cast[pointer](d +% n.sons[i].offset), @@ -366,7 +366,7 @@ proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) = if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.kind - of tyRef, tyString, tySequence: # leaf: + of tyRef, tyOptAsRef, tyString, tySequence: # leaf: doOperation(cast[PPointer](d)[], op) of tyObject, tyTuple: forAllSlotsAux(dest, mt.node, op) @@ -379,13 +379,13 @@ proc forAllChildren(cell: PCell, op: WalkOp) = gcAssert(cell != nil, "forAllChildren: 1") gcAssert(isAllocatedPtr(gch.region, cell), "forAllChildren: 2") gcAssert(cell.typ != nil, "forAllChildren: 3") - gcAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: 4" + gcAssert cell.typ.kind in {tyRef, tyOptAsRef, tySequence, tyString}, "forAllChildren: 4" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) else: case cell.typ.kind - of tyRef: # common case + of tyRef, tyOptAsRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: var d = cast[ByteAddress](cellToUsr(cell)) @@ -461,7 +461,7 @@ proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = incTypeSize typ, size sysAssert(allocInv(gch.region), "rawNewObj begin") acquire(gch) - gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") + gcAssert(typ.kind in {tyRef, tyOptAsRef, tyString, tySequence}, "newObj: 1") collectCT(gch) var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) #gcAssert typ.kind in {tyString, tySequence} or size >= typ.base.size, "size too small" @@ -509,7 +509,7 @@ proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = incTypeSize typ, size sysAssert(allocInv(gch.region), "newObjRC1 begin") acquire(gch) - gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") + gcAssert(typ.kind in {tyRef, tyOptAsRef, tyString, tySequence}, "newObj: 1") collectCT(gch) sysAssert(allocInv(gch.region), "newObjRC1 after collectCT") @@ -945,10 +945,10 @@ when not defined(useNimRtl): "[GC] max cycle table size: " & $gch.stat.cycleTableSize & "\n" & "[GC] max pause time [ms]: " & $(gch.stat.maxPause div 1000_000) & "\n" when nimCoroutines: - result = result & "[GC] number of stacks: " & $gch.stack.len & "\n" + result.add "[GC] number of stacks: " & $gch.stack.len & "\n" for stack in items(gch.stack): - result = result & "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & cast[pointer](stack.maxStackSize).repr & "\n" + result.add "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & cast[pointer](stack.maxStackSize).repr & "\n" else: - result = result & "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" + result.add "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" {.pop.} # profiler: off, stackTrace: off diff --git a/lib/system/gc2.nim b/lib/system/gc2.nim index 083c06fe3..6dffc323e 100644 --- a/lib/system/gc2.nim +++ b/lib/system/gc2.nim @@ -1,7 +1,7 @@ # # # Nim's Runtime Library -# (c) Copyright 2015 Andreas Rumpf +# (c) Copyright 2017 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. @@ -9,17 +9,19 @@ # Garbage Collector # -# The basic algorithm is *Deferred Reference Counting* with an incremental mark +# The basic algorithm is an incremental mark # and sweep GC to free cycles. It is hard realtime in that if you play # according to its rules, no deadline will ever be missed. - -# XXX Ensure by smart color masking that the object is not in the ZCT. +# Since this kind of collector is very bad at recycling dead objects +# early, Nim's codegen emits ``nimEscape`` calls at strategic +# places. For this to work even 'unsureAsgnRef' needs to mark things +# so that only return values need to be considered in ``nimEscape``. {.push profiler:off.} const CycleIncrease = 2 # is a multiplicative increase - InitialCycleThreshold = 4*1024*1024 # X MB because cycle checking is slow + InitialCycleThreshold = 512*1024 # start collecting after 500KB ZctThreshold = 500 # we collect garbage if the ZCT's size # reaches this threshold # this seems to be a good value @@ -40,13 +42,11 @@ type iterToProc(allObjects, ptr ObjectSpaceIter, allObjectsAsProc) const - rcIncrement = 0b1000 # so that lowest 3 bits are not touched + escapedBit = 0b1000 # so that lowest 3 bits are not touched rcBlackOrig = 0b000 rcWhiteOrig = 0b001 rcGrey = 0b010 # traditional color for incremental mark&sweep rcUnused = 0b011 - ZctFlag = 0b100 # in ZCT - rcShift = 3 # shift by rcShift to get the reference counter colorMask = 0b011 type WalkOp = enum @@ -63,13 +63,13 @@ type GcStat = object stackScans: int # number of performed stack scans (for statistics) - cycleCollections: int # number of performed full collections + completedCollections: int # number of performed full collections maxThreshold: int # max threshold that has been set maxStackSize: int # max stack size maxStackCells: int # max stack cells in ``decStack`` cycleTableSize: int # max entries in cycle table maxPause: int64 # max measured GC pause in nanoseconds - + GcStack {.final, pure.} = object when nimCoroutines: prev: ptr GcStack @@ -93,15 +93,13 @@ type cycleThreshold: int when useCellIds: idGenerator: int - zct: CellSeq # the zero count table - decStack: CellSeq # cells in the stack that are to decref again greyStack: CellSeq recGcLock: int # prevent recursion via finalizers; no thread lock when withRealTime: maxPause: Nanos # max allowed pause in nanoseconds; active if > 0 region: MemRegion # garbage collected region stat: GcStat - additionalRoots: CellSeq # dummy roots for GC_ref/unref + additionalRoots: CellSeq # explicit roots for GC_ref/unref spaceIter: ObjectSpaceIter pDumpHeapFile: pointer # File that is used for GC_dumpHeap when hasThreadSupport: @@ -113,19 +111,25 @@ var when not defined(useNimRtl): instantiateForRegion(gch.region) +template acquire(gch: GcHeap) = + when hasThreadSupport and hasSharedHeap: + acquireSys(HeapLock) + +template release(gch: GcHeap) = + when hasThreadSupport and hasSharedHeap: + releaseSys(HeapLock) + proc initGC() = when not defined(useNimRtl): gch.red = (1-gch.black) gch.cycleThreshold = InitialCycleThreshold gch.stat.stackScans = 0 - gch.stat.cycleCollections = 0 + gch.stat.completedCollections = 0 gch.stat.maxThreshold = 0 gch.stat.maxStackSize = 0 gch.stat.maxStackCells = 0 gch.stat.cycleTableSize = 0 # init the rt - init(gch.zct) - init(gch.decStack) init(gch.additionalRoots) init(gch.greyStack) when hasThreadSupport: @@ -147,11 +151,6 @@ template gcAssert(cond: bool, msg: string) = writeStackTrace() quit 1 -proc addZCT(s: var CellSeq, c: PCell) {.noinline.} = - if (c.refcount and ZctFlag) == 0: - c.refcount = c.refcount or ZctFlag - add(s, c) - proc cellToUsr(cell: PCell): pointer {.inline.} = # convert object (=pointer to refcount) to pointer to userdata result = cast[pointer](cast[ByteAddress](cell)+%ByteAddress(sizeof(Cell))) @@ -168,7 +167,7 @@ proc extGetCellType(c: pointer): PNimType {.compilerproc.} = result = usrToCell(c).typ proc internRefcount(p: pointer): int {.exportc: "getRefcount".} = - result = int(usrToCell(p).refcount) shr rcShift + result = 0 # this that has to equals zero, otherwise we have to round up UnitsPerPage: when BitsPerPage mod (sizeof(int)*8) != 0: @@ -178,6 +177,12 @@ template color(c): expr = c.refCount and colorMask template setColor(c, col) = c.refcount = c.refcount and not colorMask or col +template markAsEscaped(c: PCell) = + c.refcount = c.refcount or escapedBit + +template didEscape(c: PCell): bool = + (c.refCount and escapedBit) != 0 + proc writeCell(file: File; msg: cstring, c: PCell) = var kind = -1 if c.typ != nil: kind = ord(c.typ.kind) @@ -189,18 +194,18 @@ proc writeCell(file: File; msg: cstring, c: PCell) = else: let id = c when leakDetector: - c_fprintf(file, "%s %p %d rc=%ld color=%c from %s(%ld)\n", - msg, id, kind, c.refcount shr rcShift, col, c.filename, c.line) + c_fprintf(file, "%s %p %d escaped=%ld color=%c from %s(%ld)\n", + msg, id, kind, didEscape(c), col, c.filename, c.line) else: - c_fprintf(file, "%s %p %d rc=%ld color=%c\n", - msg, id, kind, c.refcount shr rcShift, col) + c_fprintf(file, "%s %p %d escaped=%ld color=%c\n", + msg, id, kind, didEscape(c), col) proc writeCell(msg: cstring, c: PCell) = stdout.writeCell(msg, c) proc myastToStr[T](x: T): string {.magic: "AstToStr", noSideEffect.} -template gcTrace(cell, state: expr): stmt {.immediate.} = +template gcTrace(cell, state: untyped) = when traceGC: writeCell(myastToStr(state), cell) # forward declarations: @@ -211,52 +216,17 @@ proc doOperation(p: pointer, op: WalkOp) {.benign.} proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) {.benign.} # we need the prototype here for debugging purposes -when hasThreadSupport and hasSharedHeap: - template `--`(x: expr): expr = atomicDec(x, rcIncrement) <% rcIncrement - template `++`(x: expr): stmt = discard atomicInc(x, rcIncrement) -else: - template `--`(x: expr): expr = - dec(x, rcIncrement) - x <% rcIncrement - template `++`(x: expr): stmt = inc(x, rcIncrement) - -proc prepareDealloc(cell: PCell) = - if cell.typ.finalizer != nil: - # the finalizer could invoke something that - # allocates memory; this could trigger a garbage - # collection. Since we are already collecting we - # prevend recursive entering here by a lock. - # XXX: we should set the cell's children to nil! - inc(gch.recGcLock) - (cast[Finalizer](cell.typ.finalizer))(cellToUsr(cell)) - dec(gch.recGcLock) - proc rtlAddCycleRoot(c: PCell) {.rtl, inl.} = # we MUST access gch as a global here, because this crosses DLL boundaries! discard -proc rtlAddZCT(c: PCell) {.rtl, inl.} = - # we MUST access gch as a global here, because this crosses DLL boundaries! - addZCT(gch.zct, c) - -proc decRef(c: PCell) {.inline.} = - gcAssert(isAllocatedPtr(gch.region, c), "decRef: interiorPtr") - gcAssert(c.refcount >=% rcIncrement, "decRef") - if --c.refcount: - rtlAddZCT(c) - -proc incRef(c: PCell) {.inline.} = - gcAssert(isAllocatedPtr(gch.region, c), "incRef: interiorPtr") - c.refcount = c.refcount +% rcIncrement - proc nimGCref(p: pointer) {.compilerProc.} = let cell = usrToCell(p) - incRef(cell) + markAsEscaped(cell) add(gch.additionalRoots, cell) proc nimGCunref(p: pointer) {.compilerProc.} = let cell = usrToCell(p) - decRef(cell) var L = gch.additionalRoots.len-1 var i = L let d = gch.additionalRoots.d @@ -267,6 +237,12 @@ proc nimGCunref(p: pointer) {.compilerProc.} = break dec(i) +proc nimGCunrefNoCycle(p: pointer) {.compilerProc, inline.} = + discard "can we do some freeing here?" + +proc nimGCunrefRC1(p: pointer) {.compilerProc, inline.} = + discard "can we do some freeing here?" + template markGrey(x: PCell) = if x.color != 1-gch.black and gch.phase == Phase.Marking: if not isAllocatedPtr(gch.region, x): @@ -280,59 +256,32 @@ proc GC_addCycleRoot*[T](p: ref T) {.inline.} = ## adds 'p' to the cycle candidate set for the cycle collector. It is ## necessary if you used the 'acyclic' pragma for optimization ## purposes and need to break cycles manually. - rtlAddCycleRoot(usrToCell(cast[pointer](p))) - -proc nimGCunrefNoCycle(p: pointer) {.compilerProc, inline.} = - sysAssert(allocInv(gch.region), "begin nimGCunrefNoCycle") - var c = usrToCell(p) - gcAssert(isAllocatedPtr(gch.region, c), "nimGCunrefNoCycle: isAllocatedPtr") - if --c.refcount: - rtlAddZCT(c) - sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 2") - sysAssert(allocInv(gch.region), "end nimGCunrefNoCycle 5") + discard -proc asgnRef(dest: PPointer, src: pointer) {.compilerProc, inline.} = - # the code generator calls this proc! +template asgnRefImpl = gcAssert(not isOnStack(dest), "asgnRef") # BUGFIX: first incRef then decRef! if src != nil: let s = usrToCell(src) - incRef(s) + markAsEscaped(s) markGrey(s) - if dest[] != nil: decRef(usrToCell(dest[])) dest[] = src +proc asgnRef(dest: PPointer, src: pointer) {.compilerProc, inline.} = + # the code generator calls this proc! + asgnRefImpl() + proc asgnRefNoCycle(dest: PPointer, src: pointer) {.compilerProc, inline.} = - # the code generator calls this proc if it is known at compile time that no - # cycle is possible. - gcAssert(not isOnStack(dest), "asgnRefNoCycle") - if src != nil: - var c = usrToCell(src) - ++c.refcount - markGrey(c) - if dest[] != nil: - var c = usrToCell(dest[]) - if --c.refcount: - rtlAddZCT(c) - dest[] = src + asgnRefImpl() proc unsureAsgnRef(dest: PPointer, src: pointer) {.compilerProc.} = - # unsureAsgnRef updates the reference counters only if dest is not on the + # unsureAsgnRef marks 'src' as grey only if dest is not on the # stack. It is used by the code generator if it cannot decide wether a # reference is in the stack or not (this can happen for var parameters). - if not isOnStack(dest): - if src != nil: - let s = usrToCell(src) - incRef(s) - markGrey(s) - # XXX finally use assembler for the stack checking instead! - # the test for '!= nil' is correct, but I got tired of the segfaults - # resulting from the crappy stack checking: - if cast[int](dest[]) >=% PageSize: decRef(usrToCell(dest[])) - else: - # can't be an interior pointer if it's a stack location! - gcAssert(interiorAllocatedPtr(gch.region, dest) == nil, - "stack loc AND interior pointer") + if src != nil: + let s = usrToCell(src) + markAsEscaped(s) + if not isOnStack(dest): markGrey(s) dest[] = src type @@ -366,7 +315,7 @@ proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) = if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.kind - of tyRef, tyString, tySequence: # leaf: + of tyRef, tyOptAsRef, tyString, tySequence: # leaf: doOperation(cast[PPointer](d)[], op) of tyObject, tyTuple: forAllSlotsAux(dest, mt.node, op) @@ -379,13 +328,13 @@ proc forAllChildren(cell: PCell, op: WalkOp) = gcAssert(cell != nil, "forAllChildren: 1") gcAssert(isAllocatedPtr(gch.region, cell), "forAllChildren: 2") gcAssert(cell.typ != nil, "forAllChildren: 3") - gcAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: 4" + gcAssert cell.typ.kind in {tyRef, tyOptAsRef, tySequence, tyString}, "forAllChildren: 4" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) else: case cell.typ.kind - of tyRef: # common case + of tyRef, tyOptAsRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: var d = cast[ByteAddress](cellToUsr(cell)) @@ -396,50 +345,6 @@ proc forAllChildren(cell: PCell, op: WalkOp) = GenericSeqSize), cell.typ.base, op) else: discard -proc addNewObjToZCT(res: PCell, gch: var GcHeap) {.inline.} = - # we check the last 8 entries (cache line) for a slot that could be reused. - # In 63% of all cases we succeed here! But we have to optimize the heck - # out of this small linear search so that ``newObj`` is not slowed down. - # - # Slots to try cache hit - # 1 32% - # 4 59% - # 8 63% - # 16 66% - # all slots 68% - var L = gch.zct.len - var d = gch.zct.d - when true: - # loop unrolled for performance: - template replaceZctEntry(i: expr) = - c = d[i] - if c.refcount >=% rcIncrement: - c.refcount = c.refcount and not ZctFlag - d[i] = res - return - if L > 8: - var c: PCell - replaceZctEntry(L-1) - replaceZctEntry(L-2) - replaceZctEntry(L-3) - replaceZctEntry(L-4) - replaceZctEntry(L-5) - replaceZctEntry(L-6) - replaceZctEntry(L-7) - replaceZctEntry(L-8) - add(gch.zct, res) - else: - d[L] = res - inc(gch.zct.len) - else: - for i in countdown(L-1, max(0, L-8)): - var c = d[i] - if c.refcount >=% rcIncrement: - c.refcount = c.refcount and not ZctFlag - d[i] = res - return - add(gch.zct, res) - {.push stackTrace: off, profiler:off.} proc gcInvariant*() = sysAssert(allocInv(gch.region), "injected") @@ -447,10 +352,12 @@ proc gcInvariant*() = markForDebug(gch) {.pop.} +include gc_common + proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = # generates a new object and sets its reference counter to 0 sysAssert(allocInv(gch.region), "rawNewObj begin") - gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") + gcAssert(typ.kind in {tyRef, tyOptAsRef, tyString, tySequence}, "newObj: 1") collectCT(gch) var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) gcAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") @@ -461,10 +368,8 @@ proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = res.filename = framePtr.prev.filename res.line = framePtr.prev.line # refcount is zero, color is black, but mark it to be in the ZCT - res.refcount = ZctFlag or allocColor() + res.refcount = allocColor() sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") - # its refcount is zero, so add it to the ZCT: - addNewObjToZCT(res, gch) when logGC: writeCell("new cell", res) gcTrace(res, csAllocated) when useCellIds: @@ -493,95 +398,38 @@ proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.} = when defined(memProfiler): nimProfile(size) proc newObjRC1(typ: PNimType, size: int): pointer {.compilerRtl.} = - # generates a new object and sets its reference counter to 1 - sysAssert(allocInv(gch.region), "newObjRC1 begin") - gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") - collectCT(gch) - sysAssert(allocInv(gch.region), "newObjRC1 after collectCT") - - var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) - sysAssert(allocInv(gch.region), "newObjRC1 after rawAlloc") - sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") - # now it is buffered in the ZCT - res.typ = typ - when leakDetector: - if framePtr != nil and framePtr.prev != nil: - res.filename = framePtr.prev.filename - res.line = framePtr.prev.line - res.refcount = rcIncrement or allocColor() # refcount is 1 - sysAssert(isAllocatedPtr(gch.region, res), "newObj: 3") - when logGC: writeCell("new cell", res) - gcTrace(res, csAllocated) - when useCellIds: - inc gch.idGenerator - res.id = gch.idGenerator - result = cellToUsr(res) - zeroMem(result, size) - sysAssert(allocInv(gch.region), "newObjRC1 end") - when defined(memProfiler): nimProfile(size) + result = newObj(typ, size) proc newSeqRC1(typ: PNimType, len: int): pointer {.compilerRtl.} = - let size = addInt(mulInt(len, typ.base.size), GenericSeqSize) - result = newObjRC1(typ, size) - cast[PGenericSeq](result).len = len - cast[PGenericSeq](result).reserved = len - when defined(memProfiler): nimProfile(size) + result = newSeq(typ, len) proc growObj(old: pointer, newsize: int, gch: var GcHeap): pointer = + acquire(gch) collectCT(gch) var ol = usrToCell(old) - gcAssert(isAllocatedPtr(gch.region, ol), "growObj: freed pointer?") - sysAssert(ol.typ != nil, "growObj: 1") gcAssert(ol.typ.kind in {tyString, tySequence}, "growObj: 2") - sysAssert(allocInv(gch.region), "growObj begin") var res = cast[PCell](rawAlloc(gch.region, newsize + sizeof(Cell))) var elemSize = 1 if ol.typ.kind != tyString: elemSize = ol.typ.base.size + incTypeSize ol.typ, newsize - let oldsize = cast[PGenericSeq](old).len*elemSize + GenericSeqSize + var oldsize = cast[PGenericSeq](old).len*elemSize + GenericSeqSize copyMem(res, ol, oldsize + sizeof(Cell)) - zeroMem(cast[pointer](cast[ByteAddress](res) +% oldsize +% sizeof(Cell)), + zeroMem(cast[pointer](cast[ByteAddress](res)+% oldsize +% sizeof(Cell)), newsize-oldsize) sysAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "growObj: 3") - # This can be wrong for intermediate temps that are nevertheless on the - # heap because of lambda lifting: - #gcAssert(res.refcount shr rcShift <=% 1, "growObj: 4") - when logGC: - writeCell("growObj old cell", ol) - writeCell("growObj new cell", res) - gcTrace(ol, csZctFreed) - gcTrace(res, csAllocated) - when reallyDealloc: - sysAssert(allocInv(gch.region), "growObj before dealloc") - if ol.refcount shr rcShift <=% 1: - # free immediately to save space: - if (ol.refcount and ZctFlag) != 0: - var j = gch.zct.len-1 - var d = gch.zct.d - while j >= 0: - if d[j] == ol: - d[j] = res - break - dec(j) - rawDealloc(gch.region, ol) + when false: + # this is wrong since seqs can be shared via 'shallow': + when reallyDealloc: rawDealloc(gch.region, ol) else: - # we split the old refcount in 2 parts. XXX This is still not entirely - # correct if the pointer that receives growObj's result is on the stack. - # A better fix would be to emit the location specific write barrier for - # 'growObj', but this is lots of more work and who knows what new problems - # this would create. - res.refcount = rcIncrement or allocColor() - decRef(ol) - else: - sysAssert(ol.typ != nil, "growObj: 5") - zeroMem(ol, sizeof(Cell)) + zeroMem(ol, sizeof(Cell)) when useCellIds: inc gch.idGenerator res.id = gch.idGenerator + release(gch) result = cellToUsr(res) - sysAssert(allocInv(gch.region), "growObj end") when defined(memProfiler): nimProfile(newsize-oldsize) proc growObj(old: pointer, newsize: int): pointer {.rtl.} = @@ -637,12 +485,13 @@ proc GC_dumpHeap*(file: File) = ## can be translated into "dot" syntax via the "heapdump2dot" tool. gch.pDumpHeapFile = file var spaceIter: ObjectSpaceIter - var d = gch.decStack.d - for i in 0 .. < gch.decStack.len: - if isAllocatedPtr(gch.region, d[i]): - c_fprintf(file, "onstack %p\n", d[i]) - else: - c_fprintf(file, "onstack_invalid %p\n", d[i]) + when false: + var d = gch.decStack.d + for i in 0 .. < gch.decStack.len: + if isAllocatedPtr(gch.region, d[i]): + c_fprintf(file, "onstack %p\n", d[i]) + else: + c_fprintf(file, "onstack_invalid %p\n", d[i]) for i in 0 .. < globalMarkersLen: globalMarkers[i]() while true: let x = allObjectsAsProc(gch.region, addr spaceIter) @@ -667,14 +516,6 @@ proc GC_dumpHeap() = proc freeCyclicCell(gch: var GcHeap, c: PCell) = gcAssert(isAllocatedPtr(gch.region, c), "freeCyclicCell: freed pointer?") - - var d = gch.decStack.d - for i in 0..gch.decStack.len-1: - if d[i] == c: - writeCell("freeing ", c) - GC_dumpHeap() - gcAssert d[i] != c, "wtf man, freeing obviously alive stuff?!!" - prepareDealloc(c) gcTrace(c, csCycFreed) when logGC: writeCell("cycle collector dealloc cell", c) @@ -713,15 +554,6 @@ proc markRoot(gch: var GcHeap, c: PCell) {.inline.} = if c.color == 1-gch.black: c.setColor(rcGrey) add(gch.greyStack, c) - elif c.color == rcGrey: - var isGrey = false - var d = gch.decStack.d - for i in 0..gch.decStack.len-1: - if d[i] == c: - isGrey = true - break - if not isGrey: - gcAssert false, "markRoot: root is already grey?!" proc markIncremental(gch: var GcHeap): bool = var L = addr(gch.greyStack.len) @@ -741,30 +573,14 @@ proc markIncremental(gch: var GcHeap): bool = c.setColor(gch.black) forAllChildren(c, waMarkGrey) elif c.color == (1-gch.black): - gcAssert false, "wtf why are there white object in the greystack?" + gcAssert false, "wtf why are there white objects in the greystack?" checkTime() gcAssert gch.greyStack.len == 0, "markIncremental: greystack not empty " - - # assert that all local roots are black by now: - var d = gch.decStack.d - var errors = false - for i in 0..gch.decStack.len-1: - gcAssert(isAllocatedPtr(gch.region, d[i]), "markIncremental: isAllocatedPtr 2") - if d[i].color != gch.black: - writeCell("not black ", d[i]) - errors = true - gcAssert(not errors, "wtf something wrong hre") result = true proc markGlobals(gch: var GcHeap) = for i in 0 .. < globalMarkersLen: globalMarkers[i]() -proc markLocals(gch: var GcHeap) = - var d = gch.decStack.d - for i in 0 .. < gch.decStack.len: - sysAssert isAllocatedPtr(gch.region, d[i]), "markLocals" - markRoot(gch, d[i]) - proc doOperation(p: pointer, op: WalkOp) = if p == nil: return var c: PCell = usrToCell(p) @@ -776,11 +592,7 @@ proc doOperation(p: pointer, op: WalkOp) = #if not isAllocatedPtr(gch.region, c): # c_fprintf(stdout, "[GC] decref bug: %p", c) gcAssert(isAllocatedPtr(gch.region, c), "decRef: waZctDecRef") - gcAssert(c.refcount >=% rcIncrement, "doOperation 2") - #c.refcount = c.refcount -% rcIncrement - when logGC: writeCell("decref (from doOperation)", c) - decRef(c) - #if c.refcount <% rcIncrement: addZCT(gch.zct, c) + discard "use me for nimEscape?" of waMarkGlobal: template handleRoot = if gch.dumpHeapFile.isNil: @@ -811,107 +623,54 @@ proc doOperation(p: pointer, op: WalkOp) = proc nimGCvisit(d: pointer, op: int) {.compilerRtl.} = doOperation(d, WalkOp(op)) -proc collectZCT(gch: var GcHeap): bool {.benign.} - -proc collectCycles(gch: var GcHeap): bool = - when hasThreadSupport: - for c in gch.toDispose: - nimGCunref(c) +proc gcMark(gch: var GcHeap, p: pointer) {.inline.} = + # the addresses are not as cells on the stack, so turn them to cells: + sysAssert(allocInv(gch.region), "gcMark begin") + var cell = usrToCell(p) + var c = cast[ByteAddress](cell) + if c >% PageSize: + # fast check: does it look like a cell? + var objStart = cast[PCell](interiorAllocatedPtr(gch.region, cell)) + if objStart != nil: + # mark the cell: + markRoot(gch, objStart) + sysAssert(allocInv(gch.region), "gcMark end") - # ensure the ZCT 'color' is not used: - while gch.zct.len > 0: discard collectZCT(gch) +proc markStackAndRegisters(gch: var GcHeap) {.noinline, cdecl.} = + forEachStackSlot(gch, gcMark) +proc collectALittle(gch: var GcHeap): bool = case gch.phase of Phase.None: - gch.phase = Phase.Marking - markGlobals(gch) - - c_fprintf(stdout, "collectCycles: introduced bug E %ld\n", gch.phase) - discard allocInv(gch.region) + if getOccupiedMem(gch.region) >= gch.cycleThreshold: + gch.phase = Phase.Marking + markGlobals(gch) + result = collectALittle(gch) + #when false: c_fprintf(stdout, "collectALittle: introduced bug E %ld\n", gch.phase) + #discard allocInv(gch.region) of Phase.Marking: - # since locals do not have a write barrier, we need - # to keep re-scanning them :-( but there is really nothing we can - # do about that. - markLocals(gch) + when hasThreadSupport: + for c in gch.toDispose: + nimGCunref(c) + prepareForInteriorPointerChecking(gch.region) + markStackAndRegisters(gch) + inc(gch.stat.stackScans) if markIncremental(gch): gch.phase = Phase.Sweeping gch.red = 1 - gch.red of Phase.Sweeping: gcAssert gch.greyStack.len == 0, "greystack not empty" + when hasThreadSupport: + for c in gch.toDispose: + nimGCunref(c) if sweep(gch): gch.phase = Phase.None # flip black/white meanings: gch.black = 1 - gch.black gcAssert gch.red == 1 - gch.black, "red color is wrong" + inc(gch.stat.completedCollections) result = true -proc gcMark(gch: var GcHeap, p: pointer) {.inline.} = - # the addresses are not as cells on the stack, so turn them to cells: - sysAssert(allocInv(gch.region), "gcMark begin") - var cell = usrToCell(p) - var c = cast[ByteAddress](cell) - if c >% PageSize: - # fast check: does it look like a cell? - var objStart = cast[PCell](interiorAllocatedPtr(gch.region, cell)) - if objStart != nil: - # mark the cell: - objStart.refcount = objStart.refcount +% rcIncrement - add(gch.decStack, objStart) - sysAssert(allocInv(gch.region), "gcMark end") - -include gc_common - -proc markStackAndRegisters(gch: var GcHeap) {.noinline, cdecl.} = - forEachStackSlot(gch, gcMark) - -proc collectZCT(gch: var GcHeap): bool = - # Note: Freeing may add child objects to the ZCT! So essentially we do - # deep freeing, which is bad for incremental operation. In order to - # avoid a deep stack, we move objects to keep the ZCT small. - # This is performance critical! - var L = addr(gch.zct.len) - takeStartTime(100) - - while L[] > 0: - var c = gch.zct.d[0] - sysAssert(isAllocatedPtr(gch.region, c), "CollectZCT: isAllocatedPtr") - # remove from ZCT: - gcAssert((c.refcount and ZctFlag) == ZctFlag, "collectZCT") - - c.refcount = c.refcount and not ZctFlag - gch.zct.d[0] = gch.zct.d[L[] - 1] - dec(L[]) - takeTime() - if c.refcount <% rcIncrement and c.color != rcGrey: - # It may have a RC > 0, if it is in the hardware stack or - # it has not been removed yet from the ZCT. This is because - # ``incref`` does not bother to remove the cell from the ZCT - # as this might be too slow. - # In any case, it should be removed from the ZCT. But not - # freed. **KEEP THIS IN MIND WHEN MAKING THIS INCREMENTAL!** - when logGC: writeCell("zct dealloc cell", c) - gcTrace(c, csZctFreed) - # We are about to free the object, call the finalizer BEFORE its - # children are deleted as well, because otherwise the finalizer may - # access invalid memory. This is done by prepareDealloc(): - prepareDealloc(c) - forAllChildren(c, waZctDecRef) - when reallyDealloc: - sysAssert(allocInv(gch.region), "collectZCT: rawDealloc") - rawDealloc(gch.region, c) - else: - sysAssert(c.typ != nil, "collectZCT 2") - zeroMem(c, sizeof(Cell)) - checkTime() - result = true - -proc unmarkStackAndRegisters(gch: var GcHeap) = - var d = gch.decStack.d - for i in 0..gch.decStack.len-1: - sysAssert isAllocatedPtr(gch.region, d[i]), "unmarkStackAndRegisters" - decRef(d[i]) - gch.decStack.len = 0 - proc collectCTBody(gch: var GcHeap) = when withRealTime: let t0 = getticks() @@ -919,22 +678,12 @@ proc collectCTBody(gch: var GcHeap) = when not nimCoroutines: gch.stat.maxStackSize = max(gch.stat.maxStackSize, stackSize()) - sysAssert(gch.decStack.len == 0, "collectCT") - prepareForInteriorPointerChecking(gch.region) - markStackAndRegisters(gch) - gch.stat.maxStackCells = max(gch.stat.maxStackCells, gch.decStack.len) - inc(gch.stat.stackScans) - if collectZCT(gch): - when cycleGC: - if getOccupiedMem(gch.region) >= gch.cycleThreshold or alwaysCycleGC: - if collectCycles(gch): - inc(gch.stat.cycleCollections) - gch.cycleThreshold = max(InitialCycleThreshold, getOccupiedMem() * - CycleIncrease) - gch.stat.maxThreshold = max(gch.stat.maxThreshold, gch.cycleThreshold) - unmarkStackAndRegisters(gch) + #gch.stat.maxStackCells = max(gch.stat.maxStackCells, gch.decStack.len) + if collectALittle(gch): + gch.cycleThreshold = max(InitialCycleThreshold, getOccupiedMem() * + CycleIncrease) + gch.stat.maxThreshold = max(gch.stat.maxThreshold, gch.cycleThreshold) sysAssert(allocInv(gch.region), "collectCT: end") - when withRealTime: let duration = getticks() - t0 gch.stat.maxPause = max(gch.stat.maxPause, duration) @@ -955,7 +704,7 @@ proc collectCT(gch: var GcHeap) = let stackMarkCosts = max(currentStackSizes() div (16*sizeof(int)), ZctThreshold) else: let stackMarkCosts = max(stackSize() div (16*sizeof(int)), ZctThreshold) - if (gch.zct.len >= stackMarkCosts or (cycleGC and + if (gch.greyStack.len >= stackMarkCosts or (cycleGC and getOccupiedMem(gch.region)>=gch.cycleThreshold) or alwaysGC) and gch.recGcLock == 0: collectCTBody(gch) @@ -969,10 +718,9 @@ when withRealTime: proc GC_step(gch: var GcHeap, us: int, strongAdvice: bool) = gch.maxPause = us.toNano - if (gch.zct.len >= ZctThreshold or (cycleGC and - getOccupiedMem(gch.region)>=gch.cycleThreshold) or alwaysGC) or - strongAdvice: - collectCTBody(gch) + #if (getOccupiedMem(gch.region)>=gch.cycleThreshold) or + # alwaysGC or strongAdvice: + collectCTBody(gch) proc GC_step*(us: int, strongAdvice = false, stackSize = -1) {.noinline.} = if stackSize >= 0: @@ -1010,12 +758,8 @@ when not defined(useNimRtl): proc GC_setStrategy(strategy: GC_Strategy) = discard - proc GC_enableMarkAndSweep() = - gch.cycleThreshold = InitialCycleThreshold - - proc GC_disableMarkAndSweep() = - gch.cycleThreshold = high(gch.cycleThreshold)-1 - # set to the max value to suppress the cycle detector + proc GC_enableMarkAndSweep() = discard + proc GC_disableMarkAndSweep() = discard proc GC_fullCollect() = var oldThreshold = gch.cycleThreshold @@ -1029,17 +773,17 @@ when not defined(useNimRtl): "[GC] occupied memory: " & $(getOccupiedMem()) & "\n" & "[GC] stack scans: " & $gch.stat.stackScans & "\n" & "[GC] stack cells: " & $gch.stat.maxStackCells & "\n" & - "[GC] cycle collections: " & $gch.stat.cycleCollections & "\n" & + "[GC] completed collections: " & $gch.stat.completedCollections & "\n" & "[GC] max threshold: " & $gch.stat.maxThreshold & "\n" & - "[GC] zct capacity: " & $gch.zct.cap & "\n" & + "[GC] grey stack capacity: " & $gch.greyStack.cap & "\n" & "[GC] max cycle table size: " & $gch.stat.cycleTableSize & "\n" & - "[GC] max pause time [ms]: " & $(gch.stat.maxPause div 1000_000) + "[GC] max pause time [ms]: " & $(gch.stat.maxPause div 1000_000) & "\n" when nimCoroutines: - result = result & "[GC] number of stacks: " & $gch.stack.len & "\n" + result.add "[GC] number of stacks: " & $gch.stack.len & "\n" for stack in items(gch.stack): - result = result & "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & $stack.maxStackSize & "\n" + result.add "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & $stack.maxStackSize & "\n" else: - result = result & "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" + result.add "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" GC_enable() {.pop.} diff --git a/lib/system/gc_common.nim b/lib/system/gc_common.nim index 220331e96..484a4db9a 100644 --- a/lib/system/gc_common.nim +++ b/lib/system/gc_common.nim @@ -373,12 +373,22 @@ proc deallocHeap*(runFinalizers = true; allowGcAfterwards = true) = ## is true. If ``allowGcAfterwards`` is true, a minimal amount of allocation ## happens to ensure the GC can continue to work after the call ## to ``deallocHeap``. + template deallocCell(x) = + if isCell(x): + # cast to PCell is correct here: + prepareDealloc(cast[PCell](x)) + if runFinalizers: - for x in allObjects(gch.region): - if isCell(x): - # cast to PCell is correct here: - var c = cast[PCell](x) - prepareDealloc(c) + when not declared(allObjectsAsProc): + for x in allObjects(gch.region): + deallocCell(x) + else: + var spaceIter: ObjectSpaceIter + while true: + let x = allObjectsAsProc(gch.region, addr spaceIter) + if spaceIter.state < 0: break + deallocCell(x) + deallocOsPages(gch.region) zeroMem(addr gch.region, sizeof(gch.region)) if allowGcAfterwards: diff --git a/lib/system/gc_ms.nim b/lib/system/gc_ms.nim index e03140d05..cfc0dfa8a 100644 --- a/lib/system/gc_ms.nim +++ b/lib/system/gc_ms.nim @@ -252,7 +252,7 @@ proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) = if dest == nil: return # nothing to do if ntfNoRefs notin mt.flags: case mt.kind - of tyRef, tyString, tySequence: # leaf: + of tyRef, tyOptAsRef, tyString, tySequence: # leaf: doOperation(cast[PPointer](d)[], op) of tyObject, tyTuple: forAllSlotsAux(dest, mt.node, op) @@ -264,13 +264,13 @@ proc forAllChildrenAux(dest: pointer, mt: PNimType, op: WalkOp) = proc forAllChildren(cell: PCell, op: WalkOp) = gcAssert(cell != nil, "forAllChildren: 1") gcAssert(cell.typ != nil, "forAllChildren: 2") - gcAssert cell.typ.kind in {tyRef, tySequence, tyString}, "forAllChildren: 3" + gcAssert cell.typ.kind in {tyRef, tyOptAsRef, tySequence, tyString}, "forAllChildren: 3" let marker = cell.typ.marker if marker != nil: marker(cellToUsr(cell), op.int) else: case cell.typ.kind - of tyRef: # common case + of tyRef, tyOptAsRef: # common case forAllChildrenAux(cellToUsr(cell), cell.typ.base, op) of tySequence: var d = cast[ByteAddress](cellToUsr(cell)) @@ -285,7 +285,7 @@ proc rawNewObj(typ: PNimType, size: int, gch: var GcHeap): pointer = # generates a new object and sets its reference counter to 0 incTypeSize typ, size acquire(gch) - gcAssert(typ.kind in {tyRef, tyString, tySequence}, "newObj: 1") + gcAssert(typ.kind in {tyRef, tyOptAsRef, tyString, tySequence}, "newObj: 1") collectCT(gch) var res = cast[PCell](rawAlloc(gch.region, size + sizeof(Cell))) gcAssert((cast[ByteAddress](res) and (MemAlign-1)) == 0, "newObj: 2") @@ -526,10 +526,10 @@ when not defined(useNimRtl): "[GC] max threshold: " & $gch.stat.maxThreshold & "\n" & "[GC] freed objects: " & $gch.stat.freedObjects & "\n" when nimCoroutines: - result = result & "[GC] number of stacks: " & $gch.stack.len & "\n" + result.add "[GC] number of stacks: " & $gch.stack.len & "\n" for stack in items(gch.stack): - result = result & "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & $stack.maxStackSize & "\n" + result.add "[GC] stack " & stack.bottom.repr & "[GC] max stack size " & $stack.maxStackSize & "\n" else: - result = result & "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" + result.add "[GC] max stack size: " & $gch.stat.maxStackSize & "\n" {.pop.} diff --git a/lib/system/hti.nim b/lib/system/hti.nim index 69f4f9508..45b1d1cd3 100644 --- a/lib/system/hti.nim +++ b/lib/system/hti.nim @@ -62,6 +62,21 @@ type tyUInt16, tyUInt32, tyUInt64, + tyOptAsRef, tyUnused1, tyUnused2, + tyVarargsHidden, + tyUnusedHidden, + tyProxyHidden, + tyBuiltInTypeClassHidden, + tyUserTypeClassHidden, + tyUserTypeClassInstHidden, + tyCompositeTypeClassHidden, + tyInferredHidden, + tyAndHidden, tyOrHidden, tyNotHidden, + tyAnythingHidden, + tyStaticHidden, + tyFromExprHidden, + tyOpt, + tyVoidHidden TNimNodeKind = enum nkNone, nkSlot, nkList, nkCase TNimNode {.codegenType.} = object diff --git a/lib/system/mmdisp.nim b/lib/system/mmdisp.nim index d2160fdac..824934966 100644 --- a/lib/system/mmdisp.nim +++ b/lib/system/mmdisp.nim @@ -564,7 +564,11 @@ else: when not declared(nimNewSeqOfCap): proc nimNewSeqOfCap(typ: PNimType, cap: int): pointer {.compilerproc.} = - result = newObj(typ, addInt(mulInt(cap, typ.base.size), GenericSeqSize)) + let s = addInt(mulInt(cap, typ.base.size), GenericSeqSize) + when declared(newObjNoInit): + result = if ntfNoRefs in typ.base.flags: newObjNoInit(typ, s) else: newObj(typ, s) + else: + result = newObj(typ, s) cast[PGenericSeq](result).len = 0 cast[PGenericSeq](result).reserved = cap diff --git a/lib/system/nimscript.nim b/lib/system/nimscript.nim index 73bb91fef..f5b9cf3ed 100644 --- a/lib/system/nimscript.nim +++ b/lib/system/nimscript.nim @@ -11,6 +11,15 @@ # Nim's configuration system now uses Nim for scripting. This module provides # a few things that are required for this to work. +const + buildOS* {.magic: "BuildOS".}: string = "" + ## The OS this build is running on. Can be different from ``system.hostOS`` + ## for cross compilations. + + buildCPU* {.magic: "BuildCPU".}: string = "" + ## The CPU this build is running on. Can be different from ``system.hostCPU`` + ## for cross compilations. + template builtin = discard # We know the effects better than the compiler: diff --git a/lib/system/sysstr.nim b/lib/system/sysstr.nim index c3150cb07..90201202c 100644 --- a/lib/system/sysstr.nim +++ b/lib/system/sysstr.nim @@ -95,6 +95,9 @@ proc cstrToNimstr(str: cstring): NimString {.compilerRtl.} = if str == nil: NimString(nil) else: toNimStr(str, str.len) +template wasMoved(x: NimString): bool = false +# (x.reserved and seqShallowFlag) != 0 + proc copyString(src: NimString): NimString {.compilerRtl.} = if src != nil: if (src.reserved and seqShallowFlag) != 0: @@ -103,6 +106,16 @@ proc copyString(src: NimString): NimString {.compilerRtl.} = result = rawNewStringNoInit(src.len) result.len = src.len copyMem(addr(result.data), addr(src.data), src.len + 1) + sysAssert((seqShallowFlag and result.reserved) == 0, "copyString") + when defined(nimShallowStrings): + if (src.reserved and strlitFlag) != 0: + result.reserved = (result.reserved and not strlitFlag) or seqShallowFlag + +proc newOwnedString(src: NimString; n: int): NimString = + result = rawNewStringNoInit(n) + result.len = n + copyMem(addr(result.data), addr(src.data), n) + result.data[n] = '\0' proc copyStringRC1(src: NimString): NimString {.compilerRtl.} = if src != nil: @@ -116,6 +129,10 @@ proc copyStringRC1(src: NimString): NimString {.compilerRtl.} = result = rawNewStringNoInit(src.len) result.len = src.len copyMem(addr(result.data), addr(src.data), src.len + 1) + sysAssert((seqShallowFlag and result.reserved) == 0, "copyStringRC1") + when defined(nimShallowStrings): + if (src.reserved and strlitFlag) != 0: + result.reserved = (result.reserved and not strlitFlag) or seqShallowFlag proc copyDeepString(src: NimString): NimString {.inline.} = if src != nil: @@ -140,9 +157,12 @@ proc addChar(s: NimString, c: char): NimString = # is compilerproc! result = s if result.len >= result.space: - result.reserved = resize(result.space) + let r = resize(result.space) result = cast[NimString](growObj(result, - sizeof(TGenericSeq) + result.reserved + 1)) + sizeof(TGenericSeq) + r + 1)) + result.reserved = r + elif wasMoved(s): + result = newOwnedString(s, s.len) result.data[result.len] = c result.data[result.len+1] = '\0' inc(result.len) @@ -179,7 +199,7 @@ proc addChar(s: NimString, c: char): NimString = # s = rawNewString(0); proc resizeString(dest: NimString, addlen: int): NimString {.compilerRtl.} = - if dest.len + addlen <= dest.space: + if dest.len + addlen <= dest.space and not wasMoved(dest): result = dest else: # slow path: var sp = max(resize(dest.space), dest.len + addlen) @@ -200,7 +220,9 @@ proc appendChar(dest: NimString, c: char) {.compilerproc, inline.} = proc setLengthStr(s: NimString, newLen: int): NimString {.compilerRtl.} = var n = max(newLen, 0) - if n <= s.space: + if wasMoved(s): + result = newOwnedString(s, n) + elif n <= s.space: result = s else: result = resizeString(s, n) @@ -218,26 +240,29 @@ proc incrSeq(seq: PGenericSeq, elemSize: int): PGenericSeq {.compilerProc.} = # seq[seq->len-1] = x; result = seq if result.len >= result.space: - result.reserved = resize(result.space) - result = cast[PGenericSeq](growObj(result, elemSize * result.reserved + + let r = resize(result.space) + result = cast[PGenericSeq](growObj(result, elemSize * r + GenericSeqSize)) + result.reserved = r inc(result.len) proc incrSeqV2(seq: PGenericSeq, elemSize: int): PGenericSeq {.compilerProc.} = # incrSeq version 2 result = seq if result.len >= result.space: - result.reserved = resize(result.space) - result = cast[PGenericSeq](growObj(result, elemSize * result.reserved + + let r = resize(result.space) + result = cast[PGenericSeq](growObj(result, elemSize * r + GenericSeqSize)) + result.reserved = r proc setLengthSeq(seq: PGenericSeq, elemSize, newLen: int): PGenericSeq {. compilerRtl.} = result = seq if result.space < newLen: - result.reserved = max(resize(result.space), newLen) - result = cast[PGenericSeq](growObj(result, elemSize * result.reserved + + let r = max(resize(result.space), newLen) + result = cast[PGenericSeq](growObj(result, elemSize * r + GenericSeqSize)) + result.reserved = r elif newLen < result.len: # we need to decref here, otherwise the GC leaks! when not defined(boehmGC) and not defined(nogc) and diff --git a/lib/system/threads.nim b/lib/system/threads.nim index a7a811844..96c045e6b 100644 --- a/lib/system/threads.nim +++ b/lib/system/threads.nim @@ -127,7 +127,8 @@ elif defined(genode): proc initThread(s: var SysThread, stackSize: culonglong, entry: GenodeThreadProc, - arg: pointer) {. + arg: pointer, + affinity: cuint) {. importcpp: "#.initThread(genodeEnv, @)".} proc threadVarAlloc(): ThreadVarSlot = 0 @@ -567,6 +568,9 @@ when hostOS == "windows": setThreadAffinityMask(t.sys, uint(1 shl cpu)) elif defined(genode): + var affinityOffset: cuint = 1 + # CPU affinity offset for next thread, safe to roll-over + proc createThread*[TArg](t: var Thread[TArg], tp: proc (arg: TArg) {.thread, nimcall.}, param: TArg) = @@ -577,7 +581,8 @@ elif defined(genode): when hasSharedHeap: t.stackSize = ThreadStackSize t.sys.initThread( ThreadStackSize.culonglong, - threadProcWrapper[TArg], addr(t)) + threadProcWrapper[TArg], addr(t), affinityOffset) + inc affinityOffset proc pinToCpu*[Arg](t: var Thread[Arg]; cpu: Natural) = {.hint: "cannot change Genode thread CPU affinity after initialization".} |