Port a Library (#64)


#1

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Twice this week, I’ve gone looking for the Ruby equivalent to a simple
Perl
module and had trouble finding what I was after. Both times I’ve peeked
inside
the source and been surprised at how trivial the operations are. “I
could port
that in no time,” I thought. This quiz is my thinly disguised attempt
to pass
my homework on to others. :slight_smile:

Seriously, this quiz is not intended to be a lot of work. Don’t
underestimate
the power of a simple library. (See the “Rethinking Memoization” thread
where
we are trying to improve a very helpful library that is literally 10
lines of
code, in one of the forms presented.)

Given all that, this is a build-it-yourself Ruby Q… Most of us are
familiar
with another language. Go into their libraries and find something you
like,
that is also simple, and port the library to Ruby. (You might want to
search
the RAA and RubyForge first, just to make sure someone hasn’t done
similar work
already.) If a library is over 200 lines, forget it. This one is for
the
little guys!

If you’ll allow a brief aside here, it can be interesting to consider
what the
word “port” means. Obviously, the goal of this is to build a library
that does
the same things for Ruby. Don’t think that means you should copy every
method,
verbatim though. If you don’t think a method is needed, leave it out.
See a
better way to do something, use your way. Most important though,
remember to
Rubyize the interface. It’s fine to port your favorite Java library,
but Ruby
programmers don’t want to call methodsNamedLikeThis(). Watch for
chances to use
blocks and jump on them when they lead to a better experience. Just
remember
the adage, “If it ain’t broke, don’t fix it.”

A few more details: Please tell us what your library does and show an
example
of simple usage in your submission email. Be kind to your quiz
summarizer. :wink:
Also, please credit the original library and author who worked so hard
to give
you something cool to play with!

Now, if you have no idea what to port, here are two suggestions.
(Please feel
free to post other suggestions to Ruby T… These are not spoilers!)

File::ReadBackwards

This is a Perl module (by Uri Guttman) for reading a file in reverse,
line-by-line. This can often be helpful for things like log files,
where the
interesting information is usually at the end.

Don’t worry about the Perl interface on this one, copy Ruby’s File
instead.
Heck, all I really want is a foreach() iterator. Anything else is
extra.

This module is so well commented, you should be able to understand how
it works,
even if you aren’t familiar with Perl. Here’s a link straight to the
source:

http://search.cpan.org/src/URI/File-ReadBackwards-1.04/ReadBackwards.pm

WWW::RobotRules

This is another Perl module (by Gisle Aas) and it is actually over the
200 line
limit. Trust me though, it doesn’t need to be. :slight_smile:

The idea here is that many web sites provide a /robots.txt file, telling
spider
programs which pages they should not visit. This module gives you a way
to
parse these rules and make queries about what you are allowed to visit.
You can
learn all about the interface and even the file format of /robots.txt
at:

http://search.cpan.org/~gaas/libwww-perl-5.805/lib/WWW/RobotRules.pm

#2

(By my calculations it’s gone 48 hours now? Hope so, anyway…)

I did “Ruby Murray” - a port of Johan Lodin’s Sub::Curry from Perl. It’s
not so useful in Ruby I guess but it’s fun and pretty flexible. Below is
the uncommented version, but since I can’t sleep when I have
undocumented code I did Rdoc it and make the commented version available
at http://roscopeco.co.uk/code/ruby-quiz-entries/64/ .

There’s also a translation of the Sub::Curry cookbook I used to drive
development a bit. The original Sub::Curry can be found at
http://search.cpan.org/~lodin/Sub-Curry-0.8/lib/Sub/Curry.pm and the
cookbook is at
http://search.cpan.org/~lodin/Sub-Curry-0.8/lib/Sub/Curry/Cookbook.pod .

Ruby Murray is about a hundred lines for the main Curry class, another
forty or so for convenience methods and the like, and about 70 lines of
tests. It could be smaller but I like (reasonably) readable code and the
TDD makes it more verbose I guess…

Here’s a couple of quick examples. See the cookbook and tests (either
below or in the Rdoc linked above if formatting is broken) for more.

Just curry a method:

c = "string".method(:slice).curry(Curry::HOLE,2)
c.call(0)
# => "st"
c.call(2)
# => "ri"

Swallow arguments:

curry = lambda { |*args| args }.curry(1,Curry::ANTISPICE,3)
curry.call(2,5)
# => [1,3,5]

Do some mad curry to curry stuff:

curry = [10,20,30].method(:inject).curry(Curry::HOLE)
curry.call(0) { |s,i| s + i }
# => 60

mult_sum = lambda do |sum, i, mult|
  sum + (i * mult)
end.curry(Curry::BLACKHOLE, Curry::HOLE)

double_sum = mult_sum.new(Curry::BLACKHOLE, Curry::WHITEHOLE, 2)
triple_sum = mult_sum.new(Curry::BLACKHOLE, Curry::WHITEHOLE, 3)

curry.call(0, &double_sum)
# => 120

curry.call(0, &triple_sum)
# => 180

Obviously it’s completely different from the Perl original under the
hood but I tried to make it familiar enough while making good use of
Ruby.

There’s a few other ideas I’d like to have tried but I didn’t want to
get too far into it ;). One advantage this version has over Perl’s is
that it’s easy to make custom Spice argument types (HOLE, BLACKHOLE,
etc) so maybe there’s some scope for hacking around in there…

=====[CURRY.RB]=====
require ‘singleton’

class Curry
WHITEHOLE = Object.new
ANTIHOLE = Object.new
def WHITEHOLE.inspect #:nodoc:
“”
end
def ANTIHOLE.inspect #:nodoc:
“”
end

class SpiceArg
def initialize(name)
@name = name
end
def spice_arg(args_remain)
raise NoMethodError, “Abstract method”
end
def inspect
“<#{@name}>”
end
end

