PostgreSQL Source Code  git master
pg_dump_sort.c File Reference
#include "postgres_fe.h"
#include "catalog/pg_class_d.h"
#include "pg_backup_archiver.h"
#include "pg_backup_utils.h"
#include "pg_dump.h"
Include dependency graph for pg_dump_sort.c:

Go to the source code of this file.

Enumerations

enum  dbObjectTypePriorities {
  PRIO_NAMESPACE = 1 , PRIO_PROCLANG , PRIO_COLLATION , PRIO_TRANSFORM ,
  PRIO_EXTENSION , PRIO_TYPE , PRIO_CAST , PRIO_FUNC ,
  PRIO_AGG , PRIO_ACCESS_METHOD , PRIO_OPERATOR , PRIO_OPFAMILY ,
  PRIO_CONVERSION , PRIO_TSPARSER , PRIO_TSTEMPLATE , PRIO_TSDICT ,
  PRIO_TSCONFIG , PRIO_FDW , PRIO_FOREIGN_SERVER , PRIO_TABLE ,
  PRIO_TABLE_ATTACH , PRIO_DUMMY_TYPE , PRIO_ATTRDEF , PRIO_BLOB ,
  PRIO_PRE_DATA_BOUNDARY , PRIO_TABLE_DATA , PRIO_SEQUENCE_SET , PRIO_BLOB_DATA ,
  PRIO_POST_DATA_BOUNDARY , PRIO_CONSTRAINT , PRIO_INDEX , PRIO_INDEX_ATTACH ,
  PRIO_STATSEXT , PRIO_RULE , PRIO_TRIGGER , PRIO_FK_CONSTRAINT ,
  PRIO_POLICY , PRIO_PUBLICATION , PRIO_PUBLICATION_REL , PRIO_PUBLICATION_TABLE_IN_SCHEMA ,
  PRIO_SUBSCRIPTION , PRIO_DEFAULT_ACL , PRIO_EVENT_TRIGGER , PRIO_REFRESH_MATVIEW
}
 

Functions

 StaticAssertDecl (lengthof(dbObjectTypePriority)==(DO_SUBSCRIPTION+1), "array length mismatch")
 
static int DOTypeNameCompare (const void *p1, const void *p2)
 
static bool TopoSort (DumpableObject **objs, int numObjs, DumpableObject **ordering, int *nOrdering)
 
static void addHeapElement (int val, int *heap, int heapLength)
 
static int removeHeapElement (int *heap, int heapLength)
 
static void findDependencyLoops (DumpableObject **objs, int nObjs, int totObjs)
 
static int findLoop (DumpableObject *obj, DumpId startPoint, bool *processed, DumpId *searchFailed, DumpableObject **workspace, int depth)
 
static void repairDependencyLoop (DumpableObject **loop, int nLoop)
 
static void describeDumpableObject (DumpableObject *obj, char *buf, int bufsize)
 
void sortDumpableObjectsByTypeName (DumpableObject **objs, int numObjs)
 
void sortDumpableObjects (DumpableObject **objs, int numObjs, DumpId preBoundaryId, DumpId postBoundaryId)
 
static void repairTypeFuncLoop (DumpableObject *typeobj, DumpableObject *funcobj)
 
static void repairViewRuleLoop (DumpableObject *viewobj, DumpableObject *ruleobj)
 
static void repairViewRuleMultiLoop (DumpableObject *viewobj, DumpableObject *ruleobj)
 
static void repairMatViewBoundaryMultiLoop (DumpableObject *boundaryobj, DumpableObject *nextobj)
 
static void repairTableConstraintLoop (DumpableObject *tableobj, DumpableObject *constraintobj)
 
static void repairTableConstraintMultiLoop (DumpableObject *tableobj, DumpableObject *constraintobj)
 
static void repairTableAttrDefLoop (DumpableObject *tableobj, DumpableObject *attrdefobj)
 
static void repairTableAttrDefMultiLoop (DumpableObject *tableobj, DumpableObject *attrdefobj)
 
static void repairDomainConstraintLoop (DumpableObject *domainobj, DumpableObject *constraintobj)
 
static void repairDomainConstraintMultiLoop (DumpableObject *domainobj, DumpableObject *constraintobj)
 
static void repairIndexLoop (DumpableObject *partedindex, DumpableObject *partindex)
 

Variables

static const int dbObjectTypePriority []
 
static DumpId preDataBoundId
 
static DumpId postDataBoundId
 

Enumeration Type Documentation

◆ dbObjectTypePriorities

Enumerator
PRIO_NAMESPACE 
PRIO_PROCLANG 
PRIO_COLLATION 
PRIO_TRANSFORM 
PRIO_EXTENSION 
PRIO_TYPE 
PRIO_CAST 
PRIO_FUNC 
PRIO_AGG 
PRIO_ACCESS_METHOD 
PRIO_OPERATOR 
PRIO_OPFAMILY 
PRIO_CONVERSION 
PRIO_TSPARSER 
PRIO_TSTEMPLATE 
PRIO_TSDICT 
PRIO_TSCONFIG 
PRIO_FDW 
PRIO_FOREIGN_SERVER 
PRIO_TABLE 
PRIO_TABLE_ATTACH 
PRIO_DUMMY_TYPE 
PRIO_ATTRDEF 
PRIO_BLOB 
PRIO_PRE_DATA_BOUNDARY 
PRIO_TABLE_DATA 
PRIO_SEQUENCE_SET 
PRIO_BLOB_DATA 
PRIO_POST_DATA_BOUNDARY 
PRIO_CONSTRAINT 
PRIO_INDEX 
PRIO_INDEX_ATTACH 
PRIO_STATSEXT 
PRIO_RULE 
PRIO_TRIGGER 
PRIO_FK_CONSTRAINT 
PRIO_POLICY 
PRIO_PUBLICATION 
PRIO_PUBLICATION_REL 
PRIO_PUBLICATION_TABLE_IN_SCHEMA 
PRIO_SUBSCRIPTION 
PRIO_DEFAULT_ACL 
PRIO_EVENT_TRIGGER 
PRIO_REFRESH_MATVIEW 

Definition at line 53 of file pg_dump_sort.c.

