Adding upstream version 3.40.1.upstream/3.40.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

8 files changed, 1980 insertions, 0 deletions

diff --git a/doc/F2FS.txt b/doc/F2FS.txt
new file mode 100644
index 0000000..47ad229
--- /dev/null
+++ b/doc/F2FS.txt
@@ -0,0 +1,87 @@
+
+SQLite's OS layer contains the following definitions used in F2FS related
+calls:
+
+#define F2FS_IOCTL_MAGIC        0xf5
+#define F2FS_IOC_START_ATOMIC_WRITE     _IO(F2FS_IOCTL_MAGIC, 1)
+#define F2FS_IOC_COMMIT_ATOMIC_WRITE    _IO(F2FS_IOCTL_MAGIC, 2)
+#define F2FS_IOC_START_VOLATILE_WRITE   _IO(F2FS_IOCTL_MAGIC, 3)
+#define F2FS_IOC_ABORT_VOLATILE_WRITE   _IO(F2FS_IOCTL_MAGIC, 5)
+#define F2FS_IOC_GET_FEATURES           _IOR(F2FS_IOCTL_MAGIC, 12, u32)
+#define F2FS_FEATURE_ATOMIC_WRITE       0x0004
+
+After opening a database file on Linux (including Android), SQLite determines
+whether or not a file supports F2FS atomic commits as follows:
+
+  u32 flags = 0;
+  rc = ioctl(fd, F2FS_IOC_GET_FEATURES, &flags);
+  if( rc==0 && (flags & F2FS_FEATURE_ATOMIC_WRITE) ){
+    /* File supports F2FS atomic commits */
+  }else{
+    /* File does NOT support F2FS atomic commits */
+  }
+
+where "fd" is the file-descriptor open on the database file.
+
+Usually, when writing to a database file that supports atomic commits, SQLite
+accumulates the entire transaction in heap memory, deferring all writes to the
+db file until the transaction is committed.
+
+When it is time to commit a transaction on a file that supports atomic
+commits, SQLite does:
+
+  /* Take an F_WRLCK lock on the database file. This prevents any other
+  ** SQLite clients from reading or writing the file until the lock
+  ** is released.  */
+  rc = fcntl(fd, F_SETLK, ...);
+  if( rc!=0 ) goto failed;
+
+  rc = ioctl(fd, F2FS_IOC_START_ATOMIC_WRITE);
+  if( rc!=0 ) goto fallback_to_legacy_journal_commit;
+
+  foreach (dirty page){
+    rc = write(fd, ...dirty page...);
+    if( rc!=0 ){
+      ioctl(fd, F2FS_IOC_ABORT_VOLATILE_WRITE);
+      goto fallback_to_legacy_journal_commit;
+    }
+  }
+
+  rc = ioctl(fd, F2FS_IOC_COMMIT_ATOMIC_WRITE);
+  if( rc!=0 ){
+    ioctl(fd, F2FS_IOC_ABORT_VOLATILE_WRITE);
+    goto fallback_to_legacy_journal_commit;
+  }
+
+  /* If we get there, the transaction has been successfully 
+  ** committed to persistent storage. The following call
+  ** relinquishes the F_WRLCK lock.  */
+  fcntl(fd, F_SETLK, ...);
+
+Assumptions:
+
+1. After either of the F2FS_IOC_ABORT_VOLATILE_WRITE calls return,
+   the database file is in the state that it was in before
+   F2FS_IOC_START_ATOMIC_WRITE was invoked. Even if the ioctl()
+   fails - we're ignoring the return code.
+
+   This is true regardless of the type of error that occurred in
+   ioctl() or write().
+
+2. If the system fails before the F2FS_IOC_COMMIT_ATOMIC_WRITE is
+   completed, then following a reboot the database file is in the
+   state that it was in before F2FS_IOC_START_ATOMIC_WRITE was invoked.
+   Or, if the write was commited right before the system failed, in a 
+   state indicating that all write() calls were successfully committed
+   to persistent storage before the failure occurred.
+
+3. If the process crashes before the F2FS_IOC_COMMIT_ATOMIC_WRITE is
+   completed then the file is automatically restored to the state that
+   it was in before F2FS_IOC_START_ATOMIC_WRITE was called. This occurs
+   before the posix advisory lock is automatically dropped - there is
+   no chance that another client will be able to read the file in a
+   half-committed state before the rollback operation occurs.
+
+
+
+
diff --git a/doc/json-enhancements.md b/doc/json-enhancements.md
new file mode 100644
index 0000000..bc03e89
--- /dev/null
+++ b/doc/json-enhancements.md
@@ -0,0 +1,144 @@
+# JSON Functions Enhancements (2022)
+
+This document summaries enhancements to the SQLite JSON support added in
+early 2022.
+
+## 1.0 Change summary:
+
+  1.  New **->** and **->>** operators that work like MySQL and PostgreSQL (PG).
+  2.  JSON functions are built-in rather than being an extension.  They
+      are included by default, but can be omitted using the
+      -DSQLITE_OMIT_JSON compile-time option.
+
+
+## 2.0 New operators **->** and **->>**
+
+The SQLite language adds two new binary operators **->** and **->>**.
+Both operators are similar to json_extract().  The left operand is
+JSON and the right operand is a JSON path expression (possibly abbreviated
+for compatibility with PG - see below).  So they are similar to a
+two-argument call to json_extract().
+
+The difference between -> and ->> (and json_extract()) is as follows:
+
+  *  The -> operator always returns JSON.
+
+  *  The ->> operator converts the answer into a primitive SQL datatype
+     such as TEXT, INTEGER, REAL, or NULL.  If a JSON object or array
+     is selected, that object or array is rendered as text.  If a JSON
+     value is selected, that value is converted into its corresponding
+     SQL type
+
+  *  The json_extract() interface returns JSON when a JSON object or
+     array is selected, or a primitive SQL datatype when a JSON value
+     is selected.  This is different from MySQL, in which json_extract()
+     always returns JSON, but the difference is retained because it has
+     worked that way for 6 years and changing it now would likely break
+     a lot of legacy code.
+
+In MySQL and PG, the ->> operator always returns TEXT (or NULL) and never
+INTEGER or REAL.  This is due to limitations in the type handling capabilities
+of those systems.  In MySQL and PG, the result type a function or operator
+may only depend on the type of its arguments, never the value of its arguments.
+But the underlying JSON type depends on the value of the JSON path
+expression, not the type of the JSON path expression (which is always TEXT).
+Hence, the result type of ->> in MySQL and PG is unable to vary according
+to the type of the JSON value being extracted.
+
+The type system in SQLite is more general.  Functions in SQLite are able
+to return different datatypes depending on the value of their arguments.
+So the ->> operator in SQLite is able to return TEXT, INTEGER, REAL, or NULL
+depending on the JSON type of the value being extracted.  This means that
+the behavior of the ->> is slightly different in SQLite versus MySQL and PG
+in that it will sometimes return INTEGER and REAL values, depending on its
+inputs.  It is possible to implement the ->> operator in SQLite so that it
+always operates exactly like MySQL and PG and always returns TEXT or NULL,
+but I have been unable to think of any situations where returning the
+actual JSON value this would cause problems, so I'm including the enhanced
+functionality in SQLite.
+
+The table below attempts to summarize the differences between the
+-> and ->> operators and the json_extract() function, for SQLite, MySQL,
+and PG.  JSON values are shown using their SQL text representation but
+in a bold font.
+
+
+<table border=1 cellpadding=5 cellspacing=0>
+<tr><th>JSON<th>PATH<th>-&gt; operator<br>(all)<th>-&gt;&gt; operator<br>(MySQL/PG)
+    <th>-&gt;&gt; operator<br>(SQLite)<th>json_extract()<br>(SQLite)
+<tr><td> **'{"a":123}'**     <td>'$.a'<td> **'123'**     <td> '123'          <td> 123           <td> 123
+<tr><td> **'{"a":4.5}'**     <td>'$.a'<td> **'4.5'**     <td> '4.5'          <td> 4.5           <td> 4.5
+<tr><td> **'{"a":"xyz"}'**   <td>'$.a'<td> **'"xyz"'**   <td> 'xyz'          <td> 'xyz'         <td> 'xyz'
+<tr><td> **'{"a":null}'**    <td>'$.a'<td> **'null'**    <td> NULL           <td> NULL          <td> NULL
+<tr><td> **'{"a":[6,7,8]}'** <td>'$.a'<td> **'[6,7,8]'** <td> '[6,7,8]'      <td> '[6,7,8]'     <td> **'[6,7,8]'**
+<tr><td> **'{"a":{"x":9}}'** <td>'$.a'<td> **'{"x":9}'** <td> '{"x":9}'      <td> '{"x":9}'     <td> **'{"x":9}'**
+<tr><td> **'{"b":999}'**     <td>'$.a'<td> NULL          <td> NULL           <td> NULL          <td> NULL
+</table>
+
+Important points about the table above:
+
+  *  The -> operator always returns either JSON or NULL.
+
+  *  The ->> operator never returns JSON.  It always returns TEXT or NULL, or in the
+     case of SQLite, INTEGER or REAL.
+
+  *  The MySQL json_extract() function works exactly the same
+     as the MySQL -> operator.
+
+  *  The SQLite json_extract() operator works like -> for JSON objects and
+     arrays, and like ->> for JSON values.
+
+  *  The -> operator works the same for all systems.
+
+  *  The only difference in ->> between SQLite and other systems is that
+     when the JSON value is numeric, SQLite returns a numeric SQL value,
+     whereas the other systems return a text representation of the numeric
+     value.
+
+### 2.1 Abbreviated JSON path expressions for PG compatibility
+
+The table above always shows the full JSON path expression: '$.a'.  But
+PG does not accept this syntax.  PG only allows a single JSON object label
+name or a single integer array index.  In order to provide compatibility
+with PG, The -> and ->> operators in SQLite are extended to also support
+a JSON object label or an integer array index for the right-hand side
+operand, in addition to a full JSON path expression.
+
+Thus, a -> or ->> operator that works on MySQL will work in
+SQLite.  And a -> or ->> operator that works in PG will work in SQLite.
+But because SQLite supports the union of the disjoint capabilities of
+MySQL and PG, there will always be -> and ->> operators that work in
+SQLite that do not work in one of MySQL and PG.  This is an unavoidable
+consequence of the different syntax for -> and ->> in MySQL and PG.
+
+In the following table, assume that "value1" is a JSON object and
+"value2" is a JSON array.
+
+<table border=1 cellpadding=5 cellspacing=0>
+<tr><th>SQL expression     <th>Works in MySQL?<th>Works in PG?<th>Works in SQLite
+<tr><td>value1-&gt;'$.a'   <td> yes           <td>  no        <td> yes
+<tr><td>value1-&gt;'a'     <td> no            <td>  yes       <td> yes
+<tr><td>value2-&gt;'$[2]'  <td> yes           <td>  no        <td> yes
+<tr><td>value2-&gt;2       <td> no            <td>  yes       <td> yes
+</table>
+
+The abbreviated JSON path expressions only work for the -> and ->> operators
+in SQLite.  The json_extract() function, and all other built-in SQLite
+JSON functions, continue to require complete JSON path expressions for their
+PATH arguments.
+
+## 3.0 JSON moved into the core
+
+The JSON interface is now moved into the SQLite core.
+
+When originally written in 2015, the JSON functions were an extension
+that could be optionally included at compile-time, or loaded at run-time.
+The implementation was in a source file named ext/misc/json1.c in the
+source tree.  JSON functions were only compiled in if the
+-DSQLITE_ENABLE_JSON1 compile-time option was used.
+
+After these enhancements, the JSON functions are now built-ins.
+The source file that implements the JSON functions is moved to src/json.c.
+No special compile-time options are needed to load JSON into the build.
+Instead, there is a new -DSQLITE_OMIT_JSON compile-time option to leave
+them out.
diff --git a/doc/lemon.html b/doc/lemon.html
new file mode 100644
index 0000000..324b3f3
--- /dev/null
+++ b/doc/lemon.html
@@ -0,0 +1,1264 @@
+<html>
+<head>
+<title>The Lemon Parser Generator</title>
+</head>
+<body>
+<a id="main"></a>
+<h1 align='center'>The Lemon Parser Generator</h1>
+
+<p>Lemon is an LALR(1) parser generator for C.
+It does the same job as "bison" and "yacc".
+But Lemon is not a bison or yacc clone.  Lemon
+uses a different grammar syntax which is designed to
+reduce the number of coding errors.  Lemon also uses a
+parsing engine that is faster than yacc and
+bison and which is both reentrant and threadsafe.
+(Update: Since the previous sentence was written, bison
+has also been updated so that it too can generate a
+reentrant and threadsafe parser.)
+Lemon also implements features that can be used
+to eliminate resource leaks, making it suitable for use
+in long-running programs such as graphical user interfaces
+or embedded controllers.</p>
+
+<p>This document is an introduction to the Lemon
+parser generator.</p>
+
+<a id="toc"></a>
+<h2>1.0 Table of Contents</h2>
+<ul>
+<li><a href="#main">Introduction</a>
+<li><a href="#toc">1.0 Table of Contents</a>
+<li><a href="#secnot">2.0 Security Notes</a><br>
+<li><a href="#optheory">3.0 Theory of Operation</a>
+    <ul>
+    <li><a href="#options">3.1 Command Line Options</a>
+    <li><a href="#interface">3.2 The Parser Interface</a>
+        <ul>
+        <li><a href="#onstack">3.2.1 Allocating The Parse Object On Stack</a>
+        <li><a href="#ifsum">3.2.2 Interface Summary</a>
+        </ul>
+    <li><a href="#yaccdiff">3.3 Differences With YACC and BISON</a>
+    <li><a href="#build">3.4 Building The "lemon" Or "lemon.exe" Executable</a>
+    </ul>
+<li><a href="#syntax">4.0 Input File Syntax</a>
+    <ul>
+    <li><a href="#tnt">4.1 Terminals and Nonterminals</a>
+    <li><a href="#rules">4.2 Grammar Rules</a>
+    <li><a href="#precrules">4.3 Precedence Rules</a>
+    <li><a href="#special">4.4 Special Directives</a>
+    </ul>
+<li><a href="#errors">5.0 Error Processing</a>
+<li><a href="#history">6.0 History of Lemon</a>
+<li><a href="#copyright">7.0 Copyright</a>
+</ul>
+
+<a id="secnot"></a>
+<h2>2.0 Security Note</h2>
+
+<p>The language parser code created by Lemon is very robust and
+is well-suited for use in internet-facing applications that need to
+safely process maliciously crafted inputs.</p>
+
+<p>The "lemon.exe" command-line tool itself works great when given a valid
+input grammar file and almost always gives helpful
+error messages for malformed inputs.  However,  it is possible for
+a malicious user to craft a grammar file that will cause 
+lemon.exe to crash.
+We do not see this as a problem, as lemon.exe is not intended to be used
+with hostile inputs.
+To summarize:</p>
+
+<ul>
+<li>Parser code generated by lemon &rarr; Robust and secure
+<li>The "lemon.exe" command line tool itself &rarr; Not so much
+</ul>
+
+<a id="optheory"></a>
+<h2>3.0 Theory of Operation</h2>
+
+<p>Lemon is computer program that translates a context free grammar (CFG)
+for a particular language into C code that implements a parser for
+that language.
+The Lemon program has two inputs:</p>
+<ul>
+<li>The grammar specification.
+<li>A parser template file.
+</ul>
+<p>Typically, only the grammar specification is supplied by the programmer.
+Lemon comes with a default parser template
+("<a href="https://sqlite.org/src/file/tool/lempar.c">lempar.c</a>")
+that works fine for most applications.  But the user is free to substitute
+a different parser template if desired.</p>
+
+<p>Depending on command-line options, Lemon will generate up to
+three output files.</p>
+<ul>
+<li>C code to implement a parser for the input grammar.
+<li>A header file defining an integer ID for each terminal symbol
+    (or "token").
+<li>An information file that describes the states of the generated parser
+    automaton.
+</ul>
+<p>By default, all three of these output files are generated.
+The header file is suppressed if the "-m" command-line option is
+used and the report file is omitted when "-q" is selected.</p>
+
+<p>The grammar specification file uses a ".y" suffix, by convention.
+In the examples used in this document, we'll assume the name of the
+grammar file is "gram.y".  A typical use of Lemon would be the
+following command:</p>
+<pre>
+   lemon gram.y
+</pre>
+<p>This command will generate three output files named "gram.c",
+"gram.h" and "gram.out".
+The first is C code to implement the parser.  The second
+is the header file that defines numerical values for all
+terminal symbols, and the last is the report that explains
+the states used by the parser automaton.</p>
+
+<a id="options"></a>
+<h3>3.1 Command Line Options</h3>
+
+<p>The behavior of Lemon can be modified using command-line options.
+You can obtain a list of the available command-line options together
+with a brief explanation of what each does by typing</p>
+<pre>
+   lemon "-?"
+</pre>
+<p>As of this writing, the following command-line options are supported:</p>
+<ul>
+<li><b>-b</b>
+Show only the basis for each parser state in the report file.
+<li><b>-c</b>
+Do not compress the generated action tables.  The parser will be a
+little larger and slower, but it will detect syntax errors sooner.
+<li><b>-d</b><i>directory</i>
+Write all output files into <i>directory</i>.  Normally, output files
+are written into the directory that contains the input grammar file.
+<li><b>-D<i>name</i></b>
+Define C preprocessor macro <i>name</i>.  This macro is usable by
+"<tt><a href='#pifdef'>%ifdef</a></tt>",
+"<tt><a href='#pifdef'>%ifndef</a></tt>", and
+"<tt><a href="#pifdef">%if</a></tt> lines
+in the grammar file.
+<li><b>-E</b>
+Run the "%if" preprocessor step only and print the revised grammar
+file.
+<li><b>-g</b>
+Do not generate a parser.  Instead write the input grammar to standard
+output with all comments, actions, and other extraneous text removed.
+<li><b>-l</b>
+Omit "#line" directives in the generated parser C code.
+<li><b>-m</b>
+Cause the output C source code to be compatible with the "makeheaders"
+program.
+<li><b>-p</b>
+Display all conflicts that are resolved by
+<a href='#precrules'>precedence rules</a>.
+<li><b>-q</b>
+Suppress generation of the report file.
+<li><b>-r</b>
+Do not sort or renumber the parser states as part of optimization.
+<li><b>-s</b>
+Show parser statistics before exiting.
+<li><b>-T<i>file</i></b>
+Use <i>file</i> as the template for the generated C-code parser implementation.
+<li><b>-x</b>
+Print the Lemon version number.
+</ul>
+
+<a id="interface"></a>
+<h3>3.2 The Parser Interface</h3>
+
+<p>Lemon doesn't generate a complete, working program.  It only generates
+a few subroutines that implement a parser.  This section describes
+the interface to those subroutines.  It is up to the programmer to
+call these subroutines in an appropriate way in order to produce a
+complete system.</p>
+
+<p>Before a program begins using a Lemon-generated parser, the program
+must first create the parser.
+A new parser is created as follows:</p>
+<pre>
+   void *pParser = ParseAlloc( malloc );
+</pre>
+<p>The ParseAlloc() routine allocates and initializes a new parser and
+returns a pointer to it.
+The actual data structure used to represent a parser is opaque &mdash;
+its internal structure is not visible or usable by the calling routine.
+For this reason, the ParseAlloc() routine returns a pointer to void
+rather than a pointer to some particular structure.
+The sole argument to the ParseAlloc() routine is a pointer to the
+subroutine used to allocate memory.  Typically this means malloc().</p>
+
+<p>After a program is finished using a parser, it can reclaim all
+memory allocated by that parser by calling</p>
+<pre>
+   ParseFree(pParser, free);
+</pre>
+<p>The first argument is the same pointer returned by ParseAlloc().  The
+second argument is a pointer to the function used to release bulk
+memory back to the system.</p>
+
+<p>After a parser has been allocated using ParseAlloc(), the programmer
+must supply the parser with a sequence of tokens (terminal symbols) to
+be parsed.  This is accomplished by calling the following function
+once for each token:<p>
+<pre>
+   Parse(pParser, hTokenID, sTokenData, pArg);
+</pre>
+<p>The first argument to the Parse() routine is the pointer returned by
+ParseAlloc().
+The second argument is a small positive integer that tells the parser the
+type of the next token in the data stream.
+There is one token type for each terminal symbol in the grammar.
+The gram.h file generated by Lemon contains #define statements that
+map symbolic terminal symbol names into appropriate integer values.
+A value of 0 for the second argument is a special flag to the
+parser to indicate that the end of input has been reached.
+The third argument is the value of the given token.  By default,
+the type of the third argument is "void*", but the grammar will
+usually redefine this type to be some kind of structure.
+Typically the second argument will be a broad category of tokens
+such as "identifier" or "number" and the third argument will
+be the name of the identifier or the value of the number.</p>
+
+<p>The Parse() function may have either three or four arguments,
+depending on the grammar.  If the grammar specification file requests
+it (via the <tt><a href='#extraarg'>%extra_argument</a></tt> directive),
+the Parse() function will have a fourth parameter that can be
+of any type chosen by the programmer.  The parser doesn't do anything
+with this argument except to pass it through to action routines.
+This is a convenient mechanism for passing state information down
+to the action routines without having to use global variables.</p>
+
+<p>A typical use of a Lemon parser might look something like the
+following:</p>
+<pre>
+    1 ParseTree *ParseFile(const char *zFilename){
+    2    Tokenizer *pTokenizer;
+    3    void *pParser;
+    4    Token sToken;
+    5    int hTokenId;
+    6    ParserState sState;
+    7
+    8    pTokenizer = TokenizerCreate(zFilename);
+    9    pParser = ParseAlloc( malloc );
+   10    InitParserState(&amp;sState);
+   11    while( GetNextToken(pTokenizer, &amp;hTokenId, &amp;sToken) ){
+   12       Parse(pParser, hTokenId, sToken, &amp;sState);
+   13    }
+   14    Parse(pParser, 0, sToken, &amp;sState);
+   15    ParseFree(pParser, free );
+   16    TokenizerFree(pTokenizer);
+   17    return sState.treeRoot;
+   18 }
+</pre>
+<p>This example shows a user-written routine that parses a file of
+text and returns a pointer to the parse tree.
+(All error-handling code is omitted from this example to keep it
+simple.)
+We assume the existence of some kind of tokenizer which is created
+using TokenizerCreate() on line 8 and deleted by TokenizerFree()
+on line 16.  The GetNextToken() function on line 11 retrieves the
+next token from the input file and puts its type in the
+integer variable hTokenId.  The sToken variable is assumed to be
+some kind of structure that contains details about each token,
+such as its complete text, what line it occurs on, etc.</p>
+
+<p>This example also assumes the existence of a structure of type
+ParserState that holds state information about a particular parse.
+An instance of such a structure is created on line 6 and initialized
+on line 10.  A pointer to this structure is passed into the Parse()
+routine as the optional 4th argument.
+The action routine specified by the grammar for the parser can use
+the ParserState structure to hold whatever information is useful and
+appropriate.  In the example, we note that the treeRoot field of
+the ParserState structure is left pointing to the root of the parse
+tree.</p>
+
+<p>The core of this example as it relates to Lemon is as follows:</p>
+<pre>
+   ParseFile(){
+      pParser = ParseAlloc( malloc );
+      while( GetNextToken(pTokenizer,&amp;hTokenId, &amp;sToken) ){
+         Parse(pParser, hTokenId, sToken);
+      }
+      Parse(pParser, 0, sToken);
+      ParseFree(pParser, free );
+   }
+</pre>
+<p>Basically, what a program has to do to use a Lemon-generated parser
+is first create the parser, then send it lots of tokens obtained by
+tokenizing an input source.  When the end of input is reached, the
+Parse() routine should be called one last time with a token type
+of 0.  This step is necessary to inform the parser that the end of
+input has been reached.  Finally, we reclaim memory used by the
+parser by calling ParseFree().</p>
+
+<p>There is one other interface routine that should be mentioned
+before we move on.
+The ParseTrace() function can be used to generate debugging output
+from the parser.  A prototype for this routine is as follows:</p>
+<pre>
+   ParseTrace(FILE *stream, char *zPrefix);
+</pre>
+<p>After this routine is called, a short (one-line) message is written
+to the designated output stream every time the parser changes states
+or calls an action routine.  Each such message is prefaced using
+the text given by zPrefix.  This debugging output can be turned off
+by calling ParseTrace() again with a first argument of NULL (0).</p>
+
+<a id="onstack"></a>
+<h4>3.2.1 Allocating The Parse Object On Stack</h4>
+
+<p>If all calls to the Parse() interface are made from within
+<a href="#pcode"><tt>%code</tt> directives</a>, then the parse
+object can be allocated from the stack rather than from the heap.
+These are the steps:
+
+<ul>
+<li> Declare a local variable of type "yyParser"
+<li> Initialize the variable using ParseInit()
+<li> Pass a pointer to the variable in calls ot Parse()
+<li> Deallocate substructure in the parse variable using ParseFinalize().
+</ul>
+
+<p>The following code illustrates how this is done:
+
+<pre>
+   ParseFile(){
+      yyParser x;
+      ParseInit( &x );
+      while( GetNextToken(pTokenizer,&amp;hTokenId, &amp;sToken) ){
+         Parse(&x, hTokenId, sToken);
+      }
+      Parse(&x, 0, sToken);
+      ParseFinalize( &x );
+   }
+</pre>
+
+<a id="ifsum"></a>
+<h4>3.2.2 Interface Summary</h4>
+
+<p>Here is a quick overview of the C-language interface to a
+Lemon-generated parser:</p>
+
+<blockquote><pre>
+void *ParseAlloc( (void*(*malloc)(size_t) );
+void ParseFree(void *pParser, (void(*free)(void*) );
+void Parse(void *pParser, int tokenCode, ParseTOKENTYPE token, ...);
+void ParseTrace(FILE *stream, char *zPrefix);
+</pre></blockquote>
+
+<p>Notes:</p>
+<ul>
+<li> Use the <a href="#pname"><tt>%name</tt> directive</a> to change
+the "Parse" prefix names of the procedures in the interface.
+<li> Use the <a href="#token_type"><tt>%token_type</tt> directive</a>
+to define the "ParseTOKENTYPE" type.
+<li> Use the <a href="#extraarg"><tt>%extra_argument</tt> directive</a>
+to specify the type and name of the 4th parameter to the
+Parse() function.
+</ul>
+
+<a id="yaccdiff"></a>
+<h3>3.3 Differences With YACC and BISON</h3>
+
+<p>Programmers who have previously used the yacc or bison parser
+generator will notice several important differences between yacc and/or
+bison and Lemon.</p>
+<ul>
+<li>In yacc and bison, the parser calls the tokenizer.  In Lemon,
+    the tokenizer calls the parser.
+<li>Lemon uses no global variables.  Yacc and bison use global variables
+    to pass information between the tokenizer and parser.
+<li>Lemon allows multiple parsers to be running simultaneously.  Yacc
+    and bison do not.
+</ul>
+<p>These differences may cause some initial confusion for programmers
+with prior yacc and bison experience.
+But after years of experience using Lemon, I firmly
+believe that the Lemon way of doing things is better.</p>
+
+<p><i>Updated as of 2016-02-16:</i>
+The text above was written in the 1990s.
+We are told that Bison has lately been enhanced to support the
+tokenizer-calls-parser paradigm used by Lemon, eliminating the
+need for global variables.</p>
+
+<a id="build"><a>
+<h3>3.4 Building The "lemon" or "lemon.exe" Executable</h3>
+
+<p>The "lemon" or "lemon.exe" program is built from a single file
+of C-code named 
+"<a href="https://sqlite.org/src/tool/lemon.c">lemon.c</a>". 
+The Lemon source code is generic C89 code that uses
+no unusual or non-standard libraries.  Any
+reasonable C compiler should suffice to compile the lemon program.  
+A command-line like the following will usually work:</p>
+
+<blockquote><pre>
+cc -o lemon lemon.c
+</pre></blockquote
+
+<p>On Windows machines with Visual C++ installed, bring up a
+"VS20<i>NN</i> x64 Native Tools Command Prompt" window and enter:
+
+<blockquote><pre>
+cl lemon.c
+</pre></blockquote>
+
+<p>Compiling Lemon really is that simple. 
+Additional compiler options such as
+"-O2" or "-g" or "-Wall" can be added if desired, but they are not
+necessary.</p>
+
+
+<a id="syntax"></a>
+<h2>4.0 Input File Syntax</h2>
+
+<p>The main purpose of the grammar specification file for Lemon is
+to define the grammar for the parser.  But the input file also
+specifies additional information Lemon requires to do its job.
+Most of the work in using Lemon is in writing an appropriate
+grammar file.</p>
+
+<p>The grammar file for Lemon is, for the most part, a free format.
+It does not have sections or divisions like yacc or bison.  Any
+declaration can occur at any point in the file.  Lemon ignores
+whitespace (except where it is needed to separate tokens), and it
+honors the same commenting conventions as C and C++.</p>
+
+<a id="tnt"></a>
+<h3>4.1 Terminals and Nonterminals</h3>
+
+<p>A terminal symbol (token) is any string of alphanumeric
+and/or underscore characters
+that begins with an uppercase letter.
+A terminal can contain lowercase letters after the first character,
+but the usual convention is to make terminals all uppercase.
+A nonterminal, on the other hand, is any string of alphanumeric
+and underscore characters than begins with a lowercase letter.
+Again, the usual convention is to make nonterminals use all lowercase
+letters.</p>
+
+<p>In Lemon, terminal and nonterminal symbols do not need to
+be declared or identified in a separate section of the grammar file.
+Lemon is able to generate a list of all terminals and nonterminals
+by examining the grammar rules, and it can always distinguish a
+terminal from a nonterminal by checking the case of the first
+character of the name.</p>
+
+<p>Yacc and bison allow terminal symbols to have either alphanumeric
+names or to be individual characters included in single quotes, like
+this: ')' or '$'.  Lemon does not allow this alternative form for
+terminal symbols.  With Lemon, all symbols, terminals and nonterminals,
+must have alphanumeric names.</p>
+
+<a id="rules"></a>
+<h3>4.2 Grammar Rules</h3>
+
+<p>The main component of a Lemon grammar file is a sequence of grammar
+rules.
+Each grammar rule consists of a nonterminal symbol followed by
+the special symbol "::=" and then a list of terminals and/or nonterminals.
+The rule is terminated by a period.
+The list of terminals and nonterminals on the right-hand side of the
+rule can be empty.
+Rules can occur in any order, except that the left-hand side of the
+first rule is assumed to be the start symbol for the grammar (unless
+specified otherwise using the <tt><a href='#start_symbol'>%start_symbol</a></tt>
+directive described below.)
+A typical sequence of grammar rules might look something like this:</p>
+<pre>
+  expr ::= expr PLUS expr.
+  expr ::= expr TIMES expr.
+  expr ::= LPAREN expr RPAREN.
+  expr ::= VALUE.
+</pre>
+
+<p>There is one non-terminal in this example, "expr", and five
+terminal symbols or tokens: "PLUS", "TIMES", "LPAREN",
+"RPAREN" and "VALUE".</p>
+
+<p>Like yacc and bison, Lemon allows the grammar to specify a block
+of C code that will be executed whenever a grammar rule is reduced
+by the parser.
+In Lemon, this action is specified by putting the C code (contained
+within curly braces <tt>{...}</tt>) immediately after the
+period that closes the rule.
+For example:</p>
+<pre>
+  expr ::= expr PLUS expr.   { printf("Doing an addition...\n"); }
+</pre>
+
+<p>In order to be useful, grammar actions must normally be linked to
+their associated grammar rules.
+In yacc and bison, this is accomplished by embedding a "$$" in the
+action to stand for the value of the left-hand side of the rule and
+symbols "$1", "$2", and so forth to stand for the value of
+the terminal or nonterminal at position 1, 2 and so forth on the
+right-hand side of the rule.
+This idea is very powerful, but it is also very error-prone.  The
+single most common source of errors in a yacc or bison grammar is
+to miscount the number of symbols on the right-hand side of a grammar
+rule and say "$7" when you really mean "$8".</p>
+
+<p>Lemon avoids the need to count grammar symbols by assigning symbolic
+names to each symbol in a grammar rule and then using those symbolic
+names in the action.
+In yacc or bison, one would write this:</p>
+<pre>
+  expr -&gt; expr PLUS expr  { $$ = $1 + $3; };
+</pre>
+<p>But in Lemon, the same rule becomes the following:</p>
+<pre>
+  expr(A) ::= expr(B) PLUS expr(C).  { A = B+C; }
+</pre>
+<p>In the Lemon rule, any symbol in parentheses after a grammar rule
+symbol becomes a place holder for that symbol in the grammar rule.
+This place holder can then be used in the associated C action to
+stand for the value of that symbol.</p>
+
+<p>The Lemon notation for linking a grammar rule with its reduce
+action is superior to yacc/bison on several counts.
+First, as mentioned above, the Lemon method avoids the need to
+count grammar symbols.
+Secondly, if a terminal or nonterminal in a Lemon grammar rule
+includes a linking symbol in parentheses but that linking symbol
+is not actually used in the reduce action, then an error message
+is generated.
+For example, the rule</p>
+<pre>
+  expr(A) ::= expr(B) PLUS expr(C).  { A = B; }
+</pre>
+<p>will generate an error because the linking symbol "C" is used
+in the grammar rule but not in the reduce action.</p>
+
+<p>The Lemon notation for linking grammar rules to reduce actions
+also facilitates the use of destructors for reclaiming memory
+allocated by the values of terminals and nonterminals on the
+right-hand side of a rule.</p>
+
+<a id='precrules'></a>
+<h3>4.3 Precedence Rules</h3>
+
+<p>Lemon resolves parsing ambiguities in exactly the same way as
+yacc and bison.  A shift-reduce conflict is resolved in favor
+of the shift, and a reduce-reduce conflict is resolved by reducing
+whichever rule comes first in the grammar file.</p>
+
+<p>Just like in
+yacc and bison, Lemon allows a measure of control
+over the resolution of parsing conflicts using precedence rules.
+A precedence value can be assigned to any terminal symbol
+using the
+<tt><a href='#pleft'>%left</a></tt>,
+<tt><a href='#pright'>%right</a></tt> or
+<tt><a href='#pnonassoc'>%nonassoc</a></tt> directives.  Terminal symbols
+mentioned in earlier directives have a lower precedence than
+terminal symbols mentioned in later directives.  For example:</p>
+
+<pre>
+   %left AND.
+   %left OR.
+   %nonassoc EQ NE GT GE LT LE.
+   %left PLUS MINUS.
+   %left TIMES DIVIDE MOD.
+   %right EXP NOT.
+</pre>
+
+<p>In the preceding sequence of directives, the AND operator is
+defined to have the lowest precedence.  The OR operator is one
+precedence level higher.  And so forth.  Hence, the grammar would
+attempt to group the ambiguous expression</p>
+<pre>
+     a AND b OR c
+</pre>
+<p>like this</p>
+<pre>
+     a AND (b OR c).
+</pre>
+<p>The associativity (left, right or nonassoc) is used to determine
+the grouping when the precedence is the same.  AND is left-associative
+in our example, so</p>
+<pre>
+     a AND b AND c
+</pre>
+<p>is parsed like this</p>
+<pre>
+     (a AND b) AND c.
+</pre>
+<p>The EXP operator is right-associative, though, so</p>
+<pre>
+     a EXP b EXP c
+</pre>
+<p>is parsed like this</p>
+<pre>
+     a EXP (b EXP c).
+</pre>
+<p>The nonassoc precedence is used for non-associative operators.
+So</p>
+<pre>
+     a EQ b EQ c
+</pre>
+<p>is an error.</p>
+
+<p>The precedence of non-terminals is transferred to rules as follows:
+The precedence of a grammar rule is equal to the precedence of the
+left-most terminal symbol in the rule for which a precedence is
+defined.  This is normally what you want, but in those cases where
+you want the precedence of a grammar rule to be something different,
+you can specify an alternative precedence symbol by putting the
+symbol in square braces after the period at the end of the rule and
+before any C-code.  For example:</p>
+
+<pre>
+   expr = MINUS expr.  [NOT]
+</pre>
+
+<p>This rule has a precedence equal to that of the NOT symbol, not the
+MINUS symbol as would have been the case by default.</p>
+
+<p>With the knowledge of how precedence is assigned to terminal
+symbols and individual
+grammar rules, we can now explain precisely how parsing conflicts
+are resolved in Lemon.  Shift-reduce conflicts are resolved
+as follows:</p>
+<ul>
+<li> If either the token to be shifted or the rule to be reduced
+     lacks precedence information, then resolve in favor of the
+     shift, but report a parsing conflict.
+<li> If the precedence of the token to be shifted is greater than
+     the precedence of the rule to reduce, then resolve in favor
+     of the shift.  No parsing conflict is reported.
+<li> If the precedence of the token to be shifted is less than the
+     precedence of the rule to reduce, then resolve in favor of the
+     reduce action.  No parsing conflict is reported.
+<li> If the precedences are the same and the shift token is
+     right-associative, then resolve in favor of the shift.
+     No parsing conflict is reported.
+<li> If the precedences are the same and the shift token is
+     left-associative, then resolve in favor of the reduce.
+     No parsing conflict is reported.
+<li> Otherwise, resolve the conflict by doing the shift, and
+     report a parsing conflict.
+</ul>
+<p>Reduce-reduce conflicts are resolved this way:</p>
+<ul>
+<li> If either reduce rule
+     lacks precedence information, then resolve in favor of the
+     rule that appears first in the grammar, and report a parsing
+     conflict.
+<li> If both rules have precedence and the precedence is different,
+     then resolve the dispute in favor of the rule with the highest
+     precedence, and do not report a conflict.
+<li> Otherwise, resolve the conflict by reducing by the rule that
+     appears first in the grammar, and report a parsing conflict.
+</ul>
+
+<a id="special"></a>
+<h3>4.4 Special Directives</h3>
+
+<p>The input grammar to Lemon consists of grammar rules and special
+directives.  We've described all the grammar rules, so now we'll
+talk about the special directives.</p>
+
+<p>Directives in Lemon can occur in any order.  You can put them before
+the grammar rules, or after the grammar rules, or in the midst of the
+grammar rules.  It doesn't matter.  The relative order of
+directives used to assign precedence to terminals is important, but
+other than that, the order of directives in Lemon is arbitrary.</p>
+
+<p>Lemon supports the following special directives:</p>
+<ul>
+<li><tt><a href='#pcode'>%code</a></tt>
+<li><tt><a href='#default_destructor'>%default_destructor</a></tt>
+<li><tt><a href='#default_type'>%default_type</a></tt>
+<li><tt><a href='#destructor'>%destructor</a></tt>
+<li><tt><a href='#pifdef'>%else</a></tt>
+<li><tt><a href='#pifdef'>%endif</a></tt>
+<li><tt><a href='#extraarg'>%extra_argument</a></tt>
+<li><tt><a href='#pfallback'>%fallback</a></tt>
+<li><tt><a href='#pifdef'>%if</a></tt>
+<li><tt><a href='#pifdef'>%ifdef</a></tt>
+<li><tt><a href='#pifdef'>%ifndef</a></tt>
+<li><tt><a href='#pinclude'>%include</a></tt>
+<li><tt><a href='#pleft'>%left</a></tt>
+<li><tt><a href='#pname'>%name</a></tt>
+<li><tt><a href='#pnonassoc'>%nonassoc</a></tt>
+<li><tt><a href='#parse_accept'>%parse_accept</a></tt>
+<li><tt><a href='#parse_failure'>%parse_failure</a></tt>
+<li><tt><a href='#pright'>%right</a></tt>
+<li><tt><a href='#stack_overflow'>%stack_overflow</a></tt>
+<li><tt><a href='#stack_size'>%stack_size</a></tt>
+<li><tt><a href='#start_symbol'>%start_symbol</a></tt>
+<li><tt><a href='#syntax_error'>%syntax_error</a></tt>
+<li><tt><a href='#token'>%token</a></tt>
+<li><tt><a href='#token_class'>%token_class</a></tt>
+<li><tt><a href='#token_destructor'>%token_destructor</a></tt>
+<li><tt><a href='#token_prefix'>%token_prefix</a></tt>
+<li><tt><a href='#token_type'>%token_type</a></tt>
+<li><tt><a href='#ptype'>%type</a></tt>
+<li><tt><a href='#pwildcard'>%wildcard</a></tt>
+</ul>
+<p>Each of these directives will be described separately in the
+following sections:</p>
+
+<a id='pcode'></a>
+<h4>4.4.1 The <tt>%code</tt> directive</h4>
+
+<p>The <tt>%code</tt> directive is used to specify additional C code that
+is added to the end of the main output file.  This is similar to
+the <tt><a href='#pinclude'>%include</a></tt> directive except that
+<tt>%include</tt> is inserted at the beginning of the main output file.</p>
+
+<p><tt>%code</tt> is typically used to include some action routines or perhaps
+a tokenizer or even the "main()" function
+as part of the output file.</p>
+
+<p>There can be multiple <tt>%code</tt> directives.  The arguments of
+all <tt>%code</tt> directives are concatenated.</p>
+
+<a id='default_destructor'></a>
+<h4>4.4.2 The <tt>%default_destructor</tt> directive</h4>
+
+<p>The <tt>%default_destructor</tt> directive specifies a destructor to
+use for non-terminals that do not have their own destructor
+specified by a separate <tt>%destructor</tt> directive.  See the documentation
+on the <tt><a href='#destructor'>%destructor</a></tt> directive below for
+additional information.</p>
+
+<p>In some grammars, many different non-terminal symbols have the
+same data type and hence the same destructor.  This directive is
+a convenient way to specify the same destructor for all those
+non-terminals using a single statement.</p>
+
+<a id='default_type'></a>
+<h4>4.4.3 The <tt>%default_type</tt> directive</h4>
+
+<p>The <tt>%default_type</tt> directive specifies the data type of non-terminal
+symbols that do not have their own data type defined using a separate
+<tt><a href='#ptype'>%type</a></tt> directive.</p>
+
+<a id='destructor'></a>
+<h4>4.4.4 The <tt>%destructor</tt> directive</h4>
+
+<p>The <tt>%destructor</tt> directive is used to specify a destructor for
+a non-terminal symbol.
+(See also the <tt><a href='#token_destructor'>%token_destructor</a></tt>
+directive which is used to specify a destructor for terminal symbols.)</p>
+
+<p>A non-terminal's destructor is called to dispose of the
+non-terminal's value whenever the non-terminal is popped from
+the stack.  This includes all of the following circumstances:</p>
+<ul>
+<li> When a rule reduces and the value of a non-terminal on
+     the right-hand side is not linked to C code.
+<li> When the stack is popped during error processing.
+<li> When the ParseFree() function runs.
+</ul>
+<p>The destructor can do whatever it wants with the value of
+the non-terminal, but its design is to deallocate memory
+or other resources held by that non-terminal.</p>
+
+<p>Consider an example:</p>
+<pre>
+   %type nt {void*}
+   %destructor nt { free($$); }
+   nt(A) ::= ID NUM.   { A = malloc( 100 ); }
+</pre>
+<p>This example is a bit contrived, but it serves to illustrate how
+destructors work.  The example shows a non-terminal named
+"nt" that holds values of type "void*".  When the rule for
+an "nt" reduces, it sets the value of the non-terminal to
+space obtained from malloc().  Later, when the nt non-terminal
+is popped from the stack, the destructor will fire and call
+free() on this malloced space, thus avoiding a memory leak.
+(Note that the symbol "$$" in the destructor code is replaced
+by the value of the non-terminal.)</p>
+
+<p>It is important to note that the value of a non-terminal is passed
+to the destructor whenever the non-terminal is removed from the
+stack, unless the non-terminal is used in a C-code action.  If
+the non-terminal is used by C-code, then it is assumed that the
+C-code will take care of destroying it.
+More commonly, the value is used to build some
+larger structure, and we don't want to destroy it, which is why
+the destructor is not called in this circumstance.</p>
+
+<p>Destructors help avoid memory leaks by automatically freeing
+allocated objects when they go out of scope.
+To do the same using yacc or bison is much more difficult.</p>
+
+<a id='extraarg'></a>
+<h4>4.4.5 The <tt>%extra_argument</tt> directive</h4>
+
+<p>The <tt>%extra_argument</tt> directive instructs Lemon to add a 4th parameter
+to the parameter list of the Parse() function it generates.  Lemon
+doesn't do anything itself with this extra argument, but it does
+make the argument available to C-code action routines, destructors,
+and so forth.  For example, if the grammar file contains:</p>
+
+<pre>
+    %extra_argument { MyStruct *pAbc }
+</pre>
+
+<p>Then the Parse() function generated will have an 4th parameter
+of type "MyStruct*" and all action routines will have access to
+a variable named "pAbc" that is the value of the 4th parameter
+in the most recent call to Parse().</p>
+
+<p>The <tt>%extra_context</tt> directive works the same except that it
+is passed in on the ParseAlloc() or ParseInit() routines instead of
+on Parse().</p>
+
+<a id='extractx'></a>
+<h4>4.4.6 The <tt>%extra_context</tt> directive</h4>
+
+<p>The <tt>%extra_context</tt> directive instructs Lemon to add a 2nd parameter
+to the parameter list of the ParseAlloc() and ParseInit() functions.  Lemon
+doesn't do anything itself with these extra argument, but it does
+store the value make it available to C-code action routines, destructors,
+and so forth.  For example, if the grammar file contains:</p>
+
+<pre>
+    %extra_context { MyStruct *pAbc }
+</pre>
+
+<p>Then the ParseAlloc() and ParseInit() functions will have an 2nd parameter
+of type "MyStruct*" and all action routines will have access to
+a variable named "pAbc" that is the value of that 2nd parameter.</p>
+
+<p>The <tt>%extra_argument</tt> directive works the same except that it
+is passed in on the Parse() routine instead of on ParseAlloc()/ParseInit().</p>
+
+<a id='pfallback'></a>
+<h4>4.4.7 The <tt>%fallback</tt> directive</h4>
+
+<p>The <tt>%fallback</tt> directive specifies an alternative meaning for one
+or more tokens.  The alternative meaning is tried if the original token
+would have generated a syntax error.</p>
+
+<p>The <tt>%fallback</tt> directive was added to support robust parsing of SQL
+syntax in <a href='https://www.sqlite.org/'>SQLite</a>.
+The SQL language contains a large assortment of keywords, each of which
+appears as a different token to the language parser.  SQL contains so
+many keywords that it can be difficult for programmers to keep up with
+them all.  Programmers will, therefore, sometimes mistakenly use an
+obscure language keyword for an identifier.  The <tt>%fallback</tt> directive
+provides a mechanism to tell the parser:  "If you are unable to parse
+this keyword, try treating it as an identifier instead."</p>
+
+<p>The syntax of <tt>%fallback</tt> is as follows:</p>
+
+<blockquote>
+<tt>%fallback</tt> <i>ID</i> <i>TOKEN...</i> <b>.</b>
+</blockquote></p>
+
+<p>In words, the <tt>%fallback</tt> directive is followed by a list of token
+names terminated by a period.
+The first token name is the fallback token &mdash; the
+token to which all the other tokens fall back to.  The second and subsequent
+arguments are tokens which fall back to the token identified by the first
+argument.</p>
+
+<a id='pifdef'></a>
+<h4>4.4.8 The <tt>%if</tt> directive and its friends</h4>
+
+<p>The <tt>%if</tt>, <tt>%ifdef</tt>, <tt>%ifndef</tt>, <tt>%else</tt>,
+and <tt>%endif</tt> directives
+are similar to #if, #ifdef, #ifndef, #else, and #endif in the C-preprocessor,
+just not as general.
+Each of these directives must begin at the left margin.  No whitespace
+is allowed between the "%" and the directive name.</p>
+
+<p>Grammar text in between "<tt>%ifdef MACRO</tt>" and the next nested
+"<tt>%endif</tt>" is
+ignored unless the "-DMACRO" command-line option is used.  Grammar text
+betwen "<tt>%ifndef MACRO</tt>" and the next nested "<tt>%endif</tt>" is
+included except when the "-DMACRO" command-line option is used.<p>
+
+<p>The text in between "<tt>%if</tt> <i>CONDITIONAL</i>" and its
+corresponding <tt>%endif</tt> is included only if <i>CONDITIONAL</i>
+is true.  The CONDITION is one or more macro names, optionally connected
+using the "||" and "&amp;&amp;" binary operators, the "!" unary operator,
+and grouped using balanced parentheses.  Each term is true if the
+corresponding macro exists, and false if it does not exist.</p>
+
+<p>An optional "<tt>%else</tt>" directive can occur anywhere in between a 
+<tt>%ifdef</tt>, <tt>%ifndef</tt>, or <tt>%if</tt> directive and
+its corresponding <tt>%endif</tt>.</p>
+
+<p>Note that the argument to <tt>%ifdef</tt> and <tt>%ifndef</tt> is
+intended to be a single preprocessor symbol name, not a general expression.
+Use the "<tt>%if</tt>" directive for general expressions.</p>
+
+<a id='pinclude'></a>
+<h4>4.4.9 The <tt>%include</tt> directive</h4>
+
+<p>The <tt>%include</tt> directive specifies C code that is included at the
+top of the generated parser.  You can include any text you want &mdash;
+the Lemon parser generator copies it blindly.  If you have multiple
+<tt>%include</tt> directives in your grammar file, their values are concatenated
+so that all <tt>%include</tt> code ultimately appears near the top of the
+generated parser, in the same order as it appeared in the grammar.</p>
+
+<p>The <tt>%include</tt> directive is very handy for getting some extra #include
+preprocessor statements at the beginning of the generated parser.
+For example:</p>
+
+<pre>
+   %include {#include &lt;unistd.h&gt;}
+</pre>
+
+<p>This might be needed, for example, if some of the C actions in the
+grammar call functions that are prototyped in unistd.h.</p>
+
+<p>Use the <tt><a href="#pcode">%code</a></tt> directive to add code to
+the end of the generated parser.</p>
+
+<a id='pleft'></a>
+<h4>4.4.10 The <tt>%left</tt> directive</h4>
+
+The <tt>%left</tt> directive is used (along with the
+<tt><a href='#pright'>%right</a></tt> and
+<tt><a href='#pnonassoc'>%nonassoc</a></tt> directives) to declare
+precedences of terminal symbols.
+Every terminal symbol whose name appears after
+a <tt>%left</tt> directive but before the next period (".") is
+given the same left-associative precedence value.  Subsequent
+<tt>%left</tt> directives have higher precedence.  For example:</p>
+
+<pre>
+   %left AND.
+   %left OR.
+   %nonassoc EQ NE GT GE LT LE.
+   %left PLUS MINUS.
+   %left TIMES DIVIDE MOD.
+   %right EXP NOT.
+</pre>
+
+<p>Note the period that terminates each <tt>%left</tt>,
+<tt>%right</tt> or <tt>%nonassoc</tt>
+directive.</p>
+
+<p>LALR(1) grammars can get into a situation where they require
+a large amount of stack space if you make heavy use or right-associative
+operators.  For this reason, it is recommended that you use <tt>%left</tt>
+rather than <tt>%right</tt> whenever possible.</p>
+
+<a id='pname'></a>
+<h4>4.4.11 The <tt>%name</tt> directive</h4>
+
+<p>By default, the functions generated by Lemon all begin with the
+five-character string "Parse".  You can change this string to something
+different using the <tt>%name</tt> directive.  For instance:</p>
+
+<pre>
+   %name Abcde
+</pre>
+
+<p>Putting this directive in the grammar file will cause Lemon to generate
+functions named</p>
+<ul>
+<li> AbcdeAlloc(),
+<li> AbcdeFree(),
+<li> AbcdeTrace(), and
+<li> Abcde().
+</ul>
+</p>The <tt>%name</tt> directive allows you to generate two or more different
+parsers and link them all into the same executable.</p>
+
+<a id='pnonassoc'></a>
+<h4>4.4.12 The <tt>%nonassoc</tt> directive</h4>
+
+<p>This directive is used to assign non-associative precedence to
+one or more terminal symbols.  See the section on
+<a href='#precrules'>precedence rules</a>
+or on the <tt><a href='#pleft'>%left</a></tt> directive
+for additional information.</p>
+
+<a id='parse_accept'></a>
+<h4>4.4.13 The <tt>%parse_accept</tt> directive</h4>
+
+<p>The <tt>%parse_accept</tt> directive specifies a block of C code that is
+executed whenever the parser accepts its input string.  To "accept"
+an input string means that the parser was able to process all tokens
+without error.</p>
+
+<p>For example:</p>
+
+<pre>
+   %parse_accept {
+      printf("parsing complete!\n");
+   }
+</pre>
+
+<a id='parse_failure'></a>
+<h4>4.4.14 The <tt>%parse_failure</tt> directive</h4>
+
+<p>The <tt>%parse_failure</tt> directive specifies a block of C code that
+is executed whenever the parser fails complete.  This code is not
+executed until the parser has tried and failed to resolve an input
+error using is usual error recovery strategy.  The routine is
+only invoked when parsing is unable to continue.</p>
+
+<pre>
+   %parse_failure {
+     fprintf(stderr,"Giving up.  Parser is hopelessly lost...\n");
+   }
+</pre>
+
+<a id='pright'></a>
+<h4>4.4.15 The <tt>%right</tt> directive</h4>
+
+<p>This directive is used to assign right-associative precedence to
+one or more terminal symbols.  See the section on
+<a href='#precrules'>precedence rules</a>
+or on the <a href='#pleft'>%left</a> directive for additional information.</p>
+
+<a id='stack_overflow'></a>
+<h4>4.4.16 The <tt>%stack_overflow</tt> directive</h4>
+
+<p>The <tt>%stack_overflow</tt> directive specifies a block of C code that
+is executed if the parser's internal stack ever overflows.  Typically
+this just prints an error message.  After a stack overflow, the parser
+will be unable to continue and must be reset.</p>
+
+<pre>
+   %stack_overflow {
+     fprintf(stderr,"Giving up.  Parser stack overflow\n");
+   }
+</pre>
+
+<p>You can help prevent parser stack overflows by avoiding the use
+of right recursion and right-precedence operators in your grammar.
+Use left recursion and and left-precedence operators instead to
+encourage rules to reduce sooner and keep the stack size down.
+For example, do rules like this:</p>
+<pre>
+   list ::= list element.      // left-recursion.  Good!
+   list ::= .
+</pre>
+<p>Not like this:</p>
+<pre>
+   list ::= element list.      // right-recursion.  Bad!
+   list ::= .
+</pre>
+
+<a id='stack_size'></a>
+<h4>4.4.17 The <tt>%stack_size</tt> directive</h4>
+
+<p>If stack overflow is a problem and you can't resolve the trouble
+by using left-recursion, then you might want to increase the size
+of the parser's stack using this directive.  Put an positive integer
+after the <tt>%stack_size</tt> directive and Lemon will generate a parse
+with a stack of the requested size.  The default value is 100.</p>
+
+<pre>
+   %stack_size 2000
+</pre>
+
+<a id='start_symbol'></a>
+<h4>4.4.18 The <tt>%start_symbol</tt> directive</h4>
+
+<p>By default, the start symbol for the grammar that Lemon generates
+is the first non-terminal that appears in the grammar file.  But you
+can choose a different start symbol using the
+<tt>%start_symbol</tt> directive.</p>
+
+<pre>
+   %start_symbol  prog
+</pre>
+
+<a id='syntax_error'></a>
+<h4>4.4.19 The <tt>%syntax_error</tt> directive</h4>
+
+<p>See <a href='#errors'>Error Processing</a>.</p>
+
+<a id='token'></a>
+<h4>4.4.20 The <tt>%token</tt> directive</h4>
+
+<p>Tokens are normally created automatically, the first time they are used.
+Any identifier that begins with an upper-case letter is a token.
+
+<p>Sometimes it is useful to declare tokens in advance, however.  The
+integer values assigned to each token determined by the order in which
+the tokens are seen.  So by declaring tokens in advance, it is possible to
+cause some tokens to have low-numbered values, which might be desirable in
+some grammers, or to have sequential values assigned to a sequence of
+related tokens.  For this reason, the %token directive is provided to
+declare tokens in advance.  The syntax is as follows:
+
+<blockquote>
+<tt>%token</tt> <i>TOKEN</i> <i>TOKEN...</i> <b>.</b>
+</blockquote></p>
+
+<p>The %token directive is followed by zero or more token symbols and
+terminated by a single ".".  Each token named is created if it does not
+already exist.  Tokens are created in order.
+
+
+<a id='token_class'></a>
+<h4>4.4.21 The <tt>%token_class</tt> directive</h4>
+
+<p>Undocumented.  Appears to be related to the MULTITERMINAL concept.
+<a href='http://sqlite.org/src/fdiff?v1=796930d5fc2036c7&v2=624b24c5dc048e09&sbs=0'>Implementation</a>.</p>
+
+<a id='token_destructor'></a>
+<h4>4.4.22 The <tt>%token_destructor</tt> directive</h4>
+
+<p>The <tt>%destructor</tt> directive assigns a destructor to a non-terminal
+symbol.  (See the description of the
+<tt><a href='%destructor'>%destructor</a></tt> directive above.)
+The <tt>%token_destructor</tt> directive does the same thing
+for all terminal symbols.</p>
+
+<p>Unlike non-terminal symbols, which may each have a different data type
+for their values, terminals all use the same data type (defined by
+the <tt><a href='#token_type'>%token_type</a></tt> directive)
+and so they use a common destructor.
+Other than that, the token destructor works just like the non-terminal
+destructors.</p>
+
+<a id='token_prefix'></a>
+<h4>4.4.23 The <tt>%token_prefix</tt> directive</h4>
+
+<p>Lemon generates #defines that assign small integer constants
+to each terminal symbol in the grammar.  If desired, Lemon will
+add a prefix specified by this directive
+to each of the #defines it generates.</p>
+
+<p>So if the default output of Lemon looked like this:</p>
+<pre>
+    #define AND              1
+    #define MINUS            2
+    #define OR               3
+    #define PLUS             4
+</pre>
+<p>You can insert a statement into the grammar like this:</p>
+<pre>
+    %token_prefix    TOKEN_
+</pre>
+<p>to cause Lemon to produce these symbols instead:</p>
+<pre>
+    #define TOKEN_AND        1
+    #define TOKEN_MINUS      2
+    #define TOKEN_OR         3
+    #define TOKEN_PLUS       4
+</pre>
+
+<a id='token_type'></a><a id='ptype'></a>
+<h4>4.4.24 The <tt>%token_type</tt> and <tt>%type</tt> directives</h4>
+
+<p>These directives are used to specify the data types for values
+on the parser's stack associated with terminal and non-terminal
+symbols.  The values of all terminal symbols must be of the same
+type.  This turns out to be the same data type as the 3rd parameter
+to the Parse() function generated by Lemon.  Typically, you will
+make the value of a terminal symbol be a pointer to some kind of
+token structure.  Like this:</p>
+
+<pre>
+   %token_type    {Token*}
+</pre>
+
+<p>If the data type of terminals is not specified, the default value
+is "void*".</p>
+
+<p>Non-terminal symbols can each have their own data types.  Typically
+the data type of a non-terminal is a pointer to the root of a parse tree
+structure that contains all information about that non-terminal.
+For example:</p>
+
+<pre>
+   %type   expr  {Expr*}
+</pre>
+
+<p>Each entry on the parser's stack is actually a union containing
+instances of all data types for every non-terminal and terminal symbol.
+Lemon will automatically use the correct element of this union depending
+on what the corresponding non-terminal or terminal symbol is.  But
+the grammar designer should keep in mind that the size of the union
+will be the size of its largest element.  So if you have a single
+non-terminal whose data type requires 1K of storage, then your 100
+entry parser stack will require 100K of heap space.  If you are willing
+and able to pay that price, fine.  You just need to know.</p>
+
+<a id='pwildcard'></a>
+<h4>4.4.25 The <tt>%wildcard</tt> directive</h4>
+
+<p>The <tt>%wildcard</tt> directive is followed by a single token name and a
+period.  This directive specifies that the identified token should
+match any input token.</p>
+
+<p>When the generated parser has the choice of matching an input against
+the wildcard token and some other token, the other token is always used.
+The wildcard token is only matched if there are no alternatives.</p>
+
+<a id='errors'></a>
+<h2>5.0 Error Processing</h2>
+
+<p>After extensive experimentation over several years, it has been
+discovered that the error recovery strategy used by yacc is about
+as good as it gets.  And so that is what Lemon uses.</p>
+
+<p>When a Lemon-generated parser encounters a syntax error, it
+first invokes the code specified by the <tt>%syntax_error</tt> directive, if
+any.  It then enters its error recovery strategy.  The error recovery
+strategy is to begin popping the parsers stack until it enters a
+state where it is permitted to shift a special non-terminal symbol
+named "error".  It then shifts this non-terminal and continues
+parsing.  The <tt>%syntax_error</tt> routine will not be called again
+until at least three new tokens have been successfully shifted.</p>
+
+<p>If the parser pops its stack until the stack is empty, and it still
+is unable to shift the error symbol, then the
+<tt><a href='#parse_failure'>%parse_failure</a></tt> routine
+is invoked and the parser resets itself to its start state, ready
+to begin parsing a new file.  This is what will happen at the very
+first syntax error, of course, if there are no instances of the
+"error" non-terminal in your grammar.</p>
+
+<a id='history'></a>
+<h2>6.0 History of Lemon</h2>
+
+<p>Lemon was originally written by Richard Hipp sometime in the late
+1980s on a Sun4 Workstation using K&amp;R C.  
+There was a companion LL(1) parser generator program named "Lime", the
+source code to which as been lost.</p>
+
+<p>The lemon.c source file was originally many separate files that were
+compiled together to generate the "lemon" executable.  Sometime in the
+1990s, the individual source code files were combined together into
+the current single large "lemon.c" source file.  You can still see traces
+of original filenames in the code.</p>
+
+<p>Since 2001, Lemon has been part of the 
+<a href="https://sqlite.org/">SQLite project</a> and the source code
+to Lemon has been managed as a part of the 
+<a href="https://sqlite.org/src">SQLite source tree</a> in the following
+files:</p>
+
+<ul>
+<li> <a href="https://sqlite.org/src/file/tool/lemon.c">tool/lemon.c</a>
+<li> <a href="https://sqlite.org/src/file/tool/lempar.c">tool/lempar.c</a>
+<li> <a href="https://sqlite.org/src/file/doc/lemon.html">doc/lemon.html</a>
+</ul>
+
+<a id="copyright"></a>
+<h2>7.0 Copyright</h2>
+
+<p>All of the source code to Lemon, including the template parser file
+"lempar.c" and this documentation file ("lemon.html") are in the public
+domain.  You can use the code for any purpose and without attribution.</p>
+
+<p>The code comes with no warranty.  If it breaks, you get to keep both
+pieces.</p>
+
+</body>
+</html>
diff --git a/doc/pager-invariants.txt b/doc/pager-invariants.txt
new file mode 100644
index 0000000..44444da
--- /dev/null
+++ b/doc/pager-invariants.txt
@@ -0,0 +1,76 @@
+ *** Throughout this document, a page is deemed to have been synced
+     automatically as soon as it is written when PRAGMA synchronous=OFF.
+     Otherwise, the page is not synced until the xSync method of the VFS
+     is called successfully on the file containing the page.
+
+ *** Definition:  A page of the database file is said to be "overwriteable" if
+     one or more of the following are true about the page:
+ 
+     (a)  The original content of the page as it was at the beginning of
+          the transaction has been written into the rollback journal and
+          synced.
+ 
+     (b)  The page was a freelist leaf page at the start of the transaction.
+ 
+     (c)  The page number is greater than the largest page that existed in
+          the database file at the start of the transaction.
+ 
+ (1) A page of the database file is never overwritten unless one of the
+     following are true:
+ 
+     (a) The page and all other pages on the same sector are overwriteable.
+ 
+     (b) The atomic page write optimization is enabled, and the entire
+         transaction other than the update of the transaction sequence
+         number consists of a single page change.
+ 
+ (2) The content of a page written into the rollback journal exactly matches
+     both the content in the database when the rollback journal was written
+     and the content in the database at the beginning of the current
+     transaction.
+ 
+ (3) Writes to the database file are an integer multiple of the page size
+     in length and are aligned to a page boundary.
+ 
+ (4) Reads from the database file are either aligned on a page boundary and
+     an integer multiple of the page size in length or are taken from the
+     first 100 bytes of the database file.
+ 
+ (5) All writes to the database file are synced prior to the rollback journal
+     being deleted, truncated, or zeroed.
+ 
+ (6) If a master journal file is used, then all writes to the database file
+     are synced prior to the master journal being deleted.
+ 
+ *** Definition: Two databases (or the same database at two points it time)
+     are said to be "logically equivalent" if they give the same answer to
+     all queries.  Note in particular the content of freelist leaf
+     pages can be changed arbitarily without effecting the logical equivalence
+     of the database.
+ 
+ (7) At any time, if any subset, including the empty set and the total set,
+     of the unsynced changes to a rollback journal are removed and the 
+     journal is rolled back, the resulting database file will be logical
+     equivalent to the database file at the beginning of the transaction.
+ 
+ (8) When a transaction is rolled back, the xTruncate method of the VFS
+     is called to restore the database file to the same size it was at
+     the beginning of the transaction.  (In some VFSes, the xTruncate
+     method is a no-op, but that does not change the fact the SQLite will
+     invoke it.)
+ 
+ (9) Whenever the database file is modified, at least one bit in the range
+     of bytes from 24 through 39 inclusive will be changed prior to releasing
+     the EXCLUSIVE lock.
+
+(10) The pattern of bits in bytes 24 through 39 shall not repeat in less
+     than one billion transactions.
+
+(11) A database file is well-formed at the beginning and at the conclusion
+     of every transaction.
+
+(12) An EXCLUSIVE lock must be held on the database file before making
+     any changes to the database file.
+
+(13) A SHARED lock must be held on the database file before reading any
+     content out of the database file.
diff --git a/doc/trusted-schema.md b/doc/trusted-schema.md
new file mode 100644
index 0000000..d431fd4
--- /dev/null
+++ b/doc/trusted-schema.md
@@ -0,0 +1,142 @@
+# The new-security-options branch
+
+## The problem that the [new-security-options](/timeline?r=new-security-options) branch tries to solve
+
+An attacker might modify the schema of an SQLite database by adding
+structures that cause code to run when some other application opens and
+reads the database.  For example, the attacker might replace a table
+definition with a view.  Or the attacker might add triggers to tables
+or views, or add new CHECK constraints or generated columns or indexes
+with expressions in the index list or in the WHERE clause.  If the
+added features invoke SQL functions or virtual tables with side effects,
+that might cause harm to the system if run by a high-privilege victim.
+Or, the added features might exfiltrate information if the database is
+read by a high-privilege victim.
+
+The changes in this branch strive to make it easier for high-privilege
+applications to safely read SQLite database files that might have been
+maliciously corrupted by an attacker.
+
+## Overview of changes in [new-security-options](/timeline?r=new-security-options)
+
+The basic idea is to tag every SQL function and virtual table with one
+of three risk levels:
+
+  1.  Innocuous
+  2.  Normal
+  3.  Direct-Only
+
+Innocuous functions/vtabs are safe and can be used at any time.
+Direct-only elements, in contrast, might have cause side-effects and
+should only be used from top-level SQL, not from within triggers or views nor
+in elements of the schema such as CHECK constraint, DEFAULT values, 
+generated columns, index expressions, or in the WHERE clause of a 
+partial index that are potentially under the control of an attacker.
+Normal elements behave like Innocuous if TRUSTED\_SCHEMA=on
+and behave like direct-only if TRUSTED\_SCHEMA=off.
+
+Application-defined functions and virtual tables go in as Normal unless
+the application takes deliberate steps to change the risk level.
+
+For backwards compatibility, the default is TRUSTED\_SCHEMA=on.  Documentation
+will be updated to recommend applications turn TRUSTED\_SCHEMA to off.
+
+An innocuous function or virtual table is one that can only read content
+from the database file in which it resides, and can only alter the database
+in which it resides.  Most SQL functions are innocuous.  For example, there
+is no harm in an attacker running the abs() function.
+
+Direct-only elements that have side-effects that go outside the database file
+in which it lives, or return information from outside of the database file.
+Examples of direct-only elements include:
+
+  1.  The fts3\_tokenizer() function
+  2.  The writefile() function
+  3.  The readfile() function
+  4.  The zipvfs virtual table
+  5.  The csv virtual table
+
+We do not want an attacker to be able to add these kinds of things to
+the database schema and possibly trick a high-privilege application 
+from performing any of these actions.  Therefore, functions and vtabs
+with side-effects are marked as Direct-Only.
+
+Legacy applications might add other risky functions or vtabs.  Those will
+go in as "Normal" by default.  For optimal security, we want those risky
+app-defined functions and vtabs to be direct-only, but making that the
+default might break some legacy applications.  Hence, all app-defined
+functions and vtabs go in as Normal, but the application can switch them
+over to "Direct-Only" behavior using a single pragma.
+
+The restrictions on the use of functions and virtual tables do not apply
+to TEMP.  A TEMP VIEW or a TEMP TRIGGER can use any valid SQL function
+or virtual table.  The idea is that TEMP views and triggers must be
+directly created by the application and are thus under the control of the
+application.  TEMP views and triggers cannot be created by an attacker who
+corrupts the schema of a persistent database file.  Hence TEMP views and
+triggers are safe.
+
+## Specific changes
+
+  1.  New sqlite3\_db\_config() option SQLITE\_DBCONFIG\_TRUSTED\_SCHEMA for
+      turning TRUSTED\_SCHEMA on and off.  It defaults to ON.
+
+  2.  Compile-time option -DSQLITE\_TRUSTED\_SCHEMA=0 causes the default
+      TRUSTED\_SCHEMA setting to be off.
+
+  3.  New pragma "PRAGMA trusted\_schema=(ON\|OFF);".  This provides access
+      to the TRUSTED_SCHEMA setting for application coded using scripting
+      languages or other secondary languages where they are unable to make
+      calls to sqlite3\_db\_config().
+
+  4.  New options for the "enc" parameter to sqlite3\_create\_function() and
+      its kin:
+      <ol type="a">
+      <li>  _SQLITE\_INNOCUOUS_  &rarr; tags the new functions as Innocuous
+      <li>  _SQLITE\_DIRECTONLY_ &rarr; tags the new functions as Direct-Only
+      </ol>
+
+  5.  New options to sqlite3\_vtab\_config():
+      <ol type="a">
+      <li>  _SQLITE\_VTAB\_INNOCUOUS_   &rarr; tags the vtab as Innocuous
+      <li>  _SQLITE\_VTAB\_DIRECTONLY_  &rarr; tags the vtab as Direct-Only
+      </ol>
+
+  6.  Change many of the functions and virtual tables in the SQLite source
+      tree to use one of the tags above.
+
+  7.  Enhanced PRAGMA function\_list and virtual-table "pragma\_function\_list"
+      with additional columns.  The columns now are:
+      <ul>
+      <li> _name_      &rarr;  Name of the function
+      <li> _builtin_   &rarr;  1 for built-in functions.  0 otherwise.
+      <li> _type_      &rarr;  's'=Scalar, 'a'=Aggregate, 'w'=Window
+      <li> _enc_       &rarr;  'utf8', 'utf16le', or 'utf16be'
+      <li> _narg_      &rarr;  number of argument
+      <li> _flags_     &rarr;  Bitmask of SQLITE\_INNOCUOUS, SQLITE\_DIRECTONLY,
+                               SQLITE\_DETERMINISTIC, SQLITE\_SUBTYPE, and
+                               SQLITE\_FUNC\_INTERNAL flags.
+      </ul>
+      <p>The last four columns are new.
+
+  8.  The function\_list PRAGMA now also shows all entries for each function.
+      So, for example, if a function can take either 2 or 3 arguments,
+      there are separate rows for the 2-argument and 3-argument versions of
+      the function.
+
+## Additional Notes
+
+The function_list enhancements allow the application to query the set
+of SQL functions that meet various criteria.  For example, to see all
+SQL functions that are never allowed to be used in the schema or in
+trigger or views:
+
+~~~
+    SELECT DISTINCT name FROM pragma_function_list
+     WHERE (flags & 0x80000)!=0
+     ORDER BY name;
+~~~
+
+Doing the same is not possible for virtual tables, as a virtual table
+might be Innocuous, Normal, or Direct-Only depending on the arguments
+passed into the xConnect method.
diff --git a/doc/vdbesort-memory.md b/doc/vdbesort-memory.md
new file mode 100644
index 0000000..5c3dd62
--- /dev/null
+++ b/doc/vdbesort-memory.md
@@ -0,0 +1,49 @@
+
+20-11-2020
+
+# Memory Allocation In vdbesort.c
+
+Memory allocation is slightly different depending on:
+
+  * whether or not SQLITE_CONFIG_SMALL_MALLOC is set, and
+  * whether or not worker threads are enabled.
+
+## SQLITE_CONFIG_SMALL_MALLOC=0
+
+Assuming SQLITE_CONFIG_SMALL_MALLOC is not set, keys passed to the sorter are
+added to an in-memory buffer. This buffer is grown using sqlite3Realloc() as
+required it reaches the size configured for the main pager cache using "PRAGMA
+cache_size". i.e. if the user has executed "PRAGMA main.cache_size = -2048",
+then this buffer is allowed to grow up to 2MB in size.
+
+Once the buffer has grown to its threshold, keys are sorted and written to
+a temp file. If worker threads are not enabled, this is the only significant
+allocation the sorter module makes. After keys are sorted and flushed out to
+the temp file, the buffer is reused to accumulate the next batch of keys.
+
+If worker threads are available, then the buffer is passed to a worker thread
+to sort and flush once it is full, and a new buffer allocated to allow the
+main thread to continue to accumulate keys. Buffers are reused once they
+have been flushed, so in this case at most (nWorker+1) buffers are allocated
+and used, where nWorker is the number of configured worker threads.
+
+There are no other significant users of heap memory in the sorter module. 
+Once sorted buffers of keys have been flushed to disk, they are read back
+either by mapping the file (via sqlite3_file.xFetch()) or else read back
+in one page at a time.
+
+All buffers are allocated by the main thread. A sorter object is associated
+with a single database connection, to which it holds a pointer.
+
+## SQLITE_CONFIG_SMALL_MALLOC=1
+
+This case is similar to the above, except that instead of accumulating
+multiple keys in a single large buffer, sqlite3VdbeSorterWrite() stores
+keys in a regular heap-memory linked list (one allocation per element).
+List elements are freed as they are flushed to disk, either by the main
+thread or by a worker thread.
+
+Each time a key is added the sorter (and an allocation made),
+sqlite3HeapNearlyFull() is called. If it returns true, the current
+list of keys is flushed to a temporary file, even if it has not yet
+reached the size threshold.
diff --git a/doc/vfs-shm.txt b/doc/vfs-shm.txt
new file mode 100644
index 0000000..c1f125a
--- /dev/null
+++ b/doc/vfs-shm.txt
@@ -0,0 +1,130 @@
+The 5 states of an historical rollback lock as implemented by the
+xLock, xUnlock, and xCheckReservedLock methods of the sqlite3_io_methods
+objec are:
+
+   UNLOCKED
+   SHARED
+   RESERVED
+   PENDING
+   EXCLUSIVE
+
+The wal-index file has a similar locking hierarchy implemented using
+the xShmLock method of the sqlite3_vfs object, but with 7
+states.  Each connection to a wal-index file must be in one of
+the following 7 states:
+
+   UNLOCKED
+   READ
+   READ_FULL
+   WRITE
+   PENDING
+   CHECKPOINT
+   RECOVER
+
+These roughly correspond to the 5 states of a rollback lock except
+that SHARED is split out into 2 states: READ and READ_FULL and
+there is an extra RECOVER state used for wal-index reconstruction.
+
+The meanings of the various wal-index locking states is as follows:
+
+   UNLOCKED    - The wal-index is not in use.
+
+   READ        - Some prefix of the wal-index is being read. Additional
+                 wal-index information can be appended at any time.  The
+                 newly appended content will be ignored by the holder of
+                 the READ lock.
+
+   READ_FULL   - The entire wal-index is being read.  No new information
+                 can be added to the wal-index.  The holder of a READ_FULL
+                 lock promises never to read pages from the database file
+                 that are available anywhere in the wal-index.
+
+   WRITE       - It is OK to append to the wal-index file and to adjust
+                 the header to indicate the new "last valid frame".
+
+   PENDING     - Waiting on all READ locks to clear so that a
+                 CHECKPOINT lock can be acquired.
+
+   CHECKPOINT  - It is OK to write any WAL data into the database file
+                 and zero the last valid frame field of the wal-index
+                 header.  The wal-index file itself may not be changed
+                 other than to zero the last valid frame field in the
+                 header.
+
+   RECOVER     - Held during wal-index recovery.  Used to prevent a
+                 race if multiple clients try to recover a wal-index at
+                 the same time.
+   
+
+A particular lock manager implementation may coalesce one or more of 
+the wal-index locking states, though with a reduction in concurrency.
+For example, an implemention might implement only exclusive locking,
+in which case all states would be equivalent to CHECKPOINT, meaning that 
+only one reader or one writer or one checkpointer could be active at a 
+time.  Or, an implementation might combine READ and READ_FULL into 
+a single state equivalent to READ, meaning that a writer could
+coexist with a reader, but no reader or writers could coexist with a
+checkpointer.
+
+The lock manager must obey the following rules:
+
+(1)  A READ cannot coexist with CHECKPOINT.
+(2)  A READ_FULL cannot coexist with WRITE.
+(3)  None of WRITE, PENDING, CHECKPOINT, or RECOVER can coexist.
+
+The SQLite core will obey the next set of rules.  These rules are
+assertions on the behavior of the SQLite core which might be verified
+during testing using an instrumented lock manager.
+
+(5)  No part of the wal-index will be read without holding either some
+     kind of SHM lock or an EXCLUSIVE lock on the original database.
+     The original database is the file named in the 2nd parameter to
+     the xShmOpen method.
+
+(6)  A holder of a READ_FULL will never read any page of the database
+     file that is contained anywhere in the wal-index.
+
+(7)  No part of the wal-index other than the header will be written nor
+     will the size of the wal-index grow without holding a WRITE or
+     an EXCLUSIVE on the original database file.
+
+(8)  The wal-index header will not be written without holding one of
+     WRITE, CHECKPOINT, or RECOVER on the wal-index or an EXCLUSIVE on
+     the original database files.
+
+(9)  A CHECKPOINT or RECOVER must be held on the wal-index, or an
+     EXCLUSIVE on the original database file, in order to reset the 
+     last valid frame counter in the header of the wal-index back to zero.
+
+(10) A WRITE can only increase the last valid frame pointer in the header.
+
+The SQLite core will only ever send requests for UNLOCK, READ, WRITE,
+CHECKPOINT, or RECOVER to the lock manager.   The SQLite core will never
+request a READ_FULL or PENDING lock though the lock manager may deliver
+those locking states in response to READ and CHECKPOINT requests,
+respectively, if and only if the requested READ or CHECKPOINT cannot
+be delivered.
+
+The following are the allowed lock transitions:
+
+       Original-State     Request         New-State
+       --------------     ----------      ----------
+(11a)  UNLOCK             READ            READ
+(11b)  UNLOCK             READ            READ_FULL
+(11c)  UNLOCK             CHECKPOINT      PENDING
+(11d)  UNLOCK             CHECKPOINT      CHECKPOINT
+(11e)  READ               UNLOCK          UNLOCK
+(11f)  READ               WRITE           WRITE
+(11g)  READ               RECOVER         RECOVER
+(11h)  READ_FULL          UNLOCK          UNLOCK
+(11i)  READ_FULL          WRITE           WRITE
+(11j)  READ_FULL          RECOVER         RECOVER
+(11k)  WRITE              READ            READ
+(11l)  PENDING            UNLOCK          UNLOCK
+(11m)  PENDING            CHECKPOINT      CHECKPOINT
+(11n)  CHECKPOINT         UNLOCK          UNLOCK
+(11o)  RECOVER            READ            READ
+
+These 15 transitions are all that needs to be supported.  The lock
+manager implementation can assert that fact.  The other 27 possible
+transitions among the 7 locking states will never occur.
diff --git a/doc/wal-lock.md b/doc/wal-lock.md
new file mode 100644
index 0000000..d74bb88
--- /dev/null
+++ b/doc/wal-lock.md
@@ -0,0 +1,88 @@
+# Wal-Mode Blocking Locks
+
+On some Unix-like systems, SQLite may be configured to use POSIX blocking locks
+by:
+
+  * building the library with SQLITE\_ENABLE\_SETLK\_TIMEOUT defined, and 
+  * configuring a timeout in ms using the sqlite3\_busy\_timeout() API.
+
+Blocking locks may be advantageous as (a) waiting database clients do not
+need to continuously poll the database lock, and (b) using blocking locks
+facilitates transfer of OS priority between processes when a high priority
+process is blocked by a lower priority one.
+
+Only read/write clients use blocking locks. Clients that have read-only access
+to the \*-shm file nevery use blocking locks.
+
+Threads or processes that access a single database at a time never deadlock as
+a result of blocking database locks. But it is of course possible for threads
+that lock multiple databases simultaneously to do so. In most cases the OS will
+detect the deadlock and return an error.
+
+## Wal Recovery
+
+Wal database "recovery" is a process required when the number of connected
+database clients changes from zero to one. In this case, a client is 
+considered to connect to the database when it first reads data from it.
+Before recovery commences, an exclusive WRITER lock is taken. 
+
+Without blocking locks, if two clients attempt recovery simultaneously, one
+fails to obtain the WRITER lock and either invokes the busy-handler callback or
+returns SQLITE\_BUSY to the user. With blocking locks configured, the second
+client blocks on the WRITER lock.
+
+## Database Readers
+
+Usually, read-only are not blocked by any other database clients, so they 
+have no need of blocking locks.
+
+If a read-only transaction is being opened on a snapshot, the CHECKPOINTER
+lock is required briefly as part of opening the transaction (to check that a
+checkpointer is not currently overwriting the snapshot being opened). A
+blocking lock is used to obtain the CHECKPOINTER lock in this case. A snapshot
+opener may therefore block on and transfer priority to a checkpointer in some
+cases.
+
+## Database Writers
+
+A database writer must obtain the exclusive WRITER lock. It uses a blocking
+lock to do so if any of the following are true:
+
+  * the transaction is an implicit one consisting of a single DML or DDL
+    statement, or
+  * the transaction is opened using BEGIN IMMEDIATE or BEGIN EXCLUSIVE, or
+  * the first SQL statement executed following the BEGIN command is a DML or
+    DDL statement (not a read-only statement like a SELECT).
+
+In other words, in all cases except when an open read-transaction is upgraded
+to a write-transaction. In that case a non-blocking lock is used.
+
+## Database Checkpointers
+
+Database checkpointers takes the following locks, in order:
+
+  * The exclusive CHECKPOINTER lock.
+  * The exclusive WRITER lock (FULL, RESTART and TRUNCATE only).
+  * Exclusive lock on read-mark slots 1-N. These are immediately released after being taken.
+  * Exclusive lock on read-mark 0.
+  * Exclusive lock on read-mark slots 1-N again. These are immediately released
+    after being taken (RESTART and TRUNCATE only).
+
+All of the above use blocking locks.
+
+## Summary
+
+With blocking locks configured, the only cases in which clients should see an
+SQLITE\_BUSY error are:
+
+  * if the OS does not grant a blocking lock before the configured timeout
+    expires, and
+  * when an open read-transaction is upgraded to a write-transaction.
+
+In all other cases the blocking locks implementation should prevent clients
+from having to handle SQLITE\_BUSY errors and facilitate appropriate transfer
+of priorities between competing clients.
+
+Clients that lock multiple databases simultaneously must be wary of deadlock.
+
+