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