src/rope.rs

   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.
   4 //
   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.
  10
  11 // TODO
  12 // ----
  13 // docs - mod docs, item docs
  14 // tests
  15 // pull out into its own crate
  16 // impl Default, Extend
  17 // impl DoubleEndedIter and ExactSizeIter for RopeChars
  18 // better allocation
  19 // balancing?
  20
  21 extern crate unicode;
  22 use std::fmt;
  23 use std::ops::Range;
  24 use std::num::{SignedInt, Int};
  25
  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
  30 // whilst searching.
  31 pub struct Rope {
  32     root: Node,
  33     len: usize,
  34     src_len: usize,
  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
  37     // memory
  38     storage: Vec<Vec<u8>>
  39 }
  40
  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.
  46     start: usize,
  47     // The length of text in the last node.
  48     len: usize,
  49 }
  50
  51 // An iterator over the chars in a rope.
  52 pub struct RopeChars<'rope> {
  53     data: RopeSlice<'rope>,
  54     cur_node: usize,
  55     cur_byte: usize,
  56     abs_byte: usize,
  57 }
  58
  59 impl Rope {
  60     // Create an empty rope.
  61     pub fn new() -> Rope {
  62         Rope {
  63             root: Node::empty_inner(),
  64             len: 0,
  65             src_len: 0,
  66             storage: vec![],
  67         }
  68     }
  69
  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
  73
  74         let mut result = Rope::new();
  75         result.insert(0, text);
  76         result.fix_src();
  77         result
  78     }
  79
  80     // When initialising a rope, indicates that the rope is complete wrt the
  81     // source text.
  82     fn fix_src(&mut self) {
  83         self.root.fix_src();
  84         self.src_len = self.len;
  85     }
  86
  87     // Length of the rope.
  88     pub fn len(&self) -> usize {
  89         self.len
  90     }
  91
  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());
  95     }
  96
  97     pub fn insert(&mut self, start: usize, text: String) {
  98         self.insert_inner(start,
  99                           text,
 100                           |this, node| this.root.insert(node, start, start))
 101     }
 102
 103     pub fn src_insert(&mut self, start: usize, text: String) {
 104         self.insert_inner(start,
 105                           text,
 106                           |this, node| this.root.src_insert(node, start, start))
 107     }
 108
 109     fn insert_inner<F>(&mut self,
 110                        start: usize,
 111                        text: String,
 112                        do_insert: F)
 113         where F: Fn(&mut Rope, Box<Node>) -> NodeAction
 114     {
 115         if text.len() == 0 {
 116             return;
 117         }
 118
 119         debug_assert!(start <= self.src_len, "insertion out of bounds of rope");
 120
 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);
 125
 126         match do_insert(self, new_node) {
 127             NodeAction::Change(n, adj) => {
 128                 assert!(adj as usize == len);
 129                 self.root = *n;
 130             }
 131             NodeAction::Adjust(adj) => {
 132                 assert!(adj as usize == len);
 133             }
 134             _ => panic!("Unexpected action")
 135         }
 136         self.len += len;
 137     }
 138
 139     pub fn push(&mut self, text: String) {
 140         let len = self.len();
 141         self.insert(len, text);
 142     }
 143
 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());
 148     }
 149
 150     pub fn remove(&mut self, start: usize, end: usize) {
 151         self.remove_inner(start, end, |this| this.root.remove(start, end, start))
 152     }
 153
 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))
 156     }
 157
 158     fn remove_inner<F>(&mut self,
 159                        start: usize,
 160                        end: usize,
 161                        do_remove: F)
 162         where F: Fn(&mut Rope) -> NodeAction
 163     {
 164         assert!(end >= start);
 165         if start == end {
 166             return;
 167         }
 168
 169         match do_remove(self) {
 170             NodeAction::None => {}
 171             NodeAction::Remove => {
 172                 self.root = Node::empty_inner();
 173                 self.len = 0;
 174             }
 175             NodeAction::Adjust(adj) => self.len = (self.len as isize + adj) as usize,
 176             NodeAction::Change(node, adj) => {
 177                 self.root = *node;
 178                 self.len = (self.len as isize + adj) as usize;
 179             }
 180         }
 181     }
 182
 183     // TODO src_replace
 184     // TODO src_replace_str
 185
 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()[..]);
 196     }
 197
 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);
 201     }
 202
 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
 208         }
 209     }
 210
 211     pub fn slice(&self, Range { start, end }: Range<usize>) -> RopeSlice {
 212         debug_assert!(end > start && start <= self.len && end <= self.len);
 213         if start == end {
 214             return RopeSlice::empty();
 215         }
 216
 217         let mut result = RopeSlice::empty();
 218         self.root.find_slice(start, end, &mut result);
 219         result
 220     }
 221
 222     pub fn full_slice(&self) -> RopeSlice {
 223         self.slice(0..self.len)
 224     }
 225
 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);
 228         if start == end {
 229             return RopeSlice::empty();
 230         }
 231
 232         let mut result = RopeSlice::empty();
 233         self.root.find_src_slice(start, end, &mut result);
 234         result
 235     }
 236
 237     pub fn chars(&self) -> RopeChars {
 238         RopeChars {
 239             data: self.full_slice(),
 240             cur_node: 0,
 241             cur_byte: 0,
 242             abs_byte: 0,
 243         }
 244     }
 245 }
 246
 247 impl<'rope> RopeSlice<'rope> {
 248     fn empty<'r>() -> RopeSlice<'r> {
 249         RopeSlice {
 250             nodes: vec![],
 251             start: 0,
 252             len: 0,
 253         }
 254     }
 255 }
 256
 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() {
 261             return None;
 262         }
 263
 264         let byte = self.abs_byte;
 265         let node = self.data.nodes[self.cur_node];
 266         if self.cur_byte >= node.len {
 267             self.cur_byte = 0;
 268             self.cur_node += 1;
 269             return self.next();
 270         }
 271
 272         let result = self.read_char();
 273         return Some((result, byte));
 274     }
 275 }
 276
 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);
 281         if width == 1 {
 282             return first_byte as char
 283         }
 284         if width == 0 {
 285             panic!("non-utf8 char in rope");
 286         }
 287         let mut buf = [first_byte, 0, 0, 0];
 288         {
 289             let mut start = 1;
 290             while start < width {
 291                 buf[start] = self.read_byte();
 292                 start += 1;
 293             }
 294         }
 295         match ::std::str::from_utf8(&buf[..width]).ok() {
 296             Some(s) => s.char_at(0),
 297             None => panic!("bad chars in rope")
 298         }
 299     }
 300
 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;
 304         self.cur_byte += 1;
 305         self.abs_byte += 1;
 306         let addr = addr as *const u8;
 307         unsafe {
 308             *addr
 309         }
 310     }
 311 }
 312
 313 impl ::std::str::FromStr for Rope {
 314     type Err = ();
 315     fn from_str(text: &str) -> Result<Rope, ()> {
 316         // TODO should split large texts into segments as we insert
 317
 318         let mut result = Rope::new();
 319         result.insert_copy(0, text);
 320         result.fix_src();
 321         Ok(result)
 322     }
 323 }
 324
 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 {
 328             return Ok(());
 329         }
 330
 331         let last_idx = self.nodes.len() - 1;
 332         for (i, n) in self.nodes.iter().enumerate() {
 333             let mut ptr = n.text;
 334             let mut len = n.len;
 335             if i == 0 {
 336                 ptr = (ptr as usize + self.start) as *const u8;
 337                 len -= self.start;
 338             }
 339             if i == last_idx {
 340                 len = self.len;
 341             }
 342             unsafe {
 343                 try!(write!(fmt,
 344                             "{}",
 345                             ::std::str::from_utf8(::std::slice::from_raw_parts(ptr, len)).unwrap()));
 346             }
 347         }
 348         Ok(())
 349     }
 350 }
 351
 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;
 357             let mut len = n.len;
 358             if i == 0 {
 359                 ptr = (ptr as usize + self.start) as *const u8;
 360                 len -= self.start;
 361             } else {
 362                 try!(write!(fmt, "|"));
 363             }
 364             if i == last_idx {
 365                 len = self.len;
 366             }
 367             unsafe {
 368                 try!(write!(fmt,
 369                             "\"{}\"",
 370                             ::std::str::from_utf8(::std::slice::from_raw_parts(ptr, len)).unwrap()));
 371             }
 372         }
 373         Ok(())
 374     }
 375 }
 376
 377 impl fmt::Display for Rope {
 378     fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
 379         write!(fmt, "{}", self.root)
 380     }
 381 }
 382
 383 impl fmt::Debug for Rope {
 384     fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
 385         write!(fmt, "{:?}", self.root)
 386     }
 387 }
 388
 389 impl fmt::Display for Node {
 390     fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
 391         match *self {
 392             Node::InnerNode(Inode { ref left, ref right, .. }) => {
 393                 if let Some(ref left) = *left {
 394                     write!(fmt, "{}", left)
 395                 } else {
 396                     Ok(())
 397                 }.and_then(|_| if let Some(ref right) = *right {
 398                     write!(fmt, "{}", right)
 399                 } else {
 400                     Ok(())
 401                 })
 402             }
 403             Node::LeafNode(Lnode{ ref text, len, .. }) => {
 404                 unsafe {
 405                     write!(fmt,
 406                            "{}",
 407                            ::std::str::from_utf8(::std::slice::from_raw_parts(*text, len)).unwrap())
 408                 }
 409             }
 410         }
 411     }
 412 }
 413
 414 impl fmt::Debug for Node {
 415     fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
 416         match *self {
 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));
 421                 } else {
 422                     try!(write!(fmt, "left: ()"));
 423                 }
 424                 try!(write!(fmt, ", "));
 425                 if let Some(ref right) = *right {
 426                     try!(write!(fmt, "right: {:?}", &**right));
 427                 } else {
 428                     try!(write!(fmt, "right: ()"));
 429                 }
 430                 write!(fmt, "; {})", weight)
 431             }
 432             Node::LeafNode(Lnode{ ref text, len, .. }) => {
 433                 unsafe {
 434                     write!(fmt,
 435                            "(\"{}\"; {})",
 436                            ::std::str::from_utf8(::std::slice::from_raw_parts(*text, len)).unwrap(),
 437                            len)
 438                 }
 439             }
 440         }
 441     }
 442 }
 443
 444 #[derive(Clone, Eq, PartialEq)]
 445 enum Node {
 446     InnerNode(Inode),
 447     LeafNode(Lnode),
 448 }
 449
 450 #[derive(Clone, Eq, PartialEq)]
 451 struct Inode {
 452     weight: usize,
 453     src_weight: usize,
 454     left: Option<Box<Node>>,
 455     right: Option<Box<Node>>,
 456 }
 457
 458 #[derive(Clone, Eq, PartialEq)]
 459 struct Lnode {
 460     text: *const u8,
 461     len: usize,
 462     // text + src_offset = src text (src_offset should always be <= 0)
 463     src_offset: isize,
 464 }
 465
 466 impl Node {
 467     fn empty_inner() -> Node {
 468         Node::InnerNode(Inode {
 469             left: None,
 470             right: None,
 471             weight: 0,
 472             src_weight: 0,
 473         })
 474     }
 475
 476     fn new_inner(left: Option<Box<Node>>,
 477                  right: Option<Box<Node>>,
 478                  weight: usize,
 479                  src_weight: usize)
 480     -> Node {
 481         Node::InnerNode(Inode {
 482             left: left,
 483             right: right,
 484             weight: weight,
 485             src_weight: src_weight,
 486         })
 487     }
 488
 489     fn new_leaf(text: *const u8, len: usize, src_offset: isize) -> Node {
 490         Node::LeafNode(Lnode {
 491             text: text,
 492             len: len,
 493             src_offset: src_offset,
 494         })
 495     }
 496
 497     fn len(&self) -> usize {
 498         match *self {
 499             Node::InnerNode(Inode { weight, ref right, .. }) => {
 500                 match *right {
 501                     Some(ref r) => weight + r.len(),
 502                     None => weight
 503                 }
 504             }
 505             Node::LeafNode(Lnode { len, .. }) => len,
 506         }
 507     }
 508
 509     fn fix_src(&mut self) {
 510         match *self {
 511             Node::InnerNode(ref mut i) => i.fix_src(),
 512             Node::LeafNode(ref mut l) => {
 513                 l.src_offset = 0;
 514             },
 515         }
 516     }
 517
 518     // Most of these methods are just doing dynamic dispatch, TODO use a macro
 519
 520     // precond: start < end
 521     fn remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
 522         match *self {
 523             Node::InnerNode(ref mut i) => i.remove(start, end, src_start),
 524             Node::LeafNode(ref mut l) => l.remove(start, end, src_start),
 525         }
 526     }
 527
 528     fn src_remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
 529         match *self {
 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);
 537                 if end > start {
 538                     l.remove(start as usize, end as usize, src_start as usize)
 539                 } else {
 540                     NodeAction::None
 541                 }
 542             }
 543         }
 544     }
 545
 546     fn insert(&mut self, node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
 547         match *self {
 548             Node::InnerNode(ref mut i) => i.insert(node, start, src_start),
 549             Node::LeafNode(ref mut l) => l.insert(node, start, src_start),
 550         }
 551     }
 552
 553     fn src_insert(&mut self, node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
 554         match *self {
 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)
 562             }
 563         }
 564     }
 565
 566     fn find_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
 567         match *self {
 568             Node::InnerNode(ref i) => i.find_slice(start, end, slice),
 569             Node::LeafNode(ref l) => l.find_slice(start, end, slice),
 570         }
 571     }
 572
 573     fn find_src_slice<'a>(&'a self, start: usize, end: usize, slice: &mut RopeSlice<'a>) {
 574         match *self {
 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);
 581                 if end > start {
 582                     l.find_slice(start as usize, end as usize, slice);
 583                 }
 584             }
 585         }
 586     }
 587
 588     fn replace(&mut self, start: usize, new_str: &str) {
 589         match *self {
 590             Node::InnerNode(ref mut i) => i.replace(start, new_str),
 591             Node::LeafNode(ref mut l) => l.replace(start, new_str),
 592         }
 593     }
 594
 595     fn col_for_src_loc(&self, src_loc: usize) -> Search {
 596         match *self {
 597             Node::InnerNode(ref i) => i.col_for_src_loc(src_loc),
 598             Node::LeafNode(ref l) => l.col_for_src_loc(src_loc),
 599         }
 600     }
 601
 602     fn find_last_char(&self, c: char) -> Option<usize> {
 603         match *self {
 604             Node::InnerNode(ref i) => i.find_last_char(c),
 605             Node::LeafNode(ref l) => l.find_last_char(c),
 606         }
 607     }
 608 }
 609
 610 #[derive(Debug, Clone, Eq, PartialEq)]
 611 enum NodeAction {
 612     None,
 613     Remove,
 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.
 616 }
 617
 618 impl Inode {
 619     fn remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
 620         debug!("Inode::remove: {}, {}, {}", start, end, self.weight);
 621
 622         let left_action = if start <= self.weight {
 623             if let Some(ref mut left) = self.left {
 624                 left.remove(start, end, src_start)
 625             } else {
 626                 panic!();
 627             }
 628         } else {
 629             NodeAction::None
 630         };
 631
 632         let right_action = if end > self.weight {
 633             if let Some(ref mut right) = self.right {
 634                 let start = if start < self.weight {
 635                     0
 636                 } else {
 637                     start - self.weight
 638                 };
 639                 let src_start = if src_start < self.src_weight {
 640                     0
 641                 } else {
 642                     src_start - self.src_weight
 643                 };
 644                 right.remove(start, end - self.weight, src_start)
 645             } else {
 646                 panic!();
 647             }
 648         } else {
 649             NodeAction::None
 650         };
 651
 652
 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;
 657         }
 658
 659         if left_action == NodeAction::Remove {
 660             return NodeAction::Change(self.right.clone().unwrap(),
 661                                       -(self.weight as isize));
 662         }
 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));
 666         }
 667
 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;
 672             total_adj += adj;
 673         }
 674         if let NodeAction::Change(ref n, adj) = right_action {
 675             self.right = Some(n.clone());
 676             total_adj += adj;
 677         }
 678
 679         if let NodeAction::Adjust(adj) = left_action {
 680             self.weight = (self.weight as isize + adj) as usize;
 681             total_adj += adj;
 682         }
 683         if let NodeAction::Adjust(adj) = right_action {
 684             total_adj += adj;
 685         }
 686
 687         return NodeAction::Adjust(total_adj);
 688     }
 689
 690     fn src_remove(&mut self, start: usize, end: usize, src_start: usize) -> NodeAction {
 691         // TODO refactor with remove
 692
 693         debug!("Inode::src_remove: {}, {}, {}/{}", start, end, self.src_weight, self.weight);
 694
 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)
 698             } else {
 699                 panic!();
 700             }
 701         } else {
 702             NodeAction::None
 703         };
 704
 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 {
 708                     0
 709                 } else {
 710                     start - self.src_weight
 711                 };
 712                 let src_start = if src_start < self.src_weight {
 713                     0
 714                 } else {
 715                     src_start - self.src_weight
 716                 };
 717                 right.src_remove(start, end - self.src_weight, src_start)
 718             } else {
 719                 panic!();
 720             }
 721         } else {
 722             NodeAction::None
 723         };
 724
 725
 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;
 730         }
 731
 732         if left_action == NodeAction::Remove {
 733             return NodeAction::Change(self.right.clone().unwrap(),
 734                                       -(self.weight as isize));
 735         }
 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));
 739         }
 740
 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;
 745             total_adj += adj;
 746         }
 747         if let NodeAction::Change(ref n, adj) = right_action {
 748             self.right = Some(n.clone());
 749             total_adj += adj;
 750         }
 751
 752         if let NodeAction::Adjust(adj) = left_action {
 753             self.weight = (self.weight as isize + adj) as usize;
 754             total_adj += adj;
 755         }
 756         if let NodeAction::Adjust(adj) = right_action {
 757             total_adj += adj;
 758         }
 759
 760         return NodeAction::Adjust(total_adj);
 761     }
 762
 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)
 768             } else {
 769                 assert!(self.weight == 0);
 770                 let len = node.len() as isize;
 771                 NodeAction::Change(node, len)
 772             };
 773
 774             match action {
 775                 NodeAction::Change(n, adj) => {
 776                     self.left = Some(n);
 777                     self.weight += adj as usize;
 778                     total_adj += adj;
 779                 }
 780                 NodeAction::Adjust(adj) => {
 781                     self.weight += adj as usize;
 782                     total_adj += adj;
 783                 }
 784                 _ => panic!("Unexpected action"),
 785             }
 786         } else {
 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)
 791             } else {
 792                 let len = node.len() as isize;
 793                 NodeAction::Change(node, len)
 794             };
 795
 796             match action {
 797                 NodeAction::Change(n, adj) => {
 798                     self.right = Some(n);
 799                     total_adj += adj;
 800                 }
 801                 NodeAction::Adjust(adj) => total_adj += adj,
 802                 _ => panic!("Unexpected action"),
 803             }
 804         }
 805
 806         NodeAction::Adjust(total_adj)
 807     }
 808
 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)
 814             } else {
 815                 let len = node.len() as isize;
 816                 NodeAction::Change(node, len)
 817             };
 818
 819             match action {
 820                 NodeAction::Change(n, adj) => {
 821                     self.left = Some(n);
 822                     self.weight += adj as usize;
 823                     total_adj += adj;
 824                 }
 825                 NodeAction::Adjust(adj) => {
 826                     self.weight += adj as usize;
 827                     total_adj += adj;
 828                 }
 829                 _ => panic!("Unexpected action"),
 830             }
 831         } else {
 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)
 836             } else {
 837                 let len = node.len() as isize;
 838                 NodeAction::Change(node, len)
 839             };
 840
 841             match action {
 842                 NodeAction::Change(n, adj) => {
 843                     self.right = Some(n);
 844                     total_adj += adj;
 845                 }
 846                 NodeAction::Adjust(adj) => total_adj += adj,
 847                 _ => panic!("Unexpected action"),
 848             }
 849         }
 850
 851         NodeAction::Adjust(total_adj)
 852     }
 853
 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);
 858         }
 859         if end > self.weight {
 860             let start = if start < self.weight {
 861                 0
 862             } else {
 863                 start - self.weight
 864             };
 865             self.right.as_ref().unwrap().find_slice(start, end - self.weight, slice)
 866         }
 867     }
 868
 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);
 873         }
 874         if end > self.src_weight && self.right.is_some() {
 875             let start = if start < self.src_weight {
 876                 0
 877             } else {
 878                 start - self.src_weight
 879             };
 880             self.right.as_ref().unwrap().find_src_slice(start, end - self.src_weight, slice)
 881         }
 882     }
 883
 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())]);
 890             } else {
 891                 panic!();
 892             }
 893         }
 894         if end > self.weight {
 895             let (start, offset) = if start < self.weight {
 896                 (0, self.weight - start)
 897             } else {
 898                 (start - self.weight, 0)
 899             };
 900             if let Some(ref mut right) = self.right {
 901                 right.replace(start, &new_str[offset..]);
 902             } else {
 903                 panic!();
 904             }
 905         }
 906     }
 907
 908     fn fix_src(&mut self) {
 909         self.src_weight = self.weight;
 910         if let Some(ref mut left) = self.left {
 911             left.fix_src();
 912         }
 913         if let Some(ref mut right) = self.right {
 914             right.fix_src();
 915         }
 916     }
 917
 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))
 923             } else {
 924                 None
 925             }
 926         } else {
 927             None
 928         };
 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') {
 935                             Some(l) => {
 936                                 Search::Done((self.weight - l - 1) + c)
 937                             }
 938                             None => {
 939                                 Search::Continue(c + self.weight)
 940                             }
 941                         }
 942                     }
 943                     result => result,
 944                 }
 945             } else {
 946                 panic!("Can't look up source location");
 947             }
 948         } else {
 949             // TODO don't do it this way
 950             result.unwrap()
 951         }
 952     }
 953
 954     fn find_last_char(&self, c: char) -> Option<usize> {
 955         // TODO use map or something
 956         match self.right {
 957             Some(ref right) => match right.find_last_char(c) {
 958                 Some(x) => return Some(x),
 959                 None => {},
 960             },
 961             None => {}
 962         }
 963         match self.left {
 964             Some(ref left) => match left.find_last_char(c) {
 965                 Some(x) => return Some(x),
 966                 None => {},
 967             },
 968             None => {}
 969         }
 970         None
 971     }
 972 }
 973
 974 impl Lnode {
 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);
 978
 979         if start == 0 && end >= self.len {
 980             // The removal span includes us, remove ourselves.
 981             return NodeAction::Remove;
 982         }
 983
 984         let old_len = self.len;
 985         if start == 0 {
 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);
 992         }
 993
 994         if end >= self.len {
 995             // Truncate the right of the node.
 996             self.len = start;
 997             return NodeAction::Adjust(self.len as isize - old_len as isize);
 998         }
 999
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,
1005                                     old_len - end,
1006                                     self.src_offset + delta)),
1007             start,
1008             src_start);
1009         return NodeAction::Change(box new_node, delta);
1010     }
1011
1012     fn insert(&mut self, mut node: Box<Node>, start: usize, src_start: usize) -> NodeAction {
1013         match node {
1014             box Node::LeafNode(ref mut node) => node.src_offset = self.src_offset,
1015             _ => panic!()
1016         }
1017
1018         let len = node.len();
1019         if start == 0 {
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())),
1023                                                len,
1024                                                0);
1025             return NodeAction::Change(new_node, len as isize)
1026         }
1027
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())),
1031                                                Some(node),
1032                                                self.len,
1033                                                self.len);
1034             return NodeAction::Change(new_node, len as isize)
1035         }
1036
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,
1041                                             self.len - start,
1042                                             self.src_offset));
1043         let new_node = box Node::new_inner(Some(new_left), right, start + len, src_start);
1044
1045         return NodeAction::Change(new_node, len as isize)
1046     }
1047
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");
1051
1052         slice.nodes.push(self);
1053         let mut len = ::std::cmp::min(end, self.len);
1054         if start > 0 {
1055             slice.start = start;
1056             len -= start;
1057         }
1058         slice.len = len;
1059     }
1060
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;
1065         unsafe {
1066             ::std::intrinsics::copy_nonoverlapping_memory(addr, &new_str.as_bytes()[0], new_str.len());
1067         }
1068     }
1069
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
1074             self.len as isize
1075         } else {
1076             (src_loc as isize + self.src_offset)
1077         };
1078
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;
1082         while i >= 0 {
1083             unsafe {
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)
1088                 }
1089             }
1090             i -= 1;
1091         }
1092
1093         let loc = minz(loc) as usize;
1094         debug!("Lnode::col_for_src_loc, return Continue({})", loc);
1095         Search::Continue(loc)
1096     }
1097
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;
1102         while loc >= 0 {
1103             unsafe {
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)
1107                 }
1108             }
1109             loc -= 1;
1110         }
1111
1112         return None
1113     }
1114 }
1115
1116 // The state of searching through a rope.
1117 enum Search {
1118     // TODO comment
1119     Continue(usize),
1120     // TODO comment
1121     Done(usize)
1122 }
1123
1124 fn minz<I: SignedInt>(x: I) -> I {
1125     if x.is_negative() {
1126         return I::zero();
1127     }
1128
1129     x
1130 }
1131
1132 #[cfg(test)]
1133 mod test {
1134     use super::*;
1135     // FIXME is this a Rust bug? Why is minz not imported by the glob import?
1136     use super::minz;
1137
1138     #[test]
1139     fn test_new() {
1140         let r = Rope::new();
1141         assert!(r.len() == 0);
1142         assert!(r.to_string() == "");
1143
1144         let r = Rope::from_string("Hello world!".to_string());
1145         assert!(r.len() == 12);
1146         assert!(r.to_string() == "Hello world!");
1147     }
1148
1149     #[test]
1150     fn test_minz() {
1151         let x: i32 = 0;
1152         assert!(super::minz(x) == 0);
1153         let x: i32 = 42;
1154         assert!(minz(x) == 42);
1155         let x: i32 = -42;
1156         assert!(minz(x) == 0);
1157         let x: isize = 0;
1158         assert!(minz(x) == 0);
1159         let x: isize = 42;
1160         assert!(minz(x) == 42);
1161         let x: isize = -42;
1162         assert!(minz(x) == 0);
1163     }
1164
1165     #[test]
1166     fn test_from_string() {
1167         let r: Rope = "Hello world!".parse().unwrap();
1168         assert!(r.to_string() == "Hello world!");
1169     }
1170
1171     #[test]
1172     fn test_remove() {
1173         let mut r: Rope = "Hello world!".parse().unwrap();
1174         r.remove(0, 10);
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!");
1178
1179         let mut r: Rope = "Hello world!".parse().unwrap();
1180         r.remove(4, 12);
1181         assert!(r.to_string() == "Hell");
1182         // TODO
1183         //assert!(r.src_slice(0..4).to_string() == "Hell");
1184         //assert!(r.src_slice(10..12).to_string() == "");
1185
1186         let mut r: Rope = "Hello world!".parse().unwrap();
1187         r.remove(4, 10);
1188         assert!(r.to_string() == "Helld!");
1189         // TODO
1190         //assert!(r.src_slice(1..5).to_string() == "ell");
1191         assert!(r.src_slice(9..12).to_string() == "d!");
1192     }
1193
1194     #[test]
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");
1200
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");
1205
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");
1210     }
1211
1212     #[test]
1213     fn test_push_copy() {
1214         let mut r: Rope = "Hello world!".parse().unwrap();
1215         r.push_copy("foo");
1216         assert!(r.to_string() == "Hello world!foo");
1217         assert!(r.slice(2..8).to_string() == "llo wo");
1218     }
1219
1220     #[test]
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ர!");
1225         r.replace(0, 'H');
1226         r.replace(15, '~');
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ர");
1232
1233         let expected = "Hellofoರrlர~";
1234         let mut byte_pos = 0;
1235         for ((c, b), e) in r.chars().zip(expected.chars()) {
1236             assert!(c == e);
1237             assert!(b == byte_pos);
1238             byte_pos += e.len_utf8();
1239         }
1240     }
1241
1242     #[test]
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!");
1248
1249         r.src_remove(2, 4);
1250         r.src_remove(10, 12);
1251         assert!(r.to_string() == "hefooobar\n wor!");
1252
1253         let expected = "hefooobar\n wor!";
1254         let mut byte_pos = 0;
1255         for ((c, b), e) in r.chars().zip(expected.chars()) {
1256             assert!(c == e);
1257             assert!(b == byte_pos);
1258             byte_pos += e.len_utf8();
1259         }
1260
1261         let expected = [0, 1, 2, 2, 5, 9, 0, 1, 2, 3, 4, 4, 4];
1262         for i in 0..13 {
1263             assert!(r.col_for_src_loc(i) == expected[i]);
1264         }
1265     }
1266
1267     #[test]
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");
1280     }
1281 }