From 6c0185d4b7a9b38fa246c47c6d9baf3633e880d0 Mon Sep 17 00:00:00 2001 From: Yuriy Glukhov Date: Wed, 16 May 2018 13:04:08 +0300 Subject: Allow better optimisations by removing NOINLINE from module init procs --- compiler/cgen.nim | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/compiler/cgen.nim b/compiler/cgen.nim index 133e86cea..79bcf0491 100644 --- a/compiler/cgen.nim +++ b/compiler/cgen.nim @@ -1115,8 +1115,8 @@ proc registerModuleToMain(g: BModuleList; m: PSym) = var init = m.getInitName datInit = m.getDatInitName - addf(g.mainModProcs, "NIM_EXTERNC N_NOINLINE(void, $1)(void);$N", [init]) - addf(g.mainModProcs, "NIM_EXTERNC N_NOINLINE(void, $1)(void);$N", [datInit]) + addf(g.mainModProcs, "N_LIB_PRIVATE N_NIMCALL(void, $1)(void);$N", [init]) + addf(g.mainModProcs, "N_LIB_PRIVATE N_NIMCALL(void, $1)(void);$N", [datInit]) if sfSystemModule notin m.flags: addf(g.mainDatInit, "\t$1();$N", [datInit]) let initCall = "\t$1();$N" % [init] @@ -1127,7 +1127,7 @@ proc registerModuleToMain(g: BModuleList; m: PSym) = proc genInitCode(m: BModule) = var initname = getInitName(m.module) - var prc = "NIM_EXTERNC N_NOINLINE(void, $1)(void) {$N" % [initname] + var prc = "N_LIB_PRIVATE N_NIMCALL(void, $1)(void) {$N" % [initname] if m.typeNodes > 0: appcg(m, m.s[cfsTypeInit1], "static #TNimNode $1[$2];$n", [m.typeNodesName, rope(m.typeNodes)]) @@ -1169,7 +1169,7 @@ proc genInitCode(m: BModule) = add(prc, deinitGCFrame(m.initProc)) addf(prc, "}$N$N", []) - prc.addf("NIM_EXTERNC N_NOINLINE(void, $1)(void) {$N", + prc.addf("N_LIB_PRIVATE N_NIMCALL(void, $1)(void) {$N", [getDatInitName(m.module)]) for i in cfsTypeInit1..cfsDynLibInit: -- cgit 1.4.1-2-gfad0 From 173c92d374323f6fbbecae2ac344e6062dcfa351 Mon Sep 17 00:00:00 2001 From: data-man Date: Thu, 17 May 2018 19:54:41 +0300 Subject: Fixes factorial's bug --- lib/pure/math.nim | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/lib/pure/math.nim b/lib/pure/math.nim index 5f3240e00..9e590debc 100644 --- a/lib/pure/math.nim +++ b/lib/pure/math.nim @@ -41,7 +41,7 @@ proc fac*(n: int): int = createFactTable[13]() else: createFactTable[21]() - assert(n > 0, $n & " must not be negative.") + assert(n >= 0, $n & " must not be negative.") assert(n < factTable.len, $n & " is too large to look up in the table") factTable[n] @@ -560,3 +560,14 @@ when isMainModule: assert sgn(Inf) == 1 assert sgn(NaN) == 0 + block: # fac() tests + try: + discard fac(-1) + except AssertionError: + discard + + doAssert fac(0) == 1 + doAssert fac(1) == 1 + doAssert fac(2) == 2 + doAssert fac(3) == 6 + doAssert fac(4) == 24 -- cgit 1.4.1-2-gfad0 From 4b3ad4f00cf8b5080c38248e32d3de27badb4101 Mon Sep 17 00:00:00 2001 From: Araq Date: Fri, 18 May 2018 01:35:09 +0200 Subject: keep algorithm.nim warning free --- lib/pure/algorithm.nim | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 22793ab1c..2b668d1ca 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -520,15 +520,15 @@ when isMainModule: block testBinarySearch: var noData: seq[int] - doAssert binarySearch(noData, 7) == -1 + doAssert binarySearch(noData, 7) == -1 let oneData = @[1] - doAssert binarySearch(oneData, 1) == 0 - doAssert binarySearch(onedata, 7) == -1 + doAssert binarySearch(oneData, 1) == 0 + doAssert binarySearch(onedata, 7) == -1 let someData = @[1,3,4,7] - doAssert binarySearch(someData, 1) == 0 - doAssert binarySearch(somedata, 7) == 3 + doAssert binarySearch(someData, 1) == 0 + doAssert binarySearch(somedata, 7) == 3 doAssert binarySearch(someData, -1) == -1 - doAssert binarySearch(someData, 5) == -1 + doAssert binarySearch(someData, 5) == -1 doAssert binarySearch(someData, 13) == -1 let moreData = @[1,3,5,7,4711] doAssert binarySearch(moreData, -1) == -1 -- cgit 1.4.1-2-gfad0 From 4e63f0c267c43821b7d471c8bb56f21c5d5b6d6f Mon Sep 17 00:00:00 2001 From: Araq Date: Fri, 18 May 2018 01:35:53 +0200 Subject: keep unicode.nim warning free --- lib/pure/unicode.nim | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/lib/pure/unicode.nim b/lib/pure/unicode.nim index cc4d28f5b..bfd01be55 100644 --- a/lib/pure/unicode.nim +++ b/lib/pure/unicode.nim @@ -1826,8 +1826,8 @@ when isMainModule: doAssert(runeSubStr(s, 17, 1) == "€") # echo runeStrAtPos(s, 18) # index error - doAssert(runeSubStr(s, 0) == "Hänsel ««: 10,00€") - doAssert(runeSubStr(s, -18) == "Hänsel ««: 10,00€") + doAssert(runeSubStr(s, 0) == "Hänsel ««: 10,00€") + doAssert(runeSubStr(s, -18) == "Hänsel ««: 10,00€") doAssert(runeSubStr(s, 10) == ": 10,00€") doAssert(runeSubStr(s, 18) == "") doAssert(runeSubStr(s, 0, 10) == "Hänsel ««") @@ -1840,7 +1840,7 @@ when isMainModule: doAssert(runeSubStr(s, -6, 5) == "10,00") doAssert(runeSubStr(s, -6, -1) == "10,00") - doAssert(runeSubStr(s, 0, 100) == "Hänsel ««: 10,00€") - doAssert(runeSubStr(s, -100, 100) == "Hänsel ««: 10,00€") + doAssert(runeSubStr(s, 0, 100) == "Hänsel ««: 10,00€") + doAssert(runeSubStr(s, -100, 100) == "Hänsel ««: 10,00€") doAssert(runeSubStr(s, 0, -100) == "") doAssert(runeSubStr(s, 100, -100) == "") -- cgit 1.4.1-2-gfad0 From 221b34ad8313be854a6e27352ce67ffe8492b7ff Mon Sep 17 00:00:00 2001 From: Araq Date: Fri, 18 May 2018 01:49:49 +0200 Subject: move parsejson logic into its own standard lib module --- lib/pure/json.nim | 517 ++--------------------------------------------- lib/pure/parsejson.nim | 535 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 547 insertions(+), 505 deletions(-) create mode 100644 lib/pure/parsejson.nim diff --git a/lib/pure/json.nim b/lib/pure/json.nim index 9f9339961..ca7e164b8 100644 --- a/lib/pure/json.nim +++ b/lib/pure/json.nim @@ -89,506 +89,21 @@ ## echo j2 import - hashes, tables, strutils, lexbase, streams, unicode, macros + hashes, tables, strutils, lexbase, streams, unicode, macros, parsejson export tables.`$` +export + parsejson.JsonEventKind, parsejson.JsonError, JsonParser, JsonKindError, + open, close, str, getInt, getFloat, kind, getColumn, getLine, getFilename, + errorMsg, errorMsgExpected, next, JsonParsingError, raiseParseErr + when defined(nimJsonGet): {.pragma: deprecatedGet, deprecated.} else: {.pragma: deprecatedGet.} -type - JsonEventKind* = enum ## enumeration of all events that may occur when parsing - jsonError, ## an error occurred during parsing - jsonEof, ## end of file reached - jsonString, ## a string literal - jsonInt, ## an integer literal - jsonFloat, ## a float literal - jsonTrue, ## the value ``true`` - jsonFalse, ## the value ``false`` - jsonNull, ## the value ``null`` - jsonObjectStart, ## start of an object: the ``{`` token - jsonObjectEnd, ## end of an object: the ``}`` token - jsonArrayStart, ## start of an array: the ``[`` token - jsonArrayEnd ## start of an array: the ``]`` token - - TokKind = enum # must be synchronized with TJsonEventKind! - tkError, - tkEof, - tkString, - tkInt, - tkFloat, - tkTrue, - tkFalse, - tkNull, - tkCurlyLe, - tkCurlyRi, - tkBracketLe, - tkBracketRi, - tkColon, - tkComma - - JsonError* = enum ## enumeration that lists all errors that can occur - errNone, ## no error - errInvalidToken, ## invalid token - errStringExpected, ## string expected - errColonExpected, ## ``:`` expected - errCommaExpected, ## ``,`` expected - errBracketRiExpected, ## ``]`` expected - errCurlyRiExpected, ## ``}`` expected - errQuoteExpected, ## ``"`` or ``'`` expected - errEOC_Expected, ## ``*/`` expected - errEofExpected, ## EOF expected - errExprExpected ## expr expected - - ParserState = enum - stateEof, stateStart, stateObject, stateArray, stateExpectArrayComma, - stateExpectObjectComma, stateExpectColon, stateExpectValue - - JsonParser* = object of BaseLexer ## the parser object. - a: string - tok: TokKind - kind: JsonEventKind - err: JsonError - state: seq[ParserState] - filename: string - - JsonKindError* = object of ValueError ## raised by the ``to`` macro if the - ## JSON kind is incorrect. - -const - errorMessages: array[JsonError, string] = [ - "no error", - "invalid token", - "string expected", - "':' expected", - "',' expected", - "']' expected", - "'}' expected", - "'\"' or \"'\" expected", - "'*/' expected", - "EOF expected", - "expression expected" - ] - tokToStr: array[TokKind, string] = [ - "invalid token", - "EOF", - "string literal", - "int literal", - "float literal", - "true", - "false", - "null", - "{", "}", "[", "]", ":", "," - ] - -proc open*(my: var JsonParser, input: Stream, filename: string) = - ## initializes the parser with an input stream. `Filename` is only used - ## for nice error messages. - lexbase.open(my, input) - my.filename = filename - my.state = @[stateStart] - my.kind = jsonError - my.a = "" - -proc close*(my: var JsonParser) {.inline.} = - ## closes the parser `my` and its associated input stream. - lexbase.close(my) - -proc str*(my: JsonParser): string {.inline.} = - ## returns the character data for the events: ``jsonInt``, ``jsonFloat``, - ## ``jsonString`` - assert(my.kind in {jsonInt, jsonFloat, jsonString}) - return my.a - -proc getInt*(my: JsonParser): BiggestInt {.inline.} = - ## returns the number for the event: ``jsonInt`` - assert(my.kind == jsonInt) - return parseBiggestInt(my.a) - -proc getFloat*(my: JsonParser): float {.inline.} = - ## returns the number for the event: ``jsonFloat`` - assert(my.kind == jsonFloat) - return parseFloat(my.a) - -proc kind*(my: JsonParser): JsonEventKind {.inline.} = - ## returns the current event type for the JSON parser - return my.kind - -proc getColumn*(my: JsonParser): int {.inline.} = - ## get the current column the parser has arrived at. - result = getColNumber(my, my.bufpos) - -proc getLine*(my: JsonParser): int {.inline.} = - ## get the current line the parser has arrived at. - result = my.lineNumber - -proc getFilename*(my: JsonParser): string {.inline.} = - ## get the filename of the file that the parser processes. - result = my.filename - -proc errorMsg*(my: JsonParser): string = - ## returns a helpful error message for the event ``jsonError`` - assert(my.kind == jsonError) - result = "$1($2, $3) Error: $4" % [ - my.filename, $getLine(my), $getColumn(my), errorMessages[my.err]] - -proc errorMsgExpected*(my: JsonParser, e: string): string = - ## returns an error message "`e` expected" in the same format as the - ## other error messages - result = "$1($2, $3) Error: $4" % [ - my.filename, $getLine(my), $getColumn(my), e & " expected"] - -proc handleHexChar(c: char, x: var int): bool = - result = true # Success - case c - of '0'..'9': x = (x shl 4) or (ord(c) - ord('0')) - of 'a'..'f': x = (x shl 4) or (ord(c) - ord('a') + 10) - of 'A'..'F': x = (x shl 4) or (ord(c) - ord('A') + 10) - else: result = false # error - -proc parseEscapedUTF16(buf: cstring, pos: var int): int = - result = 0 - #UTF-16 escape is always 4 bytes. - for _ in 0..3: - if handleHexChar(buf[pos], result): - inc(pos) - else: - return -1 - -proc parseString(my: var JsonParser): TokKind = - result = tkString - var pos = my.bufpos + 1 - var buf = my.buf - while true: - case buf[pos] - of '\0': - my.err = errQuoteExpected - result = tkError - break - of '"': - inc(pos) - break - of '\\': - case buf[pos+1] - of '\\', '"', '\'', '/': - add(my.a, buf[pos+1]) - inc(pos, 2) - of 'b': - add(my.a, '\b') - inc(pos, 2) - of 'f': - add(my.a, '\f') - inc(pos, 2) - of 'n': - add(my.a, '\L') - inc(pos, 2) - of 'r': - add(my.a, '\C') - inc(pos, 2) - of 't': - add(my.a, '\t') - inc(pos, 2) - of 'u': - inc(pos, 2) - var r = parseEscapedUTF16(buf, pos) - if r < 0: - my.err = errInvalidToken - break - # Deal with surrogates - if (r and 0xfc00) == 0xd800: - if buf[pos] & buf[pos+1] != "\\u": - my.err = errInvalidToken - break - inc(pos, 2) - var s = parseEscapedUTF16(buf, pos) - if (s and 0xfc00) == 0xdc00 and s > 0: - r = 0x10000 + (((r - 0xd800) shl 10) or (s - 0xdc00)) - else: - my.err = errInvalidToken - break - add(my.a, toUTF8(Rune(r))) - else: - # don't bother with the error - add(my.a, buf[pos]) - inc(pos) - of '\c': - pos = lexbase.handleCR(my, pos) - buf = my.buf - add(my.a, '\c') - of '\L': - pos = lexbase.handleLF(my, pos) - buf = my.buf - add(my.a, '\L') - else: - add(my.a, buf[pos]) - inc(pos) - my.bufpos = pos # store back - -proc skip(my: var JsonParser) = - var pos = my.bufpos - var buf = my.buf - while true: - case buf[pos] - of '/': - if buf[pos+1] == '/': - # skip line comment: - inc(pos, 2) - while true: - case buf[pos] - of '\0': - break - of '\c': - pos = lexbase.handleCR(my, pos) - buf = my.buf - break - of '\L': - pos = lexbase.handleLF(my, pos) - buf = my.buf - break - else: - inc(pos) - elif buf[pos+1] == '*': - # skip long comment: - inc(pos, 2) - while true: - case buf[pos] - of '\0': - my.err = errEOC_Expected - break - of '\c': - pos = lexbase.handleCR(my, pos) - buf = my.buf - of '\L': - pos = lexbase.handleLF(my, pos) - buf = my.buf - of '*': - inc(pos) - if buf[pos] == '/': - inc(pos) - break - else: - inc(pos) - else: - break - of ' ', '\t': - inc(pos) - of '\c': - pos = lexbase.handleCR(my, pos) - buf = my.buf - of '\L': - pos = lexbase.handleLF(my, pos) - buf = my.buf - else: - break - my.bufpos = pos - -proc parseNumber(my: var JsonParser) = - var pos = my.bufpos - var buf = my.buf - if buf[pos] == '-': - add(my.a, '-') - inc(pos) - if buf[pos] == '.': - add(my.a, "0.") - inc(pos) - else: - while buf[pos] in Digits: - add(my.a, buf[pos]) - inc(pos) - if buf[pos] == '.': - add(my.a, '.') - inc(pos) - # digits after the dot: - while buf[pos] in Digits: - add(my.a, buf[pos]) - inc(pos) - if buf[pos] in {'E', 'e'}: - add(my.a, buf[pos]) - inc(pos) - if buf[pos] in {'+', '-'}: - add(my.a, buf[pos]) - inc(pos) - while buf[pos] in Digits: - add(my.a, buf[pos]) - inc(pos) - my.bufpos = pos - -proc parseName(my: var JsonParser) = - var pos = my.bufpos - var buf = my.buf - if buf[pos] in IdentStartChars: - while buf[pos] in IdentChars: - add(my.a, buf[pos]) - inc(pos) - my.bufpos = pos - -proc getTok(my: var JsonParser): TokKind = - setLen(my.a, 0) - skip(my) # skip whitespace, comments - case my.buf[my.bufpos] - of '-', '.', '0'..'9': - parseNumber(my) - if {'.', 'e', 'E'} in my.a: - result = tkFloat - else: - result = tkInt - of '"': - result = parseString(my) - of '[': - inc(my.bufpos) - result = tkBracketLe - of '{': - inc(my.bufpos) - result = tkCurlyLe - of ']': - inc(my.bufpos) - result = tkBracketRi - of '}': - inc(my.bufpos) - result = tkCurlyRi - of ',': - inc(my.bufpos) - result = tkComma - of ':': - inc(my.bufpos) - result = tkColon - of '\0': - result = tkEof - of 'a'..'z', 'A'..'Z', '_': - parseName(my) - case my.a - of "null": result = tkNull - of "true": result = tkTrue - of "false": result = tkFalse - else: result = tkError - else: - inc(my.bufpos) - result = tkError - my.tok = result - -proc next*(my: var JsonParser) = - ## retrieves the first/next event. This controls the parser. - var tk = getTok(my) - var i = my.state.len-1 - # the following code is a state machine. If we had proper coroutines, - # the code could be much simpler. - case my.state[i] - of stateEof: - if tk == tkEof: - my.kind = jsonEof - else: - my.kind = jsonError - my.err = errEofExpected - of stateStart: - # tokens allowed? - case tk - of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: - my.state[i] = stateEof # expect EOF next! - my.kind = JsonEventKind(ord(tk)) - of tkBracketLe: - my.state.add(stateArray) # we expect any - my.kind = jsonArrayStart - of tkCurlyLe: - my.state.add(stateObject) - my.kind = jsonObjectStart - of tkEof: - my.kind = jsonEof - else: - my.kind = jsonError - my.err = errEofExpected - of stateObject: - case tk - of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: - my.state.add(stateExpectColon) - my.kind = JsonEventKind(ord(tk)) - of tkBracketLe: - my.state.add(stateExpectColon) - my.state.add(stateArray) - my.kind = jsonArrayStart - of tkCurlyLe: - my.state.add(stateExpectColon) - my.state.add(stateObject) - my.kind = jsonObjectStart - of tkCurlyRi: - my.kind = jsonObjectEnd - discard my.state.pop() - else: - my.kind = jsonError - my.err = errCurlyRiExpected - of stateArray: - case tk - of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: - my.state.add(stateExpectArrayComma) # expect value next! - my.kind = JsonEventKind(ord(tk)) - of tkBracketLe: - my.state.add(stateExpectArrayComma) - my.state.add(stateArray) - my.kind = jsonArrayStart - of tkCurlyLe: - my.state.add(stateExpectArrayComma) - my.state.add(stateObject) - my.kind = jsonObjectStart - of tkBracketRi: - my.kind = jsonArrayEnd - discard my.state.pop() - else: - my.kind = jsonError - my.err = errBracketRiExpected - of stateExpectArrayComma: - case tk - of tkComma: - discard my.state.pop() - next(my) - of tkBracketRi: - my.kind = jsonArrayEnd - discard my.state.pop() # pop stateExpectArrayComma - discard my.state.pop() # pop stateArray - else: - my.kind = jsonError - my.err = errBracketRiExpected - of stateExpectObjectComma: - case tk - of tkComma: - discard my.state.pop() - next(my) - of tkCurlyRi: - my.kind = jsonObjectEnd - discard my.state.pop() # pop stateExpectObjectComma - discard my.state.pop() # pop stateObject - else: - my.kind = jsonError - my.err = errCurlyRiExpected - of stateExpectColon: - case tk - of tkColon: - my.state[i] = stateExpectValue - next(my) - else: - my.kind = jsonError - my.err = errColonExpected - of stateExpectValue: - case tk - of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: - my.state[i] = stateExpectObjectComma - my.kind = JsonEventKind(ord(tk)) - of tkBracketLe: - my.state[i] = stateExpectObjectComma - my.state.add(stateArray) - my.kind = jsonArrayStart - of tkCurlyLe: - my.state[i] = stateExpectObjectComma - my.state.add(stateObject) - my.kind = jsonObjectStart - else: - my.kind = jsonError - my.err = errExprExpected - - -# ------------- higher level interface --------------------------------------- - type JsonNodeKind* = enum ## possible JSON node types JNull, @@ -617,12 +132,6 @@ type of JArray: elems*: seq[JsonNode] - JsonParsingError* = object of ValueError ## is raised for a JSON error - -proc raiseParseErr*(p: JsonParser, msg: string) {.noinline, noreturn.} = - ## raises an `EJsonParsingError` exception. - raise newException(JsonParsingError, errorMsgExpected(p, msg)) - proc newJString*(s: string): JsonNode = ## Creates a new `JString JsonNode`. new(result) @@ -1194,10 +703,6 @@ iterator mpairs*(node: var JsonNode): tuple[key: string, val: var JsonNode] = for key, val in mpairs(node.fields): yield (key, val) -proc eat(p: var JsonParser, tok: TokKind) = - if p.tok == tok: discard getTok(p) - else: raiseParseErr(p, tokToStr[tok]) - proc parseJson(p: var JsonParser): JsonNode = ## Parses JSON from a JSON Parser `p`. case p.tok @@ -1253,10 +758,12 @@ when not defined(js): ## If `s` contains extra data, it will raise `JsonParsingError`. var p: JsonParser p.open(s, filename) - defer: p.close() - discard getTok(p) # read first token - result = p.parseJson() - eat(p, tkEof) # check if there is no extra data + try: + discard getTok(p) # read first token + result = p.parseJson() + eat(p, tkEof) # check if there is no extra data + finally: + p.close() proc parseJson*(buffer: string): JsonNode = ## Parses JSON from `buffer`. diff --git a/lib/pure/parsejson.nim b/lib/pure/parsejson.nim new file mode 100644 index 000000000..9c53af6a6 --- /dev/null +++ b/lib/pure/parsejson.nim @@ -0,0 +1,535 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2018 Nim contributors +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## This module implements a json parser. It is used +## and exported by the ``json`` standard library +## module, but can also be used in its own right. + +import + strutils, lexbase, streams, unicode + +type + JsonEventKind* = enum ## enumeration of all events that may occur when parsing + jsonError, ## an error occurred during parsing + jsonEof, ## end of file reached + jsonString, ## a string literal + jsonInt, ## an integer literal + jsonFloat, ## a float literal + jsonTrue, ## the value ``true`` + jsonFalse, ## the value ``false`` + jsonNull, ## the value ``null`` + jsonObjectStart, ## start of an object: the ``{`` token + jsonObjectEnd, ## end of an object: the ``}`` token + jsonArrayStart, ## start of an array: the ``[`` token + jsonArrayEnd ## start of an array: the ``]`` token + + TokKind* = enum # must be synchronized with TJsonEventKind! + tkError, + tkEof, + tkString, + tkInt, + tkFloat, + tkTrue, + tkFalse, + tkNull, + tkCurlyLe, + tkCurlyRi, + tkBracketLe, + tkBracketRi, + tkColon, + tkComma + + JsonError* = enum ## enumeration that lists all errors that can occur + errNone, ## no error + errInvalidToken, ## invalid token + errStringExpected, ## string expected + errColonExpected, ## ``:`` expected + errCommaExpected, ## ``,`` expected + errBracketRiExpected, ## ``]`` expected + errCurlyRiExpected, ## ``}`` expected + errQuoteExpected, ## ``"`` or ``'`` expected + errEOC_Expected, ## ``*/`` expected + errEofExpected, ## EOF expected + errExprExpected ## expr expected + + ParserState = enum + stateEof, stateStart, stateObject, stateArray, stateExpectArrayComma, + stateExpectObjectComma, stateExpectColon, stateExpectValue + + JsonParser* = object of BaseLexer ## the parser object. + a*: string + tok*: TokKind + kind: JsonEventKind + err: JsonError + state: seq[ParserState] + filename: string + rawStringLiterals: bool + + JsonKindError* = object of ValueError ## raised by the ``to`` macro if the + ## JSON kind is incorrect. + JsonParsingError* = object of ValueError ## is raised for a JSON error + +const + errorMessages*: array[JsonError, string] = [ + "no error", + "invalid token", + "string expected", + "':' expected", + "',' expected", + "']' expected", + "'}' expected", + "'\"' or \"'\" expected", + "'*/' expected", + "EOF expected", + "expression expected" + ] + tokToStr: array[TokKind, string] = [ + "invalid token", + "EOF", + "string literal", + "int literal", + "float literal", + "true", + "false", + "null", + "{", "}", "[", "]", ":", "," + ] + +proc open*(my: var JsonParser, input: Stream, filename: string; + rawStringLiterals = false) = + ## initializes the parser with an input stream. `Filename` is only used + ## for nice error messages. If `rawStringLiterals` is true, string literals + ## are kepts with their surrounding quotes and escape sequences in them are + ## left untouched too. + lexbase.open(my, input) + my.filename = filename + my.state = @[stateStart] + my.kind = jsonError + my.a = "" + my.rawStringLiterals = rawStringLiterals + +proc close*(my: var JsonParser) {.inline.} = + ## closes the parser `my` and its associated input stream. + lexbase.close(my) + +proc str*(my: JsonParser): string {.inline.} = + ## returns the character data for the events: ``jsonInt``, ``jsonFloat``, + ## ``jsonString`` + assert(my.kind in {jsonInt, jsonFloat, jsonString}) + return my.a + +proc getInt*(my: JsonParser): BiggestInt {.inline.} = + ## returns the number for the event: ``jsonInt`` + assert(my.kind == jsonInt) + return parseBiggestInt(my.a) + +proc getFloat*(my: JsonParser): float {.inline.} = + ## returns the number for the event: ``jsonFloat`` + assert(my.kind == jsonFloat) + return parseFloat(my.a) + +proc kind*(my: JsonParser): JsonEventKind {.inline.} = + ## returns the current event type for the JSON parser + return my.kind + +proc getColumn*(my: JsonParser): int {.inline.} = + ## get the current column the parser has arrived at. + result = getColNumber(my, my.bufpos) + +proc getLine*(my: JsonParser): int {.inline.} = + ## get the current line the parser has arrived at. + result = my.lineNumber + +proc getFilename*(my: JsonParser): string {.inline.} = + ## get the filename of the file that the parser processes. + result = my.filename + +proc errorMsg*(my: JsonParser): string = + ## returns a helpful error message for the event ``jsonError`` + assert(my.kind == jsonError) + result = "$1($2, $3) Error: $4" % [ + my.filename, $getLine(my), $getColumn(my), errorMessages[my.err]] + +proc errorMsgExpected*(my: JsonParser, e: string): string = + ## returns an error message "`e` expected" in the same format as the + ## other error messages + result = "$1($2, $3) Error: $4" % [ + my.filename, $getLine(my), $getColumn(my), e & " expected"] + +proc handleHexChar(c: char, x: var int): bool = + result = true # Success + case c + of '0'..'9': x = (x shl 4) or (ord(c) - ord('0')) + of 'a'..'f': x = (x shl 4) or (ord(c) - ord('a') + 10) + of 'A'..'F': x = (x shl 4) or (ord(c) - ord('A') + 10) + else: result = false # error + +proc parseEscapedUTF16*(buf: cstring, pos: var int): int = + result = 0 + #UTF-16 escape is always 4 bytes. + for _ in 0..3: + if handleHexChar(buf[pos], result): + inc(pos) + else: + return -1 + +proc parseString(my: var JsonParser): TokKind = + result = tkString + var pos = my.bufpos + 1 + var buf = my.buf + if my.rawStringLiterals: + add(my.a, '"') + while true: + case buf[pos] + of '\0': + my.err = errQuoteExpected + result = tkError + break + of '"': + if my.rawStringLiterals: + add(my.a, '"') + inc(pos) + break + of '\\': + if my.rawStringLiterals: + add(my.a, '\\') + case buf[pos+1] + of '\\', '"', '\'', '/': + add(my.a, buf[pos+1]) + inc(pos, 2) + of 'b': + add(my.a, '\b') + inc(pos, 2) + of 'f': + add(my.a, '\f') + inc(pos, 2) + of 'n': + add(my.a, '\L') + inc(pos, 2) + of 'r': + add(my.a, '\C') + inc(pos, 2) + of 't': + add(my.a, '\t') + inc(pos, 2) + of 'u': + if my.rawStringLiterals: + add(my.a, 'u') + inc(pos, 2) + var pos2 = pos + var r = parseEscapedUTF16(buf, pos) + if r < 0: + my.err = errInvalidToken + break + # Deal with surrogates + if (r and 0xfc00) == 0xd800: + if buf[pos] != '\\' or buf[pos+1] != 'u': + my.err = errInvalidToken + break + inc(pos, 2) + var s = parseEscapedUTF16(buf, pos) + if (s and 0xfc00) == 0xdc00 and s > 0: + r = 0x10000 + (((r - 0xd800) shl 10) or (s - 0xdc00)) + else: + my.err = errInvalidToken + break + if my.rawStringLiterals: + let length = pos - pos2 + for i in 1 .. length: + if buf[pos2] in {'0'..'9', 'A'..'F', 'a'..'f'}: + add(my.a, buf[pos2]) + inc pos2 + else: + break + else: + add(my.a, toUTF8(Rune(r))) + else: + # don't bother with the error + add(my.a, buf[pos]) + inc(pos) + of '\c': + pos = lexbase.handleCR(my, pos) + buf = my.buf + add(my.a, '\c') + of '\L': + pos = lexbase.handleLF(my, pos) + buf = my.buf + add(my.a, '\L') + else: + add(my.a, buf[pos]) + inc(pos) + my.bufpos = pos # store back + +proc skip(my: var JsonParser) = + var pos = my.bufpos + var buf = my.buf + while true: + case buf[pos] + of '/': + if buf[pos+1] == '/': + # skip line comment: + inc(pos, 2) + while true: + case buf[pos] + of '\0': + break + of '\c': + pos = lexbase.handleCR(my, pos) + buf = my.buf + break + of '\L': + pos = lexbase.handleLF(my, pos) + buf = my.buf + break + else: + inc(pos) + elif buf[pos+1] == '*': + # skip long comment: + inc(pos, 2) + while true: + case buf[pos] + of '\0': + my.err = errEOC_Expected + break + of '\c': + pos = lexbase.handleCR(my, pos) + buf = my.buf + of '\L': + pos = lexbase.handleLF(my, pos) + buf = my.buf + of '*': + inc(pos) + if buf[pos] == '/': + inc(pos) + break + else: + inc(pos) + else: + break + of ' ', '\t': + inc(pos) + of '\c': + pos = lexbase.handleCR(my, pos) + buf = my.buf + of '\L': + pos = lexbase.handleLF(my, pos) + buf = my.buf + else: + break + my.bufpos = pos + +proc parseNumber(my: var JsonParser) = + var pos = my.bufpos + var buf = my.buf + if buf[pos] == '-': + add(my.a, '-') + inc(pos) + if buf[pos] == '.': + add(my.a, "0.") + inc(pos) + else: + while buf[pos] in Digits: + add(my.a, buf[pos]) + inc(pos) + if buf[pos] == '.': + add(my.a, '.') + inc(pos) + # digits after the dot: + while buf[pos] in Digits: + add(my.a, buf[pos]) + inc(pos) + if buf[pos] in {'E', 'e'}: + add(my.a, buf[pos]) + inc(pos) + if buf[pos] in {'+', '-'}: + add(my.a, buf[pos]) + inc(pos) + while buf[pos] in Digits: + add(my.a, buf[pos]) + inc(pos) + my.bufpos = pos + +proc parseName(my: var JsonParser) = + var pos = my.bufpos + var buf = my.buf + if buf[pos] in IdentStartChars: + while buf[pos] in IdentChars: + add(my.a, buf[pos]) + inc(pos) + my.bufpos = pos + +proc getTok*(my: var JsonParser): TokKind = + setLen(my.a, 0) + skip(my) # skip whitespace, comments + case my.buf[my.bufpos] + of '-', '.', '0'..'9': + parseNumber(my) + if {'.', 'e', 'E'} in my.a: + result = tkFloat + else: + result = tkInt + of '"': + result = parseString(my) + of '[': + inc(my.bufpos) + result = tkBracketLe + of '{': + inc(my.bufpos) + result = tkCurlyLe + of ']': + inc(my.bufpos) + result = tkBracketRi + of '}': + inc(my.bufpos) + result = tkCurlyRi + of ',': + inc(my.bufpos) + result = tkComma + of ':': + inc(my.bufpos) + result = tkColon + of '\0': + result = tkEof + of 'a'..'z', 'A'..'Z', '_': + parseName(my) + case my.a + of "null": result = tkNull + of "true": result = tkTrue + of "false": result = tkFalse + else: result = tkError + else: + inc(my.bufpos) + result = tkError + my.tok = result + + +proc next*(my: var JsonParser) = + ## retrieves the first/next event. This controls the parser. + var tk = getTok(my) + var i = my.state.len-1 + # the following code is a state machine. If we had proper coroutines, + # the code could be much simpler. + case my.state[i] + of stateEof: + if tk == tkEof: + my.kind = jsonEof + else: + my.kind = jsonError + my.err = errEofExpected + of stateStart: + # tokens allowed? + case tk + of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: + my.state[i] = stateEof # expect EOF next! + my.kind = JsonEventKind(ord(tk)) + of tkBracketLe: + my.state.add(stateArray) # we expect any + my.kind = jsonArrayStart + of tkCurlyLe: + my.state.add(stateObject) + my.kind = jsonObjectStart + of tkEof: + my.kind = jsonEof + else: + my.kind = jsonError + my.err = errEofExpected + of stateObject: + case tk + of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: + my.state.add(stateExpectColon) + my.kind = JsonEventKind(ord(tk)) + of tkBracketLe: + my.state.add(stateExpectColon) + my.state.add(stateArray) + my.kind = jsonArrayStart + of tkCurlyLe: + my.state.add(stateExpectColon) + my.state.add(stateObject) + my.kind = jsonObjectStart + of tkCurlyRi: + my.kind = jsonObjectEnd + discard my.state.pop() + else: + my.kind = jsonError + my.err = errCurlyRiExpected + of stateArray: + case tk + of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: + my.state.add(stateExpectArrayComma) # expect value next! + my.kind = JsonEventKind(ord(tk)) + of tkBracketLe: + my.state.add(stateExpectArrayComma) + my.state.add(stateArray) + my.kind = jsonArrayStart + of tkCurlyLe: + my.state.add(stateExpectArrayComma) + my.state.add(stateObject) + my.kind = jsonObjectStart + of tkBracketRi: + my.kind = jsonArrayEnd + discard my.state.pop() + else: + my.kind = jsonError + my.err = errBracketRiExpected + of stateExpectArrayComma: + case tk + of tkComma: + discard my.state.pop() + next(my) + of tkBracketRi: + my.kind = jsonArrayEnd + discard my.state.pop() # pop stateExpectArrayComma + discard my.state.pop() # pop stateArray + else: + my.kind = jsonError + my.err = errBracketRiExpected + of stateExpectObjectComma: + case tk + of tkComma: + discard my.state.pop() + next(my) + of tkCurlyRi: + my.kind = jsonObjectEnd + discard my.state.pop() # pop stateExpectObjectComma + discard my.state.pop() # pop stateObject + else: + my.kind = jsonError + my.err = errCurlyRiExpected + of stateExpectColon: + case tk + of tkColon: + my.state[i] = stateExpectValue + next(my) + else: + my.kind = jsonError + my.err = errColonExpected + of stateExpectValue: + case tk + of tkString, tkInt, tkFloat, tkTrue, tkFalse, tkNull: + my.state[i] = stateExpectObjectComma + my.kind = JsonEventKind(ord(tk)) + of tkBracketLe: + my.state[i] = stateExpectObjectComma + my.state.add(stateArray) + my.kind = jsonArrayStart + of tkCurlyLe: + my.state[i] = stateExpectObjectComma + my.state.add(stateObject) + my.kind = jsonObjectStart + else: + my.kind = jsonError + my.err = errExprExpected + +proc raiseParseErr*(p: JsonParser, msg: string) {.noinline, noreturn.} = + ## raises an `EJsonParsingError` exception. + raise newException(JsonParsingError, errorMsgExpected(p, msg)) + +proc eat*(p: var JsonParser, tok: TokKind) = + if p.tok == tok: discard getTok(p) + else: raiseParseErr(p, tokToStr[tok]) -- cgit 1.4.1-2-gfad0 From 5b176f14a2d6ef12e91027d736d60dcaa799347c Mon Sep 17 00:00:00 2001 From: Emery Hemingway Date: Thu, 17 May 2018 12:49:17 +0200 Subject: Provide configuration for Genode toolchain --- config/nim.cfg | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/config/nim.cfg b/config/nim.cfg index 9b3172e90..e11826587 100644 --- a/config/nim.cfg +++ b/config/nim.cfg @@ -243,3 +243,11 @@ vcc.cpp.options.size = "/O1" # Configuration for the Tiny C Compiler: tcc.options.always = "-w" + +# Configuration for the Genode toolchain +amd64.genode.gcc.cpp.exe = "genode-x86-g++" +amd64.genode.gcc.exe = "genode-x86-gcc" +amd64.genode.gcc.path = "/usr/local/genode-gcc/bin" +arm.genode.gcc.cpp.exe = "genode-arm-g++" +arm.genode.gcc.exe = "genode-arm-gcc" +arm.genode.gcc.path = "/usr/local/genode-gcc/bin" -- cgit 1.4.1-2-gfad0 From 43b1ac07d4bb7eeecec45f8dca50442618f2608b Mon Sep 17 00:00:00 2001 From: coffeepots Date: Fri, 18 May 2018 18:37:28 +0100 Subject: Fix typo in "out of bounds" error message --- compiler/vm.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/compiler/vm.nim b/compiler/vm.nim index dcb4cefd7..cbd304caa 100644 --- a/compiler/vm.nim +++ b/compiler/vm.nim @@ -441,7 +441,7 @@ proc setLenSeq(c: PCtx; node: PNode; newLen: int; info: TLineInfo) = node.sons[i] = newNodeI(typeKind, info) const - errIndexOutOfBounds = "index ouf of bounds" + errIndexOutOfBounds = "index out of bounds" errNilAccess = "attempt to access a nil address" errOverOrUnderflow = "over- or underflow" errConstantDivisionByZero = "division by zero" -- cgit 1.4.1-2-gfad0 From 06bdf8392bd3e597dbe3ef12c7a819b60e32d7ac Mon Sep 17 00:00:00 2001 From: Dmitry Atamanov Date: Fri, 18 May 2018 22:13:29 +0300 Subject: Fixes CritBitTree.inc's bug (#7838) * Fixes CritBitTree.inc's bug * Update changelog --- changelog.md | 1 + lib/pure/collections/critbits.nim | 18 ++++++++++++++---- 2 files changed, 15 insertions(+), 4 deletions(-) diff --git a/changelog.md b/changelog.md index cbefbc421..f9daf55d1 100644 --- a/changelog.md +++ b/changelog.md @@ -74,6 +74,7 @@ deprecated. - The `terminal` module now exports additional procs for generating ANSI color codes as strings. +- Added the parameter ``val`` for the ``CritBitTree[int].inc`` proc. ### Language additions diff --git a/lib/pure/collections/critbits.nim b/lib/pure/collections/critbits.nim index 95fffdf88..5ae5e26b2 100644 --- a/lib/pure/collections/critbits.nim +++ b/lib/pure/collections/critbits.nim @@ -163,13 +163,13 @@ proc containsOrIncl*(c: var CritBitTree[void], key: string): bool = var n = rawInsert(c, key) result = c.count == oldCount -proc inc*(c: var CritBitTree[int]; key: string) = - ## counts the 'key'. +proc inc*(c: var CritBitTree[int]; key: string, val: int = 1) = + ## increments `c[key]` by `val`. let oldCount = c.count var n = rawInsert(c, key) - if c.count == oldCount: + if c.count == oldCount or oldCount == 0: # not a new key: - inc n.val + inc n.val, val proc incl*(c: var CritBitTree[void], key: string) = ## includes `key` in `c`. @@ -352,3 +352,13 @@ when isMainModule: assert toSeq(r.items) == @["abc", "definition", "prefix", "xyz"] assert toSeq(r.itemsWithPrefix("de")) == @["definition"] + var c = CritBitTree[int]() + + c.inc("a") + assert c["a"] == 1 + + c.inc("a", 4) + assert c["a"] == 5 + + c.inc("a", -5) + assert c["a"] == 0 -- cgit 1.4.1-2-gfad0 From aefa6547c3a616a31e311b333c385a5e8761a68a Mon Sep 17 00:00:00 2001 From: koranza <15344611+koranza@users.noreply.github.com> Date: Fri, 18 May 2018 18:25:49 -0500 Subject: check string lengths to avoid index out of bound --- lib/pure/os.nim | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/lib/pure/os.nim b/lib/pure/os.nim index 03445a035..9a1fb39d5 100644 --- a/lib/pure/os.nim +++ b/lib/pure/os.nim @@ -139,6 +139,7 @@ proc findExe*(exe: string, followSymlinks: bool = true; ## is added the `ExeExts <#ExeExts>`_ file extensions if it has none. ## If the system supports symlinks it also resolves them until it ## meets the actual file. This behavior can be disabled if desired. + if exe.len == 0: return template checkCurrentDir() = for ext in extensions: result = addFileExt(exe, ext) @@ -149,8 +150,9 @@ proc findExe*(exe: string, followSymlinks: bool = true; checkCurrentDir() let path = string(getEnv("PATH")) for candidate in split(path, PathSep): + if candidate.len == 0: continue when defined(windows): - var x = (if candidate[0] == '"' and candidate[^1] == '"': + var x = (if candidate.len > 2 and candidate[0] == '"' and candidate[^1] == '"': substr(candidate, 1, candidate.len-2) else: candidate) / exe else: @@ -1649,4 +1651,4 @@ proc setLastModificationTime*(file: string, t: times.Time) = var ft = t.toWinTime.toFILETIME let res = setFileTime(h, nil, nil, ft.addr) discard h.closeHandle - if res == 0'i32: raiseOSError(osLastError()) \ No newline at end of file + if res == 0'i32: raiseOSError(osLastError()) -- cgit 1.4.1-2-gfad0 From 04ddd069a1b3315dc0e323d98fefd621d1430a4d Mon Sep 17 00:00:00 2001 From: Andreas Rumpf Date: Sat, 19 May 2018 11:17:22 +0200 Subject: added experimental undokumented std/varints module --- lib/std/varints.nim | 145 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 145 insertions(+) create mode 100644 lib/std/varints.nim diff --git a/lib/std/varints.nim b/lib/std/varints.nim new file mode 100644 index 000000000..bfc1945fe --- /dev/null +++ b/lib/std/varints.nim @@ -0,0 +1,145 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2018 Nim contributors +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Note this API is still experimental! A variable length integer +## encoding implementation inspired by SQLite. + +const + maxVarIntLen* = 9 ## the maximal number of bytes a varint can take + +proc readVu64*(z: openArray[byte]; pResult: var uint64): int = + if z[0] <= 240: + pResult = z[0] + return 1 + if z[0] <= 248: + if z.len < 2: return 0 + pResult = (uint64 z[0] - 241) * 256 + uint64 z[1] + 240 + return 2 + if z.len < int(z[0]-246): return 0 + if z[0] == 249: + pResult = 2288u64 + 256u64*z[1].uint64 + z[2].uint64 + return 3 + if z[0] == 250: + pResult = (z[1].uint64 shl 16u64) + (z[2].uint64 shl 8u64) + z[3].uint64 + return 4 + let x = (z[1].uint64 shl 24) + (z[2].uint64 shl 16) + (z[3].uint64 shl 8) + z[4].uint64 + if z[0] == 251: + pResult = x + return 5 + if z[0] == 252: + pResult = (((uint64)x) shl 8) + z[5].uint64 + return 6 + if z[0] == 253: + pResult = (((uint64)x) shl 16) + (z[5].uint64 shl 8) + z[6].uint64 + return 7 + if z[0] == 254: + pResult = (((uint64)x) shl 24) + (z[5].uint64 shl 16) + (z[6].uint64 shl 8) + z[7].uint64 + return 8 + pResult = (((uint64)x) shl 32) + + (0xffffffff'u64 and ((z[5].uint64 shl 24) + + (z[6].uint64 shl 16) + (z[7].uint64 shl 8) + z[8].uint64)) + return 9 + +proc varintWrite32(z: var openArray[byte]; y: uint32) = + z[0] = uint8(y shr 24) + z[1] = uint8(y shr 16) + z[2] = uint8(y shr 8) + z[3] = uint8(y) + +proc writeVu64*(z: var openArray[byte], x: uint64): int = + ## Write a varint into z. The buffer z must be at least 9 characters + ## long to accommodate the largest possible varint. Returns the number of + ## bytes used. + if x <= 240: + z[0] = uint8 x + return 1 + if x <= 2287: + let y = uint32(x - 240) + z[0] = uint8(y shr 8 + 241) + z[1] = uint8(y and 255) + return 2 + if x <= 67823: + let y = uint32(x - 2288) + z[0] = 249 + z[1] = uint8(y shr 8) + z[2] = uint8(y and 255) + return 3 + let y = uint32 x + let w = uint32(x shr 32) + if w == 0: + if y <= 16777215: + z[0] = 250 + z[1] = uint8(y shr 16) + z[2] = uint8(y shr 8) + z[3] = uint8(y) + return 4 + z[0] = 251 + varintWrite32(toOpenArray(z, 1, z.high-1), y) + return 5 + if w <= 255: + z[0] = 252 + z[1] = uint8 w + varintWrite32(toOpenArray(z, 2, z.high-2), y) + return 6 + if w <= 65535: + z[0] = 253 + z[1] = uint8(w shr 8) + z[2] = uint8 w + varintWrite32(toOpenArray(z, 3, z.high-3), y) + return 7 + if w <= 16777215: + z[0] = 254 + z[1] = uint8(w shr 16) + z[2] = uint8(w shr 8) + z[3] = uint8 w + varintWrite32(toOpenArray(z, 4, z.high-4), y) + return 8 + z[0] = 255 + varintWrite32(toOpenArray(z, 1, z.high-1), w) + varintWrite32(toOpenArray(z, 5, z.high-5), y) + return 9 + +proc sar(a, b: int64): int64 = + {.emit: [result, " = ", a, " >> ", b, ";"].} + +proc sal(a, b: int64): int64 = + {.emit: [result, " = ", a, " << ", b, ";"].} + +proc encodeZigzag*(x: int64): uint64 {.inline.} = + uint64(sal(x, 1)) xor uint64(sar(x, 63)) + +proc decodeZigzag*(x: uint64): int64 {.inline.} = + let casted = cast[int64](x) + result = (`shr`(casted, 1)) xor (-(casted and 1)) + +when isMainModule: + #import random + + var dest: array[50, byte] + var got: uint64 + + for test in [0xFFFF_FFFF_FFFFF_FFFFu64, 77u64, 0u64, 10_000_000u64, uint64(high(int64)), + uint64(high(int32)),uint64(low(int32)),uint64(low(int64))]: + let wrLen = writeVu64(dest, test) + let rdLen = readVu64(dest, got) + assert wrLen == rdLen + echo(if got == test: "YES" else: "NO") + echo "number is ", got + + if encodeZigzag(decodeZigzag(test)) != test: + echo "Failure for ", test, " ", encodeZigzag(decodeZigzag(test)), " ", decodeZigzag(test) + + # check this also works for floats: + for test in [0.0, 0.1, 2.0, +Inf, Nan, NegInf]: + let t = cast[uint64](test) + let wrLenB = writeVu64(dest, t) + let rdLenB = readVu64(dest, got) + assert wrLenB == rdLenB + echo rdLenB + echo(if cast[float64](got) == test: "YES" else: "NO") -- cgit 1.4.1-2-gfad0 From 94c45136eae6c47321414352d50a680c4312b729 Mon Sep 17 00:00:00 2001 From: Dmitry Atamanov Date: Sat, 19 May 2018 18:32:18 +0300 Subject: Fixes #6832 (#7813) Fixes #6832 --- lib/system.nim | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/lib/system.nim b/lib/system.nim index 5781aff27..06c4f103b 100644 --- a/lib/system.nim +++ b/lib/system.nim @@ -3808,7 +3808,9 @@ template doAssert*(cond: bool, msg = "") = bind instantiationInfo {.line: instantiationInfo().}: if not cond: - raiseAssert(astToStr(cond) & ' ' & msg) + raiseAssert(astToStr(cond) & ' ' & + instantiationInfo(-1, false).fileName & '(' & + $instantiationInfo(-1, false).line & ") " & msg) iterator items*[T](a: seq[T]): T {.inline.} = ## iterates over each item of `a`. -- cgit 1.4.1-2-gfad0 From dedf0f3e19332c02562689b168cc4ac45b812174 Mon Sep 17 00:00:00 2001 From: data-man Date: Sat, 19 May 2018 20:02:49 +0300 Subject: Removed space between "array" and a square bracket in the docs --- doc/endb.rst | 2 +- doc/manual.rst | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/doc/endb.rst b/doc/endb.rst index 6757d98e3..90bb964ba 100644 --- a/doc/endb.rst +++ b/doc/endb.rst @@ -128,7 +128,7 @@ The ``watchpoint`` pragma is syntactically a statement. It can be used to mark a location as a watchpoint: .. code-block:: Nim - var a: array [0..20, int] + var a: array[0..20, int] {.watchpoint: a[3].} for i in 0 .. 20: a[i] = i diff --git a/doc/manual.rst b/doc/manual.rst index 44e2ee5b5..95af86a6a 100644 --- a/doc/manual.rst +++ b/doc/manual.rst @@ -2527,7 +2527,7 @@ The implicit initialization can be avoided for optimization reasons with the .. code-block:: nim var - a {.noInit.}: array [0..1023, char] + a {.noInit.}: array[0..1023, char] If a proc is annotated with the ``noinit`` pragma this refers to its implicit ``result`` variable: @@ -6632,7 +6632,7 @@ Syntactically it has to be used as a statement inside the loop: enumA, enumB, enumC, enumD, enumE proc vm() = - var instructions: array [0..100, MyEnum] + var instructions: array[0..100, MyEnum] instructions[2] = enumC instructions[3] = enumD instructions[4] = enumA -- cgit 1.4.1-2-gfad0 From f9358e85caecb0c863a395203b759961351f9afd Mon Sep 17 00:00:00 2001 From: koranza <15344611+koranza@users.noreply.github.com> Date: Sat, 19 May 2018 14:48:19 -0500 Subject: remove unneeded check on length --- lib/pure/os.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/pure/os.nim b/lib/pure/os.nim index 9a1fb39d5..370420d37 100644 --- a/lib/pure/os.nim +++ b/lib/pure/os.nim @@ -152,7 +152,7 @@ proc findExe*(exe: string, followSymlinks: bool = true; for candidate in split(path, PathSep): if candidate.len == 0: continue when defined(windows): - var x = (if candidate.len > 2 and candidate[0] == '"' and candidate[^1] == '"': + var x = (if candidate[0] == '"' and candidate[^1] == '"': substr(candidate, 1, candidate.len-2) else: candidate) / exe else: -- cgit 1.4.1-2-gfad0 From 90afb1baa7cd4c047093f6cb108c954cb3cb6ca9 Mon Sep 17 00:00:00 2001 From: Dmitry Atamanov Date: Sun, 20 May 2018 21:11:25 +0300 Subject: binarySearch improvements (#7850) --- changelog.md | 1 + lib/pure/algorithm.nim | 50 ++++++++++++++++++++++++++++++++++++-------------- 2 files changed, 37 insertions(+), 14 deletions(-) diff --git a/changelog.md b/changelog.md index f9daf55d1..57b54c71e 100644 --- a/changelog.md +++ b/changelog.md @@ -56,6 +56,7 @@ - Added the type ``times.Duration`` for representing fixed durations of time. - Added the proc ``times.convert`` for converting between different time units, e.g days to seconds. +- Added the proc ``algorithm.binarySearch[T, K]`` with the ```cmp``` parameter. ### Library changes diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 2b668d1ca..169dcd602 100644 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -64,27 +64,49 @@ proc reversed*[T](a: openArray[T]): seq[T] = ## returns the reverse of the array `a`. reversed(a, 0, a.high) -proc binarySearch*[T](a: openArray[T], key: T): int = +proc binarySearch*[T, K](a: openArray[T], key: K, + cmp: proc (x: T, y: K): int {.closure.}): int = ## binary search for `key` in `a`. Returns -1 if not found. - if ((a.len - 1) and a.len) == 0 and a.len > 0: - # when `a.len` is a power of 2, a faster div can be used. - var step = a.len div 2 + ## + ## `cmp` is the comparator function to use, the expected return values are + ## the same as that of system.cmp. + if a.len == 0: + return -1 + + let len = a.len + + if len == 1: + if cmp(a[0], key) == 0: + return 0 + else: + return -1 + + if (len and (len - 1)) == 0: + # when `len` is a power of 2, a faster shr can be used. + var step = len shr 1 while step > 0: - if a[result or step] <= key: - result = result or step + let i = result or step + if cmp(a[i], key) < 1: + result = i step = step shr 1 - if a[result] != key: result = -1 + if cmp(a[result], key) != 0: result = -1 else: - var b = len(a) + var b = len while result < b: - var mid = (result + b) div 2 - if a[mid] < key: result = mid + 1 - else: b = mid - if result >= len(a) or a[result] != key: result = -1 + var mid = (result + b) shr 1 + if cmp(a[mid], key) < 0: + result = mid + 1 + else: + b = mid + if result >= len or cmp(a[result], key) != 0: result = -1 + +proc binarySearch*[T](a: openArray[T], key: T): int = + ## binary search for `key` in `a`. Returns -1 if not found. + binarySearch(a, key, cmp[T]) proc smartBinarySearch*[T](a: openArray[T], key: T): int {.deprecated.} = ## **Deprecated since version 0.18.1**; Use ``binarySearch`` instead. - binarySearch(a,key) + binarySearch(a, key, cmp[T]) const onlySafeCode = true @@ -108,7 +130,7 @@ proc lowerBound*[T, K](a: openArray[T], key: K, cmp: proc(x: T, k: K): int {.clo var count = a.high - a.low + 1 var step, pos: int while count != 0: - step = count div 2 + step = count shr 1 pos = result + step if cmp(a[pos], key) < 0: result = pos + 1 -- cgit 1.4.1-2-gfad0 From 5472574f721ae08cb696f4129abcff54e1e88d83 Mon Sep 17 00:00:00 2001 From: Araq Date: Sun, 20 May 2018 23:00:25 +0200 Subject: json.nim: delete should raise KeyError, not IndexError, minor cleanup of the tests --- lib/pure/json.nim | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/lib/pure/json.nim b/lib/pure/json.nim index ca7e164b8..2bb830bcb 100644 --- a/lib/pure/json.nim +++ b/lib/pure/json.nim @@ -509,7 +509,7 @@ proc delete*(obj: JsonNode, key: string) = ## Deletes ``obj[key]``. assert(obj.kind == JObject) if not obj.fields.hasKey(key): - raise newException(IndexError, "key not in object") + raise newException(KeyError, "key not in object") obj.fields.del(key) proc copy*(p: JsonNode): JsonNode = @@ -1496,18 +1496,18 @@ when isMainModule: # Bounds checking try: let a = testJson["a"][9] - doAssert(false, "EInvalidIndex not thrown") + doAssert(false, "IndexError not thrown") except IndexError: discard try: let a = testJson["a"][-1] - doAssert(false, "EInvalidIndex not thrown") + doAssert(false, "IndexError not thrown") except IndexError: discard try: doAssert(testJson["a"][0].num == 1, "Index doesn't correspond to its value") except: - doAssert(false, "EInvalidIndex thrown for valid index") + doAssert(false, "IndexError thrown for valid index") doAssert(testJson{"b"}.str=="asd", "Couldn't fetch a singly nested key with {}") doAssert(isNil(testJson{"nonexistent"}), "Non-existent keys should return nil") -- cgit 1.4.1-2-gfad0 From dc809bd485ae9a104666a4ee4a3728eab9e2b39f Mon Sep 17 00:00:00 2001 From: Araq Date: Mon, 21 May 2018 14:22:02 +0200 Subject: fixes yet another indexing bug caused by the strict strings --- compiler/renderer.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/compiler/renderer.nim b/compiler/renderer.nim index 966bed769..75c19a163 100644 --- a/compiler/renderer.nim +++ b/compiler/renderer.nim @@ -189,7 +189,7 @@ proc putComment(g: var TSrcGen, s: string) = put(g, tkComment, com) com = "## " inc(i) - if s[i] == '\x0A': inc(i) + if i < s.len and s[i] == '\x0A': inc(i) optNL(g, ind) of '\x0A': put(g, tkComment, com) -- cgit 1.4.1-2-gfad0