54 {
55  PRIO_NAMESPACE = 1,
60  PRIO_TYPE, /* used for DO_TYPE and DO_SHELL_TYPE */
61  PRIO_CAST,
62  PRIO_FUNC,
63  PRIO_AGG,
66  PRIO_OPFAMILY, /* used for DO_OPFAMILY and DO_OPCLASS */
72  PRIO_FDW,
74  PRIO_TABLE,
78  PRIO_BLOB,
79  PRIO_PRE_DATA_BOUNDARY, /* boundary! */
83  PRIO_POST_DATA_BOUNDARY, /* boundary! */
85  PRIO_INDEX,
88  PRIO_RULE,
96  PRIO_DEFAULT_ACL, /* done in ACL pass */
97  PRIO_EVENT_TRIGGER, /* must be next to last! */
98  PRIO_REFRESH_MATVIEW /* must be last! */
99 };
@ PRIO_EVENT_TRIGGER
Definition: pg_dump_sort.c:97
@ PRIO_SUBSCRIPTION
Definition: pg_dump_sort.c:95
@ PRIO_FDW
Definition: pg_dump_sort.c:72
@ PRIO_INDEX_ATTACH
Definition: pg_dump_sort.c:86
@ PRIO_FK_CONSTRAINT
Definition: pg_dump_sort.c:90
@ PRIO_TSCONFIG
Definition: pg_dump_sort.c:71
@ PRIO_POST_DATA_BOUNDARY
Definition: pg_dump_sort.c:83
@ PRIO_PUBLICATION
Definition: pg_dump_sort.c:92
@ PRIO_PUBLICATION_TABLE_IN_SCHEMA
Definition: pg_dump_sort.c:94
@ PRIO_TABLE
Definition: pg_dump_sort.c:74
@ PRIO_DEFAULT_ACL
Definition: pg_dump_sort.c:96
@ PRIO_CAST
Definition: pg_dump_sort.c:61
@ PRIO_AGG
Definition: pg_dump_sort.c:63
@ PRIO_PROCLANG
Definition: pg_dump_sort.c:56
@ PRIO_CONVERSION
Definition: pg_dump_sort.c:67
@ PRIO_FUNC
Definition: pg_dump_sort.c:62
@ PRIO_CONSTRAINT
Definition: pg_dump_sort.c:84
@ PRIO_REFRESH_MATVIEW
Definition: pg_dump_sort.c:98
@ PRIO_POLICY
Definition: pg_dump_sort.c:91
@ PRIO_STATSEXT
Definition: pg_dump_sort.c:87
@ PRIO_EXTENSION
Definition: pg_dump_sort.c:59
@ PRIO_TSPARSER
Definition: pg_dump_sort.c:68
@ PRIO_DUMMY_TYPE
Definition: pg_dump_sort.c:76
@ PRIO_OPERATOR
Definition: pg_dump_sort.c:65
@ PRIO_RULE
Definition: pg_dump_sort.c:88
@ PRIO_NAMESPACE
Definition: pg_dump_sort.c:55
@ PRIO_PUBLICATION_REL
Definition: pg_dump_sort.c:93
@ PRIO_FOREIGN_SERVER
Definition: pg_dump_sort.c:73
@ PRIO_SEQUENCE_SET
Definition: pg_dump_sort.c:81
@ PRIO_TSDICT
Definition: pg_dump_sort.c:70
@ PRIO_ACCESS_METHOD
Definition: pg_dump_sort.c:64
@ PRIO_BLOB_DATA
Definition: pg_dump_sort.c:82
@ PRIO_ATTRDEF
Definition: pg_dump_sort.c:77
@ PRIO_PRE_DATA_BOUNDARY
Definition: pg_dump_sort.c:79
@ PRIO_COLLATION
Definition: pg_dump_sort.c:57
@ PRIO_INDEX
Definition: pg_dump_sort.c:85
@ PRIO_TRIGGER
Definition: pg_dump_sort.c:89
@ PRIO_TYPE
Definition: pg_dump_sort.c:60
@ PRIO_OPFAMILY
Definition: pg_dump_sort.c:66
@ PRIO_TSTEMPLATE
Definition: pg_dump_sort.c:69
@ PRIO_TRANSFORM
Definition: pg_dump_sort.c:58
@ PRIO_TABLE_DATA
Definition: pg_dump_sort.c:80
@ PRIO_TABLE_ATTACH
Definition: pg_dump_sort.c:75
@ PRIO_BLOB
Definition: pg_dump_sort.c:78

Function Documentation

◆ addHeapElement()

static void addHeapElement ( int  val,
int *  heap,
int  heapLength 
)
static

Definition at line 514 of file pg_dump_sort.c.

515 {
516  int j;
517 
518  /*
519  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
520  * using 1-based array indexes, not 0-based.
521  */
522  j = heapLength;
523  while (j > 0)
524  {
525  int i = (j - 1) >> 1;
526 
527  if (val <= heap[i])
528  break;
529  heap[j] = heap[i];
530  j = i;
531  }
532  heap[j] = val;
533 }
long val
Definition: informix.c:664
int j
Definition: isn.c:74
int i
Definition: isn.c:73

References i, j, and val.

Referenced by TopoSort().

◆ describeDumpableObject()

static void describeDumpableObject ( DumpableObject obj,
char *  buf,
int  bufsize 
)
static

Definition at line 1271 of file pg_dump_sort.c.

