200510.1 · 293dbd34e9e892ce03dabac15012135db564c0c3
released 2.1.0 - new option --tag; new --format field %g; relaxed regex size and complexity limits; new regex engine VM opcodes
reading declarations
@@ -30,11 +30,12 @@ search pdf and office documents using filters - Unlimited pro edition - forever free open source (BSD-3) - Written in clean and efficient C++11, built for speed-- Ultra fast with new match algorithms [beating](#speed) ripgrep, silver searcher, hyperscan, etc.+- Ultra fast with new match algorithms [beating](#speed) grep, ripgrep, silver searcher, hyperscan, etc. - Multi-threaded search using high-performance lock-free job queue stealing - Multi-threaded task-parallel decompression and search - Optimized pattern matching (AVX, SSE2, ARM NEON/AArch64) - Optimized asynchronous IO implementation+- Thoroughly tested (includes over 1000 test cases) - Compatible with the standard GNU/BSD grep command-line options - Comprehensive how-to [tutorial](#tutorial) for beginners to advanced users - Interactive [query UI](#query) to enter search patterns@@ -262,9 +263,7 @@ The corpora used in the tests are available for Performance tests were conducted with a Mac OS X using clang 9.0.0 -O2 on a 2.9 GHz Intel Core i7, 16 GB 2133 MHz LPDDR3 Mac OS 10.12.6 machine. The best-times for at least 30 runs is shown under minimal machine load. Note that-performance results depend on compilers, libraries, the OS, the CPU type, and-file system latencies.+times for at least 30 runs is shown under minimal machine load. Results are shown in real time (wall clock time) seconds elapsed. Best times are shown in **boldface** and *n/a* means that the running time exceeded 1@@ -272,7 +271,7 @@ minute or the selected options are not supported (e.g. option `-z`). GREP | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 | T10 | T11 | T12 | --------------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |-ugrep | **0.05** | **0.06** | **0.08** | **0.03** | **0.99** | **0.97** | **0.87** | **0.89** | **0.30** | **0.10** | **0.19** | **0.02** |+ugrep | **0.05** | **0.06** | **0.08** | **0.03** | **0.99** | **0.99** | **0.89** | **0.88** | **0.29** | **0.10** | **0.19** | **0.02** | hyperscan grep | 0.09 | 0.10 | 0.11 | 0.04 | 7.78 | 3.39 | 2.35 | 1.41 | 1.17 | *n/a* | *n/a* | *n/a* | ripgrep | 0.06 | 0.10 | 0.19 | 0.06 | 2.20 | 2.07 | 2.00 | 2.01 | 2.14 | 0.12 | 0.36 | 0.03 | silver searcher | 0.10 | 0.11 | 0.16 | 0.21 | *n/a* | *n/a* | *n/a* | *n/a* | *n/a* | 0.45 | 0.32 | 0.09 |@@ -300,6 +299,10 @@ overhead. The `null` utility source code: #include <unistd.h> int main() { char buf[65536]; while (read(0, buf, 65536) > 0) continue; } +Note: performance results depend on warm/cold runs, compilers, libraries, the+OS, the CPU type, and file system latencies. However, comparable competitive+results were obtained on many other types of machines.+ <a name="install"/> Download and build@@ -822,7 +825,7 @@ To show a list of `-t TYPES` option values: the default is 5 (0.5s delay). Initial patterns may be specified with -e PATTERN, i.e. a PATTERN argument requires option -e. Press F1 or CTRL-Z to view the help screen. No whitespace may be given- between -Q and its argument DELAY.+ between -Q and its argument DELAY. Enables --heading. This option starts a user interface to enter search patterns interactively: - Press F1 or CTRL-Z to view a help screen and to enable or disable options.@@ -855,9 +858,8 @@ This option starts a user interface to enter search patterns interactively: and cancelling searches by each key pressed. Reducing the level of parallelism helps to reduce system load, i.e. with option `-J`, e.g. `-J2` to run 2 worker jobs at most.-- To avoid long pathnames to obscure the view, enable `--heading` or press- `Alt-+`.- +- To avoid long pathnames to obscure the view, `--heading` is enabled by+ default. Press Alt-+ to switch headings off. To interactively search the files in the working directory and below: @@ -959,8 +961,13 @@ symbolic links (note that `-R` is redundant as no FILE arguments are given): ugrep -Rl '' -To list all non-empty files in directory `mydir` (but not deeper, since a FILE-argument is given):+To list all non-empty files in the working directory but not deeper, since a+FILE argument is given (in this case `.` for the working directory):++ ugrep -l '' .++To list all non-empty files in directory `mydir` but not deeper, since a FILE+argument is given: ugrep -l '' mydir @@ -982,7 +989,7 @@ symbolic links (except when on the command line such as `mydir`): To recursively list all `Makefile` matching the text `CPP`: - ugrep -l -gMakefile 'bin_PROGRAMS'+ ugrep -l -gMakefile 'CPP' To recursively list all `Makefile.*` matching `bin_PROGRAMS`: @@ -2174,6 +2181,9 @@ To display the line and column numbers of matches in XML with `--xml`: bright. A foreground and a background color may be combined with font properties `n' (normal), `f' (faint), `h' (highlight), `i' (invert), `u' (underline). Selectively overrides GREP_COLORS.+ --tag[=TAG[,END]]+ Disables colors to mark up matches with TAG. If END is specified,+ the end of a match is marked with END. The default is `___'. --[no-]pager[=COMMAND] When output is sent to the terminal, uses COMMAND to page through the output. The default COMMAND is `less -R'. Enables --heading@@ -2393,6 +2403,7 @@ field | output `%w` | the width of the match, counting (wide) characters `%d` | the size of the match, counting bytes `%e` | the ending byte offset of the match+`%g` | the group capture index of the match or zero (see note) `%u` | select unique lines only unless option -u is used `%,` | if not the first match: a comma, same as `%[,]>` `%:` | if not the first match: a colon, same as `%[:]>`@@ -2418,6 +2429,11 @@ Note: same line. When field `%u` is found anywhere in the specified format string, matching lines are output only once unless option `-u`, `--ungroup` is used or when a newline is matched.+- The group capture index `%g` corresponds to the index of the sub-pattern+ matched among alternations in the pattern when option `-P` is not used. For+ example `foo|bar` matches `foo` with index 1 and `bar` with index 2. With+ option `-P`, the index corresponds to the index of the group captured in the+ specified pattern. To output matching lines faster by omitting the header output and binary match checks, using `--format` with field `%O` (output matching line as is) and field@@ -2469,6 +2485,16 @@ To output matches in AckMate format: ugrep --format=":%f%~%n;%k %w:%O%~" 'href=' index.html +To output the sub-pattern indices 1, 2, and 3 on the left to the match for the+three patterns `foo`, `bar`, and `baz` in file `foobar.txt`:++ ugrep --format='%g: %o%~' 'foo|bar|baz' foobar.txt++Same, but using a file `foos` containing three lines with `foo`, `bar`, and+`baz`, where option `-F` is used to match strings instead of regex:++ ugrep -F -f foos --format='%g: %o%~' foobar.txt+ <a name="replace"/> ### Replacing matches with --format backreferences to group captures@@ -2716,7 +2742,7 @@ in markdown: NAME- ugrep -- universal file pattern searcher+ ugrep -- file pattern searcher SYNOPSIS ugrep [OPTIONS] [-A NUM] [-B NUM] [-C[NUM]] [PATTERN] [-e PATTERN]@@ -3158,96 +3184,102 @@ in markdown: of 100ms, where the default is 5 (0.5s delay). Initial patterns may be specified with -e PATTERN, i.e. a PATTERN argument requires option -e. Press F1 or CTRL-Z to view the help screen.- No whitespace may be given between -Q and its argument DELAY.+ No whitespace may be given between -Q and its argument DELAY.+ Enables --heading. -q, --quiet, --silent Quiet mode: suppress all output. ugrep will only search until a- match has been found, making searches potentially less expen-+ match has been found, making searches potentially less expen- sive. -R, --dereference-recursive- Recursively read all files under each directory. Follow all- symbolic links, unlike -r. When -J1 is specified, files are+ Recursively read all files under each directory. Follow all+ symbolic links, unlike -r. When -J1 is specified, files are searched in the same order as specified. Note that when no FILE- arguments are specified and input is read from a terminal,+ arguments are specified and input is read from a terminal, recursive searches are performed as if -R is specified. -r, --recursive- Recursively read all files under each directory, following sym-- bolic links only if they are on the command line. When -J1 is+ Recursively read all files under each directory, following sym-+ bolic links only if they are on the command line. When -J1 is specified, files are searched in the same order as specified. --range=FIRST[,LAST] Start searching at line FIRST, stop at line LAST when specified. -S, --dereference- If -r is specified, all symbolic links are followed, like -R.+ If -r is specified, all symbolic links are followed, like -R. The default is not to follow symbolic links. -s, --no-messages- Silent mode: nonexistent and unreadable files are ignored, i.e.+ Silent mode: nonexistent and unreadable files are ignored, i.e. their error messages are suppressed. --separator[=SEP]- Use SEP as field separator between file name, line number, col-+ Use SEP as field separator between file name, line number, col- umn number, byte offset, and the matched line. The default is a colon (`:'). --sort[=KEY]- Displays matching files in the order specified by KEY in recur-+ Displays matching files in the order specified by KEY in recur- sive searches. KEY can be `name' to sort by pathname (default), `size' to sort by file size, `used' to sort by last access time,- `changed' to sort by last modification time, and `created' to+ `changed' to sort by last modification time, and `created' to sort by creation time. Sorting is reversed by `rname', `rsize',- `rused', `rchanged', or `rcreated'. Archive contents are not- sorted. Subdirectories are displayed after matching files.- FILE arguments are searched in the same order as specified.- Normally ugrep displays matches in no particular order to+ `rused', `rchanged', or `rcreated'. Archive contents are not+ sorted. Subdirectories are displayed after matching files.+ FILE arguments are searched in the same order as specified.+ Normally ugrep displays matches in no particular order to improve performance. --stats- Display statistics on the number of files and directories+ Display statistics on the number of files and directories searched, and the inclusion and exclusion constraints applied. -T, --initial-tab- Add a tab space to separate the file name, line number, column+ Add a tab space to separate the file name, line number, column number, and byte offset with the matched line. -t TYPES, --file-type=TYPES- Search only files associated with TYPES, a comma-separated list- of file types. Each file type corresponds to a set of filename+ Search only files associated with TYPES, a comma-separated list+ of file types. Each file type corresponds to a set of filename extensions passed to option -O. For capitalized file types, the search is expanded to include files with matching file signature- magic bytes, as if passed to option -M. When a type is pre-- ceeded by a `!' or a `^', excludes files of the specified type.- This option may be repeated. The possible file types can be- (where -tlist displays a detailed list): `actionscript', `ada',- `asm', `asp', `aspx', `autoconf', `automake', `awk', `Awk',- `basic', `batch', `bison', `c', `c++', `clojure', `csharp',+ magic bytes, as if passed to option -M. When a type is pre-+ ceeded by a `!' or a `^', excludes files of the specified type.+ This option may be repeated. The possible file types can be+ (where -tlist displays a detailed list): `actionscript', `ada',+ `asm', `asp', `aspx', `autoconf', `automake', `awk', `Awk',+ `basic', `batch', `bison', `c', `c++', `clojure', `csharp', `css', `csv', `dart', `Dart', `delphi', `elisp', `elixir',- `erlang', `fortran', `gif', `Gif', `go', `groovy', `gsp',+ `erlang', `fortran', `gif', `Gif', `go', `groovy', `gsp', `haskell', `html', `jade', `java', `jpeg', `Jpeg', `js', `json',- `jsp', `julia', `kotlin', `less', `lex', `lisp', `lua', `m4',- `make', `markdown', `matlab', `node', `Node', `objc', `objc++',+ `jsp', `julia', `kotlin', `less', `lex', `lisp', `lua', `m4',+ `make', `markdown', `matlab', `node', `Node', `objc', `objc++', `ocaml', `parrot', `pascal', `pdf', `Pdf', `perl', `Perl',- `php', `Php', `png', `Png', `prolog', `python', `Python', `r',- `rpm', `Rpm', `rst', `rtf', `Rtf', `ruby', `Ruby', `rust',- `scala', `scheme', `shell', `Shell', `smalltalk', `sql', `svg',- `swift', `tcl', `tex', `text', `tiff', `Tiff', `tt', `type-+ `php', `Php', `png', `Png', `prolog', `python', `Python', `r',+ `rpm', `Rpm', `rst', `rtf', `Rtf', `ruby', `Ruby', `rust',+ `scala', `scheme', `shell', `Shell', `smalltalk', `sql', `svg',+ `swift', `tcl', `tex', `text', `tiff', `Tiff', `tt', `type- script', `verilog', `vhdl', `vim', `xml', `Xml', `yacc', `yaml'. --tabs=NUM Set the tab size to NUM to expand tabs for option -k. The value of NUM may be 1, 2, 4, or 8. The default tab size is 8. + --tag[=TAG[,END]]+ Disables colors to mark up matches with TAG. If END is speci-+ fied, the end of a match is marked with END. The default is+ `___'.+ -U, --binary Disables Unicode matching for binary file matching, forcing PAT-- TERN to match bytes, not Unicode characters. For example, -U- '\xa3' matches byte A3 (hex) instead of the Unicode code point+ TERN to match bytes, not Unicode characters. For example, -U+ '\xa3' matches byte A3 (hex) instead of the Unicode code point U+00A3 represented by the two-byte UTF-8 sequence C2 A3. -u, --ungroup- Do not group multiple pattern matches on the same matched line.+ Do not group multiple pattern matches on the same matched line. Output the matched line again for each additional pattern match, using `+' as the field separator. @@ -3255,17 +3287,17 @@ in markdown: Display version information and exit. -v, --invert-match- Selected lines are those not matching any of the specified pat-+ Selected lines are those not matching any of the specified pat- terns. -W, --with-hex- Output binary matches in hexadecimal, leaving text matches+ Output binary matches in hexadecimal, leaving text matches alone. This option is equivalent to the --binary-files=with-hex option. -w, --word-regexp- The PATTERN is searched for as a word (as if surrounded by \<- and \>). If a PATTERN is specified (or -e PATTERN or -N PAT-+ The PATTERN is searched for as a word (as if surrounded by \<+ and \>). If a PATTERN is specified (or -e PATTERN or -N PAT- TERN), then this option does not apply to -f FILE patterns. -X, --hex@@ -3273,58 +3305,58 @@ in markdown: --binary-files=hex option. See also option --hexdump. -x, --line-regexp- Only input lines selected against the entire PATTERN is consid-- ered to be matching lines (as if surrounded by ^ and $). If a- PATTERN is specified (or -e PATTERN or -N PATTERN), then this+ Only input lines selected against the entire PATTERN is consid-+ ered to be matching lines (as if surrounded by ^ and $). If a+ PATTERN is specified (or -e PATTERN or -N PATTERN), then this option does not apply to -f FILE patterns. - --xml Output file matches in XML. If -H, -n, -k, or -b is specified,+ --xml Output file matches in XML. If -H, -n, -k, or -b is specified, additional values are output. See also options --format and -u. -Y, --empty- Permits empty matches. By default, empty matches are disabled,+ Permits empty matches. By default, empty matches are disabled, unless a pattern begins with `^' or ends with `$'. Note that -Y- when specified with an empty-matching pattern, such as x? and- x*, match all input, not only lines containing the character+ when specified with an empty-matching pattern, such as x? and+ x*, match all input, not only lines containing the character `x'. -y, --any-line Any matching or non-matching line is output. Non-matching lines- are output with the `-' separator as context of the matching- lines. See also options -A, -B, and -C. Disables multi-line+ are output with the `-' separator as context of the matching+ lines. See also options -A, -B, and -C. Disables multi-line matching. -Z, --null, -0 Prints a zero-byte after the file name. -z, --decompress- Decompress files to search, when compressed. Archives (.cpio,- .pax, .tar, and .zip) and compressed archives (e.g. .taz, .tgz,- .tpz, .tbz, .tbz2, .tb2, .tz2, .tlz, and .txz) are searched and- matching pathnames of files in archives are output in braces.- If -g, -O, -M, or -t is specified, searches files within ar-- chives whose name matches globs, matches file name extensions,- matches file signature magic bytes, or matches file types,- respectively. Supported compression formats: gzip (.gz), com-+ Decompress files to search, when compressed. Archives (.cpio,+ .pax, .tar, and .zip) and compressed archives (e.g. .taz, .tgz,+ .tpz, .tbz, .tbz2, .tb2, .tz2, .tlz, and .txz) are searched and+ matching pathnames of files in archives are output in braces.+ If -g, -O, -M, or -t is specified, searches files within ar-+ chives whose name matches globs, matches file name extensions,+ matches file signature magic bytes, or matches file types,+ respectively. Supported compression formats: gzip (.gz), com- press (.Z), zip, bzip2 (requires suffix .bz, .bz2, .bzip2, .tbz,- .tbz2, .tb2, .tz2), lzma and xz (requires suffix .lzma, .tlz,+ .tbz2, .tb2, .tz2), lzma and xz (requires suffix .lzma, .tlz, .xz, .txz). - If no FILE arguments are specified and input is read from a terminal,+ If no FILE arguments are specified and input is read from a terminal, recursive searches are performed as if -R is specified. To force read- ing from standard input, specify `-' as the FILE argument. - A `--' signals the end of options; the rest of the parameters are FILE+ A `--' signals the end of options; the rest of the parameters are FILE arguments, allowing filenames to begin with a `-' character. - The regular expression pattern syntax is an extended form of the POSIX+ The regular expression pattern syntax is an extended form of the POSIX ERE syntax. For an overview of the syntax see README.md or visit: https://github.com/Genivia/ugrep - Note that `.' matches any non-newline character. Pattern `\n' matches- a newline character. Multiple lines may be matched with patterns that- match newlines, unless one or more of the context options -A, -B, -C,+ Note that `.' matches any non-newline character. Pattern `\n' matches+ a newline character. Multiple lines may be matched with patterns that+ match newlines, unless one or more of the context options -A, -B, -C, or -y is used, or option -v is used. EXIT STATUS@@ -3336,22 +3368,22 @@ in markdown: >1 An error occurred. - If -q or --quiet or --silent is used and a line is selected, the exit+ If -q or --quiet or --silent is used and a line is selected, the exit status is 0 even if an error occurred. GLOBBING- Globbing is used by options -g, --include, --include-dir, --include-- from, --exclude, --exclude-dir, --exclude-from to match pathnames and- basenames in recursive searches. Globbing supports gitignore syntax+ Globbing is used by options -g, --include, --include-dir, --include-+ from, --exclude, --exclude-dir, --exclude-from to match pathnames and+ basenames in recursive searches. Globbing supports gitignore syntax and the corresponding matching rules. When a glob ends in a path sepa-- rator it matches directories as if --include-dir or --exclude-dir is- specified. When a glob contains a path separator `/', the full path-- name is matched. Otherwise the basename of a file or directory is- matched. For example, *.h matches foo.h and bar/foo.h. bar/*.h- matches bar/foo.h but not foo.h and not bar/bar/foo.h. Use a leading+ rator it matches directories as if --include-dir or --exclude-dir is+ specified. When a glob contains a path separator `/', the full path-+ name is matched. Otherwise the basename of a file or directory is+ matched. For example, *.h matches foo.h and bar/foo.h. bar/*.h+ matches bar/foo.h but not foo.h and not bar/bar/foo.h. Use a leading `/' to force /*.h to match foo.h but not bar/foo.h. - When a glob starts with a `!' as specified with -g!GLOB, or specified+ When a glob starts with a `!' as specified with -g!GLOB, or specified in a FILE with --include-from=FILE or --exclude-from=FILE, its match is negated. @@ -3367,12 +3399,12 @@ in markdown: [!a-z] Matches one character not in the selected range of characters. - / When used at the begin of a glob, matches if pathname has no /.+ / When used at the begin of a glob, matches if pathname has no /. When used at the end of a glob, matches directories only. **/ Matches zero or more directories. - /** When used at the end of a glob, matches everything after the /.+ /** When used at the end of a glob, matches everything after the /. \? Matches a ? (or any character specified after the backslash). @@ -3409,37 +3441,37 @@ in markdown: a\?b Matches a?b, but not a, b, ab, axb, a/b - Lines in the --exclude-from and --include-from files are ignored when- empty or start with a `#'. When a glob is prefixed with `!', negates+ Lines in the --exclude-from and --include-from files are ignored when+ empty or start with a `#'. When a glob is prefixed with `!', negates the match. ENVIRONMENT GREP_PATH- May be used to specify a file path to pattern files. The file- path is used by option -f to open a pattern file, when the file+ May be used to specify a file path to pattern files. The file+ path is used by option -f to open a pattern file, when the file cannot be opened. GREP_COLOR- May be used to specify ANSI SGR parameters to highlight matches- when option --color is used, e.g. 1;35;40 shows pattern matches+ May be used to specify ANSI SGR parameters to highlight matches+ when option --color is used, e.g. 1;35;40 shows pattern matches in bold magenta text on a black background. Deprecated in favor of GREP_COLORS, but still supported. GREP_COLORS- May be used to specify ANSI SGR parameters to highlight matches- and other attributes when option --color is used. Its value is- a colon-separated list of ANSI SGR parameters that defaults to+ May be used to specify ANSI SGR parameters to highlight matches+ and other attributes when option --color is used. Its value is+ a colon-separated list of ANSI SGR parameters that defaults to cx=33:mt=1;31:fn=1;35:ln=1;32:cn=1;32:bn=1;32:se=36. The mt=,- ms=, and mc= capabilities of GREP_COLORS have priority over+ ms=, and mc= capabilities of GREP_COLORS have priority over GREP_COLOR. Option --colors has priority over GREP_COLORS. GREP_COLORS- Colors are specified as string of colon-separated ANSI SGR parameters- of the form `what=substring', where `substring' is a semicolon-sepa-- rated list of ANSI SGR codes or `k' (black), `r' (red), `g' (green),- `y' (yellow), `b' (blue), `m' (magenta), `c' (cyan), `w' (white).- Upper case specifies background colors. A `+' qualifies a color as- bright. A foreground and a background color may be combined with one+ Colors are specified as string of colon-separated ANSI SGR parameters+ of the form `what=substring', where `substring' is a semicolon-sepa-+ rated list of ANSI SGR codes or `k' (black), `r' (red), `g' (green),+ `y' (yellow), `b' (blue), `m' (magenta), `c' (cyan), `w' (white).+ Upper case specifies background colors. A `+' qualifies a color as+ bright. A foreground and a background color may be combined with one or more font properties `n' (normal), `f' (faint), `h' (highlight), `i' (invert), `u' (underline). Substrings may be specified for: @@ -3451,10 +3483,10 @@ in markdown: mt= SGR substring for matching text in any matching line. - ms= SGR substring for matching text in a selected line. The sub-+ ms= SGR substring for matching text in a selected line. The sub- string mt= by default. - mc= SGR substring for matching text in a context line. The sub-+ mc= SGR substring for matching text in a context line. The sub- string mt= by default. fn= SGR substring for file names.@@ -3468,7 +3500,7 @@ in markdown: se= SGR substring for separators. FORMAT- Option --format=FORMAT specifies an output format for file matches.+ Option --format=FORMAT specifies an output format for file matches. Fields may be used in FORMAT, which expand into the following values: %[ARG]F@@ -3551,6 +3583,8 @@ in markdown: %e the ending byte offset of the match. + %g the group capture index of the match or zero (option -P).+ %u select unique lines only unless option -u is used. %, if not the first match: a comma, same as %[,]>.@@ -3563,27 +3597,27 @@ in markdown: %% the percentage sign. - %1 the first regex group capture of the match, and so on up to+ %1 the first regex group capture of the match, and so on up to group %9, same as %[1]#; requires option -P Perl matching. %[NUM]# the regex group capture NUM; requires option -P Perl matching. - The [ARG] part of a field is optional and may be omitted. When- present, the argument must be placed in [] brackets, for example %[,]F+ The [ARG] part of a field is optional and may be omitted. When+ present, the argument must be placed in [] brackets, for example %[,]F to output a comma, the pathname, and a separator. %[SEP]$ and %u are switches and do not send anything to the output. The separator used by %P, %H, %N, %K, %B, and %S may be changed by pre-- ceeding the field by %[SEP]$. When [SEP] is not provided, this+ ceeding the field by %[SEP]$. When [SEP] is not provided, this reverses the separator to the default separator or the separator speci- fied with --separator. Formatted output is written for each matching pattern, which means that- a line may be output multiple times when patterns match more than once- on the same line. When field %u is found anywhere in the specified- format string, matching lines are output only once unless option -u,+ a line may be output multiple times when patterns match more than once+ on the same line. When field %u is found anywhere in the specified+ format string, matching lines are output only once unless option -u, --ungroup is used or when a newline is matched. Additional formatting options:@@ -3645,7 +3679,7 @@ in markdown: $ ugrep -n -f c++/comments myfile.cpp - List the lines that need fixing in a C/C++ source file by looking for+ List the lines that need fixing in a C/C++ source file by looking for the word `FIXME' while skipping any `FIXME' in quoted strings: $ ugrep -e 'FIXME' -N '"(\\.|\\\r?\n|[^\\\n"])*"' myfile.cpp@@ -3684,9 +3718,9 @@ in markdown: $ ugrep -r -z -w --filter='pdf:pdftotext % -' 'copyright' - Match the binary pattern `A3hhhhA3hh' (hex) in a binary file without- Unicode pattern matching -U (which would otherwise match `\xaf' as a- Unicode character U+00A3 with UTF-8 byte sequence C2 A3) and display+ Match the binary pattern `A3hhhhA3hh' (hex) in a binary file without+ Unicode pattern matching -U (which would otherwise match `\xaf' as a+ Unicode character U+00A3 with UTF-8 byte sequence C2 A3) and display the results in hex with -X using `less -R' as a pager: $ ugrep --pager -UXo '\xa3[\x00-\xff]{2}\xa3[\x00-\xff]' a.out@@ -3699,7 +3733,7 @@ in markdown: $ ugrep -Rl '' --ignore-files - List all files containing a RPM signature, located in the `rpm' direc-+ List all files containing a RPM signature, located in the `rpm' direc- tory and recursively below up to two levels deeper (3 levels): $ ugrep -3 -l -tRpm '' rpm/@@ -3715,8 +3749,8 @@ in markdown: LICENSE- ugrep is released under the BSD-3 license. All parts of the software- have reasonable copyright terms permitting free redistribution. This+ ugrep is released under the BSD-3 license. All parts of the software+ have reasonable copyright terms permitting free redistribution. This includes the ability to reuse all or parts of the ugrep source tree. SEE ALSO@@ -3724,7 +3758,7 @@ in markdown: - ugrep 2.0.7 April 29, 2020 UGREP(1)+ ugrep 2.1.0 May 10, 2020 UGREP(1) <a name="patterns"/>
@@ -92,19 +92,22 @@ More info TODO class AbstractMatcher { protected: typedef int Method; ///< a method is one of Const::SCAN, Const::FIND, Const::SPLIT, Const::MATCH+ public: /// AbstractMatcher::Const common constants. struct Const {- static const Method SCAN = 0; ///< AbstractMatcher::match method is to scan input (tokenizer)- static const Method FIND = 1; ///< AbstractMatcher::match method is to find pattern in input- static const Method SPLIT = 2; ///< AbstractMatcher::match method is to split input at pattern matches- static const Method MATCH = 3; ///< AbstractMatcher::match method is to match the entire input- static const int NUL = '\0'; ///< NUL string terminator- static const int UNK = 256; ///< unknown/undefined character meta-char marker- static const int BOB = 257; ///< begin of buffer meta-char marker- static const int EOB = EOF; ///< end of buffer meta-char marker- static const size_t EMPTY = 0xFFFF; ///< accept() returns empty last split at end of input- static const size_t BLOCK = 8192; ///< buffer growth factor, buffer is initially 2*BLOCK size, at least 256+ static const Method SCAN = 0; ///< AbstractMatcher::match method is to scan input (tokenizer)+ static const Method FIND = 1; ///< AbstractMatcher::match method is to find pattern in input+ static const Method SPLIT = 2; ///< AbstractMatcher::match method is to split input at pattern matches+ static const Method MATCH = 3; ///< AbstractMatcher::match method is to match the entire input+ static const int NUL = '\0'; ///< NUL string terminator+ static const int UNK = 256; ///< unknown/undefined character meta-char marker+ static const int BOB = 257; ///< begin of buffer meta-char marker+ static const int EOB = EOF; ///< end of buffer meta-char marker+ static const size_t BLOCK = 8192; ///< buffer growth factor, buffer is initially 2*BLOCK size, at least 256+ static const size_t REDO = 0x7FFFFFFF; ///< reflex::Matcher::accept() returns "redo" with reflex::Matcher option "A"+ static const size_t EMPTY = 0xFFFFFFFF; ///< accept() returns "empty" last split at end of input };+ protected: /// AbstractMatcher::Options for matcher engines. struct Option { Option()
@@ -68,6 +68,7 @@ namespace convert_flag { const convert_flag_type dotall = 0x0080; ///< convert `.` (dot) to match all, same as `(?s)` const convert_flag_type freespace = 0x0100; ///< convert regex by removing spacing, same as `(?x)` const convert_flag_type notnewline = 0x0200; ///< inverted character classes do not match newline `\n`+ const convert_flag_type permissive = 0x0400; ///< convert Unicode to compact UTF-8 patterns and DFA, permits some invalid UTF-8 sequences } /// @brief Returns the converted regex string given a regex library signature and conversion flags, throws regex_error.
@@ -30,7 +30,7 @@ @file matcher.h @brief RE/flex matcher engine @author Robert van Engelen - engelen@genivia.com-@copyright (c) 2016-2019, Robert van Engelen, Genivia Inc. All rights reserved.+@copyright (c) 2016-2020, Robert van Engelen, Genivia Inc. All rights reserved. @copyright (c) BSD-3 License - see LICENSE.txt */ @@ -215,13 +215,13 @@ class Matcher : public PatternMatcher<reflex::Pattern> { fsm_.c1 = c1; } /// FSM code TAKE.- inline void FSM_TAKE(Pattern::Index cap)+ inline void FSM_TAKE(Pattern::Accept cap) { cap_ = cap; cur_ = pos_; } /// FSM code TAKE.- inline void FSM_TAKE(Pattern::Index cap, int c1)+ inline void FSM_TAKE(Pattern::Accept cap, int c1) { cap_ = cap; cur_ = pos_;@@ -231,26 +231,26 @@ class Matcher : public PatternMatcher<reflex::Pattern> { /// FSM code REDO. inline void FSM_REDO() {- cap_ = Const::EMPTY;+ cap_ = Const::REDO; cur_ = pos_; } /// FSM code REDO. inline void FSM_REDO(int c1) {- cap_ = Const::EMPTY;+ cap_ = Const::REDO; cur_ = pos_; if (c1 != EOF) --cur_; } /// FSM code HEAD.- inline void FSM_HEAD(Pattern::Index la)+ inline void FSM_HEAD(Pattern::Lookahead la) {- if (lap_.size() <= la && la < Pattern::Const::IMAX)+ if (lap_.size() <= la) lap_.resize(la + 1, -1); lap_[la] = static_cast<int>(pos_ - (txt_ - buf_)); } /// FSM code TAIL.- inline void FSM_TAIL(Pattern::Index la)+ inline void FSM_TAIL(Pattern::Lookahead la) { if (lap_.size() > la && lap_[la] >= 0) cur_ = txt_ - buf_ + static_cast<size_t>(lap_[la]);@@ -413,43 +413,52 @@ redo: while (true) { Pattern::Opcode opcode = *pc;- DBGLOG("Fetch: code[%zu] = 0x%08X", pc - pat_->opc_, opcode);- Pattern::Index index;- if (Pattern::is_opcode_halt(opcode))- break;- if (Pattern::is_opcode_meta(opcode))+ DBGLOG("Fetch: code[%u] = 0x%08X", pc - pat_->opc_, opcode);+ if (!Pattern::is_opcode_goto(opcode)) {- switch (opcode >> 16)+ switch (opcode >> 24) {- case 0xFF00: // TAKE- cap_ = Pattern::index_of(opcode);- DBGLOG("Take: cap = %zu", cap_);+ case 0xFE: // TAKE+ cap_ = Pattern::long_index_of(opcode); cur_ = pos_; ++pc;+ DBGLOG("Take: cap = %u", cap_); continue;- case 0xFF7E: // TAIL- index = Pattern::index_of(opcode);- DBGLOG("Tail: %u", index);- if (lap_.size() > index && lap_[index] >= 0)- cur_ = txt_ - buf_ + static_cast<size_t>(lap_[index]); // mind the (new) gap+ case 0xFD: // REDO+ cap_ = Const::REDO;+ DBGLOG("Redo");+ cur_ = pos_;+ ++pc;+ continue;+ case 0xFC: // TAIL+ {+ Pattern::Lookahead la = Pattern::lookahead_of(opcode);+ DBGLOG("Tail: %u", la);+ if (lap_.size() > la && lap_[la] >= 0)+ cur_ = txt_ - buf_ + static_cast<size_t>(lap_[la]); // mind the (new) gap ++pc; continue;- case 0xFF7F: // HEAD- index = Pattern::index_of(opcode);- DBGLOG("Head: lookahead[%u] = %zu", index, pos_ - (txt_ - buf_));- if (lap_.size() <= index)- lap_.resize(index + 1, -1);- lap_[index] = static_cast<int>(pos_ - (txt_ - buf_)); // mind the gap+ }+ case 0xFB: // HEAD+ {+ Pattern::Lookahead la = Pattern::lookahead_of(opcode);+ DBGLOG("Head: lookahead[%u] = %zu", la, pos_ - (txt_ - buf_));+ if (lap_.size() <= la)+ lap_.resize(la + 1, -1);+ lap_[la] = static_cast<int>(pos_ - (txt_ - buf_)); // mind the gap ++pc; continue;+ } #if !defined(WITH_NO_INDENT)- case 0xFF00 | Pattern::META_DED:+ case Pattern::META_DED - Pattern::META_MIN: if (ded_ > 0) {- index = Pattern::index_of(opcode);+ Pattern::Index jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(pc[1]); DBGLOG("Dedent ded = %zu", ded_); // unconditional dedent matching \j nul = true;- pc = pat_->opc_ + index;+ pc = pat_->opc_ + jump; continue; } #endif@@ -460,118 +469,182 @@ redo: c1 = get(); DBGLOG("Get: c1 = %d", c1); Pattern::Index back = Pattern::Const::IMAX; // where to jump back to (backtrack on meta transitions)- Pattern::Index la;- index = Pattern::Const::IMAX;+ Pattern::Index jump = Pattern::Const::IMAX; // to jump to longest sequence of matching metas while (true) {- if (Pattern::is_opcode_meta(opcode) && (index == Pattern::Const::IMAX || back == Pattern::Const::IMAX))+ if ((jump == Pattern::Const::IMAX || back == Pattern::Const::IMAX) && !Pattern::is_opcode_goto(opcode)) {- // we no longer have to pass through all if index and back are set- switch (opcode >> 16)+ // we no longer have to pass through all if jump and back are set+ switch (opcode >> 24) {- case 0xFF00: // TAKE- cap_ = Pattern::index_of(opcode);- DBGLOG("Take: cap = %zu", cap_);+ case 0xFE: // TAKE+ cap_ = Pattern::long_index_of(opcode);+ cur_ = pos_;+ if (c1 != EOF)+ --cur_; // must unget one char+ opcode = *++pc;+ DBGLOG("Take: cap = %u", cap_);+ continue;+ case 0xFD: // REDO+ cap_ = Const::REDO;+ DBGLOG("Redo"); cur_ = pos_; if (c1 != EOF) --cur_; // must unget one char opcode = *++pc; continue;- case 0xFF7E: // TAIL- la = Pattern::index_of(opcode);+ case 0xFC: // TAIL+ {+ Pattern::Lookahead la = Pattern::lookahead_of(opcode); DBGLOG("Tail: %u", la); if (lap_.size() > la && lap_[la] >= 0) cur_ = txt_ - buf_ + static_cast<size_t>(lap_[la]); // mind the (new) gap opcode = *++pc; continue;- case 0xFF7F: // HEAD+ }+ case 0xFB: // HEAD opcode = *++pc; continue; #if !defined(WITH_NO_INDENT)- case 0xFF00 | Pattern::META_DED:+ case Pattern::META_DED - Pattern::META_MIN: DBGLOG("DED? %d", c1);- if (index == Pattern::Const::IMAX && back == Pattern::Const::IMAX && bol && dedent())- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && back == Pattern::Const::IMAX && bol && dedent())+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_IND:+ case Pattern::META_IND - Pattern::META_MIN: DBGLOG("IND? %d", c1);- if (index == Pattern::Const::IMAX && back == Pattern::Const::IMAX && bol && indent())- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && back == Pattern::Const::IMAX && bol && indent())+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_UND:+ case Pattern::META_UND - Pattern::META_MIN: DBGLOG("UND"); if (mrk_)- index = Pattern::index_of(opcode);+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } mrk_ = false; ded_ = 0; opcode = *++pc; continue; #endif- case 0xFF00 | Pattern::META_EOB:+ case Pattern::META_EOB - Pattern::META_MIN: DBGLOG("EOB? %d", c1);- if (index == Pattern::Const::IMAX && c1 == EOF)- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && c1 == EOF)+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_BOB:+ case Pattern::META_BOB - Pattern::META_MIN: DBGLOG("BOB? %d", at_bob());- if (index == Pattern::Const::IMAX && at_bob())- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && at_bob())+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_EOL:+ case Pattern::META_EOL - Pattern::META_MIN: DBGLOG("EOL? %d", c1);- if (index == Pattern::Const::IMAX && (c1 == EOF || c1 == '\n'))- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && (c1 == EOF || c1 == '\n'))+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_BOL:+ case Pattern::META_BOL - Pattern::META_MIN: DBGLOG("BOL? %d", bol);- if (index == Pattern::Const::IMAX && bol)- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && bol)+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_EWE:+ case Pattern::META_EWE - Pattern::META_MIN: DBGLOG("EWE? %d %d %d", c0, c1, isword(c0) && !isword(c1));- if (index == Pattern::Const::IMAX && isword(c0) && !isword(c1))- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && isword(c0) && !isword(c1))+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_BWE:+ case Pattern::META_BWE - Pattern::META_MIN: DBGLOG("BWE? %d %d %d", c0, c1, !isword(c0) && isword(c1));- if (index == Pattern::Const::IMAX && !isword(c0) && isword(c1))- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && !isword(c0) && isword(c1))+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_EWB:+ case Pattern::META_EWB - Pattern::META_MIN: DBGLOG("EWB? %d", at_eow());- if (index == Pattern::Const::IMAX && at_eow())- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && at_eow())+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_BWB:+ case Pattern::META_BWB - Pattern::META_MIN: DBGLOG("BWB? %d", at_bow());- if (index == Pattern::Const::IMAX && at_bow())- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && at_bow())+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_NWE:+ case Pattern::META_NWE - Pattern::META_MIN: DBGLOG("NWE? %d %d %d", c0, c1, isword(c0) == isword(c1));- if (index == Pattern::Const::IMAX && isword(c0) == isword(c1))- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && isword(c0) == isword(c1))+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ } opcode = *++pc; continue;- case 0xFF00 | Pattern::META_NWB:+ case Pattern::META_NWB - Pattern::META_MIN: DBGLOG("NWB? %d %d", at_bow(), at_eow());- if (index == Pattern::Const::IMAX && !at_bow() && !at_eow())- index = Pattern::index_of(opcode);+ if (jump == Pattern::Const::IMAX && !at_bow() && !at_eow())+ {+ jump = Pattern::index_of(opcode);+ if (jump == Pattern::Const::LONG)+ jump = Pattern::long_index_of(*++pc);+ }+ opcode = *++pc;+ continue;+ case 0xFF: // LONG opcode = *++pc; continue; } }- if (index == Pattern::Const::IMAX)+ if (jump == Pattern::Const::IMAX) { if (back != Pattern::Const::IMAX) {@@ -580,18 +653,20 @@ redo: } break; }- DBGLOG("Backtrack: pc = %u", index);+ DBGLOG("Backtrack: pc = %u", jump); if (back == Pattern::Const::IMAX) back = static_cast<Pattern::Index>(pc - pat_->opc_);- pc = pat_->opc_ + index;+ pc = pat_->opc_ + jump; opcode = *pc;- index = Pattern::Const::IMAX;+ jump = Pattern::Const::IMAX; } if (c1 == EOF) break; } else {+ if (Pattern::is_opcode_halt(opcode))+ break; if (c1 == EOF) break; c1 = get();@@ -635,16 +710,24 @@ unrolled: } } }- index = Pattern::index_of(opcode);- if (index == Pattern::Const::IMAX)- break;- if (index == 0 && cap_ == 0) // failed to match so far, set cur_ to move forward from cur_ + 1 with FIND advance()- cur_ = pos_;- pc = pat_->opc_ + index;+ Pattern::Index jump = Pattern::index_of(opcode);+ if (jump == 0)+ {+ // loop back to start state: failed to match anything so far?+ if (cap_ == 0)+ cur_ = pos_; // set cur_ to move forward from cur_ + 1 with FIND advance()+ }+ else if (jump >= Pattern::Const::LONG)+ {+ if (jump == Pattern::Const::HALT)+ break;+ jump = Pattern::long_index_of(pc[1]);+ }+ pc = pat_->opc_ + jump; } } #if !defined(WITH_NO_INDENT)- if (mrk_ && cap_ != Const::EMPTY)+ if (mrk_ && cap_ != Const::REDO) { if (col_ > 0 && (tab_.empty() || tab_.back() < col_)) {@@ -779,7 +862,7 @@ unrolled: else if (len_ == 0 && cur_ == end_) { DBGLOG("Hit end: got = %d", got_);- if (cap_ == Const::EMPTY && !opt_.A)+ if (cap_ == Const::REDO && !opt_.A) cap_ = 0; } else@@ -787,7 +870,7 @@ unrolled: set_current(cur_); if (len_ > 0) {- if (cap_ == Const::EMPTY && !opt_.A)+ if (cap_ == Const::REDO && !opt_.A) { DBGLOG("Ignore accept and continue: len = %zu", len_); len_ = 0;
@@ -64,14 +64,17 @@ class Pattern { friend class Matcher; ///< permit access by the reflex::Matcher engine public: typedef uint8_t Pred; ///< predict match bits- typedef uint16_t Hash; ///< hash type (uint16_t), max value is Const::HASH- typedef uint16_t Index; ///< index into opcodes array Pattern::opc_ and subpattern indexing+ typedef uint16_t Hash; ///< hash value type, max value is Const::HASH+ typedef uint32_t Index; ///< index into opcodes array Pattern::opc_ and subpattern indexing+ typedef uint32_t Accept; ///< group capture index typedef uint32_t Opcode; ///< 32 bit opcode word typedef void (*FSM)(class Matcher&); ///< function pointer to FSM code /// Common constants. struct Const {- static const Index IMAX = 0xFFFF; ///< max index, also serves as a marker- static const Index HASH = 0x1000; ///< size of the predict match array+ static const Index IMAX = static_cast<Index>(~0U); ///< max index, also serves as a marker+ static const Index LONG = 0xFFFE; ///< LONG marker for 64 bit opcodes, must be HALT-1+ static const Index HALT = 0xFFFF; ///< HALT marker for GOTO opcodes, must be 16 bit max+ static const Hash HASH = 0x1000; ///< size of the predict match array }; /// Construct an unset pattern. explicit Pattern()@@ -235,7 +238,7 @@ class Pattern { { nop_ = pattern.nop_; Opcode *code = new Opcode[nop_];- for (Index i = 0; i < nop_; ++i)+ for (size_t i = 0; i < nop_; ++i) code[i] = pattern.opc_[i]; opc_ = code; }@@ -266,10 +269,10 @@ class Pattern { return assign(fsm); } /// Get the number of subpatterns of this pattern object.- Index size() const+ Accept size() const /// @returns number of subpatterns {- return static_cast<Index>(end_.size());+ return static_cast<Accept>(end_.size()); } /// Return true if this pattern is not assigned. bool empty() const@@ -278,11 +281,11 @@ class Pattern { return opc_ == NULL && fsm_ == NULL; } /// Get subpattern regex of this pattern object or the whole regex with index 0.- const std::string operator[](Index choice) const+ const std::string operator[](Accept choice) const /// @returns subpattern string or "" when not set ; /// Check if subpattern is reachable by a match.- bool reachable(Index choice) const+ bool reachable(Accept choice) const /// @returns true if subpattern is reachable { return choice >= 1 && choice <= size() && acc_.at(choice - 1);@@ -384,47 +387,89 @@ class Pattern { size_t pos = 0) ///< optional location of the error in regex string Pattern::rex_ const; private:- typedef unsigned int Char;-#if defined(WITH_BITS)- typedef Bits Chars; ///< represent char (0-255 + meta chars) set as a bitvector-#else- typedef ORanges<Char> Chars; ///< represent char (0-255 + meta chars) set as a set of ranges-#endif- typedef size_t Location;+ typedef uint16_t Char; // 8 bit char and meta chars up to META_MAX-1+ typedef uint8_t Lazy;+ typedef uint16_t Iter;+ typedef uint16_t Lookahead;+ typedef std::set<Lookahead> Lookaheads;+ typedef uint32_t Location; typedef ORanges<Location> Locations; typedef std::set<Location> Set; typedef std::map<int,Locations> Map;+ /// Set of chars and meta chars+ struct Chars {+ Chars() { clear(); }+ Chars(const Chars& c) { b[0] = c.b[0]; b[1] = c.b[1]; b[2] = c.b[2]; b[3] = c.b[3]; b[4] = c.b[4]; }+ Chars(const uint64_t c[5]) { b[0] = c[0]; b[1] = c[1]; b[2] = c[2]; b[3] = c[3]; b[4] = c[4]; }+ void clear() { b[0] = b[1] = b[2] = b[3] = b[4] = 0ULL; }+ bool any() const { return b[0] || b[1] || b[2] || b[3] || b[4]; }+ bool intersects(const Chars& c) const { return (b[0] & c.b[0]) || (b[1] & c.b[1]) || (b[2] & c.b[2]) || (b[3] & c.b[3]) || (b[4] & c.b[4]); }+ bool contains(const Chars& c) const { return !(c - *this).any(); }+ bool contains(Char c) const { return b[c >> 6] & (1ULL << (c & 0x3F)); }+ Chars& insert(Char c) { b[c >> 6] |= 1ULL << (c & 0x3F); return *this; }+ Chars& insert(Char lo, Char hi) { while (lo <= hi) insert(lo++); return *this; }+ Chars& flip() { b[0] = ~b[0]; b[1] = ~b[1]; b[2] = ~b[2]; b[3] = ~b[3]; b[4] = ~b[4]; return *this; }+ Chars& flip256() { b[0] = ~b[0]; b[1] = ~b[1]; b[2] = ~b[2]; b[3] = ~b[3]; return *this; }+ Chars& swap(Chars& c) { Chars t = c; c = *this; return *this = t; }+ Chars& operator+=(const Chars& c) { return operator|=(c); }+ Chars& operator-=(const Chars& c) { b[0] &=~c.b[0]; b[1] &=~c.b[1]; b[2] &=~c.b[2]; b[3] &=~c.b[3]; b[4] &=~c.b[4]; return *this; }+ Chars& operator|=(const Chars& c) { b[0] |= c.b[0]; b[1] |= c.b[1]; b[2] |= c.b[2]; b[3] |= c.b[3]; b[4] |= c.b[4]; return *this; }+ Chars& operator&=(const Chars& c) { b[0] &= c.b[0]; b[1] &= c.b[1]; b[2] &= c.b[2]; b[3] &= c.b[3]; b[4] &= c.b[4]; return *this; }+ Chars& operator^=(const Chars& c) { b[0] ^= c.b[0]; b[1] ^= c.b[1]; b[2] ^= c.b[2]; b[3] ^= c.b[3]; b[4] ^= c.b[4]; return *this; }+ Chars operator+(const Chars& c) const { return Chars(*this) += c; }+ Chars operator-(const Chars& c) const { return Chars(*this) -= c; }+ Chars operator|(const Chars& c) const { return Chars(*this) |= c; }+ Chars operator&(const Chars& c) const { return Chars(*this) &= c; }+ Chars operator^(const Chars& c) const { return Chars(*this) ^= c; }+ Chars operator~() const { return Chars(*this).flip(); }+ operator bool() const { return any(); }+ Chars& operator=(const Chars& c) { b[0] = c.b[0]; b[1] = c.b[1]; b[2] = c.b[2]; b[3] = c.b[3]; b[4] = c.b[4]; return *this; }+ bool operator==(const Chars& c) const { return b[0] == c.b[0] && b[1] == c.b[1] && b[2] == c.b[2] && b[3] == c.b[3] && b[4] == c.b[4]; }+ bool operator<(const Chars& c) const { return b[0] < c.b[0] || (b[0] == c.b[0] && (b[1] < c.b[1] || (b[1] == c.b[1] && (b[2] < c.b[2] || (b[2] == c.b[2] && (b[3] < c.b[3] || (b[3] == c.b[3] && b[4] < c.b[4]))))))); }+ bool operator>(const Chars& c) const { return c < *this; }+ bool operator<=(const Chars& c) const { return !(c < *this); }+ bool operator>=(const Chars& c) const { return !(*this < c); }+ Char lo() const { for (Char i = 0; i < 5; ++i) if (b[i]) for (Char j = 0; j < 64; ++j) if (b[i] & (1ULL << j)) return (i << 6) + j; return 0; }+ Char hi() const { for (Char i = 0; i < 5; ++i) if (b[4-i]) for (Char j = 0; j < 64; ++j) if (b[4-i] & (1ULL << (63-j))) return ((4-i) << 6) + (63-j); return 0; }+ uint64_t b[5]; ///< 256 bits for chars + bits for meta+ }; /// Finite state machine construction position information. struct Position { typedef uint64_t value_type;- static const value_type MAXLOC = (1 << 24) - 1;- static const value_type NPOS = static_cast<value_type>(~0ULL);- static const value_type TICKED = 1LL << 44;- static const value_type GREEDY = 1LL << 45;- static const value_type ANCHOR = 1LL << 46;- static const value_type ACCEPT = 1LL << 47;+ static const Iter MAXITER = 0xFFFF;+ static const Location MAXLOC = 0xFFFFFFFFUL;+ static const value_type NPOS = 0xFFFFFFFFFFFFFFFFULL;+ static const value_type RES1 = 1ULL << 48; ///< reserved+ static const value_type RES2 = 1ULL << 49; ///< reserved+ static const value_type RES3 = 1ULL << 50; ///< reserved+ static const value_type RES4 = 1ULL << 51; ///< reserved+ static const value_type TICKED = 1ULL << 52; ///< marks lookahead ending ) in (?=X)+ static const value_type GREEDY = 1ULL << 53; ///< force greedy quants+ static const value_type ANCHOR = 1ULL << 54; ///< marks begin of word anchors+ static const value_type ACCEPT = 1ULL << 55; ///< accept, not a regex position Position() : k(NPOS) { } Position(value_type k) : k(k) { } Position(const Position& p) : k(p.k) { } Position& operator=(const Position& p) { k = p.k; return *this; } operator value_type() const { return k; }- Position iter(Index i) const { return Position(k + (static_cast<value_type>(i) << 24)); }+ Position iter(Iter i) const { return Position(k + (static_cast<value_type>(i) << 32)); } Position ticked(bool b) const { return b ? Position(k | TICKED) : Position(k & ~TICKED); } Position greedy(bool b) const { return b ? Position(k | GREEDY) : Position(k & ~GREEDY); } Position anchor(bool b) const { return b ? Position(k | ANCHOR) : Position(k & ~ANCHOR); } Position accept(bool b) const { return b ? Position(k | ACCEPT) : Position(k & ~ACCEPT); }- Position lazy(Location l) const { return Position((k & 0x0000FFFFFFFFFFFFLL) | static_cast<value_type>(l) << 48); }- Position pos() const { return Position(k & 0x000000FFFFFFFFFFLL); }- Location loc() const { return static_cast<Location>(k & 0xFFFFFF); }- Index accepts() const { return static_cast<Index>(k & 0xFFFF); }- Index iter() const { return static_cast<Index>((k >> 24) & 0xFFFF); }+ Position lazy(Lazy l) const { return Position((k & 0x00FFFFFFFFFFFFFFULL) | static_cast<value_type>(l) << 56); }+ Position pos() const { return Position(k & 0x0000FFFFFFFFFFFFULL); }+ Location loc() const { return static_cast<Location>(k); }+ Accept accepts() const { return static_cast<Accept>(k); }+ Iter iter() const { return static_cast<Index>((k >> 32) & 0xFFFF); } bool ticked() const { return (k & TICKED) != 0; } bool greedy() const { return (k & GREEDY) != 0; } bool anchor() const { return (k & ANCHOR) != 0; } bool accept() const { return (k & ACCEPT) != 0; }- Location lazy() const { return static_cast<Location>((k >> 48) & 0xFFFF); }+ Lazy lazy() const { return static_cast<Lazy>(k >> 56); } value_type k; };+ typedef std::set<Lazy> Lazyset; typedef std::set<Position> Positions; typedef std::map<Position,Positions> Follow; typedef std::pair<Chars,Positions> Move;@@ -438,25 +483,27 @@ class Pattern { next(NULL), left(NULL), right(NULL),+ first(0), index(0), accept(0), redo(false) { }- State *next; ///< points to sibling state allocated depth-first by subset construction- State *left; ///< left pointer for O(log N) node insertion in the state graph- State *right; ///< right pointer for O(log N) node insertion in the state graph- Edges edges; ///< state transitions- Index index; ///< index of this state- Index accept; ///< nonzero if final state, the index of an accepted/captured subpattern- Set heads; ///< lookahead head set- Set tails; ///< lookahead tail set- bool redo; ///< true if this is an ignorable final state+ State *next; ///< points to next state in a linked list of states allocated by subset construction+ State *left; ///< left pointer for O(log N) node insertion in the hash overflow tree+ State *right; ///< right pointer for O(log N) node insertion in the hash overflow tree+ Edges edges; ///< state transitions+ Index first; ///< index of this state in the opcode table as determined by the first pass+ Index index; ///< index of this state in the opcode table+ Accept accept; ///< nonzero if final state, the index of an accepted/captured subpattern+ Lookaheads heads; ///< lookahead head set+ Lookaheads tails; ///< lookahead tail set+ bool redo; ///< true if this is an ignorable final state }; /// Global modifier modes, syntax flags, and compiler options. struct Option { Option() : b(), e(), f(), i(), l(), m(), n(), o(), p(), q(), r(), s(), w(), x(), z() { } bool b; ///< disable escapes in bracket lists- Char e; ///< escape character, or '\0' for none, '\\' default+ Char e; ///< escape character, or > 255 for none, '\\' default std::vector<std::string> f; ///< output to files bool i; ///< case insensitive mode, also `(?i:X)` bool l; ///< lex mode@@ -506,10 +553,11 @@ class Pattern { Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter);+ Iter& iter); void parse2( bool begin, Location& loc,@@ -517,10 +565,11 @@ class Pattern { Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter);+ Iter& iter); void parse3( bool begin, Location& loc,@@ -528,10 +577,11 @@ class Pattern { Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter);+ Iter& iter); void parse4( bool begin, Location& loc,@@ -539,21 +589,24 @@ class Pattern { Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter);- void parse_esc(Location& loc) const;+ Iter& iter);+ Char parse_esc(+ Location& loc,+ Chars *chars = NULL) const; void compile( State& start, Follow& followpos, const Map& modifiers, const Map& lookahead); void lazy(- const Positions& lazypos,- Positions& pos) const;+ const Lazyset& lazyset,+ Positions& pos) const; void lazy(- const Positions& lazypos,+ const Lazyset& lazyset, const Positions& pos, Positions& pos1) const; void greedy(Positions& pos) const;@@ -566,11 +619,8 @@ class Pattern { Moves& moves) const; void transition( Moves& moves,- const Chars& chars,+ Chars& chars, const Positions& follow) const;- Char compile_esc(- Location loc,- Chars& chars) const; void compile_list( Location loc, Chars& chars,@@ -599,7 +649,7 @@ class Pattern { void predict_match_dfa(State& start); void gen_predict_match(State *state); void gen_predict_match_transitions(State *state, std::map<State*,ORanges<Hash> >& states);- void gen_predict_match_transitions(Index level, State *state, ORanges<Hash>& labels, std::map<State*,ORanges<Hash> >& states);+ void gen_predict_match_transitions(size_t level, State *state, ORanges<Hash>& labels, std::map<State*,ORanges<Hash> >& states); void write_predictor(FILE *fd) const; void write_namespace_open(FILE* fd) const; void write_namespace_close(FILE* fd) const;@@ -621,20 +671,16 @@ class Pattern { } Char escape_at(Location loc) const {- if (opt_.e != '\0' && at(loc) == opt_.e)+ if (at(loc) == opt_.e) return at(loc + 1);- if (at(loc) == '[' && at(loc + 1) == '[' && at(loc + 2) == ':' && at(loc + 4) == ':' && at(loc + 5) == ']' && at(loc + 6) == ']')- return at(loc + 3); return '\0'; } Char escapes_at( Location loc, const char *escapes) const {- if (opt_.e != '\0' && at(loc) == opt_.e && std::strchr(escapes, at(loc + 1)))+ if (at(loc) == opt_.e && std::strchr(escapes, at(loc + 1))) return at(loc + 1);- if (at(loc) == '[' && at(loc + 1) == '[' && at(loc + 2) == ':' && std::strchr(escapes, at(loc + 3)) && at(loc + 4) == ':' && at(loc + 5) == ']' && at(loc + 6) == ']')- return at(loc + 3); return '\0'; } static bool is_modified(@@ -663,75 +709,101 @@ class Pattern { modifiers[mode].insert(from, to); } }+ static inline uint16_t hash_pos(const Positions& pos)+ {+ uint16_t h = 0;+ for (Positions::const_iterator i = pos.begin(); i != pos.end(); ++i)+ h += static_cast<uint16_t>(*i ^ (*i >> 24)); // (Position(*i).iter() << 4) unique hash for up to 16 chars iterated (abc...p){iter}+ return h;+ }+ static inline bool valid_goto_index(Index index)+ {+ return index <= 0xFEFFFF;+ }+ static inline bool valid_take_index(Index index)+ {+ return index <= 0xFDFFFF;+ }+ static inline bool valid_lookahead_index(Index index)+ {+ return index <= 0xFAFFFF;+ } static inline bool is_meta(Char c) {- return c > 0x100;+ return c > META_MIN;+ }+ static inline Opcode opcode_long(Index index)+ {+ return 0xFF000000 | (index & 0xFFFFFF); // index <= 0xFEFFFF max } static inline Opcode opcode_take(Index index) {- return 0xFF000000 | index;+ return 0xFE000000 | (index & 0xFFFFFF); // index <= 0xFDFFFF max } static inline Opcode opcode_redo() {- return 0xFF000000 | Const::IMAX;+ return 0xFD000000; } static inline Opcode opcode_tail(Index index) {- return 0xFF7E0000 | index;+ return 0xFC000000 | (index & 0xFFFFFF); // index <= 0xFBFFFF max } static inline Opcode opcode_head(Index index) {- return 0xFF7F0000 | index;+ return 0xFB000000 | (index & 0xFFFFFF); // index <= 0xFAFFFF max } static inline Opcode opcode_goto( Char lo, Char hi, Index index) {- if (!is_meta(lo)) return lo << 24 | hi << 16 | index;- return 0xFF000000 | (lo - META_MIN) << 16 | index;+ return is_meta(lo) ? (lo << 24) | index : (lo << 24) | (hi << 16) | index; } static inline Opcode opcode_halt() {- return 0x00FF0000 | Const::IMAX;+ return 0x00FFFFFF; }- static inline bool is_opcode_redo(Opcode opcode)+ static inline bool is_opcode_long(Opcode opcode) {- return opcode == (0xFF000000 | Const::IMAX);+ return (opcode & 0xFF000000) == 0xFF000000; } static inline bool is_opcode_take(Opcode opcode) {- return (opcode & 0xFFFF0000) == 0xFF000000;+ return (opcode & 0xFE000000) == 0xFE000000;+ }+ static inline bool is_opcode_redo(Opcode opcode)+ {+ return opcode == 0xFD000000; } static inline bool is_opcode_tail(Opcode opcode) {- return (opcode & 0xFFFF0000) == 0xFF7E0000;+ return (opcode & 0xFF000000) == 0xFC000000; } static inline bool is_opcode_head(Opcode opcode) {- return (opcode & 0xFFFF0000) == 0xFF7F0000;+ return (opcode & 0xFF000000) == 0xFB000000; } static inline bool is_opcode_halt(Opcode opcode) {- return opcode == (0x00FF0000 | Const::IMAX);+ return opcode == 0x00FFFFFF; }- static inline bool is_opcode_meta(Opcode opcode)+ static inline bool is_opcode_goto(Opcode opcode) {- return (opcode & 0xFF800000) == 0xFF000000;+ return (opcode << 8) >= (opcode & 0xFF000000); }- static inline bool is_opcode_meta(Opcode opcode, Char a)+ static inline bool is_opcode_meta(Opcode opcode) {- return (opcode & 0xFFFF0000) == (0xFF000000 | (a - META_MIN) << 16);+ return (opcode & 0x00FF0000) == 0x00000000 && (opcode >> 24) > 0; }- static inline bool is_opcode_match(+ static inline bool is_opcode_goto( Opcode opcode, unsigned char c) {- return c >= (opcode >> 24) && c <= (opcode >> 16 & 0xFF);+ return c >= (opcode >> 24) && c <= ((opcode >> 16) & 0xFF); } static inline Char meta_of(Opcode opcode) {- return META_MIN + (opcode >> 16 & 0xFF);+ return META_MIN + (opcode >> 24); } static inline Char lo_of(Opcode opcode) {@@ -739,12 +811,20 @@ class Pattern { } static inline Char hi_of(Opcode opcode) {- return is_opcode_meta(opcode) ? meta_of(opcode) : opcode >> 16 & 0xFF;+ return is_opcode_meta(opcode) ? meta_of(opcode) : (opcode >> 16) & 0xFF; } static inline Index index_of(Opcode opcode) { return opcode & 0xFFFF; }+ static inline Index long_index_of(Opcode opcode)+ {+ return opcode & 0xFFFFFF;+ }+ static inline Lookahead lookahead_of(Opcode opcode)+ {+ return opcode & 0xFFFF;+ } static inline Char lowercase(Char c) { return static_cast<unsigned char>(c | 0x20);@@ -772,7 +852,7 @@ class Pattern { size_t vno_; ///< number of finite state machine vertices |V| size_t eno_; ///< number of finite state machine edges |E| const Opcode *opc_; ///< points to the opcode table- Index nop_; ///< number of opcodes generated+ size_t nop_; ///< number of opcodes generated FSM fsm_; ///< function pointer to FSM code size_t len_; ///< prefix length of pre_[], less or equal to 255 size_t min_; ///< patterns after the prefix are at least this long but no more than 8
@@ -98,7 +98,7 @@ static std::string posix_class(const char *s, int esc) return regex; } -static std::string unicode_class(const char *s, int esc, const char *par)+static std::string unicode_class(const char *s, int esc, convert_flag_type flags, const char *par) { std::string regex; const int *wc = Unicode::range(s + (s[0] == '^'));@@ -111,13 +111,13 @@ static std::string unicode_class(const char *s, int esc, const char *par) if (wc[0] > 0xDFFF) { // exclude U+D800 to U+DFFF- regex.assign(utf8(0x00, 0xD7FF, esc, par)).push_back('|');+ regex.assign(utf8(0x00, 0xD7FF, esc, par, !(flags & convert_flag::permissive))).push_back('|'); if (wc[0] > 0xE000)- regex.append(utf8(0xE000, wc[0] - 1, esc, par)).push_back('|');+ regex.append(utf8(0xE000, wc[0] - 1, esc, par, !(flags & convert_flag::permissive))).push_back('|'); } else {- regex.assign(utf8(0x00, wc[0] - 1, esc, par)).push_back('|');+ regex.assign(utf8(0x00, wc[0] - 1, esc, par, !(flags & convert_flag::permissive))).push_back('|'); } } int last = wc[1] + 1;@@ -128,13 +128,13 @@ static std::string unicode_class(const char *s, int esc, const char *par) { // exclude U+D800 to U+DFFF if (last < 0xD800)- regex.append(utf8(last, 0xD7FF, esc, par)).push_back('|');+ regex.append(utf8(last, 0xD7FF, esc, par, !(flags & convert_flag::permissive))).push_back('|'); if (wc[0] > 0xE000)- regex.append(utf8(0xE000, wc[0] - 1, esc, par)).push_back('|');+ regex.append(utf8(0xE000, wc[0] - 1, esc, par, !(flags & convert_flag::permissive))).push_back('|'); } else {- regex.append(utf8(last, wc[0] - 1, esc, par)).push_back('|');+ regex.append(utf8(last, wc[0] - 1, esc, par, !(flags & convert_flag::permissive))).push_back('|'); } last = wc[1] + 1; }@@ -144,12 +144,12 @@ static std::string unicode_class(const char *s, int esc, const char *par) { // exclude U+D800 to U+DFFF if (last < 0xD800)- regex.append(utf8(last, 0xD7FF, esc, par)).push_back('|');- regex.append(utf8(0xE000, 0x10FFFF, esc, par)).push_back('|');+ regex.append(utf8(last, 0xD7FF, esc, par, !(flags & convert_flag::permissive))).push_back('|');+ regex.append(utf8(0xE000, 0x10FFFF, esc, par, !(flags & convert_flag::permissive))).push_back('|'); } else {- regex.append(utf8(last, 0x10FFFF, esc, par)).push_back('|');+ regex.append(utf8(last, 0x10FFFF, esc, par, !(flags & convert_flag::permissive))).push_back('|'); } } if (!regex.empty())@@ -157,10 +157,10 @@ static std::string unicode_class(const char *s, int esc, const char *par) } else {- regex.assign(utf8(wc[0], wc[1], esc, par));+ regex.assign(utf8(wc[0], wc[1], esc, par, !(flags & convert_flag::permissive))); wc += 2; for (; wc[1] != 0; wc += 2)- regex.append("|").append(utf8(wc[0], wc[1], esc, par));+ regex.append("|").append(utf8(wc[0], wc[1], esc, par, !(flags & convert_flag::permissive))); } } if (regex.find('|') != std::string::npos)@@ -235,7 +235,7 @@ inline int hex_or_octal_escape(const char *signature) // // //////////////////////////////////////////////////////////////////////////////// -static void convert_escape_char(const char *pattern, size_t& loc, size_t& pos, const char *signature, const std::map<size_t,std::string>& mod, const char *par, std::string& regex)+static void convert_escape_char(const char *pattern, size_t& loc, size_t& pos, convert_flag_type flags, const char *signature, const std::map<size_t,std::string>& mod, const char *par, std::string& regex) { int c = pattern[pos]; if (std::strchr(regex_unescapes, c) != NULL)@@ -261,7 +261,7 @@ static void convert_escape_char(const char *pattern, size_t& loc, size_t& pos, c if (is_modified(mod, 'u')) { if (!supports_escape(signature, invert ? 'P' : 'p'))- translated = unicode_class(name, esc, par);+ translated = unicode_class(name, esc, flags, par); } else if (!supports_escape(signature, c)) {@@ -565,7 +565,7 @@ static void convert_escape(const char *pattern, size_t len, size_t& loc, size_t& } else {- convert_escape_char(pattern, loc, pos, signature, mod, par, regex);+ convert_escape_char(pattern, loc, pos, flags, signature, mod, par, regex); } } else if (c == 'p' || c == 'P')@@ -595,7 +595,7 @@ static void convert_escape(const char *pattern, size_t len, size_t& loc, size_t& int esc = hex_or_octal_escape(signature); if (is_modified(mod, 'u')) {- translated = unicode_class(name.c_str(), esc, par);+ translated = unicode_class(name.c_str(), esc, flags, par); if (translated.empty()) { translated = posix_class(name.c_str(), esc);@@ -622,7 +622,7 @@ static void convert_escape(const char *pattern, size_t len, size_t& loc, size_t& } else {- convert_escape_char(pattern, loc, pos, signature, mod, par, regex);+ convert_escape_char(pattern, loc, pos, flags, signature, mod, par, regex); } } @@ -1209,12 +1209,12 @@ static void insert_list(const char *pattern, size_t len, size_t& pos, convert_fl throw regex_error(regex_error::empty_class, pattern, loc); } -static std::string convert_unicode_ranges(const ORanges<int>& ranges, const char *signature, const char *par)+static std::string convert_unicode_ranges(const ORanges<int>& ranges, convert_flag_type flags, const char *signature, const char *par) { std::string regex; int esc = hex_or_octal_escape(signature); for (ORanges<int>::const_iterator i = ranges.begin(); i != ranges.end(); ++i)- regex.append(utf8(i->first, i->second - 1, esc, par)).push_back('|');+ regex.append(utf8(i->first, i->second - 1, esc, par, !(flags & convert_flag::permissive))).push_back('|'); regex.resize(regex.size() - 1); if (regex.find('|') != std::string::npos) regex.insert(0, par).push_back(')');@@ -1253,12 +1253,12 @@ static void convert_anycase_ranges(ORanges<int>& ranges) ranges.insert(i->first ^ 0x20, (i->second - 1) ^ 0x20); } -static std::string convert_ranges(const char *pattern, size_t pos, ORanges<int>& ranges, const std::map<size_t,std::string>& mod, const char *signature, const char *par)+static std::string convert_ranges(const char *pattern, size_t pos, ORanges<int>& ranges, const std::map<size_t,std::string>& mod, convert_flag_type flags, const char *signature, const char *par) { if (is_modified(mod, 'i')) convert_anycase_ranges(ranges); if (is_modified(mod, 'u') && ranges.hi() > 0x7F)- return convert_unicode_ranges(ranges, signature, par);+ return convert_unicode_ranges(ranges, flags, signature, par); if (ranges.hi() > 0xFF) throw regex_error(regex_error::invalid_class, pattern, pos); return convert_posix_ranges(ranges, signature);@@ -1692,7 +1692,7 @@ std::string convert(const char *pattern, const char *signature, convert_flag_typ regex.append(&pattern[loc], pos - loc); ++pos; insert_list(pattern, len, pos, flags, mod, ranges, macros);- regex.append(convert_ranges(pattern, pos, ranges, mod, signature, par));+ regex.append(convert_ranges(pattern, pos, ranges, mod, flags, signature, par)); loc = pos + 1; anc = false; beg = false;@@ -1788,7 +1788,7 @@ std::string convert(const char *pattern, const char *signature, convert_flag_typ if (subpos + 1 < subregex.size()) throw regex_error(regex_error::invalid_class_range, pattern, loc); extend_list(pattern, len, pos, flags, mod, ranges, macros);- regex.append(convert_ranges(pattern, pos, ranges, mod, signature, par));+ regex.append(convert_ranges(pattern, pos, ranges, mod, flags, signature, par)); } else {
@@ -41,15 +41,22 @@ #include <cmath> /// DFA compaction: -1 == reverse order edge compression (best); 1 == edge compression; 0 == no edge compression.+/** Edge compression reorders edges to produce fewer tests when executed in the compacted order.+ For example ([a-cg-ik]|d|[e-g]|j|y|[x-z]) after reverse edge compression has only 2 edges:+ c1 = m.FSM_CHAR();+ if ('x' <= c1 && c1 <= 'z') goto S3;+ if ('a' <= c1 && c1 <= 'k') goto S3;+ return m.FSM_HALT(c1);+*/ #define WITH_COMPACT_DFA -1 #ifdef DEBUG # define DBGLOGPOS(p) \ if ((p).accept()) \ { \- DBGLOGA(" (%hu)", (p).accepts()); \+ DBGLOGA(" (%u)", (p).accepts()); \ if ((p).lazy()) \- DBGLOGA("?%zu", (p).lazy()); \+ DBGLOGA("?%u", (p).lazy()); \ if ((p).greedy()) \ DBGLOGA("!"); \ } \@@ -57,10 +64,10 @@ { \ DBGLOGA(" "); \ if ((p).iter()) \- DBGLOGA("%hu.", (p).iter()); \- DBGLOGA("%lu", (p).loc()); \+ DBGLOGA("%u.", (p).iter()); \+ DBGLOGA("%u", (p).loc()); \ if ((p).lazy()) \- DBGLOGA("?%zu", (p).lazy()); \+ DBGLOGA("?%u", (p).lazy()); \ if ((p).anchor()) \ DBGLOGA("^"); \ if ((p).greedy()) \@@ -89,7 +96,7 @@ static void print_char(FILE *file, int c, bool h = false) else if (std::isprint(c)) ::fprintf(file, "'%c'", c); else if (h)- ::fprintf(file, "%02X", c);+ ::fprintf(file, "%02x", c); else ::fprintf(file, "%u", c); }@@ -128,7 +135,7 @@ static const char *meta_label[] = { "DED", }; -const std::string Pattern::operator[](Index choice) const+const std::string Pattern::operator[](Accept choice) const { if (choice == 0) return rex_;@@ -226,7 +233,8 @@ void Pattern::init_options(const char *opt) opt_.b = true; break; case 'e':- opt_.e = (*(s += (s[1] == '=') + 1) == ';' ? '\0' : *s);+ opt_.e = (*(s += (s[1] == '=') + 1) == ';' || *s == '\0' ? 256 : *s++);+ --s; break; case 'p': opt_.p = true;@@ -304,11 +312,12 @@ void Pattern::parse( if (rex_.size() > Position::MAXLOC) throw regex_error(regex_error::exceeds_length, rex_, Position::MAXLOC); Location loc = 0;- Index choice = 1;+ Accept choice = 1;+ Lazy lazyidx = 0; Positions firstpos; Positions lastpos; bool nullable;- Index iter;+ Iter iter; timer_type t; timer_start(t); if (at(0) == '(' && at(1) == '?')@@ -351,7 +360,7 @@ void Pattern::parse( } do {- Positions lazypos;+ Lazyset lazyset; parse2( true, loc,@@ -359,7 +368,8 @@ void Pattern::parse( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead[choice], iter);@@ -367,29 +377,30 @@ void Pattern::parse( set_insert(startpos, firstpos); if (nullable) {- if (lazypos.empty())+ if (lazyset.empty()) { startpos.insert(Position(choice).accept(true)); } else {- for (Positions::const_iterator p = lazypos.begin(); p != lazypos.end(); ++p)- startpos.insert(Position(choice).accept(true).lazy(p->loc()));+ for (Lazyset::const_iterator l = lazyset.begin(); l != lazyset.end(); ++l)+ startpos.insert(Position(choice).accept(true).lazy(*l)); } } for (Positions::const_iterator p = lastpos.begin(); p != lastpos.end(); ++p) {- if (lazypos.empty())+ if (lazyset.empty()) { followpos[p->pos()].insert(Position(choice).accept(true)); } else {- for (Positions::const_iterator q = lazypos.begin(); q != lazypos.end(); ++q)- followpos[p->pos()].insert(Position(choice).accept(true).lazy(q->loc()));+ for (Lazyset::const_iterator l = lazyset.begin(); l != lazyset.end(); ++l)+ followpos[p->pos()].insert(Position(choice).accept(true).lazy(*l)); } }- ++choice;+ if (++choice == 0)+ error(regex_error::exceeds_limits, loc); // overflow: too many top-level alternations } while (at(loc++) == '|'); if (opt_.i) update_modified('i', modifiers, 0, rex_.size() - 1);@@ -423,12 +434,13 @@ void Pattern::parse1( Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter)+ Iter& iter) {- DBGLOG("BEGIN parse1(%zu)", loc);+ DBGLOG("BEGIN parse1(%u)", loc); parse2( begin, loc,@@ -436,15 +448,16 @@ void Pattern::parse1( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter); Positions firstpos1; Positions lastpos1; bool nullable1;- Positions lazypos1;- Index iter1;+ Lazyset lazyset1;+ Iter iter1; while (at(loc) == '|') { ++loc;@@ -455,13 +468,14 @@ void Pattern::parse1( lastpos1, nullable1, followpos,- lazypos1,+ lazyidx,+ lazyset1, modifiers, lookahead, iter1); set_insert(firstpos, firstpos1); set_insert(lastpos, lastpos1);- set_insert(lazypos, lazypos1);+ set_insert(lazyset, lazyset1); if (nullable1) nullable = true; if (iter1 > iter)@@ -477,12 +491,13 @@ void Pattern::parse2( Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter)+ Iter& iter) {- DBGLOG("BEGIN parse2(%zu)", loc);+ DBGLOG("BEGIN parse2(%u)", loc); Positions a_pos; if (begin) {@@ -517,15 +532,16 @@ void Pattern::parse2( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter); Positions firstpos1; Positions lastpos1; bool nullable1;- Positions lazypos1;- Index iter1;+ Lazyset lazyset1;+ Iter iter1; Position l_pos; Char c; while ((c = at(loc)) != '\0' && c != '|' && c != ')')@@ -539,19 +555,20 @@ void Pattern::parse2( lastpos1, nullable1, followpos,- lazypos1,+ lazyidx,+ lazyset1, modifiers, lookahead, iter1); if (c == '/' && l_pos != Position::NPOS) firstpos1.insert(l_pos);- if (!lazypos.empty()) // CHECKED this is an extra rule for + only and (may) not be needed for *+ if (!lazyset.empty()) // CHECKED this is an extra rule for + only and (may) not be needed for * {- // CHECKED algorithmic options: lazy(lazypos, firstpos1); does not work for (a|b)*?a*b+, below works+ // CHECKED algorithmic options: lazy(lazyset, firstpos1); does not work for (a|b)*?a*b+, below works Positions firstpos2;- lazy(lazypos, firstpos1, firstpos2);+ lazy(lazyset, firstpos1, firstpos2); set_insert(firstpos1, firstpos2);- // if (lazypos1.empty())+ // if (lazyset1.empty()) // greedy(firstpos1); // CHECKED algorithmic options: 8/1 works except fails for ((a|b)*?b){2} and (a|b)??(a|b)??aa } if (nullable)@@ -561,15 +578,15 @@ void Pattern::parse2( if (nullable1) { set_insert(lastpos, lastpos1);- set_insert(lazypos, lazypos1); // CHECKED 10/21+ set_insert(lazyset, lazyset1); // CHECKED 10/21 } else { lastpos.swap(lastpos1);- lazypos.swap(lazypos1); // CHECKED 10/21+ lazyset.swap(lazyset1); // CHECKED 10/21 nullable = false; }- // CHECKED 10/21 set_insert(lazypos, lazypos1);+ // CHECKED 10/21 set_insert(lazyset, lazyset1); if (iter1 > iter) iter = iter1; }@@ -605,12 +622,13 @@ void Pattern::parse3( Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter)+ Iter& iter) {- DBGLOG("BEGIN parse3(%zu)", loc);+ DBGLOG("BEGIN parse3(%u)", loc); Position b_pos(loc); parse4( begin,@@ -619,7 +637,8 @@ void Pattern::parse3( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter);@@ -635,21 +654,23 @@ void Pattern::parse3( nullable = true; if (at(++loc) == '?') {- lazypos.insert(loc);+ if (++lazyidx == 0)+ error(regex_error::exceeds_limits, loc);+ lazyset.insert(lazyidx); // overflow: exceeds max 255 lazy quantifiers if (nullable)- lazy(lazypos, firstpos);+ lazy(lazyset, firstpos); ++loc; } else { // CHECKED algorithmic options: 7/30 if (!nullable)- // CHECKED algorithmic options: 7/30 lazypos.clear();+ // CHECKED algorithmic options: 7/30 lazyset.clear(); greedy(firstpos); }- if (c == '+' && !nullable && !lazypos.empty())+ if (c == '+' && !nullable && !lazyset.empty()) { Positions firstpos1;- lazy(lazypos, firstpos, firstpos1);+ lazy(lazyset, firstpos, firstpos1); for (Positions::const_iterator p = lastpos.begin(); p != lastpos.end(); ++p) set_insert(followpos[p->pos()], firstpos1); set_insert(firstpos, firstpos1);@@ -665,10 +686,10 @@ void Pattern::parse3( size_t k = 0; for (Location i = 0; i < 7 && std::isdigit(c = at(++loc)); ++i) k = 10 * k + (c - '0');- if (k > Const::IMAX)+ if (k > Position::MAXITER) error(regex_error::exceeds_limits, loc);- Index n = static_cast<Index>(k);- Index m = n;+ Iter n = static_cast<Iter>(k);+ Iter m = n; bool unlimited = false; if (at(loc) == ',') {@@ -693,14 +714,16 @@ void Pattern::parse3( error(regex_error::invalid_repeat, loc); if (at(++loc) == '?') {- lazypos.insert(loc);+ if (++lazyidx == 0)+ error(regex_error::exceeds_limits, loc); // overflow: exceeds max 255 lazy quantifiers+ lazyset.insert(lazyidx); if (nullable) {- lazy(lazypos, firstpos);+ lazy(lazyset, firstpos); } /* CHECKED algorithmic options: 8/1 else {- lazy(lazypos, firstpos, firstpos1);+ lazy(lazyset, firstpos, firstpos1); set_insert(firstpos, firstpos1); pfirstpos = &firstpos1; } */@@ -709,15 +732,15 @@ void Pattern::parse3( else { // CHECKED algorithmic options 7/30 if (!nullable)- // CHECKED algorithmic options 7/30 lazypos.clear();- if (n < m && lazypos.empty())+ // CHECKED algorithmic options 7/30 lazyset.clear();+ if (n < m && lazyset.empty()) greedy(firstpos); } // CHECKED added pfirstpos to point to updated firstpos with lazy quants Positions firstpos1, *pfirstpos = &firstpos;- if (!nullable && !lazypos.empty()) // CHECKED algorithmic options 8/1 added to make ((a|b)*?b){2} work+ if (!nullable && !lazyset.empty()) // CHECKED algorithmic options 8/1 added to make ((a|b)*?b){2} work {- lazy(lazypos, firstpos, firstpos1);+ lazy(lazyset, firstpos, firstpos1); pfirstpos = &firstpos1; } if (nullable && unlimited) // {0,} == *@@ -727,37 +750,37 @@ void Pattern::parse3( } else if (m > 0) {- if (iter * m >= Const::IMAX)+ if (iter * m > Position::MAXITER) error(regex_error::exceeds_limits, loc); // update followpos by virtually repeating sub-regex m-1 times Follow followpos1; for (Follow::const_iterator fp = followpos.begin(); fp != followpos.end(); ++fp) if (fp->first.loc() >= b_pos)- for (Index i = 1; i < m; ++i)+ for (Iter i = 0; i < m - 1; ++i) for (Positions::const_iterator p = fp->second.begin(); p != fp->second.end(); ++p)- followpos1[fp->first.iter(iter * i)].insert(p->iter(iter * i));+ followpos1[fp->first.iter(iter * (i + 1))].insert(p->iter(iter * (i + 1))); for (Follow::const_iterator fp = followpos1.begin(); fp != followpos1.end(); ++fp) set_insert(followpos[fp->first], fp->second); // add m-1 times virtual concatenation (by indexed positions k.i)- for (Index i = 0; i < m - 1; ++i)+ for (Iter i = 0; i < m - 1; ++i) for (Positions::const_iterator k = lastpos.begin(); k != lastpos.end(); ++k) for (Positions::const_iterator j = pfirstpos->begin(); j != pfirstpos->end(); ++j) followpos[k->pos().iter(iter * i)].insert(j->iter(iter * i + iter)); if (unlimited) for (Positions::const_iterator k = lastpos.begin(); k != lastpos.end(); ++k) for (Positions::const_iterator j = pfirstpos->begin(); j != pfirstpos->end(); ++j)- followpos[k->pos().iter(iter * m - iter)].insert(j->iter(iter * m - iter));+ followpos[k->pos().iter(iter * (m - 1))].insert(j->iter(iter * (m - 1))); if (nullable1) { // extend firstpos when sub-regex is nullable Positions firstpos1 = *pfirstpos;- for (Index i = 1; i <= m - 1; ++i)+ for (Iter i = 1; i <= m - 1; ++i) for (Positions::const_iterator k = firstpos1.begin(); k != firstpos1.end(); ++k) firstpos.insert(k->iter(iter * i)); } // n to m-1 are optional with all 0 to m-1 are optional when nullable Positions lastpos1;- for (Index i = (nullable ? 0 : n - 1); i <= m - 1; ++i)+ for (Iter i = (nullable ? 0 : n - 1); i <= m - 1; ++i) for (Positions::const_iterator k = lastpos.begin(); k != lastpos.end(); ++k) lastpos1.insert(k->iter(iter * i)); lastpos.swap(lastpos1);@@ -767,7 +790,7 @@ void Pattern::parse3( { firstpos.clear(); lastpos.clear();- lazypos.clear();+ lazyset.clear(); } } else@@ -791,16 +814,17 @@ void Pattern::parse4( Positions& lastpos, bool& nullable, Follow& followpos,- Positions& lazypos,+ Lazy& lazyidx,+ Lazyset& lazyset, Map& modifiers, Locations& lookahead,- Index& iter)+ Iter& iter) {- DBGLOG("BEGIN parse4(%zu)", loc);+ DBGLOG("BEGIN parse4(%u)", loc); firstpos.clear(); lastpos.clear(); nullable = true;- lazypos.clear();+ lazyset.clear(); iter = 1; Char c = at(loc); if (c == '(')@@ -825,7 +849,8 @@ void Pattern::parse4( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter);@@ -842,7 +867,8 @@ void Pattern::parse4( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter);@@ -870,7 +896,8 @@ void Pattern::parse4( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter);@@ -906,7 +933,8 @@ void Pattern::parse4( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter);@@ -940,7 +968,8 @@ void Pattern::parse4( lastpos, nullable, followpos,- lazypos,+ lazyidx,+ lazyset, modifiers, lookahead, iter);@@ -964,11 +993,11 @@ void Pattern::parse4( { if (c == '[' && at(loc + 1) == ':') {- Location c_loc = find_at(loc + 2, ':');+ size_t c_loc = find_at(loc + 2, ':'); if (c_loc != std::string::npos && at(c_loc + 1) == ']')- loc = c_loc + 1;+ loc = static_cast<Location>(c_loc + 1); }- else if (c == opt_.e && opt_.e != '\0' && !opt_.b)+ else if (c == opt_.e && !opt_.b) { ++loc; }@@ -984,34 +1013,31 @@ void Pattern::parse4( bool quoted = (c == '"'); if (!quoted) ++loc;- Location q_loc = loc++;- if ((c = at(loc)) != '\0' && (!quoted || c != '"') && (quoted || c != opt_.e || at(loc + 1) != 'E'))+ Location q_loc = ++loc;+ c = at(loc);+ if (c != '\0' && (quoted ? c != '"' : c != opt_.e || at(loc + 1) != 'E')) { firstpos.insert(loc); Position p; do {- if (c == '\\' && at(loc + 1) == '"' && quoted)+ if (quoted && c == opt_.e && at(loc + 1) == '"') ++loc; if (p != Position::NPOS)- followpos[p].insert(loc);+ followpos[p.pos()].insert(loc); p = loc++;- } while ((c = at(loc)) != '\0' && (!quoted || c != '"') && (quoted || c != opt_.e || at(loc + 1) != 'E'));+ c = at(loc);+ } while (c != '\0' && (!quoted || c != '"') && (quoted || c != opt_.e || at(loc + 1) != 'E')); lastpos.insert(p); nullable = false;+ modifiers['q'].insert(q_loc, loc - 1); }- modifiers['q'].insert(q_loc, loc);- if (c != '\0')- {- if (!quoted)- ++loc;- if (at(loc) != '\0')- ++loc;- }+ if (!quoted && at(loc) != '\0')+ ++loc;+ if (at(loc) != '\0')+ ++loc; else- { error(regex_error::mismatched_quotation, loc);- } } else if (c == '#' && opt_.x) {@@ -1048,7 +1074,10 @@ void Pattern::parse4( firstpos.insert(loc); lastpos.insert(loc); nullable = false;- parse_esc(loc);+ if (c == opt_.e)+ (void)parse_esc(loc);+ else+ ++loc; } else if (begin && c != '\0') // permits empty regex pattern but not empty subpatterns {@@ -1057,63 +1086,140 @@ void Pattern::parse4( DBGLOG("END parse4()"); } -void Pattern::parse_esc(Location& loc) const+Pattern::Char Pattern::parse_esc(Location& loc, Chars *chars) const {- Char c;- if (at(loc++) == opt_.e && opt_.e != '\0' && (c = at(loc)) != '\0')+ Char c = at(++loc);+ if (c == '0') {- if (c == '0')+ c = 0;+ int d = at(++loc);+ if (d >= '0' && d <= '7') {- ++loc;- for (int i = 0; i < 3 && std::isdigit(at(loc)); ++i)- ++loc;+ c = d - '0';+ d = at(++loc);+ if (d >= '0' && d <= '7')+ {+ c = (c << 3) + d - '0';+ d = at(++loc);+ if (c < 32 && d >= '0' && d <= '7')+ {+ c = (c << 3) + d - '0';+ ++loc;+ }+ } }- else if ((c == 'p' || c == 'P') && at(loc + 1) == '{')+ }+ else if ((c == 'x' || c == 'u') && at(loc + 1) == '{')+ {+ c = 0;+ loc += 2;+ int d = at(loc);+ if (std::isxdigit(d)) {- ++loc;- while (std::isalnum(at(++loc)))- continue;- if (at(loc) == '}')+ c = (d > '9' ? (d | 0x20) - ('a' - 10) : d - '0');+ d = at(++loc);+ if (std::isxdigit(d))+ {+ c = (c << 4) + (d > '9' ? (d | 0x20) - ('a' - 10) : d - '0'); ++loc;- else- error(regex_error::invalid_escape, loc);+ } }- else if (c == 'u' && at(loc + 1) == '{')+ if (at(loc) == '}')+ ++loc;+ else+ error(regex_error::invalid_escape, loc);+ }+ else if (c == 'x' && std::isxdigit(at(loc + 1)))+ {+ int d = at(++loc);+ c = (d > '9' ? (d | 0x20) - ('a' - 10) : d - '0');+ d = at(++loc);+ if (std::isxdigit(d)) {+ c = (c << 4) + (d > '9' ? (d | 0x20) - ('a' - 10) : d - '0'); ++loc;- while (std::isxdigit(at(++loc)))- continue;+ }+ }+ else if (c == 'c')+ {+ c = at(++loc) % 32;+ ++loc;+ }+ else if (c == 'e')+ {+ c = 0x1B;+ ++loc;+ }+ else if (c == 'N')+ {+ if (chars != NULL)+ {+ chars->insert(0, 9);+ chars->insert(11, 255);+ }+ ++loc;+ c = META_EOL;+ }+ else if ((c == 'p' || c == 'P') && at(loc + 1) == '{')+ {+ loc += 2;+ if (chars != NULL)+ {+ size_t i;+ for (i = 0; i < 14; ++i)+ if (eq_at(loc, posix_class[i]))+ break;+ if (i < 14)+ posix(i, *chars);+ else+ error(regex_error::invalid_class, loc);+ if (c == 'P')+ flip(*chars);+ loc += strlen(posix_class[i]); if (at(loc) == '}') ++loc; else error(regex_error::invalid_escape, loc); }- else if (c == 'x' && at(loc + 1) == '{')+ else {- ++loc;- while (std::isxdigit(at(++loc)))+ while ((c = at(++loc)) != '\0' && c != '}') continue;- if (at(loc) == '}')+ if (c == '}') ++loc; else error(regex_error::invalid_escape, loc); }- else if (c == 'x')+ c = META_EOL;+ }+ else if (c != '_')+ {+ static const char abtnvfr[] = "abtnvfr";+ const char *s = std::strchr(abtnvfr, c);+ if (s != NULL) {- ++loc;- for (int i = 0; i < 2 && std::isxdigit(at(loc)); ++i)- ++loc;+ c = static_cast<Char>(s - abtnvfr + '\a'); } else {- if (c == 'c')- ++loc;- if (at(loc) != '\0')- ++loc;- else- error(regex_error::invalid_escape, loc);+ static const char escapes[] = "__sSxX________hHdD__lL__uUwW";+ s = std::strchr(escapes, c);+ if (s != NULL)+ {+ if (chars != NULL)+ {+ posix((s - escapes) / 2, *chars);+ if ((s - escapes) % 2)+ flip(*chars);+ }+ c = META_EOL;+ } }+ ++loc; }+ if (c <= 0xFF && chars != NULL)+ chars->insert(c);+ return c; } void Pattern::compile(@@ -1123,14 +1229,22 @@ void Pattern::compile( const Map& lookahead) { DBGLOG("BEGIN compile()");- State *back_state = &start;+ // init stats and timers vno_ = 0; eno_ = 0; ems_ = 0.0; timer_type vt, et; timer_start(vt);+ // construct the DFA acc_.resize(end_.size(), false); trim_lazy(start);+ // hash table with 64K entries (uint16_t indexed)+ State **table = new State*[65536];+ for (int i = 0; i < 65536; ++i)+ table[i] = NULL;+ table[hash_pos(start)] = &start;+ // last added state+ State *last_state = &start; for (State *state = &start; state; state = state->next) { Moves moves;@@ -1148,10 +1262,12 @@ void Pattern::compile( trim_lazy(pos); if (!pos.empty()) {- State *target_state = &start;- State **branch_ptr = NULL;- // binary search for a matching state- do+ State *target_state;+ uint16_t h = hash_pos(pos);+ State **branch_ptr = &table[h];+ target_state = *branch_ptr;+ // binary search for a matching state in the hash table overflow tree+ while (target_state != NULL) { if (pos < *target_state) target_state = *(branch_ptr = &target_state->left);@@ -1159,83 +1275,67 @@ void Pattern::compile( target_state = *(branch_ptr = &target_state->right); else break;- } while (target_state);- if (!target_state)- back_state = back_state->next = *branch_ptr = target_state = new State(pos);-#if defined(WITH_BITS)- Char lo = i->first.find_first(), j = lo, k = lo;- while (true)+ }+ if (target_state == NULL) {- if (j != k)- {- Char hi = k - 1;-#if WITH_COMPACT_DFA == -1- state->edges[lo] = std::pair<Char,State*>(hi, target_state);-#else- state->edges[hi] = std::pair<Char,State*>(lo, target_state);-#endif- lo = k = j;- }- j = i->first.find_next(j);- ++k;- ++eno_;- size_t n = i->first.find_next(j);- if (n == Bits::npos)+ last_state = last_state->next = target_state = new State(pos);+ if (branch_ptr != NULL)+ *branch_ptr = target_state;+ else+ table[h] = target_state;+ }+ Char lo = i->first.lo();+ Char max = i->first.hi();+ while (lo <= max)+ {+ if (i->first.contains(lo)) {- Char hi = k - 1;+ Char hi = lo + 1;+ while (hi <= max && i->first.contains(hi))+ ++hi;+ --hi; #if WITH_COMPACT_DFA == -1 state->edges[lo] = std::pair<Char,State*>(hi, target_state); #else state->edges[hi] = std::pair<Char,State*>(lo, target_state); #endif- break;+ eno_ += hi - lo + 1;+ lo = hi + 1; }- j = static_cast<Char>(n);- }-#else- for (Chars::const_iterator j = i->first.begin(); j != i->first.end(); ++j)- {- Char lo = j->first;- Char hi = j->second - 1; // -1 to adjust open ended [lo,hi)-#if WITH_COMPACT_DFA == -1- state->edges[lo] = std::pair<Char,State*>(hi, target_state);-#else- state->edges[hi] = std::pair<Char,State*>(lo, target_state);-#endif- eno_ += hi - lo + 1;+ ++lo; }-#endif } } if (state->accept > 0 && state->accept <= end_.size()) acc_[state->accept - 1] = true; ++vno_; }+ delete[] table; vms_ = timer_elapsed(vt) - ems_; DBGLOG("END compile()"); } void Pattern::lazy(- const Positions& lazypos,- Positions& pos) const+ const Lazyset& lazyset,+ Positions& pos) const {- if (!lazypos.empty())+ if (!lazyset.empty()) { Positions pos1;- lazy(lazypos, pos, pos1);+ lazy(lazyset, pos, pos1); pos.swap(pos1); } } void Pattern::lazy(- const Positions& lazypos,+ const Lazyset& lazyset, const Positions& pos, Positions& pos1) const { for (Positions::const_iterator p = pos.begin(); p != pos.end(); ++p)- for (Positions::const_iterator q = lazypos.begin(); q != lazypos.end(); ++q)- // pos1.insert(p->lazy() ? *p : p->lazy(q->loc())); // CHECKED algorithmic options: only if p is not already lazy??- pos1.insert(p->lazy(q->loc())); // overrides lazyness even when p is already lazy+ for (Lazyset::const_iterator l = lazyset.begin(); l != lazyset.end(); ++l)+ // pos1.insert(p->lazy() ? *p : p->lazy(*l)); // CHECKED algorithmic options: only if p is not already lazy??+ pos1.insert(p->lazy(*l)); // overrides lazyness even when p is already lazy } void Pattern::greedy(Positions& pos) const@@ -1336,7 +1436,7 @@ void Pattern::compile_transition( { if (k->accept()) {- Index accept = k->accepts();+ Accept accept = k->accepts(); if (state->accept == 0 || accept < state->accept) state->accept = accept; // pick lowest nonzero accept index if (accept == 0)@@ -1346,37 +1446,51 @@ void Pattern::compile_transition( { Location loc = k->loc(); Char c = at(loc);- DBGLOGN("At %lu: %c", loc, c);+ DBGLOGN("At %u: %c", loc, c); bool literal = is_modified('q', modifiers, loc); if (c == '/' && opt_.l && !literal) {- Position n(0);+ Lookahead n = 0; DBGLOG("LOOKAHEAD"); for (Map::const_iterator i = lookahead.begin(); i != lookahead.end(); ++i) { Locations::const_iterator j = i->second.find(loc);- DBGLOGN("%d %d (%d) %lu", state->accept, i->first, j != i->second.end(), n.loc());+ DBGLOGN("%d %d (%d) %u", state->accept, i->first, j != i->second.end(), n); if (j != i->second.end()) {- if (!k->ticked())- state->heads.insert(static_cast<Index>(n + std::distance(i->second.begin(), j)));+ Lookahead l = n + static_cast<Lookahead>(std::distance(i->second.begin(), j));+ if (l < n)+ error(regex_error::exceeds_limits, loc);+ if (k->ticked())+ state->tails.insert(l); else // CHECKED algorithmic options: 7/18 if (state->accept == i->first) no longer check for accept state, assume we are at an accept state- state->tails.insert(static_cast<Index>(n + std::distance(i->second.begin(), j)));+ state->heads.insert(l); }- n = n + i->second.size();+ Lookahead k = n;+ n += static_cast<Lookahead>(i->second.size());+ if (n < k)+ error(regex_error::exceeds_limits, loc); } } else if (c == '(' && !literal) {- Position n(0);+ Lookahead n = 0; DBGLOG("LOOKAHEAD HEAD"); for (Map::const_iterator i = lookahead.begin(); i != lookahead.end(); ++i) { Locations::const_iterator j = i->second.find(loc);- DBGLOGN("%d %d (%d) %lu", state->accept, i->first, j != i->second.end(), n.loc());+ DBGLOGN("%d %d (%d) %u", state->accept, i->first, j != i->second.end(), n); if (j != i->second.end())- state->heads.insert(static_cast<Index>(n + std::distance(i->second.begin(), j)));- n = n + i->second.size();+ {+ Lookahead l = n + static_cast<Lookahead>(std::distance(i->second.begin(), j));+ if (l < n)+ error(regex_error::exceeds_limits, loc);+ state->heads.insert(l);+ }+ Lookahead k = n;+ n += static_cast<Lookahead>(i->second.size());+ if (n < k)+ error(regex_error::exceeds_limits, loc); } } else if (c == ')' && !literal)@@ -1385,15 +1499,23 @@ void Pattern::compile_transition( if (state->accept > 0) */ {- Position n(0);+ Lookahead n = 0; DBGLOG("LOOKAHEAD TAIL"); for (Map::const_iterator i = lookahead.begin(); i != lookahead.end(); ++i) { Locations::const_iterator j = i->second.find(loc);- DBGLOGN("%d %d (%d) %lu", state->accept, i->first, j != i->second.end(), n.loc());+ DBGLOGN("%d %d (%d) %u", state->accept, i->first, j != i->second.end(), n); if (j != i->second.end() /* CHECKED algorithmic options: 7/18 && state->accept == i->first */ ) // only add lookstop when part of the proper accept state- state->tails.insert(static_cast<Index>(n + std::distance(i->second.begin(), j)));- n = n + i->second.size();+ {+ Lookahead l = n + std::distance(i->second.begin(), j);+ if (l < n)+ error(regex_error::exceeds_limits, loc);+ state->tails.insert(l);+ }+ Lookahead k = n;+ n += static_cast<Lookahead>(i->second.size());+ if (n < k)+ error(regex_error::exceeds_limits, loc); } } }@@ -1430,7 +1552,15 @@ void Pattern::compile_transition( Chars chars; if (literal) {- chars.insert(c);+ if (std::isalpha(c) && is_modified('i', modifiers, loc))+ {+ chars.insert(uppercase(c));+ chars.insert(lowercase(c));+ }+ else+ {+ chars.insert(c);+ } } else {@@ -1439,12 +1569,13 @@ void Pattern::compile_transition( case '.': if (is_modified('s', modifiers, loc)) {- chars.insert(0, 0xFF);+ static const uint64_t dot[5] = { 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0 };+ chars |= Chars(dot); } else {- chars.insert(0, 9);- chars.insert(11, 0xFF);+ static const uint64_t dot[5] = { 0xFFFFFFFFFFFFFBFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0 };+ chars |= Chars(dot); } break; case '^':@@ -1454,7 +1585,7 @@ void Pattern::compile_transition( chars.insert(is_modified('m', modifiers, loc) ? META_EOL : META_EOB); break; default:- if (c == '[' && !escapes_at(loc, "AzBb<>ij"))+ if (c == '[' && !escapes_at(loc, "AzBb<>ijk")) { compile_list(loc + 1, chars, modifiers); }@@ -1504,8 +1635,8 @@ void Pattern::compile_transition( } break; default:- c = compile_esc(loc + 1, chars);- if (c <= 255 && std::isalpha(c) && is_modified('i', modifiers, loc))+ c = parse_esc(loc, &chars);+ if (c <= 'z' && std::isalpha(c) && is_modified('i', modifiers, loc)) { chars.insert(uppercase(c)); chars.insert(lowercase(c));@@ -1524,131 +1655,53 @@ void Pattern::compile_transition( void Pattern::transition( Moves& moves,- const Chars& chars,+ Chars& chars, const Positions& follow) const {- Chars rest = chars; Moves::iterator i = moves.begin(); Moves::const_iterator end = moves.end(); while (i != end) {- if (i->second == follow)+ if (is_subset(i->second, follow)) {- rest |= i->first;+ chars += i->first; moves.erase(i++); }- else if (chars.intersects(i->first))+ else+ {+ ++i;+ }+ }+ for (i = moves.begin(); i != end; ++i)+ {+ if (chars.intersects(i->first)) {- Chars common(chars & i->first); if (is_subset(follow, i->second)) {- rest -= common;- ++i;+ chars -= i->first; }- else if (i->first == common)+ else {- if (is_subset(i->second, follow))+ if (chars.contains(i->first)) {- moves.erase(i++);+ chars -= i->first;+ set_insert(i->second, follow); } else {- rest -= common;- set_insert(i->second, follow);+ Move back(chars & i->first, i->second);+ set_insert(back.second, follow);+ chars -= back.first;+ i->first -= back.first;+ moves.push_back(back); } }- else- {- rest -= common;- i->first -= common;- Move back;- back.first.swap(common);- back.second = i->second;- set_insert(back.second, follow);- moves.push_back(back); // faster: C++11 emplace_back(Chars(), i->second); move.back().first.swap(common)- ++i;- }- }- else- {- ++i;- }- }- if (rest.any())- moves.push_back(Move(rest, follow)); // faster: C++11 move.emplace_back(rest, follow)-}--Pattern::Char Pattern::compile_esc(Location loc, Chars& chars) const-{- Char c = at(loc);- if (c == '0')- {- c = static_cast<Char>(std::strtoul(rex_.substr(loc + 1, 3).c_str(), NULL, 8));- }- else if ((c == 'x' || c == 'u') && at(loc + 1) == '{')- {- c = static_cast<Char>(std::strtoul(rex_.c_str() + 2, NULL, 16));- }- else if (c == 'x' && std::isxdigit(at(loc + 1)))- {- c = static_cast<Char>(std::strtoul(rex_.substr(loc + 1, 2).c_str(), NULL, 16));- }- else if (c == 'c')- {- c = at(loc + 1) % 32;- }- else if (c == 'e')- {- c = 0x1B;- }- else if (c == '_')- {- posix(6 /* alpha */, chars);- }- else if (c == 'N')- {- chars.insert(0, 9);- chars.insert(11, 255);- }- else if ((c == 'p' || c == 'P') && at(loc + 1) == '{')- {- size_t i;- for (i = 0; i < 14; ++i)- if (eq_at(loc + 2, posix_class[i]))- break;- if (i < 14)- posix(i, chars);- else- error(regex_error::invalid_class, loc);- if (c == 'P')- flip(chars);- return META_EOL;- }- else- {- static const char abtnvfr[] = "abtnvfr";- const char *s = std::strchr(abtnvfr, c);- if (s)- {- c = static_cast<Char>(s - abtnvfr + '\a');- }- else- {- static const char escapes[] = "__sSxX________hHdD__lL__uUwW";- s = std::strchr(escapes, c);- if (s)- {- posix((s - escapes) / 2, chars);- if ((s - escapes) % 2)- flip(chars);- return META_EOL;- }+ if (!chars.any())+ return; } }- if (c > 0xFF)- error(regex_error::invalid_escape, loc);- chars.insert(c);- return c;+ if (chars.any())+ moves.push_back(Move(chars, follow)); } void Pattern::compile_list(Location loc, Chars& chars, const Map& modifiers) const@@ -1666,11 +1719,14 @@ void Pattern::compile_list(Location loc, Chars& chars, const Map& modifiers) con } else {- Location c_loc;+ size_t c_loc; if (c == '[' && at(loc + 1) == ':' && (c_loc = find_at(loc + 2, ':')) != std::string::npos && at(c_loc + 1) == ']') { if (c_loc == loc + 3)- c = compile_esc(loc + 2, chars);+ {+ ++loc;+ c = parse_esc(loc, &chars);+ } else { size_t i;@@ -1683,12 +1739,11 @@ void Pattern::compile_list(Location loc, Chars& chars, const Map& modifiers) con error(regex_error::invalid_class, loc); c = META_EOL; }- loc = c_loc + 1;+ loc = static_cast<Location>(c_loc + 1); }- else if (c == opt_.e && opt_.e != '\0' && !opt_.b)+ else if (c == opt_.e && !opt_.b) {- c = compile_esc(loc + 1, chars);- parse_esc(loc);+ c = parse_esc(loc, &chars); --loc; } if (!is_meta(c))@@ -1737,84 +1792,28 @@ void Pattern::compile_list(Location loc, Chars& chars, const Map& modifiers) con void Pattern::posix(size_t index, Chars& chars) const { DBGLOG("posix(%lu)", index);- switch (index)- {- case 0:- chars.insert(0x00, 0x7F);- break;- case 1:- chars.insert('\t', '\r');- chars.insert(' ');- break;- case 2:- chars.insert('0', '9');- chars.insert('A', 'F');- chars.insert('a', 'f');- break;- case 3:- chars.insert(0x00, 0x1F);- chars.insert(0x7F);- break;- case 4:- chars.insert(' ', '~');- break;- case 5:- chars.insert('0', '9');- chars.insert('A', 'Z');- chars.insert('a', 'z');- break;- case 6:- chars.insert('A', 'Z');- chars.insert('a', 'z');- break;- case 7:- chars.insert('\t');- chars.insert(' ');- break;- case 8:- chars.insert('0', '9');- break;- case 9:- chars.insert('!', '~');- break;- case 10:- chars.insert('a', 'z');- break;- case 11:- chars.insert('!', '/');- chars.insert(':', '@');- chars.insert('[', '`');- chars.insert('{', '~');- break;- case 12:- chars.insert('A', 'Z');- break;- case 13:- chars.insert('0', '9');- chars.insert('A', 'Z');- chars.insert('a', 'z');- chars.insert('_');- break;- }+ static const uint64_t posix_chars[14][5] = {+ { 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0, 0, 0 }, // ASCII+ { 0x0000000100003E00, 0x0000000000000000, 0, 0, 0 }, // Space: \t-\r, ' '+ { 0x03FF000000000000, 0x0000007E0000007E, 0, 0, 0 }, // XDigit: 0-9, A-F, a-f+ { 0x00000000FFFFFFFF, 0x8000000000000000, 0, 0, 0 }, // Cntrl: \x00-0x1F, \0x7F+ { 0xFFFFFFFF00000000, 0x7FFFFFFFFFFFFFFF, 0, 0, 0 }, // Print: ' '-'~'+ { 0x03FF000000000000, 0x07FFFFFE07FFFFFE, 0, 0, 0 }, // Alnum: 0-9, A-Z, a-z+ { 0x0000000000000000, 0x07FFFFFE07FFFFFE, 0, 0, 0 }, // Alpha: A-Z, a-z+ { 0x0000000100000200, 0x0000000000000000, 0, 0, 0 }, // Blank: \t, ' '+ { 0x03FF000000000000, 0x0000000000000000, 0, 0, 0 }, // Digit: 0-9+ { 0xFFFFFFFE00000000, 0x7FFFFFFFFFFFFFFF, 0, 0, 0 }, // Graph: '!'-'~'+ { 0x0000000000000000, 0x07FFFFFE00000000, 0, 0, 0 }, // Lower: a-z+ { 0xFC00FFFE00000000, 0x78000001F8000001, 0, 0, 0 }, // Punct: '!'-'/', ':'-'@', '['-'`', '{'-'~'+ { 0x0000000000000000, 0x0000000007FFFFFE, 0, 0, 0 }, // Upper: A-Z+ { 0x03FF000000000000, 0x07FFFFFE87FFFFFE, 0, 0, 0 }, // Word: 0-9, A-Z, a-z, _+ };+ chars |= Chars(posix_chars[index]); } void Pattern::flip(Chars& chars) const {-#if defined(WITH_BITS)- chars.reserve(256).flip();-#else- Chars flip;- Char c = 0;- for (Chars::const_iterator i = chars.begin(); i != chars.end(); ++i)- {- if (c < i->first)- flip.insert(c, i->first - 1);- c = i->second;- }- if (c <= 0xFF)- flip.insert(c, 0xFF);- chars.swap(flip);-#endif+ chars.flip256(); } void Pattern::assemble(State& start)@@ -1826,10 +1825,10 @@ void Pattern::assemble(State& start) export_dfa(start); compact_dfa(start); encode_dfa(start);+ wms_ = timer_elapsed(t); gencode_dfa(start); delete_dfa(start); export_code();- wms_ = timer_elapsed(t); DBGLOG("END assemble()"); } @@ -1897,7 +1896,9 @@ void Pattern::encode_dfa(State& start) nop_ = 0; for (State *state = &start; state; state = state->next) {- state->index = nop_;+ if (state->accept > 0 && !valid_take_index(state->accept))+ throw regex_error(regex_error::exceeds_limits, rex_, rex_.size());+ state->first = state->index = nop_; #if WITH_COMPACT_DFA == -1 Char hi = 0x00; for (State::Edges::const_iterator i = state->edges.begin(); i != state->edges.end(); ++i)@@ -1909,7 +1910,7 @@ void Pattern::encode_dfa(State& start) if (is_meta(lo)) nop_ += i->second.first - lo; }- // add dead state only when needed+ // add dead state only when needed, i.e. skip dead state only if all input is covered if (hi <= 0xFF) { state->edges[hi] = std::pair<Char,State*>(0xFF, NULL);@@ -1926,53 +1927,149 @@ void Pattern::encode_dfa(State& start) if (i->second.first == 0x00) covered = true; else- lo = i->second.first - 1;+ lo = i->second.first - 1; } ++nop_; if (is_meta(lo)) nop_ += hi - i->second.first; }- // add dead state only when needed+ // add dead state only when needed, i.e. skip dead state only if all input is covered if (!covered) { state->edges[lo] = std::pair<Char,State*>(0x00, NULL); ++nop_; } #endif- nop_ += static_cast<Index>(state->heads.size() + state->tails.size() + (state->accept > 0 || state->redo));- if (nop_ < state->index)- throw regex_error(regex_error::exceeds_limits, rex_, rex_.size());+ nop_ += state->heads.size() + state->tails.size() + (state->accept > 0 || state->redo); }+ if (nop_ > Const::LONG)+ {+ // over 64K opcodes: use 64-bit GOTO opcodes+ nop_ = 0;+ for (State *state = &start; state; state = state->next)+ {+ state->index = nop_;+#if WITH_COMPACT_DFA == -1+ Char hi = 0x00;+ for (State::Edges::const_iterator i = state->edges.begin(); i != state->edges.end(); ++i)+ {+ Char lo = i->first;+ if (lo == hi)+ hi = i->second.first + 1;+ // use 64-bit jump opcode if forward jump determined by previous loop is beyond 32K or backward jump is beyond 64K+ if (i->second.second != NULL &&+ ((i->second.second->first > state->first && i->second.second->first >= Const::LONG / 2) ||+ i->second.second->index >= Const::LONG))+ nop_ += 2;+ else+ ++nop_;+ if (is_meta(lo))+ {+ // use 64-bit jump opcode if forward jump determined by previous loop is beyond 32K or backward jump is beyond 64K+ if (i->second.second != NULL &&+ ((i->second.second->first > state->first && i->second.second->first >= Const::LONG / 2) ||+ i->second.second->index >= Const::LONG))+ nop_ += 2 * (i->second.first - lo);+ else+ nop_ += i->second.first - lo;+ }+ }+#else+ Char lo = 0xFF;+ for (State::Edges::const_reverse_iterator i = state->edges.rbegin(); i != state->edges.rend(); ++i)+ {+ Char hi = i->first;+ if (lo == hi)+ lo = i->second.first - 1;+ // use 64-bit jump opcode if forward jump determined by previous loop is beyond 32K or backward jump is beyond 64K+ if (i->second.second != NULL &&+ ((i->second.second->first > state->first && i->second.second->first >= Const::LONG / 2) ||+ i->second.second->index >= Const::LONG))+ nop_ += 2;+ else+ ++nop_;+ if (is_meta(lo))+ {+ // use 64-bit jump opcode if forward jump determined by previous loop is beyond 32K or backward jump is beyond 64K+ if (i->second.second != NULL &&+ ((i->second.second->first > state->first && i->second.second->first >= Const::LONG / 2) ||+ i->second.second->index >= Const::LONG))+ nop_ += 2 * (hi - i->second.first);+ else+ nop_ += hi - i->second.first;+ }+ }+#endif+ nop_ += state->heads.size() + state->tails.size() + (state->accept > 0 || state->redo);+ }+ }+ if (!valid_goto_index(nop_))+ throw regex_error(regex_error::exceeds_limits, rex_, rex_.size()); Opcode *opcode = new Opcode[nop_]; opc_ = opcode; Index pc = 0; for (const State *state = &start; state; state = state->next) { if (state->redo)+ { opcode[pc++] = opcode_redo();+ } else if (state->accept > 0)+ { opcode[pc++] = opcode_take(state->accept);- for (Set::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)+ }+ for (Lookaheads::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)+ {+ if (!valid_lookahead_index(static_cast<Index>(*i)))+ throw regex_error(regex_error::exceeds_limits, rex_, rex_.size()); opcode[pc++] = opcode_tail(static_cast<Index>(*i));- for (Set::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)+ }+ for (Lookaheads::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)+ {+ if (!valid_lookahead_index(static_cast<Index>(*i)))+ throw regex_error(regex_error::exceeds_limits, rex_, rex_.size()); opcode[pc++] = opcode_head(static_cast<Index>(*i));+ } #if WITH_COMPACT_DFA == -1 for (State::Edges::const_reverse_iterator i = state->edges.rbegin(); i != state->edges.rend(); ++i) { Char lo = i->first; Char hi = i->second.first;- Index target_index = Const::IMAX;- if (i->second.second)- target_index = i->second.second->index;+ Index target_first = i->second.second != NULL ? i->second.second->first : Const::IMAX;+ Index target_index = i->second.second != NULL ? i->second.second->index : Const::IMAX; if (!is_meta(lo)) {- opcode[pc++] = opcode_goto(lo, hi, target_index);+ if (target_index == Const::IMAX)+ {+ opcode[pc++] = opcode_goto(lo, hi, Const::HALT);+ }+ else if (nop_ > Const::LONG && ((target_first > state->first && target_first >= Const::LONG / 2) || target_index >= Const::LONG))+ {+ opcode[pc++] = opcode_goto(lo, hi, Const::LONG);+ opcode[pc++] = opcode_long(target_index);+ }+ else+ {+ opcode[pc++] = opcode_goto(lo, hi, target_index);+ } } else { do {- opcode[pc++] = opcode_goto(lo, lo, target_index);+ if (target_index == Const::IMAX)+ {+ opcode[pc++] = opcode_goto(lo, lo, Const::HALT);+ }+ else if (nop_ > Const::LONG && ((target_first > state->first && target_first >= Const::LONG / 2) || target_index >= Const::LONG))+ {+ opcode[pc++] = opcode_goto(lo, lo, Const::LONG);+ opcode[pc++] = opcode_long(target_index);+ }+ else+ {+ opcode[pc++] = opcode_goto(lo, lo, target_index);+ } } while (++lo <= hi); } }@@ -1983,12 +2080,23 @@ void Pattern::encode_dfa(State& start) Char lo = i->second.first; if (is_meta(lo)) {- Index target_index = Const::IMAX;- if (i->second.second)- target_index = i->second.second->index;+ Index target_first = i->second.second != NULL ? i->second.second->first : Const::IMAX;+ Index target_index = i->second.second != NULL ? i->second.second->index : Const::IMAX; do {- opcode[pc++] = opcode_goto(lo, lo, target_index);+ if (target_index == Const::IMAX)+ {+ opcode[pc++] = opcode_goto(lo, lo, Const::HALT);+ }+ else if (nop_ > Const::LONG && ((target_first > state->first && target_first >= Const::LONG / 2) || target_index >= Const::LONG))+ {+ opcode[pc++] = opcode_goto(lo, lo, Const::LONG);+ opcode[pc++] = opcode_long(target_index);+ }+ else+ {+ opcode[pc++] = opcode_goto(lo, lo, target_index);+ } } while (++lo <= hi); } }@@ -1998,10 +2106,24 @@ void Pattern::encode_dfa(State& start) if (!is_meta(lo)) { Char hi = i->first;- Index target_index = Const::IMAX;- if (i->second.second)- target_index = i->second.second->index;- opcode[pc++] = opcode_goto(lo, hi, target_index);+ if (i->second.second != NULL)+ {+ Index target_first = i->second.second->first;+ Index target_index = i->second.second->index;+ if (nop_ > Const::LONG && ((target_first > state->first && target_first >= Const::LONG / 2) || target_index >= Const::LONG))+ {+ opcode[pc++] = opcode_goto(lo, hi, Const::LONG);+ opcode[pc++] = opcode_long(target_index);+ }+ else+ {+ opcode[pc++] = opcode_goto(lo, hi, target_index);+ }+ }+ else+ {+ opcode[pc++] = opcode_goto(lo, hi, Const::HALT);+ } } } #endif@@ -2057,10 +2179,10 @@ void Pattern::gencode_dfa(const State& start) const ::fprintf(file, " m.FSM_REDO();\n"); else if (state->accept > 0) ::fprintf(file, " m.FSM_TAKE(%u);\n", state->accept);- for (Set::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)- ::fprintf(file, " m.FSM_TAIL(%zu);\n", *i);- for (Set::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)- ::fprintf(file, " m.FSM_HEAD(%zu);\n", *i);+ for (Lookaheads::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)+ ::fprintf(file, " m.FSM_TAIL(%u);\n", *i);+ for (Lookaheads::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)+ ::fprintf(file, " m.FSM_HEAD(%u);\n", *i); if (state->edges.rbegin() != state->edges.rend() && state->edges.rbegin()->first == META_DED) ::fprintf(file, " if (m.FSM_DENT()) goto S%u;\n", state->edges.rbegin()->second.second->index); bool peek = false; // if we need to read a character into c1@@ -2356,8 +2478,8 @@ void Pattern::gencode_dfa_closure(FILE *file, const State *state, int nest, bool else ::fprintf(file, "%*sm.FSM_TAKE(%u);\n", 2*nest, "", state->accept); }- for (Set::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)- ::fprintf(file, "%*sm.FSM_TAIL(%zu);\n", 2*nest, "", *i);+ for (Lookaheads::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)+ ::fprintf(file, "%*sm.FSM_TAIL(%u);\n", 2*nest, "", *i); if (nest > 5) return; for (State::Edges::const_reverse_iterator i = state->edges.rbegin(); i != state->edges.rend(); ++i)@@ -2445,14 +2567,14 @@ void Pattern::export_dfa(const State& start) const { if (state == &start) ::fprintf(file, "\n/*START*/\t");- if (state->redo) // state->accept == Const::IMAX)+ if (state->redo) ::fprintf(file, "\n/*REDO*/\t"); else if (state->accept)- ::fprintf(file, "\n/*ACCEPT %hu*/\t", state->accept);- for (Set::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)- ::fprintf(file, "\n/*HEAD %zu*/\t", *i);- for (Set::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)- ::fprintf(file, "\n/*TAIL %zu*/\t", *i);+ ::fprintf(file, "\n/*ACCEPT %u*/\t", state->accept);+ for (Lookaheads::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)+ ::fprintf(file, "\n/*HEAD %u*/\t", *i);+ for (Lookaheads::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)+ ::fprintf(file, "\n/*TAIL %u*/\t", *i); if (state != &start && !state->accept && state->heads.empty() && state->tails.empty()) ::fprintf(file, "\n/*STATE*/\t"); ::fprintf(file, "N%p [label=\"", (void*)state);@@ -2465,16 +2587,16 @@ void Pattern::export_dfa(const State& start) const ::fprintf(file, "%s", sep); if (i->accept()) {- ::fprintf(file, "(%hu)", i->accepts());+ ::fprintf(file, "(%u)", i->accepts()); } else { if (i->iter())- ::fprintf(file, "%hu.", i->iter());- ::fprintf(file, "%zu", i->loc());+ ::fprintf(file, "%u.", i->iter());+ ::fprintf(file, "%u", i->loc()); } if (i->lazy())- ::fprintf(file, "?%zu", i->lazy());+ ::fprintf(file, "?%u", i->lazy()); if (i->anchor()) ::fprintf(file, "^"); if (i->greedy())@@ -2489,15 +2611,15 @@ void Pattern::export_dfa(const State& start) const if ((state->accept && !state->redo) || !state->heads.empty() || !state->tails.empty()) ::fprintf(file, "\\n"); #endif- if (state->accept && !state->redo) // state->accept != Const::IMAX)- ::fprintf(file, "[%hu]", state->accept);- for (Set::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)- ::fprintf(file, "%zu>", *i);- for (Set::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)- ::fprintf(file, "<%zu", *i);- if (state->redo) // state->accept != Const::IMAX)+ if (state->accept && !state->redo)+ ::fprintf(file, "[%u]", state->accept);+ for (Lookaheads::const_iterator i = state->tails.begin(); i != state->tails.end(); ++i)+ ::fprintf(file, "%u>", *i);+ for (Lookaheads::const_iterator i = state->heads.begin(); i != state->heads.end(); ++i)+ ::fprintf(file, "<%u", *i);+ if (state->redo) ::fprintf(file, "\",style=dashed,peripheries=1];\n");- else if (state->accept) // state->accept != Const::IMAX)+ else if (state->accept) ::fprintf(file, "\",peripheries=2];\n"); else if (!state->heads.empty()) ::fprintf(file, "\",style=dashed,peripheries=2];\n");@@ -2526,7 +2648,7 @@ void Pattern::export_dfa(const State& start) const else if (lo < 8) ::fprintf(file, "\\\\%u", lo); else- ::fprintf(file, "\\\\x%2.2x", lo);+ ::fprintf(file, "\\\\x%02x", lo); if (lo != hi) { ::fprintf(file, "-");@@ -2541,7 +2663,7 @@ void Pattern::export_dfa(const State& start) const else if (hi < 8) ::fprintf(file, "\\\\%u", hi); else- ::fprintf(file, "\\\\x%2.2x", hi);+ ::fprintf(file, "\\\\x%02x", hi); } ::fprintf(file, "\"];\n"); }@@ -2553,7 +2675,7 @@ void Pattern::export_dfa(const State& start) const } while (++lo <= hi); } }- if (state->redo) // state->accept == Const::IMAX)+ if (state->redo) ::fprintf(file, "\t\tN%p -> R%p;\n\t\tR%p [peripheries=0,label=\"redo\"];\n", (void*)state, (void*)state, (void*)state); } ::fprintf(file, "}\n");@@ -2566,7 +2688,7 @@ void Pattern::export_dfa(const State& start) const void Pattern::export_code() const {- if (!nop_)+ if (nop_ == 0) return; if (opt_.o) return;@@ -2591,27 +2713,28 @@ void Pattern::export_code() const { ::fprintf(file, "#ifndef REFLEX_CODE_DECL\n#include <reflex/pattern.h>\n#define REFLEX_CODE_DECL const reflex::Pattern::Opcode\n#endif\n\n"); write_namespace_open(file);- ::fprintf(file, "extern REFLEX_CODE_DECL reflex_code_%s[%hu] =\n{\n", opt_.n.empty() ? "FSM" : opt_.n.c_str(), nop_);+ ::fprintf(file, "extern REFLEX_CODE_DECL reflex_code_%s[%zu] =\n{\n", opt_.n.empty() ? "FSM" : opt_.n.c_str(), nop_); for (Index i = 0; i < nop_; ++i) { Opcode opcode = opc_[i];- ::fprintf(file, " 0x%08X, // %hu: ", opcode, i);- Index index = index_of(opcode);+ Char lo = lo_of(opcode);+ Char hi = hi_of(opcode);+ ::fprintf(file, " 0x%08X, // %u: ", opcode, i); if (is_opcode_redo(opcode)) { ::fprintf(file, "REDO\n"); } else if (is_opcode_take(opcode)) {- ::fprintf(file, "TAKE %u\n", index);+ ::fprintf(file, "TAKE %u\n", long_index_of(opcode)); } else if (is_opcode_tail(opcode)) {- ::fprintf(file, "TAIL %u\n", index);+ ::fprintf(file, "TAIL %u\n", long_index_of(opcode)); } else if (is_opcode_head(opcode)) {- ::fprintf(file, "HEAD %u\n", index);+ ::fprintf(file, "HEAD %u\n", long_index_of(opcode)); } else if (is_opcode_halt(opcode)) {@@ -2619,15 +2742,27 @@ void Pattern::export_code() const } else {- if (index == Const::IMAX)+ Index index = index_of(opcode);+ if (index == Const::HALT)+ { ::fprintf(file, "HALT ON ");+ } else- ::fprintf(file, "GOTO %u ON ", index);- Char lo = lo_of(opcode);+ {+ if (index == Const::LONG)+ {+ opcode = opc_[++i];+ index = long_index_of(opcode);+ ::fprintf(file, "GOTO\n 0x%08X, // %u: FAR %u ON ", opcode, i, index);+ }+ else+ {+ ::fprintf(file, "GOTO %u ON ", index);+ }+ } if (!is_meta(lo)) { print_char(file, lo, true);- Char hi = hi_of(opcode); if (lo != hi) { ::fprintf(file, "-");@@ -2674,7 +2809,7 @@ void Pattern::predict_match_dfa(State& start) one_ = false; break; }- pre_[len_++] = lo;+ pre_[len_++] = static_cast<uint8_t>(lo); } else {@@ -2699,34 +2834,34 @@ void Pattern::predict_match_dfa(State& start) { gen_predict_match(state); #ifdef DEBUG- for (Index i = 0; i < 256; ++i)+ for (Char i = 0; i < 256; ++i) { if (bit_[i] != 0xFF) { if (isprint(i))- DBGLOGN("bit['%c'] = %2x\n", i, bit_[i]);+ DBGLOGN("bit['%c'] = %02x", i, bit_[i]); else- DBGLOGN("bit[%3d] = %2x\n", i, bit_[i]);+ DBGLOGN("bit[%3d] = %02x", i, bit_[i]); } }- for (Index i = 0; i < Const::HASH; ++i)+ for (Hash i = 0; i < Const::HASH; ++i) { if (pmh_[i] != 0xFF) { if (isprint(pmh_[i]))- DBGLOGN("pmh['%c'] = %2x\n", i, pmh_[i]);+ DBGLOGN("pmh['%c'] = %02x", i, pmh_[i]); else- DBGLOGN("pmh[%3d] = %2x\n", i, pmh_[i]);+ DBGLOGN("pmh[%3d] = %02x", i, pmh_[i]); } }- for (Index i = 0; i < Const::HASH; ++i)+ for (Hash i = 0; i < Const::HASH; ++i) { if (pma_[i] != 0xFF) { if (isprint(pma_[i]))- DBGLOGN("pma['%c'] = %2x\n", i, pma_[i]);+ DBGLOGN("pma['%c'] = %02x", i, pma_[i]); else- DBGLOGN("pma[%3d] = %2x\n", i, pma_[i]);+ DBGLOGN("pma[%3d] = %02x", i, pma_[i]); } } #endif@@ -2740,7 +2875,7 @@ void Pattern::gen_predict_match(State *state) min_ = 8; std::map<State*,ORanges<Hash> > states[8]; gen_predict_match_transitions(state, states[0]);- for (Index level = 1; level < 8; ++level)+ for (int level = 1; level < 8; ++level) for (std::map<State*,ORanges<Hash> >::iterator from = states[level - 1].begin(); from != states[level - 1].end(); ++from) gen_predict_match_transitions(level, from->first, from->second, states[level]); for (Char i = 0; i < 256; ++i)@@ -2793,7 +2928,7 @@ void Pattern::gen_predict_match_transitions(State *state, std::map<State*,ORange } } -void Pattern::gen_predict_match_transitions(Index level, State *state, ORanges<Hash>& labels, std::map<State*,ORanges<Hash> >& states)+void Pattern::gen_predict_match_transitions(size_t level, State *state, ORanges<Hash>& labels, std::map<State*,ORanges<Hash> >& states) { for (State::Edges::const_iterator edge = state->edges.begin(); edge != state->edges.end(); ++edge) {@@ -2834,7 +2969,7 @@ void Pattern::gen_predict_match_transitions(Index level, State *state, ORanges<H { for (lo = edge->first; lo <= hi; ++lo) {- Hash h = hash(label_lo, lo);+ Hash h = hash(label_lo, static_cast<uint8_t>(lo)); pmh_[h] &= ~(1 << level); if (level < 4) {@@ -2861,17 +2996,17 @@ void Pattern::write_predictor(FILE *file) const { if (min_ > 1 && len_ == 0) {- for (Index i = 0; i < 256; ++i)+ for (Char i = 0; i < 256; ++i) ::fprintf(file, "%s%3hhu,", (i & 0xF) ? "" : "\n ", static_cast<uint8_t>(~bit_[i])); } if (min_ >= 4) {- for (Index i = 0; i < Const::HASH; ++i)+ for (Hash i = 0; i < Const::HASH; ++i) ::fprintf(file, "%s%3hhu,", (i & 0xF) ? "" : "\n ", static_cast<uint8_t>(~pmh_[i])); } else {- for (Index i = 0; i < Const::HASH; ++i)+ for (Hash i = 0; i < Const::HASH; ++i) ::fprintf(file, "%s%3hhu,", (i & 0xF) ? "" : "\n ", static_cast<uint8_t>(~pma_[i])); } }
@@ -105,6 +105,7 @@ static const char *regex_range(char *buf, int a, int b, int esc, bool brackets = return buf; } +/// Convert an 8-bit ASCII + Latin-1 Supplement range [a,b] to a regex pattern. std::string latin1(int a, int b, int esc, bool brackets) { if (a < 0)@@ -115,13 +116,14 @@ std::string latin1(int a, int b, int esc, bool brackets) return regex_range(buf, a, b, esc, brackets); } +/// Convert a UCS-4 range [a,b] to a UTF-8 regex pattern. std::string utf8(int a, int b, int esc, const char *par, bool strict) { if (a < 0) return ""; // undefined if (a > b) b = a;- static const char *min_utf8_strict[6] = { // strict: exact UTF-8 validation+ static const char *min_utf8_strict[6] = { // strict: pattern is strict, matching only strictly valid UTF-8 "\x00", "\xc2\x80", "\xe0\xa0\x80",@@ -129,7 +131,7 @@ std::string utf8(int a, int b, int esc, const char *par, bool strict) "\xf8\x88\x80\x80\x80", "\xfc\x84\x80\x80\x80\x80" };- static const char *min_utf8_lean[6] = { // lean: permissive UTF-8 validation with more tightly compressed UTF-8+ static const char *min_utf8_lean[6] = { // lean: pattern is permissive, matching also some invalid UTF-8 but more tightly compressed UTF-8 "\x00", "\xc2\x80", "\xe0\x80\x80",
@@ -15,7 +15,7 @@ mkdir -p man echo '.TH UGREP "1" "'`date '+%B %d, %Y'`'" "ugrep '$1'" "User Commands"' > man/ugrep.1 cat >> man/ugrep.1 << 'END' .SH NAME-\fBugrep\fR -- universal file pattern searcher+\fBugrep\fR -- file pattern searcher .SH SYNOPSIS .B ugrep [\fIOPTIONS\fR] [\fB-A\fR \fINUM\fR] [\fB-B\fR \fINUM\fR] [\fB-C\fR[\fINUM\fR]] [\fIPATTERN\fR] [\fB-e\fR \fIPATTERN\fR]@@ -283,6 +283,8 @@ the width of the match, counting wide characters. the size of the match, counting bytes. .IP \fB%e\fR the ending byte offset of the match.+.IP \fB%g\fR+the group capture index of the match or zero (option -P). .IP \fB%u\fR select unique lines only unless option \fB-u\fR is used. .IP \fB%,\fR
@@ -1,6 +1,6 @@-.TH UGREP "1" "April 29, 2020" "ugrep 2.0.7" "User Commands"+.TH UGREP "1" "May 10, 2020" "ugrep 2.1.0" "User Commands" .SH NAME-\fBugrep\fR -- universal file pattern searcher+\fBugrep\fR -- file pattern searcher .SH SYNOPSIS .B ugrep [\fIOPTIONS\fR] [\fB-A\fR \fINUM\fR] [\fB-B\fR \fINUM\fR] [\fB-C\fR[\fINUM\fR]] [\fIPATTERN\fR] [\fB-e\fR \fIPATTERN\fR]@@ -433,7 +433,7 @@ searches after the last key press, in increments of 100ms, where the default is 5 (0.5s delay). Initial patterns may be specified with \fB\-e\fR \fIPATTERN\fR, i.e. a PATTERN argument requires option \fB\-e\fR. Press F1 or CTRL\-Z to view the help screen. No whitespace may be given-between \fB\-Q\fR and its argument DELAY.+between \fB\-Q\fR and its argument DELAY. Enables \fB\-\-heading\fR. .TP \fB\-q\fR, \fB\-\-quiet\fR, \fB\-\-silent\fR Quiet mode: suppress all output. ugrep will only search until a@@ -514,6 +514,10 @@ option may be repeated. The possible file types can be (where Set the tab size to NUM to expand tabs for option \fB\-k\fR. The value of NUM may be 1, 2, 4, or 8. The default tab size is 8. .TP+\fB\-\-tag[\fR=\fITAG\fR[,\fIEND\fR]]+Disables colors to mark up matches with TAG. If END is specified,+the end of a match is marked with END. The default is `___'.+.TP \fB\-U\fR, \fB\-\-binary\fR Disables Unicode matching for binary file matching, forcing PATTERN to match bytes, not Unicode characters. For example, \fB\-U\fR '\\xa3'@@ -800,6 +804,8 @@ the width of the match, counting wide characters. the size of the match, counting bytes. .IP \fB%e\fR the ending byte offset of the match.+.IP \fB%g\fR+the group capture index of the match or zero (option -P). .IP \fB%u\fR select unique lines only unless option \fB-u\fR is used. .IP \fB%,\fR
@@ -527,6 +527,10 @@ void Output::format(const char *format, const char *pathname, const std::string& num(matcher->last()); break; + case 'g':+ num(matcher->accept());+ break;+ case 'm': num(matches); break;
@@ -67,7 +67,7 @@ After this, you may want to test ugrep and install it (optional): */ // ugrep version-#define UGREP_VERSION "2.0.7"+#define UGREP_VERSION "2.1.0" #include "ugrep.hpp" #include "glob.hpp"@@ -155,6 +155,11 @@ After this, you may want to test ugrep and install it (optional): # endif #endif +// the default --tag+#ifndef DEFAULT_TAG+# define DEFAULT_TAG "___"+#endif+ // the default pager when --pager is used #ifndef DEFAULT_PAGER # ifdef OS_WIN@@ -307,11 +312,12 @@ char color_cn[COLORLEN]; // column number char color_bn[COLORLEN]; // byte offset char color_se[COLORLEN]; // separator -char match_ms[COLORLEN]; // --match: matched text in a selected line-char match_mc[COLORLEN]; // --match: matched text in a context line+char match_ms[COLORLEN]; // --match or --tag: matched text in a selected line+char match_mc[COLORLEN]; // --match or --tag: matched text in a context line+char match_off[COLORLEN]; // --match or --tag: off -const char *color_del = ""; // erase line after the cursor const char *color_off = ""; // disable colors+const char *color_del = ""; // erase line after the cursor const char *color_high = ""; // stderr highlighted text const char *color_error = ""; // stderr error text@@ -395,7 +401,6 @@ bool flag_decompress = false; bool flag_any_line = false; bool flag_heading = false; bool flag_break = false;-bool flag_stats = false; bool flag_cpp = false; bool flag_csv = false; bool flag_json = false;@@ -429,6 +434,7 @@ size_t flag_max_mmap = DEFAULT_MAX_MMAP_SIZE; size_t flag_min_steal = MIN_STEAL; const char *flag_pager = FLAG_PAGER; const char *flag_color = FLAG_COLOR;+const char *flag_tag = NULL; const char *flag_apply_color = NULL; const char *flag_hexdump = NULL; const char *flag_colors = NULL;@@ -440,6 +446,7 @@ const char *flag_format_end = NULL; const char *flag_format_open = NULL; const char *flag_format_close = NULL; const char *flag_sort = NULL;+const char *flag_stats = NULL; const char *flag_devices = "skip"; const char *flag_directories = "skip"; const char *flag_label = "(standard input)";@@ -619,9 +626,16 @@ inline void read_line(reflex::AbstractMatcher *matcher, const std::string& line) } // copy color buffers-inline void copy_color(char to[COLORLEN], char from[COLORLEN])+inline void copy_color(char to[COLORLEN], const char from[COLORLEN]) {- memcpy(to, from, COLORLEN);+ size_t len = std::min(strlen(from), static_cast<size_t>(COLORLEN - 1));++ memcpy(to, from, len);+ to[len] = '\0';++ char *comma = strchr(to, ',');+ if (comma != NULL)+ *comma = '\0'; } // grep manages output, matcher, input, and decompression@@ -2328,7 +2342,15 @@ int main(int argc, const char **argv) #endif - options(argc, argv);+ try+ {+ options(argc, argv);+ }++ catch (std::exception& error)+ {+ abort("exception: ", error.what());+ } if (flag_query > 0) {@@ -2361,6 +2383,22 @@ int main(int argc, const char **argv) return warnings == 0 && Stats::found_any_file() ? EXIT_OK : EXIT_FAIL; } +static void set_depth(const char *arg)+{+ if (flag_max_depth > 0)+ {+ if (flag_min_depth == 0)+ flag_min_depth = flag_max_depth;+ flag_max_depth = strtopos(arg, "invalid argument --");+ if (flag_min_depth > flag_max_depth)+ help("invalid argument -", arg);+ }+ else+ {+ strtopos2(arg, flag_min_depth, flag_max_depth, "invalid argument --", true);+ }+}+ // parse the command-line options void options(int argc, const char **argv) {@@ -2593,9 +2631,15 @@ void options(int argc, const char **argv) else if (strncmp(arg, "sort=", 5) == 0) flag_sort = arg + 5; else if (strcmp(arg, "stats") == 0)- flag_stats = true;+ flag_stats = "";+ else if (strncmp(arg, "stats=", 6) == 0)+ flag_stats = arg + 6; else if (strncmp(arg, "tabs=", 5) == 0) flag_tabs = strtopos(arg + 5, "invalid argument --tabs=");+ else if (strcmp(arg, "tag") == 0)+ flag_tag = DEFAULT_TAG;+ else if (strncmp(arg, "tag=", 4) == 0)+ flag_tag = arg + 4; else if (strcmp(arg, "text") == 0) flag_binary_files = "text"; else if (strcmp(arg, "ungroup") == 0)@@ -2610,28 +2654,10 @@ void options(int argc, const char **argv) flag_word_regexp = true; else if (strcmp(arg, "xml") == 0) flag_xml = true;+ else if (isdigit(*arg))+ set_depth(arg); else- {- if (isdigit(*arg))- {- if (flag_max_depth > 0)- {- if (flag_min_depth == 0)- flag_min_depth = flag_max_depth;- flag_max_depth = strtopos(arg, "invalid argument --");- if (flag_min_depth > flag_max_depth)- help("invalid argument -", arg);- }- else- {- strtopos2(arg, flag_min_depth, flag_max_depth, "invalid argument --", true);- }- }- else- {- help("invalid option --", arg);- }- }+ help("invalid option --", arg); is_grouped = false; break; @@ -3649,7 +3675,7 @@ void terminal() } // whether to apply colors- flag_apply_color = flag_query > 0 ? "always" : flag_color;+ flag_apply_color = flag_tag != NULL ? "never" : flag_query > 0 ? "always" : flag_color; if (!flag_quiet) {@@ -3680,7 +3706,12 @@ void terminal() if (flag_query > 0) {- // --query: enable --line-buffered to flush output to the pager immediately+ // --query: run the interactive query UI++ // enable --heading+ flag_heading = true;++ // enable --line-buffered to flush output immediately flag_line_buffered = true; } else if (flag_pager != NULL)@@ -3816,8 +3847,10 @@ void terminal() if (*color_mc == '\0') copy_color(color_mc, color_mt); - color_del = "\033[K"; color_off = "\033[m";+ color_del = "\033[K";++ copy_color(match_off, color_off); if (isatty(STDERR_FILENO)) {@@ -3920,6 +3953,18 @@ void ugrep() size_t from = 0; size_t to; + // replace all \E in pattern with \E\\E\Q+ if (flag_fixed_strings)+ {+ while ((to = pattern.find("\\E", from)) != std::string::npos)+ {+ pattern.insert(to + 2, "\\\\E\\Q");+ from = to + 7;+ }+ }++ from = 0;+ // split regex at newlines, for -F add \Q \E to each string, separate by | while ((to = pattern.find('\n', from)) != std::string::npos) {@@ -3950,16 +3995,40 @@ void ugrep() { copy_color(match_ms, color_sl); copy_color(match_mc, color_cx);+ copy_color(match_off, color_off); } else {- copy_color(match_ms, color_ms);- copy_color(match_mc, color_mc);- }+ // --tag: tag matches instead of colors+ if (flag_tag != NULL)+ {+ const char *s1 = strchr(flag_tag, ',');+ const char *s2 = s1 != NULL ? strchr(s1 + 1, ',') : NULL; - // --heading: enable --break- if (flag_heading)- flag_break = true;+ copy_color(match_ms, flag_tag);++ if (s1 == NULL)+ {+ copy_color(match_mc, flag_tag);+ copy_color(match_off, flag_tag);+ }+ else+ {+ copy_color(match_off, s1 + 1);++ if (s2 == NULL)+ copy_color(match_mc, match_ms);+ else+ copy_color(match_mc, s2 + 1);+ }+ }+ else+ {+ copy_color(match_ms, color_ms);+ copy_color(match_mc, color_mc);+ copy_color(match_off, color_off);+ }+ } // the regex compiled from -N PATTERN std::string neg_regex;@@ -4093,7 +4162,6 @@ void ugrep() reflex::BufferedInput input(file); std::string line;- size_t lineno = 0; while (true) {@@ -4101,8 +4169,6 @@ void ugrep() if (getline(input, line)) break; - ++lineno;- trim_nl(line); // add line to the regex if not empty@@ -4207,6 +4273,10 @@ void ugrep() flag_count = false; } + // --heading: enable --break when filenames are shown+ if (flag_heading && flag_with_filename)+ flag_break = true;+ // -J: when not set the default is the number of cores (or hardware threads), limited to MAX_JOBS if (flag_jobs == 0) {@@ -4269,6 +4339,13 @@ void ugrep() if (!flag_quiet && flag_format_begin != NULL) format(flag_format_begin, 0); + size_t nodes = 0;+ size_t edges = 0;+ size_t words = 0;+ size_t nodes_time = 0;+ size_t edges_time = 0;+ size_t words_time = 0;+ // -P: Perl matching with Boost.Regex if (flag_perl_regexp) {@@ -4381,6 +4458,13 @@ void ugrep() grep.ugrep(); reset_handle(); }++ nodes = pattern.nodes();+ edges = pattern.edges();+ words = pattern.words();+ nodes_time = static_cast<size_t>(pattern.nodes_time());+ edges_time = static_cast<size_t>(pattern.parse_time() + pattern.edges_time());+ words_time = static_cast<size_t>(pattern.words_time()); } // --format-end@@ -4388,9 +4472,14 @@ void ugrep() format(flag_format_end, Stats::found_parts()); // --stats: display stats when we're done- if (flag_stats)+ if (flag_stats != NULL)+ { Stats::report(); + if (strcmp(flag_stats, "vm") == 0 && words > 0)+ fprintf(output, "VM memory: %zu nodes (%zums), %zu edges (%zums), %zu opcode words (%zums)\n", nodes, nodes_time, edges, edges_time, words, words_time);+ }+ // close the pipe to the forked pager if (flag_pager != NULL && output != NULL && output != stdout) pclose(output);@@ -5574,7 +5663,7 @@ void Grep::search(const char *pathname) { out.str(match_ms); out.str(from, to - from + 1);- out.str(color_off);+ out.str(match_off); if (to + 1 <= begin + size) out.header(pathname, partname, ++lineno, NULL, matcher->first() + (to - begin) + 1, "|", false);@@ -5588,7 +5677,7 @@ void Grep::search(const char *pathname) out.str(match_ms); out.str(begin, size);- out.str(color_off);+ out.str(match_off); if (size == 0 || begin[size - 1] != '\n') out.chr('\n');@@ -5745,7 +5834,7 @@ void Grep::search(const char *pathname) { out.str(match_ms); out.str(from, to - from + 1);- out.str(color_off);+ out.str(match_off); if (to + 1 <= begin + size) out.header(pathname, partname, lineno + num, NULL, first + (to - begin) + 1, "|", false);@@ -5760,7 +5849,7 @@ void Grep::search(const char *pathname) out.str(match_ms); out.str(begin, size);- out.str(color_off);+ out.str(match_off); if (flag_ungroup) {@@ -5831,7 +5920,7 @@ void Grep::search(const char *pathname) { out.str(match_ms); out.str(from, to - from + 1);- out.str(color_off);+ out.str(match_off); if (to + 1 <= begin + size) out.header(pathname, partname, lineno + num, NULL, first + (to - begin) + 1, "|", false);@@ -5846,7 +5935,7 @@ void Grep::search(const char *pathname) out.str(match_ms); out.str(begin, size);- out.str(color_off);+ out.str(match_off); } if (lines == 1)@@ -6095,7 +6184,7 @@ void Grep::search(const char *pathname) { out.str(match_mc); out.str(matcher->begin(), matcher->size());- out.str(color_off);+ out.str(match_off); } } else@@ -6234,7 +6323,7 @@ void Grep::search(const char *pathname) { out.str(match_mc); out.str(matcher->begin(), matcher->size());- out.str(color_off);+ out.str(match_off); } } @@ -6424,7 +6513,7 @@ void Grep::search(const char *pathname) out.str(color_off); out.str(match_ms); out.str(matcher->begin(), matcher->size());- out.str(color_off);+ out.str(match_off); out.str(color_sl); out.str(lines[current].c_str() + matcher->last(), lines[current].size() - matcher->last()); out.str(color_off);@@ -6477,7 +6566,7 @@ void Grep::search(const char *pathname) out.str(color_off); out.str(match_ms); out.str(matcher->begin(), matcher->size());- out.str(color_off);+ out.str(match_off); } } @@ -7203,9 +7292,7 @@ void help(const char *message, const char *arg) #ifdef OS_WIN std::cout << "Windows system and "; #endif- std::cout << "hidden files and directories.\n";-#ifndef OS_WIN- std::cout << "\+ std::cout << "hidden files and directories.\n\ -I\n\ Ignore matches in binary files. This option is equivalent to the\n\ --binary-files=without-match option.\n\@@ -7323,9 +7410,7 @@ void help(const char *message, const char *arg) each file processed.\n\ --no-group-separator\n\ Removes the group separator line from the output for context\n\- options -A, -B, and -C.\n";-#endif- std::cout << "\+ options -A, -B, and -C.\n\ -O EXTENSIONS, --file-extensions=EXTENSIONS\n\ Search only files whose filename extensions match the specified\n\ comma-separated list of EXTENSIONS, same as --include='*.ext' for\n\@@ -7371,7 +7456,7 @@ void help(const char *message, const char *arg) the default is 5 (0.5s delay). Initial patterns may be specified\n\ with -e PATTERN, i.e. a PATTERN argument requires option -e. Press\n\ F1 or CTRL-Z to view the help screen. No whitespace may be given\n\- between -Q and its argument DELAY.\n\+ between -Q and its argument DELAY. Enables --heading.\n\ -q, --quiet, --silent\n\ Quiet mode: suppress all output. ugrep will only search until a\n\ match has been found, making searches potentially less expensive.\n\@@ -7428,6 +7513,9 @@ void help(const char *message, const char *arg) --tabs=NUM\n\ Set the tab size to NUM to expand tabs for option -k. The value of\n\ NUM may be 1, 2, 4, or 8. The default tab size is 8.\n\+ --tag[=TAG[,END]]\n\+ Disables colors to mark up matches with TAG. If END is specified,\n\+ the end of a match is marked with END. The default is `___'.\n\ -U, --binary\n"; #ifdef OS_WIN std::cout << "\
@@ -207,7 +207,6 @@ extern bool flag_decompress; extern bool flag_any_line; extern bool flag_heading; extern bool flag_break;-extern bool flag_stats; extern bool flag_cpp; extern bool flag_csv; extern bool flag_json;@@ -241,6 +240,7 @@ extern size_t flag_max_mmap; extern size_t flag_min_steal; extern const char *flag_pager; extern const char *flag_color;+extern const char *flag_tags; extern const char *flag_apply_color; extern const char *flag_hexdump; extern const char *flag_colors;@@ -252,6 +252,7 @@ extern const char *flag_format_end; extern const char *flag_format_open; extern const char *flag_format_close; extern const char *flag_sort;+extern const char *flag_stats; extern const char *flag_devices; extern const char *flag_directories; extern const char *flag_label;@@ -309,11 +310,12 @@ extern char color_cn[COLORLEN]; // column number extern char color_bn[COLORLEN]; // byte offset extern char color_se[COLORLEN]; // separator -extern char match_ms[COLORLEN]; // --match: matched text in a selected line-extern char match_mc[COLORLEN]; // --match: matched text in a context line+extern char match_ms[COLORLEN]; // --match or --tag: matched text in a selected line+extern char match_mc[COLORLEN]; // --match or --tag: matched text in a context line+extern char match_off[COLORLEN]; // --match or --tag: off -extern const char *color_del; // erase line after the cursor-extern const char *color_off; // disable colors+extern const char *color_off; // disable colors+extern const char *color_del; // erase line after the cursor // check TTY availability and set colors extern void terminal();
tests/out/lorem.latin1.out
@@ -1 +1 @@-14+18
tests/out/lorem.utf16.out
@@ -1 +1 @@-14+18
tests/out/lorem.utf32.out
@@ -1 +1 @@-14+18
tests/out/lorem.utf8.out
@@ -1 +1 @@-14+18