[Rails] To RForum devs: Writing a reusable NestedSet implementation

[Sascha Ebach]

Hi,

I am adressing the guys behind RForum, but everybody else is also 
welcomed to join in.

Everytime I develop a fairly complex application there is always the 
question of how to store the content. Usually there are two options.

The first one being the easiest and also the one with the most 
repetition (DRY) is just to store everything in its own table and write 
a class for it. This one doesn't scale very well. With scaling in this 
case I mean everytime you add another content type you have to add 
another table for it. Being a developer this is not a big problem 
besides the repetition. But what if you want to give the user the 
possibility to create her own content types via a web interface? (For 
example a form with self defined fields or a new media type or what if 
you suddenly decide to put in products that are for sale or comments to 
an article ...)

The second very common option is to put everything in one table and use 
a tree structure to represent the data. This is not only useful if you 
are developing a forum (like RForum), but can be for other application 
types as well. For example in a CMS (which I am developing using Rails 
right now) you can store all kinds of content into a single table 
consisting of different content types like folders, articles, media, 
forms, products and what not. And this is what I have been doing.

Working with tree structures in a database server usually involves some 
mixture of the adjacency list model (using a parent_id field) with the 
modified preorder tree traversal algo (using a left and right field) or 
"nested set". Everytime I reimplement such a nested set it mind boggles 
me and I wish I wouldn't have to do it ;) I am certain that other 
developers feel the same (ohhh, not a nested set again ...) So this time 
I was glad that I could already find a rails implementation of this in 
RForum. I gladly stole half of the code and put it in my source. But the 
RForum impl. is not complete, yet. It doesn't allow for different 
things. The most important to me at the moment is moving/copying 
trees/nodes. I know it must be on your todo list because one of your 
user stories says "Admin splits a topic into two topics" on 
http://rforum.andreas-s.net/trac/wiki/UserStories.

Wouldn't it be great if we had a "module NestedSet" the would not be 
dependent on RForum, my CMS (or any other package that might use it) or 
even Rails/AR. This strikes me as something very useful for development 
of web apps with complexer content repositories.

I could imagine myself the following features.

- CRUD of nodes and trees of course
- defining your own table layout (maybe you don't want to call your left 
and right fields 'l' and 'r', but 'lft' and 'rgt'), this would make it 
possible to hook it into legacy systems
- fetching the children (subtrees) of a node (all or upto x levels)
- fetching only the immediate children of a node (by using parent_id)
- copy/move nodes an whole trees
- rebuild the the nested set from the parent_id field (already have a 
method for this)
- fetching the path to a node (for those breadcrumb trails)
- displaying the tree by all means of outputs via a separat adapter 
(class NestedSetOutput), for ex. nested HTML lists 
(<ul><li><ul><li></li></ul></ul>), graphical trees by GraphViz, forum 
posts of course, DHTML menus (if one must) and whatever you can think of.
- being able to use the module without Rails, i.e. AR (like any sane 
person would ever want to ;)
- everything well tested, so the developer can concentrate on testing 
other parts of the system.

Does that sound interesting to you, too? And this would work by simply doing

class Post < ActiveRecord::Base
   inlcude NestedSet::Base
   include NestedSet::Output::ForumPost

   # overwrite the standard field names
   def nested_set_fields
     {'id'     => 'id',       # key, by which a node is identified
      'left'   => 'lft',      # left key for nested set
      'right'  => 'rgt',      # right key for nested set
      'order'  => 'priority', # for sorting siblings
      'level'  => 'level',    # level or depth of node
      'parent' => 'parent_id' # for adjacency list stuff
     }
   end

   # we are good to go. you just saved yourself days of developing
   # and testing your own tree structure

end

I was actually going to just start this and see how far I can come until 
after xmas. I thought it might be a good idea to just throw this idea 
onto this list and listen to what (RForum) ppl have to say about that.

Also, I would like to recommend looking at the source code of 
NestedSet.php (php pear package DB_NestedSet) which already does exactly 
this. In my opinion this particular php class is reasonably well 
designed (it is a little bloaty)
and could be used as a reference for features that could be implemented. 
It is even unit tested which is rare for a php class.

http://cvs.php.net/co.php/pear/DB_NestedSet/NestedSet.php?r=1.86


Another thing is that I don't have any public repository like 
(http://rforum.andreas-s.net/trac) and it would be cool if we could just 
put it in there. If that is not possible I would have to think of 
something else.

What do you think?

I am going to start to extract the nested set functionality that I have 
so far into a module and when I have something concrete I am going to 
post to this list again. Maybe we can set something up?

(I am off now until tommorow evening, so don't wait for any immediate 
responses.)


-- 
Sascha Ebach