forked from nim-lang/Nim
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathropes.nim
338 lines (300 loc) · 8.94 KB
/
ropes.nim
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
335
336
337
338
#
#
# The Nim Compiler
# (c) Copyright 2012 Andreas Rumpf
#
# See the file "copying.txt", included in this
# 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
from pathutils import AbsoluteFile
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
proc len*(a: Rope): int =
## the rope's length
if a == nil: result = 0
else: result = abs a.L
proc newRope(data: string = ""): Rope =
new(result)
result.L = -data.len
result.data = data
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 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))
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)
proc writeRope*(head: Rope, filename: AbsoluteFile): bool =
var f: File
if open(f, filename.string, fmWrite):
if head != nil: 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
var num = 0
while i < frmt.len:
if frmt[i] == '$':
inc(i) # skip '$'
case frmt[i]
of '$':
result.add("$")
inc(i)
of '#':
inc(i)
result.add(args[num])
inc(num)
of '0'..'9':
var j = 0
while true:
j = j * 10 + ord(frmt[i]) - ord('0')
inc(i)
if i >= frmt.len or frmt[i] notin {'0'..'9'}: break
num = j
if j > high(args) + 1:
doAssert false, "invalid format string: " & frmt
else:
result.add(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)
num = j
if frmt[i] == '}': inc(i)
else:
doAssert false, "invalid format string: " & frmt
if j > high(args) + 1:
doAssert false, "invalid format string: " & frmt
else:
result.add(args[j-1])
of 'n':
result.add("\n")
inc(i)
of 'N':
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))
proc `%`*(frmt: static[FormatStr], args: openArray[Rope]): Rope =
runtimeFormat(frmt, args)
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 =
## returns true if the contents of the file `f` equal `r`.
var
buf: array[bufSize, char]
bpos = buf.len
blen = buf.len
btotal = 0
rtotal = 0
for s in leaves(r):
var spos = 0
rtotal += s.len
while spos < s.len:
if bpos == blen:
# Read more data
bpos = 0
blen = readBuffer(f, addr(buf[0]), buf.len)
btotal += blen
if blen == 0: # no more data in file
result = false
return
let n = min(blen - bpos, s.len - 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 and
btotal == rtotal # check that we've read all
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
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