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