Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 897 lines (813 sloc) 18.775 kb
511dc44 initial import
Laurent Sansonetti authored
1 # $Id$
2
3 # This class implements a pretty printing algorithm. It finds line breaks and
4 # nice indentations for grouped structure.
5 #
6 # By default, the class assumes that primitive elements are strings and each
7 # byte in the strings have single column in width. But it can be used for
8 # other situations by giving suitable arguments for some methods:
9 # * newline object and space generation block for PrettyPrint.new
10 # * optional width argument for PrettyPrint#text
11 # * PrettyPrint#breakable
12 #
13 # There are several candidate uses:
14 # * text formatting using proportional fonts
15 # * multibyte characters which has columns different to number of bytes
16 # * non-string formatting
17 #
18 # == Bugs
19 # * Box based formatting?
20 # * Other (better) model/algorithm?
21 #
22 # == References
23 # Christian Lindig, Strictly Pretty, March 2000,
24 # http://www.st.cs.uni-sb.de/~lindig/papers/#pretty
25 #
26 # Philip Wadler, A prettier printer, March 1998,
27 # http://homepages.inf.ed.ac.uk/wadler/topics/language-design.html#prettier
28 #
29 # == Author
30 # Tanaka Akira <akr@m17n.org>
31 #
32 class PrettyPrint
33
34 # This is a convenience method which is same as follows:
35 #
36 # begin
37 # q = PrettyPrint.new(output, maxwidth, newline, &genspace)
38 # ...
39 # q.flush
40 # output
41 # end
42 #
43 def PrettyPrint.format(output='', maxwidth=79, newline="\n", genspace=lambda {|n| ' ' * n})
44 q = PrettyPrint.new(output, maxwidth, newline, &genspace)
45 yield q
46 q.flush
47 output
48 end
49
50 # This is similar to PrettyPrint::format but the result has no breaks.
51 #
52 # +maxwidth+, +newline+ and +genspace+ are ignored.
53 #
54 # The invocation of +breakable+ in the block doesn't break a line and is
55 # treated as just an invocation of +text+.
56 #
57 def PrettyPrint.singleline_format(output='', maxwidth=nil, newline=nil, genspace=nil)
58 q = SingleLine.new(output)
59 yield q
60 output
61 end
62
63 # Creates a buffer for pretty printing.
64 #
65 # +output+ is an output target. If it is not specified, '' is assumed. It
66 # should have a << method which accepts the first argument +obj+ of
67 # PrettyPrint#text, the first argument +sep+ of PrettyPrint#breakable, the
68 # first argument +newline+ of PrettyPrint.new, and the result of a given
69 # block for PrettyPrint.new.
70 #
71 # +maxwidth+ specifies maximum line length. If it is not specified, 79 is
72 # assumed. However actual outputs may overflow +maxwidth+ if long
73 # non-breakable texts are provided.
74 #
75 # +newline+ is used for line breaks. "\n" is used if it is not specified.
76 #
77 # The block is used to generate spaces. {|width| ' ' * width} is used if it
78 # is not given.
79 #
80 def initialize(output='', maxwidth=79, newline="\n", &genspace)
81 @output = output
82 @maxwidth = maxwidth
83 @newline = newline
84 @genspace = genspace || lambda {|n| ' ' * n}
85
86 @output_width = 0
87 @buffer_width = 0
88 @buffer = []
89
90 root_group = Group.new(0)
91 @group_stack = [root_group]
92 @group_queue = GroupQueue.new(root_group)
93 @indent = 0
94 end
95 attr_reader :output, :maxwidth, :newline, :genspace
96 attr_reader :indent, :group_queue
97
98 def current_group
99 @group_stack.last
100 end
101
102 # first? is a predicate to test the call is a first call to first? with
103 # current group.
104 #
105 # It is useful to format comma separated values as:
106 #
107 # q.group(1, '[', ']') {
108 # xxx.each {|yyy|
109 # unless q.first?
110 # q.text ','
111 # q.breakable
112 # end
113 # ... pretty printing yyy ...
114 # }
115 # }
116 #
117 # first? is obsoleted in 1.8.2.
118 #
119 def first?
120 warn "PrettyPrint#first? is obsoleted at 1.8.2."
121 current_group.first?
122 end
123
124 def break_outmost_groups
125 while @maxwidth < @output_width + @buffer_width
126 return unless group = @group_queue.deq
127 until group.breakables.empty?
128 data = @buffer.shift
129 @output_width = data.output(@output, @output_width)
130 @buffer_width -= data.width
131 end
132 while !@buffer.empty? && Text === @buffer.first
133 text = @buffer.shift
134 @output_width = text.output(@output, @output_width)
135 @buffer_width -= text.width
136 end
137 end
138 end
139
140 # This adds +obj+ as a text of +width+ columns in width.
141 #
142 # If +width+ is not specified, obj.length is used.
143 #
144 def text(obj, width=obj.length)
145 if @buffer.empty?
146 @output << obj
147 @output_width += width
148 else
149 text = @buffer.last
150 unless Text === text
151 text = Text.new
152 @buffer << text
153 end
154 text.add(obj, width)
155 @buffer_width += width
156 break_outmost_groups
157 end
158 end
159
160 def fill_breakable(sep=' ', width=sep.length)
161 group { breakable sep, width }
162 end
163
164 # This tells "you can break a line here if necessary", and a +width+\-column
165 # text +sep+ is inserted if a line is not broken at the point.
166 #
167 # If +sep+ is not specified, " " is used.
168 #
169 # If +width+ is not specified, +sep.length+ is used. You will have to
170 # specify this when +sep+ is a multibyte character, for example.
171 #
172 def breakable(sep=' ', width=sep.length)
173 group = @group_stack.last
174 if group.break?
175 flush
176 @output << @newline
177 @output << @genspace.call(@indent)
178 @output_width = @indent
179 @buffer_width = 0
180 else
181 @buffer << Breakable.new(sep, width, self)
182 @buffer_width += width
183 break_outmost_groups
184 end
185 end
186
187 # Groups line break hints added in the block. The line break hints are all
188 # to be used or not.
189 #
190 # If +indent+ is specified, the method call is regarded as nested by
191 # nest(indent) { ... }.
192 #
193 # If +open_obj+ is specified, <tt>text open_obj, open_width</tt> is called
194 # before grouping. If +close_obj+ is specified, <tt>text close_obj,
195 # close_width</tt> is called after grouping.
196 #
197 def group(indent=0, open_obj='', close_obj='', open_width=open_obj.length, close_width=close_obj.length)
198 text open_obj, open_width
199 group_sub {
200 nest(indent) {
201 yield
202 }
203 }
204 text close_obj, close_width
205 end
206
207 def group_sub
208 group = Group.new(@group_stack.last.depth + 1)
209 @group_stack.push group
210 @group_queue.enq group
211 begin
212 yield
213 ensure
214 @group_stack.pop
215 if group.breakables.empty?
216 @group_queue.delete group
217 end
218 end
219 end
220
221 # Increases left margin after newline with +indent+ for line breaks added in
222 # the block.
223 #
224 def nest(indent)
225 @indent += indent
226 begin
227 yield
228 ensure
229 @indent -= indent
230 end
231 end
232
233 # outputs buffered data.
234 #
235 def flush
236 @buffer.each {|data|
237 @output_width = data.output(@output, @output_width)
238 }
239 @buffer.clear
240 @buffer_width = 0
241 end
242
243 class Text
244 def initialize
245 @objs = []
246 @width = 0
247 end
248 attr_reader :width
249
250 def output(out, output_width)
251 @objs.each {|obj| out << obj}
252 output_width + @width
253 end
254
255 def add(obj, width)
256 @objs << obj
257 @width += width
258 end
259 end
260
261 class Breakable
262 def initialize(sep, width, q)
263 @obj = sep
264 @width = width
265 @pp = q
266 @indent = q.indent
267 @group = q.current_group
268 @group.breakables.push self
269 end
270 attr_reader :obj, :width, :indent
271
272 def output(out, output_width)
273 @group.breakables.shift
274 if @group.break?
275 out << @pp.newline
276 out << @pp.genspace.call(@indent)
277 @indent
278 else
279 @pp.group_queue.delete @group if @group.breakables.empty?
280 out << @obj
281 output_width + @width
282 end
283 end
284 end
285
286 class Group
287 def initialize(depth)
288 @depth = depth
289 @breakables = []
290 @break = false
291 end
292 attr_reader :depth, :breakables
293
294 def break
295 @break = true
296 end
297
298 def break?
299 @break
300 end
301
302 def first?
303 if defined? @first
304 false
305 else
306 @first = false
307 true
308 end
309 end
310 end
311
312 class GroupQueue
313 def initialize(*groups)
314 @queue = []
315 groups.each {|g| enq g}
316 end
317
318 def enq(group)
319 depth = group.depth
320 @queue << [] until depth < @queue.length
321 @queue[depth] << group
322 end
323
324 def deq
325 @queue.each {|gs|
326 (gs.length-1).downto(0) {|i|
327 unless gs[i].breakables.empty?
328 group = gs.slice!(i, 1).first
329 group.break
330 return group
331 end
332 }
333 gs.each {|group| group.break}
334 gs.clear
335 }
336 return nil
337 end
338
339 def delete(group)
340 @queue[group.depth].delete(group)
341 end
342 end
343
344 class SingleLine
345 def initialize(output, maxwidth=nil, newline=nil)
346 @output = output
347 @first = [true]
348 end
349
350 def text(obj, width=nil)
351 @output << obj
352 end
353
354 def breakable(sep=' ', width=nil)
355 @output << sep
356 end
357
358 def nest(indent)
359 yield
360 end
361
362 def group(indent=nil, open_obj='', close_obj='', open_width=nil, close_width=nil)
363 @first.push true
364 @output << open_obj
365 yield
366 @output << close_obj
367 @first.pop
368 end
369
370 def flush
371 end
372
373 def first?
374 result = @first[-1]
375 @first[-1] = false
376 result
377 end
378 end
379 end
380
381 if __FILE__ == $0
382 require 'test/unit'
383
384 class WadlerExample < Test::Unit::TestCase # :nodoc:
385 def setup
386 @tree = Tree.new("aaaa", Tree.new("bbbbb", Tree.new("ccc"),
387 Tree.new("dd")),
388 Tree.new("eee"),
389 Tree.new("ffff", Tree.new("gg"),
390 Tree.new("hhh"),
391 Tree.new("ii")))
392 end
393
394 def hello(width)
395 PrettyPrint.format('', width) {|hello|
396 hello.group {
397 hello.group {
398 hello.group {
399 hello.group {
400 hello.text 'hello'
401 hello.breakable; hello.text 'a'
402 }
403 hello.breakable; hello.text 'b'
404 }
405 hello.breakable; hello.text 'c'
406 }
407 hello.breakable; hello.text 'd'
408 }
409 }
410 end
411
412 def test_hello_00_06
413 expected = <<'End'.chomp
414 hello
415 a
416 b
417 c
418 d
419 End
420 assert_equal(expected, hello(0))
421 assert_equal(expected, hello(6))
422 end
423
424 def test_hello_07_08
425 expected = <<'End'.chomp
426 hello a
427 b
428 c
429 d
430 End
431 assert_equal(expected, hello(7))
432 assert_equal(expected, hello(8))
433 end
434
435 def test_hello_09_10
436 expected = <<'End'.chomp
437 hello a b
438 c
439 d
440 End
441 out = hello(9); assert_equal(expected, out)
442 out = hello(10); assert_equal(expected, out)
443 end
444
445 def test_hello_11_12
446 expected = <<'End'.chomp
447 hello a b c
448 d
449 End
450 assert_equal(expected, hello(11))
451 assert_equal(expected, hello(12))
452 end
453
454 def test_hello_13
455 expected = <<'End'.chomp
456 hello a b c d
457 End
458 assert_equal(expected, hello(13))
459 end
460
461 def tree(width)
462 PrettyPrint.format('', width) {|q| @tree.show(q)}
463 end
464
465 def test_tree_00_19
466 expected = <<'End'.chomp
467 aaaa[bbbbb[ccc,
468 dd],
469 eee,
470 ffff[gg,
471 hhh,
472 ii]]
473 End
474 assert_equal(expected, tree(0))
475 assert_equal(expected, tree(19))
476 end
477
478 def test_tree_20_22
479 expected = <<'End'.chomp
480 aaaa[bbbbb[ccc, dd],
481 eee,
482 ffff[gg,
483 hhh,
484 ii]]
485 End
486 assert_equal(expected, tree(20))
487 assert_equal(expected, tree(22))
488 end
489
490 def test_tree_23_43
491 expected = <<'End'.chomp
492 aaaa[bbbbb[ccc, dd],
493 eee,
494 ffff[gg, hhh, ii]]
495 End
496 assert_equal(expected, tree(23))
497 assert_equal(expected, tree(43))
498 end
499
500 def test_tree_44
501 assert_equal(<<'End'.chomp, tree(44))
502 aaaa[bbbbb[ccc, dd], eee, ffff[gg, hhh, ii]]
503 End
504 end
505
506 def tree_alt(width)
507 PrettyPrint.format('', width) {|q| @tree.altshow(q)}
508 end
509
510 def test_tree_alt_00_18
511 expected = <<'End'.chomp
512 aaaa[
513 bbbbb[
514 ccc,
515 dd
516 ],
517 eee,
518 ffff[
519 gg,
520 hhh,
521 ii
522 ]
523 ]
524 End
525 assert_equal(expected, tree_alt(0))
526 assert_equal(expected, tree_alt(18))
527 end
528
529 def test_tree_alt_19_20
530 expected = <<'End'.chomp
531 aaaa[
532 bbbbb[ ccc, dd ],
533 eee,
534 ffff[
535 gg,
536 hhh,
537 ii
538 ]
539 ]
540 End
541 assert_equal(expected, tree_alt(19))
542 assert_equal(expected, tree_alt(20))
543 end
544
545 def test_tree_alt_20_49
546 expected = <<'End'.chomp
547 aaaa[
548 bbbbb[ ccc, dd ],
549 eee,
550 ffff[ gg, hhh, ii ]
551 ]
552 End
553 assert_equal(expected, tree_alt(21))
554 assert_equal(expected, tree_alt(49))
555 end
556
557 def test_tree_alt_50
558 expected = <<'End'.chomp
559 aaaa[ bbbbb[ ccc, dd ], eee, ffff[ gg, hhh, ii ] ]
560 End
561 assert_equal(expected, tree_alt(50))
562 end
563
564 class Tree # :nodoc:
565 def initialize(string, *children)
566 @string = string
567 @children = children
568 end
569
570 def show(q)
571 q.group {
572 q.text @string
573 q.nest(@string.length) {
574 unless @children.empty?
575 q.text '['
576 q.nest(1) {
577 first = true
578 @children.each {|t|
579 if first
580 first = false
581 else
582 q.text ','
583 q.breakable
584 end
585 t.show(q)
586 }
587 }
588 q.text ']'
589 end
590 }
591 }
592 end
593
594 def altshow(q)
595 q.group {
596 q.text @string
597 unless @children.empty?
598 q.text '['
599 q.nest(2) {
600 q.breakable
601 first = true
602 @children.each {|t|
603 if first
604 first = false
605 else
606 q.text ','
607 q.breakable
608 end
609 t.altshow(q)
610 }
611 }
612 q.breakable
613 q.text ']'
614 end
615 }
616 end
617
618 end
619 end
620
621 class StrictPrettyExample < Test::Unit::TestCase # :nodoc:
622 def prog(width)
623 PrettyPrint.format('', width) {|q|
624 q.group {
625 q.group {q.nest(2) {
626 q.text "if"; q.breakable;
627 q.group {
628 q.nest(2) {
629 q.group {q.text "a"; q.breakable; q.text "=="}
630 q.breakable; q.text "b"}}}}
631 q.breakable
632 q.group {q.nest(2) {
633 q.text "then"; q.breakable;
634 q.group {
635 q.nest(2) {
636 q.group {q.text "a"; q.breakable; q.text "<<"}
637 q.breakable; q.text "2"}}}}
638 q.breakable
639 q.group {q.nest(2) {
640 q.text "else"; q.breakable;
641 q.group {
642 q.nest(2) {
643 q.group {q.text "a"; q.breakable; q.text "+"}
644 q.breakable; q.text "b"}}}}}
645 }
646 end
647
648 def test_00_04
649 expected = <<'End'.chomp
650 if
651 a
652 ==
653 b
654 then
655 a
656 <<
657 2
658 else
659 a
660 +
661 b
662 End
663 assert_equal(expected, prog(0))
664 assert_equal(expected, prog(4))
665 end
666
667 def test_05
668 expected = <<'End'.chomp
669 if
670 a
671 ==
672 b
673 then
674 a
675 <<
676 2
677 else
678 a +
679 b
680 End
681 assert_equal(expected, prog(5))
682 end
683
684 def test_06
685 expected = <<'End'.chomp
686 if
687 a ==
688 b
689 then
690 a <<
691 2
692 else
693 a +
694 b
695 End
696 assert_equal(expected, prog(6))
697 end
698
699 def test_07
700 expected = <<'End'.chomp
701 if
702 a ==
703 b
704 then
705 a <<
706 2
707 else
708 a + b
709 End
710 assert_equal(expected, prog(7))
711 end
712
713 def test_08
714 expected = <<'End'.chomp
715 if
716 a == b
717 then
718 a << 2
719 else
720 a + b
721 End
722 assert_equal(expected, prog(8))
723 end
724
725 def test_09
726 expected = <<'End'.chomp
727 if a == b
728 then
729 a << 2
730 else
731 a + b
732 End
733 assert_equal(expected, prog(9))
734 end
735
736 def test_10
737 expected = <<'End'.chomp
738 if a == b
739 then
740 a << 2
741 else a + b
742 End
743 assert_equal(expected, prog(10))
744 end
745
746 def test_11_31
747 expected = <<'End'.chomp
748 if a == b
749 then a << 2
750 else a + b
751 End
752 assert_equal(expected, prog(11))
753 assert_equal(expected, prog(15))
754 assert_equal(expected, prog(31))
755 end
756
757 def test_32
758 expected = <<'End'.chomp
759 if a == b then a << 2 else a + b
760 End
761 assert_equal(expected, prog(32))
762 end
763
764 end
765
766 class TailGroup < Test::Unit::TestCase # :nodoc:
767 def test_1
768 out = PrettyPrint.format('', 10) {|q|
769 q.group {
770 q.group {
771 q.text "abc"
772 q.breakable
773 q.text "def"
774 }
775 q.group {
776 q.text "ghi"
777 q.breakable
778 q.text "jkl"
779 }
780 }
781 }
782 assert_equal("abc defghi\njkl", out)
783 end
784 end
785
786 class NonString < Test::Unit::TestCase # :nodoc:
787 def format(width)
788 PrettyPrint.format([], width, 'newline', lambda {|n| "#{n} spaces"}) {|q|
789 q.text(3, 3)
790 q.breakable(1, 1)
791 q.text(3, 3)
792 }
793 end
794
795 def test_6
796 assert_equal([3, "newline", "0 spaces", 3], format(6))
797 end
798
799 def test_7
800 assert_equal([3, 1, 3], format(7))
801 end
802
803 end
804
805 class Fill < Test::Unit::TestCase # :nodoc:
806 def format(width)
807 PrettyPrint.format('', width) {|q|
808 q.group {
809 q.text 'abc'
810 q.fill_breakable
811 q.text 'def'
812 q.fill_breakable
813 q.text 'ghi'
814 q.fill_breakable
815 q.text 'jkl'
816 q.fill_breakable
817 q.text 'mno'
818 q.fill_breakable
819 q.text 'pqr'
820 q.fill_breakable
821 q.text 'stu'
822 }
823 }
824 end
825
826 def test_00_06
827 expected = <<'End'.chomp
828 abc
829 def
830 ghi
831 jkl
832 mno
833 pqr
834 stu
835 End
836 assert_equal(expected, format(0))
837 assert_equal(expected, format(6))
838 end
839
840 def test_07_10
841 expected = <<'End'.chomp
842 abc def
843 ghi jkl
844 mno pqr
845 stu
846 End
847 assert_equal(expected, format(7))
848 assert_equal(expected, format(10))
849 end
850
851 def test_11_14
852 expected = <<'End'.chomp
853 abc def ghi
854 jkl mno pqr
855 stu
856 End
857 assert_equal(expected, format(11))
858 assert_equal(expected, format(14))
859 end
860
861 def test_15_18
862 expected = <<'End'.chomp
863 abc def ghi jkl
864 mno pqr stu
865 End
866 assert_equal(expected, format(15))
867 assert_equal(expected, format(18))
868 end
869
870 def test_19_22
871 expected = <<'End'.chomp
872 abc def ghi jkl mno
873 pqr stu
874 End
875 assert_equal(expected, format(19))
876 assert_equal(expected, format(22))
877 end
878
879 def test_23_26
880 expected = <<'End'.chomp
881 abc def ghi jkl mno pqr
882 stu
883 End
884 assert_equal(expected, format(23))
885 assert_equal(expected, format(26))
886 end
887
888 def test_27
889 expected = <<'End'.chomp
890 abc def ghi jkl mno pqr stu
891 End
892 assert_equal(expected, format(27))
893 end
894
895 end
896 end
Something went wrong with that request. Please try again.