class HoleArg < SpiceArg #:nodoc: all
include Singleton
def initialize; super(“HOLE”); end
def spice_arg(args_remain)
a = args_remain.shift
if a == ANTIHOLE
[]
else
[a]
end
end
end

class BlackHoleArg < SpiceArg #:nodoc: all
include Singleton
def initialize; super(“BLACKHOLE”); end
def spice_arg(args_remain)
if idx = args_remain.index(WHITEHOLE)
args_remain.slice!(0…idx)[0…-2]
else
args_remain.slice!(0…args_remain.length)
end
end
end

class AntiSpiceArg < SpiceArg #:nodoc: all
include Singleton
def initialize; super(“ANTISPICE”); end
def spice_arg(args_remain)
args_remain.shift
[]
end
end

HOLE = HoleArg.instance
BLACKHOLE = BlackHoleArg.instance
ANTISPICE = AntiSpiceArg.instance

attr_reader :spice
attr_reader :uncurried

def initialize(*spice, &block)
block = block || (spice.shift if spice.first.respond_to?(:call))
raise ArgumentError, “No block supplied” unless block
@spice, @uncurried = spice, block
end

def call(*args, &blk)
@uncurried.call(*call_spice(args), &blk)
end

This would be an alias, but it’s documented along with call and

I couldn’t :nodoc: an alias - how do we do that ?

def # :nodoc:
call(*args)
end

def new(*spice)
Curry.new(*merge_spice(spice), &@uncurried)
end

def to_proc
@extern_proc ||= method(:call).to_proc
end

private

def merge_spice(spice)
largs = spice.dup

res = @spice.inject([]) do |res, sparg|
  if sparg.is_a?(SpiceArg) && !largs.empty?
    res + sparg.spice_arg(largs)
  else
    res << sparg
  end
end

res + largs

end

def call_spice(args)
sp = merge_spice(args)
sp.map do |a|
if a.is_a? SpiceArg
nil
else
a
end
end
end
end

Undocumented alias for Perl familiarity

module Sub #:nodoc: all
Curry = ::Curry
end

module Curriable
def curry(*spice)
Curry.new(self, *spice)
end
end

unless defined? NO_CORE_CURRY
NO_CORE_CURRY = (ENV[‘NO_CORE_CURRY’] || $SAFE > 3)
end

unless NO_CORE_CURRY
class Proc
include Curriable
end

class Method
include Curriable
end
end

if $0 == FILE || (TEST_CURRY if defined? TEST_CURRY)
require ‘test/unit’

class TestCurry < Test::Unit::TestCase
def test_fixed_args
curry = Curry.new(1,2,3) { |a,b,c| [a,b,c] }
assert_equal [1,2,3], curry.call
end

def test_fixed_array_args
  curry = Curry.new([1],[2,3]) { |*args| args }
  assert_equal [[1],[2,3]], curry.call
end

def test_hole
  curry = Curry.new(1,Curry::HOLE,3) { |a,b,c| [a,b,c] }
  assert_equal [1,nil,3], curry.call
  assert_equal [1,2,3], curry.call(2)

  curry = Curry.new(1,Curry::HOLE,3,Curry::HOLE) { |*args| args }
  assert_equal [1,2,3,4], curry.call(2,4)
  assert_equal [1,2,3,4,5,6], curry.call(2,4,5,6)
  assert_equal [1,[2,'two'],3,[4,0],[[14]]],
               curry.call([2,'two'],[4,0],[[14]])

end

def test_antihole
  curry = Curry.new(1,Curry::HOLE,3) { |*args| args }
  assert_equal [1,3], curry.call(Curry::ANTIHOLE)

  curry = Curry.new(1,Curry::HOLE,3,Curry::HOLE,4) { |*args| args }
  assert_equal [1,2,3,4,5], curry.call(2,Curry::ANTIHOLE,5)
end

def test_antispice
  curry = Curry.new(1,Curry::ANTISPICE,3,Curry::HOLE,4) { |*args|

args }
assert_equal [1,3,4,5], curry.call(2,Curry::ANTIHOLE,5)
end

def test_black_hole
  curry = Curry.new(1,Curry::BLACKHOLE) { |*args| args }
  assert_equal [1,2,3], curry.call(2,3)

  curry = Curry.new(1,Curry::BLACKHOLE,3,4) { |*args| args }
  assert_equal [1,2,10,3,4], curry.call(2,10)
end

def test_white_hole
  curry = Curry.new(1,Curry::BLACKHOLE,3,Curry::HOLE,5) { |*args|

args }
assert_equal [1,2,3,7,5,8,9], curry.call(2,Curry::WHITEHOLE,7,8,9)
assert_equal [1,10,20,3,nil,5], curry.call(10,20,Curry::WHITEHOLE)
assert_equal [1,10,20,25,3,4,5],
curry.call(10,20,25,Curry::WHITEHOLE,4)

  curry =

Curry.new(1,Curry::BLACKHOLE,6,Curry::HOLE,3,4,Curry::BLACKHOLE,5) { |
*args| args }
assert_equal [1,10,20,25,6,40,3,4,50,60,5],
curry.call(10,20,25,Curry::WHITEHOLE,40,50,60)
end

def test_curry_from_curry
  curry =

Curry.new(1,Curry::BLACKHOLE,6,Curry::HOLE,3,4,Curry::BLACKHOLE,5) { |
*args| args }
curry = curry.new(Curry::HOLE,Curry::WHITEHOLE,8,9,10)
assert_equal [1,Curry::HOLE,6,8,3,4,9,10,5], curry.spice

  curry = curry.new(Curry::HOLE, 4, Curry::BLACKHOLE)
  assert_equal [1,Curry::HOLE,6,8,3,4,9,10,5,4,Curry::BLACKHOLE],

