Closure Tree is a mostly-API-compatible replacement for the ancestry, acts_as_tree and awesome_nested_set gems, giving you:
- Best-in-class select performance:
- Fetch your whole ancestor lineage in 1 SELECT.
- Grab all your descendants: 1 SELECT.
- Get all your siblings: 1 SELECT.
- Fetch all 7-degrees-of-bacon in a nested hash: 1 SELECT.
- Best-in-class mutation performance:
- 2 SQL INSERTs on node creation
- 3 SQL INSERT/UPDATEs on node reparenting
- Support for reparenting children (and all their progeny)
- Support for polymorphism STI within the hierarchy
find_or_create_by_path
for building out hierarchies quickly and conveniently- Support for deterministic ordering of children
- Support for single-select depth-limited nested hashes
- Excellent test coverage in a variety of environments
See Bill Karwin's excellent Models for hierarchical data presentation for a description of different tree storage algorithms.
- Installation
- Usage
- Accessing Data
- Polymorphic hierarchies with STI
- Deterministic ordering
- FAQ
- Testing
- Change log
Note that closure_tree only supports Rails 3.0 and later, and has test coverage for MySQL, PostgreSQL, and SQLite.
-
Add this to your Gemfile:
gem 'closure_tree'
-
Run
bundle install
-
Add
acts_as_tree
to your hierarchical model(s). There are a number of options you can pass in, too. -
Add a migration to add a
parent_id
column to the model you want to act_as_tree. You may want to also add a column for deterministic ordering of children, but that's optional.class AddParentIdToTag < ActiveRecord::Migration def change add_column :tag, :parent_id, :integer end end
Note that if the column is null, the tag will be considered a root node.
-
Add a database migration to store the hierarchy for your model. By default the table name will be the model's table name, followed by "_hierarchies". Note that by calling
acts_as_tree
, a "virtual model" (in this case,TagHierarchy
) will be added automatically, so you don't need to create it.class CreateTagHierarchies < ActiveRecord::Migration def change create_table :tag_hierarchies, :id => false do |t| t.integer :ancestor_id, :null => false # ID of the parent/grandparent/great-grandparent/... tag t.integer :descendant_id, :null => false # ID of the target tag t.integer :generations, :null => false # Number of generations between the ancestor and the descendant. Parent/child = 1, for example. end # For "all progeny of…" selects: add_index :tag_hierarchies, [:ancestor_id, :descendant_id], :unique => true # For "all ancestors of…" selects add_index :tag_hierarchies, [:descendant_id] end end
-
Run
rake db:migrate
-
If you're migrating from another system where your model already has a
parent_id
column, runTag.rebuild!
and the …_hierarchy table will be truncated and rebuilt.If you're starting from scratch you don't need to call
rebuild!
.
Create a root node:
grandparent = Tag.create(:name => 'Grandparent')
Child nodes are created by appending to the children collection:
parent = grandparent.children.create(:name => 'Parent')
Or by giving the parent to the constructor:
child1 = Tag.create(:name => 'First Child', :parent => parent)
Or by appending to the children collection:
child2 = Tag.new(:name => 'Second Child')
parent.children << child2
Or by calling the "add_child" method:
child3 = Tag.new(:name => 'Third Child')
parent.add_child child3
Then:
grandparent.self_and_descendants.collect(&:name)
=> ["Grandparent", "Parent", "First Child", "Second Child", "Third Child"]
child1.ancestry_path
=> ["Grandparent", "Parent", "First Child"]
We can do all the node creation and add_child calls with one method call:
child = Tag.find_or_create_by_path(["grandparent", "parent", "child"])
You can find
as well as find_or_create
by "ancestry paths".
Ancestry paths may be built using any column in your model. The default
column is name
, which can be changed with the :name_column option
provided to acts_as_tree
.
Note that any other AR fields can be set with the second, optional attributes
argument.
child = Tag.find_or_create_by_path(%w{home chuck Photos"}, {:tag_type => "File"})
This will pass the attribute hash of {:name => "home", :tag_type => "File"}
to
Tag.find_or_create_by_name
if the root directory doesn't exist (and
{:name => "chuck", :tag_type => "File"}
if the second-level tag doesn't exist, and so on).
Nodes can be moved around to other parents, and closure_tree moves the node's descendancy to the new parent for you:
d = Tag.find_or_create_by_path %w(a b c d)
h = Tag.find_or_create_by_path %w(e f g h)
e = h.root
d.add_child(e) # "d.children << e" would work too, of course
h.ancestry_path
=> ["a", "b", "c", "d", "e", "f", "g", "h"]
hash_tree
provides a method for rendering a subtree as an
ordered nested hash:
b = Tag.find_or_create_by_path %w(a b)
a = b.parent
b2 = Tag.find_or_create_by_path %w(a b2)
d1 = b.find_or_create_by_path %w(c1 d1)
c1 = d1.parent
d2 = b.find_or_create_by_path %w(c2 d2)
c2 = d2.parent
Tag.hash_tree
=> {a => {b => {c1 => {d1 => {}}, c2 => {d2 => {}}}, b2 => {}}}
Tag.hash_tree(:limit_depth => 2)
=> {a => {b => {}, b2 => {}}}
b.hash_tree
=> {b => {c1 => {d1 => {}}, c2 => {d2 => {}}}}
b.hash_tree(:limit_depth => 2)
=> {b => {c1 => {}, c2 => {}}}
When you include acts_as_tree
in your model, you can provide a hash to override the following defaults:
:parent_column_name
to override the column name of the parent foreign key in the model's table. This defaults to "parent_id".:hierarchy_table_name
to override the hierarchy class name. This defaults to the singular name of the model + "Hierarchy", likeTagHierarchy
.:hierarchy_table_name
to override the hierarchy table name. This defaults to the singular name of the model + "_hierarchies", liketag_hierarchies
.:dependent
determines what happens when a node is destroyed. Defaults tonullify
.:nullify
will simply set the parent column to null. Each child node will be considered a "root" node. This is the default.:delete_all
will delete all descendant nodes (which circumvents the destroy hooks):destroy
will destroy all descendant nodes (which runs the destroy hooks on each child node)
:name_column
used by #find_or_create_by_path
, #find_by_path
, andancestry_path
instance methods. This is primarily useful if the model only has one required field (like a "tag").:order
used to set up deterministic ordering
Tag.root
returns an arbitrary root nodeTag.roots
returns all root nodesTag.leaves
returns all leaf nodesTag.hash_tree
returns an ordered, nested hash that can be depth-limited.Tag.find_by_path(path)
returns the node whose name path ispath
. See (#find_or_create_by_path).Tag.find_or_create_by_path(path)
returns the node whose name path ispath
, and will create the node if it doesn't exist already.See (#find_or_create_by_path).Tag.find_all_by_generation(generation_level)
returns the descendant nodes who aregeneration_level
away from a root.Tag.find_all_by_generation(0)
is equivalent toTag.roots
.
tag.root
returns the root for this nodetag.root?
returns true if this is a root nodetag.child?
returns true if this is a child node. It has a parent.tag.leaf?
returns true if this is a leaf node. It has no children.tag.leaves
is scoped to all leaf nodes in self_and_descendants.tag.depth
returns the depth, or "generation", for this node in the tree. A root node will have a value of 0.tag.parent
returns the node's immediate parent. Root nodes will return nil.tag.children
is ahas_many
of immediate children (just those nodes whose parent is the current node).tag.ancestors
is a ordered scope of [ parent, grandparent, great grandparent, … ]. Note that the size of this array will always equaltag.depth
.tag.ancestor_ids
is an array of the IDs of the ancestors.tag.self_and_ancestors
returns a scope containing self, parent, grandparent, great grandparent, etc.tag.siblings
returns a scope containing all nodes with the same parent astag
, excluding self.tag.sibling_ids
returns an array of the IDs of the siblings.tag.self_and_siblings
returns a scope containing all nodes with the same parent astag
, including self.tag.descendants
returns a scope of all children, childrens' children, etc., excluding self ordered by depth.tag.descendant_ids
returns an array of the IDs of the descendants.tag.self_and_descendants
returns a scope of all children, childrens' children, etc., including self, ordered by depth.tag.hash_tree
returns an ordered, nested hash that can be depth-limited.tag.find_by_path(path)
returns the node whose name path fromtag
ispath
. See (#find_or_create_by_path).tag.find_or_create_by_path(path)
returns the node whose name path fromtag
ispath
, and will create the node if it doesn't exist already.See (#find_or_create_by_path).tag.find_all_by_generation(generation_level)
returns the descendant nodes who aregeneration_level
away fromtag
.tag.find_all_by_generation(0).to_a
==[tag]
tag.find_all_by_generation(1)
==tag.children
tag.find_all_by_generation(2)
will return the tag's grandchildren, and so on.
tag.destroy
will destroy a node and do something to its children, which is determined by the:dependent
option passed toacts_as_tree
.
Polymorphic models using single table inheritance (STI) are supported:
- Create a db migration that adds a String
type
column to your model - Subclass the model class. You only need to add
acts_as_tree
to your base class:
class Tag < ActiveRecord::Base
acts_as_tree
end
class WhenTag < Tag ; end
class WhereTag < Tag ; end
class WhatTag < Tag ; end
By default, children will be ordered by your database engine, which may not be what you want.
If you want to order children alphabetically, and your model has a name
column, you'd do this:
class Tag < ActiveRecord::Base
acts_as_tree :order => 'name'
end
If you want a specific order, add a new integer column to your model in a migration:
t.integer :sort_order
and in your model:
class OrderedTag < ActiveRecord::Base
acts_as_tree :order => 'sort_order'
end
When you enable order
, you'll also have the following new methods injected into your model:
tag.siblings_before
is a scope containing all nodes with the same parent astag
, whose sort order column is less thanself
. These will be ordered properly, so thelast
element in scope will be the sibling immediately beforeself
tag.siblings_after
is a scope containing all nodes with the same parent astag
, whose sort order column is more thanself
. These will be ordered properly, so thefirst
element in scope will be the sibling immediately "after"self
If your order
column is an integer attribute, you'll also have these:
-
node1.prepend_sibling(node2)
which will- set
node2
to the same parent asnode1
, - set
node2
's order column to 1 less thannode1
's value, and - decrement the order_column of all children of node1's parents whose order_column is <>>= node2's new value by 1.
- set
-
node1.append_sibling(node2)
which will- set
node2
to the same parent asnode1
, - set
node2
's order column to 1 more thannode1
's value, and - increment the order_column of all children of node1's parents whose order_column is >= node2's new value by 1.
- set
root = OrderedTag.create(:name => "root")
a = OrderedTag.create(:name => "a", :parent => "root")
b = OrderedTag.create(:name => "b")
c = OrderedTag.create(:name => "c")
# We have to call 'root.reload.children' because root won't be in sync with the database otherwise:
a.append_sibling(b)
root.reload.children.collect(&:name)
=> ["a", "b"]
a.prepend_sibling(b)
root.reload.children.collect(&:name)
=> ["b", "a"]
a.append_sibling(c)
root.reload.children.collect(&:name)
=> ["b", "a", "c"]
b.append_sibling(c)
root.reload.children.collect(&:name)
=> ["b", "c", "a"]
No. This gem's API is based on the assumption that each node has either 0 or 1 parent.
The underlying closure tree structure will support multiple parents, but there would be many breaking-API changes to support it. I'm open to suggestions and pull requests.
Closure tree is tested under every combination of
- Ruby 1.8.7 and Ruby 1.9.3
- The latest Rails 3.0, 3.1, and 3.2 branches, and
- MySQL, PostgreSQL, & SQLite.
- Fixed issue 24, which optimized
#hash_tree
for roots. Thanks, Saverio Trioni!
- Fixed issue 23, which added support for
#siblings
when sort_order wasn't specified. Thanks, garygreyling!
- Fixed issue 20, which affected deterministic ordering when siblings where different STI classes. Thanks, edwinramirez!
Added support for:
:hierarchy_class_name
as an option- ActiveRecord::Base.table_name_prefix
- ActiveRecord::Base.table_name_suffix
This addresses issue 21. Thanks, Judd Blair!
- Added
find_all_by_generation
for feature request 17.
- Fixed issue 18, which affected append_node/prepend_node ordering when the first node didn't have an explicit order_by value
- Reverted .gemspec mistake that changed add_development_dependency to add_runtime_dependency
Fixed issue 15:
- "parent" is now attr_accessible, which adds support for constructor-provided parents.
- updated readme accordingly
- Merged calebphillips' patch for a more efficient leaves query
- Added support for partially-unsaved hierarchies issue 13:
a = Tag.new(name: "a")
b = Tag.new(name: "b")
a.children << b
a.save
- Added
hash_tree
.
- Added
ancestor_ids
,descendant_ids
, andsibling_ids
- Added example spec to solve issue 9
- Added support for deterministic ordering of nodes.
- Switched to using
has_many :though
rather thanhas_and_belongs_to_many
- Merged pull request to fix
.siblings
and.self_and_siblings
(Thanks, eljojo!)
- Added support for ActiveRecord's whitelist_attributes
(Make sure you read the Rails Security Guide, and
enable
config.active_record.whitelist_attributes
in yourconfig/application.rb
ASAP!)
- Fix for ancestry-loop detection (performed by a validation, not through raising an exception in before_save)
- Support 3.2.0's fickle deprecation of InstanceMethods (Thanks, jheiss)!
- Support for polymorphic trees
find_by_path
andfind_or_create_by_path
signatures changed to support constructor attributes- tested against Rails 3.1.3
- Had to increment the major version, as rebuild! will need to be called by prior consumers to support the new
leaves
class and instance methods. - Tag deletion is supported now along with
:dependent => :destroy
and:dependent => :delete_all
- Switched from default rails plugin directory structure to rspec
- Support for running specs under different database engines:
export DB ; for DB in sqlite3 mysql postgresql ; do rake ; done
- https://github.com/collectiveidea/awesome_nested_set
- https://github.com/patshaughnessy/class_factory
- JetBrains, which provides an open-source license to RubyMine for the development of this project.