summary refs log tree commit diff stats
path: root/lib/pure/ropes.nim
blob: 41d6211b41484ffd50992da27ab94fd75e1c6e61 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
#
#
#            Nim's Runtime Library
#        (c) Copyright 2010 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## This module contains support for a `rope`:idx: data type.
## Ropes can represent very long strings efficiently; especially concatenation
## is done in O(1) instead of O(n). They are essentially concatenation
## trees that are only flattened when converting to a native Nim
## string. The empty string is represented by ``nil``. Ropes are immutable and
## subtrees can be shared without copying.
## Leaves can be cached for better memory efficiency at the cost of
## runtime efficiency.

include "system/inclrtl"
import streams

{.push debugger: off.} # the user does not want to trace a part
                       # of the standard library!

const
  countCacheMisses = false

var
  cacheEnabled = false

type
  Rope* = ref RopeObj ## empty rope is represented by nil
  RopeObj {.acyclic.} = object
    left, right: Rope
    length: int
    data: string # != nil if a leaf

# Note that the left and right pointers are not needed for leafs.
# Leaves have relatively high memory overhead (~30 bytes on a 32
# bit machine) and we produce many of them. This is why we cache and
# share leafs across different rope trees.
# To cache them they are inserted in another tree, a splay tree for best
# performance. But for the caching tree we use the leaf's left and right
# pointers.

proc len*(a: Rope): int {.rtl, extern: "nro$1".} =
  ## the rope's length
  if a == nil: result = 0
  else: result = a.length

proc newRope(): Rope = new(result)
proc newRope(data: string): Rope =
  new(result)
  result.length = len(data)
  result.data = data

var
  cache {.threadvar.}: Rope # the root of the cache tree
  N {.threadvar.}: Rope     # dummy rope needed for splay algorithm

when countCacheMisses:
  var misses, hits: int

proc splay(s: string, tree: Rope, cmpres: var int): Rope =
  var c: int
  var t = tree
  N.left = nil
  N.right = nil # reset to nil
  var le = N
  var r = N
  while true:
    c = cmp(s, t.data)
    if c < 0:
      if (t.left != nil) and (s < t.left.data):
        var y = t.left
        t.left = y.right
        y.right = t
        t = y
      if t.left == nil: break
      r.left = t
      r = t
      t = t.left
    elif c > 0:
      if (t.right != nil) and (s > t.right.data):
        var y = t.right
        t.right = y.left
        y.left = t
        t = y
      if t.right == nil: break
      le.right = t
      le = t
      t = t.right
    else:
      break
  cmpres = c
  le.right = t.left
  r.left = t.right
  t.left = N.right
  t.right = N.left
  result = t

proc insertInCache(s: string, tree: Rope): Rope =
  var t = tree
  if t == nil:
    result = newRope(s)
    when countCacheMisses: inc(misses)
    return
  var cmp: int
  t = splay(s, t, cmp)
  if cmp == 0:
    # We get here if it's already in the Tree
    # Don't add it again
    result = t
    when countCacheMisses: inc(hits)
  else:
    when countCacheMisses: inc(misses)
    result = newRope(s)
    if cmp < 0:
      result.left = t.left
      result.right = t
      t.left = nil
    else:
      # i > t.item:
      result.right = t.right
      result.left = t
      t.right = nil

proc rope*(s: string = ""): Rope {.rtl, extern: "nro$1Str".} =
  ## Converts a string to a rope.
  if s.len == 0:
    result = nil
  else:
    when nimvm:
      # No caching in VM context
      result = newRope(s)
    else:
      if cacheEnabled:
        result = insertInCache(s, cache)
        cache = result
      else:
        result = newRope(s)

proc rope*(i: BiggestInt): Rope {.rtl, extern: "nro$1BiggestInt".} =
  ## Converts an int to a rope.
  result = rope($i)

proc rope*(f: BiggestFloat): Rope {.rtl, extern: "nro$1BiggestFloat".} =
  ## Converts a float to a rope.
  result = rope($f)

proc enableCache*() {.rtl, extern: "nro$1".} =
  ## Enables the caching of leaves. This reduces the memory footprint at
  ## the cost of runtime efficiency.
  cacheEnabled = true

proc disableCache*() {.rtl, extern: "nro$1".} =
  ## the cache is discarded and disabled. The GC will reuse its used memory.
  cache = nil
  cacheEnabled = false

proc `&`*(a, b: Rope): Rope {.rtl, extern: "nroConcRopeRope".} =
  ## the concatenation operator for ropes.
  if a == nil:
    result = b
  elif b == nil:
    result = a
  else:
    result = newRope()
    result.length = a.length + b.length
    result.left = a
    result.right = b

