000001  /*
000002  **
000003  ** The author disclaims copyright to this source code.  In place of
000004  ** a legal notice, here is a blessing:
000005  **
000006  **    May you do good and not evil.
000007  **    May you find forgiveness for yourself and forgive others.
000008  **    May you share freely, never taking more than you give.
000009  **
000010  *************************************************************************
000011  ** This file contains code used by the compiler to add foreign key
000012  ** support to compiled SQL statements.
000013  */
000014  #include "sqliteInt.h"
000015  
000016  #ifndef SQLITE_OMIT_FOREIGN_KEY
000017  #ifndef SQLITE_OMIT_TRIGGER
000018  
000019  /*
000020  ** Deferred and Immediate FKs
000021  ** --------------------------
000022  **
000023  ** Foreign keys in SQLite come in two flavours: deferred and immediate.
000024  ** If an immediate foreign key constraint is violated,
000025  ** SQLITE_CONSTRAINT_FOREIGNKEY is returned and the current
000026  ** statement transaction rolled back. If a 
000027  ** deferred foreign key constraint is violated, no action is taken 
000028  ** immediately. However if the application attempts to commit the 
000029  ** transaction before fixing the constraint violation, the attempt fails.
000030  **
000031  ** Deferred constraints are implemented using a simple counter associated
000032  ** with the database handle. The counter is set to zero each time a 
000033  ** database transaction is opened. Each time a statement is executed 
000034  ** that causes a foreign key violation, the counter is incremented. Each
000035  ** time a statement is executed that removes an existing violation from
000036  ** the database, the counter is decremented. When the transaction is
000037  ** committed, the commit fails if the current value of the counter is
000038  ** greater than zero. This scheme has two big drawbacks:
000039  **
000040  **   * When a commit fails due to a deferred foreign key constraint, 
000041  **     there is no way to tell which foreign constraint is not satisfied,
000042  **     or which row it is not satisfied for.
000043  **
000044  **   * If the database contains foreign key violations when the 
000045  **     transaction is opened, this may cause the mechanism to malfunction.
000046  **
000047  ** Despite these problems, this approach is adopted as it seems simpler
000048  ** than the alternatives.
000049  **
000050  ** INSERT operations:
000051  **
000052  **   I.1) For each FK for which the table is the child table, search
000053  **        the parent table for a match. If none is found increment the
000054  **        constraint counter.
000055  **
000056  **   I.2) For each FK for which the table is the parent table, 
000057  **        search the child table for rows that correspond to the new
000058  **        row in the parent table. Decrement the counter for each row
000059  **        found (as the constraint is now satisfied).
000060  **
000061  ** DELETE operations:
000062  **
000063  **   D.1) For each FK for which the table is the child table, 
000064  **        search the parent table for a row that corresponds to the 
000065  **        deleted row in the child table. If such a row is not found, 
000066  **        decrement the counter.
000067  **
000068  **   D.2) For each FK for which the table is the parent table, search 
000069  **        the child table for rows that correspond to the deleted row 
000070  **        in the parent table. For each found increment the counter.
000071  **
000072  ** UPDATE operations:
000073  **
000074  **   An UPDATE command requires that all 4 steps above are taken, but only
000075  **   for FK constraints for which the affected columns are actually 
000076  **   modified (values must be compared at runtime).
000077  **
000078  ** Note that I.1 and D.1 are very similar operations, as are I.2 and D.2.
000079  ** This simplifies the implementation a bit.
000080  **
000081  ** For the purposes of immediate FK constraints, the OR REPLACE conflict
000082  ** resolution is considered to delete rows before the new row is inserted.
000083  ** If a delete caused by OR REPLACE violates an FK constraint, an exception
000084  ** is thrown, even if the FK constraint would be satisfied after the new 
000085  ** row is inserted.
000086  **
000087  ** Immediate constraints are usually handled similarly. The only difference 
000088  ** is that the counter used is stored as part of each individual statement
000089  ** object (struct Vdbe). If, after the statement has run, its immediate
000090  ** constraint counter is greater than zero,
000091  ** it returns SQLITE_CONSTRAINT_FOREIGNKEY
000092  ** and the statement transaction is rolled back. An exception is an INSERT
000093  ** statement that inserts a single row only (no triggers). In this case,
000094  ** instead of using a counter, an exception is thrown immediately if the
000095  ** INSERT violates a foreign key constraint. This is necessary as such
000096  ** an INSERT does not open a statement transaction.
000097  **
000098  ** TODO: How should dropping a table be handled? How should renaming a 
000099  ** table be handled?
000100  **
000101  **
000102  ** Query API Notes
000103  ** ---------------
000104  **
000105  ** Before coding an UPDATE or DELETE row operation, the code-generator
000106  ** for those two operations needs to know whether or not the operation
000107  ** requires any FK processing and, if so, which columns of the original
000108  ** row are required by the FK processing VDBE code (i.e. if FKs were
000109  ** implemented using triggers, which of the old.* columns would be 
000110  ** accessed). No information is required by the code-generator before
000111  ** coding an INSERT operation. The functions used by the UPDATE/DELETE
000112  ** generation code to query for this information are:
000113  **
000114  **   sqlite3FkRequired() - Test to see if FK processing is required.
000115  **   sqlite3FkOldmask()  - Query for the set of required old.* columns.
000116  **
000117  **
000118  ** Externally accessible module functions
000119  ** --------------------------------------
000120  **
000121  **   sqlite3FkCheck()    - Check for foreign key violations.
000122  **   sqlite3FkActions()  - Code triggers for ON UPDATE/ON DELETE actions.
000123  **   sqlite3FkDelete()   - Delete an FKey structure.
000124  */
000125  
000126  /*
000127  ** VDBE Calling Convention
000128  ** -----------------------
000129  **
000130  ** Example:
000131  **
000132  **   For the following INSERT statement:
000133  **
000134  **     CREATE TABLE t1(a, b INTEGER PRIMARY KEY, c);
000135  **     INSERT INTO t1 VALUES(1, 2, 3.1);
000136  **
000137  **   Register (x):        2    (type integer)
000138  **   Register (x+1):      1    (type integer)
000139  **   Register (x+2):      NULL (type NULL)
000140  **   Register (x+3):      3.1  (type real)
000141  */
000142  
000143  /*
000144  ** A foreign key constraint requires that the key columns in the parent
000145  ** table are collectively subject to a UNIQUE or PRIMARY KEY constraint.
000146  ** Given that pParent is the parent table for foreign key constraint pFKey, 
000147  ** search the schema for a unique index on the parent key columns. 
000148  **
000149  ** If successful, zero is returned. If the parent key is an INTEGER PRIMARY 
000150  ** KEY column, then output variable *ppIdx is set to NULL. Otherwise, *ppIdx 
000151  ** is set to point to the unique index. 
000152  ** 
000153  ** If the parent key consists of a single column (the foreign key constraint
000154  ** is not a composite foreign key), output variable *paiCol is set to NULL.
000155  ** Otherwise, it is set to point to an allocated array of size N, where
000156  ** N is the number of columns in the parent key. The first element of the
000157  ** array is the index of the child table column that is mapped by the FK
000158  ** constraint to the parent table column stored in the left-most column
000159  ** of index *ppIdx. The second element of the array is the index of the
000160  ** child table column that corresponds to the second left-most column of
000161  ** *ppIdx, and so on.
000162  **
000163  ** If the required index cannot be found, either because:
000164  **
000165  **   1) The named parent key columns do not exist, or
000166  **
000167  **   2) The named parent key columns do exist, but are not subject to a
000168  **      UNIQUE or PRIMARY KEY constraint, or
000169  **
000170  **   3) No parent key columns were provided explicitly as part of the
000171  **      foreign key definition, and the parent table does not have a
000172  **      PRIMARY KEY, or
000173  **
000174  **   4) No parent key columns were provided explicitly as part of the
000175  **      foreign key definition, and the PRIMARY KEY of the parent table 
000176  **      consists of a different number of columns to the child key in 
000177  **      the child table.
000178  **
000179  ** then non-zero is returned, and a "foreign key mismatch" error loaded
000180  ** into pParse. If an OOM error occurs, non-zero is returned and the
000181  ** pParse->db->mallocFailed flag is set.
000182  */
000183  int sqlite3FkLocateIndex(
000184    Parse *pParse,                  /* Parse context to store any error in */
000185    Table *pParent,                 /* Parent table of FK constraint pFKey */
000186    FKey *pFKey,                    /* Foreign key to find index for */
000187    Index **ppIdx,                  /* OUT: Unique index on parent table */
000188    int **paiCol                    /* OUT: Map of index columns in pFKey */
000189  ){
000190    Index *pIdx = 0;                    /* Value to return via *ppIdx */
000191    int *aiCol = 0;                     /* Value to return via *paiCol */
000192    int nCol = pFKey->nCol;             /* Number of columns in parent key */
000193    char *zKey = pFKey->aCol[0].zCol;   /* Name of left-most parent key column */
000194  
000195    /* The caller is responsible for zeroing output parameters. */
000196    assert( ppIdx && *ppIdx==0 );
000197    assert( !paiCol || *paiCol==0 );
000198    assert( pParse );
000199  
000200    /* If this is a non-composite (single column) foreign key, check if it 
000201    ** maps to the INTEGER PRIMARY KEY of table pParent. If so, leave *ppIdx 
000202    ** and *paiCol set to zero and return early. 
000203    **
000204    ** Otherwise, for a composite foreign key (more than one column), allocate
000205    ** space for the aiCol array (returned via output parameter *paiCol).
000206    ** Non-composite foreign keys do not require the aiCol array.
000207    */
000208    if( nCol==1 ){
000209      /* The FK maps to the IPK if any of the following are true:
000210      **
000211      **   1) There is an INTEGER PRIMARY KEY column and the FK is implicitly 
000212      **      mapped to the primary key of table pParent, or
000213      **   2) The FK is explicitly mapped to a column declared as INTEGER
000214      **      PRIMARY KEY.
000215      */
000216      if( pParent->iPKey>=0 ){
000217        if( !zKey ) return 0;
000218        if( !sqlite3StrICmp(pParent->aCol[pParent->iPKey].zName, zKey) ) return 0;
000219      }
000220    }else if( paiCol ){
000221      assert( nCol>1 );
000222      aiCol = (int *)sqlite3DbMallocRawNN(pParse->db, nCol*sizeof(int));
000223      if( !aiCol ) return 1;
000224      *paiCol = aiCol;
000225    }
000226  
000227    for(pIdx=pParent->pIndex; pIdx; pIdx=pIdx->pNext){
000228      if( pIdx->nKeyCol==nCol && IsUniqueIndex(pIdx) && pIdx->pPartIdxWhere==0 ){ 
000229        /* pIdx is a UNIQUE index (or a PRIMARY KEY) and has the right number
000230        ** of columns. If each indexed column corresponds to a foreign key
000231        ** column of pFKey, then this index is a winner.  */
000232  
000233        if( zKey==0 ){
000234          /* If zKey is NULL, then this foreign key is implicitly mapped to 
000235          ** the PRIMARY KEY of table pParent. The PRIMARY KEY index may be 
000236          ** identified by the test.  */
000237          if( IsPrimaryKeyIndex(pIdx) ){
000238            if( aiCol ){
000239              int i;
000240              for(i=0; i<nCol; i++) aiCol[i] = pFKey->aCol[i].iFrom;
000241            }
000242            break;
000243          }
000244        }else{
000245          /* If zKey is non-NULL, then this foreign key was declared to
000246          ** map to an explicit list of columns in table pParent. Check if this
000247          ** index matches those columns. Also, check that the index uses
000248          ** the default collation sequences for each column. */
000249          int i, j;
000250          for(i=0; i<nCol; i++){
000251            i16 iCol = pIdx->aiColumn[i];     /* Index of column in parent tbl */
000252            const char *zDfltColl;            /* Def. collation for column */
000253            char *zIdxCol;                    /* Name of indexed column */
000254  
000255            if( iCol<0 ) break; /* No foreign keys against expression indexes */
000256  
000257            /* If the index uses a collation sequence that is different from
000258            ** the default collation sequence for the column, this index is
000259            ** unusable. Bail out early in this case.  */
000260            zDfltColl = pParent->aCol[iCol].zColl;
000261            if( !zDfltColl ) zDfltColl = sqlite3StrBINARY;
000262            if( sqlite3StrICmp(pIdx->azColl[i], zDfltColl) ) break;
000263  
000264            zIdxCol = pParent->aCol[iCol].zName;
000265            for(j=0; j<nCol; j++){
000266              if( sqlite3StrICmp(pFKey->aCol[j].zCol, zIdxCol)==0 ){
000267                if( aiCol ) aiCol[i] = pFKey->aCol[j].iFrom;
000268                break;
000269              }
000270            }
000271            if( j==nCol ) break;
000272          }
000273          if( i==nCol ) break;      /* pIdx is usable */
000274        }
000275      }
000276    }
000277  
000278    if( !pIdx ){
000279      if( !pParse->disableTriggers ){
000280        sqlite3ErrorMsg(pParse,
000281             "foreign key mismatch - \"%w\" referencing \"%w\"",
000282             pFKey->pFrom->zName, pFKey->zTo);
000283      }
000284      sqlite3DbFree(pParse->db, aiCol);
000285      return 1;
000286    }
000287  
000288    *ppIdx = pIdx;
000289    return 0;
000290  }
000291  
000292  /*
000293  ** This function is called when a row is inserted into or deleted from the 
000294  ** child table of foreign key constraint pFKey. If an SQL UPDATE is executed 
000295  ** on the child table of pFKey, this function is invoked twice for each row
000296  ** affected - once to "delete" the old row, and then again to "insert" the
000297  ** new row.
000298  **
000299  ** Each time it is called, this function generates VDBE code to locate the
000300  ** row in the parent table that corresponds to the row being inserted into 
000301  ** or deleted from the child table. If the parent row can be found, no 
000302  ** special action is taken. Otherwise, if the parent row can *not* be
000303  ** found in the parent table:
000304  **
000305  **   Operation | FK type   | Action taken
000306  **   --------------------------------------------------------------------------
000307  **   INSERT      immediate   Increment the "immediate constraint counter".
000308  **
000309  **   DELETE      immediate   Decrement the "immediate constraint counter".
000310  **
000311  **   INSERT      deferred    Increment the "deferred constraint counter".
000312  **
000313  **   DELETE      deferred    Decrement the "deferred constraint counter".
000314  **
000315  ** These operations are identified in the comment at the top of this file 
000316  ** (fkey.c) as "I.1" and "D.1".
000317  */
000318  static void fkLookupParent(
000319    Parse *pParse,        /* Parse context */
000320    int iDb,              /* Index of database housing pTab */
000321    Table *pTab,          /* Parent table of FK pFKey */
000322    Index *pIdx,          /* Unique index on parent key columns in pTab */
000323    FKey *pFKey,          /* Foreign key constraint */
000324    int *aiCol,           /* Map from parent key columns to child table columns */
000325    int regData,          /* Address of array containing child table row */
000326    int nIncr,            /* Increment constraint counter by this */
000327    int isIgnore          /* If true, pretend pTab contains all NULL values */
000328  ){
000329    int i;                                    /* Iterator variable */
000330    Vdbe *v = sqlite3GetVdbe(pParse);         /* Vdbe to add code to */
000331    int iCur = pParse->nTab - 1;              /* Cursor number to use */
000332    int iOk = sqlite3VdbeMakeLabel(v);        /* jump here if parent key found */
000333  
000334    /* If nIncr is less than zero, then check at runtime if there are any
000335    ** outstanding constraints to resolve. If there are not, there is no need
000336    ** to check if deleting this row resolves any outstanding violations.
000337    **
000338    ** Check if any of the key columns in the child table row are NULL. If 
000339    ** any are, then the constraint is considered satisfied. No need to 
000340    ** search for a matching row in the parent table.  */
000341    if( nIncr<0 ){
000342      sqlite3VdbeAddOp2(v, OP_FkIfZero, pFKey->isDeferred, iOk);
000343      VdbeCoverage(v);
000344    }
000345    for(i=0; i<pFKey->nCol; i++){
000346      int iReg = aiCol[i] + regData + 1;
000347      sqlite3VdbeAddOp2(v, OP_IsNull, iReg, iOk); VdbeCoverage(v);
000348    }
000349  
000350    if( isIgnore==0 ){
000351      if( pIdx==0 ){
000352        /* If pIdx is NULL, then the parent key is the INTEGER PRIMARY KEY
000353        ** column of the parent table (table pTab).  */
000354        int iMustBeInt;               /* Address of MustBeInt instruction */
000355        int regTemp = sqlite3GetTempReg(pParse);
000356    
000357        /* Invoke MustBeInt to coerce the child key value to an integer (i.e. 
000358        ** apply the affinity of the parent key). If this fails, then there
000359        ** is no matching parent key. Before using MustBeInt, make a copy of
000360        ** the value. Otherwise, the value inserted into the child key column
000361        ** will have INTEGER affinity applied to it, which may not be correct.  */
000362        sqlite3VdbeAddOp2(v, OP_SCopy, aiCol[0]+1+regData, regTemp);
000363        iMustBeInt = sqlite3VdbeAddOp2(v, OP_MustBeInt, regTemp, 0);
000364        VdbeCoverage(v);
000365    
000366        /* If the parent table is the same as the child table, and we are about
000367        ** to increment the constraint-counter (i.e. this is an INSERT operation),
000368        ** then check if the row being inserted matches itself. If so, do not
000369        ** increment the constraint-counter.  */
000370        if( pTab==pFKey->pFrom && nIncr==1 ){
000371          sqlite3VdbeAddOp3(v, OP_Eq, regData, iOk, regTemp); VdbeCoverage(v);
000372          sqlite3VdbeChangeP5(v, SQLITE_NOTNULL);
000373        }
000374    
000375        sqlite3OpenTable(pParse, iCur, iDb, pTab, OP_OpenRead);
000376        sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, regTemp); VdbeCoverage(v);
000377        sqlite3VdbeGoto(v, iOk);
000378        sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
000379        sqlite3VdbeJumpHere(v, iMustBeInt);
000380        sqlite3ReleaseTempReg(pParse, regTemp);
000381      }else{
000382        int nCol = pFKey->nCol;
000383        int regTemp = sqlite3GetTempRange(pParse, nCol);
000384        int regRec = sqlite3GetTempReg(pParse);
000385    
000386        sqlite3VdbeAddOp3(v, OP_OpenRead, iCur, pIdx->tnum, iDb);
000387        sqlite3VdbeSetP4KeyInfo(pParse, pIdx);
000388        for(i=0; i<nCol; i++){
000389          sqlite3VdbeAddOp2(v, OP_Copy, aiCol[i]+1+regData, regTemp+i);
000390        }
000391    
000392        /* If the parent table is the same as the child table, and we are about
000393        ** to increment the constraint-counter (i.e. this is an INSERT operation),
000394        ** then check if the row being inserted matches itself. If so, do not
000395        ** increment the constraint-counter. 
000396        **
000397        ** If any of the parent-key values are NULL, then the row cannot match 
000398        ** itself. So set JUMPIFNULL to make sure we do the OP_Found if any
000399        ** of the parent-key values are NULL (at this point it is known that
000400        ** none of the child key values are).
000401        */
000402        if( pTab==pFKey->pFrom && nIncr==1 ){
000403          int iJump = sqlite3VdbeCurrentAddr(v) + nCol + 1;
000404          for(i=0; i<nCol; i++){
000405            int iChild = aiCol[i]+1+regData;
000406            int iParent = pIdx->aiColumn[i]+1+regData;
000407            assert( pIdx->aiColumn[i]>=0 );
000408            assert( aiCol[i]!=pTab->iPKey );
000409            if( pIdx->aiColumn[i]==pTab->iPKey ){
000410              /* The parent key is a composite key that includes the IPK column */
000411              iParent = regData;
000412            }
000413            sqlite3VdbeAddOp3(v, OP_Ne, iChild, iJump, iParent); VdbeCoverage(v);
000414            sqlite3VdbeChangeP5(v, SQLITE_JUMPIFNULL);
000415          }
000416          sqlite3VdbeGoto(v, iOk);
000417        }
000418    
000419        sqlite3VdbeAddOp4(v, OP_MakeRecord, regTemp, nCol, regRec,
000420                          sqlite3IndexAffinityStr(pParse->db,pIdx), nCol);
000421        sqlite3VdbeAddOp4Int(v, OP_Found, iCur, iOk, regRec, 0); VdbeCoverage(v);
000422    
000423        sqlite3ReleaseTempReg(pParse, regRec);
000424        sqlite3ReleaseTempRange(pParse, regTemp, nCol);
000425      }
000426    }
000427  
000428    if( !pFKey->isDeferred && !(pParse->db->flags & SQLITE_DeferFKs)
000429     && !pParse->pToplevel 
000430     && !pParse->isMultiWrite 
000431    ){
000432      /* Special case: If this is an INSERT statement that will insert exactly
000433      ** one row into the table, raise a constraint immediately instead of
000434      ** incrementing a counter. This is necessary as the VM code is being
000435      ** generated for will not open a statement transaction.  */
000436      assert( nIncr==1 );
000437      sqlite3HaltConstraint(pParse, SQLITE_CONSTRAINT_FOREIGNKEY,
000438          OE_Abort, 0, P4_STATIC, P5_ConstraintFK);
000439    }else{
000440      if( nIncr>0 && pFKey->isDeferred==0 ){
000441        sqlite3MayAbort(pParse);
000442      }
000443      sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, nIncr);
000444    }
000445  
000446    sqlite3VdbeResolveLabel(v, iOk);
000447    sqlite3VdbeAddOp1(v, OP_Close, iCur);
000448  }
000449  
000450  
000451  /*
000452  ** Return an Expr object that refers to a memory register corresponding
000453  ** to column iCol of table pTab.
000454  **
000455  ** regBase is the first of an array of register that contains the data
000456  ** for pTab.  regBase itself holds the rowid.  regBase+1 holds the first
000457  ** column.  regBase+2 holds the second column, and so forth.
000458  */
000459  static Expr *exprTableRegister(
000460    Parse *pParse,     /* Parsing and code generating context */
000461    Table *pTab,       /* The table whose content is at r[regBase]... */
000462    int regBase,       /* Contents of table pTab */
000463    i16 iCol           /* Which column of pTab is desired */
000464  ){
000465    Expr *pExpr;
000466    Column *pCol;
000467    const char *zColl;
000468    sqlite3 *db = pParse->db;
000469  
000470    pExpr = sqlite3Expr(db, TK_REGISTER, 0);
000471    if( pExpr ){
000472      if( iCol>=0 && iCol!=pTab->iPKey ){
000473        pCol = &pTab->aCol[iCol];
000474        pExpr->iTable = regBase + iCol + 1;
000475        pExpr->affinity = pCol->affinity;
000476        zColl = pCol->zColl;
000477        if( zColl==0 ) zColl = db->pDfltColl->zName;
000478        pExpr = sqlite3ExprAddCollateString(pParse, pExpr, zColl);
000479      }else{
000480        pExpr->iTable = regBase;
000481        pExpr->affinity = SQLITE_AFF_INTEGER;
000482      }
000483    }
000484    return pExpr;
000485  }
000486  
000487  /*
000488  ** Return an Expr object that refers to column iCol of table pTab which
000489  ** has cursor iCur.
000490  */
000491  static Expr *exprTableColumn(
000492    sqlite3 *db,      /* The database connection */
000493    Table *pTab,      /* The table whose column is desired */
000494    int iCursor,      /* The open cursor on the table */
000495    i16 iCol          /* The column that is wanted */
000496  ){
000497    Expr *pExpr = sqlite3Expr(db, TK_COLUMN, 0);
000498    if( pExpr ){
000499      pExpr->pTab = pTab;
000500      pExpr->iTable = iCursor;
000501      pExpr->iColumn = iCol;
000502    }
000503    return pExpr;
000504  }
000505  
000506  /*
000507  ** This function is called to generate code executed when a row is deleted
000508  ** from the parent table of foreign key constraint pFKey and, if pFKey is 
000509  ** deferred, when a row is inserted into the same table. When generating
000510  ** code for an SQL UPDATE operation, this function may be called twice -
000511  ** once to "delete" the old row and once to "insert" the new row.
000512  **
000513  ** Parameter nIncr is passed -1 when inserting a row (as this may decrease
000514  ** the number of FK violations in the db) or +1 when deleting one (as this
000515  ** may increase the number of FK constraint problems).
000516  **
000517  ** The code generated by this function scans through the rows in the child
000518  ** table that correspond to the parent table row being deleted or inserted.
000519  ** For each child row found, one of the following actions is taken:
000520  **
000521  **   Operation | FK type   | Action taken
000522  **   --------------------------------------------------------------------------
000523  **   DELETE      immediate   Increment the "immediate constraint counter".
000524  **                           Or, if the ON (UPDATE|DELETE) action is RESTRICT,
000525  **                           throw a "FOREIGN KEY constraint failed" exception.
000526  **
000527  **   INSERT      immediate   Decrement the "immediate constraint counter".
000528  **
000529  **   DELETE      deferred    Increment the "deferred constraint counter".
000530  **                           Or, if the ON (UPDATE|DELETE) action is RESTRICT,
000531  **                           throw a "FOREIGN KEY constraint failed" exception.
000532  **
000533  **   INSERT      deferred    Decrement the "deferred constraint counter".
000534  **
000535  ** These operations are identified in the comment at the top of this file 
000536  ** (fkey.c) as "I.2" and "D.2".
000537  */
000538  static void fkScanChildren(
000539    Parse *pParse,                  /* Parse context */
000540    SrcList *pSrc,                  /* The child table to be scanned */
000541    Table *pTab,                    /* The parent table */
000542    Index *pIdx,                    /* Index on parent covering the foreign key */
000543    FKey *pFKey,                    /* The foreign key linking pSrc to pTab */
000544    int *aiCol,                     /* Map from pIdx cols to child table cols */
000545    int regData,                    /* Parent row data starts here */
000546    int nIncr                       /* Amount to increment deferred counter by */
000547  ){
000548    sqlite3 *db = pParse->db;       /* Database handle */
000549    int i;                          /* Iterator variable */
000550    Expr *pWhere = 0;               /* WHERE clause to scan with */
000551    NameContext sNameContext;       /* Context used to resolve WHERE clause */
000552    WhereInfo *pWInfo;              /* Context used by sqlite3WhereXXX() */
000553    int iFkIfZero = 0;              /* Address of OP_FkIfZero */
000554    Vdbe *v = sqlite3GetVdbe(pParse);
000555  
000556    assert( pIdx==0 || pIdx->pTable==pTab );
000557    assert( pIdx==0 || pIdx->nKeyCol==pFKey->nCol );
000558    assert( pIdx!=0 || pFKey->nCol==1 );
000559    assert( pIdx!=0 || HasRowid(pTab) );
000560  
000561    if( nIncr<0 ){
000562      iFkIfZero = sqlite3VdbeAddOp2(v, OP_FkIfZero, pFKey->isDeferred, 0);
000563      VdbeCoverage(v);
000564    }
000565  
000566    /* Create an Expr object representing an SQL expression like:
000567    **
000568    **   <parent-key1> = <child-key1> AND <parent-key2> = <child-key2> ...
000569    **
000570    ** The collation sequence used for the comparison should be that of
000571    ** the parent key columns. The affinity of the parent key column should
000572    ** be applied to each child key value before the comparison takes place.
000573    */
000574    for(i=0; i<pFKey->nCol; i++){
000575      Expr *pLeft;                  /* Value from parent table row */
000576      Expr *pRight;                 /* Column ref to child table */
000577      Expr *pEq;                    /* Expression (pLeft = pRight) */
000578      i16 iCol;                     /* Index of column in child table */ 
000579      const char *zCol;             /* Name of column in child table */
000580  
000581      iCol = pIdx ? pIdx->aiColumn[i] : -1;
000582      pLeft = exprTableRegister(pParse, pTab, regData, iCol);
000583      iCol = aiCol ? aiCol[i] : pFKey->aCol[0].iFrom;
000584      assert( iCol>=0 );
000585      zCol = pFKey->pFrom->aCol[iCol].zName;
000586      pRight = sqlite3Expr(db, TK_ID, zCol);
000587      pEq = sqlite3PExpr(pParse, TK_EQ, pLeft, pRight);
000588      pWhere = sqlite3ExprAnd(db, pWhere, pEq);
000589    }
000590  
000591    /* If the child table is the same as the parent table, then add terms
000592    ** to the WHERE clause that prevent this entry from being scanned.
000593    ** The added WHERE clause terms are like this:
000594    **
000595    **     $current_rowid!=rowid
000596    **     NOT( $current_a==a AND $current_b==b AND ... )
000597    **
000598    ** The first form is used for rowid tables.  The second form is used
000599    ** for WITHOUT ROWID tables.  In the second form, the primary key is
000600    ** (a,b,...)
000601    */
000602    if( pTab==pFKey->pFrom && nIncr>0 ){
000603      Expr *pNe;                    /* Expression (pLeft != pRight) */
000604      Expr *pLeft;                  /* Value from parent table row */
000605      Expr *pRight;                 /* Column ref to child table */
000606      if( HasRowid(pTab) ){
000607        pLeft = exprTableRegister(pParse, pTab, regData, -1);
000608        pRight = exprTableColumn(db, pTab, pSrc->a[0].iCursor, -1);
000609        pNe = sqlite3PExpr(pParse, TK_NE, pLeft, pRight);
000610      }else{
000611        Expr *pEq, *pAll = 0;
000612        Index *pPk = sqlite3PrimaryKeyIndex(pTab);
000613        assert( pIdx!=0 );
000614        for(i=0; i<pPk->nKeyCol; i++){
000615          i16 iCol = pIdx->aiColumn[i];
000616          assert( iCol>=0 );
000617          pLeft = exprTableRegister(pParse, pTab, regData, iCol);
000618          pRight = exprTableColumn(db, pTab, pSrc->a[0].iCursor, iCol);
000619          pEq = sqlite3PExpr(pParse, TK_EQ, pLeft, pRight);
000620          pAll = sqlite3ExprAnd(db, pAll, pEq);
000621        }
000622        pNe = sqlite3PExpr(pParse, TK_NOT, pAll, 0);
000623      }
000624      pWhere = sqlite3ExprAnd(db, pWhere, pNe);
000625    }
000626  
000627    /* Resolve the references in the WHERE clause. */
000628    memset(&sNameContext, 0, sizeof(NameContext));
000629    sNameContext.pSrcList = pSrc;
000630    sNameContext.pParse = pParse;
000631    sqlite3ResolveExprNames(&sNameContext, pWhere);
000632  
000633    /* Create VDBE to loop through the entries in pSrc that match the WHERE
000634    ** clause. For each row found, increment either the deferred or immediate
000635    ** foreign key constraint counter. */
000636    if( pParse->nErr==0 ){
000637      pWInfo = sqlite3WhereBegin(pParse, pSrc, pWhere, 0, 0, 0, 0);
000638      sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, nIncr);
000639      if( pWInfo ){
000640        sqlite3WhereEnd(pWInfo);
000641      }
000642    }
000643  
000644    /* Clean up the WHERE clause constructed above. */
000645    sqlite3ExprDelete(db, pWhere);
000646    if( iFkIfZero ){
000647      sqlite3VdbeJumpHere(v, iFkIfZero);
000648    }
000649  }
000650  
000651  /*
000652  ** This function returns a linked list of FKey objects (connected by
000653  ** FKey.pNextTo) holding all children of table pTab.  For example,
000654  ** given the following schema:
000655  **
000656  **   CREATE TABLE t1(a PRIMARY KEY);
000657  **   CREATE TABLE t2(b REFERENCES t1(a);
000658  **
000659  ** Calling this function with table "t1" as an argument returns a pointer
000660  ** to the FKey structure representing the foreign key constraint on table
000661  ** "t2". Calling this function with "t2" as the argument would return a
000662  ** NULL pointer (as there are no FK constraints for which t2 is the parent
000663  ** table).
000664  */
000665  FKey *sqlite3FkReferences(Table *pTab){
000666    return (FKey *)sqlite3HashFind(&pTab->pSchema->fkeyHash, pTab->zName);
000667  }
000668  
000669  /*
000670  ** The second argument is a Trigger structure allocated by the 
000671  ** fkActionTrigger() routine. This function deletes the Trigger structure
000672  ** and all of its sub-components.
000673  **
000674  ** The Trigger structure or any of its sub-components may be allocated from
000675  ** the lookaside buffer belonging to database handle dbMem.
000676  */
000677  static void fkTriggerDelete(sqlite3 *dbMem, Trigger *p){
000678    if( p ){
000679      TriggerStep *pStep = p->step_list;
000680      sqlite3ExprDelete(dbMem, pStep->pWhere);
000681      sqlite3ExprListDelete(dbMem, pStep->pExprList);
000682      sqlite3SelectDelete(dbMem, pStep->pSelect);
000683      sqlite3ExprDelete(dbMem, p->pWhen);
000684      sqlite3DbFree(dbMem, p);
000685    }
000686  }
000687  
000688  /*
000689  ** This function is called to generate code that runs when table pTab is
000690  ** being dropped from the database. The SrcList passed as the second argument
000691  ** to this function contains a single entry guaranteed to resolve to
000692  ** table pTab.
000693  **
000694  ** Normally, no code is required. However, if either
000695  **
000696  **   (a) The table is the parent table of a FK constraint, or
000697  **   (b) The table is the child table of a deferred FK constraint and it is
000698  **       determined at runtime that there are outstanding deferred FK 
000699  **       constraint violations in the database,
000700  **
000701  ** then the equivalent of "DELETE FROM <tbl>" is executed before dropping
000702  ** the table from the database. Triggers are disabled while running this
000703  ** DELETE, but foreign key actions are not.
000704  */
000705  void sqlite3FkDropTable(Parse *pParse, SrcList *pName, Table *pTab){
000706    sqlite3 *db = pParse->db;
000707    if( (db->flags&SQLITE_ForeignKeys) && !IsVirtual(pTab) && !pTab->pSelect ){
000708      int iSkip = 0;
000709      Vdbe *v = sqlite3GetVdbe(pParse);
000710  
000711      assert( v );                  /* VDBE has already been allocated */
000712      if( sqlite3FkReferences(pTab)==0 ){
000713        /* Search for a deferred foreign key constraint for which this table
000714        ** is the child table. If one cannot be found, return without 
000715        ** generating any VDBE code. If one can be found, then jump over
000716        ** the entire DELETE if there are no outstanding deferred constraints
000717        ** when this statement is run.  */
000718        FKey *p;
000719        for(p=pTab->pFKey; p; p=p->pNextFrom){
000720          if( p->isDeferred || (db->flags & SQLITE_DeferFKs) ) break;
000721        }
000722        if( !p ) return;
000723        iSkip = sqlite3VdbeMakeLabel(v);
000724        sqlite3VdbeAddOp2(v, OP_FkIfZero, 1, iSkip); VdbeCoverage(v);
000725      }
000726  
000727      pParse->disableTriggers = 1;
000728      sqlite3DeleteFrom(pParse, sqlite3SrcListDup(db, pName, 0), 0);
000729      pParse->disableTriggers = 0;
000730  
000731      /* If the DELETE has generated immediate foreign key constraint 
000732      ** violations, halt the VDBE and return an error at this point, before
000733      ** any modifications to the schema are made. This is because statement
000734      ** transactions are not able to rollback schema changes.  
000735      **
000736      ** If the SQLITE_DeferFKs flag is set, then this is not required, as
000737      ** the statement transaction will not be rolled back even if FK
000738      ** constraints are violated.
000739      */
000740      if( (db->flags & SQLITE_DeferFKs)==0 ){
000741        sqlite3VdbeAddOp2(v, OP_FkIfZero, 0, sqlite3VdbeCurrentAddr(v)+2);
000742        VdbeCoverage(v);
000743        sqlite3HaltConstraint(pParse, SQLITE_CONSTRAINT_FOREIGNKEY,
000744            OE_Abort, 0, P4_STATIC, P5_ConstraintFK);
000745      }
000746  
000747      if( iSkip ){
000748        sqlite3VdbeResolveLabel(v, iSkip);
000749      }
000750    }
000751  }
000752  
000753  
000754  /*
000755  ** The second argument points to an FKey object representing a foreign key
000756  ** for which pTab is the child table. An UPDATE statement against pTab
000757  ** is currently being processed. For each column of the table that is 
000758  ** actually updated, the corresponding element in the aChange[] array
000759  ** is zero or greater (if a column is unmodified the corresponding element
000760  ** is set to -1). If the rowid column is modified by the UPDATE statement
000761  ** the bChngRowid argument is non-zero.
000762  **
000763  ** This function returns true if any of the columns that are part of the
000764  ** child key for FK constraint *p are modified.
000765  */
000766  static int fkChildIsModified(
000767    Table *pTab,                    /* Table being updated */
000768    FKey *p,                        /* Foreign key for which pTab is the child */
000769    int *aChange,                   /* Array indicating modified columns */
000770    int bChngRowid                  /* True if rowid is modified by this update */
000771  ){
000772    int i;
000773    for(i=0; i<p->nCol; i++){
000774      int iChildKey = p->aCol[i].iFrom;
000775      if( aChange[iChildKey]>=0 ) return 1;
000776      if( iChildKey==pTab->iPKey && bChngRowid ) return 1;
000777    }
000778    return 0;
000779  }
000780  
000781  /*
000782  ** The second argument points to an FKey object representing a foreign key
000783  ** for which pTab is the parent table. An UPDATE statement against pTab
000784  ** is currently being processed. For each column of the table that is 
000785  ** actually updated, the corresponding element in the aChange[] array
000786  ** is zero or greater (if a column is unmodified the corresponding element
000787  ** is set to -1). If the rowid column is modified by the UPDATE statement
000788  ** the bChngRowid argument is non-zero.
000789  **
000790  ** This function returns true if any of the columns that are part of the
000791  ** parent key for FK constraint *p are modified.
000792  */
000793  static int fkParentIsModified(
000794    Table *pTab, 
000795    FKey *p, 
000796    int *aChange, 
000797    int bChngRowid
000798  ){
000799    int i;
000800    for(i=0; i<p->nCol; i++){
000801      char *zKey = p->aCol[i].zCol;
000802      int iKey;
000803      for(iKey=0; iKey<pTab->nCol; iKey++){
000804        if( aChange[iKey]>=0 || (iKey==pTab->iPKey && bChngRowid) ){
000805          Column *pCol = &pTab->aCol[iKey];
000806          if( zKey ){
000807            if( 0==sqlite3StrICmp(pCol->zName, zKey) ) return 1;
000808          }else if( pCol->colFlags & COLFLAG_PRIMKEY ){
000809            return 1;
000810          }
000811        }
000812      }
000813    }
000814    return 0;
000815  }
000816  
000817  /*
000818  ** Return true if the parser passed as the first argument is being
000819  ** used to code a trigger that is really a "SET NULL" action belonging
000820  ** to trigger pFKey.
000821  */
000822  static int isSetNullAction(Parse *pParse, FKey *pFKey){
000823    Parse *pTop = sqlite3ParseToplevel(pParse);
000824    if( pTop->pTriggerPrg ){
000825      Trigger *p = pTop->pTriggerPrg->pTrigger;
000826      if( (p==pFKey->apTrigger[0] && pFKey->aAction[0]==OE_SetNull)
000827       || (p==pFKey->apTrigger[1] && pFKey->aAction[1]==OE_SetNull)
000828      ){
000829        return 1;
000830      }
000831    }
000832    return 0;
000833  }
000834  
000835  /*
000836  ** This function is called when inserting, deleting or updating a row of
000837  ** table pTab to generate VDBE code to perform foreign key constraint 
000838  ** processing for the operation.
000839  **
000840  ** For a DELETE operation, parameter regOld is passed the index of the
000841  ** first register in an array of (pTab->nCol+1) registers containing the
000842  ** rowid of the row being deleted, followed by each of the column values
000843  ** of the row being deleted, from left to right. Parameter regNew is passed
000844  ** zero in this case.
000845  **
000846  ** For an INSERT operation, regOld is passed zero and regNew is passed the
000847  ** first register of an array of (pTab->nCol+1) registers containing the new
000848  ** row data.
000849  **
000850  ** For an UPDATE operation, this function is called twice. Once before
000851  ** the original record is deleted from the table using the calling convention
000852  ** described for DELETE. Then again after the original record is deleted
000853  ** but before the new record is inserted using the INSERT convention. 
000854  */
000855  void sqlite3FkCheck(
000856    Parse *pParse,                  /* Parse context */
000857    Table *pTab,                    /* Row is being deleted from this table */ 
000858    int regOld,                     /* Previous row data is stored here */
000859    int regNew,                     /* New row data is stored here */
000860    int *aChange,                   /* Array indicating UPDATEd columns (or 0) */
000861    int bChngRowid                  /* True if rowid is UPDATEd */
000862  ){
000863    sqlite3 *db = pParse->db;       /* Database handle */
000864    FKey *pFKey;                    /* Used to iterate through FKs */
000865    int iDb;                        /* Index of database containing pTab */
000866    const char *zDb;                /* Name of database containing pTab */
000867    int isIgnoreErrors = pParse->disableTriggers;
000868  
000869    /* Exactly one of regOld and regNew should be non-zero. */
000870    assert( (regOld==0)!=(regNew==0) );
000871  
000872    /* If foreign-keys are disabled, this function is a no-op. */
000873    if( (db->flags&SQLITE_ForeignKeys)==0 ) return;
000874  
000875    iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
000876    zDb = db->aDb[iDb].zDbSName;
000877  
000878    /* Loop through all the foreign key constraints for which pTab is the
000879    ** child table (the table that the foreign key definition is part of).  */
000880    for(pFKey=pTab->pFKey; pFKey; pFKey=pFKey->pNextFrom){
000881      Table *pTo;                   /* Parent table of foreign key pFKey */
000882      Index *pIdx = 0;              /* Index on key columns in pTo */
000883      int *aiFree = 0;
000884      int *aiCol;
000885      int iCol;
000886      int i;
000887      int bIgnore = 0;
000888  
000889      if( aChange 
000890       && sqlite3_stricmp(pTab->zName, pFKey->zTo)!=0
000891       && fkChildIsModified(pTab, pFKey, aChange, bChngRowid)==0 
000892      ){
000893        continue;
000894      }
000895  
000896      /* Find the parent table of this foreign key. Also find a unique index 
000897      ** on the parent key columns in the parent table. If either of these 
000898      ** schema items cannot be located, set an error in pParse and return 
000899      ** early.  */
000900      if( pParse->disableTriggers ){
000901        pTo = sqlite3FindTable(db, pFKey->zTo, zDb);
000902      }else{
000903        pTo = sqlite3LocateTable(pParse, 0, pFKey->zTo, zDb);
000904      }
000905      if( !pTo || sqlite3FkLocateIndex(pParse, pTo, pFKey, &pIdx, &aiFree) ){
000906        assert( isIgnoreErrors==0 || (regOld!=0 && regNew==0) );
000907        if( !isIgnoreErrors || db->mallocFailed ) return;
000908        if( pTo==0 ){
000909          /* If isIgnoreErrors is true, then a table is being dropped. In this
000910          ** case SQLite runs a "DELETE FROM xxx" on the table being dropped
000911          ** before actually dropping it in order to check FK constraints.
000912          ** If the parent table of an FK constraint on the current table is
000913          ** missing, behave as if it is empty. i.e. decrement the relevant
000914          ** FK counter for each row of the current table with non-NULL keys.
000915          */
000916          Vdbe *v = sqlite3GetVdbe(pParse);
000917          int iJump = sqlite3VdbeCurrentAddr(v) + pFKey->nCol + 1;
000918          for(i=0; i<pFKey->nCol; i++){
000919            int iReg = pFKey->aCol[i].iFrom + regOld + 1;
000920            sqlite3VdbeAddOp2(v, OP_IsNull, iReg, iJump); VdbeCoverage(v);
000921          }
000922          sqlite3VdbeAddOp2(v, OP_FkCounter, pFKey->isDeferred, -1);
000923        }
000924        continue;
000925      }
000926      assert( pFKey->nCol==1 || (aiFree && pIdx) );
000927  
000928      if( aiFree ){
000929        aiCol = aiFree;
000930      }else{
000931        iCol = pFKey->aCol[0].iFrom;
000932        aiCol = &iCol;
000933      }
000934      for(i=0; i<pFKey->nCol; i++){
000935        if( aiCol[i]==pTab->iPKey ){
000936          aiCol[i] = -1;
000937        }
000938        assert( pIdx==0 || pIdx->aiColumn[i]>=0 );
000939  #ifndef SQLITE_OMIT_AUTHORIZATION
000940        /* Request permission to read the parent key columns. If the 
000941        ** authorization callback returns SQLITE_IGNORE, behave as if any
000942        ** values read from the parent table are NULL. */
000943        if( db->xAuth ){
000944          int rcauth;
000945          char *zCol = pTo->aCol[pIdx ? pIdx->aiColumn[i] : pTo->iPKey].zName;
000946          rcauth = sqlite3AuthReadCol(pParse, pTo->zName, zCol, iDb);
000947          bIgnore = (rcauth==SQLITE_IGNORE);
000948        }
000949  #endif
000950      }
000951  
000952      /* Take a shared-cache advisory read-lock on the parent table. Allocate 
000953      ** a cursor to use to search the unique index on the parent key columns 
000954      ** in the parent table.  */
000955      sqlite3TableLock(pParse, iDb, pTo->tnum, 0, pTo->zName);
000956      pParse->nTab++;
000957  
000958      if( regOld!=0 ){
000959        /* A row is being removed from the child table. Search for the parent.
000960        ** If the parent does not exist, removing the child row resolves an 
000961        ** outstanding foreign key constraint violation. */
000962        fkLookupParent(pParse, iDb, pTo, pIdx, pFKey, aiCol, regOld, -1, bIgnore);
000963      }
000964      if( regNew!=0 && !isSetNullAction(pParse, pFKey) ){
000965        /* A row is being added to the child table. If a parent row cannot
000966        ** be found, adding the child row has violated the FK constraint. 
000967        **
000968        ** If this operation is being performed as part of a trigger program
000969        ** that is actually a "SET NULL" action belonging to this very 
000970        ** foreign key, then omit this scan altogether. As all child key
000971        ** values are guaranteed to be NULL, it is not possible for adding
000972        ** this row to cause an FK violation.  */
000973        fkLookupParent(pParse, iDb, pTo, pIdx, pFKey, aiCol, regNew, +1, bIgnore);
000974      }
000975  
000976      sqlite3DbFree(db, aiFree);
000977    }
000978  
000979    /* Loop through all the foreign key constraints that refer to this table.
000980    ** (the "child" constraints) */
000981    for(pFKey = sqlite3FkReferences(pTab); pFKey; pFKey=pFKey->pNextTo){
000982      Index *pIdx = 0;              /* Foreign key index for pFKey */
000983      SrcList *pSrc;
000984      int *aiCol = 0;
000985  
000986      if( aChange && fkParentIsModified(pTab, pFKey, aChange, bChngRowid)==0 ){
000987        continue;
000988      }
000989  
000990      if( !pFKey->isDeferred && !(db->flags & SQLITE_DeferFKs) 
000991       && !pParse->pToplevel && !pParse->isMultiWrite 
000992      ){
000993        assert( regOld==0 && regNew!=0 );
000994        /* Inserting a single row into a parent table cannot cause (or fix)
000995        ** an immediate foreign key violation. So do nothing in this case.  */
000996        continue;
000997      }
000998  
000999      if( sqlite3FkLocateIndex(pParse, pTab, pFKey, &pIdx, &aiCol) ){
001000        if( !isIgnoreErrors || db->mallocFailed ) return;
001001        continue;
001002      }
001003      assert( aiCol || pFKey->nCol==1 );
001004  
001005      /* Create a SrcList structure containing the child table.  We need the
001006      ** child table as a SrcList for sqlite3WhereBegin() */
001007      pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
001008      if( pSrc ){
001009        struct SrcList_item *pItem = pSrc->a;
001010        pItem->pTab = pFKey->pFrom;
001011        pItem->zName = pFKey->pFrom->zName;
001012        pItem->pTab->nTabRef++;
001013        pItem->iCursor = pParse->nTab++;
001014    
001015        if( regNew!=0 ){
001016          fkScanChildren(pParse, pSrc, pTab, pIdx, pFKey, aiCol, regNew, -1);
001017        }
001018        if( regOld!=0 ){
001019          int eAction = pFKey->aAction[aChange!=0];
001020          fkScanChildren(pParse, pSrc, pTab, pIdx, pFKey, aiCol, regOld, 1);
001021          /* If this is a deferred FK constraint, or a CASCADE or SET NULL
001022          ** action applies, then any foreign key violations caused by
001023          ** removing the parent key will be rectified by the action trigger.
001024          ** So do not set the "may-abort" flag in this case.
001025          **
001026          ** Note 1: If the FK is declared "ON UPDATE CASCADE", then the
001027          ** may-abort flag will eventually be set on this statement anyway
001028          ** (when this function is called as part of processing the UPDATE
001029          ** within the action trigger).
001030          **
001031          ** Note 2: At first glance it may seem like SQLite could simply omit
001032          ** all OP_FkCounter related scans when either CASCADE or SET NULL
001033          ** applies. The trouble starts if the CASCADE or SET NULL action 
001034          ** trigger causes other triggers or action rules attached to the 
001035          ** child table to fire. In these cases the fk constraint counters
001036          ** might be set incorrectly if any OP_FkCounter related scans are 
001037          ** omitted.  */
001038          if( !pFKey->isDeferred && eAction!=OE_Cascade && eAction!=OE_SetNull ){
001039            sqlite3MayAbort(pParse);
001040          }
001041        }
001042        pItem->zName = 0;
001043        sqlite3SrcListDelete(db, pSrc);
001044      }
001045      sqlite3DbFree(db, aiCol);
001046    }
001047  }
001048  
001049  #define COLUMN_MASK(x) (((x)>31) ? 0xffffffff : ((u32)1<<(x)))
001050  
001051  /*
001052  ** This function is called before generating code to update or delete a 
001053  ** row contained in table pTab.
001054  */
001055  u32 sqlite3FkOldmask(
001056    Parse *pParse,                  /* Parse context */
001057    Table *pTab                     /* Table being modified */
001058  ){
001059    u32 mask = 0;
001060    if( pParse->db->flags&SQLITE_ForeignKeys ){
001061      FKey *p;
001062      int i;
001063      for(p=pTab->pFKey; p; p=p->pNextFrom){
001064        for(i=0; i<p->nCol; i++) mask |= COLUMN_MASK(p->aCol[i].iFrom);
001065      }
001066      for(p=sqlite3FkReferences(pTab); p; p=p->pNextTo){
001067        Index *pIdx = 0;
001068        sqlite3FkLocateIndex(pParse, pTab, p, &pIdx, 0);
001069        if( pIdx ){
001070          for(i=0; i<pIdx->nKeyCol; i++){
001071            assert( pIdx->aiColumn[i]>=0 );
001072            mask |= COLUMN_MASK(pIdx->aiColumn[i]);
001073          }
001074        }
001075      }
001076    }
001077    return mask;
001078  }
001079  
001080  
001081  /*
001082  ** This function is called before generating code to update or delete a 
001083  ** row contained in table pTab. If the operation is a DELETE, then
001084  ** parameter aChange is passed a NULL value. For an UPDATE, aChange points
001085  ** to an array of size N, where N is the number of columns in table pTab.
001086  ** If the i'th column is not modified by the UPDATE, then the corresponding 
001087  ** entry in the aChange[] array is set to -1. If the column is modified,
001088  ** the value is 0 or greater. Parameter chngRowid is set to true if the
001089  ** UPDATE statement modifies the rowid fields of the table.
001090  **
001091  ** If any foreign key processing will be required, this function returns
001092  ** non-zero. If there is no foreign key related processing, this function 
001093  ** returns zero.
001094  **
001095  ** For an UPDATE, this function returns 2 if:
001096  **
001097  **   * There are any FKs for which pTab is the child and the parent table, or
001098  **   * the UPDATE modifies one or more parent keys for which the action is
001099  **     not "NO ACTION" (i.e. is CASCADE, SET DEFAULT or SET NULL).
001100  **
001101  ** Or, assuming some other foreign key processing is required, 1.
001102  */
001103  int sqlite3FkRequired(
001104    Parse *pParse,                  /* Parse context */
001105    Table *pTab,                    /* Table being modified */
001106    int *aChange,                   /* Non-NULL for UPDATE operations */
001107    int chngRowid                   /* True for UPDATE that affects rowid */
001108  ){
001109    int eRet = 0;
001110    if( pParse->db->flags&SQLITE_ForeignKeys ){
001111      if( !aChange ){
001112        /* A DELETE operation. Foreign key processing is required if the 
001113        ** table in question is either the child or parent table for any 
001114        ** foreign key constraint.  */
001115        eRet = (sqlite3FkReferences(pTab) || pTab->pFKey);
001116      }else{
001117        /* This is an UPDATE. Foreign key processing is only required if the
001118        ** operation modifies one or more child or parent key columns. */
001119        FKey *p;
001120  
001121        /* Check if any child key columns are being modified. */
001122        for(p=pTab->pFKey; p; p=p->pNextFrom){
001123          if( 0==sqlite3_stricmp(pTab->zName, p->zTo) ) return 2;
001124          if( fkChildIsModified(pTab, p, aChange, chngRowid) ){
001125            eRet = 1;
001126          }
001127        }
001128  
001129        /* Check if any parent key columns are being modified. */
001130        for(p=sqlite3FkReferences(pTab); p; p=p->pNextTo){
001131          if( fkParentIsModified(pTab, p, aChange, chngRowid) ){
001132            if( p->aAction[1]!=OE_None ) return 2;
001133            eRet = 1;
001134          }
001135        }
001136      }
001137    }
001138    return eRet;
001139  }
001140  
001141  /*
001142  ** This function is called when an UPDATE or DELETE operation is being 
001143  ** compiled on table pTab, which is the parent table of foreign-key pFKey.
001144  ** If the current operation is an UPDATE, then the pChanges parameter is
001145  ** passed a pointer to the list of columns being modified. If it is a
001146  ** DELETE, pChanges is passed a NULL pointer.
001147  **
001148  ** It returns a pointer to a Trigger structure containing a trigger
001149  ** equivalent to the ON UPDATE or ON DELETE action specified by pFKey.
001150  ** If the action is "NO ACTION" or "RESTRICT", then a NULL pointer is
001151  ** returned (these actions require no special handling by the triggers
001152  ** sub-system, code for them is created by fkScanChildren()).
001153  **
001154  ** For example, if pFKey is the foreign key and pTab is table "p" in 
001155  ** the following schema:
001156  **
001157  **   CREATE TABLE p(pk PRIMARY KEY);
001158  **   CREATE TABLE c(ck REFERENCES p ON DELETE CASCADE);
001159  **
001160  ** then the returned trigger structure is equivalent to:
001161  **
001162  **   CREATE TRIGGER ... DELETE ON p BEGIN
001163  **     DELETE FROM c WHERE ck = old.pk;
001164  **   END;
001165  **
001166  ** The returned pointer is cached as part of the foreign key object. It
001167  ** is eventually freed along with the rest of the foreign key object by 
001168  ** sqlite3FkDelete().
001169  */
001170  static Trigger *fkActionTrigger(
001171    Parse *pParse,                  /* Parse context */
001172    Table *pTab,                    /* Table being updated or deleted from */
001173    FKey *pFKey,                    /* Foreign key to get action for */
001174    ExprList *pChanges              /* Change-list for UPDATE, NULL for DELETE */
001175  ){
001176    sqlite3 *db = pParse->db;       /* Database handle */
001177    int action;                     /* One of OE_None, OE_Cascade etc. */
001178    Trigger *pTrigger;              /* Trigger definition to return */
001179    int iAction = (pChanges!=0);    /* 1 for UPDATE, 0 for DELETE */
001180  
001181    action = pFKey->aAction[iAction];
001182    if( action==OE_Restrict && (db->flags & SQLITE_DeferFKs) ){
001183      return 0;
001184    }
001185    pTrigger = pFKey->apTrigger[iAction];
001186  
001187    if( action!=OE_None && !pTrigger ){
001188      char const *zFrom;            /* Name of child table */
001189      int nFrom;                    /* Length in bytes of zFrom */
001190      Index *pIdx = 0;              /* Parent key index for this FK */
001191      int *aiCol = 0;               /* child table cols -> parent key cols */
001192      TriggerStep *pStep = 0;        /* First (only) step of trigger program */
001193      Expr *pWhere = 0;             /* WHERE clause of trigger step */
001194      ExprList *pList = 0;          /* Changes list if ON UPDATE CASCADE */
001195      Select *pSelect = 0;          /* If RESTRICT, "SELECT RAISE(...)" */
001196      int i;                        /* Iterator variable */
001197      Expr *pWhen = 0;              /* WHEN clause for the trigger */
001198  
001199      if( sqlite3FkLocateIndex(pParse, pTab, pFKey, &pIdx, &aiCol) ) return 0;
001200      assert( aiCol || pFKey->nCol==1 );
001201  
001202      for(i=0; i<pFKey->nCol; i++){
001203        Token tOld = { "old", 3 };  /* Literal "old" token */
001204        Token tNew = { "new", 3 };  /* Literal "new" token */
001205        Token tFromCol;             /* Name of column in child table */
001206        Token tToCol;               /* Name of column in parent table */
001207        int iFromCol;               /* Idx of column in child table */
001208        Expr *pEq;                  /* tFromCol = OLD.tToCol */
001209  
001210        iFromCol = aiCol ? aiCol[i] : pFKey->aCol[0].iFrom;
001211        assert( iFromCol>=0 );
001212        assert( pIdx!=0 || (pTab->iPKey>=0 && pTab->iPKey<pTab->nCol) );
001213        assert( pIdx==0 || pIdx->aiColumn[i]>=0 );
001214        sqlite3TokenInit(&tToCol,
001215                     pTab->aCol[pIdx ? pIdx->aiColumn[i] : pTab->iPKey].zName);
001216        sqlite3TokenInit(&tFromCol, pFKey->pFrom->aCol[iFromCol].zName);
001217  
001218        /* Create the expression "OLD.zToCol = zFromCol". It is important
001219        ** that the "OLD.zToCol" term is on the LHS of the = operator, so
001220        ** that the affinity and collation sequence associated with the
001221        ** parent table are used for the comparison. */
001222        pEq = sqlite3PExpr(pParse, TK_EQ,
001223            sqlite3PExpr(pParse, TK_DOT, 
001224              sqlite3ExprAlloc(db, TK_ID, &tOld, 0),
001225              sqlite3ExprAlloc(db, TK_ID, &tToCol, 0)),
001226            sqlite3ExprAlloc(db, TK_ID, &tFromCol, 0)
001227        );
001228        pWhere = sqlite3ExprAnd(db, pWhere, pEq);
001229  
001230        /* For ON UPDATE, construct the next term of the WHEN clause.
001231        ** The final WHEN clause will be like this:
001232        **
001233        **    WHEN NOT(old.col1 IS new.col1 AND ... AND old.colN IS new.colN)
001234        */
001235        if( pChanges ){
001236          pEq = sqlite3PExpr(pParse, TK_IS,
001237              sqlite3PExpr(pParse, TK_DOT, 
001238                sqlite3ExprAlloc(db, TK_ID, &tOld, 0),
001239                sqlite3ExprAlloc(db, TK_ID, &tToCol, 0)),
001240              sqlite3PExpr(pParse, TK_DOT, 
001241                sqlite3ExprAlloc(db, TK_ID, &tNew, 0),
001242                sqlite3ExprAlloc(db, TK_ID, &tToCol, 0))
001243              );
001244          pWhen = sqlite3ExprAnd(db, pWhen, pEq);
001245        }
001246    
001247        if( action!=OE_Restrict && (action!=OE_Cascade || pChanges) ){
001248          Expr *pNew;
001249          if( action==OE_Cascade ){
001250            pNew = sqlite3PExpr(pParse, TK_DOT, 
001251              sqlite3ExprAlloc(db, TK_ID, &tNew, 0),
001252              sqlite3ExprAlloc(db, TK_ID, &tToCol, 0));
001253          }else if( action==OE_SetDflt ){
001254            Expr *pDflt = pFKey->pFrom->aCol[iFromCol].pDflt;
001255            if( pDflt ){
001256              pNew = sqlite3ExprDup(db, pDflt, 0);
001257            }else{
001258              pNew = sqlite3ExprAlloc(db, TK_NULL, 0, 0);
001259            }
001260          }else{
001261            pNew = sqlite3ExprAlloc(db, TK_NULL, 0, 0);
001262          }
001263          pList = sqlite3ExprListAppend(pParse, pList, pNew);
001264          sqlite3ExprListSetName(pParse, pList, &tFromCol, 0);
001265        }
001266      }
001267      sqlite3DbFree(db, aiCol);
001268  
001269      zFrom = pFKey->pFrom->zName;
001270      nFrom = sqlite3Strlen30(zFrom);
001271  
001272      if( action==OE_Restrict ){
001273        Token tFrom;
001274        Expr *pRaise; 
001275  
001276        tFrom.z = zFrom;
001277        tFrom.n = nFrom;
001278        pRaise = sqlite3Expr(db, TK_RAISE, "FOREIGN KEY constraint failed");
001279        if( pRaise ){
001280          pRaise->affinity = OE_Abort;
001281        }
001282        pSelect = sqlite3SelectNew(pParse, 
001283            sqlite3ExprListAppend(pParse, 0, pRaise),
001284            sqlite3SrcListAppend(db, 0, &tFrom, 0),
001285            pWhere,
001286            0, 0, 0, 0, 0, 0
001287        );
001288        pWhere = 0;
001289      }
001290  
001291      /* Disable lookaside memory allocation */
001292      db->lookaside.bDisable++;
001293  
001294      pTrigger = (Trigger *)sqlite3DbMallocZero(db, 
001295          sizeof(Trigger) +         /* struct Trigger */
001296          sizeof(TriggerStep) +     /* Single step in trigger program */
001297          nFrom + 1                 /* Space for pStep->zTarget */
001298      );
001299      if( pTrigger ){
001300        pStep = pTrigger->step_list = (TriggerStep *)&pTrigger[1];
001301        pStep->zTarget = (char *)&pStep[1];
001302        memcpy((char *)pStep->zTarget, zFrom, nFrom);
001303    
001304        pStep->pWhere = sqlite3ExprDup(db, pWhere, EXPRDUP_REDUCE);
001305        pStep->pExprList = sqlite3ExprListDup(db, pList, EXPRDUP_REDUCE);
001306        pStep->pSelect = sqlite3SelectDup(db, pSelect, EXPRDUP_REDUCE);
001307        if( pWhen ){
001308          pWhen = sqlite3PExpr(pParse, TK_NOT, pWhen, 0);
001309          pTrigger->pWhen = sqlite3ExprDup(db, pWhen, EXPRDUP_REDUCE);
001310        }
001311      }
001312  
001313      /* Re-enable the lookaside buffer, if it was disabled earlier. */
001314      db->lookaside.bDisable--;
001315  
001316      sqlite3ExprDelete(db, pWhere);
001317      sqlite3ExprDelete(db, pWhen);
001318      sqlite3ExprListDelete(db, pList);
001319      sqlite3SelectDelete(db, pSelect);
001320      if( db->mallocFailed==1 ){
001321        fkTriggerDelete(db, pTrigger);
001322        return 0;
001323      }
001324      assert( pStep!=0 );
001325  
001326      switch( action ){
001327        case OE_Restrict:
001328          pStep->op = TK_SELECT; 
001329          break;
001330        case OE_Cascade: 
001331          if( !pChanges ){ 
001332            pStep->op = TK_DELETE; 
001333            break; 
001334          }
001335        default:
001336          pStep->op = TK_UPDATE;
001337      }
001338      pStep->pTrig = pTrigger;
001339      pTrigger->pSchema = pTab->pSchema;
001340      pTrigger->pTabSchema = pTab->pSchema;
001341      pFKey->apTrigger[iAction] = pTrigger;
001342      pTrigger->op = (pChanges ? TK_UPDATE : TK_DELETE);
001343    }
001344  
001345    return pTrigger;
001346  }
001347  
001348  /*
001349  ** This function is called when deleting or updating a row to implement
001350  ** any required CASCADE, SET NULL or SET DEFAULT actions.
001351  */
001352  void sqlite3FkActions(
001353    Parse *pParse,                  /* Parse context */
001354    Table *pTab,                    /* Table being updated or deleted from */
001355    ExprList *pChanges,             /* Change-list for UPDATE, NULL for DELETE */
001356    int regOld,                     /* Address of array containing old row */
001357    int *aChange,                   /* Array indicating UPDATEd columns (or 0) */
001358    int bChngRowid                  /* True if rowid is UPDATEd */
001359  ){
001360    /* If foreign-key support is enabled, iterate through all FKs that 
001361    ** refer to table pTab. If there is an action associated with the FK 
001362    ** for this operation (either update or delete), invoke the associated 
001363    ** trigger sub-program.  */
001364    if( pParse->db->flags&SQLITE_ForeignKeys ){
001365      FKey *pFKey;                  /* Iterator variable */
001366      for(pFKey = sqlite3FkReferences(pTab); pFKey; pFKey=pFKey->pNextTo){
001367        if( aChange==0 || fkParentIsModified(pTab, pFKey, aChange, bChngRowid) ){
001368          Trigger *pAct = fkActionTrigger(pParse, pTab, pFKey, pChanges);
001369          if( pAct ){
001370            sqlite3CodeRowTriggerDirect(pParse, pAct, pTab, regOld, OE_Abort, 0);
001371          }
001372        }
001373      }
001374    }
001375  }
001376  
001377  #endif /* ifndef SQLITE_OMIT_TRIGGER */
001378  
001379  /*
001380  ** Free all memory associated with foreign key definitions attached to
001381  ** table pTab. Remove the deleted foreign keys from the Schema.fkeyHash
001382  ** hash table.
001383  */
001384  void sqlite3FkDelete(sqlite3 *db, Table *pTab){
001385    FKey *pFKey;                    /* Iterator variable */
001386    FKey *pNext;                    /* Copy of pFKey->pNextFrom */
001387  
001388    assert( db==0 || IsVirtual(pTab)
001389           || sqlite3SchemaMutexHeld(db, 0, pTab->pSchema) );
001390    for(pFKey=pTab->pFKey; pFKey; pFKey=pNext){
001391  
001392      /* Remove the FK from the fkeyHash hash table. */
001393      if( !db || db->pnBytesFreed==0 ){
001394        if( pFKey->pPrevTo ){
001395          pFKey->pPrevTo->pNextTo = pFKey->pNextTo;
001396        }else{
001397          void *p = (void *)pFKey->pNextTo;
001398          const char *z = (p ? pFKey->pNextTo->zTo : pFKey->zTo);
001399          sqlite3HashInsert(&pTab->pSchema->fkeyHash, z, p);
001400        }
001401        if( pFKey->pNextTo ){
001402          pFKey->pNextTo->pPrevTo = pFKey->pPrevTo;
001403        }
001404      }
001405  
001406      /* EV: R-30323-21917 Each foreign key constraint in SQLite is
001407      ** classified as either immediate or deferred.
001408      */
001409      assert( pFKey->isDeferred==0 || pFKey->isDeferred==1 );
001410  
001411      /* Delete any triggers created to implement actions for this FK. */
001412  #ifndef SQLITE_OMIT_TRIGGER
001413      fkTriggerDelete(db, pFKey->apTrigger[0]);
001414      fkTriggerDelete(db, pFKey->apTrigger[1]);
001415  #endif
001416  
001417      pNext = pFKey->pNextFrom;
001418      sqlite3DbFree(db, pFKey);
001419    }
001420  }
001421  #endif /* ifndef SQLITE_OMIT_FOREIGN_KEY */