src/fkey.c

   1 /*
   2 **
   3 ** The author disclaims copyright to this source code.  In place of
   4 ** a legal notice, here is a blessing:
   5 **
   6 **    May you do good and not evil.
   7 **    May you find forgiveness for yourself and forgive others.
   8 **    May you share freely, never taking more than you give.
   9 **
  10 *************************************************************************
  11 ** This file contains code used by the compiler to add foreign key
  12 ** support to compiled SQL statements.
  13 */
  14 #include "sqliteInt.h"
  15
  16 #ifndef SQLITE_OMIT_FOREIGN_KEY
  17 #ifndef SQLITE_OMIT_TRIGGER
  18
  19 /*
  20 ** Deferred and Immediate FKs
  21 ** --------------------------
  22 **
  23 ** Foreign keys in SQLite come in two flavours: deferred and immediate.
  24 ** If an immediate foreign key constraint is violated,
  25 ** SQLITE_CONSTRAINT_FOREIGNKEY is returned and the current
  26 ** statement transaction rolled back. If a
  27 ** deferred foreign key constraint is violated, no action is taken
  28 ** immediately. However if the application attempts to commit the
  29 ** transaction before fixing the constraint violation, the attempt fails.
  30 **
  31 ** Deferred constraints are implemented using a simple counter associated
  32 ** with the database handle. The counter is set to zero each time a
  33 ** database transaction is opened. Each time a statement is executed
  34 ** that causes a foreign key violation, the counter is incremented. Each
  35 ** time a statement is executed that removes an existing violation from
  36 ** the database, the counter is decremented. When the transaction is
  37 ** committed, the commit fails if the current value of the counter is
  38 ** greater than zero. This scheme has two big drawbacks:
  39 **
  40 **   * When a commit fails due to a deferred foreign key constraint,
  41 **     there is no way to tell which foreign constraint is not satisfied,
  42 **     or which row it is not satisfied for.
  43 **
  44 **   * If the database contains foreign key violations when the
  45 **     transaction is opened, this may cause the mechanism to malfunction.
  46 **
  47 ** Despite these problems, this approach is adopted as it seems simpler
  48 ** than the alternatives.
  49 **
  50 ** INSERT operations:
  51 **
  52 **   I.1) For each FK for which the table is the child table, search
  53 **        the parent table for a match. If none is found increment the
  54 **        constraint counter.
  55 **
  56 **   I.2) For each FK for which the table is the parent table,
  57 **        search the child table for rows that correspond to the new
  58 **        row in the parent table. Decrement the counter for each row
  59 **        found (as the constraint is now satisfied).
  60 **
  61 ** DELETE operations:
  62 **
  63 **   D.1) For each FK for which the table is the child table,
  64 **        search the parent table for a row that corresponds to the
  65 **        deleted row in the child table. If such a row is not found,
  66 **        decrement the counter.
  67 **
  68 **   D.2) For each FK for which the table is the parent table, search
  69 **        the child table for rows that correspond to the deleted row
  70 **        in the parent table. For each found increment the counter.
  71 **
  72 ** UPDATE operations:
  73 **
  74 **   An UPDATE command requires that all 4 steps above are taken, but only
  75 **   for FK constraints for which the affected columns are actually
  76 **   modified (values must be compared at runtime).
  77 **
  78 ** Note that I.1 and D.1 are very similar operations, as are I.2 and D.2.
  79 ** This simplifies the implementation a bit.
  80 **
  81 ** For the purposes of immediate FK constraints, the OR REPLACE conflict
  82 ** resolution is considered to delete rows before the new row is inserted.
  83 ** If a delete caused by OR REPLACE violates an FK constraint, an exception
  84 ** is thrown, even if the FK constraint would be satisfied after the new
  85 ** row is inserted.
  86 **
  87 ** Immediate constraints are usually handled similarly. The only difference
  88 ** is that the counter used is stored as part of each individual statement
  89 ** object (struct Vdbe). If, after the statement has run, its immediate
  90 ** constraint counter is greater than zero,
  91 ** it returns SQLITE_CONSTRAINT_FOREIGNKEY
  92 ** and the statement transaction is rolled back. An exception is an INSERT
  93 ** statement that inserts a single row only (no triggers). In this case,
  94 ** instead of using a counter, an exception is thrown immediately if the
  95 ** INSERT violates a foreign key constraint. This is necessary as such
  96 ** an INSERT does not open a statement transaction.
  97 **
  98 ** TODO: How should dropping a table be handled? How should renaming a
  99 ** table be handled?
 100 **
 101 **
 102 ** Query API Notes
 103 ** ---------------
 104 **
 105 ** Before coding an UPDATE or DELETE row operation, the code-generator
 106 ** for those two operations needs to know whether or not the operation
 107 ** requires any FK processing and, if so, which columns of the original
 108 ** row are required by the FK processing VDBE code (i.e. if FKs were
 109 ** implemented using triggers, which of the old.* columns would be
 110 ** accessed). No information is required by the code-generator before
 111 ** coding an INSERT operation. The functions used by the UPDATE/DELETE
 112 ** generation code to query for this information are:
 113 **
 114 **   sqlite3FkRequired() - Test to see if FK processing is required.
 115 **   sqlite3FkOldmask()  - Query for the set of required old.* columns.
 116 **
 117 **
 118 ** Externally accessible module functions
 119 ** --------------------------------------
 120 **
 121 **   sqlite3FkCheck()    - Check for foreign key violations.
 122 **   sqlite3FkActions()  - Code triggers for ON UPDATE/ON DELETE actions.
 123 **   sqlite3FkDelete()   - Delete an FKey structure.
 124 */
 125
 126 /*
 127 ** VDBE Calling Convention
 128 ** -----------------------
 129 **
 130 ** Example:
 131 **
 132 **   For the following INSERT statement:
 133 **
 134 **     CREATE TABLE t1(a, b INTEGER PRIMARY KEY, c);
 135 **     INSERT INTO t1 VALUES(1, 2, 3.1);
 136 **
 137 **   Register (x):        2    (type integer)
 138 **   Register (x+1):      1    (type integer)
 139 **   Register (x+2):      NULL (type NULL)
 140 **   Register (x+3):      3.1  (type real)
 141 */
 142
 143 /*
 144 ** A foreign key constraint requires that the key columns in the parent
 145 ** table are collectively subject to a UNIQUE or PRIMARY KEY constraint.
 146 ** Given that pParent is the parent table for foreign key constraint pFKey,
 147 ** search the schema for a unique index on the parent key columns.
 148 **
 149 ** If successful, zero is returned. If the parent key is an INTEGER PRIMARY
 150 ** KEY column, then output variable *ppIdx is set to NULL. Otherwise, *ppIdx
 151 ** is set to point to the unique index.
 152 **
 153 ** If the parent key consists of a single column (the foreign key constraint
 154 ** is not a composite foreign key), output variable *paiCol is set to NULL.
 155 ** Otherwise, it is set to point to an allocated array of size N, where
 156 ** N is the number of columns in the parent key. The first element of the
 157 ** array is the index of the child table column that is mapped by the FK
 158 ** constraint to the parent table column stored in the left-most column
 159 ** of index *ppIdx. The second element of the array is the index of the
 160 ** child table column that corresponds to the second left-most column of
 161 ** *ppIdx, and so on.
 162 **
 163 ** If the required index cannot be found, either because:
 164 **
 165 **   1) The named parent key columns do not exist, or
 166 **
 167 **   2) The named parent key columns do exist, but are not subject to a
 168 **      UNIQUE or PRIMARY KEY constraint, or
 169 **
 170 **   3) No parent key columns were provided explicitly as part of the
 171 **      foreign key definition, and the parent table does not have a
 172 **      PRIMARY KEY, or
 173 **
 174 **   4) No parent key columns were provided explicitly as part of the
 175 **      foreign key definition, and the PRIMARY KEY of the parent table
 176 **      consists of a different number of columns to the child key in
 177 **      the child table.
 178 **
 179 ** then non-zero is returned, and a "foreign key mismatch" error loaded
 180 ** into pParse. If an OOM error occurs, non-zero is returned and the
 181 ** pParse->db->mallocFailed flag is set.
 182 */
 183 int sqlite3FkLocateIndex(
 184   Parse *pParse,                  /* Parse context to store any error in */
 185   Table *pParent,                 /* Parent table of FK constraint pFKey */
 186   FKey *pFKey,                    /* Foreign key to find index for */
 187   Index **ppIdx,                  /* OUT: Unique index on parent table */
 188   int **paiCol                    /* OUT: Map of index columns in pFKey */
 189 ){
 190   Index *pIdx = 0;                    /* Value to return via *ppIdx */
 191   int *aiCol = 0;                     /* Value to return via *paiCol */
 192   int nCol = pFKey->nCol;             /* Number of columns in parent key */
 193   char *zKey = pFKey->aCol[0].zCol;   /* Name of left-most parent key column */
 194
 195   /* The caller is responsible for zeroing output parameters. */
 196   assert( ppIdx && *ppIdx==0 );
 197   assert( !paiCol || *paiCol==0 );
 198   assert( pParse );
 199
 200   /* If this is a non-composite (single column) foreign key, check if it
 201   ** maps to the INTEGER PRIMARY KEY of table pParent. If so, leave *ppIdx
 202   ** and *paiCol set to zero and return early.
 203   **
 204   ** Otherwise, for a composite foreign key (more than one column), allocate
 205   ** space for the aiCol array (returned via output parameter *paiCol).
 206   ** Non-composite foreign keys do not require the aiCol array.
 207   */
 208   if( nCol==1 ){
 209     /* The FK maps to the IPK if any of the following are true:
 210     **
 211     **   1) There is an INTEGER PRIMARY KEY column and the FK is implicitly
 212     **      mapped to the primary key of table pParent, or
 213     **   2) The FK is explicitly mapped to a column declared as INTEGER
 214     **      PRIMARY KEY.
 215     */
 216     if( pParent->iPKey>=0 ){
 217       if( !zKey ) return 0;
 218       if( !sqlite3StrICmp(pParent->aCol[pParent->iPKey].zCnName, zKey) ){
 219         return 0;
 220       }
 221     }
 222   }else if( paiCol ){
 223     assert( nCol>1 );
 224     aiCol = (int *)sqlite3DbMallocRawNN(pParse->db, nCol*sizeof(int));
 225     if( !aiCol ) return 1;
 226     *paiCol = aiCol;
 227   }
 228
 229   for(pIdx=pParent->pIndex; pIdx; pIdx=pIdx->pNext){
 230     if( pIdx->nKeyCol==nCol && IsUniqueIndex(pIdx) && pIdx->pPartIdxWhere==0 ){
 231       /* pIdx is a UNIQUE index (or a PRIMARY KEY) and has the right number
 232       ** of columns. If each indexed column corresponds to a foreign key
 233       ** column of pFKey, then this index is a winner.  */
 234
 235       if( zKey==0 ){
 236         /* If zKey is NULL, then this foreign key is implicitly mapped to
 237         ** the PRIMARY KEY of table pParent. The PRIMARY KEY index may be
 238         ** identified by the test.  */
 239         if( IsPrimaryKeyIndex(pIdx) ){
 240           if( aiCol ){
 241             int i;
 242             for(i=0; i<nCol; i++) aiCol[i] = pFKey->aCol[i].iFrom;
 243           }
 244           break;
 245         }
 246       }else{
 247         /* If zKey is non-NULL, then this foreign key was declared to
 248         ** map to an explicit list of columns in table pParent. Check if this
 249         ** index matches those columns. Also, check that the index uses
 250         ** the default collation sequences for each column. */
 251         int i, j;
 252         for(i=0; i<nCol; i++){
 253           i16 iCol = pIdx->aiColumn[i];     /* Index of column in parent tbl */
 254           const char *zDfltColl;            /* Def. collation for column */
 255           char *zIdxCol;                    /* Name of indexed column */
 256
 257           if( iCol<0 ) break; /* No foreign keys against expression indexes */
 258
 259           /* If the index uses a collation sequence that is different from
 260           ** the default collation sequence for the column, this index is
 261           ** unusable. Bail out early in this case.  */
 262           zDfltColl = sqlite3ColumnColl(&pParent->aCol[iCol]);
 263           if( !zDfltColl ) zDfltColl = sqlite3StrBINARY;
 264           if( sqlite3StrICmp(pIdx->azColl[i], zDfltColl) ) break;
 265
 266           zIdxCol = pParent->aCol[iCol].zCnName;
 267           for(j=0; j<nCol; j++){
 268             if( sqlite3StrICmp(pFKey->aCol[j].zCol, zIdxCol)==0 ){
 269               if( aiCol ) aiCol[i] = pFKey->aCol[j].iFrom;
 270               break;
 271             }
 272           }
 273           if( j==nCol ) break;
 274         }
 275         if( i==nCol ) break;      /* pIdx is usable */
 276       }
 277     }
 278   }
 279
 280   if( !pIdx ){
 281     if( !pParse->disableTriggers ){
 282       sqlite3ErrorMsg(pParse,
 283            "foreign key mismatch - \"%w\" referencing \"%w\"",
 284            pFKey->pFrom->zName, pFKey->zTo);
 285     }
 286     sqlite3DbFree(pParse->db, aiCol);
 287     return 1;
 288   }
 289
 290   *ppIdx = pIdx;
 291   return 0;
 292 }
 293
 294 /*
 295 ** This function is called when a row is inserted into or deleted from the
 296 ** child table of foreign key constraint pFKey. If an SQL UPDATE is executed
 297 ** on the child table of pFKey, this function is invoked twice for each row
 298 ** affected - once to "delete" the old row, and then again to "insert" the
 299 ** new row.
 300 **
 301 ** Each time it is called, this function generates VDBE code to locate the
 302 ** row in the parent table that corresponds to the row being inserted into
 303 ** or deleted from the child table. If the parent row can be found, no
 304 ** special action is taken. Otherwise, if the parent row can *not* be
 305 ** found in the parent table:
 306 **
 307 **   Operation | FK type   | Action taken
 308 **   --------------------------------------------------------------------------
 309 **   INSERT      immediate   Increment the "immediate constraint counter".
 310 **
 311 **   DELETE      immediate   Decrement the "immediate constraint counter".
 312 **
 313 **   INSERT      deferred    Increment the "deferred constraint counter".
 314 **
 315 **   DELETE      deferred    Decrement the "deferred constraint counter".
 316 **
 317 ** These operations are identified in the comment at the top of this file
 318 ** (fkey.c) as "I.1" and "D.1".
 319 */
 320 static void fkLookupParent(
 321   Parse *pParse,        /* Parse context */
 322   int iDb,              /* Index of database housing pTab */
 323   Table *pTab,          /* Parent table of FK pFKey */
 324   Index *pIdx,          /* Unique index on parent key columns in pTab */
 325   FKey *pFKey,          /* Foreign key constraint */
 326   int *aiCol,           /* Map from parent key columns to child table columns */
 327   int regData,          /* Address of array containing child table row */
 328   int nIncr,            /* Increment constraint counter by this */
 329   int isIgnore          /* If true, pretend pTab contains all NULL values */
 330 ){
 331   int i;                                    /* Iterator variable */
 332   Vdbe *v = sqlite3GetVdbe(pParse);         /* Vdbe to add code to */
 333   int iCur = pParse->nTab - 1;              /* Cursor number to use */
 334   int iOk = sqlite3VdbeMakeLabel(pParse);   /* jump here if parent key found */
 335
 336   sqlite3VdbeVerifyAbortable(v,
 337     (!pFKey->isDeferred
 338       && !(pParse->db->flags & SQLITE_DeferFKs)
 339       && !pParse->pToplevel
 340       && !pParse->isMultiWrite) ? OE_Abort : OE_Ignore);
 341
 342   /* If nIncr is less than zero, then check at runtime if there are any
 343   ** outstanding constraints to resolve. If there are not, there is no need
 344   ** to check if deleting this row resolves any outstanding violations.
 345   **
 346   ** Check if any of the key columns in the child table row are NULL. If
 347   ** any are, then the constraint is considered satisfied. No need to
 348   ** search for a matching row in the parent table.  */
 349   if( nIncr<0 ){
 350     sqlite3VdbeAddOp2(v, OP_FkIfZero, pFKey->isDeferred, iOk);
 351     VdbeCoverage(v);
 352   }
 353   for(i=0; i<pFKey->nCol; i++){
 354     int iReg = sqlite3TableColumnToStorage(pFKey->pFrom,aiCol[i]) + regData + 1;
 355     sqlite3VdbeAddOp2(v, OP_IsNull, iReg, iOk); VdbeCoverage(v);
 356   }
 357
 358   if( isIgnore==0 ){
 359     if( pIdx==0 ){
 360       /* If pIdx is NULL, then the parent key is the INTEGER PRIMARY KEY
 361       ** column of the parent table (table pTab).  */
 362       int iMustBeInt;               /* Address of MustBeInt instruction */
 363       int regTemp = sqlite3GetTempReg(pParse);
 364
 365       /* Invoke MustBeInt to coerce the child key value to an integer (i.e.
 366       ** apply the affinity of the parent key). If this fails, then there
 367       ** is no matching parent key. Before using MustBeInt, make a copy of
 368       ** the value. Otherwise, the value inserted into the child key column
 369       ** will have INTEGER affinity applied to it, which may not be correct.  */
 370       sqlite3VdbeAddOp2(v, OP_SCopy,
 371         sqlite3TableColumnToStorage(pFKey->pFrom,aiCol[0])+1+regData, regTemp);
 372       iMustBeInt = sqlite3VdbeAddOp2(v, OP_MustBeInt, regTemp, 0);
 373       VdbeCoverage(v);
 374
 375       /* If the parent table is the same as the child table, and we are about
 376       ** to increment the constraint-counter (i.e. this is an INSERT operation),
 377       ** then check if the row being inserted matches itself. If so, do not
 378       ** increment the constraint-counter.  */
 379       if( pTab==pFKey->pFrom && nIncr==1 ){
 380         sqlite3VdbeAddOp3(v, OP_Eq, regData, iOk, regTemp); VdbeCoverage(v);
 381         sqlite3VdbeChangeP5(v, SQLITE_NOTNULL);
 382       }
 383
 384       sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenRead);
 385       sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, regTemp); VdbeCoverage(v);
 386       sqlite3VdbeGoto(v, iOk);
 387       sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
 388       sqlite3VdbeJumpHere(v, iMustBeInt);
 389       sqlite3ReleaseTempReg(pParse, regTemp);
 390     }else{
 391       int nCol = pFKey->nCol;
 392       int regTemp = sqlite3GetTempRange(pParse, nCol);
 393
 394       sqlite3VdbeAddOp3(v, OP_OpenRead, iCur, pIdx->tnum, iDb);
 395       sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
 396       for(i=0; i<nCol; i++){
 397         sqlite3VdbeAddOp2(v, OP_Copy,
 398                sqlite3TableColumnToStorage(pFKey->pFrom, aiCol[i])+1+regData,
 399                regTemp+i);
 400       }
 401
 402       /* If the parent table is the same as the child table, and we are about
 403       ** to increment the constraint-counter (i.e. this is an INSERT operation),
 404       ** then check if the row being inserted matches itself. If so, do not
 405       ** increment the constraint-counter.
 406       **
 407       ** If any of the parent-key values are NULL, then the row cannot match
 408       ** itself. So set JUMPIFNULL to make sure we do the OP_Found if any
 409       ** of the parent-key values are NULL (at this point it is known that
 410       ** none of the child key values are).
 411       */
 412       if( pTab==pFKey->pFrom && nIncr==1 ){
 413         int iJump = sqlite3VdbeCurrentAddr(v) + nCol + 1;
 414         for(i=0; i<nCol; i++){
 415           int iChild = sqlite3TableColumnToStorage(pFKey->pFrom,aiCol[i])
 416                               +1+regData;
 417           int iParent = 1+regData;
 418           iParent += sqlite3TableColumnToStorage(pIdx->pTable,
 419                                                  pIdx->aiColumn[i]);
 420           assert( pIdx->aiColumn[i]>=0 );
 421           assert( aiCol[i]!=pTab->iPKey );
 422           if( pIdx->aiColumn[i]==pTab->iPKey ){
 423             /* The parent key is a composite key that includes the IPK column */
 424             iParent = regData;
 425           }
 426           sqlite3VdbeAddOp3(v, OP_Ne, iChild, iJump, iParent); VdbeCoverage(v);
 427           sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
 428         }
 429         sqlite3VdbeGoto(v, iOk);
 430       }
 431
 432       sqlite3VdbeAddOp4(v, OP_Affinity, regTemp, nCol, 0,
 433                         sqlite3IndexAffinityStr(pParse->db,pIdx), nCol);
 434       sqlite3VdbeAddOp4Int(v, OP_Found, iCur, iOk, regTemp, nCol);
 435       VdbeCoverage(v);
 436       sqlite3ReleaseTempRange(pParse, regTemp, nCol);
 437     }
 438   }
 439
 440   if( !pFKey->isDeferred && !(pParse->db->flags & SQLITE_DeferFKs)
 441    && !pParse->pToplevel
 442    && !pParse->isMultiWrite
 443   ){
 444     /* Special case: If this is an INSERT statement that will insert exactly
 445     ** one row into the table, raise a constraint immediately instead of
 446     ** incrementing a counter. This is necessary as the VM code is being
 447     ** generated for will not open a statement transaction.  */
 448     assert( nIncr==1 );
 449     sqlite3HaltConstraint(pParse, SQLITE_CONSTRAINT_FOREIGNKEY,
 450         OE_Abort, 0, P4_STATIC, P5_ConstraintFK);
 451   }else{
 452     if( nIncr>0 && pFKey->isDeferred==0 ){
 453       sqlite3MayAbort(pParse);
 454     }
 455     sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, nIncr);
 456   }
 457
 458   sqlite3VdbeResolveLabel(v, iOk);
 459   sqlite3VdbeAddOp1(v, OP_Close, iCur);
 460 }
 461
 462
 463 /*
 464 ** Return an Expr object that refers to a memory register corresponding
 465 ** to column iCol of table pTab.
 466 **
 467 ** regBase is the first of an array of register that contains the data
 468 ** for pTab.  regBase itself holds the rowid.  regBase+1 holds the first
 469 ** column.  regBase+2 holds the second column, and so forth.
 470 */
 471 static Expr *exprTableRegister(
 472   Parse *pParse,     /* Parsing and code generating context */
 473   Table *pTab,       /* The table whose content is at r[regBase]... */
 474   int regBase,       /* Contents of table pTab */
 475   i16 iCol           /* Which column of pTab is desired */
 476 ){
 477   Expr *pExpr;
 478   Column *pCol;
 479   const char *zColl;
 480   sqlite3 *db = pParse->db;
 481
 482   pExpr = sqlite3Expr(db, TK_REGISTER, 0);
 483   if( pExpr ){
 484     if( iCol>=0 && iCol!=pTab->iPKey ){
 485       pCol = &pTab->aCol[iCol];
 486       pExpr->iTable = regBase + sqlite3TableColumnToStorage(pTab,iCol) + 1;
 487       pExpr->affExpr = pCol->affinity;
 488       zColl = sqlite3ColumnColl(pCol);
 489       if( zColl==0 ) zColl = db->pDfltColl->zName;
 490       pExpr = sqlite3ExprAddCollateString(pParse, pExpr, zColl);
 491     }else{
 492       pExpr->iTable = regBase;
 493       pExpr->affExpr = SQLITE_AFF_INTEGER;
 494     }
 495   }
 496   return pExpr;
 497 }
 498
 499 /*
 500 ** Return an Expr object that refers to column iCol of table pTab which
 501 ** has cursor iCur.
 502 */
 503 static Expr *exprTableColumn(
 504   sqlite3 *db,      /* The database connection */
 505   Table *pTab,      /* The table whose column is desired */
 506   int iCursor,      /* The open cursor on the table */
 507   i16 iCol          /* The column that is wanted */
 508 ){
 509   Expr *pExpr = sqlite3Expr(db, TK_COLUMN, 0);
 510   if( pExpr ){
 511     assert( ExprUseYTab(pExpr) );
 512     pExpr->y.pTab = pTab;
 513     pExpr->iTable = iCursor;
 514     pExpr->iColumn = iCol;
 515   }
 516   return pExpr;
 517 }
 518
 519 /*
 520 ** This function is called to generate code executed when a row is deleted
 521 ** from the parent table of foreign key constraint pFKey and, if pFKey is
 522 ** deferred, when a row is inserted into the same table. When generating
 523 ** code for an SQL UPDATE operation, this function may be called twice -
 524 ** once to "delete" the old row and once to "insert" the new row.
 525 **
 526 ** Parameter nIncr is passed -1 when inserting a row (as this may decrease
 527 ** the number of FK violations in the db) or +1 when deleting one (as this
 528 ** may increase the number of FK constraint problems).
 529 **
 530 ** The code generated by this function scans through the rows in the child
 531 ** table that correspond to the parent table row being deleted or inserted.
 532 ** For each child row found, one of the following actions is taken:
 533 **
 534 **   Operation | FK type   | Action taken
 535 **   --------------------------------------------------------------------------
 536 **   DELETE      immediate   Increment the "immediate constraint counter".
 537 **
 538 **   INSERT      immediate   Decrement the "immediate constraint counter".
 539 **
 540 **   DELETE      deferred    Increment the "deferred constraint counter".
 541 **
 542 **   INSERT      deferred    Decrement the "deferred constraint counter".
 543 **
 544 ** These operations are identified in the comment at the top of this file
 545 ** (fkey.c) as "I.2" and "D.2".
 546 */
 547 static void fkScanChildren(
 548   Parse *pParse,                  /* Parse context */
 549   SrcList *pSrc,                  /* The child table to be scanned */
 550   Table *pTab,                    /* The parent table */
 551   Index *pIdx,                    /* Index on parent covering the foreign key */
 552   FKey *pFKey,                    /* The foreign key linking pSrc to pTab */
 553   int *aiCol,                     /* Map from pIdx cols to child table cols */
 554   int regData,                    /* Parent row data starts here */
 555   int nIncr                       /* Amount to increment deferred counter by */
 556 ){
 557   sqlite3 *db = pParse->db;       /* Database handle */
 558   int i;                          /* Iterator variable */
 559   Expr *pWhere = 0;               /* WHERE clause to scan with */
 560   NameContext sNameContext;       /* Context used to resolve WHERE clause */
 561   WhereInfo *pWInfo;              /* Context used by sqlite3WhereXXX() */
 562   int iFkIfZero = 0;              /* Address of OP_FkIfZero */
 563   Vdbe *v = sqlite3GetVdbe(pParse);
 564
 565   assert( pIdx==0 || pIdx->pTable==pTab );
 566   assert( pIdx==0 || pIdx->nKeyCol==pFKey->nCol );
 567   assert( pIdx!=0 || pFKey->nCol==1 );
 568   assert( pIdx!=0 || HasRowid(pTab) );
 569
 570   if( nIncr<0 ){
 571     iFkIfZero = sqlite3VdbeAddOp2(v, OP_FkIfZero, pFKey->isDeferred, 0);
 572     VdbeCoverage(v);
 573   }
 574
 575   /* Create an Expr object representing an SQL expression like:
 576   **
 577   **   <parent-key1> = <child-key1> AND <parent-key2> = <child-key2> ...
 578   **
 579   ** The collation sequence used for the comparison should be that of
 580   ** the parent key columns. The affinity of the parent key column should
 581   ** be applied to each child key value before the comparison takes place.
 582   */
 583   for(i=0; i<pFKey->nCol; i++){
 584     Expr *pLeft;                  /* Value from parent table row */
 585     Expr *pRight;                 /* Column ref to child table */
 586     Expr *pEq;                    /* Expression (pLeft = pRight) */
 587     i16 iCol;                     /* Index of column in child table */
 588     const char *zCol;             /* Name of column in child table */
 589
 590     iCol = pIdx ? pIdx->aiColumn[i] : -1;
 591     pLeft = exprTableRegister(pParse, pTab, regData, iCol);
 592     iCol = aiCol ? aiCol[i] : pFKey->aCol[0].iFrom;
 593     assert( iCol>=0 );
 594     zCol = pFKey->pFrom->aCol[iCol].zCnName;
 595     pRight = sqlite3Expr(db, TK_ID, zCol);
 596     pEq = sqlite3PExpr(pParse, TK_EQ, pLeft, pRight);
 597     pWhere = sqlite3ExprAnd(pParse, pWhere, pEq);
 598   }
 599
 600   /* If the child table is the same as the parent table, then add terms
 601   ** to the WHERE clause that prevent this entry from being scanned.
 602   ** The added WHERE clause terms are like this:
 603   **
 604   **     $current_rowid!=rowid
 605   **     NOT( $current_a==a AND $current_b==b AND ... )
 606   **
 607   ** The first form is used for rowid tables.  The second form is used
 608   ** for WITHOUT ROWID tables. In the second form, the *parent* key is
 609   ** (a,b,...). Either the parent or primary key could be used to
 610   ** uniquely identify the current row, but the parent key is more convenient
 611   ** as the required values have already been loaded into registers
 612   ** by the caller.
 613   */
 614   if( pTab==pFKey->pFrom && nIncr>0 ){
 615     Expr *pNe;                    /* Expression (pLeft != pRight) */
 616     Expr *pLeft;                  /* Value from parent table row */
 617     Expr *pRight;                 /* Column ref to child table */
 618     if( HasRowid(pTab) ){
 619       pLeft = exprTableRegister(pParse, pTab, regData, -1);
 620       pRight = exprTableColumn(db, pTab, pSrc->a[0].iCursor, -1);
 621       pNe = sqlite3PExpr(pParse, TK_NE, pLeft, pRight);
 622     }else{
 623       Expr *pEq, *pAll = 0;
 624       assert( pIdx!=0 );
 625       for(i=0; i<pIdx->nKeyCol; i++){
 626         i16 iCol = pIdx->aiColumn[i];
 627         assert( iCol>=0 );
 628         pLeft = exprTableRegister(pParse, pTab, regData, iCol);
 629         pRight = sqlite3Expr(db, TK_ID, pTab->aCol[iCol].zCnName);
 630         pEq = sqlite3PExpr(pParse, TK_IS, pLeft, pRight);
 631         pAll = sqlite3ExprAnd(pParse, pAll, pEq);
 632       }
 633       pNe = sqlite3PExpr(pParse, TK_NOT, pAll, 0);
 634     }
 635     pWhere = sqlite3ExprAnd(pParse, pWhere, pNe);
 636   }
 637
 638   /* Resolve the references in the WHERE clause. */
 639   memset(&sNameContext, 0, sizeof(NameContext));
 640   sNameContext.pSrcList = pSrc;
 641   sNameContext.pParse = pParse;
 642   sqlite3ResolveExprNames(&sNameContext, pWhere);
 643
 644   /* Create VDBE to loop through the entries in pSrc that match the WHERE
 645   ** clause. For each row found, increment either the deferred or immediate
 646   ** foreign key constraint counter. */
 647   if( pParse->nErr==0 ){
 648     pWInfo = sqlite3WhereBegin(pParse, pSrc, pWhere, 0, 0, 0, 0, 0);
 649     sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, nIncr);
 650     if( pWInfo ){
 651       sqlite3WhereEnd(pWInfo);
 652     }
 653   }
 654
 655   /* Clean up the WHERE clause constructed above. */
 656   sqlite3ExprDelete(db, pWhere);
 657   if( iFkIfZero ){
 658     sqlite3VdbeJumpHereOrPopInst(v, iFkIfZero);
 659   }
 660 }
 661
 662 /*
 663 ** This function returns a linked list of FKey objects (connected by
 664 ** FKey.pNextTo) holding all children of table pTab.  For example,
 665 ** given the following schema:
 666 **
 667 **   CREATE TABLE t1(a PRIMARY KEY);
 668 **   CREATE TABLE t2(b REFERENCES t1(a);
 669 **
 670 ** Calling this function with table "t1" as an argument returns a pointer
 671 ** to the FKey structure representing the foreign key constraint on table
 672 ** "t2". Calling this function with "t2" as the argument would return a
 673 ** NULL pointer (as there are no FK constraints for which t2 is the parent
 674 ** table).
 675 */
 676 FKey *sqlite3FkReferences(Table *pTab){
 677   return (FKey *)sqlite3HashFind(&pTab->pSchema->fkeyHash, pTab->zName);
 678 }
 679
 680 /*
 681 ** The second argument is a Trigger structure allocated by the
 682 ** fkActionTrigger() routine. This function deletes the Trigger structure
 683 ** and all of its sub-components.
 684 **
 685 ** The Trigger structure or any of its sub-components may be allocated from
 686 ** the lookaside buffer belonging to database handle dbMem.
 687 */
 688 static void fkTriggerDelete(sqlite3 *dbMem, Trigger *p){
 689   if( p ){
 690     TriggerStep *pStep = p->step_list;
 691     sqlite3ExprDelete(dbMem, pStep->pWhere);
 692     sqlite3ExprListDelete(dbMem, pStep->pExprList);
 693     sqlite3SelectDelete(dbMem, pStep->pSelect);
 694     sqlite3ExprDelete(dbMem, p->pWhen);
 695     sqlite3DbFree(dbMem, p);
 696   }
 697 }
 698
 699 /*
 700 ** Clear the apTrigger[] cache of CASCADE triggers for all foreign keys
 701 ** in a particular database.  This needs to happen when the schema
 702 ** changes.
 703 */
 704 void sqlite3FkClearTriggerCache(sqlite3 *db, int iDb){
 705   HashElem *k;
 706   Hash *pHash = &db->aDb[iDb].pSchema->tblHash;
 707   for(k=sqliteHashFirst(pHash); k; k=sqliteHashNext(k)){
 708     Table *pTab = sqliteHashData(k);
 709     FKey *pFKey;
 710     if( !IsOrdinaryTable(pTab) ) continue;
 711     for(pFKey=pTab->u.tab.pFKey; pFKey; pFKey=pFKey->pNextFrom){
 712       fkTriggerDelete(db, pFKey->apTrigger[0]); pFKey->apTrigger[0] = 0;
 713       fkTriggerDelete(db, pFKey->apTrigger[1]); pFKey->apTrigger[1] = 0;
 714     }
 715   }
 716 }
 717
 718 /*
 719 ** This function is called to generate code that runs when table pTab is
 720 ** being dropped from the database. The SrcList passed as the second argument
 721 ** to this function contains a single entry guaranteed to resolve to
 722 ** table pTab.
 723 **
 724 ** Normally, no code is required. However, if either
 725 **
 726 **   (a) The table is the parent table of a FK constraint, or
 727 **   (b) The table is the child table of a deferred FK constraint and it is
 728 **       determined at runtime that there are outstanding deferred FK
 729 **       constraint violations in the database,
 730 **
 731 ** then the equivalent of "DELETE FROM <tbl>" is executed before dropping
 732 ** the table from the database. Triggers are disabled while running this
 733 ** DELETE, but foreign key actions are not.
 734 */
 735 void sqlite3FkDropTable(Parse *pParse, SrcList *pName, Table *pTab){
 736   sqlite3 *db = pParse->db;
 737   if( (db->flags&SQLITE_ForeignKeys) && IsOrdinaryTable(pTab) ){
 738     int iSkip = 0;
 739     Vdbe *v = sqlite3GetVdbe(pParse);
 740
 741     assert( v );                  /* VDBE has already been allocated */
 742     assert( IsOrdinaryTable(pTab) );
 743     if( sqlite3FkReferences(pTab)==0 ){
 744       /* Search for a deferred foreign key constraint for which this table
 745       ** is the child table. If one cannot be found, return without
 746       ** generating any VDBE code. If one can be found, then jump over
 747       ** the entire DELETE if there are no outstanding deferred constraints
 748       ** when this statement is run.  */
 749       FKey *p;
 750       for(p=pTab->u.tab.pFKey; p; p=p->pNextFrom){
 751         if( p->isDeferred || (db->flags & SQLITE_DeferFKs) ) break;
 752       }
 753       if( !p ) return;
 754       iSkip = sqlite3VdbeMakeLabel(pParse);
 755       sqlite3VdbeAddOp2(v, OP_FkIfZero, 1, iSkip); VdbeCoverage(v);
 756     }
 757
 758     pParse->disableTriggers = 1;
 759     sqlite3DeleteFrom(pParse, sqlite3SrcListDup(db, pName, 0), 0, 0, 0);
 760     pParse->disableTriggers = 0;
 761
 762     /* If the DELETE has generated immediate foreign key constraint
 763     ** violations, halt the VDBE and return an error at this point, before
 764     ** any modifications to the schema are made. This is because statement
 765     ** transactions are not able to rollback schema changes.
 766     **
 767     ** If the SQLITE_DeferFKs flag is set, then this is not required, as
 768     ** the statement transaction will not be rolled back even if FK
 769     ** constraints are violated.
 770     */
 771     if( (db->flags & SQLITE_DeferFKs)==0 ){
 772       sqlite3VdbeVerifyAbortable(v, OE_Abort);
 773       sqlite3VdbeAddOp2(v, OP_FkIfZero, 0, sqlite3VdbeCurrentAddr(v)+2);
 774       VdbeCoverage(v);
 775       sqlite3HaltConstraint(pParse, SQLITE_CONSTRAINT_FOREIGNKEY,
 776           OE_Abort, 0, P4_STATIC, P5_ConstraintFK);
 777     }
 778
 779     if( iSkip ){
 780       sqlite3VdbeResolveLabel(v, iSkip);
 781     }
 782   }
 783 }
 784
 785
 786 /*
 787 ** The second argument points to an FKey object representing a foreign key
 788 ** for which pTab is the child table. An UPDATE statement against pTab
 789 ** is currently being processed. For each column of the table that is
 790 ** actually updated, the corresponding element in the aChange[] array
 791 ** is zero or greater (if a column is unmodified the corresponding element
 792 ** is set to -1). If the rowid column is modified by the UPDATE statement
 793 ** the bChngRowid argument is non-zero.
 794 **
 795 ** This function returns true if any of the columns that are part of the
 796 ** child key for FK constraint *p are modified.
 797 */
 798 static int fkChildIsModified(
 799   Table *pTab,                    /* Table being updated */
 800   FKey *p,                        /* Foreign key for which pTab is the child */
 801   int *aChange,                   /* Array indicating modified columns */
 802   int bChngRowid                  /* True if rowid is modified by this update */
 803 ){
 804   int i;
 805   for(i=0; i<p->nCol; i++){
 806     int iChildKey = p->aCol[i].iFrom;
 807     if( aChange[iChildKey]>=0 ) return 1;
 808     if( iChildKey==pTab->iPKey && bChngRowid ) return 1;
 809   }
 810   return 0;
 811 }
 812
 813 /*
 814 ** The second argument points to an FKey object representing a foreign key
 815 ** for which pTab is the parent table. An UPDATE statement against pTab
 816 ** is currently being processed. For each column of the table that is
 817 ** actually updated, the corresponding element in the aChange[] array
 818 ** is zero or greater (if a column is unmodified the corresponding element
 819 ** is set to -1). If the rowid column is modified by the UPDATE statement
 820 ** the bChngRowid argument is non-zero.
 821 **
 822 ** This function returns true if any of the columns that are part of the
 823 ** parent key for FK constraint *p are modified.
 824 */
 825 static int fkParentIsModified(
 826   Table *pTab,
 827   FKey *p,
 828   int *aChange,
 829   int bChngRowid
 830 ){
 831   int i;
 832   for(i=0; i<p->nCol; i++){
 833     char *zKey = p->aCol[i].zCol;
 834     int iKey;
 835     for(iKey=0; iKey<pTab->nCol; iKey++){
 836       if( aChange[iKey]>=0 || (iKey==pTab->iPKey && bChngRowid) ){
 837         Column *pCol = &pTab->aCol[iKey];
 838         if( zKey ){
 839           if( 0==sqlite3StrICmp(pCol->zCnName, zKey) ) return 1;
 840         }else if( pCol->colFlags & COLFLAG_PRIMKEY ){
 841           return 1;
 842         }
 843       }
 844     }
 845   }
 846   return 0;
 847 }
 848
 849 /*
 850 ** Return true if the parser passed as the first argument is being
 851 ** used to code a trigger that is really a "SET NULL" action belonging
 852 ** to trigger pFKey.
 853 */
 854 static int isSetNullAction(Parse *pParse, FKey *pFKey){
 855   Parse *pTop = sqlite3ParseToplevel(pParse);
 856   if( pTop->pTriggerPrg ){
 857     Trigger *p = pTop->pTriggerPrg->pTrigger;
 858     if( (p==pFKey->apTrigger[0] && pFKey->aAction[0]==OE_SetNull)
 859      || (p==pFKey->apTrigger[1] && pFKey->aAction[1]==OE_SetNull)
 860     ){
 861       assert( (pTop->db->flags & SQLITE_FkNoAction)==0 );
 862       return 1;
 863     }
 864   }
 865   return 0;
 866 }
 867
 868 /*
 869 ** This function is called when inserting, deleting or updating a row of
 870 ** table pTab to generate VDBE code to perform foreign key constraint
 871 ** processing for the operation.
 872 **
 873 ** For a DELETE operation, parameter regOld is passed the index of the
 874 ** first register in an array of (pTab->nCol+1) registers containing the
 875 ** rowid of the row being deleted, followed by each of the column values
 876 ** of the row being deleted, from left to right. Parameter regNew is passed
 877 ** zero in this case.
 878 **
 879 ** For an INSERT operation, regOld is passed zero and regNew is passed the
 880 ** first register of an array of (pTab->nCol+1) registers containing the new
 881 ** row data.
 882 **
 883 ** For an UPDATE operation, this function is called twice. Once before
 884 ** the original record is deleted from the table using the calling convention
 885 ** described for DELETE. Then again after the original record is deleted
 886 ** but before the new record is inserted using the INSERT convention.
 887 */
 888 void sqlite3FkCheck(
 889   Parse *pParse,                  /* Parse context */
 890   Table *pTab,                    /* Row is being deleted from this table */
 891   int regOld,                     /* Previous row data is stored here */
 892   int regNew,                     /* New row data is stored here */
 893   int *aChange,                   /* Array indicating UPDATEd columns (or 0) */
 894   int bChngRowid                  /* True if rowid is UPDATEd */
 895 ){
 896   sqlite3 *db = pParse->db;       /* Database handle */
 897   FKey *pFKey;                    /* Used to iterate through FKs */
 898   int iDb;                        /* Index of database containing pTab */
 899   const char *zDb;                /* Name of database containing pTab */
 900   int isIgnoreErrors = pParse->disableTriggers;
 901
 902   /* Exactly one of regOld and regNew should be non-zero. */
 903   assert( (regOld==0)!=(regNew==0) );
 904
 905   /* If foreign-keys are disabled, this function is a no-op. */
 906   if( (db->flags&SQLITE_ForeignKeys)==0 ) return;
 907   if( !IsOrdinaryTable(pTab) ) return;
 908
 909   iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
 910   zDb = db->aDb[iDb].zDbSName;
 911
 912   /* Loop through all the foreign key constraints for which pTab is the
 913   ** child table (the table that the foreign key definition is part of).  */
 914   for(pFKey=pTab->u.tab.pFKey; pFKey; pFKey=pFKey->pNextFrom){
 915     Table *pTo;                   /* Parent table of foreign key pFKey */
 916     Index *pIdx = 0;              /* Index on key columns in pTo */
 917     int *aiFree = 0;
 918     int *aiCol;
 919     int iCol;
 920     int i;
 921     int bIgnore = 0;
 922
 923     if( aChange
 924      && sqlite3_stricmp(pTab->zName, pFKey->zTo)!=0
 925      && fkChildIsModified(pTab, pFKey, aChange, bChngRowid)==0
 926     ){
 927       continue;
 928     }
 929
 930     /* Find the parent table of this foreign key. Also find a unique index
 931     ** on the parent key columns in the parent table. If either of these
 932     ** schema items cannot be located, set an error in pParse and return
 933     ** early.  */
 934     if( pParse->disableTriggers ){
 935       pTo = sqlite3FindTable(db, pFKey->zTo, zDb);
 936     }else{
 937       pTo = sqlite3LocateTable(pParse, 0, pFKey->zTo, zDb);
 938     }
 939     if( !pTo || sqlite3FkLocateIndex(pParse, pTo, pFKey, &pIdx, &aiFree) ){
 940       assert( isIgnoreErrors==0 || (regOld!=0 && regNew==0) );
 941       if( !isIgnoreErrors || db->mallocFailed ) return;
 942       if( pTo==0 ){
 943         /* If isIgnoreErrors is true, then a table is being dropped. In this
 944         ** case SQLite runs a "DELETE FROM xxx" on the table being dropped
 945         ** before actually dropping it in order to check FK constraints.
 946         ** If the parent table of an FK constraint on the current table is
 947         ** missing, behave as if it is empty. i.e. decrement the relevant
 948         ** FK counter for each row of the current table with non-NULL keys.
 949         */
 950         Vdbe *v = sqlite3GetVdbe(pParse);
 951         int iJump = sqlite3VdbeCurrentAddr(v) + pFKey->nCol + 1;
 952         for(i=0; i<pFKey->nCol; i++){
 953           int iFromCol, iReg;
 954           iFromCol = pFKey->aCol[i].iFrom;
 955           iReg = sqlite3TableColumnToStorage(pFKey->pFrom,iFromCol) + regOld+1;
 956           sqlite3VdbeAddOp2(v, OP_IsNull, iReg, iJump); VdbeCoverage(v);
 957         }
 958         sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, -1);
 959       }
 960       continue;
 961     }
 962     assert( pFKey->nCol==1 || (aiFree && pIdx) );
 963
 964     if( aiFree ){
 965       aiCol = aiFree;
 966     }else{
 967       iCol = pFKey->aCol[0].iFrom;
 968       aiCol = &iCol;
 969     }
 970     for(i=0; i<pFKey->nCol; i++){
 971       if( aiCol[i]==pTab->iPKey ){
 972         aiCol[i] = -1;
 973       }
 974       assert( pIdx==0 || pIdx->aiColumn[i]>=0 );
 975 #ifndef SQLITE_OMIT_AUTHORIZATION
 976       /* Request permission to read the parent key columns. If the
 977       ** authorization callback returns SQLITE_IGNORE, behave as if any
 978       ** values read from the parent table are NULL. */
 979       if( db->xAuth ){
 980         int rcauth;
 981         char *zCol = pTo->aCol[pIdx ? pIdx->aiColumn[i] : pTo->iPKey].zCnName;
 982         rcauth = sqlite3AuthReadCol(pParse, pTo->zName, zCol, iDb);
 983         bIgnore = (rcauth==SQLITE_IGNORE);
 984       }
 985 #endif
 986     }
 987
 988     /* Take a shared-cache advisory read-lock on the parent table. Allocate
 989     ** a cursor to use to search the unique index on the parent key columns
 990     ** in the parent table.  */
 991     sqlite3TableLock(pParse, iDb, pTo->tnum, 0, pTo->zName);
 992     pParse->nTab++;
 993
 994     if( regOld!=0 ){
 995       /* A row is being removed from the child table. Search for the parent.
 996       ** If the parent does not exist, removing the child row resolves an
 997       ** outstanding foreign key constraint violation. */
 998       fkLookupParent(pParse, iDb, pTo, pIdx, pFKey, aiCol, regOld, -1, bIgnore);
 999     }
1000     if( regNew!=0 && !isSetNullAction(pParse, pFKey) ){
1001       /* A row is being added to the child table. If a parent row cannot
1002       ** be found, adding the child row has violated the FK constraint.
1003       **
1004       ** If this operation is being performed as part of a trigger program
1005       ** that is actually a "SET NULL" action belonging to this very
1006       ** foreign key, then omit this scan altogether. As all child key
1007       ** values are guaranteed to be NULL, it is not possible for adding
1008       ** this row to cause an FK violation.  */
1009       fkLookupParent(pParse, iDb, pTo, pIdx, pFKey, aiCol, regNew, +1, bIgnore);
1010     }
1011
1012     sqlite3DbFree(db, aiFree);
1013   }
1014
1015   /* Loop through all the foreign key constraints that refer to this table.
1016   ** (the "child" constraints) */
1017   for(pFKey = sqlite3FkReferences(pTab); pFKey; pFKey=pFKey->pNextTo){
1018     Index *pIdx = 0;              /* Foreign key index for pFKey */
1019     SrcList *pSrc;
1020     int *aiCol = 0;
1021
1022     if( aChange && fkParentIsModified(pTab, pFKey, aChange, bChngRowid)==0 ){
1023       continue;
1024     }
1025
1026     if( !pFKey->isDeferred && !(db->flags & SQLITE_DeferFKs)
1027      && !pParse->pToplevel && !pParse->isMultiWrite
1028     ){
1029       assert( regOld==0 && regNew!=0 );
1030       /* Inserting a single row into a parent table cannot cause (or fix)
1031       ** an immediate foreign key violation. So do nothing in this case.  */
1032       continue;
1033     }
1034
1035     if( sqlite3FkLocateIndex(pParse, pTab, pFKey, &pIdx, &aiCol) ){
1036       if( !isIgnoreErrors || db->mallocFailed ) return;
1037       continue;
1038     }
1039     assert( aiCol || pFKey->nCol==1 );
1040
1041     /* Create a SrcList structure containing the child table.  We need the
1042     ** child table as a SrcList for sqlite3WhereBegin() */
1043     pSrc = sqlite3SrcListAppend(pParse, 0, 0, 0);
1044     if( pSrc ){
1045       SrcItem *pItem = pSrc->a;
1046       pItem->pTab = pFKey->pFrom;
1047       pItem->zName = pFKey->pFrom->zName;
1048       pItem->pTab->nTabRef++;
1049       pItem->iCursor = pParse->nTab++;
1050
1051       if( regNew!=0 ){
1052         fkScanChildren(pParse, pSrc, pTab, pIdx, pFKey, aiCol, regNew, -1);
1053       }
1054       if( regOld!=0 ){
1055         int eAction = pFKey->aAction[aChange!=0];
1056         if( (db->flags & SQLITE_FkNoAction) ) eAction = OE_None;
1057
1058         fkScanChildren(pParse, pSrc, pTab, pIdx, pFKey, aiCol, regOld, 1);
1059         /* If this is a deferred FK constraint, or a CASCADE or SET NULL
1060         ** action applies, then any foreign key violations caused by
1061         ** removing the parent key will be rectified by the action trigger.
1062         ** So do not set the "may-abort" flag in this case.
1063         **
1064         ** Note 1: If the FK is declared "ON UPDATE CASCADE", then the
1065         ** may-abort flag will eventually be set on this statement anyway
1066         ** (when this function is called as part of processing the UPDATE
1067         ** within the action trigger).
1068         **
1069         ** Note 2: At first glance it may seem like SQLite could simply omit
1070         ** all OP_FkCounter related scans when either CASCADE or SET NULL
1071         ** applies. The trouble starts if the CASCADE or SET NULL action
1072         ** trigger causes other triggers or action rules attached to the
1073         ** child table to fire. In these cases the fk constraint counters
1074         ** might be set incorrectly if any OP_FkCounter related scans are
1075         ** omitted.  */
1076         if( !pFKey->isDeferred && eAction!=OE_Cascade && eAction!=OE_SetNull ){
1077           sqlite3MayAbort(pParse);
1078         }
1079       }
1080       pItem->zName = 0;
1081       sqlite3SrcListDelete(db, pSrc);
1082     }
1083     sqlite3DbFree(db, aiCol);
1084   }
1085 }
1086
1087 #define COLUMN_MASK(x) (((x)>31) ? 0xffffffff : ((u32)1<<(x)))
1088
1089 /*
1090 ** This function is called before generating code to update or delete a
1091 ** row contained in table pTab.
1092 */
1093 u32 sqlite3FkOldmask(
1094   Parse *pParse,                  /* Parse context */
1095   Table *pTab                     /* Table being modified */
1096 ){
1097   u32 mask = 0;
1098   if( pParse->db->flags&SQLITE_ForeignKeys && IsOrdinaryTable(pTab) ){
1099     FKey *p;
1100     int i;
1101     for(p=pTab->u.tab.pFKey; p; p=p->pNextFrom){
1102       for(i=0; i<p->nCol; i++) mask |= COLUMN_MASK(p->aCol[i].iFrom);
1103     }
1104     for(p=sqlite3FkReferences(pTab); p; p=p->pNextTo){
1105       Index *pIdx = 0;
1106       sqlite3FkLocateIndex(pParse, pTab, p, &pIdx, 0);
1107       if( pIdx ){
1108         for(i=0; i<pIdx->nKeyCol; i++){
1109           assert( pIdx->aiColumn[i]>=0 );
1110           mask |= COLUMN_MASK(pIdx->aiColumn[i]);
1111         }
1112       }
1113     }
1114   }
1115   return mask;
1116 }
1117
1118
1119 /*
1120 ** This function is called before generating code to update or delete a
1121 ** row contained in table pTab. If the operation is a DELETE, then
1122 ** parameter aChange is passed a NULL value. For an UPDATE, aChange points
1123 ** to an array of size N, where N is the number of columns in table pTab.
1124 ** If the i'th column is not modified by the UPDATE, then the corresponding
1125 ** entry in the aChange[] array is set to -1. If the column is modified,
1126 ** the value is 0 or greater. Parameter chngRowid is set to true if the
1127 ** UPDATE statement modifies the rowid fields of the table.
1128 **
1129 ** If any foreign key processing will be required, this function returns
1130 ** non-zero. If there is no foreign key related processing, this function
1131 ** returns zero.
1132 **
1133 ** For an UPDATE, this function returns 2 if:
1134 **
1135 **   * There are any FKs for which pTab is the child and the parent table
1136 **     and any FK processing at all is required (even of a different FK), or
1137 **
1138 **   * the UPDATE modifies one or more parent keys for which the action is
1139 **     not "NO ACTION" (i.e. is CASCADE, SET DEFAULT or SET NULL).
1140 **
1141 ** Or, assuming some other foreign key processing is required, 1.
1142 */
1143 int sqlite3FkRequired(
1144   Parse *pParse,                  /* Parse context */
1145   Table *pTab,                    /* Table being modified */
1146   int *aChange,                   /* Non-NULL for UPDATE operations */
1147   int chngRowid                   /* True for UPDATE that affects rowid */
1148 ){
1149   int eRet = 1;                   /* Value to return if bHaveFK is true */
1150   int bHaveFK = 0;                /* If FK processing is required */
1151   if( pParse->db->flags&SQLITE_ForeignKeys && IsOrdinaryTable(pTab) ){
1152     if( !aChange ){
1153       /* A DELETE operation. Foreign key processing is required if the
1154       ** table in question is either the child or parent table for any
1155       ** foreign key constraint.  */
1156       bHaveFK = (sqlite3FkReferences(pTab) || pTab->u.tab.pFKey);
1157     }else{
1158       /* This is an UPDATE. Foreign key processing is only required if the
1159       ** operation modifies one or more child or parent key columns. */
1160       FKey *p;
1161
1162       /* Check if any child key columns are being modified. */
1163       for(p=pTab->u.tab.pFKey; p; p=p->pNextFrom){
1164         if( fkChildIsModified(pTab, p, aChange, chngRowid) ){
1165           if( 0==sqlite3_stricmp(pTab->zName, p->zTo) ) eRet = 2;
1166           bHaveFK = 1;
1167         }
1168       }
1169
1170       /* Check if any parent key columns are being modified. */
1171       for(p=sqlite3FkReferences(pTab); p; p=p->pNextTo){
1172         if( fkParentIsModified(pTab, p, aChange, chngRowid) ){
1173           if( (pParse->db->flags & SQLITE_FkNoAction)==0
1174            && p->aAction[1]!=OE_None
1175           ){
1176             return 2;
1177           }
1178           bHaveFK = 1;
1179         }
1180       }
1181     }
1182   }
1183   return bHaveFK ? eRet : 0;
1184 }
1185
1186 /*
1187 ** This function is called when an UPDATE or DELETE operation is being
1188 ** compiled on table pTab, which is the parent table of foreign-key pFKey.
1189 ** If the current operation is an UPDATE, then the pChanges parameter is
1190 ** passed a pointer to the list of columns being modified. If it is a
1191 ** DELETE, pChanges is passed a NULL pointer.
1192 **
1193 ** It returns a pointer to a Trigger structure containing a trigger
1194 ** equivalent to the ON UPDATE or ON DELETE action specified by pFKey.
1195 ** If the action is "NO ACTION" then a NULL pointer is returned (these actions
1196 ** require no special handling by the triggers sub-system, code for them is
1197 ** created by fkScanChildren()).
1198 **
1199 ** For example, if pFKey is the foreign key and pTab is table "p" in
1200 ** the following schema:
1201 **
1202 **   CREATE TABLE p(pk PRIMARY KEY);
1203 **   CREATE TABLE c(ck REFERENCES p ON DELETE CASCADE);
1204 **
1205 ** then the returned trigger structure is equivalent to:
1206 **
1207 **   CREATE TRIGGER ... DELETE ON p BEGIN
1208 **     DELETE FROM c WHERE ck = old.pk;
1209 **   END;
1210 **
1211 ** The returned pointer is cached as part of the foreign key object. It
1212 ** is eventually freed along with the rest of the foreign key object by
1213 ** sqlite3FkDelete().
1214 */
1215 static Trigger *fkActionTrigger(
1216   Parse *pParse,                  /* Parse context */
1217   Table *pTab,                    /* Table being updated or deleted from */
1218   FKey *pFKey,                    /* Foreign key to get action for */
1219   ExprList *pChanges              /* Change-list for UPDATE, NULL for DELETE */
1220 ){
1221   sqlite3 *db = pParse->db;       /* Database handle */
1222   int action;                     /* One of OE_None, OE_Cascade etc. */
1223   Trigger *pTrigger;              /* Trigger definition to return */
1224   int iAction = (pChanges!=0);    /* 1 for UPDATE, 0 for DELETE */
1225
1226   action = pFKey->aAction[iAction];
1227   if( (db->flags & SQLITE_FkNoAction) ) action = OE_None;
1228   if( action==OE_Restrict && (db->flags & SQLITE_DeferFKs) ){
1229     return 0;
1230   }
1231   pTrigger = pFKey->apTrigger[iAction];
1232
1233   if( action!=OE_None && !pTrigger ){
1234     char const *zFrom;            /* Name of child table */
1235     int nFrom;                    /* Length in bytes of zFrom */
1236     Index *pIdx = 0;              /* Parent key index for this FK */
1237     int *aiCol = 0;               /* child table cols -> parent key cols */
1238     TriggerStep *pStep = 0;        /* First (only) step of trigger program */
1239     Expr *pWhere = 0;             /* WHERE clause of trigger step */
1240     ExprList *pList = 0;          /* Changes list if ON UPDATE CASCADE */
1241     Select *pSelect = 0;          /* If RESTRICT, "SELECT RAISE(...)" */
1242     int i;                        /* Iterator variable */
1243     Expr *pWhen = 0;              /* WHEN clause for the trigger */
1244
1245     if( sqlite3FkLocateIndex(pParse, pTab, pFKey, &pIdx, &aiCol) ) return 0;
1246     assert( aiCol || pFKey->nCol==1 );
1247
1248     for(i=0; i<pFKey->nCol; i++){
1249       Token tOld = { "old", 3 };  /* Literal "old" token */
1250       Token tNew = { "new", 3 };  /* Literal "new" token */
1251       Token tFromCol;             /* Name of column in child table */
1252       Token tToCol;               /* Name of column in parent table */
1253       int iFromCol;               /* Idx of column in child table */
1254       Expr *pEq;                  /* tFromCol = OLD.tToCol */
1255
1256       iFromCol = aiCol ? aiCol[i] : pFKey->aCol[0].iFrom;
1257       assert( iFromCol>=0 );
1258       assert( pIdx!=0 || (pTab->iPKey>=0 && pTab->iPKey<pTab->nCol) );
1259       assert( pIdx==0 || pIdx->aiColumn[i]>=0 );
1260       sqlite3TokenInit(&tToCol,
1261                    pTab->aCol[pIdx ? pIdx->aiColumn[i] : pTab->iPKey].zCnName);
1262       sqlite3TokenInit(&tFromCol, pFKey->pFrom->aCol[iFromCol].zCnName);
1263
1264       /* Create the expression "OLD.zToCol = zFromCol". It is important
1265       ** that the "OLD.zToCol" term is on the LHS of the = operator, so
1266       ** that the affinity and collation sequence associated with the
1267       ** parent table are used for the comparison. */
1268       pEq = sqlite3PExpr(pParse, TK_EQ,
1269           sqlite3PExpr(pParse, TK_DOT,
1270             sqlite3ExprAlloc(db, TK_ID, &tOld, 0),
1271             sqlite3ExprAlloc(db, TK_ID, &tToCol, 0)),
1272           sqlite3ExprAlloc(db, TK_ID, &tFromCol, 0)
1273       );
1274       pWhere = sqlite3ExprAnd(pParse, pWhere, pEq);
1275
1276       /* For ON UPDATE, construct the next term of the WHEN clause.
1277       ** The final WHEN clause will be like this:
1278       **
1279       **    WHEN NOT(old.col1 IS new.col1 AND ... AND old.colN IS new.colN)
1280       */
1281       if( pChanges ){
1282         pEq = sqlite3PExpr(pParse, TK_IS,
1283             sqlite3PExpr(pParse, TK_DOT,
1284               sqlite3ExprAlloc(db, TK_ID, &tOld, 0),
1285               sqlite3ExprAlloc(db, TK_ID, &tToCol, 0)),
1286             sqlite3PExpr(pParse, TK_DOT,
1287               sqlite3ExprAlloc(db, TK_ID, &tNew, 0),
1288               sqlite3ExprAlloc(db, TK_ID, &tToCol, 0))
1289             );
1290         pWhen = sqlite3ExprAnd(pParse, pWhen, pEq);
1291       }
1292
1293       if( action!=OE_Restrict && (action!=OE_Cascade || pChanges) ){
1294         Expr *pNew;
1295         if( action==OE_Cascade ){
1296           pNew = sqlite3PExpr(pParse, TK_DOT,
1297             sqlite3ExprAlloc(db, TK_ID, &tNew, 0),
1298             sqlite3ExprAlloc(db, TK_ID, &tToCol, 0));
1299         }else if( action==OE_SetDflt ){
1300           Column *pCol = pFKey->pFrom->aCol + iFromCol;
1301           Expr *pDflt;
1302           if( pCol->colFlags & COLFLAG_GENERATED ){
1303             testcase( pCol->colFlags & COLFLAG_VIRTUAL );
1304             testcase( pCol->colFlags & COLFLAG_STORED );
1305             pDflt = 0;
1306           }else{
1307             pDflt = sqlite3ColumnExpr(pFKey->pFrom, pCol);
1308           }
1309           if( pDflt ){
1310             pNew = sqlite3ExprDup(db, pDflt, 0);
1311           }else{
1312             pNew = sqlite3ExprAlloc(db, TK_NULL, 0, 0);
1313           }
1314         }else{
1315           pNew = sqlite3ExprAlloc(db, TK_NULL, 0, 0);
1316         }
1317         pList = sqlite3ExprListAppend(pParse, pList, pNew);
1318         sqlite3ExprListSetName(pParse, pList, &tFromCol, 0);
1319       }
1320     }
1321     sqlite3DbFree(db, aiCol);
1322
1323     zFrom = pFKey->pFrom->zName;
1324     nFrom = sqlite3Strlen30(zFrom);
1325
1326     if( action==OE_Restrict ){
1327       int iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
1328       SrcList *pSrc;
1329       Expr *pRaise;
1330
1331       pRaise = sqlite3Expr(db, TK_RAISE, "FOREIGN KEY constraint failed");
1332       if( pRaise ){
1333         pRaise->affExpr = OE_Abort;
1334       }
1335       pSrc = sqlite3SrcListAppend(pParse, 0, 0, 0);
1336       if( pSrc ){
1337         assert( pSrc->nSrc==1 );
1338         pSrc->a[0].zName = sqlite3DbStrDup(db, zFrom);
1339         pSrc->a[0].zDatabase = sqlite3DbStrDup(db, db->aDb[iDb].zDbSName);
1340       }
1341       pSelect = sqlite3SelectNew(pParse,
1342           sqlite3ExprListAppend(pParse, 0, pRaise),
1343           pSrc,
1344           pWhere,
1345           0, 0, 0, 0, 0
1346       );
1347       pWhere = 0;
1348     }
1349
1350     /* Disable lookaside memory allocation */
1351     DisableLookaside;
1352
1353     pTrigger = (Trigger *)sqlite3DbMallocZero(db,
1354         sizeof(Trigger) +         /* struct Trigger */
1355         sizeof(TriggerStep) +     /* Single step in trigger program */
1356         nFrom + 1                 /* Space for pStep->zTarget */
1357     );
1358     if( pTrigger ){
1359       pStep = pTrigger->step_list = (TriggerStep *)&pTrigger[1];
1360       pStep->zTarget = (char *)&pStep[1];
1361       memcpy((char *)pStep->zTarget, zFrom, nFrom);
1362
1363       pStep->pWhere = sqlite3ExprDup(db, pWhere, EXPRDUP_REDUCE);
1364       pStep->pExprList = sqlite3ExprListDup(db, pList, EXPRDUP_REDUCE);
1365       pStep->pSelect = sqlite3SelectDup(db, pSelect, EXPRDUP_REDUCE);
1366       if( pWhen ){
1367         pWhen = sqlite3PExpr(pParse, TK_NOT, pWhen, 0);
1368         pTrigger->pWhen = sqlite3ExprDup(db, pWhen, EXPRDUP_REDUCE);
1369       }
1370     }
1371
1372     /* Re-enable the lookaside buffer, if it was disabled earlier. */
1373     EnableLookaside;
1374
1375     sqlite3ExprDelete(db, pWhere);
1376     sqlite3ExprDelete(db, pWhen);
1377     sqlite3ExprListDelete(db, pList);
1378     sqlite3SelectDelete(db, pSelect);
1379     if( db->mallocFailed==1 ){
1380       fkTriggerDelete(db, pTrigger);
1381       return 0;
1382     }
1383     assert( pStep!=0 );
1384     assert( pTrigger!=0 );
1385
1386     switch( action ){
1387       case OE_Restrict:
1388         pStep->op = TK_SELECT;
1389         break;
1390       case OE_Cascade:
1391         if( !pChanges ){
1392           pStep->op = TK_DELETE;
1393           break;
1394         }
1395         /* no break */ deliberate_fall_through
1396       default:
1397         pStep->op = TK_UPDATE;
1398     }
1399     pStep->pTrig = pTrigger;
1400     pTrigger->pSchema = pTab->pSchema;
1401     pTrigger->pTabSchema = pTab->pSchema;
1402     pFKey->apTrigger[iAction] = pTrigger;
1403     pTrigger->op = (pChanges ? TK_UPDATE : TK_DELETE);
1404   }
1405
1406   return pTrigger;
1407 }
1408
1409 /*
1410 ** This function is called when deleting or updating a row to implement
1411 ** any required CASCADE, SET NULL or SET DEFAULT actions.
1412 */
1413 void sqlite3FkActions(
1414   Parse *pParse,                  /* Parse context */
1415   Table *pTab,                    /* Table being updated or deleted from */
1416   ExprList *pChanges,             /* Change-list for UPDATE, NULL for DELETE */
1417   int regOld,                     /* Address of array containing old row */
1418   int *aChange,                   /* Array indicating UPDATEd columns (or 0) */
1419   int bChngRowid                  /* True if rowid is UPDATEd */
1420 ){
1421   /* If foreign-key support is enabled, iterate through all FKs that
1422   ** refer to table pTab. If there is an action associated with the FK
1423   ** for this operation (either update or delete), invoke the associated
1424   ** trigger sub-program.  */
1425   if( pParse->db->flags&SQLITE_ForeignKeys ){
1426     FKey *pFKey;                  /* Iterator variable */
1427     for(pFKey = sqlite3FkReferences(pTab); pFKey; pFKey=pFKey->pNextTo){
1428       if( aChange==0 || fkParentIsModified(pTab, pFKey, aChange, bChngRowid) ){
1429         Trigger *pAct = fkActionTrigger(pParse, pTab, pFKey, pChanges);
1430         if( pAct ){
1431           sqlite3CodeRowTriggerDirect(pParse, pAct, pTab, regOld, OE_Abort, 0);
1432         }
1433       }
1434     }
1435   }
1436 }
1437
1438 #endif /* ifndef SQLITE_OMIT_TRIGGER */
1439
1440 /*
1441 ** Free all memory associated with foreign key definitions attached to
1442 ** table pTab. Remove the deleted foreign keys from the Schema.fkeyHash
1443 ** hash table.
1444 */
1445 void sqlite3FkDelete(sqlite3 *db, Table *pTab){
1446   FKey *pFKey;                    /* Iterator variable */
1447   FKey *pNext;                    /* Copy of pFKey->pNextFrom */
1448
1449   assert( IsOrdinaryTable(pTab) );
1450   assert( db!=0 );
1451   for(pFKey=pTab->u.tab.pFKey; pFKey; pFKey=pNext){
1452     assert( db==0 || sqlite3SchemaMutexHeld(db, 0, pTab->pSchema) );
1453
1454     /* Remove the FK from the fkeyHash hash table. */
1455     if( db->pnBytesFreed==0 ){
1456       if( pFKey->pPrevTo ){
1457         pFKey->pPrevTo->pNextTo = pFKey->pNextTo;
1458       }else{
1459         const char *z = (pFKey->pNextTo ? pFKey->pNextTo->zTo : pFKey->zTo);
1460         sqlite3HashInsert(&pTab->pSchema->fkeyHash, z, pFKey->pNextTo);
1461       }
1462       if( pFKey->pNextTo ){
1463         pFKey->pNextTo->pPrevTo = pFKey->pPrevTo;
1464       }
1465     }
1466
1467     /* EV: R-30323-21917 Each foreign key constraint in SQLite is
1468     ** classified as either immediate or deferred.
1469     */
1470     assert( pFKey->isDeferred==0 || pFKey->isDeferred==1 );
1471
1472     /* Delete any triggers created to implement actions for this FK. */
1473 #ifndef SQLITE_OMIT_TRIGGER
1474     fkTriggerDelete(db, pFKey->apTrigger[0]);
1475     fkTriggerDelete(db, pFKey->apTrigger[1]);
1476 #endif
1477
1478     pNext = pFKey->pNextFrom;
1479     sqlite3DbFree(db, pFKey);
1480   }
1481 }
1482 #endif /* ifndef SQLITE_OMIT_FOREIGN_KEY */