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