curry.spice

  curry = curry.new(Curry::ANTIHOLE)
  assert_equal [1,6,8,3,4,9,10,5,4,Curry::BLACKHOLE], curry.spice

  curry = curry.new(3,Curry::BLACKHOLE,Curry::WHITEHOLE,0)
  assert_equal [1,6,8,3,4,9,10,5,4,3,Curry::BLACKHOLE,0],

curry.spice
assert_equal [1,6,8,3,4,9,10,5,4,3,2,1,0], curry.call(2,1)
end

def test_cant_block_to_curried_block
  a = Curry.new(1,2) { |*args| args }

  assert_equal [1,2,3], a.call(3) { |b| }
end

def test_curry_proc
  a = [1,2,3,4,5]
  c = Curry.new(*a) { |*args| args * 2 }
  assert_equal [1,2,3,4,5,1,2,3,4,5], c.call

  if NO_CORE_CURRY
    warn "Skipping Proc extension test"
  else
    c = lambda { |*args| args * 2 }.curry(*a)
    assert_equal [1,2,3,4,5,1,2,3,4,5], c.call
  end
end

def test_curry_method
  a = [1,2,3,4,5]
  injsum = Curry.new(a.method(:inject),0)
  assert_equal 15, injsum.call { |s,i| s + i }

  if NO_CORE_CURRY
    warn "Skipping Method extension test"
  else
    injsum = a.method(:inject).curry(0)
    assert_equal 15, injsum.call { |s,i| s + i }
  end
end

def test_curry_to_proc
  curry = Curry.new(Curry::HOLE, Curry::HOLE, 'thou') { |ary,i,msg|

ary << “#{i} #{msg}” }
assert_equal [“1 thou”, “2 thou”, “3 thou”],
[1,2,3].inject([],&curry)
end

def test_alt_bits
  curry = Curry.new(Curry::BLACKHOLE, 'too', 'true') { |one, two,

*rest| [one, two, rest] }
assert_equal [1,2,[‘too’,‘true’]], curry[1,2]
end

def test_perlish
  s = "str"
  s = Sub::Curry.new(s.method(:+), "ing")
  assert_equal "string", s.call
end

end

if ARGV.member?(’–doc’) || !File.exist?(‘doc’)
ARGV.reject! { |a| a == ‘–doc’ }
system(“rdoc #{FILE} #{‘currybook.rdoc’ if
File.exists?(‘currybook.rdoc’)} --main Curry”)
end
end

END


#3

There aren’t any particular libraries I’ve used anytime recently…
all my work is in-house code. But I took a quick glance over CPAN for
something relatively small and simple… the latter because I stopped
coding in Perl years ago and don’t remember all the syntax very well,
especially the stuff that has been added for objects.

In any case, I found a simple library called Trampoline by Steven
Lembark which allows you to create an object but delay actual
construction… which is useful to have something with expensive
construction cost ready to go but not actually constructed until used.

Below I provide a really basic implementation that is probably not
rock-solid and could probably be done better … I’m still such a
n00b, especially when it comes to metaclasses (or eigenclasses, or
whatever they want to be called this week). It also doesn’t do
everything the Perl lib did, just what I found useful and could
understand.

Anyway, here’s the code (trampoline.rb), with a couple of use examples
at the bottom.

module Trampoline

Instance methods

class Bounce
def initialize(cons, klass, *args)
@klass, @cons, @args = klass, cons, args
end

  def method_missing(method, *args)
     @obj = @klass.send(@cons, *@args) unless @obj
     @obj.send(method, *args)
  end

end

Class methods

class << Bounce
alias_method :old_new, :new

  def new(*args)
     old_new(:new, *args)
  end

  def method_missing(method, *args)
     old_new(method, *args)
  end

end
end

And now, example use. Obviously, this class is not in need of delayed
construction; just using it as an example.

require ‘trampoline’
class Logger
def initialize(prefix)
puts ‘Constructing Logger…’
@prefix = prefix
end

def Logger.make(prefix)
Logger.new(prefix)
end

def log(msg)
puts “#{@prefix}: #{msg}”
end
end

puts “start”
errors = Trampoline::Bounce.new(Logger, ‘ERROR’)
puts “made bouncer, about to log message”
errors.log(‘Hello, world!’)
puts “about to log second message”
errors.log(‘Goodbye, world!’)
puts “message logged”

This is really the same, but eventually calls Logger.make to

construct.
puts “start”
warns = Trampoline::Bounce.make(Logger, ‘WARNING’)
puts “made bouncer, about to log message”
warns.log(‘Hello, world!’)
puts “about to log second message”
warns.log(‘Goodbye, world!’)
puts “message logged”

Output from the example code:

start
made bouncer, about to log message
Constructing Logger…
ERROR: Hello, world!
about to log second message
ERROR: Goodbye, world!
message logged
start
made bouncer, about to log message
Constructing Logger…
WARNING: Hello, world!
about to log second message
WARNING: Goodbye, world!
message logged


#4

On Jan 27, 2006, at 7:52 AM, Ruby Q. wrote:

Seriously, this quiz is not intended to be a lot of work.

I just know people aren’t going to believe me on this, so here’s my
attempt to put my code where my mouth is. This is my port of
File::ReadBackwards. Translating the heart of the algorithm took me
well under an hour, though I did spend a bit more time adding
interface methods and documentation.

James Edward G. II

#!/usr/local/bin/ruby -w

elif.rb

Created by James Edward G. II on 2006-01-28.

Copyright 2006 Gray Productions. All rights reserved.

A File-like object for reading lines from a disk file in reverse

order. See

