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

Generated by: LCOV version 1.13