From e50f2d285fd88913fc34caef6f0ad8232d3b386b Mon Sep 17 00:00:00 2001 From: akr Date: Thu, 27 Jun 2002 06:27:20 +0000 Subject: * lib/prettyprint.rb: re-implemented for incremental output to handle huge data. API is changed a bit. * lib/pp.rb: adapt new pretty printing API. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@2600 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- lib/prettyprint.rb | 567 ++++++++++++++++++++++++++--------------------------- 1 file changed, 282 insertions(+), 285 deletions(-) (limited to 'lib/prettyprint.rb') diff --git a/lib/prettyprint.rb b/lib/prettyprint.rb index b05da3f56f..7c02b3ffa1 100644 --- a/lib/prettyprint.rb +++ b/lib/prettyprint.rb @@ -3,10 +3,10 @@ =begin = PrettyPrint The class implements pretty printing algorithm. -It finds line breaks and nice indentations for grouped structure. +It finds line breaks and nice indentations for grouped structure. By default, the class assumes that primitive elements are strings and -each byte in the strings have single column in width. +each byte in the strings have single column in width. But it can be used for other situasions by giving suitable arguments for some methods: newline object and space generation block for (({PrettyPrint.new})), @@ -17,17 +17,30 @@ text formatting using proportional fonts, multibyte characters which has columns diffrent to number of bytes, non-string formatting, etc. -== class methods ---- PrettyPrint.new([newline]) [{|width| ...}] +== class methods +--- PrettyPrint.new(output[, maxwidth[, newline]]) [{|width| ...}] creates a buffer for pretty printing. + ((|output|)) is a output target. It should have a (({<<})) method + which accepts + the first argument ((|obj|)) of (({PrettyPrint#text})), + the first argument ((|sep|)) of (({PrettyPrint#breakable})), + the first argument ((|newline|)) of (({PrettyPrint.new})), + and + the result of a given block for (({PrettyPrint.new})). + + ((|maxwidth|)) specifies maximum line length. + If it is not specified, 79 is assumed. + However actual outputs may overflow ((|maxwidth|)) if + long non-breakable texts are provided. + ((|newline|)) is used for line breaks. (({"\n"})) is used if it is not specified. The block is used to generate spaces. (({{|width| ' ' * width}})) is used if it is not given. -== methods +== methods --- text(obj[, width]) adds ((|obj|)) as a text of ((|width|)) columns in width. @@ -45,31 +58,19 @@ non-string formatting, etc. character, for example. --- nest(indent) {...} - increases left margin after newline with ((|indent|)) for line breaks added in the block. + increases left margin after newline with ((|indent|)) for line breaks added + in the block. --- group {...} groups line break hints added in the block. The line break hints are all to be breaked or not. ---- fill_group {...} - groups line break hints added in the block. - The each line break hints may be breaked or not differently. - ---- format(out[, width]) - outputs buffered data to ((|out|)). - It tries to restrict the line length to ((|width|)) but it may - overflow. - - If ((|width|)) is not specified, 79 is assumed. - - ((|out|)) must have a method named (({<<})) which accepts - a first argument ((|obj|)) of (({PrettyPrint#text})), - a first argument ((|sep|)) of (({PrettyPrint#breakable})), - a first argument ((|newline|)) of (({PrettyPrint.new})), - and - a result of a given block for (({PrettyPrint.new})). +--- flush + outputs buffered data. == Bugs +* Current API is for minimalists. More useful methods are required. + * Box based formatting? Other (better) model/algorithm? == References @@ -82,180 +83,180 @@ Philip Wadler, A prettier printer, March 1998, =end class PrettyPrint - def initialize(newline="\n", &genspace) + def initialize(output, maxwidth=79, newline="\n", &genspace) + @output = output + @maxwidth = maxwidth @newline = newline @genspace = genspace || lambda {|n| ' ' * n} - @buf = Group.new - @nest = [0] - @stack = [] + + @output_width = 0 + @buffer_width = 0 + @buffer = [] + + root_group = Group.new(0) + @group_stack = [root_group] + @group_queue = GroupQueue.new(root_group) + @indent = 0 end - def text(obj, width=obj.length) - @buf << Text.new(obj, width) + def break_outmost_groups + while @maxwidth < @output_width + @buffer_width + return unless group = @group_queue.deq + until group.breakables.empty? + data = @buffer.shift + @output_width = data.output(@output, @output_width, @newline, @genspace) + @buffer_width -= data.width + end + while !@buffer.empty? && Text === @buffer.first + text = @buffer.shift + @output_width = text.output(@output, @output_width) + @buffer_width -= text.width + end + end end - def breakable(sep=' ', width=sep.length) - @buf << Breakable.new(sep, width, @nest.last, @newline, @genspace) + def text(obj, width=obj.length) + if @buffer.empty? + @output << obj + @output_width += width + else + text = @buffer.last + unless Text === text + text = Text.new + @buffer << text + end + text.add(obj, width) + @buffer_width += width + break_outmost_groups + end end - def nest(indent) - @nest << @nest.last + indent - begin - yield - ensure - @nest.pop + def breakable(sep=' ', width=sep.length) + group = @group_stack.last + if group.break? + flush + @output << @newline + @output << @genspace.call(@indent) + @output_width = @indent + @buffer_width = 0 + else + @buffer << Breakable.new(sep, width, @indent, group) + @buffer_width += width + break_outmost_groups end end def group - g = Group.new - @buf << g - @stack << @buf - @buf = g + group = Group.new(@group_stack.last.depth + 1) + @group_stack.push group + @group_queue.enq group begin yield ensure - @buf = @stack.pop + @group_stack.pop end end - def fill_group - g = FillGroup.new - @buf << g - @stack << @buf - @buf = g + def nest(indent) + @indent += indent begin yield ensure - @buf = @stack.pop + @indent -= indent end end - def format(out, width=79) - tails = [[-1, 0]] - @buf.update_tails(tails, 0) - @buf.multiline_output(out, 0, 0, width) + def flush + @buffer.each {|data| + @output_width = data.output(@output, @output_width, @newline, @genspace) + } + @buffer.clear + @buffer_width = 0 end class Text - def initialize(text, width) - @text = text - @width = width - end - - def update_tails(tails, group) - @tail = tails[-1][1] - tails[-1][1] += @width - end - attr_reader :tail - - def singleline_width - return @width + def initialize + @objs = [] + @width = 0 end + attr_reader :width - def singleline_output(out) - out << @text + def output(out, output_width, newline=nil, genspace=nil) + @objs.each {|obj| out << obj} + output_width + @width end - def multiline_output(out, group, margin, width) - singleline_output(out) - return margin + singleline_width + def add(obj, width) + @objs << obj + @width += width end end class Breakable - def initialize(sep, width, indent, newline, genspace) - @sep = sep + def initialize(sep, width, indent, group) + @obj = sep @width = width @indent = indent - @newline = newline - @genspace = genspace + @group = group + @group.breakables.push self end + attr_reader :obj, :width, :indent - def update_tails(tails, group) - @tail = tails[-1][1] - if group == tails[-1][0] - tails[-2][1] += @width + tails[-1][1] - tails[-1][1] = 0 + def output(out, output_width, newline, genspace) + @group.breakables.shift + if @group.break? + out << newline + out << genspace.call(@indent) + @indent else - tails[-1][1] += @width - tails << [group, 0] + out << @obj + output_width + @width end end - attr_reader :tail - - def singleline_width - return @width - end - - def singleline_output(out) - out << @sep - end - - def multiline_output(out, group, margin, width) - out << @newline - out << @genspace.call(@indent) - return @indent - end end class Group - def initialize - @buf = [] - @singleline_width = nil + def initialize(depth) + @depth = depth + @breakables = [] + @break = false end + attr_reader :depth, :breakables - def <<(obj) - @buf << obj + def break + @break = true end - def update_tails(tails, group) - @tail = tails[-1][1] - len = 0 - @buf.reverse_each {|obj| - obj.update_tails(tails, group + 1) - len += obj.singleline_width - } - @singleline_width = len - while group < tails[-1][0] - tails[-2][1] += tails[-1][1] - tails.pop - end + def break? + @break end - attr_reader :tail + end - def singleline_width - return @singleline_width + class GroupQueue + def initialize(*groups) + @queue = [] + groups.each {|g| enq g} end - def singleline_output(out) - @buf.each {|obj| obj.singleline_output(out)} + def enq(group) + depth = group.depth + @queue << [] until depth < @queue.length + @queue[depth] << group end - def multiline_output(out, group, margin, width) - if margin + singleline_width + @tail <= width - singleline_output(out) - margin += @singleline_width - else - @buf.each {|obj| - margin = obj.multiline_output(out, group + 1, margin, width) + def deq + @queue.each {|gs| + (gs.length-1).downto(0) {|i| + unless gs[i].breakables.empty? + group = gs.slice!(i, 1).first + group.break + return group + end } - end - return margin - end - end - - class FillGroup < Group - def multiline_output(out, group, margin, width) - @buf.each {|obj| - if margin + obj.singleline_width + obj.tail <= width - obj.singleline_output(out) - margin += obj.singleline_width - else - margin = obj.multiline_output(out, group + 1, margin, width) - end + gs.each {|group| group.break} + gs.clear } - return margin + return nil end end end @@ -266,20 +267,6 @@ if __FILE__ == $0 class WadlerExample < RUNIT::TestCase def setup - @hello = PrettyPrint.new - @hello.group { - @hello.group { - @hello.group { - @hello.group { - @hello.text 'hello'; @hello.breakable; @hello.text 'a' - } - @hello.breakable; @hello.text 'b' - } - @hello.breakable; @hello.text 'c' - } - @hello.breakable; @hello.text 'd' - } - @tree = Tree.new("aaaa", Tree.new("bbbbb", Tree.new("ccc"), Tree.new("dd")), Tree.new("eee"), @@ -288,6 +275,22 @@ if __FILE__ == $0 Tree.new("ii"))) end + def hello(width) + out = '' + hello = PrettyPrint.new(out, width) + hello.group { + hello.group { + hello.group { + hello.group { + hello.text 'hello' + hello.breakable; hello.text 'a'} + hello.breakable; hello.text 'b'} + hello.breakable; hello.text 'c'} + hello.breakable; hello.text 'd'} + hello.flush + out + end + def test_hello_00_06 expected = <<'End'.chomp hello @@ -296,8 +299,8 @@ b c d End - @hello.format(out='', 0); assert_equal(expected, out) - @hello.format(out='', 6); assert_equal(expected, out) + assert_equal(expected, hello(0)) + assert_equal(expected, hello(6)) end def test_hello_07_08 @@ -307,8 +310,8 @@ b c d End - @hello.format(out='', 7); assert_equal(expected, out) - @hello.format(out='', 8); assert_equal(expected, out) + assert_equal(expected, hello(7)) + assert_equal(expected, hello(8)) end def test_hello_09_10 @@ -317,8 +320,8 @@ hello a b c d End - @hello.format(out='', 9); assert_equal(expected, out) - @hello.format(out='', 10); assert_equal(expected, out) + out = hello(9); assert_equal(expected, out) + out = hello(10); assert_equal(expected, out) end def test_hello_11_12 @@ -326,20 +329,26 @@ End hello a b c d End - @hello.format(out='', 11); assert_equal(expected, out) - @hello.format(out='', 12); assert_equal(expected, out) + assert_equal(expected, hello(11)) + assert_equal(expected, hello(12)) end def test_hello_13 expected = <<'End'.chomp hello a b c d End - @hello.format(out='', 13); assert_equal(expected, out) + assert_equal(expected, hello(13)) end - def test_tree_00_19 - pp = PrettyPrint.new + def tree(width) + out = '' + pp = PrettyPrint.new(out, width) @tree.show(pp) + pp.flush + out + end + + def test_tree_00_19 expected = <<'End'.chomp aaaa[bbbbb[ccc, dd], @@ -348,13 +357,11 @@ aaaa[bbbbb[ccc, hhh, ii]] End - pp.format(out='', 0); assert_equal(expected, out) - pp.format(out='', 19); assert_equal(expected, out) + assert_equal(expected, tree(0)) + assert_equal(expected, tree(19)) end def test_tree_20_22 - pp = PrettyPrint.new - @tree.show(pp) expected = <<'End'.chomp aaaa[bbbbb[ccc, dd], eee, @@ -362,34 +369,35 @@ aaaa[bbbbb[ccc, dd], hhh, ii]] End - pp.format(out='', 20); assert_equal(expected, out) - pp.format(out='', 22); assert_equal(expected, out) + assert_equal(expected, tree(20)) + assert_equal(expected, tree(22)) end def test_tree_23_43 - pp = PrettyPrint.new - @tree.show(pp) expected = <<'End'.chomp aaaa[bbbbb[ccc, dd], eee, ffff[gg, hhh, ii]] End - pp.format(out='', 23); assert_equal(expected, out) - pp.format(out='', 43); assert_equal(expected, out) + assert_equal(expected, tree(23)) + assert_equal(expected, tree(43)) end def test_tree_44 - pp = PrettyPrint.new - @tree.show(pp) - pp.format(out='', 44) - assert_equal(<<'End'.chomp, out) + assert_equal(<<'End'.chomp, tree(44)) aaaa[bbbbb[ccc, dd], eee, ffff[gg, hhh, ii]] End end - def test_tree_alt_00_18 - pp = PrettyPrint.new + def tree_alt(width) + out = '' + pp = PrettyPrint.new(out, width) @tree.altshow(pp) + pp.flush + out + end + + def test_tree_alt_00_18 expected = <<'End'.chomp aaaa[ bbbbb[ @@ -404,13 +412,11 @@ aaaa[ ] ] End - pp.format(out='', 0); assert_equal(expected, out) - pp.format(out='', 18); assert_equal(expected, out) + assert_equal(expected, tree_alt(0)) + assert_equal(expected, tree_alt(18)) end def test_tree_alt_19_20 - pp = PrettyPrint.new - @tree.altshow(pp) expected = <<'End'.chomp aaaa[ bbbbb[ ccc, dd ], @@ -422,13 +428,11 @@ aaaa[ ] ] End - pp.format(out='', 19); assert_equal(expected, out) - pp.format(out='', 20); assert_equal(expected, out) + assert_equal(expected, tree_alt(19)) + assert_equal(expected, tree_alt(20)) end def test_tree_alt_20_49 - pp = PrettyPrint.new - @tree.altshow(pp) expected = <<'End'.chomp aaaa[ bbbbb[ ccc, dd ], @@ -436,17 +440,15 @@ aaaa[ ffff[ gg, hhh, ii ] ] End - pp.format(out='', 21); assert_equal(expected, out) - pp.format(out='', 49); assert_equal(expected, out) + assert_equal(expected, tree_alt(21)) + assert_equal(expected, tree_alt(49)) end def test_tree_alt_50 - pp = PrettyPrint.new - @tree.altshow(pp) expected = <<'End'.chomp aaaa[ bbbbb[ ccc, dd ], eee, ffff[ gg, hhh, ii ] ] End - pp.format(out='', 50); assert_equal(expected, out) + assert_equal(expected, tree_alt(50)) end class Tree @@ -507,29 +509,32 @@ End end class StrictPrettyExample < RUNIT::TestCase - def setup - @pp = PrettyPrint.new - @pp.group { - @pp.group {@pp.nest(2) { - @pp.text "if"; @pp.breakable; - @pp.group { - @pp.nest(2) { - @pp.group {@pp.text "a"; @pp.breakable; @pp.text "=="} - @pp.breakable; @pp.text "b"}}}} - @pp.breakable - @pp.group {@pp.nest(2) { - @pp.text "then"; @pp.breakable; - @pp.group { - @pp.nest(2) { - @pp.group {@pp.text "a"; @pp.breakable; @pp.text "<<"} - @pp.breakable; @pp.text "2"}}}} - @pp.breakable - @pp.group {@pp.nest(2) { - @pp.text "else"; @pp.breakable; - @pp.group { - @pp.nest(2) { - @pp.group {@pp.text "a"; @pp.breakable; @pp.text "+"} - @pp.breakable; @pp.text "b"}}}}} + def prog(width) + out = '' + pp = PrettyPrint.new(out, width) + pp.group { + pp.group {pp.nest(2) { + pp.text "if"; pp.breakable; + pp.group { + pp.nest(2) { + pp.group {pp.text "a"; pp.breakable; pp.text "=="} + pp.breakable; pp.text "b"}}}} + pp.breakable + pp.group {pp.nest(2) { + pp.text "then"; pp.breakable; + pp.group { + pp.nest(2) { + pp.group {pp.text "a"; pp.breakable; pp.text "<<"} + pp.breakable; pp.text "2"}}}} + pp.breakable + pp.group {pp.nest(2) { + pp.text "else"; pp.breakable; + pp.group { + pp.nest(2) { + pp.group {pp.text "a"; pp.breakable; pp.text "+"} + pp.breakable; pp.text "b"}}}}} + pp.flush + out end def test_00_04 @@ -547,8 +552,8 @@ else + b End - @pp.format(out='', 0); assert_equal(expected, out) - @pp.format(out='', 4); assert_equal(expected, out) + assert_equal(expected, prog(0)) + assert_equal(expected, prog(4)) end def test_05 @@ -565,7 +570,7 @@ else a + b End - @pp.format(out='', 5); assert_equal(expected, out) + assert_equal(expected, prog(5)) end def test_06 @@ -580,7 +585,7 @@ else a + b End - @pp.format(out='', 6); assert_equal(expected, out) + assert_equal(expected, prog(6)) end def test_07 @@ -594,7 +599,7 @@ then else a + b End - @pp.format(out='', 7); assert_equal(expected, out) + assert_equal(expected, prog(7)) end def test_08 @@ -606,7 +611,7 @@ then else a + b End - @pp.format(out='', 8); assert_equal(expected, out) + assert_equal(expected, prog(8)) end def test_09 @@ -617,7 +622,7 @@ then else a + b End - @pp.format(out='', 9); assert_equal(expected, out) + assert_equal(expected, prog(9)) end def test_10 @@ -627,7 +632,7 @@ then a << 2 else a + b End - @pp.format(out='', 10); assert_equal(expected, out) + assert_equal(expected, prog(10)) end def test_11_31 @@ -636,23 +641,24 @@ if a == b then a << 2 else a + b End - @pp.format(out='', 11); assert_equal(expected, out) - @pp.format(out='', 15); assert_equal(expected, out) - @pp.format(out='', 31); assert_equal(expected, out) + assert_equal(expected, prog(11)) + assert_equal(expected, prog(15)) + assert_equal(expected, prog(31)) end def test_32 expected = <<'End'.chomp if a == b then a << 2 else a + b End - @pp.format(out='', 32); assert_equal(expected, out) + assert_equal(expected, prog(32)) end end class TailGroup < RUNIT::TestCase def test_1 - pp = PrettyPrint.new + out = '' + pp = PrettyPrint.new(out, 10) pp.group { pp.group { pp.text "abc" @@ -665,52 +671,56 @@ End pp.text "jkl" } } - pp.format(out='', 10) - assert_equal("abc\ndefghi jkl", out) + pp.flush + assert_equal("abc defghi\njkl", out) end end class NonString < RUNIT::TestCase - def setup - @pp = PrettyPrint.new('newline') {|n| "#{n} spaces"} - @pp.text(3, 3) - @pp.breakable(1, 1) - @pp.text(3, 3) + def format(width) + out = [] + pp = PrettyPrint.new(out, width, 'newline') {|n| "#{n} spaces"} + pp.text(3, 3) + pp.breakable(1, 1) + pp.text(3, 3) + pp.flush + out end def test_6 - @pp.format(out=[], 6) - assert_equal([3, "newline", "0 spaces", 3], out) + assert_equal([3, "newline", "0 spaces", 3], format(6)) end def test_7 - @pp.format(out=[], 7) - assert_equal([3, 1, 3], out) + assert_equal([3, 1, 3], format(7)) end end class Fill < RUNIT::TestCase - def setup - @pp = PrettyPrint.new - @pp.fill_group { - @pp.text 'abc' - @pp.breakable - @pp.text 'def' - @pp.breakable - @pp.text 'ghi' - @pp.breakable - @pp.text 'jkl' - @pp.breakable - @pp.text 'mno' - @pp.breakable - @pp.text 'pqr' - @pp.breakable - @pp.text 'stu' + def format(width) + out = '' + pp = PrettyPrint.new(out, width) + pp.group { + pp.text 'abc' + pp.group { pp.breakable } + pp.text 'def' + pp.group { pp.breakable } + pp.text 'ghi' + pp.group { pp.breakable } + pp.text 'jkl' + pp.group { pp.breakable } + pp.text 'mno' + pp.group { pp.breakable } + pp.text 'pqr' + pp.group { pp.breakable } + pp.text 'stu' } + pp.flush + out end - def test_0_6 + def test_00_06 expected = <<'End'.chomp abc def @@ -720,23 +730,19 @@ mno pqr stu End - @pp.format(out='', 0) - assert_equal(expected, out) - @pp.format(out='', 6) - assert_equal(expected, out) + assert_equal(expected, format(0)) + assert_equal(expected, format(6)) end - def test_7_10 + def test_07_10 expected = <<'End'.chomp abc def ghi jkl mno pqr stu End - @pp.format(out='', 7) - assert_equal(expected, out) - @pp.format(out='', 10) - assert_equal(expected, out) + assert_equal(expected, format(7)) + assert_equal(expected, format(10)) end def test_11_14 @@ -745,10 +751,8 @@ abc def ghi jkl mno pqr stu End - @pp.format(out='', 11) - assert_equal(expected, out) - @pp.format(out='', 14) - assert_equal(expected, out) + assert_equal(expected, format(11)) + assert_equal(expected, format(14)) end def test_15_18 @@ -756,10 +760,8 @@ End abc def ghi jkl mno pqr stu End - @pp.format(out='', 15) - assert_equal(expected, out) - @pp.format(out='', 18) - assert_equal(expected, out) + assert_equal(expected, format(15)) + assert_equal(expected, format(18)) end def test_19_22 @@ -767,10 +769,8 @@ End abc def ghi jkl mno pqr stu End - @pp.format(out='', 19) - assert_equal(expected, out) - @pp.format(out='', 22) - assert_equal(expected, out) + assert_equal(expected, format(19)) + assert_equal(expected, format(22)) end def test_23_26 @@ -778,18 +778,15 @@ End abc def ghi jkl mno pqr stu End - @pp.format(out='', 23) - assert_equal(expected, out) - @pp.format(out='', 26) - assert_equal(expected, out) + assert_equal(expected, format(23)) + assert_equal(expected, format(26)) end def test_27 expected = <<'End'.chomp abc def ghi jkl mno pqr stu End - @pp.format(out='', 27) - assert_equal(expected, out) + assert_equal(expected, format(27)) end end -- cgit v1.2.3