Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pg_dump_sort.c
4 : * Sort the items of a dump into a safe order for dumping
5 : *
6 : *
7 : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 : * Portions Copyright (c) 1994, Regents of the University of California
9 : *
10 : *
11 : * IDENTIFICATION
12 : * src/bin/pg_dump/pg_dump_sort.c
13 : *
14 : *-------------------------------------------------------------------------
15 : */
16 : #include "postgres_fe.h"
17 :
18 : #include "catalog/pg_class_d.h"
19 : #include "common/int.h"
20 : #include "lib/binaryheap.h"
21 : #include "pg_backup_utils.h"
22 : #include "pg_dump.h"
23 :
24 : /*
25 : * Sort priority for database object types.
26 : * Objects are sorted by type, and within a type by name.
27 : *
28 : * Triggers, event triggers, and materialized views are intentionally sorted
29 : * late. Triggers must be restored after all data modifications, so that
30 : * they don't interfere with loading data. Event triggers are restored
31 : * next-to-last so that they don't interfere with object creations of any
32 : * kind. Matview refreshes are last because they should execute in the
33 : * database's normal state (e.g., they must come after all ACLs are restored;
34 : * also, if they choose to look at system catalogs, they should see the final
35 : * restore state). If you think to change this, see also the RestorePass
36 : * mechanism in pg_backup_archiver.c.
37 : *
38 : * On the other hand, casts are intentionally sorted earlier than you might
39 : * expect; logically they should come after functions, since they usually
40 : * depend on those. This works around the backend's habit of recording
41 : * views that use casts as dependent on the cast's underlying function.
42 : * We initially sort casts first, and then any functions used by casts
43 : * will be hoisted above the casts, and in turn views that those functions
44 : * depend on will be hoisted above the functions. But views not used that
45 : * way won't be hoisted.
46 : *
47 : * NOTE: object-type priorities must match the section assignments made in
48 : * pg_dump.c; that is, PRE_DATA objects must sort before DO_PRE_DATA_BOUNDARY,
49 : * POST_DATA objects must sort after DO_POST_DATA_BOUNDARY, and DATA objects
50 : * must sort between them.
51 : */
52 :
53 : /* This enum lists the priority levels in order */
54 : enum dbObjectTypePriorities
55 : {
56 : PRIO_NAMESPACE = 1,
57 : PRIO_PROCLANG,
58 : PRIO_COLLATION,
59 : PRIO_TRANSFORM,
60 : PRIO_EXTENSION,
61 : PRIO_TYPE, /* used for DO_TYPE and DO_SHELL_TYPE */
62 : PRIO_CAST,
63 : PRIO_FUNC,
64 : PRIO_AGG,
65 : PRIO_ACCESS_METHOD,
66 : PRIO_OPERATOR,
67 : PRIO_OPFAMILY, /* used for DO_OPFAMILY and DO_OPCLASS */
68 : PRIO_CONVERSION,
69 : PRIO_TSPARSER,
70 : PRIO_TSTEMPLATE,
71 : PRIO_TSDICT,
72 : PRIO_TSCONFIG,
73 : PRIO_FDW,
74 : PRIO_FOREIGN_SERVER,
75 : PRIO_TABLE,
76 : PRIO_TABLE_ATTACH,
77 : PRIO_DUMMY_TYPE,
78 : PRIO_ATTRDEF,
79 : PRIO_LARGE_OBJECT,
80 : PRIO_PRE_DATA_BOUNDARY, /* boundary! */
81 : PRIO_TABLE_DATA,
82 : PRIO_SEQUENCE_SET,
83 : PRIO_LARGE_OBJECT_DATA,
84 : PRIO_POST_DATA_BOUNDARY, /* boundary! */
85 : PRIO_CONSTRAINT,
86 : PRIO_INDEX,
87 : PRIO_INDEX_ATTACH,
88 : PRIO_STATSEXT,
89 : PRIO_RULE,
90 : PRIO_TRIGGER,
91 : PRIO_FK_CONSTRAINT,
92 : PRIO_POLICY,
93 : PRIO_PUBLICATION,
94 : PRIO_PUBLICATION_REL,
95 : PRIO_PUBLICATION_TABLE_IN_SCHEMA,
96 : PRIO_SUBSCRIPTION,
97 : PRIO_SUBSCRIPTION_REL,
98 : PRIO_DEFAULT_ACL, /* done in ACL pass */
99 : PRIO_EVENT_TRIGGER, /* must be next to last! */
100 : PRIO_REFRESH_MATVIEW /* must be last! */
101 : };
102 :
103 : /* This table is indexed by enum DumpableObjectType */
104 : static const int dbObjectTypePriority[] =
105 : {
106 : [DO_NAMESPACE] = PRIO_NAMESPACE,
107 : [DO_EXTENSION] = PRIO_EXTENSION,
108 : [DO_TYPE] = PRIO_TYPE,
109 : [DO_SHELL_TYPE] = PRIO_TYPE,
110 : [DO_FUNC] = PRIO_FUNC,
111 : [DO_AGG] = PRIO_AGG,
112 : [DO_OPERATOR] = PRIO_OPERATOR,
113 : [DO_ACCESS_METHOD] = PRIO_ACCESS_METHOD,
114 : [DO_OPCLASS] = PRIO_OPFAMILY,
115 : [DO_OPFAMILY] = PRIO_OPFAMILY,
116 : [DO_COLLATION] = PRIO_COLLATION,
117 : [DO_CONVERSION] = PRIO_CONVERSION,
118 : [DO_TABLE] = PRIO_TABLE,
119 : [DO_TABLE_ATTACH] = PRIO_TABLE_ATTACH,
120 : [DO_ATTRDEF] = PRIO_ATTRDEF,
121 : [DO_INDEX] = PRIO_INDEX,
122 : [DO_INDEX_ATTACH] = PRIO_INDEX_ATTACH,
123 : [DO_STATSEXT] = PRIO_STATSEXT,
124 : [DO_RULE] = PRIO_RULE,
125 : [DO_TRIGGER] = PRIO_TRIGGER,
126 : [DO_CONSTRAINT] = PRIO_CONSTRAINT,
127 : [DO_FK_CONSTRAINT] = PRIO_FK_CONSTRAINT,
128 : [DO_PROCLANG] = PRIO_PROCLANG,
129 : [DO_CAST] = PRIO_CAST,
130 : [DO_TABLE_DATA] = PRIO_TABLE_DATA,
131 : [DO_SEQUENCE_SET] = PRIO_SEQUENCE_SET,
132 : [DO_DUMMY_TYPE] = PRIO_DUMMY_TYPE,
133 : [DO_TSPARSER] = PRIO_TSPARSER,
134 : [DO_TSDICT] = PRIO_TSDICT,
135 : [DO_TSTEMPLATE] = PRIO_TSTEMPLATE,
136 : [DO_TSCONFIG] = PRIO_TSCONFIG,
137 : [DO_FDW] = PRIO_FDW,
138 : [DO_FOREIGN_SERVER] = PRIO_FOREIGN_SERVER,
139 : [DO_DEFAULT_ACL] = PRIO_DEFAULT_ACL,
140 : [DO_TRANSFORM] = PRIO_TRANSFORM,
141 : [DO_LARGE_OBJECT] = PRIO_LARGE_OBJECT,
142 : [DO_LARGE_OBJECT_DATA] = PRIO_LARGE_OBJECT_DATA,
143 : [DO_PRE_DATA_BOUNDARY] = PRIO_PRE_DATA_BOUNDARY,
144 : [DO_POST_DATA_BOUNDARY] = PRIO_POST_DATA_BOUNDARY,
145 : [DO_EVENT_TRIGGER] = PRIO_EVENT_TRIGGER,
146 : [DO_REFRESH_MATVIEW] = PRIO_REFRESH_MATVIEW,
147 : [DO_POLICY] = PRIO_POLICY,
148 : [DO_PUBLICATION] = PRIO_PUBLICATION,
149 : [DO_PUBLICATION_REL] = PRIO_PUBLICATION_REL,
150 : [DO_PUBLICATION_TABLE_IN_SCHEMA] = PRIO_PUBLICATION_TABLE_IN_SCHEMA,
151 : [DO_SUBSCRIPTION] = PRIO_SUBSCRIPTION,
152 : [DO_SUBSCRIPTION_REL] = PRIO_SUBSCRIPTION_REL,
153 : };
154 :
155 : StaticAssertDecl(lengthof(dbObjectTypePriority) == (DO_SUBSCRIPTION_REL + 1),
156 : "array length mismatch");
157 :
158 : static DumpId preDataBoundId;
159 : static DumpId postDataBoundId;
160 :
161 :
162 : static int DOTypeNameCompare(const void *p1, const void *p2);
163 : static bool TopoSort(DumpableObject **objs,
164 : int numObjs,
165 : DumpableObject **ordering,
166 : int *nOrdering);
167 : static void findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs);
168 : static int findLoop(DumpableObject *obj,
169 : DumpId startPoint,
170 : bool *processed,
171 : DumpId *searchFailed,
172 : DumpableObject **workspace,
173 : int depth);
174 : static void repairDependencyLoop(DumpableObject **loop,
175 : int nLoop);
176 : static void describeDumpableObject(DumpableObject *obj,
177 : char *buf, int bufsize);
178 : static int int_cmp(void *a, void *b, void *arg);
179 :
180 :
181 : /*
182 : * Sort the given objects into a type/name-based ordering
183 : *
184 : * Normally this is just the starting point for the dependency-based
185 : * ordering.
186 : */
187 : void
188 308 : sortDumpableObjectsByTypeName(DumpableObject **objs, int numObjs)
189 : {
190 308 : if (numObjs > 1)
191 308 : qsort(objs, numObjs, sizeof(DumpableObject *),
192 : DOTypeNameCompare);
193 308 : }
194 :
195 : static int
196 14125866 : DOTypeNameCompare(const void *p1, const void *p2)
197 : {
198 14125866 : DumpableObject *obj1 = *(DumpableObject *const *) p1;
199 14125866 : DumpableObject *obj2 = *(DumpableObject *const *) p2;
200 : int cmpval;
201 :
202 : /* Sort by type's priority */
203 14125866 : cmpval = dbObjectTypePriority[obj1->objType] -
204 14125866 : dbObjectTypePriority[obj2->objType];
205 :
206 14125866 : if (cmpval != 0)
207 3547162 : return cmpval;
208 :
209 : /*
210 : * Sort by namespace. Typically, all objects of the same priority would
211 : * either have or not have a namespace link, but there are exceptions.
212 : * Sort NULL namespace after non-NULL in such cases.
213 : */
214 10578704 : if (obj1->namespace)
215 : {
216 10001394 : if (obj2->namespace)
217 : {
218 10001280 : cmpval = strcmp(obj1->namespace->dobj.name,
219 10001280 : obj2->namespace->dobj.name);
220 10001280 : if (cmpval != 0)
221 467596 : return cmpval;
222 : }
223 : else
224 114 : return -1;
225 : }
226 577310 : else if (obj2->namespace)
227 232 : return 1;
228 :
229 : /* Sort by name */
230 10110762 : cmpval = strcmp(obj1->name, obj2->name);
231 10110762 : if (cmpval != 0)
232 8587120 : return cmpval;
233 :
234 : /* To have a stable sort order, break ties for some object types */
235 1523642 : if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
236 0 : {
237 156 : FuncInfo *fobj1 = *(FuncInfo *const *) p1;
238 156 : FuncInfo *fobj2 = *(FuncInfo *const *) p2;
239 : int i;
240 :
241 : /* Sort by number of arguments, then argument type names */
242 156 : cmpval = fobj1->nargs - fobj2->nargs;
243 156 : if (cmpval != 0)
244 34 : return cmpval;
245 136 : for (i = 0; i < fobj1->nargs; i++)
246 : {
247 136 : TypeInfo *argtype1 = findTypeByOid(fobj1->argtypes[i]);
248 136 : TypeInfo *argtype2 = findTypeByOid(fobj2->argtypes[i]);
249 :
250 136 : if (argtype1 && argtype2)
251 : {
252 136 : if (argtype1->dobj.namespace && argtype2->dobj.namespace)
253 : {
254 136 : cmpval = strcmp(argtype1->dobj.namespace->dobj.name,
255 136 : argtype2->dobj.namespace->dobj.name);
256 136 : if (cmpval != 0)
257 30 : return cmpval;
258 : }
259 106 : cmpval = strcmp(argtype1->dobj.name, argtype2->dobj.name);
260 106 : if (cmpval != 0)
261 92 : return cmpval;
262 : }
263 : }
264 : }
265 1523486 : else if (obj1->objType == DO_OPERATOR)
266 : {
267 1134444 : OprInfo *oobj1 = *(OprInfo *const *) p1;
268 1134444 : OprInfo *oobj2 = *(OprInfo *const *) p2;
269 :
270 : /* oprkind is 'l', 'r', or 'b'; this sorts prefix, postfix, infix */
271 1134444 : cmpval = (oobj2->oprkind - oobj1->oprkind);
272 1134444 : if (cmpval != 0)
273 30658 : return cmpval;
274 : }
275 389042 : else if (obj1->objType == DO_ATTRDEF)
276 : {
277 472 : AttrDefInfo *adobj1 = *(AttrDefInfo *const *) p1;
278 472 : AttrDefInfo *adobj2 = *(AttrDefInfo *const *) p2;
279 :
280 : /* Sort by attribute number */
281 472 : cmpval = (adobj1->adnum - adobj2->adnum);
282 472 : if (cmpval != 0)
283 472 : return cmpval;
284 : }
285 388570 : else if (obj1->objType == DO_POLICY)
286 : {
287 46 : PolicyInfo *pobj1 = *(PolicyInfo *const *) p1;
288 46 : PolicyInfo *pobj2 = *(PolicyInfo *const *) p2;
289 :
290 : /* Sort by table name (table namespace was considered already) */
291 46 : cmpval = strcmp(pobj1->poltable->dobj.name,
292 46 : pobj2->poltable->dobj.name);
293 46 : if (cmpval != 0)
294 46 : return cmpval;
295 : }
296 388524 : else if (obj1->objType == DO_RULE)
297 : {
298 285854 : RuleInfo *robj1 = *(RuleInfo *const *) p1;
299 285854 : RuleInfo *robj2 = *(RuleInfo *const *) p2;
300 :
301 : /* Sort by table name (table namespace was considered already) */
302 285854 : cmpval = strcmp(robj1->ruletable->dobj.name,
303 285854 : robj2->ruletable->dobj.name);
304 285854 : if (cmpval != 0)
305 285854 : return cmpval;
306 : }
307 102670 : else if (obj1->objType == DO_TRIGGER)
308 : {
309 724 : TriggerInfo *tobj1 = *(TriggerInfo *const *) p1;
310 724 : TriggerInfo *tobj2 = *(TriggerInfo *const *) p2;
311 :
312 : /* Sort by table name (table namespace was considered already) */
313 724 : cmpval = strcmp(tobj1->tgtable->dobj.name,
314 724 : tobj2->tgtable->dobj.name);
315 724 : if (cmpval != 0)
316 724 : return cmpval;
317 : }
318 :
319 : /* Usually shouldn't get here, but if we do, sort by OID */
320 1205732 : return oidcmp(obj1->catId.oid, obj2->catId.oid);
321 : }
322 :
323 :
324 : /*
325 : * Sort the given objects into a safe dump order using dependency
326 : * information (to the extent we have it available).
327 : *
328 : * The DumpIds of the PRE_DATA_BOUNDARY and POST_DATA_BOUNDARY objects are
329 : * passed in separately, in case we need them during dependency loop repair.
330 : */
331 : void
332 308 : sortDumpableObjects(DumpableObject **objs, int numObjs,
333 : DumpId preBoundaryId, DumpId postBoundaryId)
334 : {
335 : DumpableObject **ordering;
336 : int nOrdering;
337 :
338 308 : if (numObjs <= 0) /* can't happen anymore ... */
339 0 : return;
340 :
341 : /*
342 : * Saving the boundary IDs in static variables is a bit grotty, but seems
343 : * better than adding them to parameter lists of subsidiary functions.
344 : */
345 308 : preDataBoundId = preBoundaryId;
346 308 : postDataBoundId = postBoundaryId;
347 :
348 308 : ordering = (DumpableObject **) pg_malloc(numObjs * sizeof(DumpableObject *));
349 908 : while (!TopoSort(objs, numObjs, ordering, &nOrdering))
350 600 : findDependencyLoops(ordering, nOrdering, numObjs);
351 :
352 308 : memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));
353 :
354 308 : free(ordering);
355 : }
356 :
357 : /*
358 : * TopoSort -- topological sort of a dump list
359 : *
360 : * Generate a re-ordering of the dump list that satisfies all the dependency
361 : * constraints shown in the dump list. (Each such constraint is a fact of a
362 : * partial ordering.) Minimize rearrangement of the list not needed to
363 : * achieve the partial ordering.
364 : *
365 : * The input is the list of numObjs objects in objs[]. This list is not
366 : * modified.
367 : *
368 : * Returns true if able to build an ordering that satisfies all the
369 : * constraints, false if not (there are contradictory constraints).
370 : *
371 : * On success (true result), ordering[] is filled with a sorted array of
372 : * DumpableObject pointers, of length equal to the input list length.
373 : *
374 : * On failure (false result), ordering[] is filled with an unsorted array of
375 : * DumpableObject pointers of length *nOrdering, listing the objects that
376 : * prevented the sort from being completed. In general, these objects either
377 : * participate directly in a dependency cycle, or are depended on by objects
378 : * that are in a cycle. (The latter objects are not actually problematic,
379 : * but it takes further analysis to identify which are which.)
380 : *
381 : * The caller is responsible for allocating sufficient space at *ordering.
382 : */
383 : static bool
384 908 : TopoSort(DumpableObject **objs,
385 : int numObjs,
386 : DumpableObject **ordering, /* output argument */
387 : int *nOrdering) /* output argument */
388 : {
389 908 : DumpId maxDumpId = getMaxDumpId();
390 : binaryheap *pendingHeap;
391 : int *beforeConstraints;
392 : int *idMap;
393 : DumpableObject *obj;
394 : int i,
395 : j,
396 : k;
397 :
398 : /*
399 : * This is basically the same algorithm shown for topological sorting in
400 : * Knuth's Volume 1. However, we would like to minimize unnecessary
401 : * rearrangement of the input ordering; that is, when we have a choice of
402 : * which item to output next, we always want to take the one highest in
403 : * the original list. Therefore, instead of maintaining an unordered
404 : * linked list of items-ready-to-output as Knuth does, we maintain a heap
405 : * of their item numbers, which we can use as a priority queue. This
406 : * turns the algorithm from O(N) to O(N log N) because each insertion or
407 : * removal of a heap item takes O(log N) time. However, that's still
408 : * plenty fast enough for this application.
409 : */
410 :
411 908 : *nOrdering = numObjs; /* for success return */
412 :
413 : /* Eliminate the null case */
414 908 : if (numObjs <= 0)
415 0 : return true;
416 :
417 : /* Create workspace for the above-described heap */
418 908 : pendingHeap = binaryheap_allocate(numObjs, int_cmp, NULL);
419 :
420 : /*
421 : * Scan the constraints, and for each item in the input, generate a count
422 : * of the number of constraints that say it must be before something else.
423 : * The count for the item with dumpId j is stored in beforeConstraints[j].
424 : * We also make a map showing the input-order index of the item with
425 : * dumpId j.
426 : */
427 908 : beforeConstraints = (int *) pg_malloc0((maxDumpId + 1) * sizeof(int));
428 908 : idMap = (int *) pg_malloc((maxDumpId + 1) * sizeof(int));
429 3532040 : for (i = 0; i < numObjs; i++)
430 : {
431 3531132 : obj = objs[i];
432 3531132 : j = obj->dumpId;
433 3531132 : if (j <= 0 || j > maxDumpId)
434 0 : pg_fatal("invalid dumpId %d", j);
435 3531132 : idMap[j] = i;
436 9157294 : for (j = 0; j < obj->nDeps; j++)
437 : {
438 5626162 : k = obj->dependencies[j];
439 5626162 : if (k <= 0 || k > maxDumpId)
440 0 : pg_fatal("invalid dependency %d", k);
441 5626162 : beforeConstraints[k]++;
442 : }
443 : }
444 :
445 : /*
446 : * Now initialize the heap of items-ready-to-output by filling it with the
447 : * indexes of items that already have beforeConstraints[id] == 0.
448 : *
449 : * We enter the indexes into pendingHeap in decreasing order so that the
450 : * heap invariant is satisfied at the completion of this loop. This
451 : * reduces the amount of work that binaryheap_build() must do.
452 : */
453 3532040 : for (i = numObjs; --i >= 0;)
454 : {
455 3531132 : if (beforeConstraints[objs[i]->dumpId] == 0)
456 49790 : binaryheap_add_unordered(pendingHeap, (void *) (intptr_t) i);
457 : }
458 908 : binaryheap_build(pendingHeap);
459 :
460 : /*--------------------
461 : * Now emit objects, working backwards in the output list. At each step,
462 : * we use the priority heap to select the last item that has no remaining
463 : * before-constraints. We remove that item from the heap, output it to
464 : * ordering[], and decrease the beforeConstraints count of each of the
465 : * items it was constrained against. Whenever an item's beforeConstraints
466 : * count is thereby decreased to zero, we insert it into the priority heap
467 : * to show that it is a candidate to output. We are done when the heap
468 : * becomes empty; if we have output every element then we succeeded,
469 : * otherwise we failed.
470 : * i = number of ordering[] entries left to output
471 : * j = objs[] index of item we are outputting
472 : * k = temp for scanning constraint list for item j
473 : *--------------------
474 : */
475 908 : i = numObjs;
476 2180016 : while (!binaryheap_empty(pendingHeap))
477 : {
478 : /* Select object to output by removing largest heap member */
479 2179108 : j = (int) (intptr_t) binaryheap_remove_first(pendingHeap);
480 2179108 : obj = objs[j];
481 : /* Output candidate to ordering[] */
482 2179108 : ordering[--i] = obj;
483 : /* Update beforeConstraints counts of its predecessors */
484 5443056 : for (k = 0; k < obj->nDeps; k++)
485 : {
486 3263948 : int id = obj->dependencies[k];
487 :
488 3263948 : if ((--beforeConstraints[id]) == 0)
489 2129318 : binaryheap_add(pendingHeap, (void *) (intptr_t) idMap[id]);
490 : }
491 : }
492 :
493 : /*
494 : * If we failed, report the objects that couldn't be output; these are the
495 : * ones with beforeConstraints[] still nonzero.
496 : */
497 908 : if (i != 0)
498 : {
499 600 : k = 0;
500 2405948 : for (j = 1; j <= maxDumpId; j++)
501 : {
502 2405348 : if (beforeConstraints[j] != 0)
503 1352024 : ordering[k++] = objs[idMap[j]];
504 : }
505 600 : *nOrdering = k;
506 : }
507 :
508 : /* Done */
509 908 : binaryheap_free(pendingHeap);
510 908 : free(beforeConstraints);
511 908 : free(idMap);
512 :
513 908 : return (i == 0);
514 : }
515 :
516 : /*
517 : * findDependencyLoops - identify loops in TopoSort's failure output,
518 : * and pass each such loop to repairDependencyLoop() for action
519 : *
520 : * In general there may be many loops in the set of objects returned by
521 : * TopoSort; for speed we should try to repair as many loops as we can
522 : * before trying TopoSort again. We can safely repair loops that are
523 : * disjoint (have no members in common); if we find overlapping loops
524 : * then we repair only the first one found, because the action taken to
525 : * repair the first might have repaired the other as well. (If not,
526 : * we'll fix it on the next go-round.)
527 : *
528 : * objs[] lists the objects TopoSort couldn't sort
529 : * nObjs is the number of such objects
530 : * totObjs is the total number of objects in the universe
531 : */
532 : static void
533 600 : findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
534 : {
535 : /*
536 : * We use three data structures here:
537 : *
538 : * processed[] is a bool array indexed by dump ID, marking the objects
539 : * already processed during this invocation of findDependencyLoops().
540 : *
541 : * searchFailed[] is another array indexed by dump ID. searchFailed[j] is
542 : * set to dump ID k if we have proven that there is no dependency path
543 : * leading from object j back to start point k. This allows us to skip
544 : * useless searching when there are multiple dependency paths from k to j,
545 : * which is a common situation. We could use a simple bool array for
546 : * this, but then we'd need to re-zero it for each start point, resulting
547 : * in O(N^2) zeroing work. Using the start point's dump ID as the "true"
548 : * value lets us skip clearing the array before we consider the next start
549 : * point.
550 : *
551 : * workspace[] is an array of DumpableObject pointers, in which we try to
552 : * build lists of objects constituting loops. We make workspace[] large
553 : * enough to hold all the objects in TopoSort's output, which is huge
554 : * overkill in most cases but could theoretically be necessary if there is
555 : * a single dependency chain linking all the objects.
556 : */
557 : bool *processed;
558 : DumpId *searchFailed;
559 : DumpableObject **workspace;
560 : bool fixedloop;
561 : int i;
562 :
563 600 : processed = (bool *) pg_malloc0((getMaxDumpId() + 1) * sizeof(bool));
564 600 : searchFailed = (DumpId *) pg_malloc0((getMaxDumpId() + 1) * sizeof(DumpId));
565 600 : workspace = (DumpableObject **) pg_malloc(totObjs * sizeof(DumpableObject *));
566 600 : fixedloop = false;
567 :
568 1352624 : for (i = 0; i < nObjs; i++)
569 : {
570 1352024 : DumpableObject *obj = objs[i];
571 : int looplen;
572 : int j;
573 :
574 1352024 : looplen = findLoop(obj,
575 : obj->dumpId,
576 : processed,
577 : searchFailed,
578 : workspace,
579 : 0);
580 :
581 1352024 : if (looplen > 0)
582 : {
583 : /* Found a loop, repair it */
584 50562 : repairDependencyLoop(workspace, looplen);
585 50562 : fixedloop = true;
586 : /* Mark loop members as processed */
587 151866 : for (j = 0; j < looplen; j++)
588 101304 : processed[workspace[j]->dumpId] = true;
589 : }
590 : else
591 : {
592 : /*
593 : * There's no loop starting at this object, but mark it processed
594 : * anyway. This is not necessary for correctness, but saves later
595 : * invocations of findLoop() from uselessly chasing references to
596 : * such an object.
597 : */
598 1301462 : processed[obj->dumpId] = true;
599 : }
600 : }
601 :
602 : /* We'd better have fixed at least one loop */
603 600 : if (!fixedloop)
604 0 : pg_fatal("could not identify dependency loop");
605 :
606 600 : free(workspace);
607 600 : free(searchFailed);
608 600 : free(processed);
609 600 : }
610 :
611 : /*
612 : * Recursively search for a circular dependency loop that doesn't include
613 : * any already-processed objects.
614 : *
615 : * obj: object we are examining now
616 : * startPoint: dumpId of starting object for the hoped-for circular loop
617 : * processed[]: flag array marking already-processed objects
618 : * searchFailed[]: flag array marking already-unsuccessfully-visited objects
619 : * workspace[]: work array in which we are building list of loop members
620 : * depth: number of valid entries in workspace[] at call
621 : *
622 : * On success, the length of the loop is returned, and workspace[] is filled
623 : * with pointers to the members of the loop. On failure, we return 0.
624 : *
625 : * Note: it is possible that the given starting object is a member of more
626 : * than one cycle; if so, we will find an arbitrary one of the cycles.
627 : */
628 : static int
629 37574114 : findLoop(DumpableObject *obj,
630 : DumpId startPoint,
631 : bool *processed,
632 : DumpId *searchFailed,
633 : DumpableObject **workspace,
634 : int depth)
635 : {
636 : int i;
637 :
638 : /*
639 : * Reject if obj is already processed. This test prevents us from finding
640 : * loops that overlap previously-processed loops.
641 : */
642 37574114 : if (processed[obj->dumpId])
643 35806918 : return 0;
644 :
645 : /*
646 : * If we've already proven there is no path from this object back to the
647 : * startPoint, forget it.
648 : */
649 1767196 : if (searchFailed[obj->dumpId] == startPoint)
650 191612 : return 0;
651 :
652 : /*
653 : * Reject if obj is already present in workspace. This test prevents us
654 : * from going into infinite recursion if we are given a startPoint object
655 : * that links to a cycle it's not a member of, and it guarantees that we
656 : * can't overflow the allocated size of workspace[].
657 : */
658 2461304 : for (i = 0; i < depth; i++)
659 : {
660 887182 : if (workspace[i] == obj)
661 1462 : return 0;
662 : }
663 :
664 : /*
665 : * Okay, tentatively add obj to workspace
666 : */
667 1574122 : workspace[depth++] = obj;
668 :
669 : /*
670 : * See if we've found a loop back to the desired startPoint; if so, done
671 : */
672 38499736 : for (i = 0; i < obj->nDeps; i++)
673 : {
674 36976176 : if (obj->dependencies[i] == startPoint)
675 50562 : return depth;
676 : }
677 :
678 : /*
679 : * Recurse down each outgoing branch
680 : */
681 37694908 : for (i = 0; i < obj->nDeps; i++)
682 : {
683 36222090 : DumpableObject *nextobj = findObjectByDumpId(obj->dependencies[i]);
684 : int newDepth;
685 :
686 36222090 : if (!nextobj)
687 0 : continue; /* ignore dependencies on undumped objects */
688 36222090 : newDepth = findLoop(nextobj,
689 : startPoint,
690 : processed,
691 : searchFailed,
692 : workspace,
693 : depth);
694 36222090 : if (newDepth > 0)
695 50742 : return newDepth;
696 : }
697 :
698 : /*
699 : * Remember there is no path from here back to startPoint
700 : */
701 1472818 : searchFailed[obj->dumpId] = startPoint;
702 :
703 1472818 : return 0;
704 : }
705 :
706 : /*
707 : * A user-defined datatype will have a dependency loop with each of its
708 : * I/O functions (since those have the datatype as input or output).
709 : * Similarly, a range type will have a loop with its canonicalize function,
710 : * if any. Break the loop by making the function depend on the associated
711 : * shell type, instead.
712 : */
713 : static void
714 368 : repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
715 : {
716 368 : TypeInfo *typeInfo = (TypeInfo *) typeobj;
717 :
718 : /* remove function's dependency on type */
719 368 : removeObjectDependency(funcobj, typeobj->dumpId);
720 :
721 : /* add function's dependency on shell type, instead */
722 368 : if (typeInfo->shellType)
723 : {
724 284 : addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
725 :
726 : /*
727 : * Mark shell type (always including the definition, as we need the
728 : * shell type defined to identify the function fully) as to be dumped
729 : * if any such function is
730 : */
731 284 : if (funcobj->dump)
732 284 : typeInfo->shellType->dobj.dump = funcobj->dump |
733 : DUMP_COMPONENT_DEFINITION;
734 : }
735 368 : }
736 :
737 : /*
738 : * Because we force a view to depend on its ON SELECT rule, while there
739 : * will be an implicit dependency in the other direction, we need to break
740 : * the loop. If there are no other objects in the loop then we can remove
741 : * the implicit dependency and leave the ON SELECT rule non-separate.
742 : * This applies to matviews, as well.
743 : */
744 : static void
745 45688 : repairViewRuleLoop(DumpableObject *viewobj,
746 : DumpableObject *ruleobj)
747 : {
748 : /* remove rule's dependency on view */
749 45688 : removeObjectDependency(ruleobj, viewobj->dumpId);
750 : /* flags on the two objects are already set correctly for this case */
751 45688 : }
752 :
753 : /*
754 : * However, if there are other objects in the loop, we must break the loop
755 : * by making the ON SELECT rule a separately-dumped object.
756 : *
757 : * Because findLoop() finds shorter cycles before longer ones, it's likely
758 : * that we will have previously fired repairViewRuleLoop() and removed the
759 : * rule's dependency on the view. Put it back to ensure the rule won't be
760 : * emitted before the view.
761 : *
762 : * Note: this approach does *not* work for matviews, at the moment.
763 : */
764 : static void
765 20 : repairViewRuleMultiLoop(DumpableObject *viewobj,
766 : DumpableObject *ruleobj)
767 : {
768 20 : TableInfo *viewinfo = (TableInfo *) viewobj;
769 20 : RuleInfo *ruleinfo = (RuleInfo *) ruleobj;
770 :
771 : /* remove view's dependency on rule */
772 20 : removeObjectDependency(viewobj, ruleobj->dumpId);
773 : /* mark view to be printed with a dummy definition */
774 20 : viewinfo->dummy_view = true;
775 : /* mark rule as needing its own dump */
776 20 : ruleinfo->separate = true;
777 : /* put back rule's dependency on view */
778 20 : addObjectDependency(ruleobj, viewobj->dumpId);
779 : /* now that rule is separate, it must be post-data */
780 20 : addObjectDependency(ruleobj, postDataBoundId);
781 20 : }
782 :
783 : /*
784 : * If a matview is involved in a multi-object loop, we can't currently fix
785 : * that by splitting off the rule. As a stopgap, we try to fix it by
786 : * dropping the constraint that the matview be dumped in the pre-data section.
787 : * This is sufficient to handle cases where a matview depends on some unique
788 : * index, as can happen if it has a GROUP BY for example.
789 : *
790 : * Note that the "next object" is not necessarily the matview itself;
791 : * it could be the matview's rowtype, for example. We may come through here
792 : * several times while removing all the pre-data linkages. In particular,
793 : * if there are other matviews that depend on the one with the circularity
794 : * problem, we'll come through here for each such matview and mark them all
795 : * as postponed. (This works because all MVs have pre-data dependencies
796 : * to begin with, so each of them will get visited.)
797 : */
798 : static void
799 216 : repairMatViewBoundaryMultiLoop(DumpableObject *boundaryobj,
800 : DumpableObject *nextobj)
801 : {
802 : /* remove boundary's dependency on object after it in loop */
803 216 : removeObjectDependency(boundaryobj, nextobj->dumpId);
804 : /* if that object is a matview, mark it as postponed into post-data */
805 216 : if (nextobj->objType == DO_TABLE)
806 : {
807 72 : TableInfo *nextinfo = (TableInfo *) nextobj;
808 :
809 72 : if (nextinfo->relkind == RELKIND_MATVIEW)
810 72 : nextinfo->postponed_def = true;
811 : }
812 216 : }
813 :
814 : /*
815 : * If a function is involved in a multi-object loop, we can't currently fix
816 : * that by splitting it into two DumpableObjects. As a stopgap, we try to fix
817 : * it by dropping the constraint that the function be dumped in the pre-data
818 : * section. This is sufficient to handle cases where a function depends on
819 : * some unique index, as can happen if it has a GROUP BY for example.
820 : */
821 : static void
822 72 : repairFunctionBoundaryMultiLoop(DumpableObject *boundaryobj,
823 : DumpableObject *nextobj)
824 : {
825 : /* remove boundary's dependency on object after it in loop */
826 72 : removeObjectDependency(boundaryobj, nextobj->dumpId);
827 : /* if that object is a function, mark it as postponed into post-data */
828 72 : if (nextobj->objType == DO_FUNC)
829 : {
830 72 : FuncInfo *nextinfo = (FuncInfo *) nextobj;
831 :
832 72 : nextinfo->postponed_def = true;
833 : }
834 72 : }
835 :
836 : /*
837 : * Because we make tables depend on their CHECK constraints, while there
838 : * will be an automatic dependency in the other direction, we need to break
839 : * the loop. If there are no other objects in the loop then we can remove
840 : * the automatic dependency and leave the CHECK constraint non-separate.
841 : */
842 : static void
843 1046 : repairTableConstraintLoop(DumpableObject *tableobj,
844 : DumpableObject *constraintobj)
845 : {
846 : /* remove constraint's dependency on table */
847 1046 : removeObjectDependency(constraintobj, tableobj->dumpId);
848 1046 : }
849 :
850 : /*
851 : * However, if there are other objects in the loop, we must break the loop
852 : * by making the CHECK constraint a separately-dumped object.
853 : *
854 : * Because findLoop() finds shorter cycles before longer ones, it's likely
855 : * that we will have previously fired repairTableConstraintLoop() and
856 : * removed the constraint's dependency on the table. Put it back to ensure
857 : * the constraint won't be emitted before the table...
858 : */
859 : static void
860 10 : repairTableConstraintMultiLoop(DumpableObject *tableobj,
861 : DumpableObject *constraintobj)
862 : {
863 : /* remove table's dependency on constraint */
864 10 : removeObjectDependency(tableobj, constraintobj->dumpId);
865 : /* mark constraint as needing its own dump */
866 10 : ((ConstraintInfo *) constraintobj)->separate = true;
867 : /* put back constraint's dependency on table */
868 10 : addObjectDependency(constraintobj, tableobj->dumpId);
869 : /* now that constraint is separate, it must be post-data */
870 10 : addObjectDependency(constraintobj, postDataBoundId);
871 10 : }
872 :
873 : /*
874 : * Attribute defaults behave exactly the same as CHECK constraints...
875 : */
876 : static void
877 1312 : repairTableAttrDefLoop(DumpableObject *tableobj,
878 : DumpableObject *attrdefobj)
879 : {
880 : /* remove attrdef's dependency on table */
881 1312 : removeObjectDependency(attrdefobj, tableobj->dumpId);
882 1312 : }
883 :
884 : static void
885 220 : repairTableAttrDefMultiLoop(DumpableObject *tableobj,
886 : DumpableObject *attrdefobj)
887 : {
888 : /* remove table's dependency on attrdef */
889 220 : removeObjectDependency(tableobj, attrdefobj->dumpId);
890 : /* mark attrdef as needing its own dump */
891 220 : ((AttrDefInfo *) attrdefobj)->separate = true;
892 : /* put back attrdef's dependency on table */
893 220 : addObjectDependency(attrdefobj, tableobj->dumpId);
894 220 : }
895 :
896 : /*
897 : * CHECK constraints on domains work just like those on tables ...
898 : */
899 : static void
900 182 : repairDomainConstraintLoop(DumpableObject *domainobj,
901 : DumpableObject *constraintobj)
902 : {
903 : /* remove constraint's dependency on domain */
904 182 : removeObjectDependency(constraintobj, domainobj->dumpId);
905 182 : }
906 :
907 : static void
908 0 : repairDomainConstraintMultiLoop(DumpableObject *domainobj,
909 : DumpableObject *constraintobj)
910 : {
911 : /* remove domain's dependency on constraint */
912 0 : removeObjectDependency(domainobj, constraintobj->dumpId);
913 : /* mark constraint as needing its own dump */
914 0 : ((ConstraintInfo *) constraintobj)->separate = true;
915 : /* put back constraint's dependency on domain */
916 0 : addObjectDependency(constraintobj, domainobj->dumpId);
917 : /* now that constraint is separate, it must be post-data */
918 0 : addObjectDependency(constraintobj, postDataBoundId);
919 0 : }
920 :
921 : static void
922 0 : repairIndexLoop(DumpableObject *partedindex,
923 : DumpableObject *partindex)
924 : {
925 0 : removeObjectDependency(partedindex, partindex->dumpId);
926 0 : }
927 :
928 : /*
929 : * Fix a dependency loop, or die trying ...
930 : *
931 : * This routine is mainly concerned with reducing the multiple ways that
932 : * a loop might appear to common cases, which it passes off to the
933 : * "fixer" routines above.
934 : */
935 : static void
936 50562 : repairDependencyLoop(DumpableObject **loop,
937 : int nLoop)
938 : {
939 : int i,
940 : j;
941 :
942 : /* Datatype and one of its I/O or canonicalize functions */
943 50562 : if (nLoop == 2 &&
944 48596 : loop[0]->objType == DO_TYPE &&
945 182 : loop[1]->objType == DO_FUNC)
946 : {
947 0 : repairTypeFuncLoop(loop[0], loop[1]);
948 0 : return;
949 : }
950 50562 : if (nLoop == 2 &&
951 48596 : loop[1]->objType == DO_TYPE &&
952 368 : loop[0]->objType == DO_FUNC)
953 : {
954 368 : repairTypeFuncLoop(loop[1], loop[0]);
955 368 : return;
956 : }
957 :
958 : /* View (including matview) and its ON SELECT rule */
959 50194 : if (nLoop == 2 &&
960 48228 : loop[0]->objType == DO_TABLE &&
961 48046 : loop[1]->objType == DO_RULE &&
962 45688 : (((TableInfo *) loop[0])->relkind == RELKIND_VIEW ||
963 886 : ((TableInfo *) loop[0])->relkind == RELKIND_MATVIEW) &&
964 45688 : ((RuleInfo *) loop[1])->ev_type == '1' &&
965 45688 : ((RuleInfo *) loop[1])->is_instead &&
966 45688 : ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
967 : {
968 45688 : repairViewRuleLoop(loop[0], loop[1]);
969 45688 : return;
970 : }
971 4506 : if (nLoop == 2 &&
972 2540 : loop[1]->objType == DO_TABLE &&
973 0 : loop[0]->objType == DO_RULE &&
974 0 : (((TableInfo *) loop[1])->relkind == RELKIND_VIEW ||
975 0 : ((TableInfo *) loop[1])->relkind == RELKIND_MATVIEW) &&
976 0 : ((RuleInfo *) loop[0])->ev_type == '1' &&
977 0 : ((RuleInfo *) loop[0])->is_instead &&
978 0 : ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
979 : {
980 0 : repairViewRuleLoop(loop[1], loop[0]);
981 0 : return;
982 : }
983 :
984 : /* Indirect loop involving view (but not matview) and ON SELECT rule */
985 4506 : if (nLoop > 2)
986 : {
987 3102 : for (i = 0; i < nLoop; i++)
988 : {
989 2584 : if (loop[i]->objType == DO_TABLE &&
990 686 : ((TableInfo *) loop[i])->relkind == RELKIND_VIEW)
991 : {
992 40 : for (j = 0; j < nLoop; j++)
993 : {
994 40 : if (loop[j]->objType == DO_RULE &&
995 20 : ((RuleInfo *) loop[j])->ev_type == '1' &&
996 20 : ((RuleInfo *) loop[j])->is_instead &&
997 20 : ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
998 : {
999 20 : repairViewRuleMultiLoop(loop[i], loop[j]);
1000 20 : return;
1001 : }
1002 : }
1003 : }
1004 : }
1005 : }
1006 :
1007 : /* Indirect loop involving matview and data boundary */
1008 4486 : if (nLoop > 2)
1009 : {
1010 1576 : for (i = 0; i < nLoop; i++)
1011 : {
1012 1274 : if (loop[i]->objType == DO_TABLE &&
1013 666 : ((TableInfo *) loop[i])->relkind == RELKIND_MATVIEW)
1014 : {
1015 1290 : for (j = 0; j < nLoop; j++)
1016 : {
1017 1290 : if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
1018 : {
1019 : DumpableObject *nextobj;
1020 :
1021 216 : nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
1022 216 : repairMatViewBoundaryMultiLoop(loop[j], nextobj);
1023 216 : return;
1024 : }
1025 : }
1026 : }
1027 : }
1028 : }
1029 :
1030 : /* Indirect loop involving function and data boundary */
1031 4270 : if (nLoop > 2)
1032 : {
1033 1002 : for (i = 0; i < nLoop; i++)
1034 : {
1035 772 : if (loop[i]->objType == DO_FUNC)
1036 : {
1037 408 : for (j = 0; j < nLoop; j++)
1038 : {
1039 398 : if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
1040 : {
1041 : DumpableObject *nextobj;
1042 :
1043 72 : nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
1044 72 : repairFunctionBoundaryMultiLoop(loop[j], nextobj);
1045 72 : return;
1046 : }
1047 : }
1048 : }
1049 : }
1050 : }
1051 :
1052 : /* Table and CHECK constraint */
1053 4198 : if (nLoop == 2 &&
1054 2540 : loop[0]->objType == DO_TABLE &&
1055 2358 : loop[1]->objType == DO_CONSTRAINT &&
1056 1046 : ((ConstraintInfo *) loop[1])->contype == 'c' &&
1057 1046 : ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
1058 : {
1059 1046 : repairTableConstraintLoop(loop[0], loop[1]);
1060 1046 : return;
1061 : }
1062 3152 : if (nLoop == 2 &&
1063 1494 : loop[1]->objType == DO_TABLE &&
1064 0 : loop[0]->objType == DO_CONSTRAINT &&
1065 0 : ((ConstraintInfo *) loop[0])->contype == 'c' &&
1066 0 : ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
1067 : {
1068 0 : repairTableConstraintLoop(loop[1], loop[0]);
1069 0 : return;
1070 : }
1071 :
1072 : /* Indirect loop involving table and CHECK constraint */
1073 3152 : if (nLoop > 2)
1074 : {
1075 890 : for (i = 0; i < nLoop; i++)
1076 : {
1077 670 : if (loop[i]->objType == DO_TABLE)
1078 : {
1079 1780 : for (j = 0; j < nLoop; j++)
1080 : {
1081 1340 : if (loop[j]->objType == DO_CONSTRAINT &&
1082 10 : ((ConstraintInfo *) loop[j])->contype == 'c' &&
1083 10 : ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
1084 : {
1085 10 : repairTableConstraintMultiLoop(loop[i], loop[j]);
1086 10 : return;
1087 : }
1088 : }
1089 : }
1090 : }
1091 : }
1092 :
1093 : /* Table and attribute default */
1094 3142 : if (nLoop == 2 &&
1095 1494 : loop[0]->objType == DO_TABLE &&
1096 1312 : loop[1]->objType == DO_ATTRDEF &&
1097 1312 : ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
1098 : {
1099 1312 : repairTableAttrDefLoop(loop[0], loop[1]);
1100 1312 : return;
1101 : }
1102 1830 : if (nLoop == 2 &&
1103 182 : loop[1]->objType == DO_TABLE &&
1104 0 : loop[0]->objType == DO_ATTRDEF &&
1105 0 : ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
1106 : {
1107 0 : repairTableAttrDefLoop(loop[1], loop[0]);
1108 0 : return;
1109 : }
1110 :
1111 : /* index on partitioned table and corresponding index on partition */
1112 1830 : if (nLoop == 2 &&
1113 182 : loop[0]->objType == DO_INDEX &&
1114 0 : loop[1]->objType == DO_INDEX)
1115 : {
1116 0 : if (((IndxInfo *) loop[0])->parentidx == loop[1]->catId.oid)
1117 : {
1118 0 : repairIndexLoop(loop[0], loop[1]);
1119 0 : return;
1120 : }
1121 0 : else if (((IndxInfo *) loop[1])->parentidx == loop[0]->catId.oid)
1122 : {
1123 0 : repairIndexLoop(loop[1], loop[0]);
1124 0 : return;
1125 : }
1126 : }
1127 :
1128 : /* Indirect loop involving table and attribute default */
1129 1830 : if (nLoop > 2)
1130 : {
1131 440 : for (i = 0; i < nLoop; i++)
1132 : {
1133 440 : if (loop[i]->objType == DO_TABLE)
1134 : {
1135 1540 : for (j = 0; j < nLoop; j++)
1136 : {
1137 1320 : if (loop[j]->objType == DO_ATTRDEF &&
1138 440 : ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
1139 : {
1140 220 : repairTableAttrDefMultiLoop(loop[i], loop[j]);
1141 220 : return;
1142 : }
1143 : }
1144 : }
1145 : }
1146 : }
1147 :
1148 : /* Domain and CHECK constraint */
1149 1610 : if (nLoop == 2 &&
1150 182 : loop[0]->objType == DO_TYPE &&
1151 182 : loop[1]->objType == DO_CONSTRAINT &&
1152 182 : ((ConstraintInfo *) loop[1])->contype == 'c' &&
1153 182 : ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
1154 : {
1155 182 : repairDomainConstraintLoop(loop[0], loop[1]);
1156 182 : return;
1157 : }
1158 1428 : if (nLoop == 2 &&
1159 0 : loop[1]->objType == DO_TYPE &&
1160 0 : loop[0]->objType == DO_CONSTRAINT &&
1161 0 : ((ConstraintInfo *) loop[0])->contype == 'c' &&
1162 0 : ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
1163 : {
1164 0 : repairDomainConstraintLoop(loop[1], loop[0]);
1165 0 : return;
1166 : }
1167 :
1168 : /* Indirect loop involving domain and CHECK constraint */
1169 1428 : if (nLoop > 2)
1170 : {
1171 0 : for (i = 0; i < nLoop; i++)
1172 : {
1173 0 : if (loop[i]->objType == DO_TYPE)
1174 : {
1175 0 : for (j = 0; j < nLoop; j++)
1176 : {
1177 0 : if (loop[j]->objType == DO_CONSTRAINT &&
1178 0 : ((ConstraintInfo *) loop[j])->contype == 'c' &&
1179 0 : ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
1180 : {
1181 0 : repairDomainConstraintMultiLoop(loop[i], loop[j]);
1182 0 : return;
1183 : }
1184 : }
1185 : }
1186 : }
1187 : }
1188 :
1189 : /*
1190 : * Loop of table with itself --- just ignore it.
1191 : *
1192 : * (Actually, what this arises from is a dependency of a table column on
1193 : * another column, which happened with generated columns before v15; or a
1194 : * dependency of a table column on the whole table, which happens with
1195 : * partitioning. But we didn't pay attention to sub-object IDs while
1196 : * collecting the dependency data, so we can't see that here.)
1197 : */
1198 1428 : if (nLoop == 1)
1199 : {
1200 1428 : if (loop[0]->objType == DO_TABLE)
1201 : {
1202 1428 : removeObjectDependency(loop[0], loop[0]->dumpId);
1203 1428 : return;
1204 : }
1205 : }
1206 :
1207 : /*
1208 : * If all the objects are TABLE_DATA items, what we must have is a
1209 : * circular set of foreign key constraints (or a single self-referential
1210 : * table). Print an appropriate complaint and break the loop arbitrarily.
1211 : */
1212 0 : for (i = 0; i < nLoop; i++)
1213 : {
1214 0 : if (loop[i]->objType != DO_TABLE_DATA)
1215 0 : break;
1216 : }
1217 0 : if (i >= nLoop)
1218 : {
1219 0 : pg_log_warning(ngettext("there are circular foreign-key constraints on this table:",
1220 : "there are circular foreign-key constraints among these tables:",
1221 : nLoop));
1222 0 : for (i = 0; i < nLoop; i++)
1223 0 : pg_log_warning_detail("%s", loop[i]->name);
1224 0 : pg_log_warning_hint("You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.");
1225 0 : pg_log_warning_hint("Consider using a full dump instead of a --data-only dump to avoid this problem.");
1226 0 : if (nLoop > 1)
1227 0 : removeObjectDependency(loop[0], loop[1]->dumpId);
1228 : else /* must be a self-dependency */
1229 0 : removeObjectDependency(loop[0], loop[0]->dumpId);
1230 0 : return;
1231 : }
1232 :
1233 : /*
1234 : * If we can't find a principled way to break the loop, complain and break
1235 : * it in an arbitrary fashion.
1236 : */
1237 0 : pg_log_warning("could not resolve dependency loop among these items:");
1238 0 : for (i = 0; i < nLoop; i++)
1239 : {
1240 : char buf[1024];
1241 :
1242 0 : describeDumpableObject(loop[i], buf, sizeof(buf));
1243 0 : pg_log_warning_detail("%s", buf);
1244 : }
1245 :
1246 0 : if (nLoop > 1)
1247 0 : removeObjectDependency(loop[0], loop[1]->dumpId);
1248 : else /* must be a self-dependency */
1249 0 : removeObjectDependency(loop[0], loop[0]->dumpId);
1250 : }
1251 :
1252 : /*
1253 : * Describe a dumpable object usefully for errors
1254 : *
1255 : * This should probably go somewhere else...
1256 : */
1257 : static void
1258 0 : describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
1259 : {
1260 0 : switch (obj->objType)
1261 : {
1262 0 : case DO_NAMESPACE:
1263 0 : snprintf(buf, bufsize,
1264 : "SCHEMA %s (ID %d OID %u)",
1265 : obj->name, obj->dumpId, obj->catId.oid);
1266 0 : return;
1267 0 : case DO_EXTENSION:
1268 0 : snprintf(buf, bufsize,
1269 : "EXTENSION %s (ID %d OID %u)",
1270 : obj->name, obj->dumpId, obj->catId.oid);
1271 0 : return;
1272 0 : case DO_TYPE:
1273 0 : snprintf(buf, bufsize,
1274 : "TYPE %s (ID %d OID %u)",
1275 : obj->name, obj->dumpId, obj->catId.oid);
1276 0 : return;
1277 0 : case DO_SHELL_TYPE:
1278 0 : snprintf(buf, bufsize,
1279 : "SHELL TYPE %s (ID %d OID %u)",
1280 : obj->name, obj->dumpId, obj->catId.oid);
1281 0 : return;
1282 0 : case DO_FUNC:
1283 0 : snprintf(buf, bufsize,
1284 : "FUNCTION %s (ID %d OID %u)",
1285 : obj->name, obj->dumpId, obj->catId.oid);
1286 0 : return;
1287 0 : case DO_AGG:
1288 0 : snprintf(buf, bufsize,
1289 : "AGGREGATE %s (ID %d OID %u)",
1290 : obj->name, obj->dumpId, obj->catId.oid);
1291 0 : return;
1292 0 : case DO_OPERATOR:
1293 0 : snprintf(buf, bufsize,
1294 : "OPERATOR %s (ID %d OID %u)",
1295 : obj->name, obj->dumpId, obj->catId.oid);
1296 0 : return;
1297 0 : case DO_ACCESS_METHOD:
1298 0 : snprintf(buf, bufsize,
1299 : "ACCESS METHOD %s (ID %d OID %u)",
1300 : obj->name, obj->dumpId, obj->catId.oid);
1301 0 : return;
1302 0 : case DO_OPCLASS:
1303 0 : snprintf(buf, bufsize,
1304 : "OPERATOR CLASS %s (ID %d OID %u)",
1305 : obj->name, obj->dumpId, obj->catId.oid);
1306 0 : return;
1307 0 : case DO_OPFAMILY:
1308 0 : snprintf(buf, bufsize,
1309 : "OPERATOR FAMILY %s (ID %d OID %u)",
1310 : obj->name, obj->dumpId, obj->catId.oid);
1311 0 : return;
1312 0 : case DO_COLLATION:
1313 0 : snprintf(buf, bufsize,
1314 : "COLLATION %s (ID %d OID %u)",
1315 : obj->name, obj->dumpId, obj->catId.oid);
1316 0 : return;
1317 0 : case DO_CONVERSION:
1318 0 : snprintf(buf, bufsize,
1319 : "CONVERSION %s (ID %d OID %u)",
1320 : obj->name, obj->dumpId, obj->catId.oid);
1321 0 : return;
1322 0 : case DO_TABLE:
1323 0 : snprintf(buf, bufsize,
1324 : "TABLE %s (ID %d OID %u)",
1325 : obj->name, obj->dumpId, obj->catId.oid);
1326 0 : return;
1327 0 : case DO_TABLE_ATTACH:
1328 0 : snprintf(buf, bufsize,
1329 : "TABLE ATTACH %s (ID %d)",
1330 : obj->name, obj->dumpId);
1331 0 : return;
1332 0 : case DO_ATTRDEF:
1333 0 : snprintf(buf, bufsize,
1334 : "ATTRDEF %s.%s (ID %d OID %u)",
1335 0 : ((AttrDefInfo *) obj)->adtable->dobj.name,
1336 0 : ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
1337 : obj->dumpId, obj->catId.oid);
1338 0 : return;
1339 0 : case DO_INDEX:
1340 0 : snprintf(buf, bufsize,
1341 : "INDEX %s (ID %d OID %u)",
1342 : obj->name, obj->dumpId, obj->catId.oid);
1343 0 : return;
1344 0 : case DO_INDEX_ATTACH:
1345 0 : snprintf(buf, bufsize,
1346 : "INDEX ATTACH %s (ID %d)",
1347 : obj->name, obj->dumpId);
1348 0 : return;
1349 0 : case DO_STATSEXT:
1350 0 : snprintf(buf, bufsize,
1351 : "STATISTICS %s (ID %d OID %u)",
1352 : obj->name, obj->dumpId, obj->catId.oid);
1353 0 : return;
1354 0 : case DO_REFRESH_MATVIEW:
1355 0 : snprintf(buf, bufsize,
1356 : "REFRESH MATERIALIZED VIEW %s (ID %d OID %u)",
1357 : obj->name, obj->dumpId, obj->catId.oid);
1358 0 : return;
1359 0 : case DO_RULE:
1360 0 : snprintf(buf, bufsize,
1361 : "RULE %s (ID %d OID %u)",
1362 : obj->name, obj->dumpId, obj->catId.oid);
1363 0 : return;
1364 0 : case DO_TRIGGER:
1365 0 : snprintf(buf, bufsize,
1366 : "TRIGGER %s (ID %d OID %u)",
1367 : obj->name, obj->dumpId, obj->catId.oid);
1368 0 : return;
1369 0 : case DO_EVENT_TRIGGER:
1370 0 : snprintf(buf, bufsize,
1371 : "EVENT TRIGGER %s (ID %d OID %u)",
1372 : obj->name, obj->dumpId, obj->catId.oid);
1373 0 : return;
1374 0 : case DO_CONSTRAINT:
1375 0 : snprintf(buf, bufsize,
1376 : "CONSTRAINT %s (ID %d OID %u)",
1377 : obj->name, obj->dumpId, obj->catId.oid);
1378 0 : return;
1379 0 : case DO_FK_CONSTRAINT:
1380 0 : snprintf(buf, bufsize,
1381 : "FK CONSTRAINT %s (ID %d OID %u)",
1382 : obj->name, obj->dumpId, obj->catId.oid);
1383 0 : return;
1384 0 : case DO_PROCLANG:
1385 0 : snprintf(buf, bufsize,
1386 : "PROCEDURAL LANGUAGE %s (ID %d OID %u)",
1387 : obj->name, obj->dumpId, obj->catId.oid);
1388 0 : return;
1389 0 : case DO_CAST:
1390 0 : snprintf(buf, bufsize,
1391 : "CAST %u to %u (ID %d OID %u)",
1392 : ((CastInfo *) obj)->castsource,
1393 : ((CastInfo *) obj)->casttarget,
1394 : obj->dumpId, obj->catId.oid);
1395 0 : return;
1396 0 : case DO_TRANSFORM:
1397 0 : snprintf(buf, bufsize,
1398 : "TRANSFORM %u lang %u (ID %d OID %u)",
1399 : ((TransformInfo *) obj)->trftype,
1400 : ((TransformInfo *) obj)->trflang,
1401 : obj->dumpId, obj->catId.oid);
1402 0 : return;
1403 0 : case DO_TABLE_DATA:
1404 0 : snprintf(buf, bufsize,
1405 : "TABLE DATA %s (ID %d OID %u)",
1406 : obj->name, obj->dumpId, obj->catId.oid);
1407 0 : return;
1408 0 : case DO_SEQUENCE_SET:
1409 0 : snprintf(buf, bufsize,
1410 : "SEQUENCE SET %s (ID %d OID %u)",
1411 : obj->name, obj->dumpId, obj->catId.oid);
1412 0 : return;
1413 0 : case DO_DUMMY_TYPE:
1414 0 : snprintf(buf, bufsize,
1415 : "DUMMY TYPE %s (ID %d OID %u)",
1416 : obj->name, obj->dumpId, obj->catId.oid);
1417 0 : return;
1418 0 : case DO_TSPARSER:
1419 0 : snprintf(buf, bufsize,
1420 : "TEXT SEARCH PARSER %s (ID %d OID %u)",
1421 : obj->name, obj->dumpId, obj->catId.oid);
1422 0 : return;
1423 0 : case DO_TSDICT:
1424 0 : snprintf(buf, bufsize,
1425 : "TEXT SEARCH DICTIONARY %s (ID %d OID %u)",
1426 : obj->name, obj->dumpId, obj->catId.oid);
1427 0 : return;
1428 0 : case DO_TSTEMPLATE:
1429 0 : snprintf(buf, bufsize,
1430 : "TEXT SEARCH TEMPLATE %s (ID %d OID %u)",
1431 : obj->name, obj->dumpId, obj->catId.oid);
1432 0 : return;
1433 0 : case DO_TSCONFIG:
1434 0 : snprintf(buf, bufsize,
1435 : "TEXT SEARCH CONFIGURATION %s (ID %d OID %u)",
1436 : obj->name, obj->dumpId, obj->catId.oid);
1437 0 : return;
1438 0 : case DO_FDW:
1439 0 : snprintf(buf, bufsize,
1440 : "FOREIGN DATA WRAPPER %s (ID %d OID %u)",
1441 : obj->name, obj->dumpId, obj->catId.oid);
1442 0 : return;
1443 0 : case DO_FOREIGN_SERVER:
1444 0 : snprintf(buf, bufsize,
1445 : "FOREIGN SERVER %s (ID %d OID %u)",
1446 : obj->name, obj->dumpId, obj->catId.oid);
1447 0 : return;
1448 0 : case DO_DEFAULT_ACL:
1449 0 : snprintf(buf, bufsize,
1450 : "DEFAULT ACL %s (ID %d OID %u)",
1451 : obj->name, obj->dumpId, obj->catId.oid);
1452 0 : return;
1453 0 : case DO_LARGE_OBJECT:
1454 0 : snprintf(buf, bufsize,
1455 : "LARGE OBJECT (ID %d OID %u)",
1456 : obj->dumpId, obj->catId.oid);
1457 0 : return;
1458 0 : case DO_LARGE_OBJECT_DATA:
1459 0 : snprintf(buf, bufsize,
1460 : "LARGE OBJECT DATA (ID %d)",
1461 : obj->dumpId);
1462 0 : return;
1463 0 : case DO_POLICY:
1464 0 : snprintf(buf, bufsize,
1465 : "POLICY (ID %d OID %u)",
1466 : obj->dumpId, obj->catId.oid);
1467 0 : return;
1468 0 : case DO_PUBLICATION:
1469 0 : snprintf(buf, bufsize,
1470 : "PUBLICATION (ID %d OID %u)",
1471 : obj->dumpId, obj->catId.oid);
1472 0 : return;
1473 0 : case DO_PUBLICATION_REL:
1474 0 : snprintf(buf, bufsize,
1475 : "PUBLICATION TABLE (ID %d OID %u)",
1476 : obj->dumpId, obj->catId.oid);
1477 0 : return;
1478 0 : case DO_PUBLICATION_TABLE_IN_SCHEMA:
1479 0 : snprintf(buf, bufsize,
1480 : "PUBLICATION TABLES IN SCHEMA (ID %d OID %u)",
1481 : obj->dumpId, obj->catId.oid);
1482 0 : return;
1483 0 : case DO_SUBSCRIPTION:
1484 0 : snprintf(buf, bufsize,
1485 : "SUBSCRIPTION (ID %d OID %u)",
1486 : obj->dumpId, obj->catId.oid);
1487 0 : return;
1488 0 : case DO_SUBSCRIPTION_REL:
1489 0 : snprintf(buf, bufsize,
1490 : "SUBSCRIPTION TABLE (ID %d OID %u)",
1491 : obj->dumpId, obj->catId.oid);
1492 0 : return;
1493 0 : case DO_PRE_DATA_BOUNDARY:
1494 0 : snprintf(buf, bufsize,
1495 : "PRE-DATA BOUNDARY (ID %d)",
1496 : obj->dumpId);
1497 0 : return;
1498 0 : case DO_POST_DATA_BOUNDARY:
1499 0 : snprintf(buf, bufsize,
1500 : "POST-DATA BOUNDARY (ID %d)",
1501 : obj->dumpId);
1502 0 : return;
1503 : }
1504 : /* shouldn't get here */
1505 0 : snprintf(buf, bufsize,
1506 : "object type %d (ID %d OID %u)",
1507 0 : (int) obj->objType,
1508 : obj->dumpId, obj->catId.oid);
1509 : }
1510 :
1511 : /* binaryheap comparator that compares "a" and "b" as integers */
1512 : static int
1513 45158568 : int_cmp(void *a, void *b, void *arg)
1514 : {
1515 45158568 : int ai = (int) (intptr_t) a;
1516 45158568 : int bi = (int) (intptr_t) b;
1517 :
1518 45158568 : return pg_cmp_s32(ai, bi);
1519 : }
|
