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