/proc/self/root/proc/thread-self/root/proc/self/root/usr/share/doc/grep
This explorer reads the filesystem of the server it runs on, so /workspace/user isn't present here. Browsing and the terminal still work against this server's own disk from /.
Things to do for GNU grep Copyright (C) 1992, 1997-2002, 2004-2022 Free Software Foundation, Inc. Copying and distribution of this file, with or without modification, are permitted in any medium without royalty provided the copyright notice and this notice are preserved. ===============Short term work=============== See where we are with UTF-8 performance. Merge Debian patches that seem relevant. Go through patches in Savannah. Fix --directories=read. Write better Texinfo documentation for grep. The manual page would be agood place to start, but Info documents are also supposed to contain atutorial and examples. Some tests in tests/spencer2.tests should have failed! Need to filter outsome bugs in dfa.[ch]/regex.[ch]. Multithreading? GNU grep originally did 32-bit arithmetic. Although it has moved to64-bit on 64-bit platforms by using types like ptrdiff_t and size_t,this conversion has not been entirely systematic and should be checked. Lazy dynamic linking of the PCRE library. Check FreeBSD’s integration of zgrep (-Z) and bzgrep (-J) in onebinary. Is there a possibility of doing even better by automaticallychecking the magic of binary files ourselves (0x1F 0x8B for gzip, 0x1F0x9D for compress, and 0x42 0x5A 0x68 for bzip2)? Once what to do withthe PCRE library is decided, do the same for libz and libbz2. ===================Matching algorithms=================== Take a look at these and consider opportunities for merging or cloning: -- http://osrd.org/projects/grep/global-regular-expression-print-tools-grep-variants -- ja-grep’s mlb2 patch (Japanese grep) <http://distcache.freebsd.org/ports-distfiles/grep-2.4.2-mlb2.patch.gz> -- lgrep (from lv, a Powerful Multilingual File Viewer / Grep) <http://www.mt.cs.keio.ac.jp/person/narita/lv/>; -- cgrep (Context grep) <https://awgn.github.io/cgrep/> seems like nice work; -- sgrep (Struct grep) <https://www.cs.helsinki.fi/u/jjaakkol/sgrep.html>; -- agrep (Approximate grep) <https://www.tgries.de/agrep/>, from glimpse; -- nr-grep (Nondeterministic reverse grep) <https://www.dcc.uchile.cl/~gnavarro/software/>; -- ggrep (Grouse grep) <http://www.grouse.com.au/ggrep/>; -- freegrep <https://github.com/howardjp/freegrep>; Check some new algorithms for matching. See, for example, Faro &Lecroq (cited in kwset.c). Fix the DFA matcher to never use exponential space. (Fortunately, thesecases are rare.) ============================Standards: POSIX and Unicode============================ For POSIX compliance issues, see POSIX 1003.1. Current support for the POSIX [= =] and [. .] constructs is limited toplatforms whose regular expression matchers are sufficientlycompatible with the GNU C library so that the --without-included-regexoption of ‘configure’ is in effect. Extend this support to non-glibcplatforms, where --with-included-regex is in effect, by modifying theincluded version of the regex code to defer to the native version whenhandling [= =] and [. .]. For Unicode, interesting things to check include the Unicode Standard<https://www.unicode.org/standard/standard.html> and the Unicode TechnicalStandard #18 (<https://www.unicode.org/reports/tr18/> “Unicode RegularExpressions”). Talk to Bruno Haible who’s maintaining GNU libunistring.See also Unicode Standard Annex #15 (<https://www.unicode.org/reports/tr15/>“Unicode Normalization Forms”), already implemented by GNU libunistring. In particular, --ignore-case needs to be evaluated against the standards.We may want to deviate from POSIX if Unicode provides better or clearersemantics. POSIX and --ignore-case----------------------- For this issue, interesting things to check in POSIX include theOpen Group Base Specifications, Chapter “Regular Expressions”, inparticular Section “Regular Expression General Requirements” and itsparagraph about caseless matching (this may not have been fullythought through and that this text may be self-contradicting[specifically: “of either data or patterns” versus all the rest]).See: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html#tag_09_02 In particular, consider the following with POSIX’s approach to casefolding in mind. Assume a non-Turkic locale with a characterrepertoire reduced to the following various forms of “LATIN LETTER I”: 0049;LATIN CAPITAL LETTER I;Lu;0;L;;;;;N;;;;0069; 0069;LATIN SMALL LETTER I;Ll;0;L;;;;;N;;;0049;;0049 0130;LATIN CAPITAL LETTER I WITH DOT ABOVE;Lu;0;L;0049 0307;;;;N;\ LATIN CAPITAL LETTER I DOT;;;0069; 0131;LATIN SMALL LETTER DOTLESS I;Ll;0;L;;;;;N;;;0049;;0049 UTF-8 octet lengths differ between U+0049 (0x49) and U+0069 (0x69)versus U+0130 (0xC4 0xB0) and U+0131 (0xC4 0xB1). This implies thatwhole UTF-8 strings cannot be case-converted in place, using the samememory buffer, and that the needed octet-size of the new buffer cannotmerely be guessed (although there’s a simple upper bound of five timesthe size of the input, as the longest UTF-8 encoding of any characteris five bytes). We have lc(I) = i, uc(I) = I lc(i) = i, uc(i) = I lc(İ) = i, uc(İ) = İ lc(ı) = ı, uc(ı) = I where lc() and uc() denote lower-case and upper-case conversions. There are several candidate --ignore-case logics. Using the if (lc(input_wchar) == lc(pattern_wchar)) logic leads to the following matches: \in I i İ ı pat\ ---------- I | Y Y Y n i | Y Y Y n İ | Y Y Y n ı | n n n Y There is a lack of symmetry between CAPITAL and SMALL LETTERs withthis. Using the if (uc(input_wchar) == uc(pattern_wchar)) logic (which is what GNU grep currently does although this is notdocumented or guaranteed in the future), leads to the followingmatches: \in I i İ ı pat\ ---------- I | Y Y n Y i | Y Y n Y İ | n n Y n ı | Y Y n Y There is a lack of symmetry between CAPITAL and SMALL LETTERs withthis. Using the if (lc(input_wchar) == lc(pattern_wchar) || uc(input_wchar) == uc(pattern_wchar)) logic leads to the following matches: \in I i İ ı pat\ ---------- I | Y Y Y Y i | Y Y Y Y İ | Y Y Y n ı | Y Y n Y There is some elegance and symmetry with this. But there arepotentially two conversions to be made per input character. If thepattern is pre-converted, two copies of it need to be kept and used ina mutually coherent fashion. Using the if (input_wchar == pattern_wchar || lc(input_wchar) == pattern_wchar || uc(input_wchar) == pattern_wchar) logic (a plausible interpretation of POSIX) leads to the followingmatches: \in I i İ ı pat\ ---------- I | Y Y n Y i | Y Y Y n İ | n n Y n ı | n n n Y There is a different CAPITAL/SMALL symmetry with this. But there’salso a loss of pattern/input symmetry that’s unique to it. Also thereare potentially two conversions to be made per input character. Using the if (lc(uc(input_wchar)) == lc(uc(pattern_wchar))) logic leads to the following matches: \in I i İ ı pat\ ---------- I | Y Y Y Y i | Y Y Y Y İ | Y Y Y Y ı | Y Y Y Y This shows total symmetry and transitivity (at least in this exampleanalysis). There are two conversions to be made per input character,but support could be added for having a single straight mappingperforming a composition of the two conversions. Any optimization in the implementation of each logic must not changeits basic semantic. Unicode and --ignore-case------------------------- For this issue, interesting things to check in Unicode include: - The Unicode Standard, Chapter 3 (<https://www.unicode.org/versions/Unicode9.0.0/ch03.pdf> “Conformance”), Section 3.13 (“Default Case Algorithms”) and the toCasefold() case conversion operation. - The Unicode Standard, Chapter 4 (<https://www.unicode.org/versions/Unicode9.0.0/ch04.pdf> “Character Properties”), Section 4.2 (“Case”) and the <https://www.unicode.org/Public/UNIDATA/SpecialCasing.txt> SpecialCasing.txt and <https://www.unicode.org/Public/UNIDATA/CaseFolding.txt> CaseFolding.txt files. - The Unicode Standard, Chapter 5 (<https://www.unicode.org/versions/Unicode9.0.0/ch05.pdf> “Implementation Guidelines”), Section 5.18 (“Case Mappings”), Subsection “Caseless Matching”. - The Unicode case charts <https://www.unicode.org/charts/case/>. Unicode uses the if (toCasefold(input_wchar_string) == toCasefold(pattern_wchar_string)) logic for caseless matching. Consider the “LATIN LETTER I” examplementioned above. In a non-Turkic locale, simple case folding yields toCasefold_simple(U+0049) = U+0069 toCasefold_simple(U+0069) = U+0069 toCasefold_simple(U+0130) = U+0130 toCasefold_simple(U+0131) = U+0131 which leads to the following matches: \in I i İ ı pat\ ---------- I | Y Y n n i | Y Y n n İ | n n Y n ı | n n n Y This is different from anything so far! In a non-Turkic locale, full case folding yields toCasefold_full(U+0049) = U+0069 toCasefold_full(U+0069) = U+0069 toCasefold_full(U+0130) = <U+0069, U+0307> toCasefold_full(U+0131) = U+0131 with 0307;COMBINING DOT ABOVE;Mn;230;NSM;;;;;N;NON-SPACING DOT ABOVE;;;; which leads to the following matches: \in I i İ ı pat\ ---------- I | Y Y * n i | Y Y * n İ | n n Y n ı | n n n Y This is just sad! Having toCasefold(U+0131), simple or full, map to itself instead ofU+0069 is in contradiction with the rules of Section 5.18 of theUnicode Standard since toUpperCase(U+0131) is U+0049. Same thing fortoCasefold_simple(U+0130) since toLowerCase(U+0131) is U+0069. Thejustification for the weird toCasefold_full(U+0130) mapping isunknown; it doesn’t even make sense to add a dot (U+0307) to a letterthat already has one (U+0069). It would have been so simple to putthem all in the same equivalence class! Otherwise, also consider the following problem with Unicode’s approachon case folding in mind. Assume that we want to perform echo 'AßBC' | grep -i 'Sb' which corresponds to input: U+0041 U+00DF U+0042 U+0043 U+000A pattern: U+0053 U+0062 Following CaseFolding.txt, applying the toCasefold() transformation tothese yields input: U+0061 U+0073 U+0073 U+0062 U+0063 U+000A pattern: U+0073 U+0062 so, according to this approach, the input should match the pattern.As long as the original input line is to be reported to the user as awhole, there is no problem (from the user’s point-of-view;implementation is complicated by this). However, consider both these GNU extensions: echo 'AßBC' | grep -i --only-matching 'Sb' echo 'AßBC' | grep -i --color=always 'Sb' What is to be reported in these cases, since the match begins in the*middle* of the original input character ‘ß’? Unicode’s toCasefold() cannot be implemented in terms of POSIX’stowctrans() since that can only return a single wint_t value per inputwint_t value.