1272 {
1273  switch (obj->objType)
1274  {
1275  case DO_NAMESPACE:
1276  snprintf(buf, bufsize,
1277  "SCHEMA %s (ID %d OID %u)",
1278  obj->name, obj->dumpId, obj->catId.oid);
1279  return;
1280  case DO_EXTENSION:
1281  snprintf(buf, bufsize,
1282  "EXTENSION %s (ID %d OID %u)",
1283  obj->name, obj->dumpId, obj->catId.oid);
1284  return;
1285  case DO_TYPE:
1286  snprintf(buf, bufsize,
1287  "TYPE %s (ID %d OID %u)",
1288  obj->name, obj->dumpId, obj->catId.oid);
1289  return;
1290  case DO_SHELL_TYPE:
1291  snprintf(buf, bufsize,
1292  "SHELL TYPE %s (ID %d OID %u)",
1293  obj->name, obj->dumpId, obj->catId.oid);
1294  return;
1295  case DO_FUNC:
1296  snprintf(buf, bufsize,
1297  "FUNCTION %s (ID %d OID %u)",
1298  obj->name, obj->dumpId, obj->catId.oid);
1299  return;
1300  case DO_AGG:
1301  snprintf(buf, bufsize,
1302  "AGGREGATE %s (ID %d OID %u)",
1303  obj->name, obj->dumpId, obj->catId.oid);
1304  return;
1305  case DO_OPERATOR:
1306  snprintf(buf, bufsize,
1307  "OPERATOR %s (ID %d OID %u)",
1308  obj->name, obj->dumpId, obj->catId.oid);
1309  return;
1310  case DO_ACCESS_METHOD:
1311  snprintf(buf, bufsize,
1312  "ACCESS METHOD %s (ID %d OID %u)",
1313  obj->name, obj->dumpId, obj->catId.oid);
1314  return;
1315  case DO_OPCLASS:
1316  snprintf(buf, bufsize,
1317  "OPERATOR CLASS %s (ID %d OID %u)",
1318  obj->name, obj->dumpId, obj->catId.oid);
1319  return;
1320  case DO_OPFAMILY:
1321  snprintf(buf, bufsize,
1322  "OPERATOR FAMILY %s (ID %d OID %u)",
1323  obj->name, obj->dumpId, obj->catId.oid);
1324  return;
1325  case DO_COLLATION:
1326  snprintf(buf, bufsize,
1327  "COLLATION %s (ID %d OID %u)",
1328  obj->name, obj->dumpId, obj->catId.oid);
1329  return;
1330  case DO_CONVERSION:
1331  snprintf(buf, bufsize,
1332  "CONVERSION %s (ID %d OID %u)",
1333  obj->name, obj->dumpId, obj->catId.oid);
1334  return;
1335  case DO_TABLE:
1336  snprintf(buf, bufsize,
1337  "TABLE %s (ID %d OID %u)",
1338  obj->name, obj->dumpId, obj->catId.oid);
1339  return;
1340  case DO_TABLE_ATTACH:
1341  snprintf(buf, bufsize,
1342  "TABLE ATTACH %s (ID %d)",
1343  obj->name, obj->dumpId);
1344  return;
1345  case DO_ATTRDEF:
1346  snprintf(buf, bufsize,
1347  "ATTRDEF %s.%s (ID %d OID %u)",
1348  ((AttrDefInfo *) obj)->adtable->dobj.name,
1349  ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
1350  obj->dumpId, obj->catId.oid);
1351  return;
1352  case DO_INDEX:
1353  snprintf(buf, bufsize,
1354  "INDEX %s (ID %d OID %u)",
1355  obj->name, obj->dumpId, obj->catId.oid);
1356  return;
1357  case DO_INDEX_ATTACH:
1358  snprintf(buf, bufsize,
1359  "INDEX ATTACH %s (ID %d)",
1360  obj->name, obj->dumpId);
1361  return;
1362  case DO_STATSEXT:
1363  snprintf(buf, bufsize,
1364  "STATISTICS %s (ID %d OID %u)",
1365  obj->name, obj->dumpId, obj->catId.oid);
1366  return;
1367  case DO_REFRESH_MATVIEW:
1368  snprintf(buf, bufsize,
1369  "REFRESH MATERIALIZED VIEW %s (ID %d OID %u)",
1370  obj->name, obj->dumpId, obj->catId.oid);
1371  return;
1372  case DO_RULE:
1373  snprintf(buf, bufsize,
1374  "RULE %s (ID %d OID %u)",
1375  obj->name, obj->dumpId, obj->catId.oid);
1376  return;
1377  case DO_TRIGGER:
1378  snprintf(buf, bufsize,
1379  "TRIGGER %s (ID %d OID %u)",
1380  obj->name, obj->dumpId, obj->catId.oid);
1381  return;
1382  case DO_EVENT_TRIGGER:
1383  snprintf(buf, bufsize,
1384  "EVENT TRIGGER %s (ID %d OID %u)",
1385  obj->name, obj->dumpId, obj->catId.oid);
1386  return;
1387  case DO_CONSTRAINT:
1388  snprintf(buf, bufsize,
1389  "CONSTRAINT %s (ID %d OID %u)",
1390  obj->name, obj->dumpId, obj->catId.oid);
1391  return;
1392  case DO_FK_CONSTRAINT:
1393  snprintf(buf, bufsize,
1394  "FK CONSTRAINT %s (ID %d OID %u)",
1395  obj->name, obj->dumpId, obj->catId.oid);
1396  return;
1397  case DO_PROCLANG:
1398  snprintf(buf, bufsize,
1399  "PROCEDURAL LANGUAGE %s (ID %d OID %u)",
1400  obj->name, obj->dumpId, obj->catId.oid);
1401  return;
1402  case DO_CAST:
1403  snprintf(buf, bufsize,
1404  "CAST %u to %u (ID %d OID %u)",
1405  ((CastInfo *) obj)->castsource,
1406  ((CastInfo *) obj)->casttarget,
1407  obj->dumpId, obj->catId.oid);
1408  return;
1409  case DO_TRANSFORM:
1410  snprintf(buf, bufsize,
1411  "TRANSFORM %u lang %u (ID %d OID %u)",
1412  ((TransformInfo *) obj)->trftype,
1413  ((TransformInfo *) obj)->trflang,
1414  obj->dumpId, obj->catId.oid);
1415  return;
1416  case DO_TABLE_DATA:
1417  snprintf(buf, bufsize,
1418  "TABLE DATA %s (ID %d OID %u)",
1419  obj->name, obj->dumpId, obj->catId.oid);
1420  return;
1421  case DO_SEQUENCE_SET:
1422  snprintf(buf, bufsize,
1423  "SEQUENCE SET %s (ID %d OID %u)",
1424  obj->name, obj->dumpId, obj->catId.oid);
1425  return;
1426  case DO_DUMMY_TYPE:
1427  snprintf(buf, bufsize,
1428  "DUMMY TYPE %s (ID %d OID %u)",
1429  obj->name, obj->dumpId, obj->catId.oid);
1430  return;
1431  case DO_TSPARSER:
1432  snprintf(buf, bufsize,
1433  "TEXT SEARCH PARSER %s (ID %d OID %u)",
1434  obj->name, obj->dumpId, obj->catId.oid);
1435  return;
1436  case DO_TSDICT:
1437  snprintf(buf, bufsize,
1438  "TEXT SEARCH DICTIONARY %s (ID %d OID %u)",
1439  obj->name, obj->dumpId, obj->catId.oid);
1440  return;
1441  case DO_TSTEMPLATE:
1442  snprintf(buf, bufsize,
1443  "TEXT SEARCH TEMPLATE %s (ID %d OID %u)",
1444  obj->name, obj->dumpId, obj->catId.oid);
1445  return;
1446  case DO_TSCONFIG:
1447  snprintf(buf, bufsize,
1448  "TEXT SEARCH CONFIGURATION %s (ID %d OID %u)",
1449  obj->name, obj->dumpId, obj->catId.oid);
1450  return;
1451  case DO_FDW:
1452  snprintf(buf, bufsize,
1453  "FOREIGN DATA WRAPPER %s (ID %d OID %u)",
1454  obj->name, obj->dumpId, obj->catId.oid);
1455  return;
1456  case DO_FOREIGN_SERVER:
1457  snprintf(buf, bufsize,
1458  "FOREIGN SERVER %s (ID %d OID %u)",
1459  obj->name, obj->dumpId, obj->catId.oid);
1460  return;
1461  case DO_DEFAULT_ACL:
1462  snprintf(buf, bufsize,
1463  "DEFAULT ACL %s (ID %d OID %u)",
1464  obj->name, obj->dumpId, obj->catId.oid);
1465  return;
1466  case DO_BLOB:
1467  snprintf(buf, bufsize,
1468  "BLOB (ID %d OID %u)",
1469  obj->dumpId, obj->catId.oid);
1470  return;
1471  case DO_BLOB_DATA:
1472  snprintf(buf, bufsize,
1473  "BLOB DATA (ID %d)",
1474  obj->dumpId);
1475  return;
1476  case DO_POLICY:
1477  snprintf(buf, bufsize,
1478  "POLICY (ID %d OID %u)",
1479  obj->dumpId, obj->catId.oid);
1480  return;
1481  case DO_PUBLICATION:
1482  snprintf(buf, bufsize,
1483  "PUBLICATION (ID %d OID %u)",
1484  obj->dumpId, obj->catId.oid);
1485  return;
1486  case DO_PUBLICATION_REL:
1487  snprintf(buf, bufsize,
1488  "PUBLICATION TABLE (ID %d OID %u)",
1489  obj->dumpId, obj->catId.oid);
1490  return;
1492  snprintf(buf, bufsize,
1493  "PUBLICATION TABLES IN SCHEMA (ID %d OID %u)",
1494  obj->dumpId, obj->catId.oid);
1495  return;
1496  case DO_SUBSCRIPTION:
1497  snprintf(buf, bufsize,
1498  "SUBSCRIPTION (ID %d OID %u)",
1499  obj->dumpId, obj->catId.oid);
1500  return;
1501  case DO_PRE_DATA_BOUNDARY:
1502  snprintf(buf, bufsize,
1503  "PRE-DATA BOUNDARY (ID %d)",
1504  obj->dumpId);
1505  return;
1506  case DO_POST_DATA_BOUNDARY:
1507  snprintf(buf, bufsize,
1508  "POST-DATA BOUNDARY (ID %d)",
1509  obj->dumpId);
1510  return;
1511  }
1512  /* shouldn't get here */
1513  snprintf(buf, bufsize,
1514  "object type %d (ID %d OID %u)",
1515  (int) obj->objType,
1516  obj->dumpId, obj->catId.oid);
1517 }
@ DO_EVENT_TRIGGER
Definition: pg_dump.h:79
@ DO_REFRESH_MATVIEW
Definition: pg_dump.h:80
@ DO_POLICY
Definition: pg_dump.h:81
@ DO_CAST
Definition: pg_dump.h:63
@ DO_FOREIGN_SERVER
Definition: pg_dump.h:72
@ DO_PRE_DATA_BOUNDARY
Definition: pg_dump.h:77
@ DO_PROCLANG
Definition: pg_dump.h:62
@ DO_TYPE
Definition: pg_dump.h:42
@ DO_INDEX
Definition: pg_dump.h:55
@ DO_COLLATION
Definition: pg_dump.h:50
@ DO_BLOB
Definition: pg_dump.h:75
@ DO_TSCONFIG
Definition: pg_dump.h:70
@ DO_OPERATOR
Definition: pg_dump.h:46
@ DO_FK_CONSTRAINT
Definition: pg_dump.h:61
@ DO_CONSTRAINT
Definition: pg_dump.h:60
@ DO_SUBSCRIPTION
Definition: pg_dump.h:85
@ DO_DEFAULT_ACL
Definition: pg_dump.h:73
@ DO_FDW
Definition: pg_dump.h:71
@ DO_SEQUENCE_SET
Definition: pg_dump.h:65
@ DO_ATTRDEF
Definition: pg_dump.h:54
@ DO_BLOB_DATA
Definition: pg_dump.h:76
@ DO_PUBLICATION_REL
Definition: pg_dump.h:83
@ DO_TABLE_ATTACH
Definition: pg_dump.h:53
@ DO_OPCLASS
Definition: pg_dump.h:48
@ DO_INDEX_ATTACH
Definition: pg_dump.h:56
@ DO_TSTEMPLATE
Definition: pg_dump.h:69
@ DO_STATSEXT
Definition: pg_dump.h:57
@ DO_FUNC
Definition: pg_dump.h:44
@ DO_POST_DATA_BOUNDARY
Definition: pg_dump.h:78
@ DO_OPFAMILY
Definition: pg_dump.h:49
@ DO_TRANSFORM
Definition: pg_dump.h:74
@ DO_ACCESS_METHOD
Definition: pg_dump.h:47
@ DO_PUBLICATION_TABLE_IN_SCHEMA
Definition: pg_dump.h:84
@ DO_CONVERSION
Definition: pg_dump.h:51
@ DO_TRIGGER
Definition: pg_dump.h:59
@ DO_RULE
Definition: pg_dump.h:58
@ DO_DUMMY_TYPE
Definition: pg_dump.h:66
@ DO_TSDICT
Definition: pg_dump.h:68
@ DO_TSPARSER
Definition: pg_dump.h:67
@ DO_EXTENSION
Definition: pg_dump.h:41
@ DO_TABLE_DATA
Definition: pg_dump.h:64
@ DO_PUBLICATION
Definition: pg_dump.h:82
@ DO_TABLE
Definition: pg_dump.h:52
@ DO_NAMESPACE
Definition: pg_dump.h:40
@ DO_AGG
Definition: pg_dump.h:45
@ DO_SHELL_TYPE
Definition: pg_dump.h:43
static char * buf
Definition: pg_test_fsync.c:67
#define snprintf
Definition: port.h:225
char * name
Definition: pg_dump.h:137
DumpId dumpId
Definition: pg_dump.h:136
DumpableObjectType objType
Definition: pg_dump.h:134
CatalogId catId
Definition: pg_dump.h:135

