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