AncestryEx

Organise the records of an Ecto schema as a tree (or a forest of trees) with a materialized path column, like Ruby's ancestry gem, for PostgreSQL.

Every node stores the ids of all its ancestors in a single indexed string column:

id  name        ancestry
1   Electronics /
2   Phones      /1/
3   Android     /1/2/
4   Books       /

With that column, every navigation (parent, ancestors, children, descendants, siblings, depth) is a single indexed query, and moving a subtree is a single UPDATE, however large the subtree is.

• Navigation functions return composable Ecto.Query structs.
• Changeset functions keep the tree consistent inside the repo transaction: they resolve parent_id, reject cycles, move descendants and apply orphan strategies.
• Optional depth cache (a regular column or a PostgreSQL generated column), counter cache and touching of ancestors.
• arrange/1 builds nested trees in memory.
• Integrity check and repair, and migration from an existing parent_id column with one recursive query.
• Code generators for migrations, schemas and contexts.

Installation

def deps do
  [
    {:ancestry_ex, "~> 0.1.0"}
  ]
end

Requires Ecto SQL 3.13+ and PostgreSQL. Add :ancestry_ex to import_deps in your .formatter.exs so ancestry_fields is formatted without parentheses.

Quick start with the generators

# context + schema + migration
$ mix ancestry_ex.gen.context Catalog Category categories name:string --cache-depth --counter-cache

# only schema + migration
$ mix ancestry_ex.gen.schema Catalog.Category categories name:string

# add ancestry to an existing table
$ mix ancestry_ex.gen.migration categories --cache-depth

# convert an existing parent_id tree in place
$ mix ancestry_ex.gen.migration categories --from-parent-id

mix ancestry_ex.gen.context generates:

Catalog.create_category(%{name: "Phones", parent_id: electronics.id})
Catalog.list_root_categories()
Catalog.list_category_children(category)
Catalog.list_category_ancestors(category)   # breadcrumbs
Catalog.category_tree()                      # [{category, [{child, [...]}]}]
Catalog.category_subtree(category)
Catalog.move_category(category, new_parent)  # or nil to make it a root
Catalog.update_category(category, %{parent_id: id})
Catalog.delete_category(category)            # applies the orphan strategy

Run mix help ancestry_ex.gen.context to see all options (orphan strategy, caches, --binary-id, --table, --format, ...).

Manual setup

Migration

alter table(:categories) do
  add :ancestry, :string, null: false, default: "/", collation: "C"
  add :ancestry_depth, :integer, null: false, default: 0   # cache_depth: true
  add :children_count, :integer, null: false, default: 0  # counter_cache: true
end

create index(:categories, [:ancestry])

The "C" collation lets PostgreSQL use the btree index for the LIKE '/1/2/%' prefix searches used to find descendants.

Schema

defmodule MyApp.Catalog.Category do
  use Ecto.Schema
  use AncestryEx, orphan_strategy: :rootify, cache_depth: true, counter_cache: true

  import Ecto.Changeset

  schema "categories" do
    field :name, :string
    ancestry_fields()
    timestamps()
  end

  def changeset(category, attrs) do
    category
    |> cast(attrs, [:name])
    |> validate_required([:name])
    |> AncestryEx.Changeset.cast_parent()
  end
end

ancestry_fields() defines the ancestry column, the cache columns that are enabled, and a virtual parent_id field.

Options

Writing

Ecto has no model callbacks, so the tree is maintained by changeset functions. They register Ecto.Changeset.prepare_changes/2 callbacks, which the repo runs in the same transaction as the write.

# create: parent_id comes from the params (string or integer, "" or nil means root)
%Category{} |> Category.changeset(%{"name" => "Phones", "parent_id" => "1"}) |> Repo.insert()

# move a node and its whole subtree (one UPDATE for all descendants)
category |> Category.changeset(%{parent_id: other.id}) |> Repo.update()
category |> AncestryEx.Changeset.put_parent(other) |> Repo.update()
category |> AncestryEx.Changeset.put_parent(nil) |> Repo.update()   # make it a root

