1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or is a part of
11 # Ropes with a special kind of Leaves that act similar to a `Buffer`
13 # When using this module, re-allocations are limited by the introduction
14 # of a larger-than-necessary buffered area for the native part of a `String`
15 # in an append-only fashion.
17 # Concretely, when concatenating two small strings of length `n` + `m` < `maxlen`
18 # What happens is that a `maxlen` byte buffer is allocated, ready to receive more
19 # bytes a posteriori without necessarily reallocating a new byte array.
21 # Theoretically, this should lower the number of concatenations
22 # and reallocations when concatenating `String` objects.
25 intrude import core
::text
::ropes
27 # Hidden buffer, used to simulate a `FlatBuffer` on a short string.
29 # This is to be used by low-level APIs because of its lack of
30 # safety, if you use it, make sure you know what you are doing !
32 # Practically, it is the underlying representation of a `Leaf` in
33 # the `Rope` block, its advantage is that it saves a bit more space
34 # for future concatenations, without risking to overwrite previously
35 # used space, making it suitable for Strings.
37 # Note for future use : Should there be parallel capacity in Nit at
38 # some point, this is NOT thread safe !
39 private class ManualBuffer
40 var ns
: NativeString is noinit
41 # Current position in the `NativeString`
43 # It is used by the clients of `ManualBuffer` as a guard
44 # to detect if the concatenation in the `ManualBuffer`
48 # Say we have two strings `x` and `y` referencing the
49 # same `ManualBuffer` `b`, `y` is the concatenation of
50 # `x` and another string.
52 # If we try to concatenate a `String` `z` to `x`, a new
53 # `ManualBuffer` will be created since `pos` and `x.length`
56 # However, if we concatenate the same `String` to `y`,
57 # the contents of `z` will be copied to the `ManualBuffer`.
60 init do ns
= new NativeString(maxlen
)
62 fun [](i
: Int): Byte do return ns
[i
]
65 # Simple implementation of the iterator on Substrings for `Leaf`
67 # Basically just returns `self` encapsulated in a `FlatString`.
68 private class LeafSubstrings
69 super IndexedIterator[FlatText]
72 var str
: FlatString is noinit
76 str
= new FlatString.with_infos
(leaf
.buf
.ns
, leaf
.length
, 0, leaf
.length
- 1)
79 redef fun is_ok
do return avail
81 redef fun next
do avail
= false
83 redef fun index
do return 0
85 redef fun item
do return str
88 # Leaf of a `Rope`, used as a buffered area for speedy concatenation.
94 var bns
: NativeString is noinit
95 redef var length
is noinit
97 # Unsafe, but since it is an experiment, don't mind
98 redef fun bytelen
do return length
100 redef fun empty
do return new Leaf(new ManualBuffer)
102 redef fun to_cstring
do
104 var ns
= new NativeString(len
+ 1)
106 buf
.ns
.copy_to
(ns
, len
, 0, 0)
110 redef fun substrings
do return new LeafSubstrings(self)
112 redef fun [](i
) do return buf
[i
].to_i
.ascii
119 redef fun output
do new FlatString.with_infos
(buf
.ns
, length
, 0, length
- 1).output
121 redef fun to_upper
do
122 var x
= new FlatBuffer
123 for i
in chars
do x
.add
(i
.to_upper
)
127 redef fun to_lower
do
128 var x
= new FlatBuffer
129 for i
in chars
do x
.add
(i
.to_lower
)
133 redef fun reversed
do
134 var x
= new ManualBuffer
139 for i
in [0 .. mlen
[ do
147 redef fun substring
(from
, len
) do
148 return new FlatString.with_infos
(buf
.ns
, len
, from
, from
+ len
- 1)
151 redef fun insert_at
(s
, pos
) do
152 var l
= substring
(0, pos
)
153 var r
= substring_from
(pos
)
161 if slen
== 0 then return self
162 if mlen
== 0 then return s
163 var nlen
= mlen
+ slen
164 if nlen
> maxlen
then return new Concat(self, s
)
165 if s
isa FlatString then
169 sits
.copy_to
(buf
.ns
, slen
, s
.first_byte
, bpos
)
170 buf
.pos
= bpos
+ slen
173 var b
= new ManualBuffer
175 bns
.copy_to
(nbns
, mlen
, 0, 0)
176 sits
.copy_to
(nbns
, slen
, s
.first_byte
, mlen
)
180 else if s
isa Leaf then
184 sbns
.copy_to
(bns
, slen
, 0, bpos
)
188 var b
= new ManualBuffer
190 bns
.copy_to
(nbns
, mlen
, 0, 0)
191 sbns
.copy_to
(nbns
, slen
, 0, mlen
)
195 else if s
isa Concat then
196 if not s
.left
isa Concat then
197 return new Concat(self + s
.left
, s
.right
)
199 return new Concat(self, s
)
205 bns
.copy_to
(b
.ns
, mlen
, 0, 0)
217 redef fun to_cstring
do
219 var ns
= new NativeString(len
+ 1)
222 for i
in substrings
do
224 if i
isa FlatString then
225 i
.items
.copy_to
(ns
, ilen
, i
.first_byte
, off
)
226 else if i
isa Leaf then
227 i
.buf
.ns
.copy_to
(ns
, ilen
, 0, off
)
239 if s
isa FlatString then
242 if rlen
+ slen
> maxlen
then return new Concat(left
, new Concat(r
, s
))
243 return new Concat(left
, r
+ s
)
244 else if s
isa Concat then
245 return new Concat(self, s
)
246 else if s
isa Leaf then
249 if rlen
+ slen
> maxlen
then return new Concat(left
, new Concat(r
, s
))
250 return new Concat(left
, r
+ s
)
257 redef class FlatString
262 if slen
== 0 then return self
263 if mlen
== 0 then return s
264 if s
isa FlatString then
265 if slen
+ mlen
> maxlen
then return new Concat(self, s
)
267 var sifrom
= s
.first_byte
268 var mifrom
= first_byte
270 var b
= new ManualBuffer
272 mits
.copy_to
(bns
, mlen
, mifrom
, 0)
273 sits
.copy_to
(bns
, slen
, sifrom
, mlen
)
276 else if s
isa Concat then
278 var sllen
= sl
.length
279 if sllen
+ mlen
> maxlen
then return new Concat(self, s
)
280 return new Concat(sl
+ self, s
.right
)
281 else if s
isa Leaf then
282 if slen
+ mlen
> maxlen
then return new Concat(self, s
)
283 var mifrom
= first_byte
285 var b
= new ManualBuffer
287 items
.copy_to
(bns
, mlen
, mifrom
, 0)
288 sb
.ns
.copy_to
(bns
, slen
, 0, mlen
)
299 # Fast implementation
302 if l
== 0 then return ""
303 if l
== 1 then if self[0] == null then return "" else return self[0].to_s
305 var na
= new NativeArray[String](l
)
321 var ns
= new NativeString(sl
+ 1)
328 if tmp
isa FlatString then
329 tmp
.items
.copy_to
(ns
, tpl
, tmp
.first_byte
, off
)
332 for j
in tmp
.substrings
do
334 if j
isa FlatString then
335 j
.items
.copy_to
(ns
, slen
, j
.first_byte
, off
)
336 else if j
isa Leaf then
337 j
.buf
.ns
.copy_to
(ns
, slen
, 0, off
)
344 return ns
.to_s_with_length
(sl
)