sqlite3recover.c · cryptotaxi247/netdata-1

Code Commits Issues Pulls Sessions CI/CD

master

c 2,872 lines 86.5 KB

Raw

1	/*
2	** 2022-08-27
3	**
4	** The author disclaims copyright to this source code. In place of
5	** a legal notice, here is a blessing:
6	**
7	** May you do good and not evil.
8	** May you find forgiveness for yourself and forgive others.
9	** May you share freely, never taking more than you give.
10	**
11	*************************************************************************
12	**
13	*/
14
15	#pragma GCC diagnostic push
16	#pragma GCC diagnostic ignored "-Wsign-compare"
17	#include "sqlite3recover.h"
18	#include <assert.h>
19	#include <string.h>
20
21	#ifndef SQLITE_OMIT_VIRTUALTABLE
22
23	/*
24	** Declaration for public API function in file dbdata.c. This may be called
25	** with NULL as the final two arguments to register the sqlite_dbptr and
26	** sqlite_dbdata virtual tables with a database handle.
27	*/
28	#ifdef _WIN32
29	__declspec(dllexport)
30	#endif
31	int sqlite3_dbdata_init(sqlite3, char, const sqlite3_api_routines);
32
33	typedef unsigned int u32;
34	typedef unsigned char u8;
35	typedef sqlite3_int64 i64;
36
37	typedef struct RecoverTable RecoverTable;
38	typedef struct RecoverColumn RecoverColumn;
39
40	/*
41	** When recovering rows of data that can be associated with table
42	** definitions recovered from the sqlite_schema table, each table is
43	** represented by an instance of the following object.
44	**
45	** iRoot:
46	** The root page in the original database. Not necessarily (and usually
47	** not) the same in the recovered database.
48	**
49	** zTab:
50	** Name of the table.
51	**
52	** nCol/aCol[]:
53	** aCol[] is an array of nCol columns. In the order in which they appear
54	** in the table.
55	**
56	** bIntkey:
57	** Set to true for intkey tables, false for WITHOUT ROWID.
58	**
59	** iRowidBind:
60	** Each column in the aCol[] array has associated with it the index of
61	** the bind parameter its values will be bound to in the INSERT statement
62	** used to construct the output database. If the table does has a rowid
63	** but not an INTEGER PRIMARY KEY column, then iRowidBind contains the
64	** index of the bind paramater to which the rowid value should be bound.
65	** Otherwise, it contains -1. If the table does contain an INTEGER PRIMARY
66	** KEY column, then the rowid value should be bound to the index associated
67	** with the column.
68	**
69	** pNext:
70	** All RecoverTable objects used by the recovery operation are allocated
71	** and populated as part of creating the recovered database schema in
72	** the output database, before any non-schema data are recovered. They
73	** are then stored in a singly-linked list linked by this variable beginning
74	** at sqlite3_recover.pTblList.
75	*/
76	struct RecoverTable {
77	u32 iRoot; /* Root page in original database */
78	char zTab; / Name of table */
79	int nCol; /* Number of columns in table */
80	RecoverColumn aCol; / Array of columns */
81	int bIntkey; /* True for intkey, false for without rowid */
82	int iRowidBind; /* If >0, bind rowid to INSERT here */
83	RecoverTable *pNext;
84	};
85
86	/*
87	** Each database column is represented by an instance of the following object
88	** stored in the RecoverTable.aCol[] array of the associated table.
89	**
90	** iField:
91	** The index of the associated field within database records. Or -1 if
92	** there is no associated field (e.g. for virtual generated columns).
93	**
94	** iBind:
95	** The bind index of the INSERT statement to bind this columns values
96	** to. Or 0 if there is no such index (iff (iField<0)).
97	**
98	** bIPK:
99	** True if this is the INTEGER PRIMARY KEY column.
100	**
101	** zCol:
102	** Name of column.
103	**
104	** eHidden:
105	** A RECOVER_EHIDDEN_* constant value (see below for interpretation of each).
106	*/
107	struct RecoverColumn {
108	int iField; /* Field in record on disk */
109	int iBind; /* Binding to use in INSERT */
110	int bIPK; /* True for IPK column */
111	char *zCol;
112	int eHidden;
113	};
114
115	#define RECOVER_EHIDDEN_NONE 0 /* Normal database column */
116	#define RECOVER_EHIDDEN_HIDDEN 1 /* Column is __HIDDEN__ */
117	#define RECOVER_EHIDDEN_VIRTUAL 2 /* Virtual generated column */
118	#define RECOVER_EHIDDEN_STORED 3 /* Stored generated column */
119
120	/*
121	** Bitmap object used to track pages in the input database. Allocated
122	** and manipulated only by the following functions:
123	**
124	** recoverBitmapAlloc()
125	** recoverBitmapFree()
126	** recoverBitmapSet()
127	** recoverBitmapQuery()
128	**
129	** nPg:
130	** Largest page number that may be stored in the bitmap. The range
131	** of valid keys is 1 to nPg, inclusive.
132	**
133	** aElem[]:
134	** Array large enough to contain a bit for each key. For key value
135	** iKey, the associated bit is the bit (iKey%32) of aElem[iKey/32].
136	** In other words, the following is true if bit iKey is set, or
137	** false if it is clear:
138	**
139	** (aElem[iKey/32] & (1 << (iKey%32))) ? 1 : 0
140	*/
141	typedef struct RecoverBitmap RecoverBitmap;
142	struct RecoverBitmap {
143	i64 nPg; /* Size of bitmap */
144	u32 aElem[1]; /* Array of 32-bit bitmasks */
145	};
146
147	/*
148	** State variables (part of the sqlite3_recover structure) used while
149	** recovering data for tables identified in the recovered schema (state
150	** RECOVER_STATE_WRITING).
151	*/
152	typedef struct RecoverStateW1 RecoverStateW1;
153	struct RecoverStateW1 {
154	sqlite3_stmt *pTbls;
155	sqlite3_stmt *pSel;
156	sqlite3_stmt *pInsert;
157	int nInsert;
158
159	RecoverTable pTab; / Table currently being written */
160	int nMax; /* Max column count in any schema table */
161	sqlite3_value *apVal; / Array of nMax values */
162	int nVal; /* Number of valid entries in apVal[] */
163	int bHaveRowid;
164	i64 iRowid;
165	i64 iPrevPage;
166	int iPrevCell;
167	};
168
169	/*
170	** State variables (part of the sqlite3_recover structure) used while
171	** recovering data destined for the lost and found table (states
172	** RECOVER_STATE_LOSTANDFOUND[123]).
173	*/
174	typedef struct RecoverStateLAF RecoverStateLAF;
175	struct RecoverStateLAF {
176	RecoverBitmap *pUsed;
177	i64 nPg; /* Size of db in pages */
178	sqlite3_stmt *pAllAndParent;
179	sqlite3_stmt *pMapInsert;
180	sqlite3_stmt *pMaxField;
181	sqlite3_stmt *pUsedPages;
182	sqlite3_stmt *pFindRoot;
183	sqlite3_stmt pInsert; / INSERT INTO lost_and_found ... */
184	sqlite3_stmt *pAllPage;
185	sqlite3_stmt *pPageData;
186	sqlite3_value **apVal;
187	int nMaxField;
188	};
189
190	/*
191	** Main recover handle structure.
192	*/
193	struct sqlite3_recover {
194	/* Copies of sqlite3_recover_init[_sql]() parameters */
195	sqlite3 dbIn; / Input database */
196	char zDb; / Name of input db ("main" etc.) */
197	char zUri; / URI for output database */
198	void pSqlCtx; / SQL callback context */
199	int (xSql)(void,const char); / Pointer to SQL callback function */
200
201	/* Values configured by sqlite3_recover_config() */
202	char zStateDb; / State database to use (or NULL) */
203	char zLostAndFound; / Name of lost-and-found table (or NULL) */
204	int bFreelistCorrupt; /* SQLITE_RECOVER_FREELIST_CORRUPT setting */
205	int bRecoverRowid; /* SQLITE_RECOVER_ROWIDS setting */
206	int bSlowIndexes; /* SQLITE_RECOVER_SLOWINDEXES setting */
207
208	int pgsz;
209	int detected_pgsz;
210	int nReserve;
211	u8 *pPage1Disk;
212	u8 *pPage1Cache;
213
214	/* Error code and error message */
215	int errCode; /* For sqlite3_recover_errcode() */
216	char zErrMsg; / For sqlite3_recover_errmsg() */
217
218	int eState;
219	int bCloseTransaction;
220
221	/* Variables used with eState==RECOVER_STATE_WRITING */
222	RecoverStateW1 w1;
223
224	/* Variables used with states RECOVER_STATE_LOSTANDFOUND[123] */
225	RecoverStateLAF laf;
226
227	/* Fields used within sqlite3_recover_run() */
228	sqlite3 dbOut; / Output database */
229	sqlite3_stmt pGetPage; / SELECT against input db sqlite_dbdata */
230	RecoverTable pTblList; / List of tables recovered from schema */
231	};
232
233	/*
234	** The various states in which an sqlite3_recover object may exist:
235	**
236	** RECOVER_STATE_INIT:
237	** The object is initially created in this state. sqlite3_recover_step()
238	** has yet to be called. This is the only state in which it is permitted
239	** to call sqlite3_recover_config().
240	**
241	** RECOVER_STATE_WRITING:
242	**
243	** RECOVER_STATE_LOSTANDFOUND1:
244	** State to populate the bitmap of pages used by other tables or the
245	** database freelist.
246	**
247	** RECOVER_STATE_LOSTANDFOUND2:
248	** Populate the recovery.map table - used to figure out a "root" page
249	** for each lost page from in the database from which records are
250	** extracted.
251	**
252	** RECOVER_STATE_LOSTANDFOUND3:
253	** Populate the lost-and-found table itself.
254	*/
255	#define RECOVER_STATE_INIT 0
256	#define RECOVER_STATE_WRITING 1
257	#define RECOVER_STATE_LOSTANDFOUND1 2
258	#define RECOVER_STATE_LOSTANDFOUND2 3
259	#define RECOVER_STATE_LOSTANDFOUND3 4
260	#define RECOVER_STATE_SCHEMA2 5
261	#define RECOVER_STATE_DONE 6
262
263
264	/*
265	** Global variables used by this extension.
266	*/
267	typedef struct RecoverGlobal RecoverGlobal;
268	struct RecoverGlobal {
269	const sqlite3_io_methods *pMethods;
270	sqlite3_recover *p;
271	};
272	static RecoverGlobal recover_g;
273
274	/*
275	** Use this static SQLite mutex to protect the globals during the
276	** first call to sqlite3_recover_step().
277	*/
278	#define RECOVER_MUTEX_ID SQLITE_MUTEX_STATIC_APP2
279
280
281	/*
282	** Default value for SQLITE_RECOVER_ROWIDS (sqlite3_recover.bRecoverRowid).
283	*/
284	#define RECOVER_ROWID_DEFAULT 1
285
286	/*
287	** Mutex handling:
288	**
289	** recoverEnterMutex() - Enter the recovery mutex
290	** recoverLeaveMutex() - Leave the recovery mutex
291	** recoverAssertMutexHeld() - Assert that the recovery mutex is held
292	*/
293	#if defined(SQLITE_THREADSAFE) && SQLITE_THREADSAFE==0
294	# define recoverEnterMutex()
295	# define recoverLeaveMutex()
296	#else
297	static void recoverEnterMutex(void){
298	sqlite3_mutex_enter(sqlite3_mutex_alloc(RECOVER_MUTEX_ID));
299	}
300	static void recoverLeaveMutex(void){
301	sqlite3_mutex_leave(sqlite3_mutex_alloc(RECOVER_MUTEX_ID));
302	}
303	#endif
304	#if SQLITE_THREADSAFE+0>=1 && defined(SQLITE_DEBUG)
305	static void recoverAssertMutexHeld(void){
306	assert( sqlite3_mutex_held(sqlite3_mutex_alloc(RECOVER_MUTEX_ID)) );
307	}
308	#else
309	# define recoverAssertMutexHeld()
310	#endif
311
312
313	/*
314	** Like strlen(). But handles NULL pointer arguments.
315	*/
316	static int recoverStrlen(const char *zStr){
317	if( zStr==0 ) return 0;
318	return (int)(strlen(zStr)&0x7fffffff);
319	}
320
321	/*
322	** This function is a no-op if the recover handle passed as the first
323	** argument already contains an error (if p->errCode!=SQLITE_OK).
324	**
325	** Otherwise, an attempt is made to allocate, zero and return a buffer nByte
326	** bytes in size. If successful, a pointer to the new buffer is returned. Or,
327	** if an OOM error occurs, NULL is returned and the handle error code
328	** (p->errCode) set to SQLITE_NOMEM.
329	*/
330	static void recoverMalloc(sqlite3_recover p, i64 nByte){
331	void *pRet = 0;
332	assert( nByte>0 );
333	if( p->errCode==SQLITE_OK ){
334	pRet = sqlite3_malloc64(nByte);
335	if( pRet ){
336	memset(pRet, 0, nByte);
337	}else{
338	p->errCode = SQLITE_NOMEM;
339	}
340	}
341	return pRet;
342	}
343
344	/*
345	** Set the error code and error message for the recover handle passed as
346	** the first argument. The error code is set to the value of parameter
347	** errCode.
348	**
349	** Parameter zFmt must be a printf() style formatting string. The handle
350	** error message is set to the result of using any trailing arguments for
351	** parameter substitutions in the formatting string.
352	**
353	** For example:
354	**
355	** recoverError(p, SQLITE_ERROR, "no such table: %s", zTablename);
356	*/
357	static int recoverError(
358	sqlite3_recover *p,
359	int errCode,
360	const char *zFmt, ...
361	){
362	char *z = 0;
363	va_list ap;
364	va_start(ap, zFmt);
365	if( zFmt ){
366	z = sqlite3_vmprintf(zFmt, ap);
367	va_end(ap);
368	}
369	sqlite3_free(p->zErrMsg);
370	p->zErrMsg = z;
371	p->errCode = errCode;
372	return errCode;
373	}
374
375
376	/*
377	** This function is a no-op if p->errCode is initially other than SQLITE_OK.
378	** In this case it returns NULL.
379	**
380	** Otherwise, an attempt is made to allocate and return a bitmap object
381	** large enough to store a bit for all page numbers between 1 and nPg,
382	** inclusive. The bitmap is initially zeroed.
383	*/
384	static RecoverBitmap recoverBitmapAlloc(sqlite3_recover p, i64 nPg){
385	int nElem = (nPg+1+31) / 32;
386	int nByte = sizeof(RecoverBitmap) + nElem*sizeof(u32);
387	RecoverBitmap pRet = (RecoverBitmap)recoverMalloc(p, nByte);
388
389	if( pRet ){
390	pRet->nPg = nPg;
391	}
392	return pRet;
393	}
394
395	/*
396	** Free a bitmap object allocated by recoverBitmapAlloc().
397	*/
398	static void recoverBitmapFree(RecoverBitmap *pMap){
399	sqlite3_free(pMap);
400	}
401
402	/*
403	** Set the bit associated with page iPg in bitvec pMap.
404	*/
405	static void recoverBitmapSet(RecoverBitmap *pMap, i64 iPg){
406	if( iPg<=pMap->nPg ){
407	int iElem = (iPg / 32);
408	int iBit = (iPg % 32);
409	pMap->aElem[iElem] \|= (((u32)1) << iBit);
410	}
411	}
412
413	/*
414	** Query bitmap object pMap for the state of the bit associated with page
415	** iPg. Return 1 if it is set, or 0 otherwise.
416	*/
417	static int recoverBitmapQuery(RecoverBitmap *pMap, i64 iPg){
418	int ret = 1;
419	if( iPg<=pMap->nPg && iPg>0 ){
420	int iElem = (iPg / 32);
421	int iBit = (iPg % 32);
422	ret = (pMap->aElem[iElem] & (((u32)1) << iBit)) ? 1 : 0;
423	}
424	return ret;
425	}
426
427	/*
428	** Set the recover handle error to the error code and message returned by
429	** calling sqlite3_errcode() and sqlite3_errmsg(), respectively, on database
430	** handle db.
431	*/
432	static int recoverDbError(sqlite3_recover p, sqlite3 db){
433	return recoverError(p, sqlite3_errcode(db), "%s", sqlite3_errmsg(db));
434	}
435
436	/*
437	** This function is a no-op if recover handle p already contains an error
438	** (if p->errCode!=SQLITE_OK).
439	**
440	** Otherwise, it attempts to prepare the SQL statement in zSql against
441	** database handle db. If successful, the statement handle is returned.
442	** Or, if an error occurs, NULL is returned and an error left in the
443	** recover handle.
444	*/
445	static sqlite3_stmt *recoverPrepare(
446	sqlite3_recover *p,
447	sqlite3 *db,
448	const char *zSql
449	){
450	sqlite3_stmt *pStmt = 0;
451	if( p->errCode==SQLITE_OK ){
452	if( sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0) ){
453	recoverDbError(p, db);
454	}
455	}
456	return pStmt;
457	}
458
459	/*
460	** This function is a no-op if recover handle p already contains an error
461	** (if p->errCode!=SQLITE_OK).
462	**
463	** Otherwise, argument zFmt is used as a printf() style format string,
464	** along with any trailing arguments, to create an SQL statement. This
465	** SQL statement is prepared against database handle db and, if successful,
466	** the statment handle returned. Or, if an error occurs - either during
467	** the printf() formatting or when preparing the resulting SQL - an
468	** error code and message are left in the recover handle.
469	*/
470	static sqlite3_stmt *recoverPreparePrintf(
471	sqlite3_recover *p,
472	sqlite3 *db,
473	const char *zFmt, ...
474	){
475	sqlite3_stmt *pStmt = 0;
476	if( p->errCode==SQLITE_OK ){
477	va_list ap;
478	char *z;
479	va_start(ap, zFmt);
480	z = sqlite3_vmprintf(zFmt, ap);
481	va_end(ap);
482	if( z==0 ){
483	p->errCode = SQLITE_NOMEM;
484	}else{
485	pStmt = recoverPrepare(p, db, z);
486	sqlite3_free(z);
487	}
488	}
489	return pStmt;
490	}
491
492	/*
493	** Reset SQLite statement handle pStmt. If the call to sqlite3_reset()
494	** indicates that an error occurred, and there is not already an error
495	** in the recover handle passed as the first argument, set the error
496	** code and error message appropriately.
497	**
498	** This function returns a copy of the statement handle pointer passed
499	** as the second argument.
500	*/
501	static sqlite3_stmt recoverReset(sqlite3_recover p, sqlite3_stmt *pStmt){
502	int rc = sqlite3_reset(pStmt);
503	if( rc!=SQLITE_OK && rc!=SQLITE_CONSTRAINT && p->errCode==SQLITE_OK ){
504	recoverDbError(p, sqlite3_db_handle(pStmt));
505	}
506	return pStmt;
507	}
508
509	/*
510	** Finalize SQLite statement handle pStmt. If the call to sqlite3_reset()
511	** indicates that an error occurred, and there is not already an error
512	** in the recover handle passed as the first argument, set the error
513	** code and error message appropriately.
514	*/
515	static void recoverFinalize(sqlite3_recover p, sqlite3_stmt pStmt){
516	sqlite3 *db = sqlite3_db_handle(pStmt);
517	int rc = sqlite3_finalize(pStmt);
518	if( rc!=SQLITE_OK && p->errCode==SQLITE_OK ){
519	recoverDbError(p, db);
520	}
521	}
522
523	/*
524	** This function is a no-op if recover handle p already contains an error
525	** (if p->errCode!=SQLITE_OK). A copy of p->errCode is returned in this
526	** case.
527	**
528	** Otherwise, execute SQL script zSql. If successful, return SQLITE_OK.
529	** Or, if an error occurs, leave an error code and message in the recover
530	** handle and return a copy of the error code.
531	*/
532	static int recoverExec(sqlite3_recover p, sqlite3 db, const char *zSql){
533	if( p->errCode==SQLITE_OK ){
534	int rc = sqlite3_exec(db, zSql, 0, 0, 0);
535	if( rc ){
536	recoverDbError(p, db);
537	}
538	}
539	return p->errCode;
540	}
541
542	/*
543	** Bind the value pVal to parameter iBind of statement pStmt. Leave an
544	** error in the recover handle passed as the first argument if an error
545	** (e.g. an OOM) occurs.
546	*/
547	static void recoverBindValue(
548	sqlite3_recover *p,
549	sqlite3_stmt *pStmt,
550	int iBind,
551	sqlite3_value *pVal
552	){
553	if( p->errCode==SQLITE_OK ){
554	int rc = sqlite3_bind_value(pStmt, iBind, pVal);
555	if( rc ) recoverError(p, rc, 0);
556	}
557	}
558
559	/*
560	** This function is a no-op if recover handle p already contains an error
561	** (if p->errCode!=SQLITE_OK). NULL is returned in this case.
562	**
563	** Otherwise, an attempt is made to interpret zFmt as a printf() style
564	** formatting string and the result of using the trailing arguments for
565	** parameter substitution with it written into a buffer obtained from
566	** sqlite3_malloc(). If successful, a pointer to the buffer is returned.
567	** It is the responsibility of the caller to eventually free the buffer
568	** using sqlite3_free().
569	**
570	** Or, if an error occurs, an error code and message is left in the recover
571	** handle and NULL returned.
572	*/
573	static char recoverMPrintf(sqlite3_recover p, const char *zFmt, ...){
574	va_list ap;
575	char *z;
576	va_start(ap, zFmt);
577	z = sqlite3_vmprintf(zFmt, ap);
578	va_end(ap);
579	if( p->errCode==SQLITE_OK ){
580	if( z==0 ) p->errCode = SQLITE_NOMEM;
581	}else{
582	sqlite3_free(z);
583	z = 0;
584	}
585	return z;
586	}
587
588	/*
589	** This function is a no-op if recover handle p already contains an error
590	** (if p->errCode!=SQLITE_OK). Zero is returned in this case.
591	**
592	** Otherwise, execute "PRAGMA page_count" against the input database. If
593	** successful, return the integer result. Or, if an error occurs, leave an
594	** error code and error message in the sqlite3_recover handle and return
595	** zero.
596	*/
597	static i64 recoverPageCount(sqlite3_recover *p){
598	i64 nPg = 0;
599	if( p->errCode==SQLITE_OK ){
600	sqlite3_stmt *pStmt = 0;
601	pStmt = recoverPreparePrintf(p, p->dbIn, "PRAGMA %Q.page_count", p->zDb);
602	if( pStmt ){
603	sqlite3_step(pStmt);
604	nPg = sqlite3_column_int64(pStmt, 0);
605	}
606	recoverFinalize(p, pStmt);
607	}
608	return nPg;
609	}
610
611	/*
612	** Implementation of SQL scalar function "read_i32". The first argument to
613	** this function must be a blob. The second a non-negative integer. This
614	** function reads and returns a 32-bit big-endian integer from byte
615	** offset (4*<arg2>) of the blob.
616	**
617	** SELECT read_i32(<blob>, <idx>)
618	*/
619	static void recoverReadI32(
620	sqlite3_context *context,
621	int argc,
622	sqlite3_value **argv
623	){
624	const unsigned char *pBlob;
625	int nBlob;
626	int iInt;
627
628	assert( argc==2 );
629	nBlob = sqlite3_value_bytes(argv[0]);
630	pBlob = (const unsigned char*)sqlite3_value_blob(argv[0]);
631	iInt = sqlite3_value_int(argv[1]) & 0xFFFF;
632
633	if( (iInt+1)*4<=nBlob ){
634	const unsigned char a = &pBlob[iInt4];
635	i64 iVal = ((i64)a[0]<<24)
636	+ ((i64)a[1]<<16)
637	+ ((i64)a[2]<< 8)
638	+ ((i64)a[3]<< 0);
639	sqlite3_result_int64(context, iVal);
640	}
641	}
642
643	/*
644	** Implementation of SQL scalar function "page_is_used". This function
645	** is used as part of the procedure for locating orphan rows for the
646	** lost-and-found table, and it depends on those routines having populated
647	** the sqlite3_recover.laf.pUsed variable.
648	**
649	** The only argument to this function is a page-number. It returns true
650	** if the page has already been used somehow during data recovery, or false
651	** otherwise.
652	**
653	** SELECT page_is_used(<pgno>);
654	*/
655	static void recoverPageIsUsed(
656	sqlite3_context *pCtx,
657	int nArg,
658	sqlite3_value **apArg
659	){
660	sqlite3_recover p = (sqlite3_recover)sqlite3_user_data(pCtx);
661	i64 pgno = sqlite3_value_int64(apArg[0]);
662	assert( nArg==1 );
663	sqlite3_result_int(pCtx, recoverBitmapQuery(p->laf.pUsed, pgno));
664	}
665
666	/*
667	** The implementation of a user-defined SQL function invoked by the
668	** sqlite_dbdata and sqlite_dbptr virtual table modules to access pages
669	** of the database being recovered.
670	**
671	** This function always takes a single integer argument. If the argument
672	** is zero, then the value returned is the number of pages in the db being
673	** recovered. If the argument is greater than zero, it is a page number.
674	** The value returned in this case is an SQL blob containing the data for
675	** the identified page of the db being recovered. e.g.
676	**
677	** SELECT getpage(0); -- return number of pages in db
678	** SELECT getpage(4); -- return page 4 of db as a blob of data
679	*/
680	static void recoverGetPage(
681	sqlite3_context *pCtx,
682	int nArg,
683	sqlite3_value **apArg
684	){
685	sqlite3_recover p = (sqlite3_recover)sqlite3_user_data(pCtx);
686	i64 pgno = sqlite3_value_int64(apArg[0]);
687	sqlite3_stmt *pStmt = 0;
688
689	assert( nArg==1 );
690	if( pgno==0 ){
691	i64 nPg = recoverPageCount(p);
692	sqlite3_result_int64(pCtx, nPg);
693	return;
694	}else{
695	if( p->pGetPage==0 ){
696	pStmt = p->pGetPage = recoverPreparePrintf(
697	p, p->dbIn, "SELECT data FROM sqlite_dbpage(%Q) WHERE pgno=?", p->zDb
698	);
699	}else if( p->errCode==SQLITE_OK ){
700	pStmt = p->pGetPage;
701	}
702
703	if( pStmt ){
704	sqlite3_bind_int64(pStmt, 1, pgno);
705	if( SQLITE_ROW==sqlite3_step(pStmt) ){
706	const u8 *aPg;
707	int nPg;
708	assert( p->errCode==SQLITE_OK );
709	aPg = sqlite3_column_blob(pStmt, 0);
710	nPg = sqlite3_column_bytes(pStmt, 0);
711	if( pgno==1 && nPg==p->pgsz && 0==memcmp(p->pPage1Cache, aPg, nPg) ){
712	aPg = p->pPage1Disk;
713	}
714	sqlite3_result_blob(pCtx, aPg, nPg-p->nReserve, SQLITE_TRANSIENT);
715	}
716	recoverReset(p, pStmt);
717	}
718	}
719
720	if( p->errCode ){
721	if( p->zErrMsg ) sqlite3_result_error(pCtx, p->zErrMsg, -1);
722	sqlite3_result_error_code(pCtx, p->errCode);
723	}
724	}
725
726	/*
727	** Find a string that is not found anywhere in z[]. Return a pointer
728	** to that string.
729	**
730	** Try to use zA and zB first. If both of those are already found in z[]
731	** then make up some string and store it in the buffer zBuf.
732	*/
733	static const char *recoverUnusedString(
734	const char z, / Result must not appear anywhere in z */
735	const char zA, const char zB, /* Try these first */
736	char zBuf / Space to store a generated string */
737	){
738	unsigned i = 0;
739	if( strstr(z, zA)==0 ) return zA;
740	if( strstr(z, zB)==0 ) return zB;
741	do{
742	sqlite3_snprintf(20,zBuf,"(%s%u)", zA, i++);
743	}while( strstr(z,zBuf)!=0 );
744	return zBuf;
745	}
746
747	/*
748	** Implementation of scalar SQL function "escape_crnl". The argument passed to
749	** this function is the output of built-in function quote(). If the first
750	** character of the input is "'", indicating that the value passed to quote()
751	** was a text value, then this function searches the input for "\n" and "\r"
752	** characters and adds a wrapper similar to the following:
753	**
754	** replace(replace(<input>, '\n', char(10), '\r', char(13));
755	**
756	** Or, if the first character of the input is not "'", then a copy of the input
757	** is returned.
758	*/
759	static void recoverEscapeCrnl(
760	sqlite3_context *context,
761	int argc,
762	sqlite3_value **argv
763	){
764	const char zText = (const char)sqlite3_value_text(argv[0]);
765	(void)argc;
766	if( zText && zText[0]=='\'' ){
767	int nText = sqlite3_value_bytes(argv[0]);
768	int i;
769	char zBuf1[20];
770	char zBuf2[20];
771	const char *zNL = 0;
772	const char *zCR = 0;
773	int nCR = 0;
774	int nNL = 0;
775
776	for(i=0; zText[i]; i++){
777	if( zNL==0 && zText[i]=='\n' ){
778	zNL = recoverUnusedString(zText, "\\n", "\\012", zBuf1);
779	nNL = (int)strlen(zNL);
780	}
781	if( zCR==0 && zText[i]=='\r' ){
782	zCR = recoverUnusedString(zText, "\\r", "\\015", zBuf2);
783	nCR = (int)strlen(zCR);
784	}
785	}
786
787	if( zNL \|\| zCR ){
788	int iOut = 0;
789	i64 nMax = (nNL > nCR) ? nNL : nCR;
790	i64 nAlloc = nMax * nText + (nMax+64)*2;
791	char zOut = (char)sqlite3_malloc64(nAlloc);
792	if( zOut==0 ){
793	sqlite3_result_error_nomem(context);
794	return;
795	}
796
797	if( zNL && zCR ){
798	memcpy(&zOut[iOut], "replace(replace(", 16);
799	iOut += 16;
800	}else{
801	memcpy(&zOut[iOut], "replace(", 8);
802	iOut += 8;
803	}
804	for(i=0; zText[i]; i++){
805	if( zText[i]=='\n' ){
806	memcpy(&zOut[iOut], zNL, nNL);
807	iOut += nNL;
808	}else if( zText[i]=='\r' ){
809	memcpy(&zOut[iOut], zCR, nCR);
810	iOut += nCR;
811	}else{
812	zOut[iOut] = zText[i];
813	iOut++;
814	}
815	}
816
817	if( zNL ){
818	memcpy(&zOut[iOut], ",'", 2); iOut += 2;
819	memcpy(&zOut[iOut], zNL, nNL); iOut += nNL;
820	memcpy(&zOut[iOut], "', char(10))", 12); iOut += 12;
821	}
822	if( zCR ){
823	memcpy(&zOut[iOut], ",'", 2); iOut += 2;
824	memcpy(&zOut[iOut], zCR, nCR); iOut += nCR;
825	memcpy(&zOut[iOut], "', char(13))", 12); iOut += 12;
826	}
827
828	sqlite3_result_text(context, zOut, iOut, SQLITE_TRANSIENT);
829	sqlite3_free(zOut);
830	return;
831	}
832	}
833
834	sqlite3_result_value(context, argv[0]);
835	}
836
837	/*
838	** This function is a no-op if recover handle p already contains an error
839	** (if p->errCode!=SQLITE_OK). A copy of the error code is returned in
840	** this case.
841	**
842	** Otherwise, attempt to populate temporary table "recovery.schema" with the
843	** parts of the database schema that can be extracted from the input database.
844	**
845	** If no error occurs, SQLITE_OK is returned. Otherwise, an error code
846	** and error message are left in the recover handle and a copy of the
847	** error code returned. It is not considered an error if part of all of
848	** the database schema cannot be recovered due to corruption.
849	*/
850	static int recoverCacheSchema(sqlite3_recover *p){
851	return recoverExec(p, p->dbOut,
852	"WITH RECURSIVE pages(p) AS ("
853	" SELECT 1"
854	" UNION"
855	" SELECT child FROM sqlite_dbptr('getpage()'), pages WHERE pgno=p"
856	")"
857	"INSERT INTO recovery.schema SELECT"
858	" max(CASE WHEN field=0 THEN value ELSE NULL END),"
859	" max(CASE WHEN field=1 THEN value ELSE NULL END),"
860	" max(CASE WHEN field=2 THEN value ELSE NULL END),"
861	" max(CASE WHEN field=3 THEN value ELSE NULL END),"
862	" max(CASE WHEN field=4 THEN value ELSE NULL END)"
863	"FROM sqlite_dbdata('getpage()') WHERE pgno IN ("
864	" SELECT p FROM pages"
865	") GROUP BY pgno, cell"
866	);
867	}
868
869	/*
870	** If this recover handle is not in SQL callback mode (i.e. was not created
871	** using sqlite3_recover_init_sql()) of if an error has already occurred,
872	** this function is a no-op. Otherwise, issue a callback with SQL statement
873	** zSql as the parameter.
874	**
875	** If the callback returns non-zero, set the recover handle error code to
876	** the value returned (so that the caller will abandon processing).
877	*/
878	static void recoverSqlCallback(sqlite3_recover p, const char zSql){
879	if( p->errCode==SQLITE_OK && p->xSql ){
880	int res = p->xSql(p->pSqlCtx, zSql);
881	if( res ){
882	recoverError(p, SQLITE_ERROR, "callback returned an error - %d", res);
883	}
884	}
885	}
886
887	/*
888	** Transfer the following settings from the input database to the output
889	** database:
890	**
891	** + page-size,
892	** + auto-vacuum settings,
893	** + database encoding,
894	** + user-version (PRAGMA user_version), and
895	** + application-id (PRAGMA application_id), and
896	*/
897	static void recoverTransferSettings(sqlite3_recover *p){
898	const char *aPragma[] = {
899	"encoding",
900	"page_size",
901	"auto_vacuum",
902	"user_version",
903	"application_id"
904	};
905	int ii;
906
907	/* Truncate the output database to 0 pages in size. This is done by
908	** opening a new, empty, temp db, then using the backup API to clobber
909	** any existing output db with a copy of it. */
910	if( p->errCode==SQLITE_OK ){
911	sqlite3 *db2 = 0;
912	int rc = sqlite3_open("", &db2);
913	if( rc!=SQLITE_OK ){
914	recoverDbError(p, db2);
915	return;
916	}
917
918	for(ii=0; ii<(int)(sizeof(aPragma)/sizeof(aPragma[0])); ii++){
919	const char *zPrag = aPragma[ii];
920	sqlite3_stmt *p1 = 0;
921	p1 = recoverPreparePrintf(p, p->dbIn, "PRAGMA %Q.%s", p->zDb, zPrag);
922	if( p->errCode==SQLITE_OK && sqlite3_step(p1)==SQLITE_ROW ){
923	const char zArg = (const char)sqlite3_column_text(p1, 0);
924	char *z2 = recoverMPrintf(p, "PRAGMA %s = %Q", zPrag, zArg);
925	recoverSqlCallback(p, z2);
926	recoverExec(p, db2, z2);
927	sqlite3_free(z2);
928	if( zArg==0 ){
929	recoverError(p, SQLITE_NOMEM, 0);
930	}
931	}
932	recoverFinalize(p, p1);
933	}
934	recoverExec(p, db2, "CREATE TABLE t1(a); DROP TABLE t1;");
935
936	if( p->errCode==SQLITE_OK ){
937	sqlite3 *db = p->dbOut;
938	sqlite3_backup *pBackup = sqlite3_backup_init(db, "main", db2, "main");
939	if( pBackup ){
940	sqlite3_backup_step(pBackup, -1);
941	p->errCode = sqlite3_backup_finish(pBackup);
942	}else{
943	recoverDbError(p, db);
944	}
945	}
946
947	sqlite3_close(db2);
948	}
949	}
950
951	/*
952	** This function is a no-op if recover handle p already contains an error
953	** (if p->errCode!=SQLITE_OK). A copy of the error code is returned in
954	** this case.
955	**
956	** Otherwise, an attempt is made to open the output database, attach
957	** and create the schema of the temporary database used to store
958	** intermediate data, and to register all required user functions and
959	** virtual table modules with the output handle.
960	**
961	** If no error occurs, SQLITE_OK is returned. Otherwise, an error code
962	** and error message are left in the recover handle and a copy of the
963	** error code returned.
964	*/
965	static int recoverOpenOutput(sqlite3_recover *p){
966	struct Func {
967	const char *zName;
968	int nArg;
969	void (xFunc)(sqlite3_context,int,sqlite3_value **);
970	} aFunc[] = {
971	{ "getpage", 1, recoverGetPage },
972	{ "page_is_used", 1, recoverPageIsUsed },
973	{ "read_i32", 2, recoverReadI32 },
974	{ "escape_crnl", 1, recoverEscapeCrnl },
975	};
976
977	const int flags = SQLITE_OPEN_URI\|SQLITE_OPEN_CREATE\|SQLITE_OPEN_READWRITE;
978	sqlite3 db = 0; / New database handle */
979	int ii; /* For iterating through aFunc[] */
980
981	assert( p->dbOut==0 );
982
983	if( sqlite3_open_v2(p->zUri, &db, flags, 0) ){
984	recoverDbError(p, db);
985	}
986
987	/* Register the sqlite_dbdata and sqlite_dbptr virtual table modules.
988	** These two are registered with the output database handle - this
989	** module depends on the input handle supporting the sqlite_dbpage
990	** virtual table only. */
991	if( p->errCode==SQLITE_OK ){
992	p->errCode = sqlite3_dbdata_init(db, 0, 0);
993	}
994
995	/* Register the custom user-functions with the output handle. */
996	for(ii=0;
997	p->errCode==SQLITE_OK && ii<(int)(sizeof(aFunc)/sizeof(aFunc[0]));
998	ii++){
999	p->errCode = sqlite3_create_function(db, aFunc[ii].zName,
1000	aFunc[ii].nArg, SQLITE_UTF8, (void*)p, aFunc[ii].xFunc, 0, 0
1001	);
1002	}
1003
1004	p->dbOut = db;
1005	return p->errCode;
1006	}
1007
1008	/*
1009	** Attach the auxiliary database 'recovery' to the output database handle.
1010	** This temporary database is used during the recovery process and then
1011	** discarded.
1012	*/
1013	static void recoverOpenRecovery(sqlite3_recover *p){
1014	char *zSql = recoverMPrintf(p, "ATTACH %Q AS recovery;", p->zStateDb);
1015	recoverExec(p, p->dbOut, zSql);
1016	recoverExec(p, p->dbOut,
1017	"PRAGMA writable_schema = 1;"
1018	"CREATE TABLE recovery.map(pgno INTEGER PRIMARY KEY, parent INT);"
1019	"CREATE TABLE recovery.schema(type, name, tbl_name, rootpage, sql);"
1020	);
1021	sqlite3_free(zSql);
1022	}
1023
1024
1025	/*
1026	** This function is a no-op if recover handle p already contains an error
1027	** (if p->errCode!=SQLITE_OK).
1028	**
1029	** Otherwise, argument zName must be the name of a table that has just been
1030	** created in the output database. This function queries the output db
1031	** for the schema of said table, and creates a RecoverTable object to
1032	** store the schema in memory. The new RecoverTable object is linked into
1033	** the list at sqlite3_recover.pTblList.
1034	**
1035	** Parameter iRoot must be the root page of table zName in the INPUT
1036	** database.
1037	*/
1038	static void recoverAddTable(
1039	sqlite3_recover *p,
1040	const char zName, / Name of table created in output db */
1041	i64 iRoot /* Root page of same table in INPUT db */
1042	){
1043	sqlite3_stmt *pStmt = recoverPreparePrintf(p, p->dbOut,
1044	"PRAGMA table_xinfo(%Q)", zName
1045	);
1046
1047	if( pStmt ){
1048	int iPk = -1;
1049	int iBind = 1;
1050	RecoverTable *pNew = 0;
1051	int nCol = 0;
1052	int nName = recoverStrlen(zName);
1053	int nByte = 0;
1054	while( sqlite3_step(pStmt)==SQLITE_ROW ){
1055	nCol++;
1056	nByte += (sqlite3_column_bytes(pStmt, 1)+1);
1057	}
1058	nByte += sizeof(RecoverTable) + nCol*sizeof(RecoverColumn) + nName+1;
1059	recoverReset(p, pStmt);
1060
1061	pNew = recoverMalloc(p, nByte);
1062	if( pNew ){
1063	int i = 0;
1064	int iField = 0;
1065	char *csr = 0;
1066	pNew->aCol = (RecoverColumn*)&pNew[1];
1067	pNew->zTab = csr = (char*)&pNew->aCol[nCol];
1068	pNew->nCol = nCol;
1069	pNew->iRoot = iRoot;
1070	memcpy(csr, zName, nName);
1071	csr += nName+1;
1072
1073	for(i=0; sqlite3_step(pStmt)==SQLITE_ROW; i++){
1074	int iPKF = sqlite3_column_int(pStmt, 5);
1075	int n = sqlite3_column_bytes(pStmt, 1);
1076	const char z = (const char)sqlite3_column_text(pStmt, 1);
1077	const char zType = (const char)sqlite3_column_text(pStmt, 2);
1078	int eHidden = sqlite3_column_int(pStmt, 6);
1079
1080	if( iPk==-1 && iPKF==1 && !sqlite3_stricmp("integer", zType) ) iPk = i;
1081	if( iPKF>1 ) iPk = -2;
1082	pNew->aCol[i].zCol = csr;
1083	pNew->aCol[i].eHidden = eHidden;
1084	if( eHidden==RECOVER_EHIDDEN_VIRTUAL ){
1085	pNew->aCol[i].iField = -1;
1086	}else{
1087	pNew->aCol[i].iField = iField++;
1088	}
1089	if( eHidden!=RECOVER_EHIDDEN_VIRTUAL
1090	&& eHidden!=RECOVER_EHIDDEN_STORED
1091	){
1092	pNew->aCol[i].iBind = iBind++;
1093	}
1094	memcpy(csr, z, n);
1095	csr += (n+1);
1096	}
1097
1098	pNew->pNext = p->pTblList;
1099	p->pTblList = pNew;
1100	pNew->bIntkey = 1;
1101	}
1102
1103	recoverFinalize(p, pStmt);
1104
1105	pStmt = recoverPreparePrintf(p, p->dbOut, "PRAGMA index_xinfo(%Q)", zName);
1106	while( pStmt && sqlite3_step(pStmt)==SQLITE_ROW ){
1107	int iField = sqlite3_column_int(pStmt, 0);
1108	int iCol = sqlite3_column_int(pStmt, 1);
1109
1110	assert( iCol<pNew->nCol );
1111	pNew->aCol[iCol].iField = iField;
1112
1113	pNew->bIntkey = 0;
1114	iPk = -2;
1115	}
1116	recoverFinalize(p, pStmt);
1117
1118	if( p->errCode==SQLITE_OK ){
1119	if( iPk>=0 ){
1120	pNew->aCol[iPk].bIPK = 1;
1121	}else if( pNew->bIntkey ){
1122	pNew->iRowidBind = iBind++;
1123	}
1124	}
1125	}
1126	}
1127
1128	/*
1129	** This function is called after recoverCacheSchema() has cached those parts
1130	** of the input database schema that could be recovered in temporary table
1131	** "recovery.schema". This function creates in the output database copies
1132	** of all parts of that schema that must be created before the tables can
1133	** be populated. Specifically, this means:
1134	**
1135	** * all tables that are not VIRTUAL, and
1136	** * UNIQUE indexes.
1137	**
1138	** If the recovery handle uses SQL callbacks, then callbacks containing
1139	** the associated "CREATE TABLE" and "CREATE INDEX" statements are made.
1140	**
1141	** Additionally, records are added to the sqlite_schema table of the
1142	** output database for any VIRTUAL tables. The CREATE VIRTUAL TABLE
1143	** records are written directly to sqlite_schema, not actually executed.
1144	** If the handle is in SQL callback mode, then callbacks are invoked
1145	** with equivalent SQL statements.
1146	*/
1147	static int recoverWriteSchema1(sqlite3_recover *p){
1148	sqlite3_stmt *pSelect = 0;
1149	sqlite3_stmt *pTblname = 0;
1150
1151	pSelect = recoverPrepare(p, p->dbOut,
1152	"WITH dbschema(rootpage, name, sql, tbl, isVirtual, isIndex) AS ("
1153	" SELECT rootpage, name, sql, "
1154	" type='table', "
1155	" sql LIKE 'create virtual%',"
1156	" (type='index' AND (sql LIKE '%unique%' OR ?1))"
1157	" FROM recovery.schema"
1158	")"
1159	"SELECT rootpage, tbl, isVirtual, name, sql"
1160	" FROM dbschema "
1161	" WHERE tbl OR isIndex"
1162	" ORDER BY tbl DESC, name=='sqlite_sequence' DESC"
1163	);
1164
1165	pTblname = recoverPrepare(p, p->dbOut,
1166	"SELECT name FROM sqlite_schema "
1167	"WHERE type='table' ORDER BY rowid DESC LIMIT 1"
1168	);
1169
1170	if( pSelect ){
1171	sqlite3_bind_int(pSelect, 1, p->bSlowIndexes);
1172	while( sqlite3_step(pSelect)==SQLITE_ROW ){
1173	i64 iRoot = sqlite3_column_int64(pSelect, 0);
1174	int bTable = sqlite3_column_int(pSelect, 1);
1175	int bVirtual = sqlite3_column_int(pSelect, 2);
1176	const char zName = (const char)sqlite3_column_text(pSelect, 3);
1177	const char zSql = (const char)sqlite3_column_text(pSelect, 4);
1178	char *zFree = 0;
1179	int rc = SQLITE_OK;
1180
1181	if( bVirtual ){
1182	zSql = (const char*)(zFree = recoverMPrintf(p,
1183	"INSERT INTO sqlite_schema VALUES('table', %Q, %Q, 0, %Q)",
1184	zName, zName, zSql
1185	));
1186	}
1187	rc = sqlite3_exec(p->dbOut, zSql, 0, 0, 0);
1188	if( rc==SQLITE_OK ){
1189	recoverSqlCallback(p, zSql);
1190	if( bTable && !bVirtual ){
1191	if( SQLITE_ROW==sqlite3_step(pTblname) ){
1192	const char zTbl = (const char)sqlite3_column_text(pTblname, 0);
1193	if( zTbl ) recoverAddTable(p, zTbl, iRoot);
1194	}
1195	recoverReset(p, pTblname);
1196	}
1197	}else if( rc!=SQLITE_ERROR ){
1198	recoverDbError(p, p->dbOut);
1199	}
1200	sqlite3_free(zFree);
1201	}
1202	}
1203	recoverFinalize(p, pSelect);
1204	recoverFinalize(p, pTblname);
1205
1206	return p->errCode;
1207	}
1208
1209	/*
1210	** This function is called after the output database has been populated. It
1211	** adds all recovered schema elements that were not created in the output
1212	** database by recoverWriteSchema1() - everything except for tables and
1213	** UNIQUE indexes. Specifically:
1214	**
1215	** * views,
1216	** * triggers,
1217	** * non-UNIQUE indexes.
1218	**
1219	** If the recover handle is in SQL callback mode, then equivalent callbacks
1220	** are issued to create the schema elements.
1221	*/
1222	static int recoverWriteSchema2(sqlite3_recover *p){
1223	sqlite3_stmt *pSelect = 0;
1224
1225	pSelect = recoverPrepare(p, p->dbOut,
1226	p->bSlowIndexes ?
1227	"SELECT rootpage, sql FROM recovery.schema "
1228	" WHERE type!='table' AND type!='index'"
1229	:
1230	"SELECT rootpage, sql FROM recovery.schema "
1231	" WHERE type!='table' AND (type!='index' OR sql NOT LIKE '%unique%')"
1232	);
1233
1234	if( pSelect ){
1235	while( sqlite3_step(pSelect)==SQLITE_ROW ){
1236	const char zSql = (const char)sqlite3_column_text(pSelect, 1);
1237	int rc = sqlite3_exec(p->dbOut, zSql, 0, 0, 0);
1238	if( rc==SQLITE_OK ){
1239	recoverSqlCallback(p, zSql);
1240	}else if( rc!=SQLITE_ERROR ){
1241	recoverDbError(p, p->dbOut);
1242	}
1243	}
1244	}
1245	recoverFinalize(p, pSelect);
1246
1247	return p->errCode;
1248	}
1249
1250	/*
1251	** This function is a no-op if recover handle p already contains an error
1252	** (if p->errCode!=SQLITE_OK). In this case it returns NULL.
1253	**
1254	** Otherwise, if the recover handle is configured to create an output
1255	** database (was created by sqlite3_recover_init()), then this function
1256	** prepares and returns an SQL statement to INSERT a new record into table
1257	** pTab, assuming the first nField fields of a record extracted from disk
1258	** are valid.
1259	**
1260	** For example, if table pTab is:
1261	**
1262	** CREATE TABLE name(a, b GENERATED ALWAYS AS (a+1) STORED, c, d, e);
1263	**
1264	** And nField is 4, then the SQL statement prepared and returned is:
1265	**
1266	** INSERT INTO (a, c, d) VALUES (?1, ?2, ?3);
1267	**
1268	** In this case even though 4 values were extracted from the input db,
1269	** only 3 are written to the output, as the generated STORED column
1270	** cannot be written.
1271	**
1272	** If the recover handle is in SQL callback mode, then the SQL statement
1273	** prepared is such that evaluating it returns a single row containing
1274	** a single text value - itself an SQL statement similar to the above,
1275	** except with SQL literals in place of the variables. For example:
1276	**
1277	** SELECT 'INSERT INTO (a, c, d) VALUES ('
1278	** \|\| quote(?1) \|\| ', '
1279	** \|\| quote(?2) \|\| ', '
1280	** \|\| quote(?3) \|\| ')';
1281	**
1282	** In either case, it is the responsibility of the caller to eventually
1283	** free the statement handle using sqlite3_finalize().
1284	*/
1285	static sqlite3_stmt *recoverInsertStmt(
1286	sqlite3_recover *p,
1287	RecoverTable *pTab,
1288	int nField
1289	){
1290	sqlite3_stmt *pRet = 0;
1291	const char *zSep = "";
1292	const char *zSqlSep = "";
1293	char *zSql = 0;
1294	char *zFinal = 0;
1295	char *zBind = 0;
1296	int ii;
1297	int bSql = p->xSql ? 1 : 0;
1298
1299	if( nField<=0 ) return 0;
1300
1301	assert( nField<=pTab->nCol );
1302
1303	zSql = recoverMPrintf(p, "INSERT OR IGNORE INTO %Q(", pTab->zTab);
1304
1305	if( pTab->iRowidBind ){
1306	assert( pTab->bIntkey );
1307	zSql = recoverMPrintf(p, "%z_rowid_", zSql);
1308	if( bSql ){
1309	zBind = recoverMPrintf(p, "%zquote(?%d)", zBind, pTab->iRowidBind);
1310	}else{
1311	zBind = recoverMPrintf(p, "%z?%d", zBind, pTab->iRowidBind);
1312	}
1313	zSqlSep = "\|\|', '\|\|";
1314	zSep = ", ";
1315	}
1316
1317	for(ii=0; ii<nField; ii++){
1318	int eHidden = pTab->aCol[ii].eHidden;
1319	if( eHidden!=RECOVER_EHIDDEN_VIRTUAL
1320	&& eHidden!=RECOVER_EHIDDEN_STORED
1321	){
1322	assert( pTab->aCol[ii].iField>=0 && pTab->aCol[ii].iBind>=1 );
1323	zSql = recoverMPrintf(p, "%z%s%Q", zSql, zSep, pTab->aCol[ii].zCol);
1324
1325	if( bSql ){
1326	zBind = recoverMPrintf(p,
1327	"%z%sescape_crnl(quote(?%d))", zBind, zSqlSep, pTab->aCol[ii].iBind
1328	);
1329	zSqlSep = "\|\|', '\|\|";
1330	}else{
1331	zBind = recoverMPrintf(p, "%z%s?%d", zBind, zSep, pTab->aCol[ii].iBind);
1332	}
1333	zSep = ", ";
1334	}
1335	}
1336
1337	if( bSql ){
1338	zFinal = recoverMPrintf(p, "SELECT %Q \|\| ') VALUES (' \|\| %s \|\| ')'",
1339	zSql, zBind
1340	);
1341	}else{
1342	zFinal = recoverMPrintf(p, "%s) VALUES (%s)", zSql, zBind);
1343	}
1344
1345	pRet = recoverPrepare(p, p->dbOut, zFinal);
1346	sqlite3_free(zSql);
1347	sqlite3_free(zBind);
1348	sqlite3_free(zFinal);
1349
1350	return pRet;
1351	}
1352
1353
1354	/*
1355	** Search the list of RecoverTable objects at p->pTblList for one that
1356	** has root page iRoot in the input database. If such an object is found,
1357	** return a pointer to it. Otherwise, return NULL.
1358	*/
1359	static RecoverTable recoverFindTable(sqlite3_recover p, u32 iRoot){
1360	RecoverTable *pRet = 0;
1361	for(pRet=p->pTblList; pRet && pRet->iRoot!=iRoot; pRet=pRet->pNext);
1362	return pRet;
1363	}
1364
1365	/*
1366	** This function attempts to create a lost and found table within the
1367	** output db. If successful, it returns a pointer to a buffer containing
1368	** the name of the new table. It is the responsibility of the caller to
1369	** eventually free this buffer using sqlite3_free().
1370	**
1371	** If an error occurs, NULL is returned and an error code and error
1372	** message left in the recover handle.
1373	*/
1374	static char *recoverLostAndFoundCreate(
1375	sqlite3_recover p, / Recover object */
1376	int nField /* Number of column fields in new table */
1377	){
1378	char *zTbl = 0;
1379	sqlite3_stmt *pProbe = 0;
1380	int ii = 0;
1381
1382	pProbe = recoverPrepare(p, p->dbOut,
1383	"SELECT 1 FROM sqlite_schema WHERE name=?"
1384	);
1385	for(ii=-1; zTbl==0 && p->errCode==SQLITE_OK && ii<1000; ii++){
1386	int bFail = 0;
1387	if( ii<0 ){
1388	zTbl = recoverMPrintf(p, "%s", p->zLostAndFound);
1389	}else{
1390	zTbl = recoverMPrintf(p, "%s_%d", p->zLostAndFound, ii);
1391	}
1392
1393	if( p->errCode==SQLITE_OK ){
1394	sqlite3_bind_text(pProbe, 1, zTbl, -1, SQLITE_STATIC);
1395	if( SQLITE_ROW==sqlite3_step(pProbe) ){
1396	bFail = 1;
1397	}
1398	recoverReset(p, pProbe);
1399	}
1400
1401	if( bFail ){
1402	sqlite3_clear_bindings(pProbe);
1403	sqlite3_free(zTbl);
1404	zTbl = 0;
1405	}
1406	}
1407	recoverFinalize(p, pProbe);
1408
1409	if( zTbl ){
1410	const char *zSep = 0;
1411	char *zField = 0;
1412	char *zSql = 0;
1413
1414	zSep = "rootpgno INTEGER, pgno INTEGER, nfield INTEGER, id INTEGER, ";
1415	for(ii=0; p->errCode==SQLITE_OK && ii<nField; ii++){
1416	zField = recoverMPrintf(p, "%z%sc%d", zField, zSep, ii);
1417	zSep = ", ";
1418	}
1419
1420	zSql = recoverMPrintf(p, "CREATE TABLE %s(%s)", zTbl, zField);
1421	sqlite3_free(zField);
1422
1423	recoverExec(p, p->dbOut, zSql);
1424	recoverSqlCallback(p, zSql);
1425	sqlite3_free(zSql);
1426	}else if( p->errCode==SQLITE_OK ){
1427	recoverError(
1428	p, SQLITE_ERROR, "failed to create %s output table", p->zLostAndFound
1429	);
1430	}
1431
1432	return zTbl;
1433	}
1434
1435	/*
1436	** Synthesize and prepare an INSERT statement to write to the lost_and_found
1437	** table in the output database. The name of the table is zTab, and it has
1438	** nField c* fields.
1439	*/
1440	static sqlite3_stmt *recoverLostAndFoundInsert(
1441	sqlite3_recover *p,
1442	const char *zTab,
1443	int nField
1444	){
1445	int nTotal = nField + 4;
1446	int ii;
1447	char *zBind = 0;
1448	sqlite3_stmt *pRet = 0;
1449
1450	if( p->xSql==0 ){
1451	for(ii=0; ii<nTotal; ii++){
1452	zBind = recoverMPrintf(p, "%z%s?", zBind, zBind?", ":"", ii);
1453	}
1454	pRet = recoverPreparePrintf(
1455	p, p->dbOut, "INSERT INTO %s VALUES(%s)", zTab, zBind
1456	);
1457	}else{
1458	const char *zSep = "";
1459	for(ii=0; ii<nTotal; ii++){
1460	zBind = recoverMPrintf(p, "%z%squote(?)", zBind, zSep);
1461	zSep = "\|\| ', ' \|\|";
1462	}
1463	pRet = recoverPreparePrintf(
1464	p, p->dbOut, "SELECT 'INSERT INTO %s VALUES(' \|\| %s \|\| ')'", zTab, zBind
1465	);
1466	}
1467
1468	sqlite3_free(zBind);
1469	return pRet;
1470	}
1471
1472	/*
1473	** Input database page iPg contains data that will be written to the
1474	** lost-and-found table of the output database. This function attempts
1475	** to identify the root page of the tree that page iPg belonged to.
1476	** If successful, it sets output variable (*piRoot) to the page number
1477	** of the root page and returns SQLITE_OK. Otherwise, if an error occurs,
1478	** an SQLite error code is returned and the final value of *piRoot
1479	** undefined.
1480	*/
1481	static int recoverLostAndFoundFindRoot(
1482	sqlite3_recover *p,
1483	i64 iPg,
1484	i64 *piRoot
1485	){
1486	RecoverStateLAF *pLaf = &p->laf;
1487
1488	if( pLaf->pFindRoot==0 ){
1489	pLaf->pFindRoot = recoverPrepare(p, p->dbOut,
1490	"WITH RECURSIVE p(pgno) AS ("
1491	" SELECT ?"
1492	" UNION"
1493	" SELECT parent FROM recovery.map AS m, p WHERE m.pgno=p.pgno"
1494	") "
1495	"SELECT p.pgno FROM p, recovery.map m WHERE m.pgno=p.pgno "
1496	" AND m.parent IS NULL"
1497	);
1498	}
1499	if( p->errCode==SQLITE_OK ){
1500	sqlite3_bind_int64(pLaf->pFindRoot, 1, iPg);
1501	if( sqlite3_step(pLaf->pFindRoot)==SQLITE_ROW ){
1502	*piRoot = sqlite3_column_int64(pLaf->pFindRoot, 0);
1503	}else{
1504	*piRoot = iPg;
1505	}
1506	recoverReset(p, pLaf->pFindRoot);
1507	}
1508	return p->errCode;
1509	}
1510
1511	/*
1512	** Recover data from page iPage of the input database and write it to
1513	** the lost-and-found table in the output database.
1514	*/
1515	static void recoverLostAndFoundOnePage(sqlite3_recover *p, i64 iPage){
1516	RecoverStateLAF *pLaf = &p->laf;
1517	sqlite3_value **apVal = pLaf->apVal;
1518	sqlite3_stmt *pPageData = pLaf->pPageData;
1519	sqlite3_stmt *pInsert = pLaf->pInsert;
1520
1521	int nVal = -1;
1522	int iPrevCell = 0;
1523	i64 iRoot = 0;
1524	int bHaveRowid = 0;
1525	i64 iRowid = 0;
1526	int ii = 0;
1527
1528	if( recoverLostAndFoundFindRoot(p, iPage, &iRoot) ) return;
1529	sqlite3_bind_int64(pPageData, 1, iPage);
1530	while( p->errCode==SQLITE_OK && SQLITE_ROW==sqlite3_step(pPageData) ){
1531	int iCell = sqlite3_column_int64(pPageData, 0);
1532	int iField = sqlite3_column_int64(pPageData, 1);
1533
1534	if( iPrevCell!=iCell && nVal>=0 ){
1535	/* Insert the new row */
1536	sqlite3_bind_int64(pInsert, 1, iRoot); /* rootpgno */
1537	sqlite3_bind_int64(pInsert, 2, iPage); /* pgno */
1538	sqlite3_bind_int(pInsert, 3, nVal); /* nfield */
1539	if( bHaveRowid ){
1540	sqlite3_bind_int64(pInsert, 4, iRowid); /* id */
1541	}
1542	for(ii=0; ii<nVal; ii++){
1543	recoverBindValue(p, pInsert, 5+ii, apVal[ii]);
1544	}
1545	if( sqlite3_step(pInsert)==SQLITE_ROW ){
1546	recoverSqlCallback(p, (const char*)sqlite3_column_text(pInsert, 0));
1547	}
1548	recoverReset(p, pInsert);
1549
1550	/* Discard the accumulated row data */
1551	for(ii=0; ii<nVal; ii++){
1552	sqlite3_value_free(apVal[ii]);
1553	apVal[ii] = 0;
1554	}
1555	sqlite3_clear_bindings(pInsert);
1556	bHaveRowid = 0;
1557	nVal = -1;
1558	}
1559
1560	if( iCell<0 ) break;
1561
1562	if( iField<0 ){
1563	assert( nVal==-1 );
1564	iRowid = sqlite3_column_int64(pPageData, 2);
1565	bHaveRowid = 1;
1566	nVal = 0;
1567	}else if( iField<pLaf->nMaxField ){
1568	sqlite3_value *pVal = sqlite3_column_value(pPageData, 2);
1569	apVal[iField] = sqlite3_value_dup(pVal);
1570	assert( iField==nVal \|\| (nVal==-1 && iField==0) );
1571	nVal = iField+1;
1572	if( apVal[iField]==0 ){
1573	recoverError(p, SQLITE_NOMEM, 0);
1574	}
1575	}
1576
1577	iPrevCell = iCell;
1578	}
1579	recoverReset(p, pPageData);
1580
1581	for(ii=0; ii<nVal; ii++){
1582	sqlite3_value_free(apVal[ii]);
1583	apVal[ii] = 0;
1584	}
1585	}
1586
1587	/*
1588	** Perform one step (sqlite3_recover_step()) of work for the connection
1589	** passed as the only argument, which is guaranteed to be in
1590	** RECOVER_STATE_LOSTANDFOUND3 state - during which the lost-and-found
1591	** table of the output database is populated with recovered data that can
1592	** not be assigned to any recovered schema object.
1593	*/
1594	static int recoverLostAndFound3Step(sqlite3_recover *p){
1595	RecoverStateLAF *pLaf = &p->laf;
1596	if( p->errCode==SQLITE_OK ){
1597	if( pLaf->pInsert==0 ){
1598	return SQLITE_DONE;
1599	}else{
1600	if( p->errCode==SQLITE_OK ){
1601	int res = sqlite3_step(pLaf->pAllPage);
1602	if( res==SQLITE_ROW ){
1603	i64 iPage = sqlite3_column_int64(pLaf->pAllPage, 0);
1604	if( recoverBitmapQuery(pLaf->pUsed, iPage)==0 ){
1605	recoverLostAndFoundOnePage(p, iPage);
1606	}
1607	}else{
1608	recoverReset(p, pLaf->pAllPage);
1609	return SQLITE_DONE;
1610	}
1611	}
1612	}
1613	}
1614	return SQLITE_OK;
1615	}
1616
1617	/*
1618	** Initialize resources required in RECOVER_STATE_LOSTANDFOUND3
1619	** state - during which the lost-and-found table of the output database
1620	** is populated with recovered data that can not be assigned to any
1621	** recovered schema object.
1622	*/
1623	static void recoverLostAndFound3Init(sqlite3_recover *p){
1624	RecoverStateLAF *pLaf = &p->laf;
1625
1626	if( pLaf->nMaxField>0 ){
1627	char zTab = 0; / Name of lost_and_found table */
1628
1629	zTab = recoverLostAndFoundCreate(p, pLaf->nMaxField);
1630	pLaf->pInsert = recoverLostAndFoundInsert(p, zTab, pLaf->nMaxField);
1631	sqlite3_free(zTab);
1632
1633	pLaf->pAllPage = recoverPreparePrintf(p, p->dbOut,
1634	"WITH RECURSIVE seq(ii) AS ("
1635	" SELECT 1 UNION ALL SELECT ii+1 FROM seq WHERE ii<%lld"
1636	")"
1637	"SELECT ii FROM seq" , p->laf.nPg
1638	);
1639	pLaf->pPageData = recoverPrepare(p, p->dbOut,
1640	"SELECT cell, field, value "
1641	"FROM sqlite_dbdata('getpage()') d WHERE d.pgno=? "
1642	"UNION ALL "
1643	"SELECT -1, -1, -1"
1644	);
1645
1646	pLaf->apVal = (sqlite3_value**)recoverMalloc(p,
1647	pLaf->nMaxFieldsizeof(sqlite3_value)
1648	);
1649	}
1650	}
1651
1652	/*
1653	** Initialize resources required in RECOVER_STATE_WRITING state - during which
1654	** tables recovered from the schema of the input database are populated with
1655	** recovered data.
1656	*/
1657	static int recoverWriteDataInit(sqlite3_recover *p){
1658	RecoverStateW1 *p1 = &p->w1;
1659	RecoverTable *pTbl = 0;
1660	int nByte = 0;
1661
1662	/* Figure out the maximum number of columns for any table in the schema */
1663	assert( p1->nMax==0 );
1664	for(pTbl=p->pTblList; pTbl; pTbl=pTbl->pNext){
1665	if( pTbl->nCol>p1->nMax ) p1->nMax = pTbl->nCol;
1666	}
1667
1668	/* Allocate an array of (sqlite3_value*) in which to accumulate the values
1669	** that will be written to the output database in a single row. */
1670	nByte = sizeof(sqlite3_value) (p1->nMax+1);
1671	p1->apVal = (sqlite3_value**)recoverMalloc(p, nByte);
1672	if( p1->apVal==0 ) return p->errCode;
1673
1674	/* Prepare the SELECT to loop through schema tables (pTbls) and the SELECT
1675	** to loop through cells that appear to belong to a single table (pSel). */
1676	p1->pTbls = recoverPrepare(p, p->dbOut,
1677	"SELECT rootpage FROM recovery.schema "
1678	" WHERE type='table' AND (sql NOT LIKE 'create virtual%')"
1679	" ORDER BY (tbl_name='sqlite_sequence') ASC"
1680	);
1681	p1->pSel = recoverPrepare(p, p->dbOut,
1682	"WITH RECURSIVE pages(page) AS ("
1683	" SELECT ?1"
1684	" UNION"
1685	" SELECT child FROM sqlite_dbptr('getpage()'), pages "
1686	" WHERE pgno=page"
1687	") "
1688	"SELECT page, cell, field, value "
1689	"FROM sqlite_dbdata('getpage()') d, pages p WHERE p.page=d.pgno "
1690	"UNION ALL "
1691	"SELECT 0, 0, 0, 0"
1692	);
1693
1694	return p->errCode;
1695	}
1696
1697	/*
1698	** Clean up resources allocated by recoverWriteDataInit() (stuff in
1699	** sqlite3_recover.w1).
1700	*/
1701	static void recoverWriteDataCleanup(sqlite3_recover *p){
1702	RecoverStateW1 *p1 = &p->w1;
1703	int ii;
1704	for(ii=0; ii<p1->nVal; ii++){
1705	sqlite3_value_free(p1->apVal[ii]);
1706	}
1707	sqlite3_free(p1->apVal);
1708	recoverFinalize(p, p1->pInsert);
1709	recoverFinalize(p, p1->pTbls);
1710	recoverFinalize(p, p1->pSel);
1711	memset(p1, 0, sizeof(*p1));
1712	}
1713
1714	/*
1715	** Perform one step (sqlite3_recover_step()) of work for the connection
1716	** passed as the only argument, which is guaranteed to be in
1717	** RECOVER_STATE_WRITING state - during which tables recovered from the
1718	** schema of the input database are populated with recovered data.
1719	*/
1720	static int recoverWriteDataStep(sqlite3_recover *p){
1721	RecoverStateW1 *p1 = &p->w1;
1722	sqlite3_stmt *pSel = p1->pSel;
1723	sqlite3_value **apVal = p1->apVal;
1724
1725	if( p->errCode==SQLITE_OK && p1->pTab==0 ){
1726	if( sqlite3_step(p1->pTbls)==SQLITE_ROW ){
1727	i64 iRoot = sqlite3_column_int64(p1->pTbls, 0);
1728	p1->pTab = recoverFindTable(p, iRoot);
1729
1730	recoverFinalize(p, p1->pInsert);
1731	p1->pInsert = 0;
1732
1733	/* If this table is unknown, return early. The caller will invoke this
1734	** function again and it will move on to the next table. */
1735	if( p1->pTab==0 ) return p->errCode;
1736
1737	/* If this is the sqlite_sequence table, delete any rows added by
1738	** earlier INSERT statements on tables with AUTOINCREMENT primary
1739	** keys before recovering its contents. The p1->pTbls SELECT statement
1740	** is rigged to deliver "sqlite_sequence" last of all, so we don't
1741	** worry about it being modified after it is recovered. */
1742	if( sqlite3_stricmp("sqlite_sequence", p1->pTab->zTab)==0 ){
1743	recoverExec(p, p->dbOut, "DELETE FROM sqlite_sequence");
1744	recoverSqlCallback(p, "DELETE FROM sqlite_sequence");
1745	}
1746
1747	/* Bind the root page of this table within the original database to
1748	** SELECT statement p1->pSel. The SELECT statement will then iterate
1749	** through cells that look like they belong to table pTab. */
1750	sqlite3_bind_int64(pSel, 1, iRoot);
1751
1752	p1->nVal = 0;
1753	p1->bHaveRowid = 0;
1754	p1->iPrevPage = -1;
1755	p1->iPrevCell = -1;
1756	}else{
1757	return SQLITE_DONE;
1758	}
1759	}
1760	assert( p->errCode!=SQLITE_OK \|\| p1->pTab );
1761
1762	if( p->errCode==SQLITE_OK && sqlite3_step(pSel)==SQLITE_ROW ){
1763	RecoverTable *pTab = p1->pTab;
1764
1765	i64 iPage = sqlite3_column_int64(pSel, 0);
1766	int iCell = sqlite3_column_int(pSel, 1);
1767	int iField = sqlite3_column_int(pSel, 2);
1768	sqlite3_value *pVal = sqlite3_column_value(pSel, 3);
1769	int bNewCell = (p1->iPrevPage!=iPage \|\| p1->iPrevCell!=iCell);
1770
1771	assert( bNewCell==0 \|\| (iField==-1 \|\| iField==0) );
1772	assert( bNewCell \|\| iField==p1->nVal \|\| p1->nVal==pTab->nCol );
1773
1774	if( bNewCell ){
1775	int ii = 0;
1776	if( p1->nVal>=0 ){
1777	if( p1->pInsert==0 \|\| p1->nVal!=p1->nInsert ){
1778	recoverFinalize(p, p1->pInsert);
1779	p1->pInsert = recoverInsertStmt(p, pTab, p1->nVal);
1780	p1->nInsert = p1->nVal;
1781	}
1782	if( p1->nVal>0 ){
1783	sqlite3_stmt *pInsert = p1->pInsert;
1784	for(ii=0; ii<pTab->nCol; ii++){
1785	RecoverColumn *pCol = &pTab->aCol[ii];
1786	int iBind = pCol->iBind;
1787	if( iBind>0 ){
1788	if( pCol->bIPK ){
1789	sqlite3_bind_int64(pInsert, iBind, p1->iRowid);
1790	}else if( pCol->iField<p1->nVal ){
1791	recoverBindValue(p, pInsert, iBind, apVal[pCol->iField]);
1792	}
1793	}
1794	}
1795	if( p->bRecoverRowid && pTab->iRowidBind>0 && p1->bHaveRowid ){
1796	sqlite3_bind_int64(pInsert, pTab->iRowidBind, p1->iRowid);
1797	}
1798	if( SQLITE_ROW==sqlite3_step(pInsert) ){
1799	const char z = (const char)sqlite3_column_text(pInsert, 0);
1800	recoverSqlCallback(p, z);
1801	}
1802	recoverReset(p, pInsert);
1803	assert( p->errCode \|\| pInsert );
1804	if( pInsert ) sqlite3_clear_bindings(pInsert);
1805	}
1806	}
1807
1808	for(ii=0; ii<p1->nVal; ii++){
1809	sqlite3_value_free(apVal[ii]);
1810	apVal[ii] = 0;
1811	}
1812	p1->nVal = -1;
1813	p1->bHaveRowid = 0;
1814	}
1815
1816	if( iPage!=0 ){
1817	if( iField<0 ){
1818	p1->iRowid = sqlite3_column_int64(pSel, 3);
1819	assert( p1->nVal==-1 );
1820	p1->nVal = 0;
1821	p1->bHaveRowid = 1;
1822	}else if( iField<pTab->nCol ){
1823	assert( apVal[iField]==0 );
1824	apVal[iField] = sqlite3_value_dup( pVal );
1825	if( apVal[iField]==0 ){
1826	recoverError(p, SQLITE_NOMEM, 0);
1827	}
1828	p1->nVal = iField+1;
1829	}
1830	p1->iPrevCell = iCell;
1831	p1->iPrevPage = iPage;
1832	}
1833	}else{
1834	recoverReset(p, pSel);
1835	p1->pTab = 0;
1836	}
1837
1838	return p->errCode;
1839	}
1840
1841	/*
1842	** Initialize resources required by sqlite3_recover_step() in
1843	** RECOVER_STATE_LOSTANDFOUND1 state - during which the set of pages not
1844	** already allocated to a recovered schema element is determined.
1845	*/
1846	static void recoverLostAndFound1Init(sqlite3_recover *p){
1847	RecoverStateLAF *pLaf = &p->laf;
1848	sqlite3_stmt *pStmt = 0;
1849
1850	assert( p->laf.pUsed==0 );
1851	pLaf->nPg = recoverPageCount(p);
1852	pLaf->pUsed = recoverBitmapAlloc(p, pLaf->nPg);
1853
1854	/* Prepare a statement to iterate through all pages that are part of any tree
1855	** in the recoverable part of the input database schema to the bitmap. And,
1856	** if !p->bFreelistCorrupt, add all pages that appear to be part of the
1857	** freelist. */
1858	pStmt = recoverPrepare(
1859	p, p->dbOut,
1860	"WITH trunk(pgno) AS ("
1861	" SELECT read_i32(getpage(1), 8) AS x WHERE x>0"
1862	" UNION"
1863	" SELECT read_i32(getpage(trunk.pgno), 0) AS x FROM trunk WHERE x>0"
1864	"),"
1865	"trunkdata(pgno, data) AS ("
1866	" SELECT pgno, getpage(pgno) FROM trunk"
1867	"),"
1868	"freelist(data, n, freepgno) AS ("
1869	" SELECT data, min(16384, read_i32(data, 1)-1), pgno FROM trunkdata"
1870	" UNION ALL"
1871	" SELECT data, n-1, read_i32(data, 2+n) FROM freelist WHERE n>=0"
1872	"),"
1873	""
1874	"roots(r) AS ("
1875	" SELECT 1 UNION ALL"
1876	" SELECT rootpage FROM recovery.schema WHERE rootpage>0"
1877	"),"
1878	"used(page) AS ("
1879	" SELECT r FROM roots"
1880	" UNION"
1881	" SELECT child FROM sqlite_dbptr('getpage()'), used "
1882	" WHERE pgno=page"
1883	") "
1884	"SELECT page FROM used"
1885	" UNION ALL "
1886	"SELECT freepgno FROM freelist WHERE NOT ?"
1887	);
1888	if( pStmt ) sqlite3_bind_int(pStmt, 1, p->bFreelistCorrupt);
1889	pLaf->pUsedPages = pStmt;
1890	}
1891
1892	/*
1893	** Perform one step (sqlite3_recover_step()) of work for the connection
1894	** passed as the only argument, which is guaranteed to be in
1895	** RECOVER_STATE_LOSTANDFOUND1 state - during which the set of pages not
1896	** already allocated to a recovered schema element is determined.
1897	*/
1898	static int recoverLostAndFound1Step(sqlite3_recover *p){
1899	RecoverStateLAF *pLaf = &p->laf;
1900	int rc = p->errCode;
1901	if( rc==SQLITE_OK ){
1902	rc = sqlite3_step(pLaf->pUsedPages);
1903	if( rc==SQLITE_ROW ){
1904	i64 iPg = sqlite3_column_int64(pLaf->pUsedPages, 0);
1905	recoverBitmapSet(pLaf->pUsed, iPg);
1906	rc = SQLITE_OK;
1907	}else{
1908	recoverFinalize(p, pLaf->pUsedPages);
1909	pLaf->pUsedPages = 0;
1910	}
1911	}
1912	return rc;
1913	}
1914
1915	/*
1916	** Initialize resources required by RECOVER_STATE_LOSTANDFOUND2
1917	** state - during which the pages identified in RECOVER_STATE_LOSTANDFOUND1
1918	** are sorted into sets that likely belonged to the same database tree.
1919	*/
1920	static void recoverLostAndFound2Init(sqlite3_recover *p){
1921	RecoverStateLAF *pLaf = &p->laf;
1922
1923	assert( p->laf.pAllAndParent==0 );
1924	assert( p->laf.pMapInsert==0 );
1925	assert( p->laf.pMaxField==0 );
1926	assert( p->laf.nMaxField==0 );
1927
1928	pLaf->pMapInsert = recoverPrepare(p, p->dbOut,
1929	"INSERT OR IGNORE INTO recovery.map(pgno, parent) VALUES(?, ?)"
1930	);
1931	pLaf->pAllAndParent = recoverPreparePrintf(p, p->dbOut,
1932	"WITH RECURSIVE seq(ii) AS ("
1933	" SELECT 1 UNION ALL SELECT ii+1 FROM seq WHERE ii<%lld"
1934	")"
1935	"SELECT pgno, child FROM sqlite_dbptr('getpage()') "
1936	" UNION ALL "
1937	"SELECT NULL, ii FROM seq", p->laf.nPg
1938	);
1939	pLaf->pMaxField = recoverPreparePrintf(p, p->dbOut,
1940	"SELECT max(field)+1 FROM sqlite_dbdata('getpage') WHERE pgno = ?"
1941	);
1942	}
1943
1944	/*
1945	** Perform one step (sqlite3_recover_step()) of work for the connection
1946	** passed as the only argument, which is guaranteed to be in
1947	** RECOVER_STATE_LOSTANDFOUND2 state - during which the pages identified
1948	** in RECOVER_STATE_LOSTANDFOUND1 are sorted into sets that likely belonged
1949	** to the same database tree.
1950	*/
1951	static int recoverLostAndFound2Step(sqlite3_recover *p){
1952	RecoverStateLAF *pLaf = &p->laf;
1953	if( p->errCode==SQLITE_OK ){
1954	int res = sqlite3_step(pLaf->pAllAndParent);
1955	if( res==SQLITE_ROW ){
1956	i64 iChild = sqlite3_column_int(pLaf->pAllAndParent, 1);
1957	if( recoverBitmapQuery(pLaf->pUsed, iChild)==0 ){
1958	sqlite3_bind_int64(pLaf->pMapInsert, 1, iChild);
1959	sqlite3_bind_value(pLaf->pMapInsert, 2,
1960	sqlite3_column_value(pLaf->pAllAndParent, 0)
1961	);
1962	sqlite3_step(pLaf->pMapInsert);
1963	recoverReset(p, pLaf->pMapInsert);
1964	sqlite3_bind_int64(pLaf->pMaxField, 1, iChild);
1965	if( SQLITE_ROW==sqlite3_step(pLaf->pMaxField) ){
1966	int nMax = sqlite3_column_int(pLaf->pMaxField, 0);
1967	if( nMax>pLaf->nMaxField ) pLaf->nMaxField = nMax;
1968	}
1969	recoverReset(p, pLaf->pMaxField);
1970	}
1971	}else{
1972	recoverFinalize(p, pLaf->pAllAndParent);
1973	pLaf->pAllAndParent =0;
1974	return SQLITE_DONE;
1975	}
1976	}
1977	return p->errCode;
1978	}
1979
1980	/*
1981	** Free all resources allocated as part of sqlite3_recover_step() calls
1982	** in one of the RECOVER_STATE_LOSTANDFOUND[123] states.
1983	*/
1984	static void recoverLostAndFoundCleanup(sqlite3_recover *p){
1985	recoverBitmapFree(p->laf.pUsed);
1986	p->laf.pUsed = 0;
1987	sqlite3_finalize(p->laf.pUsedPages);
1988	sqlite3_finalize(p->laf.pAllAndParent);
1989	sqlite3_finalize(p->laf.pMapInsert);
1990	sqlite3_finalize(p->laf.pMaxField);
1991	sqlite3_finalize(p->laf.pFindRoot);
1992	sqlite3_finalize(p->laf.pInsert);
1993	sqlite3_finalize(p->laf.pAllPage);
1994	sqlite3_finalize(p->laf.pPageData);
1995	p->laf.pUsedPages = 0;
1996	p->laf.pAllAndParent = 0;
1997	p->laf.pMapInsert = 0;
1998	p->laf.pMaxField = 0;
1999	p->laf.pFindRoot = 0;
2000	p->laf.pInsert = 0;
2001	p->laf.pAllPage = 0;
2002	p->laf.pPageData = 0;
2003	sqlite3_free(p->laf.apVal);
2004	p->laf.apVal = 0;
2005	}
2006
2007	/*
2008	** Free all resources allocated as part of sqlite3_recover_step() calls.
2009	*/
2010	static void recoverFinalCleanup(sqlite3_recover *p){
2011	RecoverTable *pTab = 0;
2012	RecoverTable *pNext = 0;
2013
2014	recoverWriteDataCleanup(p);
2015	recoverLostAndFoundCleanup(p);
2016
2017	for(pTab=p->pTblList; pTab; pTab=pNext){
2018	pNext = pTab->pNext;
2019	sqlite3_free(pTab);
2020	}
2021	p->pTblList = 0;
2022	sqlite3_finalize(p->pGetPage);
2023	p->pGetPage = 0;
2024	sqlite3_file_control(p->dbIn, p->zDb, SQLITE_FCNTL_RESET_CACHE, 0);
2025
2026	{
2027	#ifndef NDEBUG
2028	int res =
2029	#endif
2030	sqlite3_close(p->dbOut);
2031	assert( res==SQLITE_OK );
2032	}
2033	p->dbOut = 0;
2034	}
2035
2036	/*
2037	** Decode and return an unsigned 16-bit big-endian integer value from
2038	** buffer a[].
2039	*/
2040	static u32 recoverGetU16(const u8 *a){
2041	return (((u32)a[0])<<8) + ((u32)a[1]);
2042	}
2043
2044	/*
2045	** Decode and return an unsigned 32-bit big-endian integer value from
2046	** buffer a[].
2047	*/
2048	static u32 recoverGetU32(const u8 *a){
2049	return (((u32)a[0])<<24) + (((u32)a[1])<<16) + (((u32)a[2])<<8) + ((u32)a[3]);
2050	}
2051
2052	/*
2053	** Decode an SQLite varint from buffer a[]. Write the decoded value to (*pVal)
2054	** and return the number of bytes consumed.
2055	*/
2056	static int recoverGetVarint(const u8 a, i64 pVal){
2057	sqlite3_uint64 u = 0;
2058	int i;
2059	for(i=0; i<8; i++){
2060	u = (u<<7) + (a[i]&0x7f);
2061	if( (a[i]&0x80)==0 ){ *pVal = (sqlite3_int64)u; return i+1; }
2062	}
2063	u = (u<<8) + (a[i]&0xff);
2064	*pVal = (sqlite3_int64)u;
2065	return 9;
2066	}
2067
2068	/*
2069	** The second argument points to a buffer n bytes in size. If this buffer
2070	** or a prefix thereof appears to contain a well-formed SQLite b-tree page,
2071	** return the page-size in bytes. Otherwise, if the buffer does not
2072	** appear to contain a well-formed b-tree page, return 0.
2073	*/
2074	static int recoverIsValidPage(u8 aTmp, const u8 a, int n){
2075	u8 *aUsed = aTmp;
2076	int nFrag = 0;
2077	int nActual = 0;
2078	int iFree = 0;
2079	int nCell = 0; /* Number of cells on page */
2080	int iCellOff = 0; /* Offset of cell array in page */
2081	int iContent = 0;
2082	int eType = 0;
2083	int ii = 0;
2084
2085	eType = (int)a[0];
2086	if( eType!=0x02 && eType!=0x05 && eType!=0x0A && eType!=0x0D ) return 0;
2087
2088	iFree = (int)recoverGetU16(&a[1]);
2089	nCell = (int)recoverGetU16(&a[3]);
2090	iContent = (int)recoverGetU16(&a[5]);
2091	if( iContent==0 ) iContent = 65536;
2092	nFrag = (int)a[7];
2093
2094	if( iContent>n ) return 0;
2095
2096	memset(aUsed, 0, n);
2097	memset(aUsed, 0xFF, iContent);
2098
2099	/* Follow the free-list. This is the same format for all b-tree pages. */
2100	if( iFree && iFree<=iContent ) return 0;
2101	while( iFree ){
2102	int iNext = 0;
2103	int nByte = 0;
2104	if( iFree>(n-4) ) return 0;
2105	iNext = recoverGetU16(&a[iFree]);
2106	nByte = recoverGetU16(&a[iFree+2]);
2107	if( iFree+nByte>n \|\| nByte<4 ) return 0;
2108	if( iNext && iNext<iFree+nByte ) return 0;
2109	memset(&aUsed[iFree], 0xFF, nByte);
2110	iFree = iNext;
2111	}
2112
2113	/* Run through the cells */
2114	if( eType==0x02 \|\| eType==0x05 ){
2115	iCellOff = 12;
2116	}else{
2117	iCellOff = 8;
2118	}
2119	if( (iCellOff + 2*nCell)>iContent ) return 0;
2120	for(ii=0; ii<nCell; ii++){
2121	int iByte;
2122	i64 nPayload = 0;
2123	int nByte = 0;
2124	int iOff = recoverGetU16(&a[iCellOff + 2*ii]);
2125	if( iOff<iContent \|\| iOff>n ){
2126	return 0;
2127	}
2128	if( eType==0x05 \|\| eType==0x02 ) nByte += 4;
2129	nByte += recoverGetVarint(&a[iOff+nByte], &nPayload);
2130	if( eType==0x0D ){
2131	i64 dummy = 0;
2132	nByte += recoverGetVarint(&a[iOff+nByte], &dummy);
2133	}
2134	if( eType!=0x05 ){
2135	int X = (eType==0x0D) ? n-35 : (((n-12)*64/255)-23);
2136	int M = ((n-12)*32/255)-23;
2137	int K = M+((nPayload-M)%(n-4));
2138
2139	if( nPayload<X ){
2140	nByte += nPayload;
2141	}else if( K<=X ){
2142	nByte += K+4;
2143	}else{
2144	nByte += M+4;
2145	}
2146	}
2147
2148	if( iOff+nByte>n ){
2149	return 0;
2150	}
2151	for(iByte=iOff; iByte<(iOff+nByte); iByte++){
2152	if( aUsed[iByte]!=0 ){
2153	return 0;
2154	}
2155	aUsed[iByte] = 0xFF;
2156	}
2157	}
2158
2159	nActual = 0;
2160	for(ii=0; ii<n; ii++){
2161	if( aUsed[ii]==0 ) nActual++;
2162	}
2163	return (nActual==nFrag);
2164	}
2165
2166
2167	static int recoverVfsClose(sqlite3_file*);
2168	static int recoverVfsRead(sqlite3_file, void, int iAmt, sqlite3_int64 iOfst);
2169	static int recoverVfsWrite(sqlite3_file, const void, int, sqlite3_int64);
2170	static int recoverVfsTruncate(sqlite3_file*, sqlite3_int64 size);
2171	static int recoverVfsSync(sqlite3_file*, int flags);
2172	static int recoverVfsFileSize(sqlite3_file, sqlite3_int64 pSize);
2173	static int recoverVfsLock(sqlite3_file*, int);
2174	static int recoverVfsUnlock(sqlite3_file*, int);
2175	static int recoverVfsCheckReservedLock(sqlite3_file, int pResOut);
2176	static int recoverVfsFileControl(sqlite3_file, int op, void pArg);
2177	static int recoverVfsSectorSize(sqlite3_file*);
2178	static int recoverVfsDeviceCharacteristics(sqlite3_file*);
2179	static int recoverVfsShmMap(sqlite3_file, int, int, int, void volatile*);
2180	static int recoverVfsShmLock(sqlite3_file*, int offset, int n, int flags);
2181	static void recoverVfsShmBarrier(sqlite3_file*);
2182	static int recoverVfsShmUnmap(sqlite3_file*, int deleteFlag);
2183	static int recoverVfsFetch(sqlite3_file, sqlite3_int64, int, void*);
2184	static int recoverVfsUnfetch(sqlite3_file pFd, sqlite3_int64 iOff, void p);
2185
2186	static sqlite3_io_methods recover_methods = {
2187	2, /* iVersion */
2188	recoverVfsClose,
2189	recoverVfsRead,
2190	recoverVfsWrite,
2191	recoverVfsTruncate,
2192	recoverVfsSync,
2193	recoverVfsFileSize,
2194	recoverVfsLock,
2195	recoverVfsUnlock,
2196	recoverVfsCheckReservedLock,
2197	recoverVfsFileControl,
2198	recoverVfsSectorSize,
2199	recoverVfsDeviceCharacteristics,
2200	recoverVfsShmMap,
2201	recoverVfsShmLock,
2202	recoverVfsShmBarrier,
2203	recoverVfsShmUnmap,
2204	recoverVfsFetch,
2205	recoverVfsUnfetch
2206	};
2207
2208	static int recoverVfsClose(sqlite3_file *pFd){
2209	assert( pFd->pMethods!=&recover_methods );
2210	return pFd->pMethods->xClose(pFd);
2211	}
2212
2213	/*
2214	** Write value v to buffer a[] as a 16-bit big-endian unsigned integer.
2215	*/
2216	static void recoverPutU16(u8 *a, u32 v){
2217	a[0] = (v>>8) & 0x00FF;
2218	a[1] = (v>>0) & 0x00FF;
2219	}
2220
2221	/*
2222	** Write value v to buffer a[] as a 32-bit big-endian unsigned integer.
2223	*/
2224	static void recoverPutU32(u8 *a, u32 v){
2225	a[0] = (v>>24) & 0x00FF;
2226	a[1] = (v>>16) & 0x00FF;
2227	a[2] = (v>>8) & 0x00FF;
2228	a[3] = (v>>0) & 0x00FF;
2229	}
2230
2231	/*
2232	** Detect the page-size of the database opened by file-handle pFd by
2233	** searching the first part of the file for a well-formed SQLite b-tree
2234	** page. If parameter nReserve is non-zero, then as well as searching for
2235	** a b-tree page with zero reserved bytes, this function searches for one
2236	** with nReserve reserved bytes at the end of it.
2237	**
2238	** If successful, set variable p->detected_pgsz to the detected page-size
2239	** in bytes and return SQLITE_OK. Or, if no error occurs but no valid page
2240	** can be found, return SQLITE_OK but leave p->detected_pgsz set to 0. Or,
2241	** if an error occurs (e.g. an IO or OOM error), then an SQLite error code
2242	** is returned. The final value of p->detected_pgsz is undefined in this
2243	** case.
2244	*/
2245	static int recoverVfsDetectPagesize(
2246	sqlite3_recover p, / Recover handle */
2247	sqlite3_file pFd, / File-handle open on input database */
2248	u32 nReserve, /* Possible nReserve value */
2249	i64 nSz /* Size of database file in bytes */
2250	){
2251	int rc = SQLITE_OK;
2252	const int nMin = 512;
2253	const int nMax = 65536;
2254	const int nMaxBlk = 4;
2255	u32 pgsz = 0;
2256	int iBlk = 0;
2257	u8 *aPg = 0;
2258	u8 *aTmp = 0;
2259	int nBlk = 0;
2260
2261	aPg = (u8)sqlite3_malloc(2nMax);
2262	if( aPg==0 ) return SQLITE_NOMEM;
2263	aTmp = &aPg[nMax];
2264
2265	nBlk = (nSz+nMax-1)/nMax;
2266	if( nBlk>nMaxBlk ) nBlk = nMaxBlk;
2267
2268	do {
2269	for(iBlk=0; rc==SQLITE_OK && iBlk<nBlk; iBlk++){
2270	int nByte = (nSz>=((iBlk+1)*nMax)) ? nMax : (nSz % nMax);
2271	memset(aPg, 0, nMax);
2272	rc = pFd->pMethods->xRead(pFd, aPg, nByte, iBlk*nMax);
2273	if( rc==SQLITE_OK ){
2274	int pgsz2;
2275	for(pgsz2=(pgsz ? pgsz2 : nMin); pgsz2<=nMax; pgsz2=pgsz22){
2276	int iOff;
2277	for(iOff=0; iOff<nMax; iOff+=pgsz2){
2278	if( recoverIsValidPage(aTmp, &aPg[iOff], pgsz2-nReserve) ){
2279	pgsz = pgsz2;
2280	break;
2281	}
2282	}
2283	}
2284	}
2285	}
2286	if( pgsz>(u32)p->detected_pgsz ){
2287	p->detected_pgsz = pgsz;
2288	p->nReserve = nReserve;
2289	}
2290	if( nReserve==0 ) break;
2291	nReserve = 0;
2292	}while( 1 );
2293
2294	p->detected_pgsz = pgsz;
2295	sqlite3_free(aPg);
2296	return rc;
2297	}
2298
2299	/*
2300	** The xRead() method of the wrapper VFS. This is used to intercept calls
2301	** to read page 1 of the input database.
2302	*/
2303	static int recoverVfsRead(sqlite3_file pFd, void aBuf, int nByte, i64 iOff){
2304	int rc = SQLITE_OK;
2305	if( pFd->pMethods==&recover_methods ){
2306	pFd->pMethods = recover_g.pMethods;
2307	rc = pFd->pMethods->xRead(pFd, aBuf, nByte, iOff);
2308	if( nByte==16 ){
2309	sqlite3_randomness(16, aBuf);
2310	}else
2311	if( rc==SQLITE_OK && iOff==0 && nByte>=108 ){
2312	/* Ensure that the database has a valid header file. The only fields
2313	** that really matter to recovery are:
2314	**
2315	** + Database page size (16-bits at offset 16)
2316	** + Size of db in pages (32-bits at offset 28)
2317	** + Database encoding (32-bits at offset 56)
2318	**
2319	** Also preserved are:
2320	**
2321	** + first freelist page (32-bits at offset 32)
2322	** + size of freelist (32-bits at offset 36)
2323	** + the wal-mode flags (16-bits at offset 18)
2324	**
2325	** We also try to preserve the auto-vacuum, incr-value, user-version
2326	** and application-id fields - all 32 bit quantities at offsets
2327	** 52, 60, 64 and 68. All other fields are set to known good values.
2328	**
2329	** Byte offset 105 should also contain the page-size as a 16-bit
2330	** integer.
2331	*/
2332	const int aPreserve[] = {32, 36, 52, 60, 64, 68};
2333	u8 aHdr[108] = {
2334	0x53, 0x51, 0x4c, 0x69, 0x74, 0x65, 0x20, 0x66,
2335	0x6f, 0x72, 0x6d, 0x61, 0x74, 0x20, 0x33, 0x00,
2336	0xFF, 0xFF, 0x01, 0x01, 0x00, 0x40, 0x20, 0x20,
2337	0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
2338	0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
2339	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
2340	0x00, 0x00, 0x10, 0x00, 0xFF, 0xFF, 0xFF, 0xFF,
2341	0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
2342	0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
2343	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2344	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2345	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2346	0x00, 0x2e, 0x5b, 0x30,
2347
2348	0x0D, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0x00
2349	};
2350	u8 a = (u8)aBuf;
2351
2352	u32 pgsz = recoverGetU16(&a[16]);
2353	u32 nReserve = a[20];
2354	u32 enc = recoverGetU32(&a[56]);
2355	u32 dbsz = 0;
2356	i64 dbFileSize = 0;
2357	int ii;
2358	sqlite3_recover *p = recover_g.p;
2359
2360	if( pgsz==0x01 ) pgsz = 65536;
2361	rc = pFd->pMethods->xFileSize(pFd, &dbFileSize);
2362
2363	if( rc==SQLITE_OK && p->detected_pgsz==0 ){
2364	rc = recoverVfsDetectPagesize(p, pFd, nReserve, dbFileSize);
2365	}
2366	if( p->detected_pgsz ){
2367	pgsz = p->detected_pgsz;
2368	nReserve = p->nReserve;
2369	}
2370
2371	if( pgsz ){
2372	dbsz = dbFileSize / pgsz;
2373	}
2374	if( enc!=SQLITE_UTF8 && enc!=SQLITE_UTF16BE && enc!=SQLITE_UTF16LE ){
2375	enc = SQLITE_UTF8;
2376	}
2377
2378	sqlite3_free(p->pPage1Cache);
2379	p->pPage1Cache = 0;
2380	p->pPage1Disk = 0;
2381
2382	p->pgsz = nByte;
2383	p->pPage1Cache = (u8)recoverMalloc(p, nByte2);
2384	if( p->pPage1Cache ){
2385	p->pPage1Disk = &p->pPage1Cache[nByte];
2386	memcpy(p->pPage1Disk, aBuf, nByte);
2387	aHdr[18] = a[18];
2388	aHdr[19] = a[19];
2389	recoverPutU32(&aHdr[28], dbsz);
2390	recoverPutU32(&aHdr[56], enc);
2391	recoverPutU16(&aHdr[105], pgsz-nReserve);
2392	if( pgsz==65536 ) pgsz = 1;
2393	recoverPutU16(&aHdr[16], pgsz);
2394	aHdr[20] = nReserve;
2395	for(ii=0; ii<(int)(sizeof(aPreserve)/sizeof(aPreserve[0])); ii++){
2396	memcpy(&aHdr[aPreserve[ii]], &a[aPreserve[ii]], 4);
2397	}
2398	memcpy(aBuf, aHdr, sizeof(aHdr));
2399	memset(&((u8*)aBuf)[sizeof(aHdr)], 0, nByte-sizeof(aHdr));
2400
2401	memcpy(p->pPage1Cache, aBuf, nByte);
2402	}else{
2403	rc = p->errCode;
2404	}
2405
2406	}
2407	pFd->pMethods = &recover_methods;
2408	}else{
2409	rc = pFd->pMethods->xRead(pFd, aBuf, nByte, iOff);
2410	}
2411	return rc;
2412	}
2413
2414	/*
2415	** Used to make sqlite3_io_methods wrapper methods less verbose.
2416	*/
2417	#define RECOVER_VFS_WRAPPER(code) \
2418	int rc = SQLITE_OK; \
2419	if( pFd->pMethods==&recover_methods ){ \
2420	pFd->pMethods = recover_g.pMethods; \
2421	rc = code; \
2422	pFd->pMethods = &recover_methods; \
2423	}else{ \
2424	rc = code; \
2425	} \
2426	return rc;
2427
2428	/*
2429	** Methods of the wrapper VFS. All methods except for xRead() and xClose()
2430	** simply uninstall the sqlite3_io_methods wrapper, invoke the equivalent
2431	** method on the lower level VFS, then reinstall the wrapper before returning.
2432	** Those that return an integer value use the RECOVER_VFS_WRAPPER macro.
2433	*/
2434	static int recoverVfsWrite(
2435	sqlite3_file pFd, const void aBuf, int nByte, i64 iOff
2436	){
2437	RECOVER_VFS_WRAPPER (
2438	pFd->pMethods->xWrite(pFd, aBuf, nByte, iOff)
2439	);
2440	}
2441	static int recoverVfsTruncate(sqlite3_file *pFd, sqlite3_int64 size){
2442	RECOVER_VFS_WRAPPER (
2443	pFd->pMethods->xTruncate(pFd, size)
2444	);
2445	}
2446	static int recoverVfsSync(sqlite3_file *pFd, int flags){
2447	RECOVER_VFS_WRAPPER (
2448	pFd->pMethods->xSync(pFd, flags)
2449	);
2450	}
2451	static int recoverVfsFileSize(sqlite3_file pFd, sqlite3_int64 pSize){
2452	RECOVER_VFS_WRAPPER (
2453	pFd->pMethods->xFileSize(pFd, pSize)
2454	);
2455	}
2456	static int recoverVfsLock(sqlite3_file *pFd, int eLock){
2457	RECOVER_VFS_WRAPPER (
2458	pFd->pMethods->xLock(pFd, eLock)
2459	);
2460	}
2461	static int recoverVfsUnlock(sqlite3_file *pFd, int eLock){
2462	RECOVER_VFS_WRAPPER (
2463	pFd->pMethods->xUnlock(pFd, eLock)
2464	);
2465	}
2466	static int recoverVfsCheckReservedLock(sqlite3_file pFd, int pResOut){
2467	RECOVER_VFS_WRAPPER (
2468	pFd->pMethods->xCheckReservedLock(pFd, pResOut)
2469	);
2470	}
2471	static int recoverVfsFileControl(sqlite3_file pFd, int op, void pArg){
2472	RECOVER_VFS_WRAPPER (
2473	(pFd->pMethods ? pFd->pMethods->xFileControl(pFd, op, pArg) : SQLITE_NOTFOUND)
2474	);
2475	}
2476	static int recoverVfsSectorSize(sqlite3_file *pFd){
2477	RECOVER_VFS_WRAPPER (
2478	pFd->pMethods->xSectorSize(pFd)
2479	);
2480	}
2481	static int recoverVfsDeviceCharacteristics(sqlite3_file *pFd){
2482	RECOVER_VFS_WRAPPER (
2483	pFd->pMethods->xDeviceCharacteristics(pFd)
2484	);
2485	}
2486	static int recoverVfsShmMap(
2487	sqlite3_file pFd, int iPg, int pgsz, int bExtend, void volatile *pp
2488	){
2489	RECOVER_VFS_WRAPPER (
2490	pFd->pMethods->xShmMap(pFd, iPg, pgsz, bExtend, pp)
2491	);
2492	}
2493	static int recoverVfsShmLock(sqlite3_file *pFd, int offset, int n, int flags){
2494	RECOVER_VFS_WRAPPER (
2495	pFd->pMethods->xShmLock(pFd, offset, n, flags)
2496	);
2497	}
2498	static void recoverVfsShmBarrier(sqlite3_file *pFd){
2499	if( pFd->pMethods==&recover_methods ){
2500	pFd->pMethods = recover_g.pMethods;
2501	pFd->pMethods->xShmBarrier(pFd);
2502	pFd->pMethods = &recover_methods;
2503	}else{
2504	pFd->pMethods->xShmBarrier(pFd);
2505	}
2506	}
2507	static int recoverVfsShmUnmap(sqlite3_file *pFd, int deleteFlag){
2508	RECOVER_VFS_WRAPPER (
2509	pFd->pMethods->xShmUnmap(pFd, deleteFlag)
2510	);
2511	}
2512
2513	static int recoverVfsFetch(
2514	sqlite3_file *pFd,
2515	sqlite3_int64 iOff,
2516	int iAmt,
2517	void **pp
2518	){
2519	(void)pFd;
2520	(void)iOff;
2521	(void)iAmt;
2522	*pp = 0;
2523	return SQLITE_OK;
2524	}
2525	static int recoverVfsUnfetch(sqlite3_file pFd, sqlite3_int64 iOff, void p){
2526	(void)pFd;
2527	(void)iOff;
2528	(void)p;
2529	return SQLITE_OK;
2530	}
2531
2532	/*
2533	** Install the VFS wrapper around the file-descriptor open on the input
2534	** database for recover handle p. Mutex RECOVER_MUTEX_ID must be held
2535	** when this function is called.
2536	*/
2537	static void recoverInstallWrapper(sqlite3_recover *p){
2538	sqlite3_file *pFd = 0;
2539	assert( recover_g.pMethods==0 );
2540	recoverAssertMutexHeld();
2541	sqlite3_file_control(p->dbIn, p->zDb, SQLITE_FCNTL_FILE_POINTER, (void*)&pFd);
2542	assert( pFd==0 \|\| pFd->pMethods!=&recover_methods );
2543	if( pFd && pFd->pMethods ){
2544	int iVersion = 1 + (pFd->pMethods->iVersion>1 && pFd->pMethods->xShmMap!=0);
2545	recover_g.pMethods = pFd->pMethods;
2546	recover_g.p = p;
2547	recover_methods.iVersion = iVersion;
2548	pFd->pMethods = &recover_methods;
2549	}
2550	}
2551
2552	/*
2553	** Uninstall the VFS wrapper that was installed around the file-descriptor open
2554	** on the input database for recover handle p. Mutex RECOVER_MUTEX_ID must be
2555	** held when this function is called.
2556	*/
2557	static void recoverUninstallWrapper(sqlite3_recover *p){
2558	sqlite3_file *pFd = 0;
2559	recoverAssertMutexHeld();
2560	sqlite3_file_control(p->dbIn, p->zDb,SQLITE_FCNTL_FILE_POINTER,(void*)&pFd);
2561	if( pFd && pFd->pMethods ){
2562	pFd->pMethods = recover_g.pMethods;
2563	recover_g.pMethods = 0;
2564	recover_g.p = 0;
2565	}
2566	}
2567
2568	/*
2569	** This function does the work of a single sqlite3_recover_step() call. It
2570	** is guaranteed that the handle is not in an error state when this
2571	** function is called.
2572	*/
2573	static void recoverStep(sqlite3_recover *p){
2574	assert( p && p->errCode==SQLITE_OK );
2575	switch( p->eState ){
2576	case RECOVER_STATE_INIT:
2577	/* This is the very first call to sqlite3_recover_step() on this object.
2578	*/
2579	recoverSqlCallback(p, "BEGIN");
2580	recoverSqlCallback(p, "PRAGMA writable_schema = on");
2581
2582	recoverEnterMutex();
2583	recoverInstallWrapper(p);
2584
2585	/* Open the output database. And register required virtual tables and
2586	** user functions with the new handle. */
2587	recoverOpenOutput(p);
2588
2589	/* Open transactions on both the input and output databases. */
2590	sqlite3_file_control(p->dbIn, p->zDb, SQLITE_FCNTL_RESET_CACHE, 0);
2591	recoverExec(p, p->dbIn, "PRAGMA writable_schema = on");
2592	recoverExec(p, p->dbIn, "BEGIN");
2593	if( p->errCode==SQLITE_OK ) p->bCloseTransaction = 1;
2594	recoverExec(p, p->dbIn, "SELECT 1 FROM sqlite_schema");
2595	recoverTransferSettings(p);
2596	recoverOpenRecovery(p);
2597	recoverCacheSchema(p);
2598
2599	recoverUninstallWrapper(p);
2600	recoverLeaveMutex();
2601
2602	recoverExec(p, p->dbOut, "BEGIN");
2603
2604	recoverWriteSchema1(p);
2605	p->eState = RECOVER_STATE_WRITING;
2606	break;
2607
2608	case RECOVER_STATE_WRITING: {
2609	if( p->w1.pTbls==0 ){
2610	recoverWriteDataInit(p);
2611	}
2612	if( SQLITE_DONE==recoverWriteDataStep(p) ){
2613	recoverWriteDataCleanup(p);
2614	if( p->zLostAndFound ){
2615	p->eState = RECOVER_STATE_LOSTANDFOUND1;
2616	}else{
2617	p->eState = RECOVER_STATE_SCHEMA2;
2618	}
2619	}
2620	break;
2621	}
2622
2623	case RECOVER_STATE_LOSTANDFOUND1: {
2624	if( p->laf.pUsed==0 ){
2625	recoverLostAndFound1Init(p);
2626	}
2627	if( SQLITE_DONE==recoverLostAndFound1Step(p) ){
2628	p->eState = RECOVER_STATE_LOSTANDFOUND2;
2629	}
2630	break;
2631	}
2632	case RECOVER_STATE_LOSTANDFOUND2: {
2633	if( p->laf.pAllAndParent==0 ){
2634	recoverLostAndFound2Init(p);
2635	}
2636	if( SQLITE_DONE==recoverLostAndFound2Step(p) ){
2637	p->eState = RECOVER_STATE_LOSTANDFOUND3;
2638	}
2639	break;
2640	}
2641
2642	case RECOVER_STATE_LOSTANDFOUND3: {
2643	if( p->laf.pInsert==0 ){
2644	recoverLostAndFound3Init(p);
2645	}
2646	if( SQLITE_DONE==recoverLostAndFound3Step(p) ){
2647	p->eState = RECOVER_STATE_SCHEMA2;
2648	}
2649	break;
2650	}
2651
2652	case RECOVER_STATE_SCHEMA2: {
2653	int rc = SQLITE_OK;
2654
2655	recoverWriteSchema2(p);
2656	p->eState = RECOVER_STATE_DONE;
2657
2658	/* If no error has occurred, commit the write transaction on the output
2659	** database. Regardless of whether or not an error has occurred, make
2660	** an attempt to end the read transaction on the input database. */
2661	recoverExec(p, p->dbOut, "COMMIT");
2662	rc = sqlite3_exec(p->dbIn, "END", 0, 0, 0);
2663	if( p->errCode==SQLITE_OK ) p->errCode = rc;
2664
2665	recoverSqlCallback(p, "PRAGMA writable_schema = off");
2666	recoverSqlCallback(p, "COMMIT");
2667	p->eState = RECOVER_STATE_DONE;
2668	recoverFinalCleanup(p);
2669	break;
2670	};
2671
2672	case RECOVER_STATE_DONE: {
2673	/* no-op */
2674	break;
2675	};
2676	}
2677	}
2678
2679
2680	/*
2681	** This is a worker function that does the heavy lifting for both init
2682	** functions:
2683	**
2684	** sqlite3_recover_init()
2685	** sqlite3_recover_init_sql()
2686	**
2687	** All this function does is allocate space for the recover handle and
2688	** take copies of the input parameters. All the real work is done within
2689	** sqlite3_recover_run().
2690	*/
2691	sqlite3_recover *recoverInit(
2692	sqlite3* db,
2693	const char *zDb,
2694	const char zUri, / Output URI for _recover_init() */
2695	int (xSql)(void, const char),/ SQL callback for _recover_init_sql() */
2696	void pSqlCtx / Context arg for _recover_init_sql() */
2697	){
2698	sqlite3_recover *pRet = 0;
2699	int nDb = 0;
2700	int nUri = 0;
2701	int nByte = 0;
2702
2703	if( zDb==0 ){ zDb = "main"; }
2704
2705	nDb = recoverStrlen(zDb);
2706	nUri = recoverStrlen(zUri);
2707
2708	nByte = sizeof(sqlite3_recover) + nDb+1 + nUri+1;
2709	pRet = (sqlite3_recover*)sqlite3_malloc(nByte);
2710	if( pRet ){
2711	memset(pRet, 0, nByte);
2712	pRet->dbIn = db;
2713	pRet->zDb = (char*)&pRet[1];
2714	pRet->zUri = &pRet->zDb[nDb+1];
2715	memcpy(pRet->zDb, zDb, nDb);
2716	if( nUri>0 && zUri ) memcpy(pRet->zUri, zUri, nUri);
2717	pRet->xSql = xSql;
2718	pRet->pSqlCtx = pSqlCtx;
2719	pRet->bRecoverRowid = RECOVER_ROWID_DEFAULT;
2720	}
2721
2722	return pRet;
2723	}
2724
2725	/*
2726	** Initialize a recovery handle that creates a new database containing
2727	** the recovered data.
2728	*/
2729	sqlite3_recover *sqlite3_recover_init(
2730	sqlite3* db,
2731	const char *zDb,
2732	const char *zUri
2733	){
2734	return recoverInit(db, zDb, zUri, 0, 0);
2735	}
2736
2737	/*
2738	** Initialize a recovery handle that returns recovered data in the
2739	** form of SQL statements via a callback.
2740	*/
2741	sqlite3_recover *sqlite3_recover_init_sql(
2742	sqlite3* db,
2743	const char *zDb,
2744	int (xSql)(void, const char*),
2745	void *pSqlCtx
2746	){
2747	return recoverInit(db, zDb, 0, xSql, pSqlCtx);
2748	}
2749
2750	/*
2751	** Return the handle error message, if any.
2752	*/
2753	const char sqlite3_recover_errmsg(sqlite3_recover p){
2754	return (p && p->errCode!=SQLITE_NOMEM) ? p->zErrMsg : "out of memory";
2755	}
2756
2757	/*
2758	** Return the handle error code.
2759	*/
2760	int sqlite3_recover_errcode(sqlite3_recover *p){
2761	return p ? p->errCode : SQLITE_NOMEM;
2762	}
2763
2764	/*
2765	** Configure the handle.
2766	*/
2767	int sqlite3_recover_config(sqlite3_recover p, int op, void pArg){
2768	int rc = SQLITE_OK;
2769	if( p==0 ){
2770	rc = SQLITE_NOMEM;
2771	}else if( p->eState!=RECOVER_STATE_INIT ){
2772	rc = SQLITE_MISUSE;
2773	}else{
2774	switch( op ){
2775	case 789:
2776	/* This undocumented magic configuration option is used to set the
2777	** name of the auxiliary database that is ATTACH-ed to the database
2778	** connection and used to hold state information during the
2779	** recovery process. This option is for debugging use only and
2780	** is subject to change or removal at any time. */
2781	sqlite3_free(p->zStateDb);
2782	p->zStateDb = recoverMPrintf(p, "%s", (char*)pArg);
2783	break;
2784
2785	case SQLITE_RECOVER_LOST_AND_FOUND: {
2786	const char zArg = (const char)pArg;
2787	sqlite3_free(p->zLostAndFound);
2788	if( zArg ){
2789	p->zLostAndFound = recoverMPrintf(p, "%s", zArg);
2790	}else{
2791	p->zLostAndFound = 0;
2792	}
2793	break;
2794	}
2795
2796	case SQLITE_RECOVER_FREELIST_CORRUPT:
2797	p->bFreelistCorrupt = (int)pArg;
2798	break;
2799
2800	case SQLITE_RECOVER_ROWIDS:
2801	p->bRecoverRowid = (int)pArg;
2802	break;
2803
2804	case SQLITE_RECOVER_SLOWINDEXES:
2805	p->bSlowIndexes = (int)pArg;
2806	break;
2807
2808	default:
2809	rc = SQLITE_NOTFOUND;
2810	break;
2811	}
2812	}
2813
2814	return rc;
2815	}
2816
2817	/*
2818	** Do a unit of work towards the recovery job. Return SQLITE_OK if
2819	** no error has occurred but database recovery is not finished, SQLITE_DONE
2820	** if database recovery has been successfully completed, or an SQLite
2821	** error code if an error has occurred.
2822	*/
2823	int sqlite3_recover_step(sqlite3_recover *p){
2824	if( p==0 ) return SQLITE_NOMEM;
2825	if( p->errCode==SQLITE_OK ) recoverStep(p);
2826	if( p->eState==RECOVER_STATE_DONE && p->errCode==SQLITE_OK ){
2827	return SQLITE_DONE;
2828	}
2829	return p->errCode;
2830	}
2831
2832	/*
2833	** Do the configured recovery operation. Return SQLITE_OK if successful, or
2834	** else an SQLite error code.
2835	*/
2836	int sqlite3_recover_run(sqlite3_recover *p){
2837	while( SQLITE_OK==sqlite3_recover_step(p) );
2838	return sqlite3_recover_errcode(p);
2839	}
2840
2841
2842	/*
2843	** Free all resources associated with the recover handle passed as the only
2844	argument. The results of using a handle with any sqlite3_recover_
2845	** API function after it has been passed to this function are undefined.
2846	**
2847	** A copy of the value returned by the first call made to sqlite3_recover_run()
2848	** on this handle is returned, or SQLITE_OK if sqlite3_recover_run() has
2849	** not been called on this handle.
2850	*/
2851	int sqlite3_recover_finish(sqlite3_recover *p){
2852	int rc;
2853	if( p==0 ){
2854	rc = SQLITE_NOMEM;
2855	}else{
2856	recoverFinalCleanup(p);
2857	if( p->bCloseTransaction && sqlite3_get_autocommit(p->dbIn)==0 ){
2858	rc = sqlite3_exec(p->dbIn, "END", 0, 0, 0);
2859	if( p->errCode==SQLITE_OK ) p->errCode = rc;
2860	}
2861	rc = p->errCode;
2862	sqlite3_free(p->zErrMsg);
2863	sqlite3_free(p->zStateDb);
2864	sqlite3_free(p->zLostAndFound);
2865	sqlite3_free(p->pPage1Cache);
2866	sqlite3_free(p);
2867	}
2868	return rc;
2869	}
2870
2871	#endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */
2872	#pragma GCC diagnostic pop