Elif::new and Elif#gets for details. All other methods are just

interface

conveniences.

Based on Perl’s File::ReadBackwards module, by Uri Guttman.

class Elif

The size of the reads we will use to add to the line buffer.

MAX_READ_SIZE = 1 << 10 # 1024

Works just line File::foreach, save that the lines come in

reverse order.
def self.foreach( name, sep_string = $/ )
open(name) do |file|
while line = file.gets(sep_string)
yield line
end
end
end

Works just line File::open.

def self.open( *args )
file = new(*args)
if block_given?
begin
yield file
ensure
file.close
end
else
file
end
end

Works just line File::readlines, save that line Array will be in

reverse order.

def self.readlines( name, sep_string = $/ )
open(name) { |file| file.readlines(sep_string) }
end

The first half of the Elif algorithm (to read file lines in

reverse order).

This creates a new Elif object, shifts the read pointer to the

end of the

file, and prepares a buffer to hold read lines until they can be

returned.

This method also sets the @read_size to the remainer of

File#size

and +MAX_READ_SIZE+ for the first read.

Technically +args+ are delegated straight to File#new, but you

must open the

File object for reading for it to work with this algorithm.

def initialize( *args )
# Delegate to File::new and move to the end of the file.
@file = File.new(*args)
@file.seek(0, IO::SEEK_END)

 # Record where we are.
 @current_pos = @file.pos

 # Get the size of the next of the first read, the dangling bit

of the file.
@read_size = @file.pos % MAX_READ_SIZE
@read_size = MAX_READ_SIZE if @read_size.zero?

 # A buffer to hold lines read, but not yet returned.
 @line_buffer = Array.new

end

The second half on the Elif algorthim (see Elif::new). This

method returns

the next line of the File, working from the end to the beginning

in reverse

line order.

It works by moving the file pointer backwords +MAX_READ_SIZE+ at

a time,

storing seen lines in @line_buffer. Once the buffer

contains at

least two lines (ensuring we have seen on full line) or the file

pointer

reaches the head of the File, the last line from the buffer is

returned.

When the buffer is exhausted, this will throw +nil+ (from the

empty Array).

def gets( sep_string = $/ )
#
# If we have more than one line in the buffer or we have reached
the
# beginning of the file, send the last line in the buffer to the
caller.
# (This may be +nil+, if the buffer has been exhausted.)
#
return @line_buffer.pop if @line_buffer.size > 2 or
@current_pos.zero?

 #
 # If we made it this far, we need to read more data to try and

find the
# beginning of a line or the beginning of the file. Move the
file pointer
# back a step, to give us new bytes to read.
#
@current_pos -= @read_size
@file.seek(@current_pos, IO::SEEK_SET)

 #
 # Read more bytes and prepend them to the first (likely partial)

line in the
# buffer.
#
@line_buffer[0] = “#{@file.read(@read_size)}#{@line_buffer[0]}”
@read_size = MAX_READ_SIZE # Set a size for the next read.

 #
 # Divide the first line of the buffer based on +sep_string+ and

#flatten!
# those new lines into the buffer.
#
@line_buffer[0] = @line_buffer[0].scan(/.*?#{Regexp.escape
(sep_string)}|.+/)
@line_buffer.flatten!

 # We have move data now, so try again to read a line...
 gets(sep_string)

end

Works just line File#each, save that the lines come in reverse

order.
def each( sep_string = $/ )
while line = gets(sep_string)
yield line
end
end
alias_method :each_line, :each # Works just like File#each_line.
include Enumerable # Support all the standard iterators.

Works just line File#readline, save that the lines come in

reverse order.
def readline( sep_string = $/ )
gets(sep_string) || raise(EOFError, “end of file reached”)
end

Works just line File#readlines, save that line Array will be in

reverse order.

def readlines( sep_string = $/ )
lines = Array.new
while line = gets(sep_string)
lines << line
end
lines
end

Works just line File#close.

def close
@file.close
end
end


#5

On Jan 29, 2006, at 10:23 AM, James Edward G. II wrote:

This is my port of File::ReadBackwards.

I just noticed that everyone provided sample usage (just as I asked
them too), but me! Egad. Here’s Elif at work:

$ cat sample_data.txt
This is line one.
This is line two.
This is line three.

$ ruby -r elif -e ‘puts Elif.readlines(ARGV.first)’ sample_data.txt

This is line three.
This is line two.
This is line one.
$ ruby -r elif -e ‘Elif.foreach(ARGV.first) { |line| puts line if
line =~ /t[a-z]+.$/ }’ sample_data.txt
This is line three.
This is line two.

James Edward G. II


#6

On Jan 29, 2006, at 10:23 AM, James Edward G. II wrote:

This is my port of File::ReadBackwards.

I haven’t had time to document it yet, but here is the other port of
WWW::RobotRules. You use it something like this:

#!/usr/local/bin/ruby -w

require “robot_rules”
require “open-uri”

rules = RobotRules.new(“RubyQuizBrowser 1.0”)
robots_url = “http://pragmaticprogrammer.com/robots.txt

open(robots_url) do |url|
data = url.read

puts “/robots.txt:”
puts data
puts

rules.parse(robots_url, data)
end

