1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 // docs - mod docs, item docs
15 // pull out into its own crate
16 // impl Default, Extend
17 // impl DoubleEndedIter and ExactSizeIter for RopeChars
24 use std::num::{SignedInt, Int};
26 // A Rope, based on an unbalanced binary tree. The rope is somewhat special in
27 // that it tracks positions in the source text. So when locating a position in
28 // the rope, the user can use either a current position in the text or a
29 // position in the source text, which the Rope will adjust to a current position
35 // FIXME: Allocation is very dumb at the moment, we always add another
36 // buffer for every inserted string and we never resuse or collect old
41 // A view over a portion of a Rope. Analagous to string slices (`str`);
42 pub struct RopeSlice<'rope> {
43 // All nodes which make up the slice, in order.
44 nodes: Vec<&'rope Lnode>,
45 // The offset of the start point in the first node.
47 // The length of text in the last node.
51 // An iterator over the chars in a rope.
52 pub struct RopeChars<'rope> {
53 data: RopeSlice<'rope>,
60 // Create an empty rope.
61 pub fn new() -> Rope {
63 root: Node::empty_inner(),
70 // Uses text as initial storage.
71 pub fn from_string(text: String) -> Rope {
72 // TODO should split very large texts into segments as we insert
74 let mut result = Rope::new();
75 result.insert(0, text);
80 // When initialising a rope, indicates that the rope is complete wrt the
82 fn fix_src(&mut self) {
84 self.src_len = self.len;
87 // Length of the rope.
88 pub fn len(&self) -> usize {
92 pub fn insert_copy(&mut self, start: usize, text: &str) {
93 // FIXME If we did clever things with allocation, we could do better here.
94 self.insert(start, text.to_string());
97 pub fn insert(&mut self, start: usize, text: String) {
98 self.insert_inner(start,
100 |this, node| this.root.insert(node, start, start))
103 pub fn src_insert(&mut self, start: usize, text: String) {
104 self.insert_inner(start,
106 |this, node| this.root.src_insert(node, start, start))
109 fn insert_inner<F>(&mut self,
113 where F: Fn(&mut Rope, Box<Node>) -> NodeAction
119 debug_assert!(start <= self.src_len, "insertion out of bounds of rope");
121 let len = text.len();
122 let storage = text.into_bytes();
123 let new_node = box Node::new_leaf(&storage[..][0] as *const u8, len, 0);
124 self.storage.push(storage);
126 match do_insert(self, new_node) {
127 NodeAction::Change(n, adj) => {
128 assert!(adj as usize == len);
131 NodeAction::Adjust(adj) => {
132 assert!(adj as usize == len);
134 _ => panic!("Unexpected action")
139 pub fn push(&mut self, text: String) {
140 let len = self.len();
141 self.insert(len, text);
144 pub fn push_copy(&mut self, text: &str) {
145 // If we did clever things with allocation, we could do better here
146 let len = self.len();
147 self.insert(len, text.to_string());
150 pub fn remove(&mut self, start: usize, end: usize) {
151 self.remove_inner(start, end, |this| this.root.remove(start, end, start))
154 pub fn src_remove(&mut self, start: usize, end: usize) {
155 self.remove_inner(start, end, |this| this.root.src_remove(start, end, start))
158 fn remove_inner<F>(&mut self,
162 where F: Fn(&mut Rope) -> NodeAction
164 assert!(end >= start);
169 match do_remove(self) {
170 NodeAction::None => {}
171 NodeAction::Remove => {
172 self.root = Node::empty_inner();
175 NodeAction::Adjust(adj) => self.len = (self.len as isize + adj) as usize,
176 NodeAction::Change(node, adj) => {
178 self.len = (self.len as isize + adj) as usize;
184 // TODO src_replace_str
186 // This can go horribly wrong if you overwrite a grapheme of different size.
187 // It is the callers responsibility to ensure that the grapheme at point start
188 // has the same size as new_char.
189 pub fn replace(&mut self, start: usize, new_char: char) {
190 assert!(start + new_char.len_utf8() <= self.len);
191 // This is pretty wasteful in that we're allocating for no point, but
192 // I think that is better than duplicating a bunch of code.
193 // It should be possible to view a &char as a &[u8] somehow, and then
194 // we can optimise this (FIXME).
195 self.replace_str(start, &new_char.to_string()[..]);
198 pub fn replace_str(&mut self, start: usize, new_str: &str) {
199 assert!(start + new_str.len() <= self.len);
200 self.root.replace(start, new_str);
203 // Note, this is not necessarily cheap.
204 pub fn col_for_src_loc(&self, src_loc: usize) -> usize {
205 assert!(src_loc <= self.src_len);
206 match self.root.col_for_src_loc(src_loc) {
207 Search::Done(c) | Search::Continue(c) => c
211 pub fn slice(&self, Range { start, end }: Range<usize>) -> RopeSlice {
212 debug_assert!(end > start && start <= self.len && end <= self.len);
214 return RopeSlice::empty();
217 let mut result = RopeSlice::empty();
218 self.root.find_slice(start, end, &mut result);
222 pub fn full_slice(&self) -> RopeSlice {
223 self.slice(0..self.len)
226 pub fn src_slice(&self, Range { start, end }: Range<usize>) -> RopeSlice {
227 debug_assert!(end > start && start <= self.src_len && end <= self.src_len);
229 return RopeSlice::empty();
232 let mut result = RopeSlice::empty();
233 self.root.find_src_slice(start, end, &mut result);
237 pub fn chars(&self) -> RopeChars {
239 data: self.full_slice(),
247 impl<'rope> RopeSlice<'rope> {
248 fn empty<'r>() -> RopeSlice<'r> {
257 impl<'rope> Iterator for RopeChars<'rope> {
258 type Item = (char, usize);
259 fn next(&mut self) -> Option<(char, usize)> {
260 if self.cur_node >= self.data.nodes.len() {
264 let byte = self.abs_byte;
265 let node = self.data.nodes[self.cur_node];
266 if self.cur_byte >= node.len {
272 let result = self.read_char();
273 return Some((result, byte));
277 impl<'rope> RopeChars<'rope> {
278 fn read_char(&mut self) -> char {
279 let first_byte = self.read_byte();
280 let width = unicode::str::utf8_char_width(first_byte);
282 return first_byte as char
285 panic!("non-utf8 char in rope");
287 let mut buf = [first_byte, 0, 0, 0];
290 while start < width {
291 buf[start] = self.read_byte();
295 match ::std::str::from_utf8(&buf[..width]).ok() {
296 Some(s) => s.char_at(0),
297 None => panic!("bad chars in rope")
301 fn read_byte(&mut self) -> u8 {
302 let node = self.data.nodes[self.cur_node];
303 let addr = node.text as usize + self.cur_byte;
306 let addr = addr as *const u8;
313 impl ::std::str::FromStr for Rope {
315 fn from_str(text: &str) -> Result<Rope, ()> {
316 // TODO should split large texts into segments as we insert
318 let mut result = Rope::new();
319 result.insert_copy(0, text);
325 impl<'a> fmt::Display for RopeSlice<'a> {
326 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
327 if self.nodes.len() == 0 {
331 let last_idx = self.nodes.len() - 1;
332 for (i, n) in self.nodes.iter().enumerate() {
333 let mut ptr = n.text;
336 ptr = (ptr as usize + self.start) as *const u8;
345 ::std::str::from_utf8(::std::slice::from_raw_parts(ptr, len)).unwrap()));
352 impl<'a> fmt::Debug for RopeSlice<'a> {
353 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
354 let last_idx = self.nodes.len() - 1;
355 for (i, n) in self.nodes.iter().enumerate() {
356 let mut ptr = n.text;
359 ptr = (ptr as usize + self.start) as *const u8;
362 try!(write!(fmt, "|"));
370 ::std::str::from_utf8(::std::slice::from_raw_parts(ptr, len)).unwrap()));
377 impl fmt::Display for Rope {
378 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
379 write!(fmt, "{}", self.root)
383 impl fmt::Debug for Rope {
384 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
385 write!(fmt, "{:?}", self.root)
389 impl fmt::Display for Node {
390 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
392 Node::InnerNode(Inode { ref left, ref right, .. }) => {
393 if let Some(ref left) = *left {
394 write!(fmt, "{}", left)
397 }.and_then(|_| if let Some(ref right) = *right {
398 write!(fmt, "{}", right)
403 Node::LeafNode(Lnode{ ref text, len, .. }) => {
407 ::std::str::from_utf8(::std::slice::from_raw_parts(*text, len)).unwrap())
414 impl fmt::Debug for Node {
415 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
417 Node::InnerNode(Inode { ref left, ref right, weight, .. }) => {
418 try!(write!(fmt, "("));
419 if let Some(ref left) = *left {
420 try!(write!(fmt, "left: {:?}", &**left));
422 try!(write!(fmt, "left: ()"));
424 try!(write!(fmt, ", "));
425 if let Some(ref right) = *right {
426 try!(write!(fmt, "right: {:?}", &**right));
428 try!(write!(fmt, "right: ()"));
430 write!(fmt, "; {})", weight)
432 Node::LeafNode(Lnode{ ref text, len, .. }) => {
436 ::std::str::from_utf8(::std::slice::from_raw_parts(*text, len)).unwrap(),
444 #[derive(Clone, Eq, PartialEq)]
450 #[derive(Clone, Eq, PartialEq)]
454 left: Option<Box<Node>>,
455 right: Option<Box<Node>>,
458 #[derive(Clone, Eq, PartialEq)]
462 // text + src_offset = src text (src_offset should always be <= 0)
467 fn empty_inner() -> Node {
468 Node::InnerNode(Inode {
476 fn new_inner(left: Option<Box<Node>>,
477 right: Option<Box<Node>>,
481 Node::InnerNode(Inode {
485 src_weight: src_weight,
489 fn new_leaf(text: *const u8, len: usize, src_offset: isize) -> Node {
490 Node::LeafNode(Lnode {
493 src_offset: src_offset,
497 fn len(&self) -> usize {
499 Node::InnerNode(Inode { weight, ref right, .. }) => {
501 Some(ref r) => weight + r.len(),
505 Node::LeafNode(Lnode { len, .. }) => len,
509 fn fix_src(&mut self) {
511 Node::InnerNode(ref mut i) => i.fix_src(),
512 Node::LeafNode(ref mut l) => {
518 // Most of these methods are just doing dynamic dispatch, TODO use a macro
520 // precond: start < end
521 fn remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
523 Node::InnerNode(ref mut i) => i.remove(start, end, src_start),
524 Node::LeafNode(ref mut l) => l.remove(start, end, src_start),
528 fn src_remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
530 Node::InnerNode(ref mut i) => i.src_remove(start, end, src_start),
531 Node::LeafNode(ref mut l) => {
532 debug!("src_remove: pre-adjust {}-{}; {}", start, end, l.src_offset);
533 let start = minz(start as isize + l.src_offset);
534 let end = minz(end as isize + l.src_offset);
535 let src_start = minz(src_start as isize + l.src_offset);
536 debug!("src_remove: post-adjust {}-{}, {}", start, end, src_start);
538 l.remove(start as usize, end as usize, src_start as usize)
546 fn insert(&mut self, node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
548 Node::InnerNode(ref mut i) => i.insert(node, start, src_start),
549 Node::LeafNode(ref mut l) => l.insert(node, start, src_start),
553 fn src_insert(&mut self, node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
555 Node::InnerNode(ref mut i) => i.src_insert(node, start, src_start),
556 Node::LeafNode(ref mut l) => {
557 debug!("src_insert: pre-adjust {}, {}; {}", start, src_start, l.src_offset);
558 let start = minz(start as isize + l.src_offset);
559 let src_start = minz(src_start as isize + l.src_offset);
560 debug!("src_insert: post-adjust {}, {}", start, src_start);
561 l.insert(node, start as usize, src_start as usize)
566 fn find_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
568 Node::InnerNode(ref i) => i.find_slice(start, end, slice),
569 Node::LeafNode(ref l) => l.find_slice(start, end, slice),
573 fn find_src_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
575 Node::InnerNode(ref i) => i.find_src_slice(start, end, slice),
576 Node::LeafNode(ref l) => {
577 debug!("find_src_slice: pre-adjust {}-{}; {}", start, end, l.src_offset);
578 let start = minz(start as isize + l.src_offset);
579 let end = minz(end as isize + l.src_offset);
580 debug!("find_src_slice: post-adjust {}-{}", start, end);
582 l.find_slice(start as usize, end as usize, slice);
588 fn replace(&mut self, start: usize, new_str: &str) {
590 Node::InnerNode(ref mut i) => i.replace(start, new_str),
591 Node::LeafNode(ref mut l) => l.replace(start, new_str),
595 fn col_for_src_loc(&self, src_loc: usize) -> Search {
597 Node::InnerNode(ref i) => i.col_for_src_loc(src_loc),
598 Node::LeafNode(ref l) => l.col_for_src_loc(src_loc),
602 fn find_last_char(&self, c: char) -> Option<usize> {
604 Node::InnerNode(ref i) => i.find_last_char(c),
605 Node::LeafNode(ref l) => l.find_last_char(c),
610 #[derive(Debug, Clone, Eq, PartialEq)]
614 Adjust(isize), // Arg is the length of the old node - the length of the newly adjusted node.
615 Change(Box<Node>, isize) // Args are the new node and the change in length.
619 fn remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
620 debug!("Inode::remove: {}, {}, {}", start, end, self.weight);
622 let left_action = if start <= self.weight {
623 if let Some(ref mut left) = self.left {
624 left.remove(start, end, src_start)
632 let right_action = if end > self.weight {
633 if let Some(ref mut right) = self.right {
634 let start = if start < self.weight {
639 let src_start = if src_start < self.src_weight {
642 src_start - self.src_weight
644 right.remove(start, end - self.weight, src_start)
653 if left_action == NodeAction::Remove && right_action == NodeAction::Remove ||
654 left_action == NodeAction::Remove && self.right.is_none() ||
655 right_action == NodeAction::Remove && self.left.is_none() {
656 return NodeAction::Remove;
659 if left_action == NodeAction::Remove {
660 return NodeAction::Change(self.right.clone().unwrap(),
661 -(self.weight as isize));
663 if right_action == NodeAction::Remove {
664 return NodeAction::Change(self.left.clone().unwrap(),
665 -(self.right.as_ref().map(|n| n.len()).unwrap() as isize));
668 let mut total_adj = 0;
669 if let NodeAction::Change(ref n, adj) = left_action {
670 self.left = Some(n.clone());
671 self.weight = (self.weight as isize + adj) as usize;
674 if let NodeAction::Change(ref n, adj) = right_action {
675 self.right = Some(n.clone());
679 if let NodeAction::Adjust(adj) = left_action {
680 self.weight = (self.weight as isize + adj) as usize;
683 if let NodeAction::Adjust(adj) = right_action {
687 return NodeAction::Adjust(total_adj);
690 fn src_remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
691 // TODO refactor with remove
693 debug!("Inode::src_remove: {}, {}, {}/{}", start, end, self.src_weight, self.weight);
695 let left_action = if start <= self.src_weight {
696 if let Some(ref mut left) = self.left {
697 left.src_remove(start, end, src_start)
705 let right_action = if end > self.src_weight {
706 if let Some(ref mut right) = self.right {
707 let start = if start < self.src_weight {
710 start - self.src_weight
712 let src_start = if src_start < self.src_weight {
715 src_start - self.src_weight
717 right.src_remove(start, end - self.src_weight, src_start)
726 if left_action == NodeAction::Remove && right_action == NodeAction::Remove ||
727 left_action == NodeAction::Remove && self.right.is_none() ||
728 right_action == NodeAction::Remove && self.left.is_none() {
729 return NodeAction::Remove;
732 if left_action == NodeAction::Remove {
733 return NodeAction::Change(self.right.clone().unwrap(),
734 -(self.weight as isize));
736 if right_action == NodeAction::Remove {
737 return NodeAction::Change(self.left.clone().unwrap(),
738 -(self.right.as_ref().map(|n| n.len()).unwrap() as isize));
741 let mut total_adj = 0;
742 if let NodeAction::Change(ref n, adj) = left_action {
743 self.left = Some(n.clone());
744 self.weight = (self.weight as isize + adj) as usize;
747 if let NodeAction::Change(ref n, adj) = right_action {
748 self.right = Some(n.clone());
752 if let NodeAction::Adjust(adj) = left_action {
753 self.weight = (self.weight as isize + adj) as usize;
756 if let NodeAction::Adjust(adj) = right_action {
760 return NodeAction::Adjust(total_adj);
763 fn insert(&mut self, node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
764 let mut total_adj = 0;
765 if start <= self.weight {
766 let action = if let Some(ref mut left) = self.left {
767 left.insert(node, start, src_start)
769 assert!(self.weight == 0);
770 let len = node.len() as isize;
771 NodeAction::Change(node, len)
775 NodeAction::Change(n, adj) => {
777 self.weight += adj as usize;
780 NodeAction::Adjust(adj) => {
781 self.weight += adj as usize;
784 _ => panic!("Unexpected action"),
787 let action = if let Some(ref mut right) = self.right {
788 assert!(start >= self.weight);
789 assert!(src_start >= self.src_weight);
790 right.insert(node, start - self.weight, src_start - self.src_weight)
792 let len = node.len() as isize;
793 NodeAction::Change(node, len)
797 NodeAction::Change(n, adj) => {
798 self.right = Some(n);
801 NodeAction::Adjust(adj) => total_adj += adj,
802 _ => panic!("Unexpected action"),
806 NodeAction::Adjust(total_adj)
809 fn src_insert(&mut self, node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
810 let mut total_adj = 0;
811 if start <= self.src_weight {
812 let action = if let Some(ref mut left) = self.left {
813 left.src_insert(node, start, src_start)
815 let len = node.len() as isize;
816 NodeAction::Change(node, len)
820 NodeAction::Change(n, adj) => {
822 self.weight += adj as usize;
825 NodeAction::Adjust(adj) => {
826 self.weight += adj as usize;
829 _ => panic!("Unexpected action"),
832 let action = if let Some(ref mut right) = self.right {
833 assert!(start >= self.src_weight);
834 assert!(src_start >= self.src_weight);
835 right.src_insert(node, start - self.src_weight, src_start - self.src_weight)
837 let len = node.len() as isize;
838 NodeAction::Change(node, len)
842 NodeAction::Change(n, adj) => {
843 self.right = Some(n);
846 NodeAction::Adjust(adj) => total_adj += adj,
847 _ => panic!("Unexpected action"),
851 NodeAction::Adjust(total_adj)
854 fn find_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
855 debug!("Inode::find_slice: {}, {}, {}", start, end, self.weight);
856 if start < self.weight {
857 self.left.as_ref().unwrap().find_slice(start, end, slice);
859 if end > self.weight {
860 let start = if start < self.weight {
865 self.right.as_ref().unwrap().find_slice(start, end - self.weight, slice)
869 fn find_src_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
870 debug!("Inode::find_src_slice: {}, {}, {}", start, end, self.src_weight);
871 if start < self.src_weight && self.left.is_some() {
872 self.left.as_ref().unwrap().find_src_slice(start, end, slice);
874 if end > self.src_weight && self.right.is_some() {
875 let start = if start < self.src_weight {
878 start - self.src_weight
880 self.right.as_ref().unwrap().find_src_slice(start, end - self.src_weight, slice)
884 fn replace(&mut self, start: usize, new_str: &str) {
885 debug!("Inode::replace: {}, {}, {}", start, new_str, self.weight);
886 let end = start + new_str.len();
887 if start < self.weight {
888 if let Some(ref mut left) = self.left {
889 left.replace(start, &new_str[..::std::cmp::min(self.weight-start, new_str.len())]);
894 if end > self.weight {
895 let (start, offset) = if start < self.weight {
896 (0, self.weight - start)
898 (start - self.weight, 0)
900 if let Some(ref mut right) = self.right {
901 right.replace(start, &new_str[offset..]);
908 fn fix_src(&mut self) {
909 self.src_weight = self.weight;
910 if let Some(ref mut left) = self.left {
913 if let Some(ref mut right) = self.right {
918 fn col_for_src_loc(&self, src_loc: usize) -> Search {
919 debug!("Inode::col_for_src_loc: {}, {}", src_loc, self.src_weight);
920 let result = if src_loc < self.src_weight {
921 if self.left.is_some() {
922 Some(self.left.as_ref().unwrap().col_for_src_loc(src_loc))
929 if result.is_none() {
930 if self.right.is_some() {
931 match self.right.as_ref().unwrap().col_for_src_loc(src_loc - self.src_weight) {
932 Search::Continue(c) if self.left.is_some() => {
933 // TODO broken - need number of chars, not bytes
934 match self.left.as_ref().unwrap().find_last_char('\n') {
936 Search::Done((self.weight - l - 1) + c)
939 Search::Continue(c + self.weight)
946 panic!("Can't look up source location");
949 // TODO don't do it this way
954 fn find_last_char(&self, c: char) -> Option<usize> {
955 // TODO use map or something
957 Some(ref right) => match right.find_last_char(c) {
958 Some(x) => return Some(x),
964 Some(ref left) => match left.find_last_char(c) {
965 Some(x) => return Some(x),
975 fn remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
976 debug!("Lnode::remove: {}, {}, {}", start, end, self.len);
977 assert!(start <= self.len);
979 if start == 0 && end >= self.len {
980 // The removal span includes us, remove ourselves.
981 return NodeAction::Remove;
984 let old_len = self.len;
986 // Truncate the left of the node.
987 self.text = (self.text as usize + end) as *const u8;
988 self.len = old_len - end;
989 let delta = self.len as isize - old_len as isize;
990 self.src_offset += delta;
991 return NodeAction::Adjust(delta);
995 // Truncate the right of the node.
997 return NodeAction::Adjust(self.len as isize - old_len as isize);
1000 let delta = -((end - start) as isize);
1001 // Split the node (span to remove is in the middle of the node).
1002 let new_node = Node::new_inner(
1003 Some(box Node::new_leaf(self.text, start, self.src_offset)),
1004 Some(box Node::new_leaf((self.text as usize + end) as *const u8,
1006 self.src_offset + delta)),
1009 return NodeAction::Change(box new_node, delta);
1012 fn insert(&mut self, mut node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
1014 box Node::LeafNode(ref mut node) => node.src_offset = self.src_offset,
1018 let len = node.len();
1020 // Insert at the start of the node
1021 let new_node = box Node::new_inner(Some(node),
1022 Some(box Node::LeafNode(self.clone())),
1025 return NodeAction::Change(new_node, len as isize)
1028 if start == self.len {
1029 // Insert at the end of the node
1030 let new_node = box Node::new_inner(Some(box Node::LeafNode(self.clone())),
1034 return NodeAction::Change(new_node, len as isize)
1037 // Insert into the middle of the node
1038 let left = Some(box Node::new_leaf(self.text, start, self.src_offset));
1039 let new_left = box Node::new_inner(left, Some(node), start, src_start);
1040 let right = Some(box Node::new_leaf((self.text as usize + (start)) as *const u8,
1043 let new_node = box Node::new_inner(Some(new_left), right, start + len, src_start);
1045 return NodeAction::Change(new_node, len as isize)
1048 fn find_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
1049 debug!("Lnode::find_slice: {}, {}, {}, {}", start, end, self.len, self.src_offset);
1050 debug_assert!(start < self.len, "Shouldn't have called this fn, we're out of bounds");
1052 slice.nodes.push(self);
1053 let mut len = ::std::cmp::min(end, self.len);
1055 slice.start = start;
1061 fn replace(&mut self, start: usize, new_str: &str) {
1062 debug!("Lnode::replace: {}, {}, {}", start, new_str, self.len);
1063 debug_assert!(start + new_str.len() <= self.len);
1064 let addr = (self.text as usize + start) as *mut u8;
1066 ::std::intrinsics::copy_nonoverlapping_memory(addr, &new_str.as_bytes()[0], new_str.len());
1070 fn col_for_src_loc(&self, src_loc: usize) -> Search {
1071 debug!("Lnode::col_for_src_loc {}; {}; {}", src_loc, self.len, self.src_offset);
1072 let loc = if (src_loc as isize) > (self.len as isize - self.src_offset) {
1073 // The source location we are looking up has been removed
1076 (src_loc as isize + self.src_offset)
1079 // FIXME if '/n' as u8 is part of a multi-byte grapheme, then this will
1080 // cause false positives.
1081 let mut i = loc - 1;
1084 let c = *((self.text as usize + i as usize) as *const u8);
1085 if c as char == '\n' {
1086 debug!("Lnode::col_for_src_loc, return Done({})", loc - i - 1);
1087 return Search::Done((loc - i - 1) as usize)
1093 let loc = minz(loc) as usize;
1094 debug!("Lnode::col_for_src_loc, return Continue({})", loc);
1095 Search::Continue(loc)
1098 fn find_last_char(&self, needle: char) -> Option<usize> {
1099 // FIXME due to multi-byte chars, this will give false positives
1100 // FIXME use std::str::GraphemeIndices to do this!
1101 let mut loc = self.len as isize - 1;
1104 let c = *((self.text as usize + loc as usize) as *const u8);
1105 if c as char == needle {
1106 return Some(loc as usize)
1116 // The state of searching through a rope.
1124 fn minz<I: SignedInt>(x: I) -> I {
1125 if x.is_negative() {
1135 // FIXME is this a Rust bug? Why is minz not imported by the glob import?
1140 let r = Rope::new();
1141 assert!(r.len() == 0);
1142 assert!(r.to_string() == "");
1144 let r = Rope::from_string("Hello world!".to_string());
1145 assert!(r.len() == 12);
1146 assert!(r.to_string() == "Hello world!");
1152 assert!(super::minz(x) == 0);
1154 assert!(minz(x) == 42);
1156 assert!(minz(x) == 0);
1158 assert!(minz(x) == 0);
1160 assert!(minz(x) == 42);
1162 assert!(minz(x) == 0);
1166 fn test_from_string() {
1167 let r: Rope = "Hello world!".parse().unwrap();
1168 assert!(r.to_string() == "Hello world!");
1173 let mut r: Rope = "Hello world!".parse().unwrap();
1175 assert!(r.to_string() == "d!");
1176 assert!(r.src_slice(0..5).to_string() == "");
1177 assert!(r.src_slice(10..12).to_string() == "d!");
1179 let mut r: Rope = "Hello world!".parse().unwrap();
1181 assert!(r.to_string() == "Hell");
1183 //assert!(r.src_slice(0..4).to_string() == "Hell");
1184 //assert!(r.src_slice(10..12).to_string() == "");
1186 let mut r: Rope = "Hello world!".parse().unwrap();
1188 assert!(r.to_string() == "Helld!");
1190 //assert!(r.src_slice(1..5).to_string() == "ell");
1191 assert!(r.src_slice(9..12).to_string() == "d!");
1195 fn test_insert_copy() {
1196 let mut r: Rope = "Hello world!".parse().unwrap();
1197 r.insert_copy(0, "foo");
1198 assert!(r.to_string() == "fooHello world!");
1199 assert!(r.slice(2..8).to_string() == "oHello");
1201 let mut r: Rope = "Hello world!".parse().unwrap();
1202 r.insert_copy(12, "foo");
1203 assert!(r.to_string() == "Hello world!foo");
1204 assert!(r.slice(2..8).to_string() == "llo wo");
1206 let mut r: Rope = "Hello world!".parse().unwrap();
1207 r.insert_copy(5, "foo");
1208 assert!(r.to_string() == "Hellofoo world!");
1209 assert!(r.slice(2..8).to_string() == "llofoo");
1213 fn test_push_copy() {
1214 let mut r: Rope = "Hello world!".parse().unwrap();
1216 assert!(r.to_string() == "Hello world!foo");
1217 assert!(r.slice(2..8).to_string() == "llo wo");
1221 fn test_insert_replace() {
1222 let mut r: Rope = "hello worl\u{00bb0}!".parse().unwrap();
1223 r.insert_copy(5, "bb");
1224 assert!(r.to_string() == "hellobb worlர!");
1227 r.replace_str(5, "fo\u{00cb0}");
1228 assert!(r.to_string() == "Hellofoರrlர~");
1229 assert!(r.slice(0..10).to_string() == "Hellofoರ");
1230 assert!(r.slice(5..10).to_string() == "foರ");
1231 assert!(r.slice(10..15).to_string() == "rlர");
1233 let expected = "Hellofoರrlர~";
1234 let mut byte_pos = 0;
1235 for ((c, b), e) in r.chars().zip(expected.chars()) {
1237 assert!(b == byte_pos);
1238 byte_pos += e.len_utf8();
1243 fn test_src_insert_remove_col_for_src_loc() {
1244 let mut r: Rope = "hello\n world!".parse().unwrap();
1245 r.src_insert(4, "foo".to_string());
1246 r.src_insert(5, "bar".to_string());
1247 assert!(r.to_string() == "hellfooobar\n world!");
1250 r.src_remove(10, 12);
1251 assert!(r.to_string() == "hefooobar\n wor!");
1253 let expected = "hefooobar\n wor!";
1254 let mut byte_pos = 0;
1255 for ((c, b), e) in r.chars().zip(expected.chars()) {
1257 assert!(b == byte_pos);
1258 byte_pos += e.len_utf8();
1261 let expected = [0, 1, 2, 2, 5, 9, 0, 1, 2, 3, 4, 4, 4];
1263 assert!(r.col_for_src_loc(i) == expected[i]);
1268 fn test_src_insert() {
1269 let mut r: Rope = "Hello world!".parse().unwrap();
1270 r.src_insert(4, "foo".to_string());
1271 r.src_insert(0, "foo".to_string());
1272 r.src_insert(12, "foo".to_string());
1273 assert!(r.to_string() == "fooHellfooo world!foo");
1274 r.src_insert(4, "bar".to_string());
1275 r.src_insert(5, "bar".to_string());
1276 r.src_insert(3, "bar".to_string());
1277 r.src_insert(0, "bar".to_string());
1278 r.src_insert(12, "bar".to_string());
1279 assert!(r.to_string() == "barfooHelbarlbarfooobar world!barfoo");