Coverage for utilities/ltree.py: 82%
41 statements
« prev ^ index » next coverage.py v7.15.2, created at 2026-10-10 18:35 +0000
1"""
2Migration support for ltree-based hierarchical models.
4This module holds the schema-level machinery that backs `netbox.models.ltree`:
5the PostgreSQL trigger function / trigger SQL and the `InstallLtreeTriggers`
6migration operation that installs them. It is kept separate from the model layer
7(`netbox.models.ltree`) so that migrations depend only on this DB-level code and
8not on the model definitions.
10The paths maintained by these triggers are never computed or mutated from Python;
11the model layer only reads `path`/`sort_path` back from the database.
13Trigger DDL and search_path
14---------------------------
15Everything this module emits is replayed verbatim by `pg_restore`, which runs with
16`search_path` set to the empty string and schema-qualifies every name it can (a
17CVE-2018-1058 hardening). Unqualified names in the SQL below therefore have to
18resolve without help from the path, and the two halves of a trigger differ in when
19that resolution happens:
21* A trigger's WHEN clause is resolved at CREATE TRIGGER time. `IS DISTINCT FROM`
22 (like `=`, `<`, ...) is grammar which expands to the operand type's operator, and
23 there is no syntax to schema-qualify it. An extension type whose operators live
24 outside `pg_catalog` — `ltree` installs into `public` — makes that CREATE TRIGGER
25 unrestorable, and because `psql` does not stop on error by default the restore
26 appears to succeed with the trigger silently missing (#23130).
27* A trigger FUNCTION's body survives only because pg_dump emits
28 `SET check_function_bodies = false`, which suppresses the validation that would
29 otherwise reject the unqualified `ltree` declarations below at CREATE FUNCTION
30 time. Under the default `check_function_bodies = on` they fail with
31 `type "ltree" does not exist`. So the bodies are not inherently path-independent;
32 they are exempted by the restore's own configuration. Anything replaying this DDL
33 outside a pg_dump context must either put the extension's schema on the path or
34 set that GUC itself.
36 Rule: keep WHEN-clause operand types inside `pg_catalog`. Cast an
37 extension-typed column with `::text` (ltree's text I/O is byte-canonical, so
38 `::text` equality is exactly ltree equality).
40`RestoreUnderRestrictedSearchPathTests` in `utilities/tests/test_ltree.py` enforces
41this by creating the generated DDL with the extension's schema off the search_path.
42"""
43from django.db import migrations
45__all__ = (
46 'InstallLtreeTriggers',
47 'ReinstallLtreeTriggers',
48 'ltree_trigger_sql',
49)
52# Path label is the row's PK zero-padded to 19 chars (max bigint width) so that
53# lexicographic ordering of ltree labels matches numeric PK ordering across digit
54# boundaries (e.g. "0...09" sorts before "0...10").
55# Per-tree advisory locking (see _lock_tree_roots_sql / LtreeModel "Concurrency"):
56# every child insert / move / reparent of a node takes a transaction-level
57# advisory lock keyed on the root(s) of the tree(s) it touches, BEFORE reading the
58# parent path. A concurrent reparent of an ancestor takes the same key, so the two
59# serialize and the AFTER cascade can never miss a row inserted concurrently;
60# writes in different trees use different keys and run in parallel. Inserting a new
61# root (parent_id IS NULL) takes no lock at all -- it is a race-free singleton tree
62# -- so a bulk import of many top-level objects does not accumulate one lock per
63# root and cannot exhaust the shared lock table.
64_LOCK_TREE_ROOTS_SQL = '''
65 -- A brand-new root (INSERT with parent_id IS NULL) starts its own singleton
66 -- tree that no concurrent transaction can yet see (MVCC: the uncommitted row
67 -- is invisible) or reference (no other transaction has its PK). For such a
68 -- row this BEFORE function reads no other row (the parent lookup below is
69 -- gated on parent_id) and the AFTER cascade fires only on UPDATE, so the
70 -- insert touches solely its own NEW row -- there is nothing to serialize
71 -- against, and the advisory lock it would otherwise take can never contend.
72 -- Skipping it here is what stops a bulk import of many top-level objects from
73 -- taking one xact-lock per root and exhausting the shared lock table
74 -- (sized by max_locks_per_transaction). Every other case still locks below:
75 -- a child insert, any reparent, and a reparent-to-root (TG_OP = UPDATE, where
76 -- the existing row has a real subtree the AFTER cascade must rewrite).
77 IF NOT (TG_OP = 'INSERT' AND NEW.parent_id IS NULL) THEN
78 -- Destination tree root: the parent's root label, or this row's own label
79 -- when it is (or becomes) a root. The CASE guards against a parent whose path
80 -- is the empty ltree '' (reachable only via a trigger-bypassing raw write):
81 -- subltree('', 0, 1) would raise 'invalid positions', so fall back to the
82 -- child's own label as the lock key rather than aborting the insert/move.
83 IF NEW.parent_id IS NOT NULL THEN
84 EXECUTE format(
85 'SELECT CASE WHEN nlevel(path) > 0 THEN subltree(path, 0, 1)::text END'
86 ' FROM %%I WHERE id = $1',
87 TG_TABLE_NAME
88 ) INTO dest_root USING NEW.parent_id;
89 END IF;
90 dest_root := COALESCE(dest_root, lpad(NEW.id::text, 19, '0'));
91 -- Source tree root (moves only): this row's current root, which the AFTER
92 -- cascade will rewrite.
93 IF TG_OP = 'UPDATE' AND OLD.path IS NOT NULL AND nlevel(OLD.path) > 0 THEN
94 old_root := subltree(OLD.path, 0, 1)::text;
95 END IF;
96 key_dest := hashtextextended(TG_TABLE_NAME || ':' || dest_root, 0);
97 IF old_root IS NOT NULL AND old_root <> dest_root THEN
98 -- Cross-tree move: lock both roots, ascending, to avoid deadlock between
99 -- two concurrent moves that touch the same pair.
100 key_old := hashtextextended(TG_TABLE_NAME || ':' || old_root, 0);
101 PERFORM pg_advisory_xact_lock(LEAST(key_dest, key_old));
102 PERFORM pg_advisory_xact_lock(GREATEST(key_dest, key_old));
103 ELSE
104 PERFORM pg_advisory_xact_lock(key_dest);
105 END IF;
106 END IF;
107'''
109_COMPUTE_PATH_ONLY_FN = '''
110CREATE OR REPLACE FUNCTION "{table}_ltree_compute_path_fn"() RETURNS TRIGGER AS $$
111DECLARE
112 parent_path ltree;
113 dest_root text;
114 old_root text;
115 key_dest bigint;
116 key_old bigint;
117BEGIN
118''' + _LOCK_TREE_ROOTS_SQL + '''
119 IF NEW.parent_id IS NOT NULL THEN
120 EXECUTE format('SELECT path FROM %%I WHERE id = $1', TG_TABLE_NAME)
121 INTO parent_path USING NEW.parent_id;
122 -- Cycle guard. The Python LtreeModel.save() also rejects cyclic moves,
123 -- but a QuerySet.update() / bulk_update() bypasses save() entirely, so
124 -- catch the case here as a last line of defense. A cycle exists iff
125 -- this row's own label appears anywhere in parent_path (the row would
126 -- become its own ancestor). Match the label as any segment via lquery.
127 IF parent_path ~ ('*.' || lpad(NEW.id::text, 19, '0') || '.*')::lquery
128 OR parent_path = lpad(NEW.id::text, 19, '0')::ltree THEN
129 RAISE EXCEPTION 'cycle detected: %% cannot be its own ancestor', TG_TABLE_NAME
130 USING ERRCODE = 'check_violation';
131 END IF;
132 NEW.path := parent_path || lpad(NEW.id::text, 19, '0')::ltree;
133 ELSE
134 NEW.path := lpad(NEW.id::text, 19, '0')::ltree;
135 END IF;
136 RETURN NEW;
137END
138$$ LANGUAGE plpgsql;
139'''
141_CASCADE_PATH_ONLY_FN = '''
142CREATE OR REPLACE FUNCTION "{table}_ltree_cascade_path_fn"() RETURNS TRIGGER AS $$
143BEGIN
144 -- `nlevel($2) > 0` guards against an empty OLD.path ('', reachable only via a
145 -- trigger-bypassing raw write): `path <@ ''` is true for EVERY row, so without
146 -- this the cascade would rewrite the entire table on one reparent.
147 EXECUTE format(
148 'UPDATE %%I SET path = $1 || subpath(path, nlevel($2))'
149 ' WHERE nlevel($2) > 0 AND path <@ $2 AND id != $3',
150 TG_TABLE_NAME
151 ) USING NEW.path, OLD.path, NEW.id;
152 RETURN NULL;
153END
154$$ LANGUAGE plpgsql;
155'''
157# For models with order_insertion_by=(name,) — maintain a second text column
158# `sort_path` whose value is the chain of ancestor names joined by chr(9) (TAB).
159# TAB sorts strictly below any printable character under both the default text
160# collation and the ICU `natural_sort` collation (which is `und-u-kn-true`).
161# ICU collations with default variable weighting treat U+0001..U+0008 as
162# variable-ignorable, so a chr(1) separator under natural_sort would interleave
163# children with unrelated roots; TAB is given a primary weight and orders
164# deterministically. ORDER BY sort_path then gives MPTT-equivalent
165# tree-flatten ordering with siblings in name (collation) order.
166#
167# The BEFORE trigger fires on INSERT, parent_id changes, and name changes, so
168# a rename updates the row's own sort_path; the AFTER trigger then cascades
169# the new sort_path into descendants. (django-mptt's `order_insertion_by`
170# stops at the renamed node and leaves descendants stale until a manual
171# rebuild — NetBox auto-cascades because operators expect renames to flow
172# through. `rebuild_sort_paths()` is still available for bulk repair.)
173_COMPUTE_PATH_AND_SORT_FN = '''
174CREATE OR REPLACE FUNCTION "{table}_ltree_compute_path_fn"() RETURNS TRIGGER AS $$
175DECLARE
176 parent_path ltree;
177 parent_sort_path text;
178 dest_root text;
179 old_root text;
180 key_dest bigint;
181 key_old bigint;
182BEGIN
183''' + _LOCK_TREE_ROOTS_SQL + '''
184 -- sort_path joins ancestor names with chr(9) (TAB); a literal tab in a name
185 -- would inject a spurious separator and corrupt sibling ordering for the node
186 -- and its descendants. LtreeModel.clean() rejects this for forms/serializers;
187 -- this is the backstop for bulk_create / scripts / raw writes that bypass clean().
188 IF position(chr(9) in COALESCE(NEW."{name_col}", '')) > 0 THEN
189 RAISE EXCEPTION 'name contains a tab character, which is not allowed'
190 USING ERRCODE = 'check_violation';
191 END IF;
192 IF NEW.parent_id IS NOT NULL THEN
193 EXECUTE format('SELECT path, sort_path FROM %%I WHERE id = $1', TG_TABLE_NAME)
194 INTO parent_path, parent_sort_path USING NEW.parent_id;
195 -- Cycle guard. See _COMPUTE_PATH_ONLY_FN for the rationale; this catches
196 -- raw UPDATE / bulk_update paths that bypass LtreeModel.save().
197 IF parent_path ~ ('*.' || lpad(NEW.id::text, 19, '0') || '.*')::lquery
198 OR parent_path = lpad(NEW.id::text, 19, '0')::ltree THEN
199 RAISE EXCEPTION 'cycle detected: %% cannot be its own ancestor', TG_TABLE_NAME
200 USING ERRCODE = 'check_violation';
201 END IF;
202 NEW.path := parent_path || lpad(NEW.id::text, 19, '0')::ltree;
203 NEW.sort_path := parent_sort_path || chr(9) || NEW."{name_col}";
204 ELSE
205 NEW.path := lpad(NEW.id::text, 19, '0')::ltree;
206 NEW.sort_path := NEW."{name_col}";
207 END IF;
208 RETURN NEW;
209END
210$$ LANGUAGE plpgsql;
211'''
213_CASCADE_PATH_AND_SORT_FN = """
214CREATE OR REPLACE FUNCTION "{table}_ltree_cascade_path_fn"() RETURNS TRIGGER AS $$
215BEGIN
216 -- COALESCE guards against a NULL sort_path slipping in via a raw write that
217 -- bypassed the BEFORE trigger: without it, length(NULL)/substring(... FROM NULL)
218 -- would cascade NULL to every descendant's sort_path in one shot.
219 -- `nlevel($2) > 0` guards against an empty OLD.path ('', reachable only via a
220 -- trigger-bypassing raw write): `path <@ ''` is true for EVERY row, so without
221 -- this the cascade would rewrite the entire table on one reparent.
222 EXECUTE format(
223 'UPDATE %%I SET '
224 ' path = $1 || subpath(path, nlevel($2)), '
225 ' sort_path = COALESCE($4, '''') || substring(COALESCE(sort_path, '''') FROM length(COALESCE($5, '''')) + 1) '
226 'WHERE nlevel($2) > 0 AND path <@ $2 AND id != $3',
227 TG_TABLE_NAME
228 ) USING NEW.path, OLD.path, NEW.id, NEW.sort_path, OLD.sort_path;
229 RETURN NULL;
230END
231$$ LANGUAGE plpgsql;
232"""
234_BEFORE_TRIGGER_PATH_ONLY = '''
235CREATE TRIGGER "{table}_ltree_compute_path"
236 BEFORE INSERT OR UPDATE OF parent_id ON "{table}"
237 FOR EACH ROW EXECUTE FUNCTION "{table}_ltree_compute_path_fn"();
238'''
240# For path+sort tables, also fire on UPDATE OF {name_col} so that renaming a
241# node recomputes its sort_path. The cascade trigger then propagates the new
242# sort_path to descendants.
243_BEFORE_TRIGGER_PATH_AND_SORT = '''
244CREATE TRIGGER "{table}_ltree_compute_path"
245 BEFORE INSERT OR UPDATE OF parent_id, "{name_col}" ON "{table}"
246 FOR EACH ROW EXECUTE FUNCTION "{table}_ltree_compute_path_fn"();
247'''
249# AFTER trigger fires on the columns that operators / Django write directly
250# (parent_id and the name column) — NOT on path or sort_path. The cascade
251# function rewrites path/sort_path on descendants in a single statement, and
252# because that statement does not touch parent_id or {name_col}, the AFTER
253# trigger does not re-fire on those descendant rows. This prevents the
254# quadratic re-cascade that would otherwise occur for any deep subtree.
255#
256# `path` is compared as text rather than as ltree. `IS DISTINCT FROM` is SQL
257# grammar, not an operator: it has no schema-qualification syntax, and it expands
258# to the operand type's `=` operator, which is resolved from search_path at
259# CREATE TRIGGER time. `ltree =` lives in whichever schema the extension was
260# installed into (normally `public`), so a CREATE TRIGGER replayed by pg_restore
261# — which runs with `search_path` set to the empty string and schema-qualifies
262# every name it can — cannot resolve it and fails with "operator does not exist:
263# public.ltree = public.ltree", silently dropping the cascade trigger from the
264# restored database (#23130). `text =` is in `pg_catalog`, which is always on the
265# effective path, so the cast makes the DDL search_path-independent.
266#
267# The comparison is equivalent: ltree's text I/O is byte-preserving (parse_ltree
268# and deparse_ltree copy label bytes with memcpy, and ltree_eq is a memcmp over
269# those same bytes), so two ltree values are equal iff their text renderings are
270# — see contrib/ltree/ltree_io.c and ltree_op.c. PostgreSQL publishes no explicit
271# guarantee of this; it is a property of the implementation, which cannot change
272# without breaking ltree's on-disk format and every existing ltree index.
273#
274# `sort_path` needs no cast: it is already a text column.
275#
276# See also the module docstring ("Trigger DDL and search_path") and
277# RestoreUnderRestrictedSearchPathTests in utilities/tests/test_ltree.py, which
278# enforces this by creating the generated DDL with the extension's schema off the
279# search_path.
280_AFTER_TRIGGER_PATH_ONLY = '''
281CREATE TRIGGER "{table}_ltree_cascade_path"
282 AFTER UPDATE OF parent_id ON "{table}"
283 FOR EACH ROW WHEN (OLD.path::text IS DISTINCT FROM NEW.path::text)
284 EXECUTE FUNCTION "{table}_ltree_cascade_path_fn"();
285'''
287_AFTER_TRIGGER_PATH_AND_SORT = '''
288CREATE TRIGGER "{table}_ltree_cascade_path"
289 AFTER UPDATE OF parent_id, "{name_col}" ON "{table}"
290 FOR EACH ROW WHEN (
291 OLD.path::text IS DISTINCT FROM NEW.path::text
292 OR OLD.sort_path IS DISTINCT FROM NEW.sort_path
293 )
294 EXECUTE FUNCTION "{table}_ltree_cascade_path_fn"();
295'''
298def ltree_trigger_sql(table, name_column=None):
299 """
300 Return the DDL statements which install ltree path-maintenance triggers on `table`.
302 Two functions and two triggers, in dependency order. If `name_column` is given, the
303 table is expected to carry a `sort_path` column and gets the variants which maintain
304 it alongside `path`.
306 The triggers are dropped before being created, so re-running this SQL converges
307 instead of failing: a plain `CREATE TRIGGER` raises 42710 when the trigger already
308 exists, which a re-run, a partially-applied migration, or a later migration
309 reinstalling a corrected definition (#23130) would all hit. The functions already use
310 CREATE OR REPLACE. This mirrors `utilities.migration.InstallDenormalizationTrigger`.
312 `InstallLtreeTriggers` executes exactly this SQL, so tests can assert against the
313 statements migrations really run rather than a copy which can drift.
314 """
315 if name_column:
316 function_sql = (
317 _COMPUTE_PATH_AND_SORT_FN.format(table=table, name_col=name_column),
318 _CASCADE_PATH_AND_SORT_FN.format(table=table),
319 )
320 trigger_sql = (
321 _BEFORE_TRIGGER_PATH_AND_SORT.format(table=table, name_col=name_column),
322 _AFTER_TRIGGER_PATH_AND_SORT.format(table=table, name_col=name_column),
323 )
324 else:
325 function_sql = (
326 _COMPUTE_PATH_ONLY_FN.format(table=table),
327 _CASCADE_PATH_ONLY_FN.format(table=table),
328 )
329 trigger_sql = (
330 _BEFORE_TRIGGER_PATH_ONLY.format(table=table),
331 _AFTER_TRIGGER_PATH_ONLY.format(table=table),
332 )
334 return (
335 *function_sql,
336 f'DROP TRIGGER IF EXISTS "{table}_ltree_cascade_path" ON "{table}";',
337 f'DROP TRIGGER IF EXISTS "{table}_ltree_compute_path" ON "{table}";',
338 *trigger_sql,
339 )
342class InstallLtreeTriggers(migrations.operations.base.Operation):
343 """
344 Install per-table ltree path-maintenance triggers.
346 Two row-level triggers are installed on each target table:
348 BEFORE INSERT OR UPDATE OF parent_id -> compute NEW.path (and sort_path if applicable)
349 AFTER UPDATE OF parent_id -> cascade path/sort_path change to descendants
351 If `name_column` is provided, the model is expected to have a `sort_path`
352 text column whose value will be maintained as a chr(9)-separated chain of
353 ancestor names. This implements MPTT's `order_insertion_by=(name,)`
354 semantics: insert, reparent, and rename all honor the current value of
355 `name_column`, with renames cascaded into descendants' sort_paths.
357 Applying this operation is idempotent (see `ltree_trigger_sql`), so it can be
358 re-run to reinstall a corrected trigger definition on a table which already has
359 one.
360 """
361 reversible = True
363 def __init__(self, table_name, name_column=None):
364 self.table_name = table_name
365 self.name_column = name_column
367 def state_forwards(self, app_label, state):
368 pass
370 def database_forwards(self, app_label, schema_editor, from_state, to_state):
371 for sql in ltree_trigger_sql(self.table_name, self.name_column):
372 schema_editor.execute(sql)
374 def database_backwards(self, app_label, schema_editor, from_state, to_state):
375 t = self.table_name
376 schema_editor.execute(f'DROP TRIGGER IF EXISTS "{t}_ltree_cascade_path" ON "{t}";')
377 schema_editor.execute(f'DROP TRIGGER IF EXISTS "{t}_ltree_compute_path" ON "{t}";')
378 schema_editor.execute(f'DROP FUNCTION IF EXISTS "{t}_ltree_cascade_path_fn"();')
379 schema_editor.execute(f'DROP FUNCTION IF EXISTS "{t}_ltree_compute_path_fn"();')
381 def describe(self):
382 return f"Install ltree path triggers on {self.table_name}"
385class ReinstallLtreeTriggers(InstallLtreeTriggers):
386 """
387 Reinstall a table's ltree path-maintenance triggers, replacing an earlier definition.
389 Identical to `InstallLtreeTriggers` going forwards, but a no-op in reverse. The
390 parent operation's reverse drops both triggers and both functions, which is right
391 when reversing the migration that first installed them and wrong when reversing one
392 that merely corrected them: it would leave the table with no path maintenance at all
393 — a state no release ever shipped — and every subsequent INSERT failing on `path`'s
394 NOT NULL constraint. The triggers this replaces are recreated by reversing back to
395 the migration which installed them, so there is nothing for this operation to undo.
396 """
398 def database_backwards(self, app_label, schema_editor, from_state, to_state):
399 pass
401 def describe(self):
402 return f"Reinstall ltree path triggers on {self.table_name}"