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

Generated by: LCOV version 1.14