Skip to content
This repository
Newer
Older
100644 897 lines (813 sloc) 18.768 kb
511dc44a »
2008-02-25 initial import
1 # $Id$
2
3 # This class implements a pretty printing algorithm. It finds line breaks and
4 # nice indentations for grouped structure.
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
5 #
511dc44a »
2008-02-25 initial import
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?
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
21 #
511dc44a »
2008-02-25 initial import
22 # == References
23 # Christian Lindig, Strictly Pretty, March 2000,
24 # http://www.st.cs.uni-sb.de/~lindig/papers/#pretty
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
25 #
511dc44a »
2008-02-25 initial import
26 # Philip Wadler, A prettier printer, March 1998,
27 # http://homepages.inf.ed.ac.uk/wadler/topics/language-design.html#prettier
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
28 #
511dc44a »
2008-02-25 initial import
29 # == Author
30 # Tanaka Akira <akr@m17n.org>
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
31 #
511dc44a »
2008-02-25 initial import
32 class PrettyPrint
33
34 # This is a convenience method which is same as follows:
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
35 #
511dc44a »
2008-02-25 initial import
36 # begin
37 # q = PrettyPrint.new(output, maxwidth, newline, &genspace)
38 # ...
39 # q.flush
40 # output
41 # end
8f211620 »
2009-03-02 bring lib up to r22701 (ruby 1.9.1_0 tag). there are build issues usi…
42 #
511dc44a »
2008-02-25 initial import
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.