References buf, _dumpableObject::catId, DO_ACCESS_METHOD, DO_AGG, DO_ATTRDEF, DO_BLOB, DO_BLOB_DATA, DO_CAST, DO_COLLATION, DO_CONSTRAINT, DO_CONVERSION, DO_DEFAULT_ACL, DO_DUMMY_TYPE, DO_EVENT_TRIGGER, DO_EXTENSION, DO_FDW, DO_FK_CONSTRAINT, DO_FOREIGN_SERVER, DO_FUNC, DO_INDEX, DO_INDEX_ATTACH, DO_NAMESPACE, DO_OPCLASS, DO_OPERATOR, DO_OPFAMILY, DO_POLICY, DO_POST_DATA_BOUNDARY, DO_PRE_DATA_BOUNDARY, DO_PROCLANG, DO_PUBLICATION, DO_PUBLICATION_REL, DO_PUBLICATION_TABLE_IN_SCHEMA, DO_REFRESH_MATVIEW, DO_RULE, DO_SEQUENCE_SET, DO_SHELL_TYPE, DO_STATSEXT, DO_SUBSCRIPTION, DO_TABLE, DO_TABLE_ATTACH, DO_TABLE_DATA, DO_TRANSFORM, DO_TRIGGER, DO_TSCONFIG, DO_TSDICT, DO_TSPARSER, DO_TSTEMPLATE, DO_TYPE, _dumpableObject::dumpId, _dumpableObject::name, _dumpableObject::objType, CatalogId::oid, and snprintf.

Referenced by repairDependencyLoop().

◆ DOTypeNameCompare()

static int DOTypeNameCompare ( const void *  p1,
const void *  p2 
)
static

Definition at line 194 of file pg_dump_sort.c.

195 {
196  DumpableObject *obj1 = *(DumpableObject *const *) p1;
197  DumpableObject *obj2 = *(DumpableObject *const *) p2;
198  int cmpval;
199 
200  /* Sort by type's priority */
201  cmpval = dbObjectTypePriority[obj1->objType] -
203 
204  if (cmpval != 0)
205  return cmpval;
206 
207  /*
208  * Sort by namespace. Typically, all objects of the same priority would
209  * either have or not have a namespace link, but there are exceptions.
210  * Sort NULL namespace after non-NULL in such cases.
211  */
212  if (obj1->namespace)
213  {
214  if (obj2->namespace)
215  {
216  cmpval = strcmp(obj1->namespace->dobj.name,
217  obj2->namespace->dobj.name);
218  if (cmpval != 0)
219  return cmpval;
220  }
221  else
222  return -1;
223  }
224  else if (obj2->namespace)
225  return 1;
226 
227  /* Sort by name */
228  cmpval = strcmp(obj1->name, obj2->name);
229  if (cmpval != 0)
230  return cmpval;
231 
232  /* To have a stable sort order, break ties for some object types */
233  if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
234  {
235  FuncInfo *fobj1 = *(FuncInfo *const *) p1;
236  FuncInfo *fobj2 = *(FuncInfo *const *) p2;
237  int i;
238 
239  /* Sort by number of arguments, then argument type names */
240  cmpval = fobj1->nargs - fobj2->nargs;
241  if (cmpval != 0)
242  return cmpval;
243  for (i = 0; i < fobj1->nargs; i++)
244  {
245  TypeInfo *argtype1 = findTypeByOid(fobj1->argtypes[i]);
246  TypeInfo *argtype2 = findTypeByOid(fobj2->argtypes[i]);
247 
248  if (argtype1 && argtype2)
249  {
250  if (argtype1->dobj.namespace && argtype2->dobj.namespace)
251  {
252  cmpval = strcmp(argtype1->dobj.namespace->dobj.name,
253  argtype2->dobj.namespace->dobj.name);
254  if (cmpval != 0)
255  return cmpval;
256  }
257  cmpval = strcmp(argtype1->dobj.name, argtype2->dobj.name);
258  if (cmpval != 0)
259  return cmpval;
260  }
261  }
262  }
263  else if (obj1->objType == DO_OPERATOR)
264  {
265  OprInfo *oobj1 = *(OprInfo *const *) p1;
266  OprInfo *oobj2 = *(OprInfo *const *) p2;
267 
268  /* oprkind is 'l', 'r', or 'b'; this sorts prefix, postfix, infix */
269  cmpval = (oobj2->oprkind - oobj1->oprkind);
270  if (cmpval != 0)
271  return cmpval;
272  }
273  else if (obj1->objType == DO_ATTRDEF)
274  {
275  AttrDefInfo *adobj1 = *(AttrDefInfo *const *) p1;
276  AttrDefInfo *adobj2 = *(AttrDefInfo *const *) p2;
277 
278  /* Sort by attribute number */
279  cmpval = (adobj1->adnum - adobj2->adnum);
280  if (cmpval != 0)
281  return cmpval;
282  }
283  else if (obj1->objType == DO_POLICY)
284  {
285  PolicyInfo *pobj1 = *(PolicyInfo *const *) p1;
286  PolicyInfo *pobj2 = *(PolicyInfo *const *) p2;
287 
288  /* Sort by table name (table namespace was considered already) */
289  cmpval = strcmp(pobj1->poltable->dobj.name,
290  pobj2->poltable->dobj.name);
291  if (cmpval != 0)
292  return cmpval;
293  }
294  else if (obj1->objType == DO_TRIGGER)
295  {
296  TriggerInfo *tobj1 = *(TriggerInfo *const *) p1;
297  TriggerInfo *tobj2 = *(TriggerInfo *const *) p2;
298 
299  /* Sort by table name (table namespace was considered already) */
300  cmpval = strcmp(tobj1->tgtable->dobj.name,
301  tobj2->tgtable->dobj.name);
302  if (cmpval != 0)
303  return cmpval;
304  }
305 
306  /* Usually shouldn't get here, but if we do, sort by OID */
307  return oidcmp(obj1->catId.oid, obj2->catId.oid);
308 }
TypeInfo * findTypeByOid(Oid oid)
Definition: common.c:803
#define oidcmp(x, y)
Definition: pg_dump.h:20
static const int dbObjectTypePriority[]
Definition: pg_dump_sort.c:102
Oid * argtypes
Definition: pg_dump.h:228
int nargs
Definition: pg_dump.h:227
char oprkind
Definition: pg_dump.h:243
TableInfo * poltable
Definition: pg_dump.h:601
DumpableObject dobj
Definition: pg_dump.h:283
TableInfo * tgtable
Definition: pg_dump.h:437
DumpableObject dobj
Definition: pg_dump.h:190

References _attrDefInfo::adnum, _funcInfo::argtypes, _dumpableObject::catId, dbObjectTypePriority, DO_AGG, DO_ATTRDEF, DO_FUNC, DO_OPERATOR, DO_POLICY, DO_TRIGGER, _typeInfo::dobj, _tableInfo::dobj, findTypeByOid(), i, _dumpableObject::name, _funcInfo::nargs, _dumpableObject::objType, CatalogId::oid, oidcmp, _oprInfo::oprkind, p2, _policyInfo::poltable, and _triggerInfo::tgtable.

Referenced by sortDumpableObjectsByTypeName().

