Coverage for netbox/models/ltree.py: 67%
181 statements
« prev ^ index » next coverage.py v7.15.2, created at 2026-10-10 18:35 +0000
1"""
2Ltree-based hierarchical model support - a replacement for django-mptt backed by
3a PostgreSQL ltree column.
5LtreeModel covers the subset of django-mptt's MPTTModel API that NetBox actually
6uses. It is deliberately NOT a full reimplementation of MPTT's surface — methods
7NetBox does not rely on (e.g. get_leafnodes(), get_next_sibling(),
8get_previous_sibling()) are intentionally omitted.
10Paths are maintained entirely by PostgreSQL triggers installed via the
11InstallLtreeTriggers migration operation. The Python layer never computes or
12mutates paths directly; it only reads `path` back from the database after
13inserts and parent_id changes via refresh_from_db(fields=['path']).
14"""
15from django.core.exceptions import FieldDoesNotExist, ValidationError
16from django.db import IntegrityError, OperationalError, connection, models
17from django.db.models import ForeignKey, ManyToManyField
18from django.db.models.expressions import RawSQL
19from django.utils.translation import gettext_lazy as _
21# Import lookup classes by their fully-qualified path rather than `from . import
22# lookups`: this module is imported by netbox/models/__init__.py before that package
23# finishes initializing, so a package-relative import would fail the attribute lookup
24# on the partially-initialized `netbox.models` package (circular import).
25from netbox.models.lookups import Ancestor, AncestorOrEqual, Descendant, DescendantOrEqual
26from utilities.data import normalize_update_fields
27from utilities.querysets import RestrictedQuerySet
29__all__ = (
30 'LtreeField',
31 'LtreeManager',
32 'LtreeModel',
33 'LtreeQuerySet',
34 'SortPathField',
35)
38#
39# Field
40#
42class LtreeField(models.TextField):
43 """
44 Custom field backed by PostgreSQL's ltree type. Stores hierarchical paths
45 such as "1.4.27" (each label is the integer PK of an ancestor).
46 """
47 description = "PostgreSQL ltree field"
49 # `path` is computed by a BEFORE INSERT trigger, so its final value isn't known
50 # until the row is written. Marking the field db_returning lets the
51 # INSERT ... RETURNING clause fetch the trigger-computed value in the same
52 # round-trip (PostgreSQL evaluates RETURNING after BEFORE triggers fire),
53 # avoiding a follow-up SELECT in LtreeModel.save(). Mirrors AutoFieldMixin.
54 db_returning = True
56 def db_type(self, connection):
57 return 'ltree'
59 def get_prep_value(self, value):
60 if value is None:
61 return value
62 return str(value)
65LtreeField.register_lookup(Ancestor)
66LtreeField.register_lookup(AncestorOrEqual)
67LtreeField.register_lookup(Descendant)
68LtreeField.register_lookup(DescendantOrEqual)
71class SortPathField(models.TextField):
72 """
73 Text column holding the chr(9)-separated chain of ancestor names that drives
74 tree-flatten ordering. Like `path`, its value is maintained by triggers, so it
75 is marked db_returning to be populated via INSERT ... RETURNING without an
76 extra SELECT. It deconstructs as a plain TextField so existing migrations
77 (which created the column as TextField) require no schema change.
78 """
79 db_returning = True
81 def deconstruct(self):
82 name, path, args, kwargs = super().deconstruct()
83 return name, 'django.db.models.TextField', args, kwargs
86#
87# QuerySet / Manager
88#
90class LtreeQuerySet(RestrictedQuerySet):
91 """QuerySet for ltree-based hierarchies, layered on RestrictedQuerySet."""
93 def bulk_create(self, objs, *args, **kwargs):
94 """
95 Same as the standard `bulk_create` but rejects any row whose parent is an
96 unsaved instance. Django's bulk_create builds the multi-row INSERT VALUES
97 up front from each instance's `parent_id`; an unsaved parent's pk is not
98 assigned until the INSERT's RETURNING clause executes, so a child
99 referencing an unsaved parent (even one earlier in the same batch) goes
100 in with parent_id=NULL and the BEFORE trigger stores it as a root. Save
101 the parents first, then bulk_create their children.
102 """
103 objs_list = list(objs)
104 for idx, obj in enumerate(objs_list):
105 parent = getattr(obj, 'parent', None)
106 if parent is not None and parent.pk is None:
107 raise ValueError(
108 "bulk_create: child at index {idx} references an unsaved parent. "
109 "Django cannot propagate the parent's RETURNING-assigned pk into "
110 "the child's parent_id before the INSERT executes, so the child "
111 "would be persisted with parent_id=NULL and stored as a root. "
112 "Save the parent first, then bulk_create the children.".format(idx=idx)
113 )
114 return super().bulk_create(objs_list, *args, **kwargs)
116 def add_related_count(self, queryset, model, rel_field, count_attr, cumulative=False):
117 """
118 Annotate `queryset` with the count of `model` instances related via
119 `rel_field`, mirroring django-mptt's `TreeManager.add_related_count`.
121 When `cumulative=True`, counts include rows pointing to any descendant
122 (using the ltree `<@` operator against the parent's `path`). Handles
123 ForeignKey, ManyToManyField, and the NetBox GenericForeignKey "scope"
124 pattern (scope_type / scope_id).
126 The six historical variants (3 relation kinds × cumulative/not) are
127 assembled from two fragments: how a related row links to a tree node
128 (`link_expr` + any join/scope filter), and which node is counted — the
129 parent row itself (non-cumulative) or any node in its subtree via `<@`
130 (cumulative).
131 """
132 try:
133 field = model._meta.get_field(rel_field)
134 except Exception:
135 field = None
136 is_many_to_many = isinstance(field, ManyToManyField)
137 has_direct_fk = isinstance(field, ForeignKey)
138 has_generic_fk = (
139 hasattr(model, 'scope_type') and hasattr(model, 'scope_id')
140 and not has_direct_fk and not is_many_to_many
141 )
143 qn = connection.ops.quote_name
144 parent_table = qn(queryset.model._meta.db_table)
145 related_table = qn(model._meta.db_table)
147 # `from_join` is the FROM (+ m2m join); `link_expr` is the column that points
148 # at a tree node's id; `scope_filter` constrains the generic-FK content type.
149 params = []
150 from_join = f'FROM {related_table}'
151 scope_filter = ''
152 if is_many_to_many: 152 ↛ 155line 152 didn't jump to line 155 because the condition on line 152 was never true
153 # m2m_column_name() points at the declaring model (`model`);
154 # m2m_reverse_name() points at the related (tree) model.
155 m2m_table = qn(field.remote_field.through._meta.db_table)
156 from_join += (
157 f' INNER JOIN {m2m_table}'
158 f' ON {related_table}."id" = {m2m_table}.{qn(field.m2m_column_name())}'
159 )
160 link_expr = f'{m2m_table}.{qn(field.m2m_reverse_name())}'
161 elif has_generic_fk:
162 link_expr = f'{related_table}."scope_id"'
163 # Resolve scope_type_id via subquery so the annotation can be built at
164 # import time (e.g. in a view class body) before contenttypes migrate.
165 scope_filter = (
166 f' AND {related_table}."scope_type_id" = ('
167 'SELECT id FROM django_content_type WHERE app_label = %s AND model = %s)'
168 )
169 params = [queryset.model._meta.app_label, queryset.model._meta.model_name]
170 else:
171 # field.column honors a custom db_column; fall back to Django's default
172 # `{rel_field}_id` if the field was not resolved (a renamed unrelated
173 # field must not break import-time annotation construction).
174 rel_field_col = qn(field.column if field is not None else f'{rel_field}_id')
175 link_expr = f'{related_table}.{rel_field_col}'
177 if cumulative: 177 ↛ 181line 177 didn't jump to line 181 because the condition on line 177 was always true
178 node_join = f' INNER JOIN {parent_table} AS subtree ON {link_expr} = subtree."id"'
179 where = f'WHERE subtree."path" <@ {parent_table}."path"{scope_filter}'
180 else:
181 node_join = ''
182 where = f'WHERE {link_expr} = {parent_table}."id"{scope_filter}'
184 sql = f'(SELECT COUNT(DISTINCT {related_table}."id") {from_join}{node_join} {where})'
185 return queryset.annotate(**{
186 count_attr: RawSQL(sql, params, output_field=models.IntegerField())
187 })
190class LtreeManager(models.Manager.from_queryset(LtreeQuerySet)):
191 """Drop-in replacement for django-mptt's TreeManager."""
194#
195# Abstract model
196#
198class LtreeModelBase(models.base.ModelBase):
199 """
200 Metaclass that keeps a model's `sort_path` collation in sync with its `name`.
202 `sort_path` holds a chr(9)-joined chain of ancestor names, so to flatten siblings
203 in the same order the database sorts `name`, the two columns must share a collation.
204 Deriving it here means a subclass that gives `name` a custom db_collation (e.g.
205 `natural_sort`) automatically gets a matching `sort_path` — no need to redeclare the
206 field just to repeat the collation. An explicit db_collation on `sort_path` is left
207 untouched.
208 """
209 def __new__(mcs, name, bases, namespace, **kwargs):
210 cls = super().__new__(mcs, name, bases, namespace, **kwargs)
211 if cls._meta.abstract:
212 return cls
213 try:
214 name_field = cls._meta.get_field('name')
215 sort_path_field = cls._meta.get_field('sort_path')
216 except FieldDoesNotExist:
217 return cls
218 name_collation = getattr(name_field, 'db_collation', None)
219 if name_collation and not getattr(sort_path_field, 'db_collation', None):
220 sort_path_field.db_collation = name_collation
221 return cls
224class LtreeModel(models.Model, metaclass=LtreeModelBase):
225 """
226 Abstract base for hierarchical models backed by PostgreSQL ltree.
228 Subclasses must declare a `parent = models.ForeignKey('self', ...)`. The
229 `path` column is maintained by per-table triggers installed via
230 InstallLtreeTriggers; do not write to it from Python.
232 Bulk creates:
233 The BEFORE INSERT trigger resolves a row's parent by SELECTing `path`
234 from the same table by parent_id. LtreeQuerySet.bulk_create() rejects any
235 row whose parent is an *unsaved* instance, so in normal use — parents
236 saved before their children are bulk-created — batch order does not matter
237 (each parent row already exists for the lookup). The lone exception is
238 manually pre-assigned PKs: if a child references a same-batch parent by a
239 hand-set pk, that parent must appear earlier in the batch (the BEFORE
240 trigger fires per row in list order), or the child gets a root-level path.
242 Sort-path on rename:
243 For subclasses with the optional `sort_path` column (see
244 InstallLtreeTriggers' `name_column` arg), renaming a row updates its
245 own sort_path AND cascades into descendants' sort_paths via the AFTER
246 trigger. This diverges from django-mptt's `order_insertion_by` (which
247 leaves both the renamed row and its descendants stale until a manual
248 rebuild) because list views are expected to reflect renames promptly.
249 `rebuild_sort_paths()` is still available for bulk repair after raw
250 SQL writes that bypass the triggers.
252 Concurrency:
253 Path maintenance takes no table-wide lock (unlike django-mptt, which
254 acquired a per-model advisory lock on *every* write to protect its global
255 lft/rght/tree_id numbering). Instead, the BEFORE trigger serializes per
256 tree: it takes a transaction-level advisory lock keyed on the root of the
257 tree being written (and, for a cross-tree move, on both the source and
258 destination roots, acquired in ascending key order to avoid deadlocks).
260 Every child insert, move, and reparent of a node in a tree takes the same
261 key, so an insert deep in a subtree and a concurrent reparent of one of its
262 ancestors are serialized — the loser blocks until the winner commits, and
263 the winner's AFTER cascade can never miss a row inserted concurrently
264 (which a row-level `FOR SHARE` on the parent could not prevent: a set-based
265 cascade's snapshot would skip a row inserted after it began). Writes to
266 *different* trees use different keys and proceed fully in parallel — e.g.
267 inventory ingestion across different devices, each its own tree.
269 Inserting a *new root* (parent_id IS NULL) takes no lock: the uncommitted
270 row is invisible to other transactions and has no descendants, so nothing
271 can contend with it. This keeps a bulk import of many top-level objects
272 (the dominant import pattern) lock-free instead of taking one advisory lock
273 per root. The residual case that still scales with volume is inserting
274 children into many *distinct existing* trees in one transaction (one lock
275 per distinct tree touched); if a very large such import hits "out of shared
276 memory", raising the server's `max_locks_per_transaction` is the remedy.
278 Two residual, retryable cases remain (PostgreSQL aborts one transaction
279 with a deadlock error rather than persisting a stale path): crossing
280 reparents (moving A under B while moving B under A), and two concurrent
281 *moves* in an ancestor/descendant relationship (a move locks the moved
282 row before its BEFORE trigger can take the advisory lock). Plain inserts
283 — the high-volume path — never hit this.
284 """
285 # `default=''` here is a Django-side placeholder that the BEFORE INSERT
286 # trigger always overwrites with a valid path before the row reaches
287 # storage. Empty ltree (`''`) is itself a valid PostgreSQL ltree value
288 # (nlevel = 0) in supported PostgreSQL versions (15+), so even harnesses
289 # that bypass the trigger will not fail at INSERT — they will simply
290 # store a zero-level path.
291 path = LtreeField(editable=False, null=False, blank=True, default='')
293 objects = LtreeManager()
295 class Meta:
296 abstract = True
298 def __init__(self, *args, **kwargs):
299 super().__init__(*args, **kwargs)
300 # Read from __dict__ rather than via attribute access: a deferred
301 # `parent_id`/`name` (e.g. a GraphQL query selecting only a subset of
302 # fields) must not be lazily loaded here, since that triggers
303 # refresh_from_db() which rebuilds the instance and recurses into __init__.
304 self._loaded_parent_id = self.__dict__.get('parent_id')
305 self._loaded_name = self.__dict__.get('name')
307 @classmethod
308 def from_db(cls, db, field_names, values, **kwargs):
309 instance = super().from_db(db, field_names, values, **kwargs)
310 instance._loaded_parent_id = instance.__dict__.get('parent_id')
311 instance._loaded_name = instance.__dict__.get('name')
312 return instance
314 def _parent_creates_cycle(self):
315 """
316 Return True if the current `parent` assignment would make this node its
317 own ancestor (the new parent is self or one of its descendants), mirroring
318 django-mptt's save-time InvalidMove guard.
320 Subclasses whose `parent` is system-managed (e.g. ModuleBay, whose parent
321 is derived from its module) may override this to disable the check.
322 """
323 if self.parent_id is None: 323 ↛ 327line 323 didn't jump to line 327 because the condition on line 323 was always true
324 return False
325 # Self-as-parent is always a cycle and must be caught even if self.path
326 # is empty or deferred (path would otherwise short-circuit below).
327 if self.parent_id == self.pk:
328 return True
329 if not self.path:
330 return False
331 # The new parent lies inside this node's current subtree iff its path is a
332 # descendant of (or equal to) self.path.
333 return type(self)._default_manager.filter(
334 pk=self.parent_id, path__descendant_or_equal=self.path
335 ).exists()
337 @classmethod
338 def _has_sort_path(cls):
339 """
340 Whether this model carries the optional trigger-maintained `sort_path`
341 column (the MPTT `order_insertion_by=('name',)` equivalent). Single source
342 of truth for clean(), save(), and _tree_order_field().
343 """
344 try:
345 cls._meta.get_field('sort_path')
346 return True
347 except FieldDoesNotExist:
348 return False
350 def clean(self):
351 """
352 Reject assigning self or a descendant as parent, surfacing it as a field
353 error for forms/serializers. This mirrors the save()-time guard; the two
354 share _parent_creates_cycle() so the rule lives in exactly one place.
356 Subclasses whose `parent` is system-managed (e.g. ModuleBay) disable the
357 check by overriding _parent_creates_cycle() to return False.
359 For sort_path-backed models, also reject a tab in the name column: sort_path
360 joins ancestor names with chr(9) (TAB), so a literal tab in a name would
361 corrupt sibling ordering for the node and its descendants.
362 """
363 super().clean()
365 if self.pk and self._parent_creates_cycle(): 365 ↛ 366line 365 didn't jump to line 366 because the condition on line 365 was never true
366 raise ValidationError({
367 "parent": _("Cannot assign self or a descendant as parent.")
368 })
370 if self._has_sort_path() and '\t' in (getattr(self, 'name', None) or ''): 370 ↛ 371line 370 didn't jump to line 371 because the condition on line 370 was never true
371 raise ValidationError({
372 "name": _("Name cannot contain tab characters.")
373 })
375 def save(self, *args, **kwargs):
376 """
377 Triggers compute `path` (and `sort_path`, where present) server-side.
379 On INSERT the trigger-maintained columns are db_returning, so they are
380 populated in-place by the INSERT ... RETURNING clause without an extra
381 query. On an UPDATE that changes `parent` or the name column the triggers
382 rewrite those columns server-side, so refresh them afterward to keep the
383 in-memory instance consistent (e.g. so change logging snapshots the value
384 the triggers actually wrote, not a stale one).
385 """
386 is_insert = self._state.adding
387 # When update_fields is supplied and excludes parent, the DB does not see
388 # the new parent_id, so the trigger does not fire and _loaded_parent_id
389 # must not advance — otherwise a subsequent full save() would mis-detect
390 # the (real) parent change as already-applied and leave path stale.
391 update_fields = normalize_update_fields(kwargs)
392 parent_written = update_fields is None or 'parent' in update_fields or 'parent_id' in update_fields
393 parent_changed = (not is_insert) and parent_written and self.parent_id != self._loaded_parent_id
395 # Reject cyclic moves before writing, mirroring django-mptt's save-time
396 # guard so scripts / bulk callers (which bypass form & serializer clean())
397 # cannot silently corrupt the tree.
398 if parent_changed and self._parent_creates_cycle(): 398 ↛ 399line 398 didn't jump to line 399 because the condition on line 398 was never true
399 raise ValidationError(_("Cannot assign self or a descendant as parent."))
401 # The sort_path trigger also fires on a name change; detect that so the
402 # cascaded sort_path can be refreshed below (path-only models have no
403 # sort_path and are unaffected by renames).
404 has_sort_path = self._has_sort_path()
405 name_written = update_fields is None or 'name' in update_fields
406 name_changed = (
407 (not is_insert) and has_sort_path and name_written
408 and self.__dict__.get('name') != self._loaded_name
409 )
411 try:
412 super().save(*args, **kwargs)
413 except IntegrityError as exc:
414 # A concurrent reparent that races the Python-level _parent_creates_cycle
415 # check is caught by the BEFORE trigger, which RAISEs 'cycle detected ...'
416 # with ERRCODE = check_violation (SQLSTATE 23514). Gate on the SQLSTATE
417 # (the primary, stable signal) AND the message marker, so an unrelated
418 # CHECK constraint on a subclass (also 23514) is not misreported as a
419 # cycle. Surface it as a ValidationError so the API/UI returns 400 instead
420 # of the IntegrityError → 500 the trigger would otherwise produce.
421 if (
422 getattr(exc.__cause__, 'sqlstate', None) == '23514'
423 and 'cycle detected' in str(exc)
424 ):
425 raise ValidationError(
426 _("Cannot assign self or a descendant as parent.")
427 ) from None
428 # The BEFORE trigger likewise rejects a tab in the name (it would corrupt
429 # sort_path); translate it for direct save() calls that skip clean().
430 if (
431 getattr(exc.__cause__, 'sqlstate', None) == '23514'
432 and 'tab character' in str(exc)
433 ):
434 raise ValidationError({
435 "name": _("Name cannot contain tab characters.")
436 }) from None
437 raise
438 except OperationalError as exc:
439 # The per-tree advisory locks can deadlock on crossing reparents or two
440 # concurrent ancestor/descendant moves; PostgreSQL aborts one with
441 # SQLSTATE 40P01. Surface a clear, retryable message instead of the
442 # opaque 500 the bare OperationalError would produce.
443 if getattr(exc.__cause__, 'sqlstate', None) == '40P01':
444 raise ValidationError(
445 _("The hierarchy was modified concurrently; please retry.")
446 ) from None
447 raise
449 if (parent_changed or name_changed) and not is_insert:
450 # The triggers rewrote path/sort_path on this UPDATE; fetch them back so
451 # the in-memory instance matches storage (e.g. so change logging snapshots
452 # the value the triggers wrote, not a stale one). This costs one extra
453 # SELECT per reparent/rename; INSERT ... RETURNING covers the insert case,
454 # so only updates reach here.
455 refresh_fields = ['path'] + (['sort_path'] if has_sort_path else [])
456 self.refresh_from_db(fields=refresh_fields)
458 if is_insert or parent_written: 458 ↛ 460line 458 didn't jump to line 460 because the condition on line 458 was always true
459 self._loaded_parent_id = self.parent_id
460 if is_insert or name_written: 460 ↛ exitline 460 didn't return from function 'save' because the condition on line 460 was always true
461 self._loaded_name = self.__dict__.get('name')
463 # -- MPTT-compatible API ------------------------------------------------
465 @property
466 def level(self):
467 """Zero-based depth (root = 0). Mirrors django-mptt's `level`."""
468 if not self.path: 468 ↛ 469line 468 didn't jump to line 469 because the condition on line 468 was never true
469 return 0
470 return str(self.path).count('.')
472 def get_level(self):
473 return self.level
475 @classmethod
476 def _tree_order_field(cls):
477 """
478 Field name to order hierarchical queries by. Models that carry a
479 `sort_path` column (the MPTT `order_insertion_by=('name',)` equivalent)
480 order siblings by name to match the prior MPTT behavior; models
481 without it fall back to `path` (PK-padded, insertion order).
482 """
483 return 'sort_path' if cls._has_sort_path() else 'path'
485 def get_ancestors(self, ascending=False, include_self=False):
486 if not self.path: 486 ↛ 487line 486 didn't jump to line 487 because the condition on line 486 was never true
487 return type(self)._default_manager.none()
488 lookup = 'ancestor_or_equal' if include_self else 'ancestor'
489 qs = type(self)._default_manager.filter(**{f'path__{lookup}': self.path})
490 order_field = self._tree_order_field()
491 return qs.order_by(f'-{order_field}' if ascending else order_field)
493 def get_descendants(self, include_self=False):
494 if not self.path: 494 ↛ 495line 494 didn't jump to line 495 because the condition on line 494 was never true
495 return type(self)._default_manager.none()
496 lookup = 'descendant_or_equal' if include_self else 'descendant'
497 return type(self)._default_manager.filter(
498 **{f'path__{lookup}': self.path}
499 ).order_by(self._tree_order_field())
501 def get_children(self):
502 return type(self)._default_manager.filter(parent_id=self.pk).order_by(self._tree_order_field())
504 @classmethod
505 def rebuild_sort_paths(cls, name_column='name'):
506 """
507 Recompute `sort_path` for every row from current values of `name_column`.
509 Inserts, reparents, AND renames are all maintained automatically by the
510 BEFORE/AFTER triggers (the BEFORE trigger fires on INSERT and on updates to
511 parent_id or the name column). Use this only to repair `sort_path` after a
512 raw SQL write (e.g. a bulk COPY or a direct UPDATE) that bypassed those
513 triggers.
515 Raises if the table does not have a `sort_path` column.
516 """
517 from django.db import connection
519 if not cls._has_sort_path():
520 raise NotImplementedError(
521 f"{cls.__name__} does not have a sort_path column"
522 )
523 qn = connection.ops.quote_name
524 table = qn(cls._meta.db_table)
525 name_col = qn(name_column)
526 sql = f'''
527 WITH RECURSIVE t(id, parent_id, sort_path) AS (
528 SELECT id, parent_id, {name_col}::text
529 FROM {table} WHERE parent_id IS NULL
530 UNION ALL
531 SELECT r.id, r.parent_id, t.sort_path || chr(9) || r.{name_col}
532 FROM {table} r INNER JOIN t ON r.parent_id = t.id
533 )
534 UPDATE {table} SET sort_path = t.sort_path FROM t WHERE {table}.id = t.id;
535 '''
536 with connection.cursor() as cursor:
537 cursor.execute(sql)