# 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](https://github.com/stefankroes/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 ```elixir 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 ```shell # 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: ```elixir 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 ```elixir 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 ```elixir 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 | Option | Default | Description | | --------------------- | --------------------- | ----------- | | `:ancestry_column` | `:ancestry` | Column holding the path. | | `:ancestry_format` | `:materialized_path2` | `:materialized_path2` (roots store `"/"`) or `:materialized_path` (roots store `NULL`, the gem's legacy format). | | `:orphan_strategy` | `:destroy` | `:destroy`, `:rootify`, `:adopt`, `:restrict` or `:none`. | | `:cache_depth` | `false` | `true` for an integer column, `:virtual` for a PostgreSQL generated column. | | `:depth_cache_column` | `:ancestry_depth` | Name of the depth column. | | `:counter_cache` | `false` | `true` (`:children_count`) or a column name. | | `:touch` | `false` | Bump `updated_at` of the ancestors when a node is saved or deleted. | ## 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. ```elixir # 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}`. | Orphan strategy | Descendants of a deleted node | | --------------- | ----------------------------- | | `:destroy` | Deleted, with one `DELETE`. | | `:rootify` | Children become roots and keep their own subtrees. | | `:adopt` | Children move up to the parent of the deleted node. | | `:restrict` | The delete fails if the node has children. | | `:none` | Left untouched (orphaned). | > [!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: ```elixir 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 ``` | Ruby `ancestry` | AncestryEx (query) | AncestryEx (no database) | | ------------------------------------------- | -------------------------------- | ------------------------------------------------ | | `Model.roots` | `roots/0,1` | `root?/1`, `has_parent?/1` | | `parent` | `parent/1,2` | `parent_id/1`, `parent_of?/2` | | `root` | `root/1,2` | `root_id/1`, `root_of?/2` | | `ancestors` / `ancestors_of` | `ancestors/1,2` | `ancestor_ids/1`, `ancestor_of?/2` | | `path` / `path_of` | `path/1,2` | `path_ids/1` | | `children` / `children_of` | `children/1,2` | `child_of?/2`, `child_ancestry/1` | | `siblings` / `siblings_of` (excludes self) | `siblings/1,2` | `sibling_of?/2` | | `descendants` / `descendants_of` | `descendants/1,2` | `descendant_of?/2` | | `subtree` / `subtree_of` | `subtree/1,2` | `in_subtree_of?/2` | | `indirects` / `indirects_of` | `indirects/1,2` | `indirect_of?/2` | | `leaves` | `leaves/0,1` | | | `depth` | `at_depth/1,2` and friends | `depth/1` | | `ordered_by_ancestry` | `ordered_by_ancestry/0,1` | | 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 ```elixir 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 ```elixir 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`). ```shell $ mix deps.get $ mix test ``` ## License MIT