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