Do you use LiveJournal ?

Every time I visit someone's page on LiveJournal, I see something like this.

It reminds me a Homer Simpson's web page. How people can use that crap ? Duh.

Building tree out of nested set

This keeps popping up over and over again. About 2 years ago I mentioned solution on how to build tree out of nested set, but the solution was lost in google groups. I'm going to publish it here.

So, nested set: every item has LEFT and RIGHT numbers. LEFT number is less than any LEFT or RIGHT number of any descendant item. RIGHT number is greater than any LEFT or RIGHT number of any descendant item. To get a subtree, select all items with LEFT greater than given LEFT and RIGHT less than given RIGHT number. You get the flat array of items of that tree structure. Next thing is to convert it to tree which means for any given item you need the ability to iterate over all of it's children.

First thing you need to do is to order items by LEFT number, than by RIGHT number.

A small sidenote: we will assume that LEFT and RIGHT numbers are compact so that if your root item has LEFT=1 and RIGHT=10 then for each number X in interval [1, 10] there is item for which X is the value of LEFT or RIGHT. This allows easy calculation of how many descendants particular item has.

So, say we have an flat array and we need to know how many items in array you need to skip to get to given item's next sibling. And that number is (RIGHT-LEFT) (minus one if you do not count the item itself).

# Class that allows performance wise traversing a list of items
# that form a part of nested set structure.
class NestedSetTreePresenter
  include Enumerable

  # Constructs presenter with a items that form part of nested set,
  # offset of first item on desired level and count - number of items
  # on current level.
  # Items should be ordered by their left bound values.
  def initialize(items, offset = 0, count = nil)
    @items = items
    @offset = offset
    @count = count || @items.size
  end

  # For each item of the same level in nested set as the first item
  # calls block passing corresponding item.
  def each
    i = @offset
    bound = @offset + @count
    bound = @items.size if bound > @items.size

    while i<bound
      item = @items[i]
      descendants_count = (item.rgt-item.lft)/2
      yield item
      i += 1 + descendants_count
    end
  end

  # For each item of the same level in nested set as the first item
  # calls block passing corresponding item and collection, that
  # represent all immediate children of that item. Collection is also
  # an instance of this class.
  def each_with_children
    i = @offset
    bound = @offset + @count
    bound = @items.size if bound > @items.size

    while i<bound
      item = @items[i]
      descendants_count = (item.rgt-item.lft)/2
      yield item, NestedSetTreePresenter.new(@items, i+1, descendants_count)
      i += 1 + descendants_count
    end
  end
end

I chose not to yield a proxy, container or anything else to minimize the number of objects created.

Here is how to use it:

def print_tree(items, level = 0)
  items.each_with_children do |item, children|
    puts "  "*level + item.name
    print_tree(children, level+1)
  end
end

print_tree(NestedSetTreePresenter.new(items))

RSpec's matchers without all bullshit

I've used to use and like RSpec. The problem was that it always broke with new versions of Rails and internals were too complex to understand. Then appeared Shoulda and removed the pain of writing RUnit tests, so I switched to using it. But I always missed the elegance of RSpec's matchers.

Until Matchy appeared.

The cool thing about it is that you can create custom matchers easily with #custom_matcher() method provided. Nice.

Allowing ssh access to Darcs repositories

I've been using Darcs since early 2006 and I do not see any reason to switch to any other (D)VCS like git.

Today at work we decided to put our new project into Darcs and I needed to setup access for others to my repository. The readonly access is not a problem, but allowing others to push into my repositories was a bit trickier. There is a protocol wrapper called "darcs-server", but I don't like that solution. I wanted to configure Darcs to do get/pull/push with minimal additional components.

The traditional way to do Push is via SSH. You can create a separate account for Darcs VCS or just share your own. Then, you set up access via public/private keys and here we go: you can do all operations. The only thing is that everybody can do anything with your account, which is bad. You need to restrict users to running just a small set of commands sufficient for normal Darcs operation. With Darcs 2 it turns out that you only need to allow running "darcs" with various arguments (as Darcs 2 uses special tunelling to do all work while Darcs 1 used to open tons of connections). After several experiments, here is what you need:

#!/bin/sh

first_word() { echo $1; }

