diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/F2FS.txt | 87 | ||||
| -rw-r--r-- | doc/json-enhancements.md | 144 | ||||
| -rw-r--r-- | doc/lemon.html | 1264 | ||||
| -rw-r--r-- | doc/pager-invariants.txt | 76 | ||||
| -rw-r--r-- | doc/trusted-schema.md | 142 | ||||
| -rw-r--r-- | doc/vdbesort-memory.md | 49 | ||||
| -rw-r--r-- | doc/vfs-shm.txt | 130 | ||||
| -rw-r--r-- | doc/wal-lock.md | 88 |
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>-> operator<br>(all)<th>->> operator<br>(MySQL/PG) + <th>->> 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->'$.a' <td> yes <td> no <td> yes +<tr><td>value1->'a' <td> no <td> yes <td> yes +<tr><td>value2->'$[2]' <td> yes <td> no <td> yes +<tr><td>value2->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 → Robust and secure +<li>The "lemon.exe" command line tool itself → 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 — +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(&sState); + 11 while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){ + 12 Parse(pParser, hTokenId, sToken, &sState); + 13 } + 14 Parse(pParser, 0, sToken, &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,&hTokenId, &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,&hTokenId, &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 -> 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 — 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 "&&" 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 — +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 <unistd.h>} +</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&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_ → tags the new functions as Innocuous + <li> _SQLITE\_DIRECTONLY_ → tags the new functions as Direct-Only + </ol> + + 5. New options to sqlite3\_vtab\_config(): + <ol type="a"> + <li> _SQLITE\_VTAB\_INNOCUOUS_ → tags the vtab as Innocuous + <li> _SQLITE\_VTAB\_DIRECTONLY_ → 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_ → Name of the function + <li> _builtin_ → 1 for built-in functions. 0 otherwise. + <li> _type_ → 's'=Scalar, 'a'=Aggregate, 'w'=Window + <li> _enc_ → 'utf8', 'utf16le', or 'utf16be' + <li> _narg_ → number of argument + <li> _flags_ → 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. + + |