LCOV - code coverage report
Current view: top level - src/bin/pg_dump - pg_dump_sort.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 309 535 57.8 %
Date: 2020-05-25 05:06:35 Functions: 17 21 81.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13