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