◆ findDependencyLoops()

static void findDependencyLoops ( DumpableObject **  objs,
int  nObjs,
int  totObjs 
)
static

Definition at line 590 of file pg_dump_sort.c.

591 {
592  /*
593  * We use three data structures here:
594  *
595  * processed[] is a bool array indexed by dump ID, marking the objects
596  * already processed during this invocation of findDependencyLoops().
597  *
598  * searchFailed[] is another array indexed by dump ID. searchFailed[j] is
599  * set to dump ID k if we have proven that there is no dependency path
600  * leading from object j back to start point k. This allows us to skip
601  * useless searching when there are multiple dependency paths from k to j,
602  * which is a common situation. We could use a simple bool array for
603  * this, but then we'd need to re-zero it for each start point, resulting
604  * in O(N^2) zeroing work. Using the start point's dump ID as the "true"
605  * value lets us skip clearing the array before we consider the next start
606  * point.
607  *
608  * workspace[] is an array of DumpableObject pointers, in which we try to
609  * build lists of objects constituting loops. We make workspace[] large
610  * enough to hold all the objects in TopoSort's output, which is huge
611  * overkill in most cases but could theoretically be necessary if there is
612  * a single dependency chain linking all the objects.
613  */
614  bool *processed;
615  DumpId *searchFailed;
616  DumpableObject **workspace;
617  bool fixedloop;
618  int i;
619 
620  processed = (bool *) pg_malloc0((getMaxDumpId() + 1) * sizeof(bool));
621  searchFailed = (DumpId *) pg_malloc0((getMaxDumpId() + 1) * sizeof(DumpId));
622  workspace = (DumpableObject **) pg_malloc(totObjs * sizeof(DumpableObject *));
623  fixedloop = false;
624 
625  for (i = 0; i < nObjs; i++)
626  {
627  DumpableObject *obj = objs[i];
628  int looplen;
629  int j;
630 
631  looplen = findLoop(obj,
632  obj->dumpId,
633  processed,
634  searchFailed,
635  workspace,
636  0);
637 
638  if (looplen > 0)
639  {
640  /* Found a loop, repair it */
641  repairDependencyLoop(workspace, looplen);
642  fixedloop = true;
643  /* Mark loop members as processed */
644  for (j = 0; j < looplen; j++)
645  processed[workspace[j]->dumpId] = true;
646  }
647  else
648  {
649  /*
650  * There's no loop starting at this object, but mark it processed
651  * anyway. This is not necessary for correctness, but saves later
652  * invocations of findLoop() from uselessly chasing references to
653  * such an object.
654  */
655  processed[obj->dumpId] = true;
656  }
657  }
658 
659  /* We'd better have fixed at least one loop */
660  if (!fixedloop)
661  pg_fatal("could not identify dependency loop");
662 
663  free(workspace);
664  free(searchFailed);
665  free(processed);
666 }
DumpId getMaxDumpId(void)
Definition: common.c:655
unsigned char bool
Definition: c.h:391
void * pg_malloc0(size_t size)
Definition: fe_memutils.c:53
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
#define free(a)
Definition: header.h:65
int DumpId
Definition: pg_backup.h:265
#define pg_fatal(...)
static int findLoop(DumpableObject *obj, DumpId startPoint, bool *processed, DumpId *searchFailed, DumpableObject **workspace, int depth)
Definition: pg_dump_sort.c:686
static void repairDependencyLoop(DumpableObject **loop, int nLoop)
Definition: pg_dump_sort.c:971

References _dumpableObject::dumpId, findLoop(), free, getMaxDumpId(), i, j, pg_fatal, pg_malloc(), pg_malloc0(), and repairDependencyLoop().

Referenced by sortDumpableObjects().

◆ findLoop()

static int findLoop ( DumpableObject obj,
DumpId  startPoint,
bool processed,
DumpId searchFailed,
DumpableObject **  workspace,
int  depth 
)
static

Definition at line 686 of file pg_dump_sort.c.

692 {
693  int i;
694 
695  /*
696  * Reject if obj is already processed. This test prevents us from finding
697  * loops that overlap previously-processed loops.
698  */
699  if (processed[obj->dumpId])
700  return 0;
701 
702  /*
703  * If we've already proven there is no path from this object back to the
704  * startPoint, forget it.
705  */
706  if (searchFailed[obj->dumpId] == startPoint)
707  return 0;
708 
709  /*
710  * Reject if obj is already present in workspace. This test prevents us
711  * from going into infinite recursion if we are given a startPoint object
712  * that links to a cycle it's not a member of, and it guarantees that we
713  * can't overflow the allocated size of workspace[].
714  */
715  for (i = 0; i < depth; i++)
716  {
717  if (workspace[i] == obj)
718  return 0;
719  }
720 
721  /*
722  * Okay, tentatively add obj to workspace
723  */
724  workspace[depth++] = obj;
725 
726  /*
727  * See if we've found a loop back to the desired startPoint; if so, done
728  */
729  for (i = 0; i < obj->nDeps; i++)
730  {
731  if (obj->dependencies[i] == startPoint)
732  return depth;
733  }
734 
735  /*
736  * Recurse down each outgoing branch
737  */
738  for (i = 0; i < obj->nDeps; i++)
739  {
741  int newDepth;
742 
743  if (!nextobj)
744  continue; /* ignore dependencies on undumped objects */
745  newDepth = findLoop(nextobj,
746  startPoint,
747  processed,
748  searchFailed,
749  workspace,
750  depth);
751  if (newDepth > 0)
752  return newDepth;
753  }
754 
755  /*
756  * Remember there is no path from here back to startPoint
757  */
758  searchFailed[obj->dumpId] = startPoint;
759 
760  return 0;
761 }
DumpableObject * findObjectByDumpId(DumpId dumpId)
Definition: common.c:666
DumpId * dependencies
Definition: pg_dump.h:144

References _dumpableObject::dependencies, _dumpableObject::dumpId, findObjectByDumpId(), i, and _dumpableObject::nDeps.

Referenced by findDependencyLoops().

◆ removeHeapElement()

static int removeHeapElement ( int *  heap,
int  heapLength 
)
static

Definition at line 545 of file pg_dump_sort.c.

546 {
547  int result = heap[0];
548  int val;
549  int i;
550 
551  if (--heapLength <= 0)
552  return result;
553  val = heap[heapLength]; /* value that must be reinserted */
554  i = 0; /* i is where the "hole" is */
555  for (;;)
556  {
557  int j = 2 * i + 1;
558 
559  if (j >= heapLength)
560  break;
561  if (j + 1 < heapLength &&
562  heap[j] < heap[j + 1])
563  j++;
564  if (val >= heap[j])
565  break;
566  heap[i] = heap[j];
567  i = j;
568  }
569  heap[i] = val;
570  return result;
571 }

References i, j, and val.

Referenced by TopoSort().

◆ repairDependencyLoop()

static void repairDependencyLoop ( DumpableObject **  loop,
int  nLoop 
)
static

Definition at line 971 of file pg_dump_sort.c.

