lib/buffered_ropes.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   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
   9 # another product.
  10
  11 # Ropes with a special kind of Leaves that act similar to a `Buffer`
  12 #
  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.
  16 #
  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.
  20 #
  21 # Theoretically, this should lower the number of concatenations
  22 # and reallocations when concatenating `String` objects.
  23 module buffered_ropes
  24
  25 intrude import standard::text::ropes
  26
  27 # Hidden buffer, used to simulate a `FlatBuffer` on a short string.
  28 #
  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 !
  31 #
  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.
  36 #
  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`
  42         #
  43         # It is used by the clients of `ManualBuffer` as a guard
  44         # to detect if the concatenation in the `ManualBuffer`
  45         # is safe or not.
  46         #
  47         # i.e. :
  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.
  51         #
  52         # If we try to concatenate a `String` `z` to `x`, a new
  53         # `ManualBuffer` will be created since `pos` and `x.length`
  54         # do not match.
  55         #
  56         # However, if we concatenate the same `String` to `y`,
  57         # the contents of `z` will be copied to the `ManualBuffer`.
  58         var pos = 0
  59
  60         init do ns = new NativeString(maxlen)
  61
  62         fun [](i: Int): Char do return ns[i]
  63 end
  64
  65 # Simple implementation of the iterator on Substrings for `Leaf`
  66 #
  67 # Basically just returns `self` encapsulated in a `FlatString`.
  68 private class LeafSubstrings
  69         super IndexedIterator[FlatText]
  70
  71         var leaf: Leaf
  72         var str: FlatString is noinit
  73         var avail = true
  74
  75         init do
  76                 str = new FlatString.with_infos(leaf.buf.ns, leaf.length, 0, leaf.length - 1)
  77         end
  78
  79         redef fun is_ok do return avail
  80
  81         redef fun next do avail = false
  82
  83         redef fun index do return 0
  84
  85         redef fun item do return str
  86 end
  87
  88 # Leaf of a `Rope`, used as a buffered area for speedy concatenation.
  89 private class Leaf
  90         super String
  91         super Rope
  92
  93         var buf: ManualBuffer
  94         var bns: NativeString is noinit
  95         redef var length: Int is noinit
  96
  97         redef fun empty do return new Leaf(new ManualBuffer)
  98
  99         redef fun to_cstring do
 100                 var len = length
 101                 var ns = new NativeString(len + 1)
 102                 ns[len] = '\0'
 103                 buf.ns.copy_to(ns, len, 0, 0)
 104                 return ns
 105         end
 106
 107         redef fun substrings do return new LeafSubstrings(self)
 108
 109         redef fun [](i) do return buf[i]
 110
 111         init do
 112                 bns = buf.ns
 113                 length = buf.pos
 114         end
 115
 116         redef fun output do new FlatString.with_infos(buf.ns, length, 0, length - 1).output
 117
 118         redef fun to_upper do
 119                 var x = new ManualBuffer
 120                 var nns = x.ns
 121                 var ns = bns
 122                 var mlen = length
 123                 for i in [0..mlen[ do
 124                         nns[i] = ns[i].to_upper
 125                 end
 126                 x.pos = mlen - 1
 127                 return new Leaf(x)
 128         end
 129
 130         redef fun to_lower do
 131                 var x = new ManualBuffer
 132                 var nns = x.ns
 133                 var ns = bns
 134                 var mlen = length
 135                 for i in [0..mlen[ do
 136                         nns[i] = ns[i].to_lower
 137                 end
 138                 x.pos = mlen - 1
 139                 return new Leaf(x)
 140         end
 141
 142         redef fun reversed do
 143                 var x = new ManualBuffer
 144                 var nns = x.ns
 145                 var ns = bns
 146                 var mlen = length
 147                 var j = mlen - 1
 148                 for i in [0 .. mlen[ do
 149                         nns[j] = ns[i]
 150                         j -= 1
 151                 end
 152                 x.pos = mlen - 1
 153                 return new Leaf(x)
 154         end
 155
 156         redef fun substring(from, len) do
 157                 return new FlatString.with_infos(buf.ns, len, from, from + len - 1)
 158         end
 159
 160         redef fun insert_at(s, pos) do
 161                 var l = substring(0, pos)
 162                 var r = substring_from(pos)
 163                 return l + s + r
 164         end
 165
 166         redef fun +(o) do
 167                 var s = o.to_s
 168                 var slen = s.length
 169                 var mlen = length
 170                 if slen == 0 then return self
 171                 if mlen == 0 then return s
 172                 var nlen = mlen + slen
 173                 if nlen > maxlen then return new Concat(self, s)
 174                 if s isa FlatString then
 175                         var bpos = buf.pos
 176                         var sits = s.items
 177                         if bpos == mlen then
 178                                 sits.copy_to(buf.ns, slen, s.index_from, bpos)
 179                                 buf.pos = bpos + slen
 180                                 return new Leaf(buf)
 181                         else
 182                                 var b = new ManualBuffer
 183                                 var nbns = b.ns
 184                                 bns.copy_to(nbns, mlen, 0, 0)
 185                                 sits.copy_to(nbns, slen, s.index_from, mlen)
 186                                 b.pos = nlen
 187                                 return new Leaf(b)
 188                         end
 189                 else if s isa Leaf then
 190                         var bpos = buf.pos
 191                         var sbns = s.bns
 192                         if bpos == mlen then
 193                                 sbns.copy_to(bns, slen, 0, bpos)
 194                                 buf.pos += slen
 195                                 return new Leaf(buf)
 196                         else
 197                                 var b = new ManualBuffer
 198                                 var nbns = b.ns
 199                                 bns.copy_to(nbns, mlen, 0, 0)
 200                                 sbns.copy_to(nbns, slen, 0, mlen)
 201                                 b.pos = nlen
 202                                 return new Leaf(b)
 203                         end
 204                 else if s isa Concat then
 205                         if not s.left isa Concat then
 206                                 return new Concat(self + s.left, s.right)
 207                         end
 208                         return new Concat(self, s)
 209                 else
 210                         var bpos = buf.pos
 211                         var b = buf
 212                         if bpos != mlen then
 213                                 b = new ManualBuffer
 214                                 bns.copy_to(b.ns, mlen, 0, 0)
 215                         end
 216                         for i in s.chars do
 217                                 bns[bpos] = i
 218                                 bpos += 1
 219                         end
 220                         return new Leaf(b)
 221                 end
 222         end
 223 end
 224
 225 redef class Concat
 226         redef fun to_cstring do
 227                 var len = length
 228                 var ns = new NativeString(len + 1)
 229                 ns[len] = '\0'
 230                 var off = 0
 231                 for i in substrings do
 232                         var ilen = i.length
 233                         if i isa FlatString then
 234                                 i.items.copy_to(ns, ilen, i.index_from, off)
 235                         else if i isa Leaf then
 236                                 i.buf.ns.copy_to(ns, ilen, 0, off)
 237                         else
 238                                 abort
 239                         end
 240                         off += ilen
 241                 end
 242                 return ns
 243         end
 244
 245         redef fun +(o) do
 246                 var s = o.to_s
 247                 var slen = s.length
 248                 if s isa FlatString then
 249                         var r = right
 250                         var rlen = r.length
 251                         if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
 252                         return new Concat(left, r + s)
 253                 else if s isa Concat then
 254                         return new Concat(self, s)
 255                 else if s isa Leaf then
 256                         var r = right
 257                         var rlen = r.length
 258                         if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
 259                         return new Concat(left, r + s)
 260                 else
 261                         abort
 262                 end
 263         end
 264 end
 265
 266 redef class FlatString
 267         redef fun +(o) do
 268                 var s = o.to_s
 269                 var slen = s.length
 270                 var mlen = length
 271                 if slen == 0 then return self
 272                 if mlen == 0 then return s
 273                 if s isa FlatString then
 274                         if slen + mlen > maxlen then return new Concat(self, s)
 275                         var mits = items
 276                         var sifrom = s.index_from
 277                         var mifrom = index_from
 278                         var sits = s.items
 279                         var b = new ManualBuffer
 280                         var bns = b.ns
 281                         mits.copy_to(bns, mlen, mifrom, 0)
 282                         sits.copy_to(bns, slen, sifrom, mlen)
 283                         b.pos = mlen + slen
 284                         return new Leaf(b)
 285                 else if s isa Concat then
 286                         var sl = s.left
 287                         var sllen = sl.length
 288                         if sllen + mlen > maxlen then return new Concat(self, s)
 289                         return new Concat(sl + self, s.right)
 290                 else if s isa Leaf then
 291                         if slen + mlen > maxlen then return new Concat(self, s)
 292                         var mifrom = index_from
 293                         var sb = s.buf
 294                         var b = new ManualBuffer
 295                         var bns = b.ns
 296                         items.copy_to(bns, mlen, mifrom, 0)
 297                         sb.ns.copy_to(bns, slen, 0, mlen)
 298                         b.pos = mlen + slen
 299                         return new Leaf(b)
 300                 else
 301                         abort
 302                 end
 303         end
 304 end
 305
 306 redef class Array[E]
 307
 308         # Fast implementation
 309         redef fun to_s do
 310                 var l = length
 311                 if l == 0 then return ""
 312                 if l == 1 then if self[0] == null then return "" else return self[0].to_s
 313                 var its = _items
 314                 var na = new NativeArray[String](l)
 315                 var i = 0
 316                 var sl = 0
 317                 var mypos = 0
 318                 while i < l do
 319                         var itsi = its[i]
 320                         if itsi == null then
 321                                 i += 1
 322                                 continue
 323                         end
 324                         var tmp = itsi.to_s
 325                         sl += tmp.length
 326                         na[mypos] = tmp
 327                         i += 1
 328                         mypos += 1
 329                 end
 330                 var ns = new NativeString(sl + 1)
 331                 ns[sl] = '\0'
 332                 i = 0
 333                 var off = 0
 334                 while i < mypos do
 335                         var tmp = na[i]
 336                         var tpl = tmp.length
 337                         if tmp isa FlatString then
 338                                 tmp.items.copy_to(ns, tpl, tmp.index_from, off)
 339                                 off += tpl
 340                         else
 341                                 for j in tmp.substrings do
 342                                         var slen = j.length
 343                                         if j isa FlatString then
 344                                                 j.items.copy_to(ns, slen, j.index_from, off)
 345                                         else if j isa Leaf then
 346                                                 j.buf.ns.copy_to(ns, slen, 0, off)
 347                                         end
 348                                         off += slen
 349                                 end
 350                         end
 351                         i += 1
 352                 end
 353                 return ns.to_s_with_length(sl)
 354         end
 355 end