puts “URL tests:”
%w{ http://pragmaticprogrammer.com/images/dave.jpg
http://pragmaticprogrammer.com/imagination }.each do |test|
puts “rules.allowed?( #{test.inspect} )”
puts rules.allowed?(test)
end

END

Which prints:

/robots.txt:
User-agent: *
Disallow: images

URL tests:
rules.allowed?( “http://pragmaticprogrammer.com/images/dave.jpg” )
false
rules.allowed?( “http://pragmaticprogrammer.com/imagination” )
true

James Edward G. II

#!/usr/local/bin/ruby -w

robot_rules.rb

Created by James Edward G. II on 2006-01-31.

Copyright 2006 Gray Productions. All rights reserved.

require “uri”

Based on Perl’s WWW::RobotRules module, by Gisle Aas.

class RobotRules
def initialize( user_agent )
@user_agent = user_agent.scan(/\S+/).first.sub(%r{/.*},
“”).downcase
@rules = Hash.new { |rules, rule| rules[rule] = Array.new }
end

def parse( text_uri, robots_data )
uri = URI.parse(text_uri)
location = “#{uri.host}:#{uri.port}”
@rules.delete(location)

 rules      = robots_data.split(/[\015\012]+/).
                          map { |rule| rule.sub(/\s*#.*$/, "") }
 anon_rules = Array.new
 my_rules   = Array.new
 current    = anon_rules
 rules.each do |rule|
   case rule
   when /^\s*User-Agent\s*:\s*(.+?)\s*$/i
     break unless my_rules.empty?

     current = if $1 == "*"
       anon_rules
     elsif $1.downcase.index(@user_agent)
       my_rules
     else
       nil
     end
   when /^\s*Disallow\s*:\s*(.*?)\s*$/i
     next if current.nil?

     if $1.empty?
       current << nil
     else
       disallow = URI.parse($1)

       next unless disallow.scheme.nil? or disallow.scheme ==

uri.scheme
next unless disallow.port.nil? or disallow.port == uri.port
next unless disallow.host.nil? or
disallow.host.downcase == uri.host.downcase

       disallow = disallow.path
       disallow = "/"            if disallow.empty?
       disallow = "/#{disallow}" unless disallow[0] == ?/

       current << disallow
     end
   end
 end

 @rules[location] = if my_rules.empty?
   anon_rules.compact
 else
   my_rules.compact
 end

end

def allowed?( text_uri )
uri = URI.parse(text_uri)
location = “#{uri.host}:#{uri.port}”
path = uri.path

 return true unless %w{http https}.include?(uri.scheme)

 not @rules[location].any? { |rule| path.index(rule) == 0 }

end
end


#7

Hello.

This is my first rubyquiz, and I am still learning Ruby. I decided to
go with something simple but fun. So I did a search on the CPAN (I’ve
used Perl before) for the Acme modules, and chose Acme::Bleach
(http://search.cpan.org/~dconway/Acme-Bleach-1.12/lib/Acme/Bleach.pm)
to implement. I couldn’t find a Ruby version on either RAA or
rubyforge.

Acme::Bleach is a module by Damian Conway, and it literally bleaches
your program, whilst still leaving it in a runnable state. It’s a
really cool little module, and I stuck as close to the original as
possible - even using nearly the same method names. Here it is in its
entirety. Any suggestions, criticisms, etc. are highly welcome.

#Ruby port of Acme::Bleach - by Amran Gaye
#You can use this by doing an "include ‘Bleach’ " at the top of your
program

$tie="\t"*8

def whiten(laundry)
#Change laundry to binary 1s and 0s…
#then change those to tab and space characters. Finally add newlines
after every 9th character
result = laundry.unpack(‘b*’).to_s.tr(‘01’,"
\t").gsub(/(.{9})/,"\1\n")
return $tie + result #Add a tie to the washed shirt, and
return it
end

def brighten(laundry)
#Does the opposite of whiten
laundry.sub!(/\t{8}/,’’) #Remove tie
laundry.tr!("\n",’’) #Remove newlines
laundry.tr(" \t",‘01’).to_a.pack(‘b*’) #Change spaces and tabs to 0s
and 1s, then repack them as binary
end

def dirty?(laundry) #Laundry is dirty only if it contains
non-space characters
laundry =~ /\S/
end

def proper?(laundry) #shirt is proper if it contains a
tie
laundry =~ /^#$tie/
end

shirt = IO.readlines($0).to_s #Read in current program
shirt.sub!(“require ‘Bleach’”,’’) #Remove require line

if(not dirty?(shirt) and proper?(shirt))
eval brighten(shirt)
else
file = File.new($0,“w”)
file.puts(“require ‘Bleach’”)
file.puts(whiten(shirt))
file.close
end


#8

Soon after I posted this, I saw Rubyquiz #34 (Whiteout) and - much to
my chagrin - it was the same problem! :frowning: Seems I arrived too late to
the party. Still, I hope someone found it interesting.


#9

I went browsing in CPAN to find something interesting, and came up
with Algorithm::Merge.
I don’t use the perl version, but 3 way merging is something I do
often since we allow concurrent access with our source control at
work.

Merge.rb is a fairly straight port of the perl version. I did change
a callback to a block, and added some symbols in place of numeric
constants. I need to add better documentation, but I wanted to get
this in before it was too late for the summary.

Usage:
original= “Ok,\n this is a test sentence\n which will be edited.”
edited =“Ok,\n this is a sample phrase\n which has been edited.”
change=“Hello World,\n this is a test phrase\n which I edited.”

puts “\nSplit by lines\n--------------------”
$;="\n"
Merge::diff3(original.split, edited.split, change.split).each{|l| puts
l.inspect}
puts Merge::merge(original.split, edited.split, change.split)
puts “\nSplit by words\n--------------------”
$;=" "
Merge::diff3(original.split, edited.split, change.split).each{|l| puts
l.inspect}
puts Merge::merge(original.split, edited.split,
change.split){|conflicts|
["<<"]+conflicts[1]+["|"]+conflicts[2]+[">>"]}.join(’ ')

yields:
Split by lines

[“r”, “Ok,”, “Ok,”, “Hello World,”]
[“c”, " this is a test sentence", " this is a sample phrase", " this
is a test phrase"]
[“c”, " which will be edited.", " which has been edited.", " which I
edited."]
Hello World,

this is a sample phrase
which has been edited.

this is a test phrase
which I edited.

}

Split by words

[“r”, “Ok,”, “Ok,”, “Hello”]
[“r”, nil, nil, “World,”]
[“u”, “this”, “this”, “this”]
[“u”, “is”, “is”, “is”]
[“u”, “a”, “a”, “a”]
[“l”, “test”, “sample”, “test”]
[“o”, “sentence”, “phrase”, “phrase”]
[“u”, “which”, “which”, “which”]
[“c”, “will”, “has”, “I”]
[“c”, “be”, “been”, nil]
[“u”, “edited.”, “edited.”, “edited.”]
Hello World, this is a sample phrase which << has been | I >> edited.

Bugs:

  • Merge::diff3(original,edited, change) - does a character-based diff,
    but returns inconsistent results (lines like [u, e, s, e]). I think
    this is because the callback_map has some no-ops where it should have
    valid callbacks, but it could be due to a porting error. I am still
    struggling to completely grok the use of the callback_map, with hopes
    of simplifying/clarifying it.

Question:
Can I add to or replace the Perl license with the ruby one?

Source:
---- Merge.rb -----
module Merge

Module Merge

Three-way merge and diff

based on perl’s Algorithm::Merge

by James G. Smith, removed_email_address@domain.invalid

Copyright © 2003 Texas A&M University. All Rights Reserved.

This module is free software; you may redistribute it and/or

modify it under the same terms as Perl itself.

ported to Ruby

by Adam S. removed_email_address@domain.invalid

require ‘diff/lcs’

Given references to three lists of items, diff3 performs a

three-way difference.

This function returns an array of operations describing how the

left and right lists differ from the original list. In scalar

context, this function returns a reference to such an array.

Given the following three lists,

original: a b c e f h i k

left: a b d e f g i j k

right: a b c d e h i j k

merge: a b d e g i j k

we have the following result from diff3:

[ ‘u’, ‘a’, ‘a’, ‘a’ ],

[ ‘u’, ‘b’, ‘b’, ‘b’ ],

[ ‘l’, ‘c’, undef, ‘c’ ],

[ ‘o’, undef, ‘d’, ‘d’ ],

[ ‘u’, ‘e’, ‘e’, ‘e’ ],

[ ‘r’, ‘f’, ‘f’, undef ],

[ ‘o’, ‘h’, ‘g’, ‘h’ ],

[ ‘u’, ‘i’, ‘i’, ‘i’ ],

[ ‘o’, undef, ‘j’, ‘j’ ],

[ ‘u’, ‘k’, ‘k’, ‘k’ ]

The first element in each row is the array with the difference:

c - conflict (no two are the same)

l - left is different

o - original is different

r - right is different

u - unchanged

The next three elements are the lists from the original, left,

and right arrays respectively that the row refers to (in the synopsis,

def Merge::diff3( pivot, doc_a, doc_b)
ret = []

no_change = proc do |args|
  ret << ['u', pivot[args[0]], doc_a[args[1]], doc_b[args[2]] ]
end

conflict = proc do |args|
  p= pivot[args[0]] if args[0]
  a= doc_a[args[1]] if args[1]
  b= doc_b[args[2]] if args[2]
  ret << ['c', p, a, b]
end

diff_a = proc do |args|
  case args.size
    when 1
      ret << ['o',pivot[args[0]], nil, nil]
    when 2
      ret << ['o',nil, doc_a[args[0]], doc_b[args[1]]]
    when 3
      ret << ['o', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
    end
end

diff_b = proc do |args|
  case args.size
    when 1
      ret << ['l', nil, doc_a[args[0]], nil]
    when 2
      ret << ['l', pivot[args[0]], nil, doc_b[args[1]]]
    when 3
      ret << ['l', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
    end
end

diff_c = proc do |args|
  case args.size
    when 1
      ret << ['r', nil, nil, doc_b[args[0]]]
    when 2
      ret << ['r', pivot[args[0]], doc_a[args[1]], nil]
    when 3
      ret << ['r', pivot[args[0]], doc_a[args[1]], doc_b[args[2]]]
    end
end

traverse_sequences3(pivot, doc_a, doc_b,
  {:NO_CHANGE=>no_change, :CONFLICT=>conflict,
    :A_DIFF=> diff_a, :B_DIFF=>diff_b, :C_DIFF=>diff_c}
)
return ret

end

#callbacks for Diff::LCS
class LCS_Traverse_Callbacks
def initialize diffs
@diffs = diffs
end
def [] l,r
@diffs[@left=l]=[]
@diffs[@right=r]=[]
self
end
def match *args
end
def discard_a event
@diffs[@left]<<event.old_position
end
def discard_b event
@diffs[@right]<<event.new_position
end
end

constants for traverse_sequences

D=nil
AB_A=32
AB_B=16
AC_A=8
AC_C=4
BC_B=2
BC_C=1
CB_B=5 #not used in calculations
CB_C=3 #not used in calculations
@base_doc = {AB_A=>:A,AB_B=>:B,AC_A=>:A,AC_C=>:C,BC_B=>:B,BC_C=>:C}

def Merge::traverse_sequences3(adoc, bdoc, cdoc, callbacks = {})
target_len = [bdoc.size,cdoc.size].min
bc_different_len = (bdoc.size != cdoc.size)
diffs = Hash.new([])

    # callbacks#match::               Called when +a+ and +b+ are 

pointing
# to common elements in +:A+ and
+:B+.
# callbacks#discard_a:: Called when +a+ is pointing to
an
# element not in +:B+.
# callbacks#discard_b:: Called when +b+ is pointing to
an
# element not in +:A+.
# The methods for callbacks#match,
callbacks#discard_a,
# and callbacks#discard_b are invoked with an event
comprising
# the action ("=", “+”, or “-”, respectively), the indicies +ii+
and
# +jj+, and the elements :A[ii] and :B[jj].
Return
# values are discarded by #traverse_sequences.

ts_callbacks = LCS_Traverse_Callbacks.new(diffs)

Diff::LCS::traverse_sequences(adoc, bdoc, ts_callbacks[AB_A, AB_B])
Diff::LCS::traverse_sequences(adoc, cdoc, ts_callbacks[AC_A,AC_C])

if (bc_different_len)
  Diff::LCS::traverse_sequences(cdoc, bdoc, ts_callbacks[CB_C,CB_B])
  Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])

  if diffs[CB_B] != diffs[BC_B] || diffs[CB_C] != diffs[BC_C]
    puts "Diff::diff is not symmetric for second and third

sequences - results might not be correct";

    #trim to equal lengths and try again
    b_len, c_len = bdoc.size, cdoc.size
    bdoc_save = bdoc.slice!(target_len..-1)
    cdoc_save = cdoc.slice!(target_len..-1)
    Diff::LCS::traverse_sequences(bdoc, cdoc, 

ts_callbacks[BC_B,BC_C])

    #mark the trimmed part as different and then restore
    diffs[BC_B] += (target_len..b_len).to_a if target_len < b_len
    diffs[BC_C] += (target_len..c_len).to_a if target_len < c_len
    bdoc.concat bdoc_save
    cdoc.concat cdoc_save
  end

else # not bc_different_len
  Diff::LCS::traverse_sequences(bdoc, cdoc, ts_callbacks[BC_B,BC_C])
end
pos = {:A=>0,:B=>0,:C=>0}
sizes ={:A=>adoc.size, :B=>bdoc.size, :C=>cdoc.size}
matches=[]
noop = proc {}

    # Callback_Map is indexed by the sum of AB_A, AB_B, ..., as

indicated by @matches
# this isn’t the most efficient, but it’s a bit easier to
maintain and
# read than if it were broken up into separate arrays
# half the entries are not noop - it would seem then that no
# entries should be noop. I need patterns to figure out what
the
# other entries are.

  callback_Map = [
    [ callbacks[:NO_CHANGE], :A, :B, :C ], # 0  - no matches
    [ noop,                             ], # 1  -
    BC_C
    [ callbacks[:B_DIFF],         :B    ], #*2  - 

BC_B
[ noop, ], # 3 -
BC_B BC_C
[ noop, ], # 4 -
AC_C
[ callbacks[:C_DIFF], :C ], # 5 -
AC_C BC_C
[ noop, ], # 6 -
AC_C BC_B
[ noop, ], # 7 -
AC_C BC_B BC_C
[ callbacks[:A_DIFF], :A ], # 8 - AC_A
[ noop, ], # 9 - AC_A
BC_C
[ callbacks[:C_DIFF], :A, :B ], # 10 - AC_A
BC_B
[ callbacks[:C_DIFF], :A, :B, ], # 11 - AC_A
BC_B BC_C
[ noop, ], # 12 - AC_A
AC_C
[ noop, ], # 13 - AC_A
AC_C BC_C
[ callbacks[:C_DIFF], :A, :B, ], # 14 - AC_A
AC_C BC_B
[ callbacks[:C_DIFF], :A, :B, :C ], # 15 - AC_A
AC_C BC_B BC_C
[ noop, ], # 16 - AB_B
[ noop, ], # 17 - AB_B
BC_C
[ callbacks[:B_DIFF], :B ], # 18 - AB_B
BC_B
[ noop, ], # 19 - AB_B
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 20 - AB_B
AC_C
[ noop, ], # 21 - AB_B
AC_C BC_C
[ noop, ], # 22 - AB_B
AC_C BC_B
[ callbacks[:CONFLICT], :A, :B, :C ], # 23 - AB_B
AC_C BC_B BC_C
[ callbacks[:B_DIFF], :B ], # 24 - AB_B AC_A
[ noop, ], # 25 - AB_B AC_A
BC_C
[ callbacks[:C_DIFF], :B, :C ], # 26 - AB_B AC_A
BC_B
[ noop, ], # 27 - AB_B AC_A
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 28 - AB_B AC_A
AC_C
[ noop, ], # 29 - AB_B AC_A
AC_C BC_C
[ noop, ], # 30 - AB_B AC_A
AC_C BC_B
[ callbacks[:B_DIFF], :B ], # 31 - AB_B AC_A
AC_C BC_B BC_C
[ callbacks[:NO_CHANGE], :A, :B, :C ], # 32 - AB_A
[ callbacks[:B_DIFF], :A, :C ], # 33 - AB_A
BC_C
[ noop, ], # 34 - AB_A
BC_B
[ callbacks[:B_DIFF], :A, :C ], # 35 - AB_A
BC_B BC_C
[ noop, ], # 36 - AB_A
AC_C
[ noop, ], # 37 - AB_A
AC_C BC_C
[ noop, ], # 38 - AB_A
AC_C BC_B
[ noop, ], # 39 - AB_A
AC_C BC_B BC_C
[ callbacks[:A_DIFF], :A, ], # 40 - AB_A AC_A
[ noop, ], # 41 - AB_A AC_A
BC_C
[ callbacks[:A_DIFF], :A ], # 42 - AB_A AC_A
BC_B
[ noop, ], # 43 - AB_A AC_A
BC_B BC_C
[ noop, ], # 44 - AB_A AC_A
AC_C
[ callbacks[:C_DIFF], :A, D, :C ], # 45 - AB_A AC_A
AC_C BC_C ##ADS: I think this should be :CONFLICT??
[ noop, ], # 46 - AB_A AC_A
AC_C BC_B
[ noop, ], # 47 - AB_A AC_A
AC_C BC_B BC_C
[ noop, ], # 48 - AB_A AB_B
[ callbacks[:B_DIFF], :A, :C ], # 49 - AB_A AB_B
BC_C
[ noop, ], # 50 - AB_A AB_B
BC_B
[ callbacks[:B_DIFF], :A, :B, :C ], # 51 - AB_A AB_B
BC_B BC_C
[ callbacks[:A_DIFF], :B, :C ], # 52 - AB_A AB_B
AC_C
[ noop, ], # 53 - AB_A AB_B
AC_C BC_C
[ noop, ], # 54 - AB_A AB_B
AC_C BC_B
[ callbacks[:C_DIFF], :C ], # 55 - AB_A AB_B
AC_C BC_B BC_C
[ callbacks[:B_DIFF], :A, :C ], # 56 - AB_A AB_B AC_A
[ noop, ], # 57 - AB_A AB_B AC_A
BC_C
[ callbacks[:CONFLICT], :A, :B, D ], # 58 - AB_A AB_B AC_A
BC_B ##ADS: I changed this one to :CONFLICT
[ noop, ], # 59 - AB_A AB_B AC_A
BC_B BC_C
[ callbacks[:A_DIFF], :A, :B, :C ], # 60 - AB_A AB_B AC_A
AC_C
[ callbacks[:CONFLICT], :A, D, :C ], # 61 - AB_A AB_B AC_A
AC_C BC_C
[ callbacks[:CONFLICT], :A, :B, D ], # 62 - AB_A AB_B AC_A
AC_C BC_B
[ callbacks[:CONFLICT], :A, :B, :C ], # 63 - AB_A AB_B AC_A
AC_C BC_B BC_C
]

#while there is something to work with
while diffs.values.find{|e|e.size>0} && 

[:A,:B,:C].find{|n|pos[n]<sizes[n]}

  #find all the differences  at the current position of each doc
  matchset=[:A,:B,:C].inject([]) do |ms,i|
    ms+diffs.find_all {|k,v|@base_doc[k]==i && v[0]==pos[i]}
  end
  callback_num=matchset.uniq.inject(0){|cb,val| (cb|val[0])}
  callback = callback_Map[callback_num]
  args = callback[1..-1]
  callback[0].call(args.map{|ar| ar&&pos[ar]})


  args.each do |n|
    pos[n]+=1 if n
    case n
      when :A
        diffs[AB_A].shift while diffs[AB_A][0] && ( diffs[AB_A][0]

< pos[n] )
diffs[AC_A].shift while diffs[AC_A][0] && ( diffs[AC_A][0]
< pos[n] )
when :B
diffs[AB_B].shift while diffs[AB_B][0] && ( diffs[AB_B][0]
< pos[n] )
diffs[BC_B].shift while diffs[BC_B][0] && ( diffs[BC_B][0]
< pos[n] )
when :C
diffs[AC_C].shift while diffs[AC_C][0] && ( diffs[AC_C][0]
< pos[n] )
diffs[BC_C].shift while diffs[BC_C][0] && ( diffs[BC_C][0]
< pos[n] )
end
end #args.each
#raise “args empty” if args.empty? ##ADS: args.empty? is true
if the callback was a no-op. I don’t think that should happen.
break if args.empty?
end

#this part takes care of the leftovers
bits={:A=>4,:B=>2,:C=>1}
while [:A,:B,:C].find{|n|pos[n]<sizes[n]}
  match = 0
  args=[]
  [:A,:B,:C].each do |i|
    if pos[i]<sizes[i]
      match|=bits[i]
      args << pos[i]
      pos[i]+=1
    end
  end
  switch = [0,5,24,17,34,8,10,0][match] #ADS: I totally don't

understand how these callbacks were chosen
callback_Map[switch][0].call(*args) if callback_Map[switch][0]
end
end

Given references to three lists of items, merge performs a three-way

merge. The merge function uses the diff3 function to do most of

the work.

The optional block parameter is called for conflicts. It should

accept an array of 3 arrays

The first array holds a list of elements from the original list.

The second array has a list of elements from the left list.

The last array holds a list of elements from the right list.

The block should return a list of elements to place in the merged

list in place of the conflict.

The default conflict handler returns:

["<!-- ------ START CONFLICT ------ -->",

args[1],

“<!-- ---------------------------- -->”,

args[2],

“<!-- ------ END CONFLICT ------ -->}”]

def Merge::merge(pivot,doc_a, doc_b)

conflict_callback =  proc do |args|
    ["<!-- ------ START CONFLICT ------ -->",
    args[1],
    "<!-- ---------------------------- -->",
    args[2],
    "<!-- ------  END  CONFLICT ------ -->}"]
  end

diff = diff3(pivot, doc_a, doc_b);

ret = []
conflict = [[],[],[]]

diff.each do |diffline|
  i = 0
  if diffline[0] == 'c' # conflict
    conflict[0] << diffline[1] if diffline[1];
    conflict[1] << diffline[2] if diffline[2];
    conflict[2] << diffline[3] if diffline[3];
  else
    unless (conflict[0].empty? && conflict[1].empty? && 

conflict[2].empty?)
ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
conflict = [[],[],[]]
end
case diffline[0]
when ‘u’ # unchanged
ret << diffline[2] || diffline[3];
when ‘o’,‘l’ # added by both or left
ret << diffline[2] if diffline[2]
when ‘r’ #added by right
ret << diffline[3] if diffline[3]
end
end
end
unless (conflict[0].empty? && conflict[1].empty? &&
conflict[2].empty?)
ret << (block_given? ? yield(conflict) :
conflict_callback.call(conflict))
end

ret

end

end