proc `&`*(a: Rope, b: string): Rope {.rtl, extern: "nroConcRopeStr".} =
  ## the concatenation operator for ropes.
  result = a & rope(b)

proc `&`*(a: string, b: Rope): Rope {.rtl, extern: "nroConcStrRope".} =
  ## the concatenation operator for ropes.
  result = rope(a) & b

proc `&`*(a: openArray[Rope]): Rope {.rtl, extern: "nroConcOpenArray".} =
  ## the concatenation operator for an openarray of ropes.
  for i in countup(0, high(a)): result = result & a[i]

proc add*(a: var Rope, b: Rope) {.rtl, extern: "nro$1Rope".} =
  ## adds `b` to the rope `a`.
  a = a & b

proc add*(a: var Rope, b: string) {.rtl, extern: "nro$1Str".} =
  ## adds `b` to the rope `a`.
  a = a & b

proc `[]`*(r: Rope, i: int): char {.rtl, extern: "nroCharAt".} =
  ## returns the character at position `i` in the rope `r`. This is quite
  ## expensive! Worst-case: O(n). If ``i >= r.len``, ``\0`` is returned.
  var x = r
  var j = i
  if x == nil: return
  while true:
    if x != nil and x.data.len > 0:
      if j < x.data.len: return x.data[j]
      return '\0'
    else:
      if x.left.length > j:
        x = x.left
      else:
        x = x.right
        dec(j, x.len)

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 write*(f: File, r: Rope) {.rtl, extern: "nro$1".} =
  ## writes a rope to a file.
  for s in leaves(r): write(f, s)

proc write*(s: Stream, r: Rope) {.rtl, extern: "nroWriteStream".} =
  ## writes a rope to a stream.
  for rs in leaves(r): write(s, rs)

proc `$`*(r: Rope): string {.rtl, extern: "nroToString".} =
  ## converts a rope back to a string.
  result = newStringOfCap(r.len)
  for s in leaves(r): add(result, s)

proc `%`*(frmt: string, args: openArray[Rope]): Rope {.
  rtl, extern: "nroFormat".} =
  ## `%` substitution operator for ropes. Does not support the ``$identifier``
  ## nor ``${identifier}`` notations.
  var i = 0
  var length = len(frmt)
  result = nil
  var num = 0
  while i < length:
    if frmt[i] == '$':
      inc(i)
      case frmt[i]
      of '$':
        add(result, "$")
        inc(i)
      of '#':
        inc(i)
        add(result, args[num])
        inc(num)
      of '0'..'9':
        var j = 0
        while true:
          j = j * 10 + ord(frmt[i]) - ord('0')
          inc(i)
          if frmt[i] notin {'0'..'9'}: break
        add(result, args[j-1])
      of '{':
        inc(i)
        var j = 0
        while frmt[i] in {'0'..'9'}:
          j = j * 10 + ord(frmt[i]) - ord('0')
          inc(i)
        if frmt[i] == '}': inc(i)
        else: raise newException(ValueError, "invalid format string")

        add(result, args[j-1])
      else: raise newException(ValueError, "invalid format string")
    var start = i
    while i < length:
      if frmt[i] != '$': inc(i)
      else: break
    if i - 1 >= start:
      add(result, substr(frmt, start, i - 1))

proc addf*(c: var Rope, frmt: string, args: openArray[Rope]) {.
  rtl, extern: "nro$1".} =
  ## shortcut for ``add(c, frmt % args)``.
  add(c, frmt % args)

when not defined(js) and not defined(nimscript):
  const
    bufSize = 1024 # 1 KB is reasonable

  proc equalsFile*(r: Rope, f: File): bool {.rtl, extern: "nro$1File".} =
    ## returns true if the contents of the file `f` equal `r`.
    var
      buf: array[bufSize, char]
      bpos = buf.len
      blen = buf.len

    for s in leaves(r):
      var spos = 0
      let slen = s.len
      while spos < slen:
        if bpos == blen:
          # Read more data
          bpos = 0
          blen = readBuffer(f, addr(buf[0]), buf.len)
          if blen == 0: # no more data in file
            result = false
            return
        let n = min(blen - bpos, slen - spos)
        # TODO There's gotta be a better way of comparing here...
        if not equalMem(addr(buf[bpos]),
                        cast[pointer](cast[int](cstring(s))+spos), n):
          result = false
          return
        spos += n
        bpos += n

    result = readBuffer(f, addr(buf[0]), 1) == 0 # check that we've read all

  proc equalsFile*(r: Rope, filename: string): bool {.rtl, extern: "nro$1Str".} =
    ## returns true if the contents of the file `f` equal `r`. If `f` does not
    ## exist, false is returned.
    var f: File
    result = open(f, filename)
    if result:
      result = equalsFile(r, f)
      close(f)

new(N) # init dummy node for splay algorithm

{.pop.}