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