line="$SSH_ORIGINAL_COMMAND"

command=$(first_word $line)
if [ "$command" = "darcs" ]; then
  sh -c "$line"
else
  echo "$command is not allowed"
fi

Then, you add "command='/home/username/bin/darcs-wrapper' " at the beginning of your collegues' public key lines in ~/.ssh/authorized_keys and boom - they are restricted to running only darcs. You can also add no-port-forwarding, no-X11-forwarding, no-agent-forwarding, no-pty to tighten security. And you can set environment variable DARCS_LOGNAME to name of particular user to get proper names in darcs changes logs: add "environment='DARCS_LOGNAME=username'" to your authorized_keys file.

Hope that helps.

UPDATE: after thinking a little, I found a case when this can be workaround to execute any command, e.g. "darcs help; rm -rf *". The problem is with "sh -c". Originally, it was introduced in place of call to "exec" to workaround problem with extra quotation marks that are not removed when parsing line and which cause Darcs to handle arguments improperly. It turns out, that "exec" is really needed there and unquoting should be done manually. Here is the corrected version:

#!/bin/sh

first_word() { echo $1; }
unquoted_words() {
  for word in $@; do
    echo $(echo $word | sed -E "s/^'(.*)'$/\1/; s/^\"(.*)\"$/\1/")
  done
}

line="$SSH_ORIGINAL_COMMAND"

command=$(first_word $line)
if [ "$command" = "darcs" ]; then
  exec $(unquoted_words $line)
else
  echo "$command is not allowed"
fi

UPDATE2: that "sed -E" thing seem to not work on Linux. Linux Sed's option for full regular expressions is called "-r". Probably need to try rewriting regexps to normal Sed's functionality. Later.

UPDATE3: very handy thing in debugging Darcs' SSH is using "--debug --verbose" options to "darcs". Then, you can see what commands are sent to server and how response is interpreted. Then, you can issue those commands manually and see if server's wrapper script outputs errors.

Specific or default templates in Rails

I want to develop admin controller to do simple CRUD operations on not-so-complex models. I want it to be DRY and to allow adding features to all of them easily. This is my second attempt, the first one was way too ugly: it used inheritance from admin's base controller and descendants passed customization parameters to base class; also, have used custom "render" methods to find template for specific controller or, if the specific template is missing, fall back to general template.

And then it broke. Yeah, this could be fixed, but the whole idea seemed bad.

I just finished the second attempt and it looks promising.

First, it includes only one controller and uses routes to determine the actual model to operate on. Every route includes additional parameter that is passed to controller that contains name of model:

map.resources :users, :controller => 'items',
    :requirements => { :item_type => 'User' }
map.resources :regions, :controller => 'items',
    :requirements => { :item_type => 'Region' }

Second, the most troublesome was to make it work like this: I have default views in app/views/items... I wanted to have subdirectories with name of particular model that would contain overrides to default templates:

app/views/items
    index.html.erb
    new.html.erb
    edit.html.erb
    _item.html.erb
    _form.html.erb
app/views/items/users
    _item.html.erb
    _form.html.erb
app/views/items/regions
    _form.html.erb

Regions doesn't need custom 'item' partial because default one (which outputs only item.to_s) fits well.

Obviously, controller's view_paths should be manipulated to search first in concrete subfolders and then in default place. But the problem was that it always tried to prepend controller name and so find it in corresponding subfolder. It's not very nice being forced to create additional directories like this:

app/views/items
app/views/items/users/items
    _item.html.erb

Well, after some digging the way to do it elegantly I found this solution:

1. Redefine controller's controller_path to return nil. After this all templates are searched in app/views/ instead of app/views/items, so it needs to be fixed, so

2. Redefine controller's view_paths to base in app/views/items.

3. Based on current item type prepend corresponding view path.

The result is as follows:

class ItemsController < ApplicationController
  def self.controller_path
    nil
  end
  self.view_paths = [ RAILS_ROOT + '/app/views/items' ]

  before_filter :setup_model

  # ... action code

  private

  def setup_model
    @model  = params[:item_type].constantize
    prepend_view_path(RAILS_ROOT + '/app/views/items/' + params[:item_type].underscore)
  end
end

Happy coding!