973 {
974  int i,
975  j;
976 
977  /* Datatype and one of its I/O or canonicalize functions */
978  if (nLoop == 2 &&
979  loop[0]->objType == DO_TYPE &&
980  loop[1]->objType == DO_FUNC)
981  {
982  repairTypeFuncLoop(loop[0], loop[1]);
983  return;
984  }
985  if (nLoop == 2 &&
986  loop[1]->objType == DO_TYPE &&
987  loop[0]->objType == DO_FUNC)
988  {
989  repairTypeFuncLoop(loop[1], loop[0]);
990  return;
991  }
992 
993  /* View (including matview) and its ON SELECT rule */
994  if (nLoop == 2 &&
995  loop[0]->objType == DO_TABLE &&
996  loop[1]->objType == DO_RULE &&
997  (((TableInfo *) loop[0])->relkind == RELKIND_VIEW ||
998  ((TableInfo *) loop[0])->relkind == RELKIND_MATVIEW) &&
999  ((RuleInfo *) loop[1])->ev_type == '1' &&
1000  ((RuleInfo *) loop[1])->is_instead &&
1001  ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
1002  {
1003  repairViewRuleLoop(loop[0], loop[1]);
1004  return;
1005  }
1006  if (nLoop == 2 &&
1007  loop[1]->objType == DO_TABLE &&
1008  loop[0]->objType == DO_RULE &&
1009  (((TableInfo *) loop[1])->relkind == RELKIND_VIEW ||
1010  ((TableInfo *) loop[1])->relkind == RELKIND_MATVIEW) &&
1011  ((RuleInfo *) loop[0])->ev_type == '1' &&
1012  ((RuleInfo *) loop[0])->is_instead &&
1013  ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
1014  {
1015  repairViewRuleLoop(loop[1], loop[0]);
1016  return;
1017  }
1018 
1019  /* Indirect loop involving view (but not matview) and ON SELECT rule */
1020  if (nLoop > 2)
1021  {
1022  for (i = 0; i < nLoop; i++)
1023  {
1024  if (loop[i]->objType == DO_TABLE &&
1025  ((TableInfo *) loop[i])->relkind == RELKIND_VIEW)
1026  {
1027  for (j = 0; j < nLoop; j++)
1028  {
1029  if (loop[j]->objType == DO_RULE &&
1030  ((RuleInfo *) loop[j])->ev_type == '1' &&
1031  ((RuleInfo *) loop[j])->is_instead &&
1032  ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
1033  {
1034  repairViewRuleMultiLoop(loop[i], loop[j]);
1035  return;
1036  }
1037  }
1038  }
1039  }
1040  }
1041 
1042  /* Indirect loop involving matview and data boundary */
1043  if (nLoop > 2)
1044  {
1045  for (i = 0; i < nLoop; i++)
1046  {
1047  if (loop[i]->objType == DO_TABLE &&
1048  ((TableInfo *) loop[i])->relkind == RELKIND_MATVIEW)
1049  {
1050  for (j = 0; j < nLoop; j++)
1051  {
1052  if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
1053  {
1054  DumpableObject *nextobj;
1055 
1056  nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
1057  repairMatViewBoundaryMultiLoop(loop[j], nextobj);
1058  return;
1059  }
1060  }
1061  }
1062  }
1063  }
1064 
1065  /* Table and CHECK constraint */
1066  if (nLoop == 2 &&
1067  loop[0]->objType == DO_TABLE &&
1068  loop[1]->objType == DO_CONSTRAINT &&
1069  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1070  ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
1071  {
1072  repairTableConstraintLoop(loop[0], loop[1]);
1073  return;
1074  }
1075  if (nLoop == 2 &&
1076  loop[1]->objType == DO_TABLE &&
1077  loop[0]->objType == DO_CONSTRAINT &&
1078  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1079  ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
1080  {
1081  repairTableConstraintLoop(loop[1], loop[0]);
1082  return;
1083  }
1084 
1085  /* Indirect loop involving table and CHECK constraint */
1086  if (nLoop > 2)
1087  {
1088  for (i = 0; i < nLoop; i++)
1089  {
1090  if (loop[i]->objType == DO_TABLE)
1091  {
1092  for (j = 0; j < nLoop; j++)
1093  {
1094  if (loop[j]->objType == DO_CONSTRAINT &&
1095  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1096  ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
1097  {
1098  repairTableConstraintMultiLoop(loop[i], loop[j]);
1099  return;
1100  }
1101  }
1102  }
1103  }
1104  }
1105 
1106  /* Table and attribute default */
1107  if (nLoop == 2 &&
1108  loop[0]->objType == DO_TABLE &&
1109  loop[1]->objType == DO_ATTRDEF &&
1110  ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
1111  {
1112  repairTableAttrDefLoop(loop[0], loop[1]);
1113  return;
1114  }
1115  if (nLoop == 2 &&
1116  loop[1]->objType == DO_TABLE &&
1117  loop[0]->objType == DO_ATTRDEF &&
1118  ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
1119  {
1120  repairTableAttrDefLoop(loop[1], loop[0]);
1121  return;
1122  }
1123 
1124  /* index on partitioned table and corresponding index on partition */
1125  if (nLoop == 2 &&
1126  loop[0]->objType == DO_INDEX &&
1127  loop[1]->objType == DO_INDEX)
1128  {
1129  if (((IndxInfo *) loop[0])->parentidx == loop[1]->catId.oid)
1130  {
1131  repairIndexLoop(loop[0], loop[1]);
1132  return;
1133  }
1134  else if (((IndxInfo *) loop[1])->parentidx == loop[0]->catId.oid)
1135  {
1136  repairIndexLoop(loop[1], loop[0]);
1137  return;
1138  }
1139  }
1140 
1141  /* Indirect loop involving table and attribute default */
1142  if (nLoop > 2)
1143  {
1144  for (i = 0; i < nLoop; i++)
1145  {
1146  if (loop[i]->objType == DO_TABLE)
1147  {
1148  for (j = 0; j < nLoop; j++)
1149  {
1150  if (loop[j]->objType == DO_ATTRDEF &&
1151  ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
1152  {
1153  repairTableAttrDefMultiLoop(loop[i], loop[j]);
1154  return;
1155  }
1156  }
1157  }
1158  }
1159  }
1160 
1161  /* Domain and CHECK constraint */
1162  if (nLoop == 2 &&
1163  loop[0]->objType == DO_TYPE &&
1164  loop[1]->objType == DO_CONSTRAINT &&
1165  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1166  ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
1167  {
1168  repairDomainConstraintLoop(loop[0], loop[1]);
1169  return;
1170  }
1171  if (nLoop == 2 &&
1172  loop[1]->objType == DO_TYPE &&
1173  loop[0]->objType == DO_CONSTRAINT &&
1174  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1175  ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
1176  {
1177  repairDomainConstraintLoop(loop[1], loop[0]);
1178  return;
1179  }
1180 
1181  /* Indirect loop involving domain and CHECK constraint */
1182  if (nLoop > 2)
1183  {
1184  for (i = 0; i < nLoop; i++)
1185  {
1186  if (loop[i]->objType == DO_TYPE)
1187  {
1188  for (j = 0; j < nLoop; j++)
1189  {
1190  if (loop[j]->objType == DO_CONSTRAINT &&
1191  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1192  ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
1193  {
1194  repairDomainConstraintMultiLoop(loop[i], loop[j]);
1195  return;
1196  }
1197  }
1198  }
1199  }
1200  }
1201 
1202  /*
1203  * Loop of table with itself --- just ignore it.
1204  *
1205  * (Actually, what this arises from is a dependency of a table column on
1206  * another column, which happened with generated columns before v15; or a
1207  * dependency of a table column on the whole table, which happens with
1208  * partitioning. But we didn't pay attention to sub-object IDs while
1209  * collecting the dependency data, so we can't see that here.)
1210  */
1211  if (nLoop == 1)
1212  {
1213  if (loop[0]->objType == DO_TABLE)
1214  {
1215  removeObjectDependency(loop[0], loop[0]->dumpId);
1216  return;
1217  }
1218  }
1219 
1220  /*
1221  * If all the objects are TABLE_DATA items, what we must have is a
1222  * circular set of foreign key constraints (or a single self-referential
1223  * table). Print an appropriate complaint and break the loop arbitrarily.
1224  */
1225  for (i = 0; i < nLoop; i++)
1226  {
1227  if (loop[i]->objType != DO_TABLE_DATA)
1228  break;
1229  }
1230  if (i >= nLoop)
1231  {
1232  pg_log_warning(ngettext("there are circular foreign-key constraints on this table:",
1233  "there are circular foreign-key constraints among these tables:",
1234  nLoop));
1235  for (i = 0; i < nLoop; i++)
1236  pg_log_info(" %s", loop[i]->name);
1237  pg_log_info("You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.");
1238  pg_log_info("Consider using a full dump instead of a --data-only dump to avoid this problem.");
1239  if (nLoop > 1)
1240  removeObjectDependency(loop[0], loop[1]->dumpId);
1241  else /* must be a self-dependency */
1242  removeObjectDependency(loop[0], loop[0]->dumpId);
1243  return;
1244  }
1245 
1246  /*
1247  * If we can't find a principled way to break the loop, complain and break
1248  * it in an arbitrary fashion.
1249  */
1250  pg_log_warning("could not resolve dependency loop among these items:");
1251  for (i = 0; i < nLoop; i++)
1252  {
1253  char buf[1024];
1254 
1255  describeDumpableObject(loop[i], buf, sizeof(buf));
1256  pg_log_info(" %s", buf);
1257  }
1258 
1259  if (nLoop > 1)
1260  removeObjectDependency(loop[0], loop[1]->dumpId);
1261  else /* must be a self-dependency */
1262  removeObjectDependency(loop[0], loop[0]->dumpId);
1263 }
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:747
#define ngettext(s, p, n)
Definition: c.h:1179
const char * name
Definition: encode.c:561
#define pg_log_info(...)
Definition: logging.h:124
static void repairMatViewBoundaryMultiLoop(DumpableObject *boundaryobj, DumpableObject *nextobj)
Definition: pg_dump_sort.c:856
static void repairTableAttrDefLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:912
static void repairTableConstraintLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:878
static void repairTableAttrDefMultiLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:920
static void repairViewRuleMultiLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:822
static void repairDomainConstraintLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:935
static void repairTableConstraintMultiLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:895
static void describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
static void repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
Definition: pg_dump_sort.c:771
static void repairDomainConstraintMultiLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:943
static void repairIndexLoop(DumpableObject *partedindex, DumpableObject *partindex)
Definition: pg_dump_sort.c:957
static void repairViewRuleLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:802
#define pg_log_warning(...)
Definition: pgfnames.c:24

References buf, describeDumpableObject(), DO_ATTRDEF, DO_CONSTRAINT, DO_FUNC, DO_INDEX, DO_PRE_DATA_BOUNDARY, DO_RULE, DO_TABLE, DO_TABLE_DATA, DO_TYPE, i, j, name, ngettext, pg_log_info, pg_log_warning, removeObjectDependency(), repairDomainConstraintLoop(), repairDomainConstraintMultiLoop(), repairIndexLoop(), repairMatViewBoundaryMultiLoop(), repairTableAttrDefLoop(), repairTableAttrDefMultiLoop(), repairTableConstraintLoop(), repairTableConstraintMultiLoop(), repairTypeFuncLoop(), repairViewRuleLoop(), and repairViewRuleMultiLoop().

Referenced by findDependencyLoops().

◆ repairDomainConstraintLoop()

static void repairDomainConstraintLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 935 of file pg_dump_sort.c.

937 {
938  /* remove constraint's dependency on domain */
939  removeObjectDependency(constraintobj, domainobj->dumpId);
940 }

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairDomainConstraintMultiLoop()

static void repairDomainConstraintMultiLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 943 of file pg_dump_sort.c.

945 {
946  /* remove domain's dependency on constraint */
947  removeObjectDependency(domainobj, constraintobj->dumpId);
948  /* mark constraint as needing its own dump */
949  ((ConstraintInfo *) constraintobj)->separate = true;
950  /* put back constraint's dependency on domain */
951  addObjectDependency(constraintobj, domainobj->dumpId);
952  /* now that constraint is separate, it must be post-data */
953  addObjectDependency(constraintobj, postDataBoundId);
954 }
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:720
static DumpId postDataBoundId
Definition: pg_dump_sort.c:156

References addObjectDependency(), _dumpableObject::dumpId, postDataBoundId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairIndexLoop()

static void repairIndexLoop ( DumpableObject partedindex,
DumpableObject partindex 
)
static

Definition at line 957 of file pg_dump_sort.c.

959 {
960  removeObjectDependency(partedindex, partindex->dumpId);
961 }

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairMatViewBoundaryMultiLoop()

static void repairMatViewBoundaryMultiLoop ( DumpableObject boundaryobj,
DumpableObject nextobj 
)
static

Definition at line 856 of file pg_dump_sort.c.

858 {
859  /* remove boundary's dependency on object after it in loop */
860  removeObjectDependency(boundaryobj, nextobj->dumpId);
861  /* if that object is a matview, mark it as postponed into post-data */
862  if (nextobj->objType == DO_TABLE)
863  {
864  TableInfo *nextinfo = (TableInfo *) nextobj;
865 
866  if (nextinfo->relkind == RELKIND_MATVIEW)
867  nextinfo->postponed_def = true;
868  }
869 }
char relkind
Definition: pg_dump.h:286
bool postponed_def
Definition: pg_dump.h:319

References DO_TABLE, _dumpableObject::dumpId, _dumpableObject::objType, _tableInfo::postponed_def, _tableInfo::relkind, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairTableAttrDefLoop()

static void repairTableAttrDefLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 912 of file pg_dump_sort.c.

914 {
915  /* remove attrdef's dependency on table */
916  removeObjectDependency(attrdefobj, tableobj->dumpId);
917 }

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairTableAttrDefMultiLoop()

static void repairTableAttrDefMultiLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 920 of file pg_dump_sort.c.

922 {
923  /* remove table's dependency on attrdef */
924  removeObjectDependency(tableobj, attrdefobj->dumpId);
925  /* mark attrdef as needing its own dump */
926  ((AttrDefInfo *) attrdefobj)->separate = true;
927  /* put back attrdef's dependency on table */
928  addObjectDependency(attrdefobj, tableobj->dumpId);
929 }

References addObjectDependency(), _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairTableConstraintLoop()

static void repairTableConstraintLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 878 of file pg_dump_sort.c.

880 {
881  /* remove constraint's dependency on table */
882  removeObjectDependency(constraintobj, tableobj->dumpId);
883 }

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairTableConstraintMultiLoop()

static void repairTableConstraintMultiLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 895 of file pg_dump_sort.c.

897 {
898  /* remove table's dependency on constraint */
899  removeObjectDependency(tableobj, constraintobj->dumpId);
900  /* mark constraint as needing its own dump */
901  ((ConstraintInfo *) constraintobj)->separate = true;
902  /* put back constraint's dependency on table */
903  addObjectDependency(constraintobj, tableobj->dumpId);
904  /* now that constraint is separate, it must be post-data */
905  addObjectDependency(constraintobj, postDataBoundId);
906 }

References addObjectDependency(), _dumpableObject::dumpId, postDataBoundId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairTypeFuncLoop()

static void repairTypeFuncLoop ( DumpableObject typeobj,
DumpableObject funcobj 
)
static

Definition at line 771 of file pg_dump_sort.c.

772 {
773  TypeInfo *typeInfo = (TypeInfo *) typeobj;
774 
775  /* remove function's dependency on type */
776  removeObjectDependency(funcobj, typeobj->dumpId);
777 
778  /* add function's dependency on shell type, instead */
779  if (typeInfo->shellType)
780  {
781  addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
782 
783  /*
784  * Mark shell type (always including the definition, as we need the
785  * shell type defined to identify the function fully) as to be dumped
786  * if any such function is
787  */
788  if (funcobj->dump)
789  typeInfo->shellType->dobj.dump = funcobj->dump |
791  }
792 }
#define DUMP_COMPONENT_DEFINITION
Definition: pg_dump.h:96
DumpComponents dump
Definition: pg_dump.h:138
DumpableObject dobj
Definition: pg_dump.h:216
struct _shellTypeInfo * shellType
Definition: pg_dump.h:208

References addObjectDependency(), _shellTypeInfo::dobj, _dumpableObject::dump, DUMP_COMPONENT_DEFINITION, _dumpableObject::dumpId, removeObjectDependency(), and _typeInfo::shellType.

Referenced by repairDependencyLoop().

◆ repairViewRuleLoop()

static void repairViewRuleLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 802 of file pg_dump_sort.c.

804 {
805  /* remove rule's dependency on view */
806  removeObjectDependency(ruleobj, viewobj->dumpId);
807  /* flags on the two objects are already set correctly for this case */
808 }

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

◆ repairViewRuleMultiLoop()

static void repairViewRuleMultiLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 822 of file pg_dump_sort.c.

824 {
825  TableInfo *viewinfo = (TableInfo *) viewobj;
826  RuleInfo *ruleinfo = (RuleInfo *) ruleobj;
827 
828  /* remove view's dependency on rule */
829  removeObjectDependency(viewobj, ruleobj->dumpId);
830  /* mark view to be printed with a dummy definition */
831  viewinfo->dummy_view = true;
832  /* mark rule as needing its own dump */
833  ruleinfo->separate = true;
834  /* put back rule's dependency on view */
835  addObjectDependency(ruleobj, viewobj->dumpId);
836  /* now that rule is separate, it must be post-data */
838 }
bool separate
Definition: pg_dump.h:430
bool dummy_view
Definition: pg_dump.h:318

References addObjectDependency(), _tableInfo::dummy_view, _dumpableObject::dumpId, postDataBoundId, removeObjectDependency(), and _ruleInfo::separate.

Referenced by repairDependencyLoop().

◆ sortDumpableObjects()

void sortDumpableObjects ( DumpableObject **  objs,
int  numObjs,
DumpId  preBoundaryId,
DumpId  postBoundaryId 
)

Definition at line 319 of file pg_dump_sort.c.

321 {
322  DumpableObject **ordering;
323  int nOrdering;
324 
325  if (numObjs <= 0) /* can't happen anymore ... */
326  return;
327 
328  /*
329  * Saving the boundary IDs in static variables is a bit grotty, but seems
330  * better than adding them to parameter lists of subsidiary functions.
331  */
332  preDataBoundId = preBoundaryId;
333  postDataBoundId = postBoundaryId;
334 
335  ordering = (DumpableObject **) pg_malloc(numObjs * sizeof(DumpableObject *));
336  while (!TopoSort(objs, numObjs, ordering, &nOrdering))
337  findDependencyLoops(ordering, nOrdering, numObjs);
338 
339  memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));
340 
341  free(ordering);
342 }
static void findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
Definition: pg_dump_sort.c:590
static DumpId preDataBoundId
Definition: pg_dump_sort.c:155
static bool TopoSort(DumpableObject **objs, int numObjs, DumpableObject **ordering, int *nOrdering)
Definition: pg_dump_sort.c:371

References findDependencyLoops(), free, pg_malloc(), postDataBoundId, preDataBoundId, and TopoSort().

Referenced by main().

◆ sortDumpableObjectsByTypeName()

void sortDumpableObjectsByTypeName ( DumpableObject **  objs,
int  numObjs 
)

Definition at line 186 of file pg_dump_sort.c.

187 {
188  if (numObjs > 1)
189  qsort((void *) objs, numObjs, sizeof(DumpableObject *),
191 }
static int DOTypeNameCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:194
#define qsort(a, b, c, d)
Definition: port.h:495

References DOTypeNameCompare(), and qsort.

Referenced by main().

◆ StaticAssertDecl()

StaticAssertDecl ( lengthof(dbObjectTypePriority = =(DO_SUBSCRIPTION+1),
"array length mismatch"   
)

◆ TopoSort()

static bool TopoSort ( DumpableObject **  objs,
int  numObjs,
DumpableObject **  ordering,
int *  nOrdering 
)
static

Definition at line 371 of file pg_dump_sort.c.

375 {
376  DumpId maxDumpId = getMaxDumpId();
377  int *pendingHeap;
378  int *beforeConstraints;
379  int *idMap;
380  DumpableObject *obj;
381  int heapLength;
382  int i,
383  j,
384  k;
385 
386  /*
387  * This is basically the same algorithm shown for topological sorting in
388  * Knuth's Volume 1. However, we would like to minimize unnecessary
389  * rearrangement of the input ordering; that is, when we have a choice of
390  * which item to output next, we always want to take the one highest in
391  * the original list. Therefore, instead of maintaining an unordered
392  * linked list of items-ready-to-output as Knuth does, we maintain a heap
393  * of their item numbers, which we can use as a priority queue. This
394  * turns the algorithm from O(N) to O(N log N) because each insertion or
395  * removal of a heap item takes O(log N) time. However, that's still
396  * plenty fast enough for this application.
397  */
398 
399  *nOrdering = numObjs; /* for success return */
400 
401  /* Eliminate the null case */
402  if (numObjs <= 0)
403  return true;
404 
405  /* Create workspace for the above-described heap */
406  pendingHeap = (int *) pg_malloc(numObjs * sizeof(int));
407 
408  /*
409  * Scan the constraints, and for each item in the input, generate a count
410  * of the number of constraints that say it must be before something else.
411  * The count for the item with dumpId j is stored in beforeConstraints[j].
412  * We also make a map showing the input-order index of the item with
413  * dumpId j.
414  */
415  beforeConstraints = (int *) pg_malloc0((maxDumpId + 1) * sizeof(int));
416  idMap = (int *) pg_malloc((maxDumpId + 1) * sizeof(int));
417  for (i = 0; i < numObjs; i++)
418  {
419  obj = objs[i];
420  j = obj->dumpId;
421  if (j <= 0 || j > maxDumpId)
422  pg_fatal("invalid dumpId %d", j);
423  idMap[j] = i;
424  for (j = 0; j < obj->nDeps; j++)
425  {
426  k = obj->dependencies[j];
427  if (k <= 0 || k > maxDumpId)
428  pg_fatal("invalid dependency %d", k);
429  beforeConstraints[k]++;
430  }
431  }
432 
433  /*
434  * Now initialize the heap of items-ready-to-output by filling it with the
435  * indexes of items that already have beforeConstraints[id] == 0.
436  *
437  * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
438  * in the range 1..heapLength-1 (note we are using 0-based subscripts
439  * here, while the discussion in Knuth assumes 1-based subscripts). So, if
440  * we simply enter the indexes into pendingHeap[] in decreasing order, we
441  * a-fortiori have the heap invariant satisfied at completion of this
442  * loop, and don't need to do any sift-up comparisons.
443  */
444  heapLength = 0;
445  for (i = numObjs; --i >= 0;)
446  {
447  if (beforeConstraints[objs[i]->dumpId] == 0)
448  pendingHeap[heapLength++] = i;
449  }
450 
451  /*--------------------
452  * Now emit objects, working backwards in the output list. At each step,
453  * we use the priority heap to select the last item that has no remaining
454  * before-constraints. We remove that item from the heap, output it to
455  * ordering[], and decrease the beforeConstraints count of each of the
456  * items it was constrained against. Whenever an item's beforeConstraints
457  * count is thereby decreased to zero, we insert it into the priority heap
458  * to show that it is a candidate to output. We are done when the heap
459  * becomes empty; if we have output every element then we succeeded,
460  * otherwise we failed.
461  * i = number of ordering[] entries left to output
462  * j = objs[] index of item we are outputting
463  * k = temp for scanning constraint list for item j
464  *--------------------
465  */
466  i = numObjs;
467  while (heapLength > 0)
468  {
469  /* Select object to output by removing largest heap member */
470  j = removeHeapElement(pendingHeap, heapLength--);
471  obj = objs[j];
472  /* Output candidate to ordering[] */
473  ordering[--i] = obj;
474  /* Update beforeConstraints counts of its predecessors */
475  for (k = 0; k < obj->nDeps; k++)
476  {
477  int id = obj->dependencies[k];
478 
479  if ((--beforeConstraints[id]) == 0)
480  addHeapElement(idMap[id], pendingHeap, heapLength++);
481  }
482  }
483 
484  /*
485  * If we failed, report the objects that couldn't be output; these are the
486  * ones with beforeConstraints[] still nonzero.
487  */
488  if (i != 0)
489  {
490  k = 0;
491  for (j = 1; j <= maxDumpId; j++)
492  {
493  if (beforeConstraints[j] != 0)
494  ordering[k++] = objs[idMap[j]];
495  }
496  *nOrdering = k;
497  }
498 
499  /* Done */
500  free(pendingHeap);
502  free(idMap);
503 
504  return (i == 0);
505 }
static int * beforeConstraints
Definition: deadlock.c:107
static int removeHeapElement(int *heap, int heapLength)
Definition: pg_dump_sort.c:545
static void addHeapElement(int val, int *heap, int heapLength)
Definition: pg_dump_sort.c:514

References addHeapElement(), beforeConstraints, _dumpableObject::dependencies, _dumpableObject::dumpId, free, getMaxDumpId(), i, j, _dumpableObject::nDeps, pg_fatal, pg_malloc(), pg_malloc0(), and removeHeapElement().

Referenced by sortDumpableObjects().

Variable Documentation

◆ dbObjectTypePriority

const int dbObjectTypePriority[]
static

Definition at line 102 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

◆ postDataBoundId

◆ preDataBoundId

DumpId preDataBoundId
static

Definition at line 155 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().