src/libsyntax/print/pp.rs

   1 // Copyright 2012 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 use core::prelude::*;
  12
  13 use core::cmp;
  14 use core::dvec::DVec;
  15 use core::io::WriterUtil;
  16 use core::io;
  17 use core::str;
  18 use core::vec;
  19
  20 /*
  21  * This pretty-printer is a direct reimplementation of Philip Karlton's
  22  * Mesa pretty-printer, as described in appendix A of
  23  *
  24  *     STAN-CS-79-770: "Pretty Printing", by Derek C. Oppen.
  25  *     Stanford Department of Computer Science, 1979.
  26  *
  27  * The algorithm's aim is to break a stream into as few lines as possible
  28  * while respecting the indentation-consistency requirements of the enclosing
  29  * block, and avoiding breaking at silly places on block boundaries, for
  30  * example, between "x" and ")" in "x)".
  31  *
  32  * I am implementing this algorithm because it comes with 20 pages of
  33  * documentation explaining its theory, and because it addresses the set of
  34  * concerns I've seen other pretty-printers fall down on. Weirdly. Even though
  35  * it's 32 years old. What can I say?
  36  *
  37  * Despite some redundancies and quirks in the way it's implemented in that
  38  * paper, I've opted to keep the implementation here as similar as I can,
  39  * changing only what was blatantly wrong, a typo, or sufficiently
  40  * non-idiomatic rust that it really stuck out.
  41  *
  42  * In particular you'll see a certain amount of churn related to INTEGER vs.
  43  * CARDINAL in the Mesa implementation. Mesa apparently interconverts the two
  44  * somewhat readily? In any case, I've used uint for indices-in-buffers and
  45  * ints for character-sizes-and-indentation-offsets. This respects the need
  46  * for ints to "go negative" while carrying a pending-calculation balance, and
  47  * helps differentiate all the numbers flying around internally (slightly).
  48  *
  49  * I also inverted the indentation arithmetic used in the print stack, since
  50  * the Mesa implementation (somewhat randomly) stores the offset on the print
  51  * stack in terms of margin-col rather than col itself. I store col.
  52  *
  53  * I also implemented a small change in the STRING token, in that I store an
  54  * explicit length for the string. For most tokens this is just the length of
  55  * the accompanying string. But it's necessary to permit it to differ, for
  56  * encoding things that are supposed to "go on their own line" -- certain
  57  * classes of comment and blank-line -- where relying on adjacent
  58  * hardbreak-like BREAK tokens with long blankness indication doesn't actually
  59  * work. To see why, consider when there is a "thing that should be on its own
  60  * line" between two long blocks, say functions. If you put a hardbreak after
  61  * each function (or before each) and the breaking algorithm decides to break
  62  * there anyways (because the functions themselves are long) you wind up with
  63  * extra blank lines. If you don't put hardbreaks you can wind up with the
  64  * "thing which should be on its own line" not getting its own line in the
  65  * rare case of "really small functions" or such. This re-occurs with comments
  66  * and explicit blank lines. So in those cases we use a string with a payload
  67  * we want isolated to a line and an explicit length that's huge, surrounded
  68  * by two zero-length breaks. The algorithm will try its best to fit it on a
  69  * line (which it can't) and so naturally place the content on its own line to
  70  * avoid combining it with other lines and making matters even worse.
  71  */
  72 #[deriving_eq]
  73 pub enum breaks { consistent, inconsistent, }
  74
  75 pub struct break_t {
  76     offset: int,
  77     blank_space: int
  78 }
  79
  80 pub struct begin_t {
  81     offset: int,
  82     breaks: breaks
  83 }
  84
  85 pub enum token {
  86     STRING(@~str, int),
  87     BREAK(break_t),
  88     BEGIN(begin_t),
  89     END,
  90     EOF,
  91 }
  92
  93 pub impl token {
  94     fn is_eof(&self) -> bool {
  95         match *self { EOF => true, _ => false }
  96     }
  97     fn is_hardbreak_tok(&self) -> bool {
  98         match *self {
  99             BREAK(break_t {
 100                 offset: 0,
 101                 blank_space: bs
 102             }) if bs == size_infinity =>
 103                 true,
 104             _ =>
 105                 false
 106         }
 107     }
 108 }
 109
 110 pub fn tok_str(++t: token) -> ~str {
 111     match t {
 112         STRING(s, len) => return fmt!("STR(%s,%d)", *s, len),
 113         BREAK(_) => return ~"BREAK",
 114         BEGIN(_) => return ~"BEGIN",
 115         END => return ~"END",
 116         EOF => return ~"EOF"
 117     }
 118 }
 119
 120 pub fn buf_str(toks: ~[token], szs: ~[int], left: uint, right: uint,
 121                lim: uint) -> ~str {
 122     let n = vec::len(toks);
 123     assert (n == vec::len(szs));
 124     let mut i = left;
 125     let mut L = lim;
 126     let mut s = ~"[";
 127     while i != right && L != 0u {
 128         L -= 1u;
 129         if i != left { s += ~", "; }
 130         s += fmt!("%d=%s", szs[i], tok_str(toks[i]));
 131         i += 1u;
 132         i %= n;
 133     }
 134     s += ~"]";
 135     return s;
 136 }
 137
 138 pub enum print_stack_break { fits, broken(breaks), }
 139
 140 pub struct print_stack_elt {
 141     offset: int,
 142     pbreak: print_stack_break
 143 }
 144
 145 pub const size_infinity: int = 0xffff;
 146
 147 pub fn mk_printer(out: @io::Writer, linewidth: uint) -> @mut Printer {
 148     // Yes 3, it makes the ring buffers big enough to never
 149     // fall behind.
 150     let n: uint = 3 * linewidth;
 151     debug!("mk_printer %u", linewidth);
 152     let mut token: ~[token] = vec::from_elem(n, EOF);
 153     let mut size: ~[int] = vec::from_elem(n, 0);
 154     let mut scan_stack: ~[uint] = vec::from_elem(n, 0u);
 155     @mut Printer {
 156         out: @out,
 157         buf_len: n,
 158         margin: linewidth as int,
 159         space: linewidth as int,
 160         left: 0,
 161         right: 0,
 162         token: token,
 163         size: size,
 164         left_total: 0,
 165         right_total: 0,
 166         scan_stack: scan_stack,
 167         scan_stack_empty: true,
 168         top: 0,
 169         bottom: 0,
 170         print_stack: @mut ~[],
 171         pending_indentation: 0
 172     }
 173 }
 174
 175
 176 /*
 177  * In case you do not have the paper, here is an explanation of what's going
 178  * on.
 179  *
 180  * There is a stream of input tokens flowing through this printer.
 181  *
 182  * The printer buffers up to 3N tokens inside itself, where N is linewidth.
 183  * Yes, linewidth is chars and tokens are multi-char, but in the worst
 184  * case every token worth buffering is 1 char long, so it's ok.
 185  *
 186  * Tokens are STRING, BREAK, and BEGIN/END to delimit blocks.
 187  *
 188  * BEGIN tokens can carry an offset, saying "how far to indent when you break
 189  * inside here", as well as a flag indicating "consistent" or "inconsistent"
 190  * breaking. Consistent breaking means that after the first break, no attempt
 191  * will be made to flow subsequent breaks together onto lines. Inconsistent
 192  * is the opposite. Inconsistent breaking example would be, say:
 193  *
 194  *  foo(hello, there, good, friends)
 195  *
 196  * breaking inconsistently to become
 197  *
 198  *  foo(hello, there
 199  *      good, friends);
 200  *
 201  * whereas a consistent breaking would yield:
 202  *
 203  *  foo(hello,
 204  *      there
 205  *      good,
 206  *      friends);
 207  *
 208  * That is, in the consistent-break blocks we value vertical alignment
 209  * more than the ability to cram stuff onto a line. But in all cases if it
 210  * can make a block a one-liner, it'll do so.
 211  *
 212  * Carrying on with high-level logic:
 213  *
 214  * The buffered tokens go through a ring-buffer, 'tokens'. The 'left' and
 215  * 'right' indices denote the active portion of the ring buffer as well as
 216  * describing hypothetical points-in-the-infinite-stream at most 3N tokens
 217  * apart (i.e. "not wrapped to ring-buffer boundaries"). The paper will switch
 218  * between using 'left' and 'right' terms to denote the wrapepd-to-ring-buffer
 219  * and point-in-infinite-stream senses freely.
 220  *
 221  * There is a parallel ring buffer, 'size', that holds the calculated size of
 222  * each token. Why calculated? Because for BEGIN/END pairs, the "size"
 223  * includes everything betwen the pair. That is, the "size" of BEGIN is
 224  * actually the sum of the sizes of everything between BEGIN and the paired
 225  * END that follows. Since that is arbitrarily far in the future, 'size' is
 226  * being rewritten regularly while the printer runs; in fact most of the
 227  * machinery is here to work out 'size' entries on the fly (and give up when
 228  * they're so obviously over-long that "infinity" is a good enough
 229  * approximation for purposes of line breaking).
 230  *
 231  * The "input side" of the printer is managed as an abstract process called
 232  * SCAN, which uses 'scan_stack', 'scan_stack_empty', 'top' and 'bottom', to
 233  * manage calculating 'size'. SCAN is, in other words, the process of
 234  * calculating 'size' entries.
 235  *
 236  * The "output side" of the printer is managed by an abstract process called
 237  * PRINT, which uses 'print_stack', 'margin' and 'space' to figure out what to
 238  * do with each token/size pair it consumes as it goes. It's trying to consume
 239  * the entire buffered window, but can't output anything until the size is >=
 240  * 0 (sizes are set to negative while they're pending calculation).
 241  *
 242  * So SCAN takeks input and buffers tokens and pending calculations, while
 243  * PRINT gobbles up completed calculations and tokens from the buffer. The
 244  * theory is that the two can never get more than 3N tokens apart, because
 245  * once there's "obviously" too much data to fit on a line, in a size
 246  * calculation, SCAN will write "infinity" to the size and let PRINT consume
 247  * it.
 248  *
 249  * In this implementation (following the paper, again) the SCAN process is
 250  * the method called 'pretty_print', and the 'PRINT' process is the method
 251  * called 'print'.
 252  */
 253 pub struct Printer {
 254     out: @@io::Writer,
 255     buf_len: uint,
 256     margin: int, // width of lines we're constrained to
 257     space: int, // number of spaces left on line
 258     left: uint, // index of left side of input stream
 259     right: uint, // index of right side of input stream
 260     token: ~[token], // ring-buffr stream goes through
 261     size: ~[int], // ring-buffer of calculated sizes
 262     left_total: int, // running size of stream "...left"
 263     right_total: int, // running size of stream "...right"
 264     // pseudo-stack, really a ring too. Holds the
 265     // primary-ring-buffers index of the BEGIN that started the
 266     // current block, possibly with the most recent BREAK after that
 267     // BEGIN (if there is any) on top of it. Stuff is flushed off the
 268     // bottom as it becomes irrelevant due to the primary ring-buffer
 269     // advancing.
 270     scan_stack: ~[uint],
 271     scan_stack_empty: bool, // top==bottom disambiguator
 272     top: uint, // index of top of scan_stack
 273     bottom: uint, // index of bottom of scan_stack
 274     // stack of blocks-in-progress being flushed by print
 275     print_stack: @mut ~[print_stack_elt],
 276     // buffered indentation to avoid writing trailing whitespace
 277     pending_indentation: int,
 278 }
 279
 280 pub impl Printer {
 281     fn last_token(&mut self) -> token { self.token[self.right] }
 282     // be very careful with this!
 283     fn replace_last_token(&mut self, t: token) { self.token[self.right] = t; }
 284     fn pretty_print(&mut self, t: token) {
 285         debug!("pp ~[%u,%u]", self.left, self.right);
 286         match t {
 287           EOF => {
 288             if !self.scan_stack_empty {
 289                 self.check_stack(0);
 290                 self.advance_left(self.token[self.left],
 291                                   self.size[self.left]);
 292             }
 293             self.indent(0);
 294           }
 295           BEGIN(b) => {
 296             if self.scan_stack_empty {
 297                 self.left_total = 1;
 298                 self.right_total = 1;
 299                 self.left = 0u;
 300                 self.right = 0u;
 301             } else { self.advance_right(); }
 302             debug!("pp BEGIN(%d)/buffer ~[%u,%u]",
 303                    b.offset, self.left, self.right);
 304             self.token[self.right] = t;
 305             self.size[self.right] = -self.right_total;
 306             self.scan_push(self.right);
 307           }
 308           END => {
 309             if self.scan_stack_empty {
 310                 debug!("pp END/print ~[%u,%u]", self.left, self.right);
 311                 self.print(t, 0);
 312             } else {
 313                 debug!("pp END/buffer ~[%u,%u]", self.left, self.right);
 314                 self.advance_right();
 315                 self.token[self.right] = t;
 316                 self.size[self.right] = -1;
 317                 self.scan_push(self.right);
 318             }
 319           }
 320           BREAK(b) => {
 321             if self.scan_stack_empty {
 322                 self.left_total = 1;
 323                 self.right_total = 1;
 324                 self.left = 0u;
 325                 self.right = 0u;
 326             } else { self.advance_right(); }
 327             debug!("pp BREAK(%d)/buffer ~[%u,%u]",
 328                    b.offset, self.left, self.right);
 329             self.check_stack(0);
 330             self.scan_push(self.right);
 331             self.token[self.right] = t;
 332             self.size[self.right] = -self.right_total;
 333             self.right_total += b.blank_space;
 334           }
 335           STRING(s, len) => {
 336             if self.scan_stack_empty {
 337                 debug!("pp STRING('%s')/print ~[%u,%u]",
 338                        *s, self.left, self.right);
 339                 self.print(t, len);
 340             } else {
 341                 debug!("pp STRING('%s')/buffer ~[%u,%u]",
 342                        *s, self.left, self.right);
 343                 self.advance_right();
 344                 self.token[self.right] = t;
 345                 self.size[self.right] = len;
 346                 self.right_total += len;
 347                 self.check_stream();
 348             }
 349           }
 350         }
 351     }
 352     fn check_stream(&mut self) {
 353         debug!("check_stream ~[%u, %u] with left_total=%d, right_total=%d",
 354                self.left, self.right, self.left_total, self.right_total);
 355         if self.right_total - self.left_total > self.space {
 356             debug!("scan window is %d, longer than space on line (%d)",
 357                    self.right_total - self.left_total, self.space);
 358             if !self.scan_stack_empty {
 359                 if self.left == self.scan_stack[self.bottom] {
 360                     debug!("setting %u to infinity and popping", self.left);
 361                     self.size[self.scan_pop_bottom()] = size_infinity;
 362                 }
 363             }
 364             self.advance_left(self.token[self.left], self.size[self.left]);
 365             if self.left != self.right { self.check_stream(); }
 366         }
 367     }
 368     fn scan_push(&mut self, x: uint) {
 369         debug!("scan_push %u", x);
 370         if self.scan_stack_empty {
 371             self.scan_stack_empty = false;
 372         } else {
 373             self.top += 1u;
 374             self.top %= self.buf_len;
 375             assert (self.top != self.bottom);
 376         }
 377         self.scan_stack[self.top] = x;
 378     }
 379     fn scan_pop(&mut self) -> uint {
 380         assert (!self.scan_stack_empty);
 381         let x = self.scan_stack[self.top];
 382         if self.top == self.bottom {
 383             self.scan_stack_empty = true;
 384         } else { self.top += self.buf_len - 1u; self.top %= self.buf_len; }
 385         return x;
 386     }
 387     fn scan_top(&mut self) -> uint {
 388         assert (!self.scan_stack_empty);
 389         return self.scan_stack[self.top];
 390     }
 391     fn scan_pop_bottom(&mut self) -> uint {
 392         assert (!self.scan_stack_empty);
 393         let x = self.scan_stack[self.bottom];
 394         if self.top == self.bottom {
 395             self.scan_stack_empty = true;
 396         } else { self.bottom += 1u; self.bottom %= self.buf_len; }
 397         return x;
 398     }
 399     fn advance_right(&mut self) {
 400         self.right += 1u;
 401         self.right %= self.buf_len;
 402         assert (self.right != self.left);
 403     }
 404     fn advance_left(&mut self, ++x: token, L: int) {
 405         debug!("advnce_left ~[%u,%u], sizeof(%u)=%d", self.left, self.right,
 406                self.left, L);
 407         if L >= 0 {
 408             self.print(x, L);
 409             match x {
 410               BREAK(b) => self.left_total += b.blank_space,
 411               STRING(_, len) => { assert (len == L); self.left_total += len; }
 412               _ => ()
 413             }
 414             if self.left != self.right {
 415                 self.left += 1u;
 416                 self.left %= self.buf_len;
 417                 self.advance_left(self.token[self.left],
 418                                   self.size[self.left]);
 419             }
 420         }
 421     }
 422     fn check_stack(&mut self, k: int) {
 423         if !self.scan_stack_empty {
 424             let x = self.scan_top();
 425             match copy self.token[x] {
 426               BEGIN(_) => {
 427                 if k > 0 {
 428                     self.size[self.scan_pop()] = self.size[x] +
 429                         self.right_total;
 430                     self.check_stack(k - 1);
 431                 }
 432               }
 433               END => {
 434                 // paper says + not =, but that makes no sense.
 435                 self.size[self.scan_pop()] = 1;
 436                 self.check_stack(k + 1);
 437               }
 438               _ => {
 439                 self.size[self.scan_pop()] = self.size[x] + self.right_total;
 440                 if k > 0 { self.check_stack(k); }
 441               }
 442             }
 443         }
 444     }
 445     fn print_newline(&mut self, amount: int) {
 446         debug!("NEWLINE %d", amount);
 447         (*self.out).write_str(~"\n");
 448         self.pending_indentation = 0;
 449         self.indent(amount);
 450     }
 451     fn indent(&mut self, amount: int) {
 452         debug!("INDENT %d", amount);
 453         self.pending_indentation += amount;
 454     }
 455     fn get_top(&mut self) -> print_stack_elt {
 456         let n = self.print_stack.len();
 457         if n != 0u {
 458             self.print_stack[n - 1u]
 459         } else {
 460             print_stack_elt {
 461                 offset: 0,
 462                 pbreak: broken(inconsistent)
 463             }
 464         }
 465     }
 466     fn print_str(&mut self, s: ~str) {
 467         while self.pending_indentation > 0 {
 468             (*self.out).write_str(~" ");
 469             self.pending_indentation -= 1;
 470         }
 471         (*self.out).write_str(s);
 472     }
 473     fn print(&mut self, x: token, L: int) {
 474         debug!("print %s %d (remaining line space=%d)", tok_str(x), L,
 475                self.space);
 476         log(debug, buf_str(copy self.token,
 477                            copy self.size,
 478                            self.left,
 479                            self.right,
 480                            6u));
 481         match x {
 482           BEGIN(b) => {
 483             if L > self.space {
 484                 let col = self.margin - self.space + b.offset;
 485                 debug!("print BEGIN -> push broken block at col %d", col);
 486                 self.print_stack.push(print_stack_elt {
 487                     offset: col,
 488                     pbreak: broken(b.breaks)
 489                 });
 490             } else {
 491                 debug!("print BEGIN -> push fitting block");
 492                 self.print_stack.push(print_stack_elt {
 493                     offset: 0,
 494                     pbreak: fits
 495                 });
 496             }
 497           }
 498           END => {
 499             debug!("print END -> pop END");
 500             assert (self.print_stack.len() != 0u);
 501             self.print_stack.pop();
 502           }
 503           BREAK(b) => {
 504             let top = self.get_top();
 505             match top.pbreak {
 506               fits => {
 507                 debug!("print BREAK(%d) in fitting block", b.blank_space);
 508                 self.space -= b.blank_space;
 509                 self.indent(b.blank_space);
 510               }
 511               broken(consistent) => {
 512                 debug!("print BREAK(%d+%d) in consistent block",
 513                        top.offset, b.offset);
 514                 self.print_newline(top.offset + b.offset);
 515                 self.space = self.margin - (top.offset + b.offset);
 516               }
 517               broken(inconsistent) => {
 518                 if L > self.space {
 519                     debug!("print BREAK(%d+%d) w/ newline in inconsistent",
 520                            top.offset, b.offset);
 521                     self.print_newline(top.offset + b.offset);
 522                     self.space = self.margin - (top.offset + b.offset);
 523                 } else {
 524                     debug!("print BREAK(%d) w/o newline in inconsistent",
 525                            b.blank_space);
 526                     self.indent(b.blank_space);
 527                     self.space -= b.blank_space;
 528                 }
 529               }
 530             }
 531           }
 532           STRING(s, len) => {
 533             debug!("print STRING(%s)", *s);
 534             assert (L == len);
 535             // assert L <= space;
 536             self.space -= len;
 537             self.print_str(*s);
 538           }
 539           EOF => {
 540             // EOF should never get here.
 541             fail!();
 542           }
 543         }
 544     }
 545 }
 546
 547 // Convenience functions to talk to the printer.
 548 pub fn box(p: @mut Printer, indent: uint, b: breaks) {
 549     p.pretty_print(BEGIN(begin_t {
 550         offset: indent as int,
 551         breaks: b
 552     }));
 553 }
 554
 555 pub fn ibox(p: @mut Printer, indent: uint) { box(p, indent, inconsistent); }
 556
 557 pub fn cbox(p: @mut Printer, indent: uint) { box(p, indent, consistent); }
 558
 559 pub fn break_offset(p: @mut Printer, n: uint, off: int) {
 560     p.pretty_print(BREAK(break_t {
 561         offset: off,
 562         blank_space: n as int
 563     }));
 564 }
 565
 566 pub fn end(p: @mut Printer) { p.pretty_print(END); }
 567
 568 pub fn eof(p: @mut Printer) { p.pretty_print(EOF); }
 569
 570 pub fn word(p: @mut Printer, wrd: ~str) {
 571     p.pretty_print(STRING(@wrd, str::len(wrd) as int));
 572 }
 573
 574 pub fn huge_word(p: @mut Printer, wrd: ~str) {
 575     p.pretty_print(STRING(@wrd, size_infinity));
 576 }
 577
 578 pub fn zero_word(p: @mut Printer, wrd: ~str) {
 579     p.pretty_print(STRING(@wrd, 0));
 580 }
 581
 582 pub fn spaces(p: @mut Printer, n: uint) { break_offset(p, n, 0); }
 583
 584 pub fn zerobreak(p: @mut Printer) { spaces(p, 0u); }
 585
 586 pub fn space(p: @mut Printer) { spaces(p, 1u); }
 587
 588 pub fn hardbreak(p: @mut Printer) { spaces(p, size_infinity as uint); }
 589
 590 pub fn hardbreak_tok_offset(off: int) -> token {
 591     BREAK(break_t {offset: off, blank_space: size_infinity})
 592 }
 593
 594 pub fn hardbreak_tok() -> token { return hardbreak_tok_offset(0); }
 595
 596
 597 //
 598 // Local Variables:
 599 // mode: rust
 600 // fill-column: 78;
 601 // indent-tabs-mode: nil
 602 // c-basic-offset: 4
 603 // buffer-file-coding-system: utf-8-unix
 604 // End:
 605 //