granicus.if.org Git - postgresql/blob - src/bin/pg_dump/pg_dump_sort.c

   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-2011, 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 "pg_backup_archiver.h"
  17
  18
  19 static const char *modulename = gettext_noop("sorter");
  20
  21 /*
  22  * Sort priority for object types when dumping a pre-7.3 database.
  23  * Objects are sorted by priority levels, and within an equal priority level
  24  * by OID.      (This is a relatively crude hack to provide semi-reasonable
  25  * behavior for old databases without full dependency info.)  Note: extensions,
  26  * text search, foreign-data, and default ACL objects can't really happen here,
  27  * so the rather bogus priorities for them don't matter.
  28  */
  29 static const int oldObjectTypePriority[] =
  30 {
  31         1,                                                      /* DO_NAMESPACE */
  32         1,                                                      /* DO_EXTENSION */
  33         2,                                                      /* DO_TYPE */
  34         2,                                                      /* DO_SHELL_TYPE */
  35         2,                                                      /* DO_FUNC */
  36         3,                                                      /* DO_AGG */
  37         3,                                                      /* DO_OPERATOR */
  38         4,                                                      /* DO_OPCLASS */
  39         4,                                                      /* DO_OPFAMILY */
  40         5,                                                      /* DO_CONVERSION */
  41         6,                                                      /* DO_TABLE */
  42         8,                                                      /* DO_ATTRDEF */
  43         13,                                                     /* DO_INDEX */
  44         14,                                                     /* DO_RULE */
  45         15,                                                     /* DO_TRIGGER */
  46         12,                                                     /* DO_CONSTRAINT */
  47         16,                                                     /* DO_FK_CONSTRAINT */
  48         2,                                                      /* DO_PROCLANG */
  49         2,                                                      /* DO_CAST */
  50         10,                                                     /* DO_TABLE_DATA */
  51         7,                                                      /* DO_DUMMY_TYPE */
  52         3,                                                      /* DO_TSPARSER */
  53         4,                                                      /* DO_TSDICT */
  54         3,                                                      /* DO_TSTEMPLATE */
  55         5,                                                      /* DO_TSCONFIG */
  56         3,                                                      /* DO_FDW */
  57         4,                                                      /* DO_FOREIGN_SERVER */
  58         17,                                                     /* DO_DEFAULT_ACL */
  59         9,                                                      /* DO_BLOB */
  60         11                                                      /* DO_BLOB_DATA */
  61 };
  62
  63 /*
  64  * Sort priority for object types when dumping newer databases.
  65  * Objects are sorted by type, and within a type by name.
  66  */
  67 static const int newObjectTypePriority[] =
  68 {
  69         1,                                                      /* DO_NAMESPACE */
  70         3,                                                      /* DO_EXTENSION */
  71         4,                                                      /* DO_TYPE */
  72         4,                                                      /* DO_SHELL_TYPE */
  73         5,                                                      /* DO_FUNC */
  74         6,                                                      /* DO_AGG */
  75         7,                                                      /* DO_OPERATOR */
  76         8,                                                      /* DO_OPCLASS */
  77         8,                                                      /* DO_OPFAMILY */
  78         10,                                                     /* DO_CONVERSION */
  79         17,                                                     /* DO_TABLE */
  80         19,                                                     /* DO_ATTRDEF */
  81         24,                                                     /* DO_INDEX */
  82         25,                                                     /* DO_RULE */
  83         26,                                                     /* DO_TRIGGER */
  84         23,                                                     /* DO_CONSTRAINT */
  85         27,                                                     /* DO_FK_CONSTRAINT */
  86         2,                                                      /* DO_PROCLANG */
  87         9,                                                      /* DO_CAST */
  88         21,                                                     /* DO_TABLE_DATA */
  89         18,                                                     /* DO_DUMMY_TYPE */
  90         11,                                                     /* DO_TSPARSER */
  91         13,                                                     /* DO_TSDICT */
  92         12,                                                     /* DO_TSTEMPLATE */
  93         14,                                                     /* DO_TSCONFIG */
  94         15,                                                     /* DO_FDW */
  95         16,                                                     /* DO_FOREIGN_SERVER */
  96         28,                                                     /* DO_DEFAULT_ACL */
  97         20,                                                     /* DO_BLOB */
  98         22                                                      /* DO_BLOB_DATA */
  99 };
 100
 101
 102 static int      DOTypeNameCompare(const void *p1, const void *p2);
 103 static int      DOTypeOidCompare(const void *p1, const void *p2);
 104 static bool TopoSort(DumpableObject **objs,
 105                  int numObjs,
 106                  DumpableObject **ordering,
 107                  int *nOrdering);
 108 static void addHeapElement(int val, int *heap, int heapLength);
 109 static int      removeHeapElement(int *heap, int heapLength);
 110 static void findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs);
 111 static bool findLoop(DumpableObject *obj,
 112                  DumpId startPoint,
 113                  DumpableObject **workspace,
 114                  int depth,
 115                  int *newDepth);
 116 static void repairDependencyLoop(DumpableObject **loop,
 117                                          int nLoop);
 118 static void describeDumpableObject(DumpableObject *obj,
 119                                            char *buf, int bufsize);
 120
 121
 122 /*
 123  * Sort the given objects into a type/name-based ordering
 124  *
 125  * Normally this is just the starting point for the dependency-based
 126  * ordering.
 127  */
 128 void
 129 sortDumpableObjectsByTypeName(DumpableObject **objs, int numObjs)
 130 {
 131         if (numObjs > 1)
 132                 qsort((void *) objs, numObjs, sizeof(DumpableObject *),
 133                           DOTypeNameCompare);
 134 }
 135
 136 static int
 137 DOTypeNameCompare(const void *p1, const void *p2)
 138 {
 139         DumpableObject *obj1 = *(DumpableObject **) p1;
 140         DumpableObject *obj2 = *(DumpableObject **) p2;
 141         int                     cmpval;
 142
 143         /* Sort by type */
 144         cmpval = newObjectTypePriority[obj1->objType] -
 145                 newObjectTypePriority[obj2->objType];
 146
 147         if (cmpval != 0)
 148                 return cmpval;
 149
 150         /*
 151          * Sort by namespace.  Note that all objects of the same type should
 152          * either have or not have a namespace link, so we needn't be fancy about
 153          * cases where one link is null and the other not.
 154          */
 155         if (obj1->namespace && obj2->namespace)
 156         {
 157                 cmpval = strcmp(obj1->namespace->dobj.name,
 158                                                 obj2->namespace->dobj.name);
 159                 if (cmpval != 0)
 160                         return cmpval;
 161         }
 162
 163         /* Sort by name */
 164         cmpval = strcmp(obj1->name, obj2->name);
 165         if (cmpval != 0)
 166                 return cmpval;
 167
 168         /* To have a stable sort order, break ties for some object types */
 169         if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
 170         {
 171                 FuncInfo   *fobj1 = *(FuncInfo **) p1;
 172                 FuncInfo   *fobj2 = *(FuncInfo **) p2;
 173
 174                 cmpval = fobj1->nargs - fobj2->nargs;
 175                 if (cmpval != 0)
 176                         return cmpval;
 177         }
 178
 179         /* Usually shouldn't get here, but if we do, sort by OID */
 180         return oidcmp(obj1->catId.oid, obj2->catId.oid);
 181 }
 182
 183
 184 /*
 185  * Sort the given objects into a type/OID-based ordering
 186  *
 187  * This is used with pre-7.3 source databases as a crude substitute for the
 188  * lack of dependency information.
 189  */
 190 void
 191 sortDumpableObjectsByTypeOid(DumpableObject **objs, int numObjs)
 192 {
 193         if (numObjs > 1)
 194                 qsort((void *) objs, numObjs, sizeof(DumpableObject *),
 195                           DOTypeOidCompare);
 196 }
 197
 198 static int
 199 DOTypeOidCompare(const void *p1, const void *p2)
 200 {
 201         DumpableObject *obj1 = *(DumpableObject **) p1;
 202         DumpableObject *obj2 = *(DumpableObject **) p2;
 203         int                     cmpval;
 204
 205         cmpval = oldObjectTypePriority[obj1->objType] -
 206                 oldObjectTypePriority[obj2->objType];
 207
 208         if (cmpval != 0)
 209                 return cmpval;
 210
 211         return oidcmp(obj1->catId.oid, obj2->catId.oid);
 212 }
 213
 214
 215 /*
 216  * Sort the given objects into a safe dump order using dependency
 217  * information (to the extent we have it available).
 218  */
 219 void
 220 sortDumpableObjects(DumpableObject **objs, int numObjs)
 221 {
 222         DumpableObject **ordering;
 223         int                     nOrdering;
 224
 225         if (numObjs <= 0)
 226                 return;
 227
 228         ordering = (DumpableObject **) malloc(numObjs * sizeof(DumpableObject *));
 229         if (ordering == NULL)
 230                 exit_horribly(NULL, modulename, "out of memory\n");
 231
 232         while (!TopoSort(objs, numObjs, ordering, &nOrdering))
 233                 findDependencyLoops(ordering, nOrdering, numObjs);
 234
 235         memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));
 236
 237         free(ordering);
 238 }
 239
 240 /*
 241  * TopoSort -- topological sort of a dump list
 242  *
 243  * Generate a re-ordering of the dump list that satisfies all the dependency
 244  * constraints shown in the dump list.  (Each such constraint is a fact of a
 245  * partial ordering.)  Minimize rearrangement of the list not needed to
 246  * achieve the partial ordering.
 247  *
 248  * The input is the list of numObjs objects in objs[].  This list is not
 249  * modified.
 250  *
 251  * Returns TRUE if able to build an ordering that satisfies all the
 252  * constraints, FALSE if not (there are contradictory constraints).
 253  *
 254  * On success (TRUE result), ordering[] is filled with a sorted array of
 255  * DumpableObject pointers, of length equal to the input list length.
 256  *
 257  * On failure (FALSE result), ordering[] is filled with an unsorted array of
 258  * DumpableObject pointers of length *nOrdering, listing the objects that
 259  * prevented the sort from being completed.  In general, these objects either
 260  * participate directly in a dependency cycle, or are depended on by objects
 261  * that are in a cycle.  (The latter objects are not actually problematic,
 262  * but it takes further analysis to identify which are which.)
 263  *
 264  * The caller is responsible for allocating sufficient space at *ordering.
 265  */
 266 static bool
 267 TopoSort(DumpableObject **objs,
 268                  int numObjs,
 269                  DumpableObject **ordering,             /* output argument */
 270                  int *nOrdering)                /* output argument */
 271 {
 272         DumpId          maxDumpId = getMaxDumpId();
 273         int                *pendingHeap;
 274         int                *beforeConstraints;
 275         int                *idMap;
 276         DumpableObject *obj;
 277         int                     heapLength;
 278         int                     i,
 279                                 j,
 280                                 k;
 281
 282         /*
 283          * This is basically the same algorithm shown for topological sorting in
 284          * Knuth's Volume 1.  However, we would like to minimize unnecessary
 285          * rearrangement of the input ordering; that is, when we have a choice of
 286          * which item to output next, we always want to take the one highest in
 287          * the original list.  Therefore, instead of maintaining an unordered
 288          * linked list of items-ready-to-output as Knuth does, we maintain a heap
 289          * of their item numbers, which we can use as a priority queue.  This
 290          * turns the algorithm from O(N) to O(N log N) because each insertion or
 291          * removal of a heap item takes O(log N) time.  However, that's still
 292          * plenty fast enough for this application.
 293          */
 294
 295         *nOrdering = numObjs;           /* for success return */
 296
 297         /* Eliminate the null case */
 298         if (numObjs <= 0)
 299                 return true;
 300
 301         /* Create workspace for the above-described heap */
 302         pendingHeap = (int *) malloc(numObjs * sizeof(int));
 303         if (pendingHeap == NULL)
 304                 exit_horribly(NULL, modulename, "out of memory\n");
 305
 306         /*
 307          * Scan the constraints, and for each item in the input, generate a count
 308          * of the number of constraints that say it must be before something else.
 309          * The count for the item with dumpId j is stored in beforeConstraints[j].
 310          * We also make a map showing the input-order index of the item with
 311          * dumpId j.
 312          */
 313         beforeConstraints = (int *) malloc((maxDumpId + 1) * sizeof(int));
 314         if (beforeConstraints == NULL)
 315                 exit_horribly(NULL, modulename, "out of memory\n");
 316         memset(beforeConstraints, 0, (maxDumpId + 1) * sizeof(int));
 317         idMap = (int *) malloc((maxDumpId + 1) * sizeof(int));
 318         if (idMap == NULL)
 319                 exit_horribly(NULL, modulename, "out of memory\n");
 320         for (i = 0; i < numObjs; i++)
 321         {
 322                 obj = objs[i];
 323                 j = obj->dumpId;
 324                 if (j <= 0 || j > maxDumpId)
 325                         exit_horribly(NULL, modulename, "invalid dumpId %d\n", j);
 326                 idMap[j] = i;
 327                 for (j = 0; j < obj->nDeps; j++)
 328                 {
 329                         k = obj->dependencies[j];
 330                         if (k <= 0 || k > maxDumpId)
 331                                 exit_horribly(NULL, modulename, "invalid dependency %d\n", k);
 332                         beforeConstraints[k]++;
 333                 }
 334         }
 335
 336         /*
 337          * Now initialize the heap of items-ready-to-output by filling it with the
 338          * indexes of items that already have beforeConstraints[id] == 0.
 339          *
 340          * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
 341          * in the range 1..heapLength-1 (note we are using 0-based subscripts
 342          * here, while the discussion in Knuth assumes 1-based subscripts). So, if
 343          * we simply enter the indexes into pendingHeap[] in decreasing order, we
 344          * a-fortiori have the heap invariant satisfied at completion of this
 345          * loop, and don't need to do any sift-up comparisons.
 346          */
 347         heapLength = 0;
 348         for (i = numObjs; --i >= 0;)
 349         {
 350                 if (beforeConstraints[objs[i]->dumpId] == 0)
 351                         pendingHeap[heapLength++] = i;
 352         }
 353
 354         /*--------------------
 355          * Now emit objects, working backwards in the output list.      At each step,
 356          * we use the priority heap to select the last item that has no remaining
 357          * before-constraints.  We remove that item from the heap, output it to
 358          * ordering[], and decrease the beforeConstraints count of each of the
 359          * items it was constrained against.  Whenever an item's beforeConstraints
 360          * count is thereby decreased to zero, we insert it into the priority heap
 361          * to show that it is a candidate to output.  We are done when the heap
 362          * becomes empty; if we have output every element then we succeeded,
 363          * otherwise we failed.
 364          * i = number of ordering[] entries left to output
 365          * j = objs[] index of item we are outputting
 366          * k = temp for scanning constraint list for item j
 367          *--------------------
 368          */
 369         i = numObjs;
 370         while (heapLength > 0)
 371         {
 372                 /* Select object to output by removing largest heap member */
 373                 j = removeHeapElement(pendingHeap, heapLength--);
 374                 obj = objs[j];
 375                 /* Output candidate to ordering[] */
 376                 ordering[--i] = obj;
 377                 /* Update beforeConstraints counts of its predecessors */
 378                 for (k = 0; k < obj->nDeps; k++)
 379                 {
 380                         int                     id = obj->dependencies[k];
 381
 382                         if ((--beforeConstraints[id]) == 0)
 383                                 addHeapElement(idMap[id], pendingHeap, heapLength++);
 384                 }
 385         }
 386
 387         /*
 388          * If we failed, report the objects that couldn't be output; these are the
 389          * ones with beforeConstraints[] still nonzero.
 390          */
 391         if (i != 0)
 392         {
 393                 k = 0;
 394                 for (j = 1; j <= maxDumpId; j++)
 395                 {
 396                         if (beforeConstraints[j] != 0)
 397                                 ordering[k++] = objs[idMap[j]];
 398                 }
 399                 *nOrdering = k;
 400         }
 401
 402         /* Done */
 403         free(pendingHeap);
 404         free(beforeConstraints);
 405         free(idMap);
 406
 407         return (i == 0);
 408 }
 409
 410 /*
 411  * Add an item to a heap (priority queue)
 412  *
 413  * heapLength is the current heap size; caller is responsible for increasing
 414  * its value after the call.  There must be sufficient storage at *heap.
 415  */
 416 static void
 417 addHeapElement(int val, int *heap, int heapLength)
 418 {
 419         int                     j;
 420
 421         /*
 422          * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
 423          * using 1-based array indexes, not 0-based.
 424          */
 425         j = heapLength;
 426         while (j > 0)
 427         {
 428                 int                     i = (j - 1) >> 1;
 429
 430                 if (val <= heap[i])
 431                         break;
 432                 heap[j] = heap[i];
 433                 j = i;
 434         }
 435         heap[j] = val;
 436 }
 437
 438 /*
 439  * Remove the largest item present in a heap (priority queue)
 440  *
 441  * heapLength is the current heap size; caller is responsible for decreasing
 442  * its value after the call.
 443  *
 444  * We remove and return heap[0], which is always the largest element of
 445  * the heap, and then "sift up" to maintain the heap invariant.
 446  */
 447 static int
 448 removeHeapElement(int *heap, int heapLength)
 449 {
 450         int                     result = heap[0];
 451         int                     val;
 452         int                     i;
 453
 454         if (--heapLength <= 0)
 455                 return result;
 456         val = heap[heapLength];         /* value that must be reinserted */
 457         i = 0;                                          /* i is where the "hole" is */
 458         for (;;)
 459         {
 460                 int                     j = 2 * i + 1;
 461
 462                 if (j >= heapLength)
 463                         break;
 464                 if (j + 1 < heapLength &&
 465                         heap[j] < heap[j + 1])
 466                         j++;
 467                 if (val >= heap[j])
 468                         break;
 469                 heap[i] = heap[j];
 470                 i = j;
 471         }
 472         heap[i] = val;
 473         return result;
 474 }
 475
 476 /*
 477  * findDependencyLoops - identify loops in TopoSort's failure output,
 478  *              and pass each such loop to repairDependencyLoop() for action
 479  *
 480  * In general there may be many loops in the set of objects returned by
 481  * TopoSort; for speed we should try to repair as many loops as we can
 482  * before trying TopoSort again.  We can safely repair loops that are
 483  * disjoint (have no members in common); if we find overlapping loops
 484  * then we repair only the first one found, because the action taken to
 485  * repair the first might have repaired the other as well.      (If not,
 486  * we'll fix it on the next go-round.)
 487  *
 488  * objs[] lists the objects TopoSort couldn't sort
 489  * nObjs is the number of such objects
 490  * totObjs is the total number of objects in the universe
 491  */
 492 static void
 493 findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
 494 {
 495         /*
 496          * We use a workspace array, the initial part of which stores objects
 497          * already processed, and the rest of which is used as temporary space to
 498          * try to build a loop in.      This is convenient because we do not care
 499          * about loops involving already-processed objects (see notes above); we
 500          * can easily reject such loops in findLoop() because of this
 501          * representation.      After we identify and process a loop, we can add it to
 502          * the initial part of the workspace just by moving the boundary pointer.
 503          *
 504          * When we determine that an object is not part of any interesting loop,
 505          * we also add it to the initial part of the workspace.  This is not
 506          * necessary for correctness, but saves later invocations of findLoop()
 507          * from uselessly chasing references to such an object.
 508          *
 509          * We make the workspace large enough to hold all objects in the original
 510          * universe.  This is probably overkill, but it's provably enough space...
 511          */
 512         DumpableObject **workspace;
 513         int                     initiallen;
 514         bool            fixedloop;
 515         int                     i;
 516
 517         workspace = (DumpableObject **) malloc(totObjs * sizeof(DumpableObject *));
 518         if (workspace == NULL)
 519                 exit_horribly(NULL, modulename, "out of memory\n");
 520         initiallen = 0;
 521         fixedloop = false;
 522
 523         for (i = 0; i < nObjs; i++)
 524         {
 525                 DumpableObject *obj = objs[i];
 526                 int                     newlen;
 527
 528                 workspace[initiallen] = NULL;   /* see test below */
 529
 530                 if (findLoop(obj, obj->dumpId, workspace, initiallen, &newlen))
 531                 {
 532                         /* Found a loop of length newlen - initiallen */
 533                         repairDependencyLoop(&workspace[initiallen], newlen - initiallen);
 534                         /* Add loop members to workspace */
 535                         initiallen = newlen;
 536                         fixedloop = true;
 537                 }
 538                 else
 539                 {
 540                         /*
 541                          * Didn't find a loop, but add this object to workspace anyway,
 542                          * unless it's already present.  We piggyback on the test that
 543                          * findLoop() already did: it won't have tentatively added obj to
 544                          * workspace if it's already present.
 545                          */
 546                         if (workspace[initiallen] == obj)
 547                                 initiallen++;
 548                 }
 549         }
 550
 551         /* We'd better have fixed at least one loop */
 552         if (!fixedloop)
 553                 exit_horribly(NULL, modulename, "could not identify dependency loop\n");
 554
 555         free(workspace);
 556 }
 557
 558 /*
 559  * Recursively search for a circular dependency loop that doesn't include
 560  * any existing workspace members.
 561  *
 562  *      obj: object we are examining now
 563  *      startPoint: dumpId of starting object for the hoped-for circular loop
 564  *      workspace[]: work array for previously processed and current objects
 565  *      depth: number of valid entries in workspace[] at call
 566  *      newDepth: if successful, set to new number of workspace[] entries
 567  *
 568  * On success, *newDepth is set and workspace[] entries depth..*newDepth-1
 569  * are filled with pointers to the members of the loop.
 570  *
 571  * Note: it is possible that the given starting object is a member of more
 572  * than one cycle; if so, we will find an arbitrary one of the cycles.
 573  */
 574 static bool
 575 findLoop(DumpableObject *obj,
 576                  DumpId startPoint,
 577                  DumpableObject **workspace,
 578                  int depth,
 579                  int *newDepth)
 580 {
 581         int                     i;
 582
 583         /*
 584          * Reject if obj is already present in workspace.  This test serves three
 585          * purposes: it prevents us from finding loops that overlap
 586          * previously-processed loops, it prevents us from going into infinite
 587          * recursion if we are given a startPoint object that links to a cycle
 588          * it's not a member of, and it guarantees that we can't overflow the
 589          * allocated size of workspace[].
 590          */
 591         for (i = 0; i < depth; i++)
 592         {
 593                 if (workspace[i] == obj)
 594                         return false;
 595         }
 596
 597         /*
 598          * Okay, tentatively add obj to workspace
 599          */
 600         workspace[depth++] = obj;
 601
 602         /*
 603          * See if we've found a loop back to the desired startPoint; if so, done
 604          */
 605         for (i = 0; i < obj->nDeps; i++)
 606         {
 607                 if (obj->dependencies[i] == startPoint)
 608                 {
 609                         *newDepth = depth;
 610                         return true;
 611                 }
 612         }
 613
 614         /*
 615          * Recurse down each outgoing branch
 616          */
 617         for (i = 0; i < obj->nDeps; i++)
 618         {
 619                 DumpableObject *nextobj = findObjectByDumpId(obj->dependencies[i]);
 620
 621                 if (!nextobj)
 622                         continue;                       /* ignore dependencies on undumped objects */
 623                 if (findLoop(nextobj,
 624                                          startPoint,
 625                                          workspace,
 626                                          depth,
 627                                          newDepth))
 628                         return true;
 629         }
 630
 631         return false;
 632 }
 633
 634 /*
 635  * A user-defined datatype will have a dependency loop with each of its
 636  * I/O functions (since those have the datatype as input or output).
 637  * Break the loop and make the I/O function depend on the associated
 638  * shell type, instead.
 639  */
 640 static void
 641 repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
 642 {
 643         TypeInfo   *typeInfo = (TypeInfo *) typeobj;
 644
 645         /* remove function's dependency on type */
 646         removeObjectDependency(funcobj, typeobj->dumpId);
 647
 648         /* add function's dependency on shell type, instead */
 649         if (typeInfo->shellType)
 650         {
 651                 addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
 652                 /* Mark shell type as to be dumped if any I/O function is */
 653                 if (funcobj->dump)
 654                         typeInfo->shellType->dobj.dump = true;
 655         }
 656 }
 657
 658 /*
 659  * Because we force a view to depend on its ON SELECT rule, while there
 660  * will be an implicit dependency in the other direction, we need to break
 661  * the loop.  If there are no other objects in the loop then we can remove
 662  * the implicit dependency and leave the ON SELECT rule non-separate.
 663  */
 664 static void
 665 repairViewRuleLoop(DumpableObject *viewobj,
 666                                    DumpableObject *ruleobj)
 667 {
 668         /* remove rule's dependency on view */
 669         removeObjectDependency(ruleobj, viewobj->dumpId);
 670 }
 671
 672 /*
 673  * However, if there are other objects in the loop, we must break the loop
 674  * by making the ON SELECT rule a separately-dumped object.
 675  *
 676  * Because findLoop() finds shorter cycles before longer ones, it's likely
 677  * that we will have previously fired repairViewRuleLoop() and removed the
 678  * rule's dependency on the view.  Put it back to ensure the rule won't be
 679  * emitted before the view...
 680  */
 681 static void
 682 repairViewRuleMultiLoop(DumpableObject *viewobj,
 683                                                 DumpableObject *ruleobj)
 684 {
 685         /* remove view's dependency on rule */
 686         removeObjectDependency(viewobj, ruleobj->dumpId);
 687         /* pretend view is a plain table and dump it that way */
 688         ((TableInfo *) viewobj)->relkind = 'r';         /* RELKIND_RELATION */
 689         /* mark rule as needing its own dump */
 690         ((RuleInfo *) ruleobj)->separate = true;
 691         /* put back rule's dependency on view */
 692         addObjectDependency(ruleobj, viewobj->dumpId);
 693 }
 694
 695 /*
 696  * Because we make tables depend on their CHECK constraints, while there
 697  * will be an automatic dependency in the other direction, we need to break
 698  * the loop.  If there are no other objects in the loop then we can remove
 699  * the automatic dependency and leave the CHECK constraint non-separate.
 700  */
 701 static void
 702 repairTableConstraintLoop(DumpableObject *tableobj,
 703                                                   DumpableObject *constraintobj)
 704 {
 705         /* remove constraint's dependency on table */
 706         removeObjectDependency(constraintobj, tableobj->dumpId);
 707 }
 708
 709 /*
 710  * However, if there are other objects in the loop, we must break the loop
 711  * by making the CHECK constraint a separately-dumped object.
 712  *
 713  * Because findLoop() finds shorter cycles before longer ones, it's likely
 714  * that we will have previously fired repairTableConstraintLoop() and
 715  * removed the constraint's dependency on the table.  Put it back to ensure
 716  * the constraint won't be emitted before the table...
 717  */
 718 static void
 719 repairTableConstraintMultiLoop(DumpableObject *tableobj,
 720                                                            DumpableObject *constraintobj)
 721 {
 722         /* remove table's dependency on constraint */
 723         removeObjectDependency(tableobj, constraintobj->dumpId);
 724         /* mark constraint as needing its own dump */
 725         ((ConstraintInfo *) constraintobj)->separate = true;
 726         /* put back constraint's dependency on table */
 727         addObjectDependency(constraintobj, tableobj->dumpId);
 728 }
 729
 730 /*
 731  * Attribute defaults behave exactly the same as CHECK constraints...
 732  */
 733 static void
 734 repairTableAttrDefLoop(DumpableObject *tableobj,
 735                                            DumpableObject *attrdefobj)
 736 {
 737         /* remove attrdef's dependency on table */
 738         removeObjectDependency(attrdefobj, tableobj->dumpId);
 739 }
 740
 741 static void
 742 repairTableAttrDefMultiLoop(DumpableObject *tableobj,
 743                                                         DumpableObject *attrdefobj)
 744 {
 745         /* remove table's dependency on attrdef */
 746         removeObjectDependency(tableobj, attrdefobj->dumpId);
 747         /* mark attrdef as needing its own dump */
 748         ((AttrDefInfo *) attrdefobj)->separate = true;
 749         /* put back attrdef's dependency on table */
 750         addObjectDependency(attrdefobj, tableobj->dumpId);
 751 }
 752
 753 /*
 754  * CHECK constraints on domains work just like those on tables ...
 755  */
 756 static void
 757 repairDomainConstraintLoop(DumpableObject *domainobj,
 758                                                    DumpableObject *constraintobj)
 759 {
 760         /* remove constraint's dependency on domain */
 761         removeObjectDependency(constraintobj, domainobj->dumpId);
 762 }
 763
 764 static void
 765 repairDomainConstraintMultiLoop(DumpableObject *domainobj,
 766                                                                 DumpableObject *constraintobj)
 767 {
 768         /* remove domain's dependency on constraint */
 769         removeObjectDependency(domainobj, constraintobj->dumpId);
 770         /* mark constraint as needing its own dump */
 771         ((ConstraintInfo *) constraintobj)->separate = true;
 772         /* put back constraint's dependency on domain */
 773         addObjectDependency(constraintobj, domainobj->dumpId);
 774 }
 775
 776 /*
 777  * Fix a dependency loop, or die trying ...
 778  *
 779  * This routine is mainly concerned with reducing the multiple ways that
 780  * a loop might appear to common cases, which it passes off to the
 781  * "fixer" routines above.
 782  */
 783 static void
 784 repairDependencyLoop(DumpableObject **loop,
 785                                          int nLoop)
 786 {
 787         int                     i,
 788                                 j;
 789
 790         /* Datatype and one of its I/O functions */
 791         if (nLoop == 2 &&
 792                 loop[0]->objType == DO_TYPE &&
 793                 loop[1]->objType == DO_FUNC)
 794         {
 795                 repairTypeFuncLoop(loop[0], loop[1]);
 796                 return;
 797         }
 798         if (nLoop == 2 &&
 799                 loop[1]->objType == DO_TYPE &&
 800                 loop[0]->objType == DO_FUNC)
 801         {
 802                 repairTypeFuncLoop(loop[1], loop[0]);
 803                 return;
 804         }
 805
 806         /* View and its ON SELECT rule */
 807         if (nLoop == 2 &&
 808                 loop[0]->objType == DO_TABLE &&
 809                 loop[1]->objType == DO_RULE &&
 810                 ((RuleInfo *) loop[1])->ev_type == '1' &&
 811                 ((RuleInfo *) loop[1])->is_instead &&
 812                 ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
 813         {
 814                 repairViewRuleLoop(loop[0], loop[1]);
 815                 return;
 816         }
 817         if (nLoop == 2 &&
 818                 loop[1]->objType == DO_TABLE &&
 819                 loop[0]->objType == DO_RULE &&
 820                 ((RuleInfo *) loop[0])->ev_type == '1' &&
 821                 ((RuleInfo *) loop[0])->is_instead &&
 822                 ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
 823         {
 824                 repairViewRuleLoop(loop[1], loop[0]);
 825                 return;
 826         }
 827
 828         /* Indirect loop involving view and ON SELECT rule */
 829         if (nLoop > 2)
 830         {
 831                 for (i = 0; i < nLoop; i++)
 832                 {
 833                         if (loop[i]->objType == DO_TABLE)
 834                         {
 835                                 for (j = 0; j < nLoop; j++)
 836                                 {
 837                                         if (loop[j]->objType == DO_RULE &&
 838                                                 ((RuleInfo *) loop[j])->ev_type == '1' &&
 839                                                 ((RuleInfo *) loop[j])->is_instead &&
 840                                                 ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
 841                                         {
 842                                                 repairViewRuleMultiLoop(loop[i], loop[j]);
 843                                                 return;
 844                                         }
 845                                 }
 846                         }
 847                 }
 848         }
 849
 850         /* Table and CHECK constraint */
 851         if (nLoop == 2 &&
 852                 loop[0]->objType == DO_TABLE &&
 853                 loop[1]->objType == DO_CONSTRAINT &&
 854                 ((ConstraintInfo *) loop[1])->contype == 'c' &&
 855                 ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
 856         {
 857                 repairTableConstraintLoop(loop[0], loop[1]);
 858                 return;
 859         }
 860         if (nLoop == 2 &&
 861                 loop[1]->objType == DO_TABLE &&
 862                 loop[0]->objType == DO_CONSTRAINT &&
 863                 ((ConstraintInfo *) loop[0])->contype == 'c' &&
 864                 ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
 865         {
 866                 repairTableConstraintLoop(loop[1], loop[0]);
 867                 return;
 868         }
 869
 870         /* Indirect loop involving table and CHECK constraint */
 871         if (nLoop > 2)
 872         {
 873                 for (i = 0; i < nLoop; i++)
 874                 {
 875                         if (loop[i]->objType == DO_TABLE)
 876                         {
 877                                 for (j = 0; j < nLoop; j++)
 878                                 {
 879                                         if (loop[j]->objType == DO_CONSTRAINT &&
 880                                                 ((ConstraintInfo *) loop[j])->contype == 'c' &&
 881                                                 ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
 882                                         {
 883                                                 repairTableConstraintMultiLoop(loop[i], loop[j]);
 884                                                 return;
 885                                         }
 886                                 }
 887                         }
 888                 }
 889         }
 890
 891         /* Table and attribute default */
 892         if (nLoop == 2 &&
 893                 loop[0]->objType == DO_TABLE &&
 894                 loop[1]->objType == DO_ATTRDEF &&
 895                 ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
 896         {
 897                 repairTableAttrDefLoop(loop[0], loop[1]);
 898                 return;
 899         }
 900         if (nLoop == 2 &&
 901                 loop[1]->objType == DO_TABLE &&
 902                 loop[0]->objType == DO_ATTRDEF &&
 903                 ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
 904         {
 905                 repairTableAttrDefLoop(loop[1], loop[0]);
 906                 return;
 907         }
 908
 909         /* Indirect loop involving table and attribute default */
 910         if (nLoop > 2)
 911         {
 912                 for (i = 0; i < nLoop; i++)
 913                 {
 914                         if (loop[i]->objType == DO_TABLE)
 915                         {
 916                                 for (j = 0; j < nLoop; j++)
 917                                 {
 918                                         if (loop[j]->objType == DO_ATTRDEF &&
 919                                                 ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
 920                                         {
 921                                                 repairTableAttrDefMultiLoop(loop[i], loop[j]);
 922                                                 return;
 923                                         }
 924                                 }
 925                         }
 926                 }
 927         }
 928
 929         /* Domain and CHECK constraint */
 930         if (nLoop == 2 &&
 931                 loop[0]->objType == DO_TYPE &&
 932                 loop[1]->objType == DO_CONSTRAINT &&
 933                 ((ConstraintInfo *) loop[1])->contype == 'c' &&
 934                 ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
 935         {
 936                 repairDomainConstraintLoop(loop[0], loop[1]);
 937                 return;
 938         }
 939         if (nLoop == 2 &&
 940                 loop[1]->objType == DO_TYPE &&
 941                 loop[0]->objType == DO_CONSTRAINT &&
 942                 ((ConstraintInfo *) loop[0])->contype == 'c' &&
 943                 ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
 944         {
 945                 repairDomainConstraintLoop(loop[1], loop[0]);
 946                 return;
 947         }
 948
 949         /* Indirect loop involving domain and CHECK constraint */
 950         if (nLoop > 2)
 951         {
 952                 for (i = 0; i < nLoop; i++)
 953                 {
 954                         if (loop[i]->objType == DO_TYPE)
 955                         {
 956                                 for (j = 0; j < nLoop; j++)
 957                                 {
 958                                         if (loop[j]->objType == DO_CONSTRAINT &&
 959                                                 ((ConstraintInfo *) loop[j])->contype == 'c' &&
 960                                                 ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
 961                                         {
 962                                                 repairDomainConstraintMultiLoop(loop[i], loop[j]);
 963                                                 return;
 964                                         }
 965                                 }
 966                         }
 967                 }
 968         }
 969
 970         /*
 971          * If all the objects are TABLE_DATA items, what we must have is a
 972          * circular set of foreign key constraints (or a single self-referential
 973          * table).      Print an appropriate complaint and break the loop arbitrarily.
 974          */
 975         for (i = 0; i < nLoop; i++)
 976         {
 977                 if (loop[i]->objType != DO_TABLE_DATA)
 978                         break;
 979         }
 980         if (i >= nLoop)
 981         {
 982                 write_msg(NULL, "NOTICE: there are circular foreign-key constraints among these table(s):\n");
 983                 for (i = 0; i < nLoop; i++)
 984                         write_msg(NULL, "  %s\n", loop[i]->name);
 985                 write_msg(NULL, "You may not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.\n");
 986                 write_msg(NULL, "Consider using a full dump instead of a --data-only dump to avoid this problem.\n");
 987                 if (nLoop > 1)
 988                         removeObjectDependency(loop[0], loop[1]->dumpId);
 989                 else    /* must be a self-dependency */
 990                         removeObjectDependency(loop[0], loop[0]->dumpId);
 991                 return;
 992         }
 993
 994         /*
 995          * If we can't find a principled way to break the loop, complain and break
 996          * it in an arbitrary fashion.
 997          */
 998         write_msg(modulename, "WARNING: could not resolve dependency loop among these items:\n");
 999         for (i = 0; i < nLoop; i++)
1000         {
1001                 char            buf[1024];
1002
1003                 describeDumpableObject(loop[i], buf, sizeof(buf));
1004                 write_msg(modulename, "  %s\n", buf);
1005         }
1006
1007         if (nLoop > 1)
1008                 removeObjectDependency(loop[0], loop[1]->dumpId);
1009         else    /* must be a self-dependency */
1010                 removeObjectDependency(loop[0], loop[0]->dumpId);
1011 }
1012
1013 /*
1014  * Describe a dumpable object usefully for errors
1015  *
1016  * This should probably go somewhere else...
1017  */
1018 static void
1019 describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
1020 {
1021         switch (obj->objType)
1022         {
1023                 case DO_NAMESPACE:
1024                         snprintf(buf, bufsize,
1025                                          "SCHEMA %s  (ID %d OID %u)",
1026                                          obj->name, obj->dumpId, obj->catId.oid);
1027                         return;
1028                 case DO_EXTENSION:
1029                         snprintf(buf, bufsize,
1030                                          "EXTENSION %s  (ID %d OID %u)",
1031                                          obj->name, obj->dumpId, obj->catId.oid);
1032                         return;
1033                 case DO_TYPE:
1034                         snprintf(buf, bufsize,
1035                                          "TYPE %s  (ID %d OID %u)",
1036                                          obj->name, obj->dumpId, obj->catId.oid);
1037                         return;
1038                 case DO_SHELL_TYPE:
1039                         snprintf(buf, bufsize,
1040                                          "SHELL TYPE %s  (ID %d OID %u)",
1041                                          obj->name, obj->dumpId, obj->catId.oid);
1042                         return;
1043                 case DO_FUNC:
1044                         snprintf(buf, bufsize,
1045                                          "FUNCTION %s  (ID %d OID %u)",
1046                                          obj->name, obj->dumpId, obj->catId.oid);
1047                         return;
1048                 case DO_AGG:
1049                         snprintf(buf, bufsize,
1050                                          "AGGREGATE %s  (ID %d OID %u)",
1051                                          obj->name, obj->dumpId, obj->catId.oid);
1052                         return;
1053                 case DO_OPERATOR:
1054                         snprintf(buf, bufsize,
1055                                          "OPERATOR %s  (ID %d OID %u)",
1056                                          obj->name, obj->dumpId, obj->catId.oid);
1057                         return;
1058                 case DO_OPCLASS:
1059                         snprintf(buf, bufsize,
1060                                          "OPERATOR CLASS %s  (ID %d OID %u)",
1061                                          obj->name, obj->dumpId, obj->catId.oid);
1062                         return;
1063                 case DO_OPFAMILY:
1064                         snprintf(buf, bufsize,
1065                                          "OPERATOR FAMILY %s  (ID %d OID %u)",
1066                                          obj->name, obj->dumpId, obj->catId.oid);
1067                         return;
1068                 case DO_CONVERSION:
1069                         snprintf(buf, bufsize,
1070                                          "CONVERSION %s  (ID %d OID %u)",
1071                                          obj->name, obj->dumpId, obj->catId.oid);
1072                         return;
1073                 case DO_TABLE:
1074                         snprintf(buf, bufsize,
1075                                          "TABLE %s  (ID %d OID %u)",
1076                                          obj->name, obj->dumpId, obj->catId.oid);
1077                         return;
1078                 case DO_ATTRDEF:
1079                         snprintf(buf, bufsize,
1080                                          "ATTRDEF %s.%s  (ID %d OID %u)",
1081                                          ((AttrDefInfo *) obj)->adtable->dobj.name,
1082                                          ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
1083                                          obj->dumpId, obj->catId.oid);
1084                         return;
1085                 case DO_INDEX:
1086                         snprintf(buf, bufsize,
1087                                          "INDEX %s  (ID %d OID %u)",
1088                                          obj->name, obj->dumpId, obj->catId.oid);
1089                         return;
1090                 case DO_RULE:
1091                         snprintf(buf, bufsize,
1092                                          "RULE %s  (ID %d OID %u)",
1093                                          obj->name, obj->dumpId, obj->catId.oid);
1094                         return;
1095                 case DO_TRIGGER:
1096                         snprintf(buf, bufsize,
1097                                          "TRIGGER %s  (ID %d OID %u)",
1098                                          obj->name, obj->dumpId, obj->catId.oid);
1099                         return;
1100                 case DO_CONSTRAINT:
1101                         snprintf(buf, bufsize,
1102                                          "CONSTRAINT %s  (ID %d OID %u)",
1103                                          obj->name, obj->dumpId, obj->catId.oid);
1104                         return;
1105                 case DO_FK_CONSTRAINT:
1106                         snprintf(buf, bufsize,
1107                                          "FK CONSTRAINT %s  (ID %d OID %u)",
1108                                          obj->name, obj->dumpId, obj->catId.oid);
1109                         return;
1110                 case DO_PROCLANG:
1111                         snprintf(buf, bufsize,
1112                                          "PROCEDURAL LANGUAGE %s  (ID %d OID %u)",
1113                                          obj->name, obj->dumpId, obj->catId.oid);
1114                         return;
1115                 case DO_CAST:
1116                         snprintf(buf, bufsize,
1117                                          "CAST %u to %u  (ID %d OID %u)",
1118                                          ((CastInfo *) obj)->castsource,
1119                                          ((CastInfo *) obj)->casttarget,
1120                                          obj->dumpId, obj->catId.oid);
1121                         return;
1122                 case DO_TABLE_DATA:
1123                         snprintf(buf, bufsize,
1124                                          "TABLE DATA %s  (ID %d OID %u)",
1125                                          obj->name, obj->dumpId, obj->catId.oid);
1126                         return;
1127                 case DO_DUMMY_TYPE:
1128                         snprintf(buf, bufsize,
1129                                          "DUMMY TYPE %s  (ID %d OID %u)",
1130                                          obj->name, obj->dumpId, obj->catId.oid);
1131                         return;
1132                 case DO_TSPARSER:
1133                         snprintf(buf, bufsize,
1134                                          "TEXT SEARCH PARSER %s  (ID %d OID %u)",
1135                                          obj->name, obj->dumpId, obj->catId.oid);
1136                         return;
1137                 case DO_TSDICT:
1138                         snprintf(buf, bufsize,
1139                                          "TEXT SEARCH DICTIONARY %s  (ID %d OID %u)",
1140                                          obj->name, obj->dumpId, obj->catId.oid);
1141                         return;
1142                 case DO_TSTEMPLATE:
1143                         snprintf(buf, bufsize,
1144                                          "TEXT SEARCH TEMPLATE %s  (ID %d OID %u)",
1145                                          obj->name, obj->dumpId, obj->catId.oid);
1146                         return;
1147                 case DO_TSCONFIG:
1148                         snprintf(buf, bufsize,
1149                                          "TEXT SEARCH CONFIGURATION %s  (ID %d OID %u)",
1150                                          obj->name, obj->dumpId, obj->catId.oid);
1151                         return;
1152                 case DO_FDW:
1153                         snprintf(buf, bufsize,
1154                                          "FOREIGN DATA WRAPPER %s  (ID %d OID %u)",
1155                                          obj->name, obj->dumpId, obj->catId.oid);
1156                         return;
1157                 case DO_FOREIGN_SERVER:
1158                         snprintf(buf, bufsize,
1159                                          "FOREIGN SERVER %s  (ID %d OID %u)",
1160                                          obj->name, obj->dumpId, obj->catId.oid);
1161                         return;
1162                 case DO_DEFAULT_ACL:
1163                         snprintf(buf, bufsize,
1164                                          "DEFAULT ACL %s  (ID %d OID %u)",
1165                                          obj->name, obj->dumpId, obj->catId.oid);
1166                         return;
1167                 case DO_BLOB:
1168                         snprintf(buf, bufsize,
1169                                          "BLOB  (ID %d OID %u)",
1170                                          obj->dumpId, obj->catId.oid);
1171                         return;
1172                 case DO_BLOB_DATA:
1173                         snprintf(buf, bufsize,
1174                                          "BLOB DATA  (ID %d)",
1175                                          obj->dumpId);
1176                         return;
1177         }
1178         /* shouldn't get here */
1179         snprintf(buf, bufsize,
1180                          "object type %d  (ID %d OID %u)",
1181                          (int) obj->objType,
1182                          obj->dumpId, obj->catId.oid);
1183 }