1 files changed, 215 insertions, 0 deletions
diff --git a/doc/pcrestack.3 b/doc/pcrestack.3
new file mode 100644
index 0000000..798f0bc
--- /dev/null
+++ b/doc/pcrestack.3
@@ -0,0 +1,215 @@
+.TH PCRESTACK 3 "24 June 2012" "PCRE 8.30"
+.SH NAME
+PCRE - Perl-compatible regular expressions
+.SH "PCRE DISCUSSION OF STACK USAGE"
+.rs
+.sp
+When you call \fBpcre[16|32]_exec()\fP, it makes use of an internal function
+called \fBmatch()\fP. This calls itself recursively at branch points in the
+pattern, in order to remember the state of the match so that it can back up and
+try a different alternative if the first one fails. As matching proceeds deeper
+and deeper into the tree of possibilities, the recursion depth increases. The
+\fBmatch()\fP function is also called in other circumstances, for example,
+whenever a parenthesized sub-pattern is entered, and in certain cases of
+repetition.
+.P
+Not all calls of \fBmatch()\fP increase the recursion depth; for an item such
+as a* it may be called several times at the same level, after matching
+different numbers of a's. Furthermore, in a number of cases where the result of
+the recursive call would immediately be passed back as the result of the
+current call (a "tail recursion"), the function is just restarted instead.
+.P
+The above comments apply when \fBpcre[16|32]_exec()\fP is run in its normal
+interpretive manner. If the pattern was studied with the
+PCRE_STUDY_JIT_COMPILE option, and just-in-time compiling was successful, and
+the options passed to \fBpcre[16|32]_exec()\fP were not incompatible, the matching
+process uses the JIT-compiled code instead of the \fBmatch()\fP function. In
+this case, the memory requirements are handled entirely differently. See the
+.\" HREF
+\fBpcrejit\fP
+.\"
+documentation for details.
+.P
+The \fBpcre[16|32]_dfa_exec()\fP function operates in an entirely different way,
+and uses recursion only when there is a regular expression recursion or
+subroutine call in the pattern. This includes the processing of assertion and
+"once-only" subpatterns, which are handled like subroutine calls. Normally,
+these are never very deep, and the limit on the complexity of
+\fBpcre[16|32]_dfa_exec()\fP is controlled by the amount of workspace it is given.
+However, it is possible to write patterns with runaway infinite recursions;
+such patterns will cause \fBpcre[16|32]_dfa_exec()\fP to run out of stack. At
+present, there is no protection against this.
+.P
+The comments that follow do NOT apply to \fBpcre[16|32]_dfa_exec()\fP; they are
+relevant only for \fBpcre[16|32]_exec()\fP without the JIT optimization.
+.
+.
+.SS "Reducing \fBpcre[16|32]_exec()\fP's stack usage"
+.rs
+.sp
+Each time that \fBmatch()\fP is actually called recursively, it uses memory
+from the process stack. For certain kinds of pattern and data, very large
+amounts of stack may be needed, despite the recognition of "tail recursion".
+You can often reduce the amount of recursion, and therefore the amount of stack
+used, by modifying the pattern that is being matched. Consider, for example,
+this pattern:
+.sp
+  ([^<]|<(?!inet))+
+.sp
+It matches from wherever it starts until it encounters "<inet" or the end of
+the data, and is the kind of pattern that might be used when processing an XML
+file. Each iteration of the outer parentheses matches either one character that
+is not "<" or a "<" that is not followed by "inet". However, each time a
+parenthesis is processed, a recursion occurs, so this formulation uses a stack
+frame for each matched character. For a long string, a lot of stack is
+required. Consider now this rewritten pattern, which matches exactly the same
+strings:
+.sp
+  ([^<]++|<(?!inet))+
+.sp
+This uses very much less stack, because runs of characters that do not contain
+"<" are "swallowed" in one item inside the parentheses. Recursion happens only
+when a "<" character that is not followed by "inet" is encountered (and we
+assume this is relatively rare). A possessive quantifier is used to stop any
+backtracking into the runs of non-"<" characters, but that is not related to
+stack usage.
+.P
+This example shows that one way of avoiding stack problems when matching long
+subject strings is to write repeated parenthesized subpatterns to match more
+than one character whenever possible.
+.
+.
+.SS "Compiling PCRE to use heap instead of stack for \fBpcre[16|32]_exec()\fP"
+.rs
+.sp
+In environments where stack memory is constrained, you might want to compile
+PCRE to use heap memory instead of stack for remembering back-up points when
+\fBpcre[16|32]_exec()\fP is running. This makes it run a lot more slowly, however.
+Details of how to do this are given in the
+.\" HREF
+\fBpcrebuild\fP
+.\"
+documentation. When built in this way, instead of using the stack, PCRE obtains
+and frees memory by calling the functions that are pointed to by the
+\fBpcre[16|32]_stack_malloc\fP and \fBpcre[16|32]_stack_free\fP variables. By
+default, these point to \fBmalloc()\fP and \fBfree()\fP, but you can replace
+the pointers to cause PCRE to use your own functions. Since the block sizes are
+always the same, and are always freed in reverse order, it may be possible to
+implement customized memory handlers that are more efficient than the standard
+functions.
+.
+.
+.SS "Limiting \fBpcre[16|32]_exec()\fP's stack usage"
+.rs
+.sp
+You can set limits on the number of times that \fBmatch()\fP is called, both in
+total and recursively. If a limit is exceeded, \fBpcre[16|32]_exec()\fP returns an
+error code. Setting suitable limits should prevent it from running out of
+stack. The default values of the limits are very large, and unlikely ever to
+operate. They can be changed when PCRE is built, and they can also be set when
+\fBpcre[16|32]_exec()\fP is called. For details of these interfaces, see the
+.\" HREF
+\fBpcrebuild\fP
+.\"
+documentation and the
+.\" HTML <a href="pcreapi.html#extradata">
+.\" </a>
+section on extra data for \fBpcre[16|32]_exec()\fP
+.\"
+in the
+.\" HREF
+\fBpcreapi\fP
+.\"
+documentation.
+.P
+As a very rough rule of thumb, you should reckon on about 500 bytes per
+recursion. Thus, if you want to limit your stack usage to 8Mb, you should set
+the limit at 16000 recursions. A 64Mb stack, on the other hand, can support
+around 128000 recursions.
+.P
+In Unix-like environments, the \fBpcretest\fP test program has a command line
+option (\fB-S\fP) that can be used to increase the size of its stack. As long
+as the stack is large enough, another option (\fB-M\fP) can be used to find the
+smallest limits that allow a particular pattern to match a given subject
+string. This is done by calling \fBpcre[16|32]_exec()\fP repeatedly with different
+limits.
+.
+.
+.SS "Obtaining an estimate of stack usage"
+.rs
+.sp
+The actual amount of stack used per recursion can vary quite a lot, depending
+on the compiler that was used to build PCRE and the optimization or debugging
+options that were set for it. The rule of thumb value of 500 bytes mentioned
+above may be larger or smaller than what is actually needed. A better
+approximation can be obtained by running this command:
+.sp
+  pcretest -m -C
+.sp
+The \fB-C\fP option causes \fBpcretest\fP to output information about the
+options with which PCRE was compiled. When \fB-m\fP is also given (before
+\fB-C\fP), information about stack use is given in a line like this:
+.sp
+  Match recursion uses stack: approximate frame size = 640 bytes
+.sp
+The value is approximate because some recursions need a bit more (up to perhaps
+16 more bytes).
+.P
+If the above command is given when PCRE is compiled to use the heap instead of
+the stack for recursion, the value that is output is the size of each block
+that is obtained from the heap.
+.
+.
+.SS "Changing stack size in Unix-like systems"
+.rs
+.sp
+In Unix-like environments, there is not often a problem with the stack unless
+very long strings are involved, though the default limit on stack size varies
+from system to system. Values from 8Mb to 64Mb are common. You can find your
+default limit by running the command:
+.sp
+  ulimit -s
+.sp
+Unfortunately, the effect of running out of stack is often SIGSEGV, though
+sometimes a more explicit error message is given. You can normally increase the
+limit on stack size by code such as this:
+.sp
+  struct rlimit rlim;
+  getrlimit(RLIMIT_STACK, &rlim);
+  rlim.rlim_cur = 100*1024*1024;
+  setrlimit(RLIMIT_STACK, &rlim);
+.sp
+This reads the current limits (soft and hard) using \fBgetrlimit()\fP, then
+attempts to increase the soft limit to 100Mb using \fBsetrlimit()\fP. You must
+do this before calling \fBpcre[16|32]_exec()\fP.
+.
+.
+.SS "Changing stack size in Mac OS X"
+.rs
+.sp
+Using \fBsetrlimit()\fP, as described above, should also work on Mac OS X. It
+is also possible to set a stack size when linking a program. There is a
+discussion about stack sizes in Mac OS X at this web site:
+.\" HTML <a href="http://developer.apple.com/qa/qa2005/qa1419.html">
+.\" </a>
+http://developer.apple.com/qa/qa2005/qa1419.html.
+.\"
+.
+.
+.SH AUTHOR
+.rs
+.sp
+.nf
+Philip Hazel
+University Computing Service
+Cambridge CB2 3QH, England.
+.fi
+.
+.
+.SH REVISION
+.rs
+.sp
+.nf
+Last updated: 24 June 2012
+Copyright (c) 1997-2012 University of Cambridge.
+.fi