diff options
Diffstat (limited to 'compiler/ropes.nim')
| -rw-r--r-- | compiler/ropes.nim | 230 |
1 files changed, 25 insertions, 205 deletions
diff --git a/compiler/ropes.nim b/compiler/ropes.nim index 1e7957337..e0d5aa0d3 100644 --- a/compiler/ropes.nim +++ b/compiler/ropes.nim @@ -7,213 +7,55 @@ # distribution, for details about the copyright. # -# Ropes for the C code generator -# -# Ropes are a data structure that represents a very long string -# efficiently; especially concatenation is done in O(1) instead of O(N). -# Ropes make use a lazy evaluation: They are essentially concatenation -# trees that are only flattened when converting to a native Nim -# string or when written to disk. The empty string is represented by a -# nil pointer. -# A little picture makes everything clear: -# -# "this string" & " is internally " & "represented as" -# -# con -- inner nodes do not contain raw data -# / \ -# / \ -# / \ -# con "represented as" -# / \ -# / \ -# / \ -# / \ -# / \ -#"this string" " is internally " -# -# Note that this is the same as: -# "this string" & (" is internally " & "represented as") -# -# con -# / \ -# / \ -# / \ -# "this string" con -# / \ -# / \ -# / \ -# / \ -# / \ -#" is internally " "represented as" -# -# The 'con' operator is associative! This does not matter however for -# the algorithms we use for ropes. -# -# Note that the left and right pointers are not needed for leaves. -# Leaves have relatively high memory overhead (~30 bytes on a 32 -# bit machines) and we produce many of them. This is why we cache and -# share leaves across different rope trees. -# To cache them they are inserted in a `cache` array. - -import - hashes +# Ropes for the C code generator. Ropes are mapped to `string` directly nowadays. from pathutils import AbsoluteFile +when defined(nimPreviewSlimSystem): + import std/[assertions, syncio, formatfloat] + type FormatStr* = string # later we may change it to CString for better # performance of the code generator (assignments # copy the format strings # though it is not necessary) - Rope* = ref RopeObj - RopeObj*{.acyclic.} = object of RootObj # the empty rope is represented - # by nil to safe space - left, right: Rope - L: int # <= 0 if a leaf - data*: string + Rope* = string -proc len*(a: Rope): int = - ## the rope's length - if a == nil: result = 0 - else: result = abs a.L +proc newRopeAppender*(cap = 80): string {.inline.} = + result = newStringOfCap(cap) -proc newRope(data: string = ""): Rope = - new(result) - result.L = -data.len - result.data = data +proc freeze*(r: Rope) {.inline.} = discard -when not compileOption("threads"): - var - cache: array[0..2048*2 - 1, Rope] - - proc resetRopeCache* = - for i in low(cache)..high(cache): - cache[i] = nil - -proc ropeInvariant(r: Rope): bool = - if r == nil: - result = true - else: - result = true # - # if r.data <> snil then - # result := true - # else begin - # result := (r.left <> nil) and (r.right <> nil); - # if result then result := ropeInvariant(r.left); - # if result then result := ropeInvariant(r.right); - # end - -var gCacheTries* = 0 -var gCacheMisses* = 0 -var gCacheIntTries* = 0 +proc resetRopeCache* = discard -proc insertInCache(s: string): Rope = - when declared(cache): - inc gCacheTries - var h = hash(s) and high(cache) - result = cache[h] - if isNil(result) or result.data != s: - inc gCacheMisses - result = newRope(s) - cache[h] = result - else: - result = newRope(s) - -proc rope*(s: string): Rope = - ## Converts a string to a rope. - if s.len == 0: - result = nil - else: - result = insertInCache(s) - assert(ropeInvariant(result)) +template rope*(s: string): string = s proc rope*(i: BiggestInt): Rope = ## Converts an int to a rope. - inc gCacheIntTries result = rope($i) proc rope*(f: BiggestFloat): Rope = ## Converts a float to a rope. result = rope($f) -proc `&`*(a, b: Rope): Rope = - if a == nil: - result = b - elif b == nil: - result = a - else: - result = newRope() - result.L = abs(a.L) + abs(b.L) - result.left = a - result.right = b - -proc `&`*(a: Rope, b: string): Rope = - ## the concatenation operator for ropes. - result = a & rope(b) - -proc `&`*(a: string, b: Rope): Rope = - ## the concatenation operator for ropes. - result = rope(a) & b - -proc `&`*(a: openArray[Rope]): Rope = - ## the concatenation operator for an openarray of ropes. - for i in 0..high(a): result = result & a[i] - -proc add*(a: var Rope, b: Rope) = - ## adds `b` to the rope `a`. - a = a & b - -proc add*(a: var Rope, b: string) = - ## adds `b` to the rope `a`. - a = a & b - -iterator leaves*(r: Rope): string = - ## iterates over any leaf string in the rope `r`. - if r != nil: - var stack = @[r] - while stack.len > 0: - var it = stack.pop - while it.left != nil: - assert it.right != nil - stack.add(it.right) - it = it.left - assert(it != nil) - yield it.data - -iterator items*(r: Rope): char = - ## iterates over any character in the rope `r`. - for s in leaves(r): - for c in items(s): yield c - proc writeRope*(f: File, r: Rope) = ## writes a rope to a file. - for s in leaves(r): write(f, s) + write(f, r) proc writeRope*(head: Rope, filename: AbsoluteFile): bool = - var f: File + var f: File = default(File) if open(f, filename.string, fmWrite): - if head != nil: writeRope(f, head) + writeRope(f, head) close(f) result = true else: result = false -proc `$`*(r: Rope): string = - ## converts a rope back to a string. - result = newString(r.len) - setLen(result, 0) - for s in leaves(r): result.add(s) - -proc ropeConcat*(a: varargs[Rope]): Rope = - # not overloaded version of concat to speed-up `rfmt` a little bit - for i in 0..high(a): result = result & a[i] - -proc prepend*(a: var Rope, b: Rope) = a = b & a proc prepend*(a: var Rope, b: string) = a = b & a proc runtimeFormat*(frmt: FormatStr, args: openArray[Rope]): Rope = var i = 0 - result = nil + result = newRopeAppender() var num = 0 while i < frmt.len: if frmt[i] == '$': @@ -234,7 +76,7 @@ proc runtimeFormat*(frmt: FormatStr, args: openArray[Rope]): Rope = if i >= frmt.len or frmt[i] notin {'0'..'9'}: break num = j if j > high(args) + 1: - doAssert false, "invalid format string: " & frmt + raiseAssert "invalid format string: " & frmt else: result.add(args[j-1]) of '{': @@ -246,10 +88,10 @@ proc runtimeFormat*(frmt: FormatStr, args: openArray[Rope]): Rope = num = j if frmt[i] == '}': inc(i) else: - doAssert false, "invalid format string: " & frmt + raiseAssert "invalid format string: " & frmt if j > high(args) + 1: - doAssert false, "invalid format string: " & frmt + raiseAssert "invalid format string: " & frmt else: result.add(args[j-1]) of 'n': @@ -259,14 +101,10 @@ proc runtimeFormat*(frmt: FormatStr, args: openArray[Rope]): Rope = result.add("\n") inc(i) else: - doAssert false, "invalid format string: " & frmt - var start = i - while i < frmt.len: - if frmt[i] != '$': inc(i) - else: break - if i - 1 >= start: - result.add(substr(frmt, start, i - 1)) - assert(ropeInvariant(result)) + raiseAssert "invalid format string: " & frmt + else: + result.add(frmt[i]) + inc(i) proc `%`*(frmt: static[FormatStr], args: openArray[Rope]): Rope = runtimeFormat(frmt, args) @@ -275,30 +113,19 @@ template addf*(c: var Rope, frmt: FormatStr, args: openArray[Rope]) = ## shortcut for ``add(c, frmt % args)``. c.add(frmt % args) -when true: - template `~`*(r: string): Rope = r % [] -else: - {.push stack_trace: off, line_trace: off.} - proc `~`*(r: static[string]): Rope = - # this is the new optimized "to rope" operator - # the mnemonic is that `~` looks a bit like a rope :) - var r {.global.} = r % [] - return r - {.pop.} - const bufSize = 1024 # 1 KB is reasonable -proc equalsFile*(r: Rope, f: File): bool = +proc equalsFile*(s: Rope, f: File): bool = ## returns true if the contents of the file `f` equal `r`. var - buf: array[bufSize, char] + buf: array[bufSize, char] = default(array[bufSize, char]) bpos = buf.len blen = buf.len btotal = 0 rtotal = 0 - for s in leaves(r): + when true: var spos = 0 rtotal += s.len while spos < s.len: @@ -324,15 +151,8 @@ proc equalsFile*(r: Rope, f: File): bool = proc equalsFile*(r: Rope, filename: AbsoluteFile): bool = ## returns true if the contents of the file `f` equal `r`. If `f` does not ## exist, false is returned. - var f: File + var f: File = default(File) result = open(f, filename.string) if result: result = equalsFile(r, f) close(f) - -proc writeRopeIfNotEqual*(r: Rope, filename: AbsoluteFile): bool = - # returns true if overwritten - if not equalsFile(r, filename): - result = writeRope(r, filename) - else: - result = false |