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::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[Text]
  70
  71         var leaf: Leaf
  72         var str: String 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 RopeString
  91
  92         var buf: ManualBuffer
  93         var bns: NativeString is noinit
  94         redef var length: Int is noinit
  95
  96         redef fun empty do return new Leaf(new ManualBuffer)
  97
  98         redef fun to_cstring do
  99                 var len = length
 100                 var ns = new NativeString(len + 1)
 101                 ns[len] = '\0'
 102                 buf.ns.copy_to(ns, len, 0, 0)
 103                 return ns
 104         end
 105
 106         redef fun substrings do return new LeafSubstrings(self)
 107
 108         redef fun [](i) do return buf[i]
 109
 110         init do
 111                 bns = buf.ns
 112                 length = buf.pos
 113         end
 114
 115         redef fun output do new FlatString.with_infos(buf.ns, length, 0, length - 1).output
 116
 117         redef fun to_upper do
 118                 var x = new ManualBuffer
 119                 var nns = x.ns
 120                 var ns = bns
 121                 var mlen = length
 122                 for i in [0..mlen[ do
 123                         nns[i] = ns[i].to_upper
 124                 end
 125                 x.pos = mlen - 1
 126                 return new Leaf(x)
 127         end
 128
 129         redef fun to_lower do
 130                 var x = new ManualBuffer
 131                 var nns = x.ns
 132                 var ns = bns
 133                 var mlen = length
 134                 for i in [0..mlen[ do
 135                         nns[i] = ns[i].to_lower
 136                 end
 137                 x.pos = mlen - 1
 138                 return new Leaf(x)
 139         end
 140
 141         redef fun reversed do
 142                 var x = new ManualBuffer
 143                 var nns = x.ns
 144                 var ns = bns
 145                 var mlen = length
 146                 var j = mlen - 1
 147                 for i in [0 .. mlen[ do
 148                         nns[j] = ns[i]
 149                         j -= 1
 150                 end
 151                 x.pos = mlen - 1
 152                 return new Leaf(x)
 153         end
 154
 155         redef fun substring(from, len) do
 156                 return new FlatString.with_infos(buf.ns, len, from, from + len - 1)
 157         end
 158
 159         redef fun insert_at(s, pos) do
 160                 var l = substring(0, pos)
 161                 var r = substring_from(pos)
 162                 return l + s + r
 163         end
 164
 165         redef fun +(o) do
 166                 var s = o.to_s
 167                 var slen = s.length
 168                 var mlen = length
 169                 if slen == 0 then return self
 170                 if mlen == 0 then return s
 171                 var nlen = mlen + slen
 172                 if nlen > maxlen then return new Concat(self, s)
 173                 if s isa FlatString then
 174                         var bpos = buf.pos
 175                         var sits = s.items
 176                         if bpos == mlen then
 177                                 sits.copy_to(buf.ns, slen, s.index_from, bpos)
 178                                 buf.pos = bpos + slen
 179                                 return new Leaf(buf)
 180                         else
 181                                 var b = new ManualBuffer
 182                                 var nbns = b.ns
 183                                 bns.copy_to(nbns, mlen, 0, 0)
 184                                 sits.copy_to(nbns, slen, s.index_from, mlen)
 185                                 b.pos = nlen
 186                                 return new Leaf(b)
 187                         end
 188                 else if s isa Leaf then
 189                         var bpos = buf.pos
 190                         var sbns = s.bns
 191                         if bpos == mlen then
 192                                 sbns.copy_to(bns, slen, 0, bpos)
 193                                 buf.pos += slen
 194                                 return new Leaf(buf)
 195                         else
 196                                 var b = new ManualBuffer
 197                                 var nbns = b.ns
 198                                 bns.copy_to(nbns, mlen, 0, 0)
 199                                 sbns.copy_to(nbns, slen, 0, mlen)
 200                                 b.pos = nlen
 201                                 return new Leaf(b)
 202                         end
 203                 else if s isa Concat then
 204                         if not s.left isa Concat then
 205                                 return new Concat(self + s.left, s.right)
 206                         end
 207                         return new Concat(self, s)
 208                 else
 209                         var bpos = buf.pos
 210                         var b = buf
 211                         if bpos != mlen then
 212                                 b = new ManualBuffer
 213                                 bns.copy_to(b.ns, mlen, 0, 0)
 214                         end
 215                         for i in s.chars do
 216                                 bns[bpos] = i
 217                                 bpos += 1
 218                         end
 219                         return new Leaf(b)
 220                 end
 221         end
 222 end
 223
 224 redef class Concat
 225         redef fun to_cstring do
 226                 var len = length
 227                 var ns = new NativeString(len + 1)
 228                 ns[len] = '\0'
 229                 var off = 0
 230                 for i in substrings do
 231                         var ilen = i.length
 232                         if i isa FlatString then
 233                                 i.items.copy_to(ns, ilen, i.index_from, off)
 234                         else if i isa Leaf then
 235                                 i.buf.ns.copy_to(ns, ilen, 0, off)
 236                         else
 237                                 abort
 238                         end
 239                         off += ilen
 240                 end
 241                 return ns
 242         end
 243
 244         redef fun +(o) do
 245                 var s = o.to_s
 246                 var slen = s.length
 247                 if s isa FlatString then
 248                         var r = right
 249                         var rlen = r.length
 250                         if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
 251                         return new Concat(left, r + s)
 252                 else if s isa Concat then
 253                         return new Concat(self, s)
 254                 else if s isa Leaf then
 255                         var r = right
 256                         var rlen = r.length
 257                         if rlen + slen > maxlen then return new Concat(left, new Concat(r, s))
 258                         return new Concat(left, r + s)
 259                 else
 260                         abort
 261                 end
 262         end
 263 end
 264
 265 redef class FlatString
 266         redef fun +(o) do
 267                 var s = o.to_s
 268                 var slen = s.length
 269                 var mlen = length
 270                 if slen == 0 then return self
 271                 if mlen == 0 then return s
 272                 if s isa FlatString then
 273                         if slen + mlen > maxlen then return new Concat(self, s)
 274                         var mits = items
 275                         var sifrom = s.index_from
 276                         var mifrom = index_from
 277                         var sits = s.items
 278                         var b = new ManualBuffer
 279                         var bns = b.ns
 280                         mits.copy_to(bns, mlen, mifrom, 0)
 281                         sits.copy_to(bns, slen, sifrom, mlen)
 282                         b.pos = mlen + slen
 283                         return new Leaf(b)
 284                 else if s isa Concat then
 285                         var sl = s.left
 286                         var sllen = sl.length
 287                         if sllen + mlen > maxlen then return new Concat(self, s)
 288                         return new Concat(sl + self, s.right)
 289                 else if s isa Leaf then
 290                         if slen + mlen > maxlen then return new Concat(self, s)
 291                         var mifrom = index_from
 292                         var sb = s.buf
 293                         var b = new ManualBuffer
 294                         var bns = b.ns
 295                         items.copy_to(bns, mlen, mifrom, 0)
 296                         sb.ns.copy_to(bns, slen, 0, mlen)
 297                         b.pos = mlen + slen
 298                         return new Leaf(b)
 299                 else
 300                         abort
 301                 end
 302         end
 303 end
 304
 305 redef class Array[E]
 306
 307         # Fast implementation
 308         redef fun to_s do
 309                 var l = length
 310                 if l == 0 then return ""
 311                 if l == 1 then if self[0] == null then return "" else return self[0].to_s
 312                 var its = _items
 313                 var na = new NativeArray[String](l)
 314                 var i = 0
 315                 var sl = 0
 316                 var mypos = 0
 317                 while i < l do
 318                         var itsi = its[i]
 319                         if itsi == null then
 320                                 i += 1
 321                                 continue
 322                         end
 323                         var tmp = itsi.to_s
 324                         sl += tmp.length
 325                         na[mypos] = tmp
 326                         i += 1
 327                         mypos += 1
 328                 end
 329                 var ns = new NativeString(sl + 1)
 330                 ns[sl] = '\0'
 331                 i = 0
 332                 var off = 0
 333                 while i < mypos do
 334                         var tmp = na[i]
 335                         var tpl = tmp.length
 336                         if tmp isa FlatString then
 337                                 tmp.items.copy_to(ns, tpl, tmp.index_from, off)
 338                                 off += tpl
 339                         else
 340                                 for j in tmp.substrings do
 341                                         var slen = j.length
 342                                         if j isa FlatString then
 343                                                 j.items.copy_to(ns, slen, j.index_from, off)
 344                                         else if j isa Leaf then
 345                                                 j.buf.ns.copy_to(ns, slen, 0, off)
 346                                         end
 347                                         off += slen
 348                                 end
 349                         end
 350                         i += 1
 351                 end
 352                 return ns.to_s_with_length(sl)
 353         end
 354 end