ancestry_ex

# 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