# delete, applying the orphan strategy of the schema (or another one)
category |> AncestryEx.Changeset.handle_orphans() |> Repo.delete()
category |> AncestryEx.Changeset.handle_orphans(orphan_strategy: :adopt) |> Repo.delete()

Validation errors go on :parent_id: "is invalid", "does not exist", "cannot be the record itself" and "cannot be the record itself or one of its descendants" (when moving a node under its own subtree). With :restrict, deleting a node that has children returns {:error, changeset}.

[!IMPORTANT] Repo.insert/update/delete on a struct or changeset that did not go through cast_parent/1, put_parent/2 or handle_orphans/2 skips all of this. In particular, Repo.delete(category) leaves the descendants orphaned.

Reading

Navigation functions are defined in the schema and return queries. Pass a queryable as first argument to scope them, then pipe into the repo:

Category.children(category) |> Repo.all()
Category.descendants(category) |> where(active: true) |> order_by(:name) |> Repo.all()
Category.children(where(Category, active: true), category) |> Repo.all()
Repo.exists?(Category.children(category))     # has children?
Category.ancestors(category) |> Repo.all()     # ordered from the root down

Depth scopes: before_depth/1, to_depth/1, at_depth/1, from_depth/1 and after_depth/1. They use the depth cache column when there is one, and compute the depth in SQL otherwise. To get the leaves under a node, compose: category |> Category.descendants() |> Category.leaves().

The pure helpers are also available in the AncestryEx module (AncestryEx.parent_id(node)), and every generated function can be overridden.

Trees in memory

Category
|> Category.ordered_by_ancestry()
|> Repo.all()
|> AncestryEx.arrange()
#=> [{%Category{name: "Electronics"}, [{%Category{name: "Phones"}, [...]}]}, ...]

AncestryEx.arrange_serializable(nodes)
#=> [%{id: 1, name: "Electronics", children: [%{id: 2, ...}]}]

AncestryEx.arrange_serializable(nodes, fn node, children ->
  %{title: node.name, children: children}
end)

AncestryEx.sort_by_ancestry(nodes)   # parents before children (pre-order)

Nodes whose parent is not in the list become top-level entries, and siblings keep the order they had in the input, so order the query to sort siblings.

Maintenance

AncestryEx.Integrity.check(Repo, Category)
#=> :ok | {:error, [{:missing_ancestor, 12, 7}, {:cyclic_ancestry, 3}, ...]}

AncestryEx.Integrity.restore(Repo, Category)                         # repair
AncestryEx.Integrity.build_ancestry_from_parent_ids(Repo, Category)  # from a parent_id column
AncestryEx.Integrity.rebuild_depth_cache(Repo, Category)
AncestryEx.Integrity.rebuild_counter_cache(Repo, Category)

Migrating from a parent_id column

mix ancestry_ex.gen.migration categories --from-parent-id generates a migration that adds the columns and fills them from parent_id with a single recursive CTE. If the schema keeps its parent_id field (for example a belongs_to :parent), use ancestry_fields(parent_id: false) so the virtual field is not defined twice.

Differences from the Ruby gem

• No callbacks: writes go through AncestryEx.Changeset (see above).
• Navigation returns Ecto.Query structs, not records: Repo.one(Category.parent(node)).
• Descendants are always updated with one SQL statement (the gem's update_strategy: :sql). No callbacks run for them.
• Formats: materialized_path2 (default) and materialized_path. The gem's materialized_path3, ltree and array formats are not supported.
• cache_depth: :virtual uses a PostgreSQL generated column.

As in the gem, moving a node relies on the ancestry values loaded in memory. Two concurrent moves in the same subtree can conflict. Serialise them (for example with SELECT ... FOR UPDATE on the nodes involved) if your application allows concurrent edits of the tree. AncestryEx.Integrity.restore/3 repairs the tree if that ever happens.

Development

Tests need a running PostgreSQL. Connection settings are read from PGUSER, PGPASSWORD, PGHOST and PGPORT (defaults postgres/postgres/localhost/5432).

$ mix deps.get
$ mix test

License

MIT