[pypy-svn] r39705 - in pypy/branch/rope-branch/pypy: config objspace/std objspace/std/test
cfbolz at codespeak.net
cfbolz at codespeak.net
Fri Mar 2 16:24:31 CET 2007
Author: cfbolz
Date: Fri Mar 2 16:24:27 2007
New Revision: 39705
Added:
pypy/branch/rope-branch/pypy/objspace/std/rope.py
pypy/branch/rope-branch/pypy/objspace/std/ropeobject.py
pypy/branch/rope-branch/pypy/objspace/std/test/test_rope.py
pypy/branch/rope-branch/pypy/objspace/std/test/test_ropeobject.py
Modified:
pypy/branch/rope-branch/pypy/config/pypyoption.py
pypy/branch/rope-branch/pypy/objspace/std/marshal_impl.py
pypy/branch/rope-branch/pypy/objspace/std/model.py
pypy/branch/rope-branch/pypy/objspace/std/objspace.py
pypy/branch/rope-branch/pypy/objspace/std/stringtype.py
pypy/branch/rope-branch/pypy/objspace/std/unicodeobject.py
Log:
a first go at implementing ropes.
Modified: pypy/branch/rope-branch/pypy/config/pypyoption.py
==============================================================================
--- pypy/branch/rope-branch/pypy/config/pypyoption.py (original)
+++ pypy/branch/rope-branch/pypy/config/pypyoption.py Fri Mar 2 16:24:27 2007
@@ -123,6 +123,9 @@
BoolOption("withstrslice", "use strings optimized for slicing",
default=False),
+ BoolOption("withrope", "use ropes as the string implementation",
+ default=False),
+
BoolOption("withstrdict",
"use dictionaries optimized for string keys",
default=False),
Modified: pypy/branch/rope-branch/pypy/objspace/std/marshal_impl.py
==============================================================================
--- pypy/branch/rope-branch/pypy/objspace/std/marshal_impl.py (original)
+++ pypy/branch/rope-branch/pypy/objspace/std/marshal_impl.py Fri Mar 2 16:24:27 2007
@@ -303,11 +303,11 @@
m.atom_str(TYPE_STRING, s)
def unmarshal_String(space, u, tc):
- return W_StringObject(u.get_str())
+ return space.wrap(u.get_str())
register(TYPE_STRING, unmarshal_String)
def unmarshal_interned(space, u, tc):
- w_ret = W_StringObject(u.get_str())
+ w_ret = space.wrap(u.get_str())
u.stringtable_w.append(w_ret)
w_intern = space.builtin.get('intern')
space.call_function(w_intern, w_ret)
@@ -495,7 +495,7 @@
string_to_buffer = app.interphook('string_to_buffer')
def unmarshal_buffer(space, u, tc):
- w_s = W_StringObject(u.get_str())
+ w_s = space.wrap(u.get_str())
return string_to_buffer(space, w_s)
register(TYPE_UNKNOWN, unmarshal_buffer)
Modified: pypy/branch/rope-branch/pypy/objspace/std/model.py
==============================================================================
--- pypy/branch/rope-branch/pypy/objspace/std/model.py (original)
+++ pypy/branch/rope-branch/pypy/objspace/std/model.py Fri Mar 2 16:24:27 2007
@@ -17,6 +17,8 @@
"withmultidict" : ["dictmultiobject.W_DictMultiObject",
"dictmultiobject.W_DictMultiIterObject"],
"withmultilist" : ["listmultiobject.W_ListMultiObject"],
+ "withrope" : ["ropeobject.W_RopeObject",
+ "ropeobject.W_RopeIterObject"],
"withrangelist" : ["rangeobject.W_RangeListObject",
"rangeobject.W_RangeIterObject"],
"withtproxy" : ["proxyobject.W_TransparentList",
@@ -68,6 +70,7 @@
from pypy.objspace.std import dictmultiobject
from pypy.objspace.std import listmultiobject
from pypy.objspace.std import stringobject
+ from pypy.objspace.std import ropeobject
from pypy.objspace.std import strsliceobject
from pypy.objspace.std import strjoinobject
from pypy.objspace.std import typeobject
@@ -115,6 +118,7 @@
dictobject.W_DictObject: True,
dictobject.W_DictIterObject: True,
listobject.W_ListObject: True,
+ stringobject.W_StringObject: True,
}
for option, value in config.objspace.std:
if option.startswith("with") and option in option_to_typename:
@@ -132,6 +136,8 @@
if config.objspace.std.withmultilist:
del self.typeorder[listobject.W_ListObject]
+ if config.objspace.std.withrope:
+ del self.typeorder[stringobject.W_StringObject]
#check if we missed implementations
from pypy.objspace.std.objspace import _registered_implementations
@@ -179,9 +185,14 @@
(complexobject.W_ComplexObject,
complexobject.delegate_Float2Complex),
]
- self.typeorder[stringobject.W_StringObject] += [
- (unicodeobject.W_UnicodeObject, unicodeobject.delegate_String2Unicode),
- ]
+ if not config.objspace.std.withrope:
+ self.typeorder[stringobject.W_StringObject] += [
+ (unicodeobject.W_UnicodeObject, unicodeobject.delegate_String2Unicode),
+ ]
+ else:
+ self.typeorder[ropeobject.W_RopeObject] += [
+ (unicodeobject.W_UnicodeObject, unicodeobject.delegate_String2Unicode),
+ ]
if config.objspace.std.withstrslice:
self.typeorder[strsliceobject.W_StringSliceObject] += [
Modified: pypy/branch/rope-branch/pypy/objspace/std/objspace.py
==============================================================================
--- pypy/branch/rope-branch/pypy/objspace/std/objspace.py (original)
+++ pypy/branch/rope-branch/pypy/objspace/std/objspace.py Fri Mar 2 16:24:27 2007
@@ -335,6 +335,9 @@
else:
return self.newint(x)
if isinstance(x, str):
+ if self.config.objspace.std.withrope:
+ from pypy.objspace.std.ropeobject import rope, W_RopeObject
+ return W_RopeObject(rope.LiteralStringNode(x))
return W_StringObject(x)
if isinstance(x, unicode):
return W_UnicodeObject([unichr(ord(u)) for u in x]) # xxx
@@ -468,7 +471,11 @@
except ValueError: # chr(out-of-range)
raise OperationError(self.w_ValueError,
self.wrap("character code not in range(256)"))
- return W_StringObject(''.join(chars))
+ if self.config.objspace.std.withrope:
+ from pypy.objspace.std.ropeobject import W_RopeObject, rope
+ return W_RopeObject(rope.rope_from_charlist(chars))
+ else:
+ return W_StringObject(''.join(chars))
def newunicode(self, chars):
try:
Added: pypy/branch/rope-branch/pypy/objspace/std/rope.py
==============================================================================
--- (empty file)
+++ pypy/branch/rope-branch/pypy/objspace/std/rope.py Fri Mar 2 16:24:27 2007
@@ -0,0 +1,782 @@
+import py
+import sys
+
+NEW_NODE_WHEN_LENGTH = 16
+MAX_DEPTH = 32 # maybe should be smaller
+MIN_SLICE_LENGTH = 64
+CONCATENATE_WHEN_MULTIPLYING = 128
+
+def find_fib_index(l):
+ if l == 0:
+ return -1
+ a, b = 1, 2
+ i = 0
+ while 1:
+ if a <= l < b:
+ return i
+ a, b = b, a + b
+ i += 1
+
+class StringNode(object):
+ def length(self):
+ return 0
+
+ def depth(self):
+ return 0
+
+ def rebalance(self):
+ return self
+
+ def flatten(self):
+ return ''
+
+ def __add__(self, other):
+ return concatenate(self, other)
+
+ def __getitem__(self, index):
+ if isinstance(index, slice):
+ start, stop, step = index.indices(self.length())
+ # XXX sucks
+ slicelength = len(range(start, stop, step))
+ return getslice(self, start, stop, step, slicelength)
+ return self.getitem(index)
+
+ def getitem(self, index):
+ raise NotImplementedError("abstract base class")
+
+ def getitem_slice(self, start, stop):
+ # XXX really horrible, in most cases
+ result = []
+ for i in range(start, stop):
+ result.append(self.getitem(i))
+ return rope_from_charlist(result)
+
+ def view(self):
+ from pypy.translator.tool.pygame import graphclient
+ view([self])
+
+ def check_balanced(self):
+ return True
+
+
+class LiteralStringNode(StringNode):
+ def __init__(self, s):
+ self.s = s
+
+ def length(self):
+ return len(self.s)
+
+ def flatten(self):
+ return self.s
+
+ def getitem(self, index):
+ return self.s[index]
+
+ def getitem_slice(self, start, stop):
+ return LiteralStringNode(self.s[start:stop])
+
+ def dot(self, seen, toplevel=False):
+ if self in seen:
+ return
+ seen[self] = True
+ addinfo = str(self.s).replace('"', "'") or "_"
+ if len(addinfo) > 10:
+ addinfo = addinfo[:3] + "..." + addinfo[-3:]
+ yield ('"%s" [shape=box,label="length: %s\\n%s"];' % (
+ id(self), len(self.s),
+ repr(addinfo).replace('"', '').replace("\\", "\\\\")))
+
+
+class BinaryConcatNode(StringNode):
+ def __init__(self, left, right):
+ self.left = left
+ self.right = right
+ self.len = left.length() + right.length()
+ self._depth = max(left.depth(), right.depth()) + 1
+ self.balanced = False
+
+ def check_balanced(self):
+ if self.balanced:
+ return True
+ if not self.left.check_balanced() or not self.right.check_balanced():
+ return False
+ left = self.left
+ right = self.right
+ llen = left.length()
+ rlen = right.length()
+ ldepth = left.depth()
+ rdepth = right.depth()
+ balanced = (find_fib_index(self.len // (NEW_NODE_WHEN_LENGTH / 2)) >=
+ self._depth)
+ self.balanced = balanced
+ return balanced
+
+ def length(self):
+ return self.len
+
+ def depth(self):
+ return self._depth
+
+ def getitem(self, index):
+ llen = self.left.length()
+ if index >= llen:
+ return self.right.getitem(index - llen)
+ else:
+ return self.left.getitem(index)
+
+ def flatten(self):
+ f = fringe(self)
+ return "".join([node.flatten() for node in f])
+
+ def rebalance(self):
+ return rebalance([self], self.len)
+
+ def dot(self, seen, toplevel=False):
+ if self in seen:
+ return
+ seen[self] = True
+ if toplevel:
+ addition = ", fillcolor=red"
+ elif self.check_balanced():
+ addition = ", fillcolor=yellow"
+ else:
+ addition = ""
+ yield '"%s" [shape=octagon,label="+\\ndepth=%s, length=%s"%s];' % (
+ id(self), self._depth, self.len, addition)
+ for child in [self.left, self.right]:
+ yield '"%s" -> "%s";' % (id(self), id(child))
+ for line in child.dot(seen):
+ yield line
+
+class SliceNode(StringNode):
+ def __init__(self, start, stop, node):
+ self.start = start
+ self.stop = stop
+ self.node = node
+
+ def length(self):
+ return self.stop - self.start
+
+ def getitem_slice(self, start, stop):
+ return self.node.getitem_slice(self.start + start, self.start + stop)
+
+ def getitem(self, index):
+ return self.node.getitem(self.start + index)
+
+ def flatten(self):
+ return self.node.flatten()[self.start: self.stop]
+
+ def dot(self, seen, toplevel=False):
+ if self in seen:
+ return
+ seen[self] = True
+ yield '"%s" [shape=octagon,label="slice\\nstart=%s, stop=%s"];' % (
+ id(self), self.start, self.stop)
+ yield '"%s" -> "%s";' % (id(self), id(self.node))
+ for line in self.node.dot(seen):
+ yield line
+
+def concatenate(node1, node2):
+ if node1.length() == 0:
+ return node2
+ if node2.length() == 0:
+ return node1
+ if (isinstance(node2, LiteralStringNode) and
+ len(node2.s) <= NEW_NODE_WHEN_LENGTH):
+ if isinstance(node1, LiteralStringNode):
+ if len(node1.s) + len(node2.s) <= NEW_NODE_WHEN_LENGTH:
+ return LiteralStringNode(node1.s + node2.s)
+ elif isinstance(node1, BinaryConcatNode):
+ r = node1.right
+ if isinstance(r, LiteralStringNode):
+ if len(r.s) + len(node2.s) <= NEW_NODE_WHEN_LENGTH:
+ return BinaryConcatNode(node1.left,
+ LiteralStringNode(r.s + node2.s))
+ result = BinaryConcatNode(node1, node2)
+ if result.depth() > MAX_DEPTH: #XXX better check
+ return result.rebalance()
+ return result
+
+def getslice(node, start, stop, step, slicelength):
+ start, stop, node = find_straddling(node, start, stop)
+ if step != 1:
+ # XXX optimize later using SeekableCharIterator
+ iter = SeekableCharIterator(node)
+ iter.seekforward(start)
+ result = [iter.next()]
+ for i in range(slicelength - 1):
+ iter.seekforward(step - 1)
+ result.append(iter.next())
+ return rope_from_charlist(result)
+ return getslice_one(node, start, stop)
+
+def getslice_one(node, start, stop):
+ if isinstance(node, BinaryConcatNode):
+ if start == 0:
+ if stop == node.length():
+ return node
+ return getslice_left(node, stop)
+ if stop == node.length():
+ return getslice_right(node, start)
+ return concatenate(
+ getslice_right(node.left, start),
+ getslice_left(node.right, stop - node.left.length()))
+ else:
+ return getslice_primitive(node, start, stop)
+
+def find_straddling(node, start, stop):
+ while 1:
+ if isinstance(node, BinaryConcatNode):
+ llen = node.left.length()
+ if start >= llen:
+ node = node.right
+ start = start - llen
+ stop = stop - llen
+ continue
+ if stop <= llen:
+ node = node.left
+ continue
+ return start, stop, node
+
+def getslice_right(node, start):
+ while 1:
+ if start == 0:
+ return node
+ if isinstance(node, BinaryConcatNode):
+ llen = node.left.length()
+ if start >= llen:
+ node = node.right
+ start = start - llen
+ continue
+ else:
+ return concatenate(getslice_right(node.left, start),
+ node.right)
+ return getslice_primitive(node, start, node.length())
+
+def getslice_left(node, stop):
+ while 1:
+ if stop == node.length():
+ return node
+ if isinstance(node, BinaryConcatNode):
+ llen = node.left.length()
+ if stop <= llen:
+ node = node.left
+ continue
+ else:
+ return concatenate(node.left,
+ getslice_left(node.right, stop - llen))
+ return getslice_primitive(node, 0, stop)
+
+
+def getslice_primitive(node, start, stop):
+ if stop - start >= MIN_SLICE_LENGTH:
+ if isinstance(node, SliceNode):
+ return SliceNode(start + node.start, stop + node.start,
+ node.node)
+ return SliceNode(start, stop, node)
+ return node.getitem_slice(start, stop)
+
+def multiply(node, times):
+ if times <= 0:
+ return LiteralStringNode("")
+ if times == 1:
+ return node
+ end_length = node.length() * times
+ num_bits = 0
+ mask = times
+ while mask:
+ num_bits += 1
+ mask >>= 1
+ result = node
+ mask = 1 << (num_bits - 2)
+ #import pdb; pdb.set_trace()
+ for i in range(num_bits - 1):
+ if mask & times:
+ if result.length() < CONCATENATE_WHEN_MULTIPLYING:
+ result = concatenate(result, result)
+ result = concatenate(result, node)
+ else:
+ result = BinaryConcatNode(result, result)
+ result = BinaryConcatNode(result, node)
+ else:
+ if result.length() < CONCATENATE_WHEN_MULTIPLYING:
+ result = concatenate(result, result)
+ else:
+ result = BinaryConcatNode(result, result)
+ mask >>= 1
+ return result
+
+def join(node, l):
+ if node.length() == 0:
+ return rebalance(l)
+ nodelist = [None] * (2 * len(l) - 1)
+ length = 0
+ for i in range(len(l)):
+ nodelist[2 * i] = l[i]
+ length += l[i].length()
+ for i in range(len(l) - 1):
+ nodelist[2 * i + 1] = node
+ length += (len(l) - 1) * node.length()
+ return rebalance(nodelist, length)
+
+def rebalance(nodelist, sizehint=-1):
+ if not nodelist:
+ return LiteralStringNode("")
+ nodelist.reverse()
+ if sizehint < 0:
+ sizehint = 0
+ for node in nodelist:
+ sizehint += node.length()
+ l = [None] * (find_fib_index(sizehint) + 2)
+ stack = nodelist
+ i = 0
+ curr = None
+ while stack:
+ curr = stack.pop()
+ while 1:
+ if isinstance(curr, BinaryConcatNode) and not curr.balanced:
+ stack.append(curr.right)
+ curr = curr.left
+ else:
+ i = orig_i = find_fib_index(curr.length())
+ index = 0
+ added = False
+ while index <= i:
+ if l[index] is not None:
+ curr = concatenate(l[index], curr)
+ l[index] = None
+ if index >= orig_i or not added:
+ i += 1
+ added = True
+ index += 1
+ if i == len(l):
+ return curr
+ l[i] = curr
+ break
+ for index in range(i + 1, len(l)):
+ if l[index] is not None:
+ curr = BinaryConcatNode(l[index], curr)
+ assert curr is not None
+ curr.check_balanced()
+ return curr
+
+# __________________________________________________________________________
+# construction from normal strings
+
+def rope_from_charlist(charlist):
+ nodelist = []
+ size = 0
+ for i in range(0, len(charlist), NEW_NODE_WHEN_LENGTH):
+ chars = charlist[i: min(len(charlist), i + NEW_NODE_WHEN_LENGTH)]
+ nodelist.append(LiteralStringNode("".join(chars)))
+ size += len(chars)
+ return rebalance(nodelist, size)
+
+# __________________________________________________________________________
+# searching
+
+def find_char(node, c, start=0, stop=-1):
+ offset = 0
+ length = node.length()
+ if stop == -1:
+ stop = length
+ if start != 0 or stop != length:
+ newstart, newstop, node = find_straddling(node, start, stop)
+ offset = start - newstart
+ start = newstart
+ stop = newstop
+ if isinstance(node, LiteralStringNode):
+ result = node.s.find(c, start, stop)
+ if result == -1:
+ return -1
+ return result + offset
+ elif isinstance(node, SliceNode):
+ return find_char(node.node, c, node.start + start,
+ node.start + stop) - node.start + offset
+ iter = CharIterator(node)
+ i = 0
+ while i < stop:
+ try:
+ c2 = iter.next()
+ if i < start:
+ i += 1
+ continue
+ if c == c2:
+ return i + offset
+ i += 1
+ except StopIteration:
+ return -1
+ return -1
+
+def find(node, subnode, start=0, stop=-1):
+
+ len1 = node.length()
+ if stop > len1 or stop == -1:
+ stop = len1
+ substring = subnode.flatten() # stressful to do it as a node
+ len2 = len(substring)
+ if len2 == 1:
+ return find_char(node, substring[0], start, stop)
+ if len2 == 0:
+ if (stop - start) < 0:
+ return -1
+ return start
+ restart = construct_restart_positions(substring)
+ return _find(node, substring, start, stop, restart)
+
+def _find(node, substring, start, stop, restart):
+ len2 = len(substring)
+ i = 0
+ m = start
+ iter = SeekableCharIterator(node)
+ iter.seekforward(start)
+ c = iter.next()
+ while m + i < stop:
+ if c == substring[i]:
+ i += 1
+ if i == len2:
+ return m
+ if m + i < stop:
+ c = iter.next()
+ else:
+ # mismatch, go back to the last possible starting pos
+ if i==0:
+ m += 1
+ if m + i < stop:
+ c = iter.next()
+ else:
+ e = restart[i-1]
+ new_m = m + i - e
+ assert new_m <= m + i
+ seek = m + i - new_m
+ if seek:
+ iter.seekback(m + i - new_m)
+ c = iter.next()
+ m = new_m
+ i = e
+ return -1
+
+def construct_restart_positions(s):
+ l = len(s)
+ restart = [0] * l
+ restart[0] = 0
+ i = 1
+ j = 0
+ while i < l:
+ if s[i] == s[j]:
+ j += 1
+ restart[i] = j
+ i += 1
+ elif j>0:
+ j = restart[j-1]
+ else:
+ restart[i] = 0
+ i += 1
+ j = 0
+ return restart
+
+def construct_restart_positions_node(node):
+ # really a bit overkill
+ l = node.length()
+ restart = [0] * l
+ restart[0] = 0
+ i = 1
+ j = 0
+ iter1 = CharIterator(node)
+ iter1.next()
+ c1 = iter1.next()
+ iter2 = SeekableCharIterator(node)
+ c2 = iter2.next()
+ while i < l:
+ if c1 == c2:
+ j += 1
+ if j != l:
+ c2 = iter2.next()
+ restart[i] = j
+ i += 1
+ if i != l:
+ c1 = iter1.next()
+ else:
+ break
+ elif j>0:
+ new_j = restart[j-1]
+ assert new_j < j
+ iter2.seekback(j - new_j)
+ c2 = iter2.next()
+ j = new_j
+ else:
+ restart[i] = 0
+ i += 1
+ if i != l:
+ c1 = iter1.next()
+ else:
+ break
+ j = 0
+ iter2 = SeekableCharIterator(node)
+ c2 = iter2.next()
+ return restart
+
+def view(objs):
+ from pypy.translator.tool.pygame import graphclient
+ content = ["digraph G{"]
+ seen = {}
+ for i, obj in enumerate(objs):
+ if obj is None:
+ content.append(str(i) + ";")
+ else:
+ content.extend(obj.dot(seen, toplevel=True))
+ content.append("}")
+ p = py.test.ensuretemp("automaton").join("temp.dot")
+ p.write("\n".join(content))
+ graphclient.display_dot_file(str(p))
+
+
+# __________________________________________________________________________
+# iteration
+
+class FringeIterator(object):
+ def __init__(self, node):
+ self.stack = [node]
+
+ def next(self):
+ while self.stack:
+ curr = self.stack.pop()
+ while 1:
+ if isinstance(curr, BinaryConcatNode):
+ self.stack.append(curr.right)
+ curr = curr.left
+ else:
+ return curr
+ raise StopIteration
+
+def fringe(node):
+ result = []
+ iter = FringeIterator(node)
+ while 1:
+ try:
+ result.append(iter.next())
+ except StopIteration:
+ return result
+
+class SeekableFringeIterator(object):
+ def __init__(self, node):
+ self.stack = [node]
+ self.fringestack = []
+ self.fringe = []
+
+ def next(self):
+ if self.fringestack:
+ result = self.fringestack.pop()
+ self.fringe.append(result)
+ return result
+ while self.stack:
+ curr = self.stack.pop()
+ while 1:
+ if isinstance(curr, BinaryConcatNode):
+ self.stack.append(curr.right)
+ curr = curr.left
+ else:
+ self.fringe.append(curr)
+ return curr
+ raise StopIteration
+
+ def seekback(self):
+ result = self.fringe.pop()
+ self.fringestack.append(result)
+ return result
+
+
+class CharIterator(object):
+ def __init__(self, node):
+ self.iter = FringeIterator(node)
+ self.node = None
+ self.nodelength = 0
+ self.index = 0
+
+ def next(self):
+ node = self.node
+ if node is None:
+ while 1:
+ node = self.node = self.iter.next()
+ nodelength = self.nodelength = node.length()
+ if nodelength != 0:
+ break
+ self.index = 0
+ index = self.index
+ result = self.node.getitem(index)
+ if self.index == self.nodelength - 1:
+ self.node = None
+ else:
+ self.index = index + 1
+ return result
+
+class SeekableCharIterator(object):
+ def __init__(self, node):
+ self.iter = SeekableFringeIterator(node)
+ self.node = self.nextnode()
+ self.nodelength = self.node.length()
+ self.index = 0
+
+ def nextnode(self):
+ while 1:
+ node = self.node = self.iter.next()
+ nodelength = self.nodelength = node.length()
+ if nodelength != 0:
+ break
+ self.index = 0
+ return node
+
+ def next(self):
+ node = self.node
+ if node is None:
+ node = self.nextnode()
+ index = self.index
+ result = self.node.getitem(index)
+ if self.index == self.nodelength - 1:
+ self.node = None
+ self.index = index + 1
+ return result
+
+ def seekforward(self, numchars):
+ if numchars < (self.nodelength - self.index):
+ self.index += numchars
+ return
+ numchars -= self.nodelength - self.index
+ while 1:
+ node = self.iter.next()
+ length = node.length()
+ if length <= numchars:
+ numchars -= length
+ else:
+ self.index = numchars
+ self.node = node
+ self.nodelength = node.length()
+ return
+
+ def seekback(self, numchars):
+ if numchars <= self.index:
+ self.index -= numchars
+ return
+ numchars -= self.index
+ self.iter.seekback() # for first item
+ while 1:
+ node = self.iter.seekback()
+ length = node.length()
+ if length < numchars:
+ numchars -= length
+ else:
+ self.index = length - numchars
+ self.node = self.iter.next()
+ self.nodelength = self.node.length()
+ return
+
+class FindIterator(object):
+ def __init__(self, node, sub, start=0, stop=-1):
+ self.node = node
+ len1 = self.length = node.length()
+ substring = self.substring = sub.flatten() # for now
+ len2 = len(substring)
+ self.search_length = len2
+ if len2 == 0:
+ self.restart_positions = None
+ elif len2 == 1:
+ self.restart_positions = None
+ else:
+ self.restart_positions = construct_restart_positions(substring)
+ self.start = start
+ if stop == -1 or stop > len1:
+ stop = len1
+ self.stop = stop
+
+ def next(self):
+ if self.search_length == 0:
+ if (self.stop - self.start) < 0:
+ raise StopIteration
+ start = self.start
+ self.start += 1
+ return start
+ elif self.search_length == 1:
+ result = find_char(self.node, self.substring[0],
+ self.start, self.stop)
+ if result == -1:
+ self.start = self.length
+ raise StopIteration
+ self.start = result + 1
+ return result
+ if self.start >= self.stop:
+ raise StopIteration
+ result = _find(self.node, self.substring, self.start,
+ self.stop, self.restart_positions)
+ if result == -1:
+ self.start = self.length
+ raise StopIteration
+ self.start = result + self.search_length
+ return result
+
+# __________________________________________________________________________
+# comparison
+
+
+def eq(node1, node2):
+ if node1 is node2:
+ return True
+ # could be cleverer and detect partial equalities
+ if node1.length() != node2.length():
+ return False
+ iter1 = CharIterator(node1)
+ iter2 = CharIterator(node2)
+ while 1:
+ try:
+ c = iter1.next()
+ except StopIteration:
+ return True
+ if c != iter2.next():
+ return False
+
+def compare(node1, node2):
+ len1 = node1.length()
+ len2 = node2.length()
+ if not len1:
+ if not len2:
+ return 0
+ return -1
+ if not len2:
+ return 1
+
+ if len1 < len2:
+ cmplen = len1
+ else:
+ cmplen = len2
+ i = 0
+ iter1 = CharIterator(node1)
+ iter2 = CharIterator(node2)
+ while i < cmplen:
+ diff = ord(iter1.next()) - ord(iter2.next())
+ if diff != 0:
+ return diff
+ i += 1
+ return len1 - len2
+
+
+# __________________________________________________________________________
+# misc
+
+
+def hash_rope(rope):
+ from pypy.rlib.rarithmetic import intmask
+ length = rope.length()
+ if length == 0:
+ x = -1
+ else:
+ x = ord(rope.getitem(0)) << 7
+ iter = CharIterator(rope)
+ while 1:
+ try:
+ x = (1000003*x) ^ ord(iter.next())
+ except StopIteration:
+ break
+ x ^= length
+ if x == 0:
+ x = -1
+ return intmask(x)
+
Added: pypy/branch/rope-branch/pypy/objspace/std/ropeobject.py
==============================================================================
--- (empty file)
+++ pypy/branch/rope-branch/pypy/objspace/std/ropeobject.py Fri Mar 2 16:24:27 2007
@@ -0,0 +1,1034 @@
+from pypy.objspace.std.objspace import *
+from pypy.interpreter import gateway
+from pypy.rlib.objectmodel import we_are_translated
+from pypy.objspace.std.inttype import wrapint
+from pypy.objspace.std.sliceobject import W_SliceObject
+from pypy.objspace.std import slicetype
+from pypy.objspace.std.listobject import W_ListObject
+from pypy.objspace.std.noneobject import W_NoneObject
+from pypy.objspace.std.tupleobject import W_TupleObject
+from pypy.rlib.rarithmetic import ovfcheck
+
+from pypy.objspace.std import rope
+
+class W_RopeObject(W_Object):
+ from pypy.objspace.std.stringtype import str_typedef as typedef
+
+ def __init__(w_self, node):
+ w_self._node = node
+
+ def __repr__(w_self):
+ """ representation for debugging purposes """
+ return "%s(%r)" % (w_self.__class__.__name__, w_self._node)
+
+ def unwrap(w_self, space):
+ return w_self._node.flatten()
+
+ def create_if_subclassed(w_self):
+ if type(w_self) == W_RopeObject:
+ return w_self
+ return W_RopeObject(w_self._node)
+
+W_RopeObject.empty = W_RopeObject(rope.LiteralStringNode(""))
+
+registerimplementation(W_RopeObject)
+
+class W_RopeIterObject(W_Object):
+ from pypy.objspace.std.itertype import iter_typedef as typedef
+
+ def __init__(w_self, w_rope, index=0):
+ w_self.node = node = w_rope._node
+ w_self.char_iter = rope.CharIterator(node)
+ w_self.index = index
+
+registerimplementation(W_RopeIterObject)
+
+def wrap_rpystr(s):
+ return W_RopeObject(rope.LiteralStringNode(s))
+
+def _is_generic(space, w_self, fun):
+ l = w_self._node.length()
+ if l == 0:
+ return space.w_False
+ iter = rope.CharIterator(w_self._node)
+ for i in range(l):
+ if not fun(iter.next()):
+ return space.w_False
+ return space.w_True
+_is_generic._annspecialcase_ = "specialize:arg(2)"
+
+def _upper(ch):
+ if ch.islower():
+ o = ord(ch) - 32
+ return chr(o)
+ else:
+ return ch
+
+def _lower(ch):
+ if ch.isupper():
+ o = ord(ch) + 32
+ return chr(o)
+ else:
+ return ch
+
+_isspace = lambda c: c.isspace()
+_isdigit = lambda c: c.isdigit()
+_isalpha = lambda c: c.isalpha()
+_isalnum = lambda c: c.isalnum()
+
+def str_isspace__Rope(space, w_self):
+ return _is_generic(space, w_self, _isspace)
+
+def str_isdigit__Rope(space, w_self):
+ return _is_generic(space, w_self, _isdigit)
+
+def str_isalpha__Rope(space, w_self):
+ return _is_generic(space, w_self, _isalpha)
+
+def str_isalnum__Rope(space, w_self):
+ return _is_generic(space, w_self, _isalnum)
+
+def str_isupper__Rope(space, w_self):
+ """Return True if all cased characters in S are uppercase and there is
+at least one cased character in S, False otherwise."""
+ l = w_self._node.length()
+
+ if l == 0:
+ return space.w_False
+ cased = False
+ iter = rope.CharIterator(w_self._node)
+ for idx in range(l):
+ c = iter.next()
+ if c.islower():
+ return space.w_False
+ elif not cased and c.isupper():
+ cased = True
+ return space.newbool(cased)
+
+def str_islower__Rope(space, w_self):
+ """Return True if all cased characters in S are lowercase and there is
+at least one cased character in S, False otherwise."""
+ l = w_self._node.length()
+
+ if l == 0:
+ return space.w_False
+ cased = False
+ iter = rope.CharIterator(w_self._node)
+ for idx in range(l):
+ c = iter.next()
+ if c.isupper():
+ return space.w_False
+ elif not cased and c.islower():
+ cased = True
+ return space.newbool(cased)
+
+def str_istitle__Rope(space, w_self):
+ """Return True if S is a titlecased string and there is at least one
+character in S, i.e. uppercase characters may only follow uncased
+characters and lowercase characters only cased ones. Return False
+otherwise."""
+ cased = False
+ previous_is_cased = False
+
+ iter = rope.CharIterator(w_self._node)
+ for pos in range(0, w_self._node.length()):
+ ch = iter.next()
+ if ch.isupper():
+ if previous_is_cased:
+ return space.w_False
+ previous_is_cased = True
+ cased = True
+ elif ch.islower():
+ if not previous_is_cased:
+ return space.w_False
+ cased = True
+ else:
+ previous_is_cased = False
+
+ return space.newbool(cased)
+
+def str_upper__Rope(space, w_self):
+ l = w_self._node.length()
+ res = [' '] * l
+ iter = rope.CharIterator(w_self._node)
+ for i in range(l):
+ ch = iter.next()
+ res[i] = _upper(ch)
+
+ return W_RopeObject(rope.rope_from_charlist(res))
+
+def str_lower__Rope(space, w_self):
+ l = w_self._node.length()
+ res = [' '] * l
+ iter = rope.CharIterator(w_self._node)
+ for i in range(l):
+ ch = iter.next()
+ res[i] = _lower(ch)
+
+ return W_RopeObject(rope.rope_from_charlist(res))
+
+def str_swapcase__Rope(space, w_self):
+ l = w_self._node.length()
+ res = [' '] * l
+ iter = rope.CharIterator(w_self._node)
+ for i in range(l):
+ ch = iter.next()
+ if ch.isupper():
+ o = ord(ch) + 32
+ res[i] = chr(o)
+ elif ch.islower():
+ o = ord(ch) - 32
+ res[i] = chr(o)
+ else:
+ res[i] = ch
+
+ return W_RopeObject(rope.rope_from_charlist(res))
+
+
+def str_capitalize__Rope(space, w_self):
+ node = w_self._node
+ length = node.length()
+ buffer = [' '] * length
+ if length > 0:
+ iter = rope.CharIterator(node)
+ ch = iter.next()
+ if ch.islower():
+ o = ord(ch) - 32
+ buffer[0] = chr(o)
+ else:
+ buffer[0] = ch
+
+ for i in range(1, length):
+ ch = iter.next()
+ if ch.isupper():
+ o = ord(ch) + 32
+ buffer[i] = chr(o)
+ else:
+ buffer[i] = ch
+ else:
+ return W_RopeObject.empty
+
+ return W_RopeObject(rope.rope_from_charlist(buffer))
+
+def str_title__Rope(space, w_self):
+ node = w_self._node
+ length = node.length()
+ buffer = [' '] * length
+ prev_letter = ' '
+
+ iter = rope.CharIterator(node)
+ for pos in range(0, length):
+ ch = iter.next()
+ if not prev_letter.isalpha():
+ buffer[pos] = _upper(ch)
+ else:
+ buffer[pos] = _lower(ch)
+
+ prev_letter = buffer[pos]
+
+ return W_RopeObject(rope.rope_from_charlist(buffer))
+
+def str_split__Rope_None_ANY(space, w_self, w_none, w_maxsplit=-1):
+ maxsplit = space.int_w(w_maxsplit)
+ res_w = []
+ node = w_self._node
+ length = node.length()
+ i = 0
+ iter = rope.CharIterator(node)
+ while True:
+ # find the beginning of the next word
+ while i < length:
+ if not iter.next().isspace():
+ break # found
+ i += 1
+ else:
+ break # end of string, finished
+
+ # find the end of the word
+ if maxsplit == 0:
+ j = length # take all the rest of the string
+ else:
+ j = i + 1
+ while j < length and not iter.next().isspace():
+ j += 1
+ maxsplit -= 1 # NB. if it's already < 0, it stays < 0
+
+ # the word is value[i:j]
+ res_w.append(W_RopeObject(rope.getslice_one(node, i, j)))
+
+ # continue to look from the character following the space after the word
+ i = j + 1
+
+ return space.newlist(res_w)
+
+
+def str_split__Rope_Rope_ANY(space, w_self, w_by, w_maxsplit=-1):
+ maxsplit = space.int_w(w_maxsplit)
+ res_w = []
+ start = 0
+ selfnode = w_self._node
+ bynode = w_by._node
+ iter = rope.FindIterator(selfnode, bynode)
+ bylen = bynode.length()
+ if bylen == 0:
+ raise OperationError(space.w_ValueError, space.wrap("empty separator"))
+
+ while maxsplit != 0:
+ try:
+ next = iter.next()
+ except StopIteration:
+ break
+ res_w.append(W_RopeObject(rope.getslice_one(selfnode, start, next)))
+ start = next + bylen
+ maxsplit -= 1 # NB. if it's already < 0, it stays < 0
+
+ res_w.append(W_RopeObject(rope.getslice_one(
+ selfnode, start, selfnode.length())))
+ return space.newlist(res_w)
+
+def str_rsplit__Rope_None_ANY(space, w_self, w_none, w_maxsplit=-1):
+ # XXX works but flattens
+ maxsplit = space.int_w(w_maxsplit)
+ res_w = []
+ value = w_self._node.flatten()
+ i = len(value)-1
+ while True:
+ # starting from the end, find the end of the next word
+ while i >= 0:
+ if not value[i].isspace():
+ break # found
+ i -= 1
+ else:
+ break # end of string, finished
+
+ # find the start of the word
+ # (more precisely, 'j' will be the space character before the word)
+ if maxsplit == 0:
+ j = -1 # take all the rest of the string
+ else:
+ j = i - 1
+ while j >= 0 and not value[j].isspace():
+ j -= 1
+ maxsplit -= 1 # NB. if it's already < 0, it stays < 0
+
+ # the word is value[j+1:i+1]
+ j1 = j + 1
+ assert j1 >= 0
+ res_w.append(wrap_rpystr(value[j1:i+1]))
+
+ # continue to look from the character before the space before the word
+ i = j - 1
+
+ res_w.reverse()
+ return space.newlist(res_w)
+
+def str_rsplit__Rope_Rope_ANY(space, w_self, w_by, w_maxsplit=-1):
+ # XXX works but flattens
+ maxsplit = space.int_w(w_maxsplit)
+ res_w = []
+ value = w_self._node.flatten()
+ end = len(value)
+ by = w_by._node.flatten()
+ bylen = len(by)
+ if bylen == 0:
+ raise OperationError(space.w_ValueError, space.wrap("empty separator"))
+
+ while maxsplit != 0:
+ next = value.rfind(by, 0, end)
+ if next < 0:
+ break
+ res_w.append(wrap_rpystr(value[next+bylen: end]))
+ end = next
+ maxsplit -= 1 # NB. if it's already < 0, it stays < 0
+
+ res_w.append(wrap_rpystr(value[:end]))
+ res_w.reverse()
+ return space.newlist(res_w)
+
+def str_join__Rope_ANY(space, w_self, w_list):
+ list_w = space.unpackiterable(w_list)
+ str_w = space.str_w
+ if list_w:
+ self = w_self._node
+ listlen = 0
+ reslen = 0
+ l = []
+ for i in range(len(list_w)):
+ w_s = list_w[i]
+ if not space.is_true(space.isinstance(w_s, space.w_str)):
+ if space.is_true(space.isinstance(w_s, space.w_unicode)):
+ w_u = space.call_function(space.w_unicode, w_self)
+ return space.call_method(w_u, "join", space.newlist(list_w))
+ raise OperationError(
+ space.w_TypeError,
+ space.wrap("sequence item %d: expected string, %s "
+ "found" % (i, space.type(w_s).name)))
+ assert isinstance(w_s, W_RopeObject)
+ l.append(w_s._node)
+ return W_RopeObject(rope.join(w_self._node, l))
+ else:
+ return W_RopeObject.empty
+
+def str_rjust__Rope_ANY_ANY(space, w_self, w_arg, w_fillchar):
+ u_arg = space.int_w(w_arg)
+ selfnode = w_self._node
+ fillchar = space.str_w(w_fillchar)
+ if len(fillchar) != 1:
+ raise OperationError(space.w_TypeError,
+ space.wrap("rjust() argument 2 must be a single character"))
+
+ d = u_arg - selfnode.length()
+ if d > 0:
+ fillchar = fillchar[0] # annotator hint: it's a single character
+ resultnode = rope.concatenate(rope.LiteralStringNode(d * fillchar),
+ selfnode)
+ return W_RopeObject(resultnode)
+ else:
+ return W_RopeObject(selfnode)
+
+def str_ljust__Rope_ANY_ANY(space, w_self, w_arg, w_fillchar):
+ u_arg = space.int_w(w_arg)
+ selfnode = w_self._node
+ fillchar = space.str_w(w_fillchar)
+ if len(fillchar) != 1:
+ raise OperationError(space.w_TypeError,
+ space.wrap("rjust() argument 2 must be a single character"))
+
+ d = u_arg - selfnode.length()
+ if d > 0:
+ fillchar = fillchar[0] # annotator hint: it's a single character
+ resultnode = rope.concatenate(selfnode,
+ rope.LiteralStringNode(d * fillchar))
+ return W_RopeObject(resultnode)
+ else:
+ return W_RopeObject(selfnode)
+
+
+def _convert_idx_params(space, w_self, w_sub, w_start, w_end):
+ self = w_self._node
+ sub = w_sub._node
+ w_len = space.wrap(self.length())
+ w_start = slicetype.adapt_bound(space, w_start, w_len)
+ w_end = slicetype.adapt_bound(space, w_end, w_len)
+
+ start = space.int_w(w_start)
+ end = space.int_w(w_end)
+ assert start >= 0
+ assert end >= 0
+
+ return (self, sub, start, end)
+
+def contains__Rope_Rope(space, w_self, w_sub):
+ self = w_self._node
+ sub = w_sub._node
+ return space.newbool(rope.find(self, sub) >= 0)
+
+def str_find__Rope_Rope_ANY_ANY(space, w_self, w_sub, w_start, w_end):
+
+ (self, sub, start, end) = _convert_idx_params(space, w_self, w_sub, w_start, w_end)
+ res = rope.find(self, sub, start, end)
+ return wrapint(space, res)
+
+def str_rfind__Rope_Rope_ANY_ANY(space, w_self, w_sub, w_start, w_end):
+ # XXX works but flattens
+ (self, sub, start, end) = _convert_idx_params(space, w_self, w_sub, w_start, w_end)
+ self = self.flatten()
+ sub = sub.flatten()
+ res = self.rfind(sub, start, end)
+ return wrapint(space, res)
+
+def str_index__Rope_Rope_ANY_ANY(space, w_self, w_sub, w_start, w_end):
+
+ (self, sub, start, end) = _convert_idx_params(space, w_self, w_sub, w_start, w_end)
+ res = rope.find(self, sub, start, end)
+ if res < 0:
+ raise OperationError(space.w_ValueError,
+ space.wrap("substring not found in string.index"))
+
+ return wrapint(space, res)
+
+
+def str_rindex__Rope_Rope_ANY_ANY(space, w_self, w_sub, w_start, w_end):
+ (self, sub, start, end) = _convert_idx_params(space, w_self, w_sub, w_start, w_end)
+ # XXX works but flattens
+ self = self.flatten()
+ sub = sub.flatten()
+ res = self.rfind(sub, start, end)
+ if res < 0:
+ raise OperationError(space.w_ValueError,
+ space.wrap("substring not found in string.rindex"))
+
+ return wrapint(space, res)
+
+
+def str_replace__Rope_Rope_Rope_ANY(space, w_self, w_sub, w_by, w_maxsplit=-1):
+
+ node = w_self._node
+ length = node.length()
+ sub = w_sub._node
+ by = w_by._node
+ maxsplit = space.int_w(w_maxsplit)
+ if maxsplit == 0:
+ return w_self.create_if_subclassed()
+
+ if not sub.length():
+ upper = node.length()
+ if maxsplit > 0 and maxsplit < upper + 2:
+ upper = maxsplit - 1
+ assert upper >= 0
+ substrings = [by]
+ iter = rope.CharIterator(node)
+ for i in range(upper):
+ substrings.append(rope.LiteralStringNode(iter.next()))
+ substrings.append(by)
+ substrings.append(rope.getslice_one(node, upper, length))
+ return W_RopeObject(rope.rebalance(substrings))
+ startidx = 0
+ substrings = []
+ iter = rope.FindIterator(node, sub)
+ try:
+ foundidx = iter.next()
+ except StopIteration:
+ return w_self.create_if_subclassed()
+ while maxsplit != 0:
+ substrings.append(rope.getslice_one(node, startidx, foundidx))
+ startidx = foundidx + sub.length()
+ try:
+ foundidx = iter.next()
+ except StopIteration:
+ break
+ maxsplit = maxsplit - 1
+ substrings.append(rope.getslice_one(node, startidx, length))
+ return W_RopeObject(rope.join(by, substrings))
+
+def _strip(space, w_self, w_chars, left, right):
+ "internal function called by str_xstrip methods"
+ node = w_self._node
+ length = node.length()
+ u_chars = space.str_w(w_chars)
+
+ lpos = 0
+ rpos = length
+
+ if left:
+ #print "while %d < %d and -%s- in -%s-:"%(lpos, rpos, u_self[lpos],w_chars)
+ iter = rope.CharIterator(node)
+ while lpos < rpos and iter.next() in u_chars:
+ lpos += 1
+
+ if right:
+ # XXX improve this
+ while rpos > lpos and node.getitem(rpos - 1) in u_chars:
+ rpos -= 1
+
+ return W_RopeObject(rope.getslice_one(node, lpos, rpos))
+
+def _strip_none(space, w_self, left, right):
+ "internal function called by str_xstrip methods"
+ node = w_self._node
+ length = node.length()
+
+ lpos = 0
+ rpos = length
+
+ if left:
+ #print "while %d < %d and -%s- in -%s-:"%(lpos, rpos, u_self[lpos],w_chars)
+ iter = rope.CharIterator(node)
+ while lpos < rpos and iter.next().isspace():
+ lpos += 1
+
+ if right:
+ # XXX fix this
+ while rpos > lpos and node.getitem(rpos - 1).isspace():
+ rpos -= 1
+
+ assert rpos >= lpos # annotator hint, don't remove
+ return W_RopeObject(rope.getslice_one(node, lpos, rpos))
+
+def str_strip__Rope_Rope(space, w_self, w_chars):
+ return _strip(space, w_self, w_chars, left=1, right=1)
+
+def str_strip__Rope_None(space, w_self, w_chars):
+ return _strip_none(space, w_self, left=1, right=1)
+
+def str_rstrip__Rope_Rope(space, w_self, w_chars):
+ return _strip(space, w_self, w_chars, left=0, right=1)
+
+def str_rstrip__Rope_None(space, w_self, w_chars):
+ return _strip_none(space, w_self, left=0, right=1)
+
+
+def str_lstrip__Rope_Rope(space, w_self, w_chars):
+ return _strip(space, w_self, w_chars, left=1, right=0)
+
+def str_lstrip__Rope_None(space, w_self, w_chars):
+ return _strip_none(space, w_self, left=1, right=0)
+
+
+
+def str_center__Rope_ANY_ANY(space, w_self, w_arg, w_fillchar):
+ node = w_self._node
+ length = node.length()
+ arg = space.int_w(w_arg)
+ fillchar = space.str_w(w_fillchar)
+ if len(fillchar) != 1:
+ raise OperationError(space.w_TypeError,
+ space.wrap("center() argument 2 must be a single character"))
+
+ d = arg - length
+ if d>0:
+ offset = d//2
+ fillcharnode = rope.LiteralStringNode(fillchar)
+ pre = rope.multiply(fillcharnode, offset)
+ post = rope.multiply(fillcharnode, (d - offset))
+ centered = rope.rebalance([pre, node, post])
+ return W_RopeObject(centered)
+ else:
+ return w_self.create_if_subclassed()
+
+def str_count__Rope_Rope_ANY_ANY(space, w_self, w_arg, w_start, w_end):
+ selfnode = w_self._node
+ length = selfnode.length()
+ argnode = w_arg._node
+
+ w_start = slicetype.adapt_bound(space, w_start, space.wrap(length))
+ w_end = slicetype.adapt_bound(space, w_end, space.wrap(length))
+ u_start = space.int_w(w_start)
+ u_end = space.int_w(w_end)
+ assert u_start >= 0
+ assert u_end >= 0
+ iter = rope.FindIterator(selfnode, argnode, u_start, u_end)
+ i = 0
+ while 1:
+ try:
+ index = iter.next()
+ except StopIteration:
+ break
+ i += 1
+ return wrapint(space, i)
+
+def str_endswith__Rope_Rope_ANY_ANY(space, w_self, w_suffix, w_start, w_end):
+ (self, suffix, start, end) = _convert_idx_params(space, w_self,
+ w_suffix, w_start, w_end)
+ if suffix.length() == 0:
+ return space.w_True
+ if self.length() == 0:
+ return space.w_False
+ begin = end - suffix.length()
+ if begin < start:
+ return space.w_False
+ iter1 = rope.SeekableCharIterator(self)
+ iter1.seekforward(begin)
+ iter2 = rope.CharIterator(suffix)
+ for i in range(suffix.length()):
+ if iter1.next() != iter2.next():
+ return space.w_False
+ return space.w_True
+
+def str_startswith__Rope_Rope_ANY_ANY(space, w_self, w_prefix, w_start, w_end):
+ (self, prefix, start, end) = _convert_idx_params(space, w_self,
+ w_prefix, w_start, w_end)
+ if prefix.length() == 0:
+ return space.w_True
+ if self.length() == 0:
+ return space.w_False
+ stop = start + prefix.length()
+ if stop > end:
+ return space.w_False
+ iter1 = rope.SeekableCharIterator(self)
+ iter1.seekforward(start)
+ iter2 = rope.CharIterator(prefix)
+ for i in range(prefix.length()):
+ if iter1.next() != iter2.next():
+ return space.w_False
+ return space.w_True
+
+
+def _tabindent(node, tabsize):
+ "calculates distance after the token to the next tabstop"
+ # XXX implement reverse char iterator
+ length = node.length()
+ distance = tabsize
+ if length:
+ distance = 0
+ offset = length
+
+ while 1:
+ # no sophisticated linebreak support now
+ # '\r' just for passing adapted CPython test
+ char = node.getitem(offset - 1)
+ if char == "\n" or char == "\r":
+ break
+ distance += 1
+ offset -= 1
+ if offset == 0:
+ break
+
+ #the same like distance = len(u_token) - (offset + 1)
+ distance = (tabsize - distance) % tabsize
+ if distance == 0:
+ return tabsize
+
+ return distance
+
+
+def str_expandtabs__Rope_ANY(space, w_self, w_tabsize):
+ node = w_self._node
+ length = node.length()
+ if length == 0:
+ return W_RopeObject.empty
+ tabsize = space.int_w(w_tabsize)
+
+ expanded = []
+ iter = rope.FindIterator(node, rope.LiteralStringNode("\t"))
+ #split = u_self.split("\t")
+ #u_expanded = oldtoken = split.pop(0)
+
+ #for token in split:
+ # u_expanded += " " * _tabindent(oldtoken,u_tabsize) + token
+ # oldtoken = token
+ start = 0
+ try:
+ start = iter.next()
+ last = rope.getslice_one(node, 0, start)
+ start += 1
+ except StopIteration:
+ return w_self.create_if_subclassed()
+ expanded.append(last)
+ while 1:
+ expanded.append(rope.multiply(rope.LiteralStringNode(" "),
+ _tabindent(last, tabsize)))
+ try:
+ next = iter.next()
+ except StopIteration:
+ break
+ last = rope.getslice_one(node, start, next)
+ expanded.append(last)
+ start = next + 1
+
+ expanded.append(rope.getslice_one(node, start, length))
+ return W_RopeObject(rope.rebalance(expanded))
+
+
+def str_splitlines__Rope_ANY(space, w_self, w_keepends):
+ #import pdb; pdb.set_trace()
+ keepends = bool(space.int_w(w_keepends)) # truth value, but type checked
+ node = w_self._node
+ length = node.length()
+ if length == 0:
+ return space.newlist([])
+
+ strs_w = []
+ iter = rope.CharIterator(node)
+ i = j = 0
+ last = " "
+ char = iter.next()
+ while i < length:
+ # Find a line and append it
+ while char != '\n' and char != '\r':
+ try:
+ i += 1
+ last = char
+ char = iter.next()
+ except StopIteration:
+ break
+ # Skip the line break reading CRLF as one line break
+ eol = i
+ i += 1
+ last = char
+ try:
+ char = iter.next()
+ except StopIteration:
+ pass
+ else:
+ if last == '\r' and char == '\n':
+ i += 1
+ try:
+ last = char
+ char = iter.next()
+ except StopIteration:
+ pass
+ if keepends:
+ eol = i
+ strs_w.append(W_RopeObject(rope.getslice_one(node, j, eol)))
+ j = i
+
+ if j == 0:
+ strs_w.append(w_self.create_if_subclassed())
+ elif j < length:
+ strs_w.append(W_RopeObject(rope.getslice_one(node, j, length)))
+
+ return space.newlist(strs_w)
+
+def str_zfill__Rope_ANY(space, w_self, w_width):
+ node = w_self._node
+ length = node.length()
+ width = space.int_w(w_width)
+
+ if length >= width:
+ return w_self.create_if_subclassed()
+ zero = rope.LiteralStringNode("0")
+ if length == 0:
+ return W_RopeObject(rope.multiply(zero, width))
+
+ middle = width - length
+ firstchar = node.getitem(0)
+ if length > 0 and (firstchar == '+' or firstchar == '-'):
+ return W_RopeObject(rope.rebalance(
+ [rope.LiteralStringNode(firstchar),
+ rope.multiply(zero, middle),
+ rope.getslice_one(node, 1, length)]))
+ else:
+ middle = width - length
+ return W_RopeObject(rope.concatenate(
+ rope.multiply(zero, middle), node))
+
+def str_w__Rope(space, w_str):
+ return w_str._node.flatten()
+
+def hash__Rope(space, w_str):
+ node = w_str._node
+ x = rope.hash_rope(node)
+ return wrapint(space, x)
+
+def lt__Rope_Rope(space, w_str1, w_str2):
+ n1 = w_str1._node
+ n2 = w_str2._node
+ return space.newbool(rope.compare(n1, n2) < 0)
+
+def le__Rope_Rope(space, w_str1, w_str2):
+ n1 = w_str1._node
+ n2 = w_str2._node
+ return space.newbool(rope.compare(n1, n2) <= 0)
+
+def eq__Rope_Rope(space, w_str1, w_str2):
+ n1 = w_str1._node
+ n2 = w_str2._node
+ return space.newbool(rope.eq(n1, n2))
+
+def ne__Rope_Rope(space, w_str1, w_str2):
+ n1 = w_str1._node
+ n2 = w_str2._node
+ return space.newbool(not rope.eq(n1, n2))
+
+def gt__Rope_Rope(space, w_str1, w_str2):
+ n1 = w_str1._node
+ n2 = w_str2._node
+ return space.newbool(rope.compare(n1, n2) > 0)
+
+def ge__Rope_Rope(space, w_str1, w_str2):
+ n1 = w_str1._node
+ n2 = w_str2._node
+ return space.newbool(rope.compare(n1, n2) >= 0)
+
+def getitem__Rope_ANY(space, w_str, w_index):
+ ival = space.int_w(w_index)
+ node = w_str._node
+ slen = node.length()
+ if ival < 0:
+ ival += slen
+ if ival < 0 or ival >= slen:
+ exc = space.call_function(space.w_IndexError,
+ space.wrap("string index out of range"))
+ raise OperationError(space.w_IndexError, exc)
+ return wrap_rpystr(node.getitem(ival))
+
+def getitem__Rope_Slice(space, w_str, w_slice):
+ node = w_str._node
+ length = node.length()
+ start, stop, step, sl = w_slice.indices4(space, length)
+ if sl == 0:
+ return W_RopeObject.empty
+ return W_RopeObject(rope.getslice(node, start, stop, step, sl))
+
+def mul_string_times(space, w_str, w_times):
+ try:
+ mul = space.int_w(w_times)
+ except OperationError, e:
+ if e.match(space, space.w_TypeError):
+ raise FailedToImplement
+ raise
+ if mul <= 0:
+ return W_RopeObject.empty
+ node = w_str._node
+ length = node.length()
+ try:
+ buflen = ovfcheck(mul * length)
+ except OverflowError:
+ raise OperationError(
+ space.w_OverflowError,
+ space.wrap("repeated string is too long: %d %d" % (input_len, mul)))
+ return W_RopeObject(rope.multiply(node, mul))
+
+def mul__Rope_ANY(space, w_str, w_times):
+ return mul_string_times(space, w_str, w_times)
+
+def mul__ANY_Rope(space, w_times, w_str):
+ return mul_string_times(space, w_str, w_times)
+
+def add__Rope_Rope(space, w_left, w_right):
+ right = w_right._node
+ left = w_left._node
+ return W_RopeObject(rope.concatenate(left, right))
+
+def len__Rope(space, w_str):
+ return space.wrap(w_str._node.length())
+
+def str__Rope(space, w_str):
+ if type(w_str) is W_RopeObject:
+ return w_str
+ return W_RopeObject(w_str._node)
+
+def iter__Rope(space, w_list):
+ return W_RopeIterObject(w_list)
+
+def ord__Rope(space, w_str):
+ node = w_str._node
+ if node.length() != 1:
+ raise OperationError(
+ space.w_TypeError,
+ space.wrap("ord() expected a character, but string "
+ "of length %d found"%(len(w_str._value),)))
+ return space.wrap(ord(node.flatten()[0]))
+
+def getnewargs__Rope(space, w_str):
+ return space.newtuple([W_RopeObject(w_str._node)])
+
+def repr__Rope(space, w_str):
+ node = w_str._node
+ length = node.length()
+
+ i = 0
+ buf = [' '] * (length * 4 + 2) # safely overallocate
+
+ quote = "'"
+ if rope.find_char(node, quote) != -1 and rope.find_char(node, '"') == -1:
+ quote = '"'
+
+ buf[0] = quote
+
+ iter = rope.CharIterator(node)
+ while 1:
+ try:
+ c = iter.next()
+ i += 1
+ except StopIteration:
+ break
+ bs_char = None # character quoted by backspace
+
+ if c == '\\' or c == quote:
+ bs_char = c
+ elif c == '\t': bs_char = 't'
+ elif c == '\r': bs_char = 'r'
+ elif c == '\n': bs_char = 'n'
+ elif not '\x20' <= c < '\x7f':
+ n = ord(c)
+ buf[i] = '\\'
+ i += 1
+ buf[i] = 'x'
+ i += 1
+ buf[i] = "0123456789abcdef"[n>>4]
+ i += 1
+ buf[i] = "0123456789abcdef"[n&0xF]
+ else:
+ buf[i] = c
+
+ if bs_char is not None:
+ buf[i] = '\\'
+ i += 1
+ buf[i] = bs_char
+
+ i += 1
+ buf[i] = quote
+
+ return W_RopeObject(rope.rope_from_charlist(buf[:i+1]))
+
+
+app = gateway.applevel(r'''
+ def str_translate__Rope_ANY_ANY(s, table, deletechars=''):
+ """charfilter - unicode handling is not implemented
+
+ Return a copy of the string where all characters occurring
+ in the optional argument deletechars are removed, and the
+ remaining characters have been mapped through the given translation table,
+ which must be a string of length 256"""
+
+ if len(table) != 256:
+ raise ValueError("translation table must be 256 characters long")
+
+ L = [ table[ord(s[i])] for i in range(len(s)) if s[i] not in deletechars ]
+ return ''.join(L)
+
+ def str_decode__Rope_ANY_ANY(str, encoding=None, errors=None):
+ import codecs
+ if encoding is None and errors is None:
+ return unicode(str)
+ elif errors is None:
+ return codecs.getdecoder(encoding)(str)[0]
+ else:
+ return codecs.getdecoder(encoding)(str, errors)[0]
+
+ def str_encode__Rope_ANY_ANY(str, encoding=None, errors=None):
+ import codecs
+ if encoding is None and errors is None:
+ return unicode(str)
+ elif errors is None:
+ return codecs.getencoder(encoding)(str)[0]
+ else:
+ return codecs.getencoder(encoding)(str, errors)[0]
+''', filename=__file__)
+
+# this one should do the import of _formatting:
+app2 = gateway.applevel('''
+ import _formatting
+
+ def mod__Rope_ANY(format, values):
+ if isinstance(values, tuple):
+ return _formatting.format(format, values, None)
+ else:
+ # CPython's logic for deciding if ""%values is
+ # an error (1 value, 0 %-formatters) or not
+ # (values is of a mapping type)
+ if (hasattr(values, '__getitem__')
+ and not isinstance(values, basestring)):
+ return _formatting.format(format, (values,), values)
+ else:
+ return _formatting.format(format, (values,), None)
+''', filename=__file__)
+
+str_translate__Rope_ANY_ANY = app.interphook('str_translate__Rope_ANY_ANY')
+str_decode__Rope_ANY_ANY = app.interphook('str_decode__Rope_ANY_ANY')
+str_encode__Rope_ANY_ANY = app.interphook('str_encode__Rope_ANY_ANY')
+mod__Rope_ANY = app2.interphook('mod__Rope_ANY')
+
+# methods of the iterator
+
+def iter__RopeIter(space, w_ropeiter):
+ return w_ropeiter
+
+def next__RopeIter(space, w_ropeiter):
+ if w_ropeiter.node is None:
+ raise OperationError(space.w_StopIteration, space.w_None)
+ try:
+ char = w_ropeiter.char_iter.next()
+ w_item = wrap_rpystr(char)
+ except StopIteration:
+ w_ropeiter.node = None
+ w_ropeiter.char_iter = None
+ raise OperationError(space.w_StopIteration, space.w_None)
+ w_ropeiter.index += 1
+ return w_item
+
+def len__RopeIter(space, w_ropeiter):
+ if w_ropeiter.node is None:
+ return wrapint(space, 0)
+ index = w_ropeiter.index
+ length = w_ropeiter.node.length()
+ result = length - index
+ if result < 0:
+ return wrapint(space, 0)
+ return wrapint(space, result)
+
+# register all methods
+from pypy.objspace.std import stringtype
+register_all(vars(), stringtype)
Modified: pypy/branch/rope-branch/pypy/objspace/std/stringtype.py
==============================================================================
--- pypy/branch/rope-branch/pypy/objspace/std/stringtype.py (original)
+++ pypy/branch/rope-branch/pypy/objspace/std/stringtype.py Fri Mar 2 16:24:27 2007
@@ -4,6 +4,7 @@
from sys import maxint
def sliced(space, s, start, stop):
+ assert not space.config.objspace.std.withrope
if space.config.objspace.std.withstrslice:
from pypy.objspace.std.strsliceobject import W_StringSliceObject
from pypy.objspace.std.stringobject import W_StringObject
@@ -17,6 +18,7 @@
return W_StringObject(s[start:stop])
def joined(space, strlist):
+ assert not space.config.objspace.std.withrope
if space.config.objspace.std.withstrjoin:
from pypy.objspace.std.strjoinobject import W_StringJoinObject
return W_StringJoinObject(strlist)
@@ -222,9 +224,15 @@
if space.is_w(w_stringtype, space.w_str):
return w_obj # XXX might be reworked when space.str() typechecks
value = space.str_w(w_obj)
- w_obj = space.allocate_instance(W_StringObject, w_stringtype)
- W_StringObject.__init__(w_obj, value)
- return w_obj
+ if space.config.objspace.std.withrope:
+ from pypy.objspace.std.ropeobject import rope, W_RopeObject
+ w_obj = space.allocate_instance(W_RopeObject, w_stringtype)
+ W_RopeObject.__init__(w_obj, rope.LiteralStringNode(value))
+ return w_obj
+ else:
+ w_obj = space.allocate_instance(W_StringObject, w_stringtype)
+ W_StringObject.__init__(w_obj, value)
+ return w_obj
# ____________________________________________________________
Added: pypy/branch/rope-branch/pypy/objspace/std/test/test_rope.py
==============================================================================
--- (empty file)
+++ pypy/branch/rope-branch/pypy/objspace/std/test/test_rope.py Fri Mar 2 16:24:27 2007
@@ -0,0 +1,307 @@
+import random
+from pypy.objspace.std.rope import *
+
+def make_random_string(operations=10, slicing=True):
+ seed = random.randrange(10000)
+ print seed
+ random.seed(seed)
+ st = "abc"
+ curr = LiteralStringNode(st)
+ if slicing:
+ choice = [0, 1, 2]
+ else:
+ choice = [0, 1]
+ for i in range(operations):
+ a = (chr(random.randrange(ord('a'), ord('z') + 1)) *
+ random.randrange(500))
+ c = random.choice(choice)
+ if c == 0:
+ curr = curr + LiteralStringNode(a)
+ st = st + a
+ elif c == 1:
+ curr = LiteralStringNode(a) + curr
+ st = a + st
+ else:
+ if len(st) < 10:
+ continue
+ start = random.randrange(len(st) // 3)
+ stop = random.randrange(len(st) // 3 * 2, len(st))
+ curr = curr[start: stop]
+ st = st[start: stop]
+ return curr, st
+
+
+def test_add():
+ s = (LiteralStringNode("a" * 32) + LiteralStringNode("bc" * 32) +
+ LiteralStringNode("d" * 32) + LiteralStringNode("ef" * 32) +
+ LiteralStringNode(""))
+ assert s.depth() == 3
+ assert s.flatten() == "".join([c * 32 for c in "a", "bc", "d", "ef"])
+ s = s.rebalance()
+ assert s.flatten() == "".join([c * 32 for c in "a", "bc", "d", "ef"])
+
+def test_dont_rebalance_again():
+ s = (LiteralStringNode("a" * 32) + LiteralStringNode("b" * 32) +
+ LiteralStringNode("d" * 32) + LiteralStringNode("e" * 32) +
+ LiteralStringNode(""))
+ assert s.depth() == 3
+ assert s.flatten() == "".join([c * 32 for c in "abde"])
+ s = s.rebalance()
+ assert s.check_balanced()
+ assert s.balanced
+ assert s.flatten() == "".join([c * 32 for c in "abde"])
+
+def test_random_addition_test():
+ seed = random.randrange(10000)
+ print seed # 4443
+ st = "abc"
+ curr = LiteralStringNode(st)
+ for i in range(1000):
+ a = (chr(random.randrange(ord('a'), ord('z') + 1)) *
+ random.randrange(100))
+ if random.choice([0, 1]):
+ curr = curr + LiteralStringNode(a)
+ st = st + a
+ else:
+ curr = LiteralStringNode(a) + curr
+ st = a + st
+ assert curr.flatten() == st
+ curr = curr.rebalance()
+ assert curr.flatten() == st
+
+def test_getitem():
+ result = "".join([c * 32 for c in "a", "bc", "d", "ef"])
+ s1 = (LiteralStringNode("a" * 32) + LiteralStringNode("bc" * 32) +
+ LiteralStringNode("d" * 32) + LiteralStringNode("ef" * 32) +
+ LiteralStringNode(""))
+ s2 = s1.rebalance()
+ for i in range(len(result)):
+ for s in [s1, s2]:
+ assert s[i] == result[i]
+
+def test_getslice():
+ result = "".join([c * 32 for c in "a", "bc", "d", "ef"])
+ s1 = (LiteralStringNode("a" * 32) + LiteralStringNode("bc" * 32) +
+ LiteralStringNode("d" * 32) + LiteralStringNode("ef" * 32) +
+ LiteralStringNode(""))
+ s2 = s1.rebalance()
+ for s in [s1, s2]:
+ for start in range(0, len(result)):
+ for stop in range(start, len(result)):
+ assert s[start:stop].flatten() == result[start:stop]
+
+def test_getslice_step():
+ s1 = (LiteralStringNode("abcde") + LiteralStringNode("fghijklm") +
+ LiteralStringNode("nopqrstu") + LiteralStringNode("vwxyz") +
+ LiteralStringNode("zyxwvut") + LiteralStringNode("srqpomnlk"))
+ s2 = s1.rebalance()
+ result = s1.flatten()
+ assert s2.flatten() == result
+ for s in [s1, s2]:
+ for start in range(0, len(result)):
+ for stop in range(start, len(result)):
+ for step in range(1, stop - start):
+ assert s[start:stop:step].flatten() == result[start:stop:step]
+
+
+def test_random_addition_and_slicing():
+ seed = random.randrange(10000)
+ print seed
+ random.seed(seed)
+ st = "abc"
+ curr = LiteralStringNode(st)
+ last = None
+ all = []
+ for i in range(1000):
+ a = (chr(random.randrange(ord('a'), ord('z') + 1)) *
+ random.randrange(500))
+ last = curr
+ all.append(curr)
+ c = random.choice([0, 1, 2])
+ if c == 0:
+ curr = curr + LiteralStringNode(a)
+ st = st + a
+ elif c == 1:
+ curr = LiteralStringNode(a) + curr
+ st = a + st
+ else:
+ if len(st) < 10:
+ continue
+ # get a significant portion of the string
+ #import pdb; pdb.set_trace()
+ start = random.randrange(len(st) // 3)
+ stop = random.randrange(len(st) // 3 * 2, len(st))
+ curr = curr[start: stop]
+ st = st[start: stop]
+ assert curr.flatten() == st
+ curr = curr.rebalance()
+ assert curr.flatten() == st
+
+def test_iteration():
+ rope, real_st = make_random_string(200)
+ iter = CharIterator(rope)
+ for c in real_st:
+ c2 = iter.next()
+ assert c2 == c
+ py.test.raises(StopIteration, iter.next)
+
+def test_multiply():
+ strs = [(LiteralStringNode("a"), "a"), (LiteralStringNode("abc"), "abc"),
+ make_random_string(500)]
+ times = range(100)
+ for i in range(9, 30):
+ times.append(i ** 2 - 1)
+ times.append(i ** 2)
+ times.append(i ** 2 + 1)
+ times.append(i ** 2 + 2)
+ for r, st in strs:
+ for i in times:
+ r2 = multiply(r, i)
+ assert r2.flatten() == st * i
+
+def test_join():
+ seps = [(LiteralStringNode("a"), "a"), (LiteralStringNode("abc"), "abc"),
+ (LiteralStringNode("d"), "d"), (LiteralStringNode(""), "")]
+ l, strs = zip(*[(LiteralStringNode("x"), "x"),
+ (LiteralStringNode("xyz"), "xyz"),
+ (LiteralStringNode("w"), "w")])
+ l = list(l)
+ for s, st in seps:
+ node = join(s, l)
+ result1 = node.flatten()
+ result2 = st.join(strs)
+ for i in range(node.length()):
+ assert result1[i] == result2[i]
+
+def test_join_random():
+ l, strs = zip(*[make_random_string(10 * i) for i in range(1, 5)])
+ l = list(l)
+ seps = [(LiteralStringNode("a"), "a"), (LiteralStringNode("abc"), "abc"),
+ make_random_string(500)]
+ for s, st in seps:
+ node = join(s, l)
+ result1 = node.flatten()
+ result2 = st.join(strs)
+ for i in range(node.length()):
+ assert result1[i] == result2[i]
+
+def test_seekbackward():
+ rope = BinaryConcatNode(BinaryConcatNode(LiteralStringNode("abc"),
+ LiteralStringNode("def")),
+ LiteralStringNode("ghi"))
+ iter = SeekableCharIterator(rope)
+ for c in "abcdefgh":
+ c2 = iter.next()
+ assert c2 == c
+ for i in range(7):
+ iter.seekback(i)
+ for c in "abcdefghi"[-1-i:-1]:
+ c2 = iter.next()
+ assert c2 == c
+ c2 = iter.next()
+ assert c2 == "i"
+ py.test.raises(StopIteration, iter.next)
+
+def test_seekforward():
+ rope = BinaryConcatNode(BinaryConcatNode(LiteralStringNode("abc"),
+ LiteralStringNode("def")),
+ LiteralStringNode("ghi"))
+ rope = rope + rope
+ result = rope.flatten()
+ for j in range(len(result) - 1):
+ for i in range(len(result) - 1 - j):
+ iter = SeekableCharIterator(rope)
+# if (j, i) == (3, 1):
+# import pdb; pdb.set_trace()
+ for c in result[:j]:
+ c2 = iter.next()
+ assert c2 == c
+ iter.seekforward(i)
+ for c in result[i + j:]:
+ c2 = iter.next()
+ assert c2 == c
+ py.test.raises(StopIteration, iter.next)
+
+def test_find_char():
+ rope, st = make_random_string()
+ rope = rope[10:100]
+ st = st[10:100]
+ for i in range(len(st)):
+ print i
+ for j in range(i + 1, len(st)):
+ c = st[i:j][(j - i) // 2]
+ pos = find_char(rope, c, i, j)
+ assert pos == st.find(c, i, j)
+
+def test_find_char_bugs():
+ r = find_char(LiteralStringNode("ascii"), " ", 0, 5)
+ assert r == -1
+ r = find_char(LiteralStringNode("a"), "a")
+ assert r == 0
+
+
+def test_restart_positions():
+ restart = construct_restart_positions_node(
+ BinaryConcatNode(LiteralStringNode("aba"), LiteralStringNode("bcabab")))
+ assert restart == [0, 0, 1, 2, 0, 1, 2, 3, 4]
+ restart = construct_restart_positions("ababcabab")
+ assert restart == [0, 0, 1, 2, 0, 1, 2, 3, 4]
+
+def test_find():
+ node = BinaryConcatNode(LiteralStringNode("aba"),
+ LiteralStringNode("bcabab"))
+ pos = find(node, LiteralStringNode("abc"), 0, node.length())
+ assert pos == 2
+ node = BinaryConcatNode(LiteralStringNode("btffp"),
+ LiteralStringNode("bacbb"))
+ pos = find(node, LiteralStringNode("a"), 0, node.length())
+ assert pos == 6
+
+def test_fromcharlist():
+ for i in range(0, 100, 10):
+ chars = ["a"] * 50 + ["b"] * i
+ node = rope_from_charlist(chars)
+ assert node.flatten() == "a" * 50 + "b" * i
+ assert rope_from_charlist([]).flatten() == ""
+
+def test_find_iterator():
+ for searchstring in ["abc", "a", "", "x", "xyz"]:
+ node = join(LiteralStringNode(searchstring),
+ [LiteralStringNode("cde" * i) for i in range(1, 10)])
+ # node.view()
+ iter = FindIterator(node, LiteralStringNode(searchstring))
+ s = node.flatten()
+ assert s == searchstring.join(["cde" * i for i in range(1, 10)])
+ start = 0
+ while 1:
+ r2 = s.find(searchstring, start)
+ try:
+ r1 = iter.next()
+ except StopIteration:
+ assert r2 == -1
+ break
+ assert r1 == r2
+ start = r2 + max(len(searchstring), 1)
+
+def test_hash():
+ from pypy.rlib.rarithmetic import _hash_string
+ rope, st = make_random_string()
+ assert hash_rope(rope) == _hash_string(st)
+
+def test_equality():
+ l = [make_random_string() for i in range(3)]
+ l.append((LiteralStringNode(""), ""))
+ for rope1, st1 in l:
+ for rope2, st2 in l:
+ assert eq(rope1, rope2) == (st1 == st2)
+
+def test_compare_random():
+ l = [make_random_string() for i in range(3)]
+ l.append((LiteralStringNode(""), ""))
+ for rope1, st1 in l:
+ for rope2, st2 in l:
+ c = compare(rope1, rope2)
+ if c:
+ c = c // abs(c)
+ assert c == cmp(st1, st2)
+
Added: pypy/branch/rope-branch/pypy/objspace/std/test/test_ropeobject.py
==============================================================================
--- (empty file)
+++ pypy/branch/rope-branch/pypy/objspace/std/test/test_ropeobject.py Fri Mar 2 16:24:27 2007
@@ -0,0 +1,27 @@
+import py
+
+from pypy.objspace.std.test import test_stringobject, test_unicodeobject
+from pypy.conftest import gettestobjspace
+
+class AppTestRopeObject(test_stringobject.AppTestStringObject):
+
+ def setup_class(cls):
+ cls.space = gettestobjspace(**{"objspace.std.withrope": True})
+
+class AppTestRopeUnicode(object):
+
+ def setup_class(cls):
+ cls.space = gettestobjspace(**{"objspace.std.withrope": True})
+
+ def test_startswith(self):
+ assert "abc".startswith("a", 0, 2147483647)
+
+class AppTestUnicodeRopeStdOnly(test_unicodeobject.AppTestUnicodeStringStdOnly):
+
+ def setup_class(cls):
+ cls.space = gettestobjspace(**{"objspace.std.withrope": True})
+
+class AppTestUnicodeRope(test_unicodeobject.AppTestUnicodeString):
+
+ def setup_class(cls):
+ cls.space = gettestobjspace(**{"objspace.std.withrope": True})
Modified: pypy/branch/rope-branch/pypy/objspace/std/unicodeobject.py
==============================================================================
--- pypy/branch/rope-branch/pypy/objspace/std/unicodeobject.py (original)
+++ pypy/branch/rope-branch/pypy/objspace/std/unicodeobject.py Fri Mar 2 16:24:27 2007
@@ -1,6 +1,7 @@
from pypy.objspace.std.objspace import *
from pypy.interpreter import gateway
from pypy.objspace.std.stringobject import W_StringObject
+from pypy.objspace.std.ropeobject import W_RopeObject
from pypy.objspace.std.noneobject import W_NoneObject
from pypy.objspace.std.sliceobject import W_SliceObject
from pypy.rlib.rarithmetic import intmask, ovfcheck
@@ -100,11 +101,17 @@
def add__String_Unicode(space, w_left, w_right):
return space.add(space.call_function(space.w_unicode, w_left) , w_right)
+add__Rope_Unicode = add__String_Unicode
+
def add__Unicode_String(space, w_left, w_right):
return space.add(w_left, space.call_function(space.w_unicode, w_right))
+add__Unicode_Rope = add__Unicode_String
+
def contains__String_Unicode(space, w_container, w_item):
return space.contains(space.call_function(space.w_unicode, w_container), w_item )
+contains__Rope_Unicode = contains__String_Unicode
+
def _find(self, sub, start, end):
if len(sub) == 0:
@@ -388,6 +395,7 @@
def unicode_strip__Unicode_String(space, w_self, w_chars):
return space.call_method(w_self, 'strip',
space.call_function(space.w_unicode, w_chars))
+unicode_strip__Unicode_Rope = unicode_strip__Unicode_String
def unicode_lstrip__Unicode_None(space, w_self, w_chars):
return _strip_none(space, w_self, 1, 0)
@@ -397,6 +405,8 @@
return space.call_method(w_self, 'lstrip',
space.call_function(space.w_unicode, w_chars))
+unicode_lstrip__Unicode_Rope = unicode_lstrip__Unicode_String
+
def unicode_rstrip__Unicode_None(space, w_self, w_chars):
return _strip_none(space, w_self, 0, 1)
def unicode_rstrip__Unicode_Unicode(space, w_self, w_chars):
@@ -405,6 +415,8 @@
return space.call_method(w_self, 'rstrip',
space.call_function(space.w_unicode, w_chars))
+unicode_rstrip__Unicode_Rope = unicode_rstrip__Unicode_String
+
def unicode_capitalize__Unicode(space, w_self):
input = w_self._value
if len(input) == 0:
@@ -999,41 +1011,49 @@
import stringtype
W_UnicodeObject = W_UnicodeObject
from pypy.objspace.std.stringobject import W_StringObject
+ from pypy.objspace.std.ropeobject import W_RopeObject
def str_strip__String_Unicode(space, w_self, w_chars):
return space.call_method(space.call_function(space.w_unicode, w_self),
'strip', w_chars)
+ str_strip__Rope_Unicode = str_strip__String_Unicode
def str_lstrip__String_Unicode(space, w_self, w_chars):
return space.call_method(space.call_function(space.w_unicode, w_self),
'lstrip', w_chars)
+ str_lstrip__Rope_Unicode = str_lstrip__String_Unicode
def str_rstrip__String_Unicode(space, w_self, w_chars):
return space.call_method(space.call_function(space.w_unicode, w_self),
'rstrip', w_chars)
+ str_rstrip__Rope_Unicode = str_rstrip__String_Unicode
def str_count__String_Unicode_ANY_ANY(space, w_self, w_substr, w_start, w_end):
return space.call_method(space.call_function(space.w_unicode, w_self),
'count', w_substr, w_start, w_end)
+ str_count__Rope_Unicode_ANY_ANY = str_count__String_Unicode_ANY_ANY
def str_find__String_Unicode_ANY_ANY(space, w_self, w_substr, w_start, w_end):
return space.call_method(space.call_function(space.w_unicode, w_self),
'find', w_substr, w_start, w_end)
+ str_find__Rope_Unicode_ANY_ANY = str_find__String_Unicode_ANY_ANY
def str_rfind__String_Unicode_ANY_ANY(space, w_self, w_substr, w_start, w_end):
return space.call_method(space.call_function(space.w_unicode, w_self),
'rfind', w_substr, w_start, w_end)
+ str_rfind__Rope_Unicode_ANY_ANY = str_rfind__String_Unicode_ANY_ANY
def str_index__String_Unicode_ANY_ANY(space, w_self, w_substr, w_start, w_end):
return space.call_method(space.call_function(space.w_unicode, w_self),
'index', w_substr, w_start, w_end)
+ str_index__Rope_Unicode_ANY_ANY = str_index__String_Unicode_ANY_ANY
def str_rindex__String_Unicode_ANY_ANY(space, w_self, w_substr, w_start, w_end):
return space.call_method(space.call_function(space.w_unicode, w_self),
'rindex', w_substr, w_start, w_end)
-
+ str_rindex__Rope_Unicode_ANY_ANY = str_rindex__String_Unicode_ANY_ANY
def str_replace__String_Unicode_Unicode_ANY(space, w_self, w_old, w_new, w_maxsplit):
return space.call_method(space.call_function(space.w_unicode, w_self),
'replace', w_old, w_new, w_maxsplit)
-
+ str_replace__Rope_Unicode_Unicode_ANY = str_replace__String_Unicode_Unicode_ANY
def str_split__String_Unicode_ANY(space, w_self, w_delim, w_maxsplit):
return space.call_method(space.call_function(space.w_unicode, w_self),
'split', w_delim, w_maxsplit)
-
+ str_split__Rope_Unicode_ANY = str_split__String_Unicode_ANY
def str_rsplit__String_Unicode_ANY(space, w_self, w_delim, w_maxsplit):
return space.call_method(space.call_function(space.w_unicode, w_self),
'rsplit', w_delim, w_maxsplit)
-
+ str_rsplit__Rope_Unicode_ANY = str_rsplit__String_Unicode_ANY
register_all(vars(), stringtype)
More information about the pypy-svn
mailing list