X-Git-Url: http://nitlanguage.org diff --git a/lib/core/text/ropes.nit b/lib/core/text/ropes.nit index f582292..f57b33d 100644 --- a/lib/core/text/ropes.nit +++ b/lib/core/text/ropes.nit @@ -78,24 +78,26 @@ private class Concat redef var bytelen is noinit - redef fun substrings do return new RopeSubstrings(self) + redef fun substrings do return new RopeSubstrings.from(self, 0) redef fun empty do return "" # Cache for the latest accessed FlatString in `self` - var flat_cache: String = "" + var flat_cache: FlatString is noinit # Position of the beginning of `flat_cache` in `self` var flat_last_pos_start: Int = -1 + var flat_last_pos_end: Int = -1 + redef var to_cstring is lazy do - var len = bytelen + var len = _bytelen var ns = new NativeString(len + 1) ns[len] = 0u8 var off = 0 for i in substrings do - var ilen = i.bytelen - i.as(FlatString).items.copy_to(ns, ilen, i.as(FlatString).first_byte, off) + var ilen = i._bytelen + i.as(FlatString)._items.copy_to(ns, ilen, i.as(FlatString)._first_byte, off) off += ilen end return ns @@ -107,16 +109,20 @@ private class Concat var right: String init do - length = left.length + right.length - bytelen = left.bytelen + right.bytelen + var l = _left + var r = _right + length = l.length + r.length + _bytelen = l.bytelen + r.bytelen end + redef fun is_empty do return _bytelen == 0 + redef fun output do - left.output - right.output + _left.output + _right.output end - redef fun iterator do return new RopeCharIterator(self) + redef fun iterator do return new RopeCharIterator.from(self, 0) redef fun *(i) do var x: String = self @@ -125,52 +131,81 @@ private class Concat end redef fun [](i) do - if flat_last_pos_start != -1 then - var fsp = i - flat_last_pos_start - if fsp >= 0 and fsp < flat_cache.length then return flat_cache[fsp] + assert i >= 0 and i <= _length + var flps = _flat_last_pos_start + if flps != -1 and i >= flps and i <= _flat_last_pos_end then + return _flat_cache.fetch_char_at(i - flps) + end + var lf = get_leaf_at(i) + return lf.fetch_char_at(i - _flat_last_pos_start) + end + + fun get_leaf_at(pos: Int): FlatString do + var flps = _flat_last_pos_start + if flps != -1 and pos >= flps and pos <= _flat_last_pos_end then + return _flat_cache end var s: String = self - var st = i + var st = pos loop if s isa FlatString then break s = s.as(Concat) - var lft = s.left + var lft = s._left var llen = lft.length - if i >= llen then - s = s.right - i -= llen + if pos >= llen then + s = s._right + pos -= llen else - s = s.left + s = lft end end - flat_last_pos_start = st - i - flat_cache = s - return s[i] + _flat_last_pos_start = st - pos + _flat_last_pos_end = st - pos + s.length - 1 + _flat_cache = s + return s end - redef fun substring(from, len) do - var llen = left.length + redef fun substring(from, count) do + if from < 0 then + count += from + if count < 0 then return "" + from = 0 + end + + var ln = _length + if (count + from) > ln then count = ln - from + if count <= 0 then return "" + var end_index = from + count - 1 + + var flps = _flat_last_pos_start + if flps != -1 and from >= flps and end_index <= _flat_last_pos_end then + return _flat_cache.substring_impl(from - flps, count, end_index - flps) + end + + var lft = _left + var llen = lft.length if from < llen then - if from + len < llen then return left.substring(from,len) + if from + count < llen then return lft.substring(from, count) var lsublen = llen - from - return left.substring_from(from) + right.substring(0, len - lsublen) + return lft.substring_from(from) + _right.substring(0, count - lsublen) else - return right.substring(from - llen, len) + return _right.substring(from - llen, count) end end - redef fun reversed do return new Concat(right.reversed, left.reversed) + redef fun reversed do return new Concat(_right.reversed, _left.reversed) redef fun insert_at(s, pos) do - if pos > left.length then - return left + right.insert_at(s, pos - left.length) + var lft = _left + if pos > lft.length then + return lft + _right.insert_at(s, pos - lft.length) end - return left.insert_at(s, pos) + right + return lft.insert_at(s, pos) + _right end - redef fun to_upper do return new Concat(left.to_upper, right.to_upper) + redef fun to_upper do return new Concat(_left.to_upper, _right.to_upper) - redef fun to_lower do return new Concat(left.to_lower, right.to_lower) + redef fun to_lower do return new Concat(_left.to_lower, _right.to_lower) redef fun +(o) do var s = o.to_s @@ -178,31 +213,24 @@ private class Concat if s isa Concat then return new Concat(self, s) else - var r = right + var r = _right var rlen = r.bytelen if rlen + slen > maxlen then return new Concat(self, s) - return new Concat(left, r + s) + return new Concat(_left, r + s) end end redef fun copy_to_native(dest, n, src_offset, dest_offset) do - var subs = new RopeSubstrings.from(self, src_offset) - var st = src_offset - subs.pos - var off = dest_offset - while n > 0 do - var it = subs.item - if n > it.length then - var cplen = it.length - st - it.items.copy_to(dest, cplen, st, off) - off += cplen - n -= cplen - else - it.items.copy_to(dest, n, st, off) - n = 0 - end - subs.next - st = 0 + var l = _left + if src_offset < l.bytelen then + var lcopy = l.bytelen - src_offset + lcopy = if lcopy > n then n else lcopy + l.copy_to_native(dest, lcopy, src_offset, dest_offset) + dest_offset += lcopy + n -= lcopy + src_offset = 0 end + _right.copy_to_native(dest, n, src_offset, dest_offset) end # Returns a balanced version of `self` @@ -220,10 +248,10 @@ private class Concat end if not iter.ldone then iter.ldone = true - iter = new RopeCharIteratorPiece(rnod.left, false, false, iter) + iter = new RopeCharIteratorPiece(rnod._left, false, false, iter) else if not iter.rdone then iter.rdone = true - iter = new RopeCharIteratorPiece(rnod.right, false, false, iter) + iter = new RopeCharIteratorPiece(rnod._right, false, false, iter) else iter = iter.prev end @@ -311,7 +339,7 @@ class RopeBuffer # mutable native string (`ns`) private var buf_size: Int is noinit - redef fun substrings do return new RopeBufSubstringIterator(self) + redef fun substrings do return new RopeBufSubstringIterator.from(self) # Builds an empty `RopeBuffer` init do @@ -325,7 +353,7 @@ class RopeBuffer self.str = str ns = new NativeString(maxlen) buf_size = maxlen - bytelen = str.length + _bytelen = str.length dumped = 0 end @@ -356,7 +384,7 @@ class RopeBuffer assert i >= 0 and i <= length if i == length then add c if i < str.length then - bytelen += c.u8char_len - str[i].u8char_len + _bytelen += c.u8char_len - str[i].u8char_len var s = str var l = s.substring(0, i) var r = s.substring_from(i + 1) @@ -379,7 +407,7 @@ class RopeBuffer else ns.copy_to(ns, rpos - st_nxt, st_nxt, st_nxt + delta) end - bytelen += delta + _bytelen += delta rpos += delta end ns.set_char_at(index, c) @@ -390,7 +418,7 @@ class RopeBuffer redef fun clear do str = "" - bytelen = 0 + _bytelen = 0 rpos = 0 dumped = 0 if written then @@ -421,12 +449,12 @@ class RopeBuffer var rem = count - subpos var nns = new NativeString(rem) ns.copy_to(nns, rem, dumped, 0) - return new RopeBuffer.from(l + nns.to_s_with_length(rem)) + return new RopeBuffer.from(l + nns.to_s_unsafe(rem)) end else var nns = new NativeString(count) ns.copy_to(nns, count, dumped, 0) - return new RopeBuffer.from(nns.to_s_with_length(count)) + return new RopeBuffer.from(nns.to_s_unsafe(count)) end end @@ -438,7 +466,7 @@ class RopeBuffer return end if s isa FlatText then - var oits = s.items + var oits = s._items var from = s.first_byte var remsp = buf_size - rpos if slen <= remsp then @@ -459,14 +487,15 @@ class RopeBuffer redef fun add(c) do var rp = rpos - if rp >= buf_size then + var remsp = buf_size - rp + var cln = c.u8char_len + if cln > remsp then dump_buffer rp = 0 end - # TODO: Fix when supporting UTF-8 - ns[rp] = c.ascii.to_b - rp += 1 - bytelen += 1 + ns.set_char_at(rp, c) + rp += cln + _bytelen += cln rpos = rp end @@ -474,7 +503,7 @@ class RopeBuffer # the final String and re-allocates a new larger Buffer. private fun dump_buffer do written = false - var nstr = new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1) + var nstr = new FlatString.with_infos(ns, rpos - dumped, dumped) str += nstr var bs = buf_size bs = bs * 2 @@ -487,14 +516,14 @@ class RopeBuffer # Similar to dump_buffer, but does not reallocate a new NativeString private fun persist_buffer do if rpos == dumped then return - var nstr = new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1) + var nstr = new FlatString.with_infos(ns, rpos - dumped, dumped) str += nstr dumped = rpos end redef fun output do str.output - new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1).output + new FlatString.with_infos(ns, rpos - dumped, dumped).output end # Enlarge is useless here since the `Buffer` @@ -516,7 +545,7 @@ class RopeBuffer redef fun reverse do # Flush the buffer in order to only have to reverse `str`. if rpos > 0 and dumped != rpos then - str += new FlatString.with_infos(ns, rpos - dumped, dumped, rpos - 1) + str += new FlatString.with_infos(ns, rpos - dumped, dumped) dumped = rpos end str = str.reversed @@ -546,25 +575,25 @@ redef class FlatString redef fun +(o) do var s = o.to_s var slen = s.bytelen - var mlen = bytelen + var mlen = _bytelen if slen == 0 then return self if mlen == 0 then return s var nlen = slen + mlen if s isa FlatString then if nlen > maxlen then return new Concat(self, s) - var mits = items - var sifrom = s.first_byte - var mifrom = first_byte - var sits = s.items + var mits = _items + var sifrom = s._first_byte + var mifrom = _first_byte + var sits = s._items var ns = new NativeString(nlen + 1) mits.copy_to(ns, mlen, mifrom, 0) sits.copy_to(ns, slen, sifrom, mlen) - return new FlatString.full(ns, nlen, 0, nlen - 1, length + s.length) + return new FlatString.full(ns, nlen, 0, length + s.length) else if s isa Concat then - var sl = s.left + var sl = s._left var sllen = sl.bytelen if sllen + mlen > maxlen then return new Concat(self, s) - return new Concat(self + sl, s.right) + return new Concat(self + sl, s._right) else abort end @@ -575,9 +604,9 @@ end private class RopeCharIteratorPiece # The encapsulated node of the `Rope` var node: String - # Was its left child (if any) visited ? + # Was its _left child (if any) visited ? var ldone: Bool - # Was its right child (if any) visited ? + # Was its _right child (if any) visited ? var rdone: Bool # The previous node in the list. var prev: nullable RopeCharIteratorPiece @@ -588,28 +617,20 @@ private class RopeByteReverseIterator super IndexedIterator[Byte] # Current NativeString - var ns: NativeString + var ns: NativeString is noautoinit # Current position in NativeString - var pns: Int + var pns: Int is noautoinit # Position in the Rope (0-indexed) - var pos: Int + var pos: Int is noautoinit # Iterator on the substrings, does the Postfix part of # the Rope traversal. - var subs: IndexedIterator[FlatString] - - init(root: Concat) is old_style_init do - pos = root.bytelen - 1 - subs = new ReverseRopeSubstrings(root) - var s = subs.item - ns = s.items - pns = s.last_byte - end + var subs: IndexedIterator[FlatString] is noautoinit init from(root: Concat, pos: Int) do self.pos = pos subs = new ReverseRopeSubstrings.from(root, pos) var s = subs.item - ns = s.items + ns = s._items pns = pos - subs.index end @@ -627,7 +648,7 @@ private class RopeByteReverseIterator subs.next if not subs.is_ok then return var s = subs.item - ns = s.items + ns = s._items pns = s.last_byte end end @@ -637,30 +658,22 @@ private class RopeByteIterator super IndexedIterator[Byte] # Position in current `String` - var pns: Int + var pns: Int is noautoinit # Current `String` being iterated on - var ns: NativeString + var ns: NativeString is noautoinit # Substrings of the Rope - var subs: IndexedIterator[FlatString] - # Maximum position to iterate on (e.g. Rope.length) - var max: Int + var subs: IndexedIterator[FlatString] is noautoinit + # Maximum position to iterate on (e.g. Rope.bytelen) + var max: Int is noautoinit # Position (char) in the Rope (0-indexed) - var pos: Int - - init(root: Concat) is old_style_init do - subs = new RopeSubstrings(root) - pns = 0 - ns = subs.item.items - max = root.length - 1 - pos = 0 - end + var pos: Int is noautoinit init from(root: Concat, pos: Int) do subs = new RopeSubstrings.from(root, pos) pns = pos - subs.index self.pos = pos - ns = subs.item.items - max = root.length - 1 + ns = subs.item._items + max = root.bytelen - 1 end redef fun item do return ns[pns] @@ -672,11 +685,11 @@ private class RopeByteIterator redef fun next do pns += 1 pos += 1 - if pns < subs.item.bytelen then return + if pns < subs.item._bytelen then return if not subs.is_ok then return subs.next if not subs.is_ok then return - ns = subs.item.items + ns = subs.item._items pns = 0 end end @@ -687,21 +700,14 @@ private class RopeCharReverseIterator super IndexedIterator[Char] # Current NativeString - var ns: String + var ns: String is noautoinit # Current position in NativeString - var pns: Int + var pns: Int is noautoinit # Position in the Rope (0-indexed) - var pos: Int + var pos: Int is noautoinit # Iterator on the substrings, does the Postfix part of # the Rope traversal. - var subs: IndexedIterator[String] - - init(root: Concat) is old_style_init do - pos = root.length - 1 - subs = new ReverseRopeSubstrings(root) - ns = subs.item - pns = ns.length - 1 - end + var subs: IndexedIterator[String] is noautoinit init from(root: Concat, pos: Int) do self.pos = pos @@ -733,23 +739,15 @@ private class RopeCharIterator super IndexedIterator[Char] # Position in current `String` - var pns: Int + var pns: Int is noautoinit # Current `String` being iterated on - var str: String + var str: String is noautoinit # Substrings of the Rope - var subs: IndexedIterator[String] + var subs: IndexedIterator[String] is noautoinit # Maximum position to iterate on (e.g. Rope.length) - var max: Int + var max: Int is noautoinit # Position (char) in the Rope (0-indexed) - var pos: Int - - init(root: Concat) is old_style_init do - subs = new RopeSubstrings(root) - pns = 0 - str = subs.item - max = root.length - 1 - pos = 0 - end + var pos: Int is noautoinit init from(root: Concat, pos: Int) do subs = new RopeSubstrings.from(root, pos) @@ -789,35 +787,19 @@ private class ReverseRopeSubstrings # Current leaf var str: FlatString is noinit - init(root: Concat) is old_style_init do - var r = new RopeCharIteratorPiece(root, false, true, null) - pos = root.length - 1 - var lnod: String = root - loop - if lnod isa Concat then - lnod = lnod.right - r = new RopeCharIteratorPiece(lnod, false, true, r) - else - str = lnod.as(FlatString) - iter = r - break - end - end - end - init from(root: Concat, pos: Int) do var r = new RopeCharIteratorPiece(root, false, true, null) var rnod: String = root var off = pos loop if rnod isa Concat then - if off >= rnod.left.length then - off -= rnod.left.length - rnod = rnod.right + if off >= rnod._left.length then + off -= rnod._left.length + rnod = rnod._right r = new RopeCharIteratorPiece(rnod, false, true, r) else r.ldone = true - rnod = rnod.left + rnod = rnod._left r = new RopeCharIteratorPiece(rnod, false, true, r) end else @@ -839,7 +821,7 @@ private class ReverseRopeSubstrings redef fun next do if pos < 0 then return var curr = iter.prev - var currit = curr.node + var currit = curr.as(not null).node while curr != null do currit = curr.node if not currit isa Concat then @@ -850,12 +832,12 @@ private class ReverseRopeSubstrings end if not curr.rdone then curr.rdone = true - curr = new RopeCharIteratorPiece(currit.right, false, false, curr) + curr = new RopeCharIteratorPiece(currit._right, false, false, curr) continue end if not curr.ldone then curr.ldone = true - curr = new RopeCharIteratorPiece(currit.left, false, false, curr) + curr = new RopeCharIteratorPiece(currit._left, false, false, curr) continue end curr = curr.prev @@ -868,15 +850,15 @@ private class RopeBufSubstringIterator super Iterator[FlatText] # Iterator on the substrings of the building string - var iter: Iterator[FlatText] + var iter: Iterator[FlatText] is noautoinit # Makes a String out of the buffered part of the Ropebuffer - var nsstr: FlatString + var nsstr: FlatString is noautoinit # Did we attain the buffered part ? var nsstr_done = false - init(str: RopeBuffer) is old_style_init do + init from(str: RopeBuffer) do iter = str.str.substrings - nsstr = new FlatString.with_infos(str.ns, str.rpos - str.dumped, str.dumped, str.rpos - 1) + nsstr = new FlatString.with_infos(str.ns, str.rpos - str.dumped, str.dumped) if str.length == 0 then nsstr_done = true end @@ -911,24 +893,6 @@ private class RopeSubstrings # Current leaf var str: FlatString is noinit - init(root: Concat) is old_style_init do - var r = new RopeCharIteratorPiece(root, true, false, null) - pos = 0 - max = root.length - 1 - var rnod: String = root - loop - if rnod isa Concat then - rnod = rnod.left - r = new RopeCharIteratorPiece(rnod, true, false, r) - else - str = rnod.as(FlatString) - r.rdone = true - iter = r - break - end - end - end - init from(root: Concat, pos: Int) do var r = new RopeCharIteratorPiece(root, true, false, null) max = root.length - 1 @@ -936,13 +900,13 @@ private class RopeSubstrings var off = pos loop if rnod isa Concat then - if off >= rnod.left.length then + if off >= rnod._left.length then r.rdone = true - off -= rnod.left.length - rnod = rnod.right + off -= rnod._left.length + rnod = rnod._right r = new RopeCharIteratorPiece(rnod, true, false, r) else - rnod = rnod.left + rnod = rnod._left r = new RopeCharIteratorPiece(rnod, true, false, r) end else @@ -964,26 +928,26 @@ private class RopeSubstrings redef fun next do pos += str.length if pos > max then return - var it = iter.prev + var it = iter.prev.as(not null) var rnod = it.node loop if not rnod isa Concat then it.ldone = true it.rdone = true str = rnod.as(FlatString) - iter = it.as(not null) + iter = it break end if not it.ldone then - rnod = rnod.left + rnod = rnod._left it.ldone = true it = new RopeCharIteratorPiece(rnod, false, false, it) else if not it.rdone then it.rdone = true - rnod = rnod.right + rnod = rnod._right it = new RopeCharIteratorPiece(rnod, false, false, it) else - it = it.prev + it = it.prev.as(not null) rnod = it.node continue end @@ -1013,17 +977,45 @@ private class RopeBytes redef type SELFTYPE: Concat + var cache: FlatString is noinit + + var cache_start: Int = -1 + + var cache_end: Int = -1 + redef fun [](i) do - var nod: String = target + assert i >= 0 and i < target._bytelen + var flps = _cache_start + if i >= flps and i <= _cache_end then + return _cache.bytes[i - flps] + end + var lf = get_leaf_at(i) + return lf.bytes[i - _cache_start] + end + + fun get_leaf_at(pos: Int): FlatString do + var flps = _cache_start + if pos >= flps and pos <= _cache_end then + return _cache + end + var s: String = target + var st = pos loop - if nod isa FlatString then return nod.items[i] - if not nod isa Concat then abort - if nod.left.bytelen >= i then - nod = nod.right + if s isa FlatString then break + s = s.as(Concat) + var lft = s._left + var llen = lft.bytelen + if pos >= llen then + s = s._right + pos -= llen else - nod = nod.left + s = lft end end + _cache_start = st - pos + _cache_end = st - pos + s.bytelen - 1 + _cache = s + return s end redef fun iterator_from(i) do return new RopeByteIterator.from(target, i) @@ -1037,16 +1029,10 @@ class RopeBufferCharIterator super IndexedIterator[Char] # Subiterator. - var sit: IndexedIterator[Char] + var sit: IndexedIterator[Char] is noautoinit redef fun index do return sit.index - # Init the iterator from a RopeBuffer. - init(t: RopeBuffer) is old_style_init do - t.persist_buffer - sit = t.str.chars.iterator - end - # Init the iterator from a RopeBuffer starting from `pos`. init from(t: RopeBuffer, pos: Int) do t.persist_buffer @@ -1068,16 +1054,10 @@ class RopeBufferCharReverseIterator super IndexedIterator[Char] # Subiterator. - var sit: IndexedIterator[Char] + var sit: IndexedIterator[Char] is noautoinit redef fun index do return sit.index - # Init the iterator from a RopeBuffer. - init(tgt: RopeBuffer) is old_style_init do - tgt.persist_buffer - sit = tgt.str.chars.reverse_iterator - end - # Init the iterator from a RopeBuffer starting from `pos`. init from(tgt: RopeBuffer, pos: Int) do tgt.persist_buffer @@ -1118,32 +1098,23 @@ class RopeBufferByteIterator super IndexedIterator[Byte] # Subiterator. - var sit: IndexedIterator[Byte] + var sit: IndexedIterator[Byte] is noautoinit # Native string iterated over. - var ns: NativeString + var ns: NativeString is noautoinit # Current position in `ns`. - var pns: Int + var pns: Int is noautoinit # Maximum position iterable. - var maxpos: Int + var maxpos: Int is noautoinit - redef var index - - # Init the iterator from a RopeBuffer. - init(t: RopeBuffer) is old_style_init do - ns = t.ns - maxpos = t.bytelen - sit = t.str.bytes.iterator - pns = t.dumped - index = 0 - end + redef var index is noautoinit # Init the iterator from a RopeBuffer starting from `pos`. init from(t: RopeBuffer, pos: Int) do ns = t.ns - maxpos = t.bytelen + maxpos = t._bytelen sit = t.str.bytes.iterator_from(pos) pns = pos - t.str.length index = pos @@ -1171,23 +1142,15 @@ class RopeBufferByteReverseIterator super IndexedIterator[Byte] # Subiterator. - var sit: IndexedIterator[Byte] + var sit: IndexedIterator[Byte] is noautoinit # Native string iterated over. - var ns: NativeString + var ns: NativeString is noautoinit # Current position in `ns`. - var pns: Int - - redef var index + var pns: Int is noautoinit - # Init the iterator from a RopeBuffer. - init(tgt: RopeBuffer) is old_style_init do - sit = tgt.str.bytes.reverse_iterator - pns = tgt.rpos - 1 - index = tgt.bytelen - 1 - ns = tgt.ns - end + redef var index is noautoinit # Init the iterator from a RopeBuffer starting from `pos`. init from(tgt: RopeBuffer, pos: Int) do @@ -1206,7 +1169,7 @@ class RopeBufferByteReverseIterator redef fun next do index -= 1 - if pns > 0 then + if pns >= 0 then pns -= 1 else sit.next