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